2009 | OriginalPaper | Buchkapitel
Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps
verfasst von : Dariusz R. Kowalski, Andrzej Pelc
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We address the fundamental distributed problem of leader election in ad hoc radio networks modeled as undirected graphs. Nodes are stations having distinct integer labels, and each node knows only its own label and a polynomial upper bound on all labels. A signal from a transmitting node reaches all neighbors. What distinguishes radio networks from message-passing networks is that a message is received successfully by a node, if and only if, exactly one of its neighbors transmits in this round. If two neighbors of a node transmit simultaneously in a given round, none of the messages is heard by the receiving node. In this case we say that a
collision
occurred at this node.
An important capability of nodes of a radio network is
collision detection
: the ability of nodes to distinguish a collision from the background noise occurring when no neighbor transmits. (This ability is the “keen ear” of the nodes.) Can collision detection speed up leader election in arbitrary radio networks? We give a positive answer to this question. More precisely, our main result is a deterministic leader election algorithm working in time
O
(
n
) in all
n
-node networks, if collision detection is available, while it is known that deterministic leader election requires time
Ω
(
n
log
n
), even for complete networks, if there is no collision detection. This is the first computational task whose execution for arbitrary radio networks is shown to be faster with collision detection than without it.