Modelli di mobilità per la simulazione di reti Ad-hoc

INTRODUZIONE
il consumo energetico. Parlando di mobilità in ambito di reti senza fili, abbiamo a che
fare con apparecchi portatili come palmari e notebook, quindi di elementi dotati di una
limitata disponibilità energetica: perciò trattare il consumo diventa un aspetto rilevante
e difficilmente occultabile. Il consumo energetico da noi trattato si riferisce alla potenza
necessaria per la trasmissione dei dati e gli algoritmi studiati vertono all’ottimizzazio-
ne del consumo energetico in questo campo, e non in quello riguardante i componenti
hardware, i quali sono già studiati a fondo a livello ingegneristico.
Lo scopo di questo lavoro è, quindi, quello di presentare una serie modelli di mobili-
tà e algoritmi di ottimizzazione per il consumo energetico presenti in letteratura e di
sviluppare uno strumento software per l’esecuzione dei modelli e l’applicazione degli
algoritmi.
Di seguito viene descritto come è stato strutturato questo lavoro.
Nel capitolo 1 viene fatta una panoramica sulle reti ad-hoc iniziando con i passi storici
che sono stati compiuti e i motivi, che come vedremo, inizialmente furono strettamente
militari, che hanno portato alla sua prima formulazione. Successivamente sono eviden-
ziate le carateristiche fondamentali delle reti ad-hoc (come ad esempio, la già citata
autoconfigurazione) e presentati alcuni scenari di utilizzo.
Nel capitolo 2 vengono presentati i modelli di mobilità. Vedremo inizialmente una pos-
sibile classificazione di questi modelli dei quali successivamente saranno descritte in
modo particolareggiato le caratteristiche e la matematica che ne sta alla base. Nel corso
del capitolo si comprenderà meglio le differenze tra i vari modelli e gli aspetti che que-
st’ultimi riescono a evidenziare; inoltre tutto questo sarà più chiaro visionando i grafici
ottenuti mediante l’applicazione delle metriche, che sono illustrate dalla sezione 2.6 fi-
no alla fine del capitolo.
Nel capitolo 3 viene trattato il problema del consumo energetico. In questo capitolo
presentiamo il problema in modo incrementale, ovvero vediamo il consumo di energia
in una rete informatica composta da due utenti, evidenziandone i costi e le possibili
strategie da impiegare per l’ottimizzazione energetica, e successivamente aumentiamo
la complessità (aggiungendo altri utenti alla rete) fino ad ottenere una formulazione ri-
corsiva che diventerà la base per la creazione degli algoritmi. Successivamente vengono
2
INTRODUZIONE
presentati alcuni algoritmi di ottimizzazione, suddivisi da alcune caratteristiche. Come
nel caso del capitolo 2, si ha la necessità di verificare la teoria mediante delle metriche.
Le metriche per la valutazione degli algoritmi sono indicate nella sezione 3.3 e sono
verificabili mediante i grafici ottenuti dalla nostra applicazione.
In fine, nell’appendice A vengono descritti gli algoritmi utilizzati per lo sviluppo dei
modelli e degli algoritmi presentati nei capitoli precedenti, mentre nell’appendice B
viene presentato il software sviluppato per questa tesi. Come vedremo questo program-
ma permette, mediante un’interfaccia grafica, di visualizzare tutto cio che è stato trattato
nella tesi (ad esempio, le tracce dei movimenti dei nodi nei modelli di mobilità, oppure
l’albero di indirizzamento generato dai vari algoritmi su un’istanza ottenuta da un qual-
siasi modello o ottenuta da un inserimento manuale). Grazie al software siamo in grado
di notare, passo per passo, come varia la distribuzione dei nodi nell’area di simulazione.
Inoltre è possibile applicare le metriche evidenziate nella tesi e visualizzare i grafici dei
risultati ottenuti.
3
Capitolo 1
Reti ad-hoc
Favorito dal web e dalle applicazioni multimediali, l’uso di Internet nell’ultima decade
è largamente cresciuto fino ad essere presente in ogni luogo che possiamo visitare. At-
tualmente la principale via di accesso a Internet sono ancora i fili o le fibre ottiche: ne
consegue che un sempre più alto numero di utenti chiede una maggiore mobilità quando
sono a lavoro, a casa o in ogni altro momento in cui sono in movimento. Per esempio,
gli utenti potrebbero voler confrontare i prezzi di un negozio con quelli trovati sul web,
accedere alla navigazione dalla propria auto, leggere le e-mail durante un viaggio in
autobus e controllare un progetto durante una pausa al bar o all’aeroporto.
I concetti di rete senza fili (wireless) e di Internet mobile, non sono certamente nuovi.
Quando la tecnologia di smistamento di pacchetti, la base su cui si fonda Internet, fu
introdotta con ARPANET nel 1969, il Dipartimento della Difesa americano capì im-
mediatamente il potenziale di una tecnologia in grado di smistare i pacchetti mediante
onde radio, in modo da connettere i singoli nodi in un campo di battaglia. Il proget-
to Packet Radio della DARPA (Defense Advanced Research Projects Agency) iniziato
prima degli anni ’70, ha aiutato a stabilire le prime nozioni di rete senza fili ad-hoc.
È questa una tecnologia utilizzabile ovunque, in grado di sfruttare una rete senza fili
in ambienti dove non esistono cavi o infrastrutture per i cellulari (come ad esempio, i
campi di battaglia), o dove, se anche ci fossero, potrebbero risultare inadaguate o troppo
4
Reti ad-hoc
costose.
Il termine ‘ad-hoc’ implica che questa rete viene stabilita per un servizio, spesso tem-
poraneo e personalizzato per una certa applicazione. Così, normalmente, una rete di
questo tipo è generata per un limitato periodo di tempo. I protocolli utilizzati variano a
seconda dell’applicazione in uso (ad esempio, inviare un video, scoprire se l’incendio
è partito da una foresta, oppure stabilire una videoconferenza tra tre gruppi di ricerca
impegnati nei rilievi di un disastro naturale). Le applicazioni possono essere mobili e gli
ambienti possono variare dinamicamente. Di conseguenza, un protocollo per una rete
ad-hoc deve essere in grado di autoconfigurarsi a seconda dell’ambiente in cui si trova.
Quella che emerge da queste caratteristiche è un’alta flessibilità e malleabilità, mante-
nedo una architettura di rete robusta.
Data la sua mobilità e l’assenza di infrastutture, una rete ad-hoc necessita di nuovi requi-
siti. Il primo è l’autoconfigurazione (di indirizzi e di routing). A livello applicazione,
poi, gli utenti di una rete ad-hoc tipicamente comunicano e collaborano come gruppi
(ad esempio, polizia, vigili del fuoco o medici). Queste applicazioni richiedono, quindi,
efficienti comunicazioni di gruppo (multicasting1) sia per i dati sia per il traffico in
tempo reale. Inoltre, una rete ad-hoc stimola la creazione di servizi orientati alla posi-
zione, non esistenti per una rete cablata.
La complessità di generare una rete mobile ad-hoc ha sfidato varie generazioni di ri-
cercatori sin dagli anni ’70. Grazie all’evoluzione della tecnologia nell’ambito della
trasmissione radio, si sono avuti grandi successi sia in ambito miltare che in quello ci-
vile. A prima vista, queste applicazioni contrastano con il concetto di infrastruttura di
rete e di inter-rete, su cui si basano gran parte delle applicazioni commerciali, e questa
è la ragione per cui la tecnologia di rete ad-hoc ha avuto tempi duri nella transizione a
scenari commerciali.
Tuttavia tutto ciò sta ora cambiando. Il concetto che emerge, invertendo l’andamento
precedente, è quello di ‘rete ad-hoc opportunistica’. Una sottorete ad-hoc opportuni-
stica si connette a Internet mediante protocolli come 802.11 o 2.5/3G e ne estende la
raggiungibilità e la flessibilità. Così, possiamo beneficiare, per esempio, in un ambiente
1Nelle reti di calcolatori, un pacchetto destinato ad un gruppo arbitrario di nodi, e l’indirizzo usato
per inviare un tale pacchetto, è detto multicast.
5
Reti ad-hoc 1.1 Caratteristiche di una rete ad-hoc
domestico, di essere interconnessi pur essendo lontano dalla periferica di collegamento;
in un ambiente urbano, lo stabilire una rete senza fili permette di connettere non solo
i punti di accesso fissi (ad esempio, le prese di rete), ma anche i veicoli o i pedoni;
in un campus universitario, è possibile interconnettere gruppi di studenti e ricercatori
via Internet. Appare ormai evidente che, dopo 30 anni di evoluzione, finalmente le reti
ad-hoc e la rete cablata Internet cooperano alla produzione di una base per applicazioni
commerciali.
1.1 Caratteristiche di una rete ad-hoc
Mobilità: Il fatto che i nodi possono rapidamente riposizionarsi e/o muoversi è la ‘ra-
gione d’essere’ delle reti ad-hoc. Il rapido sviluppo in aree prive di infrastutture, spesso
implica che gli utenti debbano esplorare l’area, probabilmente formando dei gruppi e
coordinandosi per formare una missione. È possibile avere mobilità casuale individua-
le, mobilità di gruppo, movimenti lungo predeterminate strade, e così via. Il modello di
mobilità può avere un grande impatto sulla selezione degli schemi di instradamento e
quindi può anche influenzare le prestazioni globali.
Multihopping: Una rete multihop (salti multipli) è una rete dove il cammino tra la
sorgente e la destinazione attraversa diversi altri nodi intermedi. Una rete ad-hoc utilizza
i salti per aggirare gli ostacoli e per la conservazione dell’energia. In un ambiente come
un campo di battaglia è invece preferibile avere pochi salti, in modo da limitare il rischio
di essere rintracciati dal nemico.
Autoconfigurazione: Una rete ad-hoc deve autonomamente determinare i propri pa-
rametri di configurazione, incluso l’indirizzamento, il routing, l’identificazione della
posizione ed il controllo dell’energia. In alcuni casi, dei nodi speciali possono muoversi
in modo da coprire alcune zone che inizialmente erano fuori copertura.
Conservazione dell’energia: Molti apparecchi appartenenti ad una rete ad-hoc (ad
esempio, portatili, palmari o sensori) hanno una limitata disponibilità di energia e non
6
Reti ad-hoc 1.1 Caratteristiche di una rete ad-hoc
sono in grado di ricrearne della nuova una volta che è terminata. Un protocollo di utiliz-
zo efficiente dell’energia può rappresentare un fattore critico in una missione, qualunque
essa sia.
Scalabilità: In molte applicazioni, una rete può crescere fino a contenere migliaia di
nodi. Per le infrastrutture di reti senza fili, la scalabilità consiste semplicemente nel-
l’occuparsi della costruzione di una gerarchia. La limitata mobilità delle infrastrutture
di rete, può essere facilmente aggirata usando Mobile IP.2 Al contrario, data la maggior
mobilità, una rete ad-hoc pura non tollera l’uso di Mobile IP o di strutture di gerarchia
fissate. Così, la mobilità, in congiunzione con la grande scalabilità è uno dei più critici
problemi di una rete ad-hoc.
Sicurezza: L’avversario della sicurezza di una rete senza fili, come sappiamo, è l’a-
bilità dell’attaccante di mettersi in ascolto, ovviamente di nascosto, sul canale di col-
legamento e bloccare o fare IP spoofing.3 In generale è stato fatto molto lavoro sulle
infrastrutture wireless per estenderle a domini ad-hoc, ma queste reti sono ancora più
vulnerabili ad attacchi.
Sono possibili entrambi i tipi di attacco: attivo e passivo. Un attacco attivo tende ad
effettuare azioni distruttive (ad esempio, un impostore si identifica come il legittimo no-
do e intercetta i pacchetti di controllo e di dati, danneggia le tabelle di routing, effettua
attacchi di tipo ‘denial of service’4). Data la complessità dei protocolli di una rete ad-
hoc, questi tipi di attacchi attivi sono di gran lunga più difficili da rilevare che per una
normalissima rete.
2Mobile IP è un’estensione del protocollo IP studiata per la gestione del traffico Internet da parte
dei dispositivi mobili. Mobile IP risolve il problema adottando due indirizzi: uno fisso (l’home address)
che vale nella rete di appartenenza e l’altro (il care-of address) che vale al di fuori di essa e identifica la
‘posizione’ del dispositivo mobile, cambiando ogni volta che questo passa da una rete a un’altra.
3IP spoofing indica una tecnica tramite la quale si crea un pacchetto IP nel quale viene falsificato
l’indirizzo IP del mittente.
4Denial of service è un tipo di attacco con cui si cerca di portare il funzionamento di un sistema
informatico che fornisce un servizio, ad esempio un sito web, al limite delle sue prestazioni, lavorando su
uno dei parametri d’ingresso, fino a renderlo non più in grado di erogare il servizio.
7