工學 碩士學位 論文

RFID 시스템에서의 bit 충돌 상태 정보를 이용한 anti-collision 알고리즘

Anti-collision algorithm using information

of bit collision condition in the RFID system

亞洲大學校 大學院

電 子 工 學 科

崔 皓 丞

RFID 시스템에서의 bit 충돌 상태 정보를 이용한 anti-collision 알고리즘

Anti-collision algorithm using information of bit collision condition in the RFID

system

指 導 敎 授 金 宰 顯

이 論文을 工學 碩士學位 論文으로 提出함.

2006 年 2 月

亞洲大學校 大學院

電 子 工 學 科

崔 皓 丞

崔皓丞의 碩士學位 論文으로 認准함.

審 査 委 員 長 金 宰 顯 (印)

審 査 委 員 吳 成 根 (印)

審 査 委 員 李 採 羽 (印)

亞洲大學校 大學院

2006 年 2 月

감사의 글

2년의 석사과정 동안 많은 것을 배우고 졸업하게 되어 매우 기쁩니다.

물론 더 배울 것이 많다고 생각되어 많은 아쉬움이 남고 석사과정 동안 더

열심히 공부하지 못한 것에 대한 후회도 남습니다.

우선 저의 학문적인 능력뿐 아니라 세상을 바라보는 안목과 인성 등

전반적인 부분에서 발전할 수 있도록 도와주신 저의 지도교수님인 김재현

교수님께 진심으로 감사 드립니다. 그리고 저에게 좋은 말씀도 많이 해주시

고 저의 논문을 성의껏 심사해주신 오성근 교수님과 이채우 교수님께도 깊

은 감사를 드립니다.

또한 석사과정 동안 같이 공부하면서 저에게 큰 도움을 준 재룡이 형,

성민이 형, 현진에게도 감사의 말을 전하고 싶습니다. 그리고 저에게 연구실

생활을 하는 동안 많은 좋은 추억을 남겨주고 다방면에서 저에게 도움을 준

주아, 성진, 지수, 충희에게도 감사의 마음을 전합니다. 비록 같은 연구실은

아니지만 같이 일했었고 저에게 도움을 주었던 기범이 형, 희구 형, 수련이

누나에게도 감사 드리며, 마지막으로 지금의 제가 있을 수 있도록 저를 낳아

주시고 길러주신 부모님과 하나뿐인 사랑하는 여동생에게도 깊은 감사를 드

리며 이 논문을 바칩니다.

목 차

목 차.................................................................................................................................... i

그림 목차.............................................................................................................................. ii

표 목차 ................................................................................................................................ iii

약 어 표............................................................................................................................... iv

국문 요약.............................................................................................................................１

제１장 서론........................................................................................................................... 3

제２장 기존 충돌 방지 알고리즘 .......................................................................................... 5

２.１ 이진 탐색 알고리즘 .............................................................................................. 5

가. 기본 이진 탐색 알고리즘................................................................................... 5

나. 동적 이진 탐색 알고리즘................................................................................... 6

２.２ 슬롯단위 이진 트리 알고리즘............................................................................... 7

가. 기본 슬롯단위 이진 트리 알고리즘 ................................................................... 7

나. Modified 슬롯단위 이진 트리 알고리즘 .............................................................. 8

２.３ Bit-by-bit 이진 트리 알고리즘.......................................................................... 10

２.４ 기존의 EPC CLASS 1 UHF anti-collision 알고리즘.......................................... 11

제３장 제안한 anti-collision 알고리즘 .................................................................................. 14

３.１ Improved bit-by-bit 이진 트리 알고리즘.......................................................... 14

３.２ 제안한 EPC CLASS 1 UHF용 anti-collision 알고리즘........................................ 16

제４장 성능 분석................................................................................................................ 20

４.１ Improved bit-by-bit 이진 트리 알고리즘.......................................................... 20

가. 제안한 알고리즘의 반복횟수 분석................................................................... 20

나. 태그가 보낸 총 bit 수 ..................................................................................... 26

４.２ EPC CLASS 1 UHF용 anti-collision 알고리즘.................................................. 27

가. 기존의 EPC CLASS 1 UHF anti-collision 알고리즘.............................................. 27

나. 제안한 anti-collision 알고리즘 .......................................................................... 32

제５장 수학적 분석 및 시뮬레이션 결과 ............................................................................ 34

５.１ Improved bit-by-bit 이진 트리 알고리즘.......................................................... 34

５.２ 제안한 EPC CLASS 1 UHF용 anti-collision 알고리즘........................................ 37

제６장 결론......................................................................................................................... 42

참고 문헌............................................................................................................................ 44

Abstract................................................................................................................................ 46

i

그림 목차 그림 1. 슬롯단위 이진 트리 알고리즘의 예 ............................................................ 8

그림 2. 슬롯단위 이진 트리 알고리즘의 예 ............................................................ 9

그림 3. Bit-by-bit 이진 트리 알고리즘의 예.......................................................... 11

그림 4. EPC CLASS 1 UHF anti-collision 알고리즘의 태그인식 과정 ........................ 13

그림 5. Improved bit-by-bit 이진 트리 알고리즘의 예.............................................. 15

그림 6. 제안한 EPC CLASS 1 UHF용 anti-collision 알고리즘의 태그인식 과정........ 17

그림 7. ScrollAllID 명령을 사용하였을 경우 제안한 EPC CLASS 1 UHF용 anti-

collision 알고리즘의 태그인식 과정................................................................. 19

그림 8. 순차적인 8개의 태그 ID의 트리 구조 (000~111) ....................................... 22

그림 9. 태그개수에 대한 태그가 보낸 총 bit 수 ................................................... 34

그림 10. bit-by-bit방식과 제안한 알고리즘에서 태그의 개수에 대한 반복횟수 ....... 35

그림 11. 충돌이 발생한 태그 개수에 따른 리더의 PingID 명령의 반복횟수(랜덤한

태그 ID).......................................................................................................... 37

그림 12. 충돌이 발생한 태그 개수에 따른 리더의 태그인식시간 (랜덤한 태그 ID

사용) ............................................................................................................... 39

그림 13. 충돌이 발생한 태그 개수에 따른 리더의 PingID 명령의 반복횟수

(순차적인 태그 ID 사용)................................................................................. 40

그림 14. 충돌이 발생한 태그 개수에 따른 리더의 태그인식시간 (순차적인 태그 ID

사용) ............................................................................................................... 41

ii

표 목차 표 1. 사용된 태그의 ID ........................................................................................... 5

iii

약 어 표

EPC Electronic Product Code

UHF Ultra High Frequency

RFID Radio Frequency Identification

OPNET Optimized Network Engineering Tools

ID Identifier

VB Valid Bit

BBS Basic Binary Search algorithm

BSBT Basic Slotted Binary Tree algorithm

MSBT Modified Slotted Binary Tree algorithm

BBT Bit-by-bit Binary Tree algorithm

IBBT Improved Bit-by-bit Binary Tree algorithm

iv

국문 요약

본 논문은 RFID 시스템에서 태그 anti-collision 알고리즘을 제안하고

분석한다. 제안한 RFID 시스템에서 EPC CLASS 0 anti-collision 알고리즘과 기

존의 이진 방식 알고리즘들(이진 탐색 알고리즘, time 슬롯을 이용한 슬롯단

위 이진 트리 알고리즘 및 EPC(Electronic Product Code)global에서 제안한 bit-

by-bit 이진 트리 알고리즘)의 성능을 수학적으로 비교하고 분석하였다. 수학

적 분석 결과는 OPNET(Optimized Network Engineering Tools) 시뮬레이션을 통

하여 그 결과를 검증하였다. 분석 결과에 의하면 제안한 Improved bit-by-bit

이진 트리 알고리즘의 성능이 기존의 anti-collision 알고리즘 중 가장 좋은 성

능을 보이는 bit-by-bit 이진 트리 알고리즘과 비교할 때 리더의 전송요구에

응답한 태그의 개수가 20개일 경우에는 약 304% 정도의 성능향상이 있었으

며 리더의 전송요구에 응답한 태그의 개수가 200개일 경우에는 839%의 성능

향상이 있었다.

또한 본 논문에서는 EPC CLASS 1 UHF anti-collision 알고리즘의 성능을

분석하고, 기존 알고리즘을 개선한 anti-collision 알고리즘을 제안한다. 제안한

알고리즘의 성능을 수학적으로 분석하고 기존의 알고리즘과 비교하였으며,

성능분석 결과 제안한 알고리즘의 성능이 월등하게 우수한 것을 확인하였으

며, 시뮬레이션을 통하여 그 결과를 검증하였다. 제안한 알고리즘은 기존 알

고리즘보다 랜덤한 ID(Identifier)를 갖는 태그를 사용했을 때 충돌이 발생한

태그의 개수가 20개일 경우에는 약 70%의 성능 향상이 있었으며, 태그의 개

수가 200개일 경우에는 약 130%의 성능 향상이 있었다. 또한, 기존 알고리즘

１

은 순차적인 태그 ID를 사용하였을 경우 랜덤한 ID를 사용하였을 경우보다

성능이 저하 되었으나 제안한 알고리즘은 순차적인 태그 ID를 사용하였을

경우가 랜덤한 ID를 사용하였을 경우보다 최대 약 16% 정도의 성능이 향상

되었다.

２

제１장 서론 RFID(Radio Frequency Identification) 기술은 무선 환경에서 여러 개의

물리적 개체를 인식하기 위해 사용되는 센서 네트워크의 한 형태로 사물에

매우 작은 전자 태그를 부착하고 전파를 이용하여 사물의 정보 및 주변 환

경정보를 자동으로 관리한다. 이러한 RFID 기술은 신정보화 시대를 이루어

향후 IT기술을 선도할 것이다. RFID 기술을 기반으로 구축될 유비쿼터스 센

서 네트워크 상에는 일상의 사물들, 상품들, 기업의 물류, 생산, 판매 등의

사업을 구성하는 시스템들이 모두 연결됨으로써 원가절감, 생산성 및 부가가

치 향상 등의 큰 기대효과를 얻을 수 있다. 그 외에도 RFID 기술은 전장, 병

원, 가정집, 사무실, 학교 등 여러 장소에서 편의를 제공하고, 보다 효율적인

업무를 할 수 있도록 도와줄 것이다. RFID 시스템은 여러 개의 리더와 태그

들로 구성된다. 리더는 무선채널을 통하여 각각의 태그들과 통신을 하는데,

모든 태그들이 리더가 보낸 신호를 동시에 듣게 되고 리더의 전송요구에 응

답을 한다. 이 때 발생하는 충돌은 두 가지가 있다. 하나의 리더가 동시에

응답한 여러 개의 태그를 인식해야 하는 문제가 발생을 하는데 이를 '태그

충돌(Tag collision)' 이라 한다[1]-[5]. 그리고 같은 주파수 대역을 사용하는 두

개 이상의 리더가 하나의 태그를 동시에 인식하려 할 때 발생하는 문제를 '

리더 충돌(Reader collision)' 이라 한다[6]-[7]. 이 두 가지 충돌을 효율적으로

해결하기 위한 anti-collision 알고리즘의 개발은 RFID 시스템의 성능 향상을

위해 매우 중요하다. 본 논문에서는 이 두 가지 충돌 중 '태그 충돌'을 해결

하기 위한 태그 anti-collision 알고리즘을 제안한다. RFID 시스템 성능의 중요

3

한 척도는 태그를 인식하기 위해 필요한 시간이다. 리더에 의해 전송요구가

있을 때 태그가 보낸 데이터가 적을수록 태그인식시간이 단축된다. 본 논문

에서는 제안한 Improved bit-by-bit 이진 트리 알고리즘과 이진 탐색 알고리즘

[8], time 슬롯을 이용한 슬롯단위 이진 트리 알고리즘[9], EPCglobal에서 제안

한 CLASS 0 bit-by-bit 이진 트리 알고리즘[10]-[12]을 수학적으로 비교하고 분

석하였으며 시뮬레이션을 통해 분석된 결과를 검증하였다. 또한 EPCglobal에

서 제안한 CLASS 1 UHF anti-collision 알고리즘[13]-[15]의 성능을 분석하고 기

존의 방식을 개선하여 보다 좋은 성능을 가지는 anti-collision 알고리즘을 제

안하였다. 그리고 제안한 알고리즘과 기존의 CLASS 1 UHF anti-collision 알고

리즘의 성능을 수학적으로 비교하고 분석하였으며 시뮬레이션을 통해 분석

된 결과를 검증하였다.

2장에서는 기존의 anti-collision 알고리즘을 설명하고, 3장에서는 제안한

anti-collision 알고리즘을 설명한다. 4장에서는 제안한 알고리즘을 분석하고 성

능평가를 위한 반복횟수와 태그가 보낸 총 bit 수를 구한다. 5장에서는 수학

적 분석 및 시뮬레이션을 통해 기존의 알고리즘과 제안한 알고리즘의 성능

을 비교하고 분석하며 6장에서 결론을 맺는다.

4

제２장 기존 충돌 방지 알고리즘

２.１ 이진 탐색 알고리즘

가. 기본 이진 탐색 알고리즘

기본 이진 탐색 알고리즘은 충돌이 발생한 부분을 점차 줄임으로써

전송 가능한 태그의 수를 줄여 충돌을 해결하는 방식이다[8]. 리더는 인식 가

능한 영역에 있는 모든 태그의 ID를 받아서 충돌이 일어나는 bit의 위치를

파악한다. 그 중 충돌이 발생한 최상위 bit가 1인 태그는 전송이 지연되고,

충돌이 발생한 최상위 bit가 0인 태그는 ID를 전송한다. 이런 과정을 순차적

으로 반복 수행함으로써 하나의 태그를 인식한다.

표 1. 사용된 태그의 ID

Table 1. IDs of the used tags

태그 1 0001

태그 2 0010

태그 3 1010

태그 4 1011

예를 들어 리더가 표 1에 있는 ID가 4 bit인 4개의 태그를 인식하기 위

해 REQUEST(≤1111) 명령을 전송하면 ID가 '1111'보다 작거나 같은 값을 가

지고 있는 태그들은 모두 자신의 ID를 전송한다. 리더는 태그로부터 수신된

5

ID의 시퀀스를 메모리에 저장한다. 수신된 bit 시퀀스 중 첫 번째 bit가 충돌

이 발생하였으므로 임의로 검색범위를 '≤0111'로 해서 REQUEST 명령을 전

송하게 되고 하나의 태그가 남을 때까지 이런 과정을 반복함으로써 n개의

태그 중 하나를 인식한다. n개의 태그가 존재한다고 할 때 하나의 태그를 인

식하기 위한 기본 이진 탐색 알고리즘의 반복횟수(IBBS)는 식 (1)과 같다.

log( ) 1log(2)BBS

nI = + (1)

이 때, 반복횟수는 리더의 REQUEST 명령 전송 횟수를 의미한다.

나. 동적 이진 탐색 알고리즘

기본 이진 탐색 알고리즘에서 태그는 항상 리더에게 모든 ID bit를 전

송한다. 따라서 ID의 길이가 길어지면 하나의 태그를 인식하기 위해 전송되

는 데이터의 양은 증가하므로 하나의 태그를 처리하는 시간이 증가한다. 동

적 이진 탐색 알고리즘은 이를 보완하기 위한 방법으로서, 리더는 REQUEST

명령 외에 VB(Valid Bit)를 추가하여 전송한다[8]. VB는 충돌이 발생하는 bit의

위치를 의미한다. 예를 들어 리더에 수신된 bit 시퀀스가 'X0XX'이면, 리더는

충돌이 발생하는 최상위 bit의 위치를 전송한다. 시퀀스 'X0XX'에서 'X'는 충

돌이 발생하였음을 의미한다. 이때 그 위치의 값이 1인 태그는 ID의 전송이

지연되고 0인 태그들은 ID중 VB까지의 bit를 제외한 나머지 bit를 전송한다.

이와 같은 방식으로 반복과정에서 전송되는 데이터의 양을 줄여 태그를 인

6

식하기 위한 탐색시간을 줄인다. 동적 이진 탐색 알고리즘에서 하나의 태그

를 인식하기 위한 반복횟수는 기본 이진 탐색 알고리즘과 같다. 그러나 데이

터의 총 전송량은 기본 이진 탐색 알고리즘과 비교할 때 50%까지 줄일 수

있기 때문에 하나의 태그를 인식하기 위한 탐색시간을 줄일 수 있다.

２.２ 슬롯단위 이진 트리 알고리즘

가. 기본 슬롯단위 이진 트리 알고리즘

리더가 태그에게 전송요구를 하면 응답한 태그들은 랜덤하게 0과 1을

선택함으로써 두 개의 그룹으로 나누어진다. 만일 리더가 i번째 슬롯에서 태

그에게 전송요구를 하면 모든 태그들은 i번째 슬롯에서 자신의 ID를 전송한

다. 리더의 전송 요구에 응답한 태그 중 0을 선택한 그룹의 태그들은 i+1번

째 슬롯에서 전송을 시도하고 1을 선택한 그룹의 태그들은 0을 선택한 그룹

의 태그들이 모두 성공적으로 ID를 전송할 때까지 기다리게 된다. i+1번째 슬

롯이 idle 슬롯이거나 성공적으로 전송을 하게 되면 1을 선택한 두 번째 그

룹의 태그들은 i+2번째 슬롯에서 재전송을 하게 된다. 여기서 idle 슬롯이란

태그로부터의 전송이 없는 슬롯을 의미한다. 그러나 i+1번째 슬롯에서 또다

시 충돌이 발생하게 되면 다시 랜덤하게 0 또는 1을 선택하여 또 다른 두

개의 하위 그룹으로 나누어진다. 이런 과정을 반복적으로 수행함으로써 모든

충돌을 해결할 수 있게 된다. 그림 1은 표 1에 있는 4개의 태그를 인식하기

위한 기본 슬롯단위 이진 트리 알고리즘의 진행순서를 나타낸다.

7

그림 1. 슬롯단위 이진 트리 알고리즘의 예

Fig. 1. An example of slotted binary tree algorithm

그림 1에서, 'X'는 리더의 요구에 응답한 태그의 개수가 2개 이상 이여

서 충돌이 발생했음을 의미하고, 'I'는 idle 슬롯을 의미하며, 'S'는 리더의 요구

에 응답한 태그의 개수가 1개여서 성공적인 전송이 이루어졌음을 의미한다.

슬롯단위 이진 트리 알고리즘에서 n개의 태그를 해결하기 위한 반복횟수

(IBBSBT)는 식 (2)와 같다[9].

2

2( 1)( 1)1[1 (1 ) ]

kn

BSBT kk

n kIk p p=

⎛ ⎞ − −= + ⎜ ⎟ − − −⎝ ⎠

∑ k (2)

이 때, p는 태그가 0 또는 1을 선택할 확률로 0.5이다.

나. Modified 슬롯단위 이진 트리 알고리즘

기본 슬롯단위 이진 트리 알고리즘에서 각 태그들이 0 또는 1을 선택

8

할 때 모두 0을 선택하거나 1을 선택하게 되면 idle상태가 존재하게 되는데,

modified 슬롯단위 이진 트리 알고리즘은 ternary feedback을 이용하여 idle슬롯

을 제거함으로써 충돌 해결 과정을 좀 더 빠르게 할 수 있다[9]. 그림 2는 표

1에 있는 4개의 태그를 인식하기 위한 modified 슬롯단위 이진 트리 알고리

즘의 진행순서를 나타낸다.

그림 2. 슬롯단위 이진 트리 알고리즘의 예

Fig. 2. An example of modified slotted binary tree algorithm

그림 2에서는 그림 1의 idle 슬롯이 제거되어 반복횟수가 1회 줄어든

것을 확인할 수 있다. Modified 슬롯단위 이진 트리 알고리즘에서 n개의 태그

를 해결하기 위한 반복횟수(I )는 식 (3)과 같다[9]. MSBT

2

( 1) [ (1 ) 1 ]1 2[1 (1 )]

k kn

MSBT k kk

n k p pI nk p p=

⎛ ⎞ − + − −= + ≥⎜ ⎟ − − −⎝ ⎠

∑ (3)

이 때, p는 기본 슬롯단위 이진 트리 알고리즘과 동일하다.

9

２.３ Bit-by-bit 이진 트리 알고리즘

EPCglobal에서 제안한 CLASS 0 bit-by-bit 이진 트리 알고리즘에서[10]-

[12], 리더가 인식할 수 있는 영역 내의 모든 태그들에게 ID 중 원하는 bit를

순서대로 요청하게 되면 모든 태그들은 리더의 요구에 대한 응답으로 0 또

는 1을 전송한다. 충돌이 발생 하지 않으면 리더는 태그로부터 받은 bit를 메

모리에 저장한 후 다음 bit를 요청하게 된다. 그러나 충돌이 발생하면 리더는

알고리즘에 의해 0 또는 1을 가진 그룹 중에서 하나의 그룹을 선택하고 다

음 bit를 요청하게 된다. 예를 들면, 리더가 인식할 수 있는 범위 내의 모든

태그에게 ID의 k번째 bit 전송요구(k의 초기값은 1)를 하게 되면 모든 태그들

은 리더의 요구에 대한 응답으로 k번째 bit를 전송하게 된다. 태그로부터 받

은 k번째 bit가 충돌이 발생하지 않으면 k번째 bit를 메모리에 저장한 후 다

음 bit의 전송을 요구한다. 그러나 충돌이 발생하면 메모리에 임의로 k번째

bit를 0으로 저장한 후 다음 bit의 전송요구와 함께 k번째 bit가 1인 모든 태

그를 inactive 상태로 만든다(inactive 상태 : 알고리즘 수행 중 충돌이 발생했

을 때 충돌이 발생한 bit가 1인 태그들이 일시적으로 리더의 다음 bit 전송

요구에 응답하지 않는 대기상태, 하나의 태그가 인식되면 리더는 inactive 상

태의 태그들을 리더의 전송요구에 응답할 수 있는 active 상태로 만든다). 이

런 과정을 태그의 ID길이만큼 반복함으로써 하나의 태그를 인식하게 된다.

10

그림 3. Bit-by-bit 이진 트리 알고리즘의 예

Fig. 3. An example of bit-by-bit binary tree algorithm

그림 3은 bit-by-bit 이진 트리 알고리즘을 사용하여 표 1에 있는 4개의

태그를 인식하기 위한 과정을 나타낸다. 이 때, 4개의 태그를 인식하기 위한

반복횟수는 16회(4×4 bit)이다. 만일 n개의 태그가 존재하고 각 태그의 ID가

j bit라면 모든 태그를 인식하기 위해 필요한 반복횟수(I )는 식 (4)와 같다. BBT

BBTI n j= × (4)

２.４ 기존의 EPC CLASS 1 UHF anti-collision 알고리즘

EPC CLASS 1 UHF anti-collision 알고리즘은 기본적으로 PingID 명령을

사용하여 Bin 슬롯에 태그의 응답을 수신하여 태그의 충돌을 해결한다. 하나

의 PingID 명령 응답 기간은 8개의 Bin 슬롯으로 구성되어 있고, 각 Bin 슬

롯은 순서대로 ‘000’부터 ‘111’까지를 나타낸다. PingID 명령을 사용하는 과정

은 다음과 같다. 리더가 PingID 명령을 전송하면 리더의 인식영역 안에 있는

11

태그 중 active 상태이며, 리더의 명령 패킷의 [PTR] 위치에서 시작하는

[LEN] 길이에 해당하는 [VALUE]값과 일치하는 ID를 가지고 있는 태그들이

ID의 [VALUE]값 다음의 최상위 3 bit를 이용하여 8개의 Bin 슬롯 중 자신의

Bin을 선택하고 8 bit ID를 전송한다. 따라서, ID의 [VALUE]값 다음의 최상위

3 bit가 ‘000’인 태그는 Bin 0에 응답을 하고, ‘111’인 태그는 Bin 7에 응답을

하게 된다. 태그들의 응답을 수신한 리더는 Bin 0부터 차례대로 다음과 같이

처리한다. 리더는 Bin 슬롯의 정보를 이용하여 하나의 Bin 슬롯에 두 개 이

상의 태그가 응답한 경우에는 다시 PingID 명령을 보내고, 하나의 Bin 슬롯

에 하나의 태그가 응답한 경우에는 ScrollID 명령을 이용하여 응답한 태그에

게 자신의 모든 ID bit를 전송하도록 한다. 따라서, ScrollID 명령에 응답하는

태그는 하나이며, ScrollID 명령을 받은 태그는 명령 패킷의 [PTR] 위치에서

시작하는 [LEN] 길이에 해당하는 [VALUE]값이 자신의 ID값과 일치하면 이

에 대한 응답으로 자신의 모든 ID를 리더에게 전송하고, 리더는 그 태그를

인식하게 된다. 하나의 태그를 인식한 리더는 다시 PingID 명령을 전송하게

되고, 다시 위의 과정을 반복하여 충돌이 발생한 모든 태그를 인식하게 된다.

리더가 PingID 명령과 ScrollID 명령을 사용하여 충돌이 발생한 태그를 인식

하는 과정을 간단한 예로 설명하면 그림 4와 같다. 보다 자세한 사항은 [14]

를 참조하면 알 수 있다.

12

그림 4. EPC CLASS 1 UHF anti-collision 알고리즘의 태그인식 과정

Fig. 4. An example of the conventional anti-collision algorithm

13

제３장 제안한 anti-collision 알고리즘

３.１ Improved bit-by-bit 이진 트리 알고리즘

Bit-by-bit 이진 트리 알고리즘[10]-[12]의 단점은 리더가 항상 태그 ID

의 모든 bit를 요구한다는 것이다. 본 논문에서 제안한 Improved bit-by-bit 이

진 트리 알고리즘은 이러한 문제점을 해결하고 개선함으로써 태그인식과정

을 단축시켰다. 리더는 우선 인식 가능한 모든 태그에게 모든 ID bit의 전송

을 요구한다. 태그들이 리더에게 ID bit를 전송할 때 전송한 bit가 모두 1(0)이

면 리더는 메모리에 1(0)을 저장하고, 충돌이 발생할 경우 메모리에 'X'를 저

장한다. 따라서, 리더는 태그들에게 모든 ID bit를 전송 받고 그 시퀀스를 메

모리에 저장한다. 초기에 모든 ID bit의 전송을 마친 후 리더는 태그에게 bit-

by-bit 방식으로 충돌이 발생한 bit만을 요구하여 태그를 인식하게 된다. 리더

는 태그 인식 과정 중 inactive 상태인 태그가 없는 경우에 '0(1)'을 전송 받게

되면 인식되지 않은 모든 태그들의 해당 시퀀스의 ID bit가 '0(1)'인 것을 알

수 있으므로 해당 시퀀스를 'X'에서 '0(1)'으로 바꾸게 된다. 그러므로 다음에

인식되는 태그는 보다 적은 반복횟수로 인식이 가능하게 되고, 같은 원리로

그 다음에 인식되는 태그들은 점차 적은 반복횟수를 갖게 된다. 만일 리더가

태그에게 마지막 bit 전송요구를 했을 때 충돌이 발생하면 ID 중 마지막 bit

만 다른 두 개의 태그가 존재한다는 것을 알 수 있으므로 알고리즘에 의해

동시에 두 개의 태그를 인식할 수 있다. 그림 5는 표 1에 있는 4개의 태그를

인식하기 위하여 제안한 Improved bit-by-bit 이진 트리 알고리즘의 진행순서를

나타낸다.

14

그림 5. Improved bit-by-bit 이진 트리 알고리즘의 예

Fig. 5. An example of Improved bit-by-bit binary tree algorithm

우선 리더는 사용된 모든 태그들에게 모든 ID bit의 전송을 요청한다.

리더는 태그들에게 k번째 bit를 전송받을 때 그 bit들이 모두 0(1)이면 그 위

치의 bit를 0(1)으로 저장하고, 충돌이 발생할 경우 구분하기 위해 X로 표시

한다. 따라서 리더에 저장된 bit정보는 X0XX가 된다. 첫 번째, 세 번째, 네

번째 bit는 충돌이 발생한 것이고, 2번째 bit는 0이다. 리더는 모든 태그들의

ID bit를 전송 받아 충돌 상태를 파악한 후 첫 번째 충돌이 발생한 bit부터 마

지막 충돌이 발생한 부분까지 bit-by-bit 방식으로 태그로부터 ID bit를 수신하

고, bit를 받는 중 inactive 상태인 태그가 없는 경우에 충돌이 발생하지 않으

면 그 위치의 상태를 X상태에서 전송 받은 bit로 바꾸어 저장한 후, 태그들

에게 다음으로 충돌이 발생한 bit를 요구한다. 따라서 첫 번째로 인식되는 태

그(0001)는 리더로부터 bit 전송요구를 2번 받는다. 이 때, 첫 번째 충돌이 발

생한 bit는 리더에서 0으로 인식하여 태그에게 bit 전송 요구를 하지 않는다.

15

두 번째와 세 번째로 인식되는 태그(0010, 1010)는 리더로부터 bit 전송요구를

3번 받는다. 여기서, ID가 '1010'인 태그와 '1011'인 태그는 ID 중 마지막 bit만

다르기 때문에 리더가 마지막 bit 전송요구를 했을 때 태그로부터 수신된 데

이터가 충돌이 발생하면 리더는 재전송 요구 없이 두 개의 태그를 동시에

인식한다. 그러므로 모든 태그를 인식하기 위한 리더의 전송 횟수는 9이고,

태그의 전송 횟수는 12이다. 태그의 총 전송 횟수가 리더의 전송 횟수보다 3

회 더 많은 이유는 초기에 리더가 모든 태그에게 자신의 모든 ID bit 전송을

요구하기 때문에 태그는 자신의 (ID bit 수 - 1)만큼 리더보다 더 많은 전송

횟수를 갖는다. 그림 3의 bit-by-bit 이진 트리 알고리즘과 그림 5의 Improved

bit-by-bit 이진 트리 알고리즘을 비교할 때 Improved bit-by-bit 이진 트리 알고

리즘에서 태그의 전송 횟수는 4회 감소했으며 리더의 전송 횟수가 7회 감소

했고, 리더가 태그에게 보내는 전송 bit 수가 태그가 리더에게 보내는 전송

bit 수보다 훨씬 많은 점을 고려하면 Improved bit-by-bit 이진 트리 알고리즘

은 bit-by-bit 이진 트리 알고리즘보다 확실히 성능이 향상된 것을 알 수 있

다. 또한, 사용된 태그의 ID가 순차적인 경우에는 충돌이 발생하는 bit 수가

줄어들기 때문에 성능이 더욱 향상된다. 자세한 성능분석은 4장에서 기술하

였다.

３.２ 제안한 EPC CLASS 1 UHF용 anti-collision 알고리즘

기존의 EPC CLASS 1 UHF anti-collision 알고리즘에서는 리더가 PingID

명령과 ScrollID 명령을 이용하여 하나의 태그를 인식한 후 다음 태그를 인

16

식하기 위해 처음부터 같은 과정을 반복한다. 그러나 만약 리더가 각 단계별

로 Bin 슬롯 정보를 기억할 수 있다면 불필요한 PingID 명령의 반복횟수를

줄여 알고리즘의 성능을 향상시킬 수 있다. 제안한 알고리즘의 태그인식 과

정을 살펴보면 그림 6과 같다.

그림 6. 제안한 EPC CLASS 1 UHF용 anti-collision 알고리즘의 태그인식 과정

Fig. 6. Tag identification procedure of the proposed algorithm for EPC CLASS 1 UHF

그림 4에서는 하나의 태그를 인식한 후 다시 처음부터 PingID 명령을

사용해 다음 태그를 인식한다. 그러나 제안한 방식을 이용한다면 그림 6과

17

같이 불필요한 명령의 반복을 줄이고 보다 빠른 시간에 많은 태그를 인식할

수 있다. 또한, 기존 알고리즘은 충돌이 발생한 태그를 인식하기 위해 PingID

명령과 ScrollID 명령만을 사용한다. 그러므로 기존 알고리즘을 순차적인 ID

를 갖는 태그들을 인식하는데 사용한다면 태그 하나하나를 인식하기 위해

계속 PingID명령을 반복하게 되므로 오히려 랜덤한 ID를 갖는 태그들을 인

식할 때보다 성능이 저하된다. 그러나 [14]에 정의되어 있는 ScrollAllID 명령

을 사용한다면 태그 ID bit의 충돌 정보를 이용하여 불필요한 PingID 명령의

반복횟수를 줄이고 알고리즘의 성능을 향상시킬 수 있다. ScrollAllID 명령을

사용하여 태그를 인식하는 방법은 다음과 같다. 우선 리더는 ScrollAllID 명

령을 태그들에게 전송한다. ScrollAllID 명령을 받은 태그들은 자신의 모든 ID

를 리더에게 전송을 하게 되고, 이를 수신한 리더는 전송된 ID bit의 충돌 정

보를 알 수 있게 된다. 따라서, 리더는 태그들에게 ScrollAllID에 대한 응답을

받은 후 [PTR] field를 최초 충돌이 발생한 ID bit의 위치로 설정하여 PingID

명령을 보낸다. 이 때, 모든 태그가 응답을 하게 되고, 리더는 Bin 슬롯의 정

보를 기억하면서 하나의 태그만이 응답할 때까지 PingID 명령을 반복한다.

하나의 태그가 응답을 하면 ScrollID 명령을 사용하여 응답한 태그를 인식하

고, Bin 슬롯 정보를 이용하여 처음 단계로 돌아가 PingID 명령을 반복할 필

요 없이 최초 하나의 태그가 인식되기 바로 전 단계로 돌아가 태그 인식과

정을 거쳐 다음 태그를 인식하게 되고, 충돌이 발생한 모든 태그를 인식할

때까지 이와 같은 과정을 반복하게 된다. 그림 7은 ScrollAllID 명령을 사용

하였을 경우 제안한 알고리즘의 태그 인식과정을 나타낸다.

18

그림 7. ScrollAllID 명령을 사용하였을 경우 제안한 EPC CLASS 1 UHF용 anti-collision 알고

리즘의 태그인식 과정

Fig. 7. Tag identification procedure of the proposed algorithm for EPC CLASS 1 UHF using

ScrollAllID command

19

제４장 성능 분석

４.１ Improved bit-by-bit 이진 트리 알고리즘

제안한 Improved bit-by-bit 이진 트리 알고리즘의 성능을 분석하기 위하

여 반복횟수와 태그가 전송한 총 bit 수를 계산한다. 태그 ID의 길이는 36

bit[10] 라고 가정한다.

가. 제안한 알고리즘의 반복횟수 분석

0부터 n-1까지의 값을 갖는 순차적인 n개의 ID를 갖는 태그들 중 임의

의 m개의 태그들이 사용된다고 가정하고, 총 태그 ID는 36 bit라고 가정할 때,

n의 범위는 2r<n≤2(r+1)(단, 0≤r≤35, r은 정수)이다. 이 때 반복횟수가 r+1 인

태그 개수의 기대값 N 은 식 (5)와 같다. r+1

12 1

r

rN mn+ = × + (5)

그리고 반복횟수가 r, r-1, r-2인 태그 개수의 기대값 N , N , Nr r-1 r-2는 각각

식 (6), (7), (8)과 같다.

21

2

r

r

mn

N

⎛ ⎞−⎜ ⎟

⎝= ⎠ (6)

1

21

4

r

r

mn

N −

⎛ ⎞−⎜ ⎟

⎝= ⎠ (7)

20

2

21

8

r

r

mn

N −

⎛ ⎞−⎜ ⎟

⎝= ⎠ (8)

따라서 을 마지막 bit만 충돌이 발생한 태그들을 고려하지 않았을

경우의 반복횟수라고 정의하면 은 식 (9)와 같다.

Ω

Ω

( ) ( )

( ) ( )max max

2

max

max max

2log 1

1

2 21 12 1 1 1

2 4

2 21 11 1

2 2

2 21 12( 1 ) 1 ( 1)

2 2

r

r r

r

r r

k k

r rm

n r

kkk

m mn n

m r r rn

m mn n

r k r k

m mn n

r k m rn

⎛ ⎞−⎜ ⎟⎜ ⎟

⎝ ⎠

=

⎛ ⎞ ⎛ ⎞− −⎜ ⎟ ⎜ ⎟⎛ ⎞ ⎝ ⎠ ⎝ ⎠Ω = × + + + + − +⎜ ⎟

⎝ ⎠⎛ ⎞⎛ ⎞ ⎛ ⎞

− −⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠⎜ ⎟⋅⋅ ⋅ + + − + − −

⎜ ⎟⎜ ⎟⎝ ⎠

⎛ ⎞ ⎛ ⎞− −⎜ ⎟ ⎜ ⎟⎛ ⎞⎝ ⎠ ⎝ ⎠= + − + × + + + −⎜ ⎟

⎝ ⎠∑ max1 ( )r k

⎛ ⎞⎜ ⎟⎜ ⎟ −⎜ ⎟⎜ ⎟⎝ ⎠

(9)

22log 1

r

mn

⎛ ⎞−⎜

⎝ ⎠이 때, kmax는 ⎟보다 작거나 같은 최대정수가 된다. 따라서,

마지막 bit만 충돌이 발생한 태그들을 고려했을 경우의 반복횟수는 에 마

지막 bit만 충돌이 발생한 태그들을 고려한 term을 곱하여 나타낼 수 있다.

Ω

제안한 알고리즘의 반복횟수는 태그의 개수가 짝수일 때와 홀수일 때

로 구분하여 분석하였다. 그리고 태그의 개수가 짝수일 때와 홀수일 때 각각

에 대해 태그의 개수가 총 태그개수의 50%이하일 때와 초과일 때로 구분하

여 분석하였다.

21

(1) 태그의 개수가 짝수일 경우

그림 8과 같이 순차적인 ID를 갖는 8(000~111)개의 태그가 있다고 가

정한다. 이 중 임의의 2개의 태그를 선택할 때 그 두 태그의 ID 중 마지막

bit를 제외한 모든 bit가 동일할 확률은 C /4 1 8C2이고, 그렇지 않을 확률은

(4C0 × 4C 22)/ C×2 8 2이다. 그리고 임의의 3개의 태그를 선택할 때 그 두 태그의

ID 중 마지막 bit를 제외한 모든 bit가 동일한 태그가 1쌍일 확률은

(4C1× 3C1×21)/8C3이고, 0쌍일 확률은 (4C0× 4C ×23)/ C 이다. 3 8 3

그림 8. 순차적인 8개의 태그 ID의 트리 구조 (000~111)

Fig. 8. Tree structure of 8 sequential tag ID (000~111)

또한 그림 8의 8개의 태그 중 임의의 4개의 태그를 선택할 때 그 두

태그의 ID 중 마지막 bit를 제외한 모든 bit가 동일한 태그가 2쌍일 확률은

4C2/8C4이고 1쌍일 확률은 (4C1× 3C2× 22)/8C4, 0쌍일 확률은 (4C0× 4C 24)/4× 8C4이

다.

22

따라서, ID가 순차적인 n개의 태그 중 사용된 태그의 개수(m)가 총 태

그 개수의 50%이하( 02nm< ≤ )일 때, 마지막 bit를 제외한 모든 bit가 동일한

두 개의 태그가 k쌍일 확률 pk를 구하면 식 (10)과 같다.

( 2 )22 22

, 02

m k

k

n n k

k m k mpnm

−⎛ ⎞⎛ ⎞−⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟

−⎝ ⎠⎝ ⎠ k= ≤ ≤⎛ ⎞⎜ ⎟⎝ ⎠

(10)

그리고 ID 중 마지막 bit를 제외한 모든 bit가 동일한 두 개의 태그가

k쌍일 때 전송 횟수는 (m-k)번이다. 따라서 전송 횟수의 평균값 MI는 식 (11)

과 같다.

(2

0

mk

I kk

)M p m k=

=

= × −∑ (11)

/ mΩ하나의 태그를 인식하기 위한 평균 반복횟수는 이므로 사용된

태그의 개수가 짝수이고 총 태그개수의 50%이하 일 때 m개의 태그를 인식

하기 위한 반복횟수(I )는 식 (12)와 같다. IBBT

23

( 2 )

2

0

22 221 (

m km

IBBTk

n n k

k m k)I m k

nmm

−

=

⎛ ⎞⎛ ⎞−⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟

−⎝ ⎠⎝ ⎠= Ω× × × −⎛ ⎞⎜ ⎟⎝ ⎠

∑ (12)

ID가 순차적인 n개의 태그 중 사용된 태그의 개수(m)가 총 태그 개수

의 50%를 초과(2n m n< ≤ )할 때, 마지막 bit를 제외한 모든 bit가 동일한 두

개의 태그가 k쌍일 확률 pk를 계산하면 식 (13)과 같다.

( 2 )2 22

2 ,2 2

m k

k

nn k

nk k m npnm

−

⎛ ⎞−⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟− +⎜ ⎟⎝ ⎠⎝ ⎠ mm k= − ≤ ≤⎛ ⎞⎜ ⎟⎝ ⎠

(13)

ID 중 마지막 bit를 제외한 모든 bit가 동일한 두 개의 태그가 k쌍일

때 전송 횟수는 (m-k)번이다. 따라서 사용된 태그의 개수가 짝수이고 총 태그

개수의 50%를 초과할 때 m개의 태그를 인식하기 위한 반복횟수(IIBBT)는 식

(14)와 같다.

( 2 )

2

2

2 22

1 2 (

m k

m

IBBTnk m

nn k

nk k m)I m k

nmm

−

= −

⎛ ⎞−⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟− +⎜ ⎟⎝ ⎠⎝ ⎠= Ω× × × −⎛ ⎞⎜ ⎟⎝ ⎠

∑ (14)

24

(2) 태그의 개수가 홀수일 경우

ID가 순차적인 n개의 태그 중 사용된 태그의 개수(m)가 총 태그 개수

의 50%미만( 02nm< < )일 때, 마지막 bit를 제외한 모든 bit가 동일한 두 개의

태그가 k쌍일 확률 pk를 구하면 식 (15)와 같다.

( 2 )22 22 1, 0

2

m k

k

n n k

k m k mpnm

−⎛ ⎞⎛ ⎞−⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟

−k −⎝ ⎠⎝ ⎠=

⎛ ⎞⎜ ⎟⎝ ⎠

≤ ≤ (15)

ID 중 마지막 bit를 제외한 모든 bit가 동일한 두 개의 태그가 k쌍일

때 전송 횟수는 (m-k)번이다. 따라서 사용된 태그의 개수가 홀수이고 총 태그

개수의 50%미만일 때 m개의 태그를 인식하기 위한 반복횟수(IIBBT)는 식 (16)

과 같다.

( 2 )1

2

0

22 221 (

m km

IBBTk

n n k

k m k)I m k

nmm

−−

=

⎛ ⎞⎛ ⎞−⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟

−⎝ ⎠⎝ ⎠= Ω× × × −⎛ ⎞⎜ ⎟⎝ ⎠

∑ (16)

ID가 순차적인 n개의 태그 중 사용된 태그의 개수(m)가 총 태그 개수

의 50%를 초과 (2n m n< < )할 때, 마지막 bit를 제외한 모든 bit가 동일한 두

개의 태그가 k쌍일 확률 pk를 계산하면 식 (17)과 같다.

25

( 2 )2 22

12 ,2 2

m k

k

nn k

nk k m n mp mnm

−

⎛ ⎞−⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟− +⎜ ⎟⎝ ⎠k −⎝ ⎠= −

⎛ ⎞⎜ ⎟⎝ ⎠

≤ ≤ (17)

ID 중 마지막 bit를 제외한 모든 bit가 동일한 두 개의 태그가 k쌍일

때 전송 횟수는 (m-k)번이다. 따라서 사용된 태그의 개수가 홀수이고 총 태그

개수의 50%를 초과할 때 m개의 태그를 인식하기 위한 반복횟수(IIBBT)는 식

(18)과 같다.

( 2 )

12

2

2 22

1 2 (

m k

m

IBBTnk m

nn k

nk k m)I m k

nmm

−

−

= −

⎛ ⎞−⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟− +⎜ ⎟⎝ ⎠⎝ ⎠= Ω× × × −⎛ ⎞⎜ ⎟⎝ ⎠

∑ (18)

최종적으로, 사용된 태그를 모두 인식하는데 필요한 반복횟수는 식

(12), (14), (16) 및 (18)을 사용하여 구할 수 있다.

나. 태그가 보낸 총 bit 수

RFID 시스템 성능의 중요한 척도는 태그를 인식하기 위해 필요한 시

간이다. 리더에 의해 전송요구가 있을 때 태그가 보낸 데이터가 적을수록 태

26

그인식시간이 단축된다. 따라서 본 논문에서는 리더의 요구에 태그가 응답한

횟수의 총 합인 반복횟수와 태그가 보낸 총 bit 수를 구한다. Improved bit-by-

bit 이진 트리 알고리즘을 제외한 각 알고리즘의 반복횟수를 I라 하고 매 반

복마다 태그가 보낸 bit 수를 BBI라 하면 태그가 보낸 총 bit 수 BtotalB

B

은 식

(19)와 같다.

total IB I= × (19)

Improved bit-by-bit 이진 트리 알고리즘의 경우 리더가 최초 태그에게

모든 ID bit 전송을 요구할 때 태그는 리더에게 36 bit를 전송을 하게 되므로,

태그가 보낸 총 bit 수는 반복횟수에 35를 더하면 된다.

４.２ EPC CLASS 1 UHF용 anti-collision 알고리즘

기존의 EPC CLASS 1 UHF anti-collision 알고리즘과 제안한 anti-collision

알고리즘의 성능을 수학적으로 분석한다. 분석결과로 리더가 전송하는

PingID 명령의 반복횟수와 태그 인식 시간을 도출한다.

가. 기존의 EPC CLASS 1 UHF anti-collision 알고리즘

태그의 ID는 랜덤하고, 충돌이 발생한 태그의 개수는 m, Bin 슬롯의

개수를 r이라 할 때, Bin 0에서 Bin n-1 응답한 태그가 없을 확률 qn은 식 (20)

과 같다.

27

- m

nr nq

r⎛ ⎞= ⎜ ⎟⎝ ⎠

(20)

그리고 나머지 r-n개의 슬롯 중 Bin n에 응답이 없을 확률은 [(r-1-n)/(r-

n)]m 이며, r-n개의 슬롯 중 Bin n에 응답한 태그가 하나일 확률은 [m/(r-

n)]× [(r-1-n)/(r-n)]m-1 이다. 따라서 r-n개의 슬롯 중 Bin n에 응답한 태그가 2개

이상일 확률 q 은 식 (21)과 같이 나타내어진다. rn

11 11m m

rnr n r nq m

r n r n r n

− 1⎡ ⎤− − − −⎛ ⎞ ⎛ ⎞= − − ⋅⎢ ⎥⎜ ⎟ ⎜ ⎟− −⎝ ⎠ ⎝ ⎠ −⎢ ⎥⎣ ⎦ (21)

그러므로 리더가 첫 번째 PingID 명령 전송시 Bin 0에서 Bin n-1까지

응답한 태그가 없고 Bin n에서 2개 이상의 태그가 응답할 확률을 p1n이라 정

의하면 p1n은 식 (22)와 같으며

1

11 11

m m m

nr n r n r np m

r r n r n r

− 1n

⎡ ⎤− − − − −⎛ ⎞ ⎛ ⎞ ⎛ ⎞= − − ⋅⎢ ⎥⎜ ⎟ ⎜ ⎟ ⎜ ⎟− − −⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎢ ⎥⎣ ⎦ (22)

0 n 7≤ ≤이때, r은 8이고 n은 인 정수이다.

따라서, 첫 번째 PingID 명령 전송 후 다시 리더가 PingID 명령을 전

송할 확률 p 은 식 (23)과 같다. 1

7

10

nn

p p=

= 1∑ . (23)

28

Bin 슬롯의 개수는 r개이므로, 리더의 첫 번째 PingID 명령 전송 시

같은 Bin 슬롯에 응답하는 태그 개수의 기대값은 m/r이다. 따라서 리더가 두

번째 PingID 명령 전송시 Bin 0에서 Bin n-1까지 응답한 태그가 없고 Bin n에

서 2개 이상의 태그가 응답할 확률을 p2n이라 정의하면 p2n은 식 (24)와 같이

계산된다.

1

21 11

m m mr r r

nr n r n m r np

r r n r r n r

−⎡ ⎤− − − − −⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎢ ⎥= − − ⋅⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎢ ⎥− −⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎣ ⎦

1n−

2

(24)

따라서, 두 번째 PingID 명령 전송 후 다시 리더가 PingID 명령을 전

송할 확률 p 는 식 (25)와 같다. 2

7

20

nn

p p=

=∑ (25)

리더가 k 번째 PingID 명령을 전송하였을 때 같은 Bin 슬롯에 응답하

는 태그 개수의 기대값은 m/rk-1이다. 따라서, k 번째 PingID 명령 전송 후 다

시 리더가 PingID 명령을 전송할 확률 pk는 식 (26)과 같다.

1 1 1 17 7

10 0

1 11k k km m m

r r r

k kn kn n

r n r n m r np pr r n r r n

− − −−

−= =

1r n

⎡ ⎤− − − − −⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎢ ⎥= = − − ⋅⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎢ ⎥− −⎝ ⎠ ⎝ ⎠ ⎝ ⎠ −⎣ ⎦

∑ ∑ (26)

29

그러므로 최초 하나의 태그를 인식하기 위한 리더의 PingID 명령 전송

횟수의 기대값 I1은 식 (27)과 같이 계산된다.

17

10 0

1 1 11 1 ,k k k

m m mr r r

k kk n

r n r n m r n mIr r n r r n r n

−∞

= =

⎡ ⎤− − − − −⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎢ ⎥= + − − ⋅ >⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎢ ⎥− − −⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎣ ⎦

∑∑ 1r

(27)

리더가 하나의 태그를 인식하면 남은 태그의 개수는 m-1이 되고 두

번째 태그를 인식하기 위해서 모든 과정을 처음부터 반복하므로 리더가 m개

의 태그를 모두 인식할 때까지 전송한 PingID 명령의 평균 반복횟수 Itotal은

식 (28)과 같이 계산된다.

17

2 0 0

1 1 11 ,k k k

L L Lm r r r

total k kL k n

r n r n L r n mI mr r n r r n r n r

−∞

= = =

⎡ ⎤− − − − −⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎢ ⎥= + − − ⋅ >⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎢ ⎥− − −⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎣ ⎦

∑∑∑ 1 (28)

그리고 리더는 m개의 태그를 인식하기 위하여 m번의 ScrollID 명령을

반복하므로 리더가 m개의 태그를 인식하는데 걸리는 총 시간은 리더가

PingID 명령과 ScrollID 명령을 전송하는데 걸리는 시간과 그에 따른 태그의

응답 시간, 리더와 태그의 지연 시간을 모두 합하여 구할 수 있다. 리더가

태그에게 보내는 패킷의 크기를 RL_C라 정의하고, 리더의 data rate을 DRreader

라 정의하면, 리더가 m개의 태그를 인식하는 동안 리더가 태그에게 명령을

전송하는데 걸리는 시간 treader는 식 (29)와 같으며,

30

_ ( )totalreader

reader

RL C I mtDR

+= (29)

이 때, RL_C는 147 bit이며, DRreader는 70,180 bps 이다[14].

또한, 리더의 PingID 명령에 의한 태그의 응답 패킷의 크기를 TL_P라

하고, ScrollID 명령에 의한 태그의 응답 패킷의 크기를 TL_S로 정의하며, 태

그의 data rate을 DRtag라 정의할 때, 리더가 m개의 태그를 인식하는 동안 태

그가 리더에게 응답을 전송하는데 걸리는 시간 t 는 식 (30)과 같으며, tag

_ _totaltag

tag

TL P I TL S mtDR

× + ×= (30)

이 때, TL_P는 8 bit, TL_S는 120 bit 이고, DRtag는140,350 bps이다.

리더의 전송 지연을 DEreader라 정의하고, 태그의 전송 지연을 DEtag라

정의할 때, 리더가 m개의 태그를 인식하는 동안의 총 지연시간 tdelay는 식

(31)과 같고,

( )(delay total reader tagt I m DE DE= + + ) (31)

이 때, DEreader는 17.81 ㎲이고 DE 는 57 ㎲이다. tag

따라서, 리더가 m개의 태그를 인식하는데 소요되는 총 시간 ttotal은 식

(32)와 같다.

total reader tag delayt t t t= + + . (32)

31

나. 제안한 anti-collision 알고리즘

태그의 ID는 랜덤하고, 충돌이 발생한 태그의 개수를 m이라 하며, Bin

슬롯의 개수를 r이라 할 때 최초 리더가 PingID 명령 전송시 하나의 Bin 슬

롯에 2개 이상의 태그가 응답할 확률 pcol은 식 (33)과 같다.

11 11m m

colr rp m

r r

−⎛ ⎞− −⎛ ⎞ ⎛ ⎞ 1r

= − −⎜ ⎜ ⎟ ⎜ ⎟⎜ ⎝ ⎠ ⎝ ⎠⎝ ⎠⋅ ⎟⎟ (33)

Bin 슬롯은 모두 r개이므로 첫 번째 PingID 명령 전송 이후 리더가 다

시 전송할 PingID 명령 개수의 기대값 I1은 식 (34)와 같이 계산된다.

1

11 11

m mr rI r mr r

−⎛ ⎞− −⎛ ⎞ ⎛ ⎞ 1r

= × − − ⋅⎜ ⎜ ⎟ ⎜ ⎟⎜ ⎝ ⎠ ⎝ ⎠⎝ ⎠⎟⎟ (34)

제안한 알고리즘의 경우 리더가 Bin 슬롯의 정보를 기억하므로 Bin 슬

롯들은 트리 구조를 이루게 된다. 따라서, 두 번째 PingID 명령 전송 이후 리

더가 다시 전송할 PingID 명령 개수의 기대값 I2는 식 (35)와 같다.

12

21 11

m mr rr m rI r

r r r

−⎛ ⎞− −⎛ ⎞ ⎛ ⎞⎜ ⎟1r

= × − − ⋅⎜ ⎟ ⎜ ⎟⎜ ⎟⎝ ⎠ ⎝ ⎠⎝ ⎠

(35)

32

그러므로 k 번째 PingID 명령 전송 이후 리더가 다시 전송할 PingID

명령 개수의 기대값 Ik는 식 (36)과 같다.

1 1 1

1

1 11k km m

r rkk k

r m rI rr r r

− −−

−

⎡ ⎤− −⎛ ⎞ ⎛ ⎞⎢ ⎥1r

= × − − ⋅⎜ ⎟ ⎜ ⎟⎢ ⎥⎝ ⎠ ⎝ ⎠⎣ ⎦

(36)

결과적으로 리더가 m개의 태그를 모두 인식할 때까지 전송한 PingID

명령의 반복횟수 Itotal은 식 (37)과 같이 계산되며,

1 1 1

0 10 1

1 1 1r

1k km m

r rktotal k k

k k

r m rI I I rr r r

− −−∞ ∞

−= =

⎛ ⎞− −⎛ ⎞ ⎛ ⎞⎜ ⎟= = + × − − ⋅⎜ ⎟ ⎜ ⎟⎜ ⎟⎝ ⎠ ⎝ ⎠⎝ ⎠

∑ ∑ , 1 1k

mr − > (37)

I0는 최초 리더의 PingID 명령 전송 횟수로 1이다.

제안한 알고리즘의 경우 리더가 m개의 태그를 인식하는데 걸리는 총

시간 ttotal은 식 (29), (30), (31)과 같은 과정을 거쳐 식 (32)와 같이 구할 수 있

다. ScrollAllID 명령을 사용하는 경우 ScrollID 명령의 수만 1만큼 증가하므로

리더가 m개의 태그를 인식하는데 걸리는 총 시간 ttotal은 식 (29), (30), (31)의

과정에 m대신 m+1을 대입하여 식 (32)와 같이 구할 수 있다.

33

제５장 수학적 분석 및 시뮬레이션 결과

５.１ Improved bit-by-bit 이진 트리 알고리즘

그림 9는 각 알고리즘에서 태그의 개수에 따른 태그가 전송한 총 bit

수를 나타낸 것이며 이것은 수학적 분석에 의한 결과이다. 제안한 알고리즘

은 리더로부터 전송요구가 있을 때 마다 태그 ID 중 1 bit 만을 전송한다. 그

러나 이진 탐색 알고리즘과 기본 슬롯단위(basic slotted) 이진 트리 알고리즘

은 리더로부터의 전송요구가 있을 때마다 태그 ID의 모든 bit 또는 2 bit 이상

을 전송한다.(단, 동적 이진 탐색 알고리즘은 리더로부터의 전송요구가 있을

때마다 태그가 전송하는 bit 수가 점점 감소한다.)

그림 9. 태그개수에 대한 태그가 보낸 총 bit 수

Fig. 9. The number of total transferred bits from the tag versus the number of used tags.

34

그림 9에서 100개의 태그를 인식하기 위해 이진 탐색 알고리즘은

22491 bit를 전송하고 modified 슬롯단위(modified slotted) 이진 트리 알고리즘

은 9482 bit를 전송하며, EPCglobal에서 제안한 bit-by-bit 이진 트리 알고리즘은

3600 bit를 전송한다. 그러나 본 논문에서 제안한 Improved bit-by-bit 이진 트

리 알고리즘은 100개의 태그를 인식하기 위해 578 bit만을 전송하므로 기존의

anti-collision 알고리즘과 비교할 때 성능이 크게 향상되었음을 알 수 있다.

또한 제안한 Improved bit-by-bit 이진 트리 알고리즘은 태그의 개수가 200개인

경우 기존의 알고리즘 중 성능이 가장 뛰어난 bit-by-bit 이진 트리 알고리즘

과 비교할 때 839%의 성능향상이 있음을 알 수 있다.

그림 10. bit-by-bit방식과 제안한 알고리즘에서 태그의 개수에 대한 반복횟수

Fig. 10. The number of iterations versus the number of used tags in bit-by-bit binary tree algorithm

and the proposed algorithm.

35

그림 10은 bit-by-bit 이진 트리 알고리즘(BBT)과 제안한 Improved bit-

by-bit 이진 트리 알고리즘(IBBT)에서 태그의 ID bit 수[10]에 따른 태그의 개

수에 대한 반복횟수를 나타낸다. 그림 10에서 선으로 표시된 부분은 수학적

분석의 결과를 나타내고 기호로 표시된 부분은 OPNET을 이용한 시뮬레이션

결과를 나타낸다. 수학적 분석에 의해 얻은 값과 시뮬레이션의 결과 값이 매

우 유사함을 알 수 있었다. 그림에서 알 수 있듯이 bit-by-bit 이진 트리 알고

리즘은 태그의 ID bit 수가 증가할수록 태그를 인식하기 위한 반복횟수가 증

가하는 것을 알 수 있다. 그러나 제안한 Improved bit-by-bit 이진 트리 알고리

즘은 태그의 ID bit 수가 증가하여도 반복횟수에는 변함이 없는 것을 알 수

있다. 태그의 ID bit 수가 많을수록 제안한 알고리즘이 더욱 우수한 성능을

보이는 것을 알 수 있다. 제안한 Improved bit-by-bit 이진 트리 알고리즘은

bit-by-bit 이진 트리 알고리즘과 비교할 때 태그의 ID가 36 bit인 경우 순차적

인 200개의 태그 중 사용된 태그가 임의의 20개일 경우에는 약 304%정도의

성능향상이 있고 사용된 태그가 200개일 경우에는 839%의 성능향상이 있음

을 알 수 있었다. 따라서 태그의 개수가 증가할수록 제안한 Improved bit-by-

bit 이진 트리 알고리즘이 더욱더 좋은 성능을 보임을 알 수 있었다. 따라서

분석결과에 의하면 제안한 알고리즘은 n개의 태그를 인식하기 위해 태그가

보낸 bit 수가 기존의 알고리즘에 비해 적기 때문에 태그를 인식하기 위한

시간이 단축된다.

36

５.２ 제안한 EPC CLASS 1 UHF용 anti-collision 알고리즘

본 절에서는 기존의 EPC CLASS 1 UHF anti-collision 알고리즘과 제안한

알고리즘의 성능을 수학적으로 비교하고 분석하였으며, 시뮬레이션을 통해

그 결과를 검증하였다. 태그의 ID는 96 bit이고, 그 중 실제로 태그를 인식하

기 위한 부분은 36 bit로 가정하였다. 실제와 동일한 환경의 시뮬레이터 구축

을 위해서 시뮬레이터에서 사용된 리더와 태그의 전송 패킷의 크기는 실제

패킷 크기와 동일하게 하였으며, 리더와 태그의 data rate도 실제와 동일하게

하였고 리더와 태그의 패킷 전송 지연을 모두 고려하였다[14].

20 40 60 80 100 120 140 160 180 2000

100

200

300

400

500

600

사용된태그의 개수

Pin

gID

명령의반복횟수

EPC CLASS 1( )기존의 수학적분석 EPC CLASS 1( )기존의 시뮬레이션 ( )제안한알고리즘 수학적분석 ( )제안한알고리즘 시뮬레이션 using ScrollAllID( )제안한알고리즘 수학적분석 using ScrollAllID( )제안한알고리즘 시뮬레이션

그림 11. 충돌이 발생한 태그 개수에 따른 리더의 PingID 명령의 반복횟수(랜덤한 태그 ID)

Fig. 11. The number of PingID command for the number of used tags(random tag ID)

37

그림 11은 기존의 EPC CLASS 1 UHF anti-collision 알고리즘과 제안한

알고리즘, ScrollAllID 명령을 사용하여 제안한 알고리즘에 대한 충돌이 발생

한 태그의 개수에 따른 리더의 PingID 명령 전송 반복횟수를 나타낸다. 태그

의 ID는 랜덤한 ID를 사용하였으며, 선은 수학적 분석결과를 나타내고, 도형

은 시뮬레이션 결과를 나타낸다. 그림 11을 보면 기존의 알고리즘에서 수학

적 분석결과와 시뮬레이션 결과가 약간의 차이를 나타낸다. 그 이유는

PingID 명령의 반복횟수를 계산하는 과정에서 1k

mr

≤ 이후에 발생할 수 있는

추가적인 리더의 PingID 명령을 고려하지 않았기 때문이다. 그림 11에서 알

수 있듯이 제안한 알고리즘이 기존의 알고리즘보다 리더의 PingID 전송 반복

횟수가 현저히 적다.

그림 12는 위의 세 알고리즘에 대한 충돌이 발생한 태그의 개수에 따

른 리더의 태그인식시간을 나타낸다. 태그의 ID는 랜덤한 ID를 사용하였으며,

선은 수학적 분석결과를 나타내고, 도형은 시뮬레이션 결과를 나타낸다. 그

림 12에서 알 수 있듯이 제안한 알고리즘이 기존의 알고리즘보다 태그인식

시간에 있어 태그의 개수가 20개 일 때 약 70%의 성능 향상이 있었으며, 태

그의 개수가 200개 일 때 약 130%의 성능 향상이 있었다. 초당 태그인식속

도로 계산하면 기존의 알고리즘의 경우 초당 약 117개의 태그 인식이 가능

하며, 제안한 알고리즘의 경우 초당 약 252개의 태그 인식이 가능하다.

38

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

사용된태그의개수

(sec

)태그인식시간

EPC CLASS 1( )기존의 수학적분석 EPC CLASS 1( )기존의 시뮬레이션 ( )제안한알고리즘 수학적분석 ( )제안한알고리즘 시뮬레이션 using ScrollAllID( )제안한알고리즘 수학적분석 using ScrollAllID( )제안한알고리즘 시뮬레이션

그림 12. 충돌이 발생한 태그 개수에 따른 리더의 태그인식시간 (랜덤한 태그 ID 사용)

Fig. 12. Tag identification time for the number of used tags (random tag ID)

그림 13은 위의 세 알고리즘에 대해 순차적인 태그 ID를 사용하였을

경우 충돌이 발생한 태그의 개수에 따른 리더의 PingID 명령 전송 반복횟수

를 나타내며 이는 시뮬레이션 결과이다. 그림 13에서 기존의 알고리즘은 순

차적인 ID를 갖는 태그에 대해서 오히려 리더의 PingID 명령 전송 반복횟수

가 증가한 것을 알 수 있다. 순차적인 태그를 사용할 경우 리더가 PingID 명

령 전송시 같은 Bin 슬롯으로 응답하는 태그가 많기 때문에 하나의 태그 인

식 후 다시 처음부터 PingID 명령 전송을 반복하는 기존의 알고리즘의 경우

PingID 명령 전송 반복횟수가 현저히 증가하였다. 반면에 제안한 알고리즘의

39

경우에는 PingID 명령 전송 반복횟수가 줄어든 것을 알 수 있다. 제안한 알

고리즘의 경우 리더가 Bin 슬롯 정보를 기억하기 때문에 불필요한 PingID 명

령의 반복을 줄일 수 있다. 그리고 ScrollAllID 명령을 사용할 경우 리더는

충돌이 발생한 태그들의 ID bit의 충돌 정보를 알 수 있으므로, 최초 충돌이

발생한 위치부터 PingID 명령 전송을 시작하므로 순차적인 태그 ID를 사용

할 경우 PingID 명령 전송 반복횟수를 더 줄일 수 있다.

20 40 60 80 100 120 140 160 180 2000

500

1000

1500

2000

2500

사용된 태그의개수

Pin

gID

명령의반복횟수

EPC CLASS 1기존의 제안한알고리즘 using ScrollAllID제안한알고리즘

20 40 60 80 100 120 140 160 180 2005

10

15

20

25

30

35

40

45

50

그림 13. 충돌이 발생한 태그 개수에 따른 리더의 PingID 명령의 반복횟수

(순차적인 태그 ID 사용)

Fig. 13. The number of PingID command for the number of used tags (sequential tag ID)

40

그림 14는 위에서 비교한 세 알고리즘에 대해 순차적인 태그 ID를 사

용하였을 경우 충돌이 발생한 태그의 개수에 따른 리더의 태그인식시간을

나타내며 이는 시뮬레이션 결과이다. 그림 14에서 나타난 바와 같이 기존 알

고리즘은 순차적인 태그 ID를 사용하였을 경우 랜덤한 태그 ID를 사용하였

을 경우보다 태그인식시간이 증가하였다. 제안한 알고리즘은 순차적인 태그

ID를 사용하였을 경우 랜덤한 ID를 사용하였을 경우보다 200개의 충돌이 발

생한 태그에 대해서 태그인식시간에 있어 약 13% 정도 성능이 향상하였으며,

ScrollAllID 명령을 사용한 경우에는 약 16% 정도 성능이 향상되었다.

20 40 60 80 100 120 140 160 180 2000

1

2

3

4

5

6

사용된 태그의 개수

(sec

)태그인식시간

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

그림 14. 충돌이 발생한 태그 개수에 따른 리더의 태그인식시간 (순차적인 태그 ID 사용)

Fig. 14. Tag identification time for the number of used tags(sequential tag ID)

41

제６장 결론 본 논문에서는 RFID 시스템에서의 EPC CLASS 0 anti-collision 알고리즘

으로 Improved bit-by-bit 이진 트리 알고리즘을 제안하였고, 기존의 anti-

collision 알고리즘과 성능을 수학적으로 비교하고 분석하였으며 시뮬레이션

을 통하여 분석 결과를 검증하였다. 제안한 알고리즘은 사용된 태그의 수가

많아질수록 기존의 bit-by-bit 이진 트리 알고리즘보다 더 좋은 성능을 보이고

태그로부터 전송된 bit 수가 다른 방식에 비하여 가장 적다. 분석 결과에 의

하면 제안한 Improved bit-by-bit 이진 트리 알고리즘의 경우 bit-by-bit 이진 트

리 알고리즘과 비교할 때 사용된 태그의 개수가 총 태그 개수의 100%일 경

우에는 839%의 성능향상이 있음을 확인했다.

또한 EPC CLASS 1 UHF anti-collision 알고리즘의 성능을 분석하였고,

향상된 성능을 보이는 개선된 anti-collision 알고리즘을 제안하였다. 제안한

알고리즘은 수학적으로 성능을 분석하였으며, 시뮬레이션을 통해 그 수학적

분석의 결과를 검증하였다. 제안한 알고리즘은 기존 알고리즘보다 랜덤한 ID

를 갖는 태그를 사용했을 경우 충돌이 발생한 태그의 개수가 20개 일 때 약

1.7배의 성능 향상이 있었으며, 태그의 개수가 200개 일 때 약 2.3배의 성능

향상이 있었다. 현재 출시되고 있는 하나의 안테나와 리더에 의해서는 기존

알고리즘의 경우 초당 약 117개의 태그 인식이 가능하나 제안한 알고리즘의

경우 초당 약 252개의 태그 인식이 가능하므로 알고리즘의 성능이 월등히

향상된 것을 알 수 있다. 그리고 RFID 시스템에서는 순차적인 ID를 갖는 태

그들을 사용할 경우가 빈번히 발생한다. 그러한 경우에 기존 알고리즘을 사

42

용하면 PingID 명령의 많은 반복으로 인하여 알고리즘의 성능이 저하되나,

제안한 알고리즘을 사용할 경우 랜덤한 ID를 사용할 경우보다 약 13% 정도

성능이 향상하였으며, ScrollAllID 명령을 사용한 경우에는 약 16% 정도 성능

이 향상되었다. 따라서, 제안한 알고리즘들을 RFID 시스템에 적용한다면 같

은 시간 내에 더 많은 태그를 인식할 수 있으므로 RFID 시스템 성능 향상에

크게 기여할 수 있을 것이다.

43

참고 문헌

[1] H. Vogt, “Efficient Object Identification with Passive RFID

tags,” International Conference on Pervasive Computing, pp.98-113,

Zürich, 2002.

S. A. Weis, S. E. Sarma, R. L. Rivest and D. W. Engels, “Security and

Privacy Aspects of Low-Cost Radio Frequency Identification Systems,” First

International Conference on Security in Pervasive Computing, Mar. 2003.

[2]

[3] F. Zhou, D. Jin, C. Huang, and M. Hao, “Optimize the Power Consumption

of Electronic Passive Tags for Anti-collision Schemes,” IEEE, 2003.

H. Vogt, “Multiple Object Identification with Passive RFID Tags,” 2002

IEEE International Conference on Systems, Man and Cybernetics, vol.3,

pp.6-9, Oct. 2002.

[4]

ISO/IEC FDIS 18000-6:2003(E), Part 6: Parameters for Air nterface

Communications at 860-960 MHz, Nov. 2003.

[5]

D. W. Engels and S.E. Sarma, “The Reader Collision Problem,” 2002 IEEE

International Conference on Systems, Man and Cybernetics, vol.3, p.6, Oct.

2002.

[6]

S. Sarma, J. Waldrop, and D. Engels, “Colorwave : An Anti-collision

Algorithm for the Reader Collision Problem,” IEEE International

Conference on Communications, ICC ‘03, vol. 2, pp.1206-1210, May 2003.

[7]

[8] K. Finkenzeller, RFID Handbook;Fundamentals and Applications in

44

Contactless Smart Cards and Identification, Second Edition, John Wiley &

Sons Ltd, pp.195-219, 2003.

[9] J. L. Massey, “Collision Resolution Algorithms and Random-access

Communications,” University California, Los Angeles, Technical Report

UCLAENG -8016, Apr. 1980.

[10] Auto-ID Center, Draft Protocol Specification for a Class 0 Radio Frequency

Identification tag., Feb. 2003.

[11] M. Jacomet, A. Ehrsam, and U. Gehrig, “Contactless Identification Device

with Anticollision Algorithm,” IEEE Computer Society CSCC’99, Athens,

pp.269-273, Jul. 1999.

[12] H. S. Choi, J. R. Cha, and J. H. Kim, “Fast Wireless Anti-collision

Algorithm in Ubiquitous ID System,” in Proceeding IEEE Vehicular

Technology Conference 2004, L.A., USA, Sep. 2004.

[13] Auto-ID Center, 900 MHz ISM Band Class 1 Radio Frequency Identification

Tag Interface Specification : Candidate Recommendation, Version 1.0.0,

2003.

[14] EPC Global, EPCTM Tag Data Standards Version 1.1 Rev.1.24, Apr. 2004.

[15] H. S. Choi and J. H. Kim, “A Novel Tag identification algorithm for RFID

System using UHF,” Lecture Note on Computer Science 3824: Embedded

and Ubiquitous Computing-EUC 2005, pp. 629-638, Dec. 2005.

45

Abstract Anti-collision algorithm is very important in the RFID system, because it

decides tag identification time and tag identification accuracy. This thesis proposes and

analyzes Tag anti-collision algorithms in RFID system. We mathematically compare the

performance of the proposed algorithm for EPC CLASS 0 with existing binary

algorithms(binary search algorithm, slotted binary tree algorithm using time slot, and

bit-by-bit binary tree algorithm proposed by EPCglobal). We also validated analytic

results using OPNET simulation. Based on analytic result, comparing the proposed

Improved bit-by-bit binary tree algorithm with bit-by-bit binary tree algorithm which is

the best of existing algorithms, the performance of Improved bit-by-bit binary tree

algorithm is about 304% higher when the number of tags is 20, and 839% higher when

the number of tags is 200.

This thesis also proposes improved anti-collision algorithm for EPC CLASS 1

UHF tag. In the proposed algorithm, if the reader memorizes the Bin slot information, it

can reduce the repetition of the unnecessary PingID command and the time to identify

tags. If the reader also use ScrollAllID command in the proposed algorithm, the reader

knows the sequence of collided ID bits. Using this sequence, the reader can reduce the

repetition of PingID command and tag identification time. We analyze the performance

of the proposed anti-collision algorithm and compare the performance of the proposed

algorithms with that of the conventional algorithm. We also validate analytic results

using simulation. According to the analysis, for the random tag ID, comparing the

46

proposed algorithms with the conventional algorithm, the performance of the proposed

algorithms is about 130% higher when the number of the tags is 200. For the sequential

tag ID, the performance of the conventional algorithm decreases. On the contrary, the

performance of the proposed algorithm using ScrollAllID command is about 16%

higher than the case of using random tag ID.

47