## 5 Tag Collision  
By modifying the existing Tree-based algorithm, the proposed communication model resolves the tag collision issue. By reducing idle nodes in the tree, the proposed model increases tag identification time very quickly. A schematic of the query-tree is shown in Figure 11. Based on the tag response, each node in the proposed tree algorithm defines the anti-collision condition. The nodes are categorized into three modes--idle, readable (successful), and collision. These conditions are defined as follows [23; 31]. * _Idle_: There is no transmission as no tag is present in the query zone. * _Readable_: Successful transmission as single tag responds to the query of reader. * _Collision_: Collision occurs as multiple tags respond to the query of the same reader. Tag collision can be more efficiently reduced if binary query tree is improved to M-ary query tree. The same number of tags can be identified in M-ary tree algorithm with a less collision cycle however, number of idle cycles increases as compared to binary query tree [22; 32]. Hence, to further reduce the idle cycles without compromising the tag collision probability, the M-ary Trimming Query tree is proposed in this work. As shown in Figure 10, an M-ary tree is divided into \(M\) groups of bits, highlighted as b\({}_{0}\), b\({}_{1}\) up to b\({}_{\text{m}-1}\). The reader first sends query prefix to tag in communicating zone. The tag responds to the query after comparing with the own ID prefix. Collision bit detection is carried out by Manchester code. If there is collision, reader updates the query prefix and collision node is divided further in the next level into M-groups as illustrated in Figure 10.  
The trimming for the M-ary tree method is carried out in three ways. Consider the value of \(M\) is 8 and the position of the highest collided bit b\({}_{\text{m}-1}\) is 0, then all query nodes with a least significant bit (LSB) value 1 are eliminated and rest of nodes are set as new prefix and added to stack. Inversely, if the the highest collided bit b\({}_{\text{m}-1}\) is 1, then query nodes with LSB value 0 are removed and rest of the nodes are set as new prefix and pushed to stack. If the highest collided bit is unknown then there will be no trimming, it will get forwarded to the subsequent level of the tree. The key parameter of RFID tag identification is total time slot. In an anticollision algorithm, lesser the total time slot, greater the speed of execution of the algorithm. The analytical calculation is compared between conventional M-ary tree and M-ary trimming tree. Root node, intermediate nodes and leaf nodes are the sections of the M-ary query  
Figure 11: Schematic representation of M-ary query trimming tree. trimming tree. The level of leaf node is zero and level of intermediate node is equal to level of the tree e.g., \(M\). Therefore, total nodes of the M-ary tree is [33]:  
\[N{=}~{}n_{0}+n_{M}. \tag{33}\]  
where, \(n_{0}\) is the number of nodes at level 0 and \(n_{M}\) is the number of nodes at level \(M\). The root node is not the child node. Intermediate node has \(M\) number of children nodes and leaf nodes don't have any child node. Thus, total number of nodes of M-ary tree is [33]  
\[N{=}~{}(~{}0\times n_{0})+(M\times n_{M})+1, \tag{34}\]  
Then,  
\[n_{0}+n_{M}=Mn_{M}+1. \tag{35}\]  
Hence, number of leaf nodes and intermediate nodes can be determined as,  
\[n_{0}=(M-1)n_{M}+1, \tag{36}\]  
\[n_{M}=\frac{(n_{0}-1)}{(M-1)}. \tag{37}\]  
Let, \(n\) is the number of tags. The number of leaf nodes is equal to number of tags, which are needed to be identified under the trimming condition as there is no idle slot in this algorithm. Therefore,  
\[n_{0}=n, \tag{38}\]  
\[n=(M-1)n_{M}+1. \tag{39}\]  
Let, at the trimming condition, the probability of getting least collision at the intermediate node is 1.