An effective genetic algorithm to improve wireless sensor network lifetime for large-scale surveillance applications

Wireless sensor network lifetime for large-scale surveillance systems is defined as the time span that all targets can be covered. One approach to extend the lifetime is to divide the deployed sensors into disjoint subsets of sensors, or sensor covers, such that each sensor cover can cover all targets and work by turns. The more sensor covers can be found, the longer sensor network lifetime can be prolonged. Finding the maximum number of sensor covers can be solved via transformation to the Disjoint Set Covers (DSC) problem, which has been proved to be NP-complete. For this optimization problem, existing heuristic algorithms either get unsatisfactory solutions in some cases or take exponential time complexity. This paper proposes a genetic algorithm to solve the DSC problem. The simulation results show that the proposed algorithm can get near-optimal solutions with polynomial computation time and can improve the performance of the most constrained-minimum constraining heuristic algorithm by 16% in solution quality.