An Efficient Adaptive Anticollision Algorithm Based on 4-Ary Pruning Query Tree

In radio frequency identification system (RFID), the efficiency in which the reader identifies multiple tags is closely related to the methods to solve the collision of multiple tags. At present, a reasonable solution is the introduction of 4-ary query tree (or n-ary query tree) to reduce the collision time slots and additional query is used to decrease idle timeslots. The advantage of a 4-ary tree anti-collision algorithm is that it is able to reduce collision timeslots, but it also increases the idle timeslots. To reduce these excessive idle timeslots the 4-ary tree anticollision algorithm brings, an anti-collision algorithm based on adaptive 4-ary pruning query tree (A4PQT) is proposed in this paper. On the basis of the information of collision bits, some idle timeslots can be eliminated through pruning the 4-ary tree. Both theoretical analysis and simulation results support that A4PQT algorithm can significantly reduce recognition time and improve throughput of the RFID system. 1. Introduction In the Radio frequency identification (RFID) system, if multiple readers and multiple tags, or a single reader and multiple tags, transmit simultaneously in the readers’ working area, there are three types of collision as readers and tags operate on the same wireless channel. First, it is the frequency interference among readers which is due to the overlapping of two or more readers in the working area. The signals transmitted by these readers are causing mutual interference; thus the readers cannot read properly the tag data within the region. Second, when a tag appears in two or more readers' working area, it will not know which readers to communicate with. Third, when many tags appear in the working area of one reader, these tags respond simultaneously to the queries of the reader, which will result in collision. Generally, the first two types of collision are called reader-to-reader collision, and the third is known as reader-to-tag collision. When collision occurs, the reader cannot read the tag's data. How to reduce the number of collisions? How to reduce the messages that tag transmits repeatedly and reduce the communication overhead of the RFID system? Therefore, an efficient anticollision algorithm for identifying multitag is of great importance for the wireless RFID system. RFID system for solving multitag collision problem is currently divided into ALOHA-based anticollision algorithms and tree-based anticollision algorithms [1, 2]. ALOHA-based anticollision algorithms such as Slotted ALOHA, framed slotted ALOHA, dynamic framed slotted ALOHA, and