3.5 Processo di anticollisione

La comunicazione RFID fallisce nel caso in cui due transponder cerchino di comunicare contemporaneamente. Quando ciò avviene, la comunicazione ricevuta dal reader è la fusione di due comunicazioni ed è quindi indecifrabile; si parla in questo caso di collisione.
Per risolvere questo problema esistono diversi protocolli di anticollisione: i più semplici richiedono tag di scarsa complessità circuitale (e quindi più economici), ma a discapito della rapidità di lettura. I protocolli più veloci richiedono invece tag più costosi poiché devono essere capaci di compiere operazioni di una certa intelligenza.
Un protocollo di base che sfrutta il metodo TDMA (Time Division Multiple Access) prevede che ad ogni transponder venga assegnato un preciso slot temporale nel corso del quale trasmettere i propri dati. L’assegnazione dello slot viene fatta in base alle ultime due cifre del UId del tag [BAT03].
Visto che ogni tag può inviare i propri dati solo durante lo slot a lui assegnato, il rischio di collisioni si potrebbe pensare che sia nullo. Nel caso reale però è facile trovare in commercio tag con le ultime due cifre dell’UId identiche.  Inoltre operare secondo questo metodo significherebbe ritardare il momento della lettura in modo proporzionale al numero dei tag. Tranne il caso in cui il numero dei transponder è molto basso, tale ritardo rende inefficiente il protocollo, che quindi non viene mai utilizzato.
I protocolli di anticollisione utilizzati nell’RFID cercano di minimizzare il più possibile l’attesa. Esistono due famiglie di protocolli: stocastici e deterministici. Nei primi, il momento in cui i transponder possono inviare i propri dati avviene in modo casuale; nei secondi invece tale momento è calcolato secondo precise tecniche [PATc].

3.5.1 I protocolli stocastici

I protocolli stocastici derivano dal protocollo Aloha, nato negli anni ’70 per risolvere un problema della comunicazione radio: molte stazioni radio, che condividono lo stesso canale comunicativo, devono inviare ad una stazione centrale pacchetti di informazioni generati a istanti non prevedibili; le sorgenti sono indipendenti e non hanno possibilità di comunicare l’una con l’altra.
La soluzione scelta è la seguente: appena una stazione ha qualcosa da trasmettere, lo fa immediatamente; in caso di collisione attende un tempo casuale e ritrasmette i propri dati. In caso di ulteriori collisioni la procedura viene ripetuta. In questo modo, il ritardo subito da un pacchetto dal momento in cui è stato inviato fino a quello in cui è correttamente ricevuto è generalmente limitato [PET01].
Questa situazione è analoga ad un sistema RFID: le stazioni radio possono essere immaginate come i transponder e la stazione centrale come il reader. In caso di traffico moderato la probabilità di collisione è ridotta e solo di rado si rende necessaria una nuova trasmissione. Al contrario, con il verificarsi di traffico intenso le collisioni diventano molto frequenti e il continuo ingresso di nuovi pacchetti le moltiplica rendendo il sistema instabile. E’ per questo che per potere gestire i sistemi RFID il protocollo Aloha è stato modificato, facendo nascere diverse nuove tecniche.
Per poterle comprendere è necessario sapere che nei sistemi a radiofrequenza le modalità in cui la lettura può avvenire sono due [BEN04]:

  • Free access: i transponder inviano i propri dati appena entrano in una zona di trasmissione di un reader e li ritrasmettono fino a che la lettura non va a buon fine.
  • Blocked access: è il reader che decide quando interrogare i transponder presenti nella sua zona. Il reader invia il segnale di inizio lettura che rende i transponder presenti come gli unici partecipi del processo; da quell’istante i transponder che potrebbero entrare nella zona non sarebbero abilitati a trasmettere.

Nei prossimi paragrafi vengono trattati i protocolli più importanti. Essi fanno tutti parte della tipologia blocked access (la più utilizzata) e possono essere classificati in tre categorie: Pure, Slotted, e Framed (fig. 3.17).


Fig. 3.17  Classificazione dei protocolli Aloha


3.5.1.1 I protocolli Aloha Pure

Aloha Pure Free Running
Il reader comunica ai tag solo quando deve iniziare e terminare la lettura. In questo lasso di tempo ogni tag comunica continuamente, ma ad intervalli casuali, il proprio codice (fig. 3.18).
Se il numero di transponder da gestire è basso, la probabilità di collisione è ridotta e solo di rado si rende necessaria una nuova trasmissione. Al contrario, se il numero di transponder è alto, le collisioni diventano molto frequenti e il continuo ingresso di nuovi pacchetti le moltiplica rendendo il sistema instabile [BEN04].


Fig. 3.18  Protocollo Aloha Pure Free Running

Aloha Pure Switch Off
E’ simile al metodo precedente, ma con un grosso miglioramento. Come prima, i transponder tentano in modo casuale di inviare il proprio codice, ma continuano a farlo solamente finché i dati non sono stati letti correttamente. Infatti, quando ciò avviene, il reader manda un segnale di ACK (acknowledgement) al relativo transponder che da quel momento cessa di prendere parte al processo di lettura (fig. 3.19) [BUR04].
In questo modo il rischio di collisioni diminuisce col passare del tempo, ed è possibile gestire anche centinaia di transponder.
Questo protocollo può essere anche utilizzato in modalità Free Access [BEN04].


Fig. 3.19  Protocollo Aloha Pure Switch Off

Aloha Pure Fast
Nel metodo precedente il reader riusciva a gestire le collisioni tramite segnali di ACK. Questo protocollo, chiamato anche Carrier Sense, prevede invece dei segnali di MUTE [BUR04].
Il segnale di MUTE, al contrario dell’ACK, viene inviato appena un transponder comincia a trasmettere ed è indirizzato a tutti i tag ad eccezione di quello che sta trasmettendo: esso blocca le azioni dei tag per un tempo pari alla durata di uno slot, mandando sicuramente a buon fine la lettura dell’unico tag rimasto che al momento sta trasmettendo (fig. 3.20).
Questo protocollo assicura una buona gestione delle collisioni, anche se richiede un reader più complesso. Per poter essere in grado di leggere e contemporaneamente inviare il segnale di MUTE, infatti il reader deve disporre di una doppia antenna [BEN04].


Fig. 3.20  Protocollo Aloha Pure Fast

Aloha Pure Fast Switch Off
E’la combinazione dei precedenti due metodi. Il reader comunica con i transponder attraverso segnali di ACK e di MUTE (fig. 3.21).
Questo metodo richiede una notevole complessità circuitale e quindi costi maggiori che vengono però ripagati da un tempo di comunicazione nettamente più breve rispetto a quello dei precedenti metodi, soprattutto in presenza di diverse centinaia di transponder [BEN04].


Fig. 3.21  Protocollo Aloha Pure Fast Switch Off


3.5.1.2 I protocolli Aloha Slotted

Per tutti i protocolli dell’Aloha Pure si ha una comunicazione asincrona, in quanto localizzata esclusivamente all’inizio o alla fine di una trasmissione del tag.
L’Aloha Slotted prevede invece una comunicazione sincrona, mediante una divisione del tempo in slot temporali della lunghezza di un pacchetto trasmesso dal tag.
Il reader comunica ai transponder l’inizio di un nuovo slot ed ogni tag, con il solito processo di estrazione casuale, decide se trasmettere oppure no nello slot attuale.
Nel caso in cui non venga inserito nessun altro segnale di comunicazione, il protocollo assume il nome di Aloha Slotted Free Running; se il reader invece prevede il segnale di ACK (in maniera analoga al metodo Aloha Pure Switch Off), si ha la modalità Aloha Slotted Switch Off. Per quest’ultima modalità, analogamente all’Aloha Pure, può essere effettuata anche una lettura in modalità Free access.
L’Aloha Slotted Switch Off permette buone comunicazioni, anche se quelle gestite con Aloha Pure Fast Switch Off sono più veloci. Per ottenere comunicazioni ancora più veloci si potrebbe pensare ad un Aloha Slotted Fast Switch Off, ma ciò è poco fattibile poiché essa richiederebbe una complessità circuitale troppo elevata [BEN04].


3.5.1.3 I protocolli Aloha Framed

I protocolli più evoluti lavorano con i frame, cioè con insiemi di slot. Il numero di slot che compongono un frame solitamente non è fisso, ma è comunicato dal reader ai tag ed è scelto secondo criteri di massimizzazione della velocità di lettura.
Ogni tag invia i propri dati durante uno slot ancora casuale, ma tale invio accade solo una volta ogni frame, in modo da limitare le possibili collisioni.
I metodi principali di Aloha Framed sono due: I-Code e ISO 18000.

I-Code
Questo protocollo è stato brevettato dalla Philips Semiconductors. Il suo funzionamento è analogo a quello del protocollo Aloha Slotted Free Running, ma invece di lavorare con gli slot, lavora con i frame.
Il numero di slot di un frame è variabile: esso è scelto, mediante una stima dei tag presenti nel campo. Questa stima è calcolata dal reader in base al numero di collisioni e di successi rilevati. Alla fine di ogni frame, il numero di slot del frame successivo viene dimensionato di conseguenza. Naturalmente questo calcolo non può avvenire per il primo frame, il quale avrà una dimensione prestabilita [BEN04].

ISO 18000 (Aloha Framed Switch Off)
L’ultima evoluzione del metodo Aloha è uno dei due protocolli riconosciuti dallo standard 18000-6. Il funzionamento di questo algoritmo è analogo a quello dell’Aloha Slotted Switch Off, con l’organizzazione degli slot in frame [ISO18000].
Le caratteristiche sono quelle del protocollo I-Code, con in aggiunta l’utilizzo del segnale di ACK. Grazie ad esse le prestazioni migliorano notevolmente: in caso di numerosi transponder (anche migliaia) è il protocollo più rapido, anche se è quello che richiede la comunicazione più intensa tra reader e tag.
 

3.5.2 I protocolli deterministici

A differenza dei protocolli stocastici che derivano tutti dal metodo Aloha, nei protocolli deterministici non esiste un metodo base: essi sono nati ognuno da un’idea specifica.
E’ tuttavia possibile attuare una classificazione in due categorie distinte: alla prima appartengono i protocolli che risolvono le collisioni basandosi solo sul numero seriale dei transponder (protocolli totalmente deterministici); i protocolli della seconda categoria non si servono dell’UId, ma di un generatore di numeri casuali posto su ogni transponder (protocolli deterministici con elemento casuale) [PATc].

Binary Search
Tra i protocolli totalmente deterministici uno dei più utilizzati è quello di ricerca binaria, il quale necessita, per un corretto funzionamento, di due elementi chiave:

  • una sincronizzazione sui bit di codice risposti contemporaneamente da più transponder interrogati dal reader.
  • un livello di logica sul transponder che permetta di individuare se il codice inviato dal reader è di valore maggiore, oppure minore, di quello posseduto dal transponder.

Il funzionamento dell’algoritmo è schematizzato nella figura 3.22 ed è qui di seguito descritto.
Ad ogni passo dell’algoritmo il reader invia un numero e, in modo sincronizzato, i tag che hanno un UId di valore inferiore o uguale a tale numero trasmettono il proprio codice identificativo.
Al primo passo dell’algoritmo il reader invia ai transponder il massimo numero ottenibile. Per esempio, in caso di tag con UId a 8 bit, il numero inviato dal reader sarà 255, cioè “11111111”. Tutti i tag verificano di avere il proprio codice minore o uguale a 255 e lo inviano.
Grazie alla sincronizzazione dei transponder, il reader riesce ad individuare i bit sui quali è avvenuta una collisione. Questo significa che i transponder hanno UId che differiscono tra loro in quei determinati bit.
A questo punto, a partire dal primo bit più significativo su cui si è riscontrata una collisione, il reader invia un codice che restringe il campo dei tag che possono rispondere; per fare ciò, basta prendere il vecchio codice e porre a 0 tale bit.
Si procede in questo modo finché non rimane un solo tag a rispondere. Il codice di quel tag viene quindi identificato dal reader, che successivamente disabiliterà il transponder.
Il percorso di ricerca riprende dall’ultima richiesta precedente alla scoperta del codice e termina quando il reader scopre il codice dell’ultimo tag rimasto [BEN04].


Fig. 3.22  Funzionamento del Binary Search in caso di 4 transponder con codici presenti.
La freccia uscente significa che il tag  di rispettivo
UId è stato identificato e quindi disattivato.


Stack ISO 18000
Questo protocollo è l’altro metodo riconosciuto dallo standard ISO 18000-6 (il primo metodo è già stato trattato nei precedenti paragrafi) e fa parte dei protocolli deterministici con elemento casuale [ISO18000].
L’algoritmo infatti non lavora in base all’UId dei tag, mentre necessita dei seguenti elementi chiave:

  • un generatore casuale su ogni tag di un numero che può assumere solo i valori “0” o “1”.
  • un contatore su ogni tag che mantenga memoria di un numero intero e lo aggiorni durante lo svolgimento dell’algoritmo. Quando questo contatore assume un valore maggiore di zero il tag non è abilitato a inviare il proprio UId.

Il funzionamento dell’algoritmo è facilmente intuibile studiando il diagramma degli stati dei tag (visualizzato in figura 3.23) che viene di seguito trattato.
Ogni transponder può assumere uno dei seguenti stati:

  • WAIT (tag in attesa): il tag non può inviare il proprio UId. Il reader può provocare l’incremento o il decremento del contatore. Quando il contatore raggiunge il valore zero il tag passa allo stato ACTIVE.
  • ACTIVE: (tag attivo): il tag invia il proprio UId. Se non si verificano collisioni il tag passa allo stato SLEEP, altrimenti rimane nello stato ACTIVE (nel caso il generatore casuale dia il risultato “0”) oppure ritorna allo stato WAIT (nel caso il generatore dia “1”).
  • SLEEP (tag disattivato): il transponder non può più partecipare alla sessione di lettura.

Quando un reader decidere di iniziare una lettura in blocked access, tutti i transponder che partecipano alla sessione azzerano il proprio contatore e inviano quindi al reader il proprio UId.
Il reader ogni volta che rileva delle collisioni invia un segnale di FAIL che provoca l’incremento dei contatori dei tag; ogni volta che invece rileva una corretta comunicazione oppure non rileva nessun traffico invia un segnale di SUCCESS che provoca il decremento dei contatori dei tag. Se il SUCCESS si è verificato in seguito alla trasmissione di un tag, il reader ne acquisisce l’UId e lo disattiva.
L’algoritmo ha termine quando sono stati letti tutti gli UId dei transponder, cioè quando non si ha più traffico verso il reader poiché tutti i tag sono bloccati nello stato di SLEEP [BEN04].


Fig. 3.23  Diagramma degli stati di un tag funzionante tramite protocollo Stack


<< Sezione precedente                                                           Sezione successiva >>