Foundation of Reactive Local Topology Control

We formalize the concept reactive (aka contention-based or beaconless) topology control and its underlying problem statement. By means of message complexity, we define the classes of O(k)- and Ω(k)-reactive topology control algorithms which allow us to distinguish reactive from conventional local ap...

Full description

Saved in:
Bibliographic Details
Published in:IEEE communications letters 2015-07, Vol.19 (7), p.1213-1216
Main Authors: Neumann, Florentin, Frey, Hannes
Format: Article
Language:English
Subjects:
Ad hoc networks
Ad hoc wireless networks
beaconless
Classification algorithms
Complexity theory
Delays
local algorithms
Network topology
on-demand
reactive
Topology
topology control
Wireless networks
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We formalize the concept reactive (aka contention-based or beaconless) topology control and its underlying problem statement. By means of message complexity, we define the classes of O(k)- and Ω(k)-reactive topology control algorithms which allow us to distinguish reactive from conventional local approaches and to classify the former. Moreover, based on our formalisms we prove two fundamental propositions regarding the reactive computability of standard topology control structures. Thus, our contribution not only establishes a taxonomy for identification of research gaps, but constitutes a theoretical foundation for profound investigation of this algorithm classes' principal power.
ISSN:1089-7798
1558-2558
DOI:10.1109/LCOMM.2015.2432019