Title: Connected dominating set in wireless ad hoc networks
Abstract: A Wireless Ad Hoc Network (WANET) is dynamically formed by a collection of static or mobile hosts communicating with each other over a scarce shared wireless channel, in absence of a fixed infrastructure and a predefined central administration system. Wireless ad hoc networks can be flexibly and quickly deployed for many applications such as automated battlefield, search and rescue, and disaster relief, etc. Due to its characteristics of dynamic topology, multi-hop communication and strict resource limitation, routing in WANET presents a challenging problem and has drawn significant attentions.
Although no physical backbone is present, a virtual backbone formed by nodes in a Connected Dominating Set (CDS) can be superimposed and plays a very important role in routing, broadcasting and connectivity management in wireless ad hoc networks. However, the construction of an Minimum Connected Dominating Set (MCDS) is proven to be NP-hard. Therefore research work has been focused on designing approximation algorithms for the MCDS problem. A number of approximation algorithms are presented in this dissertation.
Firstly, in homogeneous wireless ad hoc networks, where the network topology can be represented by a Unit Disk Graph, a completely localized distributed algorithm called r-CDS is proposed to construct an MCDS, which has a constant performance ratio of 172. Applying certain pruning rules on locally redundant nodes, the size of the CDS can be further reduced.
Secondly, in a special case of heterogeneous wireless ad hoc networks where the network topology can be represented by a Disk Graph with Bidirectional links (DGB), two efficient approximation algorithms are presented to obtain an MCDS. The performance ratio of these algorithms is constant if the ratio of the maximum transmission range over the minimum transmission range in the network is bounded. Distributed versions of these algorithms are also implemented. The size relationship between a maximal independent set and a CDS is shown, as well as a bound of the maximum number of independent neighbors of a node in disk graphs.
Lastly, a polynomial time approximation scheme (PTAS) is presented to find a minimum d-hop connected dominating set (d-CDS) in a class of growth-bounded graphs, including unit disk graphs, unit balls, etc., which can represent a majority of existing wireless networks. Based on predefined network parameters, the growth-bounded graph can be partitioned into clusters. d-CDS is constructed for each cluster and the union of each d-CDS forms a d-CDS for the graph, with some additional nodes connecting them. Performance and complexity analysis of the PTAS are provided.
Publication Year: 2009
Publication Date: 2009-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot