An efficient genetic algorithm for maximizing area coverage in wireless sensor networks

Abstract Wireless sensor networks collect and transfer environmental data from a predefined region to a base station to be processed and analyzed. A major problem when designing these networks is deploying sensors such that their area coverage is maximized. Given a number of sensors with heterogeneous sensing ranges, the problem of coverage maximization is known to be NP-hard. As such, prevailing methods often rely on metaheuristic techniques while employing approximated fitness functions, resulting in modest solution quality and stability. This paper proposes a novel and efficient metaheuristic in the form of a genetic algorithm, which overcomes several weaknesses of existing metaheuristics, along with an exact method for calculating the fitness function for this problem. The proposed genetic algorithm includes a heuristic population initialization procedure, the proposed exact integral area calculation for the fitness function, and a combination of Laplace Crossover and Arithmetic Crossover Method operators. Experiments have been conducted to compare the proposed algorithm with five state-of-the-art methods on a wide range of problem instances. The results show that our algorithm delivers the best performance in terms of solution quality and stability on a majority of the tested instances.