QSRP: un protocollo di routing per la qualità del servizio in reti ad hoc

  
12
scarsa qualità del mezzo trasmissivo, l’alta probabilità di collisione, la mobilità e 
la poca energia disponibile nei dispositivi. 
Tutto ciò ha evidenziato la necessità di introdurre nuove metriche prestazionali da 
considerare al fine di proporre nuovi protocolli, specificamente pensati per questo 
tipo di reti. 
In particolare, uno dei problemi chiave, è quello della consegna affidabile dei 
pacchetti informativi in questi scenari altamente dinamici. Questo problema è 
noto in letteratura come routing. 
In particolare, la volontà di introdurre nella tecnologia delle MANET concetti 
nuovi come quello di qualità del servizio (QoS), ha portato all’introduzione di 
soluzioni originali ed innovative. 
 
 In questa tesi viene proposto un protocollo di QoS routing per MANET 
chiamato QSRP (Quality of Service Routing Protocol).  
Il QSRP è un protocollo distribuito che utilizza informazioni geografiche, ottenute 
per mezzo di GPS o altro, per ricercare un percorso che vada da un nodo sorgente 
ad un noto destinazione soddisfacendo delle metriche di QoS,  senza conoscere 
l’intera topologia di rete. In questo lavoro verrà mostrato come il QSRP è in grado 
di soddisfare vincoli imposti dalla applicazione in termini di qualità del servizio 
quali banda, ritardo end-to-end e probabilità di perdita del pacchetto. Si 
dimostrerà come il QSRP è in grado di cercare in maniera efficace un percorso 
valido conoscendo poche informazioni topologiche sulla rete. In particolare si 
utilizzerà un algoritmo di route discovery, che impiega un meccanismo di 
duplicazione dei messaggi di probe a cui è stato dato il nome di splitting. 
Vedremo come tale meccanismo riuscirà a far fronte alla mancanza di 
informazioni globali della rete da parte di un nodo.  
Insieme a questa tecnica, si farà uso del concetto di classe di servizio, già 
sviluppato per reti ATM, ed applicato in questa tesi alle MANET. Le classi di 
servizio saranno usate per definire le metriche da soddisfare in fase di ricerca dei 
percorsi di rete. La progettazione di questo protocollo terrà conto anche di un 
algoritmo molto semplice di route maintenance basato sulla predizione della 
posizione futura dei nodi, grazie all’uso di informazioni di tipo geografico.  
  
13
In questo lavoro di tesi si applicherà inoltre all’algoritmo di QoS routing proposto, 
un nuovo algoritmo di cooperazione detto a punti o a crediti. Si vedrà quale 
tecnica originale questo algoritmo usa per incentivare la cooperazione ed isolare i 
nodi egoisti che agiscono in una rete ad hoc. 
Si analizzeranno in dettaglio le strutture che compongono il protocollo, quali 
messaggi di controllo e tabelle interne ai nodi, e verranno illustrate altresì  le 
routine principali degli algoritmi di route discovery, route maintenance e 
cooperazione a punti tramite l’ausilio di pseudo-codice, che faciliterà il lettore 
nella comprensione di quanto realizzato.  
Infine si illustreranno i risultati ottenuti grazie all’utilizzo del simulatore ns-2 per 
reti wireless ad hoc. In tal modo verrà mostrato il buon comportamento del 
protocollo QSRP, in particolare in condizioni di alto traffico e di elevata mobilità 
dei nodi.  
 
Questo lavoro di tesi si articolerà nel modo seguente. Nel primo capitolo 
verrà presentata un’ampia panoramica delle reti ad hoc soffermandosi soprattutto 
sui problemi legati al routing, alla qualità di servizio e alla cooperazione. Nel 
secondo capitolo verrà discusso lo stato dell’arte sugli algoritmi di routing, con e 
senza QoS, e sugli algoritmi di collaborazione tra i nodi. Nel terzo capitolo verrà 
illustrato ampiamente il protocollo QSRP, con routine e strutture che lo 
compongono. Infine, nel quarto capitolo, verranno discusse le performance del 
protocollo in vari contesti con alta densità di nodi, elevato traffico ed alta 
mobilità. Infine nel quinto capitolo, verranno tratte le conclusioni sul lavoro 
svolto. 
 
  
14
 
 
 
 
 
 
 
 
Capitolo I  
Le reti ad hoc wireless  
  
15
I.1 Reti ad hoc 
 
Le reti ad hoc sono un sistema di comunicazione, generalmente basato su 
trasmissioni via radio, implementato come estensione o come alternativa ad una 
rete locale cablata. Sin dalla loro prima apparizione agli inizi degli anni ’70, le reti 
ad hoc hanno avuto il loro principale utilizzo in ambito militare, come tutte le 
altre tipologie di reti. Chiamate inizialmente packet radio network (PRNET) dal 
Defense Advanced Research Projects Agency (DARPA), sono state ideate in 
ambito bellico per mantenere una comunicazione tra il quartier generale ed i vari 
accampamenti militari, posti in zone ostili. 
In seguito, il progetto delle reti ad hoc è stato impiegato anche in ambiente di 
protezione civile. A partire dagli anni novanta, il rilevante costo del cablaggio 
delle reti che gravava sul bilancio di industrie e aziende, ha spinto sempre più le 
aziende verso l’utilizzo di una soluzione interna che non necessitasse di cavi di 
connessione. Soprattutto in questi ultimi anni la maggiore diffusione e uso di 
computer portatili, personal digital assistant (PDA), telefoni cellulari dell’ultima 
generazione ha dato una spinta fortissima alla ricerca in questo campo. Si sono 
venute a creare così le wireless local area networks o WLANs. Attualmente la 
tecnologia più diffusa nel campo delle wireless networks è quello riconducibile 
allo standard IEEE 802.11b, conosciuto comunemente con la sigla Wi-Fi (wireless 
fidelity) promossa dall’Institute of Electrical and Electronics Engineers 
(IEEE). Questo protocollo viene implementato nella maggior parte delle schede 
di rete wireless esistenti sul mercato e può gestire una connessione con o senza 
infrastruttura ad una velocità di 1, 2 o 11 Mbit/sec. Inoltre attualmente sul mercato 
stanno cominciando ad apparire schede di rete che utilizzano nuovi standard IEEE 
quali l’IEEE 802.11g che permette di raggiunge i 54 Mbit/sec o l’ 802.11e che 
confiderebbe anche il supporto della qualità di servizio (QoS), ma che tuttavia allo 
stato attuale non è ancora disponibile. 
Le reti wireless ad hoc, si classificano in due tipologie: 
 
- Reti ad hoc infrastrutturata 
- Reti ad hoc non infrastrutturata.  
  
16
 
Le prime prevedono la presenza di stazioni base o punti di accesso, fissi e 
collegati tra loro mediante connessioni con filo ad alta velocità, che consentono ai 
dispositivi o terminali mobili di poter comunicare usando le stazioni base come 
ponti. Un punto di accesso può essere collegato ad un'altra rete wired o wireless o 
Internet. Per coprire aree di vaste dimensioni è possibile anche utilizzare più punti 
di accesso. Una rete di tale tipo è infatti composta da nodi mobili comunicanti tra 
loro con l’ausilio di infrastrutture: access point (AP), apparecchiature che 
permettono la connessione tra i singoli terminali wireless e la connessione dalla 
rete wireless ad una rete di tipo wired ; i ripetitori di segnale, ovvero antenne che 
possono estendere la rete wireless in una certa direzione minimizzando le relative 
interferenze.  
Il principio delle reti infrastrutturate trova al giorno d'oggi ampia applicazione nel 
campo della telefonia mobile, mentre ne è ulteriore attuazione la rete locale senza 
filo da ufficio, nota anche come WLAN.  
 
 
Figura I.1: Esempio di rete wireless a infrastruttura 
 
Nelle reti ad hoc non infrastrutturate, invece, tutti i dispositivi sono mobili e 
capaci di connettersi dinamicamente. In più, ognuno di essi ricopre il ruolo di 
router, può, cioè, determinare e memorizzare i percorsi per ciascun altro 
dispositivo della rete.  
Queste reti ad hoc, non necessitando di un'infrastruttura fissa, vantano un'elevata 
elasticità di impiego che ne consente l'applicazione nei più disparati campi. 
Maggiori dettagli li vedremo nel prossimo paragrafo, poiché esse sono oggetto di 
trattazione di questa tesi, mentre delle reti ad hoc infrastrutturate non si farà più 
menzione. 
  
17
 
 
 
       Figura I.2: Esempio di rete ad hoc 
 
Prima di passare oltre bisogna tuttavia fare attenzione però a distinguere 
tra due tipologie di reti che molto spesso vengono confuse tra loro. Ovvero rete 
mobile e rete wireless vengono spesso considerate erroneamente la medesima 
cosa. Questi due sistemi presentano contesti, architetture, protocolli di 
comunicazioni e dispone di terminali differenti. La rete mobile è un sistema dove 
i terminali sono mobili e non hanno una posizione fissa, possono muoversi in uno 
spazio molto ampio senza che venga persa la conversazione attiva e possono 
essere rintracciati ovunque a patto di essere connessi con la rete. Una rete mobile 
non è obbligatoriamente una rete wireless poiché con questo termine ci si riferisce 
al tipo di trasmissione dati che viene utilizzata, ovvero una trasmissione senza 
connessioni fisiche come può essere quella radio. La rete wireless in certi casi si 
presenta come un sottoinsieme di rete mobile come dismostrato in figura. 
 
 
Figura I.3: Differenza rete mobile-rete wireless 
 
Ad esempio una rete mobile è la rete radio-cellulare GSM che è una rete mobile 
che utilizza le onde radio come canale trasmissivo.  
 
  
18
I.2  Reti ad-hoc non infrastrutturate 
 
Una rete ad hoc non infrastrutturata, denominata con l’acronimo MANET 
(Mobile Ad-hoc NETwork), consiste in un insieme di nodi mobili equipaggiati di 
trasmettitore e ricevitore wireless in grado di creare tra loro interconnessioni 
tramite antenne senza richiedere l’uso di punti di accesso cablati. Tra le tecnologie 
più utilizzate per formare le reti ad-hoc annoveriamo l’infrarosso, la trasmissione 
ottica e le onde radio. L’infrarosso è molto semplice per certi punti di vista ma ha 
alcuni difetti non trascurabili. Esso infatti è sensibile agli ostacoli, tanto da 
richiedere che i dispositivi siano tra loro visibili, e molto spesso i terminali per 
comunicare tra loro devono essere posti l’uno di fronte all’altro, a pochissimi 
centimetri di distanza. Dal punto di vista elettromagnetico una parete molto sottile 
costituisce una barriera nelle comunicazioni che utilizzano questa tecnologia. Per 
questo essa viene solitamente usata in spazi aperti o all’interno di un ufficio 
purché non vi siano ostacoli frapposti tra i due dispositivi. Per risolvere queste 
limitazioni la tecnologia maggiormente utilizzata è la trasmissione via radio. Le 
reti WLAN che utilizzano le onde radio per la comunicazione, possono scegliere 
tra due differenti metodi per effettuare la  trasmissione, poggianti entrambi su la 
stessa soluzione di comunicazione detta a spettro diffuso (spread spectrum) e si 
classifica in: 1) direct sequence e 2) frequency hopping.  
La prima tecnica, Direct Sequence Spread Spectrum (DSSS), prevede la 
trasmissione del segnale moltiplicato per una sequenza binaria nota a velocità 
maggiore (chip sequence), rendendolo simile ad un rumore a bassa potenza, ma a 
larga banda. Il ricevitore, che conosce la chip sequence, può recuperare 
l’informazione contenuta nel segnale trasmesso. 
La tecnica 2), Frequency Hopping Spread Spectrum (FHSS), invece, trasmette il 
segnale in slot temporali cui è associata di volta in volta una portante a frequenza 
diversa secondo una sequenza di salto (hopping sequence) nota al ricevitore [87]. 
Queste tecniche permettono di ottenere un segnale a bassa densità spettrale di 
potenza - essendo distribuito su un ampia banda di frequenza - che minimizza la 
possibilità di interferire con altri segnali, presenti nella medesima area. Un altro 
  
19
vantaggio importante è legato alla ridondanza del messaggio (siccome esso è 
presente su più frequenze) che rende il sistema altamente resistente al rumore e 
alle interferenze . 
Il range di trasmissione di ciascun nodo bisogna risulta limitato, per cui la 
connessione tra due o più terminali è creata tramite connessioni multi-hop. Così i 
nodi assumono la doppia valenza di terminale e di router della rete che essi 
costituiscono. In tal modo, mentre con le reti wireless ad infrastruttura ci 
trovavamo ad avere un’architettura con almeno due livelli gerarchici, nelle 
MANET ci ritroviamo in generale ad avere una rete ad un solo livello gerarchico, 
ovvero completamente flat. 
Una delle principali caratteristiche di questa tipologia di reti è la loro capacità di 
costituire autonomamente e spontaneamente (ovvero senza alcuna azione 
effettuata dall’utente) delle reti per la comunicazione. Ciò ha procurato alle reti ad 
hoc non infrastrutturate ( che da ivi in poi verranno chiamate più semplicemente 
ad hoc) l’appellativo di reti self-oranizing e spontanee.  
Mentre le reti wireless convenzionali viste prima hanno bisogno di una 
architettura che permetta loro di essere una rete organizzata, con access point o 
altro, le reti ad hoc non hanno invece bisogno di una organizzazione precostituita 
e fissa. Questa mancanza di infrastruttura permette a questo tipo di reti di essere 
estremamente dinamiche e versatili, il che risulta di enorme importanza per talune 
applicazioni e per alcuni ambienti. Per questo motivo le reti ad hoc, che come 
indica il loro stesso nome, possono essere facilmente e rapidamente disponibili 
ovunque (anywhere) e in qualsiasi momento (anytyme). Da ciò è chiare che le reti 
ad-hoc abbiano riscosso grande interesse in campo militare, in quanto utili per 
soldati in un campo di battaglia o polizia in missione. Le reti ad hoc risultaono 
utili anche in luoghi che hanno subito un disastro, un conflitto o sono rimasti 
isolati. Tuttavia, anche ambienti civili possono usufruire dei vantaggi e benefici 
che derivano da questa tipologia di rete wireless. Immaginiamo ad esempio di 
trovarci in un convegno dove ogni partecipante è provvisto di un terminale 
proprio e si vuole scambiare materiale di tipo elettronico con i colleghi. Un 
ulteriore esempio è quello di una rete costituita da autovetture su di una autostrada 
che si scambiano informazioni sul traffico in modo rapido ed esatto. I più 
  
20
maliziosi potrebbero pensare addirittura di costruire una rete ad hoc tra semplici 
PDA durante un esame scritto all’università di Catania. 
Gli scenari applicativi delle reti ad hoc si possono suddividere principalmente in 
tre categorie: 
 
- Personal Area Networks (PANs) 
- Body Area Networks (BANs) 
- Sensor Networks 
 
Le PANs sono costituite da persone che per motivi di lavoro o per la necessitò di 
svolgere attività collaborative, si ritrovano ad operare all’interno di una stessa 
area, condividendo informazioni. 
Le BANs invece sono reti costituite da componenti elettronici applicati sul corpo 
di persona, come microfoni, telefoni o sensori vari che possono monitorare 
funzioni vitali corporali quali pressione sanguigna, temperatura corporea o 
pulsazione cardiaca. 
Le sensor networks infine sono reti di sensori con compiti di monitoring che 
assolvono funzioni tra le più disparate, dal monitoraggio ambientale, a quello 
meteorologico, a quello legato all’home automation. 
 
  
21
I.3 Problematiche delle reti ad hoc 
 
 Nonostante le numerose applicazioni, numerosi sono i problemi che ancora 
affliggono questo tipo di reti. Tra i primi problemi riscontrabili nelle reti wireless,  
vi è la minor disponibilità di risorse rispetto alle reti di tipo wired. Si pensi infatti 
che le reti LAN wireless hanno una banda limitata, problemi energetici, problemi 
inerenti il limitato range di trasmissione nonché la limitata qualità di trasmissione. 
In più ci sono problemi dovuti dalla topologia altamente dinamica, alla limitata 
sicurezza al livello fisico o addirittura anche limitate capacità di storage e di 
processing dei dispositivi utilizzati.  
La bassa capacità dei link nelle MANET rispetto alle reti wired, ha sicuramente  
effetti negativi sul throughput, soprattutto considerando che a ciò si sommano 
rumore, interferenze e collisioni sul canale trasmissivo.  
Per quanto riguarda i problemi energetici, essi sono legati dal fatto che i terminali 
delle reti ad hoc sono alimentati da batteria e non hanno un autonomia elevata. Per 
questo, nelle reti ad hoc, il problema della conservazione di energia diventa di una 
certa rilevanza. 
 
I.3.1 Protocollo di MAC 
Per quanto concerne poi la propagazione delle informazioni sul mezzo trasmissivo 
varie difficoltà si riscontrano. Infatti la connessione tra due nodi mobili avviene 
tramite segnali radio in modalità broadcast. Nel caso in cui ci fosse una rilevante 
densità di nodi mobili nella rete si potrebbero incontrare alcuni ben noti problemi 
conosciuti con gli ameni nomi di problema della stazione nascosta, problema 
della stazione esposta, capture problem e problema del terminale intruso. 
Vediamo più in dettaglio in cosa consistono tali problemi. 
Il problema della stazione esposta si verifica quando ci sono più nodi mobili, ad 
esempio A, B, C e D come in figura, che devono comunicare 
contemporaneamente tra loro. 
  
22
  
Figura I.4: Problema della stazione nascosta 
 
Supponiamo adesso che A voglia comunicare con B e, non trovandosi all’interno 
del range di copertura di C non saprà che ci sono altri utenti che stanno 
trasmettano verso B, crede di poter trasmettere. Il nodo C, essendo in grado di 
sentire solo B e D ma non A, decide di trasmettere a B, perché non sente il 
segnale precedentemente spedito da A. Così facendo si darà luogo ad una 
collisione dei messaggi di A e di C su B. 
Un problema opposto invece si ha quando C vuole comunicare con D e B vuole 
comunicare con A. Dato che B e C sono l’uno nel range di trasmissione dell’altro, 
uno dei due nodi, trovando il campo occupato, crederà di non poter trasmettere 
perché c’è il rischio di una collisione con l’altro nodo. Per esempio se B sta già 
trasmettendo ad A, C non trasmetterà nessun pacchetto verso D. Ciò porterà 
tuttavia ad un’inutile paralisi di parte della rete con conseguente riduzione delle 
prestazioni. Il suddetto fenomeno è noto con il nome di problema della stazione 
esposta. 
 
 
Figura I.5: Problema della stazione esposta 
  
23
Per ovviare a questi inconvenienti lo standard IEEE 802.11 che utilizza il 
protocollo di MAC CSMA/CA (Carrier Sensing Multiple Access with Collision 
Avoidance), nato dal precedente MACAW. Quest’altro si basa essenzialmente sul 
protocollo CSMA/CD (Carrier Sensing Multiple Access with Collision 
Detection).  
Per evitare le collisioni, una stazione, attraverso il carrier sensing, verifica se il 
canale sia occupato, e in caso risulti libero, non trasmette subito ma aspetta un 
intervallo di tempo fisso chiamato DIFS ( Distributed Inter-Frame Slot). Una volta 
scaduto il DIFS, la stazione che ha trasmesso per ultima avvia un finestra 
temporale di attesa denominata Contention Window (CW) nella quale questa si 
inibisce, mentre, chi vuole trasmettere, adotta un algoritmo di backoff random. La 
stazione che vedrà scadere questo tempo per prima, comincerà a trasmettere, 
mentre le altre rimarranno in sensing sospendendo il periodo di backoff senza 
resettarlo, per poi farlo ripartire alla prossima contesa del canale. Si vede 
chiaramente che questo non basta ad evitare la collisione tra due nodi né ad 
evitare i problemi sopra esposti.  
Al fine di superare i suddetti problemi, una volta scaduto il tempo di backoff, la 
trama non viene subito trasmessa, ma viene lanciato un RTS (Request To Send) al 
ricevente. Quindi nel peggiore dei casi, la collisione può avvenire sulla 
trasmissione di un pacchetto di controllo e non su un messaggio. Tutte le stazioni 
che ascoltano l’RTS inibiranno la propria trasmissione e il ricevente spedirà un 
segnale CTS (Clear To Send) dopo aver ricevuto l’RTS. Per evitare che 
avvengano ulteriori collisioni su quest’ultimo messaggio il ricevente attende un 
tempo SIFS (Short Inter-Frame Slot), minore del DIFS, prima di trasmettere. 
Infine, quando un nodo riceve un CTS aspetta un SIFS prima di cominciare la 
trasmissione dati. La minor durata di SIFS permette una certa priorità di 
trasmissione. Con questo metodo si riesce ad evitare il problema dei nodi nascosti 
e di quelli esposti. 
 Un altro problema che può essere incontrato in tali reti, è il capture 
problem. Esso si verifica quando due nodi trasmettono ad un nodo comune ed uno 
di essi è più vicino dell’altro. Questo tuttavia fa si che il nodo destinatario riceva il 
segnale dal nodo sorgente più vicino con maggior potenza.