| ID:
356648.0,
MPI für Informatik / Algorithms and Complexity Group |
| The wake-up problem in multihop radio networks |
| Authors: | Chrobak, Marek; Gasieniec, Leszek; Kowalski, Dariusz R. |
| Language: | English |
| Date of Publication (YYYY-MM-DD): | 2007 |
| Title of Journal: | SIAM Journal on Computing |
| Volume: | 36 |
| Issue / Number: | 5 |
| Start Page: | 1453 |
| End Page: | 1471 |
| Review Status: | Peer-review |
| Audience: | Experts Only |
| Intended Educational Use: | No |
| Abstract / Description: | We study the problem of waking up a collection of $n$ processors connected by a
multihop ad hoc ratio network with unknown topology, no access to a global
clock, and no collision detection mechanism available. Each node in the network
either wakes up spontaneously or gets activated by receiving a wake-up signal
from another node. All active nodes transmit the wake-up signals according to a
given protocol $\calW$. The running time of $\calW$ is the number of steps
counted from the first spontaneous wake-up until all nodes become activated. We
provide two protocols for this problem. The first one is a deterministic
protocol with running time $O(n^{5/3}\log n)$. Our protocol is based on a novel
concept of a shift-tolerant selector to which we refer as a (radio)
synchronizer. The second protocol is randomized, and its expected running time
is $O(D \log^2 n)$, where $D$ is the diameter of the network. Subsequently we
show how to employ our wake-up protocols to solve two other communication
primitives: leader election and clock synchronization. |
| Last Change of the Resource (YYYY-MM-DD): | 2008-02-28 |
| External Publication Status: | published |
| Document Type: | Article |
| Communicated by: | Kurt Mehlhorn |
| Affiliations: | MPI für Informatik/Algorithms and Complexity Group
|
| Identifiers: | LOCALID:C12573CC004A8E26-40739073EBED9539C12573E9004477EA-...
DOI:10.1137/S0097539704442726
ISSN:0097-5397 |
|
Advanced
