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

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

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 -