ADRC - Lesson 10

Una radio network è un insieme di dispositivi fisici collocati in uno spazio euclideo, ognuno dei qua dotato di un trasmettitore radio (o wireless). Ogni nodo \(v\) della rete ha un fissato raggio di trasmissione \(r(v) > 0\), entro il quale potrà trasmettere il suo segnale. Un qualsiasi nodo \(w\) per ricevere un messaggio da \(v\) deve essere ad una distanza minore del raggio di trasmissione \(r(v)\) \[ \Vert v - w \Vert \leq r(v) \] Inoltre il nodo \(v\) non può selezionare a quale dei suoi nodi vicini inviare il messaggio e a quali no: il messaggio verrà trasmesso in broadcast a tutti i nodi entro il raggio di trasmissione di \(v\). Questo tipo di comunicazione è detta node based¹.

Data quindi una rete radio si può costruire una grafo diretto delle comunicazioni, in cui esiste l'arco diretto \((u,v)\) solo se \(v\) è coperto dal raggio di trasmissione di \(u\).

Le reti radio sono anche dette unknown in quanto i nodi non hanno nessuna conoscenza in merito agli altri nodi e alla loro posizione, perciò è come considerare un grafo in cui i nodi non conoscono il loro vicinato, in cui hanno una sola porta dalla quale trasmettere il messaggio e basta.

Infine le reti radio sono considerate essere un sistema completamente sincrono Tutti i nodi condividono un clock globale, perciò diremo che i nodi agiscono in time slots Inoltre si assume che i messaggi vengono trasmessi nella propria area di stramissione in un solo time slot.

In un contesto reale, in genere, se troppi dispositivi trasmettono nello stesso momento e in una stessa area si crea troppo rumore, o interferenza. In una rete radio quindi, se un nodo \(v\) riceve più di un messaggio in uno stesso time slot, assumeremo che si crei una interferenza e che quindi \(v\) non ha ricevuto il messaggio.

Più formalmente diremo che il nodo \(v\) viene informato al time slot \(t>0\) se e solo se esiste un unico suo vicino che gli trasmette il messaggio al tempo \(t\).

Uno dei task più comuni in un ambiete reale è quello del broadcast di un segnale su una rete radio. Come accennato, questo task soffre del problema dell'interferenza, perciò si vuole trovare un protocollo che porti a termine il broadcast di un'informazione considerando questa ulteriore difficoltà.

Modelliamo quindi il problema considerando come grafo il grafo di comunicazione \(G\) derivato dalla rete radio, assumendo di trovarci sotto le seguenti assunzioni:

1. Sistema sincrono ogni nodo condivide uno stesso clock globale che standisce le azioni.
2. Unica sorgente \(s\) che avvia il protocollo.
3. Connettività di \(G\), non necessariamente forte, quantomeno ogni nodo deve essere raggiungibile dalla sorgente \(s\).
4. Presenza di interferenze come descritta nella precedente sezione: un nodo \(v\) viene informato al tempo \(t\) se esiste un unico nodo che al tempo \(t-1\) gli trasmette il messaggio.

Come primo passo potremmo iniziare considerando il protocollo di flooding discusso nella lezione 3. È facile trovare un controesempio in cui il protocollo non informerà mai tutti i nodi

Consideriamo il grafo di comunicazione nella precedente immagine, e supponiamo che la sorgente sia il nodo \(s\). Al time slot \(t_0\) la sorgente \(s\) invierà il messaggio ai nodi \(u,v,w\), e al time slot successivo i nodi \(u,v,w\) invieranno il messaggio al nodo \(x\), causando un interferenza. Dopo che \(u,v,w\) avranno trasmesso, essi entrarenna nello stato done e non trasmetteranno mai più. Così facendo il nodo \(x\) non riceverà mai il messaggio, e il task non sarà mai risolto.

Assumiamo che i nodi siano univocamente identificati da un valore nell'intervallo \(\left[ 1, n \right]\), e che tutti i nodi conoscano una buona approssimazione di \(n\). Per semplicità al momento assumiamo che conoscano il valore esatto di \(n\).

L'idea del protocollo Round-Robin (in breve RR) è quella di scandire il protocollo in fasi con durata complessiva di \(n\) time slots ciascuno. Dato che ogni fase \(k \geq 0\) dura esattamente \(n\) istanti, ogni nodo con etichetta \(i\) trasmetterà al time slot \(i\)-esimo della fase \(k\). Più formalmente per ogni \(k \geq 0\), il nodo \(i\) può trasmettere solo negli istanti \(kn + i\). Importante osservare che è possibile definire una scansione temporale delle azioni da svolgere grazie all'assunzione di sincronismo del sistema.

Questo sistema ci garantisce che non è possibile che accada una situazione d'interferenza, in quanto può "paralre" (trasmettere) un solo nodo alla volta.

if self.state == "SOURCE":
    spontaneously:
	self.state = "INFORMED"

elif self.state == "ASLEEP":
    receiving(msg):
	self.state = "INFORMED"

elif self.state == "INFORMED":
    global clock, n
    if clock % n == self.id:
	transimt(msg)
	self.state = "DONE"

elif self.state == "DONE":
    None

Fin ora abbiamo assunto che tutti i nodi hanno una conoscenza di \(n\), oppure una sua buona approssimazione. Per esempio, se tutti i nodi avessero come approssimazione di \(n\) un valore del tipo \(3.5n\), l'efficienza del protocollo RR in temrmini asintotici non cambia.

Supponiamo ora invece che i nodi abbiano un'approssimazione \(N\) del numero di nodi \(n\). Col protocollo RR il tempo di terminazione globale² sarà \(O(N^2)\). Purtroppo però, se \(N \approx n^2\) il tempo di terminazion del protocollo sarà dell'ordine di \(O(n^4)\), e se \(N \approx 2^n\) il tempo di completamento sarà \(O(2^{2n})\) (molto male!).

Supponiamo in maniera ancor più generale che i nodi della rete non conoscano affatto \(n\) né una sua stima. Generalmente, in questi casi in cui non si conoscono alcuni parametri importanti per il problema, si ricorre alla tecnica della simulazione, in cui si provano tutti i possibili valori che i parametri mancanti possono assumere.

In questo caso quindi, dato che stiamo in un sistema totalmente sincrono, si eseguirà per prima cosa il protocollor RR supponendo che \(n\) sia pari ad 1, poi si ripete supponendo che sia uguale 2, e così via… Così facendo, esisterà un tempo \(t\) nel quale verrà eseguito il protocollo col corretto valore di \(n\), portando a termine così il task del bradcast su reti radio.

def round_robin(n):
    clock = 0

    if self.state == "SOURCE":
	self.state = "INFORMED"

    for fase in range(n):

	for round in range(n):

	    if self.state == "ASLEEP":
		receiving(msg):
		    self.state = "INFORMED"

	    elif self.state == "INFORMED":
		if clock % n == self.id and self.id <= n:
		    transimt(msg)
		    self.state = "DONE"

	    elif self.state == "DONE":
		None

	    clock += 1

i = 1
while True:
    round_robin(i)
    i += 1

Importante specificare però, che qualora un nodo abbia una etichetta \(x\) maggiore del corrente valore di \(n\), esso non dovrà mai essere in grado di mandare il messaggio, in quanto potrebbe esistere un altro nodo con etichetta \(y \leq n\) tale che \(x \equiv_n y\), e quindi potrebbero occorrere interferenze.

In questo caso il task verrà completato in un tempo dell'ordine di \[ TIME = \sum_{i=1}^{n} TIME(\texttt{round_robin}(i)) = \sum_{i=1}^{n} \Theta(i^2) \in \Theta(n^3) \]