Packet Compression Ratio Dependent Spanning Tree for Convergecast

Changjin Suh, Jisoo Shin
DOI: 10.4236/wsn.201027062                

Abstract

A convergecast is a popular routing in sensor networks. It periodically forwards collected data at every sensor node along a configured routing path to the outside of a sensor network via the base station (BS). To extend the lifetime of energy-limited sensor networks, many previous researches proposed schemes for data compression. However, few researches investigated the relation between packet compression ratio and spanning trees. We propose packet Compression ratio dependent Spanning Tree (CST) which can provide effective routing paths in terms of the tree length for all ranges of compression ratio f. CST is equivalent to the Shortest Path spanning Tree (SPT) which is optimum in the case of no-compression (f = 0) and is equivalent to the Minimum Spanning Tree (MST) in the case of full-compression (f = 1). CST outperforms SPT and MST for any range of f (0 < f < 1). Through simulation we show CST provides shorter paths than MST and SPT in terms of the tree length by 34.1% and 7.8% respectively. We confirm CST is very useful in convergecasts.

Keywords

Packet Compression, Convergecast, CST, Spanning Tree, Sensor Network

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. N. Al-Karaki and A. E. Kamal, “Routing Techniques in Wireless Sensor Networks: A Survey,” IEEE Wireless Communications, Vol. 11, No. 6, December 2004, pp. 6-28.
[2]	J. N. Al-Karaki, R. Ul-Mustafa and A. E. Kamal, “Data Aggregation in Wireless Sensor Networks—Exact and Approximate Algorithms,” Proceedings of IEEE Workshop on High Performance Switching and Routing (HPSR), Phoenix, April 2004, pp. 18-21.
[3]	I. Demirkol, C. Ersoy and F. Alagoz, “MAC Protocols for Wireless Sensor Networks: A Survey,” IEEE Communication Magazine, Vol. 44, No. 4, April 2006, pp. 115-121.
[4]	R. Vidhyapriya and P. T. Vanathi, “Conserving Energy in Wireless Sensor Networks,” IEEE Potentials, Vol. 26, No. 5, 2007, pp. 37-42.
[5]	C.-K. Liang, Y.-J. Huang and J.-D. Lin, “An Energy Efficient Routing Scheme in Wireless Sensor Networks,” 22nd International Conference on Advanced Information Networking and Applications (AINAW), Okinawa, March 2008, pp. 916-921.
[6]	L. K. Lawrence, “Sensor and Data Fusion Concept and Applications,” 2nd Edition, SPIE Optical Engineering Press, Bellingham, 1999.
[7]	S. Upadhyayula and S. K. S. Gupta, “Spanning Tree based Algorithms for Low Latency and Energy Efficient Data Aggregation Enhanced Convergecast (DAC) in Wireless Sensor Networks,” Ad Hoc Networks, Vol. 5, No. 5, July 2007, pp. 626-648.
[8]	H. Luo, J. Luo, Y. Liu and S. K. Das, “Adaptive Data Fusion for Energy Efficient Routing in Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, Vol. 55, No. 10, October 2006, pp. 1286-1299.
[9]	H. Luo, J. Luo, Y. Liu and S. K. Das, “Routing Correlated Data with Fusion Cost in Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, Vol. 5, No. 11, November 2006, pp. 1620-1632.
[10]	H. C. Thomas, E. L. Charles, L. R. Ronald and S. Clifford, “Introduction to Algorithms,” 2nd Edition, MIT press, Cambridge, 2001.
[11]	R. C. Prim, “Shortest Connection Networks and some Generalizations,” Bell System Technical Journal, Vol. 36, 1957, pp. 1389-1401.