Sviluppo e valutazione prestazionale di soluzioni di routing per reti di sensori

  
5
Queste limitazioni, in unione alla necessità di coprire ampie aree, costringono ad 
utilizzare nelle trasmissioni dei nodi intermedi e a realizzare reti che siano in grado di 
formarsi autonomamente senza l’intervento di un qualche ente esterno e che minimizzino 
anche il consumo energetico nello svolgimento delle loro operazioni. 
Uno degli aspetti più critici da affrontare è, senza dubbio, l’algoritmo di routing. Purtroppo, 
come analizzato nel dettaglio in [1], le caratteristiche di queste reti in generale e l’elevato 
numero e le ridotte capacità dei nodi, in particolare, mettono in difficoltà qualsiasi algoritmo di 
routing non appositamente progettato, invalidando le soluzioni pensate per le normali reti ad-
Hoc.  
Essendo l’argomento molto affascinante, ben presto la comunità scientifica ha proposto 
soluzioni specifiche per questo tipo di reti; attualmente, i fronti lungo i quali si svolge la 
ricerca sono due, l’Interest Dissemination, ossia come il sink possa comunicare ai sensori le 
rilevazioni che vuole ricevere; il Convergecasting, ossia l’invio delle rilevazioni dei sensori al 
Sink. La disseminazione degli interessi dal sink ai nodi e la raccolta dei dati dai nodi sensori 
al sink, deve poi essere effettuata massimizzando il risparmio energetico, in modo da 
aumentare il più possibile il tempo di operatività della rete stessa  
Alcune delle proposte sono applicabili solo alla fase di Interest Dissemination, come 
GOSSIP [2], che fondamentalmente prevede di effettuare flooding limitando però, il numero 
di nodi coinvolti nella ritrasmissione dei messaggi (ciascun nodo ritrasmette un messaggio 
ricevuto solo con una certa probabilità p; mentre con probabilità (1-p) rimane in silenzio). 
 
Altre soluzioni affrontano solo la fase di Convergecasting, come GERAF [3], che integra a 
un routing geografico basato sulla conoscenza della posizione dei nodi e del sink  
meccanismi di alternanza dei nodi tra stati di awake in cui l’interfaccia radio e’ operativa ed il 
consumo energetico e’ alto e stati di asleep in cui il nodo non può trasmettere e ricevere ma 
il consumo energetico è minimo. 
Altre soluzioni si concentrano solo sulla minimizzazione del consumo energetico, come 
GAF [4] che si propone di determinare quali nodi possono essere spenti senza perdere la 
connessione della rete, o STEM [5], che utilizzando due radio e dedicandone una a svegliare 
i vicini, permette ai nodi di restare spenti finché non sia necessaria la loro accensione. 
Infine esistono soluzioni più complete, come directed diffusion [6] che implementa sia la 
fase di disseminazione degli interessi che di Convergecasting, ma con modalità che causano 
un overhead elevato e quindi un consumo energetico eccessivo. 
Purtroppo, nessuna delle soluzioni proposte affronta contemporaneamente tutti e tre i 
punti chiave descritti, inoltre, l’utilizzo di soluzioni separate per i diversi aspetti, non sembra 
essere una buona soluzione. 
  
6
Per ottenere un algoritmo soddisfacente è necessario considerare attentamente lo 
scenario nel quale esso deve operare. In questo tipo di reti, infatti, lo scambio dei pacchetti, 
tende ad avere dei picchi intervallati da periodi relativamente lunghi di inattività, nei quali 
risulta conveniente spegnere i nodi per risparmiare energia. Ciò, pur permettendo di ridurre il 
consumo, modifica di continuo la topologia della rete, rendendo difficoltoso, e soprattutto 
dispendioso, cercare di determinare le rotte attraverso la conoscenza della stessa.  
D’altro canto abbiamo che i nodi sensori non devono comunicare tra di loro, ma soltanto 
con il Sink, e che, l’elevata quantità di nodi, oltre a rappresentare un limite, è per certi versi 
anche un vantaggio in quanto permette di avere un numero di rotte altrettanto elevato. Un 
altro aspetto da considerare è il fatto che le trasmissioni avvengono sul canale radio, per sua 
natura un canale condiviso, e che quindi si può, trasmettendo in BROADCAST, raggiungere 
con lo stesso sforzo uno o tutti i nodi presenti nel raggio trasmissivo.  
Tenendo presenti le considerazioni appena fatte, proporremo un nuovo algoritmo di 
routing nel quale esse vengono tenute in alta considerazione. Prevedremo, infatti, di 
realizzare l’instradamento senza avere rotte predeterminate, ma utilizzando trasmissioni in 
broadcast per far identificare ad ogni nodo, solo nel momento in cui ne ha la necessità, quale 
tra i suoi vicini è in quel particolare momento attivo e in posizione migliore rispetto al Sink. 
I nodi vengono a conoscenza della propria distanza dal Sink nella fase di Interest 
Dissemination, nella quale, questa informazione viene propagata insieme all’interesse 
stesso. Quindi, ogni volta che un nodo deve trasmettere dati riguardanti un particolare 
interesse, esso trasmetterà in broadcast una sequenza di richieste, indicando la propria 
distanza dal sink. I nodi che in quel momento sono attivi, alla ricezione della richiesta,  
valuteranno la propria posizione rispetto a quella del nodo che la ha trasmessa, e nel caso in 
cui si trovino ad una distanza inferiore, si offriranno per essere usati come transito. Il nodo 
impegnato nella propagazione del messaggio, tra tutte le offerte ricevute, ne sceglierà una e 
quindi trasmetterà al nodo corrispondente il messaggio contenente i dati. 
Agendo in questo modo, il nostro algoritmo, sfruttando sia trasmissioni in broadcast che la 
numerosità dei nodi, riesce, senza mantenere informazioni dettagliate sulla topologia o sullo 
stato dei suoi vicini e permettendo ad essi di alternare le fasi di asleep e awake, in maniera 
del tutto indipendente tra di loro, a realizzare sia l’Interest Dissemination che il 
Convergecasting in maniera più conveniente rispetto agli approcci più deterministici. 
Per dimostrare il corretto funzionamento dell’algoritmo proposto abbiamo effettuato 
simulazioni NS2. Dato che questo simulatore, non dispone di strumenti specifici per la 
simulazione di reti di sensori, abbiamo sviluppato un Framework di supporto per l’analisi dei 
dati. Questo  Framework, mediante la scrittura di poche righe di codice, permette di 
effettuare agevolmente simulazioni di reti di sensori basate su di un qualsiasi algoritmo di 
routing. Le sue principali funzionalità sono: 
  
7
 ξ  Possibilità di generare topologie di una qualsiasi dimensione, ottenute o 
distribuendo i nodi in un area definibile in modo tale da formare una griglia 
uniforme, o posizionandoli all’interno della stessa area in maniera casuale 
secondo una distribuzione uniforme o una distribuzione HILL. 
 ξ  Possibilità di forzare le topologie generate ad essere connesse. In questo caso 
verrà generata una topologia iniziale anche non connessa, che poi, tramite 
aggiustamenti successivi, sarà resa connessa. 
 ξ  Possibilità di generare in maniera casuale, con un modello, sequenze di eventi da 
iniettare nella rete.  
 ξ  Misurazione secondo diverse metriche delle prestazioni della rete 
Inoltre, grazie alla possibilità di realizzare script partendo da topologie e sequenze di 
eventi predefinite, il framework permette di analizzare il comportamento di più algoritmi 
sottoponendoli alle stesse sollecitazioni. 
Con il supporto di questo Framework abbiamo potuto condurre analisi dettagliate del 
funzionamento dell’algoritmo proposto, analizzando il suo comportamento al variare dei 
parametri operativi e degli scenari in cui viene chiamato ad operare. Sempre grazie al 
framework è stato possibile confrontare il suo funzionamento con quello di Directed 
Diffusion, evidenziando pregi e i difetti di una soluzione rispetto all’altra. 
Come vedremo nell’ultimo capitolo di questo documento i risultati ottenuti dal nostro 
algoritmo sono soddisfacenti. Esso, infatti, si comporta mediamente meglio di directed 
diffusion. In particolare noteremo che pur garantendo un tempo di vita della rete maggiore, il 
nostro algoritmo offre interessanti prestazioni e risulta altamente scalabile, in quanto, non 
risente praticamente del numero dei nodi, a differenza di directed diffusion, che ben presto 
registra un calo delle prestazioni su tutti i fronti. In sostanza, verificheremo che l’approccio da 
noi adottato, risulta ottimo nelle applicazioni tipiche di una rete di sensori. 
La descrizione dell’algoritmo che proponiamo è riportata nel primo capitolo di questo 
documento. Nei restanti capitoli definiremo prima le metriche di interesse da noi utilizzate per 
valutare gli algoritmi, quindi una accurata descrizione del framework da noi sviluppato, e 
infine un capitolo dedicato alla descrizione delle simulazioni che abbiamo effettuato e dei 
risultati ottenuti. 
  
8
1 Descrizione dell’algoritmo DIGE 
 
In questa sezione descriveremo DIGE,  un nuovo algoritmo di routing per reti di sensori 
che, prendendo spunto da soluzioni già esistenti, realizza tanto l’Interest Dissemination che il 
ConvergeCasting in una rete nella quale i nodi alternano periodi di awake a periodi di asleep. 
 
1.1 Gestione awake/asleep 
 
La maggior parte del fabbisogno energetico dei nodi viene assorbito dall’interfaccia 
radio, la quale necessita di elevate quantità di energia in trasmissione, in ricezione ed 
anche semplicemente per rimanere attiva. Per questo motivo, i nodi, al fine di permettere il 
risparmio energetico, dispongono di due modalità di funzionamento. 
La prima modalità, definita awake, è la condizione normale dei nodi; in questo stato essi 
mantengono l’interfaccia radio attiva e in ascolto sul canale radio, sono pertanto in grado di 
ricevere pacchetti. Un nodo tenuto in questo stato consuma costantemente una quantità di 
energia paragonabile all’energia dissipata durante la vera e propria ricezione. 
La seconda modalità di funzionamento è definita di asleep. In questo stato, i nodi 
tengono spenta l’interfaccia radio ottenendo così, un consumo di energia di alcuni ordini di 
grandezza inferiore al consumo nello stato di awake. Il vantaggio di aver un così basso 
consumo lo si paga con il fatto che i nodi in questo stato non sono in grado ne di ricevere 
ne di trasmettere pacchetti, e che quindi non è possibile in alcun modo raggiungerli. 
Nell’algoritmo che presentiamo i nodi alternano fasi di asleep a fasi di awake secondo 
una schedulazione che dispone dei seguenti tre parametri: 
 ξ  dutyCycle: Definisce la percentuale del tempo totale in cui il nodo è nello stato 
di awake. 
 ξ  awakeTime: Determina la quantità di tempo per cui un nodo permane nella 
fase di awake. Il fatto di avere una lunghezza fissa dello stato di awake 
presenta diversi vantaggi. Innanzitutto, se il tempo di awake fosse troppo breve, 
difficilmente si potrebbe contattare il nodo con successo, in quanto potrebbe 
essere estremamente difficoltoso per i vicini trasmettere esattamente nei pochi 
istanti di tempo in cui esso rimane nello stato di awake. In secondo luogo, 
avendo un tempo fissato per la durata dello stato di awake, si può conoscere 
l’intervallo entro il quale rispondere ad una sua richiesta avendo la certezza di 
trovare il nodo attivo. Infine, ma altrettanto importante, si deve considerare che i 
  
9
nodi reali hanno delle isteresi nei cambiamenti di stato che non permettono di 
permanere in uno stato per un tempo piccolo a piacere. 
 ξ  cycleLength : Definisce l’intervallo di tempo massimo che può trascorrere tra 
due fasi di awake. Avere un tempo massimo, entro il quale un nodo debba 
obbligatoriamente transitare per la fase di awake permette di limitare 
superiormente i ritardi. Infatti, avendo posto questo limite abbiamo la certezza 
che trascorso questo tempo il nodo che si vuole contattare deve essere stato, 
almeno una volta, in grado di ricevere i messaggi a lui diretti.  
Vediamo ora come viene effettuata la schedulazione dei tempi: 
Allo startUp, un nodo il nodo determinerà casualmente un istante che rappresenterà la 
base per una suddivisione di tutto il tempo futuro in sottointervalli lunghi esattamente 
 ÷
 ÷
 ≠
 •
 ♦
 ♦
 ♥
 ♣
dutyCycle
awakeTime
1
 
All’interno di ognuno di questi intervalli verrà scelto, ancora casualmente, un istante per 
transitare nello stato di awake, nel quale si permarrà per un intervallo lungo esattamente 
awakeTime. Un esempio di una possibile schedulazione è il seguente: 
 
 
Verifichiamo che questa schedulazione abbia le caratteristiche richieste. 
L’ awakeTime è ovviamente rispettato in quanto il nodo prevede di restare in awake per 
esattamente questo tempo. 
Il rispetto del dutycycle è garantito dal modo in cui si è scelta la lunghezza degli 
intervalli, infatti il nodo resterà nello stato di awake ogni intervallo lungo 
awake*(1/dutyCycle), ossia resterà attivo per la seguente percentuale del tempo totale: 
AWAKE 
ASLEEP 
awakeTime(1/duty awakeTime(1/duty awakeTime(1/duty
awakeTi
awakeTi
awakeTi
  
10
dutyCycle
dutyCycle
awakeTime
awakeTime
  
 ÷
 ÷
 ≠
 •
 ♦
 ♦
 ♥
 ♣ 1
 
Infine, esiste una massima distanza tra due fasi di awake. Il caso peggiore possibile (e 
quindi la massima lunghezza di questo intervallo) si avrà quando, in un intervallo la fase di 
awake è posta immediatamente all’inizio, nell’intervallo successivo è posta alla fine, e si 
inizia ad osservare il nodo proprio nel punto in ci esso esegue la prima transizione da 
awake ad asleep, illustriamo con un grafico quanto appena descritto: 
 
AWAKE 
ASLEEP 
awakeTime(1/duty awakeTime(1/duty
  
11
1.2 Interest Dissemination  
 
Nello scenario nel quale il nostro algoritmo è chiamato ad operare, un ottimo algoritmo 
dal quale prendere spunto è FIREWORK [2]. Nel documento che lo descrive è dimostrato 
che se ogni nodo propaga, con probabilità  1-p,  il messaggio a (se esistono) un numero 
constante c, con c≥4, di  suoi vicini scelti casualmente e con probabilità p a tutti, è 
possibile con valori bassi di p (ad esempio ponendo p=0,1) raggiungere tutti i nodi 
appartenenti alla stessa componente connessa della topologia originale.  
FIREWORK è pensato per reti nelle quali i nodi sono sempre raggiungibili e hanno la 
conoscenza del proprio vicinato. Nei prossimi paragrafi mostreremo come, introducendo 
alcune variazioni, sia possibile utilizzarlo anche per la disseminazione degli interessi in uno 
scenario nel quale queste due condizioni vengono a mancare. 
Nel seguito, fisseremo la variabile C al valore 4 che è il minimo valore ammesso. 
 
1.2.1 Selezionare 4 vicini casualmente 
Nell’algoritmo che proponiamo i nodi non possiedono alcuna informazione sulla 
topologia nella quale sono inseriti, e, di conseguenza, non possono scegliere in alcun 
modo i 4 vicini ai quali propagare il messaggio come richiesto da FIREWORK.  
Considerando che i nodi alternano, con la modalità presentata all’inizio del capitolo,  
fasi di awake e di asleep in maniera casuale, avremo che; scelto un istante, alcuni di essi 
saranno casualmente nello stato di awake, e quindi in grado di ricevere un messaggio, 
mentre altri saranno nello stato di asleep. Grazie a questo comportamento dei nodi 
possiamo asserire che; scegliere casualmente n vicini, equivale a scegliere casualmente 
un insieme di istanti e selezionare i vicini che sono in quel momento attivi. 
I nodi eseguono la disseminazione degli interessi attraverso l’invio di un messaggio, 
definito ANNOUNCE, con il quale annunciano, appunto, un interesse. I nodi all’interno 
del raggio trasmissivo, solo quando ricevono per la prima volta un ANNOUNCE da un 
loro vicino, risponderanno con un messaggio di ACK, con il quale comunicano al primo 
nodo che hanno ricevuto l’interesse. Dato che i nodi rispondono solo la prima volta che 
ricevono l’ANNOUNCE da un vicino, ogni ricezione di ACK, implica che un nuovo nodo è 
stato contattato. Premesso ciò, i nodi, per selezionare casualmente i 4 vicini, trasmettono 
una sequenza di messaggi casualmente distanziati, e quando gli ACK ricevuti saranno 
almeno 4, potranno terminare la loro ricerca. Per non perdere eventuali risposte, il nodi , 
dopo aver trasmesso un interesse non andranno più in asleep fino a quando non 
avranno completato l’operazione. 
  
12
In un generico istante, i vicini di un nodo impegnato nella propagazione di un 
interesse, possono essere divisi in tre partizioni, rispettivamente: 
 ξ  Vicini già contattati dal nodo. 
 ξ  Vicini non contattati ma impegnati nella propagazione di un interesse. 
 ξ  Vicini non contattati da nessun nodo. 
Abbiamo affermato che ogni nodo deve scegliere casualmente e con distribuzione 
uniforme un vicino, ma mentre i nodi appartenenti alla seconda partizione sono sempre 
nello stato di awake quelli della seconda alternano l’awake con lo asleep. Per mantenere 
l’equiprobabilità di selezione tra le ultime due partizioni è necessario che la trasmissione 
degli ACK avvenga sempre, se il nodo appartiene alla terza partizione, con una 
probabilità pari a dutyCycle, se il nodo appartiene alla seconda partizione. 
Può avvenire che i vicini di un nodo siano meno di C, e quindi che non si riesca mai 
a raggiungerne un numero sufficiente; in questo caso, così com’è previsto da 
FRAMEWORK, il nodo dovrà comunque contattarli tutti. Illustreremo come è possibile 
ottenere questo dopo aver descritto come contattarli tutti con probabilità p. 
 
1.2.2 Raggiungere tutti i vicini con probabilità p 
FIREWORK prevede che i nodi debbano contattare tutti i vicini con probabilità p.  Il 
metodo più immediato per soddisfare questo requisito è quello di far estrarre ad un nodo 
un numero casuale compreso tra 0 e 1, e, se il numero estratto è minore di p, forzare il 
nodo a contattare tutti i suoi vicini. L’adozione di questa strategia presenta il grave 
svantaggio di richiedere che i nodi impegnati a contattare tutti i loro vicini, debbano 
trasmettere un numero elevato di pacchetti.  
In questo paragrafo introdurremo un approccio alternativo che soddisfa il requisito di 
FIREWORK facendo trasmettere a tutti i nodi un numero di messaggi tale da ottenere 
per ognuno una probabilità pari a p di aver contattato tutti i nodi, ottenendo così, una 
distribuzione uniforme del carico tra tutti i nodi e una riduzione del numero di pacchetti 
necessari.  
Prima di proseguire nell’illustrazione del metodo da noi adottato introduciamo una 
utile proposizione: 
PROPOSIZIONE: Sia N un nodo e V
1,
 V
2,..
 V
n
 un insieme di nodi nel suo raggio 
trasmissivo, sia P
on
 la probabilità di raggiungere un nodo trasmettendo un solo messaggio, 
allora la probabilità di raggiungere tutti i nodi V
n
  trasmettendo k messaggi è: 
       
n
k
on
P   11