TY - GEN
T1 - K-connected target coverage problem in wireless sensor networks
AU - Li, Deying
AU - Cao, Jiannong
AU - Liu, Ming
AU - Zheng, Yuan
PY - 2007/12/1
Y1 - 2007/12/1
N2 - An important issue in deploying a WSN is to provide target coverage with high energy efficiency and fault-tolerance. Sensor nodes in a wireless sensor network are resource-constrained, especially in energy supply, and prone to failure. In this paper, we study the problem of constructing energy efficient and fault-tolerant target coverage. More specifically, we propose solutions to forming k-connected coverage of targets with the minimal number of active nodes. We first address the k-connected augmentation problem, and then show that the k-connected target coverage problem is NP-hard. We propose two heuristic algorithms to solve the problem. We have carried out extensive simulations to study the performance of the proposed algorithms. The evaluation results have demonstrated their desirable efficiency.
AB - An important issue in deploying a WSN is to provide target coverage with high energy efficiency and fault-tolerance. Sensor nodes in a wireless sensor network are resource-constrained, especially in energy supply, and prone to failure. In this paper, we study the problem of constructing energy efficient and fault-tolerant target coverage. More specifically, we propose solutions to forming k-connected coverage of targets with the minimal number of active nodes. We first address the k-connected augmentation problem, and then show that the k-connected target coverage problem is NP-hard. We propose two heuristic algorithms to solve the problem. We have carried out extensive simulations to study the performance of the proposed algorithms. The evaluation results have demonstrated their desirable efficiency.
KW - Heuristic algorithms
KW - K-connected augmentation
KW - K-connected target coverage
KW - NP-hard problems
KW - Wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=38149067564&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
SN - 9783540735557
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 20
EP - 31
BT - Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings
T2 - 1st International Conference on Combinatorial Optimization and Applications, COCOA 2007
Y2 - 14 August 2007 through 16 August 2007
ER -