# 2 CA-R2: A Hybrid MAC Protocol for Machine-Type Communications
## 3 The 2C Algorithm and Its Adaptable Version
### The 2C Algorithm  
The 2C algorithm [16] resolves access conflicts by means of random access to a time-slotted channel. There is a central station in charge of examining each time slot with the aim of informing the events that it detected. This latter action is performed through feedback messages that are broadcast to the stations in the network at the end of each slot. In turn, contending stations can be in one of the following two states: transmission (T\({}_{\rm x}\)) and waiting (W). A station with a pending packet has to put itself in state T\({}_{\rm x}\), and it must wait for the beginning of a time slot to attempt channel access. If only one station transmits, it will be successful and the central station will return an NC (no collision) message. However, if two or more stations transmit, a collision will be detected by the central station and it will return a C (collision) message. In such a case, a collision resolution interval (CRI) will start in the following slot. This interval will finish when all stations involved in the initial collision successfully transmit their packets. A station that generates a transmission request when a CRI is in progress has to wait until it ends. Let us consider the list symbols shown in Table 2. Each station participating in a CRI maintains a state variable that controls its channel access by switching between T\({}_{\rm x}\) and W. Let us denote by \(r_{t}\) the value of this variable at the beginning of an arbitrary slot \(t\). Let \(f_{t}\) be the feedback message corresponding to the transmission in slot \(t\) and received at the end of the same time slot. If the transmission ended in collision, then \(f_{t}=\rm C\), otherwise \(f_{t}=\rm NC\). Let us assume that up to the current slot, all packets have been transmitted (i.e., there is no CRI in progress). Stations with packets to transmit set their state variables to T\({}_{\rm x}\) and attempt channel access in the following slot. Depending on the sequence of feedback messages received from the central station, each station updates its state variable as follows:  
1. If \(r_{t}=\rm W\) and \(f_{t}=\rm NC\), then \(r_{t+1}=\rm T_{x}\). 2. If \(r_{t}=\rm W\) and \(f_{t}=\rm C\), then \(r_{t+1}=\rm W\). 3. If \(r_{t}=\rm T_{x}\) and \(f_{t}=\rm C\), then \(r_{t+1}=\rm T_{x}\) with probability \(p=1/2\) or \(r_{t+1}=\rm W\), also with probability \(1/2\). In the following slot, each station will behave according to the updated value of its state variable. This is repeated until all stations are able to transmit their packets. Note that as collisions occur, more and more stations leave the transmitting state and join the group of waiting stations. This procedure continues until only one station is left in the transmitting state and achieves a successful transmission. In case a successful transmission occurs or all stations abandon the transmitting state, the central station transmits an NC feedback message. Furthermore, note that following an NC feedback message, all stations with \(r_{t}=\rm W\) will change their state to T\({}_{\rm x}\) and will attempt to transmit in the following slot, \begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Description** \\ \hline \(r_{t}\) & Station state at the beginning of slot \(t\); it can be waiting (W) or \\  & transmitting (T\({}_{\rm x}\)) \\ \(f_{t}\) & Feedback message returned by the central station at the end of slot \(t\) \\ \(p\) & Transmission probability \\ \(p(\cdot)\) & Adaptive transmission probability \\ \(\bar{N}\) & Estimation of the collision multiplicity \\ \(s\) & Reserved transmission slot \\ \hline \hline \end{tabular}
\end{table} 
Table 2: List of symbols used in the description of 2C, Adaptive-2C. and 2 CA-R\({}^{2}\). causing a new collision. Therefore, two consecutive NC feedback messages can only occur at the end of a CRI. This algorithm is called 2C because the contending stations may be either transmitting or waiting, and this situation can be depicted using a two-cell stack.