@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",

month = dec,

day = "1",

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",

}