Volevo dedicare poche righe di questa tesi a ringraziare tutti coloro che col-laborando o credendo in questo lavoro mi hanno sostenuto:
in particolare volevo ringraziare il prof. Andrea Torsello per la sua parteci-pazione sempre viva e i suoi preziosi suggerimenti e consigli, che no alla ne hanno reso possibile la conclusione di questa tesi.
Volevo ringraziare la mia famiglia che mi ha sempre sostenuto credendoci alla realizzazione di questo progetto.
Un po' di algoritmi per Zigbee
February 10, 2013
Abstract
In questa tesi vengono applicati a dei sensori zigbee vari algoritmi, comunemente usati in intelligenza arti ciale.
Vengono trattati due tipologie di macro-situazioni con o senza apprendi-mento.
Per quanto riguarda i sensori, oggetto di questa tesi, questi rilevano la loro distanza grazie all'abbattimento di un segnale che gli stessi sono in grado di tresmettere e di misurare.
Viene da se, che associando questa intensità di segnale ad una distanza, gli algoritmi più usati saranno quelli di trilaterazione o multilaterazione: algoritmi questi in grado di mettere in relazione più distanze con delle posizioni o delle aree.
Queste tipologie sono, in questa tesi, sviluppate sotto la dicitura di algoritmi di steepest, in realtà, questo è un algoritmo (Steepest descendent method) usato per risolvere i sistemi di equazioni non lineari, dovuti proprio al concetto di distanza.
1. In prima analisi i problemi sono associati direttamente a misure di dis-tanze, in particolare viene usato l'algoritmo LLE (Linear Loacal Embed-ding).
L'idea, essenzialmente, è quella di considerare ogni distanza tra sensori ssi e sensore mobile, come una dimensione a sè: LLE è un algoritmo di riduzione dimensionale per cui proietta uno spazio di dimensione molto grande, in uno spazio di dimensione più piccola in questo caso in tre di-mensioni. Nello spazio di arrivo vengono poi determinati i vicini e così, anche i corrispondenti nello spazio di partenza dove viene stimato il punto attraverso l'applicazione dello stesso algoritmo.
2. Nell'evoluzione del progetto si mettono da parte le distanze per usare l'RSSI, misura di decadimento del segnale, data dai sensori. In particolare vengono considerate più situazioni:
In questa situazione il sistema è in grado di autodeterminare tutti i parametri di funzionamento la A la N in questione e ovviamente la posizione del sensore mobile, anche con qualche perturbazione ambi-entale.
L'altra prevede una ricostruzione dell'ambiente fatta con l'uso dei sensori ssi:
con questo sitema vengono ricavate le varie N ed A tra e dei sen-sori ssi , viene interpolata la N tra l'ipotetica posizione del sensore mobile e i vari sensori ssi.
Usando lo steepest descendent method, questo sposta il punto in modo da avvicinarsi alla soluzione, sino a che non vi converge con una determinata tolleranza.
In ogni ipotesi di riposizionamento del sensore mobile viene ristimata la N.
3. A conclusione della tesi è stata eseguita una prova sperimentale dell'algoritmo LLE con campionamento.
La prova è stata eseguita in un ambiente molto disturbato. Questa è consistita in
un campionamento dell'ambiente che ha prodotto misure di RSSI che hanno contribuito, assieme alle posizioni, a costituire più griglie di misura.
Nelle elaborazioni delle posizioni del sensore mobile attraverso LLE. sono stati elaborati dallo stesso più parametri:
direttamente le posizioni pesate attraverso l'RSSI dei vicini o indiret-tamente con le N pesate attraverso RSSI e quindi la determinazione della posizione.
L'algoritmo è stato applicato variando il numero dei vicini per l'interpolazione:
questo ha consentito, attraverso lo studio degli errori, di stabilire le con gurazioni ottime per le singole griglie.
1
1per ambiente uniforme si pensa ad una situazione in cui tra tutti i sensori presenti N è
Contents
I Problemi e tecnologie
10
1 Il problema 10
2 Sistemi di localizzazione 11
2.1 Componenti base di un sistema di localizzazione . . . 11
2.2 Grandezze misurabili per la localizzazione . . . 11
2.3 Sistemi basati sul tempo . . . 11
2.3.1 Time of Arrival . . . 12
2.3.2 Time Dierence of Arrival . . . 12
2.4 Sistemi basati sull'intensita . . . 12
2.5 Sistemi basati sull'interferometria . . . 13
2.6 Sistemi basati sull'angolo di provenienza . . . 14
2.7 Riepilogo . . . 14 3 Algoritmi di localizzazione 15 3.1 Triangolazione . . . 15 3.2 Trilaterazione . . . 16 3.3 Multilaterazione . . . 17 3.3.1 Multilaterazione atomica . . . 17 3.3.2 Multilaterazione iterativa . . . 18 3.3.3 Multilaterazione collaborativa . . . 18 3.4 Min-max . . . 19 4 Zigbee 21 4.1 I protocolli . . . 21
4.2 Elementi essenziali per la de nizione di una rete ZigBee. . . 21
4.2.1 ZigBee Coordinator . . . 22
4.2.2 ZigBee Router . . . 22
4.2.3 ZigBee End Device . . . 22
5 Qualche considerazione iniziale 23 5.1 Premessa . . . 23
5.2 Una ipotesi iniziale . . . 23
5.3 Un riferimento . . . 24
5.4 Più riferimenti . . . 24
5.5 Le aree . . . 25
5.6 Propagazione teorica del segnale . . . 27
5.7 Considerazioni . . . 28
5.8 Un po' di conti . . . 29
5.9 In caso di due circonferenze . . . 29
5.9.1 Facciamo un esempio . . . 31
II Le soluzioni
35
6 LLE Linear Local Embedding 35
6.1 Modello con apprendimento . . . 35
6.2 Senza Apprendimento . . . 39
7 Inserimento RSSI 43 7.1 Senza uso di impostazioni . . . 43
8 Determinazione dell'ambiente 47 8.1 Perturbazione dell'ambiente . . . 47
8.2 Minimizzare l'energia . . . 49
8.3 Qualche considerazione . . . 50
8.4 Cosa si fa degli N trovati . . . 50
8.5 Radial basis function . . . 50
8.5.1 Approssimazione . . . 51
8.6 Medie Pesate . . . 51
9 La chiusura del cerchio 52 9.1 Come si procede usando Thin plate spline . . . 52
9.1.1 Il sistema . . . 53
9.2 I conti . . . 54
9.3 Convergenza errata . . . 57
9.3.1 Un po' di valutazioni . . . 57
9.4 La soluzione considerando la Nix come la Ai o la Rixcome un semplice fattore ambientale . . . 58
9.4.1 Il sistema usando Thin plate spline come interpolatore . . 58
9.4.2 I conti . . . 59
9.5 Come si procede usando la media pesata come interpolatore . . . 61
III Test
63
10 Speci che tecniche 63 11 Descrizione ambiente di misura 65 11.1 Descrizione della misura . . . 6712 Trattamento dei dati 68 12.1 Dati trasformati per la rilevazione dell'ambiente tramite i sensori ssi . . . 68
12.2 Dati trasformati per l'algoritmo LLE . . . 69
13 Le varie fasi delle misure 71
13.1 Gestione esperimento LLE . . . 71
13.2 Prova di LLE da RSSI monitorando l'ambiente. . . 71
13.3 L'uso delle varie griglie e di un diverso numero di Vicini . . . . 73
14 Analisi dei risultati 74 14.1 Rilevazioni griglie ed errori . . . 74
14.1.1 Errori in funzione delle griglie . . . 75
14.1.2 Errori in funzione delle griglie, ripetto al numero di vicini 77 14.2 Conclusione con numero ottimo di vicini . . . 81
15 Conclusioni 82
IV Bibliogra a
83
V Appendice
84
16 Algoritmi usati in questa tesi 84 16.1 E.M. Expectationmaximization algorithm [8, 9, 10] . . . 8416.1.1 k-means . . . 84
16.2 Linear Local Embedding [3] . . . 85
16.2.1 Notazione e convenzioni . . . 87
16.2.2 L'intuizione su cui è basato: . . . 87
16.2.3 L'algoritmo . . . 89
16.3 Steepest descendent method[5] . . . 89
16.4 Radial bias functions . . . 91
16.4.1 Thin plate spline . . . 91
16.5 Box Muller method[7] . . . 91
16.5.1 Motivazione . . . 91
16.5.2 Metodo . . . 93
List of Figures
1 Principio dell'interferometria di fase . . . 132 Il punto C oggetto di triangolazione . . . 15
3 Il piano z = 0 mostra i centri delle tre sfere: P1, P2 e P3 di raggio: r1, r2 e r3; e le distanze: d, i, e j. B è il punto di intersezione delle tre sfere. . . 16
4 Il centro del quadrilatero formato dall'intersezione dei tre quadrati da una stima della posizione del nodo mobile che non dierisce di molto dall'intersezione delle circonferenze . . . 20
5 rappresantazione sfera cono . . . 23
6 Distanza rilevata con un solo sensore con altezza ssata . . . 24
8 Situazione con l'altezza ssata a metà di quella della stanza . . . 26
9 Quadrato circoscritto . . . 26
10 Intersezioni con 2 circonferenze e tre circonferenze . . . 27
11 Circonferenza centro (α, β) e raggio r . . . 29
12 Retta passante per l'intersezione di due circonferenze . . . 30
13 Esempio con 2 circonferenze . . . 31
14 Schema dell'uso di LLE per la riduzione dimensionale: le letture delle distanze, da parte dei sensori, vengono considerate dimen-sioni a se stanti; l'algoritmo proietterà poi lo spazio in dimensione 3. . . 35
15 LLE con apprendimento: rappesentazione griglia sensore mobile e sensori ssi a so tto. . . 36
16 Rappresentazione delle distanze in un piano 3d . . . 36
17 Vicini del punto mobile nello spazio di arrivo tridimensionale . . 37
18 Vicini del punto mobile nello spazio di partenza . . . 38
19 LLE senza apprendimento . . . 39
20 Vicini nello spazio di arrivo senza apprendimento . . . 40
21 Vicini nello spazio di partenza senza apprendimento . . . 40
22 Steepest variazione della posizione . . . 41
23 Steepest variazione della f . . . 42
24 Ambiente di misura senza setting . . . 43
25 N tra i sensori ssi N12N13... N1nN21N23... N2n...Nmm+1Nmm+2...Nmn 48 26 A dei sensori ssi A1A2...An. . . 48
27 Situazione N iniziale tra i sensori ssi . . . 61
28 La Nx risultante . . . 62
29 Apparecchiature usata per l'esperimento . . . 63
30 Come primo step è stata scelta una porzione quadrata dell'azienda, quella più vicina alla mia scrivania . . . 65
31 Le piastrelle sopra schematizzate . . . 66
32 Angolo di partenza delle misure . . . 66
33 La Stanza . . . 67
34 Passaggio dal CSV a dati usabili . . . 68
35 Tutti i punti campionati: in blu in rosso sono rappresentate le posizioni dei punti ssi . . . 70
36 Griglia1 e griglia2 : griglia a passo costante 60x80, e la seconda a passo 120x80 . . . 70
37 Griglia3 a passo costante 120x180 e griglia4 a passo variabile alternato 20x80 e 40x80 . . . 71
38 Schema di funzionamento LLE con apprendimento . . . 72
39 Situazioni di misura reali rappresentate da Matlab: La x rossa rappresenta il calcolo diretto della posizione da parte di LLE pe-sato attraverso L'RSSI; la x verde è invece il risultato dell'elaborazione della N pesato con l'RSSI da parte di LLE; la x blu è ottenuta dalla media totale delle N su tutti i punti della griglia. . . 74
40 Visualizzazione errore calcolato con la Griglia1 nei vari punti di test con 4 vicini. L'errore è un errore assoluto espresso in cm. . 75
41 Visualizzazione errore calcolato con la Griglia2 nei vari punti di test con 3 vicini. L'errore è un errore assoluto espresso in cm. . . 76 42 Visualizzazione errore calcolato con la Griglia3 nei vari punti di
test con 3 vicini. Questa è la soluzione migliore per la determi-nazione dalla posizione x rosse. . . 76 43 Visualizzazione errore calcolato con la Griglia4 nei vari punti di
test con 6 vicini. L'errore è un errore assoluto espresso in cm. . . 77 44 Visualizzazione errore Griglia1 in funzione al numero vicini: le
linee rappresentano solo un modo comodo per leggere il gra co, facendo intuire delle tendenze: seguendo la linea rossa si indi-vidua subito che il minimo errore con LLE sull'elaborazione della posizione, si ha con 4 sensori vicini. La linea verde riguarda l'elaborazione di N con 5, la linea blu costante la N media. La somma degli errori assoluti è espressa in m. . . 78 45 Risultato errori Griglia1 con 5 vicini con media pesata con errori
molto bassi . . . 78 46 Visualizzazione errore Griglia2 in funzione al numero vicini . . . 79 47 Visualizzazione errore Griglia3 in funzione al numero vicini . . . 79 48 Situazione migliore Griglia3 calcolo N con LLE: elaborata con 3
vicini . . . 80 49 Visualizzazione errore Griglia4 in funzione al numero vicini . . . 80 50 Un piano arricciato:swiss roll . . . 86 51 Un one dimensional manifold nascosto in tre dimensioni . . . 86 52 Steepest Descendent method trova il minimo con un pattern
zig-zag dove la nuova direzione cercata è ortogonale alla precedente . 90 53 La convergenza del metodo Steepest Descendent. La dimensione
del passo diviene sempre più piccola, girando e rigirando the val-ley(mostrate come linee di contorno), no a che trova il minimo . 91
Part I
Problemi e tecnologie
1 Il problema
Il sistema ha due tipologie di moduli ZigBee: i nodi di riferimento o ssi e i nodi mobili. I nodi di riferimento restano nella stessa posizione nota e vengono usati dai nodi mobili, liberi di muoversi, per fare misure di RSSI.
Il sistema traduce le misure di RSSI in distanze e tramite algoritmi di multi-laterazione fa una stima delle posizioni dei nodi mobili. L'indice RSSI è soggetto a forti variazioni dipendenti dall'ambiente in cui ci si trova, quindi la stima della posizione che ne deriva non è molto precisa.
In questa tesi si vuole aumentare tale precisione usando dei sistemi per cam-pionare l'ambiente.
Tale campionamento da modo, correggendo i parametri ambientali, di ridurre gli errori.
2 Sistemi di localizzazione
2.1 Componenti base di un sistema di localizzazione
In ogni sistema di localizzazione si possono individuare due componenti fonda-mentali:
Punti mobili: corrispondono agli oggetti che si vuole localizzare, la loro posizione non e quindi nota a priori, sono liberi di muoversi all'interno dell'area dove e stato installato il sistema di localizzazione.
Punti di riferimento: vengono installati in posizioni note e vi restano stabil-mente, vengono utilizzati dai punti mobili per calcolare le proprie posizioni.
L'area in cui si vuole installare il sistema di localizzazione dovrà quindi essere interamente coperta da punti di riferimento.
2.2 Grandezze misurabili per la localizzazione
Per poter localizzare e quindi stimare la posizione di un oggetto mobile, occorre raccogliere alcune misure rispetto ad altri punti di riferimento le cui posizioni sono note a priori. Queste misure servono a scoprire le distanze dei punti di riferimento oppure le direzioni e quindi gli angoli in cui si trovano rispetto al punto mobile di cui si vuole stimare la posizione.
Un sistema di localizzazione puo misurare le seguenti grandezze per stimare la posizione:
Tempo di viaggio
Intensita Fase (interferometria) Angolo di provenienza
2.3 Sistemi basati sul tempo
Se si riesce a misurare il tempo impiegato da un segnale per propagarsi da una stazione trasmittente ad una stazione ricevente è possibile stimare la distanza tra le due stazioni.
Le onde radio nell'aria si propagano con una velocita di poco inferiore a quella della luce (c = 299792468m=s) e dato che la luce impiega 3,3 ns per percorrere un metro per ottenere una precisione di 30 cm bisognerebbe avere un sistema in grado di rilevare intervalli di tempo no ad un nanosecondo. E' di questo tipo il sistema GPS (che però ha a che fare con distanze molto piu elevate), non puo essere usato in ambienti indoor in quanto i segnali provenienti dai satelliti non riescono ad oltrepassare i muri degli edici.
Una tale precisione è disponibile al momento sui dispositivi UWB (Ultra Wide Band). I sistemi UWB sono i piu precisi ma anche i piu costosi. Invece nel sistema Cricket sviluppato da Crossbow, per fare le misure, usa segnali piu lenti rispetto alle onde radio e cioe gli ultrasuoni. Pur essendo piu economico rispetto ai sistemi UWB, Cricket presenta problemi sulle lunghe distanze proprio per il fatto di usare gli ultrasuoni e questo si traduce nella necessita di installare una maglia" di nodi di riferimento piu tta.
2.3.1 Time of Arrival
Con Time of Arrival (ToA) detto anche Time of Flight (ToF) si intende il tempo impiegato da un segnale radio trasmesso da un singolo trasmettitore per raggiungere un singolo ricevitore remoto.
Tenendo conto del dielettrico presente, tra trasmettitore e ricevitore e conoscendo la velocita di propagazione del segnale (che sara vicina a quella della luce), si potra stimare la distanza tra trasmettitore e ricevitore.
Nel momento in cui si riescono a misurare tempistiche molto piccole questo metodo si dimostra molto accurato. Dato che si ha a che fare con la velocita della luce si otterranno risultati migliori misurando distanze elevate.
La sincronizzazione tra le due stazioni radio e di fondamentale importanza, la stazione ricevente misurera il tempo con un suo orologio interno che dovra essere perfettamente sincronizzato con quello della stazione trasmittente.
Queste misure vengono utilizzate dagli algoritmi di trilaterazione che facendo uso delle distanze tra una stazione radio mobile, di posizione imprecisata, e almeno altre tre stazioni radio sse, di posizione nota, permettono di calcolare la posizione della stazione mobile su di un piano.
2.3.2 Time Dierence of Arrival
E' una tecnica per misurare il tempo di propagazione di un segnale quando si hanno a disposizione dispositivi in grado di trasmettere segnali con velocita di propagazione dierenti.
Un nodo che puo trasmettere sia onde radio (RF) che ultrasuoni (US), trasmette prima un segnale radio e immediatamente dopo un segnale ad ul-trasuoni. Dato che il suono viaggia molto piu lentamente rispetto alle onde radio i nodi nelle vicinanze si vedranno arrivare prima il segnale RF e solo dopo un certo tempo vedranno arrivare anche il segnale US.
Considerando il segnale RF istantaneo si puo dedurre da questa dierenza di tempo, che sarebbe il tempo di propagazione del segnale US, la distanza a cui si trova il nodo trasmittente.
2.4 Sistemi basati sull'intensita
Valutando l'intensita di un segnale ricevuto è possibile stimare la distanza della stazione che l'ha trasmesso.
Nel caso delle reti di sensori e nelle reti WiFi si usa l'indice RSSI (Received Signal Streght Indicator) che indica una stima della potenza del segnale ricevuto in dBm.
In un qualunque collegamento radio reale le onde vengono ri esse e ostruite da tutti gli oggetti illuminati dall'antenna trasmittente.
Calcolare il raggio di trasmissione in un ambiente reale può risultare molto complesso e sarebbero necessarie grandi risorse in termini di potenza di calcolo. Inoltre in alcuni ambienti potrebbero esserci degli oggetti in movimento o delle interferenze radio che andrebbero solo ad aumentare la complessita del sistema.
Dato che nella pratica e molto di cile tener conto di tutte le ri essioni e delle interferenze (e inoltre per una data misura di RSSI si potrebbero avere piu distanze corrispondenti) di solito ci si accontenta di usare la formula:
RSSI = −(10n log10d − A)
opportunamente calibrata scegliendo i parametri A ed n in base all'ambiente in cui ci si trova.
2.5 Sistemi basati sull'interferometria
Se si hanno due antenne separate da una distanza d, su cui le onde radio incidono con un angolo θ si ottiene che il segnale deve percorrere distanze diverse per raggiungere entrambe le antenne.
Questa dierenza si traduce in una dierenza di fase 4φ del segnale ricevuto tra le due antenne.
Con questa formula si puo calcolare la direzione di arrivo del segnale:
θ = sin−1 λ4φ 2πd
Dove λ è la lunghezza d'onda del segnale.
Figure 1: Principio dell'interferometria di fase
E' su questo principio che si basano alcuni sistemi di localizzazione, come per esempio RIPS (Radio Interferometric Positioning System), questi permettono di ottenere una buona precisione ma possono insorgere problemi nel caso il segnale giunga a destinazione da piu percorsi attraverso varie ri essioni. Infatti nel caso in cui il segnale venga ricevuto da percorsi multipli (multipath) può risultare di cile capire quale sia la giusta dierenza di fase su cui fare i calcoli.
In un ambiente indoor si hanno chiaramente molte ri essioni e il sistema, può quindi trovarsi di fronte a problemi computazionalmente molto pesanti non così immediati da risolvere.
2.6 Sistemi basati sull'angolo di provenienza
Per rilevare l'angolo di provenienza occorre un'antenna direzionale oppure un'array di antenne, che, come si e visto prima, grazie all'interferometria di fase, perme-tte calcolare l'angolo di provenienza. Questi sistemi, detti anche AoA (Angle of Arrival ), richiedono antenne piu complesse o la capacita di rilevare piccole dierenze di fase, caratteristiche solitamente non presenti sui moduli piu comuni delle reti di sensori. Conoscendo gli angoli di provenienza dei segnali trasmessi dai punti di riferimento, e possibile calcolare la posizione del punto mobile con algoritmi di triangolazione.
2.7 Riepilogo
Sistema Principio Precisione Costo utente Costo infrastruttura Criticita
Reti ZigBee Onde radio RSSI 1-5 m basso basso precisione
Reti WiFi Onde radio RSSI 1-5 m basso medio precisione, costo
UWB Onde radio ToA 30 cm basso alto costo
Cricket Ultrasuoni TDoA 50 cm basso medio costo
RIPS Interferometria 20-50 cm basso basso multipath
Table 1: Tabella riassuntiva dei sistemi di localizzazione indoor citati preceden-temente
Per costo dell'infrastruttura, si intende il costo necessario per coprire l'area dove si vuole installare il sistema di localizzazione con i moduli che faranno da punti di riferimento.
I punti di riferimento dovranno essere installati con una densita compatibile con la loro portata.
Invece per costo utente, si intende il costo dei singoli moduli da usare come punti mobili che dovranno essere localizzati dal sistema.
3 Algoritmi di localizzazione
3.1 Triangolazione
Con triangolazione, si intende il processo per determinare la posizione di un punto, misurando gli angoli che puntano verso di esso da due punti di posizione nota agli estremi di una linea che è la base del triangolo così formato.
Figure 2: Il punto C oggetto di triangolazione La distanza AB tra i due angoli noti α e β si calcola nel così:
AB = CR
tan α+ CR tan β Dove CR è l'altezza del triangolo di base AB. Dalla precedente CR sarà:
CR = AB 1 tan α+ 1 tan β ricordando che: sin α BC = sin β AC = sin γ AB Così dato che AB è noto si calcola immediatamente:
AC = AB sin β sin γ
BC =AB sin α sin γ CR =AB sin α sin β sin γ = AB sin α sin β sin (α + β)
3.2 Trilaterazione
La trilaterazione è un metodo per trovare l'intersezione della supercie di tre sfere i cui centri e raggi sono noti.
Per quanto riguarda i sistemi di localizzazione i centri delle sfere sono dati dalle coordinate dei punti di riferimento, mentre i raggi sono le distanze rilevate dal punto mobile rispetto ai punti di ssi nelle vicinanze.
L'intersezione delle sfere individua quindi la posizione del punto mobile. In un sistema di riferimento installato su di una supercie piana, come per esempio un piano di un edicio, eliminando l'asse z, il problema si semplica nel trovare l'intersezione di tre circonferenze. Assumendo che le tre sfere abbiano i centri sul piano z = 0 e , se si trasla l'origine del sistema di rifermento nel centro della prima circonferenza.
Figure 3: Il piano z = 0 mostra i centri delle tre sfere: P1, P2 e P3 di raggio: r1, r2 e r3; e le distanze: d, i, e j. B è il punto di intersezione delle tre sfere.
Mettendo a sistema le tre equazioni delle sfere: r12= x2+ y2+ z2 r2 2= (x − d) 2 + y2+ z2 r2= (x − i)2+ (y − j)2+ z2
risolvendo in x :
x = r
2
1− r22+ d2
2d con un po' di conti:
y = r 2 1− r32+ i2+ j2 2j − i jx e per nire z: z = ± q r2 1− x2− y2
Si puo quindi notare che il problema può non avere soluzione nel caso di un numero negativo sotto radice oppure può averne una o due.
Nel caso di due soluzioni può essere utile avere anche una quarta circon-ferenza qualora non fosse possibile si possono usare altri stratagemmi per evitare ambiguita.
Ad esempio il sistema GPS, che fa uso di algoritmi di trilaterazione, quando ha a disposizione solo tre satelliti che portano a due soluzioni assume che quella corretta sia quella piu vicina alla supercie terrestre.
Questo metodo di calcolare la posizione si complica di parecchio quando si hanno degli errori di misura sui raggi delle sfere:
in questo caso si può considerare due raggi per ogni sfera uno massimo e uno minimo le soluzioni saranno date da tutti i punti appartenenti al volume dato dall'intersezione dei tre gusci".
3.3 Multilaterazione
La multilaterazione è il caso generico della trilaterazione in cui si possono avere le distanze non più rispetto a soli 3 punti di riferimento ma questa volta rispetto ad n punti di riferimento.
In un sistema di localizzazione, in cui le misure di distanza rispetto ai punti di riferimento sono soggette ad errori, può essere molto utile ricorrere a questa tecnica di calcolo, che permette di tenere in considerazione le misure rispetto a tutti i punti di riferimento rilevati dal punto mobile.
3.3.1 Multilaterazione atomica
Con multilaterazione atomica si intende quando tale calcolo viene applicato ad un singolo punto mobile per stimarne la posizione, ha un requisito fondamentale: il nodo mobile deve avere nelle vicinanze almeno tre nodi di riferimento con cui può comunicare direttamente con un solo salto.
Poniamo di avere le misure di distanza rispetto a n punti di riferimento di coordinate note: ne risulta un sistema di n equazioni.
L'i-esima equazione non e altro che la circonferenza con centro di coordinate pari al suo i-esimo punto di riferimento (xi; yi)e di raggio ri pari alla distanza
rilevata verso tale punto di riferimento. (x1− x)2+ (y1− y)2= r21 (x2− x) 2 + (y2− y) 2 = r22 ... ... (xn− x)2+ (yn− y)2= r2n
con x si intedende un vettore (xm, ym). Queso solo se tutte le misure sono
perfette ovvero tutte le circonferenze si inteersecano su un punto.
Nel caso molto più realistico in cui le misure non sono perfette, si potrebbero avere circonferenze che si intersecano in piu punti dando origine a un'area di possibili soluzioni oppure potrebbero non intersecarsi aatto, la multilaterazione fornisce la soluzione che piu si avvicina a quella corretta, che quindi tenderà ad essere piu vicina al centro della circonferenza piu piccola e man mano piu distante dai centri dalle altre.
Per valutare la bontà della soluzione si può calcolare il residuo tra le distanze misurate ri e le distanze che si avrebbero dalla posizione stimata (xm; ym):
residuo = Pn i=1 q (xi− xm) 2 + (yi− ym) − ri n
Un residuo molto ampio è indice di un sistema di equazioni inconsistente e questo è dovuto a misure soggette a forti errori.
3.3.2 Multilaterazione iterativa
Con multilaterazione iterativa, si intende il processo eseguito su di un singolo elaboratore, quindi centralizzato, che si occupa di raccogliere tutte le misure da una rete di sensori e di ripetere la multilaterazione atomica su ogni nodo mobile di cui ancora non si conosce la posizione. Dato che non è detto che tutti i nodi mobili possano rispettare il requisito necessario per la multilaterazione si puo usare quest'approccio:
nel momento in cui si e stimata la posizione di un nodo mobile, questo viene considerato come punto di riferimento, con la posizione appena stimata.
In tal modo si aggiungono punti di riferimento al sistema che possono aiutare a stimare la posizione dei nodi mobili che non avevano abbastanza punti di riferimento nelle vicinanze.
3.3.3 Multilaterazione collaborativa
Ci sono dei casi in cui un singolo nodo mobile non ha abbastanza nodi di rifer-imento nei suoi paraggi in cui si trovano invece altri nodi mobili di posizione indeterminata nelle sue stesse condizioni.
In pratica si possono venire a creare delle situazioni in cui alcuni nodi mobili vedono meno di tre nodi di rifermento nelle loro vicinanze (non e quindi possibile
stimare la loro posizione con con la multilaterazione atomica) ma nella rete ogni nodo vede almeno tre altri nodi o mobili o di riferimento. I nodi possono collaborare tra di loro per provare a determinare la posizione de nodi mobili per i quali non è stato possibile trovarla iterando con la multilaterazione.
3.4 Min-max
I calcoli matriciali appena visti per fare la multilaterazione si traducono in numerose operazioni
oating point che risultano molto costose in termini computazionali qualora sia necessario stimare le posizioni di numerosi nodi mobili frequentemente, in un sistema centralizzato o che risultano inappropriate da eseguirsi direttamente sull'hardware limitato dei nodi della rete in un sistema distribuito. Il metodo min-max, ideato da Andreas Savvides molto piu semplice permette di avere delle stime comunque vicine a quelle che si avrebbero con la multilaterazione.
L'idea principale si basa sul costruire dei quadrati (al posto delle circon-ferenze) per ogni punto di riferimento. Ogni punto di riferimento e al centro di un quadrato il cui lato e il doppio della distanza rilevata rispetto a quel punto di riferimento; quindi il quadrato per l'a-esimo punto di riferimento (xa; ya),
rilevato a distanza ra può essere così rappresentato:
Figure 4: Il centro del quadrilatero formato dall'intersezione dei tre quadrati da una stima della posizione del nodo mobile che non dierisce di molto dall'intersezione delle circonferenze
L'intersezione di questi quadrati determina un'altro quadrilatero i cui estremi possono essere facilmente calcolati prendendo i massimi e i minimi di tutte le coordinate:
[max(xi− ri), max(yi− ri)] × [min(xi+ ri), min(yi+ ri)]
4 Zigbee
Questa introduzione è tratta per brevità e ricchezza di particolari da un articolo di test [1]:
Il termine ZigBee, deriva da zigging bee la danza delle api domestiche, metodo attraverso il quale vengono comunicati i dati essenziali per la sopravvivenza della colonia.
4.1 I protocolli
ZigBee è un insieme di protocolli di comunicazione basato sullo Standard 802.15.4. Opera alle frequenze delle Bande ISM (Industrial, Scienti c and Medical) assegnate: a) 868 MHz (Europa), b) 915 MHz (Nord America) e 2,4 GHz (in tutto il mondo). La tipologia di rete di nodi ZigBee rientra nelle low bitrate Personal Area Network (PAN) a short range.
ZigBee fu concepito nel 1998 per soddisfare i bisogni di piccole reti auto-con guranti ed economiche. Nel 2003 fu rilasciato dai gruppi IEEE 802 collegati alle PAN, lo standard 802.15.4 che de nisce i livelli inferiori (OSI) di ZigBee, ovvero un'infrastruttura di comunicazione ed una logica di controllo semplice e leggera dove i dispositivi sono in grado di comunicare tra loro in maniera autonoma.
Lo standard Zig Bee de nisce un meccanismo di comunicazione Wireless operante su piccole distanze e con una modesta banda passante: 250 kbps su un raggio teorico di copertura tra i trenta metri in ambienti indoor e i cento metri in situazioni outdoor.
ZigBee opera come rete a basso bitrate e a consumo limitato, e può essere impiegato nei collegamenti di dispositivi quali: interruttori della luce, serrature, sensori ambientali o allarmi a cui fornire la capacità di integrarsi in una rete domotica.
Questi dispositivi non richiedono alte velocità di comunicazione, hanno poche informazioni da scambiare al secondo, hanno bisogno di consumare poca energia e consentire ai terminali, con pile incorporate, di funzionare per lungo tempo (mesi o anni) vista la generica insostituibilità delle batterie stesse.
Sfruttando la tecnologia ZigBee è possibile monitorare e controllare lo stato dei sistemi in maniera distribuita in ambiente domestico, commerciale o indus-triale.
4.2 Elementi essenziali per la de nizione di una rete
Zig-Bee.
ZigBee è un'organizzazione gerarchica. Lo standard de nisce tre livelli di fun-zioni logiche degli apparati:
4.2.1 ZigBee Coordinator
ZC E' l'elemento più complesso della rete ZigBee e l'unico essenziale. Opera come nodo radice di coordinamento della rete ad albero, inizializza la rete, gestisce i vari nodi, opera la raccolta dati ed è in grado di operare come bridge verso altre reti. Per ogni rete viene designato un Coordinator che contiene le informazioni sulla rete e le chiavi di sicurezza. Senza il nodo Coordinator non può essere formata una rete ZigBee.
4.2.2 ZigBee Router
ZR E' un elemento opzionale della rete, viene de nito Full Function De-vice (FFD), gestisce il routing delle comunicazioni di rete attraverso le rela-tive tabelle, può allocare nuovi dispositivi nella rete, raccoglie le informazioni ricevute dai nodi secondari e le invia al nodo centrale.
4.2.3 ZigBee End Device
ZED E' un elemento opzionale della rete, viene de nito Reduced Function De-vice (RFID), genera informazioni e le invia al Coordinator o al Router, non può operare come intermediario per altri dispositivi. E' l'elemento più semplice ed economico, solitamente destinato ad oggetti quali interruttori TV, radio, lam-pade, elettrodomestici, ecc. Si possono realizzare reti a topologia Mesh, in cui sottoreti a stella (un sensore ZR/FFD che coordina diversi sensori ZED/RFD) si interfacciano mediante collegamenti diretti fra FFD (Fig. 1).
Nelle reti Mesh gli apparati possono divenire essi stessi nodi di smistamento delle informazioni, con la conseguente estensione della portata della rete, au-mento dell'a dabilità e soprattutto della resistenza a interferenze e guasti di apparati, grazie alla possibilità di modi care i percorsi della comunicazione a seconda delle condizioni al contorno.
5 Qualche considerazione iniziale
5.1 Premessa
Questa non vuole essere un'analisi precisa e dettagliata di come i vari compo-nenti emettono, ricevono o interpretano le intensità dei segnali.Si usa spesso nell'informatica il concetto di black-box, questa viene ad hoc si ha in ingresso un segnale in uscita una distanza, come per ora poco importa.
5.2 Una ipotesi iniziale
Si consideri un sensore: probabilmente nel misurare la potenza del segnale, il ricevente si trova teoricamente sulla super cie di una semisfera: l' ipotesi è che il segnale abbia la stessa potenza per una uguale distanza poniamo idealmente che il sensore sia a so tto, a pavimento o a parete allora la sfera si riduce ad una semisfera che cade all'interno dell'ambiente. Si ponga poi che il ricevente sia posto ad una determinata altezza. Si vorrebbe così trattare il caso più semplice:
sensori a so tto e ricevitore ad una certa altezza.
Intuitivamente in teoria il sensore può essere visto come sulla circonferenza di base di un cono all'interno della semisfera. In particolare il sensore sta nella circonferenza creata dal cono con la sfera.
Un cono è un solido in rotazione: questo è dato dalla rotazione di un triangolo rettangolo. Quest'ultimo ha come ipotenusa quella che noi de niamo distanza, come cateto adiacente, quello utile a determinare il raggio della cella in cui è contenuto.
Figure 5: rappresantazione sfera cono Per trovare questo raggio usiamo direttamente Pitagora.
R =√distanza2− Altezza2.
De nito il raggio che delimita teoricamente la cella, si possono analizzare analizzare le varie casistiche, inutile dire che per semplicità non è stato consid-erato nessun tipo di errore.
Si sta solo tentando di mettere in piedi un ragionamento iniziale che regga . Una ulteriore sempli cazione è stata inserita sul concetto di distanza che, come sappiamo nasce dalla misura di una intensità di un segnale e maggiore causa di errori. Analizziamo perciò delle situazioni tipo create all'uopo.
5.3 Un riferimento
E' chiaro che avendo un rifermento ci si deve basare sulla distanza suggerita dall'unico sensore.
Questa viene considerata come ipotesi zero; in questo caso è molto semplice determinare la distanza:
Nota la posizione del sensore questa per de nizione, il ricevente ottiene la sua distanza dal sensore, come si vede la distanza ( ssata l'altezza del ricevente) è lungo la circonferenza. La posizione, con le dovute correzioni, sarà intuitiva-mente lungo una circonferenza attorno al sensore che ha un Raggio calcolato come sopra. Con questo metodo ovviamente non ottengo una posizione precisa ma una circonferenza, nella quale è presente il ricevitore, non si può in nessun modo stabilire dove. Si prende perciò l'area del cerchio e si dice che sta lì.
Figure 6: Distanza rilevata con un solo sensore con altezza ssata
5.4 Più riferimenti
Con più riferimenti la cosa si complica: è chiaro che ogni sensore, in prossimità del ricevente, invierà la distanza; questo creerà un problema valutare la posizione il più possibile esatta con più letture.
Partiamo dal caso più semplice 2 sensori:
Con 2 sensori si può teoricamente determinare uno o più punti così intuiti-vamente la vediamo come intersezione tra le 2 circonferenze , in questo caso 2 punti ma in prima approssimazione anche l' area tra esse compresa.
E' chiaro che con più sensori si avranno più intersezioni e quindi più punti possibili. Per fare la famosa triangolazione sono necessari 3 sensori per 2 dimen-sioni ovvero avremo l'intersezione di tre circonferenze su un punto e quest'ultimo rappresenta la posizione.
Questo rappresenta la condizione ottimale: Se per ogni ambiente si riuscisse a triangolare si avrebbe la migliore situazione possibile. Ricordando che se non viene ssata la famosa altezza per 3 dimensioni c'è bisogno di 4 punti . . . Comunque la si metta si tratta sempre e comunque di risolvere un sistema di equazioni ognuna rappresentante una circonferenza. E' altrettanto chiaro che la soluzione del sistema rappresenta i punti di intersezione. C'è anche il caso reale che le due circonferenze non si intersechino.
Figure 7: Più riferimenti con l'altezza ssata
ricordando che parliamo di misure, può esserci un muro che attenua il seg-nale, e quindi risultare più distante . . .
A questo punto la circonferenza con raggio maggiore è da scartare poiché non quadra con le altre misure più vicine, saranno quelle le intersezioni da considerare. Fino ad ora però si è parlato di intersezioni e di punti, in realtà si sa che questi sono solo concetti, un po' come quello di impostare l'altezza del ricevente, si dovranno perciò allargare un po' le maglie.
5.5 Le aree
Riepilogando ciò che è stato ipotizzato si possono tenere delle aree non dei punti. Cominciando dall'altezza del ricevitore, non sarà sempre possibile darla al sistema si potrà ssare in modo arbitrario quest'ultima, ad es a metà tra so tto e pavimento, questa scelta è chiaro che non restituisce più punti ma aree e che probabilmente le estende alla parte di sfera contenuta sotto al cono.
Figure 8: Situazione con l'altezza ssata a metà di quella della stanza Il problema, adesso, diventa come descrivere un'area.
Se si usassero dei rettangoli basterebbero le coordinate dei vertici, con le circonferenze centro e raggio. Si scelgono i rettangoli. Probabilmente qualcuno si chiederà perché dopo sfere, coni e cerchi, proprio rettangoli: se si trattasse di risolvere un riferimento, probabilmente il fatto di tenere la circonferenza, magari aumentando un po' il raggio . . . e quando ho una intersezione il sistema impazzisce per trovare circonferenze, se esistono, passanti per tutti i punti di intersezione? No molto più semplice: si prendono le coordinate dei punti di intersezione si trovanoo min x e min y, max x e max y e si ottengono le coordinate del rettangolo. Ma se c'è una sola circonferenza?
Si prendono le coordinate del centro aggiungendo e tolgliendo il raggio a x e a y si trova il quadrato circoscritto corrispondente.
A questo punto si è ottenuto un sistema abbastanza approssimativo per trovare delle aree dove può essere presente il ricevitore.
Figure 9: Quadrato circoscritto
Figure 10: Intersezioni con 2 circonferenze e tre circonferenze
nel caso di tre circonferenze secondo la de nizione si ottiene un punto in realtà con la tolleranza sulle misure si ottiene.
5.6 Propagazione teorica del segnale
RSSI sta per Received Signal Strenght Indicator.
Il valore di RSSI ri ette l'intensità del segnale ricevuto in un determinato istante. L'intensità del segnale ricevuto è funzione della potenza trasmessa e della distanza tra il trasmettitore e il ricevitore.
La forza del segnale ricevuto diminuisce con l'aumentare della distanza con la seguente:
RSSI = − (10 ∗ n ∗ log10d − A)
n è una costante di propagazione del segnale, anche chiamato esponente di propagazione;
d è la distanza dal trasmettitore;
A l'intensità del segnale ricevuto alla distanza di un metro.
Ovviamente la sopra menzionata formula è solo teorica. Vi sono svariati prob-lemi nel mondo reale che rendono inesatti i valori di quest'ultima. Ci sono due semplici modi per ltrare i valori RSSI il primo è la media il secondo i ltri di feedback. La media è il più semplice, ma richiede l'invio di più pacchetti dati.
I ltri di feedback utilizzano solo una piccola parte dei valori RSSI più recenti. Ricapitolando il valore medio viene calcolato dalla seguente:
RSSI = 1 n n X i=1 RSSIi
L'altro ltro invece:
RSSIn= a ∗ RSSIn+ (1 − a) + RSSIn−1
con la costante a che di solito è 0.75 o superiore.
Con questo tipo di approccio grosse dierenze nei valori di RSSI possono essere smussate, quindi non è consigliabile se ciò che viene monitorato si muove tra un calcolo e l'altro.
5.7 Considerazioni
Fatta questa breve panoramica si tenta di usare ciò che si è imparato: RSSI = − (10 ∗ n ∗ log10d ∗ A)
Se in quella stanza vi sono almeno tre nodi di riferimento si procede con la stima delle coordinate.
Gli RSSI vengono convertiti in distanze con la seguente formula:
d = 10
A−RSSI 10n
Tutte le distanze più lunghe di quella massima misurabile in quella stanza ven-gono scartate.
5.8 Un po' di conti
In un sistema di assi cartesiani Oxy, la circonferenza di centro(α, β) e raggio r è il luogo dei punti caratterizzati dall'equazione:
Figure 11: Circonferenza centro (α, β) e raggio r
(x − α)2+ (y − β)2= r2, Sviluppando i quadrati si ottiene:
x2− 2αx + α2+ y2− 2βy + y2= r2
x2− 2αx + α2+ y2− 2βy + y2− r2= 0
questa può essere riscritta in forma canonica come: x2+ y2+ ax + by + c = 0 con
a = −2α b = −2β
c = α2+ β2− r2
5.9 In caso di due circonferenze
1. x2+ y2+ a
1x + b1y + c1= 0
2. x2+ y2+ a
2x + b2y + c2= 0
Considerando che 1. e 2. rappresentano un sistema di due equazioni si può sottrarre la seconda dalla prima:
x2+ y2+ a1x + b1y + c1= 0
In questo modo si è ottenuto l'equazione della retta passante per i punti di intersezione tra le 2 circonferenze ovviamente se questi ci sono.
Figure 12: Retta passante per l'intersezione di due circonferenze Risolvendo per sostituzione:
y = [−(a1− a2)x − c1+ c2]/(b1− b2)
che sostituita nella 1 x2+ [(a2− a1)x − c1+ c2]2 (b1− b2)2 + a1x + b1 [(a2− a1)x − c1+ c2] (b1− b2) + c1= 0 ponendo: a12= a2− a1 b12= b1− b2 c12= c2− c1 Si ottiene: x2+(a12x + c12) 2 b2 12 + a1x + b1 a12x + c12 b12 + c1= 0 x2+a 2 12x 2+ 2a 12xc12+ c212 b2 12 + a1x + b1 a12x + c12 b12 + c1= 0 Denominatore comune: x2(b2 12+ a212) + x(2a12c12+ a1b212+ a12b1b12) + c212+ b1c12b12+ c1b212= 0
malgrado la ricchezza dei coe cienti questa è una banale equazione di sec-ondo grado che darà origine a due radici, se queste esistono.
Ponendo: a = b2
12+ a212
b = 2a12c12+ a1b212+ a12b1b12
c = c212+ b1c12b12+ c1b212
E' anche possibile che coincidano in caso di tangenza delle due circonferenze. ax2+ bx + c = 0
x1,2=
−b ±√b2− 4ac
2a basta sostituire.
5.9.1 Facciamo un esempio
Figure 13: Esempio con 2 circonferenze (x − α)2+ (y − β)2= r2
x2− 2αx + α2+ y2− 2βy + β2= r2
x2− 2αx + y2− 2βy + α2+ β2− r2= 0
1. (x − 60)2+ (y − 70)2= 502
possiamo riscriverla in forma canonica
x2− 120x + y2− 140y + 602+ 702− 502 = 0 x2− 120x + y2− 140y + 6000 = 0 con a1= −2α = 120; b1= −2β = 140; c1 = α2+ β2− r2= 6000; x2+ y2+ a 1x + b1y + c1= 0 (x − 130)2+ (y − 100)2= 502 x2− 260x + y2− 200y + 169000 + 100000 − 2500 = 0 x2− 260x + y2− 200y + 266500 = 0 con : a1 = −2α = 260; b1 = −2β = 200;
c1 = α2+ β2=r2= 266500; 1. x2− 120x + y2− 140y + 6000 = 0 a1= −120; b1= −140; c1= 6000; 2. x2− 260x + y2− 200y + 24400 = 0 x2+ y2+ a 2x + b2y + c2 = 0 a2= −260; b2= −200; c2= 24400; 1-2 ->2 (a1− a2)x + (b1− b2)y + c1− c2= 0 140x + 60y − 24400 = 0 y = −(a1− a2)x − c1+ c2 b1− b2 y = 140x + 18400 60 x2+[(a2− a1) x − c1+ c2] 2 (b1 − b2)2 + a1x + b1 (a2− a1) x − c1+ c2 (b1− b2) + c1= 0 poniamo : a12= a2− a1 a12= −140 b12= b1− b2 b12= 60 c12= c2− c1 c12= 18400 x2+ (a12x + c12) 2 b2 12 + a1x + b1 a12x + c12 b12 + c1= 0 a = b2 12+ a212 a = 23200 b = 2a12c12+ a1b212+ b1a12b12 b = −4408000 c = c2 12+ b1c12b12+ c1b212 c = 205600000
delta = b2− 4ac = 3.5078e + 11
deltasqr =√delta = 5.9227e + 05 x1= (−b + deltasqr)/2a x1= 107.76
x2= (−b − deltasqr)/2a x2= 82.236
Come si può controllare dalla gura le misure sono corrette
Ciò signi ca che quest'ultima è una possibile parametrizzazione del prob-lema.
5.9.2 In caso di tree circonferenze
In questo caso si puo usare il metodo usato sopra intersecando le circonferenze due a due.
La cosa non solo è formalmente corretta ma permette di trovare delle ottime soluzioni con qualunque numero di circonferenze.
Il metodo che segue sarà interessante da usare come veri ca ma avrà uno scopo solo di taratura:
pensare che trovare un punto partendo da un segnale è pura utopia. Caso teorico di tree circonferenze:
Con queste premesse si puo riscrivere:
Nel caso di intersezione tra due o tre circonferenze si scrive il seguente sis-tema: 1. x2+ y2+ a 1x + b1y + c1= 0 2. x2+ y2+ a 2x + b2y + c2= 0 3. x2+ y2+ a 3x + b3y + c3= 0 Analogamente a prima: 1.-2. ->2. 1.-3. ->3. 1. x2+ y2+ a 1x + b1y + c1= 0 2. (a1− a2)x + (b1− b2)y + c1− c2= 0 3. (a1− a3)x + (b1− b3)y + c1− c3= 0
Le 2. e 3. rappresentano le equazioni delle rette passanti per le rispettive circonferenze.
Se volessimo rappresentarlo per i computer dovremo usare matrici e vettori. a1− a2 b1− b2 a1− a3 b1− b3 ∗ x y = c1− c2 c1− c3
questo è il sistema di equazioni che rappresenta le 2 rette ora simbolicamente è come fosse scritto:
¯ x = x y ¯ b = c1− c2 c1− c3
A è la matrice dei coe cienti per cui : A¯x = ¯b
per risolverlo bisogna trovare la matrice inversa A−1:
Ponendo: u = a1− a2
v = b1− b2
w = a1− a3
z = b1− b3
trovata la matrice inversa A-1 A−1= z −v −w u ∗ 1 zu − wv
Dopo queste semplici ri essioni ci si rende conto che per un approccio di questo tipo, si sono dovute inserire varie sempli cazioni e, pur valido da un punto di vista teorico, non può rappresentare una soluzione reale alle problematiche:
nei modelli che seguiranno verranno introdotte volta per volta varie soluzioni e proprio partendo dal concetto di distanze che verrà introdotto LLE.
Part II
Le soluzioni
6 LLE Linear Local Embedding
Algoritmo di riduzione dimensionale usato per escludere letture non attendibili. Questa sezione serve a capire il perché della scelta di LLE.
Il problema con i sensori è quello che, le varie rilevazioni possono essere non attendibili; considerando i valori riferiti ai più vicini, come più attendibili, si è scelto un algoritmo che conserva i vicini.
E' chiaro che questo tipo di considerazione non spiega l'algoritmo che verrà illustrato poi, l'importante sarà perciò dell'idea: vedendo perciò l'algoritmo come una black box in cui entrano dei dati di uno spazio di dimensione molto grande e ne escono rimaneggiati in una dimensione più piccola.
Figure 14: Schema dell'uso di LLE per la riduzione dimensionale: le letture delle distanze, da parte dei sensori, vengono considerate dimensioni a se stanti; l'algoritmo proietterà poi lo spazio in dimensione 3.
Con queste premesse, l'intuizione porta a pensare che, fornendo a LLE una serie ordinata di dati, questo restituirà in uscita la serie di dati trasformata ordinata.
Ora sono stati provati due modelli per usare LLE, con apprendimento e senza.
6.1 Modello con apprendimento
Quando si pensa ad un modello con apprendimento, si passa all'algoritmo una serie posizioni note (training set), si vede dove vengono mappate, poi si inserisce un punto non conosciuto vicino ai dati e con ciò che conosce l'algoritmo, se tutto funziona, individua quel punto.
Viene creata una griglia bidimensionale, vengono determinate le posizioni più centrali per la disposizione dei sensori ssi, si fa il training spostando il sensore mobile in ogni punto della griglia campionandone la misura delle distanze da tutti i sensori ssi, successivamente si dispone il sensore mobile in un punto qualunque all'interno della griglia.
2
Figure 15: LLE con apprendimento: rappesentazione griglia sensore mobile e sensori ssi a so tto.
Per entrare un po' più sul tecnico: se si produce una griglia e si calcolano le distanze di ogni punto della griglia dai sensori ssi, si ottiene così una matrice MxN su cui si applica LLE, che restituirà una matrice QxN .
Figure 16: Rappresentazione delle distanze in un piano 3d
2griglia bidimensionale: per questa si intende una successione ordinata di punti 3d che
Se poi si suppone di avere dei sensori ssi posti in modo abbastanza regolare nella stanza (è stato usato l'algoritmo EM per centrare i sensori rispetto ai punti della griglia), si calcolano le distanze tra ogni punto della griglia e i sensori ssi, ottenendo uno spazio di rappresentazione di ogni punto attraverso le distanze.
Questo sarà lo spazio da dare in pasto ad LLE che lo riproietterà in 3d. Come si può immaginare non c'è perdita di informazione poiché si passa da uno spazio 3d ad un'altro.
Ma allora a cosa è servito tutto ciò? A sbarazzarsi delle distanze non a dabili.
Ora il punto sconosciuto è stato inserito come ultimo punto e quindi sarà ultimo anche nello spazio di arrivo.
Vengono ora trovati i punti vicini in questo spazio, questi avranno la stessa posizione nella matrice anche nello spazio di partenza.
Con questa considerazione, ora si sa quali sono i vicini del punto mobile, sia nello spazio di partenza, che nello spazio di arrivo.
Figure 17: Vicini del punto mobile nello spazio di arrivo tridimensionale Riepilogando, si trovano quattro vicini nello spazio di arrivo (semplicemente con la distanza euclidea) si determinano, in base alla posizione, i quattro vicini corrispondenti nello spazio di partenza.
Al termine di questo procedimento, dello spazio di partenza si conoscono le posizioni (griglia ) risolvendo il sistema si trova la posizione del punto di interesse.
6.2 Senza Apprendimento
E' chiaro che quanto fatto prima, riesce in qualche modo a risolvere il prob-lema, si potrebbe però tentare di sempli care la cose togliendo l'apprendimento, ovvero misurando direttamente le distanze tra i sensori ssi e il punto sconosci-uto, darle ad LLE da riproiattere: tutto come prima.
Figure 19: LLE senza apprendimento
Come si vede chiaramente non c'è la griglia, questa è stata usata solo per determinare la posizione 2d dei sensori ssi.
Anche qui si trovano i vicini nello spazio di arrivo:
Ora i vicini nello spazio di arrivo saranno le proiezioni dei sensori ssi più vicini.
Per determinare la posizione del punto nello spazio di partenza non si può più fare fede sui vicini, perché, essendo lontani, viene a mancare la precisione; bisogna quindi a darsi ad un altro metodo. Si trovano quindi i vicini nello spazio di partenza:
Figure 20: Vicini nello spazio di arrivo senza apprendimento
Figure 21: Vicini nello spazio di partenza senza apprendimento
Quello che si sa di quest'ultimi, sono le rispettive distanze dal punto, con queste informazioni abbiamo tre sfere e la loro intersezione teorica è il punto.
La cosa più conveniente è di usare un metodo numerico per trovare un qualcosa che si avvicina a quel punto.
Il metodo del gradiente discendente è quello che meglio si presta all'uopo: questo minimizza la somma dei quadrati delle equazioni delle sfere.
Questo metodo si avvicina sempre più alla soluzione, con una precisione stabilita, seguendo di volta in volta la direzione del gradiente ma con il verso opposto.
Figure 22: Steepest variazione della posizione
come si vede il metodo cambia la posiziobe di X che oscilla in modo sempre più stretto no a convergere.
Di conseguenza la funzione da minimizzare oscilla sempre meno no a con-vergere.
Figure 23: Steepest variazione della f
Come si può intuire la convergenza della funzione coincide al ritrovamento del punto X.
I prossimi passi saranno: togliere le distanze e lavorare direttamente con RSSI.
Introdurre tutta una serie di perturbazioni per provare a vedere quanto regge l'algoritmo.
7 Inserimento RSSI
In questa sezione verrà inserito l'RSSI, questo nella modellazione viene calcolato a partire dalle distanze.
7.1 Senza uso di impostazioni
L'obiettivo, è quello di eliminare il setting da parte dell'utente.
Dato come punto di partenza l'algoritmo senza apprendimento, si cerca ora di modi care tale algoritmo per ricavare ciò che serve, dalla semplice analisi delle RSSI.
Come sempre, almeno inizialmente, si considera una situazione ideale: questo signi cherà considerare la N dell'ambiente costante.
La situazione è la seguente
Figure 24: Ambiente di misura senza setting
Le linee tratteggiate fanno capo ai sensori ssi di cui è nota la posizione. Ora se il sensore mobile invia un segnale ai sensori ssi è evidente che il parametro A (abbattimento potenza del segnale a 1 m) è lo stesso per tutti perché è l'unico.
Ribadendo che RSSI rilevata dell'iesimo sensore Ri è:
Ri= −(10 ∗ n ∗ log10(di) + A) (1)
Se si normalizza sia l'espressione che le letture, si ottiene che, la convergenza dell'espressione normalizzata, va verso quella normalizzata delle letture.
Posta la seguente:
yi = log10di (2)
Con un po' di conto si ottiene che RSSI normalizzato per ogni sensore, è dato da: ri= yi− 1 n P iyi s 1 n P i yi− 1 n P jyj (3)
questo va rarontato con la lettura normalizzata che verrà data da ogni sensore sso.
Chiamando ora questa lettura ri si ottiene immediatamente l'energia da
minimizzare.
Per comodità si ponga:
y = 1 n
X
i
yi
Si de nisce l'energia come:
E =X i yi− yi r 1 n P i(yi− y) − ri 2 (4)
E' abbastanza intuitivo che, nel momento in cui si trovano gli yi giusti,
l'energia sarà in teoria zero.
Tutto sommato si aerma solo l'esattezza della (eq.3). In realtà poi ci si ac-contenterà di trovare una soluzione approssimata usando il metodo del gradiente discendente.
Si determina perciò il gradiente in questione: Si ponga ora: Y − Y = OY con O : O = I − 1 n11 T
Le cose in gioco sono tutte abbastanza chiare ma poco costa speci carle: I è la matrice Identità, matrice quadrata nxn con tutti uni nella diagonale principale, 1 è un vettore orizzontale di n uni .
E =1 2 OY 1 √ nkOY k − r (5)
Si trova così il gradiente di E:
Questo analogamente alla derivata di f2 d (f )2
= 2f d (f )sarà: ∇YE = * OY 1 √ nkOY k − r ∇Y √ n OY kOY k + (6) ora d f g =d (f ) ∗ g − f ∗ d (g) g2
Considerando le singole derivate parziali
∂E ∂yi = * √ n OY kOY k− r √ nOeikOY k − OY ∂ ∂yi kOY k kOY k2 + (7) Si mette in evidenza un trucco:
kOY k2=OY OY = YTOTOY Sviluppando il prodotto scalare
∂E ∂yi = n YTOTOe ikOY k kOY k2kOY k − YTOTOY ∂ ∂yi kOY k kOY k2kOY k − rTOeikOY k kOY k2kOY k− rTOY ∂ ∂yi kOY k kOY k2kOY k usando il trucco: ∂E ∂yi = n YTOTOe i YTOTOY − YTOTOY ∂ ∂yi kOY k YTOTOY kOY k − rTOei YTOTOY − rTOY ∂ ∂yi kOY k YTOTOY kOY k Ora se si sviluppa: ∂ ∂yi kOY k = ∂ ∂yi √ YTOTOY =1 2 2YTOTOe i √ YTOTOY = YTOTOe i kOY k (8) Sostituendo: ∂E ∂yi = n kOY k2 Y T OTOei− YTOTOei− rTOei− rTOY YTOTOe i kOY k2 !
∂E ∂yi = n kOY k2 −r TOe i− rTOY YTOTOe i kOY k2 ! ∇YE = n kOY k2 r TOY OTOY kOY k2 − O Tr ! (9) E questo è il gradiente che si andrà a passare a all'algoritmo di steepest (steepestGen).
Con questo sistema si è determinato l'Y che minimizza l'energia E. A questo punto non resta che ricordare chi è Y: è un vettore composto da n yi ognuna delle quali è:
yi = log10di
da qui facilmente: di= 10yi
Il problema viene ricondotto a quello analizzato precedentemente:
avendo una serie di distanze, si ordinano, si prendono le tre più piccole e, applicando steepest, si trova il punto che, come si vede in gura 1 è molto vicino all' origine teorica.
Come si vorrebbe proseguire la modellazione?
Per ora sono stati svolti dei conti su situazioni ideali, ovvero senza alcun tipo di perturbazione, quindi tutto ciò assomiglia ad una prova del nove.
Il prossimo passo sarà quello di perturbare l'ambiente vedendo di quanto sbaglia.
Poi trovare il modo, monitorando l'ambiente, di stabilire degli N per appli-care la soluzione.
8 Determinazione dell'ambiente
Analisi del problema:
ci sono dei nodi ssi di cui si conosce la posizione, questi si possono usare per monitorare l'ambiente.
L'equazione di base per il calcolo dell'RSSI: RSSI = −10 ∗ N ∗ log d − A
ora si sa che N è qualcosa che dipende dall'ambiente e A dalla potenza di trasmissione del sensore;
si può quindi aermare che con n nodi, si avranno n A diversi, per quanto riguarda N dipende dalle coppie di nodi:
N umN = n2
mentre le distanze tra i punti sono N umD = n2 ∗ 2
Per risolvere un sistema, come è noto bisogna avere almeno tante equazioni quante sono le incognite.
In questo caso vi sarà: una equazione per ogni distanza ordinata, ovvero dij 6= djicome equazione perchè Ai 6= Aj è chiaro invece che come valore le due
distanze sono identiche essendo semplicemente distanze tra 2 punti.
8.1 Perturbazione dell'ambiente
Allo scopo di simulare degli ipotetici ostacoli all'interno dell'ambiente, sono stati introdotti degli errori casuali per indebolire l'RSSI3.
Nel fare questo sono state usate più modalità; in particolare si sono usati 2 tipi di massimi pre ssati:
un massimo percentuale rispetto al valore medio; un massimo percentuale rispetto alla singola misura.
La seconda soluzione sembra la più adatta ad ottenere delle soluzioni più razion-ali.
In questo contesto si è proceduto sfruttando le misure dei sensori ssi (quelle perturbate) per determinare l'ambiente.
Come si vede dalle gure sono calcolati gli N tra i sensori ssi e gli A degli stessi.
Ora si vedono i passi che ne hanno portato alla determinazione.
3Risulta evidente che introdurre errori casuali possa compromettere la soluzione nella
de-terminazione della posizione del sensore mobile,
è comunque utile per quanto riguarda la determinazione di N ed A, perciò va presa come testing di questa parte del problema.
Figure 25: N tra i sensori ssi N12 N13... N1n N21N23...
N2n...Nmm+1Nmm+2...Nmn
8.2 Minimizzare l'energia
L' obiettivo ora è quello di minimizzare E:
Nota: N{i,j},d{i,j}questa notazione è dovuta al fatto che{i, j} è l'insieme di
i e j cioè non dipende dall'ordine.
Per brevità rij corrisponderà a RSSIij.
E =1 2 X i X j
rij+ 10N{i,j}log d{i,j}+ Ai
2
+ rji+ 10N{j,i}log d{j,i}+ Aj
2
L'un mezzo è dovuto al fatto che si somma due volte la stessa quantità. Ora, minimizzare una quantità signi ca imporre alle derivate di questa quan-tità di essere 0.
Le derivate parziali:
∂E ∂N{i,j}
= 10 log d{i,j} rij+ rji+ 10N{i,j}log d{i,j}+ 10N{j,i}log d{j,i}+ Ai+ Aj
∂E ∂Ai
=X
j
rij+ 10N{i,j}log d{i,j}+ Ai
Ora ∀ {i, j} δE δN{i,j} = 0 ∀i δE δAi = 0
Questo rappresenta un sistema lineare in N{i,j}e Ai
Posizione: Se i=j si pone tutto a zero.
Si scrivono ora le equazioni che costituiranno il sistema:
come si può osservare la scrittura è stata già sempli cata, sia per quanto riguarda le distanze d sia per le N :
dij = djie Nij = Nji
Si deve ricordare che dei vari RSSI sono rilevati, quindi noti, le distanze, essendo note le posizioni sono facilmente determinabili.
E12= r12+ 10N{1,2}log d{1,2}+ A1 2 + r21+ 10N{2,1}log d{2,1}+ A2 2 ∂E ∂N{1,2}
= 10 log d{1,2} r12+ r21+ 10N{1,2}log d{1,2}+ 10N{2,1}log d{2,1}+ A1+ A2
∂E ∂A1 = r12+ 10N{1,2}log d{1,2}+ A1 ∂E ∂A2 = r21+ 10N{2,1}log d{2,1}+ A2
8.3 Qualche considerazione
∂E ∂N{i,j}
= 10 log d{i,j} rij+ rji+ 10N{i,j}log d{i,j}+ 10N{j,i}log d{j,i}+ Ai+ Aj
in virtù del fatto che N{i,j}= N{j,i}e d{i,j}= d{j,i}si ottiene che:
∂E
∂N{i,j} = 10 log d{i,j} rij+ rji+ 20N{i,j}log d{i,j}+ Ai+ Aj
∂E ∂Ai
=X
j
rij+ 10N{i,j}log d{i,j}+ Ai
A quante equazioni si arriva?
Premesso che non ha senso considerare N{i,i}si può considerare che per ogni
iabbiamo j = n − 1.
Considerando poi le simmetrie già discusse in precedenza, per d e N si ha: rispetto a N n (n − 1)
2 equazioni linearmente indipendenti; mentre per A ne avrà n
in tutto il sistema consterà di: n (n − 1)
2 + n =
n (n + 1)
2 equazioni.
E' chiaro che essendo il numero di equazioni, dato dalla giustapposizione di tutte le equazioni riguardanti le variabili senza ripetizioni, è giusto il numero che consente di risolvere il sistema.
8.4 Cosa si fa degli N trovati
Una volta trovati gli N si confronteranno i risultati allo scopo di riprodurre lo spazio, per fare questo ci sarà bisogno di pesare questi valori con un criterio di prossimità, Sono stati usati 2 algoritmi per interpolare i valori.
8.5 Radial basis function
Una RBF è una funzione a valori reali, i cui valori dipendono solodalla distanza dall'origine così che
φ (x) = φ (kxk)
o in alternativa dalla distanza di alcuni punti c φ (x, c) = φ (kx − ck)
Ogni funzione ϕche soddisfala proprietà φ (x) = φ (kxk) è una funzione ra-diale.
La norma è usualmente la disttanza euclidea sebbene altre funzioni distanza siano possibili.
Tipi di RBF
Gaussian φ (r) = e−(r)2 Multiquadratic φ (r) =q1 + (r)2 Inverse Quadratic φ (r) = 1 1 + (r)2 Inverse Multiquadratic φ (r) =q 1 1 + (r)2 Polymorphic spline φ (r) = rk k = 1, 3, 5, ... φ (r) = rkln (r) k = 2, 4, 6, ...
Thin plate spline φ (r) = r2ln (r)
8.5.1 Approssimazione
Le Radial bias function sono spesso usate per fare funzioni di approssimazione del tipo:
y (x) =Pn
i=1 = ωiφ (kx − xik)
dove l'approssimazione funzione y (x) è rappresentata come una somma di N radial bias function, ciascuna associata ad un diverso centro xi, e ponderata
da un coe ciente wi appropriato. La connessione wi pesi può essere stimata
utilizzando i metodi di matrice lineare minimi quadrati, perché la funzione avvic-inamento è lineare nei pesi.
8.6 Medie Pesate
Un altro interpolatore, possibile è quello di produrre delle medie pesate rispetto alle distanze:
Dati dei valori in n punti v1, v2, .., vn, l'interpolazione in un punto i viene
ottenuta vi= Pn j=1 1 dij vj Pn j=1 1 dij con i diverso da j.
il vantaggio di questo sistema si evince immediatamente:
per ciò che riguarda il calcolo della N che si ricorda essere molto legata al fattore ambientale è chiaro che la vicinanza sarà un fattore fondamentale per la somiglianza nel valore, di qua l'immediata appropriatezza de questo semplice interpolatore.
9 La chiusura del cerchio
Allo scopo di ottenere dei risultati più precisi gli algoritmi che seguono verranno applicati su un disturbo generato come rumore bianco.
Per fare questo , viene dato uno schema che genera una variabile gaussiana casuale distribuita su N(0, 1) usando una distribuzione uniforme su [0, 1]; questo schema è chiamato Box Muller method con media 0 e varianza 1.
9.1 Come si procede usando Thin plate spline
Nella precedente sezione , è stato monitorato l'ambiente:
sono cioè state trovate le A dei sensori ssi, sono state stimate le N tra i vari sensori ssi.
La posizione esatta del sensore mobile è incognita, si può però stimare la N in ogni posizione che man mano verrà calcolata.
Usando un po' di matematica:
Per ogni sensore sso conoscendone la A:
Rix= −10 ∗ Nix∗ log10(dix) − Ai (10)
questa rappresenta in modo compatto il segnale che viene ricevuto dal sen-sore mobile x rispetto al sensen-sore sso i.
A questo punto si ricorda che per thin plate spline Nix=P n j6=i h Cjk ˙x − Pjk 2 ∗ log (k ˙x − Pjk) i è altrettanto semplice capire che x è il vettore di coordinate del punto mobile
e Pjle coordinate del punto sso.
Con queste considerazioni si ottiene che la norma 2k ˙x − Pjkin realtà è:
k ˙x − Pjk = q x − xpj 2 + y − ypj 2 + z − zpj 2 Analogamente per quanto concerne dix:
dix= q (x − xpi) 2 + (y − ypi) 2 + (z − zpi) 2
Provando a fare un po' di conto: Nix=P n j6=i Cj x − xpj 2 + y − ypj 2 + z − zpj 2 ∗ 1 2log x − xpj 2 + y − ypj 2 + z − zpj 2 L'ultima cosa che resta da considerare è Rixè il segnale che il sensore mobile
rileva dal sensore i.
A questo punto bisogna applicare uno steepest su tre variabili x, y e z del punto mobile come uniche incognite.
Non resta che raggruppare ciò che è stato detto e calcolare funzione e gradi-ente.
9.1.1 Il sistema
Per trovare le coordinate si può usare un sistema di equazioni non lineari: −10 ∗ N1x∗ log10(d1x) − A1− R1x= 0 −10 ∗ N2x∗ log10(d2x) − A2− R2x= 0 . . . −10 ∗ Nix∗ log10(dix) − Ai− Rix= 0 . . . −10 ∗ Nnx∗ log10(dnx) − An− Rnx= 0 (11) ora la funzione G( ˙x) = −10 ∗ N1x∗ log10(d1x) − A1− R1x −10 ∗ N2x∗ log10(d2x) − A2− R2x · · · −10 ∗ Nix∗ log10(dix) − Ai− Rix · · · −10 ∗ Nnx∗ log10(dnx) − An− Rnx dove ˙x = x y z e la funzione obiettivo F ( ˙x) = 1 2∗ G T( ˙x) ∗ G( ˙x) (12) F ( ˙x) = 1 2 h (−10 ∗ N1x∗ log10(d1x) − A1− R1x) 2 + · · · + (−10 ∗ Nnx∗ log10(dnx) − An− Rnx) 2i partendo da un punto ˙ x(0)= x0 y0 z0 con questo metodo:
˙ x(1)= ˙x(0)− γ0∇F ˙ x(0) (13) ricordando che ∇F ˙x(0) = J G x˙(0) T ∗ G ˙x(0)
e JGè come ci si aspetta la Jacobiana di G calcolata in ˙x(0)
e così avanti per i passi successivi.
9.2 I conti
Ora non resta che fare realmente i conti.
JG( ˙x) = ∂ ∂xE1 ∂ ∂yE1 ∂ ∂zE1 ∂ ∂xE2 ∂ ∂yE2 ∂ ∂zE2 · · · · ∂ ∂xEi ∂ ∂yEi ∂ ∂zEi · · · · ∂ ∂xEn ∂ ∂yEn ∂ ∂zEn (14)
in questo caso i dierenziali sono molto simili quindi si lavorerà per dieren-ziare una generica equazione i-esima:
Ei = −10 ∗ Nix∗ log10(dix) − Ai− Rix
ora sia Aiche Rixsono delle costanti, resta da schematizzare il resto.
∂ ∂xEi= −10∗ ∂ ∂x(Nix∗ log10(dix)) = −10∗ ∂ ∂x(Nix) ∗ log10(dix) + Nix∗ ∂ ∂x(log10(dix)) (15) ∂ ∂yEi= −10∗ ∂ ∂y(Nix∗ log10(dix)) = −10∗ ∂ ∂y(Nix) ∗ log10(dix) + Nix∗ ∂ ∂y(log10(dix)) (16) ∂ ∂zEi= −10∗ ∂ ∂z(Nix∗ log10(dix)) = −10∗ ∂ ∂z(Nix) ∗ log10(dix) + Nix∗ ∂ ∂z(log10(dix)) (17)
non resta per iniziare che trovare ∂ ∂x(Nix), ∂ ∂y(Nix), ∂ ∂z(Nix): ∂ ∂xNix= ∂ ∂x n X j6=i Cj x − xpj 2 + y − ypj 2 + z − zpj 2 −1 2log x − xpj 2 + y − ypj 2 + z − zpj 2 per derivare una somma si fanno le derivate dei singoli addendi:
∂ δx Cj x − xpj 2 + y − ypj 2 + z − zpj 2 ∗ 1 2log x − xpj 2 + y − ypj 2 + z − zpj 2 =∗ se si rinominano C x − x 2+ y − y 2+ z − z 2= U
