Clearly, in the case of initial access there are many, potentially infinite, number of devices that can connect, but at a given time only one or very few of them want to do that. After the initial access, the communication can either proceed as a scheduled one or, if the activity of the device is sporadic, rely again on a random access. The latter is typical for scenarios in which a massive number of small Internet of Things (IoT) devices are connected to a base station Basil. However, at a given time only a small subset of them is active; this subset is random and unknown to Basil.
The canonical scenario for random access is depicted in Figure 2.1. In this scenario, a number of uncoordinated mobile devices attempt to transmit data or control information to a common receiver.
In presenting the algorithms for random access we will keep the assumptions on the collision model established in the previous chapter: a packet is an atomic transmission unit and any overlap between two or more packets leads to collision and incorrect reception of all collided packets. We will consider two classes of random access protocols: ALOHA type and probing (also known as tree type protocols). The variant of ALOHA considered here is not the original ALOHA, but rather framed ALOHA, a variant that logically extends the reservation schemes discussed in the previous chapter.
Figure 2.1 Canonical scenario for random access protocols, where a number of uncoordinated devices attempt to transmit in the uplink to the same receiver, which here is the base station Basil.
2.1 Framed ALOHA
The context for this discussion is in Section 1.4.3, where we introduced the reservation slots. Looking only at the expression (1.8), we can try to understand in which situation the usage of reservation slots may not lead to an efficient operation. For example, let us take the scenario in which the terminals connected to Basil are not phones, but sensors that monitor certain physical phenomena and only occasionally have data to send.
The parameters of this scenario can be described as follows. The total number of sensors connected to Basil is large, while the number of users that have some data to send at a given frame is small. In other words, the probability that a particular sensor has data to send in a particular frame is very low. The amount of data in a packet of each sensor is also small. Let us assume that the number of data slots that follow the reservation slots is small and, furthermore, all slots are full with data. In that case, using the equation (1.8), one can see that starts to dominate in the denominator, leading to decrease in the goodput. This is an example of a case in which the resources consumed by the metadata, which include reservation slots and all the other auxiliary packets, become comparable to the amount of data that needs to be sent and the overall system efficiency drops.
In the extreme case there is only sensor transmitting. Let us fix and assume that, in a given frame, the probability that a particular sensor has data to send is . This means that, on average, only packet comes in a frame from the total population of sensors. Let then the number of reservation slots be . Recall that, in the previous chapter we had , such that each reservation slot was deterministically and exclusively allocated to a single device (sensor). Here we have , such that an exclusive allocation is not possible. Let us assume that, at the start of the frame, each sensor that has data to send picks randomly one of the reservation slots and sends a reservation packet. Note that, unlike the case with deterministic allocation of reservation slots from the previous chapter, here Basil cannot know who is the sender unless its address is included in the reservation packet. Although in our example the expected number of sensors with data is , it can happen, with a significant probability, that two or more sensors have data to send in the same frame. If exactly two out of the sensors, Zoya and Yoshi, have data to send in the same frame, then the following outcomes are possible:
1 Case 1. Each sensor picks a different reservation slot. Then Basil receives both reservation packets and decides to allocate the data slot to, for example, Zoya. Yoshi tries again to send its reservation packet in a future frame.
2 Case 2. Both sensors pick the same reservation slot and end up in a collision. Then Basil cannot allocate the data slot to any of the two sensors, leaving the data slot empty.
Each of the two outcomes occurs with probability and in both cases it becomes apparent that having a fixed is not efficient. In the first case, the successful reservation of Yoshi is wasted1. In the second case, the data transmission slot is empty and wasted, as none of the two sensors can use it for transmission.
This leads us to think of a more efficient solution: does not need to be fixed, but it would be the best if the value of can be adapted to be equal to the number of successful outcomes, denoted by , where in the reservation frame of size . Basil needs to dynamically set , since in each new frame is a random number. Recalling the discussion from the previous chapter, this flexibility demands additional signaling information, as Basil needs to decide the value of after the reservation phase is finished and then communicate the value to the terminals. Since
