POLITECNICO DI BARI Facoltà di Ingegneria

Corso di Laurea Magistrale in Ingegneria Informatica ______________________________________________________________

Tema d'anno di Grafi e combinatoria

Applicazione della teoria dei grafi e dei

codici correttori alle reti VANET

Relatore:

Chiar.ma Prof.ssa Bambina LARATO

Studenti:

Marco COLAPRICO Angelo Antonio SALATINO

______________________________________________________________

Anno Accademico 2010-2011

2 | P a g i n a

Sommario

Capitolo 1 – Teoria dei grafi ........................................................................................................................... 4

Introduzione ................................................................................................................................................... 4

Definizione di grafo ....................................................................................................................................... 6

Isomorfismo di grafi ...................................................................................................................................... 9

Sottografi ....................................................................................................................................................... 9

Grado di un vertice ...................................................................................................................................... 11

Nomenclatura .............................................................................................................................................. 12

Cammini ...................................................................................................................................................... 12

Alberi ........................................................................................................................................................... 16

Applicazioni sui grafi .................................................................................................................................. 18

Algoritmo di Dijkstra............................................................................................................................... 18

Algoritmo di Bellman – Ford .................................................................................................................. 20

Confronto di complessità computazionale............................................................................................... 22

Capitolo 2 - Teoria dei codici ........................................................................................................................ 23

Definizione di codice ................................................................................................................................... 23

Parametri di un codice ................................................................................................................................. 25

Capitolo 3 - Teoria dei codici correttori e rilevatori di errore .................................................................. 29

Introduzione alla teoria dei codici correttori ............................................................................................... 29

Codici ridondanti ......................................................................................................................................... 31

Decodifica di minima distanza e codici correttori ....................................................................................... 32

Codifica di un codice lineare ....................................................................................................................... 35

I codici di Hamming .................................................................................................................................... 43

Capitolo 4 – Analisi delle reti VANET ......................................................................................................... 45

Introduzione ................................................................................................................................................. 45

Storia delle reti VANET .............................................................................................................................. 46

Applicazioni utente ...................................................................................................................................... 46

Architettura di un nodo ................................................................................................................................ 47

Applicazione dei grafi sulle VANET .......................................................................................................... 47

Livello di rete per VANET .......................................................................................................................... 48

Distance Vector ....................................................................................................................................... 48

Scenario ....................................................................................................................................................... 48

Applicazione del codice Hamming (7, 4) alle reti VANET ........................................................................ 53

Primo metodo con operazioni logiche ..................................................................................................... 54

Secondo metodo con matrici G e H ......................................................................................................... 56

3 | P a g i n a

Progressi tecnologici ................................................................................................................................... 58

Bibliografia ..................................................................................................................................................... 59

Indice delle figure

Figura 1 - Esempio della struttura grafo ............................................................................................................ 4

Figura 2 - Mappa della città di Konigsberg ....................................................................................................... 5

Figura 3 - Mappa dei ponti e degli isolotti di Konigsberg ................................................................................. 5

Figura 4 - Grafo relativo ai ponti di Konigsberg ............................................................................................... 6

Figura 5 - Mappa della metropolitana di Londra ............................................................................................... 7

Figura 6 - Esempio di traduzione da un circuito in un grafo ............................................................................. 8

Figura 7 - Mappa dei maggiori aeroporti degli USA con relative linee aeree pesate ........................................ 8 Figura 8 - Esempio di grafi isomorfi ................................................................................................................. 9

Figura 9 - Esempio di un sottografo ................................................................................................................ 10

Figura 10 - Esempio di un sottografo indotto .................................................................................................. 10

Figura 11 - Esempio di un sottografo indotto da X ......................................................................................... 11

Figura 12 - Grado di un grafo .......................................................................................................................... 12

Figura 13 - Esempio di un cammino di un grafo ............................................................................................. 13

Figura 14 - Esempi di cammini: chiuso (sinistra), aperto (destra)................................................................... 13

Figura 15 - Esempio sulla differenza tra trail e path ....................................................................................... 14

Figura 16 - Esempio di ciclo ........................................................................................................................... 14

Figura 17 - Esempio di grafo per il calcolo della lunghezza ........................................................................... 15

Figura 18 - Differenza tra un grafo connesso e non ........................................................................................ 15

Figura 19 - Esempio di grafi aciclici e foresta ................................................................................................. 16

Figura 20 - Esempio 1 di spanning tree ........................................................................................................... 17

Figura 21 - Esempio 2 di spanning tree ........................................................................................................... 17

Figura 22 - Spanning tree creato con l'algoritmo di Kruskal ........................................................................... 18

Figura 23 - Schema di un sistema di comunicazione ...................................................................................... 29

Figura 24 - Canale binario simmetrico ............................................................................................................ 30

Figura 25 - Sfera di Hamming di centro x e raggio r....................................................................................... 33

Figura 26 - Esempio di decodifica di minima distanza ................................................................................... 33

Figura 27 - Reti VANET ................................................................................................................................. 45

Figura 28 - Segnalazione dovuta ad un veicolo d'emergenza .......................................................................... 46

Figura 29 - Inoltro di una notifica raccolta ...................................................................................................... 47

Figura 30 - Scenario di esempio per le VANET.............................................................................................. 49

Figura 31 - Scenario della sola rete VANET ................................................................................................... 49

Figura 32 - Grafo rappresentativo dello scenario ............................................................................................ 50

Figura 33 - Grafo dei cammini minimi per lo scenario analizzato .................................................................. 53

Figura 34 - Copertura dei bit di parità ............................................................................................................. 55

Figura 35 - Schema circuitale dell'encoder e del decoder per Ham(7, 4) ........................................................ 56

45 | P a g i n a

Capitolo 4 – Analisi delle reti VANET

Introduzione

Per evitare di incorrere in quello che esula dalla trattazione di questa tesina, si cercherà in questo capitolo di dare una breve e concisa descrizione sulle reti ed in particolare delle VANET, in modo da lasciare ampio spazio ad una trattazione puramente incentrata sui grafi.

Le reti veicolari ad-hoc (Vehicular Ad-hoc NETwork, VANET) sono un tipo di tecnologia emergente che sta trovando ampio spazio nella disciplina delle Telecomunicazioni. Questa rete si basa su tecnologia Wi-Fi tesa ad offrire ai veicoli la possibilità di scambio di informazioni di qualsiasi natura, i cui nodi, essenzialmente veicoli, sono caratterizzati da un'alta mobilità. Assumendo che i collegamenti fisici (onde radio) della rete possano formare dei lati, è possibile impiegare lo scenario su descritto in una struttura a grafo.

G = (V,E) con V uguale all’insieme dei veicoli e E l’insieme dei link fisici tra i nodi

Nella seguente figura è possibile apprezzare uno scenario delle applicazioni di questo tipo di reti:

Figura 27 - Reti VANET

Le reti VANET infatti sono una particolare tipologia di reti mobili ad-hoc (Mobile Ad-hoc NETwork, MANET). L’Internet Engineering Task Force (IETF) definisce cosi: “Una MANET é un sistema autonomo di router mobili e dei loro host associati, connessi con collegamenti di tipo wireless che sono uniti formando un grafo di forma arbitraria. Tali router sono liberi di muoversi casualmente e di auto organizzarsi arbitrariamente, sebbene la topologia wireless vari rapidamente ed in modo imprevedibile. Tale rete può operare da sola oppure essere connessa alla rete Internet”. Le reti VANET si differenziano dalle semplici reti MANET per l'alta mobilità dei nodi che causano cambiamenti topologici frequenti e radicali. Si può inoltre notare come il set di applicazioni candidate ad essere sviluppate per questa tecnologia (es. notifiche di incidenti stradali e informazioni sul traffico), oltre alle risorse disponibili (es. spettro di frequenze dedicato, ampia capacità energetica e di calcolo) e le limitazioni dovute allo scenario di sviluppo (es. dinamicità del flusso di traffico, vincoli di privacy), fanno delle VANET un’area distinta dell’ ambiente delle comunicazioni wireless. Negli ultimi dieci anni la ricerca su questa tecnologia ha subito una forte accelerazione dovuta ai possibili risvolti commerciali ed al probabile impatto sulla sicurezza stradale che le

46 | P a g i n a

VANET potrebbero avere. Ed è per questo che sono sorti negli anni numerosi comitati di sviluppo al fine di dare una spinta alla imminente standardizzazione dei protocolli e dei dispositivi concernenti le VANET [7].

Storia delle reti VANET

La storia dell’utilizzo delle comunicazioni radio per l’interazione tra veicoli o tra veicolo e infrastruttura stradale è fortemente tesa alla costituzione di un sistema di trasporto intelligente [8]. Numerosi progetti sono stati sviluppati da altrettanto numerosi enti, privati e statali, dall’inizio degli anni ’80 ad oggi. Già dalla fine degli anni ’60 furono sviluppati i primi sistemi di “automazione stradale” basati su onde radio, che hanno sottolineato come l’attenzione della ricerca con il passare degli anni, si sia spostata dall’egemonia delle esigenze di sicurezza verso la possibilità di ottenere servizi quali la navigazione assistita [8].

L’utilizzo di queste tecnologie si prefiggeva che oltre a ottenere in tempo reale le notizie relative a quello che accadeva sulla strada che si stava percorrendo, permetteva a sua volta la:

• Riduzione della congestione del traffico • Riduzione dell’emissione di gas di scarico dovuti al traffico • Prevenzione di incidenti stradali

• Miglioramento del ruolo sociale dell’automobile

Le comunicazioni vehicle-to-vehicle, cioè quelle destinate allo scambio di informazioni esclusivamente tra veicoli, giocarono però un ruolo dominante: molte delle ricerche prodotte allora [9] risultano attualmente ancora valide. L’interesse per le comunicazioni vehicle-to-vehicle continuarono a spingere le attività in Giappone e USA. La svolta si ebbe quando nel 1999 la FCC21 diede la possibilità di dedicare 75 MHz di banda intorno a 5.9 GHz per le comunicazioni a breve distanza, mettendo cosi a disposizione una fetta di frequenze per le comunicazioni tra i veicoli. Negli anni successivi numerosi furono gli standard prodotti. Solo nel 2004 però viene coniato, nell’ambito dell’ACM International Workshop on Vehicular Ad- hoc Networks a Philadelphia, per la prima volta il termine “VANET” [8].

Applicazioni utente

Ci sono applicazioni per la gestione del traffico rivolte a migliorarne il flusso, riducendo così sia la congestione, sia gli incidenti da essa risultanti. La gestione del traffico include anche il monitoraggio dello stesso, la gestione dei semafori, e l’instradamento dei veicoli d’emergenza (fig. 23).

Figura 28 - Segnalazione dovuta ad un veicolo d'emergenza

21FCC: US Federal Communication Commission è l’ente delle comunicazioni statunitense .

47 | P a g i n a

In particolare il monitoraggio è in grado di fornire informazioni tempestive e molto precise riguardo le condizioni del flusso veicolare anche a strade distanti parecchi chilometri: infatti ogni veicolo della rete VANET funge da sensore per la raccolta delle informazioni e da ripetitore per le notifiche (fig. 29).

Figura 29 - Inoltro di una notifica raccolta

La gestione dei semafori inoltre potrebbe essere fondamentale per lo smaltimento del traffico negli orari di punta in modo da creare percorsi ad alto scorrimento. Tuttavia, ci sono applicazioni di supporto alla guida che provvedono a fornire ai passeggeri dei veicoli informazioni locali, mappe e messaggi di tipo generico di validità limitata nello spazio e nel tempo. Ad esempio si pensi a informazioni utili come mappe aggiornate della zona, stazioni benzina, aree parcheggio o punti di interesse. Non di minore rilevanza sono però le cosiddette “comfort application” tese a dare servizi di intrattenimento ai passeggeri al fine di rendere il viaggio più piacevole. Questa classe di applicazioni può essere ad esempio spinta dall’esigenza dei passeggeri di comunicare tramite la rete Internet (si pensi ai client di instant messaging o ai social network) o di sfruttare la forte diffusione dei file multimediali nella rete.

Architettura di un nodo

Nelle reti VANET come d’altronde in un qualsiasi tipo di rete, un nodo è provvisto di un insieme di protocolli che regolano le trasmissioni dei dati. Evitando di cadere in troppi dettagli si dirà semplicemente che qualsiasi nodo di una qualsiasi rete ha come riferimento il modello ISO/OSI. Il modello appena citato, detto anche stack protocollare, è formato essenzialmente da sette livelli che vanno dal livello fisico ovvero il collegamento wireless nella fattispecie delle reti VANET, fino al livello applicazione dove incontriamo i software che regolano le applicazioni utente (descritte nel paragrafo precedente). Tutti gli altri livelli intermedi ad eccezione del livello di rete non saranno trattati per semplicità. Un nodo di una data rete si differenzia da un altro nodo esterno a tale rete perché implementa diversamente i sette livelli del modello OSI.

Applicazione dei grafi sulle VANET

Ripartendo dallo stack protocollare precedentemente descritto, vi è un livello tra tutti che fa più uso della teoria dei grafi, in quanto espleta il compito di instradamento dei dati. Si fa uso di questa teoria perché banalmente si pensi alla rete stessa come un grafo, formato dai veicoli come nodi e i collegamenti wireless come lati. In sostanza il livello dello stack protocollare, detto livello di rete, che si occupa dell’instradamento dei dati dovrà essenzialmente implementare delle tecniche basate sugli algoritmi di Bellman-Ford e Dijktra descritti nel capitolo precedente.

48 | P a g i n a

Livello di rete per VANET

A causa della natura dinamica della rete, trovare e mantenere percorsi di indirizzamento per i pacchetti è un compito a dir poco arduo. Molte, infatti, sono state le proposte per risolvere i numerosi problemi sorti nell'implementazione di protocolli che fossero efficienti per le VANET. Esse però possono essere classificate in cinque macro-gruppi: ad-hoc, position-based, cluster-based, broadcast e geocast. In questi gruppi rientrano tutt’una serie di protocolli differenti tra loro che ricoprono determinate esigenze. Si immagini che tra le esigenze ci siano, risparmio di energie, tempi ridotti, sicurezza, instradamento veloce ecc. Ai fini di questa tesina si provvederà a descrivere una tecnica utilizzata in molti protocolli detta Distance Vector il quale utilizza l’algoritmo di Bellman-Ford.

Anche se l’algoritmo di Dijkstra è più efficiente dell’algoritmo di Bellman-Ford, viene spesso usato il secondo perché non possiede vincoli troppo restrittivi sui costi del percorso.

Distance Vector

Il distance vector è una tecnica di instradamento basato sul vettore delle distanze, noto anche come routing di Bellman-Ford, ed è un tipo di algoritmo di routing dinamico.

Questa tecnica consiste essenzialmente nella trasmissione, da parte di tutti i nodi, di una tabella o vettore, contenente le connessioni che un nodo possiede in quel momento con gli altri nodi. In definitiva ogni singolo nodo, verifica le proprie connessioni, crea una tabella con un record per ogni connessione e la scambia con i propri vicini, aggiornando cosi la propria tabella. Questa operazione termina quando tutti i nodi hanno ricevuto tutte le tabelle. Inoltre le tabelle devono essere inviate periodicamente o quando c’è un cambio topologico della rete. In sostanza ogni nodo con lo scambio delle tabelle tende a conoscere la topologia della rete per cui, data la circostanza, è possibile utilizzare l’algoritmo di Bellman-Ford per il calcolo del percorso minimo [9].

Nella tabella di routing memorizzata da ogni nodo, per ogni record vi sono le seguenti informazioni:

• indirizzo IP del nodo destinazione (destination IP); • numero di sequenza del nodo destinazione (destination sequence number); • flag di validità della rotta (indica se la rotta è valida o invalida o in riparazione); • distanza in numero di hop (hop count); • lista dei precursori per quella rotta; • tempo di validità (lifetime).

Questa operazione comincia ad aver senso perché, si pensi che ogni nodo se deve trasferire un dato, deve innanzitutto sapere chi è connesso alla rete e deve anche conoscere la topologia della rete stessa affinché con l’algoritmo di Bellman-Ford, possa calcolarsi il percorso minimo e procedere poi con l’instradamento.

Il routing basato su Distance Vector risulta semplice dal punto di vista computazionale e non richiede grandi quantitativi di memoria. Tuttavia il protocollo richiede tempi più lunghi rispetto ad altri protocolli per stabilire una connessione tra due nodi di una rete [10].

Scenario

In questa parte dell’elaborato si procederà con una dimostrazione di un vero è proprio scenario in cui si necessità di comunicare attraverso questo tipo di reti. La seguente figura presenta un incrocio della quale si mostrerà, a titolo di esempio, come i dati passano da un veicolo ad un altro attraverso le considerazioni teoriche su descritte.

49 | P a g i n a

Figura 30 - Scenario di esempio per le VANET

Le linee gialle all’interno della figura mostrano i link wireless presenti tra i vari nodi (automobili), l’automobile gialla a sinistra possiede tre collegamenti di cui uno con l’auto blu e gli altri due con altre auto tagliate fuori dalla figura, per completezza verranno considerate nel grafo che rappresenta la rete. Andando ora a considerare solo le parti necessarie di questo scenario otteniamo la seguente figura:

Figura 31 - Scenario della sola rete VANET

La cui rappresentazione a grafo dello scenario proposto è:

50 | P a g i n a

Figura 32 - Grafo rappresentativo dello scenario

Senza ledere in generalità consideriamo che lo scenario proposto sia formato dai soli nodi mostrati, perché in generale i nodi facenti parte la rete sono in numero leggermente superiore, inoltre qui il peso di ogni lato è stato assegnato arbitrariamente mentre nella realtà viene calcolato a partire da una serie di fattori come velocità del veicolo, condizioni atmosferiche ecc.

Ripetendo le nozioni teoriche trattate nei precedenti paragrafi si ha che ogni nodo (veicolo) possiede uno stack protocollare formato da dei livelli. Tra i quali ritroviamo il livello fisico che è formato dal hardware che consente la connessione wireless, poi tra gli ultimi si trova il livello applicativo formato da una serie di utility e tra di essi vi è il livello di rete che implementa dei protocolli i quali usano il Distance Vector che a sua volta fa uso dell’algoritmo di Bellman-Ford per la risoluzione dei percorsi.

Alla base del grafo su mostrato, per poter definire un percorso minimo tra due nodi che si scambiano dati si dovrà necessariamente implementare la tecnica del Distance Vector.

STEP 1: Creazione delle tabelle da parte di tutti i nodi (S=Source, D=Destination, W=Weight).

Nodo 1 S D W

1 3 5

Nodo 2 S D W

2 3 3

Nodo 3 S D W

3 1 5

3 2 3

3 4 4

Nodo 4 S D W

4 3 4

4 5 6

4 6 5

Nodo 5 S D W

5 4 6

5 6 6

5 9 3

5 8 4

Nodo 6 S D W

6 5 6

6 4 5

6 7 2

Nodo 7 S D W

7 6 2

Nodo 8 S D W

8 5 4

Nodo 9 S D W

9 5 3

51 | P a g i n a

STEP 2: I nodi comunicano ai loro limitrofi le tabelle costruite.

Nodo 1 S D W

1 3 5

3 1 5

3 2 3

3 4 4

Nodo 2 S D W

2 3 3

3 1 5

3 2 3

3 4 4

Nodo 3 S D W

3 1 5

3 2 3

3 4 4

1 3 5

2 3 3

4 3 4

4 5 6

4 6 5

Nodo 4 S D W

4 3 4

4 5 6

4 6 5

3 1 5

3 2 3

3 4 4

5 4 6

5 6 6

5 9 3

5 8 4

6 5 6

6 4 5

6 7 2

Nodo 5 S D W

5 4 6

5 6 6

5 9 3

5 8 4

4 3 4

4 5 6

4 6 5

6 5 6

6 4 5

6 7 2

8 5 4

9 5 3

Nodo 6 S D W

6 5 6

6 4 5

6 7 2

4 3 4

4 5 6

4 6 5

5 4 6

5 6 6

5 9 3

5 8 4

7 6 2

Nodo 7 S D W

7 6 2

6 5 6

6 4 5

6 7 2

Nodo 8 S D W

8 5 4

5 4 6

5 6 6

5 9 3

5 8 4

Nodo 9 S D W

9 5 3

5 4 6

5 6 6

5 9 3

5 8 4

STEP 3: Eliminazione dei record doppioni, questa operazione ha senso perché il grafo si presenta in questo scenario non orientato, quindi sorgente e destinatario sono mutuabili.

52 | P a g i n a

Nodo 1 S D W

1 3 5

3 2 3

3 4 4

Nodo 2 S D W

2 3 3

3 1 5

3 4 4

Nodo 3

S D W

3 1 5

3 2 3

3 4 4

4 5 6

4 6 5

Nodo 4 S D W

4 3 4

4 5 6

4 6 5

3 1 5

3 2 3

5 6 6

5 9 3

5 8 4

6 5 6

6 7 2

Nodo 5 S D W

5 4 6

5 6 6

5 9 3

5 8 4

4 3 4

4 6 5

6 4 5

6 7 2

Nodo 6 S D W

6 5 6

6 4 5

6 7 2

4 3 4

4 5 6

5 4 6

5 9 3

5 8 4

Nodo 7 S D W

7 6 2

6 5 6

6 4 5

Nodo 8 S D W

8 5 4

5 4 6

5 6 6

5 9 3

Nodo 9 S D W

9 5 3

5 4 6

5 6 6

5 8 4

Proseguendo in avanti con lo scambio delle tabelle tra i vari nodi, al termine di tutte le iterazioni si avrà che ogni nodo presenta la seguente tabella:

Nodo 1,2,3,4,5,6,7,8,9 S D W

1 3 5

2 3 3

3 4 4

4 5 6

4 6 5

5 6 6

5 8 4

5 9 3

53 | P a g i n a

6 7 2

Dalla precedente tabella si comprende che ogni nodo conosce la topologia del grafo e considerando il caso in cui uno di essi necessita la trasmissione di un dato verso un altro nodo procederà quindi al calcolo del percorso minimo attraverso l’algoritmo più volte richiamato.

Si supponga per ipotesi che il nodo 1 voglia trasmettere un pacchetto al nodo 7, quindi si mostrerà la tabella dei pesi minimi:

Iterazione Nodo 1 Nodo 2 Nodo 3 Nodo 4 Nodo 5 Nodo 6 Nodo 7 Nodo 8 Nodo 9 h=0 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ h=1 0 ∞ 5 (1) ∞ ∞ ∞ ∞ ∞ ∞ h=2 0 8 (3) 5 (1) 9 (3) ∞ ∞ ∞ ∞ ∞ h=3 0 8 (3) 5 (1) 9 (3) 15 (4) 14 (4) ∞ ∞ ∞ h=4 0 8 (3) 5 (1) 9 (3) 15 (4) 14 (4) ∞ 19 (5) 18 (5) h=5 0 8 (3) 5 (1) 9 (3) 15 (4) 14 (4) 16 (6) 19 (5) 18 (5)

I valori tra parentesi tonde sono definiti come etichette ovvero il nodo precedente da cui attinge il calcolo del peso.

Dalla seguente tabella si ricava cosi il grafo delle etichette, ovvero l’albero dei cammini minimi:

Figura 33 - Grafo dei cammini minimi per lo scenario analizzato

Al di la del grafo dei cammini minimi appena mostrato, guardando la tabella, su il nodo 1 desidera trasmettere un dato verso il nodo 7, esso saprà che l’intero percorso ha peso uguale a 16 e risalendo a ritroso tra le iterazioni riesce a capire quali sono i nodi intermedi che il dato deve attraversare grazie alle etichette, p = 1,3,4,6,7.

Applicazione del codice Hamming (7, 4) alle reti VANET

Per l'applicazione esaminata la codifica di canale riveste un ruolo fondamentale perché il canale trasmissivo potrebbe essere facilmente affetto da rumore vista la sua natura, per cui è importante avere una codifica di canale che permetta la correzione degli errori. È necessario inoltre considerare un altro aspetto che riguarda il contesto applicativo: gli apparati a disposizione in questo tipo di applicazione non hanno grandi capacità computazionale (in termini di processore e memoria) per cui un codice che richiede operazioni onerose di codifica e decodifica renderebbe la comunicazione tra dispositivi nella rete estremamente lenta.

54 | P a g i n a

Per questi motivi si è optato per la scelta di Hamming (7, 4): un codice lineare, perfetto, in grado di correggere un errore e rilevarne due, per il quale è possibile implementare direttamente in hardware la codifica e la decodifica. In particolare, per questo codice è possibile implementare due possibili strategie di codifica/decodifica.

Primo metodo con operazioni logiche

Per il codice Hamming (7, 4), sfruttando lo schema in tabella 2 si ottengono le seguenti parole di codice:

d1 d2 d3 d4 p1 p2 d1 p3 d2 d3 d4 0 0 0 0 → 0 0 0 0 0 0 0

0 0 0 1 → 1 1 0 1 0 0 1

0 0 1 0 → 0 1 0 1 0 1 0

0 0 1 1 → 1 0 0 0 0 1 1

0 1 0 0 → 1 0 0 1 1 0 0

0 1 0 1 → 0 1 0 0 1 0 1

0 1 1 0 → 1 1 0 0 1 1 0

0 1 1 1 → 0 0 0 1 1 1 1

1 0 0 0 → 1 1 1 0 0 0 0

1 0 0 1 → 0 0 1 1 0 0 1

1 0 1 0 → 1 0 1 1 0 1 0

1 0 1 1 → 0 1 1 0 0 1 1

1 1 0 0 → 0 1 1 1 1 0 0

1 1 0 1 → 1 0 1 0 1 0 1

1 1 1 0 → 0 0 1 0 1 1 0

1 1 1 1 → 1 1 1 1 1 1 1

Tabella 4 - Parole del codice Hamming (7, 4)

Dalla tabella 1 si ricava che per Hamming (7, 4) vale che (la somma è applicata in GF(2) per cui 1 + 1 = 0): p1 = d1 + d2 + d4 p2 = d1 + d3 + d4 p3 = d2 + d3 + d4

La copertura dei bit di parità può essere definita dal seguente diagramma:

55 | P a g i n a

Figura 34 - Copertura dei bit di parità

Asserendo che il bit di parità 1 (p1) copre se stesso, il bit di dati d1, d2 e d4 vuol dire che esso è in grado di correggere un errore su uno di questi bit.

La parola p1 p2 d1 p3 d2 d3 d4 che giunge al destinatario deve essere codificata in modo da generare altri tre bit k1 k2 e k3 definiti come k1 = p1 + d1 + d2 + d4 k2 = p2 + d1 + d3 + d4 k3 = p3 + d2 + d3 + d4 e che individuano la posizione dell'errore secondo la tabella seguente:

k3 k2 k1 Significato Uscita Encoder 0 0 0 Nessun errore in ricezione 0000000

0 0 1 Errore nella posizione 1 (bit p1) 1000000

0 1 0 Errore nella posizione 2 (bit p2) 0100000

0 1 1 Errore nella posizione 3 (bit d1) 0010000

1 0 0 Errore nella posizione 4 (bit p3) 0001000

1 0 1 Errore nella posizione 5 (bit d2) 0000100

1 1 0 Errore nella posizione 6 (bit d3) 0000010

1 1 1 Errore nella posizione 7 (bit d4) 0000001

Tabella 5 - Bit per la decodifica

Questo tipo di codifica si presta molto bene ad un'implementazione circuitale estremamente veloce e semplice per via del fatto che richiede l'utilizzo delle sole porte logiche XOR. Un possibile schema hardware è il seguente:

56 | P a g i n a

Figura 35 - Schema circuitale dell'encoder e del decoder per Ham(7, 4)

Secondo metodo con matrici G e H

Le tre cifre di parità sono combinazioni diverse delle quattro cifre d’informazione nel seguente schema [6]: p1 = i2 + i3 + i4 p2 = i1 + i3 + i4 p3 = i1 + i2 + i4

che sono disposte in i1 i2 i3 i4 p1 p2 p3 per formare le 16 parole del codice:

i1 i2 i3 i4 i1 i2 i3 i4 p1 p2 p3 0 0 0 0 → 0 0 0 0 0 0 0

0 0 0 1 → 0 0 0 1 1 1 1

0 0 1 0 → 0 0 1 0 1 1 0

0 0 1 1 → 0 0 1 1 0 0 1

0 1 0 0 → 0 1 0 0 1 0 1

0 1 0 1 → 0 1 0 1 0 1 0

0 1 1 0 → 0 1 1 0 0 1 1

0 1 1 1 → 0 1 1 1 1 0 0

1 0 0 0 → 1 0 0 0 0 1 1

1 0 0 1 → 1 0 0 1 1 0 0

1 0 1 0 → 1 0 1 0 1 0 1

57 | P a g i n a

1 0 1 1 → 1 0 1 1 0 1 0

1 1 0 0 → 1 1 0 0 1 1 0

1 1 0 1 → 1 1 0 1 0 0 1

1 1 1 0 → 1 1 1 0 0 0 0

1 1 1 1 → 1 1 1 1 1 1 1

Tabella 6 - Parole del codice Hamming (7, 4)

In totale si utilizzano 2k = 16 delle 2n = 128 configurazioni di 7 bit. Si può verificare che le 15 parole non nulle contengono almeno tre uni, e quindi che le parole di codice differiscono in almeno tre posizioni. Quindi d = 3 e il codice può rivelare tutti gli errori semplici e doppi (ed altri di peso maggiore) ed è in grado di correggere tutti gli errori semplici: per la correzione basta cercare la parola che differisce in un solo bit da quella ricevuta.

Si può rappresentare la codifica nella forma c = i � G dove c è il vettore di 7 elementi trasmesso (parola di codice), i è il vettore di 4 elementi delle cifre d’informazione, G è la matrice generatrice di dimensione 4x7:

� � �1 0 00 1 000 00 100 0 10 1 001 11 11

1101� � ���

Le parole di codice sono tutte le combinazioni lineari delle righe della matrice generatrice. Le tre equazioni di parità riportate nel blocco X della matrice G sono c5 = c2 + c3 + c4 c6 = c1 + c3 + c4 c7 = c1 + c2 + c4

possono essere scritte come c � H = 0 dove H è una matrice 7x3 detta matrice di parità:

�������0 1 1111100

011010

101001������ � ����

Ricevuta la n-pla y = c + e dove e è il vettore errore, si calcola la sindrome s = y � H = c � H + e � H = e � H La sindrome è un vettore di n - k = 3 componenti, che dice se le tre regole di parità sono o meno soddisfatte. La sindrome può presentarsi in 23 = 8 modi, mentre le possibili configurazioni d’errore (inclusa la mancanza di errori) sono 27 = 128. Si verifica facilmente che la stessa sindrome corrisponde a 128/8=16 diverse configurazioni d’errore. Se il calcolo della sindrome s produce un vettore nullo vuol dire che la parola ricevuta è corretta, altrimenti sommando il coset leader, corrispondente alla sindrome ottenuta, alla parola ricevuta sarà possibile correggere l'errore. In questo, l'SDA(Standard Decoding Array) sarà così costituito:

Coset leaders u Sindrome u ���� H 0000000 000 1000000 011 0100000 101 0010000 110

58 | P a g i n a

0001000 111 0000100 100 0000010 010 0000001 001

Tabella 7 - SDA per il codice Hamming (7, 4)

Ad esempio, se la parola ricevuta è w = 1110000 allora w � H = 000 che è la sindrome di 0000000. Da ciò v = w + u = 1110000 + 0000000 = 1110000. Se la parola ricevuta è w = 1110001 allora w � H = 001 che è la sindrome di 0000001. Da ciò v = w + u = 1110001 + 0000001 = 1110000. La parola ricevuta è stata corretta.

Progressi tecnologici

Finora si è visto come si applica la teoria dei grafi sulle VANET grazie alla tecnica del distance vector. Tuttavia recenti ricerche hanno confermato ulteriori tecniche/protocolli innovativi che consentono la trasmissione dei dati tra veicoli con meno problemi, es. perdite di dati, scarsa sicurezza, ecc. Tra questi protocolli si contempla l’AODV ovvero Ad-hoc On-demand Distance Vector, che si basa sempre sul distance vector ma introduce nuovi meccanismi di interazione tra i nodi in modo da migliorare ulteriormente quello che il distance vector è in grado di offrire. Tuttavia degli studi e comparazioni su AODV dimostrano che questo algoritmo non è in grado di trovare rapidamente lunghi percorsi (path) di indirizzamento, né tantomeno di aggiornarli e mantenerli efficientemente. Per ridurre gli effetti deleteri dei continui cambiamenti di topologia l'AODV è stato modificato in modo tale da contenere algoritmi di previsione: nascono così PRAODV e PRAODVM [4]. Entrambi i protocolli utilizzano la posizione del nodo e la sua velocità per prevedere l'intervallo di tempo in cui il canale sarà attivo. Mentre PRAODV calcola un percorso alternativo prima che l'intervallo di vita stimato del canale scada, PRAODVM seleziona, tra i percorsi alternativi presenti, quello con la durata di vita stimata più alta. Un'altra modifica interessante all'AODV è quella che permette di inoltrare notifiche solo nelle zone di interesse (ZOR) [10], solitamente zone rettangolari o circolari: si pensi ad esempio, in uno scenario autostradale, in cui si deve inoltrare una notifica di incidente solo ai veicoli retrostanti nel proprio senso di marcia. In questo caso verrà data ai pacchetti una maggiore priorità (safety application), in modo che vengano trasmessi con il minor ritardo possibile.

Per quanto concerne la codifica di canale, in contesti applicativi reali si utilizzano altri tipi di codici come ad esempio i codici convoluzionali o i turbo codici in grado di correggere più di un errore e con elevate prestazioni in termini di tempo necessario per la codifica o la decodifica. Sebbene i primi sono già noti in letteratura, i turbo codici sono attualmente in fase di studio.

59 | P a g i n a

Bibliografia

[1] : Larato B. “Appunti del corso di Grafi e Combinatoria 2010/2011 di Colaprico e Salatino”

[2] : Bolla R., Caviglione L., Davoli F. “Appunti del corso di Reti di Telecomunicazioni, Lez. 31 - Tecniche di Instradamento”

[3] : De Giovanni L. “Appunti del corso di Ricerca Operativa, Cammini minimi: Algoritmi di Bellman-Ford e Dijkstra”

[4] : Hill R. “ A First Course in Coding Theory”, Oxford University Press

[5] : Mazzocca F. “Lucidi del corso di codici lineari”, Seconda Università degli Studi di Napoli - Corso di laurea in Matematica

[6] : Cauchi L., La Terra V., Grasso G., Gullo F. “Appunti di teoria dei codici”, Università di Catania - Facoltà di Ingegneria

[7] : Scavo G. “Modelli di mobilità nelle reti VANET”, Tesi di Laurea in Ingegneria Informatica – Politecnico di Bari, A.A. 2009/2010

[8] : Hartenstein, Laberteaux, “VANET: Vehicular Application and Inter-Networking Technologies”, Wiley edition, 2010

[9] : Grieco A., “Algoritmi e Protocolli di Routing”, Appunti del corso di Telematica 1, Politecnico di Bari, A.A. 2009/2010.

[10] : Li, Wang, “Routing in Vehicular Ad Hoc Networks: A Survey”, IEEE Vehicular Technology Magazine, 2007