UNIVERSITÀ DEGLI STUDI DI PARMA
FACOLTÀ DI INGEGNERIA
CORSO DI LAUREA IN INGEGNERIA INFORMATICA
LA LOCALIZZAZIONE IN INTERNI
TRAMITE UNA RETE WIRELESS
ETHERNET
Relatore:
Correlatore:
Candidato:
Chiar.mo Prof. G. Conte
Chiar.mo Prof. F. Zanichelli
Dario Lodi Rizzini
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
1
Il problema della Localizzazione
Lo scopo dello studio è localizzare un dispositivo radiomobile in
interni tramite le intensità dei segnali trasmessi dai punti di accesso
di una rete Wireless Ethernet.
Peculiarità del problema:
• La scelta di operare in interni
→ complica la descrizione della propagazione delle onde radio
a causa del fenomeno dei cammini multipli;
→ rende impossibile l’applicazione di tecniche classiche di
localizzazione (triangolazione).
• L’impiego di hardware non dedicato:
→ maschera le caratteristiche fisiche e crea problemi di
interfacciamento e di interpretazione dei dati;
→ limita i costi e sfrutta la diffusione delle reti Ethernet.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
2
Il problema della Localizzazione
Il problema appartiene alla vasta classe di problemi context-aware.
1. Posizione
Intensità
dei segnali
Localizzatore
…
AP1 AP2
(vettore di
coordinate
reali)
2. Stato
APM
Access point della rete
(identificati dal MAC address)
(appartiene ad un
insieme discreto
di posizioni)
Pre-conoscenza
del contesto
(posizioni degli AP,
mappatura ed
apprendimento, ecc.)
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
3
Tecniche di Localizzazione
I vari approcci alla localizzazione possono essere classificati in
due categorie:
• Metodi basati sull’analisi della propagazione delle onde radio
in interni → definiscono un modello fisico in grado di descrivere
le modalità con cui l’onda radio si propaga.
• Metodi di fingerprinting → si limitano al confronto fra gli stimoli
ricevuti e le cosiddette impronte dei segnali ricavate in posizioni
fisse dette stati, durante la fase di mappatura.
→ si possono fare rientrare in questa categoria, con le dovute
differenze, anche le tecniche basate sulle reti neurali.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
4
Modelli basati sull’analisi della propagazione delle onde
radio in interni
L’efficacia di questa classe di tecniche dipende dalla capacità di descrivere con un
modello fisico le modalità di propagazione dell’onda radio.
Un modello completo deve essere in grado di prevedere l’effetto dei cammini
multipli sul segnale rilevato dal ricevitore.
Esempi:
• tecniche di ray-tracing;
• modelli probabilistici (Rayleigh e Rician fading, modelli basati sulla distribuzione di
Poisson)
Vantaggi:
• Non richiedono una preventiva mappatura.
• Spiegano completamente la situazione fisica.
Svantaggi:
• Sono molto complessi.
• Sono più adatti a risolvere il problema inverso (posizione → intensità del segnale)
• Richiedono una buona conoscenza delle grandezze fisiche in gioco (valori restituiti
dalla scheda, caratteristiche dei materiali, ecc.).
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
5
Tecniche di fingerprinting
Le tecniche dette di fingerprinting si basano sulla possibilità di individuare una impronta il
grado di caratterizzare un insieme di posizioni scelte a priori durante la fase di mappatura,
dette stati.
• La mappatura è quella fase in cui viene definito l’insieme degli stati ed a ciascuno stato
viene associata la corrispondente impronta.
• L’impronta è l’insieme dei parametri in grado di caratterizzare uno stato derivanti dalla
elaborazione delle intensità dei segnali rilevati durante la mappatura; a seconda dei metodi
l’impronta può essere data dalla media o dalla distribuzione delle intensità.
Le tecniche di fingerprinting esaminate: algoritmo NNSS e metodo basato sull’inferenza
bayesiana.
Vantaggi:
• L’efficacia e la semplicità di questi metodi.
• Non richiedono una precisa conoscenza delle caratteristiche fisiche del contesto in
cui operiamo (alto livello di astrazione).
Svantaggi:
• Mappare il segnale è una operazione costosa in termini di tempo.
• Non portano ad una spiegazione delle distribuzioni dei segnali, si limitano al
confronto.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
6
Algoritmo NNSS
Il metodo dello stato più vicino nello spazio dei segnali (o nearest neighbor in
signal space, NNSS) assume che uno stato possa essere caratterizzato dalle medie
delle intensità dei segnali provenienti da ciascuna stazione base.
Impronta: (BS1, BS2,…, BSM) → (ss1j, ss2j,…,ssMj)
dove ssij è l’intensità media del segnale proveniente da BSi nello stato sj.
La localizzazione avviene per confronto fra l’impronta di ciascuno stato (ossia
l’insieme delle impronte detto spazio dei segnali) e le medie dei segnali ottenute in
tempo reale x = (x1, x2,…,xM).
Per confrontare gli stimoli ambientali e le impronte si ricorre ad una norma:
La posizione individuata alla fine dal localizzatore NNSS può essere:
• la posizione dello stato più vicino sj, ossia tale che
Lj(x) = min {L1(x), L2(x),..., LN(x)};
• il baricentro dei k stati più vicini ad x nello spazio dei segnali.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
7
Metodo basato sull’inferenza bayesiana
Il metodo di inferenza bayesiana considera come impronta di uno stato l’intera
distribuzione delle intensità dei segnali per ciascuno dei punti di accesso della rete.
La procedura del confronto è più complessa: occorre definire in modo preciso il concetto di
osservazione inteso come vettore:
o = < k, f1,…, fM, (BS1, λ1),…, (BSk, λk) >
dove k è il n.ro delle misure comprese in una osservazione, fi il n.ro di volte che si riceve un
segnale dal i-esimo access point, (BSj,λj) la j-esima misura avente intensità λj.
Il risultato finale è la distribuzione delle probabilità πi di trovarsi nello stato si, che viene
aggiornata in seguito ad una osservazione o secondo la formula di Bayes:
Assumendo l’indipendenza nel comportamento dei diversi access point è possibile calcolare le
probabilità condizionate come
dove ciascun fattore della produttoria si può ricavare empiricamente durante la mappatura.
La posizione restituita è quella dello stato con maggiore probabilità πi.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
8
Strumenti di lavoro
Hardware impiegato: rete WiFi (IEEE 802.11b) del Dipartimento di
Ingegneria dell’informazione, scheda di rete wireless PCMCIA,
notebook.
Principali difficoltà nello sviluppo dell’applicazione di
localizzazione:
• Interfacciamento con il dispositivo wireless, definizione della
natura e delle modalità di acquisizione dei dati sulle intensità.
• Scelta delle strutture dati necessarie per una gestione efficiente e
razionale del confronto fra impronte ed intensità, nel calcolo delle
probabilità, ecc.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
9
Luogo delle esperienze
15.5 m
39.3 m
Pianta della palazzina 1 della sede scientifica del Dipartimento di Ingegneria dell’Informazione
nel quale si sono svolti i test di localizzazione.
Stati scelti per i test finali di localizzazione.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
10
Le impronte
Le distribuzioni delle intensità dei segnali ottenute sperimentalmente si
contraddistinguono per irregolarità e varietà.
Misurando nella stessa
posizione l’intensità del segnale
proveniente da un determinato
punto di accesso in momenti
diversi, è possibile riscontrare
lo stesso andamento nella
distribuzione.
Anche la media dell’intensità
subisce poche variazioni.
Nell’esempio in figura le medie sono pari a 61.328, 55.150, 62.439 e 60.275; dunque c’è un solo caso
anomalo.
→ È possibile parlare di impronta caratteristica di una posizione.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
11
Valutazione dell’impatto della quantità di dati
La durata della fase di mappatura e la rapidità della risposta durante la localizzazione
dipendono dalla capacità di descrivere un’impronta con una quantità limitata di misure.
L’andamento della PMF tende a conservarsi
al variare della quantità di misure impiegate
per ottenerla.
L’errore relativo commesso sulla media
è limitato. Con sole 20 misure è al di
sotto del 3.5%.
Gli scostamenti del valore delle probabilità
possono però essere anche notevoli.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
12
Risultati
90%
75%
50%
I risultati ottenuti con il più
sofisticato metodo di inferenza
bayesiana sono inferiori rispetto a
quelli attesi e presentati nelle
pubblicazioni.
Possibili cause:
→ squilibri nelle distribuzioni dello
spazio degli stati;
→ stati vicini non hanno necessariamente
impronte simili.
L’algoritmo NNSS ha prestazioni
nettamente superiori: tende a
mantenere l’errore vicino alle
dimensioni del reticolo di stati (2 m).
Per ovviare alla dispersione dell’algoritmo probabilistico è stata introdotta una soluzione euristica.
• L’algoritmo NNSS è usato per selezionare i k stati più vicini nello spazio dei segnali.
• L’algoritmo basato sull’inferenza bayesiana è applicato solo sui k stati individuati.
Vantaggi:
• Stabilizzazione dei risultati del metodo probabilistico.
• Risultati confrontabili con l’algoritmo NNSS se non migliori (per alcuni percentili).
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
13
Conclusioni
• Le prestazioni complessive del nostro sistema sono buone con ciascuno dei
metodi testati, escludendo l’algoritmo basato sull’inferenza bayesiana.
Metodo
Percentile 50%
Percentile 75%
Percentile 90%
Algoritmo NNSS
1.58 m
2.20 m
4.08 m
Algoritmo bayesiano
2.25 m
3.00 m
5.62 m
Soluzione euristica
1.60 m
2.40 m
3.40 m
• Se lo scopo principale del nostro studio è stato raggiunto, l’approccio alla
localizzazione adottato non consente una piena comprensione della situazione
fisica; ciò limita in parte la validità dei risultati (esistenza dell’impronta, impatto
della quantità dei dati, ecc.) in quanto sono ottenuti solo per via empirica.
• Una migliore comprensione delle ragioni delle prestazioni non ottimali del
metodo basato sull’inferenza bayesiana potrebbe portare ad approfondimenti e
a nuove soluzioni nell’ambito degli algoritmi probabilistici.
La Localizzazione in interni tramite una rete wireless Ethernet - Dario Lodi Rizzini
15