Capitolo 1: I protocolli Aloha

Capitolo 1: I protocolli Aloha

1.1 - Concetti Generali

La procedura di gestione multi accesso chiamata Aloha nasce negli anni ‘70 allo scopo di risolvere un importante 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.

L’impiego del protocollo Aloha si rende necessario per avere quelle prestazioni precluse nel caso di una comunicazione che avvenga secondo le regole di un time-division multiple access (TDMA), la quale prevede che ad ogni sorgente venga assegnata un preciso slot temporale nel corso del quale trasmettere. Dal momento che l’informazione che il trasmittente vuole inviare viene generata in un momento del tutto indipendente dallo slot ad esso assegnato, operare tramite un TDMA significherebbe ritardare il momento della lettura in modo proporzionale al numero delle sorgenti. Tranne il caso in cui il numero delle stazioni sia molto piccolo, tale ritardo rende inefficiente il protocollo. La soluzione che cerca di ovviare ad un simile inconveniente minimizzando quanto più possibile l’attesa è prospettata nel protocollo Aloha secondo un meccanismo semplice ma efficace: il trasmittente invia il proprio messaggio non appena quest’ultimo è pronto e, nel caso in cui la centrale non lo riceva correttamente, dovrà ritrasmettere il messaggio. Rispetto a quanto può accadere agendo con un TDMA, nell’Aloha il ritardo subito da un pacchetto dal momento in cui è stato inviato fino a quello in cui è correttamente ricevuto è generalmente limitato. 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, l’approccio appena mostrato presenta un limite evidente: le collisioni diventano molto

frequenti e il continuo ingresso di nuovi pacchetti le moltiplica rendendo il sistema instabile in quanto il tempo, dopo il quale un nuovo pacchetto mediamente viene letto, aumenta sempre più.

Nell’adattare la procedura Aloha per l’utilizzo nei sistemi RFID occorre innanzitutto fare una distinzione fondamentale: le modalità in cui può avvenire la lettura sono due e prendono il nome di Free access e Blocked access. L’approccio che viene usato nell’accesso multiplo è basato sul Free access ed è la modalità introdotta ad inizio paragrafo: le stazioni trasmittenti sono fisse e in grado di generare nel tempo pacchetti ad istanti non preordinati. La stazione centrale riceve sia i nuovi pacchetti sia quelli ritrasmessi, in quanto coinvolti in collisioni; quando la lettura di un pacchetto è portata a termine con successo la stazione centrale invia un segnale che è la conferma, per la stazione che ha appena trasmesso, del fatto che il suo messaggio è stato consegnato e può tornare in attesa di uno nuovo da inviare. Nei sistemi RFID le stazioni trasmittenti sono rappresentate dai transponder mobili e un sistema Free access prevederebbe a che essi trasmettano il loro contenuto non appena entrati nella zona di interrogazione di una nuova stazione centrale (reader). Allo stesso modo di come avveniva nell’accesso multiplo, il nuovo transponder trasmette immediatamente il proprio codice e, se la trasmissione va a buon fine, il reader provvede a comunicarglielo.

Al contrario, nel Blocked access, è il reader a decidere ad un certo momento di avere un inventario dei 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. Nel campo dell’RFID si è orientati verso la modalità Blocked access, modalità per la quale sono possibili molteplici varianti: dal protocollo base, chiamato Free running, in cui durante il processo di lettura c’è assenza di comunicazione dal reader ai transponder, si passa a protocolli più evoluti, classificabili in base alle informazioni che i transponder

possono ricevere dal reader. Tali informazioni consistono in segnali in grado di rendere inattivo un tag che ha finito di inviare correttamente il proprio messaggio, dando vita al protocollo Switch-off, oppure di fare in modo che mentre un tag sta comunicando con il reader gli altri restino silenziosi (protocollo Fast). Il nome che si trova comunemente per identificare il segnale che rende il protocollo di tipo Switch-off è quello di ACK, mentre per il Fast si utilizza il segnale di MUTE.

Un altro miglioramento consiste nel sincronizzare i tempi di inizio di una trasmissione del tag: nel protocollo base, che prende il nome di Aloha Pure, ogni sorgente può ritrasmettere in qualsiasi momento, il quale dipenderà da un generatore di numeri casuali.

Framed: I-Code

Slotted

Pure con MUTE: Fast

Pure

NO ACK

ALOHA

Framed: Iso 18000

Slotted

Pure con MUTE: Fast switch-off

Pure

ACK

Figura 1.1 Schema rappresentativo dei protocolli Aloha raggruppati secondo la presenza o meno del segnale inviato dal reader ACK.

Un metodo relativamente semplice per diminuire la probabilità che tale messaggio ha di entrare in collisione con quello di un'altra sorgente consiste nel suddividere il tempo in slot temporali e fare in modo che il messaggio sia inviato nello slot immediatamente successivo a quello in cui il messaggio è stato creato. Questa procedura è chiamata Aloha Slotted e diminuisce la probabilità di collisione: infatti, mentre nell’Aloha Slotted un messaggio subisce sovrapposizioni da parte di altri solo se trasmettono nello stesso slot, nell’Aloha Pure entra in collisione anche un pacchetto che ha iniziato a trasmettere nello slot

precedente. Infine c’è la possibilità di raggruppare più slot per formare un ‘frame’ nel quale tutti i tag attivi sono programmati per trasmettere una sola volta. Il numero di slot che compongono ogni nuovo frame è comunicato dal reader ai tag ed è scelto secondo criteri di massimizzazione della velocità di lettura. Tale procedura prende il nome di Aloha Framed.

Dopo aver descritto brevemente il segnale ACK e le possibili sincronizzazioni temporali necessarie per migliorare il rendimento di un protocollo Aloha, è ora possibile distinguere in due differenti classificazioni (Figure 1.1 e 1.2) i protocolli che saranno trattati in questo capitolo. Nella prima è sembrato opportuno mettere in risalto il ruolo giocato dal segnale ACK che, come si vedrà nell’analisi delle prestazioni dei singoli protocolli, nel caso in cui sia previsto in una qualsiasi delle possibili varianti, apporta un notevole miglioramento. Al contrario, il secondo tipo di classificazione è effettuato innanzitutto in base alla sincronizzazione temporale e successivamente al tipo di segnali informativi inviati dal reader; nel caso in cui l’evoluzione della lettura sia libera, cioè si tratti di Aloha Pure, si hanno quattro protocolli, due rispettivamente per ciascuna dei due possibili tipi di sincronizzazione Slotted e Framed. Sarà la cronologia dei protocolli di tale seconda classificazione ad essere adottata in questo capitolo per l’analisi di ogni singolo protocollo.

Switch off Free running Fast switch-off Fast Switch off Free running Switch-off: ISO 18000 Free running: I-Code

PURE SLOTTED FRAMED

ALOHA

Figura 1.2 Schema rappresentativo dei protocolli Aloha raggruppati secondo la tipologia di sincronizzazione utilizzata (Slotted e Framed) o la sua assenza (Pure).

1.2 – Aloha Pure

Un esempio importante di tag che sfrutta il protocollo Aloha Pure è descritto nel protocollo EM4022 della Marin1[1]. Le modalità nelle quali tale transponder può effettuare la lettura dei tag sono quattro. La modalità di funzionamento di base è costituita dal semplice Free running, per il quale in pratica, durante il processo di lettura, non vi è nessuna comunicazione dal reader ai tag. Ogni transponder, dall’inizio alla fine del processo, determinati dal reader, trasmette tutte le volte che il generatore casuale riporta un successo nell’estrazione di un numero.

TAG 1 TAG 2 TAG 3 Lettura corretta Collisione READER

Figura 1.3 Temporizzazione tipica di un Aloha Pure in modalità Free running.

Le altre tre possibili modalità sono ottenute mediante una comunicazione dal reader ai tag, che si concretizza in un segnale di ACK o di MUTE. L’ACK, contrazione di ‘acknowledgement’, è utilizzato per segnalare al tag che ha appena finito di trasmettere la corretta ricezione del suo pachetto da parte del reader. Dalla ricezione del segnale di ACK

[1] EM MICROELECTRONIC – MARIN SA, 2002. “EM4022: Multi Frequency Contactless Identification Device”.

il transponder cessa di prendere parte al processo di lettura. Il segnale di MUTE, al contrario dell’ACK, viene inviato appena un tag comincia a trasmettere ed è indirizzato a tutti i tag ad eccezione di quello che sta trasmettendo: esso ‘congela’ 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. Poiché il segnale MUTE è inviato dal reader non appena sente l’inizio di una nuova trasmissione, per implementare questa caratteristica, a differenza del caso in cui si utilizza solo il segnale di ACK, il reader deve possedere una doppia antenna, una per leggere il tag in trasmissione e l’altra per inviare contemporaneamente a tutti gli altri tag il segnale MUTE.

La modalità che utilizza solo il segnale di ACK è chiamata ‘Switch-off’. Per il grafico di Figura 1.3 è stato immaginato uno svolgimento casuale degli eventi in modalità Free running, in Figura 1.4, con la medesima successione degli eventi, si è immaginata una lettura in modalità Switch-off. Dal confronto si osserva il notevole impatto sulla riduzione delle collisioni che si ottiene con l’aggiunta del segnale ACK.

TAG 1 TAG 2 TAG 3

Lettura corretta _Collisione READER

Segnale di ACK

La modalità che prevede solo il segnale di MUTE è denominata ‘Fast’. Infine, il segnale di ACK e di MUTE possono coesistere, dando vita alla modalità ‘Fast switch-off’. Ancora una volta, per le figure 1.5 e 1.6, è stato mantenuto lo stesso svolgimento casuale degli eventi immaginato nella lettura in Free running. Entrambe le figure mettono in risalto le potenzialità del segnale di MUTE, che verranno confermate dall’analisi delle prestazioni dei due protocolli che includono il segnale di MUTE.

TAG 1 TAG 2 TAG 3

Lettura corretta Tag muto per τ sec

READER

Invio del segnale di MUTE e lettura corretta

Figura 1.5 Temporizzazione tipica di un Aloha Pure in modalità Fast. Il reader deve esser costruito in modo tale da leggere e contemporaneamente inviare il segnale di MUTE, in pratica deve possedere una

TAG 1

TAG 2

TAG 3

Lettura corretta Tag muto per τ sec

READER

Invio del segnale di MUTE, lettura e invio del segnale di ACK

Figura 1.6 Temporizzazione tipica di un Aloha Pure in modalità Fast switch-off

1.2.1 – Aloha Pure: Free running

Il protocollo Free running è in assoluto il più semplice per quanto riguarda la comunicazione tra sorgenti e lettore: il reader comunica ai tag solo quando deve iniziare e terminare la lettura, ogni tag comunica per tutta la durata della lettura, ad intervalli casuali, il proprio codice. Si è già detto che, con un funzionamento in Free running, si può operare solo in modalità Blocked access, perciò la valutazione di tale protocollo si basa sulla distribuzione di probabilità del tempo necessario per la lettura di tutti i tag, sul tempo medio ed è importante anche conoscere qual è il tempo dopo il quale con probabilità molto alta, che si pone del 99%, tutti i tag sono stati letti. Il numero di tag analizzato, rispetto alle applicazioni tipiche dichiarate per l’ RFID, varierà da poche unità a centinaia.

Il metodo seguito per poter valutare le caratteristiche del protocollo sopra citate è la simulazione Monte Carlo. Ogni singola simulazione genera una storia artificiale del sistema: poiché una singola corsa, per decidere quale direzione intraprendere, richiede la

generazione di numeri casuali, lo sviluppo di ogni simulazione è in generale differente dagli altri. Tenendo conto di questo fatto, per avere un campione di dati attendibile dal quale dedurre i parametri di bontà del protocollo, occorre effettuare molte prove e successivamente estrarre i valori dei parametri d’interesse.

Il programma che realizza lo sviluppo di una corsa è scritto in linguaggio C++ e simula il comportamento di un Aloha Free running utilizzando una serie di macchine a stati, una per il comportamento del reader e tante identiche quanti sono i tag presenti nel processo di lettura. Nella realtà il sistema Aloha Free running è un sistema a tempo continuo, ma il meccanismo di avanzamento del tempo usato nella simulazione non può essere che discreto, per intervalli fissi di durata ∆. Ad ogni incremento di ∆ ciascuna macchina a stati esegue le istruzioni contenute nello stato in cui si trova e aggiorna lo stato in cui dovrà trovarsi all’istante successivo. I tag si comportano in modo totalmente indipendente dalle azioni del reader: ad ogni passo il singolo tag, se non sta trasmettendo, estrae un numero casuale intero su un insieme finito di valori e, in caso di successo, passa allo stato attivo di trasmissione nel quale vi rimane per tutta la durata della trasmissione di un pacchetto. Poiché i tag si comportano tutti allo stesso modo e ognuno di essi opera indipendentemente dagli altri, al fine di contemplarli tutti è sufficiente eseguire tante volte una routine che li descrive quanti sono in numero i tag coinvolti nel processo di lettura. Per entrare più nel dettaglio del comportamento del tag si utilizza la descrizione della macchina a stati mediante il diagramma di flusso, riportato in Figura 1.7. Per il comportamento del tag sono sufficienti due stati: SILENT, in cui attende l’evento casuale che lo porti nello stato ACTIVE, dove vi resta per un tempo τ, che rappresenta la durata di un messaggio ed è espresso in multipli di ∆.

Tag i-esimo:

ACTIVE SILENT Messaggio non ricevuto correttamente Ritrasmissione Attesa per la ritrasmissione Count[i]<

τ

Figura 1.7 Schema a blocchi, utilizzato nel programma in C++, che descrive il comportamento di un tag

SILENT: è lo stato in cui il tag non trasmette, ad ogni incremento della variabile temporale viene estratto un numero intero compreso tra 1 e LMτ (L è un parametro che viene scelto in modo da minimizzare il tempo complessivo di lettura, M è il numero di tag presenti). Il tag comincia a trasmettere, cioè passa nello stato ACTIVE, solo se il numero estratto vale 1; in questo modo si rende il passaggio di stato una variabile temporale aleatoria di Poisson di media 1/( LMτ)

ACTIVE: in questo stato il tag sta inviando il messaggio al reader, perciò attende che sia trascorso un tempo τ, la durata di un pacchetto, per poi ritornare nello stato SILENT.

Il tempo τ può essere definito uno slot temporale e diventerà l’unità di misura con cui valutare i risultati di ogni singola corsa. La scelta del valore di τ influisce sul grado di approssimazione che si vuole ottenere: se ipotizziamo che in realtà l’Aloha Pure sia un sistema tempo continuo (rinunciamo alla sincronizzazione dei clock dei tag) risulta evidente come il sistema simulato, a tempo discreto, si avvicini il più possibile alla realtà continua nel caso in cui le grandezze temporali in gioco, come τ e il tempo di attesa prima di una ritrasmissione, siano molto più grandi della variabile temporale di base. Si è già detto che τ è espresso in multipli di ∆: facendo in modo che l’incremento ∆ sia

rappresentato con l'unità di tempo è un buon compromesso scegliere per τ un valore pari a 20: infatti quanto più τ è grande tanto più aumenta la durata del calcolo per la risoluzione dell’ algoritmo.

Al contrario dei tag, che durante tutto lo svolgimento dell’algoritmo operano in modo indipendente da ogni fattore esterno, il comportamento del reader è esclusivamente dipendente dalle azioni dei tag. Una variabile, chiamata ‘activity’ ed aggiornata ad ogni incremento della variabile tempo, ha la funzione di contare quanti trasponder sono attualmente attivi. Come illustrato dal diagramma di Figura 1.8, il reader rimane o passa allo stato di WAIT se la variabile activity assume valore nullo (nessun tag sta trasmettendo), mentre si trova in stato di COLLISION se tale variabile è maggiore di uno. In stato di WAIT e con il passaggio di activity ad uno, il reader inizia una nuova lettura portandosi nello stato di READ. Il pacchetto di cui è appena iniziata la lettura sarà acquisito correttamente solo se durante la trasmissione non intervengono trasmissioni di altri transponder. Dallo stato READ si può uscire attraverso IDENTIFY se durante il tempo τ della lettura del pacchetto activity resta sempre ad uno, oppure andando nello stato COLLISION se un altro tag inizia a trasmettere prima che il tempo τ sia trascorso completamente. Il pacchetto che il tag invia al reader è costituito dal suo codice identificativo ed il reader ha interesse ad acquisire tutti i codici presenti per effettuare in un secondo momento una lettura selettiva. Poiché, a causa del protocollo che viene usato, uno stesso codice può essere letto più volte all’interno del processo occorre un registro che indichi al reader se il codice che ha appena terminato di leggere incrementa o meno il numero dei tag letti. Questo registro che memorizza i codici letti è un vettore chiamato ‘Stored [i]’, la sua dimensione è uguale al numero di tag coinvolti nel processo e un suo elemento assume valore uno se il tag i-esimo è stato letto, zero altrimenti. Quando il reader si trova nello stato di IDENTIFY, cioè una corretta lettura è stata appena portata a termine,

il contatore predisposto per il numero dei tag letti è incrementato solo se nel controllo del vettore Stored [i] risulta che il codice i-esimo non è ancora stato acquisito.

WAIT READ IDENTIFY Count_red<

τ

Reader:

COLLISION Activity=1 Activity=0 Activity>1 Activity=1 & Activity>1 Activity=0 Activity=1 & Count_red=

τ

Activity>=1 Activity=0

Figura 1.8 Schema a blocchi, utilizzato nel programma in C++, che descrive il comportamento del reader

WAIT: Nessun tag era in fase di trasmissione nell’istante precedente, perciò il reader qui verifica se un tag inizia a trasmettere: se ciò avviene, activity passa ad uno, si azzera il contatore preposto per l’attesa di τ, chiamato ‘Count_red’, e lo stato successivo sarà READ. Chiaramente se più tag cominciano a trasmettere contemporaneamente, cioè activity assume valore maggiore di uno, si ha il passaggio nello stato COLLISION.

READ: il reader è in fase di lettura di un pacchetto. Nel caso in cui altri tag comincino a trasmettere, cioè activity diviene maggiore di uno, salta allo stato COLLISION, altrimenti incrementa Count_red e se esso ha raggiunto il valore τ si passa allo stato IDENTIFY.

IDENTIFY: in questa fase il reader verifica semplicemente se il pacchetto appena letto è nuovo o è già stato letto precedentemente. Nel caso in cui il vettore Stored [i] indichi che il tag appena letto è al primo passaggio aggiorna il numero dei tag letti, dopodichè passa automaticamente a READ.

COLLISION: Più tag stanno trasmettendo per cui si deve solo attendere che activity passi a zero per tornare nello stato di WAIT.

Prima di valutare la funzione di distribuzione, tempo medio e tempo per la lettura con una probabilità del 99%, occorre considerare qual è l’estremo superiore del numero casuale estratto per la ritrasmissione che massimizza la velocità del protocollo. Nell’Aloha Pure il numero estratto, ad ogni incremento della variabile temporale di base, è un numero intero nell’intervallo compreso tra 1 e LMτ, dove L è un numero intero, M e τ sono

rispettivamente il numero di tag e la durata di uno slot.Il tag passa allo stato di

trasmissione solo se tale numero vale 1 in modo da rendere il passaggio di stato una variabile di Poisson di media 1/( LMτ). Le conseguenze della scelta di un valore più grande o più piccolo di L sono, come è facile intuire, semplici da analizzare : un L molto grande rende le ripetizioni molto rare e le collisioni più rare; viceversa un L troppo piccolo intensifica a tal punto il traffico che per un valore inferiore a 2 si può osservare come il tempo medio di lettura cominci a crescere molto rapidamente a causa delle frequenti collisioni facilmente immaginabili. In Figura 1.9, che riporta il tempo medio di lettura al variare di L, è possibile osservare che la scelta di tale parametro che massimizza la velocità di lettura è un valore nell’intervallo tra 3,5 e 4,5.

1

2

3

4

5

6

7

8

9 10

0

1000

2000

3000

4000

5000

6000

M=30

M=80

Average read time

L

Figura 1.9 Tempo medio di lettura al variare dell’estremo superiore del numero casuale estratto (LMτ) per l’attesa tra la fine di una trasmissione e la successiva.

Poichè ad inizio lettura risulta ignoto il numero di tag che partecipano al processo, si è impossibilitati a fissare l’estremo che rende ottimali le ripetizioni dei pacchetti dei tag. Sia:

1 LM =

λ

_τ

(1) E’ ragionevole pensare che l’estremo LMτ

,

cioè λ

,

venga fissato all’inizio di una lettura in modalità Blocked access, dalla Figura 1.10 è immediata una semplice osservazione: poiché per fissare l’estremo superiore, scelto un valore del parametro L pari a 4, non resta che scegliere il valore di M, è conveniente sovrastimare, piuttosto che sottostimare, il numero di tag che potrebbero partecipare alla lettura. Questo è giustificabile con un semplice esempio numerico tratto direttamente dalla figura: per un numero di 30 tag presenti vi è una piccola differenza sul tempo medio di lettura, all’incirca del 15%, tra lo stimare per M il suo valore reale, 30, o il valore di 80, al contrario, a parti inverse, con un numero di tag pari a 80 la differenza sarebbe del 100%.

0

20

40

60

80 100 120 140

100

1000

10000

80000

Av

e

ra

ge tim

e (

slot)

Tag number

λ

=1/(120

τ

)

λ

=1/(320

τ

)

Figura 1.10 Tempo medio per la lettura scegliendo diversi valori per il valore λ, frequenza media di ripetizione del messaggio del tag. Poiché λ=1/(LMτ) e in questo caso il valore di L ottimale è pari a 4, scegliere λ=1/(120τ) significa fissare la frequenza ottimale di ripetizione per 30 tag, λ=1/(320τ) per 80.

Nelle prossime simulazioni, a meno che non venga chiaramente esplicitato il contrario, il programma verrà eseguito con il valore di λ ottimale, cioè L pari a quattro, ed M pari al numero di tag che prendono effettivamente parte al processo. Saranno ricavate le distribuzioni di probabilità del tempo di lettura di un certo numero di tag, poi saranno presentati dati interessanti quali il tempo medio per la lettura totale e il tempo per la lettura globale per raggiungere la sicurezza che, nel 99% delle prove, la lettura venga portata a termine. Tale tempo verrà spesso chiamato ‘Tempo 99%’ o ‘t99’. Nelle Figure 1.11 e 1.12

sono rappresentati l’andamento di una singola lettura di 30 tag e il numero medio di tag letti al passare del tempo. Sebbene questi grafici non diano importanti indicazioni sulle prestazioni di un algoritmo, sono tuttavia utili per comprendere l’evoluzione di una lettura: dopo un periodo iniziale, all’incirca il 20% del tempo totale, nel quale si legge il 70% dei

esempio, in Figura 1.11 si osserva che gli ultimi due codici sono acquisiti ogni 120 slot, mentre nel primo tratto, in un tempo equivalente, ne erano stati letti solo 20.

0 100 200 300 400 500 600

0

5

10

15

20

25

30

Tag number read

Time (slot)

Figura 1.11 Simulazione del comportamento dell’algoritmo per la lettura di 30 tag al passare del tempo.

0

200

400

600

800

1000

0

5

10

15

20

25

30

Average tag number read

Time (slot)

Figura 1.12 Numero medio di tag letti al passare del tempo quando si leggono 30 tag. Il numero di simulazioni su cui si fa la media è 200.

Il grafico della densità di probabilità (Figura 1.13), costruito con 3000 simulazioni, analizzando una lettura di 30 tag, denota una distribuzione non simmetrica, pertanto non di tipo gaussiano. La presenza di una coda significativa si può notare anche dalla relativa funzione di distribuzione della figura seguente. Nonostante le 3000 simulazioni impiegate non siano un campione ottimale per valutare la funzione di distribuzione oltre una percentuale di acquisizione del 99%, in essa è comunque significativo osservare che il tempo per passare dalla percentuale di acquisizione dei tag del 99% a quella del 99,9% è pari all’incirca al 25% del tempo totale impiegato dal t99. In Figura 1.15 tempo medio e

Tempo 99% completano il quadro delle prestazioni: il tempo medio scala in modo lineare con coefficiente 25, il Tempo 99% non risulta perfettamente lineare, ma si può approssimare a tale andamento, con un coefficiente 40. Il t99 è un dato più importante del

tempo medio, in quanto l’algoritmo non permette di sapere il momento in cui sono stati letti tutti i tag. In conseguenza di tale considerazione il t99 si presenta come uno strumento

valido per decidere quando concludere la lettura con un basso margine di errore.

0

400

800

1200

1600

0

50

100

150

200

250

300

O

ccur

renci

es

Time (slot)

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

300

600

900

1200

1500

5.0 20.0 40.0 50.0 60.0 80.0 95.0 99.0 99.9

Distribution function (%)

Time (slot)

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

0

50

100 150 200

250 300

0

2

4

6

8

10

12

14

16

average time

t

₉₉

T

im

e (s

lo

t,1

0

3

)

Tag number

Figura 1.15 Tempo medio e tempo per la lettura di tutti i tag con una probabilità del 99%. Il numero di simulazioni effettuate per ogni numero di tag trattato è 200.

1.2.2 – Aloha Pure: Switch-off

Rispetto all’Aloha free running descritto nel paragrafo precedente, il protocollo Aloha switch-off aggiunge un segnale che il reader può inviare ai tag durante il processo di lettura: il segnale di acknowledgment che spegne il tag che ha appena concluso una lettura corretta. Le operazioni che vengono effettuate da un tag sono molto semplici: esso invia il pacchetto informativo lungo _{τ e, se nel periodo tack successivo alla fine della trasmissione,} riceve dal reader la conferma che la lettura è stata correttamente eseguita, entra in uno stato inattivo, altrimenti ritrasmette dopo aver atteso un tempo aleatorio che segue una distribuzione poissoniana a media λ. In Figura 1.16 è riportata una temporizzazione tipica, grazie alla quale è possibile osservare quello che viene definito ‘periodo vulnerabile’, vale a dire l’arco di tempo durante il quale non dovrebbero avere inizio altre comunicazioni ad esclusione di quella che vorremmo vedere portata a termine con successo.

Periodo vulnerabile: 2τ τ tack

Periodo casuale Messaggio lettocorrettamente Messaggi in collisione

collisione

Figura 1.16 Temporizzazione tipica di un sistema Aloha che prevede la comunicazione del segnale di lettura avvenuta con successo (ACK) dal reader al tag.

Poichè l’Aloha switch-off, a differenza dell’Aloha free running, prevede anche la modalità Free access, della quale si può effettuare una precisa analisi teorica che permette di verificare la validità della simulazione Monte Carlo, effettuata con un programma scritto in C++ ed unico strumento per ottenere risultati nel Blocked access, tratteremo entrambe le modalità, a partire da quella Free access.

1.2.2.1 – Aloha Pure switch-off: Free access

Una prima deduzione su questo tipo di procedura può essere fatta in modo intuitivo: quando l’ingresso di nuovi tag è un evento sporadico può accadere che vi sia qualche collisione, ma è ragionevole pensare che alla fine ogni trasponder comunichi favorevolmente il proprio contenuto.

E’ facile immaginare cosa accada nel caso di alta frequenza di nuovi ingressi: le collisioni si moltiplicano e i nuovi entranti non fanno altro che amplificare questo andamento; il tempo medio per la lettura di un tag si allunga sempre più e l’algoritmo si dice in questo caso instabile.

Le considerazioni appena svolte sono supportate dall’analisi teorica della procedura e dall’osservazione dei due indici che determinano la bontà del sistema, il throughput ed il tempo medio tra l’istante in cui un tag entra nella zona di interrogazione e invia per la prima volta il suo codice e l’istante in cui il suo contenuto viene letto correttamente. L’analisi teorica e le definizioni si fondano sull’ ipotesi che la durata di un pacchetto comunicato dal tag al reader abbia una durata costante e che la comunicazione non sia affetta da errori né in trasmissione né in ricezione. Entrambi gli indici dipendono da un parametro fondamentale: il carico medio, indicato con G. Se T è il tempo di osservazione scelto della lunghezza di qualche τ, M il numero di tag che nell’arco di T trasmettono almeno una volta e ri il numero di trasmissioni effettuate da ogni singolo tag, il tempo

gli M tag di ri*τ. Il carico medio G è definito G come il rapporto tra questo tempo e il tempo d’osservazione: M i i=1 r t G = T

∑

(1.2)

In altri termini il carico medio indica il numero medio di pacchetti che sono globalmente inviati in un tempo τ. Il throughput medio S sarà il numero medio di pacchetti letti correttamente nel tempo τ; definendo ni il numero di trasmissioni, terminate con successo,

compiute nel periodo T la definizione di throughput è espressa dal rapporto: M i i=1 n t S = T

∑

(1.3)

Introduciamo ora l’ipotesi che il processo d’arrivo dei pacchetti nuovi e ritrasmessi segua una distribuzione di Poisson, in cui la variabile aleatoria che rappresenta il numero di trasmissioni che si hanno in un periodo di osservazione abbia media attesa λ. Per la distribuzione di Poisson vale:

w λ

(λ) P [w trasmissioni nel periodo di osservazione] = e

w!

−

(1.4)

Si ha interesse di conoscere la probabilità che nessuna trasmissione interferisca con quella che si vuole vedere portata a termine correttamente, cioè la probabilità che nessuna trasmissione avvenga nel periodo vulnerabile, definito in precedenza, della lunghezza 2τ. E’ stato già osservato che il carico medio G fornisce una misura del numero medio di trasmissioni che si hanno nel tempo τ di uno slot. La variabile aleatoria, che rappresenta il numero di trasmissioni in un periodo 2τ, avrà pertanto una media attesa di 2G. Sostituendo le nuove variabili nella (1.4):

k -2G

(2G) P [k trasmissioni in 2τ] = e

La probabilità che nessuna trasmissione avvenga in un tempo 2τ si ottiene ponendo k pari a zero nella (1.5): 0 -2G -2G (2 G) P [0 trasmissioni in 2τ] = e = e 0! (1.6) Il throughput, definito come il numero medio di successi in uno slot, si può ottenere dal prodotto tra la probabilità che nessuna trasmissione avvenga nel periodo vulnerabile e il carico medio:

-2G

S= GP [no collisioni]= GP [0 trasmissioni in 2t] = G e (1.7)

.

0

1

2

3

4

0.00

0.05

0.10

0.15

0.20

S

G

Si ricerca ora il tempo che in media deve attendere un pacchetto prima di essere letto. Il numero medio di tentativi che un tag compie prima di essere letto correttamente è:

2G G

= e

S (1.8) Sottraendo la trasmissione che ottiene successo si ottiene il numero medio di trasmissioni che hanno un insuccesso:

G_{-1 = e -1}2G

S (1.9) Il tempo medio che un tag deve attendere prima di avere una lettura corretta è la moltiplicazione del numero di ripetizioni, ricavato nella (1.9), con il tempo che trascorre, in media, tra due successive ripetizioni. Questo ultimo dato viene ricavato dalla definizione di G, espressa nella formula (1.2), con l’ipotesi che gli M transponder presenti siano indipendenti. Ciò permette di scrivere che, in un periodo di osservazione, ogni tag trasmetta mediamente un numero r di volte:

M i i=1 r τ Mr τ G = = T T

∑

(1.10)

Il tempo che intercorre tra due ripetizioni, definito ts, è il rapporto tra il tempo di osservazione e il numero di ripetizioni che un tag compie al suo interno. Introducendo successivamente anche il parametro L, definito come il rapporto tra M e G, dalla formula (1.10) si ha:

s

T M τ

t = = = L τ

r G (1.11)

A questo punto è un’operazione relativamente semplice calcolare il tempo medio atteso da un tag prima di ricevere una lettura corretta:

2G 2G

tag ack ack s ack ack

E[T ] = τ + t + (e -1)(τ + t + t ) = τ + t + (e -1)(τ + t + L τ) (1.12)

che scritta in multipli di diviene: τ

2G

tag ack ack

E[T ]/ τ = 1+ t / τ + (e -1)(1+ t / τ + L) (1.13)

E’ ragionevole immaginare che il tempo d’attesa per la conferma della lettura sia

trascurabile rispetto alla lunghezza di uno slot :

ack t τ 2G tag E[T ]/ τ = 1+ (e -1)(1+ L) (1.14)

Dall’espressione appena ricavata si osserva che il ritardo medio che subisce un pacchetto dipende sia dal carico medio G che dalla scelta del parametro L. L’influenza che il parametro L ha sul valore del carico medio può essere descritta in modo qualitativo: un piccolo valore di L aumenta il numero medio di trasmissioni che ogni tag compie in un periodo di osservazione all’interno dell’intervallo dal momento che trasmette per la prima volta fino a quando non riceve l’ACK, questo aumenta il valore del carico medio. Viceversa si può affermare che al crescere del valore di L le ripetizioni, compiute dai tag che sono stati coinvolti in collisione, sono più distanti nel tempo provocando una diminuzione del carico medio. Per il grafico di Figura 1.18 è stato scelto, per il parametro L, il valore 16.

0.02

1

0.1

1

2

10

100

500

Average t

im

e

(sl

o

t)

G

Figura 1.18 Ritardo medio di lettura in funzione del carico medio. Il ritardo è quello osservato da un singolo pacchetto dal momento in cui è trasmesso per la prima volta fino a quando non riceve il segnale di

acknowledgement, cioè di lettura avvenuta con successo. Il parametro L vale 16.

Il sistema è stato simulato allo scopo di ottenere i medesimi risulati ottenuti per via analitica: throughput e tempo di attesa in relazione al carico. Il programma per effettuare la simulazione segue, con poche significative modifiche, lo schema utilizzato nell’Aloha Free running: occorre aggiungere al tag lo stato inattivo in cui si porta dopo aver ricevuto l’acknowledgment e dal quale esce dopo un tempo casuale,variabile aleatoria di Poisson, che significa che un nuovo pacchetto è pronto. Questa nuova fonte di aleatorietà viene inserita con lo stesso concetto di come era stata implementata per il tempo di attesa per la ritrasmissione: allo stato inattivo (SLEEP) corrisponde la mancanza di un nuovo pacchetto da trasmettere e, ad ogni incremento della variabile temporale di base, viene estratto un numero intero tra 1 e λ e se questo vale 1 significa che il tag ha un nuovo pacchetto da trasmettere. Solo quando questo avviene c’è il passaggio allo stato attivo in trasmissione (ACTIVE), dal quale, se trascorso il tempo τ, tempo nel quale il tag trasmette il pacchetto,

il reader mette ad uno la variabile di acknowledgement, il tag torna nello stato di SLEEP, altrimenti il suo nuovo stato sarà quello di SILENT, in cui si attende che si verifichi la condizione che aleatoriamente faccia tornare il tag a ritrasmettere lo stesso messaggio.

SLEEP ACTIVE SILENT Nuovo messaggio pronto Messaggio ricevuto correttamente Messaggio non ricevuto correttamente Ritrasmissione Nessun nuovo messaggio pronto Attesa per la ritrasmissione Count[i]<

τ

Tag i-esimo:

Figura 1.19 Schema a blocchi, utilizzato nel programma in C++, che descrive il comportamento di un tag

Il reader si comporta in un modo quasi identico a quanto faceva nell’Aloha free running: ora, essendo presente il segnale di ACK, non ha più bisogno di utilizzare il vettore Stored che teneva memoria di quali tag erano già stati letti almeno una volta, poiché non si rende più necessaria la verifica che un pacchetto sia alla prima trasmissione positiva. Allo scopo di simulare il segnale di ACK, che nella realtà serve per spegnere il tag, il reader presenta nello stato IDENTIFY un’istruzione che manda nello stato SLEEP il tag che ha trasmesso.

WAIT READ IDENTIFY Count_red<

τ

Reader:

COLLISION Activity=1 Activity=0 Activity>1 Activity=1 & Activity>1 Activity=0 Activity=1 & Count_red=

τ

Activity>=1 Activity=0

Figura 1.20 Schema a blocchi, utilizzato nel programma in C++, che descrive il comportamento del reader

Per ottenere throughput medio e tempo medio d’attesa dalle simulazioni occorre aggiungere dei contatori ausiliari all’interno del programma: seguendo le definizioni di carico, throughput e ritardo medio c’è bisogno, all’interno di un tempo di osservazione, di un contatore del tempo totale durante il quale complessivamente i tag trasmettono, di un contatore di quanti tag hanno avuto una lettura portata a termine con successo e un contatore su ogni tag che serva a contare il tempo trascorso tra la prima trasmissione e la ricezione del segnale ack. Per aver conto del tempo totale di trasmissione è stato sufficiente aggiungere ad un contatore, ad ogni passo, il contenuto della variabile activity. Altrettanto semplice è scoprire quanti tag hanno trasmesso: basta predisporre un contatore che incrementa di uno ogni volta che la variabile ACK è posta ad uno. La scelta per L, già discussa in precedenza, è ancora il valore 16 e un carico medio variabile sull’intervallo

desiderato è stato ottenuto con una frequenza di ingresso di nuovi pacchetti diversa ad ogni prova. Il tempo di osservazione è stato scelto in modo tale da avere un sistema già a regime: la simulazione è stata fatta girare fino ad un tempo di 10000 e i contatori sono abilitati solo dopo l’istante 2000 (una singola ripetizione è effettuata in media dopo un tempo di 160). Il tempo di osservazione risulta pertanto pari a 8000.

0

1

2

3

4

5

0.00

0.05

0.10

0.15

0.20

Simulato

Teorico

S

G

Figura 1.20 Throughput al variare del carico. Il grafico teorico è quello già ricavato in precedenza, i dati sono stati ottenuti dalla simulazione facendo più prove con probabilità crescente di generazione di nuovi

pacchetti.

Per il ritardo l’uso dei contatori è un po’ più laborioso: su ogni transponder è previsto un contatore incrementale del tempo che inizia al passaggio di stato da SLEEP a ACTIVE e termina quando da ACTIVE si torna a SLEEP. A questo punto il suo contenuto è passato immediatamente a un contatore del ritardo globale, il cui valore finale sarà diviso per il numero di transponder che hanno inviato con successo il loro codice.

0.1

1

5

1

10

100

Average t

ime (slot)

G

Simulato

Teorico

Figura 1.21 Tempo medio d’attesa del messaggio di un nuovo tag, in numero di slot, al variare del carico. Il grafico teorico è quello già ricavato in precedenza, i dati sono stati ottenuti dalla simulazione facendo più

prove con probabilità crescente di generazione di nuovi pacchetti.

1.2.2.2 – Aloha Pure switch-off: Blocked access

Attraverso l’analisi teorica dell’Aloha Switch-off in modalità Free access condotta nel paragrafo precedente si è verificato il corretto funzionamento del programma impiegato nella simulazione Monte Carlo. Il programma che si va ora ad utilizzare per la modalità Blocked access dell’Aloha Switch-off prevede una sola modifica: una volta entrato nello stato SLEEP, cioè solo dopo aver ricevuto il segnale di ACK in seguito ad una lettura corretta, al contrario di ciò che avveniva in Free access, il transponder non parteciperà più

al processo di lettura. Se la trasmissione precedente non è andata a buon fine, il tag decide il momento in cui deve trasmettere secondo un processo di Poisson. Il numero di transponder che partecipano al processo è M, τ la durata di un messaggio e L un parametro, la media λ di questo processo aleatorio è definita come nella (1.1).

SLEEP ACTIVE SILENT Messaggio ricevuto correttamente Messaggio non ricevuto correttamente Ritrasmissione Attesa per la ritrasmissione Count[i]<

τ

Tag i-esimo:

Figura 1.22 Schema a blocchi, utilizzato nel programma in C++, che descrive il comportamento di un tag

Così come è stato fatto per l’Aloha free running, anche ora sembra interessante ricavare il valore di λ che rende ottimale il tempo medio per la lettura degli M transponder presenti nella zona. Fissati M e τ il valore di λ viene a a dipendere esclusivamente da L e dal grafico di Figura 1.23 ottenuto mediante simulazione, è possibile osservare che con il valore 2 si ottiene il λ desiderato.

1

2

3

4

5

200

400

600

800

1000

Time (slot)

L

M=30

M=80

Figura 1.23 Ricerca del valore di L ottimale per il numero casuale estratto per la ritrasmissione. Il valore dell’estremo superiore del numero intero estratto ad ogni passo è LMτ e un transponder trasmette se si estrae

il valore 1.

Trattandosi di un processo di Poisson, il valore di λ può essere definito come la frequenza media di ripetizione del messaggio fino al momento in cui il tag, letto correttamente, non cessa la sua attività.

Tale parametro viene fissato all’inizio di una lettura in Blocked access e per la scelta del suo valore vale la stessa osservazione fatta per la modalità Free running: poiché per fissare il suo valore, scelto il valore ottimale di L, pari a 2, non resta che scegliere il valore di M, è conveniente sovrastimare, piuttosto che sottostimare, il numero di transponder, sconosciuto all’inizio, che potrebbero partecipare alla lettura. Questo è giustificabile con un semplice esempio numerico tratto direttamente dalla Figura 24: per un numero di 30 tag presenti vi è una piccola differenza sul tempo di lettura, all’incirca il 20%, tra lo stimare per M il suo valore reale il valore di 100. Al contrario, a parti inverse, con un numero di tag da leggere pari a 100 la differenza sarebbe dell’80%.

10

30

100

200

100

1000

10000

20000

λ

=1/(60

τ

)

λ

=1/(140

τ

)

λ

=1/(200

τ

)

Average t

ime (sl

o

t)

Tag number

Figura 1.24 Tempo medio per la lettura scegliendo diversi valori per il valore λ, frequenza media di ripetizione del messaggio del transponder. Poiché λ=1/(LMτ) e in questo caso il valore di L ottimale è pari a

2, scegliere λ=1/(60τ) significa fissare la frequenza ottimale di ripetizione per 30 tag, λ=1/(140τ) per 70 e λ=1/(200τ) per 100.

Le prossime simulazioni verranno eseguite con il valore ottimale di λ, cioè L pari a due ed M pari al numero di tag da leggere. Saranno ricavati gli andamenti per il numero dei transponder letti al passare del tempo mediati su 200 prove, la densità di probabilità e la relativa funzione di distribuzione per una lettura di 40 tag. Saranno infine presentati il tempo medio per la lettura totale e il tempo 99%.

0

50 100 150 200 250 300 350 400

0

5

10

15

20

25

30

35

40

Tag number read

Time (slot)

Figura 1.25 Numero medio di tag letti al passare del tempo. I tag coinvolti nella lettura sono 40 e per ogni particolare numero i tag indagato si utilizza il valore di λ ottimale, cioè con L=2. il numero di simulazioni con

la quale si costruisce il grafico è 200.

100 150 200 250 300 350 400 450

0

100

200

300

400

Occurencies

Time (slot)

Densità di probabilità, normalizzata su 3000 simulazioni, del tempo necessario per effettuare una lettura completa di 40 tag. L’unità di misura del tempo è un singolo slot.

La densità di probabilità, con una distribuzione non del tutto simmetrica, presenta una coda significativa che si può notare anche dalla relativa funzione di distribuzione della figura seguente. Su un totale di 3000 simulazioni, non abbastanza per trarre conclusioni certe per la funzione di distribuzione oltre una percentuale di acquisizione del 99%, è comunque significativo osservare che il tempo per passare dalla percentuale di acquisizione dei tag del 99% a quella del 99,9% è pari all’incirca al 7% del tempo totale impiegato per raggiungere il livello di sicurezza del 99%. Tale dato, confrontato con il 25% del caso Aloha free running, evidenzia già un notevole miglioramento grazie all’utilizzo del segnale di ACK l’entità del quale è definita chiaramente mediante l’analisi del tempo medio e del tempo 99%. Sia Free running che Switch-off scalano ancora in modo lineare rispetto al numero di tag ma, mentre nel primo caso i coefficienti erano rispettivamente 25 per il tempo medio e 40 per il t99, ora valgono 7 e 9, facendo risultare i due protocolli su piani qualitativi nettamente distinti.

200 225 250 275 300 325 350 375 400

5.0

20.0

40.0

60.0

80.0

95.0

99.0

99.9

Dist

ribut

ion f

unction (%)

Time (slot)

20

40

60

80

100

0

200

400

600

800

1000

average time

t

₉₉

Time (slot)

Tag number

Figura 1.28 Tempo medio e tempo per la lettura nel 99% dei casi. Il numero di transponder analizzati cade nell’intervallo da 10 a 100 e il numero di simulazioni per ogni dato è 200.

10

100

1000

50

100

1000

10000

average time

t

₉₉

Tim

e

(s

lo

t)

Tag number

Figura 1.29 Tempo medio e tempo per la lettura nel 99% dei casi. Il numero di tag analizzati cade nell’intervallo da 10 a 1000 e il numero di simulazioni per ogni dato è 200.

1.2.3 – Aloha Pure: Fast

La modalità chiamata Fast, già illustrata nella presentazione dei quattro protocolli dell’Aloha Pure, è un tipo di miglioramento alternativo alla modalità Switch off in quanto prevede che il reader comunichi ai transponder solo il segnale di MUTE e non quello di ACK, cioè la segnalazione di lettura avvenuta correttamente. Nel momento in cui, con nessun’altra comunicazione in corso, un tag inizia a inviare il proprio pacchetto, il reader invia il segnale di MUTE che causa il congelamento di tutti gli altri tag che non stanno trasmettendo per un tempo equivalente alla lunghezza di un pacchetto. Questo accorgimento elimina del tutto la possibilità di collisione, mandando ogni nuova trasmissione certamente a buon fine.

TAG 1 TAG 2 TAG 3

Lettura corretta Tag muto perτ sec

Figura 1.30 Esempio di un’evoluzione temporale di una lettura con il protocollo Aloha Pure Fast

Ancora una volta le prestazioni del sistema non possono essere indagate se non mediante una simulazione del processo. Il programma impiegato è una semplice evoluzione di quello utilizzato nel caso del Free running: si rende necessaria l’aggiunta di un terzo stato per la macchina che simula il comportamento del singolo transponder e di un’istruzione supplementare nel reader per il segnale MUTE. Facendo riferimento alla macchina a stati del reader utilizzata nel caso Free running, quando il reader, nello stato di WAIT, osserva

l’inizio di una nuova trasmissione, cioè il passaggio della variabile activity dal valore nullo a uno, una direttiva manda nello stato MUTE tutti i tag ad eccezione di quello ha appena iniziato la nuova trasmissione, il quale si trova nello stato ACTIVE. I tag che sono entrati nello stato MUTE attendono un tempo τ, pari alla lunghezza di un pacchetto, prima di ritornare allo stato SILENT. Allo stesso modo degli altri protocolli visti finora, nello stato SILENT il tag decide di entrare nello stato ACTIVE a seconda del risultato dell’estrazione di un numero intero nell’intervallo tra 1 e LMτ, con M che rappresenta il numero di tag coinvolti nella lettura blocked access.

SILENT ACTIVE MUTE Nuovo messaggio pronto Nessun nuovo messaggio pronto

Tag i-esimo:

Attesa del tempoτ Attesa terminata

Inizio della lettura di un altro tag

Attesa terminata

Attesa del tempoτ

Figura 1.31 Diagramma di flusso della macchina a stati che simula il comportamento del transponder nel caso di Aoha puro in modalità Fast.

Ancora una volta, prima di passare all’analisi dei risultati è necessario valutare il parametro L che rende minimo il tempo medio per la lettura degli M tag. Dal grafico di Figura 1.32 appare una buona scelta il valore di 0,1. Il fatto che convenga sovrastimare il numero di tag presenti nel fissare l’estremo superiore ad inizio lettura, come già osservato dei precedenti protocolli dell’Aloha Pure, è ancora una volta confermata da questo

0.0

0.1

0.2

0.3

0.4

50

60

70

80

90

100

Average ti

m

e

(sl

o

t)

L

Figura 1.32 Tempo medio per la lettura di tutti i transponder al variare del parametro L, nel caso in cui i transponder siano in numero di 30. Il numero di simulazioni per ottenere ciascun dato è 200.

10

50

100

20

100

1000

Av

erage time (slot)

Tag number

λ

=1/(3

τ

)

λ

=1/(8

τ

)

Figura 1.33 Tempo medio per la lettura scegliendo diversi valori per il valore λ, frequenza media di ripetizione del messaggio del transponder. Poiché λ=1/(LMτ) e in questo caso il valore di L ottimale è pari a

10 20 30 40 50 60 70 80 90 100

0

40

80

120

160

200

240

Time (slot)

Tag number

average time

t

₉₉

Figura 1.34 Tempo medio,deviazione standard e tempo per la lettura di tutti i tag con una probabilità del

99% per un numero di tag nell’intervallo da 10 a 100.Il numero di simulazioni per ogni dato acquisito è 200.

0

100

200

300

400

500

0

200

400

600

800

1000

1200

1400

1600

Time (slot)

Tag number

average time t₉₉

Figura 1.35 Tempo medio,deviazione standard e tempo per la lettura di tutti i tag con una probabilità del

1.2.4 – Aloha Pure: Fast switch-off

Se al funzionamento nella modalità Fast viene aggiunto anche il segnale di ACK si ottiene la modalità Fast switch-off. Alla fine di una trasmissione effettuata da un singolo transponder, se il messaggio è stato ricevuto in modo corretto dal reader, un segnale di ACK prevede a disattivare il tag che ha apena trasmesso. Come sarà verificato in seguito, una conclusione abbastanza scontata è che, a fronte di un notevole complessità di comunicazione, il sistema presenta prestazioni notevoli in termini di velocità di acquisizione dei codici.

TAG 1 TAG 2 TAG 3

Lettura corretta Tag muto per

τ

sec

Figura 1.36 Esempio di un’evoluzione temporale di una lettura con il protocollo Aloha puro in modalità Fast switch off.

Per la simulazione del processo, a partire dal programma scritto per l’Aloha Fast, è sufficiente aggiungere uno stato alla macchina a stati del transponder: lo stato di SLEEP in cui il tag va a posizionarsi dopo aver trasmesso il proprio messaggio. Il passaggio dallo stato ACTIVE a SLEEP avviene a fine trasmissione se il reader ha ricevuto correttamente il messaggio, eventualità che può non verificarsi solo per colpa di errori in trasmissione e non per colpa di collisioni, dato che è stato previsto un segnale MUTE per congelare tutti gli altri tag durante la trasmissione. Nella simulazione si è assunta come ipotesi che il

messaggio venga sempre letto correttamente perciò il passaggio da ACTIVE a MUTE diviene automatico. SILENT ACTIVE MUTE Nuovo messaggio pronto Nessun nuovo messaggio pronto

Tag i-esimo:

Attesa del tempoτ Attesa terminata

Inizio della lettura di un altro tag

Attesa del tempoτ

SLEEP Messaggio letto

correttamente Messaggio non letto

correttamente

Figura 1.37 Diagramma di flusso della macchina a stati che simula il comportamento del transponder nel caso di Aloha puro inmodalità Fast switch-off

0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.10

80

82

84

86

88

90

92

94

96

98

100

Av

e

ra

g

e

tim

e

(

slo

t)

L

10

30

100

10

50

100

1000

Time (slot)

Tag number

λ

=1/(1.5

τ

)

λ

=1/(4

τ

)

Figura 1.39 Tempo medio per la lettura scegliendo diversi valori per il valore λ, frequenza media di ripetizione del messaggio del transponder. Poiché λ=1/(LMτ) e in questo caso il valore di L ottimale è pari a

0.05, scegliere λ=1/(1.5τ) significa fissare la frequenza ottimale di ripetizione per 30 tag, λ=1/(4τ) per 80.

50

100

150

200

250

300

0

100

200

300

400

500

600

Time (slot

)

Tag number

average time

t

₉₉

Figura 1.40 Tempo medio,deviazione standard e tempo per la lettura di tutti i transponder con una

probabilità del 99% per un numero di tag nell’intervallo da 10 a 300.Il numero di simulazioni per ogni dato

1.2.5 – Aloha Pure: confronti

Dall’analisi dei protocolli presi singolarmente è già stata osservata la dipendenza pressoché lineare che presentano tempo medio e t99 rispetto all’aumentare del numero di tag, nel caso in cui si operi sempre nelle condizioni di ottimalità per la frequenza di ripetizione. I grafici di Figura 1.41 e 1.42 riportano, per tutti i quattro protocolli Aloha, tempo medio e tempo 99%. Sfruttando la caratteristica di linearità di tali tempi con l’aumentare del numero di tag, considerazioni immediate si ottengono dalla tabella di Figura 1.43, nella quale sono scritti i coefficienti con i quali scalano i diversi protocolli. Tenendo presente la notevole differenza che si ha, relativamente alla complessità nella comunicazione, a partire dal protocollo base Free running fino al più veloce Fast switch-off, viene messo a confronto il miglioramento introdotto dal segnale ACK con quello introdotto dal segnale MUTE: lo Switch-off riduce la velocità più di tre volte rispetto al Free running, mentre il Fast addirittura undici volte.

0

50

100

150

200

0

500

1000

1500

2000

2500

3000

Av

era

g

e

time

(slo

t)

Tag number

Free running Switch off Fast

Fast switch off

Figura 1.41 Confronto sul tempo medio per la lettura di tutti i tag tra i quattro protocolli dell’area Aloha Pure.

0

40

80 120 160 200 240 280

0

2000

4000

6000

8000

10000

Time 99% (slot)

Tag number

Free running Switch off Fast

Fast switch off

Figura 1.42 Confronto sul tempo per la lettura con una probabilità del 99% di tutti i tag presenti tra i quattro protocolli dell’area Aloha Pure.

Tempo medio Tempo 99%

Free running 25 40

Switch off 7 9

Fast 2 2.2

Fast switch off 1.7 1.8

Figura 1.43 Tabella che riporta il numero di slot da aggiungere per ogni incremento del numero di transponder

1.3 – Aloha Slotted

Nella trattazione dell’Aloha Pure si è avuto modo di considerare l’evoluzione del modello base Free running in varianti che possiedono caratteristiche di velocità migliori, a discapito della semplicità nella comunicazione tra transponder e reader, che porta come conseguenza il dover disporre di transponder con logica più complessa. Sono stati introdotti due possibili segnali di comunicazione dal reader al tag, il segnale di ACK e quello di MUTE, che utilizzati singolarmente o in coppia danno vita alle tre evoluzioni già analizzate nel dettaglio. Ora, sempre partendo dal modello Free running dell’Aloha Pure, verranno analizzati due protocolli che possono essere ottenuti con un tipo del tutto nuovo di comunicazione tra reader e tag.

Periodo casuale

Messaggio letto correttamente

Messaggi in collisione

Figura 1.44 Esempio di un’evoluzione temporale di una lettura con un protocollo Aloha slotted. Se è previsto anche il segnale di ACK, dopo una corretta lettura, il transponder che ha appena trasmesso entra in

uno stato inattivo.

Se per i protocolli dell’Aloha Pure si aveva una comunicazione asincrona, in quanto localizzata esclusivamente all’inizio o alla fine di una trasmissione del tag, l’Aloha Slotted ne prevede una sincrona, mediante una divisione del tempo in slot temporali della lunghezza di un pacchetto trasmesso dal tag. Il reader comunica ai tag l’inizio di una nuova 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; successivamente, prevedendo il segnale di ACK con lo stesso scopo che esso aveva nell’Aloha Pure, 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.

1.3.1 – Aloha Slotted: Free running

Le prestazioni del sistema sono valutate con una simulazione Monte Carlo del sistema. Tale simulazione segue lo stesso schema logico di quella utilizzata per l’Aloha Pure, con l’introduzione di un’unica modifica: la variabile che rappresenta il tempo fa corrispondere, ad ogni suo incremento, un nuovo slot. Gli stati delle macchine per il reader e i tag rimangono i medesimi, con la semplificazione che il tempo di attesa corrispondente ad un pacchetto è rappresentato non più da un tempo τ, bensì da un’unità temporale.

Tag i-esimo:

ACTIVE SILENT Condizione per la ritrasmisione verificata Condizione per la ritrasmisione non verificata

Figura 1.45 Diagramma di flusso del transponder utilizzato per il protocollo di lettura Aloha Slotted free running.

Prima di valutare la funzione di distribuzione, tempo medio e tempo per la lettura con una probabilità del 99% occorre, come è stato fatto anche nei protocolli dell’Aloha Pure, valutare qual è l’estremo superiore del numero casuale estratto per la ritrasmissione che massimizza la velocità del protocollo. Nell’Aloha Pure il numero estratto, ad ogni incremento della variabile temporale di base, era un numero intero nell’intervallo compreso tra 1 e LM, dove L è un parametro ed M è il numero di transponder. Il tag passa allo stato di trasmissione solo se tale numero vale 1, in modo da rendere il passaggio di stato una variabile di Poisson di media 1/( LM). Nell’Aloha Slotted, per analogia con l’Aloha Pure, poiché la variabile temporale di base è della lunghezza di uno slot, il numero intero estratto causa il passaggio di stato se vale uno sull’ insieme di numeri da 1 a LM. Dalla Figura 1.46 si osserva che la scelta del parametro L che massimizza la velocità del protocollo è un valore nell’intervallo tra 2 e 3. Le osservazioni relative a L sono le stesse di quelle fatte nell’Aloha Pure. È noto che a priori sconosciuto è il numero di tag dei quali si procede a fare una lettura completa, perciò fissare sul tag un valore di L ottimale non basta a garantire che la media della variabile di Poisson estratta sia quella ottimale per il processo. E’ ragionevole pensare che l’estremo LM venga fissato all’inizio di una lettura in Blocked access. Dalla Figura 4 deriva immediatamente una semplice osservazione: poiché per fissare l’estremo superiore, scelto un L pari a 2,5, non resta che scegliere il valore di M, è conveniente sovrastimare, piuttosto che sottostimare, il numero di tag che potrebbero partecipare alla lettura. Tale scelta è giustificabile con un esempio numerico tratto direttamente dalla Figura 1.47: per un numero di tag presenti pari a 30 vi è una piccola differenza sul tempo medio di lettura, all’incirca del 30%, tra stimare per M il suo valore reale o il valore di 100; al contrario, a parti inverse, con un numero di tag pari a 100 la differenza sarebbe del 400%.

0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0

0

2000

4000

6000

8000

Time (slot)

L

M=30

100

300

Figura 1.46 Tempo medio per la lettura di tutti i transponder al variare del parametro L, nel caso in cui i tag siano in numero di 30. Il numero di simulazioni per ottenere ciascun dato è 200.

20

100

200

100

1000

10000

100000

Time (slot)

Tag number

λ

=1/(60)

λ

=1/(120)

λ

=1/(200)

Figura 1.47 Tempo medio per la lettura scegliendo diversi valori per il valore λ, frequenza media di ripetizione del messaggio del tag. Poiché λ=1/(LM) e in questo caso il valore di L ottimale è pari a 2, scegliere λ=1/(60) significa fissare la frequenza ottimale di ripetizione per 30 tag, λ=1/(120) per 60 e

Fatte le dovute osservazioni sul parametro L e appurato che la scelta dell’estremo ottimale, essendo impossibile a priori, rimane una decisione critica della lettura, nei prossimi grafici saranno visualizzati i parametri di bontà del protocollo per il valore ottimale dell’estremo superiore. Il valore scelto per L è 2.5 ed M assume di volta in volta il valore corrispondente al numero di tag analizzato. Il grafico della densità di probabilità per 50 tag (Figura 1.48) denota ancora una volta una distribuzione non simmetrica e pertanto non di tipo gaussiano. La presenza di una coda piuttosto lunga si può notare anche dalla seguente funzione di distribuzione nella quale è significativo osservare che il tempo per passare dalla sicurezza di avere acquisito tutti i tag del 99% a quella del 99,9% è pari all’incirca al 25% di quello impiegato per arrivare al 99%.

0

200 400 600 800 1000 1200 1400

0

50

100

150

200

250

Occurrencies

Time (slot)

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

200

400

600

800

1000

5.0 20.0 40.0 50.0 60.0 80.0 95.0 99.0 99.9

D

istribuction function (%)

Time (slot)

Figura 1.49 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.

Tempo medio e t99 sono riportati nelle Figure 1.51 e 1.52, prima per l’analisi del dettaglio di un numero di 100 tag e successivamente fino a 1000. Questi due parametri risultano ancora una volta lineare all’aumentare del numero di tag e il coefficiente con cui scalano all’aumentare al numero di tag è rispettivamente 12,5 e 22,5.

0

20

40

60

80

100

0

500

1000

1500

2000

2500

Time (

slot)

Tag number

average time

t

₉₉

Figura 1.50 Tempo medio,deviazione standard e tempo per la lettura di tutti i transponder con una

probabilità del 99% per un numero di tag nell’intervallo da 10 a 100.Il numero di simulazioni per ogni dato

acquisito è 200.

0

200

400

600

800

1000

0

5

10

15

20

25

30

Tim

e

(

slo

t,1

0

3

)

Tag number

average time

t

₉₉

Figura 1.51 Tempo medio,deviazione standard e tempo per la lettura di tutti i tag con una probabilità del

99% per un numero di tag nell’intervallo da 10 a 1000.Il numero di simulazioni per ogni dato acquisito è

1.3.2 – Aloha Slotted: Switch-off

Come per l’Aloha Pure, anche per lo Slotted, quando sia prevista la possibilità di comunicare ad un transponder che la sua lettura è avvenuta correttamente, è possibile operare in due diferenti modalità: Free access e Blocked access. Innanzitutto si analizza il caso Free access con un procedimento analogo a quello utilizzato per l’Aloha Pure, successivamente sarà preso in esame il caso della lettura in Blocked access.

1.3.2.1 – Aloha Slotted switch-off: Free access

I due parametri che indicano la bontà dell’algoritmo sono i medesimi del caso Pure, il throughput e il tempo medio che trascorre tra quando un transponder trasmette per la prima volta e il momento in cui riceve il segnale di acknowledgement. Si può immaginare che il tag effettui l’estrazione che determina l’inizio della trasmissione, così come per l’Aloha Pure, in modo continuo, ma che tale tag inizi effettivamente a trasmettere solo nello slot seguente a quello in cui ha deciso di effettuare la trasmissione.

Periodo vulnerabile:

Tempo di attesa per una lettura corretta

Messaggio letto correttamente

Messaggi in collisione

τ

Figura 1.52 Esempio di un’evoluzione temporale di una lettura con un protocollo Aloha Slotted. Sono evidenziati il periodo vulnerabile lungo uno slot, in quanto un transponder che decide di trasmettere lo può fare solo all’inizio di un slot in cui è diviso l’asse temporale, e il tempo di attesa del tag prima di essere letto

Si mantiene l’ipotesi che il processo d’arrivo dei pacchetti nuovi e ritrasmessi segua una distribuzione di Poisson, in cui la variabile aleatoria che rappresenta il numero di trasmissioni che si hanno in un periodo di osservazione abbia media attesa λ. In base alla definizione di periodo vulnerabile che è stata data per l’Aloha Pure, si osserva facilmente dalla Figura 1.52 che il valore che esso assume nel caso dell’Aloha slotted è τ. La variabile aleatoria, che rappresenta il numero di trasmissioni in un periodo τ, avrà una media attesa di G. Carico e throughput medi seguono le definizioni (1.2) e (1.3) formulate per l’Aloha Pure. Sostituendo le nuove variabili nella probabilità di avere un certo numero di trasmissioni in un periodo di osservazione della (1.4) si ha:

k -G

(G) P [k trasmissioni in τ] = e

k! (1.15)

La probabilità che nessuna trasmissione interferisca con quella che si vuole vedere portata a termine correttamente, cioè la probabilità che nessuna trasmissione avvenga nel periodo vulnerabile, si ha dalla 1 per k pari a zero:

0

-G -G

(G)

P [0 trasmissioni in τ] = e = e

0! (1.16) Il throughput si ottiene dal prodotto tra la probabilità che nessuna trasmissione avvenga nel periodo vulnerabile, riportata nella 2, e il carico medio:

-G

0

1

2

3

4

5

6

7

8

0.00

0.05

0.10

0.15

0.20

0.25

0.30

0.35

0.40

S

G

Figura 1.53 Grafico teorico che riporta il throughput medio in funzione del carico medio

Il calcolo per il tempo medio d’attesa è lo stesso di quello effettuato per l’Aloha Pure, con la semplice osservazione che il numero medio di trasmissioni che hanno un insuccesso ora è:

G_{-1 = e -1}2G

S (1.18) Utilizzando lo stesso ragionamento impiegato nell’Aloha Pure, considerando che il tempo tra due successive trasmissioni è Lτ, ne consegue che:

G

tag ack ack

E[T ] = τ + t + (e -1)(τ + t + L τ) (1.19)

Scrivendo la (1.19) in multipli di τ:

G

tag ack ack