a
Facoltà di Ingegneria
Corso di Studi in Ingegneria Informatica
Tesi di laurea
Progetto e valutazione di algoritmi per
la raccolta dati affidabile su reti di
sensori senza cavo
Anno Accademico
2005/2006
Relatore
Ch.mo Prof. Stefano RUSSO
Correlatore
Ing. Marcello CINQUE
Candidato
Salvatore Falsino
matr. 885/42
Ai miei genitori
La difficoltà attira l ' uomo di carattere, perché affrontandola si realizza
(Charles De Gaulle)
INDICE
INTRODUZIONE ........................................................................................ 1
1. RETI DI SENSORI SENZA CAVO....................................................... 3
1.1
LE WIRELESS SENSOR NETWORK .................................................................. 3
1.2
DIFFERENZA TRA RETI DI SENSORI E RETI AD HOC .................................. 5
1.3
ARCHITETTURA DELLA RETE......................................................................... 6
1.4
DESCRIZIONE DEI NODI SENSORI .................................................................. 8
1.4.1
Sensing Module .............................................................................................. 8
1.4.2
Unità di elaborazione..................................................................................... 9
1.4.3
Unità di comunicazione................................................................................ 10
1.4.4
Alimentazione ............................................................................................... 10
1.5
PARAMETRI DI PROGETTO ............................................................................ 11
1.5.1
Consumo energetico ..................................................................................... 12
1.5.2
Costo ............................................................................................................ 14
1.5.3
Connettività .................................................................................................. 14
1.5.4
Topologia della rete ..................................................................................... 15
1.5.5
Dimensioni e posizionamento dei nodi......................................................... 16
1.5.6
Mobilità ........................................................................................................ 16
1.5.7
Scalabilità..................................................................................................... 17
1.5.8
Sicurezza ...................................................................................................... 17
1.5.9
Affidabilità.................................................................................................... 18
1.6
PROTOCOLLI DI COMUNICAZIONE.............................................................. 18
1.6.1
Livello Fisico................................................................................................ 18
1.6.2
Livello data-link ........................................................................................... 19
1.6.3
Livello di rete ............................................................................................... 21
1.7
I SISTEMI OPERATIVI E LE RETI DI SENSORI.............................................. 25
1.7.1
Introduzione a TinyOS.................................................................................. 27
1.7.2
Introduzione a NesC..................................................................................... 31
1.8
LE PIATTAFORME HARDWARE .................................................................... 33
1.8.1
Sensori per Mica2 ........................................................................................ 36
1.9
APPLICAZIONI .................................................................................................. 38
2. AFFIDABILITÀ NELLE RETI DI SENSORI SENZA CAVO ........ 42
2.1
IL CONCETTO DI AFFIDABILITA’ ................................................................. 42
2.2
AFFIDABILITA’ IN RETI DI SENSORI SENZA CAVO .................................. 44
2.2.1 Il problema della copertura ............................................................................ 46
2.3
AFFIDABILITA’: STATO DELL’ARTE............................................................ 49
2.4
AMBIENTI DI SIMULAZIONE ......................................................................... 51
2.4.1 Il Simulatore Tossim........................................................................................ 55
2.5
OSSERVAZIONI................................................................................................. 57
I
3. ALGORITMI PER LA RACCOLTA DATI AFFIDABILE ............. 59
3.1
CONSIDERAZIONI GENERALI ED OBIETTIVI ............................................. 59
3.2
ALGORITMI DI DATA GATHERING............................................................... 60
3.3
INTERAZIONE TRA I NODI: IL PROTOCOLLO MULTIHOP........................ 62
3.4
CLUSTERING IN UNA WSN ............................................................................. 65
3.5
CLUSTERING: STATO DELL’ARTE................................................................ 68
3.6
APPROCCIO PROPOSTO PER IL CLUSTERING ............................................ 72
3.6.1
Procedura di elezione del leader.................................................................. 74
3.7
ALGORITMI DI TRASPORTO AFFIDABILE.................................................. 75
3.8
APPROCCIO PROPOSTO PER IL TRASPORTO AFFIDABILE DELLE
MISURAZIONI ................................................................................................... 79
3.9
CLUSTERING E LEADER ELECTION ............................................................. 82
4. VALUTAZIONE COMPARATIVA DEGLI ALGORITMI ............. 85
4.1
OBIETTIVI .......................................................................................................... 85
4.2
DATA GATHERING BASE................................................................................ 86
4.3
DATA GATHERING AFFIDABILE................................................................... 91
4.4
DATA GATHERING CON CLUSTER ............................................................... 95
4.5
DATA GATHERING CON CLUSTERING E PROTOCOLLO AFFIDABILE 100
4.6
OVERLAY NETWORK .................................................................................... 103
CONCLUSIONI ................................................................................................................. 107
BIBLIOGRAFIA .................................................................................................................. 109
II
INDICE DELLE FIGURE
Figura 1.1: Architettura di una WSN ..................................................................................... 7
Figura 1.2: Componenti hardware di un nodo sensori............................................................ 8
Figura 1.3 : Modello a strati di TinyOS ............................................................................... 29
Figura 1.4: Rappresentazione di un componente TinyOS .................................................... 31
Figura 1.5: Mica2 ................................................................................................................. 33
Figura 1.6: Mica2DOT......................................................................................................... 34
Figura 1.7: Architettura del progetto Great Duck Island...................................................... 39
Figura 2.1: Architettura WSN per rilevazione incendio....................................................... 47
Figura 3.1: Scenario tipico di una rete di sensori wireless: i comandi sono inoltrati in
modalità broadcast mentre le misurazioni recapitate al nodo sink tramite
protocollo multihop ............................................................................................ 61
Figura 3.2: Configurazione di Multihop Router .................................................................. 63
Figura 3.3: Organizzazione in cluster della rete ................................................................... 66
Figura 3.4: Architettura protocollo RMST........................................................................... 77
Figura 3.5: Rete composta da otto dispositivi sensori .......................................................... 81
Figura 3.6: Rete organizzata in 3 cluster senza procedura di elezione di cluster-head......... 82
Figura 3.7: Organizzazione in cluster della rete con cluster-head........................................ 83
Figura 4.1: Architettura della rete in Tinyviz....................................................................... 87
Figura 4.2: Stralcio del file di configurazione della prima simulazione............................... 88
Figura 4.3: Evento metodo ReceiveMeasure attivato sul nodo sink alla ricezione della
misurazione ........................................................................................................ 89
Figura 4.4: Andamento % della ricezione delle misurazioni al crescere del numero di
nodi.......... .......................................................................................................... 90
Figura 4.5: Andamento % della ricezione delle misurazioni con utilizzo della plugin
TinySan .............................................................................................................. 91
Figura 4.6: Stralcio procedura seguita dal nodo sink per assicurarsi la ricezione delle
misurazioni da parte dei nodi sensori ................................................................ 92
Figura 4.7: Confronto percentuali copertura con uso protocollo affidabile e non
affidabile ............................................................................................................ 93
Figura 4.8: Andamento della vita media dei singoli sensori nel caso di utilizzo di un
protocollo di comunicazione affidabile confrontato con il caso di utilizzo
di un protocollo di tipo best-effort...................................................................... 94
Figura 4.9: Confronto consumo energetico dei singoli nodi ................................................ 94
Figura 4.10: Rete organizzata in cluster............................................................................... 96
Figura 4.11: Procedura di invio di un messaggio Master ..................................................... 97
Figura 4.12: Procedura seguita dai nodi alla ricezione di un master_msg ........................... 98
Figura 4.13: Confronto copertura con uso protocoolo affidabile e non affidabile ............... 99
Figura 4.14: Guadagno energetico con rete organizzata in cluster....................................... 99
Figura 4.15: Analisi comparativa degli algoritmi............................................................... 101
Figura 4.16: Elezione eseguita ciclicamente o all’esaurimento energetico di un nodo ...... 102
Figura 4.17: Overlay Network ........................................................................................... 104
Figura 4.18: Impatto del modulo radio sulla vita di un sensore ......................................... 105
III
INDICE DELLE TABELLE
Tabella 1-1:
Tabella 1-2:
Tabella 1-3:
Tabella 3-1:
Tabella 4-1:
Tabella 4-2:
Tabella 4-3:
Tabella 4-4:
Alcune caratteristiche della piattaforma Mica2 ............................................. 35
Tabella comparativa delle prestazioni di mica2 e mica 2 dot ........................ 35
Schede disponibili per piattaforma MICA ..................................................... 37
Schema riassuntivo dei protocolli di trasporto affidabili................................ 79
Caratteristiche della simulazione n°1.............................................................. 87
Caratteristiche della simulazione n°2.............................................................. 91
Caratteristiche della simulazione n°3 con rete organizzata in cluster ............. 95
Caratteristiche della simulazione n°4 con rete organizzata in cluster e uso
protocollo di recapito affidabile.................................................................... 100
IV
Ringraziamenti
Eccomi qua, alla fine di un percorso, al raggiungimento di un sogno tanto
desiderato. Molte sono le persone a cui vorrei esprimere tutta la mia
gratitudine.
Un grazie particolare al professore Stefano Russo, non solo per avermi dato
l’opportunità di far parte di un gruppo davvero fantastico, ma per i consigli
dati, molto importanti per la mia crescita professionale.
Grazie anche al professore Domenico Cotroneo, per la sua disponibilità e
cortesia nel chiarire ogni mio dubbio; grazie Marcello, i tuoi ottimi consigli
sono stati fondamentali per portare a termine il lavoro, grazie per tutto il
tempo che mi hai dedicato e per il tuo aiuto nella stesura di questa tesi;
grazie anche a te Lelio valido punto di confronto.
Grazie mamma, grazie papà per tutto il vostro sostegno e incoraggiamento a
dare sempre il massimo, per avermi dato la possibilità di proseguire i miei
studi nella serenità più totale, grazie per tutto ciò che avete fatto e che ora
non ricordo…vi voglio bene! Grazie Clemente, fratello e miglior amico, per
i tuoi consigli nei momenti in cui avevo bisogno di supporto…ti sono
riconoscente!
Un pensiero particolare va a tutti i miei familiari e anche a coloro i quali non
possono gioire con me in questo giorno.
Un dolcissimo grazie va ad Antonietta, mi hai “sopportato” nei momenti in
cui la tensione era alta e mi hai offerto un valido supporto morale: sei
importante!
Infine grazie a tutti i miei amici universitari e non (evito di fare l’elenco
perché sicuramente dimenticherei qualcuno), ognuno dei quali è stato
importante, a suo modo, nella mia vita.
Salvatore
V
Introduzione
Negli ultimi anni lo sviluppo delle tecnologie hardware ha reso possibile la
realizzazione di dispositivi sempre più potenti e miniaturizzati. Questo
progresso tecnologico, insieme a quello riguardante le comunicazioni senza
fili, ha costituito la base per una nuova prospettiva tecnologica di successo:
le reti di sensore senza filo (WSN).
La chiave del successo delle WSN è da ricercare nella loro versatilità, nel
basso costo dei nodi sensore e nelle loro alte doti di auto- riconfigurabilità.
Queste peculiarità hanno proiettato le WSN in diversi scenari applicativi,
alcuni dei quali con stringenti requisiti di affidabilità come le WSN per la
telemedicina e per alcune applicazioni militari.
Attualmente si sta indagando su come gestire in maniera più efficiente il
consumo energetico dei nodi sensori in modo da aumentare l’autonomia
della rete e in particolare come instradare in modo ottimo le comunicazioni
dal sensore all’utilizzatore, come raccoglierle, memorizzare e rappresentare
con la minima occupazione di memoria le informazioni raccolte.
In particolare, la necessità di avere algoritmi di raccolta dati affidabili,
energeticamente efficienti, risulta essere una esigenza molto diffusa in
quanto è alla base per il monitoraggio e/o controllo di fenomeni fisici per un
vasto arco temporale.
Questo lavoro di tesi ha come obiettivo la progettazione e valutazione di una
soluzione di compromesso (trade off) tra algoritmi energeticamente
efficienti e specifici requisiti di affidabilità come la consegna di una quantità
significativa di misurazioni e copertura dell’area da monitorare.
1
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Il lavoro si articola in quattro capitoli di cui nel seguito si fornisce una breve
descrizione.
Il capitolo 1 introduce brevemente alcuni concetti sulle Wireless Sensor
Networks. Vengono fornite alcune importanti definizioni e aspetti salienti
che le contraddistinguono. Si precede poi con la discussione dei parametri
da considerare nella progettazione e delle possibili applicazioni di una WSN
fornendo alcuni concetti di base per la comprensione del presente lavoro di
tesi.
Il capitolo 2 fornisce un’introduzione al concetto di affidabilità nell’ambito
delle reti di sensori senza cavo proponendo un’analisi di alcuni lavori
presenti in letteratura. Vengono inoltre presentati alcuni dei più importanti
ambienti di simulazione per WSN, soffermandosi sulle principali
caratteristiche di questi ultimi.
Il capitolo 3 propone una dettagliata analisi sulle strategie di clustering e sui
protocolli per la consegna affidabile di informazioni al nodo sink. Viene
inoltre proposto un approccio basato sull’utilizzo combinato di strategie di
clustering, procedure di leader election e protocolli affidabili per la raccolta
dati al fine di ottenere una soluzione che sia un buon compromesso tra un
consumo energetico dei nodi sensori e ben precisi requisiti di affidabilità
come la copertura dell’area da monitorare e la consegna di una quantità
significativa di misurazioni.
In conclusione il capitolo 4 fornisce una analisi comparativa degli algoritmi
proposti nel precedente capitolo al fine di valutarne gli effettivi benefici in
termini di aumento della autonomia dei nodi sensori. Viene inoltre proposta
una interessante via di sviluppo che, attraverso la ristrutturazione del
protocollo di routing e l’utilizzo di una piattaforma hardware che consenta
lo spegnimento selettivo (da codice) dei moduli radio, permette di ottenere
significativi vantaggi nell’autonomia della rete.
2
Capitolo 1
Reti di sensori senza cavo
1.1
LE WIRELESS SENSOR NETWORK
I rapidi progressi nella progettazione di sistemi microelettromeccanici
(MEMS) e a radio frequenze (RF) hanno favorito un repentino sviluppo di
“nodi sensori”, termine generico con cui si indica un insieme di dispositivi
estremamente versatili e dalle dimensioni generalmente ridotte, dotati della
capacità di comunicare a breve distanza. L’interconnessione di tali “nodi
sensori” per mezzo di tecnologie radio, unitamente allo sviluppo di una
architettura protocollare che consenta la cooperazione tra le diverse entità,
non fa altro che amplificare, in modo esponenziale, la capacità dei singoli
dispositivi dando il via allo sviluppo di un insieme vastissimo di nuove
applicazioni.
Questo concetto è alla base delle reti di sensori, note in letteratura con il
nome di Wireless Sensor Network (WSN) il cui obiettivo è l’utilizzo di un
numero abbastanza elevato di sensori, organizzati in un sistema intelligente
di gestione e di rilevazione. I benefici introdotti dalle WSN possono essere
riassunti in:
ƒ
Facile dislocazione: la copertura dei tradizionali macrosensori
cablati è limitata a certe aree a causa dei vincoli imposti dal costo e
3
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
dalla posa, rigorosamente ad opera di personale specializzato. In
contrasto, le WSNs possono contenere un grande numero di nodi
fisicamente separati. Anche se la copertura radio fornita da un
singolo nodo è ridotta, nodi densamente distribuiti possono lavorare
simultaneamente e in maniera cooperativa così da estendere la
copertura dell’intera rete; inoltre i sensori possono essere
letteralmente paracadutati in zone avverse [28];
ƒ
Ridondanza naturale: una densa dislocazione dei sensori senza filo
e la correlazione tra dati di nodi vicini in una specifica area rende le
WSN molto più flessibili rispetto alle classiche reti di sensori cablati.
In caso di fallimento di uno dei nodi, la rete riesce a reagire molto
bene grazie alla forte ridondanza spaziale che caratterizza le WSN
cosa che invece non sarebbe proponibile nelle reti di macrosensori.
Inoltre, la possibilità di poter raggiungere diversi nodi direttamente
(poiché posizionati in una area di raggio minore di quello di
trasmissione) garantisce una ridondanza anche nei possibili cammini
verso la destinazione
ƒ
Accuratezza: anche se i macrosensori possono fornire misure con
una maggiore precisione rispetto ad un microsensore, la grande
quantità di dati collezionati da una moltitudine di minuscoli sensori
riflette meglio le caratteristiche della realtà. Inoltre, adottando
appositi algoritmi di cooperazione tra nodi è possibile abbattere il
rumore di misura incorrelato e incrementare la componente comune.
ƒ
Costo: E’ previsto che le WSN siano molto meno costose rispetto
alle reti di macrosensori: basti pensare che il solo costo del cablaggio
sia per la trasmissione delle misure che per l’alimentazione dei
sensori, a volte raggiunge costi molto superiori a quelli dei soli nodi.
4
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
1.2
DIFFERENZA TRA RETI DI SENSORI E RETI AD
HOC
Le Wireless Sensor Network sono considerate come dei particolari casi di
reti ad hoc dette “Mobile Ad-hoc NETworks” (MANET) [2] però bisogna
evidenziare che seppur condividono molti elementi con esse molte sono
anche le differenze e specificità che hanno suscitato una particolare
attenzione della ricerca [3]. È importante quindi evidenziare le differenza
tra le comuni reti ad-hoc e le reti di sensori in termini di:
ƒ
SCALABILITA’: perché il numero di nodi che compongono una rete
di sensori può essere di diversi ordini di grandezza superiore rispetto
quello di una rete tradizionale, inoltre la densità dei nodi nelle
vicinanze del fenomeno da rilevare può risultare molto elevata;
ƒ
FLUSSO DI COMUNICAZIONE: in quanto nelle tradizionali WSN
il flusso è fortemente asimmetrico, ovvero tutti i nodi inviano i dati
raccolti all’interfaccia con l’utilizzatore, cosa che di solito non
accade nelle reti ad-hoc dove si prediligono le comunicazioni tra i
singoli nodi (peer-to-peer);
ƒ
CAPACITA’ ENERGETICHE E DI CALCOLO: che nelle WSN sono
estremamente limitate e che risultano essere un vincolo progettuale e
quindi da tenere debitamente in conto nella progettazione
dell’architettura della rete.
ƒ
FAULT-TOLERANCE: in quanto i nodi di una wireless sensor
network possono essere molto spesso soggetti a guasti.
ƒ
CENTRALITA’ DEI DATI: in quanto le informazioni originate da un
nodo generalmente non sono di fondamentale importanza per la
missione della rete: l’utente finale è più interessato ad avere una
5
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
visione d’insieme del sistema; quindi se un nodi si guasta è molto
probabile che ciò non influenzi significativamente le prestazioni
globali del sistema, grazie alla ridondanza caratteristica delle WSN.
1.3
ARCHITETTURA DELLA RETE
Una rete di sensori è un insieme, eventualmente eterogeneo, di nodi sensore
che forma una predeterminata topologia. I nodi sensore possono essere
equipaggiati con dispositivi in grado di rilevare una grande varietà di
condizioni ambientali, come temperatura, umidità, movimento dei veicoli,
luminosità, pressione, livello di rumore, presenza o assenza di certi tipi di
oggetti, grado di stress meccanico, valori istantanei di velocità, direzione e
dimensioni di un oggetto.
Gli elementi della rete sono collocati all’interno dell’area da monitorare, o
comunque nelle immediate vicinanze. Solitamente si associa ogni nodo a un
oggetto, una persona, un animale o un luogo determinante per lo studio del
fenomeno che si desidera osservare. Tipicamente non è prevista nessuna
infrastruttura fissa a cui si possano appoggiare i nodi, per questo di parla di
reti “ad-hoc”, che possono essere centralizzate se tutte le comunicazioni
sono dirette ad un unico nodo che elabora le informazioni raccolte, oppure
distribuite se i nodi hanno capacità e intelligenza sufficienti a elaborare i
dati autonomamente. La Figura 1.1 mostra come un messaggio attraversi la
rete attraverso un routing multihop da un nodo generico fino al sink, il nodo
dedicato alla raccolta de dati, a
cui può essere direttamente collegato
l’elaboratore dell’utente oppure un’interfaccia con altre WSN o altre reti
eterogenee (per esempio Internet).
6
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 1.1: Architettura di una WSN
È inoltre possibile prevedere più stazioni di raccolta dati intermedie,
eventualmente anche mobili, come ad esempio un utente dotato di PDA
(Personal Digital Assistant), oppure un aereo in volo.
Attraverso il percorso inverso l’utente, mediante l’applicazione di gestione
della rete, è in grado di inviare comandi ad ogni nodo della WSN. Se oltre
ad essere equipaggiati con sensori, i nodi dispongono anche di attuatori si
parla di Wireless Sensor and Actor Network (WSAN). A partire dalle
informazioni raccolte dal mondo che li circonda, i sensori sono in grado di
decidere come agire per modificare l’ambiente in cui si trovano tramite gli
attuatori. Non necessariamente tutti i nodi di una WSAN sono forniti di
attuatori che implicano un più alto consumo di energia e una maggior
complessità di rispondere rapidamente ad un evento per pilotare
tempestivamente l’attuatore.
7
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
1.4
DESCRIZIONE DEI NODI SENSORI
Esistono diverse piattaforme hardware di nodi per WSN, in Figura 1.2 viene
mostrato lo schema generale nel quale è possibile rintracciare cinque
elementi fondamentali: uno o più sensori della grandezza fisica da rilevare
(trasduttore), un trasmettitore per la comunicazione e lo scambio dei dati
(radio), un'unità di elaborazione digitale della grandezza misurata
che
sovrintende anche alla comunicazione radio (unità di elaborazione e
controllo), un sistema di alimentazione autonomo (power management) e,
in infine, uno o più attuatori.
1.4.1 Sensing Module
Comunemente col termine sensore si indica l’intero nodo di una WSN. In
questo contesto però indicheremo con il termine sensore l’hardware di cui è
dotato un nodo per trasformare la grandezza fisica acquisita in un segnale
elettrico che possa essere elaborato (trasduttore).
Un nodo può disporre di più sensori, anche di grandezze fisiche diverse,
che sono strettamente legate alla specifica applicazione; si possono avere ad
esempio sensori di luminosità, pressione, temperatura, prossimità. La
maggior parte dei sensori, prevede inoltre la presenza di un blocco di
conversione analogica-digitale (ADC, Analog to Digital Converter), da
Figura 1.2: Componenti hardware di un nodo sensori
8
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
utilizzare durante la fase di acquisizione del segnale. Il tipo di elaborazione
da effettuare dipende dalla grandezza fisica rilevata e influisce direttamente
sui consumi: si pensi ad esempio di dover
digitalizzare un particolare
segnale analogico: la rapidità con cui varia determina
la velocità di
campionamento necessaria per acquisirlo correttamente, mentre la
sua
dinamica e la precisione con cui lo si vuol rappresentare stabiliscono il
numero di bit della parola associata ad ogni campione. All’aumentare della
velocità di campionamento e del numero di bit del convertitore analogico
digitale, si ha un incremento dei consumi.
1.4.2 Unità di elaborazione
La presenza di una CPU permette di dotare il nodo delle capacità
elaborative per gestire le comunicazioni e le grandezze misurate. Il ruolo
della CPU può essere svolto da diverse tipologie di circuiti
logici.
Comunemente la scelta ricade su un microcontrollore a basso consumo, ma
è possibile impiegare anche un FPGA (Field Programmable Gate Array), un
DSP (Digital Signal Processing) o un ASIC(Application Specific Integrated
Circuit). Un compito tipico del microprocessore in queste piattaforme è la
verifica dell’effettiva necessità di utilizzare le risorse: per preservare la
carica della batteria il nodo deve disattivare tutti i dispositivi come chip
radio, timer, oscillatori, ogni volta che questi non sono indispensabili per le
attività del nodo stesso. La gestione dei tempi e delle modalità del passaggio
dallo stato a basso consumo a quello di attività dei vari componenti è
affidata al microprocessore.
Il microprocessore è spesso integrato con alcuni blocchi di memoria ROM e
RAM utilizzati per ospitare il codice eseguibile del sistema operativo e
dell’applicazione, nonché i dati acquisiti dai
sensori ed elaborati
dall’applicazione. La gestione e l’utilizzo delle memorie è una fonte di
consumo energetico, pertanto i blocchi di memoria integrati hanno capacità
9
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
ridotte, limitate a poche decine di kbyte e la loro dimensione, in termini di
capacità di immagazzinare dati, non va sovrastimata. Alcune piattaforme,
tuttavia, possono essere dotate di memorie Flash aggiuntive, connesse al
microprocessore
per mezzo di interfacce seriali. Queste memorie,
solitamente di capacità superiore rispetto alle memorie integrate con il
microprocessore, possono essere utilizzate per contenere parametri per la
configurazione del nodo o altri dati. Chiaramente, l’utilizzo delle memorie
aggiuntive aumenta la potenzialità del nodo, ma influisce negativamente,
come già detto, sui consumi energetici.
1.4.3 Unità di comunicazione
Per garantire la connettività tra i nodi di una WSN è possibile adottare
diverse strategie. Tipicamente la connessione è realizzata via radio, anche se
per alcune particolari applicazioni sono disponibili soluzioni alternative che
impieghino ultrasuoni o comunicazioni ottiche. Solitamente tra tutti i
componenti del nodo, il chip radio è il dispositivo che consuma la maggior
parte dell'energia. Per ridurre il costo e il consumo energetico dei nodi, si
utilizzano tipicamente modulazioni ben consolidate e di bassa complessità,
a discapito della capacità trasmissiva che è spesso limitata a qualche decina
di kbit/s. Per limitare ulteriormente il costo finale
del dispositivo, la
modulazione radio avviene normalmente nelle bande comprese tra gli 868870 MHz o nelle bande ISM (Industrial ScientificMedical) attorno ai 900
MHz e ai 2,4 GHz, per le quali non è richiesta licenza governativa.
1.4.4 Alimentazione
Data l’impossibilità di usufruire di una rete di distribuzione dell’energia, è
necessario che ciascun elemento della WSN sia equipaggiato con un sistema
autonomo di alimentazione. Attualmente l’unica soluzione diffusa è data
10
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
dall’utilizzo di pile elettrochimiche, il cui sviluppo tecnologico non ha visto
notevoli incrementi nell’ultimo ventennio; ecco perchè la progettazione
delle reti di sensori è centrata sul risparmio energetico. Fonti di energia
alternative sono argomento di ricerca ma, come riportato in Tab. 1.1, al
momento non sono ancora in grado di rimpiazzare l’alimentazione a
batterie; l’unica strategia applicabile per ora è lo spegnimento selettivo dei
nodi per la maggior parte del tempo, in modo da ridurre il consumo di
potenza medio. Promettente è la combinazione data da energia solare ed
elettrochimica, in cui l’energia elettrica prodotta dalle celle fotovoltaiche
esposte alla luce del sole, va a ricaricare una batteria tampone che il nodo
utilizza in assenza di luce.
1.5
PARAMETRI DI PROGETTO
Le WSN sono state concepite al fine di rilevare delle informazioni
dall’ambiente circostante e di inviarle presso un centro specializzato che
elabori queste informazioni. Le reti di sensori wireless possono essere
dislocate anche in ambienti particolarmente ostili o comunque in ambienti in
Sorgente di energia
Trasduttore
Potenza
Conversione diretta da
camminata
Piezoelettrico
5W
Solare
Cella fotovoltaica
20mW
Campo magnetico
Induttore
1.5 mW
Vibrazioni
Bobina mobile
400 mW
Vibrazioni ad alta
frequenza
Campo a radio
frequenza
MEMS e bobina
mobile
100 mW
Antenna 5 mW
-
Svantaggi
Elevato rumore E.M. ed
elevato ingombro
Utilizzabile solo durante
le ore del giorno e
abbastanza costosa
Scarsa potenza erogabile
Necessità di vibrazioni per
essere attivato
Necessità di vibrazioni per
essere attivato
Scarsa potenza erogabile
Tabella 4-1: Fonti energetiche alternative
11
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
cui un intervento di manutenzione da parte dell’uomo potrebbe risultare
impossibile (si pensi ad esempio ad una dislocazione di nodi in un bosco
attraverso l’ausilio di un aereo).
Questo primo esempio ci fa già comprendere come le caratteristiche di una
rete di sensori siano strettamente legate al reale impiego che se ne deve fare,
infatti ogni specifica applicazione richiede che la WSN abbia delle proprietà
particolari; questo naturalmente limita fortemente la portabilità e riusabilità
delle rete in contesti differenti (al contrario delle tradizionali reti ad-hoc) e
si paga anche in termini di complessità di progettazione e tempi di sviluppo.
Gli aspetti da considerare sono molteplici [3], di seguito si prenderanno in
considerazione i principali parametri da tenere in considerazione nella fase
di progettazione di una Wireless Sensor Network.
1.5.1 Consumo energetico
La vita di un sensore è legata principalmente alla durata della batteria.
Inoltre, la riserva di energia posseduta da un sensore risulta essere
estremamente ridotta, e molto spesso difficile da rifornire. Ciò implica
l’introduzione di appositi meccanismi che preservino la durata delle batterie,
se possibile, fino ad alcuni anni, massimizzando l’invio delle informazioni
dall’ambiente in cui si è scelto di installare la WSN. In questa logica lo
scopo principale da perseguire, che del resto è una vera e propria sfida
tecnologica per questi sistemi, è la riduzione del consumo di potenza. La
richiesta di potenza va quindi minimizzata ad ogni livello di sviluppo, sia a
livello hardware che software al fine di ottenere le prestazioni energetiche
desiderate. Il consumo energetico può essere suddiviso in due punti
fondamentali: comunicazione ed elaborazione dati in tempo reale.
•
COMUNICAZIONE:
Un sensore spende la maggior parte dell’energia nelle fasi di
comunicazione, che comprendono sia la trasmissione che la ricezione dei
12
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
dati. A corto raggio, trasmettere e ricevere dati comporta pressoché lo stesso
consumo di potenza, ma in generale è la trasmissione di dati che necessita
maggiore energia. In tale caso non si deve considerare solo il consumo di
potenza attiva, ma anche la potenza di “avvio” della trasmissione, in quanto
questa fase ha dei tempi non trascurabili. Basti pensare che non appena le
dimensioni del pacchetto da trasmettere diminuiscono, tale potenza tende
addirittura a dominare sulla potenza attiva. Di conseguenza, non si può
considerare un trasmettitore solo nella fase ON o OFF, perchè una buona
parte di potenza viene spesa nel momento in cui si accende. La potenza Pc
spesa da una radio può essere sintetizzata dalla seguente formula:
PC = NT [PT (Ton + Tst ) + Pout (Ton )] + NR [PR (Ron + Rst )]
dove PT e PR rappresentano la potenza consumata nel trasmettere e ricevere,
Pout la potenza di uscita dal trasmettitore, Ton e Ron il tempo in cui il
trasmettitore e il ricevitore sono nella fase ON, Tst e Rst il tempo in cui il
trasmettitore e ricevitore sono nella fase di avvio e NT NR il tempo in cui il
trasmettitore e il ricevitore è attivo per unità di tempo. Tipicamente, per
trasmettitori a basso consumo di potenza, PT e PR assumono valori
dell’ordine dei 20 dBm e Pout attorno agli 0 dBm. In conclusione, il
progetto di una rete di sensori e la scelta del protocollo utilizzato sono
influenzati da considerazioni sulla potenza.
•
ELABORAZIONE DATI IN TEMPO REALE
Nonostante l’energia spesa nell’elaborazione dei dati sia significativamente
inferiore a quella spesa per la loro trasmissione, è comunque un’ aspetto
cruciale ridurre al minimo l’elaborazione dei dati sia per risparmiare
energia, sia per abbassare il tempo in cui i sensori processano i dati. Ogni
nodo deve perciò essere costruito in modo da avere varie abilità
computazionali ed essere in grado di interagire con i sensori vicini.
13
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Studi specifici, effettuati su CMOS usati in regime digitale, hanno portato
alla seguente formula che permette di calcolare approssimativamente la
potenza Pp spesa nell’elaborazione dei dati:
Pp = CV dd f + V dd I 0 exp(
2
V dd
VT )
n
dove C è la capacità totale del carico pilotato dall’elettronica, Vdd è il
voltaggio di alimentazione ed f la frequenza media di commutazione. Da
notare inoltre che il secondo termine indica la potenza spesa a causa della
dispersione di corrente.
1.5.2 Costo
È indispensabile che l’utilizzo della WSN sia economicamente conveniente
rispetto a soluzioni alternative; d’altro canto solo una produzione di massa
dei sensori può abbatterne i costi e incentivarne l’utilizzo. La speranza è che
entro pochi anni il costo di un nodo non superi il dollaro, ma attualmente si
è ancora lontani da questa previsione: infatti il costo del Bluetooth, il
dispositivo radio attualmente più economico, si aggira intorno ai cinque
dollari. Si deve poi considerare che un nodo possa disporre anche di altre
dotazioni come GPS (Global Positioning System), alimentatori e attuatori
che ne fanno aumentare il costo. Piuttosto di sostenere costi di
manutenzione talvolta si preferisce smettere di utilizzare i nodi che si
guastano, il che risulta economicamente più conveniente se ciò non limita
eccessivamente la connettività.
1.5.3 Connettività
La capacità dei nodi di comunicare fra loro definisce la connettività. Una
rete in cui ogni nodo può comunicare con qualunque altro, anche attraverso
multihop (non direttamente ma mediante altri nodi che fungono da ponte), si
14
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
dice connessa. In una WSN, tuttavia, questo tipo di connettività non è
garantito, in quanto i nodi passano lunghi periodi in stato di inattività (sleep)
al fine di risparmiare energia, risultando raggiungibili solo in determinati
intervalli di tempo. Inoltre, alcuni nodi possono risultare permanentemente
disconnessi a causa di un guasto o esaurimento delle riserve energetiche. In
questo caso si ha una rete partizionata
e si parla di connettività a
intermittenza che deve essere attentamente considerata nella progettazione
dei protocolli di comunicazione e dei meccanismi di inoltro dei dati che
devono quindi risultare robusti al partizionamento temporaneo e alle
variazioni topologiche della rete e alla perdita dei dati. Infine se un nodo
resta per la maggior parte del tempo isolato e può comunicare solo
raramente si parla di comunicazione sporadica.
1.5.4
Topologia della rete
La topologia di una rete di sensori è soggetta a continui cambiamenti dovuti
a fattori casuali e a imprevisti, come possono essere danneggiamento ed
esaurimento energetico. Inoltre tale topologia varia anche per il fatto che
non tutti i nodi sono funzionanti nello stesso istante, ma alcuni sono tenuti
in uno stato di basso consumo di energia. In tale stato il transceiver del nodo
non è attivo e questo si traduce da un lato in un certo risparmio di energia,
dall’altro nel fatto che il sensore non è connesso alla rete. Questo comporta
una diminuzione della capacità di copertura e della connettività della rete. Il
compromesso tra questi due parametri e il risparmio energetico è noto come
topology management. L’evoluzione della topologia di una rete si può
riassumere in tre fasi:
1) Schieramento:
i
nodi
sono
distribuiti
casualmente
nell’ambiente (anche se possono essere presenti tecniche di
15
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
posizionamento studiate per ridurre le interferenze o per
avvantaggiare l’auto-organizzazione dei nodi);
2) Post-schieramento: la topologia della rete cambia a causa dello
spostamento, della distruzione o dell’esaurimento dell’energia
dei nodi;
3) Rischieramento: i nodi non più funzionanti vengono sostituiti
da altri.
1.5.5
Dimensioni e posizionamento dei nodi
Per poter essere posizionati negli ambienti più disparati è necessario che i
nodi siano di piccole dimensioni e leggeri, cosa non semplice per la
presenza di componenti non facilmente integrabili come batteria e antenna. I
nodi inoltre, possono essere installati in posizioni specifiche, o possono
essere distribuiti in maniera casuale a ricoprire tutto un territorio. Per varie
ragioni i nodi possono essere rimpiazzati, o se ne possono aggiungere altri
influenzando così la localizzazione, la densità e la topologia della rete.
Riguardo la densità dei nodi viene definita in modi diversi: in termini di
numero di nodi nell’area considerata oppure come rapporto fra il numero di
nodi all’interno dell’intera rete e la superficie della regione su cui è
distribuita la rete. La dimensione della rete influenza l’affidabilità e
l’accuratezza degli algoritmi di elaborazione.
1.5.6
Mobilità
In alcuni casi tutti i sensori della rete, o solo alcuni, possono spostarsi o
essere parte di un dispositivo mobile: si parla in questo caso di MANET
(Mobile Ad-hoc NETwork). In genere le WSN sono caratterizzate da un
basso grado di mobilità. Velocità di spostamento e grado di mobilità
influiscono sulla progettazione dei protocolli, in particolar modo quelli
distribuiti.
16
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
1.5.7
Scalabilità
La scalabilità indica la capacità che ha una rete di garantire un degrado
lineare delle prestazioni al crescere del numero di nodi di cui è composta.
Per analizzare correttamente questo parametro si deve fare riferimento alla
densità dei nodi nella rete:
μ ( R) =
NπR 2
A
dove N rappresenta il numero dei nodi, R il raggio di trasmissione, A la
superficie in cui la rete opera, e μ(R) rappresenta il numero medio di nodi
che si trovano entro la portata di un sensore.
1.5.8
Sicurezza
Una WSN può essere soggetta a molteplici attacchi, quali:
ƒ
appropriamento delle informazioni scambiate fra i nodi, da parte
di un ascoltatore esterno in grado di ricevere le comunicazioni
scambiate non crittografate;
ƒ sostituzione di un nodo, che dopo essere stato sottratto alla rete,
manomesso e reinserito può rendere accessibile a un ascoltatore
esterno le chiavi di crittografia di messaggi di livello più alto;
ƒ inserimento di un nodo fasullo, non appartenente alla rete ma che
la rete stessa invece riconosce come proprio e che può inoltrare
false informazioni nella WSN o bloccare il passaggio di
informazioni autentiche;
ƒ nodo malfunzionante, che può immettere nella rete informazioni
non corrette che si propagano nella WSN;
ƒ corruzione del messaggio, può avvenire se un intruso si inserisce
nella comunicazione fra i nodi tentando di danneggiare
l’integrità del messaggio, modificandolo;
17
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
ƒ negazione del servizio, avviene in diversi modi ad esempio
creando continue collisioni nelle trasmissioni radio, riducendo le
risorse della rete o alterando il routing;
ƒ analisi del traffico, attraverso lo studio della parte di dati
trasmessi senza crittografia, consente di rendere inutilizzabile la
rete.
1.5.9
Affidabilità
Nell’ambito specifico delle reti di sensori senza cavo il concetto di
affidabilità si formalizza come la capacità che deve avere una rete di
conservare le proprie funzionalità indipendentemente dall’eventuale guasto
di qualche sensore o semplicemente da una trasmissione fallita. Attualmente
il requisito di affidabilità, in una WSN, ha assunto un ruolo di primo livello
e influenza non poco il progetto dell’intera architettura del sistema, uno
studio approfondito sarà portato avanti nel capitolo 2.
1.6
PROTOCOLLI DI COMUNICAZIONE
I protocolli di comunicazione rappresentano una delle aree di ricerca più
attive nell'ambito delle reti di sensori. I maggiori sforzi si sono concentrati
nella
realizzazione di protocolli MAC efficienti dal punto di vista
energetico e di protocolli di routing che offrano soluzioni efficaci per tutte
le esigenze. Dei livelli di cui è composto il modello ISO/OSI, quelli
coinvolti nella progettazione di protocolli di rete per una rete di sensori
sono il livello fisico, il livello data-link ed il livello di rete, di cui ne daremo
una breve descrizione nei successivi sottoparagrafi.
1.6.1 Livello Fisico
18
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Il livello fisico si occupa di impostare la frequenza, di generare la portante e
del riconoscimento del segnale e infine della modulazione e codifica dei
dati. Ma rispetto alle classiche trasmissioni radio, in questo caso il
principale problema è come trasmettere i dati spendendo la quantità minima
di energia, tenendo conto di tutti i costi collegati (overhead, etc).
Molti lavori si concentrano sulla modulazione efficiente del segnale dal
punto di vista energetico [4] [5].
1.6.2
Livello data-link
Il livello data-link è responsabile della multiplazione dei flussi di dati, del
riconoscimento dei frame, del controllo dell'accesso al mezzo e del controllo
dell'errore. Di questi aspetti forse il più interessante è la progettazione del
protocollo MAC [6].
Gli obiettivi del MAC sono i seguenti:
ƒ
Ridurre
le
collisioni.
Se
due
o
più
nodi
trasmettono
contemporaneamente sullo stesso canale radio, i loro messaggi
interferiscono reciprocamente e in ricezione non è possibile
ricostruirli; si deve quindi programmare una ritrasmissione in istanti
differenti
per
tentare
nuovamente
l’inoltro
del
messaggio.
Ritrasmettere più volte lo stesso pacchetto comporta un notevole
dispendio d’energia che, come già esposto, i nodi devono evitare. A
tal fine può essere conveniente suddividere il canale in più
sottocanali,utilizzabili contemporaneamente per ridurre i conflitti di
accesso al mezzo; le soluzioni più diffuse sfruttano la diversità
temporale (TDMA, Time Division Multiple Access), in frequenza
(FDMA, Frequency Division Multiple Access) di codifica (CDMA,
Code Division Multiple Access) e con ascolto della portante
(CSMA/CA, Carrier Sense Multiple Access / collision avoidance).
Dato l’elevato numero di nodi che compongono una rete non è
19
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
possibile dedicare un sottocanale per ogni
collegamento punto-
punto, le risorse per la comunicazione devono essere quindi
riallocabili più volte all’interno della rete. Come vedremo, questo
aspetto sarà un limite progettuale non di poco conto per la scelta di
algoritmi di comunicazione affidabili.
ƒ
Utilizzare algoritmi adattativi per il supporto della mobilità. Alcune
applicazioni richiedono di poter gestire in modo semplice nodi che si
muovono all’interno della rete; tale problematica può essere trattata
nella ipotesi semplificativa di nodi a bassa mobilità, dato che le
condizioni
d’impiego delle reti di sensori non richiedono di
effettuare rapidi
spostamenti. Un nodo in movimento può aver
bisogno della riallocazione dinamica dei canali se questi sono già
utilizzati dai nodi a cui si avvicina; inoltre anche a questi ultimi, per
lo stesso motivo, può essere necessario cambiare i canali riservati.
Per poter effettuare queste riconfigurazioni della rete, i nodi fissi
nelle vicinanze del nodo mobile, devono essere sempre attivi, o
comunque risvegliabili con un segnale di wake up, in modo da
creare una zona limitrofa al nodo mobile che gli garantisca in ogni
momento la connettività.
ƒ
Ridurre l’overhead. Oltre alle informazioni legate all’applicazione,
in ogni pacchetto i nodi inseriscono dati necessari alla gestione della
comunicazione, pur essendo indispensabili questi bit aggiuntivi
comportano un dispendio di energia. Per ridurre i consumi e
aumentare la
durata dei nodi, è necessario limitare il numero di
informazioni scambiate senza compromettere le funzionalità della
rete; ad esempio si diminuisce il numero di pacchetti riservati
esclusivamente alla gestione radio, i quali sono privi del campo dati
(payload) e quindi determinano uno spreco di risorse.
20
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
ƒ
Tenere spento il più a lungo possibile il chip radio. Dato che la radio
è il componente col maggior consumo energetico, è evidente che
appena non è più richiesto il suo utilizzo essa sia disattivata.
1.6.3
Livello di rete
Compito del livello di rete è gestire l’indirizzamento e l’instradamento dei
messaggi.
Tenendo presente che l’obiettivo di una WSN è in maggior parte di
monitorare e tenere sotto controllo un fenomeno fisico, attraverso
rilevazioni periodiche effettuate dai sensori, se questi dati venissero
instradati nella rete senza alcun accorgimento, si verificherebbe un traffico
elevato, con informazioni ripetitive ed inutili, che provocherebbero
congestioni e soprattutto una drastica riduzione del tempo di vita della rete.
Al fine di evitare questo problema urge una attenta progettazione e scelta
del particolare algoritmo di routing da utilizzare.
Lo scambio d’informazioni fra nodi remoti, ovvero non nel reciproco raggio
di copertura, avviene attraverso il transito per altri nodi intermedi finchè il
messaggio non giunge a destinazione; si parla in questo caso di percorso
multihop. Questo meccanismo richiede in genere la conoscenza della
posizione relativa tra i nodi che può essere memorizzata in vari modi,
definendo tipologie di protocolli differenti:
ƒ
Proattiva (Proactive). Durante la fase di inizializzazione della rete
si
memorizzano in tabelle dette Look Up Table (LUT) tutti i
cammini a peso minimo fra ogni coppia di nodi. La creazione di
queste tabelle è un’operazione che richiede molta energia poiché, per
realizzarla tutti i nodi della WSN devono essere attivi e scambiare
messaggi tra loro, per questo le tabelle vengono successivamente
aggiornate solo in caso di malfunzionamento di qualche nodo. Le
21
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
dimensioni di queste tabelle crescono rapidamente all’aumentare del
numero dei nodi e la loro memorizzazione richiede quindi memorie
di grandi dimensioni, che implicano un considerevole consumo di
energia. Questi protocolli cercano di mantenere lo stato delle proprie
tabelle il più aggiornato possibile, anche in mancanza di un effettivo
utilizzo della rete. Esempi di questa classe di protocolli di routing
sono:
•
DSDV (Highly Dynamic Destination-Sequenced Distance
Vector routing protocol);
ƒ
•
HSLS (Hazy Sighted Link State routing protocol);
•
OLSR (Optimized Link State Routing Protocol);
•
STAR (Source Tree Adaptive routing protocol).
Reattiva (Reactive). Il cammino a costo minimo viene individuato
solamente quando è realmente necessario, questo consente di non
dover memorizzare grandi tabelle poiché il percorso ottimale viene
selezionato dinamicamente tramite l’invio di dati. La ricerca del
cammino migliore impiega la radio per un tempo considerevole, il
che influisce negativamente sui consumi di potenza ma permette di
non dover impiegare memorie di grandi dimensioni. Un esempio di
questa classe di protocolli di routing può essere trovato in [7] dove
Karp et al. presentano il Greedy Perimeter Stateless Routing
(GPSR), un nuovo protocollo di routing per reti wireless a
datagrammi. In GPSR viene utilizzata la posizione del router e della
destinazione dei pacchetti per decidere il percorso di inoltro. Le
uniche informazioni utilizzate riguardano i router e i vicini nella
topologia della rete.
ƒ
Tecniche ibride. L’utilizzo combinato delle due tecniche precedenti,
permette la determinazione del cammino minimo nel momento di
22
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
effettivo bisogno quando si devono trasmettere messaggi, ma è poi
possibile memorizzare il percorso in LUT di dimensioni limitate per
un riutilizzo futuro. In questo modo si dispone dei vantaggi di
entrambe le strategie, riducendo le perdite di prestazioni tipiche dei
singoli metodi considerati separatamente. Esempi di tecniche ibride
per il routing possono essere trovati in tutti gli algoritmi Ant [8]. Gli
algoritmi Ant sono una classe di agenti basati su algoritmi di routing
che modellano il comportamento delle formiche. Le formiche sono,
infatti, capaci di trovare il percorso più breve tra il formicaio e un
punto del terreno in cui vi sia del cibo. L'aspetto interessante e
curioso è che sono in grado di farlo senza informazioni visive (le
formiche di molte specie sono infatti cieche), ma utilizzando segnali
"odorosi". Quando una formica ha trovato del cibo, ritorna al
formicaio depositando sul terreno una certa quantità di una sostanza
chimica detta feromone. La direzione del cammino di una formica
dipende dalla quantità di feromone che essa percepisce: dove la
concentrazione è più forte, è più probabile che la formica si diriga.
Nel tempo le tracce di feromone sul terreno evaporano ed,
eventualmente, sono rinforzate dal passaggio di altre formiche. Ora
entra in gioco un meccanismo molto importante chiamato
retroazione positiva: più formiche scelgono un percorso, più forte
sarà la concentrazione di feromone e quindi ancora più formiche
saranno richiamate sullo stesso percorso. Perciò, dopo una prima
fase di transitorio in cui le formiche scelgono direzioni diverse, si
arriva ad una situazione stazionaria in cui la maggior parte delle
formiche segue uno stesso percorso. Siccome il feromone evapora
nel tempo, il percorso più breve sarà quello scelto alla fine dal
"sistema formiche".
23
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Analogamente gli agenti viaggiano nella rete codificando la qualità
del cammino visitato e lasciando questa informazione nell’ultimo
nodo attraversato. In ogni nodo un agente sceglie la prossima
destinazione in
maniera probabilistica ma comunque polarizzata
verso il migliore dei cammini già noti. Questa tecnica risulta essere
molto veloce per l’esplorazione di buoni percorsi e inoltre in questo
modo si riescono facilmente a trovare buoni cammini alternativi in
caso del fallimento di uno dei nodi sull’albero di routing, proprio
perchè ad ogni nodo l’agente cerca sempre un cammino intorno alla
precedente soluzione (buona).
Per completezza riportiamo di seguito anche altri protocolli di routing non
basati sul paradigma del multihop:
9 FLOODING: è una vecchia tecnica dove un nodo che riceve
dati o pacchetti li ritrasmette in modo broadcast (a meno che
il pacchetto non abbia raggiunto un numero massimo di hop
o che il nodo stesso sia la destinazione del pacchetto). Il
flooding [3] è una tecnica reattiva e che non richiede un
mantenimento della topologia ma presenta alcuni problemi
che vanno risolti in fase di implementazione:
i. Implosion: situazione in cui i duplicati di un
messaggio siano inviati allo stesso nodo;
ii. Overlap: quando due nodi condividono la stessa
regione di osservazione entrambi potrebbero rilevare
gli stessi stimoli e quindi i nodi vicini ricevono
messaggi duplicati;
iii. Resource Blindness: questo protocollo non tiene
conto della risorsa energia disponibile;
9 GOSSIPPING: è una variante del flooding solo che i nodi
non usano il broadcast ma inviano i pacchetti ad un solo nodo
24
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
selezionato in modo random tra tutti i vicini [3]. Così si evita
il problema di implosione ma si impiega molto più tempo per
propagare un messaggio a tutti i nodi.
9 ENERGY EFFICIENT ROUTE: il percorso che viene
seguito è quello più efficiente dal punto di vista energetico
9 LEACH (Low Energy Adaptive Clustering Hierarchy): è un
protocollo basato sul clustering [10] che minimizza la
dissipazione di energia in una rete di sensori. Lo scopo di
questo protocollo è quello di scegliere in maniera random
alcuni nodi ed eleggerli a capo-cluster. Gli altri nodi, invece
si associano ad un cluster in modo da minimizzare la
dissipazione di energia. In questo modo il capo cluster riceve
ed aggrega i dati dei nodi appartenenti al cluster prima di
inviare questi alla stazione base. Dopo un certo periodo di
tempo la rete entra nuovamente in fase di setup e inizia
nuovamente la fase di selezione dei capo- cluster.
1.7
I SISTEMI OPERATIVI E LE RETI DI SENSORI
Le caratteristiche delle reti di sensori in relazione alla progettazione di un
sistema operativo devono essere adeguatamente tenute in considerazione.
Uno degli aspetti più evidenti delle reti di sensori sono le ridotte dimensioni
della piattaforma hardware e la scarsa disponibilità di energia. Questi fattori
influiscono sulla capacità di elaborazione del sistema, sulla quantità di
informazioni che è possibile scambiare e sulla capacità di comunicare con
l'esterno. Il software sviluppato per le reti di sensori dovrà essere perciò
molto semplice, per evitare operazioni inutili, e poco ingombrante in termini
di occupazione di memoria.
25
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Le reti di sensori sono soggette a continue
sollecitazioni. Si pensi ad
esempio alla quantità di pacchetti che ogni nodo deve trattare, sia perchè ha
la necessità di inviare le informazioni raccolte, sia perchè la rete comunica
secondo un protocollo multi-hop. Inoltre l'ambiente esterno deve essere
continuamente monitorato e la rete, per poter garantite i servizi essenziali,
deve continuamente scambiarsi delle informazioni di “servizio" (si pensi al
problema della mobilità o a quello della sincronizzazione temporale). In
pratica il sistema deve gestire una quantità non trascurabile di eventi nel
modo più veloce possibile, per evitare di perdere informazioni preziose,
però il livello di parallelismo insito in questo tipo di sistemi è molto basso
rispetto ai sistemi convenzionali. Questo è dovuto principalmente alle
limitazioni fisiche dei nodi (bassa capacità di elaborazione, poca memoria,
etc.) quindi si preferisce sfruttare
le poche risorse per effettuare le
operazioni essenziali. Come abbiamo già visto, le reti di sensori possono
essere utilizzate in numerose applicazioni, differenti tra loro. Queste
richiedono in molti casi dell'hardware dedicato e quindi sono necessarie
delle reimplementazioni dello stesso software per adeguarlo ai diversi
dispositivi. Tuttavia, se il software viene sviluppato seguendo il criterio di
modularità,
non
sono
necessarie
complete
reimplementazioni
di
un'applicazione ma dovrebbe essere sufficiente sostituire alcuni moduli per
ottenere il medesimo risultato. Lo stesso problema sorge quando ad esempio
si vuole sostituire un protocollo all'interno di un applicazione. In generale
quindi, si dovrebbe progettare un sistema operativo in grado di adattarsi
facilmente a tutti i cambiamenti tecnologici, sia hardware che software. I
nodi in alcune applicazioni si trovano a lavorare in ambienti critici che ne
potrebbero alterare il funzionamento. Questi possono guastarsi o rimanere
bloccati quindi è necessario sviluppare applicazioni tolleranti ai guasti.
Anche il sistema operativo deve fare la sua parte, cioè deve supportare
26
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
eventuali guasti dei dispositivi e favorire lo sviluppo di
applicazioni
affidabili e distribuite, in conclusione deve garantire operazioni robuste.
Per completezza ricordiamo che in letteratura si distinguono principalmente
due approcci allo sviluppo di sistemi operativi per reti di sensori senza cavo:
o
Sviluppare un sistema i cui componenti vengono compilati assieme
all'applicazione (esempio TinyOs).
o
Sviluppare un sistema che includa i tradizionali strati software dei
sistemi general purpose in versione ridotta (esempio MANTIS [23])
Riguardo il primo approccio, questo, di fatto, consente che una sola
applicazione sia in esecuzione in un dato momento; tuttavia tale sistema
permette di avere bassissimi consumi. Lo svantaggio però derivante da tale
approccio è la limitata versalità e i seri vincoli di riconfigurabilità
dell'applicazione.
Riguardo invece il secondo approccio, risulta in questo caso difficile tenere i
consumi e le risorse impiegate sotto controllo, ma si guadagna in versatilità,
potendo eseguire più applicazioni contemporaneamente.
1.7.1
Introduzione a TinyOS
TinyOS è un sistema operativo open-source, sviluppato dalla University of
California at Berkeley. Data la possibilità di modificare il codice, questo
sistema operativo è diventato la piattaforma di sviluppo per ogni soluzione
proposta nel campo delle reti di sensori. In effetti grossi contributi sono
stati forniti dalla comunità di sviluppatori, lo testimonia la lunga lista di
progetti attivi relativi a
tutti campi della ricerca, da protocolli per
l'instradamento dei pacchetti alla localizzazione, dalla realizzazione di un
interfaccia grafica per lo sviluppo delle
27
applicazioni all'estensione del
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
compilatore ncc per il supporto di nuove piattaforme hardware (come la
piattaforma 8051) 1 .
TinyOS è stato progettato principalmente per le reti di sensori ed adotta
soluzioni molto semplici ed
efficienti, al fine di ridurre al massimo i
consumi di energia. Infatti TinyOS non possiede un nucleo ma permette
l'accesso diretto all'hardware, inoltre sparisce il concetto di
processore
virtuale per evitare i cambi di contesto, e quello di memoria virtuale: la
memoria viene infatti considerata come un unico e lineare spazio fisico, che
viene assegnato alle applicazioni a tempo di compilazione. In pratica viene
eliminato qualsiasi tipo di overhead, poiché nelle reti di sensori questo
causa un’inutile dispersione di energia senza portare tangibili vantaggi.
Queste scelte impattano direttamente sull'architettura che risulta molto
compatta e ben si sposa con le dimensioni ridotte della memoria che è
dell’ordine di pochi KB.
Lo scopo dichiarato dei progettisti di TinyOS era infatti quello di:
1. ridurre i consumi di energia;
2. ridurre il carico computazionale e le dimensioni del sistema
operativo;
3. supportare intensive richieste di operazioni che devono essere svolte
concorrentemente e in maniera tale da raggiungere un alto livello
robustezza ed un efficiente modularità.
Per soddisfare il requisito della modularità, TinyOS favorisce lo sviluppo di
una serie di piccoli componenti, ognuno con un ben precisa funzione, che
realizza un qualche aspetto dell'hardware del sistema o di un'applicazione.
Ogni componente poi, definisce un interfaccia che garantisce la riusabilità
del componente ed eventualmente la sua sostituzione.
1
http://tinyos.cvs.sourceforge.net/tinyos/
28
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 1.3 : Modello a strati di TinyOS
Guardando il modello a strati del sistema operativo (figura 1.3), possiamo
intuire come sia facilitato lo sviluppo di applicazioni mediante il riutilizzo
dei componenti esistenti.
TinyOS è stato implementato seguendo il modello ad eventi. Nei
tradizionali modelli infatti, è necessario allocare un certa quantità di
memoria sullo stack per ogni attività in esecuzione e inoltre, il sistema è
soggetto a frequenti commutazioni di contesto per servire ogni tipo di
richiesta, come l'invio di pacchetti, la lettura di un dato su un sensore, etc.
Poiché i nodi non dispongono di grosse quantità di memoria il modello ad
eventi ben si addice ad un sistema continuamente sollecitato, in quanto
utilizza il microprocessore nella maniera più efficiente possibile. Non sono
permesse condizioni di stallo né attese attive che sprecherebbero energia
inutilmente. Quando invece non ci sono attività da eseguire il sistema mette
a riposo il microprocessore che viene risvegliato all'arrivo di un evento.
1.7.1.1 Caratteristiche tipiche
Le caratteristiche tipiche del TinyOs si possono riassumere nei seguenti
punti:
•
Architettura basata su componenti
29
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Una applicazione è composta da uno o più componenti che possono
dialogare tra loro facendo uso di due set di funzioni: i comandi e gli
eventi. TinyOs mette a disposizione del programmatore un set di
componenti
standard.
componenti utilizzando
Un'applicazione
può
connettere
tali
delle specifiche di legame che sono
indipendenti dall'effettiva
implementazione. Ogni componente
inoltre contiene un'area dati chiamata frame, la quale viene allocata
staticamente (figura 1.4).
•
Operazioni in diverse fasi
La richiesta di una data operazione e il suo completamento sono due
funzioni distinte. I comandi tipicamente richiedono l'esecuzione di
un'operazione: quando questa termina, viene generato un evento che
segnala
all'applicazione il termine dell'operazione richiesta. Un
esempio tipico è l'invio di un pacchetto: l'applicazione invoca il
comando send per iniziare la
trasmissione e il componente di
comunicazione segnala l'evento sendDone quando l'operazione è
terminata. Esistono anche comandi al cui termine non è richiamato
alcun evento (ad esempio l'accensione di un LED).
•
Concorrenza:
Il TinyOs può eseguire un solo programma alla volta, tipicamente
formato da più componenti. Ci sono due tipi di thread: task ed
eventi hardware. I primi sono funzioni la cui esecuzione può essere
ritardata: essi vengono eseguiti in ordine secondo una coda FIFO.
Gli eventi hardware hanno priorità massima e bloccano qualsiasi
esecuzione in corso. Possono dunque nascere situazioni di data race
(ad esempio l’aggiornamento di una variabile)
•
Active Messages
Active messages è la tecnologia di rete utilizzata da TinyOs. Questo
sistema permette di inviare messaggi a tutti o a un singolo nodo tra i
30
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 1.4: Rappresentazione di un componente TinyOS
vicini (eventuali protocolli di routing vengono implementati ad un
livello superiore, quindi Active messages contiene solo un
meccanismo di indirizzamento verso i nodi vicini). Ogni pacchetto
spedito contiene l'identificazione di un handler da richiamare sulla
macchina di destinazione e il payload dei dati. Il principale
svantaggio dell'approccio è che tutti i nodi comunicanti devono
avere lo stesso software o
come minimo
implementare un
componente che definisca lo stesso handler.
1.7.2
Introduzione a NesC
NesC è il linguaggio di programmazione usato in ambiente TinyOs. La sua
sintassi è molto simile al classico C con alcune differenze: supporta il
modello di concorrenza del TinyOs e permette di collegare, strutturare
componenti software. NesC permette ai programmatori di sviluppare
componenti che possano essere facilmente assemblati tra loro.
Le caratteristiche basilari del NesC possono essere così riassunte:
1. nesC è una estensione del C: C produce codice efficiente per tutti i
processori che vengono di solito usati nelle reti di sensori; fornisce
31
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
tutte le caratteristiche necessarie per comunicare con l'hardware e
l'interazione con codice già esistente è semplificata. Inoltre è un
linguaggio molto conosciuto. D'altra parte però, C non aiuta molto a
scrivere codice strutturato privo di errori. Il nesC garantisce più
modularità grazie ad una sintassi molto ridotta e dà la possibilità di
strutturare i componenti collegandoli tra loro.
2. Analisi di tutto il programma: I programmi nesC, in fase di
compilazione, vengono analizzati nella loro interezza per ottenere
una sicurezza maggiore e per rendere possibile l'ottimizzazione. Di
conseguenza, non
esiste la possibilità di compiere compilazioni
separate. D'altra parte i
programmi scritti in nesC sono molto
leggeri e di conseguenza la compilazione risulta comunque veloce.
3. nesC è un linguaggio “statico”: Non esiste la possibilità di allocare
memoria dinamicamente. Questa restrizione rende più facile e
accurata l'analisi del programma in fase di debug.
4.
nesC riflette la struttura del TinyOs: nesC è basato sul concetto
di componente e supporta appieno il modello di concorrenza del
TinyOs. Inoltre il TinyOs è stato completamente programmato in
nesC. Nel
momento in cui un'applicazione viene compilata, i
componenti di TinyOs
vengono compilati insieme ad essa e il
risultato costituisce l'intero software del sensore. Questo approccio
porta ad un ingente risparmio energetico; tuttavia la versatilità viene
notevolmente limitata, non è possibile installare più applicazioni
indipendenti nello stesso sensore.
32
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
1.8
LE PIATTAFORME HARDWARE
Come già accennato nel paragrafo 1.4 le piattaforme hardware sono diverse,
in questo paragrafo ci concentreremo in particolare su Mica2 e Mica2dot
entrambe sviluppate dai ricercatori della University of California in Berkley.
I nodi sensore Mica2 sono equipaggiati con 512 KB di memoria flash per
memorizzare in modo permanente i dati raccolti e dispongono di un
connettore a 51-pin per l'aggiunta di un espansione (attuatori, dispositivi
sensori, etc).
Possiedono un clock esterno a 32 kHz che il sistema
operativo, in questo caso TinyOS, utilizza per sincronizzarsi con i vicini a
meno di +/- 1 ms e per assicurarsi che questi siano attivi ed in grado di
ascoltare le trasmissioni.
I nodi Mica2 possiedono tre led, uno rosso uno giallo e uno verde, che
possono essere comandati via programma e utilizzati per visualizzare una
qualche informazione di stato. Infine entrambe le piattaforme forniscono un
collegamento seriale (sullo stesso connettore a 51-pin) per i trasferimenti di
dati e l'installazione delle applicazioni su ciascun nodo.
Figura 1.5: Mica2
33
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 1.6: Mica2DOT
Il processore montato sulla piattaforma Mica è un Atmel ATMega128 AVR.
AVR è un architettura Harvard a 8-bit con una memoria separata per le
istruzioni e per i dati. I microcontrollori AVR supportano lo stato active e
quello sleep.
Per quanto riguarda il sistema di comunicazione radio utilizzato questo è un
Chipcom CC1000 progettato per
applicazioni che richiedono un basso
consumo di energia ed è in grado di comunicare da pochi metri fino a
centinaia di metri. Utilizza la codifica Manchester e la modulazione FSK,
supporta bande di frequenza a 315, 433, 868 e 915Mhz. Il sistema radio
può lavorare in quattro distinte modalità: transmit, receive, idle e sleep.
Questo significa che mentre trasmette non è in grado di ascoltare eventuali
trasmissioni da parte di altri nodi, quindi le collisioni, se avvengono , non
sono
riconosciute. In effetti il protocollo MAC utilizzato è del tipo
CSMA/CA.
Nella tabella 1-2 si riportano alcune caratteristiche della piattaforma Mica2.
Un’analisi esaustiva delle prestazioni di questi sensori viene riportata in [24]
e comprende la tabella 1-3 riassuntiva delle prestazioni dei Mote mica2 e
mica2dot.
34
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Component
Rate
Strtup Time
Current consumption
CPU Active
4 MHz
N/A
4.6 mA
CPU Idle
4 MHz
1 us
2.4 mA
CPU Suspend
32 kHz
4 ms
10 uA
Radio Transmit
40 kHz
30 ms
12 mA
Radio Receive
40 MHz
30 ms
3.6 mA
Photo
2 kHz
10 ms
1.235 mA
I2C Temp
2 Hz
500 ms
0.150 mA
Pressare
10 Hz
500 ms
0.010 mA
Press Temp
10 Hz
500 ms
0.010 mA
Humidity
500 Hz
500 ms
0.775 mA
Thermopile
2000 Hz
200 ms
0.170 mA
Thermistor
2000 Hz
10 ms
0.126 mA
Tabella 1-5: Alcune caratteristiche della piattaforma Mica2
Mica 2
Mica2dot
4.6 Kbps
4.6 Kbps
Reception
16 mA
12 mA
Transmission
18 mA
14 mA
Computation (processor only)
8 mA
8 mA
Power down mode
10 uA
10 uA
With mormal weather condition
55 m
135 m
With fog, rain
10 m
With maximun tx power (normal weather condition)
70 m
230 m
Minimum ground distance
1m
1m
50 cm
50 cm
AVAILABLE THROUGHPUT
POWER CONSUMPTION
TRASMISSION RANGE
Minimum horizontal distance
275 m
CARRIER SENSING RANGE
Tabella 1-6: Tabella comparativa delle prestazioni di mica2 e mica 2 dot
35
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
1.8.1 Sensori per Mica2
La modularità che sta alla base del progetto di questa piattaforma ha
permesso la realizzazione di numerose schede di sensori di vario tipo. La
scheda di riferimento per i nodi tipo Mica2 è la Mica Sensorboard
(MTS300CA), una scheda molto flessibile dalle varie modalità di utilizzo.
Questa scheda infatti può essere impiegata per applicazioni che includono il
rilevamento della presenza di veicoli, l'analisi di movimenti sismici, il
riconoscimento di oggetti in movimento, la localizzazione ed altre
applicazioni. Il resto del paragrafo analizza i dettagli di tale scheda.
Microfono
Il microfono può avere due principali usi:
•
localizzazione acustica
•
registrazione e misurazione dei suoni
La localizzazione acustica è una possibilità offerta da questa scheda che può
risultare molto utile. Il funzionamento è il seguente: un nodo invia un
pacchetto via radio e contemporaneamente emette un suono tramite un
segnalatore (disponibile sulla scheda), un nodo vicino, all'arrivo del
pacchetto, azzera un contatore che poi incrementa con una certa frequenza.
Il contatore viene incrementato fino a quando lo stesso nodo non avverte il
segnale acustico. A questo punto, moltiplicando il valore del contatore per la
frequenza di incremento, si ottiene all'incirca l'intervallo di tempo occorso al
segnale acustico per
raggiungere il destinatario. Conoscendo quindi il
valore della velocità del suono si ottiene in modo approssimato la distanza
tra due nodi.
Segnalatore
Questo dispositivo è in grado di emettere un unico suono alla frequenza di 4
kHz e viene utilizzato principalmente nella localizzazione dei nodi.
Luce e temperatura
36
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Questa scheda dispone di sensori in grado di misurare la quantità di luce
nell'ambiente e la temperatura. I sensore della luce è semplicemente una
fotocellula CdSe. La massima sensibilità di questa fotocellula permette di
rilevare raggi di luce fino ad una lunghezza d'onda pari a 690 nm. Il
termistore invece è un Panasonic ERT-J1VR103J ed è in grado di rilevare
temperature che vanno da -40 a 70 °C.
Accelerometro a 2-Assi
L'accelerometro è un dispositivo MEMS a 2-assi ed è in grado di rilevare
accelerazioni fino a ±2 g. E’ utilizzabile per rilevare movimenti, vibrazioni
e/o misurazioni sismiche.
Magnetometro a 2-Assi
I sensore è un Honeywell HNC1002. Il magnetometro può misurare il
campo magnetico terrestre ed altri piccoli campi. Un applicazione in cui può
essere impiegato è il rilevamento della presenza di veicoli.
TIPO
DESCRIZIONE
MTS101
Monta un termistore di precisione e sensori di luminosità, ed è utilizzabile
in varie aree
MTS300/ MTS310
Supporta una grande varietà di sensori per MICA e MICA2
MDA500
Fornisce una interfaccia flessibile per collegamenti con nodi di tipo
MICA2DOT
MTS400/420
È in grado di effettuare il monitoraggio ambientale ed eventualmente può
essere montato un GPS (MICA2)
MDA300
È in grado di acquisire dati e monitorare l’ambiente (MICA2)
MTS510
Supporta sensori di luce, accelerazione ed un microfono (MICA2DOT)
MEP401
Moduli per luce, umidità e pressione barometrica e temperatura (MICA2)
MEP500
Modulo per temperatura e umidità (MICA2DOT)
Tabella 1-7: Schede disponibili per piattaforma MICA
37
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
1.9 APPLICAZIONI
Le applicazioni delle reti di sensori sono svariate e condizionano i nodi
stessi che possono essere dotati di sensori completamente diversi. E’
possibile, come accennato prima, misurare una vastissima gamma di
grandezze fisiche come l’umidità, la pressione, la temperatura, il suono,
l’intensità luminosa, le dimensioni di un oggetto, la presenza di oggetti in
movimento e anche la loro accelerazione.
I sensori, grazie alle ridotte dimensioni, si adattano bene a strutture ostili e
inaccessibili. Inoltre grazie al loro elevato numero, risulta particolarmente
facile monitorare grandezze in aree relativamente ampie.
Le reti di sensori ai giorni nostri sono utilizzati in svariati campi come per
esempio l’ambiente, la medicina, per uso domestico (domotica) e per
applicazioni militari e commerciali.
o Ambiente
Alcune applicazioni riguardano l'osservazione degli spostamenti di
animali, uccelli, specie marine, insetti; il monitoraggio delle condizioni
ambientali a cui sono sottoposte le colture e gli allevamenti di bestiame;
il riconoscimento degli incendi boschivi; la ricerca metereologica e
geofisica; il riconoscimento delle inondazioni; la mappatura della
biocomplessità di un ambiente; lo studio dell'inquinamento. Alcune
implementazioni di questi esempi li troviamo nel sistema per il
riconoscimento delle inondazioni denominato ALERT [14], utilizzato
negli Stati Uniti; nella mappatura della biocomplessità, con il sistema
installato
nella
James
Reserve
in
Southern
California
nell'osservazione degli spostamenti degli uccelli migratori,
[15];
con il
progetto denominato Great Duck Island Habitat Monitoring [16],[17] del
quale viene riportata l’architettura generale in figura 1.7 (fonte:
http://www.greatduckisland.net/ ).
38
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 1.7: Architettura del progetto Great Duck Island
o Applicazioni militari
Le reti di sensori possono essere parte integrante dei sistemi militari di
comando,
controllo,
comunicazione,
elaborazione,
intelligence,
sorveglianza, riconoscimento ed individuazione. La rapidità di
collocazione, l'auto-organizzazione e la tolleranza ai guasti sono
caratteristiche che rendono queste
reti particolarmente adatte
all'impiego in campo militare. Dal momento che i
nodi possono
popolare densamente una qualsiasi area ed hanno un costo ridotto, la
distruzione di alcuni nodi in seguito ad un azione ostile non ne inibisce
il funzionamento globale. Alcune applicazioni sono il monitoraggio
delle forze alleate; il riconoscimento del nemico; l'individuazione degli
obbiettivi; la sorveglianza di intere aree; il riconoscimento e
l'individuazione di attacchi nucleari, biologici e chimici.
39
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
o Sanità
Alcune applicazioni nella sanità sono: la realizzazione di interfacce per i
disabili; il monitoraggio integrato dei pazienti; la somministrazione di
farmaci negli ospedali; il telemonitoraggio dei dati fisiologici di un
individuo; il tracciamento e il monitoraggio dei pazienti e del personale
medico negli
ospedali. Un esempio di telemonitoraggio dei dati
fisiologici di un paziente è
dato dal sistema Health Smart Home,
realizzato dalla Facoltà di medicina di Grenoble - Francia [18].
o Uso domestico
Un ambiente in grado di riconoscere l’utente presente al suo interno può
predisporre tutta una serie di servizi personalizzati differenti a seconda
di chi è l’ospite, inoltre i nodi sensore possono essere inseriti negli
apparecchi elettrici, come forni a microonde, frigoriferi, VCR [19].
Questi possono interagire tra loro e con una rete esterna, via internet o
via satellite e permettono all'utente di comandare
facilmente gli
elettrodomestici a distanza. Più in generale, le reti di sensori possono
essere utilizzate per realizzare ambienti intelligenti non solo in casa ma
anche negli uffici. Un esempio è il Residential Laboratory della Georgia
Institute of Tecnology [20]. Gli obbiettivi di questo laboratorio sono
l'affidabilità, la persistenza e la trasparenza dell'automazione.
o Applicazioni commerciali
Altre possibili applicazioni sono: la realizzazione di tastiere virtuali;
l'analisi del comportamento dei materiali sottoposti a stress meccanico,
la qualità di un prodotto; guida e controllo dei robot nelle industrie
automatizzate.
Ma anche il monitoraggio dell’aria all’interno degli uffici può essere
eseguito per esempio con una rete di sensori. Il flusso di aria
40
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
condizionata è controllato in maniera centralizzata; l’uso dei sensori può
portare ad una riduzione del consumo di energia.
Altre applicazioni infine in ambito commerciale sono:
•
guida e controllo di robot nei processi industriali;
•
rilevazione di furti d’auto entro una determinata area geografica non
troppo estesa;
•
la verifica delle categorie e della qualità di vari articoli presenti in
un grande magazzino;
•
controllo del traffico tramite reti di sensori.
41
Capitolo 2
Affidabilità nelle reti di sensori senza cavo
2.1 IL CONCETTO DI AFFIDABILITA’
L’esigenza di ottenere particolari requisiti di affidabilità dai sistemi risulta
essere sempre più un argomento di primaria importanza e ha portato a
continue rivisitazioni del concetto di dependability. Nel 1982 Laprie
definiva la dependability di un sistema come: “...the ability of a system to
accomplish the tasks (or,equivalently, to provide the service) which are
expected to it” , mentre nel 2001 sempre Laprie la ridefinì come
“...the ability to deliver service that can justifiably be trusted ” per poi
infine definire nel 2004 la dependability di un sistema come: “...ability to
avoid service failures that are more frequent and more severe than
acceptable” ovvero l'abilità di un sistema di fornire un servizio che può
essere considerato "fidato" in maniera giustificata.
In realtà il termine va inteso come un insieme di attributi di qualità
(dependability attributes) che assumono singolarmente un’enfasi relativa
alla natura del sistema cui si riferiscono e al particolare contesto applicativo:
42
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
ƒ
Availability
L’availability è sinteticamente definita come la probabilità che un
sistema sia pronto a fornire il servizio in un certo istante t, ovvero:
A=P(!Failure at t)
Più esplicitamente un sistema è available in un dato istante t se è in
grado di fornire un servizio corretto.
ƒ
Reliability
La reliability R(t) è la misura della continuità di un servizio ovvero la
misura dell’intervallo di tempo in cui viene fornito un servizio corretto:
R(t)=P(!Failure in (0,t))
ƒ
Safety
Per safety si intende generalmente l’assenza di condizioni di
funzionamento che possano portare il sistema a danneggiare gli utenti
e/o l’ambiente in cui opera. Dal punto di vista matematico la safety S(t)
è la probabilità che non vi siano guasti catastrofici in [0,t].
S(t)= P (!CatastrophicFailures in [0,t])
È chiaro che il concetto di safety risulta relativo alla soggettiva
valutazione dei rischi e dell’entità dei danni provocati dal sistema.
ƒ
Performability
La performability è una metrica introdotta per valutare le prestazioni del
sistema in caso di guasto.
ƒ
Mantainability
La mantainability M(t) è definita come la capacità di un sistema di
essere sottoposto a modifiche e riparazioni, ovvero di poter essere
facilmente ripristinato in seguito al verificarsi di un guasto.
43
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
ƒ
Security
La security è definita come l’assenza di manipolazioni improprie e
accessi non autorizzati al sistema. Più in dettaglio un sistema sicuro è un
sistema in cui coesistono gli attributi di availability (riadattata alla
disponibilità del sistema solo verso utenti autorizzati), confidentiality
(prevenzione della diffusione non autorizzata delle informazioni) e
integrità (prevenzione di alterazioni improprie dello stato del sistema.
2.2 AFFIDABILITA’ IN RETI DI SENSORI SENZA CAVO
Nell’ambito specifico delle reti di sensori senza cavo il concetto di
affidabilità si formalizza come la capacità che deve avere una rete di
conservare le proprie funzionalità indipendentemente dall’eventuale guasto
di qualche sensore o semplicemente da una trasmissione fallita.
Un nodo, ad esempio, può diventare inutilizzabile a causa dell’esaurimento
della batteria o per danni fisici subiti nell’ambiente operativo.
L’affidabilità riveste un ruolo sempre più importante nella progettazione
delle Wireless Sensor Network visto che queste sono sempre più utilizzate in
applicazioni mission critical come: rilevazione di intrusioni, applicazioni
militari, etc. Il suo studio è reso, però, complicato da più fattori, già
analizzati nei paragrafi precedenti come:
•
la limitatezza delle risorse sia energetiche che di memorizzazione e
di computazione dei nodi;
•
limitata robustezza fisica dei sensori che assume un ruolo non di
poco rilievo visto che le WSN vengono spesso utilizzate in ambienti
esterni avversi e persino estremi;
•
la casualità della topologia della rete.
44
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Relativamente alla fase di progettazione di una Wireless Sensor Network gli
aspetti su cui incide l’affidabilità e che quindi devono essere debitamente
presi in considerazione sono:
1. Coverage & Deployment: con il quale si cerca di stimare un numero
sufficiente di nodi sensori affinché un evento possa essere esaminato
nella sua totalità. Al tempo stesso con questo aspetto si cerca di
stabilire in che modo effettuare una misura accurata dei dati
osservati e in che modo effettuare il deployment dei nodi per la
conformazione della rete.
2. Information accurancy: con il quale ci si concentra principalmente
sulla modalità di classificazione dei dati raccolti e sulla definizione
di strategie per il trattamento delle misurazioni non accurate.
3. Dependable data trasport: aspetto con il quale si definiscono
strategie per assicurare il recapito delle misurazioni al centro
raccolta. In particolare si definiscono strategie per combattere errori
di trasmissione, di omissione e di congestione
Spesso fornire un certo livello di affidabilità risulta arduo, soprattutto in
alcuni campi applicativi. Ad esempio il monitoraggio di strutture dinamiche
[1], richiede alti requisiti di affidabilità, che devono ben amalgamarsi con i
comuni attributi di efficienza energetica, scalabilità e autoconfigurazione
tipici di una WSN. In particolare si può avere necessità di:
ƒ
una fine sincronizzazione temporale;
ƒ
minimizzare l’intervento umano sulla rete.
ƒ
una copertura minima dell’area da monitorare;
Riguardo il primo aspetto questo risulta importante al fine di disporre di una
caratterizzazione temporale precisa del fenomeno osservato. Questo
requisito può essere rilassato nel caso in cui si considera una struttura della
rete in cui i nodi sensori sono organizzati in cluster in quanto si potrebbe
richiedere la sincronizzazione per ogni cluster e non dell’intera rete.
45
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Riguardo il secondo requisito questo risulta sempre più dominante nelle
attuali installazioni di Wireless Sensor Network. L’intervento umano,
spesso limitato alla sola sostituzione delle batterie dei nodi, o alla
sostituzione di un nodo malfunzionante può risultare spesso improponibile
(in caso di reti in scenari avversi) o estremamente costoso e per questo deve
essere ridotto quanto più è possibile al minimo. Tecniche che cercano di
soddisfare questa necessità sono basate sull’utilizzo di strategie di “load
balancing” e di “incremento della vita delle batterie”.
Il terzo aspetto, infine, è inteso come la possibilità di avere a disposizione
un minimo ammontare di misurazioni al fine di poter avere una
caratterizzazione completa del fenomeno che si sta analizzando e sarà
analizzato in dettaglio nel successivo paragrafo.
2.2.1
Il problema della copertura
Per comprendere bene cosa si intende per problema di copertura si può
immaginare uno scenario in cui si hanno a disposizione n sensori,
organizzati in un cluster, con i quali bisogna effettuare il monitoraggio di un
ponte al fine di effettuarne una analisi delle vibrazioni. Un requisito
potrebbe essere avere almeno k<n misurazioni per ogni ciclo di
misurazione. È chiaro che il valore di k deve essere scelto riguardo alle
caratteristiche del fenomeno da analizzare ed inoltre i k sensori devono
essere scelti in modo da prevenire una polarizzazione della misura (ovvero
misure che provengono solo da un zona osservata ad esempio quella
limitrofa). Il requisito di copertura può essere quindi considerato a tutti gli
effetti come un attributo che insieme alla availability, reliability, safety, ect
permette di definire dependability del sistema.
46
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Un esempio ,che vede uno scenario composto da una rete di sensori
utilizzata per il monitoraggio di disastri ambientali come gli incendi,
chiarisce ancora meglio come la copertura può essere fondamentale per la
definizione della dependability di un sistema. Una visione dell’architettura è
mostrata in figura 2.1. In questo caso è necessario per far scattare l’allarme
di incendio, che almeno un numero significativo di sensori mi forniscano
misurazioni di temperature elevate e che quindi si abbia una adeguata
copertura delle varie zone da monitorare. È chiaro che per avere una chiara
dinamica della temperatura nel tempo è necessario che i vari sensori siano
sincronizzati tra di loro ed inoltre che siano dotati di un modulo in grado di
portare avanti una procedura di localizzazione se si suppone che questi siano
disposti in maniera casuale nell’ambiente (tramite lancio attraverso un
Figura 2.1: Architettura WSN per rilevazione incendio
47
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
aereo).
In letteratura il problema della copertura è stato trattato secondo vari punti
di vista. Per esempio l’ ”Art Gallery Problem” si concentra sul determinare
il numero di controllori necessari per coprire una galleria d’arte in modo tale
che ogni punto di essa sia monitorata almeno da un controllore. Questo
problema è stato dimostrato essere risolvibile in uno spazio 2D ma si è
mostrato di tipo NP-hard se è esteso ad uno spazio 3D [66]. Il lavoro di
Meguerdichian et al. [67] definisce invece una metrica per la copertura dei
sensori denominata sorveglianza (surveillance) utilizzabile come misura
della qualità del servizio di una particolare rete di sensori senza cavo.
Lo stesso problema della copertura è direttamente collegato al risparmio
energetico dei nodi, infatti moltissimi lavori in letteratura sono dedicati a
questa tematica e in particolare al problema dello scheduling ottimale
dell’accensione dei nodi sensori al fine di preservare l’energia. Questi lavori
si basano sul concetto di spegnere selettivamente i nodi sensori senza però
inficiare sulla copertura totale che deve essere fornita.
In [68] propone una euristica per selezionare sets di sensori mutuamente
esclusivi per provvedere a una completa copertura dell’area da monitorare.
Sempre basandosi sullo spegnimento dei nodi [71] propone uno schema
molto interessante basato su un algoritmo di controllo della densità al fine di
porre in uno stato di sleep alcuni sensori che appartengono ad aree popolate
densamente, in modo da assicurare una lunga vita alla rete. I nodi in
sleeping mode sono poi risvegliati periodicamente e non fanno altro che
controllare se devono sopperire a fallimenti di nodi vicini. Risulta chiaro
come la frequenza del risveglio venga settata in modo tale da essere un
giusto compromesso tra la densità di nodi desiderata e consumo energetico.
gli autori riescono a dimostrare che un tale schema estende il periodo di vita
della rete secondo una proporzione lineare rispetto al numero di nodi
utilizzati, usando circa l’1% del totale dell’energia consumata e resistendo al
48
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
38% di fallimenti dei nodi. Un altro schema di scheduling atto a preservare
la copertura di una rete viene proposto da Tian et al. [69] dove l’analisi è
incentrata sul determinare quali nodi possono essere spenti e quando devono
essere risvegliati.
2.3
AFFIDABILITA’: STATO DELL’ARTE
Molti sono gli studi presenti in letteratura che sono dedicati alla affidabilità
nelle reti di sensori senza cavo. Un primo esempio è il lavoro di Basile et al.
[38] dove sono analizzate e proposte strategie al fine di costruire reti
wireless e reti ad-hoc affidabili e sicure. Il fulcro del lavoro è sulla nozione
di inner-circle consistency, ovvero la cooperazione tra i nodi locali viene
sfruttata al fine di neutralizzare errori e attacchi alla sorgente in modo tale
da evitare che questi si possano propagare in tutta la rete. Come strumento
per la valutazione delle strategie proposte si considera un modello dei
fallimenti in cui le possibili cause di fallimento sono i crashing o i
Byzantine behavior. Insieme al modello dei fallimenti viene utilizzato anche
un modello della rete in cui si adottano sia tecniche statistiche sulla
clusterizzazione che tecniche orientate al rispetto della security.
Gli effetti sollevati dal fallimento di un singolo nodo sullo stato di
funzionamento di una WSN sono invece analizzati nel lavoro di Shakkottai
et al. [39]. In questo contesto è stato individuato un limite superiore alla
probabilità che tutti i nodi siano connessi e tutta l’area della rete sia coperta,
questo nell’ipotesi che i nodi siano uniformemente distribuiti sul suolo e che
la probabilità di fallimento sia anch’essa uniforme in tutta la rete. Viene
inoltre ricavata una condizione necessaria e sufficiente affinché la rete
continui a coprire l’intera area (nonostante l’inaffidabilità dei nodi che la
compongono)
e
viene
anche
ricavata
la
minima
probabilità
di
funzionamento di un nodo al di là della quale la “copertura” dell’area non è
49
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
più garantita. Un aspetto non contemplato dal lavoro è però come la
connettività sia influenzata dalla morte di nodi faulty o con batterie scariche,
ipotesi in cui non varrebbe più l’assunzione di densità uniforme della rete.
Un modello di reliability è poi fornito in [40] e [41]. In [40] sono presentati
alcuni modelli a catene di Markow per diverse tipologie di sensori. La
reliability viene calcolata per diversi “failure rate” e poi i modelli sono
comparati in termini di costo e della distribuzione cumulativa e media della
funzione di reliability. Arricchisce il lavoro anche un’analisi comparativa
della reliability della rete condizionata all’utilizzo di tecniche di ridondanza
spaziale o di codici ECC (error correcting code)
In [41] Iyengar et al. focalizzano l’attenzione sulle misure di reliability per
WSN, fornendo anche delle stime sul minimo e massimo ritardo nella
consegna di un messaggio di un nodo verso il sink. Viene adottato all’uopo
un modello a grafo
probabilistico per rappresentare la rete, dove le
probabilità (di perdita di pacchetti) sono ricavate da stime sul tasso di
fallimento dei sensori. Viene definita la reliability di una WSN come la
probabilità che esista un cammino tra il sink e almeno un unico nodo
funzionante del cluster: adottando questa definizione viene
dimostrato
come per reti di topologia arbitraria, la soluzione del modello di affidabilità
considerato rappresenti un problema di complessità non polinomiale, tranne
che per un caso particolare analizzato, per cui vengono fornite anche delle
misure ottenute tramite simulazione.
In [42] Gupta e Kumar analizzano l’impatto della connettività sulla
reliability della rete. A tale scopo viene analizzano il comportamento di una
WSN organizzata in clusters, attraverso un fault model in cui vengono
considerati solo i
fallimenti del gateway relativi all’esaurimento delle
batterie e a fallimenti del modulo radio: questi ultimi dovuti sia a guasti
hardware che a fallimenti di nodi nel suo range operativo. Tutti i fallimenti
considerati sono di durata permanente.
50
In base a questo modello dei
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
fallimenti, viene proposto un meccanismo di recupero basato sul consenso
tra i gateway ancora funzionanti. Per testare la copertura della strategia
proposta, viene adottata una tecnica di iniezione dei guasti simulata, tramite
la quale viene dimostrato che l’approccio fornisce un
miglioramento
considerevole sulla stabilità del sistema riducendo l’overhead
della ri-
clusterizzazione e della riorganizzazione della rete. Il lavoro fornisce anche
un’analisi teorica sulla soglia del range radio che garantisce la connettività
tra nodi di una rete dislocata casualmente, utilizzando un modello
matematico.
Infine, uno studio, sull’impatto di fenomeni di invecchiamento dei nodi
sulla reliability della rete, è sviluppato da Krishmachari [43] dove viene
analizzata la correlazione tra la durata della vita di ogni nodo e il suo
consumo energetico in rispetto di alcune metriche di affidabilità come il
Mean Time To Failure. Risultati interessanti sono forniti in merito alle
misure relative all’impatto delle strategie di data aggregation sulla durata
della vita di un nodo.
2.4
AMBIENTI DI SIMULAZIONE
Questo paragrafo si pone l’obiettivo di effettuare una carrellata dei vari
ambienti di simulazione per l’analisi di reti di sensori senza cavo con
particolare attenzione rivolta agli strumenti forniti dai vari ambienti per una
caratterizzazione completa della rete emulata al fine di poterli sfruttare per
ricavare parametri per l’analisi dell’affidabilità.
Esaminare il comportamento di un sistema a tutti i livelli è necessario per
raggiungere il massimo grado di accuratezza, infatti spesso un approccio
basato sulla simulazione di algoritmi e protocolli di rete risulta inefficiente e
questa inefficienza si accentua soprattutto in una Wireless Sensor Network
51
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
dove i protocolli e le applicazioni possono interagire tra di loro facendo
annullare il concetto di stratificazione [25].
Emstar, insieme a Tossim è stato uno dei primi simulatori esplicitamente
progettati per le reti di sensori senza cavo, questo è framework concepito per
studiare due tipi di WSN [29][30]: quelle costituite da sensori Microservers
con architettura a 32-bit, che fanno uso tipicamente di sistema operativo
Linux, e quelle composte da sensori Mica a 8-bit, che sfruttano il sistema
operativo TinyOs. Emstar consente di studiare l’esecuzione di applicazioni
di entrambi i tipi secondo varie modalità d’uso rese disponibili all’utente; è
chiaro che l’emulazione sarà richiesta solo per le applicazioni destinate ai
sensori Mica, mentre quelle per i Microservers sono normali applicazioni
Linux che non necessitano di essere emulate. L’ambiente di simulazione
offre anche una serie di servizi utili per creare applicazioni Linux, come vari
algoritmi di routing (tra i quali il Direct Diffusion, che si occupa di inviare
messaggi solo a gruppi di nodi interessati, utile per effettuare query mirate
all’interno della rete di sensori), un servizio di localizzazione che i sensori
possono adoperare per costruire e mantenere aggiornata in maniera
dinamica la topologia della rete circostante, un servizio di sincronizzazione
tempo virtuale/reale indispensabile nelle simulazioni ibride, ed altri ancora.
Purtroppo non viene simulato l’uso del sensore, né il consumo energetico, e
queste sono delle pecche abbastanza importanti in un emulatore che si
prefigge lo scopo di studiare il funzionamento dei sensori a basso livello.
Atemu è un simulatore del comportamento dell’intero hardware dei sensori,
che usa come input il binario eseguibile dell’applicazione [31]. I sensori
simulati sono quelli delle famiglie Atmel e Mica con processore AVR; una
delle possibilità più interessanti di Atemu è quella di poter definire
l’hardware dei sensori su cui eseguire le applicazioni. Il comportamento
della rete può essere più che mai eterogeneo, decidendo sia le applicazioni
52
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
che l’architettura hardware di ciascun nodo o gruppo di nodi della rete, ed
indicandone la posizione in modo da decidere la topologia della rete a
piacimento (secondo un semplice modello 3D). L’utilizzo di Atemu è
soprattutto in ambito di debugging, visto la possibilità di poter tenere sotto
controllo, in ogni step della simulazione, lo stato di ciascun sensore (valore
dei registri interni, uso della memoria, istruzione corrente, messaggi inviati
e ricevuti). Anche in Atemu non esiste alcun modello del consumo
energetico dei sensori della rete, e non è prevista nessun meccanismo per
l’analisi dell’affidabilità.
Avrora è un emulatore scritto in Java che simula il comportamento
dell’intero hardware dei sensori, eseguendo il codice del programma in
linguaggio assemblativo [32]. I sensori simulati sono quelli delle famiglie
Atmel e Mica, dotati di processore AVR. La principale differenza con
Atemu consiste nel fatto che Avrora è un simulatore ad eventi, e non tempo
continuo. Non viene simulato il funzionamento dei sensori quando essi sono
in sleep, saltando direttamente al prossimo evento nella coda d’attesa di quel
sensore che ne provoca il risveglio ed il funzionamento. A questo si
accompagna il fatto che ogni nodo viene simulato in un thread a parte dal
simulatore, il che consente di velocizzare ulteriormente la simulazione,
anche se ciò pone il delicato problema della sincronizzazione degli eventi
che riguardano nodi diversi.
Ns-2 [33], Glomosim [34] e Opnet [35] sono simulatori di rete, adattati o
implementati per le WSN. Sono progettati per simulare specificamente lo
strato di rete dello stack di comunicazione. Ns-2 non supporta in maniera
nativa le WNS, ma esistono delle estensioni che forniscono all’ambiente di
simulazione le
capacità di simulare un canale trasmissivo wireless.
Glomosim è stato progettato specificamente per supportare reti wireless e
mette a disposizione un ottimo modello di propagazione radio. Opnet è un
53
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
simulatore standardizzato in ambito industriale e commerciale molto simile
a ns-2. Opnet viene fornito con un modulo che simula la propagazione RF e
interferenze, ma non supporta in maniera nativa le WSN.
SensorSim [36] nasce come modulo aggiuntivo per ns-2. Sviluppato dai
laboratori di ricerca UCLA2. SensorSim racchiude alcuni
interessanti
caratteristiche tra cui un modello dell’attività sensoristica, un modello della
batteria per il consumo energerico dei nodi, un leggero stack protocollare
appositamente progettato per le WSN e un modulo per la simulazione che
consente l’interazione attraverso dei reali sensori, per una simulazione
‘ibrida’.
J-Sim [37], è un ambiente di simulazione scritto in Java, con front-end in
Tcl, sviluppato prendendo ispirazione da Ns-2 e dalla sua estensione
Sensorsim. E’ realizzato secondo il paradigma della programmazione a
componenti; costituisce un framework per la simulazione di reti di
calcolatori in generale, wired e wireless, con in particolare un supporto
dedicato alle WSN ispirato direttamente a Sensorsim; implementa
funzionalità in maniera più completa rispetto a Ns-2, come ad esempio la
simulazione ibrida, che può essere condotta in varie modalità.
Shawn [58] è un simulatore orientato agli algoritmi, che offre all’utente un
ambiente di supporto in cui può scrivere in linguaggio C++ l’algoritmo che
desidera eseguire su ciascun nodo della rete. Oltre a decidere l’algoritmo
che andrà in esecuzione sui nodi della rete in maniera omogenea, si possono
stabilire alcune caratteristiche della simulazione, come il modello
topologico (a scelta tra quelli esistenti), la posizione dei nodi, il modello di
trasmissione dei messaggi sui link tra nodi adiacenti.
Algosensim [59] ,alla stregua di Shawn, è un simulatore orientato agli
algoritmi. È scritto in Java e l’ambiente di simulazione viene configurato
mediante la scrittura di files XML. Al momento è disponibile solo una
54
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
versione alpha, anche se il framework del simulatore è stato completamente
sviluppato così come buona parte delle classi.
Omnet++ [60], infine, è un simulatore scritto in C++ secondo il paradigma
della programmazione basata sui componenti, che usa il linguaggio Ned per
la configurazione della simulazione. Anche se sul sito ufficiale è dichiarata
l’esistenza di progetti per la simulazione di reti Internet, anche con elementi
wireless, ed eventualmente WSN, per il momento tali estensioni sono
assenti. La struttura del simulatore è sostanzialmente simile a quella di altri
simulatori come Ns-2 e J-Sim. La differenza principale sta nel maggior
livello di astrazione, nel minor numero di funzionalità offerte e nella
maggiore semplicità della simulazione. In Omnet++ non esistono librerie di
componenti che implementano ciascuno strato dello stack protocollare del
software di rete; il simulatore è concepito per una rappresentazione molto
più astratta dei nodi della rete, che nella maggior parte dei casi avviene
tramite un unico componente, o un insieme di pochi componenti interni, che
si occupano unicamente di descrivere come il nodo in questione gestisce la
ricetrasmissione di messaggi.
2.4.1
Il Simulatore Tossim
TOSSIM [26], [27] è un simulatore ad eventi che consente di effettuare il
debugging e l’analisi di un’applicazione per TinyOS, semplicemente
compilandola per la piattaforma PC, anziché per l’hardware del sensore (ad
esempio mica). Naturalmente TOSSIM non simula il mondo reale, ma fa
una serie di semplificazioni che permettono di mantenerne la scalabilità,
senza pregiudicarne tuttavia l’accuratezza dei risultati. Le caratteristiche
principali sono le seguenti:
55
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
9 TOSSIM simula il comportamento di TinyOS a basso livello, in
particolare simula la comunicazione fra nodi a livello di bit e tutti
gli interrupt di sistema;
9 gli interrupt sono temporizzati con precisione, mentre i tempi di
esecuzione non vengono simulati (dal punto di vista del simulatore
un pezzo di codice viene eseguito istantaneamente);
9 la propagazione dei segnali radio non viene simulata; i collegamenti
fisici sono modellati attraverso un grafo che indica per ogni coppia
di nodi la probabilità di
errore sul bit (0 significa perfetta
connettività, 1 connettività assente);
9 non viene simulato il comportamento della batteria ma viene solo
quantificata l’energia consumata da ciascun nodo.
9 in TOSSIM un interrupt non può interrompere il codice attualmente
in esecuzione, come invece è possibile nei mote reali;
9 in TOSSIM tutti i nodi sensori devono necessariamente eseguire la
stessa applicazione.
Il debugging delle applicazioni viene fatto generalmente inserendo nel
codice delle chiamate alla funzione dbg, la quale consente appunto di
inviare
stringhe di
testo al simulatore, specificandone anche il tipo.
TOSSIM durante l’esecuzione legge questi messaggi di debug e mostra
all’utente solo quelli del tipo corretto,
specificato tramite la variabile
d’ambiente DBG.
Per quanto riguarda la comunicazione wireless, il simulatore fornisce due
modelli del mezzo radio:
•
il modello simple;
•
il modello lossy.
In entrambi i casi i segnali possono in un certo istante assumere solo i valori
zero o uno e non hanno associata una
informazione sull’intensità. Il
modello simple si comporta come se i nodi fossero posizionati in una
56
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
singola cella, per cui tutti i bit trasmessi sono ricevuti senza errori da tutti i
sensori presenti. Anche se non ci sono errori di trasmissione si possono
comunque avere collisioni se due o più dispositivi trasmettono
contemporaneamente, portando alla corruzione dei dati.
Il modello lossy, più utilizzato in pratica, connette tutti i nodi in un grafo
orientato, in cui ogni arco indica la probabilità che un bit trasmesso venga
ricevuto invertito. Se ad esempio all’arco (a, b) è associato il valore 0.01
significa che ogni bit trasmesso da a ha l’1% di probabilità di essere
ricevuto corrotto da b.
Questo modello consente quindi di simulare
topologie più complesse in cui non tutti i nodi sono connessi tra loro,
permette di avere connessioni asimmetriche e di valutare le conseguenze
delle interferenze. Il grafo può essere specificato fornendo al simulatore un
file contenente i valori del bit-error-rate per ogni coppia di sensori; esiste
anche la possibilità di generare il file attraverso lo strumento LossyBuilder,
che costruisce il grafo basandosi sulla topologia e su dati sperimentali
ottenuti dagli sviluppatori.
2.5
OSSERVAZIONI
I vari simulatori analizzati nel paragrafo precedente, focalizzano la loro
attenzione su varie peculiarità delle WSN, ma nessuno di essi è in grado di
fornire delle misure di dependability della rete e/o dei nodi. Questa è una
forte limitazione in quanto le WSN sono al giorno d’oggi utilizzate in
svariati ambiti dove sono richiesti parametri di affidabilità del tutto
differenti tra di loro. Infatti, come si è potuto constatare, le applicazioni
scritte per reti WSN sono fortemente legate al contesto nel quale sono
utilizzate e per questo sarebbe utile avere un meccanismo per la valutazione
della dependability già in fase di progettazione.
Tra i vari simulatori analizzati, in questo lavoro di tesi, si è scelto di
utilizzare Tossim. La possibilità di poter eseguire le applicazioni tinyOS su
57
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
un normale PC, invece che su un dispositivo mote reale, ha sicuramente
influito positivamente sulla scelta, in quanto è possibile testare e analizzare
un’applicazione per reti di sensori in un ambiente controllato e ripetibile. Un
altro vantaggio evidente offerto da questo framework, a differenza di altri
simili come Emstar, è la possibilità di riutilizzare il codice per eseguirlo
direttamente su un dispositivo mote reale senza effettuarne nessuna
modifica. Infatti altri simulatori come Emstar prevedono che non venga
eseguito il file binario che andrà sui sensori veri e propri ma una versione
differente del codice, la quale non prevede simulazione del consumo
energetico né gestione delle interruzioni hardware, schedulando tutti gli
eventi come una serie di tasks di breve durata che vengono eseguiti in
sequenza uno dopo l’altro.
Altro punto a favore di Tossim è sicuramente la qualità e quantità della
documentazione e il grosso interesse della comunità di sviluppatori di WSN
per questo framework proprio per le caratteristiche succitate.
58
Capitolo 3
Algoritmi per la raccolta dati affidabile
3.1
CONSIDERAZIONI GENERALI ED OBIETTIVI
Come già messo in evidenza nel paragrafo 1.9 l’ambito di applicazione
delle reti di sensori senza cavo è molto vasto. L’obiettivo di questa tesi è di
progettare e valutare algoritmi per la raccolta dati affidabile.
Il contesto specifico all’interno del quale si colloca il lavoro è il
monitoraggio di una struttura dinamica, ovvero il monitoraggio dello stato
di salute di una struttura attraverso un apposita rete di sensori che possa
essere in grado di fornire mappe di deformazione, distribuzioni di
temperatura, misure di vibrazione e identificazione e localizzazione di danni
interni alla struttura. Attualmente i sistemi sviluppati sono basati su reti
“single-hop” cablate cioè su reti nelle quali si fa l’ipotesi che ogni sensore
sia in grado di comunicare con un nodo atto all’acquisizione delle
misurazioni attraverso l’utilizzo di un canale cablato. Questi sistemi sono di
solito composti da un numero basso di dispositivi sensori e presentano
problemi come gli elevati costi di installazione e il rumore elettromagnetico,
non trascurabile quando vengono utilizzati cavi di trasmissione lunghi
(superiori ai 100m). Ciò comporta
59
degrado delle misurazioni e
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
sovra-voltaggi che possono causare guasti agli stessi dispositivi. Le reti di
sensori senza cavo vengono in aiuto proprio per risolvere problemi come
questi in quanto prevedono l’eliminazione dei cavi e provvedono all’uso di
segnali digitali che sono meno soggetti ad interferenze e sovra-voltaggi.
D’altronde le WSN introducono una nuova serie di problemi dovuti alle
caratteristiche
del
mezzo
wireless
attraverso
cui
avvengono
le
comunicazioni dei nodi e all’esaurimento delle riserve energetiche dei
singoli nodi.
Di conseguenza la fase di sviluppo si arricchisce di nuove tematiche e
requisiti che vanno ad aggiungersi a quelli base per formare uno scenario in
cui è necessario avere:
1. una raccolta affidabile di un numero sufficiente di misurazioni in
una vasta area;
2. sincronizzazione delle misurazioni;
3. utilizzo di protocolli di raccolta dati energeticamente efficienti;
4. minimizzazione dell’intervento umano;
In questo lavoro di tesi si focalizzerà l’attenzione soprattutto sui punti 1 e 3
tralasciando il problema della sincronizzazione delle misurazioni.
3.2
ALGORITMI DI DATA GATHERING
Con il termine Data Gathering si intende una famiglia di algoritmi, usati
tipicamente in applicazioni di tipo monitoring, per raccogliere dati
globalmente e trasmetterli al nodo base in gergo denominato nodo sink.
Lo scenario è quello di una rete di sensori, con una certa struttura, di cui si
conosce la localizzazione di ogni singolo nodo e dove si ipotizza che ogni
nodo sia in grado di comunicare in multi-hop con qualsiasi altro nodo della
rete e quindi anche direttamente con il nodo sink (figura 3.1).
60
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 3.1: Scenario tipico di una rete di sensori wireless: i comandi sono
inoltrati in modalità broadcast mentre le misurazioni recapitate al
nodo sink tramite protocollo multihop
Questo genere di algoritmi cercano un modo efficiente, in termini di vita
globale della rete, per raccogliere i dati e renderli disponibili al nodo base.
Molto spesso si ipotizza che ogni nodo abbia anche la possibilità di fondere
e aggregare le informazioni ricevute, ed eventualmente instradarle seguendo
un percorso, variabile nel tempo, che sfrutta i nodi che ad esempio sono
dotati di maggiore energia residua. Queste tecniche sono molto utilizzate e
permettono la riduzione dell’informazione trasmessa mentre questa viaggia
all’interno della rete e sono denominate: Data aggregation e data fusion.
Entrambe evitano lo spreco di risorse (come la banda e l’energia) e cercano
di limitare il traffico che transita nella rete. L’idea principale consiste
nell’unire in un unico pacchetto inviato l’informazioni proveniente da più
nodi prima di inoltrarla verso la destinazione, aumentando l’efficienza delle
trasmissioni quando i dati da trasmettere sono pochi. Differenti strategie di
data fusion e aggregation richiedono diverse risorse e possono determinare
variazioni nel routing.
61
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
In letteratura [11] il problema del Data Gathering viene analiticamente
formalizzato come un problema di programmazione lineare che prende il
nome di MLDA (Maximum lifetime data gathering). Per reti ad elevato
numero di sensori è evidente come l’utilizzo di normali tecniche per
risolvere la PL risulti troppo oneroso in termini computazionali. Proprio per
ovviare a questo problema ultimamente si è andato sempre più sviluppando
un approccio clustering- based che nel caso dell’MLDA da una soluzione
euristica al problema, garantendo nel worst-case complessità polinomiale in
n, dove con n si indica il numero di sensori della rete. L’idea è quella di
suddividere la rete in m cluster, cercando quanto più di individuare delle
zone in cui i sensori si attestano su simili condizioni misurate, ad esempio
“zona a temperatura compresa fra 50° C e 80° C, oppure “zona a bassa
luminosità”, etc. Questo concetto verrà dettagliatamente ripreso nel
paragrafo 3.4.
3.3
INTERAZIONE TRA I NODI: IL PROTOCOLLO
MULTIHOP
Il problema di avere una vasta area da monitorare nella quale si devono far
pervenire le misurazioni ad un nodo base (sink) può essere una grossa
limitazione nel caso in cui non si abbiano a disposizione degli adeguati
protocolli di rete. La soluzione come gia si è accennato nel paragrafo 1.6.3 è
l’utilizzo del protocollo multihop che consente ai nodi sensore all’esterno
del raggio di azione del ricetrasmettitore dalla stazione base di trasmettere i
dati ai nodi sensore vicini, i quali a turno inoltreranno i dati fino alla
stazione base. Il processo di inoltro potrebbe coinvolgere anche molti nodi
sensori ma le informazioni potrebbero comunque giungere a destinazione
nel caso in cui non si verifichino collisioni.
La versione 1.1.x e successive di TinyOs includono delle librerie di
62
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
componenti che forniscono un routing multi-hop realizzato appositamente
per le reti di sensori wireless: l’implementazione, contenuta all’interno della
cartella $TOSROOT/tos/lib/Route impiega l’algoritmo dello shortest
path first con una singola destinazione, rappresentata dalla stazione base
(nodo con identificativo univoco 0), svolgendo una stima dei collegamenti.
L’inoltro dei dati e i meccanismi di routing sono implementati in due
diversi componenti (MultiHopEngineM e MultiHopLEPSM) con
una singola interfaccia (MultiHopRouter), che li collega, al fine di
permettere una più facile integrazione di ulteriori schemi di routing in
futuro (figura 3.2). MultiHopEngineM stabilisce la logica di movimento
generale dei pacchetti per le funzionalità che riguardono il routing
multihop. Tramite RouteSelect il modulo individua il next-hop nel
cammino di routing ed invia i pacchetti utilizzando la porta SendMsg.
MultiHopLEPSM fornisce:
ƒ
meccanismi per la stima dei collegamenti e per la selezione del nodo
genitore (Link Estimation Parent Selection);
ƒ
strumenti per monitorare il traffico ricevuto da un nodo;
ƒ
primitive per la ricezione/trasmissione dei messaggi di update e
Figura 3.2: Configurazione di Multihop Router
63
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
delle informazioni di routing direttamente dai nodi vicini tramite la
porta Snoop. Le informazioni accumulate sono poi utilizzate per la
scelta del next-hop. La procedura di inoltro dei messaggi di
aggiornamento dei cammini è periodica (ogni 10 sec) così come
quella di rielaborazione delle informazioni ricevute (50 sec).
Infine la configurazione MultiHopRouter
connette i due moduli
suddetti e la configurazione importa le porte fornite dalle funzioni
Receive,
Send,
Intercept
Snoop.
La porta fornita da
SendMsg, invece, è collegata ai componenti della libreria QueuedSend la
quale è impiegata per la gestione della coda dei pacchetti, sia che essi siano
stati originati localmente dal nodo sensore sia che essi siano stati inoltrati da
altri nodi.
L’utilizzo del protocollo multihop risulta essere una buona soluzione per
scenari in cui bisogna effettuare il monitoraggio di vaste aree, però va anche
evidenziato che è la soluzione più semplice possibile, e di conseguenza
presenta alcuni svantaggi come ad esempio il recapito di tutte le
misurazioni. Infatti i link RF delle comunicazioni wireless sono affetti dal
problema dell’interferenza, che nella maggior parte dei casi è dovuto alla
collisione di pacchetti che viaggiano nell’etere. Ciò causa perdita di
misurazioni e di conseguenza perdita di informazione relativa ad una zona
monitorata. Due sono quindi gli aspetti che debbono essere trattati:
1. utilizzo di approcci tesi ad evitare zone di non copertura;
2. utilizzo di tecniche per il recapito affidabile delle informazioni.
Nel prossimo paragrafo si tratterà in particolare il punto 1 mentre il 2 punto
sarà dettagliato nel paragrafo 3.7
64
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
3.4
CLUSTERING IN UNA WSN
Dato l’elevato numero di sensori che compongono la rete, può risultare
conveniente per molte applicazioni raggruppare i nodi in cluster (vedi figura
3.3), ed eleggere per ciascuno gruppo un super-nodo, detto cluster-head.
In questa accezione la raccolta di informazione può essere intesa in due
modi differenti:
1. come la collezione delle varie misure effettuate dai nodi appartenenti
allo stesso cluster, le quali vengono recapitate al nodo sink tramite il
cluster-head in quanto questo può, ad esempio, essere quello che
impiega la minor quantità di energia per il recapito delle
informazioni;
2. come raccolta della misurazione da parte del solo cluster-head.
Questa è la soluzione proposta e in questo caso lo schema assume
più un significato orientato al “load balancing”, visto che si mantiene
attivo un solo sensore per cluster e con adeguate tecniche di elezione
del cluster-head si può introdurre una politica di risparmio energia
grazie all’accensione/spegnimento selettivo dei vari nodi del gruppo.
L’utilizzo dello schema “cluster-based” permette all’intero gruppo
appartenente allo stesso cluster di essere identificato con il
medesimo
indirizzo; questa tecnica ha quindi il vantaggio di ridurre il numero di
indirizzi fisici da allocare mantenendo la possibilità di individuare
univocamente una parte della rete, inoltre si riducono i messaggi inviati che
non devono essere più ripetuti per ogni nodo appartenete al cluster, e si
riesce ad aumentare la ridondanza della rete e la risoluzione della misura
effettuata. Una organizzazione del genere affronta il problema della non
copertura di determinate zone nel corso di una procedura di monitoraggio;
infatti in ambito locale al cluster è applicato il concetto di ridondanza. La
stessa struttura può essere iterata su più livelli creando cluster di cluster,
65
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 3.3: Organizzazione in cluster della rete
fino a raggiungere il sink, il nodo di raccolta di tutte le informazioni e
d’interfaccia con reti esterne o con l’utente finale. La scelta del cluster head
può essere casuale, o può
tener conto delle risorse dei singoli nodi,
prediligendo come cluster head quello dotato di maggiore energia e meno
impegnato in comunicazioni radio; infatti è evidente che il ruolo di cluster
head richieda maggiori funzionalità, le quali coincidono con un più elevato
consumo di potenza.
È chiaro che è anche possibile assegnare periodicamente il compito di capo
cluster a nodi differenti, che in momenti diversi risultino i più idonei a
farsene carico.
Riepilogando partizionare in cluster una rete di sensori wireless può servire
sia in applicazioni di tipo Data gathering dove è richiesta una suddivisione
in aree ciascuna delle quali corrisponde, quanto più è possibile ad una certa
condizione ambientale, sia nel Direct Diffusion per eleggere una gerarchia
di nodi più importanti, detti sempre cluster-head [12], e delegare poi a questi
66
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
il compito di inoltrare l’interest nella rete, al posto di usare un banale
flooding.
Il clustering può essere effettuato con due approcci diversi:
Clustering centralizzato: l’algoritmo di clustering gira sul nodo base della
rete. La condizione necessaria è che il nodo base riceva tutti i dati dai
sensori. È evidente come questa tecnica vada a collidere con il concetto di
aggregazione, che tende a non far giungere al nodo base i dati relativi a tutti
i sensori, bensì solo i pacchetti di informazioni fuse e concentrate.
Clustering distribuito: è di gran lunga il più usato per supportare tecniche
di Data aggregation, Data gathering [11], e Direct diffussion [12]. Il
compito di partizionare in cluster viene decentralizzato e viene distribuito
su ogni nodo. Uno degli algoritmi di clustering distribuito più noto è il
DEM (Distributed Expectation Maximization [13]). Lo scopo è quello di
avere una partizione in cluster sempre aggiornata dei sensori, in base a delle
condizioni particolari che si verificano nell’ambiente. Si assume che ogni
nodo della rete rilevi dei dati (o degli eventi) che possono essere descritti da
un insieme di condizioni elementari. L’algoritmo produce una stima della
densità dei sensori per ciascuna di queste condizioni e rende quindi
possibile la clusterizzazione. Le elaborazioni avvengono localmente al
nodo, non è necessario quindi che i dati rilevati vengano inoltrati ad una
stazione centrale che effettua i calcoli. Inoltre l’algoritmo non richiede che i
sensori si scambino i dati effettivamente rilevati, ma solamente piccoli set
di dati statistici di aggiornamento. Un altro vantaggio degli algoritmi DEM
è che non producono trasmissioni simultanee; in altri termini è garantito
che, ad ogni intervallo temporale, l’algoritmo scambia uno e un solo
67
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
pacchetto di aggiornamento fra due nodi (ad uno o più vicinati di distanza).
Questa scarsa necessità di comunicazione rende l’algoritmo molto poco
pesante a livello di traffico introdotto sulla rete e quindi risulta facilmente
integrabile in qualsiasi applicazione che prevede una partizione in cluster o
una stima della densità.
3.5
CLUSTERING: STATO DELL’ARTE
Molti sono gli studi presenti in letteratura dedicati al clustering di reti di
sensori senza cavo e questi possono essere classificati in base all’approccio
seguito per effettuare proprio la procedura di clustering. In particolare
verranno trattati algoritmi basati su criteri di prossimità, potenza
trasmissiva, numero di hop (k-hop clustering), budget-based
Un primo lavoro è quello di Heinzelman et al [10] che propongono il
protocollo
LEACH
(Low
Energy
Adaptive
Clustering
Hierarchy)
appositamente ideato per applicazioni atte al monitoraggio ambientale.
L’approccio sul quale si basa il protocollo è fondato sulle seguenti 2
assunzioni: (i) esiste un'unica base station con la quale tutti i sensori
vogliono comunicare; (ii) tutti i sensori hanno la possibilità di comunicare
direttamente con la base station. Al fine di riguardare il consumo energetico
dei nodi il protocollo LEACH seleziona un numero p di sensori che fungono
da cluster-head, dove p è un parametro che deve essere esaminato dal punto
di vista ingegneristico a priori. I cluster-heads comunicano direttamente con
la base station e gli altri nodi inoltrano le proprie misurazioni attraverso i
cluster-heads (tipicamente quello più vicino a loro). Al fine di distribuire
equamente il consumo energetico dei nodi il protocollo LEACH implementa
una procedura di load-balancing che permette ai vari nodi di diventare
cluster-heads in differenti istanti temporali. Si prevede inoltre che un nodo
68
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
possa essere rieletto solo quando tutti i restanti candidati sono già stati eletti
almeno una volta. I risultati a cui Heinzelman et al giungono mostrano che il
protocollo LEACH riduce l’energia associata alla comunicazione di circa
otto volte rispetto alla trasmissione diretta (direct-transmission) e inoltre che
la durata energetica del primo nodo ad esaurirsi aumenta di circa 8 volte
rispetto al caso in cui è usato direct-transmission, mentre l’ultimo nodo si
esaurisce circa 3 volte dopo l’esaurimento dell’ultimo nodo negli altri
protocolli.
Lindsey et al. [44] proseguendo dai risultati ottenuti con il protocollo
LEACH proposero PEGASIS (Power-Efficient GAthering in Sensor
Information Systems), un protocollo in cui i nodi trasmettono le
informazioni al loro vicino più vicino e i messaggi sono trasmessi alla base
station basandosi su uno schema a catena. Il protocollo PEGASIS si è
dimostrato più robusto rispetto al LEACH nei riguardi dei fallimenti dei
nodi.
Subramanian e Katz [45] propongono invece delle linee guida per la
progettazione di reti di sensori auto-organizzanti in cluster. Viene posta
enfasi sull’importanza di implementare una struttura gerarchica al fine di
ridurre la complessità del routing per ogni nodo, in particolare viene
suggerito un approccio per il clustering nei quali i nodi “beginner”
(iniziatori) inviano un “solicitation message” a tutti i nodi che possono
ascoltarli. In ogni round dell’algoritmo gli iniziatori incrementano la loro
potenza trasmissiva e il processo di clustering continua fin quando il numero
dei nodi che rispondono sono compresi tra limite min e max di nodi per
cluster.
L’approccio utilizzato da Subramanian e Katz è molto simile all’
“Expanding Ring” di Ramamoorthy et al [46], fatta eccezione per il fatto
che i nodi “beginner”ora non incrementano la loro potenza trasmissivo ma il
numero di hop. Facciamo notare però che questo tipo di approccio può avere
69
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
una complessità nel caso peggiore molto alta in quanto dipende dal numero
totale di sensori presenti nella rete più che dallo specifico limite sulla
dimensione del cluster.
Una soluzione alternativa alla realizzazione di cluster con limitate
dimensioni e con un overhead di messaggi basso è l’approccio budget-based
clustering. In questo tipo di algoritmi al nodo iniziatore (cluster-head) è
assegnato un budget iniziale. Il cluster-head inizia col distribuire il proprio
budget ai suoi vicini i quali a loro volta fanno lo stesso fin quando il budget
non è esaurito. Questo tipo di approccio permette una crescita dei vari
cluster basandosi su decisioni locali al nodo ed evitando di coinvolgere i
cluster head in ogni round, diminuendo in questo modo l’overhead dei
messaggi. Controllando quindi il budget allocato per la formazione del
cluster si è in grado di controllare il numero superiore alla dimensione del
cluster. Krishnan e Starobinski [47] propongono due algoritmi per budgetbased clustering: rapid e persistent. Entrambi astraggono dal numero e dalla
dislocazione delle base station nella rete e non considerando l’assunzione
della connettività diretta (molto utile quando si considerano scenari reali nei
quali ci sono da considerare possibili ostacoli durante la trasmissione). Il
lavoro si pone di tener in considerazione: (i) l’efficienza dei messaggi che è
cruciale per mantenere limitati i requisiti di banda e il consumo energetico
dei sensori, (ii) la necessità di avere dimensioni dei cluster limitate in modo
da avere un impatto favorevole sulle performance dei protocolli di routing e,
(iii) scelta di adeguati budget per la procedura di clustering al fine di
controllare le dimensioni e il numero di cluster prodotti.
Una evoluzione allo studio di Krishnan e Starobinski è proposto da
Tzevelekas et al [48] dove è descritta una metodologia intelligente di
distribuzione dei budget ai vicini. L’idea è quella di far si che i nodi possano
tenere in considerazione le caratteristiche dei propri vicini al fine di stabilire
politiche per la distribuzione del budgets.
70
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
In [49] viene proposto un algoritmo intelligente per lo sviluppo di reti di
sensori wireless organizzate in cluster ed energeticamente efficienti, nel
quale ogni nodo sensore decide se effettuare l’operazione di “join” a un
cluster o se restare in uno stato di funzionamento peer to peer basando la sua
scelta sulla densità dei sensori nell’area e sul suo livello energetico.
Il lavoro proposto da Guo [50], invece, pone l’attenzione sullo sviluppo di
un metodo di formazione di cluster efficiente dal punto di vista dei costi.
Tuttavia il metodo agisce posizionando “sentinelle” (cluster head CH) al
centro di ogni cluster e assume che la topologia della rete e del numero di
cluster presenti sia nota.
Il protocollo distribuito HEED proposto in [51] , assume di eleggere i
cluster heads in base alla loro energia residua e non tenendo conto della
distribuzione dei nodi. Infatti HEED presuppone che la distribuzione dei
nodi sensori nella rete sia uniforme. Questo approccio però presenta
l’evidente problema che si possa verificare una situazione nella quale tutti i
cluster head sono localizzati in una regione specifica della rete considerata.
Altri lavori come [52,53,54] si sono invece incentrati su k-hop clustering
algorithm disinteressandosi però di considerare la completa totalità dei
vincoli riguardanti la formazione dei cluster, infatti in [52,53] si considera
solo il vincolo relativo al numero di nodi all’interno del cluster mentre in
[54] ci si basa solo sul cluster-radius. Più in particolare in [53] si
presuppone che un nodo possa essere incluso in un numero costante di
cluster e che l’intersezione di due cluster possa includere un piccolo numero
di nodi.
Bejerano [55] basa invece la suddivisione in cluster della rete su un
algoritmo di approssimazione polinomiale in modo da avere un numero
minimo di cluster disgiunti. Al fine di considerare il problema del clustering
e al tempo stesso rispettare i vincoli di QOS, Bejerano propone di
suddividere il problema in due parti. Il primo mira a ricercare il minimo
71
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
numero di cluster disgiunti che contengono tutti i nodi della rete sempre nel
rispetto di un estremo superiore al cluster radius. Il secondo invece propone
di considerare uno spanning tree in ogni cluster e di prevedere che i cluster
che violano il vincolo di carico max e di cluster size vengano ulteriormente
suddivisi in sottocluster. Si assume in questa accezione che ogni nodo abbia
un peso (rappresentante la sua richiesta di banda) e che il totale di pesi di
tutti i cluster sia limitato. Infine viene introdotto un meccanismo per
massimizzare il throughput di ogni cluster senza violare i requisiti di QOS.
Infine Aoun e Boutaba [56], analizzano il problema del clustering sottoposto
a limiti superiori per quanto riguarda la latenza e il consumo di energia dei
nodi intermedi. Il lavoro complementa i lavori precedenti di Bejerano e
Gupta in quanto tiene in conto anche del problema della formazione dei
cluster (nel rispetto di un limite superiore sul cluster-radius, sulla
dimensione del cluster e sul traffico trasmesso) e della scelta dei vari
cluster-head. In particolare ogni cluster sarà dotato di un nodo che fingerà
da gateway verso il nodo base e servirà quindi i nodi presenti all’interno del
cluster. Il lavoro prevede che ogni nodo sia associato ad un gateway e che
possa sceglierne un altro in caso di “path failure”.
3.6
APPROCCIO PROPOSTO PER IL CLUSTERING
Dai precedenti paragrafi è emerso come il clustering risulta un’ottima
soluzione per implementazione di strategie di fault-tolerance e anche per la
gestione del problema della copertura di zone monitorate. Dal paragrafo 3.5
si è potuto constatare anche come molti sono stati gli studi atti
all’individuazione di protocolli energeticamente efficienti per il clustering.
In questo lavoro di tesi l’esigenza di aumentare quanto più possibile la vita
di una rete è particolarmente sentita e per questo si è pensato di sfruttare il
protocollo di clustering unitamente al paradigma di leader-election
periodico all’interno di ogni cluster. Questo approccio sembra avvicinarsi
72
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
molto al protocollo PEGASIS proposto da Lindsey et al. [44] , ma presenta
una interpretazione del tutto diversa del concetto di cluster-head. Per
chiarezza consideriamo una WSN dotata di un nodo sink e di un cluster A e
un cluster B, dove con X0…Xn-1 indichiamo i mote appartenenti al cluster A
e con Y0…Ym-1 i mote appartenenti al cluster B. Supponiamo che i nodi X0
e Y0 siano rispettivamente i cluster-head. Secondo Lindsey i nodi X0 e Y0
saranno rispettivamente quelli che dovranno incaricarsi dell’inoltro delle
misurazioni effettuate dagli altri mote all’interno del cluster (cioè dei nodi
X1..Xn-1 e Y1…Yn-1 rispettivamente), in altri termini fungono da intermediari
tra i sensori appartenenti al cluster A e cluster B e il nodo sink. In questa
accezione la scelta di avere una procedura di leader-election periodica è
nell’ottica di scegliere dinamicamente il nodo dotato di uno “stato di salute”
migliore e in grado di comunicare con il nodo sink nel modo
energeticamente più efficiente.
In questo lavoro di tesi questo concetto viene ulteriormente estremizzato
considerando il cluster-head come l’unico nodo delegato alla misurazione
durante un ciclo di monitoraggio. In questo caso quindi i nodi X1..Xn-1 e
Y1..Yn-1 non saranno soggetti al carico computazionale dovuto alla
procedura di misurazione e avranno solo un ruolo passivo all’interno della
rete. Più in particolare si possono prevedere due scenari: un primo in cui i
suddetti nodi svolgeranno le usuali azioni atte al forwarding dei pacchetti
provenienti dagli altri nodi e all’aggiornamento delle tabelle di routing per il
funzionamento del protocollo multihop., e un secondo in cui i nodi sono
completamente spenti e saranno previste procedure di risveglio solo per
partecipare alla procedura di elezione di un nuovo leader. Riguardo la
procedura di leader-election, risulta chiaro, in questo caso, che è intesa
maggiormente nell’ottica di load-balancing e potrà essere sviluppata in
qualsiasi modo e quindi sia seguendo un paradigma che mira a eguagliare i
tempi di carico dei vari mote, sia seguendo un paradigma che mira a rendere
73
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
il consumo energetico dei mote all’interno dello stesso cluster quanto più
uniforme possibile.
3.6.1
Procedura di elezione del leader
Riguardo la procedura di leader-election la rete è stata addestrata seguendo
sostanzialmente due linee guida:
1. chi effettua l’elezione;
2. intervallo temporale in cui un nodo è cluster head
Dalla combinazione delle due possono essere ricavati quattro scenari
diversi, in particolare una prima soluzione ha previsto di delegare la
procedura di elezione ai nodi del cluster prevedendo un rate periodico di
attivazione della procedura per l’elezione di un nuovo leader. Una seconda,
invece, ha previsto un algoritmo centralizzato dove è il nodo sink a decidere
il futuro leader di un cluster e prevedendo una nuova elezione solo nel
momento in cui un nodo leader ha esaurito le proprie riserve energetiche.
Riguardo la prima soluzione l’algoritmo di elezione distribuito scelto
all’interno del cluster è stato una sorta di election ring opportunamente
modificato per adattarsi al meglio alle caratteristiche delle reti di sensori
senza cavo. Ovvero si prevede che ogni cluster sia organizzato in un anello
logico dove ogni nodo sensore diventa cluster-head nel caso in cui abbia un
token che gli può essere stato assegnato dall’inizio o ceduto da un altro nodo
sensore. L’algoritmo è stato preferito rispetto all’algoritmo di Garcia Molina
(algoritmo del prepotente o del bully), soprattutto per il basso carico
computazionale della procedura di elezione. Volendo essere più precisi in
questo caso la procedura di elezione è ridotta al minimo ma ciò ben si sposa
con l’obiettivo di evitare quanto più è possibile sprechi di energia e
distribuire quanto più è possibile il carico tra i nodi sensori. La gestione di
nodi che esauriscono le proprie riserve energetiche e di fallimenti nelle
74
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
comunicazioni possono essere gestite in maniera efficiente tramite varie
politiche. La situazione che potrebbe verificarsi è quella in cui il nodo
candidato a diventare il prossimo cluster-head sia non raggiungibile o a
causa di una degradazione del collegamento o a causa del suo esaurimento
energetico. In questi due casi il nodo che attualmente riveste il ruolo di
leader può avere sia un approccio ottimistico e quindi rimanere ancora
leader per un altro ciclo di misurazione (tentando poi di ricontattarlo nella
successiva fase di elezione) o tentare di contattare il prossimo nodo
dell’anello logico, ancora attivo. Riguardo la scelta del nuovo cluster-head
ovvero del sensore a cui cedere il token si possono immaginare algoritmi
che scelgano in base allo stato di salute generale dei vari nodi, rifacendosi in
generale a PEGASIS o HEED, però anche se ciò tiene maggiormente in
conto lo stato di “salute” generale del cluster, dall’altro si ha un notevole
incremento dei messaggi che i vari nodi sensori devono scambiarsi al fine di
poter prendere una decisione.
La seconda soluzione prevede invece che sia il nodo sink a distribuire i
token. In questo caso si presuppone che il nodo delegato al ruolo di leader
resti lo stesso fino al suo esaurimento energetico, dopodichè sarà sempre il
nodo sink ad eleggerne un altro.
3.7
ALGORITMI DI TRASPORTO AFFIDABILE
Fino ad ora è si sono presi in considerazione aspetti quali il clustering e
l’elezione al fine di aumentare la vita media della rete però non è stato
ancora trattato il problema di avere un protocollo di trasporto che sia
affidabile e che quindi si incarichi del recapito affidabile delle misurazioni
presso il nodo sink.
Il problema di avere una trasmissione affidabile tra nodi sensori remoti
anche in presenza di più passi di comunicazione (multihop), di errori sui
canali, di collisioni e di congestione ha le seguenti dimensioni:
75
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
1. trasmissione di : pacchetti singoli vs blocchi di pacchetti vs stream
di pacchetti in quanto il recapito affidabile di singoli pacchetti può
essere importante ad esempio per dati aggregati, quello di blocchi
adatto per applicazioni che usano meccanismi di disseminazione di
query nella rete, mentre quello di stream adatto per applicazioni col
compito di consegna periodiche di gruppi di misurazioni
2. recapito garantito vs recapito stocastico in quanto per alcune
applicazioni può essere necessario un alto livello di affidabilità,
come le query distribuite, ect mentre altre possono anche tollerare
perdite purchè contenute in un certo range (ad esempio quando
molti sensori provvedono ad inviare misurazioni correlate tra di
loro);
3. dai nodi sensori al sink vs dal nodo sink ai sensori
e in questo
caso si parla di “forward path” quando il flusso è quello che parte
dai nodi e arriva al Sink e di “reverse path” quando il flusso
interessa i dati inviati dal sink verso i nodi della rete.
Il “Reliable Multi-Segment Transport” (RMST) proposto da Heidemann et
al. [61] e il “Pump Slowly, Fetch Quickly” (PSFQ) di Wan et al. [62]
realizzano un protocollo di trasporto per il recapito al sink di blocchi di
pacchetti. L’RMST fu progettato per essere utilizzato unitamente al direct
diffusion [63] e prevede uno schema di recapito dei pacchetti di tipo “endto-end”. Il protocollo è basato su l’utilizzo selettivo di messaggi NACK e
può essere usato secondo due schemi: “caching mode” e “non caching
mode”. Secondo il primo schema un numero di nodi lungo un percorso, ad
esempio quello utilizzato dal direct diffusion per recapitare i dati al nodo
sink, sono denominati come “RMST node”. Ogni RSMT node provvede a
memorizzare in cache i frammenti di dati che compongono il flusso di
comunicazione, e a mantenere un timer associato ad ogni flusso di
comunicazione. Quando un frammento non è ricevuto prima che il timer sia
76
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 3.4: Architettura protocollo RMST
scaduto viene inviato un NACK sul percorso e il primo RMST node che ha
l’informazione richiesta provvede a ritrasmetterla. Il sink in questo caso
agisce come ultimo RMST node e risulta essere l’unico se si utilizza la
modalità non caching. Gli svantaggi di questo tipo di protocollo sono
principalmente legati: 1) al meccanismo di caching che richiede un
significativo overhead in termini di potenza dissipata per le operazioni di
mantenimento e 2) al problema di essere legati al direct diffusion.
Il protocollo PSFQ proposto da Wan et al.[62] è molto simile al RMST solo
che opera sul “reverse path” ovvero da sink a nodi sensore e comprende tre
funzioni:
1. trasmissione dei messaggi velocemente (operazione di pump)
2. recupero veloce da errori di trasmissione (operazione di fetch)
3. monitoraggio dello stato selettivo (operazione di report).
Ogni nodo intermedio mantiene i dati in una cache; quando viene ricevuto
un pacchetto il nodo controlla il contenuto confrontandolo con quelli
contenuti in cache e vengono scartati i duplicati. Se il pacchetto ricevuto
non era contenuto in cache allora significa che è nuovo, di conseguenza
viene decrementato il campo TTL e viene inoltrato ai vicini nel caso in cui il
TTL non sia uguale a zero e non vi siano salti nei numeri di sequenza dei
pacchetti. Nel caso in cui è rilevato un salto nei numeri di sequenza allora il
77
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
nodo effettua una operazione di fetch richiedendo una ritrasmissione ai nodi
vicini. Anche questo protocollo risulta molto oneroso in termini di potenza
dissipata e inoltre presenta anche un grosso inconveniente, in quanto la
reliability hop by hop non garantisce la reliability end-to-end.
Lo schema sviluppato nel protocollo GARUDA [64] molto simile al PSFQ è
mirato al trasporto affidabile di blocchi di dati dal nodo sink a tutti gli altri
sensori o a una parte significativa della rete. Questo protocollo usa uno
schema basato su messaggi di NACK e fa molta attenzione che il primo
pacchetto di un blocco sia recapitato in modo affidabile a tutti i sensori. In
questo modo viene risolto il problema degli schemi basati sui messaggi
NACK ovvero i destinatari devono ricevere almeno un pacchetto del blocco
affinché possano accorgersi delle perdite di ulteriori pacchetti.
I protocolli fino ad ora descritti sono stati concepiti per assicurare una
affidabilità di tipo end to end a livello di pacchetti. Akyildiz, invece propone
ESRT (Event to Sink Reliable Transport) un protocollo per gestire la
reliability sulla forward path di tipo end to end orientata invece a stream di
pacchetti e in particolare quindi agli eventi che vengono monitorati in una
rete di sensori senza cavo. La conoscenza su un fenomeno viene calcolata
basandosi sul numero di pacchetti ricevuti; definendo con r il numero di
pacchetti ricevuti in un intervallo di decisione e con R il numero di pacchetti
richiesti per poter definire che l’osservazione dell’evento è “reliable” allora
possiamo dire che se r>R
allora la rilevazione dell’evento può essere
definita come affidabile dal punto di vista della trasmissione delle
misurazioni. Nel caso in cui r<R allora la soluzione proposta dal protocollo
ESRT è quella di modificare la frequenza con cui i nodi sensori provvedono
a recapitare le informazioni al nodo sink. Inoltre l’ESRT usa un
meccanismo di rilevazione della congestione basato sul monitoraggio del
livello del buffer locale di ogni nodo. Ogni sensore il cui buffer va in
overflow è detto congestionato e informa il Sink in modo che il calcolo della
78
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Direzione
Orientamento
Stile
Uso di NACK
Risparmio
energetico
Recupero
perdite
Uso di cache
Controllo della
congestione
RMST
Sensor to sink
Pacchetto
Hop-by-hop
Si
GARUDA
Sink to sensor
blocco
Hop-by-hop
Si
PSFQ
Sink to sensor
pacchetto
Hop-by-hop
Si
ESRT
Sensor to sink
stream
End-to-end
No
-
-
-
Si
Si
Si
Si
-
Si
Si
Si
-
no
no
no
si
Tabella 3-1:Schema riassuntivo dei protocolli di trasporto affidabili
nuova frequenza con cui i nodi sensori dovranno recapitare le loro
informazioni sia influenzata dallo stato generale della rete. Maggiori
informazioni su un esempio di protocollo appositamente progettato per il
controllo della congestione sul “forward path” si possono reperire in [65]
dove è presentato CODA (Congestion Detection and Avoidance).
Uno schema riassuntivo dei protocolli analizzati viene riportato nella tabella
3-1.
3.8 APPROCCIO PROPOSTO PER IL TRASPORTO
AFFIDABILE DELLE MISURAZIONI
Anche se sono stati proposti molti protocolli per raggiungere affidabilità
nella trasmissione delle informazioni in reti di sensori senza cavo, nessuno
di essi è stato standardizzato. Del resto anche questi protocolli sono molto
suscettibili all’applicazione nella quale questi vengono utilizzati e di
conseguenza risulta difficile effettuare una scelta che sia definitiva per ogni
ambito applicativo. Ritornando ai requisiti espressi nel paragrafo 3.1,
bisogna naturalmente tener conto nella scelta della necessità di avere un
79
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
protocollo di consegna dei dati energeticamente efficiente. Dalla tabella 3.1
risulta chiaro che l’unico protocollo che tiene conto del risparmio energetico
è il protocollo ESRT (per stream di pacchetti) il quale si basa sull’idea di
poter cambiare la frequenza con cui i nodi sensori recapitano le
informazioni al nodo sink. Tenendo conto che il fine del lavoro è la
valutazione di protocolli energeticamente efficienti e riuscire ad ottenere
metriche per la valutazione complessiva della dependability del sistema, si è
deciso di ricorrere a un semplice protocollo di tipo end-to-end in cui
venissero utilizzati un numero minimo di trasmissioni di pacchetti al fine di
limitare al minimo il consumo energetico dei mote.
L’idea di seguire un tale approccio è del resto giustificata in quanto non è
detto che in ogni trasmissione vi siano perdite quindi può risultare utile
dotare il nodo sink della intelligenza sufficiente per effettuare una
operazione di monitoraggio dello stato della rete basandosi unicamente sui
pacchetti ricevuti in instanti precedenti dai nodi sensori. Sarà compito
quindi del nodo sink provvedere all’inoltro delle richieste di ritrasmissione
dirette ai sensori dai quali non ha ricevuto nessuna risposta in quanto sarà
esso stesso ad avere una chiara situazione della copertura raggiunta in ogni
ciclo di misurazione.
Secondo questo paradigma i nodi sensori sono semplicemente ridotti ad
entità passive che effettuano cicli di misurazione su richiesta e provvedono
all’inoltro delle misurazioni al nodo sink. Rispetto quindi ai protocolli
accennati nel precedente paragrafo non dovranno gestire nessuna cache
interna e non dovranno monitorare lo stato della rete. L’unica informazione
conservata dai sensori sarà la stima dell’ultima misurazione effettuata, al
fine di poterla rispedire nel caso in cui arrivi una richiesta di ritrasmissione
da parte del nodo sink.
Per essere più chiari sulla dinamica dell’algoritmo consideriamo lo scenario
di figura 3.5. La rete risulta composta da 8 nodi sensori atti al monitoraggio
80
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 3.5: Rete composta da otto dispositivi sensori
di una particolare zona. Tutti i nodi sensori effettueranno la misurazione su
richiesta del nodo sink e provvederanno all’invio della misura. Il sink
quindi, in assenza di collisioni, errori di trasmissioni, ect, riceverà un totale
di 8 misurazioni con copertura della rete al 100%. A questo punto
consideriamo le situazioni anomale che possono occorrere:
1. Trasmissione fallita a causa di collisioni, pacchetti corrotti, ect.;
2. Esaurimento energetico del dispositivo che causa una non
trasmissione della misurazione.
Riguardo il primo problema il protocollo proposto prevede di attivare una
procedura di recupero di eventuali perdite di informazioni effettuando un
massimo numero di tentativi (NRO_MAX_REQUEST_COVERAGE) per cercare di
raggiungere la copertura della rete dopo i quali la copertura completa
fallisce.
Il secondo problema, invece non viene risolto e risulta essere gravoso nei
confronti delle operazioni di monitoraggio soprattutto se si è previsto
l’utilizzo di un unico sensore per la rilevazione di una grandezza di
interesse.
81
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 3.6: Rete organizzata in 3 cluster senza procedura di elezione di cluster-head
3.9
CLUSTERING E LEADER ELECTION
In merito all’esaurimento energetico di un dispositivo che causa una non
trasmissione delle misurazioni, un approccio basato sulla organizzazione in
cluster della rete può venire in aiuto.
Consideriamo lo scenario di figura 3.6 in cui la rete risulta organizzata in 3
cluster: A, B e C rispettivamente di 3,3 e 2 nodi sensori dove non è prevista
nessuna procedura di leader election (§ 3.6.1), cioè tutti i nodi sensori
effettueranno la misurazione su richiesta del nodo sink e provvederanno
all’invio. Il sink quindi, in assenza di collisioni, errori di trasmissioni, ect,
riceverà un totale di 8 misurazioni afferenti ai tre cluster con copertura della
rete al 100%.
Poiché la clusterizzazione (§ 3.4) prevede di suddividere l’area da
monitorare in zone di interesse, si può affermare che nel caso di ricezione
di almeno n=1 misurazioni per cluster la copertura globale della rete è
raggiunta e quindi non sorgono problemi né per il punto 1 né per il punto 2
menzionati nel precedente paragrafo. Si può concludere affermando che si
hanno a disposizione un margine di 2 non recapiti di misurazioni per i
cluster A e B e di uno per il cluster C al fine di ottenere una completa
copertura della rete senza “overhead” aggiuntivi dovuti a trasmissioni di
82
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
pacchetti nella rete per avviare l’operazione di richiesta di ritrasmissioni.
Scendendo più in dettaglio sulla dinamica dell’approccio viene previsto un
massimo numero di tentativi (NRO_MAX_REQUEST_COVERAGE) a disposizione
del nodo sink per cercare di raggiungere la copertura della rete dopo i quali
la copertura completa fallisce. Questo semplice scenario mette in luce ancor
di più come il concetto di “clusterizzazione” risulta essere alla base per
l’implemetazione di strategie di tolleranza di guasti sia transienti che
permanenti e come ci venga in aiuto soprattutto per “rilassare” il requisito di
avere un trasporto affidabile. Infatti l’utilizzo di un protocollo come l’ESRT
o simili avrebbe immediatamente attivato meccanismi di ritrasmissione con
il coinvolgimento di tutti i nodi che componevano il “transmission path”.
Ciò avrebbe portato ad un overhead in termini di banda e energia spesa
anche se la copertura della rete era stata comunque raggiunta.
Detto ciò analizziamo ora il caso di figura 3.7 ovvero lo scenario che vede
una rete organizzata in cluster in cui in ogni cluster viene applicata la
procedura di leader election (§ 3.6.1). La situazione in questo caso è un po’
più complessa in quanto saranno interessati da misurazioni solo i relativi
cluster-head e non più tutti i dispositivi che fanno parte del cluster e quindi
diminuisce il margine di errori di trasmissioni che si possono tollerare prima
Figura 3.7: Organizzazione in cluster della rete con cluster-head
83
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
di dover ricorrere a ritrasmissioni ( e quindi ad un overhead aggiuntivo).
Questo ultimo scenario risulta essere un ottimo trade-off tra la necessità di
ridurre al minimo le possibilità di congestione della rete e implementare
politiche mirate al risparmio energetico dei nodi.
84
Capitolo 4
Valutazione comparativa degli algoritmi
4.1
OBIETTIVI
L’obiettivo di questo capitolo è effettuare una analisi comparativa dei
protocolli proposti nel precedente capitolo per il problema del trasporto su
reti di sensori senza cavo. Il tool di sviluppo utilizzato per i vari test è stato
Tossim Tinyviz.
Le caratteristiche che si prenderanno in considerazione durante le
simulazioni che verranno testate saranno principalmente:
1. Il numero di nodi che costituiscono la rete (tipicamente da 9 a 18
nodi sensori);
2. il protocollo di trasporto utilizzato per il recapito delle misurazioni
nel percorso dai sensori al nodo sink (forward path);
3. la topologia della rete (organizzata in cluster o non organizzata in
cluster)
e si andrà a verificare come il variare delle caratteristiche impatti su:
o copertura raggiunta;
o consumo energetico dei nodi.
Obiettivo interessante è riuscire a comprendere per i vari scenari che
verranno testati come la copertura della rete è influenzata dal numero di
85
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
dispositivi utilizzati al fine di trovare un “trade-off” tra costi di realizzazione
della rete e percentuale di copertura che si vuole raggiungere. A tutto ciò è
poi aggiunto l’esigenza di ottenere soluzioni che possano aumentare il più
possibile la durata media della vita di una rete di sensori senza cavo ovvero
soluzioni che mirino ad un consumo minimo delle risorse energetiche dei
nodi.
Per caratterizzare al meglio le misure ottenute dalla simulazione si è deciso
di analizzare i parametri suddetti in due possibili scenari:
1) con l’utilizzo della plugin Tinysan [70] che offre sia la possibilità di
simulare la qualità dei link (simulando aleatorità nella probabilità di
consegna dei pacchetti) che la possibilità di avere una stima del
consumo energetico dei nodi;
2) senza l’utilizzo della plugin Tinysan.
Il secondo scenario naturalmente presenta delle limitazioni però risulta
essere utile soprattutto per capire la scalabilità della rete, all’aumentare del
numero si sensori utilizzati e in particolar modo quanto l’aumento dei
sensori impatti sulla copertura raggiunta. Infatti con l’uso della plugin
Tinysan si ottiene una aleatorietà nelle probabilità di consegna dei pacchetti
(a causa del cambiamento delle probabilità sui link di comunicazione) che
non permette di avere uno scenario unico dove poter effettuare i vari test in
modo univoco.
Quindi con la combinazione dei due approcci possono
essere esaminati sia il problema delle collisioni dovute a trasmissioni
contemporanee dei nodi, sia la perdita dei pacchetti dovuta alla qualità dei
link tra i sensori che costituiscono la rete.
4.2
DATA GATHERING BASE
Lo scenario comune che è la base delle varie simulazioni effettuate prevede
il monitoraggio di un’area attraverso il tool di simulazione per reti di sensori
86
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
NOME PROGETTO
OBIETTIVI
PROTOCOLLO DI TRASPORTO
USATO
TOPOLOGIA DELLA RETE
Simple_Data_Gathering
Il nodo con ID 0 è incaricato della raccolta
dati da tutti gli altri sensori nella rete.
Best-effort
Non previsto uso di cluster
Tabella 4-1: Caratteristiche della simulazione n°1
senza cavo Tossim. Si suppone che le richieste di misurazione vengano
effettuate dal nodo base (sink) con una certa frequenza periodica che può
essere sincrona con il clock locale del nodo sink o eventualmente asincrona
nel caso in cui si provveda all’implementazione di una interfaccia che
consenta all’operatore umano di inoltrare a proprio piacimento richieste di
misurazioni. Le caratteristiche principali della simulazione sono riportate in
tabella 4.1. Supponiamo, che i sensori siano dislocati nell’area di cui si
vuole effettuare una analisi, in modo tale da avere un solo sensore per ogni
zona dalla quale si esige una misura. La possibile architettura della rete è
Figura 4.1: Architettura della rete in Tinyviz
87
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
mostrata in figura 4.1 dove si individuano 9 nodi sensori, di cui quello con
id pari a 0 (nodo più a destra) è il nodo sink mentre gli altri sono i nodi
addetti alle misurazioni. Le linee punto punto in grigio rappresentano i
collegamenti che godono di una probabilità di perdita dei pacchetti inferiore
al 30%, mentre quelli in rosso collegamenti con probabilità compresa tra il
30% e il 70%. Risulta chiaro, dalle caratteristiche esposte in tabella 4.1, che
per avere una completa caratterizzazione dell’evento monitorato è
necessario che ogni sensore recapiti la propria misurazione/i al nodo sink,
quindi una perdita di pacchetto dovuta alla congestione della rete o alla
bassa qualità del link tra i nodi causerà una situazione in cui il nodo sink
non avrà a disposizione tutte le informazioni necessarie al monitoraggio
della zona interessata.
Riguardo lo schema implementativo dell’applicazione questo risulta essere
molto semplice e uno stralcio del file di configurazione è presentato in
configuration Simple_Data_Gathering {}
implementation {
components Main, SurgeM, TimerC, LedsC, NoLeds, Photo, RandomLFSR,
GenericCommPromiscuous as Comm, Bcast, MultiHopRouter as
multihopM, QueuedSend, Sounder;
....
SurgeM.TimerControlCoverage -> TimerC.Timer[unique("Timer")];
SurgeM.MeasureTimer -> TimerC.Timer[unique("Timer")];
1
SurgeM.RouteControl -> multihopM;
SurgeM.Send->multihopM.Send[AM_SURGEMSG];
multihopM.ReceiveMsg[AM_SURGEMSG]->Comm.ReceiveMsg[AM_SURGEMSG];
//Per mandare e ricevere messaggi di misurazione
SurgeM.SendMeasureMsg -> Comm.SendMsg[AM_MEASUREMSG];
SurgeM.ReceiveMeasureMsg -> Comm.ReceiveMsg[AM_MEASUREMSG];
//usato dal sink per ricevere le misure
SurgeM.ReceiveMeasure -> Comm.ReceiveMsg[AM_SURGEMSG];
Figura 4.2: Stralcio del file di configurazione della prima simulazione
88
3
2
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
event TOS_MsgPtr ReceiveMeasure.receive(TOS_MsgPtr receivedMessage) {
int i;
if(TOS_LOCAL_ADDRESS==0 && receivedMessage->addr==0x7e)
{
SurgeMsg * payload;
payload2 = (TOS_MHopMsg *)receivedMessage->data;
payload = (SurgeMsg *)payload2->data;
dbg(DBG_TEMP," Msr DAL NODO: %d \n",payload2->originaddr);
for(i=0;i<NRO_MAX_MEASURE;i++)
dbg(DBG_TEMP,"->VALORE: 0x%x ",payload->reading[i]);
setCoverage();
}
return receivedMessage;
}
Figura 4.3: Evento ReceiveMeasure attivato sul nodo sink alla ricezione della
misurazione
figura 4.2 attraverso il quale si possono comprendere i componenti che
costituiscono l’applicazione e come sono legati tra di loro. Di particolare
interesse sono i due Timer (riquadro 1) utilizzati: MeasureTimer e
TimerControlCoverage. Il primo timer temporizza le richieste di
misurazioni effettuate dal nodo sink, mentre il secondo viene sempre
attivato dal nodo sink e serve per effettuare il controllo della copertura
ottenuta sulla rete. Nel riquadro 2 sono invece evidenziati i collegamenti
utili all’utilizzo del protocollo multihop, mentre il riquadro 3 mette in luce i
collegamenti con i componenti che gestiscono la comunicazione tra i nodi.
In figura 4.3 viene invece mostrata l’implementazione dell’ evento
ReceiveMeasure attivato dal nodo sink ad ogni ricezione di un messaggio di
misurazione dai nodi sensori. Le operazioni svolte alla ricezione sono 2:
o Estrazione della misurazione/i dal pacchetto dati ricevuto;
o Settaggio della copertura raggiunta al fine di avere statistiche
relative ai nodi che hanno risposto alle richieste di monitoraggio
(metodo setCoverage).
Un primo test è stato condotto al fine di comprendere quanto il numero dei
sensori utilizzati influisse sulla copertura raggiunta. Si è quindi seguito
89
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 4.4: Andamento % della ricezione delle misurazioni
al crescere del numero di nodi.
l’approccio 2 illustrato nel paragrafo 4.1 (ovvero si tralascia l’utilizzo della
plugin TinySan); i risultati ottenuti hanno mostrato una copertura totale
della zona monitorata nel 94% delle misurazioni usando un numero di nodi
pari a 9. La percentuale di raggiungimento di una completa caratterizzazione
del fenomeno va poi decrescendo linearmente all’aumentare dei nodi sensori
come illustrato in figura 4.4. Con questo test si comprende come
all’aumentare del numero di nodi aumenti la probabilità di collisione dei
pacchetti dovuto a congestione della rete e quindi come sia più facile avere
perdite di informazioni al nodo sink.
Se consideriamo invece l’approccio 1 (§ 4.1) che prevede l’utilizzo della
plugin Tinysan si può notare come la percentuale di corretta ricezione delle
misurazioni presso il nodo sink, in ogni ciclo di misurazione, cominci a
diventare molto più bassa. Infatti secondo questa metodologia la possibilità
che la misurazione venga trasmessa correttamente al nodo sink dipende non
solo dalla possibile congestione della rete ma anche dalla probabilità
intrinseca di trasmissione sul singolo link simulata appunto con l’utilizzo
della plugin TinySan. Come si può osservare in figura 4.5, ad eccezione del
caso con 12 sensori in cui la % di corretta ricezione aumenta rispetto al caso
90
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 4.5: Andamento % della ricezione delle misurazioni
con utilizzo della plugin TinySan.
precedente, l’andamento segue prettamente una funzione lineare decrescente
al crescere del numero di nodi utilizzati all’interno della rete. È chiaro che i
dati sono puramente statistici e dipendono molto dalla funzione che
caratterizza la qualità trasmissiva del link attraverso cui avviene la
comunicazione sul singolo canale e dalle rotte scelte dai sensori per inoltrare
le misurazioni al nodo sink.
4.3
DATA GATHERING AFFIDABILE
Partendo dalla applicazione descritta nel paragrafo 4.2 viene ora
implementato uno schema di comunicazione affidabile per il recapito delle
misurazioni al nodo sink (in tabella 4.2 sono riportate le caratteristiche alla
NOME PROGETTO
OBIETTIVI
PROTOCOLLO DI TRASPORTO
USATO
TOPOLOGIA DELLA RETE
Reliable_Data_Gathering
Il sink è incaricato della raccolta dati da tutti
gli altri sensori nella rete.
Affidabile end-to-end (max 2 ritrasmissioni)
Non previsto uso di cluster
Tabella 4-2: Caratteristiche della simulazione n°2
91
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
base della seconda simulazione). Lo sviluppo della applicazione ha ricalcato
l’approccio descritto nel paragrafo 9 e in figura 4.6 viene riportato uno
stralcio della procedura seguita dal nodo sink per assicurarsi di ricevere le
misurazioni dai nodi sensori.
Come si può intuire scatta un controllo del livello di copertura (riquadro 1)
che mira ad individuare i nodi che non sono stati in grado di recapitare le
loro informazioni al nodo sink e nel caso in cui non si è ancora raggiunto il
numero massimo di richieste possibili per ricercare una copertura completa
della rete (riquadro 2) si provvede ad una nuova richiesta di misurazione. Il
protocollo opera secondo uno schema di ritrasmissione end-to-end ma è
attivato solo nel momento in cui il nodo sink si accorge di non avere a
disposizione misurazioni provenienti da determinati nodi sensori; la
event result_t TimerControlCoverage.fired() {
…//dichiarazioni iniziali omissis
//controllo livello di copertura
for(i=1;i<TOTAL_NUMBER_MOTE;i++)
{payload_cov->unavailable_mote[i]=FALSE;
if(!measure_coverage[i]){ //compongo la nuova richiesta
payload_cov->unavailable_mote[i]=TRUE; must_send=TRUE; }
}
1
2
//significa che ho trovato cluster non coperti dalla misurazione
if(must_send && max_request_coverage<NRO_MAX_REQUEST_COVERAGE)
{max_request_coverage++; payload_cov->value=SpecificMeasure; count_msg++;
if(count_msg==0xFFFF) count_msg=1;
payload_cov->count = count_msg;
if(call SendMeasureMsg.send(TOS_BCAST_ADDR, sizeof(Measure_Msg),
&message)!=SUCCESS)
dbg(DBG_TEMP, "FALLITO\n"); }
elseif(must_send&&max_request_coverage>=NRO_MAX_REQUEST_COVERAGE)
{FailedCoverage++; max_request_coverage=0; }
else if(!must_send)
{max_request_coverage=0; }
return SUCCESS;
}
3
Figura 4.6: Stralcio procedura seguita dal nodo sink per assicurarsi la ricezione
delle misurazioni da parte dei nodi sensori
92
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 4.7: Confronto percentuali copertura con uso
protocollo affidabile e non affidabile.
richiesta viene inoltrata in broadcast però è diretta ai soli nodi che avevano
fallito l’invio nel corrente ciclo di misurazione (discriminati con un campo
nel messaggio inviato). Il riquadro 3 invece mostra il caso in cui si
raggiunge il numero massimo di richieste per soddisfare la copertura e
quindi si provvede a rinunciare al tentativo di raggiungere il nodo. Questo
ultimo caso risulta importante in quanto può capitare che un determinato
sensore si ritrovi ad essere isolato o abbia esaurito le proprie risorse
energetiche, una tale situazione non deve quindi impedire al nodo sink di
continuare con la raccolta di informazioni dagli altri nodi.
Concentrandoci sui risultati ottenuti (figura 4.7), un approccio di questo
tipo, evidenzia un netto miglioramento sulla percentuale di copertura, anche
portando in conto l’utilizzo della plugin Tinysan, infatti sia con una rete
composta da 9 nodi sensori che da 12 nodi sensori si ottiene sempre, in ogni
ciclo di misurazione, una copertura completa della zona monitorata. Questo
risulta essere già un buon risultato e mette in evidenzia come le possibili
perdite di pacchetto dovute o a collisioni o a errori sul canale trasmissivo
93
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 4.8 : Andamento della vita media dei singoli sensori nel caso di
utilizzo di un protocollo di comunicazione affidabile
confrontato con il caso di utilizzo di un protocollo di tipo
best-effort
sono ben recuperate con l’approccio proposto anche nel caso in cui si
prevedono solo un NRO_MAX_REQUEST_COVERAGE (ovvero numero di
richieste di ritrasmissione) pari a 2.
Passando ora a considerare il punto di vista energetico risulta chiaro che
abbiamo un peggioramento e ciò è dovuto all’overhead in seguito alla
ritrasmissione dei messaggi contenenti le misurazioni stesse. In figura 4.8
viene mostrato l’andamento della vita media dei singoli sensori facenti parte
della rete messi a confronto a seconda che sia previsto l’utilizzo di un
protocollo di recapito delle misurazioni affidabile o meno. In figura 4.9 vi è
Figura 4.9: Confronto consumo energetico dei singoli nodi
94
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
un analogo confronto però basato sul consumo medio di energia dei sensori
espresso in mJ/sec. I risultati della simulazione (rete composta da 9 nodi)
hanno evidenziato un lieve peggioramento (0.0015 % caso peggiore)della
vita media dei sensori nel caso in cui venga utilizzato un protocollo basato
su ritrasmissioni end-to-end. Questo risultato è dovuto al fatto che per il
recupero delle misurazioni non pervenute sono risultati necessari l’inoltro di
rispettivamente 30 nuove richieste di misurazioni da parte del nodo sink a
cui sono corrisposte un totale di 45 nuove ritrasmissioni di pacchetti
contenenti le informazioni monitorate. Il fatto di avere un numero maggiore
di ritrasmissioni rispetto alle richieste effettuate è dovuto alla necessità di
più tentare più volte di raggiungere la copertura totale dell’area monitorata.
4.4
DATA GATHERING CON CLUSTER
Gli studi esposti nel paragrafo 3.5 e il relativo approccio proposto nel
paragrafo 3.6 hanno messo in evidenzia come il concetto di clustering di una
rete di sensori possa favorire una migliore gestione delle risorse energetiche
dei nodi. risulta quindi interessante instrumentare una nuova simulazione le
cui caratteristiche principali sono esplicitate in tabella 4.3. Consideriamo
una rete di sensori organizzata in 3 cluster: A,B,C (figura 4.10), in cui ogni
cluster elegge ogni ELECTION_TIMER_RATE un leader (cluster-head)
che si fa carico di rispondere alle richieste di misurazioni effettuate dal nodo
sink.
Nel caso proposto i cluster heads iniziali sono i nodi 1,4,7
rispettivamente per i 3 cluster in considerazione.
NOME PROGETTO
OBIETTIVI
PROTOCOLLO DI TRASPORTO
USATO
TOPOLOGIA DELLA RETE
Cluster_Base_Data_Gathering
Il nodo con ID 0 è incaricato della raccolta
dati da tutti gli altri sensori nella rete.
Best-effort
Uso di cluster
Tabella 4-3: Caratteristiche della simulazione n°3 con rete organizzata in
cluster
95
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 4.10: Rete organizzata in cluster
La procedura di elezione di un nuovo leader, come abbiamo accennato,
avviene con un rate prefissato e viene iniziata dal nodo che riveste al tempo
dell’elezione il ruolo di leader del cluster. Più in particolare esso provvede a
scegliere con la procedura SceltaMaster() il successivo leader e poi si
interessa di comunicare ad esso che è stato eletto. La procedura di invio di
un messaggio al successivo master è illustrata in figura 4.11. Analizzando
essa in dettaglio si può notare che il nodo sensore che è cluster-head,
compone un Master_msg e lo invia al nodo designato ad essere il nuovo
cluster head (riquadro 1); contemporaneamente attiva un timer per l’attesa
di un ack da parte del sensore contattato, al fine di garantire che il nodo è
stato effettivamente eletto. Infatti si potrebbe verificare che il nodo da
eleggere
leader
sia
temporaneamente
96
non
raggiungibile
tramite
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
task void SendMasterMessage()
{Master_Msg * payload; payload = (Master_Msg *)master_message.data;
payload->becomeMaster =TRUE; payload->id actual master=TOS LOCAL ADDRESS;
if(NroSending<NRO_MAX_SENDING)
{payload->next_master=designed_address; atomic rcv_ack=FALSE;
//mando messaggio a nuovo master
if(call SendMasterMsg.send(designed_address, sizeof(Master_Msg),
&master_message)!=FAIL)
{NroSending++;
//Attivo timer e aspetto ack PER 5SEC (ack timer).
call TimerAck.start(TIMER_ONE_SHOT, ACK_TIMER); }
else { NroSending++; post SendMasterMessage();}
}
1
else
{dbg(DBG_TEMP,"Rimango master - %d -\n",TOS_LOCAL_ADDRESS);
NroSending=0; Risveglio=NroAck;
dbg(DBG_TEMP, "IMCLUSTERHEAD\n"); }
2
}
Figura 4.11: Procedura di invio di un messaggio Master
comunicazione radio, oppure che esso abbia esaurito le sue riserve
energetiche e quindi non sia eleggibile. In questo caso si prevede che, dopo
un NRO_MAX_SENDING (riquadro 2), il nodo opti per rimanere clusterhead. (chiaramente questa procedura può essere variata e più in dettaglio si
può prevedere che si contatti il nodo successivo nell’anello logico formato
dai nodi sensori appartenenti allo stesso cluster). Riguardo le azioni svolte
dai nodi che ricevono un messaggio di elezione queste sono esplicitate in
figura 4.12. Lo scenario banale prevede che i nodi che ricevono un
messaggio master_msg compongano un messaggio di ack e lo inviano al
vecchio leader. Nel caso in cui si verifichi una perdita di un messaggio di
ack (riquadro 2) l’evento viene isolato e gestito facilmente in quanto il nodo
si sarà già settato a master e quindi la ricezione di un nuovo messaggio
97
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
event TOS_MsgPtr ReceiveMasterMsg.receive(TOS_MsgPtr receivedMessage) {
//cioe' se si è attivato il timer per partecipare a una nuova elezione
if(!sleep)
{…dichiarazioni iniziali omissis…
if(!master)
{if(payload->next_master==TOS_LOCAL_ADDRESS)
{if(payload->becomeMaster)
{ack->source_address=TOS_LOCAL_ADDRESS;
ack->dest_address=payload->id_actual_master;
actual_master=payload->id_actual_master;
if(call SendAck.send(TOS_BCAST_ADDR,
sizeof(Ack_Msg),&ack_message)==SUCCESS)
{ NroAck++; atomic master=TRUE; atomic rcv_ack=FALSE;
call Election_Control.Remove_election_phase();
call Election_Control.Set_master();
dbg(DBG_TEMP, "IMCLUSTERHEAD\n");
}
}}}
// perdita di un ack significa che mi ero settato master e il mio ack si è perso
else {ack->retrasmission=TRUE;
call SendAck.send(TOS_BCAST_ADDR, sizeof(Ack_Msg),&ack_message );
}}
1
2
Figura 4.12: Procedura seguita dai nodi alla ricezione di un master_msg
master_msg sarà segno di una trasmissione non andata a buon fine.
Passiamo ora ad analizzare i risultati che sono stati ottenuti con l’utilizzo di
una rete organizzata in cluster. In figura 4.13 sono mostrati i risultati, in
termini di copertura, ottenuta per una simulazione su una rete che faccia uso
di uno schema clusterizzato e di uno schema non clusterizzato nel caso
siano utilizzati 9 nodi sensori e non si faccia uso di un protocollo affidabile
per il recapito delle misurazioni al nodo sink. Come si può notare la
percentuale di cicli di misurazioni che hanno ottenuto una copertura totale
della rete è più elevato rispetto alla analoga simulazione del paragrafo 4.3.
Del resto il risultato è ovvio visto che avendo un solo sensore attivo per
cluster diminuisce la probabilità di collisioni nella consegna delle
informazioni monitorate (a causa della congestione della rete).
98
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 4.13: Confronto copertura con uso protocollo
affidabile e non affidabile
Dal punto di vista energetico, invece il guadagno che si ottiene con l’uso di
una rete organizzata in cluster risulta abbastanza evidente (vedi figura 4.14).
Del resto ciò risulta abbastanza intuitivo in quanto il carico dei nodi sarà ora
distribuito nel tempo su tutti i nodi appartenenti allo stesso cluster
implementando così una strategia di load balancing. Dal grafico si nota
come la vita media dei sensori in una rete organizzata in cluster sia
Figura 4.14: Guadagno energetico con rete organizzata in cluster
99
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
aumentata; l’aumento è di circa il 7% nel caso in cui si prevede un numero
dispositivi per cluster pari a 2 (cluster C dispositivi 7 e 8) e arriva ad un 9%
se si prevede l’utilizzo di 3 nodi sensori per cluster. L’incremento di
autonomia della rete continua a crescere se si prevede un utilizzo di cluster
abbastanza numerosi e si è potuto riscontrare che con l’uso di un numero di
7 dispositivi per cluster si arriva ad una vita media stimata per i sensori di
circa 260 h raggiungendo quindi un incremento rispetto alla rete non
organizzata in cluster di circa il 13%. Il risultato risulta interessante in
quando adottando strategie di questo tipo si possono ottenere architetture di
monitoraggio che riescano a soddisfare vincoli stringenti relativi alla durata
della rete.
4.5
DATA GATHERING CON CLUSTERING E
PROTOCOLLO AFFIDABILE
Fino ad ora abbiamo effettuato una analisi che ha messo in evidenzia come
l’utilizzo di reti organizzate in cluster porti miglioramenti all’incremento
della vita media dei singoli nodi, ora non ci resta che analizzare così come
fatto nel paragrafo 4.3, le performance di una rete nel momento in cui si
introduce il concetto di affidabilità nei confronti del recapito delle
misurazioni; le caratteristiche principali di questa nuova simulazione sono
esposte in tabella 4.4. I risultati che sono emersi hanno evidenziato un
NOME PROGETTO
OBIETTIVI
PROTOCOLLO DI TRASPORTO
USATO
TOPOLOGIA DELLA RETE
Reliable_Cluster_Base_Data_Gathering
Il nodo con ID 0 è incaricato della raccolta
dati da tutti gli altri sensori nella rete.
Affidabile end-to-end (max 2 ritrasmissioni)
Previsto uso di cluster
Tabella 4-4: Caratteristiche della simulazione n°4 con rete organizzata in
cluster e uso protocollo di recapito affidabile
100
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
peggioramento, come è lecito aspettarsi, per quanto riguarda la vita media
dei singoli nodi causato sempre dalla maggior quantità di energia che è
spesa per le ritrasmissioni necessarie al recupero di eventuali fallimenti nel
recapito dei pacchetti. Anche in questo caso, così come riscontrato nella
simulazione esposta nel paragrafo 4.3 il protocollo end to end si mostra
essere molto leggero introducendo un decremento della vita media dei
singoli sensori molto trascurabile a testimonianza del fatto che la sua
attivazione solo nei momenti in cui abbiamo perdite è un buon approccio
per ovviare ai problemi relativi alla congestione della rete e alla scarsa
qualità dei singoli link di comunicazione. Per avere una analisi completa dei
protocolli discussi nei paragrafi precedenti, in figura 4.15 è riportato, una
comparazione tra le vite medie dei vari dispositivi in base alla topologia di
rete utilizzata e allo schema adottato per la ricezione delle informazioni
presso il nodo sink. Il risultato ottenuto risulta essere abbastanza intuitivo,
infatti come si può notare la vita media per i dispositivi più elevata, a cui
corrisponde quindi un dispendio energetico medio più basso, è stata
riscontrata nella simulazione con una rete organizzata in cluster. Il
peggioramento nel caso in cui la topologia della rete non sia organizzata in
Figura 4.15: Analisi comparativa degli algoritmi
101
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
cluster è abbastanza accentuata soprattutto nei riguardi della simulazione
riportata nel paragrafo 4.3. Di conseguenza possiamo affermare che
l’utilizzo di una strategia che vede l’organizzazione in cluster della rete
comporta comunque una miglioria per quanto riguarda la durata media della
vita della rete. Fino ad ora gli approcci che sono stati presentati relativi al
clustering sono stati tutti incentrati sull’uso di un meccanismo di elezione
che andava attivato ogni ELECTION_TIMER_RATE. Un interessante
scenario da valutare è quello in cui l’elezione del leader sia effettuata solo
nel momento in cui il dispositivo sensore che funge da leader esaurisce la
propria carica energetica. L’obiettivo di instrumentare una simulazione di
questo genere è volta ad individuare se può essere più conveniente, per la
vita media di una rete, portare all’esaurimento i nodi che sono stati designati
a leader del cluster e quindi ridurre in questo caso al minimo le procedure
stesse di elezione. Da una analisi dei risultati in figura 4.16 si può
concludere che i nodi che sono stati designati ad essere leader fin quando
possibile risultano avere una vita media stimata inferiore di circa 20h,
mentre gli altri nodi registrano un aumento di 10h di autonomia. Ciò
significa che, detto con ci il tempo di esaurimento del nodo i-esimo, al lordo
della procedura di elezione, al tempo c1=c4=c7 (~230 h) i nodi capo cluster
Figura 4.16: Elezione eseguita ciclicamente o all’esaurimento
energetico di un nodo
102
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
saranno esauriti e i restanti nodi che fino a quell’istante avevano fornito una
funzionalità semplicemente di forwarding dei pacchetti, avranno una
autonomia residua pari a c2-c1 (~30 h). A questo punto bisognerebbe
calcolare quante ore di autonomia resterebbero ai nuovi cluster head, ma il
calcolo di tale autonomia non è permesso dalla plugin in maniera analitica.
Dal punto di vista intuitivo però si dovrebbe riscontrare effettivamente un
guadagno, in quanto avremo una procedura di elezione che verrà attivata
solo nel momento in cui si sarà esaurita la riserva energetica di un nodo.
Facciamo però notare che una procedura di questo genere prevede che il
nodo sink si accorga della “morte” di un nodo solo quando ormai la
procedura di misurazione è stata lanciata; ciò quindi causa una perdita di
informazione non rimediabile. È chiaro che potrebbero essere sviluppate
procedure che mirino a indagare sullo “stato di salute” in termini energetici
dei singoli nodi, ma operazioni di questo tipo porterebbero ad un consumo
energetico aggiuntivo per il recapito di queste informazioni al nodo sink.
4.6
OVERLAY NETWORK
Tutte le simulazioni che sono state condotte nei paragrafi precedenti hanno
portato a risultati, in termini di energia media dissipata dai vari nodi (quindi
vita stimata residua), che dipendono fortemente:
1. dall’uso del protocollo multihop
2. dal ruolo dei nodi che non rivestono il ruolo di leader del cluster.
Relativamente al punto 2 un dispositivo sensore in ogni istante funge
comunque da nodo forwarder dei pacchetti al fine di poter contribuire al
recapito delle informazioni al nodo sink e un siffatto funzionamento,
comporta quindi la necessità che il modulo radio di ogni sensore sia sempre
attivo, causando un dispendio energetico che influisce fortemente sulla vita
totale della rete.
103
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
Figura 4.17: Overlay Network
Da queste osservazioni se ci poniamo nelle ipotesi:
ƒ
che i dispositivi possano essere programmati per non partecipare
continuamente al protocollo multihop e che possano effettuare una
operazione di join al protocollo solo nel momento in cui rivestono il
ruolo di leader del cluster;
ƒ
che i dispositivi non leader possano essere in uno stato di power save
e provvedano all’accensione del modulo radio solo in alcuni
intervalli di tempo;
ƒ
che il grafo dei collegamenti tra i nodi sensori sia fortemente
connesso;
allora la soluzione che prevede la costruzione di una overlay network (figura
4.17) potrà portare significativi vantaggi dal punto di vista dell’incremento
della vita della rete. Infatti, anche se in questo caso abbiamo una limitazione
dal punto di vista topologico, i vari sensori che non sono leader sono in uno
stato risparmi energetico e quindi non consumeranno risorse energetiche
104
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
dovute al mantenimento del modulo radio acceso e all’inoltro dei vari
pacchetti. Di conseguenza lo scenario che si presenta è quello di una rete in
cui gli unici nodi che sono coinvolti in procedure di inoltro di misurazioni
sono i leader di ogni cluster, mentre gli altri sono dormienti. In tale
condizione quindi otterremo globalmente un risparmio energetico ingente
grazie allo stato sleep del modulo radio. Questa assunzione, del resto, è
giustificata anche analiticamente dai risultati ottenuti dalla simulazione sulla
vita media di un sensore (figura 4.18) che hanno mostrato un netto
abbattimento dell’autonomia dei dispositivi nel caso in cui sia previsto
l’utilizzo del modulo radio per la trasmissione di misurazioni. Volendo
quindi stimare la vita media della rete potremmo dire che nel caso in cui
consideriamo tutti cluster formati da n dispositivi:
vitamedia =
lifetime _ cluster _ head + (n − 1) * lifetime _ no _ radio
n
Dove lifetime_cluster_head rappresenta l’autonomia del sensore nel
momento in cui è attivo il modulo radio, mentre lifetime_no_radio è
l’autonomia del sensore nel momento in cui non è attivo il modulo radio.
Infatti nel caso in cui si considera una rete organizzata in cluster ciascuno
composto da n=3 nodi sensori, la formazione di overlay network implicherà
Impatto del modulo radio sulla vita media di un
sensore
700,00
vita media stimata [h]
600,00
500,00
400,00
modulo radio attivo
300,00
modulo radio spento
200,00
100,00
0,00
Figura 4.18: Impatto del modulo radio sulla vita di
un sensore
105
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
che ogni nodo sensore sia con il modulo radio acceso per 1/3 della sua vita e
per i 2/3 spento. Ciò implica che essendo lifetime_cluster_head=249h e
lifetime_no_radio=658h allora avremo una vita media stimata che si attesta
sulle 521h che risulta essere più del doppio della stima nel caso in cui non si
ricorra allo spegnimento del modulo radio.
In conclusione l’idea di creare una overlay network e di modificare il
protocollo multihop in modo tale da costruire nuove tabelle di routing ogni
volta che si ha un cambiamento dei leader del cluster risulta essere una
buona prospettiva per lo sviluppo di reti di sensori con particolari esigenze
di longevità.
106
Conclusioni
Il presente lavoro di tesi nasce dall’esigenza di riuscire ad ottenere
architetture di reti di sensori senza cavo con particolari esigenze di
affidabilità nella consegna delle misurazioni e minimizzazione del consumo
energetico dei stessi sensori. Essendo i due requisiti in contrasto tra loro è
necessario valutare se può essere individuata per via sperimentale una
soluzione di compromesso (trade- off).
Dopo uno studio attento della letteratura in merito ai protocolli di
clusterizzazione e di consegna affidabile delle misurazioni, si è proposto un
nuovo modo di intendere il ruolo di leader del cluster, non più delegato a
gateway tra i nodi sensori del cluster e il nodo sink, bensì come l’unica
entità incaricata dell’azione di monitoraggio della grandezza fisica relativa
all’evento che si vuole analizzare. Attraverso poi delle strategie di leader
election periodico all’interno di ogni cluster è stato possibile implementare
load balancing al fine di ottenere un consumo energetico uniforme e
garantire quindi una ripartizione del carico tra i vari sensori afferenti ai
cluster.
I risultati sperimentali, ottenuti con l’ausilio del simulatore ad eventi discreti
TOSSIM, hanno mostrato un guadagno di circa il 9% nella autonomia dei
nodi sensori nel caso in cui si prevedano cluster con solo 3 dispositivi
(risulta chiaro che all’aumentare del numero di dispositivi previsti per
cluster aumenterà anche il guadagno dal punto di vista energetico e quindi
l’autonomia della rete). Riguardo la consegna affidabile i risultati hanno
107
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
evidenziato che, una strategia che preveda il recupero delle misurazioni,
basato su richieste di trasmissioni che vengono inoltrate dal nodo sink solo
in caso di reale perdita, è una buona soluzione di trade off tra recapito di una
definita quantità di informazione sull’evento monitorato e minimizzazione
dei consumi energetici dei nodi sensori. Infatti l’impatto sulla vita di un
siffatto protocollo è risultato essere molto basso.
In seguito all’utilizzo di TOSSIM, non è stato possibile indagare in maniera
sistematica e precisa sul guadagno che si otterrebbe se i nodi sensori che
non fungono da cluster-head fossero completamente spenti. Questa strategia
prevede vincoli dal punto di vista topologico (è necessario che il grafo
formato dai nodi sensori sia fortemente connesso pena la non raggiungibilità
delle misurazioni rilevate al nodo sink) ma da una semplice analisi emerge
che potrebbe portare ad un raddoppio della vita media di una rete, quindi
sarebbe molto interessante investigare su questo punto in quanto
permetterebbe la realizzazione di reti di sensori con particolari esigenze di
longevità.
108
Bibliografia
[1]
M. Cinque, D. Cotroneo, G. De Caro, and M. Pelella. Reliability requirements of
wireless
sensor networks for dynamic structural monitoring. International
Conference on Dependable Systems and Networks (DSN),2006.
[2]
C. Perkins, Ad Hoc Networks, Addison-Wesley, Reading, MA, 2000.
[3]
I.F.Akyildiz, W.Su, Y.Sankarasubramaniam and E.Cayirci, A Survery on Sensor
Networks, IEEE Communications Magazine, August 2002, pages 102-114, 393-442
[4]
A. Y. Wang, S. H. Cho, C. G. Sodini, and A. P. MAC for Asymmetric RF
Microsensor Systems. In Intl. Symp. on Low Power Electronics and Chandrakasan.
Energy Efficient Modulation and Design, August 2001.
[5]
C. Schurgers, O. Aberthorne, and M. B. Srivastava. Modulation Scaling for Energy
Aware Communication System In Intl. Symp. on Low Power Electronics and Design,
August 2001.
[6]
Wei Ye, John Heidemann, Medium Access Control in Wireless Sensor Networks,
USC/ISI TECHNICAL REPORT ISI-TR-580, October 2003
[7]
Brad Karp and H. T. Kung. Gpsr: greedy perimeter stateless routing for wireless
networks. In MobiCom ’00: Proceedings of the 6th annual international conference
on Mobile computing and networking, pages 243–254, New York, NY, USA, 2000.
ACM Press.
[8]
Devika Subramanian, Peter Druschel, and Johnny Chen. Ants and reinforcement
learning: A case study in routing in dynamic networks. In IJCAI (2), 1997.
[10]
W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy - efficient
communication protocol for wireless microsensor networks, Proc. 33rd Hawaii Int'l.
Conf. Sys. Sci.,pp. 3005- 3014, Jan.2000.
[11]
Konstantinos Kalpakis, Koustuv Dasgupta and Parag Namjoshi Efficient algorithms
for maximum lifetime data gathering and aggregation in wireless sensor networks
,2002.
[12] Supriyo Chatterjea and Paul Havinga A Dynamic Data Aggregation Scheme for
Wireless Sensor Networks.
[13]
R. Nowak. Distributed EM algorithms for density estimation and clustering in
sensor networks. IEEE Trans. on Sig. Proc., 51(8), August 2003.
[14]
http://www.alertsystems.org.
109
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
[15]
A. Cerpa, J. Elson, M. Hamilton, J. Zhao, Habitat monitoring: application driver for
wireless communications technology, ACM SIGCOMM'2000, Costa Rica, April
2001.
[16]
http://www.greatduckisland.net/
[17]
G. R. Polastre, “Design and Implementation of Wireless Sensor Networks for
Habitat Monitoring ”, Master dissertation, Dept. of Elec. Eng., UCB, Spring 2003.
[18]
N. Noury, T. Herve, V. Rialle, G. Virone, E. Mercier, G. Morey, A. Moro, T.
Porcheron, Monitoring behavior in home using a smart fall sensor, IEEE-EMBS
Special Topic Conference on Microtechnologies in Medicine and Biology, October
2000, pp. 607-610.
[19]
E.M. Petriu, N.D. Georganas, D.C. Petriu, D. Makrakis,V.Z. Groza, Sensor-based
information
appliances, IEEE Instrumentation and Measurement Magazine
(December 2000) 31-35.
[20]
I.A. Essa, Ubiquitous sensing for smart and aware environments, IEEE Personal
Communications (October 2000).
[21]
TinyOS: An open source operating system for WSN - www.tinyos.net.
[22]
R. Von Behren M. Welsh E. Brewer D. Gay, P. Levis and D. Culler. “The nesC
Language: A Holistic Approach to Networked Embedded Systems”. In Proceedings
of Programming Language Design and Implementation (PLDI) 2003, June 2003.
[23]
H. Abrach, J. Carlson, H. Dai, J. Rose, A. Sheth, B. Shucker, and R.Han. MANTIS:
System support for multimodal networks of in-situ sensors. In Proc. 2nd ACM Intl.
Workshop on Wireless Sensor Networks and Applications (WSNA), San Diego,
CA, September 2003.
[24]
G. Ananstasi, M. Conti, A. Falchi, E. Fragori e A. Passerella: Performance
Measurements of Mote Sensor networks. ACM/IEEE International Symposium on
Modeling, Analysis and Simulation of Wireless and Mobile System, pp. 174-181,
ACM Press, 2004.
[25]
D. D. Clark and D. L. Tennenhouse. Architectural Considerations for a New
Generation of Protocols. In Proceedings of SIGCOMM, September 1990.
[26]
Philip Levis and Nelson Lee. TOSSIM: A simulator for TinyOS networks, November
14 2003.
[27]
Philip Levis, Nelson Lee, MattWelsh, and David E. Culler. TOSSIM: accurate and
scalable simulation of entire TinyOS applications. In SenSys, pages 126–137, 2003.
[28]
Alan Mainwaring, Joseph Polastre, Robert Szewczyk, David Culler, and John
Anderson. Wireless sensor networks for habitat monitoring.
110
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
[29]
J. Elson, S. Bien, N. Busek, V. Bychkovskiy, A. Cerpa, D. Ganesan, L. Girod, B.
Greenstein, T. Schoellhammer, T. Stathopoulos, D. Estrin, 2003 “Emstar: an
environment for developing wireless embedded systems software”
[30]
L. Girod, J. Elson, A. Cerpa, T. Stathopoulos, Nithya Ramanathan, D. Estrin
“Emstar: a software environment for developing and deploying wireless sensor
networks”
Jonathan Polley, Dionysys Blazakis, Jonathan McGee, Dan Rusk, John S. Baras
“Atemu: a fine-grained sensor network simulator”.
[31]
[32]
Ben L. Titzer, Daniel K. Lee, Jens Palsberg “Avrora: scalable sensor network
simulation with precise timing”.
[33]
ISI. The network simulator 2 ns-2. http://www.isi.edu/nsnam/nsidenx.html, 2002.
[34]
Xiang Zeng, Rajive Bagrodia, and Mario Gerla. Glomosim: A library for parallel
simulation of large-scale wireless networks. In Workshop on Parallel and
Distributed Simulation, pages 154–161, 1998.
[35]
Y. Huang, J. Huang, L. Hester, A. Allen, O. Andric, P. Chen, and B. O’Dea. Opnet
simulation of a multi-hop self-organizing wireless sensor network.
[36]
A. Savvides S. Park and M. B. Srivastava. Sensorsim: a simulation framework for
sensor networks. In Proceedings of the 3rd ACM international workshop on
Modeling, analysis and simulation of wireless and mobile systems, pages 104–111,
Boston, MA USA.
[37]
Ahmed Sobeih, Wei-Peng Chen, Jennifer C. Hou, Lu-Chuan Kung, Ning Li, Hyuk
Lim, Hung-Ying Tyan, Honghai Zhang “J-Sim: a simulation and emulation
environment for wireless sensor networks”
[38]
Claudio Basile, Zbigniew Kalbarczyk, and Ravi K. Iyer. Neutralization of errors and
attacks in wireless ad hoc networks. In International Conference on Dependable
Systems and Networks(DSN), 2005.
[39]
S. Shakkottai, R. Srikant, and N. Shroff. Unreliable sensor grids: Coverage,
connectivity and diameter. In IEEE INFOCOM2003, pages 241–250, 2003.
[40]
D. Bein, V. Jolly, B. Kumar, and S. Latifi. Reliability modeling in wireless sensor
networks. International Journal of Information Technology, Vol. 11 No. 2, 2004.
[41]
Hosam M. F. AboElFotoh, S. S. Iyengar, and Krishnendu Chakrabarty. Computing
reliability and message delay for cooperative wireless distributed sensor networks
subject to random failures. IEEE TRANSACTIONS ON RELIABILITY, 54(1),
MARCH 2005.
[42]
G. Gupta and M. Younis. Fault-tolerant clustering of wireless sensor networks.
IEEE, 2003.
[43]
Jae-Joon Lee, Bhaskar Krishnamachari, and C.-C. Jay Kuo. Impact of energy
depletion and reliability on wireless sensor network connectivity, 2005.
111
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
[44]
S. Lindsey and C. S. Raghavendra. PEGASIS: Power-efficient gathering in sensor
information systems. In Proceedings of the IEEE Aerospace Conference, March
2002.
[45]
L. Subramanian and R.H. Katz, “An architecture for building self-configurable
systems”, Proceedings of the 1st ACM international symposium on Mobile ad hoc
networking and computing, pp. 63–73, Boston, MA, USA, 2000.
[46]
C. V. Ramamoorthy, A. Bhide, and J. Srivastava, “Reliable clustering techniques for
large, mobile packet radio networks”, Proceedings of the 6th Annual Joint
Conference of the IEEE Computer and Communications Societies (INFOCOM ’87),
San Francisco, CA, USA, 1:218–226, 31 March–2 April 1987.
[47]
R. Krishnan and D. Starobinski, Efficient clustering algorithms for self organizing
wireless sensor networks,. Ad Hoc Networks, vol. 4, no. 1, pp. 36.59, January 2006.
[48]
Leonidas Tzevelekas, Ziviani Towards Potential-Based Clustering forWireless
Sensor Networks CoNEXT’05, October 24.27, 2005, Toulouse, France.
[49]
Malka Halgamuge, Siddeswara Mayura Guru and Andrew Jennings; Energy efficient
Cluster Formation in wireless sensor networks, International conference on
telecommunications ICT 2003, IEEE Press.
[50]
Yuon Guo, Janise Mcnair, Cost Efficient Cluster Formation for wireless sensor
networks, Proc. of CITSA 2004, Orlando, FL, July 2004.
[51]
Ossama Younis and Sonia Fahmy, HEED: A hybrid energy efficient, distributed
clustering apparoach for Ad-hoc sensor networks, IEEE Transactions on Mobile
Computing, Oct.-Dec. 2004, Volume: 3, Issue: 4, p.p. 366 - 379.
[52]
G. Gupta and M. Younis, Load-Balanced Clustering in Wireless Sensor Networks,
IEEE International conference on communications, Anchorage, Alaska, 2003.
[53]
S. Banerjee and S. Khuller, A Clustering Scheme for Hierarchical Control in Multihop Wireless Networks, INFOCOM, 2001.
[54]
A. Antis, R. Prakash, T. Vuong, and D. Huynh, Max-Min d-Cluster Formation in
Wireless Ad Hoc Networks, IEEE INFOCOM, 2000.
[55]
Y. Bejerano, Efficient Integration of Multihop Wireless and Wired Networks with
QoS Constraints, IEEE/ACM Transactions on Networking, 2004.
[56]
B. Aoun, R. Boutaba, Clustering in WSN with latency and Energy Consumption
constraints, Journal of Network and Systems Management, Vol. 14, No. 3,
September 2006
[57]
Mudasser Iqbal, Iqbal Gondal and Laurence Dooley An Energy-Aware Dynamic
Clustering Algorithm for Load Balancing in Wireless Sensor Networks JOURNAL
OF COMMUNICATIONS, VOL. 1, NO. 3, JUNE 2006
112
Progetto e valutazione di algoritmi per la raccolta
dati affidabili su reti di sensori senza cavo
[58]
A. Kroller, D. Pfisterer, C. Buschmann, S.P. Fekete, S. Fischer, “Shawn: A new
approach to simulating wireless sensor networks”, 2005
[59]
http://tcs.unige.ch/doku.php/code/algosensim/overview
[60]
C. Mallanda, A. Suri, V. Kunchakarra, S.S. Iyengar, “Simulating wireless sensor
networks with Omnet++”, 2005
[61]
Fred Stann and John Heidemann. RMST: Reliable Data Transport in Sensor
Networks. 1st IEEE International Workshop on Sensor Net Protocols and
Applications, 2003
[62]
C. Wan, A. Campbell, L. Krishnahmurthy. PSFQ: A Reliable Transport Mechanism
for Wireless Sensor Networks. ACM International Workshop on Wireless Sensor
Networks and Applications, Atlanta, Georgia, Sept 2002.
[63]
C. Intanagonwiwat, R. Govindan, D. Estrin, j. Heidmann and F. Silva “Direct
Diffusion for wireless sensor network” IEEE/ACM Transactions on Networking,
vol.11, pp 2-16, Feb 2003
[64]
Seung-Jong Park, Ramanuja Vedantham, Raghupathy Sivakumar and Ian F.
Akyildiz A scalable approach for reliable downstream data delivery in wireless
sensor networks in the Proceedings of ACM International Symposium on Mobile Ad
hoc Networking and Computing (MOBIHOC), Japan, May 2004.
[65]
Chieh-Yih Wan, Shane B. Eisenman, Andrew T. Campbell, “CODA: Congestion
Detection and Avoidance in Sensor Networks”, in proceedings of First ACM
Conference on Embedded Networked Sensor Systems (SenSys 2003), November
2003.
[66]
J.O’Rourke. Computational geometry column 15. Int’l Journal of Computational
Geometry and Application, 2(2):217-217,1992.
[67]
Seapahn Meguerdichian, Farinaz Koushanfar, Miodrag Potkonjak, Mani B.
Srivastava, Coverage Problems in Wireless Ad-hoc Sensor Networks, in IEEE
INFOCOM, pages 1380-1387, 2001
[68]
S. Slijepcevic, M. Potkonjak, Power Efficient Organization of Wireless Sensor
Networks, In IEEE Int’l Conf. on Communications (ICC) pages 472-476, 2001.
[69]
Tian, Georganas, A Coverage-Preserving Node Scheduling Scheme for Large
Wireless Sensor Networks ACM Int’l Workshop on WSNA, 2002
[70]
Catello Di Martino, Valutazione dell'affidabilità di Reti di Sensori senza cavo,
Università degli studio di Napoli Federico II, Ottobre 2005
[71]
Fan Ye, Gary Zhong, Jesse Cheng, Songwu Lu, Lixia Zhang PEAS: A Robust
Energy Conserving Protocol for Long-lived SensorNetworks, In Int’l Conf. on
Distributed Conputing System (ICDCS), 2003
113