Facoltà di Ingegneria tesi di laurea specialistica ... Flavio Frattini.pdf · 3.10 Struttura dei...

Facoltà di Ingegneria Corso di Studi in Ingegneria Informatica

tesi di laurea specialistica

Localizzazione di sensori in reti WSN mediante la metrica RSSI Anno Accademico 2008/2009 relatori Ch.mo prof. Domenico Cotroneo Ch.mo prof. Stefano Russo correlatore Ch.mo prof. Marcello Cinque candidato Flavio Frattini matr. 885/147

II

A mia cugina Monica.

Per aspera ad astra.

Localizzazione di sensori in reti WSN mediante la metrica RSSI

iii

Indice

Indice iii

Indice delle figure vi

Indice delle tabelle viii

Simboli e abbreviazioni ix

Introduzione xii

Capitolo 1 - Localizzazione in reti di sensori 15

1.1 Le Wireless Sensor Networks 15

1.2 Il problema della localizzazione 17

1.3 Sistemi GNSS 19

1.3.1 Global Positioning System 20

1.3.2 GLONASS 23

1.3.3 GALILEO 24

1.4 Localizzazione in WSN 24

1.4.1 Algoritmi di localizzazione 26

1.5 ROCRSSI 28

Capitolo 2 - ROCRSSI+ e ROCRSSI++ 33

2.1 ROCRSSI+ 33

2.2 ROCRSSI++ 35

2.3 Studi sperimentali sul ROCRSSI 39

Capitolo 3 - Implementazione del ROCRSSI+ in TinyOS 2.1 41

3.1 802.15.4 e ZigBee 41

3.2 nesC 50

3.3 TinyOS 51

3.4 Verso l’implementazione 53

3.5 Nodi noti e nodi incogniti 55


iv

3.6 Valutazione degli RSSI e delle distanze tra i beacon 57

3.6.1 Simmetria del canale e dei valori di RSSI 59

3.7 Strutture dati 61

3.8 Aggiornamento della griglia 63

3.9 Messaggi scambiati tra i mote 66

3.9.1 RssiMsg 67

3.9.2 BeaMsg 67

3.9.3 BeaVecMsg 67

3.9.4 PosMsg 68

3.10 Struttura dei componenti realizzati 68

3.10.1 Beacon 68

3.10.2 Nodi incogniti 69

3.11 Consistenza del ROCRSSI 71

Capitolo 4 - Analisi dei risultati 75

4.1 Strumenti 75

4.2 Planning degli esperimenti 80

4.3 Definizione dell’errore 82

4.4 Rilevamento dati indoor 83

4.4.1 Configurazione 1: beacon vicini alle pareti in posizioni random 84

4.4.2 Configurazione 2: beacon lontani dalle pareti allineati alla griglia 85

4.4.3 Configurazione 3: beacon vicini alle pareti allineati alla griglia 87

4.4.4 Configurazione 4: beacon lontani dalle pareti in posizioni random 89

4.5 Errore e configurazione 90

4.6 Errore e numero beacon 92

4.7 Errore e granularità 93

4.8 Casi migliori e casi peggiori 94

4.9 Test outdoor 96

4.10 Analisi energetica 98

4.10.1 Nodi beacon 99

4.10.2 Nodi incogniti 101

4.11 Analisi temporale 102

4.12 Conclusioni 103

Capitolo 5 - Strategie per il miglioramenti delle prestazioni 105

5.1 Griglia e celle 105


v

5.2 Section of Arrival 113

5.3 Angle of Arrival 119

Capitolo 6 - Conclusioni e sviluppi futuri 125

6.1 Conclusioni 125

6.2 Sviluppi futuri 126

Appendice A 130

A.1 Datasheet Iris Mote 130

A.2 Installazione di TinyOS2.1 in Windows 133

A.3 XSniffer 135

Bibliografia 138

Ringraziamenti 142


vi

Indice delle figure

Figura 1.1 – Esempio di rete WSN. La rete può essere utilizzata a vari scopi, per il

rilevamento di dati che sono poi inoltrati ad una Base Station, la quale, a sua

volta, li invia ad un elaboratore. 16

Figura 1.2 – Sensore Iris della Crossbow Technology. 17

Figura 1.3 – Intersezione di due sfere. 21

Figura 1.4 – Intersezione di tre sfere. 22

Figura 1.5 – Correzione del clock del ricevitore GPS. 23

Figura 1.6 – Modulo GPS U-blox LEA-4a; dimensioni: 17 x 22.4 x 3 mm. 24

Figura 1.7 – Esempio di ROCRSSI. 29

Figura 1.8– Esempio di regione di intersezione disconnessa. 30

Figura 1.9 – Pseudocodice ROCRSSI. 32

Figura 2.1 – Esempio di localizzazione con ROCRSSI, che non considera le regioni

esterne alle circonferenze, e ROCRSSI+, che considera anche l’esterno delle

circonferenze centrate in A e B. A, B e C sono nodi beacon, S è un nodo

incognito, S’ indica la posizione stimata dall’algoritmo. 34

Figura 2.2 – Pseudocodice dell’algoritmo ROCRSSI+. 35

Figura 2.3 – Andamento dell’errore al crescere del numero dei beacon. 36

Figura 2.4 – Esempio di utilizzo del ROCRSSI++. 37

Figura 2.5 – Risultati simulativi del ROCRSSI++ confrontati con quelli del

ROCRSSI; si mostra l’andamento dell’errore medio, in centimetri, al variare del

numero dei nodi che costituisce la rete. Nel primo e nel secondo caso 4 nodi

sono beacon, al terzo ci sono 6 beacon. 38

Figura 3.1 – Topologia a stella e topologia peer-to-peer di una rete PAN. 43

Figura 3.2 – PDU del livello fisico in 802.15.4. 45

Figura 3.3 – Esempio di struttura del superframe. 46

Figura 3.4 – Frame generico del sottolivello MAC in 802.15.4. 48

Figura 3.5 – Architettura di TinyOS. 52


vii

Figura 3.6 – Componenti dello strato comunicazione dell’architettura di TinyOS. 53

Figura 3.7 – Pseudocodice del ROCRSSI+. 56

Figura 3.8 – Esempio di rete WSN. A, B, C sono beacon, S è un nodo incognito. 57

Figura 3.9 – Aggiornamento valore associato alle celle interne ad un cerchio. 64

Figura 3.10 – Regione della griglia esterna ad una circonferenza (a) e regione

descritta da una corona circolare (b). 65

Figura 3.11 – Wiring dei componenti relativi a Beacon Node e Unknown Node. 70

Figura 3.12 – Esempio di beacon appartenenti ad una rete. Il beacon uno ha una

distanza dal nodo beacon tre pari a 2 e comunica con un RSSI pari a 7; la

comunicazione tra i beacon due e tre anche ha RSSI 7 ma i nodi distano 1. 71

Figura 3.13 a e b – Zone individuate dall’esecuzione dell’algoritmo nei due casi: a.

scansiona i beacon nell’ordine 1-2-3, b. scansiona i beacon nell’ordine 2-1-3. 73

Figura 3.14 – Pseudocodice della versione consistente del ROCRSSI+. 74

Figura 4.1 – Schermata di Cygwin mentre si eseguono istruzioni di TinyOS. 76

Figura 4.2 – Sensor board MTS420. 77

Figura 4.3 – Programming board Crossbow MIB520. 77

Figura 4.4 – Base station. 78

Figura 4.5 – Il software XSniffer mostra dei messaggi catturati. 79

Figura 4.6 – Griglia e distanza massima. 82

Figura 4.7 – Griglia configurazione 1. le celle con sfondo grigio idicano la posizione

dei beacon, quelle con Ti la posizione reale del nodo incognito nel particolare

esperimento eseguito con 3, 4 e 5 beacon. 84

Figura 4.8 – Griglia configurazione 2. 85

Figura 4.9 – Andamento RSSI rispetto alla distanza con dati della configurazione 2. 86


Figura 4.11 – Grafico RSSI-distanza relativo ai dati della configurazione 3. 88


Figura 4.13 – Media troncata degli errori relativi alle quindici rilevazioni per ogni

configurazione. 90

Figura 4.14 – Relazione tra errore e distanza media dei beacon dalle pareti. 91

Figura 4.15 – Relazione tra errore e distanza media tra i beacon. 92

Figura 4.16 – Variazione dell’errore medio al crescere del numero dei beacon. 93

Figura 4.17 – Variazione dell’errore al crescere della dimensione della cella. 94

Figura 4.18 – Configurazione griglia nel caso oudoor. I nodi da 1 a 5 rappresentano

i beacon; da A a I i test di localizzazione. 97

Figura 4.19 – Grafico distanza-RSSI relativo ai dati dei test oudoor. 98


viii

Figura 4.20 – Consumo energetico in mJ per beacon al crescere del numero di

beacon (n= 3, 4, 5) con valutazione dell’RSSI con un solo messaggio (m=1). 100

Figura 4.21 – Consumo energetico in mJ per beacon al crescere del numero di

messaggi scambiati per la valutazione dell’RSSI (m= 5, 10, 15, 20) con 5

beacon. 100

Figura 4.22 – Consumo energetico in mJ per nodo incognito al crescere del

numero di beacon (n= 3, 4, 5) con valutazione dell’RSSI con un solo messaggio

(m=1). 101

Figura 4.23 – Consumo energetico in mJ per nodo incognito al crescere del numero

di messaggi scambiati per la valutazione dell’RSSI (m= 5, 10, 15, 20) con 5

beacon. 102

Figura 5.1 – Griglia relativa al caso T3 della configurazione 2. 106




Figura 5.5 a-e – Griglia relativa all’esecuzione dell’algoritmo con i dati del caso 1-

T5 con 5 beacon ad ogni iterazione. 112

Figura 5.6 – Sensore munito di antenna direzionale rotante. 114

Figura 5.7 – Sensore Medusa. 114

Figura 5.8 – Sensore Ping-Pong Illumimote della Crossbow. 114

Figura 5.9 – Esempio di griglia suddivisa in sezioni rispetto al beacon in (4. 5). 115

Figura 5.10 – Aggiornamento sezione relativa al beacon X per il nodo incognito C. 116

Figura 5.11 – Griglia del caso 2 della configurazione 0. 1, 2 e 3 sono nodi beacon,

X in (4; 1) è un nodo incognito. 117

Figura 5.12 – Contatori delle celle in seguito ad esecuzione del ROCRSSI+ con

dati relativi al caso 2 della configurazione 0. 118

Figura 5.13 – Contatori delle celle in seguito ad esecuzione del ROCRSSI+ con

SOA con dati relativi al caso 2 della configurazione 0. 119

Figura 5.14 – Circonferenza goniometrica centrata sul beacon di riferimento. 120

Figura 5.15 – Aggiornamento celle relative al beacon X e al nodo incognito A.

Intersezione con corona circolare. 121

Figura 5.16 - Contatori delle celle in seguito ad esecuzione del ROCRSSI+ con

AOA con dati relativi al caso 2 della configurazione 0. 123

Figura 5.17 – Variazione dell’errore al diminuire dell’ampiezza dell’intorno

dell’angolo di arrivo. 124

Figura A.1 – Esempio di schermata di XSniffer in funzione su un PC. 137


ix

Indice delle tabelle

Tabella 2.1 – Confronto tra i risultati sperimentali di ROCRSSI e ROCRSSI+ per

una rete con 3, 4 e 5 beacon in un ambiente di 50 mq. I valori sono espressi in

centimetri. 34

Tabella 3.1 – Livelli dello standard ISO/OSI. 42

Tabella 3.2 – Bande di frequenza e data rete. 44

Tabella 3.3 – BeaTable. 61

Tabella 3.4 – Matrice beacon-beacon. 62

Tabella 3.5 – Esempio di Beavector. 63

Tabella 3.6 – RssiMsg. 67

Tabella 3.7 – BeaMsg. 67

Tabella 3.8 – BeaVecMsg. 68

Tabella 3.9 – PosMsg. 68

Tabella 3.10 – Beavector. 71

Tabella 3.11 – Beatable. 72

Tabella 4.1 – Planning degli esperimenti. 81

Tabella 4.2 – Consumi relativi ad Iris mote per le operazioni di invio e ricezione

messaggi. 99

Tabella 5.1 – Beavector caso 4-T4 con quattro beacon. 108

Tabella 5.2 – Beatable caso 4-T4 con quattro beacon. 108

Tabella 5.3 – Beavector caso 4-T4 con 5 beacon. 110

Tabella 5.4 – Beavector caso 1-T5 con 5 beacon. 110


x

Simboli e abbreviazioni

AoA – Angle of Arrival;

AODV – Ad hoc On Demand Distance Vector;

CSMA-CA – Carrier Sense Multiple Access with Collision Avoidance;

ED – Energy Detection;

FFD – Full Function Device;

GNSS – Global Navigation Satellite System;

GPS – Global Positioning System;

IrDA – Infrared Data Association;

ISM – Industrial, Scientific, Medical;

ITU – International Telecommunication Union;

LLC – Logical Link Control;

LQI – Link Quality Indicator;

LR-WPAN – Low-Rate WPAN;

MAC – Media Access Control;

MEO – Medium Earth Orbit;

nesC – Network Embedded Systems C;

PAN – Personal Area Network;

PDU – Protocol Data Unit;

POS – Personal Operating Space;


xi

RF – Radiofrequenza;

RFD – Reduced Function Device;

ROCRSSI – Ring Overlapping based on Comparison of Received Signal

Strength Indicator;

RSSI – Received Signal Strength Indicator;

SoA – Section of Arrival;

TDoA – Time Difference of Arrival;

ToA – Time of Arrival;

UHF – Ultra High Frequency;

WLAN – WirelessLlocal Area Network;

WPAN – Wireless PAN;

WSN – Wireless Sensor Network.


xii

Introduzione

Negli ultimi anni vanno acquisendo sempre maggiore importanza le Wireless

Sensor Network – WSN – che, come specificato dalla denominazione, sono delle reti di

sensori senza fili; un sensore è un dispositivo utilizzato per misurare una quantità fisica

e convertire il valore rilevato in un valore digitale che può essere inviato attraverso un

trasmettitore radio.

La nascita delle WSN è legata a scopi militari ed a progetti finanziati dal

Dipartimendo della Difesa degli Stati Uniti. Oggi il loro utilizzo è molto più vasto e le

modalità di impiego di tali reti sono molteplici.

In molte di queste applicazioni i sensori costituenti la rete sono liberi di

spostarsi, per cui sorge il problema di determinarne la posizione in particolari istanti.

Ciò deve essere fatto rispettando dei requisiti delle WSN che riguardano costi, consumi

energetici e semplicità. Tale problema prende il nome di localizzazione.

In letteratura sono presenti diversi algoritmi che propongono strategie per

determinare la posizione dei nodi di una rete. Tra questi vi sono quelle basate sulla

metrica RSSI – Received Signal Strength Indicator – ovvero che utilizzano una stima

della potenza del segnale ricevuto per valutare le distanze. In tale categoria rientra il

ROCRSSI – Ring Overlapping based on Comparison of Received Signal Strength

Indicator – il quale ha il pregio di non richiedere hardware particolarmente complicato,


xiii

per cui consente di contenere i costi di realizzazione della rete e di essere semplice da

implementare.

Tuttavia, non sono molti i risultati sperimentali relativi all’utilizzo di tale

algoritmo. Infatti, fatta eccezione per qualche lavoro che riporta di sperimentazioni su

piattaforme obsolete, è stato possibile individuare solo risultati simulativi, i quali si

basano su ipotesi che non sono poi rispettate nella realtà.

Obiettivo di questo lavoro di tesi è di implementare una variante dell’algoritmo

su mensionato, detta ROCRSSI+, migliorando opportunamente il codice per gli

stringenti requisiti dei sensori, per poi poter effettuare degli esperimenti realistici.

Inoltre si intende individuare dei punti in cui intervenire per migliorare le prestazioni

dell’algoritmo.

A tal fine, viene pianificata ed effettuata una campagna di 103 esperimenti in

ambienti indoor ed outdoor che prevede il rilevamento di risultati di localizzazione al

variare di alcuni parametri dai quali è stato osservato dipendere l’errore di

localizzazione.

L’analisi dei risultati ottenuti ha consentito di individuare una configurazione

della rete in un ambiente indoor di 31 metriquadrati in cui l’errore di localizzazione è

pari al 17.23%, corrispondente a 137.15 centimetri, ed una configurazione in un

ambiente outdoor di 103 metriquadrati con errore di localizzazione del 16.80%, pari a

313.15 centimetri. Si tratta di risultati interessanti soprattutto in vista del fatto che sono

migliori di quelli relativi a simulazioni che sono stati considerati soddisfacenti. È stato

poi possibile studiare le prestazioni dell’algoritmo, oltre che in termini di precisione di

localizzazione, in base a consumi energetici e tempi di esecuzione, nonché osservare i

limiti della tecnica, ovvero situazioni in cui pur aumentando l’informazione a

disposizione non è stato possibile osservare un miglioramento delle prestazioni.

Inoltre, vengono introdotte delle tecniche, sia con che senza hardware

aggiuntivo, che consentono di migliorare ulteriormente la qualità della localizzazione,

fino a raggiungere un errore del 12.02%.


xiv

Il testo è strutturato come segue.

Nel Capitolo 1 viene definito il problema della localizzazione in reti di sensori;

sono discussi i sistemi di navigazione satellitare GNSS e vengono introdotti gli

algoritmi di localizzazione ed in particolare il ROCRSSI.

Il Capitolo 2 illustra due varianti del ROCRSSI, gli algoritmi ROCRSSI+ e

ROCRSSI++, mostrandone i miglioramenti rispetto all’algoritmo originale.

Il Capitolo 3 verte sull’implementazione del ROCRSSI+ su sensori Iris con

sistema operativo TinyOS 2.1. Vengono illustrati lo standard ZigBee, il sistema

operativo utilizzato ed il linguaggio di programmazione nesC per poi passare ai dettagli

relativi alle strutture dati utilizzate, allo scambio di messaggi, all’implementazione di

alcuni passi dell’algoritmo.

Il capitolo 4 mostra il planning degli esperimenti ed i risultati ottenuti. Sono

descritte le location in cui vengono effettuate le rilevazioni e definita un’euristica per la

valutazione dell’errore. Viene quindi mostrato l’andamento dell’errore e del consumo

di batteria al variare di alcuni parametri fondamentali, ambiente, numero di beacon,

granularità della griglia, messaggi scambiati.

Il Capitolo 5 illustra delle strategie per migliorare le prestazioni dell’algoritmo

attraverso degli accorgimenti al codice, ovvero rendendo più oculato l’utilizzo dei dati

in ingresso. Inoltre si mostra come migliora la qualità della localizzazione attraverso

l’introduzione di informazioni relative a SoA – Section of Arrival – e AoA – Angle of

Arrival.

Al Capitolo 6 sono tratte le conclusioni sul lavoro svolto e mostrati degli spunti

per lavori futuri.


15

Capitolo 1

Localizzazione in reti di sensori

Uno dei principali problemi delle reti di sensori è quello di determinare la posizione

di ogni elemento costituente la rete nel modo più economico possibile sia dal punto di vista

della realizzazione fisica della rete, che del costo computazionale e di memoria, che del

consumo di batterie.

Probabilmente il metodo più preciso e per il quale è più semplice trovare sul

mercato l’hardware necessario, è quello che fa uso dei sistemi GNSS, descritti di seguito.

Nelle WSN, tuttavia, la necessità di contenere i costi e la complessità spinge alla

definizione di algoritmi di localizzazine ad hoc, dei quali non sono presenti in letteratura

risultati sperimentali di rilievo. In questo capitolo vengono introdotti alcuni algoritmi di

localizzazione ed in particolare il ROCRSSI.

1.1 Le Wireless Sensor Networks

La nascita delle WSN è legata a scopi militari ed a progetti finanziati dal

Dipartimendo della Difesa degli Stati Uniti. Oggi il loro utilizzo è molto più vasto e le

modalità di impiego di tali reti sono molteplici.

Tra i possibili campi di applicazione delle reti di sensori, è possibile citare il

monitoraggio delle acque reflue, in particolare negli USA. Ancora, una WSN costituita da

trasmettitori di pressione sommergibili, può essere utilizzata per misurare e monitorare il

livello dell’acqua nelle discariche e, quindi, controllare il percolato. Un altro campo in cui


16

le reti di sensori trovano diffusa applicazione è quello dei trasporti; dei sensori infatti

possono essere utilizzati per il controllo del traffico automobilistico, di treni, navi o aerei in

determinate zone. Nel settore agricolo è sempre più diffuso l’utilizzo di sensori per il

controllo della pressione dei serbatoi d’acqua o all’interno delle serre.

Particolare attenzione viene rivolta all’utilizzo dei sensori per il monitoraggio

ambientale. Per monitoraggio ambientale si intende l’osservazione di fenomeni fisici che

hanno luogo in un certo ambiente e l’acquisizione di dati ad esso relativi. Tali dati possono

a loro volta essere di diversi tipi e riguardare temperatura, umidità, luminosità, posizione,

così da poter studiare e prevenire incendi, fenomeni climatici, frane.

Importante esempio è il progetto finanziato dalla Regione Campania e che si svolge

nei centri di ricerca dei laboratori CINI-ITEM di Napoli e Strago di Pozzuoli, REMOAM –

Reti di sensori per il MOnitoraggio dei rischi AMbientali – per l’analisi dei rischi

ambientali derivanti da fenomeni franosi.

Viste le modalità di impiego, le reti di sensori wireless devono avere le seguenti

Figura 1.1 – Esempio di rete WSN. La rete può essere utilizzata a vari scopi, per il rilevamento di dati che

sono poi inoltrati ad una Base Station, la quale, a sua volta, li invia ad un elaboratore.

WSN

BASESTATION


17

caratteristiche:

� ridotte capacità di memoria;

� ridotte capacità di calcolo;

� basso consumo energetico;

� basso costo;

� dimensioni ridotte di ogni dispositivo;

� resistenza a particolari condizioni ambientali;

� supportare particolari failures (dei canali di comunicazione, dei nodi, …);

� scalabilità.

Naturalmente tali caratteristiche devono essere soddisfatte da ogni applicazione

realizzata per WSN.

1.2 Il problema della localizzazione

Tra le applicazioni in cui le reti di sensori senza filo trovano ampio utilizzo, come

già accennato, rientra il monitoraggio ambientale e, in particolare, lo studio di terreni

soggetti a frane e smottamenti. L’osservazione di tali ambienti richiede il rilevamento di

alcuni dati sensibili, quali temperatura e umidità, che possono essere ricavati attraverso

l’utilizzo di nodi equipaggiati con apposite sensor board. Altra informazione di rilievo è

quella relativa alla modalità di movimento del terreno franabile; tale movimento può essere

studiato rendendo i sensori liberi di muoversi col terreno e facendo in modo che questi

siano in grado di comunicare la loro posizione in determinati istanti così da poterne

tracciare lo spostamento che rispecchia quello del suolo.

Figura 1.2 – Sensore Iris della Crossbow Technology.


18

Dunque, ci si rende conto dell’importanza di determinare la posizione dei nodi

costituenti la rete. Un esempio di sistema in grado di determinare la posizione di alcuni

dispositivi è il GNSS – Global Navigation Satellite System – per la navigazione satellitare,

di cui fa parte il GPS. Sebbene siano presenti in commercio diversi dispositivi GPS, che

saranno trattati in seguito, il loro utilizzo nelle reti di sensori è, purtroppo, limitato. Infatti il

consumo energetico di un modulo GPS con cui può essere equipaggiato un sensore è

elevato. Facendo riferimento ai dati riportati in [18], abbiamo che un sensore del tipo

Mica2, ha un consumo di corrente di 21 mA per la trasmissione radio, 16 mA per la

ricezione radio e 110,106 mA per l’utilizzo del modulo GPS; tali dati mostrano quanto sia

dispendioso dal punto di vista delle batterie l’utilizzo dei ricevitori satellitari rispetto alle

operazioni comunemente eseguite da un sensore. Tornando al caso dello studio dei terreni

franosi, è facile intuire la difficoltà della sostituzione delle batterie e l’impossibilità di

utilizzarne alcune di dimensioni maggiori per aumentarne l’autonomia, per cui uno dei

principali obiettivi nella progettazione per WSN è quello di ridurre al minimo i consumi

energetici.

Altro requisito delle reti di sensori è la semplicità. I sensori sono quindi dei

dispositivi embedded di ridotte capacità computazionali e di memoria, che consentono di

rilevare dati sensibili ed eseguire solo semplici operazioni. Pertanto, sono stati realizzati

sistemi operativi appositi per sensori e definiti nuovi linguaggi per la loro programmazione.

Ciò implica l’impossibilità per un sensore di effettuare operazioni che richiedono

particolari capacità di memoria e di calcolo per valutare informazioni come la propria

posizione.

La semplicità dei sensori è relativa anche ai singoli componenti utilizzati per il

rilevamento dei dati, per cui talvolta si dispone solo di una stima dei valori che consentono

di effettuare valutazioni qualitative più che quantitative al fine di ottenerne un ordinamento.

Tali requisiti di semplicità contribuiscono al soddisfacimento anche di un altro

requisito, quello di economicità. Infatti nelle reti WSN si tende a mantenere contenuto il

costo dei singoli dispositivi, in vista anche delle dimensioni che può assumere una rete di

sensori, che tra le caratteristiche hanno la possibilità di sviluppo in larga scala e, quindi, la


19

scalabilità. Date le grandi dimensioni, non è neanche possibile considerare il grafo di una

rete completamente connesso, pertanto le operazioni effettuate da un sensore non possono

richiedere la connettività diretta con un altro sensore, se non in particolari circostanze1.

Quindi un sensore che deve valutare la propria posizione, può utilizzare solo le

informazioni ottenute attraverso lo scambio di messaggi con i nodi visibili al suo modulo

radio, detti comunemente neighbors (vicini).

Il problema di dover determinare la posizione di un nodo viene detto localizzazione.

Visti i vincoli introdotti precedentemente, si può quindi definire quello della localizzazione

in reti di sensori come il problema di determinare la posizione di tutti o alcuni nodi

costituenti una rete di sensori, minimizzando l’errore, la capacità di memoria occupata, la

complessità computazionale, il consumo energetico necessario all’esecuzione delle

operazioni, la complessità dell’hardware utilizzato, i costi di realizzazione della rete stessa.

1.3 Sistemi GNSS

Il sistema satellitare di navigazione globale fornisce un servizio di posizionamento

geo-spaziale a copertura globale. Il GNSS consente a piccoli ricevitori di determinare la

propria posizione sulla terra, sul mare o in aria, con un errore di pochi metri utilizzando

segnali radio trasmessi da satelliti artificiali, appositamente realizzati e disposti su

particolari orbite gravitazionali. Il sistema di navigazione GPS, diffuso nel campo

automobilistico, ne è un esempio.

In origine la navigazione satellitare nacque per scopi militari; si intendeva rendere

più preciso il lancio missilistico per evitare obbiettivi errati. Oggi gli utilizzi sono

molteplici. Il più diffuso è quello dell’ausilio nei trasporti, sia su terra che aria o acqua.

Oppure sono utilizzati per determinare la posizione di incidenti, così da migliorare i tempi

di arrivo dei soccorsi. Un ente che può fornire servizi di localizzazione satellitare può in

qualsiasi momento decidere di degradare la qualità di tale servizio o annullarlo del tutto in

1 In alcuni casi si potrebbe pensare di strutturare la rete a maglie, ognuna delle quali è rappresentabile con un grafo strettamente connesso e quindi ogni nodo può raggiungere un altro nodo della rete con un percorso formato da un solo arco.


20

una determinata zona. È anche, e soprattutto, per tale motivo che i governi dei vari paesi

cercano di finanziare lo sviluppo di propri sistemi di navigazione satellitare.

Tra i sistemi GNSS ci sono l’americano NAVSTAR Global Positioning System, o

semplicemente GPS, il sistema russo GLONASS e l’europeo GALILEO.

1.3.1 Global Positioning System

È un sistema di posizionamento satellitare gestito dal dipartimento della difesa degli

Stati Uniti. Attualmente è l’unico sistema GNSS pienamente funzionante e disponibile.

Esso è costituito da tre segmenti:

� spazio, il quale comprende da 24 a 32 satelliti nell’orbita MEO – Medium Earth

Orbit – pari a circa 10000 km di altezza dalla Terra;

� control, che inculude una Master Control Station, una Alternate Master Control

Station ed un insieme di antenne e Monitor Station;

� user, ovvero gli utilizzatori del servizio, quindi militari, che utilizzano il Precise

Positioning System, e utenti civili, per scopi scientifici, industriali e di

navigazione.

Il funzionamento del sistema si basa su un insieme di segnali radio inviati dai

satelliti che ne fanno parte; tali messaggi includono informazioni circa il tempo dell’invio

del messaggio, dello stato del sistema e delle orbite dei satelliti costituenti lo Space

Segment. I satelliti utilizzano diverse frequenze per diversi scopi che vanno da 1176.45

MHz a 1575.42 MHz. Il ricevitore GPS utilizza i messaggi ricevuti per determinare il tempo

impiegato dal segnale per giungere da ogni satellite e determinare la distanza rispetto ad

ognuno di essi; tali valori vengono poi utilizzati nella trilaterazione per determinare la

posizione del ricevitore.

La trilateraizione è un metodo per determinare l’intersezione di tre superfici

sferiche, noti centri e raggi per ognuna di esse.

Se due sfere si intersecano in più di un punto, l’intersezione è un cerchio, come

mostrato in figura 1.3.


21

L’intersezione tra tre superfici sferiche, dunque, consiste nell’intersezione di una

superfice sferica con una circonferenza e, quindi, nella determinazione di due punti.

Analiticamente, considerando il caso in figura 1.4, si hanno le equazioni di tre sfere:

22221 zyxr ++=

( ) 22222 zydxr ++−=

( ) ( ) 22223 zjyixr +−+−=

Risolvendo il sistema delle equazioni di cui sopra si ottengono le coordinate:

d

drrx

2

222

21 +−

= ; xj

i

j

jirry −

++−=

2

2223

21 ; 222

1 yxrz −−±= .

Come si vede le soluzioni dell’intersezione possono essere zero, una oppure due.

Tornando al GPS e trascurando l’errore, il ricevitore è in grado di localizzarsi

utilizzando i dati dei messaggi di almeno quattro satelliti; indicando per ogni satellite i le

coordinate spaziali con xi, yi, zi e con ti il tempo di invio del messaggio abbiamo il vettore

[ ]iiiii tzyxa ,,,= ; conoscendo il tempo di arrivo del messaggio at , il ricevitore può valutare

Figura 1.3 – Intersezione di due sfere.


22

il tempo di trasmissione del messaggio dal satellite i come ( )ia tt − ; supponendo che il

messaggio abbia viaggiato alla velocità della luce c, la distanza può essere stimata come

( ) cttd iai ⋅−= . In tal modo è possibile determinare una sfera di centro ( )iii zyx ,, e raggio

id , sulla cui superficie giace il ricevitore. Avendo considerato l’assenza di errore,

l’intersezione di quattro sfere così costruite consente di determinare la posizione esatta del

ricevitore ( )rrr zyx ,, .

È stato mostrato che l’intersezione di tre sfere consente di individuare due punti. Nel

caso di mezzi di terra, il punto più vicino alla superficie terrestre può essere considerato

come la posizione del ricevitore; viceversa, nel caso di aerei, è il punto più lontano dalla

terra ad indicare la posizione dell’oggetto. La posizione corretta viene determinata

realizzando l’intersezione con una quarta sfera.

Abbandonando il caso ideale di assenza di errore, poiché il sistema GPS si basa

sulla valutazione della distanza ricevitore-satellite utilizzando i tempi di invio e ricezione di

messaggi, costituisce fonte di errore, ed assume dunque particolare importanza, la

r1r2

r3

(0,0) (d,0)

(i,j)

Figura 1.4 – Intersezione di tre sfere.


23

correttezza del clock del ricevitore. In ambito civile, nel quale è fondamentale contenere i

costi ed eviatare una localizzazione eccessivamente precisa, la posizione stimata attraverso

l’intersezione di tre sfere, può essere corretta con i dati relativi ad un quarto satellite, e

quindi una quarta sfera. Se r4 indica la distanza della posizione stimata dal ricevitore dal

quarto satellite, e p4 è il range di tale satellite, il valore 44 prdia −= indica la distanza tra la

posizione stimata dal ricevitore con tre satelliti e la sfera del quarto satellite.

Il valore cdb a /= indica la differenza tra il tempo corretto e quello del clock del

ricevitore e quindi consente di determinare se il ricevitore deve incrementare o diminuire il

clock.

1.3.2 GLONASS

GLONASS – GLObal NAvigation Satellite System – è un sistema di navigazione

r4

p 4

da

ricevitoresatellite 4

Figura 1.5 – Correzione del clock del ricevitore GPS.


24

satellitare gestito dalle Forze Spaziali Russe. Nacque per migliorare il sistema preesistente

Tsiklon e forniva informazioni di posizionamento e velocità da utilizzare per la navigazione

militare e sistemi missilistici.

Il sistema, il cui funzionamento è simile a quello del GPS, utilizza due tipi di

segnali. I segnali Standard Precision lavorano alle frequenze in un intorno di 1602.0 MHz;

il segnale High Precision è in quadratuta di fase rispetto ai segnali SP e con frequenze in un

intorno di 1246.0 MHz.

Attualmente il sistema è composto di 22 satelliti e copre l’intero territorio russo.

1.3.3 GALILEO

Si tratta di un sistema di navigazione satellitare alternativo e complementare a GPS

e GLONASS, progettato dall’ Unione Europea e dall’ Agenzia Spaziale Europea.

L’obiettivo del progetto è quello di migliorare la qualità di posizionamento rispetto agli altri

sistemi, introducendo informazioni circa l’altezza rispetto al livello del mare e migliorando

il posizionamento per latitudini più alte; inoltre, a differenza di GPS e GLONASS, viene

sviluppato per uso civile piuttosto che militare.

GALILEO fornirà quattro servizi di localizzazione. Un OS – Open Service libero a

tutti con errore minore di 15 metri in orizzontale e di 35 metri in verticale; il CS –

Commercial Service fornirà un servizio con errore inferiore al metro; Public Regulated

Service e Safety of Life Service avranno precisione simile all’ OS, ma saranno rivolti alle

autorità pubbliche per il rilevamento di problemi in meno di dieci secondi e per il

monitoraggio di sistemi di trasporto safety-critical.

1.4 Localizzazione in WSN

Date le ridotte dimensioni dei moduli GPS presenti in commercio è possibile

realizzare delle sensor board da integrare ai sensori più diffusi per effettuare un

posizionamento satellitare. Tuttavia gli elevati consumi energetici di tali moduli ne rendono

impraticabile l’utilizzo su tutti i nodi di una rete di sensori.


25

Quindi, occorre definire e sperimentare algoritmi per la localizzazione in reti di

sensori senza fili che soddisfino tali obiettivi.

In letteratura sono diversi gli algoritmi definiti per la localizzazione in WSN.

Vi sono algoritmi per sistemi centralizzati, che prevedono l’utilizzo di un super

nodo per l’elaborazione dei dati provenienti dagli altri nodi e quindi dotato di capacità di

elaborazione ed autonomia energetica maggiori; ci sono poi dei sistemi distribuiti nei quali

ogni nodo raccoglie le informazioni necessarie alla sua localizzazione.

La prima tipologia di sistemi è in grado di raggiungere ottime prestazioni dal punto

di vista della precisione di localizzazione, presenta però l’inconveniente del single-point of

failure del nodo centrale e costi elevati, i quali crescono ulteriormente se si pensa di

introdurre ridondanza. La strategia distribuita, invece, consente di ridurre notevolmente i

costi di realizzazione della rete, di semplificarla notevolmente nonché di ridurre i consumi

energetici.

Una ulteriore classificazione degli algoritmi viene fatta in base al metodo di stima

delle distanze, per cui si hanno algoritmi range-based e algoritmi range-free.

Gli algoritmi range-based determinano la posizione dei nodi attraverso le sitme della

distanza punto-punto, per cui la loro qualità è strettamente legata all’hardware necessario

alla valutazione di suddette distanze. Ciò comporta un aumento dei prezzi ed una notevole

complessità dei dispositivi, cosa che va contro l’obiettivo principale di semplicità ed

economicità.

Viceversa, gli algoritmi range-free, non utilizzano distanze assolute bensì relative,

ovvero consentono di determinare la posizione di un nodo, detto incognito, in base al

Figura 1.6 – Modulo GPS U-blox LEA-4a; dimensioni: 17 x 22.4 x 3 mm.


26

confronto di presunte distanze da più nodi con posizione nota, detti noti o beacon. In tal

modo si semplifica notevolmente l’hardware necessario alla localizzazione riducendo

dunque costi e complessità.

Esistono diverse tecniche per la stima delle distanze o posizioni relative tra i nodi,

dette tecniche di ranging. Tale stima può essere più o meno accurata in base alla qualità

dell’hardware utilizzato ed alle richiesete dell’algoritmo scelto.

L’ RSSI – Received Signal Strength Indicator – indica la potenza di un segnale radio

ricevuto da un sensore; se tale segnale è inviato da un altro sensore della rete, tale

informazione può essere utilizzata per valutare la distanza tra i nodi. Supponendo infatti una

perdita di potenza del segnale proporzionale allo spazio presente tra i sensori, si può

considerare il valore di RSSI inversamente proporzionale alla distanza tra i nodi.

ToA – Time of Arrival – è un parametro che può essere utilizzato da due sensori

sincronizzati che comunicano tra loro per determinare la loro distanza; infatti, conoscendo

la velocità di propagazione del segnale, la distanza può essere valutata, similmente al

sistema GPS, come il prodotto tra tale velocità ed il tempo che il segnale impiega per

andare da un nodo all’altro.

TDoA – Time Difference of Arrival – può essere utilizzato in una rete in cui tutti i

sensori sono perfettamente sincronizzati; se infatti allo stesso istante tutti i nodi meno uno,

inviano un segnale al nodo rimanente, questo può determinare una relazione d’ordine delle

distanze tra se e gli altri elementi della rete.

AoA – Angle of Arrival – può consentire ad un nodo di localizzarsi se conosce tale

angolo almeno rispetto a tre nodi beacon. Come viene mostrato al Capitolo 5, tale valore

può essere utilizzato anche per migliorare la qualità della localizzazione basata su una delle

tecniche precedenti.

1.4.1 Algoritmi di localizzazione

Gli algoritmi range-free utilizzano una delle tecniche di ranging viste

precedentemente per effettuare dei confronti ed ottenere un ordinamento approssimativo dei


27

nodi beacon; quindi non cercano la distanza esatta tra i nodi della rete, bensì tentano di

creare una relazione d’ordinte tra essi. Effettuando poi dei confronti tra i valori ottenuti con

una delle tecniche di ranging e distanze note, è possibile fare delle valutazioni simili a

quelle della trilaterazione, ma semplificando le superfici sferiche in circonferenze e, quindi,

riportandosi al caso bidimensionale. Questa fase di vera e propria localizzazione viene detta

di positioning.

Di seguito sono accennate alcune tecniche di localizzazione.

Lateration [24], stima la posizione di un nodo incognito utilizzando tre

circonferenze centrate su nodi beacon e di raggio pari alla distanza stimata tra ogni beacon

ed il nodo da localizzare.

SpotOn [24], stima le distanze con l’RSSI per poi utilizzare la Lateration.

Bulusus et al. in [30] propongono che un nodo incognito può valutare la sua

posizione come la media delle coordinate dei beacon da cui ha ricevuto messaggi, e quindi

visibili al suo modulo radio.

AHLoS – Ad Hoc Localization System – [1] utilizza sia RSSI che ultrasuoni per la

stima delle distanze dei nodi incogniti dai nodi beacon, per poi utilizzare la multilaterazione

iterativa per determinare la poiszione dei nodi incogniti. Una volta determinata la posizione

di un nodo incognito, questo può essere utilizzato come beacon per la localizzazione di altri

nodi.

L’algoritmo Minimum Maximum [26] valuta la posizione di un nodo come il

centroide dell’area di intersezione dei quadrati centrati sui beacon e di lato pari al doppio

della distanza stimata del beacon dal nodo incognito. Caratteristica principale di questo

metodo è la velocità con cui si riesce a localizzare un nodo.


28

APIT si basa sul PIT – Point-in-Trinagulation Test – nel quale un nodo sceglie tre

nodi beacon e testa se è all’interno del triangolo costruito con i nodi noti come vertici, per

poi ripetere tale operazione con più nodi beacon visibili al nodo incognito per determinare

delle intersezioni tra triangoli e quindi ridurre l’area in cui stima di trovarsi.

1.5 ROCRSSI

Tra gli algoritmi range free rientra il ROCRSSI, sul quale è incentrato questo lavoro

di tesi.

Si tratta di un algoritmo il cui scopo è quello di ottenere una buona localizzazione e

ridurre la comunicazione tra nodi incogniti e nodi beacon. Per nodi incogniti si intendono i

nodi che devono determinare la propria posizione, i beacon sono invece i nodi la cui

posizione è nota a priori o equipaggiati con hardware in grado di determinarla, come un

modulo GPS. L’idea base è che un sensore utilizza l’intersezione di corone circolari che si

intersecano per restringere l’area in cui stima di essere.


29

Nell’esempio di figura 1.7, il nodo incognito S può determinare che la sua distanza

da A è maggiore della distanza tra A e B, ma minore della distanza tra A e C, quindi

conclude di trovarsi nella corona circolare centrata in A e con raggio interno pari alla

distanza tra A e B e raggio esterno uguale alla distanza tra A e C. Similmente S può

costruire una corona circolare centrata in B ed un cerchio centrato in A e valutare la sua

posizione come il baricentro dell’intersezione di queste aree.

Le corone circolari possono essere generate dal confronto della potenza del segnale

che un sensore riceve da un beacon con la potenza del segnale che gli altri beacon ricevono

dallo stesso nodo noto. Tornando alla figura 1.7, dove A, B e C sono tre beacon, ed S il

nodo incognito, supponiamo che A invia messaggi per cui i nodi B, C ed S rilevano le

potenze del segnale RSSIAB, RSSIAC e RSSIAS. Supponendo di poter determinare la

relazione d’ordine RSSIAB > RSSIAS > RSSIAC, S valuta di trovarsi nella corona circolare

mostrata in figura 1.7 (a. Poiché il valore dell’RSSI è utilizzato per effettuare dei confronti

e non per valutare le distanze punto-punto, ROCRSSI è un algoritmo range-free.

Per una corretta localizzazione occorrono almeno tre nodi noti, tuttavia può accadere

che ci sono pochi nodi beacon visibili ad un nodo incognito per cui la regione di

intersezione può essere disconnessa. In tal caso il baricentro è in una zona in cui di fatto il

Figura 1.7 – Esempio di ROCRSSI.

A

B

S

C

C

S

AB

(b(a


30

nodo non può essere.

La correttezza del ROCRSSI è basata sull’ipotesi che al crescere della distanza tra

nodo mittente e nodo ricevente diminuisce la potenza del segnale ricevuto, ovvero che il

valore dell’RSSI è inversamente proporzionale alla distanza. Tuttavia risultati sperimentali

mostrano che la propagazione di segnali RF non è omogenea in tutte le direzioni, ovvero

ogni direzione può essere caratterizzata da un’attenuazione differente. Il ROCRSSI,

dunque, non esclude la generazione di corone circolari errate per cui è possibile effettuare

una stima errata a causa dell’irregolarità della radiopropagazione.

L’algoritmo è suddivisibile in due fasi, una di propagazione dell’RSSI ed una di

stima della posizione.

In un primo momento ogni beacon invia in broadcast dei messaggi che gli altri nodi

riceveranno ed utilizzeranno per la valutazione dell’RSSI tra se ed il beacon mittente.

Dunque tale fase termina quando ogni beacon conosce l’RSSI relativo al segnale

proveniente da ogni altro beacon della rete.

Può quindi avere luogo la localizzazione quando il nodo incognito S ha sufficienti

S’

S

Figura 1.8– Esempio di regione di intersezione disconnessa.


31

informazioni per la stima della sua posizione. Alla pagina seguente, in figura 1.9, si riporta

lo pseudocodice relativo a tale fase.

Si noti che se l’insieme SA1 è vuoto, ma SA2 ha elementi, si genera un cerchio; se

nessuno dei due insiemi è vuoto, invece, si genera una corona circolare.

Il passo 4 richiede la valutazione della regione di intersezione e poi, il passo 5, il

calcolo del baricentro della stessa. Per effettuare tali operazioni viene utilizzato un

algoritmo di scansione della griglia [42]. Questa tecnica consiste nel considerare l’area su

cui è presente la rete come una griglia formata da celle ad ognuna delle quali è associato un

contatore. Tale contatore viene incrementato quando si determinano dei cerchi o delle

corone circolari che comprendono la cella cui esso è associato; ad ogni passo viene quindi

modificato il valore relativo ad alcune celle ed alla fine quelle con valore maggiore

rappresentano la zona di intersezione. In questo lavoro, si considera la griglia come un

piano cartesiano, dunque ogni nodo ha delle coordinate che consentono di identificare la

cella in cui si trova. Per determinare il baricentro della zona di intersezione si effettuano

quindi delle operazioni con le coordinate delle celle con valore massimo. Indicando con I

tale insieme di celle, con ix ed iy le coordinate della generica cella appartenente a I e con

n la cardinalità dell’insieme, le coordinate del baricentro sono:

∑∈

=Ii

ixn

x1

; ∑∈

=Ii

iyn

y1

.


32

È evidente che dalla granularità della griglia dipende la precisione del metodo. Tale

aspetto sarà approfondito in fase di sperimentazione. Inoltre, l’algoritmo di grid-scan aiuta a

ridurre l’influenza di corone circolari errate. Supponendo che il 50% più uno delle corone

circolari determinate dal confronto dei valori di RSSI è corretta, l’intersezione di queste

determina un’area le cui celle hanno il contatore associato con valore maggiore rispetto ad

ogni altra cella, per cui le corone circolari non corrette non saranno considerate nel calcolo

del baricentro dell’area in cui si stima essere presente il nodo incognito.

Figura 1.9 – Pseudocodice ROCRSSI.


33

Capitolo 2

ROCRSSI+ e ROCRSSI++

Il capitolo precedente ha introdotto gli algoritmi per la risoluzione del problema

della localizzazione in reti di sensori wireless. In particolare è stato illustrato l’algoritmo

ROCRRSI. Questo capitolo introduce due algoritmi derivati da questo per migliorarne la

qualità della localizzazione, il ROCRSSI+ ed il ROCRSSI++.

2.1 ROCRSSI+

Il ROCRSSI cerca di individuare corone circolari e cerchi la cui intersezione

determina l’area in cui è, o meglio dovrebbe essere, posizionato il nodo. Non sono invece

prese in considerazione le zone con distanza maggiore di un certo valore dai beacon, il che

può determinare perdita di informazione. Il ROCRSSI+ proposto in [28], considera valide

regioni d’intersezione anche le parti di spazio esterne ad una circonferenza. Avendo definito

al capitolo precedente la procedura di grid-scan, considerare la regione esterna ad una

circonferenza, significa incrementare il contatore di tutte le celle esterne ad essa. Un

esempio di come migliora la stima della posizione con tale algoritmo è mostrata in figura

2.1, dove A, B e C sono nodi noti ed S è un nodo incognito; come si vede, nel caso (a la

regione di intersezione è quella interna alla circonferenza centrata in C, non avendo

considerato le zone esterne alle circonferenze centrate in A e B; nel caso (b, invece,

considerando anche tali regioni si restringe l’area di intersezione, ottenendo una stima più

precisa.


34

Il ROCRSSI+ differisce dall’algoritmo originale anche per l’aggiunta dell’ipotesi di

simmetria del canale, il che consente di considerare la potenza del segnale inviata da A a B

uguale a quella del segnale inviato da B ad A, e quindi RSSIAB=RSSIBA. Tale

considerazione consente al nodo incognito di scansionare la griglia appena riceve un

messaggio da un beacon senza dover attendere altri pacchetti, semplificando così

l’implementazione dell’algoritmo.

I risultati di [38] riportati in tabella 2.1, mostrano come migliorano le prestazioni

rispetto all’algoritmo originale.

ROCRSSI ROCRSSI+

Errore medio Dev std Errore medio Dev std

437 216 427 210

414 245 402 266

403 254 388 217 Tabella 2.1 – Confronto tra i risultati sperimentali di ROCRSSI e ROCRSSI+ per una rete con 3, 4 e 5 beacon in un ambiente di 50 mq. I valori sono espressi in centimetri.

Di seguito lo pseudocodice dell’algoritmo.

Figura 2.1 – Esempio di localizzazione con ROCRSSI, che non considera le regioni esterne alle

circonferenze, e ROCRSSI+, che considera anche l’esterno delle circonferenze centrate in A e B.

A, B e C sono nodi beacon, S è un nodo incognito, S’ indica la posizione stimata dall’algoritmo.

C=S’

S

ab

c

(a

ab

c

(b

AB

C

S S’

AB


35

2.2 ROCRSSI++

Diversi risultati simulativi, tra cui [36] e [38], hanno mostrato che l’errore medio di

localizzazione diminuisce al crescere del numero dei beacon, detti anche nodi àncora.

Inoltre al paragrafo 1.5 è stato visto che la localizzazione può essere del tutto errata se

eseguita con pochi beacon e, in particolare, la figura 1.8 ha mostrato che occorrono almeno

tre nodi noti. Dunque, come illustrato in seguito dai risultati sperimentali ottenuti, la

determinazione del numero di beacon presenti nella rete è una scelta fondamentale dalla

Figura 2.2 – Pseudocodice dell’algoritmo ROCRSSI+.


36

quale dipende la precisione della localizzazione.

Il ROCRSSI++, descritto in [17], propone di utilizzare alcuni dei nodi incogniti che

hanno effettuato la localizzazione come nodi beacon, detti in tal caso beacon di 2° livello,

così da poter determinare dinamicamente il numero di beacon della rete.

Si consideri il caso di figura 2.4. A, B e C sono nodi beacon, S e T nodi incogniti; se

il nodo S si localizza in S’ prima che il nodo T effettui la localizzazione, e si proclama

beacon di secondo livello, T avrà a disposizione un altro beacon per valutare la sua

posizione. T’ indica la posizione in cui il nodo si localizza. Naturalmente il nodo S si

localizza con un certo errore, che influenzerà anche la stima di T. Tuttavia la localizzazione

tende comunque a migliorare, soprattutto nei casi in cui il nodo incognito ha come vicini

Figura 2.3 – Andamento dell’errore al crescere del numero dei beacon.


37

solo due nodi beacon.

Il ROCRSSI++ prevede due fasi. La prima, detta Phase 1, consiste nello scambio di

messaggi tra i nodi beacon per determinare gli RSSI che caratterizzano le comunicazioni tra

loro; la seconda, detta Phase 2, consiste nell’invio da parte dei beacon delle informazioni

acquisite alla fase precedente ai nodi incogniti ed all’esecuzione della localizzazione da

parte di questi.

Completate le due fasi precedenti, un nodo incognito deve determinare se ha le

caratteristiche per essere beacon di secondo livello. Tali caratteristiche sono:

1. sufficiente riserva energetica per svolgere la funzione di beacon;

2. la localizzazione deve essere avvenuta utilizzando esclusivamente beacon di

S’

A

C

B

TS

T’

Figura 2.4 – Esempio di utilizzo del ROCRSSI++.


38

primo livello;

3. non devono esserci altri beacon di secondo livello vicini.

Il terzo requisito serve ad evitare che ogni nodo dopo la localizzazione diventi

beacon di secondo livello e quindi contenere il numero di questi. Se sono soddisfatti i

requisiti visti, il nodo invia un messaggio tramite il quale comunica di essere beacon di

secondo livello. Se, per motivi di consumo di batterie, determina di non poter più essere

beacon di secondo livello, il nodo lo comunica agli altri componenti della rete.

I risultati simultaivi riportati nello stesso lavoro [17] mostrano che l’algoritmo

introdotto effettivamente migliora la localizzazione rispetto all’algoritmo originale

ROCRSSI. Infatti, come si può osservare dalla figura 2.5, in prove effettuate con diverso

numero di nodi costituenti la rete, in cui varia anche il numero dei beacon da 4 a 6, si ha che

in ogni caso il ROCRSSI++ migliora le prestazioni dell’algoritmo originale. È stato rilevato

che il miglioramento medio dell’algoritmo modificato è pari al 30%.

Figura 2.5 – Risultati simulativi del ROCRSSI++ confrontati con quelli del ROCRSSI; si mostra

l’andamento dell’errore medio, in centimetri, al variare del numero dei nodi che costituisce la rete. Nel

primo e nel secondo caso 4 nodi sono beacon, al terzo ci sono 6 beacon.


39

2.3 Studi sperimentali sul ROCRSSI

Da quanto visto ai paragrafi precedenti, si intuisce che sono stati molti e diversi gli

approcci al problema della localizzazione in WSN; essi differiscono per assunzioni

sull’hardware e sulla tipologia della rete, per il modo di propagazione del segnale, per le

richieste energetiche, per l’ambiente in cui devono essere utilizzati.

Tra questi è stato scelto di studiare il metodo basato su metrica RSSI con

sovrapposizione di corone circolari. In particolare in questo lavoro viene implementata la

versione modificata ROCRSSI+, la quale sarà analizzata in diversi ambienti e con diverse

configurazioni della rete, così da mostrare anche l’andamento dell’errore al variare del

numero dei beacon presenti nella rete.

Il ROCRSSI prevede l’utilizzo di nodi beacon, ovvero nodi la cui posizione è nota a

priori. Ciò è possibile se tali nodi vengono fissati nell’ambiente in particolari posizioni

dall’uomo, oppure è possibile dotare solo tali nodi di hardware aggiuntivo capace di

effettuare la localizzazione con buona precisione. Come visto, infatti, esistono moduli GPS

appositi, da integrare su sensor board da collegare ai nodi così da consentirne

l’autolocalizzazione2. Naturalmente in tal caso se ne pregiudica l’utilizzo indoor, dove il

segnale dei satelliti GPS non è percepibile.

Sebbene in letteratura tale algoritmo sia ampiamente trattato, non sono molti i

risultati sperimentali relativi al suo utilizzo, ma la maggior parte di essi sono effettuati

tramite simulazione al calcolatore, utilizzando strumenti quali Matlab e TOSSIM.

I risultati riportati in [17] visti in figura 2.5, sono stati ottenuti attraverso l’uso di

TOSSIM. I valori ottenuti, purtroppo, non rispecchiano il caso reale, dove, come vedremo,

l’errore è di ordini di grandezza più grande.

Altri lavori che trattano il ROCRSSI sono [5], [6], [35], [36], [38], tuttavia anche in

questi casi si tratta per lo più di risultati ottenuti attraverso simulazione. Degno di nota il

lavoro [28], nel quale viene realizzata l’implementazione dell’algoritmo ROCRSSI+ su

piattaforma EyesIFX. Si tratta comunque di una piattaforma più vecchia della Iris qui

2 Considerazioni energetiche e di costi effettuate precedentemente hanno illustrato l’impossibilità di dotare tutti i sensori di tale tecnologia per l’autolocalizzazione.


40

utilizzata e l’unica variabile considerata è il numero di beacon.

L’inattendibilità dei risultati simulativi è legata principalmente ai valori di RSSI

considerati. In tali casi, infatti, tali valori non sono rilevati sul campo e non sono in grado di

mostrare il reale andamento della potenza del segnale al variare della distanza, in quanto

essa è influenzata da diversi fattori, tra cui interferenza con altri segnali e fenomeni di

riflessione. Pertanto, simulazioni che considerano sempre verificata l’inversa

proporzionalità tra RSSI e distanza, restituiscono risultati diversi dal caso reale, come sarà

mostrato al capitolo 4.


41

Capitolo 3

Implementazione del ROCRSSI+ in TinyOS2.1

In questo capitolo viene illustrata la realizzazione del codice dell’algoritmo

ROCRSSI+ visto al capitolo precedente per sensori Iris Mote con sistema operativo TinyOS

2.1.

Si mostrano dapprima le caratteristiche dello standard di comunicazione per WPAN

802.15.4 e la specifica ZigBee, utilizzata dai sensori Iris, le caratteristiche del linguaggio

nesC e del sistema operativo TinyOS, per poi entrare nel dettaglio dell’implementazione

illustrando le scelte effettuate relative alle strutture dati, allo scambio di messaggi,

all’algoritmo di grid-scan, al fine di rendere il codice ottimizzato sia dal punto di vista dello

spazio di memoria occupato sia della complessità computazionale. Infine si illustra una

correzione da apportare all’algoritmo per garantirne la consistenza.

3.1 802.15.4 e ZigBee

Nel corso degli anni sono state create diverse specifiche industriali per la

comunicazione senza fili. Gli scopi sono molteplici, così come i requisiti. I sistemi di

comunicazoine wireless più diffusi utilizzano onde radio ad alta frequenza, nota anche

come radiofrequenza o RF. In particolare le onde UHF – Ultra High Frequency – hanno

frequenza compresa tra i 300 e i 3000 MHz e vengono utilizzate per telefonia, TV e reti

wireless.

Particolare interesse è rivolto alle frequenze tra i 2.4 ed i 2.5 GHz, banda


42

denominata ISM – Industrial, Scientific, Medical – libera da ogni licenza di utilizzo.

Le WPAN – Wireless Personal Area Network – sono usate per lo scambio di

informazioni a distanze brevi e solitamente non hanno infrastruttura o ne hanno una molto

semplice. Il gruppo di lavoro 802.15 della IEEE si preoccupa di definire gli standard per

questa tipologia di reti senza fili e, in particolare, lo standard 802.15.4 è focalizzato su LR-

WPAN – Low-Rate WPAN.

Lo standard ISO/OSI prevede che una rete sia organizzata nei sette livelli riportati

alla tabella 3.1.

7 Applicazione

6 Presentazione

5 Sessione

4 Trasporto

3 Rete

LLC 2 Data Link

MAC

1 Fisico Tabella 3.1 – Livelli dello standard ISO/OSI.

Il livello fisico si occupa della gestione del mezzo trasmissivo su cui avviene lo

scambio di informazioni tra due entità; esso si occupa, quindi, della ricezione e della

trasmissione dei singoli bit come un flusso di dati non strutturati.

Il livello data link, invece, deve consentire il trasferimento affidabile dei dati

attraverso il livello fisico. Invia frame di dati con la necessaria sincronizzazione ed effettua

un controllo degli errori e delle perdite di segnale. Ciò contribuisce a far apparire ai livelli

superiori lo strato fisico come una linea di comunicazione priva di errori di trasmissione. Il

data link layer si suddivide in due sottolivelli. Il sottolivello LLC – Logical Link Control –

è quello superiore, dunque comunica con il livello 3, e può fornire servizi di controllo di

flusso, conferma, rilevazione o correzione degli errori. Il sottolivello inferiore, ovvero


43

quello che comunica con il livello fisico, è il MAC – Media Access Control – e determina

chi può utilizzare il mezzo trasmissivo in un determinato momento. Inoltre definisce la

struttura dei pacchetti per determinarne inizio e fine.

La topologia della rete è fornita dal livello rete, che non fa parte dello standard

802.15.4. Le topologie supportate sono quella a stella e quella peer-to-peer.

Nella topologia a stella la comunicazione ha luogo tra vari device ed un controllore

centrale, detto coordinatore; ogni nodo può stabilire la sua rete e diventarne il coordinatore.

Ogni elemento della rete ha un indirizzo di 64 bit.

La topologia peer-to-peer ha comunque un coordinatore di rete ma differisce dalla

precedente in quanto ogni nodo può comunicare con ogni altro nodo nel suo raggio

d’azione. Questa modalità consente di creare reti più complesse come, ad esempio, quelle a

maglia o multi-hop. Applicazioni di controllo industriale, monitoraggio, WSN,

posizionamento tendono ad utilizzare questa topologia, che aumenta il consumo di energia

ma migliora affidabilità e scalabilità.

Si noti come nella rete siano presenti dispositivi, i FFD – Full Function Device –

con funzionalità maggiori rispetto ad altri, RFD – Reduced Function Device.

Figura 3.1 – Topologia a stella e topologia peer-to-peer di una rete PAN.


44

Il documento IEEE 802.15.4-2003 definisce il livello fisico (PHY) ed il sotto-livello

medium access control (MAC) per reti wireless personali a bassissima complessità,

bassissimo costo e bassissimo consumo di energia.3

Il livello fisico – PHY – fornisce due servizi, detti data service e management

service. Il data service abilita la trasmissione e la ricezione di PDU – Protocol Data Unit –

di livello fisico sul canale radio fisico. Il management service si occupa, invece,

dell’attivazione e disattivazione del trasmettitore radio, rilevamento dell’energia o ED –

Energy Detection, di fornire un’indicazione della qualità del canale o LQI – Link Quality

Indicator.

Lo standard offre due possibilità di livello fisico basate sulla banda di frequenza,

una ad alta frequenza, 2.4 GHz, con data rate di 250kbps, l’altra a bassa frequenza, o

915MHz a 40kbps o 868MHz a 20kbps.

PHY

(MHz)

Banda di

frequenza

(MHz)

Bit rate

(kbps) Canali

868-868.6 20 1 868/915

902-928 40 10

2450 2400-2483.5 250 16 Tabella 3.2 – Bande di frequenza e data rete.

È possibile rendere dinamica la selezione del canale in base a considerazioni su

Energy detection e qualità del canale.

La misura dell’ED consiste in una stima della potenza del segnale ricevuto su un

canale; non vengono effettuate operazioni per identificare o decodificare il segnale. L’ED

viene riportato come un intero su 8 bit, quindi un valore da 0 a 255, dove il minimo indica

che la potenza del segnale ricevuto è inferiore di 10dB alla sensibilità del ricevitore.

3 Il superlativo è utilizzato nel documento ufficiale [23].


45

Il LQI intende caratterizzare la potenza e/o la qualità di un pacchetto ricevuto. La

misurazione può quindi avvenire attraverso una misura dell’ED e della stima del rumore

presente nel segnale. Anche in questo caso si tratta di un intero su 8 bit, quindi un valore da

0 a 255.

Il PDU del livello fisico è costituito da:

� SHR, che consente al ricevitore di sincronizzarsi con il flusso di bit;

� PHR, che contiene informazioni sulla lunghezza del frame;

� un payload di dimensione variabile che contiene il frame del sottolivello

MAC.

byte 4 1 1 Variabile

Preambolo SFD Lunghezza

del frame riservato PSDU

SHR PHR PHY payload Figura 3.2 – PDU del livello fisico in 802.15.4.

Anche il sottolivello MAC fornisce due servizi, uno per i dati ed uno per la gestione.

Il data service abilita trasmissione e ricezione dei PDU di livello MAC attraverso il PHY

data service. Il management service si occupa invece dell’accesso al canale, della

validazione dei frame, del corretto inoltro e di fornire meccanismi di sicurezza.

Lo standard consente al coordinatore della rete di definire un superframe da

utilizzare per la sincronizzazione tra i device della rete e per identificare la rete stessa. Il

superframe può avere una porzione attiva ed una inattiva. Nella porzione inattiva, il

coordinatore non interagisce con la PAN e può portarsi in uno stato a basso consumo. La

porzione attiva è divisa in slot di egual durata e si compone di tre parti, beacon, CAP e CFP.

La parte beacon4 viene trasmessa all’inizio dello slot 0 senza l’utilizzo del CSMA; la parte

di contention access period – CAP – ha una durata minima e i dispositivi che intendono

comunicare in questo periodo devono competere con gli altri elementi costituenti la rete per

4 In questo contesto il termine beacon non è utilizzato nel senso visto per gli algoritmi di localizzazione in WSN; si tratta di messaggi particolari utilizzati per effettuare delle operazioni di sincronizzazione.


46

ottenere l’accesso al canale, per cui occorre prevedere un meccanismo di accesso; nel corso

del contention free period – CFP – vengono garantiti degli slot temporali liberi, GTS.

Il CSMA-CA – Carrier Sense Multiple Access with Collision Avoidance – viene

utilizzato per evitare collisioni sul canale. Quando un device vuole utilizzare un canale,

verifica se questo è libero; in caso affermativo comunica alle altre stazioni la sua intenzione

di trasmettere, aspetta un tempo casuale e se trova il canale ancora libero avvia la

trasmissione. Quando il canale è trovato occupato, invece, la stazione aspetta un tempo

casuale, detto tempo di backoff, prima di riprovare l’accesso. Se i periodi di backoff sono

allineati agli slot del superframe si parla di slotted CSMA-CA, altrimenti di unslotted

CSMA-CA. Quindi nel caso unslotted i periodi di backoff di un dispositivo non sono

sincronizzati con quelli di un altro dispositivo.

Un altro meccanismo fornito per la robustezza della trasmissione dei dati è quello di

acknowledgement dei frame, il quale consente di avere riscontro della ricezione e della

validazione dei dati.

Vengono utilizzati poi meccanismi di data verification, quali frame check sequence

e cyclic redundancy check.

Il trasferimento dei dati può avvenire da un coordinatore ad un dispositivo, da un

dispositivo ad un coordinatore e tra due dispositivi di pari livello.

Se un dispositivo intende effettuare un trasferimento verso un coordinatore in una

rete che non prevede l’utilizzo di beacon, esso semplicemente trasmette il frame utilizzando

unslotted CSMA-CA al coordinatore; opzionalmente, può essere previsto un meccanismo di

riscontro con acknowledgement. Se invece la rete richiede l’uso di beacon, il dispositivo

1 2 3 4 5 6 7 8 9 10 11 12 13 14 150

BEACON

CAP CFP

GTS GTS Inattivo

BEACON

Figura 3.3 – Esempio di struttura del superframe.


47

ascolta il canale per rilevarne la presenza, quando lo trova lo usa per sincronizzarsi al

superframe. Quindi, utilizzando lo slotted CSMA-CA, trasmette il frame al coordinatore.

Anche in tal caso può essere previsto un meccanismo di riscontro.

Si osserva quindi che il trasferimento viene gestito dai dispositivi della rete

personale piuttosto che dal coordinatore così da ridurne il consumo energetico.

Se è il coordinatore a voler inviare dati ad un device, nel caso di rete con beacon

abilitati, il coordinatore indica nei suoi messaggi beacon l’intenzione di trasmettere; il

dispositivo che periodicamente ascolta il canale per rilevare i beacon determina la presenza

di un messaggio in attesa e, utilizzando lo slotted CSMA-CA, lo richiede. Anche il

coordinatore usa slotted CSMA-CA per inviare il messaggio. Ricevuto un messaggio di ack

dal ricevente il messaggio viene elimintao dalla lista degli uscenti.

Se invece la rete non è beacon-enabled, il coordinatore memorizza i dati per il

dispositivo che deve riceverli e attende di ricevere la richiesta da questo. Il dispositivo usa

comandi MAC per richiedere i dati, usando unslotted CSMA-CA. il coordinatore invia un

ack e quindi i dati.

In una rete peer-to-peer ogni dispositivo può comunicare con ogni altro dispositivo

nel suo raggio di trasmissione. Ciò può essere realizzato in due modi. Nel primo, un nodo

ascolta costantemente il canale per trasmettere utilizzando unslotted CSMA-CA; nel

secondo il nodo si sincronizza con tutti gli altri così da ridurre il consumo energetico.

La generazione di una PAN può essere avviata solo da un FFD che ha rilevato un

canale attivo. Quindi occorre una funzione di scan che consenta ad un FFD di individuare

un coordinatore che trasmette beacon nel suo raggio d’azione, POS – Personal Operating

Space. Occorre poi prevedere una procedura di associazione che includa l’invio di una

richiesta di associazione al coordinatore di una PAN.

La frame del sottolivello MAC è costituita da:

� MHR, che include il controllo del frame, numero di sequenza e informazioni

sugli indirizzi;

� payload di dimensione variabile, il quale contiene informazioni specifiche

sul tipo di frame; nel caso di frame di acknowledge non c’è payload;


48

� MFR che contiene il FCS – Frame Check Sequence – per il controllo del

frame.

byte 2 1 0/2 0/2/8 0/2 0/2/8 Variable 2

Destination

PAN

identifier

Destination

address

Source

PAN

identifier

Source

address Frame

control

Sequence

number

Campi di indirizzamento

Frame

payload FCS

MHR MAC

payload MFR

Figura 3.4 – Frame generico del sottolivello MAC in 802.15.4.

ZigBee è una specifica della ZigBee Alliance derivata dallo standard 802.15.4, come

il Bluetooth; infatti, similmente a questo, opera alle frequenze radio ISM, ma ha come

scopo quello di ottenere consumi energetici inferiori, di essere più semplice, più economica

e più scalabile.

Tale specifica ha un range di funzionamento dai 10 ai 75 metri, con dispositivi che

superano anche i 300 metri in ambiente oudoor, mentre Bluetooth funziona intorno ai 10

metri. ZigBee risponde ai datarate visti in tabella 3.2 mentre Bluetooth arriva fino a 1 Mbps.

Inoltre, mentre ZigBee consente di creare reti con molti nodi in configurazioni master-slave,

il protocollo Bluetooth supporta delle reti di piccole reti non sincronizzate dette piconet.

Infine, un dispositivo ZigBee diventa attivo alla ricezione di un pacchetto in circa 15

millisecondi mentre un dispositivo Bluetooth richiede circa 3 secondi.

I dispositivi Iris Mote che utilizzeremo lavorano nella banda di 2450 MHz con

canali da 11 a 26 definiti come: Fc = 2405 + 5 (k – 11) MHz, k = 11, 12, …, 26 dove k è il

numero del canale.

ZigBee utilizza pacchetti di dimensione massima 128 byte, di cui 104 per il payload;

gli indirizzi possono essere nel formato a 64bit o nel formato breve a 16 bit, per reti fino a

65536 nodi.


49

Per migliorare le prestazioni dal punto di vista energetico, a livello fisico di ZigBee

è possibile distinguere due modalità di funzionamento, Active e Sleep, sia per la CPU che

per il modulo radio. In tal modo è possibile disabilitare l’hardware inutilizzato risparmiando

in termini di consumo di batteria, per poi riabilitarli al momento opportuno.

Fondamentalmente si tratta di una messa in opera di quanto stabilito in 802.15.4 e, quindi,

le operazioni di connessione alla rete, accesso al canale, topologia della rete, sono quelle

viste precedentemente.

ZigBee utilizza come algoritmi di routing AODV – Ad hoc On Demand Distance

Vector – e Cluster Tree.

AODV è un algoritmo di routing on-demand puro, infatti i nodi che non

appartengono ad un percorso attivo non mantengono nessuna informazione di routing né

partecipano ad uno scambio periodico di tabelle di routing. Obiettivo principale

dell’algoritmo è la riduzione dei messaggi da inoltrare per la scoperta della rete.

Se un nodo sorgente deve comunicare con un altro nodo della rete di cui non ha

alcuna informazione, avvia un processo di Path Discovery. Il nodo sorgente invia in

broadcast una richiesta di percorso, RREQ, ai vicini, nella quale include indirizzo sorgente,

broadcast id, numero di sequenza, indirizzo destinazione, contatore di passi. Il broadcast id

è un contatore relativo ad un nodo incrementato ogni qual volta questo effettui una RREQ.

Un nodo che riceve la richiesta incrementa il contatore dei passi e la reinoltra ai suoi vicini.

Quando la richiesta giunge a un nodo che ha un percorso verso la destinazione per prima

cosa controlla di aver ricevuto la richiesta su un canale bidirezionale, quindi inoltra un

messaggio unicast di risposta, RREP, al vicino da cui ha ricevuto la richiesta così, passo

passo, si ricostruisce a ritroso il percorso tra trasmettitore e ricevitore.

Cluster Tree è un protocollo della Motorola utilizzato per creare reti cluster o grosse

reti ad albero.

Il processo di creazione di un cluster comincia con la scelta di un capo. Un nodo

scansiona i canali in cerca di un messaggio HELLO, corrispondente al messaggio beacon

dell’802.15.4; se non ne rileva alcuno in un certo intervallo di tempo si autoelegge capo di

un cluster, invia messaggi HELLO e si mette in attesa di risposte. Se tutti i nodi sono nel


50

range dell’ head del cluster, CH, la rete ha una topologia a stella e ogni nodo raggiunge

l’head con un solo salto. Un cluster può essere espanso in una struttura multi-hop quando

ogni nodo supporta connessioni multiple.

Se un particolare device assegna un cluster id ad ogni CH, che con l’id del capo

forma un indirizzo logico da utilizzare in fase di routing, si crea una rete Multi-Cluster.

3.2 nesC

nesC è un dialetto del C, come definito da uno dei suoi progettisti, David Gay,

creato specificamente per sensori. Per certi versi si tratta di un’estensione del C in quanto

fornisce un modello ad eventi non previsto dal linguaggio base, ma ne perde le funzionalità

relative a puntatori e allocazione dinamica della memoria.

Un’applicazione nesC è un insieme di componenti collegati da interfacce, ognuna

delle quali modella un servizio offerto o utilizzato. In tal modo si ottiene un’astrazione dei

componenti il cui utilizzo è indipendente dall’implementazione. Un componente che

fornisce un’interfaccia deve implementarne i comandi, mentre il comportamento al

verificarsi degli eventi compete a chi li utilizza.

In fase di compilazione, comandi ed eventi vengono tradotti in normali chiamate a

funzione, ma l’astrazione delle interfacce rende la programmazione più agevole e favorisce

la portabilità delle applicazioni.

L’implementazione di un componente prevede un modulo ed una configurazione;

nel primo vengono specificate le interfacce utilizzate e fornite e vengono implementati gli

eventi delle prime e i comandi delle seconde. La configurazione, invece, specifica quali

componenti implementano le interfacce dichiarate nel modulo stabilendo i collegamenti – o

wiring – tra fornitori ed utilizzatori.

Il codice nesC può essere sia asincrono che sincrono. Comandi ed eventi

costituiscono codice asincrono, ovvero codice che può essere raggiunto da almeno un

gestore degli interrupt. nesC fornisce poi task e sezioni atomiche per introdurre codice

sincrono. Si tratta di una collezione di comandi che costituiscono una sequenza indivisibile,

ovvero la cui esecuzione non è interrompibile se non da codice asincrono, ovvero comandi


51

ed eventi, i quali hanno sempre la priorità. I task sono gestiti da uno scheduler con politica

FIFO.

Questo semplice meccanismo di concorrenza risulta sufficiente per applicazioni

incentrate sull’ I/O, ma diventa carente all’aumentare del carico per la CPU.

3.3 TinyOS

TinyOS è un sistema operativo free ed open source, scritto in nesC e nato dalla

collaborazione tra Università di Berkley, Intel Research e Crossbow Technology, con il fine

di creare un sistema operativo ottimizzato per ridurre i consumi di energia, ridurre il

sovraccarico computazionale, minimizzare le dimensioni del sistema operativo, supportare

le richieste di operazioni frequenti e concorrenti con un alto livello di robustezza ed

efficienza.

Tale sistema operativo differisce sostanzialmente da quelli tradizionali; innanzitutto

è sporovvisto di un kernel che gestisca le risorse disponibili per cui non consente

l’esecuzione di più applicazioni. Inoltre TinyOS si integra direttamente nel programma

sviluppato, che risulta dunque una collezione di componenti nesC a cui si aggiunge uno

scheduler che ha il compito di gestire l’esecuzione dei task e delle funzioni.

I componenti di TinyOS possono essere raggruppati in tre categorie:

� Astrazioni Hardware, ovvero i componenti che forniscono le interfacce per

accedere all’hardware di sistema; contribuisce alla portabilità del codice;

� Hardware simulato, costituito dai componenti che attraverso le loro interfacce

simulano le prestazioni di hardware più complesso di quello effettivamente

presente nella piattaforma in uso;

� Componenti di alto livello che forniscono le funzioni di elaborazione più

complesse prescindendo dal particolare hardware.

In figura 3.5 è riportata l’architettura di TinyOS. Come si può vedere si ha una

decomposizione in layer verticali ed orizzontali, dove il livello più alto è costituito dal

componente Main e il più basso dall’hardware.


52

Lo stack di comunicazione è basato sugli Active Message che rappresentano un

semplice paradigma per le comunicazioni basate sullo scambio di messaggi. Ogni AM

contiene un nome di un handler di livello utente che viene invocato sul nodo target all’arrivo

del messaggio, a cui viene passato come argomento il payload del messaggio. Gli handler

ricoprono un duplice ruolo: hanno la funzione di estrarre i messaggi dalla rete e allo stesso

tempo di inoltrarli per una possibile elaborazione, oppure semplicemente per inviare un

messaggio di risposta. Questo schema è rappresentato in figura 3.6. In questo modo la rete viene

modellata come una pipeline con un minimo di buffer per la memorizzazione dei messaggi.

Questo modello di invocazione degli handler basato sugli eventi semplifica la realizzazione del

codice in quanto:

� elimina molte difficoltà dovute all’implementazione di protocolli che prevedono

la gestione dei buffer di invio e ricezione;

� consente di evitare le attese quando è in arrivo un messaggio, permettendo al

Figura 3.5 – Architettura di TinyOS.


53

sistema di svolgere della azioni contemporaneamente all’invio e ricezione dei

dati.

3.4 Verso l’implementazione

Per l’implementazione viene scelto di utilizzare sensori Iris Mote, basati su

protocollo ZigBee, e la versione 2.1 di TinyOS, che presenta diversi miglioramenti e

aggiunte rispetto alle versioni precedenti, in particolare il supporto per la piattaforma Iris.

Quindi si è optato per le soluzioni più all’avanguardia, trattandosi in entrambi i casi

degli ultimi prodotti della Crossbow Technology.

Da quanto visto finora è chiaro che un’applicazione per reti di sensori non può avere

richieste esose di memoria, di capacità computazionali e di consumi energetici. Quindi la

realizzazione del codice che implementi il ROCRSSI+ richiede delle particolari

ottimizzazioni per rispondere a tali requisiti.

Figura 3.6 – Componenti dello strato comunicazione dell’architettura di TinyOS.


54

Prima di procedere all’implementazione sono stati effettuati test per la valutazione

dell’RSSI; tali test hanno mostrato che il valore rilevato non è sempre stabile, bensì possono

esserci dei casi in cui varia rapidamente. Ciò può essere dovuto a interferenze, a fenomeni

di riflessione sulle pareti o a ostacoli. In ogni caso, l’obiettivo è quello di ottenere un valore

di RSSI che sia il più possibile un corretto indicatore della distanza dei nodi per cui

occorrono degli opportuni accorgimenti affinchè ciò sia possibile.

Dall’analisi energetica del capitolo successivo vedremo che l’invio e la ricezione dei

messaggi sono operazioni particolarmente costose dal punto di vista del consumo di

batteria; quindi è necessario ottimizzare lo scambio di messaggi tra i beacon al fine di

contenere i consumi, essendo l’autonomia energetica uno dei principali requisiti delle reti di

sensori.

Date le ridotte capacità di memoria dei sensori sarà necessario ridurre al minimo la

quantità di dati che i sensori devono utilizzare per l’esecuzione del codice. Pertanto si

cercherà di ottimizzare l’utilizzo delle strutture dati utilizzando, laddove è possibile,

particolari tecniche di memorizzazione. È il caso della tecnica di memorizzazione packed

delle matrici, che vedremo al paragrafo 3.7. Inoltre sarà preferito l’utilizzo di accumulatori

al fine di evitare array e l’occupazione di memoria con informazioni superflue.

Al capitolo 1 è stata illustrata la necessita di utilizzare l’algoritmo di scansione della

griglia. Anche in tal caso occorrerà prestare particolare attenzione all’implementazione al

fine di evitare un eccessivo costo computazionale dovuto a cicli innestati per

l’aggiornamento dei contatori associati alle celle.

Di seguito vedremo la suddivisione dell’implmentazione tra nodi noti e nodi

incogniti per poi passare alla determinazione delle distanze tra i beacon e degli RSSI relativi

alle comunicazioni tra due nodi beacon e tra beacon e nodi incogniti. Si vedranno poi nel

dettaglio le ottimizzazioni relative alle strutture dati e l’algoritmo di grid-scan per poi

passare ai messaggi scambiati tra i mote per rendere possibile ai nodi incogniti la

localizzazione.


55

3.5 Nodi noti e nodi incogniti

Come specificato in fase di descrizione dell’algoritmo, ci sono nodi la cui posizione

è nota e nodi che devono localizzarsi attraverso il ROCRSSI. Nello specifico, l’algoritmo

ROCRSSI+ viene eseguito da un nodo incognito il quale necessita delle informazioni

necessarie all’esecuzione dello stesso. Per costruire gli insiemi SA1 e SA2, di cui alle righe 6

e 7 del codice, riportato per comodità alla pagina seguente, l’esecutore dell’algoritmo deve

conoscere i valori di RSSI relativi alla comunicazione tra i beacon e di questi con se stesso.

Considerando l’esempio in figura 3.8, dove S è il nodo incognito e A, B e C i nodi beacon,

occorre che siano noti i valori di RSSI tra A e B, A e C, B e C e di ogni beacon con il nodo

che deve localizzarsi. Naturalmente non è detto che ogni nodo veda tutti gli altri, comunque

è necessario conoscere tali informazioni rispetto ai nodi vicini, ovvero visibili al modulo

radio.


56

Figura 3.7 – Pseudocodice del ROCRSSI+.


57

Inoltre occorre conoscere i valori d1 e d2 delle righe 13 e 17, ovvero le distanze effettive tra i

beacon. Infine per costruire le regioni geometriche di cui alle righe 20, 25 e 29 occorre che

il nodo incognito conosca le posizioni dei beacon che utilizza per localizzarsi. È dunque

evidente che occorre definire uno scambio di messaggi tra nodi noti e nodi incogniti e tra gli

stessi beacon per comunicare tali informazioni e per rilevare i valori di RSSI e delle

strutture dati atte a contenere tali dati di rilievo.

3.6 Valutazione degli RSSI e delle distanze tra i beacon

Per conoscere la potenza del segnale attraverso la quale due mote comunicano è

necessario che tra questi avvenga uno scambio di messaggi. Dovendo valutare gli RSSI

relativi alla comunicazione tra beacon e nodo incognito e tra beacon e beacon, facciamo in

modo che ognuno di questi invii in broadcast dei messaggi vuoti, al solo scopo che il

ricevente possa valutare la potenza del segnale con cui ha ricevuto il messaggio e

comunicarlo al mittente.

event void SendTimer.fired(){

rmsg = (RssiMsg*)(call Packet.getPayload(&msg,

sizeof(RssiMsg)));

A

B

C

S

Figura 3.8 – Esempio di rete WSN. A, B, C sono beacon, S è

un nodo incognito.


58

if (call RssiMsgSend.send(AM_BROADCAST_ADDR, &msg,

sizeof(RssiMsg))==SUCCESS) call Leds.led2Toggle();

else call Leds.led1Toggle();

}

Inoltre, avendo osservato che i valori di RSSI rilevati in momenti diversi ma a parità

di distanza possono essere diversi, si opta per determinare il valore di potenza di un segnale

come la media degli RSSI ricevuti su un certo numero di pacchetti; tale numero dipende

soprattutto dalla stabilità dei valori nell’ambiente, quindi da eventuali fenomeni di

interferenza o riflessione del segnale e da eventuali ostacoli mobili, per cui occorre

determinarlo in fase di setup della rete. Come vedremo durante l’analisi, nel corso del

capitolo 4, tale fase ha molta importanza in quanto sono diversi i parametri da determinare

per l’inizializzazione della rete. Nel nostro caso è stato scelto di valutare l’RSSI sulla base

di 20 messaggi. Un nodo A invia ogni secondo un messaggio con payload vuoto in

broadcast, un nodo B lo riceve, determina il valore dell’RSSI e attende altri 19 messaggi

dallo stesso nodo; a tal punto il nodo B assegna un valore di RSSI relativo alla

comunicazione con il nodo A.

Poiché i nodi nella rete sono più di due occorre un meccanismo per evitare che un

nodo consideri sempre i messaggi di un solo trasmettitore, non valutando mai l’RSSI

relativo ad un altro canale di comunicazione. Viene quindi introdotto un array history che

ha memoria degli ultimi nodi considerati; un nodo che riceve un messaggio per la

valutazione della potenza verifica se il mittente di quel messaggio è presente nell’history. In

caso affermativo scarta il pacchetto e ne attende uno nuovo da un altro nodo, altrimenti

procede al calcolo dell’RSSI. L’array viene svuotato allo scadere di un timer la cui durata

può variare in base all’applicazione specifica. Se id è una variabile inizializzata a 0 e idtemp

l’identificativo del mittente del messaggio appena ricevuto, si ha:

if ((id == 0 || idtemp==id) && (idtemp!=hist[0] &&

idtemp!=hist[1] && idtemp!=hist[2]) ) {

id=idtemp;

[…]


59

event void ResetHistTimer.fired(){

hist[0]=0; hist[1]=0; hist[2]=0;

}

In realtà, per ridurre lo scambio di messaggi, i pacchetti inviati dai beacon per la

valutazione dell’RSSI contengono anche le coordinate del nodo. In tal modo sia gli altri

nodi noti che i nodi incogniti ottengono le informazioni relative alla posizione del beacon

mittente. Ciò consente di ridurre il consumo di batteria, fortemente influenzato dall’invio di

messaggi.

I beacon che ricevono le coordinate di un altro nodo noto possono valutare la

distanza tra se stessi ed il mittente del pacchetto. In tal modo vengono evitati per ogni

beacon almeno gli n-1 messaggi indirizzati a ciascuno degli altri nodi noti della rete, se

questa è formata da n mote con posizione nota; inoltre anche ai nodi incogniti, come detto,

occorre conoscere le coordinate di ciascun beacon. Date le coordinate di due nodi sulla

griglia, (x1, y1) e (x2, y2), la distanza è valutata come:

3.6.1 Simmetria del canale e dei valori di RSSI

Per ridurre la quantità di spazio necessaria alla memorizzazione dei valori di RSSI

tra i beacon, i canali di comunicazione saranno considerati simmetrici. In realtà, non

necessariamente il valore valutato dal mote A relativo alla comunicazione con B è lo stesso

che B valuta relativamente alla comunicazione con A, quindi è necessario che i due nodi si

accordino su un valore comune.

Poiché quando un nodo determina la potenza del segnale con cui comunica con un

altro nodo invia questa informazione in broadcast affinchè anche gli altri nodi possano

conoscerla, anche l’altro sensore conoscerà tale informazione e sceglierà di aggiornare il

valore al massimo tra quello che aveva in memoria e quello appena ricevuto. Tale scelta è

stata fatta considerando che, mentre un valore basso può essere legato ad un ostacolo,

magari temporaneo, un valore alto rispecchia maggiormente la potenza di comunicazione

( ) 221

221 )( yyxx −+−


60

relativa a due beacon. Se in certe circostanze il valore dell’RSSI è stato valutato pari a 18 ed

in altre pari a 12, senza che i nodi fossero effettivamente spostati, il valore più alto

rappresenta con maggiore probabilità la potenza con cui i mote in questione sono in grado

di comunicare. Dunque, se il nodo A della figura 3.8 rileva un RSSI relativo alla

comunicazione con B pari a 16, mentre B aveva valutato tale valore essere pari a 15, B

aggiornerà l’informazione a sua disposizione.

Inoltre, fenomeni di interferenza possono causare dei valori di RSSI non

corrispondenti al vero e che in fase di valutazione della media potrebbero far si che la

quantità considerata non sia attendibile. Sulla base delle considerazioni fatte in precedenza,

i valori maggiori sono considerati più attendibili per cui nella media gli viene dato maggior

peso nel caso in cui la varianza sia alta.

Tuttavia, date le ridotte capacità di memoria dei sensori, occorre evitare l’utilizzo di

grosse strutture dati, preferendo accumulatori e variabili opportunamente aggiornate.

Innanzitutto valutiamo la deviazione standard attraverso la somma dei quadrati dei

valori, così da evitare l’utilizzo di un array che memorizzi tutti i valori di RSSI. Inoltre, si

ha memoria solo del massimo e del minimo valore di RSSI relativi ad un canale di

comunicazione. Se la deviazione standard, ds, è abbastanza grande, e maggiore di un certo

valore, val, viene effettuata una correzione dell’RSSI medio dando maggior peso ai valori

più grandi, rappresentati dal massimo rilevato, piuttosto che dai valori più piccoli,

rappresentati dal minimo valore rilevato:

rssitemp=getRssi(msg);

counter++;

rssi_medio = rssi_medio+rssitemp;

if (rssitemp<min) min = rssitemp;

if (rssitemp>max) max = rssitemp;

sumq = sumq + (rssitemp*rssitemp);

if (counter>=20){

rssi_medio=rssi_medio/counter;


61

ds= sumq/20-(rssi_medio*rssi_medio) ;

if(ds>=val) {

var1=(rssi_medio-min)*0.15;

var2=(max-rssi_medio)*0.25;

rssi_medio=rssi_medio+var1+var2;

}

[…]

3.7 Strutture dati

Affinchè i vari mote possano scambiarsi le informazioni relative ad RSSI,

coordinate e distanze e per poter memorizzare tali dati, occorre definire delle strutture dati

atte a contenere tali informazioni.

Ogni nodo incognito deve conoscere l’RSSI relativo alla comunicazione con ogni

nodo beacon visibile e le coordinate di quest’ultimo. Definiamo dunque una struttura

BeaTable che contiene questi dati. Considerando una rete con massimo 5 nodi noti, tale

tabella è fatta come segue:

Tabella 3.3 – BeaTable.

dove gli ri indicano i valori di RSSI tra il nodo in questione ed il nodo i e (xi, yi) sono le

coordinate di quest’ultimo.

Per quanto riguarda le informazioni relative ai beacon invece, occorre che ognuno di

questi conosca l’RSSI con cui comunica con ciascun altro beacon e la distanza. Viste le

correzioni di cui sopra per far sì che due beacon abbiano la stessa informazione relativa

all’RSSI tra loro, e supponendo che la distanza da un generico nodo A al nodo B è uguale

alla distanza da B ad A, non è necessario che il nodo incognito riceva ed utilizzi una

struttura con dati relativi a tutte le combinazioni tra i beacon. Se la rete ha n beacon, una

1 2 3 4 5

RSSI r1 r2 r3 r4 r5

coord (x1; y1) (x2; y2) (x3; y3) (x4; y4) (x5; y5)


62

struttura con n x n RSSI e n x n distanze, e quindi dimensione 2n2, risulta superflua. Invece,

data la simmetria, è possibile considerare solo la matrice triangola re superiore.

1 2 … N

1

2

…

n

Tabella 3.4 – Matrice beacon-beacon.

Per capire il risparmio di memoria che si ottiene, si supponga di avere 6 beacon;

occorre una matrice in cui ogni elemento è una struct di due campi da 2 byte, ovvero

distanza e RSSI. Quindi si avrebbero 36 elementi ognuno di 4 byte e quindi 144 byte;

poichè la matrice è triangolare simmetrica, è possibile considerare la triangolare superiore e

memorizzarla in versione packed con due vettori, ognuno di 15 elementi, ogni elemento di 2

byte, quindi 2x15x2=60 byte, il che significa un risparmio di memoria del 58.3%.

In generale le dimensioni della tabella sono nxn, il vettore invece ha dimensioni pari

a (n-1 + n-2 + … + 1) = ( )

2

1−× nn, quindi, avendo n elementi sulla diagonale principale,

significa che il risparmio di spazio è dato da ( )

nnn

+−×

2

1, e quindi in percentuale

+⋅=

nrisp

1150%_ , il che significa un risparmio di spazio sempre superiore al 50%.

Faremo riferimento a tale struttura come BeaVector.

Naturalmente occorre prestare attenzione agli indici del vettore per capire ogni

elemento a quale coppia di beacon è relativa. Considerando la tabella 3.5, si può vedere che,

ad esempio, il terzo elemento è relativo alla coppia 1-4, quindi se intende conoscere la


63

distanza del nodo 4 dal nodo 1 occorre individuare tale elemento del vettore; similmente per

conoscere l’RSSI relativo alla comunicazione tra il nodo 2 ed il nodo 5 occorre fare

riferimento al settimo elemento.

1-2 1-3 1-4 1-5 2-3 2-4 2-5 3-4 3-5 4-5

RSSI 12 X 13 10 X 10 9 X X 12

dist 6.3 X 8.2 8.6 X 10.8 9.1 X X 3.2 Tabella 3.5 – Esempio di BeaVector.

3.8 Aggiornamento della griglia

L’algoritmo ROCRSSI+, così come l’algoritmo originale, considera i mote come

disposti su una griglia le cui celle hanno un valore che viene aggiornato ad ogni iterazione

dell’algoritmo; il numero di iterazioni è uguale al numero dei beacon. In particolare, come

si può vedere dalle righe 20, 25 e 29 dello pseudocodice, riportato in figura 3.7, vengono

considerate delle celle che corrispondono ad una corona circolare, ad un cerchio, alla

regione esterna ad una circonferenza, rispettivamente.

Innanzitutto osserviamo che un cerchio non copre per intero tutte le celle della

griglia con cui si interseca; lo stesso vale per l’intersezione con l’esterno di una

circonferenza e con la corona circolare. Quindi, si stabilisce che affinchè il valore di una

cella venga incrementato, questa deve avere un’intersezione con la regione di piano

determinata dall’algoritmo uguale o maggiore alla metà dell’area della cella stessa.


64

Nel caso riportato in figura 3.9, nel quale le celle da aggiornare sono quelle interne

al cerchio centrato sulla cella contrassegnata con X e con raggio 3, il valore associato alle

celle rosse, sebbene queste abbiano un’intersezione non nulla con il cerchio in questione,

non sarà incrementato, in quanto tale intersezione non è sufficientemente grande da ritenere

la cella interna al cerchio. Considerazioni simili vengono fatte per l’esterno di una

circonferenza e per una corona circolare, come mostrato nelle figure 3.10a e 3.10b.

Figura 3.9 – Aggiornamento valore associato alle celle interne ad un cerchio.

X


65

Per effettuare tale operazione, dopo aver determinato i raggi d1 e d2, si incrementano

i valori di questi di 0.5 unità5, dopodichè si determina quali sono le celle della griglia che

rispettano una disequazione ottenuta a partire dall’equazione della circonferenza; in un

sistema di assi cartesiani XoY, la circonferenza di centro (x1, y1) e raggio r, ha equazione:

Considerando le righe 19-23 dello pseudocodice dell’algoritmo di figura 3.7,

supponendo che le coordinate di un nodo indichino il centro della cella e che il beacon A

che si sta considerando nell’iterazione abbia coordinate (x1, y1), la generica cella (t, z)

appartiene alla corona circolare di raggio interno d1 e raggio esterno d2, se sono soddisfatte

le diseguaglianze:

Similmente, nel caso delle righe 24-27 dello pseudocodice, le celle che sono

interne alla circonferenza di raggio d2 centrata sul beacon A soddisfano la diseguaglianza:

Infine, con riferimento alle righe 28-31 dello pseudocodice, le celle esterne alla

circonferenza centrata in A e raggio d1, rispettano la diseguaglianza :

5 Poiché i valori di d1 e d2 sono relativi a distanze su un piano cartesiano, tali valori sono adimensionali.

X

Figura 3.10 – Regione della griglia esterna ad una circonferenza (a) e regione descritta da una corona

circolare (b).

X

( ) ( ) 221

21 ryyxx =−+−

( ) ( )

( ) ( ) 22

22

21

21

22

21

)5.0(

)5.0(

+<−+−

+>−+−

dyzxt

dyzxt

( ) ( ) 22

22

21 )5.0( +<−+− dyzxt


66

Se d1 e d2 sono i valori determinati dall’algoritmo come alle righe 13 e 17 dello

pseudocodice di figura 3.7 e grid è la matrice che rappresenta la griglia, si ha:

if (d1!=0 && d2!=0){

rad1=d1+0.5f;

rad2=d2+0.5f;

for (q=0; q<NUMR; q++) {

for (w=0; w<NUMC; w++){

if ( ( ((q-y)*(q-y) + (w-x)*(w-x)) > (rad1*rad1) )

&& ( ((q-y)*(q-y) + (w-x)*(w-x)) < (rad2*rad2) ))

grid[q][w] = grid[q][w]+1;

}

}

}

if (d1==0 && d2!=0){

rad2=d2+0.5f;



if( ( ((q-y)*(q-y) + (w-x)*(w-x)) < (rad2*rad2) ) )


}

}

}

if (d2==0 && d1!=0){

rad1=d1+0.5f;



if( ( ((q-y)*(q-y) + (w-x)*(w-x)) > (rad1*rad1) ) )


}

}

}

3.9 Messaggi scambiati tra i mote

Come detto, sono diversi i messaggi che i mote devono scambiarsi affinchè un nodo

incognito abbia a disposizione tutti i dati necessari all’esecuzione dell’algoritmo e, quindi

alla localizzazione. Di seguito vengono mostrati nel dettaglio.

( ) ( ) 21

22

21 )5.0( +>−+− dyzxt


67

3.9.1 RssiMsg

Si tratta del messaggio inviato in broadcast da ogni altro nodo per valutare l’RSSI

relativo alle varie comunicazioni tra i nodi, sia tra beacon e beacon che tra beacon e nodi

incogniti.

Nel caso dei beacon il messaggio contiene anche le coordinate del nodo mittente.

Mittente Destinatario Campo 1

A (beacon o

incognito)

B (beacon o

incognito)

Coordinate di A (solo se

A è beacon) Tabella 3.6 – RssiMsg.

3.9.2 BeaMsg

Questo messaggio viene inviato da un nodo beacon quando, dopo aver ricevuto un

certo numero di messaggi da un nodo incognito, ha determinato l’RSSI che caratterizza la

sua comunicazione con questo stesso nodo. Il messaggio viene inviato al nodo relativo alla

comunicazione della quale si è valutata la potenza e contiene il valore medio di RSSI

calcolato e le coordinate del nodo noto che ha calcolato il valore di RSSI, valori questi che

andranno a popolare la BeaTable.

Nel caso particolare, se il nodo A ha ricevuto 20 messaggi dal nodo incognito B,

attraverso i quali ha rilevato un certo RSSI medio, il messaggio sarà:

Mittente Destinatario Campo 1 Campo 2

A (beacon) B (incognito) RSSI medio relativo alla

comunicazione tra A e B

Coordinate di

A Tabella 3.7 – BeaMsg.

3.9.3 BeaVecMsg

Questo messaggio viene inviato da un beacon in broadcast per tutti i nodi incogniti e

contiene la BeaVector di cui al paragrafo 3.7.


68

Mittente Destinatario Campi 1..n6

A (beacon) Tutti i nodi incogniti

vicini BeaVector

Tabella 3.8 – BeaVecMsg.

3.9.4 PosMsg

Dopo aver ricevuto le informazioni necessarie all’esecuzione dell’algoritmo da tutti

i nodi vicini ed essersi localizzato, il nodo incognito invia questo messaggio contenente le

coordinate in cui ha stimato la sua posizione. Tale messaggio dovrebbe essere inviato alla

sola Base Station, in tale fase viene inviato in broadcast e contiene anche informazioni

aggiuntive utilizzate in fase di test quali, ad esempio, il valore di alcune celle della griglia.

Mittente Destinatario Campo 1 Campi 2..n

A (nodo

incognito) Broadcast

Coordinate calcolate

dall’algoritmo

Informazioni utilizzate in

fase di test Tabella 3.9 – PosMsg.

3.10 Struttura dei componenti realizzati

La figura 3.11 mostra la struttura dei componenti Beacon e Unknown relativi al

codice implementato per nodi noti e nodi incogniti. Ognuno è costituito da un componente

Main più un insieme di componenti per la gestione dei timer, dei messaggi in ingresso ed

uscita e dei led. Come si può vedere dai datasheet, i sensori Iris sono dotati di tre led di

colore diverso. Questi vengono utilizzati per ottenere un riscontro visivo dello stato dei

sensori in corso d’opera.

3.10.1 Beacon

In questo caso si può vedere il componente SendTimer utilizzato per l’invio dei

messaggi RssiMsg e collegato attraverso l’interfaccia Boot. Si intuisce dunque che non

6 Il valore di n dipende dalla dimensione della BeaVector. Per ulteriori dettagli si veda 3.6.


69

appena avviato il beacon comincia ad inviare mesaggi per la valutazione della potenza del

segnale nella comunicazione con gli altri nodi beacon. Il timer ResetHistTimer serve per

svuotare il buffer relativo ai nodi di cui sono stati già ricevutei messaggi per la valutazione

dell’RSSI.

Relativamente ai messaggi, i componenti RssiMsgSender e RssiMsgReceiver

servono, rispettivamente, all’invio ed alla ricezione dei messaggi per il calcolo dell’RSSI. Il

componente BeaVecMsgSender consente di inviare i messaggi contenenti il BeaVector ai

nodi incogniti, mentre BeaMsgSender consente al beacon di comunicare ad un nodo

incognito le proprie coordinate e l’RSSI relativo alla comunicazione tra loro, ovvero un

BeaMsg. I messaggi inviati sono utilizzati attraverso l’interfaccia AMSend mentre quelli in

ingresso attraverso l’interfaccia Receive.

3.10.2 Nodi incogniti

I nodi incogniti, o Unknown nodes, sono costituiti da un timer SendTimer, come

visto per i nodi beacon, per l’invio dei messaggi RssiMsg utilizzati dai nodi noti per la

valutazione dell’RSSI. Anche in questo caso il timer è avviato all’accensione del sensore.

Il componente RssiMsgSender consente di inviare i messaggi per la rilevazione

dell’RSSI. BeaMsgReceiver e BeaVecMsgReceiver sono invece i componenti per la

ricezione di BeaMsg e BeaVecMsg, rispettivamente. Infine PosMsgSender consente di

inviare il messaggio per la comunicazione della posizione stimata e di ulteriori altre

informazioni, ovvero il PosMsg. Come per il componente Beacon, l’invio avviene

attraverso l’interfaccia AMSend e la ricezione attraverso l’interfaccia Receive.


70

Figura 3.11 – Wiring dei componenti relativi a Beacon Node e Unknown Node.


71

3.11 Consistenza del ROCRSSI

Durante le operazioni di debug, è stata osservata un’inconsistenza relativa all’

algoritmo ROCRSSI, anche nelle versioni successive.

Un algoritmo per essere consistente deve restituire lo stesso risultato qualunque sia

l’ordine in cui si analizzano, e quindi utilizzano, i dati se tale ordine non comporta una

variazione qualitativa e quantitativa dell’informazione.

In particolare è stato osservato che cambiando l’ordine con cui l’algoritmo effettua i

confronti con i valori di RSSI relativi alle comunicazioni tra i beacon varia il risultato. Di

seguito un esempio per chiarire quanto affermato.

Si consideri di avere la situazione riportata in figura 3.12 con BeaVector e BeaTable

riportate alle tabelle 3.10 e 3.11, rispettivamente.

1-2 1-3 1-4 1-5 2-3 2-4 2-5 3-4 3-5 4-5

RSSI 9 7 X X 7 X X X X X

dist 1 2 X X 1 X X X X X Tabella 3.10 – Beavector.

3

2

1

RSSI=7dist=1

RSSI=7dist=2

RSSI=9dist=1

Figura 3.12 – Esempio di beacon appartenenti ad una rete. Il beacon uno ha una distanza dal nodo

beacon tre pari a 2 e comunica con un RSSI pari a 7; la comunicazione tra i beacon due e tre anche ha RSSI 7 ma i nodi distano 1.


72

1 2 3 4 5

RSSI 12 10 10 X X

coord (8; 6) (9; 6) (9; 8) X X Tabella 3.11 – Beatable.

Si supponga che il beacon 1 abbia coordinate (8; 6), il beacon 2 (9; 6) ed il beacon 3

(9; 8). Si ipotizzi, inoltre, che i beacon 1 e 2 distino 1 ed abbiano un RSSI pari a 9, 1

comunica con 3 con RSSI 7 e distano 2, 2 dista 1 da 3 e l’RSSI relativo a questi nodi è 7; si

consideri poi un nodo incognito che ha RSSI relativi ai beacon 1, 2 e 3 pari,

rispettivamente, a 12, 10 e 10.

Se l’esecuzione dell’algoritmo analizzasse i valori di RSSI relativi alle

comunicazioni tra beacon e nodo incognito nell’ordine 1-2-3, la prima iterazione

determinerebbe d1=0, d2=1, centro (8; 6), la seconda iterazione d1=0, d2=1, centro (9; 6), per

la terza iterazione si avrebbe d1=0, d2=2 e centro (9; 8). Analizzando i valori degli RSSI

nell’ordine 2-1-3, invece, la prima iterazione valuterebbe d1=0, d2=1, centro (9; 6), la

seconda iterazione d1=0, d2=1, centro (8; 6), la terza iterazione d1=0, d2=1 e centro (9; 8).

Come si può vedere dai risultati su esposti e dalle figure seguenti, mentre per le

prime due iterazioni si determinano le aree relative agli stessi cerchi, alla terza iterazione in

un caso viene determinata una circonferenza di raggio 2 e centro (9; 6), mentre nell’altro il

centro è lo stesso, essendo invariate le coordinate del nodo, ma il raggio è pari a 1; ciò è

dovuto al fatto che viene analizzato per prima il dato relativo alla comunicazione tra i

beacon 2 e 3 e poi quello relativo ad 1 e 3, ed essendo uguale il valore dell’RSSI, come

distanza viene considerata la prima individuata e, quindi il valore 1, mentre nel primo caso

il primo valore individuato era 2.


73

Per evitare tale fenomeno e, quindi, rendere consistente l’algoritmo, occorre fare in

modo che quando vengono individuati due valori uguali di RSSI, la distanza da considerare

non deve essere scelta a caso, ovvero in base all’ordine in cui sono stati scansionati i dati,

bensì occorre un criterio di scelta che assicura la stessa decisione qualunque sia l’ordine di

analisi dei dati.

Per uniformare le scelte dei valori da assegnare alle variabili d1 e/o d2, si opta per

assegnare il valore maggiore; con riferimento all’esempio precedete, dunque, a parità di

RSSI pari a 7, in entrambi i casi verrebbe scelto il valore di distanza pari a 2, ovvero max(1,

2).

Similmente a quanto visto al paragrafo 3.6 relativamente a valori diversi di RSSI a

parità di distanza, questa scelta è fondata sull’osservazione che, se per distanze differenti

abbiamo valori uguali di RSSI, consideriamo maggiormente attendibile quello ottenuto su

una distanza maggiore in quanto, se alle medesime condizioni è stato possibile ottenere un

valore di potenza del segnale ricevuto per una coppia di beacon, il fatto che un’altra coppia

determini lo stesso valore sebbene la distanza sia inferiore, induce a pensare che un ostacolo

possa aver causato una potenza inferiore del segnale rilevato. Considerando dunque un

Figura 3.13 a e b – Zone individuate dall’esecuzione dell’algoritmo nei due casi: a. scansiona i beacon

nell’ordine 1-2-3, b. scansiona i beacon nell’ordine 2-1-3.

3

1 2

3

1 2

3

1 2

3


74

impiego per il monitoraggio ambientale, il passaggio di un branco di animali nello spazio

tra due beacon può costituire un ostacolo che comporta un valore falsato dell’RSSI.

Di seguito lo pseudocodice modificato dell’algoritmo.

Figura 3.14 – Pseudocodice della versione consistente del ROCRSSI+.


75

Capitolo 4

Analisi dei risultati

Obiettivo di questo capitolo è quello di illustrare i risultati sperimentali ottenuti

dall’utilizzo dei sensori con il codice implementato.

Vengono quindi mostrati gli strumenti necessari alla realizzazione di tali

esperimenti, per poi passare all’organizzazione della campagna sperimentale e a definire

un’euristica per la valutazione dell’errore.

La sperimentazione avviene sia in ambiente indoor che outdoor, con rete di sensori

fully connected – laddove la potenza del segnale è sufficiente – e la disposizione dei beacon

può essere più o meno lontana dalle pareti, e random o allineata alla griglia; il numero dei

nodi beacon viene fatto variare da tre a cinque; si considera poi la variazione dell’errore al

variare della granularità della griglia. Infine, si mostra come variano il consumo di batteria

ed il tempo di localizzazione al variare del numero di nodi noti e del numero di messaggi

scambiati.

4.1 Strumenti

Per poter effettuare il debug del codice creato, compilarlo, installarlo sui sensori e

quindi testarlo per poi effettuare le sperimentazioni occorrono degli strumenti hardware e

software. L’hardware consiste nei sensori Iris Mote, in una programming board necessaria

per poter flashare il codice sui sensori e in una base station che rilevi i messaggi scambiati

tra essi; il software occorre per interfacciare l’hardware con il PC, per compilare il codice


76

ed installarlo sui sensori, per leggere i dati rilevati dalla base station.

È stato quindi utilizzato il pacchetto WSN PROFESSIONAL KIT della Crossbow

costituito da 7 mote, 6 sensor board, una programming board, una base station, una data

acquisition board ed un cd contenente driver, manuali e dei software di monitoraggio.

TinyOS e compilatore nesC.

Naturalmente per la creazione del codice, per il debugging e la compilazione è

necessario che sulla macchina di sviluppo utilizzata siano installati TinyOS ed un

compilatore nesC. Il sistema operativo TinyOS2.1, così come le sue versioni precedenti,

sono forniti solo per sistemi Linux, per cui in Windows è necessario l’utilizzo di Cygwin, il

quale consente, appunto, il porting di software per sistemi POSIX su sistemi Microsoft. I

dettagli relativi all’installazione sono riportati in appendice.

Iris Mote.

Si tratta di sensori della Crossbow basati su protocollo ZigBee e modulo radio a 2.4

GHz. È caratterizzato da un ampio raggio d’azione del modulo radio, fino a tre volte quello

dei precedenti Mica, e memoria doppia rispetto a questi. Sono dotati di un processore

XM2110CA basato sull’Atmel ATmega1281. È bene osservare che quello che normalmente

viene indicato come sensore è costituito in realtà dal modulo radio e dal processore, al più

con l’aggiunta del modulo per batterie, e prende il nome di mote board. I veri sensori invece

sono su un’ulteriore scheda che prende il nome di sensor board. Nel nostro developement

Figura 4.1 – Schermata di Cygwin mentre si eseguono istruzioni di TinyOS.


77

kit le mote board sono accompagnate da schede MTS400, le quali sono dotate di

accelerometro biassiale, sensore di pressione, sensore luminoso, sensori di umidità e

temperatura, e sono equipaggiabili con modulo GPS; in tal caso sono indicate come

MTS420.

Programming board.

Come detto, si tratta di un dispositivo utilizzato per flashare la ROM dei vari sensori

con il codice necessario all’esecuzione delle istruzioni. Nello specifico, si utilizza la

MIB520 della Crossbow.

In figura 4.3 sono evidenziati i connettori per il collegamento del sensore e la porta

USB per il collegamento ad un computer. In fase di installazione del dispositivo su una

macchina la connessione attraverso USB viene mappata come su una seriale, per cui viene

assegnato un numero di porta COM_X. Utilizzando Cygwin, TinyOS ed il compilatore

Figura 4.3 – Programming board Crossbow MIB520.

Figura 4.2 – Sensor board MTS420.


78

nesC, il codice implementato viene compilato e quindi installato sul sensore attraverso il

comando da riga di codice

make <platform> install,<mote_id> <programming_board>,<com>

dove <platform> indica la piattaforma utilizzata e quindi nel nostro caso iris,

<mote_id> è, invece, l’identificativo che si vuole assegnare al sensore, si tratta di un

intero da 0 a 65535, avendo visto che nella forma breve gli indirizzi della specifica 802.15.4

sono a 16 bit, <programming_board> è mib520, <com> indica l’identificativo della

seriale su cui è mappata la connessione USB dal sistema operativo. Supponendo dunque che

la programming board è sulla porta COM6 e di voler assegnare al mote l’id 44, si ha:

make iris install,44 mib520,com6

Base station.

In tale contesto la base station consiste in un dispositivo che riceve i dati sensibili

rilevati dai componenti della rete e li invia ad una macchina cui è collegato attraverso una

portaseriale.

Si tratta di un dispositivo costituito da una programming board con una mote board

collegata sulla quale è installato del codice per la rilevazione dei dati. Il codice può differire

a seconda di quali dati prendere e come prenderli. Nel nostro caso è stato utilizzato come

strumento software XSniffer della Crossbow il quale fornisce anche il codice da flashare sul

Figura 4.4 – Base station.


79

mote della base station; in tal modo saranno “sniffati” tutti i messaggi nel raggio d’azione

dell’antenna della base station, la quale li invierà alla seriale del PC cui è collegata, dove un

software ne consentirà la visualizzazione a schermo.

XSniffer.

Si tratta di un software realizzato dalla Crossbow e fornito con il Professional Kit.

Si compone di codice per mote e software per PC. Il mote rileva tutti i messaggi

scambiati in una rete di sensori su un determinato canale e li invia alla porta seriale. Il

software per PC rileva tutti i dati che giungono alla porta seriale specificata e li mostra a

video attraverso un’interfaccia user-friendly.

Si tratta di un utile strumento in quanto agevola notevolmente la fase di testing e la

fase sperimentale, consentendo di controllare le operazioni svolte dai sensori. Infatti,

programmando questi per l’invio di messaggi con dati rappresentativi del loro stato,

consente di verificare la correttezza delle operazioni che il mote sta eseguendo.

Figura 4.5 – Il software XSniffer mostra dei messaggi catturati.


80

Oracolo Java.

Per testare l’algoritmo è stato realizzato del codice in Java. In particolare, è stata

implementata una classe con metodi che prevedono in ingresso dati relativi ad RSSI e

coordinate per l’esecuzione dell’algoritmo. In tal modo, attraverso i dati riportati nella

BeaTable e nel BeaVector, ottenuti attraverso i messaggi inviati dai beacon e sniffati con

XSniffer, è stato possibile verificare che il contenuto del PosMsg inviato dai nodi incogniti

riportasse i dati attesi, ovvero le coordinate che effettivamente dovono essere calcolate con

quei dati in ingresso. I nodi incogniti sono stati programmati anche per l’invio di dati

contenenti informazioni circa i contatori della griglia al solo scopo di testare la corretta

esecuzione dell’algoritmo attraverso il codice nesC implementato.

4.2 Planning degli esperimenti

Per rilevare un campione significativo di dati da analizzare, occorre pianificare una

campagna sperimentale che consenta di verificare la qualità della localizzazione in varie

circostanze.

L’obiettivo è quello di osservare il comportamento del sistema sia in ambiente

indoor che outdoor. I primi esperimenti sono relativi ad un ambiente chiuso dove le pareti,

come si vedrà, comportano la riflessione del segnale, per cui è opportuno considerare

diverse configurazioni della rete, con i beacon disposti più o meno vicino alle pareti e la cui

disposizione può essere random o a griglia. Per disposizione a griglia si intende che i

beacon sono disposti in modo che linee immaginarie che li uniscono senza intersecarsi se

non nei vertici formino figure geometriche regolari, così da essere certi che la copertura

della griglia sia piuttosto regolare. Inoltre si intende verificare come varia l’errore al

crescere del numero dei beacon. Altro parametro che si intende far variare è la granularità

della griglia, ovvero considerare come varia la precisione della localizzazione con celle di

dimensioni variabili.

In ambiente outdoor saranno effettuate 9 misurazioni con 5 beacon disposti a griglia.

La tabella 4.1 riporta il planning degli esperimenti.


81

Disposizione beacon Nome

configurazione Esperimenti nella config

Ambiente # beacon Granularità

Parete Griglia

Interferenze

Configurazione 0 Da 1 a 7 indoor 3-4 fissa vicina no forti

Configurazione 1 Da T1 a T5 indoor 3-5 fissa vicina no medie o ridotte

Configurazione 2 Da T1 a T5 indoor 3-5 fissa lontana si medie o ridotte

Configurazione 3 Da T1 a T5 indoor 3-5 fissa vicina si medie o ridotte

Configurazione 4 Da T1 a T5 indoor 3-5 fissa lontana no medie o ridotte

Grid 83 G83 da 1 a 9 indoor 5 variabile X X medie o ridotte



Outdoor Da O1 a O9 outdoor 5 fissa X si ridotte o nulle Tabella 4.1 – Planning degli esperimenti.

Nome configurazione ed esperimenti nella configurazione vengono utilizzati per

identificare il particolare esperimento. Ambiente indica se si tratta di un ambiente indoor o

outdoor. Viene poi indicato il numero dei beacon utilizzati per gli esperimenti; come si vede

in alcuni casi è indicato un intervallo poiché la localizzazione avviene con un numero di

nodi noti che varia in un range. Granularità indica se le dimensioni delle celle della griglia

sono fisse o variabili; come si può vedere gli esperimenti G83, G41 e G10 riportano

“variabile”, infatti sono utilizzati valori rilevati agli esprimenti precedenti ma in cui si fa

rieseguire l’algoritmo all’oracolo con una dimensione delle celle diversa. Disposizione

beacon – parete e griglia indicano se i mote sono vicini o lontani alla parete e disposti a

grigla o random. Nel caso di esperimenti outdoor la vicinanza alle pareti non è considerata,

data l’assenza delle stesse; nel caso degli esperimenti con variazione della granularità tali

parametri non sono considerati in quanto non sono rilevanti al fine di studiare l’andamento

dell’errore; inoltre sono utilizzati dati rilevati in configurazioni diverse. La colonna

interferenze indica se nell’ambiente in cui sono stati effettuati gli esperimenti erano presenti

o meno interferenze dovute a dispositivi funzionanti in un intorno delle frequenze centrate

su 2.4 GHz; in altri termini si considera la potenza di segnali Wi-Fi rilevati. Forti indica, su

una scala da 1 a 5, segnali Wi-Fi a potenza 4 o 5, medie 2 o 3, ridotte 0 o 1.

4.3 Definizione dell’errore

In questa fase sperimentale si introduce una funzione errore che ci consente di


82

valutare con dati percentuali lo scostamento della posizione ottenuta dal nodo incognito che

si localizza dalla posizione reale, ovviamente nota in questa fase.

Tale scostamento viene calcolato come rapporto tra la distanza sulla griglia della posizione

originale dalla posizione stimata e distanza massima sulla griglia, la quale corrisponde,

come mostrato in figura 4.6, alla dimensione della diagonale della griglia, ovvero alla

distanza tra il punto di coordinate (1, 1) ed il punto di coordinate massime (n, m), se la

griglia ha m righe ed n colonne.

Considerando la griglia come un piano cartesiano, la distanza tra due punti (x1, y1) e

(x2, y2) viene valutata come:

Per effettuare tale operazione e già prima in fase di implementazione, è stato

1 2 3 4 5 6 7 8 9 10 11

1 X

2

3

4

5

6

7

8

9

10

11

12

13

14

15

12

X

( ) 221

221 )( yyxx −+−

Figura 4.6 – Griglia e distanza massima.


83

realizzato un’oracolo in Java, introdotto al paragrafo 4.1, che semplifica le operazioni di

testing e debugging. Si tratta di un programma che prende in ingresso le dimensioni della

griglia, BeaTable, BeaVector e la posizione reale del nodo incognito e restituisce la

posizione stimata dall’algoritmo ROCRSSI+ e l’errore percentuale come da noi definito.

Inoltre, come vedremo più avanti, tornerà utile per verificare i risultati che si possono

ottenere modificando i dati già a disposizione o aggiungendo ulteriori informazioni.

4.4 Rilevamento dati indoor

L’analisi principale è basata su 60 misurazioni effettuate in una location indoor ed

indicate come configurazione 1, 2, 3 e 4. Si tratta di una ambiente chiuso di dimensioni

497x622 centimetri che, come spiegato in fase di implementazione, è stato suddiviso come

una griglia; le dimensioni base sono di 41.5 cm e quindi 15 righe e 12 colonne, come

mostrato in figura 4.6. In seguito saranno fatte considerazioni anche con dimensioni delle

celle della griglia di 83 cm, 21.75 cm e 10.4 cm. Inoltre, si è cercato di ridurre al minimo le

interferenze legate a segnali WiFi.

Ulteriori esperimenti sono stati effettuati in laboratori con più WiFi in funzione, si

tratta della configurazione 0 della tabella 4.1.

Le rilevazioni delle configurazioni da 1 a 4 sono state effettuate considerando sia i

nodi beacon vicini alle pareti, ovvero con distanza inferiore ai 70 centimetri, che lontani,

ovvero con una distanza di almeno 100 cm da queste; inoltre si è considerata sia una

disposizione dei beacon allineati alla griglia, sia una disposizione random. Per ogni

posizionamento è stata effettuata la localizzazione con tre, quattro e cinque beacon e per

ogni configurazione sono stati effettuati cinque diversi posizionamenti; essendo quattro le

configurazioni considerate si sono ottenute le 60 rilevazioni su menzionate.

Vediamo i risultati delle singole configurazioni.

4.4.1 Configurazione 1: beacon vicini alle pareti in posizioni random

In figura 4.7 è mostrata la configurazione in esame. Le celle con sfondo grigio


84

indicano i beacon con id che vanno da 1 a 5; le celle con T1, T2, T3, T4 e T5 indicano la

posizione reale del nodo incognito per il quale viene effettuata la localizzazione con 3, 4 e 5

beacon.

Come si vede la maggior parte dei nodi noti sono vicini alle pareti – distanza minore

di 70 cm.

In questo caso si ottiene un errore medio pari al 19.81%7; date le dimensioni della

griglia, la diagonale dell’ambiente è pari a 796 centimetri, per cui il mote si localizza in un

punto distante 796x0.1981 = 157.69 centimetri da quello in cui realmente si trova.

4.4.2 Configurazione 2: beacon lontani dalle pareti allineati alla griglia

La figura 4.8 mostra la configurazione della griglia. In tal caso i nodi sono

7 Per questa e per tutte le altre configurazioni, la media viene calcolata come media troncata su quindici valori, cinque con tre beacon, cinque con quattro e cinque con cinque nodi beacon, come descritto precedentemente.

1 2 3 4 5 6 7 8 9 10 11

1 T1 2

2 3

3

4

5 T4 T2

6

7 4

8 T3

9

10

11

12 5

13 1

14

15 T5

12

Figura 4.7 – Griglia configurazione 1. le celle con sfondo grigio idicano la posizione dei beacon,

quelle con Ti la posizione reale del nodo incognito nel particolare esperimento eseguito con 3, 4 e 5

beacon.


85

distanziati dalle pareti di almeno 100 cm ed hanno una disposizione come il 5 di un dado,

così da coprire le zone periferiche, in prossimità dei vertici della griglia, e quella centrale.

In questo caso si ottiene un errore medio del 18.77% , pari a 149.41 centimetri.

Il grafico relativo all’andamento dell’RSSI al variare della distanza, riportato alla

figura 4.9, mostra come l’inversa proporzionalità tra i due valori sia rispettata con buona

approssimazione, da cui una localizzazione migliore che negli altri casi. I valori considerati

sono relativi alla comunicazione tra i nodi beacon ed alle distanze tra questi.

1 2 3 4 5 6 7 8 9 10 11

1

2

3 1 2

4 T3

5

6

7 T4 T2

8 3

9

10 T5

11 T1

12

13 4 5

14

15

12

Figura 4.8 – Griglia configurazione 2.


86

Figura 4.9 – Andamento RSSI rispetto alla distanza con dati della configurazione 2.

13,25

11,5

13,2512,25 12,75

10,25

12 11,5

9

10

0

2

4

6

8

10

12

14

5,8 5,8 6,4 6,4 7 7 10 10 12,2 12,2

distanza

RS

SI


87

4.4.3 Configurazione 3: beacon vicini alle pareti allineati alla griglia

Qui, come mostrato in figura 4.10, i beacon sono vicini alle pareti e disposti nei

quattro angoli, più il quinto beacon a metà di uno dei due lati maggiori. La distanza media

dalla parete è di circa 21 cm.

L’errore medio è pari al 24.74% che corrisponde a 196.93 centimetri.

È interessante notare come in questo caso, che risulta essere il peggiore, non è

rispettata l’inversa proporzionalità tra RSSI e distanza; il grafico RSSI-distanza, con

riferimento ai valori relativi ai beacon e quindi riportati in BeaVector, è riportato in figura

4.11.

1 2 3 4 5 6 7 8 9 10 11

1 1

2 T2

3

4

5

6 T5

7

8 T3 T1

9

10

11

12 T4

13

14

15 4

12

2

3

5



88

Figura 4.11 – Grafico RSSI-distanza relativo ai dati della configurazione 3.

8,8

7,2

7,2

7

10,29,6

9,8

9,8

9,29,4

0

2

4

6

8

10

12

7 7 11 11 13 13 14 14 17,8 17,8

distanza

RS

SI


89

4.4.4 Configurazione 4: beacon lontani dalle pareti in posizioni random

Ancora una distanza di almeno 100 cm dalle pareti, ma con disposizione casuale dei

nodi beacon. La configurazione è riportata in figura 4.12.

Si è ottenuto un errore medio del 21.99 %, ovvero 175.04 centimetri.

1 2 3 4 5 6 7 8 9 10 11

1

2 T2

3 2

4

5 1 T1

6

7

8 T3 3

9

10

11 T5

12 5

13 4

14

15

12

T4



90

4.5 Errore e configurazione

I risultati migliori sono stati ottenuti con la configurazione 2, ovvero con i beacon

lontani dalle pareti almeno un metro e disposti a griglia; in tal caso è stato ottenuto un

errore medio del 18.77% corrispondente a una distanza tra posizione calcolata

dall’algoritmo e posizione reale di 149.41 centimetri. Del resto la lontananza dalle pareti,

che consente quantomeno di attenuare fenomeni di riflessione del segnale, e la disposizione

a griglia, che garantisce una copertura uniforme dell’ambiente, facevano già presupporre

che tale configurazione avrebbe restituito i risultati migliori.

La configurazione peggiore invece è la terza, in cui i nodi beacon sono disposti a

griglia ma la distanza dalle pareti e di circa 21 cm. Probabilmente la vicinanza alle pareti ha

accentuato la riflessione del segnale su queste, rendendo i valori di RSSI meno attendibili,

ovvero valori che non rispettano l’inversa proporzionalità tra potenza del segnale ricevuto e

distanza.

La configurazione 1 restituisce risultati comunque migliori di quest’ultima con soli

due nodi beacon, 1 e 3, leggermente più lontani dalle pareti – 60 cm circa – ed il nodo 5

ancora più accentrato.

La figura 4.13 mostra l’errore per le quattro configurazioni considerate.

Figura 4.13 – Media troncata degli errori relativi alle quindici rilevazioni per ogni configurazione.

19,8118,77

24,74

21,99

0

5

10

15

20

25

1 2 3 4


91

Inoltre è interessante osservare come varia l’errore sia al variare della distanza

media dalla parete che con la distanza media tra i beacon.

Come si vede dalla figura 4.14 il caso migliore si ottiene in corrispondenza della

distanza massima dalle pareti, mentre il peggiore si ha quando la distanza media dalle pareti

è minima.

Si osservi poi che all’aumentare della distanza media da 62.1 cm a 128.2 cm si

verifica un aumento dell’errore che corrisponde, come rappresentato in figura 4.15, al caso

in cui la distanza media tra i beacon è minima e pari a 6.698. Tale valore è relativo alla

configurazione 4, per cui, sebbene i nodi noti siano sufficientemente distanti dalle pareti da

ridurre errori dovuti alla riflessione del segnale, la disposizione random e l’eccessiva

vicinanza non riescono a coprire la griglia in maniera uniforme.

8 In tal caso la distanza è valutata come distanza sul piano cartesiano, dunque non ha unità di misura.

Figura 4.14 – Relazione tra errore e distanza media dei beacon dalle pareti.

18,77

21,99

19,81

24,74

15

17

19

21

23

25

27

20,75 62,1 128,2 136,4

distanza pareti - cm

err

ore

- %


92

4.6 Errore e numero beacon

Si mostra ora come varia l’errore all’aumentare del numero dei beacon nel caso

della configurazione migliore, che si ritiene essere la più attendibile.

Come si può osservare dall figura 4.16, l’errore diminuisce al crescere del numero

dei beacon, quindi avere più nodi con posizione nota aiuta ad ottenere una localizzazione

migliore. Tale risultato è spiegabile osservando che al crescere del numero dei beacon

aumentano i dati a disposizione per poter stimare la posizione; poiché le distanze vengono

valutate dai nodi incogniti confrontando i valori di RSSI nella comunicazione con i nodi

noti con i valori RSSI relazionati alle distanze ottenuti attraverso la comunicazione tra i

beacon, avere cinque beacon piuttosto che tre significa avere più valori di distanza e relativa

potenza del segnale con cui confrontare gli RSSI con cui il nodo incognito comunica con i

beacon; dunque, semplicemente, avere più beacon significa avere più informazione.

Tuttavia bisogna osservare che mentre passando da tre a quattro beacon l’errore

diminuisce di 3.18 punti percentuali, non si ha un egual miglioramento nel passaggio da

Figura 4.15 – Relazione tra errore e distanza media tra i beacon.

18,77

21,99

24,74

19,81

15

17

19

21

23

25

27

12,56 9,76 6,69 8,28

distanza tra beacon

err

ore

- %


93

quattro a cinque nodi noti, dove la localizzazione migliora di 0.37 punti percentuali,

mostrando una andamento del tipo exp(-x), con una diminuzione rapida che sfocia in un

comportamento asintotico, il che non solo mostra un limite di performance dell’algoritmo,

ma indica l’importanza della scelta del numero di beacon da utilizzare, dato anche il trade-

off costi-prestazioni.

4.7 Errore e granularità

Come detto le sperimentazioni sono state effettuate con una griglia 12x15 con ogni

cella avente lato di 41.5 cm. Si vuole adesso vedere come varia l’errore al variare della

granularità della griglia, ovvero al crescere ed al diminuire del numero di celle e quindi

della dimensione della singola cella. A tal fine si utilizza l’oracolo variando ad hoc la

dimensione della griglia e le coordinate dei nodi.

I risultati sono riportati in figura 4.17.

Figura 4.16 – Variazione dell’errore medio al crescere del numero dei beacon.

17,23

20,78

17,6

15

16

17

18

19

20

21

22

3 4 5

# beacon

err

ore

- %


94

Possiamo osservare subito che aumentando la dimensione della cella l’errore

aumenta; infatti far diminuire il numero di celle implica una diminuzione della precisione.

Per contro, infittire la griglia non comporta un’aumento della precisione; infatti passando da

una dimensione della cella di 41.5 cm a 20.75 e poi a 10.4 cm, lascia quasi invariato

l’errore.

Anche in questo caso abbiamo un comportamento di tipo esponenziale, con

miglioramenti rapidi in una zona, seguiti da un comportamento asintotico. Per cui, come per

il numero dei beacon, la scelta della dimensione della cella è un parametro da determinare,

magari con l’uso di un oracolo, tenendo conto del trade-off precisione-costo

computazionale. Infatti avere più celle implica un aumento della complessità di calcolo,

essendo questa, nel caso del ROCRSSI, legata al numero di celle oltre che al numero dei

beacon.

4.8 Casi migliori e casi peggiori

Vogliamo osservare cosa accomuna i casi migliori, che consentono di ottenere un

errore inferiore al 10%, ed i peggiori, ovvero quelli con errore maggiore del 35%.

Figura 4.17 – Variazione dell’errore al crescere della dimensione della cella.

16,29

16,216,07

20,24

14

15

16

17

18

19

20

21

83 41,5 20,75 10,4

dim. cella - cm

err

ore

- %


95

L’errore minore, pari al 2.31% si ottiene nel caso T3 della configurazione 2; si nota

che il nodo incognito è in prossimità del limite della regione dei beacon9 e circa

equidistante da due nodi noti. La distanza minima dalle pareti è di 145 cm. Il caso T4 della

configurazione 4 è localizzato con un errore del 2.65%. Il nodo è esterno alla regione dei

beacon e dista 21 cm dalla parete. Il caso T5 della configurazione 4 presenta un errore del

5.54%; si tratta di un nodo che si trova tra due beacon e con una distanza dalla parete di 187

cm. Il caso T1 della configurazione 3 corrisponde ad un nodo al centro della griglia, quindi

con distanza massima dalle pareti e pari a 229 cm; è equidistante dai beacon; l’errore di

localizzazione è del 7.94%. Nel caso T5 della configurazione 1 si ottiene un errore dell’

8.42%; il nodo incognito è esterno alla regione dei beacon e dista dalla parete 21 cm. Infine,

il caso T4 della configurazione 3 è relativo ad un nodo incognito che dista 103 cm dalla

parete, è equidistante da due beacon e verso il limite della regione dei beacon.

Osserviamo dunque come le localizzazioni migliori si hanno per nodi incogniti

lontani dalle pareti e/o esterni alla regione dei beacon o al limite.

Analizziamo ora i casi peggiori. Il caso T3 della configurazione 4 fa rilevare un

errore del 35.19%; il nodo è fuori dalla regione dei beacon, dista 63 cm dalla parete ed è

circa equidistante da quattro beacon. Il caso T1 della configurazione 1 è relativo ad un nodo

vicinissimo ad un altro nodo ed esterno alla regione dei beacon, ma che dista dalla parete 21

cm; l’errore di localizzazione è del 36.51%. Il caso T2 della configurazione 1 presenta un

errore del 40.18%; il nodo è al limite della regione dei beacon e dista dalla parete 63 cm. Il

caso T3 della configurazione 3 presenta un errore del 42.91%; in questo caso il nodo

incognito, esterno alla regione dei beacon, dista dalla parete 21 cm. Il caso T2 della

configurazione 2 è al limite della regione dei beacon e dista dalla parete 103 cm; l’errore di

localizzazione è pari al 47.01% e la localizzazione è effettuata con tre beacon. Il caso T5

della configurazione 3 presenta un errore del 50.03%; si tratta di un nodo che dista dalla

parete 63 cm e di una localizzazione effettuata con tre nodi noti.

In tal caso possiamo notare che i dati confermano ancora una volta l’importanza

9 Definiamo regione dei beacon la più piccola superficie interna alla griglia che contiene tutti i beacon.


96

della lontananza dalle pareti; infatti, fatta eccezione per il caso 2-T2, dove comunque si

tratta di una localizzazione con tre beacon, nei casi peggiori il nodo incognito è vicino alle

pareti, nello specifico la distanza è inferiore ai 63 cm. La distanza media dalla parete dei

nodi incogniti nei casi migliori è di 118 cm; per i casi peggiori invece la distanza media è di

56 cm.

Il problema è che nel caso reale non si ha alcuna informazione circa la distanza del

nodo incognito da eventuali oggetti che possono causare riflessione del segnale; inoltre se si

osserva la posizione valutata dall’algoritmo, ci rendiamo conto che non si può utilizzare la

posizione stimata per considerare il dato affetto da errore con buona probabilità poiché,

essendo la posizione stimata affetta da errore, questa non è attendibile.

4.9 Test outdoor

La sperimentazione outdoor è stata effettuata in un ambiente di forma rettangolare e

dimensioni 583x1770 centimetri, su cui è stata realizzata una griglia di 13x39 celle,

ciascuna con lati uguali di 45 centimetri.

Sono stati effettuati nove test con 5 beacon disposti a griglia nella configurazione

mostrata in figura 4.18.

In tal caso l’errore medio rilevato è del 16.80% che corrsiponde ad uno scostamento

medio della posizione calcolata rispetto alla reale di 313.15 centimetri.

E bene osservare che una configurazione con 5 beacon in tale ambiente non è

confrontabile con la sistuazione di 5 beacon della location vista al caso precedente, essendo

notevolmente diverse le dimensioni dello spazio considerato e non essendoci pareti. Stessa

considerazione si può fare circa lo scostamento in centimetri tra posizione reale e

localizzazione effettutata dall’algoritmo. Infatti, mentre prima avevamo un ambiente di

circa 31 metri quadrati, in questo caso le dimensioni sono di 103 metri quadrati. Anche per

questo l’errore percentuale introdotto viene valutato in relazione alle dimensioni

dell’ambiente.

L’errore minimo si ha con il nodo incognito posizionato in (7, 38), caso F in figura,

dove è dell’ 1.57%. Il caso peggiore invece è il caso E, cui corrisponde un errore del


97

1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3

1 G

2

3

4

5 1 2

6

7 C

8

9

1 0

1 1

1 2 B

1 3

1 4

1 5

1 6

1 7

1 8

1 9

2 0 3 A

2 1

2 2

2 3

2 4 E

2 5

2 6

2 7

2 8 H D

2 9

3 0

3 1

3 2

3 3

3 4

3 5 I 4 5

3 6

3 7

3 8 F

3 9

Figura 4.18 – Configurazione griglia nel caso oudoor. I nodi da 1 a 5 rappresentano i beacon; da A a I i test di

localizzazione.


98

36.65%. Calcolando la media troncata, questi valori non concorrono alla determinazione del

valore medio.

Dunque i risultati in ambiente oudoor risultano migliori di quelli in ambiente chiuso

dove, come visto, riflessione del segnale e interferenze peggioravano le rilevazioni

dell’RSSI.

La figura 4.19 riporta l’andamento dell’RSSI al variare della distanza. Anche in

questo caso sono considerati i valori relativi ai beacon.

Si osserva come in tal caso sia rispettata con buona approssimazione l’ipotesi che

l’RSSI è inversamente proporzionale alla distanza, requisito necessario per una buona

localizzazione.

4.10 Analisi energetica

Parametro fondamentale di un’applicazione per WSN è il consumo di batteria

necessario per il suo utilizzo. È quindi opportuno studiare come varia il consumo di batteria

al variare del numero di nodi beacon sia per i nodi noti che per i nodi incogniti. A tal fine si

fa riferimento ai valori riportati in [8] e [48], da cui si ottengono le stime in tabella 4.2.

In entrambi i casi considereremo trascurabile il CPU bound in quanto il maggiore

dispendio energetico si ha per l’invio e la ricezione dei messaggi. Come illustrato al

Figura 4.19 – Grafico distanza-RSSI relativo ai dati dei test oudoor.

2,33

5,33 5,22

4,78

3,22

3,44

2,22

2,56

6,33

9,22

0

1

2

3

4

5

6

7

8

9

10

6 6 15,3 15,3 15,3 15,3 30 30 30,6 30,6

distanza

RS

SI


99

paragrafo 3.6, ogni beacon utilizza un certo numero di messaggi ricevuti da un altro nodo

per valutare la media dell’RSSI con cui i due nodi sono in grado di comunicare. Indichiamo

tale valore con m. Indichiamo inoltre il numero di nodi beacon che compongono la rete con

n.

Operazione Consumo di potenza (mW)10

Trasmissione 0.0495

Ricezione 0.048

Tabella 4.2 – Consumi relativi ad Iris mote per le operazioni di invio e ricezione messaggi.

4.10.1 Nodi beacon

Effettuando la valutazione di consumo energetico relativa ad un ipotetico nodo

beacon A, affinchè ogni altro bacon della rete sia in grado di valutare il valore medio di

RSSI relativo al nodo A, questo deve inviare, nel caso peggiore, ( )1−⋅ nm messaggi;

inviando un messaggio al secondo, il consumo in mJ sarà dato da ( )10495.0 −⋅⋅ nm .

Per quanto riguarda la ricezione, invece, ciascun beacon riceverà ancora ( )1−⋅ nm

messaggi dagli altri nodi beacon, più almeno m messaggi da un nodo incognito, per un totale

di nm ⋅ messaggi. Dunque, con riferimento ad i valori in tabella 4.1, si ha nm ⋅⋅048.0 .

Quindi, il consumo energetico totale è dato da:

( ) nmnm ⋅⋅+−⋅⋅ 048.010495.0 .

La figura 4.20 mostra il consumo in mJ al crescere del numero di beacon. Si osserva

una crescita lineare del consumo di batteria al crescere del numero di nodi noti, in quanto

ciò comporta un aumento del numero di messaggi necessari per il popolamento di

BeaVector e BeaTable. Dunque, in fase di scelta del numero di beacon, occorre tenere

conto anche del consumo energetico.

Come detto, anche la scelta del numero di messaggi m necessari alla valutazione

dell’RSSI è un parametro da determinare in fase di setup della rete. La figura 4.21 mostra

come nel caso dei beacon il consumo energetico vari in funzione del numero di tali

10 I valori vengono stimati effettuando una proporzione tra i valori di potenza e corrente riportati in [48] ed i valori di consumo di corrente riportati in [8].


100

messaggi. In questo caso si considera costante il numero dei beacon.

Anche in tal caso, come intuibile, si ha una crescita lineare dei consumi. Quindi, una

stima più accurata del valore medio di RSSI relativo ad una comunicazione ed una

Figura 4.20 – Consumo energetico in mJ per beacon al crescere del numero di beacon (n= 3,

4, 5) con valutazione dell’RSSI con un solo messaggio (m=1).

Figura 4.21 – Consumo energetico in mJ per beacon al crescere del numero di messaggi scambiati

per la valutazione dell’RSSI (m= 5, 10, 15, 20) con 5 beacon.

0,2

0,25

0,3

0,35

0,4

0,45

3 4 5

# beacon

mJ

0

1

2

3

4

5

6

7

8

9

10

5 10 15 20

msg RSSI

mJ


101

localizzazione migliore ottenibile con l’aumento del numero di beacon, vengono pagate con

un peggioramento delle prestazioni energetiche.

4.10.2 Nodi incogniti

Si consideri ora il caso dei nodi incogniti. Per quanto riguarda i messaggi inviati, il

worst case si ha quando devono essere inviati gli m messaggi per effettuare la valutazione

dell’RSSI a ciascun beacon, dunque nm ⋅ messaggi, per cui il consumo in mJ sarà dato da

nm ⋅⋅0495.0 . In ricezione, invece, si hanno un messaggio per la BeaTable ed un altro per la

BeaVector, per un totale di 2 messaggi, da cui il consumo in mJ pari a 2048.0 ⋅ .

In totale, dunque:

2048.00495.0 ⋅+⋅⋅ nm

Le figure 4.22 e 4.23 mostrano la variazione del consumo energetico al crescere del

numero di beacon e del numero di messaggi utilizzati per calcolare l’RSSI. Si traggono le

medesime conclusioni del caso precedente.

Figura 4.22 – Consumo energetico in mJ per nodo incognito al crescere del numero di beacon

(n= 3, 4, 5) con valutazione dell’RSSI con un solo messaggio (m=1).

0,2

0,22

0,24

0,26

0,28

0,3

0,32

0,34

0,36

3 4 5

# beacon

mJ


102

4.11 Analisi temporale

Altra caratteristica fondamentale di un algoritmo è il tempo di esecuzione. Si

intende ora analizzare come varia il tempo di esecuzione in funzione del numero dei beacon

e dei messaggi scambiati per la valutazione della potenza dei segnali. Similmente a quanto

visto per il consumo energetico, infatti, il tempo che impiega la rete appena inizializzata

affinchè un nodo incognito comunichi la sua posizione è strettamente legato al numero di

messaggi scambiati e dal numero dei nodi noti della rete, essendo trascurabili i tempi per

l’esecuzione delle altre operazioni.

Si consideri che gli RssiMsg vengano inviati ogni secondo e che ne occorrano m per

valutare l’RSSI relativo alla comunicazione tra due nodi. Consideriamo pari a n il numero

di beacon nella rete.

Ogni beacon deve ricevere ( )1−⋅ nm messaggi dagli altri beacon per poter valutare

gli RSSI relativi alle comunicazioni tra se e gli altri nodi noti della rete; inoltre occorre che

riceva un messaggio da un nodo incognito per poter valutare la potenza del segnale ricevuto

da questo. Dunque occorrono nm ⋅ messaggi. A questi bisogna aggiungere i messaggi

relativi a BeaTable e BeaVector inviati dai beacon. Tuttavia l’invio e la ricezione di questi

messaggi sono eventi asincroni, non gestiti da timer, dunque sono trascurabili al pari delle

Figura 4.23 – Consumo energetico in mJ per nodo incognito al crescere del numero di messaggi

scambiati per la valutazione dell’RSSI (m= 5, 10, 15, 20) con 5 beacon.

0

1

2

3

4

5

6

5 10 15 20

msg RSSI

mJ


103

altre operazioni. Pertanto occorrono nm ⋅ secondi per la localizzazione di un nodo.

Fissando a 20 il numero di messaggi scambiati per il calcolo degli RSSI si ha che

occorrono 60 secondi con 3 beacon, 80 secondi con 4 beacon e 100 secondi con 5 nodi noti.

Dunque aumentare il numero dei beacon implica anche un aumento del tempo

necessario alla localizzazione di un nodo incognito, introducendo un ulteriore trade-off

qualità di localizzazione-tempi di esecuzione.

4.12 Conclusioni

Da quanto visto nei paragrafi precedenti, si può concludere che i risultati ottenuti

sono soddisfacenti; la configurazione migliore del caso indoor infatti ci permette di

raggiungere un’errore di localizzazione pari al 18.77% che, nel caso di 5 beacon, scende al

17.23%; nel caso outdoor invece l’errore medio è pari al 16.80%.

Nel lavoro [35] l’errore riportato nel caso di cinque beacon in ambiente indoor è di

circa 380 cm; poiché i test sono stati effettuati in un ambiente di dimensioni 9x10 metri,

calcolando che la diagonale è di 13.45 metri, utilizzando la funzione errore introdotta,

l’errore in percentuale sarà dato da (380/1345)*100, ovvero 28.25%, quindi di 11.02 punti

percentuali maggiore di quello ottenuto nel presente lavoro.

Nel caso outdoor del medesimo lavoro [35], realizzato in ambiente di dimensioni

9x10 metri, lo scostamento riportato è di 300 centimetri che corrispondono ad un errore del

22.30%, quindi maggiore di 5.5 punti percentuali rispetto al caso outdoor mostrato qui, nel

quale l’ambiente è anche maggiore di 13 metri quadri e quindi ad una valutazione con pari

numero di beacon non corrisponde una eguale copertura dello spazio.

È stato poi mostrato che affinchè questi risultati vengano raggiunti a costi accettabili

è fondamentale una fase di setup accurata della rete. Infatti è preferibile che i beacon siano

lontani dalle pareti e disposti a griglia, ma occorre prestare attenzione affinchè la distanza

tra i beacon sia sufficiente da garantire una copertura totale della zona di interesse. Inoltre

occorre determinare il numero dei beacon necessari e sufficienti al raggiungimento di valori

dell’errore accettabili, prestando attenzione all’aumento dei consumi e dei tempi necessari

alla localizzazione. Infatti è stato mostrato come tali valori siano direttamente proporzionali


104

al numero dei beacon presenti nella rete. Ancora, la dimensione della griglia non è casuale

ma legata al numero di nodi ed alle dimensioni dell’ambiente.


105

Capitolo 5

Strategie per il miglioramento delle prestazioni

Nel capitolo precedente sono stati mostrati i risultati raggiunti con

l’implementazione proposta del ROCRSSI e le configurazioni della rete che consentono di

ottenere i risultati migliori.

In questo capitolo si mostra come è possibile migliorare le performance della

localizzazione attraverso alcuni accorgimenti al codice. In seguito viene mostrato come,

aggiungendo delle informazioni, le quali richiedono hardware aggiuntivo, sia possibile

migliorare la stima della posizione e, quindi, la qualità della localizzazione.

5.1 Griglia e celle

Come illustrato nel capitolo 4, il ROCRSSI utilizza una griglia alle cui celle è

associato un valore aggiornato ad ogni iterazione dell’algoritmo; ciascuna iterazione utilizza

i valori di RSSI relativi ad ogni beacon e le loro coordinate. Il valore della cella indica

quanti cerchi, o zone esterne ad un cerchio, o corone circolari si intersecano su quella cella.

Dalle sperimentazioni effettuate è stato osservato che talvolta le celle con valore massimo,

pari al numero dei beacon, ovvero, più in generale, le celle con il valore più alto nella

griglia, non sono in grado di rispecchiare da sole la reale posizione del nodo incognito. Di

seguito si mostra il dettaglio di alcuni casi esemplificativi.


106

Nel caso T3 della configurazione 2 vista al capitolo precedente, nella localizzazione

con tre beacon si ha la griglia riportata in figura 5.1.

Il nodo è posizionato in (6; 4). Come si può vedere ci sono sei valori 3 che fanno

localizzare il nodo incognito nella posizione (9.83; 1.67) con un errore del 25.21%. Se si

considerassero anche le celle con valore 2, sebbene la dimensione dell’area possa implicare

una approssimazione maggiore, la stessa dimensione fa anche presupporre una probabilità

più alta che il nodo sia in quella zona; il baricentro dell’area costituita dalle celle con valore

2 e valore 3 è infatti (7.00; 5.94), cui corrisponde un errore del 12.26%, meno della metà del

precedente.

Similmente nel caso T5, sempre relativo alla configurazione 2, con cinque beacon,

l’algoritmo crea la griglia in figura 5.2.

1 2 3 4 5 6 7 8 9 10 11

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

12

2 1 1 1 1 2 2 2 2 3 3 2

2 1 1 1 2 2 2 2 2 2 3 2

1 1 1 2 2 2 2 2 2 2 2 2

2 1 1 1 1 1 2 3 3 3 2 2

1 1 1 2 2 2 2 2 2 2 2 1

1 1 2 2 2 2 2 2 2 2 2 1

1 1 2 2 2 2 2 2 2 2 1 1

1 2 2 2 2 2 2 2 2 2 1 1

1 2 2 2 2 2 2 2 2 1 1 1

1 2 2 2 2 2 2 2 1 1 1 1

0 2 2 2 2 2 1 1 1 1 1 1

0 1 1 1 1 1 1 1 1 1 1 1

0 1 1 1 1 1 1 1 1 1 1 1

0 1 1 1 1 1 1 1 1 1 1 1

0 0 1 1 1 1 1 1 1 1 1 1

Figura 5.1 – Griglia relativa al caso T3 della configurazione 2.


107

In tal caso il nodo è in (11; 10) e tre celle con valore 3 fanno sì che esso venga

localizzato in (11.67; 14.67) con un errore del 26.48%. Considerando anche le celle con

valore 2, invece, si ottiene la localizzazione in (9.59; 8.68), con un errore pari al 10.84%,

ancora una volta minore della metà del caso precedente.

Si è pensato quindi di modificare l’algoritmo facendo in modo tale che, nel caso in

cui il numero di celle individuate con valore massimo fossero in numero inferiore al 5% del

numero totale di celle presenti nella griglia, questo consideri anche le celle con valore pari

al massimo meno 1. Quindi, ad esempio, nel caso di figura 5.2 la posizione stimata è data

dal centroide della regione formata da celle con valore 2 e celle con valore 3, ovvero della

regione rossa e da quella gialla.

Con tale modifica nel caso della configurazione 2, ovvero quella con nodi lontani

dalle pareti e disposti a griglia, la media troncata dell’errore passa dal 18.77%

dell’algoritmo base al 15.86%, ovvero una riduzione di 2.91 punti percentuali. Nei casi a

1 2 3 4 5 6 7 8 9 10 11

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

12

2 1 1 1 1 1 1 1 1 1 1 0

2 1 1 1 1 1 1 1 1 1 1 1

2 1 1 1 1 1 1 1 1 1 1 1

2 0 0 0 0 0 1 1 1 1 1 1

1 0 0 0 0 0 0 0 1 1 1 2

1 0 0 0 0 0 0 0 0 0 2 2

1 0 0 0 0 0 0 0 1 1 2 2

1 1 0 0 0 0 0 0 1 1 2 2

1 1 0 0 0 0 0 1 1 1 1 2

1 1 1 0 0 0 0 1 1 1 1 2

1 1 1 0 0 0 0 1 1 1 1 2

1 1 1 1 0 0 0 1 1 1 1 2

1 1 1 1 1 0 0 1 1 1 1 2

1 1 1 1 1 1 0 0 1 1 2 3

1 1 1 1 1 1 1 1 1 2 3 3



108

cinque beacon l’errore arriva al 12.02%.

Anche i casi peggiori considerati al paragrafo 4.8 permettono di osservare dei

miglioramenti; la media dell’errore diminuisce dell’ 1.64%, passando dal 41.97% al

40.33%.

Tuttavia ci sono dei casi in cui le prestazioni peggiorano. Ad esempio il caso 4-T4

con quattro beacon, la cui griglia è riportata in figura 5.3. Il nodo incognito è in (12; 11).

La localizzazione ottenuta considerando le tre celle con valore 3 da un errore del

2.65%, mentre considerando anche i valori 2, l’errore aumenta fino al 24.59%, localizzando

il nodo in (7.68; 11.73). Si osservino ora i dati utilizzati dal nodo incognito per la

localizzazione. Le tabelle 5.1 e 5.2 riportano, rispettivamente, distanze ed RSSI tra i

beacon, quindi è il beavector definito al capitolo 3, e RSSI tra nodo incognito e beacon e

coordinate dei beacon, ovvero la beatable.

1-2 1-3 1-4 1-5 2-3 2-4 2-5 3-4 3-5 4-5

RSSI 12 X 13 10 X 10 9 X X 12

dist 6.3 X 8.2 8.6 X 10.8 9.1 X X 3.2 Tabella 5.1 – Beavector caso 4-T4 con quattro beacon.

1 2 3 4 5

RSSI 9 9 X 10 13

coord (3; 5) (9; 3) X (5; 13) (8; 12) Tabella 5.2 – Beatable caso 4-T4 con quattro beacon.


109

Si può subito notare che tra i beacon 4 e 5 c’è una piccola distanza pari a 3.2 sul

piano cartesiano, il che corrisponde a circa 133 cm; nonostante ciò la potenza del segnale

con cui comunicano i due beacon è pari a 12. Tale valore, confrontato con il valore di RSSI

relativo alla comunicazione tra il nodo incognito ed il beacon 5, pari a 13, comporta

l’aggiornamento dei valori delle celle da cui scaturiscono i tre valori 3 di figura 5.3 che

effettuano la localizzazione in (11.67; 11.33) con errore pari al 2.65%. Aumentando a 13 il

valore dell’RSSI tra i beacon 4 e 5, si avrebbe una posizione stimata (8.8; 14.13) con errore

25.15% e l’algoritmo modificato restituirebbe lo stesso risultato. Dunque, si è indotti a

supporre che l’errore basso del caso 4-T4 con 4 nodi noti sia dovuto ad un caso. Del resto

osservando i dati relativi allo stesso caso, ma con cinque beacon abbiamo un errore

maggiore, pari al 33.49%, migliorato dall’algoritmo modificato al 28.35% e l’RSSI tra i

nodi beacon 4 e 5 è pari a 13, come si vede in tabella 5.3.

1 2 3 4 5 6 7 8 9 10 11

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

12

1 1 1 1 1 1 1 1 1 2 2 2

1 1 1 1 1 1 1 1 1 1 2 2

1 1 1 1 1 1 1 1 1 1 1 2

1 1 1 1 1 1 1 1 1 1 1 0

1 1 1 1 1 1 1 1 1 1 0 0

1 1 1 1 1 1 1 1 1 1 0 1

1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 2 2 1

1 1 1 1 1 1 1 1 1 2 2 2

1 1 1 1 1 1 1 1 1 2 2 2

2 1 1 1 1 1 1 1 1 1 3 3

2 2 2 1 1 1 1 1 2 2 2 3

2 2 2 2 2 2 2 2 2 2 2 2

2 2 2 2 2 2 2 2 2 2 2 2

2 2 2 2 2 2 2 2 2 2 2 2



110

1-2 1-3 1-4 1-5 2-3 2-4 2-5 3-4 3-5 4-5

RSSI 12 10 13 10 13 11 9 12 8 13

dist 6.3 5.8 8.2 8.6 5.1 10.8 9.1 5.8 4 3.2 Tabella 5.3 – Beavector caso 4-T4 con 5 beacon.

Diversa è invece la situazione del caso 1-T5 con 5 beacon. Innanzitutto in questo

caso la performance peggiora con la modifica sia con tre, che con quattro che, come detto,

con cinque beacon.

1-2 1-3 1-4 1-5 2-3 2-4 2-5 3-4 3-5 4-5

RSSI 10 8 13 10 12 9 9 10 9 11

dist 12 13,6 11,7 6,1 8,1 11,7 12,5 5,1 10,4 6,4

Tabella 5.4 – Beavector caso 1-T5 con 5 beacon.

1 2 3 4 5 6 7 8 9 10 11

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

12

2 1 1 1 0 0 0 0 0 1 1 1

2 1 1 1 1 1 0 1 1 1 1 1

1 1 1 0 0 0 0 0 0 0 1 1

1 1 1 0 0 0 0 0 0 0 0 1

1 1 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 1

1 0 0 0 0 0 0 0 0 0 1 1

2 2 0 0 0 0 0 0 0 1 1 1

2 2 1 1 0 0 0 0 1 1 1 2

2 2 2 1 1 1 2 2 2 2 2 2

3 3 3 3 2 2 2 2 2 2 2 2



111

In questo caso l’iterazione che determina i quattro valori 3 nella griglia, riportata in

figura 5.4, aggiorna una sezione vasta della griglia, così come quella che aveva portato il

valore di quelle celle da 0 a 1 e da 1 a 2; in tal caso quindi il valore raggiunto non è dovuto

ad una casualità.

Le figure 5.5 a, b, c, d, e riportano la zona in questione della griglia ad ogni

iterazione dell’algoritmo; essendo cinque i beacon i passi sono cinque.

1 2 3 4 5 6 7 8 9 10 11

11

12

13

14

15

12

0 0 0 0 0 0 0 0 0 0 0 0

...

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

1 2 3 4 5 6 7 8 9 10 11

11

12

13

14

15

12

0 0 0 0 0 0 0 0 0 0 0 0

...

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

1 2 3 4 5 6 7 8 9 10 11

11

12

13

14

15

12

0 0 0 0 0 0 0 0 0 0 1 1

...

0 0 0 0 0 0 0 0 0 1 1 1

0 0 0 0 0 0 0 0 1 1 1 1

0 0 0 0 0 0 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1

c

b

a


112

Dalle osservazioni appena fatte si può quindi dedurre che considerare solo come

«piccolo»il numero di celle con valore massimo non è sufficiente per determinare se

apportare o meno la correzione. Occorre altresì controllare per ogni singola iterazione

quante celle sono modificate così da verificare se l’aver raggiunto un valore alto è legato ad

una casualità o ad un’effettiva localizzazione del nodo incognito in quella zona della griglia.

A tal fine occorre che l’algoritmo ad ogni passo calcoli quante siano le celle

aggiornate e ricordare per ogni cella il minimo di tali valori tra quelli relativi alle iterazioni

che la interessano. Infine, se il numero di celle con valore massimo è inferiore ad una

quantità prefissata e il valore associato a tali celle che riporta il minimo di cui sopra è pari al

minimo di tutte le iterazioni, viene tentata la correzione.

Nel caso in figura si ha che in c e d viene aggiornata l’intera riga 15 e parte delle

righe 14 e 13, per un totale di, rispettivamente, 28 e 31 celle aggiornate. Al quinto passo,

1 2 3 4 5 6 7 8 9 10 11

11

12

13

14

15

12

0 0 0 0 0 0 0 0 0 0 1 1

...

1 1 0 0 0 0 0 0 0 1 1 1

1 1 1 1 0 0 0 0 1 1 1 2

1 1 1 1 1 1 2 2 2 2 2 2

2 2 2 2 2 2 2 2 2 2 2 2

d

1 2 3 4 5 6 7 8 9 10 11

11

12

13

14

15

12

1 0 0 0 0 0 0 0 0 0 1 1

...

2 2 0 0 0 0 0 0 0 1 1 1

2 2 1 1 0 0 0 0 1 1 1 2

2 2 2 1 1 1 2 2 2 2 2 2

3 3 3 3 2 2 2 2 2 2 2 2

Figura 5.5 a-e – Griglia relativa all’esecuzione dell’algoritmo con i dati del caso 1-T5 con 5 beacon

ad ogni iterazione.

e


113

riportato in figura 5.5 (e, che porta le celle dell’ultima riga al valore 3, sono aggiornate 15

celle. Il minimo si ha alla prima iterazione dove sono aggiornate 11 celle nella parte alta

della griglia, non riportata in figura. Quindi le celle con valore massimo sono quelle con

valore 3 cui è associato un valore 15 relativo al minimo di celle aggiornate nelle iterazioni

cui hanno partecipato, ma il minimo assoluto relativo all’esecuzione è 11 per cui la

correzione non sarà apportata.

In questo modo l’errore delle configurazioni 1 e 2, che si presentavano come i casi

migliori con uno scostamento medio del 19.81% e 18.77% rispettivamente, vengono

migliorati in 19.05% e 17.07%. Per quanto riguarda le configurazioni 3 e 4 si osserva

invece un peggioramento.

Anche in questo caso quindi si ottengono dei risultati che possono variare a seconda

della configurazione della rete; quindi in fase di setup, i test contribuiranno a determinare,

oltre che granularità e numero dei beacon, se è il caso o meno di utilizzare la versione

modificata dell’algoritmo che tiene in conto l’aggiornamento delle celle della griglia.

5.2 Section of Arrival

Aumentare le informazione a disposizione del nodo incognito, naturalmente, può

contribuire a migliorare la qualità della localizzazione introducendo, però, una nuova

variabile nel trade-off costi-prestazioni.

Un sensore può essere in grado di determinare, con una precisione più o meno

buona, la direzione da cui proviene un segnale. Ciò può essere realizzato in vari modi. Uno

di questi è l’utilizzo di un’antenna direzionale rotante, come proposto in [16]. Altra

soluzione è quella di utilizzare sensori con diversi ricevitori ultrasuoni, o con particolari

sensori di luminosità come il PingPong Illumimote trattato in [19].

In questa sede tuttavia vogliamo solo mostrare la variazione dell’errore che si

ottiene aggiungendo informazioni circa la posizione reciproca tra nodi incogniti e beacon.


114

Si supponga che i sensori, beacon o nodi incogniti, siano in grado di fornire in

ingresso alla procedura di localizzazione un’informazione che indichi dove si trova il nodo

incognito rispetto a ciascun nodo noto, considerando lo spazio diviso in quatttro sezioni.

Occorre, dunque, che ogni beacon possa considerarsi al centro di uno spazio che

suddivide in quattro sezioni, che possiamo indicare come nord-ovest, nord-est, sud-ovest,

Figura 5.6 – Sensore munito di antenna direzionale rotante.

Figura 5.7 – Sensore Medusa.

Figura 5.8 – Sensore Ping-Pong Illumimote della Crossbow.


115

sud-est e sia in grado di conoscere in quali di queste è presente ogni nodo con cui comunica.

Dunque rispetto al beacon X in (4, 5) della figura 5.9, il nodo A è nella sezione di nord-

ovest, il nodo B in quella di nord-est, C in sud-ovest ed, infine, il nodo incognito D è nella

sezione di sud-est.

In tal modo quando un nodo incognito eseguirà l’algoritmo di localizzazione,

quando aggiornerà i valori delle celle della griglia che corrispondono all’interno di una

circonferenza, all’esterno di una circonferenza, ad una corona circolare, non aggiorneranno

ogni parte della griglia che ricade all’interno di tali zone, bensì solo quelle relative alla

sezione in cui si trova il nodo incognito rispetto al beacon in questione. Quando il nodo C

starà localizzandosi, all’iterazione relativa al beacon X, supponendo di dover aggiornare la

zona relativa all’interno della circonferenza centrata in X e con raggio 5, incrementerà solo

il valore delle celle relative alla sezione di sud-ovest del beacon X, come mostrato in figura

5.10.

1 2 3 4 5 6 7 8 9 10 11

1 A

2

3 B

4

5 X

6

7

8 C D

9

10

11

12

13

14

15

12

N-O N-E

S-O S-E

Figura 5.9 – Esempio di griglia suddivisa in sezioni rispetto al beacon in (4. 5).


116

Per testare la bontà del metodo si è scelto un campione di 18 tra quelli visti al

capitolo precedente. I casi test sono stati suddivisi tra quelli con errore minore del valore

medio, maggiore del valore medio e quelli in un intorno del valore medio e sono stati scelti

in maniera random 6 casi per ogni gruppo. E stato modificato l’oracolo in modo da

accettare in ingresso l’informazione relativa alla sezione da aggiornare per ogni beacon e, di

conseguenza, l’azione di aggiornamento dei valori delle celle.

Si consideri come esempio il caso 2 della configurazione 0, il cui schema è riportato

alla figura 5.11.

Figura 5.10 – Aggiornamento sezione relativa al beacon X per il nodo incognito C.

1 2 3 4 5 6 7 8 9 10 11

1

2

3

4

5 X

6

7

8 C

9

10

11

12

13

14

15

12


117

In tal caso l’algoritmo ROCRSSI+ localizza il nodo in (3.58; 1.95) con un errore

dell’ 8.1%. In figura 5.12 si può osservare la griglia con i contatori delle celle cha hanno

portato a tale localizzazione.

1 2 3 4 5 6 7 8 9

1 1 X

2

3

4

5

6

7 3

8

9

10

11 2

Figura 5.11 – Griglia del caso 2 della configurazione 0. 1, 2 e 3 sono nodi beacon, X in (4; 1) è un nodo incognito.


118

Dunque si ottiene già una buona stima della posizione. Utilizzando la SoA, tuttavia,

la localizzazione migliora ulteriormente. Infatti, come si vede in figura 5.13, viene ristretta

l’area delle intersezioni e il nodo viene localizzato in (3.83; 1.67), con un errore del 5.37%,

quindi la stima migliora di 2.73 punti percentuali. Inoltre non vengono aggiornati i contatori

di celle appartenenti a spazi della griglia in cui il nodo incognito non può essere localizzato,

evitando operazioni superflue.

Considerando l’intero insieme campione, con l’utilizzo del ROCRSSI+ l’errore

medio è pari al 27.32%; introducendo l’informazione relativa alla sezione di arrivo del

segnale, invece, l’errore scende al 24.78%.

1 2 3 4 5 6 7 8 9

1 2 2 2 2 2 2 2 2 2

2 2 2 2 2 2 1 1 1 1

3 2 2 2 1 1 1 1 1 1

4 2 1 1 1 1 1 1 1 1

5

6

7

8

9

10

11

2 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

Figura 5.12 – Contatori delle celle in seguito ad esecuzione del ROCRSSI+ con dati

relativi al caso 2 della configurazione 0.


119

5.3 Angle of Arrival

Si supponga ora che l’informazione aggiuntiva sia ancora più precisa, ovvero che un

nodo sia in grado di determinare l’angolo di arrivo del segnale, AoA – Angle of Arrival.

Innanzitutto si definisce l’angolo di arrivo del segnale che dal nodo incognito giunge

al beacon, supponendo dunque che sia quest’ultimo ad avere l’hardware necessario a

determinare la direzione da cui proviene il segnale ricevuto.

Si consideri l’angolo formato in senso orario dalla congiungente del beacon e del

nodo incognito con la retta parallela all’asse delle y passante per il beacon, quindi con

equazione x = x_beacon, ovvero con lo stesso asse delle ordinate. Dunque l’angolo di arrivo

può anche essere definito come il complementare dell’arcotangente del coefficiente

angolare della retta che unisce il beacon al nodo incognito; a questo occorre poi effettuare

una correzione per far sì che l’angolo sia compreso tra 0 e 2π.

Naturalmente nel caso reale l’AoA non può essere valutato in questo modo non

1 2 3 4 5 6 7 8 9

1 1 2 2 2 2 2 2 1 1

2 1 2 2 2 2 1 1 1 1

3 1 2 2 1 1 1 1 1 1

4 1 0 0 0 0 0 0 0 0

5

6

7

8

9

10

11

1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

Figura 5.13 – Contatori delle celle in seguito ad esecuzione del ROCRSSI+ con SOA

con dati relativi al caso 2 della configurazione 0.


120

essendo nota apriori la posizione del nodo incognito; pertanto il beacon deve essere in grado

di valutare l’angolo con cui riceve i segnali e restituire ai nodi incogniti tale informazione in

un formato congruo con la precedente definizione.

In tal caso la zona di celle da aggiornare è ancora più ristretta e corrisponde

all’intersezione tra l’interno di una circonferenza, o l’esterno di una circonferenza, o una

corona circolare, e la regione di piano compresa tra due semirette con origine nel punto in

cui si trova il beacon e coefficienti angolari pari alle tangenti dei complementari degli

angoli estremi di un intorno centrato nell’angolo di arrivo del segnale inviato dal nodo

incognito al beacon in questione. Un esempio è riportato in figura 5.15.

Si noti che la SoA, vista al paragrafo 5.2, può essere considerata come un caso

particolare di questo, ottenuto considerando un intorno asimmetrico dell’angolo di arrivo

Figura 5.14 – Circonferenza goniometrica centrata sul beacon di riferimento.


121

che descrive la regione di piano compresa tra due rette che si intersecano in corrispondenza

del beacon e perpendicolari tra loro e con gli assi del piano.

Considerando lo stesso campione di esperimenti del paragrafo precedente, valutiamo

l’errore medio del ROCRSSI+ con l’aggiunta dell’AoA facendo variare l’ampiezza

dell’intorno dello stesso angolo.

Si consideri dapprima un angolo di 90°, quindi due rette distinte che passano per il

punto in cui si trova il beacon, sono perpendicolari tra loro e formano ciascuna un angolo di

45° con la retta che unisce il beacon al nodo incognito. Si osservi che qui, sebbene l’angolo

tra le due rette sia di 90°, non corrisponde ad una sezione del caso precedente, in quanto ora

la zona di griglia che si va ad aggiornare non è delimitata da rette perpendicolari agli assi,

bensì è centrata rispetto alla retta che unisce nodo incognito e nodo beacon.

Figura 5.15 – Aggiornamento celle relative al beacon X e al nodo incognito A. Intersezione con

corona circolare.

A

X


122

Si ricorda che l’errore medio dei diciotto campioni è pari al 27.32%. In questo caso,

invece, si ottiene un errore del 19.68%.

Restringendo ulteriormente la regione di piano delimitata dalle rette con origine nel

beacon, facendo in modo che queste formino un angolo di 45°, è possibile diminuire

ulteriormente l’errore.

Si riconsideri il caso 2 della configurazione 0, le cui griglie con contatori in seguito

all’esecuzione di ROCRSSI+ e ROCRSSI+ con SoA sono riportate alle figure 5.12 e 5.13.

In seguito all’esecuizione dell’algoritmo di localizzazione con AoA con intorno dell’angolo

di arrivo di 45°, si ottiene un errore pari a 0. Ciò che è interessante, tuttavia, non è l’assenza

di errore nel singolo caso, bensì mostrare, attraverso la griglia di figura 5.16, l’ulteriore

riduzione della zona di intersezione e l’aumento del numero di celle che l’algoritmo non ha

coinvolto.

Con l’intorno dell’angolo di 45°, l’errore medio sui 18 campioni considerati

dminuisce fino al 15.83%.


123

Tuttavia, come mostrato in figura 5.17, diminuendo ancora l’ampiezza

dell’intervallo fino a 22.5° è possibile osservare un peggioramento delle prestazioni;

l’errore medio infatti aumenta al 18.98%, migliore del caso iniziale, ma peggiore rispetto al

precedente con angolo tra le rette pari a 45°.

1 2 3 4 5 6 7 8 9

1 1 2 2 2 2 2 1 1 1

2 0 0 0 1 1 0 0 0 0

3

4

5

6

7

8

9

10

11

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

Figura 5.16 - Contatori delle celle in seguito ad esecuzione del ROCRSSI+ con AOA

con dati relativi al caso 2 della configurazione 0.


124

Ciò è dovuto all’inaffidabilità del RSSI che, come detto, non sempre è inversamente

proporzionale alla distanza, per cui l’algoritmo ROCRSSI+ tende a coprire zone della

griglia lontane dal nodo incognito e l’intersezione con la regione delimitata dalle rette fa sì

che l’algoritmo converga verso una posizione che si discosta notevolmente da quella reale.

Ancora una volta, dunque, occorre prestare attenzione ai parametri da scegliere in

quanto non necessariamente restringere la regione della griglia da considerare significa

ottenere risultati migliori o, comunque, risultati per i quali convenga aumentare il costo

della rete.

Figura 5.17 – Variazione dell’errore al diminuire dell’ampiezza dell’intorno dell’angolo di arrivo.

18,931875

15,82875

19,6775

27,31625

10

12

14

16

18

20

22

24

26

28

30

90 45 22,5

ampiezza intorno AOA - gradi

err

ore

- %


125

Capitolo 6

Conclusioni e sviluppi futuri

6.1 Conclusioni

L’obiettivo di questo lavoro è stato quello di ottenere risultati sperimentali relativi

alla localizzazione in reti di sensori con l’utilizzo della metrica RSSI, evitando l’utilizzo di

hardware costoso e, quindi, preferendo algoritmi di tipo range-free. Nello specifico, è stata

utilizzata la tecnica di Ring Overlapping based on Comparison of RSSI. Tali risultati,

dunque, sono stati raggiunti, avendo testato tale metodologia di localizzazione con

hardware e software all’avanguardia che ha consentito di agevolare la fase di debug prima e

di rilevamento dei dati poi. Le prove di localizzazione sono state effettuate in diversi

ambienti indoor ed anche in un ambiente outdoor di circa 103 metriquadrati. Inoltre, è stata

osservato l’andamento dell’errore al variare della disposizione dei nodi beacon e, quindi, in

diverse configurazioni della rete a parità di ambiente, e al variare della granularità della

griglia, introdotta con l’algoritmo di grid-scan, per poi fare delle osservazioni relative al

consumo energetico ed ai tempi di esecuzione.

Inoltre è stato individuato, e risolto, un problema di consistenza dell’algoritmo

ROCRSSI.

I dati sperimentali rilevati hanno mostrato che il fenomeno di riflessione del segnale

influenza i valori rilevati di RSSI. Quindi è stato visto che in ambiente indoor è preferibile

una disposizione a griglia dei nodi beacon e posizionare questi ad una distanza di almeno un


126

metro dalle pareti. Con tale configurazione è stato ottenuto un errore del 17.23% in un

ambiente di 31 metriquadrati con 5 beacon. Tale errore corrisponde ad una distanza tra

posizione reale e posizione determinata di 137.15 centimetri.

Inoltre, è stato mostrato che in fase di setup della rete, occorre determinare, in base

all’ambiente, il numero dei beacon e la granularità della griglia da utilizzare, evitando che

ciò comporti un eccessivo aumento del consumo di batteria e dei tempi di acquisizione dei

dati necessari all’esecuzione dell’algoritmo di localizzazione. L’errore ha mostrato un

comportamento asintotico, per cui da un certo punto in poi la qualità della localizzazione

non migliora anche aumentando il numero di beacon e affinando la grana della griglia.

In ambiente outdoor, dove non erano presenti fenomeni di riflessione dovuti alle

pareti, sono stati ottenuti risultati migliori. Infatti, con una disposizione a griglia di 5

beacon, in un ambiente di 103 metri quadri, l’errore medio di localizzazione è stato del

16.80%, pari a 313.15 centimetri.

Lo studio dei dati ricavati ha consentito di introdurre una modifica alla procedura di

grid-scan volta ad evitare la localizzazione dovuta ad un esiguo numero di celle il cui

contatore ha raggiunto il valore massimo per una iterazione che coinvolge una ridotta area

della griglia.

È stato poi mostrato come l’introduzione dell’ AoA contribuisca a ridurre l’errore di

un campione di diciotto esperimenti dal 27.32% al 15.83%, comportando quindi un

miglioramento del 42.06%.

6.2 Sviluppi futuri

Nel corso dell’implementazione del codice e dello studio dei dati rilevati dalla

sperimentazione, sono stati individuati punti di intervento per ottimizzare l’algoritmo ed il

codice, nonché nuove tematiche di studio.

È stato mostrato che per determinare il valore di RSSI relativo alla comunicazione

tra due beacon è necessario utilizzare un certo numero di messaggi. Allo stato attuale tale


127

numero viene determinato in fase di inizializzazione della rete. Tuttavia, allo scopo di

semplificare la fase di setup e rendere maggiormente scalabile ed adattativo il sistema, il

numero dei messaggi può essere deciso dinamicamente dai nodi. Si può supporre dunque di

stabilire un numero iniziale n di messaggi e che tale numero possa crescere o decrescere in

base alle caratteristiche della rete. Tali caratteristiche sono relative alla varianza

dell’insieme di valori RSSI rilevati ed al numero di beacon della rete. Se i nodi dovessero

osservare una stabilità dei valori rilevati ciò consentirebbe di poter ridurre il numero di

messaggi necessari all’assegnazione di un valore di RSSI al canale; viceversa, valori molto

variabili indurrebbero alla scelta di un numero maggiore di messaggi necessari alla

determinazione di un valore. Inoltre, il numero di messaggi deve essere relazionato anche

alla quantità di nodi noti, in quanto la durata di esecuzione dell’algoritmo è legata al

numero di beacon e di messaggi scambiati, per cui esiste un trade-off tra qualità della stima

dell’RSSI e tempo di esecuzione dell’algoritmo e consumo energetico. Considerazioni

analoghe possono essere effettuate sulla granularità della griglia, sebbene in tal caso la

variazione sia legata al numero di istruzioni da eseguire e non al numero di messaggi da

scambiare, pertanto i miglioramenti non avrebbero grosso impatto sul tempo di esecuzione

e sul consumo di batteria.

Per migliorare le prestazioni dal punto di vista energetico, è bene che il modulo

radio sia disattivato al termine della determinazione dei dati utili alla localizzazione per i

nodi beacon e della comunicazione della posizione stimata per i nodi incogniti. Occorre poi

ottimizzare la scelta del momento in cui ripetere la localizzazione, per evitare lo scambio di

messaggi e quindi la riattivazione del modulo radio quando non ci sono stati cambiamenti

nella rete. Attualmente ciò avviene attraverso l’utilizzo di timer, ovvero il sistema ripete la

localizzazione ad intervalli regolari, la cui dimensione può variare in base all’applicazione.

Tuttavia è possibile utilizzare l’accelerometro presente su molte sensor board e fare in

modo che la procedure sia ripetuta quando un nodo mobile, e quindi un nodo incognito,

rileva di aver subito uno spostamento.

In generale, si può dire che l’obbiettivo è quello di ottenere un duty cycle


128

caratterizzato per la maggior parte da uno stato di sleep del sensore, sia per la CPU che per

il modulo radio.

Al fine di migliorare la qualità di localizzazione dell’algoritmo utilizzato potrebbe

essere utile effetuare una modellazione dell’errore ottenuto su un insieme maggiore di

esperimenti. Infatti, l’eventuale individuazione di uno o più fattori comuni a dei nodi

potrebbe consentire l’individuazione di una tecnica per la riduzione dello stesso, similmente

a quanto fatto per la tecnica di grid-scan.

Nel corso dell’analisi sono stati effettuati dei tentativi di correzione dei valori di

RSSI rilevati, in particolare quelli relativi ai casi in cui l’errore era piuttosto alto e il

fenomeno di riflessione evidente; ciò sfociava in valori di potenza del segnale ricevuto che

non erano inversamente proporzionali alla distanza. Sono stati effettuati tentativi di

correzione di tali valori, tuttavia non è stato individuato un metodo che migliorasse sempre

la stima della posizione o che, quantomeno, la lasciasse inalterata nei casi che poi si sono

mostrati migliori. Una quantità maggiore di dati potrebbe consentire di individuare un

metodo per correggere i valori di potenza del segnale di BeaVector e BeaTable al fine di

verificare l’inversa proporzionalità tra RSSI e distanza e, quindi, un errore inferiore.

Visti i problemi legati alla riflessione del segnale e quindi al valore di RSSI rilevato

utilizzando lo standard ZigBee, potrebbero essere utilizzati sensori con modulo Bluetooth.

Infatti, alcuni lavori, tra cui [7], hanno mostrato la stabilità dei valori di RSSI rilevati con

tale standard di comunicazione. Inoltre l’introduzione, a dicembre 2009, del Bluetooth 4.0,

supera i problemi precedenti di questo standard. Come indicato dal Bluetooth SIG – Special

Interest Group – in [21], tale specifica prevede dei grossi miglioramenti rispetto alla

versione precedente, che consitono in:

� riduzione dei consumi;

� funzionamento per anni con batterie a moneta;

� costi ridotti;

� interoperabilità con moduli radio sviluppati da produttori diversi;


129

� range d’azione maggiore.

In tal modo il bluetooth potrebbe essere considerato utilizzabile in reti di sensori

senza filo, avendo superato i problemi di consumo che ne impedivano l’utilizzo.

Sarebbe inoltre utile la sperimentazione con l’uso di sensori capaci di stimare

l’angolo di arrivo del segnale, così da valutare sul campo gli effettivi miglioramenti

ottenibili da quanto mostrato al capitolo 5.


130

Appendice A

A.1 Datasheet Iris Mote

Di seguito i datasheet dei mote board utilizzati. Per informazioni relative ad altri

componenti hardware mensionati in tale lavoro si faccia riferimento alla bibliografia ed al

sito del produttore, www.xbow.com.


131


132


133

A.2 Installazione di TinyOS2.1 in Windows

1. Scaricare:

1. java jdk: http://java.sun.com/javase/downloads/index.jsp;

2. cygwin: http://cone.informatik.uni-freiburg.de/people/aslam/cygwin-files.zip;

3. avr-binutils: http://www.tinyos.net/dist-2.1.0/tools/windows/avr-binutils-

2.17tinyos-3.cygwin.i386.rpm;

4. avr-gcc: http://www.tinyos.net/dist-2.1.0/tools/windows/avr-gcc-4.1.2-

1.cygwin.i386.rpm;

5. avr-libc: http://www.tinyos.net/dist-2.1.0/tools/windows/avr-libc-1.4.7-

1.cygwin.i386.rpm;

6. avarice: http://www.tinyos.net/dist-2.1.0/tools/windows/avarice-2.4-

1.cygwin.i386.rpm;

7. insight (avr-gdb): http://www.tinyos.net/dist-2.1.0/tools/windows/avr-insight-

6.3-1.cygwin.i386.rpm;

8. avrdude: http://www.tinyos.net/dist-2.1.0/tools/windows/avrdude-tinyos-

5.6cvs-1.cygwin.i386.rpm;

9. NesC: http://www.tinyos.net/dist-2.1.0/tinyos/windows/nesc-1.3.0-

1.cygwin.i386.rpm;

10. Deputy: http://www.tinyos.net/dist-2.1.0/tinyos/windows/tinyos-deputy-1.1-

1.cygwin.i386.rpm;

11. tinyos-tools: http://www.tinyos.net/dist-2.1.0/tinyos/windows/tinyos-tools-

1.3.0-1.cygwin.i386.rpm;

12. TinyOS: http://www.tinyos.net/dist-2.1.0/tinyos/windows/tinyos-2.1.0-

2.cygwin.noarch.rpm;

13. Graphviz: http://www.graphviz.org/Download.php.

2. Installare:

1. java;

2. cygwin;


134

in cygwin:

3. rpm -ivh avr-binutils-2.17tinyos-3.cygwin.i386.rpm;

(se il sistema indica che è presente una versione più nuova: rpm -Uvh –force

avr-binutils-2.17tinyos-3.cygwin.i386.rpm);

4. rpm –ivh avr-gcc-4.1.2-1.cygwin.i386.rpm;

5. rpm –ivh avr-libc-1.4.7-1.cygwin.i386.rpm;

6. rpm –ivh avarice-2.4-1.cygwin.i386.rpm;

7. rpm –ivh avr-insight-6.3-1.cygwin.i386.rpm;

8. rpm –ivh avrdude-tinyos-5.6cvs-1.cygwin.i386.rpm;

(se il sistema indica che manca /bin/sh: rpm -Uvh --force –nodeps avrdude-tinyos-

5.6cvs-1.cygwin.i386.rpm);

9. rpm –Uvh nesc-1.3.0-1.cygwin.i386.rpm;

10. rpm –i tinyos-deputy-1.1-1.cygwin.i386.rpm;

11. rpm –Uvh tinyos-tools-1.3.0-1.cygwin.i386.rpm;

12. rpm –ivh tinyos-2.1.0-2.cygwin.noarch.rpm;

in windows:

13. graphviz;

14. da /cygwin/lib/tinyos copiare i file toscomm.dll e getenv.dll in

/java/jdk<…>/jre/bin (in tal modo si installa tos-jni).

(Se il sistema indica un errore relativo al sistema operativo: rpm -ivh --ignoreos

<rpm>)

A tal punto occorre creare uno script che setti le variabili d’ambiente.

In /cygwin/bin creare il file setTinyos-2.sh:

#!/bin/sh

#Script di configurazione delle variabili d'ambiente di

#TinyOs-2.x


135

echo "Unsetting old variables..."

unset TOSROOT

unset TOSDIR

unset MAKERULES

unset CLASSPATH

#TinyOS 2.x Environment Variable Windows - Cygwin

echo "Setting new variables..."

export TOSROOT=/opt/tinyos-2.x

echo "TOSROOT set to : " ${TOSROOT}

export TOSDIR=$TOSROOT/tos

echo "TOSRDIR set to : " ${TOSDIR}

export MAKERULES=$TOSROOT/support/make/Makerules

echo "MAKERULES set to : " ${MAKERULES}

#export CLASSPATH="$CLASSPATH;'cygpath -w

$TOSROOT/support/sdk/java/tinyos.jar';'cygpath -w

$TOSROOT/support/sdk/java';'cygpath -w $TOSROOT/support/sdk/java/net';."

export CLASSPATH="c:\cygwin\opt\tinyos-2.x\support\sdk\java\tinyos.jar;."

echo "CLASSPATH set to : " ${CLASSPATH}

echo "Done! All variables are set."

echo "All done!"

In coda al file cygwin/home/<nome_utente>/.bash_profile aggiungere alias tinyos-

2='source setTinyOs-2.sh'.

Si faccia in modo che i caratteri di end line nei file editati seguano lo standard linux.

A.3 XSniffer

Questo tool sviluppato dalla Crossbow consente di monitorare i pacchetti scambiati

tra i mote alle frequenze radio. Ci sono due applicazioni per XSniffer:


136

� il codice TinyOS per i mote, da eseguire su una base station MIB510 o

MIB520;

� la GUI XSniffer da installare ed eseguire su PC.

La base station viene programmata per rilevare tutti i messaggi radio scambiati nel

raggio d’azione del suo modulo radio su un determinato canale. Di default il canale è 11

con frequenza centrale 2455 MHz. Il software può essere utilizzato per verificare se un

nodo si è unito alla rete, per controllare la sequenza dei pacchetti o i dati contenuti nei

messaggi.

L’interfaccia presenta diverse schede, la principale è la scheda dei log che mostra

tutto il traffico catturato indicando:

� Timestamp del messaggio;

� Indirizzo di destinazione del messaggio;

� La potenza del segnale ricevuto dal mote su cui è installato XSniffer;

� Il tipo di messaggio (health, sync, …);

� ID del gruppo di appartenenza del nodo;

� Lunghezza del messaggio;

� Mittente;

� Destinatario;

� Numero di sequenza; viene incrementato dal mote sorgente all’inoltro di

ogni messaggio;

� Numero di hop effettuati dal messaggio;

� Application ID;

� Payload del messaggio suddiviso in byte.

E possibile fare in modo che ad ogni tipologia di messaggio sia associato un colore

di visualizzazione per semplificarne l’individuazione.


137

Il software richiede che sia specificata la porta seriale cui è collegata la

programming board con il mote su cui è installato il codice nesC di XSniffer.

Una funzionalità particolarmente utile del sistema è che consente l’output su un file

excel dei dati catturati.

Figura A.1 – Esempio di schermata di XSniffer in funzione su un PC.


138

Bibliografia

[1] A. Savvides, Chih-Chieh Han, M.B. Strivastava – Dynamic fine-grained

localization in ad-hoc networks of sensors

[2] Ambili Thottam Parameswaran, Mohammad Iftekhar Husain, Shambhu

Upadhyaya – Is RSSI a Reliable Parameter in Sensor Localization Algorithms

– An Experimental Study

[3] Andreas Savvides, Chih-Chieh Han, Mani B. Strivastava – Dynamic Fine-

Grained Localization in Ad-Hoc Networks of Sensors

[4] Asis Nasipuri, Kai Li – A Directionality based Location Discovery Scheme for

Wireless Sensor Networks

[5] Chong Liu, Kui Wu – Performance Evaluation of Range-Free Localization

Methods for Wireless Sensor Networks

[6] Chong Liu, Kui Wu, Tian He – Sensor Localization with Ring Overlapping

Based on Comparison of Received Signal Strength Indicator

[7] Cristiano di Flora, Massimo Ficco, Stefano Russo, Vincenzo Vecchio – Indoor

and outdoor location based services for portable wireless devices

[8] Datasheet Iris Mote –

http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/IRIS_Datash

eet.pdf

[9] Datasheet Iris OEM –

http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/IRIS_OEM_

Datasheet.pdf

[10] Datasheet MIB520 –


139

http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/MIB520_Dat

asheet.pdf

[11] Datasheet MTS400 –

http://www.xbow.com/products/Product_pdf_files/Wireless_pdf/MTS400-

420_Datasheet.pdf

[12] Datasheet ricetrasmettitore radio – Atmel AT86RF230

[13] Datasheet WSN PROFESSIONAL KIT –

http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/WSN_PRO_

Series_Datasheet.pdf

[14] David Gay, Philip Levis, Robert von Behren, Matt Welsh, Eric Brewer, David

Culler – The nesC Language: A Holistic Approach to Networked Embedded

Systems

[15] Dragos Niculescu, Badri Nath – Ad Hoc Positioning System (APS) Using

AOA

[16] Eiman Elnahrawy, John Austen-Francisco, Richard P. Martin – Adding Angle

of Arrival Modality to Basic RSS Location Management Techniques

[17] Gabriele D’avino – Studio e sperimentazione di sistemi di localizzazione per

reti di sensori senza filo

[18] H. Davis, R. Miller – Power Management for Mica2 Motes

[19] H. Park, J. Friedman, P. Gutierrez, V. Samanta, J. Burke, M. B. Srivastava –

Illumimote: multi.modal and high fidelity light sensor module for Wireless

Sensor Networks

[20] http://remoam.consorzio-cini.it

[21] http://www.bluetooth.com/Bluetooth/Press/SIG/SIG_INTRODUCES_BLUET

OOTH_LOW_ENERGY_WIRELESS_TECHNOLOGY_THE_NEXT_GENE

RATION_OF_BLUETOOTH_WIRELESS_TE.htm

[22] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci – Wireless sensor

networks: a survey

[23] IEEE Computer Society – 802.15.4 2003, 2006, 2007 – Wireless Medium


140

Access Control (MAC) and Physical Layer (PHY) Specifications for Low-

Rate Wireless Personal Area Networks (WPANs)

[24] J. Hightower, G. Borriello – A survey and taxonomy of location system for

ubiquitous computing

[25] Je_rey Hightower, Gaetano Borriello – A Survey and Taxonomy of Location

Systems for Ubiquitous Computing

[26] K. Langendoen, N. Reijers – Distributed localization in wireless sensor

networks: a quantitative comparison

[27] Koen Langendoen, Niels Reijers – Distributed localization in wireless sensor

networks: a quantitative comparison

[28] Matteo Andretto – Studio e sperimentazione di algoritmi di localizzazione per

reti di sensori

[29] MTS/MDA Sensor Board Users Manual, Revision A, giugno 2007

[30] Nirupama Bulusu, John Heidemann, Deborah Estrin – GPS-less Low Cost

Outdoor Localization For Very Small Devices

[31] Nirupama Bulusu, John Heidemann, Deborah Estrin – GPS-less low cost

outdoor localization for very small devices

[[3322]] Patrick Kinney – ZigBee Technology: Wireless Control that Simply Works

[33] Philip Buonadonna, Jason Hill, David Culler – Active Message

Communication for Tiny Networked Sensors

[34] Philip Levis – TinyOS Programming

[35] Riccardo Crepaldi – Algoritmi di localizzazione per reti di sensori:

progettazione e realizzazione di una piattaforma sperimentale

[36] Riccardo Crepaldi, Paolo Casari, Andrea Zanella, Michele Zorzi – Testbed

Implementation and Refinement of a Range–Based Localization Algorithm for

Wireless Sensor Networks

[37] Rong Peng, Mihail L. Sichitiu – Angle of Arrival Localization for Wireless

Sensor Networks

[38] Sebastiaan Blom, Matteo Andretto, Andrea Zanella – Poster Abstract:


141

Experimental Localization Results in an Indoor Wireless Sensor Network

Testbed

[39] Sensor Network Applications

[40] Sensor Networks

[41] Sinem Coleri Ergen – ZigBee/IEEE 802.15.4 Summary

[42] Tian He, Chengdu Huang, Brian M. Blum, John A. Stankovic, Tarek

Abdelzaher – Range-Free Localization Schemes for Large-Scale Sensor

Networks

[43] TinyOS Community Forum – http://www.tinyos.net/

[44] TinyOS documentation wiki – http://docs.tinyos.net

[45] TinyOS help – https://www.millennium.berkeley.edu/pipermail/tinyos-help/

[46] TinyOS Iris documentation – Interfaces and components –

http://www.tinyos.net/tinyos-2.x/doc/nesdoc/iris/index.html

[47] TinyOS Tutorials – http://docs.tinyos.net/index.php/TinyOS_Tutorials

[48] Victor Shnayder, Mark Hempstead, Borrong Chen, Geoff Werner Allen, Matt

Welsh – Simulating the Power Consumption of Large-Scale Sensor Network

Applications

[49] Volkan Cevher, Rajbabu Velmurugan,James H. McClellan – Acoustic

Multitarget Tracking Using Direction-of-Arrival Batches

[50] William C. Craig – Zigbee: “Wireless Control That Simply Works”


142

Ringraziamenti

Il primo, grande Grazie è rivolto, naturalmente, ai miei Genitori. Ogni cosa fatta, nel

bene e nel male, è avvenuta grazie a loro, che mi hanno consentito di crescere, studiare,

giocare, avere il primo computer, la prima automobile, tutto.

Ringrazio i miei nipotini Ciro, Fabrizio e Lucrezia che con la loro dolcezza ed il loro

affetto mi hanno rallegrato nei momenti peggiori e che con il loro desiderio di giocare mi

hanno distratto in quelli più intensi…

Ringrazio mia sorella Barbara che crede in me, mi spinge a migliorarmi e a fare

tutto, presto e bene. Il suo incitamento è fondamentale.

Grazie a Ettore che mi è stato vicino in ogni momento, di studio e non, dalla

fanciullezza ad oggi e che, sono certo, continuerà a farlo.

Un ringraziamento a Marcella, sempre presente e disponibile nello studio come in

ogni evento della mia vita.

Grazie a mio fratello Peppe che mi ha iniziato allo studio, alla conoscenza, alla vita.

Il mio modo di vivere e di vedere la vita, la mia voglia di conoscere e di capire e il desiderio

di creare sono dovuti in buona parte a lui.

Ringrazio Dora e Pietro sempre gentili, disponibili, pronti ad invogliarmi.

Grazie ad Annalisa e Walter che hanno messo a disposizione i loro spazi per i miei

esperimenti, ma soprattutto per essere sempre vicini.

Un sentito grazie al Prof. Cinque, sempre disponibile, chiaro nelle spiegazioni,

brillante nei consigli, nonché pronto al sorriso nei momenti opportuni.

Ringrazio il Prof. Cotroneo per avermi sempre sostenuto, aiutato ed incitato e per

essere stato di esempio, non solo durante la stesura di questa tesi, ma in tutto il percorso


143

accademico.

Ringrazio il Prof. Russo, esempio di professionalità, cultura, brillantezza ed

eleganza come pochi.

Un sentito grazie anche ad Alessandro e a tutti i ragazzi del Mobilab.

Per avermi ospitato, riscaldato o raffreddato, per aver fatto sempre con me, ogni

giorno, il percoso casa-università e viceversa durante la realizzazione del lavoro di tesi e

ogni altro spostamento, per avermi aiutato a raggiungere i traguardi il più velocemente

possibile, grazie Biemvè.

In questi anni di duro lavoro è stata fondamentale la presenza di Ilaria. Mi ha

aiutato, esortato, dato carica, rallegrato, supportato e sopportato. È stata spesso vittima

sacrificale dei miei sfoghi. Fortunatamente mi ha compreso (e sa che dovrà comprendermi

ancora... spero...).

Grazie per avermi cambiato la vita.

Facoltà di Ingegneria tesi di laurea specialistica ... Flavio Frattini.pdf · 3.10 Struttura dei...

Documents

Transcript of Facoltà di Ingegneria tesi di laurea specialistica ... Flavio Frattini.pdf · 3.10 Struttura dei...