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

^*Corresponding author for this work

University of Prince Edward Island
HITSGS
University of Texas at Dallas
Korea University
Renmin University of China

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

47 Scopus citations

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
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1737-1744
Number of pages	8
ISBN (Print)	9781424499212
DOIs	https://doi.org/10.1109/INFCOM.2011.5934967
State	Published - 2011
Externally published	Yes
Event	IEEE INFOCOM 2011 - Shanghai, China Duration: 10 Apr 2011 → 15 Apr 2011

Publication series

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

Conference

Conference	IEEE INFOCOM 2011
Country/Territory	China
City	Shanghai
Period	10/04/11 → 15/04/11

Access to Document

10.1109/INFCOM.2011.5934967

Cite this

Du, H., Ye, Q., Wu, W., Lee, W., Li, D., Du, D., & Howard, S. (2011). Constant approximation for virtual backbone construction with Guaranteed Routing Cost in wireless sensor networks. In 2011 Proceedings IEEE INFOCOM (pp. 1737-1744). Article 5934967 (Proceedings - IEEE INFOCOM). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/INFCOM.2011.5934967

@inproceedings{1a2d37078ee94b53a456ea421c04dfe8,

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 = "英语",

isbn = "9781424499212",

series = "Proceedings - IEEE INFOCOM",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1737--1744",

booktitle = "2011 Proceedings IEEE INFOCOM",

address = "美国",

note = "IEEE INFOCOM 2011 ; Conference date: 10-04-2011 Through 15-04-2011",

}

Du, H, Ye, Q, Wu, W, Lee, W, Li, D, Du, D & Howard, S 2011, Constant approximation for virtual backbone construction with Guaranteed Routing Cost in wireless sensor networks. in 2011 Proceedings IEEE INFOCOM., 5934967, Proceedings - IEEE INFOCOM, Institute of Electrical and Electronics Engineers Inc., pp. 1737-1744, IEEE INFOCOM 2011, Shanghai, China, 10/04/11. https://doi.org/10.1109/INFCOM.2011.5934967

Constant approximation for virtual backbone construction with Guaranteed Routing Cost in wireless sensor networks. / Du, Hongwei; Ye, Qiang; Wu, Weili et al.
2011 Proceedings IEEE INFOCOM. Institute of Electrical and Electronics Engineers Inc., 2011. p. 1737-1744 5934967 (Proceedings - IEEE INFOCOM).

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

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 - https://www.scopus.com/pages/publications/79960877514

U2 - 10.1109/INFCOM.2011.5934967

DO - 10.1109/INFCOM.2011.5934967

M3 - 会议稿件

AN - SCOPUS:79960877514

SN - 9781424499212

T3 - Proceedings - IEEE INFOCOM

SP - 1737

EP - 1744

BT - 2011 Proceedings IEEE INFOCOM

PB - Institute of Electrical and Electronics Engineers Inc.

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

Conference

Access to Document

Other files and links

Fingerprint

Cite this