TY - JOUR
T1 - Routing-efficient CDS construction in Disk-Containment Graphs
AU - Lu, Zaixin
AU - Wu, Lidong
AU - Pardalos, Panos M.
AU - Maslov, Eugene
AU - Lee, Wonjun
AU - Du, Ding Zhu
N1 - Funding Information:
Acknowledgments This research work is supported in part by National Science Foundation of USA under grants CNS 0831579 and CCF 0728851. It is also jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), MEST, Korea under Basic Science Research Program (2011-0012216), and MKE, Korea under ITRC NIPA-2011-(C1090-1121-0008). The research of Panos M. Pardalos and Eugene Maslov is partially supported by LATNA Laboratory, NRU HSE, RF government grant, ag. 11.G34.31.0057.
PY - 2014/2
Y1 - 2014/2
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - CDS
KW - Routing efficiency
KW - Wireless network
UR - http://www.scopus.com/inward/record.url?scp=84893753844&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893753844&partnerID=8YFLogxK
U2 - 10.1007/s11590-012-0590-5
DO - 10.1007/s11590-012-0590-5
M3 - Article
AN - SCOPUS:84893753844
SN - 1862-4472
VL - 8
SP - 425
EP - 434
JO - Optimization Letters
JF - Optimization Letters
IS - 2
ER -
