Research On Anti-collision Algorithm For RFID System Based On Binary Search Tree

With the Internet of Thing vigorously improving technical maturity and universalapplication, radio frequency identification (RFID) technology as one of IoT underlyinginformation collection technologies causes more attention, and in the case of bothopportunities and challenges, showing great vitality and creativity. RFID technology is anon-contact automatic identification, which uses RF signal to transmit data through spacecoupling. RFID has many superiorities, such as waterproof and antimagnetic, strongpenetrating power, big data storage capacity, long transmitting distance, high security,multi-target recognition, and without human intervention etc, so it is widely applied toindustries, manufacturing and services.In RFID systems, communication between tags and a reader use one same radiochannel, when multiple tags simultaneously communicate with the reader, data collisionswould be occurred in the same wireless channel. Currently, the RFID anti-collisionalgorithms are divided into two types: deterministic algorithm based on tree andnondeterministic algorithm based on Aloha. Based on Aloha algorithm is a random timedivision multiple access methods based on a random time, and has a "hunger" problem,namely some tags are not identified for a long time. Based on tree algorithm can avoid thisphenomenon, and achieve the purpose of completed and undifferentiated recognition, butthere are still some shortcomings, such as long delay identification, energy consumptionand so on. This article will focus on researching based tree anti-collision algorithms tosolve the shortcomings of existing algorithms.Based on the analysis and study of existing anti-collision algorithm in RFID systems,this paper proposes a novel binary search tree with Bit-Lock-Grouping for anti-Collision inRFID systems, namely BS-BLG algorithm. And BS-BLG algorithm adds to twoindications lock: bit-lock-grouping and group-paging, when multiple tags communicatewith the reader, data collisions would be occurred. And these bits of tags’ ID, whichhappen data collisions are useful for identification. In BS-BLG algorithm, through thereader sending the bit-lock-grouping indication, these bits of tags’ ID, which happen data collisions, are locked and made up the new ID of tags, so communicational redundancy ofsystem can be reduced, and statistics the number of consecutive "1" for these new ID oftags, then these tags would be divided into some subsets according to the result of statistic.Through the reader sending the group-paging indication, the ID of tags would be furthershorted, and support backoff strategy to reduce the number of paging and communicationalredundancy. Mathematical proof and simulation analysis shows as: BS-BLG algorithm isbetter than other exiting algorithms, including the system throughout, the times for tagidentification, transmission delay and power consumption of tag etc.