Capitolo 2 – I protocolli deterministici

Capitolo 2 – I protocolli deterministici

2.1 - Concetti generali

In questo capitolo saranno trattati tutti quei protocolli che si basano su idee alternative a quella seguita nella procedura Aloha. Tali protocolli sono identificati con il nome generico di protocolli deterministici, appellativo scelto soprattutto per sottolineare la complementarità dei concetti su cui si fondano i protocolli di tipo Aloha e quelli di tipo deterministico. L’impossibilità di utilizzare un termine più preciso per indicare questi ultimi deriva dal fatto che ciascun protocollo ha avuto origine da un’idea specifica che, pur non essendo del tutto esclusiva e priva di parentela con quelle degli altri protocolli, rende difficile individuare una matrice comune.

I protocolli deterministici sono suddivisi in due categorie distinte: alla prima appartengono i protocolli che risolvono le collisioni basandosi solo sul numero seriale dei transponder; i protocolli della seconda categoria non si servono del codice identificativo, ma di un generatore di numeri casuali posto su ogni transponder. Sebbene fino ad ora, con l’analisi dell’Aloha, siano stati già considerati protocolli che usano come motore del processo un generatore casuale su ciascun tag, i protocolli che verranno presi in esame utilizzano tale generatore in un modo talmente differente da rendere improprio ogni confronto con un algoritmo Aloha. Questi ultimi saranno chiamati protocolli deterministici con un elemento casuale, mentre quelli che impiegano esclusivamente il codice binario prenderanno il nome di totalmente deterministici. Un solo protocollo totalmente deterministico, la ricerca ad albero dal nome del suo ideatore Capetanakis, era già utilizzato negli anni ’80 come tecnica per risolvere il problema delle collisioni nelle comunicazioni radio tra molte sorgenti indipendenti ed un lettore centrale. Dall’idea di Capetanakis nacque, per il medesimo scopo, una ricerca ad albero che, come elemento discriminante,

invece del codice utilizza un elemento casuale posto sul tag. Questi due tipi di ricerca ad albero sono stati adattati per un impiego nel campo RFID.

Stack ISO 18000 Random tree Contactless Binary search Tree search (Capetanakis)

TOTALMENTE CON ELEMENTO_CASUALE

DETERMINISTICI

Memoryless

Basic Aggressive Shortcutting advancement Optimal Binary search Optimal random tree Optimal

Figura 2.1 Schema rappresentativo dei protocolli deterministici. La distinzione riguarda i protocolli che non si servono di alcuna casualità per lo svolgimento dell’algoritmo (totalmente deterministici) e quelli che invece

utilizzano un elemento casuale.

Gli altri protocolli deterministici sono stati ideati solo negli ultimi anni, esclusivamente per risolvere il problema delle collisioni nei sistemi RFID. Tra i protocolli totalmente deterministici sono interessanti il ‘Memoryless’, la ricerca binaria ed il ‘Contactless’; come protocolli deterministici con un elemento casuale sono presi in esame l’albero casuale ed il protocollo ‘Stack’ proposto dallo standard ISO 18000. Solo per una piccola parte dei protocolli analizzati è possibile ottenere alcune espressioni analitiche, limitate al numero medio di iterazioni necessarie a portare a termine la lettura in funzione del numero dei transponder presenti. Per avere un quadro più completo della prestazione di ogni singolo protocollo, così come è stato fatto per i molteplici protocolli Aloha, si provvederà dunque a simulare il comportamento di ciascuno di essi. Se per i protocolli che utilizzano il generatore casuale è evidente che, in analogia con l’Aloha, la simulazione è di tipo Monte

Carlo, per gli algoritmi totalmente deterministici occorre una precisazione preliminare prima di giungere alla medesima conclusione. Dal momento infatti che la direzione intrapresa dall’algoritmo dipende solo dai codici dei tag presenti, è possibile effettuare una simulazione di Monte Carlo generando tanti codici quanti sono i transponder presenti, in modo casuale, all’inizio di ogni nuova simulazione.

Un’importante differenza dei protocolli deterministici rispetto al metodo di analisi dei dati che veniva usato per quelli Aloha è dovuta allo svolgimento temporale dell’ algoritmo. Nei protocolli Aloha, ad eccezione di quelli Framed, dall’inizio di una lettura globale il tempo di lettura è pari a quello in cui trasmettono i transponder in quanto il reader interviene senza che le comunicazioni dei transponder siano interrotte. Con ottima approssimazione la stessa cosa può essere detta anche per i due protocolli Aloha Framed: nonostante che all’inizio di ogni nuovo frame i tag ascoltino la comunicazione del reader, tale intervento è di durata trascurabile rispetto all’estensione di un frame. Al contrario, nei protocolli deterministici il tempo in cui il reader comunica con i tag per dirigere lo svolgimento dell’algoritmo è una frazione significativa del tempo totale di lettura. Inoltre, poiché in molti algoritmi i tag non trasmettono ogni volta l’intero codice ma solo una parte, è significativo utilizzare come unità di misura per il tempo, oltre allo slot in cui un tag invia l’intero codice, il tempo di bit inviato dal reader o dal tag. Così come è stato sempre detto per i protocolli Aloha, uno slot rappresenta la durata temporale della trasmissione dell’intero codice che generalmente nell’RFID è composto da 64 bit.

2.2 - Protocolli totalmente deterministici

2.2.1 - Tree search (Capetanakis)

Il metodo della ricerca ad albero nasce alla fine degli anni ‘70 per risolvere il problema dell’accesso multiplo di più sorgenti indipendenti che inviano i loro pacchetti ad una stazione centrale.Il primo e il più importante contributo pubblicato in ordine di tempo su tale argomento è l’articolo di John Capetanakis, ‘Tree Algorithms for Packet Broadcast Channels’1 [5], all’interno del quale è esposto un metodo pensato per la tecnica di accesso multiplo. Com’è noto, l’accesso multiplo si basa sulla modalità Free access e la limitazione fondamentale a cui si va incontro con questo approccio è il limite superiore al numero medio di nuovi pacchetti che si possono ricevere in uno slot. Un numero medio di pacchetti entro tale limite consente al sistema di lavorare a regime e leggere i nuovi pacchetti dopo un tempo medio finito; al contrario, andando oltre questo limite, il numero di pacchetti da leggere supera la capacità di lettura del sistema e questa differenza aumenta sempre più per effetto del crescente numero di collisioni. Se l’arrivo di nuovi pacchetti è modellato da un processo di Poisson, con infinite ed indipendenti sorgenti che collettivamente trasmettono k pacchetti per ogni slot, con k variabile aleatoria di Poisson a media λ, come è dimostrato in [5], il throughput medio corrisponde proprio a λ . Dall’ analisi teorica è individuato in 1/3 il limite del valore di λ oltrepassato il quale il sistema non riesce a lavorare a regime. Questo dato è ben evidenziato in Figura 2.2: in essa sono riportati, al variare di λ, i limiti superiori e inferiori del tempo medio che un pacchetto deve attendere da quando entra nella

[5] John Capetanakis. “Tree Algorithms for Packet Broadcast Channels”. IEEE trans. on information theory, vol.it-25,no.5, pp.505-515, September 1979.

zona di interrogazione fino a quando non viene letto correttamente. Per il valore di λ che si avvicina ad 1/3 il ritardo medio cresce portandosi sull'asintoto verticale e il throughput di conseguenza si avvia a diventare nullo.

Figura 2.2 Limiti superiori e inferiori del ritardo medio sperimentato da un singolo transponder in funzione del λ del processo di Poisson (la figura è tratta da [5]).

Questo protocollo, così come è avvenuto nel caso dell’Aloha, può essere adattato alla modalità Blocked access. Facendo l’ipotesi che i pacchetti trasmessi dai tag siano tutti della medesima lunghezza e la comunicazione avvenga all’interno di slot temporali predefiniti, il reader invia il segnale per iniziare una lettura completa e solo i tag presenti in quel momento partecipano al processo di lettura. La discriminante fondamentale per lo svolgimento dell’algoritmo è il codice binario, unico per ogni transponder. In Figura 2.3 è rappresentato l’albero nella sua completa espansione, quando il codice ha una dimensione di soli quattro bit, da cui deriva che il numero di tag presenti può essere al massimo 16 . Con Si sono indicate le sorgenti, cioè i tag presenti nel momento in cui si decide di effettuare una nuova lettura; nell’esempio i loro codici sono rappresentati dai numeri interi

0, 2, 4, 8 e10. La corrispondenza con il codice binario è tale che, ad esempio, al codice S2 è associata la sequenza di bit ‘0010’.

Figura 2.3 Grafico dell’albero nel quale cinque sorgenti, su un massimo di sedici, sono presenti.

Si definisce la profondità di un nodo come il numero di rami che intercorrono tra il nodo stesso e la radice. Ne consegue che con nij è indicato un nodo dell’albero, dove l’indice i rappresenta la profondità del nodo e j uno dei particolari 2i nodi che si possono avere alla profondità i. Tij è il sottoalbero che ha come radice nij. Il tempo in cui avviene la lettura è diviso in frame, per ciascuno dei quali sono previsti tre slot temporali; nel primo slot di un frame il reader invia la propria richiesta, alla quale alcuni tag, nei due successivi slot, sono chiamati a rispondere. La richiesta del reader è l’equivalente codice binario di una radice nij, dalla quale, come evidente dalla Figura 2.3, partono due sottoalberi. Nel primo dei due slot adibiti alle risposte dei tag, inviano il proprio codice quelli che appartengono al sottoalbero superiore, nel secondo i tag che si trovano in quello inferiore. Una descrizione

formale del metodo secondo il quale procede la lettura consiste nell’iterazione di due operazioni, con la condizione iniziale che la ricerca parta dal nodo n₀₀ (con riferimento all’esempio si pone Tx = T10 e Ty = T11 ): i tag interrogati nel frame attuale rispondono nel

seguente modo: quelli appartenenti al sottoalbero Tx trasmettono nella prima slot del frame,

mentre quelli appartenenti a Ty nella seconda; il reader è in grado di rilevare se all’interno

di ciascuno slot vi è stata collisione o lettura corretta. Nel caso di collisione in uno o in entrambi gli slot, prima di proseguire con le altre eventuali diramazioni dell’albero che presentano conflitti da risolvere, viene risolto totalmente il sottoalbero in cui vi è stata collisione. La risoluzione della collisione nel primo slot ha la precedenza. Si pone perciò Tx

uguale alla parte superiore del sottoalbero coinvolto nella collisione, Ty a quella inferiore.

Con riferimento agli esempi delle Figure 2.3 e 2.4, la spiegazione della dinamica dell’algoritmo diviene, seguendo i due passi sopra enunciati, abbastanza semplice. Poiché nel primo frame il reader invia la richiesta ‘00’, si ha la trasmissione dei pacchetti che

appartengono a T10 (S0,S2 e S4) nel primo slot e di quelli che appartengono a T11 (S8 e S10)

nel secondo.

READER request

TAG

transmitting S₀

1st _{slot 2}nd _{slot 3}rd_slot

1st _frame S₄ S₈ S₁₀ S₂ 00 10 20 11 22 S₁₀ S₂ S₀ S₄ S₀ S₂ S₈ S₈ S₁₀ Time 5th_frame

1st _{slot 2}nd _{slot 3}rd_slot

Figura 2.4 Rappresentazione degli eventi al passare del tempo per la lettura dei transponder presenti. La richiesta del reader rappresenta il codice binario di una radice, della quale si vogliono esaminare i due

In entrambi gli slot vengono osservate collisioni e il reader, in accordo con l’algoritmo descritto, decide di risolvere per prima la collisione del primo slot. Nel secondo frame la richiesta sarà ‘10’ con conseguente indagine dei sottoalberi T20 e T21: dal primo si hanno

più risposte mentre dal secondo si riceve una singola comunicazione e il codice del transponder relativo viene acquisito dal reader. Continuando con l’analisi della collisione nel sottoalbero T20, da quest’ultimo si ottengono due codici di tag (S0 S2) che trasmettono

in slot separate. Una volta finita così di analizzare tutta la parte superiore dell’albero si passa a quella inferiore, a partire dalla richiesta ‘11’, a cui segue una collisione nel primo slot e nessuna trasmissione nel secondo. Nel successivo e ultimo frame si hanno due successi e la lettura può dirsi completata con la certezza che tutti i codici presenti sono stati acquisiti.

Ora che il funzionamento del protocollo è stato spiegato in dettaglio, occorre valutarne le prestazioni. Con un programma in C++ si simula la creazione dell’albero, al passare del tempo, in dipendenza degli M codici dei transponder che partecipano al processo di lettura. Mentre nei programmi utilizzati per i protocolli Aloha lo svolgimento temporale del processo dipendeva, ad ogni incremento della variabile temporale, da numeri estratti in modo casuale, ora, nella costruzione dell’albero, non interviene alcun tipo di casualità poiché essa dipende esclusivamente dai codici dei transponder presenti. La simulazione è ancora di tipo Monte Carlo in quanto all’inizio di ogni completa lettura ad albero si creano in modo casuale tanti codici, diversi tra loro, quanti sono i tag. Nella realtà il codice è composto da una stringa binaria, tipicamente della dimensione di otto byte, ma nella simulazione, per semplicità di utilizzo, viene usato il corrispondente numero intero. Nelle applicazioni RFID un codice ha tipicamente una lunghezza di otto byte, ma nel programma si fa riferimento ad un codice composto da tre byte: questa operazione introduce un’approssimazione che con tutta probabilità non si manifesta nei risultati della simulazione, rispetto a ciò che si ha in realtà con un codice a 8 byte. Infatti è del tutto

improbabile che, con un numero di tag coinvolti nel processo, che può essere al massimo qualche centinaio, si possa verificare il caso che due codici abbiano i primi tre byte totalmente identici, unico caso per il quale la simulazione non rappresenterebbe correttamente la realtà. Il programma, ad ogni incremento di una variabile temporale, compie tutte le operazioni che avvengono nei tre slot di un frame: uno slot per la richiesta del reader e i due successivi per le trasmissioni dei transponder (Figura 2.4). L’idea che permette di riprodurre in questo modo il funzionamento del protocollo è costruire una pila, nella quale ad ogni livello sono scritti tre valori interi: gli estremi superiore e inferiore tra cui è compreso un sottoalbero e il numero di transponder che hanno un codice compreso tra questi due valori, ed appartengono perciò al sottoalbero in questione. All’inizio di una nuova iterazione del programma viene preso in analisi il livello più basso della pila; l’intervallo tra i due estremi che esso contiene viene suddiviso in due parti e i due nuovi intervalli che si vengono a creare, che rappresentano i due alberi, a profondità immediatamente superiore, del nodo dove si era verificata la collisione, vengono indagati separatamente. Il contenuto di tutti gli altri livelli della pila, non indagati nel passo attuale, viene copiato nel rispettivo livello superiore per liberare gli ultimi due livelli; nel livello più basso, cioè con indice identificativo zero, vengono inserite le informazioni, estremi e numero di tag, che si hanno dal primo intervallo costruito all’inizio dell’iterazione in corso. Al livello uno sono inserite le informazioni che si hanno dal secondo intervallo. Ognuno di questi due nuovi livelli è poi mantenuto solo se contiene più di un tag. Il risultato fondamentale, che esce da ogni singola corsa del programma con i codici generati in modo casuale, è il numero di iterazioni necessarie per completare l’albero. Poiché ogni iterazione del programma riproduce gli eventi di un frame ed ogni frame è composto da tre slot, il numero totale di slot con cui si porta a termine l’algoritmo è ottenibile dalla semplice moltiplicazione di questo dato per tre. E’ perciò chiaro il motivo per il quale, in tutti i prossimi grafici, il tempo, misurato in slot, sarà un multiplo del valore 3. Per tracciare un

quadro abbastanza completo delle prestazioni del protocollo di Capetanakis sono state ricavate densità di probabilità e funzione di distribuzione per una lettura rispettivamente di 30 e di 100 tag (Figure da 2.5 a 2.8). Rispetto a queste due statistiche, in confronto alla maggioranza dei protocolli Aloha e, come si avrà modo di osservare in seguito, a tutti gli altri protocolli deterministici, l’albero di Capetanakis ha prestazioni peggiori. In entrambi i casi trattati la densità di probabilità presenta un picco spostato a sinistra e una coda molto lunga. Si può eseguire una valutazione concreta di tali entità mediante le funzioni di distribuzione, in merito alle quali si osserva che è necessario almeno il 25% del tempo impiegato in vista del raggiungimento del 99,9% per passare da una probabilità del 99% ad una del 99,9% e il 60% del tempo per passare dal 50% al 99,9%. Tempo medio per la lettura completa e tempo 99%, rappresentati in Figura 2.9, hanno un andamento abbastanza lineare; in particolare il tempo medio presenta un fattore di proporzionalità di 4,5 tra il numero di slot necessari e il numero di tag presenti, mentre il tempo 99% di 6,6.

50

100

150

200

250

300

0

200

400

600

800

1000

1200

Occurrenci

e

s

Time (slot)

Figura 2.5 Densità di probabilità, normalizzata su 5000 simulazioni, del tempo necessario per effettuare una lettura completa di 30 transponder. L’unità di misura del tempo è un singolo slot.

80

120

160

200

240

280

320

5.0 20.0 40.0 50.0 60.0 80.0 95.0 99.0 99.9

D

is

tribution function (%)

Time (slot)

Figura 2.6 Funzione di distribuzione del tempo necessario per effettuare la lettura completa di 30 transponder. I dati per la sua costruzione sono tratti dalla densità di probabilità della figura precedente.

200 300 400 500 600 700 800 900

0

200

400

600

800

1000

Occurrencies

Time (slot)

Figura 2.7 Densità di probabilità, normalizzata su 5000 simulazioni, del tempo necessario per effettuare una lettura completa di 100 transponder. L’unità di misura del tempo è un singolo slot.

300

400

500

600

700

800

900

5.0 20.0 40.0 50.0 60.0 80.0 95.0 99.0 99.9

Distribution function (%)

Time (slot)

Figura 2.8 Funzione di distribuzione del tempo necessario per effettuare la lettura completa di 100 transponder. I dati per la sua costruzione sono tratti dalla densità di probabilità della figura precedente.

0

50

100

150

200

250

300

0

400

800

1200

1600

2000

0.0

25.6

51.2

76.8

102.4

128.0

T

im

e

(

b

it,1

0

3

)

T

im

e

(

slo

t)

Tag number

average time

t

₉₉

Figura 2.9 Tempo medio, deviazione standard e tempo per la lettura con una probabilità del 99%. E’ riportato il comportamento per un numero di transponder da 10 a 300 e il numero di simulazioni effettuato

2.2.2 - Memoryless

Un esempio di protocollo pensato in modo specifico per applicazioni di tipo RFID è il protocollo ‘Memoryless’ la cui denominazione, tradotta in italiano, enuncia con chiarezza la caratteristica fondamentale della logica del transponder utilizzata per eseguire l’algoritmo di anticollisione: essa non deve infatti preoccuparsi di mantenere alcuna memoria degli eventi che si verificano durante il processo di lettura. L’articolo dal titolo ‘Efficient Memoryless Protocol for Tag Identification’2[6], oltre a fornire un’esaustiva presentazione del funzionamento e dei risultati di tale protocollo, pone l’accento sull’importanza, nell’RFID, di progettare una comunicazione secondo la quale il tag abbia come unico compito quello di rispondere a successive interrogazioni effettuate dal reader. Da questa considerazione nasce il tentativo di far ricadere sul reader di tutta la complessità dell’algoritmo di risoluzione, mentre al transponder sono richiesti soltanto confronti bit a bit tra un codice inviato dal reader ed il suo stesso codice identificativo. L’obiettivo che ha dato origine alla realizzazione del protocollo Memoryless è l’ottenimento della maggiore velocità possibile nella risoluzione dell’algoritmo vincolata ad una logica su tag relativamente semplice possibile. Nel prossimo paragrafo sarà illustrata la versione base del Memoryless, in seguito saranno presentati alcuni accorgimenti per ottenere una maggiore efficienza, sia per quanto riguarda il comportamento del reader che dei tag.

[6] Ching Law, Kayi Lee, Kai-Yeung Siu. “Efficient Memoryless Protocol for Tag Identification”, MIT Auto-ID Center, 2002.

2.2.2.1 – Memoryless: Basic

Il protocollo Memoryless basic e tutte le varianti che saranno analizzate in seguito utilizzano i medesimi presupposti: la lettura avviene in modalità Blocked access e sono presenti M transponder ciascuno dei quali è identificato da un codice lungo 8 byte. In ogni passo del processo di lettura il reader invia una stringa di bit di dimensione variabile a seconda del momento dello svolgimento dell’algoritmo ed ogni tag confronta, partendo dal bit più significativo, tale stringa con il proprio codice. Se il confronto ha come risultato l’uguaglianza dei due codici, il transponder invia interamente il proprio codice. Il processo di una nuova lettura di tutti i tag inizia con l’invio, da parte del reader, di un segnale che induce tutti i tag a rispondere inviando a loro volta il proprio codice; essendo in genere più tag chiamati a svolgere tale operazione, è possibile che si abbia una collisione dei codici mandati simultaneamente in risposta. Nella versione Basic dell’algoritmo Memoryless, trattata nel presente, la lettura prosegue con l’invio di una stringa q contenente un solo bit con valore ‘0’ e, successivamente, di un’altra con valore ‘1’. A ciascuna delle due richieste rispondono solo i transponder il cui codice, rispettivamente, ha ‘0’ o ‘1’ come bit più significativo. Dal tipo di risposta che il reader ottiene dalla richiesta che ha inviato ai tag, si prefigurano tre vie per la continuazione dell’algoritmo. Se non è stata ricevuta alcuna risposta o ne è stata ricevuta una, l’indagine dei codici nella direzione intrapresa ha termine; chiaramente, se si è verificata una singola risposta, il codice acquisito viene inserito in memoria. Nel caso in cui si ricevano molteplici risposte e, di conseguenza, si verifichi una collisione, il passo successivo sarà quello di aggiungere prima il bit ‘0’ alla stringa q che aveva ricevuto una risposta con collisioni e, successivamente, il bit ‘1’. Vengono perciò inviate una dopo l’altra le richieste q0 e q1, dove ad esempio con l’espressioneq0 si vuole indicare l’aggiunta in coda a q il bit ‘0’. Tale modo di procedere con l’indagine rende deterministico il processo e ha fine solo quando non vi sono più collisioni da risolvere. Con riferimento all’esempio di Figura 2.10, si può spiegare passo

per passo come si susseguono, in modo cronologico, le richieste del reader in dipendenza delle risposte ottenute dai tag. In presenza di quattro codici su 4 bit il processo inizia, in modo simbolico, con l’invio di una stringa vuota che nella realtà è costituita da un segnale che indica ai tag l’inizio del processo di lettura. A tale richiesta rispondono tutti i codici e, così come per le due successive richieste con i soli bit ‘0’ e ‘1’, fa seguito la collisione di più codici. Richiesta Risposta ε collisione 0 collisione 1 collisione 00 nessuna risposta 01 collisione 10 1010 11 1110 010 0101 011 0110

Codici dei tag presenti: {0101,0110,1010,1110}

Figura 2.10 Esempio di svolgimento temporale di una lettura con il protocollo Memoryless basic. Al processo partecipano quattro transponder con codici composti da quattro bit. La richiesta del reader ε (stringa

vuota) rappresenta un segnale in conseguenza del quale tutti i transponder sono chiamati a trasmettere il proprio codice.

Proseguendo nella direzione indicata dal bit ‘0’ non si osserva alcuna risposta per la richiesta ‘00’ e collisione per ‘01’, mentre nella direzione indicata da ‘1’ si ottengono 2 codici letti con successo: da ‘10’ si ottiene il codice ‘1010’ e da ‘11’ il codice ‘1110’. Resta da risolvere la collisione che si è verificata in corrispondenza di ‘01’’; dall’invio di ‘010’, prima, e di ‘011’, poi, è possibile ricavare gli ultimi due tag non ancora letti. A questo punto, con nessun’altra collisione da risolvere, il reader si accorge che la lettura è stata portata a termine. Viene definita iterazione del processo l’insieme di una richiesta e della conseguente risposta, dall’analisi teorica condotta in [6] si ha un importante risultato: il

numero di iterazioni medie necessarie per leggere tutti i tag che prendono parte a tale processo di lettura:

E[I] = 2.88M-1 (2.1) Il metodo seguito per ottenere tutti gli altri parametri che determinano le prestazioni del protocollo consiste in una simulazione Monte Carlo del sistema, con un programma scritto in linguaggio C++. Dal momento che il processo di lettura con il Memoryless è del tutto simile alla creazione di un albero, il fatto che il programma utilizzato adotti le stesse idee impiegate nel programma già descritto nel paragrafo precedente a proposito dell’albero di Capetankis non richiede alcuna spiegazione. Una sola è la differenza nella creazione dei due alberi: nell’albero realizzato nel Memoryless si procede in modo da analizzare in parallelo tutte le collisioni ad un stessa profondità; al contrario, nella creazione dell’albero di Capetanakis si procedeva sempre più in profondità fino a che un tag non veniva isolato, per poi risalire e seguire le altre strade abbandonate allo scopo di individuare il singolo tag. Adattare a questa modifica il programma già usato in precedenza è molto semplice in quanto è sufficiente cambiare il modo in cui si aggiorna la pila introdotta nel programma che simulava l’albero nel paragrafo precedente. A dimostrazione del corretto funzionamento del programma si può verificare se i risultati uscenti dalla simulazione siano in accordo con la formula (2.1) che, come detto, esprime il numero medio di iterazioni necessarie per portare a termine la lettura di un certo numero M di transponder. Come si vede in Figura 2.11, la verifica sembra confermare la bontà del programma che sarà impiegato sia per l’analisi del Memoryless basic sia, con piccoli accorgimenti, per le sue evoluzioni.

0

20

40

60

80

100

0

50

100

150

200

250

300

Iteration number

Tag number

simulato

teorico

Figura 2.11 Verifica della correttezza del programma impiegato per la simulazione mediante il confronto con la formula teorica 1. Il grafico rappresenta il numero di iterazioni medie per leggere un dato numero di

transponder.

Una volta verificata la correttezza del programma, prima di presentarne i risultati più significativi occorre illustrare come tale algoritmo possa funzionare in un sistema RFID, cioè definire i tempi di sincronizzazione tra le comunicazioni reciproche di transponder e reader. In primo luogo è necessario ricordare il funzionamento reale della ricerca ad albero di Capetanakis: la comunicazione viene divisa in slot temporali della lunghezza di un codice ed ogni successiva esplorazione dell’albero risulta contenuta in un frame di tre slot, uno dedicato al reader e due ai tag. In tutti i protocolli Memoryless vi è un susseguirsi continuo di comunicazioni del reader e dei tag; nel caso Basic in esame il reader comunica un numero di bit variabile a seconda del momento del processo, mentre i tag trasmettono sempre il proprio codice in forma estesa e dunque nello spazio di uno slot. Anticipando un aspetto dell’evoluzione del caso Basic che verrà considerato in maniera più approfondita nel prossimo paragrafo, è possibile intuire che i tag comunicheranno solo una parte del

proprio codice, quella complementare alla prima parte inviata dal reader. Per rappresentare un caso reale di protocollo Memoryless si è scelto di interporre un certo numero di bit tra una comunicazione dal reader ai transponder e viceversa. Tali bit, per il numero dei quali una scelta ragionevole appare 8, servono per sincronizzare le trasmissioni e per consentire al reader ed ai transponder di preparare, rispettivamente, la richiesta o la risposta. Sia per tale fatto che per l’interesse di confrontare un simile protocollo con i suoi successivi miglioramenti e con gli altri protocolli esaminati in questo capitolo, il tempo non può essere rappresentato in numero di iterazioni, ma l’unità di misura deve essere o uno slot contenente l’intero codice oppure il tempo di comunicazione di un bit, di uguale durata nel caso che a comunicare sia il tag o il reader.

Nelle Figure 2.12 e 2.13 sono riportate la densità di probabilità e la relativa funzione di distribuzione per la lettura di 50 transponder. Le due statistiche appaiono molto regolari; la densità di probabilità ha una piccola coda, dato confermato dalla funzione di distribuzione e sul quale si può leggere che solo il 7% del tempo totale per arrivare ad un margine di sicurezza del 99,9% è impiegato nell’ultimo tratto che parte dal 99%. Tali dati sono paragonabili a quelli dei migliori protocolli Aloha, a differenza delle statistiche ben peggiori ottenute nel primo protocollo, l’albero di Capetanakis, analizzato nel paragrafo precedente. Il tempo medio ed il tempo per la lettura con una probabilità del 99% (Figura 2.14) sono lineari, quest’ultimo è all’incirca un 13% in più del tempo medio. Il tempo medio scala con un fattore di proporzionalità di 3,66 con il numero di tag di cui si deve effettuare la lettura.

125

150

175

200

225

250

275

0

200

400

600

800

1000

Occurrencies

Time (slot)

Figura 2.12 Densità di probabilità, normalizzata su 5000 simulazioni, del tempo necessario per effettuare una lettura completa di 50 transponder con il protocollo Memoryless basic. L’unità di misura del tempo è un

singolo slot.

150

175

200

225

250

5.0 20.0 40.0 50.0 60.0 80.0 95.0 99.0 99.9

Distribution function (%)

Time (slot)

Figura 2.13 Funzione di distribuzione del tempo necessario per effettuare la lettura completa di 50 transponder. I dati per la sua costruzione sono tratti dalla densità di probabilità della figura precedente.

10 20 30 40 50 60 70 80 90 100

0

50

100

150

200

250

300

350

400

450

Ti

me (sl

o

t)

Tag number

average time t₉₉

Figura 2.14 Tempo medio, deviazione standard e tempo per la lettura con una probabilità del 99%. Il numero di simulazioni effettuato per acquisire ciascun dato è 200.

2.2.2.2 – Memoryless: Optimal

Un accorgimento che si può apportare al protocollo Memoryless fino ad ora descritto consiste in una piccola modifica al comportamento del transponder: quando riceve una richiesta alla quale deve rispondere, quest’ultimo risponde inviando solo la parte di codice complementare a quella contenuta nella richiesta. Come si può osservare dal confronto tra l’esempio basato su tale tipo di lettura (Figura 2.15) e quello già visto per il caso Basic rappresentato in Figura 2.10, il reader invia le medesime richieste, ma il tempo di lettura misurato in bit inviati subisce una riduzione pari al numero dei bit complessivamente inviati dal reader. Se il protocollo descritto nella parte iniziale del paragrafo assume il nome di Memoryless basic, con l’accorgimento relativo alla parte mancante di codice a tale denominazione viene aggiunto il qualificativo Optimal.

Richiesta Risposta ε collisione 0 collisione 1 collisione 00 nessuna risposta 01 collisione 10 10 11 10 010 1 011 0

Codici dei tag presenti:

{0101,0110,1010,1110}

Figura 2.15 Esempio di svolgimento temporale di una lettura con il protocollo Optimal Memoryless. Al processo partecipano quattro transponder con codici composti da quattro bit. Ad ogni richiesta il tag è

chiamato a rispondere inviando la parte mancante del codice.

Il programma per la simulazione ricalca quello già impiegato e considera l’accorgimento introdotto, cioè non inserisce nel conto per i bit inviati il numero di quelli inviati nelle richieste del reader. Le due statistiche sulla densità e sulla funzione di distribuzione illustrate nelle Figure 2.16 e 2.17 mostrano una forma piuttosto simile a quelle del protocollo Basic, anche se il tempo per passare dal 99% al 99,9% è più ridotto, corrispondente al 5% del totale invece che al 7%. Il tempo medio e il tempo 99% (Figura 2.18) sono ancora lineari, con il tempo medio che scala con un fattore di proporzionalità di 3,6 rispetto al numero di tag da leggere in accordo con l’espressione (2.1) la quale riporta il numero di iterazioni medie necessarie per portare al termine la lettura; tale numero equivale proprio al numero di slot necessarie per una lettura con l’Optimal Memoryless. La struttura a scalini assunta dalla funzione di distribuzione è da ritenersi derivante dal metodo impiegato dal reader nell’eseguire le richieste e dal fatto che ogni richiesta e successiva risposta dei tag formano precisamente uno slot.

125

150

175

200

225

250

0

100

200

300

400

500

600

700

Occurrenci

e

s

Time (slot)

Figura 2.16 Densità di probabilità, normalizzata su 5000 simulazioni, del tempo necessario per effettuare una lettura completa di 50 transponder con il protocollo Optimal Memoryless. L’unità di misura del tempo è

un singolo slot.

150

175

200

225

250

5.0 20.0 40.0 50.0 60.0 80.0 95.0 99.0 99.9

Distribution function (%)

Time (slot)

Figura 2.17 Funzione di distribuzione del tempo necessario per effettuare la lettura completa di 50 tag. I dati per la sua costruzione sono tratti dalla densità di probabilità della figura precedente.

0 100 200 300 400 500 0 250 500 750 1000 1250 1500 1750 2000

Time (slot)

Tag number

average time t₉₉

Figura 2.18 Tempo medio, deviazione standard e tempo 99% per la lettura con il protocollo Optimal Memoryless. Il numero di simulazioni effettuato per acquisire ciascun dato è 200.

2.2.2.3 – Memoryless: Aggressive advancement

Al protocollo Memoryless Basic possono essere apportati dei miglioramenti nel modo in cui il reader formula le proprie richieste senza che venga modificata la funzionalità originale del tag, funzionalità corrispondente d’ora in poi alla versione Optimal in quanto tale da prevedere la risposta con la parte mancante. Il primo miglioramento descritto nell’articolo prende il nome di ‘Aggressive advancement’ : se alla richiesta effettuata con una stringa q è stata rilevata più di una risposta, sono saltate del tutto le richieste che aggiungono prima il bit ‘0’ e poi quello ‘1’ e sono inviate in sequenza le richieste che si trovano a profondità immediatamente superiore, cioè a q00, q01, q10 e q11. Saltare del tutto la richiesta intermedia può, a seconda dei casi, portare un beneficio o peggiorare il tempo di lettura. Nel caso in cui i transponder entrati in collisione alla richiesta q siano solo due, l’Aggressive advancement introduce un peggioramento se essi hanno bit successivi a q

differenti o impiega lo stesso numero di richieste, in numero di quattro, se i due tag proseguono con bit identici.

Richiesta Risposta ε collisione 00 nessuna risposta 01 collisione 10 10 11 10 0100 nessuna risposta 0101 (0101) 0110 (0110) 0111 nessuna risposta

Codici dei tag presenti:

{0101,0110,1010,1110}

Figura 2.19 Esempio di svolgimento temporale di una lettura con il protocollo Memoryless aggressive advancement. Al processo partecipano quattro transponder con codici composti da quattro bit; dal momento che si utilizza l’opzione di risposta con la parte mancante di codice, l’eventuale risposta alla richiesta di tutti i

quattro bit è messa tra parentesi (nella realtà il transponder risponderebbe con un segnale che ne indica la presenza).

Quando i tag entrati in collisione alla richiesta q sono invece in numero di tre i due modi di procedere illustrati impiegano lo stesso numero di iterazioni. Se i transponder entrati in collisione per q sono infine almeno quattro, il nuovo metodo proposto può introdurre un miglioramento al numero di iterazioni da fare o al limite necessitare dello stesso numero di iterazioni del protocollo base. Quest’ultimo caso si verifica se in una delle due richieste del protocollo base, che aggiungono un solo bit a q, non si ha nessuna o una sola risposta: con il Memoryless Basic si effettuano le richieste q0 e q1 e, successivamente, altre due come continuazione di una sola tra queste ultime, dato che l’altra non ha dimostrato collisione da risolvere; con l’Aggressive advancement viene effettuato lo stesso numero di richieste, come sempre pari a quattro. Il nuovo metodo permette di risparmiare due iterazioni se per entrambe le richieste q0 e q1 che si farebbero con il protocollo base si hanno collisioni. La probabilità che ciò avvenga è ricavabile in modo piuttosto semplice. Sia s il numero, di

valore almeno quattro, dei tag che sono in collisione per la richiesta q; la probabilità p che il bit successivo a q sia ‘0’ è la stessa di quella che sia ‘1’ e vale ½ . La probabilità che k degli s tag rispondano a q0 è la medesima di quella che essi rispondano a q1 ed ha il valore di:

k S-k

s s

P(k risposte a qo) = P(k risposte a q1) = p (1- p) = (1/ 2)

k k             S

}

}

S S (2.2) Si definiscono Z e U gli eventi:

{

} {

{

} {

Z = nessuna risposta per la richiesta q 0 = nessuna risposta per la richiesta q1 U = una risposta per la richiesta q 0 = nessuna risposta per la richiesta q1

La probabilità che essi si distribuiscano nei due slot successivi, in modo da rispondere ad una delle due richieste successive con nessun tag o uno, sono ricavabili con k pari a zero e ad uno nella (2.2): S s P(Z) = P(0) = (1/ 2) = (1/ 2) 0       (2.3) S s P(U) = P(1) = (1/ 2) = S(1/ 2) 1       (2.4) La probabilità che alle due richieste successive a q vi sia uno slot senza collisioni è:

P(uno slot senza collisioni) = 2 (P(Z) + P(U)) (2.5) Infine si ottiene ciò che interessa, cioè la probabilità che entrambe le richieste abbiano in risposta siano collisioni, il caso in cui utilizzando l’Aggressive advancement si ha un vantaggio:

S S

S-1

P(entrambi gli slot con collisioni) = 1- 2 (P(Z) + P(U)) = S+1

= 2((1/ 2) + S(1/ 2) ) = 1-2

(2.6)

Per valutare, sebbene poco dettagliatamente, le prestazioni dell’Aggressive advancement nel quale il tag risponda con la parte mancante di codice si ricorre ad una simulazione

mediante un programma che introduce piccole modifiche a quello impiegato per il Basic. Il tempo medio, lineare, scala con un fattore 3,53.

0

50

100

150

200

250

0

200

400

600

800

1000

0

12800

25600

38400

51200

64000

Ti

m

e (

bi

t)

Ti

m

e (

sl

ot

)

Tag number

average time

t

₉₉

Figura 2.20 Tempo medio, deviazione standard e tempo per la lettura con una probabilità del 99% del protocollo Memoryless aggressive advancement. Il numero di simulazioni effettuato per acquisire ciascun

dato è 200.

2.2.2.4 – Memoryless: Shortcutting

Lo Shortcutting rappresenta un altro possibile miglioramento non molto distante dall’idea posta alla base dell’Aggressive advancement: si tratta di saltare alcune richieste quando appare evidente che esse avranno una collisione come risposta. Entrando più nel dettaglio si è visto che nel funzionamento base, quando ad una stringa inviata dal reader fa seguito una risposta con collisione, a quest’ultima faranno seguito due successive richieste, una che aggiunge alla stringa un bit di valore ‘0’ e un’altra che aggiunge il valore ‘1’. Il metodo Shortcutting traduce in concreto la semplice osservazione che, se alla richiesta che ha aggiunto il valore ‘0’, non è stata ricevuta alcuna risposta è certo che se ne avranno almeno due in quella che aggiunge ‘1’ e si può pertanto saltare tale richiesta formulando

direttamente quelle successive. In pratica si formulano due richieste successive che aggiungono ciascuna due bit: ‘10’ e ‘11’. Questo accorgimento evita di dover inviare la richiesta con il semplice ‘1’ ed attenderne una risposta di sicura collisione.

Richiesta Risposta ε collisione 0 collisione 1 collisione 00 nessuna risposta 10 10 11 10 010 1 011 0

Codici dei tag presenti:

{0101,0110,1010,1110}

Figura 2.21 Esempio di svolgimento temporale di una lettura con il protocollo Memoryless shortcutting nel quale i tag rispondono con la parte mancante di codice. Al processo partecipano quattro tag con codici

composti da quattro bit.

Così come per il protocollo di base, [6] fornisce il numero medio di iterazioni necessarie a risolvere M transponder:

(2.7) E[I] = 2.665M-1

Nell’osservare che con l’accorgimento della parte mancante di codice ad ogni iterazione corrisponde l’invio di 64 bit divisi tra reader e tag, è evidente come tale rappresenti il tempo medio per portare a termine la lettura con l’algoritmo Optimal shortcutting nel caso in cui non si considerino gli 8 bit di separazione tra le comunicazioni di tag e reader. Nel caso reale, ad ogni iterazione composta da 64 bit occorre pertanto aggiungere due segmenti di 8 bit, per un totale di 16 bit ogni 64. Il numero medio di slot necessario a completare la lettura con l’algoritmo Optimal shortcutting sarà quindi un valore superiore del 25% di quello considerato per E[I] nell’espressione (2.2):

Tslot = 3,33M (2.8)

2.2.2.5 – Memoryless: confronti

E’ importante osservare che la differenza tra il protocollo Basic e le due evoluzioni Aggressive advancement e Shortcuting consiste soltanto in una modifica del comportamento del reader, mentre il transponder rimane il medesimo sia che la lettura venga più o meno effettuata con una modalità Optimal. Il fatto che un transponder risponda con un numero di bit complementare rispetto a quello inviato dal reader conduce alla semplice osservazione che il numero di bit complessivamente inviati in un processo di lettura è uguale al numero di iterazioni compiute moltiplicato per il numero di bit che compongono un intero codice. E’ lecito perciò fare un confronto, basato sul numero totale di iterazioni da compiere, tra i tre modi in cui il reader può decidere di effettuare le successive richieste. Il confronto sui tempi medi nei casi Optimal è riportato in Figura 2.22; il protocollo Aggressive advancement risulta non molto migliore del protocollo Basic ed è interessante osservare che rispetto a questo primo miglioramento il protocollo Shortcutting ha un tempo medio di lettura più veloce del 2,5%.

0

50

100

150

200

0

125

250

375

500

625

750

Average time (slot)

Tag number

Basic

Aggressive advancement Shortcutting

Figura 2.22 Confronto tra le tre evoluzioni del protocollo Memoryless, Basic, Aggressive advancement e Shortcutting, ottenute con il medesimo transponder e una differente sequenza nelle richieste del reader. Le

risposte dei transponder sono date con la parte mancante di codice.

2.2.3 – Binary search

L’algoritmo di risoluzione delle collisioni che prende il nome di Binary search è tratto dalla sezione riguardante i protocolli di anticollisione dell’RFID Handbook3[7]. Questo algoritmo necessita, per un corretto funzionamento, di due elementi chiave: una sincronizzazione sui bit di codice risposti contemporaneamente da più transponder interrogati dal reader e di 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. Lo svolgimento dell’algoritmo è piuttosto semplice: ad ogni passo, con un

criterio che in seguito sarà illustrato nel dettaglio, il reader invia un codice al quale rispondono solo i tag che possiedono un codice di valore inferiore o, al limite, uguale. Nel passo iniziale la richiesta è il codice con il valore più grande ottenibile con 64 bit, al confronto con il quale tutti i tag presenti verificano con successo la condizione e trasmettono. Il reader, mediante la perfetta sincronizzazione dei bit ottenuti in risposta, rileva in quali posizioni del codice a 64 bit si sono verificate collisioni. A partire dal primo bit più significativo su cui se ne è riscontrata una, esso invia come nuova richiesta un codice che restringe il campo dei tag che possono rispondere. Si procede così fino a che non rimane un solo tag a rispondere, il quale viene disabilitato dopo averne inserito il codice in memoria. Il reader mantiene in memoria la successione delle richieste effettuate consecutivamente, perciò il percorso di ricerca

riprende dall’ultima richiesta precedente alla scoperta del singolo codice. La ricerca finisce quando il reader, tornato alla richiesta con il codice massimo, inviato nel passo iniziale, scopre il codice di un ultimo tag attivo. Il criterio con il quale si effettuano di volta in volta le richieste risulta chiaro facendo riferimento all’esempio riportato in Figura 2.23. Con la richiesta iniziale, il codice massimo, il reader ha osservato che le risposte dei transponder presentano collisioni sul secondo, il quarto e l’ultimo bit. Il campo della ricerca viene ristretto inviando il codice che permette di isolare i tag che appartengono all’intervallo inferiore rispetto al valore del secondo bit: il tag che in quella posizione ha un bit di valore 1 non parteciperà per il momento alla ricerca e tornerà in gioco solo dopo che tutti i tag con un secondo bit di valore 0 saranno stati acquisiti. Al terzo passo avviene la corretta lettura di un primo tag, dopodichè il reader, come è stato detto nella descrizione dell’algoritmo, invia la richiesta del secondo passo, la quale aveva riportato collisioni. Nell’ultimo passo il reader torna ad inviare il codice iniziale al quale risponde l’ultimo tag attivo; di qui la conclusione che non rimane più alcun tag da leggere.

Richiesta del reader 11111111 Tag in risposta 10110010 10100011 10110011 11100011 Risultato 1X1X001X

Richiesta del reader 10111111 Tag in risposta

10110010 10100011 10110011 Risultato 101X001X

Richiesta del reader 10101111 Tag in risposta 10100011 Risultato 10100011

Richiesta del reader 10111111 Tag in risposta 10110010_10110011 Risultato 1011001X

Richiesta del reader 10110010 Tag in risposta 10110010 Risultato 10110010 1°passo: Codici presenti: 10110010 10100011 10110011 11100011 2°passo: 3°passo: 4°passo: 5°passo:

Richiesta del reader 11111111 Tag in risposta 11100011 Risultato 11100011

7°passo:

Richiesta del reader 10111111 Tag in risposta 10110011 Risultato 10110011

6°passo:

Figura 2.23 Esempio dello svolgimento della ricerca binaria per la soluzione dei 4 codici presenti, ciascuno da 8 bit. La freccia uscente significa che il transponder con questo codice è acquisito e poi disattivato. Ad

ogni passo dell’algoritmo, un transponder ancora attivo risponde se il suo codice ha un valore minore o uguale alla richiesta del reader.

La simulazione del sistema utilizza lo stesso schema logico impiegato per gli altri protocolli deterministici visti fino ad ora. All’inizio del programma vengono generati M codici interi in modo del tutto casuale, essi indicheranno la direzione che l’algoritmo deve prendere successivamente ad ogni incremento della variabile temporale. Ancora una volta nel corpo del programma si impiega una pila che contiene ad ogni livello il valore di un codice. Inizialmente solo il primo livello contiene un valore che corrisponde al valore

intero massimo ottenibile con il numero di bit di codice utilizzati. Il valore che si trova al primo livello è quello per il quale viene fatta la richiesta ai tag, i quali, come si è visto, rispondono solo se hanno un codice inferiore. E’ una certezza che tutti i tag rispondano alla richiesta iniziale, il reader, mediante un semplice calcolo, individua il bit più significativo che presenta collisione e mette il corrispondente codice intero, dopo aver spostato ciascuno degli altri nel proprio livello superiore, al primo livello della pila. L’algoritmo procede in questo modo fino a che non si osserva una singola risposta dal tag; a questo punto il codice rilevato viene eliminato e tutti i valori della pila vengono scalati nella posizione loro inferiore. Tutta la casualità della lettura risiede nei valori dei codici presenti, dopodichè l’algoritmo procede in un modo del tutto deterministico dettato dalle istruzioni contenute nell’algoritmo di risoluzione. Al contrario di tutti i protocolli affrontati finora, la ricerca binaria presenta un tempo unico per la lettura di un dato numero di transponder. Il numero di iterazioni I che si compiono, qualsiasi siano i codici presenti, vale infatti:

I(M) = 2 M-1 (2.9) Ogni iterazione del processo si compone di due slot, uno in cui è contenuto la richiesta del reader e uno con una o più risposte dei tag; tra le comunicazioni del reader e dei transponder occorre inoltre sempre interporre 8 bit. Le motivazioni sono le medesime di quelle già viste per il protocollo Memoryless. In definitiva, per ogni iterazione sono necessari due slot della lunghezza di un codice (64 bit) e due intervalli di attesa di 8 bit, per un totale di 144 bit. Il numero di bit per completare il processo si ottiene moltiplicando tale valore per il numero di iterazioni scritto nella formula (2.9):

Tbit = 144 (2M-1) = 288M -144 (2.10) Si è interessati a valutare la velocità dell’algoritmo di anticollisione per un numero consistente di tag, perciò si possono trascurare i 144 bit che compaiono nella (2.10). Riportando il tempo scritto in bit in numero di slot si ha :

2.2.4 - Optimal Binary search

La modifica che rende più veloce la ricerca binaria è la stessa che era stata operata sul protocollo base del Memoryless: il reader invia la prima parte del codice ed i tag, per i quali la prima parte del codice è la stessa, rispondono con la parte mancante per completare il codice di 64 bit. Rispetto alla ricerca binaria si conserva la necessità di avere una perfetta sincronizazione sulle risposte dei tag, ma la condizione che il tag deve verificare per decider se trasmettere o meno non è più una disuguaglianza tra la richiesta e il codice proprio: il tag trasmette se le due parti iniziali di codice sono identiche. Il concetto per cui un transponder risponde è il medesimo della ricerca binaria normale, cioè la verifica della condizione di inferiorità del codice. Inviare infatti la prima parte del codice alla quale rispondono i tag che hanno un codice uguale fino a quel punto equivale ad inviare la prima parte del codice seguita da tutti bit di valore 1 ed alla quale tag rispondono se hanno un codice inferiore, così come visto nella versione base.

Al fine di ricavare la velocità dell’algoritmo si procede per analogia con la Binary search del paragrafo precedente. Il numero di iterazioni I che si compiono è il medesimo dell’algoritmo di base (formula (2.9)). Ogni iterazione del processo si compone di uno slot, dal momento che la richiesta del reader e le risposte dei tag sono complementari; tra le comunicazioni del reader e dei tag occorre inoltre sempre interporre 8 bit. In definitiva, per ogni iterazione è necessario uno slot e due intervalli di attesa di 8 bit, per un totale di 80 bit.

Richiesta del reader ε Tag in risposta 10110010 10100011 10110011 11100011 Risultato 1X1X001X

Richiesta del reader 10 Tag in risposta

110010 100011 110011 Risultato 101X001X

Richiesta del reader 1010 Tag in risposta 0011 Risultato 10100011

Richiesta del reader 10 Tag in risposta 110010

110011 Risultato 1011001X

Richiesta del reader 10110010 Tag in risposta (10110010)

Risultato 10110010

Richiesta del reader 10 Tag in risposta 110011 Risultato 110011 1°passo: Codici presenti: 10110010 10100011 10110011 11100011 2°passo: 3°passo: 4°passo: 5°passo: 6°passo:

Richiesta del reader ε Tag in risposta 11100011

Risultato 11100011

7°passo:

Figura 2.24 Esempio dello svolgimento della ricerca binaria ottima per la soluzione dei 4 codici presenti. Il simbolo εrappresenta la stringa vuota, cioè una richiesta a cui i tag ancora attivi rispondono con l’intero codice. Nel 5°passo la risposta del transponder è messa tra parentesi poiché nella realtà il tag non invia nessun bit di codice ma semplicemente un segnale che indica la corrispondenza tra il codice inviato dal reader e quello posseduto dal transponder.

Il numero di bit per completare il processo si ottiene moltiplicando tale valore per il numero di iterazioni scritto nella formula (2.9):

Tbit = 80 (2M-1) = 160M -80 (2.12) Trascurando gli 80 bit per la stessa motivazione già enunciata a proposito del Binary search, il tempo scritto in numero di slot risulta:

2.2.5 – Contactless

Il protocollo chiamato Contactless, la cui presentazione si trova descritta nell’articolo ‘Contactless Identification Device with Anticollision Algorithm’4[8], è pensato esplicitamente per la comunicazione nei sistemi RFID. Tale protocollo possiede una caratteristica che lo distingue dalla maggior parte dei protocolli pensati per la comunicazione RFID: il tempo necessario a completare la lettura di tutti i tag è privo di ogni tipo di casualità ed è vincolato esclusivamente dal numero di tag che sono coinvolti nella lettura. Ogni passo effettuato nell’esecuzione dell’algoritmo mira a scoprire un bit del codice di uno dei tag presenti. Come di consueto, per una lettura in modalità blocked access, il numero dei tag che deve essere letto è sconosciuto all’inizio del processo e per ottenere tutti i codici identificativi dei tag all’interno della zona occorreranno tanti arbitration process quanti sono i tag presenti. Si definisce ‘arbitration process’ l’insieme dei passi, in numero uguale al numero dei bit di codice, per individuare e subito dopo disattivare un singolo tag tra quelli ancora attivi. Un arbitration process, riferendosi al caso di tag che possiedono un codice formato da 64 bit, è composto da 64 ‘bit-arbitration step’ in ciascuno dei quali si scopre un bit del codice del tag che alla fine verrà inserito in memoria. E’ chiaro che tutti i tag attivi partecipano all’arbitration process ma solo uno di essi risponderà al reader fino all’ultima richiesta: è il transponder che viene letto nell’arbitration process in corso. Si entra ora nel dettaglio della comunicazione all’interno di un arbitration process (Figura 2.25): in risposta al segnale di partenza tutti i tag che non sono ancora stati letti inviano il valore (BitVal) del bit più significativo del codice, il reader osserva se ha ottenuto in risposta solo bit di valore 0, solo di valore 1 o entrambi.

_{[8] Marcel Jacomet, Adrian Ehrsam, Urs Gehrig. “Contactless Identification Device with Anticollision} Algorithm”. University of Applied Sciences Berne Biel School of Engineering and Architeture.

Nel primo e nel secondo caso il valore del bit (ContBit) che il reader invia per continuare a indagare il codice sarà quello del Bitval ricevuto, nel caso che alcuni tag abbiano risposto con 0 e altri con 1 si può proseguire indicando arbitrariamente uno dei due valori, ad esempio si sceglie di inviare, quando si verifica questa situazione, sempre 0 ( o sempre 1).

READER TAG

ContBit

BitVal BitVal BitVal

ContBit

Start ContBit

MSB LSB

1st _{bit 2}nd _{bit 64}nd _bit

. . . .

time

Figura 2.25 Sequenza temporale di un arbitration process, dal momento in cui reader invia il segnale di inizio fino a quando non sono conclusi tutti i 64 passi per acquisire il codice del tag. La figura è tratta da [8].

Per la comunicazione alternata tra transponder e reader, in cui Bitval e Contbit per l’i-esimo bit di codice costituiscono un bit-arbitration step, viene proposta una soluzione implementativa della logica del transponder: il diagramma di flusso di Figura 2.26, proposto in [8], suggerisce di utilizzare due stati logici per realizzare il bit-arbitration step. Nello stato SEND il transponder invia il Bitval e si porta in CONTINUE, dove confronta il valore di ContBit inviato dal reader con il Bitval trasmesso nell’istante precedente: se questi due valori sono uguali il transponder, in quanto ancora partecipe della letura, torna nello stato SEND dal quale trasmettere il bit successivo, altrimenti esce dall’attuale arbitration process e attende che ne inizi uno nuovo.

WAIT

SEND

CONTINUE

INACTIVE

‘Bit arbitration step’ Bitval=Contbit Bitval !=Contbit Nuova lettura globale Completati i 64passi dell’arbitration process Start (nuovo arbitration process)

Figura 2.26 Diagramma di flusso del transponder. La figura è tratta dall’articolo‘Contactless identification device with anticollision algorithm’

Alla fine di un arbitration process l’unico transponder rimasto, quello che ha risposto per tutti i 64 passi, entra nello stato INACTIVE: in questo stato non prende parte a nessuno degli altri arbitration che verranno effettuati e torna ad essere attivo solo dopo la ricezione del segnale che indica una nuova lettura globale. Il tempo che occorre per risolvere totalmente la lettura dei tag è indipendente da qualsiasi elemento di casualità, caso unico tra tutti i protocolli trattati. Gli arbitration process necessari saranno tanti quanti gli M tag presenti, poiché ogni arbitration process consiste di 64 bit-arbitration step, il numero totale di bit arbitration process sarà:

bit-arbitration process

t (M) = 64 M (2.14) Al fine di permettere al reader di rilevare senza problemi la risposta dei tag ad ogni bit-arbitration step, si rende necessaria una sincronizzazione sui BitVal trasmessi dai tag. [8]

fornisce una descrizione delle modalità in cui può svolgersi la comunicazione per avere un certo margine di sicurezza: ad ogni bit-arbitration step il reader invia il Contbit (zero o uno logico) con una codifica su otto bit mentre i tag rispondono codificando su quattro bit il valore logico del BitVal che devono inviare in risposta. In definitiva il tempo, espresso in numero di bit complessivamente inviati, è:

bit

t (M) = 64M*(8+4) = 768M (2.15)

2.3 – Protocolli deterministici con elemento casuale

2.3.1 - Random tree

All’interno del presente capitolo sono stati fino ad ora trattati algoritmi totalmente estranei ad un qualsiasi elemento di casualità; l’unico fattore discriminante è stato infatti sempre il codice seriale. Da ora in avanti verranno presi in esame solo protocolli in cui il codice di ogni transponder non avrà valore di discriminante e tutto sarà affidato ai generatori casuali di un numero intero appartenenti ai transponder. Tali generatori, a differenza di quelli dei protocolli Aloha, sono predisposti per estrarre un numero in genere nell’insieme degli interi da uno a quattro.

Il primo protocollo che viene presentato, con riferimento agli articoli “Analysis of Contention Tree Algorithms”5_{[9] e “Analytic properties of Multiple Access Trees”}6_[10], viene chiamato “Random tree” ed è nato, così come accade per molte delle altre soluzioni proposte, per risolvere il problema delle collisioni nell’accesso multiplo.

[9] Augustus Janssen, Marc de Jong. “Analysis of Contention Tree Algorithm”. IEEE trans. on information theory, vol.46,no.6, pp.2163-2172. September 2000.

_{[10] M. Kaplan, E. Gulko, “Analytic properties of Multiple Access Trees”. IEEE trans. on information theory,}

Entrando nel dettaglio, si indica con M il numero di tag coinvolti nella lettura e con k un numero, compreso tra 1 e B, estratto in modo equiprobabile dal generatore casuale di un generico tag. Ogni pacchetto inviato dal tag ha la durata di uno slot e gli slot sono raggruppati per formare frame lunghi esattamente B slot. Il procedimento è descritto nel modo seguente: nel primo frame i tag si posizionano nel k-esimo slot in dipendenza del numero estratto e attendono che il reader comunichi in quali eventuali slot del frame si sono verificate collisioni. Se sono state rilevate collisioni in uno o più slot, queste vengono risolte a partire dal primo slot in cui, in ordine di tempo, c’è stata collisione. I tag di tale slot vengono distribuiti su un nuovo frame con le stesse modalità in cui erano stati distribuiti all’inizio: si posizionano nel k-esimo slot in dipendenza del numero casuale estratto tra 1 e k. Le operazioni appena descritte conducono alla formazione di un albero - come si vede in Figura 2.27 - in cui ogni ramo termina quando il relativo frame finale non ha nessuno slot coinvolto in collisioni. Dalla figura è immediatamente deducibile ciò che d’ora in poi intenderemo con l’espressione ‘livello dell’albero’. Come si può osservare al livello 1 inizia la lettura e c’è un solo frame; al secondo livello vengono risolte le eventuali collisioni verificatesi negli slot del livello precedente e così per i successivi livelli.

4 4 5 2 0 2 0 3 1 3 0 2 0 2 0 1 0 1 1 1 1 2 1 0 0 1 1 1 1 0 1 0 1 1 2 3 4

Livello

B=3

M=13,

Figura 2.27 Svolgimento della ricerca ad albero per un numero di transponder pari a 13 e utilizzando un generatore casuale che estrae numeri tra 1 e 3 (B). Al passo iniziale, rappresentato nel livello 1, i 13 tag si

distribuiscono nei tre slot del frame generando collisioni su ciascuno di essi. A causa di ciò l’algoritmo prosegue con altri tre frame di tre slot, al livello 2: in ciascuno di questi frame si distribuiscono i transponder

che erano stati coinvolti in collisione in uno slot del frame al livello 1. Lo stesso criterio è seguito nel proseguio, ai livelli 3 e 4.

L’analisi teorica compiuta in modo dettagliato da [9], al quale si è fatto riferimento fino ad ora, permette di fare le dovute considerazioni sui parametri che determinano la velocità dell’algoritmo. Essi non possono che dipendere esclusivamente dal numero di tag M e dall’estremo B del generatore casuale.

Il numero medio di livelli necessari per portare a termine l’algoritmo è:

_ _{2 ln(M)}

L(M, B)

ln (B)

 (2.16) Il numero di frame di cui si compone mediamente l’albero è:

_

frame M

t (M, B)

ln(B)

 (2.17)

Poiché in ogni frame ci sono in ogni caso B slot è immediato scrivere anche il numero di slot di cui è composto l’albero:

_ slot BM t (M, B) ln(B)  (2.18) Il simbolo di approssimazione che compare nelle tre espressioni è giustificato dal fatto

che nell’analisi teorica riportata in [9] il valor medio e la varianza non convergono ad un valore finito ma contengono termini oscillatori, dovuti alla natura discreta dell’algoritmo, intorno al valore riportato nelle espressioni. L’espressione (2.18), dalla quale si ricava il numero totale di slot di cui è composto in media l’albero per la lettura di M tag, consente di trarre alcune conclusioni sulla velocità e sulla capacità di scalare del protocollo. Immediatamente evidente è la dipendenza lineare del tempo con il numero di transponder presenti e, traducendo tale dipendenza in un grafico per alcuni valori di B, è possibile riconoscere in tre il valore di questo parametro che minimizza il numero di slot necessari in media per completare la lettura.

0

20

40

60

80

100

0

50

100

150

200

250

300

Time (slot)

Tag number

B=2,4

B=3

B=5

Figura 2.28 Grafico ottenuto dall’espressione teorica della (2.18) in cui si esprime, al variare del numero di transponder, il numero medio di slot di cui si compone l’albero per alcuni significativi valori di B.

Una semplice ma interessante analisi teorica riguardo al Random tree è svolta nel contributo di Husch e Wood, dal titolo ‘Analysis of Tree Alghoritms for RFID Arbitration’ [11]. Il protocollo Rrandom tree a cui tale articolo si riferisce è il medesimo di quello descritto nell’articolo [9], illustrato all’inizio di questo paragrafo. La Figura 2.27, all’interno della quale è riportato l’albero, costituirà il riferimento per alcune considerazioni condotte nel corso dell’analisi.

Sia M il numero dei transponder da leggere e B il massimo numero casuale estratto. Si definiscono:

_

_

_

t (M) = numero medio di slot necessari per completare l'algoritmo c (M) = numero medio di slot che presentano collisione

Ne deriva che il tempo totale misurato in numero di slot è la somma degli slot che presentano collisioni con quelli in cui nessun transponder trasmette, alla quale si deve aggiungere il numero M di slot con singola trasmissione :

_ _ _

t(M) = c(M) + z(M) + M (2.19) Si indica con p la probabilità che un tag, ad un preciso livello L dell’albero, si trovi in uno dei BL slot di quel livello; in base alla nota formula per una distribuzione binomiale si ha la probabilità che k tag, sugli M totali, finiscano in un particolare frame al livello L:

k M P(k/M, L) = p (1- p) k       M-k (2.20) Poiché il generatore casuale estrae un numero tra 1 e B in modo equiprobabile, al livello L vi sono BL slot; la probabilità p che un tag sia in un certo slot al livello L è:

-L L

1

p = = B

B (2.21) Si può ricavare la probabilità che in uno slot al livello L vi sia assenza di trasmissioni semplicemente sostituendo nell’espressione (2.20) il valore di p dall’espressione (2.21) e ponendo k pari a zero:

0 M M -L M P(0 /M, L) = p (1- p) = (1- p) = (1- B ) 0       M M-1 (2.22) In modo analogo si ricavano le probabilità che in uno slot si verifichino o una sola o molte trasmissioni: 1 M-1 M-1 -L -L M P(1/M, L) = p (1- p) = Mp(1- p) = MB (1- B ) 1       (2.23) -L M -L -L M-1 P(k > 1/M, L) = 1- P(0 /M, L) - P(1/M, L) = 1- (1- B ) - MB (1- B ) (2.24)

A questo punto è necessario introdurre due ulteriori definizioni. Sia la probabilità che lo slot i-esimo al livello L sia visitato dalla ricerca ad albero; appare chiaro che per L=1, che rappresenta la radice, il suo valore è uno. Sia la probabilità che si verifichi una collisione nello slot i-esimo al livello L. Tale probabilità è già stata ricavata nell’espressione (2.24) così come la probabilità che in uno slot vi siano molti tag ed è indipendente da quale delle B

Li/M

q

Li/M

β

L _{slot si sta analizzando, perciò:} Li/M L/M = = P (k >1/M,

β

β

L)

L

(2.25) Dalla considerazione, peraltro già evidenziata in precedenza, che uno slot al livello L ha la medesima probabilità degli altri slot di essere visitato ed osservando che esso prende parte al processo solo se si ha una collisione nello slot al livello L-1 da cui dovrebbe essere generato, possono essere ricavate le tre uguaglianze:

Li/M L/M L-1/M L > 1

q = q =β se (2.26)

Il tempo medio necessario per terminare il processo di lettura corrisponde alla la somma dei su tutti i possibili livelli e su tutti gli slot che sono possibili per ogni livello, cioè B / Li M q L _: L B _ Li/M L 1 i=1 t(M ) = ∞ q =

∑ ∑

(2.27) Dalla precedente osservazione che , per L=1, assume il valore 1 e, per valori di L maggiori di uno, vale l’espressione (2.26), la sommatoria della (2.27) diventa:

Li/M q L L B B _ L Li/M Li/M L/M L/M L=1 i=1 L=2 i=1 L=2 L=1 t(M) =

∑∑

∞ q = 3 +

∑∑

∞ q =3 +

∑

∞ B q = 3 + B

∑

∞ B

β

(2.28)

Secondo la (2.25), è uguale alla probabilità che in un qualsiasi slot dell’albero vi sia collisione; sostituendo nella formula (2.28) l’espressione ricavata dalla (2.24) per quest’ultima probabilità, in definitiva si ha:

L/M β _ L -L M -L -L L=1 t(M) = 3 + B

∑

∞ B [1- (1- B ) - MB (1- B ) ]M-1 ) (2.29) La sommatoria di questi infiniti termini, con B parametro che assume il significato già discusso nella spiegazione del protocollo, è stata analizzata con il Matlab. Ne risulta che converge ad un valore finito. Nella tabella di Figura 2.29 sono raccolti i risultati per i tipici valori di B e, così come si era concluso grazie alla (2.18), il numero medio di slot di cui si compone l’albero è funzione lineare degli M transponder ed il valore di B pari a tre consente di ottenere le migliori prestazioni.

_ ( t M

B

t(M)

2

2.89M

3

2.73M

4

2.88M

5

3.12M

Figura 2.29 Tempo medio, in numero di slot, per la lettura degli M transponder. Esso è valutato per il parametro B, numero di slot di cui si compone ogni frame, che assume valori da 2 a 5.

Concludendo, è dunque possibile affermare che la tesi in base alla quale con il parametro B pari tre si ottengono i risultati migliori è, in realtà, erronea; i risultati ottenuti nella tabella di Figura 2.29 riportano infatti il numero effettivo di slot a cui ammonta lo sviluppo completo dell’albero. Una lettura completa necessita di un tempo totale leggermente differente: al numero di slot effettivo, durante i quali a comunicare sono i tag, occorre aggiungere il tempo speso nelle comunicazioni del reader ai transponder per dirigere lo