Detailed Information

Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

CDS-Based Virtual Backbone Construction with Guaranteed Routing Cost in Wireless Sensor Networks

Authors
Du, Hongwei (David)Wu, WeiliYe, QiangLi, DeyingLee, WonjunXu, Xuepeng
Issue Date
4월-2013
Publisher
IEEE COMPUTER SOC
Keywords
Wireless sensor networks; virtual backbone; connected dominating set; routing cost
Citation
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, v.24, no.4, pp.652 - 661
Indexed
SCIE
SCOPUS
Journal Title
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Volume
24
Number
4
Start Page
652
End Page
661
URI
https://scholar.korea.ac.kr/handle/2021.sw.korea/103578
DOI
10.1109/TPDS.2012.177
ISSN
1045-9219
Abstract
Inspired by the backbone concept in wired networks, virtual backbone is expected to bring substantial benefits to routing in wireless sensor networks (WSNs). Virtual backbone construction based on Connected Dominating Set (CDS) is a competitive approach among the existing methods used to establish virtual backbone in WSNs. Traditionally, CDS size was the only factor considered in the CDS-based approach. The motivation was that smaller CDS leads to simplified network maintenance. However, routing cost in terms of routing path length is also an important factor for virtual backbone construction. In our research, both of these two factors are taken into account. Specifically, we attempt to devise a polynomial-time constant-approximation algorithm that leads to a CDS with bounded CDS size and guaranteed routing cost. We prove that, under general graph model, there is no polynomial-time constant-approximation algorithm unless P = NP. Under Unit Disk Graph (UDG) model, we propose an innovative polynomial-time constant-approximation algorithm, GOC-MCDS-C, that produces a CDS D whose size vertical bar D vertical bar is within a constant factor from that of the minimum CDS. In addition, for each node pair u and v, there exists a routing path with all intermediate nodes in D and path length at most 7.d(u, v), where d(u, v) is the length of the shortest path between u and v. Our theoretical analysis and simulation results show that the distributed version of the proposed algorithm, GOC-MCDS-D, outperforms the existing approaches.
Files in This Item
There are no files associated with this item.
Appears in
Collections
School of Cyber Security > Department of Information Security > 1. Journal Articles

qrcode

Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher Lee, Won jun photo

Lee, Won jun
정보보호학과
Read more

Altmetrics

Total Views & Downloads

BROWSE