TY - GEN
T1 - Distributed construction of connected dominating sets with minimum routing cost in wireless networks
AU - Ding, Ling
AU - Gao, Xiaofeng
AU - Wu, Weili
AU - Lee, Wonjun
AU - Zhu, Xu
AU - Du, Ding Zhu
PY - 2010
Y1 - 2010
N2 - In this paper, we will study a special Connected Dominating Set (CDS) problem - between any two nodes in a network, there exists at least one shortest path, all of whose intermediate nodes should be included in a special CDS, named Minimum rOuting Cost CDS (MOC-CDS). Therefore, routing by MOC-CDS can guarantee that each routing path between any pair of nodes is also the shortest path in the network. Thus, energy consumption and delivery delay can be reduced greatly. CDS has been studied extensively in Unit Disk Graph (UDG) or Disk Graph (DG). However, nodes in networks may have different transmission ranges and some communications may be obstructed by obstacles. Therefore, we model network as a bidirectional general graph in this paper. We prove that constructing a minimum MOC-CDS in general graph is NP-hard. We also prove that there does not exist a polynomial-time approximation algorithm for constructing a minimum MOC-CDS with performance ratio ρlnδ, where ρ is an arbitrary positive number (ρ < 1) and δ is the maximum node degree in network. We propose a distributed heuristic algorithm (called as FlagContest) for constructing MOC-CDS with performance ratio (1 - ln2) + 2lnδ. Through extensive simulations, we show that the results of FlagContest is within the upper bound proved in this paper. Simulations also demonstrate that the average length of routing paths through MOC-CDS reduces greatly compared to regular CDSs.
AB - In this paper, we will study a special Connected Dominating Set (CDS) problem - between any two nodes in a network, there exists at least one shortest path, all of whose intermediate nodes should be included in a special CDS, named Minimum rOuting Cost CDS (MOC-CDS). Therefore, routing by MOC-CDS can guarantee that each routing path between any pair of nodes is also the shortest path in the network. Thus, energy consumption and delivery delay can be reduced greatly. CDS has been studied extensively in Unit Disk Graph (UDG) or Disk Graph (DG). However, nodes in networks may have different transmission ranges and some communications may be obstructed by obstacles. Therefore, we model network as a bidirectional general graph in this paper. We prove that constructing a minimum MOC-CDS in general graph is NP-hard. We also prove that there does not exist a polynomial-time approximation algorithm for constructing a minimum MOC-CDS with performance ratio ρlnδ, where ρ is an arbitrary positive number (ρ < 1) and δ is the maximum node degree in network. We propose a distributed heuristic algorithm (called as FlagContest) for constructing MOC-CDS with performance ratio (1 - ln2) + 2lnδ. Through extensive simulations, we show that the results of FlagContest is within the upper bound proved in this paper. Simulations also demonstrate that the average length of routing paths through MOC-CDS reduces greatly compared to regular CDSs.
KW - Connected dominating set
KW - General graph
KW - NP-hard
KW - Obstacle
KW - Shortest path
KW - Virtual backbones
KW - Wireless network
UR - http://www.scopus.com/inward/record.url?scp=77955898231&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2010.17
DO - 10.1109/ICDCS.2010.17
M3 - Conference contribution
AN - SCOPUS:77955898231
SN - 9780769540597
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 448
EP - 457
BT - ICDCS 2010 - 2010 International Conference on Distributed Computing Systems
T2 - 30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010
Y2 - 21 June 2010 through 25 June 2010
ER -
