# Fast and Effective Tag Searching for Multi-Group RFID Systems
## 3 Preliminary
### Problem Statement  
Assume that the tags in the interrogation region are divided into \(G\) groups, with no overlap between groups. Each group has a group ID as a unique identification for the group. According to the knowledge of traditional tag searching, the local tag set represents the set of tags in the interrogation region, denoted by \(L\). We suppose that the reader only knows the number of local tags in group \(g\), denoted by \(|L_{g}|\), and does not know anything else about them. We use \(W\) to denote the set of wanted tags, which represent the tags that we are interested in, and we want to check whether they are in the interrogation region. The reader not only knows the number of wanted tags in group \(g\), denoted by \(|W_{g}|\), but also knows the IDs of the wanted tags in group \(g\), \(g\in\{1,2,...,G\}\). That is to say, the group state of the wanted tags is known, while the group state of the local tags is unknown. However, since the tag grouping is completed according to the actual situation before the tags are put into application, the reader has the knowledge of all group IDs. Moreover, the ultimate goal of tag searching is to determine the intersection of local tags and wanted tags in group \(g\), and we refer to the tags in the intersection as target tags, represented by \(T_{g}\), i.e., \(T_{g}=W_{g}\bigcap L_{g}\). The reader can obtain the number of target tags in each group, denoted by \(|\bar{T}_{g}|\), through performing the target tag estimation protocol. In addition, we refer to the tags in the local tag set except for the target tags as non-wanted tags, and the tags in the wanted tag set except for the target tags as non-target tags. Figure 1 briefly illustrates the tag searching problem in a multi-group RFID system.  
We are interested in tag searching event for each group. In other words, multi-group tag searching protocols need to discover the common part of the local tag set and the wanted tag set in group \(g\) under the predefined reliability requirement.  
**The multi-group tag searching problem is defined as:** In a large-scale RFID system with \(G\)-group tags, given a wanted tag set, determine \(T_{g}=W_{g}\bigcap L_{g}\) for group \(g\) with the minimum time while satisfying the following two requirements:  
1. All target tags for group \(g\) in the interrogation region must be identified. To put it simply, for group \(g\), the final searching result \(T_{g}^{*}\) must contain all the target tags, i.e., \(T_{g}\subseteq T_{g}^{*}\).
2. The tag searching result for group \(g\) has to satisfy the predefined reliability requirement \(P_{req}\)\((0<P_{req}<1)\), namely \[\frac{|T_{g}^{*}-T_{g}|}{\min(|W_{g}|,|L_{g}|)}\leq 1-P_{req},\] (1) where \(|\cdot|\) denotes cardinality of the set and \(g\in\{1,2,\ldots,G\}\). The phenomenon that the target tags in tag searching results are more than target tags in practice is due to the false positive during the tag searching, which means non-target tags and non-wanted tags are mistaken for target tags. Equation (1) indicates that the probability of the appearance of the false positive tags should be within the allowable range of reliability. Other than that, we define the target tag ratio as \(\lambda\), i.e., \(\lambda=\frac{|T_{g}|}{\min(|W_{g}|,|L_{g}|)}\) and the group interval as \(r\). Group interval is the increment size of the number of tags between different groups.