Energy and Throughput Optimized, Cluster Based Hierarchical Routing Algorithm for Heterogeneous Wireless Sensor Networks

Mahanth K Gowda, K. K. Shukla
DOI: 10.4236/ijcns.2011.45038                

Abstract

We propose a novel cluster based distributed routing algorithm in a generalized form for heterogeneous wireless sensor networks. Heterogeneity with respect to number/types of communication interfaces, their data rates and that with respect to energy dissipation model have been exploited for energy and throughput efficiency. The algorithm makes routing assignment optimized for throughput and energy and has a complexity of N/K*logN+k²logk approximately, where N is the number of nodes and k is the number of kcluster heads. Performance experiments confirm the effectiveness of throughput and energy optimizations. The importance of choosing an optimal cluster radius has been shown. The energy consumption in the network scales up well with respect to the network size.

Keywords

Routing Algorithm, Clustering, Heterogeneous Networks, WSN, Energy Efficiency

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. Qin and R. Zimmermann, “Studying Upper Bounds on Sensor Network Lifetime by Genetic Clustering,” Distributed Computing in Sensor Systems, Vol. 3560, 2005, p. 465. doi:10.1007/11502593_40
[2]	P. Ding, J. Holliday and A. Celik, “Distributed Energy-Effcient Hierarchical Clustering for Wireless Sensor Networks,” Distributed Computing in Sensor Systems, Vol. 3560, 2005, pp. 466-467. doi:10.1007/11502593_25
[3]	H. Chan and A. Perrig, “Ace: An Emergent Algorithm for Highly Uniform Cluster Formation,” Wireless Sensor Networks, Vol. 2920, 2004, pp. 154-171. doi:10.1007/978-3-540-24606-0_11
[4]	S. Hussain and A. W. Matin, “Hierarchical Cluster-Based Routing in Wireless Sensor Networks,” The 5th International Conference on Information Processing in Sensor Networks, Nashville, 19-21 April 2006.
[5]	W. Z. Wang, W.-Z. Song, X.-Y. Li and M.-N. Kosha, “Distributed Computing in Sensor Systems: Third IEEE International Conference,” Springer, Berlin, 2007.
[6]	S. Bandyopadhyay and E. J. Coyle, “An Energy Effcient Hierarchical Clustering Algorithm for Wireless Sensor Networks,” INFOCOM 2003 The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, 30 March - 3 April 2003, pp. 1713-1723.
[7]	A. Bari, A. Jaekel and S. Bandyopadhyay, “Clustering Strategies for Improving the Lifetime of Two-Tiered Sensor Networks,” Computer Communications, Vol. 31, No. 14, 2008, pp. 3451-3459. doi:10.1016/j.comcom.2008.05.038
[8]	A. Grama, A. Gupta, G. Karypis and V. Kumar, “Introduction to Parallel Computing,” Addison-Wesley Longman Publishing Co., Boston, 2003.
[9]	GNU Linear Programming Kit, 2011. http://www.gnu.org/software/glpk
[10]	The ns-3 Network Simulator, 2011. www.nsnam.org