# A Filter-Based and Parallel Unknown Tag Identification Protocol in Open RFID Systems
## 4 Filter-Based and Parallel Unknown Tag Identification Protocol
### Separation Phase
#### 4.2.1 Building an RSQF-Based Filter  
The reader first calculates the hash value for each known tag by \(H(id,r_{1})\), where \(id\) is the tag's ID and \(r_{1}\) is a random seed. The RSQF filter divides \(H(id,r_{1})\) into two parts: the first \(q\)-bit part is called _quotient_, denoted by \(h_{0}(id)\), and the second \(r\)-bit part is called _remainder_, denoted by \(h_{1}(id)\). In this paper, the original RSQF filter was modified to make it adapt to our problem. The modified RSQF-based filter maintains a vector _occupieds_ to determine whether a slot is occupied or not. A position \(j\) is occupied and is set to \"1\" when there is at least one tag \(t_{i}\) whose \(h_{0}(id_{i})=j\). The number of \"1s\" in the _occupied_ vector up to position \(j\) is counted as \(s_{j}\), and the total number of \"1s\" in the _occupieds_ vector is counted as \(s\). Furthermore, the RSQF-based filter maintains a vector \(Q\) in which there are \(N\) slots. Each slot with a size of \(r\) bits can store a _remainder_. The _remainders_ of tags with an identical _quotient_ are placed in consecutive slots from small to large. In this paper, this sequence of slots is called a _run_, and the number of tags in a _run_ is called the _runsize_. When a tag \(t_{i}\) is inserted, the RSQF-based filter tries to store its _remainder_\(h_{1}(id_{i})\) in the _home slot_\(Q[s_{h_{0}(id_{i})}]\). Here, the linear probing scheme was adopted to store the _remainders_ in the same _run_. As will be described below, the RSQF-based filter seeks out an unoccupied slot to save \(h_{1}(id_{i})\) when its _home slot_ is already occupied. A slot storing a _remainder_ is called \"used\", and a slot storing no _remainder_ is called \"unused\". Since the RSQF-based filter uses the linear probing scheme to store _remainders_, a slot may also be \"used\" even when its corresponding position in the _occupieds_ vector is not occupied. The RSQF-based filter always attempts to store the _remainders_ in their _home slots_ and only drifts a _remainder_ when its _home slot_ is occupied by another _remainder_. As shown in Figure 2, the RSQF-based filter maintains three vectors to determine whether a slot is \"used\" or not and the actual slot in which each _remainder_ is stored. Specifically, the _occupied_s bit vector with a size of \(2^{q}\) is used to indicate the _home slot_ of each tag, the _runends_ bit vector with a size of \(N\) is used to indicate the number of tags having the same _home slot_, and the _remainders_ vector (namely \(Q\) array) is used to indicate the actual slot of each tag. For the convenience of expression, two operations are defined for the RSQF-based filter: \(SELECT(\cdot)\) and \(RANK(\cdot)\). For a given bit vector \(D\), \(SELECT(D,i)\) returns the index of the \(i\)th 1 in \(D\), and \(RANK(D,i)\) returns the number of 1s preceding the \(i\)th position in \(D\), i.e., \(RANK(D,i)=\Sigma_{j=0}^{i-1}D[j]\). The two operations help seek out the \(run\) of any _quotient_\(h_{0}(id)\). If \(occupids[h_{0}(id)]=0\), there is no such \(run\); otherwise, \(RANK(occupids,h_{0}(id))\) is applied to calculate the number \(s_{j}\) of slots \(j\leq h_{0}(id)\), i.e., the number of \(runs\) preceding the slot \(h_{0}(id)\), and then, \(SELECT(runends,s_{j}+1)\) is applied to calculate the end position of the \(s_{j}\)th \(run\). As shown in Figure 2, the slot of tag \(t_{i}\) is in the \(\{\lambda_{i}\}\)th \(run\), where \(\lambda_{i}=s_{h_{0}(id_{i})}=RANK(occupids,h_{0}(id_{i}))\). The end slot of this \(run\) is \(e_{\lambda_{i}}=SELECT(runends,\lambda_{i}+1)\), and the beginning slot of this \(run\) is \(b_{\lambda_{i}}=SELECT(runends,\lambda_{i})+1\) (we set \(SELECT(runends,0)\) to be \(-1\)). Thus, the size of this \(run\) can be obtained by \(\textit{runsize}_{\lambda_{i}}=e_{\lambda_{i}}-b_{\lambda_{i}}+1\). The actual slot index of tag \(t_{i}\) falls between \(b_{\lambda_{i}}\) and \(e_{\lambda_{i}}\). The tag \(t_{i}\) checks the \(j\)th position in the _remainders_ vector (\(b_{\lambda_{i}}\leq j\leq e_{\lambda_{i}}\)).