# 2 CA-R2: A Hybrid MAC Protocol for Machine-Type Communications
## 5 Modeling the 2 CA-R\({}^{2}\) Mechanism as a Markov Chain
Figure 7: Possible transitions for a CRI in phase \(n=3\). **(a)** All transitions; **(b)** type 0 transitions; **(c)** type 1 transitions; **(d)** type 2 transitions. In summary, the type of transition depends on the kind of state from which it departs. Therefore, it is convenient to observe that a state that belongs to phase \(n\) can be classified into one out of the following three possibilities: (a) the initial state, i.e., \((n,0)\); (b) non-initial states, which belong to the set \(\{(i,n-i)|2\leq i\leq n-1\}\); and (c) states with only one possible destination, i.e., \((0,n)\) and \((1,0)\). We take into consideration this classification in order to compute the probability of transitions that depart from a state in phase \(n\) (with \(n\geq 2\)), as follows:  
* Type 0 transitions, from the initial state \((n,0)\) to \((n-j,j)\): \[P_{n,n-j}^{(n)}=\binom{n}{n-j}p^{(n-j)}(1-p)^{j},\] (2) where \[j=0,...,n;\quad p= \begin{cases}\frac{1}{2}&\text{if $n=2$,}\\ \frac{\sqrt{2n(n-1)-2}}{(n-2)(n+1)}&\text{if $n>2$.}\end{cases} \]
* Type 1 transitions, from a non-initial state \((i,n-i)\) to \((j,n-j)\): \[P_{i,j}^{(n)}=\binom{i}{j}p^{j}(1-p)^{(i-j)},\] (3) where \[2\leq i\leq n-1;\quad j=0,...,i;\quad p=\frac{1}{2}.\]
* Type 2 transition, from \((0,n)\) to \((n,0)\) (after an empty minislot, all stations in the waiting state switch their state to transmission): \[P_{0,n}^{(n)}=1.\] (4)
* Type 2 transition, from \((1,n-1)\) to \((n-1,0)\) (after a successful transmission, the CRI evolves from phase \(n\) to phase \(n-1\)). \[P_{(1,n-1),(n-1,0)}=1.\] (5) Note that in this case, the simplified notation cannot be used since the origin and destination belong to different phases. Note that a type 0 transition (i.e., the one departing from the initial state of a phase) is the only type of transition using a value of \(p=p(N)\) (calculated by (1)) since it is only at the beginning of a phase that a station knows the estimated number of contending stations \(N\) and can use that value to optimize the value of \(p\). It is worth remembering that stations can distinguish the beginning of a phase only when they receive a successful transmission feedback message or when they receive an empty minislot message. The last phase of the Markov chain starts when the system reaches state \((1,0)\) and the only remaining station is able to transmit without contention. In this case, the system transitions to state \((0,0)\) and the CRI ends. For this reason, this state is considered to be an absorbing state in the chain. The transition probabilities described above are used to create transition matrix **P**, which represents an entire CRI. Figure 8 illustrates the general form of this matrix, and Figure 9 shows a numerical example for a CRI that starts with a collision multiplicity of \(n=4\). Figure 8: Transition matrix **P**. For the sake of clarity, in this illustration, each row is labeled in green with the initial state that it represents. In the same way, each column is labeled in green with the corresponding destination state. Furthermore, note that the transition types are distinguished by color. Blue, purple, and red are used for transition types 0, 1, and 2, respectively. Figure 9: Numerical example of transition matrix **P** for \(n=4\). The colors have the same meaning as in the general form of the matrix shown in Figure 8.  
With the information in transition matrix \(\mathbf{P}\), a number of metrics of performance can be computed. For our purposes, it is of particular interest to calculate the average CRI duration. To this end, we can apply some known results from the theory on Markov chains and compute the \"hitting\" times [33] by solving the following system of linear equations:  
\[H_{A,B}= \begin{cases}0\text{ for }A=B,\\ 1+\sum_{I\
eq B}P_{A,I}H_{I,B}\text{ for }A\
eq B,\end{cases}  \tag{6}\]  
where \(A\), \(B\), and \(I\) are three states of the chain and \(H_{A,B}\) is the expected number of time minislots required to reach state \(B\) departing from state \(A\).