Dynamic Clustering with Relay Nodes (DCRN): A Clustering Technique to Maximize Stability in Wireless Sensor Networks with Relay Nodes

A. B. M. Alim Al Islam, Mohammad Sajjad Hossain, Vijay Raghunathan

School of ECE, Purdue University, West Lafayette, USA.

DOI: 10.4236/ijcns.2012.56047                

Abstract

With the growing popularity of wireless sensor networks, network stability has become a key area of current research. Different applications of wireless sensor networks demand stable sensing, coverage, and connectivity throughout their operational periods. In some cases, the death of just a single sensor node might disrupt the stability of the entire network. Therefore, a number of techniques have been proposed to improve the network stability. Clustering is one of the most commonly used techniques in this regard. Most clustering techniques assume the presence of high power sensor nodes called relay nodes and implicitly assume that these relay nodes serve as cluster heads in the network. This assumption may lead to faulty network behavior when any of the relay nodes becomes unavailable to its followers. Moreover, relay node based clustering techniques do not address the heterogeneity of sensor nodes in terms of their residual energies, which frequently occur during the operation of a network. To address these two issues, we present a novel clustering technique, Dynamic Clustering with Relay Nodes (DCRN), by considering the heterogeneity in residual battery capacity and by removing the assumption that relay nodes always serve as cluster-heads. We use an essence of the underlying mechanism of LEACH (Low-Energy Adaptive Clustering Hierarchy), which is one of the most popular clustering solutions for wireless sensor networks. In our work, we present four heuristics to increase network stability periods in terms of the time elapsed before the death of the first node in the network. Based on the proposed heuristics, we devise an algorithm for DCRN and formulate a mathematical model for its long-term rate of energy consumption. Further, we calculate the optimal percentage of relay nodes from our mathematical model. Finally, we verify the efficiency of DCRN and correctness of the mathematical model by exhaustive simulation results. Our simulation results reveal that DCRN enhances the network stability period by a significant margin in comparison to LEACH and its best-known variant.

Keywords

Network Stability Period; Clustering; Energy Consumption Rate; Relay Node

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	I. Dietrich and F. Dressler, “On the Lifetime of Wireless Sensor Networks,” ACM Transactions on Sensor Networks (TOSN), Vol. 5, No. 1, 2009, pp. 1-39. doi:10.1145/1464420.1464425
[2]	W. B. Heinzelman, A. P. Chandrakasan and H. Balakrishnan, “Energy Efficient Communication Protocol for Wireless Microsensor Networks,” Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, 1-7 January 2000. doi:10.1109/HICSS.2000.926982
[3]	J. Han and K. Micheline, “Data Mining Concepts and Techniques,” Morgan Kauffman, Waltham, 2001.
[4]	S. Basagni, “Distributed Clustering Algorithm for ad-hoc Networks,” Proceedings of International Symposium on Parallel Architectures, Algorithms and Networks, Perth/ Fremantle, 23-25 June 1999, pp. 310-315. doi:10.1109/ISPAN.1999.778957
[5]	S. Banerjee and S. Khuller, “A Clustering Scheme for Hierarchical Control in Multi-Hop Wireless Networks,” Proceedings of Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, 22-26 April 2001, pp. 1028-1037.
[6]	M. Gerla, T. J. Kwon and G. Pei, “On Demand Routing in Large Ad Hoc Wireless Networks with Passive Clustering,” Proceeding of Wireless Communications and Networking Conference, Chicago, 23-28 September 2000, pp. 100-105.
[7]	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. doi:10.1109/49.622910
[8]	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 Jose, 25-29 October 2004, pp. 31-36.
[9]	J. J. Y. Leu, M.-H. Tsai, T.-C. Chiang and Y.-M. Huang, “Adaptive Power Aware Clustering and Multicasting Protocol for Mobile Ad Hoc Networks,” International Conference on Ubiquitous Intelligence and Computing, Wuhan, 3-6 September 2006, pp. 331-340.
[10]	S. Lindsey and C. S. Raghavendra, “PEGASIS: Power-Efficient Gathering in Sensor Information Systems,” Aerospace Conference Proceedings, Big Sky, 9-16 March 2002, pp. 1125-1130. doi:10.1109/AERO.2002.1035242
[11]	L. Li, S. Dong and X. Wen, “An Energy Efficient Clustering Routing Algorithm for Wireless Sensor Networks,” The Journal of China Universities of Posts and Telecommunications, Vol. 3, No. 13, 2006, pp. 71-75. doi:10.1016/S1005-8885(07)60015-6
[12]	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. 2842-2852. doi:10.1016/j.comcom.2007.05.034
[13]	S. Ghiasi, A. Srivastava, X. Yang and M. Sarrafzadeh, “Optimal Energy Aware Clustering in Sensor Networks,” SENSORS Journal, Vol. 7, No. 2, 2002, pp. 258-269.
[14]	H. Chan and A. Perrig, “ACE: An Emergent Algorithm for Highly Uniform Cluster Formation,” Lecture Notes in Computer Science, Vol. 2920, 2004, pp. 154-171.
[15]	O. Younis and S. Fahmy, “Distributed Clustering in Ad-Hoc Sensor Networks: A Hybrid, Energy-Efficient Approach,” Proceedings of IEEE the 23rd Conference of the IEEE Communications Society, Hong Kong, 7-11 March 2004, pp. 366-379.
[16]	J. Y. Cheng, S. J. Ruan, R. G. Cheng and T. T. Hsu, “PADCP: Poweraware Dynamic Clustering Protocol for Wireless Sensor Network,” International Conference on Wireless and Optical Communications Networks, Banglore, 11-13 April 2006.
[17]	G. Smaragdakis, I. Matta and A. Bestavros, “SEP: A Stable Election Protocol for Clustered Heterogeneous Wireless Sensor Networks,” Proceedings of the International Workshop on SANPA, Boston, 22 August 2004.
[18]	M. Haase and D. Timmermann, “Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection,” The 4th International Workshop on Mobile and Wireless Communications Network, Stockholm, 9-11 September 2002, pp. 368-372.
[19]	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. doi:10.1109/TWC.2002.804190
[20]	C. Nam, H. Jeong and D. Shin, “The Adaptive Cluster Head Selection in Wireless Sensor Networks,” IEEE International Workshop on Semantic Computing and Applications, Incheon, 19-21 September 2008, pp. 147-149.
[21]	A. Giridhar and P. R. Kumar, “Maximizing the Functional Lifetime of Sensor Networks,” The Fourth International Symposium on Information Processing in Sensor Networks, Los Angeles, 25-27 April 2005, pp. 5-12.
[22]	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, Seoul, 16-20 May 2005, pp. 3295-3301.
[23]	H. Zhang and J. C. Hou, “Maximizing α-Lifetime for Wireless Sensor Networks,” International Journal of Sensor Networks, Vol. 1, No. 1, 2006, pp. 64-71. doi:10.1504/IJSNET.2006.010835
[24]	V. Rai and R. N. Mahapatra, “Lifetime Modeling of a Sensor Network,” Proceedings of Design, Automation and Test in Europe, Munich, 7-11 March 2005, pp. 202-203.
[25]	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, 11-15 June 2006, pp. 3978-3983. doi:10.1109/ICC.2006.255703
[26]	L. Shi, A. Capponi, K. H. Johansson and R. M. Murray, “Sensor Network Lifetime Maximization via Sensor Trees Construction and Scheduling,” The Third International Workshop on Feedback Control Implementation and Design in Computing Systems and Networks, Annapolis, 6 June 2008.
[27]	P. Berman, G. Calinescu, C. Shah and A. Zelikovsky, “Power Efficient Monitoring Management in Sensor Networks,” IEEE Wireless Communication and Networking Conference, Atlanta, 21-25 March 2004, pp. 2329-2334.
[28]	D. Brinza and A. Zelikovsky, “DEEPS: Deterministic Energy-Efficient Protocol for Sensor networks,” International Workshop on Self-Assembling Wireless Networks, Las Vegas, 19-20 June 2006, pp. 261-266.
[29]	A. Aung, “Distributed Algorithms for Improving Wireless Sensor Network Lifetime with Adjustable Sensing Range,” Master’s Thesis, Georgia State University, Atlanta, 2007.
[30]	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.
[31]	Y. Chen, Q. Zhao, V. Krishnamurthy and D. Djonin, “Transmission Scheduling for Sensor Network Lifetime Maximization: A Shortest Path Bandit Formulation,” IEEE International Conference on Acoustics, Speech and Signal Processing, Toulouse, 14-19 May 2006.
[32]	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, Orlando, 19-23 January 2003.
[33]	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, Nashville, 19-21 April 2006.
[34]	M. Cardei and D. Du, “Summary on Improving Wireless Sensor Network Lifetime through Power Aware Organization,” Seminar on Theoretical Computer Science, 2005.
[35]	J. Park and S. Sahni, “An Online Heuristic for Maximum Lifetime Routing in Wireless Sensor Networks,” IEEE Transactions on Computers, Vol. 55, No. 8, 2006, pp. 1048-1056. doi:10.1109/TC.2006.116
[36]	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. doi:10.1109/TNET.2004.833122
[37]	P. Djukic and S. Valaee, “Maximum Network Lifetime in Fault Tolerant Sensor Networks,” IEEE Global Telecommunications Conference, Saint Louis, 28 November-2 December 2005, pp. 3106-3111.
[38]	M. Cardei, J. Wu, M. Lu and M. O. Pervaiz, “Maximum Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges,” International Conference on Wireless and Mobile Computing, Networking and Communications, Montreal, 13-16 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. doi:10.1016/S1389-1286(03)00212-3
[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, 2006, pp. 2185-2193. doi:10.1109/TWC.2006.1687734
[41]	Y. T. Hou, Y. Shi, H. D. Sherali and S. F. Midkiff, “Prolonging Sensor Network Lifetime with Energy Provisioning and Relay Node Placement,” The Second Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, Santa Clara, 26-29 September 2005, pp. 295-304. doi:10.1109/SAHCN.2005.1557084
[42]	X. Han, X. Cao, E. L. Lloyd and C.-C. Shen, “Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks,” The 26th IEEE International Conference on Computer Communications, Anchorage, 6-12 May 2007, pp. 1667-1675.
[43]	W. Zhang, G. Xue and S. Misra, “Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Problems and Algorithms,” The 26th IEEE International Conference on Computer Communications, Anchorage, 6-12 May 2007, pp. 1649-1657.
[44]	B. Hao, J. Tang and G. Xue, “Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Formulation and Approximation,” Proceedings of IEEE Workshop High Performance Switching and Routing, Phoenix, 19-21 April 2004, pp. 246-250.
[45]	E. L. Lloyd and G. Xue, “Relay Node Placement in Wireless Sensor Networks,” IEEE Transactions on Computers, Vol. 56, No. 1, 2007, pp. 134-138. doi:10.1109/TC.2007.250629
[46]	W. Wang, V. Srinivasan and K.-C. Chua, “Using Mobile Relays to Prolong the Lifetime of Wireless Sensor Networks,” Proceedings of the 11th ACM International Conference on Mobile Computing and Networking, Cologne, August 28-September 2, 2005, pp. 270-283.
[47]	J. C. Choi and C. W. Lee, “Energy Modeling for the Cluster-Based Sensor Networks,” Proceedings of the Sixth IEEE International Conference on Computer and Information Technology, Seoul, 20-22 September 2006, p. 218.
[48]	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, 2006, pp. 40-47. doi:10.4304/jcp.1.1.40-47
[49]	A. B. M. A. A. Islam, “A Novel Approach to Cluster Heterogeneous Sensor Network (CHSN),” M.Sc. Engineering Thesis, 2009, pp. 31-41.
[50]	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, 2010. pp. 129-140. doi:10.4236/wsn.2010.22018
[51]	A. B. M. A. A. Islam, C. S. Hyder, M. H. Kabir and M. Naznin, “Stable Sensor Network (SSN): A Dynamic Clustering Technique for Maximizing Stability in Wireless Sensor Networks,” Wireless Sensor Network, Vol. 2, No. 7, 2010, pp. 538-554. doi:10.4236/wsn.2010.27066
[52]	K. Dasgupta, K. Kalpakis and P. Namjoshi, “An Efficient Clustering-Based Heuristic for Data Gathering and Aggregation in Sensor Networks,” Proceedings of the IEEE Wireless Communications and Networking Conference, New Orleans, 16-20 March 2003, pp. 1948-1953.
[53]	D. Song, “Probabilistic Modeling of Leach Protocol and Computing Sensor Energy Consumption Rate in Sensor Networks,” Technical Report, 22 February 2005.
[54]	T. Murata and H. Ishibuchi, “Performance Evaluation of Genetic Algorithms for Flowshop Scheduling Problems,” Proceedings of 1st IEEE Conference Evolutionary Computation, Orlando, 27-29 June 1994, pp. 812-817.
[55]	B. Sundararaman, U. Buy and A. Kshemkalyani, “Clock Synchronization for Wireless Sensor Networks: A Survey,” Ad Hoc Network, Vol. 3, No. 3, 2005, pp. 281-323. doi:10.1016/j.adhoc.2005.01.002
[56]	Q. Li and D. Rus, “Global Clock Synchronization in Sensor Networks,” Proceedings of IEEE Conference on Computer Communications, Hong Kong, 7-11 March 2004, pp. 564-574.
[57]	L. Meier, P. Blum and L. Thiele, “Internal Synchronization of Drift-Constrained Clocks in Ad-Hoc Sensor Networks,” Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Tokyo, 24-26 May 2004, pp. 90-97.
[58]	M. L. Sichitiu and C. Veerarittiphan, “Simple, Accurate Time Synchronization for Wireless Sensor Networks,” Proceedings of IEEE Wireless Communications and Networking Conference, New Orleans, 16-20 March 2003, pp. 1266-1273.
[59]	G. E. P. Box and M. E. Muller, “A Note on the Generation of Random Normal Deviates,” The Annals of Mathematical Statistics, Vol. 29, No. 2, 1958, pp. 610-611.
[60]	A. B. M. A. A. Islam, M. S. Hossain, V. Raghunathan, and Y. C. Hu, “Backpacking: Deployment of Heterogeneous Radios in High Data Rate Sensor Networks,” Proceedings of IEEE International Conference on Computer Communications and Networks, Maui, 31 July-4 August 2011, pp. 1-8.