A Multi-Objective Metaheuristic Approach for Improving Coverage and Connectivity in Wireless Sensor Networks
Subject Areas : electrical and computer engineeringM. Basirnezhad 1 , M. Houshmand 2 * , S. A. Hosseini 3 , M. Jalali 4
1 - گروه مهندسی کامپیوتر، واحد مشهد، دانشگاه آزاد اسلامی، مشهد، ایران
2 -
3 - 1Department of Electrical Engineering, Mashhad Branch, Islamic Azad University, Mashhad, Iran.
4 - گروه علمداده کاربردی و هوشمصنوعی، دانشگاه SRH هایدلبرگ، هایدلبرگ، آلمان
Keywords: Connectivity, metaheuristic algorithms, coverage, wireless sensor networks,
Abstract :
This paper investigates and presents a new optimization algorithm titled Multi-Objective Cheetah Optimizer (MOCO), developed with the aim of increasing coverage and improving connectivity in wireless sensor networks. Utilizing metaheuristic optimization concepts, this algorithm offers a novel approach for optimally determining sensor node positions and managing resources. In this method, by defining a multi-criteria objective function including maximizing area coverage, improving connectivity between nodes, and reducing energy consumption, it is able to establish a suitable balance among these objectives. The proposed algorithm is inspired by the random search capabilities and the acceleration of the cheetah algorithm, enabling more effective searching in the solution space. The results of simulations and performed experiments show that MOCO, compared to three algorithms CSSO, MOFAC-GA-PSO, and HHA, has been able to increase the environment coverage rate to over 94.5%, raise the network connectivity rate to approximately 97.8%, and simultaneously reduce the average energy consumption of sensors by up to 15% compared to other algorithms.
[1] J. Amutha, S. Sharma, and J. Nagar,"WSN Strategies based on sensors, deployment, sensing models, coverage and energy efficiency: Review, approaches and open issues," Wireless Personal Communications, vol. 111, no. 2, pp. 1089-1115, Oct. 2020.
[2] C. So-In, T. G. Nguyen, and N.G. Nguyen, "An efficient coverage hole-healing algorithm for area-coverage improvements in mobile sensor networks," Peer-to-Peer Networking and Applications, vol. 12, no. 3, pp. 541-552, Aug. 2019.
[3] S. Abdollahzadeh, and N. J. Navimipour, "Deployment strategies in the wireless sensor network: A comprehensive review," Computer Communications, vol. 91-92, pp. 1-16, Oct. 2016.
[4] V. Chowdary and T. Bera, "Types of coverage in wireless sensor network: A survey," vol. 8, no. 4, pp. 463-467, Feb. 2022.
[5] N. Saadi, et al., "Maximum lifetime target coverage in wireless sensor networks," Wireless Personal Communications, vol. 111, no. 3, pp. 1525-1543, Jul. 2020.
[6] A. Katti, "Target coverage in random wireless sensor networks using cover sets," Journal of King Saud University - Computer and Information Sciences, vol. 34, no. 3, pp. 734-746, Mar. 2022.
[7] H.T.T. Binh, et al., "Metaheuristics for maximization of obstacles constrained area coverage in heterogeneous wireless sensor networks, "Applied Soft Computing, vol. 86, Article ID: 105939, Nov. 2020.
[8] R. Priyadarshi, B. Gupta, and A. Anurag, "Wireless sensor networks deployment: A result oriented analysis," Wireless Personal Communications, vol. 113, no. 2, pp. 843-866, 2020.
[9] L. Kong, et al., "Surface coverage in sensor networks," IEEE Trans. on Parallel and Distributed Systems, vol. 25, no. 1, pp. 234-243, Jan. 2014.
[10] H. M. Ammari, "Connected k-coverage in two-dimensional wireless sensor networks using hexagonal slicing and area stretching," Journal of Parallel and Distributed Computing, vol. 153, no. 2, pp. 89-109, Jul. 2021.
[11] Al-Turjman, F.M., H.S. Hassanein, and M. Ibnkahla, "Quantifying connectivity in wireless sensor networks with grid-based deployments," Journal of Network and Computer Applications, vol. 36, no. 1, pp. 368-377, Jan. 2013.
[12] Liu, Y., et al., "A virtual square grid-based coverage algorithm of redundant node for wireless sensor network," Journal of Network and Computer Applications, vol. 36, no. 2, pp. 811-817, Mar. 2013.
[13] F. Abbasi, A. Mesbahi, and J.M. Velni, "A new voronoi-based blanket coverage control method for moving sensor networks," IEEE Trans. on Control Systems Technology, vol. 27, no. 1, pp. 409-417, Mar. 2019.
[14] A. Boukerche and X. Fei, "A voronoi approach for coverage protocols in wireless sensor networks," in Proc. IEEE Global Telecommunications Conf., vol. 5, pp. 5190-5194, Washington, DC, USA, 26-30 Nov. 2007.
[15] S. Fortune, "Voronoi diagrams and DELAUNAY triangulations," in Computing in Euclidean Geometry, pp. 225-265, World Scientific Publishing, 1995.
[16] J. Jiang, Z. Song, H. Zhang, and W. Dou,"Voronoi-based improved algorithm for connected coverage problem in wireless sensor networks," in Proc. of the 2005 Int. Conf. on Embedded and Ubiquitous Computing, pp. 224-233, Nagasaki, Japan, 6-9 Dec. 2005.
[17] X. Deng, et al., "An optimized node deployment solution based on a virtual spring force algorithm for wireless sensor network applications," Sensors, vol. 19, no. 8, Article ID: 1817, Sept. 2019.
[18] [18] Y. Li, B. Zhang, and S. Chai, "An energy balanced-virtual force algorithm for mobile-WSNs," in Proc. IEEE Int. Conf. on Mechatronics & Automation, Beijing, China, pp. 1779-1784, 2-5 Aug. 2015.
[19] Liu, S., R. Zhang, and Y. Shi, "Design of coverage algorithm for mobile sensor networks based on virtual molecular force," Computer Communications, vol. 150, pp. 269-277, Jan. 2020.
[20] S. Wang, et al., "A virtual force algorithm-Lévy-embedded grey wolf optimization algorithm for wireless sensor network coverage optimization," Sensors, vol. 19, no. 12, Article ID:2735, Sept. 2019.
[21] X. Wang, S. Wang, and D. Bi, "Virtual force-directed particle swarm optimization for dynamic deployment in wireless sensor networks," in Proc. Int. Conf. on Intelligent Computing, pp. 292-303, Qingdao, China, 21-24 Aug. 2007.
[22] C. C. Yang and J. H. Wen, "A hybrid local virtual force algorithm for sensing deployment in wireless sensor network," in Proc. 7th Int. Conf. on Innovative Mobile and Internet Services in Ubiquitous Computing, pp. 617-621, Taichung, Taiwan, 3-5 Jul 2013.
[23] Y. Yao, et al., "Coverage enhancement strategy for WSNs based on virtual force-directed ant lion optimization algorithm," IEEE Sensors Journal, vol. 21, no. 17, pp. 19611-19622, Oct. 2021.
[24] Zou, Y. and K. Chakrabarty, "Sensor deployment and target localization in distributed sensor networks, "ACM Trans. Embeded Computer Systems, vol. 3, no. 1, pp. 61-91, Feb. 2004.
[25] K. Mougou, et al., "Redeployment of randomly deployed wireless mobile sensor nodes," in Proc. IEEE 76th Vehicular Technology Conf. VTC Fall, 5 pp., Québec, Canada, 3-6 Sept. 2012.
[26] X. Yu, et al., "A node deployment algorithm based on Van Der Waals force in wireless sensor networks," International Journal of Distributed Sensor Networks, vol. 9, no. 10, Article ID: 505710, 2013.
[27] M. Song, L. Yong, W. Li, and T. A. Gulliver, "Improving wireless sensor network coverage using the VF-BBO algorithm," in Proc. IEEE Pacific Rim Conf. on Communications, Computers and Signal Processing, pp. 318-321, Victoria, Canada, 27-29 Aug. 2013.
[28] J. Xie, et al., "A sensor deployment approach using improved Virtual force algorithm based on area intensity for multisensor networks," Mathematical Problems in Engineering, vol. 2019, Article ID: 8015309, Mar. 2019.
[29] X. Qi, et al., "A wireless sensor node deployment scheme based on embedded virtual force resampling particle swarm optimization algorithm," Applied Intelligence, vol. 52, no.7, pp. 7420-7441, Sept. 2022.
[30] Q. Wen, et al., "Coverage enhancement algorithm for WSNs based on vampire bat and improved virtual force," IEEE Sensors Journal, vol. 22, no. 8, pp. 8245-8256, Sept. 2022.
[31] V. Kiani and M. Imanparast, "A bi-objective virtual-force local search PSO algorithm for improving sensing deployment in wireless sensor networks," Journal of AI and Data Mining, vol. 11, no. 1, pp. 1-12, Jan. 2023.
[32] W. A. Farias, et al.,"Voronoi-based approach to increase connectivity and coverage in randomly deployed wireless sensor networks," in Proc. 8th Int. Symp. on Instrumentation Systems, Circuits and Transducers, 6 pp., Joao Pesoa, Brazil, 2-6 Sept. 2024.
[33] W. -H., Liao, Y. Kao, and R. -T. Wu, "Ant colony optimization-based sensor deployment protocol for wireless sensor networks," Expert Systems with Applications, vol. 38, no. 6, p. 6599-6605, Jun. 2011.
[34] C. Öztürk, D. Karaboǧa, and B. Gorkemli, "Artificial bee colony algorithm for dynamic deployment of wireless sensor networks," Turkish Journal of Electrical Engineering and Computer Sciences, vol. 20, no. 1, pp. 255-262, Mar. 2012.
[35] G. Wang, et al., "Dynamic deployment of wireless sensor networks by biogeography based optimization algorithm," Journal of Sensor and Actuator Networks, vol. 1, no. 2, pp. 86-96, Apr. 2012.
[36] S. Özdemir, B.a.A. Attea, and Ö. A. Khalil, "Multi-objective evolutionary algorithm based on decomposition for energy efficient coverage in wireless sensor networks, "Wireless Personal Communications, vol. 71, no. 1, pp. 195-215, Mar. 2013.
[37] M. Abo-Zahhad, et al., "Coverage maximization in mobile wireless sensor networks utilizing immune node deployment algorithm," in Proc. IEEE 27th Canadian Conf. on Electrical and Computer Engineering, 6 pp., Toronto, Canada, 4-7 May 2014.
[38] K. Y. Bendigeri, and J. D. Mallapur, Energy Aware Node Placement Algorithm for Wireless Sensor Network, 2014. [39] S. Gupta, P. Kuila, and P. Jana, "Genetic algorithm for k-connected relay node placement in wireless sensor networks," in Proc. of the 2nd Int. Conf. on Computer and Communication Technologies, vol. 1, pp. 721-729, Hyderabad, India, 24-26 Jul. 2016. [40] J. George and R. M. Sharma, "Relay node placement in wireless sensor networks using modified genetic algorithm," in Proc. 2nd Int. Conf. on Applied and Theoretical Computing and Communication Technology, pp. 551-556, Bengaluru, India, 21-23 Jul. 2016.
[41] Y. El Khamlichi, et al., "A hybrid algorithm for optimal wireless sensor network deployment with the minimum number of sensor nodes," Algorithms, vol. 10, no. 3, pp. 80-88, Sept. 2017.
[42] O. M. Alia and A. Al-Ajouri, "Maximizing wireless sensor network coverage with minimum cost using harmony search algorithm," IEEE Sensors Journal, vol. 17, no. 3, p. 882-896, Jun. 2017. [43] R. Ozdag and M. Canayaz, "A new dynamic deployment approach based on whale optimization algorithm in the optimization of coverage rates of wireless sensor networks," European Journal of Technic, vol. 7, no. 1, pp. 119-130, Feb. 2017.
[44] E. Tuba, M. Tuba, and M. Beko, "Mobile wireless sensor networks coverage maximization by firefly algorithm," in Proc. 27th Int. Conf. Radioelektronika, 5 pp., Brno, Czech Republic, 19-20 Apr. 2017.
[45] B. Cao, et al., "Deployment optimization for 3D industrial wireless sensor networks based on particle swarm optimizers with distributed parallelism," Journal of Network and Computer Applications, vol. 103, pp. 225-238, Feb. 2018.
[46] N. T. Hanh, et al., "An efficient genetic algorithm for maximizing area coverage in wireless sensor networks," Information Sciences, vol. 488, pp. 58-75, Jul. 2019.
[47] Y. Yue, L. Cao, and Z. Luo, "Hybrid artificial bee colony algorithm for improving the coverage and connectivity of wireless sensor networks," Wireless Personal Communications, vol. 108, no. 3, pp. 1719-1732, May 2019.
[48] S. S. Mohar, S. Goyal, and R. Kaur, "Optimized sensor nodes deployment in wireless sensor network using bat algorithm," Wireless Personal Communications, vol. 116, no. 4, pp. 2835-2853, Aug. 2021.
[49] D. Arivudainambi, R. Pavithra, and P. Kalyani, "Cuckoo search algorithm for target coverage and sensor scheduling with adjustable sensing range in wireless sensor network," Journal of Discrete Mathematical Sciences and Cryptography, vol. 24, no. 4, pp. 975-996, Jul. 2021.
[50] L. Cao, et al., "A novel coverage optimization strategy for heterogeneous wireless sensor networks Based on connectivity and reliability," IEEE Access, vol. 9, pp. 18424-18442, 2021.
[51] G. Zhou, T. Zhang, and Y Zhou, "Elite opposition-based bare bones Mayfly algorithm for wireless sensor networks coverage optimization," Arabian Journal for Science and Engineering, vol. 50, pp.719-739, 2025.
[52] Y. Wei, et al., "SSMA: simplified slime mould algorithm for optimization wireless sensor network coverage problem," Systems Science & Control Engineering, vol. 10, no. 1, pp. 662-685, Feb. 2022.
[53] H. A. Wasay and P. K. Priya, "Effective coverage optimization techniques in WSN using the Harris hawk algorithm," in Proc. Int. Conf. on Recent Trends in Microelectronics, Automation, Computing and Communications Systems, pp. 281-286, Heydarabad, India, 28-30 Dec. 2023.
[54] H. Chen, et al., "A multi-strategy improved sparrow search algorithm for coverage optimization in a WSN," Sensors, vol. 23, no. 8, Article ID: 4124, Apr.-2 2023.
[55] T. -K. Dao, T. -D. Nguyen, and V. -T. Nguyen, "An improved honey badger algorithm for coverage optimization in wireless sensor network," Journal of Internet Technology, vol. 24, no. 2, pp. 363-377, Mar. 2023.
[56] L. Chen, et al., "Balancing the trade-off between cost and reliability for wireless sensor networks: a multi-objective optimized deployment method," Applied Intelligence, vol. 53, no. 8, pp. 9148-9173, Jun. 2023.
[57] S. K., De, et al., "Coverage area maximization using MOFAC-GA-PSO hybrid algorithm in energy efficient WSN design," IEEE Access, vol. 11, pp. 99901-99917, 2023.
[58] Y. Ou, et al., "An improved grey wolf optimizer with multi-strategies coverage in wireless sensor networks," Symmetry, vol. 16, no. 3, pp. 19-26, Apr. 2024.
[59] S. Sun, Y. Chen, and L. Dong, "An optimization method for wireless sensor networks coverage based on genetic algorithm and reinforced whale algorithm," Mathematical Biosciences and Engineering, vol. 21, no. 2, pp. 2787-2812, 2024.
[60] M. A. Akbari, et al., "The cheetah optimizer: A nature-inspired metaheuristic algorithm for large-scale optimization problems," Scientific Reports, vol. 12, Article ID: 10953, Jun. 2022.