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
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
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
ALGORITMO ALLO STATO DELL’ARTE
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
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
ALGORITMO ALLO STATO DELL’ARTE
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’:
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
ALGORITMO ALLO STATO DELL’ARTE
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 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
L’agoritmo si base su due fasi:
Fase 1:Ogni veicolo memorizza il numero divicini visti nella portata WiFi e generauna probabilita’ casuale di elezionecome CH
Fase 2:1. I veicoli tramite la WiFi
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
3. I veicoli isolati nel raggio WiFi diventano automaticamente CH
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
L’agoritmo si base su due fasi:
Fase 1:Ogni veicolo memorizza il numero divicini visti nella portata WiFi e generauna probabilita’ casuale di elezionecome CH
Fase 2:1. I veicoli tramite la WiFi
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
3. I veicoli isolati nel raggio WiFi diventano automaticamente CH
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
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 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
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 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 )
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 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 )
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
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
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
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
RISULTATI: campionamento 0,5 secondi e WiFi 100 metri
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
RISULTATI: campionamento 0,5 secondi e WiFi 100 metri
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
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%
ALGORITMO PROPOSTO ALGORITMO ALLO STATO DELL’ARTE
ALGORITMO PROPOSTO ALGORITMO ALLO STATO DELL’ARTE
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
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