## 4 Tree-Based Protocols
### Manchester Coding
#### 4.4.1 Binary Search Protocol  
The procedure in the Binary Search protocol (BS) algorithm [2; 55] involves transmitting a serial number from the reader to all the tags in the interrogation area. Only tags which have an equal or lower ID value than the received serial number will respond to the request. Then the reader checks the tags' responses bit by bit using Manchester coding and if a collision is detected, the reader divides the tags into subsets based on the collided bits.  
Table 3 shows an example of BS being used to read four tags (Tag A to Tag D). The reader begins by interrogating tags with the maximum ID value 111. Tags with a value of less than 111 will respond to the query. Their answer results in collision XXX, where all three bits have experienced a collision. In the next slot, the reader transmits a new query by replacing the most significant collided bit (MSB) with a 0. The reader transmits a new query, 011, in the next slot, and all tags compare their ID with the received value. Communication in this slot again results in a collision (01X). In the second slot, the reader replaces the third bit of the command with a 0 and transmits the next query, 010. In the new interrogation round (slot 3) only Tag A has a value equal to or lower than 010, and therefore it is successfully identified. After this slot, the reader restarts the query value with the initial value 111 and transmits it. This procedure is repeated until all of the tags are identified.  
\begin{table}
\begin{tabular}{l l l l l l l l} \hline \hline
**Slot Number** & **Reader Command** & \begin{tabular}{l} **Tag A** \\ **(010)** \\ \end{tabular} & \begin{tabular}{l} **Tag B** \\ **(011)** \\ \end{tabular} & \begin{tabular}{l} **Tag C** \\ **(100)** \\ \end{tabular} & \begin{tabular}{l} **Tag D** \\ **(110)** \\ \end{tabular} & \
\begin{tabular}{l} **Result** \\ \end{tabular} &
\begin{tabular}{l} **Type of Slot** \\ \end{tabular} \\ \hline
**Slot 1** & 111 & 010 & 011 & 100 & 110 & XXX & Collision \\
**Slot 2** & 011 & 010 & 011 & & 01X & Collision \\
**Slot 3** & 010 & 010 & & & 010 & Success \\
**Slot 4** & 111 & 011 & 100 & 110 & XXX & Collision \\
**Slot 5** & 011 & & 011 & & 011 & Success \\
**Slot 6** & 111 & & & 100 & 110 & 1X0 & Collision \\
**Slot 7** & 101 & & & 100 & & 100 & Success \\
**Slot 8** & 111 & & & & 110 & 110 & Success \\ \hline \hline \end{tabular}
\end{table}
Table 3: Example of the BS protocol.  
Figure 18: Example of Manchester codification showing a collision at the 2 nd and the 3 rd bits.  
This protocol has two additional versions: Enhanced BS protocol (EBSA) and Dynamic BS protocol (DBSA) [56]. The main difference from EBSA is that it does not restart the reading procedure after a tag is identified, as in the basic version of BS. To reduce bit consumption, in the initial slot, the reader transmits only '1' instead of all '1's. In the DBSA version, the reader uses the knowledge from the last slot and reduces the number of transmitting bits. For example, if the reader has received 01X, it will request the tags to transmit only the last bit, since the initial prefix has already been identified.