Monitoring churn in wireless networks

Wireless networks often experience a significant amount of churn, i.e. the arrival and departure of nodes, and often it is necessary to keep all nodes informed about all other nodes in the network. In this paper, we propose a distributed algorithm for single-hop networks that detects churn, meaning...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2012-09, Vol.453, p.29-43
Main Authors: Holzer, Stephan, Pignolet, Yvonne Anne, Smula, Jasmin, Wattenhofer, Roger
Format: Article
Language:English
Subjects:
Group membership
Monitoring
No collision detection
Sensor networks
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Wireless networks often experience a significant amount of churn, i.e. the arrival and departure of nodes, and often it is necessary to keep all nodes informed about all other nodes in the network. In this paper, we propose a distributed algorithm for single-hop networks that detects churn, meaning that the nodes observe other nodes joining or leaving the network and inform all other nodes in the network about their observations. Our algorithm works correctly even if the nodes which join or leave and the respective points in time are chosen by an adversary in a worst-case fashion. The delay until notification is small, such that all nodes of the network are informed about changes quickly, in asymptotically optimal time. We establish a trade-off between saving energy and minimizing the delay until notification for single- and multi-channel networks.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2011.08.012