[논문]RFID시스템에서 슬롯의 혼잡도를 이용한 DFS-ALOHA 알고리즘

이재구; 최승식

doi:10.3745/kipstc.2009.16-c.2.267

RFID시스템에서 슬롯의 혼잡도를 이용한 DFS-ALOHA 알고리즘
A DFS-ALOHA Algorithm with Slot Congestion Rates in a RFID System 원문보기

정보처리학회논문지. The KIPS transactions. Part C Part C, v.16C no.2, 2009년, pp.267 - 274

이재구 ((주)이노와이어리스 정보통신연구소) , 최승식 (인천대학교 컴퓨터공학과)

초록
AI-Helper

RFID 리더기가 영역내의 다수의 태그를 인식할 때 태그간의 통신간섭에 의해 태그인식이 방해 받는다. 이를 피하기 위해서는 충돌방지 알고리즘이 필요하게 된다. 충돌방지 알고리즘은 크게 슬롯 알로하 기반 알고리즘과 트리기반 알고리즘으로 나뉜다. 본 논문은 ISO 18000-6 TYPE A에 정의된 알로하 기반의 Framed Slotted ALOHA(FSA) 알고리즘에 태그와 슬롯간의 혼잡도를 이용하여 성능을 개선한 Dynamic Framed Slotted ALOHA-Slot Congestion(DFSA-SC) 알고리즘을 제안한다. 시뮬레이션 결과 최초 태그 수 추정의 정확도를 높여 전체 태그인식 시간이 줄어든 것을 확인 할 수 있었다. 나아가 태그 아이디의 중복성이 클 경우 대표적인 트리기반 알고리즘인 Query Tree 알고리즘보다 제안된 알고리즘이 우수한 것을 확인 할 수 있었다.

Abstract ▼ AI-Helper

For the implementation of a RFID system, an anti-collision algorithm is required to identify multiple tags within the range of a RFID Reader. There are two methods of anti-collision algorithms for the identification of multiple tags, conclusive algorithms based on tree and stochastic algorithms based on slotted ALOHA. In this paper, we propose a Dynamic Framed Slotted ALOHA-Slot Congestion(DFSA-SC) Algorithm. The proposed algorithm improves the efficiency of collision resolution. The performance of the proposed DFSA-SC algorithm is showed by simulation. The identification time of the proposed algorithm is shorter than that of the existing DFSA algorithm. Furthermore, when the bit duplication of the tagID is higher, the proposed algorithm is more efficient than Query Tree algorithm.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 기존 DFSA의 성능을 개선한 Dynamic Framed Slotted ALOHA-Slot Congestion (DFSA-SC) 알고리즘을 제안한다. 본 논문에서 제안하는 알고리즘들은 기존 DFSA 알고리즘에 슬롯-태그 간의 혼잡도를 이용하여 다음 단계의 슬롯 수를 변화 시키는 방법을 통해 성능을 개선하는 방안이다. 시뮬레이션을 통한 검증결과 사용되는 총 슬롯수를 감소시켜 태그 인식 시간의 단축은 물론 기존 DFSA 알고리즘보다 더 높은 성능을 확인할 수 있었다.
본 논문은 ISO 18000-6 TYPE A에 정의된 FSA 알고리즘을 기반으로 성능을 개선한 DFSA-SC 알고리즘을 제안하였다. 본 논문에서는 기존 DFSA 알고리즘의 태그수 추정의 복잡도를 개선하고 충돌 슬롯의 수와 최초 태그 인식 과정에서의 혼잡도를 이용하여 성능을 개선하였다. 시뮬레이션 결과 제안된 DFSA-SC 알고리즘이 다른 알고리즘에 비해 보다 우수한 성능을 보이고 있음을 확인 할 수 있었다.
FSA알고리즘의 문제점을 해결하기 위해 여러 가지의 Dynamic Framed Slotted ALOHA(DFSA) 알고리즘들에 대한 연구가 진행되어 왔다[2-4]. 본 논문에서는 기존 DFSA의 성능을 개선한 Dynamic Framed Slotted ALOHA-Slot Congestion (DFSA-SC) 알고리즘을 제안한다. 본 논문에서 제안하는 알고리즘들은 기존 DFSA 알고리즘에 슬롯-태그 간의 혼잡도를 이용하여 다음 단계의 슬롯 수를 변화 시키는 방법을 통해 성능을 개선하는 방안이다.
본 논문은 ISO 18000-6 TYPE A에 정의된 FSA 알고리즘을 기반으로 성능을 개선한 DFSA-SC 알고리즘을 제안하였다. 본 논문에서는 기존 DFSA 알고리즘의 태그수 추정의 복잡도를 개선하고 충돌 슬롯의 수와 최초 태그 인식 과정에서의 혼잡도를 이용하여 성능을 개선하였다.
본 절에서는 리더범위 내의 태그 수에 따라 최적의 프레임 크기의 관계를 구하도록 한다. DFSA 알고리즘에서 가변적인 프레임 크기를 설정함에 있어 매우 중요한 관계라 할 수 있다.
하지만 기존 알고리즘들은 이를 전혀 고려하지 못한다. 이에 본 논문은 기존에 연구되었던 DFSA 알고리즘에 최초 단계에서의 슬롯과 태그사이의 혼잡도를 감안하여 슬롯 혼잡도를 이용한 DFSA-SC 알고리즘을 제안한다.
따라서 실제 태그 수와 추정한 태그 수와의 차이가 가장 큰 단계이다. 이에 본 논문은 최초 단계에서의 슬롯과 태그사이의 혼잡도를 감안하여 보다 빠르게 리더 범위내 태그 수를 추정하는 방법을 제안한다. 첫 단계에서의 슬롯과 태그사이의 혼잡도가 높아질 수 록 실제 태그의 수가 기하급수적으로 증가하는 것을 식(1)에서 알 수 있다.

가설 설정

식(10)에서 정의한 상수 C는 2로 설정하였다. Query Tree algorithm[6]의 경우 태그ID 길이는 96bit로 태그ID가 순차적인 경우로 가정하였으며 질의-응답의 한 사이클의 시간은 하나의 슬롯 타임과 같다고 가정하였다.
Vogt 알고리즘은 충돌 슬롯 수를 이용하여 성능을 개선하였다. 하지만 Vogt 알고리즘은 충돌의 발생을 단순히 두개의 태그에 의해서만 충돌이 발생하는 것으로 가정하였다. 하지만 실제로 충돌은 2개 이상의 태그에 의해서 발생함으로 완벽한 접근법이라 할 수 없다.

제안 방법

인식된 태그는 다음 단계에서 응답하지 않도록 Inactive 상태로 설정하게 된다. 두 번째 리더의 요청명령에 인식되지 않은 태그들은 다시 랜덤하게 슬롯을 선택하여 응답 하였다. 이때 첫 번째 슬롯은 어떠한 태그도 응답하지 않은 슬롯으로 Idle 슬롯이라 하며 Idle 슬롯이 발생하는 현상을 슬롯낭비현상이라 한다.
본 절에서는 지금까지 살펴본 알고리즘들과 제안된 알고리즘에 대한 성능평가를 실시한다. 성능 평가를 위한 시뮬레이션 환경은 C언어를 기반으로 설계하였다.
본 절에서는 지금까지 살펴본 알고리즘들과 제안된 알고리즘에 대한 성능평가를 실시한다. 성능 평가를 위한 시뮬레이션 환경은 C언어를 기반으로 설계하였다. 성능 측정 기준은 모든 태그를 인식하기까지 사용된 총 슬롯의 수로 하였다.
성능 측정 기준은 모든 태그를 인식하기까지 사용된 총 슬롯의 수로 하였다. 실험값은 최초 슬롯수를 8, 16, 32, 64, 128의 각각의 경우에 태그 수를 10개부터 100개까지 10개씩 증가 시키며 100번 반복 후 평균값으로 하였다. 식(10)에서 정의한 상수 C는 2로 설정하였다.
리더의 요청명령과 요청명령 사이의 간격을 리드 사이클이라고 한다. 첫 번째 리드사이클에서 태그1은 슬롯 1을 태그 2,3,4는 슬롯 2를 태그 5,6은 슬롯 3을 선택하여 자신의 태그ID를 전송하였다. 따라서 태그 1은 인식되었고 태그 2,3,4,5,6은 인식되지 않았다.

이론/모형

이곳은 MIT의 Auto-ID 센터에서 RFID 기술 보급 및 활성화를 추진하기 위한 비영리단체로써 사실상 이곳에서 표준화를 주도하고 있으며 EPCglobal Class0과 Class1 규격이 표준으로 확정되었다. 이 중에서 ISO/IEC 18000-6 Type A와 EPC Class 1에서는 Framed Slotted ALOHA(FSA) 알고리즘이 사용되었으며 ISO/IEC 18000-6 Type B와 EPC Class 0에서는 이진트리 알고리즘이 사용되었다[1,6].

성능/효과

3.1절에서 살펴보았듯이 FSA 알고리즘은 DFSA알고리즘에 비해 더 좋은 성능을 나타 낼 수 없으며 DFSA 알고리즘에서 가장 높은 성능을 기대할 수 있는 프레임의 크기는 리더 범위 내 인식할 태그 수와 일치할 때이다. 따라서 본 논문에서 제안하는 DFSA-SC 알고리즘은 리더범위 내 태그 수를 빠르게 찾기 위한 방법이다.
두 번째 단계에서의 프레임의 크기는 8로 설정되었다. 기존의 알고리즘에 비해 본 논문에서 제안한 DFSA-CS 알고리즘이 보다 빠른 태그 수를 추정하여 성능이 개선된 것을 확인 할 수 있다. 제안된 알고리즘의 특성상 태그 수에 비해 슬롯의 수가 적을 경우 보다 큰 성능을 기대할 수 있으며 태그 수에 비해 프레임의 크기가 큰 경우는 혼잡도 값이 작아지기 때문에 슬롯 낭비 현상을 피할 수 있다.
하지만 제안된 알고리즘의 혼잡도는 최초 단계에서의 충돌이 많이 발생하면 커지고 충돌이 적으면 적어지는 구조이기 때문에 최초 단계에서의 충돌이 적다하더라도 슬롯이 낭비되는 현상을 방지 할 수 있다. 또한 Query Tree는 대표적인 트리기반 알고리즘으로 태그ID가 순차적인 경우 제안된 알고리즘이 우수한 성능을 나타내는 것을 확인 할 수 있다. 특히 태그수가 적을수록 더 좋은 성능을 나타낸다.
시뮬레이션 결과 제안된 DFSA-SC 알고리즘이 다른 알고리즘에 비해 보다 우수한 성능을 보이고 있음을 확인 할 수 있었다. 또한 대표적인 트리기반의 알고리즘인 Query Tree 알고리즘과의 비교실험을 통해 알로하 기반의 알고리즘이 태그수가 적고 ID의 중복성이 클 경우 트리기반 알고리즘보다 높은 성능을 기대 할 수 있다는 것을 확인 할 수 있었다.
본 논문에서는 기존 DFSA 알고리즘의 태그수 추정의 복잡도를 개선하고 충돌 슬롯의 수와 최초 태그 인식 과정에서의 혼잡도를 이용하여 성능을 개선하였다. 시뮬레이션 결과 제안된 DFSA-SC 알고리즘이 다른 알고리즘에 비해 보다 우수한 성능을 보이고 있음을 확인 할 수 있었다. 또한 대표적인 트리기반의 알고리즘인 Query Tree 알고리즘과의 비교실험을 통해 알로하 기반의 알고리즘이 태그수가 적고 ID의 중복성이 클 경우 트리기반 알고리즘보다 높은 성능을 기대 할 수 있다는 것을 확인 할 수 있었다.
본 논문에서 제안하는 알고리즘들은 기존 DFSA 알고리즘에 슬롯-태그 간의 혼잡도를 이용하여 다음 단계의 슬롯 수를 변화 시키는 방법을 통해 성능을 개선하는 방안이다. 시뮬레이션을 통한 검증결과 사용되는 총 슬롯수를 감소시켜 태그 인식 시간의 단축은 물론 기존 DFSA 알고리즘보다 더 높은 성능을 확인할 수 있었다.
기존의 알고리즘에 비해 본 논문에서 제안한 DFSA-CS 알고리즘이 보다 빠른 태그 수를 추정하여 성능이 개선된 것을 확인 할 수 있다. 제안된 알고리즘의 특성상 태그 수에 비해 슬롯의 수가 적을 경우 보다 큰 성능을 기대할 수 있으며 태그 수에 비해 프레임의 크기가 큰 경우는 혼잡도 값이 작아지기 때문에 슬롯 낭비 현상을 피할 수 있다.
또한 최초 프레임 크기가 커지게 되면 최초 단계에서의 충돌이 상대적으로 적어지게 된다. 하지만 제안된 알고리즘의 혼잡도는 최초 단계에서의 충돌이 많이 발생하면 커지고 충돌이 적으면 적어지는 구조이기 때문에 최초 단계에서의 충돌이 적다하더라도 슬롯이 낭비되는 현상을 방지 할 수 있다. 또한 Query Tree는 대표적인 트리기반 알고리즘으로 태그ID가 순차적인 경우 제안된 알고리즘이 우수한 성능을 나타내는 것을 확인 할 수 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	Vogt 알고리즘은 무엇을 이용하여 성능을 개선하였는가?	Vogt 알고리즘은 충돌 슬롯 수를 이용하여 성능을 개선하였다. 하지만 Vogt 알고리즘은 충돌의 발생을 단순히 두개의 태그에 의해서만 충돌이 발생하는 것으로 가정하였다.
	FSA 알고리즘에서 태그는 리더의 첫 전송요구명령 신호와 동시에 어떤 정보를 제공받는가?	리더가 범위 안의 태그에 브로드캐스트 하는 것으로 태그인식이 시작된다. 태그는 리더의 첫 전송요구명령(REQUEST) 신호와 동시에 프레임 크기와 슬롯 선택에 대한 정보를 제공받는다. 이때 각 태그들은 전송받은 정보를 이용하여 자신이 사용할 슬롯을 선택한다.
	RFID 기술은 무엇인가?	RFID 기술이란 관리할 모든 개별 사물에 전자태그를 부착하여 리더기로 무선 전파를 태그에 보내면 태그가 자신의 ID정보를 리더기로 전달하는 방식으로써 비접촉 형태로 태그 정보를 인식 할 수 있는 기술이다. 기존 바코드의 문제점을 극복 할 수 있을 뿐만 아니라 모든 개별사물의 인식이 가능하여 부착된 제품의 Traceability와 Visibility를 확보 할 수 있어 유비쿼터스 기술의 핵심기술이라 할 수 있다.

참고문헌 (7)

ISO/IEC 18000-6 : 2003(E), Part 6 : Parameters for air interface communications at 860-960 MHz, Nov., 26, 2003
차재룡, 김재현, 'RFID 시스템에서의 태그 수를 추정하는 ALOHA 방식 Anti-collision 알고리즘,' 한국통학회논문지, Vol.30, No.9A, pp.814-821. March, 2005
Jae-Ryong Cha, Jae-Hyun Kim, 'Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system,' Consumer Communications and Networking Conference, 2006. CCNC 2006. 2006 3rd
J. Cha and J. Kim, 'Novel anti-collision algorithm for fast object identification in RFID system,' in Proc. Parallel and Distributed System 2005, pp.177-172
H. Vogt, 'Efficient Object Identification with Passive RFID tags,' In International Conference on Pervasive Computing, Zurich, 2002, pp.98-113
Law, Ching, Lee, Kayi and Siu, Kai-Yeung. 'Efficient Memoryless protocol for Tag Identification,' In Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp.75-84. ACM. August, 2000
F.C. Schoute, 'Dynamic Length ALOHA,' IEEE Transactions on Communication, Apr., 1983, Vol.31, pp.565-568

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증