K-connected target coverage problem in wireless sensor networks

Deying Li, Jiannong Cao, Ming Liu, Yuan Zheng

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

13 Citations (Scopus)


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 languageEnglish
Title of host publicationCombinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings
Number of pages12
Publication statusPublished - 1 Dec 2007
Event1st International Conference on Combinatorial Optimization and Applications, COCOA 2007 - Xi'an, China
Duration: 14 Aug 200716 Aug 2007

Publication series

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


Conference1st International Conference on Combinatorial Optimization and Applications, COCOA 2007


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'K-connected target coverage problem in wireless sensor networks'. Together they form a unique fingerprint.

Cite this