Energy-efficient broadcasting in wireless ad hoc networks: performance benchmarking and distributed algorithms based on network connectivity characterization

ABSTRACT

Broadcasting in wireless ad hoc networks can use a virtual backbone formed by a connected dominating set (CDS). If nodes use constant and identical transmission power, energy-efficient broadcasting amounts to minimizing the size of the backbone (i.e., CDS cardinality). This is referred to as the minimum connected dominating set (MCDS) problem. We present two feasibility conditions, and show that each of the conditions is both sufficient and necessary for characterizing a CDS. The first condition yields an integer programming model, which allows us to compute an MCDS for networks of moderate size (up to 80 nodes in our experiments). The second condition leads to a class of distributed algorithms. We compare numerically the performance of this class of algorithms to that of a centralized algorithm, as well as to MCDS found using the integer programming model. Our performance evaluation suggests that the class of algorithms presented in this paper have a close-optimal performance. In addition, we highlight possible algorithm extensions to cope with timing and mobility issues.

REFERENCES

• 1: K. M. Alzoubi, P.-J. Wan, and O. Frieder. Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks, 4(1):22--29, March 2002.
• 2: J. Blum, M. Ding, A. Thaeler, and X. Cheng. Connected dominating set in sensor networks and MANETS. In D.-Z. Du and P. Pardalos, editors, Handbook of Combinatorial Optimization, pages 329--369. Kluwer Academic Publishers, 2004.
• 3: S. Butenko, X. Cheng, C. Oliveria, and P. M. Padalos. A new heuristic for the minimum connected dominating set problem on ad hoc wireless systems. In S. Butenko, R. Murphey, and P. Pardalos, editors, Recent Developments in Cooperative Control and Optimization, chapter 4, pages 61--73. Kluwer Academic Publishers, 2004.
• 4: M. Cardei, X. Cheng, X. Cheng, and D.-Z. Du. Connected domination in ad hoc wireless networks. In Proceedings of the Sixth International Conference on Computer Science and Informatics (CS&I), 2002.
• 5: X. Cheng, X. Huang, D. Li, W. Wu, and D.-Z. Du. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks, 42(4):202--208, 2003.
• 6: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 7: Fei Dai , Jie Wu, An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.908-920, October 2004 [doi>10.1109/TPDS.2004.48]
• 8: B. Das and V. Bharghavan. Routing in ad-hoc networks using minimum connected dominating sets. In Proceedings of IEEE ICC '97, pages 376--380, 1997.
• 9: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 10: Devdatt Dubhashi , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan , Arvind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374--387, 1998.
• 13: ILOG CPLEX 7.0, User's Manual. ILOG, 2000.
• 14: X. Li and I. Stojmenovic. Broadcasting and topology control in wireless ad hoc networks. In A. Boukerche and I. Chlamtac, editors, Handbook of Algorithms for Mobile and Wireless Networking and Computing. CRC Press, to appear.
• 15: M. Min, X. Huang, S. C.-H. Huang, and W. Wu. Improving construction for connected dominating set with Steiner tree in wireless sensor networks. Journal of Global Optimization, to appear.
• 16: Lu Ruan , Hongwei Du , Xiaohua Jia , Weili Wu , Yingshu Li , Ker-I Ko, A greedy approximation for minimum connected dominating sets, Theoretical Computer Science, v.329 n.1-3, p.325-330, 13 December 2004 [doi>10.1016/j.tcs.2004.08.013]
• 17: P. Sinha, R. Sivakumar, and V. Bharghavan. Enhancing ad hoc routing with dynamic virtual infrastructures. In Proceedings of IEEE INFOCOM '01, pages 1763--1772, 2001.
• 18: Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024]
• 19: P.-J. Wan, K. Alzoubi, and O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. In Proceedings of IEEE INFOCOM '02, pages 1597--1604, 2002.
• 20: J. E. Wieselthier, G. D. Nguyen, and A. Ephremides. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In Proceedings of IEEE INFOCOM '00, pages 585--594, 2000.
• 21: Jie Wu , Fei Dai, A Generic Distributed Broadcast Scheme in Ad Hoc Wireless Networks, IEEE Transactions on Computers, v.53 n.10, p.1343-1354, October 2004 [doi>10.1109/TC.2004.69]
• 22: J. Wu, F. Dai, M. Gao, and I. Stojmenovic. On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. Journal of Communications and Networks, 4(1):59--70, March 2002.
• 23: Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.m Miscellaneous

General Terms:
Algorithms, Performance

Keywords:
ad hoc networks, broadcasting, distributed algorithm, integer programming, virtual backbone