Constant-approximation for target coverage problem in wireless sensor networks

Ling Ding, Weili Wu, James Willson, Lidong Wu, Zaixin Lu, Wonjun Lee

Research output: Chapter in Book/Report/Conference proceedingConference contribution

56 Citations (Scopus)


When a large amount of sensors are randomly deployed into a field, how can we make a sleep/activate schedule for sensors to maximize the lifetime of target coverage in the field? This is a well-known problem, called Maximum Lifetime Coverage Problem (MLCP), which has been studied extensively in the literature. It is a long-standing open problem whether MLCP has a polynomial-time constant-approximation. The best-known approximation algorithm has performance ratio 1 + ln n where n is the number of sensors in the network, which was given by Berman et. al [1]. In their work, MLCP is reduced to Minimum Weight Sensor Coverage Problem (MWSCP) which is to find the minimum total weight of sensors to cover a given area or a given set of targets with a given set of weighted sensors. In this paper, we present a polynomial-time (4 + ε)-approximation algorithm for MWSCP and hence we obtain a polynomial-time (4+ξ)-approximation algorithm for MLCP, where ε > 0, ξ > 0.

Original languageEnglish
Title of host publication2012 Proceedings IEEE INFOCOM, INFOCOM 2012
Number of pages9
Publication statusPublished - 2012
EventIEEE Conference on Computer Communications, INFOCOM 2012 - Orlando, FL, United States
Duration: 2012 Mar 252012 Mar 30

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


OtherIEEE Conference on Computer Communications, INFOCOM 2012
Country/TerritoryUnited States
CityOrlando, FL

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


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

Cite this