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)