# An Admission-Control-Based Dynamic Query Tree Protocol for Fast Moving RFID Tag Identification
## 5 Performance Analysis
The probability that \(i\) tags are assigned into one slot in a frame with \(2^{k}\) slots is given by  
\[P(i,2^{k})=C_{n}^{i}\bigg{(}\frac{1}{2^{k}}\bigg{)}^{i}\bigg{(}1-\frac{1}{2^{k }}\bigg{)}^{n-i}. \tag{15}\]  
Since all collision slots will split in the same way, the number of slots in subsequent frames can be calculated with the following iterative function:  
\[S_{k}(n,k)=2^{k}\bigg{\{}P(0,2^{k})+P(1,2^{k})+\sum_{i=2}^{n}P(i,2^{k})\sum_{j =1}^{L-p^{\prime}}P_{bc}(i,j)S_{k}(i,j)\bigg{\}} \tag{16}\]  
where \(p^{\prime}\) is the length of maximum common prefix of the colliding tags and it varies in different slots, and \(2^{k}\) is the frame length of the stretched frame when the number of consecutive colliding bits is \(k\). Note that \(S_{k}(2,k)\leq 2\). Substituting (14), (15) and (16) to (12), the number of slots needed to identify \(n\) tags by DQTR in each round is obtained. Then, the slot efficiency is given by \(n/S(n)\). Since different types of slots will occupy various time intervals (for example, a collision slot takes much longer time than an idle slot), the slot efficiency cannot effectively evaluate the performance of a practical RFID system. So, we also consider the average identification time to recognize one tag as follows,  
\[T_{ave}=\frac{S_{succ}(n)T_{succ}+S_{idle}(n)T_{idle}+S_{coll}(n)T_{coll}}{n}, \tag{17}\]  
where \(S_{succ}(n)\) is the number of singleton and two-readable slots, and \(S_{idle}(n)\) and \(S_{coll}(n)\) are the numbers of idle and collision slots, respectively. In a deterministic algorithm, all tags will be recognized. We have \(S_{succ}(n)\leq n\). The values of \(S_{coll}\) and \(S_{idle}\) can also be calculated with similar analysis of \(S(n)\). As shown in Figure 7, the number of collision slots needed to identify \(n\) tags consists of the initial collision slot on top of the tree and the collision slots in subsequent frames in each layer of the tree. The second layer consists of only one frame, and its frame length depends on the number of consecutive colliding bits after the maximum common prefix in the initial slot. Participating tags in this slot are assigned to a stretched frame (i.e., tree branch)according to their slot indexes obtained from their IDs. Let \(S_{coll}^{k}(n,k)\) be the number of collision slots needed to identify \(n\) colliding tags when the number of consecutive colliding bits after the maximum common prefix is \(k\). The total number of collision slots is given by  
\[S_{coll}(n)=1+\sum_{k=1}^{L-p}P_{bc}(n,k)S_{coll}^{k}(n,k), \tag{18}\]  
In each frame, the attending tags are randomly assigned to each slot. If more than one tag is grouped into the same slot, these tags will repeat this process in a new frame in lower layers of the tree. Then, we can obtain  
\[S_{coll}^{k}(n,k)=2^{k}\sum_{i=2}^{n}P(i,2^{k})\sum_{j=1}^{L-p^{ \prime}}P_{bc}(i,j)S_{coll}^{k}(i,j), \tag{19}\]  
where \(2^{k}\) is the number of slots in the frame. If two tags reply in the same slot, there should be a collision or a two-readable slot. If it is a two-readable slot, the two tags can be identified directly. Otherwise, they will be split into two subsets according to the position of the first colliding bit and be recognized in two singleton slots. Then, we have \(S_{coll}^{k}(2,j)=1\). Resolving (19) with an iterative method and substituting the results into (18), the number of collision slots is obtained. Next, as shown in Figure 7, idle slots will occur if no tags are assigned. Thus, the number of idle slots in the second layer, i.e., the frame stretched from the initial collision slot, is given by  
\[S_{idle}=\sum_{k=1}^{L-p}P_{bc}(n,k)S_{idle}^{k}(n,k). \tag{20}\]  
In each subsequent frame, the probability that an idle slot occurs is \(P(0,2^{k})\) and that of a collision slot is \(P(i,2^{k}),\ i\geq 2\). Each collision slot will stretch a new branch (i.e., frame).