Finding the Optimal Percentage of Cluster Heads from a New and Complete Mathematical Model on LEACH

ABSTRACT

Network lifetime is one of the important metrics that indicate the performance of a sensor network. Different techniques are used to elongate network lifetime. Among them, clustering is one of the popular techniques. LEACH (Low-Energy Adaptive Clustering Hierarchy) is one of the most widely cited clustering solutions due to its simplicity and effectiveness. LEACH has several parameters that can be tuned to get better performance. Percentage of cluster heads is one such important parameter which affects the network lifetime significantly. At present it is hard to find the optimum value for the percentage of cluster head parameter due to the absence of a complete mathematical model on LEACH. A complete mathematical model on LEACH can be used to tune other LEACH parameters in order to get better performance. In this paper, we formulate a new and complete mathematical model on LEACH. From this new mathematical model, we compute the value for the optimal percentage of cluster heads in order to increase the network lifetime. Simulation results verify both the correctness of our mathematical model and the effectiveness of computing the optimal percentage of cluster heads to increase the network lifetime.

Network lifetime is one of the important metrics that indicate the performance of a sensor network. Different techniques are used to elongate network lifetime. Among them, clustering is one of the popular techniques. LEACH (Low-Energy Adaptive Clustering Hierarchy) is one of the most widely cited clustering solutions due to its simplicity and effectiveness. LEACH has several parameters that can be tuned to get better performance. Percentage of cluster heads is one such important parameter which affects the network lifetime significantly. At present it is hard to find the optimum value for the percentage of cluster head parameter due to the absence of a complete mathematical model on LEACH. A complete mathematical model on LEACH can be used to tune other LEACH parameters in order to get better performance. In this paper, we formulate a new and complete mathematical model on LEACH. From this new mathematical model, we compute the value for the optimal percentage of cluster heads in order to increase the network lifetime. Simulation results verify both the correctness of our mathematical model and the effectiveness of computing the optimal percentage of cluster heads to increase the network lifetime.

KEYWORDS

Wireless Senor Network, Clustering, Mathematical Model Network Lifetime, Energy Consumption Rate, Renewal Reward Process

Wireless Senor Network, Clustering, Mathematical Model Network Lifetime, Energy Consumption Rate, Renewal Reward Process

Cite this paper

nullA. ALIM AL ISLAM, C. SAYEED HYDER, 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.

nullA. ALIM AL ISLAM, C. SAYEED HYDER, H. KABIR and M. NAZNIN, "Finding the Optimal Percentage of Cluster Heads from a New and Complete Mathematical Model on LEACH,"

References

[1] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Energy efficient communication protocol for wireless microsensor networks,” In Proceedings of the Hawaii International Conference on System Sciences, Maui, Hawaii, Vol. 2, pp. 10, January2000.

[2] S. Lindsey and C. S. Raghavendra, “PEGASIS: power- efficient gathering in sensor information systems,” Aero- space Conference Proceedings, Vol. 3, pp. 1125–1130, 2002.

[3] L. Li, S. Dong, and X. Wen, “An energy efficient clustering routing algorithm for wireless sensor net- works,” The Journal of China Universities of Posts and Telecommunications, Vol. 3, No. 13, pp. 71–75, Sep- tember 2006.

[4] Y. Sangho, H. Junyoung, C. Yookun, and H. Jiman, “PEACH: power-efficient and adaptive clustering hie- rarchy protocol for wireless sensor networks,” Com- puter communications, Vol. 30, pp. 2842–2852, 2007.

[5] S. Ghiasi, A. Srivastava, X. Yang, and M. Sarrafzadeh, “Optimal energy aware clustering in sensor networks,” SENSORS Journal, Vol. 7, No. 2, pp. 258–269, 2002.

[6] H. Chan and A. Perrig, “ACE: an emergent algorithm for highly uniform cluster formatio,” Lecture Notes in Computer Science, Springer Berlin/Heidelberg, Vol. 2920, pp. 154–171, February 2004.

[7] O. Younis and S. Fahmy, “Distributed clustering in ad-hoc sensor networks: a hybrid, energy-efficient approach,” Proceedings of IEEE Infocom, Vol. 1, pp. 640, 2004.

[8] 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, pp. 6, 13 April 2006.

[9] G. Smaragdakis, I. Matta, and A. Bestavros, “SEP: a stable election protocol for clustered heterogeneous wireless sensor networks,” In the Proceedings of the International Workshop on SANPA, 2004.

[10] M. Haase and D. Timmermann, “Low energy adaptive clustering hierarchy with deterministic cluster-head selection,” 4th International Workshop on Mobile and Wireless Communications Network, pp. 368–372, 2002.

[11] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An application-specific protocol archi- tecture for wireless microsensor networks,” IEEE Transa- ctions on Wireless Communications, pp. 660–670, Octo- ber 2002.

[12] C. Nam, H. Jeong, and D. Shin, “The adaptive cluster head selection in wireless sensor networks,” IEEE International Workshop on Semantic Computing and Applications, pp. 147–149, 2008.

[13] J. C. Choi and C. W. Lee, “Energy modeling for the cluster-based sensor networks,” In Proceedings of the Sixth IEEE International Conference on Computer and Information Technology, pp. 218, September 20–22 2006.

[14] S. Selvakennedy and S. Sinnappan, “An energy-efficient clustering algorithm for multihop data gathering in wireless sensor networks,” Journal of Computers, pp. 1, April 2006.

[15] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Energy efficient communication protocol for wireless microsensor networks,” In Proceedings of the Hawaii International Conference on System Sciences, Maui, Hawaii, January 2000.

[16] E. Popova and H. C. Wu, “Renewal reward processes with fuzzy rewards and their applications to T-age replacement policies,” European Journal of Operational Research, Vol. 117, pp. 606–617, 1999.

[17] R. Zhao and B. Liu, “Renewal process with fuzzy interarrival times and rewards,” International Journal of Uncertainty, Fuzziness and Knowledge based Systems, Vol. 11, pp. 573–586, 2003.

[18] H. D. Brunk, “The strong law of large numbers,” Duke Mathematical Journal, Vol. 15, pp. 181–195, 1948.

[19] http://www.xbow.com/Products/productdetails.aspx?sid=156

[1] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Energy efficient communication protocol for wireless microsensor networks,” In Proceedings of the Hawaii International Conference on System Sciences, Maui, Hawaii, Vol. 2, pp. 10, January2000.

[2] S. Lindsey and C. S. Raghavendra, “PEGASIS: power- efficient gathering in sensor information systems,” Aero- space Conference Proceedings, Vol. 3, pp. 1125–1130, 2002.

[3] L. Li, S. Dong, and X. Wen, “An energy efficient clustering routing algorithm for wireless sensor net- works,” The Journal of China Universities of Posts and Telecommunications, Vol. 3, No. 13, pp. 71–75, Sep- tember 2006.

[4] Y. Sangho, H. Junyoung, C. Yookun, and H. Jiman, “PEACH: power-efficient and adaptive clustering hie- rarchy protocol for wireless sensor networks,” Com- puter communications, Vol. 30, pp. 2842–2852, 2007.

[5] S. Ghiasi, A. Srivastava, X. Yang, and M. Sarrafzadeh, “Optimal energy aware clustering in sensor networks,” SENSORS Journal, Vol. 7, No. 2, pp. 258–269, 2002.

[6] H. Chan and A. Perrig, “ACE: an emergent algorithm for highly uniform cluster formatio,” Lecture Notes in Computer Science, Springer Berlin/Heidelberg, Vol. 2920, pp. 154–171, February 2004.

[7] O. Younis and S. Fahmy, “Distributed clustering in ad-hoc sensor networks: a hybrid, energy-efficient approach,” Proceedings of IEEE Infocom, Vol. 1, pp. 640, 2004.

[8] 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, pp. 6, 13 April 2006.

[9] G. Smaragdakis, I. Matta, and A. Bestavros, “SEP: a stable election protocol for clustered heterogeneous wireless sensor networks,” In the Proceedings of the International Workshop on SANPA, 2004.

[10] M. Haase and D. Timmermann, “Low energy adaptive clustering hierarchy with deterministic cluster-head selection,” 4th International Workshop on Mobile and Wireless Communications Network, pp. 368–372, 2002.

[11] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An application-specific protocol archi- tecture for wireless microsensor networks,” IEEE Transa- ctions on Wireless Communications, pp. 660–670, Octo- ber 2002.

[12] C. Nam, H. Jeong, and D. Shin, “The adaptive cluster head selection in wireless sensor networks,” IEEE International Workshop on Semantic Computing and Applications, pp. 147–149, 2008.

[13] J. C. Choi and C. W. Lee, “Energy modeling for the cluster-based sensor networks,” In Proceedings of the Sixth IEEE International Conference on Computer and Information Technology, pp. 218, September 20–22 2006.

[14] S. Selvakennedy and S. Sinnappan, “An energy-efficient clustering algorithm for multihop data gathering in wireless sensor networks,” Journal of Computers, pp. 1, April 2006.

[15] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Energy efficient communication protocol for wireless microsensor networks,” In Proceedings of the Hawaii International Conference on System Sciences, Maui, Hawaii, January 2000.

[16] E. Popova and H. C. Wu, “Renewal reward processes with fuzzy rewards and their applications to T-age replacement policies,” European Journal of Operational Research, Vol. 117, pp. 606–617, 1999.

[17] R. Zhao and B. Liu, “Renewal process with fuzzy interarrival times and rewards,” International Journal of Uncertainty, Fuzziness and Knowledge based Systems, Vol. 11, pp. 573–586, 2003.

[18] H. D. Brunk, “The strong law of large numbers,” Duke Mathematical Journal, Vol. 15, pp. 181–195, 1948.

[19] http://www.xbow.com/Products/productdetails.aspx?sid=156