Geometric spanners for wireless ad hoc networks

Abstract

We propose a new geometric spanner, for wireless ad hoc networks, which can be constructed efficiently in a distributed manner. It combines the connected dominating set and the local Delaunay graph to form the backbone of a wireless network. This new spanner has the following attractive properties: (1) the backbone is a planar graph; (2) the node degree of the backbone is bounded from above by a positive constant; (3) it is a spanner both for hops and length; moreover, we show that, given any two nodes u and /spl upsi/, there is a path connecting them in the backbone such that its length is no more than 6 times that of the shortest path and the number of links is no more than 3 times that of the shortest path; (4) it can be constructed locally and is easy to maintain when the nodes move around; and (5) we show that the computation cost of each node is at most O(d log d), where d is its l-hop neighbors in the original unit disk graph, and the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance.