Universit`
a degli Studi di Pisa
DIPARTIMENTO DI INFORMATICA Corso di Laurea Magistrale in Informatica
Tesi di Laurea Magistrale in Informatica
Uso di un interpolatore spaziale in una
campagna di Mobile Crowd Sensing
Candidato:
Gaia Adami
Relatori:
Prof. Stefano Chessa Dr. Michele Girolami
Indice
Elenco delle gure iii
Elenco delle tabelle viii
1 Introduzione 1
1.1 Contenuto e organizzazione della tesi . . . 4
2 Stato dell'arte 5 2.1 Interpolazione nelle reti di sensori . . . 5
2.1.1 I principali metodi di interpolazione . . . 8
2.1.2 Migliorare la copertura nelle reti di sensori . . . 10
2.2 Interpolatori e MCS . . . 11 3 Strumenti e metodi 12 3.1 Il kriging . . . 12 3.1.1 De nizione . . . 12 3.1.2 Descrizione formale . . . 13 3.1.3 Semivariogrammi . . . 13 3.1.4 Tipi di kriging . . . 15 3.2 I dataset . . . 16 3.2.1 ParticipAct . . . 16 3.2.2 Weather Underground . . . 18
3.2.3 Formato dei dati . . . 18
3.3 L'ambiente MATLAB e il software QGIS . . . 20
4 Il problema della copertura nel MCS 21 4.1 De nizione del problema della copertura . . . 21
4.2 Modelli di copertura . . . 22
4.2.1 Modelli di copertura binari . . . 22
4.2.2 Modelli di copertura probabilistici . . . 23 i
INDICE ii
4.2.3 Modelli di copertura basati sull'evidenza . . . 24
4.3 Modelli di copertura temporali . . . 26
4.4 Introduzione degli interpolatori . . . 27
5 Organizzazione della sperimentazione 29 5.1 Preprocessing dei dati . . . 29
5.1.1 Il fetch dei dati da WU . . . 29
5.1.2 Utilizzo dei dati . . . 30
5.1.3 Allineamento temporale dei dati . . . 32
5.1.4 Combinazione delle stazioni sse e dei nodi mobili . . . . 37
5.2 Metodi per l'analisi dei risultati . . . 37
5.2.1 Cross-Validation e validazione con la ground truth . . . . 37
5.2.2 Altri metodi per l'analisi . . . 41
5.3 Con gurazione delle sperimentazioni . . . 42
5.3.1 La scelta del semivariogramma . . . 42
6 Analisi dei risultati 46 6.1 Confronto fra suddivisione statica e dinamica delle stazioni me-teorologiche . . . 46
6.1.1 Confronto con semivariogramma ssato . . . 46
6.1.2 Confronto con semivariogramma empirico . . . 49
6.2 Analisi delle tre strategie con suddivisione statica . . . 52
6.2.1 Strategia A . . . 52
6.2.2 Strategia B . . . 58
6.2.3 Strategia C . . . 63
6.2.4 Confronto della media delle varianze . . . 67
6.2.5 Studio del percentile . . . 70
6.2.6 Cross-Validation . . . 73
6.2.7 Validazione con la ground truth . . . 75
6.3 Analisi della strategia B con suddivisione dinamica . . . 84
6.3.1 Studio della media delle varianze . . . 88
6.3.2 Studio del percentile . . . 89
6.3.3 Cross-Validation . . . 92
7 Conclusioni 95
Elenco delle gure
1.1 Scenario urbano di MCS . . . 1 2.1 Tipi di griglia: (a) pattern triangolare (b) quadrato (c) esagonale 11 3.1 Esempio di modello lineare, gaussiano, esponenziale e sferico . . 14 3.2 Esempio di semivariogramma . . . 15 3.3 (a) Sensing region centrata sulla città di Bologna (b) Coordinate
dei nodi mobili a Bologna nei giorni 7-12/10/2014 . . . 17 3.4 Stazioni meteorologiche nel centro di Bologna . . . 18 4.1 Modello binario: (a) area di sensing di un sensore (b) gra co
della probabilità . . . 23 4.2 Misure di copertura in funzione della distanza fra il punto
con-siderato e un generico sensore, secondo i modelli binario, pro-babilistico e propro-babilistico troncato. . . 24 4.3 Rappresentazione dell'intervallo di sensing e dell'intervallo di
incertezza di un sensore . . . 25 5.1 Griglia creata sull'area della città di Bologna . . . 31 5.2 Le stazioni meteorologiche di Bologna suddivise staticamente
negli insiemi WUA (triangoli) e WUB (stelle) . . . 31
5.3 Le stazioni meteorologiche di Bologna, etichettate con il loro codice . . . 33 5.4 Le stazioni meteorologiche di Bologna suddivise dinamicamente
negli insiemi WUA (triangoli) e WUB (stelle) . . . 34
5.5 Esempio di Leave One Out Cross-Validation . . . 38 5.6 Esempio di k-Fold Cross-Validation, con k=3 . . . 39 5.7 Semivariogrammi calcolati alla stessa iterazione e con intervallo
temporale di 24 ore per: (a) strategia A (b) strategia B (c) strategia C . . . 44
ELENCO DELLE FIGURE iv 6.1 Mappe di calore dell'iterazione 1 con strategia B e
semivario-gramma ssato: (a) con suddivisione statica e (b) con suddivi-sione dinamica delle stazioni sse . . . 47 6.2 Mappe di calore dell'iterazione 6 con strategia B e
semivario-gramma ssato: (a) con suddivisione statica e (b) con suddivi-sione dinamica delle stazioni sse . . . 47 6.3 Mappe di calore dell'iterazione 21 con strategia B e
semivario-gramma ssato: (a) con suddivisione statica e (b) con suddivi-sione dinamica delle stazioni sse . . . 47 6.4 Mappe di calore dell'iterazione 1 con strategia A e
semivario-gramma ssato: (a) con suddivisione statica e (b) con suddivi-sione dinamica delle stazioni sse . . . 49 6.5 Mappe di calore dell'iterazione 1 con intervallo temporale di
24h, strategia B e semivariogramma ssato: (a) con suddivisione statica e (b) con suddivisione dinamica delle stazioni sse . . . . 50 6.6 Mappe di calore dell'iterazione 1 con strategia B e
semivario-gramma empirico: (a) con suddivisione statica e (b) con suddi-visione dinamica delle stazioni sse . . . 50 6.7 Mappe di calore dell'iterazione 6 con strategia B e
semivario-gramma empirico: (a) con suddivisione statica e (b) con suddi-visione dinamica delle stazioni sse . . . 50 6.8 Mappe di calore dell'iterazione 21 con strategia B e
semivario-gramma ssato: (a) con suddivisione statica e (b) con suddivi-sione dinamica delle stazioni sse . . . 51 6.9 Mappe di calore dell'iterazione 1 con intervallo temporale di 24h,
strategia B e semivariogramma empirico: (a) con suddivisione statica e (b) con suddivisione dinamica delle stazioni sse . . . . 51 6.10 Mappe di calore dell'iterazione 8 con strategia A, ∆=1h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 52 6.11 Mappe di calore dell'iterazione 20 con strategia A, ∆=1h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 53 6.12 Mappe di calore dell'iterazione 23 con strategia A, ∆=1h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 53
ELENCO DELLE FIGURE v 6.13 Semivariogrammi empirici per la strategia A, con ∆=1h e
suddi-visione statica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 55 6.14 Semivariogramma ssato con modello sferico, sill 2 gradi
centi-gradi e range 0.2 chilometri . . . 56 6.15 Mappe di calore dell'iterazione 3 con strategia A, ∆=24h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 57 6.16 Semivariogramma empirico per l'iterazione 3 con strategia A,
∆=24h e suddivisione statica . . . 57 6.17 Mappe di calore dell'iterazione 8 con strategia B, ∆=1h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 58 6.18 Mappe di calore dell'iterazione 20 con strategia B, ∆=1h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 58 6.19 Mappe di calore dell'iterazione 23 con strategia B, ∆=1h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 59 6.20 Semivariogrammi empirici per la strategia B, con ∆=1h e
suddi-visione statica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 60 6.21 Mappe di calore dell'iterazione 3 con strategia B, ∆=24h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 62 6.22 Semivariogramma empirico per l'iterazione 3 con strategia B,
∆=24h e suddivisione statica . . . 62 6.23 Mappe di calore dell'iterazione 8 con strategia C, ∆=1h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 64 6.24 Mappe di calore dell'iterazione 20 con strategia C, ∆=1h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 64 6.25 Mappe di calore dell'iterazione 23 con strategia C, ∆=1h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 64
ELENCO DELLE FIGURE vi 6.26 Semivariogrammi empirici per la strategia C, con ∆=1h e
suddi-visione statica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 65 6.27 Mappe di calore dell'iterazione 3 con strategia C, ∆=24h e
sud-divisione statica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 66 6.28 Semivariogramma empirico per l'iterazione 3 con strategia C,
∆=24h e suddivisione statica . . . 67 6.29 Surface plot della media delle varianze con ∆=1h, suddivisione
statica e semivariogramma ssato: (a) strategia A, (b) strategia B e (c) strategia C . . . 69 6.30 Surface plot della media delle varianze con ∆=1h,
suddivisio-ne statica e semivariogramma empirico: (a) strategia A, (b) strategia B e (c) strategia C . . . 71 6.31 Gra ci del 90-esimo percentile con ∆=1h, suddivisione statica e
semivariogramma ssato: (a) strategia A, (b) strategia B e (c) strategia C . . . 72 6.32 Gra ci del 90-esimo percentile con ∆=1h, suddivisione statica
e semivariogramma empirico: (a) strategia A, (b) strategia B e (c) strategia C . . . 74 6.33 Gra co dell'errore assoluto calcolato per la Cross-Validation con
strategia A, ∆=1h e suddivisione statica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 76 6.34 Gra co dell'errore assoluto calcolato per la Cross-Validation con
strategia B, ∆=1h e suddivisione statica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 77 6.35 Gra co dell'errore assoluto calcolato per la Cross-Validation con
strategia C, ∆=1h e suddivisione statica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 78 6.36 Gra ci dell'errore assoluto medio (MAE) calcolati per la
Cross-Validation con ∆=1h e suddivisione statica: (a) strategia A, (b) strategia B e (c) strategia C . . . 79 6.37 Gra co dell'errore assoluto calcolato per la validazione con la
ground truth con strategia A, ∆=1h e suddivisione statica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 81
ELENCO DELLE FIGURE vii 6.38 Gra co dell'errore assoluto calcolato per la validazione con la
ground truth con strategia C, ∆=1h e suddivisione statica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 82 6.39 Gra ci dell'errore assoluto medio (MAE) calcolati per la
Cross-Validation con ∆=1h e suddivisione statica: (a) strategia A e (b) strategia C . . . 83 6.40 Mappe di calore dell'iterazione 8 con strategia B, ∆=1h e
sud-divisione dinamica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 85 6.41 Mappe di calore dell'iterazione 20 con strategia B, ∆=1h e
sud-divisione dinamica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 85 6.42 Mappe di calore dell'iterazione 23 con strategia B, ∆=1h e
sud-divisione dinamica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 85 6.43 Semivariogrammi empirici per la strategia B, con ∆=1h e
sud-divisione dinamica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 87 6.44 Mappe di calore dell'iterazione 3 con strategia B, ∆=24h e
sud-divisione dinamica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 88 6.45 Semivariogramma empirico per l'iterazione 3 con strategia B,
∆=24h e suddivisione dinamica . . . 88 6.46 Surface plot della media delle varianze con strategia B, ∆=1h
e suddivisione dinamica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 90 6.47 Gra ci del 90-esimo percentile con strategia B, ∆=1h e
sud-divisione dinamica: (a) con semivariogramma ssato e (b) con semivariogramma empirico . . . 91 6.48 Gra co dell'errore assoluto calcolato per la Cross-Validation con
strategia B, ∆=1h e suddivisione dinamica: (a) iterazione 8, (b) iterazione 20 e (c) iterazione 23 . . . 93 6.49 Gra ci dell'errore assoluto medio (MAE) calcolati per la
Elenco delle tabelle
1.1 Alcune de nizioni di smart city . . . 2 5.1 Distanze utilizzate per la suddivisione dinamica . . . 33 5.2 Suddivisione dinamica delle stazioni nei due sottoinsiemi . . . . 34 5.3 Frammento di le della stazione IBOLOGNA40 . . . 36 5.4 Frammento di le della stazione IBOLOGNA50 . . . 36 5.5 Frammento di le della stazione IEMILIAR229 . . . 36 6.1 Valore massimo, minimo e medio per la varianza, in ◦C,
all'i-terazione 20 con strategia A, ∆=1h e suddivisione statica delle stazioni . . . 53 6.2 Valore massimo, minimo e medio per la varianza, in ◦C,
all'i-terazione 3 con strategia A, ∆=24h e suddivisione statica delle stazioni . . . 56 6.3 Dati rilevati dalle stazioni di WUB nelle iterazioni 8 (sopra) e
23 (sotto) . . . 61 6.4 Valore massimo, minimo e medio per la varianza, in ◦C,
all'i-terazione 20 con strategia B, ∆=1h e suddivisione statica delle stazioni . . . 61 6.5 Valore massimo, minimo e medio per la varianza, in ◦C,
all'i-terazione 3 con strategia B, ∆=24h e suddivisione statica delle stazioni . . . 63 6.6 Valore massimo, minimo e medio per la varianza, in ◦C,
all'i-terazione 20 con strategia C, ∆=1h e suddivisione statica delle stazioni . . . 65 6.7 Valore massimo, minimo e medio per la varianza, in ◦C,
all'i-terazione 3 con strategia C, ∆=24h e suddivisione statica delle stazioni . . . 67
ELENCO DELLE TABELLE ix 6.8 Valore massimo, minimo e medio per la media delle varianze,
in ◦C, per le tre strategie con ∆=1h, suddivisione statica delle
stazioni e semivariogramma ssato . . . 68 6.9 Valore massimo, minimo e medio per la media delle varianze,
in ◦C, per le tre strategie con ∆=1h, suddivisione statica delle
stazioni e semivariogramma empirico . . . 68 6.10 Valore massimo, minimo e medio per la varianza, in ◦C,
all'ite-razione 20 con strategia B, ∆=1h e suddivisione dinamica delle stazioni . . . 86 6.11 Valore massimo, minimo e medio per la varianza, in ◦C,
all'ite-razione 3 con strategia B, ∆=24h e suddivisione dinamica delle stazioni . . . 86 6.12 Valore massimo, minimo e medio per la media delle varianze, in
Capitolo 1
Introduzione
Il Mobile Crowd Sensing (MCS) è un paradigma emergente che sfrutta la diusione dei dispositivi mobili per raccogliere dati in modo e ciente, renden-do possibili numerose applicazioni. Il punto chiave è il coinvolgimento umano: si sfruttano i sensori presenti sui dispositivi trasportati quotidianamente dalle persone - quali smartphone e dispositivi indossabili - o sui veicoli per monito-rare fenomeni su larga scala.
La Figura 1.1 [1] illustra un esempio di scenario urbano di MCS: un gruppo
Figura 1.1: Scenario urbano di MCS
di utenti, equipaggiati con sensori mobili (giroscopio, microfono, . . . ) e moduli di comunicazione (Bluetooth, WiFi, . . . ) si muovono nella regione di interesse, raccolgono campioni e riportano i dati raccolti a un centro di monitoraggio per costruire una mappa delle rilevazioni (sensing map) di un certo fenomeno, su scala cittadina.
La crescente disponibilità di diversi tipi di sensori su dispositivi mobili, li ren-1
CAPITOLO 1. INTRODUZIONE 2 de una tecnologia abilitante per lo sviluppo delle cosiddette città intelligenti (smart city).
È di cile dare una de nizione unica di città intelligente, in quanto per ren-dere una città appunto `intelligente' si interviene su vari domini: l'ambiente, la qualità della vita, la piani cazione, la tecnologia e così via. La Tabella 1.1 riporta alcune de nizioni fra quelle proposte in letteratura, tradotte in lingua italiana, in modo da dare un'idea delle molte declinazioni che questo innovativo concetto può avere.
De nizione Fonte
`Essere una smart city signi ca usare tutte le tecnologie e le risorse disponibili in maniera coordinata e intelligente, per svi-luppare centri urbani che sono contemporaneamente integrati, abitabili e sostenibili.'1
[2]
`Una città che connette l'infrastruttura sica, l'infrastruttura IT, l'infrastruttura sociale e l'infrastruttura economica per
utilizzare a suo vantaggio l'intelligenza collettiva della città.'2 [3]
`[. . . ] le smart city trarranno vantaggio dalla comunicazione e dalle capacità dei sensori integrati nelle infrastrutture citta-dine per ottimizzare la rete elettrica, i trasporti e altre opera-zioni logistiche a supporto della vita quotidiana, migliorando quindi la qualità della vita per tutti.'3
[4]
`[. . . ] territori con un'alta capacità di apprendimento e in-novazione, che sono basati sulla creatività dei loro abitan-ti, le loro istituzioni di diusione della conoscenza e le loro infrastrutture digitali per la comunicazione'4
[5]
Tabella 1.1: Alcune de nizioni di smart city
1`Being a smart city means using all available technology and resources in an intelligent
and coordinated manner to develop urban centers that are at once integrated, habitable and sustainable.'
2`A city connecting the physical infrastructure, the IT infrastructure, the social
in-frastructure, and the business infrastructure to leverage the collective intelligence of the city.'
3`[. . . ] smart cities will take advantage of communications and sensor capabilities sewn
into the cities' infrastructures to optimize electrical, transportation, and other logistical operations supporting daily life, thereby improving the quality of life for everyone.'
4`[. . . ] territories with a high capacity for learning and innovation, which is built in to
CAPITOLO 1. INTRODUZIONE 3 Considerando quindi che in questi contesti è necessario un rilevamento di dati su larga scala, solitamente a grana ne, se si utilizzasse una rete di sen-sori `classici' bisognerebbe dislocare un gran numero di nodi per garantire la copertura dell'area. In termini economici, se aggiungiamo anche la manuten-zione dei nodi, questa solumanuten-zione risulta essere svantaggiosa rispetto a una rete formata da dispositivi mobili già esistenti.
Il coinvolgimento umano è però un'arma a doppio taglio: da una parte è più facile sviluppare una rete essibile con un'ampia copertura dell'area di interes-se a basso costo e i nodi sono mantenuti in buono stato dai loro proprietari, i quali si occupano anche della fornitura di corrente; dall'altra però possono sor-gere problemi legati alla privacy e il numero di dispositivi, la disponibilità dei sensori e la qualità dei dati rilevati cambiano in modo imprevedibile nel tempo.
Si possono distinguere due tipi di crowdsensing:
• partecipativo (partecipatory sensing): sono gli utenti stessi che decido-no cosa e quando rilevare e, di conseguenza, inviare per la raccolta dei dati
• opportunistico (opportunistic sensing): l'applicazione di rilevamento e raccolta dei dati viene eseguita in background, senza il coinvolgimento attivo degli utenti.
La gestione di un processo di MCS è un compito impegnativo, che spazia fra diverse questioni tecniche - quali la caratterizzazione della regione da mo-nitorare, la quanti cazione della densità di sensori necessaria per ottenere una determinata accuratezza, la valutazione di un buon equilibrio fra accuratezza e utilizzo delle risorse, . . . - e sociali - quali la selezione di incentivi per la par-tecipazione attiva degli utenti, il numero di persone coinvolte, . . . [6].
Un problema che deriva direttamente dal coinvolgimento degli utenti è che la topologia di reti di questo tipo non può essere predeterminata, ma cambia frequentemente in base agli spostamenti degli utenti stessi. Tuttavia, sono stati condotti alcuni studi ([1]) sull'analisi dei dati GPS di un campione di pedoni, i quali hanno dimostrato che:
• le persone tendono a muoversi in un insieme di luoghi popolari (public hotspot), non compiendo movimenti casuali
CAPITOLO 1. INTRODUZIONE 4 • ogni persona mostra preferenza per alcuni luoghi in particolare (personal
hotspot).
Questo problema e il fatto che, per quanto appena visto, di cilmente l'area di interesse potrebbe essere coperta dai soli nodi mobili sono due dei motivi per cui si è pensato di studiare piattaforme di MCS ibride, ovvero piattaforme che combinano nodi statici e mobili.
Un altro motivo è che, nonostante i sensori tradizionali abbiano un costo più elevato e una scalabilità peggiore, hanno in generale una qualità di rilevamento dei dati più a dabile, che può essere usata per compensare situazioni inade-guate che si possono presentare in un sistema composto solamente da nodi mobili.
1.1 Contenuto e organizzazione della tesi
Nel presente lavoro vengono messe a confronto le prestazioni di una rete di sensori classici, una di MCS `puro' e una di MCS ibrido. I dati studiati riguardano la temperatura ambientale e vengono interpolati in modo da avere una copertura spaziale e temporale completa dell'area di interesse che, nel caso di studio trattato nella tesi, comprende il centro della città di Bologna..
La struttura della tesi è la seguente. Nel Capitolo 2 verrà presentato lo stato dell'arte per quanto riguarda i metodi di interpolazione e il loro utilizzo nelle reti di sensori e nel Mobile Crowd Sensing. Il Capitolo 3 sarà dedicato alla presentazione degli strumenti e delle metodologie utilizzati per lo sviluppo del lavoro, a partire da una descrizione teorica del metodo del kriging no ad arrivare ai dataset utilizzati per le sperimentazioni e all'ambiente di sviluppo dell'applicazione.
Nel Capitolo 4 verrà presentato il problema della copertura e verranno discussi alcuni approcci al problema proposti in letteratura. Verrà inoltre discussa l'introduzione degli interpolatori in questo contesto.
I Capitoli 5 e 6 saranno dedicati alle sperimentazioni eettuate: nel Capitolo 5 verranno descritti l'utilizzo dei dati e i metodi per l'analisi delle prestazioni, le quali verranno poi discusse nel Capitolo 6.
Capitolo 2
Stato dell'arte
Le reti per il Mobile Crowd Sensing e le reti di sensori wireless (Wireless Sensor Network, WSN) hanno nalità simili: entrambi sono infatti costituite da dispositivi che eettuano la raccolta di dati in una regione di interesse, tramite i sensori con cui sono equipaggiati. Ai ni di questa tesi si è potuto, grazie a questa a nità, considerare reti ibride per studiare la copertura. La dierenza sostanziale fra i due tipi di rete è che nelle reti di sensori l'ar-chitettura - quindi la posizione dei nodi - è nota a priori, mentre nel MCS entra in gioco la mobilità dei dispositivi. Questa mobilità, come approfondito nel Capitolo 1, è una caratteristica intrinseca delle reti per il Mobile Crowd Sensing e sulla quale non si ha controllo, in quanto è dovuta agli spostamenti eettuati dai proprietari dei dispositivi.
Per questo motivo, in questo Capitolo verrà inizialmente trattata l'interpo-lazione nelle reti di sensori (Sezione 2.1), includendo una rassegna delle prin-cipali techiche e un'introduzione al problema della copertura, per passare poi a descrivere il corrente utilizzo dell'interpolazione nel Mobile Crowd Sensing (Sezione 2.2).
2.1 Interpolazione nelle reti di sensori
Le reti di sensori wireless rappresentano un'area di ricerca in rapida cre-scita ed in costante evoluzione, grazie alla loro utilità in un ampio spettro di applicazioni.
Con il termine WSN si indica una determinata tipologia di rete caratterizzata da un'architettura distribuita. Ogni nodo della rete è un dispositivo elettroni-co autonomo in grado di prelevare dati dall'ambiente cirelettroni-costante tramite uno
CAPITOLO 2. STATO DELL'ARTE 6 o più sensori con cui è equipaggiato (di temperatura, pressione, luminosità, . . . ). I nodi sono interconnessi e comunicano tra loro allo scopo di condividere ed elaborare i dati acquisiti.
Spesso non è possibile realizzare una WSN con nodi così densi da poter avere un sensore in ogni punto per cui si vuole avere a disposizione un valore, ad esempio a causa del costo che questo comporterebbe. Può accadere inoltre che manchi un numero, potenzialmente elevato, di osservazioni a causa di fallimento dei dispositivi, di operazioni di manutenzione, di errori umani o altri fattori.
Nelle applicazioni di WSN, dati incompleti possono portare a risultati diversi rispetto a quelli che si sarebbero ottenuti con un dataset completo. I tre problemi principali a cui questo conduce sono [7]:
• la perdita di e cienza come conseguenza della perdita di informazioni • complicazioni relative alla gestione, computazione e analisi dei dati, a
causa della loro irregolarità
• i risultati possono essere aetti da errore sistematico
Per questo motivo, serve un meccanismo tramite cui poter individuare valori in punti in cui non si ha un dato rilevato disponibile. L'interpolazione è una tecnica matematica che permette di stimare il valore di una funzione a partire da valori noti di essa e viene utilizzata come strumento per risolvere i problemi introdotti precedentemente.
Si possono distinguere due tipi di interpolazione [8]:
• temporale: approssima il valore di un determinato punto dello spazio in un istante di tempo, anche se il sensore non ha una misura rilevata in quell'istante di tempo. Questo richiede che sia eettivamente presente un sensore in quel punto e che esistano almeno una sua lettura precedente e una successiva all'istante di tempo considerato
• spaziale: permette di fornire stime in punti in cui non è sicamente presente un sensore, dato il fatto che siano noti dei valori intorno a questi punti.
Nelle reti di sensori wireless, si utilizza l'interpolazione spaziale per dare l'im-pressione di avere una dislocazione regolare dei nodi.
CAPITOLO 2. STATO DELL'ARTE 7 Per caratterizzare il concetto di interpolazione in una WSN, consideriamo la seguente equazione generica [8]:
Z∗(s0) = N P i=1 d(s0, si)Z(si) N P i=1 d(s0, si) (2.1) in cui Z∗(s
0) è il valore calcolato nel punto da interpolare, d(s0, si) è la
di-stanza fra il sensore i e il punto da interpolare, Z(si) è il valore percepito
dal sensore i e N è il numero di nodi della rete. Un procedimento che utiliz-za equazioni come la 2.1 viene chiamato algoritmo di media pesata (Weighted Average Algorithm). Dalla precedente formula si può osservare che più lontano è un sensore dal punto interpolato, meno impatto esso avrà sul valore calcolato.
Sono stati proposti molti metodi di interpolazione in letteratura. Un primo modo di classi carli è suddividerli in:
• tecniche deterministiche: il legame fra punti vicini è espresso da una leggere matematica deterministica, i cui parametri possono assumere in un dato istante uno e un solo valore
• tecniche stocastiche: il legame fra punti vicini è espresso tramite le loro proprietà statistiche, ad esempio la covarianza.
Un'altra classi cazione dei metodi può essere fatta sulla base dei dati utilizzati per costruire il modello. L'interpolazione può infatti essere eettuata:
• a livello globale: si considerano le informazioni disponibili per tutto lo spazio
• a livello locale: si considerano solo le informazioni dei punti vicini a quello da stimare.
La scelta del metodo da usare è di solito un trade-o fra prestazioni del mo-dello in termini di accuratezza delle previsioni e la sua complessità, sia di interpretazione che computazionale [9].
Per quanto riguarda in particolare i dati di stazioni climatiche, il miglior me-todo di interpolazione per una determinata applicazione varia come funzione dell'area e della scala spaziale desiderata per la mappatura [10]. È importante considerare anche la durata temporale e la natura della variabile climatica da interpolare. Sia la scelta del metodo che l'accuratezza dei risultati possono
CAPITOLO 2. STATO DELL'ARTE 8 inoltre essere in uenzati da parametri riguardanti le stazioni, quali l'altitudi-ne, la distanza dalla costa e la loro densità [11].
Metodi di interpolazione comunemente usati per la stima di variabili cli-matiche includono varie forme di metodi della distanza ponderata (distance weighting, [12, 13, 14]), regressione multipla e polinomiale ([15, 16]), kriging nelle sue varie declinazioni ([17, 12, 18]), spline ([13, 19]) e reti neurali (NN, [20]).
2.1.1 I principali metodi di interpolazione
Di seguito, una breve descrizione dei principali metodi utilizzati per l'in-terpolazione spaziale di dati climatici.
Distanza inversa ponderata
Il metodo della distanza inversa ponderata (Inverse Distance Weighting, IDW) è una tecnica deterministica di interpolazione locale. Il valore in un punto di interesse è determinato tramite combinazione lineare dei valori rilevati in punti vicini. I pesi utilizzati per il calcolo dipendono solo dalla distanza geometrica fra i campioni e il punto da stimare e il modo in cui i campioni sono distribuiti non in uenza i pesi.
La formula generica per IDW può essere così espressa: Z∗(s0) =
N
X
i=1
λiZ(si) (2.2)
in cui s0 è il punto da valutare, si sono gli N punti campione e λi sono i pesi
della combinazione lineare, i quali sono così de niti: λi =
1 d(s0, si)p
, p >0 (2.3)
Di solito si fa l'assunzione che l'in uenza di un punto campione sul punto per cui fornire un valore diminuisca con il quadrato della loro distanza, ovvero si pone p = 2 nell'equazione 2.3.
È un metodo molto utilizzato perché facile da applicare e perché produce buoni risultati.
CAPITOLO 2. STATO DELL'ARTE 9 Distanza angolare ponderata
La distanza angolare ponderata (Angular Distance Weighting, ADW) è una famiglia di tecniche comunemente usate per l'interpolazione di una rete irrego-lare di osservazioni meteorologiche mensili e giornaliere in una griglia regoirrego-lare di valori [21].
Tutte le varianti di ADW hanno in comune la stima del valore in un deter-minato punto come media ponderata dei valori osservati nelle stazioni vicine. A dierenza dell'approccio di IDW, i pesi individuali di ogni stazione sono una funzione dell'inverso della distanza rispetto al punto da stimare e della distanza angolare dalle altre stazioni.
Spline
L'interpolazione polinomiale, come abbiamo potuto vedere no a ora, uti-lizza un unico polinomio per l'approssimazione della funzione su tutta l'area considerata. Gli interpolatori della famiglia spline suddividono invece l'area in regioni e usano per ognuna di essi un polinomio diverso, di solito di grado piccolo. Si impone che due regioni continue garantiscano la continuità della funzione interpolata.
Questo tipo di interpolazione funziona bene su super ci con variabilità debole, ad esempio per la stima di temperature o di concentrazione di agenti inqui-nanti, ma non con variabili caratterizzate da repentini cambiamenti di valore nello spazio.
Il risultato è più realistico e più `smussato' rispetto a quello calcolato da IDW o da altri metodi simili.
Kriging
Il kriging è un metodo di interpolazione sviluppato negli Anni '50 da Danie G. Krige per stimare la distribuzione di risorse minerarie nel sottosuolo basan-dosi su un numero limitato di trivellazioni campione [17].
Nonostante sia stato sviluppato originariamente per dataset di dimensioni ab-bastanza grandi, il confronto con altri metodi di interpolazione mostra che il kriging può essere applicato con successo anche ad applicazioni su WSN che utilizzano un numero più basso di misurazioni [22].
Diversi studi, fra cui [9, 11], hanno infatti confrontato sullo stesso insieme di rilevazioni le prestazioni del kriging, nelle sue varie declinazioni, con quelle di altri metodi per l'interpolazione di dati climatici e ambientali, dimostrando
CAPITOLO 2. STATO DELL'ARTE 10 che il kriging è uno dei migliori metodi di interpolazione per dati di questo tipo. Il kriging può essere considerato una versione migliorata di IDW: infatti a dierenza di quest'ultimo, che calcola i coe cienti utilizzando in modo diretto la distanza fra due punti, il kriging lo fa tramite l'uso di un semivariogramma, il quale esprime la dipendeza statistica di due punti come funzione della loro distanza.
Questi concetti verranno approfonditi dettagliatamente nel Capitolo 3.
2.1.2 Migliorare la copertura nelle reti di sensori
Come descritto nei paragra precedenti, lo scopo delle reti di sensori è raccogliere dati dall'ambiente circostante in una regione di interesse.
Ogni sensore con cui è equipaggiato un nodo di una WSN è caratterizzato da un raggio massimo di rilevamento (sensing range). L'unione dei raggi di rilevamento di tutti i sensori è de nito come copertura della rete (network sensing coverage) e ri ette quanto bene l'area di interesse viene monitorata.
L'obiettivo è far sì che ogni punto dell'area di interesse sia incluso nella sensing region di almeno uno dei sensori. Il problema della copertura verrà approfondito nel Capitolo 4.
Da quanto introdotto si evince che la copertura di un'area è in uenzata dalla dislocazione dei sensori nella stessa. Ci sono varie strategie per disporre i nodi della rete, che si possono classi care in [23]:
• dislocazione deterministica: i nodi sono disposti in modo regolare nello spazio; si utilizza in ambienti ben accessibili e controllabili
• dislocazione randomica: i nodi sono distribuiti stocasticamente e in modo indipendente gli uni dagli altri; si utilizza principalmente in zone non accessibili o pericolose.
Il risultato della dislocazione deterministica è una topologia reticolare la qua-le, in generaqua-le, permette di ottenere una copertura maggiore della regione di interesse rispetto a quella che si avrebbe con la dislocazione randomica. Pattern comunemente utilizzati per formare i reticoli includono il triangolo (Figura 2.1(a)), il quadrato (Figura 2.1(b)) e l'esagono (Figura 2.1(c)). Fra questi il migliore risulta essere il triangolo, in quanto ha la minore area di sovrapposizione fra sensing range dei sensori e permette quindi di ridurre al
CAPITOLO 2. STATO DELL'ARTE 11 minimo il numero dei dispositivi necessari per la copertura della regione di interesse.
(a)
(b)
(c)
Figura 2.1: Tipi di griglia: (a) pattern triangolare (b) quadrato (c) esagonale
2.2 Interpolatori e MCS
Questa tesi pone le sue basi su un lavoro precedente, descritto in [24]. Risulta che quella sia la prima volta in cui vengono studiati gli eetti e i bene ci dell'interpolazione per l'estensione della copertura spaziale di una rete di Mobile Crowd Sensing che include dispositivi sia ssi che mobili.
Capitolo 3
Strumenti e metodi
Il metodo di interpolazione scelto per lo sviluppo del presente lavoro è il kriging ordinario. Nella Sezione 3.1 verranno descritti formalmente i vari tipi di kriging e verrà introdotto il concetto di semivariogramma.
Successivamente, nella Sezione 3.2, saranno presentati i dataset utilizzati per le sperimentazioni ovvero ParticiPact per quanto riguarda le coordinate GPS e i dati estratti da Weather Underground per quanto riguarda invece le infor-mazioni sulla temperatura.
Per concludere, nella Sezione 3.3 verrà introdotto brevemente l'ambiente uti-lizzato per lo sviluppo dell'applicazione.
3.1 Il kriging
3.1.1 De nizione
Il kriging è una famiglia di metodi di interpolazione usati nell'analisi spa-ziale (geostatistica) che permettono, conoscendo il valore di una grandezza in alcuni punti dello spazio, di determinare il valore della stessa in punti per cui non si hanno campioni. Per fare questo, si calcola una somma pesata dei valori misurati assumendo la presenza di una correlazione spaziale fra di essi (auto-correlazione): questo signi ca che, per stimare i punti non campionati, viene assegnato un peso maggiore ai valori noti più vicini e un peso minore a quelli più lontani.
Una caratteristica interessante del kriging è che, oltre a fornire i valori in-terpolati, calcola anche una stima dell'errore in ogni punto, dando una misura
CAPITOLO 3. STRUMENTI E METODI 13 dell'a dabilità del modello.
Per gli algoritmi di interpolazione, e quindi anche per il kriging, si può asserire che [25]:
• se i campioni sono abbastanza densi e uniformemente distribuiti nell'area di interesse, si ottieme una buona stima dei punti non campionati • se i campioni sono pochi o raggruppati in alcuni cluster, con grandi
spazi vuoti fra di loro, si ottiene una stima non a dabile dei punti non campionati.
Questo aspetto sarà approfondito nel Capitolo 6.
3.1.2 Descrizione formale
Supponiamo che l'area di interesse, che chiameremo anche sensing region (SR), sia un quadrato di lato L e supponiamo di dividerla in k2 caselle
qua-drate di lato L/k, ognuna denotata con qx,y per 0 ≤ x, y ≤ k.
Indichiamo con Z(qx,y)il valore misurato in qx,y: il nostro scopo è assegnare un
valore Z∗(q
x,y) a ognuna delle caselle della sensing region (in particolare, a
li-vello teorico, varrà Z∗(q
x,y) = Z(qx,y)nelle caselle per cui ho una misurazione).
La formula generale dell'interpolatore sarà allora: Z∗(qx,y) =
k
X
x,y=1
λx,yZ(qx,y)
in cui i λx,y rappresentano i pesi. Il signi cato pratico dell'autocorrelazione è
che, date due sottoaree qx,y e qx+∆,y+∆, i valori Z(qx,y) e Z(qx+∆,y+∆) sono in
relazione e più le sottoaree sono vicine, più i valori sono correlati.
Abbiamo detto che il kriging fornisce anche una stima dell'errore in ogni punto. Per la casella qi,j questo si può esprimere come x,y =| Z(qx,y) − Z∗(qx,y) |[24].
3.1.3 Semivariogrammi
Per ri ettere meglio la complessità dei fenomeni naturali, i pesi usati nel-l'interpolazione, anzichè essere determinati in modo arbitrario, ri ettono la struttura de nita dalla funzione di un semivariogramma.
Un semivariogramma è una tecnica di analisi statistica utilizzata per valuta-re l'autocorvaluta-relazione spaziale dei dati osservati: questo signi ca che vengono
CAPITOLO 3. STRUMENTI E METODI 14 messi in relazione la distanza fra due punti e il valore della semivarianza fra le misure eettuate in questi due punti. La semivarianza è data dalla dierenza media elevata al quadrato fra le misure eettuate in punti separati da distanza h (lag), ovvero:
γ(h) = 1 2N (h)
X
x,y,x0,y0| dist(qx,y,qx0,y0)=h
(Z(qx,y) − Z(qx0,y0))2
con N(h) numero di coppie di punti a distanza euclidea h1. Nella pratica, h è
accompagnata da un valore di tolleranza, dipendente dalla densità dei punti, in modo da creare degli intervalli di lag su cui calcolare la semivarianza [26]. A partire da questa formula, variando h, si crea un gra co di punti che ha le di-stanze sull'asse delle ascisse e i valori della semivarianza sull'asse delle ordinate. Al semivariogramma così calcolato (anche detto sperimentale), che sarà quindi discreto, bisogna adattare un modello, in modo da descrivere la con-tinuità spaziale dei dati. Esistono vari tipi di modelli per l'approssimazione di semivariogrammi che descrivono fenomeni sici. I più usati sono il modello lineare, gaussiano, esponenziale e sferico (vedi Figura 3.1 [27]).
Figura 3.1: Esempio di modello lineare, gaussiano, esponenziale e sferico La Figura 3.2 [28] rappresenta un semivariogramma sperimentale (i qua-drati di colore rosso) e il relativo modello che lo approssima (la linea di colore nero).
La gura mostra anche tre parametri che si possono derivare dal modello:
1Si dice distanza euclidea fra due punti in due dimensioni la misura del segmento
avente come estremi i due punti. Ovvero, dati P (px, py)e Q(qx, qy), la distanza euclidea fra
CAPITOLO 3. STRUMENTI E METODI 15 • range: la distanza oltre la quale il gra co si stabilizza; il signi cato sico di questo parametro è che punti a distanza maggiore del range non sono correlati fra loro
• sill: il valore su cui si stabilizza la semivarianza, ovvero la massima variabilità fra coppie di punti
• nugget: il punto di intersezione del gra co con l'asse y; rappresenta la variabilità dei dati su piccola scala, che può essere in parte determinata da errori di misurazione.
Figura 3.2: Esempio di semivariogramma
Il semivariogramma della Figura 3.2, in particolare, mostra una relazione spaziale che come abbiamo visto nella Sezione 3.1.1 si adatta bene all'analisi geostatistica, poichè le coppie di punti hanno una correlazione maggiore su piccole distanze e diventano meno correlati via via che la distanza aumenta.
3.1.4 Tipi di kriging
Fanno parte di questa famiglia di metodi:
• kriging ordinario (ordinary): è molto a dabile e raccomandato per la maggior parte dei dataset; assume una media costante, anche se non nota, dei valori
CAPITOLO 3. STRUMENTI E METODI 16 • kriging semplice (simple): assume che il dataset considerato abbia varianza stazionaria e valor medio noto e stazionario; matematicamente è il modello più semplice, ma anche quello meno generale
• kriging universale (universal): si usa quando i dati presentano un forte trend (ovvero una tendenza che caratterizza l'andamento del fenomeno nel tempo) modellabile con una funzione polinomiale.
La scelta di quale tipo di kriging usare dipende dalle caratteristiche dei dati e dal tipo di modello desiderato.
Lo scopo del presente studio è aumentare la copertura di un sistema di MCS nella sensing region considerata. Per farlo si è scelto di utilizzare il kriging ordinario, combinando i valori misurati dai nodi ssi e dai nodi mobili in un intervallo di tempo prede nito.
3.2 I dataset
Per simulare applicazioni di Mobile Crowd Sensing è necessaria la disponi-bilità di set di dati su larga scala. Per questo studio sono stati utilizzati due set: uno relativo alle coordinate GPS di dispositivi mobili e uno contenente valori sensoriali.
Per quanto riguarda le coordinate GPS, negli ultimi anni sono stati proposti diversi dataset contenenti dati di questo tipo. In particolare, questo lavoro è stato sviluppato usando ParticipAct. Poiché questo non comprende letture di sensori, è stato necessario combinarlo con le informazioni recuperate dal sito web Weather Underground.
Questo scenario non è comunque lontano dalla realtà, considerando che le spe-rimentazioni sono state fatte sulla temperatura ambientale: smartphone e altri dispositivi, infatti, non ottengono le informazioni su di essa direttamente dai loro sensori, ma appoggiandosi a servizi web.
3.2.1 ParticipAct
Il dataset ParticipAct [29] nasce da uno studio dell'Università di Bologna. La raccolta dei dati è iniziata nel Dicembre 2013 e sta ancora avendo luogo. Vengono monitorate le posizioni degli studenti dell'Ateneo a Bologna e Cesena, ovvero le sedi principali dell'Ateneo stesso, e nei loro spostamenti da e verso queste città. I dati vengono raccolti ogni 150 secondi e comprendono, oltre alle
CAPITOLO 3. STRUMENTI E METODI 17 coordinate GPS, anche dati dell'accelerometro, della fotocamera e così via.
Come la maggior parte delle piattaforme di MCS, anche ParticipAct ha un'architettura client-server. Gli utenti hanno il controllo sulle informazioni da inviare al server e decidono quando avviare e quando fermare l'attività di registrazione da parte dei sensori (si parla di sensing partecipativo2).
Come nel caso precedente, sono stati ristretti i dati considerati sia nel tempo che nello spazio, infatti ci si è concentrati sugli spostamenti nel centro della città di Bologna limitatamente ai giorni dal 7 al 12 Ottobre 2014 (Figura 3.3).
(a)
(b)
Figura 3.3: (a) Sensing region centrata sulla città di Bologna (b) Coordinate dei nodi mobili a Bologna nei giorni 7-12/10/2014
2Il caso opposto, ovvero quello in cui gli utenti non hanno controllo sui dati da inviare,
CAPITOLO 3. STRUMENTI E METODI 18
3.2.2 Weather Underground
Non essendo disponibile un vero e proprio dataset per quanto riguarda le informazioni relative ai dati ambientali nelle zone studiate, ne è stato crea-to uno con i valori recuperati da Weather Underground (WU) [30], un sicrea-to internet che fornisce informazioni real-time raccolte da una rete di stazioni meteorologiche dislocate in molte città di tutto il mondo.
Fra le varie informazioni fornite da questo servizio, la scelta è ricaduta sulla temperatura, in quanto misurare la temperatura è un esempio signi cativo di un possibile fenomeno da monitorare in un sistema di MCS.
Per quanto riguarda lo sviluppo di questo lavoro, sono state considerate le 19 stazioni presenti nel centro della città di Bologna (Figura 3.4).
I dati che abbiamo a disposizione sono relativi ai giorni fra il 4 e il 9 Novembre 2016.
Figura 3.4: Stazioni meteorologiche nel centro di Bologna
3.2.3 Formato dei dati
Formato dei dati di ParticipAct
• ID: numero univoco per identi care ogni dispositivo
• timestamp: data e ora della lettura, espresse in formato ISO 86013 con fuso orario UTC
3Nel formato ISO 8601 data e ora vengono rappresentate con 4 cifre per l'anno e due
per il mese, il giorno, l'ora, i minuti e i secondi, cioè aaaa-mm-gg oo:mm:ss. Un esempio è 2014-10-07 00:02:29.
CAPITOLO 3. STRUMENTI E METODI 19 • accuratezza: indica il raggio di accuratezza della localizzazione del nodo (espressa in metri); valori elevati sono dovuti al fatto che la locazione del dispositivo è approssimata con la posizione della cella GSM a cui esso è connesso
• latitudine • longitudine.
Formato dei dati di Weather Underground
Per ogni stazione meteorologica viene creato un le contenente una serie di record contenente i campi descritti nell'elenco seguente.
Da notare che alcuni di questi dati assumono valori, e in particolare valori signi- cativi, solo per alcuni tipi di software delle stazioni, mentre altri possono non essere disponibili per alcune stazioni in determinati momenti, indipendente-mente dal software. Inoltre, il numero di record in ogni le non è stabile, né pre-vedibile: si possono avere dispositivi che rilevano valori approssimativamente ogni 10 minuti e dispositivi che
• timestamp: data e ora della lettura, espresse in formato ISO 8601 e con fuso orario sia UTC che locale (UTC+1)
• tipo di software della stazione meteorologica • temperatura (in gradi Celsius)
• punto di rugiada: temperatura alla quale l'aria condensa in rugiada (in gradi Celsius)
• pressione atmosferica (in ettopascal)
• direzione del vento: come punto cardinale e in gradi [dati quasi sempre non signi cativi]
• velocità del vento: istantanea e massima in un intervallo di tempo (in chilometri orari) [dati quasi sempre non signi cativi]
• precipitazioni: orarie e giornaliere (in millimetri) [dati quasi sempre non signi cativi]
• irraggiamento solare (in watt al metro quadro) [dati raramente dispo-nibili]
CAPITOLO 3. STRUMENTI E METODI 20 • latitudine
• longitudine.
3.3 L'ambiente MATLAB e il software QGIS
Per la stesura del codice è stato usato l'ambiente di sviluppo MATLAB, che consente una facile manipolazione, analisi statistica e visualizzazione gra ca dei dati.
In particolare è stata usata mGstat, l'interfaccia per MATLAB di GSTAT, un package open source per la modellazione di dati geostatistici, che fornisce fra le varie cose anche le funzioni per il calcolo del kriging.
La visualizzazione gra ca di alcuni risultati è stata prodotta con QGIS, un sistema informativo computerizzato (in inglese Geographic Information Sy-stem, GIS). QGIS permette di processare i dati risultanti dal kriging grazie alla creazione di una mappa con vari layer, uno per ogni dato che si vuole analizzare o utilizzare per l'analisi.
In particolare, questo software è stato utilizzato per produrre la mappe di calore con i dati della varianza calcolati dal kriging.
Capitolo 4
Il problema della copertura nel
MCS
Uno dei problemi fondamentali nello studio sia delle reti di sensori che delle reti di Mobile Crowd Sensing è il cosiddetto problema della copertura. Questo può essere formulato come un problema decisionale, il cui obiettivo è deter-minare se ogni punto della sensing region è coperto da almeno k sensori (di solito, k = 1) [31]. Nel caso del MCS ibrido si considerano ovviamente sia i sensori ssi che quelli mobili.
In questo capitolo verranno descritti i modelli di copertura, spaziali e tem-porali, più comuni proposti in letteratura. Come illustrato nelle Sezioni 4.1, 4.2 e 4.3, la copertura di un'area è limitata superiormente in funzione della sua grandezza e del numeri di dispositivi che vi sono dislocati. Per questo motivo, nella Sezione 4.4, viene introdotto l'utilizzo dell'interpolazione come soluzione al problema della copertura.
4.1 De nizione del problema della copertura
Si assume per semplicità che la SR sia un'area quadrata di lato L monitora-ta da un insieme M di m dispositivi mobili e da un insieme N di n dispositivi ssi. Si indica con di, i ∈[1, n + m] un dispositivo qualsiasi fra questi. Ognuno
dei sensori presi in considerazione è caratterizzato da un raggio massimo di rilevamento ri (sensing range), ovvero può monitorare un'area entro una
di-stanza ri da esso.
CAPITOLO 4. IL PROBLEMA DELLA COPERTURA NEL MCS 22 Nella formulazione più immediata del problema, si può dire che un punto p è `coperto' da un sensore di se e solo se la distanza euclidea fra i due non
eccede il raggio di rilevamento dei sensore, ri, ovvero:
dist(di, p) ≤ ri (4.1)
con dist(di, p)la suddetta distanza euclidea.
Allo stesso modo, generalizzando, si può dire che un punto p è `j -coperto' se è incluso nel sensing range di j sensori.
4.2 Modelli di copertura
Da un punto dei vista matematico, un modello di copertura è una funzione che ha come input parametri quali la distanza (o gli angoli) fra i sensori e un punto dello spazio e come output una misura della bontà del monitoraggio della regione di interesse.
I modelli si possono classi care in vari modi. Uno di questi è dividerli in [32]: • modelli di copertura binari (binary coverage models)
• modelli di copertura probabilistici (probabilistic coverage models)
• modelli di copertura basati sull'evidenza (evidence-based coverage mo-dels).
4.2.1 Modelli di copertura binari
Vengono anche detti modelli booleani. I sensori vengono modellati come se avessero un range predeterminato di e cacia, ovvero copertura completa entro una certa distanza e copertura nulla oltre a questa distanza. Spesso si rappresenta l'area di sensing di un sensore si come un disco di raggio ri
cen-trato nelle coordinate di di (vedi Figura 4.1(a)). L'equazione 4.1 è un esempio
di questo.
Dato un punto p interno alla SR, l'equazione 4.2 calcola la probabilità che un generico sensore di rilevi un evento che accade in p [32].
Pdi/p= 1 se dist(di, p) ≤ ri 0 altrimenti (4.2)
CAPITOLO 4. IL PROBLEMA DELLA COPERTURA NEL MCS 23 La Figura 4.1(b) descrive gra camente il signi cato di questa equazione.
(a) (b)
Figura 4.1: Modello binario: (a) area di sensing di un sensore (b) gra co della probabilità
Modelli di questo tipo vengono ampiamente utilizzati grazie alla loro sem-plicità, nonostante non siano molto realistici: ad esempio, di cilmente un sensore avrà la stessa capacità di rilevamento in tutte le direzioni e comunque questa capacità nel caso generale diminuirà allontanandosi da esso. Questo può portare a stimare in maniera errata le prestazioni del sistema nel mondo reale.
4.2.2 Modelli di copertura probabilistici
A causa dei limiti dei modelli booleani, sono stati introdotti i modelli pro-babilistici, che catturano la natura stocastica del sensing.
Se, analogamente a quanto fatto nella Sezione 4.2.1, consideriamo la probabi-lità che un sensore di rilevi un evento che accade nel punto p, un esempio di
modello probabilistico è dato dall'equazione 4.3. Pdi,p =
C
dist(di, p)γ (4.3)
in cui C è una costante e γ è un esponente di attenuazione (path attenuation exponent).
In questo caso, la misura della copertura è inversamente proporzionale alla distanza fra il punto e il sensore. Quando la distanza diventa molto grande, la copertura può essere assunta nulla; viceversa, quando la distanza diventa
CAPITOLO 4. IL PROBLEMA DELLA COPERTURA NEL MCS 24 molto piccola, la copertura può essere assunta completa.
Un altro modello che fa parte di questa famiglia è il modello di copertura probabilistico troncato (truncated probabilistic coverage model), descritto dalla seguente equazione: Pdi/p = Ce−δdist(di,p) se dist(d i, p) ≤ ri 0 altrimenti (4.4)
con δ un parametro che dipende dalle speci che caratteristiche del sensore. La Figura 4.2 ([32]) confronta i modelli di coverage descritti dalle equazio-ni 4.2, 4.3 e 4.4.
Figura 4.2: Misure di copertura in funzione della distanza fra il punto con-siderato e un generico sensore, secondo i modelli binario, probabilistico e probabilistico troncato.
4.2.3 Modelli di copertura basati sull'evidenza
Nonostante i modelli puramente probabilistici rappresentino un migliora-mento rispetto a quelli binari nella rappresentazione della realtà, non conside-rano eventuali imperfezioni dei sensori.
I modelli evidence-based considerano due stati che speci cano se un punto p della regione di interesse è coperto: θ0 (non coperto o not detected) e θ1
CAPITOLO 4. IL PROBLEMA DELLA COPERTURA NEL MCS 25 il cosiddetto Frame of Discernment (FoD), si indica con Θ = {θ0, θ1}.
Analogamente a quanto fatto nelle sezioni precedenti, si considera un generico sensore di con sensing range ri. Si aggiunge a questo un'altra misura rui tale
che 0 ≤ rui ≤ ri, che rappresenta un intervallo di incertezza (uncertain range).
Figura 4.3: Rappresentazione dell'intervallo di sensing e dell'intervallo di incertezza di un sensore
Si consideri la Figura 4.3 [33].
• la zona di rilevazione sicura (Certain Detection Zone, CDZ) del sensore di è un disco centrato in di di raggio ri− rui
• la zona di incertezza di di (Uncertainty Zone, UZ) è il complemento
della sui CDZ ristretto alla regione di interesse (qui indicata con RoI, per Region of Interest), ovvero: UZ = CDZRoI. A sua volta, la UZ è
suddivisa in:
zona di ignoranza parziale (Partial Ignorance Zone, PIZ), un anello centrato in di con raggio interno ri− rui e raggio esterno ri
zona di ignoranza totale (Total Ignorance Zone, TIZ), che è il com-plemento di PIZ ristretto alla regione di interesse, escludendo ov-viamente la CDZ: T IZ = P IZRoI−CDZ.
L'idea che sta alla base della formulazione di questi modelli è che un dato letto da un sensore è un supporto dato all'ipotesi {θ1 =detected}. Un sensore
non può supportare l'ipotesi {θ0 =not detected}, ma può rappresentare il suo
grado di ignoranza rispetto a un fenomeno supportando l'ipotesi Θ = {θ0, θ1}.
CAPITOLO 4. IL PROBLEMA DELLA COPERTURA NEL MCS 26 un grado di ducia bsi,p. Secondo quanto detto sopra, il suo complementare
1 − bsi,p viene assegnato all'intero FoD, perchè codi ca l'ignoranza del sensore.
4.3 Modelli di copertura temporali
Come nella Sezione 3.1.2, suddividiamo la regione di interesse in k2 caselle
di lato L/k. Senza perdita di generalità, consideriamo un modello binario in cui i sensing range non siano dei dischi, ma ricoprano esattamente una delle caselle dell'area. Poniamo per ipotesi che, nel caso ci siano contemporanea-mente più dispositivi nella stessa casella, questi leggano esattacontemporanea-mente lo stesso valore.
Supponiamo che un osservatore esterno possa inserire da remoto dei task a tutti i sensori. Questi possono essere delle azioni quali ad esempio la raccolta di un determinato dato per una settimana in una regione limitata.
Aggiungiamo una dimensione, quella del tempo, secondo quanto fatto in [24]: ad esempio, un task viene inserito al tempo 0 e termina al tempo T. Il periodo di raccolta dei dati sarà quindi indicato con [0, T ]. Suddividiamo questa ne-stra temporale in s sottointervalli (slot) lunghi T/s. In ogni slot, ogni sensore esegue una lettura e invia il risultato all'osservatore.
Si può adesso modellare la SR sia nel tempo che nello spazio come una se-quenza di s matrici di dimensione k, ovvero SR = C1, C2, . . . , Cs. Al tempo
t, la matrice Ct sarà composta da elementi ctx,y, con 0 ≤ x, y ≤ k. Ogni ele-mento denota se la casella corrispondente, qx,y, è coperta al tempo t. Possiamo
esprimere questo fatto con la seguente equazione: ctx,y = 1 se ∃ di ∈ M ∪ N in qx,y al tempo t 0 altrimenti (4.5)
L'equazione 4.5 non considera il valore letto dal sensore, ma solo se è presente o meno un sensore che copre la casella di coordinate (x, y) al tempo t.
De niamo f : (C1, C2, . . . , Cs
) → R+ ∈ [0, 1], una funzione di copertura
che consideri anche la dimensione temporale. f sarà implementata in modo diverso a seconda del modello di copertura considerato.
Se si considera il modello binario - qui indicato come BC - la funzione si limiterà a valutare la frazione di caselle coperte nell'arco della nestra temporale di
CAPITOLO 4. IL PROBLEMA DELLA COPERTURA NEL MCS 27 grandezza T . Possiamo de nirla come:
fBC(SR) = s X t=1 |Ct| sk2 ∈ [0, 1] (4.6) con |Ct| = Pk x,y=1 ct
x,y = numero di caselle della SR coperte al tempo t.
Una versione più generale di questo modello considera l''invecchiamento' di una lettura sensoriale e viene chiamato appunto modello di invecchiamento (Ageing Coverage Model, AC). In questo modo si possono rappresentare scenari in cui non è importante solo la presenza di una lettura all'istante corrente, ma in cui anche letture passate possono essere utili per rappresentare lo stato di una casella.
Si inseriscono dei parametri che modellano il meccanismo di decadimento di una lettura. In questo caso, la funzione è:
fAC(SR) = 1 β s X t=1 |Ct| sk2α s−t ∈ [0, 1] (4.7)
in cui |Ct| è de nito come nel caso precedente, β = Ps
t=1 αs−t
s è una costante di
normalizzazione e α ∈ (0, 1] è il valore di decadimento. La scelta di α può dipendere sia da proprietà siche del sensore che dal tipo di task assegnato. Per come è de nita la funzione fAC, il peso di una lettura dipende dalla sua
lontananza nel tempo rispetto all'istante corrente.
4.4 Introduzione degli interpolatori
Dati n dispositivi ssi e m dispositivi mobili, la migliore ottimizzazione possibile della loro dislocazione non potrà in ogni caso superare una copertura di k2
n+m. Questo perché in ogni istante un massimo di n + m caselle possono
essere coperte. Se si vuole superare questa soglia la prima soluzione a cui si può pensare è aumentare il numero dei sensori, con tutte le conseguenze che questo comporta: aumento dei costi, reclutamento di nuovi utenti eccetera, come visto nei Capitoli precedenti.
Qualora l'incremento del numero di sensori non sia un'opzione o le suddette conseguenze portino a situazioni non desiderate, si può aumentare la
coper-CAPITOLO 4. IL PROBLEMA DELLA COPERTURA NEL MCS 28 tura usando un opportuno metodo di interpolazione. Analogamente a quanto descritto nella Sezione 2.1 per le WSN in questo modo il valore di una casella può essere stimato in vase ai valori disponibili per le caselle vicine.
Seguendo ancora la notazione usata nella Sezione 3.1.2, possiamo dire che lo scopo dell'interpolazione è attribuire a ogni casella un valore Z∗(q
x,y)alla ne
del periodo di campionamento [0, T ]. Di nuovo, come già approfondito, indi-cando con Z(qx,y)una lettura nella casella di coordinate (x, y), a livello teorico
vale Z∗(q
x,y) = Z(qx,y) nelle caselle per cui ho una misurazione. Per le altre
caselle invece si avrà un errore dipendente dal tipo di interpolatore e dalle misurazioni disponibili: questo signi ca che la copertura sarà del 100%, ma si avrà un certo grado di inaccuratezza.
Una misura della deviazione di un interpolatore Z∗ in un istante di tempo
t rispetto al fenomeno misurato è data dalla sua varianza, σ2t. Si può de ni-re una nuova funzione g che calcola il contributo dato dall'interpolazione alla copertura combinando in qualche modo - che dipende dagli obiettivi - i valori della varianza a ogni istante, cioè g : (σ2
0, σ12, . . . , σs2) → R+∈ [0, 1].
Data g, il modello di copertura si può ora esprimere considerando sia la coper-tura della regione senza l'interpolazione che il contributo dell'interpolazione una nuova funzione con ˆf(SR) = hf (SR), g(SR)i.
Capitolo 5
Organizzazione della
sperimentazione
Nel presente capitolo verranno descritti lo sviluppo del simulatore, l'am-biente di simulazione e la con gurazione degli esperimenti.
La parte principale del codice - tranne quindi la fase di setup iniziale e l'aggregazione nale dei dati - è un loop che viene eseguito tante volte quante bastano per coprire la nestra temporale considerata con slot di ∆ secondi. All'interno di queste iterazioni vengono utilizzati i dati disponibili, nelle moda-lità descritte nella Sezione 5.1, per calcolare diverse istanze del kriging, ognuna su un diverso insieme di nodi.
I risultati del kriging saranno poi analizzati attraverso l'uso di diverse tecniche, introdotte nella Sezione 5.2.
5.1 Preprocessing dei dati
5.1.1 Il fetch dei dati da WU
Come già accennato nella Sezione 3.2.2, non è stato possibile utilizzare un dataset preesistente di informazioni relative alla temperatura nella regione considerata. È stato quindi necessario costruirne uno ad hoc: questo è stato fatto a partire da dati realmente rilevati da alcune stazioni meteorologiche po-sizionate nell'area e raccolti dal servizio web Weather Underground, il quale li rende disponibili giornalmente per ogni stazione no alla mezzanotte del gior-no stesso.
I dati vengono estratti e organizzati nella maniera più consona agli scopi del 29
CAPITOLO 5. ORGANIZZAZIONE DELLA SPERIMENTAZIONE 30 presente lavoro tramite uno script, implementato nel linguaggio di program-mazione Python, che crea un le per ognuna delle stazioni concatenando le letture di ogni giorno nella nestra temporale desiderata. Alle informazioni delle stazioni si accede tramite URL del tipo https://www.wunderground. com/weatherstation/WXDailyHistory.asp?D={codice}&format=1, in cui si sostituisce a {codice} il codice della stazione corrente.
5.1.2 Utilizzo dei dati
Le stazioni meteorologiche sono state suddivise in due insiemi disgiunti, nel seguito denominati per semplicità WUA e WUB.
Come già detto, i dataset MDC Nokia e ParticipAct contengono per ogni dispositivo solo una serie di coordinate GPS (latitudine e longitudine), non accompagnate da letture sensoriali. Per simulare che i dispositivi siano invece equipaggiati con dei sensori per il rilevamento di dati ambientali, si esegue una prima interpolazione nei punti corrispondenti alle posizioni dei nodi mo-bili, usando come dati di partenza quelli forniti dalle stazioni del sottoinsieme WUA.
Gli elementi del sottoinsieme WUBvengono invece utilizzati come stazioni sse
vere e proprie, che verranno combinate in vari modi (vedi Sezione 5.1.4) alle stazioni mobili `aumentate' come descritto precedentemente per interpolare la sensing region.
L'interpolazione nale sulla sensing region si calcola utilizzando di nuovo un kriging su una griglia formata da 300 punti a distanza 200 metri l'uno dall'al-tro (Figura 5.1). In questo modo, la regione risulta interamente coperta e si hanno informazioni anche in aree sulle quali non sono presenti in quel momento dispositivi.
Creazione dei sottoinsiemi WUA e WUB
Per quanto riguarda la creazione dei sottoinsiemi WUA e WUB, sono stati
implementati due metodi distinti:
• metodo statico: i sottoinsiemi vengono creati una volta per tutte pri-ma dell'esecuzione del programpri-ma. La suddivisione viene fatta al di fuori dell'ambiente MATLAB, semplicemente osservando dove sono localizza-te le stazioni e inserendole nei sottoinsiemi WUA e WUB in maniera
CAPITOLO 5. ORGANIZZAZIONE DELLA SPERIMENTAZIONE 31
Figura 5.1: Griglia creata sull'area della città di Bologna
Figura 5.2: Le stazioni meteorologiche di Bologna suddivise staticamente negli insiemi WUA (triangoli) e WUB (stelle)
CAPITOLO 5. ORGANIZZAZIONE DELLA SPERIMENTAZIONE 32 • metodo dinamico: a ogni iterazione si scelgono come stazioni del sot-toinsieme WUB quelle `più lontane' dai nodi mobili disponibili a quella
speci ca iterazione. Come metrica per esprimere la lontananza si è de-ciso di considerare la media delle distanze da una stazione a ogni nodo mobile.
La motivazione che ha portato all'implementazione del metodo dinamico è che, come è stato introdotto nel Capitolo 1, le persone tendono a muoversi in un insieme di luoghi popolari, quindi è naturale che, se consideriamo ad esempio una città, ci siano delle zone meno frequentate, ovvero meno coperte dai nodi mobili.
Nel caso della città di Bologna, il dataset ParticipAct monitora gli sposta-menti di un insieme di studenti dell'Università di Bologna. La concentrazione maggiore di campioni si avrà quindi nei dintorni delle sedi universitarie, delle stazioni ferroviarie e in generale nel centro della città, mentre le aree periferi-che risulteranno essere meno frequentate (vedi Figura 3.3(b)).
In un caso di applicazione reale è una buona scelta, ove possibile, posizionare i nodi ssi nelle zone meno coperte dagli utenti.
Esempio di suddivisione dinamica delle stazioni
Nella Figura 5.3 sono rappresentati in rosso i nodi mobili presenti sulla sensing region in un determinato istante. In nero, invece, le stazioni sse, ognuna etichettata con il suo codice univoco di Weather Underground.
Per suddividere le stazioni nei due sottoinsiemi WUA e WUB si calcola, per
ogni stazione, la sua distanza media dai nodi mobili espressa in chilometri. Le distanze calcolate per questo esempio sono riportate nella Tabella 5.1.
Delle 19 stazioni meteorologiche disponibili per la città di Bologna, si è deciso di utilizzarne 9 come insieme WUA e 10 come insieme WUB. In
parti-colare, dati i calcoli delle distanze sopra riportati, le stazioni saranno ripartite come indicato nella Tabella 5.2 e illustrato nella Figura 5.4.
5.1.3 Allineamento temporale dei dati
I dati che si hanno a disposizione per quanto riguarda le coordinate GPS vanno dal 7 Ottobre 2014 al 12 Ottobre 2014, mentre per quanto riguarda i dati ambientali vanno dal 4 Novembre 2016 al 9 Novembre 2016.
CAPITOLO 5. ORGANIZZAZIONE DELLA SPERIMENTAZIONE 33
Figura 5.3: Le stazioni meteorologiche di Bologna, etichettate con il loro codice
Codice stazione Distanza media (km)
IBOLOGNA40 2.4299 IBOLOGNA50 1.9073 IBOLOGNA95 1.0562 IBOLOGNA103 1.3665 IBOLOGNA123 1.0604 IBOLOGNA147 1.3375 IBOLOGNA186 1.0414 IBOLOGNA193 1.0705 IEMILIAR178 1.6322 IEMILIAR229 1.7069 IBOLOGNA49 0.9892 IBOLOGNA52 1.9405 IBOLOGNA77 1.1912 IBOLOGNA89 1.2498 IBOLOGNA105 1.2368 IBOLOGNA139 1.4235 IBOLOGNA145 0.9755 IBOLOGNA173 1.7884 IBOLOGNA181 1.1711
CAPITOLO 5. ORGANIZZAZIONE DELLA SPERIMENTAZIONE 34 Insieme WUA IBOLOGNA145 IBOLOGNA49 IBOLOGNA186 IBOLOGNA95 IBOLOGNA123 IBOLOGNA193 IBOLOGNA181 IBOLOGNA77 IBOLOGNA105 Insieme WUB IBOLOGNA89 IBOLOGNA147 IBOLOGNA103 IBOLOGNA139 IEMILIAR178 IEMILIAR229 IBOLOGNA173 IBOLOGNA50 IBOLOGNA52 IBOLOGNA40
Tabella 5.2: Suddivisione dinamica delle stazioni nei due sottoinsiemi
Figura 5.4: Le stazioni meteorologiche di Bologna suddivise dinamicamente negli insiemi WUA (triangoli) e WUB (stelle)
CAPITOLO 5. ORGANIZZAZIONE DELLA SPERIMENTAZIONE 35 delle sperimentazioni è stato su ciente modi care le date delle informazioni ricavate da ParticipAct per farle coincidere con quelle ricavate da WU.
Un altro problema derivante direttamente dalla diversa natura dei due da-taset è quello della temporizzazione dei campioni: i dati di ParticipAct e quelli di WU sono ovviamente indipendenti, quindi saranno disponibili a tempi di-versi.
Nella Sezione 5.1.2 si è visto che il programma esegue il kriging più di una volta e con due obiettivi distinti:
• un primo kriging `di setup' a partire dal sottoinsieme WUA, per assegnare un valore di temperatura ai nodi mobili
• un secondo kriging per combinare i dati dei nodi mobili con quelli delle stazioni sse del sottoinsieme WUB, per assegnare un valore di
tempera-tura a ogni punto della sensing region.
Per risolvere il problema della diversa temporizzazione, in ogni intervallo della nestra temporale considerata:
• si tiene conto solamente di una delle posizioni rilevate per ogni nodo mobile
• si fa la media dei dati di temperatura disponibili per ogni stazione nell'in-tervallo corrispondente all'iterazione corrente; i valori delle medie sono quelli che verranno utilizzati per eseguire il calcolo dei kriging.
Da notare che, per entrambi i tipi di dato, a una certa iterazione si può avere più di un valore, ma si può anche averne nessuno. In quest'ultimo caso, la stazione ssa o il dispositivo mobile vengono ignorati a quella iterazione. Esempio di allineamento
Consideriamo una versione ridotta del problema per il kriging di assegna-mento dei valori di temperatura ai nodi mobili, in cui il sottoinsieme WUA
contiene solo 3 elementi: le stazioni meteorologiche con codice IBOLOGNA40, IBOLOGNA50 e IEMILIAR229. Consideriamo inoltre intervalli temporali di ampiezza ∆ =1h e in particolare l'intervallo che va dalle 09:00:09 alle 10:00:09 del giorno 4 Novembre 2016.
CAPITOLO 5. ORGANIZZAZIONE DELLA SPERIMENTAZIONE 36
Data Ora Temperatura, ◦C . . .
2016-11-04 08:46:00 13.8 . . .
2016-11-04 09:06:00 13.9 . . .
2016-11-04 17:02:00 16.9 . . .
Tabella 5.3: Frammento di le della stazione IBOLOGNA40
Data Ora Temperatura, ◦C . . .
2016-11-04 08:49:00 12.1 . . .
2016-11-04 17:06:00 14.3 . . .
Tabella 5.4: Frammento di le della stazione IBOLOGNA50
Data Ora Temperatura, ◦C . . .
2016-11-04 09:00:00 10.40 . . . 2016-11-04 09:05:00 10.60 . . . 2016-11-04 09:12:00 10.50 . . . 2016-11-04 09:20:00 10.40 . . . 2016-11-04 09:25:00 10.50 . . . 2016-11-04 09:32:00 10.60 . . . 2016-11-04 09:40:00 10.80 . . . 2016-11-04 09:50:00 11.20 . . . 2016-11-04 09:55:00 11.30 . . . 2016-11-04 10:00:00 11.20 . . . 2016/11/04 10:05:00 11.30 . . .
