Approximations for minimum connected sensor cover

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

doi:10.1109/INFCOM.2013.6566910

Approximations for minimum connected sensor cover

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

School of Cybersecurity

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

22 Citations (Scopus)

Abstract

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(log³ n log log n), independent from r. The second one is a deterministic approximation with performance ratio O(r), independent from n.

Original language	English
Title of host publication	2013 Proceedings IEEE INFOCOM 2013
Pages	1187-1194
Number of pages	8
DOIs	https://doi.org/10.1109/INFCOM.2013.6566910
Publication status	Published - 2013
Event	32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 - Turin, Italy Duration: 2013 Apr 14 → 2013 Apr 19

Publication series

Name	Proceedings - IEEE INFOCOM
ISSN (Print)	0743-166X

Other

Other	32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013
Country/Territory	Italy
City	Turin
Period	13/4/14 → 13/4/19

ASJC Scopus subject areas

Computer Science(all)
Electrical and Electronic Engineering

Access to Document

10.1109/INFCOM.2013.6566910

Cite this

@inproceedings{ee5f58614df04c90b83d3ab6976becd3,

title = "Approximations for minimum connected sensor cover",

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

author = "Lidong Wu and Hongwei Du and Weili Wu and Deying Li and Jing Lv and Wonjun Lee",

year = "2013",

doi = "10.1109/INFCOM.2013.6566910",

language = "English",

isbn = "9781467359467",

series = "Proceedings - IEEE INFOCOM",

pages = "1187--1194",

booktitle = "2013 Proceedings IEEE INFOCOM 2013",

note = "32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 ; Conference date: 14-04-2013 Through 19-04-2013",

}

TY - GEN

T1 - Approximations for minimum connected sensor cover

AU - Wu, Lidong

AU - Du, Hongwei

AU - Wu, Weili

AU - Li, Deying

AU - Lv, Jing

AU - Lee, Wonjun

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84883085328&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883085328&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2013.6566910

DO - 10.1109/INFCOM.2013.6566910

M3 - Conference contribution

AN - SCOPUS:84883085328

SN - 9781467359467

T3 - Proceedings - IEEE INFOCOM

SP - 1187

EP - 1194

BT - 2013 Proceedings IEEE INFOCOM 2013

T2 - 32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013

Y2 - 14 April 2013 through 19 April 2013

ER -

Approximations for minimum connected sensor cover

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this