Approximations for minimum connected sensor cover

Lidong Wu, Hongwei Du, Weili Wu, Deying Li, Jing Lv, Wonjun Lee

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

22 Citations (Scopus)


Given a requested area, the Minimum Connected Sensor Cover problem is to find a minimum number of sensors such that their communication ranges induce a connected graph and their sensing ranges cover the requested area. Several polynomial-time approximation algorithms have been designed previously in the literature. Their best known performance ratio is O(r lnn) where r is the link radius of the sensor network and n is the number of sensors. In this paper, we will present two polynomial-time approximation algorithms. The first one is a random algorithm, with probability 1-ε, producing an approximation solution with performance ratio O(log3 n log log n), independent from r. The second one is a deterministic approximation with performance ratio O(r), independent from n.

Original languageEnglish
Title of host publication2013 Proceedings IEEE INFOCOM 2013
Number of pages8
Publication statusPublished - 2013
Event32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 - Turin, Italy
Duration: 2013 Apr 142013 Apr 19

Publication series

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


Other32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Approximations for minimum connected sensor cover'. Together they form a unique fingerprint.

Cite this