Random Access Mechanism Enhancement Based on a Hybrid ALOHA Protocol Using an Analytical Model

Abdessamad Bellouch^1,*, Abdellah Zaaloul^{1, 2} and Abdelkrim Haqiq^{1, 3}

¹Hassan First University of Settat, Faculty of Sciences and Techniques, Computer, Networks, Mobility and Modeling laboratory: IR2M, 26000 – Settat, Morocco
²Ibn Zohr University of Agadir, Faculty of Sciences, Engineering, Mathematics and Informatics Laboratory (IMI). Agadir. Morocco
³Machine Intelligence Research Labs (MIR Labs), Washington, USA
E-mail: a.bellouch@uhp.ac.ma; abdelkrim.haqiq@uhp.ac.ma; a.zaaloul@uiz.ac.ma
*Corresponding Author

Received 11 March 2022; Accepted 10 April 2022; Publication 10 August 2022

Abstract

In this paper, we present a new MAC (Medium Access Control) protocol, called Hybrid ALOHA (H-ALOHA), which is a combination of two existing protocols: Pure ALOHA (P-ALOHA) protocol and Slotted ALOHA (S-ALOHA) protocol. The idea behind it is to design a MAC protocol that could meet some specific requirements in wireless networks, such as reducing energy consumption, delay minimization, and increasing the throughput. To the best of our knowledge, the S-ALOHA protocol is an improved version of P-ALOHA. However, during one single transmission scenario, P-ALOHA works better than S-ALOHA in terms of energy consumption and packet delivery. Motivated by that fact, we combine these two protocols, resulting in a hybrid ALOHA. A finite-state Markovian model is proposed to study the steady-state performance of H-ALOHA including normalized throughput, backlogged throughput, access delay, backlogged delay, and energy consumption. The proposed hybrid protocol has been compared with the S-ALOHA protocol. The simulation results show that the proposed hybrid protocol outperforms all ALOHA protocols. On average, the proposed protocol outperforms the S-ALOHA protocol by 60% in terms of normalized throughput, by 15% in terms of access delay, and by 23% in terms of total energy consumed during the transmission process.

Keywords: Medium access control, ALOHA, slotted ALOHA, performance evaluation, Markov chain.

1 Introduction

Unlike wired communication, in wireless networks, users communicate directly over a common wireless channel. A user can transmit its packet on the channel, and the transmitted packet will be received by the base station. And when two or more packets are sent at the same time, they interfere, causing a transmission collision. In the case of successful transmission, the user receives an acknowledgment from the base station on whether the packet has been well received. Otherwise, there is a collision, and retransmission is required. All collided packets (packets involved in a collision) are assumed to be corrupted, which are known as backlogged packets, and are retransmitted after some random time. Collisions mean that the transmitted packets are not received properly, resulting in low system performance [1]. There must therefore be some way to control which user has access to the medium. Media access control (MAC) protocols provide the access to the channel and a scheme to arbitrate transmissions between users so that each user on the network may communicate with other users– either on the same network or on others [2]. Anyway, the role of MAC protocols is to decrease collision and avoid crosstalk among network components in order to significantly improve the performance and Quality of Service (QoS) [3, 4]. MAC protocols are divided into two major groups, depending on the specific methods used to manage medium access: Random access protocols and scheduling-based protocols.

Random access protocols (Also known as contention-based MAC protocols) had emerged to make sure that the channel resources are efficiently shared between the users [5]. ALOHA or Pure ALOHA (P-ALOHA) [6] is the simplest and the earliest contention-based MAC protocol to be implemented. It is proposed by Norman Abrahamson and his colleagues three decades ago at the University of Hawaii with the objective to connect people on Hawaii Islands. P-ALOHA originally was designed to solve channel-allocation issues on the Hawaiian Islands during the 1970s. According to the P-ALOHA protocol, each user of the network can start transmission whenever it has the data packet to be transmitted, regardless of the channel condition (i.e. the transmission is free-control). Due to the collision issue, the P-ALOHA throughput is a little too low, $1 / (2 e) = 18.5 %$ . As this modest rate has a negative impact on network performance, S-ALOHA [7] is proposed as an improved version of P-ALOHA. The major alteration of the P-ALOHA protocol which is existed in the S-ALOHA protocol is the discrete-time (time is divided into slots), and the user can transmit only at the beginning of each time slot. The S-ALOHA throughput is thus boosted as well ( $1 / e = 37 %$ ).

Unlike P-ALOHA protocol, in S-ALOHA, time is subdivided into time slots and the users must wait for the beginning of the next time slot to start the transmission if they miss the transmission during the current slot. Waiting for the next time slot means delayed packet transmission and an increase in energy consumption. Based on that, in the case of one single transmission, the P-ALOHA protocol is much better than the S-ALOHA protocol. More and more, the probability that there is a collision in the P-ALOHA system is $1 - e^{- 2 T λ}$ , where $T$ is the necessary time for packet transmission, and $λ$ is the average arrival rate of packets. While the probability that there is a collision in the S-ALOHA system is only $1 - e^{- T λ}$ . For this reason, the S-ALOHA protocol works well during multiple transmissions compared to the P-ALOHA. This motivated us to combine P-ALOHA with the S-ALOHA, resulting in a Hybrid ALOHA (H-ALOHA). The main idea behind our H-ALOHA is that the users implement the P-ALOHA protocol during one single transmission, while they run S-ALOHA in the case of multiple transmissions. We describe the design objectives for our hybrid protocol from two perspectives. First, the new MAC protocol should be inherently energy-efficient to prolong the battery lifetime. Secondly, the new MAC protocol should provide low delay compared to both P-ALOHA and S-ALOHA protocols.

In fact, it is possible that both protocols can be used by the same user in the same wireless network. When users are communicating over the same wireless network, they should share the same Physical Layer (PHY) and Data Link Layer (DLL), at least. The access control protocol is within the DLL, and in principle, all users should follow the same rules. For instance, within a Wi-Fi network, all nodes should use the common carrier-sense multiple access with collision avoidance (CSMA/CA) access strategy [8]. This is for fairness reasons. However, even within the Wi-Fi CSMA/CA, there are different access schemes (DCF, HCF, etc.) that actually differentiate the way a node prioritizes its own (or the others) traffic.

The main contributions of this paper are as follows:

• We propose a novel MAC protocol which combines two existing protocols: P-ALOHA and S-ALOHA protocols.

• We propose a mathematical model based on Markov chains which allows determining the system’s state in the stationary regime.

• We explore different performance metrics, such as throughput, delay, number of backlogged packets, and energy consumption.

• We provide a comparative study of the proposed hybrid protocol with ALOHA protocols.

The remaining parts of this article are organized as follows. Section 2 summarizes relevant prior works. Section 3 presents an overview about ALOHA family. In Section 4, we present the system model considered in our paper. Section 5 presents the analytic model of the Hybrid ALOHA protocol using a discrete Markov chain. In Section 6, we calculate the performance metrics such as the average throughput, as well as obtaining the average delay and energy consumption. Section 7 presents the protocol evaluation based on MATLAB simulations that we have conducted to compare its average delay and energy consumption. Finally, Section 8 concludes the article.

2 Related Works

Interest has been growing in recent years in studying and improving access to a common medium in wireless communication networks. Several of these studies focus on the slotted aloha, in which time is divided into slots. For example, in [9], the authors have proposed an approach called ZigZag Decoding to enhance the Slotted ALOHA protocol. Exploiting ZigZag decoding approach, the receiver is able to retrieve packets despite the presence of collision, resulting in reducing the loss rate of colliding packets. The authors show trough numerical results that the ZigZag decoding approach can significantly enhance the performance measures of the Slotted ALOHA protocol.

In [10], the authors have proposed the Capture Effect technique to improve the performance of the Slotted ALOHA protocol for LoRa technology. The basic idea of the Capture Effect technique is that the transmitters send their packets using one of the available power levels, and the receiver is always able to retrieve the packet transmitted at the highest power level among all the transmitted packets. Authors have proven that the Capture Effect technique makes the Slotted ALOHA protocol more performant than the conventional Slotted ALOHA.

In [11], the authors have proposed a hybrid approach for enhancing the Slotted ALOHA protocol. This hybrid approach combines between two existing techniques : ZigZag Decoding (ZD) technique and Capture Effect (CE) technique. Authors proposed a study based on the Markov chain model, to define the main performance metrics such as the throughput and the average packet delay. They have also presented a comparative study of the proposed hybrid protocol (SA-CEZD) to the ones reported in the literature: the standard Slotted ALOHA (SA) [12], the Slotted ALOHA combined with ZigZag Decoding (SA-ZD) [9], and the Slotted ALOHA improved by the Capture Effect (SA-CE) [10]. The results showed that the proposed hybrid protocol outperforms all other proposals.

Authors, in [13] have proposed a novel mechanism to improve the performance of the slotted ALOHA protocol. This improvement is granted by employing two schemes. The first one is called signature codes, which help the receiver recognize the packets involved in collisions. The second scheme is known as successive interference cancellation (SIC) which is used to retrieve packets during the collision. The authors modeled the system as a two-dimensional Markov model, where the number of collided packets is taken as the system state. They derived the mathematical expressions of performance metrics as a function of the stationary distribution, such as the normalized throughput, average delay, and average memory size. Finally, through numerical results, they show that the proposed protocol outperforms the standard slotted ALOHA protocol in terms of the normalized throughput and average delay.

The authors in [14] have developed a novel policy (called the Lazy Policy, in recent literature) known as threshold-ALOHA, which is a distributed age-aware modification of the slotted ALOHA protocol. The basic idea of the proposed policy is that users suspend their transmissions until the Age of Information (AoI) of the status update flow it is sending reaches a certain threshold $Γ$ . Once the AoI exceeds $Γ$ , the user transmits with transmission probability in each time slot, as in conventional slotted ALOHA. They proposed a discrete-time Markov Chain (DTMC) to analyze the behavior of threshold-ALOHA. Then, they derived an expression relating the time average AoI in threshold-ALOHA to the network size $n$ , the transmission threshold, and the transmission probability, and they show that the optimal time average AoI scales with $n$ as $1.4169 n$ , which is close to half the minimum value en achievable by ordinary slotted ALOHA. Moreover, at this AoI optimized operating point, the loss throughout is below 1% of the maximum achievable throughput.

In [15], the authors have proposed a new approach based on the concept of policy trees to enhance the Slotted ALOHA protocol. Each node has the set of policies ${(i, 2^{m}) | 0 \leq i < m}$ , where policy $(i, 2^{m})$ prescribes transmitting in the $i - t h$ time-slot of the frame, that is, at all time slots $t$ where $t$ mod $2^{m} = i$ . To achieve higher throughput, the nodes must learn how to choose the best policies by assigning quantitative weights to all policies. This results in two variants of Slotted ALOHA, which are ALOHA-QT and ALOHA-QTF. Simulation experiments showed ALOHA-QT and ALOHA-QTF give performance improvements compared to ALOHA-Q and Slotted ALOHA with exponential backoffs.

In [16], the authors have presented an approach to enhance the Slotted ALOHA protocol for IoT environments during the COVID-19 pandemic. The proposed approach ensures fast and successful transmission of the data transmitted by COVID-19 IoT devices that implement Slotted ALOHA in a scenario consisting of other type of IoT devices that use the same random access protocol. Authors proposed a model analysis based on two-dimensional Markov chains for modeling the considered IoT network. The numerical results showed that, thanks to the priority given to COVID-19 IoT devices, leads to an enhancement of the performance of that type of IoT device compared to the other type of IoT devices in terms of all performance metrics of interest.

Contention Resolution Diversity Slotted ALOHA (CRDSA) protocol and its variant such as IRSA (Irregular Repetition Slotted ALOHA), CSA (Coded Slotted ALOHA) and MuSCA (MultiSlots Coded ALOHA) show high throughput performance compared to conventional slotted ALOHA protocol. In [17], the authors have further enhanced the flexibility and performance of CRDSA protocol along different physical layer dimensions. They are aiming to improve the performance of CRDSA in terms of throughput, power and energy efficiency, as well as the flexibility. Based on simulation results, they show that there is still chance for improvement in terms of throughput and, using heuristic methods, they find an optimized distribution of the packets power. Applying this latter, it is shown to achieve significantly enhanced performance. By employing multi-frequency CRDSA, the terminal’s peak power is drastically reduced.

In [18], the authors have proposed an approach to enhance Slotted ALOHA-Based MAC for IoT applications in the fight against COVID-19. They consider an IoT network scenario where several classes of IoT devices transmit to a single gateway, using the Slotted aloha protocol as a random access protocol. The impression is to propose a method that ensures fast and successful transmission of the data transmitted by COVID-19 IoT devices (class 1 devices) in a scenario comprising several classes of IoT devices. Indeed, the considered IoT network consists of $N$ class of devices (numbered $1, 2, \dots, N$ ) such that if $i < j$ a class $i$ IoT device always has priority over a class $j$ IoT device. They showed through numerical results that the proposed approach enhances Slotted ALOHA performance and especially improves COVID-19 IoT devices performance compared to the performance of the other classes of IoT devices in terms of all performance metrics.

In [19], the authors have considered a network scenario consisting of a mix of cooperative and non-cooperative users under incomplete game information. The authors have supposed that the users implement the Slotted ALOHA mechanism combined with ZigZag Decoding to access a shared channel. Through numerical results, they have shown that the selfish behavior of users affects negatively the network performance.

In the foregoing discussion, the S-Aloha is stabilized to be an improved version of the pure ALOHA protocol in which users are synchronized, in the sense that they can only start transmitting at the beginning of a time slot. The maximum throughput for slotted ALOHA is $\frac{1}{e}$ . Clearly, this maximum throughput is a bit too low, and the natural question is how much more throughput can be achieved. Toward answering that question, many approaches, and techniques have been proposed to resolve collisions in order to improve the throughput of the S-ALOHA protocol. All the papers discussed in this section work to enhance the S-ALOHA protocol. However, S-ALOHA requires time synchronization, which slows packet delivery and increases energy usage. While our proposed hybrid protocol achieves maximal efficiency using the same physical layer as ALOHA protocols, and without requiring time synchronization.

3 ALOHA Random Access Protocols

In this section, we present an overview of two kinds of ALOHA-based random access protocols: Pure ALOHA and Slotted ALOHA.

3.1 Pure ALOHA

In pure ALOHA (also known as non-slotted ALOHA), if multiple users transmit packets at the same instant $t_{0}$ , or interval as other users, this resulted in a collision (complete or partial collision). Figure 1 illustrates the time duration in which a collision can happen. Thus, $2 T$ is the time period (vulnerability time) in which a single transmission is successfully performed. Without verification of the status of the channel, every user can transmit its data packet, which creates the possibility of packet collision. After receiving an acknowledgment (ACK) from the receiver side, the transmission is considered successful and vice versa. And for collided or overlapped packets, retransmission is required after a random time until they are transmitted successfully. Waiting a random time before retransmitting the collided packet can avoid a further collision. The efficiency of the ALOHA channel is the probability of successful transmission without any collision. The channel throughput expression of pure ALOHA is $T h_{P - A L O H A} = G e^{- 2 G}$ , where $G$ is the traffic load (the number of users that attempt the channel access in one packet time $T$ ).

Figure 1 Vulnerability intervals for Pure ALOHA.

To derive the efficiency of Pure ALOHA channel, maximize $T h_{P - A L O H A}$ for $G$ :

$\frac{d T h_{P - A L O H A}}{d G} = 0$	$\Leftrightarrow \frac{d (G e^{- 2 G})}{d G} = 0$
	$\Leftrightarrow e^{- 2 G} - 2 G e^{- 2 G} = 0$
	$\Leftrightarrow e^{- 2 G} (1 - 2 G) = 0$
	$\Leftrightarrow G = 0.5 .$

Then, the maximum throughput efficiency of pure ALOHA is:

$T h_{P - A L O H A}^{m a x} = T h (0.5) = 0.5 e^{- 2 * 0.5},$	(1)
$T h_{P - A L O H A}^{m a x} = 0.184 kbits/sec .$	(2)

Figure 2 Vulnerability intervals for Slotted ALOHA.

3.2 Slotted ALOHA

In Slotted ALOHA, the time is divided into time intervals (known as slots) of equal length, and each user can start the transmission only within a time slot. Therefore, in Slotted ALOHA there is no partial interference, only simultaneously (same time slot) transmitted packets are destroyed. The major factors kept in mind while developing the Slotted ALOHA protocol were Packet Loss Ratio (PLR) and throughput, as well as average delay. In comparison to the pure ALOHA, users that implement Slotted ALOHA can not transmit their data whenever it is available. Consequently, they need to wait for the beginning of the next time slot to start transmission. The main drawback of the Slotted ALOHA protocol is too many collisions when the traffic is extremely heavy [20, 21]. As shown in Figure 2, successful transmission happens when there is just one packet was scheduled for transmission during a time slot. Thus, the vulnerable time in the case of Slotted ALOHA is $T$ (single slot). The channel throughput expression of Slotted ALOHA is $T h_{S - A L O H A} = G e^{- G}$ .

$\frac{d T h_{S - A L O H A}}{d G} = 0$	$\Leftrightarrow \frac{d (G e^{- G})}{d G} = 0$
	$\Leftrightarrow e^{- G} - G e^{- G} = 0$
	$\Leftrightarrow e^{- G} (1 - G) = 0$
	$\Leftrightarrow G = 1 .$

Then, the maximum throughput efficiency of slotted ALOHA is:

$T h_{S - A L O H A}^{m a x} = T h (1) = 1 e^{- 1},$	(3)
$T h_{S - A L O H A}^{m a x} = 0.3678 kbits/sec .$	(4)

4 System Model and Assumptions

In this section, the system model adopted in this work will be described as follows. Consider an uplink wireless network consisting of one receiver (e.g., base station, access point) and multiple (say in total $M$ ) sources (e.g., nodes, users), which transmit their packets to the receiver via a shared wireless channel. The single receiver is located at the cell center, while the sources are positioned in a star topology as illustrated in Figure 3. We begin by supposing that the sources have no buffer for storing incoming packets (new and old packets), thus, each source waits for the successful transmission of the current packet to send another packet. This assumption can have realistic application in the context of signaling. The packets that are failed to be received are called backlogged packets. In this system, we assume that all the sources implement our hybrid ALOHA (combination of P-ALOHA and S-ALOHA) protocol for medium access. Thus, the sources use the P-ALOHA protocol during one single transmission, while they implement the S-ALOHA protocol during multiple transmissions. That means during one single transmission, whenever a source has a packet (new or old) to send, it simply (re)transmits it at the begging of a subslot (length of subslot is $T_{subslot}$ ). And during multiple transmissions, the sources can transmit their packets only at the begging of a time slot (time is slotted into slots of fixed length $T_{slot} = N T_{subslot}$ , where the transmission of each packet take one-time slot). Once the sources generate their packets, the algorithm shown in Fig. 4 is carried out to select and determine which protocol can be implemented by sources to get better performance during transmission. Thus, the hybrid ALOHA works as follows:

• If only one source attempts transmission (new or old), it applied P-ALOHA protocol to handle the random access process.

• If two or more sources attempt transmission (new or old), they perform S-ALOHA protocol for random access control.

• In case of transmission failure, collided sources retransmit after a random delay using the best protocol for the current situation.

Figure 3 The proposed system model adopted in this paper.

Figure 4 Algorithm of the process of transmission with hybrid ALOHA.

We assume that the packet arrivals at different sources are independent, and it follows a Bernoulli process with a parameter $p_{a}$ . And if a collision happens, the packet gets backlogged, and it will be retransmitted (as an old packet) in the next time (sub)slot with re-transmission probability $p_{r} \in (0, 1]$ .

Table 1 Notation and description

Notation	Description
$M$	Total number of users
$n$	Number of backlogged users
$N$	Number of sub-slots
$p_{a}$	Transmission probability of newly arrived packets
$p_{r}$	Retransmission probability of backlogged packets
$P$	Transition matrix
$π$	Steady state probability
$T h$	Normalized throughput
$T h_{b a c k}$	Backlogged throughput
$D e$	Access delay
$D e_{b a c k}$	Backlogged delay
$E_{wx}$	Energy consumed by a source during waiting time
$E_{tx}$	Energy consumed by a source during transmission
$E_{cx}$	Energy consumed by a source during collision
$E_{rx}$	Energy consumed by a source during receiving
$E_{total}$	The total consumed energy

5 Theoretical Analysis

In this section, we build a Discrete Markov Chain Model (DMCM) based on [22, 23], to model our considered system with $M$ users. Then, the chain consists of $M$ states. We denote by $n$ the number of packets that are involved in a collision (equivalently, backlogged packets or backlogged sources) at the beginning of a (sub)slot. For any choice of $p_{r} \in (0, 1]$ , the process $n$ has the strong Markov property. The state space of the considered Markov chain is $E = {0, 1, \dots, M}$ . Figure 5, shows the transition diagram of the considered Markov chain. Table 1, shows some notations used in the paper.

Let us denote by $Q_{a} (j, n)$ the probability that $j$ unbacklogged sources transmit packets in a given (sub)slot.

Q_{a} (j, n) = (\binom{M - n}{j}) {(1 - p_{a})}^{M - n - j} p_{a}^{j},

(5)

and let $Q_{r} (j, n)$ be the transmission probability that $j$ backlogged sources retransmit their packet in a given time (sub)slot.

Q_{r} (j, n) = (\binom{n}{j}) {(1 - p_{r})}^{n - j} p_{r}^{j} .

(6)

Figure 5 Transition diagram of the considered Markov chain that represents the evolution of the numbers of backlogged packets in our hybrid ALOHA.

The transition probabilities $P_{(i, j)}$ (defined as the probability that the number of collided packets changes from $n$ to $m$ , $n, m \in E$ ) satisfy the following system equations:

P_{n, n + i} (p_{a}, p_{r}) = {\begin{matrix} Q_{a} (i, n), & i \geq 2 \\ Q_{a} (1, n) [1 - Q_{r} (0, n)], & i = 1 \\ \frac{(3 N - 1) N}{2} Q_{a} (1, n) Q_{r} (0, n) \\ + Q_{a} (0, n) [1 - Q_{r} (1, n)], & i = 0 \\ \frac{(3 N - 1) N}{2} Q_{a} (0, n) Q_{r} (1, n) & i = - 1 \\ 0 & O t h e r w i s e . \end{matrix}

(7)

where $N$ is the number of sub-slots in a Slotted ALOHA slot. In fact when $N = 1$ , hybrid ALOHA became the traditional Slotted ALOHA.

As our Markov chain is irreducible, and it has finite set of states $E$ . Therefore, it is ergodic, and it has a unique stationary probability $π$ . This latter can be calculated by solving the following system:

{\begin{matrix} π (p_{a}, p_{r}) = π (p_{a}, p_{r}) P (p_{a}, p_{r}) \\ π_{n} (p_{a}, p_{r}) \geq 0, n = 0, 1, \dots, M \\ \sum_{n = 0}^{M} π_{n} (p_{a}, p_{r}) = 1 . \end{matrix}

(8)

where $π_{n} (p_{a}, p_{r})$ , $n \in {0, 1, \dots, M}$ represents the probability that there are $n$ backlogged packets in the system. And $P (p_{a}, p_{r})$ denotes the transition matrix of the considered Markov chain.

6 Performance Evaluation

In the following subsections, we are going to derive the mathematical expressions of some performance metrics.

6.1 Normalized Throughput

In communication protocols, the throughput is defined as the number of packets that are transmitted successfully per unit of time. Therefore, the throughput of transmitted packets is given as follows:

T h_{H-ALOHA} (p_{a}, p_{r}) = \frac{1}{T} \sum_{n = 0}^{M} P_{s u c c}^{n} π_{n} (p_{a}, p_{r}),

(9)

where $P_{s u c c}^{n}$ is the successful probability, which is the average number of packets that are successfully transmitted in a slot (or sub-slot) of state $n$ . In this case, the success probability is given by:

\begin{matrix} P_{s u c c}^{n} = & \frac{(3 N - 1) N}{2} [Q_{a} (1, n) Q_{r} (0, n) + Q_{a} (0, n) Q_{r} (1, n)] . \end{matrix}

(10)

According to $\sum_{n = 0}^{M} π_{n} (p_{a}, p_{r}) = 1$ , the relation (9) can be rewritten as follows:

T h_{H-ALOHA} (p_{a}, p_{r}) = \frac{q_{a}}{T} [M - N_{b a c k} (p_{a}, p_{r})],

(11)

where $N_{b a c k} (p_{a}, p_{r})$ is the expected number of backlogged packets (collided packets), which is calculated as follows:

N_{b a c k} (p_{a}, p_{r}) = \sum_{n = 0}^{M} π_{n} (p_{a}, p_{r}) n,

(12)

and

$T$	$= \frac{(3 N - 1) N}{2} \sum_{n = 0}^{M} [Q_{a} (1, n) Q_{r} (0, n)$
	$+ Q_{a} (0, n) Q_{r} (1, n)] π_{n} (p_{a}, p_{r}) .$	(13)

6.2 Backlogged Throughput

The throughput of backlogged packets is defined as the number of backlogged packets that have been transmitted successfully over the channel, which is considered as another way to evaluate the MAC protocol performance. The average throughput for backlogged packets is given by:

T h_{H-ALOHA}^{back} (p_{a}, p_{r}) = T h_{H-ALOHA} (p_{a}, p_{r}) - T h_{H-ALOHA}^{succ} (p_{a}, p_{r}),

(14)

where $T h_{H-ALOHA}^{succ} (p_{a}, p_{r})$ is the throughput of packets that are successfully transmitted at the first attempt. It is calculated by

\begin{matrix} T h_{H-ALOHA}^{succ} (p_{a}, p_{r}) = & \frac{(3 N - 1) N}{2 T} \sum_{n = 0}^{M - 1} Q_{a} (1, n) Q_{r} (0, n) π_{n} (p_{a}, p_{r}) . \end{matrix}

6.3 Access Delay

The average delay of transmitted packets is another criterion that must be taken into consideration to evaluate the wireless communication protocols. It is defined as the average time that a packet takes from its source to the receiver, and it is expressed in slots. Applying Little’s formula [24], the average delay is given by:

$D e_{H-ALOHA} (p_{a}, p_{r})$	$= \frac{T h_{H-ALOHA} (p_{a}, p_{r}) + N_{b a c k} (p_{a}, p_{r})}{T h_{H-ALOHA} (p_{a}, p_{r})}$
	$= 1 + \frac{N_{b a c k} (p_{a}, p_{r}))}{T h_{H-ALOHA} (p_{a}, p_{r})} .$	(16)

6.4 Backlogged Delay

The expected delay of backlogged packets is defined as the average time, in slots, that a backlogged packet takes from its source to receiver. By using the little’s formula, backlogged delay is given by:

D e_{H-ALOHA}^{back} (p_{a}, p_{r}) = 1 + \frac{N_{back} (p_{a}, p_{r})}{T h_{H-ALOHA}^{back} (p_{a}, p_{r})} .

(17)

6.5 Average Energy Consumption

Energy consumption refers to the amount of energy that is spent by the sources within the transmission process. This is obtained by calculating each user’s energy level at four different operation states (transmitting a packet, receiving a packet, and collision), factoring in the initial energy consumed during the waiting for the next time slot. Then, The total consumed energy $E_{total}$ by a source that implements our hybrid ALOHA protocol during transmission will be produced by the following formula:

E_{total} = E_{wx} + E_{tx} + E_{cx} + E_{rx},

(18)

where $E_{wx}$ , $E_{tx}$ , $E_{cx}$ , and $E_{rx}$ are, respectively, the consumed energies by the source during, waiting for next slot, transmission mode, collision state, reception mode, respectively. $E_{wx}$ can be formulated as:

E_{wx} = {\begin{matrix} 0 & If only one source transmit \\ P W_{w x} . T_{w x} & Otherwise, \end{matrix}

(19)

where $P W_{w x}$ and $T_{w x}$ are the power consumption and the time duration in the waiting mode, respectively. And $E_{cx}$ can be formulated as:

E_{cx} = {\begin{matrix} 0 & If only one source transmit \\ P W_{c x} . T_{c x} & Otherwise, \end{matrix}

(20)

where $P W_{c x}$ and $T_{c x}$ are the power consumption and the time duration in the collision state, respectively. And $E_{tx}$ can be formulated as:

E_{tx} = P W_{t x} . T_{t x},

(21)

where $P W_{t x}$ and $T_{t x}$ are the power consumption and the time duration in the transmission mode, respectively. And $E_{rx}$ can be formulated as:

E_{rx} = P W_{r x} . T_{r x},

(22)

where $P W_{t x}$ and $T_{t x}$ are the power consumption and the time duration in the reception mode, respectively.

Moreover, the total consumed energy by the source is re-given in equation (23):

E_{total} = {\begin{matrix} P W_{t x} . T_{t x} + P W_{r x} . T_{r x} & If only one source \\ transmit \\ P W_{w x} . T_{w x} + P W_{c x} . T_{c x} \\ + P W_{t x} . T_{t x} + P W_{r x} . T_{r x} & Otherwise. \end{matrix}

(23)

7 Numerical Results

The numerical results are obtained using Matlab, and the parameters used for the simulation model are shown in Table 2. Through this section, we present MATLAB emulation performed to demonstrate the performance of Hybrid ALOHA (H-ALOHA) in terms of some performance metrics. Furthermore, a comparison between the proposed protocol with Slotted ALOHA (S-ALOHA) protocol will be achieved. The proposed protocol aims to increase the system throughput and decrease the delay by reducing collisions and also aiming at energy efficiency for wireless networks. There are several metrics used to evaluate the performance of the system such as normalized throughput, backlogged throughput, access delay, backlogged delay, and energy consumption.

Table 2 Protocol parameter values

Parameters	Values
Number of users $M$	10
Number of subslots $N$	10,1000
The arrival probability $p_{a}$	[0,1]
Transmission power $P W_{t x}$	30 mW
Receiving power $P W_{r x}$	40 mW
Waiting power $P W_{w x}$	16 $μ W$
Collision power $P W_{c x}$	20 mW
Transmission time $T_{t x}$	60 ms
Receiving time $T_{r x}$	30 ms
Waiting time $T_{w x}$	[0,60 ms)
Collision time $T_{c x}$	15 ms

Figure 6 Normalized throughput.

Figure 6 shows the total system normalized throughput of the H- ALOHA protocol for $N = 10, 1000$ in comparison with the traditional S-ALOHA protocol (N=1) with $M = 30$ users. Note that in this section, the normalized throughput is measured in packets per slot, with slot length $T_{slot}$ . And it is not normalized by the subslot length $T_{subslot}$ . As we mentioned before, when $N = 1$ , the subslot length equal the slot length ( $T_{slot} = T_{subslot}$ ) which is corresponding to the traditional Slotted ALOHA protocol. We mark that the throughput increases with the increasing traffic load. We can see that at high offered traffic, the throughput increases slowly because the network is near to saturation. The throughput performance of the S-ALOHA is the worst compared with others due to the probability of collisions being very high in that protocol, especially with the high traffic. While in the H-ALOHA protocol, during multiple transmissions, users are efficiently allocating slots for transmission to decrease the collision probability. Hence, the system throughput is enhanced. It can also be noticed that the proposed H-ALOHA with $N = 1000$ outperforms H-ALOHA with $N = 10$ by a big margin. That is, the throughput tends to increase as $N$ increases.

Figure 7 Backlogged throughput.

The variation of the throughput of backlogged packets for three protocols H-ALOHA ( $N = 10$ ), H-ALOHA ( $N = 1000$ ), and traditional S-ALOHA is shown in Figure 7 as a function of the arrival probability for $M = 30$ . As can be seen, when the arrival rate increases, the backlogged throughput of the three protocols declines dramatically, especially in the higher traffic load (i.e. $p_{a} = 1$ ), where the backlogged throughput becomes 0 which means no backlogged packet is transmitted over the channel. That is, due to the increase of the packets’ generation, the collision among backlogged packets will happen more frequently. The backlogged throughput of the H-ALOHA protocol decreases relatively gently, while the backlogged throughput of the S-ALOHA protocol decreases rapidly. This means that the H-ALOHA protocol performs better than the S-ALOHA protocol, especially at wispy traffic.

Figure 8 Access delay.

Figure 8 represents the delay of transmitted packets in the H-ALOHA protocol for $N = 10, 1000$ in comparison with the traditional S-ALOHA protocol ( $N = 1$ ) with $M = 30$ users. The delay is given in terms of slots. As far as we know, there is a close relationship between the traffic load and the packet delay. That is due to the collisions increment and the system saturation. As can be seen from the figure, the delay increases with increasing traffic load. As expected, H-ALOHA provides a lower access delay than the S-ALOHA protocol. This can be explained as follows. The users that implement H-ALOHA can transmit their packets when they are available, while under S-ALOHA protocol, the users must wait for the next time slot to transmit. And also we can see that hybrid ALOHA ( $N = 1000$ ) is shown to have the best performance delay compared to hybrid ALOHA ( $N = 10$ ) due to the subslot’s length in hybrid ALOHA ( $N = 10$ ) being larger than the subslot’s length in hybrid ALOHA ( $N = 1000$ ).

Figure 9 Backlogged delay.

Figure 10 Energy versus number of users.

Figure 9 illustrates the delay of backlogged packets of three protocols H-ALOHA ( $N = 10$ ), H-ALOHA ( $N = 1000$ ), and traditional S-ALOHA as a function of the arrival rate for $M = 30$ . The result depicts that the backlogged delay also increases with an increased number of generated packets for all three protocols. On comparing the three protocols in terms of backlogged delay, the H-ALOHA has a lesser delay than S-ALOHA protocols. This is due to that backlogged packets can be retransmitted at the moment they are available. And also, the H-ALOHA with $N = 1000$ show a better-backlogged delay compared to H-ALOHA with $N = 10$ . This is due to the users under H-ALOHA ( $N = 10$ ), retransmitting their backlogged packets with a delay higher compared to retransmitted packets under H-ALOHA ( $N = 1000$ ).

Finally, we plot in Figure 10 the energy consumption as a function of the traffic generation rate for the H-ALOHA, and the traditional S-ALOHA protocols. In our H-ALOHA, the users transmit their packets whenever they are available, without waiting for the beginning of the next time slot. This latter has a direct impact on the energy consumed by the users. For that reason and as we can see, the suggested protocol acquired a minimum energy consumption when compared with existing Slotted ALOHA protocol. Unlink H-ALOHA, under the S-ALOHA protocol, users must wait the begging of the next time slot for transmitting their data, which means they will consume more energy.

8 Conclusion

In this paper, we have proposed a new MAC protocol which is a replacement for both the Pure ALOHA (P-ALOHA) and Slotted ALOHA (S-ALOHA). The proposed Hybrid ALOHA (H-ALOHA) protocol achieves maximal efficiency while using the same physical layer as ALOHA protocols, and without requiring time synchronization. It can increase the throughput of the whole network and reduce the average packet delay, and also reduce energy consumption. The performance improvement is further evaluated by a mathematical framework based on the Markov chain and also by simulations based on Matlab. We have shown through this latter that H-ALOHA can perform more times better than S-ALOHA. H-ALOHA saves more energy compared to that of S-ALOHA. We remark also that the H-ALOHA protocol is more significant than S-ALOHA in terms of both average delay and throughput.

In the future, we plane to apply this approach to operational wireless networks under the cooperative and non-cooperative game framework.

References

[1] Huang, P., Xiao, L., Soltani, S., Mutka, M.W. and Xi, N., 2012. The evolution of MAC protocols in wireless sensor networks: A survey. IEEE communications surveys & tutorials, 15(1), pp. 101–120.

[2] Rajandekar, A. and Sikdar, B., 2015. A survey of MAC layer issues and protocols for machine-to-machine communications. IEEE Internet of Things Journal, 2(2), pp. 175–186.

[3] Rom, R. and Sidi, M., 2012. Multiple access protocols: performance and analysis. Springer Science & Business Media.

[4] Vázquez-Gallego, F., Tuset-Peiró, P., Alonso, L. and Alonso-Zarate, J., 2020. Delay and energy consumption analysis of frame slotted ALOHA variants for massive data collection in internet-of-things scenarios. Applied Sciences, 10(1), p.327.

[5] Tsatsanis, M.K., Zhang, R. and Banerjee, S., 2000. Network-assisted diversity for random access wireless networks. IEEE Transactions on Signal Processing, 48(3), pp. 702–711.

[6] Abramson, N., 1970, November. The ALOHA system: Another alternative for computer communications. In Proceedings of the November 17–19, 1970, fall joint computer conference (pp. 281–285).

[7] Carleial, A. and Hellman, M., 1975. Bistable behavior of ALOHA-type systems. IEEE transactions on Communications, 23(4), pp. 401–410.

[8] Mai, V.V., Thang, T.C. and Pham, A.T., 2017, May. CSMA/CA-based uplink MAC protocol design and analysis for hybrid VLC/Wifi networks. In 2017 IEEE International Conference on Communications Workshops (ICC Workshops) (pp. 457–462). IEEE.

[9] Zaaloul, A. and Haqiq, A. Enhanced slotted aloha mechanism by introducing zigzag decoding. arXiv preprint arXiv:1501.00976, 2015.

[10] Bellouch, A., Zaaloul, A., Boujnoui, A. and Haqiq, A. Modeling and performance evaluation of lora network based on capture effect. In Enabling Machine Learning Applications in Data Science, pages 249–263. Springer, 2021.

[11] Bellouch, A., Zaaloul, A., Boujnoui, A. and Haqiq, A. Hybrid approach for improving slotted aloha based on capture effect and zigzag decoding techniques. In The International Conference on Artificial Intelligence and Computer Vision, pages 218–-227. Springer, 2021.

[12] Altman, E., El-Azouzi, R. and Jimenez, T., 2003, March. Slotted Aloha as a stochastic game with partial information. In WiOpt’03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (pp. 9-pages).

[13] Jia, D., Fei, Z., Xiao, M., Cao, C. and Kuang, J., 2018. Enhanced frameless slotted ALOHA protocol with Markov chains analysis. Science China Information Sciences, 61(10), pp. 1–11.

[14] Tahir Yavascan, O. and Uysal, E., 2020. Analysis of Slotted ALOHA with an Age Threshold. arXiv e-prints, pp. arXiv-2007.

[15] de Alfaro, L., Zhang, M. and Garcia-Luna-Aceves, J.J., 2020, June. Approaching fair collision-free channel access with slotted aloha using collaborative policy-based reinforcement learning. In 2020 IFIP Networking Conference (Networking) (pp. 262–270). IEEE.

[16] Bellouch, A., Boujnoui, A., Zaaloul, A. and Haqiq, A., 2020, December. Modelling and Performance Evaluation of IoT Network During the COVID-19 Pandemic. In International Conference on Innovations in Bio-Inspired Computing and Applications (pp. 131–140). Springer, Cham.

[17] Mengali, A., De Gaudenzi, R. and Arapoglou, P.D., 2017. Enhancing the physical layer of contention resolution diversity slotted ALOHA. IEEE Transactions on Communications, 65(10), pp. 4295–4308.

[18] Bellouch, A., Boujnoui, A., Zaaloul, A. and Haqiq, A. Three-dimensional markov chain model to help reduce the spread of covid-19 in iot environment. Int. J. Comput. Inf. Syst. Ind. Manag. Appl, 13:275–285, 2021.

[19] Boujnoui, A., Zaaloul, A., Orozco-Barbosa, L. and Haqiq, A., 2022. Stochastic Game Analysis of Cooperation and Selfishness in a Random Access Mechanism. Mathematics, 10(5), p. 694.

[20] Boujnoui, A., Zaaloul, A. and Haqiq, A., 2018. Mathematical model based on game theory and Markov chains for analysing the transmission cost in SA-ZD mechanism. Int. J. Comput. Inf. Syst. Ind. Manag. Appl, 10(197–207), p. 170.

[21] Altman, E., El-Azouzi, R. and Jimenez, T., 2003, March. Slotted Aloha as a stochastic game with partial information. In WiOpt’03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (pp. 9-pages).

[22] Boujnoui, A., Zaaloul, A. and Haqiq, A. Enhanced pricing strategy for slotted aloha with zigzag decoding: A stochastic game approach. Int. J. Comput. Inf. Syst. Ind. Manag. Appl, 13:160–-171, 2021.

[23] El Hanjri, A,. Zaaloul, A. and Haqiq. A. Analytic approach using continuous markov chain to improve the qos of a wireless network. In International Conference on Innovations in Bio-Inspired Computing and Applications, pages 113–-124. Springer, 2017.

[24] Nelson, R.: Probability, stochastic processes, and queueing theory: the mathematics of computer performance modeling. Springer, New York (2013).

Biographies

Abdessamad Bellouch received his Bachelor’s degree in Mathematics and Applications at the Faculty of Sciences, Ibn Zohr University, Agadir, Morocco in 2016. He obtained his Master’s degree in Mathematics and Applications from the University of Hassan First of Settat, Morocco in 2018. And since 2017, he has been working as a professor of mathematics in high school, Bouskoura, Morocco. He is currently a Ph.D. student in Applied Mathematics at Computer, Networks, Mobility and Modeling laboratory, Faculty of Sciences and Techniques, Hassan First University of Settat, Morocco. Abdessamad Bellouch’s research interests include game theory, Markov chains, performance evaluation, queuing theory, wireless networks, and IoT.

Abdellah Zaaloul has a PhD (Doctorat d’Etat) in Applied Mathematics, option modeling and performance evaluation of computer communication networks, in the Department of Mathematics and Computer at Faculty of Sciences and Techniques (FSTS), Settat, Morocco. He received his M.Sc. degree in Mathematical and Applications engineering from the Hassan First University, Faculty of Sciences and Techniques (FSTS), Settat, Morocco, in 2011. And he has been working as a professor of mathematics in high school from 1992 until May 2018, in Settat, Morocco. And Since that date, he has been working as a Professor at the department of Mathematics Faculty of Legal, Economic and Social Sciences of Aït Melloul, Ibn Zohr University, Agadir, Morocco. Currently, he is a member of the e-NGN research group. Dr. Abdellah ZAALOUL’s interests lie in the areas of modeling and performance evaluation of communication networks, mobile communications networks, cloud computing and security, queueing theory and game theory, stochastic control, networking games.

Abdelkrim Haqiq has a High Study Degree (Diplôme des Etudes Supérieures de troisième cycle) and a PhD (Doctorat d’Etat), both in the field of modeling and performance evaluation of computer communication networks, from Mohammed V University, Faculty of Sciences, Rabat, Morocco. Since September 1995 he has been working as a Professor at the department of Applied Mathematics and Computer at the Faculty of Sciences and Techniques, Settat, Morocco. He is the Director of Computer, Networks, Mobility and Modeling laboratory: IR2M. He is an IEEE senior member and an IEEE Communications Society member. He is also a member of Machine Intelligence Research Labs (MIR Labs), Washington, USA and a member of the International Association of Engineers (IAENG). He was a co-director of a NATO Multi-Year project entitled “Cyber Security Analysis and Assurance using Cloud-Based Security Measurement system”, having the code: SPS-984425. Prof. Abdelkrim HAQIQ’s interests lie in the areas of modeling and performance evaluation of communication networks, mobile communications networks, cloud computing and security, emergent technologies, Markov Chains and queueing theory, Markov decision processes theory, and game theory. He is the author and co-author of more than 170 papers (international journals and conferences/workshops). He supervised 16 PhD thesis and co-supervised 3 others. Actually, he is supervising and co-supervising more than 8 PhD thesis. He is an associate editor of the International Journal of Computer International Systems and Industrial Management Applications (IJCISM), an editorial board member of the International Journal of Intelligent Engineering Informatics (IJIEI) and of the International Journal of Blockchains and Cryptocurrencies (IJBC), an international advisory board member of the International Journal of Smart Security Technologies (IJSST) and of the International Journal of Applied Research on Smart Surveillance Technologies and Society (IJARSSTS). He is also an editorial review board of the International Journal of Fog Computing (IJFC) and of the International Journal of Digital Crime and Forensics (IJDCF). Prof. Abdelkrim HAQIQ was a chair and a technical program committee chair/member of many international conferences and scientific events. He was also a Guest Editor and Co-Editor of special issues of some journals, books and international conference proceedings.