10.1109/INFCOM.2013.6567022
Benter, Markus
Markus
Benter
Neumann, Florentin
Florentin
Neumann
Frey, Hannes
Hannes
Frey
Reactive Planar Spanner Construction in Wireless Ad Hoc and Sensor Networks
2013
2017-10-17T12:42:29Z
2020-05-07T05:26:29Z
conference
https://ris.uni-paderborn.de/record/496
https://ris.uni-paderborn.de/record/496.json
352571 bytes
application/pdf
Within reactive topology control, a node determines its adjacent edges of a network subgraph without prior knowledge of its neighborhood. The goal is to construct a local view on a topology which provides certain desired properties such as planarity. During algorithm execution, a node, in general, is not allowed to determine all its neighbors of the network graph. There are well-known reactive algorithms for computing planar subgraphs. However, the subgraphs obtained do not have constant Euclidean spanning ratio. This means that routing along these subgraphs may result in potentially long detours. So far, it has been unknown if planar spanners can be constructed reactively. In this work, we show that at least under the unit disk network model, this is indeed possible, by proposing an algorithm for reactive construction of the partial Delaunay triangulation, which recently turned out to be a spanner. Furthermore, we show that our algorithm is message-optimal as a node will only exchange messages with nodes that are also neighbors in the spanner. The algorithmâ€™s presentation is complemented by a rigorous proof of correctness.