Please use this identifier to cite or link to this item: https://doi.org/10.1109/TNET.2007.911432
Title: Lifetime maximization for connected target coverage in wireless sensor networks
Authors: Zhao, Q.
Gurusamy, M. 
Keywords: Approximation algorithms
Coverage
Network lifetime
NP-complete
Sensor activity scheduling
Wireless sensor networks
Issue Date: 2008
Source: Zhao, Q., Gurusamy, M. (2008). Lifetime maximization for connected target coverage in wireless sensor networks. IEEE/ACM Transactions on Networking 16 (6) : 1378-1391. ScholarBank@NUS Repository. https://doi.org/10.1109/TNET.2007.911432
Abstract: 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 determine an upper bound on the network lifetime for the MCT problem and then develop a (1+w H (M) approximation algorithm to solve it, where w is an arbitrarily small number, H(M)=∑1≤i≤M(1/i) and M is the maximum number of targets in the sensing area of any sensor. As the protocol cost of the approximation algorithm may be high in practice, we develop a faster heuristic algorithm based on the approximation algorithm called Communication Weighted Greedy Cover (CWGC) algorithm and present a distributed implementation of the heuristic algorithm. We study the performance of the approximation algorithm and CWGC algorithm by comparing them with the lifetime upper bound and other basic algorithms that consider the coverage and connectivity problems independently. Simulation results show that the approximation algorithm and CWGC algorithm perform much better than others in terms of the network lifetime and the performance improvement can be up to 45% than the best-known basic algorithm. The lifetime obtained by our algorithms is close to the upper bound. Compared with the approximation algorithm, the CWGC algorithm can achieve a similar performance in terms of the network lifetime with a lower protocol cost. © 2008 IEEE.
Source Title: IEEE/ACM Transactions on Networking
URI: http://scholarbank.nus.edu.sg/handle/10635/82621
ISSN: 10636692
DOI: 10.1109/TNET.2007.911432
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

138
checked on Mar 6, 2018

WEB OF SCIENCETM
Citations

96
checked on Mar 6, 2018

Page view(s)

25
checked on Feb 25, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.