@inproceedings{286fcc17628e4d2ea9a316a5d7ee1792,
title = "Connected Domination in Multihop Ad Hoc Wireless Networks",
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.",
keywords = "Connected dominating set, Multihop ad hoc wireless network, Virtual backbone routing",
author = "Mihaela Cardei and Xiaoyan Cheng and Xiuzhen Cheng and Du, {Ding Zhu}",
year = "2002",
language = "English (US)",
isbn = "0970789017",
series = "Proceedings of the Joint Conference on Information Sciences",
pages = "251--255",
editor = "J.H. Caulfield and S.H. Chen and H.D. Cheng and R. Duro and J.H. Caufield and S.H. Chen and H.D. Cheng and R. Duro and V. Honavar",
booktitle = "Proceedings of the 6th Joint Conference on Information Sciences, JCIS 2002",
note = "Proceedings of the 6th Joint Conference on Information Sciences, JCIS 2002 ; Conference date: 08-03-2002 Through 13-03-2002",
}