Adaptive splitting protocols for RFID tag collision arbitration

ABSTRACT

Tag identification is an important tool in RFID systems with applications for monitoring and tracking. A RFID reader recognizes tags through communication over a shared wireless channel. When multiple tags simultaneously transmit their IDs to a reader, the tag signals collide and this collision disturbs the reader's identification process. Therefore, tag collision arbitration for passive RFID tags is a significant issue for fast identification. This paper presents two adaptive tag anti-collision protocols, an Adaptive Query Splitting protocol (AQS), which is an improvement on the query tree protocol and an Adaptive Binary Splitting protocol (ABS), which is based on the binary tree protocol, which is a de facto standard for RFID anti-collision protocols. To reduce collisions and identify tags efficiently, adaptive splitting protocols use information obtained from the last process of tag identification. Our performance evaluation shows that AQS and ABS outperform other tree based tag anti-collision protocols.

REFERENCES

• 1: C. Floerkemeier and M. Lampe, "Issues with RFID usage in ubiquitous computing applications," Proc. 2nd Int'l Conf. Pervasive Computing, LNCS 3001, pp. 188--193, 2004.
• 2: Ching Law , Kayi Lee , Kai-Yeung Siu, Efficient memoryless protocol for tag identification (extended abstract), Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, p.75-84, August 11-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345848.345865]
• 3: D. W. Engels and S. E. Sarma, "The reader collision problem," Proc. IEEE Int'l Conf. System, Man and Cybernetics, Hammamet, Tunisie, Oct. 2002.
• 4: "EPCTM radio-frequency identification protocols class-1 generation-2 UHF RFID protocol for communications at 860MHz-960MHz version 1.0.8," EPCglobal, Dec. 2004.
• 5: F. C. Schoute, "Dynamic frame length ALOHA," IEEE Trans. Comm., COM-31(4):565--568, Apr. 1983.
• 6: Feng Zhou , Chunhong Chen , Dawei Jin , Chenling Huang , Hao Min, Evaluating and optimizing power consumption of anti-collision protocols for applications in RFID systems, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013321]
• 7: Harald Vogt, Efficient Object Identification with Passive RFID Tags, Proceedings of the First International Conference on Pervasive Computing, p.98-113, August 26-28, 2002
• 8: I. E. Teletar and R. G. Gallager, "Combining queuing theory and information theory for multiaccess," IEEE J. Selected Areas Communication, vol. 13, pp. 963--969, Aug. 1995.
• 9: "Information technology automatic identification and data capture techniques - radio frequency identification for item management air interface - part 6: parameters for air interface communications at 860-960 MHz," Final Draft International Standard ISO 18000-6, Nov. 2003.
• 10: J. E. Wieselthier, A. Ephremides and L. A. Michaels, "An exact analysis and performance evaluation of framed ALOHA with capture," IEEE Trans. Comm., COM-38(2):125--137, 1989.
• 11: J. I. Capetanakis, "Tree algorithms for packet broadcast channels," IEEE Trans. Information Theory, IT-25(5):505--515, Sept. 1979.
• 12: J. Moseley and P. Humblet, "A class of efficient contention resolution algorithms for multiple access channels," IEEE Trans. Communications, vol. COM-33, pp. 145--151, 1985.
• 13: J. Zhai and G. Wang, "An anti-collision algorithm using two-functioned estimation for RFID tags," Proc. Int'l Conf. Computational Science and its Applications, May 2005.
• 14: Klaus Finkenzeller, RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification, John Wiley & Sons, Inc., New York, NY, 2003
• 15: N. Abramson, "The aloha system- another alternative for computer communications," Proc. Fall Joint Computer Conf., AFIPS Conf., vol. 37, pp. 281--285, 1970.
• 16: "Philips I*Code1 System Design Guide - Application Note AN00025," Philips Semiconductors, 2002.
• 17: R. Metcalfe, "Steady state analysis of a slotted and controlled Aloha system with blocking," Proc. 6th Hawaii Conf. System Science, Honolulu, HI, 1973.
• 18: R. Rao and A. Ephremides, "On the stability of interacting queues in a multiple-access system," IEEE Trans. Inform. Theory, vol. 34, pp. 918--930, 1988.
• 19: S. A. Weis, S. E. Sarma, R. L. Rivest and D. W. Engels, "Security and privacy aspects of low-cost radio frequency identification systems," Proc. First Annual Conf. Security in Pervasive Computing, LNCS 2802, pp. 201--212, Mar. 2003.
• 20: S. Lam and L. Kleinrock, "Packet switching in a multi access broadcast channel: Dynamic control procedures," IEEE Trans. Automat. Contr., vol. AC-27, pp. 891--904, 1975.
• 21: T. A. Scharfeld, "An analysis of the fundamental constraints on low cost passive radio-frequency identification system design," M.S. thesis, Massachusetts Institute of Technology, pp. 92--100, Aug. 2001.
• 22: UCODE, Philips Semiconductors, http://www.semiconductors.philips.com, 2005.
• 23: V. Anatharam, "The stability region of the finite-user slotted ALOHA protocol," IEEE Trans. Inform. Theory, vol. 37, 1991.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Performance

Keywords:
RFID, collision resolution, tag anti-collision, tag identification