CDS-Based Virtual Backbone Construction with Guaranteed Routing Cost in Wireless Sensor Networks
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Du, Hongwei (David) | - |
dc.contributor.author | Wu, Weili | - |
dc.contributor.author | Ye, Qiang | - |
dc.contributor.author | Li, Deying | - |
dc.contributor.author | Lee, Wonjun | - |
dc.contributor.author | Xu, Xuepeng | - |
dc.date.accessioned | 2021-09-06T02:50:55Z | - |
dc.date.available | 2021-09-06T02:50:55Z | - |
dc.date.created | 2021-06-14 | - |
dc.date.issued | 2013-04 | - |
dc.identifier.issn | 1045-9219 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/103578 | - |
dc.description.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. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | IEEE COMPUTER SOC | - |
dc.subject | CONNECTED DOMINATING SETS | - |
dc.subject | MINIMUM CDS | - |
dc.subject | APPROXIMATION ALGORITHMS | - |
dc.title | CDS-Based Virtual Backbone Construction with Guaranteed Routing Cost in Wireless Sensor Networks | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Lee, Wonjun | - |
dc.identifier.doi | 10.1109/TPDS.2012.177 | - |
dc.identifier.scopusid | 2-s2.0-84874964051 | - |
dc.identifier.wosid | 000316223500004 | - |
dc.identifier.bibliographicCitation | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, v.24, no.4, pp.652 - 661 | - |
dc.relation.isPartOf | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | - |
dc.citation.title | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | - |
dc.citation.volume | 24 | - |
dc.citation.number | 4 | - |
dc.citation.startPage | 652 | - |
dc.citation.endPage | 661 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Engineering | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Theory & Methods | - |
dc.relation.journalWebOfScienceCategory | Engineering, Electrical & Electronic | - |
dc.subject.keywordPlus | CONNECTED DOMINATING SETS | - |
dc.subject.keywordPlus | MINIMUM CDS | - |
dc.subject.keywordPlus | APPROXIMATION ALGORITHMS | - |
dc.subject.keywordAuthor | Wireless sensor networks | - |
dc.subject.keywordAuthor | virtual backbone | - |
dc.subject.keywordAuthor | connected dominating set | - |
dc.subject.keywordAuthor | routing cost | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.