# 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
The whole identification process of ACDQT is also given in Figure 6.  
```
1 initiate \(Q=\{(\varepsilon,0)\}\);
2 while\(Q\) is not emptydo
3 Obtains \((pre,k)=Queueout(Q)\), and broadcasts \(Query(pre,k)\);
4 for\(s=0:2^{k}-1\)do
5 Waits for tag responses and checks state of the slot;
6 ifSingleton slotthen
7 identifies the tag with (9) ;
8 elseifTwo readable slotthen
9 identifies the tags with (10);
10 elseifCollision slotthen
11 obtains \((pre^{\prime},\,k^{\prime})\) with (11) and Queuein(\((pre^{\prime},\,k^{\prime})\), Q);
12 end if
13 Send\(\,Qrep\);
14 end if
15
16 end if
```  
**Algorithm 1**Reader's Operations  
```
1 After receiving \(Query(pre,k)\);
2 if\((d_{1},\,d_{2},\,\,\cdots,\,d_{p})==pre\)then
3\(g=bin2 dec(d_{p+1},d_{p+2},\ldots,d_{p+k})\);
4 if\(g=0\)then
5\(Reply(d_{p+k+1},d_{p+k+2},\cdots,d_{L})\);
6 elseifreceive\(\,Qrep\)then
7\(g=g-1\);
8
9 end if
10
11 else
12 wait for the next \(Query()\) command;
13
14 end if
```  
**Algorithm 2**Tags' OperationsAn Example  
To clearly show the DQTR algorithm, Figure 7 illustrates an example of the identification process for 10 tags, and the tag IDs are given in Table 4. In Figure 7, \(F_{i}\) refers to the \(i\)th frame, and the queue \(Q\) of each frame is also given in the right side. At the beginning, the reader initializes queue \(Q=\{(\varepsilon,0)\}\). In the first frame \(F_{1}\), it obtains parameters from \(Q\) and broadcasts \(Query(\varepsilon,0)\). Note that the initial frame consists of only one collision slot, since all tags will match with prefix \(\varepsilon\). After receiving tags' responses, the decoded message is \"\(xxxxxxxxxx\)\". For the sake of simplicity, we use the first three constitutive colliding bits. Then, the reader sets \(pre=\varepsilon,k=3\), and pushes them into \(Q\). In \(F_{2}\), all tags will participate in this frame. After checking the first three bits of their ID, they obtain slot indices and reply in the corresponding slots. In this frame, \(\text{Tag}_{1}\) and \(\text{Tag}_{2}\) are identified in the two readable slots, i.e., the second slot, \(\text{Tag}_{6}\) and \(\text{Tag}_{10}\) are identified in two singleton slots, i.e., the fifth and seventh slots, respectively. The fourth and sixth slots are two collision slots with \(k=2\) and \(k=1\), respectively. At the end of \(F_{2}\), Q becomes \(\{(011,2),(101,1)\}\). The reader goes through the subsequent frames until  
Figure 6: Flowchart of the proposed ACDQT algorithm: (**a**) the admission control phase with MRAC; (**b**) the identification phase in each round with DQTR. Figure 7: Example of DQTR recognition process. At the end of frame \(F_{2}\), \(Q=\{(011,2),(101,1)\}\), which includes two frame parameters. Next, the reader takes \((011,2)\) from \(Q\) and broadcasts \(Query(011,2)\) to start the third frame \(F_{3}\). There are four time slots in \(F_{3}\), of which the first, second and fourth time slots have only one tag response, and the third time slot is an idle slot. The reader identifies \(\text{Tag}_{4}\), \(\text{Tag}_{5}\) and \(\text{Tag}_{3}\) in these three singleton slots, separately. Then, it continues to take frame parameters \((101,1)\) from \(Q\). In frame \(F_{4}\), two slots are executed. The first slot has only one tag response, and the reader can directly identify \(\text{Tag}_{7}\). The message reply in the second slot is \"\(1110x0\)\", so the reader recognizes \(\text{Tag}_{8}\) and \(\text{Tag}_{9}\) in this two-readable slot. At the end of \(F_{4}\), \(Q\) becomes empty. The reader terminates this reading round. The identification performance of DQTR is compared with two benchmark works, i.e., CT [4] and DPPS [7]. Table 5 lists the number of transmitted message bits on both the reader and tag sides as well as the total identification time. As can be observed, the proposed DQTR algorithm transmits the least number of message bits on both the reader and tag sides, and it also takes the least time to identify all tags.