Connected dominating set and its induced position-less sparse spanner for mobile ad hoc networks

A set S is a dominating set (DS) if each node in the graph is either in S or a neighbor to at least one of the nodes in S. A connected dominating set (CDS) is a DS that induces a connected subgraph. A t-spanner of a graph G = (V,E) is a spanning subgraph G´ = (V,E´), such that the shortest hop path between any two nodes in G´, is at most t times their shortest path in G. A sparse spanner (spanner with linear edges) is of fundamental importance to distributed networking operations. In this paper, we present a new algorithm for constructing and maintaining a CDS-based sparse spanner for mobile ad hoc networks without using geographic positions. This CDS has a constant approximation factor. Consequently, the number of nodes responsible for routing is also within a constant factor of the minimum. Our distributed algorithm runs in linear time and uses linear messages. Furthermore, the spanner has a constant topological and geometric dilation.