Back to Search
Start Over
On the Wake-Up Problem in Radio Networks.
- Source :
- Automata, Languages & Programming (9783540275800); 2005, p347-359, 13p
- Publication Year :
- 2005
-
Abstract
- Radio networks model wireless communication when processing units communicate using one wave frequency. This is captured by the property that multiple messages arriving simultaneously to a node interfere with one another and none of them can be read reliably. We present improved solutions to the problem of waking up such a network. This requires activating all nodes in a scenario when some nodes start to be active spontaneously, while every sleeping node needs to be awaken by receiving successfully a message from a neighbor. Our contributions concern the existence and efficient construction of universal radio synchronizers, which are combinatorial structures introduced in [6] as building blocks of efficient wake-up algorithms. First we show by counting that there are (n,g)-universal synchronizers for . Next we show an explicit construction of (n,g)-universal-synchronizers for . By way of applications, we obtain an existential wake-up algorithm which works in time and an explicitly instantiated algorithm that works in time , where n is the number of nodes and Δ is the maximum in-degree in the network. Algorithms for leader-election and synchronization can be developed on top of wake-up ones, as shown in [7], such that they work in time slower by a factor of than the underlying wake-up ones. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540275800
- Database :
- Supplemental Index
- Journal :
- Automata, Languages & Programming (9783540275800)
- Publication Type :
- Book
- Accession number :
- 32701434
- Full Text :
- https://doi.org/10.1007/11523468_29