Maximizing Network Lifetime for Connected Target Coverage in Wireless Sensor Networks

Network lifetime is one of the critical issues in sensor networks. An effective approach to prolong the network lifetime is to schedule the active states of sensors: only a subset of the deployed sensors that can maintain both sensing coverage and network connectivity is scheduled to be active. In this paper, we consider the connected target coverage (CTC) problem with the objective of maximizing the network lifetime by scheduling sensors into multiple sets, each of which can maintain both target coverage and connectivity among all the active sensors and the sink. We model the CTC problem as a maximum cover tree (MCT) problem and prove that the MCT problem is NP-complete. We give an upper bound on lifetime of the MCT problem and develop a heuristic algorithm called communication weighted greedy cover (CWGC) algorithm to solve it. We study the performance of CWGC algorithm comparing it with other algorithms that consider the coverage and connectivity problems independently. Simulation results show that CWGC algorithm performs much better than others in terms of the network lifetime and the lifetime obtained by our algorithm is close to the upper bound