Genetic Algorithm Based Node Deployment in Hybrid Wireless Sensor Networks

Omar Banimelhem, Moad Mowafi, Walid Aljoby

Department of Computer Engineering, Jordan University of Science and Technology, Irbid, Jordan.
Department of Network Engineering and Security, Jordan University of Science and Technology, Irbid, Jordan.

DOI: 10.4236/cn.2013.54034                

Abstract

In hybrid wireless sensor networks composed of both static and mobile sensor nodes, the random deployment of stationary nodes may cause coverage holes in the sensing field. Hence, mobile sensor nodes are added after the initial deployment to overcome the coverage holes problem. To achieve optimal coverage, an efficient algorithm should be employed to find the best positions of the additional mobile nodes. This paper presents a genetic algorithm that searches for an optimal or near optimal solution to the coverage holes problem. The proposed algorithm determines the minimum number and the best locations of the mobile nodes that need to be added after the initial deployment of the stationary nodes. The performance of the genetic algorithm was evaluated using several metrics, and the simulation results demonstrated that the proposed algorithm can optimize the network coverage in terms of the overall coverage ratio and the number of additional mobile nodes.

Keywords

Target Coverage; Node Deployment; Genetic Algorithm; Wireless Sensor Networks

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “Wireless Sensor Networks: A Survey,” Computer Networks, Vol. 38, No. 4, 2002, pp. 393-422. http://dx.doi.org/10.1016/S1389-1286(01)00302-4
[2]	B. Wang, “Coverage Problems in Sensor Networks: A Survey,” ACM Computing Surveys, Vol. 43, No. 4, 2011, 53 p. http://dx.doi.org/10.1145/1978802.1978811
[3]	M. Younis and K. Akkaya, “Strategies and Techniques for Node Placement in Wireless Sensor Networks: A Survey,” Ad Hoc Networks, Vol. 6, No. 4, 2008, pp. 621-655. http://dx.doi.org/10.1016/j.adhoc.2007.05.003
[4]	A. Howard, M. J. Mataric, and G. S. Sukhatme, “Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem,” Proceedings of 6th International Symposium on Distributed Autonomous Robotics Systems, Fukuoka, 25-27 June 2002, pp. 299-308. http://dx.doi.org/10.1007/978-4-431-65941-9_30
[5]	Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Transactions on Embedded Computing Systems, Vol. 3, No. 1, 2004, pp. 61-91. http://dx.doi.org/10.1145/972627.972631
[6]	D. E. Goldberg and J. H. Holland. “Genetic Algorithms and Machine Learning,” Machine Learning, Vol. 3, No. 2, 1988, pp. 95-99. http://dx.doi.org/10.1023/A:1022602019183
[7]	G. Wang, G. Cao and T. Porta, “Movement-Assisted Sensor Deployment,” IEEE Transactions on Mobile Computing, Vol. 5, No. 6, 2006, pp. 640-652. http://dx.doi.org/10.1109/TMC.2006.80
[8]	A. Tahiri, E. Egea-López, J. Vales-Alonso, J. GarcíaHaro and M. Essaaidi, “A Novel Approach for Optimal Wireless Sensor Network Deployment,” Proceedings of Symposium on Progress in Information & Communication Technology (SPICT’09), Kuala Lumpur, 7-8 December 2009, pp. 40-45. http://dx.doi.org/10.1109/TMC.2007.1022
[9]	G. Wang, G. Cao, P. Berman and T. Porta, “Bidding Protocols for Deploying Mobile Sensors,” IEEE Transactions on Mobile Computing, Vol. 6, No. 5, 2007, pp. 515-528. doi: 10.1109/TMC.2007.1022
[10]	N. Ahmed, S. Kanhere and S. Jha, “A Pragmatic Approach to Area Coverage in Hybrid Wireless Sensor Networks,” Wireless Communications and Mobile Computing, Vol. 11, No. 1, 2011, pp. 23-45. http://dx.doi.org/10.1002/wcm.913
[11]	X. Wang and S. Wang, “Hierarchical Deployment Optimization for Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, Vol. 10, No. 7, 2011, pp. 354-370. http://dx.doi.org/10.1109/TMC.2010.216
[12]	G. Wang, L. Guo, H. Duan, L. Liu and H. Wang, “Dynamic Deployment of Wireless Sensor Networks by Biogeography Based Optimization Algorithm,” Journal of Sensor and Actuator Networks, Vol. 1, No. 2, 2012, pp. 86-96. http://dx.doi.org/10.3390/jsan1020086
[13]	T. Kalayci and A. Ugur, “Genetic Algorithm-Based Sensor Deployment with Area Priority,” Cybernetics and Systems, Vol. 42, No. 8, 2011, pp. 605-620. http://dx.doi.org/10.1080/01969722.2011.634676
[14]	X. He, X. Gui and J. An, “A Deterministic Deployment Approach of Nodes in Wireless Sensor Networks for Target Coverage,” Journal of Xi’an Jiaotong University, No. 6, 2010, pp. 6-9.
[15]	Y. Xu and X. Yao, “A GA Approach to the Optimal Placement of Sensors in Wireless Sensor Networks with Obstacles and Preferences,” Proceedings of 3rd IEEE Consumer Communications and Networking Conference, Las Vegas, 8-10 January 2006, pp. 127-131.http://dx.doi.org/10.1109/CCNC.2006.1593001
[16]	J. Seo, Y. Kim, H. Ryou and S. Kang, “A Genetic Algorithm for Sensor Deployment Based on Two-Dimensional Operators,” Proceedings of 2008 ACM Symposium on Applied Computing, Fortaleza, 16-20 March 2008, pp. 1812-1813. http://dx.doi.org/10.1145/1363686.1364121
[17]	A. Tripathi, P. Gupta, A. Trivedi and R. Kala, “Wireless Sensor Node Placement using Hybrid Genetic Programming and Genetic Algorithms,” International Journal of Intelligent Information Technologies, Vol. 7, No. 2, 2011, pp. 63-83. http://dx.doi.org/10.4018/jiit.2011040104
[18]	K. S. Yildirim, T. E. Kalayci and A. Ugur, “Optimizing Coverage in a K-Covered and Connected Sensor Network using Genetic Algorithms,” Proceedings of the 9th WSEAS International Conference on Evolutionary Computing (EC’08), Sofia, 2-4 May 2008, pp. 21-26.
[19]	C. Sahin, et al., “Design of Genetic Algorithms for Topology Control of Unmanned Vehicles,” International Journal of Applied Decision Sciences, Vol. 3, No. 3, 2010, pp. 221-238. http://dx.doi.org/10.1504/IJADS.2010.036100
[20]	Y. Qu and S. Georgakopoulos, “Relocation of Wireless Sensor Network Nodes using a Genetic Algorithm,” Proceedings of 12th Annual IEEE Wireless and Microwave Technology Conference (WAMICON), Clearwater Beach, 18-19 April 2011, pp. 1-5. http://dx.doi.org/10.1109/WAMICON.2011.5872882
[21]	F. Nematy, N. Rahmani and R. Yagouti, “An Evolutionary Approach for Relocating Cluster Heads in Wireless Sensor Networks,” Proceedings of International Conference on Computational Intelligence and Communication Networks (CICN), Bhopal, 26-28 November 2010, pp. 323-326. http://dx.doi.org/10.1109/CICN.2010.76
[22]	N. Rahmani, F. Nematy, A. Rahmani and M. Hosseinzadeh, “Node Placement for Maximum Coverage Based on Voronoi Diagram using Genetic Algorithm in Wireless Sensor Networks,” Australian Journal of Basic and Applied Sciences, Vol. 5, No. 12, 2011, pp. 3221-3232.