Algoritmi per il controllo della topologia per reti di sensori wireless zigbee veicolari

  
[Premessa] 
 
2 
 
Nell’ambito di tale progetto il presente lavoro si è proposto un duplice 
obiettivo: da un lato la realizzazione di un simulatore tempo-discreto, in 
linguaggio C++,  per la  “Cluster Formation “e “Manteinance” di una rete di 
sensori veicolari, all’interno del quale sono state implementate funzioni in 
linea con le specifiche degli standard di comunicazione ZigBee, e dall’altro 
l’implementazione , il testing, ed il confronto di diversi algoritmi di Adaptive 
Clustering compatibili con l’ambiente VWSN (Comunicazione di tipo VTI 
“Vehicle To Infrastructure”). 
Le simulazioni sono state effettuate su diverse tipologie di scenari e facendo 
variare le variabili di progetto più significative per questo tipo di sistemi. 
I grafici ottenuti per via simulativa hanno permesso la comparazione dei 
diversi approcci di Clustering proposti, e suggerito le linee guida per la 
progettazione di Algoritmi efficienti per tali sistemi. 
 
 
 [Introduzione]
 
3 
 
Introduzione 
La possibilità di considerare dei veicoli come nodi di una rete di sensori 
rappresenta il motivo di indagine di questa dissertazione.  
L’opportunità, che le reti di sensori offrirebbero, di raccolta ed aggregazione 
dei dati permetterebbe di superare quei problemi infrastrutturali che, fino ad 
oggi, hanno limitato lo sviluppo di sistemi comunicativi basati sul modello 
VTI (Vehicle To Infrastructure) o VII (Vehicle Infrastructure Integration) (1).  
Tra questi il più condizionante è stato sicuramente la considerazione di reti 
che prevedessero un’architettura in cui ogni dispositivo mobile inviava  il 
proprio contenuto informativo (pochi byte) direttamente all’infrastruttura 
esterna. Se l’obiettivo è la scalabilità della rete, questa soluzione risulta 
infattibile a causa di numerose problematiche: da un lato una soluzione 
infrastrutturata in cui i nodi non collaborano fra di loro ma si interfacciano 
esclusivamente con l’unità centralizzata di raccolta dati, genererebbe un 
traffico notevole verso quest’ultima, costringendola ad assegnare e 
riassegnare le (limitate) risorse radio un numero considerevole di volte; 
dall’altro il costo dell’intero sistema, a causa della maggiore complessità di 
tutti i dispositivi impiegati, sarebbe estremamente elevato e non più 
giustificabile. 
Le reti di sensori rappresentano, in tale ambito, una valida alternativa in 
quanto introducono modelli collaborativi in grado di superare le 
problematiche viste sopra. 
La valutazione dell’effettiva adattabilità di queste soluzioni alle 
comunicazioni di tipo VTI è, tuttavia, ancora in fase di analisi. 
Quello che è emerso dagli studi svolti in questa tesi è che le difficoltà da 
risolvere sono ancora numerose e dipendono essenzialmente dal fatto che lo 
scenario di riferimento si colloca a metà fra il mondo delle WSNs (Wireless 
Sensor Networks) e quello più ampio e variegato delle MANETs (Mobile 
Ad-hoc NETworks)  generando una categoria specifica definibile come 
VWSNs (Vehicular Wireless Sensor Networks). 
In quest’ultimo tipo di reti vengono utilizzati i dispositivi classici delle reti di 
sensori (smart sensor), in quanto i dati relativi alle grandezze monitorate sono 
poco ingombranti e destinati esclusivamente all’infrastruttura esterna, ma 
modelli collaborativi più evoluti di quelli usati nelle WSN di tipo statico in 
quanto devono operare in ambienti caratterizzati da elevata mobilità (tipici 
delle MANET). 
 [Introduzione]
 
4 
 
La spinta maggiore all’implementazione di sistemi VWSN viene proprio 
dalle numerosissime possibilità applicative di tale tecnologia: si potrebbe, ad 
esempio, pensare di utilizzarli in uno scenario portuale od aeroportuale per 
motivi di sicurezza, dotando tutti i mezzi in movimento di sistemi di 
posizionamento o piccoli radar e monitorando real time la loro posizione per 
mezzo di un’infrastruttura esterna. Un altro possibile contesto in cui installare 
una rete di sensori veicolari è quello inerente al posizionamento dei nodi 
sensori sulle macchine, gli autobus o i taxi per monitorare incroci stradali, 
aree urbane o autostradali e, magari, fornire informazioni sulle condizioni del 
manto stradale, sulle situazioni di congestione del traffico o sull’occorrenza 
di incidenti, rendere disponibili road map di maggiore qualità od anche per 
monitorare in tempo reale particolari eventi di alert rilevati sui singoli veicoli 
e garantire quindi un intervento immediato. 
Questo lavoro si propone quindi, come obiettivo, la creazione di una suite 
simulativa in linguaggio C++ all’interno della quale possano essere 
implementati, testati e confrontati i modelli collaborativi adatti all’ambiente 
VWSN, e riguardanti la formazione ed il mantenimento di reti ad albero 
multilivello in presenza di elevata mobilità e comunicazione VTI. 
Nel primo capitolo saranno descritte le caratteristiche generali di una rete di 
sensori wireless, dai dispositivi che operano all’interno di essa e le relative 
modalità di collaborazione fino ai fattori che ne influenzano la progettazione. 
Vengono presentate le diverse applicazioni per cui una rete di sensori può 
essere realizzata e, tra i possibili protocolli di comunicazione, viene citato lo 
standard ZigBee basato su IEEE802.15.4 nei suoi aspetti più importanti. 
Nel secondo capitolo verrà investigato lo stato dell’arte riguardante i modelli 
collaborativi utilizzati nelle MANET. Verranno analizzate, quindi, tutte le 
proprietà dei protocolli per la formazione ed il mantenimento adattativo dei 
cluster, proposti  in letteratura per tali scenari, e ricavate le linee guida 
progettuali per lo sviluppo di protocolli di “Adaptive Clustering” in ambiente 
VWSN. 
Il capitolo successivo descriverà l’ambiente simulativo utilizzato, 
provvedendo quindi a specificare i flussi di input/output gestiti dai vari 
blocchi e riportando, in maniera dettagliata, tutte le specifiche 
implementative del sottosistema adibito alla formazione ed al mantenimento 
dei cluster e le considerazioni tecniche alla base delle scelte effettuate. 
 [Introduzione]
 
5 
 
Il capitolo quarto entrerà nel merito dei protocolli di Adaptive Clustering 
utilizzati, descrivendone la struttura ed il comportamento e giustificandone la 
compatibilità con l’ambiente VWSN. Verranno poi proposte diverse metriche 
di Parent Selection e delineati i possibili sviluppi futuri per tali operazioni 
decisionali.  
Il capitolo finale racchiude tutti i risultati delle varie simulazioni che sono 
state effettuate allo scopo di valutare le prestazioni degli algoritmi al variare 
delle caratteristiche dello scenario di simulazione, dei dispositivi e degli 
aspetti inerenti la mobilità dei nodi. In particolare saranno mostrate le 
topologie risultanti relative alle fasi di formazione e mantenimento della rete, 
e grafici specifici che evidenziano il chiaro trade-off, fra overhead (in termini 
di numero di operazioni riconfigurative e quindi traffico di segnalazione) e 
percentuale di sink (e conseguente qualità della rete), caratteristico di tali 
sistemi. Viene effettuata, poi, la valutazione degli stessi algoritmi in scenari 
con mobilità di tipo stradale. Il capitolo si concluderà con alcuni esempi di 
simulazione tesi a validare il software. 
 
Capitolo 1 
      Reti di Sensori   
 
6 
 
Reti Di Sensori 
1.1 Introduzione 
Le reti di sensori wireless hanno iniziato ad essere sviluppate nella metà degli 
anni novanta da un consorzio di università statunitensi. Nel 1999 venne 
pubblicato un lavoro del prof. Kris Pister dell’Università di Berkeley (2), 
California, che proponeva il progetto di una piattaforma autonoma per quanto 
riguarda l’elaborazione dei dati e la comunicazione, dalle dimensioni 
piccolissime ( circa  ), che poteva essere usata come nodo per una rete 
di sensori wireless. Gli enormi scenari che si aprivano con questa nuova 
tecnologia in tutti i campi della società moderna furono notati dal DARPA 
(Defense Advanced Research Projects Agency), che iniziò a finanziare il 
progetto Smart Dust, avente lo scopo di ridurre le dimensioni di un nodo 
wireless fino a quelle di un granello di sabbia. La spinta al progresso 
tecnologico in tale ambito, generata da tanto interesse, ha poi permesso che i 
nodi wireless diventassero sempre più economici consentendo la loro 
penetrazione nei più disparati settori industriali. 
 
1.2 Struttura degli “smart sensor” 
L’intrinseca natura di elementi di rete ha fatto sì che tali dispositivi si 
distinguessero dai semplici trasduttori di grandezze fisiche visti fino a quel 
momento (sensor), in quanto capaci di integrare oltre alle capacità di misura 
anche le capacità di memorizzazione, di calcolo ed ovviamente di essere 
dotati di interfacce di comunicazione, e venissero conseguentemente 
classificati come: smart sensor.  
Conseguentemente alla nuove potenzialità di questi sensori intelligenti, al 
concetto di singolo sensore che svolge da solo un dato compito, si sostituisce 
quello di una moltitudine di dispositivi in grado di cooperare per il 
raggiungimento di un obiettivo comune (task). La peculiarità di una rete di 
sensori è proprio nelle capacità di elaborazione e collaborazione dei nodi 
sensori: ogni dispositivo è, infatti, provvisto di un processore on-board che 
gli consente di effettuare delle elaborazioni semplici e trasmettere solo i dati 
richiesti e già processati.