Local construction of planar spanners in unit disk graphs with irregular transmission ranges
We give an algorithm for constructing a connected spanning subgraphs(panner) of a wireless network modelled as a unit disk graph with nodes of irregular transmission ranges, whereby for some parameter 0 < r ≤ 1 the transmission range of a node includes the entire disk around the node of radius at least r and it does not include any node at distance more than one. The construction of a spanner is distributed and local in the sense that nodes use only information at their vicinity, moreover for a given integer k ≥ 2 each node needs only consider all the nodes at distance at most k hops from it. The resulting spanner has maximum degree at most 3 + 6/πr + r+1/r 2, when 0 < r < 1 (and at most five, when r = 1). Furthermore it is shown that the spanner is planar provided that the distance between any two nodes is at least √1 - r2. If the spanner is planar then for k ≥ 2 the sum of the Euclidean lengths of the edges of the spanner is at most kr+1/kr-1 times the sum of the Euclidean lengths of the edges of a minimum weight Euclidean spanning tree.
|Organisation||School of Computer Science|
Chávez, E. (Edgar), Dobrev, S. (Stefan), Kranakis, E, Opatrny, J. (Jaroslav), Stacho, L. (Ladislav), & Urrutia, J. (Jorge). (2006). Local construction of planar spanners in unit disk graphs with irregular transmission ranges.