Scalable wake-up of multi-channel single-hop radio networks
Bogdan S. Chlebus, Gianluca De Marco, Dariusz Rafal Kowalski · Theoretical Computer Science · 2015
We consider single-hop radio networks with multiple channels as a model of wireless networks. There are n stations connected to b radio channels that do not provide collision detection. A station uses all the channels concurrently and independently. Some k stations may become active spontaneously at arbitrary times. The goal is to wake up the network, which occurs when all the stations hear a successful transmission on some channel. Duration of a waking-up execution is measured starting from the first spontaneous activation. We present a deterministic algorithm that wakes up a network in O(klog1/bklogn) time, where k is unknown. We give a deterministic scalable algorithm for the special case when b>dloglogn, for some constant d>1, which wakes up a network in O(kblognlog(blogn)) time, with k unknown. This algorithm misses time optimality by at most a factor of O(logn(logb+loglogn)), because any deterministic algorithm requires Ω(kblognk) time. We give a randomized algorithm that wakes up a network within O(k1/bln1ϵ) rounds with a probability that is at least 1−ϵ, for any 0log(128blogn) holds, both with probabilities that are at least 1−1/poly(n).