Study On Anti-Collision Algorithm For RFID Tags Identification Based On Collision Tree

Radio Frequency Identification (RFID) is one of automatic identification methods, which is used for wirelessly identifying data stored in a tag’s microchip by using RF waves. RFID systems consist of a reader, one or more tags, and an application system. The reader is typically a powerful device with ample memory and computational resources. On the other hand, tags vary significantly in their computational capabilities. They range from dumb passive tags, which respond only at reader commands, to smart active tags, which have an on-board micro-controller, memory, and power supply. Among tag types, passive ones are emerging to be a popular choice for large scale deployments due to their low cost and power consumption.Many applications of RFID require the simultaneous use of multiple tags. Simultaneous transmissions in RFID lead to collisions as reader and tags typically operate on the same channel. Collisions make both communication overhead and transmission delay, which often cause loss of their usefulness. Therefore, efficient anti-collision protocols for identifying multiple tags simultaneously are of great importance for the development of RFID tags identification system, especially, the large-scale RFID system. There are generally two types of collisions in RFID system:tag collisions and reader collisions. This thesis mainly focuses on the tag collision and the anti-collision protocol for it.Tag collision occurs when a plurality of the tags responds to one reader’s inquiry simultaneously, and therefore the reader cannot identify any tag. The existing RFID anti-collision protocols for solving the tag collision problem can be categorized into two classes:ALOHA-based protocols such as:slotted ALOHA procedure (S-ALOHA), frame slotted ALOHA algorithm (FSA), and tree-based protocols such as query tree protocol (QT), binary tree protocol (BT). Almost all known protocols exhibit the overall system efficiency smaller than 50%. This is obviously not satisfactory, and so it would be very important to overcome such a efficiency limit.At the same time, uniform IDs distribution has always been assumed in the past. In fact, other distributions, e.g. continuous distribution and partially continuous distribution, are more popularly in many cases, such as container terminals, warehouses, import and export inspections, etc. This is because in these cases many objects attached with RFID tags belong to the same category and are produced by the same company in the same region. Therefore, according to the partition and using principle of tag IDs, the tag IDs in these cases are distributed mostly continuously. Hence, these distribution models should be concerned in anti-collision protocol.Firstly, this thesis proposes an efficient anti-collision protocol, named collision tree protocol (CT), which overcomes the performance limitation and improves the tag identification efficiency above 50%. In CT, the collision behavior and collided bit become a crucial factor, because that the generating of prefixes and the splitting of the collided tags group are according to the collided bit directly. By this way, CT eliminates the idle cycle in tags identification absolutely, and improves the tag identification performance significantly.Meanwhile, this thesis establishes a collision tree structure, which is used to represent the tags identifying process of CT and analyze the identification performance of it. According to the definition of collision tree, all internal nodes in a collision tree are corresponding to the collision cycles and all leaf nodes are corresponding to the readable cycles in an executing of CT. Therefore, collision tree is a full binary tree and without idle node. According to the property of collision tree, the performance of CT could be calculated and analyzed easily.Another important advantage of CT is the stability of its performances. Stability is a new performance metric defined in this thesis, which is used to analyze and evaluate the performance of anti-collision protocols. In many RFID systems, such as flow productions and automatic controls, the stability of tag identification protocol is more significant, for almost all of them have strict and precise time and power constraints. The stability of an anti-collision protocol is the characteristic that the performance of the protocol is only dependent on the number of tags to be identified and the average performance of it converges to a constant. Both computational and experimental results indicate that CT is a stable and efficient anti-collision protocol for RFID tag identification. For fast and effective tags identification, lower system overhead, and simple and easy implementation, CT can be applied to various RFID tags identification system to solve the tag collision.Furthermore, CT stands for a new branch of tree-based anti-collision protocol for RFID tag identification, and lays the foundations for researching on new anti-collision protocol based on collision tree and CT. This is because CT eliminates the idle cycle completely, improves the tag identification efficiency above 50%, breakes the efficiency limit of anti-collision protocol, and could be represented and analyzed by a strict tree structure. Based on which, this thesis presents two new anti-collision protocols:the improved collision tree protocol (ICT) and the bi-response collision tree protocol (BCT), which consolidate the new branch of tree-based anti-collision protocol also.The main novelties of ICT include that the duality and certainty principle is introduced and adopted in RFID tags identification, and the continuous and partially continuous distributions of tag IDs are taken into account. According to the duality and certainty principle, if only one bit is collided in the tags’ response, ICT could identify two tags in one query cycle by designating the value of the collided bit instead of querying again. Both theoretical and experimental results indicate that ICT improves the tag identification efficiency up to 100% when the tag IDs are distributed continuously, and always above 50% even when the tag IDs are distributed uniformly. Therefore, ICT could be used in various RFID tag identification conditions, especially when the tags IDs are distributed continuously or partially continuously.The main novelties of BCT include that bi-response mechanism is put forward and used in RFID tags identification, and the response-cycle is divided into two sub-cycles, in which two group tags can answer the same query of the reader respectively and independently. By this means, BCT improves the performance of RFID tags identification system significantly, especially in reducing the reader’s queries, decreasing the transmitted bits of the reader and tags, and saveing the power of the RFID system. BCT improves the tag identification efficiency above 100% successfully, no matter the tags IDs are distributed uniformly or continuously. Like CT and ICT, the response of the tags in BCT is only dependent on the received prefix and the characteristic bit, and not dependent on the past historical queries of the reader. Therefore, BCT belongs to the class of memoryless anti-protocols, and could be used in passive RFID system to solve tag collision problem.This thesis puts forward three efficient anti-collision protocols for RFID tags identification based on the collision tree, and improves the tag identification efficiency above 50%, and establishes a new branch of anti-collision protocol based on the collision tree, which establish a good platform for the study of new anti-collision protocols.