The Wake‐Up Problem in MultiHop Radio Networks
Marek Chrobák, Leszek Gsieniec, Dariusz Rafal Kowalski · SIAM Journal on Computing · 2007
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.