KR100922393B1

KR100922393B1 - 무선 주파수 식별 시스템에서 태그 수 추정 방법 및 이를이용한 태그 인식 방법

Info

Publication number: KR100922393B1
Application number: KR1020070120468A
Authority: KR
Inventors: 엄준봉; 이태진
Original assignee: 성균관대학교산학협력단
Priority date: 2007-11-23
Filing date: 2007-11-23
Publication date: 2009-10-19
Anticipated expiration: 2027-11-23
Also published as: KR20090053577A; US8115602B2; US20090134975A1

Abstract

본 발명은 RFID 시스템에서 태그 수 추정 방법 및 이를 이용한 태그 인식 방법에 관한 것으로, 리더가 식별 가능 영역 내의 태그를 비트 마스크를 이용하여 적정 수의 그룹으로 분할하는 제1 단계; 상기 제1 단계에서 분할된 그룹 중 제1 그룹에 파일럿 프레임(L_p)을 적용하여 태그의 인식을 수행하는 제2 단계; 파일럿 프레임의 종료 후, 태그의 충돌확률을 계산하는 제3 단계; 태그의 충돌확률에 따라, 파일럿 프레임의 끝에 추가 타임슬롯(L_add)을 할당하거나 또는 새로운 프레임(L_l)을 생성하여, 파일럿 프레임 동안 인식되지 않은 제1 그룹의 태그를 인식하는 제4 단계를 구비하는 것을 특징으로 한다.

본 발명은 이와 같은 구성을 구비함으로써, 태그 수 추정에 소모되는 타임슬롯의 수를 현저하게 감소시키고 태그의 충돌을 효율적으로 방지할 수 있어, 고속의 태그 수 추정 및 태그 인식이 가능하다.

RFID, 파일럿 프레임, 비트 마스크, 태그 수 추정, 태그 인식

Description

무선 주파수 식별 시스템에서 태그 수 추정 방법 및 이를 이용한 태그 인식 방법{TAG ESTIMATION METHOD AND TAG IDENTIFICATION METHOD FOR RFID SYSTEM}

본 발명은 무선 주파수 식별(RFID) 시스템에서 태그 수 추정 방법 및 이를 이용한 태그 인식 방법에 관한 것으로, 보다 구체적으로는 식별 가능 영역 내의 태그를 몇 개의 그룹으로 나누어 고속으로 태그 수를 추정하고, 추정된 태그 수에 기초하여 효율적으로 태그의 충돌을 방지함으로써, 고속으로 태그를 인식할 수 있도록 하는 방법에 관한 것이다.

무선 주파수 식별(RFID)은 유비쿼터스(Ubiquitous) 컴퓨팅 시대의 핵심 기술 중 하나로서, 리더(Reader)와 태그(Tag) 사이의 무선통신을 통해서 각종 사물의 정보를 인식·처리하는 비 접촉식 시스템이다. 특히 RFID 시스템은 바코드(Barcode)와 달리 직접 접촉이나 스캐닝이 필요 없다는 장점이 있어, 현재 물류, 유통분야, 금융 서비스 등에서 사용중인 바코드를 대체할 기술로 인식될 정도로 산업계에서 사용이 증가하고 있다.

RFID 시스템에서는 태그에 저장된 정보를 판독하기 위하여, 리더가 식별 가능한 영역 내의 태그에 고유번호의 전송을 요청하면, 태그들이 이에 응답하여 자신의 고유번호를 리더에 전송하도록 동작한다. 그런데, 하나의 리더에 다수의 태그 정보가 전송될 경우 태그 간 충돌문제가 필연적으로 발생하게 된다. 즉, 하나의 태그가 자신의 정보를 리더로 전송할 때, 다른 태그가 동시에 동일한 리더로 자신의 정보를 전송하게 된다면 태그 간 충돌을 피할 수 없게 되는 것이다.

RFID 시스템에서 태그 간 충돌 문제는 리더가 태그를 신속하게 인식하는 것을 방해하여 시스템의 효율을 저하시키는 주된 요인이 되어 왔다. 더욱이, 현재 대부분의 시스템에 사용되고 있는 수동태그(Passive Tag)는 제한된 기능으로 인해 이러한 충돌문제를 스스로 해결할 수 없다. 따라서 태그 간 충돌문제를 어떻게 효율적으로 해결하느냐가 RFID 기술에서 중요한 이슈가 되었다.

종래 RFID 시스템에서 태그의 충돌 방지를 위한 프로토콜은 크게 알로하(ALOHA) 기반 프로토콜과 트리(Tree) 기반 프로토콜로 구별된다.

알로하 기반 프로토콜 중에서 가장 잘 알려진 기술은 프레임 알로하 방식(FSA: Framed-Slotted ALOHA)이다.

도 1a에 도시한 바와 같이, 기본 프레임 알로하 방식(BFSA: Basic Framed Slotted ALOHA)은 고정된 프레임 크기를 이용하여 태그들을 인식한다. 리더가 프레임 크기 및 랜덤 넘버와 같은 필요정보를 태그에 제공하면, 태그는 상기 정보를 수신한 후 프레임 내에 계산된 타임슬롯에 자신들의 고유번호를 전송한다. 이때 하나의 타임슬롯에서 태그 간 충돌이 발생하면, 충돌한 태그들은 다음 판독 프레임에서 자신들의 고유번호를 재전송하는 방식으로 태그인식이 수행된다. 이러한 BFSA는 태그 인식이 끝날 때까지 프레임 크기를 변경하지 않으므로 실행과정이 비교적 용이한 반면, 태그 수가 매우 많을 때에는 고정된 프레임의 대부분의 타임슬롯에서 충돌이 발생할 것이므로, 긴 시간 동안에도 태그들이 인식되지 않을 수 있는 문제가 있었다. 또한 프레임 내의 타임슬롯의 수가 태그 수보다 현저하게 큰 경우에는, 많은 타임슬롯들이 유휴 슬롯(idle slot)으로 낭비될 수 있다는 단점이 있다.

동적 프레임 알로하 방식(DFSA: Dynamic Framed-Slotted ALOHA)은, 효율적인 태그 인식을 위하여 리더가 태그 인식 전에 태그 수를 추정하여 그로부터 프레임 크기를 변화시킴으로써 상기 BFSA의 문제를 능동적으로 해결한다. 가장 단순한 DFSA는 충돌되는 타임슬롯의 수에 기초해서 프레임 크기를 변경한다. 즉, 리더는 충돌되는 타임슬롯의 수가 일정한 값보다 클 경우에는 다음 프레임에서 프레임 크기를 증가시키고, 반대로 충돌되는 타임슬롯의 수가 일정한 값보다 작을 경우에는 다음 프레임에서 프레임 크기를 감소시킨다. DFSA 방식에서는 프레임 크기가 태그 수와 같을 때 최적의 성능을 나타내는 것으로 알려졌지만, 태그 수가 최초 프레임 크기보다 더 클 경우에는 충돌확률이 커지기 때문에, 태그 수를 정확히 추정할 수 없게 되는 문제가 있었다.

트리(Tree) 기반의 RFID 프로토콜에서는 대부분 바이너리 트리 방식(Binary Tree Algorithms)을 사용한다. 도 1b에 바이너리 트리 방식을 예시로서 나타내었다. 바이너리 트리 방식에서는 하나의 타임슬롯에서 충돌이 발생되면, 충돌하는 태그들은 모든 태그들이 인식될 때까지 랜덤하게 두 개의 그룹으로 분리된다. 이와 같은 방식은, 리더가 적은 수의 태그들을 인식할 때는 매우 효율적이지만, 태그 수가 많을 때에는 초기 단계에서 많은 충돌 슬롯이 발생할 것이기 때문에, 모든 태그들이 인식될 때까지 타임슬롯의 소모가 심하다는 문제가 있다.

프레임 알로하 방식과 바이너리 트리 방식의 절충방식으로, 태그 추정과 바이너리 분할에 의한 프레임 알로하 방식(EBFSA: Framed-Slotted ALOHA with Tag Estimation and Binary Splitting)이 "Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection"(IEEE Communication Letters, vol.11, no.5, pp.452-454, 2007)에서 제시되었다. 도 1c에 종래 EBFSA 방식을 나타내었다. 도시된 바와 같이, EBFSA는 추정단계(Estimation Phase)와 인식단계(Identification Phase)로 구분된다. 리더는 추정단계에서 고정된 프레임 크기(L_est)를 사용하여 태그 추정을 수행하되, 충돌확률이 일정한 값을 초과하면 태그의 수를 정확히 추정할 수 없기 때문에, 비트마스크(bit mask)를 사용하여 태그의 수를 감소시킨다. 충돌확률이 일정한 값보다 낮아질 때까지 위 과정을 반복한다. 추정단계 후에 인식단계가 시작되는데, 인식단계의 최초 프레임 크기는 추정된 태그 수에 의해 결정된다. 한편 인식단계에서 하나의 타임슬롯에서 태그가 충돌되는 경우, 리더는 바이너리 트리 방식에 의해 충돌문제를 해결한다. EBFSA 방식은 프레임 알로하 기반의 프로토콜과 트리 기반의 프로토콜의 장점을 취해 성능을 향상시켰다는 평가를 받고 있지만, 여전히 태그 수 추정을 위해 부가적인 타임슬롯을 필요로 한다는 단점이 있었다.

본 발명은 상술한 바와 같은 문제점을 해결하기 위하여 안출된 것으로, 식별 가능 영역 내의 태그를 몇 개의 그룹으로 나누어 고속으로 태그 수를 추정하고, 추정된 태그 수에 기초하여 효율적으로 태그의 충돌을 방지함으로써, 태그 인식에 소요되는 타임슬롯의 수를 최소화하여 고속으로 태그를 인식할 수 있는 RFID 시스템에서 태그 수 추정 방법 및 이를 이용한 태그 인식 방법을 제공하는 것을 목적으로 한다.

상기 목적을 달성하기 위하여 본 발명에 의한 RFID 시스템에서 태그 수 추정 방법은, 리더가 식별 가능 영역 내의 태그를 적정 수의 그룹으로 분할하는 제1 단계; 상기 제1 단계에서 분할된 그룹 중 제1 그룹에 파일럿 프레임(L_p)을 적용하여 태그의 인식을 수행하는 제2 단계; 파일럿 프레임의 종료 후, 리더가 태그의 충돌확률(P_coll)을 계산하는 제3 단계; 및 상기 태그의 충돌확률(P_coll)에 따라, 파일럿 프레임의 끝에 추가 타임슬롯(L_add)을 할당하거나 또는 새로운 프레임(L_l)을 생성하여, 파일럿 프레임 동안 인식되지 않은 제1 그룹의 태그를 인식하는 제4 단계를 구비하는 것을 특징으로 한다.

또한, 상기 본 발명의 태그 수 추정 방법에 있어서, 상기 제1 단계에서 리더 는 비트 마스크를 이용하여 태그를 적정 수의 그룹으로 분할하는 것이 바람직하다.

또한, 상기 본 발명의 태그 수 추정 방법에 있어서, 상기 제2 단계는, 파일럿 프레임(L_p) 동안 태그의 충돌이 발생하는 경우, 파일럿 프레임에 남아 있는 타임슬롯의 수와 파일럿 프레임에서의 충돌 차수에 따라 충돌한 태그의 랜덤 카운터를 변경하고, 상기 랜덤 카운터의 값이 0이 되는 타임슬롯에서 태그의 고유번호가 전송되는 구성으로 이루어진다.

한편, 본 발명은 상기 제4 단계에서 추가 타임슬롯(L_add)이 할당된 경우, 타임슬롯(L_add)에서는 파일럿 프레(L_p)임에서와 연속하여 감해지는 태그들의 랜덤 카운터가 0이 될 때 태그에서 리더로 고유번호가 전송되되, 추가 타임슬롯(L_add)에서 충돌되는 태그들은 그 랜덤 카운터로 0 또는 1을 선택하고, 나머지 인식되지 않은 태그들은 랜덤 카운터 값을 1씩 증가시킨 후, 각 태그들의 랜덤 카운터 값을 순차적으로 감하여 카운터 값이 0이 되는 타임슬롯에서 각 태그들의 고유번호가 전송되도록 동작한다.

또한, 상기 제4 단계에서 새로운 프레임(L_l)이 생성된 경우, 새로운 프레임(L_l)에서는 파일럿 프레임(L_p)에서 인식되지 않은 태그들이 새로운 랜덤 카운터를 개시하여 랜덤 카운터 값이 0이 될 때 리더로 고유번호를 전송하되, 새로운 프레임(L_l)에서 충돌되는 태그들은 그 랜덤 카운터로 0 또는 1을 선택하고, 나머지 인식되지 않은 태그들은 랜덤 카운터 값을 1씩 증가시킨 후, 각 태그들의 랜덤 카운터 값을 순차적으로 감하여 카운터 값이 0이 되는 타임슬롯에서 각 태그들의 고유번호가 전송되도록 동작한다.

또한, 본 발명은 상기 목적을 달성하기 위하여, 상술한 본 발명의 태그 수 추정 방법을 이용하여, 리더가 식별 가능 영역 내의 태그를 비트 마스크를 이용하여 적정 수의 그룹으로 분할하는 제1 단계; 상기 제1 단계에서 분할된 그룹 중 제1 그룹에 파일럿 프레임(L_p)을 적용하여 태그의 인식을 수행하는 제2 단계; 파일럿 프레임의 종료 후, 리더가 태그의 충돌확률(P_coll)을 계산하는 제3 단계; 상기 태그의 충돌확률(P_coll)에 따라, 파일럿 프레임의 끝에 추가 타임슬롯(L_add)을 할당하거나 또는 새로운 프레임(L_l)을 생성하여, 파일럿 프레임 동안 인식되지 않은 제1 그룹의 태그를 인식하는 제4 단계; 상기 제2 내지 제4 단계를 거치면서 인식한 제1 그룹의 태그 수에 기초하여 최적의 프레임 크기(L_opt)를 결정하는 제5 단계; 상기 제5 단계에서 결정된 최적의 프레임 크기(L_opt)를 적용하여 제2 그룹의 태그를 인식하는 제6 단계; 및 제2 그룹 이후의 나머지 그룹에 대해서 순차로 태그 인식을 수행하되, 인식할 현재 그룹에는 상기 현재 그룹의 바로 이전 그룹에서 인식한 태그 수에 기초하여 결정된 최적의 프레임 크기(L_opt)를 적용하여, 상기 현재 그룹의 태그를 인식하는 제7 단계로 이루어지는 RFID 시스템에서 태그 인식 방법을 제공한다.

상기 본 발명에 의한 태그 인식 방법에 있어서, 상기 최적의 프레임 크기(L_opt)는,

(T: 태그인식에 필요한 타임슬롯의 총 수, n: 이전 그룹에서 인식된 태그 수, k: 하나의 타임슬롯에서 전송되는 태그 수, α_k: 충돌발생시 바이너리 트리방식에 의해 사용되는 타임슬롯 수의 평균값)의 식을 이전 그룹에서 인식된 태그 수(n)에 대해 미분하여 결정되는 것을 특징으로 한다. 바람직하게는, 상기 최적의 프레임 크기(L_opt)는 0.88n (n: 이전 그룹에서 인식된 태그 수)인 것을 특징으로 한다.

또한, 상기 본 발명에 의한 태그 인식 방법에 있어서, 상기 제6 단계 및 제7 단계에서 태그들은 랜덤 카운터 값이 0이 될 때 리더로 고유번호를 전송하되, 해당 프레임에서 충돌되는 태그들은 그 랜덤 카운터로 0 또는 1을 선택하고, 나머지 인식되지 않은 태그들은 랜덤 카운터 값을 1씩 증가시킨 후, 각 태그들의 랜덤 카운터 값을 순차적으로 감하여 카운터 값이 0이 되는 타임슬롯에서 각 태그들의 고유번호가 전송되는 것을 특징으로 한다.

본 발명의 RFID 시스템에서 태그 수 추정 방법에 의하면, 비트 마스크를 이용하여 태그를 몇 개의 그룹으로 분할한 후 파일럿 프레임을 적용함으로써, 태그 수 추정에 소모되는 타임슬롯의 수를 현저하게 감소시킬 수 있어 고속으로 태그 수를 추정할 수 있는 효과가 있다.

또한, 본 발명의 RFID 시스템에서 태그 인식 방법에 의하면, 고속으로 추정된 태그 수에 기초하여 최적의 프레임 크기를 결정하고 이를 분할된 후속그룹의 태그 인식에 적용함으로써, 태그의 충돌을 효율적으로 방지할 수 있어 고속의 태그 인식을 가능하게 하는 효과가 있다.

이하, 첨부되는 도면을 참조하여 본 발명의 실시예를 보다 구체적으로 설명한다. 먼저, 본 발명에서는 RFID 시스템에서 태그의 충돌을 방지하기 위하여 파일럿 프레임(Pilot Frame)에 의해 태그 수를 추정하고 이로부터 적절한 방식을 채택하여 DFSA 방식 및 바이너리 선택에 의해 태그를 인식하는 방법을 제시하였다. 따라서, 본 발명을 기술함에 있어서 본 발명의 태그 수 추정 방법 및 태그 인식 방법을, 파일럿 프레임에 의한 태그 추정 및 바이너리 선택에 의한 태그 인식을 채택한 프레임 알로하 방식(Framed-Slotted ALOHA with Estimation by Pilot Frame and Identification by Binary Selection), 즉, 간단히 'FSAPB 방식'이라고도 지칭하겠다.

본 발명의 일실시예에 의한 RFID 시스템에서 태그 수 추정 방법을 도 2의 순서도 및 도 4a 및 4b의 예시 도면을 참조하여 설명한다.

도 2에 도시된 바와 같이 본 발명에 의한 태그 수 추정 방법은, 식별할 태그를 적정한 수의 그룹으로 분할하는 제1 단계(S10); 분할된 그룹 중 제1 그룹에 파 일럿 프레임(L_p)을 적용하여 태그를 판독하는 제2 단계(S20); 파일럿 프레임의 종료 후, 리더가 태그의 충돌확률(P_coll)을 계산하는 제3 단계(S30); 및 상기 태그의 충돌확률(P_coll)에 따라, 파일럿 프레임 동안 인식되지 않은 제1 그룹의 태그를 인식하는 제4 단계(S40)로 이루어진다.

상기 제1 단계(S10)에서, 리더는 식별 가능 영역 내의 태그들을 비트 마스크(bit mask)를 이용하여 적정한 수(M)의 그룹으로 분할하도록 구성하는 것이 바람직하다. 먼저, 본 발명에서 태그들을 적정한 수(M)의 그룹으로 분할하는 이유는, 분할된 특정 그룹에 대해서만 태그 수 추정작업을 수행함으로써, 지나치게 많은 수의 태그에 대해 추정작업이 진행될 때 발생할 수 있는 태그 간 충돌로 인한 타임슬롯의 낭비를 방지할 수 있기 때문이다.

더욱이, 본 발명에서는 태그들을 균일하게 분할할 수 있는 비트 마스크를 이용함으로써, 특정 그룹에 대해 태그 수 추정이 이루어졌다면 나머지 다른 그룹의 태그 역시 균일한 랜덤 분포를 가정하여 태그 수를 예측할 수 있도록 한다. 설령 비트 마스크가 완전하게 균일한 랜덤 분포를 갖지 않는 경우를 가정하더라도, 비트 마스크를 사용함으로써 태그 수 추정에 낭비되는 타임슬롯의 수를 상당부분 감소시킬 수 있게 되는 이점이 있다. 한편, 상기 제1 단계에서 태그들을 너무 많은 그룹으로 분할할 경우, 각 그룹들 간 태그들은 균일 분포를 가지지 않을 수 있기 때문에, 상기 분할 그룹의 적정한 수(M)는 시뮬레이션을 통해 적절히 결정하는 것이 바람직하다.

다음으로 제2 단계(S20)에서, 리더는 상기 제1 단계에서 분할된 그룹 중 제1 그룹에 파일럿 프레임(L_p)을 적용하여 제1 그룹에 속한 태그들을 인식한다. 도 4a 및 도 4b를 참조하여 이를 구체적으로 살펴보면, 파일럿 프레임 동안 제1 그룹에 속한 모든 태그들은 리더의 요청에 응답하여 자신들의 고유번호를 전송하도록 동작한다. 즉, 태그들은 각자의 랜덤 카운터가 0이 되는 타임슬롯에서 자신들의 고유번호를 전송함으로써 리더에 인식된다.

한편, 파일럿 프레임(L_p) 동안 태그 간 충돌이 발생하여 태그 인식에 실패할 경우에는, 충돌한 태그의 랜덤 카운터를 해당 파일럿 프레임에 남아있는 타임슬롯의 수와 파일럿 프레임에서의 충돌 차수에 따라 변경하고, 다시 그 랜덤 카운터가 0이 되는 타임슬롯에서 고유번호를 재전송하도록 동작한다. 예컨대, 충돌 태그의 랜덤 카운터 값은 수학식 1에 의해 결정될 수 있다.

카운터

= L_p 에 남아 있는 타임슬롯의 수 + 2×(충돌차수-1) + rand(0 or 1)

파일럿 프레임에서 태그인식 프로세스가 완료되면, 제3 단계(S30)에서 리더는 태그의 충돌확률(P_coll)을 계산한다. 태그의 충돌확률(P_coll)은 파일럿 프레임에서 충돌이 발생한 타임슬롯의 수를 파일럿 프레임의 전체 타임슬롯의 수로 나눠줌으로써 계산될 수 있다.

다음으로, 상기 제4 단계(S40)는 파일럿 프레임 동안 태그 충돌로 인하여 인 식되지 않은 제1 그룹의 태그를 인식하는 단계이다. 구체적으로, 상기 제4 단계는, 파일럿 프레임의 종료 후 계산된 충돌확률(P_coll)을 비교값(P_th)과 비교한 후, 충돌확률(P_coll)이 비교값(P_th)보다 작은 경우에는 파일럿 프레임의 끝에 추가 타임슬롯(L_add)을 할당하여 태그를 인식하고, 충돌확률(P_coll)이 비교값(P_th)보다 큰 경우에는 파일럿 프레임 후에 새로운 프레임(L_l)을 생성하여 태그 인식을 수행하도록 구성된다.

충돌확률(P_coll)이 비교값(P_th)보다 작다는 것은, 하나의 타임슬롯에서 충돌되는 태그 수가 상대적으로 작다는 것을 의미하므로, 리더는 파일럿 프레임에서 충돌되는 태그들을 해결하기 위하여 파일럿 프레임의 끝에 추가 타임슬롯(L_add)을 할당한다. 상기 추가 타임슬롯(L_add)에서는, 파일럿 프레임(L_p)에서와 연속하여 감해지는 태그들의 랜덤 카운터가 0이 될 때 태그에서 리더로 고유번호가 전송된다. 이 과정에서 추가 타임슬롯(L_add)에서 충돌되는 태그들은 그 랜덤 카운터로 0 또는 1을 선택하고, 나머지 인식되지 않은 태그들은 랜덤 카운터 값을 1씩 증가시킨 후, 각 태그들의 랜덤 카운터 값을 순차적으로 감하여 카운터 값이 0이 되는 타임슬롯에서 각 태그들의 고유번호가 전송됨으로써 태그가 인식된다.

도 4a를 참조하여 추가 타임슬롯(L_add)에서의 태그인식 과정을 예시적으로 설명한다.

먼저, 리더는 파일럿 프레임(L_p) 동안 태그 1(Tag 1)과 태그 7(Tag 7)을 인식할 수 있다. 태그 2, 3, 5(Tag 2, Tag 3, Tag 5)는 파일럿 프레임에서 첫 번째 충돌을 일으키고, 태그 4, 6(Tag 4, Tag 6)은 파일럿 프레임에서 두 번째 충돌을 일으킨다. 그래서 충돌한 태그들의 랜덤 카운터를 수학식 1에 따라 변경하여, 파일럿 프레임의 끝에 할당된 추가 타임슬롯(L_add)에서 해결되도록 한다.

다음으로 추가 타임슬롯(L_add)에서는 바이너리 트리 방식에 의해 태그가 인식된다. 즉, 추가 타임슬롯(L_add)의 첫번째 슬롯에서 충돌하는 태그 2, 5(Tag 2, Tag 5)는 랜덤 카운터로 0 또는 1을 선택하고, 이 충돌로 인하여 나머지 다른 태그들은 그 카운터 값을 1씩 증가시킨다. 또한, 추가 타임슬롯(L_add)에서 충돌하는 태그 4, 6(Tag 4, Tag 6)도 랜덤 카운터로 0 또는 1을 선택하여, 그 값이 0일 때 고유번호를 전송한다.

한편, 충돌확률(P_coll)이 기준값(P_th) 보다 큰 경우는, 파일럿 프레임에 있는 대부분의 타임슬롯에서 충돌이 발생할 때이다. 이 경우에는 하나의 타임슬롯에서 충돌되는 태그 수 역시 많아질 것이므로, 리더는 파일럿 프레임의 끝에 추가 타임슬롯을 할당하는 방법보다는 새로운 프레임(L_l)을 적용하여 제1 그룹의 인식되지 않은 태그들이 인식되도록 구성한다. 상기 새로운 프레임(L_l)에서는, 파일럿 프레임에서 인식되지 않은 태그들이 새로운 랜덤 카운터를 개시하여 랜덤 카운터 값이 0이 될 때 리더로 고유번호를 전송하도록 동작한다. 이때, 새로운 프레임(L_l)에서 충돌되는 태그들은 그 랜덤 카운터로 0 또는 1을 선택하고, 나머지 인식되지 않은 태그들은 랜덤 카운터 값을 1씩 증가시킨 후, 각 태그들의 랜덤 카운터 값을 순차적으로 감하여 카운터 값이 0이 되는 타임슬롯에서 각 태그들의 고유번호를 전송함으로써 리더에 인식된다.

본 발명의 FSAPB 방식에서도, DFSA 방식에서 태그 수 추정에 사용하는 식을 파일럿 프레임(L_p)에 적용함으로써 태그 수를 추정할 수 있다. 즉, 본 발명에서는 다음의 수학식 2를 사용하여 태그 수를 추정할 수 있다.

(n: 태그의 수, L_p: 파일럿 프레임의 크기, P_coll: 충돌확률, P_idle: 유휴확률, P_succ: 성공확률)

한편, 상기 제4 단계(S40)에서 새로운 프레임의 크기는 상기 수학식 2에서 태그의 수 n을 새로운 프레임 크기 L_l로 대체함으로써 얻어질 수 있다. 즉, 본 발명에서는 제1 그룹에 적용된 파일럿 프레임의 크기(L_p)와 상기 제3 단계(S30)에서 계산된 충돌확률(P_coll)을 수학식 2에 대입하고 태그의 수 n=L_l로 함으로써 새로운 프 레임의 크기를 얻을 수 있다. 새로운 프레임(L_l)의 크기를 최적하게 설정하기 위하여, 태그 수(n)를 정확하게 추정할 필요는 없을 것이다. 왜냐하면 정확한 태그 수 추정에는 보다 많은 타임슬롯이 소모될 것이기 때문이다. 바람직하게는, 새로운 프레임의 크기는 파일럿 프레임에서 이미 판독에 성공한 태그와 최적의 프레임 크기를 고려하여 수학식 2를 충족하는 n의 최소값으로 설정된다.

도 4b를 참조하여 충돌확률(P_coll)이 비교값(P_th) 보다 큰 경우의 새로운 프레임(L_l)에서의 태그인식 과정을 예시적으로 설명한다.

먼저, 리더는 파일럿 프레임(L_p) 동안 태그 1(Tag 1)을 인식할 수 있다. 태그 1(Tag 1)을 제외한 나머지 태그들은 파일럿 프레임에서 충돌을 경험하고, 이들은 새로운 프레임(L_l)에서 각자의 고유번호를 다시 전송하게 된다.

새로운 프레임(L_l)의 진행과정에서는, 제3 타임슬롯에서 태그 4(Tag 4)와 태그 6(Tag 6)이 충돌한다. 충돌한 태그 4(Tag 4)와 태그 6(Tag 6)은 그들의 랜덤 카운터로 0 또는 1을 선택하고, 이 충돌로 인하여 나머지 인식되지 않은 태그들은 그 랜덤 카운터 값을 1씩 증가시킨다. 이런 방식으로 각각의 태그는 그 랜덤 카운터값이 0이 될 때 각자의 고유번호를 전송하도록 동작한다.

상술한 바와 같이, 본 발명의 FSAPB 방식에 의한 태그 수 추정 방법에서는, 리더가 식별 가능 영역에 있는 태그를 비트 마스크를 이용하여 분할하고, 분할된 특정 그룹에만 파일럿 프레임을 적용하여 태그인식을 수행하여 태그 수를 추정하도 록 함으로써, 태그 수 추정에 소모되는 타임슬롯의 수를 최소화할 수 있게 된다. 즉, 상기 제1 단계(S10) 내지 제4 단계(S40)의 프로세스를 통하여, 리더는 제1 그룹의 모든 태그들을 고속으로 인식할 수 있게 되며, 인식된 태그 수에 기초하여 후속 그룹의 태그 수를 예측할 수 있게 된다.

다음으로, 상술한 본 발명의 태그 수 추정 방법을 이용한 태그 인식 방법을 도 3의 순서도를 참조하여 설명한다.

도 3에 도시된 바와 같이, 본 발명에 의한 태그 인식 방법은, 리더가 식별할 태그를 비트 마스크를 이용하여 적정 수의 그룹으로 분할하는 제1 단계(S100); 분할된 그룹 중 제1 그룹에 파일럿 프레임(L_p)을 적용하여 태그를 인식하는 제2 단계(S200); 파일럿 프레임의 종료 후, 태그의 충돌확률(P_coll)을 계산하는 제3 단계(S300); 상기 태그의 충돌확률(P_coll)에 따라, 파일럿 프레임 동안 인식되지 않은 제1 그룹의 태그를 인식하는 제4 단계(S400); 상기 제1 그룹에서 인식한 태그 수에 기초하여 최적의 프레임 크기(L_opt)를 결정하는 제5 단계(S500); 결정된 최적의 프레임 크기(L_opt)를 적용하여 제2 그룹의 태그를 인식하는 제6 단계(S600); 및 모든 그룹의 태그를 인식할 때까지 태그 판독을 수행하되, 인식할 현재 그룹의 바로 이전 그룹에서 인식된 태그 수에 기초하여 결정된 최적의 프레임 크기(L_opt)를 적용하여, 현재 그룹의 태그를 인식하는 제7 단계(S700)로 구성된다.

상기 본 발명의 태그 인식 방법에서는 앞서 설명한 고속의 태그 수 추정 방법을 이용한다. 따라서, 상기 제1 단계(S100) 내지 제4 단계(S400)는 전술한 고속의 태그 수 추정을 위한 프로세스와 동일하므로, 그 구체적인 설명을 생략한다.

한편, 상기 제5 단계(S500)에서는, 리더가 상기 제2 단계 내지 제4 단계를 거치면서 인식한 제1 그룹의 태그 수에 기초하여 최적의 프레임 크기(L_opt)를 결정한다. 일반적으로 DFSA 방식의 경우에는, 프레임 크기가 태그 수와 동일할 때 시스템 효율이 최적한 것으로 알려져 있다. 그러나 도 5a의 그래프(태그 수가 100개인 경우, 프레임 크기에 따라 필요한 타임슬롯의 수를 대응시킨 그래프)가 나타내고 있는 바와 같이, 본 발명은 DFSA 방식을 일부 이용하고 있기는 하지만, 최적의 프레임 크기는 태그 수와 동일하지 않음을 알 수 있다. 따라서, 본 발명에서는 "Analysis of contention Tree Algorithms"(IEEE Trans. on Information Theory, vol.46, no.6 pp.2163-2172, Sep. 2000)에서 제시된 식을 이용하여 최적의 프레임 크기(L_opt)를 결정한다.

(T: 태그인식에 필요한 타임슬롯의 총 수, n: 이전 그룹에서 인식된 태그 수, k: 하나의 타임슬롯에서 전송되는 태그 수, α_k: 충돌발생시 바이너리 트리방식에 의해 사용되는 타임슬롯 수의 평균값)

상기 수학식 3에서 최적의 프레임 크기(L_opt)는 수학식 3을 미분하여 그 결과를 0으로 하는 값이 된다. 다양한 n값에 대해 수학식 3을 미분하는 것은 매우 어렵지만, 도 5b의 그래프(태그 수 n에 따라 1/L_opt의 값을 대응시킨 그래프)를 통해서 최적의 프레임 크기(L_opt)는 대략 0.88n(n: 이전 그룹에서 인식된 태그 수)임을 얻을 수 있다. 도 5b의 그래프는 k값이 커지면 태그 수 n에 따른 1/L_opt의 값이 k값에 영향받지 않음을 보여준다. 따라서, 수학식 3을 특정 범위의 k에 대해서만 미분하는 것이 가능하며, 이 때문에 본 발명에서 최적의 프레임 크기(L_opt)는 상기한 바와 같이 태그의 수(n)에 특정 상수(γ=0.88)가 곱해져야 한다.

상술한 제5 단계(S500)를 통하여 제1 그룹에서 인식한 태그 수에 기초하여 최적의 프레임 크기(L_opt)를 결정한 다음에는, 결정된 최적의 프레임 크기(L_opt)를 적용하여 후속 그룹인 제2 그룹의 태그를 인식하는 제6 단계(S600)를 수행한다.

본 발명에서는 비트 마스크가 태그들을 균일한 분포로 분할하는 특성을 이용하므로, 일단 리더가 제1 그룹에서 태그들을 모두 인식한 후에는, 나머지 다른 그룹에 대해서는 더 이상 파일럿 프레임을 적용하여 태그 수 추정작업을 수행할 필요가 없게 된다. 즉, 제2 그룹은 제1 그룹에서와 동일한 태그 수를 갖는 것으로 전제할 수 있으며, 제1 그룹에서 인식한 태그 수에 기초하여 결정된 최적의 프레임 크기(L_opt)를 적용하여 제2 그룹의 태그를 인식한 후에는, 다시 제2 그룹에서 인식한 태그 수에 기초하여 결정된 최적의 프레임 크기(L_opt)를 적용하여 후속 그룹인 제3 그룹의 태그인식 작업을 수행하도록 동작한다.

상기한 바와 같이, 현재 그룹에 적용할 최적의 프레임 크기(L_opt)를 이전 그룹에서 인식된 태그들의 수에 기초하여 결정하는 방식으로, 제7 단계(S700)에서는 제2 그룹 이후의 나머지 그룹들에 대해서 모든 태그들이 인식될 때까지 최적의 프레임 크기를 적용하여 태그 인식 작업을 반복하도록 이루어진다.

일단 최적의 프레임 크기가 정해지면, 제2 그룹을 포함한 나머지 그룹들에 대한 태그 인식작업은 바이너리 트리 방식에 의해 진행된다. 즉, 적용된 프레임 내에서 각 그룹에 속하는 태그들은 그 랜덤 카운터 값이 0이 될 때 리더로 고유번호를 전송하되, 해당 프레임에서 충돌되는 태그들은 그 랜덤 카운터로 0 또는 1을 선택하고, 나머지 인식되지 않은 태그들은 랜덤 카운터 값을 1씩 증가시킨 후, 각 태그들의 랜덤 카운터 값을 순차적으로 감하여 카운터 값이 0이 되는 타임슬롯에서 그 고유번호를 전송하는 방식으로 태그가 인식된다.

상술한 바와 같이, 본 발명에 의한 태그 인식 방법에서는, 파일럿 프레임을 이용한 고속의 태그 추정 방법을 이용하여, 제1 그룹 이후의 후속 그룹들에 대해서는 타임슬롯의 낭비 없이 이전 그룹에서 인식된 태그 수에 기초하여 현재 그룹의 태그 수를 예측한다. 그 다음, 예측된 태그 수로부터 최적의 프레임 크기를 계산하고, 이에 따라 프레임 크기를 변경하여 태그 인식을 수행함으로써, 효율적으로 태그의 충돌을 방지하여 태그 인식에 소요되는 전체 타임슬롯의 수를 최소화하여 고속의 태그 인식을 행한다.

종래의 충돌 방지 기술에 대한 본 발명의 우위는 다음의 시뮬레이션 결과를 통하여 더욱 명백히 확인된다. 본 시뮬레이션에서는 본 발명에 의한 FSAPB 방식이 적용된 시스템의 성능을 DFSA 방식, 바이너리 트리 방식 및 EB-FSA 방식을 각각 적용한 시스템의 성능과 비교하였다. 시뮬레이션 조건으로는, 하나의 리더가 모든 태그들을 판독하고, 태그 수를 100에서 1000까지 증가시키는 것으로 하였다. 또한, 본 발명에 의한 FSAPB 방식에서는 L_p =36, P_th =0.6, M=4로 설정하였고, EB-FSA 방식에 의한 시스템에서는 "Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection"(IEEE Communication Letters, vol.11, no.5, pp.452-454, 2007)에 언급된 조건을 참조하였다 또한, DFSA 방식에 의한 시스템에서는 최초의 태그 수는 알려져 있고 추정된 태그 수는 매우 정확한 것으로 가정하였다.

도 6a는 본 시뮬레이션의 결과에 따라, 변화하는 태그 수에 대한 태그 수 추정에 소모되는 타임슬롯의 수를 대응시킨 그래프이다. 도 6a에 도시된 바로부터, 본 발명이 적용된 시스템에서는 EB-FSA 방식보다 태그 수 추정에 훨씬 적은 타임슬롯을 사용함을 알 수 있다. 본 발명이 적용된 시스템의 그래프에서 태그 수 n=200 인 지점에 불연속성이 나타나는 이유는, 태그 수 n=200 보다 적을 때에는 L_p 에서 충돌확률(P_coll)이 비교값(P_th)보다 작아 추가 타임슬롯(L_add)을 사용하여 나머지 태그를 인식하게 되지만, 태그 수 n=300 내지 1000 일 때는 L_p 내에서 태그의 충돌이 많아지므로 새로운 프레임(L_l)을 적용하여 나머지 태그를 인식하기 때문이다. 더욱이, 본 발명의 FSAPB 방식에 의하면 태그 수가 100에서 1000개까지 변화하는 전 과정을 통하여, 태그 수 추정에 소모되는 타임슬롯의 수는 파일럿 프레임의 크기(L_p = 36) 보다도 작은 반면, EB-FSA 방식은 태그 수가 많아질수록 많은 수의 타임슬롯이 태그 수 추정에서 소모됨을 알 수 있다. 예로서, 태그 수 n=1000 일 때, EB-FSA 방식은 본 발명의 FSAPB 방식보다 5.5배의 타임슬롯을 필요로 한다.

다음으로, 도 6b에는 태그 수에 따라 태그의 인식에 사용되는 타임슬롯의 수를 대응시킴으로써, 본 발명에 의한 FSAPB 방식과 종래의 EB-FSA 방식, DFSA 방식 및 바이너리 트리 방식의 성능을 비교하였다. 도시된 바와 같이, 태그 수가 작을 때는 대부분의 방식이 거의 비슷한 성능을 나타내지만, 태그 수가 커짐에 따라 본 발명에 의한 FSAPB 방식이 더욱 효율적임을 알 수 있다. 예컨대, 태그 수가 1000 개 일 때, EB-FSA 방식, DFSA 방식 및 바이너리 트리 방식은 본 발명에서보다 각각 약 7.3%, 14.7%, 21.9%의 타임슬롯을 더 많이 사용함을 알 수 있다.

이상에서는 본 발명을 특정의 바람직한 실시예에 대해서 도시하고 설명하였다. 그러나, 본 발명은 상술한 실시예에 국한되는 것은 아니며, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자라면 다음의 청구범위에 기재된 본 발명의 기술적 사상을 벗어남이 없이 얼마든지 다양하게 변경실시할 수 있을 것이다.

도 1a 내지 도 1c는 종래의 태그 충돌 방지를 위한 BFSA 방식, 바이너리 트리 방식 및 EB-FSA 방식의 동작 과정을 각각 예시적으로 나타내는 도면,

도 2는 본 발명의 실시예에 따른 RFID 시스템에서 태그 수 추정 방법을 나타내는 순서도,

도 3은 본 발명의 실시예에 따른 RFID 시스템에서 태그 인식 방법을 나타내는 순서도,

도 4a 및 도 4b는 본 발명의 실시예에 따른 RFID 시스템에서 태그 수 추정 방법의 동작과정을 예시적으로 나타내는 도면,

도 5a는 본 발명이 적용된 RFID 시스템에서, 태그 수가 100개인 경우 필요한 타임슬롯의 수를 프레임 크기에 따라 대응시킨 그래프,

도 5b는 본 발명이 적용된 RFID 시스템에서, 1/L_opt의 값을 태그 수에 따라 대응시킨 그래프,

도 6a은 본 발명에 의한 태그 수 추정 방법과 EB-FSA 방식의 성능을 비교하기 위하여, 태그 수에 따라 태그 수 추정에 소모되는 타임슬롯의 수를 대응시킨 그래프,

도 6b는 본 발명에 의한 태그 인식 방법과 종래 방식의 성능을 비교하기 위하여, 태그 수에 따라 태그의 인식에 사용되는 타임슬롯의 수를 대응시킨 그래프.

Claims

리더가 식별 가능 영역 내의 태그를 적정 수의 그룹으로 분할하는 제1 단계;

상기 제1 단계에서 분할된 그룹 중 제1 그룹에 파일럿 프레임(L_p)을 적용하여 태그의 인식을 수행하는 제2 단계;

파일럿 프레임의 종료 후, 리더가 태그의 충돌확률(P_coll)을 계산하는 제3 단계; 및

상기 태그의 충돌확률(P_coll)에 따라, 파일럿 프레임의 끝에 추가 타임슬롯(L_add)을 할당하거나 또는 새로운 프레임(L_l)을 생성하여, 파일럿 프레임 동안 인식되지 않은 제1 그룹의 태그를 인식하는 제4 단계를 구비하는 것을 특징으로 하는 RFID 시스템에서 태그 수 추정 방법.
제1 항에 있어서,

상기 제1 단계에서 리더는 비트 마스크를 이용하여 태그를 적정 수의 그룹으로 분할하는 것을 특징으로 하는 RFID 시스템에서 태그 수 추정 방법.
제2 항에 있어서,

상기 제2 단계는, 파일럿 프레임(L_p) 동안 태그의 충돌이 발생하는 경우, 파일럿 프레임에 남아 있는 타임슬롯의 수와 파일럿 프레임에서의 충돌 차수에 따라 충돌한 태그의 랜덤 카운터를 변경하고, 상기 랜덤 카운터의 값이 0이 되는 타임슬롯에서 태그의 고유번호가 전송되는 것을 특징으로 하는 RFID 시스템에서 태그 수 추정 방법.
제3 항에 있어서,

상기 파일럿 프레임(L_p) 동안 충돌한 태그의 랜덤 카운터는,

카운터 = 파일럿 프레임에 남아 있는 타임슬롯의 수＋2×(충돌 차수－1)＋rand(0 or 1)의 계산 값에 따라 변경되는 것을 특징으로 하는 RFID 시스템에서 태그 수 추정 방법.
제4 항에 있어서,

상기 제4 단계는 태그의 충돌확률(P_coll)을 비교값(P_th)과 비교하는 단계를 추가로 구비하며, 상기 비교 결과,

충돌확률(P_coll)이 비교값(P_th)보다 작은 경우, 파일럿 프레임의 끝에 추가 타 임슬롯(L_add)을 할당하여 파일럿 프레임에서 인식되지 않은 제1 그룹의 태그를 인식하고,

충돌확률(P_coll)이 비교값(P_th)보다 큰 경우, 파일럿 프레임의 뒤에 새로운 프레임을 생성하여 파일럿 프레임에서 인식되지 않은 제1 그룹의 태그를 인식하는 것을 특징으로 하는 RFID 시스템에서 태그 수 추정 방법.
제5 항에 있어서,

상기 추가 타임슬롯(L_add)에서는,

파일럿 프레임(L_p)에서와 연속하여 감해지는 태그들의 랜덤 카운터가 0이 될 때 태그에서 리더로 고유번호가 전송되되,

추가 타임슬롯(L_add)에서 충돌되는 태그들은 그 랜덤 카운터로 0 또는 1을 선택하고, 나머지 인식되지 않은 태그들은 랜덤 카운터 값을 1씩 증가시킨 후, 각 태그들의 랜덤 카운터 값을 순차적으로 감하여 카운터 값이 0이 되는 타임슬롯에서 각 태그들의 고유번호가 전송되는 것을 특징으로 하는 RFID 시스템에서 태그 수 추정 방법.
제6 항에 있어서,

상기 새로운 프레임(L_l)에서는,

파일럿 프레임(L_p)에서 인식되지 않은 태그들이 새로운 랜덤 카운터를 개시하여 랜덤 카운터 값이 0이 될 때 리더로 고유번호를 전송하되,

새로운 프레임(L_l)에서 충돌되는 태그들은 그 랜덤 카운터로 0 또는 1을 선택하고, 나머지 인식되지 않은 태그들은 랜덤 카운터 값을 1씩 증가시킨 후, 각 태그들의 랜덤 카운터 값을 순차적으로 감하여 카운터 값이 0이 되는 타임슬롯에서 각 태그들의 고유번호가 전송되는 것을 특징으로 하는 RFID 시스템에서 태그 수 추정 방법.
제7 항에 있어서,

상기 새로운 프레임(L_l)의 크기는,

(n: 태그의 수, L_p: 파일럿 프레임의 크기, P_coll: 충돌확률, P_idle: 유휴확률, P_succ: 성공확률)의 식을 충족하는 n의 최소값으로 결정되는 것을 특징으로 하는 RFID 시스템에서 태그 수 추정 방법.
리더가 식별 가능 영역 내의 태그를 비트 마스크를 이용하여 적정 수의 그룹으로 분할하는 제1 단계;

상기 제1 단계에서 분할된 그룹 중 제1 그룹에 파일럿 프레임(L_p)을 적용하여 태그의 인식을 수행하는 제2 단계;

파일럿 프레임의 종료 후, 리더가 태그의 충돌확률(P_coll)을 계산하는 제3 단계;

상기 태그의 충돌확률(P_coll)에 따라, 파일럿 프레임의 끝에 추가 타임슬롯(L_add)을 할당하거나 또는 새로운 프레임(L_l)을 생성하여, 파일럿 프레임 동안 인식되지 않은 제1 그룹의 태그를 인식하는 제4 단계;

상기 제2 내지 제4 단계를 거치면서 인식한 제1 그룹의 태그 수에 기초하여 최적의 프레임 크기(L_opt)를 결정하는 제5 단계;

상기 제5 단계에서 결정된 최적의 프레임 크기(L_opt)를 적용하여 제2 그룹의 태그를 인식하는 제6 단계; 및

제2 그룹 이후의 나머지 그룹에 대해서 순차로 태그 인식을 수행하되, 인식할 현재 그룹에는 상기 현재 그룹의 바로 이전 그룹에서 인식한 태그 수에 기초하 여 결정된 최적의 프레임 크기(L_opt)를 적용하여, 상기 현재 그룹의 태그를 인식하는 제7 단계를 구비하는 것을 특징으로 하는 RFID 시스템에서 태그 인식 방법.
제9 항에 있어서,

상기 최적의 프레임 크기(L_opt)는,

(T: 태그인식에 필요한 타임슬롯의 총 수, n: 이전 그룹에서 인식된 태그 수, k: 하나의 타임슬롯에서 전송되는 태그 수, α_k: 충돌발생시 바이너리 트리방식에 의해 사용되는 타임슬롯 수의 평균값)의 식을 이전 그룹에서 인식된 태그 수(n)에 대해 미분하여 결정되는 것을 특징으로 하는 RFID 시스템에서 태그 인식 방법.
제10 항에 있어서,

상기 최적의 프레임 크기(L_opt)는 0.88n (n: 이전 그룹에서 인식된 태그 수)인 것을 특징으로 하는 RFID 시스템에서 태그 인식 방법.
제11 항에 있어서,

상기 제6 단계 및 제7 단계에서,

태그들은 랜덤 카운터 값이 0이 될 때 리더로 고유번호를 전송하되, 해당 프레임에서 충돌되는 태그들은 그 랜덤 카운터로 0 또는 1을 선택하고, 나머지 인식되지 않은 태그들은 랜덤 카운터 값을 1씩 증가시킨 후, 각 태그들의 랜덤 카운터 값을 순차적으로 감하여 카운터 값이 0이 되는 타임슬롯에서 각 태그들의 고유번호가 전송되는 것을 특징으로 하는 RFID 시스템에서 태그 인식 방법.