Reti Mobili Ad Hoc: architettura, protocolli e ottimizzazione della connettività wireless (Parte I)

Le Reti Mobili Ad Hoc (MANET) sono sistemi wireless decentralizzati, dove ogni dispositivo funge da nodo e router per il traffico multi-hop. L’architettura di queste reti si distingue per l’assenza di un coordinamento centralizzato, con protocolli di routing avanzati per ottimizzare la connettività e l’efficienza energetica. Cruciale è anche il controllo topologico per ridurre il consumo energetico, garantendo al contempo la durata della rete e la qualità del servizio.

Il settore delle Reti Mobili Ad Hoc (MANET)

Le reti di comunicazione mobili wireless sono diventate parte integrante della nostra società, migliorando notevolmente le capacità di comunicazione, estendendola a qualsiasi ora e luogo, e fornendo connettività senza bisogno di un’infrastruttura sottostante.

In questa prima parte dell’articolo indaghiamo sul recente settore delle Reti Mobili Ad Hoc (MANET — Mobile Ad Hoc Network), concentrandoci sugli aspetti architetturali. Nella seconda parte invece saranno approfonditi gli aspetti rilevanti per l’affermazione del paradigma delle MANET dal punto di vista della sicurezza e da quello “sociale” degli incentivi economici per i nodi della rete, stimolandone la diffusione e l’utilizzo.

Reti Mobili Ad Hoc: architettura e sicurezza

L’ambiente informatico più “distribuito” oggi conosciuto è Internet, con le sue dimensioni di crescita spontanea, la sua architettura aperta, il suo essere un deposito generalmente disponibile di informazioni non strutturate, e così via.

In un ambiente informatico distribuito, come Internet, diversi software interagiscono seguendo uno o più protocolli ben definiti. Ad esempio, la richiesta di accesso a una pagina Web, che viene fatta di routine con un semplice click del mouse, è servita da una serie di interazioni che coinvolgono, oltre al browser e al server Web remoto che ospita la pagina, anche una serie di “agenti” intermedi (router) che rendono possibile la consegna del messaggio di richiesta/risposta.

Vi è una pletora di protocolli, che sono classificati principalmente secondo un modello stratificato di rete (vedi Fig.1). All’estremità inferiore della pila abbiamo i protocolli del livello (layer) fisico, il cui obiettivo è quello di rendere possibile la consegna di sequenze di bit tra computer direttamente collegati tra di loro. All’altro lato troviamo i protocolli applicativi, che supportano i servizi di alto livello come ad es. il servizio Web (attraverso il protocollo http). I protocolli fondamentali sono probabilmente quelli che rientrano nel termine generale di TCP/IP: questi sono i protocolli su cui si basa Internet, in quanto implementano le funzioni chiave dell’instradamento e del controllo della congestione/flusso del traffico dati.

Un presupposto comune nella letteratura del calcolo e networking distribuito è che gli agenti che partecipano all’esecuzione di un protocollo seguano le linee guida specificate dal protocollo stesso; ad esempio, un router che dovrebbe instradare un pacchetto di dati più vicino al suo punto di destinazione lo farà sempre, a meno che non sia temporaneamente fuori servizio. C’è chiaramente un certo numero di impostazioni in cui questa ipotesi ha senso.

Un caso evidente, ad esempio, è quello di una rete privata di proprietà di un’unica società. Nel campo delle reti senza fili – quello che ci interessa di più in questa sede – vi sono impostazioni applicative in cui si applica anche l’assunto di cui sopra; si consideri, ad esempio, il caso di reti di sensori implementate con l’obiettivo di monitorare una data regione. Un altro caso è quello delle reti militari.

Nel seguito viene illustrata l’architettura delle reti mobili ad hoc, con particolare riferimento al routing e alle caratteristiche dei protocolli di rete.

Architettura delle Reti Mobili Ad Hoc nel dettaglio: routing e protocolli

Le Reti Mobili Ad Hoc sono reti wireless caratterizzate dall’assenza di un’entità di coordinamento centralizzato (vedi fig. 2). Ogni dispositivo (mobile) della rete, ad esempio un notebook o uno smartphone, può collegarsi direttamente solo ai dispositivi all’interno del suo raggio di trasmissione, chiamati dispositivi vicini; di conseguenza, il traffico destinato a, o originato da, un dispositivo non vicino deve essere instradato attraverso uno o più dispositivi intermedi (traffico multi-hop). Questa caratteristica rappresenta una differenza importante rispetto ad altre reti wireless, come le reti di telefonia cellulare o LAN senza fili, ed è la fonte di una serie di problemi impegnativi, che ora brevemente esamineremo.

Ottimizzazione della connettività nelle Reti Mobili Ad Hoc: sfide e protocolli di controllo topologico

Dato un range di trasmissione per ciascun dispositivo (vedi fig. 3), una rete ad hoc può essere modellata come un grafico (diretto) i cui nodi sono i dispositivi e vi è un arco dal nodo U al nodo V se e solo se V è all’interno del range di trasmissione di U. Tale grafico viene spesso definito come grafico di comunicazione (communication graph). Il controllo topologico ha la necessità di stabilire alcune proprietà di connettività desiderate per il grafico di comunicazione, che agisce sulla portata di trasmissione dei dispositivi.

A seconda dello scenario applicativo e del modello di traffico, le proprietà di connettività richieste possono variare: la più ovvia è la piena connettività (ovvero, il grafico deve essere totalmente connesso), ma in alcuni casi si possono richiedere proprietà più forti, come la doppia o tripla connettività. Inoltre, per motivi che sono legati ai protocolli degli altri livelli, è spesso richiesto che il grafico sia simmetrico, cioè che vi sia un arco (U,V) se e solo se vi è l’arco (V, U). Chiaramente, l’obiettivo del controllo topologico è quello di ottenere le proprietà di connettività desiderate, utilizzando la minima potenza di trasmissione possibile.

A causa della potenziale riduzione della potenza di trasmissione dei nodi, il controllo topologico può avere effetti positivi sia sulla durata di vita della rete che sulla capacità del canale, poiché una portata ridotta implica una minore contesa sul supporto wireless. Sfortunatamente, la determinazione della topologia corrispondente al minimo consumo di energia è un problema difficile [1, 2]. In [3, 6, 7] vengono illustrati alcuni protocolli pratici (sub-ottimali) per l’implementazione della connettività.

Instradamento (routing) nelle Reti Ad Hoc: problemi e soluzioni

L’instradamento (routing) è il problema di decidere il percorso nel grafo di comunicazione per il traffico destinato ai nodi non vicini. Logicamente, il livello di routing è al di sopra del controllo topologico, ma è strettamente correlato a questo. Alcuni autori non considerano un livello di controllo della topologia separato (in particolare, non è necessario alcun controllo della topologia se tutti i nodi hanno lo stesso, massimo, campo di trasmissione) e la topologia della rete è “determinate” dalla fase di scoperta del percorso stesso.

In considerazione della potenza necessaria per trasmettere un pacchetto dati a distanza D (che cresce almeno quadraticamente con D), i vari percorsi sorgente-destinazione possono essere caratterizzati da consumi energetici molto diversi, e un chiaro obiettivo del routing è quello di scegliere il più efficiente tra questi percorsi.

Controllo del canale wireless: MAC e connettività

Il canale wireless è condiviso tra i dispositivi di rete; chiaramente, mentre uno di questi dispositivi U sta trasmettendo, nessun altro dispositivo all’interno del raggio di trasmissione di U può avviare un’altra trasmissione. Quando si utilizzano diverse potenze di trasmissione (ad esempio in seguito a decisioni prese a livello di controllo topologico) è necessario sintonizzare il meccanismo request-to-send/clear-to-send (RTS/CTS) per “silenziare” tutti i nodi potenzialmente in conflitto.

Ad esempio, supponiamo che il nodo U non rientri nel range di V mentre quest’ultimo è all’interno di U. Quindi, un messaggio di controllo RTS inviato da V non può bloccare U, e quest’ultimo potrebbe erroneamente presumere che il canale sia disponibile per la trasmissione [5]. Si noti che il grafo di comunicazione dell’esempio precedente non è simmetrico. Si può erroneamente pensare che una soluzione ovvia al problema sia semplicemente quella di eliminare l’arco (U, V) quando si costruisce la topologia di rete.

Tuttavia, l’esempio mostra che la connettività logica è generalmente diversa dalla connettività fisica. La simmetria logica imposta a livello di controllo topologico può essere utile nella fase di ricerca delle rotte, ma ciò che conta a livello MAC è la connettività fisica. Si tratta di un punto spesso trascurato nella letteratura sul controllo topologico.

Efficienza energetica nelle Reti Ad Hoc: sfide e obiettivi

L’efficienza energetica è una preoccupazione a tutti i livelli della pila di protocolli. In particolare, il controllo topologico ha l’obiettivo specifico di determinare un grafo di comunicazione a basso consumo. Per quanto riguarda l’instradamento, è generalmente riconosciuto che le considerazioni relative all’efficienza energetica devono integrare l’analisi più tradizionale basata sul tasso di perdita di pacchetti, sui costi generali dei messaggi di instradamento, ecc.

L’obiettivo finale è aumentare la durata di vita dei singoli dispositivi e quella della rete nel suo complesso. Sono state proposte diverse definizioni della durata di vita della rete: secondo la definizione più semplice, una rete non è più attiva quando il primo nodo “muore”; un’altra definizione prende in considerazione le dimensioni del più grande componente collegato, che deve contenere almeno il 90% dei nodi. Sono possibili altre definizioni. A causa dei problemi summenzionati, la tecnologia delle reti ad hoc è ancora agli albori e non attuata su larga scala.

Tuttavia, nonostante le difficoltà di cui sopra, vi è già un vasto corpus di lavori che si occupano di reti ad hoc (si vedano, ad esempio, i documenti nei lavori annuali del Simposio ACM “MobiHoc” sulle reti mobili ad hoc, https://www.sigmobile.org/mobihoc/). Ciò è dovuto al fatto che le reti ad hoc rappresentano il paradigma più promettente per il calcolo distribuito. Come esempio di scenario di ubiquitous computing consideriamo un servizio di accesso a Internet per utenti mobili che molti provider offrono in una serie di siti “pubblici” (ad esempio, diversi aeroporti, centri commerciali e urbani in Italia stanno già offrendo questo servizio gratuitamente).

La possibilità, offerta dalla tecnologia ad hoc, di un accesso multi-hop (in cui un dispositivo mobile comunica con le stazioni base tramite altri dispositivi mobili) avrebbe un impatto positivo su aspetti quali una maggiore area di copertura del servizio[1] e, grazie all’adozione di minori range di trasmissione, una maggiore capacità e durata di vita della rete.

Classificazione dei protocolli di routing nelle reti MANET

Nelle reti cablate il compito di stabilire il percorso che i pacchetti di dati devono seguire è svolto solo da un gruppo limitato di dispositivi chiamati router. Nelle reti ad hoc wireless, invece, ogni host agisce sia come router che come mittente di pacchetti, quindi i classici protocolli di routing utilizzati dalle reti cablate non sono affatto applicabili alle MANET. I protocolli di routing esistenti possono essere classificati secondo tre criteri:

1. In base all’organizzazione logica attraverso la quale il protocollo “descrive” la rete: da questo punto di vista essi possono essere suddivisi in protocolli di routing “Uniform” e “Non Uniform”. Nel primo caso, ogni nodo genera messaggi di controllo del percorso mentre risponde alle richieste di controllo del percorso (in entrata): tutti i nodi hanno la stessa funzione. Nel secondo, invece, il modo in cui i nodi generano e/o rispondono ai messaggi di controllo del percorso può essere diverso per i diversi gruppi di nodi. I protocolli non uniformi possono essere a loro volta logicamente suddivisi in “Selezione dei vicini” (Neighbor Selection) e “Gerarchici” (Hierarchical): nel primo caso ogni nodo seleziona un sottoinsieme di nodi vicini per calcolare il percorso che i pacchetti di dati devono seguire; nel secondo caso, invece, i nodi si auto-organizzano in gruppi chiamati cluster. Per ogni cluster esiste un nodo “controller” (master o cluster head) che ha il compito di coordinare il traffico al suo interno. È evidente che i protocolli non uniformi riducono notevolmente il traffico di segnalazione rispetto a quelli uniformi, grazie al minor numero di nodi assegnati al calcolo dei percorsi; ma pagano un maggior sovraccarico dovuto al mantenimento di strutture complesse ad alto livello.
2. In base al modo in cui vengono ottenute le informazioni sul routing: da questo punto di vista, i protocolli possono essere divisi in Proattivi o guidati da tabella (Table-Driven), Reattivi o On-Demand e Ibridi. Il primo tipo tiene costantemente aggiornate le informazioni di routing attraverso lo scambio di pacchetti a intervalli temporali fissi: ciò consente la disponibilità immediata di routing ad ogni richiesta. Lo svantaggio è che gli algoritmi proattivi producono traffico di segnalazione anche quando non viene trasmesso alcun pacchetto di dati; questo può causare problemi di eccessivo carico di traffico nella rete, specialmente quando i nodi sono in rapido movimento, perché l’intervallo di tempo tra le trasmissioni di informazioni di routing deve essere inversamente proporzionale alla velocità con cui i nodi si muovono, in modo da ottenere un routing corretto. Esempi di protocolli proattivi sono DSDV (Destination-Sequenced Distance-Vector) e WRP (Wireless Routing Protocol). Nei protocolli reattivi è necessaria una procedura per stabilire il percorso di instradamento corretto solo quando i pacchetti devono essere trasmessi; in questo modo si riduce il traffico di segnalazione, ma con tempi di consegna crescenti [4]. Esempi di protocolli reattivi sono AODV (ad hoc On-Demand Distance Vector), DSR (Dynamic Source Routing) e TORA (Temporally Oruting Algorithm). Infine, i protocolli ibridi cercano di raggiungere i vantaggi di entrambi i protocolli precedenti, limitando l’applicazione degli algoritmi proattivi solo ai nodi vicini a quello che effettua la trasmissione dei pacchetti di dati. Un esempio di protocollo ibrido è ZRP (Zone Routing Protocol).
3. In base a come viene creato il percorso di routing: da questo punto di vista i protocolli possono essere suddivisi in Source Routing e Non Source Routing. Nei primi il nodo di invio determina il percorso completo verso la destinazione, registrandolo direttamente nel pacchetto; quindi, i nodi intermedi ritrasmettono solo i pacchetti a quelli indirizzati dal percorso precedentemente stabilito. Nel secondo, invece, l’unica informazione di routing contenuta nei pacchetti di dati è quella rappresentata dal miglior nodo vicino al quale deve essere inoltrata la comunicazione; di conseguenza, ogni nodo deve essere in grado di ottimizzare le decisioni di instradamento.

Note

[1] Il primo esempio noto di MANET pubblica in Italia è relativo a quella realizzata nella comunità montana dell’Alta Langa, un’area del Piemonte che copre circa 200 km quadrati e 21 città.

Riferimenti bibliografici

[1] Blough, D. M., Leoncini, M., Resta, G., and Santi, P. On the symmetric range assignment problem in wireless ad hoc networks. In Foundations of Information Technology in the Era of Network and Mobile Computing. Springer, 2002, pp. 71–82.

[2]  Clementi, A. E., Penna, P., and Silvestri, R. Hardness results for the power range assignment problem in packet radio networks. In Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques. Springer, 1999, pp. 197– 208.

[3]  Jalalinia, F., and Ghasemi, S. The cbk-neigh protocol for symmetric topo- logy control in ad hoc networks. In Sensor Technologies and Applications, 2009. SENSORCOMM’09. Third International Conference on (2009), IEEE, pp. 588–595.

[4]  Johansson, P., Larsson, T., Hedman, N., Mielczarek, B., and Degermark, M. Scenario-based performance analysis of routing protocols for mobile ad-hoc net- works. In Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking (1999), ACM, pp. 195–206.

[5]  Jung, E.-S., and Vaidya, N. H. A power control mac protocol for ad hoc networks. In Proceedings of the 8th annual international conference on Mobile computing and networking (2002), ACM, pp. 36–47.

[6]  Liu, J., and Li, B. Mobilegrid: Capacity-aware topology control in mobile ad hoc networks. In Computer Communications and Networks, 2002. Proceedings. Eleventh International Conference on (2002), IEEE, pp. 570–574.

[7]  Ramanathan, R., and Rosales-Hain, R. Topology control of multihop wireless networks using transmit power adjustment. In INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE (2000), vol. 2, IEEE, pp. 404–413.

 

A cura di: Crescenzio Gallo, Michele Perilli, Michelangelo de Bonis
Università di Foggia