Distributed Construction of Connected Dominating Sets with Minimum Routing Cost in Wireless Networks
Authors:
- Ling DingLDLing Ding
- Xiaofeng GaoXGXiaofeng Gao
- Weili WuWWWeili Wu
- Wonjun LeeWLWonjun Lee
- Xu ZhuXZXu Zhu
- Ding-Zhu DuDDDing-Zhu Du
- 1 January 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636927,p. 448-457
Abstract
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 NPhard. We also prove that there does not exist a polynomial-time approximation algorithm for constructing a minimum MOCCDS with performance ratio plnδ, where p is an arbitrary positive number (p <; 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.Keywords
This publication has 24 references indexed in Scilit:
- A simple improved distributed algorithm for minimum CDS in unit disk graphsACM Transactions on Sensor Networks, 2006
- Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor NetworksJournal of Global Optimization, 2006
- Minimum connected dominating sets and maximal independent sets in unit disk graphsTheoretical Computer Science, 2006
- A greedy approximation for minimum connected dominating setsTheoretical Computer Science, 2004
- A polynomial‐time approximation scheme for the minimum‐connected dominating set in ad hoc wireless networksNetworks, 2003
- Routing in ad-hoc networks using minimum connected dominating sets2002
- Approximations for Steiner Trees with Minimum Number of Steiner PointsJournal of Global Optimization, 2000
- Steiner tree problem with minimum number of Steiner points and bounded edge-lengthInformation Processing Letters, 1999
- Approximation Algorithms for Connected Dominating SetsAlgorithmica, 1998
- Unit disk graphsDiscrete Mathematics, 1990