Transcript PPT

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
same 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
and i≠j,
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 reader’s channel assignment has no collision to its
neighbor readers, then goto S2.
S4 If reader’s channel assignment has collision to its
neighbors, select a new {1, 2, • • • , T} such that the
number of collision pairs between the reader and its
neighbors is the minimum.
S5 Repeat steps S2 to S4 until no more improvement can
be 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 reader’s channel assignment has no collision to its
neighbor readers, then goto S2.
S4 If reader’s channel assignment has collision to its
neighbors, random generate a new {1, 2, · · · , T}.
S5 If the number of collision pairs between the reader and
its 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
its neighbors increases by ∆, generate a random number u
from a uniform distribution in [0, 1]. Then,
 i*
i  
i


if u exp(  /  ( k )),
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
constant,
 (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
for allocation is determined automatically by
the 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
area of 100m×100m.
Readers at the end of an edge are neighbors.
The number of edges in the experimental
network 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
respectively.
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
done by the 5 algorithms (heuristics, SA-CT, SA-GG, SAKP, and Colorwave) separately.
For heuristics, SA-CT, SA-GG, SA-KP algorithms, the
number 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
readers are set randomly to fault with fault rate 0.05. This
step is repeated 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
simulation






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個讀取器隨機部署在100m×100m內
•讀取器故障率為0.05
•通道配置之方法為啟發式演算法
•紅色的方框代表讀取器為故障
RFID Reader Networks
42
VII What’s Next
John Sum, Kevin Ho
RFID Reader Networks
43
VII What’s Next
John Sum, Kevin Ho
RFID Reader Networks
44
VII What’s Next
John Sum, Kevin Ho
RFID Reader Networks
45
VII What’s Next
John Sum, Kevin Ho
RFID Reader Networks
46
VII What’s Next
Hai Liu, Miodrag Bolic, Amiya Nayak and Ivan Stojmenovi, Integration of RFID and
wireless 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 What’s Next

Cyber-digital Ecosystem: Systems merge.
 Telecom networks



Facebook



Connecting people
Each person is identified by an account name (or multiple account
names)
Internet



Connecting people
Each person is identified by a mobile phone number (or multiple
phone 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 What’s 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 What’s Next
John Sum, Kevin Ho
RFID Reader Networks
50