Constant approximation for virtual backbone construction with Guaranteed Routing Cost in wireless sensor networks

Hongwei Du; Qiang Ye; Weili Wu; Wonjun Lee; Deying Li; Dingzhu Du; Stephen Howard

doi:10.1109/INFCOM.2011.5934967

Constant approximation for virtual backbone construction with Guaranteed Routing Cost in wireless sensor networks

Hongwei Du, Qiang Ye, Weili Wu, Wonjun Lee, Deying Li, Dingzhu Du, Stephen Howard

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

45 Citations (Scopus)

Abstract

In wireless sensor networks, virtual backbone construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Assume that a sensor networks is defined as a connected unit disk graph (UDG). The problem is to find a minimum connected dominating set of given UDG with minimum routing cost for each node pair. We present a constant approximation scheme which produces a connected dominating set D, whose size D is within a factor α from that of the minimum connected dominating set and each node pair exists a routing path with all intermediate nodes in D and with length at most 5 · d(u,v), where d(u,v) is the length of shortest path of this node pair. A distributed algorithm is also provided with analogical performance. Extensive simulation shows that our distributed algorithm achieves significantly than the latest solution in research direction.

Original language	English
Title of host publication	2011 Proceedings IEEE INFOCOM
Pages	1737-1744
Number of pages	8
DOIs	https://doi.org/10.1109/INFCOM.2011.5934967
Publication status	Published - 2011
Event	IEEE INFOCOM 2011 - Shanghai, China Duration: 2011 Apr 10 → 2011 Apr 15

Publication series

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

Other

Other	IEEE INFOCOM 2011
Country/Territory	China
City	Shanghai
Period	11/4/10 → 11/4/15

ASJC Scopus subject areas

General Computer Science
Electrical and Electronic Engineering

Access to Document

10.1109/INFCOM.2011.5934967

Cite this

@inproceedings{7c660bbbc4fb4e45a2633f8518f38612,

title = "Constant approximation for virtual backbone construction with Guaranteed Routing Cost in wireless sensor networks",

abstract = "In wireless sensor networks, virtual backbone construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Assume that a sensor networks is defined as a connected unit disk graph (UDG). The problem is to find a minimum connected dominating set of given UDG with minimum routing cost for each node pair. We present a constant approximation scheme which produces a connected dominating set D, whose size D is within a factor α from that of the minimum connected dominating set and each node pair exists a routing path with all intermediate nodes in D and with length at most 5 · d(u,v), where d(u,v) is the length of shortest path of this node pair. A distributed algorithm is also provided with analogical performance. Extensive simulation shows that our distributed algorithm achieves significantly than the latest solution in research direction.",

author = "Hongwei Du and Qiang Ye and Weili Wu and Wonjun Lee and Deying Li and Dingzhu Du and Stephen Howard",

year = "2011",

doi = "10.1109/INFCOM.2011.5934967",

language = "English",

isbn = "9781424499212",

series = "Proceedings - IEEE INFOCOM",

pages = "1737--1744",

booktitle = "2011 Proceedings IEEE INFOCOM",

}

TY - GEN

T1 - Constant approximation for virtual backbone construction with Guaranteed Routing Cost in wireless sensor networks

AU - Du, Hongwei

AU - Ye, Qiang

AU - Wu, Weili

AU - Lee, Wonjun

AU - Li, Deying

AU - Du, Dingzhu

AU - Howard, Stephen

PY - 2011

Y1 - 2011

N2 - In wireless sensor networks, virtual backbone construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Assume that a sensor networks is defined as a connected unit disk graph (UDG). The problem is to find a minimum connected dominating set of given UDG with minimum routing cost for each node pair. We present a constant approximation scheme which produces a connected dominating set D, whose size D is within a factor α from that of the minimum connected dominating set and each node pair exists a routing path with all intermediate nodes in D and with length at most 5 · d(u,v), where d(u,v) is the length of shortest path of this node pair. A distributed algorithm is also provided with analogical performance. Extensive simulation shows that our distributed algorithm achieves significantly than the latest solution in research direction.

AB - In wireless sensor networks, virtual backbone construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Assume that a sensor networks is defined as a connected unit disk graph (UDG). The problem is to find a minimum connected dominating set of given UDG with minimum routing cost for each node pair. We present a constant approximation scheme which produces a connected dominating set D, whose size D is within a factor α from that of the minimum connected dominating set and each node pair exists a routing path with all intermediate nodes in D and with length at most 5 · d(u,v), where d(u,v) is the length of shortest path of this node pair. A distributed algorithm is also provided with analogical performance. Extensive simulation shows that our distributed algorithm achieves significantly than the latest solution in research direction.

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

U2 - 10.1109/INFCOM.2011.5934967

DO - 10.1109/INFCOM.2011.5934967

M3 - Conference contribution

AN - SCOPUS:79960877514

SN - 9781424499212

T3 - Proceedings - IEEE INFOCOM

SP - 1737

EP - 1744

BT - 2011 Proceedings IEEE INFOCOM

T2 - IEEE INFOCOM 2011

Y2 - 10 April 2011 through 15 April 2011

ER -

Constant approximation for virtual backbone construction with Guaranteed Routing Cost in wireless sensor networks

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this