Narrow Results

In this paper, we review some new distributed algorithms that construct sparse subgraphs with bounded degree of the unit disk graph efficiently for wireless ad hoc networks. They maintain a linear number of links while still preserving power-efficient routes for any pair of nodes. It was open whether the Yao plus reverse Yao graph and the symmetric Yao graph are spanners. We show that the Yao plus reverse Yao graph has a bounded power stretch factor 2 in civilized unit disk graph. In addition, we review a recent example by M. Grünewald et al. [6] to show that the symmetric Yao graph does not have a constant bounded stretch factor. Finally, we conduct simulations to study the practical performances of these structures. All structures have small power stretch factors for randomly generated unit disk graphs in our experiments.

Given a set V of n points in a two-dimensional plane, we give an O(nlogn)-time centralized algorithm that constructs a planar t-spanner for V, for such that the degree of each node is bounded from above by , where 0<α<π/2 is an adjustable parameter. Here C_del is the spanning ratio of the Delaunay triangulation, which is at most . We also show, by applying the greedy method in Ref. [14], how to construct a low weighted bounded degree planar spanner with spanning ratio ρ(α)²(1+∊) and the same degree bound, where ∊ is any positive real constant. Here, a structure is called low weighted if its total edge length is proportional to the total edge length of the Euclidean minimum spanning tree of V. Moreover, we show that our method can be extended to construct a planar bounded degree spanner for unit disk graphs with the adjustable parameter α satisfying 0<α<π/3. Previously, only centralized method⁶ of constructing bounded degree planar spanner is known, with degree bound 27 and spanning ratio t≃10.02. The distributed implementation of this centralized method takes O(n²) communications in the worst case. Our method can be converted to a localized algorithm where the total number of messages sent by all nodes is at most O(n).