Maximum Lifetime Scheduling for Target Coverage and Data Collection in Wireless Sensor Networks

Target coverage and data collection are two fundamental problems for wireless sensor networks (WSNs). Target coverage is needed to select sensors in a given area that can monitor a set of interesting points. Data collection is needed to transmit the sensed data from sensors to a sink. Since, in many applications, sensors are battery powered, it is expected that a WSN can work untended for a long period. This paper addresses the scheduling problems for both target coverage and data collection in WSNs with the objective of maximizing network lifetime. First, a polynomial-time approximation scheme is developed for the case where the density of target points is bounded, and then, a polynomial-time constant-factor approximation algorithm is developed for the general case. It is also proved that it is NP-hard to find a maximum lifetime scheduling of target cover and data collection for a WSN, even if all the sensors have the same sensing radius and the same transmission radius. Further, the practical efficiency of our algorithms is analyzed through simulation. These extensive simulation results show better performances of our algorithms compared with other research findings.