## 3 Identification Process in Mixed Scenarios
### Markovian Analysis  
The state of an identification process in a static and a mixed scenario is determined by the number of remaining unidentified tags. Thus, the identification process can be modeled as a homogeneous DTMC, \(X_{s}\), where each state of the chain represents the number of unidentified tags, being \(s\) the frame number. Thus, the state space of the Markov process is \(\{N,N-1,\ldots,0\}\), being \(N\) the number of tags to identify. Figure 1 shows a partial DTMC state diagram from the initial state, \(X_{0}\) = \(N\). The transitions between states is governed by the probability of identifying a certain quantity of tags \(t\) in a given frame or, in other words, the probability of going from state \(i\) to an state with \((i-t)\) tags still unidentified. Let us remark again that we are considering the number of tags identified in a frame so a maximum of \(t=K\) tags can be identified in a frame.  
The transition matrix \(P\) (as usual \(p_{ij}\) denotes the probability of going from state \(i\) to state \(j\)) depends on the anti-collision protocol used and its parameters. To compute the transition matrix \(P\) in FSA, let us denote \(K\) as the number of slots per frame (frame length), and let us define the random variable \(\mu_{t}\), which indicates the number of slots being filled with exactly \(t\) tags in a reading frame.  
When \(t=1\), \(\mu_{1}\) provides the number of slots with a successful identification for a given frame length and contending tags. Its probability mass function is given by (see [23]):  
\[P_{K,N}(\mu_{1}=m)=\frac{K!N!}{m!K^{N}}\sum_{z=0}^{N-m}\frac{(-1)^{z}(K-m-z)^{ N-m-z}}{(N-m-z)!z!(K-m-z)!} \tag{1}\]  
That is, \(P_{K,N}(\mu_{1}=m)\) provides the probability that \(m\) slots have a single reply with a frame length of \(K\) slots and \(N\) tags contending. Recall from the introduction that \(K\) denotes the number of slots per  
Figure 1: Partial Markov Chain.  
frame. Thus, taking into account that tags identified in a frame will not contend in the following ones, the transition matrix \(P\)[24] is:  
\[p_{i,j}=\begin{cases}P_{K,i}(\mu_{1}=i-j)&\text{, }i-K\leq j\leq i\\ 0&\text{, otherwise}\end{cases} \tag{2}\]  
for \(i=0,\ldots,N\).  
The Markov chain clearly has a single absorbing state, \(X_{s}=0\). That is, all tags are identified after an arbitrary long time period. The mean number of steps until the absorbing state is the mean number of identification frames \((\bar{s})\). It can be computed by means of the fundamental matrix, \(D\), of the absorbing chain [25]. \(D\) is obtained from the canonical form [26] of the transition probability matrix \(P\). In our case, since there is only one absorbing state \(P\) has the form:  
\[P=\left(\begin{array}{c|c}F&Q\\ \hline 0&1\end{array}\right) \tag{3}\]  
where \(F\) denotes the sub-matrix of \(P\) with the all the transient states (note that the size of \(F\) is \(N\times N\)). Thus, the fundamental matrix \(D\) is:  
\[D=(I_{N}-F)^{-1} \tag{4}\]  
being \(I_{N}\) the identity matrix of size \((N\times N)\).  
From \(D\) the average number of identification frames \(\bar{s}\) can be calculated as follows:  
\[\bar{s}=\sum_{y=1}^{N}D_{1,y} \tag{5}\]  
That is, the sum of the elements of the first row in \(D\).  
Besides, the corresponding mean number of slots is \(\bar{L}\) = \(\bar{s}\cdot K\) since the frame length is constant.