# Multi-Power Level $Q$-Learning Algorithm for Random Access in NOMA mMTC
Systems

Giovanni Maciel Ferreira Silva, Taufik Abrão
G. Maciel and T. Abrão are with the Department of Electrical Engineering,
State University of Londrina, Paraná, Brazil. E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
(August 29, 2024)

###### Abstract

The massive machine-type communications (mMTC) service will be part of new
services planned to integrate the fifth generation of wireless communication
(B5G). In mMTC, thousands of devices sporadically access available resource
blocks on the network. In this scenario, the massive random access (RA)
problem arises when two or more devices collide when selecting the same
resource block. There are several techniques to deal with this problem. One of
them deploys $Q$-learning (QL), in which devices store in their $Q$-table the
rewards sent by the central node that indicate the quality of the transmission
performed. The device learns the best resource blocks to select and transmit
to avoid collisions. We propose a multi-power level QL (MPL-QL) algorithm that
uses non-orthogonal multiple access (NOMA) transmit scheme to generate
transmission power diversity and allow accommodate more than one device in the
same time-slot as long as the signal-to-interference-plus-noise ratio (SINR)
exceeds a threshold value. The numerical results reveal that the best
performance-complexity trade-off is obtained by using a higher number of power
levels, typically eight levels. The proposed MPL-QL can deliver better
throughput and lower latency compared to other recent QL-based algorithms
found in the literature.
Keywords – NOMA, mMTC, $Q$-Learning; random access; power allocation.

##  I Introduction

Machine-type wireless communication will be more widely used in applications
such as the internet of things (IoT), smart house, virtual reality, etc. [1,
2]. The goal of the B5G wireless communications involves achieve ubiquitous
communication in networks with ultra-dense device allocation [3, 4, 5]. A data
consumption of nearly five zettabytes per month is estimated across 17 billion
devices [6]. In addition, due to the outbreak of the COVID-19 pandemic, there
has been a remarkable increase in remote activities in work, health and
education areas, which will be much more frequent in the post-pandemic
environment [7].

Devices connected to the wireless network use different types of service. In
the fifth generation of wireless communications (5G) systems, a clear division
into three main use modes was defined [8]: enhanced mobile broadband (eMBB)
for devices that require high data rates as an augmented reality user; ultra-
reliable low-latency communications (URLLC) for applications that require
99.999% communication reliability such as remote surgery, while holding end-
to-end latency below 1 ms; and massive machine-type communications (mMTC),
composed of thousands of devices with low processing power that access network
data sporadically.

The study of these services remains relevant for 6G application scenarios. In
the new generation of communications, new services will be generated by
merging the benefits of existing ones. In [6], massive ultra-reliable low-
latency communication (mULC) is presented as a combination of the low latency
of URLLC with the high number of mMTC devices, a densification application
process. This new use mode can be associated with intelligent transport, where
high reliability is required for traffic safety and various traffic sensors
and monitors send data about the vehicle’s condition. Besides, ubiquitous
mobile broadband (uMBB) is also suggested as a use of high eMBB rates in mMTC
devices to enable applications such as ubiquitous networking and digital twin.

As the mMTC scenarios studied in 5G could be associated to the 6G systems, the
analysis of the main problems that affect this service is still relevant. One
is the random access (RA) procedure. To reduce latency in communication with
devices, it is common to use grant-free RA techniques, in which devices do not
need a training step with pilot sequences before sending data packets. With
the increase in the number of devices and the data rate starvation with new
applications, the problem of RA is aggravated. As the device access to the
network is sporadic. Still, if there is a crowded number of inactive users in
the network, then it is common for two or more devices to select the same
resource block to transmit data, characterized as a collision.

Several techniques mitigate the massive RA problem [9, 10]. One of the
simplest and least complex is performed by the slotted ALOHA (SA) protocol,
which makes the device resend the collided packet after a fixed time window.
There is also the strongest-user collision resolution (SUCRe) protocol [11],
which solves the collision problem by calculating, in a distributed way in
each user terminal (UT), the strongest user signal. Another possibility to
mitigate the RA issue in (over)-crowded networks is deploying reinforcement
learning (RL) techniques. RL is a trial-and-error-based algorithm with many
applications for many known problems in wireless networks. In [12], an RL-
based algorithm is used to increase throughput and solve the problem of
collisions between primary and secondary users in a spectrum-sharing
environment. In [13], the throughput of a multi-relay system with jamming is
increased using the RL algorithm.

In RL algorithms applied to the RA problem, devices take actions and receive
rewards from the central node indicating the quality of actions taken. RL has
an advantage over more traditional machine learning (ML) techniques in such
crowded RA complex scenarios, as it is not necessary to passively receive a
dataset [14].

A more simplified yet effective RL model for this scenario is the $Q$-learning
(QL), which is a model-free RL [15]. Typically, QL algorithms present reduced
complexity and they are easy to implement in low-power consumption IoT
devices. In [16], QL is used in an IoT environment to increase the success
rate of task scheduling. In our elaborated RA scenario, the device learns
which are the best resource blocks it should transmit based on its $Q$-table
storage of the rewards sent by the central node. The low complexity of QL
makes it suitable to operate in crowded RA scenarios with many devices
randomly transmitting short packets [17, 18]. In [19], an independent QL
technique with a binary reward and a collaborative technique in which the
device receives information on the congestion level of each time slot are
proposed. In [20], a NOMA-based QL algorithm is proposed in which the device
can transmit at up to three different power levels to generate power diversity
at the receiver while increasing throughput. Recently, [21] proposed a packet-
based QL scheme that can benefit devices that still have many packets to
transmit, sending them a bigger reward.

The contribution of this work is twofold: first, we propose a multi-power
levels QL algorithm (MPL-QL), evaluating the impact of increasing power levels
on the throughput and latency, differing from what was done in [20] where only
three power levels are proposed, which does not exploit the full benefit of
the power domain of NOMA. Second, we compare performance metrics, such as
throughput, of the proposed MPL-QL protocol with four well-established RA
protocols, the SA, the independent QL [19], the collaborative QL [19], and the
packet-based QL [21].

The remainder of the paper is composed of the system model described in
Section II; the proposed MPL-QL algorithm is presented in Section III;
numerical results are analyzed in Section IV; the final remarks in Section V
closes the paper.

##  II System model

There are $N$ mMTC devices sending uplink (UL) packets to a central node in a
circular cell with radius $r$. The frequency resources used are a carrier
$f_{c}$ and a bandwidth $B$. The $n$-th device is $d_{n}$ meters away from the
central node and transmits with power $P_{t}$. The distribution of devices
within the circular cell is shown in Fig. 1.

Figure 1: System model.

The transmit frame in the UL is divided into $K$ time slots, while a downlink
(DL) time-slot at the end is deployed for central node broadcast. The devices
randomly select a time-slot to transmit. The set $\psi_{k}$ contains the
indexes of all devices that selected $k$-th time-slot, $k\in\\{1,\dots,K\\}$.
Furthermore, each device has $L$ packets to transmit. The end of system
transmission occurs when all devices successfully transmit all of their $L$
packets. At the end, we define the total latency $\delta$ as the total number
of spent frames to attain convergence, i.e., all packets transmitted
successfully by all devices. Assuming that the DL slot is much smaller than
the UL slot, it is possible to approximate the length of a frame to $K$ time-
slots and the total number of time-slots until the end is $\delta K$. Fig. 2
shows how transmission frames are divided.

Figure 2: Frame in UL and DL time-slots until the end of system transmission
(all devices), namely convergence of transmission process.

The received signal in the central node at the $k$-th time-slot is simply
defined as:

$y_{k}=\sum_{\forall n\in\psi_{k}}x_{n,k}+w_{k},$ (1)

where $x_{n,k}$ is the attenuated signal transmitted by the $n$-th device at
the $k$-th time-slot, and $w_{k}\sim\mathcal{CN}(0,N_{0}B)$ is the additive
white Gaussian noise (AWGN) at the receiver in the $k$-th time-slot with power
spectral density $N_{0}$.

Let’s consider that $h_{n,k}$ is an independent and identically distributed
zero mean and unit variance Rayleigh fading of the $n$-th device at $k$-th
time-slot. Therefore, the instantaneous signal-to-interference-plus-noise
ratio (SINR) received from the $n$-th device at the $k$-th time-slot can be
defined as

$\gamma_{n,k}=\dfrac{P_{n,k}}{\sum_{\forall j\in\psi_{k},j\neq
n}P_{j,k}+w_{k}^{2}},$ (2)

where $P_{n,k}=h_{n,k}^{2}\bar{P}_{n}$ is the instantaneous power of the
$n$-th device at $k$-th time-slot. $\bar{P}_{n}$ is calculated based on the
log-distance path loss model:

$\bar{P}_{n}=P_{t}+\bar{P}_{d_{0}}-10\eta\log_{10}\left(\dfrac{d_{n}}{d_{0}}\right),\;\;\;\text{[dB]}$
(3)

where $\eta$ is the path loss exponent, $d_{0}$ is a reference distance, and
$\bar{P}_{d_{0}}$ is a reference constant power given by

$\bar{P}_{d_{0}}=20\log_{10}\left(\dfrac{c}{4\pi
d_{0}f_{c}}\right).\;\;\;\text{[dB]}$ (4)

Assuming that the devices have the same quality of service (QoS) requirements,
we can set a threshold SINR $\bar{\gamma}$ at the receiver to ensure the
packet can be detected. The packet transmitted by the $n$-th device at $k$-th
time-slot can be successfully received at the central node when
$\gamma_{n,k}\geq\bar{\gamma}$.

##  III Multi-Power Level $Q$-Learning Algorithm

This section describes the proposed multi-power level $Q$-learning-based
grant-free RA procedure. Each device can transmit with a maximum power
$P_{\max}$. The transmitted symbol is then assumed to have maximum amplitude
$V_{\max}$. The symbol $\tilde{x}_{n}$ transmitted by the device can assume
$\mathcal{P}$ equidistant amplitude levels between $-V_{\max}$ and $V_{\max}$,
e.g., for $\mathcal{P}$ = 4,

$\tilde{x}\in\\{-V_{\max},-\dfrac{V_{\max}}{3},\dfrac{V_{\max}}{3},V_{\max}\\}.$

The selection of which time-slot and power level the device will transmit is
based on the $Q$-table indices whose $Q$-value is maximum. When there are two
or more values equal to the maximum, the device randomly selects between them.
Fig. 3 depicts the structure of the power level and time-slot selection based
on the $Q$-table.

Figure 3: $Q$-table for each device.

As the devices present a power disparity given by the differences in distances
and transmission powers, then the central node can apply a successive
interference cancellation (SIC) procedure to remove the interference from the
devices that collided in the same time-slot. With this, the SINR considering
NOMA becomes:

$\gamma_{n,k}^{\textsc{noma}}=\dfrac{P_{n,k}}{\sum_{j=n+1}^{|\psi|}P_{j,k}+w_{k}^{2}}.$
(5)

The transmission of the $n$-th device is successful if

$R_{n,k,p}=\begin{cases}+1,\;\;\text{if}\;\gamma_{n,k}^{\textsc{noma}}\geq\bar{\gamma}\\\
-1,\;\;\text{otherwise.}\end{cases}$ (6)

With the reward received, the device updates its $Q$-table [22]:

$Q_{n,k,p}^{(t+1)}=Q_{n,k,p}^{(t)}+\alpha(R_{n,k,p}-Q_{n,k,p}^{(t)}).$ (7)

where $\alpha\in[0,1]$ is the learning rate of the QL algorithm; the closer to
1, the greater the weight that is given to the rewards sent by the central
node in relation to the current $Q$-value. If the reward received is
$R_{n,k,p}=1$, the success of transmission decrements the number of packets
$\ell_{n}$ that the $n$-th device still has to transmit.

In the context illustrated in Fig. 2, the communication system described in
Section II requires knowledge of the channel state information (CSI) on both
the transmitter and receiver sides to detect the uplink data packets and the
downlink reward. As the valuable information is the uplink packets and the
reward is binary, then a low-complexity channel estimation technique can be
deployed at the device side.

The devices continue transmitting until all of their $L$ packets are
transmitted. Total latency $\delta$ is the number of frames required for the
complete transmission of packets until the algorithm converges. Algorithm 1
indicates the pseudo-code step-by-step of the proposed MPL-QL operation.

###  III-A MPL-QL Complexity

The complexity of the algorithm can be analyzed in two ways:

  * •

Search for the largest $Q$-value within the $Q$-table on the devices side:
increasing $K$ and $\mathcal{P}$ in the system will make the $Q$-table
dimension larger, which consequently increases the search space;

  * •

Application of the SIC on the central node: in scenarios where the load factor
$\mathcal{L}=N/K$ is very high, e.g. $\mathcal{L}\geq 5$ in crowded mMTC
applications, on average more devices will compete for the available time-
slots. The central node needs to apply a SIC to calculate the SINR of each
device and check if the transmission was successful or not to send the reward.
The higher the $\mathcal{L}$, the greater the complexity and lower the
performance in the SIC calculation.

As there is much more processing power in the central node than in mMTC
devices, so the overriding factor of complexity lies in the $Q$-learning
algorithm on the device side. Therefore, it is paramount to find a suitable
value for the number of power levels $\mathcal{P}$, such that the algorithm
performs well without increasing complexity considerably.

Algorithm 1 MPL-QL algorithm

Initialize $Q_{n,k,p}\sim\mathcal{U}[-1,1]$ $\forall n,k,p$;

Initialize $\ell_{n}=L,\;\forall n$;

Initialize $\delta=0,\;S=0$

while $\sum_{n=1}^{N}\ell_{n}>0$ do

for all devices that $\ell_{n}>0$ do

Search $k$ and $p$ where

$\;Q_{n,k,p}=\max\limits_{k,p}\\{Q_{n,k,p}\\}$

for all time-slots $k=1:K$ do

if $|\psi_{k}|>0$ then

Calculate $\gamma_{n,k}^{\textsc{noma}}$ using Eq. (5) $\forall n\in\psi_{k}$

if $\gamma_{n,k}^{\textsc{noma}}\geq\bar{\gamma}$ then

Success: $S\leftarrow S+1,\;\ell_{n}\leftarrow\ell_{n}-1$

$R_{n,k,p}$ = 1

else

$R_{n,k,p}$ = -1

Update: $Q_{n,k,p}^{(t+1)}=Q_{n,k,p}^{(t)}+\alpha(R_{n,k,p}-Q_{n,k,p}^{(t)})$

Increment a frame: $\delta\leftarrow\delta+1$

##  IV Numerical Results

This section analyzes the performance and convergence of the MPL-QL algorithm.
Performance is measured by throughput and latency, and convergence is analyzed
by interference per device and convergence factor. The system simulations for
the QL algorithms were coded in Python language [23], with Table I presenting
a summary of the parameter values adopted along this section.

Table I: Numerical parameters. Parameter | Value
---|---
Monte-Carlo realizations | $\mathcal{M}=10000$
Time-slots per frame |  $K$ = 100
Network loading factor | $\mathcal{L}=\frac{N}{K}\in[0.25;\,\,10]$
Packets per device |  $L\in$ [50; 100]
Learning rate |  $\alpha$ = 0.1
SINR threshold |  $\bar{\gamma}$ = 3
Transmit power levels | $\mathcal{P}\in[2;4;8;12;16]$
Cell radius |  $r$ = 200 m
Reference distance |  $d_{0}$ = 1 m
Bandwidth |  $B$ = 125 kHz
Carrier frequency |  $f_{c}$ = 915 MHz
Path loss exponent |  $\eta$ = 3 (4.77 dB)
Noise PSD |  $N_{0}$ = $-150$ dBm/Hz
Maximum power |  $P_{\max}$ = 1 mW

The value of the chosen carrier frequency, bandwidth, and cell size parameters
are typical of IoT scenarios, and the amount of devices represents a crowded
NOMA mMTC scenario. The typical SINR threshold was selected as $\bar{\gamma}$
= 3, considering that the outage probability is a suitable metric for the
communication system performance evaluation [20]. Hence, considering the limit
of Shannon capacity, if the required SINR is bounded by:

$\gamma_{n,k}^{\textsc{noma}}\geq 2^{\zeta}-1,$ (8)

where $\zeta$ is the spectral efficiency in bits/s/Hz; hence, the adopted
(selected) spectral efficiency of $\zeta$ = 2 bits/s/Hz makes $\bar{\gamma}$ =
3.

###  IV-A Throughput and Latency of MPL-QL algorithm

Throughput $\tau$ is calculated as the ratio between the total number of
successes $S$ and the total number of time-slots required for the algorithm to
converge:

$\tau=\dfrac{S}{\delta K},\quad\quad\left[\dfrac{\text{success}}{\text{time-
slot}}\right]$ (9)

Throughput indicates on average how many devices can successfully transmit
their packets within a time-slot. In Fig. 4, the throughput of the MPL-QL
technique is analyzed as a function of the loading factor for different power
levels ($\mathcal{P}\in\\{2,4,8,12,16\\}$).

Figure 4: MPL-QL throughput for different power levels $\mathcal{P}$.

Note that the higher the number of power levels, the higher the throughput.
Hence, the higher the power levels available at the transmitter, the greater
the power difference between the desired signal and the interference at the
receiver. This makes the SIC receiver able to detect more packets successfully
under a specific limit of the number of power levels since, for a convenient
SIC operation, a minimum received power difference between the desired user
and the interfering user of the same time-slot must be guaranteed.

When increasing the power levels from 12 to 16, a marginal gain in throughput
was observed. In this scenario, there is no significant increase in the power
disparity that arrives at the receiver, so a maximum number of possible
successes is reached after SIC detection. As the increase in the number of
power levels causes an increase in the size of the $Q$-table that the device
needs to store, it is possible to say that a good number for power levels is
between 8 and 12, as a good performance-complexity trade-off is guaranteed to
devices.

In Fig. 5, the latency $\delta$ needed to obtain the algorithm’s convergence
was analyzed considering the same power levels used in Fig. 4.

Figure 5: MPL-QL latency (total number of frames).

Latency decreases with increasing power levels. Considering a loading factor
$\mathcal{L}$ = 6, the latency for $\mathcal{P}$ = 8 is $\approx 30$% lower
compared to $\mathcal{P}$ = 2. Analogously to what was discussed in Fig. 4,
with a higher value of number of power levels $\mathcal{P}$, the devices have
a larger pool of choices of power levels, and they learn from experience which
levels are best for transmission, which decreases the probability of
collisions and consequently decreases latency.

The differences (reduction) of latency for power levels $\mathcal{P}>8$ become
marginal, which again indicates that a suitable power level guaranteeing a
good performance-complexity trade-off is close to 8. This is because the
granularity is increased by increasing the power levels. As a result, two or
more devices that collide in the same time-slot will have similar power
levels. Therefore, the SINR will result higher when the granularity is
improved (more power levels), which decreases the number of successes the
algorithm can attain. The value of $\mathcal{P}=8$ power levels was used in
the remainder of this section.

###  IV-B Learning Rate for the MPL-QL algorithm

The results of Fig. 4 and Fig. 5 were generated considering $\alpha$ = 0.1, a
typical value found in the literature [19, 20, 21], as it considers that each
reward sent by the central node weights only 10% in each $Q$-table update.
However, when proposing the MPL-QL algorithm in the NOMA scenario, it is
necessary to assess whether the change in the value of $\alpha$ impacts the
choice of the most suitable $\mathcal{P}$. Fig. 6 shows the latency of the
MPL-QL algorithm when the learning rate varies within a range
$\alpha\in[0.05;0.5]$. In this numerical result, $K$ = 100 time-slots and a
loading factor $\mathcal{L}$ = 5 have been considered.

Figure 6: MPL-QL latency for different values of $\alpha$.

The MPL-QL algorithm presents an approximate constant latency up to $\alpha$ =
0.3 because the weight given to the rewards is low. $Q$-table changes are made
smoothly so that the wrong decisions at the devices regarding the transmission
resources do not negatively impact the packet deliver evolution of the
proposed algorithm.

The algorithm latency grows substantially by considering increasing learning
rate scenarios in the $0.3\leq\alpha<0.5$. As $\mathcal{L}=5$ is a very
crowded load factor, it is natural that many collisions occur and many
negative rewards are sent by the central node since there are, on average,
five devices disputing the same time-slot. As $\alpha$ increases, the weight
given to negative rewards grows. Therefore, devices make more wrong decisions
and take longer to find the best time and power resources to transmit packets
successfully.

On the other hand, as the value of $\mathcal{P}$ increases, the delay in
delivering the total number of packets of all users decreases. However, from
$\mathcal{P}$ = 8, the decrease in latency becomes marginal, corroborating the
same behavior already observed in the results of throughput (Fig. 4) and
latency vs. loading factor in Fig. 5. Hence, $\mathcal{P}$ = 8 represents a
suitable performance-complexity trade-off for the proposed MPL-QL algorithm.
Finally, from the numerical experiments in Fig. 4, 5, and 6, one can infer
that changes in the learning rate do not dramatically affect the choice of the
most suitable value for the number of power levels $\mathcal{P}$.

###  IV-C Convergence of MPL-QL algorithm

The convergence of the MPL-QL algorithm is analyzed by two figures of merit:
interference per device and convergence factor per device. The analysis was
performed only for the $n$-th device, but on average, the figures of merit for
all devices reveal the same behavior.

The interference $I_{n,k}$ of the $n$-th device at $k$-th time-slot is
calculated as the sum of the powers of the interfering devices that selected
the same time-slot, defined by the subset $\psi_{k}$; after SIC detection such
interference can be calculated as

$I_{n,k}=\sum_{j=n+1}^{|\psi_{k}|}P_{j,k},\quad\quad[W]$ (10)

while the convergence factor is defined as

$\nu_{n}=\dfrac{L-\ell_{n}}{L}.$ (11)

At the beginning of the algorithm execution, the $n$-th device transmitted
only a few packets successfully, so $\nu_{n}\rightarrow 0$. When the algorithm
is close to the convergence, the $n$-th device has already transmitted most of
its packets, making $\nu_{n}\rightarrow 1$. Fig. 7 depicts the interference
along the frames for the $n$-th device considering a) $L=50$, b) $L=100$
[packets/device], and c) convergence factor vs. the frame ($\delta$) evolution
until convergence ($\nu_{n}=1$).

Figure 7: Interference and convergence factor of the MPL-QL algorithm
considering the $n$-th device. a) $L$ = 50 packets; b) $L$ = 100 packets; c)
convergence factor under $L$ = 100 packets.

At the beginning of transmission frames, the MPL-QL algorithm can make wrong
decisions in choosing the best time-slots and power levels to transmit. Hence,
there is an oscillating behavior of high interference in the early frames.
After a latency $\delta\approx L$ frames, i.e., $L=50$ and $100$ frames in
Fig. 7, device interference starts to decrease steadily as devices have
already passed the initial learning phase and begin to discover better time-
slots and power levels to transmit their packets with a greater probability of
success. Indeed, when the number of frames equals $L$, many devices have
already transmitted all their packets, as they initially selected the least
congested time-slots. Therefore, more empty time-slots start to appear for the
$n$-th device, which makes their interference monotonically decrease after $L$
frames.

Increasing the loading factor causes more devices to collide in the same time-
slot, which causes an increase in the average interference per device. For
this reason, in Fig. 7a) and 7b), the two scenarios with a loading factor
$\mathcal{L}$ = 6 have more significant interference compared to $\mathcal{L}$
= 3. Moreover, increasing power levels makes the average interference lower.
With more power levels, the greater the signal power disparity of the devices
that collide in the same time-slot, making the difference between the power of
interest and the interfering one greater.

By increasing the loading factor $\mathcal{L}$, more devices are transmitting
in the available time-slots. This causes the interference to increase, causing
more collisions to happen and increasing the convergence time of the
algorithm. For this reason, it is possible to observe that the curves for
$\mathcal{L}$ = 3 converge faster than the curves for $\mathcal{L}$ = 6.

Increasing the number of power levels also makes convergence occur faster.
This is because more available power levels generate a power disparity between
two or more devices that collide in the same time-slot, making the signal from
the device with the highest power level even more remarkable in relation to
the interfering ones. In Fig. 7c), it can be seen that the number of power
levels $\mathcal{P}$ = 8 converged faster than the $\mathcal{P}$ = 2 in both
loading factor scenarios.

###  IV-D Comparison with Other RA Methods

The performance of the proposed MPL-QL algorithm was compared with other
methods available in the literature, specifically: a) Slotted Aloha (SA),
where there is no feedback from the central node to the devices. The devices
only send all their UL packets and the number of successes is obtained when
there is no collision; b) Independent QL [19]; c) Collaborative QL [19]; and
Packet-Based QL [21].

All QL algorithms are applied to a NOMA scenario, as there is no single
orthogonal time-slot allocation for each device, as devices randomly select
which time-slot to transmit. The central node uses SIC to eliminate
interference between devices, so the SINR is calculated using Eq. 5 to decide
if the transmission was successful.

As the QL mentioned above techniques do not consider different transmitter
power levels, the transmitted power is the same for all devices. This impacts
the evolution of the QL algorithm; hence, as the $Q$-table reveals in Fig. 3,
it does not present the dimension of the powers for such techniques, being
considered only the time-slots dimension. Thus, the device learning process is
performed only to find the best time-slot for transmission with minimal
probability of collision.

The difference between the three QL-based algorithms deployed in the
comparison is how the central node does the reward. Hence, in the independent
QL algorithm, the reward sent by the central node is defined as:

$R_{n,k}^{\textsc{ind}}=\begin{cases}+1,\;\;\text{if}\;\gamma_{n,k}^{\textsc{noma}}\geq\bar{\gamma}\\\
-1,\;\;\text{otherwise.}\end{cases}$ (12)

It is a binary reward, similar to the MPL-QL, but it is performed only in the
time-slot dimension. On the other hand, for the collaborative QL, the
congestion level of the time-slot is defined as:

$C_{k}=\dfrac{|\psi_{k}|}{N};$ (13)

and included in the adverse reward of collaborative QL:

$R_{n,k}^{\textsc{col}}=\begin{cases}+1,\;\;\text{if}\;\gamma_{n,k}^{\textsc{noma}}\geq\bar{\gamma}\\\
-C_{k},\;\;\text{otherwise.}\end{cases}$ (14)

As a result, the collaborative QL algorithm is more complex than independent
QL since the central node needs to know the number of devices colliding in
each time-slot. However, the performance is superior as more information
related to the system state is sent during the execution of the algorithm
[19].

The packet-based QL considers the convergence factor of Eq. (11) and includes
such factor in the its reward:

$R_{n,k}^{\textsc{pac}}=\begin{cases}+1,\hskip
31.29802pt\text{if}\;\gamma_{n,k}^{\textsc{noma}}\geq\bar{\gamma}\\\
-{\dfrac{L-\ell_{n}}{L}},\;\;\text{otherwise.}\end{cases}$ (15)

Packet-based QL random access strategy favors devices that still have a lot of
packets to transmit, sending them a greater reward w.r.t. devices that are
already close to convergence [21].

Fig. 8.a) shows the normalized throughput and Fig. 8.b) depicts the latency
against loading factor $\mathcal{L}$ for the proposed MPL-QL algorithm, the
Slotted Aloha, and the other three QL-based algorithms in the literature. For
these results, $K$ = 100 time-slots/frame and $L$ = 100 packets per device
were considered. SA is the most straightforward RA protocol since devices
randomly select a time-slot with no reward sent by the central node to
indicate transmission quality. For this reason, the SA throughput is the worst
among all the analyzed techniques. Independent and collaborative QL techniques
have higher throughput than SA as central node rewards are used for devices to
better select which time-slots to transmit. In [19], it is noted that the
collaborative QL performs better than the independent QL. However, by adding
the power domain in NOMA scenarios, the performance of the techniques becomes
the same.

Figure 8: a) Throughput, and b) Latency for the SA and four QL-based
algorithms, with $\mathcal{P}$ = 8 for the proposed MPL-QL. $L$ = 100 and $K$
= 100.

The proposed MPL-QL random access method has presented a substantial increase
in the throughput and simultaneously decrease in the latency for higher
loading factors, $\mathcal{L}$. Such system throughput and latency
improvements can be explained by the fact that in the realistic scenario where
devices are subject to the effects of path loss and fading, increasing the
power diversity at the transmitter allows nearby devices to transmit at
different powers, which increases the SINR after the SIC, at the receiver
side. Therefore, more successes are expected when using MPL-QL compared to
other QL algorithms, increasing the throughput.

Elaborating further, when analyzing the throughput in Fig. 8a) and latency in
Fig. 8b), one infers that the power domain can be advantageous to allocate
more devices in a time-slot. The QL-based algorithms in the literature
exploring only the time-slot domain do not take advantage of the power
diversity in the transmitter to avoid collisions, so they tend to converge
more slowly. Hence, for a loading $\mathcal{L}={4}$, where there are on
average 4 devices transmitting per time-slot, the SA protocol is capable of
generating little more than $\frac{1}{10}$ success. On the other hand,
independent and collaborative QL-based RA algorithms are able to generate
$1.7$ successes, while the proposed MPL-QL generates $2.3$ successes.
Therefore, it is shown that, on average, the MPL-QL is able to better deal
with the collisions between devices, mainly when the loading factor increasing
beyond $3$.

###  IV-E QL-based RA Techniques with Imperfect SIC

The previous results were obtained considering that the central node applies a
perfect SIC when receiving packets. However, error-free cancellation is
difficult to achieve in crowded mMTC scenarios due to the different levels of
interference affecting each signal device. In this subsection, we consider an
imperfect SIC model in which there is a residue of the powers of devices that
have already passed through the SIC modeling the poor signal-canceling effect.
Hence, considering NOMA, the new SINR with the imperfect SIC can be written
as:

$\tilde{\gamma}_{n,k}^{\textsc{noma}}=\dfrac{P_{n,k}}{\beta\sum_{j=0}^{n-1}P_{j,k}+\sum_{j=n+1}^{|\psi|}P_{j,k}+w_{k}^{2}}.$
(16)

where $\beta\in[0,1]$ is the SIC error factor. $\beta=0$ indicates that the
interference is perfectly cancelled, collapsing in Eq. (5), while when
$\beta=1$, models the absence of SIC procedure at the central node. Typical
realistic values for the error factor are in range
$\beta\in\\{0.01;\,\,0.30\\}$, depending on the level of interference and the
received power disparities distribution.

Fig. 9 depicts a comparison of the throughput of QL-based techniques
considering $\beta\in[0;\,0.1;\,0.2]$. As expected, increasing $\beta$ worsens
the throughput of all algorithms as interference increases, increasing
collision and latency until the algorithm attains convergence. Notice that
increasing the value of $\beta$ decreases the maximum number of devices the
system serves. MPL-QL achieves maximum throughput for a loading factor
$\mathcal{L}$ = 6 operating under perfect SIC, i.e., $\beta$ = 0. For $\beta$
= .01 and $\beta$ = 0.02, the loading factor to achieve maximum throughput is
reduced to $\mathcal{L}=3$ and $\mathcal{L}=2$, respectively. Such a decrease
is also due to increased latency and interference that can not be canceled
($\beta\neq 0$). The MPL-QL method proved to be superior to the other QL-based
algorithms in all RA crowded scenarios, thanks to the greater power-level
granularity, allowing the power differences between the desired device and the
interferers larger, reducing collisions.

Figure 9: Independent QL, Packet-based QL and MPL-QL under SIC imperfection:
a) $\beta$ = 0; b) $\beta$ = 0.01; $\beta$ = 0.02. We considered $L$ = 100 and
$K$ = 100.

##  V Conclusions

The performance and convergence of the proposed MPL-QL method for different
power-levels granularity have been characterized and compared with other QL-
based RA algorithms. It was observed that the best number of power levels that
guarantee a good performance-complexity trade-off is $\mathcal{P}=8$ levels.
This value was used to compare the throughput with other recent grant-free RA
algorithms, namely the independent, collaborative, and packet-based QL-based
algorithms and the classical SA method. The $8$-levels MPL-QL technique has
revealed the best performance compared to the other analyzed RA techniques due
to the enough power diversity generated by the MPL-QL technique, improving the
SINR at the receiver side while increasing the chance of successful
transmissions of a more significant number of devices in crowded RA scenarios.

The proposed MPL-QL method demonstrated superiority in both throughput and
latency regarding the other QL-based algorithms in all RA crowded scenarios
analyzed, due to the greater power-level granularity, allowing the power
differences between the desired device and the interferers to be larger,
reducing collisions.

## Acknowledgment

This work was supported in part by the Coordenação de Aperfeiçoamento de
Pessoal de Nível Superior - Brazil (CAPES) - Finance Code 001, in part by the
National Council for Scientific and Technological Development (CNPq) of Brazil
under Grant 310681/2019-7, and in part by Fundação Araucária, Paraná State,
Brazil under Grant PBA-2016.

## References

  * [1] H.-M. Chen, J. Liu, H. Su, S. Lin, J. Zhu, and L. Chen, “Towards energy and resource efficient design for scalable mMTC with a distributed energy-restricted cluster based transmission scheme,” in _2020 International Wireless Communications and Mobile Computing (IWCMC)_ , 2020, pp. 1309–1313.
  * [2] C. Kalalas and J. Alonso-Zarate, “Massive connectivity in 5G and beyond: Technical enablers for the energy and automotive verticals,” in _2020 2nd 6G Wireless Summit (6G SUMMIT)_ , 2020, pp. 1–5.
  * [3] M. Z. Chowdhury, M. Shahjalal, S. Ahmed, and Y. M. Jang, “6G wireless communication systems: Applications, requirements, technologies, challenges, and research directions,” _IEEE Open Journal of the Communications Society_ , vol. 1, pp. 957–975, 2020.
  * [4] D. C. Nguyen, M. Ding, P. N. Pathirana, A. Seneviratne, J. Li, D. Niyato, O. Dobre, and H. V. Poor, “6G internet of things: A comprehensive survey,” _IEEE Internet of Things Journal_ , pp. 1–1, 2021.
  * [5] Y. L. Lee, D. Qin, L.-C. Wang, and G. H. Sim, “6G massive radio access networks: Key applications, requirements and challenges,” _IEEE Open Journal of Vehicular Technology_ , vol. 2, pp. 54–66, 2021.
  * [6] W. Jiang, B. Han, M. A. Habibi, and H. D. Schotten, “The road towards 6G: A comprehensive survey,” _IEEE Open Journal of the Communications Society_ , vol. 2, pp. 334–366, 2021.
  * [7] J. R. Bhat and S. A. Alqahtani, “6G ecosystem: Current status and future perspective,” _IEEE Access_ , vol. 9, pp. 43 134–43 167, 2021.
  * [8] P. Popovski, K. F. Trillingsgaard, O. Simeone, and G. Durisi, “5G wireless network slicing for eMBB, URLLC, and mMTC: A communication-theoretic view,” _IEEE Access_ , vol. 6, pp. 55 765–55 779, 2018.
  * [9] J. Jiao, L. Xu, S. Wu, R. Lu, and Q. Zhang, “MSPA: Multi-slot pilot allocation random access protocol for mMTC-enabled IoT system,” _IEEE Internet of Things Journal_ , pp. 1–1, 2021.
  * [10] T. Wang, Y. Wang, C. Wang, Z. Yang, and J. Cheng, “Group-based random access and data transmission scheme for massive mtc networks,” _IEEE Transactions on Communications_ , pp. 1–1, 2021.
  * [11] O. S. Nishimura, J. C. Marinello, and T. Abrão, “A grant-based random access protocol in extra-large massive MIMO system,” _IEEE Communications Letters_ , vol. 24, no. 11, pp. 2478–2482, 2020.
  * [12] L. Zeng and J. Zhang, “Multi-agent spectrum access with sensing skipping based on reinforcement learning,” _Transactions on Emerging Telecommunications Technologies_ , vol. 32, no. 9, p. e4264, 2021. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/ett.4264
  * [13] L. Huang, T. Xu, X. Chen, Y. Xu, X. Zhang, and G. Fang, “Joint relay and channel selection in relay-aided anti-jamming system: A reinforcement learning approach,” _Transactions on Emerging Telecommunications Technologies_ , vol. 32, no. 9, p. e4243, 2021. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/ett.4243
  * [14] M. Mohri, A. Rostamizadeh, and A. Talwalkar, _Foundations of Machine Learning_ , 2nd ed. Cambridge: The MIT Press, 2018.
  * [15] M. Wiering and M. van Otterlo, _Reinforcement Learning: State-of-the-Art_ , 1st ed. Berlin: Springer-Verlag, 2012.
  * [16] J. Ge, B. Liu, T. Wang, Q. Yang, A. Liu, and A. Li, “Q-learning based flexible task scheduling in a global view for the internet of things,” _Transactions on Emerging Telecommunications Technologies_ , vol. 32, no. 8, p. e4111, 2021. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/ett.4111
  * [17] O. J. Pandey, T. Yuvaraj, J. K. Paul, H. H. Nguyen, K. Gundepudi, and M. K. Shukla, “Improving energy efficiency and QoS of LPWANs for IoT using Q-Learning based data routing,” _IEEE Transactions on Cognitive Communications and Networking_ , pp. 1–1, 2021.
  * [18] D.-D. Tran, S. K. Sharma, S. Chatzinotas, and I. Woungang, “Q-Learning-Based SCMA for efficient random access in mMTC networks with short packets,” in _2021 IEEE 32nd Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)_ , 2021, pp. 1334–1338.
  * [19] S. K. Sharma and X. Wang, “Collaborative distributed Q-learning for RACH congestion minimization in cellular IoT networks,” _IEEE Communications Letters_ , vol. 23, no. 4, pp. 600–603, 2019.
  * [20] M. V. da Silva, R. D. Souza, H. Alves, and T. Abrão, “A NOMA-based Q-learning random access method for machine type communications,” _IEEE Wireless Communications Letters_ , vol. 9, no. 10, pp. 1720–1724, 2020.
  * [21] G. M. F. Silva and T. Abrão, “Throughput and latency in the distributed Q-learning random access mMTC networks,” _Computer Networks_ , vol. 206, p. 108787, 2022.
  * [22] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_ , 2nd ed. Cambridge: The MIT Press, 2018\.
  * [23] N. Habib, _Hands-On Q-Learning with Python_ , 1st ed. Birmingham: Packt Publishing Ltd, 2019.