Un protocollo MAC multicanale per reti wireless ad-hoc

4 Capitolo 1. Introduzione
noto un telefono cellulare diventa inutilizzabile al di fuori del raggio di
copertura dei ripetitori della rete a cui appartiene. La nuova sfida inve-
ce dei dispositivi wireless consiste nel riuscire a comunicare tra di loro
senza avvalersi dell’ausilio di una architettura fissa. In quest’ottica ogni
terminale mobile assume il doppio ruolo di host e di router, cioè di instra-
datore di pacchetti, e si viene quindi a creare un schema collaborativo in
cui ogni nodo partecipa in maniera attiva allo scambio di informazioni.
Una rete composta come in questo caso di nodi mobili intelligenti, cioè
in grado di organizzarsi autonomamente, viene definita rete wireless ad
hoc. L’adozione di una rete wireless porta ad una considerevole serie di
vantaggi tra cui una semplice e rapida messa in opera data l’assenza di
un’infrastruttura fissa, la tolleranza a guasti in quanto l’organizzazione
non è affidata a pochi nodi critici come nelle reti wired ed infine una
struttura altamente scalabile.
D’altro canto esistono anche diverse problematiche connesse a questa
tipologia di reti e in gran parte legate alla mobilità degli host. Diventa
particolarmente complesso, ad esempio, instaurare una connessione stabi-
le multi-hop, ossia che coinvolge più nodi, tra host che possono cambiare
la loro posizione in maniera del tutto indipendente uno dall’altro. In
questo scenario diventano frequenti attivazioni e cadute di link mono e
bidirezionali causando continui cambiamenti nella topologia della rete.
Essendo un sistema totalmente distribuito, si può verificare che due o
più host trasmettano contemporaneamente generando delle interferenze
sul canale
1
o collisioni. Il fenomeno delle collisioni nelle reti wireless
si verifica in ricezione, cioè quando un host riceve contemporaneamente
due o più segnali sovrapposti, originati da mittenti diversi, che risultano
pertanto impossibili da interpretare. Le collisioni quindi compromettono
e rallentano le trasmissioni, sprecando energia e banda a disposizione.
Un altro problema riguardante le reti wireless ad hoc è rappresentato
dal consumo energetico dei terminali mobili. Soprattutto in mancanza
di uno schema centralizzato di controllo delle comunicazioni, non è detto
che le trasmissioni tendenzialmente abbiano un esito positivo, ad esem-
1
Con questo termine si indica l’entità logica di comunicazione che permette a due
o più host di scambiarsi informazioni
5pio a causa di una collisione o della caduta di un link: quindi si rischia di
sprecare preziose risorse energetiche. Tutti i protocolli per la gestione di
tali reti devono tener conto, non solo di una topologia instabile, ma an-
che delle limitate capacità energetiche che di solito caratterizzano questi
dispositivi.
Preso atto di queste problematiche nasce l’esigenza di definire un
nuovo framework protocollare che ben si adatti alle reti wireless ad hoc.
Il modello ISO/OSI in questo caso si allontana leggermente da questa
definizione a causa della peculiare indipendenza tra i vari livelli che lo
compongono. Ciò che si ipotizza è uno schema di protocolli che, su vari
livelli, si scambino informazioni sul contesto in cui operano, favorendo l’a-
dattamento ai repentini cambiamenti che caratterizzano questa tipologia
di reti.
Esistono già dei protocolli creati con lo scopo di affrontare temi come
il routing dei pacchetti o l’accesso al mezzo trasmissivo in presenza di
host mobili. In questo lavoro di tesi verrano sottoposti ad una analisi
attenta e meticolosa i maggiori protocolli di livello MAC (Medium Ac-
cess Control) per reti WLAN (Wireless Local Area Network) e WPAN
(Wireless Personal Area Network) tra cui Hiperlan/2, Bluetooth e IEEE
802.11, cercando di individuare pregi e carenze di ognuno rispetto al
contesto ad hoc.
Una volta analizzato lo stato dell’arte per quanto concerne il livello
MAC si definirà un nuovo protocollo per l’accesso al mezzo, con aspetti
innovativi rispetto a quelli già esistenti, e con l’adozione di uno schema
di clustering per la gestione delle trasmissioni. Visto che le reti wireless
ad hoc sono prive di un’infrastruttura fissa e predefinita, si è pensato
di introdurne una virtuale creata a partire da algoritmi di clustering. In
questo modo gli host vengono raggruppati in entità logiche separate dette
cluster in cui la gestione dell’accesso al mezzo è totalmente organizzata
ed è affidata ad un particolare nodo detto clusterhead. Un tale approccio
risulta molto più elastico rispetto ad una infrastruttura cellulare e si
adatta facilmente a scenari con mobilità.
Il protocollo definito in questo lavoro di tesi prende il nome di CSMAC
(Clustered and Synchronized Medium Access Control) e si pone lo scopo
6 Capitolo 1. Introduzione
di risolvere alcune delle problematiche introdotte dalle reti wireless ad
hoc per quanto riguarda il controllo dell’accesso al canale. CSMAC inol-
tre getta le basi per una possibile estensione rivolta a favorire servizi di
orientati ai principi di soft Quality of Service
2
, ossia di applicazioni mul-
timediali che hanno particolari esigenze in termini di banda e affidabilità
delle connessioni.
2
Un contesto mobile wireless ad hoc è per sua natura molto variabile, quindi non
si può parlare di servizi di QoS veri e propri in assenza di un’infrastruttura fissa, ma
al massimo di soft-QoS
Capitolo 2
Protocolli MAC per reti wireless
In questo capitolo, dopo una breve panoramica iniziale delle proble-
matiche più ricorrenti nelle comunicazioni wireless ad hoc, verranno presi
in esame i principali protocolli MAC attualmente utilizzati per la gestio-
ne del canale trasmissivo. Si studieranno il funzionamento e le politiche
adottate per il controllo delle comunicazioni. Si ricercheranno e valu-
teranno potenzialità e carenze di ognuno di essi. Non si analizzeranno
i protocolli nella loro interezza, ma si cercherà di estrapolare i concet-
ti e le idee più interessanti che meglio risolvono i problemi legati alle
trasmissioni wireless ad hoc nell’ipotesi del sistema considerato.
Infine si porrà l’accento su quegli aspetti protocollari che hanno in-
fluenzato maggiormente la definizione di CSMAC.
2.1 Problematiche nelle comunicazioni wire-
less ad hoc
Tipicamente nelle comunicazioni wireless il mezzo trasmissivo che vie-
ne utilizzato è costituito dalle onde radio che si propagano codificando
l’informazione che si vuole trasmettere.
Una delle caratteristiche principali di questo tipo di segnali è il de-
cadimento della potenza residua all’aumentare della distanza. Quindi
può accadere che un segnale giunto a destinazione venga scartato, o non
rilevato, perché ha una potenza residua troppo bassa. Inoltre la pro-
7
8 Capitolo 2. Protocolli MAC per reti wireless
pagazione delle onde radio può essere ostacolata dalla presenza nell’am-
biente di strutture solide come pareti e simili che amplificano l’effetto del
decadimento del segnale.
La maggior parte dei dispositivi wireless per questioni fisiche e d’im-
plementazione, vengono costruiti in modo che possano lavorare solo in
modalità half-duplex. Questo significa che non sono in grado di trasmet-
tere e ricevere contemporaneamente. Ad esempio risulta impossibile per
un dispositivo che sta trasmettendo rilevare una collisione. Questo è uno
dei fattori vincolanti che condiziona maggiormente la progettazione di
protocolli MAC per reti wireless. Sempre per questo motivo, in questa
classe di protocolli si definiscono meccanismi di Collision Avoidance,vi-
sto che i tradizionali sistemi di Collision Detection usati dalle reti wired
non sono applicabili. Pertanto si cerca di adottare delle tecniche rivolte
a prevenire le collisioni, diminuendo la probabilità delle loro occorrenza
a priori, visto che non si è sempre in grado di rilevarle.
2.1.1 Cattura
Uno dei fenomeni tipici delle trasmissioni wireless è l’effetto cattura.
Capita quando due o più dispositivi trasmettono verso lo stesso desti-
natario. In questo caso il segnale ad essere catturato dal ricevente sarà
quello con potenza residua più alta, mentre gli altri verranno ignorati. La
diversa potenza residua di ricezione di un segnale dipende dalla distanza
alla quale si trova il ricevente rispetto al trasmittente e dalla potenza
trasmissiva utilizzata da quest’ultimo. L’effetto cattura può facilmente
tramutarsi in collisione nel caso di cui il ricevente si trovi pressoché equi-
distante dai generatori del segnale e le potenze di trasmissione utilizzate
siano le stesse.
È da notare che tutte le trasmissioni effettuate con un dispositivo ad
onde radio sono intrinsecamente in broadcast. Infatti tutti i nodi nel
raggio di azione del mittente ricevono le sue trasmissioni anche se queste
hanno espressamente indirizzi di unicast. Di conseguenza una qualsiasi
trasmissione anche se indirizzata ad uno specifico host può interferire con
qualsiasi altra di un nodo vicino. Questa proprietà provoca l’impegno del
2.1. Problematiche nelle comunicazioni wireless ad hoc 9
mezzo nell’intorno del trasmittente dando luogo ad una serie di problemi
di cui si parlerà nelle prossime sezioni.
Figura 2.1: Comunicazioni Wireless
2.1.2 Nodi nascosti
Nelle comunicazioni wireless si può verificare che o il mittente o il
ricevente si trovino ad essere esposti nei confronti delle trasmissioni dei
nodi vicini. Si considerino i quattro host mobili A, B, C e D in figura 2.1
e le loro rispettive aree di copertura rappresentante dalle circonferenze.
SisuppongacheilnodoAstiatrasmettendoalnodoB.IlnodoCèfuori
dalla portata
1
di A, pertanto non sente la trasmissione che quest’ultimo
ha intrapreso nei confronti di B. Quindi se C ha dei dati da trasmettere
a B inizia tranquillamente la trasmissione generando una collisione su C.
In questo caso si dice che i nodi A e C sono nascosti uno nei confronti
dell’altro. Per evitare situazioni del genere di solito si usano dei piccoli
messaggi di controllo che vengono trasmessi in broadcast per informare
tutti i vicini che si sta per iniziare a ricevere del traffico.
1
Raggio d’azione
10 Capitolo 2. Protocolli MAC per reti wireless
2.1.3 Nodi esposti
L’utilizzo di piccoli messaggi antecedenti la trasmissione vera e pro-
pria non risolvono del tutto i problema in quest’ambito. Infatti ripren-
dendolafigura2.1sisuppongacheBstiatrasmettendoadAecheC
ne sia al corrente. Se C ha dei dati da trasmettere a D, conclude er-
roneamente che non può intraprendere la comunicazione, nonostante il
nodo A sia fuori dalla sua portata. Il nodo C non può sapere se con le
sue trasmissioni genera collisioni o meno sul destinatario dei messaggi
di B, quindi è costretto ad attendere la fine delle comunicazioni di B.
Inoltre C non è a conoscenza della posizione di D rispetto a B, quindi
se C intraprende una trasmissione nei confronti di D potrebbe generare
una collisione su D se questo è nel raggio d’azione di B.
2.2 Hiperlan/2
Lo standard Hiperlan/2 è stato sviluppato dall’ETSI (European Te-
lecommunications Standards Institute) per la gestione di reti wireless. In
[Joh99] viene presentato il protocollo con particolare riferimento alla mo-
dalità infrastracture. È ancora in via di sviluppo una metodologia, detta
directmode, che permette a due host di dialogare direttamente. Il direct
mode però prevede comunque la presenza di un’entità centrale fissa di
controllo, quindi non esiste ancora una gestione delle comunicazioni in
ambienti privi di un’infrastruttura. Ciò nonostante esistono degli aspetti
di Hiperlan/2 che vanno cosiderati in quanto, riadattati in un contesto
ad hoc, permetterebbero di affrontare in modo più efficiente alcune pro-
blematiche connesse alle reti wireless. Un tipico esempio di utilizzo di
Hiperlan/2 è mostrato in figura 2.2. Questo protocollo è in grado di
gestire le comunicazioni tra entità fisse dette Access Point (AP) e termi-
nali mobili. Gli AP sono solitamente collegati ad una infrastruttura di
tipo wired come ad esempio una LAN (Local Area Network) e forniscono
servizi di connettività ai terminali mobili, ossia un qualsiasi dispositivo
portatile con capacità di calcolo, dotato di un’interfaccia wireless.
Il protocollo è suddiviso in tre livelli:
2.2. Hiperlan/2 11
Figura 2.2: Hiperlan/2 Network
• Physical layer (PHY)
• Data Link Control layer (DLC)
• Convergence layer (CL)
Il livello fisico si dintingue per l’utilizzo di una tecnica di modulazio-
ne per la trasmissione del segnale analogico detta OFDM (Orthogonal
Frequency Digital Multiplexing), adottata anche dai cellulari di ultima
generazione.
Il livello DLC comprende a sua volta altri sottolivelli tra cui il MAC,
l’Error Control (EC) e il Radio Link Control (RLC). RLC include a sua
volta altri moduli che si occupano della gestione delle associazioni da
parte dei terminali mobili.
Il livello CL ha il compito di adattare le richieste provenienti dai livelli
più alti in funzione dei servizi che il DLC può offrire. In aggiunta si occu-
pa anche della frammentazione dei pacchetti secondo i limiti specificati
dal DLC in modo da permetterne la trasmissione affidabile.
Ai fini di questa dissertazione, si analizzerà più a fondo il livello MAC
in modo da cogliere gli aspetti che hanno motivato alcune delle scelte
effettuate nella fase progettuale di CSMAC.
12 Capitolo 2. Protocolli MAC per reti wireless
Livello MAC di Hiperlan/2
Figura 2.3: MAC frame di Hiperlan/2
Il controllo del canale è di tipo centralizzato ed è affidato all’AP.
Gli host che hanno necessità di trasmettere inviano una richiesta all’AP.
Quest’ultimo, una volta collezionate tutte le richieste, provvederà in un
secondo momento a fornire informazioni sulle risorse allocate a ciascun
host. Ciò è possibile grazie ad una suddivisione logica del tempo sul cana-
le in slot. Il termine slot indica un intervallo temporale la cui lunghezza
viene stabilita dalle specifiche implementative del protocollo in questio-
ne. Il funzionamento dell’interfaccia wireless è basato sul TDMA (Time
Division Multiple Access), una tecnica di accesso al mezzo che risolve il
problema della contesa del canale assegnando ad ogni host slot diversi.
Da notare che il TDMA richiede un ambiente altamente sincronizzato,
difficile da mantenere in contesti prettamente ad hoc. Nel caso di Hiper-
lan/2 si può parlare di un’organizzazione dell’accesso al mezzo secondo
una strutturazione ben definita che prende il nome di MAC frame.Que-
sto tipo di struttura è ciclica nel tempo e si adatta dinamicamente alle
dimensioni del traffico. In Hiperlan/2 un MAC frame ha la lunghezza di
2 ms ed è composto da diverse fasi dette transport channels.Infigura
2.3 è illustrata la composizione di un MAC frame di Hiperlan/2.
Transport Channels
Le fasi che compongono un MAC frame di Hiperlan/2 sono: broa-
dcast (BCH), frame control (FCH), access feedback (ACH), downlink
2.2. Hiperlan/2 13
(DL), uplink (UL) e random access (RCH). La fase di broadcast è di ti-
po downlink ossia prevede un flusso di informazioni solo dall’AP verso gli
host e non viceversa. Nel BCH vengono trasmessi parametri fondamen-
tali per la sincronizzazione dell’intero MAC frame come istante d’inizio
e lunghezza dell’FCH e dell’RCH.
L’FCH, anch’esso di tipo downlink, contiene un’esatta descrizione
dell’allocazione delle fasi UL e DL del MAC frame corrente. In questo
modo ogni host viene a conoscenza delle presenza o meno di slot allocati
per le proprie trasmissioni.
Nella fase di access feedback l’AP informa gli host sull’esito degli ac-
cessi nel RCH immediatamente precedente. Nell’RCH l’accesso al mezzo
avviene in maniera totalmente distribuita, senza un minimo di coordina-
zione, quindi si possono verificare delle collisioni. In questo caso si dice
che l’accesso è “in contesa”. Se invece esiste un qualche meccanismo che
prevede una regolamentazione degli accessi al mezzo si parla di accesso
non in contesa. Questi concetti verranno approfonditi quando si parlerà
del protocollo IEEE 802.11.
Durante la fase RCH gli host inviano le proprie richieste di banda
in funzione della quantità e della tipologia del traffico che hanno da
trasmettere.
Una descrizione più dettagliata dei vari transport channels che com-
pongono il MAC frame di Hiperlan/2 può essere trovata in [Joh99].
La suddivisione del canale in fasi logiche proposta da Hiperlan/2 for-
nisce uno strumento efficiente per la gestione del canale. Con questo
sistema si riducono considerevolmente le collisioni in quanto l’accesso al
canale è quasi totalmente organizzato, eccezion fatta per la fase RCH.
Inoltre con il meccanismo di allocazione delle risorse su richiesta, si ha
la possibilità di attuare diverse politiche di scheduling, anche orientate
al QoS.
Il concetto di MAC frame di Hiperlan/2 verrà ripreso ed ampliato
nella progettazione di CSMAC in modo da garantire un certo livello di
affidabilità dell’utilizzo delle risorse. Come accennato in precedenza un
MAC basato su slot richiede un buon livello di sincronizzazione tra gli
host. In un ambiente ad hoc la sincronizzazione fra le varie interfacce
14 Capitolo 2. Protocolli MAC per reti wireless
wireless costituisce un fattore critico, che può essere tuttavia attenuato
in particolari condizioni topologiche. Sarà interessante vedere come in
CSMAC con l’ausilio di tecniche di clustering si riuscirà ad arginare il
problema.
2.3 Bluetooth
In questi ultimi anni numerose tipologie di device si sono dotate di
una particolare tecnologia wireless per instaurare delle connessioni ad
hoc: Bluetooth. Questo protocollo si distingue nella sua categoria per
robustezza, consumo energetico limitato e soprattutto per costi ridot-
ti. Queste caratteristiche sono giustificate dal fatto che si tratta di una
tecnologia relativamente poco complessa che quindi riduce i costi sia
d’implementazione che di gestione. Inoltre la sua portata limitata im-
plica un impiego minimo di risorse energetiche. Intorno a Bluetooth si è
sviluppato nel 1998 uno Special Interest Group (SIG) formato dalle più
importanti esponenti dell’Information Technology come 3COM, Erics-
son, Sony, Agere Systems e Microsoft con lo scopo di realizzare una spe-
cifica opensource per standardizzare le comunicazioni tra periferiche di
qualsiasi tipo. In figura 2.4 è descritto lo stack protocollare di Bluetooth.
Ai fini di questa ricerca, si concentrerà l’attenzione sul livello Base-
band che svolge il ruolo di controllore della risorsa radio e dei collegamenti
tra i vari device. I moduli soprastanti offrono altri servizi come auten-
ticazione, supporto al QoS, emulazione dell’RS-232 ed interfacciamento
con protocolli tipo TCP, WAP, e simili.
Solitamente in ambiente wireless ad hoc tutte le interfacce condivido-
no lo stesso canale e in assenza di un coordinatore diventa assai complesso
gestire in maniera distribuita gli accessi al mezzo limitando le collisioni.
Il livello fisico di Bluetooth utilizza come tecnica di modulazione del
segnale l’FHSS (Frequency Hopping Spread Spectrum) nella banda ISM
(Industrial Scientifical and Medical) che va dai 2,4 GHz ai 2,483 GHz.
In Bluetooth attraverso l’FHSS si suddivide la banda a disposizione in
sottocanali da 1 MHz, per un totale di 79 sottocanali. Durante una
trasmissione vengono effettuati dei cambi di frequenza da un sottocanale
2.3. Bluetooth 15
Figura 2.4: Bluetooth Stack
ad un altro in rapida successione, in modo da occupare una certa gamma
di frequenze per un tempo limitato. In questo modo si minimizzano le
interferenze e si aumenta la stabilità della connessione. La sequenza di
“salti” tra i 79 sottocanali disponibili viene detta hopping sequence ed
identifica un canale logico che, per come è stato definito, non interferisce
con gli altri.
Quando due o più dipositivi Bluetooth stabiliscono una connessione
sullo stesso canale logico formano una piconet. Più piconet interconnesse
presenti su una stessa area danno vita ad una scatternet. All’interno
di una piconet viene identificato un nodo master che svolge il ruolo di
coordinatore, mentre i gli altri host vengono definiti slave.
Così facendo anche su un area limitata possono convivere numerosi
device senza interferire tra di loro visto che le comunicazioni avvengono
su diversi hopping sequence. In Bluetooth ogni canale viene suddiviso
in slot di 625 µsec di lunghezza. Le trasmissioni all’interno di una pi-
conet vengono organizzate numerando gli slot ed assegnando quelli con
identificativo pari al master e quelli dispari agli slave.
16 Capitolo 2. Protocolli MAC per reti wireless
Figura 2.5: Bluetooth Piconet e Scatternet
Ciò significa che un master può iniziare le proprie trasmissioni solo
negli slot pari e analogamente uno slave solo in quelli dispari. In generale
una trasmissione si può protrarre per al massimo cinque slot, dopodiché
il mezzo deve essere rilasciato. L’uso di tanti canali separati va a scapito
del bandwith a disposizione di ogni piconet che difatti è dell’ordine di 1
Mbit. Ogni master può avere nella propria piconet fino ad un massimo
di sette slave attivi, cioè non in modalità power saving. Un host può far
parte di più piconet contemporaneamente ricoprendo sempre il ruolo di
slave. Una piconet ha uno ed un solo master che a sua volta può essere
anche slave in un’altra piconet. In figura 2.5 sono mostrati alcuni esempi
di piconet e scatternet. Tra master e slave a livello Baseband possono
essere stabiliti due tipi di collegamento:
• Synchronous Connection-Oriented (SCO)
• Asynchronous Connection-Less (ACL)
Il primo viene utilizzato per connessioni che richiedono una certa sin-
cronizzazione come lo scambio di segnali vocali. Praticamente il master
riserva periodicamente degli slot per i link di tipo SCO in modo da ga-
rantire la banda necessaria. Per tutti gli altri tipi di collegamenti che
2.3. Bluetooth 17
Figura 2.6: Diagramma degli stati di Bluetooth
non richiedono sincronizzazione si utilizzano link ACL. Il livello Base-
band amministra tra l’altro anche le fasi di Inquiry edipaging ossia le
procedure iniziali del protocollo che permettono ad un host di entrar a
far parte di una piconet. Il diagramma in figura 2.6 mostra gli stati che
un host può assumere durante il suo ciclo di vita. Gli stati principali so-
no standby e connection; gli altri rappresentano condizioni temporanee e
vengono impiegati ad esempio durante l’aggiunta di un nuovo nodo nella
piconet. . Lo stato di default di un dispositivo Bluetooth è standby in
cui tutte le attività sono ridotte al minimo, limitando così il consumo
energetico. Si supponga che un host H
A
abbia interesse ad associarsi
ad una piconet, o più in generale, che desideri scoprire se nel suo raggio
d’azione ci sono altri dispositivi Bluetooth. H
A
passa di conseguenza nel-