Progetto e realizzazione di una procedura per la ...infocom.uniroma1.it/~robby/Tesi/Sperduti...

UNIVERSITÀ DEGLI STUDI DI ROMA “LA SAPIENZA”

FACOLTÀ DI INGEGNERIA CORSO DI LAUREA SPECIALISTICA IN INGEGNERIA DELLE TELECOMUNICAZIONI

INFO-COM DPT.

DIPARTIMENTO DI SCIENZA E TECNICA DELL’INFORMAZIONE E DELLA COMUNICAZIONE

Progetto e realizzazione di una procedura per

la localizzazione in ambienti indoor con copertura Wi-Fi

Relatore Correlatore

Prof. Roberto CUSANI Ing. Stefano RINAURO

Laureando Daniele SPERDUTI

Tesi di Laurea Specialistica

Anno Accademico 2007/2008

Indice

2

Indice

Indice delle figure ................................................................................................... 5

Introduzione ........................................................................................................... 8

1. Le reti locali Wireless....................................................................................... 12

1.1 Wireless Local Area Network ...................................................................... 13

1.2 Standard IEEE 802.11 .................................................................................. 20

1.2.1 Topologie di WLAN ........................................................................... 22

1.2.2 Livello fisico ....................................................................................... 25

1.2.3 Livello MAC ....................................................................................... 28

1.2.4 Evoluzione dello standard 802.11 ....................................................... 40

2. La localizzazione indoor .................................................................................. 48

2.1 Caratteristiche dei sistemi di posizionamento .............................................. 49

2.1.1 Sistemi di rappresentazione della posizione ....................................... 51

2.1.2 Infrastrutture di reti finalizzate alla localizzazione ............................. 52

2.2 Tecniche di posizionamento ......................................................................... 54

2.2.1 Proximity Sensing ............................................................................... 55

2.2.2 Lateration ............................................................................................ 56

2.2.3 Angle of Arrival .................................................................................. 60

2.2.4 Time of Arrival ................................................................................... 61

2.2.5 Scene Analisys .................................................................................... 63

2.3 Soluzioni per la localizzazione indoor in WLAN ........................................ 71

2.3.1 RADAR di Microsoft .......................................................................... 71

2.3.2 RTLS di Ekahau .................................................................................. 73

2.3.3 AeroScout Visibility system ............................................................... 74

2.3.4 Cisco Wireless Location Appliance .................................................... 76

3. Algoritmi e metodi di localizzazione indoor .................................................. 79

Indice

3

3.1 Classificazione ............................................................................................. 80

3.2 Metodi di fingerprinting ............................................................................... 81

3.2.1 Metodo Nearest in Signal Space ......................................................... 82

3.2.2 Metodo probabilistico ......................................................................... 84

3.3 Metodi di filtraggio ...................................................................................... 86

3.3.1 Filtro di Kalman .................................................................................. 87

3.3.2 Particle Filter ....................................................................................... 89

3.4 Metodi basati sulle reti neurali ..................................................................... 90

3.4.1 Reti Winner-take-all ............................................................................ 93

3.4.2 Reti Self-organizing map .................................................................... 96

4. Analisi delle prestazioni ................................................................................... 99

4.1 Specifiche generali del sistema .................................................................. 100

4.2 Test sperimentali ........................................................................................ 109

4.2.1 Risultati sperimentali: algoritmo NNSS ........................................... 111

4.2.2 Risultati sperimentali: metodo probabilistico ................................... 113

4.2.3 Risultati sperimentali: metodo del centroide..................................... 115

4.2.4 Osservazioni sui metodi di filtraggio ................................................ 117

5. Architettura del sistema ................................................................................ 119

5.1 Misurazione di grandezze elettromagnetiche ............................................. 121

5.2 Test di riferimento ...................................................................................... 126

5.3 Soluzione proposta ..................................................................................... 127

5.3.1 Realizzazione della rete neurale ........................................................ 131

5.3.2 Definizione delle funzioni di strato ................................................... 132

5.3.3 Diagramma di funzionamento della rete neurale .............................. 136

5.3.4 Risultati sperimentali dell’algoritmo proposto ................................. 138

5.3.5 Caso di studio .................................................................................... 143

Conclusioni ......................................................................................................... 146

Appendice ........................................................................................................... 148

Indice

4

1. Specifiche tecniche dello smartphone Nokia E51 ........................................ 148

2. Datasheet del router Sparklan modello WX-6615GT .................................. 149

3 Datasheet degli AP NETGEAR modello WG102 ........................................ 150

Bibliografia ......................................................................................................... 151

Ringraziamenti ................................................................................................... 154

Indice delle figure

5

Indice delle figure

Figura 1 – Classificazione delle tecniche di posizionamento .................................. 8

Figura 1.1 – Architettura classica di una rete WLAN ............................................ 14

Figura 1.2 – Alcuni standard del gruppo IEEE 802 ............................................... 21

Figura 1.3 – Modello OSI e standard 802.11 ......................................................... 22

Figura 1.4 – Independent Basic Service Set........................................................... 23

Figura 1.5 – Basic Service Set ............................................................................... 23

Figura 1.6 – Exended Service Set .......................................................................... 24

Figura 1.7 – Handover in WLAN .......................................................................... 25

Figura 1.8 – Caratteristiche fisiche degli standard del gruppo 802.11 .................. 26

Figura 1.9 – Modulazione DSSS ............................................................................ 28

Figura 1.10 – Il problema della stazione nascosta ................................................. 31

Figura 1.11 – Il protocollo four way handshake .................................................... 32

Figura 1.12 – Schema DFWMAC-DCF ................................................................ 33

Figura 1.13 – Frammentazione .............................................................................. 36

Figura 1.14 – Formato del frame dati..................................................................... 37

Figura 1.15 – Formato di alcuni frame di tipo Controllo ....................................... 38

Figura 1.16 – Formato PLCP ................................................................................. 39

Figura 1.17 – Formato del pacchetto 802.11.......................................................... 39

Figura 1.18 – Lista completa delle frequenze 802.11b .......................................... 42

Figura 1.19 – I tre canali non sovrapposti in 802.11 b/g ....................................... 43

Figura 1.20 – Caratteristiche degli standard fisici IEEE 802.11 ............................ 45

Figura 1.21 – Modulazione OFDM ........................................................................ 46

Figura 2.1 – Coperture omnidirezionali e settoriali dei sensori di prossimità ....... 56

Figura 2.2 – Circular Lateration in 2D ................................................................... 57

Figura 2.3 – Circular Lateration in 3D ................................................................... 59

Figura 2.4 – Hyperbolic Lateration ........................................................................ 61

Indice delle figure

6

Figura 2.5 – Principio di funzionamento della tecnica AoA .................................. 61

Figura 2.6 – Misurazione del tempo di propagazione ............................................ 62

Figura 2.7 – Confronto di fase (segnali analogici) ................................................. 62

Figura 2.8 – Confronto di fase (segnali numerici) ................................................. 63

Figura 2.9 – Fenomeni che condizionano la tecnica di Scene Analysis ................ 70

Figura 2.10 – Infrastruttura di riferimento RADAR .............................................. 72

Figura 2.11 – Elementi di alto livello dei sistemi di posizionamento Ekahau ....... 73

Figura 2.12 – Tag T201 prodotti da Ekahau .......................................................... 74

Figura 2.13 – Tag T2 di AeroScout® ..................................................................... 76

Figura 2.14 – Un AeroScout® Location Receiver .................................................. 77

Figura 2.12 – Cisco 2700 Wireless Location Appliance........................................ 78

Figura 3.1 – Schema semplificato di un filtro di Kalman ...................................... 88

Figura 3.2 – Architettura del neurone artificiale .................................................... 91

Figura 3.3 – Architettura tipica di una rete winner-take-all ................................... 95

Figura 3.4 – Architettura tipica di una rete SOM................................................... 97

Figura 4.1 – Schermata Mappa dell’applicazione Campionatura ........................ 102

Figura 4.2 – Schermata Opzioni dell’applicazione Campionatura ...................... 103

Figura 4.3 – Schermata Menu dell’applicazione Campionatura .......................... 104

Figura 4.4 – Schermata Visualizza Mappa dell’applicazione DimmiMuseo ....... 105

Figura 4.5 – Schermata Menu dell’applicazione DimmiMuseo .......................... 106

Figura 4.6 – Topologia della rete Wi-Fi utilizzata per la localizzazione ............. 107

Figura 4.7 – Applicazione di gestione delle mappe ............................................. 108

Figura 4.8 – Mappa della sede a Roma di Thera S.r.l. ......................................... 108

Figura 4.9 – Posizioni utilizzate nella fase di test ................................................ 110

Figura 4.10 – Schema funzionale della localizzazione Wi-Fi.............................. 111

Figura 4.11 – Prestazioni algoritmo NNSS .......................................................... 113

Figura 4.12 – Prestazioni metodo probabilistico (istogramma) ........................... 114

Figura 4.13 – Prestazioni metodo probabilistico (fdp Gaussiana) ....................... 115

Figura 4.14 – Prestazioni metodo del centroide ................................................... 116

Figura 4.15 – Prestazioni metodo del centroide (modificato) .............................. 117

Indice delle figure

7

Figura 5.1 – Interazione del campo e.m. con la struttura corporea umana .......... 123

Figura 5.2 – Livello di penetrazione em in funzione della frequenza .................. 124

Figura 5.3 – Effetti legati a aperture e fori ........................................................... 125

Figura 5.4 – Andamento qualitativo di un campo e.m. in ambiente indoor ......... 125

Figura 5.5 – Potenza ricevuta dal WM al variare della distanza .......................... 129

Figura 5.6 – Andamenti di potenza per i punti relativi alle SALA 4 dall’AP5.... 131

Figura 5.7 – Diagramma di flusso della rete neurale ........................................... 136

Figura 5.8 – Rete neurale ..................................................................................... 137

Figura 5.9 – Prestazioni della soluzione proposta ................................................ 139

Figura 5.10 – Effetti sulla stima al variare del numero di campioni .................... 140

Figura 5.11 – Effetti sulla stima al variare del numero di AP.............................. 141

Figura 5.12 – Prestazioni di sistemi di localizzazione indoor .............................. 142

Figura 5.13 – Facciata principale del Museo Civico di Albano Laziale .............. 143

Introduzione

8

Introduzione

La recente crescita di interesse verso applicazioni context\location aware (tali cioè

da sfruttare informazioni circa la posizione dell’utente all’interno dell’ambiente

circostante in modo da poter fornire servizi aggiuntivi) ha portato allo sviluppo di

numerose tecniche volte a fornire localizzazione delle utenze mobili all’interno di

spazi chiusi. Possibili applicazioni in questo senso possono andare dalla

disseminazione automatica di informazioni in relazione alla posizione dell’utente,

tanto all’aperto (si pensi a servizi di informazioni circa locali o attività

commerciali nelle vicinanze dell’utente o a informazioni di navigazione

all’interno di vasti spazi tipo fiere, ecc…), quanto in spazi chiusi (in ambiente

ospedaliero un sistema in grado di identificare la posizione del medico in

relazione alla dislocazione dei pazienti può fornire online la cartella medica del

paziente stesso). Una varietà di sistemi di posizionamento sono stati disegnati al

fine di determinare e inseguire automaticamente la posizione di un utente in

movimento. Una possibile classificazione è quella riportata in Figura 1.

Figura 1 – Classificazione delle tecniche di posizionamento

Attualmente la localizzazione outdoor di tipo assoluto (in relazione cioè alle

coordinate latitudinali e longitudinali terrestri, e non in relazione all’ambiente

circostante) viene tipicamente realizzata mediante il sistema Global Positioning

Introduzione

9

System (GPS). Un ricevitore GPS calcola la posizione in termini di latitudine,

longitudine ed elevazione misurando la sua distanza da almeno 4 satelliti la cui

orbita è supposta nota. La distanza da ciascun satellite è stimata misurando il

ritardo di trasmissione del collegamento tra il ricevitore e il satellite stesso. Tale

sistema presenta un’accuratezza di circa 10 metri ed è riconosciuto come standard

“de facto” in termini di navigazione outdoor. Per applicazioni di posizionamento

indoor, il GPS risulta scarsamente efficiente, tanto a causa della insufficiente

accuratezza, quanto a causa del fatto che per un corretto funzionamento richiede

linea di visibilità nel collegamento tra il ricevitore ed almeno tre satelliti.

Per ovviare al problema della localizzazione in ambienti chiusi risulta

particolarmente attrattiva l’idea di dotare di servizi di localizzazione le reti in area

locale senza fili (WLAN). In particolare, la maggior parte del lavoro di ricerca in

questo campo presente in letteratura, riguarda lo standard IEEE 802.11 ed in

particolare la release b (nota commercialmente con la denominazione Wi-Fi),

stante l’enorme penetrazione del mercato di tale tecnologia. I problemi tecnici

relativi a tale implementazione risiedono nella particolare complessità del canale,

caratterizzato da una forte presenza di multipath. A differenza dell’ambiente

outdoor, infatti, le condizioni propagative in spazi chiusi presentano complessità

maggiori a causa del maggior numero di cammini multipli, che collegano le

antenne in trasmissione e in ricezione dei vari apparati, e del maggior numero di

ostacoli presenti nell’ambiente di propagazione. Oltre agli effetti distorcenti

dovuti al fenomeno dei cammini multipli, è oltretutto necessario tenere conto delle

caratteristiche dissipative del corpo umano, che possono incidere in maniera non

trascurabile (soprattutto a particolari frequenze quale ad esempio la banda ISM

intorno a 2,4 GHz propria dello standard IEEE 802.11b) sull’attenuazione dei

segnali in gioco. Un esempio di un’applicazione context\location aware indoor,

potrebbe essere una guida museale, progettata in maniera che ogni visitatore,

attraverso l’utilizzo di un dispositivo portatile (smartphone, Personal Digital

Assistant, PlayStation Portable, riproduttori MP3, ecc…), dotato di scheda Wi-Fi,

possa conoscere la propria ubicazione all’interno del museo. Per ottenere tale

informazione, esso deve essere coperto da una rete Wi-Fi (situazione che

Introduzione

10

attualmente si registra in molti casi) e nel dispositivo portatile deve essere

installato un particolare software che si occuperà di determinare la posizione

dell’utente sfruttando l’informazione scambiata tra il dispositivo portatile e la rete.

Una volta determinata la posizione, la rete è in grado di inviare al terminale

contenuti multimediali sull’opera d’arte che si trova in quella posizione. Inoltre, il

visitatore è adesso in grado di conoscere informazioni più generali, quali

ubicazioni di: bagni, scale, uscite, uffici, ecc… ed infine, mediante servizi di

messaggistica, interagire con altri utenti o con l’amministratore della rete. In tali

condizioni, anche l’amministratore di rete è in grado di avere traccia degli utenti,

interagire con loro, costruire statistiche sulle preferenze delle opere d’arte da parte

del pubblico, ecc… Il presente progetto di tesi nasce proprio da quest’ultimo

esempio, e su proposta dall’azienda Thera S.r.l. si propone di sviluppare un

sistema di localizzazione Wi-Fi indoor, attraverso il quale offrire servizi di

Location-based Services (LBS). Infatti, Thera S.r.l. vuole lanciare sul mercato una

guida museale (DimmiMuseo), basata su un sistema di localizzazione Wi-Fi, che

per le sue caratteristiche potrà essere utilizzata anche in contesti diversi dai musei,

quali ad esempio uffici, ospedali, fiera, ecc… I sistemi di localizzazione Wi-Fi

indoor, infatti, sono di grande interesse in quanto l’infrastruttura necessaria per la

loro implementazione è poco costosa al contrario di altre tecnologie (sensori,

ultrasuoni, ecc…) che per gli alti costi di implementazione non hanno ancora

avuto successo. Lo stato dell’arte dei sistemi di localizzazione Wi-Fi indoor è

ancora in via di sviluppo e di sperimentazione, tuttavia esistono alcune soluzioni

commerciali orientate al tracking in ambiente chiusi. Infatti, aziende come

Ekahau e Cisco stanno già commercializzando sistemi di localizzazione che

lavorano con infrastruttura Wi-Fi, mentre, altri sistemi, come RADAR (Microsoft)

sono ancora in fase di sperimentazione.

Lo scopo di questa tesi consiste nell’analizzare le caratteristiche delle tecniche di

posizionamento (capitolo 2) attualmente presenti in letteratura per decidere, sulla

base dei dati a nostra disposizione, quale sarà la tecnica di posizionamento da

adottare. Una volta scelta la tecnica, occorrerà studiare i diversi metodi e algoritmi

in grado di implementarla (vedi capitolo 3) analizzando il loro comportamento e

Introduzione

11

le loro limitazioni. Il passo successivo (capitolo 4 e 5) sarà l’implementazione

software e i test dei metodi studiati che permetteranno di esaminare le prestazioni

dell’algoritmo di localizzazione in un ambiente realistico. In tal modo sarà

possibile proporre modifiche necessarie all’aumento delle performances. In

funzione dei risultati ottenuti, sarà quindi possibile scegliere il metodo che

restituirà le migliori prestazioni, e questo costituirà il cuore del sistema di

localizzazione finale.

Capitolo 1. Le reti locali Wireless

12

Capitolo 1

Le reti locali Wireless

La prima sperimentazione di network wireless si ebbe nel 1971 e fu sviluppata

dall’Università delle Hawaii, dove era necessario collegare gli elaboratori di

quattro isole senza utilizzare linee telefoniche, ma la loro diffusione si ebbe a

partire dagli anni ’80, quando l’idea di condividere dati tra computer diventava

sempre più fondamentale. La prima tecnologia utilizzata era basata sui

ricetrasmettitori a raggi infrarossi, ma, visto la grave limitazione di questi

nell’attraversare la maggior parte dei materiali, non ebbe un grande sviluppo. Il

mercato richiedeva una tecnologia pulita, con la possibilità di attraversare ostacoli

e di essere utilizzata in qualsiasi ambiente di lavoro: ecco che nacque una

tecnologia wireless basata su segnali radio. Questo tipo di reti cominciarono a

prendere piede agli inizi degli anni ’90, quando la capacità di calcolo dei

processori risultò sufficiente a gestire la ricetrasmissione via radio. Una prima

implementazione, costosa e proprietaria, non permetteva di comunicare con

nessun altro sistema; difatti le reti non compatibili si dimostrarono un fallimento.

Nel 1997 l’attenzione si focalizzò sul neonato standard creato dagli ingegneri

dell’istituto Institute of Electrical and Electronics Engineers (IEEE), appunto

l’ 802.11. Lo scopo iniziale di questo progetto era quello di creare uno standard

globale per reti operanti in una banda libera, senza la necessità di utilizzare alcuna

licenza. Gli ingegneri si trovarono ad affrontare diverse problematiche riguardo

gli apparati del nuovo standard, tra le quali, per esempio, come avrebbero dovuto

interoperare tra loro; come renderne l’impiego uguale in ogni parte del mondo;

come renderli utilizzabili non solo in ambienti interni. Far diventare lo standard

IEEE 802.11 globale richiedeva l’utilizzo di una frequenza libera da qualsiasi

vincolo burocratico, e per questo motivo venne scelta la frequenza intorno ai

2,4GHz, una banda senza licenza riservata per impieghi industriali, scientifici e

medici. Supportando il funzionamento nella banda ed adeguando i livelli di

Capitolo 1. Wireless Local Area Network

13

potenza consentiti in base alle regolamentazioni nazionali, è stato possibile

sviluppare uno standard per reti locali wireless che può essere impiegato in tutto il

mondo. L’ambiente in cui doveva essere localizzata una LAN senza fili non

doveva essere il solo ufficio. Lo standard avrebbe permesso di utilizzare la

tecnologia wireless non solo in grandi realtà come magazzini, negozi, ospedali e

grossi edifici, ma anche in ampi spazi aperti come parcheggi, campus universitari

e perfino nelle aree di stoccaggio merci.

Una delle applicazioni più frequenti in questo ambito è il cosiddetto Mobile

Internet, ossia la possibilità di accedere ad Internet tramite il proprio PC portatile,

palmare, telefono cellulare, ecc…senza l’utilizzo di cavi. Oggi molte

organizzazioni pubbliche o private offrono, grazie alla presenza di punti di

accesso nei propri siti, la possibilità di entrare in rete. Quando l’utente si trova

all’interno dell’area di copertura di un access point con il proprio terminale

wireless, può spedire una mail e navigare sul web, anche camminando. I sistemi

wireless presentano notevoli vantaggi rispetto a quelli fissi: la mobilità, la

connessione ad hoc, la copertura di aree difficili da cablare, tanto per citarne

alcuni.

In questo capitolo viene presentata una panoramica sulle WLAN comprendente

tipologie di dispositivi, aree applicative, categorie, bande di frequenze,

regolamentazione nazionale, requisiti, vantaggi e problematiche. Inoltre, viene

descritto quello che è lo standard IEEE 802.11.

1.1 Wireless Local Area Network

Una 802.11 WLAN è basata su una architettura cellulare in cui l’area nella quale

deve essere distribuito il servizio viene suddivisa in celle proprio come accade nei

sistemi di distribuzione per servizi di telefonia. Ciascuna cella (chiamata Basic

Service Set o più semplicemente BSS) è controllata da una stazione base

denominata Access Point (AP). Gli AP sono bridge che collegano la sottorete

wireless con quella cablata, mentre i Wireless Terminal (WT) sono i dispositivi


14

che usufruiscono dei servizi di rete. Gli AP possono essere implementati in

hardware (dispositivi dedicati), ma anche in software, appoggiandosi, ad esempio,

ad un PC o notebook, dotato sia dell’interfaccia wireless, sia di una scheda

Ethernet. Un singolo AP può servire un numero limitato di utenti (tra i 15 e i 50 a

seconda del servizio richiesto) e può coprire, a seconda della sua posizione, della

topologia della struttura e delle caratteristiche dell’ambiente, un’area che va dai

30 ai 300 metri. L’AP (o l’antenna connessa ad esso) è montato solitamente in

alto, ma può essere montato in qualsiasi posizione, fino al raggiungimento della

copertura radio desiderata. I WT possono essere di qualunque tipo: notebook,

Personal Digital Assistant (PDA), cellulari, ecc… ovvero, tutti quegli apparecchi

che si interfacciano allo standard IEEE 802.11. In genere i WT a cui si farà

riferimento saranno smartphone, che per funzionare in un sistema WLAN

necessitano di una scheda wireless che permette all’utente di accedere ad ulteriori

servizi in modo del tutto simile a quello che si ha con una rete cablata.

Figura 1.1 – Architettura classica di una rete WLAN.


15

Per le reti locali wireless possono essere individuate sostanzialmente quattro aree

applicative:

• Estensione di reti locali. Inizialmente le reti locali wireless nascono per

sostituire le LAN cablate eliminando i costi di cablaggio e installazione e

favorendo la rilocazione e altre modifiche alla rete. Infatti, in molti

ambienti le WLAN risolvono problemi quali i casi di strutture: con grandi

aree coperte, edifici storici (in cui è proibito intervenire nei muri), piccoli

uffici (in cui l’installazione di reti cablate non si rivela economica), ecc….

Nella maggior parte di questi casi si avrà una rete locale cablata di

supporto ai server con alcune workstation fisse;

• Interconnessione di edifici. Le tecnologie wireless connettono reti locali

distinte situate in edifici separati, che a loro volta possono utilizzare reti

locali cablate o non. In questo caso viene utilizzato un link wireless punto-

punto tra i due edifici (in particolare, tra bridge o router) che non

rappresenta di per sé una rete locale, ma viene comunque incluso nelle

possibili aree applicative delle WLAN;

• Accesso nomadico. Si tratta della situazione in cui l’access point di una

rete locale è connesso via radio ad un terminale mobile dotato di scheda

wireless. Questa topologia è utile in ambienti estesi quali un campus

universitario o un’azienda costituita da più edifici, ad esempio per

trasferire dati dal terminale al server aziendale;

• Rete ad hoc. Si tratta di una rete peer to peer configurata temporaneamente

per rispondere a determinate esigenze, ad esempio nel caso di un convegno

in cui i partecipanti vogliono scambiarsi dati senza la presenza di access

point.

Sulla base del metodo di trasmissione utilizzato possiamo distinguere le WLAN in

infrarossi (IR) e onde radio . La tecnologia ottica ad IR presenta alcuni aspetti

positivi rispetto alle onde radio poiché il suo spettro illimitato è libero, ossia non

regolato da licenze, e consente di raggiungere un elevato bit rate. Le reti basate su


16

questa tecnologia sono semplici, economiche e relativamente sicure contro le

intercettazioni; inoltre, dal momento che il raggio non attraversa le pareti, si può

costruire una rete ad IR in ogni stanza di un edificio senza alcuna interferenza.

Tuttavia la luce solare ed il calore possono attenuare e deviare il raggio IR. Per

ovviare a questo problema occorre aumentare la potenza dei trasmettitori, ma tale

incremento è limitato da problemi di sicurezza per la vista e da un eccessivo

consumo di energia elettrica. Le principali tecniche trasmissive per gli IR sono:

• raggio ad infrarosso diretto: viene usata per creare link punto-punto, ad

esempio per l’interconnessione di edifici tramite bridge o router;

• diffusione omnidirezionale: un’unica stazione base (posta in genere sul

soffitto e in linea ottica con le altre) agisce da repeater trasmettendo un

segnale broadcast in ogni direzione, mentre i ricetrasmettitori dei client

emettono un raggio direttivo verso il ripetitore;

• configurazione diffusa: il segnale inviato da tutti i trasmettitori viene

riflesso dal soffitto in tutte le direzioni e quindi captato da tutte le stazioni.

Le WLAN ad onde radio, invece, operano nello spettro compreso tra 3 kHz e 300

GHz. La tecnologia ad onde radio è la più diffusa in ambiente wireless e consente,

per ogni cella, di implementare la modalità ad hoc o quella ad infrastruttura § 2.2.

In Europa le frequenze portanti per WLAN ad onde radio sono 2,4 GHz e 5 GHz.

Le reti basate su questa tecnologia si dividono in due categorie, a dispersione

dello spettro o a banda stretta, a seconda dell’utilizzo o meno delle tecniche

Spread Spectrum. Le versioni successive dello standard iniziale IEEE 802.11

utilizzano solamente tecnologie ad onde radio, in particolare a dispersione dello

spettro.

La maggior parte dei dispositivi wireless opera alle frequenze delle bande

Industrial Scientific Medical (ISM), ovvero una serie di bande di frequenza

attorno a 2,4 GHz destinate alle applicazioni industriali, scientifiche e mediche e

che possono essere utilizzate, liberamente, senza la richiesta di licenza. Inoltre, le

bande ISM supportano anche telefoni cordless, forni a microonde, terminali


17

Bluetooth, dispositivi per il controllo dei neonati, sistemi d’allarme, radiocomandi

per cancelli automatici e altri servizi senza fili (con conseguenti problemi di

interferenza). Negli USA sono libere le seguenti bande: 902-928 MHz, 2.4-2.4835

GHz, 5.15-5.35 e 5.725-5.825 GHz. In Giappone e in Europa è invece libera

solamente la seconda banda tra le precedenti. I 300 MHz che costituiscono la

banda a 5 GHz sono noti anche come Unlicensed National Information

Infrastructure (UNII). A differenza delle bande ISM classiche, queste frequenze

sono state destinate negli USA dalla Federal Communications Commission (FCC)

solo alle comunicazioni di tipo WLAN. Sebbene si possano verificare interferenze

da parte di altri utenti WLAN autorizzati, per legge non devono essere presenti

altre interferenze. La banda ISM a 2,4 GHz è nettamente più utilizzata di quella a

5 GHz. Infatti, al crescere della frequenza aumentano gli effetti di riflessione e

assorbimento delle onde elettromagnetiche, l’attenuazione dello spazio libero e il

livello di rumore: conseguenza inevitabile è la diminuzione delle distanze

copribili.

Per quanto riguarda l’Italia, nell’Ottobre del 2005 il decreto Landolfi ha esteso la

regolamentazione dello standard IEEE 802.11 a tutto il territorio nazionale,

liberalizzando il Wi-Fi, fino ad allora relegato solo ad aree pubbliche quali

stazioni ed aeroporti, e permettendone l’utilizzo ovunque, in modo da offrire

servizi di collegamento ad abitazioni ed uffici. In questo modo è stato ampliato il

precedente decreto Gasparri , in vigore dal Maggio del 2003, che autorizzava

l’uso del Wi-Fi esclusivamente in locali aperti al pubblico e in aree confinate a

frequentazione pubblica. Il provvedimento firmato da Gasparri stabiliva inoltre

che gli operatori interessati a realizzare WLAN pubbliche dovevano richiedere

un’autorizzazione al Ministero delle Comunicazioni ed usare la potenza di

trasmissione prescritta con Equivalent Isotropically Radiated Power (EIRP)

massimo di 100 mW nella banda a 2,4 GHz, senza arrecare interferenze ad altri

servizi.

Quindi una WLAN deve rispondere agli stessi requisiti di qualsiasi rete locale:

una elevata capacità, la possibilità di coprire brevi distanze, una piena connettività


18

tra le stazioni connesse e una funzionalità di broadcast. Inoltre esistono requisiti

specifici dell'ambiente a rete locale wireless, quali:

• Produttività: il protocollo Medium Access Control (MAC) deve fare un

utilizzo il più efficiente possibile del mezzo wireless, in modo da

ottimizzare la capacità del sistema;

• Connessione alla rete fissa: spesso è necessario prevedere

un'interconnessione con le stazioni della rete locale fissa. Per le reti locali

wireless ciò è possibile utilizzando moduli di controllo che si connettono

ad entrambi i tipi di rete locale;

• Area di servizio: una tipica area di copertura per una WLAN ha un

diametro di 100-300 metri nello spazio libero, ma negli ambienti chiusi

questo aspetto è fortemente limitato da ostacoli quali rumore ambientale,

pareti, assenza di visibilità ottica;

• Solidità e sicurezza della trasmissione: se non realizzata accuratamente,

una WLAN può essere soggetta ad interferenze e intercettazioni. Il

progetto di una rete locale wireless deve consentire trasmissioni affidabili

anche in un ambiente rumoroso e deve offrire un certo livello di sicurezza

contro le intercettazioni;

• Handover: secondo questo concetto la sessione non cade durante lo

spostamento di un wireless terminal. Infatti, se un utente mobile si sposta

con il proprio terminale in una zona non più coperta da un access point, la

presenza di un altro access point, posto a distanza strategica dal

precedente, consente all'utente di proseguire le proprie operazioni;

• Configurazione dinamica: gli aspetti di indirizzamento MAC e di gestione

della rete locale dovranno consentire l'aggiunta, la cancellazione e la

rilocazione dinamica e automatica dei terminali senza introdurre problemi

per gli altri utenti;

• Alimentazione e porta di rete: sono necessarie nei siti in cui vengono

installati gli access point.


19

Se le reti locali wireless rispettano tali requisiti presentano una serie di vantaggi

peculiari di seguito elencati:

• Libertà di movimento: si può accedere in tempo reale alle informazioni

presenti sulla Intranet, in qualsiasi momento, all'interno di uno o più

edifici, senza essere collegati tramite cavi; ciò può essere particolarmente

utile per applicazioni specifiche che richiedono frequenti spostamenti;

• Facilità di installazione: l'installazione di una WLAN è facile e veloce

grazie all’assenza del cablaggio, per cui è adatta per allestire sedi

temporanee (ad esempio aule tecnologiche non permanenti e sale

espositive) in modo rapido;

• Connessioni in situazioni particolari: le reti senza fili possono risolvere il

problema del cablaggio nei luoghi in cui è opportuno evitare qualsiasi

installazione fissa (fori nei muri, canaline, ecc...), come nel caso di edifici

ad alto impatto ambientale, ad esempio palazzi storici;

• Convenienza: l'implementazione di una WLAN consente di risparmiare sui

costi del cablaggio, dell'installazione muraria e della manutenzione di una

rete fisica, nonostante in genere gli investimenti iniziali siano superiori

rispetto al caso di realizzazione di una rete wired;

• Scalabilità: per soddisfare le diverse esigenze di applicazioni particolari, è

possibile implementare le WLAN in diverse topologie con configurazioni

facilmente modificabili.

Nonostante i vantaggi riportati nel precedente paragrafo, si deve fare i conti con

alcune problematiche presenti in fase sia di progetto sia di utilizzo di una WLAN,

quali:

• Inquinamento elettromagnetico: nonostante la bassa potenza associata al

segnale radio, l'elevata frequenza di lavoro (siamo nel campo delle

microonde) non elimina completamente questo problema;

Capitolo 1. Standard IEEE 802.11

20

• Velocità di trasmissione effettiva: questa si discosta sensibilmente dal

valore teorico massimo a seconda dell'intensità del segnale e del traffico di

rete;

• Ostacoli alle onde radio: la presenza di elementi che ostacolano il corretto

funzionamento di una rete locale senza fili (rumore ambientale, assenza di

visibilità ottica, pareti, metalli, ecc…) comporta la necessità di

ridimensionare la stessa dopo aver effettuato prove e misurazioni di

campo;

• Interferenze con altri dispositivi: la banda di frequenze nell’intorno di 2,4

GHz è molto affollata, per cui si possono avere problemi di interferenza

con altri apparati quali terminali Bluetooth, forni a microonde, telefoni

cordless, apparecchiature scientifiche e mediche;

• Sicurezza: le reti wireless possono risultare vulnerabili rispetto ad

intrusioni non autorizzate nel caso in cui non vengano prese opportune

precauzioni;

• Imprevedibilità rispetto al corretto funzionamento: il rumore ambientale e

le interferenze elettromagnetiche sono aspetti determinanti per il

funzionamento della rete wireless, per cui un loro incremento rende

necessarie nuove misurazioni e una conseguente ridisposizione degli

access point;

• Costi di investimento: questi sono naturalmente legati alle necessità

infrastrutturali della WLAN. Sebbene l'acquisto di schede di rete wireless

ed access point sia accessibile a tutti, i costi per l'implementazione di una

WLAN crescono in relazione all'inadeguatezza della rete fissa alla quale

gli access point sono collegati.

1.2 Standard IEEE 802.11

L’IEEE, con il gruppo 802, si occupa di standardizzare i primi due livelli (fisico e

di collegamento dati) del modello di riferimento Open System Interconnection

(OSI) per quanto riguarda reti locali e metropolitane. IEEE 802 introduce l’idea

Capitolo 1. Standard IEEE 802.11

21

che LAN e MAN debbano fornire un'interfaccia unificata verso il terzo livello

OSI (livello di rete), pur utilizzando tecnologie trasmissive differenziate. Per fare

ciò è stato diviso il secondo livello (Data Link) in due sottolivelli: Logical Link

Control (LLC) e Media Access Control (MAC). Il sottolivello LLC è comune a

tutte le LAN e descritto nell'apposito IEEE 802.2 ,mentre il MAC è peculiare di

ciascuna LAN, così come il livello fisico a cui è strettamente associato. In questo

modo è possibile connettere una LAN wired con una WLAN 802.11 ed usufruire

di servizi analoghi. Dato che IEEE rilascia solo un insieme di specifiche, ma non

prevede nessun test né certificazione per riconoscere che un prodotto rispetta le

specifiche stesse, è stata creata l’associazione Wi-Fi Alliance per certificare

l’interoperabilità dei prodotti (tramite il logo Wi-Fi) e per diffondere le reti

wireless. In essa vi sono praticamente tutti i costruttori di componenti per schede e

dispositivi Wi-Fi.

Figura 1.2 – Alcuni standard del gruppo IEEE 802.

Capitolo 1. Topologie di WLAN

22

Nella figura 1.2 sono riportati alcuni degli standard del gruppo IEEE 802 e tra

questi 802.11 si occupa delle reti locali wireless. La prima versione dello standard

IEEE 802.11, presentata nel 1997 e nota come legacy, dettava le specifiche a

livello fisico e MAC per la realizzazione di WLAN. Questa prima versione

consentiva velocità comprese tra 1 e 2 Mb/s utilizzando i raggi infrarossi o le onde

radio nella banda 2,4 GHz per la trasmissione del segnale. La tecnologia

infrarosso venne eliminata nelle versioni successive, dato il loro scarso successo.

La figura 1.3 evidenzia come lo standard 802.11 si occupi solamente del livello

fisico e del sottolivello MAC definiti nel modello OSI; il sottolivello LLC è

standardizzato (802.2), mentre i livelli superiori sono indipendenti dalle specifiche

dello standard.

Figura 1.3 – Modello OSI e standard 802.11.

In questa sezione vengono illustrate le specifiche e le caratteristiche dello standard

IEEE 802.11, mentre nella successiva verranno descritte le sue evoluzioni.

1.2.1 Topologie di WLAN

Per topologia di una WLAN si intende il modo in cui i dispositivi wireless sono

disposti geograficamente e con quale principio avviene lo scambio di dati. In una

WLAN possiamo avere le seguenti strutture: IBSS, BSS e ESS.

L’ Independent Basic Service Set (IBSS), denominata anche configurazione in

modalità ad hoc, permette di collegare più terminali senza l’utilizzo di nessun

hardware all’infuori delle schede wireless. In un’installazione di questo tipo le


23

stazioni comunicano direttamente con altre che si trovano nel range di copertura

consentito dalla propria scheda.

Figura 1.4 – Independent Basic Service Set.

La topologia Basic Service Set (BSS) utilizza un access point con le funzioni di

stazione base e bridge tra terminali wireless, che si trovano nel range di copertura

dell’access point, e quelli fissi. Infatti, un access point non è altro che un

apparecchio radio dotato di un’interfaccia cablata con la rete e del software di

bridging che permette lo scambio di dati tra due tecnologie completamente

diverse; esso rappresenta il cervello di una rete wireless, fornisce sincronizzazione

e coordinazione e può compiere diversi compiti a seconda del contesto di utilizzo.

Oltre a svolgere la funzione di bridging, l’AP, con un software opportuno, può

operare in modo analogo ad un gateway, permettendo così di far comunicare la

rete wireless ad una connessione Internet. La topologia BSS rappresenta in

sostanza una rete locale wireless monocella, dal momento che tutti i terminali si

trovano all’interno dell’area di copertura di un singolo access point.

Figura 1.5 – Basic Service Set.


24

Lo standard 802.11 prevede la possibilità di collegare due o più BSS connesse alla

stessa rete fissa, in modo da formare un'unica grande area denominata Exended

Service Set (ESS). In questo caso, quando i dati vengono inviati verso un

destinatario che si trova in una BSS diversa da quella del mittente, essi

attraversano il Distribution System (DS), solitamente realizzato tramite la

tradizionale rete Ethernet. Il DS permette di collegare diversi access point allo

switch di una LAN Ethernet, ad un router per la connessione Internet, oppure di

collegare le varie BSS. La topologia ESS è nota anche come configurazione in

modalità ad infrastruttura, in contrapposizione alla modalità ad hoc definita dalla

IBSS. La tipologia ESSS rappresenta una rete locale wireless multicella in cui

ciascun access point, operando su un canale differente, supporta un certo numero

di terminali all’interno del proprio range di copertura.

In una configurazione di questo tipo è fondamentale la procedura di handover

grazie alla quale un utente si sposta da una cella (BSS) a quella adiacente senza

avere nessuna interruzione del servizio, in maniera del tutto analoga a quanto

accade per le reti cellulari. Quando il rapporto Signal Noise Ratio (SNR) relativo

al terminale mobile scende al di sotto di una certa soglia, non c’è più

collegamento con l’AP e a questo punto avviene l'handover, per cui il terminale

instaura un nuovo link con un altro AP in modo che la sessione non cada.

Figura 1.6 – Exended Service Set.

Capitolo 1. Livello Fisico

25

In sostanza IEEE 802.11 consente la scelta automatica dell’access point in

funzione della potenza del segnale e del traffico di rete, e non della distanza tra

stazione base e terminale.

Figura 1.7 – Handover in WLAN.

Si sottolinea che il concetto di handover si discosta da quello di roaming: infatti,

al variare della posizione fisica del terminale, nel secondo caso il provider che

fornisce il servizio cambia, mentre nel primo è sempre lo stesso.

1.2.2 Livello fisico

Lo standard 802.11 prevede tre possibili tecniche di trasmissione: DSSS e FHSS

nella banda ISM intorno a 2,4 GHz; Infrared con lunghezza d’onda tra 850 e 950

nm. Le prime due possibilità sfruttano tecniche Spread Spectrum, mentre la terza

verrà trascurata in questa trattazione, data la sua eliminazione nel livello fisico

delle evoluzioni dello standard. In ogni caso la velocità massima è pari a 1 o 2

Mb/s.

A causa soprattutto delle scarse prestazioni, successivamente l’IEEE emanò i

seguenti standard (tra parentesi l’anno di ratificazione):


26

• IEEE 802.11b (1999): denominato anche Wireless-Fidelity (Wi-Fi), questo

protocollo consente una velocità di trasmissione massima pari a 11 Mb/s

utilizzando le frequenze nell’intorno di 2,4 GHz con tecnica di

trasmissione DSSS;

• IEEE 802.11a (1999): in questo caso il bit rate arriva fino a 54 Mb/s, ma

utilizzando la banda a 5 GHz e la modulazione OFDM;

• IEEE 802.11g (2003): utilizza le stesse frequenze di Wi-Fi, quindi risulta

ad esso compatibile, e fornisce una banda teorica di 54 Mbit/s con

l’utilizzo della modulazione OFDM.

Nelle tecniche Spread Spectrum il concetto base della dispersione dello spettro

radio consiste nell’utilizzare una maggiore ampiezza di banda rispetto a quella

necessaria per la trasmissione dell’informazioni. L’utilizzo di queste tecniche, al

di là di un apparente spreco di banda, comporta vantaggi importanti quali:

maggiori immunità rispetto alla distorsione e alle intercettazioni, oltre ad una

minore sensibilità alle interferenze e ai disturbi.

L'espansione dello spettro può essere ottenuta principalmente con due tecniche di

modulazione distinte: Frequency Hopping Spread Spectrum (FHSS) e Direct

Sequence Spread Spectrum (DSSS).

Figura 1.8 – Caratteristiche fisiche degli standard del gruppo 802.11.

Per quanto riguarda la tecnica FHSS, la banda a disposizione viene suddivisa in

un certo numero di canali, ognuno dei quali è a banda relativamente stretta, di

ampiezza corrispondente a quella del segnale originale. Il trasmettitore opera su


27

un canale alla volta per un intervallo fisso di tempo, dunque il segnale è trasmesso

soltanto da una frequenza all’altra. La sequenza di canali utilizzati, ovvero la serie

di salti, è dettata da un codice di hopping; sia trasmettitore sia ricevitore devono

utilizzare e conoscere la stessa sequenza di salti in modo tale da essere

sincronizzati. Quindi il segnale è ancora a banda stretta (per un dato intervallo di

tempo è trasmesso su una singola portante) ma si distribuisce su una banda più

larga. La sequenza è unica per ogni coppia trasmettitore/ricevitore ed è tale da

minimizzare la probabilità che due mittenti utilizzino simultaneamente lo stesso

canale. Così FHSS incrementa la sicurezza rendendo il segnale non intelligibile

per gli intercettatori, poiché ad ogni intervallo (breve) di tempo si opera su un

canale diverso; quindi i disturbatori colpiscono solo pochi bit su una certa

frequenza. Inoltre aumenta la reiezione al multipath, essendo questo un fenomeno

selettivo in frequenza. In IEEE 802.11 la banda a 2,4 GHz è suddivisa in canali da

1 MHz ciascuno. Questa tecnica di tipo spread spectrum consente una velocità

massima di 2 Mb/s, perciò è stata abbandonata nelle versioni successive dello

standard, ad eccezione di 802.11a in cui comunque la modulazione OFDM

permette un bit rate nettamente maggiore.

Nel caso di modulazione DSSS, ogni bit del segnale originario è rappresentato da

un numero maggiore di bit del segnale effettivamente trasmesso. Questo risultato

può essere ottenuto utilizzando uno spreading code che disperde il segnale su una

banda di frequenze più larga, consentendo tra l’altro la ricezione di segnali deboli.

Il fattore di allargamento dipende in modo direttamente proporzionale dal numero

di bit, detti chip, della sequenza pseudocasuale di spreading. In buona sostanza, la

portante a radiofrequenza viene moltiplicata direttamente con il codice di

spreading tramite l’operatore XOR. Il ricevitore conosce lo stesso codice e in tal

modo può effettuare il despreading e riportare così la sequenza di chip nella

forma iniziale. Lo standard 802.11 specifica l’utilizzo di una particolare sequenza

ad 11 chip nota come codice di Barker.

Oltre alla dispersione del segnale, vengono impiegate anche altre tecniche di

modulazione allo scopo di codificare il segnale informativo tramite variazioni

prevedibili del segnale radio. IEEE 802.11 specifica due tipi di modulazione di

Capitolo 1. Livello MAC

28

tipo Differential Phase Shift Keying (DPSK) che rilevano la fase del segnale radio

per sistemi DSSS. La prima, Binary PSK (BPSK), rileva un’inversione a 180° del

segnale che rappresenta 0 o 1 binario: questo metodo fornisce una velocità di

trasmissione dei dati pari ad 1 Mb/s. La seconda, Quadrature PSK (QPSK), rileva

variazioni di fase di 90°: questo raddoppia la velocità di trasmissione a 2 Mb/s.

Figura 1.9 – Modulazione DSSS.

Il successivo standard 802.11b introduce la modulazione Complementary Code

Keying (CCK) ed un chipping code di 8 chip per arrivare ad un bit rate massimo

di 11 Mb/s.

1.2.3 Livello MAC

Lo standard definisce i seguenti nove servizi che devono essere forniti dalla

WLAN:

• Distribuzione: fornisce i meccanismi di trasferimento dei dati fra le

stazioni attraverso il DS; una stazione base utilizza questo servizio ogni

volta che invia frame MAC attraverso il DS verso un destinatario

appartenente ad un’altra BSS;

• Integrazione: permette il trasferimento dei dati da una stazione di una

WLAN ad una di una rete locale non IEEE 802.11;

• Associazione: mappa un terminale ad un AP, consentendo lo scambio di

dati tra i due dispositivi. Prima che il DS possa consegnare e accettare dati,


29

la stazione client deve essere associata ad un AP in base ad uno dei

seguenti modi di transizione basati sulla mobilità: nessuna transizione

(stazionaria o interna alla BSS), BSS transition (terminale che si muove da

una cella ad un’altra), ESS transition (terminale che si sposta da una BSS

di una ESS ad una BSS di un’altra ESS);

• Disassociazione: utilizzato per spezzare un’associazione esistente tra un

terminale ed un AP, questo servizio è necessario quando un client si

spegne o cambia ESS;

• Riassociazione: permette il trasferimento di associazione da un AP ad un

altro, consentendo alla stazione mobile di cambiare BSS;

• Autenticazione: fornisce un meccanismo che consente l’identificazione di

un terminale. Senza questa prova di identità, esso non può utilizzare la

WLAN per l’invio e la ricezione dei dati;

• Deautenticazione: rimuove un’autenticazione esistente, eliminando un

utente precedentemente autorizzato ed impedendogli di tornare ad

utilizzare la rete;

• Privacy: progettato per impedire che il contenuto dei messaggi venga letto

da utenti diversi dal destinatario, questo servizio include tecniche di

crittografia allo scopo di garantire riservatezza ai dati che viaggiano nella

comunicazione radio;

• Consegna: fornisce il trasferimento di frame a livello MAC fra due

stazioni.

I primi 5 servizi sono chiamati “servizi di distribuzione” e sono forniti dall’AP,

mentre i restanti costituiscono i “servizi di stazione” e sono forniti dai terminali.

I protocolli di livelli superiori del modello OSI, quale ad esempio il TCP a livello

4 (transport layer), affrontano gli errori in base a “time out” piuttosto elevati,

quindi anche il livello 2 tratta errori, in modo che gli strati superiori vedano un

canale migliore e più affidabile. Una parte dell’affidabilità consiste nei classici

concetti di acknowledgement (ACK) e ritrasmissione. Infatti, lo standard IEEE

802.11 include un protocollo per lo scambio di frame MAC quando una stazione


30

riceve un frame di dati da un’altra o invia un ACK di conferma al mittente. Se

quest’ultimo non riceve l’ACK entro un breve periodo di tempo (o perché il frame

è stato danneggiato o perché è stato danneggiato l’ACK stesso) allora il frame

viene ritrasmesso.

Il livello MAC si occupa principalmente del controllo di accesso al mezzo

condiviso (aria), utilizzando la tecnica Carrier Sense Multiple Access with

Collision Avoidance (CSMA/CA), in maniera simile, solo in parte, alla rete

Ethernet. Infatti, l’idea di base è che il mezzo (il cavo nel caso di rete fissa, l’aria

nel caso wireless) deve essere condiviso tra i vari client. Se tutti trasmettono

insieme, inviando i propri bit (sotto forma di segnale elettrico sul cavo o di onda

elettromagnetica nell’etere), si crea una collisione per cui la trasmissione non va a

buon fine. Si deve pertanto gestire o meglio evitare tale eventualità di collisione.

Un primo meccanismo è appunto il CSMA, ovvero prima della trasmissione la

stazione ascolta il mezzo per sentire se è impegnato in un’altra comunicazione; in

questo caso attende per un certo periodo prima di riprovare, altrimenti inizia a

trasmettere. A questo punto le strade dell’Ethernet e dell’802.11 si separano,

comportandosi da questo momento in avanti in modo differente. Nell’Ethernet

infatti il client trasmette così come detto quando sente il cavo libero, ma potrebbe

accadere di trasmettere contemporaneamente ad un altro client, che pure aveva

ascoltato il mezzo sentendolo libero. In tal caso si crea una collisione, che viene

rilevata da entrambi i client, i quali allora attendono un tempo casuale prima di

riprovare a trasmettere. Questo sistema prende il nome di CSMA/CD Carrier

Sense Multiple Access with Collision Detection (CSMA/CD). Tuttavia nell’etere

non è possibile rivelare la collisione, per cui un tale sistema non è applicabile ed è

così necessario averne un altro, che eviti collisioni dovute ad una contemporanea

trasmissione. Tale sistema prende il nome di Carrier Sense Multiple Access with

Collision Avoidance (CSMA/CA) e vediamo di spiegarlo analizzando un

problema tipico delle reti wireless ovvero il problema della stazione nascosta (the

hidden node problem).

Siano date tre stazioni A, B e C i cui raggi di azione sono rappresenti in figura

1.10. Supponiamo che A stia trasmettendo a B dopo aver sentito il mezzo libero;


31

se anche C vuole trasmettere a B, sente il mezzo libero e quindi invia i propri dati

verso il destinatario voluto. In questo modo sia A sia C sentono il mezzo libero e

trasmettono verso B, ma si ha una collisione che costringe entrambe le stazioni a

ritrasmettere. Per risolvere il problema della stazione nascosta, lo standard 802.11

prevede il protocollo Request To Send/Clear To Send (RTS/CTS): in questa

tecnica di rivelazione virtuale della portante, le stazioni utilizzano un four way

handshake per ottenere un accesso al canale tale da minimizzare la probabilità di

collisione da parte dell’access point.

Figura 1.10 – Il problema della stazione nascosta.

Il terminale invia un frame RTS (che comprende anche la lunghezza dei dati)

all’AP per richiedere l’utilizzo del canale; se l’AP è in grado di riceverlo, allora

risponde con un frame CTS; dopo aver ricevuto il CTS, il terminale sender può

inviare i dati; infine l’AP riscontra i byte ricevuti con messaggi ACK (uno per

ogni pacchetto). Si tenga presente che entrambi i frame RTS e CTS contengono il

tempo restante della trasmissione. Infatti, nel caso in cui la stazione A (figura

1.11) abbia già iniziato a trasmettere ogni stazione nel raggio di A o B riceve uno

o entrambi i frame e così imposta il proprio contatore di ascolto virtuale della

portante, detto Network Allocation Vector (NAV), per la durata indicata dal frame.

In buona sostanza il NAV rappresenta un contatore che viene decrementato nel

tempo fino a 0; un valore non nullo indica la presenza di una trasmissione in corso

nelle vicinanze. In conclusione, il protocollo RTS/CTS si rivela molto

vantaggioso, infatti nel caso di collisione viene perso un solo pacchetto RTS


32

anziché uno più lungo di dati, aumenta così la probabilità di trasmettere con

successo e si riduce il calo di throughput causato dalle collisioni.

Figura 1.11 – Il protocollo four way handshake.

Lo standard IEEE 802.11 prevede due modalità di algoritmo MAC:

• Distributed Coordination Function (DCF): l’accesso al mezzo è gestito

dalle stazioni in modo distribuito secondo il protocollo CSMA/CA. Questa

modalità è obbligatoria ed utilizzabile in configurazioni sia ad hoc sia

infrastructure;

• Point Coordination Function (PCF): l’AP provvede ad assegnare il canale

alle stazioni tramite un polling. Questa modalità è opzionale e,

ovviamente, implementabile solo in reti ad infrastruttura.

Prima di esaminare le due modalità di cui sopra, è utile sottolineare che lo

standard 802.11 definisce i seguenti intervalli temporali Inter Frame Space (IFS),

in ordine crescente di valore e decrescente di priorità: Short IFS (SIFS), utilizzato

in entrambe le modalità, per risposte immediate quali ACK, RTS, CTS e risposte

a polling; Point coordination function (PIFS), utilizzato dal controllore


33

centralizzato nello schema PCF, ad esempio quando l’AP gestisce i terminali

decidendo quale di essi accede al mezzo; Distributed coordination function

(DIFS), utilizzato come ritardo minimo per le contese di accesso al mezzo nello

schema DCF; Extended IFS (EIFS), utilizzato al posto del DIFS dalle stazioni che,

avendo ricevuto un frame incomprensibile, non sono in grado di estrarre le

informazioni necessarie per aggiornare il proprio NAV.

Come accennato in precedenza, lo standard 802.11 stabilisce che tutte le stazioni

devono obbligatoriamente supportare la modalità di accesso al mezzo basata sul

protocollo CSMA/CA. Oltre allo schema DCF di base, è previsto l’utilizzo

opzionale del protocollo RTS/CTS allo scopo di risolvere il problema della

stazione nascosta. Il meccanismo basato sulla modalità DCF combinata al

protocollo RTS/CTS prende il nome di DFWMAC Distributed Foundation

Wireless Medium Access Control (DFWMAC-DCF), cerchiamo di spiegarlo con

il supporto della figura 1.12.

Figura 1.12 – Schema DFWMAC-DCF.

Supponiamo che la stazione A voglia inviare dati alla stazione B:

1. A ascolta il canale; se lo sente libero per un tempo DIFS, salta al punto 3,

altrimenti prosegue al punto successivo;

2. A avvia la procedura di backoff (successivamente illustrata);

3. A, anziché inviare subito i dati, manda un frame RTS, che raggiunge B e

tutte le stazioni comprese nella stessa area di copertura di A. RTS è un

messaggio di allerta che contiene l’indirizzo del mittente, quello del


34

destinatario e la durata della trasmissione. Dunque le stazioni coinvolte si

inibiscono a trasmettere per un tempo noto e impostano il proprio

contatore NAV per la durata indicata dal frame;

4. La stazione B, dopo un tempo SIFS dalla ricezione di RTS, invia un frame

CTS che raggiunge A e le stazioni che fanno parte della stessa cella di B.

CTS è un messaggio con contenuti analoghi ad RTS: così le stazioni

capiscono che il mezzo è occupato da A e si inibiscono a trasmettere. Di

queste stazioni fa parte C di figura 1.10;

5. A riceve il CTS da B e, dopo un tempo SIFS, invia il frame contenente i

dati veri e propri;

6. B invia un ACK ad A dopo un tempo SIFS dalla ricezione dei dati. A

questo punto il canale è libero e, dopo un tempo DIFS, riparte il

meccanismo di contesa del mezzo.

Si sottolinea il fatto che la mancata ricezione del messaggio ACK da parte della

stazione A, entro un breve intervallo di tempo, implica che il frame dati non è

stato ricevuto correttamente; quindi questo dovrà essere ritrasmesso da A

ripetendo tutta la procedura.

Nella procedura di backoff si attende un tempo casuale, ma limitato, in modo da

evitare che più stazioni, in attesa che il mezzo si liberi, tentino di occupare

contemporaneamente il canale nell’istante in cui esso viene rilasciato. Qui di

seguito sono riportate le fasi dell’algoritmo di backoff:

1. La stazione A aspetta che il canale sia in stato “idle” (ovvero libero) e che

rimanga tale per un intervallo DIFS;

2. A entra in una Contention Window (CW), ovvero allo scopo di ottenere il

canale compete con altre stazioni per un certo periodo di tempo. Questa

finestra di contesa è slottizzata (al massimo 255 slot) ed ogni stazione

calcola un tempo casuale di attesa (backoff time). La situazione è simile ad

un conto alla rovescia in cui la stazione a cui scade per prima il backoff

time occupa il mezzo se il canale è libero;


35

3. Nel caso in cui il contatore di backoff ha valore nullo, A sceglie un numero

casuale tra 0 e la larghezza corrente della CW, altrimenti lo lascia al valore

attuale (residuo di una precedente procedura di backoff);

4. Per ogni intervallo pari ad uno slot che il canale resta libero, il contatore

viene decrementato e, nel caso in cui il mezzo viene occupato, torna al

punto 1;

5. Quando il backoff time raggiunge il valore 0, se il mezzo è ancora libero,

termina la procedura di backoff e la stazione può trasmettere, altrimenti la

procedura viene sospesa e ripresa alla contesa successiva.

Inoltre viene utilizzata una tecnica di tipo esponenziale allo scopo di diminuire la

probabilità di collisione. Secondo tale tecnica la CW viene raddoppiata dopo ogni

collisione in modo tale da far aumentare i tempi di attesa. Infatti, la ripetizione di

tentativi falliti provoca tempi di attesa maggiori che aiutano a ridurre il carico,

soprattutto in situazioni di alto traffico. Se ad esempio la CW inizialmente ha

dimensione pari a 7, allora ad ogni collisione essa raddoppia, incrementando via

via il numero di slot a 15, 31, 63, 127, 255. Al termine di una trasmissione

corretta la CW viene riportata al valore iniziale di 7 slot.

Nel caso in cui il frame dati sia molto grande (maggiore della dimensione

massima consentita), la modalità DCF prevede la frammentazione in elementi più

piccoli allo scopo di diminuire la probabilità d’errore. Infatti, la probabilità che un

frame sia danneggiato cresce con le sue dimensioni. La frammentazione fa sì che

vengano ritrasmessi solamente i frame danneggiati anziché l’intero frame. Come

si può notare dalla figura 1.13, ogni fragment viene trattato come un frame vero e

proprio: infatti per ognuno di essi il destinatario deve inviare un ACK al mittente.

Inoltre, ciascun frammento indica la durata del successivo, mentre l’ultimo

contiene un flag di fine trasmissione.

La modalità di accesso al mezzo PCF, a differenza della precedente, è opzionale

ed implementabile solamente in reti ad infrastruttura. Infatti, in questo caso un

dispositivo (in genere l’AP) assume il ruolo di controllore centralizzato (point

coordinator) e svolge la funzione di gestione del traffico. L’AP, dopo aver sentito


36

il canale libero per un tempo PIFS, assume il controllo del canale, quindi esegue

un polling per ogni stazione in maniera ciclica, in base a regole che esso decide

(ad esempio, priorità o trasmissione da stazioni sensibili ai ritardi): ecco che, a

differenza dello schema DCF, questa volta non c’è contesa di canale. Ad un certo

punto però l’AP può decidere la fine di questo periodo di assenza di contesa, in

modo che inizi l’implementazione della modalità DCF. Si ha così una struttura di

tipo “superframe” che si ripete ciclicamente con durata variabile degli schemi

DCF e PCF.

Figura 1.13 – Frammentazione.

Quando un terminale entra in una BSS tramite la procedura di handover oppure

semplicemente alla sua accensione, per connettersi alla rete locale wireless deve

ottenere le informazioni sulle celle presenti alla sua portata (ciò avviene grazie

alla scansione, che può essere attiva o passiva). Con la scansione di tipo passivo

un terminale, una volta entrato nell’area di una BSS, “ascolta” il beacon, ovvero il

segnale faro emesso periodicamente da ogni AP e contenente SSID ed altre

caratteristiche della cella . Nel caso di scansione attiva, invece, una stazione

mobile cerca di conoscere le caratteristiche di una BSS e del relativo AP inviando

un frame di richiesta, contenente il SSID della cella desiderata, a cui l’AP

destinatario risponde con un pacchetto soltanto se il proprio SSID e quello

richiesto coincidono.

A livello MAC, esistono sostanzialmente 3 tipi di frame: Dati, Controllo e

Gestione.


37

Ogni frame di tipo Dati presenta la struttura evidenziata in figura 1.14. Questo

frame contiene i quattro indirizzi relativi alle stazioni mobili di origine e di

destinazione ed agli AP di entrata e di uscita nelle comunicazioni fra celle

differenti. Questi indirizzi sono tutti nel formato standard IEEE 802 a 48 bit;

attraverso un’assegnazione globale si garantisce che ogni interfaccia abbia un

indirizzo univoco, in modo che una stazione possa spostarsi da una WLAN

all’altra senza rischio di collisioni.

Figura 1.14 – Formato del frame dati.

Osservando la figura 1.14 possiamo distinguere i seguenti campi: il campo

Duration con il quale i terminali che hanno ricevuto il frame possono prevedere

per quanto tempo il mezzo rimarrà occupato; il campo Sequence Control che

consente di numerare i frammenti (esso è costituito da 16 bit, di cui 12

identificano il frame e 4 identificano il frammento); il campo Frame Control che è

a sua volta suddiviso in 11 sottocampi; in particolare, il primo ottetto è formato da

3 sottocampi con il seguente significato: Protocol version è la versione dello

standard IEEE 802.11; Type è il tipo di frame (Gestione, Controllo o Dati);

Subtype è RTS, CTS, ACK, ecc… Il secondo ottetto del campo Frame Control è

formato da 8 flag distinti che, quando impostati ad 1, hanno il seguente

significato: To DS il frame è diretto al sistema di distribuzione; From DS il frame

proviene dal sistema di distribuzione; More Fragment seguono altri frammenti

appartenenti allo stesso frame; Retry questo frammento è la ripetizione di uno

precedentemente trasmesso; Power Management al termine del frame l’interfaccia

del terminale entrerà nella modalità di basso consumo; More Data il trasmettitore

invierà altri frame al ricevitore; WEP il campo Dati è stato crittografato con


38

l’algoritmo Wired Equivalent Privacy WEP; Order il frammento appartiene alla

classe di servizio “strictly ordered”. Alla fine del frame Dati si trova il campo

Cyclic Redundancy Check (CRC), ovvero un codice ciclico a ridondanza per la

rivelazione di errori.

I frame di tipo Gestione presentano un formato simile al caso precedente ma

richiedono solo tre indirizzi dal momento che rimangono confinati in una singola

BSS. I frame di tipo Controllo, invece, sono ancora più brevi dei due precedenti,

in quanto contengono solo uno o due indirizzi e non presentano i campi Dati e

Sequence Control. Quelli più importanti hanno la seguente struttura:

Figura 1.15 – Formato di alcuni frame di tipo Controllo.

Dopo aver concentrato la nostra attenzione sul formato dei frame MAC, possiamo

aggiungere che viene inserita un’intestazione anche a livello fisico, basata sul

protocollo Physical Layer Convergence Procedure (PLCP), e a sua volta

suddivisa nelle strutture preamble (long o short) e header. Il preambolo PLCP è

formato dai seguenti campi: Syncronization, costituito da 128 bit per il long

preamble e 56 bit per lo short preamble. Il long preamble garantisce compatibilità

tra tutti gli standard IEEE 802.11, mentre lo short consente di incrementare il


39

throughput per supportare applicazioni real time; Start Frame Delimiter (SFD), i

cui bit marcano l’inizio di ogni frame.

Figura 1.16 – Formato PLCP.

La testata PLCP contiene i seguenti campi: Signal o Data Rate, indicante quanto

velocemente i dati verranno trasmessi/ricevuti; Service, indicante la modulazione

utilizzata; Length, indicante la lunghezza del blocco del livello MAC; Cyclic

Redundancy Check (CRC), ovvero il codice ciclico a ridondanza utilizzato per la

rivelazione di errori. In conclusione, il pacchetto effettivamente trasmesso sul

canale assume la seguente struttura:

Figura 1.17 – Formato del pacchetto 802.11.

Lo standard IEEE 802.11 definisce due meccanismi basilari che forniscono il

controllo degli accessi e la riservatezza dei dati relativamente alle reti locali senza

fili: SSID e WEP.

• Service Set IDentifier (SSID): questo consiste di un nome, scelto

dall’amministratore di rete, comune per i dispositivi di una BSS. I client

che non conoscono il SSID non possono accedere alla rete. Questo nome

viene impostato sicuramente nell’AP mentre non sempre nei terminali.

Utilizzare il SSID come identificativo per concedere o negare l’accesso è

pericoloso perché questo nome non è completamente sicuro. Infatti, di

default esso è inviato in broadcast dall’AP insieme al segnale di beacon,

Capitolo 1. Evoluzione dello standard 802.11

40

per cui non deve essere impostato nella scheda di rete del client; tuttavia,

anche nel caso in cui il broadcasting del SSID sia disabilitato, un intruso

può rivelare tale nome attraverso uno “sniffing” (infatti oggi esistono

numerosi tool in grado di catturare il nome della rete). Inoltre, molti access

point prevedono la possibilità di configurare SSID multipli sullo stesso

dispositivo allo scopo, per esempio, di differenziare i profili. In tal caso un

nome potrebbe essere noto solo all’amministratore e non irradiato in

broadcast, mentre un altro potrebbe essere inviato assieme al beacon in

modo da permettere una connessione semplice agli utenti;

• Wired Equivalent Privacy (WEP): lo standard IEEE 802.11 stabilisce uno

schema di encryption opzionale denominato WEP, che offre un

meccanismo per la sicurezza dei flussi di dati nelle reti locali wireless. Il

WEP utilizza uno schema simmetrico nel quale vengono impiegati una

chiave ed un algoritmo sia per la cifratura sia per la decifrazione dei dati.

Gli obiettivi del WEP sono sostanzialmente due: il primo è quello di

impedire agli utenti non autorizzati, che non dispongono di una corretta

WEP key, di accedere alla rete (controllo degli accessi); il secondo,

invece, è quello di proteggere i flussi di dati della LAN wireless tramite

crittografia e consentirne poi la decifrazione soltanto agli utenti muniti

della chiave WEP corretta (principio di riservatezza).

Un ulteriore meccanismo che assicura la riservatezza è la Virtual Private Network

(VPN), implementata in modo trasparente nella WLAN. Poiché il suo utilizzo è

indipendente da qualsiasi schema di sicurezza della rete wireless, verrà trascurato

in questo contesto.

1.2.4 Evoluzione dello standard 802.11

A causa soprattutto della limitata velocità, lo standard 802.11 “legacy” non ebbe

molto successo e quindi successivamente l’IEEE ha emanato tre ulteriori

protocolli per il livello fisico: 802.11b, 802.11a, 802.11g.


41

Il primo consistente passo in avanti in ambiente WLAN avvenne con la

ratificazione dello standard IEEE 802.11b (Wi-Fi) nel 1999; infatti questo

consente una velocità di trasmissione massima pari a 11 Mb/s utilizzando ancora

le frequenze nell’intorno di 2,4 GHz. Sono state inoltre sviluppate soluzioni

proprietarie, normalmente chiamate 802.11b+, che portano il throughput massimo

a 22 Mb/s. Per quanto riguarda la copertura, il range di trasmissione previsto è

pari a 300 metri outdoor e 30 metri indoor. Si sottolinea che al diminuire della

velocità cresce la dimensione fisica di una rete locale wireless, nel senso che

aumenta il raggio di copertura dell'AP: in genere si raggiungono 10 metri di

raggio mantenendo la massima velocità, 20 metri dimezzandola, fino ai limiti

della BSS con valori di 1 e 2 Mb/s.

Comunque si tenga presente che i valori (sia di velocità di trasmissione sia di

range di copertura) indicati in precedenza sono solamente teorici. Inoltre, poiché il

mezzo è unico e condiviso tra gli utenti, la banda disponibile per ciascuno di

questi diminuisce al crescere del loro numero complessivo all’interno di una BSS.

Lo spettro da 2,400 GHZ a 2,4835 GHz è suddiviso in 14 canali spaziati di 5

MHz, ognuno dei quali in sostanza rappresenta una frequenza radio a cui è

associato un numero. Ad esempio, il canale 1 corrisponde alla frequenza di 2412

MHz, il canale 2 alla frequenza di 2417 MHz, il canale 3 alla frequenza di 2422

MHz e così via. La possibilità di utilizzare certi canali dipende dalle disposizioni

nazionali (vedi figura 1.18): in Italia dall’1 al 13, negli USA dall’1 all’11, il 14

solo in Giappone.

Ad ogni AP è assegnato un canale, selezionato automaticamente oppure scelto

dall’amministratore di rete. Tuttavia i canali sono ampi circa 22 MHz ciascuno

per cui, a causa della spaziatura di 5 MHz, si sovrappongono parzialmente.

Questo fatto vincola a tre il numero massimo di canali non sovrapposti da

utilizzare in altrettante celle non interferenti nella stessa zona: in particolare, come

mostra la figura 1.18, i canali 1, 6, 11 ed i canali 1, 7, 13. Quindi tre AP vicini

verranno abilitati a funzionare sui canali precedenti in modo da non creare

interferenze. Il protocollo 802.11b utilizza la tecnica di trasmissione DSSS, con

codice di Barker ad 11 chip e modulazioni BPSK e QPSK (rispettivamente per


42

velocità di 1 e 2 Mb/s, come lo standard del 1997), e con spreading code ad 8 chip

e modulazione CCK (per velocità di 5,5 e 11 Mb/s).

Figura 1.18 – Lista completa delle frequenze 802.11b.

I vantaggi di IEEE 802.11b sono legati soprattutto alla grande diffusione dei

prodotti su scala mondiale. Tuttavia si deve fare i conti con un data rate che nella

realtà non supera 5,5 Mb/s circa. In conclusione, per quanto detto, l’utilizzo di

questo protocollo risulta conveniente in situazioni con un numero limitato di

utenti e con applicazioni che richiedono una larghezza di banda non eccessiva.

Lo standard IEEE 802.11a (approvato nel 1999), invece, utilizza lo spazio di

frequenze nell'intorno dei 5 GHz e opera con una velocità di trasmissione

massima pari a 54 Mbit/s, sebbene nella realtà il valore reale sia circa 20 Mbit/s. Il

throughput massimo può essere ridotto a 48, 36, 24, 18, 12, 9, 6 Mb/s se il SNR lo

impone. Lo standard suddivide le bande 5.15-5.25, 5.25-5.35, 5.725-5.825 GHz in

12 canali non sovrapposti di 25 MHz ciascuno, di cui 8 dedicati alle

comunicazioni interne e 4 per le connessioni tra edifici. Analogamente a quanto

avviene nel protocollo precedente, l’effettivo utilizzo dei canali è dettato da


43

regolamentazioni nazionali. Negli USA è possibile sfruttare tutti i 12 canali,

mentre inizialmente in Europa la regolamentazione delle frequenze è stata

piuttosto complessa perché la banda nell’intorno dei 5 GHz è già impegnata per

altre applicazioni, in particolare trasmissioni satellitari e militari. Per quanto

concerne la copertura, facendo un confronto con il protocollo precedente, il range

è inferiore (a parità di potenza) vista la maggiore frequenza di lavoro. Quindi, se

da un lato sono necessari più AP per coprire la stessa area (con conseguente

aumento dei costi), dall’altro possono operare più utenti in una BSS e con un data

rate maggiore. Un altro vantaggio di 802.11a, oltre alla maggiore banda (ottenibile

grazie alla modulazione OFDM in seguito descritta) e alla possibilità di numerosi

valori di data rate scalabili, riguarda l’utilizzo di bande libere ma meno affollate di

quelle a 2,4 GHz, con la conseguenza di presentare minori interferenze con altri

dispositivi (uno dei problemi principali degli standard a 2,4 GHz). Il protocollo

802.11a non ha riscosso i favori del pubblico a causa del limitato raggio d'azione e

dell'incompatibilità con le specifiche 802.11b/g, i cui prodotti sono di gran lunga

più diffusi.

Figura 1.19 – I tre canali non sovrapposti in 802.11 b/g.


44

Lo standard IEEE 802.11g, ratificato nel 2003, utilizza le stesse frequenze di

802.11b (cioè la banda a 2,4 GHz) e fornisce una velocità massima teorica di 54

Mbit/s grazie alla modulazione OFDM, analogamente ad 802.11a. È totalmente

compatibile con 802.11b, per cui consente una migliore tutela degli investimenti

già effettuati, ma, quando si trova ad operare con periferiche del “vecchio” Wi-Fi,

deve ovviamente ridurre la sua velocità massima ad 11 Mb/s per evitare problemi

di congestione. A titolo di esempio, in una WLAN è possibile ottenere un

collegamento tra un terminale dotato di scheda di rete wireless secondo le

specifiche 802.11b ed un access point in tecnologia 802.11g; naturalmente, la

velocità di trasmissione in questo link è limitata dal minore throughput

supportabile dalle schede, quindi ha un valore massimo di 11 Mbps.

Alcuni costruttori introducono nei loro prodotti delle ulteriori varianti chiamate

g+ o Super G, che utilizzano l'accoppiata di due canali per raddoppiare la banda

disponibile. Grazie all’elevata larghezza di banda, 802.11g (così come il

precedente protocollo 802.11a) risulta adatto al supporto di applicazioni real time

quali telefonia su IP e streaming audio/video, rimediando ai limiti di 802.11b pur

conservandone la frequenza di lavoro.

Lo standard 802.11g costituisce ormai il vero fiore all’occhiello delle WLAN:

basta pensare che la grande maggioranza di PC portatili attuali contiene schede

wireless integrate ed il software di gestione compreso nel sistema operativo.

Come precedentemente detto, IEEE 802.11a e 802.11g utilizzano la tecnica

OFDM, abbinata ad altre modulazioni soprattutto di tipo QAM, per supportare

velocità maggiori rispetto allo standard Wi-Fi ad 11 Mb/s. Nel 1970 Bell Labs

brevettò questa tecnica basata sul processo matematico noto come Fast Fourier

Transform (FFT). La trasformata consente la sovrapposizione nel tempo di 52

canali al massimo (di cui 4 pilota) senza che questi perdano la loro individualità e

ortogonalità (vedi figura 1.21); questa sovrapposizione comporta maggiore

efficienza nell’utilizzo dello spettro e nell’elaborazione dei canali al ricevitore.

In buona sostanza, la frequenza portante è suddivisa in più sottoportanti a bassa

velocità; ognuna di queste è modulata individualmente ed ha velocità di


45

trasmissione e potenza variabili in relazione alla qualità del canale per quella

specifica frequenza, in modo da ottimizzare le prestazioni del sistema.

Figura 1.20 – Caratteristiche degli standard fisici IEEE 802.11.

Le sottoportanti vengono trasmesse in parallelo sovrapponendole nel tempo, in

modo da generare un unico segnale da inviare sul canale. Quindi i dati trasmessi

da ciascuna sottoportante sono inviati e ricevuti simultaneamente. Questa tecnica

consente di raggiungere un data rate elevato (54 Mb/s in questo contesto wireless)

senza diminuire il tempo di simbolo, ma sovrapponendo nel tempo le

sottoportanti, che sono separate nel dominio della frequenza. Uno dei maggiori

vantaggi della tecnica OFDM è la sua resistenza alle interferenze multipath e alla

dispersione del ritardo.

L’interferenza multipath sorge quando le onde radio vengono riflesse o quando

attraversano gli oggetti presenti nell’ambiente. Le onde radio vengono attenuate o

indebolite in vari modi a seconda dei materiali che compongono gli oggetti. A


46

causa delle riflessioni e delle attenuazioni, una singola trasmissione può

sperimentare potenze di segnale differenti e può provenire da direzioni differenti a

seconda del tipo di materiale incontrato.

Figura 1.21 – Modulazione OFDM.

La dispersione del ritardo (delay spread) è associata al problema del multipath.

Poiché il segnale deve raggiungere il ricevitore seguendo cammini diversi, esso

arriva in momenti differenti. A mano a mano che aumenta la velocità di

trasmissione, cresce anche la probabilità di interferenze con i segnali trasmessi in

precedenza.

I fenomeni del multipath e della dispersione del ritardo non sono molto gravi per

data rate fino a 3 o 4 Mb/s, mentre aumentando la velocità è necessario adottare

qualche meccanismo per ridurre l’effetto di questi disturbi. A tal proposito,

802.11b utilizza la modulazione CCK, mentre 802.11a e 802.11g utilizzano la

tecnica OFDM illustrata in questo paragrafo.

Altri standard IEEE 802.11 sono:

• 802.11e: questo protocollo supporta caratteristiche Quality of Service

(QoS) tra cui priorità di trasmissioni dati, voce e video. Le code dei

pacchetti da trasmettere sono differenziate a seconda dell’appartenenza a


47

definite access categories, le quali sono caratterizzate da tempi di accesso

al servizio differenti, in modo da garantire differenti livelli di priorità.

Normalmente i servizi che richiedono minori ritardi di trasmissione sono

servizi real time (VoIP, videoconferenze, telecontrollo, ecc…), sono

associati a livelli di priorità più elevati, mentre il traffico best effort (web

browsing, FTP) viene associato ad una priorità inferiore;

• 802.11f o più comunemente detto Inter Access Point Protocol (IAPP):

indica la compatibilità tra AP di produttori differenti;

• 802.11h: estende l’operabilità delle specifiche 802.11a in Europa tramite

meccanismi quali la misurazione per la selezione dinamica del canale

Dynamic Frequency Selection (DFS) e il controllo di potenza Transmit

Control Power (TCP);

• 802.11i (Wi-Fi Protected Access 2, WPA2): questo standard, ratificato nel

Giugno del 2004, è stato sviluppato per migliorare i meccanismi di

sicurezza grazie all’utilizzo dell’algoritmo Advanced Encryption Standard

(AES);.

• 802.11n: standard per reti metropolitane con velocità 100 Mb/s, include la

possibilità di utilizzare la tecnologia Multiple Input Multiple Output

(MIMO) in modo da consentire l’utilizzo di più antenne per trasmettere e

più antenne per ricevere, incrementando così la banda disponibile e il

range di copertura;

• 802.11p (Wave Access for the Vehicular Environment, WAVE): permette

lo scambio di dati tra veicoli ad alta velocità e tra veicoli e infrastrutture

poste sul lato della strada nella banda 5,850-5,925 GHz in Nord America.

Capitolo 2. La localizzazione indoor

48

Capitolo 2

La localizzazione indoor

Le infrastrutture WLAN attualmente sono disponibili nella maggior parte degli

edifici pubblici, ed inoltre i venditori di dispositivi mobili come PDA,

smartphone, (PSP), riproduttori MP3, ecc… includono connettività Wi-Fi su

questi dispositivi, rendendo più attraente lo sviluppo dei servizi LBS basati sulla

localizzazione indoor. Quindi, vista la facilità di accesso alle reti Wi-Fi e visto il

gran numero di dispositivi in grado di interfacciarsi con esse, non vi sono ingenti

costi di infrastruttura, poiché dal lato HW i dispositivi sono economici e dal lato

SW l’implementazione risulta più semplice. Questo rende l’infrastruttura WLAN

una soluzione per la localizzazione, più appetibile dal punto di vista economico

rispetto ad altre infrastrutture dedicate.

Un altro vantaggio del posizionamento tramite reti Wi-Fi è che esse operano

meglio in ambienti indoor, di grandi o piccole dimensioni, quindi il raggio di

copertura non è limitato, anzi, vi è la possibilità di scalare utilizzando tecniche di

localizzazioni che mutano in base alle diverse esigenze. Inoltre, i sistemi di

comunicazione wireless sono affetti da fenomeni di propagazione del segnale che

possono causare delle imprecisioni nel calcolo della posizione; tuttavia, il segnale

radio è più robusto del segnale impiegato per altri sistemi come l’infrarossi o

l’ultrasuoni, che hanno più limitazioni nel caso non ci sia linea di vista diretta tra

il trasmettitore e il ricevitore oppure per disturbi come la luce solare, luce

fluorescenti, ecc…

Quindi la localizzazione in ambienti indoor tramite reti Wi-Fi ha il vantaggio di

essere una soluzione economica, mutevole e robusta rispetto ad altri sistemi, ed in

particolare essa si basa nella collezione di un certo parametro presente nel segnale

radio che viaggia tra gli AP e i terminali, e attraverso la tecnica e il metodo di

localizzazione selezionati, sarà possibile processare tale parametro e determinare

la posizione reale dell’utente. Questi metodi non sempre si basano su un semplice

Capitolo 2. Caratteristiche dei sistemi di posizionamento

49

confronto del parametro rilevato, ma spesso impiegano trasformazioni

matematiche per determinare la posizione.

Questo capitolo mira a chiarire come può avvenire la localizzazione attraverso il

riutilizzo di strutture preesistenti come una rete wireless per il collegamento ad

internet senza fili. Inoltre, verranno illustrate le tecniche di localizzazione

utilizzate sia in ambiente outdoor che in ambienti indoor, attraverso misure di

parametri della rete. Queste saranno descritte in modo discorsivo non essendo

questa parte tecnica l’obiettivo della tesi. Inoltre, verrà identifica la tecnica da

utilizzare e le specifiche di questa scelta. Infine, verranno descritti i sistemi di

localizzazione indoor Wi-Fi attualmente esistenti.

2.1 Caratteristiche dei sistemi di posizionamento

Il posizionamento è un processo atto ad ottenere la posizione spaziale di un

determinato oggetto o di un utente che sia collegato a un servizio di

localizzazione. Per determinare la posizione esistono diversi metodi, che in

generale sono legati dai seguenti fattori: i parametri osservati durante il processo

di misurazione; il tipo di calcolo realizzato per determinare la posizione; il sistema

di rappresentazione della posizione; l’infrastruttura; i protocolli per la

coordinazione del processo di posizionamento.

La parte centrale di un meccanismo di posizionamento è la misurazione di uno o

più parametri osservabili, ad esempio: angoli, range, differenza di range, velocità,

ecc… Questi parametri solitamente definiscono una relazione spaziale tra i diversi

punti di una stessa area. In particolare è possibile distinguere tra punti fissi e punti

individuati. I primi rappresentano quei punti ben identificati, mentre i secondi si

ottengono attraverso relazioni sulle coordinate dei primi. Comunque, entrambi i

punti vengono misurati attraverso uno dei parametri che definiscono il segnale

radio. Dopo che questo parametro è stato identificato, la posizione istantanea

deriverà principalmente da esso. Questa identificazione è basata sulla scelta dei

metodi che andranno ad implementare la tecnica scelta.

Capitolo 2. Caratteristiche dei sistemi di posizionamento

50

Un metodo di localizzazione per determinare la posizione istantanea di un utente

in un sistema di riferimento ha bisogno di un’infrastruttura distribuita, in quanto

non è in grado di determinare la posizione in maniera autonoma. Quindi, ogni

utente che vuole essere individuato deve essere provvisto di un terminale e la zona

d’implementazione deve essere fornita di dispositivi che fungono da stazioni base,

in modo tale che il terminale possa misurare il parametro associato al metodo

impiegato.

Inoltre, il posizionamento necessita di essere coordinato e controllato dai

protocolli che gestiscono i componenti del sistema. Generalmente lo schema di

coordinazione si basa sull’utilizzazione di un’unità centrale di controllo, che

gestisce la comunicazione tra le diverse stazioni base e la comunicazione tra le

stazioni base e i terminali.

Infine, va osservato che i criteri per valutare la qualità di un certo metodo di

posizionamento sono:

• L’accuratezza e la precisione. Con accuratezza si intende il grado di

corrispondenza tra la posizione stimata e quella reale. Invece, con

precisione si intende il grado di convergenza tra la posizione stimata e il

suo valore medio. Questi sono considerati i parametri di qualità più

importanti nei sistemi di localizzazione;

• Rendimento e consistenza. Con rendimento si intende l’abilità del metodo

di posizionamento di stimare la posizione in tutti i tipi di ambienti, mentre,

la consistenza è una misura della stabilità dell’accuratezza in differenti

ambienti;

• Overhead. Indica la quantità d’informazione scambiata tra il terminale e il

sistema. Quindi è direttamente legata al livello di accuratezza e precisione

che si vuole raggiungere;

• Consumo di potenza. In quanto è necessario considerare le risorse

energetiche disponibili per il terminale. Inoltre, bisogna studiare il

consumo durante le operazioni di comunicazioni con il sistema e

prevedere procedure di risparmio nei momenti d’inattività;

Capitolo 2. Sistemi di rappresentazione della posizione

51

• Latenza. Si riferisce all’intervallo di tempo tra una richiesta di

posizionamento e la risposta del sistema in termini di una posizione fissa.

Generalmente per sistemi LBS è dell’ordine dei secondi;

• Costi roll-out e costi operativi. I costi roll-out sono quei costi necessari per

installare l’infrastruttura (le stazioni base, database, unità di controllo,

ampliamento dell’infrastruttura già esistente, ecc…). Invece, i costi

operativi sono legati alla complessità del sostenimento e mantenimento

dell’infrastruttura impiegata.

2.1.1 Sistemi di rappresentazione della posizione

Nell’ambito dei servizi basati sulla localizzazione, si fa riferimento sempre a una

posizione fisica che può essere rappresentata per mezzo di una descrizione

generica in cui si trova l’utente (in un’area geografica, una regione, in una stanza

di un determinato palazzo, ecc…) oppure mediante una rappresentazione spaziale,

cioè sono indicate le coordinate di dove si trova l’utente.

Un esempio del primo caso potrebbe essere la localizzazione della cella alla quale

appartiene in un determinato momento un terminale di una rete mobile cellulare.

Un esempio del secondo caso invece è il classico sistema GPS, o la sua versione

Europea denominata Galileo.

Inoltre, tra i sistemi di rappresentazione delle coordinate possiamo distinguere

quelli che utilizzano un sistema di riferimento cartesiano e quelli che utilizzano un

sistema di riferimento ellissoidale. Il sistema cartesiano è utilizzato quando la

localizzazione è riferita a uno spazio con quota costante, generalmente in ambienti

indoor, dove non interessa la posizione dell’utente in funzione delle caratteristiche

geografiche della terra. In ambienti outdoor, come accade nel caso dei sistemi di

navigazione satellitare, il campo di ricerca è più ampio e più complesso e quindi è

preferibile utilizzare un sistema di coordinate ellissoidale più adatto alla

localizzazione geografica.

Siccome il nostro progetto si occupa della localizzazione in un ambiente indoor la

posizione verrà rappresentata attraverso le coordinate di un sistema cartesiano, ma

Capitolo 2. Infrastrutture di reti finalizzate alla localizzazione

52

in alcuni casi può essere utile rappresentare la posizione utilizzando un approccio

di tipo geografico per cluster.

L’utilizzo di un sistema basato sulla localizzazione geografica in ambienti indoor

nasce fondamentalmente dall’incertezza derivante dai meccanismi di

posizionamento puntuali utilizzati in Wi-Fi. Alcuni vantaggi dell’approccio

geografico sono dovuti al fatto che un sistema basato sulla localizzazione

geografica è in grado di individuare un terminale in un modo più sistematico

rispetto all’approccio puntuale. Per esempio, se viene utilizzato questo sistema per

determinare la posizione di un oggetto, l'utente può iniziare la sua ricerca nella

zona individuata dal sistema e con un’alta probabilità l’oggetto si troverà in

quell’area o almeno in un’area adiacente. Inoltre, dal punto di vista dell’utente, è

più naturale e intuitivo individuare una zona piuttosto che un punto. Infatti, se ad

esempio il sistema restituisce come risposta il nome di una stanza, per l'utente sarà

più facile capire la posizione in cui si trova, anziché determinarla attraverso le

coordinate su una mappa. Infine, in termini di prestazioni, un sistema basato sulla

localizzazione di aree, sicuramente avrà un range di accuratezza e precisione più

alto, visto che l’errore generato dipende dalla differenza tra la posizione corretta e

quella stimata.

Quindi, anche se la posizione viene espressa attraverso le coordinate di un sistema

cartesiano per velocizzare l’apprendimento della posizione dell’utente, in alcuni

casi è preferibile utilizzare un approccio di tipo geografico.

2.1.2 Infrastrutture di reti finalizzate alla localizzazione

La localizzazione e le infrastrutture di posizionamento possono essere classificate

sulla base di diversi criteri. La principale distinzione è l’infrastruttura che può

essere integrata o stand-alone.

Un’infrastruttura integrata fa riferimento a una rete wireless che può essere

utilizzata sia per la comunicazione che per il posizionamento. Generalmente tali

reti sono state progettate solo per comunicazione ma ora si stanno sperimentando

estensioni che permettano la localizzazione degli utenti attraverso meccanismi di

Capitolo 2. Infrastrutture di reti finalizzate alla localizzazione

53

posizionamento su dispositivi mobili. I componenti che possono essere riutilizzati

per la localizzazione sono le stazioni base, i dispositivi mobili, nonché i protocolli

di localizzazione e di gestione della mobilità. L’estensione della rete riguarda

l'installazione di nuove versioni software e di componenti di rete per l'esecuzione

e il controllo di posizionamento, inoltre è prevista l'installazione di nuovi

componenti hardware utilizzati per svolgere funzioni di sincronizzazione, raccolta

dati e per altri scopi. Un approccio integrato ha i seguenti vantaggi: la rete non ha

bisogno di essere interamente costruita; i costi roll-out e i costi operativi sono

esigui. Tuttavia, va osservato che gestire il posizionamento sulla rete risulta

oneroso in termini di traffico aggiunto e di conseguenza si registra una minore

capacità nell’offerta di servizi di base per l’utenza. Inoltre, va registrato il fatto

che nella maggior parte dei casi le misurazioni devono essere effettuate all’interno

di reti già esistenti, la cui progettazione non è stata pensata per il posizionamento

e che quindi possono richiedere ulteriori implementazioni.

Un’infrastruttura stand-alone invece opera indipendentemente dalla rete di

comunicazione alla quale l'utente è collegato. In contrasto con un sistema

integrato, le infrastrutture e le interfacce sono destinate esclusivamente al

posizionamento e la loro progettazione è molto semplice. Il più noto esempio di

infrastruttura stand-alone è il Global Positioning System (GPS). Gli svantaggi di

tali infrastrutture sono dovute ai costi elevatissimi, poiché gli utenti non possono

essere localizzati attraverso un dispositivo mobile standard ma richiedono

componenti hardware proprietari.

Un’ulteriore distinzione può essere fatta tra il posizionamento basato sulla rete e il

posizionamento basato sul terminale, in termini di chi effettua le misurazioni e chi

esegue il calcolo della posizione fissa. Un approccio ibrido, in questo caso, si ha

quando il terminale effettua le misurazioni e le trasmette alla rete, che ha il

compito di processare le misurazioni al fine di determinare la posizione. Tale

approccio di posizionamento è assistito dalla rete sul terminale. L’operazione

inversa (posizionamento assistito dal terminale sulla rete) è stata definita, ma è

applicata molto raramente.

Capitolo 2. Tecniche di posizionamento

54

2.2 Tecniche di posizionamento

Il problema della localizzazione può essere approcciato generalmente in due

modalità: da una parte si può lavorare per via geometrica, effettuando una

triangolazione, nota la distanza da almeno tre AP ovvero l’angolo di arrivo del

segnale da almeno due AP, la cui posizione sia ovviamente nota a priori. A tal

fine possono implementarsi algoritmi di tipo Time of Arrival (ToA) o Angle of

Arrival (AoA). Tali tecniche, utilizzate soprattutto per localizzazioni di tipo

outdoor, mal si adattano però ad ambienti indoor, caratterizzati da multipath

particolarmente profondo, cosa che si può tradurre in errori nel processo di

localizzazione. E’ oltretutto importante sottolineare come soluzioni di tale tipo

possono comportare un costo computazionale oneroso per terminali caratterizzati

da capacità elaborative limitate, soprattutto laddove si voglia un’elevata

precisione nella localizzazione. Altra limitazione è data dal fatto che tali sistemi

richiedono tanto una sincronizzazione a livello di rete quanto l’utilizzo di

hardware dedicato disposto spazialmente nell’ambiente di lavoro in maniera

appropriata.

A fianco di dette metodologie è altresì ben studiato in letteratura l’approccio

basato sulla cosiddetta scene analysis. In questo caso l’algoritmo risulta diviso in

due passi. Preliminarmente alla messa in esercizio del sistema, si effettuano

campagne di misurazione di parametri sensibili (ad esempio il livello di potenza di

segnale ricevuto da più AP) in un certo numero di posizioni all’interno dell’area

di copertura, costruendo in tal modo un database di misure, con una o più entry

per ogni locazione. Successivamente, al momento della necessità di stimare la

posizione, l’entità preposta effettua una misurazione dei medesimi parametri e

confronta il risultato con le entry del database costruito offline, optando per il best

matching; essenzialmente, quindi, il problema di localizzazione diventa un

problema di classificazione, che può essere oggetto di ottimizzazione in modo da

non gravare eccessivamente sul device dal punto di vista computazionale.

Algoritmi di questo tipo si prestano ad essere implementati tanto in modalità

client based quanto in modalità client assisted, mediante l’aiuto di opportuni

Capitolo 2. Proximity Sensing

55

sensori, detti sniffers, che effettuano continuativamente un passive scanning dei

segnali effettuando le misurazioni necessarie e sgravando in tal modo i client di

una parte del carico elaborativo. Altra possibilità di cooperazione tra rete e client è

quella di demandare interamente alla rete la classificazione, lasciando al client il

solo compito di effettuare le misurazioni online e di trasmetterle alla rete, la quale

risponderà con l’informazione di localizzazione. Tale approccio permette una

soluzione client assisted puramente software (non sono necessari hardware

aggiuntivi quali gli sniffers) e il traffico di segnalazione introdotto risulta

pressoché nullo. Per quel che riguarda invece possibili incrementi di efficienza in

un approccio puramente client based, si può pensare di considerare non solo le

misure di un solo device, ma anche quelle effettuate dai neighbour device, ove sia

tollerabile il conseguente aumento di traffico di segnalazione.

Tali tecniche verranno di seguito descritte facendo enfasi sui principi di

funzionamento e sulla determinazione dei parametri influenzati dalla posizione.

2.2.1 Proximity Sensing

E’ la tecnica più semplice e più diffusa per ottenere la posizione di un terminale.

Essa è basata sulla creazione di una zona delimitata dal raggio di copertura di un

segnale radio, infrarosso o ultrasuono. La posizione di un terminale è derivata in

questo caso dalle coordinate della stazione base che pilota il segnale in direzione

uplink o dei segnali pilota che sono ricevuti dal terminale in downlink. Il principio

dei sensori di prossimità si mostra nella figura 2.1. In questo caso si assume che la

posizione del terminale è semplicemente la posizione della stazione base che invia

e riceve i segnali pilota. Nella figura a sinistra si mostra una configurazione con

sensori di prossimità, impiegando antenne omnidirezionali, mentre nella figura a

destra si mostra il caso con antenne settorizzate. L’implementazione di questi

sensori può essere fatta in diversi modi, alcuni di essi standardizzati mentre altri

sono soluzioni proprietarie di alcuni operatori o fornitori. Comunque, la posizione

dei sensori dipenderà esclusivamente dal fatto che si stia impiegando

un’infrastruttura integrata o stand-alone.

Capitolo 2. Lateration

56

Figura 2.1 – Coperture omnidirezionali e settoriali dei sensori di prossimità.

2.2.2 Lateration

Con questa tecnica si può partire sia dalla conoscenza della copertura che dalle

differenze di copertura di n stazioni base vicine al terminale in studio.

Quest’ultima informazione è utilizzata per definire un sistema di n equazioni non

lineari necessarie a determinare la posizione del terminale. Se il posizionamento si

basa sulle coperture, si parlerà di circular lateration poiché il problema da

risolvere è l’intersezione di cerchi aventi raggio pari alla copertura delle stazioni

base in funzione della posizione del terminale nel caso 2D mentre nel caso 3D il

problema da risolvere sarà l’intersezione di tre sfere. Invece, nel caso in cui il

posizionamento sia basato sulla differenza delle coperture delle stazioni base, si

parlerà di hyperbolic lateration.

Detto ciò esaminiamo il caso di circular lateration in 2D. Assumiamo che le

distanze tra il terminale e le stazioni base siano conosciute e denotate come r i con

i = 1,...,n e n pari al numero di stazioni base. Come si vede nella figura 2.2,

conoscendo i diversi valori di r i, è possibile rappresentare tutti i punti che distano

r i da ogni stazione base, mediante il raggio di un cerchio. Se viene presa in

considerazione più di una stazione base, le soluzioni possibili vengono ridotte, per

tale motivo bastano semplicemente tre stazioni base per avere una soluzione

univoca al problema di posizionamento. In quest’ultimo caso tale procedura

prende il nome di triangolazione.


57

Figura 2.2 – Circular Lateration in 2D.

Se le coordinate dei punti di riferimento, cioè la posizione delle stazioni base in

studio, rispetto a un sistema di coordinate cartesiano sono (Xi,Yi), allora il

problema di posizionamento viene risolto attraverso le seguenti equazioni:

( ) ( )22 yYxXr iii −+−= , per i = 1,2,3

dove (x,y), è la coppia di coordinate del terminale e r i le equazioni dei diversi

cerchi intorno al punto in studio. Quindi si ottiene il seguente sistema di

equazioni:


58

( ) ( )( ) ( )( ) ( )

=−+−==−+−==−+−=

23

23

23

22

22

22

21

21

21

ryYxXC

ryYxXB

ryYxXA

Tale sistema può essere ridotto ad un sistema in due equazioni del tipo:

( ) ( ) ( ) ( )[ ]( ) ( ) ( ) ( )[ ]

=−+−−=−+−=−

=−+−−=−+−=−

23

23

23

22

22

22

22

22

22

21

21

21

ryYxXryYxXCB

ryYxXryYxXBA

che può essere visto nella forma:

=+=−=+=−

fdycxCB

ebyaxBA

Dunque si ottiene un sistema in due equazioni lineari e due incognite, facilmente

risolvibile utilizzando il Teorema di Cramer:

)(

)(

)(

)(

dc

baDet

fc

eaDet

y

dc

baDet

cf

beDet

x ==

Sostituendo le rispettive costanti la localizzazione diventa un semplice problema

di determinanti di matrici.

Questa procedura può essere estesa al caso tridimensionale, con la differenza che

in questo caso entra in gioco una terza coordinata e si parlerà quindi di

intersezione di sfere. Infatti, per analogia, nel caso di circular lateration in 3D

(figura 2.3) si ha:

( ) ( ) ( )222 zZyYxXr iiii −+−+−= , per i = 1,2,3


59

dove i parametri z e Zi rappresentano rispettivamente l'altitudine dell'obiettivo e

dell'i-sima stazione base.

Per spiegare il funzionamento della lateration hyperbolic, invece, partiamo dalla

definizione di iperbole. Si definisce iperbole il luogo dei punti del piano per i

quali è costante la differenza delle distanze da punti fissi detti fuochi. Nel caso

specifico questi punti saranno le stazioni base.

Figura 2.3 – Circular Lateration in 3D.

Per il caso del 2D, si considera la differenza di distanza tra un obiettivo e due

stazioni base come decritto in figura 2.4. La distanza tra l’obbiettivo e la prima

stazione base è indicata con r1, mentre, la distanza tra l’obbiettivo e la seconda

stazione è indicata con r2. In queste condizioni, la differenza r2 - r1 ora limita la

posizione dell'obiettivo ad un'iperbole, come mostrato in figura 2.4 (a). Se la

differenza viene determinata per un’altra stazione base, per esempio la terza, si

crea un'iperbole supplementare e l'intersecazione di ambo delimita ulteriormente

la posizione dell'obiettivo come in figura 2.4 (b). Nel caso 3D, le differenze di

distanza tra un obiettivo e due stazioni di base sono date dalla superficie di un

iperboloide ed è necessario determinare un minimo di tre iperboloidi per

individuare inequivocabilmente l'obiettivo. Quindi è possibile scrivere:

Capitolo 3. Cisco Wireless Location Appliance

60

( ) ( ) ( ) ( ) ( ) ( )222222 zZyYxXzZyYxXrrd jjjiiijiij −+−+−−−+−+−=−=

dove dij rappresenta la differenza tra r i e r j con la regola che i ≠ j. In questo modo

è possibile costruire un sistema in tre equazioni nelle tre incognite (x,y,z) del

nostro obbiettivo.

Figura 2.4 – Hyperbolic Lateration.

2.2.3 Angle of Arrival

La differenza rispetto alla tecnica precedente risiede nel fatto che qui sono

misurati gli angoli tra il terminale e un certo numero di stazioni base. Per

determinare tali angoli è necessario che le stazioni base come i terminali siano

dotati di array di antenne, secondo il tipo di posizionamento (basato sul terminale

o basato sulla rete). Tuttavia, oggi, per ragioni di complessità e costi, si preferisce

una soluzione orientata alla rete piuttosto che ai terminali. Il principio di base di

tale tecnica è illustrato nella figura 2.5. L'angolo di arrivo di un segnale pilota in

ingresso è misurato rispetto alla stazione base e a una linea che unisce il terminale

nella sua posizione istantanea. Se si prende in considerazione l'angolo di una

Capitolo 2. Angle of Arrival

61

seconda stazione base si definisce un’altra linea che unisce il terminale con questa

seconda stazione base. L’intersezione di entrambe le linee rappresenta quindi la

posizione del terminale.

Figura 2.5 – Principio di funzionamento della tecnica AoA.

2.2.4 Time of Arrival

In questa tecnica si applicano i principi di lateration utilizzando però il ritardo che

subisce il segnale. Si parla di circular lateration nel caso in cui si prendono

direttamente i ritardi (Time of Arrival, ToA), di hyperbolic lateration nel caso in

cui si prende in esame la differenza tra questi ritardi (Time Differential of Arrival,

TDoA). Anche in questa tecnica bisogna distinguere tra posizionamento orientato

al terminale o alla rete. Tale distinzione dipende dal verso in cui si effettuano le

misurazioni dei ritardi (downlink o uplink). Nel caso downlink, il terminale

esamina i segnali pilota ricevuti dalle stazioni base. Invece, nel caso uplink, la

rete, ma più precisamente le stazioni base ricevono il singolo segnale pilota

proveniente dal terminale. Questi segnali pilota possono essere radio, infrarossi o

ultrasuoni, anche se in questo contesto considereremo solo i segnali radio. I

metodi utilizzati per determinare i ritardi sono:

• Pulse ranging: viene misurato il tempo di propagazione di un singolo

impulso. Per il caso ToA deve essere noto il momento in cui è trasmesso

Capitolo 2. Time of Arrival

62

questo impulso. Invece, per il caso TDoA, non è necessario, poiché il

calcolo si effettua in base alle differenze di tempo con altri segnali arrivati;

Figura 2.6 – Misurazione del tempo di propagazione.

• Carrier phase ranging: in questo caso il segnale ricevuto è confrontato in

fase con un segnale di riferimento generato previamente per il ricevitore.

Questa differenza di fase determina il ritardo di propagazione;

Figura 2.7 – Confronto di fase (segnali analogici).

• Code phase ranging: anche in questo caso si misura la differenza di fase

del segnale ricevuto con un segnale di riferimento, la differenza con il

metodo precedente è che i segnali sono modulati con un codice spreading

noto, e quindi è necessario per il calcolo della fase determinare la

correlazione tra i due segnali. Il valore Integer Ambiguity riflette il numero

Capitolo 2. Time of Arrival

63

di cicli del segnale di riferimento prima che esso agganci il segnale pilota

ricevuto.

Figura 2.8 – Confronto di fase (segnali numerici).

In tutti questi metodi, vi è una grande dipendenza dalla velocità di propagazione

del segnale, per cui è necessaria un’esatta sincronizzazione tra gli orologi del

terminale e la stazione base coinvolta per il caso ToA e tra gli orologi delle

diverse stazioni base coinvolte per il caso TDoA.

2.2.5 Scene Analysis

L’ultima tecnica, che sarà quella scelta per una serie di motivi economici,

strutturali e tecnici, permette la localizzazione dell’utente attraverso il paragone

fra potenze misurate in un ambiente che non ha subito notevoli variazioni nel

tempo trascorso tra le due rilevazioni.

La tecnica infatti prevede la misurazione di tante potenze nei vari punti di un

ambiente (fase offline). Maggiori saranno i punti dove effettuare le rilevazioni,

maggiore sarà il dettaglio di localizzazione. In seguito, portandosi su un punto del

luogo in esame, sarà possibile, rilevando di nuovo una potenza (fase online),

conoscere la posizione all’interno dell’area d’interesse e confrontarla con quelle

precedentemente rilevate. Fra queste, una avrà "distanza" minore delle altre,

perciò sarà deducibile che l’utente si trova in prossimità dello stesso punto dove

essa è stata prelevata durante la fase offline.

Capitolo 2. Scene Analysis

64

Questa tecnica è stata da noi scelta per motivi di riutilizzo delle risorse, quali gli

stessi AP utilizzati per creare la WLAN (senza doverli aumentare di numero per

ottenere una adeguata precisione), e per motivi economici in quanto non si

necessita di alcun hardware aggiuntivo per l’utente, il quale riutilizzerà la stessa

scheda con cui si collega alla rete wireless. Lo scene analysis si divide perciò in

due fasi, la prima, definita anche fase offline, in cui si effettua la registrazione

delle potenze ricevute dai singoli AP, la seconda, la fase online, dove si propone

un vettore di potenze ricevute (pattern) da confrontare con i vettori registrati nella

precedente fase. La fase offline, in questo caso empirica, potrebbe essere sostituita

dalla stesura di un modello analitico che sostituisce le numerose rilevazioni da

effettuare nell’ambiente. Per formalizzare la nostra trattazione dobbiamo definire

uno spazio delle intensità dei segnali S ed uno spazio delle posizioni P, ossia

l’insieme dei dati e delle soluzioni. Prima di arrivare a risolvere il problema di

localizzazione in genere conviene trovare un modello in grado di risolvere quello

inverso. Nel caso più semplice esso sarà una funzione:

SPf a:

La difficoltà risiede il più delle volte nel trovare la funzione inversa:

PSf a:1−

poiché spesso non esiste e occorre trovare allora un algoritmo che lavori su

ciascun tratto invertibile ed effettui gli opportuni confronti. Per chiarire meglio il

nostro pensiero cominciamo allora a considerare il metodo della triangolazione,

certamente uno dei più utilizzati anche se non per localizzare in interni. Per

descrivere in questo caso la f -1 occorre in primo luogo definire per ciascuna delle

M stazioni base una funzione:

+RSdi a: , per i = 1,..., M


65

capace di restituire la distanza di del dispositivo radiomobile da localizzare (il

nostro obiettivo) dalla stazione base BSi. Nota la posizione reciproca di ciascun

punto di accesso, ossia la pre-conoscenza di cui dobbiamo disporre per impiegare

questa tecnica, con una costruzione geometrica relativamente semplice o

addirittura banale se la localizzazione avviene in un piano, è possibile risalire alla

posizione dell’obiettivo. Se la localizzazione avviene nello spazio occorrono

almeno tre trasmittenti; disponendo di un numero maggiore diviene anche

possibile arrivare a stimare l’errore. Il modello di propagazione di riferimento nel

nostro caso sarà dato da una relazione tra la potenza ricevuta PR e la distanza

simile alla seguente:

LdGGPP RTTR

1

4γ

πλ

=

dove PT è la potenza emessa dall’antenna trasmittente, GT e GR sono

rispettivamente i guadagni dell’antenna trasmittente e ricevente, λ è la lunghezza

d’onda del segnale radio, PR la potenza misurata al ricevitore, d la distanza fra

trasmettitore e ricevitore ed infine L e γ sono costanti empiriche di attenuazione.

Nel caso in cui L = 1 e γ = 2 l’equazione precedente si riduce alla nota formula di

Friis che descrive la propagazione nello spazio libero con assenza di ulteriore

attenuazione. Per poterla applicare anche in situazioni più complesse sono state

introdotte le costanti empiriche γ ed L il cui scopo è tener conto in modo molto

approssimativo di fenomeni di attenuazioni e disturbi. Un modello come quello

illustrato che ha dalla sua il vantaggio della semplicità e della invertibilità si rivela

purtroppo inefficace in quanto a causa del fenomeno dei cammini multipli

complica notevolmente la descrizione fisica del segnale. Infatti, se si assume che

il valore dell’intensità del segnale sia uno solo con al più l’incertezza sulla misura,

l’effetto di disturbi che la fanno oscillare intorno ad un valore centrale durante la

misura sono distribuzioni del tutto imprevedibili.

In definitiva quel che ci occorre è un modello che riesca a prendere in

considerazione questi fenomeni. Vedremo ora una breve rassegna sugli approcci


66

ormai classici per lo studio della propagazione in interni affetta dal disturbo

generato dai cammini multipli.

Molto usati sono i modelli probabilistici poiché consentono di svincolarsi entro

certi limiti dal valutare la struttura geometrica dell’ambiente, evitando per

esempio di tracciare e sviluppare un modello matematico per ciascun cammino.

Un possibile approccio probabilistico si basa sulla possibilità di descrivere la

potenza del segnale tramite una particolare distribuzione e fra tutte queste la più

usata è certamente la distribuzione di Rice:

( )

=+−

202

2

2

22

σν

σσ

νr

Ier

rfr

R

dove r ≥ 0 è l’intensità del segnale, σ è noto come parametro o inviluppo di

Rayleigh, v rappresenta la potenza associata al cammino in linea retta o in line of

sight (LOS) fra trasmettitore e ricevitore, I0 è la funzione di Bessel di prima specie

di ordine 0 modificata. Nel caso in cui v = 0 la distribuzione di Rice coincide con

quella di Rayleigh, usata appunto quando ciascun cammino ha la stessa intensità e

dunque non esiste un cammino privilegiato.

Sebbene l’uso di distribuzioni sia frequente nella simulazione del rumore durante

la progettazione di sistemi radiomobili (ad esempio cellulari) non è molto adatto

per i nostri scopi. Ricordiamo che a noi interessa caratterizzare una certa

posizione. Dopo aver preso in considerazione la possibilità di impiegare le

distribuzioni, quel che ci occorre è un compromesso fra semplicità ed accuratezza.

Per rispondere a tale compromesso può essere adottato un modello elementare in

grado di descrivere l’impatto della presenza di pareti sull’intensità media del

segnale tramite un parametro detto Wall Attenuation Factor (WAF). Precisamente

la potenza del segnale espressa in scala logaritmica (dBm) è calcolata come segue:

( )( ) ( )( ) nAttenuatiod

dnLogdBmdPdBmdP −

−=

0100 10

WAFnWnAttenuatio ⋅= , se nW < C


67

Attenuation=C·WAF, se nW ≥ C

dove d0 è una distanza di riferimento alla quale misuriamo la potenza emessa

P(d0); n è una costante che indica la velocità con cui decresce la potenza al variare

della distanza; d è la distanza tra trasmettitore e ricevitore; nW il numero di

ostacoli tra il trasmettitore ed il ricevitore; WAF è come si è detto il Wall

Attenuation Factor; C è il numero massimo di pareti oltrepassato il quale

l’ulteriore presenza di muri è pressoché ininfluente. A dispetto dei buoni risultati

che si possono ottenere, diverse ragioni ci spingono a non ricorrere a questa

tecnica in quanto non esiste una procedura rigorosa per ricavare sperimentalmente

i due parametri C e WAF e si parla genericamente di media degli effetti di ciascun

ostacolo per il WAF e di una valutazione qualitativa per quel che riguarda C.

Certamente senza una più rigorosa definizione di queste costanti non possiamo

affermare che la tecnica è scalabile e nemmeno che è facilmente adattabile alla

nostra particolare situazione. Un motivo di critica più sottile riguarda la

dipendenza da alcune ipotesi che ne compromettono l’adattabilità ad ambienti

diversi. Per esempio si suppone implicitamente che tutti gli ostacoli abbiano lo

stesso effetto sulle onde radio e, quindi, che ci sia una certa omogeneità di

materiale e dimensione delle pareti. Ancora più contestabile è limitarsi a

considerare l’effetto dell’attenuazione quando il principale fenomeno di disturbo

per i nostri rilevamenti, ossia la presenza di cammini multipli, è il risultato anche

di riflessioni e rifrazioni. Non entriamo ulteriormente nei dettagli poiché il nostro

scopo è semplicemente quello di far comprendere quale sia la complessità dei

modelli che tentano di descrivere la propagazione delle onde radio in interni. Quel

che ci preme è semmai riassumere i motivi per cui non adotteremo l’approccio

propagativo e che in parte sono stati anticipati durante la trattazione. Innanzitutto

l’analisi della propagazione è efficace quando dobbiamo risolvere il problema

inverso al nostro, ossia prevedere il valore dell’intensità una volta che è nota la

nostra posizione rispetto al ricevitore. Se già la potenza del segnale è una funzione

molto complessa della posizione, riuscire ad invertirla per sfruttarne i risultati per

la localizzazione è ancora più difficile. Inutile sottolineare che occuparsi di


68

grandezze fisiche elettriche quando si lavora con uno standard come l’IEEE

802.11b che maschera l’interfaccia elettrica aggiunge ulteriori problemi. Infine, va

osservato che questi modelli sono molto utili per evitare la lunga raccolta di dati

empirici dei segnali di potenza ma alla fine sono troppo dipendenti dal luogo in

cui si utilizzano. Infatti determinare tutti i parametri risulterebbe un lavoro molto

più brigoso che rilevare punto per punto la mappa radio ovvero tutte le potenze

della fase offline. La mappa radio sarà così determinata. Le scelte che rimangono

da fare sarà se mantenere valori deterministici delle potenze rilevate dagli AP in

un punto o mantenere tutta la statistica decidendo di non mediare le rilevazioni

effettuate in un punto, ma di costruire una funzione densità di probabilità. Si pensi

anche alla soluzione di mantenere solamente media e varianza invece che tutta la

distribuzione. Questi due metodi di registrazione della mappa radio determinano

se utilizzare una tecnica deterministica o probabilistica per effettuare la

localizzazione.

La tecnica deterministica significa avere semplicemente due valori da confrontare

tante volte quanti sono i valori della mappa radio. Il primo valore infatti è pescato

dalla mappa costruita in precedenza, mentre il secondo risulterà quello rilevato per

determinarne la posizione. Già la Microsoft, con l’algoritmo RADAR, ha precorso

i tempi gettando le basi per la determinazione del pattern più vicino. La prima

versione dell’algoritmo è stata quella Nearest Neighbor in Signal Space (NNSS).

Questa non fa altro che calcolare la distanza euclidea fra due vettori di potenza per

ogni pattern della mappa radio. Quello a distanza euclidea minore dal vettore da

localizzare vince e lo localizza nelle sue vicinanze. Questo algoritmo nasce dal

criterio Maximum a Posteriori (MAP) per la determinazione del vettore di

potenza più vicino considerando perciò solo la media delle potenze, che risulta

infatti il valore deterministico registrato. Sempre da casa Microsoft sono nate

numerose varianti, vale la pena citare quella in cui si considera la posizione

precedente dell’utente. Infatti, tenendo conto di ciò e che l’utente non può

spostarsi a velocità elevata, un suo monitoraggio viene facilitato dall’esclusione di

posizioni troppo lontane dalle posizioni precedenti. Le tecniche probabilistiche

invece avranno una mappa radio che conterrà la frequenza relativa delle potenze


69

rilevate per ogni AP per ogni punto di prelievo. Se avremo frequenze relative

questa mappa sarà stata costruita empiricamente. Se si vuole tutta la funzione

densità allora si potranno utilizzare i modelli analitici già citati. Inoltre, un gruppo

di ricercatori dell’Università del Maryland ha proposto due ulteriori tecniche

probabilistiche. La prima, ovvero quella del Join Clustering, oltre alle

informazioni statistiche del segnale, necessita di una clusterizzazione che viene

eseguita raggruppando posizioni che hanno alcune caratteristiche comuni,

permettendo di ridurre notevolmente lo spazio di ricerca e, quindi, di ridurre i

calcoli computazionali richiesti dall’algoritmo di localizzazione. Per la

localizzazione si sceglie un numero di AP minimo da considerare, solitamente

quello a potenza maggiore e in seguito si determina, attraverso il criterio

Maximum Likelihood (ML) e alcune semplificazioni, quale pattern della mappa

radio ha più probabilità di essere corretto (o quello più vicino a quello misurato).

Un’altra tecnica, quella della Triangolazione Incrementale, utilizza gli AP in

modo incrementale, uno dopo l’altro, fino a quando non si ottiene una stima

corretta della posizione che presenta un’accuratezza che sta entro una soglia

predeterminata. Quindi, anche se le tecniche probabilistiche danno maggiore

accuratezza ai risultati e inoltre il tempo di calcolo è ridotto grazie all’utilizzo di

cluster, esse comportano difficoltà maggiore sopratutto nella fase offline dove ad

essere registrato dovrà essere un numero notevolmente superiore di informazioni.

Quindi come si è potuto vedere le variabili che influenzano la tecnica di Scene

Analysis anche denominata tecnica di fingerprinting, rendendola complessa, sono

svariate. Innanzitutto, si osserva che ogni ambiente possiede delle caratteristiche

che lo rendono unico, in vista di ciò le problematiche più usuali che vengono

riscontrate nella realtà sono riportate in figura 2.9, dove:

• Numero Access Point: rappresenta il numero di access point che sono

rilevati contemporaneamente dal dispositivo client nel luogo in cui è

localizzato;

• Velocità utente: rappresenta la velocità con cui si muove il dispositivo

client (utente) durante il suo spostamento nell’area da monitorare (m/sec);


70

• Intervallo di scansione: indica l’intervallo di tempo di lettura del sistema

dei valori di RSSI durante la fase di rilevazione del dispositivo;

• Densità di calibrazione: rappresenta la risoluzione dei punti di misura

(sample point) che vengono registrati nell’area di interesse durante la fase

di calibrazione (fase off-line);

• Condizioni ambientali: indica la “condizione” in cui avviene la

localizzazione che può variare con la presenza di altri utenti nell’ambiente,

specificamente la presenza e/o spostamento delle persone nell'area da

monitorare, l’apertura o chiusura di porte e finestre, ed altro.

Figura 2.9 – Fenomeni che condizionano la tecnica di Scene Analysis.

Tutti questi parametri influiscono in maniera rilevante e differente

sull’accuratezza della localizzazione. Mentre le prime quattro variabili possono

essere controllate, la quinta (condizioni ambientali) risulta del tutto casuale e

quindi di difficile controllabilità in quanto l’ambiente viene continuamente

modificato dalla presenza dell’uomo e dai suoi spostamenti. Quindi quest’ultima

variabile risulta essere quella che più influisce sull’errore commesso dal sistema

Capitolo 2. Soluzioni per la localizzazione indoor in WLAN

71

nella localizzazione dell’utente. I segnali che vengono inviati dagli AP hanno una

frequenza di 2,4 GHz e quindi una lunghezza d’onda di 12,5 cm. La presenza del

corpo umano interferisce con la propagazione del segnale radio che raggiunge il

dispositivo client variandone l’intensità e determinando un errore nel sistema di

localizzazione che fornisce un’errata posizione dell’utente. In più questo stato di

imprevedibilità delle condizioni operative dell’ambiente influenzano anche la

stabilità delle altre quattro variabili (numero di access point, velocità utente,

intervallo di scansione, densità di calibrazione) che dovranno essere rielaborate.

2.3 Soluzioni per la localizzazione indoor in WLAN

Dopo aver descritto le tecniche sviluppate nell’ambito della ricerca per la

localizzazione in ambienti indoor, in questa sezione ci soffermeremo sui principali

prodotti software e hardware per la localizzazione indoor in WLAN attualmente

disponibili. Infatti, Wi-Fi è la tecnologia maggiormente rappresentata nell’offerta

attuale, principalmente a causa della grande penetrazione che le reti WLAN di

tipo Wi-Fi possiedono nel mondo delle imprese e, in generale, delle entità

interessate a usufruire di servizi di localizzazione. Il principale vantaggio del

riutilizzo di una tecnologia di comunicazione ampiamente diffusa per finalità

ulteriori a quelle per le quali è stata inizialmente installata è un evidente fattore di

risparmio rispetto all’acquisizione di tecnologie esclusivamente preposte a fornire

servizi di localizzazione.

2.3.1 RADAR di Microsoft

Capostipite della ricerca nel campo della radiolocalizzazione indoor in una

infrastruttura WLAN è il prototipo di progetto pubblicato dalla Microsoft

Research nel marzo del 2000, denominato RADAR, un sistema a radio frequenza

per la localizzazione ed il tracciamento degli utenti all’interno di edifici.

Merito dei progettisti di RADAR non è stato solo quello di assicurare un elevato

livello di accuratezza nella determinazione della posizione tramite la tecnologia

WLAN in commercio, ma, soprattutto, quello di fornire una metodologia di

Capitolo 2. Radar di Microsoft

72

analisi completa, ordinata e coerente di tutte le problematiche fondamentali,

corredate da accurati studi sui principi di propagazione dei segnali nel canale

radio indoor, e le relative soluzioni, con promettenti risultati sperimentali.

Tale lavoro ha spianato la strada per la ricerca successiva, e non solo per le

WLAN. Quasi tutti, in modo più o meno evidente, seguono la scia di RADAR

negli esperimenti e nelle argomentazioni, considerandolo, addirittura, come metro

di confronto per giudicare la precisione raggiunta da un sistema di localizzazione.

Il sistema RADAR si prefigge come scopo la localizzazione di terminali mobili in

ambienti indoor utilizzando un meccanismo di “Scene Analysis” e considerando

come caratteristiche di ogni locazione la potenza ricevuta (RSSI) del segnale

proveniente da stazioni fisse. L’infrastruttura considerata è una WLAN, basata

sullo standard 802.11b. Le stazioni fisse e di posizione nota sono quindi gli AP,

mentre i terminali mobili sono dotati di una scheda WLAN.

Questo sistema differisce da altri in quanto si prefigge di essere “non invasivo”

rispetto all’infrastruttura di comunicazione. In altre parole, non vi deve essere

necessità di una strutturazione dell’ambiente confacente alle sue necessità, bensì

deve essere esso adattabile al luogo nel quale si trova a lavorare.

Figura 2.10 – Infrastruttura di riferimento RADAR.

Capitolo 2. RTLS di Ekahau

73

2.3.2 RTLS di Ekahau

La società californiana Ekahau fornisce soluzioni complete per la localizzazione e

la gestione di applicazioni Location Based con tecnologia WLAN IEEE 802.11.

In figura 2.11 sono riportati sinteticamente gli elementi costitutivi dei sistemi di

posizionamento proposti da Ekahau.

Figura 2.11 – Elementi di alto livello dei sistemi di posizionamento Ekahau.

Possiamo notare che i dispositivi di cui si vuole tracciare, anche dinamicamente,

la posizione possono essere dispositivi Wi-Fi generici, come PDA, PC laptop o

telefoni IP, oppure dispositivi specificamente forniti da Ekahau, quali i tag T201.

Per poter essere localizzati, i dispositivi devono trovarsi all’interno dell’area di

copertura di più AP, che trasmettono i dati collezionati ad un Server di

posizionamento. Ekahau propone diverse applicazioni in grado di interfacciarsi

con i dati raccolti dal Server di posizionamento, al fine di costruire tracce di tipo

real-time, o effettuare ricerche su oggetti e/o persone, o ancora gestire allarmi

personalizzati.

La tecnica di localizzazione utilizzata dai sistemi Ekahau è il già citato

fingerprinting, il cui capostipite è l’algoritmo RADAR proposto nel 2000 da

Microsoft Research. In una prima fase di calibratura del sistema vengono raccolte

informazioni di potenza in punti di test all’interno dell’area di interesse.

Successivamente, il tracciamento e la localizzazione avvengono tramite il

Capitolo 2. AeroScout Visibility system

74

confronto tra le potenze lette istantaneamente e quelle raccolte nella fase di

calibratura.

I tag T201 sono dispositivi Wi-Fi specificamente sviluppati per applicazioni di

localizzazione. Possiedono due LED, che permettono di distinguere a vista la

presenza dei tag all’interno dell’area di interesse, un pulsante di allarme, che

permette di comunicare al sistema centrale l’identità del tag e la sua posizione in

presenza, ad esempio, di situazioni di pericolo e, infine, possono emettere allarmi

sonori attivabili a seguito di particolari condizioni registrate dal sistema di

posizionamento e comunicate da remoto.

Figura 2.12 – Tag T201 prodotti da Ekahau.

2.3.3 AeroScout Visibility system

Come riportato nel sito ufficiale di AeroScout ®, “the AeroScout suite of products

provides Enterprise Visibility Solutions using Wi-Fi wireless networks as an

infrastructure”, i prodotti AeroScout forniscono soluzioni per la localizzazione

utilizzando reti di comunicazione Wi-Fi IEEE 802.11 già installate presso i siti di

interesse. Il sistema di localizzazione sviluppato da AeroScout non è progettato

per funzionare esclusivamente in ambienti indoor, piuttosto è in grado di offrire

servizi di localizzazione in tempo reale per oggetti e/o persone in un qualunque

ambiente che offra copertura WLAN con un numero sufficiente di AP WLAN.


75

Le tecniche di localizzazione che AeroScout dichiara di utilizzare sono basate su

misure di RSSI e di TDoA per segnali scambiati con terminali IEEE 802.11, senza

tuttavia specificare i dettagli sugli algoritmi effettivamente usati.

Il sistema di localizzazione AeroScout può funzionare con dispositivi Wi-Fi

standard, sia terminali che AP, ma sono proposte anche soluzioni proprietarie per i

terminali da localizzare, detti tag, e anche per gli AP, chiamati Location

Receivers. In figura 2.11 riportiamo il tag T2 che possiede caratteristiche e

funzioni specifiche per la localizzazione, tra cui citiamo:

• Una batteria rimovibile che garantisce una durata di funzionamento di

circa 4 anni;

• Una piccola memoria riscrivibile capace di contenere 10 messaggi da 10

Bytes ciascuno;

• La presenza di un bottone che può essere programmato per generare, ad

esempio, eventi di allarme;

• La presenza di un’interfaccia di comunicazione a corto raggio operante a

bassa frequenza (125 kHz) per la comunicazione con opportuni dispositivi

di interrogazione RFID, detti Exciters, di cui parleremo nel seguito;

• Dimensioni fisiche molto ridotte (62 mm x 40 mm x 17 mm) che

permettono di associare facilmente i tag a persone o a merci;

• Un sensore di movimento che permette di rilevare quando il tag rimane

fermo in una posizione e, di conseguenza, permette di limitare la

trasmissione di segnali per la localizzazione ai soli momenti in cui esso sia

in movimento; in questo modo è possibile al contempo allungare il tempo

di vita delle batterie ed evitare di trasmettere nel mezzo radio informazioni

ridondanti.

L’AeroScout Location Receiver, riportato in figura 2.14, è un dispositivo assai

simile ad un Access Point, che però possiede esclusivamente funzionalità di

localizzazione e non di inoltro di dati. Infatti, pur essendo pienamente conforme

agli standard di trasmissione IEEE 802.11b/g, il Location Receiver non accetta


76

l’associazione di terminali WLAN per la trasmissione di dati, ma si occupa

esclusivamente di raccogliere misure di TDoA e di RSSI al fine di localizzare i

terminali presenti all’interno del proprio raggio di copertura. Per localizzare un

tag e/o un dispositivo WLAN standard è richiesta la copertura contemporanea di

almeno tre Location Receiver o AP standard.

Figura 2.13 – Tag T2 di AeroScout ®.

Secondo il produttore la copertura radio offerta dal dispositivo Location Receiver

si estende su un’area maggiore di quella ottenibile con Access Point standard. I

dispositivi AeroScout Exciter operano alla frequenza di 125 kHz, con aree di

copertura più limitate, pari al massimo a 6 metri, e hanno la funzione specifica di

interrogare i tag T2 che ricadono nel loro raggio di copertura. I tag che ricevono

un segnale di sveglia da parte di un Exciter emettono a loro volta un segnale Wi-

Fi diretto ad un Location Receiver o ad un semplice AP, fornendo informazioni in

tempo reale sul suo passaggio in prossimità della posizione nota in cui è posto

l’Exciter. Gli Exciter sono disponibili con due diversi fattori di forma: uno di

dimensioni maggiori che permette, ad esempio, di implementare varchi ad accesso

controllato; un secondo, di dimensioni decisamente minori, che può essere

facilmente spostato per rilevare tag in aree di interesse specifiche.

Come molti altri produttori di sistemi per la localizzazione, anche AeroScout

fornisce software che si basano sui dispositivi fin qui presentati e forniscono

ambienti grafici per il controllo della posizione degli oggetti e/o delle persone da

localizzare.


77

Figura 2.14 – Un AeroScout® Location Receiver

2.3.4 Cisco Wireless Location Appliance

Anche Cisco Systems ® propone una soluzione integrata per fornire servizi di

localizzazione e tracciamento tramite tecnologia WLAN, con i dispositivi della

serie 2700/2710 detti Wireless Location Appliance. Il dispositivo Cisco 2700

Wireless Location Appliance è riportato in figura 2.15.

A differenza di altri competitori industriali, Cisco illustra ampiamente le modalità

di funzionamento dei suoi prodotti di localizzazione, che si fondano ancora una

volta sulla tecnica del fingerprinting. Un dispositivo di Location Appliance riceve

da parte degli Access Point disponibili nella rete le misure di RSS ricevute

durante la comunicazione con i dispositivi WLAN da localizzare e le confronta

con:

• Le misure ottenute durante la fase offline di calibrazione del sistema, che

consiste nella raccolta da parte del sistema delle misure di potenza

elettromagnetica trasmesse da un dispositivo WLAN portatile. Il

dispositivo viene posizionato su una griglia di punti all’interno dell’area di

interesse e, in presenza di edifici su più livelli, le operazioni sono ripetute

per ciascun piano dell’edificio;


78

• I modelli di propagazione applicati all’ambiente specifico, accompagnati

da informazioni quali la presenza di ostacoli in muratura, porte o, ancora,

di altri oggetti ingombranti.

Figura 2.15 – Cisco 2700 Wireless Location Appliance.

L’utilizzo combinato di tecniche predittive del segnale elettromagnetico e di

confronto con misure prese a campione in posizioni selezionate può condurre ad

un miglioramento delle prestazioni della localizzazione.

Cisco dichiara, ancora in maniera poco comune, le specifiche sull’accuratezza dei

propri sistemi di localizzazione con WLAN, affermando di riuscire a localizzare

oggetti con una precisione superiore ai 10 metri nel 90% delle misure. Si fa

notare, inoltre, che tali prestazioni medie dipendono in maniera significativa dalle

caratteristiche del particolare ambiente considerato.

Attualmente sono disponibili numerose altre soluzioni per la localizzazione indoor

tramite tecnologia WLAN. Queste soluzioni, tuttavia, non si differenziano in

maniera sostanziale da quelle che abbiamo analizzato fin qui, poiché si fondano

tutte sulla tecnica di localizzazione, già ampiamente descritta, del fingerprinting.

Capitolo 3. Algoritmi e metodi di localizzazione indoor

79

Capitolo 3

Algoritmi e metodi di localizzazione indoor

Come si è visto nel precedente capitolo, le tecniche di posizionamento che

possono essere impiegate per determinare le coordinate di un terminale mobile,

provvisto di scheda Wi-Fi, in un ambiente indoor, a sua volta coperto da una rete

Wi-Fi, si basano sull’elaborazione di un insieme di parametri misurati. Questi

parametri possono essere: il tempo, un angolo o il livello di potenza. In funzione

della scelta dei parametri, è possibile costruire una differente procedura

matematica che determina la posizione. Per costruire tale procedura, la rete deve

essere in grado di gestire e rilevare questi parametri e quindi disporre di risorse

hardware e software appropriate.

Esaminando i requisiti del nostro progetto di Location-based Services (LBS),

possiamo osservare che la principale restrizione è data dalle schede Wi-Fi

disponibili (sui dispositivi mobili e sugli AP) e dal sistema operativo su cui

operiamo, in questo caso, il Symbian OS, disponibile sul Nokia modello E51. Tale

sistema permette l’accesso all’informazione relativa ai livelli di potenza ricevuti

dai diversi AP, cioè, i valori di Received Signal Strength Indication (RSSI).

Allora, la tecnica che si deve utilizzare deve far riferimento a questo parametro o

comunque, utilizzare un approccio che, partendo dal RSSI, sia in grado di

processare altri parametri, quali, ad esempio, la distanza o il ritardo. Quindi, è

possibile ottenere una tecnica molto duttile che può essere diversificata a seconda

dei parametri che si vogliono prendere in esame.

Dal momento che i parametri a nostra disposizione sono fortemente dipendenti

dall’ambiente (indoor), e quindi soggetti a fenomeni di multipath che fanno

variare in modo considerevole i valori di RSSI a nostra disposizione, per ottenere

una tecnica affidabile bisogna far ricorso ad una serie di valori di riferimento

(punti fingerprinting o impronte digitali) che possono essere presi in una fase

precedente, detta offline, e dei quali si conoscono le coordinate e i rispettivi valori

Capitolo 3. Classificazione

80

di RSSI. In seguito, una volta attivato il sistema di localizzazione (fase online), in

base alla potenza ricevuta dal terminale mobile, è possibile effettuare una stima

della sua posizione in funzione dei punti di riferimento. Allo scopo di ottenere un

livello di accuratezza e precisione maggiore, è preferibile utilizzare una

combinazione di metodi basati sui valori di RSSI.

In particolare, per organizzare meglio l’esposizione e per potersi orientare nella

varietà di approcci distinguiamo tra i metodi denominati solitamente di

fingerprinting e quelli di filtraggio. Prenderemo anche in considerazione un

approccio al problema basato sulle reti neurali che non può essere ricondotto a

nessuna delle due categorie.

3.1 Classificazione

Abbiamo già sottolineato la varietà di scelte di progetto che ci si accinge a

risolvere ed in parte abbiamo già evidenziato che questa varietà è dovuta alla

diversità degli approcci possibili alla localizzazione. Ricordiamo che la natura

stessa dell’output del sistema e dei dati preliminari del problema dipendono dal

metodo di localizzazione adottato. Per questa ragione si sente il bisogno di una

classificazione che ci consenta di mettere ordine anche nelle nostre decisioni

progettuali. Precisiamo che parlando di varietà di metodi non intendiamo

affermare che quelli proposti siano molti, anzi al contrario le pubblicazioni

sull’argomento sono esigue né potrebbe essere diversamente visto che l’idea di

impiegare reti wireless per la localizzazione, come pure la loro diffusione, è

abbastanza recente, quanto piuttosto che essi presentino molte differenze e siano

privi di qualsiasi soluzione di continuità e tanto meno di evoluzione o di

derivazione reciproca.

Precisamente distingueremo tra approcci che si limitano a considerare quella che

viene definita “impronta digitale” del segnale, caratteristica di una certa posizione,

e i metodi di filtraggio utilizzati per ridurre l’errore di stima.

Chiaramente avremmo potuto scegliere altri criteri di classificazione. Per esempio

si potrebbe distinguere tra metodi deterministici e metodi probabilistici, tra

Capitolo 3. Metodi di fingerprinting

81

algoritmi che forniscono univocamente e staticamente una risposta e algoritmi che

apprendono sulla base dei propri errori. Ci è però sembrato opportuno scegliere

quella classificazione che fosse in grado di cogliere le differenze sostanziali sia

dal punto di vista teorico sia da quello pratico fra i vari paradigmi risolutivi. Il

criterio da noi adottato ci è parso più significativo poiché distingue tra i modelli

che per dare una risposta si limitano ad organizzare e confrontare i dati raccolti

empiricamente e modelli che attuano una procedura di riduzione dell’errore di

stima

3.2 Metodi di fingerprinting

Il termine fingerprinting, che abbiamo già usato direttamente o tradotto con

impronta digitale, si riferisce alla tecnica di localizzazione Scene Analysis il cui

presupposto è la possibilità di associare una qualche caratteristica del segnale

detta impronta, che si riferisce all’intensità di segnale radio delle posizioni

appartenenti ad un insieme di lavoro definito a priori. Si deduce quindi che tutte le

strategie risolutive che consideriamo in questo paragrafo ricercano la soluzione in

un insieme discreto di posizioni o stati e che occorrerà sempre mappare il segnale,

ossia misurare sperimentalmente l’impronta in ciascuno stato. Definiamo appunto

fase di mappatura, detta anche training o fase offline, quel complesso di scelte,

misure ed elaborazioni che devono essere compiute prima di poter operare con un

metodo di impronta digitale nello spazio di lavoro ed il cui scopo è la costruzione

della pre-conoscenza, ossia le informazioni preliminari necessarie per la

localizzazione che avviene in tempo reale.

Nel precedente capitolo abbiamo fatto rilevare che proprio la fase di mappatura

costituisce il principale inconveniente di questi approcci poiché comporta una

mole di lavoro proporzionale alle dimensioni del contesto in cui operiamo e

poiché costringe a scegliere a priori il numero di stati che saranno usati per

localizzare, scelta che può condizionare le prestazioni del sistema. D’altra parte

criticando gli altri metodi nel corso della trattazione implicitamente ne abbiamo

messo in evidenza le qualità. Con uno schema ad impronta possiamo infatti

Capitolo 3. Metodo Nearest Neighbor in Signal Space

82

ignorare quasi completamente le caratteristiche fisiche e geometriche

dell’ambiente in cui operiamo e non siamo neppure costretti ad una analisi

approfondita delle caratteristiche elettriche della scheda di rete.

L’aspetto se vogliamo più critico riguarda semmai il presupposto stesso che

l’impronta sia realmente un elemento significativo per l’individuazione di uno

stato. La risposta a questo quesito può essere data solo sperimentalmente ed è

proprio ciò che faremo nel capitolo 4. Nel seguito prenderemo in esame i due

principali metodi basati sul riconoscimento dell’impronta.

3.2.1 Metodo Nearest Neighbor in Signal Space

A dispetto del nome la tecnica del Nearest Neighbor in Signal Space (NNSS)

figura sicuramente tra gli approcci più semplici e, forse, più efficaci al problema

della localizzazione in interni. L’impronta caratteristica del segnale si presenta in

questo caso come un vettore le cui componenti sono le intensità dei segnali

provenienti da ciascun access point.

Allora, assumendo l punti di riferimento {L1, L2,…, Ln}, ognuno caratterizzato

dalla propria impronta F = {F1, F2, …, Fn}, nella fase online, il terminale riceve,

in un dato istante di tempo, dagli AP i corrispondenti valori di RSSI e li

memorizza all’interno di un vettore S = {s1, s2,.., sn}T che chiameremo campione,

dove n rappresenta il numero di AP presenti. Ogni impronta F, associata ad una

determinata posizione i, può essere rappresentata come un vettore Fi = {p i1, p

i2,…,

pin}

T, composto dal valor medio RSSI di ogni AP presente. A questo punto, si

effettua una semplice selezione dell’impronta in base alla vicinanza al valore

RSSI misurato correntemente. Per fare ciò, si deve calcolare la minima distanza

spaziale tra il valore corrente e quelli misurati in fase offline. Tale distanza viene

determinata attraverso una regola di decisione che può essere così espressa:

jkFkSDFjSD ≠∀≤ ),,(),(

dove S si riferisce al vettore contenente i valori RSSI dei diversi AP, Fj

all’impronta nella postazione corrente, Fk rappresenta le diverse impronte

Capitolo 3. Metodo Nearest Neighbor in Signal Space

83

misurate in fase offline, ed infine D rappresenta una funzione che calcola la

distanza spaziale.

Uno dei metodi più generalmente utilizzati per il calcolo di distanze spaziali è la

differenza euclidea, determinata a partire dalla seguente equazione:

pN

i

p

iii

psN

Lp

/1

1

11

−= ∑

= ω

dove Lp rappresenta la differenza euclidea, N il numero di AP rilevati, si e pi

rappresentano rispettivamente l’impronta e il valore corrente del RSSI dell’i-

esimo AP. Poiché ci troviamo nel caso euclideo p = 2 e ωi = 1, quindi:

2222

211 )(...)()( NN pspspsD −++−+−=

Il principale limite di questo metodo risiede nel fatto che la soluzione rappresenta

soltanto il valore più vicino, quindi, per avere una stima sufficientemente corretta,

è necessario disporre di un numero adeguato di campioni che, in senso euclideo,

siano il più possibile vicini al punto da stimare.

Per ovviare a tale limite abbiamo utilizzato il metodo del centroide che consiste

nell’associare alle coordinate di ciascun impronta una probabilità in funzione dei

dati d’ingresso e nell’effettuare la stima della posizione in relazione ad esso.

Allora, essendo p(i) la probabilità della posizione xi appartenente ad un insieme

X , il quale contiene la lista di tutte le coppie di coordinate delle impronte,

ordinate in modo decrescente in base alla probabilità ad esse associata, possiamo

scrivere la seguente relazione:

∑

∑

=

==N

i

N

ii

ip

ipx

x

1

1

)(

)(

Capitolo 3. Metodo probabilistico

84

dove ix corrisponde all’i-esimo valore dell’insieme X ed N al numero totale di

elementi dell’insieme.

Per determinare la probabilità p(i) può essere utilizzata la funzione di

distribuzione Gaussiana, ovvero:

∏=

−

−−=

M

j

jj ssip

0

2

22exp

2

1)(

σπσ

dove M rappresenta il numero di AP, σ la deviazione standard, sj il valore di

potenza ricevuto dal j-esimo AP e js−

la media della potenza ricevuta dai campioni

nella fase offline dall’AP j-esimo.

3.2.2 Metodo probabilistico

Come è ormai chiaro uno degli aspetti più critici di un metodo di fingerprinting

riguarda la natura delle impronte, la loro capacità di caratterizzare il segnale e le

conseguenti modalità di confronto. Uno dei vantaggi dell’algoritmo probabilistico

risiede appunto nella possibilità di evitare di definire l’impronta tramite un

insieme di parametri, la cui efficacia come impronte è tutta da verificare sia

sperimentalmente che teoricamente. Scegliere ad esempio un vettore di valori

medi come si è fatto nel paragrafo precedente pone infatti quesiti sull’efficacia di

una tale scelta. Il metodo che evidenzieremo ora, invece, cerca di stimare la

posizione in funzione delle impronte digitali ottenute in fase offline, utilizzando le

definizioni di probabilità condizionata e il teorema di Bayes. Per far ciò, è

necessario conoscere la distribuzione di probabilità che meglio modellano i valori

RSS ottenuti in fase offline oppure mediante l’utilizzo di un modello di

propagazione utilizzato per stimare il comportamento del segnale radio.

Per ogni posizione L sulla mappa, si può stimare la funzione densità di probabilità

condizionata P(F|L) a partire da un numero elevato di campioni contenenti i valori

RSSI che definiscono l’impronta di L.

Capitolo 3. Metodo probabilistico

85

Un modo per determinare la distribuzione di probabilità è la costruzione di un

istogramma con i valori RSSI prelevati da ogni AP in ogni punto. Tali valori

verranno poi pesati in funzione dell’istogramma associato ad ogni AP in ogni

posizione, ovvero P(s1|L), P(s2|L),…, P(sN|L).

Un’altra definizione di distribuzione di probabilità è pensare ad una funzione di

distribuzione Gaussiana. In pratica, quello che si fa è prendere n campioni di RSS

per uno stesso AP su quella posizione e poi assumere che essi abbiano una

distribuzione Gaussiana con media µ e deviazione standard σ. Quindi

considerando un singolo AP è possibile scrivere:

∑=

−−=

n

i

ips

nLsP

12

2

2

)(exp

2

11)|(

σσπ

in questa equazione s rappresenta il valore RSSI corrente e pi il valore RSSI di un

punto campionato in fase offline.

Quindi, prendendo in considerazione più AP e assumendo che essi siano

indipendenti tra di loro, è possibile stimare la probabilità condizionata come:

P(F|L) = P(s1|L)P(s2|L),…, P(sN|L)

In tal modo è possibile stimare la somiglianza di una data impronta con la

posizione corrente. Assumendo che la probabilità P(L) per ogni posizione è nota

(inizialmente potrebbero essere tutte uguali), si può applicare il teorema di Bayes

per trovare la probabilità condizionata della posizione L, data un’impronta F,

come si mostra nella seguente espressione:

)()|(

)()|(

)(

)()|()|(

kLk k LPLFP

LPLFP

FP

LPLFPFLP

∑ ∈

==

Assumendo che esistono due posizioni con le loro rispettive impronte A(LA) e

B(LB), la regola di decisione di Bayes potrebbe scegliere A anziché B poiché:

P(LA|F)> P(LB|F)

Capitolo 3. Metodi di filtraggio

86

P(F|LA) P(LA)> P(F|LB) P(LB)

Con informazione addizionale riguardante la distribuzione delle locazioni L,

questo metodo sarebbe utile per stimare la posizione. Tuttavia, saranno necessari

una grande quantità di campioni durante la fase offline dei valori RSSI per ogni

postazione per raggiungere un grado di accuratezza accettabile.

3.3 Metodi di filtraggio

Nei sistemi di posizionamento indoor le fluttuazioni dei valori RSSI causano

problemi nell’accuratezza della stima. Quindi, il terminale ha bisogno di essere

tracciato continuamente e i filtri possono essere utili in quanto si adattano ai

percorsi seguiti per ridurre così l’errore nella stima.

In applicazioni di tracciamento è comunemente utilizzato un filtro di Kalman. Lo

svantaggio di questo filtro è dato principalmente dal fatto che definisce un

modello lineare, il quale non si avvicina al comportamento reale del parametro in

studio. Nel nostro caso questo parametro si riferisce al segnale descritto mediante

diversi valori RSSI (livelli di potenza) che dipendono dal canale radio il quale non

ha un comportamento lineare nel tempo. Esistono due versioni del filtro di

Kalman che cercano di simulare comportamenti non lineari: Extended Kalman

Filter (EKF) e Unscented Kalman Filter (UKF). La versione estesa EKF utilizza

un approccio differenziale, invece la UKF utilizza trasformazioni deterministiche

intorno ad una variabile aleatoria.

Un’alternativa ai filtri di Kalman è il Particle Filter che esegue operazioni più

semplici e può essere implementato per risolvere problemi di natura non lineare e

di distribuzioni non Gaussiane. Considerando come informazioni addizionali la

distanza percorsa e informazioni sulla mappa dei valori di potenza, si potrebbero

migliorare le prestazioni di questo filtro. Infatti, si assume che l’informazione

sulla mappa non è lineare e distribuita nello spazio, mentre la distanza percorsa

caratterizza solo una parte del comportamento del movimento, per esempio,

potrebbe non considerare l’informazione sull’orientamento. Nel seguito di questo

paragrafo sono specificate le caratteristiche matematiche e fisiche di questi filtri.

Capitolo 3. Filtro di Kalman

87

3.3.1 Filtro di Kalman

Il Filtro di Kalman che viene presentato è del tipo EKF. Esso modella un processo

in tempo discreto, utilizzando le seguenti equazioni lineari differenziali

stocastiche, per un dato vettore stato x(k), un dato vettore misura z(k) e un vettore

controllo u(k):

)()()(

)1()()1()(

kvkHxkz

kwkBukFxkx

+=−++−=

dove le matrici F, B e H definiscono la transizione lineare e la fase di misurazione,

mentre i vettori aleatori n e v rappresentano rispettivamente il processo e il rumore

misurato, che sono assunti come distribuzioni normali, bianche e indipendenti,

cioè:

),0()(

),0()(

RNvp

QNnp

∝∝

con le matrici Q e R rispettivamente di covarianza dell’errore sullo stato e

dell’errore sulle misure. Per un sistema basato sull’utilizzo di RSS, si possono

definire i parametri come segue:

)(

)()(,

)(

)(

02

0

0

02

)(

0010

0001,0,

1000

0100

010

001

)(

)()(,

)(

)(

)(

)(

)(

2

2

ke

kekv

ka

ka

t

t

t

t

kw

HBt

t

F

ky

kxkz

kv

kv

ky

kx

kx

y

x

y

x

RSS

RSS

y

x

=

∆

∆

∆

∆

=

==∆

∆

=

==

Capitolo 3. Filtro di Kalman

88

dove x e y sono le coordinate della posizione; vx e vy rappresentano le velocità

rispetto al sistema di riferimento adottato; ax e ay rappresentano le accelerazioni

rispetto agli assi e sono legate a una distribuzione aleatoria con le stesse

caratteristiche del rumore; z è la posizione stimata a partire delle misure dei valori

RSSI. Allora lo stato può essere calcolato utilizzando le seguenti equazioni di

predizione e correzione:

)())(()(

)),(ˆ)()(()(ˆ)(ˆ

,))(()()(

,)1()(

),1(ˆ)(ˆ

1

kPHkKIkP

kxHkzkKkxkx

RHkHPHkPkK

QFkFPkP

kxFkx

TT

T

−

−−

−−−

−

−

−=

−+=

+=+−=

−=

dove P-(k) è la matrice di covarianza corrispondente alla predizione dello stato,

mentre P(k) è la matrice di covarianza corrispondente allo stato stimato

considerando anche le misure correnti dei valori RSSI.

Figura 3.1 – Schema semplificato di un filtro di Kalman.

Capitolo 3. Particle Filter

89

La figura 3.1 mostra uno schema semplificato del funzionamento del filtro di

Kalman. Come è possibile vedere esso si divide in due strati, quello visibile dove

si trovano i parametri esterni al sistema e quello nascosto prodotto dalla procedura

di calcolo che modella il funzionamento del filtro secondo lo stato.

3.3.2 Particle Filter

Il particle filter, a differenza del filtro di Kalman, si basa sulla stima della

funzione densità di probabilità (f.d.p.) a posteriori dello stato x(k), date le

osservazioni precedenti di Z(k), ovvero:

∑=

−≈N

i

ii kxkxkwkZkxp1

))()(()())(|)(( δ

dove xi(k) è l’i-esimo campione del punto o della particella, mentre wi è il peso

della particella.

Infine si descrivono in maniera molto sintetica i passi di un algoritmo generico

particle filter:

• Inizializzazione: sono campionate N particelle { }Nixi ...1),0( = e

inizialmente esse sono tutte uniformemente distribuite;

• Predizione: per ogni particella xi(k), data una nuova particella xi(k+1), si

calcola la f.d.p. transitoria p(x(k+1)|xi(k));

• Importance Sampling: per ogni nuova particella xi(k+1) si calcola la

funzione dei pesi wi(k+1)=p(z(k+1)|xi(k+1));

• Normalizzazione e Resampling: i pesi sono normalizzati e nel passo di

resampling le particelle con peso più basso sono cancellate e quelle con

peso più alto sono raddoppiate.

Un’osservazione rispetto alla f.d.p. transitoria p(x(k+1)|xi(k)) ed al suo

aggiornamento p(z(k+1)|xi(k+1)): esse devono essere funzioni note e non

Capitolo 3. Metodi basati sulle reti neurali

90

necessariamente di tipo Gaussiano. Per il caso RSSI i pesi possono essere

determinati tramite la seguente equazione:

+−+++−+−

=++=+2

22

2

))1()1(())1()1((

2

1))1(|)1(()1( σ

σπ

kykykxkx

ii

RSSIi

RSSIi

ekxkzpkw

In questa equazione si assume che la posizione stimata attraverso i valori RSSI è

una distribuzione Gaussiana con media, la posizione esatta oppure una stima di

essa.

Ciò che manca per definire il funzionamento del particle filter è il suo modello

dinamico che rappresenta il comportamento delle particelle su un sistema di

coordinate cartesiane.

]2,0[),)tan(2,(

]10,0[,)1,(

)sin(

)cos(

1

121

11

11

παπαα

αα

=∆−=

=∆=

+∆+=+∆+=

−

−−−

−−

−−

contt

vaN

msvcontmsvNv

ntVYY

ntVXX

tit

tt

tttii

tttii

dove le coordinate (Xi,Yi) descrivono le posizioni delle particelle in un

determinato momento; vt e αt rappresentano rispettivamente la velocità e la

direzione delle particelle all’istante t; nt-1 rappresenta il rumore del sistema con

distribuzione Gaussiana. Questi valori di vt e αt, devono essere ottenuti mediante

sensori di misura dell’inerzia e per tale motivo le formule finora mostrate

rappresentano soltanto un modello euristico.

3.4 Metodi basati sulle reti neurali

Discutiamo in questo paragrafo un approccio che ci è difficile da classificare in

una delle due categorie che abbiamo definito a riprova della natura il più delle


91

volte arbitraria di una classificazione. Un modello a rete neurale, almeno per

quanto riguarda i nostri scopi, ha come obiettivo di trovare una connessione fra

l’input (le misure provenienti dagli access point) con l’output (la posizione). In

particolare, le reti neurali artificiali (RNA) sono sistemi di processamento

dell’informazione distribuiti e paralleli ispirati alla struttura e al funzionamento

delle reti neurali biologiche. Questi sistemi di processamento dell’informazione

sono concepiti per emulare certe funzioni eseguite dal cervello umano, quali

riconoscimento dei patterns, classificazioni, apprendimento, memoria e

l’astrazione della conoscenza fra le altre funzioni.

Queste reti sono formate dall’insieme di neuroni artificiali collegati tra loro in

diverse modalità dove ogni collegamento è caratterizzato da un peso per il

neurone che sta a valle verso il neurone a monte. I neuroni artificiali

rappresentano una particolare informazione, cioè, analogamente ai sistemi

biologici, lo spazio neurale viene utilizzato per dare una rappresentazione degli

eventi esterni. Le grandezze che lo caratterizzano sono mostrate in figura 3.2.

Figura 3.2 – Architettura del neurone artificiale.

Il vettore X = (X1,…, Xn) rappresenta il vettore degli ingressi al neurone che

possono essere a loro volta le uscite di altri neuroni quando sono presenti delle

sinapsi; il vettore W = (W1,…, Wn) è il vettore dei pesi che rappresenta cioè il peso

da attribuire alla sinapsi corrispondente; A non è altro che la Funzione di


92

attivazione ossia la funzione che stabilisce il livello di attivazione del neurone

artificiale come conseguenza degli ingressi ricevuti. In corrispondenza al piano

biologico questa funzione identifica gli insiemi dei valori che assume il Potenziale

di Membrana a Riposo (PMR) come conseguenza della sommatoria spazio-

temporale dei potenziali postsinaptici. Le funzioni più comunemente usate sono:

funzione identità, funzione rampa, funzione Gaussiana, ecc... F(A) invece è la

Funzione di propagazione che stabilisce quando il neurone è autorizzato a dare

un’uscita, corrisponde quindi alla Funzione di uscita.

Un’alternativa alle reti neurali sono le reti neurali competitive che costituiscono il

modo in cui la rete cerca di scoprire caratteristiche e patterns speciali dai dati di

entrata, senza che ci sia alcuna supervisione esterna. Questo tipo di rete utilizza

algoritmi d’apprendimento senza supervisione per eseguire compiti come:

• Clustering (raggruppamento): consiste nel raggruppare o dividere un

insieme di dati in sottoinsiemi separati (clusters), in modo tale che i

patterns appartenenti a uno stesso cluster siano molto simili fra di essi,

mentre i patterns appartenenti a clusters diversi siano il più possibile

differenti;

• Vector quantization: questo tipo di compito è molto simile al clustering.

Lo spazio di entrata è diviso in diverse regioni connesse. Ciascuna regione

viene rappresentata utilizzando un unico vettore. Ciascun pattern nello

spazio di entrata appartiene a una regione particolare (quella che possiede

il vettore più vicino al pattern);

• Distribuzione di probabilità: Il metodo consiste nell’ottenere una

descrizione riassuntiva di grandi volumi di dati estratti da una

distribuzione di probabilità. La descrizione potrebbe consistere in un

insieme di punti dello spazio di dati, tale che la distribuzione di questi

punti costituisca un’approssimazione della distribuzione originale;

• Estrazione di caratteristiche: il metodo consiste nello scoprire le

caratteristiche più importanti (cioè quelle che posseggono maggiore

variazione) nello spazio di dati. Seguendo questo metodo, patterns

Capitolo 3. Reti Winner-take-all

93

appartenenti a clusters differenti possono essere individuati da alcune

caratteristiche. L’estrazione di caratteristiche porta a una riduzione della

dimensione dei patterns di entrata.

Queste caratteristiche permettono di affermare l'utilità delle reti neurali nella

gestione di un sistema di localizzazione, dove i neuroni in questo caso

rappresentano il legame tra la posizione da stimare e un determinato punto, noto

in fase offline mediante le sue coordinate e mediante i suoi valori RSSI.

L'approccio a strati agevola l'analisi della stima e potrebbe aumentare la

precisione del sistema giacché, a differenza degli algoritmi precedenti, non si basa

soltanto su una procedura matematica per stimare la posizione, ma anzi, prima di

restituire la posizione, si devono eseguire una serie di analisi, che man mano

riducono l'insieme di possibile soluzioni. Infatti, i risultati ottenuti potrebbero

essere utilizzati per aggiornare l'informazione del sistema oppure aggiustarsi alle

condizioni reali dell'ambiente in cui si implementa, quindi, questi punti fissi

potrebbero essere cancellati o aggiornati in funzione delle caratteristiche

aggiuntive di analisi della rete neurale.

3.4.1 Reti Winner-take-all

Le reti winner-take-all costituiscono il principale approccio per eseguire

l’apprendimento competitivo. Questo meccanismo presuppone l’utilizzo dello

spazio neurale (strati di neuroni) per la rappresentazione delle categorie, le quali

vengono organizzate su questo spazio in maniera spontanea attraverso

l’interazione con gli eventi esterni. Le principali caratteristiche di questo tipo di

rete sono le seguenti:

• La rete neurale è organizzata in strati. Vi sono collegamenti eccitatori fra i

neuroni appartenenti ai diversi strati e collegamenti inibitori fra i neuroni

appartenenti allo stesso strato;

• I neuroni nello strato di uscita stabiliscono una gara fra loro per

rappresentare il pattern d’ingresso, ognuno inibendo gli altri con il suo


94

livello di attivazione attuale. Dopo la gara, il neurone vincitore è attivato, e

il suo vettore peso sarà aggiustato per avvicinarlo al pattern di ingresso;

• I pesi sinaptici sono aggiornati in accordo ad una regola Hebbiana in

quanto la variazione del peso della connessione tra due nodi i e j è

proporzionale al prodotto delle due attivazioni. In questo modo il peso

della connessione aumenta se i due nodi sono correlati.

L’idea base di questo principio di organizzazione è la seguente: i neuroni o

insieme di neuroni, che rappresentano una porzione dello spazio neurale,

competono fra loro per rispondere alla presentazione di una particolare categoria

di eventi esterni. La gara si basa sui diversi livelli di attività raggiunti dai diversi

neuroni, data la presentazione di un evento esterno, nonché in una struttura di

inibizione laterale esistente fra i neuroni. Una rete winner-take-all è composta da

diversi strati. Le caratteristiche del processamento cambiano a seconda di dove

questo si svolge: fra gli strati o all’interno di uno strato particolare. Quando il

processamento ha luogo fra gli strati ciascun neurone in uno strato inferiore si

collega a tutti i neuroni ubicati nello strato immediatamente superiore e tutte le

connessioni sono eccitatrici, si ottiene così un flusso dell’informazione di tipo

feedforward. Il processamento all’interno di un strato viene generalmente

caratterizzato da:

• I neuroni dentro uno strato (tranne nello strato di entrata) si dispongono in

clusters, i quali possono ( o non possono) definire regioni di intersezione

fra di loro;

• Ciascun neurone dentro un cluster si collega con i restanti neuroni del

cluster attraverso connessioni inibitrici;

• L’attività fluisce in maniera ricorrente fra i neuroni del cluster finché non

sia raggiunto uno stato nel quale solo un neurone è in grado di mantenersi

attivo.

I neuroni vincitori per ciascun cluster saranno quelli che invieranno la loro uscita

al prossimo strato. Dunque, il pattern di entrata ad uno strato superiore sarà quello


95

che risulta dai processi inibitori che accadono nello strato immediatamente

inferiore. In una rete winner-take-all l’apprendimento è competitivo giacché il

processo di aggiornamento dei pesi si verifica in funzione dei neuroni vincitori.

Un neurone “vince” la gara quando risponde con un livello di attività più elevato

rispetto agli altri neuroni del cluster alla presentazione di un particolare pattern

originato dalle uscite dei neuroni dello strato inferiore. Il vettore di pesi del

neurone vincitore è modificato e tale modifica fa sì che il neurone risponda ancora

con maggiore forza a successive presentazioni dello stesso pattern oppure di

patterns simili. Questo fatto porta a una “specializzazione” graduale del neurone

nel riconoscimento di patterns particolari.

Figura 3.3 – Architettura tipica di una rete winner-take-all.

Il processamento dell’informazione in una rete winner-take-all può essere

descritto nei seguenti termini: l’organizzazione raggiunta da ciascuno strato

durante il processo d’apprendimento permette che ogni strato neurale esegua un

processo di estrazione di caratteristiche dai patterns che arrivano dallo strato

immediatamente inferiore. L’organizzazione gerarchica degli strati garantisce che

le caratteristiche ricavate siano ogni volta più astratte. In altri termini, le

caratteristiche comuni scoperte in strati superiori sono ogni volta meno evidenti,

quando si considerano i patterns primari presentati nello strato di entrata. Di

Capitolo 3. Reti Self-organizing map

96

conseguenza, nell’ultimo strato si raggiunge l’implementazione di un sistema di

categorie che segue la struttura di organizzazione “naturale” degli eventi con i

quali interagisce la rete. La figura 3.3 ne mostra l’architettura tipica.

3.4.2 Reti Self-organizing map

Agli inizi degli anni ottanta Tuevo Kohonen propose la più utilizzata delle reti

organizzate in funzione della topologia, conosciuta come mappa auto-

organizzativa (dall’inglese self-organizing map, SOM) che preserva la topologia o

mappa di caratteristiche auto-organizzative (SOFM). La SOM di Kohonen

combina un principio di apprendimento competitivo con una strutturazione

topologica dei neuroni, in modo che i neuroni adiacenti tendano a possedere

vettori di pesi simili. Nella rete SOM i neuroni tendono a possedere vettori di pesi

che prendono le caratteristiche dello spazio vettoriale di entrata. La relazione di

vicinanza si traduce nella prossimità fra i neuroni nello spazio Euclideo, pur

essendo i vettori di pesi iniziali arbitrari. La rete SOM di Kohonen è composta da

due strati (vedere figura 3.4), un primo strato vettoriale che costituisce lo strato di

entrata con dimensione pari a quella dei patterns d’ingresso, e un secondo strato a

forma di matrice o esagono il quale è lo strato di uscita dove evolve la

strutturazione topologica della rete. I neuroni dello strato di entrata si collegano

con quelli dello strato di uscita e la forza di tali connessioni viene data dai vettori

n-dimensionali wj = (wj1,…, wjn) che caratterizzano ogni neurone dello strato di

uscita. A questi pesi vengono assegnati inizialmente valori aleatori.

Nella rete SOM i valori dei pesi vengono modificati attraverso il processo di

apprendimento. In questo processo ogni vettore di pesi si muove nella direzione

del prototipo (o centro) di qualche sottoinsieme di patterns di entrata. L’uscita di

ciascun neurone dello strato di uscita rappresenta la vicinanza del neurone al

pattern di entrata.

Quando un pattern d’ingresso viene presentato nello strato d’entrata, l’algoritmo

SOM aggiorna il vettore di peso del neurone vincitore ed anche i vettori di pesi

dei neuroni che appartengono alla regione di vicinanza topologica definita per il


97

neurone vincitore. Quindi, l’unico criterio da seguire è la distanza topologica fra i

neuroni nello spazio Euclideo. Un’area Nj(t) contiene i neuroni che si trovano ad

una distanza topologica D(t) dal neurone j nel tempo t, dove D(t) diminuisce nel

tempo. D(t) non si riferisce alla distanza Euclidea fra i patterns di ingresso e i

vettori di pesi, bensì alla lunghezza del percorso che collega due neuroni dello

strato di uscita a seconda della topologia scelta per la rete.

Figura 3.4 – Architettura tipica di una rete SOM.

Quando una rete SOM viene utilizzata per classificazione di pattern, i pattern

d’ingresso sono assegnati a un gruppo di clusters sulla base della similitudine fra

loro e i vettori di riferimento dei clusters. Prima di iniziare il compito di

classificazione o riconoscimento di pattern, l’utente deve predefinire una

topologia di nodi (tipicamente un array rettangolare o esagonale bidimensionale,

dove ogni nodo nell’array rappresenta un cluster). All’inizio, vettori di riferimento

aleatori sono generati e assegnati a ciascun nodo. Dopodichè, un processo

iterativo esegue i seguenti passi:


98

1. Un pattern d’ingresso è scelto in modo aleatorio e il nodo più vicino a

questo è scelto in termini di una distanza;

2. Il vettore di riferimento del nodo scelto (nello spazio del pattern

d’ingresso) è allora aggiustato, in modo tale che questo diventi più simile

al pattern d’ingresso assegnato;

3. I vettori di riferimento degli altri nodi vicini al nodo scelto nell’ array

bidimensionale (a seconda un criterio di vicinanza) vengono aggiustati.

Capitolo 4. Analisi delle prestazioni

99

Capitolo 4

Analisi delle prestazioni

Il problema della definizione di un sistema di localizzazione è stato affrontato

finora solamente in linea teorica. I capitoli precedenti, infatti, hanno soltanto

definito il principio che permette di identificare la posizione in cui si trova un

utente mobile, ma hanno lasciato irrisolti alcuni aspetti del problema che, sebbene

non traspaiono da un punto di vista teorico, vanno invece opportunamente

affrontati se si vuole progettare un algoritmo capace di fornire risultati precisi ed

in tempi accettabili. Inoltre, è necessario operare la scelta della tecnologia wireless

con cui andare ad implementare il sistema, scelta questa, che dovrà essere

opportunamente guidata da criteri come il costo e il livello di diffusione sul

mercato.

Per tale motivo gli strumenti hardware e software impiegati nel nostro studio, i

risultati ottenuti negli esperimenti da noi condotti e le conseguenti osservazioni

costituiscono l’argomento di questo capitolo. Verrà dedicata particolare attenzione

al problema dell’interfacciamento con la scheda di rete, ai conseguenti quesiti

sollevati circa la natura dei dati restituiti ed alla presentazione delle scelte di

progetto che hanno determinato la struttura del software. Avremo anche modo di

descrivere l’ambiente in cui gli esperimenti hanno avuto luogo giustificando le

decisioni prese durante la fase di mappatura.

Inoltre, si cercherà di rispondere ai quesiti sollevati dall’adozione dei metodi di

Scene Analysis per la localizzazione; in particolare si cercherà di capire se

effettivamente si possa caratterizzare un certo stato con una certa tipologia di

impronta; se tale impronta ha una qualche relazione con la collocazione spaziale

dello stato che deve caratterizzare; quale è l’impatto della quantità di campioni,

delle scelte di mappatura e di altri fattori sull’efficacia del metodo. Verranno poi

illustrate le esperienze che ci hanno spinto ad abbandonare definitivamente il

Capitolo 4. Specifiche generali del sistema

100

metodo della triangolazione e più in generale l’analisi della propagazione delle

onde radio in interni.

L’obiettivo finale cui tutta questa discussione mira è la verifica ed il confronto

delle prestazioni ottenute tramite il principale metodo di impronta, ossia

l’approccio deterministico dell’algoritmo NNSS e quello basato sulle reti neurali.

Cercheremo inoltre di illustrare una possibile soluzione euristica che, sfruttando

opportunamente entrambe le tecniche, sia in grado di ovviare ai difetti di ciascuna

di esse.

4.1 Specifiche generali del sistema

L’obiettivo di tale progetto è stata la realizzazione di un sistema che permettesse

di stimare la posizione di un apparato radiomobile portatile, nello specifico uno

smartphone, all’interno di un ambiente chiuso del tipo ufficio, museo, fiera,

ospedale, ecc… basandosi sulla connessione radio dell’apparato stesso a un

numero ristretto di AP con tecnologia Wi-Fi presenti all’interno dell’ambiente.

L’infrastruttura impiegata è del tipo network-based; la rete esegue la

localizzazione a partire dai valori misurati di livello di segnale dai terminali

d’utente. A questo scopo è utilizzato un server remoto il quale gestisce le funzioni

di rete, quali l’esecuzione dell’algoritmo di posizionamento, il salvataggio dei

punti campionati, il salvataggio delle mappe, i collegamenti, ecc…

Tale soluzione solleva i terminali da operazioni computazionalmente onerose,

come l’esecuzione dell’algoritmo di localizzazione e l’accesso al database delle

misure offline. Le risorse hardware e software utilizzate, le quali influenzano

direttamente lo scenario e l’analisi delle soluzioni possibili al problema del

posizionamento indoor, sono le seguenti:

• I terminali mobili sono smartphone provvisti di scheda WLAN Wi-Fi

(IEEE 802.11b) compliant. Nel caso del progetto in esame si sono adottati

terminali Nokia modello E51 dotati di Symbian OS, sul quale è possibile

sviluppare applicazioni Symbian Series 60 e Mobile Information Device


101

Profile 2.0 (MIDP 2.0). Il sistema di localizzazione e l’algoritmo

sviluppato sono tuttavia in grado di funzionare con dispositivi e sistemi

operativi diversi, purché ovviamente Wi-Fi compliant;

• La rete Wi-Fi è costituita da diversi dispositivi AP compatibili con lo

standard IEEE 802.11b. Questi devono essere in grado di restituire i

rispettivi valori di potenza, il Service Set IDentifier (SSID) e l’indirizzo

MAC. Gli AP utilizzati sono Netgear modello WG-102;

• La piattaforma di sviluppo è Microsoft .NET Framework, in ambiente

Visual Studio 2005, sotto Windows XP Pro OS;

• Un server remoto di alte prestazioni per lavorare con le diverse

applicazioni in gioco (Processore Core Duo, memoria RAM superiore a 2

Gb, scheda di rete LAN, unità Disco Rigido, unità CD/DVD-ROM, porte

USB, altre porte e uscite standard), su piattaforma Windows Server 2003,

compatibile con la piattaforma .NET Framework.

La tecnica di posizionamento scelta richiede la misura dei livelli di potenza

ricevuti dagli AP costituenti l’infrastruttura della rete; a tal fine, è stata sviluppata

un'applicazione in grado di campionare i valori Received Signal Strength (RSS)

ricevuti dagli AP. Attraverso questa applicazione si è in grado di misurare, in

qualsiasi istante di tempo, il valore di potenza ricevuto da un determinato AP.

L’applicazione, detta “Campionatura”, è stata sviluppata su piattaforma Microsoft

.NET, eseguibile su palmari con Windows Mobile OS. L’applicazione di

Campionatura presenta le seguenti caratteristiche:

• Un’interfaccia grafica, Mappa, dove sono caricate le mappe, in formato

Scalable Vector Graphics (SVG), delle zone dove si desidera

implementare la localizzazione. Sulle mappe a disposizione vi è la

possibilità di selezionare i punti dove si vuole campionare. Per ogni punto

scelto, con una precisione di 10 pixel (valore di default), si può associare

un nome, dopodichè inizia la fase di campionatura. In caso d’errore, vi è la

possibilità di eliminare i punti oppure di raffinare la misura considerando


102

più campioni. Un esempio dell’interfaccia grafica Mappa è riportato in

figura 4.1. In tale figura i punti di colore verde rappresentano le impronte

digitali;

Figura 4.1 – Schermata Mappa dell’applicazione Campionatura.

• Un’etichetta Opzioni che contiene le variabili che possono essere

configurate, e cioè: un “Filtro AP” che controlla l’identificativo SSID

degli AP di cui si vuole misurare il livello di potenza; il “Numero di

campionature” che stabilisce il numero di campioni con il quale si

vogliono rappresentare le nostre impronte digitali e che può variare in

decade, da 10 fino 100 campioni; “Intervallo campionature” che stabilisce

l’intervallo di attesa tra un campione e quello successivo e può variare da 1

secondo fino 10 secondi; uno “Zoom mappa” per ingrandire o diminuire le

dimensioni delle mappe sullo schermo del palmare, che può variare di un

fattore di 1x (valore di default) fino a 5x; la “Grandezza del punto” che

stabilisce quanti pixel coprono i punti sullo schermo e che può essere da 1

fino a 10 oppure impostato per default in Auto (naturalmente minore sarà

questo valore e maggiore sarà la possibilità di effettuare campioni in punti


103

il più possibile vicini); la “tolleranza del clic” che stabilisce quanto sono

grandi in pixel i punti segnati sottoforma di palline e che va da 1 pixel fino

a 10 pixel; infine è specificata una legenda per differenziare un punto da

campionare, un punto campionato oppure un punto annullato. Un esempio

del menu Opzioni è riportato in figura 4.2.

Figura 4.2 – Schermata Opzioni dell’applicazione Campionatura.

• Una schermata Menu contenente le seguenti opzioni: indirizzo IP associato

al server remoto dove risiede il database delle misure popolato durante il

processo di campionatura (WS); indirizzo IP associato al server dove viene

implementato l’algoritmo di stima della posizione (POS) che in fase di test

si riferisce al computer di sviluppo (dove sarà possibile eseguire il codice

in step, l’analisi degli errori, correzioni, raffinamenti dell’algoritmo,

ecc…) mentre in fase finale farà riferimento al server remoto stesso;

opzione “Sincronizza mappe” con la quale è possibile visualizzare i file

SVG che si trovano sul palmare; opzione “Sincronizza punti campionati”,

grazie alla quale è possibile trasferire al server remoto il file temporale

Campionamenti contenente i campionamenti delle impronte digitali sulle


104

quali l’algoritmo è in grado di effettuare la stima della posizione; infine

l’opzione “Esci” che consente di chiudere l’applicazione. Un esempio di

schermata Menu è riportato in figura 4.3.

Figura 4.3 – Schermata Menu dell’applicazione Campionatura.

Dopo aver descritto l’applicazione Campionatura che permette di eseguire l’intera

fase offline, concentriamo ora la nostra attenzione sulle applicazioni

DimmiSymbian e DimmiMuseo le quali ci consentono di realizzare la fase online

attraverso l’utilizzo di dispositivi smartphone. La prima delle due applicazione è

stata realizzata attraverso il linguaggio di programmazione C++ , mentre l’altra

attraverso il linguaggio di programmazione Java profilo MIDP 2.0. Si è deciso di

realizzare due differenti applicazioni per superare l’impossibilità dei programmi

Java di accedere al livello fisico del Wi-Fi. Quindi, in pratica, è l’applicazione

DimmiSymbian che fa da ponte tra l’applicazione Java e lo strato fisico andando a

prelevare i differenti valori di potenza. La comunicazione tra i due processi

avviene tramite protocollo TCP\IP. Una volta che l’applicazione Java ha ricevuto i

differenti valori di potenza è in grado di aggiornare il server con l’informazione

sul proprio stato, quindi quest’ultimo risponde con la stima corrente della


105

posizione del dispositivo client. In tal modo, l’utilizzatore è in grado di

visualizzare la mappa con la nuova posizione stimata (vedi figura 4.4). Questo

comportamento viene ripetuto ad intervalli regolari che variano in funzione delle

variazioni dei livelli di potenza i quali, ad esempio, possono cambiare in funzione della

velocità dell’utente.

Figura 4.4 – Schermata Visualizza Mappa dell’applicazione DimmiMuseo.

Oltre a ricevere i valori di potenza rilevati dall’applicazione DimmiSymbian,

l’applicazione DimmiMuseo è in grado di riprodurre file multimediali che danno

una descrizione approfondita dei beni presenti nella sala che si sta visitando. Tutte

le funzioni che l’applicazione Dimmi Museo è in grado di svolgere vengono

selezionate attraverso un apposito menu. Quindi con riferimento alla figura 4.5

l’utente è in grado di inserire un nuovo codice che dà la possibilità di riprodurre

un nuovo file multimediale; tornare alla bacheca che dà la possibilità di visionare

quali sono i codici associati ai beni presenti nella sala; visualizzare la mappa che,

come abbiamo detto, dà la possibilità all’utente di visionare in qualsiasi momento

la propria posizione; infine, attraverso la voce “Esci” è possibile uscire

dall’applicazione. Quest’ultima funzione è stata pensata in modo tale che una

volta usciti dall’applicazione Java si è in grado di chiudere contemporaneamente


106

l’applicazione DimmiSymbian che, come abbiamo visto, senza il normale

funzionamento dell’applicazione DimmiMuseo non avrebbe alcun senso.

Figura 4.5 – Schermata Menu dell’applicazione DimmiMuseo.

Per quanto riguarda l’infrastruttura rete WLAN, essa può essere costituita da AP

Wi-Fi (compatibili con IEEE 802.11b) di diversi fabbricanti e caratteristiche

purché apportino le informazioni necessarie al processo di campionatura e di

localizzazione. Queste informazioni sono: SSID, l’indirizzo MAC associato alla

scheda Wi-Fi dell’AP ed il valore RSS, cioè il livello di potenza del segnale radio

dell’AP. In particolare si sono utilizzati, come detto in precedenza, Access Point

Netgear modello WG-102.

E’ altresì presente un server remoto, collegato via cavo ad un router Wi-Fi, che

funge da coordinatore della rete, permettendo così di scambiare (mediante la

tecnologia wireless) informazioni sui punti campionati, con il palmare in maniera

remota. Il router è un Sparklan modello WX-66156T.

La topologia della rete ove sono stati compiuti i test è di tipo a stella, dove il nodo

centrale è rappresentato dal router (collegato al server remoto da un link cablato


107

Ethernet), e gli estremi sono gli altri AP. Tale topologia è rappresentata

schematicamente in figura 4.6.

Figura 4.6 – Topologia della rete Wi-Fi utilizzata per la localizzazione.

Come si è detto le applicazioni DimmiMuseo e Campionatura sono in grado di

visualizzare e manipolare le mappe in formato SVG. Tale mappe sono state

costruite attraverso una piccola applicazione eseguibile su Microsoft Windows OS.

Tale applicazione inoltre è in grado di associare su ciascuna mappa diversi oggetti

utili al posizionamento indoor. Tra questi i più importanti sono sicuramente le

posizioni delle stazioni base che potrebbero essere utili per l'algoritmo di

posizionamento. Comunque l'applicazione, per il momento, è più rilevante per il

progetto aziendale e commerciale di posizionamento, quindi non viene dettagliato


108

il suo funzionamento. Nella figura 4.6 si mostra l'interfaccia grafica di questa

applicazione.

Figura 4.7 – Applicazione di gestione delle mappe.

In figura 4.8 si mostra, a titolo di esempio, la mappa della sede di Roma

dell'azienda Thera S.r.l. realizzata con la suddetta applicazione:

Figura 4.8 – Mappa della sede a Roma di Thera S.r.l.

Capitolo 4. Test sperimentali

109

4.2 Test sperimentali

In questa sezione saranno brevemente illustrati i risultati sperimentali degli

algoritmi esposti in precedenza. La sperimentazione è suddivisa in fase offline e

fase online. La fase offline si riferisce alle impostazioni iniziali comuni e

indipendenti dal metodo impiegato. Invece la fase online varia a seconda delle

caratteristiche implementative di ciascun metodo utilizzato. Gli esperimenti in

questa fase si riferiscono alla sede dell’azienda Thera S.r.l, locata a Roma in via

Cristoforo Colombo.

Nella fase offline viene effettuata la campionatura spaziale dell’area di

riferimento. L’area di copertura viene suddivisa in una serie di punti di

riferimento scelti in maniera arbitraria. Tali punti, che saranno caratterizzati

ciascuno da un opportuno fingerprint, possono essere dislocati uniformemente

sulle diverse zone in cui si divide l'ambiente indoor, oppure addensati in funzione

della quantità di informazione che deve essere localizzata. Per ciascun punto di

riferimento, i fingerprint vengono calcolati mediando la potenza ricevuta da

ciascun AP sul canale di beacon entro un determinato intervallo di tempo.

Nel caso in esame, il numero di punti di riferimento viene scelto in funzione della

dimensione degli ambienti. Quindi risulta ovvio che nelle aree più piccole si siano

considerati un numero di punti minore rispetto agli ambienti più vasti.

Nell’ambiente di riferimento è altresì presente un corridoio che pone particolari

difficoltà a causa della sua geometria che influisce sulle condizioni propagative.

I valori di potenza sono stati mediati su 100 campioni presi con un intervallo di

campionamento di 2 secondi utilizzando le accortezze precedentemente descritte.

Le misure così effettuate sono state memorizzate nel server remoto. Con

riferimento alla figura 4.9 dei punti base, ne sono stati scelti 10, uniformemente

distribuiti su tutta l’area, per essere utilizzati in fase di test.

La fase online, invece, riguarda l’esecuzione del posizionamento mediante

l’interazione tra il terminale e la rete. I terminali d’utente effettuano misurazioni

di potenza dai vari access point sul canale di beacon e inviano tali risultati al

Capitolo 4. Test sperimentali

110

server remoto. Quest’ultimo implementa l’algoritmo di localizzazione inviando in

risposta allo smartphone il risultato in termini di coordinate.

Figura 4.9 – Posizioni utilizzate nella fase di test.

La figura 4.10 mostra lo schema logico della procedura di posizionamento online.

Le prestazioni saranno misurate sulla base dei due seguenti parametri di

riferimento:

• Precisione: con la quale si intende la probabilità, mediata su un numero

consistente di prove ripetute, che il risultato della stima disti meno di

mezzo metro dal punto fisso più vicino alla posizione effettiva del

terminale;

• Accuratezza: con la quale si intende la deviazione standard dell’errore di

stima rispetto all’effettiva posizione del terminale, i.e.

Capitolo 4. Risultati sperimentali: algoritmo NNSS

111

( )

n

ZZn

iti

acc

∑=

−= 0

2

σ

dove Zi rappresenta le coordinate associate alla stima ottenuta in un ogni istante di

tempo, mentre Zt rappresenta le coordinate associate alla vera posizione del

terminale. Il numero di misurazioni è rappresentato da n.

Figura 4.10 – Schema funzionale della localizzazione Wi-Fi.

4.2.1 Risultati sperimentali: algoritmo NNSS

I risultati qui presentati riguardano l’algoritmo NNSS descritto in precedenza. La

metrica adottata è la distanza Euclidea. I dati misurati dal terminale d’utente

vengono inviati al server remoto che li confronta con i valori memorizzati nel

database delle misure. Il punto con fingerprint a minore distanza Euclidea dal

fingerprint esperito è scelto come risultato di localizzazione ed inviato in riposta

all’utente. I risultati ottenuti sono riassunti nella figura 4.11, che mostra il

comportamento dell'algoritmo nei punti scelti come insieme di test. Le

osservazioni sono le seguenti:

Capitolo 4. Risultati sperimentali: algoritmo NNSS

112

• Nelle zone non coperte direttamente dagli AP oppure dove sia presente

sovrapposizione delle coperture radio di tanti AP, la stima ha dato risultati

poco soddisfacenti tanto in termini di precisione quanto in termini di

accuratezza. Tale decadimento prestazionale dipende dalla difficoltà di

caratterizzare bene il fingerprint nei punti non direttamente coperti da un

AP. D’altro canto, laddove vi sia una sovrapposizione netta tra due segnali

di due AP diversi (i.e. al centro di una sala illuminata lateralmente da due

AP) la precisione è limitata dal fatto che a causa dei diversi fenomeni di

attenuazione il segnale dell’AP più lontano può essere ricevuto più forte.

Un motivo di tale sbilanciamento nelle misure può essere dovuto, ad

esempio, alla posizione dell’utente rispetto alla direzione di arrivo del

segnale dell’AP. Per ovviare a tali inconvenienti si può ricorrere

all’utilizzo di antenne di tipo direzionale, evitando così le sovrapposizioni

dovute al comportamento isotropico della radiazione delle antenne.

Comunque, a causa dei costi elevati, questo genere di antenne non viene

utilizzato nell’ambito di questo progetto;

• Un altro fattore che influenza le prestazioni di questo algoritmo sono le

attenuazioni del canale radio, in presenza di più utenti in una determinata

zona; infatti, l’attenuazione aggiuntiva dovuta alla presenza di altri utenti

modifica i valori di potenza misurati rispetto al caso della campionatura in

fase offline, laddove l’ambiente era totalmente vuoto. Utenti che si

spostano arbitrariamente nell’ambiente generano più fenomeni di

riflessione;

• Un ultimo problema prestazionale di tale algoritmo riguarda i falsi allarmi.

Difatti, dal momento che l’algoritmo sceglie il fingerprint a distanza

minima non sfrutta l’informazione contenente nei fingerprint a distanza

maggiore, ma comunque confrontabile con la minima. In tal modo

l’algoritmo risulta particolarmente sensibile a disturbi o a sovrapposizioni

di segnale e può portare a risultati notevolmente errati in termini di

distanza dalla locazione effettiva dell’utente. Per ovviare a tale problema si

possono considerare più misure (non solo quella a distanza minima) o

Capitolo 4. Risultati sperimentali: metodo probabilistico

113

eliminare alcune possibilità qualora sia nota, a causa di informazioni

esterne o da rilevamenti precedenti, una prima grossolana informazione di

localizzazione.

0

10

20

30

40

50

60

70

80

90

100

1 2 3 4 5 6 7 8 9 10

P osiz ione d e i P unt i

Pre

cis

ion

e (

%)

0

1

2

3

4

5

6

7

8

9

10

Acc

ura

tezz

a (m

etri

)

Precisione (%)

Accuratezza (m et ri)

Figura 4.11 – Prestazioni algoritmo NNSS.

In media le prestazioni di tale algoritmo sono riassumibili in un'accuratezza media

di 2,7 metri ed una precisione per il 75% dei casi, considerando tutti i fattori

precedentemente elencati. Come si nota, la significatività di tali dati in termini

medi è particolarmente influenzato dal dato relativo ai punti 3 e 4. In generale tale

metodo presenta un’elevata precisione ma un’accuratezza limitata.

4.2.2 Risultati sperimentali: metodo probabilistico

In questo caso l'algoritmo ricava una stima della locazione d’utente

massimizzando la probabilità di trovarsi in un dato punto dell’ambiente di

riferimento, noto il fingerprint misurato. Tale probabilità può calcolarsi sia

utilizzando un istogramma dei valori campionanti sia ipotizzando una

distribuzione Gaussiana dei valori misurati, come in § 3.2.2.

Capitolo 4. Risultati sperimentali: metodo probabilistico

114

E’ possibile anche in questa metodologia avere problemi simili al caso del NNSS:

si potrebbero infatti verificare casi di falsi allarmi o grandi errori di localizzazione

dovuti alla rumorosità dei dati, in quanto anche in questo caso l’algoritmo non

tiene conto dell’informazione contenuta nei punti caratterizzati da una probabilità

vicina alla massima. Nuovamente, al fine di ovviare a tali problemi, si può

effettuare una discriminazione sulle possibili locazioni sulla base di informazioni

esterne.

Il grafico in figura 4.12 mostra le prestazioni dell’algoritmo quando le probabilità

condizionate siano stimate a partire dall’istogramma dei dati misurati.

0

10

20

30

40

50

60

70

80

90

100

1 2 3 4 5 6 7 8 9 10


Pre

cis

ion

e (

%)

0

1

2

3

4

5

6

7

8

9

10

Acc

ura

tezz

a (m

etri

)

Precisione (%)


Figura 4.12 – Prestazioni metodo probabilistico (istogramma).

Si nota come il comportamento dell'algoritmo basato sul metodo probabilistico,

utilizzando l’approccio dell’istogramma per il calcolo delle probabilità singole,

presenti basse prestazioni rispetto all'algoritmo NNSS, con un'accuratezza media

di 3,6 metri ed una precisione media del 48%. La stima è molto imprecisa in

particolare per le zone che non sono coperte direttamente da un AP, ove

l’algoritmo ritorna valori che oltrepassano la zona di appartenenza, quindi non è

consigliato il suo utilizzo per rilevamento puntuale.

Capitolo 4. Risultati sperimentali: metodo del centroide

115

La figura 4.13 invece riporta le prestazioni dell’approccio probabilistico, ove per

il calcolo delle probabilità è utilizzata la funzione di distribuzione Gaussiana.

0

10

20

30

40

50

60

70

80

90

100

1 2 3 4 5 6 7 8 9 10


Pre

cis

ion

e (

%)

0

1

2

3

4

5

6

7

8

9

10

Acc

ura

tezz

a (m

etri

)

Precisione (%)


Figura 4.13 – Prestazioni metodo probabilistico (fdp Gaussiana).

In linee generali, utilizzando la distribuzione Gaussiana, si guadagna un po' di

stabilità nella stima, cosa che rende preferibile questo approccio rispetto al

precedente. L’accuratezza media è di circa 3 metri e la precisione media del 65%.

Rispetto all'algoritmo NNSS le prestazioni sono leggermente inferiori; tale

approccio è infatti meno robusto alle variazioni del segnale e allo spostamento del

terminale.

4.2.3 Risultati sperimentali: metodo del centroide

Il metodo del centroide stima in maniera probabilistica la posizione del terminale

e a differenza dei metodi precedenti dà una risposta a partire da più punti fissi.

Quindi la sua esecuzione permette di sfruttare l’informazione relativa a più punti

rendendo oltretutto l’algoritmo adatto a risolvere problemi di spostamento del

Capitolo 4. Risultati sperimentali: metodo del centroide

116

terminale, nel caso in cui serva un tracciamento a partire del segnale Wi-Fi

ricevuto dal terminale stesso.

0

10

20

30

40

50

60

70

80

90

100

1 2 3 4 5 6 7 8 9 10


Pre

cis

ion

e (

%)

0

1

2

3

4

5

6

7

8

9

10

Acc

ura

tezz

a (m

etri

)

Precisione (%)


Figura 4.14 – Prestazioni metodo del centroide.

In linee generali, dalla figura 4.14 si osserva come questo algoritmo, sebbene non

molto preciso (con 50% di precisione), offra per la maggioranza dei casi

un'accuratezza media di 2,3 metri, migliore che nel caso NNSS (di 2,7 metri

rispettivamente). Le prestazioni, rispetto ai casi precedenti, migliorano in termini

di accuratezza, ma peggiorano in termini di precisione. Tale calo prestazionale

sulla precisione è facilmente spiegabile considerando che l’algoritmo, a differenza

di NNSS e dell’approccio probabilistico, non risponde seccamente con uno dei

punti fissi. Da questo punto di vista, una metrica prestazionale strettamente legata

ai punti fissi quale la precisione così come definita in questo caso, è poco adatta a

rappresentare le prestazioni di tale algoritmo. Difatti una stima della posizione,

calcolando il centroide a partire da tutti i punti fissi, potrebbe essere influenzata in

maniera eccessiva da valori di posizioni lontane che, a causa di problemi

propagativi, si sono esperiti in valori di potenza elevati o comunque anomali.

Capitolo 3. Osservazioni sui metodi di filtraggio

117

Nuovamente, le prestazioni di tale algoritmo possono essere limitate dalla

variabilità del segnale ricevuto a causa tanto di fattori propagativi quanto di

eventuali attenuazioni supplementari dovute alla presenza di utenti nell’area

coperta. Per limitare l’influenza di tali problemi si può aumentare il numero di

campioni rilevati da ciascun AP in fase di misurazione in modo da avere un valore

medio meno dipendente dall’aleatorietà del processo. Ovviamente tale

accorgimento aumenta i tempi di attesa prima della risposta del server. La figura

4.15 riporta le prestazioni dell’algoritmo del centroide dove gli utenti mediano la

potenza su tre misurazioni, invece di una.

0

10

20

30

40

50

60

70

80

90

100

1 2 3 4 5 6 7 8 9 10


Pre

cis

ion

e (

%)

0

1

2

3

4

5

6

7

8

9

10

Acc

ura

tezz

a (m

etri

)

Precisione (%)


Figura 4.15 – Prestazioni metodo del centroide (modificato).

Le prestazioni in generale sono aumentate: 2,1 metri di accuratezza e 61% di precisione.

4.2.4 Osservazioni sui metodi di filtraggio

Tra gli algoritmi di filtraggio esposti nel precedente capitolo, quello più adatto e

più semplice per essere implementato a livello software, è quello del particle

filter. Tuttavia, andando ad osservare la formula associata ai pesi, la quale viene

espressa in termini di una funzione di distribuzione di probabilità del tipo

Capitolo 4. Osservazioni sui metodi di filtraggio

118

Gaussiana, si osserva che essa dipende fortemente dalle conoscenze delle

coordinate del terminale in tempo reale. In tal modo, si ha la necessità di stabilire

un metodo iniziale che permetta di ottenere queste coordinate. Quindi può essere

utilizzato il metodo NNSS ovvero l’approccio probabilistico, dei quali si

conoscono le prestazioni, ottenute nei test precedenti.

Un altro approccio per determinare la posizione delle particelle si basa sul

modello di propagazione radio che stabilisce le perdite di percorso in ambiente

indoor. Comunque, come si è visto, il modello di propagazione non è molto

affidabile, anzi potrebbe anche compromettere le prestazioni del particle filter.

Quindi, le prestazioni del particle filter dipendono dall’approssimazione della

posizione stimata rispetto a quella reale, ragione per la quale si consiglia di

utilizzarlo solo nei casi in cui si conosce effettivamente la posizione esatta (o

almeno con un alto grado di precisione) del terminale. Tale risultato può essere

raggiunto, ad esempio, impiegando sensori prossimità. Comunque, nel nostro caso

l’infrastruttura (Wi-Fi) a disposizione per la localizzazione non consente l’utilizzo

di questi modelli.

Per i motivi precedentemente indicati i metodi di filtraggio non sono stati

implementati a livello software e quindi è impossibile verificare le loro

prestazioni in questo contesto.

Capitolo 5. Architettura del sistema

119

Capitolo 5

Architettura del sistema

Nel precedente capitolo si è visto come algoritmi del tipo NNSS o probabilistico

siano affetti dal problema di riportare una stima della localizzazione basandosi sul

valore massimo dato da una determinata metrica sui fingerprint misurati in

ciascun punto. Tale limitazione porta gli algoritmi di questo tipo a scartare

informazioni relative ai punti limitrofi. D’altro canto il metodo del centroide

permette di aumentare l’accuratezza della stima ma soffre del problema legato ai

punti lontani che possono eccessivamente influenzare la stima.

Appare fin da ora evidente come la soluzione migliore possa essere data da

un’opportuna fusione di tali tecniche, utilizzando la prima (NNSS) precisa ma

poco accurata, al fine di limitare una sotto zona ove poi raffinare la stima

mediante il metodo del centroide, in grado di fornire risultati più accurati.

Una fusione di tali approcci permetterebbe infatti di sfruttare tanto i buoni risultati

in termini di precisione dell’algoritmo NNSS (si ricordi che a parte casi

particolari, la precisione era molto elevata) quanto la maggiore accuratezza del

metodo del centroide.

Inoltre, si è esaminato in linee generali il funzionamento delle reti neurali e come

le sue caratteristiche aggiuntive (evoluzione e apprendimento) potrebbero essere

utili per gestire un problema di localizzazione Wi-Fi. Più precisamente la stima

del posizionamento di un terminale non è un problema statico, è piuttosto un

problema dinamico in quanto non si conoscono a priori i diversi percorsi che si

potrebbero seguire e quindi il suo comportamento risulta essere imprevedibile.

Si deve infine ricordare che il segnale radio varia nel tempo. Tale variazione è

dovuta alle caratteristiche del canale e dell'ambiente di propagazione, e questa

situazione pone dei limiti nelle prestazioni dei metodi di localizzazione. Esistono

diversi approcci di rete neurale per affrontare il problema di localizzazione di

utenti mobili in un ambiente provvisto di una rete Wi-Fi: il clustering e il vector

Capitolo 5. Architettura del sistema

120

quantization sono alcuni esempi. Si riscontrano comunque grosse limitazioni nello

sviluppo di una rete neurale evolutiva e con apprendimento in quanto:

• Il modello di propagazione, che descrive le perdite di percorso del segnale

in ambiente indoor, non è del tutto affidabile data la sua natura empirica,

quindi è difficile, conoscendo a priori certi valori di potenza e di distanza

di riferimento, stimare la posizione esatta di un terminale. Infatti, il fattore

più influente è la riflessione del segnale dovuto alla presenza di muri e

mobili. Tale fattore provoca fluttuazioni nei livelli di potenza ricevuti, i

quali sono fondamentali per determinare la posizione del terminale. Per

questo è difficile trovare neuroni con vettore di peso (valori di RSSI)

simili;

• Nel caso in cui l'algoritmo di stima della posizione non abbia buone

prestazioni, non è possibile aggiornare e sostituire i neuroni, perché non si

può affermare a priori che i valori restituiti rappresentino la vera posizione

del terminale;

• Il database, com’è stato progettato, non permette variazioni in fase online

dei neuroni.

Soluzioni a questi problemi potrebbero assicurare un aggiornamento affidabile

della rete neurale. Infatti, una soluzione raggiungibile sarebbe quella di dotare

l'infrastruttura di sensori, che permettano di rilevare grossi cambiamenti nei valori

RSSI in una posizione ben determinata, ma comunque, questo aumenterebbe la

complessità e i costi del sistema. Ovviamente, se non si è in grado di aggiornare i

neuroni, non si può raggiungere un apprendimento effettivo perché i neuroni

saranno sempre gli stessi.

A tal proposito, si decide di utilizzare l'approccio neurale soltanto per poter gestire

la rete, e se in futuro si trovassero soluzioni appropriate ai problemi esposti, in

modo tale da poter aggiungere caratteristiche di evoluzione e apprendimento, non

bisognerà fare grossi cambiamenti data la struttura a strati e modulare della rete

neurale.

Capitolo 5. Misurazione di grandezze elettromagnetiche

121

Di seguito si introdurranno brevemente gli approcci scientifici necessari a

realizzare le misurazioni dei valori di potenza atti ad essere utilizzati tanto nella

fase di popolamento del database dei fingerprint, quanto nei test veri e propri delle

tecniche di localizzazione; saranno analizzati i dati di alcune misure e sarà

descritto l’algoritmo disegnato nell’ambito di tale progetto sulla scorta

dell’osservazione di tali misure.

5.1 Misurazione di grandezze elettromagnetiche

Per la localizzazione indoor, in maniera analoga a quanto si rileva negli ambienti

aperti, esistono problematiche di natura elettromagnetica (em) che devono essere

analizzate e verificate.

In questo paragrafo non si intende fare un trattato di campi e.m., tuttavia si ritiene

utile ricordare, anche se in forma semplificata, le equazioni fondamentali della

propagazione dell’onda e.m. e le relazioni con la frequenza e la distanza. Le

“equazioni” nel vuoto espresse in forma differenziale, essendo nulle correnti di

conduzione e carica elettrica, sono perfettamente simmetriche. Campo magnetico

e campo elettrico sono entrambi costituiti da linee chiuse e la loro dipendenza dal

tempo fa sì che le onde elettromagnetiche si generino e siano sostenute da

“campi” variabili nel tempo.

Allo scopo di introdurre altre osservazioni sui “campi”, facciamo una ulteriore

semplificazione considerando le funzioni del tempo come “sinusoidali pure” con

pulsazione ω, da cui si ricava che: dE/dt = ω E e dB/dt = ω B anche se i vettori E e

B sono sfasati di 90° nel tempo, per cui rotE = - ω B ed rotB = - ω E ma risulta

anche: Vi = - ω B dove Vi rappresenta la forza elettromotrice indotta (legge di


122

Lenz-Faraday-Neumann) che vuol dire che a parità di induzione magnetica B,

aumentando la frequenza, la forza elettromotrice indotta si riduce

proporzionalmente, così per il duale campo elettrico, da cui il campo

elettromagnetico che si propaga si attenua proporzionalmente alla frequenza.

Affrontiamo ora il più “semplice” problema della distanza. Un'onda, generata in

un ipotetico punto dello spazio libero, tende a propagarsi nello stesso modo

dell’onda che si ottiene tirando una pietra in uno stagno. In analogia ai cerchi che

si vedono concentrici al punto dove è caduta la pietra, l'onda elettromagnetica

tende a formare sfere (la simmetria deve essere tri-dimensionale) il cui raggio è

sempre più grande. La distanza tra due massimi successivi è proprio uguale alla

lunghezza d’onda dell’onda elettromagnetica in esame. La velocità di

propagazione dei cerchi nello stagno è legata alla densità dell'acqua. In presenza

di molto fango la velocità tende a ridursi. Un fenomeno analogo si riscontra per le

onde elettromagnetiche, dove la velocità massima di propagazione, velocità della

luce, è associata al vuoto (nell’aria non si discosta molto) ed è pari a circa 300.000

Km/secondo. Nello spazio libero, il campo elettrico si attenua in modo lineare con

la distanza dalla sorgente. La superficie aumenta con il quadrato della distanza

(raggio della sfera), l'energia è proporzionale al quadrato del campo elettrico e

quindi distanza e riduzione del campo sono in proporzione lineare; due massimi

consecutivi si trovano a distanza di una lunghezza d’onda. Per un raddoppio della

distanza si ottiene la riduzione ad un quarto della potenza, o viceversa: con 6 dB

di potenza in meno si riduce la distanza alla metà. Nelle comunicazioni reali la

riduzione del campo è superiore a ciò che ci si attende per la sola distanza. Due

sono i problemi principali: lo spazio non è vuoto e tra le antenne trasmittente e

ricevente possono esistere ostacoli di varia natura, nel caso in esame possono

essere costituiti da pareti, persone, ecc…

Come è noto si possono fare delle similarità tra le onde radio e le onde luminose.

Possiamo quindi più facilmente analizzare il comportamento delle onde

elettromagnetiche comparandole con i fenomeni luminosi, con l'accortezza di non

trascurare che il rapporto tra la lunghezza d'onda e la dimensione dell'oggetto è un

parametro fondamentale. La penetrazione di un'onda elettromagnetica in una


123

parete di determinata conducibilità è maggiore alle frequenze più basse: più cresce

la frequenza e meglio è riflessa un'onda. Oppure, per riflettere frequenze più basse

serve una parete di spessore superiore o conducibilità superiore. La riflessione,

come per la luce, può avvenire anche nell’attraversamento di materiali a costante

dielettrica differente. Il metallo anche con spessori sottili è un buon riflettore; nel

caso di pareti si devono tenere presenti eventuali reti metalliche inserite

nell’intonaco per ridurre le interferenze esterne. Il comportamento delle onde

elettromagnetiche che incontrano una parete di buon conduttore è analogo a

quanto si verifica in una linea di trasmissione chiusa in cortocircuito: tutta

l’energia è riflessa. Per quanto attiene gli effetti legati alla presenza di persone si

parla di interazione quando l’organismo umano interferisce con un campo

elettromagnetico con il risultato di una perturbazione del suo equilibrio

precedente. Un esempio del tutto schematico di come il campo e.m. interagisce

con la struttura corporea umana è riportato in figura 5.1.

Figura 5.1 – Interazione del campo e.m. con la struttura corporea umana.

L’interazione non implica necessariamente un effetto biologico di una certa

rilevanza né, tanto meno, un effetto sanitario. Comunque si ha una penetrazione il

cui livello è funzione della frequenza dell’onda elettromagnetica e, di

conseguenza una attenuazione della potenza dell’onda trasmessa che ha


124

attraversato il corpo. Un andamento qualitativo del livello di penetrazione di

un’onda em in funzione della frequenza di lavoro è riportato in figura 5.2.

Figura 5.2 – Livello di penetrazione em in funzione della frequenza.

Le strutture che interessano la propagazione delle onde e.m. alle lunghezze d’onda

associate al Wi-Fi sono sicuramente dotate di aperture, con conseguenti ulteriori

fenomeni: rifrazione e diffrazione. La rifrazione si verifica, di nuovo,

similarmente con la luce, con ostacoli che abbiano dimensioni comparabili con la

lunghezza d'onda della radio frequenza considerata. In tali condizioni, si ha il

cambiamento della direzione dell'onda. Uno dei fenomeni associati è quello legato

alla possibilità di ricevere, in particolari condizioni, segnali a radio frequenza pur

non essendo in vista della sorgente. Dobbiamo pertanto iniziare a fare una analisi

dell’ambiente operativo in cui si instaura il servizio di “telemetria” di cui ci

stiamo interessando. Il concetto di “foro o apertura” è legato al rapporto tra la

lunghezza d’onda λ e la dimensione minore d dell’apertura che attraversa. Per

rapporti λ\d maggiore di 10 assumiamo che la superficie si comporti come

“continua”, per rapporti λ\d minore di 10 assumiamo che la superficie si comporti

come “apertura”.


125

Figura 5.3 – Effetti legati ad aperture e fori.

Nella figura 5.3 si presentano i fenomeni legati alle aperture presenti o che

possono generarsi per la presenza di molte persone con conseguente

“rigenerazione” della sorgente in forma attenuata. Il campo e.m., per effetto di

questi molteplici effetti, assume un aspetto estremamente variabile nello spazio

tipo quanto rappresentato in figura 5.4.

Figura 5.4 – Andamento qualitativo di un campo e.m. in ambiente indoor.

Capitolo 5. Test di riferimento

126

5.2 Test di riferimento

Il progetto dell'azienda Thera S.r.l prevede l’utilizzo di dispositivi standard per la

localizzazione Wi-Fi in ambiente indoor e si basa sulla acquisizione di molteplici

valori di misura della potenza ricevuta dal dispositivo impiegato. Le prove sono

state effettuate in un ambiente tipo (figura 4.9) in cui sono state rilevate le misure

nei punti indicati in verde sulla figura.

Il metodo di localizzazione adottato si affida al valore di potenza indicato dal

dispositivo mobile associato “all’osservatore”. Il primo passo è quindi la misura

del campo e.m. in alcuni punti. La posizione dello strumento di lettura è stato

posizionato ad un’altezza di 1,5m in quanto essa risulta essere la più probabile per

una persona di altezza media che tenga in mano un dispositivo mobile. La

migliore posizione è quella che permette una giusta distanza dalla parete e

consente ad una persona di stare da entrambi i lati, ovvero di fronte o di spalle alla

sorgente. Senza ricorrere a strumenti misuratori di campo elettrico e\o magnetico,

come si è visto nella § 4.1, è stata realizzata un’applicazione Campionatura che è

stata da riferimento per le nostre necessità. Dopo la serie di misure (almeno 100

letture della potenza associata al segnale) si attribuisce alla popolazione di dati

una statistica gaussiana : si estrae la media e la varianza.

A valle delle misurazioni dei pattern di potenza si passa all’analisi dei valori

esperiti. Sulla scorta delle considerazioni sulle rilevanze sperimentali si passa alla

fase vera e propria di disegno dell’algoritmo. Preliminarmente i dati vanno

spiegati sulla scorta di un modello statistico che ne descriva in maniera quanto più

accurata possibile il processo di generazione. Tale operazione di modellizzazione

statistica (oltre ad essere il cuore di un eventuale approccio algoritmico alla

soluzione ricercata) permette inoltre di poter eliminare alcuni dati misurati, i

cosiddetti ouliers, non spiegati dal modello e quindi interpretabili come casi

statisticamente irrilevanti (ad esempio in quanto figli di errori di misura o

procedimento) e quindi da trascurare nelle operazioni successive.

Generalmente i valori di potenza misurati in contesti quali quelli in esame sono

ben spiegati da una distribuzione di tipo Gaussiano di media e varianza date. Tale

Capitolo 5. Soluzione proposta

127

descrizione ai fini del disegno dell’algoritmo è di fondamentale importanza. Tanto

per cominciare permette di caratterizzare i dati rilevati sulla base di pochi

parametri (vale infatti la pena ricordare che una distribuzione Gaussiana è

completamente descritta dai soli parametri di media e varianza). L’aver

modellizzato una statistica differente, d’altro canto, può guidare verso

l’individuazione di diversi parametri caratterizzanti. Ad esempio, a differenza del

caso Gaussiano, per una qualsiasi distribuzione bi-modale il valor medio è di

scarso significato (si pensi ad esempio ad una variabile discreta che può assumere

con medesima probabilità il valore 1 o il valore -1; in tal caso il valor medio è 0, e

pur tuttavia è un valore non direttamente assumibile dalla variabile). Per di più la

descrizione statistica viene direttamente calata all’interno della descrizione

dell’algoritmo (si veda ad esempio nel caso del metodo del centroide) all’interno

di funzionali di guadagno da massimizzare.

5.3 Soluzione proposta

Nel caso del progetto in esame, avente come obiettivo lo studio e

l’implementazione prototipale di un sistema con fini di commercializzazione

futura, i tempi e i costi associati ad un approccio scientificamente rigoroso, non

sono stati ritenuti commisurati agli obiettivi preposti dall’azienda.

Lo scopo della ricerca è stato in effetti quello, partendo da zero, di poter inferire

circa la possibile commerciabilità su vasta scala del sistema. Da questo punto di

vista (a monte della spesa da sobbarcarsi da parte dell’azienda per la calibrazione

accurata del sistema) una prima, seppur non eccessivamente accurata, valutazione

delle prestazioni ottenibili si è ritenuta prioritaria. Conseguentemente si è preferito

allentare alcuni vincoli in termini di rigore scientifico dell’approccio in quei

contesti in cui la perdita di accuratezza fosse, se non trascurabile, almeno poco

influente, a tutto vantaggio di poter avere, con tempi e costi opportuni, una stima

circa le prestazioni raggiungibili del sistema, e conseguentemente poter

commisurare da parte dell’azienda un investimento rilevante ai fini della

commercializzazione. In particolar modo, le misurazioni sono state fatte


128

direttamente con dispositivi commerciali anziché con strumenti di misurazione

scientifica e in condizioni variegate per quel che riguarda l’ambiente circostante.

E’ tuttavia doveroso sottolineare che sebbene questi setting di misurazione

risultino non in linea con un metodo rigorosamente scientifico, tuttavia

permettono di portare risultati più accordati a contesti realistici di lavoro del

sistema, cosa che date le finalità aziendali del progetto stesso è sembrata

opportuna.

In accordo con quanto descritto i valori di potenza sono stati calcolati mediando

su ciascun punto la potenza ricevuta da ciascun AP. Nel dettaglio le misure sono

state prese considerando un unico orientamento mediando 100 campioni per

effettuare la media. La misurazione è stata effettuata con un dispositivo simile a

quello utilizzato poi successivamente per la localizzazione.

Il terminale era tenuto in mano da uno sperimentatore ad un altezza di circa 1,5m.

Il valore dei campioni su cui è stata effettuata la media è stato scelto come trade

off tra accuratezza nella stima della media (crescente col numero di campioni) e

l’influenza di variazioni non controllate nelle misurazioni (anche esse crescenti

col numero di campioni), dovute al fatto che il terminale poteva non trovarsi

sempre alla stessa altezza; alle lunghezze d’onda in gioco, anche pochi cm

possono portare a consistenti variazioni del campo esperito.

A commento di tali osservazioni si consideri il grafico in figura 5.5 riportante la

potenza esperita al variare della distanza. Tale grafico riporta un andamento

misurato del tipo di quello qualitativo presentato in figura 5.4. Il brusco

decadimento della potenza ricevuta a 2 metri dalla sorgente nel caso di 100

campioni non può essere solo spiegato dall’attenuazione da multipath, soprattutto

in relazione ai valori a distanze maggiori. Tale crollo è dovuto infatti al fatto che

la misura in quel momento è stata affetta da uno spostamento in elevazione del

terminale che alle lunghezze d’onda in gioco ha portato l’antenna ricevente in una

zona ove il campo era caratterizzato da valori molto bassi. Nel computo della

media tali valori dovuti a imprecisioni di misura hanno avuto un effetto maggiore

rispetto al caso mediato su meno campioni, che riesce a rappresentare in maniera

più realistica i fenomeni spazio varianti dell’attenuazione da multipath.


129

-90

-80

-70

-60

-50

-40

-30

-20

-10

0

1 2 3 4 5 6 7 8 9

D ist a nz a ( m e t r i)

Po

ten

za

Ric

ev

uta

(d

Bm

)

10 cam pioni

100 cam pioni

Figura 5.5 – Potenza ricevuta dal WM al variare della distanza.

Di seguito si mostreranno alcune valori di segnale misurati in ambienti di test.

L’osservazione di tali valori giustificherà alcune scelte di progetto per quel che

riguarda l’algoritmo finale. Le seguenti misure si riferiscono agli uffici della

Thera S.r.l. locati in Via Cristoforo Colombo a Roma. La tabella mostra i valori

medi di potenza esperiti nei punti fissi nella mappa (figura 4.9) da ciascuno degli

AP per gli ambienti indicati come “SALA 4” e “SALA 1”. Tali dati risultano

consistenti con la dislocazione spaziale degli AP rispetto ai punti fissi e in

relazione alla presenza di pareti e porte. Notiamo ad esempio come per i punti 1 e

2 della “SALA 4” i valori dominanti siano quelli dell’AP1 dislocato nel medesimo

ambiente. Il punto 1, localizzato più in prossimità dell’AP, presenta un valore di

potenza maggiore. I valori relativi ad AP remoti invece non differiscono tra il

punto 1 e il punto 2 (si veda ad esempio il caso dell’AP4). Risulta evidente come i

pattern relativi a ciascun punto siano fortemente caratterizzati dal valore ricevuto

dall’AP4 e dall’AP5. In questo caso infatti, il contributo di attenuazione dovuto

alla presenza di ostacoli (quali ad esempio i muri) è dominante rispetto a quello


130

dovuto alla distanza, cosicché la potenza ricevuta è confrontabile, nonostante i

punti siano a distanza diversa dalla sorgente.

Per il secondo ambiente considerato (“SALA 1”) si possono trarre le medesime

conclusioni. Nuovamente, infatti, il segnale più forte è quello proveniente dall’AP

più vicino. A completamento di tali misure si riportano nei grafici seguenti (figura

5.6) gli andamenti di potenza esperiti per i punti relativi alle “SALA 4” da ciascun

AP5. La forte variabilità dei valori, dovuta all’aver rilassato i vincoli di rigore

sulle misurazioni, può ben apprezzarsi. Tuttavia, come già rimarcato, tale

variabilità ben si accorda con contesti reali; inoltre i valori medi sono ben

distinguibili e del tutto plausibili con la configurazione dell’ambiente. L’analisi

dei risultati sperimentali mostrerà infine come le approssimazioni fatte non

abbiano inficiato le prestazioni del sistema, confrontabili ove non superiori a

quelle di applicazioni analoghe e del tutto accettabili in termini di prerequisiti di

progetto. Il decadimento della potenza esperita fa sì che al di fuori della sala ove

fisicamente è localizzato l’AP il livello di segnale risulti particolarmente

attenuato.

Capitolo 5. Realizzazione della rete neurale

131

Figura 5.6 – Andamenti di potenza per i punti relativi alle SALA 4 dall’AP5.

Sulla scorta di tale osservazione possiamo concludere che ciascun fingerprint sarà

caratterizzato fortemente dal valore relativo all’AP locato nella medesima sala ove

si trova il punto cui il fingerprint si riferisce, riducendo l’impatto delle altre

misure, che appariranno fortemente rumorose. Da questo punto di vista, la scelta

del fingerprint più vicino ai valori esperiti può vedersi come un problema di

classificazione di dati rumorosi. Per limitare l’impatto di tale effetto di disturbo

inerente alle misure si è pensato di calare gli algoritmi precedentemente esaminati

nell’ambito di una rete neurale in modo tale da poter ovviare ai problemi delle

misure sfruttando le capacità generalizzatrici di tali strutture algoritmiche.

5.3.1 Realizzazione della rete neurale

In una rete neurale possono essere distinti tre diversi tipi di neuroni che si

differenziano sulla base della tipologia di strato a cui essi appartengono: strato di

ingresso, strato nascosto (intermedio) e strato d’uscita. Ogni neurone si differenzia

dagli altri per caratteristiche che dipendono dallo strato di appartenenza e che lo

rendono unico.

La rete viene addestrata nella fase offline che corrisponde alla campionatura. In

tale fase (detta di apprendimento) le misure vengono immesse nella rete

specificando l’uscita desiderata in relazione a ciascun ingresso e la rete definisce

le sue regioni di classificazione. Nella fase online, che corrisponde alla stima della

posizione, le informazioni acquisite nella fase di addestramento, sono utilizzate

Capitolo 5. Definizione delle funzioni di strato

132

per elaborare i dati in ingresso. Caratteristiche specifiche di questa rete neurale

sono le seguenti:

• I neuroni sono rappresentati dai vettori contenenti i valori di potenza

rilevati nella fase offline per quel che riguarda lo strato nascosto; dalle

coordinate cartesiane, nel caso dello strato di uscita; dai valori correnti di

RSSI ricevuti dal terminale, nel caso dello strato d’ingresso. I valori in

ingresso prendono il nome di pattern d’ingresso o, più semplicemente,

pattern;

• I pesi associati a ciascun neurone. In particolare i neuroni dello strato

d’ingresso non hanno pesi; i neuroni dello strato nascosto avranno un peso

dipendente dai valori di RSSI ottenuti durante la fase offline; i neuroni di

uscita avranno un peso che dipende dallo strato nascosto;

• Il sistema che gestisce il comportamento dei neuroni in base allo strato in

cui si trovano. Tale sistema si aspetta di ricevere pattern che abbiano

lunghezza pari al numero di AP e valori numerici che rappresentano le

potenze. E’ necessario, inoltre, controllare la coerenza dei valori contenuti

nel pattern, altrimenti l’informazione non potrà essere processata dagli

strati successivi, e quindi la stima della posizione non avrà alcun senso.

La rete viene arricchita da un identificativo che dà la possibilità di avere più reti

neurali che fanno localizzazione all’interno di uno stesso sistema. Ad esempio, ad

ogni piano di un palazzo, costituito da un insieme di neuroni, viene associato un

diverso codice identificativo.

5.3.2 Definizione delle funzioni di strato

Le funzioni di strato per questa rete neurale, come precedentemente accennato,

fondono i metodi di localizzazione analizzati precedentemente quali il metodo

NNSS e il metodo del centroide in modo da sfruttare i vantaggi di entrambe le

tecniche, andando a migliorare i risultati dell’una, con le caratteristiche dell’atra e

viceversa.


133

Ciò che avviene, per grandi linee, è che l’algoritmo NNSS viene utilizzato per

identificare, a partire da un set di fingerprint che presentano le distanze minori dal

fingerprint misurato, una macrozona ove è localizzato il punto. Si tratta a tutti gli

effetti di una stima della posizione più grossolana a livello di macrozone (che ad

esempio potrebbero coincidere con le stanze dell’ambiente di lavoro). A partire da

tali valori, prescelti mediante l’algoritmo NNSS, viene calcolata la posizione con

l’algoritmo del centroide, che permette di avere migliore accuratezza, e può

avvantaggiarsi del fatto che misure no significative (relative cioè ad ambienti

lontani) siano state eliminate mediante la prima fase di stima grossolana. Nel

dettaglio di implementazione della rete neurale, il metodo NNSS verrà utilizzato

per determinare i neuroni nascosti più vicini al pattern d’ingresso, che

chiameremo per semplicità neuroni vincitori. Inoltre, il luogo nel quale si vuole

effettuare la localizzazione, viene preventivamente suddiviso in zone (stanze) e ad

ogni neurone vincitore viene associato un peso in funzione dell’ubicazione

geografica del pattern in quell’istante di tempo.

Il metodo del centroide, invece, viene utilizzato per determinare la posizione che

meglio rappresenta il pattern d’ingresso in funzione dei neuroni vincitori e dei

pesi ottenuti nello strato nascosto. Allora, rispetto alle grandezze della rete neurale

(vedi § 3.4):

• Il vettore X = {X1, X2,…, XN} rappresenta il vettore degli ingressi, cioè il

pattern, mentre N rappresenta il numero di AP visibili per quel pattern;

• A rappresenta la funzione di attivazione dello strato;

• F(A) rappresenta la funzione di propagazione dello strato.

Il primo strato avrà come funzione di attivazione e propagazione la funzione

identità, perciò entrambe le funzioni dovranno dare in uscita il valore d’ingresso

cioè il pattern. Quanto detto si può esprimere in termini matematici:

( ) ingressoingressoingresso

ingresso

AAF

XA

=

=


134

Ogni neurone del primo strato ha ora dei valori di uscita da consegnare allo strato

nascosto che avrà una funzione di attivazione con il compito di misurare la

distanza fra il pattern d’ingresso e il vettore dei pesi dei neuroni nascosti. Questa

distanza è calcolata mediante la differenza euclidea utilizzata nel metodo NNSS.

Successivamente, questa distanza verrà utilizzata nella funzione di propagazione

che ne calcolerà l’inverso più 1, così il neurone più vicino al pattern d’ingresso

sarà quello con funzione di attivazione minima, ossia:

( ) ( ) ( ) ( )

( ) ( ) 1,

1

...,

coscos

2211cos

+=

−++−+−==

SXdAF

XSXSXSSXdA

tonastonas

NNtonas

dove S = {S1, S2 ,…, SN} è il vettore dei pesi dei neuroni nascosti e N la

lunghezza del vettore, che in questo caso dipenderà del numero di AP visibili dal

neurone nascosto. In questo modo è possibile ordinare i neuroni in base al valore

restituito dalla funzione di propagazione e considerare solo i neuroni con

differenza minima. In altre parole, viene introdotta una soglia (threshold) che

permette all’amministratore di rete di decidere quanti neuroni potranno definire la

zona a cui appartiene il pattern d’ingresso. Questa operazione di sogliatura

permette, in buona sostanza, di scegliere il numero di punti sul quale effettuare la

stima con il metodo del centroide. Il valore della soglia va opportunamente

dimensionato in funzione della caratterizzazione propagative dell’ambiente di

lavoro. Allora, in base al sottoinsieme di neuroni (ordinati in una lista crescente

secondo la differenza ottenuta e determinata dalla funzione di propagazione),

considerando le loro zone di appartenenza in funzione del pattern, è possibile,

mediante una semplice regola statistica, determinare quale sarà la zona che ha più

probabilità di contenere il pattern d’ingresso. La regola statistica è così definita:

tresholdlistainapparechevoltaprimalaclusterposizione

listanellaclusterilapparechevoltedinumeroPesocluster ∗

=


135

Tale regola stabilisce il peso di una zona o cluster in base a due fattori: il primo è

il numero di volte che il cluster si trova nella lista, il secondo è la posizione

assunta nella lista dal cluster. In tal modo, più volte compare il cluster nella lista,

più probabilità ci sono che il pattern appartenga ad esso, inoltre, minore è la

differenza ottenuta e più probabilità ci sono che il pattern appartenga a quel

cluster. Questa procedura del tutto euristica è necessaria a determinare i cluster

più vicini al pattern d’ingresso. Tale informazione sarà successivamente trasferita

allo strato di uscita, rappresentato da una lista contenente i cluster coinvolti e i

rispettivi pesi.

Nello strato di uscita, infine, la funzione di attivazione classificherà i neuroni in

funzione dei pesi ottenuti nello strato nascosto. In tal modo, la funzione di

propagazione sarà realizzata attraverso una somma ponderata determinata

attraverso il metodo del centroide, quindi verrà propagata la stima della posizione

del pattern d’ingresso, espressa in termini di coordinate (x,y). Per collegare ogni

neurone ricevuto dallo strato nascosto con il rispettivo cluster di appartenenza, a

questa somma si aggiunge il peso del cluster. Allora, si avrà:

( )

( )( )

ClusterN

tClusterNeuroni

N

tClusterNeuroni

uscitauscita

clusterNuscita

PesoiP

XiPAF

PesoClusterNeuroniLISTA

∑

∑

=

−

==

=

1/

1/

)(

,/

La regola per stabilire i pesi associati a ciascun cluster nello strato nascosto è

pensata in modo tale da garantire parità di condizioni nella gara tra neuroni che

appartengono allo stesso cluster. Le probabilità p(i), invece, vengono determinate

considerando che i valori RSSI dei neuroni nascosti e quelli del pattern d’ingresso

che presentano comportamento probabilistico simile a una funzione di

distribuzione Gaussiana, mentre, l’insieme X contiene la lista con le coordinate

associate ai neuroni proveniente dallo strato nascosto. Una volta determinato il

centroide, la risposta della rete neurale sarà quella delle coordinate stimate per il

terminale in quell’istante.

Capitolo 5. Diagramma di funzionamento della rete neurale

136

5.3.3 Diagramma di funzionamento della rete neurale

E’ possibile ora, con quanto è stato descritto precedentemente, schematizzare, in

maniera sintetica, il funzionamento della rete neurale che verrà eseguita mediante

un’applicazione sviluppata in ambiente Visual Studio in linguaggio C#. Nella

figura 5.7 si illustra come sono implementate le funzioni di attivazione e di

propagazione (A e F rispettivamente) della rete neurale.

Figura 5.7 – Diagramma di flusso della rete neurale.

La nomenclatura utilizzata è la seguente:

• X rappresenta il pattern d’ingresso alla rete, costituito da valori di potenza

(RSS) rilevati per ogni AP visibile in quel momento dal terminale, ognuno

identificato con il rispettivo indirizzo MAC. In linguaggio C# esso è

rappresentato da due array, uno di tipo int (intero) per i valori RSS e un

altro di tipo string (stringa) per gli indirizzi MAC;


137

• S rappresenta la lista contenente i neuroni nascosti che presentano una

struttura simile al pattern d’ingresso. In linguaggio C# questi vengono

raggruppati mediante liste speciali definite per le caratteristiche

dell’informazione che devono contenere, ovvero: nome del punto “name”

di tipo string, livello di potenza RSSI “power” di tipo array d’interi e

indirizzi MAC di tipo array di stringhe. Tutte queste informazioni sono

ottenute in fase di campionatura e memorizzate in un file di tipo XML;

• C è la lista contenente i neuroni di uscita contraddistinti dalla coppia di

coordinate (x,y) contenute nel file XML, precedentemente descritto. In

linguaggio C# essa viene tradotta in una lista contenente l’informazione

“name” e le coordinate del punto in un array di interi int[2] .

L’implementazione software della rete neurale si basa sul diagramma di figura

5.7, cioè si creano metodi che eseguono le funzioni in ogni strato (InputLayer(),

HiddenLayer() e OutputLayer()) e che vengono invocati da un metodo principale

(NetworkManagment()), incaricato di ricevere il pattern d’ingresso e controllare la

gestione dei neuroni all’interno della rete. Infine, la figura 5.8 mostra l’interazione

tra i neuroni della rete neurale da implementare.

Figura 5.8 – Rete neurale.

Capitolo 5. Risultati sperimentali dell’algoritmo proposto

138

Di seguito saranno esposti i risultati sperimentali relativi all’implementazione

della soluzione proposta nelle medesime condizioni sperimentali dei test

precedenti.

5.3.4 Risultati sperimentali dell’algoritmo proposto

In questa sezione si riportano i risultati relativi al prototipo di sistema di

localizzazione indoor su tecnologia Wi-Fi oggetto del presente progetto di ricerca.

La soluzione proposta implementa l’algoritmo presentato nelle precedenti

sottosezioni. Gli apparati hardware utilizzati sono i seguenti:

• Un server remoto su piattaforma Windows Server 2003 OS, che gestisce il

database con le informazioni riguardanti la fase di campionatura e stima

della posizione tramite l’algoritmo basato sulla rete neurale;

• Un portatile per lo sviluppo software dell’algoritmo che gestisce la rete

neurale, su piattaforma Windows XP Professional SP2 OS, compatibile

con l’ambiente di sviluppo utilizzato Microsoft Visual Studio 2005. Questo

calcolatore, collegato mediante link Ethernet al server remoto, ha la

finalità di valutare e modificare la rete neurale;

• Un router Wi-Fi SparkLAN WX-6615GT, collegato al server remoto, per

stabilire il collegamento wireless tra il terminale d’utente e il server stesso;

• Gli AP impiegati per la rete di localizzazione, di tipo NETGEAR WG-102.

Per quanto riguarda l’ubicazione degli AL all’interno dell’area di test si

può fare riferimento alla figura 4.7;

• I dispositivi terminali utilizzati sono smartphone di tipo Nokia E51

operanti su piattaforma Symbian OS.

Il database delle misure offline è il medesimo utilizzato per testare gli algoritmi di

letteratura. Nella fase online il calcolo della localizzazione viene effettuato non

appena attivata l’applicazione DimmiMuseo. Dopo l’attivazione, lo smartphone

effettua le misure e le invia al server remoto; quest’ultimo esegue l’algoritmo e

invia come risposta allo smartphone le coordinate della posizione stimata. Le


139

prestazioni riscontrate nei medesimi punti considerati per i test precedenti sono

riassunte in figura 5.9. Come era lecito attendersi, l’algoritmo riesce a fondere i

vantaggi di entrambi gli approcci implementati nei diversi strati della rete neurale. In

particolar modo le prestazioni migliorano notevolmente in termini di accuratezza media

(intorno a 1,78 metri) che può effettivamente interpretarsi come errore quadratico medio

della localizzazione.

0

10

20

30

40

50

60

70

80

90

100

1 2 3 4 5 6 7 8 9 10


Pre

cis

ion

e (

%)

0

1

2

3

4

5

6

7

8

9

10

Ac

cu

rate

zz

a (

me

tri)

Precisione (%)


Figura 5.9 – Prestazioni della soluzione proposta.

La precisione cala leggermente rispetto all’algoritmo NNSS puro, ma si

riscontrano valori maggiori nei punti dove l’algoritmo NNSS era messo in crisi (si

vedano a titolo di esempio i punti 3 e 4). Le motivazioni di tale perdita sono da

ascriversi in particolar modo all’esecuzione dell’algoritmo del centroide nello

strato di uscita che (come detto in precedenza) non risponde necessariamente con

un punto fisso precampionato. Da questo punto di vista la probabilità di trovarsi a

una distanza maggiore di 0,5 metri dal punto di riferimento più vicino può

abbassarsi (portando al calo di prestazioni in termini di precisione) anche se la

localizzazione avviene tuttavia in maniera corretta. Va dunque tenuto in conto che


140

non necessariamente tale abbassamento di precisione si traduce direttamente in un

errore di localizzazione. Da questo punto di vista le buone prestazioni in termini

di accuratezza possono giustificare tale assunto. Le prestazioni medie sono

riassumibili in una precisione pari al 70% ca e in un’accuratezza di 1.78 metri.

Tali valori, se messi in relazione all’applicazione commerciale per cui il prototipo

si propone, almeno nella sua fase iniziale di commercializzazione, localizzazione

all’interno di ambienti museali al fine di disseminazione di informazioni relative

alle opere esposte, sono del tutto soddisfacenti, soprattutto in termini di

accuratezza. A completamento delle sperimentazioni, sono di seguito esposte le

variazioni prestazionali a fronte di variazioni di parametri di sistema. Più nel

dettaglio il grafico in figura 5.10 mostra l’influenza del numero di campioni su cui

è mediata la potenza ricevuta dagli AP in fase di campionatura. Come

presumibile, al calare del numero di campioni, le prestazioni in termini di

accuratezza media tendono a diminuire essendo le misure meno accurate e più

sensibili a rumore e disturbi.

0

0 ,5

1

1 ,5

2

2 ,5

3

3 ,5

4

4 ,5

10 30 50 60 70 100

Nu m e r o d i cam p io n i

Acc

ura

tezz

a (

me

tri)

Accuratezza

Figura 5.10 – Effetti sulla stima al variare del numero di campioni.


141

Come si nota al crescere del numero di campioni, l’accuratezza tende a

stabilizzarsi intorno ad un valore limite. Ciò implica che oltre tale valore, le

prestazioni dell’algoritmo non sono più limitate da un’errata stima del valore

medio della potenza, quanto da altri fattori esterni, quali condizioni di

propagazione istantanee, fenomeni di assorbimento, ecc… Tale osservazione

giustifica la scelta fatta in fase di progetto di mediare su 100 campioni le misure

in fase di campionatura. Altro fattore che ha influenza nelle prestazioni è il

numero degli AP da cui misurare la potenza ricevuta al fine di costruire i

fingerprint. E’ verosimile ipotizzare che le prestazioni miglioreranno fino ad un

certo numero limite, oltre il quale le misurazioni aggiuntive non saranno costituite

che da rumore e quindi tali da non apportare informazione aggiuntiva ai fini di

localizzazione. Il grafico in figura 5.11 mostra l’andamento dell’accuratezza

media esperita caratterizzando i fingerprint con un numero crescente di AP.

0

1

2

3

4

5

6

7

8

9

1 2 3 4 5

Nu m e ro d i AP

Acc

ura

tezz

a (

me

tri)

Accuratezza

Figura 5.11 – Effetti sulla stima al variare del numero di AP.

I risultati confermano le osservazioni precedentemente riportate. Nel dettaglio si è

determinato empiricamente che i valori di potenza inferiori a -80 dBm non sono

utili ai fini degli algoritmi in gioco. Tale osservazione porta con sé due specifiche


142

di progetto: da un lato , infatti, è necessario fare in modo che in ciascun ambiente

dell’area di servizio possano giungere ad un livello di potenza maggiore di -

80dBm almeno i segnali di beacon di almeno 4\5 AP. A tal proposito occorre

inoltre prestare particolare attenzione alle caratteristiche propagative dei segnali

(tenendo presente quindi anche la dislocazione fisica degli AP stessi. Ad esempio,

aumentando l’altezza a cui sono installati gli AP, si può ridurre il numero di

riflessioni); dall’altro canto tale informazione determina indirettamente il numero

di AP da considerare per costruire i fingerprint. Come mostrato dalla figura 5.11,

nel caso in esame il numero di AP ottimo è pari a 5. La latenza del sistema

descritto in questo progetto è di circa 2 secondi, tempo che tiene conto del

collegamento del terminale al server remoto in modo wireless, le operazioni via

software della rete neurale, e la restituzione delle coordinate sulla mappa.

Considerando le applicazioni per cui il prototipo è stato ideato, tale ritardo di

risposta è del tutto accettabile. A conclusione si riportano in figura 5.12 le

prestazioni di sistemi commerciali o prototipali di localizzazione, basati sulla

misura del livello di segnale (RSS).

Figura 5.12 – Prestazioni di sistemi di localizzazione indoor.

Di tali sistemi l’unico attualmente commercializzato è Ekahau (vedi § 2.3.2). Tale

sistema assicura prestazioni medie migliori in termini di precisione e leggermente

peggiori in termini di accuratezza. Va però sottolineato che tale sistema richiede

l’utilizzo di appositi Wi-Fi tag da installare nell’infrastruttura di rete preesistente,

laddove la soluzione qui proposta non richiede l’installazione di alcun hardware

aggiuntivo ai fini della gestione delle misure relative alla localizzazione,

Capitolo 5. Caso di studio

143

presentandosi così come una soluzione più flessibile e dai ridotti costi di

installazione.

5.3.5 Caso di studio

Nel mese di Aprile 2008, sono state fatte una serie di prove dell’intero sistema di

localizzazione Wi-Fi nel Museo Civico di Albano Laziale (figura 5.13), con lo

scopo di verificare le prestazioni del sistema in un ambiente diverso da quello di

un ufficio.

Figura 5.13 – Facciata principale del Museo Civico di Albano Laziale.

L’accuratezza raggiunta per l’implementazione, mostrata nel paragrafo

precedente, non è adeguata per conoscere la posizione esatta dei beni esposti nelle

diverse sale del museo, per tale motivo si è deciso di applicare una localizzazione

geografica, anziché una localizzazione puntuale com’è stato fatto finora. In questo

contesto per localizzazione geografica si intende la determinazione univoca delle

sale del museo.


144

Per quanto riguarda la fase di campionatura, le 22 sale del museo sono state

discriminate con 2 fingerprinting distanti almeno 2 metri l’uno dall’altro. Tuttavia

in questo contesto, nella fase di campionatura, a differenza dei precedenti casi, si

deve fare attenzione ad associare ogni punto al corrispondente piano, mediante un

identificativo che permetta di discriminare tra le diverse mappe (una per ciascun

piano). In tal modo la rete neurale sarà in grado di stimare la posizione del

terminale nel piano corrispondente. Questo identificativo si ottiene direttamente

durante la campionatura, poiché il campionamento si effettua in funzione del

piano e quindi della corrispondente mappa. Ciò significa che nella fase offline la

posizione non è più rappresentata in un semplice sistema bidimensionale, in

quanto esiste una terza informazione che corrisponde al piano in cui si trova il

terminale. Tale informazione è accessibile dal file in formato XML elaborato dal

server.

Per definire con maggiore precisione la localizzazione geografica, si è utilizzata

l’applicazione Map che oltre a disegnare le mappe è in grado anche di permettere

la loro gestione. Infatti, con tale applicazione, è possibile delimitare le zone, in

modo tale che il server nel tentativo di stimare via software la giusta posizione del

terminale sia in grado di stabilire in quale sala si trovi l’utente.

Per quanto riguarda la collocazione degli AP si è scelta la seguente distribuzione

per coprire i tre piani (seminterrato, terra e primo) su cui è strutturato il museo:

• 5 AP nel piano seminterrato, configurati in topologia a stella per eseguire

la funzione di repeater. In tale configurazione uno degli AP svolge la

funzione di coordinatore centrale in quanto è in grado di collegarsi in

modalità punto-multipunto al resto degli AP. Il resto degli AP si collega in

modo punto-punto al coordinatore centrale. In tal modo si crea una

configurazione degli AP in grado di coprire tutto il piano. Per far ciò è

necessario configurare i diversi AP con il proprio software di gestione

(vedi Appendice 2). Inoltre, la connessione in modalità repeater tra gli AP

periferici e quello centrale è una funzionalità molto utile in ambiente di

grosse dimensioni, come succede in questo caso, per permettere sempre al


145

terminale di collegarsi via wireless con l’AP che abbia il segnale più forte

in quel momento, diminuendo così la latenza complessiva del sistema.

Questo è un fattore importante poiché l’utente si aspetta una risposta

immediata dell’applicazione;

• 5 AP nel primo piano, anche questi configurati in topologia stella, come

spiegato prima;

• Nessun AP nel piano terra, in quanto vi sono solamente 3 sale da coprire e

in base alle misurazioni effettuate su queste sale il segnale degli AP

collocati nel piano seminterrato e nel primo piano raggiungeva le sale

collocate in questo piano.

Tutti gli AP sono stati indirizzati in modo manuale onde evitare conflitti. In tal

modo tutti i dispositivi che formano la rete sono collegati tra di loro ed accessibili

da qualsiasi punto.

Per eseguire il posizionamento il server è sempre in attesa dell’informazione

contenente i valori RSS rilevati dal terminale, grazie ai quali è in grado di

eseguire la stima della posizione. Una volta ottenuta la posizione, il server cerca la

sala associata a quel punto e invia questa informazione al terminale mobile.

L’utilizzo di un approccio geografico anziché puntuale permette di ottenere

risultati migliori in quanto la precisione nella stima ottenuta cresce notevolmente.

Inoltre, si fa notare che anche utilizzando un numero minore di campioni di quello

utilizzato durante i test effettuati e descritti nei precedenti capitoli, i risultati

ottenuti mostrano maggiore stabilità. Tali obbiettivi sono stati possibili anche

grazie alle caratteristiche fisiche dell’ambiente, in quanto le zone sono più regolari

rispetto a quelle viste nella fase di test.

Conclusioni

146

Conclusioni

L’obiettivo principale di questa tesi è stato quello di progettare e testare un

sistema di localizzazione Wi-Fi in ambiente indoor basato su tecnologia WLAN.

L’idea alla base del sistema sviluppato è stata quella di riuscire a dotare

infrastrutture di rete wireless in area locale preesistenti di funzionalità di

localizzazione senza la necessità di istallazione di hardware aggiuntivo. Tale

prerequisito renderebbe la soluzione economica e quindi particolarmente attrattiva

per chi volesse fornire servizi location aware in ambienti già coperti da reti

WLAN quali musei, ospedali, fiere, ecc…

Il contributo di questo lavoro si è articolato nelle seguenti fasi:

1. ricerca in letteratura di algoritmi di stato dell’arte circa il problema da

affrontare; scelta di un set di soluzioni realizzabili date le specifiche

richieste di sistema;

2. test di tali soluzioni;

3. sviluppo di un algoritmo innovativo tale da fornire migliori prestazioni

rispetto alle soluzioni di stato dell’arte.

La prima fase ha avuto come risultato l’individuazione di tre classi di tecniche di

localizzazione, ciascuna basata sulla misura di diverse grandezze fisiche (misure

di distanza, misure di angolo d’arrivo, misure di pattern di potenza). La scelta di

investigare la classe di algoritmi basati sulla misura di pattern di potenza ricevuta,

è giustificata dal fatto che le altre tecniche o mal si adattavano al problema

affrontato (misure di distanza) o richiedevano l’installazione di hardware

aggiuntivo (misure di angolo di arrivo) che non rispondevano ad una precisa

specifica di sistema.

La seconda fase ha visto lo studio e la realizzazione di test sperimentali di una

serie di algoritmi di localizzazione nell’ambito della classe di riferimento scelta

nella prima fase (algoritmo NNSS, metodo probabilistico, ecc…).

L’interpretazione dei risultati di tali algoritmi in relazione alle specifiche in

Conclusioni

147

termini di prestazioni richieste dal sistema in esame, insieme con un’attenta

analisi dei pattern di potenza in gioco negli ambienti di riferimento, ha portato allo

sviluppo di un algoritmo basato sull’implementazione di una rete neurale. Le

prestazioni di tale algoritmo sono state valutate su base prototipale ed hanno

portato a risultati incoraggianti e confrontabili con quelli di altri sistemi di

localizzazione indoor su tecnologia WLAN.

Sviluppo nel breve futuro di questo studio sarà la realizzazione di un prodotto

denominato Dimmi Museo, commercializzato dall’azienda Thera S.r.l. ; Dimmi

Museo si propone come una guida museale interattiva in grado di disseminare

informazioni circa le opere esposte automaticamente, nota la posizione dell’utente

in relazione alla dislocazione delle opere stesse. Le prestazioni finali del sistema

di localizzazione sono rappresentate in termini di accuratezza e precisione, con

valori rispettivi di 1,7 metri e 70%. Questi valori possono essere confrontati con

altri sistemi proprietari.

Appendice Specifiche tecniche dello smartphone Nokia E51

148

Appendice

1. Specifiche tecniche dello smartphone Nokia E51

Appendice Datasheet del router Sparklan modello WX-6615GT

149

2. Datasheet del router Sparklan modello WX-6615GT

Appendice Datasheet degli AP NETGEAR modello WG102

150

3. Datasheet degli AP NETGEAR modello WG102

Bibliografia

151

Bibliografia

[1] F. Izquierdo, M. Ciurana, F.Barcelo, J.Paradells and E. Zola, “Performance evaluation of a TOA-based trilateration method to locate terminals in WLAN”, Proc 1st Symposium on Wireless Pervasive Computing, Jan 2006.

[2] X. Li, K. Pahlavan, M. Latva-aho and M. Ylianttila, “Indoor Geolocation using OFD; signals in HIPERLAN/2 wireless LANs”, Proc, PIMRC 2000 11th Symp. on Personal, Indoor and Mobile Communications, London, UK, vol. 2, Sept 18-21 2000, pp. 1449-1453.

[3] J. Hightower and G. Borriello, “Location Systems for Ubiqiotous Computing”, IEEE Computer, vol. 34, no. 8, pp. 57-66, Aug. 2001.

[4] J. Hightower and G. Borriello, “Location Sensing Techniques”, Tech. Rep. UW-CSE-01-07-01, University of Washington, Computer Science and Engg. Departement, 2001.

[5] J. Caffery Jr., G. Stuber, “Overview of Radiolocation in CDMA Cellular System”, IEEE Comm. Mag. April 1998.

[6] K. Pahlavan, P. Krishnamurty and J. Beneat, “Wideband Radio Propagation modeling for indoor geolocation applications”, IEEE Comm. Mag., pp.60-65, April 1998.

[7] G. Sun, J. Chen, W. Guo, “Singal Processing Techniques in Network Aided Positioning”, IEEE Signal Processing Magazine, July 2005, pp. 12-23.

[8] S. Saha, K. Chaudhuri, D. Shanghi and P. Bhagwat, “Location Determination of a Mobile Device Using IEEE 802.11b Access Point Signals”, Proc. IEEE Wireless Communication and Networking Conf., Volume 3, 16-20 March 2003 Page(s):1987 – 1992.

[9] S. Ganu, A. S. Krishnakumar and P. Krishnan, “Infrastructure-based Location Estimation in WLAN Networks”, Proc. IEEE Wireless Communication and Networking Conf. , 2004, pp. 465-470.

[10] T. Kitasuka, T. Nakanishi and A Fukuda, “Design of WiPS: WLAN-Based Indoor Positioning System”, Korea Multimedia Society, Vol.7, No.4, pp.15-29, Dec. 2003.

[11] P. Prasithsangaree, P. Krishnamurthy and P. K: Chrysanthis, “On Indoor Location With Wireless Lans”, Proc. IEEE Personal, Indoor and Mobile Radio Communications, Volume 2, 15-18 Sept. 2002 pp 720 – 724.

Bibliografia

152

[12] M. A. Youssef, A. Agrawala and A. U. Shankar, “WLAN Location Determination via Clustering and Probability Distributions”, Proc. IEEE Pervasive Computing and Communication, 23-26 March 2003 pp:143 – 150.

[13] Asim Smailagic Jason Small and Daniel P. Siewiorek, “Determining user location for context aware computing through the use of a wireless lan infrastructure”, Institute for Complex Engineered Systems, Carnegie Mellon University.

[14] Paramvir Bahl and Venkata N. Padmanabhan, “RADAR: An in-building RFbased user location and tracking system”, Proc. IEEE Joint Conference of the Computer and Communications Societies., Tel Aviv, 2000.

[15] P. Krishnamurthy, P. Prasithsangaree and P. K. Chrysanthis, “On indoor position location with wireless lans”, Proc. IEEE International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC’02), Lisbon, 2002

[16] Küpper Axel. Location-based Services: Fundamentals and Operation. Wiley,

2005.

[17] Rappaport Theodore S. Wireless Communications: Principles and Practice.

Prentice Hall Communications Engineering and Emerging Technologies Series,

2002.

[18] Dispense del corso Comunicazioni Mobili 2 del prof. Roberto Cusani,

Dipartimento INFOCOM, Facoltà di Ingegneria, Università degli Studi di Roma

“La Sapienza”.

[19] IEEE Standards Association: IEEE 802.11: LAN/MAN Wireless LANS Standards.

IEEE, 1999-2007

[20] Lyu M., Kin F. and Tilen M.: Location-Based Multimedia Mobile Service. Final

Year Project Report. Department of Computer Science and Engineering CUHK,

2005.

[21] Patmanathan, Vinod. Area Localization using WLAN. Master of Science Thesis,

Stockholm, Sweden, 2006.

[22] Youssef, M. and Agrawala, A.: The Horus WLAN Location Determination

System. Department of Computer Science University of Maryland, 2005.

Bibliografia

153

[23] Zawar S. and Malaney R. A.: Particles Filters and Positioning Tracking in Wi-Fi

Networks. IEEE, 2006.

[24] Wang H., Lenz H., Szabo A., Bamberger J. And Hanebeck U.: WLAN-Based

Pedestrian Tracking Using Particle Filters and Low-Cost MEMS Sensors.

Workshop on Positioning, Navigation and Communication (WPCN), 2007.

[25] Widyawan, Klepal M. and Pesch Dirk: RF-BASED Location system In Harsh

Environment. IFAWC, Tel-Aviv, Israel, 2007.

[26] Bahl, P. and Padmanabhan, V.: RADAR: An In-Building RF-Based User Location

and Tracking System. Microsoft Research, 2000.

[27] Bahl P, Padmanabhan V. and Balachandran A.: A software System for Locating

Mobile Users: Design, Evaluation, and Lessons. Microsoft Research, 2002.

[28] Cheng, Y., Chawathe, Y., LaMarca A. and Krumm, J.: Accuracy

Characterization for Metropolitan-scale Wi-Fi Localization. IEEE, 2005.

[29] Haykin Simon. Kalman Filtering and Neural Networks. John Wiley & Son, INC.

2001.

[30] Richard Harrison. Symbian OS C++ for Mobile Phones, Volume 3, 2007.

[32] www.ekahau.com

[33] www.aeroscout.com

[34] www.cisco.com

[35] www.nokia.com

[36] www.sparklan.com

[37] www.netgear.it

[38] it.sun.com

[39] S60 3rd Edition SDK for Symbian OS, Supporting Feature Pack 1, for C++

Ringraziamenti

154

Ringraziamenti

“A conclusione di questo lavoro di tesi, è doveroso porre i miei più sentiti

ringraziamenti alle persone che ho avuto modo di conoscere in questo importante

periodo della mia vita e che mi hanno aiutato a crescere sia dal punto di vista

intellettuale sia dal punto di vista umano. E’ difficile in poche righe ricordare

tutte le persone che, a vario titolo, hanno contribuito a rendere migliore questo

periodo.

Un ringraziamento sentito va al Prof. Roberto Cusani che mi ha dato

l’opportunità di partecipare a questo importante progetto.

Un ringraziamento particolare va al mio correlatore Ing. Stefano Rinauro che mi

ha consigliato e aiutato durante tutto lo svolgimento della tesi.

Uno speciale ringraziamento va a tutta la società Thera S.r.l. e in particolare a

Massimiliano Giurelli e all’Ing. Giuseppe Grisafi per l'aiuto che mi hanno fornito

quotidianamente durante tutto il periodo di tesi.

Ai miei compagni di studio, in particolar Raffaele e Paolo, con cui ho condiviso i

momenti tristi e felici di questo lungo cammino.

Non so se trovo le parole giuste per ringraziare i miei genitori e la mia famiglia,

però vorrei che questo mio traguardo raggiunto, per quanto possibile, fosse un

premio anche per loro e per i sacrifici che hanno fatto.

Per ultimo ma non per ordine di importanza, vorrei ringraziare Francesca la

persona che mi è stata vicina in ogni momento di difficoltà e che in qualche modo

ha reso possibile il compimento di tale lavoro standomi sempre accanto.”

Daniele

Progetto e realizzazione di una procedura per la ...infocom.uniroma1.it/~robby/Tesi/Sperduti...

Documents

Transcript of Progetto e realizzazione di una procedura per la ...infocom.uniroma1.it/~robby/Tesi/Sperduti...