## 3 Proposed Channel-Quality Aware Query Tree Algorithm
### The CAQT Algorithm  
For the conventional tree-based collision resolution protocols, when a reader encounters an unreadable slot, this reader would regard collision occurs in this slot and then split the tags into several groups in order to resolve the collision. However, this strategy causes inferior performance because the unreadable slot may result from the channel error. To be more specific, when there is only one tag transmitting in one slot and encountering channel error, the reader would treat this slot as a collision slot and attempt to use more slots to resolve this collision. Nevertheless, only one slot will be used, and remaining slots will be wasted. This study therefore provides a CAQT to overcome above mentioned issue. When a reader encounters an unreadable slot, CAQT will statistically judge whether it is simply due to channel error or it is caused by collision. If this unreadable slot is due to channel error, CAQT will ask the tag to retransmit its message in the next slot. On the other hand, CAQT will treat this unreadable slot as a collision and split the collided tags into several group to resolve the collision. Figure 8 shows the flowchart of CAQT. The basic idea of CAQT is that, for example, when the reader detect a slot of which the status is unreadable, the reader would calculate \(E_{rtx}\) and \(E_{spl}\) to determine whether to ask the tag for retransmission or to split the collided tags. If \(E_{spl}\) is lower than \(E_{rtx}\). When the reader detects an unreadable slot, it then statistically calculates the efficiency. In this case, the slots consumed by the splitting procedure (3 slots) are more than that  
Figure 8: Flowchart of CAQT (Channel-quality Aware Query Tree algorithm). Figure 7: An example of PER (Packet Error Rate) between \(U_{s}^{i-1}\) and \(U_{s}^{i}\). consumed by retransmission (1 slot). Therefore, the reader then asks the tag to retransmit its message immediately. On the other hand, if \(E_{spl}\) is higher than \(E_{rtx}\), the reader would treat this event as the collision and then adopt the Query tree-based algorithm to split the tags. Figure 9 demonstrates the pseudo code of CAQT. Line 3-5 in the Main function and Line 8-10 in the query function as the same as the conventional query tree based algorithm for the initial query. Once an unreadable slot is detected in Line 7, CAQT has to estimate the number of tags (\(\widetilde{m}\)) which transmit their message in this slot. To assume \(\widetilde{m}\) is the margin between the current estimated number of tags within the reader radio coverage (\(\widetilde{N_{curr}}\)) and the previously estimated one (\(\widetilde{N_{pre}}\)) and is therefore the reason resulting in this collision, that is:  
\[\widetilde{m}=\big{|}\widetilde{N_{curr}}-\widetilde{N_{pre}}\big{|}, \tag{3}\]  
The number of the tags within the reader radio coverage (\(\widetilde{N}\)) can be estimated by  
\[\widetilde{N}=\frac{N_{s}}{\Pr(q)} \tag{4}\]  
where \(N_{s}\) is the number of identified tags and \(\Pr(q)\) is the probability to identify the \(N_{s}\) tags through the query string \(q\). Since the procedure to resolve the collided tags is based on Query Tree algorithm, and thus the \(\Pr(q)\) can be estimated by  
\[\Pr(q)=\left(\sum_{i=1}^{\text{length}(q)}\frac{q_{i}}{2^{i}}\right)+\frac{1}{ 2^{\text{length}(q)}} \tag{5}\]  
where \(q_{i}\) is the \(i\)-th character of the query string \(q\) and \(\text{length}(q)\) is the length of the query string \(q\)[32]. It should be noted that the query string \(q\) is a binary string, which is \(q=q_{1}q_{2}...q_{j}...q_{k}\) where \(q_{j}\in\{0,1\}\). Then the reader has to compare the efficiency between asking the tags to retransmit and splitting the collided tags, which are denoted by \(\text{E}_{rtx}\big{(}\widetilde{m},\widetilde{PER}\big{)}\) and \(\text{E}_{spl}\big{(}\widetilde{m},\widetilde{PER}\big{)}\), respectively. The efficiency means the expected number of tags can be transmit in one slot.