RFID Reader Networks: Channel allocation algorithms, performance evaluation and simulator John Sum, National Chung Hsing University OUTLINE RFID Reader Network Reader Collision Problem Algorithms

Non Progressive Progressive Hybrid Simulation Results Conclusions Simulator design John Sum, Kevin Ho RFID Reader Networks 2 I. RFID Reader Network

John Sum, Kevin Ho RFID Reader Networks 3 I. RFID Reader Network Reader Host Computer 802.11bgn Reader Tags

ETSI EN 302 208 (European regulation) 15 sub-bands (channels) in the ISM band, 10 channels are available and 5 guard bands Readers access the medium by Carrier Sense Multiple Access (CSMA) mechanism (Listen Before Talk). If the sub-band is free, the readers start to transmit into. Then, the sub-band is used for up to 4 s, after which it must be free for at least 100 ms. EPC global Class-1 Gen-2 UHF Protocol 50 different sub-bands. Readers randomly alternate (every 0.4 s) between bands, following the Frequency Hopping Spread Spectrum (FHSS)

Readers do not listen to the channel before accessing to it. The reader transmissions are restricted to operate in even-numbered sub-bands and tag backscatter in odd-numbered sub-bands. John Sum, Kevin Ho RFID Reader Networks 4 I. RFID Reader Network Readers are powered by batteries, with much powerful computational and memory capacities.

Tags (passive) are powered by the radio signal transmitted by the readers. Memory is small. Backscattered signal is weak. John Sum, Kevin Ho RFID Reader Networks 5 I. RFID Reader Network John Sum, Kevin Ho RFID Reader Networks 6 I. RFID Reader Network

John Sum, Kevin Ho RFID Reader Networks 7 I. RFID Reader Network Tag collision problem Single reader multiple tags

Multiple tags receive signal from the same reader. The backscattered signals interfere. As a result, reader could not read from anyone of them. This problem can be alleviated by TDMA like methods. One tag responses at a time, by something like tag address. John Sum, Kevin Ho RFID Reader Networks 8 I. RFID Reader Network Reader collision problem

Multiple readers single (or multiple) tags Neighbor readers send the same frequency signal to the air. At the same time, these two signals interfere each other. Tags are unable to backscatter signal. This problem can be alleviated by TDMA (CSMA) or FDMA (frequency hopping) like methods. Time slot allocation and channel allocation John Sum, Kevin Ho RFID Reader Networks

9 I. RFID Reader Network EPC Class 1 Gen 2 UHF Air Interface Protocol (2004) John Sum, Kevin Ho RFID Reader Networks 10 II. READER COLLISION PROBLEM Operation Environment

Any two readers will have collision if their distance apart d(i ,j) is within a range r and they are collecting data in the sam e time slot. 1 eij 0 if d (i , j ) r if d (i , j ) r . Readers are not able to select their frequency bands. The readers are deployed uniformly random within an area

of 100m 100m, and are not moveable. Each reader can only assigned with one channel (for i = 1 , 2, ,N ) in each cycle of interrogation. No mobile reader is allowed within the area of deployment. John Sum, Kevin Ho RFID Reader Networks 11 II. READER COLLISION PROBLEM Operation Mechanism

Channel allocation is done by the control computer. Once the solution has obtained, the control computer will send message informing the readers the channels being assigned. The readers will thus record their channels being assigned and wait for the synchronization signal from the control computer. Once the syn. signal has been received, each reader will then operate at the dedicated channel to read the tags data. Communication between the control computer and the readers are implemented by wireless LAN. John Sum, Kevin Ho RFID Reader Networks

12 II. READER COLLISION PROBLEM The collision matrix: For i, j = 1, 2, , N an d ij, 1if {eij 1}and { i j } c ij 0 otherwise.

The number of collision pairs (CP) in a reader network can be defined as follows: 1 N N CP cij . 2 i 1 j 1 John Sum, Kevin Ho RFID Reader Networks 13 III. ALGORITHMS (Non Progressive) The maximum number of channels available is predefined.

Non progressive algorithms Heuristics Simulated Annealing (CT, KIRK, GG) Distributed Color Selection John Sum, Kevin Ho RFID Reader Networks 14 III. ALGORITHMS (Non Progressive)

Heuristics S1 Generate random numbers in {1, 2, , T} for 1, 2, , N as their initial random channels allocation. S2 Random select a reader, say i. S3 If readers channel assignment has no collision to its nei ghbor readers, then goto S2. S4 If readers channel assignment has collision to its neigh bors, select a new {1, 2, , T} such that the number of c

ollision pairs between the reader and its neighbors is the mi nimum. S5 Repeat steps S2 to S4 until no more improvement can b e made. John Sum, Kevin Ho RFID Reader Networks 15 III. ALGORITHMS (Non Progressive) Simulated Annealing

S1 Generate random numbers in {1, 2, , T} for 1, 2, , N as their initial random channels allocation. k = 0. S2 Random select a reader, say i. Then, k = k + 1. S3 If readers channel assignment has no collision to its neig hbor readers, then goto S2. S4 If readers channel assignment has collision to its neighb ors, random generate a new {1, 2, , T}. S5 If the number of collision pairs between the reader and it s neighbors reduces. John Sum, Kevin Ho RFID Reader Networks

16 III. ALGORITHMS (Non Progressive) Simulated Annealing S6 If the number of collision pairs between the reader and it s neighbors increases by , generate a random number u fr om a uniform distribution in [0, 1]. Then, i* if u exp( / ( k )), i i if u exp( / ( k )).

S7 Repeat steps S2 to S6 for k MaxRun. John Sum, Kevin Ho RFID Reader Networks 17 III. ALGORITHMS (Non Progressive) a) Constant Temperature: For all k 0 and a << 1 is a small c onstant, (k ) a.

b) Geman-Geman Rule: For all k 0 and b is a constant, b (k ) . log(k 1) c) Kirkpatrick et al Rule: For all k 0 and 0 < < 1. i.e. (k) = (k 1). John Sum, Kevin Ho RFID Reader Networks 18 III. ALGORITHMS (Progressive)
The maximum number of channels required f or allocation is determined automatically by th e algorithms. Progressive algorithms Progressive Heuristics Progressive SA (CT, KIRK, GG) Colorwave John Sum, Kevin Ho RFID Reader Networks

19 III. ALGORITHMS (Progressive) John Sum, Kevin Ho RFID Reader Networks 20 IV. SIMULATION RESULTS John Sum, Kevin Ho RFID Reader Networks 21

IV. SIMULATION RESULTS 250 readers in random locations within an ar ea of 100m100m. Readers at the end of an edge are neighbors. The number of edges in the experimental net work is 3830. In average, each reader has 15.32 neighbors. The constants a, d, c, and in the simulated annealing algorithms are 0.01, 1, 2 and 0.99 r espectively.

John Sum, Kevin Ho RFID Reader Networks 22 IV. SIMULATION RESULTS (NP) Comparison

Average number of collision pairs Convergence properties Channel distributions (Entropies) Fault tolerance Labels RAND: Initial Random Allocation HEU: Heuristic Algorithm CT: Constant Temperature SA GG: Geman-Geman Rule KP: Kirkpatrick et al Rule. John Sum, Kevin Ho

RFID Reader Networks 23 IV. SIMULATION RESULTS (NP) John Sum, Kevin Ho RFID Reader Networks 24 IV. SIMULATION RESULTS (NP)

Convergence Collision Pairs VS Number of Steps John Sum, Kevin Ho RFID Reader Networks 25 IV. SIMULATION RESULTS (NP) Slots Distributions Algo. t Pt log(Pt) Random

2.7721 Heuristic 2.5249 SA CT 2.7605 SA GE 2.7633 SA KP 2.7622 John Sum, Kevin Ho

RFID Reader Networks 26 IV. SIMULATION RESULTS (P) John Sum, Kevin Ho RFID Reader Networks 27 IV. SIMULATION RESULTS (P) John Sum, Kevin Ho

RFID Reader Networks 28 IV. SIMULATION RESULTS (Hybrid) John Sum, Kevin Ho RFID Reader Networks 29 IV. SIMULATION RESULTS (Fault tolerance) Experimental setup

20 random reader networks are generated Channel allocation for each of these reader networks is don e by the 5 algorithms (heuristics, SA-CT, SA-GG, SA-KP, a nd Colorwave) separately. For heuristics, SA-CT, SA-GG, SA-KP algorithms, the num ber of available channels is fixed to 16. For Colorwave, the initial channel number is set to 16. Once the channel allocations have been finished, all reader s are set randomly to fault with fault rate 0.05. This step is r epeated 20 times. John Sum, Kevin Ho

RFID Reader Networks 30 IV. SIMULATION RESULTS John Sum, Kevin Ho RFID Reader Networks 31 IV. SIMULATION RESULTS Colorwave algorithm John Sum, Kevin Ho RFID Reader Networks

32 V. CONCLUSIONS Towards a framework for the RFID developer to investigate the performance of an RFID system Simulate the environment in which the RFID readers are not perfect. Algorithms for solving RCP are introduced, including

HEUR, SA-CT, SA-KIRK, SA-GEM, DCS P-HEUR, PSA-CT, PSA-KIRK, PSA-GEM, CW HYBRID John Sum, Kevin Ho RFID Reader Networks 33 V. CONCLUSIONS Computational Speed (for NP type):

Channel Distribution (for NP type): HEUR > DCS > SA SA > DCS > HEUR DCS is unable to solve the problem John Sum, Kevin Ho RFID Reader Networks 34 V. CONCLUSIONS

Channel Distribution (Progressive) Fault tolerance PSA > P.HEUR > CW Similar behaviors Overall (Comp. Speed + Distribution)

HYBRID > Progressive > Non-Progressive John Sum, Kevin Ho RFID Reader Networks 35 V. CONCLUSIONS Even slot distributions Demand on high bandwidth communication between readers and control computer can be reduced. John Sum, Kevin Ho RFID Reader Networks

36 VI. Simulator System Design RFID John Sum, Kevin Ho RFID Reader Networks 37 VI. Simulator System Design John Sum, Kevin Ho RFID Reader Networks

38 VI. Simulator System Design John Sum, Kevin Ho RFID Reader Networks 39 VI. Simulator System Design MATLAB M-file, MATLAB FIG-file User is able to set the following parameters for si mulation

Number of Readers Transmission Range Number of Channel Number of Steps Reader Fault Rate Channel Allocation Algorithm John Sum, Kevin Ho RFID Reader Networks 40

VI. Simulator System Design John Sum, Kevin Ho RFID Reader Networks 41 VI. Simulator System Design John Sum, Kevin Ho 250 100m100m 0.05 RFID Reader Networks

42 VII Whats Next John Sum, Kevin Ho RFID Reader Networks 43 VII Whats Next John Sum, Kevin Ho RFID Reader Networks 44

VII Whats Next John Sum, Kevin Ho RFID Reader Networks 45 VII Whats Next John Sum, Kevin Ho RFID Reader Networks 46 VII Whats Next Hai Liu, Miodrag Bolic, Amiya Nayak and Ivan Stojmenovi, Integration of RFID and wirel

ess sensor networks, Encyclopedia on Ad Hoc and Ubiquitous Computing, Dharma P. Agrawal, Bin Xie (eds.), World Scientific Press, Singapore, 2009. John Sum, Kevin Ho RFID Reader Networks 47 VII Whats Next Cyber-digital Ecosystem: Systems merge. Telecom networks Facebook

Connecting people Each person is identified by an account name (or multiple account na mes) Internet Connecting people Each person is identified by a mobile phone number (or multiple phon e numbers)

Connecting networks Each network is uniquely identified by a domain ID Computer network Connecting computing machines Each machine is uniquely identified by a unique local IP address John Sum, Kevin Ho RFID Reader Networks 48 VII Whats Next

Cyber-digital Ecosystem: Systems merge. Sensor networks RFID systems Connecting Moving compartments Each compartment is a LAN which is identified by an ID

Personal area networks Connecting physical stuffs Each stuff is uniquely identified by a tag ID Vehicle networks Connecting sensors for environmental information Each information is uniquely identified by a unique sensor ID Connecting body sensors, wireless headset

Each device is uniquely identified by a unique ID Finally John Sum, Kevin Ho RFID Reader Networks 49 VII Whats Next John Sum, Kevin Ho RFID Reader Networks 50