CORSO DI LAUREA SPECIALISTICA IN INGEGNERIA DELL ...schenato/PSC07/RelazionePSC07_Track_2.pdf ·...

CORSO DI LAUREA SPECIALISTICA IN INGEGNERIA DELL’AUTOMAZIONE, PROGETTAZIONE DI SISTEMI DI CONTROLLO, AA 2006/07 1

Localizzazione e tracking distribuito tramite rete disensori wireless

Alessandro Marcassa (546931-IAM), Riccardo Marcon (547379-IAM),Fabio Maran (547557-IAM), Filippo Zanella (550895-IAM)

Abstract— In questo progetto si affronta il problemadella localizzazione di un nodo wireless utilizzando le infor-mazioni derivanti dalle comunicazioni radio fra i nodi diuna rete di sensori wireless. Nel capitolo II verrà propostal’architettura hardware e software scelta, successivamentesi procederà all’analisi della connettività, capitolo III,basata sugli studi precedenti ([8], [9], [13], [18] e [19]).Seguirà la descrizione degli algoritmi di localizzazione,capitolo IV, e i risultati ottenuti in simulazione, al V. Infineverrà presentato dettagliatamente il pacchetto softwarerealizzato, dal lato WSN in NesC+TinyOS, al capitolo VI,e dal lato GUI in Java+Linux, al VII.

I. INTRODUZIONE

L a necessità di monitorare ambienti indoor e outdoorè un aspetto comune a diversi settori per svariate

applicazioni: monitoraggio dell’ambiente, logistico e deitrasporti, militare, etc. Queste esigenze hanno portatoallo sviluppo di reti di sensori in grado di acquisire,elaborare, organizzare e instradare le informazioni nec-essarie al controllo dell’ambiente in cui è inserita la retestessa. Grazie allo sviluppo tecnologico di dispositivielettronici a basso costo, a ridotto consumo di energia,di piccole dimensioni e in grado di comunicare via radiocon altri dispositivi, si sono potute sviluppare wirelesssensor network (WSN) apposite per lo sviluppo delleapplicazioni sopracitate. Uno dei problemi più vicinialle esigenze del mercato è quello della localizzazione:determinare con precisione la posizione di uno o più nodimobili nota quella dei nodi fissi. In particolare, in questoprogetto si propone di sviluppare l’architettura di unarete di sensori wireless all’interno di un edificio di grandidimensioni, in grado di localizzare e fornire informazionidi posizione in tempo reale e in maniera distribuita aduna serie di operatori. Tale architettura sarà costituita da

una WSN all’interno dell’area di interesse composta danodi la cui posizione è nota ai nodi stessi e agli operatori.L’operatore è dotato di una strumentazione appropriata(palmare, videotelefono, etc..) in grado di interfacciarsicon la rete di nodi fissi. Ogni operatore porta con se unpalmare con un sensore simile a quelli usati dalla retefissa integrato (nodo mobile), in grado di interagire conesse.

Il progetto verrà sviluppato in collaborazione con M31engineering per l’INFN di Legnaro (che si estende su unasuperficie di 8000 [m2]): lo scopo è la realizzazione di unsistema di localizzazione di emergenza da utilizzare incaso di incendio per permettere alle squadre di soccorsodi operare al meglio in ambienti particolarmente ostili.

Lo sviluppo si articola in quattro passi fondamentali.

A La prima parte sarà dedicata allo sviluppometodologico che dovrà affrontare i seguenti punti:

1) studio e sviluppo di metriche per la con-nettività dell’ambiente in analisi: si andràa verificare con appositi test quando larete è affidabile e il numero minimo dinodi e loro posizione ottima per ottenereun’adeguata connettività. Inoltre si cercheràdi valutare soluzioni hardware differenti (so-prattutto riguardanti la scelta dell’antenna:interna o esterna omnidirezionale) che an-dranno a facilitare l’ingegnerizzazione (PuntoC).

2) sviluppo di algoritmi di localizzazionee tracking con conseguente studiodell’architettura di rete più consona trauna caratterizzata da intelligenza distribuitae una centralizzata.

2 CORSO DI LAUREA SPECIALISTICA IN INGEGNERIA DELL’AUTOMAZIONE, PROGETTAZIONE DI SISTEMI DI CONTROLLO, AA 2006/07

B Implementazione del Testbed in una zona ristrettadel complesso per facilitarne lo studio: la zona inquestione sarà la peggiore dal punto di vista dellaconnettività, in modo da poter lavorare nel worstcase e rendere il sistema più efficiente possibile evalido anche per le altre zone.

C Identificazione del prodotto e ottimizzazione deicosti progettando dei nodi ad hoc sulla base deirisultati ottenuti nei Testbed.

D Sviluppo delle interfacce utente (GUI).

Il gruppo si propone di sviluppare al meglio i punti Ae B lasciando la parte di ingegnerizzazione (C e D) asviluppi futuri.

LOCALIZZAZIONE E TRACKING DISTRIBUITO TRAMITE RETE DI SENSORI WIRELESS 3

II. ARCHITETTURA DEL SISTEMA

P er lo sviluppo del sistema risulta fondamentale ladefinizione del tipo di architettura (su questa si

baseranno gli studi descritti nei punti 2, 3 del paragrafoI).

La soluzione più consona è un’architettura decen-tralizzata, in modo da poter garantire una maggior ro-bustezza in caso di guasto, una migliore connettività euna maggior velocità di calcolo grazie alla distribuzionedel carico computazionale tra i vari nodi ancora. Inparticolare verrà considerata una struttura di nodi ancoracollegata via wireless ad un access-point di riferimento,connesso a sua volta via ethernet con il sistema dicontrollo centrale la cui funzione sarà quella di rilevarela posizione di tutti i nodi mobili. Ogni nodo mobilecollegato ad un palmare si autolocalizzerrà sfruttandoi segnali ricevuti dai nodi ancora e, allo stesso tempo,reinvierà la sua posizione alla rete di sensori fissa chesi preoccuperà di instradare tale informazione all’accesspoint di zona e quindi al sistema di elaborazione centraleper un monitoraggio globale di tutti gli operatori attivi.

Fig. 1: Schema generale dell’applicazione.

In figura 1 è riportata tale struttura: come si può notareil mote (cioè la tipologia di nodo wireless utilizzato,figura 2) mobile collegato al palmare comunica solocon i nodi della zona in cui si trova (in realtà con unasottocella di tale zona formata da n mote vicini in mododa poter gestire al meglio il traffico dei dati) e attraversol’algoritmo descritto in IV determina la sua posizioneche viene poi inviata, prima via wireless e poi via LAN,al sistema di elaborazione centrale.

Tale architettura verrà realizzata con hardware di"sviluppo" dal quale sarà possibile ricavare prezioseinformazioni per la progettazione di hardware ad-hoc inun ottica di commercializzazione del prodotto.

Fig. 2: Nodo TmoteSky.

Nel dettaglio i nodi utilizzati sono TMOTESKYr (figura2) prodotti dalla MOTEIVr (i dati tecnici sono riportatiin [2]). I nodi TMOTESKYr sono equipaggiati con unmicrocontrollore MSP430 [4] prodotto dalla Texas In-struments il quale ha a disposizione 48Kbyte di memoriaFlash dedicata per il software e 10Kbyte di SRAM. Haun oscillatore (DCO) che opera sopra gli 8[MHz] e unoscillatore al quarzo utile alla calibrazione del primo.È dotato di 8 porte ADC interne e altrettante esterne,necessarie per leggere i valori dei sensori o dei livelli dibatterie.La piattaforma è dotata anche di una flash RAM (STM25P80, [6]) che opera a 40[MHz] e fornisce 1024[kB]per memorizzare dati divisi in 16 segmenti di 64[kB]l’uno e collegata al microcontrollore tramite il bus SPI.Il chip radio montato è il CC2420 prodotto dalla Chipcon(i dati tecnici sono riportati in [5] assieme allo stan-dard IEEE 802.15.4 descritto in [7]) ed è controllatodall’MSP430 tramite il bus SPI. Possono essere program-


mati tutti i parametri fondamentali per la trasmissione :è possibile definire attraverso appositi comandi potenza,frequenza e gruppo. La radio lavora infatti nell’intornodei 2.4[GHz] con una modulazione O-QPSK, ma èpossibile selezionare tra 16 canali differenti numerati da11 a 26, con i quali ci si può spostare dalla frequenzabase con step di 5[MHz] per canale. Per quanto riguardala potenza in trasmissione, sono disponibili 32 diversilivelli, quantizzati in 8 possibili valori elencati nellatabella I dal più elevato (31) al più debole (3).

TABLE I: Livelli di potenza di trasmissione con relativiconsumi.

LIVELLO Pot. di trasmissione [dBm] Consumo [mA]31 0 17.427 −1 16.523 −3 15.219 −5 13.915 −7 12.511 −10 11.27 −15 9.93 −25 8.5

Inoltre con questo integrato è possibile rilevare l’indicedi potenza del segnale ricevuto (RSSI) e l’indicatore diqualità della connessione (LQI).

I nodi sono programmati in un linguaggio di altolivello simile al C/C++, il NESC, e gli algoritmi digestione delle diverse funzionalità del chip sono gestiteattraverso il sistema operativo TINYOS. Il lato utente sicompone di una GUI scritta in JAVA.Dopo uno studio preliminare approfondito del TINYOSsi è deciso di utilizzare la versione più recente delsoftware, la 2.0.1, a fronte dei numerosi perfezionamentiapportati e dei bug opportunamente corretti o patchati,rispetto alla versione 1.0.In questo progetto non verrà fornita una trattazione sullaprogrammazione del sistema operativo, data l’odiernacomplessità del TINYOS, si rimanda perciò, per i dettaglitecnici, alla numerosa letteratura disponibile a riguardo[22], [23], [24], [25], [26], [27], [28], [29], [30].


III. ANALISI DELLA CONNETTIVITÀ

N ell’implementazione di una WSN è fondamentaleconsiderare le distanze che la connessione wireless

deve coprire e quindi le attenuazioni dovute all’ambientedove è installato l’applicativo. Nel caso in esame (in-door) le problematiche sono particolarmente evidenti: ènoto che in tali ambienti la connessione è soggetta amolteplici fenomeni di disturbo e risulta quindi difficil-mente prevedibile la propagazione delle onde elettromag-netiche. Queste tipologie di disturbi sono strettamentelegati alla lunghezza d’onda del campo elettromagneticoe alle dimensioni degli oggetti circostanti. Come già ac-cennato nel capitolo introduttivo lo standard di comuni-cazione utilizzato dai nodi è l’IEEE 802.15.4 (Zig Bee)che limita le frequenze di trasmissione nell’intervallo2400 ÷ 2483.5[MHz]: la lunghezza d’onda del campoelettromagnetico generato sarà dell’ordine di 12.08 ÷12.5[cm]. Se si considera che esistono numerosi oggettiall’interno di tale intervallo, i fenomeni che più andrannoad incidere nelle comunicazione sono:

• riflessione: questo disturbo è dovuto ad ostacoliaventi dimensioni molto maggiori della lunghezzad’onda del segnale. Quando l’onda raggiunge unoggetto riflettente con un angolo θ rispetto allanormale e la sua traiettoria si modifica tornandoindietro secondo un angolo θ′ = −θ.

Fig. 3: Esempio di riflessione.

• diffrazione: è un fenomeno dovuto alla natura on-dulatoria del campo elettromagnetico e si verificaquando il campo insiste su oggetti impenetrabiliseparati fra loro di distanze inferiori della lunghezza

d’onda. Una volta attraversata la fenditura si creauna superficie di onde semi-circolari, di intensitàpari alla prima, che si propagano in ogni di-rezione (principio di Huygens). Il fenomeno delladiffrazione è anche detto shadowing in quanto con-sente la trasmissione del campo elettromagneticofra trasmettitore e ricevitore anche quando fra i duemanca un cammino diretto.

Fig. 4: Esempio di diffrazione.

• Scattering: la presenza di oggetti impenetrabili didimensione paragonabile alla lunghezza d’onda ela natura corpuscolare del campo elettromagneticofa si che l’energia dell’onda, che insiste su talioggetti, venga reirradiata in moltissime direzioninon stimabili.

Fig. 5: Esempio di scattering, nel caso di fotoni.

Il manifestarsi di questi fenomeni portano allaricezione di innumerevoli onde elettromagnetiche prove-nienti da molteplici direzioni (conseguentemente con fasidifferenti) e quindi si generano interferenze costruttive odistruttive a seconda dell’amplificazione o attenuazionedella potenza del campo. Queste variazioni della potenzadel campo elettromagnetico ricevuto, rispetto al valorenominale, prendono il nome di medium scale fading: il


fenomeno si dimostra essere tanto più evidente quantopiù si restringe l’intervallo di frequenze utilizzate nellatrasmissione radio. Al fine di ridurre tale effetto ilprotocollo di comunicazione di livello fisico utilizzatodai nodi prevede l’utilizzo di tecniche di tipo Direct Se-quence Spread Spectrum (DSSS) con una modulazioneO-QPSK che consentono la suddivisione della potenzadel segnale sull’intera banda consentita dal protocollo,83.5[MHz], e la conseguente riduzione della probabilitàdi errore nella ricezione dei pacchetti.

Per quanto appena detto, prima dello sviluppo dialgoritmi di localizzazione è fondamentale effettuare unostudio sufficientemente approfondito per la valutazionein termini empirici e statistici della connessione in ter-mini di distanza e qualità. Per fare questo si è selezionatauna zona particolare dell’Istituto Nazionale di FisicaNucleare caratterizzata da muri e pareti in calcestruzzo dispessore compreso tra 0.7 e 1.4[m], generatori e quadrielettrici ad alta tensione e gabbie metalliche di sicurezzaalte 1[m] circa. Tutto questo è fonte di disturbo per letrasmissioni radio e quindi è sensato un test in questazona in quanto si va ad analizzare nel caso limite (worst-case).

In figura 6 è riportata la planimetria della zona inquestione, formata da un corridoio di accesso e tre stanzeprincipali: la prima (in alto, da adesso rinominata ZONA1) è una sala di 539[m2] caratterizzata da due stanze (S1e S2) delimitate da muri spessi 0.7 [m] e una stanza prin-cipale con colonne portanti in cemento armato di 1[m2],inoltre i soffitti sono attraversati da canalette metallichecontenti cavi dati o cavi ad alta tensione (20000[V]).La seconda (in basso, da adesso rinominata ZONA 2) siestende su 500[m2] con una stanza (S3) e, diversamentedalla precedente, questa stanza presenta numerosi gruppidi continuità. Il corridoio permette l’accesso solo allaZONA 1 attraverso la quale si arriva alla ZONA 2per mezzo di un cancello, passando per una piccolastanza intermedia (ZONA 3). La zona è stata scelta,oltre che per le sue caratteristiche strutturali, anche perla sua predisposizione ideale al test di algoritmi dilocalizzazione e tracking con supporto all’instradamentoin un dato punto avendo a disposizione svariati accessie quindi più percorsi possibili per raggiungere un dato

punto.

ZONA 1

ZONA 2

ZONA 3

S1

S3

S2

Fig. 6: Planimetria della zona in cui è stato effettuato ilTest-Bed.

Per come sarà strutturato l’algoritmo (localizzazionebasata sulle prestazioni della comunicazione tra nodomobile e nodi ancora adiacenti) non risulta necessariaun’analisi delle connettività estesa dove si deve conside-rare la connessione di tutti i nodi ancora nella zona dicopertura [9]. Nel nostro caso sono state effettuate duetipologie di prove, la prima per analizzare ed individuarela distanza ottima tra i nodi ancora, la seconda perstudiare il comportamento del nodo mobile rispetto allesottocelle previste dall’algoritmo di localizzazione.

A. Modello del canale

Prima di andare a discutere i risultati ottenuti nei varitest è necessario definire con precisione il modello delcanale trasmissivo in questione. Dagli studi effettuatinegli ultimi anni, si utilizzano i parametri forniti dalchip radio (RSS e LQI) per lo sviluppo di tecniche dilocalizzazione.

LQI (Level Quality Indicator) indica la facilità diassociare la sequenza di simboli ricevuti ad una parola diquattro bit. Quindi questo valore si lega alla misura dalla


quantità di rumore presente nella banda in cui avvienela trasmissione.

L’RSS è un valore determinato a partire dal valoredi RSSI (Received Signal Strength Indicator), e i dueparametri sono legati dall’equazione (si veda i datasheetdell’integrato CC2420 [5]):

RSS = RSSI − 45 [dBm]

dove il valore di RSSI possiede un’accuratezza di6[dBm] ed è quantizzato su un insieme di 100 valori.

SmartRF CC2420

-60

-40

-20

0

20

40

60

-100 -80 -60 -40 -20 0

RF Level [dBm]

RS

SI R

eg

iste

r V

alu

e

Figure 27. Typical RSSI value vs. input power

24 Link Quality Indication

The link quality indication (LQI) measurement is a characterisation of the strength and/or quality of a received packet, as defined by [1].

The RSSI value described in the previous section may be used by the MAC software to produce the LQI value. The LQI value is required by [1] to be limited to the range 0 through 255, with at least 8 unique values. Software is responsible for generating the appropriate scaling of the LQI value for the given application.

Using the RSSI value directly to calculate the LQI value has the disadvantage that e.g. a narrowband interferer inside the channel bandwidth will increase the LQI value although it actually reduces the true

link quality. CC2420 therefore also provides an average correlation value for each incoming packet, based on the 8 first symbols following the SFD. This unsigned 7-bit value can be looked upon as a measurement of the “chip error rate,”

although CC2420 does not do chip decision.

As described in the Frame check sequence section on page 38, the average correlation value for the 8 first symbols is appended to each received frame together with the RSSI and CRC OK/not OK when MDMCTRL0.AUTOCRC is set. A correlation

value of ~110 indicates a maximum quality frame while a value of ~50 is typically the lowest quality frames detectable by

CC2420.

Software must convert the correlation value to the range 0-255 defined by [1], e.g. by calculating:

LQI = (CORR – a) · b

limited to the range 0-255, where a and b are found empirically based on PER measurements as a function of the correlation value.

A combination of RSSI and correlation values may also be used to generate the LQI value.

Chipcon AS SmartRF CC2420 Datasheet (rev 1.3), 2005-10-03 Page 50 of 90

Fig. 7: Andamento dell’RSSI in funzione della potenza delsegnale ricevuto.

Dagli studi fin ora effettuati ([13], [9]), non risultachiara quali dei due parametri restituisca maggiori in-formazioni ai fini della localizzazione, tuttavia si èscelto di utilizzare l’RSS dato il modello noto che legala distanza di trasmissione con la potenza del campoelettromagnetico

P (d) = P (d0)− 10np log(

d

d0

)+ χσ. (1)

dove si definisce:

• la potenza P (d) del campo elettromagnetico rice-vuto espressa in [dBm];

• la potenza P (d0) del campo elettromagnetico aduna distanza d0 fissata dal trasmettitore espressa in[dBm];

• il fattore np di decrescenza della potenza del campoelettromagnetico in funzione del logaritmo delladistanza dal trasmettitore;

• la variabile aleatoria gaussiana χσ di media nulla evarianza σ2 (espressa in [dBm]);

• la distanza d (espressa in [m]) dal trasmettitore.

Dall’equazione (1) si deduce che P (d) è una variabilealeatoria gaussiana di media

P (d) = P (d0)− 10np log(

d

d0

)e varianza σ (in quanto P (d) è espressa come trasfor-mazione lineare affine di una variabile aleatoria gaus-siana). Una formulazione alternativa a (1) è

P (d) = PTX + A− 10np log(d) + χσ

dove compare la potenza di trasmissione PTX nota eil fattore di attenuazione A. Infatti all’aumentare delladistanza d tra trasmettitore e ricevitore la potenza delcampo elettromagnetico decresce con legge:

P (d) =P (d0)( d

d0)np

[W] =

=⇒ 10 log(P (d0)) + 10np log(P (d0))

− 10np log(P (d)) [dBm]

=⇒ P (d)[dBm] = 10 log(

P (d)1[mW]

)=

= PTX + A− 10np log(

d

d0

)dove si ipotizza un generico valore np > 2 in quanto ilcanale trasmissivo non è ideale e quindi dissipa energia(il valore ideale è np = 2). L’effetto del medium scalefading, dipendente direttamente dalle coordinate spazialidei due nodi, è modellato con la variabile aleatoria gaus-siana χ espressa in [dBm], a media nulla (in quanto nonmisurabile) e varianza σ determinabile empiricamente.

Tale modello quindi esclude il movimento deglioggetti o meglio il passaggio delle persone negli am-bienti, effetto che può essere notevolmente attenuatomediando il valore dell’RSS nel tempo. Dopo varieprove effettuate analizzando l’RSS ottenuto dalla comu-nicazione tra due mote a più distanze prefissate, si èvisto che per rendere sufficientemente stabile la misuradella potenza del segnale ricevuto senza far decadereeccessivamente le prestazioni di un generico algoritmodi localizzazione è mediare l’RSS su 40 pacchetti inviaticon un tempo di campionamento di 15[ms]. I risultatiottenuti sono riportati nella figura 8.Infine si tenga conto che il modello non considera osta-coli come i muri che diminuiscono il valore dell’RSSI


0 100 200 300 400 500 600 700 800 900−55

−54

−53

−52

−51

−50

−49R

SS

[dB

m]

n

RSS

Media su Nr Campioni

Fig. 8: Andamento dell’RSS misurato e mediato.

a parità di distanza trasmettitore-ricevitore. Tuttavia, daidati ottenuti durante l’analisi di connettività, si è vistoche mediando il valore dell’RSS la presenza o menodi un muro in cemento armato di 1[m] è irrilevanteper distanze inferiori ai 5[m]. A conferma di ciò siriportano parte delle misurazioni effettuate analizzandola comunicazione tra due mote con e senza ostacoli. Inparticolare si riporta la sperimentazione, effettuata in unarco temporale di 22.5[s] con tempo di campionamentodi 50[ms], in cui si confronta l’RSS ottenuto dallacomunicazione tra gli stessi mote alla stessa distanzadi 3[m] con e senza una colonna di cemento armato di1[m2] tra i 2 (figura 9).

0 50 100 150 200 250 300 350 400 450−76

−75

−74

−73

−72

−71

−70

−69

−68

−67

−66

−65

Campioni

Pote

nza

Ric

evuta

RSS

[dB

m]

Media

Media

Media

RSS 3[m] no muro

RSS 3[m] muro

RSS 3[m] muro

Fig. 9: Andamento dell’RSS con e senza muro di disturbo.

B. Identificazione dei Parametri del Canale

Il modello del canale definito nel paragrafo III-Anecessita della stima dei parametri: A, np e σ. Come

prima cosa, al fine di rendere più precisa la stima, ènecessario verificare le potenze di trasmissione note edimpostabili del chip CC2420, come riportato in tabellaII.

TABLE II: Livelli di potenza di trasmissione misuraticonfrontati con il datasheet.

LIVELLO Pot. di trasmissione Pot. di trasmissioneda datasheet [dBm] misurata [dBm]

31 0 027 −1 −123 −3 −419 −5 −715 −7 −811 −10 −137 −15 −173 −25 −27

Per identificare i parametri del modello si è inizial-mente scelto di utilizzare due metodi: stimatore ai mini-mi quadrati e RANSAC (Random Sample Consensus).

Per quanto riguarda lo stimatore ai minimi quadrati sidefinisce un modello di regressione lineare:

y = Sθ + w =y1

...yN

= S

[m

q

]+

w1

...wN

,

S =

x1 1...

...xN 1

dove compaiono i parametri che descrivono l’equazionedella retta yi = mxi + q (i = 1, . . . , N ) con xi

corrispondente al logaritmo della distanza tra i due motee yi il corrispondente RSS. Inoltre si ipotizza w vettorealeatorio a media nulla e varianza σ2IN . Si dimostra [10]che lo stimatore ai minimi quadrati risulta:

θ = (ST S)−1STy

con varianza:σ2 =

1N‖y − Sθ‖2

Diversamente, RANSAC è basato sulla votazione:vince la stima dei parametri più votata dai dati equindi permette di eliminare gli outliers i.e. dati chenon ottengono mai un grande consenso facendo deviare


notevolmente la stima M.Q. L’algoritmo si articola in trepassaggi fondamentali:

1) si prende un campione casuale di n puntidall’insieme delle osservazioni;

2) per questo sottoinsieme (J = i1, . . . , in) sidetermina la regressione, attraverso gli n puntirisolvendo un sistema di n equazioni lineari in n

incognite, ottenendo una stima di prova θJ ;3) si calcola il consenso della stima:

|yi : (yi − xTi θJ)2 < T | ovvero la cardinalità

delle osservazioni che concordano (entro unacerta tolleranza T ) con la stima di prova;

4) si ripetono i passi 1 ÷ 3 finché il consenso nonsupera una certa soglia τ ;

5) si effettua una regressione sui punti dell’insiemedi consenso trovato per calcolare la stima finale.

La differenza principale tra uno stimatore ai minimiquadrati e RANSAC è che il primo ricerca la soluzioneche minimizza una certa misura di dispersione, mentrel’obiettivo di RANSAC è quello di trovare il più grandeinsieme di consenso nell’insieme delle osservazioni ipo-tizzando l’esistenza dei parametri "veri" per il modello.

0 0.2 0.4 0.6 0.8 1−100

−95

−90

−85

−80

−75

−70

−65

−60

−55

log(d) [m]

Pote

nza

Ric

evuta

RSS

[dB

m]

RSS

Modello RANSAC

Modello MQ

Fig. 10: Andamento del modello del canale ottenutorispettivamente con una stima MQ e RANSAC.

Nel nostro caso non avendo un modello del canale suf-ficientemente preciso si è optato per un’identificazionedei parametri utilizzando lo stimatore ai minimi quadrati.In figura 10 sono riportati i modelli stimati con le duetecniche, tuttavia si tenga conto che ad ogni test ilmodello ritornato da RANSAC risulta diverso in quantoil canale non è esattamente lineare e quindi l’algoritmo

varia sistematicamente l’insieme di inliers.

Una volta determinata la tecnica di identificazionesi è scelto di effettuare misure nelle varie zone deltestbed posizionando i mote ad una distanza compresanell’intervallo [0 15][m] sia per terra che sul sof-fitto. Fittando le 88000 misure si è stimata la retta aiM.Q. riportata nel grafico 11 che è caratterizzata daun’attenuazione del canale A pari a −63.67[dBm], uncoefficiente di decadimento np pari a 2.12 e una varianzaσ di 7.57[dBm]. Tuttavia l’ambiente particolarmentevario in quanto a disturbi e il circuito di calcolo dell’RSSintegrato nel chip CC2420, che secondo i datasheet pre-senta un’incertezza differente tra mote e mote, portanoa stime dei parametri del canale diverse.

0 0.2 0.4 0.6 0.8 1

−100

−95

−90

−85

−80

−75

−70

−65

−60

−55

log(d) [m]

Pote

nza

Ric

evuta

[dB

m]

Fig. 11: Andamento del modello del canale ottenuto con unastima MQ utilizzando tutti i dati a disposizione.

Nella tabella III e nel grafico 12 sono riportati rispet-tivamente la stima del modello effettuata basandosi sudue set di dati differenti per posizionamento: nel primoset i dati sono stati raccolti ancorando i mote al soffittocon l’antenna rivolta verso il basso e il secondo setappoggiandoli per terra con l’antenna rivolta verso l’alto.

Analoghi risultati sono stati ottenuti anche utilizzandomote diversi nelle stesse condizioni ambientali.

TABLE III: Variazione dei parametri del modello al variaredei set di dati acquisiti.

A [dBm] np σ [dBm]Mote sul soffitto −59.77 2.15 3.81Mote a terra 2 −62.80 2.01 4.26


0 0.2 0.4 0.6 0.8 1

−90

−85

−80

−75

−70

−65

−60

−55

log(d) [m]

Pote

nza

Ric

evuta

RSS

[dB

m]

Set 1

Set 2

Modello MQ Set 1

Modello MQ Set 2

Fig. 12: Andamento del modello del canale ottenuto con unastima MQ basata su 2 set di dati differenti.

Nella tabella IV e nel grafico 13 sono riportati i duemodelli ottenuti utilizzando una coppia di mote differ-ente.

TABLE IV: Variazione dei parametri del modello al variaredei set di dati acquisiti.A [dBm] np σ [dBm]

Set 1 −59.77 2.15 3.81Set 2 −75.0 1.63 6.08

0 0.2 0.4 0.6 0.8 1

−100

−95

−90

−85

−80

−75

−70

−65

−60

−55

log(d) [m]

Pote

nza

Ric

evuta

[dB

m]

Set 1

Set 2

Modello MQ Set 1

Modello MQ Set 2

Fig. 13: Andamento del modello del canale ottenuto con unastima MQ basata su 2 set di dati differenti ottenuti con mote

diversi.

Per ovviare a questa problematica si è optato, in fasedi testbed, per tarare i parametri del canale su ognisingolo mote. Infatti, come si vedrà in seguito la stimadella distanza del nodo mobile rispetto al singolo nodoancora verrà fatta dal nodo ancora stesso. Con le tecnichedescritte nel paragrafo III-A, si è proceduto alla taraturadi A, np, e σ di ogni piattaforma wireless. Tale soluzione

è ovviamente a scopo di test, in un’ottica di sviluppodi un prodotto finito si può sviluppare un software ditaratura automatica che dato un set sufficiente ampiodi dati ricevuti da ogni mote con la distanza dal nodomobile variabile determini automaticamente i parametridel canale.

C. Distanza Ottimale tra i Nodi Ancora

Come già introdotto, è necessario individuareuna disposizione ottima dei nodi ancora: visto chel’applicazione lo permette, si vuole disporre il minornumero di sensori nella zona di interesse assicurandola miglior connettività possibile solo tra nodi adiacenti.Quindi si vuole aumentare il più possibile la distanza T

tra i vari sensori, senza incorrere in perdita di pacchettidovuta alla scarsa connettività.

Il posizionamento regolare ottimo dei nodi di unaWSN è riportato in figura 14 dove l’area è coperta conil minimo numero di sensori N :

N =2PAREA

T 2√

3(2)

dove PAREA è la dimensione dell’area da monitorare.Inoltre, in caso si volesse sfruttare i nodi ancora permonitorare delle grandezze fisiche quali temperatura eluminosità (grandezze molto utili, ad esempio in casodi incendio, per instradare gli utenti in possesso dellostrumento di localizzazione verso percorsi sicuri cheevitino stanze potenzialmente incendiate) si può rivederel’equazione (2) considerando il raggio di sensitività r =T/sqrt3:

N =2PAREA

r2√

27. (3)

Secondo gli studi di connettività effettuati nei labo-ratori del Dipartimento di Ingegneria dell’Informazionedell’Università degli Studi di Padova [9], risulta che ilink compresi nella fascia tra gli 8 e i 12[m] comunicanocon una percentuale di pacchetti persi pari al 26%.Tenendo conto che il Test-Bed verrà effettuato in unambiente più ostico si considera che un buon valore perT è dato da 4[m] (da cui si ricava che gli eventualisensori montati sui nodi ancora dovranno avere un raggiodi sensitività r = T/

√3 = 2.31[m]): quindi nelle varie

zone definite nella figura 6 saranno necessari un ben


determinato numero di sensori riportato in tabella V.

r

T

TT

Fig. 14: Disposizione ottima di una WSN.

TABLE V: Stima iniziale del numero di sensori.Ambiente Dimensione [m2] Numero di Sensori

Zona 1 539 39Zona 2 499.8 36Zona 3 18.38 1

Corridoio 144 10

Una volta determinata la posizione e il numero disensori si è pensato a come orientarli non essendociun’antenna omnidirezionale installata ma una sempliceantenna planare.

(a) (b)

(c) (d)

Fig. 15: Possibili Orientazioni dei mote, da in alto a sinistra:mote sullo stesso piano orizzontale con le antenne affacciatee non, mote su piani verticali con antenne affacciate e non.

Empiricamente si è visto che posizionando due moteorizzontalmente (quindi con le antenne sullo stesso pianoorizzontale, figura 15(a)) con le antenne affacciate con0.5[cm] di distanza si ottiene un RSS compreso tra −9 e−13[dBm] (con LQI pari a 107) che cala nell’intervallo[−15 − 18][dBm] in caso di antenne non affacciate

(15(b)). Diversamente, se si posizionano i mote su pianiverticali paralleli, con le antenne affacciate (15(c)) a0.5[cm] di distanza si ha un RSS di 0[dBm] con LQIpari a 107 che cala fina a −5[dBm] orientando le antennecon direzioni opposte (15(d)).Quindi, come già ci si aspettava, i nodi ancora sono statiposizionati sul soffitto con l’antenna rivolta verso il bassoipotizzando il nodo mobile sempre con la stessa rivoltaverso l’alto.

D. Caratterizzazione della cella

Una volta determinata la posizione dei nodi ancorasono state effettuate ulteriori prove per verificare la bontàdel segnale RSS in un ottica di stima della distanzabasata su misure provenienti da una cella di mote con-siderata "affidabile".

Dalle misure effettuate si è visto che il modello linearedella potenza (III-B) è valido entro un raggio d’azionedi 10[m] a cui corrispondo −75[dBm] sotto i quali lamisura non è più attendibile (figura 16), ulteriori e piùapprofondite considerazioni saranno fatte nel paragraforelativo alla localizzazione.

0 5 10 15 20 25 30 35 40

−90

−85

−80

−75

−70

−65

−60

−55

Distanza Percorsa [m]

RSS

[dB

m]

RSS

RSS mediatosu 40 pacchetti

Fig. 16: Andamento dell’RSS in funzione della distanza.

Successivamente è stata effettuata un’analisi dellaperdita di pacchetti, i cui risultati sono riportati neigrafici 17 e 18. Come si può notare la probabilitàdi arrivo è superiore allo 0.98% entro i 6[m] oltreil quale si dimostra esserci un’intervallo variabile incui la probabilità di arrivo assume un andamento non


deterministico (nel nostro caso [6 14][m]) per poi tenderea 0 (oltre i 18[m]). L’andamento appena descritto èconfermato, con intervalli diversi, anche dall’analisi diconnettività effettuata presso il Dipartimento di Ingeg-neria dell’Informazione dell’Università di Padova [9].

0 2 4 6 8 10 12 140

1000

2000

3000

4000

5000

6000

7000

8000

Distanza tra i nodi [m]

Pacc

het

tiin

via

ti

0 2 4 6 8 10 12 140

200

400

600

800

1000

1200

1400

1600

1800


Pacc

het

tiper

si

Fig. 17: Numero di pacchetti inviati (figura di sinistra) e persi(figura destra) nell’intervallo di distanza tra mote [0 14][m].

0 2 4 6 8 10 12 140.65

0.7

0.75

0.8

0.85

0.9

0.95

1


Pro

babilit

adiarr

ivo

λ

Fig. 18: Probabilità empirica di arrivo di un pacchetto alvariare della distanza tra i mote.

Tali risultati sono stati ulteriormente verificati analiz-zando l’RSS e l’LQI ricevuto da un nodo mobile trasmet-titore mosso con velocità costante lungo una traiettoriarettilinea di 12[m] (figura 19) all’interno di una zonadi 4 nodi ancora fissati sul soffito. Come si può notarel’andamento dell’RSS mediato su 40 pacchetti risulta co-erente con i risultati precedenti e sufficientemente stabile.Infatti gli andamenti relativi ai nodi 6 e 7 sono semprecrescenti in quanto la traiettoria prefissata prevede unavvicinamento costante a tali mote. Diversamente l’RSSrelativo ai nodi 9 e 10 presenta il suo massimo a 10[m],i.e. quando il nodo mobile passa sotto il nodo 10 che cor-risponde appunto alla distanza minima tra nodo mobile enodi 9, 10. Gli andamenti sono risultati coincidenti con

Fig. 19: Posizionamento dei sensori (quadrati blu conrelativo numero rosso) nell’area di testbed e traiettoria

seguita dal nodo mobile.

quelli ottenuti in simulazione, a parte per i valori ottenutiin quanto il simulatore non considera la terza dimensione(figura 20). Infatti quando il nodo mobile si trova sotto alnodo 10 per il simulatore la distanza è nulla mentre nelnostro caso è pari alla distanza verticale tra nodo ancorae mobile di 1.08[m].

0 2 4 6 8 10−90

−85

−80

−75

−70

−65

−60

−55

−50

d [m]

Pote

nza

Ric

evuta

RSS

[dB

m]

Nodo 6

Nodo 7

Nodo 9

Nodo 10

Fig. 20: Variazione dell’RSS dei nodi ancora con lospostamento del nodo mobile ottenuto in simulazione.

Per quanto riguarda l’andamento dell’LQI si vede che unvalore attendibile per discriminare l’RSS è superiore a


100 tarabile a seconda del range massimo in cui si vuoleconsiderare l’RSS.

Da queste analisi sono stati dedotti i parametri dis-criminanti per la formazione delle celle di misura unadistanza nodo ancora-mobile non superiore ai 6[m] conRSS non inferiore a −75[dBm] e LQI superiore a 103.Queste condizioni sono da ritenere utili esclusivamenteper questo tipo di applicazione. Infatti se si consideral’applicazione di secondaria di instradamento dei dati diposizione per il monitoraggio di ogni nodo mobile sipuò pensare di sfruttare percorsi che sfruttano nodi adistanze maggiori ottenendo quindi minor ritardo e unminor rischio globale di perdita di pacchetti effettuandoun routing che interessa meno nodi.

0 2 4 6 8 10

−80

−70

−60

−50

Distanza [m]

RSS

[dB

m]N

odo

10

0 2 4 6 8 10

−80

−70

−60

RSS

[dB

m]N

odo

9

0 2 4 6 8 10

−80

−70

−60

RSS

[dB

m]N

odo

6

0 2 4 6 8 10−80

−70

−60

RSS

[dB

m]N

odo

7

Fig. 21: Variazione dell’RSS dei nodi ancora con lospostamento del nodo mobile.

0 2 4 6 8 10100

102

104

106

108

Distanza [m]

LQ

I[d

Bm

]N

odo

10

0 2 4 6 8 1095

100

105

LQ

I[d

Bm

]N

odo

9

0 2 4 6 8 10

95

100

105

LQ

I[d

Bm

]N

odo

6

0 2 4 6 8 10

102

104

106

108

LQ

I[d

Bm

]N

odo

7

Fig. 22: Variazione dell’LQI dei nodi ancora con lospostamento del nodo mobile.


IV. LOCALIZZAZIONE

L a letteratura riguardante la localizzazione basatasulla cooperazione tra sensori è molto estesa, in-

teressando svariati ambiti di ricerca come l’elaborazionenumerica dei segnali, la statistica e l’informatica. Unapanoramica sulle principali tecniche fonte d’ispirazioneper l’algoritmo ideato è riportata nel paragrafo IV-A; perun esempio su alcuni progetti realizzati si veda [13].

Grande importanza ha il tipo di sensore di cui il nodowireless è equipaggiato: sismico, magnetico, acustico,infrarossi oppure a onde radio; in generale quindi lagrandezza fisica misurata (dal sensore) è diversa daquella utilizzata per la trasmissione delle informazioni tranodi via wireless (onde radio). Nel nostro caso, invece,le onde radio vengono usate sia per la misura dellagrandezza fisica che per la comunicazione tra nodi; ladifferenza sta nel modo in cui si analizza tale grandezza[14]:

1) misura della potenza del segnale ricevuto RSS,come nel caso in esame; la relazione tra RSS edistanza tra nodi è ben modellizzata da (1), comevalidato dai numerosi esperimenti effettuati nelcapitolo III, [13], [14];

2) misura del tempo di volo TOA (Time of Arrival),dato dal tempo che il segnale radio impiega pergiungere al ricevitore; il TOA misurato è dato dallasomma del tempo di trasmissione e del ritardodi tempo dovuto alla propagazione del segnale.Indicato con Ti,j[s] il ritardo tra la trasmissione delsensore j-esimo e la ricezione di quello i-esimo,allora Ti,j = di,j

vpin cui di,j[m] è la distanza tra i

due nodi e vp[m/s] è la velocità di propagazione:pertanto dalla misura del TOA si riesce a stimarela distanza tra ogni coppia di sensori, e quindi sipossono utilizzare tutte queste stime per il calcolodella posizione;

3) misura dell’angolo di arrivo AOA (Angle of Ar-rival), che dà informazioni al nodo ricevente sulladirezione del nodo trasmettente (figura 23); questainformazione è da considerarsi complementare alTOA e all’RSS per la risoluzione del problemadella localizzazione.

Fig. 23: Angolo di arrivo AOA e un possibile metodo per lasua stima; sul nodo ricevente (sensor node) si dispongono

due o più antenne RF aventi locazioni note: la stimadell’AOA è effettuata a partire dalle differenze nei tempi divolo tra nodo trasmittente (source signal) e le varie antenne.

A. Stato dell’arte e definizione del problema

Si deve innanzitutto definire precisamente il problemada risolvere; le principali categorie cui afferiscono iproblemi di localizzazione sono

1) autolocalizzazione: si devono stimare le coordinatedei nodi fissi di una rete wireless, conoscendoquelle di alcuni di loro;

2) tracking: si devono stimare le coordinate di uno(single-target tracking) o più (multi-target track-ing) nodi mobili, detti target, che si muovonoall’interno di una rete di nodi fissi aventi coor-dinate note.

Il problema affrontato in questo lavoro cade nella secon-da categoria, come formalmente definito da1

Problema 1 (Single-Target Tracking): Si consideriuna rete di N sensori, indicati con i pedici 1, . . . , N ;il problema è quello della stima delle coordinate di unsensore mobile connesso via porta seriale USB a unportatile/palmare,

z1(t) =(x1(t), y1(t), z1(t)

)per t ∈ R,

date le coordinate note e costanti nel tempo degli N − 1

1Il problema 1 è definito su tre gradi di libertà poichè il por-tatile/palmare si muove nello spazio; tuttavia il problema può esserefacilmente ridotto a due gradi di libertà.


nodi fissi,

zj = (xj , yj , zj) con j = 2, . . . , N ;

la stima di posizione è effettuata in istanti discreti neltempo: z1(kTc) con k ∈ Z e Tc[s] periodo di cam-pionamento. I sensori effettuano misure di potenza delsegnale ricevuto RSS, i.e. Pi,j è la potenza (1) ricevutadal nodo i-esimo e trasmessa dal nodo j-esimo. A partireda queste, l’algoritmo di localizzazione, presente neinodi wireless oppure nel portatile/palmare, stima z1(t)assumendo una simmetria nelle osservazioni, i.e. Pi,j =Pj,i. È previsto il caso di osservazioni incomplete, incui ad esempio due nodi siano troppo lontani e non siapossibile la comunicazione.�

Gli algoritmi che risolvono il problema del trackingpossono essere divisi generalmente in due gruppi: cen-tralizzati e decentralizzati.

Negli algoritmi centralizzati [14] le misure vengonotrasmesse a un processore centrale che in seguito svolgeil calcolo della posizione; la stima può essere di tipostatico o dinamico:

1) nel caso di stima statica, z1(kTc) è basata solosulle misure di potenza raccolte all’istante kTc;molteplici approcci possono essere utilizzati, dallastima ai minimi quadrati a quella di massimaverosimiglianza;

2) nel caso di stima dinamica, z1(kTc) è basata sullemisure di potenza raccolte fino all’istante kTc,utilizzando ovviamente approcci di tipo ricorsivo(filtro di Kalman) che evitano la memorizzazionedi tutte le misure ad ogni istante.

Lo stimatore di massima verosimiglianza (M.V.) puòessere derivato e usato se i dati sono descritti bene daun particolare modello statistico (e.g. gaussiano o log-normale); una ragione per usare questo stimatore è chela sua varianza tende asintoticamente al limite inferioredi Cramer-Rao. In questo approccio si deve trovare ilmassimo della funzione di verosimiglianza, e pertantonascono due difficoltà:

1) massimi locali: sebbene la stima di M.V. sia ini-zializzata a un valore possibilmente vicino allasoluzione corretta, è possibile che l’algoritmo di

massimizzazione non trovi il massimo globale;2) dipendenza dal modello: se le misure non sono

descritte bene dal modello scelto (o dai parametridel modello), allora non sono più garantiti risultatiottimali.

Negli algoritmi distribuiti [17], [12], [20] i sensoricondividono le informazioni solo con i vicini. Ci sonodue grandi motivazioni per sviluppare tali algoritmi:innanzitutto, in certe applicazioni non è disponibile unprocessore centrale oppure il carico computazionale è ec-cessivo per l’hardware a disposizione; inoltre, è preferi-bile evitare il collo di bottiglia che si genera quandoun’intera rete di sensori invia pacchetti ad un’uniconodo centrale. Gli algoritmi distribuiti che si trovano inletteratura sono in maggior parte composti dai seguentipassi:

1) il primo nodo ancora H1 che avverte il target nellevicinanze (RSS misurato supera una certa soglia)sveglia i nodi ancora vicini (i quali formano unacella) che quindi si mettono in ascolto;

2) si elegge un nodo leader H2 nella cella di nodiancora vicini al target, in base ad esempio alladistanza stimata o ai valori di RSS misurati;

3) H1 passa la track information a H2 che nel frat-tempo riceve tutti i valori di RSS misurati dairimanenti nodi della cella;

4) H2 effettua la stima di posizione del target ediventa il nuovo track information keeper H1;

5) si itera il procedimento.

Oltre alla stima di posizione del target, si può fare ancheuna stima di velocità e direzione [17] in modo tale dapredirne il comportamento e attivare preventivamentela cella in cui il target probabilmente starà nell’istantesuccessivo.

B. Algoritmo proposto

L’algoritmo proposto ha l’ambizioso obiettivo disfruttare il meglio di entrambi gli approcci, centra-lizzato e decentralizzato. In primo luogo si è stu-diato lo stimatore M.V. centralizzato sviluppato daN. Patwari [14], [15], [16] per risolvere il problemadell’autolocalizzazione dato che il tracking è un caso


speciale in cui tutti i nodi sono fissi con coordinatenote, tranne il nodo target (ricordiamo che il nostroproblema è di single-target tracking). In seguito si èadattato questo stimatore alle specifiche degli algoritmidistribuiti, introducendo il concetto di cella, al fineprincipalmente di ridurre le collisioni di pacchetti e fareseguire una parte consistente del calcolo della stima ainodi fissi in maniera parallela (diminuzione del caricocomputazionale del palmare/nodo centrale e diminuzionedel tempo di stima).

L’algoritmo proposto è costituito da due parti:l’algoritmo principale nel caso in cui il collegamentoseriale tra portatile/palmare sia funzionante e l’algoritmodi recovery se il collegamento risulta interrotto; il primoè stato implementato e testato sui nodi wireless, mentreil secondo è stato provato solo in simulazione.

L’algoritmo principale realizzato è composto daiseguenti passi:

1) inizializzazione: tutti i nodi si accendono, settanoil canale di comunicazione e la potenza di trasmis-sione, accendono la radio;

2) broadcast: il nodo mobile manda in broadcastogni Tbroad[ms] a tutti i nodi fissi Npck pacchetti(ciascun pacchetto viene mandato ogni Tpck[ms]),mentre i nodi fissi sono in attesa di pacchetti;

3) ascolto: a partire dal primo pacchetto ricevuto dalnodo mobile, ciascun nodo fisso j = 2, . . . , N ,tiene i pacchetti ricevuti in memoria se la potenzadel segnale ricevuto P1,j e l’indice di qualitàdella ricezione LQI superano rispettivamente certesoglie precalcolate Pth[dBm] e LQIth;

4) formazione della cella: ciascun nodo fisso j =2, . . . , N , calcola la media campionaria P1,j (10)delle potenze P1,j sui pacchetti effettivamentememorizzati e in seguito esegue una stima di M.V.della distanza d1,j col nodo mobile, d1,j data da(11) e basata su P1,j ; si forma in tal modo unacella di Ns nodi vicini al nodo mobile, definitadall’insieme

As ={

j > 1∣∣P1,j > Pth, d1,j < Range

e LQI1,j > LQIth

},

dove Range[m] sta ad indicare il range radio delnodo mobile;

5) invio distanze stimate: i nodi appartenenti alla cellaAs inviano al nodo mobile pacchetti contenenti illoro identificativo j e la stima della distanza d1,j

calcolata al punto precedente;6) stima della posizione: il nodo mobile raccoglie

tutti le stime d1,j e le invia attraverso collega-mento seriale (USB) al portatile/palmare a cui ècollegato; il portatile/palmare effettua la stima diM.V. z1(kTc) (data da (14)) della propria posizionee contemporaneamente il nodo mobile ritorna alpunto 2.

Da numerose prove su campo si sono trovati i seguentivalori per i parametri dell’algoritmo, che possono esseresoggetti a variazioni: Tbroad = 1050[ms], Npck = 40,Tpck = 15[ms], Pth = −80[dBm], LQIth = 103 eRange = 6[m]; si noti che il periodo di broadcastcoincide con il tempo di campionamento della stimaeffettuata, i.e. Tbroad = Tc.

Nel caso in cui il portatile/palmare si rompa o co-munque non sia più disponibile (e quindi la comuni-cazione seriale risulti interrotta), è previsto un algo-ritmo di recovery in cui la stima è fatta dai nodi fissitramite uno stimatore meno pesante computazionalmenterispetto a quello di M.V.; questo procedimento si com-pone dei seguenti passi:

1) il primo punto è composto dal broadcast, ascoltoe formazione della cella dell’algoritmo principale;

2) invio distanze stimate: i nodi appartenenti alla cellaAs inviano al nodo mobile pacchetti contenenti illoro identificativo j, la loro posizione zj , la stimadella distanza d1,j e/o la stima di E

[d2

1,j

](in base

alla scelta dei pesi da usare nell’algoritmo M.R.C.,(18) oppure (19)) calcolata al punto precedente;

3) stima della posizione: il nodo mobile raccoglietutti le stime d1,j e le posizioni zj e le salva inmemoria; successivamente effettua la stima dellasua posizione z1(kTc) tramite minimi quadratiM.Q. (16) se |As| ≥ 3 mentre tramite maximumratio combining M.R.C. (17) altrimenti; infine in-via z1(kTc) al sistema di supervisione;

4) check seriale: il nodo mobile fa una verifica se


il collegamento seriale è ancora interrotto; in talcaso ritorna al punto 1 dell’algoritmo di recovery,altrimenti va al punto 2 dell’algoritmo principale.

L’esclusione dei nodi lontani rispetto al target dallaformazione della cella permette di non utilizzare infor-mazioni erronee nella stima di posizione: infatti si èevidenziato empiricamente2 che il modello lineare perla potenza (1) è una buona descrizione del canale radiosolo fino ad una certa soglia Pth oltre la quale è difficiledare una descrizione accurata (intervengono saturazionio altre non linearità non modellizzabili).

Gli stimatori di posizione (14), (16) e (17) checompongono gli algoritmi ideati, sono stati ricavati eutilizzati a tre gradi di libertà (le incognite in tal casosono date da x1(t), y1(t) e z1(t)); è immediato ricavarei medesimi stimatori a due gradi di libertà, eliminandodalle equazioni l’incognita z1(t) e adattando le espres-sioni.

La scelta del metodo di stima (M.Q. o M.R.C.)nell’algoritmo di recovery è dovuta al fatto che la stimaM.Q. (16) non viene effettuata se |As| ≤ 2 (problemasottodimensionato) quando si usano tre gradi di libertàe se |As| = 1 quando si usano due gradi di libertà,risultando in quest’ultimo caso fallace se |As| = 2 (comerisulta evidenziato dalle simulazioni).

Nelle prossime sezioni verranno illustrati tutti glistimatori che compongono gli algoritmi sviluppati, prin-cipale e di recovery.

C. Stimatore di M.V. della distanza

La potenza ricevuta in [dBm] al sensore mobile etrasmessa dal sensore j-esimo, P1,j modellizzata da (1),ha densità di probabilità gaussiana

f(p |x1, y1, z1) =1√

2πσ2exp

{−1

2

(p− P (d1,j)

σ

)2}

(4)

dove

d1,j = ||z1 − zj ||

=√

(x1 − xj)2 + (y1 − yj)

2 + (z1 − zj)2.

2Testando sul campo il funzionamento dello stimatore M.V. delladistanza (9).

La funzione di log-verosimiglianza ottenuta a partire da(4) risulta essere

ln f(p |x1, y1, z1) = c1 −[p− P (||z1 − zj ||)

]22σ2

(5)

con c1 costante indipendente da (x1, y1, z1); è chiaro cheil massimo di (5) è ottenuto per P1,j = P (||z1 − zj ||)essendo una forma quadratica e quindi lo stimatore diM.V. della distanza è

d1,j = d0 · 10P (d0)−P1,j

10np . (6)

Lo stimatore (6) ha le proprietà di avere distribuzionelog-normale, essendo ln d1,j distribuito normalmente, edi non essere corretto, dato che [13]

E[d1,j

]= C||z1 − zj ||

dove C = exp (γ/2) con

γ =(

σ ln 1010np

)2

;

la varianza di (6) è data da [13]

Var[d1,j

]= eγ (eγ − 1) ||z1 − zj ||2. (7)

Uno stimatore corretto, ma non più di M.V., è dato quindida

d1,j =d0

C10

P (d0)−P1,j

10np , (8)

avente varianza [13]

Var[d1,j

]= (eγ − 1) ||z1 − zj ||2.

Si noti come lo stimatore di M.V. (6) può essere anchescritto in funzione di d1,j ,

d1,j = d1,j · 10χσ

10np ,

evidenziando come l’errore di stima d1,j − d1,j siaproporzionale alla distanza. Pertanto per sfruttare almassimo l’accuratezza data dall’RSS a piccole distanze,è necessario utilizzare una rete abbastanza densa di nodie soprattutto usare le informazioni fornite dai nodi fissipiù vicini al nodo mobile.

Lo stimatore di M.V. della distanza (6) può esserenotevolmente migliorato se lo si calcola a partire dalla


media di P1,j ,

d1,j , d0 · 10P (d0)−P1,j

10np ; (9)

infatti, sostituendo la media P1,j data da (III-A) nella(9), si ottiene lo stimatore di (pseudo-) M.V.

d1,j = d0 · 10log(d1,j/d0) = d1,j .

La media statistica P1,j può essere approssimata daquella campionaria utilizzando il teorema ergodico3 [11]

P1,j(Npck) ,1

Npck

Npck∑i=1

P1,j(i) −→ P1,j per Npck →∞

(10)

in cui Npck è il numero di potenze su cui si fa la mediae i = 1, . . . , Npck è l’indice temporale con cui vienecampionata la potenza; pertanto lo stimatore di (pseudo-) M.V. realizzato è dato da

dNpck

1,j , d0 · 10P (d0)−P1,j(Npck)

10np . (11)

D. Limite di Cramer-Rao per lo stimatore della distanza

Per (8) ha senso il confronto della sua varianza con illimite inferiore della varianza (scalare) per uno stimatorecorretto, detto limite di Cramer-Rao, dato da [11]

Var[d]≥ C.R.Bound =

1I(d)

in cui I(d) è la matrice di Fisher associata alla famigliaparametrica di densità (4) che descrive P (d),

I(d) = −Ed

[∂2 ln f(p | d)

∂d2

];

la derivata seconda della densità ln f(p | d) rispetto alparametro d è data da [13]

∂2 ln f(p | d)∂d2

=1d2

(10np

ln 10σ

)2

(ln d− 1)

+1d2

10np

ln 10σ2(p− P (d0))

e quindi la matrice di Fisher risulta

I(d) =1d2

(10np

ln 10σ

)2

.

3In un intervallo di broadcast Tbroad la distanza vera può essereconsiderata costante e pertanto le misure di RSS sono variabilialeatorie che compongono un processo aleatorio i.i.d. P1,j(iTpck),con i ∈ Z base dei tempi, per cui vale il teorema ergodico.

In conclusione si ha

C.R.Bound =1

I(d)= d2γ;

con i parametri del canale a disposizione (A =−63.67[dBm], np = 2.12 e σ = 7.57[dBm]) si ottiene

Var[d]

= 0.966 · d2 ≥ C.R.Bound = 0.6760 · d2 :

si noti come la varianza dello stimatore di M.V. sia sensi-bilmente maggiore rispetto al limite inferiore di Cramer-Rao, a causa della notevole dispersione delle misure dipotenza (al 95% delle probabilità, P1,j è compresa traP (d1,j)± 1.96σ = P (d1,j)± 14.8372[dBm]).

E. Stimatore di M.V. della posizione

Si definisca p ∈ R|As| il vettore ottenuto incolon-nando le potenze effettivamente ricevute dai nodi fissidella cella, dove si è indicato con |As| la cardinalitàdell’insieme As; nell’ipotesi di indipendenza dei varicanali di comunicazione, si ha che la densità di pro-babilità congiunta di p è

f(p |x1, y1, z1) =1

(2πσ2)|As|exp

{−1

2||p− E[p]||2

σ2

}= c

∏j∈As

{exp

[−1

2

(P1,j − P (d1,j)

σ

)2]}(12)

in cui c è un’opportuna costante indipendente da(x1, y1, z1). Inserendo l’equazione (1) in (12), prenden-done il logaritmo negativo e calcolando il minimo, siottiene che lo stimatore di M.V. della posizione è

z1 = (x1, y1, z1) , arg max(x1,y1,z1)

ln f(p |x1, y1, z1)

= arg min(x1,y1,z1)

∑j∈As

(ln

d21,j

d21,j

)2

; (13)

il minimo viene calcolato numericamente tramitel’algoritmo del gradiente coniugato [21]. La stima (13)è non corretta, a causa dell’errore di bias nello stimatoredi M.V. della distanza d1,j ; si può quindi definire uno


stimatore di pseudo-M.V. dato da

z1 = (x1, y1, z1) = arg min(x1,y1,z1)

∑j∈As

(ln

d21,j

d21,j

)2

= arg min(x1,y1,z1)

∑j∈As

(ln

d21,j

C2d21,j

)2

in cui si utilizza d1,j per stimare la distanza.La stima effettivamente realizzata nell’algoritmo usa

lo stimatore M.V. della distanza dato da (9), che utilizzala media delle potenze; lo stimatore della posizionediviene quindi

z1 = (x1, y1, z1) = arg min(x1,y1,z1)

∑j∈As

(ln

d21,j

d21,j

)2

. (14)

F. Stimatore ai M.Q. della posizione

In questo caso, per ottenere la stima della posizionez1(t), si risolve il seguente sistema sovradeterminato[13]

||z1(t)− zi1 ||2 = d21,i1

...||z1(t)− ziM

||2 = d21,iM

(15)

dove gli indici i1, . . . , iM stanno ad indicare i nodifissi, appartenenti alla cella As, che contribuiscono allastima. Il sistema (15) può essere riportato ad un sistemalineare nelle incognite x1(t) e y1(t), sottraendo allaprima equazione tutte le successive, ottenendo

xi1 − xi2 yi1 − yi2 zi1 − zi2

......

xi1 − xiMyi1 − yiM

zi1 − ziM

︸︷︷︸

A

x1(t)y1(t)z1(t)

︸︷︷︸

z1(t)

=

12

d2

i2− d2

i1− x2

i2+ x2

i1− y2

i2+ y2

i1− z2

i2+ z2

i1...

d2iM− d2

i1− x2

iM+ x2

i1− y2

iM+ y2

i1− z2

iM+ z2

i1

︸︷︷︸

b

;

questo è risolvibile tramite la tecnica dei M.Q., i.e.

z1(t) = arg minz1(t)

||Az1(t)− b||2

=(AT A

)−1ATb (16)

in cui si utilizza la stima M.V. della distanza d1,ik(data

da (11)) al posto della distanza vera d1,ik.

G. Stimatore M.R.C. della posizione

La stima della posizione è data da una combinazioneconvessa delle coordinate dei nodi fissi che appartengonoalla cella, i.e.

z1(t) =∑j∈As

wjzj (17)

dove wj sono pesi che soddisfano alla condizione∑j∈As

wj = 1. I wj sono scelti in modo da consideraremaggiormente le coordinate dei nodi fissi più vicini alnodo mobile; una possibile scelta è data da

wj =1/d2

1,j∑i∈As

(1/d2

1,i

) (18)

oppure da

wj =1/E

[d2

1,j

]∑

i∈As

(1/E

[d2

1,i

]) (19)

in cui le potenze statistiche vengono calcolate in manieracampionaria sfruttando il teorema ergodico4 [11], i.e.

E[d2

1,j

]' 1

Npck

Npck∑k=1

d21,j(k)

dove ciascuna stima della distanza (6) k-esima è fattasu un solo pacchetto. I pesi (19) sfruttano il fatto chela potenza statistica delle stime aumenta all’aumentaredella distanza: infatti, per lo stimatore a MV non correttoa partire da (7) si ottiene

E[d2

1,j

]= Var

[d1,j

]+ E

[d1,j

]2= eγ (eγ − 1) d2

1,j + eγd21,j

= e2γd21,j .

4In un intervallo di broadcast Tbroad, le d21,j sono variabili aleatorie

funzioni di P1,j e formano un processo aleatorio d21,j(iTpck), con i ∈

Z base dei tempi; pertanto vale il teorema ergodico per d21,j(iTpck).


V. SIMULATORE

P er testare la bontà degli algoritmi finora illustratie verificarne la robustezza al variare dei parametri

caratterizzanti (quali numero di nodi nella stanza, nu-mero di pacchetti su cui mediare, parametri del canaledi trasmissione e altro), è stato implementato un pro-gramma di simulazione.

Si è scelto di realizzarlo in MATLAB, per sfruttarel’elasticità del linguaggio di programmazione e la vastasuite di funzioni messe a disposizione dell’utente.

L’approccio è del tutto parametrico: l’utente può ge-stire ogni tipo di situazione grazie alla modularità dellefunzioni implementate. In breve, le fasi del programmasono

1) generazione della traiettoria e impostazione deiparametri;

2) posizionamento dei nodi in base alle dimensionidella stanza e al numero desiderato, secondoquanto illustrato in figura 14;

3) ad ogni istante di simulazione, calcolo della stimadella distanza fra ogni nodo àncora e il nodomobile, e formazione della cella

4) ad ogni istante di simulazione, calcolo della stimadella posizione con il metodo scelto in base alledistanze calcolate al punto precedente;

5) plottaggio finale delle traiettorie vera e stimata,dell’andamento dell’errore di stima (in norma) erelativa analisi in media e varianza campionarie.

Vediamo ora nello specifico le funzioni e le caratteri-stiche fondamentali del simulatore.

A. Funzioni implementate

Il simulatore si articola in una serie di funzioni MAT-LAB implementate per rendere il più possibile accurati eaffidabili i risultati: analizziamole nel dettaglio.

1) Generazione delle traiettorie. Come primo aspettoci si è occupati di realizzare funzioni in grado digenerare traiettorie all’interno dell’area di interes-se. Sono stati scelti due approcci. In primo luo-go, si è implementata la funzione randomWalk,che restituisce una passeggiata aleatoria di Nsim

(parametro passato in ingresso) campioni sfrut-tando il modello in spazio di stato

xk+1 = Axk + vk

yk = Cxk + wk

dove lo stato è composto da posizione e velocitàin x e in y, le matricei A e C sono

A =

1 0.1 0 00 1 0 00 0 1 0.10 0 0 1

C =

[1 0 0 00 0 1 0

]in modo che l’uscita corrisponda solo alla po-sizione, e vk, wk sono rispettivamente i rumoridi modello e di misura. Parametri necessari sonolo stato iniziale x0 (il “punto di partenza” dellatraiettoria) e le costanti moltiplicative q e r chemoltiplicano rispettivamente le matrici

Q =

0.01 0.1 0 00.1 1 0 00 0 0.01 0.10 0 0.1 1

R =

[0.01 00 0.01

]varianza dei rumori di modello e di misura.In alternativa, si è implementato anche un fileTrajectoryGenerator che presi in ingressole dimensioni della stanza dimX , dimY e il nu-mero di campioni desiderati Nsim, genera a casoNsim/5 punti equidistanziati due a due, li inter-pola mediante spline cubica e infine effettua unadecimazione per riportare il numero di campioni aNsim.In entrambi i casi, viene restituita una matrice Y ∈R2×Nsim avente nella generica colonna i l’i-esimacoordinata della traiettoria (xi, yi).

2) Posizionamento dei nodi. La funzionenodePositioning permette la disposizioneautomatica dei nodi àncora, note le dimensioni


della stanza (dimX , dimY ) e il numero di nodivoluto (Nnodes), secondo il metodo illustrato nelparagrafo III-C. Oltre a questi, un altro parametropreso in ingresso e rangeRadio, ovvero il raggiodi copertura del segnale radio di un nodo in[m], ottenuto da datasheet. Come prima cosa, lafunzione in base ai dati controlla che il numero dinodi inserito sia almeno uguale a quello minimonecessario per coprire l’intera dimensione dellastanza con la disposizione scelta, verificando chesia rispettata l’equazione (3): in caso contrario,l’intero programma si ferma.Nel paragrafo III-C si è visto come, nel caso in cuiil numero di nodi coincida con quello minimo, c’èuna semplice relazione geometrica fra il raggio ditrasmissione r e la distanza fra nodi T : r = T/

√3.

Per trovare la T necessaria si è quindi calcolatoun “falso” valore del range radio, fakeRange,tale per cui il numero di nodi voluto sia minimo,e tramite questo si ricava facilmente T . Sempregrazie a facili considerazioni geometriche sulladisposizione dei nodi, si ricava che la distanzalungo x fra due nodi è Tx = T , lungo y èTy = T

√3/2 (altezza di un triangolo equilatero

di lato T ). In base ai risultati appena ottenuti, siricava il numero di nodi lungo x e lungo y

Nx = round(dimX/Tx)

Ny = round(dimY /Ty);

si noti che l’arrotondamento, ovviamente neces-sario, comporta la possibilità che nella dispo-sizione finale il numero di nodi non sia esattamentequello richiesto, ma sia leggermente inferiore osuperiore (tipicamente di 1): questo è sensato, inquanto non è sempre geometricamente possibilecoprire l’area con un determinato numero di sen-sori. L’algoritmo comunque fa in modo che ilnumero sia il più vicino possibile.All’interno del ciclo vero e proprio di posiziona-mento è stato anche inserito un controllo per farein modo di non superare le dimensioni della stanza.Il piazzamento viene eseguito ponendo il primo

nodo in posizione (0, 0), e quindi le posizioni deinodi dei fissi non sono centrate nella stanza maspostate in basso a sinistra. L’ultimo passo consistequindi nel centrare la griglia creata, calcolando letraslazioni tx, ty necessarie. L’output della routineè una matrice coordinates ∈ R2×Ncoord (Ncoord

quantità di nodi fissi piazzati), avente su ognicolonna la coordinata di un nodo àncora (xi, yi),e la distanza T fra due nodi contigui.

3) Stima della distanza. Nota la traiettoriae la posizione dei nodi, la routinedistanceEstimateML simula la potenzaricevuta da un nodo àncora ed effettua in base adessa la stima a massima verosimiglianza (6) delladistanza dal nodo mobile. I parametri di ingressosono

• la distanza vera d

• il numero massimo di pacchetti su cui effet-tuare la media della potenza NmeanMax

• i parametri del canale np, d0, σ, A

• la probabilità di arrivo del singolo pacchettoλ.

Quest’ultimo parametro è stato introdotto per si-mulare la possibilità di perdita di pacchetti: eccoperchè viene passato non l’esatto numero di pac-chetti su cui mediare l’RSS, ma quello massimo.Per stabilire quale sarà il numero vero di pacchettiusati, si effettua un ciclo di NmeanMax iterazioniin ciauscuna delle quali si richiama la routinerandbin, che restituisce 1 con probabilità λ e0 con probabilità 1− λ. Il numero di pacchetti sucui si medierà, Nmean, sarà il totale di 1 ottenuti.Una volta ottenuto tale valore, si passa a simularela potenza ricevuta secondo l’equazione (1) usandoi parametri passati in ingresso (σ è la deviazionestandard della variabile aleatoria χσ) per ognunodegli Nmean pacchetti ricevuti; la potenza usataper la stima sarà la media dei valori calcolati.Nota quest’ultima, si effettua la stima ML comein (6), che viene restituita in output assieme allapotenza media calcolata e al numero di pacchettieffettivamente usati. È prevista inoltre la possibilità


di restituire la stima corretta di equazione (8).4) Funzione per la stima della posizione. La routine

ml è una semplice funzione che, presi in ingressoun punto z1, le coordinate dei nodi fissi e ledistanze stimate dal punto, restituisce al variare diz1 della funzione di log-verosimiglianza

∑j∈As

(ln

d21,j

d21,j

)2

di cui in seguito si troverà il punto che la mini-mizzi.

5) Stima della posizione. La funzionepositionEstimate è il cuore del simulatoreimplementato. I parametri di ingresso sono

• la traiettoria γ : T → Y, in cui T =[0 . . . Nsim] è la base dei tempi

• la matrice di coordinate dei nodi fissi• i parametri per il calcolo della stima della

distanza NmeanMax, np, d0, σ, A

• le soglie perla formazione della cella, Pth perla potenza, range per il raggio

• un vettore λ con le probabilità di arrivo dipacchetti in funzione della distanza

• una variabile booleana per la scelta di qualemetodo usare.

In particolare, il vettore λ ha in posizione i laprobabilità di arrivo dei pacchetti alle distanzecomprese fra i−1 e i [m]. L’andamento è scelto persemplicità con un interpolazione lineare ai minimiquadrati con saturazione, come evidente in figura24: i dati di partenza sono stati rilevati sul campo(figura 18). Si noti che si arriva solo fino ai 15 [m]in quanto sicuramente il limite per la formazionedella cella non sarà superiore e per evitare diandare a considerare zone in cui il segnale perdesignificativamente di affidabilità.Come prima operazione, la routine calcola una ma-trice di distanze D, in cui l’elemento in posizioneij corrisponde a

‖z1(i)− zj‖

ovvero la distanza fra il nodo àncora j e quello

0 2 4 6 8 10 12 140.65

0.7

0.75

0.8

0.85

0.9

0.95

1

1.05

distanza [m]

Probabilita di perdita di pacchetti

Fig. 24: Andamento della probabilità λ.

mobile all’istante i-esimo, i = 0, . . . , Nsim. Questivalori saranno necessari per richiamare la funzionedistanceEstimateML e simulare la potenzaricevuta da ogni nodo fisso.Dopo questa inizializzazione, si passaall’algoritmo vero e proprio. I passi sono iseguenti:

a) per ogni i-esimo istante di simulazione(i = 1, . . . , Nsim) si inizializzano due vet-tori vuoti, uno per le stime delle distanzeestimates, uno per tener conto del numerodi pacchetti su cui si è mediato (a scopodi analisi) currentMeanPackages e unamatrice group per memorizzare le coordinatedei nodi che formeranno la cella;

b) per ogni j-esimo nodo fisso si richiamala funzione distanceEstimateML

passando, oltre ai parametri del canale,l’elemento (D)ij e la giusta componente delvettore λ, ottenendo la stima della distanzaE, la potenza ricevuta P e il numero dipacchetti usati mean;

c) se E < range e P > Pth il nodo fa partedella cella, e si memorizzano la stima, ilnumero di pacchetti e le coordinate nei vettorie nella matrice precedentemente inizializzati;si itera il procedimento per tutti i nodi fissi;


d) se i vettori restano vuoti, significa che il nodomobile è uscito dall’area di interesse, e siblocca il programma;

e) altrimenti, si passa alla minimizzazione verae propria. Per calcolarla, si è utilizzata la rou-tine messa a disposizione dalle librerie MAT-LAB fminunc, che trova l’argomento cheminimizza una certa funzione senza che sianospecificati vincoli. Come parametri, bisognapassare il generico argomento rispetto cuifare la minimizzazione, la funzione da mi-nimizzare con eventuali parametri necessari(nel nostro caso, ml con il vettore estimates

e la matrice group) e la condizione inizialex0 da cui far partire l’algoritmo numericoper la ricerca del minimo. L’algoritmo uti-lizzato da fminunc è quello del gradienteconiugato (spiegato più avanti), e come c.i. èstata sempre presa la stima della posizionecalcolata al passo precedente, nell’ipotesi chelo spostamento fra due istanti successivi siaridotto e quindi al fine di facilitare la con-vergenza della procedura. Il risultato vienesalvato in una matrice X;

f) si salvano inoltre in due diversi cell-array(strutture dati caratteristiche di MATLAB chepermettono di memorizzare in matrici oggettiquali vettori o altre matrici) le coordinatedella cella corrente e i pacchetti usati perciascun nodo che vi appartiene;

g) si itera il procedimento.

Una considerazione su x0: il procedimento de-scritto non è chiaramente valido alla prima itera-zione, in cui non si hanno stime precalcolate. Perevitare di scegliere un valore a caso, col rischio diportare alla divergenza l’algoritmo, si è scelto diusare come inizializzazione al primo passo la stimaottenuta col metodo ai minimi quadrati descritto da(16).Quanto finora illustrato si verifica solo se il con-trollo sulla variabile booleana passata in ingressoalla funzione si rivela positivo. In caso contrario, la

routine effettua la stima della posizione col metodoMQ per ogni campione della traiettoria: i passi damodificare sono i seguenti

e) se la cella è formata da un solo nodo, si usala coordinata di tale àncora come stima; se èformata da due nodi, si usa una combinazioneconvessa con coefficienti illustrati nel para-grafo IV-G secondo il metodo MRC (a causadel possibile malcondizionamento di A). Al-trimenti, si calcolano la matrice A e il vettoreb come descritto nel paragrafo IV-F e si ricavala stima come nell’equazione (16), usando lasemplice routine privata implementata mq

Tutti gli altri step vengono eseguiti allo stessomodo.Si noti che la procedura appena descritta è iden-tica anche per l’inizializzazione di x0 alla primaiterazione quando si usi la stima MV.Infine, solo a scopo di confronto è stata realizzatauna variante per la stima dell’intera traiettoriacon il metodo MRC, nel qual caso il passo damodificare è

e) se la cella è formata da un solo nodo, siusa la coordinata di tale àncora come stima;altrimenti, si usa una combinazione convessacon coefficienti illustrati nel paragrafo IV-G.

L’output della funzione positionEstimate èla matrice X ∈ R2×N delle stime, un cell-arraycontentente le N celle e un altro cell-array contenteil numero di pacchetti usati di volta in volta dainodi delle varie celle.

6) Simulazione e plottaggio dei risultati. L’ultimaroutine implementata è Simulator. I parametridi ingresso sono

• la traiettoria γ

• le dimensioni della stanza dimX , dimY e ilnumero di nodi fissi Nnodes

• il raggio di copertura nominale del chip radiorangeRadio

• il numero massimo di pacchetti su cui mediareNmeanMax, il range per la formazione dellacella range e la potenza di soglia Pth


• i parametri del canale np, d0, A, σ

• il vettore delle probabilità di arrivo di pacchettiin funzione della distanza λ

• due variabili booleane ML e filmato.

Il programma in primo luogo richiama lafunzione nodePositioning per ottenerele coordinate dei nodi fissi, dopodiché usapositionEstimate per la stima vera epropria: la variabile ML ha lo scopo si selezionarequale metodo usare (settata a 1 seleziona il metodoMV, a 0 quello MQ). In uscita restituisce il vettoredelle stime e il cell-array contenente il numerodi pacchetti usati, entrambi derivati sempre dapositionEstimate.Oltre a questo, calcola la norma dell’errore di stimaper ogni istante di simulazione, e ne scrive su con-sole media e varianza campionarie; plotta inoltredue grafici, uno rappresentante l’area considerata,dove vengono messi in evidenza i nodi fissi, latraiettoria vera e quella stimata, l’altro l’andamentodella norma dell’errore.Infine, se la variabile filmato è settata a 1viene anche mostrato un filmato in cui si ve-dono real-time l’andamento vero e quello sti-mato, evidenziando ad ogni istante la cella us-ata (possibile grazie al cell-array ritornato dapositionEstimate, come descritto al puntoprecedente).

B. Risultati delle simulazioni

Il simulatore appena illustrato è stato utilizzato pertestare diversi metodi di stima sia della posizione chedella distanza, al variare dei parametri principali, sia perillustrare come alcune variazioni influenzino la qualitàdel risultato, sia come orientazione per le scelte dacompiere in fase di implementazione reale.

Per maggior coerenza, le simulazioni sono state effet-tuate considerando un’area del tutto simile a quella chesarà effettivamente usata nel testbed, ovvero una zona di11.5×12 [m2] coperta con 10 nodi, di cui uno all’esternodell’area. Nei grafici riportati, i nodi sono rappresentatida un asterisco nero e l’area di interesse è delimitata dalinee. Gli altri valori utilizzati sono stati

• rangeRadio = 30• range = 6• Pth = −80• NmeanMax = 40• np = 2.12• A = −63.67• d0 = 1• σ = 7.57• λ calcolato come interpolazione con polinomio di

6° grado dei dati raccolti per distanze fino a 15 [m].

Come traiettoria, si è utilizzato un percorso a passeg-giata aleatoria, interamente contenuto nell’area di inter-esse.

Da sottolineare il fatto che di default si è usato lostimatore non corretto della distanza, che si è rivelatomigliore di quello corretto, come si vedrà dall’analisidei dati.

1) Confronto fra metodi: il primo test riguarda il con-fronto fra i tre metodi di stima della posizione illustratinella sezione precedente: MV (o ML, dall’inglese Max-imum Likelihood), MQ e MRC. Gli andamenti sarannoutili per capire qual’è il metodo migliore sia per quantoriguarda l’algoritmo principale che quello di recovery,da far calcolare direttamente al nodo mobile nel casoin cui la seriale venga meno, per permetterne comunquel’individuazione e, nel caso specifico, l’invio di ulteriorisoccorsi.

I risultati sono riportati in figura 25, dove è evidentecome quello a massima verosimiglianza sia il più preciso,sia valutando la traiettoria stimata che osservando lanorma dell’errore, che si mantiene quasi costantementeben al di sotto del metro. Fra gli altri due, risulta migliorela stima ai minimi quadrati, che a parte qualche picco,mantiene un errore di stima significativamente più bassorispetto al maximum ratio combining (il peggiore deitre), ed è quindi da preferire come approccio alternativo.L’analisi statistica campionaria è in tabella VI, dove ivalori di media e varianza di ‖z‖ confermano quantomostrato dai grafici. Da sottolineare che il primo metodo,oltre ad avere l’errore in media più piccolo, mostra anchela varianza minore, a sottolineare come non solo sia il piùpreciso, ma anche il più affidabile a livello di stabilità.

I dati raccolti per quanto riguarda il metodo MRC


TABLE VI: Media e varianza di ‖z‖E[‖z‖] [m] Var ‖z‖ [m2]

MV 0.3186 0.0481MQ 0.8315 0.2968

MRC 2.7635 1.0659

sono stati calcolati usando combinatori proporzionali alledistanze stimate, come mostrato in (18): questo noncomporta né vantaggi né svantaggi rispetto all’utilizzodei coefficienti proporzionali alle varianze (equazione(19)), come si può vedere sia da figura 26 che in tabellaVII, dove sono messe a confronto e stime usando i duediversi tipi di combinatori.

TABLE VII: Media e varianza di ‖z‖E[‖z‖] [m] Var ‖z‖ [m2]

MRC (wj ∝ d1j) 1.4491 0.8409MRC (wj ∝ Var d1j) 1.4769 0.8113

Un’ultima osservazione va fatta per quanto riguardail malcondizionamento della matrice A nel metodo MQ.Come già accennato, nel caso in cui la cella sia formatada nodi fissi aventi tutti una coordinata comune, si hache una colonna della matrice è nulla, e ciò porta aduna soluzione indeterminata per quanto riguarda la stimacorrispondente a tale coordinata. Si consideri la figura25(a): si può notare come ci siano diverse stime MQ concoordinata y nulla, nonostante soltanto il primo passodella traiettoria rispecchi tale condizione. Questo accadeperchè, dato il particolare percorso, nei primi istantila cella è formata dai primi due nodi àncora in bassoa sinistra, che hanno proprio la medesima coordinatay: l’algoritmo, trovando una soluzione indeterminata, lapone a 0. Il problema è evidente soprattutto quandoquesta situazione si ripete per posizioni molto distantidall’origine, al contrario dell’esempio considerato: in talisituazioni, porre y = 0 comporta grandi errori nellastima della posizione. È perciò preferibile in questi casiaffidarsi alla stima MRC, che in caso di coordinatacomune mantiene tale coordinata anche per la stima(dato che effettua una combinazione convessa) e, seppursbagliando, l’errore è meno drammatico che in prece-denza: ecco perchè nell’implementazione si applica tale

metodo nel caso la cella sia formata da meno di trenodi (si è scelto così perchè praticamente impossibileche si formino celle con più di tre nodi aventi medesimacoordinata). Questa caratteristica dell’algoritmo MRC sipuò osservare sempre in figura 25, dove si notano diversestime avente la stessa coordinata y dei primi due nodifissi.

D’ora in avanti, i grafici includeranno solo i duemetodi migliori, essendo quelli significativi per il pro-getto.

2) Variazione del range della cella: le prove suc-cessive riguardano l’effetto di variazioni nel range diselezione della cella; ci si aspetta un miglioramentoall’aumentare di tale valore, dato che si includono piùstime della distanza ad ogni istante per calcolare laposizione, con un effetto “a saturazione”, poiché oltre uncerto valore è logico pensare che i nodi troppo distantidal mobile non forniscano più stime attendibili, noncontribuendo in maniera significativa al calcolo dellaposizione se non addirittura peggiorandolo.

I risultati sono riportati in figura 27–28–29–30,l’analisi di ‖z‖ in tabella VIII.

In particolare la tabella conferma quanto si era sospet-tato: con un range di 4 [m], pari alla distanza fra duenodi consecutivi, i risultati decadono notevolmente. Eraquanto ci si poteva aspettare, in questa condizione lecelle sono sempre formate da pochissimi nodi, e quindil’informazione si rivela spesso insufficiente per garantireuna buona stima della posizione. In particolare, si nota ungrosso decadimento nel metodo MQ a causa dei problemidi malcondizionamento nei tratti iniziale e finale delmoto, in cui le celle sono formate da due nodi con stessacoordinata y, e ciò pesa maggiormente quando i nodisono distanti dall’origine.

All’aumentare del range la situazione miglioranotevolmente, e per 6, 8 e 10 [m] i risultati si equival-gono, come c’era da aspettarsi: si può perciò concludereche 6 [m] è una distanza più che sufficiente per garantirela bontà della stima. È comunque interessante notarecome ai 10 [m] si abbia un leggero peggioramentonella stima MV, problema non risentito dai MQ cheanzi migliorano leggermente: questo perchè l’eccessodi informazione poco attendibile derivante dai nodi àn-


cora più lontani ha un’effetto negativo su un algoritmopreciso come quello a massima verosimiglianza, men-tre i minimi quadrati, il cui scopo è minimizzare lavarianza dell’errore, traggono giovamento dall’avere ungrosso numero di stime, anche se alcune di esse menoattendibili.

Ovviamente questo discorso non è da estremizzare, eun eccessiva quantità di stime della distanza errate portaad un decadimento della qualità di qualsiasi algoritmodi localizzazione.

Si tenga conto, infine, che il canale simulato è lineareper qualsiasi distanza d, al contrario del caso reale;pertanto è buona cosa non prendere range troppo grandi.

TABLE VIII: Media e varianza di ‖z‖E[‖z‖] [m] Var ‖z‖ [m2]

MV, range = 4 0.5581 0.2212MQ, range = 4 1.0814 2.2543MV, range = 6 0.3446 0.0845MQ, range = 6 0.6228 0.1308MV, range = 8 0.3569 0.0554MQ, range = 8 0.8212 0.3377MV, range = 10 0.4122 0.0745MQ, range = 10 0.7808 0.3502

3) Variazione del numero massimo di pacchetti:il comportamento con queste variazioni dovrebbe es-sere simile a quello del punto precedente, ovveroall’aumentare del numero massimo di pacchetti su cuicalcolare la media dell’RSS la stima della posizionedovrebbe migliorare, questa volta grazie alla maggiorcura nella stima della distanza dovuta ad una potenzaradio misurata con più precisione. Si dovrebbe comunquepresentare ancora una volta una effetto saturazione, inquanto è logico aspettarsi che oltre una certa soglia nonvi siano più miglioramenti apprezzabili alla precisionenella misura della potenza.

I grafici sono in figura 31–32–33–34, l’analisi statis-tica dell’errore in tabella IX, per valori di NmeanMax

pari a 20, 30, 40, 50. Il miglioramento all’aumentare delnumero di pacchetti è evidente dalla riduzione dei valorisia della media che della varianza della norma dell’erroredi posizione, per entrambi i metodi. Come ci si aspettava,

mentre i salti di qualità da 20 a 30 e da 30 a 40sono notevoli, fra 40 e 50 il miglioramento è molto piùlimitato, segno che tali valori sono vicini alla soglia diqualità massima. Da queste osservazioni, e a causa anchedei problemi di temporizzazione dei mote utilizzati, siè scelto come valore ottimale NmeanMax = 40, cherestituisce comunque risultati soddisfacenti.

TABLE IX: Media e varianza di ‖z‖E[‖z‖] [m] Var ‖z‖ [m2]

MV, NmeanMax = 20 0.5056 0.0943MQ, NmeanMax = 20 0.8932 0.2236MV, NmeanMax = 30 0.4256 0.0950MQ, NmeanMax = 30 0.7290 0.1918MV, NmeanMax = 40 0.3264 0.0439MQ, NmeanMax = 40 0.5549 0.1272MV, NmeanMax = 50 0.3085 0.0377MQ, NmeanMax = 50 0.5672 0.1241

4) Variazione del numero di nodi fissi: in questo caso,si è voluto osservare l’effetto di una diminuzione e di unaumento di circa il 50% del numero di nodi nell’area deltestbed, testando una copertura rispettivamente di 6 e 15nodi àncora, corrispondenti a distanze fra nodi contiguirispettivamente di 5.1535 [m] e 3.2593 [m].

I risultati sono in figura 35–36 e in tabella X, dove siriporta anche la distanza T fra due nodi contigui.

L’analisi non rivela sorprese: come è logico aspet-tarsi, una diminuzione del numero di nodi peggiorasensibilmente la stima, così come un aumento portagrande giovamento alla precisione. Il motivo è semplice:a parità di range per la formazione della cella, in uncaso si hanno meno nodi, nell’altro di più, e quindi lamaggior quantità di informazione attendibile riguardo lastima della distanza porta necessariamente a risultati piùaccurati. È quindi importante valutare bene il trade-offfra precisione e costo dei nodi per stabilirne il numeroottimale: nel nostro caso, si è scelto 10 in quanto unerrore medio di circa 30-35 [cm] è da considerarsi piùche soddisfacente ai fini dell’applicazione.

5) Variazioni dei parametri del canale: questo test èparticolarmente importante per l’implementazione reale.Il metodo scelto per stimare la distanza fisso-mobile èfortemente basato sul modello, e quindi ha una grande


TABLE X: Media e varianza di ‖z‖E[‖z‖] [m] Var ‖z‖ [m2]

MV, Nnodes = 6 0.5829 0.2153MQ, Nnodes = 6 1.1304 2.5362MV, Nnodes = 15 0.2371 0.0289MQ, Nnodes = 15 0.6196 0.1367

dipendenza dai parametri A,np: se non sono calcolaticon cura, e quindi quelli che appaiono nel processo dellepotenze (1) differiscono sensibilmente da quelli usatinella formula (9) per la stima a massima verosimiglianza,la stima prodotta degrada in maniera inaccettabile pro-ducendo risultati scadenti che vanno a ripercuotersi pe-santemente sulla stima della posizione, qualsiasi sia ilmetodo scelto per calcolarla.

Per simulare l’effetto di differenti valori di A, è statousato A = −56 in (1), derivato come si vedrà da proveempiriche nell’area di test, e A = −63.67 nell’equazione(9), ottenuto da un’interpolazione lineare dei dati raccolti(come illustrato nel paragrafo III-B). I grafici ottenutisono in figura 37, in tabella XI sono riportati mediae varianza di ‖z‖. È evidente un deciso calo delleprestazioni, con pessimi risultati e stime spesso sbagliatedi più di 2 [m] per entrambi i metodi: ciò confermaquanto sia cruciale trovare i valori giusti dei parametridel canale per avere valori affidabili di z, ed è quindinecessario curare attentamente questo aspetto in fase ditest.

TABLE XI: Media e varianza di ‖z‖E[‖z‖] [m] Var ‖z‖ [m2]

MV 1.6644 0.6871MQ 1.7743 0.8097

A maggior riprova, è stata condotta in maniera analogauna simulazione usando np = 3 nel processo di gener-azione delle potenze e np = 2.12 nella stima MV delladistanza: i risultati sono in figura 38 e in tabella XII, incui si notano errori grandissimi a ulteriore conferma diquanto affermato in precedenza.

.

TABLE XII: Media e varianza di ‖z‖E[‖z‖] [m] Var ‖z‖ [m2]

MV 1.7525 0.6396MQ 2.2374 2.4227


−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ

Stima MRC

(a) Traiettorie reali e stimate

5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

istanti di simulazione

[m]

Stima ML

Stima MQ

Stima MRC

(b) Andamento di ‖z‖

Fig. 25: Confronto fra i tre metodi di stima.

−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima MRC (wj ∝ d1j )

Stima MRC (wj ∝ Var d1j )


5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

3

3.5


[m]

Stima MRC (wj ∝ d1j )

Stima MRC (wj ∝ Var d1j )


Fig. 26: Confronto fra stime MRC usando diversi combinatori.


−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

2

4

6

8

10

12


[m]

Stima ML

Stima MQ


Fig. 27: Stime con range 4 [m].

−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2


[m]

Stima ML

Stima MQ




−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

3


[m]

Stima ML

Stima MQ



−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

3

3.5


[m]

Stima ML

Stima MQ


Fig. 30: Stime con range = 10 [m].


−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5


[m]

Stima ML

Stima MQ


Fig. 31: Stime con NmeanMax = 20.

−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2


[m]

Stima ML

Stima MQ




−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8


[m]

Stima ML

Stima MQ



−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8


[m]

Stima ML

Stima MQ




−4 −2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

1

2

3

4

5

6


[m]

Stima ML

Stima MQ


Fig. 35: Stime con Nnodes = 6.

0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6


[m]

Stima ML

Stima MQ


Fig. 36: Stime con Nnodes = 15.


−2 0 2 4 6 8 10 12

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

3

3.5

4


[m]

Stima ML

Stima MQ


Fig. 37: Stime con parametro A reale diverso da quello usato per la stima della distanza.


−4 −2 0 2 4 6 8 10 12

−2

0

2

4

6

8

10

12

[m]

[m]

Nodi

Target

Stima ML

Stima MQ


5 10 15 20 25 30 35 40 45 500

1

2

3

4

5

6

7

8

9

10


[m]

Stima ML

Stima MQ


Fig. 38: Stime con parametro np reale diverso da quello usato per la stima della distanza.


VI. SOFTWARE I - NESC

P er testare sui TMOTESKYr l’algoritmo principaledi localizzazione, visto al capitolo IV, sono stati

scritti due module, e le due relative configuration:

1) AnchorNodeP.nc per i nodi fissi;2) MobileNodeP.nc per il nodo mobile.

Entrambi i moduli fanno però riferimento ad un C++header file comune, Localization.h al fine di con-dividere costanti e tipi di messaggi.In questo capitolo verranno illustrati i codici sorgenti,trattandone l’implementazione e le finalità, in mododa chiarire come opera l’algoritmo in real-time neiTMOTESKYr. Nel capitolo VII verrà presentato inveceil client JAVA realizzato sia per fornire un tool di basecompleto all’utente finale sia per utilizzarlo come debug-ger, in sostituzione al simulatore TOSSIM del TINYOS.Inizialmente è stato utilizzato per la programmazione ilsistema operativo XUBUNTOS, ovvero la versione 6.10di XUBUNTU corredata dei pacchetti del TINYOS 2.0.1(più il repository CVS del TinyOS 1.x) preinstallati.Potendo usarlo anche come LINUX live CD e basandosisu una versione compatta di UBUNTU con un windowmanager XFCE si era dimostrato un’ottima soluzione.Purtroppo durante il development si è danneggiata lapostazione di lavoro, un Presario X1000 - Pentium M1.3 Ghz - DDR SDRAM 256 MB, e migrando su unToshiba A100-170 - Core Due Duo 2.0 Ghz - DDR22000 MB, quindi non è stato possibile installare corret-tamente XUBUNTOS con il dual-boot, a causa di bug diXUBUNTU 6.10.Si è migrati dunque in UBUNTU FEISTY, configurandoil sistema e installando i package necessari seguendo leistruzioni documentate in [23].

A. Header file

Poiché durante la descrizione dei sorgenti verrannorichiamate spesso le costanti e le tipologie di messaggiutilizzate, in questa sezione ci si propone di elencarle edescriverle in modo da poter far facilmente riferimentoad esse nel prosieguo della trattazione. Dato che nelleTinyOS Extension Proposal viene consigliato uno stan-dard di programmazione, nella redazione del codice cisi è attenuti alle coding conventions specificate in [24].

Lo schema di figura 39 ritrae le modalità di comuni-cazione e il direzionamento dei messaggi implicati.

Fig. 39: Interchanging dei messaggi tra gli applicativi.

Ipotizzando di prender in considerazione i messaggisecondo l’ordine temporale con cui vengono coinvoltinella trasmissione, il primo ad essere chiamato in causaè il mote_ctrl_msg. Questo messaggio viene inviatotramite USB (RS232) dall’utente al nodo mobile peravviare o terminare la procedura di localizzazione.

1) mote_ctrl_msg:

• nx_uint8_t work: start/stop del mote.

Un segnale di stop ovviamente interromperebbe ognicomunicazione in corso, viceversa, uno start forzerebbeil nodo mobile ad iniziare un nuovo ciclo dell’algoritmo.Ponendoci in quest’ultimo caso il nodo mobile inviaimmediatamente un ping_pc_msg alla piattaforma acui è collegato sia per avvisare il client JAVA che staper partire il processo di localizzazione sia per inviarealcune informazioni di configurazione del mote.


2) ping_pc_msg:

• nx_uint8_t pkgId: ID del pacchetto inviato;• nx_uint16_t broadcastNum: numerazione

dei broadcast effettuati;• nx_uint8_t mobileNodeId: ID del mote;• nx_uint8_t power: potenza di trasmissione del

nodo mobile;• nx_uint8_t channel: frequenza di trasmis-

sione del nodo mobile.

Dopo aver allertato il front-end, il nodo mobile iniziaa trasmettere in broadcast, via wireless, un numerospecifico di ping, definiti come ping_node_msg.

3) ping_node_msg:

• nx_uint16_t pkgId: ID del pacchetto inviatoin broadcast.

A questo punto i nodi fissi, nei limiti della portata delsegnale radio, ricevono i ping_node_msg e comin-ciano a compiere le operazioni di filtraggio. I mes-saggi che presentano un RSS e un LQI entro le soglieprestabilite vengono considerati idonei e quindi vengonosalvati in una coda come ping_acpt_msg.

4) ping_acpt_msg:

• nx_uint16_t pkgId: ID del pacchetto inviatoin broadcast;

• nx_int8_t rss: RSS [dBm].

Compiuto il calcolo della stima M.V. della distanza i nodifissi impacchettano i risultati in un data_msg che vienespedito in broadcast al nodo mobile. Il mote a sua voltalo inoltrerà al client, che potrà completare le operazioninecessarie per la formazione della cella e per la stimadella posizione del mote, chiudendo così la catena dieventi che costituiscono l’algoritmo di localizzazione.

5) data_msg:

• nx_uint16_t nodeId: ID del nodo fisso;• nx_uint8_t pkgAcpt: numero di pacchetti che

superano il filtraggio RSS-LQI;• nx_int16_t averageRss: valor medio

dell’RSS dei pacchetti ricevuti ed accettati [dBm];• nx_uint32_t dHat: distanza stimata del nodo

fisso dal nodo mobile [m];• nx_uint8_t power: potenza di trasmissione del

nodo fisso [dBm];

• nx_uint8_t channel: frequenza di trasmis-sione del nodo fisso.

Dato che i nodi si comportano come fossero delle mac-chine a stati finiti si è pensato di circoscrivere ognunadelle specifiche condizioni di lavoro entro un campo diesecuzione legato ad una variabile di stato. Cosicché inodi fissi sono caratterizzati dall’ enum state_a_t:

AUDIT = 4: ricezione dei ping_node_msg;ESTIMATION = 5: stima della distanza;SEND = 6: invio dei data_msg al nodo mobile.

mentre il nodo mobile è caratterizzato dall’enumstate_m_t:

SEND_PC = 2: invio dei ping_pc_msg;SEND_NODE = 3: invio dei ping_node_msg;AUDIT_NODE = 4: ricezione dei data_msg;IDLE = 5: quiete;START_MN = 0xA: segnale di start;START_MN = 0xB: segnale di stop;WAIT_CMD = 0xC: attesa di uno user command.

Le numerose costanti definite nell’header sono tutteracchiuse in un’unica enum preferibile alla macro#define solitamente usata in C++. Tra queste vi sonoi parametri di configurazione della radio CC2420:

CHANNEL_RADIO = 4: livello frequenza;POWER_RADIO = 31: livello potenza;RSSI_OFFSET = -45: offset RSSI [dBm];

inoltre vi sono gli identificativi degli ActiveMessage,ovvero i dispatch identifier dei protocolli per permetterea più servizi di usare un protocollo in maniera indipen-dente:

AM_PING_PC_MSG = 83;AM_PING_NODE_MSG = 84;AM_DATA_MSG = 85;AM_MOTE_CTRL_MSG = 86;

e, infine, le soglie per il filtraggio della potenza:

LQI_BOUND = 103: [dBm];RSS_BOUND = -80: [dBm].

Le rimanenti costanti derivano da uno studio a prioridei range entro i quali devono compiersi le varie fasidell’algoritmo di localizzazione. Le assegnazioni dei val-ori sono state fatte tenendo presente il numero massimodi nodi fissi che andranno presumibilmente a comporre


la cella, supposto pari a N_MAX_NODI = 6 nel worstcase. Questa procedura è stata adottata per far sì che an-che nell’ipotesi di massimo traffico della rete non si creioverlapping tra le tempistiche, che potrebbero causareuna perdita dei dati o un comportamento anomalo delsistema.

TIMER_BROADCAST = 1000: durata di un ciclocompleto dell’algoritmo di localizzazione [ms];TIMER_SEND_PING_PC = 25: periodo di ripe-tizione dell’invio dei ping_pc_msg [ms];TIMER_SEND_PING_NODE = 15: periodo diripetizione dell’invio dei ping_node_msg [ms];TIMER_SEND_DATA = 8: periodo di ripetizionedell’invio dei data_msg [ms];DELAY = 45: ritardo legato al tempo di attesa perpassare allo stato ESTIMATION;CUT_RAND_DELAY = 0x3F: riduzione delritardo casuale nell’invio dei data_msg

all’intervallo 0 : 63 [ms];MAX_PING_PC_MSG = 1: numero massimo diping_pc_msg da inviare;MAX_PING_NODE_MSG = 45: numero massimodi ping_node_msg da inviare;MAX_DATA_MSG = 3: numero massimo didata_msg da inviare al nodo mobile per ciascunnodo fisso;MIN_ACPT_MSG = 10: numero minimo diping_acpt_msg da accettare per considerareattendibile la stima;MAX_FAIL_DATA_MSG = 15: numero massimodi fallimenti nell’inviare i data_msg al mote;QUEUE_PING_NODE_SIZE = 50: dimensionedella coda FIFO per i ping_node_msg;QUEUE_DATA_SIZE = 40: dimensione dellacoda FIFO per i data_msg.

B. Mobile node NesC module

Per descrivere l’implementazione del module

MobileNodeP, conviene simulare un normalefunzionamento delle routine coinvolte nell’algoritmo dilocalizzazione, per comprendere così in maniera piùchiara la funzione ricoperta da ognuna di esse. In figura40 viene proposto lo schema della temporizzazione

per un ciclo completo dell’algoritmo, della durata diTIMER_BROADCAST [ms], confrontando sulla stessascala temporale le modalità operative dei nodi fissi, delnodo mobile e della piattaforma dell’utente. Lo schemadi figura, se pur completo, risulta semplificato in quantoè privo dell’indicazione dei passaggi di stato e non ponein evidenza l’aleatorietà legata all’esecuzione di alcunieventi. E’ comunque significativo per comprenderel’evoluzione temporale dei processi che vanno acostituire l’algoritmo principale.

Nella descrizione del codice sorgente non si faràmenzione dei moduli del TINYOS su cui si appoggiaMobileNodeP per poter usufruire di particolarieventi o comandi: essi sono parte integrante del file diconfigurazione MobileNodeC, il cui scopo è delinearesia al programmatore che al compilatore come sonoconnesse fra di loro le varie componenti.

All’accensione del nodo mobile, o al RESETdel sistema, il TINYOS avvia la sequenza diboot. Nella funzione booted() dell’interfacciaBoot vengono inizializzate le periferiche el’ambiente, portando il mote nello stato IDLE eWAIT_CMD ovvero nell’attesa di ricevere il comandoSTART_MN dall’utente. Viene inoltre impostata aCHANNEL_RADIO la frequenza di trasmissione,utilizzando il comando setChannel(uint8_t)

dell’interfaccia CC2420Config. Tale cambiamento diconfigurazione deve essere sincronizzato con l’hardwaredella radio, mediante il comando sync(). Se l’eventosyncDone(error_t) segnala che l’operazione èavvenuta con successo vengono avviate in successione laradio e la comunicazione seriale, invocando per entrambeil comando start() dell’interfaccia SplitControl.Se tutte le operazioni avvengono correttamente siottiene che tutti i led del mote sono accesi, in casocontrario è sufficiente che un led qualsiasi sia spentoper segnalare che vi è un problema nell’inizializzazionedelle periferiche.Supponendo che tutte le notifiche abbiamo esito positivo,una call al setPower(message_t*, uint8_t)

dell’interfaccia CC2420Packet, permette di settare aPOWER_RADIO la potenza con cui il mote trasmetterà


i ping_node_msg. Dopo questa operazione il nodomobile si mette in attesa di un comando da parte dallato client.Quando il mote riceve uno START_MN, vieneavviato il Timer<TMilli> che periodicamenteogni TIMER_BROADCAST [ms] lancia il proprioevento fired(). Dopo che sono trascorsi i primiTIMER_BROADCAST, [ms] parte dunque a tutti glieffetti l’algoritmo, con un fired() che prevede di:

• porre lo stato corrente a SEND_PC;• azzerare i vari contatori, i.e. gli ID, dei pacchetti;• spegnere i led;• incrementare di una unità il numero del broadcast;• fermare il timer dell’invio dei data_msg, se attivo;• avviare il timer che ogni TIMER_SEND_PING_PC

[ms] invia un ping_pc_msg alla piattaforma con-nessa al mote.

Allo scadere dei TIMER_SEND_PING_PC [ms] ilPC viene informato ripetutamente dell’avvio del pro-cesso di localizzazione, per un numero di volte pari aMAX_PING_PC_MSG. Questa operazione viene compiu-ta postando il task sendPingPcMsg() che inoltra imessaggi alla porta seriale.

Dopodiché il mote passa nello stato SEND_NODE,ferma il timer dei ping_pc_msg con il comandostop() e avvia il Timer<TMilli> che si occupadi spedire in broadcast MAX_PING_NODE_MSG mes-saggi ogni TIMER_SEND_PING_NODE [ms]. Nuo-vamente l’invio è gestito da un task, in questocaso sendPingNodeMsg(), che viene periodicamentepostato dal timer, fintantoché non sono terminati imessaggi previsti. Quando il nodo mobile finisce ilpinging il suo stato diviene AUDIT_NODE e il timerdell’operazione precedente viene fermato, permettendocosì al mote di mettersi in attesa dei data_msg.Dopo un tempo necessario ai nodi fissi per stimarela distanza dal mote e formare una cella preliminare,il nodo mobile comincia a ricevere i data_msg.Il receive è accompagnato dalla memorizzazione deimessaggi in una coda FIFO Queue<data_msg> didimensione QUEUE_DATA_SIZE e dall’invio ogniTIMER_SEND_DATA [ms] degli stessi alla seriale. IlTimer<TMilli> adibito alla trasmissione dei data_msg

al client non fa altro che un posting ripetuto del tasksendDataMsg(), il quale completa a tutti gli effettil’inoltro dei messaggi solamente se la coda non è statagià svuotata in una precedente spedizione. Il mote per-mane nello stato AUDIT_NODE finché non scatta il timerrelativo al TIMER_BROADCAST [ms], istante in cui ilnodo mobile ritorna alle condizioni iniziali, pronto periniziare un nuovo processo di localizzazione.A sua discrezione l’utente può fermare in ogni momentol’esecuzione dell’algoritmo comandando al mote unoSTOP_MN: immediatamente vengono fermati tutti i timere il nodo mobile entra nello stato IDLE.

C. Anchor node NesC module

Similmente a quanto visto in VI-B, per descriverel’implementazione del module AnchorNodeP

conviene simulare un normale funzionamento delleroutine coinvolte nell’algoritmo di localizzazione.All’accensione del nodo fisso, o al RESET delsistema, il TINYOS avvia la sequenza di boot. Nellafunzione booted() dell’interfaccia Boot vengonoinizializzate le periferiche e l’ambiente, portandoil nodo nello stato AUDIT ovvero nell’attesa diricevere un ping_node_msg dal nodo mobile,tramite contatto radio. Viene inoltre impostata aCHANNEL_RADIO la frequenza di trasmissione e,se l’evento syncDone(error_t) segnala che lasincronizzazione ha avuto successo, vengono avviate insuccessione la radio e la comunicazione seriale.Supponendo che tutte le notifiche abbiamo esitopositivo, viene impostata a POWER_RADIO la potenzacon cui il nodo fisso trasmetterà i data_msg. Dopoquesta operazione il nodo fisso è definitivamente prontoper la ricezione dei messaggi.Quando il mote riceve i ping_node_msg ricavada essi l’RSSI, shiftato di RSSI_OFFSET, el’LQI, mediante i comandi getRssi(int8_t)

e getLqi(int8_t) dell’interfaccia CC2420Packet.I messaggi che hanno valori di RSSI e LQI superiori allerispettive soglie RSS_BOUND e LQI_BOUND vengonomemorizzati in una coda Queue<ping_acpt_msg>,di dimensione QUEUE_PING_NODE_SIZE,come ping_acpt_msg. Dopo un tempo pari a


TIMER_SEND_PING_NODE*MAX_PING_NODE_MSG

+ DELAY - γ(loss) associato al comandostartOneShot(uint32_t) di un Timer<TMilli>,viene avviata la stima della distanza. γ(loss) è unafunzione nota che dipende linearmente dall’ID delprimo ping_node_msg accettato; questa funzioneserve per poter valutare accuratamente l’istante incui il nodo mobile ha inviato il ping_node_msg,così da poter prevedere quando dovrà arrivare l’ultimodei MAX_PING_NODE_MSG e poter di conseguenzainiziare la computazione della stima della distanza.Al verificarsi dell’evento fired() il nodo fissopassa nello stato ESTIMATION e calcola il valormedio di tutti gli RSS dei ping_acpt_msg salvatinella coda. Questo valore viene passato al comandodistanceEstimation(int16_t) che calcola lastima di M.V. della distanza, secondo l’equazione (9).I parametri che caratterizzano il canale sono dichiaraticome #define all’inizio dell’implementazione, nonpotendo essere usati come enum essendo alcuni infloating point. Essi sono:

• D_ZERO 1: distanza di riferimento d0 [m];• P_TX 0: potenza di trasmissione PTX [dBm];• A -56: attenuazione del canale [dBm] tarata du-

rante la fase di testbed;• POWER_D_ZERO (P_TX+A): potenza di trasmis-

sione P (d0) [dBm];• N_P 2.12: fattore di decrescenza della potenza.

Il risultato restituito dalla formula (9) è solitamente unnumero in virgola mobile: non potendo essere trasmessocome float al PC, poiché i tipi di dato supportati dalTINYOS per le comunicazioni sono interi unsigned,viene shiftato di una quantità pari a SHIFT_ROUND

sufficiente per poterlo castare a uint32_t senzaperdita di precisione dovuta a eventuali arrotondamenti.Tale stratagemma presuppone però che a valle, nel latoclient, il dato sia poi riconvertito a float applicandola trasformazione inversa.Disponendo della distanza il nodo fissopassa allo stato SEND e chiama un’altrostartOneShot(uint32_t) che ha il compitodi avviare il sending dei data_msg al nodo

mobile. L’istante in cui avviene la spedizione èdeterminato in maniera aleatoria assegnando un valoretemporale con il comando rand16() dell’interfacciaRandom, dopo averlo filtrato in maniera bitwise di unCUT_RAND_DELAY, per fare in modo che il rangeprobabilistico sia compreso tra 0 ÷ 63 [ms]. Questatecnica viene adottata per evitare che tutti i nodiappartenenti alla cella mandino i propri data_msg

contemporaneamente, cosicché venga ridotta lapossibilità di collisione fra i dati.Allo scadere del timer, il nodo fisso controlla se ilnumero di messaggi accettati è superiore alla sogliaminima MIN_ACPT_MSG: in caso affermativo vienechiamato il task sendDistance() che provaad inviare un numero pari a MAX_DATA_MSG

di data_msg con un limite massimo diMAX_FAIL_DATA_MSG tentativi, prima di tornareallo stato AUDIT. Se non è stato validato unnumero sufficiente di messaggi il nodo fisso ritornaimmediatamente allo stato AUDIT escludendosi dunquedalla cella, rimanendo pronto per il successivo broadcast.


Inv

io

Da

taM

sg

AU

DIT

_TIM

E

0

0

� �

TIM

ER

_BR

OA

DC

AS

T

Sti

ma

Po

siz

ion

e

Ric

ez

ion

e

Da

taM

sg

Ric

ez

ion

e

Pin

gP

cM

sg

� ��

Inv

io

Pin

gP

cM

sg

Sti

ma

Dis

tan

za

Ric

ez

ion

e

Pin

gN

od

eM

sg

TIM

ER

_SE

ND

_PIN

G_P

C

TIM

ER

_SE

ND

_PIN

G_N

OD

E *

MA

X_P

ING

_NO

DE

_MS

G

Ric

ez

ion

e/

Inv

io

Da

taM

sg

Inv

io

Pin

gN

od

eM

sg

� ��

� ��

TIM

ER

_SE

ND

_PIN

G_N

OD

E *

MA

X_P

ING

_NO

DE

_MS

G -

��

+ D

EL

AY

ran

d1

6()

& C

UT

_RA

ND

_DE

LA

Y

An

ch

or

No

de

Mo

bile

No

de

P

oc

ke

t

PC

� ��

[m

s]

� ��

[m

s]

� ��

[m

s]

Fig. 40: Temporizzazione dell’algoritmo di localizzazione.


VII. SOFTWARE II - JAVA

C on l’obiettivo di fornire all’utente un’interfacciasemplice e comoda per il monitoraggio e il settag-

gio del sistema si è pensato di realizzare un frame JAVA.Un JFrame è sostanzialmente una applicazione con-cettualmente simile alle form realizzate in VISUAL C++,che per essere eseguita deve essere collocata all’internodel classico metodo statico main(String[]).Questa scelta è stata motivata da una serie di vantaggiche andavano a riflettersi positivamente sia sullo stadiodi sviluppo sia sulla sintesi del prodotto finale. Tra lenote positive figurano:

• la buona conoscenza del linguaggio di program-mazione JAVA da parte del progettista, che ha per-messo di rendere esigui i tempi di apprendimentoa favore di una accurata fase di debugging e dimiglioramento dell’applicativo;

• la possibilità di lavorare in un worst case com-putazionale, essendo JAVA più oneroso in terminidi risorse rispetto ad altri software real-time o dicalcolo numerico, al fine di testarne i limiti difunzionamento;

• la sicurezza, la semplicità, l’orientazione aglioggetti e la ricca libreria standard che rendono JAVA

un ottimo prodotto didattico;• la trasferibilità fornita dalla JAVA VIRTUAL MA-

CHINE, concretizzata nella possibilità di utilizzareil medesimo software su piattaforme diverse, WIN-DOWS o UNIX.

In previsione di sviluppi futuri, prima di proseguirecon i dettagli implementativi del software verrà fornitoun breve how-to sulla gestione del progetto, intesa comeorganizzazione dell’ambiente di lavoro, per consentireuna facile utilizzazione e/o modifica dell’applicativo.

A. Project managment

Per la programmazione in JAVA è stato utilizzata laJ2SE 1.5.0.06 con sistema operativo UBUNTU FEISTY,su NETBEANS 5.5.1, un ottimo IDE (Integrated Deve-lopment Environment) gratuito.La scelta dell’IDE è ricaduta su NETBEANS in quantotale ambiente è fornito di un GUI Builder che permette

di creare in maniera molto intuitiva il layout del frame,similmente al QT DESIGNER per il linguaggio C++.Per un efficace gestione del lavoro NETBEANS prevededi creare un progetto, il quale è sostanzialmente una rootdirectory, coordinata da alcuni .xml file, che raggruppauna serie di sottodirectory con ruoli specifici:

• build: contiene tutti i file .class generati in fasedi compilazione, in ordine gerarchico a seconda delpackage di appartenenza;

• dist: contiene l’eventuale file .jar, accompag-nato dalle librerie necessarie non presenti nei pack-age standard di JAVA, pronto per essere distribuitoo eseguito;

• src: contiene tutti i file sorgenti JAVA, automati-camente predisposti in ordine gerarchico a secondadel package di appartenenza e eventuali altri cartelleper file multimediali o di corredo.

Sulla base di ciò si è partiti col creare un progetto,chiamato Localizer, sfruttando la scheletratura di unGUI Form Example offerto da NETBEANS, accessibiledal menu File → New Project → Samples → General.Attualmente il JFrame, battezzato TESEO, è distribuitosu 9 sorgenti JAVA interni al package principale, de-nominato anch’esso teseo, per un totale di circa3000 code line. A questo package ne fa capo un al-tro, mlfunction, che raggruppa altri 12 sorgenti checostituiscono il cuore dell’algoritmo di localizzazione,descritto nella sezione IV, per un totale di circa 2000code line. All’interno di teseo permangono due di-rectory, img, che contiene dei file immagine funziona-li all’interfaccia grafica, e maps, la cui finalità verràchiarita nel paragrafo VII-C.Una volta impostato l’ambiente di lavoro dell’IDE sipossono compilare i sorgenti premendo semplicementeF11, che afferisce a Build → Build Main Project eeseguire il main(String[]) tramite F6 che afferiscea Run → Run Main Project.

Per scindere il progetto dall’IDE, in modo da venireincontro ad eventuali programmatori che non hannofamiliarità con NETBEANS, è stata creata una gerarchiadi directory parallela a quella dell’IDE e sono statiscritti degli script per bash Linux per facilitare la compi-lazione e l’esecuzione del programma principale. Nella


medesima root directory utilizzata per NETBEANS fannodunque capo le seguenti cartelle:

• classes: contiene tutti i file *.class generati infase di compilazione, in ordine gerarchico a secondadel package di appartenenza;

• lib: contiene le librerie necessarie non presenti neipackage standard di JAVA;

• src: appositamente identica a quella di NET-BEANS, svolge la stessa funzione per permetteredi modificare i sorgenti sia tramite IDE sia conqualunque altro editor JAVA.

Gli script menzionati si trovano nella root directory esono i seguenti:

1) make.sh: imposta il CLASSPATH per il re-perimento delle librerie aggiuntive e invoca ilcomando make di Linux che fa riferimento alMakefile per la compilazione di tutti i sorgentie la generazione del pacchetto Teseo.jar. Conun make clean si ha la possibilità di rimuoveretutti i .class compilati;

2) run.sh: imposta il CLASSPATH per il reperi-mento delle librerie aggiuntive e invoca il comandojava per l’esecuzione del programma.

Il file compresso .jar (Java Archive) è predispostoper contenere il bytecode necessario per eseguire ilframe, i file multimediali e i file di configurazionedel software. Per eseguire il progetto direttamente dallacommand line tramite il file Teseo.jar è sufficientedigitare il comando java -jar "Teseo.jar" dalladirectory che lo contiene.

B. Implementazione del frame

In questa sezione verrà esposto il source code relativoal frame, sottolineandone gli aspetti fondamentali.Va precisato che grazie al tool Javadoc5 è possibilerealizzare una chiara e completa documentazione HTMLdel codice JAVA. Questi file HTML rendono agevolela comprensione del codice che compone il frame,perciò un programmatore sarebbe tenuto a corredare i

5NETBEANS dispone di una procedura guidata e automatica perla creazione della documentazione, accessibile dal Build → GenerateJavadoc for Project.

sorgenti con tutti i commenti necessari. Attualmente ilprogetto non è conforme al Javadoc, pertanto per gliapprofondimenti tecnici e dettagliati del codice si invitaalla consultazione dei paragrafi VII-C e VII-D.Il package teseo è composto dai seguenti files .java:

• Teseo: JFrame, entry point del software client;• MapPanel: JPanel che gestisce, come Thread,

la visualizzazione degli elementi grafici all’internodella mappa corrente;

• Constants: interfaccia contenente tutte le costanti;• DataMsg: interfaccia al tipo di messaggioDataMsg che fa riferimento alla nx_struct

data_msg definita nel C++ header del softwaredei TMOTESKYr e descritta al paragrafo VI-A;

• MoteCtrlMsg: interfaccia al tipo di messag-gio MoteCtrlMsg che fa riferimento allanx_struct mote_ctrl_msg definita nel C++header del software dei TMOTESKYr e descritta alparagrafo VI-A;

• PingPcMsg: interfaccia JAVA al tipo di messaggioPingPcMsg che fa riferimento alla nx_struct

ping_pc_msg definita nel C++ header del soft-ware dei TMOTESKYr, descritta al paragrafo VI-A;

• Node: oggetto volto a definire un nodo, sia mobile ofisso. Esso è costituito da un insieme di coordinate,che possono essere bidimensionali, Coordinate2D,o tridimensionali, Coordinate3D. Inoltre è costi-tuito da un identificativo di tipo int e dal numerodella stanza in cui è posizionato;

• About: JPanel, accessibile dal menu del JFrame,contenente la finestra di informazioni del software.

Le classi DataMsg, MoteCtrlMsg, PingPcMsg vengonogenerate automaticamente dal MIG tramite il Makefilepresente nella directory src. Esse devono essere dunqueaggiunte al package in una seconda istanza, modificandoi file ivi generati.Il package teseo.mlfunction è composto daiseguenti files .java:

• Coordinate2D: coordinate bidimensionali;• Coordinate3D: coordinate tridimensionali;• MLfunction: implementa la funzione multivariabile


da minimizzare nella stima di M.V. della posizionedel nodo mobile (14), fornendo tutti i parametrinecessari per la minimizzazione;

• ConjugateGradientSearch: estensione di Multi-variateMinimum, minimizza una funzione a piùvariabili a valori reali usando il gradiente coniu-gato. Nel caso in esame è volta a minimizzarela MLfunction. Sono disponibili diverse modali-tà per l’aggiornamento della direzione (Fletcher-Reeves, Polak-Ribiere, Beale-Sorenson, Hestenes-Stiefel): in questa sede si è optato per il metodoBeale-Sorenson, Hestenes-Stiefel;

• NumericalDerivative: approssima numericamentele derivate prime e seconde di una funzione ad unavariabile e approssima il gradiente e la diagonaledell’Hessiana di funzioni multivariabili;

• MultivariateFunction: interfaccia per una funzionea più variabili;

• MFWithGradient: interfaccia per una funzione apiù variabili con gradiente annesso;

• MultivariateMinimum: classe di base astratta perla minimizzazione di una MultivariateFunction;

• UnivariateFunction: interfaccia per una funzionead una variabile;

• UnivariateMinimum: classe di base astratta per laminimizzazione di una UnivariateFunction a valorireali senza l’uso delle derivate;

• LineFunction: classe che converte una Multivaria-teFunction in una UnivariateFunction;

• MachineAccuracy: classe volta a determinarel’accuratezza della macchina che deve svolgere ilcalcolo numerico;

Tutti i file del package teseo.mlfunction, ad ec-cezione di MLfunction, Coordinate2D, Coordinate3D,sono opera di Korbinian Strimmer, del PAL DevelopmentCore Team © 1999-2001, e sono distribuiti in accordoalle condizioni poste dalla LGPL (Lesser GNU GeneralPublic License), allegata al medesimo package.

In figura 41 è riportato lo schema delleinterconnessioni tra le varie classi. Le linee continuerappresentano le associazioni; le realizzazioni sonoevidenziati in verde, mentre le interfaccie in azzurro.Il diagramma è abbastanza coercitivo in quanto sono

escluse dal contesto le User Interface & Base Libraries.

1) Le librerie della GUI: Il frame, in ogni sua parte,usufruisce degli User Interface Toolkits. Gli UIT sonoattualmente due: AWT e SWING. La storia di questipackage è legata da un filo comune perciò in questasezione se ne evidenziano le affinità e attributi, in mododa rendere inequivocabili le funzionalità.

Al rilascio della versione 1.0 JAVA conteneva una classlibrary per la programmazione di interfacce grafiche,battezzata Abstract Window Toolkit (AWT). L’AWT dele-ga ai toolkit nativi su ogni target platform (WINDOWS,LINUX, MAC ...) la creazione e la gestione del com-portamento degli elementi presenti nella GUI: per ognipiattaforma ci sono dei peer object equivalenti aglioggetti AWT. Questo criterio si adattò egregiamentead applicazioni abbastanza semplici, ma divenne prestochiaro che era diabolicamente complicato scrivere unalibreria grafica portabile e di alta qualità che dipendessedagli elementi della native UI. Nel 1996 NETSCAPE creò(IFC), Internet Foundation Classes, una GUI library cheusava un approccio totalmente differente: gli elementidell’interfaccia grafica venivano disegnati all’interno difinestre vuote. L’unica funzionalità peer richiesta era ilmodo in cui costruire le finestre e dipingere in esse.Successivamente, in collaborazione con SUN, nacqueSwing, la libreria ufficiale per il GUI toolkit, non-peer-based, che è parte delle Java Foundation Classes.

I motivi per scegliere Swing sono ragguardevoli:

• ha un insieme di elementi, per le user interface, piùricco e conveniente;

• dipende molto meno dalla piattaforma, per cui èmeno incline ai bugs specifici della underlyingplatform;

Swing non ha rimpiazzato completamente l’AWT, infattii componenti peer-based sono ancora disponibili. Disolito gli elementi della libreria Swing si distinguono daquelli AWT per l’aggiunta di una “J” al nome di questiultimi, per cui è semplice effettuarne la conversione6. Nelframe gli oggetti sono praticamente tutti di tipo Swing,

6Ad esempio il frame appartiene alla classe JFrame, della libreriajavax.swing diversamente da Frame, contenuto in java.awt.


Fig. 41: Diagramma UML dei componenti del frame.


fatta eccezione per gli events handling, che sono rimastiinalterati rispetto a JAVA 1.1.

Tra le librerie aggiuntive, non contemplate nella li-breria standard di JAVA e perciò inserite in Properties→ Libraries → Compile di Localizer, figurano duepackage indispensabili:

• swing-layout-1.9.jar: contiene i file.class adoperati da NETBEANS per semplificarela creazione del layout, pertanto tale libreriaè presente di default al progetto, provvedendoNETBEANS stesso al suo linking. Del pacchettoviene estensivamente utilizzata la classeGroupLayout, un LayoutManager che raggruppagerarchicamente i componenti per realizzare ilayout più o meno comuni;

• tinyos.jar: contiene i file .class utiliper comunicare con i TMOTESKYr, siaa livello di protocolli che di applicativi.Tale libreria è reperibile dalla directory/opt/tinyos-2.x/support/sdk/java

dopo aver installato il TinyOS 2.x. Si trattadi file JNI (Java Native Interface), poiché lalibreria standard di JAVA non supporta le featureespressamente dipendenti dalla piattaformaTMOTESKYr. Diviene necessario quindi usarele JNI per poter scrivere metodi JAVA nativi, pergestire quelle situazioni che si presentano quandouna applicazione non può essere scritta interamentein JAVA. Tra i package presenti nel tinyos.jarsi fa riferimento principalmente a:

– net.tinyos.message.* che permette diconvertire byte array in pacchetti TINYOS

2.0r astratti. Esso è inteso per essere usato inassociazione al codice JAVA generato da MIG;

– net.tinyos.packet.* che offreastrazioni per la lettura e la scrittura di datamessage per differenti fonti di comunicazione,specie quella seriale.

2) Il multithreading e i timer: Prima di addentrarcinelle singole classi realizzate è utile capire come JAVA

gestisce la programmazione concorrente.

Diversamente dai linguaggi single-threaded, come

C/C++, che devono effettuare chiamate alle primitive delsistema operativo, JAVA contiene già queste primitive alsuo interno, ovvero dispone del multithreading.Anche se JAVA è probabilmente il linguaggio di pro-grammazione più portabile attualmente in uso, il multi-threading è un meccanismo che dipende dall’architetturadel sistema, in particolare ci sono delle differenze trala piattaforma SOLARIS e la piattaforma WIN32. Perentrambe le piattaforme si usa una schedulazione ditipo preemptive. La differenza sta nell’esecuzione deithread aventi pari priorità: WINDOWS adotta la schedu-lazione round robing sfruttando dei timeslice predefinitie quindi i thread vengono eseguiti a turno soltanto peril loro tempo predefinito (quanto), mentre SOLARIS

è un sistema senza timeslicing, dove un thread vienenormalmente eseguito fino al proprio completamento.

Ogni applet o applicazione JAVA è di tipo multi-threader. Ogni thread ha una priorità che può essereimpostata con il metodo setPriority(int) ed èrappresentata da un intero che va da 1 (minima) a 10(massima). E’ compito dello scheduler di JAVA gestire ivari thread mantenendo in esecuzione quello a prioritàmaggiore o eseguire a turno quelli di pari priorità sedisponibile il timeslicing. Per i sistemi come SOLARIS,è possibile utilizzare la chiamata al metodo yield perdare la possibilità ad altri thread di pari priorità di essereeseguiti.JAVA utilizza dei monitor per eseguire la sincroniz-zazione dei thread. Ogni oggetto che possiede metodisynchronized è un monitor. Tali monitor permettonoad un thread per volta di eseguire un metodo syn-chronized sull’oggetto; per fare questo l’oggetto vienebloccato quando viene invocato tale metodo e sbloccatoal termine dell’esecuzione dello stesso.JAVA ha inoltre un supporto built-in, per prevenire col-lisioni a livello di risorse, racchiuso proprio nella key-word synchronized. Essa si comporta similmente ad unSemaphore: quando un thread vuole eseguire un pezzodi codice salvaguardato dalla keyword synchronizedcontrolla prima se il semaforo è disponibilie e in casoaffermativo lo acquisisce, eseguendo il codice, per poirilasciarlo.

Un’importante classe relazionata al multithreading è


la classe Timer. Essa consente di schedulare vari taskper eseguirli in futuro, una volta sola o ripetutamentead intervalli regolari. In corrispondenza ad ogni oggettoTimer vi è un singolo thread che è utilizzato per eseguiresequenzialmente in background tutti i task del timer.Dopo che tutti gli outstanding task hanno completatola loro esecuzione, termina anche il thread associatoai task, divenendo soggetto alla garbage collection.Va sottolineato che questa classe è thread-safe: threadmultipli possono condividere un singolo Timer senzarichiedere una sincronizzazione esterna. Inoltre questaclasse non offre garanzie di real-time, poiché schedula itask utilizzando il metodo Object.wait(long).

3) Metodi numerici per il calcolo del minimo diuna funzione: Un problema di minimizzazione comequello per la stima ML della posizione (13) viene risoltoattraverso metodi numerici, tipicamente con i metodidel gradiente. Questi si basano su un’approssimazionequadratica della funzione f da minimizzare del tipo

f(x) = xT Ax− bT x + c + o(‖x‖2) (20)

con A matrice simmetrica definita positiva. Trascurandoi termini oltre il second’ordine, si ottiene facilmente ilgradiente di f come

∇f = Ax− b (21)

dalla simmetria di A: la ricerca del minimo per f siriduce a quella dello zero di ∇f , ovvero del vettore x

per cuiAx = b.

Per questo tipo di problema, si consideri la classe diproblemi equivalenti del punto fisso del tipo

x = x+α(x)(b−Ax), α(x) : RN → R, α(x) 6= 0 ∀x

e si consideri l’iterazione semplice

xk+1 = xk + α(xk)(b−Axk) = xk + α(xk)rk

la quale, se converge, converge alla soluzione del sis-tema lineare. Tale metodo è caratterizzato dal fatto cheogni punto della traiettoria xk+1 è raggiunto dal puntoprecedente avanzando nella direzione del residuo. Più in

generale, si considerino iterazioni del tipo

xk+1 = xk + α(xk)pk (22)

dove le direzioni pk sono a loro volta definite attraversoil residuo nel seguente modo

pk = rk + β(xk)pk−1, β(xk) : RN → R.

Soffermiamoci dapprima sulla scelta delle costantiα(xk), che saranno indicate semplicemente con αk. Essepossono venire ricavate, ad ogni passo, in modo da min-imizzare la norma pesata con A dell’errore. Ricordandoche per norma pesata con A si intende

‖z‖2A , zT Az

si tratta quindi di minimizzare al passo (k + 1)-esimo ilfunzionale

Φ(xk+1) , ‖x− xk+1‖2A = (x− xk+1)T A(x− xk+1)

con xk+1 definito in (22). Si ottiene così

Φ(xk+1) = ‖x− xk+1‖2A

= (x− xk − αkpk)T A(x− xk − αkpk)

= (x− xk)T A(x− xk)− 2(αkpk)T A(x− xk)+

+ (αkpk)T A(αkpk)

= ‖x− xk‖2A − 2αkp

Tk rk + α2

k‖pk‖2A

il cui minimo è raggiunto per

αk =pT

k rk

‖pk‖2A

cui corrisponde

Φ(xk+1) = ‖x− xk‖2A −

(pTk rk)2

‖pk‖2A

. (23)

Si osservi che con tale scelta ottimale del parametro αk

si ha, per ogni direzione di discesa pk, un residuo rk+1

ortogonale alla direzione pk stessa: infatti si ha

rk+1 = b−Axk+1 = A(xk + αkpk)− b = rk − αkApk


dalla quale si ricava

pkT rk+1 = pTk (rk − αkApk) = pT

k rk − αkpTk Apk

= pTk rk −

pTk rk

‖pk‖2A

pTk Apk = 0. (24)

E’ interessante considerare l’interpretazione geomet-rica del metodo. Si osservi che l’equazione in z

Φ(z) = (z − x)T A(z − x) = c (25)

rappresenta, al variare di c ∈ R+ ∪ {0}, delle ellissiconcentriche di centro x. In particolare il punto xk dellatraiettoria si trova sull’ellisse

Φ(z) = (xk − x)T A(xk − x) = c. (26)

Inoltre il minimo del funzionale Φ(z) è 0 ed è raggiuntonel punto z = x. Poiché il punto xk+1 è cercato sullaretta s = xk + ξpk , ξ ∈ R, in modo da minimizzare(x − xk+1)T A(x − xk+1), esso si trova sull’ellisse piùinterna tra tutte quelle che intersecano la retta s, cioèsull’ellisse tangente ad s (figura 42).

Inoltre il minimo del funzionale Φ(z) è 0 ed è raggiunto nel punto z=x. Poichè il punto xk+1 è cercato sulla retta s=xk+ξpk , ξ∈R, in modo da minimizzare (x-xk+1)TA(x-xk+1), esso si trova sull'ellisse più interna tra tutte quelle che intersecano la retta s, cioè sull'ellisse tangente ad s.

*x

k

* xk+1

s

*x

Φ =Φ(z) (x )k

Φ (z)=Φk+1

(x )

direzione di rk+1

direzione di pk

Metodo del gradiente (di discesa piu’ ripida). Quando la direzione di discesa è quella del residuo: pk =rk , allora la direzione del passo successivo, che è rk+1 , risulta ortogonale alla precedente, cioe’ ortogonale alla curva di livello nel punto xk+1. Tale direzione è quella del gradiente della funzione Φ(z) nel punto xk+1. Per questo motivo il metodo è detto metodo del gradiente. Va inoltre ricordato che per una qualunque funzione regolare Φ(z), la direzione del gradiente e’ quella di massima pendenza.

dato 0x

per k=0,1,…

kk Axbr −=

2

22

Ak

k

kTk

kTk

kr

r

Arrrr

==α

kkkk rxx α+=+1

86

Fig. 42: Interpretazione geometrica del gradiente.

4) Metodo del gradiente coniugato: Come già detto,nel progetto è stato scelto di usare per la minimizzazionedi (13) il metodo numerico del gradiente coniugato.

Si considerano come si è visto iterazioni del tipo

xk+1 = xk + α(xk)pk

con il parametro α(xk) scelto nel modo ottimale prece-dentemente illustrato. Si imponga ora che la direzione

di discesa al passo k-esimo sia presa nel piano generatodai due vettori pk−1 e rk relativi al passo precedente, chesappiamo essere tra loro ortogonali. Sia dunque, comegià considerato all’inizio del paragrafo,

pk = rk + β(xk)pk−1.

Fissata la direzione iniziale p0 = r0, si tratta di fissareil parametro β(xk) , βk in modo da minimizzare ilfunzionale Φ(xk+1) dato dalla (23). Poiché pk = rk +βkpk−1, esso assume la forma

Φ(xk+1) = ‖x− xk‖2A −

(rTk rk)2

‖pk‖2A

e quindi sarà minimizzato per quel valore che minimizza‖pk‖2

A; in modo diretto si trova

βk = −pT

k−1Ark

‖pk−1‖2A

.

Ferma restando la relazione (24) che stabilisce, ad ognipasso k, l’ortogonalità tra la direzione di discesa pk edil residuo relativo al punto xk+1

pTk rk+1 = 0,

in questo caso si osserva che le due direzioni pk−1 epk sono ortogonali nel prodotto scalare < z,w >A,

zT Ax, cioè sono A-coniugate. Si ha infatti

pTk−1Apk = pT

k−1A(rk + βkpk−1)

= pTk−1Ark + βk‖pk−1‖2

A = 0.

Per questa ragione il metodo prende il nome di metododel gradiente coniugato.

I passi dell’algoritmo sono quindi

1) x0 dato;2) p0 = r0 = b−Ax0;3) per k = 0, 1, . . .

a) αk = pTk rk

pTk Apk

= pTk rk

‖pk‖2A

;b) xk+1 = xk + αkpk;c) rk+1 = −Axk+1 + b = rk − αkApk;d) βk+1 = −pT

k−1Ark

‖pk−1‖2A

= ‖rk+1‖2

‖rk‖2 (norma eu-clidea);

e) pk+1 = rk+1 + βk+1pk.

Si dimostra inoltre che la direzione pk è A-coniugata nonsolo a pk−1 ma a tutte le precedenti direzioni di discesa e


che il residuo rk è ortogonale a tutti i precedenti residui

pTk Api = 0, rT

k ri = 0 ∀i = 0, 1, . . . , k − 1.

Da quest’ultima si evince che il metodo del gradienteconiugato converge in un numero finito di passi nonsuperiore a N .

Si dimostra inoltre che vale la seguente stima tra lenorme degli errori di due passi successivi

Φ(xk+1) ≤

(√K2(A)− 1√K2(A) + 1

)2

Φ(xk)

con K2(A) indice di condizionamento della matrice A

secondo la norma-27: minore è l’indice di condiziona-mento, più rapido è il tempo di smorzamento dell’errore.Può accadere che, per matrici ben condizionate, il nu-mero di iterazioni sufficienti ad ottenere una buonaapprossimazione sia considerevolmente inferiore ad N .

C. Teseo.java

Quando l’utente avvia il frame, dopo aver collegato ilnodo mobile al pc, TESEO entra in esecuzione, invocatodal main(String) che richiama il costruttore delJFrame e visualizza immediatamente il frame, il qualesi presenta come in figura 43.

Fig. 43: Schermata iniziale del frame.

7Si definisce indice di condizionamento Kp di A secondo unanorma-p come Kp(A) , ‖A‖p · ‖A‖−1.

Il costruttore si può considerare come una inizializ-zazione del sistema, suddivisa nelle seguenti fasi:

a Init della form - design side.Il primo passo prevede di chiamare il metodoinitComponents() i cui contenuti sonorelativi alle palette Swing e AWT del frame. Icontenuti vengono sempre rigenerati dal FormEditor di NETBEANS e perciò non possonoessere modificati manualmente. E’ necessarioquindi che initComponents() sia il primometodo ad essere eseguito, onde evitare cheNETBEANS possa modificare impostazioni per-sonalizzate dell’utente, creando conflitti;

b Init della mappa.Il metodo initEnvironment(String)

della classe MapPanel inizializza l’ambientein cui il nodo mobile verrà visualizzato. Senzaindagare al momento i dettagli di questometodo, che saranno descritti nella sezione VII-D, viene riportata in figura 44 una illustrazioneesemplificativa del MapPanel all’avvio;

Fig. 44: Screenshot esemplare del MapPanel.

c Init della form - source side.Con il metodo initMyComponents() sicompleta l’istanziazione delle variabili stretta-mente legate all’interfaccia e si inizializzanoalcune variabili boolean di controllo dei variblocchi condizionali. Vengono inoltre allocatein memoria le istanze globali del JFrame;

d Avvio salvataggio dei dati.


Viene inizializzato il file log.txt su disco,in cui salvare dei dati di log. Questi possonoessere scelti a piacere dal programmatore. At-tualmente il logging si referisce al trace dellaposizione occupata dal nodo mobile nei diversiistanti temporali. Se il sistema operativo è unaversione di WINDOWS il file verrà memoriz-zato sul desktop altrimenti verrà collocato nelladirectory temporanea /tmp/foo. La format-tazione del file è stata ideata per facilitarnela lettura con un qualsiasi editor di testi chepermetta di visualizzare caratteri ASCII;

e Aggiornamento VSI.Ultimate le operazioni fondamentali per l’avviodel frame viene comunicato all’utente chel’applicativo o è pronto per essere utiliz-zato oppure deve essere riavviato a causadi qualche Exception. Tale comunicazioneavviene tramite quello che è stata chiamato VSI(Verbose System Information), una JTextAreaposta sotto il MapPanel, che volendo può fun-gere anche da output per un debug del sistema.Un esempio di VSI è riportato in figura 45;

Fig. 45: Screenshot esemplare della VSI.

f Abilitazione alla ricezione messaggi.L’ultima operazione coinvolta nell’initè l’abilitazione del frame allaricezione dei messaggi. La ricezionesi traduce nell’esecuzione del metodomessageReceived(int, Message),che agisce come un interrupt, segnalandol’arrivo di un messaggio dalla porta dicomunicazione predefinita. L’enable è divenutodunque indispensabile in quanto questo metodopoteva generare delle null exception qualora

venisse invocato da JAVA prima che il frameavesse completato l’istanziazione di tutti glioggetti.

Terminato l’init, se il nodo mobile si trova nello statoIDLE anche il frame permane in uno stato di quiete,fintantoché l’utente non invia qualche comando al mote.Per poter interagire con il nodo mobile l’utente disponedella consolle di figura 46.

Fig. 46: Screenshot dei pulsanti per lo start/stop delTMOTESKYr.

La consolle di comando prevede di poter specificare laporta di comunicazione con il TMOTESKYr, che didefault è serial@/dev/ttyUSB0:tmote, ovverouna porta USB che funge da seriale. Definito l’inputdel PC si può procedere all’avvio del nodo mobile,premendo il tasto START. Questo JButton provvede in-nanzitutto a stabilire una connessione con il nodo mobile,qualora non fosse stato fatto in precedenza, chiamandoil metodo connect(String). Questo metodo crea unoggetto PhoenixSource che si basa su un PacketSourceper automatizzare sia la lettura e il dispatching deipacchetti sia il restarting della porta di comunicazione. IlPhoenixSource viene agganciato ad un oggetto MoteIFche fornisce un interfacciamento JAVA a livello appli-cation per ricevere messaggi da, e inviare messaggi al,mote. A questo punto il JFrame viene registrato comeMessageListeners del MoteIF per ognuno dei tipi dimessaggio generati dal MIG: DataMsg, MoteCtrlMsg,PingPcMsg. Se la connessione va a buon fine vieneinoltrato al mote il comando di START mediante la fun-zione send(int, Message) dell’oggetto MoteIF.Similmente si comporta il tasto relegato allo STOP delmote: alla pressione del corrispettivo JButton se TESEO

è connesso al nodo mobile viene inoltrato al mote ilcomando di STOP.Tra le modalità per fermare il nodo mobile è pre-


vista anche la chiusura del frame dal menu dellafinestra di sistema. Quando il JFrame rileva l’eventoWINDOW_CLOSING viene stoppato il mote secondole modalità descritte precedentemente e inoltre vienerichiamata la funzione logging() che ha il compito disalvare definitivamente su file i dati raccolti fino a quelmomento.

Dall’istante in cui il mote non si trova più in unostato IDLE il frame diviene sensibile alla ricezionedi messaggi trasmessi via seriale dal mote. Primadi procedere però nell’analizzare il ruolo svolto dalmetodo messageReceived(int, Message) con-viene prestare attenzione ad un altra feature di TESEO:il JPanel di figura 47, denominato Channel.

Fig. 47: Pannello per la gestione della stima della distanzadai nodi che compongono la cella.

Questo pannello è molto utile per il debug del sistema inquanto consente di trasferire a JAVA il compito di calco-lare la distanza dei nodi fissi dal nodo mobile, mediantelo stimatore di M.V. (6). Di default il ButtonGroupè impostato sul JRadioButton Disable e quindi lastima della posizione viene fatta basandosi sulle distanzedei nodi che dinamicamente vanno a costituire la cella.Se si seleziona il JRadioButton All Cell Nodes

o #Node si ha la possibilità di impostare i valori A

e np della potenza P (d) di trasmissione, confermandola modifica con il tasto Apply. Questi valori vengonopassati al metodo estimateDistance(int) checalcola la distanza a partire dalla media della potenzadi trasmissione, differente nodo per nodo, contenuta nel

DataMsg. In questo modo è possibile ricavare i valori A

e np opportuni per il canale, senza dover riprogrammareuno ad uno i nodi, risparmiando un notevole quantitativodi tempo. Con il JRadioButton All Cell Nodestalestrategia viene applicata indistintamente per tutti i nodimentre con il JRadioButton #Node ci si può concen-trare su un’unico nodo, specificato dal suo ID number,la cui distanza stimata viene visualizzata in una JLabeldel JPanel Channel.

Indipendentemente dalle scelte di debug, se nonvi sono problemi di comunicazione, il frame sitrova in costante attesa di pacchetti dal nodomobile. Come detto precedentemente, una call dimessageReceived(int, Message) viene igno-rata se il frame non è stato ancora completamente inizia-lizzato; inoltre il metodo termina subito se è in corso lastima della posizione del nodo mobile. In caso contrarioil metodo ravvisa due distinte operazioni a seconda cheil messaggio sia di tipo PingPcMsg o DataMsg:

1) se è un PingPcMsg ed è il primo messaggio diquesto tipo ad essere arrivato allora il frame sisincronizza con l’algoritmo di localizzazione prin-cipale, procedura che il nodo mobile sta ciclandoripetutamente. Per fare ciò viene istanziato unTimer, variabile globale del JFrame, che schedulal’esecuzione di un TimerEstimate con un delay diAUDIT_TIME [ms]. Il metodo poi termina:

• memorizzando la frequenza e la potenza ditrasmissione, l’ID del nodo mobile e l’ID delbroadcast attuale, tutte informazioni che sonocontenute nel PingPcMsg;

• resettando la HashMap<Integer,Node> delMapPanel che contiene i nodi fissi costituentila cella (al passo precedente rispetto al broad-cast appena rilevato), qualora non sia ancoraarrivato almeno un DataMsg.

Prima che possa scadere il timer, il cui delayè appositamente studiato per essere di pocosuperiore alla durata temporale del broadcast,pari a TIMER_BROADCAST [ms], il metodomessageReceived(int, Message) puòcontinuare ovviamente a ricevere messaggi. Infatti


il software JAVA deve avere il tempo per creare lacella di nodi fissi attribuita al broadcast corrente,senza la quale non potrebbe arrivare a determinarela posizione del mote mobile.TimerEstimate è sottoclasse di TimerTaske implementa l’interfaccia Runnable: quandosono trascorsi gli AUDIT_TIME [ms] vieneinvocato il run() del TimerEstimate, chepassa semplicemente il testimone al metodorealEstimate() della classe Estimate,anch’essa variabile globale del frame. La classeEstimate si occupa a tutti gli effetti della stimadella posizione; si intuisce dunque perché laricezione dei DataMsg utili deve terminare primache scada il timer;

2) se è un DataMsg ed è il primo messag-gio di questo tipo ad essere arrivato in se-guito all’ultima stima effettuata, viene resettatala HashMap<Integer,Node> del MapPanel inmodo da elimare i nodi fissi che costituivano lacella al passo precedente. Dopodiché, se il nodofisso a cui appartiene il DataMsg non è presentenella cella, viene controllato se la sua distanzadal mote è inferiore al MAX_CELL_RANGE [m].In questo modo viene completata l’ultima ope-razione di filtraggio sui nodi, escludendo quelliche si trovano al di fuori di un raggio diMAX_CELL_RANGE [m] dal nodo mobile. Se ilcheck ha esito positivo il nodo fisso viene ag-giunto alla HashMap<Integer,Node> del Map-Panel e le sue coordinate vengono aggiunteal Vector<Coordinate3D> della classe Estimateassieme alla misura della distanza, aggiunta alVector<Double>, sempre della classe Estimate.Come discusso precedentemente la distanza puòessere quella stimata dal nodo fisso stesso o quellastimata in JAVA, a seconda di quale JRadioBut-ton è momentaneamente selezionato nel JPanelChannel. Al dì là di motivi legati al debug laprecisione numerica delle due stime è la medesima,ciò significa che non vi sono errori numerici legatialla capacità di computazione del microprocessoredei TMOTESKYr. Questo ottimo risultato è stato

reso possibile anche grazie al fatto che la distanza,prima di essere trasmessa dal mote, viene shiftatadi una quantità pari a SHIFT_ROUND in modoche il dato, inizialmente float, venga inviatocome long, per essere riportato poi dal PC conun D_HAT_TOS_RESCALE al suo valore reale invirgola mobile.

Il metodo messageReceived(int, Message),come accennato, continua a discriminare i messaggi perun AUDIT_TIME [ms], dopodiché decreta l’inizio delprocesso di stima della posizione del mote, affidato allaclasse Estimate.

Estimate:Questa classe è praticamente assimilabile al suo unicometodo, realEstimate() di tipo synchronized

che si suddivide nelle seguenti, sequenziali, operazioni:

1) copia dei valori contenuti nel Vec-tor<Coordinate3D> e nel Vector<Double>in due rispettivi array, per poter essere passaticome parametri al costruttore di un oggettoMLfunction. Vector<Coordinate3D> contiene leposizioni dei nodi fissi costituenti la cella, mentreVector<Double> contiene le distanze dei singolinodi fissi dal nodo mobile;

2) istanziazione di una MLfunction.Questa classe implementa l’interfacciaMultivariateFunction pertanto è dotata diun metodo evaluate(double[]) il qualeracchiude la funzione dell’algoritmo di M.V.della posizione, equazione (14), da minimizzare.I bound degli argomenti passati come parametriall’evaluate(double[]) sono ±∞ pertantonon si pongono limiti ai possibili valori che puòassumere il minimo, l’argomento del quale sarà ditipo Coordinate2D o Coordinate3D a secondache si vogliano stimare o solo le componentiplanari o quelle tridimensionali.

3) creazione del ConjugateGradientSearch, impo-stando il metodo Beale-Sorenson, Hestenes-Stiefelper l’aggiornamento della direzione del gradienteconiugato e uno step di 1.0 [m], lasciato al suovalore di default, per indicare lo scostamento atteso


dalla soluzione;4) ricerca del minimo, richiamando il metodo

optimize(MultivariateFunction,

double[], double, double), che vieneapplicato alla MLfunction. Tale metodo richiededi specificare la condizione iniziale da cuil’algoritmo deve partire, che è stata fissataarbitrariamente in corrispondenza del centrodella stanza, e il livello di tollerranza numerica,dato da TOL_X e TOL_FX. Va sottolineato cheConjugateGradientSearch è una sottoclassedi MultivariateMinimum, la quale dovrebbesvolgere sulla MLfunction un numero massimodi computazioni onde evitare di loopare per untempo eccessivamente lungo. Attualmente questolimite viene ignorato, in quanto si è visto che,nel peggiore dei casi, l’algoritmo impiega untempo non superiore ai 200 [ms] per terminare.In pratica ci si è approcciati al calcolo numericocon una filosofia brute force: se il minimo esistenon sussistono problemi, altrimenti la funzioneviene iterata per un numero imprecisato di voltefino a che un criterio di stop non dà esitopositivo per 4 volte, causando l’interruzione dellaroutine dedicata alla minimum search. Qualora ilminimo non esista il valore ritornato è un NaN,cioè viene considerato come un not a number,altrimenti l’ottimizzazione restituisce direttamentelo stimatore. In entrambi i casi il risultato vienesalvato come posizione del nodo mobile;

5) gestione della posizione del mote. Se questa èdiversa da NaN viene:

• memorizzata nell’oggetto Node riferito almode della classe MapPanel;

• aggiunta al Vector<Node> che raggruppatutte le posizioni stimate fino a quel momento,in modo da poterne effettuare il tracing;

• approssimata ad un certo numero di cifresignificative, per essere ridotta ad una Stringvisualizzabile nel frame.

In caso contrario viene comunicato all’utente chela stima attuale non è un numero valido, che viene

pertanto ignorato, tenendo implicitamente validal’ultima posizione stimata con successo;

6) reset delle variabili. realEstimate() terminafacendo un clear() di Vector<Coordinate3D>e Vector<Double> e notificando al frame che ilprocesso di stima si è concluso.

A questo punto il JFrame è pronto per attendere unnuovo PingPcMsg, a cui seguiranno altri DataMsg, cheverranno utilizzati per procedere ad una nuova stimadella posizione del mote.Per tenere traccia del broadcast corrente e delle coor-dinate calcolate lo user ha a disposizione il pannello difigura 48. Interagendo con esso può anche essere attivatoil tracing, vedendo così la traccia del percorso fatto finoa quell’istante dal nodo mobile, ovviamente a livello distima di massima verosimiglianza.

Fig. 48: Finestra informativa del nodo mobile.

Nella colonna della consolle di comando del softwareè presente anche una sezione di pulsanti che allo statoattuale non sono abilitati, poiché il codice sorgente percui sarebbero predisposti non è stato ancora realizzato.

Fig. 49: Pulsanti adibiti allo zoom.

Questi JButton, evidenziati in figura 49, dovrebberoservire per poter effettuare uno zoom in o zoom outdella mappa, e conseguentemente poterla scorrere, permettere in risalto delle aree specifiche, presumibilmente


nei dintorni della posizione dell’utente.In ultimo, dal JMenu del frame è possibile visualiz-

zare la JDialog di figura 50, che ritrae le informazioniriguardo al software e ai produttori.

Fig. 50: Screenshot della finestra di "About".

D. MapPanel.java

MapPanel è una sottoclasse di JPanel la cui funzioneè coordinare la visualizzazione dell’ambiente graficoinerente la mappa. Teseo contiene una istanza di Map-Panel, come variabile globale, che viene inizializzatainvocando il metodo initEnvironment(String)

in una delle fasi dell’init di Teseo, privando dunque ilcostruttore di questo compito.

La prima operazione che spetta al MapPanel, è quelladi caricare sia il file immagine della mappa predefinita,sia le posizioni dei nodi fissi previamente dispostiall’interno delle varie locazioni della mappa. Per rendereflessibile tale necessità si è realizzato un parser, al fine dileggere le impostazioni direttamente da dei file di con-figurazione testuali aventi estensione .map. Il parsingviene eseguito dal metodo parseMapFile(String)al quale viene passato come parametro il nome delfile di configurazione, contenuto nella sottodirectory/maps del package teseo. Perché il parsing avvenga inmaniera corretta il file deve essere compilato rispettandole seguenti regole:

• la prima riga deve contenere il nome del file im-magine .jpg della mappa, di dimensioni esclusi-vamente pari a 640x480;

• la seconda riga deve contenere la posizionedell’origine degli assi cartesiani di riferimento, in

[pxl], utilizzati per misurare le posizioni relative deinodi nella location;

• le righe successive devono contenere le infor-mazioni dei nodi fissi, ovvero, nell’ordine: l’IDdella stanza di appartenenza, l’ID del nodo,l’ordinata in [cm], l’ascissa in [cm] e la coordinataz in [cm];

Le righe del file /maps vengono numerate in progres-sione, escludendo le righe vuote e quelle commentate.Per inserire un commento il primo carattere inserito deveessere "#".La scansione del file viene eseguita impiegando unsemplice text scanner della libreria standard di JAVA

che può unire tipi di dato primitivi e stringhe medianteregular expressions. Uno Scanner separa l’input in varitoken discriminati da un delimiter pattern che per defaultcorrisponde al whitespace. I token risultanti possonoessere convertiti in tipi di dato differenti utilizzando ivari metodi next() corrispondenti.I nodi vengono memorizzati in una HashMap<Integer,Node>, una tabella hash basata su una implementazionedell’interfaccia Map<K, V>, che consente di inseriree trovare coppie di elementi in O(1). L’indicizzazioneviene effettuata usando come key l’ID dei nodi, che èunivoca per definizione. All’occorrenza, per accedere ite-rativamente al contenuto dell’intera HashMap<Integer,Node>, si fa scorrere un Iterator sul Set delle chiavi,ottenibile in un passo con il metodo keySet() diMap<Integer, Node>.

Completato il parsing, con il metodoloadImage(String) vengono caricate le iconeassociate al nodo mobile, ai nodi fissi e all’originevirtuale degli assi, riportate in figura 51. Il nodo mobileviene visualizzato alternando in sequenza tre iconeverdi di diverse dimensioni, per dare al mote un sensodi dinamicità. I nodi fissi invece sono dei rettangoli dicolore blu o rosso a seconda che il nodo appartenga omeno alla cella. Il riferimento, la cui visualizzazioneè opzionale, è un mirino verde oliva. Nell’ipotesi cheil loading di alcune immagini non vada a buon fineè prevista la sostituzione di queste con un rettangolodella classe Graphics, disegnabile con il metodofillRect(int, int, int, int).


Fig. 51: Icone utilizzate nel MaPanel.

Fig. 52: Screenshot esemplare del MapPanel in funzione.

L’ultima azione eseguita dall’init è l’avvio di unThread, cammuffato dal MapPanel stesso, che serveper fare il refresh del JPanel ogni REFRESH_TIME[ms], impostabili a piacere. Il refreshing si traducenel richiamare il rapaint() che a sua voltainvoca paintComponent(Graphics). InpaintComponent(Graphics) vengono disegnati:

1) la mappa, con drawImage(Image, int, int,

int, int, ImageObserver);2) l’origine, con drawImage(Image, int, int,

int, int, ImageObserver);3) i nodi fissi, iterando drawAnchorNode(Node,

Graphics, boolean);4) il mote, con drawMobileNode(Graphics);5) la traccia del percorso eseguito fin’ora dal nodo

mobile, se richiesta, ottenuta unendo con una lineale diverse posizioni del mote. Le posizioni vengonoprelevate in ordine temporale da un Vector<Node>grazie ad un Iterator su un Enumeration deglielementi del vettore. La linea viene disegnatacon il metodo drawThickLine(Graphics,

int, int, int, int, int, Color).

E. Conclusioni e sviluppi futuri

Il software TESEO, sufficiente per uno studio di fat-tibilità e di collaudo degli algoritmi trattati, è da ritenersiuna versione sicuramente incompleta dal punto di vistadel prodotto finale. Si è cercato di realizzare un applica-tivo stabile, gestendo le varie Exception che si possonopresentare nell’utilizzo del software, ma non è stata effet-tuata un’analisi delle prestazioni globale, concernente lamemoria occupata e il tempo di calcolo richiesti da JAVA.Mettendo da parte un’opera minuziosa di debug, TESEO

può essere suscettibile di svariate migliorie e aggiunte,tra le quali si annoverano le seguenti:

1) studiare delle alternative alla stima M.V. da appli-care quando si presenta il NaN;

2) dotare l’interfaccia di uno zoom in e zoom out perla mappa, con la possibilità di spostarsi nei varipunti della mappa tramite le freccie del pannellodi controllo;

3) aggiungere il controllo di TESEO da tastiera o dajoypad;

4) dotare il software di un change automatico dellemappe, a seconda dello spostamento del nodomobile nelle varie stanze;

5) valutare la possibilità di segnalare graficamente lazona colpita dall’incendio, tramite l’uso dei sensoridi temperatura di cui sono dotati i TMOTESKYr;

6) implementare l’algoritmo di emergenza interno alnodo mobile per la stima della posizione, qualoravenga a mancare il client, per motivi che possonoandare dal crash del sistema all’interruzione dellecomunicazioni o dell’alimentazione;

7) prevedere la comunicazione con un serial for-warder centrale;

8) approfondire l’uso del binding di JAVA per le QT,ovvero la migrazione da JAVA a QT tramite librerieappositamente studiate per lo scopo, disponibili inLinux;

9) completare il tracing della posizione del nodomobile, filtrando opportunamente le posizioni;

10) fornire una documentazione del codice secondo lasintassi e le regole della Javadoc.


VIII. CONCLUSIONI

L’algoritmo principale di localizzazione è stato speri-mentato nel testbed e ha dato risultati soddisfacenti; inparticolare, si è percorso un tracciato all’interno dellazona coperta dai nodi ancora, notando che la posizionestimata dal software Teseo è molto vicina rispetto aquella reale commettendo un errore compreso tra 0 e1.5 metri; ciò è testimoniato dal video nel cd allegatoalla relazione. Risultati migliori si potrebbero ottenereutilizzando, nella stima di massima verosimiglianza delledistanze, una media su un numero maggiore di potenze;ciò d’altra parte comporta un aumento delle tempistichein gioco ed è quindi stato preferito Npck = 40.

L’algoritmo realizzato è stato preferito ad altri piùcomplessi (e.g. filtro particellare) per poterlo realizzarefino al basso livello, in modo da dare all’utente finale unprodotto completo; nonostante ciò l’algoritmo può esseremigliorato, ad esempio integrando la stima di massimaverosimiglianza con il filtro di Kalman: la stima di M.V.può essere l’inizializzazione del filtro, che negli istantisuccessivi lavora su un modello generico a passeggiataaleatoria, oppure la stima di M.V. può costituire ad ognipasso la predizione che viene corretta successivamentedal filtro con un opportuno guadagno.


REFERENCES

[1] A. Fusiello, Visione Computazionale: appunti delle lezioni,Università di Verona, 2006.

[2] Moteiv, T-mote Sky: Ultra low power IEEE 802.15.4 compliantwireless sensor module - Product information, 2006.

[3] Moteiv, T-mote Sky: Ultra low power IEEE 802.15.4 compliantwireless sensor module - QuickStart Guide, 2006.

[4] Texas Instruments, Datasheet MSP43X1XX Family - User’sGuide, 2006.

[5] Chipcon, Datasheet CC2420 2.4 GHz IEEE 802.15.4 ZigBee-ready RF Transceiver, 2005.

[6] ST Microelectronics, Datasheet STM5P80, 2007.

[7] IEEE Standard, Wireless Medium Access Control (MAC) andPhysical Layer (PHY) Specifications for Low-Rate Wireless Per-sonal Area Networks (LR-WPANs), IEEE Standard for Informa-tion technology, 2003.

[8] E.L. Lloyd, G. Xue, Relay Note Placement in Wireless SensorNetworks, IEEE Transaction on Computers, Vol. 56, No. 1,January 2007.

[9] Francesco Roveron, Analisi sperimentale di connettività per unarete di sensori wireless, 2007.

[10] Giorgio Picci, Filtraggio Statistico (Wiener,Levinson,Kalman) eapplicazioni, Edizioni Libreria Progetto, 2004.

[11] G. Picci Metodi Statistici per l’Identificazione di ModelliLineari Dispense per il corso di Identificazione dei Modelli,a.a.2006/07.

[12] L. Song, D. Hatzinakos A Cross-Layer Architecture of WirelessSensor Networks for Target Tracking, IEEE/ACM Transactionson Networking, vol.15, no.1, February 2007.

[13] Luca Parolini, Metodi di localizzazione per reti di sensoriwireless, 2006.

[14] Neal Patwari, Location Estimation in Sensor Networks, Ph.D.Thesis in Electrical Engineering: Systems, University of Michi-gan, 2005.

[15] N. Patwari, A.O. Hero III, M. Perkins, N.S. Correal andR.J. O’Dea Relative Location Estimation in Wireless SensorNetworks, IEEE Transactions on Signal Processing, October2002.

[16] N. Patwari, R.J. O’Dea and Y. Wang Relative Location inWireless Networks, IEEE VTC, vol.2, May 2001.

[17] R.R. Brooks, P. Ramanathan and A.M.Sayeed Distributed Tar-get Classification and Tracking in Sensor Networks, Proceedingsof the IEEE, vol.91, no.8, August 2003.

[18] S. Slijepcevic, M. Potkonjak, Power Efficient Organizationof Wireless Sensor Networks, Computer Science Department,University of California (UCLA), 2006.

[19] S. Meguerdichian, F. Koushanfar, M. Potkonjak, M.B. Srivas-tava Coverage Problems in Wireless Ad-hoc Sensor Networks,2006.

[20] T. He, P. Vicaire, T. Yan, L. Luo, L. Gu, G. Zhou, R. Stoleru,Q. Cao, J.A. Stankovic and T. Abdelzaher Achieving Real-TimeTarget Tracking Using Wireless Sensor Networks, 2005.

[21] W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. FlanneryNumerical Recipes in C: The Art of Scientific Computing, Cam-bridge University Press, 2nd ed., 1992.

[22] Philip Levis, TinyOS Programming, 2006.[23] Philip Levis TinyOS 2.0 Tutorials, 2007.[24] Ion Yannopoulos, David Gay TEP 3 - Coding Standard, 2006.[25] David Gay, Jonathan Hui TEP 103 - Permanent Data Storage

(Flash), final.[26] Philip Levis, Cory Sharp TEP 106 - Schedulers and Tasks, final.[27] Philip Levis TEP 107 - TinyOS 2.x Boot Sequence, final.[28] Philip Levis TEP 111 - message_t, final.[29] Ben Greenstein, Philip Levis TEP 113 - Serial Communication,

2006.[30] Philip Levis TEP 116 - Packet Protocols, 2007.[31] Bruce Eckel, Thinking in Java, 3rd Edition, Prentice Hall PTR,

2003.[32] Cay S. Horstmann, Gary Cornell Core Java 2: Volume I -

Fundamentals, Prentice Hall PTR, 2002.[33] Cay S. Horstmann, Gary Cornell Core Java 2: Volume II -

Advanced Features, Prentice Hall PTR, 2002.[34] Bil Lewis, Daniel J. Berg Multithreaded Programming with

Java Technology, Prentice Hall PTR, 2001.[35] Richard P. Brent Algorithms for finding zeros and extrema of

functions without calculating derivatives Prentice Hall, 1973.


Alessandro MOGGI Marcassa (dato chenon riceve mai telefonate), nato a Venezia il23/12/1983, automatico puro grazie ai preziosiconsigli del fratello è cresciuto mangiandofiltri di Kalman e bevendo spritz, Havana Colae quant’altro. Anche lui accolto, assieme agliamici Riccardo e Fabio, nella grande famigliadegli automatici guidata dal Prof. A.B. e G.P.

(mito incontrastato del 3°piano). Ha una spiccata vena commercialee politica ma grossi problemi con donne e alcool.

Riccardo Marcon , nato a Piove di Saccoil 27/08/1983, genio incompreso, aspiranteZio Paperone e berlusconiano doc, ha iniziatola sua carriera universitaria prendendo unabrutta piega (o piaga): ingegneria informatica.Nonostante ciò, illuminato dal Prof. A.B. hapreso la giusta via alla fine del secondo anno.Acclamato e cercato da tutti dedica la sua vita

all’identificazione, al controllo e soprattutto a donne & alcool.

Fabio Maran , nato a Padova il 13/09/1983,figlio del peccato (Laurea triennale in Ing. In-formatica) ma redento anche lui dal Prof. A.B.si dedica con passione al controllo. Insepara-bile amico di Riccardo, con cui condivide tuttotranne le donne e G.P. Recentemente traviatodal resto della banda bassotti stà raggiungendola via della perdizione divergendo con velocità

esponenziale. Colore preferito: Nero, chi lo conosce lo sa.

Filippo Zanella , nato a Valdobbiadene il04/02/1983, donnaiolo, poeta, aspirante im-prenditore, Rotaractiano, schermidore, bene-fattore e anche automatico con ascendenteinformatico perseguitato da Benny. Nella vitaha combinato (disastri) e combina di tutto, vivein un mondo parallelo ma qualche volta tornain quello che tutti noi conosciamo e in cui

viviamo. E’ il tipico esempio di bronsa coerta: viso angelico, mentediabolica. Nota: deceduto alle ore 07.15 a.m. del 23 Luglio 2007dopo 222 ore consecutive di tex.

CORSO DI LAUREA SPECIALISTICA IN INGEGNERIA DELL ...schenato/PSC07/RelazionePSC07_Track_2.pdf ·...

Documents

Transcript of CORSO DI LAUREA SPECIALISTICA IN INGEGNERIA DELL ...schenato/PSC07/RelazionePSC07_Track_2.pdf ·...