Connected Domination in Multihop Ad Hoc Wireless Networks

Mihaela Cardei, Xiaoyan Cheng, Xiuzhen Cheng, Ding Zhu Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution

60 Scopus citations

Abstract

The idea of virtual backbone routing for ad hoc wireless networks is to operate routing protocols over a virtual backbone. One purpose of virtual backbone routing is to alleviate the serious broadcast storm problem suffered by many exiting on-demand routing protocols for route detection. Thus constructing a virtual backbone is very important. In our study, the virtual backbone is approximated by a minimum connected dominating set (MCDS) in a unit-disk graph. This is a NP-hard problem. We propose a distributed approximation algorithm with performance ratio at most 8. This algorithm has time complexity O(n) and message complexity O(n · Δ), where n is the number of hosts and Δ is the maximum degree. To our knowledge, this is the best (time and message efficient) distributed algorithm known so far. We first find a maximal independent set. Then we use a Steinter tree to connect all vertices in the set. The performance of our algorithm is witnessed by both simulation results and theoretical analysis.

Original languageEnglish (US)
Title of host publicationProceedings of the 6th Joint Conference on Information Sciences, JCIS 2002
EditorsJ.H. Caulfield, S.H. Chen, H.D. Cheng, R. Duro, J.H. Caufield, S.H. Chen, H.D. Cheng, R. Duro, V. Honavar
Pages251-255
Number of pages5
StatePublished - Dec 1 2002
EventProceedings of the 6th Joint Conference on Information Sciences, JCIS 2002 - Research Triange Park, NC, United States
Duration: Mar 8 2002Mar 13 2002

Publication series

NameProceedings of the Joint Conference on Information Sciences
Volume6

Other

OtherProceedings of the 6th Joint Conference on Information Sciences, JCIS 2002
CountryUnited States
CityResearch Triange Park, NC
Period3/8/023/13/02

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Connected dominating set
  • Multihop ad hoc wireless network
  • Virtual backbone routing

Fingerprint Dive into the research topics of 'Connected Domination in Multihop Ad Hoc Wireless Networks'. Together they form a unique fingerprint.

Cite this