Optimal Slot Assignment for Binary Tracking Tree Protocol in RFID Tag Identification

Tag anti-collision has long been an important issue in RFID systems. To accelerate tag identification, some researchers have recently adopted bit tracking technology that allows the reader to detect the locations of collided bits in a collision slot. However, these methods still encounter the problem of too many collisions occurring at the beginning of identification. This paper proposes an optimal binary tracking tree protocol (OBTT) that tries to separate all of the tags into smaller sets to reduce collisions at the beginning of identification. Using bit tracking technology, OBTT mainly adopts three proposed approaches, bit estimation, optimal partition, and binary tracking tree. Bit estimation first estimates the number of tags based on the locations of collided bits. Optimal partition then determines the optimal number of the initial sets based on this estimation. Binary tracking tree lets the tag utilize one counter to achieve the split during the identification process. This paper formally analyzes the slot efficiency of OBTT, which represents how many tags can be identified in a slot. Results show that the slot efficiency is close to 0.614, the highest value published to date. Considering slot lengths, OBTT further determines the optimal number of the initial sets to minimize the identification delay. The analytical results show that the delay efficiency of OBTT achieves 0.750, where delay efficiency represents the number of tags that can be identified in a baseline slot, the length of which is the complete ID sent by the tag. The simulation results show that OBTT outperforms other existing algorithms.