## 4 Tree-Based Protocols
### Manchester Coding
#### 4.4.3 Optimal Query Tracking Tree Protocol  
The Optimal Query Tracking Tree protocol (OQTT) divides all of the tags in the interrogation area into small tag sets in order to reduce the number of collisions at the beginning of the identification  
Figure 19: Example of the CT protocol. process [58]. This protocol uses three main approaches: bit estimation, an optimal partition, and a query tracking tree. With bit estimation, the reader, using bit tracking technology, can estimate the number of tags in the interrogation area with a small deviation. This phase detects the status of the bits to perform the estimation. The reader broadcasts the parameter \(l\), which denotes the default value of the tag ID length. After receiving a command, all tags must randomly choose a value \(k\) between 0 and \(l-1\). To simplify the procedure, the tags only respond with a bit string of length \(b\), instead of a bit string of length \(l\). All tags generate a b-string of all \"0\" and set the bit k mod b to \"1\". Accordingly, the reader can compute the number of selected bits (NSB), and the number of non-selected bits (NNB) from the tags' responses. The probabilities of bits being selected or of being non-selected are calculated from the expressions presented in (2). Finally, the optimal estimation of the number of tags is denoted by \(\tilde{n}\) and is calculated from (3). \[ \begin{split} Pr_{NB}(n,l)=(1-\frac{1}{l})^{n}\\ Pr_{SB}(n,l)=1-Pr_{NB}(n,l)\end{split}  \tag{3}\]  
\[ \begin{split}\tilde{n}(l,N_{NB},N_{SB})=\arg\min_{n}\left|\begin{pmatrix} l\times Pr_{NB}(n,l)\\ l\times Pr_{SB}(n,l)\end{pmatrix}-\begin{pmatrix}N_{NB}\\ N_{SB}\end{pmatrix}\right|\end{split}  \tag{4}\]  
The next approach is an optimal partition which determines the number of initial sets. The reader divides the tags into different sets with initial queries. The query tracking tree is the last procedure in OQTT, and splits the set of collided tags into two subsets using the first collided bit of the tags' responses. This procedure is followed until no more queries remain in the stack. The queries in the optimal partition are calculated using the equations \(c_{1}+c_{2}=m\) and \(2c_{1}+c_{2}=2l\), where \(c_{1}\) denotes the number of \((l-1)\)-bit queries and \(c_{2}\) the number of \(l\)-bit queries. The number of bits in each query is computed from the equations \(2l-1<m\leq 2l\). Table 4 shows an example of OQTT. In the interrogation area there are 5 tags, whose IDs are as follows: '1010', '1100', '0100', '0010' and '0111'. At the beginning of the frame, the reader estimates the number of tags, which here is \(\widetilde{n}=5\). By using this estimate for the number of tags, the initial number of sets is calculated with the formula \(m=\left\lceil 0.595824\times\widetilde{n}\right\rceil\), which yields 3. When \(m=3\), there are two 2-bit queries and one 1-bit query. The reader generates the queries 00, 01 and 1 and pushes them into the stack. In the presented example, \(c_{2}=2\) (queries 00 and 01) and \(c_{1}=1\) (query 1). As presented in Figure 11, when the reader pops a query, the tags answer with the value \(k-q\), where \(k\) and \(q\) are the lengths of the ID and the query, respectively. When a collision occurs, this protocol splits the collided query according to the first collided bit. This is the case with slots 3, 4, 5, and 6. \begin{table}
\begin{tabular}{l l l l l l l l l} \hline \hline
**Slot** & **Query** & \multicolumn{6}{c}{**Tag Response**} \\ \hline  & & **Tag A** & **Tag B** & **Tag C** & **Tag D** & **Tag E** & **Status** & **Stack** \\  & **Est.** & & & & & & & **00,01,1** \\ \hline
**1** & 00 & & & & 10 & & Identified & 01,1 \\
**2** & 01 & & & 00 & & 11 & Collision & 010,011,1 \\
**3** & 010 & & & 0 & & Identified & 011,1 \\
**4** & 011 & & & & 1 & Identified & 1 \\
**5** & 1 & 010 & 100 & & & Collision & 10,11 \\
**6** & 10 & 10 & & & & Identified & 11 \\
**7** & 11 & & 00 & & & Identified & empty \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Example of the OQTT protocol.