# 2 CA-R2: A Hybrid MAC Protocol for Machine-Type Communications
## 5 Modeling the 2 CA-R\({}^{2}\) Mechanism as a Markov Chain  
The Markov chain model introduced in this section represents the time evolution of the contention interval of the 2 CA-R\({}^{2}\) protocol, which is based on Adaptive-2C with updates per phase. Each state of the chain is identified by the ordered pair (\(TC\), \(WC\)), where \(TC\) and \(WC\) indicate the number of packets in the transmission cell and in the waiting cell, respectively. Figure 6 depicts the model where the states of the chain are represented as circles. The \"Start\" labels in Figure 6 indicate the possible starting states of a CRI depending on the number of stations that collided in its first minislot. Let us also recall that a collision involving all currently active stations marks the beginning of a phase. Therefore, phase \(n\) starts with a collision of multiplicity \(n\), i.e., in state \((n,0)\), and ends with a successful transmission in state \((1,n-1)\). When phase \(n\) ends, the system transitions to phase \(n-1\), where there are \(n-1\) contending stations. Let \(A=(a,b)\) and \(B=(c,d)\) be two states of the chain. Then, the probability of transitioning from the former to the latter can be written as \(P_{A,B}\) or, more explicitly, as \(P_{(a,b),(c,d)}\). However, based on the following observation and for readability reasons, we use a simplified notation for transitions among states that belong to the same phase. Let us note that in any given phase \(n\), the following observation holds. If there are \(i\) stations in the transmission cell (with \(i\) in the interval \(0\leq i\leq n\)), then there must be \(n-i\) stations in the waiting cell. Therefore, a state in phase \(n\) can be fully identified by using only one subscript (i.e., \(i\) in this case). Therefore, let us denote a transition from state \(i\) to state \(j\) of phase \(n\) by \(P_{i,j}^{(n)}\). Figure 6 shows the transition probabilities as labels placed along the arrows that connect the states. Table 3 summarizes the notation used in the model description. In our analysis, it is convenient to distinguish among three types of transitions. A type 0 transition occurs when it departs from the initial state of a phase. In turn, a type 1 transition is originated at a non-initial state. Finally, a type 2 transition is the one that occurs with probability 1. This last situation occurs in the following two cases: (a) when state \((0,n)\) is reached (empty minislot), the only possibility is to transition to the initial state of the same phase (i.e., \((n,0)\)); and (b) when state \((1,n-1)\) is reached (successful transmission), the only possibility is to transition to the initial state of the following phase, that is, \((n-1,0)\). As an example of the transition types, Figure 7a shows all transitions corresponding to phase \(n=3\). The following three types of transitions can be identified:  
* Type 0 transitions. Figure 7b shows all possible transitions from the initial state \((3,0)\) (lettering in blue). * Type 1 transitions. Figure 7c shows all possible transitions departing from \((2,1)\), which is not an initial state (lettering in purple). * Type 2 transitions. Figure 7d shows the cases with only one possible destination (lettering in red). \begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Description** \\ \hline \(n\) & Phase number \\ \(TC\) & Number of stations in transmission cell \\ \(WC\) & Number of stations in waiting cell \\ \(P_{i,j}^{(n)}\) & Probability of going from state \((i,n-i)\) to state \((j,n-j)\) in phase \(n\) \\ \(\mathbf{P}\) & Transition matrix \\ \(H_{A,B}\) & Expected number of minislots required to reach state \(B\) departing from state \(A\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: List of mathematical symbols used in the Markov chain model of 2 CA-R\({}^{2}\). Figure 6: Markov chain model for Adaptive-2C with update per phase. For readability reasons, the superscript indicating the phase of some probabilities has been omitted because this information is shown to the left.