Localized Spanners for Ad Hoc Wireless Networks
Mirela Damian and Sriram V. Pemmaraju
We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G = (V,E) and any ε > 0, a (1+ε)-spanner for G of maximum degree O(1) and total weight O(ω(MST)), where ω(MST) denotes the weight of a minimum spanning tree for V. We further show that similar localized techniques can be used to construct, for a given unit disk graph G = (V,E), a planarCdel (1+ε)(1+π/2 )-spanner for G of maximum degree O(1) and total weight O(ω(MST)). Here Cdel denotes the stretch factor of the unit Delaunay triangulation for V. Both constructions can be completed in O(1) rounds of communication, and require each node to know its own coordinates.
Keywords: Wireless ad-hoc networks, unit disk graphs, topology control, spanners, localized algorithms.