# An Admission-Control-Based Dynamic Query Tree Protocol for Fast Moving RFID Tag Identification
## 5 Performance Analysis  
In mobile systems, ACDQT performs two key strategies, i.e., multi-round admission control (MRAC) and dynamic query tree recognition (DQTR), to accelerate the identification efficiency. In MRAC, the number of admitted tags is controlled to facilitate the identification of each round. Therefore, the overall system efficiency highly depends on the identification process in each round. In this section, we analyze the performance of DQTR in each round based on probability theory and classical tree analysis methods [33; 34; 35]. In DQTR, all tags will reply in the initial slot. As demonstrated in Figure 7, if there is more than one tag replying simultaneously, a collision slot occurs. The colliding tags will be split into small subsets according to the number of consecutive colliding bits after the maximum common prefix, i.e., they will attend a new frame in the next layer of the tree. Let \(P_{kc}(i,k)\) be the probability that there are \(k\) consecutive colliding bits after the maximum common prefix when \(i\) tags reply in the slot. Then, the number of slots needed to identify \(n\) tags using DQTR in each round is given by  
\[S(n)=1+\sum_{k=1}^{L-p}P_{kc}(n,k)\cdot S_{k}(n,k), \tag{12}\]  
where \(L\) and \(p\) are the lengths of the tag ID and the maximum common prefix of colliding tags, respectively. \(S_{k}(n,k)\) is the number of slots needed to identify \(n\) colliding tags when the number of consecutive collision bits in tag responses is \(k\). \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Tag** & **ID** & **Tag** & **ID** & **Tag** & **ID** & **Tag** & **ID** \\ \hline \(Tag_{1}\) & 0011000111 & \(Tag_{2}\) & 0011100111 & \(Tag_{3}\) & 0111101101 & \(Tag_{4}\) & 01100010 \\ \hline \(Tag_{5}\) & 01100111 & \(Tag_{6}\) & 1000011010 & \(Tag_{7}\) & 1010100010 & \(Tag_{8}\) & 1011111010 \\ \hline \(Tag_{9}\) & 1011111000 & \(Tag_{10}\) & 1101100111 & & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 4: \(\text{Tags}^{\prime}\) ID information. \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Message** & **Message** \\  & **Transmitted** & **Transmitted** \\  & **by Reader (bit)** & **by Each Tag (bit)** & **Time (s)** \\ \hline CT & 1028 & 191 & 0.0201 \\ \hline DPPS & 585 & 152 & 0.0143 \\ \hline DQTR & **425** & **131** & **0.0124** \\ \hline \hline \end{tabular} The bold values are the least cost in each column.  
\end{table} 
Table 5: Compared with CT and DPPS. Assume that \(i\) tags reply in the same slot. There should be at least one colliding bit in the received message. In a specific bit position, if the corresponding bit of all response messages are the same, i.e., all zeroes or ones, this bit position is not colliding. Thus, the probability that a specific bit position is colliding can be expressed as  
\[P_{b}=1-\frac{1}{2^{i}}\cdot 2=1-\frac{1}{2^{(i-1)}}. \tag{13}\]  
In a collision slot, there is at least one colliding bit. Thus, the probability of the first colliding bit in tag responses in a collision slot with \(i\) tags is \(P_{bc}(i,1)=1,\ i>1\). If the number of consecutive colliding bits \(k\) is greater than one, that means the 2 nd to \(k\)th bits are all colliding bits. Therefore, in a collision slot with \(i\) attending tags, the probability that \(k\) consecutive colliding bits exist after the maximum common prefix is obtained by  
\[P_{bc}(i,k)=p_{b}^{k-1}\cdot(1-p_{b})=\left(1-\frac{1}{2^{i-1}}\right)^{k-1} \cdot\frac{1}{2^{i-1}},\ \ k>1. \tag{14}\]  
Note that in a collision slot, there should be at least one colliding bit, i.e., the colliding bit after the maximum common prefix. In a collision slot with \(k\) consecutive colliding bits after the maximum common prefix, the tags will be split into \(2^{k}\) sets and will attend \(2^{k}\) slots in the subsequent frame. Assume the event that a tag assigned to a specific slot follows the binomial distribution as most previous works [5; 6; 7; 15].