View
2
Download
0
Category
Preview:
Citation preview
EPC CLASS 1 UHF 대역Anti-collision 알고리즘 개발
삼성탈레스삼성탈레스
May 06, 2005May 06, 2005
김재현김재현
Wireless Information & Network Engineering Research Lab. Wireless Information & Network Engineering Research Lab. (WINNER Lab.)(WINNER Lab.)
School of Electrical and Computer Engineering School of Electrical and Computer Engineering
AJOU UniversityAJOU University
2Jae-Hyun Kim
목목 차차
RFID 시스템에서의 Anti-collision 알고리즘
EPC CLASS 1 Spec. 분석
제안한 EPC CLASS 1 Anti-collision 알고리즘
프로젝트수행계획
결론
3Jae-Hyun Kim
RFID RFID 시스템시스템 에서의에서의 AntiAnti--collision collision 알고리즘알고리즘
4Jae-Hyun Kim
RFID SystemRFID System
RFID (Radio Frequency IDentification) system이란?무선환경에서여러개의물리적기기(tags)를인식하기위한무선센서네트워크의한형태
RFID 시스템의활용분야물류/유통 (SCM, 재고관리)
교통 (교통요금, 전자화폐)
동물관리(가축관리)
병원환자관리
Hospital
Casino: i-coin
Cloth
Secret Document Pet, Cow ID, Credit card
5Jae-Hyun Kim
TagTag--collision Problem & Issuescollision Problem & Issues
Tag-collision Problem수동태그간의통신불가
리더는모든태그에게데이터전송요구
동시에리더의전송요구에두개이상의태그가응답하면충돌이발생
Tag-collision problem
Tag-collision problem을해결할수있는 Anti-collision Algorithm 필요One of key technologies
ID RequestID RequestCollision
6Jae-Hyun Kim
AntiAnti--collision Algorithm collision Algorithm -- ALOHAALOHA
Framed Slotted ALOHA Algorithm (FS-ALOHA)ISO 18000-6 TYPE AEPCglobal Class 1 G2Use the fixed frame sizeShow substantial increase of identification time when the number of tags is (even) more than the frame size
Need to vary the frame size according the number of tagsVogt
Proposed the algorithm to estimate the number of tags using the distanceProposed how to allocate the optimal frame size using simulationDid not consider the inactivation state in which the tags do not respond to next reader’s ID transfer request temporarily
StandardsRefer to the basic concept of Framed Slotted ALOHA algorithmNo algorithm to estimate the number of tagsNo method how to vary the frame size in detail
7Jae-Hyun Kim
AntiAnti--collision Algorithm collision Algorithm --ALOHAALOHA
Operation of Framed Slotted ALOHA
0101TAG 40011TAG 31010TAG 21011TAG 1
사용된태그의 ID
TAG4(0101)
TAG3(0011)
TAG2(1010)
TAG1(1011)
STATE
2nd REQSlot4Slot3Slot2Slot11st REQREADER
Frame Size = 4
IDLE1011 COLL 0101
0011
1010
1011
0101
0011
1010
8Jae-Hyun Kim
AntiAnti--collision Algorithm collision Algorithm -- BinaryBinary
Binary Tree Algorithm ISO 18000-6 TYPE B
EPC CLASS 1 G2
CRP (Collision Resolution Protocol)
Use internal counter and random number generator to identify tags
9Jae-Hyun Kim
AntiAnti--collision Algorithm collision Algorithm -- BinaryBinary
Bit-by-bit Binary Tree Search AlgorithmEPC CLASS 0 (UHF)
태그는리더의전송요구에고유번호중한비트전송
태그로부터수신된비트정보가충돌이면알고리즘에의해하나의그룹 (e.g. 비트정보가 0인그룹)을선택
REPLY
TAG
X(0)
READER
REPLY
TAG READERTAGREADERTAGREADERREADER
TAG3(100)
TAG2(011)
TAG1(001)
STATE
X(0)REPLYCMDREPLYX(0)CMD
0
0
X
0
1
1
0
X 001 X
100태그 3
011태그 2
001태그 1
사용된태그의 ID
1 1
10Jae-Hyun Kim
AntiAnti--collision algorithms in Standardscollision algorithms in Standards
User
programmable
User
Programmable
User
Programmable
Read-only
태그메모리
64
64
23, 24, 34 and 36
(EPC)
23, 24, 34 and 36
(EPC)
Serial Number
(bits)
Avg. : 100 tags/sBinary Tree
ISO 18000-6
TYPE B
(UHF)
Avg. : 100 tags/sFramed Slotted ALOHA
ISO 18000-6
TYPE A
(UHF)
Not specifiedBinary Tree – Bin Slot /
Binary Tree and Framed Slotted ALOHA (G2)
EPC
CLASS1
(UHF)
Avg. : 200 tags/s
Max : 800 tags/sBit-by-bit Binary Tree
EPC
CLASS0
(UHF)
태그 인식개수충돌방지알고리즘
11Jae-Hyun Kim
Reader to tag communication in StandardsReader to tag communication in Standards
40025 / 25 or 12540 / 8 or 40FM0 /
Manchester ASK860-930
ISO 18000-6
TYPE B
(UHF)
30025 / 20 or 4040 / 33FM0 /
Pulse Interval ASK860-930
ISO 18000-6
TYPE A
(UHF)
647.13 / 14.25140.35 / 70.18 Pulse Interval AM /
AM Pulse width mod.
902-928
(908.5-914)
EPC
CLASS1
(UHF)
80025 or 12.5 /
25 or 12.5
40 or 80 /
40 or 80
FM0 /
AM Pulse width mod.902-928
EPC
CLASS0
(UHF)
태그리셋시간
(us)
비트전송시간
(상/하향)
(us)
전송속도 (상/하향)
(kbps)
에어인터페이스
(상/하향)동작주파수
(Mhz)
12Jae-Hyun Kim
EPC CLASS 1 Spec. EPC CLASS 1 Spec. 분석분석
13Jae-Hyun Kim
OverviewReader talks first (Passive RFID system)
Half-duplex manner
Class 1 RFID Tags only use backscatter modulation.
Class 1 Tag의 ITM (Identifier Tag Memory) 구조
RF communication range: >3m, <10m, worst>2m
16 bit 64 or 96 or 256 bit 8 bit
860 MHz 860 MHz –– 960 MHz Class 1960 MHz Class 1
14Jae-Hyun Kim
ReaderReader--toto--Tag Communication SignalsTag Communication Signals
Parameter definition and valuesNorth American
15Jae-Hyun Kim
ReaderReader--toto--Tag Communication SignalsTag Communication Signals
Parameter definition and valuesEuropean
16Jae-Hyun Kim
ReaderReader--toto--Tag Communication SignalsTag Communication Signals
Reader-to-Tag Command Signal Phases5개의단계로구성
First Phase: Transaction Gap (1.25*T0), T0 = 14.25us(North American)
Second Phase: minimum 64 usec CW period
[PREAMBLE] = First Phase + Second Phase
Third Phase: Data modulation window
Forth Phase: Tag setup period (8*T0)
Fifth Phase: low modulation phase (태그응답단계)
Reader-to-Tag Command Signal Phases 5단계
17Jae-Hyun Kim
ReaderReader--toto--Tag Communication SignalsTag Communication Signals
Data modulation: Pulse Width Modulation (PWM)Binary “0”: 1/8* T0
Binary “1”: 3/8* T0
Reader-to-Tag Signal Modulation DepthASK with 30%~100% modulation depth
18Jae-Hyun Kim
Reader-to-Tag Data EncodingBinary “0”
Binary “1”
Coast Interval리더로부터받은 On-tag computation power가유지되는시간
태그의 Power-on 시간이 Tcoast이므로리더가 Coast Interval 이내에다음 transaction을위한명령어를전송해야함
ReaderReader--toto--Tag Communication SignalsTag Communication Signals
19Jae-Hyun Kim
TagTag--toto--Reader Communication SignalsReader Communication Signals
Parameter definition and valuesNorth American
European
20Jae-Hyun Kim
TagTag--toto--Reader Communication SignalsReader Communication Signals
ScrollID reply delay
PingID reply Delay
ScrollID reply duration
21Jae-Hyun Kim
TagTag--toto--Reader Communication SignalsReader Communication Signals
Tag-to-Reader bit cell encoding
Tag-to-Reader bit cell variation
7.13 us
22Jae-Hyun Kim
ReaderReader--toto--Tag Logical CommunicationTag Logical Communication
Reader-to-Tag Command 형식 (8 fields + 5 parity bits)
Reader-to-Tag Command Field Description[PREAMBLE]: Transaction Gap + Period CW transmission (minimum 64 usec)[CLKSYNC]: 20 binary zeros for on-tag clock synchronization[SOF]: Start of frame (bit 1 전송)[CMD]: Required commands, Identifier programming commands[PTR]: 태그인식에서포인터위치 (8 bits)[LEN]: [VALUE] field에서보내지는데이터길이 (8 bits)[VALUE]: CMD에의존하는데이터 (Variable)[EOF]: End of frame indicator (bit 1 전송)Parity bits [P1] [P2] [P3] [P4] [P5]
[P1]: Odd parity of the [CMD] field[P2]: Odd parity of the [PTR] field[P3]: Odd parity of the [LEN] field[P4]: Odd parity of the [VALUE] field[P5]: Odd parity of all of the parity fields
PREAMBLE(NA)
CLKSYNC(20)
SOF(1)
CMD(8)
P1(1)
PTR(8*)
P2(1)
LEN(8*)
P3(1)
VALUE(variable)
P4(1)
P5(1)
EOF(1)
23Jae-Hyun Kim
ReaderReader--toto--Tag Logical CommunicationTag Logical Communication
Reader-to-Tag Command 종류Required commands (ScrollAllID, ScrolID, PingID, Quiet, Talk, Kill)
Identifier programming commands (ProgramID, VerifyID, LockID, EraseID)
Tag-to-Reader Reply CommunicationScrollAllID, ScrollID, PingID, VerifyID에만 Reply (나머지는 status 변경)
24Jae-Hyun Kim
ReaderReader--toto--Tag Required Command DescriptionsTag Required Command Descriptions
ScrollAllIDDownlink: [CMD]=[0011 0100]
Uplink: [PREAMBLE, 8 bits][CRC, 16 bits][Tag ID, 64, 96 or 256 bits]
모든태그들이자신의모든 ID 전송
ScrollIDDownlink: [CMD]=[0000 0001]
Uplink: [PREAMBLE, 8 bits][CRC, 16 bits][Tag ID, 64, 96 or 256 bits]
[PTR]위치에서시작하는 [LEN]의길이에해당하는 [VALUE] field의값과일치하는태그들만응답
25Jae-Hyun Kim
ReaderReader--toto--Tag Required Command DescriptionsTag Required Command Descriptions
PingIDDownlink: [CMD]=[0000 1000]Uplink: [8 bits ID][PTR]위치에서시작하는 [LEN]의길이에해당하는 [VALUE] field의값과일치하는태그들만 [VALUE]값이후의최상위 8 bit 전송태그는 8 bit 전송, 최상위 3bit를이용하여 8개의 bin slot에응답
QuietDownlink: [CMD]=[0000 0010]Uplink: No replyQuiet 명령보낸후, 7개의 binary “0”전송[PTR]위치에서시작하는 [LEN]의길이에해당하는 [VALUE] field의값과일치하는태그만명령수행
명령수행한 tag는 inactive 상태로천이Talk 명령을받을때까지, power를잃을때까지현재의상태를유지
26Jae-Hyun Kim
ReaderReader--toto--Tag Required Command DescriptionsTag Required Command Descriptions
TalkDownlink: [CMD]=[0001 0000]
Uplink: No reply
Talk 명령보낸후, 7개의 binary “0”전송(tag의명령수행시간)
[PTR]위치에서시작하는 [LEN]의길이에해당하는 [VALUE] field의값과일치하는태그만명령수행
명령수행한 tag는 active 상태로천이
KillDownlink: [CMD]=[0000 0100]
Uplink: No reply
[VALUE]=complete tag ID, CRC, 8-bit Password
Tag를영구적으로 inactive 상태로만들때사용
27Jae-Hyun Kim
ReaderReader--toto--Tag Identifier Programming Tag Identifier Programming Command DescriptionsCommand Descriptions
ProgramIDDownlink: [CMD]=[0011 0001]
Uplink: No reply
[PTR]위치에서 [LEN] 길이에해당하는 [VALUE] 데이터를저장
데이터를 16 bit 단위로저장([LEN] has decimal value 16)
[PTR] (0, 16, 32, 48, 64, 80, 96)의 decimal value로표현
최소 30 msec의프로그래밍시간을유지하기위해리더는 [EOF] 후 binary 0을지속적으로전송
리더는프로그래밍구간의끝을알리는 binary 1을태그로부터받음으로써프로그래밍동작을종료
마지막으로리더는 7개의 binary 0을전송
Locked tag는이명령에반응하지않음
VerifyIDDownlink: [CMD]=[0011 1000]
Uplink: [PREAMBL][CRC][TAGID][PASSWRD]
VerifyID명령을받은태그는자신의모든 ITM을전송
Locked 태그는 VerifyID command 무시
28Jae-Hyun Kim
ReaderReader--toto--Tag Identifier Programming Tag Identifier Programming Command DescriptionsCommand Descriptions
LockIDDownlink: [CMD]=[0011 0001]
Uplink: No reply
LockID를받은태그는자신의 ITM을변경할수없음(메모리변경방지)
[PTR]는 Password의MSB를가리킴
[LEN]는 16
[VALUE]의마지막 8 bits=0xA5
EraseIDDownlink: [CMD]=[0011 0010]
Uplink: No reply
태그의모든메모리 (Tag ID, CRC, Password) 상태초기화 “0”
Erase 시간최소 30 msec동안유지하기위해리더는 [EOF] 후 binary 0을지속적으로전송
리더는프로그래밍구간의끝을알리는 binary 1을태그로부터받음으로써 Erase 동작을종료
마지막으로, 리더는 7개의 binary 0을전송
Locked tag는이명령에반응하지않음
29Jae-Hyun Kim
State Diagram of a tagState Diagram of a tag
Power Off Mode
ActiveMode
QuietMode
DeactiveMode
Quiet
Talk
Kill
PingID ScrollAllID ScrollID
PingID ScrollAllID ScrollID
RF disconnectedRF disconnected
30Jae-Hyun Kim
Tag Identification ProcedureTag Identification Procedure
Basic procedure
STATUS
REQ.
TAG 1
VALUE
TAG 2
TAG 3
LENGTHPOINTER Bin 7
(111)
Bin 6
(110)
Bin 5
(101)
Bin 4
(100)
Bin 3
(011)
Bin2
(010)
Bin 1
(001)
Bin 0
(000)
COMMAND
TAG RESPONSEREADER
PingID0000 00000000 0100
1010
(1010001110101010)
(1010010101001010)
(1010010010011010)
00111010
01010100
0100100101001101
10100101
(1010001110101010)
(1010010101001010)
(1010010010011010)
IDLE IDLE SUCC IDLE IDLE SUCC IDLE IDLE
PingID0000 00000000 11101010010
IDLE SUCC COLL IDLE IDLE IDLE IDLE IDLE
(1010001110101010)
(1010010101001010)
(1010010010011010)
TAG 1 sends ITM ( Full ID )(1010001110101010)
(1010010101001010)
(1010010010011010)
ScrollID0000 00000000 01111010001
(1010001110101010)
(1010010101001010)
(1010010010011010)
31Jae-Hyun Kim
제안한제안한 EPC CLASS 1 AntiEPC CLASS 1 Anti--collision collision 알고리즘알고리즘
32Jae-Hyun Kim
EPC CLASS 1 UHF AntiEPC CLASS 1 UHF Anti--collision collision 알고리즘알고리즘
EPC CLASS 1 UHF 알고리즘의태그인식과정Ping ID 명령을사용하여태그인식
33Jae-Hyun Kim
제안한제안한 AntiAnti--collision collision 알고리즘알고리즘 11
Idea 1 : 리더의메모리를사용하여 Bin slot 정보를 저장
불필요한 Ping ID 명령의반복을줄임
34Jae-Hyun Kim
제안한제안한 AntiAnti--collision collision 알고리즘알고리즘 22
Idea 2 : Idea 1 + ScrollAllID명령사용사용된 tag가순차적일경우 Ping ID 명령의반복횟수가현저히감소
35Jae-Hyun Kim
성능성능 분석분석 ((기존기존 EPC CLASS 1 UHF EPC CLASS 1 UHF 알고리즘알고리즘))
Ping ID 명령전송반복횟수 (Itotal)
Tag 인식시간
17
2 0 0
1 1 11
k k k
L L Lm r r r
total kL k n
r n r n L r nI m
r r n r n r nr
−∞
= = =
⎛ ⎞− − − − −⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟= + − − ⋅⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟− − −⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠
∑ ∑ ∑
1k
m
r>단,
_ ( )totalreader
reader
RL C I mt
DR
+=
_ _totaltag
tag
TL P I TL S mt
DR
× + ×=
( )( )delay total reader tagt I m DE DE= + +
total reader tag delayt t t t= + +
Bin Slot의개수r
Tag의전송시간ttag
전송 delaytdelay
Reader의전송시간treader
총 tag 인식시간ttotal
Tag의 delayDetag
Reader의 delayDereader
Tag의 Data rateDrtag
Tag의 ScrollID 명령응답 packet 크기TL_STag의 Ping ID 명령응답 packet 크기TL_PReader의 Data rateDrreader
Reader의명령 packet 크기Drreader
사용된태그의개수m
DescriptionsParameters
36Jae-Hyun Kim
성능성능 분석분석 ((제안한제안한 AntiAnti--collision collision 알고리즘알고리즘))
Ping ID 명령전송반복횟수 (Itotal)
Tag 인식시간기존알고리즘의 tag 인식시간계산수식에위에서계산한 Itotal값대입
ScrollAllID명령을사용하는경우m 대신m+1 대입
1 11
0 10 1
1 1 11
k k
m m
r rktotal k k
k k
r m rI I I r
r r rr
− − −∞ ∞
−= =
⎛ ⎞− −⎛ ⎞ ⎛ ⎞⎜ ⎟= = + × − − ⋅⎜ ⎟ ⎜ ⎟⎜ ⎟⎝ ⎠ ⎝ ⎠⎝ ⎠
∑ ∑
11
k
m
r − >단, , I0 = 1(리더의최초 Ping ID 명령전송횟수)
37Jae-Hyun Kim
리더의 Ping ID 명령의반복횟수 (랜덤한태그 ID 사용)
성능성능 분석분석 결과결과
20 40 60 80 100 120 140 160 180 2000
100
200
300
400
500
600 EPC CLASS 1( )기존의 수기적분석 EPC CLASS 1( )기존의 시기기이기 ( )제안한알고리즘 수기적분석 ( )제안한알고리즘 시기기이기 using ScrollAllID( )제안한알고리즘 수기적분석 using ScrollAllID( )제안한알고리즘 시기기이기
제안한알고리즘기존알고리즘
85회515회
PingID 명령반복회수 (Random ID)
(사용된태그 = 200 개)
38Jae-Hyun Kim
성능성능 분석분석 결과결과
리더의태그인식시간 (랜덤한태그 ID 사용)
20 40 60 80 100 120 140 160 180 2000
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2 EPC CLASS 1( )기존의 수기적분석 EPC CLASS 1( )기존의 시기기이기 ( )제안한알고리즘 수기적분석 ( )제안한알고리즘 시기기이기 using ScrollAllID( )제안한알고리즘 수기적분석 using ScrollAllID( )제안한알고리즘 시기기이기
제안한알고리즘기존알고리즘
초당 252개초당 117개
태그인식시간 ( per sec )
39Jae-Hyun Kim
성능성능 분석분석 결과결과 ((시뮬레이션시뮬레이션))
리더의 Ping ID 명령의반복횟수 (순차적인태그 ID 사용)
20 40 60 80 100 120 140 160 180 2000
500
1000
1500
2000
2500 EPC CLASS 1기존의 제안한알고리즘 using ScrollAllID제안한알고리즘
20 40 60 80 100 120 140 160 180 2005
10
15
20
25
30
35
40
45
50
제안한알고리즘
(using ScrollAllID)기존알고리즘
37 회2350 회
PingID 명령반복회수 (Sequential ID)(사용된태그 = 200 개)
40Jae-Hyun Kim
성능성능 분석분석 결과결과 ((시뮬레이션시뮬레이션))
리더의태그인식시간 (순차적인태그 ID 사용)
20 40 60 80 100 120 140 160 180 2000
1
2
3
4
5
6 EPC CLASS 1기존의 제안한알고리즘 using ScrollAllID제안한알고리즘
100 120 140 160 180 2000.35
0.4
0.45
0.5
0.55
0.6
0.65
0.7
0.75
-기존알고리즘은순차적인태그 ID 사용시 PingID 명령반복회수증가로성능격감
ScrollAllID 사용ScrollAllID 사용 안함
1.16배성능향상1.13배성능향상
태그인식시간 (Sequential ID)(사용된태그 = 200)
Recommended