K-connected target coverage problem in wireless sensor networks

Deying Li; Jiannong Cao; Ming Liu; Yuan Zheng

K-connected target coverage problem in wireless sensor networks

Deying Li, Jiannong Cao, Ming Liu, Yuan Zheng

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

13 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings
Pages	20-31
Number of pages	12
Publication status	Published - 1 Dec 2007
Event	1st International Conference on Combinatorial Optimization and Applications, COCOA 2007 - Xi'an, China Duration: 14 Aug 2007 → 16 Aug 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4616 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Conference on Combinatorial Optimization and Applications, COCOA 2007
Country	China
City	Xi'an
Period	14/08/07 → 16/08/07

Keywords

Heuristic algorithms
K-connected augmentation
K-connected target coverage
NP-hard problems
Wireless sensor networks

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Cite this

Li, D., Cao, J., Liu, M., & Zheng, Y. (2007). K-connected target coverage problem in wireless sensor networks. In Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings (pp. 20-31). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4616 LNCS).

Li, Deying ; Cao, Jiannong ; Liu, Ming ; Zheng, Yuan. / K-connected target coverage problem in wireless sensor networks. Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings. 2007. pp. 20-31 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{110ea16cf139467c834d0cc2aa90d3f1,

title = "K-connected target coverage problem in wireless sensor networks",

abstract = "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.",

keywords = "Heuristic algorithms, K-connected augmentation, K-connected target coverage, NP-hard problems, Wireless sensor networks",

author = "Deying Li and Jiannong Cao and Ming Liu and Yuan Zheng",

year = "2007",

month = dec,

day = "1",

language = "English",

isbn = "9783540735557",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "20--31",

booktitle = "Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings",

note = "1st International Conference on Combinatorial Optimization and Applications, COCOA 2007 ; Conference date: 14-08-2007 Through 16-08-2007",

}

Li, D, Cao, J, Liu, M & Zheng, Y 2007, K-connected target coverage problem in wireless sensor networks. in Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4616 LNCS, pp. 20-31, 1st International Conference on Combinatorial Optimization and Applications, COCOA 2007, Xi'an, China, 14/08/07.

K-connected target coverage problem in wireless sensor networks. / Li, Deying; Cao, Jiannong; Liu, Ming; Zheng, Yuan.

Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings. 2007. p. 20-31 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4616 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

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 -