# Fast and Effective Tag Searching for Multi-Group RFID Systems
## 4 B-Search
### Parameter Optimization  
First, the reader needs to broadcast the group ID to notify the tags in the group performing tag searching. \(T_{0}\) denotes the time taken to broadcast the group IDs:  
\[T_{0}=16\cdot G\cdot T_{s}. \tag{2}\]  
Figure 2: Illustration of the B-Search tag searching protocol. B-Search protocol performs tag searching sequentially in groups. Only one group is searched at a time. Thus, we can take the \(g\)-th group as an example for parameter optimization. Actually, the filter vector \(V_{1}\) is an important method for non-wanted tag deactivation, which is obtained by combining multiple vectors. The probability that any bit in a vector equals 1 is denoted by \(P_{v}\), which is calculated as follows:  
\[P_{v}=1-\left(1-\frac{1}{f_{g}}\right)^{k_{g}\cdot|W_{g}|}\approx 1-e^{-\frac{k_{g }\cdot|W_{g}|}{f_{g}}}. \tag{3}\]  
Subsequently, if the third bit of the filter vector \(V_{1}\) is equal to \(r\), it means that the third bits in the vectors constructed by the first \(r-1\) queries in the phase II all equal 1, and the third bit in the vector constructed by the \(r\)-th query equals 0. It represents the third bit in the vector constructed by the \(r\)-th query is adopted by the filter vector \(V_{1}\). A non-wanted tag cannot be deactivated if all slots that the tag selects are not adopted by the filter vector \(V_{1}\). We denote the probability that a non-wanted tag will not be deactivated as \(P_{d}\). As we know,  
\[P_{d}=\prod_{r=1}^{l}\left(1-(1-P_{v})\cdot P_{v}^{r-1}\right)^{k}. \tag{4}\]  
Thus, the number of non-wanted tags in the \(g\)-th group that are not deactivated is \(P_{d}\cdot(|L_{g}|-|T_{g}|)\). In multi-group tag searching, the search results for each group need to satisfy predefined reliability requirements \(P_{req}\), so  
\[\frac{P_{d}\cdot(|L_{g}|-|T_{g}|)}{\min(|W_{g}|,|L_{g}|)}\leq 1-P_{req}. \tag{5}\]  
As shown in Equation (5), we need to choose the appropriate parameters \(l\), \(k\), and \(f_{g}\), so that \(P_{d}\) satisfies the reliability requirements. In [14], [PERSON] et al. revealed that, when \(l\geq 3\), the decrease of \(P_{d}\) is not significant as \(l\) increases through simulations. Therefore, it is quite appropriate for us to set \(l\) to 3. The time spent by the \(g\)-th group in phase II is denoted as \(T_{g}\), which is  
\[T_{g}=\left(1+\lceil\frac{f_{g}\cdot\lceil log_{2}(l+1)\rceil}{96}\rceil \right)\cdot T_{tag}. \tag{6}\]  
We can find the optimal frame length \(f_{g}^{*}\) and the number of hash functions \(k^{*}\) by integer programming. \[ \begin{split}&(k^{*},f_{g}^{*})=\operatorname*{arg\,min}_{k,f_{g}} \left(\left(1+\lceil\frac{f_{g}\cdot\lceil log_{2}(l+1)\rceil}{96}\rceil \right)\cdot T_{tag}\right),\\ &\text{ }s.t.\quad\left\{\begin{array}{l}k\in N^{+},f_{g}\in N^{+}\\ P_{d}\leq(1-P_{req})\cdot\frac{\min(|W_{g}||L_{g}|)}{(|L_{g}|-|T_{g}|)}\end{array} \right.,\end{split}  \tag{7}\]  
where \(N^{+}\) denotes the set of positive integers. In phase III of B-Search, we only need to determine the frame length \(f_{g}^{\prime}\). Because the response vectors of all local tags are packaged into some 96-bit messages, \(f_{g}^{\prime}\) can be taken as:  
\[f_{g}^{\prime}=\lceil\frac{|W_{g}|}{96}+p\rceil\cdot 96\qquad p\in N^{+}, \tag{8}\]where \(p\) is an adjustment factor. We denote the time spent of the \(g\)-th group in the target tag verification phase by \(T_{g}^{\prime}\). It is easy to know that:  
\[ \begin{split} T_{g}^{\prime}&=\left(\lceil\frac{f_{g}^ {\prime}\cdot\lceil\log_{2}(h_{g}+1)\rceil}{96}\rceil+1\right)\cdot T_{tag}+ \lceil\frac{f_{g}^{\prime}}{96}\rceil\cdot T_{tag}\\ &\leq\left(\lceil\frac{\lceil\log_{2}(h_{g}+1)\rceil}{96}\rceil +2\right)\cdot\lceil\frac{f_{g}^{\prime}}{96}\rceil\cdot T_{tag}\\ &\approx\lceil\frac{\log_{2}(h_{g}+1)}{96}+2\rceil\cdot\left( \lceil\frac{|W_{g}|}{96}\rceil+p\right)\cdot T_{tag}.\end{split}  \tag{9}\]  
From the analysis of [PERSON] et al. in [14], we know that \(T_{g}^{\prime}\) can be taken to the minimum value when \(p=0\).