Abstract
Motivated by recent developments in Wireless Sensor Networks(WSNs), we present distributed clustering algorithms for maximizingthe lifetime of WSNs, i.e., the duration till the first node dies. Westudy the joint problem of prolonging network lifetime by introducing clustering techniques and energy-harvesting (EH) nodes. Firstlywe propose distributed clustering algorithm for maximizing the lifetime of clustered WSN, which includes EH nodes, serving as relaynodes for cluster heads (CHs). Secondly graph-based and LP-basedEH-CH matching algorithms are proposed which serve as benchmarkalgorithms. Extensive simulation results show that the proposed algorithms can achieve optimal or suboptimal solutions efficientlyReferences
P. Rawat, K. D. Singh, H. Chaouchi, and J. M. Bonnin, “Wireless sensornetworks: a survey on recent developments and potential synergies,†The
Journal of supercomputing, vol. 68, no. 1, pp. 1–48, 2014.24[2] R. Vullers, R. Schaijk, H. Visser, J. Penders, and C. Hoof, “Energyharvesting for autonomous wireless sensor networks,†IEEE Solid-State
Circuits Magazine, vol. 2, no. 2, pp. 29–38, 2010.[3] I. Khan, F. Belqasmi, R. Glitho, N. Crespi, M. Morrow, and P. Polakos,“Wireless sensor network virtualization: A survey,†IEEE Communications Surveys & Tutorials, vol. 18, no. 1, pp. 553–576, 2015[4] J. Singh, B. P. Singh, and S. B. Shaw, “A survey on leach-based hierarchical routing protocols in wireless sensor network,†in International
Journal of Engineering Research and Technology, vol. 3, no. 6 (June-2014). ESRSA Publications, 2014.[5] X. Liu, “A survey on clustering routing protocols in wireless sensornetworks,†Sensors, vol. 12, no. 8, pp. 11 113–11 153, 2012.[6] S. Tyagi and N. Kumar, “A systematic review on clustering and routing techniques based upon leach protocol for wireless sensor networks,â€Journal of Network and Computer Applications, vol. 36, no. 2, pp. 623–645, 2013.[7] S. P. Singh and S. Sharma, “A survey on cluster based routing protocolsin wireless sensor networks,†Procedia computer science, vol. 45, pp.687–695, 2015.[8] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energyefficient communication protocol for wireless microsensor networks,â€Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, vol. 2, p. 223, Jan. 2000.[9] L. Qing, Q. Zhu, and M. Wang, “Design of a distributed energy-efficientclustering algorithm for heterogeneous wireless sensor networks,†Computer Communications, vol. 29, no. 12, pp. 2230 – 2237, 2006.[10] M. Ye, C. Li, G. Chen, and J. Wu, “Eecs: an energy efficient clusteringscheme in wireless sensor networks,†24th IEEE International Performance, Computing, and Communications Conference, pp. 535 – 540,April 2005.25[11] O. Younis and S. Fahmy, “Heed: a hybrid, energy-efficient, distributedclustering approach for ad hoc sensor networks,†IEEE Transactions on
Mobile Computing, vol. 3, no. 4, pp. 366 – 379, oct.-dec. 2004.[12] M. Zhang, C. Gong, and Y. Lu, “An novel dynamic clustering algorithmbased on geographical location for wireless sensor networks,†International Symposium on Information Science and Engineering, vol. 1, pp.565 –568, Dec. 2008.[13] Y.-F. Huang, W.-H. Luo, J. Sum, L.-H. Chang, C.-W. Chang, and R.-C.Chen, “Lifetime performance of an energy efficient clustering algorithfor cluster-based wireless sensor networks,†Frontiers of High Performance Computing and Networking ISPA 2007 Workshops, vol. 4743,pp. 455–464, 2007.[14] J. Peng, L. Li, and S. Xu, “A novel energy efficient and reliable clusteringalgorithm in wireless sensor networks,†IET Conference Publications,vol. 2007, no. 533, pp. 596–599, 2007.[15] S.-S. Wang and Z.-P. Chen, “Lcm: a link-aware clustering mechanismfor energy-efficient routing in wireless sensor networks,†IEEE Sensors
Journal, vol. 13, no. 2, pp. 728–736, 2013.[16] A. Chehri and H. Mouftah, “An efficient clusterhead placement for hybrid sensor networks,†Ad-Hoc, Mobile and Wireless Networks, vol. 6288,pp. 123–134, 2010.[17] A. Peiravi, H. R. Mashhadi, and S. Hamed Javadi, “An optimal energyefficient clustering method in wireless sensor networks using multiobjective genetic algorithm,†International Journal of Communication
Systems, vol. 26, no. 1, pp. 114–126, 2013.[18] H. Bagci and A. Yazici, “An energy aware fuzzy approach to unequalclustering in wireless sensor networks,†Applied Soft Computing, vol. 13,no. 4, pp. 1741–1749, 2013.[19] D. Kumar, “Performance analysis of energy efficient clustering protocols for maximising lifetime of wireless sensor networks,†IET Wireless
Sensor Systems, vol. 4, no. 1, pp. 9–16, 2014.26[20] D. C. Hoang, P. Yadav, R. Kumar, and S. K. Panda, “Real-time implementation of a harmony search algorithm-based clustering protocol forenergy-efficient wireless sensor networks,†IEEE Transactions on Industrial Informatics, vol. 10, no. 1, pp. 774–783, 2014.[21] P. Kuila and P. K. Jana, “Energy efficient clustering and routing algorithms for wireless sensor networks: Particle swarm optimization approach,†Engineering Applications of Artificial Intelligence, vol. 33, pp.127–140, 2014.[22] N. Javaid, T. Qureshi, A. Khan, A. Iqbal, E. Akhtar, and M. Ishfaq, “Eddeec: enhanced developed distributed energy-efficient clustering for heterogeneous wireless sensor networks,†Procedia computer science, vol. 19,pp. 914–919, 2013.[23] P. Zhang, G. Xiao, and H.-P. Tan, “Clustering algorithms for maximizing the lifetime of wireless sensor networks with energy-harvestingsensors,†Computer Networks, vol. 57, no. 14, pp. 2689–2704, Oct. 2013.[24] N. A. Pantazis, S. A. Nikolidakis, and D. D. Vergados, “Energy-efficientrouting protocols in wireless sensor networks: A survey,†IEEE Communications Surveys & Tutorials, vol. 15, no. 2, pp. 551–591, 2013.[25] P. Huang, L. Xiao, S. Soltani, M. W. Mutka, and N. Xi, “The evolution of mac protocols in wireless sensor networks: A survey,†IEEE
Communications Surveys & Tutorials, vol. 15, no. 1, pp. 101–120, 2013.[26] Q. Dong and W. Dargie, “A survey on mobility and mobility-aware macprotocols in wireless sensor networks,†IEEE Communications Surveys
& Tutorials, vol. 15, no. 1, pp. 88–100, 2013.[27] P. M. Pawar, R. H. Nielsen, N. R. Prasad, and R. Prasad, “Mobilityimpact on cluster based mac layer protocols in wireless sensor networks,â€Wireless Personal Communications, vol. 74, no. 4, pp. 1213–1229, 2014.[28] S. Sudevalayam and P. Kulkarni, “Energy harvesting sensor nodes: Survey and implications,†IEEE Communications Surveys Tutorials, no. 99,pp. 1 –19, 2010.27[29] M. Gorlatova, P. Kinget, I. Kymissis, D. Rubenstein, X. Wang, andG. Zussman, “Challenge: ultra-low-power energy-harvesting active networked tags (enhants),†Proceedings of the 15th annual international
conference on Mobile computing and networking, pp. 253–260, 2009.[30] H. Yoo, M. Shim, and D. Kim, “Dynamic duty-cycle scheduling schemesfor energy-harvesting wireless sensor networks,†IEEE communications
letters, vol. 16, no. 2, pp. 202–204, 2012.[31] D. Hasenfratz, A. Meier, C. Moser, J.-J. Chen, and L. Thiele, “Analysis,comparison, and optimization of routing protocols for energy harvestingwireless sensor networks,†2010 IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC), pp. 19–26, June 2010.[32] C. Bergonzini, D. Brunelli, and L. Benini, “Algorithms for harvestedenergy prediction in batteryless wireless sensor networks,†3rd International Workshop on Advances in sensors and Interfaces, pp. 144 –149,June 2009.[33] M. Islam, M. Islam, and M. Islam, “A-sleach: An advanced solar awareleach protocol for energy efficient routing in wireless sensor networks,â€Sixth International Conference on Networking, p. 4, April 2007.[34] B. Medepally and N. Mehta, “Voluntary energy harvesting relays andselection in cooperative wireless networks,†IEEE Transactions on Wireless Communications, vol. 9, no. 11, pp. 3543 –3553, November 2010.[35] P. Zhang, G. Xiao, and H.-P. Tan, “Distributed relay scheduling formaximizing lifetime in clustered wireless sensor networks,†2012 IEEE
International Conference on Communication Systems (ICCS), pp. 11–15, Nov 2012.[36] T. E. Anderson, S. S. Owicki, J. B. Saxe, and C. P. Thacker, “Highspeed switch scheduling for local-area networks,†ACM Trans. Comput.Syst., vol. 11, no. 4, pp. 319–352, Nov. 1993.[37] N. McKeown, “The islip scheduling algorithm for input-queuedswitches,†IEEE/ACM Transactions on Networking,, vol. 7, no. 2, pp188 –201, Apr. 1999.28[38] T. Voigt, A. Dunkels, J. Alonso, H. Ritter, and J. Schiller, “Solar-awareclustering in wireless sensor networks,†Ninth International Symposium
on Computers and Communications, vol. 1, pp. 238 – 243, July 2004.[39] K. Kinoshita, T. Okazaki, H. Tode, and K. Murakami, “A data gatheringscheme for environmental energy-based wireless sensor networks,†5th
IEEE Consumer Communications and Networking Conference, pp. 719–723, Jan. 2008.[40] C. Alippi, R. Camplani, C. Galperti, and M. Roveri, “A robust, adaptive, solar-powered wsn framework for aquatic environmental monitoring,†IEEE Sensors Journal, vol. 11, no. 1, pp. 45 –55, Jan. 2011.[41] H. Gou, Y. Yoo, and H. Zeng, “A partition-based leach algorithmfor wireless sensor networks,†Ninth IEEE International Conference on
Computer and Information Technology, vol. 2, pp. 40 –45, Oct. 2009.[42] P. M., “A distributed switch scheduling algorithm,†Performance Evaluation, vol. 64, no. 9-12, pp. 1053 – 1061, 2007.[43] T. S. Rappaport, Wireless communications: principles and practice.Prentice Hall PTR New Jersey, 2002.[44] J. E. Hopcroft and R. M. Karp, “A n5/2 algorithm for maximum matchings in bipartite,†12th Annual Symposium on Switching and Automata
Theory,, pp. 122–125, 1971.[45] K. Mjelde, “Max-min resource allocation,†BIT, vol. 23, no. 4, pp. 529–
, 1983.[46] B. Calhoun, D. Daly, N. Verma, D. Finchelstein, D. Wentzloff, A. Wang,S.-H. Cho, and A. Chandrakasan, “Design considerations for ultra-lowenergy wireless microsensor nodes,†IEEE Transactions on Computers,vol. 54, no. 6, pp. 727–740, 2005.