Evolutionary full-coverage minimum sensor deployment using dual population structure and multiple overlap measure

Evolutionary sensor deployment algorithm using the dual population scheme and the multiple overlap measure (ESDA-DPMO) is proposed to solve the full-coverage problem with non-penetrable obstacles. The full-coverage state group (FCSG) and the non-full-coverage state group (NFCSG) find sensor deployment solutions using different fitness functions, mutation operators and selection operators, respectively. Two distinguished search directions keep genetic diversity of sensor deployment solutions and avoid getting stuck in local optimum. In addition, information change between two is well designed for efficient exploration ability. The proposed multiple overlap measure boosts both evolution of FCSG and NFCSG. In the FCSG, by gathering sensors together as much as possible, there is a high probability of reducing redundant sensor without breaking full-coverage state. In contrast, in the NFCSG, by scattering sensors as much as possible to get lower overlap rate, higher coverage rate is obtained using same number of sensors. We perform simulations on 3 virtual maps to verify the proposed ESDA-DPMO as compared to conventional approaches. The results show that the proposed ESDA-DPMO provides full-coverage solutions efficiently.