Protocolli MAC per reti wireless ad-hoc

Questo protocollo si basa sul protocollo ad accesso multiplo con prevenzione delle collisioni (MACA), proposto per risolvere alcuni problemi dei protocolli CSMA quando vengono utilizzati nelle reti wireless.

• CSMA (Carrier Sense Multiple Access)
  Nei protocolli CSMA, il sender (nodo che deve trasmettere) prima ascolta il canale:
  • se questo è occupato ritarda la trasmissione riprovando a sondare il canale dopo un tempo random;
  • se è libero il sender trasmette.

  Il protocollo CSMA prevede il sensing del canale solo presso il sender e non risolve il problema del terminale nascosto. In un tipico scenario di rete wireless sender e receiver non sempre si rilevano l'un l'altro. In queste situazioni la trasmissione di pacchetti da parte di un nodo è soggetta a collisioni presso il receiver, a causa di trasmissioni simultanee da parte di nodi nascosti. Inoltre, l'utilizzo della banda nei protocolli CSMA è basso a causa del problema del terminale esposto.

• MACA (Multiple Access with Collision Avoidance)
  Introdotto come alternativa ai tradizionali protocolli CSMA per le reti wireless. MACA non fa uso del carrier-sensing per l'accesso al canale: utilizza, invece, 2 pacchetti di segnalazione:
  1. il pacchetto RTS (request-to-send);
  2. il pacchetto CTS (clear-to-send).

  Quando un nodo deve trasmettere, invia prima un RTS. Il receiver, se è pronto a ricevere il pacchetto, invia un CTS. Se il sender riceve corretamente il CTS, inizia a trasmettere il pacchetto dati.

  Fonte

  Se un pacchetto trasmesso da un nodo viene perso, questo utilizza l'algoritmo BEB (binary exponential back-off) per attendere un intervallo random prima di riprovare. Secondo questo algoritmo, ogni volta che viene rilevata una collisione, il nodo raddoppia la sua finestra di back-off.

  • Problema del terminale nascosto (RTS/CTS - campo duration)

    I nodi vicini al sender che rilevano l'RTS non trasmettono per un periodo di tempo sufficiente a far ricevere il CTS al sender. Sia l'RTS che il CTS contengono il campo duration che indica la durata prevista per lo scambio dei pacchetti di dati. I nodi vicini al receiver che rilevano il CTS rimandano la loro trasmissione per un periodo di tempo sufficiente a far ricevere i pacchetti di dati al receiver. In questo modo il protocollo MACA risolve il problema del terminale nascosto.

  • Problema del terminale esposto

    Come già descritto, un nodo che rileva un pacchetto RTS rimanda la sua trasmissione per un periodo di tempo sufficiente a far arrivare il CTS al sender; se il CTS non viene rilevato durante questo periodo di attesa, il nodo è libero di trasmettere una volta scaduto il tempo. Pertanto, un nodo che rileva solo l'RTS è libero di trasmettere simultaneamente al sender dell'RTS che sta trasmettendo pacchetti di dati. In questo modo il MACA risolve il problema del terminale esposto.

• MACAW (Multiple Access with Collision Avoidance for Wireless LANs)
  Questo protocollo è stato progettato per risolvere alcuni problemi del MACA visto che, a causa dell'algoritmo di back-off BEB, quest'ultimo non consente un accesso equo al canale da parte di tutti i nodi che vogliono trasmettere.
  • Problema dell'accesso equo al canale (algoritmo MILD)

    Ad esempio si consideri uno scenario in cui vi siano 2 sender (S1 ed S2) ed un receiver (R2). Tutti e 2 i sender generano un alto volume di traffico. Il nodo che accede per primo al canale (ad esempio S1) inizia a trasmettere i pacchetti. I pacchetti spediti da S2 collidono presso il receiver R2, pertanto S2 incrementa la sua finestra di back-off seguendo l'algoritmo BEB. A causa di questo, la probabilità che S2 acceda al canale decresce sempre più e, dopo un pò, il nodo risulta completamente bloccato. Per risolvere il problema il protocollo MACAW utilizza un algoritmo di back-off modificato.

    L'header del pacchetto contiene un campo aggiuntivo contenente il valore corrente del timer di back-off del sender. Un nodo che riceve il pacchetto copia questo valore nel suo timer di back-off. Ciò assicura un accesso equo al canale da parte di tutti i sender. Un altro problema dell'algoritmo BEB è che esso modifica molto rapidamente il valore del timer di back-off, sia quando il nodo trasmette con successo, sia quando viene rilevata una collisione. Il timer di back-off viene settato al valore minimo ad ogni trasmissione con successo. Per ovviare a queste grandi variazioni del valore del timer di back-off il MACAW utilizza l'algoritmo MILD (multiplicative increase linear decrease). Secondo quest'ultimo algoritmo, dopo una collisione, il back-off è incrementato di un fattore moltiplicativo (1,5) e, dopo una trasmissione con successo, decrementato di 1. Questo permette di eliminare la contesa e quindi i lunghi periodi di contesa dopo ogni trasmissione con successo e, allo stesso tempo, consente un'incremento ragionevole dei valori di back-off quando la contesa è alta.

  • Equità dei flussi (code multiple)

    Un'altra modifica introdotta con il MACAW consiste nell'equità dei flussi, anziché l'equità dei nodi come nel MACA. Ogni nodo mantiene diverse code, ognuna per un flusso di dati, ed utilizza un timer di back-off diverso per ognuna di esse. Un nodo che deve trasmettere, deve prima determinare quanto tempo deve attendere prima di spedire un RTS ad ogni nodo di destinazione corrispondente ai primi pacchetti nelle code del nodo. Viene scelto pacchetto per il quale questo tempo di attesa è minore di tutti gli altri.

  • ACK

    Oltre ai pacchetti RTS/CTS utilizzati in MACA, MACAW utilizza un altro pacchetto di controllo: ACK. Nel MACA, la correzione degli errori di trasmissione è demamndata al livello trasporto; questo implica ulteriori ritardi nel recupero degli errori. MACAW, invece, gestisce gli errori di trasmissione direttamente a livello Data-Link, tramite l'uso dei riscontri (ACK). Nel MACAW, dopo la ricezione con successo di un pacchetto, il receiver trasmette un ACK. Se il sender non riceve l'ACK, rischedula la trasmissione del pacchetto precedentemente inviato ed incrementa il timer di back-off. Se l'ACK viene perso nella trasmissione, il sender riproverà a trasmettere un RTS per lo stesso pacchetto, ma questa volta il receiver manderà un ACK invece del CTS.

  • Problema del terminale esposto (DS)

    Nel MACA un nodo esposto, che riceve solo l'RTS e non il CTS, è libero di trasmettere contemporaneamente all'altro sender. Nello scenario in figura, durante la trasmissione di B ad A, il nodo C è libero di trasmettere, in quanto non rileva il CTS di A. C, quindi, invia un RTS a D e quest'ultimo restituisce un CTS che, però, non verrà ricevuto correttamente da C in quanto colliderà con i pacchetti della trasmissione tra B ed A. Per questo motivo, C incrementerà inultimente il suo timer di back-off. Un nodo esposto, quindi, non dovrebbe trasmettere.

    Fonte

    Il problema consiste nel fatto che un nodo esposto non è a conoscenza se lo scambio RTS/CTS è andato a buon fine (il nodo esposto non riceve il CTS). Il MACAW risolve questo problema utilizzando un ulteriore pacchetto di controllo (DS); questo pacchetto (Data-Send) contiene informazioni sulla durata della trasmissione dati. In questo modo un nodo esposto che rileva un DS è a conoscenza che uno scambio RTS/CTS è andato a buon fine e può ritardare la sua trasmissione di un periodo sufficiente a far terminare la trasmissione DATA-ACK.

  • Request-for-Request-To-Send (RRTS)

    Il MACAW utilizza un altro pacchetto di controllo: l'RRTS. Si consideri lo scenario in figura: S1 sta trasmettendo ad R1. Il nodo S2 vuole trasmettere ad R2, che, essendo vicino di R1, riceve il CTS da esso e quindi ritarderà le sue trasmissioni. Il nodo S2 non è a conoscenza del periodo durante il quale esso può contendere il canale e quindi riproverà ad accedere al canale aumentando il suo timer di back-off ad ogni tentativo fallito. Il problema consiste nel fatto che S2 non ha informazioni aggiornate riguardo lo stato delle trasmissioni in corso.

    

    Il protocollo MACAW risolve questo problema usando il pacchetto RRTS. Se il nodo R2 ha già ricevuto un RTS da S2, ma non ha risposto con un CTS per via della trasmissione in corso tra S1 ed R1, attenderà il prossimo periodo di contesa ed invierà ad S2 un RRTS (Request-for-Request-To-Send). I nodi vicini a R2 che ricevono un RRTS (incluso R1) dovranno attendere per due slot successivi (per far in modo che avvenga lo scambio RTS/CTS). Il sender S2, che riceve l'RRTS da R2, trasmetterà un regolare RTS a R2 e si continuerà con il normale scambio di pacchetti (RTS/CTS/Data/ACK).

  • Riepilogo

    Nella figura seguente viene riportato l'intero schema di funzionamento del protocollo MACAW:

    Fonte

    Per riassumere, il protocollo MACAW si basa sulle seguenti osservazioni:

    1. La congestione rilevante avviene presso il receiver e non presso il sender. Questo rende i protocolli CSMA non adatti alle reti wireless ad-hoc, e quindi si rende necessario lo scambio RTS/CTS/Data/ACK di MACA. Il MACAW lo migliora usando lo schema RTS/CTS/DS/Data/ACK.
    2. La congestione non dipende dalla posizione del receiver; quindi, invece di caratterizzare il back-off come singolo parametro, vengono utilizzati diversi back-off separati per ciascun flusso di dati.
    3. Conoscere la congestione ai vari nodi rappresenta un'attività collettiva. Per questo motivo è stato introdotta nel MACA la copia dei valori di back-off estratta dai pacchetti ricevuti.
    4. Per contendere il canale in maniera efficace, devono essere propagate informazioni di sincronizzazione ai nodi interessati: si pensi all'introduzione dei pacchetti di controllo DS ed RRTS.

I protocolli FAMA sono basati su una disciplina di accesso al canale che consiste di carrier-sensing e di un dialogo tra il sender ed il receiver per la prevenzione delle collisioni. "Floor acquisition" si referisce al processo di acquisizione del canale. Ad ogni istante di tempo prefissato, il controllo del canale è assegnato ad un solo nodo a cui è garantita la trasmissione di uno o più pacchetti verso diverse destinazioni, senza avere collisioni. Il carrier-sensing effettuato dal sender, insieme allo scambio di pacchetti RTS/CTS, risolve il problema del terminale nascosto come nel MACA, ed è efficiente come il CSMA in altre situazioni. Il protocollo FAMA richiede che un nodo che abbia da trasmettere debba prima acquisire il canale tramite lo scambio di pacchetti di controllo. Sebbene questi pacchetti possano collidere con altri, una volta che il nodo ha acquisito il canale viene garantito che la trasmissione dati avvenga senza nessuna collisione. Due versioni di FAMA verranno descritte in questa sezione:

1. scambio di RTS/CTS senza carrier-sensing (viene utilizzato il protocollo ALOHA per trasmettere i pacchetti RTS);
2. scambio di RTS/CTS con carrier-sensing non persistente¹ (viene utilizzato quest'ultimo protocollo per trasmettere i pacchetti RTS).

¹ Il sender ascolta il canale e, se questo è occupato, riprova l'ascolto dopo un tempo casuale. Se invece il canale è libero il nodo trasmette subito.

• MACA
  Il protocollo MACA (Multiple Access with Collision Avoidance), che è stato introdotto precedentemente, ricade nella categoria dei protocolli FAMA. Come già descritto, nel MACA i nodi non ascoltano il canale: un nodo ritarda la sua trasmissione solo se riceve un RTS o un CTS. In questo protocollo, i pacchetti RTS sono soggetti a collisioni. In accordo con i principi dei protocolli FAMA, per garantire una trasmissione dati priva di collisioni, il campo duration dell'RTS deve essere impostato almeno pari a due volte il ritardo massimo di propagazione del canale. La trasmissione di burst di pacchetti non è possibile nel MACA.
• FAMA-NTR (FAMA Non-persistent Transmit Request) o FAMA-NCS
  Questo protocollo è una versione modificata del MACA che permette la trasmissione di burst di pacchetti impostando i tempi di attesa sui nodi in maniera proporzionale al tempo di propagazione del canale. Prima di inviare un pacchetto, il sender ascolta il canale:
  • se il canale è occupato, il sender attende un periodo di tempo random e riprova più tardi;
  • se il canale è libero, il sender trasmette un pacchetto RTS.

  Dopo aver inviato l'RTS, il sender ascolta il canale per un round-trip-time oltre al tempo richiesto dal receiver per inviare un CTS. Se non riceve il CTS durante questo periodo di tempo o se il CTS ricevuto è corrotto, il sender attende un periodo di tempo random prima di riprovare. Una volta ricevuto correttamente il CTS, il sender può trasmettere un burst di pacchetti di dati. Il burst è limitato da un numero massimo di pacchetti di dati, superato il quale il sender deve rilasciare il canale e contenderselo nuovamente con gli altri nodi.

Il BTMA è uno dei più recenti protocolli proposti per risolvere il problema del terminale nascosto, tipico degli ambienti wireless. Il canale di trasmissione è suddiviso in due:

1. un canale dati, utilizzato per la trasmissione di pacchetti di dati;
2. un canale di controllo, utilizzato per la trasmissione del segnale busy tone.

Quando un nodo è pronto a trasmettere, ascolta il canale per vedere se è il segnale busy tone è attivo:

• se non è attivo, attiva il segnale busy tone ed inizia la trasmissione dati;
• altrimenti, rischedula la trasmissione del pacchetto e riprova dopo un tempo random.

Ogni altro nodo che ascolta la trasmissione dati sul canale attiva il segnale busy tone sul canale di controllo. In questo modo, quando un nodo sta trasmettendo, a nessun altro nodo, che si trova all'interno di una distanza di 2 hop dal sender, è permesso di trasmettere contemporaneamente. Quindi, sebbene la probabilità di collisione nel BTMA è molto bassa, l'utilizzo della banda è molto bassa.

Questo protocollo è un'estensione del BTMA. Anche qui il canale è suddiviso in:

• canale dati, utilizzato, come nel BTMA, per la trasmissione dei dati;
• canale di controllo, utilizzato per la trasmissione dei pacchetti di controllo RTS/CTS e dei segnali busy tone.

DBTMA fa uso di 2 busy tone:

• BT_t, utilizzato da un nodo per segnalare la sua trasmissione dati;
• BT_r, utilizzato da un nodo per segnalare la ricezione di dati.

I due busy tone sono due onde sinusoidali con frequenze differenti e ben separate.

Quando un nodo è pronto a trasmettere un pacchetto di dati, prima ascolta il canale per determinare se BT_r è attivo. Un BT_r attivo indica che un nodo nelle vicinanze sta ricevendo pacchetti di dati. Se il nodo non rileva nessun BT_r, trasmette un RTS sul canale di controllo. Alla ricezione dell'RTS, il receiver controlla se il segnale BT_t è attivo. Se cosí fosse, significa che qualche altro nodo nelle vicinanze sta trasmettendo e quindi, per il momento, esso non può ricevere pacchetti. Se il BT_t non è attivo, il receiver risponde inviando un CTS e attivando il segnale BT_r (che informa gli altri nodi nelle vicinanze che esso sta ricevendo). Il sender, una volta ricevuto il CTS, attiva il segnale BT_t (informando i nodi nelle vicinanze che esso sta trasmettendo) ed inizia a trasmettere i dati. A trasmissione conclusa, il sender disattiva il segnale BT_t ed il receiver il segnale BT_r.

Se confrontato con gli altri protocolli basati sullo scambio RTS/CTS (come il MACA ed il MACAW), il DBTMA presenta un migliore utilizzo della banda. Questo poiché gli altri protocolli bloccano sia la trasmissione in avanti, sia quella all'indietro sul canale dati, quando "prenotano" il canale con gli RTS ed i CTS. Ma nel DBTMA, quando un nodo sta trasmettendo o ricevendo, sono bloccati rispettivamente solo i canali inverso (ricezione) o diretto (trasmissione). Per questo motivo, l'utilizzo della banda del DBTMA è circa il doppio di quella utilizzata dagli altri protocolli basati su RTS/CTS.