Maximizing network lifetime using coverage sets scheduling in wireless sensor networks

In a Wireless Sensor Network (WSN), when a large amount of sensors are randomly deployed into a detection area, an efficient sleep/active scheduling for sensors to maximize the network lifetime of target (or detection area) coverage, which is called the coverage problem, is an important issue. The problem was proved NP-complete. Recently, many methods were proposed for solving the coverage problem, each of which can be divided into two phases: the first is to find as many as possible coverage sets from the sensors and the other is to schedule the coverage sets got from the first phase. Therefore, all coverage problems involve the scheduling process of the coverage sets to maximize the network lifetime. In this paper, we investigate the Maximum Coverage Sets Scheduling (MCSS) problem: given a coverage set collection in which each coverage set covers all targets (or the whole detection area) in WSN, the problem is to find a feasible scheduling for the coverage set collection to maximize the network lifetime. Firstly, we prove the MCSS problem is NP-hard. Secondly, we formulate the problem as an integer linear programming problem. Thirdly, we first propose a greedy algorithm, called Greedy-MCSS, to solve the MCSS problem. Then based on the Greedy-MCSS algorithm, we propose an approximation algorithm, MCSS Algorithm (MCSSA) for solving the MCSS problem, which gives the theoretical performance guarantee. Finally, extensive simulation results are shown to further verify the performance of our algorithms.