# An Admission-Control-Based Dynamic Query Tree Protocol for Fast Moving RFID Tag Identification
## 4 Admission-Control-Based Dynamic Query Tree Protocol for Fast Moving Tag Identification
### Multi-Round Admission Control Algorithm  
In conveyor belt systems, tags continuously move through the reader's reading range. The participating time of a tag greatly affects the identification efficiency. In traditional methods, a newly arriving tag directly joins the current round or waits to participate in the subsequent round. If tag flow rate and identification efficiency differ widely, the identification process will be inefficient with much idle time or collisions. In this work, a multi-round admission control (MRAC) algorithm is proposed to improve the identification efficiency. The identification process of MRAC is abstracted in Figure 3, where \(n\) is the number of tags participating in each round, and \(T\) is the time interval of two consecutive rounds. At the beginning, there is no tag in the reading range. With the conveyor belt moving for \(T_{0}\) s, there are \(n_{1}\) tags arrived, and the reader starts the first round immediately. Suppose after \(T_{1}\) s, the reader recognized all \(n_{1}\) tags and starts the second round. During this time, the number of newly arrived tags is \(n_{2}\). Similarly, if the second round takes \(T_{2}\) s, the number of newly arrived tags in this round is \(n_{3}\), and the recognition time in round 3 is \(T_{3}\). Suppose the conveyor belt keeps moving at a constant speed, the tag flow rate \(r_{t}\) is obtained by  
\[r_{t}=n_{2}/T_{1}=n_{3}/T_{2}\ (\text{tags}/\text{s}) \tag{1}\] \begin{table}
\begin{tabular}{c c} \hline \hline
**Symbol** & **Definition** \\ \hline \(ID\) & Tag’s unique identifier, \(d_{t}\) refers to the \(i\)th bit position \\ \hline \(pre\) & Matching prefix transmitted by the reader at the beginning of each round, \(q_{i}\) denotes the \(i^{\text{th}}\) bit, and \(L_{pre}\) is the length of \(pre\) \\ \hline \(Q\) & Query queue maintained by the reader to record \((pre,k)\) of each frame \\ \hline \(TC\) & Slot index \\ \hline \(Query()\) & Frame start command broadcast by the reader to start each frame and to inform tags of the frame parameters. \\ \hline \(Qrep\) & Slot start command broadcast by the reader to start each slot within a frame \\ \hline \(PUISH(a,Q)\) & Push \(a\) into \(Q\) with first-in-first-out manner \\ \hline \(POP(Q)\) & Obtain the first item and delete it from \(Q\) \\ \hline \(bin2 dec(a)\) & Convert binary string \(a\) to decimal number \\ \hline \(dec2 hin(n,m)\) & Convert decimal number \(n\) to an \(m\)-bit binary string \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Symbol definitions. The average time needed to identify one tag in the first three rounds is  
\[T_{ave}=(T_{1}+T_{2})/(n_{2}+n_{3}) \tag{2}\]  
With the estimation results and system requirement, the number of tags admitted to participate in the subsequent round can be calculated. In what follows, we analyze the influence of participating tag number \(n\) on the tag lost ratio \(\alpha\) in one round. As given in Figure 4, the identification process in a single round is considered in three cases, i.e., \(n>N\), \(n=N\) and \(n<N\), where \(N\) is the maximum number of tags that the reader can recognize in a normal situation. In Figure 4, the shadowed rectangles give the number of participating tags, the white rectangles represent the number of slots used to identify tags, and \(L\) is the reader's coverage range. When \(n<N\), the reader can recognize all participating tags before they move out of its reading range. There is some time left before the reader starts the next round. Thus, the system does not reach its optimal situation. When \(n=N\), the reader completely recognizes all participating tags and makes full use of time in such a reading round. There is no slot waste, and the tag lost ratio \(\alpha=0\). However, when \(n>N\), the time needed to recognize all \(n\) tags is greater than the maximum staying time of these tags. Therefore, some of them may become lost. To balance the tag lost ratio and identification efficiency, the number of admitted tags in each round is critical.