Routing-efficient CDS construction in Disk-Containment Graphs
- Authors
- Lu, Zaixin; Wu, Lidong; Pardalos, Panos M.; Maslov, Eugene; Lee, Wonjun; Du, Ding-Zhu
- Issue Date
- 2월-2014
- Publisher
- SPRINGER HEIDELBERG
- Keywords
- Wireless network; CDS; Routing efficiency; Approximation algorithm
- Citation
- OPTIMIZATION LETTERS, v.8, no.2, pp.425 - 434
- Indexed
- SCIE
SCOPUS
- Journal Title
- OPTIMIZATION LETTERS
- Volume
- 8
- Number
- 2
- Start Page
- 425
- End Page
- 434
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/99333
- DOI
- 10.1007/s11590-012-0590-5
- ISSN
- 1862-4472
- Abstract
- In wireless networks, Connected Dominating Sets (CDSs) are widely used as virtual backbones for communications. On one hand, reducing the backbone size will reduce the maintenance overhead. So how to minimize the CDS size is a critical issue. On the other hand, when evaluating the performance of a wireless network, the hop distance between two communication nodes, which reflect the energy consumption and response delay, is of great importance. Hence how to minimize the routing cost is also a key problem for constructing the network virtual backbone. In this paper, we study the problem of constructing applicable CDS in wireless networks in terms of size and routing cost. We formulate a wireless network as a Disk-Containment Graph (DCG), which is a generalization of the Unit-Disk Graph (UDG), and we develop an efficient algorithm to construct CDS in such kind of graphs. The algorithm contains two parts and is flexible to balance the performance between the two metrics. We also analyze the algorithm theoretically. It is shown that our algorithm has provable performance in minimizing the CDS size and reducing the communication distance for routing.
- 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
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.