An anti-collision algorithm without idle cycle using 4-ary tree in RFID system

ABSTRACT

This paper proposes an anti-collision algorithm needed in the process of recognizing data of the tags when one reader and multiple passive tags simultaneously have data communications in RFID system. QTA And 4-ary QTA which are based on the Tree algorithm, have the problem that the numbers of query - response are many and the idle cycle (requesting about non-existent tag) exists in the process of recognizing the tags. Advanced 4-ary Query Tree Algorithm(A4QTA) has a 4-ary tree structure and when tag responses according to query of the reader, it applies a digital coding method, the Manchester code, in order to detect the collision point. Also, this algorithm reduces the number of query-response compared to QTA and 4-ary QTA by devising a method for one bit collision and series two bit?s collision in these bits as well as improves the performance by removing the idle cycle.

REFERENCES

• 1: Klaus Finkenzeller, RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification, John Wiley & Sons, Inc., New York, NY, 2003
• 2: P. H. Cole, "Fundamentals in RFID part1," Korean RFID course, 2006, Available at:http://autoidlab.eleceng.adelaide.edu.au/education/FundamentalsInRfidPart1.pdf.
• 3: Sanjay Sarma , David Brock , Daniel Engels, Radio Frequency Identification and the Electronic Product Code, IEEE Micro, v.21 n.6, p.50-54, November 2001 [doi>10.1109/40.977758]
• 4: D. W. Engels and S. E. Sarma, "The Reader Collision Problem," In Proceedings of IEEE International Conference on System, Man and Cybernetics, Hammamet, Tunisie, October 2002.
• 5: Jihoon Myung , Wonjun Lee, Adaptive binary splitting: a RFID tag collision arbitration protocol for tag identification, Mobile Networks and Applications, v.11 n.5, p.711-722, October 2006 [doi>10.1145/1160115.1160121]
• 6: 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]
• 7: P. Mathys and P. Flajolet, "Q-ary collision resolution algorithms in random-access systems with free or blocked channel access," in IEEE Trans. Inform. Theory, pp. 21 7--243, 1985.

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:
4-ary query tree, RFID, anti-collision, idle-cycle, the number of query-responses