Introduzione progetto Pegasus e obiettivo della tesi Algoritmo proposto e stato dellarte Scenario di...

UNIVERSITA’ DEGLI STUDI DI MODENA E REGGIO EMILIACORSO DI LAUREA IN INGEGNERIA INFORMATICA

STUDIO, SIMULAZIONE E VALUTAZIONE DI UN ALGORITMO

V2V PER LO SCAMBIO DI INFORMAZIONI

TESI DI LAUREA DI: MATTEO PERGOLA

RELATORE: PROF. FEDERICA ANDREOLI

CORRELATORI: ING. LUCA CARAFOLI E PROF. RICCARDO MARTOGLIA

STUDIO, SIMULAZIONE E VALUTAZIONE DI UN ALGORITMO V2V PER LO SCAMBIO DI INFORMAZIONI

Introduzione progetto Pegasus e obiettivo della tesi

Algoritmo proposto e stato dell’arte

Scenario di riferimento Sperimentazione Conclusioni e sviluppi futuri

INTRODUZIONEStato attuale del traffico:

• Elevato numero di incidenti• Consumo eccessivo di carburante• Inquinamento acustico e ambientale• Generale stato di congestione

Nuovi concetti di mobilita’ e trasporti promossi nel 7° Programma Quadro dell’UE

Sviluppo di ricerche per un sistema di trasporto intelligente (ITS) dove definire le tecnonologie dell’informazione e della comunicazione (ICT) da integrare

PROGETTO PEGASUS

ProgEtto per la Gestione della mobilita’Attraverso Sistemi infotelematici per l’ambito Urbanoper la Sicurezza di passeggeri, veicoli e merci

OBIETTIVO: Sviluppare un sistema di trasporto intelligente per una gestione del traffico efficente e per migliorare la sicurezza stradale

Tramite l’uso di una piattaforma infotelematicain cui ogni veicolo e’ equipaggiato con una OBU:On Board Unit

Progetto Industria 2015a cui partecipa l’ISGroup nell’unità IEIIT-CNR

PROGETTO PEGASUSScenario di riferimento

• Ogni veicolo tramite l’OBU invia e riceve dati dalla centrale

• Due differenti tipi di comunicazione

1) V2I Vehicle-to-Infrastructure 2) V2V Vehicle-to-Vehicle

• Il Centro di Controllo riceve i dati,

li salva, e gestisce i messaggi scambiati con le OBU

Il Centro di Controllo comunica tramite la rete GPRS

ad-hoc multi-hop V2V communicationV2I communication

BTS

BTS

Control Centre

Infr

ast

ruct

ure

d

Netw

ork

OBU

Real-time commsengine

Smart navigationengine

Maps &real-time

dataUser interface

GPS unit

Accel unit

WiFi V2V unit

GPRS V2I unit

OBU: On Board Unit

OBIETTIVO DELLA TESIL’uso della rete GPRS porta degli alti costi di trasmissione datitra ogni veicolo e il Centro di Controllo

Uso di tecniche comunication-savingper minimizzare le comunicazioni

• Strategia di comunicazione ibrida• Le comunicazioni V2V riducono il carico V2I

Combinazione e selezione dinamica di:

• Tecniche di comunication-saving V2V• Tecniche di comunication-saving V2I

OBIETTIVO DELLA TESITecniche comunication-saving nella comunicazione V2V

I veicoli sfruttano la connessione WiFi gratuita per:• Auto-organizzarsi dinamicamente in cluster• Aggregare i loro dati• Minimizzare le comunicazioni V2I (minimizzare i costi)

Auto-organizzazione delle OBU vicine in cluster:• Essenziale in questo ambiente ampiamente dinamico• I Cluster Member (CM) comunicano con il loro Cluster Head CH• I CH comunicano alla Centrale di Controllo• Le comunicazioni intra-cluster sono immediate (per esempio notifica di incidente)

Protocolli di aggregazione dinamica distribuita interne al cluster per stimare misure utili :• Non si assume un’infrastruttura di routing• Dynamic Counting• Distributed Averaging

OBIETTIVO: Studiare, implementare e valutare un nuovo algoritmo di clustering in grado di affrontare l’alta dinamicità della rete e cercare al tempo stesso una stabilità nei cluster

ALGORITMO ALLO STATO DELL’ARTE

Esempio Fase 1

A

B

C

D

E

F

0,9

0,6 0,5

0,1

0,2

G

H

0,3

0,2 0,8

I

0,5

L’agoritmo si base su due fasi:

Fase 1:Ogni veicolo generauna probabilita' casuale di elezionecome CH

Fase 2:1. I veicoli tramite la WiFi

scambiano la loro probabilita’2. Viene eletto CH ogni veicolo con

probabilita’ maggiore rispetto a tutti i suoi vicini, i quali diventano suoi CM

3. I veicoli isolati nel raggio WiFi diventano automaticamente CH


A

B

C

D

E

F

CH

CH CM di A CM di D

CM di D

FN 0,3

G

H

CM di H

FN 0,2 CH

I

CH

Esempio Fase 2


Fase 1:Ogni veicolo generauna probabilita' casuale di elezionecome CH






A

B

C

D

E

F

CH

CH CM di A CM di D

CM di D

FN 0,3

G

H

CM di H

FN 0,2 CH

I

CH

Esempio Fase 2

Possono essere presenti veicoliche non sono stati eletti ne’ CH ne’ CM

Quindi si ripete la seconda fase,finche ogni veicolo e’ CM o CH, cioe’:






Esempio RipetizioneFase 2

A

B

C

D

E

F

CH

CHCM di ACM di DCM di B

CM di D

CH

H

CM di HCM di FCM di B

CH CH

G I

CH

Possono essere presenti veicoliche non sono stati eletti ne’ CH ne’ CM

Quindi si ripete la seconda fase,finche ogni veicolo e’ CM o CH, cioe’:






Fase 1:Ogni veicolo memorizza il numero divicini visti nella portata WiFi e generauna probabilita’ casuale di elezionecome CH


scambiano la loro probabilita’2. Viene eletto CH ogni veicolo

che vede il maggior numero di vicini, e in caso di parita’ di veicoli visti, l’elezione si confronta con la probabilita’ maggiore, a seguire si eleggono i vari CM


ALGORITMO PROPOSTO

Esempio Fase 1

( 2 ; 0,6 )

A

B

C

D

E

F

( 1 ; 0,9 )

( 4 ; 0,5 )

( 2 ; 0,1 )

( 2 ; 0,2 )

G

H

( 3 ; 0,3 )

( 1 ; 0,2 )

( 1 ; 0,8 )

I

( 0 ; 0,5 )

ALGORITMO PROPOSTO

Esempio Fase 2

A

B

C

D

E

F

CM di C

CM di C CH

CM di C

CM di C CM di G

G

H

CH

CM di G

CM di G

I

CH


Fase 1:Ogni veicolo memorizza il numero divicini visti nella portata WiFi e generauna probabilita’ casuale di elezionecome CH


scambiano la loro probabilita’2. Viene eletto CH ogni veicolo

che vede il maggior numero di vicini, e in caso di parita’ di veicoli visti, l’elezione si confronta con la probabilita’ maggiore, a seguire si eleggono i vari CM


ALGORITMO PROPOSTOPossono essere presenti dei veicoliche non sono stati eletti ne’ CH ne’ CM,e come detto prima per l’algoritmo allo stato dell’arte, si risolvono ripetendo la seconda fase,finche ogni veicolo e’ CM o CH

In questo esempionon e’ sono presenti FN

Esempio Fase 2

A

B

C

D

E

F

CM di C

CM di C CH

CM di C

CM di C CM di G

G

H

CH

CM di G

CM di G

I

CH

ANALISI CMMCHDalla definizione degli algoritmi, e’ possibile che un CM sia assegnato a piu’ CHe viene quindi chiamato CMMCH (cluster member multi cluster head).

Questa situazione non deve esserci, perche’ contro la politica dicommunication-saving

Si usano le seguenti soluzioni

Algoritrmo allo stato dell’arte:

I CMMCH sono assegnati al CHcon probabilita’ minore

Esempio CMMCH presenti

CMMCH: CM di H CM di F CM di B

A

B

C

D

E

F

CH 0,9

CH 0,6

CMMCH: CM di A CM di D CM di B

CM di D

CH 0,3

H CH 0,2 CH 0,8

G I

CH 0,5




Algoritrmo allo stato dell’arte:

I CMMCH sono assegnati al CHcon probabilita’ minore

Esempio CMMCH risolti

A

B

C

D

E

F

CH 0,9

CH 0,6 CM di B

CM di D

CH 0,3

H

CM di F

CH 0,2 CH 0,8

G I

CH 0,5




Algoritrmo proposto:

I CMMCH sono assegnati al CHcon minor numerodi veicoli visti e conprobabilita’ minore

Esempio CMMCH presenti

A

B

C

D

E

F

CM di C

CM di CCH(4 ; 0,5 )

CM di C

CMMCH: CM di C CM di G

G

H

CH( 3 ; 0,3 )

CM di G CM di G

I

CH( 0 ; 0,5 )




Algoritrmo proposto:

I CMMCH sono assegnati al CHcon minor numerodi veicoli visti e conprobabilita’ minore

Esempio CMMCH risolti

A

B

C

D

E

F

CM di C

CM di C CH ( 4 ; 0,5 )

CM di C

CM di G

G

H

CH ( 3 ; 0,3 )

CM di G CM di G

I

CH ( 0 ; 0,5 )

SCENARIO DI RIFERIMENTOLa simulazione degli algoritmi e’ stata realizzata sulla mappa di Roma,in una variante del raccordo anulare, in Via Tiburtina nel tratto Via di Casal Bruciato Ponte Mammolo redattaa Perugia nel 1999:

• Durata della simulazione: 600 secondi

• Passo di simulazione: 0,5 secondi

Mappa studiata

I dati di partenza della mappa sono stati ottenuti dalmicrosimulatore VissimVISSIM:

Modello di microsimulazione dinamica della circolazione stradale, parte della linea di prodotti PTV Vision.

Mappa ottenuta da Vissim

SPERIMENTAZIONEPer poter testare il nuovo algoritmo proposto, si e’ creato un simulatore in Javaper interfacciarsi con la mappa di Vissim e implementare quindi gli algoritmi.

Portata WiFiDell’OBU

Il raggio e’ stato cambiato neivalori: 100 – 120 – 140 – 250 metri

Il simulatore in Java ha permesso di testare gli algoritmi al variare di:

Campionamentodella simulazione

Questo dato fisicamente corrisponde alla frequenza di scambio dati tra le OBU.Il campionamento e’ stato cambiato nei valori:0,5 – 1 – 2 – 4 – 8 secondiGlobalmente sono state effettuate 20 simulazioni differenti in

cui: Ogni simulazione ha generato 7 file Ogni file e’ costituito da anche piu’ di 1200 righe per 15 colonne

RISULTATI: campionamento 0,5 secondi e WiFi 100 metri

76%

24%

STABILITA' CM 1

AVG LIFE IN OTHERS CH 1 AVG LIFE IN ONE CH 1

34%

66%

STABILITA' DIMENSIONE CH 1

DIM CONSTANT CH AVG 1 DIM CHANGE CH AVG 1

Algoritmo proposto

Algoritmo allo stato dell’arte

88%

12%

STABILITA' CM 2

AVG LIFE IN OTHERS CH 2 AVG LIFE IN ONE CH 2

23%

77%

STABILITA' DIMENSIONE CH 2

DIM CONSTANT CH AVG 2 DIM CHANGE CH AVG 2

L’algoritmo proposto ha migliorato la stabilita’ dei cluster

Analisi globale

• Maggior tempo di permanenza di un CM nello stesso cluster

• Minor cambi di dimensione di un CH


Algoritmo proposto

Algoritmo allo stato dell’arte

35%

65%

PERCENTUALE DI CH "NUOVI E VECCHI" ELETTI AD OGNI PASSO

DELLA SIMULAZIONE

OLD CH 1

NEW CH 1

94%

6%

PERCENTUALE DI CH ISOLATI E NON PRESENTI AD OGNI PASSO DELLA

SIMULAZIONESTATE WITH OTHERS 1STATE LONELY 1

23%

77%

PERCENTUALE DI CH "NUOVI E VECCHI" ELETTI AD OGNI PASSO DELLA

SIMULAZIONE

OLD CH 2

NEW CH 2

92%

8%

PERCENTUALE DI CH ISOLATI E NON PRESENTI AD OGNI PASSO DELLA

SIMULAZIONE

STATE WITH OTHERS 2STATE LONELY 2

L’algoritmo proposto ha migliorato la stabilita’ dei cluster

Analisi globale

• Maggior numero di CH mantenuti dagli step precedenti

• Minor numero di CH isolati presenti ad ogni step


1 73 145 217 289 361 433 505 577 649 721 793 865 937 1009108111530

5

10

15

20

25

30

35

n CHs 1 n CHs LONELY 1n CHs 2 n CHs LONELY 2

STEP

N

1 73 145 217 289 361 433 505 577 649 721 793 865 937 1009108111530

5

10

15

20

25

30

35

NEW CHs 1 OLD CHs 1NEW CHs 2 OLD CHs 2

STEP

N

• Minor numero di CH eletti

• Minor numero di CH isolati eletti

Analisi lungo gli step di simulazione Continuita’ dell’algoritmo nella rete dinamica

ALGORITMO PROPOSTOALGORITMO ALLO STATO DELL’ARTE

ALGORITMO PROPOSTOALGORITMO ALLO STATO DELL’ARTE

• Minor numero di nuovi CH eletti ad ogni step

• Maggior numero di CH mantenuti dagli step precedenti

RISULTATI: al variare del campionamento e WiFi 100 metri

0.5 1 2 4 80

0.05

0.1

0.15

0.2

0.25

0.3

PERCENTUALE DI TEMPO DI PERMANENZA DI UN OBU NELLO STESSO CLUSTER

AVG LIFE IN ONE CH 1 AVG LIFE IN ONE CH 2

CAMPIONAMENTO

0.5 1 2 4 80

0.2

0.4

0.6

0.8

1

PERCENTUALE DI CH "NUOVI" ELETTI AD OGNI PASSO DELLA SIMULAZIONE

NEW CH 1 NEW CH 2

CAMPIONAMENTO

Vantaggi ridotti o annullatiall’umentare del campionamento

ALGORITMO PROPOSTO ALGORITMO ALLO STATO DELL’ARTE


RISULTATI: performance al variare del campionamento e della WiFi

0.5 1 2 4 80

0.2

0.4

0.6

PERCENTUALE DI MESSAGGI INVIATI PER LA VELOCITA' MEDIA NEI SEGMENTI RISPETTO ALL'ASSENZA DI ALGORITMI DI ELEZIONE

TOT SEND MESSAGES 1 TOT SEND MESSAGES 2

CAMPIONAMENTONUMERO DI MESSAGGI INVIATI V2I:SENZA ALGORITMO: 263094 131491 65685 32805 16329ALGORITMO 1: 112162 56207 28011 13965 6942ALGORITMO 2: 115386 57698 28901 14363 7156

100 120 140 2500

0.10.20.30.40.5

PERCENTUALE DI MESSAGGI INVIATI PER LA VELOCITA' MEDIA NEI SEGMENTI RISPETTO ALL'ASSENZA DI ALGORITMI DI ELEZIONE

TOT SEND MESSAGES 1 TOT SEND MESSAGES 2

WIFI

NUMERO DI MESSAGGI INVIATI V2I:SENZA ALGORITMO: 263094 263094 263094 263094ALGORITMO 1: 112162 106873 104988 95433ALGORITMO 2: 115386 109306 104538 92276

• Differenze minime tra l’algoritmo proposto e l’algoritmo allo stato dell’arte• Riduzione delle comunicazioni V2I di circa un 50%



CONCLUSIONI

Maggiore stabilita’ lungo la simulazione Maggiore stabilita’ al variare della portata WiFi Minor numero di comunicazioni V2I effettutate

SVILUPPI FUTURI Test di simulazione su scenari piu’ o meno estesi e diversificati (strade urbane, extrarbane, autostrade, congestioni di traffico, etc)

Implementazione nel simulatore di protocolli di aggregazione dinamica distribuita

GRAZIE A TUTTI PERL’ATTENZIONE

Introduzione progetto Pegasus e obiettivo della tesi Algoritmo proposto e stato dellarte Scenario di...

Documents

Transcript of Introduzione progetto Pegasus e obiettivo della tesi Algoritmo proposto e stato dellarte Scenario di...