The Journal of Korean Institute of Communications and Information Sciences (한국통신학회논문지)

The Korean Institute of Commucations and Information Sciences (한국통신학회)
권호 표지

Performance Evaluation of Anti-collision Algorithms in the Low-cost RFID System

저비용 RFID 시스템에서의 충돌방지 알고리즘에 대한 성능평가

  • 권성호 (대구대학교 정보통신공학과) ;
  • 홍원기 (대구대학교 정보통신공학부) ;
  • 이용두 (대구대학교 정보통신공학부) ;
  • 김희철 (대구대학교 정보통신공학부)
  • Published : 2005.01.01
Download PDF
⟨ Previous Next ⟩

Abstract

RFID(Radio Frequency IDentification) is a technology that automatically identifies objects attached with electronic tags by using radio wave. For the implementation of an RFID system, an anti-collision algorithm is required to identify several tags within the RFID reader's range. Few researches report the performance trade-off among anti-collision algorithms in terms of the communications traffic between the reader and tags, the identification speed, and so on. In this paper, we analyze both tree based memoryless algorithms and slot aloha based algorithms that comprise of almost every class of existing anti-collision algorithms. To compare the performance, we evaluated each class of anti-collision algorithms with respect to low-cost RFID system with 96-bit EPC(Electronic Product Code). The results show that the collision tracking tree algorithm outperforms current tree based and aloha based algorithms by at least 2 times to 50 times.

RFID(Radio Frequency IDentification) 기술은 RF 신호를 사용하여 물품에 부착된 전자태그를 비접촉식으로 식별하는 자동인식기술이다. RFID 시스템 구축에 있어 식별영역 내에 다수의 태그가 존재할 경우, 다중태그 식별(multi-tag identification)을 위한 충돌방지(anti-collision) 알고리즘이 필수적으로 요구된다. 태그 충돌방지와 관련된 기존 연구들은 각각 고유한 형태의 코드체계를 기반으로 하고 있으며 태그 식별성능에 대한 비교연구도 부족한 상태이다. 본 논문에서는 저비용(low-cost) RFID 시스템 구축을 목표로 표준화가 진행되고 있는 96-비트 EPC(Electronic Product Code) 코드를 기반으로 기존 대표적인 충돌방지 알고리즘인 트리 기반 메모리래스(tree based memoryless) 충돌방지 알고리즘들과 슬롯 알로하 기반으로 (slot aloha based) 충돌방지 알고리즘들의 성능평가를 수행한다. 성능평가 결과 초당 평균 태그 식별개수에서 충돌 추적 트리(collision tracking tree) 알고리즘이 다른 알고리즘들보다 최소 2배에서 최대 50배 이상의 우수한 성능을 보여준다.

Keywords

References

  1. 권성호, 김희철, ETC네트워크를 위한 다중 RFID 태그 식별 알고리즘의 분석. 한국인터넷정보학회, Vol. 4, No. 4, Pages 27-37. December 2003
  2. Hush, Don R. and Wood, Cliff. Analysis of Tree Algorithms for RFID Arbitration. In IEEE International Symposium on Information Theory, Pages 107-. IEEE, 1998
  3. Jacomet M, Ehrsam A, Gehrig U. Contactless identification device with anti-collision algorithm. IEEE Computer Society, CSCC 99, Conference on Circuits, Systems, Computers and Communications, Athens. 4-8 July 1999
  4. A. Juels, R. Rivest, and M. Szydlo. The Blocker Tag: Selective Blocking of RFID Tags for Consumer Privacy. Proceedings of the 10th ACM conference on Computer and communication security, ISBN:1-58113-738-9, Pages 103-111. 2003
  5. 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, Pages 75-84. ACM. August 2000
  6. 권성호, 박경랑, 김희철. 충돌 추적 기법을 적용한 다중 태그 식별 알고리즘의 설계 및 구현, 대한전자공학회하계종합학술대회, Vol. 27, No. 1, Pages 679-682. June 2004
  7. Vogt, H. Efficient Object Identification with Passive RFID Tags. In International Conference on Pervasive Computing, LNCS. Springer-Verlag. 2002
  8. Auto-ID Center. 13.56MHz ISM Band Class 1 Radio Frequency Identification Tag Interface Specification: Candidate Recommendation, Version 1.0.0. Auto-ID Center. May 1, 2003
  9. Changsoon Kim, Kyunglang Park, Hiecheol Kim, Shindug Kim. An Efficient Stochastic Anti-collision Algorithm using Bit-Slot Mechanism. PDP'2004, July 2004
  10. Auto-ID Center. Protocol Specification for 900MHz RFID Tag. Auto-ID Center. February 23, 2003
  11. Auto-ID Center. 860MHz-930MHz Class I Radio Frequency Identification Tag Radio Frequency & Logical Communication Interface Specification Candidate Recommendation, Version 1.0.1. Auto-ID Center. November 14, 2002