# Learning Emergent Random Access Protocol for LEO Satellite Networks

Ju-Hyung Lee, Hyowoon Seo, Jihong Park,
Mehdi Bennis, and Young-Chai Ko J.-H. Lee and Y.-C. Ko are with the School of
Electrical and Computer Engineering, Korea University, Seoul 02841, Korea
(e-mail: {leejuhyung, koyc}@korea.ac.kr).J. Park is with the School of
Information Technology, Deakin University, Geelong, VIC 3220, Australia
(e-mail<EMAIL_ADDRESS>gist.ac.kr}).H. Seo and M. Bennis are
with the Centre for Wireless Communications, University of Oulu, Oulu 90014,
Finland (e-mail: {hyowoon.seo, mehdi.bennis}@oulu.fi).

###### Abstract

A mega-constellation of low-altitude earth orbit (LEO) satellites (SATs) are
envisaged to provide a global coverage SAT network in beyond fifth-generation
(5G) cellular systems. LEO SAT networks exhibit extremely long link distances
of many users under time-varying SAT network topology. This makes existing
multiple access protocols, such as random access channel (RACH) based cellular
protocol designed for fixed terrestrial network topology, ill-suited. To
overcome this issue, in this paper, we propose a novel grant-free random
access solution for LEO SAT networks, dubbed _emergent random access channel
protocol (eRACH)_. In stark contrast to existing model-based and standardized
protocols, eRACH is a model-free approach that emerges through interaction
with the non-stationary network environment, using multi-agent deep
reinforcement learning (MADRL). Furthermore, by exploiting known SAT orbiting
patterns, eRACH does not require central coordination or additional
communication across users, while training convergence is stabilized through
the regular orbiting patterns. Compared to RACH, we show from various
simulations that our proposed eRACH yields $54.6$% higher average network
throughput with around two times lower average access delay while achieving
$0.989$ Jain’s fairness index.

###### Index Terms:

LEO satellite network, random access, emergent protocol learning, multi-agent
deep reinforcement learning, 6G.

##  I Introduction

We are at the cusp of an unprecedented revolution led by thousands of low
earth orbit (LEO) satellites (SATs) in space. SpaceX has already launched more
than 1,500 Starlink LEO SATs [1, 2, 3] covering 12 countries in 3 different
continents [4]. Besides, federal communications commission (FCC) has recently
authorized Amazon Project Kuiper to launch half of 3,236 LEO SATs by 2026 and
the rest by 2029 [5]. The ramification of this LEO SAT mega-constellation is
not only limited to advancing conventional SAT applications such as high-
precision earth observation [6] but also envisaged to open up a new type of
wireless connectivity, i.e., non-terrestrial networks (NTNs) in beyond the
fifth-generation (5G) or 6G cellular systems [7]. While each SAT plays a role
as a mobile base station (BS), a mega-constellation of LEO SATs has a great
potential in provisioning fast and reliable connectivity to ground users
anywhere in the globe, including ocean, rural areas, and disaster sites [8, 9,
10].

Notwithstanding, each SAT BS has an extremely wide coverage (e.g., $160-1000$
[km] inter-SAT BS distance [11]), disallowing sophisticated central
coordination among SAT BSs and users in real-time under limited communication
and computing resources. Furthermore, as opposed to fixed terrestrial BSs, SAT
BSs move, requiring location-specific resource management. Unfortunately,
existing model-based and standardized protocols, such as carrier-sense
multiple access (CSMA) based WiFi protocols and random access channel (RACH)
based cellular protocols, cannot flexibly optimize their operations without
incurring severe protocol fragmentation, not to mention a significant effort
in protocol standardization for a myriad of possible scenarios.

To overcome the aforementioned fundamental challenges in LEO SAT networks, in
this article, we develop a novel model-free random access (RA) protocol that
naturally emerges from a given local SAT random access environment, dubbed
_emergent random access channel protocol (eRACH)_. In eRACH, the emergence of
RA protocol is induced by deep reinforcement learning (DRL) at the ground user
agents by utilizing locally observable information, not requiring inter-agent
communication or centralized training. Consequently, eRACH jointly takes into
account SAT associations and RA collision avoidance in a given local
environment, thereby achieving lower RA latency and high downstream
communication efficiency after eRACH.

The fundamentals of eRACH are laid by _protocol learning_ via multi-agent DRL
(MADRL). Several recent works have underpinned the effectiveness of protocol
learning [12, 13, 14] in that the learned protocols can adapt to various
environments while achieving higher communication efficiency than those of
model-based protocols. However, these benefits come at the cost of additional
inter-agent communication for MADRL, which are non-negligible under non-
stationary network topologies, questioning the feasibility of protocol
learning for LEO SAT networks. In fact, MADRL agents in [12, 13, 14] learn to
communicate by exchanging local state information of each agent using a few
bits, where the information exchange between agents is often referred to as a
_cheap talk_. Such cheap talks may no longer be cheap under a non-stationary
topology of an LEO SAT network, which may require a large amount of local
state information for RA and SAT BS associations.

In this respect, our proposed eRACH is designed based on locally observable
information. We extensively test which of the locally observable information
candidates are essential on eRACH training. Surprisingly, it is shown that
eRACH does not even require cheap talks. Instead, eRACH exploits 1) the
expected SAT location that is known a priori owing to the pre-determined SAT
orbiting pattern and 2) the collision events that are inherently observable
without additional costs. While training eRACH, we have validated that the
expected SAT location contains sufficient information on the network topology,
as long as the variance between the expected and the actual SAT locations is
less than 1 [km]. Furthermore, we have realized that the collision event
contains sufficient information on how crowded each SAT BS is. Given 1) and
2), thanks to the periodic orbiting pattern of LEO SAT, the problem of MADRL
frequently revisits the almost identical environment, ensuring to discover an
optimal protocol carrying out SAT BS association and RA decisions.

We summarize our contributions in this paper as follows.

  * •

We propose a novel emergent RA protocol for a ground-to-LEO SAT communication
network, dubbed eRACH. To the best of our knowledge, this is the first of its
kind to show that a new protocol that collaborates between multi-agents can
emerge by utilizing just locally observable information, especially suited for
LEO SAT networks. This is done by developing an actor-critic-based neural
network architecture and a fully distributed MADRL framework without any
inter-agent communication (see Algorithm 1 in Sec. IV).

  * •

To provide an upper-bound performance, we additionally introduce a cheap-talk
inter-agent communication into eRACH, and propose a variant of eRACH, termed
eRACH-Coop (see Sec. V-A).

  * •

Numerical results corroborate that while eRACH-Coop achieves the highest
average network throughput with the lowest collision rate at the cost of the
cheap talk overhead, eRACH still achieves up to $6.02$x and $54.6\%$ higher
average network throughput with $10$x and $2$x lower average RA latency than
slotted ALOHA and conventional cellular RACH, respectively (see Table II in
Sec. V).

  * •

Furthermore, the distributed operations and the limited local information of
eRACH inherently promote equal RA opportunities for all users, yielding 23.6%
higher Jain’s fairness than eRACH-Coop (see Table II in Sec. V).

The remainder of this article is organized as follows. In Sec. II, we first
summarize the RA protocols for the traditional stationary SAT and for the
emerging non-stationary SAT networks. In Sec. III, network model, system
scenario, and performance matrices are presented. Then, the emergent
contention-based RA for the LEO SAT networks, called eRACH, is proposed, which
is addressed by our proposed multi-agent Actor-Critic based algorithm in Sec.
IV. In Sec. V, simulation results are provided, followed by concluding remarks
in Sec. VI.

Notation: Throughout this paper, we use the normal-face font to denote
scalars, and boldface font to denote vectors. We use $\mathbb{R}^{D\times 1}$
to represent the $D$-dimensional space of real-valued vectors. We also use
$\|\cdot\|$ to denote the $L^{2}$-norm, which is a Euclidean norm, and use
$(\cdot)^{{\dagger}}$ to represents conjugate transpose.
$\nabla_{\mathbf{x}}f(\mathbf{x})$ denotes the gradient vector of function
$f(\mathbf{x})$, i.e., its components are the partial derivatives of
$f(\mathbf{x})$. $\mathbf{I}_{N}$ is the identity matrix of size $N$.

Figure 1: An illustration of random access in LEO satellite networks.

##  II Related Works and Backgrounds

###  II-A Random Access for Satellite Networks

In traditional SAT networks, most of the access protocols have been developed
for geosynchronous equatorial orbit (GEO) SATs, also known as geostationary
SATs [15]. Slotted ALOHA scheme is widely used for GEO SAT network systems
owing to its simple implementation. Various types of slotted ALOHA have been
further proposed, taking into account the characteristics of GEO SAT,
including large propagation latency [16, 17]. However, these ALOHA-based
access protocols fail to support many user terminals due to a lack of
collision control. Designing multiple access protocols for SAT networks, long
round trip time (RTT) latency limits the adoption of conventional access
techniques, such as CSMA/CA. Such long RTT latency is induced by long one-way
propagation delay in GEO SAT network (approximately $120$ [ms]) and in LEO SAT
network (approximately $1$ \- $5$ [ms]). Particularly for GEO SAT networks,
centralized reservation schemes are employed which avoid failed access
attempts prior to the packet transmission to cope with such long RTT latency
[15]. However, for LEO SAT networks which connect a myriad of scattered
terrestrial user terminals, the coordinated method requires a significant
system overhead.

In contrast to stationary GEO SAT networks, emerging LEO SAT networks, wherein
numerous LEO SATs orbit rapidly at a speed of around $7.6$ [km/s] (see Fig.
1), are dynamic and require frequent and fast handovers [18, 19], calling for
another channel access considering not only long RTT latency but also the
inherent dynamics of LEO SAT networks. In this regard, the contention-based
random access channel (RACH), adopted for cellular networks (e.g., 5G NR, 4G
LTE/LTE-A), is also considered for LEO SAT networks [20, 21]. The contention-
based RACH procedure is used to initialize and synchronize prior to allocating
resources in downlink (DL) and uplink (UL) channels. In the RACH, a sender
randomly transmits short packet preambles to the receiver and then waits for a
positive response from the receiver prior to transmitting the complete
message. Particularly, the RACH protocol is initiated by transmission of a
randomly chosen preamble through physical RACH (PRACH) for the preamble
transmission. The basic RACH is designed to follow the four-step message
exchanging procedure, that is, 1) PRACH transmission, 2) random access
response (RAR), 3) radio resource control (RRC) connection request, and 4) an
RRC connection setup (and resolution). By the four-step procedure and
utilizing Zadoff-Chu (ZC) sequences, RACH is able to control collision events
while attempting to access many users. Despite this, RACH is not ideally
suited for LEO SAT networks as it does not takes into account SAT associations
[22, 23]. As such, existing access protocols have some limitations for non-
stationary LEO SAT networks.

To design LEO SAT-oriented access protocol, we need to consider the following
two conditions: 1) Collisions needs to be managed efficiently without
centralized access control; and 2) SAT associations and backoff mechanisms
need to be jointly optimized to achieve low access delay and high spectral
efficiency. The current standardized protocols and archetypical model-based
algorithms face several challenges, mainly due to the non-stationarity of the
LEO SAT network topology. Recently, a model-free protocol has been studied in
the context of emergent communication, using model-free DRL algorithms, e.g.,
Actor-Critic [24], $Q$-learning [25], and deep deterministic policy gradient
(DDPG) [26], which can be an alternative solution for the time-varying network
topology.

###  II-B Emergence of Protocol through MADRL

Pioneered by [12, 27], the topic of emergent communication has arisen firstly
in the deep learning literature. In [12], Foerster et al. studied how
languages emerge and how to teach natural languages to artificial agents.
Spurred by this trend of emergent communication, Hoydis et al. adopted the
idea of emergent communication into cellular systems in [13, 14]. Here, MAC
signaling is interpreted as a language spoken by the user equipment (UE) and
the base station (BS) to coordinate while pursuing the goal of delivering
traffic across a network. Therein, two distinct policies (i.e., a channel
access policy and a signaling policy) are trained by using the off-the-shelf
learning-to-communicate (L2C) techniques (e.g., DIAL and RIAL in [12]). This
approach has shown the potential of the emergent protocol design in their
particular scenario.

Despite the novelty of [13, 14], the superior performance of the learned
protocol largely depends on the learning of cheap-talk exchanged between
network nodes, which incurs additional communication and learning overhead.
Moreover, the proposed method assumes centralized training that requires each
network node to obtain full-observable information; it is an obstacle to
actual system application. Besides, in these works, the protocol was optimized
for only stationary networks. Thus, it is still questionable whether a
protocol for non-stationary networks can emerge without relying too much on
information exchange between agents.

##  III System Model

###  III-A Network and Channel Models

Consider a set $\mathcal{K}$ of orbital planes around the earth, sets
$\mathcal{I}_{k}$ of LEO SATs orbiting on the orbital plane $k$ for all
$k\in\mathcal{K}$, and a set $\mathcal{J}$ of SAT user terminals (UTs)
deployed on the ground inside an area $A$. The position of UT
$j\in\mathcal{J}$ is expressed as a 3-dimensional real vector on Cartesian
coordinates denoted by ${\bf\it
q}_{j}=(q^{x}_{j},q_{j}^{y},q_{j}^{z})\in\mathbb{R}^{3}$, and similarly, the
position and velocity of SAT $i\in\bigcup_{k\in\mathcal{K}}\mathcal{I}_{k}$ at
time $t\geq 0$ is denoted by ${\bf\it
q}_{i}(t)=(q_{i}^{x}(t),q_{i}^{y}(t),q_{i}^{z}(t))\in\mathbb{R}^{3}$ and
${\bf\it v}_{i}(t)=(v_{i}^{x}(t),v_{i}^{y}(t),v_{i}^{z}(t))\in\mathbb{R}^{3}$,
respectively, for all $i\in\bigcup_{k\in\mathcal{K}}\mathcal{I}_{k}$. Suppose
the number of SATs on each orbital plane is equal to each other given as
$|\mathcal{I}_{k}|=I$ for all $k\in\mathcal{K}$, and assume all SATs are
moving in uniform circular motion with the same orbital period $T$, while the
arc length between any two neighboring SATs on the same orbital plane is equal
to each other.

Consider that time is discretized in slots of length $\tau$ and let ${\bf\it
q}_{i}[0]$ be the initial position of the SAT
$i\in\bigcup_{k\in\mathcal{K}}\mathcal{I}_{k}$ at time $t=0$. Then, by
following the discrete-time state-space model [28, 19], the position of SAT
$i$ at time $t=m\tau$ can be expressed as

$\displaystyle{\bf\it q}_{i}(m\tau)\approx{\bf\it
q}_{i}(0)+\tau\sum_{m^{\prime}=1}^{m}{\bf\it v}_{i}(m^{\prime}\tau)+{\bf\it
n}_{i},$ (1)

where ${\bf\it n}_{i}$ is the additive random noise representing the
perturbation on the $i$-th satellite position and attitude determination error
[29], whose entries are independent and identically distributed zero-mean
Gaussian random variables with $\mathbb{E}[{\bf\it n}_{i}{\bf\it
n}_{i}^{{\dagger}}]=\sigma_{i}^{2}\mathbf{I}_{3}$.

Communication channels between SATs and UTs follow the characteristics of
ground-to-space (or space-to-ground) RF link [30]. The channel gain between
satellite $i\in\bigcup_{k\in\mathcal{K}}\mathcal{I}_{k}$ and UT
$j\in\mathcal{J}$ at time $t$ is expressed as

$h_{i,j}(t)=\tilde{h}_{i,j}(t)\sqrt{\gamma_{i,j}(t)},$ (2)

where $\gamma_{i,j}(t)$ and $\tilde{h}_{i,j}(t)$ are the effects of large-
scale (e.g., path loss and shadowing) and small-scale fading at time $t$,
respectively, and $\mathbb{E}[|\tilde{h}_{i,j}(t)|^{2}]=1$ for all $t\geq 0$.

The large-scale fading is modeled based on the tractable line-of-sight (LoS)
probability model [30, 31] with shadowing and blockage effects. Note that in
the LoS probability model, the large-scale fading follows generalized
Bernoulli distribution of two different events; the channel is LoS or non-LoS
(NLoS) with a certain probability. The probability of event that a channel
between SAT $i$ and UT $j$ at time $t$ being LoS is modeled as

$\displaystyle\varphi^{\text{LoS}}_{i,j}(t)=\frac{1}{1+L_{1}\mathrm{exp}[-L_{2}(\theta_{i,j}(t)-L_{1})]},$
(3)

where $L_{1}$ and $L_{2}$ are the environmental parameters depending on the
propagation condition [32] and

$\displaystyle\theta_{i,j}(t)=\frac{180}{\pi}\mathrm{sin}^{-1}\\!\left(\frac{q_{i}^{z}(t)-q_{j}^{z}}{||{\bf\it
q}_{i}(t)-{\bf\it q}_{j}||_{2}}\\!\right)$ (4)

is the angle of SAT $i$ and UT $j$ referred to as an elevation angle.

Meanwhile, depending on whether the channel is LoS or NLoS, different large-
scale fading $\gamma_{i,j}(t)$ can be expressed as

$\gamma_{i,j}(t)=\begin{cases}\beta_{o}||{\bf\it q}_{i}(t)-{\bf\it
q}_{j}||_{2}^{-\alpha},&\text{for LoS channel},\\\ \kappa\beta_{o}||{\bf\it
q}_{i}(t)-{\bf\it q}_{j}||_{2}^{-\alpha},&\text{for NLoS channel},\\\
\end{cases}$ (5)

where $\beta_{o}$ is the average power gain at the reference distance
$d_{o}=1$ [m], $\alpha$ is the path loss exponent and $\kappa$ is the
attenuation scaling factor in the NLoS link [31]. Note that
$\tilde{h}_{i_{k},j}$ has its randomness from both random occurrence of LoS
and NLoS as well as the small-scale fading. Accordingly, the expected channel
gain over both randomness is given by

$\mathbb{E}\\!\left[|h_{i,j}(t)|^{2}\\!\right]=\tilde{\varphi}^{\text{LoS}}_{i,j}(t)\beta_{o}||{\bf\it
q}_{i}(t)-{\bf\it q}_{j}||_{2}^{-\alpha},$ (6)

where
$\tilde{\varphi}^{\text{LoS}}_{i,j}(t)=\varphi^{\text{LoS}}_{i,j}(t)+\kappa(1-\varphi^{\text{LoS}}_{i,j}(t))$.

Figure 2: Time and frequency resource structure of the considering random
access scenario.

###  III-B LEO SAT Random Access Scenario

Consider an LEO satellite random access (RA) scenario, where UTs attempt to
access to LEO satellite networks for radio resource grant. Suppose that UTs
always have data to transmit in their infinite length queue, and thus, they
always have intentions to RA at every opportunity they have. Each UT has
information of the periodic position of SATs on each orbital plane and
attempts to access only to the closest SAT on each orbital plane. For the sake
of convenience, we assume that the closest SAT on each orbital plane is the
same for every UT at the same time point. According to the network model, note
that the time duration that one SAT becomes the closest among all SAT on each
orbital plane is $\frac{T}{I}$, where $T$ is the orbiting period and $I$ is
the number of SATs on each orbital plane. Suppose that there are $N$ RA
opportunities during the interval $\frac{T}{I}$ and they are synchronized over
all orbital planes as shown in Fig. 2. The time duration of each RA
opportunity is $\frac{T}{IN}$, which incorporates RA signaling duration
$\tau_{s}$ and data transmission duration $\tau_{d}$, i.e.,
$\tau_{s}+\tau_{d}=\frac{T}{IN}$, for some $\tau_{s}$ and $\tau_{d}$ such that
${\tau_{s}}/{\tau},{\tau_{d}}/{\tau}\in\mathbb{Z}^{+}$. For simple
description, we focus only on $N$ RA opportunities in the rest of this section
and suppose the first opportunity starts at $t=0$. Here, the time duration of
each $n$-th RA opportunity is discretized with $\tau$, i.e., $t=n\tau,\forall
n\in\\{1,2,\dots,N\\}$.

At each RA opportunity, each UT chooses whether to access or backoff, and then
further decide the SAT to which it will access. Such set of actions is simply
denoted by $\\{\texttt{BACKOFF},1,\ldots,K\\}$ in which $K:=|\mathcal{K}|$ is
the number of orbital planes. The RA action of UT $j\in\mathcal{J}$ at RA
opportunity $n$ is denoted by

$a_{j}[n]\in\\{\texttt{BACKOFF},1,\ldots,K\\}.$ (7)

Note that $a_{j}[n]=\texttt{BACKOFF}$ means that the UT $j$ does not access at
the $n$-th opportunity and waits for the next one. Moreover, those who attempt
to access additionally choose a preamble uniform-randomly, that is

$p_{j}[n]\in\\{1,2,\dots,P\\}.$ (8)

Here, each preamble is associated with $P$ resources that the SATs can grant
during the data transmission duration.

The RA signaling is done in two steps. First, those UTs that determine to
access send preambles to the corresponding SATs. Secondly, SATs send feedback
to confirm whether there were collisions or not for each chosen preamble. UTs
that have chosen collided preambles fail to access, while those of UTs that
have chosen preambles without collision succeed to access.

###  III-C Collision Rate, Access Delay, and Network Throughput

The performance of RA in LEO SAT network is evaluated with collision rate,
access delay and average network throughput, as explained in the following.

####  III-C1 Collision Rate

Denote the collision indicator of UT $j\in\mathcal{J}$’s RA at opportunity
$n\in\\{1,\dots,N\\}$ by $c_{j}[n]$, and define it as

$\displaystyle
c_{j}[n]\\!=\\!\begin{cases}0,&(a_{j}[n],p_{j}[n])\\!\neq\\!(a_{j^{{}^{\prime}}}[n],p_{j^{\prime}}[n])\
\forall j^{\prime}\\!\in\\!\mathcal{J}\backslash j\\\
1,&\text{otherwise},\end{cases}$ (9)

if $a_{j}[n]\neq\texttt{BACKOFF}$, and otherwise we have $c_{j}[n]=0$. Then,
the _collision rate_ is defined as:

$\displaystyle
C=\frac{1}{|\mathcal{J}|}\sum_{n=1}^{N}\sum_{j\in\mathcal{J}}{c_{j}[n]}.$ (10)

####  III-C2 Access Delay

Define the access indicator of UT $j\in\mathcal{J}$’s RA at opportunity
$n\in\\{1,\dots,N\\}$ as

$\displaystyle\eta_{j}[n]=\begin{cases}(1-c_{j}[n]),&a_{j}[n]\neq\texttt{BACKOFF}\\\
0,&a_{j}[n]=\texttt{BACKOFF}\end{cases}.$ (11)

Let $N_{s}$ be the number of successful accesses of all UTs out of $N$ access
attempts, which is given as

$\displaystyle
N_{a}=\frac{1}{|\mathcal{J}|}\sum_{n=1}^{N}\sum_{j\in\mathcal{J}}\eta_{j}[n].$
(12)

Then, the _average access delay_ is given as:

$\displaystyle D=\frac{(N_{a}-N)(m_{s}+m_{d})\tau}{N_{a}}+m_{s}\tau.$ (13)

####  III-C3 Network Throughput

According to the defined channel model, the uplink (UL) throughput from UT
$j\in\mathcal{J}$ to SAT $i\in\bigcup_{k\in\mathcal{K}}\mathcal{I}_{k}$ can be
expressed as

$\displaystyle
R_{i,j}(t)=B\log_{2}\left(1+\frac{\Gamma\left|h_{i,j}(t)\right|^{2}}{\sigma_{n}^{2}}\right)\mathrm{[bps]},$
(14)

where $B$ represent the bandwidth, $\sigma_{n}^{2}$ is the noise variance, and
$\Gamma$ is the UL transmission power.

Note that UT can transmit data only when its access is successful. Thus, when
$a_{j}[n]\neq\texttt{BACKOFF}$, the attainable throughput at UT
$j\in\mathcal{J}$ in the $n$-th RA opportunity can be expressed as

$\displaystyle
R_{j}[n]=\eta_{j}[n]\tau_{d}\sum_{t=(n-1)(\tau_{s}+\tau_{d})+\tau_{d}}^{n(\tau_{s}+\tau_{d})}R_{i_{a_{j}[n]},j}(t),$
(15)

where $i_{k}\in\mathcal{I}_{k}$ denotes the most closest SAT from UT $j$ among
all SATs on the orbital plane $k\in\mathcal{K}$. Otherwise if
$a_{j}[n]=\texttt{BACKOFF}$, $R_{j}[n]=0$. Consequently, the time-average
network throughput $R$ within $N$ RA opportunities can be given as

$\displaystyle R=\frac{1}{N}\sum_{n=1}^{N}\sum_{j\in\mathcal{J}}R_{j}[n].$
(16)

In what follows, under the LEO SAT RA scenario and with the performance
metrics including collision rate, access delay, and network throughput, we
propose an emergent RA protocol for LEO SAT networks.

##  IV Emergent Random Access Protocol for
LEO Satellite Networks

This section introduces the emergent contention-based RA protocol for LEO SAT
networks. Moreover, we explain step-by-step how the protocol is specifically
designed.

###  IV-A Emergent RA Protocol for LEO SAT

We propose a novel RA solution for LEO SAT networks, coined _emergent random
access channel protocol (eRACH)_. As illustrated in Fig. 1, the UT on the
ground attempts to access an SAT by the contention-based RA and then transmits
a data frame only when it successfully accesses to intended LEO SAT. To
specifically discuss and evaluate our proposed eRACH protocol, the following
optimization problem is mathematically formulated. This problem aims to
maximize the throughput while minimizing the collision rate under the
constraints related to the practical conditions of LEO SAT networks:

$\displaystyle\displaystyle\max_{\scriptsize\begin{array}[]{c}\scriptsize
a_{j}[n]\end{array}}$ $\displaystyle\sum_{n=1}^{N}R_{j}[n]-\rho c_{j}[n],\
\forall j\in\mathcal{J},$ s.t. $\displaystyle\eqref{C_LEO_q},\
\eqref{Collision},$

where $\rho$ denotes a normalization coefficient, which strikes a balance
between throughput and collision rate, and $N$ represents one orbital cycle of
SAT. Here, the constraint in (1) represents the orbital motion of the LEO SAT
constellation. Besides, the constraint in (9) represents the collision in LEO
SAT. Recall that the collision occurs for UT agents that attempt to access the
same LEO SAT $i_{k}$ with the same preamble signature, at the same time slot.

In a nutshell, eRACH considers the following steps:

  1. 1.

Association decision for SAT-UT,

  2. 2.

Backoff decision,

  3. 3.

RACH access (PRACH preamble $p$ is chosen uniform-randomly), and

  4. 4.

UL data transmission (only when accessed successfully),

during which, eRACH determines 1) and 2), while the rest are automatically
determined according to the established protocol as described in Sec. III-B.
As 3) and 4) follow the standard operations, the problem of interest focuses
on the joint decision on 1) and 2). However, to optimize 1) and 2) for (IV-A),
traditional convex optimization methods (e.g., SCA [33], BCD [34]) face
several challenges mainly due to time-varying LEO SAT networks.

To this end, we utilize MADRL algorithm in the eRACH protocol. While training
the MADRL, we only use locally observable information of UT in the LEO SAT
networks. Further, considering the specificity of the LEO SAT networks, we
carefully pick out a piece of essential by extensively testing candidates
among locally observable information to minimize the complexity while
retaining near-optimality. For applying the MADRL method, first and foremost,
it is necessary to design Markov decision process (MDP) model, which includes
a state, action, and reward function in an environment that reflects our
network scenario, which is discussed next.

###  IV-B MADRL Formulation for Emergent RA Protocol

In what follows, we first reformulate the problem (IV-A) of eRACH using an MDP
model, and then describe how to solve this problem via MADRL.

####  IV-B1 MDP Modeling

To recast (IV-A) as an MADRL problem, we model the SAT network scenario using
an MDP, a discrete-time stochastic control process that mathematically
characterizes decision-making in a random environment. In the MDP model, for a
given state, a policy $\pi$ refers to the probability of choosing an action,
and $\pi^{*}$ is the optimal policy maximizing the long-term average reward,
which is the goal of MADRL.

Figure 3: An illustration of the proposed eRACH training process based on
multi-agent Actor-Critic method.

Environment. As illustrated in Fig. 3, the MADRL framework under study
consists of multiple UTs interacting with an environment that follows an MDP
model. At each time $t$, each UT $j$ is an agent observing a state
$\mathbf{s}_{j}[n]\in\mathcal{S}$, and takes an action
$\mathbf{a}_{j}[n]\in\mathcal{A}$ based on a state-action policy $\pi$. Given
this action, the state of the agent $j$ transitions from $\mathbf{s}_{j}[n]$
to $\mathbf{s}_{j}[n+1]$, and in return receives a reward $r_{j}[n]$ that
reinforces the agent follows an optimal policy $\pi^{*}$. How to define these
states, actions, and rewards significantly affects the performance,
communication, and computing costs of eRACH as we shall elaborate next.

Figure 4: Comparison of cumulative rewards with different information included
in the state $s_{j}[n]$.

State. In the aforementioned MDP model, we consider the following state of UT
$j$:

$\displaystyle{\bf\it s}_{j}[n]$ $\displaystyle=\\{n,{\bf\it
q}_{i_{1}}[n],\dots,{\bf\it
q}_{i_{K}}[n],R_{j}[n],c_{j}[n],a_{j}[n\\!-\\!1]\\},$ (19)

where ${\bf\it q}_{i_{k}}[n]\in\mathbb{R}^{I\times
3},i\in\mathcal{I},k\in\mathcal{K}$ denotes the position of SAT $i$ in the
orbital plane $k$, $R_{j}[n]$ is the throughput, $c_{j}[n]$ is a binary
indicator function of an RA collision event, and $a_{j}[0]$ and ${\bf\it
s}_{j}[1]$ are initial values chosen randomly at the beginning of Algorithm 1.
Here, the previous action $a_{j}[n-1]$ and current time slot $n$ are used as a
_fingerprint_ , adopting the fingerprint-based method proposed in [35] to
stabilize experience replay in the MADRL. Note that the non-stationarity of
the multi-agent environment is dealt with by the fingerprinting that
disambiguates the age of training samples and stabilizes the replay memory.

The state of an agent should contain sufficient information for carrying out
decision-making. Meanwhile such information should be minimal to reduce any
additional data collection overhead from the environment or other agents and
to promote MADRL training convergence. To screen for important information to
be included in the state among locally observable information, we extensively
test possible local information candidates and their impacts on eRACH
performance. In this regard, we provide an ablation study of Fig. 4 which
presents the contribution of each information to the overall system. Each
information in $s_{j}[n]$ has a different importance. As shown in this figure,
eRACH mainly exploits the following information: 1) the expected SAT locations
that are known a priori owing to the pre-determined LEO SAT orbiting pattern;
and 2) the collision that are inherently observable. Such two locally
observable information significantly contributes to the training of eRACH,
which highlights eRACH does not even require cheap talks between agents.

While training eRACH, we validate that the expected SAT location contains
sufficient information on the network topology, as long as the variance
between the expected and actual SAT position is less than $1$ [km] as shown in
Fig. 5. Moreover, it is confirmed that the collision event incorporates
sufficient information on the local environment, e.g., how crowded the network
is, as will be elaborated in Sec V. As the LEO SAT periodically orbits a pre-
designed trajectory, MADRL frequently revisits the same environment of SAT-UT
RA, which facilitates the discovery of emergency protocols that perform SAT-UT
connections and RA decisions without communication overhead between agents.

Figure 5: Robustness to SAT BS positioning errors, where shaded regions
identifies the three different regimes: (a) same reward and convergence speed,
(b) same reward, slower convergence, and (c) lower reward, slower convergence.
Specific reward values and convergence times are reported in Table IV.

Action. The action space $\mathcal{A}$ in our environment is related to RA.
Among SATs $i_{k}$ in orbital plane $k$, the agent UT $j$ chooses one SAT to
access by using the access action $a_{j}[n]$ in (7). For the set of access
action, $\mathcal{A}$, we define an one-hot encoded action as follows

$\mathbf{a}_{j}[n]=\\{a_{0},a_{1},a_{2},\cdots,a_{K}\\},\
\mathrm{s.t.}\sum_{\ell=0}^{K}a_{\ell}=1,$ (20)

where $a_{\ell}$ for $\ell\neq 0$ denotes the association with the $\ell$-th
orbital plane, and $a_{0}$ implies backoff. Note that it is assumed that the
UT attempts to access the nearest SAT among SATs $\mathcal{I}_{k}$ in orbital
plane $k$.

Reward. Our reward function is supposed to reinforce UTs to carry out optimal
access actions that maximize the network throughput while penalizing access
collision. The objective function (IV-A) captures this goal, although it is
not suitable for the reward function. Indeed, if there is no collision, (IV-A)
gives positive throughput without penalty, and otherwise imposes only
collision penalty with zero throughput. This incurs too significant and
frequent reward variation, hindering the training convergence. To mitigate
this issue, following [25, 36], we normalize (IV-A), and consider the reward
function of UT $j$ as follows

$\displaystyle r_{j}[n]=g(R_{j}[n]-\rho c_{j}[n]).$ (21)

Note that the normalization function is given by $g(Y)=\frac{Y-\mu}{\Sigma}$,
where $\Sigma$ and $\mu$ are parameters for scale which shrinks the output
value $Y$ between $-1$ and $1$ and for mean value, respectively. Here, the
mean value corresponds with the network throughput of the RACH baseline in
Sec. V.

It is worth noting that the state and reward of each UT agent are all locally
observable information and thus the MDP model for RA protocol can be trained
and executed in a fully _distributed_ manner.

####  IV-B2 Actor-Critic MADRL

Following the standard RL settings, the aforementioned SAT-UT RA environment
is considered in which many agents interact for a given number of discrete
time steps. At each time step $n$, the agent $j$ receives a state
$\mathbf{s}_{j}[n]$ and selects an action $\mathbf{a}_{j}[n]$ from some set of
possible actions $\mathcal{A}$ according to its policy $\pi_{\theta_{j}}$,
where $\pi_{\theta_{j}}$ is a mapping from states $\mathbf{s}_{j}[n]$ to
actions $\mathbf{s}_{j}[n]$. In return, the agent receives the next state
$\mathbf{s}_{j}[n+1]$ and receives a scalar reward $r_{j}[n]$. The process
continues until the agent reaches a terminal state after which the process
restarts. The return
$\tilde{r}_{j}[n]=\sum\nolimits_{k=0}^{\infty}\gamma^{k}r_{j}[n+k]$ is the
total accumulated return from time step $n$ with discount factor
$\gamma\in(0,1]$.

For our multi-agent scenario, we employ an Actor-Critic RL framework [37],
which combines the benefits of both policy gradient and value-based methods.
The Actor-Critic framework comprises a pair of two NNs: an Actor NN seeks to
take actions to obtain higher rewards based on the policy gradient method; and
its paired Critic NN aims to approximate value functions more accurately via
the value-based method. In particular, each UT agent $j$ has an Actor NN and a
Critic NN and follows the synchronous advantage Actor-Critic operation [37,
24], in which the Critic NN updates its model parameters $\phi_{j}$ according
to the policy $\pi_{\theta_{j}}$ given by the Actor NN. Meanwhile, the Actor
NN updates its model parameters $\theta_{j}$ according to the value functions
$V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[n];\phi_{j})$ approximated by the Critic
NN. Specifically, the Critic NN aims to minimize the loss function

$\displaystyle L^{j}_{\mathrm{Critic}}(\phi_{j})=\kappa_{j}[n]^{2},$ (22)

where $\kappa\mathbf{s}_{j}[n]=r_{j}[n+1]+\gamma
V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[n+1];\phi_{j})-V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[n];\phi_{j})$
is referred to as the advantage of an action [38]. The Critic NN model
parameters are then updated as

$d\phi_{j}\leftarrow
d\phi_{j}+\beta_{c}(R-V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[n];\theta_{j}))\nabla_{\phi_{j}}V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[n];\phi_{j}),$
(23)

where $\beta_{c}$ is the hyperparameter of Critic NN, which is related to the
value estimate loss. Meanwhile, the Actor NN aims to minimize the loss
function

$L^{j}_{\mathrm{Actor}}(\theta_{j})=-\kappa_{j}[n]\log\pi(\mathbf{s}_{j}[n]|\mathbf{s}_{j}[n];\theta_{j}).$
(24)

Hereafter, the index $j$ identifies different actors for multi-agent
scenarios, which can be omitted for a single agent case. Consequently, the
Actor NN model parameters are updated as

$d\theta_{j}\leftarrow
d\theta_{j}+\nabla_{\theta_{j}}\log{\pi(\mathbf{s}_{j}[n]|\mathbf{s}_{j}[n];\theta_{j})(R-V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[n];\theta_{j}))}.$
(25)

where $H(\pi)$ is the entropy of the policy and $\beta_{e}$ is the
hyperparameter of controlling the relative contributions of the entropy
regularization term. The NN parameters are updated via gradient descent and
backpropagation through time, using Advantage Actor-Critic as detailed by
[24]. We summarize the eRACH training process for each UT agent $j$ in
Algorithm 1.

Algorithm 1 eRACH Training Algorithm

Initialize step counter $n\leftarrow 1$
Initialize episode counter $E\leftarrow 1$
repeat

Reset gradients: $d\theta_{j}\leftarrow 0$ and $d\phi_{j}\leftarrow 0$
$n_{\mathrm{start}}=n$
Get state $\mathbf{s}_{j}[n]$
repeat

Perform access action $\mathbf{s}_{j}[n]$ according to policy
$\pi(\mathbf{s}_{j}[n]|\mathbf{s}_{j}[n];\theta_{j})$
Receive reward $r_{j}[n]$ and new state $\mathbf{s}_{j}[n+1]$
$n\leftarrow n+1$

until  _$\mathrm{terminal}\ \mathbf{s}_{j}[n]$_ ;

$R=\begin{cases}0,&\text{for terminal}\ \mathbf{s}_{j}[n]\\\
V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[n];\theta_{j}),&\text{for non-terminal}\
\mathbf{s}_{j}[n]\end{cases}$
for  _$i\in\\{n-1,\dots,n_{\mathrm{start}}\\}$_ do

$R\leftarrow r_{j}[n]+\gamma R$
Accumulate gradients w.r.t. $\theta_{j}$:
$d\theta_{j}\leftarrow
d\theta_{j}+\nabla_{\theta_{j}}\log{\pi(\mathbf{a}_{j}[i]|\mathbf{s}_{j}[i];\theta_{j})(R-V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[i];\theta_{j}))}$
$+\beta_{e}\partial
H(\pi(\mathbf{a}_{j}[i]|\mathbf{s}_{j}[i];\theta_{j})/\partial\theta$
Accumulate gradients w.r.t. $\phi_{j}$:
$d\phi_{j}\leftarrow
d\phi_{j}+\beta_{c}(R-V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[i];\theta_{j}))\nabla_{\phi_{j}}V^{\pi_{\theta_{j}}}(\mathbf{s}_{j}[i];\phi_{j})$

end for

Perform update of $\theta_{j}$ using $d\theta_{j}$ and of $d\phi_{j}$ using
$\phi_{j}$
$E\leftarrow E+1$

until  _$E >E_{\mathrm{max}}$_;

##  V Numerical Evaluations

This section validates the proposed emergent RA methods of eRACH for LEO SAT
networks with respect to average throughout, collision rate, and delay.

###  V-A Simulation Settings

Table I: Simulation parameters. Parameter | Value
---|---
Altitude of SAT |  $H_{\mathrm{L}}=550$ [km] (from [3])
Velocity (Speed) of SAT1 ($k=1$) |  $\mathbf{v}^{1}_{\mathrm{L},\mathrm{I}}=[0,7590,0]^{T}$ ($7590$ [m/s])
Velocity of SAT2 ($k=2$) | $\mathbf{v}^{2}_{\mathrm{L},\mathrm{I}}=[0,-7590,0]^{T}$
Radius of an orbit |  $r_{\mathrm{E}}=6921$ [km]
Circumference of an orbital lane |  $c_{\mathrm{E}}=43486$ [km]
Number of SATs per orbital lane | $I=22$
Inter-SAT distance |  $1977$ [km]
Number of UT | $J=5$
Bandwidth |  $B=10^{8}$ [Hz]
Path loss exponent | $\tilde{\alpha}=2.1$
Parameter for LoS probability |  $L_{1}=10$, $L_{2}=0.6$
Attenuation factor | $\kappa=0.2$
Random access duration |  $\tau_{s}=10$ [ms]
Data transmission duration |  $\tau_{d}=90$ [ms]
Preamble signatures for each SAT | $P=2-54$
Orbital period |  $T=5728$ [s]
Number of time slots per episode | $N=2604$

Unless otherwise stated, UTs under study are located in the ground uniformly
at random within an area of $1000\times 1000$ [m2], while two orbital planes
$K=2$ circulate over UTs at the altitude of $550$ [km]. Each orbital lane
consists of $22$ SATs with the orbital lane circumference of $43486$ [km],
resulting in an inter-SAT distance of $1977$ [km]. Since the orbital lane
circumference is much larger than the area of interest, each orbital lane is
approximated as a line segment at the altitude of $550$ [km] [3], in which
$22$ SATs orbit with the orbital speed $7.59$ [km/s], are separated with the
inter-SAT distance $1977$ [km], and perturbed with $\sigma_{i}$. Here, the
orbital period and speed are calculated using the relations
$4\pi^{2}(r_{\mathrm{E}})^{3}=T^{2}GM$ and $V^{2}r_{\mathrm{E}}=GM$,
respectively, where $r_{\mathrm{E}}$ is the radius of orbit in metres; $T$,
the orbital period in seconds; $V$, the orbital speed in [m/s]; $G$, the
gravitational constant, approximately $6.673\times 10^{-11}$ [m3/kg1/s2]; $M$,
the mass of Earth, approximately $5.98\times 1024$ [kg].

Unless otherwise stated, the simulation environments and parameters are as
follows: each RA opportunity is opened in every $\tau=\tau_{s}+\tau_{d}=100$
[ms]; the RA signaling duration and data transmission duration are set as
$\tau_{s}=10$ [ms] and $\tau_{d}=90$ [ms], respectively; data transmission is
conducted for $\tau_{d}$ time only if the attempt of the access succeeds; the
objective function in our MDP model corresponds to the un-discounted
accumulated rewards with $\rho=1$ over an episode up to
$N=\frac{T}{I\tau}=2604$, which corresponds to the RA opportunity; and $J=5$
five UT agents are considered wherein two orbital planes $K=2$ circulate over
UTs with resources $P=2$, given the MADRL environment mentioned above.

Table II: Throughput, collision rate, and access latency of eRACH, compared with eRACH-Coop, RACH, and Slotted ALOHA.  RA Scheme | Avg. Thr. [Mbps] | Avg. Collision Rate | Avg. Access Delay [ms] | Jain’s Fairness [39] | Cheap Talk
---|---|---|---|---|---
Slotted ALOHA |  $12.249$ |  $0.9339$ |  $1441.1$ |  $0.8921$ | $\times$
RACH |  $47.679$ |  $0.1338$ |  $293.1$ |  $0.9917$ | $\times$
eRACH |  $62.347$ |  $0.6614$ |  $197.1$ |  $0.9887$ | $\times$
eRACH-Coop |  $73.716$ |  $0.4000$ |  $151.2$ |  $0.8000$ | $\circ$

Throughout this section, we consider two benchmark RA schemes and our proposed
eRACH with or without cooperation among agents as listed below.

  1. 1.

Slotted ALOHA is a traditional contention-based channel access protocol. UTs
agree upon the discrete slot boundaries. At the beginning of the access slot,
i.e., $\tau_{s}$, each UT uniform-randomly chooses the SAT to access. For each
SAT, if more than one UT attempts to access at the beginning of a slot,
collisions occur.

  2. 2.

RACH is another conventional contention-based channel access protocol used in
NR and LTE. RACH uniform-randomly selects a SAT to access and additionally
chooses the preamble $p_{j}[n]$ at the beginning of the access slot, i.e.,
$\tau_{s}$. When a collision occurs, UT waits for a uniformly distributed
backoff time and again repeats the process from the beginning. Here, the
backoff range follows a discrete uniform distribution as $\tau_{b}\sim
DU(1,W\tau)$, where $W$ is the backoff window size assumed fixed at $10$. As
in Release 16 of NR [40], we consider that RA signaling is done in two steps,
i.e., 2-step RACH.

  3. 3.

eRACH-Coop is another variant of our proposed RA scheme, in which each UT can
select an optimal action while cooperatively communicating with other UT
agents. Unlike _eRACH_ where each distributed UT agent uses partially
observable information, for _eRACH-Coop_ , cooperative UT agents use the full
observability through cheap-talk with other agents.

In particular, the cooperative UT agents use the network throughput as a
corresponding reward by the previous access action of each agent, and the
collision rate which involves all the collision information of each UT as
state. The reward and state for the cooperative agent $j$ is given by

$\displaystyle r^{\mathrm{C}}_{j}[n]$
$\displaystyle=g({\textstyle\sum}_{j\in\mathcal{J}}R[n]),$ (26)
$\displaystyle\mathbf{s}^{\mathrm{C}}_{j}[n]$
$\displaystyle=\\{\mathbf{s}_{j}[n],{\textstyle\sum}_{j\in\mathcal{J}}R_{j}[n],{\textstyle\sum}_{j\in\mathcal{J}}c_{j}[n]\\}.$
(27)

Here, this reward structure is used in the centralized training and
decentralized execution (CTDE). During the centralized training, the
centralized reward can be used to observe the throughput and the collision
event of other UT agents. Note that each agent has its own Actor-Critic
network and decide the optimal access action for itself via trained policy.
Here, cheap talk is necessary during both the training and exploitation
phases.

  4. 4.

eRACH is our proposed RA scheme with using Actor-Critic framework, wherein
each UT agent optimizes its access action in the environment in a fully
_distributed_ manner. Each UT has partial state observability. The agents
interact through the environment but do not communicate with other agents. The
learning can be cast as a partially observable MDP (POMDP).

It is worth noting that in eRACH-Coop, each UT utilizes information from other
UTs (see (26) and (27)) unlike the other baselines. Accordingly, eRACH-Coop
can achieve better performance by using additional information. Here, one can
regard its performance as an upper-bound result.

The following conditions are considered comparing the baselines: 1) all UTs
have enough data to be transmitted; 2) if collisions occur at a time slot for
an SAT, all attempted UTs fail to access at the time slot to the SAT; and 3)
the RA signaling is done in a two step procedure (see Sec. III-B).

Figure 6: The convergence of eRACH for each UT agent ($J=5$). Figure 7:
Network throughput for different RA schemes.

###  V-B Model Architecture and Training

For all Actor and Critic NNs, we identically consider a $4$-layer fully-
connected multi-layer perceptron (MLP) NN architecture. Each MLP has $2$
hidden layers, each of which has the $128\times 128$ dimension with the
rectified linear unit (ReLU) activation functions. Both Actor and Critic NNs
are trained using RMSprop with the learning rate $0.0001$, batch size $2604$,
$2604$ iterations per episode, training episodes $1000$, and $2604$ iterations
per update. The simulations are implemented using TensorFlow Version 2.3. Main
parameters on simulation settings are summarized in Table I.

Figs. 6 and 7 plot the convergence of eRACH. Firstly, in Fig. 6, it is
provided the training convergence behavior of Actor and Critic NNs for the
five UT agents, in which the solid curves denote cumulative reward for each UT
agent. The results show that each Actor and Critic NN for $J=5$ converge
within about $500$ episodes. Besides, Fig. 7 compares eRACH and eRACH-Coop
with conventional RACH and slotted ALOHA over the number of training episodes,
in which shaded areas correspond to the maximum deviations during $5$
simulation runs. Note that our cumulative reward corresponds to the average
network throughput, such that we can validate the convergence of the proposed
Actor-Critic MADRL-based method in Algorithm 1 with this figure.

As identified in this figure, eRACH and eRACH-Coop converge and outperform the
conventional RACH scheme only within around $200$ training episodes. It
suggests that the observed data during only one day is enough to train the
eRACH UT agent.

Table III: Top-view snapshots of SAT BS associations and preamble resource utilization (Resource Util.) under eRACH and RACH for $4$ consecutive time slots, where associated and backed-off UTs are drawn with or without solid lines, respectively ($K=2$, $I=22$, $J=5$, $P=2$). For the same period, the RA snapshots are illustrated in Fig. 8.  |  Time Slot = 1 |  Time Slot = 2 |  Time Slot = 3 |  Time Slot = 4
---|---|---|---|---
RACH |  |  |  |
Resource Util. |  67%  |  27%  |  42%  |  24%
|  0 %100 % |  0 %100 % |  0 %100 % |  0 %100 %
eRACH |  |  |  |
Resource Util. |  77%  |  99%  |  79%  |  97%
|  0 %100 % |  0 %100 % |  0 %100 % |  0 %100 %

(a) RACH.  (b) eRACH.  (c) eRACH-Coop.

Figure 8: RA snapshots under eRACH, eRACH-Coop, and RACH for $10$ consecutive
time slots, where $\\{\textsf{SAT1},\textsf{SAT2}\\}$ identifies SAT BS
associations, and the red color of each box indicates the collision rate (the
darker, the higher). For the first $4$ consecutive time slots in (a) and (b),
the SAT BS association snapshots are illustrated in Fig. III ($K=2$, $I=22$,
$J=5$, $P=2$).

###  V-C RA Performance Analysis

Fig. 7 and Table II compare eRACH with other baselines, in terms of network
throughput, collision rate, and access delay. The results validate that eRACH
achieves higher average network throughput with lower average access delay
than the baselines. In particular, compared to RACH, eRACH and eRACH-Coop
achieve 31.18 % and 54.61 % higher average network throughput, which is
equivalent to 5.08x and 6.02x higher average network throughput of slotted
ALOHA, respectively. Moreover, the results show that eRACH achieves 1.49x and
7.31x lower average access latency compared to RACH and slotted ALOHA,
respectively.

Next, in terms of RA collision, the average collision rate of eRACH is 1.41x
lower than slotted ALOHA, yet is 4.94x higher than RACH. As opposed to other
model-based protocols, eRACH is willing to risk collisions for yielding higher
throughput and lower access latency in a given network and channel
environment. This fact suggests that eRACH optimizes access flexibly according
to the importance of throughput-collision in the LEO SAT network. Such
flexibility is advantageous to best-effort services such as enhanced mobile
broadband (eMBB) applications, but becomes a downside for mission-critical
applications such as ultra-reliable and low-latency communication (URLLC). For
the latter case, investigating the emergent protocols that strictly abide by a
collision constraint are interesting and deferred to future work.

Lastly, comparing the performance between eRACH and eRACH-Coop in Table II, we
conclude that eRACH is a fairer protocol that achieves 1.24x higher Jain’s
fairness than that of eRACH-Coop. The rationale is because the fully
distributed operations of eRACH inherently hide the information that may
promote selfish actions. Meanwhile, there is also a room to improve the
fairness of eRACH-Coop by applying a fairness-aware reward function during
training and/or learning fairness-aware representations for cheap talk
communication, which could be an interesting direction for future research.

###  V-D SAT Association and RA Operations

As shown in Table III, eRACH efficiently utilizes resources by optimizing the
association of SAT-UT while considering the non-stationary LEO SAT network.
Besides, as shown in Fig. 8, eRACH backs off flexibly thereby avoiding the
collision under consideration of the given local environment, whereas when
collision occurs, RACH backs off more than necessary due to a randomly
selected backoff window.

In particular, eRACH-Coop in Fig. 8c shows that a certain UT agent
continuously backs off. Here, since the cooperative UT agents consider the
network throughput rather than the throughput of itself in the reward
function, the sacrifice by this certain agent is reasonable. In contrast, for
eRACH in Fig. 8b, each agent takes turns and decides to backoff. The
distributed UT agents also learn how to sacrifice for the entire network even
without exchanging information between agents. It suggests that the
distributed eRACH protocol is able to emerge from a given local environment
during the training process.

We, however, are aware of a few limitations of eRACH and eRACH-Coop, which are
marked by a dotted purple line in Figs. 8b and 8c. In eRACH and eRACH-Coop,
there are unnecessary backoff decisions that seem to be throughput-wise
inefficient. It underlines that 1) DRL-based method occasionally decides a
poor action, especially when dealing with time-series data, like our
environment, and 2) the fairness issue can arise in Cooperative, during the
certain agent sacrifice for the sake of the entire network.

Despite the few limitations, we observe from such comparison results that
eRACH can emerge from a local environment with the following remarkable
features: 1) eRACH flexibly avoids unnecessary backoff with an understanding
of the given network conditions, and 2) eRACH access the optimal LEO SAT
considering the periodicity of the LEO SAT constellation.

###  V-E Ablation Study of Key Hyper Parameters

Figure 9: Impact of SAT location precision on average network throughput
($\sigma^{2}=100$).

Impact of SAT Location Precision. While training eRACH, the information of SAT
location affects dominantly the reward and convergence, as explained in Fig. 4
of Sec. IV-B. However, it is challenging to find the SAT location precisely.
In this regard, to examine whether easy-to-acquire prior information can be
used instead of actual observed information, we present Fig. 9 and Table IV.

Table IV: Impact of SAT location precision on normalized reward and the number
episodes until convergence. This table is also visualized in Fig. 5.

Position. Err. | Norm. Reward | # of Ep. for Convergence
---|---|---
$\sigma^{2}\simeq 0$ |  $0$ |  $\simeq 200$
$\sigma^{2}<10^{2}$ |  $0$ |  $<300$
$10^{2}\\!<\sigma^{2}\\!<10^{3}$ |  $<\\!-5$ |  $<700$
$10^{3}\\!<\sigma^{2}\\!<10^{4}$ |  $<\\!-45$ |  $<2000$
$\sigma^{2}>10^{4}$ | Diverge  | Diverge
|  $-50$$-25$$0$ |  $200$$1000$$2000$$\infty$

Specifically, various physical forces perturb SAT, e.g., Earth oblateness,
solar and lunar gravitational effects, and gravitational resonance effects
[29]. In actual SAT communication systems, various methods are used to track
the location of perturbed SAT, such as pointing, acquisition, and tracking
(PAT) mechanism [41] and global navigation satellite system (GNSS). Even with
the tracking and navigation systems, some orbital positioning error of LEO SAT
is inevitable. In this regard, we demonstrate the validity of the LEO SAT
periodic location information, which is prior knowledge, in eRACH in Fig. 9
and Table IV.

As shown in Fig. 9, eRACH trained with the periodic LEO SAT position
information converges within around $600$ episodes. It closely approaches the
one trained with actual LEO SAT position information. However, the periodic
SAT position is not always effective for training eRACH, as shown in Table IV.
The number of episodes for convergence, which corresponds to the training
time, increases as the positional error goes. Besides, the overall reward
decreases as the positional error goes. Nevertheless, information of periodic
SAT position can still be used effectively for eRACH until the divergence
point at around $\sigma^{2}=10^{4}$. These results suggest that eRACH can be
sufficiently trained with only prior information, and this emphasize that
eRACH can be trained by not only online RL but also offline RL [42].

(a) Sparse Case, $d_{j,j^{\prime}}=1000$.

(b) Dense Case, $d_{j,j^{\prime}}=10$.

Figure 10: Impact of UT distribution on access action policy of eRACH. Here,
$d_{j,j^{\prime}}$ represents the average distance between UTs in [m].

Impact of UT Distribution. The performance of the access protocol depends not
only on the available resources and the number of UTs which attempt to access
but also on the deployment scenario, e.g., sparse and dense networks. In this
regard, we present Fig. 10 to demonstrate the impact of UT distribution on
eRACH.

In the sparse networks, each UT experiences different channel conditions for
SAT; thus, each UT has a particular advantageous SAT to connect to. Here,
eRACH mainly focuses on designing the optimal association with SAT rather than
backoff action. Whilst, in the dense networks, the channel difference between
each UT is not noticeable since the distance between UTs is relatively close
compared to the distance between SAT and UTs.

For the sparse case of Fig. 10a, eRACH does not backoff during the entire time
slot. In contrast, in the dense case of Fig. 10b, eRACH backoff up to about
$30$ % of the total time slot and focuses on backoff action rather than
optimal association. Notably, eRACH in both cases achieves similar performance
even though they chose different aspects of access action. This fact further
corroborates that eRACH, which flexibly decides the access action, can emerge
from a given local network scenario without communication between agents.

(a) Rate-Max ($\rho=0$).

(b) Collision-Aware ($\rho=2$).

Figure 11: Impact of the collision aversion factor $\rho$ on access action
policy of eRACH.

Impact of the Collision Aversion Factor $\rho$. In the LEO SAT network, which
suffers from a long one-way propagation delay, the contention resolution is
challenging, as discussed in Sec. II. Hence, consideration for collision can
be another significant issue. Regarding this, we further present the numerical
results of the collision aversion case.

To clearly see the collision aversion case, we additionally present Rate Max,
which only considers the throughput while training of eRACH by setting
$\rho=0$. Here, the reward function in (21) is rewritten for Rate Max case as
follows.

$\displaystyle r_{j}[n]=g(R_{j}[n]),\ \forall j,n.$ (28)

As shown in Table V and Figs. 11 and 12, the eRACH agent learns mainly
maximizing throughput or mainly minimizing collision, depending on the
collision aversion factor $\rho$. Those results verify that eRACH method can
be flexibly applied to various applications.

Table V:  Impact of $\rho$ on average network throughput and average collision
rate of eRACH ($K=2$, $I=22$, $J=5$, $P=2$).

Objective | Avg. Thr. [Mbps] | Avg. Collision Rate
---|---|---
Rate-Max ($\rho=0$) |  $66.391$ |  $0.6713$
Collision-Aware ($\rho=2$) |  $54.285$ |  $0.4020$

Figure 12: Comparison of eRACH over the collision aversion factor $\rho$.

##  VI Conclusion

In this article, we proposed a novel RA for LEO SAT networks. To cope with the
challenges incurred by its wide coverage and time-varying network topology, we
proposed a model-free RA protocol that emerges from the given LEO SAT network
environment via MADRL, dubbed eRACH. By simulations, we validated that eRACH
better reflects the time-varying network topology than model-based ALOHA and
RACH baselines, thereby achieving higher average network throughput with lower
collision rates. Furthermore, eRACH is robust to SAT BS positioning errors,
enabling its operations with known periodic patterns of SAT BS locations.
Lastly, eRACH can flexibly adjust and optimize throughput-collision objectives
in various user population scenarios. Extending the current throughput and
collision objectives, considering a fairness-aware objective could be an
interesting topic for future research. It is also worth investigating highly
scalable MADRL frameworks to address complicated scenarios with more orbital
lanes and users at different altitudes, such as high altitude platform systems
(HAPS) and other GEO and MEO SATs.

## References

  * [1] N. Saeed, A. Elzanaty, H. Almorad, H. Dahrouj, T. Y. Al-Naffouri, and M.-S. Alouini, “CubeSat communications: Recent advances and future challenges,” _IEEE Commun. Surveys Tuts._ , vol. 22, no. 3, pp. 1839–1862, 2020.
  * [2] M. Handley, “Delay is not an option: Low latency routing in space,” in _Proc. ACM Workshop on Hot Topics in Networks_ , 2018, pp. 85–91.
  * [3] Starlink, Accessed: Sep- 2021. [Online]. Available: https://www.starlink.com/
  * [4] N. Pachler, I. del Portillo, E. F. Crawley, and B. G. Cameron, “An updated comparison of four low earth orbit satellite constellation systems to provide global broadband,” in _Proc. IEEE International Conf. on Commun. Workshops (ICC Wkshps)_ , 2021, pp. 1–7.
  * [5] Federal Communication Commission (FCC). (2020, Jul.) FCC authorizes kuiper satellite constellation. [Online]. Available: https://www.fcc.gov/document/fcc-authorizes-kuiper-satellite-constellation
  * [6] O. Kodheli, E. Lagunas, N. Maturo, S. K. Sharma, B. Shankar, J. F. M. Montoya, J. C. M. Duncan, D. Spano, S. Chatzinotas, S. Kisseleff, J. Querol, L. Lei, T. X. Vu, and G. Goussetis, “Satellite communications in the new space era: A survey and future challenges,” _IEEE Commun. Surveys Tuts._ , vol. 23, no. 1, pp. 70–109, 2021.
  * [7] M. Giordani and M. Zorzi, “Non-Terrestrial networks in the 6G era: Challenges and opportunities,” _IEEE Network_ , vol. 35, no. 2, pp. 244–251, 2021.
  * [8] M. Mozaffari, W. Saad, M. Bennis, Y. Nam, and M. Debbah, “A tutorial on UAVs for wireless networks: Applications, challenges and open problems,” _IEEE Commun. Surveys Tuts._ , vol. 21, no. 3, pp. 2334–2360, Mar. 2019.
  * [9] Y. Zeng, R. Zhang, and T. J. Lim, “Wireless communications with unmanned aerial vehicles: Opportunities and challenges,” _IEEE Commun. Mag._ , vol. 54, no. 5, pp. 36–42, May. 2016.
  * [10] E. Yaacoub and M. Alouini, “A key 6G challenge and Opportunity—Connecting the base of the pyramid: A survey on rural connectivity,” _Proceedings of the IEEE_ , vol. 108, no. 4, pp. 533–582, Apr. 2020.
  * [11] N. Saeed, H. Almorad, H. Dahrouj, T. Y. Al-Naffouri, J. S. Shamma, and M.-S. Alouini, “Point-to-Point communication in integrated Satellite-Aerial 6G networks: State-of-the-Art and future challenges,” _IEEE Open J. Commun. Soc._ , vol. 2, pp. 1505–1525, 2021.
  * [12] J. Foerster, Y. Assael, N. de Freitas, and S. Whiteson, “Learning to communicate with deep multi-agent reinforcement learning,” in _Proc. of International Conf. on Neural Information Processing (NIPS)_ , 2016, pp. 2145–2153.
  * [13] A. Valcarce and J. Hoydis, “Towards joint learning of optimal MAC signaling and wireless channel access,” _arXiv: 2007.09948 [cs.IT]_ , 2021.
  * [14] M. P. Mota, A. Valcarce, J.-M. Gorce, and J. Hoydis, “The emergence of wireless MAC protocols with Multi-Agent reinforcement learning,” _arXiv: 2108.07144 [cs.IT]_ , 2021.
  * [15] R. De Gaudenzi and O. del Rio Herrero, “Advances in random access protocols for satellite networks,” in _International Workshop on Satellite and Space Communications_ , 2009, pp. 331–336.
  * [16] G. Choudhury and S. Rappaport, “Diversity ALOHA - a random access scheme for satellite communications,” _IEEE Trans. Wireless Commun._ , vol. 31, no. 3, pp. 450–457, 1983.
  * [17] E. Casini, R. De Gaudenzi, and O. Del Rio Herrero, “Contention resolution diversity slotted aloha (CRDSA): An enhanced random access scheme for satellite access packet networks,” _IEEE Trans. Wireless Commun._ , vol. 6, no. 4, pp. 1408–1419, 2007.
  * [18] 3GPP TR38.811 v15.4.0, “Study on new radio (NR) to support non-terrestrial networks,” Oct. 2020.
  * [19] J.-H. Lee, J. Park, M. Bennis, and Y.-C. Ko, “Integrating LEO satellite and UAV relaying via reinforcement learning for Non-Terrestrial networks,” in _Proc. IEEE Global Commun. Conf. (GLOBECOM)_ , Taipei, Taiwan, 2020, pp. 1–6.
  * [20] 3GPP TS 38.321 v16.5.0, “NR; medium access control (MAC) protocol specification,” Jul. 2021.
  * [21] H. Seo, J.-P. Hong, and W. Choi, “Low latency random access for sporadic MTC devices in internet of things,” _IEEE Internet of Things J._ , vol. 6, no. 3, pp. 5108–5118, 2019.
  * [22] 3GPP TS 38.211 v15.9.0, “NR; physical channels and modulation,” Jun. 2021\.
  * [23] 3GPP TS 38.213 v15.14.0, “NR; physical layer procedures for control,” Jun. 2021.
  * [24] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu, “Asynchronous methods for deep reinforcement learning,” in _Proc. of International Conf. on Machine Learning (ICML)_ , vol. 48, New York, New York, USA, 20–22 Jun 2016, pp. 1928–1937.
  * [25] V. Mnih, K. Kavukcuoglu, D. Silver, and et al., “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, pp. 529–533, 2015.
  * [26] D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller, “Deterministic policy gradient algorithms,” ser. Proc. of International Conf. on Machine Learning (ICML), 2014, p. 387–395.
  * [27] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson, “Counterfactual Multi-Agent policy gradients,” in _AAAI Conf. on Artificial Intelligence_ , 2018.
  * [28] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory optimization,” _IEEE Trans. Wireless Commun._ , vol. 16, no. 6, pp. 3747–3760, Jun. 2017.
  * [29] H. Yoon, _Pointing system performance analysis for optical inter-satellite communication on CubeSats_. Massachusetts Institute of Technology (MIT), 2017.
  * [30] A. Al-Hourani and I. Guvenc, “On modeling Satellite-to-Ground Path-Loss in urban environments,” _IEEE Commun. Lett._ , vol. 25, no. 3, pp. 696–700, 2021.
  * [31] C. Zhan and Y. Zeng, “Energy-efficient data uploading for cellular-connected UAV systems,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 11, pp. 7279–7292, 2020.
  * [32] Y. Zeng, J. Xu, and R. Zhang, “Energy minimization for wireless communication with rotary-wing UAV,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 4, pp. 2329–2345, Apr. 2019.
  * [33] J.-H. Lee, K.-H. Park, Y.-C. Ko, and M.-S. Alouini, “Throughput maximization of mixed FSO/RF UAV-aided mobile relaying with a buffer,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 1, pp. 683–694, 2021.
  * [34] ——, “Optimal resource allocation and placement for terrestrial and aerial base stations in mixed RF/FSO backhaul networks,” in _Proc. IEEE Vehicular Technology Conf. (VTC-Spring)_ , May 2020, pp. 1–5.
  * [35] J. Foerster, N. Nardelli, G. Farquhar, T. Afouras, P. H. S. Torr, P. Kohli, and S. Whiteson, “Stabilising experience replay for deep Multi-Agent reinforcement learning,” ser. Proc. of International Conf. on Machine Learning (ICML), vol. 70, Sydney, Australia, 06–11 Aug 2017, pp. 1146–1155.
  * [36] H. van Hasselt, A. Guez, M. Hessel, V. Mnih, and D. Silver, “Learning values across many orders of magnitude,” 2016, p. 4294–4302.
  * [37] V. R. Konda and J. N. Tsitsiklis, “Actor-critic algorithms,” ser. Proc. of International Conf. on Neural Information Processing (NIPS), 1999, pp. 1008–1014.
  * [38] Z. Wang, V. Bapst, N. Heess, V. Mnih, R. Munos, K. Kavukcuoglu, and N. de Freitas, “Sample efficient actor-critic with experience replay,” _arXiv: 1611.01224 [cs.LG]_ , 2017.
  * [39] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” _IEEE/ACM Transactions on Networking_ , vol. 8, no. 5, pp. 556–567, 2000\.
  * [40] 3GPP TR 21.916 v0.5.0, “Release 16 description; summary of rel-16 work items,” Sep. 2021.
  * [41] M. Scheinfeild, N. S. Kopeika, and R. Melamed, “Acquisition system for microsatellites laser communication in space,” in _Free-Space Laser Communication Technologies XII_ , vol. 3932. SPIE, 2000, pp. 166 – 175.
  * [42] J. Schrittwieser, T. Hubert, A. Mandhane, M. Barekatain, I. Antonoglou, and D. Silver, “Online and offline reinforcement learning by planning with a learned model,” _arXiv: 2104.06294 [cs.LG]_ , 2021.