Localizzazione - Problema, Tecniche,...

La LocalizzazioneRanging

PositioningConclusioni

LocalizzazioneProblema, Tecniche, Algoritmi

Luca Pappalardo

Dipartimento di Informatica - Università di Pisa

Reti mobili: Ad Hoc e di sensori, 2011

Luca Pappalardo Localizzazione

SommarioCosa tratteremo

1 LA LOCALIZZAZIONE2 CLASSIFICAZIONE DELLE TECNICHE

Anchor based, Anchor free, Range based, Angle based,Range free

3 RANGING

ToA, TDoA, AoA, RSS4 POSITIONING

MinMax, Triangolazione, Trilaterazione, Multilaterazione

3 RANGING

Dove sorge, cos’èGPSMotivazioneClassificazione

La localizzazione

In una RETE DI SENSORI i nodi possono essere disposti:

Metodologicamente (uomini, robot).Le coordinate dei nodi possono essere programmateall’interno dei dispositivi.

Casualmente (aerei).I nodi devono essere in grado di calcolare automaticamentela propria posizione.

La localizzazione

Non sempre siamo a conoscenza a priori dell’esattaposizione dei sensori.Se la posizione è sconosciuta, i dati raccolti non hannosignificato.Anche quando li conosciamo c’è il problema della mobilità.E’ di fondamentale importanza riuscire a localizzare ognisingolo nodo della nostra rete.

La localizzazione

La localizzazioneGPS (Global Positioning System)

GPS è un sistema accurato di stima della posizione.Non può essere utilizzato in ambienti indoor perchè usasegnali proveniente dal satellite.

La localizzazioneGPS (Global Positioning System)

GPS è un sistema accurato di stima della posizione.Non può essere utilizzato in ambienti indoor perchè usasegnali proveniente dal satellite.

La localizzazioneMotivazione

MotivazioneUna localizzazione accurata e a basso costo è un requisitocritico per un corretto funzionamento di una rete wireless disensori in ambienti chiusi.

Scenari Anchor based o Anchor free

Possiamo trovarci in due possibili scenari:

Anchor based.Solo i nodi "ancora" conoscono la posizione. Gli altri nodiusano la posizione delle ancore per determinare la propria.Si ottiene un sistema di coordinate assoluto.Anchor free.Nessun nodo conosce la propria posizione. Si ottiene unsistema di coordinate relative.

Anchor based - Vantaggi e Svantaggi

VANTAGGI

Posizione determinata in modo univoco.La posizione può essere utilizzata al di fuori da altri sistemidi localizzazione.

SVANTAGGI

Tutti i nodi ancora devono conoscere la propria posizioneed essere posizionati correttamente nella rete.Gli altri nodi devono essere posizionati vicino alle ancoreper poter essere localizzati.

VANTAGGI

SVANTAGGI

VANTAGGI

SVANTAGGI

VANTAGGI

SVANTAGGI

VANTAGGI

SVANTAGGI

VANTAGGI

SVANTAGGI

Anchor free - Vantaggi e Svantaggi

VANTAGGI

Non ci sono problemi di disposizione dei nodi.I nodi possono essere disposti in modo casuale.

SVANTAGGI

La posizione è valida solo all’interno della rete.L’assenza di nodi ancora produce una propagazionedel’errore rispetto ad una rete ANCHOR BASED.

VANTAGGI

SVANTAGGI

VANTAGGI

SVANTAGGI

VANTAGGI

SVANTAGGI

VANTAGGI

SVANTAGGI

VANTAGGI

SVANTAGGI

Determinazione della posizione

Stabilito lo scenario ANCHOR BASED/ANCHOR FREE, ilcalcolo della posizione si effettua in base alla conoscenzadella distanza che separa i nodi.Ci sono tre famiglie di tecniche:

Range basedAngle basedRange free

Tecnica RANGE BASED

Basata sulla distanza euclidea.Vengono effettuate misurazioni per conoscere la distanzatra i nodi.Mini-Max, Trilaterazione, Multilaterazione

Tecnica RANGE BASED

Tecnica ANGLE BASED

Basata sulla distanza angolare tra i nodi della rete.Sfrutta proprietà geometriche e trigonometricheSi usano algoritmi come la Triangolazione.

Tecnica ANGLE BASED

Tecnica RANGE FREE

Indipendente dalla distanza euclidea.Usano coordinate virtualiLa corrispondenza tra coordinate virtuali e fisiche èlasciata la nodo sink

Tecnica RANGE FREE

Fasi della localizzazione

Negli algoritmi di localizzazione sono identificabili tre fasi:1 Ranging

Vengono stimate le distanze attraverso particolarimisurazioni

2 PositioningUna volte determinate le distanze un nodo puòdeterminare la propria posizione con un certa precisione.

3 RefinementL’accuratezza della posizione viene migliorata attraversouna procedura iterativa.

Time of arrival (ToA)Time difference of arrivalAngle of arrivalRSS

RangingTecniche

Stima delle distanze attraverso misurazioni fra nodi:Time of arrival (ToA)Time Difference of Arrival (TDoA)Angle of Arrival (AoA)Received Signal Strength Indicator (RSS)Carrier phase

RangingTecniche

Time of arrival

La stima della distanza è ricavato misurando il tempo dipropagazione del segnaleTime of Flight: Tf = d/c

d è la distanza tra i nodic è la velocità di propagazione (c = 299792,458km/s)

Due modalità: One-way TOA, e Two-Way TOA

Time of arrival

One-way TOA

A trasmette segnale al tempot1. Arriva a B al tempo t2Il Tf è la differenza tra i dueistantiB risale alla distanza da A(velocità di trasmissione nota)

One-way TOA

Two-way TOA

A trasmette segnale altempo t1. Arriva a B altempo t2B elabora il messaggio intempo Td e poi rispondead ATf =

(t2−t1)+(t4−t3)2

Two-way TOA

(t2−t1)+(t4−t3)2

Two-way TOA

(t2−t1)+(t4−t3)2

Two-way TOA

(t2−t1)+(t4−t3)2

Time difference of arrival

A trasmette prima un RF epoi un USI due segnali hannovelocità diverse (US piùlento)I ricevitori deducono ladistanza dalla differenzedegli istanti e dalle velocitàdi propagazione.

Angle of arrival

Antenne direzionali perstimare l’angolo di arrivodei segnaliu misura l’angolo di arrivodei segnali in base ad unsistema angolareProblemi: antenne,interference, ostacoli

Angle of arrival

Un segnale si attenua durante la propagazioneDistanza calcolata in base all’intensità del segnaleLa stima della potenza del segnale (in dBm) è data dal’indicatore RSSI (Received Signal Streght Indicator)Non necessario hardware aggiuntivoNon è precisissimo

Distanza dal trasmettitore valutata con l’equazione di Friis

PR = PTGT GRλ

(4π)2dn (1)

PR e PT : potenza del segnale (Watt) ricevuto e trasmessoGR e GT : guadagno dell’antenna ricevente e trasmittenteλ = c/f : lunghezza d’onda dove (f frequenza)d : distanza in metrin: constante di propagazione del segnale (dipendedall’ambiente)

PR = PTGT GRλ

(4π)2dn (1)

PR = PTGT GRλ

(4π)2dn (1)

PR = PTGT GRλ

(4π)2dn (1)

PR = PTGT GRλ

(4π)2dn (1)

PR = PTGT GRλ

(4π)2dn (1)

PR = PTGT GRλ

(4π)2dn (1)

Potenza da watt a dBm tramite

P[dBm] = 10log10(103P[W ]) (2)

Combinando la (1) e la (2) ed applicando le proprietà deilogaritmi:

RSSI = −(10nlog10d− A) (3)

dove A è la potenza del segnale ricevuto (dBm), a distanzadi un metro con costante di propagazione n.

P[dBm] = 10log10(103P[W ]) (2)

RSSI = −(10nlog10d− A) (3)

P[dBm] = 10log10(103P[W ]) (2)

RSSI = −(10nlog10d− A) (3)

Andamento della potenza in funzione della distanza (n = 2,A = −40 dBm)

Aggiustiamo la relazione isolando la distanza:

d = 10(A− RSSI

10n) (4)

Con questa formula possiamo calcolare la distanza tra duenodi conoscendo il valore RSSI ed i paramentri A ed n.

RSS: PROBLEMI

Figure: Riflessione

PROBLEMI IN RSSRiflessioneIl segnale si propaga ancheattraverso un percorso riflesso(provoca Multi-path fading)AssorbimentoAltera il normale decadimentodell’intensità che si avrebbe inspazio liberoProblema in ambienti indoor

RSS: PROBLEMI

Figure: Riflessione

RSS: PROBLEMI

Figure: Riflessione

RSS: PROBLEMI

Figure: Riflessione

RSS: PROBLEMI

Figure: Riflessione

Mini-MaxTriangolazioneTrilaterazioneMultilaterazione

Positioning

Dopo il ranging i nodi determinano la propria posizione.Questa fase è detta positioning (non accurata)Vari algoritmi:

Min-Max, Triangolazione. Trilaterazione, Multilaterazione

Positioning

MIN-MAX

Ideato da Andreas Savvides, è uno dei più diffusiEstrema semplicità di implementazioneStime non accuratissime ma vicine a quelle dellamultilaterazioneMetodo range-based e anchor-basedUsa RSSI

MIN-MAX

Converte RSSI in una distanza dida un nodo ancora iDisegna due linee orizzontali edue verticali a distanza di dall’ancoraOtteniamo un quadrato di lato 2di

MIN-MAX

L’intersezione determina unquadrato con estremi

[max(xi − di),max(yi − di)] x[min(xi + di),min(yi + di))]

Il centro del quadrato è laposizione stimataPiù piccola è l’area, maggiore èl’accuratezza

MIN-MAX

Triangolazione

Calcola le coordinate del nodo a partire dagli angoli cheforma con i nodi ancora con coordinate noteUtiilizza regole trigonometriche per calcolare le coordinateE’ anchor based e angle based

Triangolazione

La distanza AB è notaPossiamo facilmente calcolare:

AC = ABsinβsinγ e BC = ABsinα

RC = BCsinα = ACsinβDa RC ricaviamo le coordinate

Triangolazione

Trilaterazione

Più complesso ma più efficientedel Min-MaxI centri dei cerchi sono lecoordinate delle ancoreIl raggio è la distanza stimataI nodo target si trovanell’intersezione tra i cerchi

Trilaterazione

Equazione della circonferenza(xi , yi) centro, ri raggio:

(x − xi)2 + (y − yi)

2 = r2i

L’intersezione è:{ (x − x1)

2 + (y − y1)2 = r2

1(x − x2)

2 + (y − y2)2 = r2

2(x − x3)

2 + (y − y3)2 = r2

Trilaterazione

Equazione della circonferenza(xi , yi) centro, ri raggio:

(x − xi)2 + (y − yi)

2 = r2i

L’intersezione è:{ (x − x1)

2 + (y − y1)2 = r2

1(x − x2)

2 + (y − y2)2 = r2

2(x − x3)

2 + (y − y3)2 = r2

Trilaterazione - Altri casi

Punto di intersezione non unico Nessun punto di intersezione

Due punti di intersezioneDisegnano solo due cerchiSe il punto è unico OKSe non si toccano aumentiamo iraggi in modo proporzionaleSe ci sono due punti prendiamoquello a distanza minore dallaterza ancoraIteriamo per tutti e tre i nodi ecalcoliamo la media dellecoordinate della posizionestimata

Multilaterazione

Caso generale della trilaterazione con distanze rispetto adn puntiUtile perchè le misura di distanza sono soggette a errori eteniamo conto di tutti i punti di riferimento

Multilaterazione

Caso generale della trilaterazione con distanze rispetto adn puntiUtile perchè le misura di distanza sono soggette a errori eteniamo conto di tutti i punti di riferimento

Multilaterazione

Calcolo applicato ad un singolo puntoIl nodo deve essere vicino ad almeno tre nodiIl sistema di equazioni diventa:

(x − x1)2 + (y − y1)

2 = r21

(x − x2)2 + (y − y2)

2 = r22

...(x − xn)

2 + (y − yn)2 = r2

Multilaterazione

(x − x1)2 + (y − y1)

2 = r21

(x − x2)2 + (y − y2)

2 = r22

...(x − xn)

2 + (y − yn)2 = r2

Multilaterazione

(x − x1)2 + (y − y1)

2 = r21

(x − x2)2 + (y − y2)

2 = r22

...(x − xn)

2 + (y − yn)2 = r2

Multilaterazione

(x − x1)2 + (y − y1)

2 = r21

(x − x2)2 + (y − y2)

2 = r22

...(x − xn)

2 + (y − yn)2 = r2

Multilaterazione atomica

Risolviamo il sistema in forma Ax = bx = (AT ) · A)−1 · AT · b

Stessi casi della TrilaterazioneValutiamo la soluzione con il residuo tra le distanze ri e ledistanze dalla posizione stimata (xm, ym)

residuo =∑n

√(xi−xm)2+(yi−ym)2−ri

Se il residuo è la misura è soggetta a forti errori e convieneripeterla

residuo =∑n

Conclusioni

La problematica della localizzazione è soggetta anumerosi studi e sperimentazioniMiglioramento delle tecniche (ranging)Applicazioni delle WSN dotate di sistema di localizzazione

Conclusioni

Appendix Per ulteriori letture

Per ulteriori letture I

Marco RisiConfronto di tecniche di localizzazione per le WSN basatesu RSSITesi di laurea, 2009.

Alberto Realis-LucLocalizzazione in reti di sensori ZigBeeTesi di laurea, 2009.

Paolo sperandioAlgoritmi di localizzazione per reti di sensori wirelessTesi di laurea, 2007.

Appendix Per ulteriori letture

Per ulteriori letture II

Cuccado, De Franceschi, Fauri, SartorAnalisi di algoritmi di autolocalizzazione per reti di sensoriwirelessTesi di laurea, 2011.

Localizzazione - Problema, Tecniche,...

Documents

Transcript of Localizzazione - Problema, Tecniche,...