Harmony Search-based K-Coverage Enhancement in Wireless Sensor Networks

Authors: Shaimaa M. Mohamed, Haitham S. Hamza, Imane A. Saroit

Abstract:

Many wireless sensor network applications require K-coverage of the monitored area. In this paper, we propose a scalable harmony search based algorithm in terms of execution time, K-Coverage Enhancement Algorithm (KCEA), it attempts to enhance initial coverage, and achieve the required K-coverage degree for a specific application efficiently. Simulation results show that the proposed algorithm achieves coverage improvement of 5.34% compared to K-Coverage Rate Deployment (K-CRD), which achieves 1.31% when deploying one additional sensor. Moreover, the proposed algorithm is more time efficient.

Keywords: Wireless Sensor Networks (WSN), Harmony Search Algorithms, K-Coverage, Mobile WSN.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1338036

References:

[1] J. Paek, K. Chintalapudi, R. Govindan, J. Caffrey, and S. Masri, “A wireless sensor network for structural health monitoring: Performance and experience,” in Embedded Networked Sensors, 2005. EmNetS-II. The Second IEEE Workshop on, pp. 1–10, 2005.
[2] G. Anastasi, G. Lo Re, and M. Ortolani, “Wsns for structural health monitoring of historical buildings,” in Human System Interactions, 2009. HSI ’09. 2nd Conference on, pp. 574–579, 2009.
[3] G. Tolle, J. Polastre, R. Szewczyk, D. Culler, N. Turner, K. Tu, S. Burgess, T. Dawson, P. Buonadonna, D. Gay, and W. Hong, “A macroscope in the redwoods,” in Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems, SenSys ’05, (New York, NY, USA), pp. 51–63, ACM, 2005.
[4] G. Werner-Allen, J. Johnson, M. Ruiz, J. Lees, and M. Welsh, “Monitoring volcanic eruptions with a wireless sensor network,” in Wireless Sensor Networks, 2005. Proceeedings of the Second European Workshop on, pp. 108–120, 2005.
[5] H. Y. Jeonghwan Hwang, Changsun Shin, “Study on an agricultural environment monitoring server system using wireless sensor networks,” 2010.
[6] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, “Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with zebranet,” SIGARCH Comput. Archit. News, vol. 30, pp. 96–107, Oct. 2002.
[7] A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson, “Wireless sensor networks for habitat monitoring,” in Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, WSNA ’02, (New York, NY, USA), pp. 88–97, ACM, 2002.
[8] W. Hu, V. N. Tran, N. Bulusu, C. T. Chou, S. Jha, and A. Taylor, “The design and evaluation of a hybrid sensor network for cane-toad monitoring,” in Information Processing in Sensor Networks, 2005. IPSN 2005. Fourth International Symposium on, pp. 503–508, 2005.
[9] A.-K. Othman, K. M. Lee, H. Zen, W. Zainal, and M. F. M. Sabri, “Wireless sensor networks for swift bird farms monitoring,” in Ultra Modern Telecommunications Workshops, 2009. ICUMT ’09. International Conference on, pp. 1–7, 2009.
[10] M. Hussain, P. Khan, and K. kyung Sup, “Wsn research activities for military application,” in Advanced Communication Technology, 2009. ICACT 2009. 11th International Conference on, vol. 01, pp. 271–274, 2009.
[11] M. Khanafer, M. Guennoun, and H. Mouftah, “Intrusion detection system for wsn-based intelligent transportation systems,” in Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE, pp. 1–6, Dec 2010.
[12] Wireless Sensor Networks: Technology, Protocols, and Applications. Wiley, 2007.
[13] M. S. K. Arash Nikdel and S. M. Jamei, “An intelligent and energy efficient area coverage protocol for wireless sensor networks,” International Journal of Grid and Distributed Computing, 2011.
[14] H. R. Mohammad Amin Zare Soltani, Abolfazl Toroghi Haghighat and T. G. Chegini, “A couple of algorithms for k-coverage problem in visual sensor networks,” International Conference on Communication Engineering and Networks, 2011.
[15] M. Cardei, M. T. Thai, Y. Li, and W. Wu, “Energy-efficient target coverage in wireless sensor networks,” in in IEEE Infocom.
[16] X. Li, H. Frey, N. Santoro, and I. Stojmenovic, “Localized sensor self-deployment with coverage guarantee,” SIGMOBILE Mob. Comput. Commun. Rev., vol. 12, pp. 50–52, Apr. 2008.
[17] Y. Zou and K. Chakrabarty, “Sensor deployment and target localization in distributed sensor networks,” ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, vol. 3, no. 1, pp. 61–91, 2004.
[18] Y. Zou and K. Chakrabarty, “Sensor deployment and target localization based on virtual forces,” in Twenty-Second Annual Joint Conference of the IEEE Computer and Communications INFOCOM 2003.
[19] G. Wang, G. Cao, and T. La Porta, “Movement-assisted sensor deployment,” in Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2004.
[20] M. Ma and Y. Yang, “Adaptive triangular deployment algorithm for unattended mobile sensor networks,” Computers, IEEE Transactions on, 2007.
[21] S. L. X. Bai and J. Xu, “Mobile sensor deployment optimization for k -coverage in wireless sensor networks with a limited mobility model,” IETE Technical Review, 2010.
[22] J.-P. Sheu, G.-Y. Chang, and Y.-T. Chen, “A novel approach for k-coverage rate evaluation and re-deployment in wireless sensor networks,” in Global Telecommunications Conference, 2008. IEEE GLOBECOM 2008. IEEE, pp. 1–5, 2008.
[23] G. G. Wang, G. Cao, P. Berman, and T. F. L. Porta, “Bidding protocols for deploying mobile sensors,” IEEE Transactions on Mobile Computing, vol. 6, no. 5, pp. 563–576, 2007.
[24] N. Bartolini, T. Calamoneri, E. Fusco, A. Massini, and S. Silvestri, “Autonomous deployment of self-organizing mobile sensors for a complete coverage,” in Self-Organizing Systems (K. Hummel and J. Sterbenz, eds.), vol. 5343 of Lecture Notes in Computer Science, pp. 194–205, Springer Berlin Heidelberg, 2008.
[25] G. Tan, S. A. Jarvis, and A.-M. Kermarrec, “Connectivity-guaranteed and obstacle-adaptive deployment schemes for mobile sensor networks,” IEEE Transactions on Mobile Computing, vol. 8, no. 6, pp. 836–848, 2009.
[26] D. Li, W. Liu, and L. Cui, “Easidesign: An improved ant colony algorithm for sensor deployment in real sensor network system,” in Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE, pp. 1–5, 2010.
[27] H. J. K. Shohreh Ebrahimnezhad and M. E. Moghaddam, “Extending coverage and lifetime of k-coverage wireless sensor networks using improved harmony search,” Sensors & Transducers, 2011.
[28] C. Ozturk, D. Karaboga, and B. Gorkemli, “Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm,” Sensors, vol. 11, no. 6, pp. 6056–6065, 2011.
[29] G. L. Z.W. Geem, J.-H. Kim, “A new heuristic optimization algorithm: Harmony search,” Simulation, 2001.
[30] M. Mahdavi, M. Fesanghary, and E. Damangir, “An improved harmony search algorithm for solving optimization problems,” Applied Mathematics and Computation, 2007.
[31] M. G. Omran and M. Mahdavi, “Global-best harmony search,” Applied Mathematics and Computation, 2008.
[32] C.-M. Wang and Y.-F. Huang, “Self adaptive harmony search algorithm for optimization,” Expert Systems with Applications, 2010.
[33] S. D. D. J. P. Chakraborty, G.G. Roy, “An improved harmony search algorithm with differential mutation operator,” Fundamenta Informaticae, 2009.
[34] J. L. Q.K. Pan, PN Suganthan and M. Tasgetiren, “A local-best harmony search algorithm with dynamic subpopulations,” Engineering Optimization, 2010.
[35] B. Wang, “Coverage problems in sensor networks: A survey,” ACM Comput. Surv., vol. 43, pp. 32:1–32:53, Oct. 2011.
[36] Y.-C. Wang, C.-C. Hu, and Y.-C. Tseng, “Efficient deployment algorithms for ensuring coverage and connectivity of wireless sensor networks,” in First International Conference Proceedings on Wireless Internet, 2005., pp. 114–121, 2005.
[37] X. Bai, S. Kumar, D. Xuan, Z. Yun, and T. H. Lai, “Deploying wireless sensors to achieve both coverage and connectivity,” in Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc ’06, (New York, NY, USA), pp. 131–142, ACM, 2006.