---
_id: '496'
abstract:
- lang: eng
text: 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.
author:
- first_name: Markus
full_name: Benter, Markus
last_name: Benter
- first_name: Florentin
full_name: Neumann, Florentin
last_name: Neumann
- first_name: Hannes
full_name: Frey, Hannes
last_name: Frey
citation:
ama: 'Benter M, Neumann F, Frey H. Reactive Planar Spanner Construction in Wireless
Ad Hoc and Sensor Networks. In: Proceedings of the 32nd IEEE International
Conference on Computer Communications (INFOCOM). ; 2013:2193-2201. doi:10.1109/INFCOM.2013.6567022'
apa: Benter, M., Neumann, F., & Frey, H. (2013). Reactive Planar Spanner Construction
in Wireless Ad Hoc and Sensor Networks. In Proceedings of the 32nd IEEE International
Conference on Computer Communications (INFOCOM) (pp. 2193–2201). https://doi.org/10.1109/INFCOM.2013.6567022
bibtex: '@inproceedings{Benter_Neumann_Frey_2013, title={Reactive Planar Spanner
Construction in Wireless Ad Hoc and Sensor Networks}, DOI={10.1109/INFCOM.2013.6567022},
booktitle={Proceedings of the 32nd IEEE International Conference on Computer Communications
(INFOCOM)}, author={Benter, Markus and Neumann, Florentin and Frey, Hannes}, year={2013},
pages={2193–2201} }'
chicago: Benter, Markus, Florentin Neumann, and Hannes Frey. “Reactive Planar Spanner
Construction in Wireless Ad Hoc and Sensor Networks.” In Proceedings of the
32nd IEEE International Conference on Computer Communications (INFOCOM), 2193–2201,
2013. https://doi.org/10.1109/INFCOM.2013.6567022.
ieee: M. Benter, F. Neumann, and H. Frey, “Reactive Planar Spanner Construction
in Wireless Ad Hoc and Sensor Networks,” in Proceedings of the 32nd IEEE International
Conference on Computer Communications (INFOCOM), 2013, pp. 2193–2201.
mla: Benter, Markus, et al. “Reactive Planar Spanner Construction in Wireless Ad
Hoc and Sensor Networks.” Proceedings of the 32nd IEEE International Conference
on Computer Communications (INFOCOM), 2013, pp. 2193–201, doi:10.1109/INFCOM.2013.6567022.
short: 'M. Benter, F. Neumann, H. Frey, in: Proceedings of the 32nd IEEE International
Conference on Computer Communications (INFOCOM), 2013, pp. 2193–2201.'
date_created: 2017-10-17T12:42:29Z
date_updated: 2022-01-06T07:01:31Z
ddc:
- '040'
department:
- _id: '75'
doi: 10.1109/INFCOM.2013.6567022
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T13:41:34Z
date_updated: 2018-03-15T13:41:34Z
file_id: '1312'
file_name: 496-reactivePDT-copyright.pdf
file_size: 352571
relation: main_file
success: 1
file_date_updated: 2018-03-15T13:41:34Z
has_accepted_license: '1'
page: 2193-2201
project:
- _id: '1'
name: SFB 901
- _id: '6'
name: SFB 901 - Subprojekt A2
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 32nd IEEE International Conference on Computer Communications
(INFOCOM)
status: public
title: Reactive Planar Spanner Construction in Wireless Ad Hoc and Sensor Networks
type: conference
user_id: '15504'
year: '2013'
...