Hybrid Discrete Particle Swarm Optimization Algorithm with Genetic Operators for Target Coverage Problem in Directional Wireless Sensor Networks

Abstract

For a sensing network comprising multiple directional sensors, maximizing the number of covered targets but minimizing sensor energy use is a challenging problem. Directional sensors that can rotate to modify their sensing directions can be used to increase coverage and decrease the number of activated sensors. Solving this target coverage problem requires creating an optimized schedule where (1) the number of covered targets is maximized and (2) the number of activated directional sensors is minimized. Herein, we used a discrete particle swarm optimization algorithm (DPSO) combined with genetic operators of the genetic algorithm (GA) to compute feasible and quasioptimal schedules for directional sensors and to determine the sensing orientations among the directional sensors. We simulated the hybrid DPSO with GA operators and compared its performance to a conventional greedy algorithm and two evolutionary algorithms, GA and DPSO. Our findings show that the hybrid scheme outperforms the greedy, GA, and DPSO algorithms up to 45%, 5%, and 9%, respectively, in terms of maximization of covered targets and minimization of active sensors under different perspectives. Finally, the simulation results revealed that the hybrid DPSO with GA produced schedules and orientations consistently superior to those produced when only DPSO was used, those produced when only GA was used, and those produced when the conventional greedy algorithm was used.

Keywords

• target coverage problem
• directional sensor networks
• genetic algorithm
• discrete particle swarm optimization