# A Filter-Based and Parallel Unknown Tag Identification Protocol in Open RFID Systems
## 5 Performance Analysis
### Time Efficiency  
In this section, the time efficiency of the FPUI protocol is analyzed. The execution time comprises two parts: the separation time and the collection time. The total execution time is given as:  
\[T_{t}=T_{sep}+T_{col}, \tag{5}\]  
where \(T_{sep}\) is the separation time and \(T_{col}\) is the collection time. The separation time \(T_{sep}\) is represented as:  
\[ \begin{split} T_{sep}&=\frac{2^{q}+N\times(l_{fp}+ 1)}{96}\times t_{id}\\ &=(2^{q}+(l_{fp}+1)N)\frac{t_{id}}{96},\end{split}  \tag{6}\]  
where \(t_{id}\) is the time for transmitting 96-bit information from the reader to the tags, \(q\) is the size of _quotient_, \(N\) is the number of known tags, and \(l_{fp}\) is the average length of the fingerprint. The number \(\eta\) of bits per tag is defined as:  
\[ \begin{split}\eta&=\frac{2^{q}}{N}+(l_{fp}+1)\\ &=\frac{1}{\rho_{1}}+\lceil log_{2}\frac{\rho_{1}}{(1-e^{-\rho_{1 }})}\rceil+1.\end{split}  \tag{7}\]  
\(\eta\) is minimized to obtain the optimal space efficiency. Then, the optimal parameter \(\rho_{1}\) for minimizing \(\eta\) is investigated. The derivative of \(\eta\) can be given as follows:  
\[\frac{\partial\eta}{\partial\rho_{1}}=-\frac{1}{\rho_{1}^{2}}+\frac{1}{\rho_{ 1}ln2}-\frac{e^{-\rho_{1}}}{(1-e^{-\rho_{1}})ln2}. \tag{8}\]  
By setting the derivatives in Equation (8) to 0, the lowest space efficiency is obtained when \(\rho_{1}\) is 1.3. Then, the reader takes 1.93 bits to deactivate one known tag and the average fingerprint \(l_{fp}=2\). Figure 5(a) shows the changes of unit execution time \(\delta\) with respect to \(\rho\). Therefore, the minimum separation time is:  
\[T_{sep}^{min}=\frac{1.93t_{id}}{96}N\text{ms}=0.02 Nt_{id}\text{ms}. \tag{9}\]  
Then, the collection time \(T_{col}\) is discussed. Considering the \(i\)th round of _unknown tag IDs' collection_, the collection time, denoted by \(T_{col}^{i}\), is expressed as follows:  
\[T_{col}^{i}=M_{i}\times t_{s}+\frac{f_{i}+l_{s}^{i}\times m}{96}\times t_{id} +\lceil\frac{l_{s}^{i}}{m}\rceil\times t_{tag}^{\prime}, \tag{10}\]  
where \(M_{i}\), \(f_{i}\), and \(l_{s}^{i}\) are the number of participating unknown tags, the frame size, and the number of singleton slots in the \(i\)th round, respectively; \(t_{s}\) is the time for the tag transmitting 1 bit of information to the reader; \(t_{tag}^{\prime}\) is the time for transmitting a 96-bit ID from the tag to the reader. Note that \(t_{id}\) and \(t_{s}\) were based on the traditional _FM0_ code, and \(t_{tag}^{\prime}\) was based on the _CDMA_ code. The probability of mapping one unknown tag to a singleton slot in this round is denoted as \(P_{s}^{i}\), which is given as follows:  
\[ \begin{split} P_{s}^{i}&=M_{i}{\times}\frac{1}{f_{i}} {\times}(1-\frac{1}{f_{i}})^{M_{i}-1}\\ &=\rho e^{-\rho},\end{split}  \tag{11}\]  
where \(\rho=\frac{M_{i}}{f_{i}}\). Therefore, \(l_{s}^{i}=f_{i}{\times}\rho e^{-\rho}\). This paper defines the unit collection time \(\delta\) as the ratio of the collection time to the number of identified tags in the \(i\)th round. Therefore, we have:  
\[ \begin{split}\delta&=\frac{M_{i}{\times}t_{s}+ \frac{f_{i}\rho e^{-\rho}m}{\eta_{6}}{\times}t_{id}+\lceil\frac{f_{i}{\times} \rho e^{-\rho}}{m}\rceil{\times}t_{tag}^{\prime}}{f_{i}\rho e^{-\rho}}\\ &\approx e^{\rho}t_{s}+(\frac{e^{\rho}}{\rho}+m)\frac{t_{id}}{96} +\frac{t_{tag}^{\prime}}{m}.\end{split}  \tag{12}\]  
Here, \(\delta\) needs to be minimized to achieve the shortest collection time. Next, the optimal parameter \(\rho\) is found to minimize \(\delta\). The derivative of \(\delta\) is calculated as follows:  
\[\frac{\partial\delta}{\partial\rho}=e^{\rho}t_{s}+\frac{e^{\rho}(\rho-1)}{ \rho^{2}}\frac{t_{id}}{96}. \tag{13}\]  
Based on the Philips I-Code system [20] and the _CDMA_ code, we have \(t_{id}=2.4\) ms, \(t_{tag}=2.3\) ms, \(t_{l}=0.8\) ms, and \(t_{s}=0.4\) ms. By setting the derivative in Equation (13) to 0, the minimum unit collection time is obtained when \(\rho\) is 0.22.