The KIPS Transactions:PartC (정보처리학회논문지C)

Korea Information Processing Society (한국정보처리학회)
권호 표지
DOI QR코드

DOI QR Code

A Study on the Tree based Memoryless Anti-Collision Algorithm for RFID Systems

RFID 시스템에서의 트리 기반 메모리래스 충돌방지 알고리즘에 관한 연구

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

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.

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

Keywords

References

  1. M. Weiser, 'The Computer of the 21st Century,' Scientific America, Vol.265, No.3, pp.94-104. September, 1991 https://doi.org/10.1038/scientificamerican0991-94
  2. R. Want, K. Fishikin, A. Gujar and B. Harrison, 'Bridging Physical and Virtual Worlds with Electronic Tags,' In ACM Conference on Human Factors in Computing Systems(CHI99), Pittsburgh, PA., pp.370-377, May, 1999 https://doi.org/10.1145/302979.303111
  3. Want, R., Russell, D. M., 'Ubiquitous Electronic Tagging,' Distributed Systems Online, Vol.1, No.1, September, 2000
  4. F. Mattern, 'The Vision and Foundations of Ubiquitous Computing,' Upgrade, Vol.2, No.5, pp.2-6, October, 2001
  5. K. Romer, T., 'Schoch. Infrastructure Concepts for Tag-Based Ubiquitous Computing Applications,' Workshop on Concepts and Models for Ubiquitous Computing at Ubicomp 2002, Goteborg, Sweden, September, 2002
  6. IDTechEx Ltd., http://www.idtechex.com
  7. 권성호, 김희철, 'EPC 네트워크를 위한 다중 RFID 태그 식별 알고리즘의 분석', 한국인터넷정보학회, Vol.4, No.4, pp.27-37, December, 2003
  8. Klaus Finkenzeller, 'Fundamentals and Applications in Contactless Smart Cards and Identification, Second Edition,' John Wiley & Sons Inc., April, 2003
  9. J. L. Massey, 'Collision Resolution Algorithms and Random-Access Communications,' In G. Longa, editor, Multi-User Communication Systems, Springer-Verlag, New York, pp.73-173, 1981
  10. P. Mathys and P. Flajolet, 'Q-ary Collision Resolution Algorithms in Random Access Systems with Free or Blocked Channel Access,' IEEE Transactions on Information Theory, IT, Vol.31, No.2, pp.217-243, March, 1985 https://doi.org/10.1109/TIT.1985.1057013
  11. A. J. E. M. Janssen, M. J. de Jong, 'Analysis of Contention Tree Algorithms,' IEEE Trans. Inform. Theory, Vol.46, No.9, pp.2163-2172, September, 2000 https://doi.org/10.1109/18.868486
  12. Hush, Don R. and Wood, Cliff, 'Analysis of Tree Algorithms for RFID Arbitration,' In IEEE International Symposium on Information Theory, IEEE, pp.107-, 1998
  13. 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., July, 1999
  14. 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, pp. 103-111, 2003 https://doi.org/10.1145/948109.948126
  15. 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, ACM, pp.75-84, August, 2000 https://doi.org/10.1145/345848.345865
  16. Frits C. Schoute, 'Control of ALOHA signalling in a Mobile Radio Trunking System,' In International Conference on Radio Spectrum Conservation Techniques, IEEE, pp.38-42, 1980
  17. Jeffrey E. Wieselthier, Anthony Ephremides and Larry A. Michaels, 'An Exact Analysis and Performance Evaluation of Framed ALOHA with Capture,' IEEE Transactions on Communications, COM, Vol.37, No.2, pp.125-137, 1989 https://doi.org/10.1109/26.20080
  18. Vogt, H., 'Efficient Object Identification with Passive RFID Tags,' In International Conference on Pervasive Computing, LNCS. Springer-Verlag, 2002
  19. 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, 2003
  20. Changsoon Kim, Kyunglang Park, Hiecheol Kim, Shindug Kim, 'An Efficient Stochastic Anti-collision Algorithm using Bit-Slot Mechanism,' PDP'2004, July, 2004
  21. EPCGlobal Inc, http://www.epcglobalinc.org
  22. Auto-ID Center, 'Protocol Specification for 900MHz RFID Tag,' Auto-ID Center, February, 2003
  23. 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, 2002

Cited by

  1. An Efficient Tag Identification Algorithm using Bit Pattern Prediction Method vol.8, pp.5, 2013, https://doi.org/10.14372/IEMEK.2013.8.5.285
  2. A RFID Tag Anti-Collision Algorithm Using 4-Bit Pattern Slot Allocation Method vol.14, pp.4, 2013, https://doi.org/10.7472/jksii.2013.14.4.25