Transcript slides

PS
WASN
2009
A Counter-Based
RFID Anti-Collision Protocol
Using Parallel Splitting
Ming-Kuei Yeh and Jehn-Ruey Jiang
Department of Computer Science and Information Engineering
National Central University
Adaptive Computing and Networking Laboratory
PS
WASN
2009
Outline
•
•
•
•
•
Introduction
Anti-collision protocols
Proposed protocol
Evaluation
Conclusion
Adaptive Computing and Networking Laboratory
2
PS
WASN
2009
Outline
•
•
•
•
•
Introduction
Anti-collision protocols
Proposed protocol
Evaluation
Conclusion
Adaptive Computing and Networking Laboratory
3
PS
Introduction
• RFID (Radio Frequency
IDentification) system
RFID system
WASN
2009
Reader
Tag (Transponder)
Application
Adaptive Computing and Networking Laboratory
4
PS
Introduction
Application
Adaptive Computing and Networking Laboratory
WASN
2009
5
PS
Introduction
WASN
2009
Interrogation zone
Tag 1
Tag 3
reader
Interrogation zone
Tag 2
Adaptive Computing and Networking Laboratory
6
PS
Introduction
WASN
2009
Tag-to-tag interference
tag
reader
Interrogation zone
Tag collision problem: collision occurs when multiple tags
respond to the same reader simultaneously
Adaptive Computing and Networking Laboratory
7
PS
WASN
2009
Outline
•
•
•
•
•
Introduction
Anti-collision protocols
Proposed protocol
Evaluation
Conclusion
Adaptive Computing and Networking Laboratory
8
PS
Anti-collision protocols
category
• Anti-collision protocols
WASN
2009
For solving the tag collision problem
Two classes
• ALOHA based
• Tree based
– deterministic tree-based
– probabilistic counter-based
Adaptive Computing and Networking Laboratory
9
PS
Anti-collision protocols
WASN
2009
ALOHA based
Tag10
Tag9
Tag8
Collision !
Tag7
Tag6
Tag5
Tag4
Collision !
Tag3
Tag2
Tag1
S1
S2
S3
S4
S5 S6
S7
S8
S9 S10 S11 S12 S13 S14 S15
An example of slotted ALOHA protocol
Adaptive Computing and Networking Laboratory
S: time slot
10
PS
Anti-collision protocols
0
0
0
0
WASN
2009
Tree based
1
1
1
1 0
0
1
1
Tag1 Tag2
Tag3 Tag4
Tag5
Tag6
ID:0010
An example of bit-by-bit tree protocol
Adaptive Computing and Networking Laboratory
11
PS
Anti-collision protocols
C= counter
C=0
WASN
2009
Counter based
C=0
C
C === 000
C
C =3
=1
=2
=4
C=0
C=0
=1
C =2
=3
C=0
C =1
=2
C=0
C=0
C =0
=1
Tag1
Tag1
An example of a counter-based protocol: ISO/IEC18000-6B
Adaptive Computing and Networking Laboratory
12
PS
Outline
•
•
•
•
•
Introduction
Anti-collision protocols
Proposed protocol
Simulation
Conclusion
Adaptive Computing and Networking Laboratory
WASN
2009
13
PS
Proposed protocol
• Parallel Splitting (PS) for
RFID Tag Anti-Collision
WASN
2009
Counter based anti-collision protocol
Using two schemes
• Parallel Splitting
• Adaptive Identification-Tree Height Adjustment
Adaptive Computing and Networking Laboratory
14
PS
Proposed protocol
WASN
2009
Parallel Splitting
C
= 00
C
C===0
C
0
C
CC=1
=1
=1
C
C =0
== 00
C
C ==00
C =0
C =1
C =1 C =2
C
= 2 their
=2
JustC
left-shift
counters one bit
and add one or zero
C =3 C =4
C =5 C =6
randomly to the
counters.
C =3
C =7
Tag1
C =0
C =1 C =2 C =3 C =4 C =5 C =6 C =7 C =8 C =9 C =10 C =11 C =12 C =13 C =14
C= counter
Adaptive Computing and Networking Laboratory
15
PS
Proposed protocol
• Why do we need to adjust the
identification-tree height?
Adaptive Identification-Tree Height Adjustment
WASN
2009
May not be so lucky to split the tags perfectly
(to be a full tree)
Adaptive Computing and Networking Laboratory
16
PS
Proposed protocol
Adaptive Identification-Tree Height Adjustment (cont’)
WASN
2009
• Analyzing the ratio of the numbers of
leaf nodes that including zero tag, one tag
and multiple tags
p(S): the probability that there are S tags residing at a leaf node
N: The number of tags in the interrogation zone
L: The number of leaf nodes; ;
Adaptive Computing and Networking Laboratory
17
PS
Proposed protocol
Adaptive Identification-Tree Height Adjustment (cont’)
Adaptive Computing and Networking Laboratory
WASN
2009
18
PS
Proposed protocol
Adaptive Identification-Tree Height Adjustment (cont’)
Adaptive Computing and Networking Laboratory
WASN
2009
19
PS
Proposed protocol
Adaptive Identification-Tree Height Adjustment (cont’)
Adaptive Computing and Networking Laboratory
WASN
2009
20
PS
Proposed protocol
Adaptive Identification-Tree Height Adjustment (cont’)
Adaptive Computing and Networking Laboratory
WASN
2009
21
PS
Proposed protocol
Adaptive Identification-Tree Height Adjustment (cont’)
WASN
2009
Let the expected numbers of leaf nodes containing
none, one and multiple tags be e(0), e(1) and e(m), respectively.
Adaptive Computing and Networking Laboratory
22
PS
Proposed protocol
Adaptive Identification-Tree Height Adjustment (cont’)
WASN
2009
It is reasonable to assume L>>1 and N>>1,
and to take L–1 as L, and N–1, N–2 as N. We have
Adaptive Computing and Networking Laboratory
23
PS
Proposed protocol
Adaptive Identification-Tree Height Adjustment (cont’)
WASN
2009
• Analyzing the ratio of the numbers of
leaf nodes that including zero tag, one tag
and multiple tags
• The result of analysis
Rule1
Rule2
L : The number of leaf nodes
N : The number of tags in the interrogation zone
Adaptive Computing and Networking Laboratory
24
PS
Proposed protocol
Adaptive Identification-Tree Height Adjustment (cont’)
• The Actions of Adjustment
WASN
2009
Rule 1: If N0 > 2*N1 and N1 > 3.4*Nm,
＝＞all unidentified tags right-shift their
counters one bit to divide L by 2.
Rule 2: If 2*N0 < N1 and 1.7*N1 < Nm
＝＞ all unidentified tags left-shift their counters
one bit to multiply L by 2, and subsequently
add one or zero randomly to the counters.
Adaptive Computing and Networking Laboratory
25
PS
Proposed protocol
Two Phases of PS Protocol
• In phase I
WASN
2009
All tags are split in parallel until the first tag is
identified successfully.
In phase
phase II
II
•• In
Tags are identified one by one according to
The normal identification procedure of ISO/IEC
18000-6B protocol.
The reader applies Rule1 or Rule2 for adjusting the
number of leaf nodes to approach the actual number
N of tags (N is unknown)
Adaptive Computing and Networking Laboratory
26
PS
WASN
2009
Outline
•
•
•
•
•
Introduction
Anti-collision protocols
Proposed protocol
Evaluation
Conclusion
Adaptive Computing and Networking Laboratory
27
PS
Evaluation
WASN
2009
• The simulations are programmed
in Java language
• Each simulation is performed 1,000 times
and then calculates the average value
Adaptive Computing and Networking Laboratory
28
PS
relation between the height of the identification tree
Evaluation -The
and the number of iterations needed
An iteration is defined as
a reader sends a command
and tags perform
corresponding actions
WASN
2009
N is the number of tags in the
interrogation zone
is the “perfect” height
of the identification-tree
The comparison of the number of iterations for 1,025~2,025 tags.
Adaptive Computing and Networking Laboratory
29
PS
WASN
2009
Evaluation-the number of iterations
ISo/IEC 18000-6B(simulation)
PS(simulation)
PS(best case of simulation)
PS(analysis-wothout tree-height adjustment)
The number of itreations
7000
6000
5000
4000
3000
2000
1000
2012
1912
1812
1712
1612
1512
1412
1312
1212
1112
1012
912
812
712
612
512
0
The number of tags
The comparison of the number of iterations between
ISO18000-6B and the PS protocol for 512~2,012 tags.
Adaptive Computing and Networking Laboratory
30
PS
Evaluation-System Efficiency
PS
QT
ISO/IEC 18000 6B
Frame Slotted ALOHA
WASN
2009
0.45
System efficiency
0.4
0.35
0.3
0.25
0.2
0.15
0.1
System efficiency is defined
as the ratio of the number N
of tags to the number S of
slots (iterations) required to
identify all the tags
0.05
0
The number of tags
The comparison of PS, query tree (QT), ISO/IEC 18000-6B, and frame
slotted ALOHA protocols in terms of system efficiency for 100~1,000 tags
Adaptive Computing and Networking Laboratory
31
PS
WASN
2009
Outline
•
•
•
•
•
Introduction
Anti-collision protocols
Proposed protocol
Evaluation
Conclusion
Adaptive Computing and Networking Laboratory
32
PS
Conclusion
• We have proposed a new
counter based anti-collision
protocol (PS) for RFID systems
• Two schemes are used in this protocol
WASN
2009
parallel splitting
adaptive identification-tree height adjustment
• PS has better performance than ISO-18000 6B
Adaptive Computing and Networking Laboratory
33
PS
WASN
2009
Thanks for Your Listening!
Adaptive Computing and Networking Laboratory
34