Title :
A Bipopulation-Based Evolutionary Algorithm for Solving Full Area Coverage Problems
Author :
Joon-Hong Seok ; Joon-Yong Lee ; Won Kim ; Ju-Jang Lee
Author_Institution :
Dept. of Electr. Eng., Korea Adv. Inst. of Sci. & Technol., Daejeon, South Korea
Abstract :
The full area coverage sensor deployment problem is a challenging issue in wireless sensor networks. We focus on sensor deployment strategies that aim to acquire a full-coverage state with a minimum number of sensors in a predetermined target region that includes non-penetrable obstacles. This paper presents an efficient bipopulation-based evolutionary full area coverage (BEFAC) algorithm that involves a bipopulation structure composed of a full- and partial-coverage populations. Fitness functions, stochastic unary recombination operators, and selection procedures between the two populations are well designed. Through applying the proposed BEFAC, a full-coverage state is acquired with a minimum number of deployed sensors in the target region, which has non-penetrable obstacles, and the algorithm avoids getting caught in local minima. The performance results reveal that BEFAC outperforms the conventional deployment methods in terms of the number of deployed sensors and the number of required fitness evaluations.
Keywords :
evolutionary computation; sensor placement; wireless sensor networks; BEFAC algorithm; bipopulation-based evolutionary full area coverage algorithm; fitness functions; full area coverage sensor deployment problem; full-partial-coverage populations; nonpenetrable obstacles; partial-coverage populations; stochastic unary recombination operators; wireless sensor networks; Biological cells; Radio frequency; Robot sensing systems; Sociology; Statistics; Wireless sensor networks; Area coverage problem; evolutionary sensor deployment; full coverage problem;
Journal_Title :
Sensors Journal, IEEE
DOI :
10.1109/JSEN.2013.2274693