ADRC - Lesson 12

Nella lezion 10 è stato introdotto il protocollo Round-Robin per il task del broadcast a singola sorgente su reti wireless unknown¹ con presenza d'interferenza, ed è stato dimostrato che questo protocollo porta a termine il suo task in tempo \(O(Dn)\), dove \(D\) è il diametro della rate di \(n\) nodi considerata.

Avalendosi di altri costrutti matematici e aggiungendo conoscenza ai nodi è possibile ottenere risultati migliori. Per esempio, dato l'insieme \( \left[ n \right] \) e un \(k \leq n\) diremo che la famiglia di sottoinsiemi \(H = \lbrace H_1, H_2, ..., H_t \rbrace\) è \((n,k)\)-selettiva se per ogni sottoinsieme \(S \subseteq \left[ n \right]\) con \(\vert S \vert \leq k\) esiste almeno un \(H_i \in H\) tale che \(\vert S \cap H_i \vert = 1\).
Se supponiamo che tutti i nodi conoscano la stessa faminiglia \(H\) \((n,\Delta)\)-selettiva di \(V\), dove \(\Delta = \max_{v \in V}{ \lbrace d(v) \rbrace }\), allora è possibile definire un protocollo deterministico che termina il task in questione in tempo \(O(D \cdot \vert H \vert)\), con \(D = diam(G)\).

Nell'articolo Round Robin is optimal for fault-tolerant broadcasting on wireless networks viene dimostrato che per valori sufficientemente grandi di \(n\) esiste sempre una famigli \((n,k)\)-selettiva di dimensione \(O(k \log{n}\). Tale risultato implica che sotto queste assunzioni è possibile definire un protocollo che termina il task in tempo \(O(D \Delta \log{n})\).

Purtroppo però senza queste assunzioni non è possibile fare deterministicamente meglio.

THM Data un grafo diretto di trasmissione \(G=(V,E)\) realtivo ad una rete wireless, con diametro \(D\), grado massimo \(\Delta\) tale che \(D\Delta < n\), allora esiste sempre un modo di manipolare i ritardi in modo tale che non si possa risolvere il problema del broadcasting a singola sorgente in un tempo migliore di \[ \Omega\left( D \Delta \log{ \left( \frac{n}{D} \right) } \right) \] a meno che non si assuma che tutti i nodi conoscano un famiglia \((n,\Delta)\)-selettiva di \(V\).

Per esempio, se consideriamo un grafo con un diametro costante, per esempio \(D = 3\), avremo che il grado massimo dei nodi \(\Delta\) crescerà molto velocemente al crescere di \(n\), per esempio in maniera lineare (\(\Delta \in O(n)\)). Perciò in questo caso avremo un lowerbound di \(\Omega(n \log{n})\).

Quello che ci si chiede è se esiste un modo per abbattere il fattore \(\Delta\) dal lowerbound. Il teorema precedentemente enunciato ci dice che questo è deterministicamente impossibile, perciò è necessario occorrere alla randomness.

Definiamo un protocollo probabilistico molto semplice, in cui ogni nodo informato trsmette ai suoi vicini con una certa probabilità \(p\) fissata e uguale per tutti. È facile mostrare un controesempio in cui il tampo medio di completamento del protocollo è pessimo.

Sia la sorgente \(u\). Sicuramente esiste un tempo \(t_0\) in cui \(u\) trasmette il messagio a tutti i suoi vicini \(1, 2, ..., n-1\) senza interferenze. Dal time slot successivo tutti i suoi vicini inizieranno a tresmettere verso \(v\), ognuno con probabilità \(p\). Supponiamo per esempio che \(p = \frac{1}{2}\), e cerchiamo di stabilire entro quanto tempo ci si aspetta che \(v\) verrà informato senza alcuna interferenza. Per prima cosa dobbiamo calcolare con quale probabilità l'evento \(\mathcal{E} = \mbox{" } v \mbox{ vinene informato"}\) occorre, e questo si può fare usando la distribuzione binomiale \[ \mathcal{P}(\mathcal{E}) = \binom{n-2}{1}\frac{1}{2}\left(1 - \frac{1}{2}\right)^{n-3} = \frac{n-2}{2^{n-2}} \in \Theta\left( \frac{n}{2^n} \right) \] Ciò implica che il tempo di completamento del task di questo protocollo nel controesempio in questione è di circa \(\Theta\left( \frac{2^n}{n} \right)\) (molto male!).

Anche se \(v\) avesse molti meno vicini, per esempio \(\sqrt(n)\), il tempo di completamento sarebbe pessimo (ovvero esponenziale \(\Theta\left( \frac{2^{\sqrt{n}}}{\sqrt{n}} \right)\)).
Se invece \(v\) avesse solomante 2 vicini che trasmettono, il protocollo terminerebbe in tempi brevissimi (sempre considerando questo esempio).

Ciò ci suggerisce che dobbiamo trovare un valore di \(p\) in modo tale che è poco probabile che avvengano interferenze, ovvero un valore per il quale in media trasmette un solo vicino di ogni nodo. Considerando sempre il precedente controesempio, il valore ottimale di \(p\) per il quale i vicini di \(v\) devono trasmettere è \(\frac{1}{d^{(in)}(v)}\), ovvero il grado entrante di \(v\).