.png){kind=icon}
.png){kind=icon}
Return
A genetic algorithm method for improving suboptimal sensor arrangements in coverage and connectivity problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.asoc.2024.112047.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper is concerned with the solution of a Coverage and Connectivity Problem (CCP). The proposed method performs the placement of sensors forming a connected Wireless Sensor Network (WSN) to fully cover a Field of Interest (FoI). Full coverage is attained despite the presence of opaque obstacles that impair both sensing and communication. To this end, we leverage set operations involving polygons to tessellate the free space. Moreover, we propose the concept of C R-visibility to assess the total area coverage of a polygon by a sensor. The deployment of the minimal number of sensors to completely cover the FoI is cast into the form of an Integer Linear Program (ILP). Two different formulations of connectivity constraints are appended to the ILP. The first one is necessary and sufficient for connectivity, whereas the second alternative is only sufficient. While the number of inequalities in the former grows combinatorially with the number of sensors, the growth is linear in the latter, rendering it more computationally appealing for real-sized FoI. Lastly, we formulate an unconstrained version of the CCP, which is solved by a Genetic Algorithm (GA) with integer variables. We present a small simulation scenario for initial illustration of the proposed method, and a larger, real-life scenario based on the map of an actual urban setting. The results obtained with the real-life scenario show that: (i) high-quality solutions can be obtained in short computation times by imposing the sufficient constraints for connectivity; (ii) the large number of inequalities associated to the necessary and sufficient constraints render the numerical solution impractical; (iii) by using random initialization, the GA solution of the unconstrained problem requires more sensors than the ILP solution with the sufficient connectivity constraint; (iv) including that ILP solution in the initial population of the GA enables it to find a sensor placement that requires fewer sensors.
Keywords:
Wireless Sensor Network (WSN)
Coverage and connectivity problem (CCP)
Computational geometry
Integer Linear Programming (ILP)
Genetic algorithm (GA)
Journal
IF:
6.6
Papers:
1.4W
Citations:
4.8W
View more organizations