Scalable wake-up of multi-channel single-hop radio networks

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/b⁡klog⁡n) time, where k is unknown. We give a deterministic scalable algorithm for the special case when b>dlog⁡log⁡n, for some constant d>1, which wakes up a network in O(kblog⁡nlog⁡(blog⁡n)) time, with k unknown. This algorithm misses time optimality by at most a factor of O(log⁡n(log⁡b+log⁡log⁡n)), because any deterministic algorithm requires Ω(kblog⁡nk) time. We give a randomized algorithm that wakes up a network within O(k1/bln⁡1ϵ) rounds with a probability that is at least 1−ϵ, for any 0<ϵ<1, where k is known. We also consider a model of jamming, in which each channel in any round may be jammed to prevent a successful transmission, which happens with some known parameter probability p, independently across all channels and rounds. For this model, we give two deterministic algorithms for unknown k: one wakes up a network in time O(log−1⁡(1p)klog⁡nlog1/b⁡k), and the other in time O(log−1⁡(1p)kblog⁡nlog⁡(blog⁡n)) when the inequality b>log⁡(128blog⁡n) holds, both with probabilities that are at least 1−1/poly(n).