Modelo de posicionamento de nos sensores através da utilização de um algoritmo genético satisfazendo as restrições de k-cobertura e m-conectividade

Abstract

The coverage problem in wireless sensor networks consists of: given n targets (or observa tion points) find a coverage scheme in order to contemplate the n points, using the least number of sensor nodes. Some redundancy criteria can be incorporated in this problem, such as the degree of connectivity of each sensor node (m - connectivity) and the degree of coverage of each target (k - coverage), among others. In this work, the problems of covering sensor nodes with the k-coverage and m-connectivity constraints are addressed simultaneously. Because it is a NP-Complete problem, it is proposed to use a specific ge netic algorithm for the sensor positioning problem, with the application of a modification of the crossover function based on the Flexible Genetic Algorithm and use of the Voronoi Diagram and a function of perturbation of the sensor nodes to perform a preprocessing in the positioning of the nodes. The experimental results show that the proposed algorithm obtained a good performance in relation to the number of selected sensor nodes, choosing the least amount of sensor nodes and maintaining the k - coverage and m - connectivity of the network, after applying the modifications described.