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

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

A Stack Bit-by-Bit Algorithm for RFID Multi-Tag Identification

RFID 다중 태그 인식을 위한 스택 Bit-By-Bit 알고리즘

  • 이재구 (인천대학교 컴퓨터공학과 무선정보 네트워크 연구실) ;
  • 유대석 (인천대학교 컴퓨터공학과 무선정보 네트워크 연구실) ;
  • 최승식 (인천대학교 컴퓨터공학과 무선정보 네트워크 연구실)
  • Published : 2007.08.31
Download PDF
⟨ Previous Next ⟩

Abstract

For the implementation of a RFID system, an anti-collision algorithm is required to identify multiple tags within the range of a RFID Reader. A Bit-by-Bit algorithm is defined by Auto ID Class 0. In this paper, we propose a SBBB(Stack Bit-by-Bit) algorithm. The SBBB algorithm save the collision position and makes a query using the saved data. SBBB improve the efficiency of collision resolution. We show the performance of the SBBB algorithm by simulation. The performance of the proposed algorithm is higher than that of BBB algorithm. Especially, the more each tag bit streams are the duplicate, the higher performance is.

RFID(Radio Frequency IDentification) 리더기가 영역내의 다수의 태그를 인식하기 위해선 충돌방지 알고리즘이 반드시 필요하다. 본 논문은 Auto ID Class 0에서 정의한 충돌방지 알고리즘인 Bit-by-Bit(BBB) 이진트리 알고리즘의 충돌 위치를 스택에 저장하고 이를 통해 다음 질의어를 결정함으로써 성능이 크게 개선된 Stack-Bit-by-Bit(SBBB) 알고리즘을 제안한다. 시뮬레이션을 통한 검증결과 대표적인 충돌 방지 기술인 Query Tree(QT)는 물론 기존의 BBB 알고리즘에 비해 질의-응답 횟수, 질의어의 크기, 응답어의 크기의 모든 면에서 성능이 개선된 것을 확인할 수 있었다.

Keywords

References

  1. 이현지, 김종덕, '충돌 비트 위치를 활용한 RFID 다중 태그 인식 알고리즘,' 한국통신학회논문지, Vol. 31, No. 4A, December 2005
  2. Auto-ID Center, 'Draft Protocol Specification for a Class 0 Radio Frequency Identification tag,' 2003
  3. Auto-ID Center, 'Draft protocol specification for a 900MHz Class 0 Radio Frequency Identification Tag,' Auto-ID Center. February 23, 2003
  4. Don. R. Hush, and Wood Cliff, 'Analysis of Tree Algorithms for RFID Arbitration,' In IEEE International Sysmposium on Information Theory, Pages 107-. IEEE, 1998
  5. 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, ISBM:1-58 113-738-9, Pages 103-111. 2003
  6. 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
  7. 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
  8. 권성호, 박경랑, 김회철, '충돌 추적 기법을 적용 한 다중 태그 식별 알고리즘의 설계 및 구현,' 대한전자공학회하계종합학술대회, Vol. 27, No.1, Pages 679-682. June 2004
  9. Auto-ID Center, 'Draft Protocol Specification for a Class 1 Radio Frequency Identification tag,”'2003
  10. Vogt, H. 'Efficient Object Identification with Passive RFID Tags,' In International Conference on Pervasive Computing LNCS. Springer-Verlag. 2002
  11. Auto-ID Center. '13.56MHz ISM Band Class 1Radio Frequency Identification Tag Interface Specification: Candidate Recommendation, Version 1.0.0,' Auto-ID Center. May 1, 2003
  12. Changsoon Kim, Kyunglang Park, Hiecheol Kim, Shindug Kim, 'An Efficient Stochastic Anti-collision Algotithm using Bit-Slot Mechanism,' PDP'2004, July 2004
  13. ISO/IEC 18000-6 : 2003(E), Part 6 : Parameters for air interface communications at 860-960 MHz, Nov. 26, 2003
  14. 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
  15. EPCglobal, 'EPCglobal Tag Data Standards Version 1.3,' Ratified Specification, March 2006