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

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.

• Shaimaa M. Mohamed
• Haitham S. Hamza
• Imane A. Saroit

• Wireless Sensor Networks (WSN)
• Harmony Search Algorithms
• K-Coverage
• Mobile WSN.

[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.