An energy-efficient adaptive frameless ALOHA protocol

The first version of ALOHA, also known as pure ALOHA, is a distributed random access in which each user transmits whenever it has a packet for transmission. There is no time slot in pure ALOHA, and all the packets are of the same size. Successful transmissions are the ones that do not bare any interference. The achievable throughput, T, defined as the average number of successful packet transmissions per packet time, in this scheme is \(\frac {1}{2e}\).

The introduction of slotted [4] and framed slotted [5] ALOHA was among the first attempts to improve the throughput of pure ALOHA protocol. In slotted ALOHA, the shared access time is divided into slots of equal duration. Users are only allowed to send their packets at the beginning of a time slot. Only collision free packets, i.e., the ones that are not interfered by packets transmitted by other users, are counted as successful transmissions. This random access scheme doubles the achievable throughput of pure ALOHA reaching a throughput of \(\frac {1}{e}\).

Framed slotted ALOHA [5] is a version of slotted ALOHA where the shared access time is divided into frames, consisting of M time slots. Each user may have a transmission in a frame with probability p, called the access probability. Every user who intends to transmit randomly and uniformly selects one of the time slots in the frame to transmit its packet. Same as the slotted ALOHA scheme, only collision-free slots are considered as successful transmissions in a frame. The maximum throughput of the framed slotted ALOHA is also \(\frac {1}{e}\). However, framed slotted ALOHA has a lower implementation complexity compared to slotted ALOHA since the synchronization among the users is on the basis of a frame rather than a time slot.

In an attempt to further improve the throughput of the framed slotted ALOHA, the authors in [6] propose the idea of transmission of several replicas of the same user message within a frame. This idea was further developed in [7], by introducing successive interference cancellation (SIC) technique which considerably increases the throughput of the framed slotted ALOHA. To this end, the receiver first resolves the collision-free packets within a frame. Then, the corresponding interferences of the these packets in other slots are canceled. By doing such, some other time slots may become interference-free which in turn results in resolving new packets. The process of resolving packets through successively canceling the interference continues until either no more time slot becomes interference-free or all the packets in that frame are resolved.

The idea of repeating users’ messages was later improved through irregular repetition method [8] where the number of replicas sent by the users follows a specific probability distribution function. By optimizing this probability distribution function, it is shown in [8] that the throughput of the framed slotted ALOHA can be even further improved.

More recently in [9], a new technique, called frameless ALOHA, has been developed. Unlike conventional framed slotted ALOHA protocols and inspired by the concept of rateless coding [10], frameless ALOHA avoids using frames with a fixed number of slots. Instead, users attempt to transmit their packets during consecutiveve contention rounds that can be seen as frames with variable number of slots. The length of each contention round is enforced by stopping criteria that are defined based on the number of resolved packets and the instantaneous throughput at the destination. Using such a dynamic approach for adjusting the length of contention rounds and employing SIC at the destination, frameless ALOHA increases the network throughput, and consequently its energy efficiency, compared to the previous variations of ALOHA protocol. Frameless slotted ALOHA is the base of our work in this paper and is explained further in detail later.

Similar to ALOHA throughput improvement, different approaches have been proposed to improve the energy efficiency of (framed) slotted ALOHA [11‐14]. For instance, optimizing the frame size [11] and nodes’ access (transmission) probabilities [12] are ways to improve the energy efficiency of slotted ALOHA. The work reported in [13] also suggests a probabilistic approach, called tree slotted ALOHA, to lower the number of transmissions in the system which consequently results in energy saving. In this work, we attempt to improve the energy efficiency of ALOHA protocol via exploiting adaptive access probabilities at the users. Details of our contribution are outlined in the following section.

The focus of this paper is on improving the energy efficiency of frameless slotted ALOHA which is one of the best performing ALOHA protocols in terms of throughput. Frameless ALOHA is also highly decentralized; thus, improving its energy efficiency would make it even more suitable for applications in M2M, RFID, and sensor networks.

To be more specific, we propose two adaptive frameless slotted ALOHA protocols to maximize the energy efficiency of the access strategy while a desired throughput is guaranteed. The basic idea behind our proposed schemes is to adaptively change the access probability of the users. That is, all users start with the same access probability at the start of the contention round. Later, each user locally updates its current access probability based on whether it has transmitted in the previous time slot or not. For this, if the user transmitted in the previous time slot, it decreases its current access probability and increases the access probability otherwise. The rationale behind this strategy is to give a higher chance to the users that have not transmitted previously and protect them from the possible interference caused by the users that have already made a transmission.

The difference between our two proposed schemes is in the step size by which the access probability changes adaptively. While the first proposed scheme employs a fixed step size, the second one benefits from variable step sizes. To further improve the performance of the suggested schemes, optimizing the step sizes are also considered. In fact, to achieve the best energy efficiency performance, we jointly optimize the stopping criteria and initial access probability of the frameless ALOHA and the step sizes of our proposed schemes.

As we discuss later in the paper, in the second proposed approach, by setting a simple relation between the increase and decrease step sizes, but letting them to change from one time slot to another, we are able to simplify the optimization problem yet surprisingly further improve the energy saving. Numerical results show that our proposed schemes significantly improve the energy efficiency of the network by reducing the average number of transmissions per time slot. In some cases, the reported energy saving reaches an outstanding value of 20 % when a variable step size is used. It is worth mentioning that our proposed approaches are distributed and such performance improvement is achieved without extra cost of central monitoring or hand shaking between the users and the base station (BS).

We assume that there are N users in the network, denoted by u _i where \(i \in \mathcal {N} = \{1,2,\ldots,N \}\) ¹. Users always have packets ready for transmission to the BS and employ frameless slotted ALOHA as the access protocol to share the channel. Like any other slotted ALOHA protocol, in frameless slotted ALOHA, the access time to the channel is divided into equal duration slots. The length of each slot is equal to the time needed to transmit a packet plus a possible guard time to counteract propagation delays [15]. Similar to the original slotted ALOHA protocol, users are synchronized on the slot basis for example via using a global synchronization mechanism [4].

However, opposed to framed ALOHA, users’ transmissions do not happen within fixed size frames in frameless ALOHA. Instead, users attempt to transmit their packets during one contention round that is a set of time slots where users are permitted to have their transmissions. Here, we denote the number of time slots in a contention round by M, which is not a priori determined and can vary from one contention round to another. In each slot of the contention round, say slot m, each user, say u _i , attempts to transmit its packet by probability p _i (m). Users continue their transmissions until they receive a beacon message from the BS notifying them about the end of the contention round². Through the feedback from the BS at the end of contention round, users are also informed whether their packets have been successfully received by the BS or not. Users whose packets have not been resolved in a contention round may attempt to transmit their packets in the following contention round. Later in this section, we will discuss the stopping criteria used by the BS to terminate a contention round and start a new one.

Following the users’ transmissions in a contention round, each arbitrary time slot has one of the following statuses: (a) no transmission (idle slot), (b) only one transmission (singleton slot), (c) more than one transmission (collision slot). To improve the throughout performance of the system, BS exploits SIC to resolve some of the packets received during the collision slots. To this end, the BS needs to store the received signals in the previous slots of a contention round. After the arrival of new time slot, the BS executes a round of SIC where it first resolves the collision-free packets from the stored and current received signals. Then, the BS cancels the corresponding interference of the resolved packets from collision slots. By doing such, some other singleton slots may appear making resolving some other packets possible. This process is iteratively repeated until no more packets can be resolved. At this point, the BS either terminates the contention round if the stopping criteria is met or waits for the next time slot to resolve further packets.

A toy example of SIC execution is shown in Fig. 1. In this graphical representation, there are four time slots in the contention round. Users are on the left side of the graph and time slots are on the right side of the graph. In this graph, a user is connected to a slot if it has transmitted a packet during that time slot. First singleton happens in time slot s ₂ which leads to resolving u ₁ packet. Now, by canceling the interference of u ₁’s packet from s ₄, s ₄ becomes a singleton slot from which u ₂’s packet can be resolved. Eventually, by canceling the interference of u ₂’s packet from s ₁, u ₃’s packet is resolved.

To explain the stopping criteria of the contention rounds, we first formally model the users’ transmissions. Assume that u _i wants to send its message, X _i , to the BS in a contention round. The received signal in time slot m of the contention round at the BS, denoted by Y _m , can be modeled as³

where s _i (m) is a Bernoulli random variable indicating whether u _i has transmitted in time slot m or not, i.e., s _i (m)=1 if transmission has occurred and s _i (m)=0 if it has not. Also, \(\mathcal {M} \triangleq \{1,2,\ldots,M \} \). From the protocol description in the above, we have

where P[·] refers to the probability of an event.

After receiving each Y(m), the BS executes SIC on Y(m) plus all stored signals from previous time slots to resolve new packets. We define the instantaneous throughput at time slot m, called T _I(m), as the ratio of the number of resolved users’ messages until a given time slot m, denoted by N _R(m), to the number of elapsed time slots. In other words,

Clearly, at the end of a contention round, the achievable throughput, T, is equal to T _I(M). Similarly, the fraction of resolved users at time slot m, F _R(m), is defined as

Now, the fraction of the resolved users at the end of a contention round is F _R=F _R(M).

Now, we explain the stopping criteria based on T _I(m) and F _R(m) for ending a contention round at the BS. And-or-tree evaluations [16] of the frameless slotted ALOHA in [17] show that T _I(m) and F _R(m) both have an avalanche behavior versus the number of elapsed time slots. That is, a sudden jump from a low value to a much higher value is observed at a specific time slot. This comes from the inherent nature of SIC where suddenly a large number of users’ transmissions are resolved by adding a single equation⁴. Further, the authors in [17] have shown that the avalanche point happens at the same time slot for both T _I(m) and F _R(m) most of the time. In addition, after the avalanche point, resolving the users’ packets happens very slowly causing only marginal increment in T _I(m) and F _R(m). As a result, it is concluded that the throughput achieves its maximum right after the avalanche point. The only case that this does not hold is when T _I(m)=1. In this case, T _I(m) reaches its maximum value, while F _R(m) may not be at its peak. That said, the stopping criteria to terminate a contention round is when T _I(m)=1 or F _R(m) reaches a threshold F. To ensure the maximum achievable throughput, in the original frameless ALOHA, F is found through a numerical optimization for different values of N as discussed in [17]. The optimized value for F is named F _opt.

In this section, we propose two new ALOHA schemes. Both of these schemes aim at improving the energy efficiency of the original frameless ALOHA protocol [17] without compromising the throughput. In the following, we first give the general intuition behind our schemes and then provide the details of these schemes later in this section.

Note that in the original frameless ALOHA protocol [9, 17], p _i (m)=p _init for any i and m, where p _init is a fixed probability assigned to the users by the BS. The value of p _init is determined based on BS’s estimation from the number of contending users N in a contention round [17]. To improve the energy efficiency, our proposed schemes benefit from adaptive access probabilities at the users. Similar to the original frameless ALOHA, the BS sends a beacon message to the users indicating the start of a contention round, as well as their initial access probability p _init. That is,

After the first time slot, as time passes, each u _i adaptively changes p _i (m) in the following time slots of the contention round. More specifically, if the user had a transmission in the current time slot, it reduces its access probability for the next time slot. Also, if the user did not have a transmission in the current time slot, it increases its access probability for the next time slot. The intuition behind this approach is to increase the chance of successful transmission for those users that have not transmitted in the previous time slot by reducing the chance of collision from the users that already have transmitted. Note that for this to happen, the increase step should be smaller than the decrease step. This is to avoid many users having high access probabilities and thus to prevent having many collisions. While both proposed schemes adaptively change the access probability at the users to achieve energy efficiency, they follow different strategies. In the first approach, the steps are fixed over the whole contention round while in the second approach the step size is variable over different time slots.

In our simulations, we compare several measures of these schemes. For throughput, we consider the average throughput of the system, denoted by \(\bar {T}\). For original frameless ALOHA, first adaptive approach, and second adaptive approach, \(\bar {T}\) is found by averaging T _o, T _a,f, and T _a,v over all simulation runs respectively. We call these average values \(\bar {T}_{\mathrm {o}}\), \(\bar {T}_{\mathrm {a,f}}\), and \(\bar {T}_{\mathrm {a,v}}\). We also present the average number of transmissions by each users, denoted by \(\bar {d}_{N}\), that is found by averaging d _N over all runs.

In addition, we compare the average probability of transmission over all users and time slots, denoted by p _t, for different schemes. Here, p _t is found as

We call the average of p _t over all simulation runs \(\bar {p}_{\mathrm {t}}\). Another measure is \(\bar {F}_{\mathrm {R}}\) that is the fraction of resolved users averaged over all the runs. Finally, we define \(L = \frac {M}{N}\) representing the normalized length of a contention round. We also present the results for \(\bar {L}\), the average of L over all simulation runs.

In our simulations, SIC is executed at the BS to resolve the users’ transmissions. Further, the optimization problem associated with each scheme is solved at the BS and the results are sent to the users at the start of the contention round. To solve the optimization problem for each value of N, we run a grid search over the optimization parameters for 10,000 times. The set of parameters that give the highest average for the objective function over these runs are then selected as the optimal parameters. For the grid search to optimize our proposed schemes, we use the parameters of the original frameless ALOHA as a starting point.More specifically, to find the optimal values of p _init and F for our schemes, we search over \(\phantom {\dot {i}\!}[p_{\text {init}_{\text {opt}}} / 2, p_{\text {init}_{\text {opt}}}]\) and [F _opt/2,F _opt] with step sizes 0.001 and 0.01 respectively where \(\phantom {\dot {i}\!}p_{\text {init}_{\text {opt}}}\) and F _opt are the optimal values of p _init and F for the original frameless ALOHA derived in [17]. To find the optimal values of α and k(for the first adaptive technique), we use an iterative grid search with adaptive mesh refinement to improve the accuracy of the solution at each iteration. The search intervals for α and k are [0,0.5] and [1,100] respectively. To search over α and k, we start by forming a two-dimensional regular coarse grid with only five points at each dimension, i.e., {0.1,0.2,0.3,0.4,0.5} for α and {20,40,60,80,100} for k. Then, we pick the point that maximizes the throughput over this coarse grid and form a (finer) grid in the vicinity of this point with again five points at each dimension. We continue searching and then refining the grid to the point that no significant change in the throughput is observed. We emphasize that the associated throughput with each of the grid points is found by averaging over 10000 runs. Note that if the number of users does not change between the contention rounds, which is often the case in moderately dynamic networks, same optimal value can be used for all contention rounds.

The simulation results for different schemes are presented in Tables 1, 2, and 3 as well as Fig. 6. By comparing the results in these tables, we can see that both adaptive schemes decrease the average number of transmissions in the network. This can be seen through the decrease in the values of \(\bar {d}_{N}\) and \(\bar {p}_{\mathrm {t}}\). Further, the adaptive schemes tend to use shorter contention rounds compared to the original frameless ALOHA and often terminate the contention round earlier. This is seen by comparing \(\bar {F}_{\mathrm {R}}\) and \(\bar {L}\) for the schemes.

The results for the energy consumption saving through our proposed schemes are presented in Table 4. The results in this table are derived by comparing \(\bar {d}_{N}\) for the adaptive schemes with the one for the original frameless ALOHA. From this table, we can observe that both schemes provide a significant energy saving over original frameless ALOHA especially for small- and medium-sized networks. In addition, it can be seen that the adaptive scheme with variable step sizes results in a higher level of energy saving compared to the adaptive approach with fixed step sizes. For instance, when N=50, the second proposed adaptive approach achieves the outstanding amount of 19.5 % in energy saving over the original frameless ALOHA. It is worth mentioning that the second approach achieves such a superior performance over the first approach with a lower optimization complexity. That is, allowing variable step sizes not only improves the energy efficiency but can also reduce the implementation complexity at the BS for an adaptive frameless ALOHA scheme.

Simulation results for \(\bar {p}(m)\) is presented in Fig. 6 for N=50. For the original frameless ALOHA, users stick to a fixed transmission probability over all time slots. For the first adaptive approach, the average access probability sharply decreases at the beginning. However, for larger values of m, the condition in (20) is violated owing to using a fixed k, and consequently, \(\bar {p}(m)\) switches to a slow increasing trend. As seen in this figure, for the second adaptive approach, \(\bar {p}(m)\) always has a decreasing trend over the contention round as a result of using variable step sizes.

¹ For dynamic networks where the number of users changes, an approach similar to the one proposed in [18] can be used to estimate N. An interested reader can also refer to [17] where the effect of imperfection in the estimation of N has been studied on the performance of the frameless ALOHA.

² Frequency division or time division duplexing may be used to enable receiving the BS beacon message and transmitting packets by the users at each time slot. For more details, see [9].

³ Our system model refers to higher layers where we are not concerned about the physical layer effects like fluctuation in the channel gain and noise.

⁴ Similar phenomenon happens in decoding based on iterative belief propagation [19].

⁵ This is assumed for the sake of simplicity and any positive real number β>α can be assumed as the decrease step.

⁶ For a contention round, it happens very rarely to have M≤3. On the other hand, these occasional cases already have a good energy efficiency that cannot be further improved using our approach.

⁷ Unlike (9), the BS does not need to optimize k.