Tecniche Communication-saving per l’Acquisizione Dati nel Sistema

Tecniche Communication-saving

per l’Acquisizione Dati nel Sistema

di Trasporto Intelligente Pegasus

UNIVERSITÀ DEGLI STUDI DI MODENA E REGGIO EMILIA

Facoltà di Scienze Matematiche, Fisiche e NaturaliCorso di Laurea Magistrale in Informatica

Tesi di Laurea di: Marcello Pietri Relatore: prof. Riccardo Martoglia

Introduzione

Lo stato attuale del traffico: In particolari momenti molto congestionato

Code, rallentamenti e ingorghi

Elevato numero di incidenti

Inquinamento acustico e ambientale

Deterioramento della qualità di vita

Intelligent Transportation Systems

Introduzione

Pegasus è un sistema di trasporto intelligente (ITS)

il cui obiettivo è la realizzazione di una piattaforma

info-telematica che dovrà permettere:il miglioramento della mobilità

l’incremento della sicurezza

Come?

Attraverso la riduzione della congestione e dei

tempi di percorrenza, tramite:l’invio di informazioni sul traffico in tempo reale

il calcolo del percorso ottimo

Introduzione

Real-time comms engine

Smart navigation engine Maps &

real-timedata

User interface

GPS unitAccel unit

GPRS V2I unit

WiFi V2V unit

Veicolo

OBU fisicaArchitettura dell’OBU

Interfaccia utente

Introduzione

ad-hoc, multi-hop, V2V communication V2I communication

BTS

BTS

Control Centre

Infr

astr

uctu

red

Net

wor

k

OBUs

OBU OBUOBU

OBU

Communication Manager

EOI Ontology

Recom-mender System

POI Ontology

OBU

OBU

Control Centre

V2I interaction

V2V interaction

Data acquisition

Storage Manager

GIS tables

Query ProcessingEngine

DSMS

Service Manager

Smart Navi-gation

SafetyUrban Mobility

Service Module

Communication-saving!

OBU

Introduzione

Introduzione

Ambito principale di ricerca:

Tecniche communication-saving• Servono a ridurre l'occupazione di banda nella trasmissione dati

digitale

• Sfruttano le ridondanze nell'utilizzo dei dati

• Introducono un’eventuale perdita d’informazione

• Sono categorizzabili come compressioni di tipo lossy

• Sono molteplici e possono essere profondamente diverse

• I risultati in uscita possono variare drasticamente in base al

contesto

• La loro qualità deve essere stabilita dall’analisi sperimentale

Argomenti della tesi:

Stato dell’arte

Analisi e progetto del simulatore

Creazione degli scenari

Simulazioni di traffico

Analisi sperimentale

Stato dell’arteTecniche communication-saving proposte:

Simple time samplinginvio di dati ad intervalli temporali regolari, ad esempio ogni 2 secondi

Simple space samplinginvio di dati ad intervalli spaziali regolari, ad esempio ogni 100 metri percorsi

Map-based samplinginvio di dati al variare del tratto di strada percorsa, ad esempio quando da via

Roma

si passa a viale Italia, oppure quando si passa dal tratto 145 al tratto 146 dell’A1

Deterministic information-needinvio di dati nel momento in cui la velocità effettiva del veicolo si discosta da quella

segnalata nella mappa, ad esempio quando sull’A1 (130Km/h) si viaggia a 70Km/h

Linear regressionsi ottimizza l’invio dei dati interpolandoli con la migliore retta possibile, stimata

con il metodo dei minimi quadrati; ad esempio invia 10 dati memorizzati nella

history inviando le coordinate di due punti e il loro tempo di acquisizione

Strategie di clustering V2Vinvio unificato dei dati di più veicoli previa aggregazione e comunicazione WiFi V2V

Stato dell’arte

Necessità di dati reali sul traffico in formato digitale

Utilizzo del simulatore di traffico Vissim

Implica l’utilizzo di scenari reali ad hoc

Necessità di un simulatore di OBU al fine di testarele tecniche communication-saving e le strategie V2V

Creazione del simulatore

In letteratura non sono presenti analisi o ambienti di sviluppo per le tecniche communication-saving :

Analisi, progetto e sviluppo del software

Testing e validazione dei risultatiAnalisi sperimentale


Stato dell’arte






Dopo la fase di analisi e la fase di specifica SRS, sono statisviluppati gli use case diagram e gli activity diagram, chehanno permesso la stesura dei package diagram e dei class diagram dello standard UML:

Real-time comms engine

Smart navigation engine Maps &real-time

dataUser interface

GPS unit Accel unit GPRS V2I unit WiFi V2V unit Architettura reale dell’OBU

Class diagramdell’OBU simulata

Analisi e progetto del simulatoreTecniche communication-saving implementate:

Simple time samplinginvio di dati ad intervalli temporali regolari, ad esempio ogni 2 secondi

100 metri 100 metri

V2I V2I

Simple space samplinginvio di dati ad intervalli spaziali regolari, ad esempio ogni 100 metri percorsi

2 secondi

V2I V2I

2 secondi

Analisi e progetto del simulatoreTecniche communication-saving

implementate:Map-based sampling

invio di dati al variare del tratto di strada percorsa, ad esempio quando da via Roma

si passa a viale Italia, oppure quando si passa dal tratto 145 al tratto 146 dell’A1

Via Emilia est

V2I

V2I

Via Roma

Viale Italia

V2I

Via Emilia nord-est


Deterministic information-needinvio di dati nel momento in cui la velocità effettiva del veicolo si discosta da quella

teorica

Versione classica:

48 Km/h V2I25 Km/h 51 Km/h

Versione sperimentale con history:

V2I58 Km/h38 Km/h Nuova media 38,1 Km/hMedia 38,27 Km/h


Simple regressionsfrutta la possibilità di eseguire varie tecniche communication-saving in

contemporanea, infatti si occupa di interpolare solo i tratti rettilinei,

mentre tralascia i tratti curvilinei

Linear regressioncerca di ottimizzare qualsiasi percorso interpolandolo con la migliore retta

possibile, utilizzando il metodo dei minimi quadrati

tragitto re

ttilineo ipotetico

tragitto re

ale

semi-rettilineo

errori tragitto reale

qualsiasi

tragitto rettilineo ipotetico

latlat

lon lo

n


Stato dell’arte






Lo scenario di Beijing (Pechino, Cina):

Progetto originale

Progetto nel simulatore di traffico Vissim

1Km

1,2Km

Creazione degli scenariLo scenario di Toll Plaza (Cadmen, New Jersey, USA):

Modello usato per analizzare le operazioni sul traffico in

Benjamin Franklin Toll Plaza per i veicoli verso il ponte di Delaware

River da Cadmen, e dal New Jersey

verso Philadelphia in Pennsylvania,

USA. I volumi di traffico, le velocità,

e tutti gli altri dati sono reali.

2,3Km

1,4Km

0,4Km

Creazione degli scenariLo scenario italiano di Bologna:

Modello creato dall’università di Bologna,

modificato in modo da permettere la circolazione dei veicoli nelle strade.I flussi di veicoli sono stati creati a posteriori con l’utilizzo di dati

pubblici.

0,6 Km

1,4Km1,6Km

1,2 Km

Creazione degli scenariLo scenario italiano di Roma:

Questo modello è stato realmente

usato dalla pubblica amministrazione

per creare ed analizzare la variante

“via Tiburtina, tratto via Casal Bruciato – Ponte Mammolo” a

Roma; nello specifico per la costruzione

e per gli impianti semaforici.Tutti i dati, tra cui anche i flussi

di veicoli, sono reali, anche se

riferiti al ‘99. Si presume che il numero

di veicoli ad oggi sia notevolmente aumentato.

2,2Km0,7Km


Stato dell’arte





Simulazioni di traffi co

Le simulazioni di traffico sono state eseguite con il software Vissim,

un potente simulatore multimodale della PTV Vision:

Per un utilizzo avanzato si richiede la lettura di più di mille pagine di

manuali in lingua inglese o tedesca

Il traffico è stato monitorato in tempi compresi tra un minuto e quattro ore

La quantità di dati utili prodotti è stata superiore ai dieci giga byte

Il campionamento è stato effettuato ad intervalli di 0,1 e 0,5 secondi

Simulazioni di traffi co


Stato dell’arte






• La fase di analisi sperimentale è stata suddivisa in due parti: l’analisi V2I e l’analisi V2V.

• Le tecniche communication-saving e le strategie di clustering V2V sono state sperimentate su tutti gli scenari descritti e anche sugli stessi scenari leggermente modificati in termini di viabilità e numero di veicoli.

• I parametri utilizzati coprono l’intero range di valori accettabili in termini di qualità del servizio.

• Nell’analisi V2I il trade-off tra quantità dati inviati ed errori commessi, in termini di distanza e velocità, determina la qualità della tecnica in analisi.

Analisi sperimentale – V2I

60 0,5

60 0,1

600 0,5

600 0,1

3600 0,5

0,0% 0,2% 0,4% 0,6% 0,8% 1,0% 1,2% 1,4% 1,6% 1,8% 2,0%

ROME

errori commessi - baseline

Dist err% ok V err % ok

percentuale d'errore

tipo

di c

am

pio

na

me

nto

60 0,5

60 0,1

600 0,5

600 0,1

3600 0,5

0 2000 4000 6000 8000 10000 12000 14000

ROME

dimensione dati per obu

data x obu

byte trasmessi

tipo

di c

am

pio

na

me

nto

Stime preliminari e dimensione del flusso di dati

Gli errori sulla distanza e sulla velocità diminuiscono al diminuire del

campionamento

La quantità di dati inviati aumenta al diminuire dell’intervallo di

campionamento

Il flusso di dati medio per ogni OBU, nella simulazione da 3600 secondi, è di

3035 byte.

Considerando circa un milione di OBU, il flusso di dati totali è di circa 0,8

MB/s, pari a 2,83 GB all’ora e 68 GB al giorno.

Analisi sperimentale – V2ISimple time sampling


campionamento


campionamento

La crescita dell’errore non è lineare come per i dati inviati, ma iperbolica

0,5

1

2

4

8

0,0% 1,0% 2,0% 3,0% 4,0% 5,0% 6,0% 7,0% 8,0%

ROMA

Dur. 600 - errori al variare del campionamento


errore %

cam

pio

na

me

nto

(s

)

0,5

1

2

4

8

0 500 1000 1500 2000 2500 3000

ROMA

Dur. 600 - data per obu al variare del campionamento

data x obu

byte trasmessi

cam

pio

na

me

nto

(s

)

0,7510% 0,1910%

1,1470% 0,2812%

1,9913% 0,5401%

3,7658% 1,2828%

7,2913% 3,4007%

Analisi sperimentale – V2ISimple space sampling


campionamento


campionamento

L’errore sulla distanza risulta molto soddisfacente, quello sulla velocità no

0,5s

1m

10m

20m

40m

80m

100m

0,0% 1,0% 2,0% 3,0% 4,0% 5,0% 6,0% 7,0% 8,0% 9,0%

ROMA



errore %

cam

pio

na

me

nto

0,5s

1m

10m

20m

40m

80m

100m

0 500 1000 1500 2000 2500 3000

ROMA


data x obu

byte trasmessi

cam

pio

na

me

nto

0,7510% 0,1910%

0,7531% 2,3587%

1,1175% 5,5345%

1,7333% 5,8719%

3,1825% 6,0067%

6,1879% 6,6805%

8,2286% 7,3627%

Analisi sperimentale – V2IDeterministic information-need

(Versione sperimentale con history)

Gli errori sulla distanza risultano inferiori a quelli sulla velocità

Le percentuali di errore sono decisamente superiori alle aspettative

La tecnica è da scartare

0,5s

0.01km/h-h15

0.05km/h-h15

0.1km/h-h1

0.1km/h-h3

0.1km/h-h9

0.1km/h-h15

1km/h-h9

10km/h-h9

0,0% 10,0% 20,0% 30,0% 40,0% 50,0% 60,0% 70,0% 80,0% 90,0% 100,0%

ROMADur. 600 - errori al variare del campionamento

Dist err% ok V err % okerrore %

cam

pion

amen

to

0,5s

0.01km/h-h15

0.05km/h-h15

0.1km/h-h1

0.1km/h-h3

0.1km/h-h9

0.1km/h-h15

1km/h-h9

10km/h-h9

0 500 1000 1500 2000 2500 3000

ROMADur. 600 - data per obu al variare del campionamento

data x obubyte trasmessi

cam

pio

na

me

nto

0,7510% 0,1910%

0,8124% 3,5226%

0,8360% 10,9404%

1,0789% 25,0423%

0,8740% 18,4573%

0,8647% 17,7751%

0,8643% 17,7673%

5,2492% 85,9966%

62,1489% 99,4708%

Analisi sperimentale – V2IDeterministic information-need

(Versione off-line)

L’andamento e le deduzioni sono leggermente negativi rispetto simple time

sampling

La variazione su errori e quantità di dati non subisce mutamenti drastici fino a

1Km/h

La tecnica è utilizzabile per individuare i punti di rallentamento (stop, code a

tratti, …)0,5s

0.025Km/h

0.05Km/h

1Km/h

2Km/h

4Km/h

8Km/h

10Km/h

0,0% 5,0% 10,0% 15,0% 20,0% 25,0% 30,0% 35,0% 40,0% 45,0%

ROMA



errore %

cam

pio

na

me

nto

0,5s

0.025Km/h

0.05Km/h

1Km/h

2Km/h

4Km/h

8Km/h

10Km/h

0 500 1000 1500 2000 2500 3000

ROMA


data x obu

byte trasmessi

cam

pio

na

me

nto

0,7510% 0,1910%

0,8311% 0,3088%

1,6499% 1,1502%

3,0952% 2,2134%

11,0853% 6,0523%

38,3545% 11,4743%

41,9727% 14,5546%

42,3624% 15,7069%

Analisi sperimentale – V2IMap-based sampling

Gli errori sulla distanza e sulla velocità risultano molto marcati

Il trade-off errori commessi - dati inviati risulta peggiore che con simple time

sampling

L’uso di questa tecnica potrebbe riguardare solo la ricostruzione dell’itinerario

percorso

0,5s

map F

map T

0,0% 5,0% 10,0% 15,0% 20,0% 25,0% 30,0% 35,0%

ROMA



errore %

cam

pio

na

me

nto

0,5s

map F

map T

0 500 1000 1500 2000 2500 3000

ROMA


data x obu

byte trasmessi

cam

pio

na

me

nto

0,7510% 0,1910%

29,9905% 22,7322%

9,8246% 6,3324%

Analisi sperimentale – V2ISimple regression

Il trade-off errori commessi - dati inviati risulta di poco peggiore a simple time

sampling

Usando campionamenti base più fini si ottengono risultati in linea a simple

time sampling

I risultati ottenuti indirizzano verso lo sviluppo di tecniche simili più avanzate

0,5s

7m_h3

7m_h5

7m_h7

7m_h10

10m_h3

10m_h5

10m_h7

10m_h10

0,0% 1,0% 2,0% 3,0% 4,0% 5,0% 6,0%

ROMA



errore %

cam

pio

na

me

nto

0,5s

7m_h3

7m_h5

7m_h7

7m_h10

10m_h3

10m_h5

10m_h7

10m_h10

0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000

ROMA


data x obu

byte trasmessi

cam

pion

amen

to

0,6862% 0,1536%

1,8485% 0,6496%

2,6247% 0,9659%

3,5071% 1,2809%

5,4560% 1,8572%

1,8487% 0,6490%

2,6385% 0,9777%

3,4700% 1,3103%

4,9872% 1,8220%

Analisi sperimentale – V2ILinear regression (1)

Il trade-off errori commessi - dati inviati risulta molto performante

Gli errori su distanza e velocità risultano inferiori all’1% interpolando anche

10 punti

I risultati ottenuti indirizzano verso l’analisi su scenari in cui l’OBU circola per

più tempo

0,5s on 0.5

0,5s on 0,1

reg h3 on 0,5 f0.5

reg h7 on 0,1 f0.5

reg h10 on 0,1 f0.5

reg h8 on 0,1 f60

0,00% 0,20% 0,40% 0,60% 0,80% 1,00% 1,20% 1,40% 1,60%

BOLOGNA



errore %

cam

pio

na

me

nto

0,5s on 0.5

0,5s on 0,1

reg h3 on 0,5 f0.5

reg h7 on 0,1 f0.5

reg h10 on 0,1 f0.5

reg h8 on 0,1 f60

0 2000 4000 6000 8000 10000 12000 14000 16000

BOLOGNA


data x obu

byte trasmessi

cam

pio

na

me

nto

0,4429% 0,3893%

0,4098% 0,4475%

0,9140% 1,5298%

0,6180% 0,6793%

0,7081% 0,8336%

0,5712% 0,5585%


Il trade-off errori commessi - dati inviati risulta migliore di simple time

sampling

L’errore sulla distanza si è ridotto fino a 5,6 volte, quello sulla velocità fino a 2

volte

L’invio di dati è diminuito di 2,3 volte nel primo caso e di 3,5 volte nell’ultimo

0,5s

regression h3 on 0.5



0,0% 0,1% 0,2% 0,3% 0,4% 0,5% 0,6%

BOLOGNA - RID



errore %

ca

mp

ion

am

en

to

0,5s




0 20000 40000 60000 80000 100000 120000 140000 160000

BOLOGNA - RID


data x obu

byte trasmessi

cam

pio

na

me

nto

0,5401% 0,5289%

0,0963% 0,2652%

0,1531% 0,2776%

0,3077% 0,5722%


Il trade-off errori commessi - dati inviati risulta migliore di simple time

sampling

L’errore sulla distanza si è ridotto fino a 1,6 volte, quello sulla velocità fino a

1,7 volte

L’invio di dati è diminuito fino a 1,8 volte

0,5s

1s

2s





0,0% 0,1% 0,2% 0,3% 0,4% 0,5% 0,6% 0,7% 0,8% 0,9% 1,0%

BOLOGNA - ZTL



errore %

ca

mp

ion

am

en

to

0,5s

1s

2s





0 50000 100000 150000 200000 250000 300000 350000 400000

BOLOGNA - ZTL


data x obu

byte trasmessi

cam

pio

na

me

nto

0,4577% 0,4613%

0,1187% 0,1248%

0,7974% 0,7848%

0,1595% 0,1833%

0,1036% 0,1273%

0,0989% 0,0824%

0,1962% 0,1692%

Analisi sperimentale – V2V

0

5

10

15

20

25

30

Dimensione dei gruppi

(al variare dello scenario)

scenario

dim

ensi

one

grup

po (#

OB

U)

0

20

40

60

80

100

120

140

160

180

Permanenza veicolo nel gruppo

(al variare dello scenario)

scenario

Per

man

enza

vei

colo

(s)

Analisi V2V – variazione dello scenario

La dimensione dei gruppi e il tempo di permanenza variano in base allo

scenario

Il tempo di permanenza dell’OBU nel gruppo non è legato alla dimensione del

gruppo

Nel caso peggiore i veicoli permangono nel gruppo per circa 8 secondi, nel

migliore 177

Analisi sperimentale – V2VAnalisi V2V – variazione della copertura WiFi

I cambiamenti all’interno dei gruppi sono costanti La dimensione dei gruppi aumenta in modo lineare Il tempo medio di permanenza dei veicoli all’interno dei gruppi cresce in modo lineare

100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250

29

31

33

35

37

39

41

BEIJING - Dur. 1200 C0.5Dimensione media del gruppo

al variare della portata WiFi

Portata WiFi (metri)

Dim

ensi

one

del g

rupp

o (O

BU)

100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250

1,2

1,4

1,6

1,8

2

2,2

2,4

ROMA - Dur. 3600 C0.5Dimensione media del gruppo



Dim

ensi

one

del g

rupp

o (O

BU)

100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250

3

3,5

4

4,5

5

5,5

6

6,5

TOLL PLAZA - Dur. 3600 C0.5

Dimensione media del gruppoal variare della portata WiFi


Dim

ensi

one

del g

rupp

o (O

BU)

100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250

170

180

190

200

210

220

230

240

250

BEIJING - Dur. 1200 C0.5Tempo di permanenza



Tem

po d

i per

man

enza

(s)

100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250

60

65

70

75

80

85

90

95

Tempo di permanenzaal variare della portata WiFi


Tem

po d

i per

man

enza

(s)

TOLL PLAZA - Dur. 3600 C0.5

100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250

46

48

50

52

54

56

58

60

62

Tempo di permanenzaal variare della portata WiFi


Tem

po d

i per

man

enza

(s)

ROMA - Dur. 3600 C0.5

Analisi sperimentale – V2VAnalisi V2V – variazione del numero di OBU

L’andamento della grandezza media dei gruppi segue un comportamento standard La dimensione dei gruppi aumenta in modo logaritmico all’aumentare del numero di OBU Il tempo medio di permanenza di un veicolo in un gruppo diminuisce, fino a stabilizzarsi, al crescere del numero di OBU coinvolte

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

0

5

10

15

20

Grandezza media dei gruppi

(BOZTL 14400 0.5)Numero di OBU conivolte (dal basso) 25, 51, 80, 108

OBU id group

dim

en

sio

ne

de

l gru

pp

o

0 25 51 81 108

00.5

11.5

22.5

33.5

44.5

5f(x) = 3.0904430904358 ln(x) + 0.244654384905165R² = 0.980080417257215

Grandezza media gruppi

Numero di OBU coinvolte

Gra

nd

ezz

a d

el g

rup

po

(O

BU

)

0 25 51 81 108

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7f(x) = 0.452713571290125 ln(x) − 0.00110456543419718R² = 0.977186070859229

Cambiamento medio nei gruppi

Numero di OBU coinvolte

Ca

mb

iam

ne

ti p

er

seco

nd

o

Conclusioni

Il lavoro svolto:

Studio di tecniche communication-saving, strategie V2V e ambienti di simulazione presenti in letteratura

Utilizzo del simulatore di traffico professionale Vissim

Analisi, modifica e creazione di nuovi scenari per la simulazione di traffico

Analisi, progetto e implementazione di un simulatore di OBU

Analisi sperimentale dei dati ottenuti

ConclusioniGli obiettivi raggiunti:

Sviluppo del codice nel rispetto degli standard e in modo da permettere la portabilità sull’architettura reale di ogni OBU

Analisi di scenari reali al fine di mostrare i flussi di veicoli necessari per un efficiente utilizzo delle strategie V2V

Definizione di strategie e politiche di clustering tra veicoli

Stima della riduzione del carico sulle comunicazioni V2I, derivata dall’utilizzo di comunicazioni V2V

Conclusioni

Riduzione delle comunicazioni senza compromettere il trade-off dati inviati – errore commesso

Quantificazione delle reali quantità di informazioni con cui si avrà a che fare nel contesto pratico

Individuazione delle migliori strategie communication-saving utilizzabili nei contesti specifici della realtà

Studio e analisi di nuove tecniche communication-saving al fine di migliorare quelle proposte in letteratura

Sviluppi futuri

In merito alle tecniche communication-saving:

eseguire test su scenari molto più estesi, aggiornati e forniti da enti certificati, al fine di validare completamente le analisi svolte

implementare un’ulteriore codifica in stile Huffmann, affiancata ad altre compressioni lossless, al fine di ridurre ulteriormente la banda richiesta

implementare ed analizzare tecniche di regressione più complesse quali Multivariate adaptative regression splines e Segemented regression

Sviluppi futuriIn merito all’estensione delle funzionalità

dell’OBU:

sviluppare ulteriormente algoritmi per il clustering V2V, al fine di ottimizzare le comunicazioni ed i gruppi formati

analizzare praticamente le migliori combinazioni di utilizzo contemporaneo di tecniche communication-saving

studiare ed implementare una tecnica di auto-selezione adattativa, che selezioni il migliore insieme di tecniche communication-saving dinamicamente

GRAZIE A TUTTI PER L’ATTENZIONE

Tecniche Communication-saving per l’Acquisizione Dati nel Sistema

Documents

Transcript of Tecniche Communication-saving per l’Acquisizione Dati nel Sistema