# On the Optimal 3D Placement of a UAV Base Station for Maximal Coverage of
UAV Users
††thanks: The authors would like to acknowledge the support of the Natural
Sciences and Engineering Research Council Canada (NSERC), Huawei Canada, and
Tunisian Ministry of Higher Education and Scientific Research.

Nesrine Cherif1, Wael Jaafar 2, Halim Yanikomeroglu2, and Abbas Yongacoglu1
1School of Electrical Engineering and Computer Science, University of Ottawa,
Ottawa, ON, Canada.
2 Department of Systems and Computer Engineering, Carleton University, Ottawa,
ON, Canada.
Email: 1{ncher082<EMAIL_ADDRESS>2{waeljaafar<EMAIL_ADDRESS>
###### Abstract

Unmanned aerial vehicles (UAVs) can be users that support new applications, or
be communication access points that serve terrestrial and/or aerial users. In
this paper, we focus on the connectivity problem of aerial users when they are
exclusively served by aerial base stations (BS), i.e., UAV-BSs. Specifically,
the 3D placement problem of a directional-antenna equipped UAV-BS, aiming to
maximize the number of covered aerial users under a spectrum sharing policy
with terrestrial networks, is investigated. Given a known spectrum sharing
policy between the aerial and terrestrial networks, we propose a 3D placement
algorithm that achieves optimality. Simulation results show the performance of
our approach, in terms of number of covered aerial users for different
configurations and parameters, such as the spectrum sharing policy, antenna
beamwidth, transmit power, and aerial users density. These results represent
novel guidelines for exclusive aerial networks deployment and applications,
distinctively for orthogonal and non-orthogonal spectrum sharing policies with
terrestrial networks.

##  I Introduction

The number of unmanned aerial vehicles (UAVs) is expected to skyrocket in the
near future according to reports from the US federal aviation administration
(FAA). Based on statistics of March 2020, slightly over 1.5 million UAVs are
registered in the US, and the number is projected to increase exponentially in
the upcoming years, as UAVs are becoming an important part of the every-day’s
life [1]. UAVs are expected to be part of the 5G wireless networks in two
ways: 1) as an aerial base station (UAV-BS) that provides cellular
connectivity [2] or 2) as an aerial user (UAV-UE) [3]. Due to their flexible
deployment, UAV-BSs (a.k.a., UxNBs in 3GPP terminology [4]), can provide in-
demand wireless broadband in temporary events or ubiquitous cellular coverage
in hard-to-access remote areas [2]. Meanwhile, UAV-UEs are used to accomplish
new services and tasks, such as flying taxis, package delivery, video
surveillance, aerial security inspection, wireless sensors data collection,
etc. To do so, UAV-UEs require a reliable connectivity to the wireless
network. Since most terrestrial BSs are down-tilted, their vertical coverage
is rather patchy and does not satisfy the stringent requirements of UAV-UEs
operations [5, 6]. In addition, hard-to-access remote areas may not have
terrestrial BSs, hence, UAV-UEs would be left without any cellular
connectivity to fulfill their tasks. Consequently, providing ubiquitous aerial
coverage using UAV-BSs becomes a key enabler of reliable UAV-UEs
communications. Hence, a comprehensive aerial coverage planning using UAV-BSs
is urgently needed to enable UAV-UEs based services.

Several works on UAV-based wireless communications have investigated
challenges linked to the efficient deployment of UAV-BSs to serve terrestrial
users. For instance, the authors of [7] developed an efficient algorithm for
3D UAV-BS placement to serve terrestrial users. Then, they extended their
study in [8] to the impact of the Quality-of-Service (QoS) irregularity on the
optimal deployment of the UAV-BS. In [9], the authors proposed an efficient
algorithm to maximize the sum-rate of terrestrial users by jointly optimizing
the UAV-BSs wireless backhaul bandwidth and the wireless link association
between terrestrial users and UAV-BSs. Also, authors in [10] investigated the
joint placement and power allocation of a UAV-BS to maximize the coverage of
terrestrial users. Finally, the authors of [11] studied the efficient
deployment of multiple UAV-BSs for terrestrial coverage using the circle
packing theorem.

Literature on cellular-connected UAVs, i.e., UAV-UEs, has been mainly focusing
on reutilizing the terrestrial network as the exclusive communications
provider to UAV-UEs. For instance, authors of [12] derived the connectivity
performance of a typical UAV-UE served by a network of terrestrial BSs, by
leveraging tools from stochastic geometry. The same authors gave interesting
insights and design recommendations in [13] for UAV-UEs deployment under the
assumption of exclusive cellular coverage provided by terrestrial networks.

Recently, we investigated in [6] the coverage probability of UAV-UEs in hybrid
terrestrial/aerial networks, called vertical heterogeneous networks
(VHetNets). We showed that in VHetNets, UAV-UEs are more likely to be served
by UAV-BSs since terrestrial BSs do not provide enough power to UAV-UEs at
high elevation angles. Moreover, the authors of [3, 14] proposed a novel
wireless network architecture of UAVs, where the optimal 3D cell association,
i.e., between UAV-UEs and UAV-BSs, is developed in order to minimize the
average latency at UAV-UEs. In their study, UAV-BSs were equipped with omni-
directional antennas, and thus their 3D coverage was modeled as a truncated
polyhedron. Yet, the 3D coverage of UAV-UEs using UAV-BSs equipped with
directional antennas is still unexplored.

Consequently, we investigate in this paper the optimal 3D deployment of a
directional-antenna equipped UAV-BS in an aerial system, where UAV-UEs are
assumed to be exclusively associated with UAV-BSs. In particular, we formulate
the UAV-BS 3D placement problem aiming to maximize the number of covered UAV-
UEs, given a spectrum sharing policy with terrestrial networks. Unlike
terrestrial networks where all users are typically located at the ground
altitude, UAV-UEs fly/hover in the 3D space at different locations and
altitudes, with respect to flight regulations. As a consequence, the 3D
coverage problem of UAV-UEs is more complex than in its terrestrial
counterpart. Nevertheless, we propose a low complexity algorithm that
determines the 3D optimal UAV-BS placement to cover the maximal number of UAV-
UEs. Since spectrum sharing between aerial and terrestrial networks does
affect the co-channel interference at terrestrial UEs, we propose a spectrum-
aware UAV-BS 3D placement in the aerial network. The results obtained
illustrate the coverage performance superiority of the UAV-BS under an
orthogonal spectrum sharing (OSS) policy over its non-OSS (N-OSS) counterpart,
where the UAV-BS placement is constrained by an interference-avoidance
condition at the terrestrial network. Also, they show distinct behaviors in
OSS and N-OSS, given different parameters and configurations, e.g., antenna
beamwidth, transmit power, aerial users density, aerial users clustering, and
interference condition. Results obtained constitute essential guidelines to
the co-existence of exclusive aerial networks with terrestrial networks.

The rest of the paper is organized as follows. In Section II, the system model
is presented. Section III formulates the 3D UAV-BS deployment problem under
orthogonal and non-orthogonal spectrum sharing policies with terrestrial
networks, and presents the associated solutions. Section IV illustrates the
simulation results. Finally, Section V concludes the paper.

##  II System Model

Figure 1: System model.

We assume a 3D geographical area in the open sky, delimited by two altitude
levels, namely $h_{\rm min}$ and $h_{\rm max}$, as shown in Fig. 1. In this
area, a set $\mathcal{U}$ of UAV-UEs fly/hover at different altitudes. It is
worth mentioning that according to the 3GPP report in [5], UAV-UEs cannot
operate at altitudes above 300 meters. Moreover, the UAV-UEs are assumed to
have the same power sensitivity $P_{\min}$, i.e., any UAV-UE succeeds in
decoding a received signal when the latter’s power is above $P_{\min}$. Let
$\textbf{q}_{i}=[x_{i},y_{i},z_{i}]$ be the 3D location of the $i^{\rm th}$
UAV-UE belonging to the set $\mathcal{U}$, such that $h_{\rm min}\leq
z_{i}\leq h_{\rm max}$.

We assume that a directional-antenna equipped UAV-BS will be deployed to serve
the UAV-UEs. Its antenna gain (in dB) is given by [11, eq (1)]

$G=\left\\{\begin{array}[]{ll}G_{\rm 3dB},&-\frac{\theta_{\rm
B}}{2}\leqslant\psi\leqslant\frac{\theta_{\rm B}}{2},\\\ g_{\rm
s},&\text{otherwise},\end{array}\right.$ (1)

where $\frac{\theta_{\rm B}}{2}$ is the UAV-BS antenna’s half beamwidth (in
degrees), $\psi$ is the sector angle, $G_{\rm
3dB}\approx\frac{29000}{\theta_{\rm B}^{2}}$ is the main-lobe gain, and
$g_{\rm s}$ is the side-lobe antenna gain.

In this work, we optimize the 3D location of the UAV-BS, designated by
$\textbf{q}_{\rm{BS}}=[x_{\rm BS},y_{\rm BS},z_{\rm BS}]$, in order to serve
the maximal number of UAV-UEs. Intuitively, the UAV-BS would be placed above
the UAV-UEs such that its antenna is tilted-down towards them in order to
provide cellular connectivity for their operations. Specifically, the altitude
of the UAV-BS should be at least $z_{\rm BS}\geq h_{\rm max}$. Finally, we
assume that the UAV-BS equivalent effective isotropic radiated power (EIRP),
denoted $P_{\rm T}$, is written as

$P_{\rm T}=P_{t}(\theta_{\rm B})+G_{\rm 3dB},$ (2)

where $P_{t}(\theta_{\rm B})$ is the transmit power associated to the
beamwidth of the directional antenna. From (1), we note that a larger antenna
beamwidth $\theta_{B}$ results in a smaller 3 dB gain $G_{\rm{3dB}}$, thus
$P_{t}(\theta_{B})$ has to be increased in order to maintain a fixed $P_{\rm
T}$.

When the UAV-BS communicates with the $i^{\rm th}$ UAV-UE, the received power
can be expressed by

$P_{i}=P_{\rm T}-\underbrace{10n\log_{10}\left(\frac{4\pi
f_{c}d_{i}}{c}\right)}_{=L_{i}}\geq P_{\min},$ (3)

where $n$ is the pathloss exponent, $f_{c}$ denotes the carrier frequency,
$d_{i}$ is the distance between the $i^{\rm th}$ UAV-UE and the UAV-BS, and
$L_{i}$ is the pathloss experienced by the $i^{\rm th}$ UAV-UE. The inequality
in (3) ensures that the received power is above the sensitivity threshold. By
taking the equality in (3), a pathloss maximal threshold can be defined as

$L_{\rm th}=P_{\rm T}-P_{\min}\geq L_{i}.\vspace{-1em}$ (4)

By substituting $L_{i}$ in (4) by its expression in (3), and after some
mathematical manipulations, we can define the 3D coverage region, denoted
$\mathcal{C}_{\rm in}$, by a maximal distance between the UAV-BS and UAV-UEs,
given by

$d_{\max}=\frac{c}{4\pi f_{c}}\;10^{\frac{L_{\rm th}}{10n}}.$ (5)

Since aerial networks would co-exist with terrestrial networks, the
interference component generated by the deployment of UAV-BSs and affecting
the terrestrial users may be non-negligible, and hence requires particular
adjustments of the aerial network. In this context, we distinguish two
spectrum sharing policies between the aerial and terrestrial networks: 1)
orthogonal spectrum sharing (OSS), where the UAV-BS communicates with its
users at a different frequency band than the terrestrial BSs, and 2) non-OSS
(N-OSS), where the aerial and terrestrial networks operate at the same
frequency band. Under the OSS policy, terrestrial users won’t experience
interference from the UAV-BS, even if the latter operates at a relatively low
altitude or high transmit power. However, under N-OSS, a regulatory altitude,
called $h_{\rm guard}$, must be respected when deploying the UAV-BS, in order
to prevent any undesired and additional interference at terrestrial users.
$h_{\rm guard}$ can be seen as the highest altitude at which a terrestrial
user can be located. Hence, the received interference power at any terrestrial
user has to be lower than a certain threshold, called $\Delta$.111This power
threshold can be seen as the peak tolerated interference by any terrestrial
user, under the assumption that transmissions in the terrestrial network are
continuous [15]. Specifically, we have

$P_{\rm T}-10n\log\left(\frac{4\pi f_{c}\left(z_{\rm BS}-h_{\rm
guard}\right)}{c}\right)\leq\Delta,$ (6)

where $z_{\rm{BS}}-h_{\rm guard}$ is the smallest distance that can separate
the UAV-BS from a terrestrial user, i.e., the latter is located directly below
the UAV-BS at altitude $h_{\rm guard}$. According to (6), the UAV-BS altitude
has to respect the condition

$z_{\rm{BS}}\geq\frac{c}{4\pi f_{c}}\;10^{\frac{P_{\rm
T}-\Delta}{10n}}+h_{\rm{guard}}=\underbrace{d_{\max}\;10^{\frac{P_{\min}-\Delta}{10n}}}_{=d^{\prime}_{\max}}+h_{\rm{guard}}.$
(7)

Based on (7), the minimum altitude of the UAV-BS, when following a N-OSS
policy, depends on both the receiver sensitivity of UAV-UEs and the tolerated
interference level at terrestrial users.

### UAV-BS Coverage Region

Based on (4)–(5), we infer that the 3D coverage region of the UAV-BS
$\mathcal{C}_{\rm in}$ is composed of two volumes, as illustrated in Fig. 1:

  * •

A 3D cone with the UAV-BS placed at its tip. The cone’s opening angle is
$\theta_{\rm B}$ and its height, denoted $h_{\rm cone}$, is

$h_{\rm cone}=d_{\max}\cos\left({\theta_{\rm B}}/{2}\right),$ (8)

whereas its base’s radius, $R_{\rm base}$, can be written as

$R_{\rm base}=d_{\max}\sin\left({\theta_{\rm B}}/{2}\right).$ (9)

  * •

A faced-down half ellipsoid with radii $(R_{\rm base},R_{\rm
base},d_{\max}-h_{\rm cone})$, and its center placed at coordinates
$\textbf{q}_{\rm{elp}}=[x_{\rm BS},y_{\rm BS},z_{\rm{BS}}-h_{\rm cone}]$,
where the ellipsoid equation is given by

$\frac{(x-x_{\rm BS})^{2}}{R_{\rm{base}}^{2}}+\frac{(y-y_{\rm
BS})^{2}}{R_{\rm{base}}^{2}}+\frac{(z-z_{\rm{BS}}+h_{\rm{cone}})^{2}}{\left(d_{\max}-h_{\rm{cone}}\right)^{2}}=1.$
(10)

In the next section, we formulate the 3D placement problem, then we propose an
algorithm that places the UAV-BS at the best location, which allows covering
the maximal number of UAV-UEs. The 3D UAV-BS deployment depends on the adopted
spectrum sharing policy, as it will be shown below.

##  III Optimal UAV-BS 3D placement for maximum UAV-UEs coverage

Received interference at the terrestrial users from the UAV-BS depends on the
latter’s 3D placement and/or transmit power. Its deployment should be
carefully planned, given the adopted spectrum sharing policy. In the
subsequent sections, we investigate the 3D optimal placement under OSS and
N-OSS policies.

###  III-A UAV-BS 3D Placement Under OSS Policy

Under the OSS policy, The UAV-BS altitude $z_{\rm{BS}}$ is not restricted, as
it doesn’t result in any interference at the terrestrial users.

######  Remark 1.

The $i^{\rm th}$ UAV-UE falls into the UAV-BS coverage region
$\mathcal{C}_{\rm{in}}$ if it satisfies the two following conditions:

$c_{1}:\;\lVert\mathbf{q}_{i}-\mathbf{q}_{\rm{BS}}\rVert\leq d_{\max}$ (11a)
$c_{2}:\;\cos{\left(\frac{\theta_{B}}{2}\right)}\leq\frac{|z_{i}-z_{\rm{BS}}|}{\lVert\mathbf{q}_{i}-\mathbf{q}_{\rm{BS}}\rVert},$
(11b)

where $\lVert\cdot\rVert$ is the Euclidean norm and $|\cdot|$ is the absolute
value operations.

According to (11a), the $i^{\rm th}$ UAV-UE is within the region
$\mathcal{C}_{\rm{in}}$ when it is distant from the UAV-BS by at most
$d_{\max}$. Meanwhile, (11b) ensures that the elevation angle between the
$i^{\rm th}$ UAV-UE and UAV-BS is below the UAV-BS antenna half-beamwidth
$\frac{\theta_{\rm B}}{2}$.

Let $c_{i}$ be the binary variable that indicates whether the $i^{\rm th}$
UAV-UE is in $\mathcal{C}_{\rm in}$ or not, i.e., $c_{i}=1$ when it is in the
coverage region of the UAV-BS, and $c_{i}=0$ otherwise. Consequently, the UAV-
BS coverage maximization problem can be formulated as a mixed integer non-
linear problem (MINLP) as follows:

$\displaystyle\max_{\mathbf{q}_{\rm{BS}},\mathbf{c}}$
$\displaystyle\quad\sum_{i\in\mathcal{U}}c_{i}$ (P1) s.t. $\displaystyle
c_{i}\times\lVert\mathbf{q}_{i}-\mathbf{q}_{\rm{BS}}\rVert\leq
d_{\max},\forall i\in\mathcal{U},$ (P1.a) $\displaystyle
c_{i}\times{\lVert\mathbf{q}_{i}-\mathbf{q}_{\rm{BS}}\rVert}\leq\frac{|z_{i}-z_{\rm{BS}}|}{\cos{\left(\frac{\theta_{\rm
B}}{2}\right)}},\forall i\in\mathcal{U},$ (P1.b) $\displaystyle
c_{i}\in\\{0,1\\},\forall i\in\mathcal{U},$ (P1.c)

where $\textbf{c}=[c_{1},\ldots,c_{U}]$, and $U$ is the total number of UAV-
UEs. In order to guarantee the feasibility of the constraints (P1.a)–(P1.b)
when $c_{i}=0$, we rewrite them as follows [7]:

$c_{1}:\;\lVert\mathbf{q}_{i}-\mathbf{q}_{\rm{BS}}\rVert\leq
d_{\max}+N(1-c_{i}),\;\forall i\in\mathcal{U}$ (13a)
$c_{2}:\;{\lVert\mathbf{q}_{i}-\mathbf{q}_{\rm{BS}}\rVert}\leq\frac{|z_{i}-z_{\rm{BS}}|}{\cos{\left(\frac{\theta_{\rm
B}}{2}\right)}}-N(1-c_{i}),\;\forall i\in\mathcal{U},$ (13b)

where $N$ is a very large number. The complexity of solving (P1) arises from
the dependency between $\mathbf{q}_{\rm{BS}}$ and $z_{\rm BS}$ in constraint
(13b). To tackle this issue, we propose to decouple the 2D UAV-BS location and
its altitude’s optimization. Indeed, for a specific UAV-BS altitude $z_{\rm
BS}^{1}$, (P1) reduces to a 2D UAV-BS location optimization problem. Then,
exhaustive search over the altitude allows to find the optimal solution to
(P1). The 2D optimization problem can be written as

$\displaystyle\max_{{x}_{\rm{BS}},{y}_{\rm{BS}},\mathbf{c}}$
$\displaystyle\quad\sum_{i\in\mathcal{U}}c_{i}$ (P2) s.t.
$\displaystyle\lVert\mathbf{q}_{i}-\mathbf{q}_{\rm{BS}}^{1}\rVert\leq
d_{\max}+N(1-c_{i}),\forall i\in\mathcal{U}$ (P2.a)
$\displaystyle{\lVert\mathbf{q}_{i}-\mathbf{q}_{\rm{BS}}^{1}\rVert}\leq\frac{|z_{i}-z_{\rm{BS}}^{1}|}{\cos{\left(\frac{\theta_{\rm
B}}{2}\right)}}-N(1-c_{i}),\forall i\in\mathcal{U}$ (P2.b) $\displaystyle
c_{i}\in\\{0,1\\},\forall i\in\mathcal{U},$ (P2.c)

where $\textbf{q}_{\rm{BS}}^{1}=[x_{\rm{BS}},y_{\rm{BS}},z_{\rm{BS}}^{1}]$.
Since (P2.a)-(P2.b) constraints are convex, (P2) can be solved using MOSEK
parser in the CVX package of Matlab [16].

Algorithm 1 3D UAV-BS placement under OSS policy

1:$P_{\rm T},\theta_{\rm B},P_{\rm min},f_{c},h_{\min},h_{\max}$

2:($\textbf{q}_{\rm BS}^{\rm opt}$, $\textbf{c}^{\rm opt}$)

3:Compute $d_{\max}$ using (5)

4:for $z_{\rm BS}^{1}\in[h_{\max},h_{\max}+d_{\max}]$ do

5: Solve (P2), get ($\bar{\textbf{q}}_{\rm BS}^{1},\bar{\textbf{c}}^{1}$), and
store it in a vector v

6:end for

7:Select the best element in v that maximizes $\sum_{i\in\mathcal{U}}c_{i}$

8:Return ($\textbf{q}_{\rm BS}^{\rm opt}$, $\textbf{c}^{\rm opt}$) as the best
element in v.

Assuming that (${\bar{\textbf{q}}}_{\rm{BS}}^{1}$, $\bar{\textbf{c}}^{1}$) is
the optimal solution of (P2) for a given $z_{\rm{BS}}^{1}$, then (P1) can be
solved iteratively using Algorithm 1, detailed above. In line 2 of Algorithm
1, $z_{\rm BS}^{1}$ is in the range $[h_{\max},h_{\max}+d_{\max}]$. Without
loss of generality, $d_{\max}\geq h_{\max}-h_{\min}$, thus $z_{\rm
BS}^{1}=h_{\max}$ ensures that the vertical coverage of the UAV-BS is deep
enough to cover even UAV-UEs flying/hovering at the lowest authorized altitude
$h_{\min}$. In contrast, when $z_{\rm BS}^{1}=h_{\max}+d_{\max}$, the coverage
area of the UAV-BS is tangent to the horizontal plan at altitude $h_{\max}$,
i.e., only a few users flying/hovering at $h_{\max}$ can be covered.

###  III-B UAV-BS 3D Placement Under N-OSS Policy

Under the N-OSS policy, the UAV-BS coverage region is restricted in order to
respect the tolerated interference level at terrestrial users. In this case,
the UAV-BS’ total transmit power, $P_{\rm T}$, should be carefully adjusted to
ensure that the UAV-BS hovers at an altitude of at least $h_{\max}$222Being at
least at $h_{\max}$ with a sufficient coverage depth, $d_{\max}$, ensures a
maximized vertical coverage. as described in Fig. 1. Thus, the UAV-BS total
transmit power should be no smaller than $P_{\rm T}^{\rm low}$ expressed by

$P_{\rm T}^{\rm low}=10n\log\left(\frac{4\pi f_{c}\left(h_{\max}-h_{\rm
guard}\right)}{c}\right)+\Delta.$ (15)

Since the UAV-BS altitude cannot exceed $d_{\max}+h_{\max}$333Above this
altitude, the coverage performance is null since no UAV-UE flies/hovers at
altitudes higher than $h_{\max}$., the UAV-BS total transmit power cannot
exceed $P_{\rm T}^{\rm high}$, which is given by

$P_{\rm T}^{\rm high}=10n\log\left(\frac{4\pi f_{c}\left(h_{\max}-h_{\rm
guard}\right)}{c\times\Omega}\right),$ (16)

where $\Omega=10^{-\frac{\Delta}{10n}}-10^{-\frac{P_{\min}}{10n}}$.

###### Proof.

The above result follows from substituting (4)–(5) into (7), where equality is
taken for $z_{\rm BS}=d_{\max}+h_{\max}$. ∎

Finally, using (15)–(16), we have $P_{\rm T}^{\rm low}\leq P_{\rm T}\leq
P_{\rm T}^{\rm high}$.

The UAV-BS 3D placement problem in N-OSS can be formulated as in (P1) with the
additional optimization parameter $P_{\rm T}$ and constraints (7), (15), and
(16). Unlike OSS policy, the UAV-BS EIRP should be optimized to guarantee two
conditions: 1) the UAV-BS coverage region is maximized, and 2) imposed
spectrum-sharing interference condition is respected. Subsequently, a similar
approach as in Algorithm 1 can be followed to solve it. The proposed approach
is presented in Algorithm 2, where $P_{\rm T}^{1}\in[P_{\rm T}^{\rm
low},P_{\rm T}^{\rm high}]$ and $z_{\rm
BS}^{1}\in[h_{\max},d_{\max}+h_{\max}]$.

Algorithm 2 3D UAV-BS placement under N-OSS policy

1:$\theta_{\rm B},P_{\rm min},f_{c},h_{\min},h_{\max},h_{\rm guard},\Delta$

2:($\textbf{q}_{\rm BS}^{\rm opt}$, $\textbf{c}^{\rm opt}$, ${P}_{\rm T}^{\rm
opt}$)

3:Compute $P_{\rm T}^{\min}$ and $P_{\rm T}^{\rm th}$ using (15) and (16)
resp.

4:for $P_{\rm T}^{1}\in[P_{\rm T}^{\rm low},P_{\rm T}^{\rm high}]$ do

5: Compute $d_{\max}$ and $d^{\prime}_{\max}$ using (5) and (7) resp.

6: for $z_{\rm BS}^{1}\in[h_{\max},h_{\max}+d_{\max}]$ do

7: Solve (P2), get ($\bar{\textbf{q}}_{\rm BS}^{1},\bar{\textbf{c}}^{1}$), and
store it in vector v

8: end for

9: Select the best element in v that maximizes $\sum_{i\in\mathcal{U}}c_{i}$
and store it with $P_{\rm T}^{1}$ in a vector u

10:end for

11:Select the best element in u that maximizes $\sum_{i\in\mathcal{U}}c_{i}$

12:Return ($\textbf{q}_{\rm BS}^{\rm opt}$, $\textbf{c}^{\rm opt}$, ${P}_{\rm
T}^{\rm opt}$) as the best element in u.

##  IV Simulation Results

In our simulations, we consider a 3 km × 3 km area. Unless stated otherwise,
we assume that $P_{\rm T}=30$ dBm, $f_{c}=2$ GHz, $P_{\min}=-70$ dBm,
$\theta_{\rm B}=60^{\circ}$, $h_{\min}=100$ meters, $h_{\max}=300$ meters,
$h_{\rm guard}=50$ meters, and $\Delta=-73$ dBm. Also, simulations are
averaged for 500 UAV-UEs scenarios. For the UAV-UEs distribution per volume
unit (${\rm km}^{3}$), we assume two point processes:

  * •

Homogeneous Poisson point process (HPPP) for UAV-UEs uniform distribution in
the 3D area delimited vertically by $h_{\min}$ and $h_{\max}$, with density
$\lambda$ UAV-UEs/km3.

  * •

Matérn cluster point process (MCPP) requiring two overlaying point processes:
1) a HPPP with density $\lambda_{P}$/${\rm km}^{3}$ as the parent cluster
heads, and 2) a daughter HPPP with density $\lambda_{D}$ of UAV-UEs belonging
to a sphere with radius $r_{D}$ centered at each parent cluster head. MCPP
mimics the heterogeneity of the UAV-UEs distribution, where a higher
$\lambda_{D}$ means more clustered UAV-UEs.

(a) Avg. max. number of covered UAV-UEs vs. UAV-BS altitude.

(b) Avg. max. number of covered UAV-UEs vs. UAV-BS antenna beamwidth.

(c) Avg. max. number of covered UAV-UEs vs. distribution of UAV-UEs.

Figure 2: UAV-BS coverage performance under OSS policy.

###  IV-A UAV-BS Coverage Performance Under OSS Policy

Fig. 2 presents the optimal coverage performance of the UAV-BS under OSS
policy.

Fig. 2(a) shows the average maximum number of covered UAV-UEs (a.k.a. coverage
performance) as a function of UAV-BS altitude $z_{\rm BS}^{1}$, for different
$\theta_{B}$ and HPPP $\lambda$ values. Under OSS, an optimal altitude can be
reached, which does not depend on the distribution of the UAV-UEs $\lambda$.
However, as the UAV-BS antenna’s beamwidth $\theta_{B}$ increases, the UAV-BS
hovers at a lower altitude to cover more UAV-UEs.

In Fig. 2(b), the impact of the UAV-BS antenna’s beamwidth $\theta_{B}$, for
different $L_{\rm th}$ is investigated, given an MCPP UAV-UEs distribution. As
$\theta_{B}$ or $L_{\rm th}$ increases, the coverage performance improves. The
same occurs when $\lambda_{D}$ is high, i.e., UAV-UEs clusters are denser.
Moreover, the transmit power $P_{t}(\theta_{B})$ of the UAV-BS is evaluated
using (2). When $\theta_{B}$ is higher, $G_{\rm 3dB}$ decreases, thus
increasing $P_{t}(\theta_{B})$, i.e., covering more UAV-UEs using a wide-
beamwidth antenna comes at the expense of a higher transmit power.

Fig. 2(c) compares the coverage performance of our proposed algorithm to that
of two benchmarks, namely “minimum sum distance” proposed in [10] where the
UAV-BS placement is determined for minimum pathloss to all UAV-UEs, and
“random placement” where the UAV-BS location is randomly selected. The
coverage performance is evaluated as a function of the MCPP density
$\lambda_{D}$, and for different MCPP $\lambda_{P}$ values. We found that UAV-
UEs clustering, i.e., higher $\lambda_{D}$ and $\lambda_{P}$, improves the
coverage performance for all UAV-BS placement approaches. Nevertheless, our
algorithm significantly outperforms both benchmarks.

###  IV-B UAV-BS Coverage Performance Under N-OSS Policy

Fig. 3 presents the optimal coverage performance of the UAV-BS under N-OSS
policy.

In Fig. 3(a), we show the coverage performance as a function of the UAV-BS
altitude, given a HPPP UAV-UEs distribution. For any ($P_{\rm T}$,
$\theta_{B}$, $\lambda$) setup, the optimal altitude is always the smallest
allowed one, which is given by (7). This is expected since increasing the
altitude can only reduce the overlapping area between the coverage region and
the operating UAV-UEs’ air corridor, thus reducing the number of covered UAV-
UEs. This interesting outcome allows to reduce the steps taken in Algorithm 2
by omitting step 4, and calculating the best altitude for a given $P_{\rm T}$
using (7) instead.

Fig. 3(b) studies the impact of $P_{\rm T}$ on the coverage performance, for
different $\theta_{B}$ and $\lambda$. For any ($\theta_{B}$, $\lambda$) setup,
an optimal $P_{\rm T}$ value can be obtained, which maximizes the coverage
performance. Also, as $\theta_{B}$ reduces, i.e., narrower antenna beamwidth,
more transmit power is required to cover the maximal number of UAV-UEs.
Indeed, the loss in horizontal coverage (wider $\theta_{B}$) is compensated by
a deeper vertical coverage (higher $P_{\rm T}$), with respect to the
interference condition $\Delta$ (i.e., moving to a higher altitude as shown in
Fig. 3(a)). Therefore, a low-altitude UAV-BS uses less transmit power for
connectivity to UAV-UEs, while keeping its interference at the terrestrial
users lower than $\Delta$.

Finally, the impact of the regulatory altitude, $h_{\rm guard}$, on the
coverage performance is illustrated in Fig. 3(c). A more relaxed regulatory
altitude for terrestrial users, i.e., smaller $h_{\rm guard}$, increases the
average maximum number of covered UAV-UEs. Indeed, the UAV-BS would move with
more flexibility in order to increase the overlapping area between its
coverage region and the UAV-UEs’ air corridor. Furthermore, wider UAV-BS
antenna beamwidth always provides a better coverage performance independently
from the regulatory altitude. Eventually, under the N-OSS policy, the
regulatory altitude $h_{\rm guard}$ and the peak tolerated interference at
terrestrial users $\Delta$ should be carefully considered as they
significantly impact the 3D UAV-BS placement and coverage performance.

(a) Avg. max. number of covered UAV-UEs vs. UAV-BS altitude.

(b) Avg. max. number of covered UAV-UEs vs. UAV-BS total transmit power.

(c) Avg. max. number of covered UAV-UEs vs. the N-OSS regulatory altitude.

Figure 3: UAV-BS coverage performance under N-OSS policy.

##  V Conclusion

In this paper, we studied the 3D placement problem of a directional-antenna
equipped UAV-BS, aiming to maximize the number of flying/hovering UAV-UEs
under its coverage region. The problem is formulated under two spectrum
sharing policies, OSS and N-OSS, where frequency resources are either shared
orthogonally or non-orthogonally between the aerial and terrestrial networks.
Then, we solved the 3D UAV-BS placement using an iterative approach, where the
horizontal 2D location of the UAV-BS is optimized for each explored altitude,
and finally the altitude demonstrating the best coverage performance is
selected. Simulation results have shown that under OSS policy, the UAV-BS
hovers at low altitudes when its antenna’s beamwidth is large. Also, we found
that differences in UAV-UEs location distributions affect the performance of
the UAV-BS. Indeed, the coverage performance improves when more UAV-UEs are
clustered together. On the other hand, under N-OSS policy, the optimal UAV-BS
altitude is always the lowest authorized one. Moreover, UAV-BS transmit power
has to be optimized for maximum 3D coverage, while satisfying the interference
condition on the terrestrial network. Finally, N-OSS results showed that a
narrower UAV-BS antenna beamwidth is compensated by a higher transmit power
and altitude.

## References

  * [1] Federal Aviation Administration (FAA). [Online]. Available: https://www.faa.gov/uas/resources/by˙the˙numbers/
  * [2] I. Bor-Yaliniz and H. Yanikomeroglu, “The new frontier in RAN heterogeneity: Multi-tier drone-cells,” _IEEE Commun. Mag._ , vol. 54, no. 11, pp. 48–55, Nov. 2016.
  * [3] M. Mozaffari, A. T. Z. Kasgari, W. Saad, M. Bennis, and M. Debbah, “Beyond 5G with UAVs: Foundations of a 3D wireless cellular network,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 1, pp. 357–372, Jan. 2019\.
  * [4] 3GPP, “Unmanned aerial system (UAS) support in 3GPP (release 17), TS 22.125,” Dec. 2019.
  * [5] ——, “Study on enhanced LTE support for aerial vehicles (release 15), TR 36.777,” Jun. 2018.
  * [6] N. Cherif, M. Alzenad, H. Yanikomeroglu, and A. Yongacoglu, “Downlink coverage analysis of an aerial user in vertical heterogeneous networks,” in _Proc. IEEE Glob. Commun. Conf. (Globecom)_ , Waikoloa, HI, USA, Dec. 2019, pp. 1–6.
  * [7] M. Alzenad, A. El-Keyi, F. Lagum, and H. Yanikomeroglu, “3-D placement of an unmanned aerial vehicle base station (UAV-BS) for energy-efficient maximal coverage,” _IEEE Wireless Commun. Lett._ , vol. 6, no. 4, pp. 434–437, Aug. 2017.
  * [8] M. Alzenad, A. El-Keyi, and H. Yanikomeroglu, “3-D placement of an unmanned aerial vehicle base station for maximum coverage of users with different QoS requirements,” _IEEE Wireless Commun. Lett._ , vol. 7, no. 1, pp. 38–41, Feb. 2018.
  * [9] E. Kalantari, I. Bor-Yaliniz, A. Yongacoglu, and H. Yanikomeroglu, “User association and bandwidth allocation for terrestrial and aerial base stations with backhaul considerations,” in _Proc. IEEE Int. Symp. on Pers., Indoor and Mobile Radio Commun. (PIMRC)_ , Montreal, QC, Canada, Oct. 2017, pp. 1–6.
  * [10] X. Liu, J. Wang, N. Zhao, Y. Chen, S. Zhang, Z. Ding, and F. R. Yu, “Placement and power allocation for NOMA-UAV networks,” _IEEE Wireless Commun. Lett._ , vol. 8, no. 3, pp. 965–968, Jun. 2019.
  * [11] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage,” _IEEE Commun. Lett._ , vol. 20, no. 8, pp. 1647–1650, Aug. 2016.
  * [12] M. M. Azari, F. Rosas, A. Chiumento, and S. Pollin, “Coexistence of terrestrial and aerial users in cellular networks,” in _Proc. IEEE Glob. Commun. Conf. (Globecom) Workshops_ , Singapore, Dec. 2017, pp. 1–6.
  * [13] M. M. Azari, F. Rosas, and S. Pollin, “Cellular connectivity for UAVs: Network modeling, performance analysis, and design guidelines,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 7, pp. 3366–3381, Jul. 2019.
  * [14] M. Mozaffari, A. T. Z. Kasgari, W. Saad, M. Bennis, and M. Debbah, “3D cellular network architecture with drones for beyond 5G,” in _Proc. IEEE Glob. Commun. Conf. (Globecom)_ , Abu Dhabi, UAE, Dec. 2018, pp. 1–6.
  * [15] W. Jaafar, T. Ohtsuki, W. Ajib, and D. Haccoun, “Impact of the CSI on the performance of cognitive relay networks with partial relay selection,” _IEEE Trans. Veh. Tech._ , vol. 65, no. 2, pp. 673–684, Feb. 2016.
  * [16] M. Grant and S. P. Boyd, “CVX: MATLAB software for disciplined convex programming,” _http://cvxr.com/cvx/_ , Jan. 2014.


# Enhancing Spatiotemporal Prediction Model using Modular Design and Beyond

Haoyu Pan 1 , Hao Wu 2, Tan Yang111Corresponding author *,1
1 School of Computer, Beijing University of Posts and Telecommunications
2 Institute of Advanced Technology, University of Science and Technology of
China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Predictive learning uses a known state to generate a future state over a
period of time. It is a challenging task to predict spatiotemporal sequence
because the spatiotemporal sequence varies both in time and space. The
mainstream method is to model spatial and temporal structures at the same time
using RNN-based or transformer-based architecture, and then generates future
data by using learned experience in the way of auto-regressive. The method of
learning spatial and temporal features simultaneously brings a lot of
parameters to the model, which makes the model difficult to be convergent. In
this paper, a modular design is proposed, which decomposes spatiotemporal
sequence model into two modules: a spatial encoder-decoder and a predictor.
These two modules can extract spatial features and predict future data
respectively. The spatial encoder-decoder maps the data into a latent
embedding space and generates data from the latent space while the predictor
forecasts future embedding from past. By applying the design to the current
research and performing experiments on KTH-Action and MovingMNIST datasets, we
both improve computational performance and obtain state-of-the-art results.

###### Index Terms:

Spatialtemporal predivitve learning, Representation learning, Deep Learning

##  I Introduction

Space-time dynamical system is common in the real world so related research on
spatiotemporal predictive learning has received extensive attention. It is
widely used in video prediction[1, 2], traffic flow prediction[3, 4, 5],
weather forecast[6, 7] and physical simulation system[8]. Different from time
series prediction, the spatiotemporal sequence at each time step can be
regarded as an image (or frame) distributed in higher dimensional feature
space. Spatiotemporal predictive learning requires sufficient modeling of time
and space structure[9].From the perspective of time, the model requires short-
term and long-term memory features, while from the perspective of space, it
needs to capture both short-range and long-range information.

In current deep neural network research, recurrent neural network (RNN) class
models have extraordinary effect on processing time-varying sequence, while
convolutional neural network(CNN) are widely used to capture spatial features
of images. Therefore, Shi et al. proposed an end-to-end model that combines
the architectures of CNN and RNN, called ConvLSTM[10], for spatio-temporal
predictive learning. On the other hand, with the advent of the transformer
architecture, an increasing number of sequence models turn to use transformer,
like natural language processing(NLP)[11, 12]. Transformer has better
parallelism than the RNN architecture, as demonstrated in NLP and time series
tasks. Then the spatiotemporal analysis models based on transformer[13, 5]
began to appear. However, there are two deficiencies in both RNN-based and
transformer-based architectures:

Deficiency I. During training, the model needs to capture temporal dependence
and spatial variance simultaneously. The large number of parameters involved
in training and slow calculation will hinder the convergence of the model.

Deficiency II. In terms of spatiotemporal feature encoding and decoding
methods, the model with pure CNN architecture performs well in the task of
image feature extraction, but performs poorly in the task of image generation.
Meanwhile, it is even more difficult for CNN to model time series changes and
spatial features at the same time, which leads to distortion of CNN’s frame
generation results in video sequences. Pixel-level prediction of
spatiotemporal sequences is still a challenging task.

We can decouple the spatiotemporal sequence prediction model into three parts:
the first part is used to capture the spatial features of the current time
step, which we call the spatial encoder. The second part combines the spatial
information captured by the first module and passes it in time to predict the
spatial features of the future frames, which we call the predictor. The last
part decodes the future spatial features generated by the predictor to
generate the real future spatiotemporal data, which we call the spatial
decoder. Since the spatial encoder and decoder are inverse operations to each
other, we can implement it with an encoder-decoder architecture, which we call
the spatial encoder-decoder. For example, in both ConvLSTM and
ConvTransformer, a pure CNN architecture is used to encode and decode spatial
features.

In computer systems, complex systems are often disassembled into relatively
simple sub-modules and then combined, and artificial intelligence systems can
do the same. In recent studies, including the current outstanding models like
PredRNN[14] and 3D-temporal convolutional transformer(TCTN)[15], both
parameters for both spatially dependent and temporally dependent aspects are
updated at training time, which leads to inefficiency of the model: a large
number of parameters need to be updated each time during training, so that
convergence is very slow. To address the deficiency I and II mentioned above,
we provide ideas to solve them.

For Deficiency I, we try to decompose a model into two modules: a spatial
encoder-decoder module and a predictive learning module, which is called a
predictor. The spatial encoder converts data into a latent space. Firstly, we
train a static image encoder-decoder, and when we do spatiotemporal sequence
prediction, we only need to input spatiotemporal data directly to this spatial
encoder-decoder, get the representation tensor of spatiotemporal data at each
time step of the sequence, and use this representation tensor instead of the
original image. This representation tensor is used to generate the
representation tensor of the future data instead of the original image.
Finally, the representation tensor generated by the predictor is input to the
spatial decoder to obtain the real spatiotemporal data. For Deficiency II, we
use Vector Quantised-Variational AutoEncoder(VQ-VAE)[16] to do this task
instead of CNN. VQ-VAE is an auto-encoder that has excellent performance in
image generation tasks and its architecture fits our needs.

We use two representative spatiotemporal sequence prediction models, PredRNN
and TCTN, as the predictor. The former predicts data using an RNN-like
architecture and the latter uses a transformer architecture for prediction.
The modification of these two different architectures demonstrates the
generality of our proposed approach. We do not make major changes to the
structure of the original models. The main changes are: on the one hand, the
input layer of the original model is modified so that the images are first
processed by a pre-trained VQ-VAE encoder before being fed into the model. On
the other hand, the parameters of the original model are reduced (the number
of layers remained the same, and the hidden units of each layer were halved).
Finally, we find experimentally that our approach improves the final results
of the model despite the reduction of the predictor parameters.

In summary, the contributions of this paper include the following:

  * •

Applying a modular design that decomposes sequence prediction model into two
parts: spatial decoder-encoder and predictor to making the training of the
model easier and more efficient.

  * •

Utilizing VQ-VAE to encode and generate images, which improves the data
generation quality.

##  II Related work

In this section we introduce two different temporal sequence model
architectures and analyze their characteristics. On the other hand, a VAE
model is introduced.

Convolutional RNNs. Models of ConvRNN-like architectures were first proposed
by Shi et al. They use convolutional operations instead of the fully connected
layer in FC-LSTM as a way to better capture spatiotemporal correlations in
spatiotemporal sequence data. However, due to its simple architecture,
ambiguity can occur in the generation of future frames. Many variant models of
ConvLSTM have been proposed[17, 18, 19], among which PredRNN is an improved
ConvLSTM network that is typical of RNN-based approaches. PredRNN adds a
spatiotemporal memory unit to the architecture of ConvLSTM and allows the data
to be passed along horizontal and vertical directions, enabling the model to
better model spatiotemporal correlation. Also RredRNN employs some techniques
to make better predictions, such as reverse schedule sampling(RSS), which
gradually replaces the real data with predicted data as input in a multi-step
iterative prediction process. The shortcomings of ConvRNNs are that they are
limited by the RNN architecture, have average prediction results when the
sequences are long, and are computationally intensive.

Convolutional Tranformers. Transformer research has gained significant results
in both natural language processing and computer vision fields, transformer-
based models in spatiotemporal sequence prediction tasks have gradually become
more numerous. The standard transformer uses stacked transformer blocks with
spatial attention and temporal attention for spatiotemporal sequence
prediction, however, the drawback is the same as FC-LSTM, limited by the fully
connected layers used, the model cannot capture short-term denpency well.
ConvTransformer[13] applies the transformer structure to the domain of
spatiotemporal sequential data, using multi-headed convolutional attention
instead of the traditional one-dimensional attention mechanism to capture
spatiotemporal features. convTransformer performs better in predicting
intermediate content with known context, but performs mediocrely for future
information. Inspired by the multi-headed convolutional attention in
ConvTransformer, Yang et al. proposed TCTN[15], a 3D convolutional
transformer-based spatiotemporal sequence prediction model.TCTN uses a
transformer-based encoder with temporal convolutional layers to be used to
capture both short-term and long-term dependencies, achieving results
comparable to PredRNN in some metrics. The results are comparable to those of
PredRNN in some metrics.

VQ-VAE. Vector quantised variational autoencoder(VQ-VAE), as known as a neural
discrete representation learning method, is a very effective auto encoder (AE)
model[16]. It consists of an encoder and a decoder. In the image generation
task, the image is input to the encoder and a latent embedding vector $z$ is
output. VQ-VAE also maintains a dictionary, which is a vector of length $D$.
The nearest vector $z^{\prime}$ is obtained by performing a nearest neighbor
search on $z$ in the dictionary, and $z^{\prime}$ is used as the final
encoding result instead of $z$. VQ-VAE uses a CNN with residual units to
perform a reduction of the encoding result $z^{\prime}$, to fit the
distribution of the encoding. When training VQ-VAE, since the process of
discrete encoding has no gradient, VQ-VAE uses Straight-Through Estimator
instead of the usual loss function. The model has great power to construct
images, videos and speech.

##  III Methods

###  III-A Overview

Figure 1: Pipeline of the modularly designed spatiotemporal sequence
prediction model. The blue line indicates the data flow of the spatial
encoder-decoder module, and the orange line indicates the data flow of the
predictor module.

A spatiotemporal sequence of data can be represented as a length-$S$ sequence
$\mathcal{X}=\\{\mathcal{X}_{1},\mathcal{X}_{2},...,\mathcal{X}_{S}\\}$, each
$\mathcal{X}_{t}\in\mathbb{R}^{W\times H\times D},t=1,2,...,S$, means
$\mathcal{X}_{t}$ has dimensions of $H\times W$ and depth of $D$. The
spatiotemporal model is to use $\mathcal{X}$ to predict length-m sequence
${\mathcal{\tilde{X}}}=\\{\mathcal{\tilde{X}}_{1},\mathcal{\tilde{X}}_{2},...,\mathcal{\tilde{X}}_{T}\\}$
which is conitunous after $\mathcal{X}$. This means that the spatiotemporal
predictive learning can be expressed as an optimization problem with maximum
conditional probability:

${\mathcal{\tilde{X}}}=\mathop{\arg\min}\limits_{\mathcal{X}_{1}...,\mathcal{X}_{T}}p(\mathcal{X}_{1},...,\mathcal{X}_{T}\
|\mathcal{X})$ (1)

The structure of our proposed method is shown in Figure 1. In this paper,
instead of using the original sequence data as the input to the predictor, we
use the embedding
$\mathcal{Z}=\\{\mathcal{Z}_{1},\mathcal{Z}_{2},...,\mathcal{Z}_{S}\\},\text{where}\,\mathcal{Z}_{i}=\text{Encoder}(\mathcal{X}_{i}),i=1,2,...,S$.

In CNN, the size of the original image affects the number of convolutional
kernel slides, which in turn affects the computation speed. The new embedding
$\mathcal{Z}$ of the original image, is smaller than $\mathcal{X}$ in size
after encoder dimensionality reduction, and the number of convolution kernel
computations is reduced, thus improving the computational speed of the
predictor. On the other hand, $\mathcal{Z}$ contains richer features because
encoder superimposes the extracted features to the channel dimension of
$\mathcal{Z}$.

Thus, we turn the original task of predicting the embedding
$\mathcal{\tilde{X}}$ by $\mathcal{X}$ into predicting the embedding
$\mathcal{\tilde{Z}}$ from the embedding $\mathcal{X}$:

${\mathcal{\tilde{Z}}}=\mathop{\arg\min}\limits_{\mathcal{Z}_{1}...,\mathcal{Z}_{T}}p(\mathcal{Z}_{1},...,\mathcal{Z}_{T}\
|\mathcal{Z})$ (2)

###  III-B Spatial Encoder-Decoder

Spatial Encoder-Decoder encodes the data $\mathcal{X}_{i}$ to
$\mathcal{Z}_{i}$ at each time step in $\mathcal{X}$ by Encoder:

$\mathcal{Z}_{i}=\rm{Encoder}(\mathcal{X}_{i}),\mathcal{Z}_{i}\in\mathbb{R}^{H^{\prime}\times
W^{\prime}\times D^{\prime}}$ (3)

Then $\mathcal{Z}_{i}$ is transformed into a one-hot embedding through the
posterior distribution probability distribution.

$p(z=k|x)=\begin{cases}&1,\text{for}\,k=\arg\min_{j}{\|z_{e}(x)-e_{j}\|_{2}}\\\
&0,\text{otherwise}\end{cases}$ (4)

The nearest neighbor algorithm is used to obtain the potential encoding vector
of the corresponding index in the embedding table:

$z_{q}(x)=e_{k},\text{where}\,k=\arg\min_{j}\|z_{e}(x)-e_{j}\|_{2}$ (5)

Finally, the decoder is then used to reduce $z_{q}$ to a real-world image:

$\mathcal{\tilde{X}}_{i}=\text{Decoder}(\mathcal{\tilde{Z}}_{i})$ (6)

###  III-C Predictor

As mentioned in Section I, we use two different architectures, respectively
transformer-based and RNN-based models, to validate the approach proposed in
this paper. We have selected typical representatives of these two models,
which are PredRNN and TCTN, and they both achieve SOTA performance in most
metrics.

Figure 2: Architecture of PredRNN. The temporal memory $\mathcal{M}$ is passed
through the layers along the black arrows with time $t$ Temporal memory
$\mathcal{C}$ is passed horizontally in the same layer as time changes. The
hidden state $\mathcal{H}$ is passed along the zigzag direction in the model.

PredRNN. The model structure of PredRNN is shown in Figure 2. PredRNN is a
model of recurrent neural network architecture, where each recurrent layer
consists of multiple spatiotemporal LSTM units stacked. In PredRNN, a new
state variable $\mathcal{M}$ is defined in addition to the memory state
$\mathcal{C}$ and the hidden state $\mathcal{H}$ in the standard LSTM network.
$\mathcal{C}$ is a temporal memory unit that propagates with time $t$; The
hidden state $\mathcal{H}$ can be simultaneously passed along the horizontal
direction and passed up along the vertical direction. Meanwhile, in addition
to the input, forgetting and output gates in the standard LSTM, input
modulation gate $g^{\prime}$, input gate $i^{\prime}$ and forgetting gate
$f^{\prime}$ are introduced to update the spatiotemporal memory unit
$\mathcal{M}$, which is calculated as following:

$\begin{split}g_{t}&=\tanh(W_{xg}\ast\mathcal{X}_{t}+W_{hg}\ast\mathcal{H}_{t-1}^{l})\\\
i_{t}&=\sigma(W_{xi}\ast\mathcal{X}_{t}+W_{hi}\ast\mathcal{H}_{t-1}^{l})\\\
f_{t}&=\sigma(W_{xf}\ast\mathcal{X}_{t}+W_{hf}\ast\mathcal{H}_{t-1}^{l})\\\
\mathcal{C}_{t}^{l}&=f_{t}\odot\mathcal{C}_{t-1}^{l}+i_{t}\odot g_{t}\\\
g_{t}^{\prime}&=\tanh(W_{xg}^{\prime}\ast\mathcal{X}_{t}+W_{mg}\ast\mathcal{M}_{t}^{l-1})\\\
i_{t}^{\prime}&=\sigma(W_{xi}^{\prime}\ast\mathcal{X}_{t}+W_{mi}\ast\mathcal{M}_{t}^{l-1})\\\
f_{t}^{\prime}&=\sigma(W_{xf}^{\prime}\ast\mathcal{X}_{t}+W_{mf}\ast\mathcal{M}_{t}^{l-1})\\\
\mathcal{M}_{t}^{l}&=f_{t}^{\prime}\odot\mathcal{M}_{t}^{l-1}+i_{t}^{\prime}\odot
g_{t}^{\prime}\\\
o_{t}&=\sigma(W_{xo}\ast\mathcal{X}_{t}+W_{ho}\ast\mathcal{H}_{t-1}^{l}+W_{co}\ast\mathcal{C}_{t}^{l}+W_{mo}\ast\mathcal{M}_{t}^{l})\\\
\mathcal{H}_{t}^{l}&=o_{t}\odot\tanh(W_{1\times
1}\ast[\mathcal{C}_{t}^{l},\mathcal{M}_{t}^{l}]).\\\ \end{split}$ (7)

TCTN.The flow chart of TCTN calculation is shown in Figure 3. TCTN is a
transformer-based spatiotemporal sequence prediction model that uses 3D
convolutional operations instead of linear operations in the standard
transformer structure to compute correlations between spatiotemporal data.
Since the transformer is insensitive to the position of the sequence data, the
position information is represented by adding the position embedding
$P\in\mathbb{R}^{H^{\prime}\times W^{\prime}\times C^{\prime}}$ to the input
data, and $P$ is calculated as follows:

Figure 3: Overview of TCTN Model Architecture. The model can be considered as
a transformer decoder using 3D convolutional operations instead of linear
operations.

$\begin{split}P_{j,h,w,2d}&=\sin(j/10000^{2d/D}),\\\
P_{j,h,w,2d+1}&=\cos(j/10000^{2d/D}),\\\ E&=\mathcal{Z}+P\end{split}$ (8)

After getting the input $E$ with position embedding, it is fed to
Spatiotemporal Decoder to perform the prediction. Specifically, after first
layer normalizing E, the computation of the matrices $Q\in\mathbb{R}^{S\times
H^{\prime}\times W^{\prime}\times D^{\prime}}$, $K\in\mathbb{R}^{S\times
H^{\prime}\times W^{\prime}\times D^{\prime}}$ and $V\in\mathbb{R}^{T\times
H^{\prime}\times W^{\prime}\times D^{\prime}}$, and compute the scaled dot-
product attention matrix $A$.

$\begin{split}\hat{E}&=\text{LN}(E),\\\ Q&=W_{q}*\hat{E},\\\
K&=W_{k}*\hat{E},\\\ V&=W_{v}*\hat{E},\\\
A&=\text{Softmax}\bigg{(}\text{Mask}(\frac{QK^{T}}{\sqrt{D^{\prime}}})\bigg{)}V\end{split}$
(9)

The difference from the standard attention mechanism is that the parameter
matrices $W_{q}$, $W_{k}$, $W_{w}$ of TCTN are 3D convolutional kernels
instead of the weights of the linear layers. Then, $A$ is added to the
original input E by residual concatenation and layer normalized to obtain
$\hat{S}$, which is used as the input of a feed forward network(FFN) layer.
The feed forward network consists of two 3D convolutional layers and a leaky
relu activation function, and the final output predicts the encoding of the
spatiotemporal sequence $\mathcal{Z}$:

$\begin{split}\hat{A}&=\text{LN}(A)\\\ S&=E+\hat{A}\\\
\hat{S}&=\text{LN}(S)\\\
\tilde{\mathcal{Z}}&=W_{1}*(\text{LReLU}(W_{2}*\hat{S}))\end{split}$ (10)

$\text{LReLU}(\cdot)$ denotes the leaky relu activation function and both
$W_{1}$ and $W_{2}$ are 3D convolution kernels.

##  IV Experiments

Figure 4: Performance comparison of different models on MovingMNIST dataset.

###  IV-A Dataset

For fair comparison, we use the dataset used in both TCTN and PredRNN, they
are:

  * •

MovingMNIST: MovingMNIST is to randomly select one or more static handwritten
digital images from the MNIST handwritten digital dataset, and give these
numbers an initial change speed and angle, so that the numbers keep this speed
and angle in a certain range of motion, so as to generate a space-time
sequence. In this article, we are consistent with the data set used by
PredRNN[14] and TCTN[15]: the generated sequence of 10,000 is 20 frames, and
each frame is a 64$\times$ 64 gray-scale image, with the first 10 frames as
input and the last 10 frames as prediction targets.We then use a sequence of
5,000 lengths as the test set.

  * •

KTH-Action[20]: KTH-Action is a real-world dataset. It captures video
sequences of six different categories of actions performed by 25 people in
four different scenarios. The average length of the video sequences was 4
seconds, with a frame rate of 25FPS and a resolution of 160 $\times$ 120\. We
follow the same settings with [21]: utilizing people numbered 1-16 as the
training set, and the rest as the test set. Each frame is rescaled into a 128
$\times$ 128 grayscale image. A sample is a sequence of images containing 20
frames, with the first 10 frames as input and the last 10 frames as target.

###  IV-B Compared Metrics

We divide the experiments into two aspects: prediction quality comparison and
computational performance comparison.

To compare the generated data results, we keep the parameters of the original
model and our modified model the same, only the input data are changed. The
input data of the basic reference model are real images, while our modified
model, called PredRNN-modular or TCTN-modular, uses the latent embedding
$\mathcal{Z}$ generated by the encoder of VQ-VAE as input. We use the
following metrics to measure the quality:

  * •

Learned Perceptual Image Patch Similarity(LPIPS). This metric is used to
measure the difference between two images by learning the reverse mapping of
the generated image to Ground Truth, and forcing the generator to learn the
reverse mapping of reconstructing the real image from the fake image and
prioritizing the perceptual similarity between them[22]. LPIPS is more
consistent with human perception than traditional methods. A lower value of
LPIPS indicates that the two images are more similar.

  * •

Structural Similarity Index Measure (SSIM). SSIM measures image similarity in
terms of brightness, contrast and structure respectively. The bigger the SSIM,
the better the result.

In order to compare the computational performance of different models, we
fine-tune the original model by increasing the number of parameters, using the
LPIPS metrics in the MNIST dataset as a benchmark until the final prediction
is essentially the same as our model. Then we calculate the training
consumption (time required for training per 100 iterations, GPU memory usage)
and the total number of parameters for the model after tuning the parameters.

###  IV-C Implementation Detail

All basic models and predictors of modular models keep the same setup with
TCTN(6 decoder layers, self-attention head, 64 hidden units each layers) and
PredRNN (4 layers, each layer contains 64 hidden units) as controls, and train
each model for 70,000 iterations to choose the best.

####  IV-C1 MovingMNIST

Figure 5: Frame-wise LPIPS results on test set. Above: MovingMNIST. Both models using the method proposed in this paper perform better. Below: KTH-Action. Our method is effective on TCTN and comparable to the base model on PredRNN. However, the result generated by our method has a smoother variance. TABLE I: Quality of predictions on MovingMNIST dataset. MODEL | LPIPS(↓) | SSIM(↑)
---|---|---
PredRNN-base | 0.102 | 0.871
PredRNN-modular | 0.055 | 0.884
TCTN-base | 0.094 | 0.861
TCTN-modular | 0.077 | 0.859

The experiment results of the MovingMNIST dataset are shown in Table I and
Figure 4. In the MovingMNIST dataset, our improvements to both models achieve
significant improvements in the LPIPS metric. This indicates that the
spatiotemporal data generated using our approach has better human readability.
In terms of SSIM, the results are comparable to the original model.

TABLE II: Quality of predictions on KTH-Action dataset. MODEL | LPIPS(↓) | SSIM(↑)
---|---|---
PredRNN-base | 0.124 | 0.854
PredRNN-modular | 0.129 | 0.848
TCTN-base | 0.298 | 0.645
TCTN-modular | 0.155 | 0.832
Figure 6: Performance comparison of different models on KTH-Action dataset.

####  IV-C2 KTH-Action

The experiment result for the KTH-Action dataset are shown in the Figure 6 and
Table II. Differs from the MovingMNIST dataset in that the spatiotemporal
dynamics of the KTH-Action dataset vary relatively continuously and has more
noise and stochastic variation because it is a real-world picture. Therefore,
the modular approach propose in this paper has different effects on the two
model enhancements.

For PredRNN, the modular design do not significantly improve the basic model,
and all metrics for comparison are similar to the original model.

For TCTN, the base model cannot capture the relatively complex spatiotemporal
variations in KTH-Action well because the model is too simple. It should be
noted that in the original paper, the image size of the KTH-Action used is
$64\times 64$[15]. The modular design significantly enhances the effectiveness
of TCTN in small number of parameters and large sample size scenarios.

####  IV-C3 Computational Performance

TABLE III: Computational performance comparison.  MODEL | LPIPS | Params(M) | Mem(GB) | Training Cost(s)
---|---|---|---|---
PredRNN-large | 0.076 | 27.79 | 5.231 | 91.8
PredRNN-modular | 0.057 | 6.60 + 2.17 | 2.197 | 70.3
TCTN-large | 0.078 | 25.52 | 2.719 | 93.0
TCTN-modular | 0.077 | 7.00 + 2.17 | 2.234 | 39.5

We follow the setup in the previous section to compare the computational
performance of the models by testing the cost of the models when they are
trained on the MNIST dataset. By increasing the models until the original
model and our model achieve the same results on LPIPS. Finally, the number of
layers of PredRNN and TCTN remain the same and the hidden units per layer are
doubled, and the results are shown in the table III.

Mem contains the memory occupied by both the training data and the model
itself. Training cost indicates the time consumed per 100 iterations. All
experiments are conducted on a single NVIDIA Tesla V100 GPU with 32G memory.
In our model, the number of parameters denotes the sum of the parameters of
the pre-trained VQ-VAE model and the predictor parameters, e.g., 6.60 + 2.17
indicates that the number of predictor parameters is 6.60M and the number of
VQ-VAE parameters is 2.17M. The parameters of VQ-VAE are no longer updated
during training, so there is no need to calculate the gradient.

In terms of the number of parameters, the size of the modular models are
31.6%(PredRNN) and 35.9%(TCTN) of the original models, respectively. This
results in a 58.0% reduction in memory usage and a 23.4% improvement in
training speed for PredRNN during training. For TCTN, there are a 17.8%
reduction in memory usage and a 57.5% increase in training speed.

##  V Conclusion

In this paper, we propose a general method to enhance the performance of
existing spatiotemporal sequence prediction models: decomposing the model into
two separate parts, which are called spatial encoder-decoder and predictor. We
use a pre-trained VQ-VAE model as the spatial encoder-decoder. The output of
the encoder at VQ-VAE is used as the input of the predictor. Finally, real
world images are generated by the decoder of VQ-VAE.

In general, we obtain competitive results with the modular design. Some of the
metrics are improved significantly on different datasets. Typically, LPIPS
indicates that our method has better human readability in generating
prediction images and improves the prediction performance. The result on the
KTH-Action dataset shows that using a modular design is effective in improving
the performance of models that perform poorly on datasets with large sample
sizes.

There are many possible attempts at the spatial encoder-decoder, such as VAE,
or representation of ViT[23], etc. Meanwhile, more and more researches are
turning to big models[24] with massive parameters, the basic idea of this
paper is quite opposite to big models. We hope that the ideas in this paper
will lead to some new thinking about big models.

## References

  * [1] Z. Chang, X. Zhang, S. Wang, S. Ma, Y. Ye, X. Xinguang, and W. Gao, “Mau: A motion-aware unit for video prediction and beyond,” in _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 26 950–26 962.
  * [2] V. Le Guen and N. Thome, “Disentangling Physical Dynamics from Unknown Factors for Unsupervised Video Prediction,” _arXiv e-prints_ , p. arXiv:2003.01460, Mar. 2020.
  * [3] L. Zhao, Y. Song, C. Zhang, Y. Liu, P. Wang, T. Lin, M. Deng, and H. Li, “T-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Prediction,” _arXiv e-prints_ , p. arXiv:1811.05320, Nov. 2018.
  * [4] Q. Zhang, J. Chang, G. Meng, S. Xiang, and C. Pan, “Spatio-temporal graph structure learning for traffic forecasting,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, pp. 1177–1185, 04 2020.
  * [5] L. Cai, K. Janowicz, G. Mai, B. Yan, and R. Zhu, “Traffic transformer: Capturing the continuity and periodicity of time series for traffic forecasting,” _Transactions in GIS_ , vol. 24, 06 2020.
  * [6] A. McGovern, D. J. Gagne, J. K. Williams, R. A. Brown, and J. B. Basara, “Enhancing understanding and improving prediction of severe weather through spatiotemporal relational learning,” _Machine Learning_ , vol. 95, no. 1, pp. 27–50, Apr 2014.
  * [7] M. Jamaly and J. Kleissl, “Spatiotemporal interpolation and forecast of irradiance data using kriging,” _Solar Energy_ , vol. 158, pp. 407–423, 2017\.
  * [8] V. Aryai and M. Mahmoodian, “Spatial-temporal reliability analysis of corroding cast iron water pipes,” _Engineering Failure Analysis_ , vol. 82, pp. 179–189, 2017.
  * [9] X. Shi and D.-Y. Yeung, “Machine Learning for Spatiotemporal Sequence Forecasting: A Survey,” _arXiv e-prints_ , p. arXiv:1808.06865, Aug. 2018\.
  * [10] X. SHI, Z. Chen, H. Wang, D.-Y. Yeung, W.-k. Wong, and W.-c. WOO, “Convolutional lstm network: A machine learning approach for precipitation nowcasting,” in _Advances in Neural Information Processing Systems_ , C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, Eds., vol. 28. Curran Associates, Inc., 2015\.
  * [11] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , ser. NIPS’17. Red Hook, NY, USA: Curran Associates Inc., 2017, p. 6000–6010.
  * [12] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding,” _arXiv e-prints_ , p. arXiv:1810.04805, Oct. 2018.
  * [13] Z. Liu, S. Luo, W. Li, J. Lu, Y. Wu, S. Sun, C. Li, and L. Yang, “ConvTransformer: A Convolutional Transformer Network for Video Frame Synthesis,” _arXiv e-prints_ , p. arXiv:2011.10185, Nov. 2020.
  * [14] Y. Wang, H. Wu, J. Zhang, Z. Gao, J. Wang, P. Yu, and M. Long, “Predrnn: A recurrent neural network for spatiotemporal predictive learning,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. PP, pp. 1–1, 04 2022.
  * [15] Z. Yang, X. Yang, and Q. Lin, “TCTN: A 3D-Temporal Convolutional Transformer Network for Spatiotemporal Predictive Learning,” _arXiv e-prints_ , p. arXiv:2112.01085, Dec. 2021.
  * [16] A. van den Oord, O. Vinyals, and k. kavukcuoglu, “Neural discrete representation learning,” in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017.
  * [17] X. Shi, Z. Gao, L. Lausen, H. Wang, D.-Y. Yeung, W.-k. Wong, and W.-c. WOO, “Deep learning for precipitation nowcasting: A benchmark and a new model,” in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017.
  * [18] Z. Lin, M. Li, Z. Zheng, Y. Cheng, and C. Yuan, “Self-attention convlstm for spatiotemporal prediction,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 07, pp. 11 531–11 538, Apr. 2020.
  * [19] Y. Wang, J. Zhang, H. Zhu, M. Long, J. Wang, and P. S. Yu, “Memory in memory: A predictive neural network for learning higher-order non-stationarity from spatiotemporal dynamics,” in _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 9146–9154.
  * [20] C. Schuldt, I. Laptev, and B. Caputo, “Recognizing human actions: a local svm approach,” in _Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004._ , vol. 3, 2004, pp. 32–36 Vol.3.
  * [21] R. Villegas, J. Yang, S. Hong, X. Lin, and H. Lee, “Decomposing motion and content for natural video sequence prediction,” in _ICLR_ , 2017.
  * [22] R. Zhang, P. Isola, A. A. Efros, E. Shechtman, and O. Wang, “The unreasonable effectiveness of deep features as a perceptual metric,” in _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 586–595.
  * [23] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby, “An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale,” _arXiv e-prints_ , p. arXiv:2010.11929, Oct. 2020.
  * [24] W. Yan, Y. Zhang, P. Abbeel, and A. Srinivas, “VideoGPT: Video Generation using VQ-VAE and Transformers,” _arXiv e-prints_ , p. arXiv:2104.10157, Apr. 2021.