Title: Strictly-Localized Construction of Near-Optimal Power Spanners for Wireless Ad-Hoc Networks
Published: August 2007
Authors: Iyad A. Kanj, Ljubomir Perkovic, Ge Xia
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.
Full Paper: [pdf]