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

详细信息    查看全文

• 作者：Bogdan S. Chlebus^a ; ¹ ; Gianluca De Marco^b ; ^{demarco@dia.unisa.it" class="auth_mail" title="E-mail the corresponding author} ; Dariusz R. Kowalski^c
• 关键词：Multiple access channel ; Radio network ; Multi-channel ; Wake-up ; Synchronization ; Deterministic algorithm ; Randomized algorithm ; Distributed algorithm
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：15 February 2016
• 年：2016
• 卷：615
• 期：Complete
• 页码：23-44
• 全文大小：579 K

文摘

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(klog^1/b⁡klog⁡n)$\mathcal{O}(k{\log }^{1/b}k\log n)$ time, where k   is unknown. We give a deterministic scalable algorithm for the special case when 7b2349ff0f339a9830f2bffa6ddf" title="Click to view the MathML source">b>dlog⁡log⁡n$b>d\log \log n$, for some constant d>1$d>1$, which wakes up a network in $\mathcal{O}(\frac{k}{b}\log n\log (b\log n))$ time, with k   unknown. This algorithm misses time optimality by at most a factor of O(log⁡n(log⁡b+log⁡log⁡n))$\mathcal{O}(\log n(\log b+\log \log n))$, because any deterministic algorithm requires $\mathrm{\Omega }(\frac{k}{b}\log \frac{n}{k})$ time. We give a randomized algorithm that wakes up a network within $\mathcal{O}(k^{1/b}\ln \frac{1}{ϵ})$ rounds with a probability that is at least 1−ϵ$1-ϵ$, for any 0<ϵ<1$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 b2039d53552547b">$\mathcal{O}({\log }^{-1}(\frac{1}{p})k\log n{\log }^{1/b}k)$, and the other in time $\mathcal{O}({\log }^{-1}(\frac{1}{p})\frac{k}{b}\log n\log (b\log n))$ when the inequality b>log⁡(128blog⁡n)$b>\log (128b\log n)$ holds, both with probabilities that are at least 1−1/poly(n)$1-1/\text{poly}(n)$.