A.Dionisi Thesis

Facolta di Ingegneria

Tesi di Laurea Specialistica in

Ingegneria Informatica

Esplorazione per Robot Mobili basata suDispositivi ZigBee

Alessandro Dionisi

Relatore Controrelatore

Prof. Luca Iocchi Prof. Roberto Beraldi

Correlatore

Dott. Ing. Vittorio Amos Ziparo

Anno Accademico 2006/2007

“Debugging is twice as hard as writing the code in the first place. Therefore, if you

write the code as cleverly as possible, you are, by definition, not smart enough to debug

it.”

Brian W. Kernighan

Ringraziamenti

Questo lavoro di tesi e nato innanzitutto grazie alla disponibilita del Prof. Beraldi,

che appresi i miei interessi per le tecnologie wireless ha saputo indirizzarmi verso il

laboratorio SIED. Ringrazio ovviamente il mio relatore, il Prof. Iocchi, per avermi dato

la possibilita di affrontare un progetto stimolante e per avermi indicato sempre la giusta

soluzione ai problemi che continuamente si sono presentati. La mia riconoscenza va

inoltre al Prof. Nardi per avermi accolto come tesista nel laboratorio SIED.

Ringrazio tutti i dottori, dottorandi e ingegneri del laboratorio, tra cui Alberto, Die-

go, Domenico, Gabriele, Gianpaolo, Giuseppe, Stefano, per i loro preziosi suggerimenti

e in particolare Arrigo, Daniele e Vittorio, per il costante supporto fornito durante tutto

il periodo di tesi.

E doveroso da parte mia ringraziare tutti i colleghi tesisti Gianluca, Giuliano, Joao,

Luigi, Stefano, Valerio, per i loro consigli e per aver reso meno pesanti le giornate

trascorse al SIED. La mia riconoscenza va inoltre ai ragazzi dell’RFID-Lab, in particolare

al Prof. Medaglia e a Leonardo, per avermi riservato parte del loro tempo.

Un ringraziamento speciale e destinato a Michela, per essermi stata cosı vicino, con

il cuore e con la mente, in questo periodo impegnativo della mia vita.

Desidero infine rigraziare tutta la mia famiglia, in particolare i miei genitori Giorgio

e Cinzia, mio fratello Francesco, i miei nonni Franco e Gina per avermi supportato

psicologicamente e moralmente durante tutti questi splendidi anni all’universita.

ii

Indice

Ringraziamenti ii

Elenco delle figure vii

Elenco delle tabelle ix

Abbreviazioni x

Introduzione 1

I Concetti fondamentali e stato dell’arte 7

1 Robot per l’esplorazione autonoma 81.1 Possibili scenari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2 Tipi di robot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2.1 Robot del laboratorio SIED . . . . . . . . . . . . . . . . . . . . . . 101.3 Moduli funzionali di un robot esploratore . . . . . . . . . . . . . . . . . . 12

1.3.1 Sensori e tecniche per l’esplorazione . . . . . . . . . . . . . . . . . 131.3.1.1 Odometria . . . . . . . . . . . . . . . . . . . . . . . . . . 131.3.1.2 Sensori inerziali . . . . . . . . . . . . . . . . . . . . . . . 141.3.1.3 Sonar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3.1.4 Laser scanner . . . . . . . . . . . . . . . . . . . . . . . . . 151.3.1.5 GPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.3.1.6 Landmark . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3.2 Localizzazione e mappe . . . . . . . . . . . . . . . . . . . . . . . . 171.3.2.1 Feature maps . . . . . . . . . . . . . . . . . . . . . . . . . 181.3.2.2 Occupancy grid . . . . . . . . . . . . . . . . . . . . . . . 181.3.2.3 Mappe topologiche . . . . . . . . . . . . . . . . . . . . . . 19

1.3.3 Navigazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.3.3.1 Pianificazione . . . . . . . . . . . . . . . . . . . . . . . . 20

1.4 Esplorazione autonoma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.5 Simulatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.5.1 Player/Stage/Gazebo . . . . . . . . . . . . . . . . . . . . . . . . . 221.5.2 USARsim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.6 Il framework SPQR-RDK . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

iii

Contenuto iv

1.6.1 Agenti e moduli . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.6.2 Repository . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.6.3 Concorrenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251.6.4 Comunicazioni tra agenti . . . . . . . . . . . . . . . . . . . . . . . 251.6.5 Strumenti di supporto . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 Localizzazione basata su dispositivi wireless 272.1 Fenomeni nella propagazione radio . . . . . . . . . . . . . . . . . . . . . . 29

2.1.1 Attenuazione dello spazio libero . . . . . . . . . . . . . . . . . . . . 292.1.2 Assorbimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.1.3 Rifrazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.1.4 Scattering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.1.5 Diffrazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.1.6 Multipath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.2 Modelli di propagazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.3 Il processo di localizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . 352.4 Metodi di localizzazione range-based . . . . . . . . . . . . . . . . . . . . . 36

2.4.1 Time Of Arrival . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.4.2 Angle Of Arrival . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.4.3 Received Signal Strenght . . . . . . . . . . . . . . . . . . . . . . . 37

2.4.3.1 RSS fingerprinting . . . . . . . . . . . . . . . . . . . . . . 382.5 Metodi di localizzazione range-free . . . . . . . . . . . . . . . . . . . . . . 40

3 Lo standard ZigBee 423.1 Le motivazioni della scelta . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.2 La nascita dello standard . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.3 Caratteristiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.4 Lo stack ZigBee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.4.1 Lo strato PHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.4.1.1 Modulazione e spreading . . . . . . . . . . . . . . . . . . 473.4.1.2 Coesistenza con interferenze . . . . . . . . . . . . . . . . 483.4.1.3 Primitive offerte dallo strato PHY . . . . . . . . . . . . . 49

3.4.2 Lo strato MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.4.2.1 Tipi di dispositivi IEEE 802.15.4 . . . . . . . . . . . . . . 503.4.2.2 Le modalita di accesso al canale . . . . . . . . . . . . . . 513.4.2.3 Indirizzamento . . . . . . . . . . . . . . . . . . . . . . . . 523.4.2.4 Primitive offerte dallo strato MAC . . . . . . . . . . . . . 52

3.4.3 Lo strato NWK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.4.3.1 Tipi di dispositivi ZigBee . . . . . . . . . . . . . . . . . . 533.4.3.2 Topologie di rete . . . . . . . . . . . . . . . . . . . . . . . 543.4.3.3 Algoritmi di routing . . . . . . . . . . . . . . . . . . . . . 553.4.3.4 Sicurezza . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.4.3.5 Primitive offerte dallo strato NWK . . . . . . . . . . . . 56

3.4.4 Lo strato applicazione . . . . . . . . . . . . . . . . . . . . . . . . . 57

Contenuto v

II Sperimentazione, progettazione e implementazione 59

4 Analisi della qualita del segnale in ambienti indoor/outdoor 604.1 La piattaforma hardware/software di riferimento . . . . . . . . . . . . . . 61

4.1.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.1.1.1 Antenna . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.1.2 Test di orientamento dell’antenna . . . . . . . . . . . . . . . . . . . 634.1.3 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.1.4 Link Quality Indicator (LQI) . . . . . . . . . . . . . . . . . . . . . 64

4.2 Rilevazioni outdoor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.2.1 Dati numerici rilevati . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.3 Rilevazioni indoor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.3.1 Test statici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.3.2 Test dinamici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.3.3 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.3.4 Dati numerici rilevati . . . . . . . . . . . . . . . . . . . . . . . . . 71

5 Esplorazione guidata dalla qualita del segnale 735.1 Concetti preliminari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.1.1 Sistema di riferimento . . . . . . . . . . . . . . . . . . . . . . . . . 755.1.2 Esplorazione mediante frontiere . . . . . . . . . . . . . . . . . . . . 755.1.3 Configurazione dell’agente . . . . . . . . . . . . . . . . . . . . . . . 76

5.2 Esplorazione guidata dal LQI - Descrizione dell’algoritmo . . . . . . . . . 765.2.1 Calcolo degli score delle frontiere . . . . . . . . . . . . . . . . . . . 79

5.2.1.1 Un esempio di esecuzione . . . . . . . . . . . . . . . . . . 825.3 Possibili scenari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5.3.1 Rendezvous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 845.3.2 Rescue robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855.3.3 Deployment di reti ad-hoc . . . . . . . . . . . . . . . . . . . . . . . 855.3.4 Sorveglianza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6 Sperimentazione 876.1 Applicazione per i dispositivi ZigBee . . . . . . . . . . . . . . . . . . . . . 876.2 Applicazione per SPQR-RDK . . . . . . . . . . . . . . . . . . . . . . . . . 88

6.2.1 Modulo FrontierFinder . . . . . . . . . . . . . . . . . . . . . . . . . 896.2.2 Modulo ZigbeeInterface . . . . . . . . . . . . . . . . . . . . . . . . 906.2.3 Modulo ZigbeeExplorator . . . . . . . . . . . . . . . . . . . . . . . 926.2.4 Moduli di navigazione . . . . . . . . . . . . . . . . . . . . . . . . . 926.2.5 Moduli di localizzazione e mapping . . . . . . . . . . . . . . . . . . 92

6.3 Simulazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 926.4 Esperimenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

6.4.1 Esperimenti in simulazione . . . . . . . . . . . . . . . . . . . . . . 936.4.2 Esperimenti in ambiente reale . . . . . . . . . . . . . . . . . . . . . 94

III Risultati e conclusioni 97

7 Conclusioni e sviluppi futuri 98

Contenuto vi

7.1 Sintesi dei risultati ottenuti . . . . . . . . . . . . . . . . . . . . . . . . . . 987.2 Sviluppi futuri ed estensioni . . . . . . . . . . . . . . . . . . . . . . . . . . 99

IV Appendici 100

A Piattaforma Freescale MC13213 101

Bibliografia 103

Elenco delle figure

1.1 Alcuni robot esploratori . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.2 Alcuni robot mobili presenti nel laboratorio SIED . . . . . . . . . . . . . . 111.3 Schematizzazione di un robot mobile . . . . . . . . . . . . . . . . . . . . . 121.4 Sonar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.5 Laser scanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.6 Alcuni tipi di mappe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.7 Simulatori per robot mobili . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.1 Fenomeno di rifrazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.2 Fenomeno di diffrazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.3 Il procedimento di trilaterazione . . . . . . . . . . . . . . . . . . . . . . . 372.4 Impronte RSS nel sistema RADAR [BP00] . . . . . . . . . . . . . . . . . . 392.5 Alcuni approcci di localizzazione range-free . . . . . . . . . . . . . . . . . 40

3.1 Bitrate e range trasmissivi di ZigBee rispetto ad altri standard wireless . . 453.2 Lo stack ZigBee completo . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.3 Spreading e modulazione in 802.15.4 . . . . . . . . . . . . . . . . . . . . . 473.4 Coesistenza di ZigBee con 802.11 . . . . . . . . . . . . . . . . . . . . . . . 483.5 Organizzazione in SAP di ZigBee . . . . . . . . . . . . . . . . . . . . . . . 503.6 Accesso al mezzo con beacon . . . . . . . . . . . . . . . . . . . . . . . . . 513.7 Accesso al mezzo senza beacon . . . . . . . . . . . . . . . . . . . . . . . . 523.8 I SAP dello strato MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.9 Topologie di rete ZigBee . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.10 I SAP dello strato NWK . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.11 Concetto di binding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.1 La Sensor Reference Board (SRB) basata sul SiP MC13213 di Freescale . 614.2 Struttura ad F-Antenna . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.3 Test di orientamento dell’antenna . . . . . . . . . . . . . . . . . . . . . . . 644.4 Setup per i test outdoor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.5 Andamento del LQI con la distanza (media e varianza) . . . . . . . . . . . 664.6 Distribuzione dei valori del LQI per ogni intervallo . . . . . . . . . . . . . 674.7 Posizioni e rilevazioni di LQI nell’abitazione . . . . . . . . . . . . . . . . . 694.8 Test dinamici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694.9 Risultati dei test dinamici . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.10 Posizioni e valori delle rilevazioni LQI al DIS . . . . . . . . . . . . . . . . 72

5.1 Sistema di riferimento per il robot . . . . . . . . . . . . . . . . . . . . . . 755.2 Esplorazione basata su frontiere . . . . . . . . . . . . . . . . . . . . . . . . 75

vii

Elenco delle figure viii

5.3 Discretizzazione dell’ambiente e matrice LQI . . . . . . . . . . . . . . . . 775.4 Macchina a stati dell’algoritmo di esplorazione . . . . . . . . . . . . . . . 785.5 La mappa in modalita DEEP SCAN . . . . . . . . . . . . . . . . . . . . . . . 795.6 Grafico della funzione ∆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825.7 Confronto tra Fdist e lunghezza del path . . . . . . . . . . . . . . . . . . . 825.8 Calcolo degli score per le frontiere . . . . . . . . . . . . . . . . . . . . . . 83

6.1 Configurazione dell’applicazione ZigBee . . . . . . . . . . . . . . . . . . . 886.2 Diagramma delle classi del sistema . . . . . . . . . . . . . . . . . . . . . . 896.3 Le frontiere trovate con l’ausilio della distance map . . . . . . . . . . . . . 906.4 Generazione della mappa statica per il LQI . . . . . . . . . . . . . . . . . 916.5 Simulazione dell’algoritmo in Player/Stage . . . . . . . . . . . . . . . . . . 936.6 Esecuzione dell’algoritmo in un’abitazione . . . . . . . . . . . . . . . . . . 946.7 Esecuzione dell’algoritmo nel primo piano del DIS . . . . . . . . . . . . . 956.8 Esecuzione dell’algoritmo nello scenario del labirinto . . . . . . . . . . . . 956.9 La mappa generata nell’esplorazione . . . . . . . . . . . . . . . . . . . . . 966.10 Sperimentazione dell’algoritmo in ambiente reale . . . . . . . . . . . . . . 96

A.1 Schema a blocchi della piattaforma MC13213 . . . . . . . . . . . . . . . . 101A.2 Grafico potenza ricevuta/riportata . . . . . . . . . . . . . . . . . . . . . . 102

Elenco delle tabelle

1.1 Parametri tipici di un laser scanner . . . . . . . . . . . . . . . . . . . . . . 16

2.1 Valori del parametro N nell’ITU Model . . . . . . . . . . . . . . . . . . . 342.2 Valori del parametro Pf (n) nell’ITU Model . . . . . . . . . . . . . . . . . 342.3 Coefficienti del Log-Distance Path-Loss Model . . . . . . . . . . . . . . . . 35

3.1 Suddivisione della banda ZigBee . . . . . . . . . . . . . . . . . . . . . . . 46

4.1 Misurazioni LQI in ambienti outdoor . . . . . . . . . . . . . . . . . . . . . 674.2 Misurazioni LQI in una abitazione . . . . . . . . . . . . . . . . . . . . . . 71

A.1 Dati tecnici della piattaforma ZigBee MC13213 di Freescale . . . . . . . . 101

ix

Abbreviazioni

AO Application Object

AOA Angle Of Arrival

APL APplication Layer

APS APplication support Sublayer

BER Bit Error Rate

BPSK Binary Shift Phase Keying

CCA Clear Channel Assessment

CSMA-CA Carrier Sense Multiple Access with Collision Avoidance

DSSS Direct Sequence Spread Spectrum

ED Energy Detection

FFD Full Function Device

ISM Industrial Scientific and Medical

LoS Line of Sight

LR-WPAN Low-rate Wireless Personal Area Network

LQI Link Quality Indicator

MAC Livello di accesso al mezzo trasmissivo

MCPS MAC Common Part Sublayer

MLME MAC Layer Management Entity

NCB Network Coordinator Board

NLDE Network Layer Data Entity

NLME Network Layer Management Entity

NWK Livello di rete

O-QPSK Offset-Quadrature Phase Shift Keying

PAN Personal Area Network

PAN-ID Personal Area Network-IDentifier

PD PHY Data

x

Abbreviazioni xi

PHY Livello fisico

PIB PAN Information Base

PLME PHY Layer Management Entity

RFD Reduced Function Device

RSS Received Signal Strenght

SAP Service Access Point

SiP System-in-Package

SLAM Simultaneous Localization And Mapping

SoC System-on-Chip

SRB Sensor Reference Board

SSP Security Service Provider

TDOA Time Difference Of Arrival

TOA Time Of Arrival

USAR Urban Search And Rescue

WSN Wireless Sensor Network

ZC ZigBee Coordinator

ZDO ZigBee Device Object

ZED ZigBee End Device

ZR ZigBee Router

Ai miei genitori, per avermi dato questa opportunita...

xii

Introduzione

La possibilita di creare reti a basso costo e ad alta densita come le Wireless Sensor

Network (WSN) ha introdotto scenari applicativi prima irrealizzabili, che vanno dal mo-

nitoraggio di impianti alla domotica. Le loro capacita di mobilita ed auto-organizzazione,

con la caratteristica, inoltre, di non dipendere da un’infrastruttura di rete fissa, le hanno

rese ormai l’icona dell’Ubiquitous Computing.

La funzione principale di una WSN e quella di riportare eventi relativi all’ambiente

controllato, oltre a trasportare dati e informazioni provenienti dai molteplici sensori pre-

senti. In letteratura, tuttavia, e sempre piu frequente l’idea di aggiungere funzionalita

differenti dal controllo e dal monitoraggio; si pensi ad esempio al contributo informativo

apportato dalla localizzazione di un sensore, oltre al valore della grandezza fisica misu-

rata. In definitiva, per un utente e importante sapere, sia che una soglia di attenzione e

stata superata, sia in quale punto preciso della rete, dato che informazioni non associate

alla loro localizzazione potrebbero essere prive di significato.

Le possibilita offerte dalle WSN e dalle capacita di localizzare dei nodi al loro interno

[MFA07], le rendono appetibili anche nel campo della robotica, ad esempio per l’impiego

su robot mobili. E facile immaginare come informazioni sulla localizzazione di punti di

interesse possano divenire di estrema importanza in problemi di SLAM (Simultaneous

Localization and Mapping) [DWB06a, DWB06b] oppure per diminuire i tempi nella

ricerca di oggetti o zone particolari. Si comprende inoltre, quanto cio sia di interesse

primario in ambienti indoor (industrie, uffici, abitazioni), o dove comunque non c’e la

possibilita di utilizzare altri sistemi di posizionamento (come ad esempio GPS).

Attualmente, l’esplorazione rappresenta la tecnica principale mediante il quale pos-

sono essere risolti i problemi di ricerca [BFDW03, BCC+04] in ambienti non noti a

priori, in quanto gradualmente l’area sconosciuta viene ridotta, fino a permettere di

trovare l’obiettivo. Se ne deduce facilmente che, se non si hanno informazioni ag-

giuntive sulla localizzazione dell’obiettivo, si procede praticamente per tentativi, con

una ricerca cieca. Effettivamente, questa e la metodologia seguita da molti approcci

[Yam98, BMF+00, KPN, MTK, SB03] che si basano sul concetto di frontiera di esplo-

razione [Yam97], ovvero la zona di confine tra lo spazio noto e quello inesplorato. In

tali sistemi, l’esplorazione procede ad ogni passo visitando una frontiera, diminuendo in

1

Introduzione 2

questo modo lo spazio di ricerca. Il problema principale, risiede nel fatto che la selezione

della frontiera viene effettuata casualmente o al massimo con strategie greedy (scegliendo

ad esempio quella piu vicina al robot), dato che in molti casi non si hanno altre sorgenti

informative per procedere diversamente.

Lo scopo di questa tesi e l’integrazione di sistemi di robotica mobile con gli strumenti

e le potenzialita offerte dalle WSN, mediante un’applicazione di supporto alla localizza-

zione. L’approccio utilizzato in questo lavoro di tesi sfrutta le informazioni sulla qualita

del segnale radio (Link Quality Indicator) ricevuto dai nodi della WSN, installati a bordo

del robot, per guidarne l’esplorazione al fine di raggiungere zone di interesse segnalate da

altrettanti dispositivi. Come vedremo, alla rete possono appartenere sia i robot, sia altri

nodi che possono segnalare oggetti o essere rilasciati durante l’esplorazione stessa, con

la funzione di landmark [SN04]. I dispositivi selezionati per la realizzazione del sistema

seguono lo standard per le LR-WPAN (Low-Rate Wireless Personal Area Network), Zig-

Bee. La scelta di questa tecnologia e avvenuta dopo un’ampia fase di studio, effettuata

presso il laboratorio RFID-Lab, dell’Universita di Roma “Sapienza”, in cui sono stati

considerati attentamente i requisiti del sistema da realizzare.

Occorre notare che, in questo lavoro, non si cerca di risolvere un problema di loca-

lizzazione wireless assoluta, affrontato gia ampiamente in altri lavori [Pat05, BGGT07,

SKOM06, PHP+03, BP00, HHB+03] e peraltro di non facile soluzione se si considera-

no ambienti indoor, a causa di fenomeni fisici come attenuazione e multipath [Rap01].

Tali considerazioni hanno richiesto un lungo periodo di sperimentazione, in cui sono

stati realizzati test sia in ambienti outdoor che indoor, orientati a dimostrare quanto

gia noto in letteratura e a far comprendere le modalita con cui affrontare un problema

di localizzazione basato su dispositivi wireless. L’approccio proposto tenta di applicare

i meccanismi alla base della localizzazione, al problema dell’esplorazione, presentandosi

come un algoritmo in grado di guidare il robot verso l’obiettivo della ricerca, mediante

un’euristica che si basa sul principio elementare per cui la potenza del segnale decresce

con la distanza. In questo modo, anche se e difficile ricavare esattamente la distanza che

separa trasmettitore e ricevitore, e possibile stimare qualitativamente quanto si e vicini

alla sorgente del segnale. Di conseguenza, la ricerca che prima era cieca, si trasforma in

ricerca informata, con il vantaggio non indifferente che per la scelta della prossima fron-

tiera da esplorare, il robot avra a disposizione qualcosa in piu di una semplice strategia

greedy.

La possibilita di effettuare un’esplorazione guidata aiuta, oltre che a diminuire i

tempi di ricerca, anche ad aumentare l’autonomia energetica del robot, evitando zone

dell’ambiente non rilevanti ai fini della missione. Uno degli scenari mediante il quale

si puo comprendere l’utilita dell’idea presentata, e l’impiego del sistema in problemi di

Search and Rescue [HSI+99], in cui i robot mobili forniscono il loro supporto a squadre

di soccorritori umani, in operazioni di ricerca e salvataggio in ambienti che hanno subito

Introduzione 3

catastrofi o devastazioni, ad alto rischio per i soccorritori stessi. E facile immaginare

come informazioni sulla localizzazione di punti di interesse (ostacoli, feriti, punti di

raccolta, altri robot) possano divenire di estrema importanza per diminuire i tempi di

esplorazione di aree devastate, con la conseguenza di aumentare la probabilita di salvare

anche vite umane. Inoltre, considerate le possibilita di miniaturizzazione che possono

essere raggiunte nella produzione di dispositivi ZigBee, possiamo pensare ad uno scenario

in cui ogni persona puo indossare un ricevitore e che, nel caso di incidenti o devastazioni,

esso possa essere interrogato, in modo da facilitare il raggiungimento della vittima stessa.

Ad esempio, tali situazioni possono verificarsi in impianti industriali ad alto rischio, dove

sono potenzialmente possibili incendi, crolli strutturali o emissioni di sostanze tossiche.

Altri possibili esempi di applicazione, in cui l’approccio puo portare i suoi vantaggi,

sono il problema del rendezvous [DR97, ZLV07] tra robot, il deployment di reti ad-

hoc in situazioni di emergenza [RB05, HMS02] e alcuni scenari di sorveglianza robotica

[HBB+00].

Questa tesi si focalizza sul problema base del raggiungimento da parte di un robot

mobile equipaggiato con un dispositivo wireless ZigBee di un punto di interesse dove e

presente un altro di questi dispositivi, non in movimento. La soluzione di tale problema,

per motivi di complessita, non considera un ambiente multi-robot, ma e sicuramente

estendibile a scenari di tale tipologia. Il sistema e stato implementato in C++, su piat-

taforma Unix, sotto forma di moduli indipendenti per il framework per robot mobili

SPQR-RDK [FGI05]. La tesi e stata sviluppata presso il laboratorio SIED (Sistemi

Intelligenti per le Emergenze e la Difesa civile), nato dalla collaborazione tra l’Istituto

Superiore Antincendi ed il Dipartimento di Informatica e Sistemistica (DIS) dell’Univer-

sita di Roma “Sapienza”, con l’obiettivo di svolgere attivita di ricerca volte allo sviluppo

di metodologie, tecniche e strumenti prototipali da utilizzare in operazioni di soccorso.

Problematiche affrontate

La realizzazione di questo lavoro mi ha permesso di studiare diverse problematiche,

inerenti sia al campo delle reti di sensori che della robotica mobile. In particolare sono

stati affrontati i seguenti temi:

• Sperimentazione e selezione, presso l’RFID-Lab, di una piattaforma hardware/-

software per WSN, al fine di individuarne una idonea all’implementazione di un

sistema di localizzazione wireless.

• Studio del protocollo per LR-WPAN ZigBee, in particolare gli strati MAC, rete e

applicazione, in modo da acquisire i primi strumenti concettuali e applicativi per

progettare e implementare piccole applicazioni.

Introduzione 4

• Analisi delle prestazioni trasmissive dell’hardware selezionato, in ambienti indoor,

outdoor e in condizioni statiche e dinamiche, con lo scopo di comprendere le

potenzialita da sfruttare per effettuare localizzazione.

• Studio della letteratura riguardante i diversi approcci alla localizzazione wireless

e all’esplorazione per robot mobili, in modo da ottenere una visione completa di

quanto gia realizzato e avere solidi concetti base da cui iniziare il lavoro.

• Progettazione di un algoritmo per l’esplorazione di ambienti indoor semistrutturati,

basato sulla qualita del segnale ricevuto da dispositivi ZigBee. Tutto cio a seguito

dei risultati ottenuti in fase di test dei dispositivi in trasmissione.

• Modifica di alcuni moduli del kernel, per garantire l’interfacciamento dei dispositivi

ZigBee anche su sistemi operativi Unix, in quanto originariamente erano presenti

solo driver funzionanti per Windows.

• Implementazione dell’algoritmo e dei componenti di interfaccia verso il dispositivo

ZigBee in linguaggio C++, sotto forma di moduli software indipendenti per il

framework SPQR-RDK.

• Test del sistema in simulazione, nell’ambiente Player/Stage, e in ambiente reale, sui

robot mobili del laboratorio SIED, con lo scopo di dimostrare i risultati conseguiti

e i vantaggi introdotti con l’approccio scelto.

Risultati conseguiti

La grande quantita di dati sperimentali, raccolti durante l’analisi delle prestazioni tra-

smissive dei dispositivi, in ambienti indoor e outdoor, ha permesso di ritrovare i risultati

teorici noti in letteratura e, allo stesso tempo, trasformare il problema iniziale di localiz-

zazione wireless assoluta in un nuovo approccio all’esplorazione per robot mobili, basato

sulla qualita del segnale ricevuto dai dispositivi di una WSN.

Le sperimentazioni effettuate, sia in simulazione che in ambiente reale, dimostrano

l’efficacia dell’approccio proposto. L’aggiunta dell’informazione sulla qualita del segnale,

consente di risolvere i problemi di ricerca in modo informato, evitando l’esplorazione

di zone dell’ambiente eccessivamente distanti dall’obiettivo. La scelta delle frontiere

viene effettuata in base alla vicinanza con la sorgente del segnale, sostituendo strategie

greedy che spesso non creano vantaggi considerevoli. In questo modo, e sicuramente

possibile diminuire i tempi necessari all’individuazione di punti di interesse nella mappa e

incrementare notevolmente l’autonomia energetica del robot utilizzato per l’esplorazione.

Ovviamente, l’euristica pensata puo essere raffinata, tenendo in considerazione anche

informazioni di natura topologica sull’ambiente o elaborando le variazioni del segnale ri-

cevuto rispetto al percorso eseguito dal robot (considerando, in alcuni istanti, il gradiente

Introduzione 5

del LQI). L’idea presentata puo inoltre essere estesa a scenari multi-robot, agevolando

la soluzione di problemi come il rendezvous [DR97] o il coordinamento durante alcune

fasi dell’esplorazione multiagente [ZKNN07].

Traccia dell’esposizione

L’esposizione e organizzata come segue:

• Capitolo 1: Presentazione di tematiche relative all’esplorazione di robot mobili e

dei componenti hardware/software necessari per l’esplorazione autonoma. Ven-

gono descritti i concetti e gli strumenti della robotica disponibili per sviluppare

l’approccio descritto, sottolineando alcune tecniche per l’esplorazione autonoma.

• Capitolo 2: Introduzione agli approcci per la localizzazione wireless e descrizione

dei fenomeni fisici che influenzano le trasmissioni wireless. Lo studio effettuato, ha

permesso di comprendere in dettaglio i problemi da tenere in considerazione nella

realizzazione di un sistema di localizzazione.

• Capitolo 3: Descrizione dello standard per le LR-WPAN, ZigBee, focalizzando

l’attenzione sulle funzionalita dello stack che sono risultate di interesse per nel-

la valutazione e la successiva implementazione delle applicazioni. Tale studio ha

permesso di avere le prime indicazioni da cui partire per risolvere un problema di lo-

calizzazione, ottenute analizzando le informazioni restituite dalle primitive relative

alla qualita del segnale (Link Quality Indicator). Sono inoltre riportate le motiva-

zioni che hanno portato alla selezione di dispositivi ZigBee per la realizzazione di

questo lavoro di tesi.

• Capitolo 4: Illustrazione di esperimenti indoor/outdoor sulla variazione della qua-

lita del segnale e presentazione della piattaforma hardware selezionata per gli espe-

rimenti. Il capitolo contiene i numerosi test trasmissivi, effettuati al fine di deter-

minarne l’idoneita alla realizzazione di un sistema di localizzazione. La grande

quantita di dati raccolti ci ha permesso, non solo di verificare in parte alcuni

concetti teorici sulle trasmissioni wireless, ma anche di definire gradualmente il

problema reale che si voleva risolvere.

• Capitolo 5: In questo capitolo viene illustrata l’idea dominante di questa tesi, ov-

vero l’uso dell’informazione sulla qualita del segnale per effettuare una esplorazione

guidata. Viene fatta una descrizione approfondita dell’algoritmo euristico ideato,

motivando le scelte effettuate nella sua progettazione. Vengono inoltre citati alcuni

scenari significativi di applicazione.

Introduzione 6

• Capitolo 6: Descrizione delle scelte implementative, sia per quanto riguarda l’appli-

cazione caricata sui dispositivi ZigBee, sia per i moduli SPQR-RDK in esecuzione

sul robot. Viene inoltre presentata la sperimentazione dell’algoritmo in ambiente

simulato Player/Stage e sul robot reale “Rotolotto”.

• Capitolo 7: Il capitolo illustra i risultati conseguiti, considerando le possibili

estensioni applicabili al sistema realizzato.

Parte I

Concetti fondamentali e stato

dell’arte

7

Capitolo 1

Robot per l’esplorazione

autonoma

I robot sono impiegati nell’industria fin dal 1961, quando la General Motors inserı nella

sua linea di assemblaggio Unimate, un braccio meccanico utilizzato per saldare parti

di automobili. Attualmente essi sono usati ampiamente in applicazioni ripetitive e di

precisione, come il montaggio di componenti su circuiti stampati; ad ogni modo questi

robot sono immobili.

La possibilita di avere robot mobili puo espandere notevolmente gli scenari in cui essi

possono fornire il loro contributo. Una delle applicazioni piu importanti della robotica

mobile consiste nell’esplorazione di ambienti non noti a priori, da parte di uno o piu

veicoli autonomi. Tale esigenza sorge tipicamente ogni qualvolta un robot mobile venga

impiegato per missioni in ambienti sconosciuti od ostili, in cui l’intervento umano sia

difficile o pericoloso (sorveglianza, demining, soccorso, esplorazione planetaria, ecc.).

La capacita di movimento per un robot introduce nuove problematiche: esso deve

conoscere la sua corretta posizione rispetto al mondo reale, in modo da poter scegliere in

modo razionale quale azione compiere. Mediante l’esplorazione autonoma e possibile co-

struire in automatico una mappa accurata dello spazio di lavoro in cui il robot si muove,

a partire dalle misure fornite dai sensori con cui e equipaggiato (laser scanner, sonar, vi-

deocamere, ecc.). Con l’ausilio della mappa costruita e possibile coordinare i movimenti

e gli spostamenti del robot al fine di raggiungere delle zone particolari nell’ambiente di

interesse. Al raggiungimento di questa autonomia comportamentale concorrono quindi

numerosi fattori, che vanno dalla capacita di estrarre informazioni significative dai dati

sensoriali e di costruire un modello (eventualmente dinamico) dell’ambiente circostan-

te, a quella di elaborare, talvolta impiegando sistemi inferenziali, una linea di azione

praticabile, che garantisca il raggiungimento degli obiettivi previsti.

Questo capitolo ha lo scopo di introdurre i concetti e gli strumenti disponibili nel-

l’ambito della robotica, per sviluppare l’approccio descritto in questa tesi. Vengono

8

Capitolo 1. Robot per l’esplorazione autonoma 9

inoltre introdotte alcune conoscenze di base sui robot idonei all’esplorazione autonoma,

mettendo in evidenza l’importanza dei sensori impiegati e dei moduli software necessari

alla navigazione. Una sezione e riservata alla descrizione di alcuni approcci esistenti per

effettuare esplorazione autonoma, mentre la parte conclusiva ha lo scopo di presentare

gli strumenti software disponibili, come i simulatori e il framework per robot mobili,

SPQR-RDK.

1.1 Possibili scenari

Un robot mobile, in grado di esplorare autonomamente un ambiente, introduce sicura-

mente nuove possibilita. Nel seguito vengono descritti alcuni scenari significativi, in cui

essi forniscono il loro importante contributo, sostituendo effettivamente o potenzialmente

operatori umani.

Ambiente domestico e medico Uno dei primi impieghi dei robot mobili e stato quel-

lo di sostituire l’uomo in task ripetitivi in ambiente domestico, come pulire i pa-

vimenti o tagliare l’erba. Uno scenario altrettanto importante e quello di fornire

servizi di assistenza alla persona, in strutture mediche o paramediche (si veda ad

esempio il progetto RoboCare1). All’interno della RoboCup2, esiste da qualche

anno la competizione RoboCup@Home, in cui viene incoraggiato lo sviluppo di

applicazioni robotiche in grado di assistere l’uomo nelle operazioni di tutti i giorni.

Sicurezza L’utilizzo di robot in ambienti dove la sicurezza e importante sta guada-

gnando sempre maggiori spazi, ad esempio in ambienti dove l’intervento umano

e rischioso (demining, operazioni militari) o dove il monitoraggio richiede accura-

tezza e tempestivita (sorveglianza). Altri possibili impieghi prevedono il controllo

ambientale, per rilevare la presenza di sostanze tossiche, fumi o radiazioni in aree

industriali.

Soccorso Gli interventi in emergenza condotti in ambienti disastrati, rischiosi per l’uo-

mo e con tempi limitati sono di vitale importanza per operazioni antincendio, di

salvataggio o di tipo militare. L’utilizzo di robot al posto di operatori umani o

come supporto in tali condizioni puo ridurre drasticamente i rischi possibili. Tali

scenari vengono spesso denominati Search and Rescue e sono il tema principale

della competizione RoboCup Rescue [TKT+00, HSI+99], in cui viene incoraggiato

lo sviluppo e la ricerca nell’ambito del soccorso robotico.1http://robocare.istc.cnr.it.2La RoboCup e una competizione fra robot autonomi a livello mondiale, che si disputa annualmente,

col tentativo di promuovere l’intelligenza artificiale, la robotica e altri campi di ricerca correlati.


Esplorazioni in condizioni estreme La possibilita di progettare robot in grado di

lavorare in qualsiasi condizione, permette di ampliare gli scenari di esplorazio-

ne, estendendoli ad ambienti invivibili per l’uomo, come l’esplorazione planetaria

(si pensi al celebre Sojourner, utilizzato nella missione Pathfinder su Marte) o

subacquea.

1.2 Tipi di robot

Le caratteristiche funzionali e di mobilita che un robot puo possedere dipendono quasi

totalmente dall’ambiente in cui esso si trovera ad operare. Una classificazione comune e

la seguente:

Unmanned Ground Vehicle (UGV): Sono veicoli terrestri, adatti all’esplorazione

di ambienti indoor e outdoor sia strutturati che destrutturati. I piu comuni utiliz-

zano ruote, ma ne esistono vari tipi cingolati e con zampe (i cosiddetti legged) che

consentono di superare le asperita del terreno.

Unmanned Aerial Vehicle (UAV): Si tratta di velivoli o elicotteri, nella maggior

parte dei casi teleguidati. Essi consentono di effettuare esplorazioni dall’alto e

talvolta agire da ripetitori per estendere comunicazioni wireless.

Autonomous Underwater Vehicle (AUV): Sono veicoli per subacquei, in grado di

raggiungere fino a 6000 m di profondita. Attualmente sono ampiamente utilizzati

per il monitoraggio di condutture sottomarine.

In figura 1.1 e possibile osservare alcuni esempi dei robot appena descritti.

1.2.1 Robot del laboratorio SIED

In questa sezione vengo descritti i principali robot presenti nel laboratorio SIED, che

sono stati utilizzati intensivamente per la sperimentazione del lavoro effettuato.

“Piccolotto”

Il robot Piccolotto era in origine un Pioneer P2-DX, ora monta un controller per mo-

tori Videre e un laser scanner Hokuyo URG-04LX, entrambi connessi ad un hub USB

collegato ad un notebook 12′′ IBM, su cui viene eseguito il software di navigazione e

l’interfacciamento mediante Player (descritto al paragrafo 1.5.1). Possiede due ruote

motrici indipendenti nella parte anteriore e una ruota castor omnidirezionale nella parte

posteriore.


(a) Un Pioneer P2-DX (b) Un quadrirotore Asctec X3D-BL

(c) L’HSV Swift della Bluefin Robotics

Figura 1.1: Alcuni robot esploratori

“Rotolotto”

Esso e un Pioneer P2-AT con quattro ruote motrici, disposte a coppie di due, e prende il

suo nome dalla forma dell’onboard PC. Il suo equipaggiamento include un laser scanner

Sick LMS200, sensori sonar e supporto per un’unita pan-tilt con stereocamera.

(a) Il robot “Piccolotto” (b) Il robot “Rotolotto”

Figura 1.2: Alcuni robot mobili presenti nel laboratorio SIED


1.3 Moduli funzionali di un robot esploratore

In figura 1.3 e rappresentata una schematizzazione che rappresenta bene le relazioni

tra i componenti funzionali di un robot idoneo all’esplorazione autonoma, presente in

[SN04]. Da questa si comprende immediatamente l’importanza di sensori e attuatori,

con i quali viene gestita l’acquisizione di informazioni e l’interazione con l’ambiente rea-

le. Mediante l’interpretazione dei dati grezzi provenienti dai sensori, vengono costruiti

modelli rappresentativi dell’ambiente (come ad esempio mappe) e ricavate informazioni

sulla posizione del robot all’interno di esso (localizzazione). In base alla strategia desi-

derata ad alto livello (obiettivi di missione), al fine di permettere al robot di raggiungere

l’obiettivo globale prefissato, i moduli di pianificazione provvedono a stabilire i compiti

da assegnare ai componenti di basso livello, come gli attuatori, in modo da garantire la

corretta navigazione del robot verso i vari target. Va notato che per svolgere attivita

di locomozione autonoma e necessario risolvere una grande varieta di problemi, come il

controllo del movimento (motion control), il superamento di ostacoli e il rilevamento di

situazioni critiche.

Raw data

Environment ModelLocal Map

“Position”Global Map

Actuator Commands

Sensing Acting

InformationExtraction and Interpretation

PathExecution

CognitionPath Planning

Knowledge,Data Base

MissionCommands

Path

Real WorldEnvironment

LocalizationMap Building

Perc

eptio

n

Mot

ion

Cont

rol

Figura 1.3: Schematizzazione di un robot mobile

Nelle prossime sezioni tali componenti verranno descritti singolarmente, fornendo

una panoramica che aiutera a comprendere concetti utilizzati nell’ambito di tutta la

tesi.


1.3.1 Sensori e tecniche per l’esplorazione

Una delle funzioni piu importanti funzionalita di un sistema autonomo e acquisire infor-

mazioni sull’ambiente che lo circonda, utilizzando misurazioni provenienti da vari sensori

ed estraendone informazioni significative. Esiste un’ampia varieta di sensori impiegati

nei robot mobili; alcuni misurano semplici valori come temperature esterne o velocita di

rotazione dei motori. Altri, piu sofisticati, possono essere usati per ricavare la posizione

del robot, ad esempio rispetto agli ostacoli o a punti di interesse per la sua missione.

Dato che il robot e continuamente in movimento, frequentemente incontrera caratte-

ristiche dell’ambiente impreviste, per cui le funzionalita di sensoristica sono alquanto

critiche. Inoltre, dato che ogni sensore acquisisce informazioni incerte sull’ambiente, so-

no necessari strumenti stocastici per mantenere limitate ed accettabili la rumorosita dei

dati. Per una trattazione abbastanza completa sui sensori per robot mobili si consulti

[Eve95].

Nelle sezioni seguenti verranno elencati alcuni dei piu importanti sensori e tecni-

che utilizzate per l’esplorazione e la navigazione; gran parte di essi sono presenti del

laboratorio SIED e installati sui robot utilizzati per gli esperimenti descritti in questa

tesi.

1.3.1.1 Odometria

L’odometria e uno dei metodi piu utilizzati per conoscere la posizione di robot mobili, in

quanto fornisce una discreta precisione su brevi distanze, non ha alti costi di applicazione

ed e facilmente integrabile con altri metodi di localizzazione che invece danno misure

piu accurate.

L’idea di base della ricostruzione odometrica e quello del calcolo della nuova posizione

del robot in base alla strada percorsa rispetto alla posizione precedente (dead-reckoning).

Il calcolo avviene tramite l’integrazione nel tempo dell’informazione sul movimento. Per

ricavare i valori da integrare, l’odometria utilizza degli encoder, attaccati agli assi delle

ruote o all’armatura del motore, che vanno a misurare la velocita di rotazione delle ruote

e l’orientazione dello sterzo (basandosi sul principio che la rotazione compiuta da una

ruota puo essere tradotta in spostamento lineare).

Questo metodo causa inevitabilmente l’accumularsi di errori, soprattutto di orien-

tazione che causano a loro volta errori in posizione, che crescono proporzionalmente

alla distanza percorsa. Gli errori dell’odometria possono essere sistematici (causati ad

esempio da diametri delle ruote diseguali o disallineate) o non sistematici (movimento

su terreno irregolare e slittamenti delle ruote).


1.3.1.2 Sensori inerziali

Come accade per l’odometria, l’utilizzo di sensori inerziali non richiede punti di rife-

rimento assoluti. Essa per calcolare la posizione del robot utilizza invece giroscopi e

accelerometri; i primi misurano la velocita di rotazione, i secondi invece l’accelerazione.

La navigazione inerziale si basa su misurazioni dinamiche, a breve termine, senza

necessita di avere informazioni esterne sulla dinamica del robot, poiche i dati sono ricavati

tramite misurazioni dirette. Il grosso svantaggio nell’impiego di sensori inerziali pero, e

dovuto al fatto che per ottenere l’orientazione e la posizione bisogna integrare una volta

e due volte rispettivamente la velocita di rotazione e l’accelerazione, generando quindi

errori in posizione che crescono in modo integrale col tempo (deriva). Come visto per

l’odometria, la localizzazione mediante questo metodo non e adatta a stime accurate per

un lungo periodo di tempo.

1.3.1.3 Sonar

Il sonar e un dispositivo che sfrutta la propagazione di onde sonore (spesso ultrasuo-

ni) per misurare la distanza da un oggetto. Come e facile osservare in figura 1.4(b),

le onde sonore emesse dal trasmettitore vengono riflesse da eventuali ostacoli e cono-

scendo la velocita del suono (343 m/s alla temperatura di 20◦C), e possibile ricavare la

distanza, misurando il tempo trascorso tra l’emissione e la ricezione dell’onda. Questo

(a) Un sonar per robot mobili

Onda emessa

Onda ri�essa

Sonar

Ostacolo

Distanza

(b) Principio di funzionamento di un sonar

Figura 1.4: Sonar


tipo di tecnica soffre molto dei fenomeni di riflessione (descritti al paragrafo 2.1.3) e cio

dipende soprattutto dall’angolo con cui l’onda colpisce l’oggetto e dal materiale di cui

esso e composto. In movimento tali fenomeni sono ancor piu amplificati e causano una

stima abbastanza grossolana della distanza dagli ostacoli. Numerosi aspetti riguardanti

l’esplorazione con il sonar e alcuni modelli probabilistici sono descritti in dettaglio in

[TBF05].

1.3.1.4 Laser scanner

I laser scanner, chiamati talvolta anche laser rangefinder, possono essere pensati come dei

piccoli sonar che utilizzano la luce invece del suono, per creare una mappa bidimensionale

degli ostacoli che si trovano in prossimita del robot. L’accuratezza, i consumi energetici

ridotti e i costi sempre piu contenuti di questi sensori li rendono preferibili rispetto a

tutti gli altri, per costruire mappe o localizzare il robot.

(a) Alcuni laser scanner

Area non visibile

Area visibileRange minimo

Range massimo

Risoluzioneangolare

(b) Parametri di un laser scanner

Figura 1.5: Laser scanner

Il principio di funzionamento e abbastanza intuitivo; ad ogni scansione vengono emes-

si iterativamente dei raggi laser distanziati di un certo angolo, che dipende dalla risolu-

zione angolare del dispositivo, fino a ricoprire l’apertura massima dello scanner (Field

Of View). Per ogni emissione, si conosce la distanza e l’angolo rispetto al sensore, da

cui puo essere ricavata la posizione dell’ostacolo rispetto alla sorgente di emissione.

I differenti tipi di laser scanner si differenziano essenzialmente in base alla risoluzio-

ne sulla distanza, risoluzione angolare, la frequenza di scansione e al range minimo e

massimo raggiungibile. Parametri tipici per questi sensori sono riportati in tabella 1.1.

Come per i sensori ad ultrasuoni, una fonte rilevante di errore e la riflessione incoe-

rente dell’energia del laser. Con la luce questo accade quando essa colpisce una superficie

molto riflettente; cio si verifica ad esempio con oggetti metallici, di legno lucido e, ov-

viamente, specchi. Inoltre, a differenza del sonar, i laser scanner non possono rilevare


Risoluzione angolare 0.3◦-0.5◦

Field Of View 180◦-240◦

Risoluzione sulla distanza 20 mmFrequenza di scansione 10-20 KHzRange minimo-massimo 20 mm - 70 m

Tabella 1.1: Parametri tipici di un laser scanner

materiali trasparenti come vetro, che talvolta puo essere presente in quantita significative

in alcuni ambienti (come ad esempio i musei).

1.3.1.5 GPS

L’utilizzo di GPS per la localizzazione outdoor e una soluzione abbastanza comune quan-

do non sono presenti altri riferimenti e non e richiesta precisione elevatissima. Il problema

principale del sistema GPS e dovuto al fatto che il ricevitore deve avere comunicazione

con almeno quattro satelliti, tre per la posizionamento e uno per correggere gli sfasa-

menti del clock. Considerando che le trasmissioni sono a bassissima potenza, e richiesta

necessariamente una condizione di Line-Of-Sight con i satelliti. Di conseguenza, in spa-

zi ristretti come ambienti urbani circondati da edifici alti o foreste molto fitte, e poco

probabile ricevere il segnale in modo affidabile. Ovviamente, anche la maggior parte

degli spazi indoor e inadeguata per l’impiego di GPS e per tali motivazioni, esso appare

adeguato solo in progetti di robotica mobile in ampie aree aperte o per essere installato

su UAV.

1.3.1.6 Landmark

I landmark sono oggetti con caratteristiche distintive che il robot puo riconoscere at-

traverso il suo sistema sensoriale, ad esempio mediante visione artificiale [BB82]. In

generale un landmark puo avere una locazione fissa e nota a priori, in base al quale il

robot puo stimare la sua posizione, e viene scelto in maniera tale da essere facilmente

distinguibile rispetto ad altri oggetti per forma o colore (ad esempio contrasta con lo

sfondo).

Esso puo essere naturale, se e un oggetto o una caratteristica gia presente nell’am-

biente che si sta esplorando (come porte, lampade, ecc) o artificiale, se e un marcatore che

deve essere posizionato, con il solo scopo di aiutare la navigazione del robot; per esempio

forme geometriche (linee, poligoni) che possono includere informazioni addizionali (ad

esempio sotto forma di codici a barre). Un vantaggio dei landmark artificiali rispetto a

quelli naturali e che date le loro caratteristiche, note a priori, si possono progettare e

costruire sensori ad hoc per quella determinata applicazione.


L’accuratezza di queste tecniche dipende soprattutto dalla precisione con cui i land-

mark possono essere riconosciuti (matching) e dall’assunzione che posizione e orientazio-

ne siano noti con una buona approssimazione, ad esempio tramite odometria, in modo

tale da diminuire lo spazio di ricerca.

Un esperimento interessante sul riconoscimento di landmark tramite visione artificiale

e riportato in [HLD07], mentre in [ZKNN07] vengono impiegati dei tag a radiofrequenza

(RFID) per stabilire dei punti di coordinamento per squadre di robot, con lo scopo di

suddividere in modo intelligente lo spazio di esplorazione dell’ambiente.

1.3.2 Localizzazione e mappe

La navigazione di un robot mobile nell’ambiente che si sta esplorando richiede la co-

struzione di una mappa; senza di essa il robot non puo ricavare ne la sua posizione ne

quella di eventuali ostacoli. Ad esempio cio e vero per i moderni navigatori basati sul

sistema GPS; quest’ultimo fornisce la posizione del ricevitore nel mondo reale, ma senza

l’uso di una mappa questa informazione non puo essere sfruttata adeguatamente per la

guida dell’autoveicolo fino alla destinazione. In problemi di complessita piu limitata, in

cui l’ambiente e gia noto, il robot puo essere istruito preventivamente mediante map-

pe metriche o topologiche. In generale, il problema di localizzazione con la conoscenza

della mappa dell’ambiente o la stima della mappa a partire dalla conoscenza piu o me-

no precisa della posizione, sono stati affrontati e risolti utilizzando differenti approcci

[FBT99, TFBD00, BEFW97].

Ovviamente le capacita di esplorazione autonoma hanno la possibilita di liberare il

robot dal vincolo di conoscere preventivamente l’ambiente, rendendo possibili applicazio-

ni anche in aree non note a priori. Inoltre, anche se accurate, le mappe fornite al robot

possono non coincidere esattamente3 con l’ambiente in ogni istante a causa di molteplici

fattori: si pensi alla presenza di oggetti e persone in movimento.

In questo tipo di problemi, occorre considerare che mentre il robot cerca di creare la

mappa, deve anche tenere conto della sua posizione, basandosi sulle percezioni dei suoi

sensori. Ne consegue che, per sviluppare un sistema in grado operare in scenari di esplo-

razione, e necessario che l’acquisizione del modello dell’ambiente e la stima della posa

del robot vengano portate avanti concorrentemente (problema chiamato in letteratura

Simultaneous Localization and Mapping - SLAM [DWB06a, DWB06b]), dato che le due

procedure sono fortemente correlate tra loro. Chiaramente, i sensori giocano un ruolo

fondamentale in tutte le forme di localizzazione; e proprio a causa dell’imprecisione e

dell’incompletezza di questi ultimi che la quasi totalita degli approcci a questo problema

sono di natura probabilistica o statistica [CDNDW01, TFB98, SAY99].3Si pensi alle conseguenze che si hanno quando le mappe del proprio navigatore satellitare non sono

correttamente aggiornate!


Nei paragrafi seguenti verranno brevemente analizzate solo le tecniche principali per

la realizzazione di mappe (mapping), mentre verra tralasciato il problema della loca-

lizzazione del robot rispetto all’ambiente, in quanto problema troppo specifico rispetto

alle argomentazioni di questa tesi (per una trattazione abbastanza completa si consulti

[TBF05]). Va comunque notato che ogni differente approccio per il mapping si presta

a rappresentare piu o meno correttamente le diverse tipologie di ambienti (strutturati,

semistrutturati o destrutturati).

1.3.2.1 Feature maps

In generale, una mappa di un ambiente e una lista di oggetti con associate, le loro

posizioni e proprieta (feature):

m = {m1,m2, . . . ,mN} (1.1)

dove N e il numero totale di oggetti.

Nelle feature maps, un generico elemento mn, contiene le proprieta della feature, con

associata la sua posizione geometrica. Spesso si tratta di mappe metriche, caratterizzate

con gli elementi che definiscono l’ambiente come linee, angoli, punti e parametrizzate

in funzione delle dimensioni, colore. In caso di ambienti strutturati (ad esempio un

ufficio), le feature possono essere estratte dalle misurazioni di sonar, laser scanner o da

sistemi di visione artificiale. In caso contrario, l’individuazione e il matching di feature

non e sempre realizzabile e di conseguenza tali mappe non trovano molte applicazioni in

ambienti destrutturati (ad esempio un edificio dopo un crollo).

1.3.2.2 Occupancy grid

Nelle occupancy grid, l’ambiente e suddiviso in una griglia piu o meno accurata, dove

ogni cella contiene un valore che rappresenta la probabilita che essa sia occupata o meno

da un oggetto. Queste mappe possono essere rese piu o meno dettagliate scegliendo la

risoluzione di ogni singola cella. Ovviamente, poiche il numero di celle cresce il modo

quadratico con le dimensioni dell’ambiente da descrivere, lo spazio di memoria necessario

per descrivere delle mappe con precisione sufficiente spesso puo essere molto grande.

Risultano particolarmente adatte per sensori sonar o laser, rappresentando uno stru-

mento valido per filtrare e quindi incrementare l’affidabilita delle misure mediante pro-

babilita condizionate. Tali mappe hanno il vantaggio di descrivere, oltre agli oggetti

presenti nell’ambiente, anche lo spazio libero, risultando adeguate alla navigazione di

robot mobili. Un esempio e riportato in figura 1.6(a). Sempre in riferimento alla nota-

zione 1.1, l’elemento generico mn e riferito ad una particolare posizione sulla mappa; ad

esempio nel caso bidimensionale e piu chiaro indicare mx,y anziche mn per esplicitare il

fatto che mx,y e una proprieta di specifiche coordinate (x, y) del mondo reale.


(a) Esempio di occupancy grid (b) Esempio di mappa topolo-gica

Figura 1.6: Alcuni tipi di mappe

1.3.2.3 Mappe topologiche

La rappresentazione mediante mappe topologiche definisce una relazione diretta tra l’am-

biente e un grafo. Esse sono definite attraverso la struttura dell’ambiente che rappresen-

tano; ogni luogo e caratterizzato in termini di unita funzionali e topologiche (ad esempio

una stanza o un corridoio) tra loro connesse (ad esempio mediante porte o scale). Nel

grafo che viene costruito, i nodi rappresentano i luoghi e gli archi le connessioni per

raggiungerli, risultando in una notazione molto compatta rispetto alle mappe metriche

e piu gestibile computazionalmente (fig. 1.6(b)).

Tuttavia le mappe topologiche hanno anche alcuni svantaggi: in particolare sono

solitamente limitate agli ambienti che possono essere descritti per mezzo di semplici

forme geometriche. Gli ambienti reali solitamente sono complessi e quindi la lista delle

forme degli oggetti e tipicamente incompleta. Un modo per aggirare questa limitazione e

quella di utilizzare mappe ibride, che rappresentano alcune parti dell’ambiente per mezzo

di oggetti e altre utilizzando delle rappresentazioni sullo stile delle occupancy grid.

1.3.3 Navigazione

Per un robot mobile, i moduli di navigazione combinano tutti quelli visti precedentemen-

te (sensoristica, localizzazione, mapping), al fine di decidere passo passo la coordinazione

dei movimenti e quindi dei comandi da fornire agli attuatori. Oltre a garantire che il

robot segua il path scelto fino al target, la navigazione deve saper affrontare scenari

in cui gli ostacoli sono dinamici, la mappa e incompleta e alcune azioni possono fallire

[SN04].

Le varie architetture di navigazione esistenti, suddividono spesso i task in globali e

locali. I primi sono visti come problemi di pianificazione a lungo termine, in cui viene

considerata l’intera rappresentazione dell’ambiente, rilassando alcuni vincoli (come ad

esempio l’esatta forma del robot); i secondi dipendono fortemente dalle letture in tempo


reale dei sensori e devono consentire al robot di evitare ostacoli (obstacle avoidance),

modulando opportunamente la sua traiettoria.

Spesso pianificazione e reazione sono visti come approcci opposti. In realta, quando

applicate a sistemi fisici come i robot mobili, essi sono complementari e ognuno e critico

per il successo dell’altro. Il problema di navigazione richiede l’esecuzione di un insieme

di azioni (o un piano) per raggiungere il target. Durante l’esecuzione, il robot deve

tuttavia reagire ad eventi imprevisti in modo tale da poter garantire il raggiungimento

dell’obiettivo globale. Senza reazione, lo sforzo della pianificazione non fornisce i risultati

sperati dato che il robot non raggiungera fisicamente il goal, bloccandosi prima, mentre

senza pianificazione, le funzioni di reazione non riusciranno mai a guidare il robot verso

un obiettivo distante.

1.3.3.1 Pianificazione

Un componente importante per garantire al robot di raggiungere un determinato obiet-

tivo e il path planning. In questo tipo di problemi, l’agente deve spostarsi da un punto di

partenza (start) ad un punto di arrivo (target), senza collidere con ostacoli dell’ambiente

circostante. Esso e essenzialmente un problema di ricerca, in cui viene scelta una tra le

sequenze di configurazioni che portano il robot dallo start al target, possibilmente quella

che minimizza la lunghezza del cammino. Lo spazio di ricerca e l’insieme di tutte le

possibili configurazioni del robot e la dimensione di questo insieme aumenta esponen-

zialmente con il numero di gradi di liberta del robot; la crescita rapida dello spazio di

ricerca e una delle maggiori difficolta nel path planning.

Una prima distinzione tra path planner puo essere fatta tra quelli deliberativi e reat-

tivi. La pianificazione deliberativa puo essere usata nelle situazioni in cui si assumono

come noti a priori l’ambiente e la posizione del robot, generando, se esiste, una tra-

iettoria che consente di evitare gli ostacoli, eventualmente ottimizzando un opportuno

indice di prestazione. La pianificazione reattiva e un requisito fondamentale per i robot

autonomi che passano ciclicamente dalla fase di pianificazione a quella di movimento

(fig. 1.3). Quelli piu avanzati, cercano di adattare il percorso ai cambiamenti improvvisi

nell’ambiente. In generale, occorre combinare questi due tipi di approcci, utilizzando

un pianificatore deliberativo basato sulla mappa dell’ambiente disponibile e poi, quando

il robot sta inseguendo la traiettoria pianificata, utilizzare un pianificatore reattivo in

grado di evitare il contatto con ostacoli precedentemente ignoti, mediante tecniche di

obstacle avoidance.

I metodi utilizzati per il path planning possono essere classificati in base al tipo

di decomposizione effettuata sull’ambiente, trasformandolo dal dominio nel continuo a

quello discreto. I metodi principali sono quelli a roadmap, a decomposizione di celle e a

campi di potenziale [SN04, Doy95].


Gli approcci a roadmap cercano di stabilire la connettivita da un insieme di configu-

razioni libere per il robot, per formare una rete di curve o linee unidimensionali chiamate

roadmap. La ricerca del path si riduce al problema di trovare una connessione tra i punti

start e target sulla roadmap, cercando quella ottima.

I metodi basati su decomposizione di celle sono ampiamente utilizzati e prevedono

di suddividere l’insieme delle configurazioni in regioni non sovrapposte, chiamate celle.

La relazione di adiacenza tra queste celle e rappresentata da un grafo di connettivita,

in cui i nodi sono le celle libere e gli archi mostrano appunto l’adiacenza tra esse. In

questo grafo viene cercato il path, seguendo le celle libere dal punto di partenza a quello

di arrivo. Il problema principale e che tutte le celle e il grafo di connettivita devono

essere costruiti, prima che il path venga trovato, e per alti gradi di liberta del robot, la

dimensione dello spazio di ricerca diventa rapidamente intrattabile.

Gli approcci a campi di potenziale utilizzano generalmente l’idea della presenza di un

potenziale repulsivo vicino agli ostacoli e attrattivo vicino all’obbiettivo. Il gradiente dei

potenziali guida il path lontano dagli ostacoli, mentre cerca di avvicinarlo all’obiettivo.

Lo svantaggio maggiore di questi metodi e che spesso la pianificazione porta a dei minimi

locali, causando la presenza di soluzioni non complete.

1.4 Esplorazione autonoma

L’esplorazione in autonomia di un’area sconosciuta e uno dei problemi fondamentali della

robotica mobile. Per la costruzione di un modello dell’ambiente consistente, il robot

deve essere in grado di esplorarlo efficientemente, individuando la posizione di ostacoli,

di oggetti e dello spazio libero, mediante l’utilizzo dei sensori e delle tecniche descritte al

paragrafo 1.3.1. L’esplorazione risulta necessaria in molte applicazioni; per la costruzione

della mappa il robot deve esplorare l’ambiente e la stessa cosa accade in scenari di Search

and Rescue, per trovare persone in situazioni di pericolo. Soprattutto per cercare un

punto di interesse in un ambiente non noto a priori, e necessario effettuare esplorazione

cieca se non si hanno informazioni aggiuntive sulla localizzazione dell’oggetto da trovare,

procedendo praticamente per tentativi.

Una buona strategia di esplorazione dovrebbe essere efficiente, per coprire l’ambiente

velocemente, accurata, per consentire la costruzione di mappe consistenti e adattabile,

in grado da poter essere utilizzata in diversi tipi di ambiente (ad esempio in spazi aper-

ti come in uffici). Durante l’esplorazione quindi, si possono avere diversi obiettivi da

ottimizzare, come ad esempio massimizzare l’area ricoperta in un intervallo di tempo

[Yam98] o incrementare l’autonomia energetica del robot [MLLH06]. A tal fine risul-

tano determinanti le scelte, fatte ad ogni passo, con lo scopo di decidere il prossimo

target da esplorare e verso cui il robot deve spostarsi. Nella maggior parte degli approc-

ci [BMF+00, KPN, MLLH06], il target e selezionato fra i punti di frontiera [Yam97],


che si trovano cioe sulla linea di confine tra lo spazio esplorato e quello non esplorato

(per un approfondimento al riguardo, si rimanda al paragrafo 5.1.2). Alcuni approcci, si

basano su wall-following [Mat92, XKC97], risultando validi solo in ambienti di limitata

complessita strutturale, altri ancora sul riconoscimento di landmark [TK93].

La scelta della frontiera spesso viene effettuata tenendo in conto utilita e costi del-

la stessa, in altri casi addirittura avviene casualmente (procedendo per random walk

[Thr95]). L’utilita puo essere stimata in base alla dimensione dell’area coperta dalla

frontiera [SB03], mentre il costo puo considerare gli spostamenti o le rotazioni necessarie

al robot per raggiungerla [Yam97, MTK]. Tipicamente vengono utilizzate delle strategie

greedy, selezionando il target in modo che l’area potenziale ricoperta sia massima e con

minor costo. In altri casi si considera la quantita di informazione ottenibile da differenti

viewpoint (problema chiamato next-best-view [GBL01]).

1.5 Simulatori

Alla complessita di un robot mobile contribuisce sicuramente l’alto numero di sensori

presenti e la capacita di movimento e interazione nell’ambiente. Per uno sviluppatore,

la possibilita di testare i propri algoritmi in un sistema di simulazione, comporta sicu-

ramente molti vantaggi in termini di costi e tempi di implementazione. Per non parlare

delle opportunita che nascono in ambito multi-robot, in quanto e possibile avere con-

temporaneamente presenti diverse tipologie di robot, considerando che tale scenario non

sempre e realizzabile nella pratica.

Durante la realizzazione della tesi e stato possibile vederne in dettaglio sostanzial-

mente due: l’accoppiata Player/Stage [GVS+01] e USARsim [WLG03]. Essi verranno

brevemente descritti nelle sezioni seguenti.

1.5.1 Player/Stage/Gazebo

La piattaforma Player/Stage e conseguenza di un progetto open-source, iniziato nel 2000

ad opera di Brian Gerkey, Richard Vaughan, Andrew Howard e risulta una delle interfac-

ce piu utilizzate dalle universita e aziende che si occupano di robotica mobile. Essa puo

essere considerata come due componenti indipendenti di un ambiente di simulazione.

Player ha un’architettura che consente di controllare con un paradigma client/server

il robot e i suoi sensori/attuatori, mediante messaggi scambiati tramite TCP/IP. Esso

fornisce un’interfaccia, indipendente dal linguaggio di programmazione, nei confronti di

dispositivi hardware, come laser scanner e sonar, grazie ai numerosi driver sviluppati

dalla comunita.

Stage invece puo essere considerato come una plugin per Player e permette di si-

mulare un ambiente multi-agente con una rappresentazione bidimensionale, utilizzando

ad esempio da una mappa bitmap. Esso comprende un insieme di dispositivi che rende


disponibili a Player e che possono essere assemblati per costituire un robot personaliz-

zato: questa particolarita permette di sperimentare in simulazione dispositivi che non

sono disponibili sul robot nella realta. Inoltre i client solitamente non percepiscono la

differenza tra i dispositivi reali e quelli equivalenti simulati da Stage e cio permette di

passare semplicemente, e spesso senza modifiche, dal mondo reale a quello simulato e

viceversa.

E presente anche un’estensione (Gazebo), che consente di ampliare le possibilita di

Player ad ambienti tridimensionali.

(a) Player/Stage (b) USARsim

Figura 1.7: Simulatori per robot mobili

1.5.2 USARsim

USARsim (Unified System for Automation and Robot Simulation) e un simulatore ad

elevato realismo, orientato agli ambienti tridimensionali e soprattutto a scenari di soc-

corso robotico, in particolare in ambito Urban Search And Rescue (USAR). Esso e

basato sull’engine grafico Unreal2 del videogame Unreal Tournament 2004 di Epic Ga-

mes e sull’API GameBots, per fornire un buon rendering grafico e allo stesso tempo una

modellazione fisica realistica.

In USARsim sono presenti numerose riproduzioni di ambienti con disastri, modelli di

robot (sia commerciali che sperimentali) e sensori. Inoltre, e possibile costruire il proprio

ambiente di simulazione, controllando tutto tramite una API basata su socket per testare

gli algoritmi e interfacce utente, senza necessita di programmazione addizionale.

Esso e inoltre il simulatore di riferimento utilizzato nella competizione RoboCup

Rescue Virtual [TKT+00], data la sua capacita di riprodurre realmente scenari con

differente grado di destrutturazione, per valutare le prestazioni di squadre di robot nella

cooperazione, ricerca di vittime e mapping dell’ambiente.


1.6 Il framework SPQR-RDK

La piattaforma SPQR-RDK (Software Per Qualunque Robot-Robot Development Kit)

e stata progettata e successivamente estesa, all’interno del Dipartimento di Informati-

ca e Sistemistica “Antonio Ruberti” (DIS), dell’Universita di Roma “Sapienza”. Essa

permette una semplicita di sviluppo e debugging, con al contempo buone capacita di

modularizzazione dei nuovi componenti che gradualmente vengono implementati. Essa e

composta da un insieme di librerie software, driver di basso livello, moduli per compor-

tamenti ad alto livello, interfacce verso gli agenti robotici ed utility grafiche di ausilio per

l’operatore. Inoltre, come il nome stesso indica, e possibile impiegarla in diversi sistemi

robotici e soprattutto nella robotica mobile. Attualmente l’SPQR-RDK viene impiegato

nella competizioni Robocup Soccer e Rescue, ed e possibile interfacciarlo a vari tipi di

robot (dai Pioneer della ActiveMedia Robotics agli Aibo della Sony).

SPQR-RDK e sviluppato interamente in C++ ed e disponibile per piattaforme

Unix (Linux, Mac OS X). Per una descrizione generale si consulti [FGI05]. Nei pa-

ragrafi seguenti viene illustrata la struttura del framework, mettendone in evidenza le

caratteristiche principali.

1.6.1 Agenti e moduli

In SPQR-RDK, l’entita principale e l’agente, un processo software che rappresenta il

robot. In esso possono essere caricati dinamicamente moduli, ognuno eseguito nel pro-

prio thread di esecuzione. La possibilita di avere un ambiente multi-thread, permette di

eseguire differenti task concorrentemente e di creare gerarchie produttore-consumatore.

Ad esempio, un generico agente, puo avere un modulo dedicato al ricevere i dati prove-

nienti da odometria e laser scanner, un modulo che con tali informazioni ha il compito

di eseguire lo scan-matching per stimare la posizione dell’agente e infine un modulo che

utilizzando tale stima e le scansioni del laser costruisce la mappa dell’ambiente.

La configurazione di un agente e dei suoi moduli e abbastanza intuitiva, in quanto e

sufficiente scrivere un file di configurazione XML-based che contiene l’elenco dei moduli

impiegati, settando opportunamente i relativi parametri.

1.6.2 Repository

Lo scambio di dati tra moduli avviene per mezzo di una memoria condivisa, denominata

repository. Nel repository si trovano tutte le proprieta che un modulo condivide con gli

altri. Esse sono organizzate in una struttura gerarchica ad albero, individuate tramite

uno specifico URL4. Le connessioni di dati tra moduli (ad esempio input-output) ven-

gono realizzate collegando le proprieta di un modulo a quella dell’altro, attraverso una4Ad esempio, la coda contenente i dati provenienti dal laser scanner, e individuata dall’URL:

rdk://agent/laserModule/laserQueue.


opportuna notazione sul file di configurazione. Tale accesso attraverso i collegamenti

risulta totalmente trasparente al programmatore, che vede la proprieta collegata come

locale al suo modulo.

1.6.3 Concorrenza

Lavorando in un ambiente multi-thread bisogna prestare particolare attenzione a pro-

blemi di sincronizzazione e concorrenza tra i differenti moduli. A run-time ogni modulo

(thread) puo trovarsi in attesa di molteplici eventi, come lo sblocco di un semaforo o

di un mutex, la scadenza di un timer o l’aggiornamento di una proprieta. Inoltre, e

possibile prevedere differenti tipi di accesso condiviso, tramite l’oggetto session, che ha

la responsabilita di governare il corretto utilizzo del repository; e possibile impostare

il locking e unlocking automatico o manuale di proprieta, a seconda delle esigenze del

programmatore.

1.6.4 Comunicazioni tra agenti

Allo stesso modo in cui avviene lo scambio dati tra diversi moduli, anche la condivi-

sione di informazioni tra diversi agenti avviene mediante il repository. Essa puo essere

realizzata mediante condivisione di proprieta o invio e la ricezione di messaggi.

Nel primo caso, un agente (subscriber) interessato ai dati di un altro (publisher): egli

indica il proprio interesse sempre mediante un collegamento alla proprieta, specificando

nell’URL anche il nome dell’agente. Il subscriber puo ricevere notifiche periodicamente

o in seguito ad un aggiornamento della proprieta.

L’invio e la ricezione di messaggi viene supportato da appositi oggetti mailbox, con

cui e possibile scambiarsi informazioni in modo asincrono.

1.6.5 Strumenti di supporto

RConsole

RConsole e una potente interfaccia grafica che permette di avere sotto controllo lo stato

dei moduli in esecuzione, visualizzando mediante appositi widget i valori dei parametri,

immagini, mappe e video prelevato da videocamere. Alcuni speciali controlli, permettono

di fornire in tempo reale comandi al robot, come ausilio a task eseguiti in teleoperazione.

Logging e reporting

In un framework di tale complessita, non possono mancare strumenti avanzati di logging

e di reporting, utilizzati ad esempio per esportare dati provenienti da sensori e utilizzabili

in altri software di elaborazione.


Interfacce con i simulatori

Alcuni moduli dell’SPQR-RDK permettono di interfacciarsi con i piu comuni simulatori

per la robotica mobile, come USARsim e la piattaforma Player/Stage/Gazebo (par.

1.5.1). Tutto avviene sempre in maniera trasparente, impostando i diversi parametri

dal file di configurazione e mantenendo la stessa interfaccia di accesso, in modo che altri

moduli possono continure ad interagire senza particolari modifiche nel codice.

Capitolo 2

Localizzazione basata su

dispositivi wireless

La localizzazione di un dispositivo all’interno di WSN e un aspetto sempre piu rilevante

[MFA07], in quanto consente di associare alla misurazione il luogo in cui si e verificata.

Ovviamente la precisione con cui la posizione viene rilevata dipende dallo specifico con-

testo applicativo: ad esempio per localizzare persone all’interno di un ufficio e sufficiente

sapere in quale stanza si trovano, mentre in uno scenario di monitoraggio di merci in un

magazzino si potrebbe essere interessati in quale particolare imballaggio e stata superata

una soglia di temperatura critica. L’informazione sulla posizione e importante anche in

fasi di amministrazione e configurazione, considerato l’elevato numero di nodi che la rete

puo contenere1.

I differenti metodi di localizzazione si differenziano oltre per la precisione che riesco-

no a raggiungere, anche per la complessita richiesta per implementarli. Alcuni di questi

fanno delle assunzioni sulla struttura dell’ambiente (indoor/outdoor), sulla configurazio-

ne della rete (ad esempio a griglia) o sulla presenza di nodi con posizione nota a priori

(detti beacon).

Si puo facilmente immaginare come, l’aggiunta di informazioni sulla localizzazione

utilizzando una WSN, possa essere agevolmente integrata su una squadra di robot mobili,

fornendo indicazioni sulla posizione che possono risultare utili sia in fase di creazione

di una mappa globale, sia per coordinare l’esplorazione dell’ambiente da parte della

squadra. In questo modo, ogni robot, puo avere una visione globale del problema,

riuscendo ad evitare azioni che non creano vantaggio per il raggiungimento dell’obiettivo,

come ad esempio visitare una zona gia esplorata.

Lo scopo principale di questo capitolo, e quello di mostrare lo stato dell’arte nei

metodi di localizzazione wireless, in particolar modo utilizzando segnali radio. Lo studio1In casi particolari, una WSN, puo essere composta da diverse migliaia di nodi

27

Capitolo 2. Localizzazione basata su dispositivi wireless 28

effettuato, ha permesso inoltre di comprendere in dettaglio i problemi e i fenomeni fisici

da tenere in considerazione nella realizzazione di un sistema di localizzazione.

Localizzazione wireless

La localizzazione wireless e implementata principalmente utilizzando le tre seguenti

tecnologie:

Infrarossi L’infrarosso e una radiazione elettromagnetica con una lunghezza d’onda

maggiore della luce visibile, ma minore delle onde radio. Molti oggetti come

persone, motori di veicoli e aerei generano e rilasciano calore, e come tali, sono

particolarmente visibili alle lunghezze d’onda infrarosse rispetto agli oggetti sullo

sfondo. Il problema principale di questo tipo di localizzazione e l’impossibilita di

oltrepassare muri ed ostruzioni. Inoltre, in ambienti indoor, si aggiunge il disturbo

provocato dall’illuminazione artificiale; la portata di un sistema a infrarossi non

supera i 5 metri, sebbene con una buona precisione (qualche centimetro).

Ultrasuoni Sebbene gli ultrasuoni lavorino a basse frequenze (tipicamente sotto i 20

kHz), essi forniscono una buona precisione per la localizzazione a una bassa ve-

locita di propagazione del suono (343 m/s). I loro vantaggi sono principalmente

la semplicita e il basso costo. Gli ultrasuoni comunque, non penetrano i muri,

vengono riflessi dalla maggior parte degli ostacoli presenti in ambienti indoor e

variazioni di temperatura possono influenzarne le performance. Il range di utilizzo

puo oscillare tra i 3 e i 10 metri, con una risoluzione anche al centimetro.

Radiofrequenze Rispetto alle tecnologie citate precedentemente, i segnali radio posso-

no penetrare la maggior parte dei materiali da costruzione, riuscendo ad ottenere

un ottimo range in ambienti indoor rispetto agli infrarossi e agli ultrasuoni. Pur-

troppo questo tipo di localizzazione risente di fenomeni di attenuazione, rifrazione,

diffrazione e multipath che verranno approfonditi nel paragrafo 2.1.

Di seguito, verranno presentati innanzitutto i diversi fenomeni fisici che si verificano nella

propagazione del segnale elettromagnetico e, successivamente, vari approcci al proble-

ma di localizzazione, mettendo in evidenza le possibilita di applicabilita degli stessi e le

problematiche con il quale devono confrontarsi. Verranno considerati esclusivamente gli

approcci basati sulla propagazione del segnale radio, in quanto in ambienti indoor, sono

gli unici che non richiedono la condizione di Line-of-Sight (LoS)2 e risentono relativa-

mente poco delle variazioni di temperatura e illuminazione. Considerando che spesso la

posizione trovata e solo approssimata, si parla anche di stima di localizzazione (location

estimation).2Ovvero la propagazione del segnale elettromagnetico secondo una linea retta immaginaria che collega

il trasmettitore e il ricevitore


2.1 Fenomeni nella propagazione radio

Nella localizzazione basata su segnali radio, e importante conoscere le proprieta di propa-

gazione della radiazione elettromagnetica. Fenomeni come attenuazione, rifrazione, scat-

tering e diffrazione hanno un ruolo rilevante, soprattutto in ambienti urbani o indoor. Le

sezioni successive si occupano di descrivere gli aspetti fondamentali della propagazione

di onde radio, analizzando anche alcuni modelli di propagazione.

2.1.1 Attenuazione dello spazio libero

L’attenuazione dello spazio libero (free-space loss), rappresenta la perdita di potenza dal

parte del segnale elettromagnetico che si ottiene in condizioni di LoS attraverso il vuoto,

senza nessun ostacolo che causi riflessione, assorbimento o diffrazione.

Un’antenna isotropa trasmette una potenza Ptx con la stessa intensita in tutte le

direzioni, ma la potenza riguarda un’area sempre maggiore man mano che l’onda si

allontana dall’antenna. Essendo 4πr2 la superficie della sfera di raggio r, la potenza S

che attraversa un m2 di superficie sferica ortogonale alla direzione di propagazione e:

S =Ptx

4πr2.

Tutte le antenne reali hanno tutte un guadagnoGtx per ogni direzione di propagazione, di

cui va tenuto conto nel calcolo dell’energia irradiata in quella direzione, per cui la potenza

prodotta da un’antenna reale, che attraversa l’area di un m2 normale alla direzione

di propagazione, risulta, di fatto, moltiplicata per il guadagno di detta antenna nella

direzione della propagazione:

S =Gtx · Ptx

4πr2.

Volendo calcolare poi la potenza Prx raccolta da un’antenna di area equivalente3:

Aeq =λ2 ·Grx

4π,

dove λ e la lunghezza d’onda, si ottiene:

Prx = S ·Aeq =Gtx · Ptx

4πr2· λ

2 ·Grx

4π=Ptx ·Gtx ·Grx · λ2

(4πr)2. (2.1)

Poiche il termine:

Asl =(

4πrλ

)2

3Tale fattore dipende dalla dimensione e dalla forma dell’antenna, rappresenta l’area effettiva su cuiil segnale incide in ricezione.


si chiama attenuazione dello spazio libero, l’equazione 2.1 si trasforma in:

Prx =Ptx ·Gtx ·Grx

Asl, (2.2)

detta anche equazione di Friis. Solitamente le grandezze in sono espresse in decibel, per

cui la 2.2 diventa:

Prx[ dBm] = Ptx[ dBm] +Gtx[ dB] +Grx[ dB]−Asl[ dB].

L’equazione di Friis per l’attenuazione dello spazio libero mostra che la potenza in

ricezione decresce con il quadrato della distanza, ovvero di 20 dB/decade. Ovviamente

se le condizioni di visibilita tra trasmettitore e ricevitore vengono a mancare, la potenza

del segnale ricevuto e significativamente minore di quanto l’equazione per l’attenua-

zione dello spazio libero indica. Inoltre, non necessariamente essa fornisce una buona

approssimazione anche in condizioni di LoS [Rap01].

2.1.2 Assorbimento

In qualsiasi sistema di comunicazione, il segnale si propaga in un mezzo trasmissivo.

Nel caso di sistemi wireless terrestri il mezzo e principalmente l’atmosfera e, in piccola

misura, materiali come vetro, calcestruzzo, legno, ecc. In seguito alle interazioni con

essi, il segnale perde parte della sua energia per ogni unita di distanza in cui si propaga.

Pertanto, l’assorbimento provoca una diminuzione di potenza proporzionale a γ−d, dove

d e la distanza e γ e una costante che dipende dalle proprieta del mezzo e dalla frequenza.

Ragionando in db, questo significa che la perdita di segnale e lineare con la distanza.

L’assorbimento e particolarmente alto per frequenze oltre i 10 GHz; in questa situa-

zione, a causa dell’atmosfera, esso diventa comparabile all’attenuazione, specialmente

durante piogge e con distanze considerevoli. Con le frequenze usate nella maggior parte

dei sistemi di comunicazione wireless (al di sotto dei 10 GHz), l’assorbimento atmosferico

e quasi trascurabile per distanze entro i 10 km.

2.1.3 Rifrazione

Il fenomeno di rifrazione si verifica quando l’onda incontra un ostacolo con dimensioni

maggiori della lunghezza d’onda. La parte di essa che non e riflessa perde parte della sua

energia in assorbimento e cio che rimane riesce ad attraversare il materiale riflettente.

Nelle comunicazioni terrestri le onde sono riflesse dal terreno, producendo due percorsi

tra il trasmettitore e il ricevitore, come mostrato in figura 2.1; il piano di incidenza e

definito come il piano contenente il raggio incidente e quello riflesso, mentre l’angolo

di incidenza α e l’angolo tra la superficie riflettente e il raggio incidente. Il segnale al

ricevitore arriva quindi come due componenti, con differente fase, che nel caso peggiore


βα

Ricevitore

Trasmettitore

Figura 2.1: Fenomeno di rifrazione

possono annullarsi. L’intensita del segnale riflesso dipende dal coefficiente di riflessione

di Fresnel che a sua volta dipende dalle proprieta del materiale riflettente, dalla frequenza

e dall’angolo di incidenza α. L’asperita della superficie causa la dispersione dell’onda

in piu direzioni e quindi il suo coefficiente di riflessione e minore rispetto a un’altra

identica ma liscia; in generale esso e differente per la componente orizzontale e verticale

dell’onda. In tali casi, la riflessione puo cambiare la polarizzazione.

2.1.4 Scattering

Lo scattering (dispersione) consiste in una deviazione delle onde elettromagnetiche dalla

loro direzione di provenienza a causa delle continue riflessioni che esse subiscono incon-

trando molecole di gas, pulviscolo, gocce d’acqua ed altri elementi. Tale fenomeno si

verifica quando l’ostacolo ha dimensioni pari o inferiori alla lunghezza d’onda del segna-

le. L’energia radiante viene diffusa in tutte le direzioni, in modo piu o meno accentuato,

facendole perdere la sua caratteristica di unidirezionalita. Gli effetti quantitativi dello

scattering dipendono moltissimo dal rapporto fra la lunghezza d’onda delle radiazioni e

le dimensioni fisiche delle particelle con cui interagiscono.

2.1.5 Diffrazione

In base al principio di Huygens, tutti i punti di fronte d’onda sono sorgenti di onde

secondarie che si propagano in tutte le direzioni. Inoltre, ogni volta che un’onda radio

colpisce uno spigolo come un angolo di un edificio, l’onda si incurva e continua a propa-

garsi nell’area oscurata da esso. Tale effetto viene chiamato diffrazione. In figura 2.2 il

trasmettitore e situato vicino a un ostacolo; le frecce descrivono la direzione di propa-

gazione quando il segnale si trova vicino allo spigolo, dovuta alle sorgenti secondarie del

fronte d’onda che si creano nei pressi dell’ostacolo.

Piu l’onda deve curvare intorno allo spigolo, piu essa perde energia. Quindi l’area

in cui il segnale curva maggiormente guadagnano relativamente meno potenza rispetto


all’area in cui il segnale procede quasi linearmente. La potenza del campo generato dalle

onde secondarie e inferiore rispetto a quello delle onde primarie; in pratica quest’ultime

possono essere trascurate se esiste una condizione di LoS tra il trasmettitore e il ricevito-

re. Il fenomeno della diffrazione viene sfruttato, ad esempio, per realizzare comunicazioni

radio oltre le montagne, quando un path LoS non e disponibile; ovviamente la potenza

di trasmissione dovra essere molto maggiore rispetto ad una trasmissione LoS.

Figura 2.2: Fenomeno di diffrazione

2.1.6 Multipath

La conseguenza diretta di tutti i fenomeni citati precedentemente e il multipath. Tale

effetto si verifica in conseguenza agli effetti di riflessione, diffrazione e scattering delle

onde nell’ambiente, che giungono al ricevitore come somma delle copie delle onde stesse.

Questo fatto puo essere determinato, per esempio, nel caso delle trasmissioni tra cellulari,

dal fatto che il trasmettitore o il ricevitore si spostano continuamente costringendo le

onde elettromagnetiche ad effettuare percorsi continuamente variabili con attenuazioni

quindi diverse.

Il risultato piu rilevante del multipath e il fading, ovvero il fatto che molteplici copie

del segnale arrivano sovrapposte al ricevitore, con differente fase, ritardo e attenuazione,

rendendo possibile la somma distruttiva delle stesse e causando interferenza intersimbolo.

Il segnale ricevuto e spesso modellato con l’effetto combinato di slow e fast fading.

La componente di slow fading descrive l’attenuazione e l’assorbimento del segnale prima

dell’arrivo al ricevitore; solitamente ha una distribuzione lognormale. Il fast fading

modella invece gli effetti dovuti al multipath. Se esiste almeno un percorso dominante

in condizioni di LOS, quest’ultimo viene rappresentato con una distribuzione di Rician,

altrimenti viene utilizzata la distribuzione di Rayleigh quando tale condizione non si

verifica.

Il fading inoltre, puo essere selective o flat, in base al fatto che tale fenomeno interessi

particolari frequenze oppure si verifichi uniformemente su tutto lo spettro. Maggiori

dettagli sul fading possono essere trovati in [Rap01, Sey00].


2.2 Modelli di propagazione

La predizione della propagazione delle onde radio e molto utile in attivita come link bud-

geting, cell planning e appunto la localizzazione. I modelli di propagazione sono utilizzati

per prevedere le proprieta delle onde che si propagano, la qualita del segnale ricevuto

e la sua variabilita. E possibile inoltre predire polarizzazione, dispersione temporale e

selettivita in frequenza.

Gli aspetti teorici menzionati nei paragrafi precedenti possono essere tenuti da conto

in vari livelli di astrazione, in base alla quantita di informazioni disponibili sull’am-

biente e all’accuratezza richiesta dal modello. Per esempio, durante la pianificazione

di una comunicazione satellitare o in generale di collegamenti estesi su decine di chilo-

metri, una buona precisione e spesso ottenuta considerando l’attenuazione (path-loss),

l’assorbimento e la riflessione della terra. Diversamente, in aree urbane, riflessione e dif-

frazione causati dagli edifici e lo scattering provocato ad esempio da alberi, hanno una

forte influenza sulla propagazione del segnale. In base alle informazioni sull’ambiente

che abbiamo a disposizione possiamo tra tre tipi di modelli:

Empirici Si basano principalmente su statistiche derivanti da misurazioni e su pochi

parametri. Sono abbastanza semplici e non molto accurati. In generale e possibile

applicarli anche in ambienti differenti.

Deterministici Sono realizzati ad-hoc per un particolare ambiente e richiedono un’e-

norme quantita di dati geometrici su di esso. Spesso sono computazionalmente

molto costosi anche se abbastanza accurati.

Semi-deterministici Basati su modelli empirici, considerando anche aspetti determi-

nistici.

In ambienti urbani, uno dei modelli piu utilizzati, e quello di Okumura-Hata [Sau00].

Esso include un insieme di curve che indicano il path-loss, prendendo in considerazione

l’attenuazione e un fattore di correzione. Quest’ultimo e ricavato da una funzione della

distanza e della frequenza del segnale. Tale modello e applicabile quando le frequenze di

trasmissione sono comprese tra i 150 e i 1500 MHz, con distanze tra 1 e 10 chilometri.

In ambienti indoor le distanze che separano il trasmettitore e il ricevitore sono molto

minori (nell’ordine dei 100 metri) ma i fenomeni fisici visti precedentemente si verificano

con molta piu variabilita. Il tipo di edificio, i suoi materiali da costruzione, le posizioni

delle antenne, possono influenzare in modo rilevante il path-loss. In tali ambienti risul-

tano interessanti l’ITU Model for Indoor Attenuation e il Log-Normal Shadowing Model

che approfondiremo nelle sezioni seguenti.

Essi si basano sul principio generico, descritto dall’equazione di Friis (equazione 2.2),

per cui la potenza del segnale in ricezione decresce proporzionalmente a d−np , sia in


Frequenza Abitazione Ufficio Area commerciale900 MHz - 33 201.2 GHz - 32 221.3 GHz - 32 221.8 GHz 28 30 224 GHz - 28 22

5.2 GHz - 31 -

Tabella 2.1: Valori del parametro N nell’ITU Model

Frequenza Numero di piani Abitazione Ufficio Area commerciale900 MHz 1 - 9 -900 MHz 2 - 19 -900 MHz 3 - 24 -1.8 GHz n 4n 15+4(n-1) 6+3(n-1)2.0 GHz n 4n 15+4(n-1) 6+3(n-1)5.2 GHz 1 - 16 -

Tabella 2.2: Valori del parametro Pf (n) nell’ITU Model

ambienti indoor che outdoor, dove d e la distanza tra trasmettitore e ricevitore, mentre

np e detto esponente di path-loss ed assume valori tipicamente tra 2 e 44. Il path-loss

alla distanza d (PL(d)[ dB]) e modellato come:

PL(d) = P0 − 10np logd

d0, (2.3)

dove P0[ dB] e la potenza ricevuta alla distanza di riferimento d0[ m].

ITU Model for Indoor Attenuation

L’ITU Indoor Propagation Model [IR01], e un modello di propagazione del segnale che

stima il path-loss dentro un edificio delimitato da muri di qualsiasi forma e materiale.

Esso prende in considerazione anche l’attenuazione fra diversi piani dell’edificio (fino a

3) ed e adatto per segnali a frequenze comprese tra i 900 MHz e i 5.2 GHz. L’equazione

caratteristica del modello e la seguente:

L = 20 log f +N log d+ Pf (n)− 28,

dove L e l’attenuazione totale [dB], f e la frequenza di trasmissione [MHz], N e il

coefficiente di perdita di potenza con la distanza, d e la distanza [m], n e il numero

di piani che separano trasmettitore e ricevitore e Pf (n) e il fattore di penetrazione del

piano. N e Pf (n) sono ricavati empiricamente; alcuni valori sono elencati nelle tabelle

2.1 e 2.2.4np = 2 nello spazio libero e maggiore di 2 in presenza di ostruzioni


Ambiente Frequenza 10γ σ

Negozio 914 MHz 22 8.7Alimentari 914 MHz 18 5.2

Ufficio con muri spessi 1.5 GHz 30 7Ufficio con muri 900 MHz 24 9.6Ufficio con muri 1.9 GHz 26 14.1Tessile o chimico 1.3 GHz 20 3.0Tessile o chimico 4 GHz 21 7.0-9.7

Metallico 1.3 GHz 16 5.8Metallico 1.3 GHz 33 6.8

Tabella 2.3: Coefficienti del Log-Distance Path-Loss Model

Log-Normal Shadowing Model

Il Log-Normal Shadowing Model e un modello di propagazione del segnale radio che

predice l’attenuazione che il segnale incontra all’interno di un edificio, correlata alla

distanza. Esso e descritto in dettaglio in [Rap01]. L’equazione da cui si ricava il path-loss

e la seguente:

L = L0 + 10γlog 10d

d0+Xg,

in cui L e il path-loss totale all’interno dell’edificio [dB], L0 e il path-loss alla distanza

d0 [dB], d e la distanza che separa trasmettitore e ricevitore [m], d0 e la distanza di

riferimento [m], γ e l’esponente di path-loss e Xg e una variabile casuale gaussiana a

media nulla e varianza σ2, relativa ai fenomeni di fading (shadow fading). Anche questi

questi coefficienti sono ricavati empiricamente; alcuni loro valori sono elencati in tabella

2.3.

2.3 Il processo di localizzazione

La localizzazione e un processo mediante il quale i nodi determinano la loro posizione.

In termini semplici, la localizzazione e un meccanismo per scoprire le relazioni spaziali

tra oggetti. I differenti approcci scelti in letteratura differiscono dal punto di vista delle

assunzioni fatte sulle capacita della rete e dei nodi utilizzati. Una lista dettagliata di

assunzioni possibili, seppur non esaustiva, comprende assunzioni sul tipo di hardware

disponibile, modelli di propagazione del segnale, requisiti energetici e di temporizzazione,

tipo di ambiente (indoor o outdoor), densita di nodi beacon, precisione necessaria e

mobilita dei nodi. In particolare, in condizioni di mobilita, possono presentarsi quattro

differenti scenari, in base al fatto che i nodi o i beacon hanno la possibilita di spostarsi.

Nel seguito verranno presentati alcuni tra piu rilevanti approcci al problema della

localizzazione, raggruppandoli in due principali categorie: i metodi di localizzazione

range-based e range-free.


2.4 Metodi di localizzazione range-based

Nei metodi di localizzazione range-based, la posizione di un nodo e calcolata relativa-

mente ai nodi nelle vicinanze5. Essi fanno l’assunzione che la distanza tra il trasmettitore

e il ricevitore puo essere stimata considerando una o piu caratteristiche del segnale. La

precisione di tale stima, comunque, dipende dalle condizioni del canale di trasmissione

e dall’ambiente circostante. Spesso, a causa dei fenomeni fisici visti precedentemente,

essa puo essere inaccurata e necessita di ulteriori elaborazioni.

Le caratteristiche del segnale usate frequentemente in approcci range-based saranno

descritte nei paragrafi seguenti.

2.4.1 Time Of Arrival

Il Time Of Arrival (TOA) e comunemente usato per ottenere informazioni sulla distanza

attraverso il tempo di propagazione del segnale. Mediante la relazione esistente tra la

velocita della luce nel vuoto e la frequenza del segnale e possibile ricavare la distanza

tra trasmettitore e ricevitore. Il sistema piu conosciuto che utilizza il TOA e senz’altro

GPS; esso richiede un hardware dedicato, per mantenere una precisa sincronizzazione

con i clock dei satelliti.

A differenza del TOA, il Time Difference Of Arrival (TDOA), non impiega i tempi

assoluti di invio e ricezione del segnale, ma le differenze temporali relative fra i nodi.

Combinando almeno tre distanze ricavate da tre posizioni di riferimento, e possibile

stimare la posizione del dispositivo effettuando un procedimento di trilaterazione, impo-

stando un sistema di equazioni che permette di trovare l’intersezione tra le circonferenze

centrate sui nodi di riferimento (fig. 2.3). Nel caso di tre nodi di riferimento avremo il

seguente sistema: (x1 − x)2 + (y1 − y)2 = d2

1

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

(x3 − x)2 + (y3 − y)2 = d23

,

dove (xi, yi) sono le coordinate del nodo di riferimento i e di le singole distanze stimate.

Ovviamente all’aumentare dei nodi di riferimento e possibile impostare un problema di

ottimizzazione (ad esempio minimi quadrati) incrementando notevolmente l’accuratezza

della stima (in questo caso si parla di multilaterazione).

2.4.2 Angle Of Arrival

L’Angle Of Arrival (AOA) e definito come l’angolo formato dalla direzione di propa-

gazione dell’onda incidente rispetto ad una direzione di riferimento, che e nota come

orientamento. In particolare viene misurata la direzione del segnale che arriva dal nodo5Sono i nodi presenti nel raggio di copertura del segnale del dispositivo


d1 d 2

d3

(x3,y3)

(x2,y2)(x1,y1)

(x,y)

Figura 2.3: Il procedimento di trilaterazione

mobile ad altri due nodi. Se la posizione dei quest’ultimi e nota, e possibile utilizzare la

triangolazione per determinare la posizione dell’unita mobile. Se sono disponibili piu di

tre misurazioni di angoli, esse non necessariamente sono compatibili a causa di possibili

errori e percio devono essere applicate delle medie complicate per ottenere la posizione

[NN03].

Un approccio comune per misurare l’AOA e utilizzare un array di antenne e cio lo

rende quasi inapplicabile nelle WSN, a causa del suo costo e della sua complessita.

2.4.3 Received Signal Strenght

Una possibilita per acquisire informazioni sulla distanza e correlarla alla potenza del

segnale ricevuto, denominata Received Signal Strenght (RSS). L’idea fondamentale die-

tro questo approccio e che la potenza di trasmissione Ptx influisce direttamente sulla

potenza di ricezione Prx. Secondo l’equazione 2.1, Prx varia in modo quadratico con la

distanza dal trasmettitore r.

Ovviamente questo ragionamento e corretto nelle condizioni ideali di LoS tra tra-

smettitore e ricevitore, nel vuoto e in assenza di fenomeni come rifrazione, diffrazione e

multipath. In scenari reali, e in particolar modo in ambienti indoor, l’andamento rea-

le dell’equazione 2.1 non e applicabile direttamente, in quanto il RSS e influenzato da

molteplici fattori:

Variabilita del trasmettitore Differenti tipi di trasmettitori si comportano differen-

temente, anche se configurati nello stesso modo. In pratica, questo significa che

quando un trasmettitore e configurato per inviare dati ad un livello di potenza di

p dBm, il valore reale non sara esattamente uguale a quanto impostato. Questo

puo alterare il RSS in ricezione e portare pertanto a stime inaccurate.


Variabilita del ricevitore La sensibilita del ricevitore, su diversi circuiti radio e dif-

ferente. In pratica, questo significa che il RSS misurato su piu tipi di ricevitori

puo non coincidere, anche se tutti gli altri parametri che lo influenzano rimangono

costanti.

Orientamento dell’antenna Ogni tipo di antenna ha il proprio pattern di radiazione

e anche se essa idealmente e isotropa, nella realta il suo guadagno non sara uni-

forme. Cio significa che alla medesima distanza, modificando l’orientamento del

dispositivo di trasmissione o ricezione, la misurazione del RSS sara differente.

Multipath fading Come descritto al paragrafo 2.1.6, in ambienti indoor, il segnale tra-

smesso viene riflesso dopo aver colpito muri o altri oggetti. Sia il segnale originale

che quello riflesso raggiungono il ricevitore quasi allo stesso istante, considerata la

velocita di propagazione pari a quella della luce. Come risultato di questo, il RSS

viene calcolato per entrambi i segnali dato che essi non sono distinguibili.

Interferenze La presenza di altri campi elettromagnetici generati da altre fonti puo

ampliare o attenuare il segnale e di conseguenza influire sul RSS.

In molte applicazioni, tali effetti, possono degradare la bonta della misurazione fa-

cendo ottenere un’alta varianza ed una bassa entropia sui dati rilevati. Spesso quindi,

correlare la potenza del segnale ricevuto alla distanza e, successivamente, alla posizione,

richiede la progettazione di sistemi che tengano conto della rumorosita del RSS.

Il fattore positivo negli algoritmi che utilizzano il RSS e il basso costo e complessita;

come vedremo al capitolo 3, nello standard IEEE 802.15.4 sono previste delle primitive

del livello fisico che permettono di estrarre il valore del RSS su ogni pacchetto ricevuto.

In questo modo e possibile implementare algoritmi di localizzazione su qualsiasi tipo di

nodo compliant con lo standard, senza la necessita di hardware costosi.

In letteratura, esistono molti approcci basati sulle considerazioni fatte, tra cui prin-

cipalmente [SHS01, PHP+03, BGGT07, SKOM06].

2.4.3.1 RSS fingerprinting

Alcuni metodi di localizzazione non impiegano il RSS per ricavarne informazioni relative

distanza; l’idea e quella di identificare una locazione sulla base della sua impronta RSS

(RSS fingerprint) rispetto a diversi nodi beacon, sotto l’assunzione che essa e univoca

per tutte le posizioni dell’ambiente in esame. Generalmente, un’impronta I e associata

alle informazioni sulla posizione P , costruendo una tupla < I, P > che viene inserita in

un database durante una prima fase off-line, denominata RSS profiling. La dimensione

delle coordinate reali nella tupla puo variare da 1 a 5, considerando uno spazio tridimen-

sionale e due variabili di orientamento. Ad esempio, le informazioni sulla posizione di


un sistema bidimensionale con orientamento, possono essere rappresentate dalla tripletta

P = {(x, y, o)|x, y ∈ R2, d ∈ {Nord,Est,Sud,Ovest}}.Nonostante il RSS risulti molto piu dipendente dalla posizione, rispetto al SNR, es-

so puo variare nel tempo rispetto al medesimo beacon e deve essere considerato come

una variabile casuale; possono essere utilizzate statistiche descrittive, approssimando

la distribuzione delle misurazioni, oppure mantenendo tutti i dati. Indipendentemente

dall’approccio scelto, l’impronta RSS di una determinata posizione conterra un vettore

I = {RSS1, RSS2, ..., RSSn}, dove n dipende dal numero di beacon considerati. Ovvia-

mente, il numero di campioni raccolti per rappresentare correttamente la locazione deve

essere adeguato all’ambiente, al fine di eliminare eventuali mismatch nell’algoritmo che

effettuera la corrispondenza. In figura 2.4 e possibile osservare un ambiente in cui sono

state effettuate misurazioni di impronte RSS (RADAR [BP00]).

Wireless Access Point

RSS �ngerprint

Figura 2.4: Impronte RSS nel sistema RADAR [BP00]

Dopo la fase di profiling, il problema di localizzazione entra nella fase on-line, in cui

l’impronta RSS del nodo viene campionata a intervalli regolari e se ne cerca l’eventuale

corrispondenza nel database costruito. Esistono vari algoritmi per trovare tali corrispon-

denze, alcuni deterministici basati su reti neurali o classificatori nearest neighbour, altri

probabilistici che impiegano l’inferenza bayesiana. Ad esempio la soluzione descritta

in [BP00] utilizza la metrica definita nearest neighbour in signal space (NNSS) che usa

essenzialmente la distanza euclidea.

Come si puo comprendere, questa classe algoritmi richiede molto tempo per la fase

di profiling e una modifica nella configurazione dei beacon comporta la ripetizione di


tutte le misurazioni. Risultano tuttavia molto robusti rispetto ai fenomeni che di soli-

to influenzano il RSS, soprattutto indoor. Essi sono utilizzati con successo in scenari

abbastanza statici, come la localizzazione in uffici. Un altro sistema basato su quanto

appena descritto e Motetrack [LW04].

2.5 Metodi di localizzazione range-free

L’approccio alla localizzazione range-free non si occupa di calcolare le distanze basandosi

sulla potenza del segnale ricevuto o altre caratteristiche del segnale come tempo, angolo,

ecc. Piuttosto, la posizione dei nodi viene calcolata sfruttando delle proprieta topologiche

della rete, ad esempio tenendo presente il numero di hop tra trasmettitore e ricevitore

oppure considerando informazioni sulla connettivita con i nodi vicini [SRZF07].

Un semplice algoritmo range-free e quello basato sul centroide [BHE00]; il nodo che

vuole conoscere la sua posizione calcola il centroide delle posizioni inviate dai beacon

che lo circondano. Esso genera un errore sulla localizzazione che ovviamente dipende

dalla configurazione dei beacon e dalla posizione del nodo.

Un approccio interessante e APIT (Approximate Point In Triangulation), descritto

in [HHB+03]. Esso richiede che una piccola percentuale di dispositivi conosca la sua

posizione e sia equipaggiato con un trasmettitore ad alta potenza. Ogni nodo stima se

si trova all’interno di una regione triangolare tra i beacon (fig. 2.5(a)); la presenza di un

nodo dentro o fuori queste aree permette di restringere l’area in cui esso potenzialmente

risiede. Utilizzando di volta in volta combinazioni di tre beacon, la precisione sulla

localizzazione aumenta ad ogni iterazione.

(a) APIT [HHB+03] (b) DV-HOP [NN01]

Figura 2.5: Alcuni approcci di localizzazione range-free

Un altro algoritmo di localizzazione range-free e DV-HOP [NN01] che impiega un

numero costante di beacon ed e basato su un’euristica che mette in relazione la distanza

con il numero di hop in reti isotrope 2.5(b). Sostanzialmente ogni nodo calcola il numero


di hop che lo separano dal beacon e lo trasforma in una distanza. L’algoritmo e struttu-

rato in due fasi: nella prima fase, ogni nodo ascolta i messaggi propagati in flooding dai

beacon e registra il minor numero di hop che lo separano da esso. Nella seconda fase,

in base alla stima effettuata, il nodo propaga un fattore di correzione che rappresenta

la distanza reale di un hop da lui percepita. Tale approccio comporta tuttavia un alto

errore di localizzazione in reti anisotrope, dove l’esistenza di un “buco” nella struttura fa

venire meno la proporzionalita fra numero di hop e distanza, causando stime inaccurate.

Data le limitazioni sulla complessita dell’hardware di un dispositivo appartenente a

WSN, le soluzioni range-free risultano una buona alternativa rispetto a quelle range-

based, anche se talvolta hanno dei requisiti abbastanza stringenti sulla topologia di rete

(richiedono ad esempio reti isotrope) e sulla densita di dispositivi che ne fanno parte.

Capitolo 3

Lo standard ZigBee

Ad oggi, la realizzazione di Personal Area Network (PAN) basate su protocolli wireless,

sta riscontrando notevole interesse, sia in ambito accademico che industriale. Nono-

stante vi siano molteplici standard e protocolli gia consolidati ed idonei a questo scopo

come Wi-Fi e Bluetooth, esistono tuttavia alcuni scenari applicativi in cui sono richieste

funzionalita aggiuntive al trasferimento dati. Si pensi ad esempio al monitoraggio di

componenti meccaniche in movimento in un’industria, al fine di misurare alcune gran-

dezze fisiche di interesse, come ad esempio accelerazioni e temperature. Una prima

idea potrebbe essere quella di impiegare dei sensori, integrati in nodi basati su Wi-Fi,

collocati sulle parti da monitorare; sorgono immediatamente alcuni dubbi, sia su come

alimentare i nodi a lungo termine (dato il consumo energetico non indifferente di tali

dispositivi non e praticabile l’impiego di batterie, almeno di ridotte dimensioni), sia in

che modo organizzare la rete dal punto di vista gerarchico, per l’aggregazione dei dati.

Tali problematiche sono tra quelle principali per cui sono state introdotte le Wireless

Sensor Network (WSN) [SACO06] e a cui appunto ZigBee1 appartiene.

In questo capitolo verra illustrata a grandi linee la struttura dello standard, focaliz-

zando l’attenzione sulle funzionalita dello stack che sono risultate di interesse per nella

valutazione e la successiva implementazione delle applicazioni. Tale studio ha permesso

di avere le prime indicazioni da cui partire per risolvere un problema di localizzazione,

ottenute analizzando le informazioni riportate dalle primitive relative alla qualita del se-

gnale (Link Quality Indicator). Sono inoltre riportate le motivazioni che hanno portato

alla selezione di dispositivi ZigBee per la realizzazione di questo lavoro di tesi.1ZigBee e un marchio registrato dalla ZigBee Alliance

42

Capitolo 3. Lo standard ZigBee 43

3.1 Le motivazioni della scelta

L’integrazione di tecnologie per WSN e sistemi di robotica mobile, al fine di realizzare

un’applicazione per la localizzazione, pone dei requisiti abbastanza chiari alla piatta-

forma hardware e software. L’avere a che fare con un sistema che lavora in mobilita,

introduce nuove problematiche, soprattutto per quanto riguarda l’organizzazione e ge-

stione della rete. Inoltre, fattori come basso costo e autonomia in termini energetici,

sono fondamentali al fine di rendere l’applicazione facilmente realizzabile anche nella

pratica. Come ultimo, e non per questo meno importante aspetto, occorre menzionare

le possibilita di miniaturizzazione dei dispositivi, in modo da poterli facilmente installare

su varie tipologie di robot mobili, anche di piccole dimensioni. Per di piu, essi potreb-

bero essere indossati anche da persone o rilasciati dinamicamente nell’ambiente durante

il processo di esplorazione, in modo da garantirne la successiva localizzazione.

Dopo un’attenta analisi, la scelta e stata indirizzata verso lo standard per LR-WPAN

ZigBee, dato che, come vedremo successivamente nel resto del capitolo, presenta molti

dei requisiti descritti in precedenza. La selezione e stata effettuata dopo due settimane di

sperimentazione presso l’RFID-Lab2, un laboratorio che si occupa principalmente di test

e integrazione di tecnologie wireless, in particolare Wi-Fi, Bluetooth, RFID, e appunto

ZigBee. Effettivamente questo periodo e stato di fondamentale importanza anche per

considerare altre alternative (ad esempio TinyOS) e al fine di valutare anche a livello

applicativo la soluzione che si stava scegliendo.

Le piattaforma selezionata dopo questa fase di studio e stata quella prodotta da

Freescale, per la precisione quella basata sul SiP MC13213 e ZigBee compliant rispetto

alla specifica ZigBee 2006. Per ulteriori dettagli sulla piattaforma impiegata si consulti

il paragrafo 4.1 e per le caratteristiche tecniche l’appendice A.

3.2 La nascita dello standard

I primi studi, che hanno portato alla successiva definizione dello standard, risalgono al

1998 ad opera di Motorola, quando alcuni gruppi di ingegneri si resero conto che effetti-

vamente molti nuovi scenari applicativi non potevano essere risolti efficacemente con le

tecnologie wireless esistenti. La versione 1.0 delle specifiche (ZigBee 2004) viene pubbli-

cata nel dicembre 2004, anche a seguito del lavoro svolto da IEEE per creare uno stan-

dard per il livello fisico e di accesso al mezzo (MAC) per le LR-WPAN, ovvero 802.15.4

[IEE06]. Contemporaneamente, nel 2002, nasceva la ZigBee Alliance, un’associazione di

oltre 200 aziende a cui partecipano alcuni dei maggiori produttori di semiconduttori a

livello mondiale, tra cui Freescale, Texas Instruments, Philips, Honeywell e Oki. Essa si2http://w3.uniroma1.it/rfidlab/default.asp

http://w3.uniroma1.it/rfidlab/default.asp


occupa di gestire l’evoluzione dello standard e di garantire l’interoperabilita e conformi-

ta alle specifiche delle applicazioni sviluppate. La versione attualmente in uso e ZigBee

2006 (settembre 2006) [Zig06] e dall’ultimo trimestre del 2007 sta per essere finalizzata

la nuova versione ZigBee Pro, che comprende alcune migliorie per quanto riguarda la

scalabilita e la sicurezza in reti di grande complessita.

3.3 Caratteristiche

Le migliori peculiarita di ZigBee, se vogliamo, sono racchiuse proprio nel suo nome. La

parola ZigBee infatti, deriva dallo zigzagare delle api durante il volo; cio rappresenta

proprio la semplicita con cui e possibile organizzare la struttura della rete e la comuni-

cazione (in particolare l’instradamento), anche in caso di guasti. Quello che aggiunge

altro entusiasmo intorno alla nascita di questo protocollo e inoltre la sua straordinaria

stabilita ed affidabilita, a fronte di consumi energetici irrisori; si pensi che con un’ali-

mentazione di 3 V3, e possibile mantenere operativo un nodo anche per piu di un anno.

Tutte queste caratteristiche portano ZigBee ad essere molto indicato in applicazioni di

controllo e monitoraggio, in cui ad esempio e significativo avere bassa latenza nelle comu-

nicazioni, sia per lo scambio di messaggi che per il collegamento alla rete. Al contrario

esso non e stato progettato per lo scambio dati ad alti data rate; il suo massimo bitrate

ottenibile e di appena 250 Kbps. In figura 3.1 sono stati messi a confronto il bitrate e il

range trasmissivo raggiungibili da ZigBee, rispetto ad altri protocolli wireless.

Considerando che la maggior parte dei dispositivi ZigBee compliant permette il col-

legamento di trasduttori e sensori di varie tipologie, possiamo immaginare dei possibili

scenari in cui ZigBee puo essere impiegato convenientemente:

Home automation Sicurezza, controllo illuminazione, HVAC, controllo accessi.

Controllo industriale Monitoraggio dei processi, gestione energia e risorse.

Agricoltura di precisione Irrigazione controllata, dosaggio fertilizzanti.

Health care Sensori e apparecchiature medicali, controllo pazienti, telemedicina.

Elettronica di consumo Periferiche, controllo a distanza elettrodomestici, giocattoli.

Gli altri punti di forza di questa tecnologia risultano essere la bassa complessita e

di conseguenza il costo di produzione. La dimensione dello stack e molto ridotta (nel-

l’ordine dei 50 KB) rispetto a Bluetooth o Wi-Fi e richiede percio hardware abbastanza

economico; una piattaforma hardware tipica e formata da processore a 16 MHz con 43Tensione corrispondente a due comuni batterie AA.


Text Internet/Audio Compressed Video Digital Video

Bluetooth 2

Bluetooth 1

802.11b

802.11a, g

802.15.3/UWB

100 Kbps 1 Mbps 10 Mbps 100 Mbps50 MbpsData Rate

10 m

100 m 802.15.4/ZigBee

150 m

Rang

e (m

)

Figura 3.1: Bitrate e range trasmissivi di ZigBee rispetto ad altri standard wireless

KB di RAM e 128 KB di memoria flash, modem e porte di I/O. Spesso tali componen-

ti vengono integrati in singoli circuiti, i cosiddetti System-In-Package (SiP), riducendo

anche le dimensioni, oltre al costo e ai consumi energetici.

Molte delle caratteristiche precedentemente descritte risultano di fondamentale im-

portanza nelle WSN, in cui sono richieste le seguenti funzionalita:

• Topologie di rete dinamiche

• Instradamento multi-hop

• Funzionamento con elevato numero di nodi

• Resistenza ai guasti

• Auto-organizzazione e self-healing

• Lunga autonomia energetica

Per quanto riguarda le caratteristiche trasmissive di ZigBee, esso opera nelle frequen-

ze radio assegnate per scopi industriali, scientifici e medici (ISM); 868 MHz in Europa,

915 MHz negli Stati Uniti e 2,4 GHz nella maggior parte dei paesi. Per i dettagli riguardo

il livello fisico consultare il paragrafo 3.4.1.

3.4 Lo stack ZigBee

La specifica ZigBee [Zig06] definisce uno stack protocollare che permette l’interoperabili-

ta di dispositivi wireless a basso costo, a bassi consumi energetici e con data rate limitati.

Esso pone le sue basi, per quanto riguarda il livello fisico (PHY) e il livello di accesso al

mezzo trasmissivo (MAC), sullo standard per le LR-WPAN IEEE 802.15.4 [IEE06]. In

questi primi due strati vengono specificati i parametri fisici di comunicazione e accesso

al canale, le primitive di trasmissione/ricezione, una gestione di base dell’autenticazione

e della sicurezza.


Banda Regione geografica Data rate Canali disponibili868.3 MHz Europa 20 Kbps 0

902-928 MHz Stati Uniti, Australia 40 Kbps 1-102.405-2.480 GHz Tutti i paesi 250 Kbps 11-26

Tabella 3.1: Suddivisione della banda ZigBee

Diversamente, i livelli superiori definiti dalla ZigBee Alliance, prevedono un livello

di rete (NWK), un livello applicazione (APL) e un servizio di sicurezza, detto Security

Service Provider (SSP). Nei prossimi paragrafi affronteremo ciascuno di questi strati

singolarmente; in figura 3.2 e possibile osservare in dettaglio lo stack ZigBee completo.

IEEE 802.15.4defined ZigBee TM Alliancedefined End manufacturerdefined Layer function Layer interface

Physical (PHY) Layer

Medium Access Control (MAC) Layer

Network (NWK) Layer

Application Support Sublayer (APS)APS Message

BrokerASL SecurityManagementAPS SecurityManagement

ReflectorManagement

ApplicationObject 240

ApplicationObject 1…

Application (APL) Layer

ZigBee Device Object (ZDO)

Endpoint 240APSDE-SAP

Endpoint 1APSDE-SAP

Endpoint 0 APSDE-SAP

NLDE-SAP

MLDE-SAP MLME-SAP

PD-SAP PLME-SAP

NWK SecurityManagement

NWK MessageBroker

RoutingManagement

Network Management

2.4 GHz Radio 868/915 MHz

SecurityServiceProvider

ZDO

Public Interfaces

Application Framework

ZDO Management Plane A

PSME-SA

P N

LME-SA

P

(SSP)

Figura 3.2: Lo stack ZigBee completo

3.4.1 Lo strato PHY

Come gia accennato precedentemente, ZigBee opera nella banda di frequenze ISM, che

non necessita di licenza se i dispositivi hanno massima potenza EIRP (potenza equiva-

lente irradiata da antenna isotropica) limitata (nell’ordine di qualche mW) e vengono

utilizzati all’interno di proprieta private; ne consegue ovviamente che in questa banda si

verificano facilmente interferenze generate da altri apparati che operano sulle medesime

frequenze ISM. Per ovviare a tale problema, come vedremo, vengono impiegate tecniche

particolari di modulazione e di accesso al mezzo trasmissivo.


Il gruppo di IEEE 802.15.4 ha previsto due differenti specifiche dello strato PHY,

operative in differenti range di frequenze; una specifica a bassa frequenza, che impiega

la banda a 868 MHz in Europa e a 915 MHz negli Stati Uniti e in Australia. La

seconda specifica ad alta frequenza utilizza invece la banda dei 2.4 GHz, disponibile nella

maggior parte dei paesi nel mondo. In tabella 3.1 e possibile comprendere l’assegnazione

delle frequenze, il numero di canali disponibili e la massime velocita di trasmissione

raggiungibili.

3.4.1.1 Modulazione e spreading

La funzione dello strato PHY e principalmente quella di trasmettere e ricevere dati

binari, provenienti e destinati, agli strati superiori. Per le due differenti specifiche (868-

915 MHz e 2.4 GHz) vengono utilizzate tecniche di modulazione e spreading differenti,

il cui principio di funzionamento e illustrato in figura 3.3.

Encoderdi�erenziale

Convertitoreda bit a chip

ModulazioneBPSK

Convertitore dabit a simbolo

Convertitore dasimbolo a chip

ModulazioneO-QPSK

DATIBINARI

SEGNALEMODULATO

868-915 MHz PHY

2.4 GHz PHY

Figura 3.3: Spreading e modulazione in 802.15.4

DSSS e modulazione O-QPSK (2.4 GHz)

In questo caso lo stream binario viene suddiviso in nibble, che vengono mappati in se-

quenze di 32 bit (dette chip) effettuando uno XOR con sequenze pseudocasuali, anch’esse

di 32 bit. Al termine di questa procedura (che prende il nome DSSS - Direct Sequence

Spread Spectrum) il segnale occupa piu banda del necessario, permettendo di condivi-

dere il singolo canale diversi utenti e di resistere maggiormente a fenomeni di jamming.

Il chip che arriva al modulatore O-QPSK (Offset Quadrature Phase Shift Keying) viene

diviso in due sequenze sfasate di mezzo periodo di chip che vengono modulate separa-

tamente (sequenza in fase [I] e in quadratura [Q]); cio limita le oscillazioni di fase a 90◦

(rispetto ai 180◦ della normale QPSK) fornendo un inviluppo con meno salti in ampiezza

rispetto a QPSK.


DSSS e modulazione BPSK (868-915 MHz)

La sequenza binaria in ingresso all’encoder bit a bit, effettuando uno XOR con il risultato

dell’operazione precedente, secondo la seguente equazione:

En = Rn ⊕ En−1

dove Rn e il bit in ingresso allo stadio di encoder differenziale, En−1 e il risultato dell’o-

perazione precedente ed En e il risultato dell’operazione, riferito all’indice n. Successi-

vamente il singolo bit viene espanso con una procedura di spreading in una sequenza di

15 bit, utilizzando un chip a 15 bit (generato in modo pseudocasuale). La sequenza pro-

dotta viene poi inviata sul canale wireless utilizzando una modulazione BPSK (Binary

Phase Shift Keying) con un impulso a coseno rialzato e fattore di rolloff α = 1.

3.4.1.2 Coesistenza con interferenze

Per un dispositivo wireless, operare nelle bande ISM, puo diventare problematico data

la numerosa presenza di altri apparecchi che utilizzano quelle frequenze. Per ZigBee le

potenziali interferenze si presentano a 2.4 GHz, frequenza a cui lavorano anche 802.11

b/g e Bluetooth. In questo interessante articolo [Cro07] e riportato un esperimento in cui

viene misurato il PER (Packet Error Rate) su una rete ZigBee funzionante in presenza

di una Wi-Fi 802.11b attiva; dai risultati si apprende che ZigBee e abbastanza tollerante

alle interferenze, avendo uno spettro di ampiezza nettamente inferiore a Wi-Fi. Ad

ogni modo, durante le fasi di installazione di diverse tecnologie wireless operanti sulla

medesima banda, e bene scegliere canali che siano ortogonali tra loro, come e possibile

osservare in figura 3.4.

84.214.204.2 2.472.462.452.442.432.42

Figura 3.4: Coesistenza di ZigBee con 802.11


Nel paragrafo 3.4.2 vedremo come viene regolato l’accesso al mezzo da parte dei piu

dispositivi che condividono lo stesso canale trasmissivo.

3.4.1.3 Primitive offerte dallo strato PHY

Lo strato PHY ha la responsabilita di fornire le seguenti funzionalita ai livelli superiori:

- Attivazione e disattivazione del transceiver

- Rilevamento della quantita di energia sul canale in uso (Energy Detection - ED)

- Misurazione della qualita del collegamento per tutti i pacchetti ricevuti (Link

Quality Indicator - LQI)

- Verifica dell’occupazione del canale (Clear channel assessment - CCA) per realizza-

re servizi di CSMA-CA (Carrier Sense Multiple Access with Collision Avoidance)

- Selezione della frequenza di trasmissione

- Invio e ricezione di dati

Come si puo notare in figura 3.2 la comunicazione tra uno strato dello stack e quelli ad

esso adiacenti e garantita mediante dei Service Access Point (SAP). Le primitive che

vengono invocate tramite questi SAP possono essere di quattro tipi:

Request La primitiva di request e inviata dallo user-N al layer-N per richiedere che un

servizio sia invocato.

Indication La primitiva di indication viene passata dal layer-N allo user-N per indicare

un evento interno al layer-N significativo per lo user-N. Questo evento puo essere

logicamente legato a una request remota o ad un evento interno al layer-N.

Response La primitiva di response viene passata dallo user-N al layer-N per completare

una procedura precedentemente invocata da una indication.

Confirm La primitiva di confirm viene passata dal layer-N allo user-N per comunicare

l’esito di una o piu richieste precedenti.

In particolare ogni strato dello stack ZigBee espone un SAP riservato ai dati e uno

alla gestione; ad esempio nel livello PHY troviamo il PD-SAP (PHY Data-SAP) e il

PLME-SAP (PHY Layer Management Entity-SAP) (fig. 3.5(b)). Il PLME ha inoltre la

responsabilita di mantenere un database (PIB - PAN Information Base) con le informa-

zioni relative al livello PHY, come ad esempio il canale e la frequenza di trasmissione.


Service Provider(layer-N)

Service User(user-N)

Service User(user-N)

RequestIndication

Response Con�rm

(a) Invocazione di primitive

PD-SAP PLME-SAP

PHYPIB

RF-SAP

PLMEPHY layer

(b) I SAP dello strato PHY

Figura 3.5: Organizzazione in SAP di ZigBee

3.4.2 Lo strato MAC

Le responsabilita fondamentali dello strato MAC, come in qualunque altro protocollo

wireless, sono quelle di fornire una comunicazione affidabile tra un nodo e i suoi vicini,

cercando di evitare collisioni sul mezzo trasmissivo. Esso ha inoltre la funzione di as-

semblare e decomporre i pacchetti dati, in arrivo e un uscita, e di garantire un primo

livello di indirizzamento al fine di mantenere la PAN operativa.

3.4.2.1 Tipi di dispositivi IEEE 802.15.4

In IEEE 802.15.4 sono state definite tre tipologie di dispositivi:

• Reduced Function Device (RFD)

– Ha funzionalita limitate, per ridurne il costo e la complessita

– Utilizzo tipico agli edge della rete

– Supporta unicamente la topologia a stella

• Full Function Device (FFD)

– Supporta tutte le funzioni specificate da 802.15.4

– Ideale per svolgere il ruolo di router e per interconnettere altre tecnologie

– Supporta qualsiasi topologia di rete

– Puo sostituire il PANC

• PAN Coordinator (PANC)

– Caso particolare di FFD

– Si occupa dello startup della rete e dell’assegnazione degli indirizzi

– Ha conoscenza globale della rete

– Richiede maggiori risorse energetiche e di calcolo


3.4.2.2 Le modalita di accesso al canale

Il canale wireless e condiviso per definizione e per garantirne una corretto utilizzo da par-

te di tutti i dispositivi della rete, devono essere previste particolari politiche di accesso.

Lo strato MAC di IEEE 802.15.4 prevede due modalita: con beacon e senza beacon.

Accesso con beacon

In questa modalita viene utilizzata una struttura a 16 slot denominata superframe, deli-

mitata da beacon che hanno la funzione di identificare la PAN, sincronizzare i dispositivi

ad essa collegati e descrivere la struttura del superframe; tra un beacon e l’altro i nodi

possono entrare in una modalita a basso consumo se non hanno dati da trasmettere.

Durante la fase di contesa (Contention Access Period), basata essenzialmente su

slotted CSMA-CA, i dispositivi si contendono l’accesso al mezzo per la trasmissione.

Per applicazioni in cui e richiesta bassa latenza, il PANC puo riservare dei Guaranteed

Time Slot in cui non e richiesta la fase di contesa del CSMA-CA (fig. 3.6).

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

tempo

CAP CFP

Beacon BeaconG

TS

GTS

CAP - Contention Access PeriodCFP - Contention Free PeriodGTS - Guaranteed Time Slot

GTS

GTS

Figura 3.6: Accesso al mezzo con beacon

Accesso senza beacon

Nelle reti senza beacon, viene impiegato esclusivamente CSMA/CA; un dispositivo che

vuole tentare di inviare dei dati prima si mette in ascolto sul canale (mediante le primitive

di ED definite precedentemente al paragrafo 3.4.1.3) e, se lo trova libero, trasmette. Nel

caso in cui il canale e occupato da un’altra comunicazione, viene attivata una funzione

di backoff che e sostanzialmente un timer per indicare quando ritentare la ritrasmissione

(fig. 3.7). Per una maggiore affidabilita ogni messaggio puo essere confermato dal

relativo ack, inviato senza bisogno della procedura di ED.

Quando la rete e priva di beacon, i dispositivi tengono i loro ricevitori sempre attivi,

provocando un consumo di energia maggiore. Nella pratica alcuni dispositivi sono co-

stantemente pronti a ricevere, mentre altri si limitano a trasmettere in presenza di uno


stimolo esterno. L’esempio tipico di una rete di questo tipo e dato dagli interruttori

wireless: il nodo ZigBee nella lampada puo essere costantemente in ricezione, avendo la

possibilita della connessione diretta alla rete elettrica, mentre l’interruttore (al pari di

un telecomando) alimentato a batteria puo rimanere inattivo fino all’istante in cui vi

e necessita di mandare un segnale. A quel punto si attiva, invia il comando, riceve un

segnale di acknowledge e ritorna inattivo. Tale distinzione si rispecchia perfettamente

nella differenza tra dispositivi RFD e FFD.

Dispositivo A Dispositivo B

Canaleoccupato

Invio dati

Tempo dibacko�

Veri�cacanale

Veri�cacanale

Canalelibero

Figura 3.7: Accesso al mezzo senza beacon

3.4.2.3 Indirizzamento

Il MAC di 802.15.4 possiede due modalita di indirizzamento a 16 e 64 bit. L’indirizzo a 64

bit (extended address) e cablato nel dispositivo e permette di distinguerlo univocamente

da tutti gli altri. La modalita a 16 bit (short addressing) puo essere utilizzata all’interno

della singola PAN e permette di indirizzare fino a 65536 (216) dispositivi; cio consente

di ridurre l’overhead dovuto all’indirizzamento mediante extended address.

3.4.2.4 Primitive offerte dallo strato MAC

Lo strato MAC ha la responsabilita di fornire le seguenti funzionalita ai livelli superiori:

- Generare dei beacon se il dispositivo e un PAN Coordinator

- Supportare la connessione e la disconnessione dalla PAN

- Supportare la sicurezza (controllata comunque dai livelli superiori)

- Utilizzo di CSMA-CA per accedere al canale

- Gestire il meccanismo dei GTS

- Fornire un collegamento affidabile tra due peer livello MAC


Come accadeva nello strato PHY, la comunicazione avviene mediante i SAP riservati

ai dati e al controllo (fig. 3.8, il MCPS-SAP (MAC Common Part Sublayer-SAP) e il

MLME-SAP (MAC Layer Management Entity-SAP) rispettivamente. Anche in questo

caso lo strato conserva un PIB in cui saranno contenuti ad esempio il periodo di beacon,

l’extended address e i parametri della funzione di backoff.

MCPS-SAP MLME-SAP

MACPIB

PD-SAP

MLMEMAC CommonPart Sublayer

PLME-SAP

Figura 3.8: I SAP dello strato MAC

3.4.3 Lo strato NWK

Come accennato precedentemente e come si puo osservare in figura 3.2, le fondamenta

su cui ZigBee fa affidamento sono lo strato PHY e MAC definiti da IEEE 802.15.4. Alle

funzionalita di questi, esso aggiunge la definizione dello strato di rete (NWK) e dello

strato applicazione (APL). In particolare il primo dei due, del quale ci occuperemo in

questo paragrafo, permette di creare delle topologie di rete complesse che vanno oltre

quelle disponibili fino allo strato MAC4. Tale strato si occupa principalmente di: gestire

la connessione alla rete di nuovi dispositivi, instradare pacchetti verso destinazioni non

direttamente raggiungibili, identificare le route verso nuove destinazioni, assegnare di

indirizzi (short address e PAN address) coerenti e infine applicare la sicurezza sui nodi

che ne fanno richiesta.

3.4.3.1 Tipi di dispositivi ZigBee

Nelle reti ZigBee, i dispositivi ricalcano fedelmente quelli precedentemente descritti nella

sezione 3.4.2.1. Anche in questo caso essi si distinguono dalle funzionalita offerte e, di

conseguenza, dalla complessita. I possibili dispositivi ZigBee rientrano in una delle

seguenti categorie, con le responsabilita e funzionalita elencate:

• ZigBee Coordinator (ZC)

– Startup della rete e decisione del relativo PAN-ID4Anche se non specificato esplicitamente, al livello MAC sono disponibili solo due topologie di rete:

quella a stella e quella peer-to-peer [IEE06]


– Permettere ai dispositivi l’entrata e l’uscita (join/leave) dalla rete

– Svolgere tutte le funzionalita di uno ZR

– Ruolo di trust center in una rete con supporto della sicurezza

• ZigBee Router (ZR)

– Instradare dati per altri dispositivi

– Permettere ai dispositivi l’entrata e l’uscita (join/leave) dalla rete

– Conservare i messaggi destinati ai suoi ZED

– Svolgere opzionalmente tutte le funzioni di uno ZED

• ZigBee End Device (ZED)

– Possibilita di funzionare in modalita risparmio energetico effettuando polling

– Costo e complessita limitati, dato che non supporta operazioni relative alla

rete (ad esempio instradamento o join/leave di altri dispositivi)

3.4.3.2 Topologie di rete

Per quanto riguarda le topologie di rete, ZigBee permette di definire configurazioni a

stella, a cluster-tree e mesh. In ognuna di esse deve essere presente esattamente uno ZC e

un qualsiasi numero di ZR e ZED. Tutte le strutture di rete sono basate su una gerarchia

genitore-figlio; quando lo ZC effettua lo startup della rete (decidendo il PAN-ID) gli altri

dispositivi che effettuano successivamente il join diventano suoi figli, impostando lo ZC

come genitore. Cio ovviamente vale anche per i ZR, che possono essere genitori di ZED

o di altri ZR.

Nella gestione delle funzionalita di rete, i nodi genitori hanno delle specifiche respon-

sabilita. In alcune configurazioni di rete infatti, gli ZED comunicano solo periodicamente

con essi, per inviare messaggi e verificarne la presenza, dopodiche possono entrare in mo-

dalita sleep per il risparmio energetico. Per questo motivo la complessita di uno ZC o di

uno ZR, in termini di risorse hardware e software, sara sicuramente superiore a quella

di uno ZED.

Vediamo ora in dettaglio le topologie di rete che Zigbee permette di formare:

Stella E composta da uno ZC e diversi ZED disposti come in figura 3.9(a). Tutti i

messaggi transitano attraverso lo ZC.

Cluster-tree La topologia cluster-tree e formata da uno ZC, uno o piu ZR e, opzio-

nalmente, da ZED. Essa estende la struttura a stella, aggiungendo le funzionalita

dei ZR. Tutti gli scambi dati seguono la gerarchia genitore-figlio; alla ricezione di

un messaggio lo ZR verifica se l’indirizzo della sorgente e un dispositivo ad esso

associato, in caso contrario lo inoltra al suo nodo genitore (fig. 3.9(b)).


Mesh Questa interessante topologia consente a dispositivi che si trovano nel medesimo

range di trasmissivo di comunicare direttamente, a differenza di quello che accade

nelle reti cluster-tree. In questo modo se il destinatario e direttamente connesso, il

messaggio impieghera un hop, altrimenti esso verra instradato seguendo il percorso

deciso dall’algoritmo di routing (fig. 3.9(c)).

Occorre specificare che, sebbene lo ZC sia richiesto per avviare la rete, esso non

e necessario per il suo successivo funzionamento (tranne che per la topologia a stella

ovviamente). Questa e una caratteristica che ritroviamo anche nei ZR e che rappresenta

una delle peculiarita di ZigBee, ovvero la capacita di resistere ai guasti organizzandosi

autonomamente.

(a) Topologia a stella (b) Topologia cluster-tree

ZigBee Coordinator(802.15.4 PAN Coordinator)

ZigBee Router(802.15.4 FFD)

ZigBee End Device(802.15.4 RFD o FFD)

(c) Topologia mesh

Figura 3.9: Topologie di rete ZigBee

3.4.3.3 Algoritmi di routing

ZigBee essendo un protocollo per WSN, richiede algoritmi di routing che non generino

traffico eccessivo per aggiornare le strutture dati dello strato di rete, come puo accadere

ad esempio in soluzioni basate su Distance Vector e Link State [PD03]. Risulta necessario

pertanto riferirsi a classi di algoritmi di routing dedicati alle MANet (Mobile Ad Hoc

Network).

Nello strato NWK ZigBee vengono impiegati sostanzialmente algoritmi gerarchici con

qualche ottimizzazione sulle tabelle di instradamento quando possibile. In particolare

vengono utilizzati:


1. Ad Hoc On Demand Distance Vector (AODV)

2. Motorola Cluster-Tree algorithm

descritti ampiamente in [Lan03, Per03, Erg04].

3.4.3.4 Sicurezza

Come e possibile osservare in figura 3.2, ZigBee offre anche meccanismi di sicurezza,

gestiti dal livello SSP. Tali meccanismi sono basati su un algoritmo AES a 128 bit,

aggiungendo alle funzionalita di base offerte dal MAC, servizi per la scelta delle chiavi

e il loro trasporto, la gestione dei dispositivi e la protezione dei frame. La gestione e

affidata ad un trust center che si occupa principalmente di:

• Autenticare i dispositivi possono accedere alla rete

• Aggiornare periodicamente le chiavi di rete

• Abilitare la sicurezza end-to-end tra dispositivi

Di solito queste responsabilita sono affidate al coordinatore o comunque ad un dispo-

sitivo con maggiori risorse di calcolo. Ovviamente, in ambienti in cui la sicurezza non

e fondamentale (come ad esempio nel monitoraggio nell’agricoltura di precisione), tali

servizi vengono disattivati per aumentare l’autonomia energetica e le prestazioni della

rete. Per maggiori dettagli sui meccanismi di sicurezza si consulti [Zig06].

3.4.3.5 Primitive offerte dallo strato NWK

Lo strato NWK ha la responsabilita di fornire le seguenti funzionalita ai livelli superiori:

- Applicare gli algoritmi di routing idonei alla topologia di rete utilizzata

- Capacita di garantire l’autenticita e la confidenzialita delle trasmissioni

- Creazione di una nuova rete (ZC)

- Gestire la connessione e disconnessione (join/leave) a reti esistenti (ZR,ZED)

- Assegnazione di indirizzi ai nuovi dispositivi

- Conoscenza dei dispositivi nel proprio raggio trasmissivo (neighborhood)

- Possibilita di scoprire nuove route (route discovery)

La comunicazione del NWK con gli strati superiori avviene mediante due SAP, il NLME-

SAP (Network Layer Management Entity-SAP) e il NLDE-SAP (Network Layer Data

Entity-SAP) (fig. 3.10). Mediante il primo vengono gestite tutte le primitive di ricerca


di reti, join/leave e route discovery. Il NLDE-SAP invece permette l’invio e la ricezione

di dati in tutte i nodi della rete, sfruttando gli algoritmi di instradamento. Anche in

questo caso lo strato conserva un IB in cui saranno contenuti ad esempio l’indirizzo di

rete(short address), le tabelle di instradamento, le tabelle dei vicini e i parametri relativi

alla sicurezza.

NLDE-SAP NLME-SAP

NWKIB

MCPS-SAP

NLMENLDE

MLME-SAP

Figura 3.10: I SAP dello strato NWK

3.4.4 Lo strato applicazione

Lo strato di applicazione (APL) di ZigBee e formato dai sottostrati APS (Application

support Sublayer) e ZDO (ZigBee Device Object) e dalle applicazioni vere e proprie

(Application Object - AO), definite dagli utenti finali. Le responsabilita di APS inclu-

dono il mantenimento delle tabelle di binding (che permette di far corrispondere due

dispositivi in base ai servizi offerti e richiesti) e lo scambio di messaggi tra due disposi-

tivi con binding. In figura 3.11 e possibile comprendere meglio tale concetto: in questo

caso l’interruttore 1 e in binding con le lampade (1,2,3), mentre l’interruttore 2 solo con

la lampada 4. Tale funzionalita e di ausilio anche nell’indirizzamento, in quanto con

una singola operazione e possibile inviare messaggi a categorie di dispositivi specifici

(ad esempio l’invio del comando di accensione a tutte le lampade in binding con uno

specifico interruttore).

RadioSwitch 1 Switch 2

RadioLamp 1 Lamp 2 Lamp 3 Lamp 4

Figura 3.11: Concetto di binding


Lo ZDO si occupa invece di definire i ruoli dei dispositivi all’interno della rete (ZC,ZR

o ZED), eseguire discovery dei nodi, ottenendo informazioni sui servizi applicativi offerti

e gestire le richieste di binding. Da un punto di vista applicativo, lo ZDO e l’interfaccia

che hanno gli AO verso lo stack ZigBee.

Su un dispositivo ZigBee possono essere caricate fino a 240 applicazioni (AO) dif-

ferenti, ognuna in esecuzione su un endpoint differente. Gli endpoint possono essere

paragonati al concetto di porta TCP e permettono ad altri dispositivi di comunicare

con le singole applicazioni. Per esempio, un controllo a distanza potrebbe impiegare

l’endpoint 1 per controllare le luci in cucina, l’endpoint 2 per gestire l’impianto di con-

dizionamento in camera da letto e l’endpoint 3 per controllare il sistema di sicurezza

dell’abitazione. Come e possibile osservare in figura 3.2, lo ZDO stesso e considerato un

AO, in esecuzione sull’endpoint 0.

Application Profile

Concludiamo questa panoramica sullo stack ZigBee parlando degli Application Profile,

un insieme di specifiche che descrive il comportamento di una particolare applicazione

distribuita. Esso definisce l’insieme dei dispositivi impiegati e il formato dei messaggi

(cluster) scambiati tra di essi. Ad esempio, esistono dei profili standard per l’Home

Automation e il controllo industriale, definiti ed approvati dalla ZigBee Alliance.

Esistono due tipi di application profile:

• Application profile pubblici: applicazioni interoperabili approvate dalla ZigBee

Alliance mirate a risolvere uno specifico problema.

• Application profile privati: definiti dai singoli produttori per interagire con i

loro dispositivi ZigBee.

I dispositivi nell’ambito del medesimo profilo possono comunicare tra loro per mezzo di

cluster, che rappresentano il formato dei possibili messaggi di input o di output. Per

esempio nel profilo dell’Home Automation esiste un cluster dedicato all’impostazione

delle temperature di soglia di un termostato.

Parte II

Sperimentazione, progettazione e

implementazione

59

Capitolo 4

Analisi della qualita del segnale in

ambienti indoor/outdoor

Come abbiamo visto al Capitolo 3, a seguito di un periodo di studio delle varie soluzioni

orientate alle WSN, la scelta e stata indirizzata verso lo standard ZigBee e la piattaforma

proposta da Freescale, per la cui descrizione approfondita si rimanda al paragrafo 4.1.

La prima esigenza dopo aver selezionato la piattaforma hardware, e stata senz’altro

quella di analizzarne il suo comportamento durante le trasmissioni, al fine di determi-

narne l’idoneita alla realizzazione di un sistema di localizzazione. La grande quantita di

dati raccolti ci ha permesso, non solo di verificare in parte alcuni concetti teorici sulle

trasmissioni wireless, ma anche di definire gradualmente il problema reale che volevamo

risolvere.

Come vedremo nelle sezioni 4.2 e 4.3, i test effettuati ricalcano abbastanza fedelmente

quanto affermato al Capitolo 2 sulla propagazione delle onde radio in ambienti outdoor

e indoor; nella prima condizione possiamo stimare la perdita di potenza da parte del

segnale trasmesso utilizzando l’equazione di Friis (eq. 2.2), mentre nella seconda condi-

zione, anche utilizzando i modelli di attenuazione indoor (par. 2.2), non e semplice far

risultare tali approssimazioni, a meno di tuning onerosi in termini di tempo sui parame-

tri e comunque limitandone la correttezza ad un particolare tipo di ambiente. Nel resto

del capitolo verranno affrontate anche analisi relative alle prestazioni delle antenne e al

comportamento dei dispositivi in movimento, trasportati ad esempio da robot mobili.

Tutte le misurazioni effettuate per la potenza del segnale ricevuto verranno espresse

in unita LQI (Link Quality Indicator) e a volte ci si riferira indifferentemente alla qua-

lita o alla potenza del segnale ricevuto; per una spiegazione dettagliata al riguardo, si

rimanda al paragrafo 4.1.4.

60

Capitolo 4. Analisi della qualita del segnale in ambienti indoor/outdoor 61

4.1 La piattaforma hardware/software di riferimento

4.1.1 Hardware

La piattaforma utilizzata durante tutto il periodo di tesi e quella di Freescale, uno dei

maggiori produttori di semiconduttori a livello mondiale e membro di ZigBee Alliance.

E stato possibile acquistare dei kit di valutazione, avendo a disposizione un buon numero

di nodi e tutto l’occorrente per effettuare i test necessari.

Ogni nodo contiene un transceiver basato sul SiP MC13213 [Sem07b, Sem07a], com-

pliant con lo standard IEEE 802.15.4 e con la specifica ZigBee 2006, funzionante alle

frequenze ISM a 2.4 GHz, con un potenza di trasmissione regolabile tra 3 dBm e -15

dBm e una sensibilita in ricezione di -95 dBm. All’interno dell’MC13213 e presente un

microcontrollore (Microcontroller Unit - MCU) della famiglia HCS08 a 40 MHz, con 60

KB di memoria flash e 4 KB di memoria RAM, che permette di avere contemporanea-

mente sullo stesso SiP sia lo stack per le comunicazioni che quello per le applicazioni.

In figura 4.1 e possibile osservare un dettaglio della Sensor Reference Board (SRB), la

scheda su cui sono installati il SiP MC13123, la memoria flash, il circuito di ricezione,

le interfacce I/O e i sensori. Questa scheda, insieme alla NCB (Network Coordinator

Board)1, viene fornita nei kit di valutazione e permette di testare in modo immediato le

potenzialita di ZigBee. Spesso l’utente finale puo essere interessato solo alle funzionalita

di comunicazione di queste schede e puo decidere, in base alle proprie esigenze2, come

progettare un nuovo tipo di scheda basata sul chip MC13213. A livello di interfacce

General purpose I/O

Interfaccia USB

Alimentazioneesterna

InterruttoreON/OFF

Interfaccia BDM

Sensore temperaturaAccelerometro XYZ

BuzzerMC13213 Transceiver

Memoria �ashLED

Tasti funzione

Figura 4.1: La Sensor Reference Board (SRB) basata sul SiP MC13213 di Freescale

1E una scheda con le stesse funzionalita della SRB, ma fornisce in aggiunta un display LCD a duelinee e l’interfaccia RS232

2Ad esempio necessita di un diverso circuito di ricezione per aumentare la portata trasmissiva e nonha bisogno dei sensori, per ridurre consumi e dimensioni


di comunicazione, esso supporta due porte seriali (Serial Communications Interface -

SCI), sia RS232 (presente solo sulla NCB) che USB, per il collegamento ad unita di

elaborazione mediante UART. E possibile inoltre far comunicare il nodo con dispositivi

esterni (ad esempio particolari sensori) mediante le porte GPIO (General Purpose I/O),

costruendo appositi circuiti di interfaccia.

Sulla SRB sono presenti inoltre un sensore di temperatura (LM61B della National

Semiconductors), un accelerometro a tre assi (MMA7260Q di Freescale) e un buzzer

audio. Essa richiede una tensione di alimentazione di 3.3 V, che puo essere fornita me-

diante due batterie AA, l’interfaccia USB o l’alimentatore esterno. Per quanto riguarda i

consumi, la MCU ha delle modalita di power-saving, anche se essi dipendono fortemente

dal numero di sensori utilizzati e soprattutto dalla frequenza delle trasmissioni dati; con

le sole batterie comunque, il dispositivo puo avere un’autonomia di oltre un anno.

4.1.1.1 Antenna

La progettazione di una antenna e un fattore critico per ottenere un buon range trasmis-

sivo e un throughput stabile in una applicazione wireless. Questo e vero specialmente

in dispositivi a bassa potenza e di dimensioni ridotte come quelli considerati, dove lo

spazio riservato all’antenna e inferiore a quello ideale.

La struttura dell’antenna dovrebbe avere dimensioni ragionevoli rispetto alla lunghez-

za d’onda del campo elettromagnetico. Una dimensione naturale e ad esempio meta della

lunghezza d’onda; a 2.4 GHz equivale a circa 6 cm e permette di lavorare alla frequenza

di risonanza. Scendere sotto questa frequenza puo causare una bassa efficienza.

Nel nostro caso, lo spazio sulla scheda permette di avere una antenna di un quarto

della lunghezza d’onda con struttura a monopolo, in cui una meta e formata dal filo

vero e proprio e l’altra dal piano di massa3. In particolare, sia la SRB che la NCB,

montano una F-Antenna [Sem06] che e possibile osservare in figura 4.2. Questo tipo

di antenna e utilizzata ampiamente, data la sua compattezza, un pattern di radiazione

quasi omnidirezionale e una buona efficienza. Ovviamente le sue ridotte dimensioni

portano a performance minori (in termini di guadagno e range trasmissivi) e non sempre

questo e accettabile; tuttavia, nei test affrontati, le prestazioni sono risultate adeguate.

In particolare, nei primi esperimenti di trasmissione, abbiamo rilevato un range tra-

smissivo massimo di circa 100 m, in condizioni di LOS e con potenza in trasmissione di 0

dBm, ottenendo un Packet Error Rate (PER) del 5% su 1000 pacchetti da 20 byte invia-

ti. Per quanto riguarda il pattern di radiazione, esso appare abbastanza uniforme come

e mostrato in figura 4.2(c); come vedremo cio risultera efficace in situazioni di mobilita

dei dispositivi. Al paragrafo 4.1.2 sono riportati alcuni test riguardo l’orientamento delle

antenne.3Costituito ad esempio da rimanenze tra i collegamenti sul circuito stampato, come collegamenti di

massa e alimentazione.


Piano di massa

Conduttore

Circuito stampato

(a) Struttura di una F-Antenna (b) Particolare dell’F-Antenna montata sullaSRB

-30-25-20-15-10

-505

Polarizzazione verticale (dBi)Polarizzazione orizzontale (dBi)

(c) Diagramma di radiazione [Sem06]

Figura 4.2: Struttura ad F-Antenna

4.1.2 Test di orientamento dell’antenna

Per verificare empiricamente il pattern di radiazione dell’antenna, trasmettitore e ri-

cevitore sono stati posti alla distanza di due metri, ad un’altezza di 50 cm dal suolo e

variando l’orientamento del ricevitore ad ogni ripetizione, come e possibile osservare nella

figura 4.3. I valori riportati sono ottenuti mediando il valore del Link Quality Indicator

(par. 4.1.4) su 100 pacchetti ricevuti. Dai risultati ottenuti, le antenne dei dispositi-

vi sembrano avere un pattern abbastanza uniforme in tutte le direzioni, soprattutto se

mantenuti in posizione orizzontale.

4.1.3 Software

Il kit di sviluppo impiegato include tre tipi di stack protocollari, con cui e possibile

sviluppare applicazioni a differente livello di complessita:

Simple MAC (SMAC) E uno stack proprietario di Freescale e puo essere utilizzato

per implementare semplici reti di tipo punto-punto e a stella. Data la sua sem-

plicita e stato impiegato nelle fasi preliminari, per testare alcune caratteristiche

trasmissive dei dispositivi.


Figura 4.3: Test di orientamento dell’antenna

IEEE 802.15.4 E lo stack che segue lo standard per le LR-WPAN IEEE 802.15.4 e

permette realizzare applicazioni su reti a stella e mesh (con tutti i dispositivi nello

stesso raggio trasmissivo).

ZigBee 2006 Include tutte le caratteristiche descritte al capitolo 3 per quanto riguarda

routing, sicurezza e livello applicazione.

La programmazione dei dispositivi e in linguaggio C, mediante l’IDE Codewarrior per

la MCU HCS08; una volta generato l’eseguibile esso viene caricato sulla flash mediante

un apposito programmatore collegato all’interfaccia BDM (Background Debug Module)

(fig. 4.1), che permette anche di eseguire il debug direttamente sul dispositivo. In ausilio

al progettista, e presente inoltre un software (BeeKit) che consente principalmente di

creare applicazioni da template, impostare i numerosi parametri presenti negli stack

protocollari e successivamente esportare il progetto sotto forma di file XML, per le fasi

di programmazione, compilazione e debugging in Codewarrior.

4.1.4 Link Quality Indicator (LQI)

Come indicato nello standard IEEE 802.15.4, la misura del LQI e una caratterizzazione

della potenza e/o della qualita del segnale, durante la ricezione di un pacchetto. Questa

funzionalita viene offerta dallo strato PHY (par. 3.4.1.3) e puo essere implementata

impiegando le primitive di ED, una stima del rapporto segnale-rumore (SNR) o una

combinazione dei due. Tale misurazione viene effettuata su ogni pacchetto ricevuto,


inserita nelle strutture dati di livello MAC ed espressa come un intero compreso tra

0x00 (0) e 0xFF (255). Il valore minimo e massimo di LQI (0x00 e 0xFF) sono associati

con la minima e la massima qualita del segnale avvertibile dal ricevitore e tutti i valori

compresi sono uniformemente compresi fra questi due limiti.

Nel caso dei dispositivi utilizzati, il LQI e direttamente correlato alla potenza del

segnale ricevuto (RSS), tramite la seguente funzione di conversione:

LQI =13 · (190 + 2 · RSS)

8, (4.1)

in cui RSS e espresso in dBm. Come e facile verificare con facili calcoli, dato che il RSS

oscilla tra -18 dBm e -95 dBm (massima sensibilita in ricezione), otterremo 0 e 255 come

valori minimo e massimo per il LQI.

4.2 Rilevazioni outdoor

La prima fase di esperimenti di trasmissione ha avuto lo scopo di verificare il compor-

tamento dei dispositivi, al variare della distanza tra trasmettitore e ricevitore, in primo

luogo per trovare una qualche relazione matematica fra potenza del segnale in ricezione

e distanza.

Per la parte outdoor il setup e quello riportato in figura 4.4; i nodi trasmettitore e

ricevitore sono in condizioni di LOS, posizionati staticamente a 50 cm dal suolo e con

le antenne orientate nel verso di trasmissione. Le misurazioni della potenza del segnale

ricevuto sono state effettuate inviando ciclicamente un pacchetto ogni 300 ms per un

totale di 100 pacchetti ogni posizione, campionando una distanza di 20 m a step di 2

m. Tali test sono stati successivamente ripetuti per 20 volte, in luoghi, giorni e orari

differenti. In tutti i casi, la potenza di trasmissione, e stata lasciata al valore di default

(0 dBm). Dopo la fase di rilevazione dei dati (consultabili integralmente al paragrafo

Figura 4.4: Setup per i test outdoor


4.2.1) e stato utile utilizzare degli strumenti statistici, per rappresentare sinteticamente

i risultati ottenuti. In figura 4.5 e possibile osservare media e varianza delle differenti

osservazioni, per ogni distanza tra 1 e 20 metri. Per quanto riguarda l’andamento della

media, come ci si puo aspettare, essa decresce all’aumentare della distanza, sebbene

intorno ai 4 m e abbastanza evidente uno strano picco, dovuto forse a una non linearita

nelle funzioni di ED o nel circuito di ricezione (vedere appendice A al riguardo). Dal

grafico della varianza si comprende invece quanto sia minore la dispersione per distanze

inferiori ai 10 m (escludendo la distanza di 4 m), a causa dell’azione piu intensa dei

fenomeni fisici come multipath e scattering (par. 2.1).

0 2 4 6 8 10 12 14 16 18 2060

80

100

120

140

160

180

Distance (m)

LQI

Distance vs. LQI (20 observations)

Average LQI

1 2 4 6 8 10 12 14 16 18 200

50

100

150

200

250Distance vs. LQI variance

Distance (m)

Var

ianc

e

Figura 4.5: Andamento del LQI con la distanza (media e varianza)

Nonostante questa irregolarita nei valori, un risultato interessante e stato quello di

poter effettivamente verificare l’equazione 2.3 per il path-loss; impostando un sistema

sovradimensionato sui dati a disposizione e risolvendo ai minimi quadrati (con d0 = 1 m

e P0 = −42.11 dBm) si ottiene la soluzione np = 1.7018, ovvero np ≈ 2 come nelle

condizioni di spazio libero. Questo era abbastanza prevedibile, considerate le condizioni

di LoS in cui i test sono stati realizzati. In figura 4.6 inoltre, e facile notare come

l’andamento del LQI sulla singola distanza sia quasi gaussiano, a dimostrazione di una

discreta regolarita nei valori riportati.


0 50 100 150 200 2500

0.5

1Distance: 1 m - Mean: 171.875 - Var: 29.5321

LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

0 50 100 150 200 2500

0.5


LQI interval

Pr(

LQI i

nter

val)

Figura 4.6: Distribuzione dei valori del LQI per ogni intervallo

4.2.1 Dati numerici rilevati

I seguenti dati sono stati rilevati utilizzando la configurazione descritta al paragrafo

4.2, configurando due nodi ZigBee, uno come trasmettitore e uno come ricevitore. Il

LQI medio e calcolato mediando su 100 pacchetti ricevuti. Nel caso in cui il luogo

Data LuogoLQI medio rilevato alla distanza (m)

1 2 4 6 8 10 12 14 16 18 20

07/12/07 15.00 Campagna 164.16 147.06 141.42 131.02 124.54 110.86 106.08 96.5 99.44 84.2 75.9407/12/07 15:30 Campagna 159.64 151.9 119.64 122.28 120.76 95.74 105.58 91.4 76.28 69.54 85.5210/12/07 14:30 Viale 172.83 160.18 126.55 139.22 125.73 114.3 101.85 102.96 96.1 96.57 65.7910/12/07 15:00 Viale 168.77 170.06 116.1 138.71 125.89 113.85 110.85 105.48 81.36 68.53 87.310/12/07 15:30 Viale* 162.42 158.14 116.93 127.95 121.55 86.44 84.34 96.85 106.91 94.1 81.9111/12/07 15:00 Urbano 173.65 147.57 102.61 132.6 133 120.42 112.34 100.48 94.71 94.89 84.1611/12/07 15:15 Urbano 178.51 149.69 120.69 146.59 124.42 126.02 122.22 114.1 112.6 92.2 100.211/12/07 15:30 Urbano 178.77 157.12 110 145.26 137.75 125.51 126.87 112.36 104.14 109.95 110.2811/12/07 15:45 Urbano 174.83 149.81 105.44 133.85 133.97 125.42 117.24 102.59 100.34 90.51 73.3611/12/07 16:00 Urbano* 175.04 143.02 112.1 135.22 129.46 112.42 114.26 105.38 95.04 96.61 99.5119/12/07 16:00 Viale 175.12 162.02 142.79 149.89 126.2 121.54 125.12 119.35 100.89 80.7 88.2719/12/07 16:15 Viale* 164.66 166.45 151.39 145.58 133.1 124.39 124.72 113.87 103.95 88 96.0619/12/07 16:30 Campagna 171.02 165.79 136.95 140.16 135.95 127.64 121.31 114.66 111.75 104.43 98.1431/03/08 16:30 Viale 175.96 166.25 132.62 135.82 141.67 126.01 107.63 78.15 99.25 103.88 101.5831/03/08 16:45 Viale* 175.72 165.94 124.01 124.25 143.07 128.37 120.7 119.78 114.72 100.17 10831/03/08 17:00 Viale 171.16 164.93 128.5 143.79 136.15 129.1 118.85 118.3 100.22 105.23 94.0831/03/08 17:15 Viale* 175.25 173.59 149 147 133.9 132.88 126 115.6 100.44 103.34 98.7631/03/08 17:45 Campagna 172.83 148.81 101.44 130.85 138.97 123.42 119.24 105.59 102.34 93.51 78.3631/03/08 18:00 Campagna* 170.04 141.02 116.1 133.22 128.46 111.42 118.26 103.38 98.04 94.61 93.5131/03/08 18:15 Campagna 177.12 164.02 141.79 147.89 122.2 124.54 127.12 116.35 105.89 86.7 84.27

Tabella 4.1: Misurazioni LQI in ambienti outdoor

della misurazione e contrassegnato da un asterisco, la misurazione e stata effettuata in

maniera simmetrica, invertendo la posizione di trasmettitore e ricevitore.


4.3 Rilevazioni indoor

Nella seconda parte di test, realizzati in ambienti indoor, l’interesse e stato rivolto a

capire come sfruttare le informazioni relative alla qualita del segnale. In questo ca-

so, trasformare la potenza del segnale ricevuto in una distanza, al fine di realizzare

un qualche metodo di localizzazione range-based, e sembrato quasi immediatamente

un procedimento poco realistico e comunque gia affrontato ampiamente in letteratura

[SKOM06, BP00, BGGT07], con risultati poco brillanti.

Anche i modelli di propagazione indoor, descritti al paragrafo 2.2, non risultano

particolarmente utili in quanto troppo dipendenti dallo specifico ambiente in cui, empi-

ricamente, vengono ricavati i diversi parametri, richiedendo una fase di tuning eccessi-

vamente complessa. Inoltre, anche dopo aver prodotto un modello abbastanza preciso,

ogni minima perturbazione nell’ambiente, come passaggio di persone, apertura o chiu-

sura di porte, puo seriamente compromettere le misurazioni della qualita del segnale, e

di conseguenza il processo di localizzazione.

4.3.1 Test statici

In prima istanza, la sperimentazione ha previsto uno scenario statico, in cui un nodo

trasmettitore viene mantenuto fisso e un altro ricevitore viene spostato in posizioni ben

determinate, al fine di stilare una specie di mappa del segnale dell’ambiente. Anche

in questo caso, si trovano alla medesima altezza (50 cm), senza considerare importan-

te l’orientamento delle antenne. Le rilevazioni sono state effettuate principalmente in

una abitazione e al Dipartimento di Informatica e Sistemistica (DIS), ed e possibile

consultare integralmente i dati rilevati al paragrafo 4.3.4. Come esempio di riferimento

consideriamo la figura 4.7, in cui e presente la pianta dell’abitazione, i punti in cui sono

state fatte le rilevazioni, il valore LQI medio in quella posizione e l’icona del dispositivo

rappresenta il trasmettitore. Quello che risulta immediatamente e l’impossibilita di rica-

vare direttamente informazioni sulla distanza, a partire dal LQI: ad esempio la posizione

a e piu vicina a b ma presenta LQI minore. Cio e dovuto ovviamente all’attenuazione

provocata dalla struttura e dagli altri fenomeni fisici della propagazione del segnale.

Sebbene non sia possibile trasformare direttamente il LQI in una distanza, se con-

sideriamo globalmente tutti i valori, essi forniscono una buona indicazione di quanto i

nodi siano vicini: i valori della stanza in cui e presente il trasmettitore sono nettamente

maggiori rispetto ai valori delle altre stanze.

4.3.2 Test dinamici

L’ultima fase di test, rispetto alle altre, ha previsto la sperimentazione di trasmissioni in

condizioni di mobilita. A questo scopo e stato previsto l’utilizzo dei robot mobili su ruote


Figura 4.7: Posizioni e rilevazioni di LQI nell’abitazione

(a) Configurazione per il test

12

4

7 6

8

3

5

CD

H

FE

AB

G

I

(b) Percorsi seguiti dal robot

Figura 4.8: Test dinamici


disponibili nel laboratorio SIED, descritti al paragrafo 1.2.1. La sperimentazione e stata

eseguita mettendo un nodo trasmettitore fisso in un punto del laboratorio e installando il

nodo ricevitore sul robot, telecomandando quest’ultimo in modo da seguire dei path pre-

stabiliti (fig. 4.8(b)), durante il quale venivano scambiati pacchetti per estrarre il LQI.

In questa modalita e stato possibile valutare il comportamento dei dispositivi in movi-

mento, in particolare le variazioni del LQI durante l’avvicinamento o l’allontanamento

del ricevitore. In figura 4.9 sono state rappresentate, per tutti i path seguiti dal robot,

le rispettive misurazioni del LQI (in blu) e le funzioni di fitting polinomiali calcolate su

di esse (in rosso); osservando i dati grezzi del LQI si notano ovviamente degli outlier,

causati da variazioni rapide della potenza del segnale ricevuto e dovuti principalmente

a fenomeni di fast fading. Utilizzando le funzioni di fitting invece, l’andamento appare

piu evidente; ad esempio nel segmento E e chiaro che il ricevitore si sta avvicinando al

trasmettitore, mentre nel segmento A esso si avvicina per poi allontanarsi.

0 50 10050

100

150

200 Segment: A

Packet number

LQI

0 50 10050

100

150

200 Segment: B

Packet number

LQI

0 50 10050

100

150

200 Segment: C

Packet number

LQI

0 50 10050

100

150

200 Segment: D

Packet number

LQI

0 50 10050

100

150

200 Segment: E

Packet number

LQI

0 50 10050

100

150

200 Segment: F

Packet number

LQI

0 50 10050

100

150

200 Segment: G

Packet number

LQI

0 50 10050

100

150

200 Segment: H

Packet number

LQI

0 50 10050

100

150

200 Segment: I

Packet number

LQI

Figura 4.9: Risultati dei test dinamici

4.3.3 Conclusioni

Come nei test precedenti, i risultati ricavati, non hanno una validita generale ma se

combinati opportunamente possono fornire delle indicazioni interessanti sui nodi. Cio


che appare evidente, almeno indoor, e la difficolta di realizzare un sistema di localiz-

zazione range-based che sfrutti esclusivamente le informazioni estratte dalla qualita del

segnale ricevuto. Come abbiamo visto anche al paragrafo 2.4.3, sono molteplici i fatto-

ri che possono influenzare le misurazioni, provocando una stima della posizione molto

imprecisa.

Inoltre, durante la mia permanenza all’RFID-Lab, mi e stato possibile assistere ad

alcune sperimentazioni da loro effettuate sul Location Engine della Texas Instrumen-

ts [Aam06], presente sui dispositivi con SoC (System-on-chip) CC2431: i risultati in-

door, sebbene considerando un alto numero di nodi beacon, non sono stati incoraggianti,

presentando alti errori di localizzazione.

Per questi ed altri motivi, come si vedra al capitolo 5, l’informazione estratta dal LQI

non verra utilizzata per realizzare un vero e proprio sistema di localizzazione, ma sara

sfruttata ampiamente per guidare l’esplorazione da parte di robot mobili in ambienti

semistrutturati.

4.3.4 Dati numerici rilevati

Le rilevazioni indoor sono state effettuate in due ambienti differenti: un’abitazione e il

1◦ piano del Dipartimento di Informatica e Sistemistica. La configurazione dei test e

descritta al paragrafo 4.3.

Abitazione

In figura 4.7 e illustrata la pianta dell’abitazione dove sono state fatte le rilevazioni.

Per interpretare correttamente i dati riportati in tabella 4.2, occorre considerare esclu-

sivamente le lettere, relative alle diverse locazioni dove il ricevitore e stato posizionato,

mentre l’icona del dispositivo rappresenta la posizione del trasmettitore (mantenuto fis-

so). Ogni valore LQI e ottenuto effettuando una media su 100 pacchetti ricevuti nella

singola posizione, mantenendo i due dispositivi ad un’altezza dal suolo di 50 cm.

DataLQI in posizione

a b c d e f g h i l m n o p q r s t u

17/12/07 77.39 66.62 46.62 69.83 115.83 91.8 54.31 65.77 69.94 26.52 83.62 30.83 72.04 77.14 66 82.65 108.44 125.44 107.5920/12/07 69.04 100.16 47.66 59.12 95.39 70.97 92.12 48.41 72.25 40.08 70.62 16.22 68.83 81.93 82.16 51.22 145.27 157.58 156.4122/12/07 63.78 98.75 44.12 65.50 112.98 85.72 88.96 49.66 70.07 33.62 76.79 30.25 69.46 78.19 84.25 69.03 148.93 148.38 155.67

Tabella 4.2: Misurazioni LQI in una abitazione

Dipartimento di Informatica e Sistemistica (1◦ Piano)

Anche in questo caso, le rilevazioni sono state effettuate nella stessa modalita dell’a-

bitazione, ma e stato possibile eseguirle una singola volta. Per semplicita i valori sono

riportati direttamente sulla pianta di figura 4.10, dove l’icona del dispositivo rappresenta


la posizione del trasmettitore (mantenuto fisso) e le lettere la posizione del ricevitore,

spostato ad ogni rilevazione. Ogni valore LQI e ottenuto effettuando una media su 100

pacchetti ricevuti nella singola posizione.

Figura 4.10: Posizioni e valori delle rilevazioni LQI al DIS

Capitolo 5

Esplorazione guidata dalla qualita

del segnale

In questo capitolo viene descritta l’idea predominante di questo lavoro di tesi: le in-

formazioni sulla qualita del segnale provenienti dai nodi ZigBee vengono utilizzate per

aiutare l’esplorazione di ambienti sconosciuti per mezzo di robot mobili. Dopo la fase

di studio dei metodi di localizzazione wireless-based (cap. 2) e l’analisi sulla qualita del

segnale (cap. 4), l’obiettivo del lavoro e evoluto, perdendo le sembianze di un vero e

proprio sistema di localizzazione di supporto per robot.

Dai risultati conseguiti nelle sperimentazioni, si evincono le complessita a cui si va

incontro nel realizzare un sistema di localizzazione basato sulla potenza del segnale

ricevuto1. Le problematiche maggiori si incontrano soprattutto indoor, dato che tale

grandezza fisica non puo essere facilmente relazionata alla distanza e cio ostacola non

poco l’applicazione di metodologie range-based. A dir la verita, sistemi basati sul RSS

fingerprinting come Radar [BP00] o MoteTrack [LW04], hanno dimostrato una discreta

precisione, a discapito di tempi di setup onerosi e dipendenza diretta dall’ambiente

in cui vengono impiegati. Gli approcci range-free appaiono senz’altro validi, ma con

considerevoli limitazioni, dovute soprattutto alle topologie di rete e alla densita di nodi

richieste, non applicabili nei nostri scenari di interesse.

Inizialmente, questo lavoro di tesi, era partito con l’intento di elaborare e sperimen-

tare, un sistema di localizzazione che traesse giovamento dall’impiego di tecnologie per

WSN, risultando di notevole interesse nel campo della robotica mobile, ad esempio per

aiutare nella soluzione di problemi di localizzazione globale o, piu in generale, di SLAM.

A seguito delle sperimentazioni effettuate, l’interesse si e spostato dalla localizzazione del

nodo ZigBee, alle strategie efficaci per raggiungerlo; questo, ovviamente, non perche il

primo problema sia meno interessante, ma perche potremmo considerare il secondo una1Come abbiamo visto al paragrafo 4.1.4, nel caso dei dispositivi impiegati, possiamo parlare

indifferentemente di RSS o LQI, grazie alla relazione 4.1

73

Capitolo 5. Esplorazione guidata dalla qualita del segnale 74

sua versione “rilassata”. Nell’esplorazione di ambienti effettuata da robot mobili, questa

funzionalita potrebbe essere pensata come un sensore aggiunto, che riesce ad indicare la

vicinanza di un punto sulla mappa, sia esso stabilito volontariamente o meno.

Quello a cui siamo davanti puo essere pensato come un nuovo approccio all’esplora-

zione, che rispetto ad altri [SB03, BMF+00, MLLH06, TK03], prende le sue decisioni in

base alla qualita del segnale ricevuto dal dispositivo ZigBee installato sul robot mobile;

in questo caso, il problema della ricerca di un punto nell’ambiente, viene risolto mediante

un’esplorazione guidata e la scelta delle frontiere avviene con un contributo informati-

vo piu rilevante rispetto ai casi in cui tali scelte vengono effettuate con una strategia

greedy (ad esempio, considerando la frontiera piu vicina [Yam98]). Con tali considera-

zioni, la ricerca cieca, risolta mediante esplorazione, diviene quindi ricerca informata e

consente di ridurre notevolmente i tempi per il raggiungimento dell’obiettivo della mis-

sione. L’idea e quella di riprodurre la situazione vista al paragrafo 4.3, mantenendo un

nodo fisso che rappresenta l’obiettivo, in grado di trasmettere un pacchetto beacon, e

piu nodi installati altrettanti su robot mobili, in grado di ricevere questi avvisi e sce-

gliere deterministicamente, basandosi sul LQI ricevuto, quale nuova zona dell’ambiente

esplorare.

Come vedremo successivamente, l’esplorazione e basata anche in questo caso sul

concetto di frontiere [Yam97], la cui selezione ad ogni step e affidata ad un algoritmo

euristico. Ovviamente, considerando che le scelte piu rilevanti fatte dall’algoritmo ven-

gono effettuate elaborando un dato poco stabile e rumoroso come il LQI, esso non sara

infallibile in ogni condizione e necessitera di strumenti di filtraggio adeguati per ridurre

le incertezze sulle misurazioni.

Questo tipo di metodologia di esplorazione, si presta abbastanza bene ad ambienti

indoor strutturati e semistrutturati, con possibili scenari di applicazione sono che de-

scritti nel seguito. L’algoritmo implementato e stato sperimentato prima in un ambiente

di simulazione e, successivamente, su un robot mobile reale. I risultati conseguiti sono

descritti al capitolo 7.

In questo capitolo verra illustrato in dettaglio il funzionamento generale dell’algorit-

mo, mentre al capitolo 6 e lasciata la descrizione delle scelte progettuali e implementative.

La sua presentazione e stata realizzata con lo scopo principale di dimostrare la validita

dell’approccio; molte considerazioni possono essere fatte, al fine di migliorarlo e renderlo

piu efficiente.

5.1 Concetti preliminari

Nel seguito vengono introdotti alcuni concetti, necessari per comprenderne al meglio la

struttura dell’intero sistema realizzato.


5.1.1 Sistema di riferimento

Considerando che in questa tesi sono stati prese in considerazione esplorazioni di spazi

bidimensionali, per specificare la posizione del robot e stata utilizzata la convenzione

che prevede un riferimento globale per il piano (XI , YI) e uno locale al robot (XR, YR),

come riportato in figura 5.1. Una volta scelto il punto P , la generica posizione (posa)

sulla mappa sara individuata dalla terna (x, y, θ).

P

YR

XR

θ

YI

XI

Figura 5.1: Sistema di riferimento per il robot

5.1.2 Esplorazione mediante frontiere

Per un robot mobile che non ha conoscenza a priori dell’ambiente e deve quindi esplorarlo,

un approccio abbastanza noto in letteratura e quello descritto in [Yam97], basato sul

concetto di frontiera. Essa rappresenta la regione di che delimita lo spazio esplorato e

quello non esplorato; in figura 5.2 e rappresentato, in bianco lo spazio esplorato, in nero

gli ostacoli, in blu lo spazio inesplorato e i punti viola rappresentano il punto selezionato

come rappresentante della frontiera, dato che essa e composta da tutti i punti bianchi

che confinano con il blu. A volte, a partire dai punti di frontiera, per calcolare il punto

Figura 5.2: Esplorazione basata su frontiere

che la rappresenta unicamente, viene utilizzato semplicemente il baricentro di tutti i suoi


punti. Nel paragrafo 6.2.1 e possibile consultare dettagli sull’implementazione software

concernente la ricerca di frontiere.

In questo la rappresentazione spaziale dell’ambiente viene fatta su occupancy grid,

in cui, ad ogni rilevazione dei sensori del robot (sonar, laser, infrarossi) viene modificata

la probabilita che in una determinata cella della mappa sia presente un ostacolo o meno.

Per la ricerca delle frontiere nella mappa di solito vengono utilizzati strumenti della

computer vision, raggruppando tutte le celle facenti parti dello spazio esplorato (bianco)

e suddividendole in differenti regioni di frontiera, utilizzando tecniche di blob coloring

[BB82]. Ogni regione con un numero di punti maggiore di una determinata soglia e

considerata un frontiera.

Questo tipo di approccio, basato sulle frontiere, si presta bene ad ambienti indoor

e outdoor, in cui gli ostacoli possono trovarsi in posizioni arbitrarie, permettendo di

estendere gradualmente gli spazi di esplorazione.

5.1.3 Configurazione dell’agente

Nel seguito si assumera di lavorare con un agente configurato per l’esplorazione auto-

noma, ovvero con componenti software e sensori in grado di permettere lo spostamento

del robot mobile da un punto libero della mappa ad un altro, in maniera indipendente

e senza intervento dell’operatore. Negli esperimenti effettuati, sia in simulazione che

nella realta, sono presenti dei moduli dedicati al mapping, alla localizzazione, al motion

control e alla navigazione, appartenenti alla piattaforma di sviluppo SPQR-RDK, intro-

dotta al paragrafo 1.6. Dal punto di vista dei sensori, oltre all’odometria, e presente un

laser scanner che permette di effettuare agevolmente esplorazione basata su frontiere.

5.2 Esplorazione guidata dal LQI - Descrizione dell’algo-

ritmo

In questa parte della tesi, viene descritto in dettaglio il funzionamento dell’algoritmo

di esplorazione per robot mobili, basato sulla qualita del segnale ricevuto da disposi-

tivi ZigBee. Per il momento la trattazione viene affrontata dal punto di vista teorico,

tralasciando alcuni aspetti implementativi che verranno illustrati al capitolo 6.

Iniziamo col dire che l’assunzione principale che viene fatta dall’algoritmo, e quella

di avere a disposizione dei nodi beacon presenti nell’ambiente da esplorare, in grado di

inviare dei messaggi a dei nodi subscribers che ne fanno richiesta. Nella fase preliminare,

il robot deve scegliere il beacon verso cui avvicinarsi. Considerando che in un dato istante

piu dispositivi ZigBee possono trovarsi nel raggio di copertura, esso ne seleziona uno

come quello obiettivo da raggiungere, basandosi su un determinato criterio (ad esempio

sceglie il nodo con LQI medio maggiore).


Figura 5.3: Discretizzazione dell’ambiente e matrice LQI

Un’astrazione importante che viene effettuata sull’ambiente esplorato, e che sara la

base da cui partire per fornire una differente priorita frontiere, e la suddivisione della

mappa (ottenuta dagli algoritmi di mapping) in celle equidimensionate e di proporzioni

adeguate alla mappa stessa (fig. 5.3): tale suddivisione favorisce la discretizzazione

dell’ambiente ed e rappresentata numericamente da una matrice Mlqi (eq. 5.1), in cui

ogni elemento indica il LQI della rispettiva cella sulla mappa (fig. 5.3). In base alla

frequenza con cui il nodo presente sul robot e il beacon si scambiano messaggi (da cui,

in ricezione, viene estratto ogni volta il LQI), puo accadere che il primo si trovi ancora

all’interno della stessa cella e in quel caso sul valore LQI puo essere effettuata una media

o un altro tipo di filtraggio.

Mlqi =

156 N.D. N.D. N.D. N.D. N.D. · · · N.D.

N.D. 163 175 N.D. N.D. N.D. · · · N.D.

N.D. 151 159 178 N.D. N.D. · · · N.D.

121 144 N.D. 157 N.D. N.D. · · · N.D....

......

......

.... . .

...

N.D. N.D. N.D. N.D. N.D. N.D. · · · N.D.

(5.1)

Come e facile notare (eq. 5.1), una possibile istanza di Mlqi, contiene la storia di tutte le

osservazioni del LQI, effettuate solo dove l’agente e transitato (negli altri casi la matrice

riporta il valore N.D.); questa matrice sara il dato principale con cui viene decisa la

prossima frontiera verso cui muoversi.

L’esplorazione guidata dal LQI procede ad ogni passo selezionando una nuova fron-

tiera, precisamente quella che presenta lo score piu alto, in base all’euristica che verra

illustrata nella sezione 5.2.1. Per ridurre la complessita dell’algoritmo, durante lo spo-

stamento da una frontiera all’altra, non vengono eseguite ulteriori azioni se non quella

di continuare a raccogliere dati sul LQI, che vanno a popolare la matrice Mlqi. Come


ausilio per l’esposizione, ci riferiremo nel seguito alla macchina a stati di figura 5.4, per

esaminare i differenti comportamenti dell’algoritmo nelle varie fasi di esplorazione.

Il robot, una volta selezionato il beacon parte dallo stato STOPPED e, quando viene

attivato il modulo di navigazione, sceglie la prima frontiera di esplorazione in modo

casuale tra quelle trovate, non avendo dati sufficienti per agire diversamente; mentre si

dirige verso la frontiera selezionata, lo stato permane in GATHERING, ovvero la matrice

Mlqi viene aggiornata con i valori del LQI rilevati durante lo spostamento. Ogni volta

che viene raggiunto il punto frontiera, lo stato passa in CLEVER CHOICE, nel quale viene

scelta la prossima frontiera da esplorare, in base agli score riportati da tutte quelle

disponibili.

Va notato che nel calcolo dello score di una frontiera, viene considerata anche la sua

distanza dal robot (a parita di score, la frontiera piu vicina incrementa il suo score); e

ovvio che non e possibile invocare il path planner per ogni frontiera, in quanto troppo

oneroso computazionalmente, per cui nel calcolo dello score viene utilizzata una metrica

euclidea. Il controllo sulla lunghezza del path viene effettuato una volta selezionata

quella con score piu alto, calcolando il path e controllando in che proporzioni sono

distanza del path e distanza euclidea. Se il path e troppo lungo, tale frontiera viene

scartata e si passa alla seconda con score piu alto, e cosi via (fig. 5.7).

STOPPED

RANDOMCHOICE

CLEVERCHOICE

GATHERING

DEEPSCAN

NEARTARGET

(Navigator enabled & Beacon choosen)

Navigatordone currentLQI >

deepScanLqiThreshold

Best frontier choosen

No more frontiers

currentLQI > nearTargetLqiThreshold

Navigator disabled

Too long computed path(planner)

Frontiers scores

too close

Random frontier choosen

Navigatordone

Figura 5.4: Macchina a stati dell’algoritmo di esplorazione

Il ciclo di stati GATHERING-CLEVER CHOICE si ripete, finche il LQI ricevuto dal robot

non supera una determinata soglia (deepScanLqiThreshold), selezionata a priori; lo

stato dell’algoritmo a questo punto transita in DEEP SCAN, una modalita in cui viene

utilizzata una seconda mappa, in ausilio a quella classica costruita con le scansioni

del range finder dai moduli di mapping. Essa e sostanzialmente un clone della mappa


originale, in cui viene simulata una scansione con raggio di apertura molto minore2, che

consente di muoversi a step piu brevi (fig. 5.5). Questa operazione e necessaria, dato che

una volta che il laser scanner nella sua scansione non trova piu frontiere, l’esplorazione

continua sulle altre, non considerando il fatto che il nodo beacon da raggiungere potrebbe

trovarsi proprio nell’area della scansione appena effettuata. Ovviamente, per semplificare

il riconoscimento di quest’ultimo quando si e nelle vicinanze, possono essere utilizzate

tecniche ausiliarie, come la visione artificiale [BB82].

Figura 5.5: La mappa in modalita DEEP SCAN

Dallo stato DEEP SCAN, si esce quando il LQI supera una seconda soglia, che rap-

presenta una situazione in cui trasmettitore e ricevitore sono ad una distanza di circa 2

metri. In questo caso lo stato diventa NEAR TARGET e il robot si ferma immediatamente

nella posizione in cui si trova, indicando che nodo beacon e nelle immediate vicinanze.

5.2.1 Calcolo degli score delle frontiere

Il punteggio (score) di una frontiera, rappresenta l’indicatore di preferenza principale,

mediante il quale, ad ogni passo dell’esplorazione, viene stabilito l’ordinamento delle

frontiere. L’attribuzione dello score, come vedremo, si basa principalmente sulla matrice

Mlqi e sulla divisione della mappa in celle. Le coordinate di un punto (x, y) sul piano

della mappa (XI , YI) (par. 5.1.1), quando necessario, vengono convertite nella relativa

cella e quindi in indici sulla matrice Mlqi, come ad esempio accade per la posa del robot

e i punti rappresentanti delle frontiere.

L’esempio esplicativo al quale ci riferiremo per la spiegazione e illustrato in figura

5.8, in una condizione in cui e necessario scegliere tra due possibili frontiere. La griglia

rappresenta Mlqi, con i valori di LQI rilevati nelle differenti celle. Come vediamo, anche

il robot e le frontiere sono posizionate su celle.2Ad esempio, nei nostri esperimenti, il laser scanner Hokuyo ha un raggio di 4 metri, mentre la

scansione ridotta viene effettuata con raggio pari a 1 metro


L’algoritmo per il calcolo degli score (Algoritmo 1) viene invocato ogni qualvolta sia

necessario selezionare una frontiera di esplorazione, tra quelle disponibili al momento.

In input viene fornito l’insieme delle frontiere F e la matrice Mlqi, mentre in output

e restituito l’insieme delle frontiere ordinato per score. Quando parleremo di distanza

nella spiegazione, ci riferiremo sempre alla distanza euclidea, calcolata sulle matrici e

quindi relativa alle celle. Ad esempio per due generici elementi α = (i, j) e β = (k, l)

essa vale:

dist(α, β) =√

(i− k)2 + (j − l)2.

Input: F : l’insieme delle frontiere - Mlqi: la matrice che contiene i valori LQI

Output: Ford: l’insieme delle frontiere ordinato per score

foreach Frontiera Fi ∈ F do1

Fdisti ← Calcola la distanza (euclidea) del robot dalla frontiera i;2

Mdisti ← Calcola matrice delle distanze per la frontiera i;3

end4

maxDist← Calcola la massima distanza possibile tra elementi di Mlqi;5

foreach Matrice Mdisti ∈Mdist do6

S1 ← 0;7

S2 ← 0;8

minDisti ← Calcola la distanza minima in Mdisti ;9

foreach mdist(j,k)∈Mdisti do10

if minDisti ≤ mdist(j,k)≤ minDisti + ∆(minDisti) then11

S1 ← S1 +Mlqi(j, k) · (maxDist−mdist(j,k));12

S2 ← S2 +mdist(j,k);13

end14

end15

Scorei ← S1S2

+ 1minDisti

−√Fdisti ;16

end17

Score ← Ordina gli score in modo decrescente;18

Ford ← Ordina le frontiere in base allo score riportato;19

return Ford;20

Algoritmo 1: Algoritmo per il calcolo degli score

Di seguito l’algoritmo viene spiegato in dettaglio, motivando le scelte computazio-

nali effettuate. Molte di esse sono ricavate empiricamente, sulla base delle numerevoli

sperimentazioni eseguite in simulazione. Per comprendere al meglio i calcoli effettuati,

si consulti l’esempio numerico presente al paragrafo 5.2.1.1.

L’esecuzione dell’algoritmo per il calcolo degli score (Algoritmo 1) procede come

segue:


1. Per ogni frontiera Fi ∈ F :

• Viene calcolata la sua distanza dal robot e inserita nel vettore Fdist, in

posizione i.

• Viene calcolata la sua matrice di distanze Mdisti , ovvero la distanza della

frontiera da ogni elemento di Mlqi diverso da N.D., e inserita nel vettore di

matrici Mdist, in posizione i.

2. Calcolo della massima distanza possibile sulla matrice Mlqi. Se ad esempio essa ha

dimensioni 20×20, maxDist =√

800. Tale valore sara necessario successivamente

per effettuare la media pesata (linea 12).

3. Per ogni matrice Mdisti ∈Mdist:

• S1 e S2, che conterranno delle somme parziali, vengono inizializzati a 0.

• Tra le distanze presenti in Mdisti , viene calcolata quella minima e inserita nel

vettore minDist in posizione i.

• Per ogni elemento mdist(j,k)∈Mdisti :

– Se il valore dimdist(j,k)e compreso traminDisti eminDisti+∆(minDisti),

allora vengono eseguite le due somme parziali S1 e S2, che serviranno per

effettuare la media pesata dei valori del LQI con la distanza. Questo signi-

fica che solo alcuni valori di Mdisti (quelli che appunto si trovano a distan-

za compresa tra minDisti e minDisti + ∆(minDisti)) vengono conside-

rati. Ad esempio, in figura 5.8 sono rappresentati con diversi colori i valori

di Mlqi considerati, a seconda della frontiera. La media pesata dei valori

LQI per ogni frontiera sara del tipo: LQIi =∑

j Mlqi(j,k)·(maxDist−dist(j,k))∑j(maxDist−dist(j,k))

,

dove S1 =∑

j Mlqi(j, k) · (maxDist − dist(j,k)) e S2 =∑

j(maxDist −dist(j,k)). Questo tipo di media fornisce un peso piu alto ai valori del

LQI piu vicini alla frontiera, rappresentando il fatto che essi risultano

maggiormente rappresentativi rispetto a quelli piu distanti.

∆(minDist) e una funzione ricavata empiricamente e dipende dalla mi-

nima distanza della frontiera i da un elemento valido di Mlqi (ovvero

minDisti). Essa modella il fatto che a differenti distanze minime, l’in-

sieme dei valori che rappresentano la frontiera (considerati quindi per il

calcolo di LQIi) varia: ad esempio a piccole distanze i valori scelti sono in

quantita minori che a distanze grandi. La funzione utilizzata e graficata

in figura 5.6.

– Lo Scorei, relativo alla frontiera Fi, viene ricavato mediante la formu-

la: S1S2

+ 1minDisti

−√Fdisti . Il termine S1

S2rappresenta il risultato della

media pesata, mentre il termine 1minDisti

fornisce uno score piu basso


1 2 3 4 5 60.4

0.5

0.6

0.7

0.8

0.9

1

1.1

1.2

1.3

minDist

∆(m

inD

ist)

Figura 5.6: Grafico della funzione ∆

alle frontiere con minDisti piu alto, indicando il fatto che frontiere ec-

cessivamente distanti dai valori di Mlqi possono essere rappresentate in

modo non veritiero. Stessa valutazione viene fatta per il termine ne-

gativo −√Fdisti , in quanto le frontiere piu distanti dal robot vedono

maggiormente decrementato il loro score (e piu costoso raggiungerle).

Dato che in questa fase stiamo considerando solo la distanza euclidea,

occorre evidenziare che, solo in fase di scelta definitiva della frontiera

(nella macchina a stati illustrata in figura 5.4), verranno risolte situazioni

come quelle di figura 5.7.

Fdist

Robot

FrontieraPath

Figura 5.7: In questo caso la Fdist e piccola, mentre la lunghezza del path per rag-giungerla e abbastanza grande. In questo la frontiera potrebbe essere scartata, per

lasciare il posto ad una eventualmente piu vicina e con score di poco inferiore.

4. Infine, le frontiere vengono ordinate in modo decrescente, in base agli score ripor-

tati.

5.2.1.1 Un esempio di esecuzione

Ritornando all’esempio di figura 5.8, procediamo all’esecuzione dell’algoritmo per le due

frontiere per verificare quale delle abbia score piu alto dell’altra. I calcoli forniscono i

seguenti risultati:


156

163 175

159 178

162144121

151

minDist2

Robot

Frontiera

F1

F2

Fdist2

Celle relative a F1Celle relative a F2minDist1

Fdist1

Obiettivo

Figura 5.8: Calcolo degli score per le frontiere

• Fdist = [√

8√

8 ]

• Mdist1 =

5.01 N.D. N.D. N.D. N.D. N.D. N.D.

N.D. 4 3 N.D. N.D. N.D. N.D.

N.D. 4.12 3.16 2.23 N.D. N.D. N.D.

5.38 4.47 N.D. 2.82 N.D. N.D. N.D.

N.D. N.D. N.D. N.D. N.D. N.D. N.D.


Mdist2 =

5.01 N.D. N.D. N.D. N.D. N.D. N.D.

N.D. 4 4.12 N.D. N.D. N.D. N.D.

N.D. 3 3.16 3.60 N.D. N.D. N.D.

2.23 2 N.D. 2.82 N.D. N.D. N.D.



• minDist1 =

√5 = 2.23 e minDist2 = 2

• ∆(minDist1) = 0.95 e ∆(minDist2) = 1

• F1 : 2.23 ≤ mdist(j,k)∈Mdist1 ≤ 3.18

– Mdist(2,3)= 3⇒Mlqi(2,3)

= 175

– Mdist(3,3)= 3.16⇒Mlqi(3,3)

= 159

– Mdist(3,4)= 2.23⇒Mlqi(3,4)

= 178

– Mdist(4,4)= 2.82⇒Mlqi(4,4)

= 162


• F2 : 2 ≤ mdist(j,k)∈Mdist2 ≤ 3

– Mdist(4,2)= 2⇒Mlqi(4,2)

= 144

– Mdist(3,2)= 3⇒Mlqi(3,2)

= 141

– Mdist(4,1)= 2.23⇒Mlqi(4,1)

= 122

• maxDist =√

(1− 6)2 + (1− 7)2 = 9.21

• LQI1 = 175·6.21+159·6.05+178·6.97+162·6.386.21+6.05+6.97+6.38 = 168.8

Score1 = 168.8 + 12.23 −

√2.82 = 167.36

• LQI2 = 144·7.21+151·6.21+121·6.977.21+6.21+6.97 = 138.26

Score2 = 138.26 + 12 −√

2.82 = 137.08

La frontiera con lo score maggiore risulta essere F1, che verra pertanto selezionata come

target dal sottosistema di navigazione del robot. Rimane valido in ogni caso il ragio-

namento descritto al paragrafo precedente, che tiene in considerazione la lunghezza del

percorso calcolato dal path planner verso il punto rappresentante della frontiera.

Un aspetto rilevante dell’algoritmo, e la capacita di uscire facilmente dai massimi

locali, situazioni che possono facilmente presentarsi in approcci di tipo a gradiente o a

campi di potenziale. L’accumularsi delle letture durante lo spostamento verso le fron-

tiere, aggiorna la conoscenza che il robot ha della mappa, permettendogli di scartare

ad ogni passo le zone che in precedenza apparivano come le migliori, ma che una volta

raggiunte riportano un basso valore LQI.

5.3 Possibili scenari

In questa sezione vengono descritti alcuni degli scenari in cui l’approccio presentato puo

dimostrare la sua utilita.

5.3.1 Rendezvous

Il problema del rendezvous [DR97, ZLV07] consiste nell’incontro, da parte di due o piu

agenti, in un punto e ad un orario ben determinato. Nei sistemi multi-robot avere questo

e un bisogno inerente. La possibilita di incontrarsi facilita innanzitutto la localizzazio-

ne e facilita il coordinamento nell’esplorazione di grandi ambienti, riducendo il tempo

necessario al completamento.

Nel nostro caso, i punti selezionati per il rendezvous (chiamati anche landmark),

possono essere pensati come dei nodi ZigBee lasciati nell’ambiente o installati sui robot.

Dato che ogni robot possiede un ricevitore, utilizzando le informazioni sul LQI e un’op-

portuna euristica e possibile raggiungere il landmark, a patto ovviamente che esso non


sia in condizioni di mobilita. Considerata l’autonomia energetica e soprattutto il costo

contenuto di questi dispositivi, questa situazione e facilmente realizzabile.

Va aggiunto che in scenari di rendezvous esistono due problemi a priori, ovvero come

scegliere il landmark e quale landmark selezionare dall’insieme di quelli potenzialmente

disponibili, temi che vanno oltre gli scopi di questa tesi.

5.3.2 Rescue robots

Nel campo della robotica di soccorso e, in particolare, in ambito Search and Rescue

[HSI+99, CFIN07, MNG06, NA07], e facile immaginare come informazioni sulla loca-

lizzazione di punti di interesse (ostacoli, feriti, punti di raccolta, altri robot) possano

divenire di estrema importanza per accelerare i tempi di esplorazione di aree devastate,

con la conseguenza di aumentare la probabilita di salvare anche vite umane. Si compren-

de inoltre quanto cio sia di interesse primario in ambienti indoor (uffici, abitazioni), o

dove comunque non c’e la possibilita di utilizzare altri sistemi di posizionamento (come

ad esempio GPS).

Considerate le possibilita di miniaturizzazione che possono essere raggiunte nella

produzione di dispositivi ZigBee, possiamo pensare ad uno scenario in cui ogni per-

sona indossi un ricevitore e che, nel caso di incidenti o devastazioni esso possa essere

interrogato, in modo da facilitare il raggiungimento della vittima stessa. Ad esempio,

tali situazioni possono verificarsi in impianti industriali ad alto rischio, dove possono

avvenire incendi, cedimenti strutturali o emissioni di sostanze tossiche.

Nelle squadre multi-robot, l’algoritmo di esplorazione guidata puo aiutare un robot

a trovare un altro membro della squadra in difficolta, perche esso fornisce funzionalita

particolari che l’altro non possiede (ad esempio, un robot “demolitore”, potrebbe riuscire

a liberare un passaggio bloccato da eventuali ostruzioni).

5.3.3 Deployment di reti ad-hoc

Sempre per quanto riguarda scenari di soccorso robotico, un’idea interessante e quella

di sfruttare l’approccio presentato per gestire efficientemente il deployment di una rete

di comunicazione wireless ad-hoc, in situazioni di emergenza [RB05]. In molti casi, la

presenza di una infrastruttura di rete, consente il controllo e monitoraggio da parte

dell’operatore esterno, permettendo inoltre di mantenere le comunicazioni tra le squadre

di robot distanti [HMS02].

Il problema che si presenta, e quello di massimizzare la copertura della rete, mi-

nimizzando il numero di nodi necessari. Apportando alcune modifiche all’algoritmo

presentato, e possibile far trovare autonomamente al robot le zone in cui la qualita del

segnale e piu bassa, considerando ovviamente una mappa del LQI per ogni dispositi-

vo e ragionando sull’intersezione delle stesse. In questo modo e come ci trovassimo in


una logica invertita rispetto al problema originale, cercando di scegliere le frontiere che

minimizzano il LQI.

5.3.4 Sorveglianza

In scenari di sorveglianza mediante robot mobili [HBB+00], l’impiego dell’algoritmo

di esplorazione puo fornire vantaggi per il monitoraggio di oggetti che frequentemente

vengono cambiati di posizione. Si pensi ad esempio a delle telecamere mobili, in grado

di rilevare condizioni di allarme e che sono equipaggiate con un dispositivo ZigBee; il

robot puo raggiungere piu efficientemente il luogo in cui si e verificato l’evento, senza

conoscenza a priori sulla posizione della telecamera, che puo quindi essere spostata a

seconda delle necessita, senza il bisogno ogni volta, di registrare su una mappa questi

cambiamenti.

Capitolo 6

Sperimentazione

In questo capitolo vengono presentate le problematiche relative all’implementazione del-

l’algoritmo di esplorazione descritto al capitolo 5 e i risultati ottenuti in sperimentazione,

in ambiente reale e simulato.

La fase di implementazione ha previsto lo sviluppo di due applicazioni distinte, una

riservata ai dispositivi ZigBee, successivamente integrata con l’applicazione in esecuzione

a bordo del robot. In questo caso, la realizzazione delle nuove componenti e stata eseguita

integrando moduli gia esistenti, facenti parte del framework per robot mobili SPQR-RDK

(par. 1.6). Dopo una descrizione dell’applicazione ZigBee realizzata, vengono illustrati

i nuovi moduli implementati e gli aspetti fondamentali dell’ambiente di simulazione

impiegato durante la sperimentazione dell’algoritmo.

La parte conclusiva del capitolo e riservata alla descrizione delle sperimentazioni

effettuate, sia in ambiente simulato (utilizzando la piattaforma Player/Stage) che in

ambiente reale, utilizzando il robot mobile “Rotolotto”, presente al laboratorio SIED.

Dai risultati ottenuti in questa fase, saranno estratte le conclusioni, a cui e dedicato il

capitolo successivo.

6.1 Applicazione per i dispositivi ZigBee

L’applicazione sviluppata per essere eseguita sui dispositivi ZigBee, prevede l’utilizzo di

almeno due dispositivi, di cui un coordinatore (ZC) e uno o piu router (ZR). Il coordina-

tore e installato sul robot mobile ed e collegato mediante interfaccia seriale all’elaboratore

che esegue il software di navigazione. Esso, oltre a possedere le funzionalita descritte al

paragrafo 3.4.3.1, e stato programmato per trovare i dispositivi ZigBee nel suo raggio di

copertura (vicinato) ed effettuare richieste ai nodi beacon (ZR).

I ZR, a loro volta, rispondono alle richieste del coordinatore, inviando periodicamente

un messaggio di beacon. Da questi messaggi, in ricezione, e possibile estrarre il valore

del LQI che mediante un apposito formato dati viene scritto sulla porta seriale USB e

letto dall’applicazione di interfaccia, in esecuzione sul robot.

87

Capitolo 6. Sperimentazione 88

Da un punto di vista implementativo, l’applicazione residente sui nodi prevede due

cluster (par. 3.4.4), uno per la richiesta (BeaconRequest) e uno per la risposta (BeaconResponse);

e proprio dai messaggi BeaconResponse ricevuti che viene estratto il valore del LQI,

necessario per il funzionamento dell’algoritmo.

L’avvio dell’applicazione avviene mediante i tasti funzione presenti sul dispositivo

(fig. 4.1), ad esempio per la richiesta del vicinato (NeighborhoodRequest) o di beacon.

Per semplificare l’interazione, il dispositivo che risulta avere LQI piu alto tra i vicini

viene scelto automaticamente come nodo obiettivo dall’algoritmo di esplorazione, che

pertanto ricevera esclusivamente da tale nodo i messaggi di beacon durante l’esecuzione.

ZigBee Coordinator ZigBee Router2. BeaconRequest

3. BeaconResponse

1. NeighborhoodRequest

LQI: 81

Figura 6.1: Configurazione dell’applicazione ZigBee

6.2 Applicazione per SPQR-RDK

Dopo la fase di sperimentazione con i dispositivi ZigBee e di ideazione dell’algoritmo

di esplorazione, una parte significativa del lavoro di tesi ha visto l’implementazione

software del sistema sotto forma di moduli per la piattaforma SPQR-RDK. Tutto il

software realizzato e presente nel repository del laboratorio SIED e scaricabile mediante

il tool Subversion1.

Il diagramma delle classi di figura 6.2 fornisce una visione d’insieme del sistema

realizzato; i sottosistemi di localizzazione, mapping, planning e navigazione erano gia

preesistenti e funzionanti. Anche il modulo per la ricerca delle frontiere (par. 5.1.2) era

parzialmente implementato ed e stato modificato per aggiungere nuove funzionalita. I

moduli realizzati interamente sono ZigbeeExplorator e ZigbeeInterface; nel primo

e stata codificata tutta la logica dell’algoritmo per la scelta delle frontiere, mentre nel

secondo e stata implementata l’interfaccia di comunicazione con il dispositivo ZigBee.1http://subversion.tigris.org/.


+readLqiValue()-lqiMap

StaticLqiMap

+readLqiValue()

ZigbeeDriver

+readLqiValue()

ZigbeeInterface

ZigbeeExplorator

+updateLqiValue()-lqiMatrix

LqiGatherer

+computeFrontiersRank()

FrontierChooser

Navigator

Path Planner

Mapping

-score-distance

Frontier

FrontierFinder

ZigbeeExploratorModule

ZigbeeInterfaceModule

Figura 6.2: Diagramma delle classi del sistema

Il diagramma delle classi, sebbene incompleto di alcuni dettagli, aiuta a comprendere

bene le dipendenze tra i moduli e le loro responsabilita nell’intero sistema. Nei para-

grafi successivi essi verranno descritti dettagliatamente, prestando attenzione ad alcuni

dettagli implementativi e alle problematiche che gradualmente si sono presentate.

6.2.1 Modulo FrontierFinder

La ricerca delle frontiere e una operazione fondamentale durante l’esplorazione in am-

bienti sconosciuti, in quanto gradualmente fornisce nuovi punti della mappa da visitare.

Esse sono rilevate trovando le regioni di confine tra la parte di mappa inesplorata e quella

esplorata; quelle con un numero sufficiente di punti vengono considerate frontiere.

Nel nostro caso, il modulo di ricerca delle frontiere era gia presente, anche se par-

zialmente implementato. Esso era in grado di fornire, per ogni frontiera, l’insieme dei

punti che la costituiva; dal punto di vista della navigazione pero, e utile trovare anche

un rappresentante di questi punti, in modo che sia possibile fornirlo come target al ro-

bot. Un approccio comune [Yam97] e quello di calcolare il centroide (o baricentro) dei

punti, dato che, considerata la natura convessa delle regioni di frontiera, tale punto per

definizione ricade all’interno della parte di mappa esplorata.

Questo ragionamento, anche se corretto, porta in alcune situazioni particolari a tro-

vare i rappresentanti troppo vicini agli ostacoli. Per questo motivo, e stata sfruttata una

informazione fornita dal modulo di mapping, la cosiddetta distance map; sostanzialmen-

te essa e una mappa in cui ogni punto indica la distanza dall’ostacolo piu vicino (fig.

6.3(a)). In questo modo, il rappresentante della frontiera, puo essere trovato calcolando


(a) La distance map (b) Le frontiere trovate

Figura 6.3: Le frontiere trovate con l’ausilio della distance map

un centroide pesato con la distanza dagli ostacoli e fornendo quindi piu rilevanza ai punti

lontani dagli ostacoli. Ad esempio, per trovare F = (Fx, Fy) si ottiene:

Fx =

∑j(pxj) · dxj∑

j dxj, Fy =

∑j(pyj) · dyj∑

j dyj

.

In figura 6.3(b), con differenti colori sono marcate le regioni di frontiera, mentre i punti

viola sono i rappresentanti trovati utilizzando il centroide e la distance map.

6.2.2 Modulo ZigbeeInterface

L’intero approccio descritto in questa tesi si basa sulla possibilita di ottenere, in ogni

momento, il valore del Link Quality Indicator sui pacchetti in ricezione. Durante l’im-

plementazione, per ottenere questo dato, si sono verificati principalmente due problemi;

in fase di simulazione era necessario emulare il comportamento del nodo ZigBee e di

conseguenza la variazione di LQI al cambiamento di posa dell’agente rispetto al nodo

beacon, mentre in fase di test sul robot reale era necessario interfacciarsi fisicamente con

il dispositivo.

La soluzione al primo problema e abbastanza intuitiva, ma ha consentito di non

rendere troppo complessa la sperimentazione dell’algoritmo di esplorazione. Esistono

numerosi software commerciali in grado di simulare abbastanza fedelmente campi elet-

tromagnetici, anche in ambienti indoor, ma un tale livello di complessita non era tuttavia

richiesto. L’idea e stata quella di effettuare misurazioni accurate del LQI, “campionan-

do” opportunamente l’ambiente secondo la configurazione descritta al paragrafo 4.3.1 e,

successivamente, mediante una interpolazione bidimensionale generare la mappa statica

del LQI utilizzata per la simulazione (fig. 6.4(b)), dove le zone piu “calde” indicano un

valore LQI piu alto rispetto alle zone “fredde”. Tale mappa viene sovrapposta idealmen-

te a quella dell’ambiente da esplorare, permettendo di avere in ogni punto il valore del


LQI in ricezione. Inoltre, considerando i risultati di figura 4.6, e possibile introdurre

una funzione di rumore gaussiano additiva che faccia variare leggermente i valori della

mappa statica, per rendere piu realistiche le letture del valore LQI2.

(a) Posizioni per le misurazioni (b) Mappa del LQI generata con interpo-lazione bicubica

Figura 6.4: Generazione della mappa statica per il LQI

L’interfacciamento fisico al dispositivo e stato tutt’altro che elementare, in quanto i

driver esistenti erano solo per piattaforma Windows. Cio ha richiesto la modifica e la

compilazione di un driver per Linux di un altro produttore, adattandolo al dispositivo a

nostra disposizione. Una volta completata questa operazione, e stato possibile estrarre

il valore del LQI scrivendo un piccolo parser per le stringhe ricevute sulla porta seriale.

In condizioni dinamiche inoltre, come e possibile osservare in figura 4.9, l’andamento

del LQI presenta degli outlier che devono essere filtrati. Per completare tutto cio in

tempo reale occorre una computazione efficiente come una media o un filtro di Kalman

[Kal60]. Per i nostri scopi e stato sufficiente eseguire una media mobile del tipo:

LQIt = α · LQIt + (1− α) · LQIt−1,

dove α ∈ R e 0 ≤ α ≤ 1. Tale parametro determina quanto pesa il valore LQI appena

letto rispetto alla media ottenuta al passo precedente. Negli esperimenti effettuati,

ponendo α = 0.85, si ottiene un sufficiente smoothing sui valori rilevati, senza necessita

di implementare altri filtri piu complessi.

Come e possibile osservare in figura 6.2, il modulo e stato progettato per essere

trasparente rispetto al metodo utilizzato per leggere il LQI, che sia proveniente dalla

mappa statica o dal dispositivo reale. Il metodo readLqiValue che viene eseguito a

run-time e specificato nel file di configurazione, mediante una variabile booleana.2In questo modo, se il robot transita piu volte nella stessa posizione della mappa, ottiene valori di

LQI differenti.


6.2.3 Modulo ZigbeeExplorator

In questo modulo e racchiusa tutta la logica dell’algoritmo, descritta al paragrafo 5.2. In

particolare, nella classe principale ZigbeeExplorator e stata implementata la macchina

a stati di figura 5.4; il suo scopo principale e coordinare l’esecuzione del FrontierChoo-

ser, per l’assegnazione dello score alle frontiere (rappresentate dalla classe Frontier), e

del modulo di navigazione, al fine di raggiungere di volta in volta il target selezionato. Il

modulo e impostato per essere schedulato ogni 500 ms, che risulta anche l’intervallo con

cui l’oggetto LqiGatherer ha la responsabilita di registrare i dati del LQI, provenienti

dalla ZigbeeInterface.

6.2.4 Moduli di navigazione

I moduli per la navigazione autonoma in ambiente sconosciuto erano gia implementati e

funzionanti. L’approccio scelto e una navigazione a due livelli, in cui viene impiegato un

path planner globale (basato sull’algoritmo A∗) e un controllore di basso livello (motion

planner) che suddivide il path in sottobiettivi di rapida attuazione, in cui il robot deve

seguire la traiettoria evitando eventuali ostacoli. In questo modo il movimento del robot

e funzione sia delle percezioni sensoriali che della posizione relativa dall’obiettivo.

6.2.5 Moduli di localizzazione e mapping

Per eseguire efficientemente i task di navigazione, sono di primaria importanza i moduli

di localizzazione e mapping, che si occupano di stimare consistentemente la posizione

del robot e la mappa dell’ambiente esplorato, a partire dalle rilevazioni dei sensori (scan

matching [MLM05]). In questo modulo viene costruita anche la distance map, che viene

utilizzata per pesare opportunamente il centroide della frontiera (par. 6.2.1).

6.3 Simulazione

Nello sviluppo e sperimentazione dell’algoritmo, ha avuto importanza rilevante impiegare

un adeguato ambiente di simulazione, nel quale e stato possibile verificare velocemente

le prestazioni su diversi ambienti, senza utilizzare necessariamente il robot reale.

La piattaforma impiegata e stata esclusivamente Player/Stage, in quanto era suffi-

ciente una rappresentazione bidimensionale dell’ambiente da esplorare. La configurazio-

ne del robot impiegato e molto simile a quella reale; e stato utilizzato un modello del

Pioneer P2-AT, con laser scanner Sick. Per emulare la lettura istantanea del valore del

LQI dal dispositivo, la mappa generata con interpolazione e stata sovrapposta idealmen-

te a quella del simulatore, facendo in modo che le coordinate del pixel sulla mappa LQI

coincidano con la posizione del robot rispetto alla mappa dell’ambiente, come e possibile


osservare in figura 6.5. In questo modo e possibile simulare facilmente diversi ambienti,

con differenti distribuzioni del segnale.

LQI Value: 79Cell (4,3)

Figura 6.5: Simulazione dell’algoritmo in Player/Stage

6.4 Esperimenti

Una volta terminata la fase di progettazione e implementazione dell’algoritmo di esplo-

razione, una parte del lavoro ha visto la sua sperimentazione sia in simulazione che in

ambiente reale. Essi tendono a mostrare la validita dell’approccio scelto, sottolineando i

vantaggi introdotti. In entrambi i casi sono considerati ambienti indoor, semistrutturati

ed esplorabili per mezzo di robot mobili su ruote dotati di laser scanner.

Va sottolineato il fatto che, i risultati ottenuti, non sono stati confrontati diretta-

mente con gli altri approcci esistenti, in quanto poco significativi, considerando che la

loro strategia di scelta delle frontiere e quasi esclusivamente greedy e non considera altre

sorgenti di informazione, come invece accade con l’algoritmo implementato.

6.4.1 Esperimenti in simulazione

La configurazione utilizzata in simulazione e quella descritta al paragrafo 6.3, conside-

rando ogni volta planimetrie e mappe LQI differenti. In ogni simulazione, nell’ambiente

Stage, sono presenti due robot; uno rappresenta l’obiettivo da raggiungere (che conserva

quindi la stessa posizione per tutta l’esecuzione) e su cui e installato il nodo che invia i

messaggi beacon, mentre l’altro e quello che esegue l’algoritmo di esplorazione guidata,

basato sulla qualita del segnale ricevuto dal suo dispositivo.


Nelle figure che seguono sono presentati gli esiti dei differenti esperimenti, realizzati

in altrettanti ambienti. In rosso e rappresentato il robot mobile su cui e in esecuzione

l’algoritmo di esplorazione, mentre in blu e indicato, anch’esso come un robot, l’obiettivo

da raggiungere. Come e facile notare, osservando i tracciati di esplorazione nelle figure

6.6, 6.7 e 6.8, le scelte effettuate dall’algoritmo forniscono un contributo determinante per

la ricerca del nodo obiettivo. L’euristica basata sul LQI aiuta a ridurre lo spazio di scelta

delle frontiere, eliminando quelle in cui l’andamento del segnale non e significativamente

alto, permettendo un’esplorazione piu rapida ed efficace dell’ambiente. In generale, il

comportamento del robot, e quello di tentare ad entrare nelle stanze e appena riscontra

un abbassamento eccessivo della qualita del segnale, prosegue per il corridoio.

Considerando che i calcoli sono effettuati basandosi sulla qualita del segnale e che

tale grandezza in ambienti indoor e abbastanza variabile, possono verificarsi casi come

quello di figura 6.8(b) in cui il robot crede di aver trovato il nodo obiettivo, anche se

esso si trova dietro un ostacolo. Ovviamente, in tali situazioni, possono contribuire al

corretto criterio di arresto dell’algoritmo altre metodologie di ricerca, che fanno uso di

sensori alternativi, come ad esempio la visione artificiale.

Figura 6.6: Esecuzione dell’algoritmo in un’abitazione

6.4.2 Esperimenti in ambiente reale

La prova conclusiva dei risultati ottenuti, ha visto la sperimentazione dell’algoritmo rea-

lizzato su un sistema reale, in particolare utilizzando il robot Rotolotto (par 1.2.1) in

un ambiente indoor, precisamente dove sono situati i laboratori RoCoCo e ALCOR,

nel seminterrato del Dipartimento di Informatica e Sistemistica. Come in simulazione,

sono presenti due dispositivi ZigBee, uno sul robot e l’altro che individua l’obiettivo

dell’esplorazione. Nell’esperimento descritto, essa inizia dalla stanza contrassegnata dal

pallino rosso (fig. 6.9) e procede secondo il percorso illustrato, fino alla corretta indivi-

duazione dell’obiettivo (indicato con un quadrato azzurro). In figura 6.10 sono riportate


Figura 6.7: Esecuzione dell’algoritmo nel primo piano del DIS

(a) Esecuzione 1 (b) Esecuzione 2

Figura 6.8: Esecuzione dell’algoritmo nello scenario del labirinto

le foto scattate all’avvio e alla terminazione dell’esplorazione. Si comprende quindi che,

i risultati ottenuti in simulazione, possono essere ricavati anche in situazione reale, sen-

za notevoli limitazioni. L’unico problema riscontrato in alcuni casi e stato la portata

trasmissiva limitata dei dispositivi in alcuni tratti, dovuto comunque alla configurazione

della struttura (ad esempio, a causa dello spessore elevato dei muri).

Come nella simulazione, il percorso seguito dal robot mostra efficacemente le scelte

effettuate dall’algoritmo di selezione delle frontiere, prima di raggiungere l’obiettivo. A

titolo di confronto, il tempo impiegato per l’esplorazione e di 8′30′′, rispetto ai 3′27′′

necessari essendo virtualmente a conoscenza della posizione dell’obiettivo, ma non della

mappa ovviamente.


Percorso effettuato

Punto di partenza

Robot

Obiettivo

Frontiere

Figura 6.9: La mappa generata nell’esplorazione

(a) Situazione di partenza (b) Situazione di arrivo

Figura 6.10: Sperimentazione dell’algoritmo in ambiente reale

Parte III

Risultati e conclusioni

97

Capitolo 7

Conclusioni e sviluppi futuri

7.1 Sintesi dei risultati ottenuti

In questo lavoro di tesi e stato progettato, implementato e sperimentato un algoritmo

per l’esplorazione di ambienti semistrutturati da parte di robot mobili autonomi, basato

sulla potenza del segnale ricevuto da dispositivi ZigBee. La sua realizzazione ha richiesto

la trattazione di numerose problematiche; in primo luogo la scelta dei dispositivi da

utilizzare e lo studio dello standard ZigBee per le reti LR-WPAN, in particolar modo

gli strati MAC, rete e applicazione. Successivamente, contemporaneamente allo studio

dello stato dell’arte nei metodi di localizzazione wireless, sono state effettuate una serie

di sperimentazioni in ambienti indoor e outdoor, al fine di valutare le caratteristiche

trasmissive dei dispositivi selezionati per il progetto. I risultati di questi test, hanno

sicuramente aiutato ad osservare il problema originale sotto un differente punto di vista,

consentendo di sfruttare le informazioni ricavate sulla potenza del segnale ricevuta, non

piu per realizzare un sistema di localizzazione wireless, ma bensı per ricavare indicazioni

utili durante l’esplorazione di ambienti sconosciuti da parte di robot mobili.

L’algoritmo pensato si presenta come un’euristica basata sul LQI (Link Quality In-

dicator), un dato che rappresenta adeguatamente la qualita del collegamento tra due

dispositivi ZigBee, dove il trasmettitore individua il punto di interesse da segnalare e

il ricevitore e installato sul robot, in grado di ricevere tali segnalazioni. Come in altri

approcci [Yam98, BMF+00, KPN, MTK, SB03], l’esplorazione viene eseguita visitando

ad ogni passo visitando le frontiere disponibili; a differenza di essi pero, la selezione della

frontiera migliore, ad ogni passo, e guidata dalle informazioni raccolte sulla variazione

del LQI, che spesso forniscono una buona stima del vantaggio ricavabile dalla scelta.

Una tale funzionalita puo risultare di notevole interesse, ad esempio, nella soluzione di

problemi di rendezvous tra robot [DR97] o per rendere piu efficiente la ricerca in ambito

Search and Rescue [BCC+04].

98

Capitolo 7. Conclusioni e sviluppi futuri 99

Il sistema e stato implementato in C++, sotto forma di moduli per il framework

SPQR-RDK, permettendo di sperimentare velocemente le prestazioni dell’algoritmo, sia

in ambiente simulato che in condizioni reali. I test effettuati hanno dimostrato la validita

dell’approccio, mostrando i benefici che si ottengono nella maggior parte dei casi ana-

lizzati. L’informazione derivante dalla qualita del segnale ricevuto puo essere pertanto

sfruttata positivamente, risultando un buon criterio per la scelta di frontiere, migliore

sicuramente della scelta casuale o greedy (ad esempio, scegliendo la frontiera piu vicina

[YSA98]).

Da un punto di vista personale, posso sicuramente essere soddisfatto dei risultati

ottenuti e delle capacita acquisite durante tutto il periodo di sviluppo della tesi. Le

tematiche affrontate sono risultate di notevole interesse, con la possibilita, inoltre, di

sperimentare i propri studi su un robot reale, oltre che in simulazione.

7.2 Sviluppi futuri ed estensioni

Il sistema presentato pone le fondamenta per la soluzione di un problema base: il rag-

giungimento da parte del robot di un punto nell’ambiente, in cui e presente un dispositivo

che invia dei messaggi di tipo beacon. Tale scenario puo essere certamente esteso, im-

maginando situazioni nel quale diversi robot esplorano l’ambiente e sono equipaggiati

con nodi ZigBee; le funzionalita dell’algoritmo possono essere sfruttate per effettuare dei

rendezvous o coordinare l’esplorazione al fine di aumentare l’area ricoperta nell’intervallo

di tempo disponibile. I dispositivi possono essere rilasciati dinamicamente da un robot

esploratore che magari e piu veloce, indicando il percorso da seguire agli altri membri

della squadra perche piu lenti o zone da evitare perche gia esplorate (in questo caso la

logica dell’algoritmo andrebbe ovviamente invertita, in modo da fornire le zone con LQI

piu basso).

Possono essere aggiunte inoltre, informazioni sulla topologia dell’ambiente mediante

una semantica ad alto livello, al fine di accelerare la ricerca dei punti di interesse; ad

esempio, se si intuisce di trovarsi in un corridoio, conviene prima effettuare un’esplo-

razione preliminare dello stesso al fine di stimare con maggiore accuratezza le possibili

stanze dove l’obiettivo puo trovarsi.

Altri miglioramenti possono essere introdotti, tenendo conto della variazione del LQI

(praticamente il gradiente del LQI) durante lo spostamento tra una frontiera e l’altra,

ad esempio aumentando lo score per quelle che si trovano nel verso di incremento del

LQI o annullando il raggiungimento di una frontiera se l’andamento e eccessivamente

decrescente, gia durante la fase di navigazione verso di essa.

Parte IV

Appendici

100

Appendice A

Piattaforma Freescale MC13213

Sono di seguito riportati i dati tecnici principali del SiP MC13213 di Freescale, montato

sui dispositivi 13213-SRB e 13213-NCB, utilizzati nello sviluppo della tesi.

Modalita di trasferimento Pacchetto e streamFrequenza e canali 2.4 GHz ISM, 16 canali

Throughput 250 Kbps con modulazione O-QPSK e spreading DSSSModalita di funzionamento 4-RF (Off, Hibernate, Doze, Idle) e 4-MCU (Wait, STOP1, STOP2, STOP3)

Sensitivita -92 dBmTensione di funzionamento 2-3.4 V

MCU HCS08 CPU a 40 MHzMemoria Flash 60 KB Flash, 4 KB RAMInput/Output 39 GPIO, ADC 10 bit e 8 canali, 4 timer, 2 SCI, IIC

Potenza in uscita da -27 dBm a +4 dBmTemperatura di funzionamento da -40◦C a +85◦C

Package 9x9x1 mm, 64 pin LGA (RoHS comnpliant)

Tabella A.1: Dati tecnici della piattaforma ZigBee MC13213 di Freescale

In figura A.1 e possibile osservare lo schema a blocchi della piattaforma.

Dig

ital T

rans

ceiv

er

Transmit/ReceiveSwitch

AnalogReceiver

AnalogTransmitter

FrequencyGenerator

Bu�er RAM

IRQ Arbiter RAM Arbiter

PowerManagement

VoltageRegulators

HCS08 CPU

Flash Memory

RAM

Low VoltageInterrupt

KeyboardInterrupt

Internal ClockGenerator

Up to 32GPIOs

COP

16 Bit Timers

I2C

2x SCI

8 Channel10 Bit ADC

BackgroundDebug Module

RFIC Timers

Digital ControlLogic

DedicatedSPI

802.15.4 Modem HCS08 MCU

Balun

BypassCT_Bias SPI

7 GPIO

Figura A.1: Schema a blocchi della piattaforma MC13213

101

Appendice A. Piattaforma Freescale MC13213 102

In figura A.2 e riportato il grafico che mostra la relazione tra la potenza del segnale

ricevuta e quella riportata; si puo notare la non-linearita tra i -45 e i -40 dBm che causa

i fenomeni descritti al paragrafo 4.2.

-85

-75

-65

-55

-45

-35

-25

-15

-85 -75 -65 -55 -45 -35 -25 -15

Input Power Level (dBm)

Rep

orte

d Po

wer

Lev

el (d

Bm

)

802.15.4 Accuracyand Range Requirements

Figura A.2: Grafico potenza ricevuta/riportata

Bibliografia

[Aam06] K. Aamodt. Texas Instruments CC2431 Location Engine - Application

Note AN042. Texas Instruments, 2006. http://focus.ti.com/lit/an/

swra095/swra095.pdf.

[BB82] Dana H. Ballard and Christopher M. Brown. Computer Vision. Prentice

Hall, 1982.

[BCC+04] S. Bahadori, D. Calisi, A. Censi, A. Farinelli, G. Grisetti, L. Iocchi, and

D. Nardi. Intelligent Systems for Search and Rescue. In Proceedings of

Intelligent Robots and Systems Workshop Urban search and rescue: from

Robocup to real world applications, 2004.

[BEFW97] J. Borenstein, H. Everett, L. Feng, and D. Wehe. Mobile Robot Positio-

ning: Sensors and Techniques. Journal of Robotic Systems, 14(4):231–249,

1997.

[BFDW03] F. Bourgault, T. Furukawa, and H.F. Durrant-Whyte. Coordinated De-

centralized Search for a Lost Target in a Bayesian World. In Proceedings

of IEEE/RSJ International Conference on Intelligent Robots and Systems,

2003.

[BGGT07] Jan Blumenthal, Ralf Grossmann, Frank Golatowski, and Dirk Timmer-

mann. Weighted Centroid Localization in Zigbee-based Sensor Networks.

In IEEE International Symposium on Intelligent Signal Processing, 2007.

[BHE00] N. Bulusu, J. Heidemann, and D. Estrin. GPS-less Low Cost Outdoor

Localization For Very Small Devices. IEEE Personal Communication

Magazine, 7(5):28–34, 2000.

[BMF+00] W. Burgard, M. Moors, D. Fox, R. Simmons, and S. Thrun. Collabo-

rative Multi-Robot Exploration. In Proceedings of IEEE International

Conference on Robotics and Automation, 2000.

[BP00] Paramvir Bahl and Venkata N. Padmanabhan. RADAR: An In-Building

RF-based User Location and Tracking System. In IEEE INFOCOM, 2000.

103

http://focus.ti.com/lit/an/swra095/swra095.pdf

http://focus.ti.com/lit/an/swra095/swra095.pdf

Bibliografia 104

[CDNDW01] S. Clark, G. Dissanayake, P. Newman, and H.F. Durrant-Whyte. A So-

lution to Simultaneous Localization and Map Building (SLAM) Problem.

IEEE Journal of Robotics and Automaton, 17(3), 2001.

[CFIN07] Daniele Calisi, Alessandro Farinelli, Luca Iocchi, and Daniele Nardi. Multi-

objective Exploration and Search for Autonomous Rescue Robots. J. Field

Robot., 24(8-9):763–777, 2007.

[Cro07] CrossBow Technology. Avoiding RF Interference Between WiFi and

ZigBee, 2007. http://www.xbow.com/Products/Product_pdf_files/

Wireless_pdf/ZigBeeandWiFiInterference.pdf.

[Doy95] Alexander Benjamin Doyle. Algorithms and Computational Techniques for

Robot Path Planning. PhD thesis, School of Electronic Engineering and

Computer Systems, University of Wales, Bangor, 1995.

[DR97] Gregory Dudek and Nicholas Roy. Multi-Robot Rendezvous in Unkno-

wn Environments. In Proceedings of AAAI International Conference on

Artificial Intelligence, 1997.

[DWB06a] H.F. Durant-White and T. Bailey. Simultaneous Localization and Map-

ping: Part I. IEEE Robotics and Automation Magazine, pages 99–108,

June 2006.

[DWB06b] H.F. Durant-White and T. Bailey. Simultaneous Localization and Map-

ping: Part II. IEEE Robotics and Automation Magazine, pages 108–117,

Semptember 2006.

[Erg04] Sinem Coleri Ergen. ZigBee/IEEE 802.15.4 Summary. Technical report,

Berkeley, September 2004.

[Eve95] H. R. Everett. Sensors for Mobile Robots. A. K. Peters, 1995.

[FBT99] D. Fox, W. Burgard, and S. Thrun. Markov Localization for Mobile Robots

in Dynamic Environments. Journal of Artificial Intelligence Research, 11,

1999.

[FGI05] A. Farinelli, G. Grisetti, and L. Iocchi. SPQR-RDK: a Modular Framework

for Programming Mobile Robots. In Proceedings of International RoboCup

Symposium 2004, pages 653–660, 2005.

[GBL01] H.H. Gonzales-Banos and J.C. Latombe. Navigation Strategies for Ex-

ploring Indoor Environments. International Journal of Robotics Research,

2001.

http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/ZigBeeandWiFiInterference.pdf

http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/ZigBeeandWiFiInterference.pdf

Bibliografia 105

[GVS+01] B.P. Gerkey, R.T. Vaughan, K. Støy, A. Howard, M.J. Matarie, and G.S.

Sukhatme. Most Valuable Player: A Robot Device Server for Distribu-

ted Control. In IEEE/RSJ Intl. Conf. on Intelligent Robots an Systems

(IROS), pages 1226–1231, October 2001.

[HBB+00] D. Hougen, S. Benjaafar, J. Bonney, J. Budenske, M. Dvorak, M. Gini,

H. French, D. Krantz, P. Li, F. Malver, B. Nelson, N. Papanikolopou-

los, P. Rybski, S. Stoeter, R. Voyles, and K. Yesin. A Miniature Robo-

tic System for Reconnaissance and Surveillance. In Proceedings of IEEE

International Conference on Robotics and Automation, pages 501–507,

2000.

[HHB+03] T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher. Range-free

Localization Schemes in Large Scale Sensor Networks, 2003.

[HLD07] J.B. Hayet, F. Lerasle, and M. Devy. A Visual Landmark Framework for

Mobile Robot Navigation. Image and Vision Computing, 25(8):1341–1351,

August 2007.

[HMS02] Andrew Howard, Maja J. Mataric, and Gaurav S. Sukhatme. An In-

cremental Self- Deployment Algorithm for Mobile Sensor Networks. In

Autonomous Robots, special issue on Intelligent Embedded Systems, 2002.

[HSI+99] Kitano H., Tadokoro S., Noda I., Matsubara H., Takahashi T., Shinjou

A., and Shimada S. RoboCup Rescue: Search and Rescue in Large-scale

Disasters as a Domain for Autonomous Agents Research. In Proceedings of

IEEE International Conference on Systems, Man and Cybernetics, 1999.

[IEE06] IEEE Standards 802 Part 15.4. Wireless Medium Access Control (MAC)

and Physical Layer (PHY) Specifications for Low-rate Wireless Perso-

nal Area Networks (WPANs), June 2006. http://standards.ieee.org/

getieee802/download/802.15.4-2003.pdf.

[IR01] ITU-R. Propagation Data and Prediction Methods for the Planning of

Indoor Radio Communication Systems and the Radio Local Area Networks

in the Frequency Range 900 MHz to 100 GHz, 2001.

[Kal60] R.E. Kalman. A New Approach to Linear Filtering and Prediction

Problems. Journal of Basic Engineering, 1960.

[KPN] Alexander Kleiner, Johann Prediger, and Bernhard Nebel. RFID

Technology-based Exploration and SLAM for Search and Rescue.

http://standards.ieee.org/getieee802/download/802.15.4-2003.pdf

http://standards.ieee.org/getieee802/download/802.15.4-2003.pdf

Bibliografia 106

[Lan03] Daniel Lang. A Comprehensive Overview About Selected Ad Hoc Net-

working Routing Protocols. http://home.leo.org/~dl/TUM-I0311.pdf,

2003.

[LW04] Konrad Lorincz and Matt Welsh. A Robust, Decentralized Approach

to RF-Based Location Tracking. Technical Report TR-04-04, Harvard

University, 2004.

[Mat92] Maja Mataric. Integration of Representation into Goal-driven Behavior-

based Robots. In IEEE Transactions on Robotics and Automation, 1992.

[MFA07] Guoqiang Mao, Barıs Fidan, and Brian D. O. Anderson. Wireless Sensor

Network Localization Techniques. Computer Networks, 51(10):2529–2553,

2007.

[MLLH06] Yongguo Mei, Yung-Hsiang Lu, C.S.G. Lee, and Y.C. Hu. Energy-efficient

Mobile Robot Exploration. In Proceedings of the International Conference

on Robotics and Automation, pages 505–511, 2006.

[MLM05] J. Minguez, F. Lamiraux, and L. Montesano. Metric-based Scan Matching

Algorithms for Mobile Robot Displacement Estimation. In Proceedings of

the IEEE International Conference on Robotics and Automation, 2005.

[MNG06] Y. Meng, J.V. Nickerson, and J. Gan. Multi-Robot Cooperation Strate-

gies in a Searching Task with Limited Communication. In Proceedings of

Robotic and Applications, 2006.

[MTK] Apurva Mudgal, Craig Tovey, and Sven Koenig. Analysis of Greedy Robot-

Navigation Methods.

[NA07] Rooker Martijn N. and Birk Andreas. Multi-robot Exploration under

the Constraints of Wireless Networking. Control Engineering Practice,

15(4):435–445, 2007.

[NN01] D. Niculescu and B. Nath. Ad Hoc Positioning System (APS). In

Proceedings of GLOBECOM, November 2001.

[NN03] D. Niculescu and B. Nath. Ad Hoc Positioning System (APS) using AOA.

In IEEE INFOCOM, 2003.

[Pat05] Neal Patwari. Location Estimation in Sensors Networks. PhD thesis,

University of Michigan, 2005.

[PD03] Larry L. Peterson and Bruce S. Davie. Computer Networks: A System

Approach. Morgan Kaufman, 2003.

http://home.leo.org/~dl/TUM-I0311.pdf

Bibliografia 107

[Per03] C. Perkins. Ad hoc On-Demand Distance Vector (AODV) Routing, July

2003. http://www.ietf.org/rfc/rfc3561.txt.

[PHP+03] N. Patwari, A. O. Hero, M. Perkins, N. S. Correal, and R. J. ODea. Lo-

cation Estimation in Wireless Sensor Networks. In IEEE Transactions on

Signal Processing, volume 51, August 2003.

[Rap01] Theodore Rappaport. Wireless Communications: Principles and Practice.

Prentice Hall PTR, Upper Saddle River, NJ, USA, 2001.

[RB05] Martijn N. Rooker and Andreas Birk. Combining Exploration and Ad-Hoc

Networking in RoboCup Rescue. In Nardi Daniele, Riedmiller Martin,

and Sammut Claude, editors, RoboCup 2004: Robot Soccer World Cup

VIII, volume 3276 of Lecture Notes in Artificial Intelligence (LNAI), pages

236–246. Springer, 2005.

[SACO06] Rajeev Shorey, Kkihebbal L. Ananda, Mun Choon Chan, and Wei Tsang

Ooi. Mobile, Wireless, and Sensor Networks - Technology, Applications,

and Future Directions. John Wiley & Sons, 2006.

[Sau00] Simon R. Saunders. Antennas and Propagation for Wireless

Communications Systems. John Wiley and Sons, 2000.

[SAY99] Alan C. Schultz, William Adams, and Brian Yamauchi. Integrating

Exploration, Localization, Navigation and Planning with a Common

Representation. Autonomous Robots, 6(3):293–308, 1999.

[SB03] C. Stachniss and W. Burgard. Exploring Unknown Environments with

Mobile Robots using Coverage Maps. In Proceedings of the International

Conference on Artificial Intelligence, 2003.

[Sem06] Freescale Semiconductors. Compact Integrated Antennas Designs and

Applications for the MC1319x, MC1320x, and MC1321x, 2006. http:

//www.freescale.com.

[Sem07a] Freescale Semiconductors. MC13211/212/213 ZigBee Compliant Platform

- 2.4 GHz Low Power Transceiver for the IEEE 802.15.4 Standard plus

Microcontroller, 2007. http://www.freescale.com.

[Sem07b] Freescale Semiconductors. MC1321x Evaluation Kit (EVK) - Reference

Manual, 2007. http://www.freescale.com.

[Sey00] John S. Seybold. Introduction to RF propagation. John Wiley and Sons,

2000.

http://www.ietf.org/rfc/rfc3561.txt

http://www.freescale.com




Bibliografia 108

[SHS01] A. Savvides, C. Han, and M. Srivastava. Dynamic Fine-grained Localiza-

tion in Ad-Hoc Networks of Sensors. In Proceedings of ACM MobiCom,

pages 166–179, July 2001.

[SKOM06] Masashi Sugano, Tomonori Kawazoe, Yoshikazu Ohta, and Masayuki Mu-

rata. Indoor Localization System Using RSSI Measurement of Wireless

Sensor Network Based on ZigBee Standard, 2006.

[SN04] Roland Siegwart and Illah R. Nourbakhsh. Introduction to Autonomous

Mobile Robots. MIT Press, 2004.

[SRZF07] Y. Shang, W. Ruml, Y. Zhang, and M. P. J. Fromherz. Localization from

Mere Connectivity. In Fourth ACM International Symposium on Mobile

Ad-Hoc Networking and Computing, June 2007.

[TBF05] S. Thrun, W. Burgard, and D. Fox. Probabilistic Robotics. MIT Press,

2005.

[TFB98] S. Thrun, D. Fox, and W. Burgard. A Probabilistic Approach to Con-

current Mapping and Localization for Mobile Robots. Machine Learning,

31:29–53, 1998.

[TFBD00] S. Thrun, D. Fox, W. Burgard, and F. Dellaert. Robust Monte Carlo

Localization for Mobile Robots. Artificial Intelligence, 128(1-2):99–141,

2000.

[Thr95] S. Thrun. Exploration in Active Learning, 1995.

[TK93] C.J. Tailor and D.J. Kriegman. Exloration Strategies for Mobile Robo-

ts. In Proceedings of the IEEE International Conference on Robotics and

Automation, pages 248–253, 1993.

[TK03] C. Tovey and S. Koenig. Improved Analysis of Greedy Mapping. In Procee-

dings of IEEE International Conference on Intelligent Robots and Systems,

pages 3251–3257, 2003.

[TKT+00] Satoshi Tadokoro, Hiroaki Kitano, Tomoichi, Takahashi, Itsuki Noda, Hi-

toshi Matsubara, Atsuhi Shinjoh, Tetsuya Koto, Ikuo Takeuchi, Hironao

Takahashi, Fumitoshi Matsuno, Mitsuo Hatayama, Jun Nobe, and Su-

sumu Shimada. The RoboCup-Rescue Project: A Robotic Approach to

the Disaster Mitigation Problem. In Proceedings of IEEE International

Conference on Robotics and Automation, 2000.

Bibliografia 109

[WLG03] J. Wang, M. Lewis, and J. Gennari. Interactive Simulation of the NIST

USAR Arenas. In IEEE International Conference on Systems, Man, and

Cybernetics, pages 1350–1354, 2003.

[XKC97] Yun Xiaoping and Tan Ko-Cheng. A Wall-following Method for Escaping

Local Minima in Potential Field Based Motion Planning. In Proceedings

of 8th International Conference on Advanced Robotics, 1997.

[Yam97] Brian Yamauchi. A Frontier-Based Approach for Autonomous Explora-

tion. In Proceedings of the IEEE International Conference on Robotics

and Automation, 1997.

[Yam98] Brian Yamauchi. Frontier-based exploration using multiple robots. In

AGENTS ’98: Proceedings of the second international conference on

Autonomous agents, pages 47–53, New York, NY, USA, 1998. ACM.

[YSA98] Brian Yamauchi, Alan Schultz, and Williams Adams. Mobile Robot Ex-

ploration and Map-Building with Continuous Localization. In Procee-

dings of the International Conference on Robotics and Automation, pages

3715–3720, 1998.

[Zig06] ZigBee Alliance. ZigBee-2006 Specification, December 2006. http://www.

zigbee.org/en/spec_download/zigbee_downloads.asp.

[ZKNN07] V.A. Ziparo, A. Kleiner, B. Nebel, and D. Nardi. RFID-Based Explora-

tion for Large Robot Teams. In Proceedings of the IEEE International

Conference on Robotics and Automation, pages 4606–4613, 2007.

[ZLV07] P. Zebrowski, Y. Litus, and R.T. Vaughan. Energy Efficient Robot Ren-

dezvous. In Fourth Canadian Conference on Computer and Robot Vision,

2007.

http://www.zigbee.org/en/spec_download/zigbee_downloads.asp

http://www.zigbee.org/en/spec_download/zigbee_downloads.asp

Questa tesi e stata scritta interamente utilizzando il software LATEX2e

A.Dionisi Thesis

Documents

Transcript of A.Dionisi Thesis