# A Novel Multi-Layer Framework for BVLoS Drone Operation: A Preliminary Study

Francesco Betti Sorbelli  Department of Computer Science and Mathematics,
University of Perugia, Italy  Punyasha Chatterjee  School of Mobile Computing
& Communication, Jadavpur University  Federico Corò  Department of Computer
Science and Mathematics, University of Perugia, Italy  Lorenzo Palazzetti
Department of Computer Science and Mathematics, University of Florence, Italy
Cristina M. Pinotti  Department of Computer Science and Mathematics,
University of Perugia, Italy

###### Abstract

Drones have become increasingly popular in a variety of fields, including
agriculture, emergency response, and package delivery. However, most drone
operations are currently limited to within Visual Line of Sight (VLoS) due to
safety concerns. Flying drones Beyond Visual Line of Sight (BVLoS) presents
new challenges and opportunities, but also requires new technologies and
regulatory frameworks, not yet implemented, to ensure that the drone is
constantly under the control of a remote operator. In this preliminary study,
we assume to remotely control the drone using the available ground cellular
network infrastructure. We propose to plan BVLoS drone operations using a
novel multi-layer framework that includes many layers of constraints that
closely resemble real-world scenarios and challenges. These layers include
information such as the potential ground risk in the event of a drone failure,
the available ground cellular network infrastructure, and the presence of
ground obstacles. From the multi-layer framework, a graph is constructed whose
edges are weighted with a dependability score that takes into account the
information of the multi-layer framework. Then, the planning of BVLoS drone
missions is equivalent to solving the Maximum Path Dependability Problem on
the constructed graph, which turns out to be solvable by applying Dijkstra’s
algorithm.

##  1 Introduction

Nowadays, Unmanned Aerial Vehicles (UAVs) or drones, or more generally
Unmanned Aerial Systems (UAS), are increasingly used in many applications and
are invoked to drive advanced air mobility (AAM) and urban air mobility [1]
(UAM). UAM is a subset of AAM that uses small automated aircraft to work at
low altitudes in urban and suburban areas. So far, only manned/unmanned ground
and manned aerial vehicles have been employed in these markets. However,
trucks are constrained by terrain and suffer from highly congested
infrastructures, while the use of planes is costly and unaffordable to most
people. Therefore, the use of UAS is a viable solution in many applications
[2] also because they do not emit greenhouse gases.

The operation of UAS is subdivided into categories depending on the risk of
the application. Operations with low risk do not require a prior authorization
before the flights, while operations with a higher risk require special
authorization. Currently, any operation that forces a drone to move Beyond
Visual Line of Sight (BVLoS) requires special authorization. To enable BVLoS
missions, there are currently many ways [3], e.g., by a NOtice To AirMen
(NOTAM) authorization, by Extended Visual Line of Sight (EVLoS) flights, or by
exploitation of “corridors” or “polygons”. A NOTAM isolates a certain area,
and the risk is lowered because only the authorized UAV operation can use that
area and all the facilities on the ground are aware of the drone’s presence.
An EVLoS flight emulates the BVLoS operation by connecting different VLoS
operators in series. Finally, exploitation of “corridors” (e.g., high-voltage
transmission lines) or “polygons” (e.g., fields), is the solution closest to
BVLoS flights in a low-risk scenario. However, these methods are artificial,
unflexible, and unfeasible to allow daily BVLoS flights in the immediate
future.

Figure 1: Big picture of our envisioned BVLoS scenario. The connectivity is
provided by the cellular infrastructure. The risk is present on the ground in
some areas. The UAV operator has a limited view and flies the drone in BVLoS
according to a certain trajectory.

To pursue flexible and scalable BVLoS flights, there are two big challenges:
risk and connectivity of the drone (see Figure 1). The ground risk depends on
the concentration of people over places in case of some malfunctioning [4].
The air risk depends on the presence of other drones in the area. In this
paper, we assume that we fly at the legal height limit of 120 $\mathrm{\,m}$,
which reduces the risk of coming across other aircraft, which normally fly
much higher than this limit. The presence of buildings, towers, and trees can
slightly mitigate the risk since they can act as shields or shelters [5], but
they also represent obstacles during the flight. A previous risk assessment
helps the UAVs to be aware in advance of the possible ground and air risks.
So, our goal is to build the UAVs’ risk awareness by leveraging ground maps
and consequently trying to limit the risks of UAV flight. Maps that describe
and constrain specific areas on the ground/air can be retrieved from many
providers, such as OpenStreetMap [6] or D-Flight [7].

Regarding connectivity, a UAV must communicate its position anytime so that
its route can be monitored by the ground, and possibly modified by providing
new tasks while receiving real-time updates from the UAV [8]. Connectivity is
indeed the way to extend the drone operation with the same level of
dependability guaranteed by the VLoS operations. Since thinking of deploying
an ad hoc infrastructure for communicating is not sustainable, it is realistic
to rely on already available ones like those used for ground users (cellular).
There are several generations of networks already deployed (e.g., 4/5G) that
can provide BVLoS links with different characteristics (e.g., bandwidth,
latency) [9] suitable for different types of UAVs, and types of applications
[10].

In this paper, we propose a novel multi-layer framework that includes
information from different layers like no-fly zones, obstacles, ground risk,
and communication infrastructure. Such layers are then discretized in order to
build a graph-based data structure which will be exploited by drone path
planning algorithms. The rest of the paper is organized as follows. Section 2
reviews the related work. Section 3 formally defines the multi-layer
framework, while Section 4 proposes the graph-based data structure for path
planning. Finally, Section 5 offers conclusions and future works.

##  2 Related Work

In this section, we describe the existing works on risk aware path planning
and handover management for UAVs flying BVLoS. We remark that none of the
works addresses the two factors simultaneously.

#### Risk Analysis and Path Planning

BVLoS operation involves a number of risks, including the potential for
collisions with other aircraft, loss of communication with the operator, and
failure of onboard sensors or systems. Primatesta et al. [4, 11, 12], propose
the use of a two-dimensional location-based Risk Map to define the risk to the
population caused by the crashing of the UAV. The risk map is generated using
a probabilistic approach and combines several layers, including population
density, sheltering factor, no-fly zones, and obstacles. The risk values are
defined by a risk assessment process using different uncontrolled descent
events, drone parameters, and environmental characteristics, as well as
uncertainties in parameters. By using the Risk Map, the authors propose an
optimum risk path based on Rapidly-exploring Random Tree (RRT*) and A*
algorithms. Note that in our work we included the risk map by Primatesta et
al. as one of the layers in the framework we presented.

The authors in [13] present a path planning algorithm that accommodates real-
time traffic and geofence constraints in low-altitude airspace BVLoS. Their
proposed algorithm integrates an RRT technique with Detect and Avoid Alerting
Logic. Similarly in [14], authors propose a methodology to analyze the
capacity of UAV corridors by linking the collision rate of the corridor and
the failure rates of UAVs with the number of fatalities on the ground.
Finally, the authors in [15] propose an optimization model to navigate an
aircraft to reach its destination by minimizing the maximum threat level and
the length of the flight path using a geometric procedure.

#### Cellular Communications and UAVs

One of the main technical challenges of BVLoS operations is maintaining a
reliable link between the drone and the operator. This is particularly
important to ensure that the operator can monitor the drone’s flight and
provide real-time guidance or take control if necessary. In fact, one of the
major goals in BVLoS flight is to keep high-quality radio communications.

One issue that can arise when using cellular networks for BVLoS communication
is the problem of handover. Handover refers to the process of transferring the
connection between the drone and the cellular network from one base station to
another as the drone moves through the coverage area. Handover is a critical
aspect of cellular communication, as it enables the drone to maintain a
continuous connection to the network when it flies. However, handover can also
be a challenge for BVLoS drones, as the drone may be flying at high speeds or
in areas with limited coverage, which can make it difficult to maintain a
stable connection.

Several studies have addressed the problem of handover for BVLoS drones. In
[16], authors study the performance of cellular-connected UAVs under 3D
practical antenna configurations. Their results reveal that vertically-mobile
UAVs are susceptible to altitude handover due to consecutive crossings of the
nulls and peaks of the antenna side lobes. The authors in [17] propose an
approximation of the probability mass function (PMF) of handover count (HOC)
as a function of the UAV’s velocity, HOC measurement time window, and ground
base station (GBS) densities. Furthermore, the authors in [18] contributed an
experimental study on cell association and handover rates for drones,
connected to an LTE-A (Long Term Evolution Advanced) network in a suburban
environment. Their experiments show that the handover frequency increases with
increasing flight altitude.

##  3 System Model

Let us consider a 3D environment bounded by a rectangular parallelepiped
(briefly, box, see Figure 2) denoted by $B$ characterized by a length $B_{L}$,
width $B_{W}$, and height $B_{H}$, that lies on the ground plane at height
$0$, with $B_{L}$, $B_{W}$, and $B_{H}\in\mathbb{R}^{+}$. Moreover, we
consider $B$ divided into a number of cubes (or cells) of the same side length
$\ell$, thus making a discrete approximation of the environment. We denote
each cube with its relative position from the origin with a tuple
$c=(x_{c},y_{c},z_{c})\in B$, where $x_{c}$, $y_{c}$, and $z_{c}\in\mathbb{N}$
are the $x$-coordinate, $y$-coordinate, and $z$-coordinate, respectively, of
$c$ in the discretized environment. For simplicity, we assume $B$ to be a flat
environment. In $B$, the cell $c=(x_{c},y_{c},1)$ lies at the lowest level at
a height $\ell$ above the ground. The sizes of $B$ are $n=\frac{B_{L}}{\ell}$,
$m=\frac{B_{W}}{\ell}$, and $h=\frac{B_{H}}{\ell}$, respectively, and so there
are $nmh$ cubes.

Since flying in BVLoS requires some essential and detailed information about
the surrounding environment in $B$, we propose a multi-layer framework in
which each layer contains useful data. Technically, a layer is a 2D matrix in
which each element is associated with a geo-referenced location, and has a
specific value depending on the type of layer. In this way, we can associate
each cube $c\in B$ with such information. In this work, the framework is
composed of the following layers.

  * •

Obstacle Layer: defines the height of buildings, trees, or other solid
obstacles on the terrain;

  * •

No-Fly zone Layer: defines the areas where drone flight is not allowed or
permitted;

  * •

Wireless infrastructure Layer: defines wireless connectivity in certain areas
with respect to the available cellular network infrastructure;

  * •

Risk-map Layer: defines the ground risk to people in the event that a drone
crashes in case of malfunctioning.

In the following, we describe the above four layers.

Figure 2: Example of the box $B$. A cell is highlighted in green, while
obstacles and no-fly zones are highlighted in yellow and red, respectively.
Notice that the no-fly zone occupies cells up to the maximum height.

###  3.1 Obstacle Layer

Obstacles such as buildings or trees occupy some cubes in $B$, where obviously
drones cannot fly. However, drones are free to fly over obstacles at a
sufficient height, and hence this layer is defined at multiple heights. In
general, the higher the drone altitude, the fewer obstacles will be
encountered. The cubes that include obstacles are not considered in $B$, and
therefore the number of cubes in $B$ is at most $nmh$.

###  3.2 No-Fly Zone Layer

No Fly-zones are areas where drone flight is forbidden, e.g., close to
airports and military warehouses. We assume that no-fly zones are effective at
any height. As before, the cubes that include no-fly zones are removed from
$B$.

###  3.3 Wireless infrastructure Layer

We assume that in the environment $B$ there is already a deployed wireless
network infrastructure that comprises a set of cellular towers. These towers
provide Internet connectivity (e.g., 4/5G) to ground users. Specifically, let
$T$ be a set of towers with a given discretized position
$t=(x_{t},y_{t},z_{t})\in B$. For simplicity, we assume that each tower $t\in
T$ is at ground level, so $z_{t}=1$. We also assume that there is no more than
one tower on each cube.

Drones can connect to these antennas if some physical constraints are met at
the same time. We have to distinguish between the transmitter device, i.e.,
the tower, and the receiver device, i.e., the drone. In this paper, we use the
Friis transmission equation (see Eq. (1)) in order to determine the quality of
the BVLoS communication link if a drone in cell $c$ establishes a connection
to a tower $t$, i.e., by evaluating:

$P_{W}(c,t)=P_{W}(t)\ G(t)\ G(c)\left(\frac{\lambda}{4\pi d_{S}}\right)^{2},$
(1)

where $P_{W}(c,t)$ is the receiving power at the drone, $P_{W}(t)$ is the
transmitting power of the tower, $G(t)$ and $G(c)$ are the antenna gains of
the transmitting and receiving devices, respectively, $\lambda$ is the
wavelength representing the effective aperture area of the receiving antenna,
and $d_{S}=\|c-t\|_{2}$ is the Euclidean slant distance that separates the
antennas.

Having said that, the wireless infrastructure layer is defined at multiple
heights, for multiple reasons. First, at different altitudes, the distance
$d_{S}$ in Eq. (1) varies, which in turn affects the received power at the
drone. Another aspect to take into account is the probability of being on the
Radio Line of Sight (briefly, LoS) which increases if the height of the drone
increases. Namely, the chances of being LoS increase with the relative
elevation angle between the drone and the tower. Not only the drone altitude
but also the presence of obstacles impact the LoS. So, when dealing with
obstacles, the chances of being LoS decrease if the density of obstacles
increases.

To wrap up, given two parameters $\alpha$ and $\beta$111The $\alpha$ and
$\beta$ parameters are called here the S-curve parameters, i.e., a modified
Sigmoid function. that model the surrounding environment (e.g., urban, rural)
by assuming that the drone is flying at the cell $c=(x_{c},y_{c},z_{c})$, the
probability to be LoS with the tower $t=(x_{t},y_{t},1)$ is defined as [19]:

$\mathcal{P}_{\text{LoS}}(c,t)=\frac{1}{1+\alpha\
e^{-\beta(\arctan{\frac{z_{c}}{d_{G}}}-\alpha)}}$ (2)

So, the higher the altitude, the longer the distance $d_{S}$, the less will be
the received power $P_{W}(c,t)$ by Eq. (1), and the less will be the quality
of the BVLoS link. But, at a higher altitude, a drone can potentially detect
more towers due to its increased elevation. Finally, given both $c$ and $t$,
let

$\mathcal{L}(c,t)=\mathcal{P}_{\text{LoS}}(c,t)\ P_{W}(c,t)$ (3)

be the link-reliability function that returns the product among the
probability of being LoS, and the normalized received power at the drone.
Potentially, there is an edge between $(c,t)$ as long as $\mathcal{L}(c,t)>0$.

For a given cell $c=(x_{c},y_{c},z_{c})\in B$, let $s(z_{c})=1+2z_{c}$. To
simplify our multi-layer model, from now on we assume that the probability of
LoS, i.e., $\mathcal{P}_{\text{LoS}}(c,t)$, is null or negligible for all
towers outside a square of size $s(z_{c})\times s(z_{c})$. Thus, when
$z_{c}=1$, $s(z_{c})=3$; while when $z_{c}=2$, $s(z_{c})=5$. In general, the
square sides depend on the $\alpha$ and $\beta$ parameters, but currently, we
omit the dependency. Formally, let $f_{T}(c)$ be the subset of towers that the
drone can see when it flies inside the cell $c$, i.e., the towers that belong
to the square of size $s(z_{c})$ centered in $c$, as represented in Figure 4.
Precisely

$\displaystyle f_{T}(c=(x_{c},y_{c},z_{c})):=\bigcup_{t\in T}(x_{t},y_{t},1),$
(4)

where $T$ consists of cells $(x_{t},y_{t},1)$ such that $x_{c}-z_{c}\leq
x_{t}\leq x_{c}+z_{c}$ and $y_{c}-z_{c}\leq y_{t}\leq y_{c}+z_{c}$. Under the
above simplification, we assume that a drone in cell $c$ can communicate with
any tower $t\in f_{T}(c)$ with a receiving power $P_{W}(c,t)$ determined
according to Eq. (1). For any $t\not\in f_{T}(c)$, there is no connection
between the drone and the tower. Note that $f_{T}(c)$ increases with the cell
height. Moreover, we normalize the value $P_{W}(c,t)$ in the interval $[0,1]$
where $P_{W}(c,t)=1$ represents the maximum received power at the drone, i.e.,
when the drone and the tower share the same position $c=t$. Notice that
$0\leq\mathcal{L}(c,t)\leq 1$.

###  3.4 Risk-map Layer

The risk-map layer models the potential risks that unexpected events can cause
to ground people. In this paper, we do not consider air risk, i.e., the
collision with other flying vehicles (manned or unmanned). The ground risk-map
layer specifically evaluates the risk on the ground depending on a
concatenation of different probabilities. Given a cell $c\in B$, the risk [12]
is defined as follows:

$\mathcal{R}(c)=\mathcal{P}_{\text{event}}(c)\ \mathcal{P}_{\text{impact}}(c)\
\mathcal{P}_{\text{fatality}}(c)$ (5)

where $\mathcal{P}_{\text{event}}$ is the probability that the drone crashes
on the ground; $\mathcal{P}_{\text{impact}}$ is the probability to impact a
person when the drone crash on the ground; and $\mathcal{P}_{\text{fatality}}$
is the probability to produce fatal injuries after a person has been impacted.

In the next section, exploiting the presented multi-layer framework, we will
create a suitable graph-based data structure used to solve our problem.

##  4 The Graph Model

In this section, our aim is to provide a graph-based data structure that can
be exploited by path planning algorithms.

###  4.1 Path Dependability

After we have presented the multi-layer framework, which is at the basis of
our BVLoS flight of drones, and before constructing the graph, we need to
introduce some fundamental prerequisites. The graph we will create has
vertices and edges. The vertices represent “locations” or “locations
associated with a tower”, while the edges represent “movements between
adjacent cells” or “tower handovers”. The graph is also weighted, where the
weight of each edge represents its dependability. In this paper, we combine
the information from the multi-layer framework that forms the path
dependability. More formally, the path dependability jointly takes into
account the ground-safeness, the link-reliability, and the handover-success-
rate. For us, the term dependability means the quality of being trustworthy
and reliable, and therefore we measure it through a probability, i.e., the
larger the probability, the more the path dependability.

So, ground-safeness, link-reliability, and handover-success-rate are
individual probabilities to combine in order to obtain the path dependability.
Consider an edge that enters the cell $c^{\prime}$ associated with the tower
$t$ and exits the cell $c$ associated with the tower $t$. Intuitively, the
ground-safeness represents the dependability of the link with respect to the
ground and the possible related safety risks. It is defined as
$\mathcal{P}_{\text{GS}}(c^{\prime},t)=1-\mathcal{R}(c^{\prime})$, where
$\mathcal{P}_{\text{GS}}(c^{\prime},t)=0$ represents the highest risk, while
$\mathcal{P}_{\text{GS}}(c^{\prime},t)=1$ does not represent risk. The link-
reliability is simply
$\mathcal{P}_{\text{LR}}(c^{\prime},t)=\mathcal{L}(c^{\prime},t)$, which
combines the probability to be in LoS, and the normalized received power at
the drone. To summarize, the edge that represents a movement between the two
cells has weight $\mathcal{P}=\mathcal{P}_{\text{GS}}(c^{\prime},t)\
\mathcal{P}_{\text{LR}}(c^{\prime},t)$, i.e., the product among the ground-
safeness, and the link-reliability of the destination cell.

Finally, we assume that the Handover-Success-Rate (HSR) is a value
$\mathcal{P}_{\text{HSR}}\in\\{\frac{1}{2},1\\}$, where
$\mathcal{P}_{\text{HSR}}=1$ represents the fact that the drone does not
change the tower, continuing communication with the same tower $t$, while
$\mathcal{P}_{\text{HSR}}\ =\frac{1}{2}$ represents the scenario when the
drone changes the connection with another nearby tower $t^{\prime}$. In this
latter case, we assume that something can go wrong, and hence the HRS is fixed
to $\frac{1}{2}$. A more complex HSR probability can be utilized in our model,
which depends on the $\mathcal{P}_{\text{LoS}}$ and $\mathcal{P}_{\text{LR}}$
parameters. Therefore, the edge that represents a tower handover has weight
$\mathcal{P}=\mathcal{P}_{\text{HSR}}$.

During a drone mission, the drone moves from a source to a destination and
traverses a path consisting of several edges. The path dependability is given
by the product of the weights of the traversed edges.

###  4.2 Graph Construction

Let $G=(V,E)$ be the weighted directed graph which is defined by a set $V$ of
vertices and a set $E$ of edges, which is built from the box $B$. Recall that
the box $B$ does not include either obstacle or no-fly zones. We build the
graph $G$ as follows. For each cell $c\in B$, we create a vertex called
$v_{c}$ that represents the cell $c$, plus $|f_{T}(c)|$ additional vertices to
represent the towers to which it is possible to connect from $c$, denoted as
$v_{c}^{t}$. So, the set of vertices is $V=\\{v_{c}:c\in
B\\}\cup\\{v_{c}^{t}:t\in f_{T}(c)\ \forall c\in B\\}$, while the set of edges
$E$ is a bit more complicated. In general, there are two types of edges:
intra-edges (i.e., tower handover) and inter-edges (i.e., moves between
adjacent cells). An intra-edge is in the form of $(v_{c},v_{c}^{t})\in E$,
while an extra-edge is in the form of $(v_{c}^{t},v_{c^{\prime}}^{t})\in E$.

Figure 3: Example of adjacent locations.

With regard to the intra-edges, these are used to connect a drone located at a
given cell to all the possible visible towers in that cell. For each
$v_{c}^{t}\in V$ we add a directed edge $(v_{c}^{t},v_{c})\in E$ with cost
$\mathcal{P}_{\text{HSR}}=1$, and a directed edge $(v_{c},v_{c}^{t})\in E$
with cost $\mathcal{P}_{\text{HSR}}=\frac{1}{2}$ (Algorithm 1, Line 1).
Crossing this latter edge represents the drone changing the connection to a
different tower. Note that we could have used the opposite manner, but the
graph construction guarantees that the handover is only paid once. The
pseudocode of the graph construction is reported in Algorithm 1.

1 for  _$c\in B$_ do

2 create vertex $v_{c}$

3 for  _$t\in f_{T}(c)$_ do

4 create vertex $v_{c}^{t}$

// intra-edges

5 add edge $(v_{c},v_{c}^{t})$ with cost
$\mathcal{P}_{\text{HSR}}=\frac{1}{2}$

6 add edge $(v_{c}^{t},v_{c})$ with cost $\mathcal{P}_{\text{HSR}}=1$

7

8

9for  _$c\in B$_ do

10 for  _$c^{\prime}\in Adj(c)$_ do

11 for  _$t\in f_{T}(c)\cap f_{T}(c^{\prime})$_ do

// inter-edges

12 add edge $(v_{c}^{t},v_{c^{\prime}}^{t})$ with cost
$\mathcal{P}_{\text{LR}}(c^{\prime},t)\ \mathcal{P}_{\text{GS}}(c^{\prime})$

13 add edge $(v_{c^{\prime}}^{t},v_{c}^{t})$ with cost
$\mathcal{P}_{\text{LR}}(c,t)\ \mathcal{P}_{\text{GS}}(c)$

14

15

16

Algorithm 1 Graph Construction

With regard to the inter-edges, these are used when the drone moves between
adjacent locations. Given $c=(x_{c},y_{c},z_{c})\in B$, let $Adj(c)$ be the
set of adjacent cells of $c$ where
$Adj(c):=\\{c^{\prime}=(x_{c^{\prime}},y_{c^{\prime}},z_{c^{\prime}})\neq
c:x_{c^{\prime}}=x_{c}\pm\\{0,1\\},y_{c^{\prime}}=y_{c}\pm\\{0,1\\},z_{c^{\prime}}=z_{c}\pm\\{0,1\\}\\}$.
So, as illustrated in Figure 3, $\max|Adj(c)|=26$. For each neighbor of $c\in
B$, i.e., $\forall c^{\prime}\in Adj(c)$, we connect pairs of vertices that
represent the same tower $t$ in the two different cells $c$ and $c^{\prime}$,
i.e., the towers in $t\in f_{T}(c)\cap f_{T}(c^{\prime})$. For each of these
pairs, we add a directed edge $(v_{c}^{t},v_{c^{\prime}}^{t})\in E$ with cost
$\mathcal{P}_{\text{LR}}(c^{\prime},t)\ \mathcal{P}_{\text{GS}}(c^{\prime})$,
and a directed edge $(v_{c^{\prime}}^{t},v_{c}^{t})\in E$ with cost
$\mathcal{P}_{\text{LR}}(c,t)\ \mathcal{P}_{\text{GS}}(c)$ (Line 1). Crossing
these edges represents the drone moving, e.g., from the cell $c$ to
$c^{\prime}$, thus considering the ground-safeness and the link-reliability of
the coming cell.

Figure 4: Example of subgraph with $3$ cells, i.e., $c=(2,3)$ (yellow),
$c=(3,3)$ (blue), and $c=(3,2)$ (red); and $h=1$. The grid on top represents
the cells along the two dimensions. Solid edges and dashed edges represent the
intra-edges and the inter-edges, respectively.

An example of the graph construction is reported in Figure 4. The yellow
vertex in position $(2,3)$ has $8$ neighbors, i.e., the ones inside the green
highlighted square. Moreover, there are $3$ towers, i.e., $t_{a}$, $t_{b}$,
and $t_{c}$. Among these, only $t_{a}$ and $t_{b}$ are in range with position
$(2,3)$, and therefore intra-edges from $v_{2,3}$ are only created between
$v_{2,3}^{a}$ and $v_{2,3}^{b}$. The blue cell is in position $(3,3)$ which is
in range with all the $3$ towers. As we can see, both $v_{2,3}$ and $v_{3,3}$
share the towers $t_{a}$ and $t_{b}$, and hence inter-edges between
$v_{2,3}^{a}$ and $v_{3,3}^{a}$, and $v_{2,3}^{b}$ and $v_{3,3}^{b}$, are
created. The same construction can be repeated for the red cell in $(3,2)$.

Note that by decoupling the tower handover from the movements between adjacent
cells, the number of edges decreases. Recall that at level $1\leq i\leq h$,
the drone can see at most $|T_{i}|=(1+2i)^{2}$ towers and $\max|Adj(c)|=26$.
Also, let $T_{\max}=\max|T_{i}|$. In our construction, instead of preparing an
edge ad hoc for each pair $v_{c}^{t}=(c,t)$ to
$(v_{c^{\prime}}^{t^{\prime}}=(c^{\prime},t^{\prime})$, we first move from
$(c,t)$ to $(c,t^{\prime})$, and then from $(c,t^{\prime})$ to
$(c^{\prime},t^{\prime})$. Without the decoupling, $(c,t)$ would have had
$\mathcal{O}(26\times T_{\max})$ outgoing edges. With the proposed decoupling,
$(c,t)$ has $\mathcal{O}(T_{\max})$ intra-edges plus $\mathcal{O}(26)$ inter-
edges. Thus, the graph construction has been strongly improved by decoupling
the tower handover and the cell movement.

With our assumptions, the box $B$ has $\mathcal{O}(nmh)$ cells and
$\mathcal{O}(nmh)$ overall inter-edges. So, the number $|V|$ of vertices of
the graph $G$ is upper-bounded by $|V|\leq
nmh+\sum_{i=1}^{h}{|T_{i}|nm}=\mathcal{O}(nmh^{3})$. With regard to the edges,
we can upper bound $|E|\leq
2\sum_{i=1}^{h}{T_{i}nm}+2\sum_{i=1}^{h}{26T_{i}nm}$, where the first
summation refers to the intra-edges, while the second summation refers to the
inter-edges (note the multiplicative factor $2$ that creates the two directed
edges). In conclusion, $|V|\in\mathcal{O}(nmh^{3})$, and
$|E|\in\mathcal{O}(nmh^{3})$.

The constructed graph represents the multi-layer framework and models any
drone mission by a path whose weight is its dependability.

###  4.3 Problem Formulation and Solution

Given a box $B$, the multi-layer framework, a starting and a destination cell
$s,g\in B$ respectively, and built the weighted dependability graph $G=(V,E)$,
we are in position for solving the Maximum Path Dependability Problem (MPDP)
whose objective is to find a drone’s path $\pi^{*}$ that starts in $s$ and
finishes in $g$ such that the dependability of
$\pi=\\{(s,\cdot),\ldots,(\cdot,g)\\}$ is maximized. Formally,

$\displaystyle\pi^{*}$
$\displaystyle=\operatorname*{arg\,max}_{\pi}{\prod_{e\in\pi}\mathcal{P}(e)}$
(6) To maximize Eq. (6) is the same as switching to exponentiation and
maximizing the argument of the $\log$ operation in Eq. (7),
$\displaystyle\pi^{*}$
$\displaystyle=\operatorname*{arg\,max}_{\pi}{\log\left(\prod_{e\in\pi}\mathcal{P}(e)\right)}$
(7)
$\displaystyle=\operatorname*{arg\,max}_{\pi}{\sum_{e\in\pi}\log\left(\mathcal{P}(e)\right)}$
(8) which is the same as minimizing Eq. (9) since all the addends are negative
$\displaystyle=\operatorname*{arg\,min}_{\pi}{\sum_{e\in\pi}|\log\left(\mathcal{P}(e)\right)|}$
(9)

Thus, the original objective to find the maximum probability path is
equivalent to finding the minimum shortest path where each edge weight
(probability) is replaced by the absolute value of its logarithm, and the path
cost is the sum of the edge weights. We remark that the above graph
construction enables standard path planning algorithms, such as Dijkstra’s
algorithm, to retrieve the optimal path for the drone to traverse in the area
prioritizing both safety and communication reliability, and thus enabling the
BVLoS operation.

So our problem is polynomially solvable in $|E|$. Moreover, our model is
flexible because by changing the path dependability we can find paths that
optimize different criteria. For example, focusing on the reliability of the
communication and posing all $\mathcal{P}_{\text{GS}}=1$, MPDP find the path
that maximizes the connectivity issues. Similarly, fixing
$\mathcal{P}_{\text{LR}}=\mathcal{P}_{\text{HSR}}=1$, MPDP will find the path
with minimum ground risk. Or, just preserving $\mathcal{P}_{\text{HSR}}$ (and
$\mathcal{P}_{\text{LR}}=\mathcal{P}_{\text{GS}}=1$), $\pi^{*}$ optimizes the
number of handovers.

##  5 Conclusion and Next Steps

In this paper, we presented a new framework for the operation of drones BVLoS
based on real-world scenarios and challenges. Our framework takes into account
ground risk and obstacles while ensuring a constant communication link between
the drone and the operator. Furthermore, we provide a polynomial graph
construction that enables simple path planning algorithms for BVLoS flight.

There are several directions for future work that could build on our framework
for BVLoS drone operation. One potential area of research is the development
of new efficient algorithms for specific sub-problems. For example, algorithms
that can ensure the communication link when the path is already given as
input, or algorithms that can handle dynamic scenarios where the ground risk
may change during the flight or a communication transfer between towers fails.
Also the exploration of specific real-world scenarios and applications for
BVLoS operation is interesting. This could include the use of BVLoS drones for
agriculture, emergency response, or package delivery, and involve the
development of case studies or pilot projects to demonstrate the feasibility
and benefits of BVLoS operation in these contexts. Overall, there is
significant potential for BVLoS drone operation to revolutionize a variety of
fields and applications, and our framework provides a starting point for
further research and development in this area.

## References

  * [1] Airbus, “Urban Air Mobility,” www.airbus.com.
  * [2] G. Capomasi, “Advanced air mobility – italian market study & recommendations for the national ecosystem,” www.romadrone.it.
  * [3] EASA, “UAS - Unmanned Aircraft Systems,” www.easa.europa.eu.
  * [4] S. Primatesta, G. Guglieri, and A. Rizzo, “A risk-aware path planning strategy for uavs in urban environments,” _Journal of Intelligent & Robotic Systems_, vol. 95, no. 2, pp. 629–643, 2019.
  * [5] M. Milano, S. Primatesta, and G. Guglieri, “Air risk maps for unmanned aircraft in urban environments,” in _Intl. Conf. on Unmanned Aircraft Systems (ICUAS)_. IEEE, 2022.
  * [6] OpenStreetMap, www.openstreetmap.org.
  * [7] D-Flight, www.d-flight.it.
  * [8] Y. Aydin, G. K. Kurt, E. Ozdemir, and H. Yanikomeroglu, “Authentication and handover challenges and methods for drone swarms,” _IEEE Journal of Radio Frequency Identification_ , 2022.
  * [9] G. Vallero, M. Deruyck, M. Meo, and W. Joseph, “Base station switching and edge caching optimisation in high energy-efficiency wireless access network,” _Computer Networks_ , vol. 192, 2021.
  * [10] D. Renga and M. Meo, “Can high altitude platforms make 6g sustainable?” _IEEE Communications Magazine_ , 2022.
  * [11] S. Primatesta _et al._ , “A risk-based path planning strategy to compute optimum risk path for unmanned aircraft systems over populated areas,” in _ICUAS_. IEEE, 2020, pp. 641–650.
  * [12] S. Primatesta, A. Rizzo, and A. la Cour-Harbo, “Ground risk map for unmanned aircraft in urban environments,” _Journal of Intelligent & Robotic Systems_, vol. 97, no. 3, pp. 489–509, 2020.
  * [13] S. Balachandran _et al._ , “A path planning algorithm to enable well-clear low altitude uas operation beyond visual line of sight,” in _Air Traffic Management Research and Development Seminar_. sn, 2017, p. 26.
  * [14] Y. Kim and J. Bae, “Risk-based uav corridor capacity analysis above a populated area,” _Drones_ , vol. 6, no. 9, p. 221, 2022.
  * [15] A. V. Savkin and H. Huang, “The problem of minimum risk path planning for flying robots in dangerous environments,” in _2016 35th Chinese Control Conference (CCC)_. IEEE, 2016, pp. 5404–5408.
  * [16] R. Amer, W. Saad, B. Galkin, and N. Marchetti, “Performance analysis of mobile cellular-connected drones under practical antenna configurations,” in _ICC 2020_. IEEE, 2020, pp. 1–7.
  * [17] M. M. U. Chowdhury, P. Sinha, and I. Güvenç, “Handover-count based velocity estimation of cellular-connected uavs,” in _2020 IEEE 21st International Workshop on SPAWC_. IEEE, 2020, pp. 1–5.
  * [18] A. Fakhreddine, C. Bettstetter _et al._ , “Handover challenges for cellular-connected drones,” in _Proceedings of the 5th Workshop on Micro Aerial Vehicle Networks, Systems, and Applications_ , 2019, pp. 9–14.
  * [19] A. Al-Hourani, S. Kandeepan, and S. Lardner, “Optimal lap altitude for maximum coverage,” _IEEE Wireless Communications Letters_ , vol. 3, no. 6, pp. 569–572, 2014.