# Fast and Effective Tag Searching for Multi-Group RFID Systems
## 4 B-Search
### Protocol Description  
Phase I: Initiate the tag searching within a group. The reader broadcasts a group ID. After broadcasting, the tag in the interrogation region checks whether its group ID matches. The matching tags remain active and execute the algorithms of phases II and III. After the tag searching in this group is completed, the reader broadcasts the next group ID to initiate tag searching for the next group. Phase II: Eliminate the interference of non-wanted tags in the group. First, the reader constructs a virtual filter vector by performing multiple hash operations on the wanted tag set. The reader initiates a query with the parameter \(f_{g}\), \(k_{g}\) and \(R_{1}\), where \(f_{g}\) indicates the frame length of this query, \(k_{g}\) indicates the number of independent hash functions used in this query, and \(R_{1}\) denotes the random seed in this query. The different hash functions in the query use the same random seed \(R_{1}\). Based on the slots selected by the wanted tags, the reader can construct a vector. Each bit in the vector corresponds to a slot. The  
Figure 1: Illustration of the tag searching problem in a multi-group RFID system. slot with tag responses is denoted by 1 and without tag responses is denoted by 0. The reader sequentially performs \(l\) queries by random seeds \(\{R_{1},R_{2},\dots,R_{l}\}\) to obtain \(l\) vectors. By synthesizing the information of these vectors, the reader can derive a filtering vector, denoted by \(V_{1}\). If the first bit of the first vector is 0, the first slot in the filter vector \(V_{1}\) is represented by 1. If the first bit of the first vector is not 0, but the first bit of the second vector is 0, the first slot of the filter vector is represented by 2, and so on. If the first bit of all vectors is not 0, the first slot in the filter vector is denoted by 0. In summary, each slot in the filter vector indicates where the first \"0\" occurs. Then, the reader broadcasts the related parameters and filter vectors \(V_{1}\) to the local tags in this group. The local tag performs \(k\times l\) hash operations in turn to select \(k\times l\) slots in \(V_{1}\) for confirming whether it is the non-wanted tag. If the number in the slot it chooses is the same as the number of the random seed it uses, the tag is a non-wanted tag and will be deactivated immediately. Phase III: Determine the target tags in the group. First, the reader assigns all the wanted tags to a slot for verification. The reader initiates many queries on the wanted tag set by some random seed \(\{R^{\prime}_{1},R^{\prime}_{2},\dots\}\), where the frame length is \(f^{\prime}_{g}\). In first query, the reader can acquire an indicator vector based on the slots selected by the wanted tags, denoted by \(V_{2}\). Each bit in the vector corresponds to a slot. The slot with only one wanted tag response is represented by 1, and the rest of the slots are represented by 0. The singleton slot which is selected by only one wanted tag is the verification slot of the wanted tag. The reader then removes the singleton slots and the wanted tags in the singleton slot, and initiates the second query with the remaining wanted tags and new frame length. At the end of the second query, the reader marks the bit in the indicator vector \(V_{2}\) corresponding to singleton slots as 2. The reader no longer performs queries until all the wanted tags are assigned to a singleton slot. Assume that a total of \(h_{g}\) hash operations have been performed with a \(h_{g}\) random seed. Apparently, each bit in the indicator vector \(V_{2}\) refers to the random seed number used by the wanted tag in the slot. The reader then broadcasts the corresponding parameters to the local tags in this group. The tag selects slots using these random seeds in turn and determines its response slot based on whether its corresponding bit in the indicator vector matches its random seed number. After determining the response slot, the tag forms a response vector.