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

• DOI: 10.1016/j.ins.2019.02.059
• Publication Date: 2019-02-25T16:34:36Z
• Authors: Nguyen Thi Hanh; Huynh Thi Thanh Binh; Nguyen Xuan Hoai; Marimuthu Swami P...
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

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.