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 source">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 source">b>dlog⁡log⁡n$b>d\log \log n$, for some constant source">d>1$d>1$, which wakes up a network in source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011342&_mathId=si16.gif&_user=111111111&_pii=S0304397515011342&_rdoc=1&_issn=03043975&md5=13fd8848b8808715eb1cc4c5f745047c">source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011342-si16.gif">$\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 source">O(log⁡n(log⁡b+log⁡log⁡n))$\mathcal{O}(\log n(\log b+\log \log n))$, because any deterministic algorithm requires source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011342&_mathId=si18.gif&_user=111111111&_pii=S0304397515011342&_rdoc=1&_issn=03043975&md5=ca50b85dd356821558b06bebb7ecfca3">source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011342-si18.gif">$\mathrm{\Omega }(\frac{k}{b}\log \frac{n}{k})$ time. We give a randomized algorithm that wakes up a network within source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011342&_mathId=si162.gif&_user=111111111&_pii=S0304397515011342&_rdoc=1&_issn=03043975&md5=f9884748f68fddfec59766b4d198b803">source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011342-si162.gif">$\mathcal{O}(k^{1/b}\ln \frac{1}{ϵ})$ rounds with a probability that is at least source">1−ϵ$1-ϵ$, for any source">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 source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011342&_mathId=si10.gif&_user=111111111&_pii=S0304397515011342&_rdoc=1&_issn=03043975&md5=2b6ddaf62b6ff2abbb2039d53552547b">source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011342-si10.gif">$\mathcal{O}({\log }^{-1}(\frac{1}{p})k\log n{\log }^{1/b}k)$, and the other in time source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011342&_mathId=si11.gif&_user=111111111&_pii=S0304397515011342&_rdoc=1&_issn=03043975&md5=06e8ebc7f20738dec44c87ec39550123">source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011342-si11.gif">$\mathcal{O}({\log }^{-1}(\frac{1}{p})\frac{k}{b}\log n\log (b\log n))$ when the inequality source">b>log⁡(128blog⁡n)$b>\log (128b\log n)$ holds, both with probabilities that are at least source">1−1/poly(n)$1-1/\text{poly}(n)$.