Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.comnet.2008.03.009
Title: Connected K-target coverage problem in wireless sensor networks with different observation scenarios
Authors: Zhao, Q.
Gurusamy, M. 
Keywords: Algorithms
Connectivity
Coverage
Lifetime maximization
Sensor activity scheduling
Wireless sensor networks
Issue Date: 8-Aug-2008
Source: Zhao, Q., Gurusamy, M. (2008-08-08). Connected K-target coverage problem in wireless sensor networks with different observation scenarios. Computer Networks 52 (11) : 2205-2220. ScholarBank@NUS Repository. https://doi.org/10.1016/j.comnet.2008.03.009
Abstract: In this paper, we consider the problem of scheduling sensor activities to maximize network lifetime while maintaining both discrete K-target coverage and network connectivity. In K-target coverage, it is required that each target should be simultaneously observed by at least K sensors. The data generated by the sensors will be transmitted to the sink node via single or multiple hop communications. As maintaining discrete target coverage cannot guarantee the network connectivity, we consider both target coverage and connectivity issues. Further, by adopting a more realistic energy consumption model, we consider the sensor activity scheduling problem and routing problem jointly. We study the problem with two observation scenarios depending on whether a sensor can distinguish the targets in its sensing area or not. For the first scenario, a more general scenario where each sensor can simultaneously observe multiple targets is considered and we develop a polynomial-time algorithm which can achieve optimal solution based on linear programming and integer theorem. For the second scenario, we show that the problem is NP-complete and develop an approximation algorithm for solving it. As the protocol cost of the optimal solution and the approximation algorithm may be high in practice, we develop a low-cost heuristic algorithm which can be implemented in a distributed fashion for both scenarios. We demonstrate the effectiveness of the heuristic algorithm through extensive simulations. © 2008 Elsevier B.V. All rights reserved.
Source Title: Computer Networks
URI: http://scholarbank.nus.edu.sg/handle/10635/55397
ISSN: 13891286
DOI: 10.1016/j.comnet.2008.03.009
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

14
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

15
checked on Nov 19, 2017

Page view(s)

27
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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