The Research On RFID Anti-collision Algorithms Based On Binary Tree

RFID (Radio Frequency Identification) is a kind of auto-identify technique appeared in 90th. It is popular in theory and application research. It has many advantages, such as abundance of data information, short recognizing time and low cost. RFID technology, which is based on the computer technology, signal process technology, wireless data transfer technology, integrated circuit technology and auto-control technology, has a lot of applications in our lives.RFID systems allow contactless identification of objects using radio frequency. When there are more than one tag within the interrogation zone of a reader, all the tags may send data at the same time which may lead to data collision. Radio frequency identification require that people can't feel the consumption of time and the receiver of reader should prevent tags'data from colliding. In RFID system, there are two type of collision resolution scheme: 1) Probabilistic algorithm, which is based on Aloha. 2) Deterministic algorithm which is based on binary tree. The Aloha algorithm is very simple procedure, a reader requests ID, tags will randomly send their data. When collision occurs, they wait random time and retransmit. In the slotted Aloha algorithm, time is divided in discrete time slot, and a tag can send its data at the beginning of its pre-specified slot. Although the slotted Aloha algorithm can enhance the channel utilization and throughput, it cannot guarantee the response time when there are many tags near reader. Besides, there are dynamic slotted Aloha, frame-slotted Aloha, dynamic frame-slotted Aloha and so on. The probabilistic algorithm based on Aloha has a fatal disadvantage that the tags may not be identified forever, which is called starvation. Deterministic algorithm based on binary tree, which has no starvation problem, is most suitable for passive tag applications. It is categorized into binary search algorithm and dynamic binary search algorithm. Both of these algorithms do not require tag's own counter. Instead of using counter, the reader transmits prefix and only tags that its ID contains this prefix are response. The binary algorithm is not random in the whole recognizing process, and can solve the collision Problem occurred when there are more than one tag within the interrogation zone of a reader. The binary algorithm can improve the speed of transmission, enhance the channel utilization and accuracy, reduce the time slot, and make the system more stable.In this paper,improved binary algorithm and diversity binary algorithm are proposed based on the binary tree algorithm. In binary algorithms, after reader transmits the query, tags within the interrogation zone of the reader response and transmit their IDs to reader. If the reader decodes the signal from tags and the reader recognizes k bits where there are collisions. This k bits is unclear for tags and the reader, and other bits are clear for them. In the binary search algorithm, the reader and tags transmit the bits whose length is equal to tags'ID, so the queries contain too much redundant information. Although the dynamic binary search algorithm minus the half of the redundant information, it is not be the best choice. Improved binary algorithm and diversity binary algorithm will minus the redundant information based on the dynamic binary search algorithm. In the binary search algorithm and dynamic binary search algorithm, after reader recognizes one tag, it returns to the root node of the binary tree and transmits queries from the root node. So this two algorithms increase a lot of redundant queries. In improved binary algorithm and diversity binary algorithm, it will return to the previous node where there occurs collision. So the number of queries will de reduced greatly. The algorithm of this paper is divided into two parts. The first part is mainly to introduce the improved binary algorithm, and propose the concept of bit-locking and the order of bit-locking. First of all, the reader recognizes the bits where there are collisions. Then the reader transmits an order of bit-locking, and the bits participate in the algorithm are just the bits which are locked. Backoff strategy is adopted in the process of querying. After bit-locking, the reader transmits prefix and only the tags that its ID contains this prefix are response and transmit other bits except the prefix. In this part, the paper discusses the encoding mode and the orders that are used in the algorithm, and explain the basic principle and working procedure of the algorithm. Manchester code is used in improved binary algorithm. Besides, the paper analysis and simulate the performance of the improved binary algorithm, which are relate to the number of the request, transmission delay, power consumption and throughput of the system. The results of simulation and analysis show that the improved binary algorithm has less number of queries, lower transmission delay, lower energy consumption and higher system throughput than the existing binary tree algorithm. The second part is mainly to introduce the diversity binary algorithm. This algorithm is more prone to applied in the intensive distribution of tags than the improved binary algorithm. First of all, the reader transmits a query and all tags reply to this order. And the reader recognizes the bits where there are collision and send a order of bit-locking. Then, the reader divides the interrogation zone into several sets based on the number of tags, when there are much more tags appear in the interrogation zone of the reader. Finally, the improved binary algorithm is implemented in each set. In this algorithm, each tags experience two query of bit-locking, so the number of bits transmitted are reduced. Also, the paper analysis and simulate the performance of the algorithm, which are relate to the number of the request, transmission delay, power consumption and throughput of the system. The results of simulation and analysis show that the diversity algorithm has less number of queries, lower transmission delay, lower energy consumption and higher system throughput than the improved binary algorithm and existing binary tree algorithm.