|
Abstract: |
We present a strictly-localized distributed algorithm
that, given a wireless ad-hoc network modeled as a unit disk graph U
in the plane, constructs a planar power spanner of U whose degree
is bounded by k and whose stretch factor is bounded by 1 + (2 sin
(π / k)) p,
where k ≥ 10 is an
integer parameter and p in [2, 5] is the power exponent constant.
For the same degree bound k, the stretch factor of our algorithm
significantly improves the previous best bounds by Song et al. and Kanj
and Perković. We show that this
bound is near-optimal by proving that the slightly smaller stretch
factor of 1 + (2 sin (π / (k
+ 1))) p is unattainable for the same degree
bound k. In contrast to previous algorithms by Song et al. and by
Kanj and Perković, the presented
algorithm is strictly localized: the construction of the power spanner
depends solely on the local structure and does not require information
propagation. As a consequence, the algorithm is highly scalable and
robust. Moreover, on a graph with n points and m edges the
algorithm exchanges no more than O(m) messages and has a local
processing time of O(Δ lg
Δ) = O(n lg n) at a
node of degree Δ. Finally, while the
algorithm is efficient and easy to implement in practice, it relies on
deep insights on the geometry of unit disk graphs and novel techniques
that are of independent interest. |