Virtual backbones in wireless ad hoc networks

Wireless ad hoc networks can be flexibly and quickly deployed for many applications such as automated battlefields, search and rescue, and disaster relief. Unlike wired networks or cellular networks, no physical backbone infrastructure is installed in wireless ad hoc networks. A communication session is achieved either through a single-hop radio transmission if the communication parties are close enough, or through relaying by intermediate nodes otherwise. The topology of such a wireless ad hoc network can be modelled as a unit-disk graph, a geometric graph in which there is an edge between two nodes if and only if their distance is at most one.; Although wireless ad hoc networks have no physical backbone infrastructure, a virtual backbone can be formed by nodes in a connected dominating set (CDS) of the corresponding unit-disk graph. A CDS is a connected subgraph, such that each node in the graph is either in the connected subgraph or adjacent to at least one of the nodes in the connected subgraph. However, it is NP-hard to find a minimum connected dominating set (MCDS). Several distributed approximation algorithms for MCDS have been proposed in the literature. All of these algorithms suffer from a logarithmic or linear approximation factor. The time complexity and message complexity of most of these algorithms are very poor. Some of these algorithms require two-hop neighborhood knowledge and message length of Ω (Δ log n) where Δ is the maximal nodal degree, and the length unit is the number of bits representing a node's ID. Since the networking nodes in wireless ad hoc networks are very limited in resources, a virtual backbone should not only be “thinner”, but should also be constructed with low communication and computation costs. In addition, the communication and computation costs should be scalable as the wireless ad hoc networks are typically deployed with large network size.; In my thesis, I first provide an analysis of the maximal independent set (MIS) properties in the unit-disk graph. Several centralized and distributed constant approximation algorithms for constructing a virtual backbone are proposed. These algorithms are based on the MIS and its properties. An Ω( n log n) lower bound on the message complexity of any distributed algorithm for nontrivial CDS is established. The first distributed algorithms with constant performance ratio, O(n log n) messages, and O(n) time complexity are proposed. These algorithms only require single-hop neighborhood knowledge, and a message length of O(log n) bits. A constant approximation algorithm with linear time and linear message complexity is introduced. This algorithm has some features that make it practical for mobility environment. More surprisingly, this algorithm is implemented to construct the first sparse 3-spanner that does not require any knowledge about the geographic position of the nodes. It is sufficient for each node to know its neighbors, without knowing their geographic location.