# Improved Anti-Collision Algorithm for the Application on Intelligent Warehouse
## 3 Group Mapping Query Tree Algorithm
### Two Rules Definition  
1. Group Rule Definition  
Group mapping query tree algorithm (GMQT) uses a three-bit grouping strategy, that is, first, we process the three bits of the tag ID by XOR, and then group them according to the rules. In this way, not only the collision time slot can be reduced, but also the reader can accurately infer the combination of the transmission data from the collision information of the received data by using the collision bit inference method. The grouping idea in this paper is based on XOR operation of binary system. Each tag has a grouping counter GC to record the group number. For the tag i, assume that the three adjacent bits starting from the jth bit of tag i are q\({}_{j}\)q\({}_{j+1}\)q\({}_{j+2}\). In addition, the grouping counter GC(i) consists of two parts, the first one represents the value of q\({}_{j}\)\(\oplus\) q\({}_{j+1}\), and the second one represents the value of q\({}_{j+1}\)\(\oplus\) q\({}_{j+2}\). For example, for '0\({}_{1}\)1\({}_{2}\)1\({}_{3}\)', there are 0\({}_{1}\)\(\oplus\) 1\({}_{2}\) = 1 and 1\({}_{2}\)\(\oplus\) 1\({}_{3}\) = 0, so GC = '10'. By analogy, it can be concluded that there are four possibilities for GC(i). That is, tags will be divided into four groups, as shown in Table 1. Since the combination of tags in each group may be known, the composition of the collision bits can be inferred from the group number.  
2. Group Number Mapping Rule Definition  
Since the group number still collides during the transmission process, the reader cannot clearly know which groups exist currently. For example, there are two groups '01' and '10', and the Manchester code of the group number obtained by the reader is '??'. Then, the reader will consider that all the group numbers exist, and sequentially query the '00', '01', '10', '11' groups, which will generate many idle slots, thereby reducing the recognition efficiency.  
The group number mapping rule in this paper uses the mapping rule proposed by [PERSON] [11], which helps the reader to determine the existing group number. The principle of mapping is to convert the k-bit data into a decimal number L, and then generate a 2\({}^{k}\)-bits data, where the last L-bit is 1, and the remaining bits are 0. Because the length of group number is 2-bits, we set k = 2, and the mapping rules are shown in Table 2. The tag processes the group number according to the mapping rules, and then transmitted to the reader. Then, the reader can deduce the group number clearly according to the Manchester code of the mapping data. For example, there are two groups '01' and '10', After mapping, the two groups are '0010' and '0100', and the Manchester code obtained by the reader is '0??0'. Because of the collision of the 2 nd and 3 rd bits, we can deduce that the existing group numbers are '01' and '10' according to the mapping rules.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Group Number** & **Bits** \\ \hline
00 & 000 \\
01 & 111 \\
01 & 001 \\
10 & 100 \\
11 & 010 \\
11 & 101 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Grouping rule.