Sensor Coverage and Target Detection Optimization using Genetic Algorithms

Abstract

In battlefield environments, enhancing situational awareness requires particular attention to two critical factors: coverage and detection. This study aims to optimize the coverage of a designated region and the detection of multiple targets using a limited set of available sensors. A Genetic Algorithm (GA)–based approach is employed to determine the optimal sensor deployment, maximizing both area coverage and target detection while minimizing the number of sensors used and ensuring a uniform spatial distribution. Uniformity is achieved by minimizing the repulsive forces between sensors, where these forces are modeled as functions of sensor strength and inter sensor distance. From this perspective, the fitness function consists of multiple objectives that are combined into a single scalar value by applying appropriate weighting factors. A compact chromosome structure is developed to support this multi-objective formulation. Each gene block encodes both the deployment coordinates and the type of sensor to be placed. Binary gene encoding is used to represent a wide range of continuous position values as well as sensor types. Targets are randomly distributed within a specified region, and it is assumed that they move collectively within a localized neighborhood. During the GA selection phase, the best chromosome is preserved in the chromosome pool. If the best solution remains unchanged for a predefined number of iterations, the algorithm terminates and the corresponding chromosome is taken as the optimal sensor deployment configuration.

Keywords

• Genetic algorithms
• Multi-objective fitness function
• Sensor coverage optimization
• Sensor detection optimization

References

1. [1] Lamine, A., Mguis, F., Snoussi, H., and Ghedira, K., “Coverage Optimization Using Multiple Unmanned Aerial Vehicles with Connectivity Constraint”, Proceedings of the International Wireless Communications and Mobile Computing Conference, 1361–1366, (2019).
2. [2] Khudhur, A. K. M. J. H., “An efficient drones path planning approach using enhanced genetic algorithms for combating terrorism and criminal activity”, Master of Science Thesis, Institute of Graduate Studies, Istanbul, (2021).
3. [3] Goldberg, D. E., and Holland, J. H., “Genetic algorithms and machine learning”, Machine Learning, 3(2): 95–99, (1988).
4. [4] Talbi, E. G., Metaheuristics from Design to Implementation, John Wiley & Sons, (2009).
5. [5] Forrest, S., “Genetic algorithms: principles of natural selection applied to computation”, Science, 261(5123): 872–878, (1993).
6. [6] Mitchell, M., An Introduction to Genetic Algorithms, MIT Press, (1999).
7. [7] Anderson, K., and Hsu, Y., “Genetic algorithm crossover strategy for enhanced solution space exploration”, AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, 2097, (1998).
8. [8] Yu, X., and Gen, M., Introduction to evolutionary algorithms, Springer, (2010).

9. [9] Gandomi, A. H., Yang, X.-S., Talatahari, S., and Alavi, A. H., “Metaheuristic algorithms in modeling and optimization”, Metaheuristic Applications in Structures and Infrastructures, 1–24, (2013).
10. [10] Zou, Y., and Chakrabarty, K., “Uncertainty-aware and coverage-oriented deployment for sensor networks”, Journal of Parallel and Distributed Computing, 64(7): 788–798, (2004).
11. [11] Singham, D., Therkildsen, M., and Schruben, L., “Applications of flocking algorithms to input modeling for agent movement”, Proceedings of the Winter Simulation Conference, 2443–2449, (2011).
12. [12] Doğan, E., “Sensor layout optimization using genetic algorithm for sniper localization systems”, Master of Science Thesis, METU, Ankara, (2019).
13. [13] Deif, D., and Gadallah, Y., “Wireless sensor network deployment using stochastic optimization techniques: a comparative study”, Proceedings of the Conference on Computing and Network Communications, 131–138, (2015).
14. [14] Benatia, M. A., Sahnoun, M., Baudry, D., Louis, A., El-Hami, A., and Mazari, B., “Multi-objective WSN deployment using genetic algorithms under cost, coverage, and connectivity constraints”, Wireless Personal Communications, 94(4): 2739–2768, (2017).
15. [15] Puri, V., Babu, A.R., Nagarajan, D., and Yadav, R., “Optimization approach for sensor deployment problem in wireless sensor network”, International Conference on Circuits and Systems in Digital Enterprise Technology, 1–6, (2018).
16. [16] Ndam N. A., Abdou, W., Dipanda, A., and Tonye, E., “Optimization of sensor deployment using multi-objective evolutionary algorithms”, Journal of Reliable Intelligent Environments, 2: 209–220, (2016).
17. [17] Ling, H., Zhu, T., He, W., Luo, H., Wang, Q., and Jiang, Y., “Coverage optimization of sensors under multiple constraints using the improved PSO algorithm”, Mathematical Problems in Engineering, Article ID 2020, (2020).
18. [18] Oh, S.C., et al., “Multiobjective optimization of sensor network deployment by a genetic algorithm”, IEEE Congress on Evolutionary Computation, 3917–3921, (2007).
19. [19] Oktay, D., “Sensor deployment optimization”, Master of Science Thesis, Gazi University, Ankara, (2004).
20. [20] Kevran, M.M., “Solving the multi-sensor positioning problem with genetic algorithms”, Air Force Academy Command, Institute of Aerospace Technologies, Istanbul, (2009).
21. [21] Li, S., Xu, C., Pan, W., and Pan, Y., “Sensor deployment optimization for detecting maneuvering targets”, International Conference on Information Fusion, Vol. 2, (2005).
22. [22] Liu, Z., Zhang, H., Smith, P., and Hui, Q., “Hierarchical optimization strategies for sensor network deployment”, World Automation Congress, (2012).
23. [23] Spanache, S., Escobet, T., and Travé-Massuyès, L., “Sensor placement optimisation using genetic algorithms”, DX Conference Proceedings, (2004).
24. [24] Liu, W., Gao, W., Sun, Y., and Xu, M., “Optimal sensor placement for spatial lattice structure based on genetic algorithms”, Journal of Sound and Vibration, 317(1): 175–189, (2008).
25. [25] Karataş, M., “Optimization of distributed underwater sensor networks with mixed integer nonlinear programming”, Marmara University Journal of Science, 24(3): 77–92, (2012).
26. [26] Özoğul, C., “A comparative study on optimal sensor placement for structural health monitoring applications”, Master of Science Thesis, Istanbul Technical University, Istanbul, (2019).
27. [27] Kodar, A., Mustika, F. A., and Wahab, A., “Utilizing genetic algorithm for optimization of maritime surveillance sensor network deployment”, International Conference on Engineering Technologies and Applied Sciences, 1–6, (2019).
28. [28] Singh, A., Amutha, J., Nagar, J., and Sharma, S., “A deep learning approach to predict the number of k-barriers for intrusion detection over a circular region”, Expert Systems with Applications, 211: 118588, (2023).
29. [29] Sun, S., Chen, Y., and Dong, L., “An optimization method for wireless sensor networks coverage based on genetic algorithm and reinforced whale algorithm”, Mathematical Biosciences and Engineering, 21(2): 2787–2812, (2024).
30. [30] Quan, L.V., Hanh, N.T., Binh, H.T.T., Toan, V.D., Ngoc, D.T., and Lam, B.T., “A bi-population genetic algorithm based on multi-objective optimization for mobile wireless sensor networks”, Expert Systems with Applications, 217: 119486, (2023).
31. [31] Kalaycı, C., and Güngör, A., “A genetic algorithm-based examination timetabling model focusing on student success”, Gazi University Journal of Science, 25(1): 137–153, (2012).
32. [32] Arık, O. A., “Genetic algorithm application for permutation flow shop scheduling problems”, Gazi University Journal of Science, 35(1): 92–111, (2022).
33. [33] Bhushan, B., and Shadique, G. L., “Optimization of coverage hole detection in wireless sensor network using genetic algorithm”, International Conference on Trends in Electronics and Informatics, 138–143, (2019).
34. [34] Carpenter, C., “Production-optimization strategy using a hybrid genetic algorithm”, Journal of Petroleum Technology, 68(12): 54–55, (2016).
35. [35] Galletly, J. E., “An overview of genetic algorithms”, Kybernetes, 21(6): 26–30, (1992).
36. [36] Back, D. T., Evolutionary algorithms in theory and practice, Oxford University Press, (1996).
37. [37] Beasley, D., Bull, D. R., and Martin, R. R., “An overview of genetic algorithms: fundamentals”, University Computing, 15(2): 58–59, (1993).
38. [38] Talbi, E. G., Metaheuristics: from design to implementation, Wiley, (2009).
39. [39] Reeves, C. R., and Rowe, J. E., Genetic algorithms: principles and perspectives, Kluwer Academic Publishers, (2002).
40. [40] Hocaoğlu, M. F., and Tosun, E., “Consensus among multi-criteria decision-making methods: using methods as a voter”, Journal of the Faculty of Engineering and Architecture of Gazi University, 40(1): 103–120, (2024).
41. [41] Dao, S. D., Abhary, K., and Marian, R., “A bibliometric analysis of genetic algorithms throughout the history”, Computers & Industrial Engineering, 110: 395–403, (2017).
42. [42] Ab Wahab, M.N., Nefti-Meziani, S., and Atyabi, A., “A comprehensive review of swarm optimization algorithms”, PLOS ONE, 10(5): 1–36, (2015).