Stable Sensor Network (SSN): A Dynamic Clustering Technique for Maximizing Stability in Wireless Sensor Networks

A. B. M. Alim Al Islam, Chowdhury Sayeed Hyder, Humayun Kabir, Mahmuda Naznin

.

DOI: 10.4236/wsn.2010.27066                

Abstract

Stability is one of the major concerns in advancement of Wireless Sensor Networks (WSN). A number of applications of WSN require guaranteed sensing, coverage and connectivity throughout its operational period. Death of the first node might cause instability in the network. Therefore, all of the sensor nodes in the network must be alive to achieve the goal during that period. One of the major obstacles to ensure these phenomena is unbalanced energy consumption rate. Different techniques have already been proposed to improve energy consumption rate such as clustering, efficient routing, and data aggregation. However, most of them do not consider the balanced energy consumption rate which is required to improve network stability. In this paper, we present a novel technique, Stable Sensor Network (SSN) to achieve balanced energy consumption rate using dynamic clustering to guarantee stability in WSN. Our technique is based on LEACH (Low-Energy Adaptive Clustering Hierarchy), which is one of the most widely deployed simple and effective clustering solutions for WSN. We present three heuristics to increase the time before the death of first sensor node in the network. We devise the algorithm of SSN based on those heuristics and also formulate its complete mathematical model. We verify the efficiency of SSN and correctness of the mathematical model by simulation results. Our simulation results show that SSN significantly improves network stability period compared to LEACH and its best variant.

Keywords

Network Stability Period, Clustering, Energy Consumption Rate

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. B. Heinzelman, A. P. Chandrakasan and H. Balakrishnan, “Energy Efficient Communication Protocol for Wireless Microsensor Networks,” Proceedings of the Hawaii International Conference on System Sciences, Maui, Vol. 2, January 2000, pp. 1-10.
[2]	J. Han and K. Micheline, “Data Mining: Concepts and Techniques,” 2nd Edition, Morgan Kauffman, Elsevier, San Francisco, 2001.
[3]	S. Basagni, “Distributed Clustering Algorithm for AdHoc Networks,” Proceedings of International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), Perth, 1999, pp. 310-315.
[4]	S. Banerjee and S. Khuller, “A Clustering Scheme for Hierarchical Control in Multi-Hop Wireless Networks,” Proceedings of IEEE INFOCOM, Anchorage, 2001, pp. 1028-1037.
[5]	M. Gerla, T. J. Kwon and G. Pei, “On Demand Routing in Large Ad Hoc Wireless Networks with Passive Clustering,” Proceedings of IEEE WCNC, Chicago, Vol. 1, 2000, pp. 100-105.
[6]	C. R. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Areas in Communications, Vol. 15, No. 7, 1997, pp. 1265-1275.
[7]	J. Kamimura, N. Wakamiya and M. Murata, “Energy-Efficient Clustering Method for Data Gathering in Sensor Networks,” Proceedings of Workshop on Broadband Advanced Sensor Networks, San Diego, Vol. 103, 2004, pp. 31-36.
[8]	J. Leu, M. H. Tsai, T. C. Chiang and H. Y. M. Huang, “Adaptive Power Aware Clustering and Multicasting Protocol for Mobile Ad Hoc Networks,” Lecture Notes in Computer Science, Vol. 4159, September 2006, pp. 331340.
[9]	S. Lindsey and C. S. Raghavendra, “PEGASIS: PowerEfficient Gathering in Sensor Information Systems,” IEEE Aerospace Conference Proceedings, Big Sky, Vol. 3, 2002, pp. 1125-1130.
[10]	L. Li, S. Dong and X. Wen, “An Energy Efficient Clustering Routing Algorithm for Wireless Sensor Networks,” Journal of China Universities of Posts and Telecommunications, Vol. 3, No. 13, September 2006, pp. 71-75.
[11]	Y. Sangho, H. Junyoung, C. Yookun and H. Jiman, “PEACH: Power-Efficient and adaptive Clustering Hierarchy Protocol for Wireless Sensor Networks,” Computer Communications, Vol. 30, No. 14-15, 2007, pp. 28422852.
[12]	S. Ghiasi, A. Srivastava, X. Yang and M. Sarrafzadeh, “Optimal Energy Aware Clustering in Sensor Networks,” Sensors Journal, Vol. 2, No. 7, 2002, pp. 258-269.
[13]	H. Chan and A. Perrig, “ACE: An Emergent Algorithm for Highly Uniform Cluster Formation,” Lecture Notes in Computer Science, Springer Berlin/Heidelberg, Vol. 2920, February 2004, pp. 154-171.
[14]	O. Younis and S. Fahmy, “Distributed Clustering in Adhoc Sensor Networks: A Hybrid, Energy-Efficient Approach,” Proceedings of IEEE INFOCOM, Hong Kong, Vol. 1, 2004, pp. 629-640.
[15]	J. Y. Cheng, S. J. Ruan, R. G. Cheng and T. T. Hsu, “PADCP: Poweraware Dynamic Clustering Protocol for Wireless Sensor Network,” IFIP International Conference on Wireless and Optical Communications Networks, Bangalore, 13 April 2006, pp. 1-6.
[16]	G. Smaragdakis, I. Matta and A. Bestavros, “SEP: A Stable Election Protocol for Clustered Heterogeneous Wireless Sensor Networks,” Proceedings of Second International Workshop on Sensor and Actor Network Protocols and Applications (SANPA), Boston, 2004, pp. 251261.
[17]	M. Haase and D. Timmermann, “Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection,” 4th International Workshop on Mobile and Wireless Communications Network, San Jose, 2002, pp. 368-372.
[18]	W. B. Heinzelman, A. P. Chandrakasan and H. Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, Vol. 14, No. 4, October 2002, pp. 660-670.
[19]	C. Nam, H. Jeong and D. Shin, “The Adaptive Cluster Head Selection in Wireless Sensor Networks,” Proceedings of the IEEE International Workshop on Semantic Computing and Applications, Incheon, 2008, pp. 147149.
[20]	A. Giridhar and P. R. Kumar, “Maximizing the Functional Lifetime of Sensor Networks,” Fourth International Symposium on Information Processing in Sensor Networks, Los Angeles, 15 April 2005, pp. 5-12.
[21]	X. Wang, W. Gu, S. Chellappan, K. Schosek and D. Xuan, “Lifetime Optimization of Sensor Networks under Physical Attacks,” Proceedings of IEEE International Conference on Communications (ICC), Seoul, Vol. 5, May 2005, pp. 3295-3301.
[22]	H. Zhang and J. C. Hou, “Maximizing α-Lifetime for Wireless Sensor Networks,” 3rd International Workshop on Measurement, Modeling, and Performance Analysis of Wireless Sensor Networks, San Diego, 21 July 2005, pp. 70-77.
[23]	V. Rai and R. N. Mahapatra, “Lifetime Modeling of a Sensor Network,” Proceedings of Design, Automation and Test in Europe, Munich, Vol. 1, 7-11 March 2005, pp. 202-203.
[24]	M. U. Ilyas and H. Radha, “Increasing Network Lifetime of an IEEE 802.15.4 Wireless Sensor Network by Energy Efficient Routing,” IEEE International Conference on Communications, Istanbul, Vol. 9, June 2006, pp. 39783983.
[25]	L. Shi, A. Capponi, K. H. Johansson and R. M. Murray, “Sensor Network Lifetime Maximization Via Sensor Trees Construction and Scheduling,” Third International Workshop on Feedback Control Implementation and Design in Computing Systems and Networks, Annapolis, June 2008.
[26]	P. Berman, G. Calinescu, C. Shah and A. Zelikovsky, “Power Efficient Monitoring Management in Sensor Networks,” IEEE Wireless Communication and Networking Conference, Atlanta, March 2004, pp. 23292334.
[27]	D. Brinza and A. Zelikovsky, “DEEPS: Deterministic Energy-Efficient Protocol for Sensor Networks,” 2nd ACIS International Workshop on Self-Assembling Wireless Networks, Las Vegas, 2006, pp. 261-266.
[28]	A. Aung, “Distributed Algorithms for Improving Wireless Sensor Network Lifetime with Adjustable Sensing Range,” M.S. Thesis, Georgia State University, 2007.
[29]	S. G. Akojwar and R. M. Patrikar, “Improving Life Time of Wireless Sensor Networks Using Neural Network Based Classification Techniques with Cooperative Routing,” International Journal of Communications, Vol. 1, No. 2, 2008, pp. 75-86.
[30]	Y. Chen, Q. Zhao, V. Krishnamurthy and D. Djonin, “Transmission Scheduling For Sensor Network Lifetime Maximization: A Shortest Path Bandit Formulation,” Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, Toulouse, May 2006, pp. 145-148.
[31]	K. Dasgupta, K. Kalpakis and P. Namjoshi, “Improving the Lifetime of Sensor Networks via Intelligent Selection of Data Aggregation Trees,” Proceedings of the Communication Networks and Distributed Systems Modeling and Simulation Conference, 2003, pp. 19-23.
[32]	H. Kang and X. Li, “Power-Aware Sensor Selection in Wireless Sensor Networks,” Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN), 2006.
[33]	M. Cardei and D. Du, “Summary on Improving Wireless Sensor Network Lifetime through Power Aware Organization,” Seminar on Theoretical Computer Science, Wireless Networks, Vol. 11, No. 3, 2005, pp. 333-340.
[34]	J. Park and S. Sahni, “An Online Heuristic for Maximum Lifetime Routing in Wireless Sensor Networks,” IEEE Transactions on Computers, Vol. 55, No. 8, August 2006, pp. 1048-1056.
[35]	J. Chang and L. Tassiulas, “Maximum Lifetime Routing in Wireless Sensor Networks,” IEEE/ACM Transactions on Networking, Vol. 12, No. 4, 2004, pp. 609-619.
[36]	P. Djukic and S. Valaee, “Maximum Network Lifetime in Fault Tolerant Sensor Networks,” IEEE Global Telecommunications Conference, GLOBECOM’ 05, St. Louis, Vol. 5, December 2005, pp. 3106-3011.
[37]	Y. T. Hou, Y. Shi, H. D. Sherali and S. F. Midkiff, “Prolonging Sensor Network Lifetime with Energy Provisioning and Relay Node Placement,” 2nd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, Santa Clara, September 2005, pp. 295-304.
[38]	M. Cardei, J. Wu, M. Lu and M. O. Pervaiz, “Maximum Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges,” IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, Montreal, Vol. 3, August 2005, pp. 438-445.
[39]	K. Kalpakis, K. Dasgupta and P. Namjoshi, “Efficient Algorithms for Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks,” Computer Networks, Vol. 42, No. 6, 2003, pp. 697-716.
[40]	R. Madan and S. Lall, “Distributed algorithms for maximum lifetime routing in wireless sensor networks,” IEEE Transactions on Wireless Communications, Vol. 5, No. 8, August 2006, pp. 2185-2193.
[41]	J. C. Choi and C. W. Lee, “Energy Modeling for the Cluster-based Sensor Networks,” Proceedings of the 6th IEEE International Conference on Computer and Information Technology, Seoul, September 2006, p. 218.
[42]	S. Selvakennedy and S. Sinnappan, “An Energy-Efficient Clustering Algorithm for Multihop Data Gathering in Wireless Sensor Networks,” Journal of Computers, Vol. 1, No. 1, April 2006, pp. 40-47.
[43]	A. B. M. A. A. Islam, “A Novel Approach To Cluster Heterogeneous Sensor Network (CHSN),” MSc Engineering Thesis, Vol. 4, May 2009, pp. 31-41.
[44]	A. B. M. A. A. Islam, C. S. Hyder, M. H. Kabir and M. Naznin, “Finding the Optimal Percentage of Cluster Heads from a New and Complete Mathematical Model on LEACH,” Wireless Sensor Network, Vol. 2, No. 2, February 2010.pp. 129-140.
[45]	W. B. Heinzelman, A. P. Chandrakasan and H. Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, Vol. 1, No. 4, 2002, pp. 660-670.
[46]	D. Song, “Probabilistic Modeling of Leach Protocol and Computing Sensor Energy Consumption Rate in Sensor Networks,” Technical Report, Texas A & M University, February 2005.
[47]	T. Murata and H. Ishibuchi, “Performance Evaluation of Genetic Algorithms for Flowshop Scheduling Problems,” Proceedings of 1st IEEE Conference Evolutionary Computation, Orlando, Vol. 2, June 1994, pp. 812-817.
[48]	G. E. P. Box and M. E. Muller, “A Note on the Generation of Random Normal Deviates,” Annals of Mathematical Statistics, Vol. 29, No. 2, 1958, pp. 610-611.