## 4 Analysis of Reservation Frame Slotted-ALOHA
### Discrete-Time Absorbing Markov Chain  
The contention process of RFSA can be modeled with a discrete-time absorbing Markov chain. The generalized state transition diagram is depicted in Figure 2, respectively, for the case where the number \(n\) of end-devices is greater than the number \(m\) of slots and for the case where the number \(n\) of end-devices is lower or equal to the number \(m\) of slots. Each state of the chain is defined by \(\{c(t),f(t)\}\), where \(c(t)\in\{0,1,...,n\}\) and \(f(t)\in\{0,1,...,m\}\) are stochastic processes that represent the number of end-devices that are contending to transmit their first data packet and the number of free slots at time \(t\), respectively. Then, the number of reserved slots at time \(t\) can be represented by \(r(t)=m-f(t)\). A discrete time scale is adopted, _i.e._, \(t\) and \(t+1\) correspond to the beginning of two consecutive frames. The process starts at \(t=1\), where \(c(t)=n\) and \(f(t)=m\), _i.e._, the initial state is \((n,m)\), and it finishes at the absorbing state \((0,m)\). By observing the state transition diagrams depicted in Figure 2, the total number \(K\) of states can be calculated as:  
\[K= \begin{cases}\left(\frac{m}{2}\right)\left(m+1\right)+\left(n-m+1\right)m+1,&if\left(n>m\right)\\ \left(\frac{n+1}{2}\right)\left(n+2\right),&if\left(n\leq m\right)\end{cases}  \tag{1}\]  
The process changes from state \((c_{i},f_{i})\) to state \((c_{j},f_{j})\) in one-step, with \(i,j\in\{1,2,...,K\}\), when the following two conditions are met:  
Condition \(1\): A number of contending end-devices succeed in transmitting their first data packet, denoted by \(S_{ij}\), which can be expressed as the difference between the number of contending end-devices in both states,  
\[S_{ij}= \begin{cases}c_{i}-c_{j},&if\left(c_{i}>c_{j}\right)\\ 0,&otherwise\end{cases}  \tag{2}\]  
and \(S_{ij}\in\{0,1,...,\max\left(S_{ij}\right)\}\), where \(\max\left(S_{ij}\right)\) is the maximum number of contending end-devices that can succeed in one frame. Formally, \(\max\left(S_{ij}\right)\) can be defined as:  
\[\max\left(S_{ij}\right)= \begin{cases}0,&if\left(f_{i}=1\right)and\left(c_{i}> 1\right)\\ f_{i}-1,&if\left(c_{i}>f_{i}\right)\\ c_{i},&if\left(c_{i}\leq f_{i}\right)\end{cases}  \tag{3}\]Condition \(2\): A number of reserved slots become free, denoted by \(F_{ij}\in\{0,1,...,(m-f_{i})\}\), which can be expressed as the sum of the difference between the number of free slots in both states (\(f_{j}-f_{i}\)), plus the difference between the number of contending end-devices in both states (_i.e._, \(S_{ij}\)),  
\[F_{ij}=\left\{ \begin{matrix}(f_{i}-f_{j})+S_{ij},&if\left(f_{i}<m\right)and \left(f_{i}\leq f_{j}\right)\\ 0,&otherwise\end{matrix} \right. \tag{4}\]  
Then, we can formulate the one-step transition probability \(p_{ij}\) from state \((c_{i},f_{i})\) to state \((c_{j},f_{j})\) as follows:  
\[p_{ij}=\left\{ \begin{matrix}P_{s}\left(S_{ij},c_{i},f_{i}\right)\left(\begin{array} []{c}m-f_{i}\\ F_{ij}\end{array}\right)p_{r}{}^{F_{ij}}\left(1-p_{r}\right)^{m-f_{i}-F_{ij}}, \\ if\left(c_{i}-\max\left(S_{ij}\right)\leq c_{j}\leq c_{i}\right)and\left(f_{ j}\leq m-c_{i}+c_{j}\right)\\ 0,&if\left(c_{j}>c_{i}\right)or\left(c_{j}<c_{i}-\max\left(S_{ij}\right) \right)or\left(f_{j}>m-c_{i}+c_{j}\right)\\ 1-\sum\limits_{i\
eq j}p_{ij},&if\left(c_{i}=c_{j}\
eq 0\right)and\left(f_{i}=f _{j}\
eq m\right)\\ 1,&if\left(c_{i}=c_{j}=0\right)and\left(f_{i}=f_{j}=m\right)\end{matrix} \right. \tag{5}\]  
Figure 2: Generalized state transition diagram of the absorbing Markov chain of RFSA: **(a)** for the case in which the number \(n\) of end-devices is greater than the number \(m\) of slots; and **(b)** for the case in which the number \(n\) of end-devices is lower or equal to the number \(m\) of slots. Some transitions have been intentionally omitted for ease of understanding of the figure.