RFID 시스템에서의 트리 기반 메모리래스 충돌방지 알고리즘에 관한 연구 = A Study on the Tree based Memoryless Anti-Collision Algorithm for RFID Systems

국문 초록 (Abstract)

RFID(Radio Frequency IDentification) 기술은 RF 신호를 사용하여 물품에 부착된 전자태그를 식별하는 비접촉 기술이다. 식별 영역 내에 다수의 태그가 존재한 경우에 요구되는 다중 태그 식별 문제는 RFID 기술 중에서도 핵심 이슈이며 이 문제는 충돌방지 알고리즘을 통하여 해결할 수 있다. 하지만 기존 알고리즘들은 구현의 복잡성과 낮은 성능이 문제로 제기되고 있다. 본 논문에서는 이러한 문제를 해결할 수 있는 트리 기반 메모리래스 충돌방지 알고리즘인 충돌 추적(Collision Tracking) 트리 알고리즘을 제안하고 성능평가 결과를 제시한다. 성능평가 결과 제안하는 알고리즘이 초당 749개의 태그를 식별하면서 기존 트리 기반 메모리래스 알고리즘인 트리-워킹 알고리즘과 쿼리 트리 알고리즘에 비해 각각 약 49배와 2.4배의 성능향상을 확인할 수 있었다.

다국어 초록 (Multilingual Abstract)

RFID(Radio frequency IDentification) is a technology that automatically identifies objects containing the electronic tags by using radio wave. The multi-tag identification problem is the core issue in the RFID and could be resolved by the anti-collision algorithm. However, most of the existing anti-collision algorithms have a problem of heavy implementation cost and low performance. In this paper. we propose a new tree based memoryless anti-collision algorithm called a collision tracking tree algorithm and presents its performance evaluation results obtained by simulation. The Collision Tracking Tree algorithm proves itself the capability of an identification rate of 749 tags per second and the performance evaluation results also show that the proposed algorithm outperforms the other two existing tree-based memoryless algorithms, i.e., the tree-walking algorithm and the query tree algorithm about 49 and 2.4 times respectively.

참고문헌 (Reference)

1 "Ubiquitous Electronic Tagging"" 1 (1): 2000

2 "The Vision and Foundations of Ubiquitous Computing" 2 (2): 2-6, 2001

3 "The Computer of the 21st Century" 265 (265): 94 1991-104,

4 "The Blocker Tag：Selective Blocking of RFID Tags for Consumer Privacy" 9 : 103-111, 2003

5 "Schoch. Infrastructure Concepts for Tag- Based Ubiquitous Computing Applications" 2002

6 "Q-ary Collision Resolution Algorithms in Random Access Systems with Free or Blocked Channel Access IEEE Transactions on Information Theory" 31 (31): 217-243, 1985.

7 "Protocol Specification for 900MHz RFID Tag" Auto-ID Center 2003

8 "Fundamentals and Applications in Contactless Smart Cards and Identification" John Wiley & Sons Inc. 2003

9 "Efficient Object Identification with Passive RFID Tags" Springer-Verlag 2002

10 "Efficient Memoryless protocol for Tag Identification and Communications" 75-84, 2000

11 "EPC 네트워크를 위한 다중 RFID 태그 식별 알고리즘의 분석" 4 (4): 27-37, 2003

12 "Control of ALOHA signalling in a Mobile Radio Trunking System" ieee : 38-42, 1980.

13 "Contactless identification device with anti-collision algorithm Conference on Circuits" 1999

14 "Collision Resolution Algorithms and Random-Access Communications" In G. Longa, editor, Multi- User Communication Systems," Springer-Verlag 73-173, 1981.

15 "Bridging Physical and Virtual Worlds with Electronic Tags" 370-377, 1999

16 "Analysis of Tree Algorithms for RFID Arbitration" 107-, 1998

17 "Analysis of Contention Tree Algorithms" 46 (46): 2163-2172, 2000

18 "An Exact Analysis and Performance Evaluation of Framed ALOHA with Capture IEEE Transactions on Communications" 37 (37): 125-137, 1989.

19 "An Efficient Stochastic Anti-collision Algorithm using Bit-Slot Mechanism" 2004

20 "860MHz-930MHz Class I Radio Frequency Identification Tag Radio Frequency^Logical Communication Interface Specification Candidate" Auto-ID Center -101, 2002

21 "13.56MHz ISM Band Class 1 Radio Frequency Identification Tag Interface Specification：Candidate Recommendation^May" Auto-ID Center -100, 2003