CAPITOLO 4

CAPITOLO 4

Il ROUTING NELLE RETI VANET

Questo capitolo presenta una rassegna dei principali algoritmi di routing per lo scambio di messaggi tra veicoli di una VANET.

Il capitolo fornisce una breve introduzione al problema del routing e fornisce una classificazione originale degli algoritmi proposti in letteratura. Per ogni classe vengono poi selezionati e descritti in dettaglio gli algoritmi più significativi.

4.1 FATTORI DETERMINANTI NELLE COMUNICAZIONI DELLE VANET

Come abbiamo visto nel capitolo 2, una rete mobile ad-hoc[127] è un sistema autonomo di host connessi da link wireless. I vari host sono liberi di muoversi in maniera casuale cambiando dinamicamente la topologia della rete. Pertanto i protocolli di routing devono essere in grado di gestire questa alta mobilità cercando di trovare i percorsi migliori tra i vari nodi. La soluzione del routing oltre a considerare il fattore mobilità dei nodi deve considerare le seguenti caratteristiche:

• La limitatezza della banda di comunicazione. Si deve cercare di limitare i messaggi per il mantenimento della connessione dopo che essa è stata stabilita.

• Minimizzare la distanza del cammino tra due nodi. Ad esempio, un nodo può inviare un messaggio al nodo più lontano che ricade all'interno del raggio

d'azione della propria antenna, cercando così di eliminare alcuni instradamenti intermedi. Questa ottimizzazione è illustrata In figura 4.1.

• Individuare errori nelle comunicazioni. Devono essere presenti meccanismi automatici che possano individuare i frequenti errori nella comunicazione VANET. Partizionamenti di rete, errori nei link sono degli esempi di errori tipici. Il grafo in Figura 4.2 rappresenta una rete VANET in cui si è verificata un interruzione nella comunicazione tra il nodo S ed il nodo D. Successivamente è stata avviata automaticamente una procedura per informare il nodo origine S del problema.

• Ripristinare la connettività. Deve essere possibile ricreare in tempi rapidi, quando possibile, un cammino alternativo tra due nodi.

• Scegliere i percorsi in base alla posizione geografica (ottenuta da GPS) dei

Figura 4.2: Esempio di interruzione della comunicazione tra due nodi e attivazione di una procedura automatica per la comunicazione dell'errore al nodo mittente.

Figura 4.1: Esempi di attraversamento di un messaggio nella rete VANET. Nell'immagine a sinistra il messaggio attraversa tutti i nodi lungo un percorso che va dal nodo origine al nodo destinazione, nella seconda invece, il messaggio viene instradato direttamente al nodo più lontano tra quelli nel raggio di comunicazione della sorgente riducendo il numero di hop.

nodi mittente, destinatario ed intermedi.

• Attivare meccanismi automatici di riduzione del numero di messaggi ridondanti durante una comunicazione tra i nodi della rete.

4.2 MODELLO DELLE VANET

Tipicamente una rete VANET viene rappresentata attraverso un grafo non orientato in cui i nodi rappresentano i veicoli e gli archi astraggono la possibilità di comunicare tra due nodi. Nel seguito forniamo alcune definizioni che formalizzano questo modello e che forniscono un quadro unificante per la descrizione dei protocolli e degli algoritmi nel resto del capitolo.

Approfondimenti o ulteriori definizioni saranno riportati all'interno dei vari paragrafi se necessari.

Definizione 1: Grafo

Un grafo, G(N, A), è una coppia di insiemi: N è un insieme finito e non vuoto di elementi detti nodi, mentre A è un insieme finito di coppie di elementi distinti di N detti archi.

Definizione 2: Grafo non orientato

Un grafo non orientato G(N, A) è un insieme di nodi e archi dove l'arco i , j∈A ha lo stesso significato dell'arco  j , i∈A

Definizione 3: Grafo orientato

Un grafo orientato G(N, A) è un'insieme di nodi e archi dove l'arco i , j∈A è diverso dall'arco  j , i∈A

Definizione 4: Grafo pesato

Un grafo pesato è un grafo ai cui nodi e/o archi sono associati dei pesi. Tali pesi possono avere significati diversi a seconda del contesto.

Definizione 5: Grafo RNG

Dati un insieme di nodi con posizioni note, un grafo RNG è un grafo in cui un arco (u, v) esiste tra i nodi u e v se la distanza tra loro è minore o uguale alla distanza fra ogni altro vertice w e i vertici u e v sono lontani da w. In simboli:

∀

Definizione 6: GRAFO GG

Un arco (u, v) esiste tra due nodi u e v se non esiste un nodo w in un intorno circolare di diametro pari a d(u, v). In simboli:

∀

u , v [ d2

u , wd2

v , w ]

Definizione 7: Cammino

Un cammino in un grafo (non orientato) è una sequenza di nodi

v1,v2,... , vk∈N tali che vi, vi1∈ A , ∀ i=1, ... , k−1

Definizione 8: Distanza tra due nodi

Dati due nodi i e j, si definisce distanza fra i e j la somma dei pesi degli archi che si attraversano in un cammino P che va da i a j. In simboli:

di , j=

∑

u , v∈ Pij

du , v _{dove P}

ij è l'insieme degli archi del cammino dal nodo i

al nodo j.

Definizione 9: Cammino minimo tra due nodi (o Shortest path)

Si definisce cammino minimo dal nodo i al nodo j il cammino con minima distanza che intercorre tra i due nodi.

Definizione 10: Vicinato di un nodo

Dato un grafo G(N, A), si definisce vicinato del nodo i∈N, l'insieme

Definizione 11: Grafo planare

In teoria dei grafi si definisce grafo planare un grafo che può essere raffigurato in un piano in modo che non si abbiano spigoli che si intersecano. La figura 4.3 mostra un esempio di grafo planare.

Definizione 12: Ciclo in un grafo

Dato un grafo non orientato G(N, A). Un cammino 〈v0,v1,... , vk〉∈N forma un

ciclo se v0=vk e v1,v2,... , vk sono distinti.

Definizione 13: Grafo Aciclico

Un Grafo G(N, A) è detto aciclico o DAG se non ha cicli

Definizione 14. Grafo DAG Destination Oriented

Un DAG è considerato Destination Oriented se per ogni nodo i esiste un cammino che arrivi al nodo destinazione j ∀ i∈N ∃〈v0,v1,... , vj〉∈N

Una rete VANET può essere rappresentata da un grafo G(N,A) pesato. Gli archi sono interpretabili come i canali di comunicazione attraverso cui fluiscono dei messaggi. I pesi degli archi rappresentano usualmente i costi di comunicazione intesi come tempo di trasmissione dei messaggi. Ogni nodo della rete è costituito da un veicolo che ha la capacità di ricevere e inviare messaggi attraverso un'antenna. Inoltre ad ogni veicolo è associata una capacità decisionale e di calcolo. Si assume inoltre che, il costo computazionale sia trascurabile rispetto alle prestazioni della rete e delle comunicazioni tra nodi.

Su questo modello si definisce problema del routing nel seguente modo:

Definizione 15. Problema del routing

Si definisce problema del routing il problema di stabilire il cammino minimo fra una coppia di nodi del grafo che rappresenta una VANET in modo da minimizzare una opportuna metrica

Essenzialmente tutte le informazioni realistiche del problema del routing lavorano su un grafo dinamico e sono intrattabili. Per questo in letteratura sono state proposte diverse strategie di approssimazione, che saranno oggetto del resto di capitolo capitolo

4.3 IL ROUTING NELLE VANET

I protocolli di routing nelle reti tradizionali packet switched usano algoritmi di routing di tipo link-state o distance vector [20, 28]. Entrambi questi algoritmi permettono ai vari nodi di trovare il cammino più breve tra i propri vicini, in modo da poter raggiungere il destinatario del pacchetto tramite il cammino minimo o “shortest path”.

In base alla definizione del paragrafo precedente, lo “shortest path” è il cammino minimo tra due nodi in un grafo in cui la somma dei pesi (le distanze) degli archi associati ai nodi è minimizzato.

Tuttavia questi protocolli non si prestano alle caratteristiche delle reti ad-hoc perché richiedono una forte conoscenza della topologia della rete, ed inoltre comportano un alto numero di messaggi di controllo nelle comunicazioni[1].

Abbiamo già sottolineato che a causa della limitata banda nei link wireless il numero dei messaggi circolanti nella rete deve essere tenuto basso. Inoltre, l'alta velocità di variazione della topologia della rete mobile necessita una procedura di ricerca dei percorsi tra i nodi estremamente veloce [1].

In letteratura, molti studi sugli algoritmi di routing sono stati fatti tenendo conto della limitatezza della banda di comunicazione, cercando quindi di ridurre il numero di messaggi superflui che si scambiano in una comunicazione.

tipo distance vector; altri invece utilizzano la ridondanza di alcune informazioni di routing. Questi ultimi, mantengono esplicitamente più percorsi di routing in modo da avere diverse alternative in caso di cambiamento della posizione dei nodi[73, 60].

4.4 UNA CLASSIFICAZIONE DEGLI ALGORITMI DI ROUTING

In letteratura sono stati proposti numerosi protocolli di routing. Le categorie di routing possono essere classificate in base allo schema in figura 4.4.

I protocolli di routing Topology-based utilizzano informazioni sui link esistenti tra i nodi della rete per effettuare il routing.

I protocolli di routing Position Based richiedono informazioni sulla posizione fi­ sica dei nodi partecipanti disponibili. Questa posizione viene acquisita grazie a pac­ chetti di beacon1 _{che i nodi vicini periodicamente trasmettono.}

I protocolli Geografici sono dei protocolli di tipo reactive che cercano di sfrutta­ re le informazioni di localizzazione dei vari nodi (ottenute da GPS) per ridurre l'ove­ rhead nella fase di ricerca delle rotte.

Figura 4.4: Classificazione delle categorie di routing

Topology Based

Protocolli Position Based

4.5 PROTOCOLLI TOPOLOGY BASED

In base allo schema in figura 4.5, i protocolli Topology Based a loro volta si suddividono in:

Protocolli di routing di tipo Proactive: essi utilizzano strategie di routing

classiche come il distance-vector routing (es. DSDV [16]) o link-state routing (es. OLSR [17] e TBRPF [18]). Essi mantengono informazioni di routing su tutti i possibili percorsi nella rete anche se questi non sono correntemente in uso. Lo svantaggio principale di questi approcci è che il mantenimento dei percorsi non usati può occupare una parte consistente della banda disponibile nel caso in cui la topologia della rete cambi frequentemente [19]. Dato che la rete tra veicoli è estremamente dinamica questo genere di approcci può non dare buoni risultati è quindi non essere utile alle reti VANET.

Protocolli di routing di tipo Reactive: i protocolli di questo tipo (come DSR

[20, 72], TORA[21, 73] e AODV[22]) mantengono solamente i percorsi attualmente in uso riducendo il carico della rete nel caso in cui sono utilizzati solo alcuni sottoinsiemi di percorsi. È auspicabile che le comunicazioni tra macchine utilizzino solo un numero limitato di rotte, il routing di tipo reactive sembra quindi adeguato in questo genere di scenario. Nel seguito discuteremo in dettaglio un esempio di protocollo che usa un approccio di tipo reactive: DSR, che da precedenti studi [23] è risultato il migliore tra diversi protocolli di routing di tipo reactive a causa delle soluzioni che adotta.

Protocolli Ibridi (reactive e proactive): I protocolli ibridi sono protocolli che in

parte utilizzano routing di tipo Proactive e in parte utilizzano routing di tipo

Figura 4.5: Classificazione dei protocolli di routing Topology Based

Topology Based

Proactive

Reactive

Reactive. Tra questi ricordiamo i protocolli TORA, ZRP[26] e altri come (LANMAR[7]).

4.6 PROTOCOLLI DI TIPO PROACTIVE

I protocolli Proactive sono protocolli che cercano di mantenere il più aggiornate possibile lo stato delle tabelle di routing di tutti i percorsi possibili nella rete, anche in mancanza di un effettivo utilizzo di tutti i cammini.

Continuando a seguire lo schema in figura 4.5, è possibile definire una classificazione ulteriore dei protocolli proactive. La figura 4.6 riporta una classificazione dei protocolli proactive.

4.7 PROTOCOLLI DI TIPO LINK-STATE

In questo tipo di protocolli ogni nodo possiede e gestisce un proprio punto di vista nella topologia della rete, incluse le liste dei costi dei link in uscita. Per mantenere le liste dei costi aggiornate, ogni nodo invia in broadcast (flooding) il costo di ogni link dei propri vicini a tutti i nodi della rete. Questa operazione viene fatta ogni qualvolta che vi sia un cambiamento di costo dei link dei nodi.

Può accadere che qualche costo ricevuto da un nodo possa essere errato, ciò può essere causato dai ritardi (fisici) di propagazione dei pacchetti nelle comunicazioni, dal partizionamento della rete o anche da altri motivi.

Figura 4.6: Classificazione dei protocolli di routing Proacrtive

Link State Distance Vector Protocolli Proactive

Questi errori possono causare dei loop nella creazione di rotte tra i nodi, però tali loop durano solamente il tempo che i pacchetti impiegano ad attraversare il diametro della rete[49].

Se un nodo riceve l'informazione di avvenuto cambiamento di costo, aggiorna la sua lista e applica l'algoritmo Shortest Path di Dijkstra[27] per scegliere il prossimo nodo che inoltrerà il messaggio. In figura 4.7 sono rappresentati alcuni protocolli di tipo Link State.

4.7.1 Optimized Link State Routing(OLSR)

Nel protocollo OLSR[50, 48] ogni nodo inizialmente collabora con i propri vicini per costruire una tabella di routing che contiene tutti i cammini verso tutti i nodi esistenti in una rete.

I nodi, per mantenere aggiornate le proprie informazioni sulla topologia della rete, si scambiano dei messaggi periodicamente.

Questi messaggi sono di tipo Hello MID e TC. I messaggi di Hello vengono inviati periodicamente ed hanno il compito di rilevare i nodi vicini e comunicare informazioni di servizio.

Il flooding viene utilizzato per lo scambio delle informazioni sullo stato di tutti i collegamenti conosciuti ad ogni nodo, in modo da poter permettere la ricostruzione della topologia di rete. Per ottimizzare il flooding e ridurre il consumo di banda e numero di pacchetti viene utilizzato un sistema chiamato Multipoint Relaying (MPR).

Infatti se si usa il semplice broadcast ogni nodo riceve più volte lo stesso messaggio e più volte lo ritrasmette causando così un notevole overhead di rete e di conseguenza un notevole spreco di banda. Una ottimizzazione può essere effettuata

Figura 4.7: Esempi di protocolli di routing Link State

OSPF Link

State

OLSR TBRPF

attraverso la scelta di sottoinsiemi di nodi che possono ritrasmettere i messaggi inibendo gli altri nella fase di ritrasmissione. In figura 4.8 viene mostrata una trasmissione senza ottimizzazioni ed una ottimizzata (MPR). È evidente che nel grafo B le comunicazioni sono molte di meno.

Nel protocollo OLSR ogni nodo sceglie un sottoinsieme dei suoi vicini tale che ogni secondo vicino sia raggiungibile tramite questo sottoinsieme. È stato dimostrato nell'RFC[50] che il problema di effettuare tale scelta è NP-completo, nella sezione 8.3.1 sempre dello stesso RFC, viene descritto un algoritmo euristico per calcolare il sottoinsieme MPR.

Il sistema MPR viene utilizzato come metodo per la ritrasmissione dei messaggi, ogni nodo a sua volta utilizzerà tale sistema per ritrasmettere i messaggi. Il protocollo OLSR utilizza pacchetti UDP per l'invio di informazioni di controllo, ogni pacchetto può contenere più di un messaggio, proveniente da mittenti differenti, per meglio sfruttare il tempo di trasmissione.

Per evitare sincronizzazioni tra i nodi nella comunicazione ogni nodo deve aspettare un tempo casuale prima di iniziare una trasmissione. Infine ogni volta che si verifica un cambiamento nella topologia della rete viene applicato un algoritmo di shortest path [27, 74] per la ricostruzione della topologia della rete.

Figura 4.8: Esempio di comunicazione broadcast in una rete. In A è rappresentato il broadcast completo dove ogni nodo invia e riceve più volte lo stesso messaggio. In B è rappresentato il broadcast MPR dove il nodo centrale seleziona un sottoinsieme di vicini come MPR e solo questi possono effettuare ritrasmissioni dei messaggi. Come si nota da B, il numero delle comunicazioni è molto inferiore rispetto ad A.

4.7.2 Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)

Nel protocollo TBRPF[18] ogni nodo calcola un percorso minimo verso per ogni nodo della rete. Per ridurre il carico nella rete, ogni nodo trasmette ai propri vicini solo parti dell'albero dei percorsi che ha in possesso. Queste parti di alberi, che contengono sottocammini minimi tra nodi della rete, quando vengono ricevuti da un nodo i essi contribuiscono alla costruzione (o all'aggiornamento) della tabella dei cammini minimi di i verso tutti gli altri nodi della rete. I messaggi contenenti gli alberi dei cammini, vengono inviati periodicamente a tutti i nodi della rete.

4.7.3 Open Shortest Path First (OSPF)

Il protocollo OSPF[74, 55, 56] è un protocollo di routing di tipo Link State. Negli algoritmi di tipo link-state, ciascun nodo costruisce un grafo complessivo della rete e poi, a partire da questo, tramite l’algoritmo di Dijkstra, costruisce la routing-table (la tabella dei percorsi per ogni nodo).

Nel protocollo OSPF i nodi inviano periodicamente ai propri vicini dei pacchetti di tipo hello. Questi pacchetti hanno il compito di verificare quali nodi vicini sono raggiungibili e attivi e quali no. Grazie ad essi ciascun nodo acquisirà una visione parziale della rete potendosi costruire così una mappa di informazioni topologiche parziale.

Successivamente, i nodi attraverso i pacchetti di tipo “Link State Packet update” si scambiano questi grafi parziali inviandoli a tutti i nodi della rete.

Al completamento di questa operazione tutti i nodi avranno acquisito una visione globale della rete attraverso la somma delle mappe parziali che via via i nodi ricevono. Questo grafo globale viene memorizzato all'interno di un database LSP (Link state packet) replicato su tutti i nodi.

Se si verificano modifiche nella topologia della rete, queste vengono propagate all'intera rete per garantire la sincronizzazione del database dello stato dei collegamenti su ciascun nodo. Al momento della ricezione delle modifiche, ogni nodo deve ricalcolare la tabella di routing. Per effettuare ciò viene impiegato il

classico algoritmo di Dijkstra. In figura figura 4.9 viene mostrato un esempio di costruzione di una tabella di routing utilizzando i dati contenuti nel database.

Per il calcolo dei percorsi della tabella di routing, il protocollo OSPF utilizza l'algoritmo SPF (Shortest Path First)[28]. SPF calcola il percorso più breve, corrispondente al costo minimo, tra il nodo e tutte le reti del sistema. I percorsi calcolati tramite SPF non non sono soggetti a nessun loop.

Il principale vantaggio del protocollo OSPF è la sua efficienza, infatti questo protocollo comporta un sovraccarico minimo della rete, anche se viene applicato in sistemi di reti molto estesi. Il principale svantaggio invece consiste nella sua complessità. Infatti, l'aumento della dimensione del database LSF comporta inevitabilmente un aumentano dei requisiti di memoria richiesta e l'aumento della frequenza del calcolo dei cammini. Per risolvere tale problema, OSPF suddivide la rete in aree, creando insiemi di reti contigue, connesse tra loro tramite un'area detta backbone. In questo modo, ogni nodo gestisce un database dello stato dei collegamenti per le aree connesse al nodo. I nodi di confine area connettono anche l'area backbone alle altre aree. Per avere una riduzione nella quantità di informazioni di routing circolanti nella rete OSPF consente l'utilizzo di aree di stub. Un'area di stub può contenere un unico punto di entrata e di uscita (un solo nodo di confine area) o più nodi di confine area, quando uno qualsiasi dei nodi può essere utilizzato per raggiungere destinazioni di route esterne.

Figura 4.9: Esempio di applicazione dell'algoritmo di Dijkstra su un grafo. Nella prima colonna della tabella a destra sono riportati i nodi del grafo, nelle altre invece i costi che ogni nodo deve sostenere per raggiungere un altro nodo.

A G E C D B F 2 3 1 2 1 9 2 A B/2 B A/2 D/3 E/2 C D/1 D B/3 C/1 G/1 E B/2 F/9 G/9 F E/9 G D/1 E/2

4.8 PROTOCOLLI DISTANCE-VECTOR

In questo tipo di protocolli, ogni nodo j, per ogni nodo destinazione i, mantiene un insieme di distanze o costi d_jk ,i dove, k è l'insieme dei vicini di i. Il nodo k viene trattato come il nodo successivo al quale sarà destinato il pacchetto, per i, se

d_jk , i=min ∀ k {djk , i}.

Affinché le distanze tra i nodi restino aggiornate, ogni volta che si ha un cambiamento della distanza minima tra una coppia di nodi, la nuova distanza minima viene diffusa ai nodi vicini. Se infine la distanza minima verso un vicino muta, il processo viene ripetuto nuovamente. Questo è il tipico comportamento dell'algoritmo distribuito di Bellman-Ford[106]. L'algoritmo di Bellman-Ford è soggetto alla creazione loop di messaggi tra i nodi, loop che possono essere a breve o a lunga durata. Inoltre possono verificarsi anche problemi di tipo “counting-to-infinity” ossia può accadere che l'algoritmo di Bellman-Ford [29] crei un enorme numero di messaggi per stabilire se un nodo risulti irraggiungibile. In letteratura sono stati proposti molti protocolli per evitare i loop a lunga durata ed evitare il problema del “counting-to-infinity”. Generalmente, questi algoritmi cercano di risolvere i problemi di counting utilizzando tecniche di coordinamento tra nodi e aumentando il numero di informazioni scambiati tra nodi. La figura 4.10 riassume i protocolli Distance Vector.

4.8.1 Distributed Update Algorithm (DUAL)

Il protocollo DUAL[75, 31, 54] è un protocollo in cui vi è una differenziazione del tipo di messaggi. I messaggi possono essere di tre tipi: update, queries e replies.

Figura 4.10: Esempi di protocolli di routing distance vector

DSDV EXBF RIP DUAL Distance Vector

A tutti i messaggi è associato un identificatore univoco. I messaggi queries e updates contengono inoltre una lista aggiornata di tutte le entry. Le entry sono dei messaggi che contengono un ID univoco, un ID del nodo destinatario e la minima distanza per raggiungerlo.

Un messaggio reply viene inviato a tutte le liste di update che si effettuano in una query.

Ogni nodo nella rete gestisce una tabella di routing, una tabella di query-origin, una tabella per lo status dei messaggi di reply ed infine una tabella della topologia di rete.

Definizione 16 Nodo attivo/passivo

Un nodo i è attivo rispetto ad un nodo destinazione j se sta aspettando una risposta dai suoi vicini riguardo j altrimenti è passivo. Se un nodo i è attivo rispetto ad un nodo j non può modificare il suo successore s nel cammino verso j all'interno della tabella di routing. Inoltre, la distanza d(i, j) deve essere uguale a d(s, j)+l(s) dove l(s) è un vettore di costi per s.

Al tempo t, la entry nella tabella di routing del nodo i, per il nodo destinazione j, contiene l'id del nodo j, l'attuale distanza d(i, j), il nodo successore s nell'attuale cammino (i , j) e la distanza d(s, j) prima che il nodo i diventi attivo. Se il nodo j non è raggiungibile dal nodo i allora il successore diventa NULL.

Tutti i nodi selezionano i vicini in base alla loro posizione, cercando di minimizzare il costo verso ogni destinazione. Il costo verso il nodo i è dato dalla seguente formula:

ci=l [ x ]d [ x , j]

dove il vettore l[x] contiene il costo dei link tra il nodo locale e ogni vicino x, mentre d[x, j] è la distanza da ogni vicino x al nodo destinazione j.

Per quanto riguarda la selezione dei percorsi, se ad un nodo arriva un messaggio update di l[k] o di d[k,j] e vale la seguente condizione:

l ' [ k]d ’[k , j]l [ x]d [x , j]

(dove l'apice indica il valore dopo l'aggiornamento) allora k diventa il prossimo hop e tale informazione viene annunciata ai vicini.

Se invece arriva un messaggio di update dove non vale la condizione precedente allora non si ha nessun cambiamento sulla determinazione dei percorsi.

Definizione 17 Condizione di accettazione

Si consideri un nodo passivo i che, al tempo t' , ha come suo successore verso j il nodo F e che d(i, j)< ∞. Si consideri anche che al tempo t > t' il nodo i individua un cambiamento in d_i F , jl  F . Il nodo i può scegliere come suo nodo successore qualunque vicino q∈Ni per cui:

d_iq , j=min {di x , j l  x : x∈Ni}∞ e diq , j≤di F , j

Definizione 18 Successore accettabile

Un successore accettabile per il nodo i al tempo t nel cammino verso il nodo j è un nodo vicino q∈Ni che soddisfa la condizione di accettazione.

Se l'insieme dei nodi vicini accettabili non risulta vuoto, si seleziona il vicino k che minimizza la distanza:

l[k] + d[k,j]

Se invece risulta essere vuoto allora viene attivato un processo detto diffusion, un processo in cui la route entry per la destinazione j viene temporaneamente congelata (perché non aggiornabile).

Successivamente viene inviato un messaggio di query a tutti i vicini eccetto x (in quanto nodo che ha inviato l'update). La query contiene la distanza congelata (

d , l ’[ x]d ’[ x , j]_{), in modo da ottenere la distanza nuova}d ’[ k , j] _{per ogni} vicino k. d è la distanza non aggiornata ossia la distanza prima dell'aggiornamento.

I nodi che si trovano nello stato passivo e che hanno un successore accettabile, inviano il messaggio di reply e rimangono nello stato passivo, se invece non hanno nessun successore accettabile passano nello stato attivo ed inviano un messaggio di query ai propri vicini.

I nodi che si trovano nello stato attivo e che ricevono una query da nodi non successori inviano il messaggio di reply e rimangono nello stato attivo.

Se ad un nodo arriva un messaggio di reply ad una query dai propri vicini, passa nello stato passivo e invia tale messaggio al nodo che ha iniziato il processo di query. In base alla dimostrazione[75] DUAL assicura dei percorsi senza loop, i nodi mantengono informazioni sul costo richiesto per raggiungere i vicini e utilizza sempre le rotte meno costose cambiando eventualmente rotta se il costo la rotta aumenta.

4.8.2 Extented Bellman Ford (EXBF)

Il protocollo EXBF[32] implementa l'algoritmo classico di Bellman Ford mantenendo sul nodo j oltre all'insieme delle distanze d_jk ,ianche un insieme di nodi N_jk , iossia l'insieme dei nodi che precedono il nodo destinazione i, nel percorso che va da j a i attraverso il nodo vicino, k.

In questo modo il nodo origine i è in grado di ricostruire l'intero percorso sino al nodo destinatario utilizzando N_jk , icome nuova destinazione.

Questo protocollo non è soggetto a problemi di loop a lunga durata e non ha problemi di counting-to-infinity se ogni nodo evita di inviare aggiornamenti del cambiamento delle rotte ad un vicino per una destinazione d e se il vicino fa parte del percorso diretto a d.

In questo protocollo in definitiva, se un link fallisce o avviene una riconnessione, il costo dei link viene ricalcolato, se invece la distanza minima viene modificata, il nuovo valore viene fornito ai nodi vicini.

4.8.3 Destination Sequenced Distance Vector (DSDV)

adeguamento del protocollo Distance Vector(DV) alle reti MANET.

In questo protocollo nelle tabelle di routing dei nodi vengono memorizzate tutte le possibili destinazioni raggiungibili da un nodo e tutti i relativi costi.

In DSDV è un'estensione dell'algoritmo distribuito di Bellman-Ford con in più un meccanismo di aging dei percorsi che consiste nell'etichettare ogni distanza tra due nodi i e j d_jk ,icon una sequenza numerica. Tale sequenza, associata ad ogni nodo, permette di effettuare una distinzione tra un percorso vecchio ed uno nuovo tra i nodi.

L'aggiornamento delle tabelle di routing dei nodi avviene in due differenti modi il time driven e il event driven. Nel timer driven i nodi inviano periodicamente le loro tabelle ai nodi vicini per mantenerle consistenti. Nell'aggiornamento event driven invece, un nodo invia la sua tabella di routing se si verificano cambiamenti nella topologia della rete.

La sequenza numerica associata ai nodi viene incrementata ogni volta che un nodo invia un aggiornamento ai vicini e poi viene distribuita in tutta la rete attraverso i messaggi di aggiornamento. La destinazione contenuta nella sequenza viene utilizzata come parametro indicativo di aggiornamento della rotta.

Per quanto riguarda le entry nelle tabelle di routing, ad ogni entry è associato un numero di sequenza. Un numero dispari indica che un nodo risulta essere irraggiungibile, i numeri pari invece vengono utilizzati dai nodi destinazione per contraddistinguere gli aggiornamenti dei percorsi. Infatti, i nodi aggiornano i percorsi usando gli aggiornamenti provenienti dalle destinazioni.

Le entry nelle tabelle vengono aggiornate solo se il numero di sequenza dell’aggiornamento del percorso risulta essere maggiore di quello già presente in tabella o se il numero di sequenza risulta essere lo stesso ma il percorso ha una metrica migliore.

Per quanto riguarda la cancellazione delle entry, essa avviene se non arrivano informazioni sul percorso per più di un certo numero di intervalli di aggiornamento.

Caratteristica di questo protocollo è che i percorsi la cui metrica è pari ad∞ vengono informati senza ritardi. Invece per i nodi con metrica diversa da∞viene applicato un ritardo basato sul settling time medio. Con questa tecnica viene evitato l’invio di aggiornamenti riguardanti i percorsi instabili, i quali verranno rimpiazzati

con percorsi migliori in futuro.

Per il calcolo del settling time medio i nodi utilizzano una tabella contenente entry formate da: l’indirizzo di destinazione, l’ultima misurazione del settling time, il settling time medio per la destinazione.

Gli aggiornamenti dei percorsi vengono inviati periodicamente e in caso di cambiamenti della topologia della rete.

4.8.4 Routing Information Protocol (RIP)

Il protocollo RIP[58, 57] è un protocollo di tipo Distance Vector nato per favorire lo scambio di informazioni di routing all'interno di in un sistema autonomo.

In questo protocollo, nall'inizio, nella tabella di routing di ciascun nodo sono presenti solo le entry relative alle reti che sono fisicamente connesse ed esso. Un nodo RIP invia ai propri vicini periodicamente degli annunci contenenti le entry della propria tabella di routing, in modo da segnalare agli altri nodi RIP locali le reti che possono raggiungere tramite esso.

I nodi RIP possono inviare informazioni di routing attraverso degli aggiornamenti. Questi aggiornamenti avvengono quando si verifica una modificata nella topologia di rete e vengono inviate informazioni di routing aggiornate in base a tali modifiche. In situazioni del genere, non occorre attendere il successivo annuncio periodico per l'invio del messaggio di aggiornamento, che viene spedito immediatamente.

Se ad esempio un nodo rileva un errore a livello di collegamento, aggiorna la propria tabella di routing e invia il messaggio contenente le rotte aggiornate. Tutti i nodi che ricevono questo messaggio di aggiornamento modificano le proprie tabelle di routing e propagano a loro volta le modifiche.

Una caratteristica di questo protocollo consiste nella sua facilità di configurazione e implementazione. Il principale svantaggio invece, consiste nel non adattamento di tale protocollo a sistemi di rete estesi.

I nodi usando RIP possono utilizzare un massimo di 15 hop, se esistono ulteriori reti oltre il 15esimo hop, vengono considerate irraggiungibili.

In genere i sistemi di rete tendono ad estendersi nella dimensione. I nodi RIP effettuano gli annunci periodici, tali annunci, se effettuati in grandi sistemi comportano un eccessivo traffico di rete da parte dei nodi.

Il protocollo RIP soffre inoltre di un tempo di ripristino elevato in caso di modifiche nella topologia. Infatti, quando viene modificata la topologia, la configurazione dei nodi RIP può necessitare diversi minuti prima che venga completata la riconfigurazione per la nuova topologia. In questi minuti si possono formare dei cicli di routing che possono comportare perdite o mancati recapiti dei dati.

4.9 CLASSIFICAZIONE DEI PROTOCOLLI DI TIPO REACTIVE

I protocolli di tipo Reactive On Demand gestiscono solo le rotte necessarie. Se si ha la necessità di una nuova rotta che arrivi ad un destinatario viene attivata una procedura di ricerca globale. Tutti gli algoritmi che utilizzano il Flooding fanno parte della classe Reactive On Demand. Al contrario dei protocolli Link State e Distance Vector, (che mantengono le rotte verso tutte le potenziali destinazioni) l'overhead di rete di questi protocolli non è eccessivamente alto. La Figura 4.11 mostra due protocolli Rective On Demand, il DSR[72] ed il AODV[35, 72, 137].

4.9.1 Il protocollo Dynamic Source Routing (DSR)

Il protocollo Dynamic Source Routing (DSR) [35, 72, 137] è un protocollo di routing di tipo reactive, progettato specificatamente per uso nelle reti ad-hoc senza wireless multi-hop con nodi mobili. L'uso di questo protocollo rende la rete

4.11 Esempi di protocolli di tipo Reactive

DSR AODV Reactive

(modellata come grafo G(N, A) orientato) completamente auto-organizzazione e auto-configurante. I nodi di rete cooperano tra loro per l'invio dei messaggi. Fattori come la mobilità dei nodi, interferenze, connessioni, sconnessioni ed altro, vengono automaticamente determinati e gestiti dal protocollo.

Dato che i nodi v_i∈N in un cammino 〈v0,v1,... , vk〉∈N sono variabili nel

tempo per effetto della mobilità dei nodi, la topologia risultante del grafo G(N, A) associata alla rete può velocemente cambiare.

In questo protocollo il nodo mittente i determina l'intero cammino 〈vi, ... , vj〉

per raggiungere il nodo destinatario j, ossia determina la completa sequenza di nodi attraverso i quali inoltrare i pacchetti e poterli consegnare al nodo destinatario.

Le principali fasi del protocollo sono la Route Discovery e la Route Maintenance:

● Route Discovery: La route discovery è un meccanismo con cui un nodo S che desidera trasmettere un pacchetto ad un nodo destinazione D ottiene un cammino 〈vs,... , vd〉 per poterlo inviare. La route discovery è usata

soltanto quando un nodo S tenta di trasmettere un pacchetto ad un nodo D e non conosce un cammino per D.

● Route Maintenance: La route maintenance è un meccanismo con cui il nodo origine S può rilevare cambiamenti nella topologia della rete e quindi nel cammino 〈vs,... , vd〉 che lo collega al nodo destinatario D. Questi

cambiamenti sono determinati da errori di comunicazione negli archi del cammino. Quando la route maintenance individua un errore, il nodo S può utilizzare un altro cammino per raggiungere D oppure invocare nuovamente la procedura di Route Discovery per cercare un nuovo cammino.

La Route Discovery e la Route Maintenance funzionano in maniera On demand. In particolare, DSR non richiede l'invio di pacchetti periodici a nessun livello della rete. Ad esempio, DSR non usa pacchetti di beacon, (controllo della condizione del collegamento) o pacchetti periodici di rilevazione del vicinato. Per la natura interamente On Demand e per la mancanza di attività periodica, nel protocollo DSR si ha una riduzione drastica nell'overhead di rete specie in situazioni in cui i nodi sono stazionari e i cammini tra loro sono stati scoperti.

Se un nodo che ha effettuato una route discovery viene successivamente a conoscenza di nuovi cammini alternativi per una destinazione, può memorizzarli in una propria cache. Questo rende DSR più reattivo ai cambiamenti topologici della rete poiché, in caso di fallimento di un cammino, un nodo può provarne altri memorizzati nelle cache dei vari nodi intermedi. L'utilizzo delle cache inoltre riduce il numero di richieste di route discovery e quindi riduce ulteriormente l'overhead di rete.

Le operazioni di Route Discovery e Route Maintenance in DSR lavorano su grafi orientati. La necessità dell'uso di grafi orientati è dovuta al fatto che (i, j)≠(j, i), infatti se i è raggiungibile da j non è sempre vero il viceversa ciò a causa delle diverse caratteristiche nella propagazione del segnale.

Una caratteristica di DSR è quella di avere un supportp per l'internetworking tra le differenti tipi di reti wireless permettendo così di creare un cammino tra nodi che usano differenti tipi di rete. Ad esempio, nella rete possono coesistere nodi dotati di antenne con raggio di trasmissione piccolo e nodi dotati di antenne con raggio di trasmissione sia piccolo che grande. Nel grafo G(N, A) possono quindi trovarsi nodi “Gateway” che oltre ad essere semplici nodi della rete ad-hoc possono anche avere accesso ad Internet.

Il protocollo Route Discovery del DSR

Nel momento in cui un nodo S genera un pacchetto destinato ad un nodo D, inserisce nell'header del pacchetto un cammino 〈vs,... , vd〉 cioè una sequenza di

nodi che il pacchetto dovrebbe attraversare per arrivare al nodo D. Normalmente dalle cache dei vari nodi, S è in grado di ottenere un cammino valido per D, se però, nelle cache non viene trovato nessun cammino, allora il DSR avvia una fase di Route Discovery in modo da trovare dinamicamente un nuovo cammino per D. In questo caso il nodo S prende il nome di initiator e il nodo D di target. In figura 4.12 è rappresentato un esempio di Route Discovery dove un nodo A è in attesa di un cammino per raggiungere E. In figura A effettua una Route Discovery e comunica a B la volontà di voler instaurare una comunicazione con E. B non avendo in cache un

percorso per E inoltra tale richiesta al nodo C inserendo però all'interno dell'header il nodo A e se stesso. Questo procedimento va avanti sino al raggiungimento di E.

Per iniziare una Route Discovery il nodo A invia in “broadcast locale” un messaggio di tipo ROUTE REQUEST. Il broadcast locale consiste nel ricevimento del messaggio solo dai nodi che si trovano all'interno dell'area di copertura dell'antenna del nodo A. La ROUTE REQUEST contiene il nodo che ha iniziato la Route Request, il nodo destinazione, un request id determinato dal nodo initiator e la lista dei nodi che il pacchetto ROUTE REQUEST ha finora attraversato. Tale lista originariamente è inizializzata a NULL dal nodo che effettua la Route Request.

Quando un nodo riceve una ROUTE REQUEST, se il nodo è il target della Route Discovery, allora invia un messaggio di ROUTE REPLY al nodo initiator che ha effettuato la Route Discovery, restituendo così una copia del cammino finora ottenuto a partire dal nodo che ha effettuato la ROUTE REQUEST.

Quando il nodo initiator riceve la ROUTE REPLY memorizza il cammino contenuto in esso per usarlo in futuro. Se un nodo k che ha ricevuto un messaggio di ROUTE REQUEST da parte del nodo initiator lo riceve nuovamente o vede che nell'header del messaggio di ROUTE REQUEST che riceve è presente il suo id, allora lo scarta. Nel caso in cui non vale nessuna di queste condizioni, il nodo k inserisce nell'header del messaggio il suo id e la sua posizione geografica ritrasmettendolo in broadcast e lasciando inalterato il request id.

In figura 4.12, quando al nodo E arriva il messaggio di ROUTE REQUEST, essendo E il nodo target, risponde con un messaggio di tipo ROUTE REPLY utilizzando come cammino verso A il cammino contenuto nell'header del messaggio di ROUTE REQUEST.

Figura 4.12: Esempio di Route Discovery del protocollo DSR. In figura il nodo A è il nodo

Il protocollo Route Maintenance del DSR

Supponiamo che un nodo S che generi per D. Il messaggio deve essere rilanciato attraverso un insieme di nodi intermedi ed ogni nodo è responsabile del recapito del messaggio al suo successore nella rotta. Ad esempio in figura 4.13 il nodo A che ha generato un messaggio per E è responsabile del suo recapito a B, il nodo B è responsabile per il recapito del messaggio a C, il nodo C è responsabile per il recapito del messaggio a D, ed infine D è responsabile per il recapito finale.

Una conferma di ricezione nel DSR può essere data a costo zero se si usa un protocollo MAC di tipo IEEE 802.11 oppure se si adotta il “passive Acknowledgement”. Il passive Acknowledgement consiste nell'ascoltare le trasmissioni del nodo successivo e quindi intuire se tale nodo ha ricevuto il mesasggio. Un esempio di passive Acknowledgement applicato alla figura 4.13 può essere il seguente: il nodo B conferma che C ha ricevuto il pacchetto che B gli ha inviato quando sente C che invia lo stesso pacchetto a D e così via sino a raggiungere la destinazione.

Se un pacchetto viene ritrasmesso in un arco (i, j) per un certo numero di volte non arriva nessuna conferma di ricezione dal destinatario j allora il nodo i restituisce al nodo che ha originato il messaggio, un pacchetto di tipo ROUTE ERROR. Questo messaggio conterrà l'arco su cui si è verificato l'errore di trasmissione.

Ad esempio, nella figura 4.13, se la C non è in grado di inviare il pacchetto al nodo seguente D, allora C restituisce un messaggio di ROUTE ERROR al nodo A, riportando l'errore di collegamento nell'arco (C, D).

Alla ricezione del messaggio di ROUTE ERROR, il nodo A rimuove l'arco (C, D) dalla propria cache. Inoltre per potere effettuare la ritrasmissione del messaggio ad E o effettuare una nuova trasmissione verso E, A deve comunque usare un

Figura 4.13: Esempio di Route Maintenance: Il nodo C non è in grado di inoltrare il pacchetto di A e destinato ad E tramite l'arco (C, D)

cammino alternativo. Tale cammino può già essere presente nella cache di A. Se in cache non è presente nessun altro cammino, allora A è costretto ad attivare una nuova Route Discovery verso il nodo E.

Sono possibili numerose ottimizzazioni nel protocollo DSR, una ad esempio potrebbe essere quella di mettere i nodi della rete in modalità “Promiscuos Mode” così da far captare tutto il traffico delle trasmissioni passanti attorno ai nodi dando la possibilità ai nodi di individuare nuovi percorsi.

Tutte le ottimizzazioni hanno lo scopo di ridurre sia il numero di pacchetti circolanti nella rete, rendere più efficiente la comunicazione tra i nodi e ridurre il numero di Route Discovery.

4.9.2 Ad-hoc On Demand Distance Vector AODV

Il protocollo AODV[35] è una variazione di tipo On Demand dei protocolli di Distance Vector. In questo protocollo i nodi che non fanno parte di un cammino attivo tra due nodi i, j non partecipano alla formazione dei percorsi e non partecipano a periodici scambi di messaggi per l'aggiornamento delle tabelle di routing. Inoltre, in AODV, un generico nodo i non si fa carico di trovare e poi mantenere un cammino 〈v0,v1,... , vj〉 verso il nodo j sino a quando non ha necessità di

comunicare con il nodo j. Il nodo i deve però partecipare al routing se fa parte di un cammino 〈u0,u1,... , ui,... , uk〉∈N che colleghi due nodi distinti. I vicini di un

nodo possono essere scoperti con le usuali modalità, ad esempio inviando messaggi di hello in broadcast. Una caratteristiche di AODV è che le tabelle di routing dei nodi delle rete vengono ottimizzate offrendo così risposte veloci in caso di richieste di creazione di nuovi cammini. Gli obiettivi principali del protocollo AODV sono:

● Inviare in broadcast pacchetti di Discovery solo quando strettamente necessari

● Distinguere la gestione dei vicini di un nodo e la gestione generale della topologia della rete

● Disseminare informazioni di cambiamento dei cammini solo ai nodi interessati.

Il protocollo AODV, come DSR, utilizza una procedura di Route Discovery, ma a differenza di DSR (che crea un cammino a partire dal nodo mittente sino al nodo destinatario) la creazione di un cammino avviene dinamicamente basandosi sui percorsi locali dei nodi intermedi. Questa caratteristica di dinamicità fa avere a AODV un overhead di rete basso specie se usato in reti con numerosi nodi.

Per il mantenimento delle informazioni sui cammini, AODV usa il concetto dei destination sequence numbers introdotti dai DSDV (sez. 4.8.3). A differenza di DSDV però, ogni nodo della rete mantiene un sequence number crescente e utilizza tale parametro per effettuare sostituzioni di vecchi cammini con cammini aggiornati nelle cache dei nodi.

La combinazione di queste due tecniche permette al protocollo AODV di essere efficiente nell'utilizzo della banda di rete, rende rapide le sue risposte ai cambiamenti della topologia ed evita la creazione di cammini ciclici tra nodi. In figura 4.14 viene rappresentato un esempio di comunicazione tra due nodi tramite AODV. Le varie fasi del protocollo sono spiegate nei paragrafi seguenti.

Il protocollo di Path Discovery di AODV

In AODV il Path Discovery inizia quando un nodo i vuole instaurare una comunicazione con un nodo j ma non ha a disposizione nella propria tabella di routing un cammino per raggiungerlo. In questo protocollo ogni nodo mantiene due contatori distinti, il node_sequence_number e il broadcast_id. Un nodo inizia un Path Discovery inviando in broadcast ai propri vicini un pacchetto di route request

Figura 4.14: Esempio di comunicazione tra due nodi tramite AODV. Il nodo S vuole iniziare una comunicazione con il nodo D

denominato RREQ. Tale pacchetto è costituito dai seguenti campi:

< source_addr, source_sequence_#, broadcast_id, dest_addr, dest_sequence_#, hop_cnt > La coppia <source_addr, broadcast_id> identifica univocamente un messaggio RREQ, dest_addr indica l'indirizzo del nodo destinatario, dest_sequence_# il destination sequence number ed infine hop_cnt indica il numero di hop finora attraversati. Il valore di broadcast_id viene incrementato ogni volta che un nodo origine emette un nuovo messaggio RREQ.

Ogni nodo vicino che riceve il pacchetto di RREQ e che è in grado di rispondere a tale richiesta con un cammino valido sino al nodo destinazione, invia un messaggio di route reply denominato RREP, se invece non è in grado di rispondere, ritrasmette in broadcast il messaggio RREQ incrementando però il valore hop_cnt contenuto nel suo interno.

È possibile che un nodo della rete possa ricevere più volte un messaggio di broadcast dai suoi vicini. Se un nodo riceve un messaggio RREQ che ha ricevuto in precedenza, lo scarta e non effettua nessun rebroadcast. Un nodo che non è in grado di soddisfare il messaggio di RREQ tiene comunque traccia delle informazioni contenute nel messaggio per poi usarle successivamente nella costruzione del reverse path setup (la costruzione dei cammini inversi). Allo stesso modo, se il nodo che ha ricevuto un messaggio RREQ è in grado di fornire un percorso verso il nodo destinazione, salva comunque delle informazioni e trasmette un messaggio di reply RREP. In figura 4.15 è rappresentato il passo del protocollo AODV in cui il nodo S genera i messaggi RREQ e li invia ai propri vicini.

Figura 4.15: Esempio di comunicazione tra due nodi tramite AODV. Il nodo S genera un pacchetto di tipo RREQ contenente l'ID e l'indirizzo del nodo destinazione D con associato un numero di sequenza

Il protocollo di Reverse Path Setup di AODV

Questo protocollo ha il compito di costruire i cammini inversi durante a formazione di un cammino verso un nodo destinazione. In un messaggio RREQ ci sono due numeri di sequenza, il source_sequence number e il last_destination sequence number. Il primo è usato per mantenere aggiornati i cammini inversi verso il nodo origine, il secondo invece indica quanto recente deve essere un cammino verso il nodo destinazione affinché possa essere accettato dal nodo origine.

Per la costruzione del reverse path, (ossia la costruzione dei cammini inversi), ogni nodo memorizza l'indirizzo del nodo da cui ha ricevuto la prima copia del messaggio RREQ. I cammini inversi devono essere mantenuti almeno per il tempo necessario affinché RREQ attraversi la rete e produca un messaggio RREP per il nodo origine. In figura 4.16 è rappresentata la fase di costruzione del Reverse Path.

Figura 4.16: Esempio di comunicazione tra due nodi tramite AODV. Al ricevimento di un pacchetto RREQ, ogni nodo setta un percorso verso il nodo sorgente S e inoltra il pacchetto RREQ ai propri vicini.

Il protocollo di Forward Path Setup di AODV

Se un messaggio di tipo RREQ arriva ad un nodo che è in possesso di un cammino che arrivi al nodo destinazione richiesto in RREQ, tale nodo prima controlla se il messaggio RREQ è stato ricevuto su un canale bidirezionale. Se un nodo intermedio ha un cammino per il nodo destinazione allora controlla se il cammino in suo possesso è quello correntemente in uso. Questo controllo viene

effettuato confrontando il destination_sequence_number del suo cammino con quello contenuto nel messaggio RREQ.

Se il destination_sequence_number del messaggio RREQ è maggiore di quello associato al cammino in suo possesso, allora non può usare il suo cammino quindi non può rispondere al messaggio RREQ. In tal caso effettuerà un ulteriore rebroadcast del RREQ ai suoi vicini.

Il nodo intermedio può rispondere ad un messaggio RREQ solamente quando è in possesso di un cammino valido verso il nodo destinazione richiesto e tale cammino avere un destination-sequence_number maggiore di quello contenuto nel RREQ. In questo caso, il nodo (in maniera unicast), risponde al nodo da cui ha ricevuto il primo RREQ inviando un messaggio RREP. In figura 4.17 è rappresentata questa fase del protocollo.

Figura 4.17: Esempio di comunicazione tra due nodi tramite AODV. Il percorso è reso disponibile da D tramite l'invio un maniera unicast di un pacchetto RREP lungo il percorso inverso. Al ricevimento di un RREP ogni nodo aggiorna la tabella di routing se il numero di sequenza è più recente.

Un messaggio RREP contiene le seguenti informazioni:

< source_addr, dest_addr, dest_sequence_# , hop_cnt, lifetime >

Il campo source_addr indica la posizione del nodo sorgente di una comunicazione, il campo dest_addr indica la posizione del nodo destinazione, il campo hop_cnt indica il numero di hop ed infine il campo lifetime indica la durata di validità del messaggio.

creazione di un reverse path cioè un cammino inverso che va dall'ultimo nodo della rete che ha ricevuto il RREQ sino ad arrivare al nodo origine. Inoltre, visto che il messaggio RREP inviato da un nodo intermedio o direttamente dal nodo destinatario deve attraversare il cammino verso il nodo origine, ogni nodo che fa parte di questo cammino setta un puntatore verso il nodo da cui ha ricevuto il messaggio di RREQ aggiornando i cammini nelle loro tabelle.

Quando un nodo intermedio che riceve un messaggio RREP, lo inoltra verso il nodo origine. Se successivamente lo stesso nodo riceve un nuovo messaggio RREP, allora controlla il dest_sequence_# ed il valore del hop_cnt associati al nuovo RREP. Se il destination sequence number del nuovo RREP è maggiore del destination sequence number del RREP precedente ed inoltre il valore del hopcount del nuovo RREP è inferiore, allora il nodo aggiorna i suoi cammini e propaga il nuovo RREP all'indietro verso il nodo sorgente del cammino. Tutti gli altri RREP che via via riceve e che non soddisfano queste condizioni, vengono eliminati. L'eliminazione dei pacchetti RREP ridondanti riduce notevolmente il traffico di rete scaturito dal protocollo.

Il nodo origine può iniziare una comunicazione con il nodo destinazione solo dopo aver ricevuto il primo pacchetto RREP dato che solo da quel momento in poi, i due nodi hanno un cammino valido che li connette. In figura 4.18 è rappresentata la fase finale del protocollo AODV in cui i due nodi S e D hanno un cammino che li collega.

Figura 4.18: Esempio di comunicazione tra due nodi tramite AODV. La connessione tra i nodi S, D è stata stabilita

La gestione delle tabelle di routing in AODV

Le tabelle di routing dei nodi della rete, oltre a contenere il destination_sequence_number contengono anche altre informazioni utili associate ai vari cammini. Ad esempio, ad ogni reverse path della tabella è associato un timer chiamato route_request_expiration_timer. Lo scopo di questo timer è quello di eliminare le reverse path contenute nelle tabelle dei nodi che non partecipano alla formazione di un cammino tra un nodo origine ed uno destinazione. Il valore di questo timer varia in base alla dimensione della rete. Un altro parametro importante contenuto nelle tabelle di routing è il route caching timeout il quale ha il compito di invalidare i cammini dopo un certo periodo di non utilizzo.

Inoltre, nelle entry delle tabelle è mantenuto anche l'indirizzo dei nodi vicini “attivi” dai quali ha ricevuto i pacchetti da inoltrare successivamente. Un vicino è considerato attivo per una data destinazione, se origina o inoltra almeno un pacchetto per quella destinazione entro un periodo active_timeout. Infine, un entry nella tabella di routing è considerata attiva se è usata da un qualche vicino attivo.

I cammini nelle tabelle di routing sono contrassegnati con i destination_sequence_number, i quali, garantiscono di evitare la formazione di cicli. Ogni nodo, nella propria tabella di routing, mantiene una entry per ogni nodo destinazione a cui è interessato. Queste entry sono formati dai seguenti dati:

● Destinazione ● Prossimo Hop

● Numero di hops (la distaza)

● Sequence_number per la destinazione ● Nodi vicini attivi per questo cammino

● Expiration time per la entry della tabella di routing.

Ogni volta che viene usata una entry della tabella di routing per inviare un messaggio da un nodo origine ad uno destinazione, il route caching timeout associato viene azzerato.

nodo confronta il destination_sequence_number del nuovo cammino con quello presente nella sua tabella. Se il destination_sequence_number del nuovo cammino è minore di di quello in suo possesso, allora lo scarta, altrimenti lo sceglie. In caso di valori uguali, la scelta del percorso è determinata dalla distanza dei cammini, infatti viene scelto cammino con distanza minore.

Path Maintenance in AODV

Lo spostamento dei nodi che non fanno parte di un cammino v_1,v_2,... , v_j non ha nessun effetto al cammino tra i due nodi sorgente e destinazione. Se invece il nodo sorgente v₁ si sposta durante una comunicazione, v₁ può rieffettuare una Route Discovery per ristabilire un nuovo cammino con v_j.

Se invece si muovono sia il nodo sorgente v₁ che il nodo destinatario v_j che i nodi intermedi v_2,... , v_kcon k j , cambiando quindi la topologia del cammino, allora ai nodi v1,v2,... , vj viene inviato uno speciale messaggio RREP.

Messaggi hello periodici possono essere utilizzati per determinare errori negli archi (i, j). In un cammino se vengono rilevati errori di collegamento tra due nodi i e j all'interno di un cammino, il nodo i, seguendo il cammino all'inverso, propaga l'informazione ai nodi attivi un messaggio di tipo RREP unsolicited con un sequence number maggiore dell'ultimo RREP che ha ricevuto. Il valore del sequence number rende il messaggio RREP unsolicited il più aggiornato tra tutti i messaggi RREP. I nodi che successivamente ricevono questo messaggio, a loro volta lo ripropagano ai propri vicini attivi e così via. Questo processo continua fino al raggiungimento del nodo sorgente.

Quando un nodo sorgente riceve un messaggio di tipo Route Error RERR che notifica l'avvenuto errore di collegamento nel cammino, può iniziare nuovamente una fase di Discovery e ricostruire quindi un nuovo cammino valido per il nodo destinazione. In figura 4.19 viene rappresentata la fase in cui si verifica un errore nel collegamento tra i nodi (f, j) del cammino che collega i nodi S e D.

Figura 4.19: Esempio di comunicazione tra due nodi tramite AODV. Dopo essersi creato un errore di collegamento nell'arco (f, j), il penultimo nodo che ha individuato l'errore diffonde ai propri vicini tramite un pacchetto RERR l'interruzione. I nodi che hanno nelle proprie tabelle di routing un cammino che include l'arco (f, j), al ricevimento di RERR, invalideranno il cammino.

4.10 CLASSIFICAZIONE DEL PROTOCOLLI DI TIPO IBRIDO

I protocolli ibridi sono protocolli che in parte utilizzano routing di tipo Proactive e in parte utilizzano routing di tipo Reactive. In figura 4.20 sono rappresentati alcuni protocolli ibridi.

Tra i vari protocolli ibridi, nei paragrafi successivi verranno approfondi in particolare il protocollo ZRP e TORA.

4.10.1 Zone Routing Protocol ZRP

ZRP[39, 40, 41] fa parte della famiglia dei protocolli ibridi infatti combina un approccio di tipo proactive ed uno di tipo reactive.

In questo protocollo, ogni nodo gestisce con algoritmi di tipo proactive i cammini verso i nodi all'interno di una regione locale chiamata “routing zone”.

Se un nodo vuole iniziare una comunicazione con un altro nodo all'interno della

Figura 4.20: Esempi di protocolli ibridi

TORA ZRP Protocolli Ibridi Altri (LANMAR)

sua regione, il calcolo del percorso tra i due nodi viene effettuato con un algoritmo di tipo proactive, se invece vuole comunicare con un nodo all'esterno della propria zona il percorso viene calcolato con un algoritmo reactive.

Questo protocollo si distingue per le buone performance nelle grandi reti con nodi interni con differenti mobilità, nelle piccole sottoreti (dette zone) oppure nei cluster di nodi. Si distingue inoltre per il fatto che supporta gli indirizzi IP nonché i messaggi ICMP (messaggi di controllo e test attraverso le reti del IP).

La dimensione delle routing zone nel protocollo ZRP è fissata in base alla frequenze delle richieste di calcolo o dalla mobilità

Grandi zone sono utili nelle reti in cui si hanno alti numeri di richieste di cammini tra i nodi e gli spostamenti dei nodi sono lenti, piccole zone sono invece utili per reti con bassi numeri di richieste di cammini e con nodi che hanno spostamenti veloci. ZRP utilizza due protocolli:

• IARP (IntraZone Routing Protocol) di tipo proactive. Questo protocollo ha il compito di assicurare che ogni nodo all'interno di una routing zone possieda una tabella di routing consistente e che tale tabella venga aggiornata periodicamente. Le informazioni contenute al suo interno sono necessarie per poter effettuare la ricerca di tutti i nodi all'interno della zona.

La routing zone di un nodo x è definita come l'insieme dei nodi che hanno distanza da x minore o uguale ad un parametro



=2.

Affinché un nodo possa costruire una routing zone è necessario che conosca i suoi vicini, ossia i nodi raggiungibili con percorsi lunghi un hop. L’identificazione dei vicini può essere effettuata attraverso l'uso del protocollo NDP (Neighbour Discovery Protocol)[34].

L'associazione o la dissociazione di un nodo in una routing zone è un evento importante per la routing zone stessa. Quest'evento viene gestito dal protocollo IARP il quale opererà solamente nella zona interessata, senza comunicarlo ad altre zone il cui evento ha scarso valore. In tal modo non appesantirà la rete.

• IERP (InterAzone Routing Protocol) di tipo reactive. Questo protocollo svolge due compiti, il primo è quello di effettuare ricerche di nodi in altre zone, il secondo è quello di ricercare un percorso per raggiungere di una specifica destinazione.

La ricerca di un percorso viene effettuata dai nodi posizionati sui bordi di una zona, detti border node, i quali reperiscono le informazioni riguardanti i nodi in altre zone. Il reperimento di tali informazioni avviene tramite l'invio di messaggi dai border node ai nodi posizionati all'interno di altre zone.

IERP fa uso di un altro protocollo, il BRP (Bordercast Resolution Protocol) che viene rappresentato il suo funzionamento in figura 4.22.

BRP invece che inoltrare una route query da vicino a vicino, permette di inoltrare tale query verso i nodi periferici non ancora raggiunti. Quando un nodo A riceve una route query da B, A marca come coperti tutti i nodi che fanno parte della routing zone di A e di B. Completato ciò, passa alla creazione di un albero di bordercast che ha come radice se stesso (A). L'albero conterrà tutti i nodi periferici ancora non coperti dalla route query. Alla fine sarà compito di A segnalare l'avvenuta copertura dei nodi periferici. Viste le caratteristiche di BRP, le operazioni compiute dal protocollo IERP sono molti simili a quelle di un qualsiasi protocollo di route discovery. Il mittente crea un pacchetto di richiesta di comunicazione indicando in esso

Figura 4.21: Esempio di routing zone del nodo S con=2. Il nodo K fa parte della routing

zone di S perché può essere raggiunto con percorsi di lunghezza 2. Il nodo L non fa parte

della routing zone in quanto non raggiungibile con percorsi di lunghezza 2. I nodi periferici in questo caso sono sono G, K, H, T, J.

l'ID del nodo che vuole contattare, dopodichè invia il pacchetto ad un sottoinsieme di nodi determinato dal protocollo BRP.

Quando un nodo riceve di una richiesta di comunicazione (route request), se è a conoscenza di un cammino verso il nodo destinazione risponde con un messaggio (route reply) contenente il cammino, se invece non ne è a conoscenza utilizzerà a sua volta il protocollo BRP per inoltrare la route request ad altri nodi.

4.10.2 Temporally Ordered Routing Algorithm TORA

Il protocollo di routing TORA[73] (Temporally-Ordered Routing Algorithm) è un protocollo di routing dotato di alta adattabilità e di conseguenza adeguato alle caratteristiche delle reti VANET.

Una delle caratteristiche principali di TORA è il mantenimento di rotte multiple verso i nodi destinazione. Avere diversi percorsi che raggiungono il nodo destinazione permette al protocollo di evitare reazioni ad ogni minimo cambiamento nella topologia di rete. Il protocollo reagisce solamente quando tutte le rotte verso un nodo destinazione D sono invalidate.

TORA prende come modello di rete una rete rappresentata da un Grafo G(N, A)

aciclico (o DAG) e usa una nozione di “altezza” per mantenere il grafo di tipo Destination Oriented. L'altezza di un nodo è intesa come la distanza d(i, j) dal nodo destinazione. Ogni nodo possiede un valore altezza che scambia con ogni suo vicino. Il significato dell'altezza implica la direzione dell'arco (i, j), infatti, un arco è sempre diretto dal nodo alto verso il nodo basso. In figura 4.23 è rappresentata un'illustrazione concettuale di un grafo aciclico Destination Oriented formato dai nodi e dalle loro altezze. Da notare in figura che i cammini vanno sempre verso altezze di valore minore ed esistono diversi cammini alternativi per il raggiungimento del nodo destinazione.

Il protocollo TORA lo utilizza tre funzioni di base:

● Creazione dei percorsi: La creazione dei percorsi a partire da un nodo i ∈ N sorgente richiede la creazione di una sequenza ordinata di nodi che va dal nodo i al nodo destinazione D∈ N. Questa funzione viene effettuata quando un nodo senza collegamenti diretti verso altri nodi richiede un percorso per un nodo destinazione D (tipo on Demand). La creazione dei percorsi corrisponde all'assegnamento di nuove altezze verso nuovi parti del grafo G(N, A) rappresentante la rete. Il metodo utilizzato per la creazione dei Figura 4.23: Rappresentazione delle rotte utilizzate da TORA su di un grafo DAG di tipo

Destination Oriented. L'altezza di un nodo dipendente dalla distanza dal nodo destinazione.

Le frecce indicano i possibili percorsi che un nodo alto può usare per inviare un messaggio ad un nodo basso.

percorsi è un adattamento del processo query/reply definito in [76] e sul lavoro [43]. I nodi del grafo inizialmente diffondono delle query in modo da poter formare i percorsi tra i nodi ed avere informazioni relative alle distanze. Tali informazioni possono comunque essere perse nella fase di gestione delle rotte a causa dell'alta mobilità dei nodi.

● Mantenimento dei percorsi: In[43] viene considerato il problema del mantenimento delle rotte come un problema di costruire un grafo Destination Oriented per una cerca destinazione. Se in un grafo G(N, A) associato alla rete, un arco di un cammino fallisce, una serie di archi inversi assicurano la formazione di un altro DAG in tempo finito. Quando un nodo destinazione non è in grado di essere raggiunto da nessun percorso, il protocollo TORA cancella i cammini non più valide verso quel nodo.

● Cancellazione dei percorsi: In caso di formazioni di partizioni di rete, TORA è in grado di determinare tali partizioni e di cancellare i percorsi non più validi. Per quanto riguarda il rilevamento dei partizionamenti della rete in questo protocollo è necessario mantenere il grafo G(N, A) associato alla topologia della rete di tipo DAG, infatti questi grafi riescono a fornire informazioni sufficienti per la determinazione dei partizionamenti nella rete. Per effettuare ciò è necessario utilizzare un algoritmo di trasformazione di grafi G(N, A) in grafi DAG.

Per quanto riguarda la cancellazione di archi non più validi in seguito ad un errore, i nodi che partecipano alla creazione di un percorso alternativo (per il raggiungimento del nodo destinazione) sono quelli precedenti all'errore e che hanno altezza più bassa rispetto a quello del nodo sorgente.

TORA, invece di mantenere informazioni su più percorsi o sulle distanze per ogni nodo i da un qualsiasi nodo destinazione mantiene su ogni nodo solo le informazioni riguardanti la direzione di interesse e l'insieme dei vicini che si trovano lungo la direzione di interesse. Se un nodo quindi deve inoltrare un pacchetto, prima controlla la direzione del pacchetto, poi seleziona un nodo tra i suoi vicini ed infine inoltra il pacchetto al vicino scelto. Ogni nodo ha a sua disposizione percorsi multipli da poter utilizzare per l'inoltro di un pacchetto. La disponibilità di percorsi multipli