# Improved Anti-Collision Algorithm for the Application on Intelligent Warehouse
## 2 Related Work  
Currently, RFID anti-collision algorithms fall into two categories: tree-based deterministic algorithm and Aloha-based uncertain algorithm. The tree-based algorithm does not have the problem of label hunger, that is, there is no case that a label cannot be recognized for a long time, and the Aloha-based uncertainty algorithm has a label hunger problem due to random allocation of time slots. However, its advantage is that the algorithm is simple and easy to implement, and its performance is not affected by the length and distribution of label ID. According to the characteristics of warehousing, this paper will improve the tree-based anti-collision algorithm. The query tree (QT) algorithm was first proposed by [PERSON] [1], and he set a stack in reader to store the query prefix. In every slot, the reader will broadcast the query command to the tags in the reader field, then the tags that match the query prefix 'q' respond to the reader, if multiple tags respond, there will be a collision, and the reader will push 'q0' and 'q1' into the stack, then the next query starts until the stack is empty. In the traditional tree traversal algorithm, regardless of whether or not there is a collision node of the tree, the algorithm will traverse the entire binary tree, which will lead to low efficiency in the RFID system. In order to solve the problems of long recognition time and low system efficiency in a tree-based deterministic algorithms, scholars have proposed many excellent improved algorithms in recent years. [PERSON] et al. [2; 3; 4] proposed a novel Query window Tree (QwT) protocol; the QwT effectively controls the number of responded bits from tags by adopting a dynamic-size 'window'. [PERSON] et al. [5] proposed a binary search algorithm based on continuous collision bits (IACA). If collision occurs, the reader can pick out the specific collision position according to the Manchester code, if the first and the second collision bits are consecutive, it will set the first two collision bits to '00', '01', '10', '11', respectively. Then, set the bits lower than the second collision bits to 1 and other bits remain unchanged. The reader set the new string as the command of next cycle. If the ID is less than command string, the tag will respond the reader with its own ID. However, if the first and the second collision bits are discontinuous, it will work as an ordinary binary search algorithm. [PERSON] et al. [6] proposed the collision tree (CT) algorithm that eliminates the idle cycle in tags identification absolutely. [PERSON] et al. [7] studied the effect of tag ID distribution on tree-based memoryless algorithms and proposed a Flexible Query window Tree (FQwT) algorithm; it also reduced recognition time and energy loss through grouping labels by an estimated distributor. [PERSON] et al. [8] proposed an OQTT algorithm which divides the number of tags into several groups by optimizing segmentation criteria based on a bit estimation method and, finally, it uses a query tracking tree to identify tags quickly. [PERSON] et al. [9] proposed an adaptive 4-ary pruning query tree algorithm (4 APQT). Compared with the classical QT algorithm, it reduces the number of queries and unnecessary idle time slots, and improves the system throughput and communication complexity. [PERSON] et al. [10] designed a characteristic-value-based grouping rule and a collision bits rule to determine transmitted bit string combinations accurately and proposed a bit arbitration tree anti-collision protocol based on these two rules to decrease the time for collecting all tag IDs. [PERSON] et al. [11] proposed a novel tag anti-collision algorithm called a M-ary query tree scheme (MQT). A mapping rule is defined in the algorithm, and the m bits of the tag are mapped into \(2^{m}\) bits and sent to the reader. In addition, the reader can deduce the collision bit combination according to the mapping rules. This algorithm can send data accurately and reduce idle time slots.