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 Ω(k/b log n/k) time. We give a randomized algorithm that wakes up a network within O(k1/b ln 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 (1/p)k log n log 1/b k), and the other in time O(log-1 (1/p)k/b log n log (blog n)) when the inequality b> log (128 blog n) holds, both with probabilities that are at least 1 - 1/poly( n).

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

DE MARCO, Gianluca;
2016-01-01

Abstract

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 Ω(k/b log n/k) time. We give a randomized algorithm that wakes up a network within O(k1/b ln 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 (1/p)k log n log 1/b k), and the other in time O(log-1 (1/p)k/b log n log (blog n)) when the inequality b> log (128 blog n) holds, both with probabilities that are at least 1 - 1/poly( n).
2016
File in questo prodotto:
File Dimensione Formato  
multi-channel-wakeup-j1 De Marco.pdf

accesso aperto

Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Creative commons
Dimensione 314.98 kB
Formato Adobe PDF
314.98 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4676659
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 19
social impact