Distributed Planarization and Local Routing Strategies in Sensor Networks

Abstract

We present an algorithm which computes a planar 2-spanner from an Unit Disk Graph when the node density is sufficient. The communication complexity in terms of number of node's identifier sent by the algorithm is \(6n\), while the computational complexity is \(O(n\Delta)\), with \(\Delta\) the maximum degree of the communication graph. Furthermore, we present a simple and efficient routing algorithm dedicated to the computed graph. Last but not least, using traditional Euclidean coordinates, our algorithm needs the broadcast of as few as \(3n\) node's identifiers. Under the hypothesis of sufficient node density, no broadcast at all is needed, reducing the previous best known complexity of an algorithm to compute a planar spanner of an Unit Disk Graph which was of \(5n\) broadcasts.