# 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
### Dynamic Query Tree Recognition Algorithm  
In this section, we propose a dynamic query tree recognition (DQTR) algorithm to effectively identify tags in each round. DQTR follows the query tree recognition process with multiple branches. In general, the reader divides tags in each colliding slot with the help of consecutive colliding bits in the tags' responses. When the reader detects a collision, it first checks the position of the first colliding bit \(p\) and the number of consecutive collision bits \(k\) after this position. Then, it divides colliding tags into \(2^{k}\) subsets to accelerate the identification process. Compared with existing bit tracking protocols, DQTR solves colliding tags with a more flexible and appropriate manner which significantly reduces time costs. The detailed algorithm is given as follows. At the beginning of a reading round, the reader initializes queue \(Q=\{(\varepsilon,0)\}\). Then, it obtains \((\mathit{pre},\ k)=Queueout(Q)\) and broadcasts \(\mathit{Query}(\mathit{pre},k)\) to start the first frame. Note that \(Queueout(Q)\) is to obtain the first item and delete it from queue \(Q\). On receiving the reader's _Query_ command, tags execute matching, indexing and replying operations in sequence as shown in Figure 5.  
* _Matching_: A tag first compares its ID with the matching prefix _pre_. If it matches, the tag transits to the transmission state and will participate in the current frame. Otherwise, it waits for the next _Query_ command. * _Indexing_: If a tag is in the transmission state, it checks the slot index from \(p+1\) to \(p+k\) bits in its ID and converts into a decimal number \(g\), i.e., \[g=bin2 dec(d_{p+1},d_{p+2},\cdots,d_{p+k})\] (8)
* _Replying_: If \(g=0\), the tag replies its remaining ID, i.e., \((d_{p+k+1},d_{p+k+2},\cdots,d_{L})\), to the reader. Otherwise, it waits for the reader's _Qrep_ command, and reduces \(g\) byone after receiving this command until zero. After receiving tags' responses in each slot, the reader determines the state of the current slot and identifies tags. In summary, there are four types of slots to appear. * _Singleton slot_: If there is only one tag reply, the received message can be successfully decoded. Then, the reader identifies the tag and recovers its ID with \[pre\;||\;dec2 bin(g,k)\;||\;(d_{p+k+1},\;d_{p+k+2},\;\cdots,\;d_{L})\] (9) where \(||\) is the concatenating operation. * _Two readable slot_: There are replies from two tags in the slot, and the received message contains only one colliding bit. Since the tag's ID is unique, the reader can recognize the two tags in one slot. For example, the message received by the reader is \"10x101\", where \"\(x\)\" is the colliding bit. The two tag IDs to be identified are \[ID=pre||dec2 bin(g,k)||\{ \begin{subarray}{c}101101\\ 1010101\end{subarray} \] (10)
* _Idle slot_: If the reader receives no message at the slot, it is an idle slot. * _Collision slot_: When more than two tags reply simultaneously in the slot, a collision slot occurs since the reader cannot recover any ID information. In this slot, the reader checks the position of the first colliding bit and the number of consecutive colliding bits after this position. Next, it obtains the parameters for subsequent frames. For  
Figure 5: Tag’s operation after receiving the reader’s Query command. example, if the decoded message is \"1 xx01\", the frame parameters are obtained by calculating  
\[pre^{\prime}=pre||+dec2 bin(g,\,k)||1,\,k^{\prime}=2. \tag{11}\]  
Then, the reader pushes \((pre^{\prime},\,k^{\prime})\) to \(Q\). After executing all slots in the current frame, the reader checks whether \(Q\) is empty. If \(Q\) is empty, it terminates the identification of this round since all the tags are identified. Otherwise, it obtains frame parameters \((pre,k)\) by \(Queueout(Q)\) and sends \(Query(pre,k)\) command to start the next frame. More specifically, Algorithms 1 and 2 give the pseudo-codes of the reader's and tags' operations in DQTR, respectively.