Open AccessArticle

Internet of Unmanned Aerial Vehicles—A Multilayer Low-Altitude Airspace Model for Distributed UAV Traffic Management

Nader Samir Labib

^1,*

Grégoire Danoy

^1,2,*

Jedrzej Musial

³,

Matthias R. Brust

and

Pascal Bouvry

^1,2

SnT—University of Luxembourg, L-4364 Esch–Sur–Alzette, Luxembourg

FSTC—CSC ILIAS, University of Luxembourg, L-4364 Esch–Sur–Alzette, Luxembourg

Institute of Computing Science, Poznań University of Technology, 60–965 Poznań, Poland

Authors to whom correspondence should be addressed.

Sensors 2019, 19(21), 4779; https://doi.org/10.3390/s19214779

Submission received: 30 September 2019 / Revised: 27 October 2019 / Accepted: 31 October 2019 / Published: 3 November 2019

(This article belongs to the Special Issue UAV-Based Applications in the Internet of Things (IoT))

Download

Browse Figures

Figure 1
Role of unmanned aerial vehicle (UAV) within Internet of Things (IoT) as: (a) smart terminal devices that interact with the physical world; (b) aerial base stations and gateways; (c) communication network connected to IoT cloud. "> Figure 2
UAV traffic management (UTM) facilitating communication between main stakeholders [<a href="#B22-sensors-19-04779" class="html-bibr">22</a>]. "> Figure 3
Proposed multilayer UTM model of the Class G airspace [<a href="#B22-sensors-19-04779" class="html-bibr">22</a>]. "> Figure 4
Total System Error of a UAV [<a href="#B22-sensors-19-04779" class="html-bibr">22</a>]. "> Figure 5
Airways and Nodes in proposed UTM model [<a href="#B22-sensors-19-04779" class="html-bibr">22</a>]. "> Figure 6
Communicated messages in a distributed and centralised UTM [<a href="#B15-sensors-19-04779" class="html-bibr">15</a>]. "> Figure 7
Example of a 75-Node three layer network and its adjacency matrix. "> Figure 8
Impact on traffic performance by varying <math display="inline"><semantics> <msub> <mi>p</mi> <mrow> <mi>r</mi> <mi>e</mi> <mi>r</mi> <mi>o</mi> <mi>u</mi> <mi>t</mi> <mi>i</mi> <mi>n</mi> <mi>g</mi> </mrow> </msub> </semantics></math> in GPD (50%, 80%, 100%). "> Figure 9
Impact on mixed objective traffic performance by varying <math display="inline"><semantics> <msub> <mi>p</mi> <mrow> <mi>r</mi> <mi>e</mi> <mi>r</mi> <mi>o</mi> <mi>u</mi> <mi>t</mi> <mi>e</mi> </mrow> </msub> </semantics></math> in GPD (50%, 80%, 100%). "> Figure 10
Impact on traffic performance by varying <math display="inline"><semantics> <mrow> <msub> <mi>T</mi> <mi>l</mi> </msub> <mi>i</mi> <mi>m</mi> </mrow> </semantics></math> in Local Pheromone Guided (LPG) (80%, 50%, 0%). "> Figure 11
Performance comparison of Global Offline Static (GOS), GPD and LPG. ">

Versions Notes

Abstract

The rapid adoption of Internet of Things (IoT) has encouraged the integration of new connected devices such as Unmanned Aerial Vehicles (UAVs) to the ubiquitous network. UAVs promise a pragmatic solution to the limitations of existing terrestrial IoT infrastructure as well as bring new means of delivering IoT services through a wide range of applications. Owning to their potential, UAVs are expected to soon dominate the low-altitude airspace over populated cities. This introduces new research challenges such as the safe management of UAVs operation under high traffic demands. This paper proposes a novel way of structuring the uncontrolled, low-altitude airspace, with the aim of addressing the complex problem of UAV traffic management at an abstract level. The work, hence, introduces a model of the airspace as a weighted multilayer network of nodes and airways and presents a set of experimental simulation results using three UAV traffic management heuristics.

Keywords:

Internet of Things; traffic management; autonomous unmanned aerial vehicles; low-altitude airspace; multilayer networks

1. Introduction

Characterised as a mega-network of heterogeneous technologies and standards, Internet of Things (IoT), broadly refers to a network of uniquely addressable, interconnected objects, built on standard communication protocols whose point of convergence is the internet [1]. The fundamental idea behind IoT lies in connecting, both, virtual and physical everyday objects, thus enabling a wide array of services that were otherwise deemed unfeasible to be realised.

The widespread of IoT has, therefore, motivated the advancement in information communication technologies, catalysing the development and integration of new devices to this ubiquitous network. One promising category of devices that recently found its way into IoT, is Unmanned Aerial Vehicles (UAVs). The miniaturisation of lightweight, low energy consumption, wireless sensors has led to the rapid advancement in UAV technologies. In turn, promising new means of efficiently collecting and transmitting data as smart terminal devices capable of interacting with the physical world for a magnitude of IoT applications. Some predominant examples include smart agriculture [2,3], smart logistics [4], smart healthcare [5] and monitoring, surveillance and disaster management [6,7,8,9]. Nevertheless, UAVs promise a pragmatic solution to the limitations of existing terrestrial IoT infrastructure that, in some cases, would not be economically feasible nor sufficient to guarantee communication coverage with an acceptable level of quality [10]. Hence, making aerial technologies, such as UAVs a promising solution where they can contribute to overcoming such limitations by offering wider coverage, better availability and higher resilience when equipped with the appropriate sensory payload [11,12]. Figure 1, based on the International Organisation for Standardisation (ISO) and the International Electrotechnical Commission’s (IEC) IoT reference architecture published in ISO/IEC 30141 [13], illustrates some examples of potential roles for UAVs within IoT.

As research and industry continue to find more uses for UAVs [14], it is reasonable to envision a near future where heterogeneous swarms of UAVs would dominate the low-altitude airspace, operating beyond direct line of sight, hence, making their safe operation and management a critical research challenge. One viable solution is a dedicated UAV Traffic Management (UTM) system [15], an infrastructure building upon IoT concepts, such as its layered design, to complement conventional Air Traffic Management (ATM) by facilitating data exchange between UAVs as well as different stakeholders, as illustrated in Figure 2. However, in comparison to Air Traffic Management (ATM), UAV Traffic Management (UTM) introduces new research challenges with UAVs’ higher degree of mobility and energy limitations. Recently becoming an important research topic, with the expected large airspace traffic demand, dynamic geo-fencing and intrusion detection requirements, the currently under-development constructs, like NASA UTM [16] and EU U-Space [17] to name a few, will eventually face limitations in scalability and resilience due to their ATM–comparable centralised architecture. On the contrary, a distributed UTM relying on local decisions and ad-hoc UAV-to-UAV and UAV-to-infrastructure communications would reduce latency by allowing UAVs to exchange the more frequent awareness messages directly as explained in Reference [15], utilising paradigms such as multi-access edge computing [18]. Hence, achieving scalability and better resilience [19].

A mandatory first step towards a distributed UTM is to design and model the low-altitude airspace as its structure will have a significant role in air traffic management. This is emphasised in Referebces [20,21] where authors investigate the impact of the airspace structure and capacity for traffic densities.

This work builds on the foundations laid in our previous work [22] where we addressed the aforementioned, complex problem of UAV traffic management at an abstract level by proposing a structure for the uncontrolled low-altitude airspace; presented as a weighted multilayer network of nodes and airways. The main contribution of this paper, therefore is extending [22] by:

emphasising on the role of UAVs within IoT;
providing a broader state of the art analysis;
extending the UTM model description with UAV communication;
considering more realistic experimental scenarios.

The remainder of this work is structured as follows. Section 2 discusses the state of the art on multilayer networks, UAV traffic management and distributed path planning. Section 3 describes the proposed multilayer low-altitude airspace model followed by a corresponding optimisation problem and resolution approaches in Section 4. Section 5 explains our experimental setup and results analysis. Finally, Section 6 concludes the work and presents future research directions.

2. State of the Art

This section first presents the related work in multilayer networks as the groundwork on which our model is based, followed by a discussion on recent UTM developments and autonomous robot path planning. At the end of each subsection we emphasise our contributions to the literature.

2.1. Multilayer Networks

One particularly useful way to study complex systems is by analysing the networks that encode the interactions among the system’s elements. However the complexity of some real systems is such that it is not possible to study them as single layer networks. To account for this complexity, a more general framework, known as multilayer networks is considered. Over the recent years, research in physics and computer science developed different notions and models for complex networks referred to as networks of networks [23], multilayer social networks [24] and interconnected networks [25] to name a few. Literature provides many applications for such systems in ecology [26], biology [27], economic applications [28] and game theory [29] but what interests us most are those addressing transportation [30].

Transportation systems are one distinct example of systems where the multilayer formulation arises in a natural way [30] as there can be multiple modes of transport between given locations. This can be represented as a multilayer network where each layer is a representation of one mode of transportation forming an already complex network. Different segments, later referred to as paths, can have very different properties such as allowable velocity, energy consumption or traffic capacity and it is thus necessary to distinguish each of them when studying the whole system [30]. A similar multilayer representation is used in aerial transportation systems such as in Reference [31] where the authors built the European air transport multilayer network having each network layer represent an airline. Similarly, References [32,33,34] analyse, respectively, the Greek and Chinese airline transportation networks using the same aforementioned framework.

Our main contribution is expanding a similar methodology to represent the structure of the low-altitude airspace—Class G—as a multilayer network which, to the best of our knowledge, has never been proposed in the air traffic management literature.

2.2. UAV Traffic Management

With the evolution of wireless sensor networks and the potential uses of IoT–enabled UAVs as smart terminal devices in a magnitude of applications, it is important to acknowledge and address the legitimate challenges of privacy, airspace management and safety, that will accompany their integration into Class G airspace over cities [14].

In order to address such pressing issues, Standard Development Organisations (SDOs) and other regulatory bodies have recently established working groups to lay down the foundations to accelerate the development of a new dedicated infrastructure for UAV management [35]. Starting with operator control, vehicle identification and control and, finally, traffic flow control, the envisioned infrastructure should allow seamless integration of heterogeneous systems and facilitate the data exchange between various stakeholders. Conflict detection and resolution, localisation & tracking and scheduling are some among many of the key function a UTM must offer.

From vehicle identification and control, conflict detection and resolution, localisation and tracking to scheduling, the envisioned infrastructure should allow seamless integration of heterogeneous systems and facilitate data exchange between various stakeholders. Supported by the foundations being laid down by Standard Development Organisations (SDOs) recently established working groups [35], research institutes and companies have recently proposed multiple UTM projects. Spearheaded by NASA Ames Research Centre in close collaboration with the Federal Aviation Administration (FAA) and over 125 industry partners [16], literature provides some constructs and architectures as part of on-going projects. Some of the most notable government led initiatives include U-Space project by the European Commission lead by the European Aviation Safety Agency (EASA) [17], China’s Civil UAS Operation Management System (UOMS) [36] the Japanese UTM [37] in collaboration with the private sector. Additionally, over the recent few years, multiple platforms were proposed by commercial industry. Deployed in over 9 countries across Europe, Asia and the United States of America, one platform that stands out is AirMap’s UAS Traffic Management [38], building on their widely adopted ATM platform. AirMap facilitates the collaboration between flight operators, industry, governments, 7 Standard Development Organisations (SDOs), 4 regulatory bodies including EASA and FAA. The interested reader can find an exhaustive list of commercial concept architectures and constructs in Reference [39] and a regularly updated map of international UTM implementations and test sites in Reference [40].

While the proposed systems offer a viable solution, such centralised systems will not be able to cope with the highly dynamic nature of the UAV traffic networks, let alone the dynamic geo-fencing, intrusion detection and communication challenges. To this extent, we envision a distributed UTM where UAVs dynamically plan their paths based on local information and decisions while optimising ad-hoc communications. This in turn would allow better scalability and resilience of the system [15,19].

2.3. Distributed Path Planning

In all the aforementioned promising applications, in order for UAVs or any other autonomous mobile robots, to perform their tasks, efficient and collision-free path planning becomes a necessity. Path planning for robotic applications is a research topic that has been actively studied over many years. However, literature have mainly focused on 2-dimensional (2D) and 2.5-dimensional (2.5D) methods [41], while approaches for UAVs, underwater vehicles and other highly mobile autonomous robots requiring 3-dimensional (3D) path planning, remain less explored.

Commonly used UAVs can be categorised as non-holonomic mobile robots [42] as the degree of their controllable actuators is less than their degree of freedom in the space which they operate; therefore, path planning optimisation adds further complexity in comparison to holonomic systems. In order to address such challenges, researchers divide path planning into two main subsystems; a global path planning subsystem complemented by a lower level addressing collision avoidance. The latter being out of the scope of this work, the interested reader can find various approaches and algorithms in Reference [43].

With focus on global path planning of UAVs, Yang et al. in Reference [44] provide a thorough survey of successful UAV 3D path planning algorithms found in literature. Additionally, the authors analyse and categorise the algorithms into sampling-based, mathematical model based, node-based and bio-inspired algorithms; out of which, we pay particular attention to the latter two, provided our proposed model of Class G. In addition to the well–known Dijkstra and A* algorithms, Likhachev et al. in Reference [45] propose an anytime heuristic search algorithm that improves on classical A* by ensuring that a robot has at least a sub-optimal path at any given time. The authors then develop further on this and propose [46], a heuristic-based re-planning method (AD*) relying on an anytime dynamic A* algorithm to continuously improve its solution within a predefined time frame as well as allow for re-computation of the path when information is updated. Another approach is the Lazy Theta*, proposed in Reference [47], building on the Theta* algorithm, this search method is not constrained to the topology of first hop neighbours in a multilayer network, in turn offers an improvement to classical A*. While this category of algorithms can find optimal paths through decomposing networks, they are not ideally suited for complex environments; hence, researchers rely on bio-inspired algorithms. From Particle Swarm Optimisation, Genetic Algorithm, Artificial Bee Colony and Bacterial Foraging Optimisation, to list a few, literature provides many bio-inspired optimisation algorithms for 3D path planning [41].

In contrast with the majority of the aforementioned heuristics, our algorithm should not only focus on optimising distance and time but should be able to optimise travel time while taking into consideration energy limitations, inspired by energy-aware routing in wireless sensors networks [48]. Therefore, we rely on our previous work in Reference [49] and on the work presented in Reference [50] on Inverted ACO for vehicle traffic management, to adopt a pheromone guided greedy heuristic in order to evaluate UAV traffic behaviour in the proposed model.

3. Multilayer UTM Model

This section encompasses our main contributions. We firstly describe the airspace model including key terminology, followed by a formal description of the network model and an illustrative operational example.

3.1. Class G Airspace Multilayer Model

The International Civil Aviation Organisation (ICAO) [51] divides the world’s navigable airspace into seven, three dimensional segments, represented by the first seven letters from the ISO basic Latin alphabet. All segments are controlled and regulated by Air Traffic Controllers (ATCs) except for the lower-most one, known as Class G. The latter ranges from 0 to 700 ft above ground level and remains uncontrolled [52] except in the proximity of published airports.

In our proposed model, illustrated in Figure 3, we further divide the Class G airspace into horizontal segments, referred to as layers, at different operational altitudes with separation allowing safe UAV flight. This extends a variation of the hemispheric rule [51] to Class G, where the separation between layers is guided by the Containment Limit (CL) of the largest UAV allowed in Class G. The CL of an aircraft is explained by ICAO as the volume with a 95% probability the aircraft is within, at any time of its stated position, both horizontally and vertically [53]. This can be derived from the Total System Error (TSE), illustrated in Figure 4. The TSE is the difference between the true position and the position on the desired/assigned flight paths of a UAV. It is the vector sum of the Navigation System Error, the Flight Technical Error and Path Definition error. The TSE defines the accuracy of a navigation system.

Following the approach explained in Reference [54], a city’s elevation map can be discretised using a topological analysis into a data-set of static-obstacle-free points within the different layers. This is key for structured airspace design and path planning. The level of detail of the discretised airspace is defined by the volume representing the UAV (alpha shape) as explained in Reference [55]. The resulting volume of obstacle-free space is referred to as the airspace which is the shared resource that is utilised by the UAVs. The latter comprises of Airways and Nodes, airways being corridors connecting nodes within a layer (horizontal) or between layers (vertical or diagonal). Airways allow UAVs to fly without direct communication with the UTM, guided only by the rules of the airway (velocity limits, flight headings and maximum traffic capacity) and information exchanged between UAVs through ad-hoc communication. Airways’ cross-sectional size is defined by the UAVs’ CL, while their lengths is defined by the segment’s static-obstacle-free space as well as airway-intersections, referred to as nodes (cf. Figure 5).

Within nodes, UAVs are allowed to change their Flight Mode. In our model, three main flight modes are considered, lateral flight, vertical flight and hovering for multirotor UAVs. We finally define a Path as a complete route from origin to destination, through different nodes and airways. Additionally, in our model, the different airspace layers allow different velocity ranges, that increase with altitude. This is supported by the argument that higher altitudes contain less static obstacles [54] and hence, longer airways are possible. UAVs rely on ad-hoc communication to exchange dynamic traffic information such as their flight velocities and airway traffic density. This in turn reduces latency and allows UAVs to make local routing decisions through the airspace eliminating the need for continuous direct communication with a centralised UTM [15].

3.2. Multilayer Network Model

We propose to model of the Class G airspace as a multi-weighted multilayer network,

M_{C l a s s G}

, where:

M_{C l a s s G} = (G_{M}, N, W_{E})

The airspace contains a non-empty set of layers N, each layer being represented as a graph of nodes and airways

G_{M} = (V_{M}, A_{M})

. Nodes can belong to one or more layers.

V_{M} = ⋃_{α = 1}^{| N |} V^{α}; α \in N

Each edge, that is, airway, is assigned three different weights defining travel time, energy cost and traffic capacity respectively:

a_{M} = (u, v, α, t, e, c)

with

u, v

∈

V_{M}

α

\in N

and

t, e, c \in W_{E}

, a non-empty set of weights at event step, E.

The set of edges is composed of intra-layer edges, that is, airways within one layer (

A^{α}

) and inter-layer edges, that is, airways connecting layers (

A^{α, β}

), with

α, β \in

A_{M} = (⋃_{α = 1}^{| N |} A^{α}) ⋃ (⋃_{α, β = 1, α \neq β}^{| N |} A^{α, β}),

with

A^{α}

⊆

V^{α} \times V^{α}

and

V^{α}

a finite, non-empty set of nodes on layer

α

and

A^{α, β}

⊆

V^{α} \times V^{β}

; with

α, β \in N

α \neq β

and

V^{β}

a finite, non-empty set of nodes on layer

β

Based on the definition in Reference [56] each layer is considered an incremental network where link weights are dynamic, that is, the structure of the network remains as is but the weights vary over time.

3.3. UAV Communication

According to IEEE’s technical committee on networked robots [57], a wireless networked robot system (WNR) is a subset of wireless sensor and actuator networks (WSANs). Such a system can be identified by two elements: (a) autonomous capabilities and (b) network-based cooperation. The first refers to the necessity, for a robot, to autonomously move and interact with the physical environment; while the second refers to its capability of communicating with others using radio technology. Over the recent years, the interaction between IoT and flying ad-hoc networks (FANETs) has become an important topic of research [58,59]. The interested reader can find a detailed analysis of such communication protocols in References [60,61,62]. Due to the high mobility of UAVs in flight, at this stage of work, we consider UAVs to communicate together (UAV-to-UAV) and to the infrastructure (UAV-to-Infrastructure) in an ad-hoc manner, similar to the communication model proposed in References [62,63]. A simplified view of the different types of communicated messages is presented in Figure 6 based on Reference [15]. In the same article, the authors firstly categorise the types of communicated messages based on their repetition rate and size then compare the communication performance of a centralised and a distributed UTM in a conflict resolution scenario.

Here each UAV is a flying node in FANET with some acting as gateways, as illustrated in Figure 1, to relay communicated information as explained in Reference [64]. UAVs exchange information using standard IoT communication protocols [62,64] at predefined time intervals, similar to automatic dependent surveillance-broadcasts and at node locations within the network. The broadcast is composed of the UAVs’ identification, lateral flight velocity, location and timestamp. With reference to Figure 6 above, in our envisioned UTM, UAVs rely on communicated awareness messages to locally evaluate traffic conditions in airways and make routing decisions.

3.4. Operational Example

To consolidate the model’s description, this subsection narrates one operational example relying on the proposed multilayer model of the Class G airspace. However, our proposed model can lend itself to multiple other scenarios.

Considering two groups of IoT–enabled UAVs, the first one is on a routine surveillance mission such as the crowd-surveillance use-case discussed in Reference [58], while the second group consists of emergency intervention UAVs such as medical rescue UAVs. Both groups, equipped with different sensory payload, entering the airspace have different mission priorities and incentives to get to their destination. UAVs enter airways through different nodes and traverse from origin to destination along paths at different layers. Each altitude segment, referred to as layer, allows different velocity ranges that increase at higher altitude layers. We assume that higher altitudes offer shorter travel times at the cost of higher energy consumption.

As each UAV traverses the network, it communicates and exchanges information with other UAVs in an ad-hoc manner using standard IoT communication protocols at predefined time intervals. Based on the exchanged traffic parameters information and rules such as critical traffic density and minimum flight velocities, UAVs make local routing decisions to switch between airways, airspace layers and flight modes according to their respective objectives of minimising time of flight or energy consumption.

4. UAV Traffic Optimisation

Given the size of the airspace, the corresponding multilayer network might become large, making path selection NP-complete [65]. This section presents the second contribution of this work, that is the path optimisation problem formulation followed by a first approach to optimise travel time and energy separately in our model of the Class G airspace.

4.1. Energy-Aware Path Optimisation

We formulate the problem of minimising the total travel time and energy consumption of UAV traffic in the network. Based on our multilayer network description, the two objective functions we aim to optimise are expressed as:

\begin{matrix} \min & P = \sum_{i = 1}^{I} \sum_{l = 1}^{L} a_{i l} * e_{l} \end{matrix}

(1)

\begin{matrix} \min & T = \sum_{i = 1}^{I} \sum_{l = 1}^{L} a_{i l} * t_{l} \end{matrix}

(2)

\begin{matrix} s . t . & \sum_{i = 1}^{I} a_{i l} = c_{l}, l = 1, \dots, L, \end{matrix}

(3)

\begin{matrix} c_{l} \leq c_{l}^{m a x}, l = 1, \dots, L, \end{matrix}

(4)

\begin{matrix} a_{i l} \in {0, 1}, i = 1, \dots, I, l = 1, \dots, L, \end{matrix}

(5)

\begin{matrix} P, T \in N, \end{matrix}

(6)

\begin{matrix} e_{l}, t_{l}, c_{l} \in N, l = 1, \dots, L, \end{matrix}

(7)

where:

P—objective function (energy consumed),
T—objective function (time elapsed),
I—number of UAVs,
i—index for UAVs,
L—number of airways,
l—index for airways,
a—selection indicator for airways/UAVs ( $\in 0, 1$ ),
e—energy consumption component for airways,
t—time elapse component for airways,
c—traffic capacity for airways,
$c^{m a x}$ —maximum traffic capacity for airways.

In our proposed model, each airway in a path has a critical traffic capacity of UAVs that it can traverse; in addition to an allowable maximum velocity which is expressed in terms of time t and energy e. Therefore, for a number of UAVs I over a complete path our first utility function (1) addresses our first objective, minimising the total energy consumption. While (2) addresses our second objective which is minimising the total travel time.

4.2. Optimisation Approach

This subsection introduces the three heuristics used in our experiments. The first one is a static path planning approach; the second is a probabilistic heuristic addressing the dynamic nature of our proposed model assuming global knowledge of the traffic conditions in the network; while the third is a pheromone guided greedy heuristic relying on local knowledge of traffic conditions. All heuristics are single objective, thus optimising either time or energy.

4.2.1. Global Offline Static—UTM (GOS)

To address the static nature of the network, at the beginning, UAVs follow a pre-computed shortest path from origin to destination. This shortest path is calculated with the A* algorithm [66] using a the respective network weights t or e, depending on the minimisation objective of each UAV and a heuristic that takes into account the Euclidean distance between network nodes, assuming optimal traffic conditions, no congestion and that UAVs can traverse the network at the maximum allowable speed of the layer. UAVs follow their given path (A*_shortest_path) and update the weights

t, e, c

of the respective airway l as long as the traffic capacity on the airway,

c_{l}

c_{l}^{m a x}

(c.f. lines 1–4 in Heuristic 1). Once maximum capacity is reached, UAVs queue at the airway entrance node, until the condition

c_{l}

c_{l}^{m a x}

is satisfied (c.f. line 5 in Heuristic 1).

4.2.2. Global Probabilistic Dynamic—UTM (GPD)

Assuming global knowledge of network weights, firstly, UAVs follow the shortest path initially computed by A* algorithm (c.f. lines 8–11 in Heuristic 2); however, on the contrary to GOS, when they encounter congestion on one airway, that is, when the maximum capacity of this airway is reached:

c_{l}

c_{l}^{m a x}

, each UAV takes a probabilistic decision

p_{r e r o u t e}

of either hovering in queue at the current node or to take an alternative shortest path computed with the same A* algorithm as in GOS on the multilayer network with updated

t, e, c

weights (c.f. lines 12–16 in Heuristic 2).

4.2.3. Local Pheromone Guided—UTM (LPG)

Relying on UAVs local knowledge of traffic condition, UAVs start by following the offline generated shortest path (A*_shortest_path) similar to in GOS and GPD, until the traffic on the next airway is superior to a predefined threshold defined by

T_{l i m}

, that is, when

c_{l}

T_{l i m}

where

T_{l i m}

c_{l}^{m a x}

(c.f. lines 19–22 in Heuristic 3). In reality,

T_{l i m}

would correspond to the critical traffic density explained in traffic theory as the capacity after which traffic flow becomes congested. At that stage each UAV lays down a pheromone trail

τ

, where

τ_{l}

1 / c_{l}^{m a x}

of airway l. The deposited trail of pheromone acts as a repellent to other UAVs, hence making the airway less desirable to take. In our model, intersecting nodes act as decision points at which the following UAVs receive the updated pheromone level and use the commonly used state transition rule introduced by Dorigo et al. in Reference [67] to decide which airway to select. This can be expressed as a function of the pheromone on the airway in addition to the quality of the airway:

p_{l}^{i}

f (τ_{l}, η_{l})

, where

p_{l}^{i}

is the probabilistic transition rule for UAV i to take airway l with quality

η_{l}

represented by

t / c_{l}^{m a x}

e / c_{l}^{m a x}

depending on the optimisation objective of the UAV. UAVs then take a decision of either staying on the same path or selecting a new airway. If the latter, UAVs recompute a path to destination, from the newly selected airway, using A* on the multilayer network with initial weights, assuming optimal traffic conditions (c.f. lines 23–25 in Heuristic 3), otherwise UAVs remain on their initial path (c.f. lines 26–30 in Heuristic 3).

5. Simulation and Results

This section outlines our experimental setup and discusses the preliminary results obtained using the aforementioned three UAV traffic management heuristics.

5.1. Experimental Setup

Experiments are conducted on a three layer network based on the Erdos – Rényi model using Python’s NetworkX library and the multiNetX package. Each layer contains the same number of nodes and each airway (intra and inter network) is assigned three weights, t, e and c, uniformly at random in predefined intervals. Figure 7 presents an example of a three layer network with 75 nodes (25 nodes per layer) and its adjacency matrix. The parameters used for the experiments are described in Table 1.

A single network with a total of 300 nodes and 3 layers (100 nodes per layer) has been used. Between every pair of nodes, there is a 20% probability an edge is created. The ranges of the three airway weights (time, energy and capacity) were selected to ensure that the lowest network layer allows less energy consumption by permitting UAVs to fly at their optimum or near optimum lateral velocity—the velocity at which a UAV is most energy efficient benefiting from transitional lift; while the higher layers allow incremental increase in flight velocity, hence reduce travel time at the cost of a higher energy consumption. Additionally, UAVs hovering in queuing state consume more energy than those in lateral flight. This is supported by the general power consumption model explained in Reference [68]. The selected capacity ranges also ensure that congestion can occur at different network layers for the tested UAV traffic values. Five traffic sample sizes were generated ranging from 10 to 500 UAVs (for experiment 1 and 2) and up to 1500 UAVs for experiment 3. All UAVs are assigned a pair of origin and destination nodes, both located on the lowest layer. All pairs are similar for experiment 1 and 2 while they differ in experiment 3. Each UAV keeps record of its current position, destination as well as its total travel time and energy consumption. Simulations were run 30 times for probabilistic heuristics.

Three main experiments are conducted. The first two aim to evaluate heuristics LPG and GPD respectively. For all three experiments we compare total UAVs’ travel time in the network—in arbitrary time units, total UAVs’ energy consumption—in arbitrary energy units, as well as the number of path changes, network layer change and total UAVs’ queuing counts.

The first experiment aims to investigate the effect of varying the decision probability

p_{r e r o u t e}

of GPD on its performance. With all UAVs having the same origin and destination pairs for all 5 traffic samples, the decision probability

p_{r e r o u t e}

is varied between 50%, 80% and 100% (c.f. Table 1), firstly with all UAVs having the same minimisation objective (i.e., time) and in a second stage with each UAV assigned either time or energy as objective.

The second experiment aims to study the effect of varying the traffic threshold

T_{l i m}

of LPG, which in turn varies the point at which UAVs start depositing pheromones on the network airways. Ensuring all UAVs have the same origin and destination pairs for all 5 traffic samples,

T_{l i m}

is varied between 0%, 50% and 80% on traffic samples with mixed minimisation objectives.

Finally, the main objective of the last experiment is to study the performance of the three heuristics (GOS, GPD, LPG) in a more realistic scenario. Each UAV is given a different pair of origin and destination and a minimisation objective (energy (1) or time (2)). The origin and destination pairs are all on the lowest layer and are more than two hops apart. The network and traffic sample size allow that airways might be shared by UAVs, hence ensuring that congestion can occur. The traffic threshold

T_{l i m}

value of LPG and decision probability

p_{r e r o u t e}

of GPD that demonstrated best performance in the first two experiments are used.

5.2. Results

This subsection presents the main results obtained during our experiments. The impact on the total UAVs’ travel time in the network, total UAVs’ energy consumption as well as the number of path changes, network layer change and queuing/hovering counts is explored. All obtained results are presented in Figure 8, Figure 9, Figure 10 and Figure 11 and summarised in Table 2, Table 3, Table 4 and Table 5. Figure 8, Figure 9, Figure 10 and Figure 11 present the impact in traffic performance by indicating the median, 25th and 75th percentile, while Table 2, Table 3, Table 4 and Table 5 present the mean and standard deviation in the results after 30 runs of the probabilistic heuristics for every varied parameter over all traffic samples: for every

T_{l i m}

in LPG and for every

p_{r e r o u t i n g}

in GPD. Statistical confidence in our comparisons is assessed by performing Kruskal-Wallis test [69] for Experiments 1 and 2 respectively and by performing the Wilcoxon test [70] for Experiment 3. The overall best result per comparison parameter is shown in bold. Additionally, the dark grey background emphasises the best results that showed statistically significant difference with a 95% confidence.

5.2.1. Experiment 1: Impact of $p_{r e r o u t i n g}$ on GPD Performance

In the first experiment we aim to study the impact of the decision probability

p_{r e r o u t e}

on the performance of GPD, firstly, for traffic samples consisting of UAVs with the same minimisation objective, then with traffic samples with varying minimisation objectives. Three

p_{r e r o u t e}

values are tested as indicated in Table 1: 50%, 80% and 100%.

It can be deduced from Table 2 and Figure 8, of the first part of the experiment, that for the smaller traffic sample sizes of 10 and 50, GPD with

p_{r e r o u t e}

50% and 80% generally showed improvement over

p_{r e r o u t e}

of 100% in total UAVs’ travel time and energy consumption. Nevertheless,

p_{r e r o u t e}

of 100% showed better performance when it came to total traffic path and layer changes for the same samples. However, since the main global objective is a scalable system, it is important to study the performance of the heuristic at larger sample sizes. While that is the case, GPD with

p_{r e r o u t e}

of 100% outperforms the same heuristic with

p_{r e r o u t e}

50% and 80% for the larger traffic samples. Improvements can be observed with statistically significant difference across all the traffic performance indicators tested for traffic sample size 500 and 200, with exception of total UAVs’ queue counts in the network for the latter.

A similar trend is observed in the second part of the experiment, presented in Table 3 and Figure 9 where UAVs have different minimisation objectives as explained in Section 5.1.

Compared to the first part, Table 3 and Figure 9 showed a significant improvement for the total UAVs’ travel time and energy consumption for GPD with

p_{r e r o u t e}

100% for larger traffic samples, regardless of the individual minimisation objective of UAVs.

5.2.2. Experiment 2: Impact of $T_{l i m}$ on LPG Performance

Similar to Experiment 1 (Section 5.2.1), the impact on total UAVs’ travel time and energy consumption in the network as well as the number of path changes, network layer change and queuing counts is explored as result of varying traffic threshold

T_{l i m}

of LPG between 0%, 50% and 80% of

c_{l}^{m a x}

Analysing the results obtained, it can be deduced from Table 4 and Figure 10 that, with the exception for the smallest traffic sample size of 10, LPG with

T_{l i m}

of 0% generally showed improvement with statistically significant difference over

T_{l i m}

of 80% and 50% across all the traffic performance indicators tested for the remaining traffic sample sizes. These results indicate that pheromone deposit caused a fast dispersion of UAVs across the network, which had a negative impact only for the smallest traffic sample. On the contrary, it led to an overall improvement in reducing total UAVs’ travel time and energy consumption across for all other traffic samples.

5.2.3. Experiment 3: Performance Comparison of GOS, GPD and LPG

Finally, Experiment 3 aims to study the performance of the three heuristics (GOS, GPD, LPG) in a more realistic scenario as explained in Section 5.1 to address the assumptions made in the previous work in the literature [22]. Here each UAV has a different origin and destination pair as well as one of the two minimisation objectives (energy (1) or time (2)).

Figure 11 and Table 5 present the obtained results when comparing the impact the three heuristics (GOS, GPD, LPG) have on traffic performance in a more realistic scenario. It can be observed that, with the exception for traffic sample 10, LPG results show improvement in total UAVs’ travel time for all traffic samples, where the percentage of UAVs with the minimisation objective (2) (i.e., time) is 50%, 40%, 45%, 19.5%, 48.8%, 49% and 48.13% for every traffic sample size respectively. On the other hand, it is worth to mention that due to the selected parameters and the nature of GPD, encouraging UAVs to be more inclined to reduce layer changes, led to the significant difference in reduction of energy consumption in comparison to LPG for traffic samples 50–200. However, for the larger traffic samples, which are more decisive in the devised scenario, LPG outperforms GPD with significant difference across 4 of the 5 main parameters of comparison, with the exception of total number of layer changes, which can be explained by the nature of the heuristic LPG which encourages UAVs to explore vertical airways between layers as they offer a higher

c_{l}^{m a x}

6. Conclusions and Future Work

IoT has catalysed and facilitated the development of new devices that are capable of interacting with our physical world, generating unprecedented amounts of information. One category that not only promise a new means of capturing information but also new means of overcoming limitations of IoT’s existing infrastructure are UAVs. However, despite the significant advantages UAVs bring, as their number continues to grow, UAV deployment is faced with challenges in their safe operation and management. This emphasises the need for a new dedicated, distributed UAV traffic management system supported by regulations and international technical standards.

In this paper, we have extended our first contributions towards our envisioned distributed UTM by presenting a broader state of the art analysis as well as description of UAV communication. The work, firstly, described our model and structure of the low altitude, Class G, airspace and outlines key terminology and an operational scenario. Secondly, the paper contributed to existing literature by representing the airspace model as a multilayer network of nodes and airways. Finally the corresponding UTM optimisation problem has been defined and some first experimental results have been obtained using three traffic management heuristics. The results showed that for the larger traffic samples, the heuristic assuming local traffic knowledge, LPG, outperforms GOS and GPD across the main traffic performance indicators selected for the study.

Whilst the simulation included assumptions to simplify the challenging multifaceted problem, future work will focus on more realistic communication scenarios. We intend to investigate different communication protocols on traffic behaviour and explore more realistic communication metrics, given the challenging nature of flying ad-hoc networks. Finally, we intend to develop and evaluate different metaheuristic optimisation techniques for this challenging problem.

Author Contributions

Conceptualization, N.S.L.; methodology, N.S.L. and G.D.; software, N.S.L.; validation, N.S.L., G.D., J.M. and M.R.B.; formal analysis, N.S.L. and G.D.; writing—original draft preparation, N.S.L.; writing—review and editing, N.S.L., G.D., J.M., M.R.B. and P.B.; visualization, N.S.L.; supervision, G.D. and P.B.

Funding

This work is partially funded by the joint research programme UL/SnT–ILNAS on Digital Trust for Smart-ICT.

Conflicts of Interest

The authors declare no conflict of interest.

References

Samir Labib, N.; Liu, C.; Dilmaghani, S.; Brust, M.R.; Danoy, G.; Bouvry, P. White Paper: Data Protection and Privacy in Smart ICT-Scientific Research and Technical Standardization; Technical Report; ILNAS—University of Luxembourg: Luxembourg, 2018. [Google Scholar] [CrossRef]
Zhou, C.; Ye, H.; Hu, J.; Shi, X.; Hua, S.; Yue, J.; Xu, Z.; Yang, G. Automated Counting of Rice Panicle by Applying Deep Learning Model to Images from Unmanned Aerial Vehicle Platform. Sensors 2019, 19, 3106. [Google Scholar] [CrossRef] [PubMed]
Su, W.; Zhang, M.; Bian, D.; Liu, Z.; Huang, J.; Wang, W.; Wu, J.; Guo, H. Phenotyping of Corn Plants Using Unmanned Aerial Vehicle (UAV) Images. Remote Sens. 2019, 11, 2021. [Google Scholar] [CrossRef]
Fernández-Caramés, T.M.; Blanco-Novoa, O.; Froiz-Míguez, I.; Fraga-Lamas, P. Towards an Autonomous Industry 4.0 Warehouse: A UAV and Blockchain-Based System for Inventory and Traceability Applications in Big Data-Driven Supply Chain Management. Sensors 2019, 19, 2394. [Google Scholar] [CrossRef]
Fakhrulddin, S.S.; Gharghan, S.K.; Al-Naji, A.; Chahl, J. An Advanced First Aid System Based on an Unmanned Aerial Vehicles and a Wireless Body Area Sensor Network for Elderly Persons in Outdoor Environments. Sensors 2019, 19, 2955. [Google Scholar] [CrossRef] [PubMed]
Manfreda, S.; McCabe, M.F.; Miller, P.E.; Lucas, R.; Pajuelo Madrigal, V.; Mallinis, G.; Ben Dor, E.; Helman, D.; Estes, L.; Ciraolo, G.; et al. On the Use of Unmanned Aerial Systems for Environmental Monitoring. Remote Sens. 2018, 10, 641. [Google Scholar] [CrossRef]
Besada, J.A.; Bergesio, L.; Campaña, I.; Vaquero-Melchor, D.; López-Araquistain, J.; Bernardos, A.M.; Casar, J.R. Drone Mission Definition and Implementation for Automated Infrastructure Inspection Using Airborne Sensors. Sensors 2018, 18, 1170. [Google Scholar] [CrossRef] [PubMed]
Erdelj, M.; Natalizio, E.; Chowdhury, K.R.; Akyildiz, I.F. Help from the Sky: Leveraging UAVs for Disaster Management. IEEE Pervasive Comput. 2017, 16, 24–32. [Google Scholar] [CrossRef]
Brust, M.R.; Danoy, G.; Bouvry, P.; Gashi, D.; Pathak, H.; Gonçalves, M.P. Defending against intrusion of malicious uavs with networked uav defense swarms. In Proceedings of the 2017 IEEE 42nd Conference on Local Computer Networks Workshops (LCN Workshops), Singapore, 9 October 2017; pp. 103–111. [Google Scholar]
Marchese, M.; Moheddine, A.; Patrone, F. IoT and UAV Integration in 5G Hybrid Terrestrial-Satellite Networks. Sensors 2019, 19, 3704. [Google Scholar] [CrossRef]
Zhan, C.; Zeng, Y.; Zhang, R. Energy-Efficient Data Collection in UAV Enabled Wireless Sensor Network. IEEE Wirel. Commun. Lett. 2018, 7, 328–331. [Google Scholar] [CrossRef]
Al-Turjman, F.; Alturjman, S. 5G/IoT-enabled UAVs for multimedia delivery in industry-oriented applications. Multimed. Tools Appl. 2018, 1–22. [Google Scholar] [CrossRef]
ISO. ISO/IEC 30141:2018 Internet of Things (loT)—Reference Architecture; Standard, International Organization for Standardization: Geneva, Switzerland, 2018. [Google Scholar]
Motlagh, N.H.; Taleb, T.; Arouk, O. Low-altitude unmanned aerial vehicles-based internet of things services: Comprehensive survey and future perspectives. IEEE Internet Things J. 2016, 3, 899–922. [Google Scholar] [CrossRef]
Schalk, L.M. Communication links for unmanned aircraft systems in very low level airspace. In Proceedings of the 2017 Integrated Communications, Navigation and Surveillance Conference (ICNS), Herndon, VA, USA, 18–20 April 2017; pp. 1–26. [Google Scholar] [CrossRef]
Kopardekar, P.; Rios, J. Enabling Civilian Low-Altitude Airspace and Unmanned Aerial System (UAS) Operations by UTM. 2015. Available online: https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20160000433.pdf (accessed on 11 September 2019).
Huttunen, M. The U-space Concept. Air Space Law 2019, 44, 69–89. [Google Scholar]
Bekkouche, O.; Taleb, T.; Bagaa, M. UAVs Traffic Control Based on Multi-Access Edge Computing. In Proceedings of the 2018 IEEE Global Communications Conference (GLOBECOM), Abu Dhabi, UAE, 9–13 December 2018; pp. 1–6. [Google Scholar] [CrossRef]
Sedov, L.; Polishchuk, V. Centralized and distributed UTM in layered airspace. In Proceedings of the 8th ICRAT, Catalonia, Spain, 16 February 2018. [Google Scholar]
Sunil, E.; Hoekstra, J.; Ellerbroek, J.; Bussink, F.; Nieuwenhuisen, D.; Vidosavljevic, A.; Kern, S. Metropolis: Relating airspace structure and capacity for extreme traffic densities. In Proceedings of the ATM Seminar 2015, 11th USA/EUROPE Air Traffic Management R&D Seminar, Lisbon, Portugal, 23–26 June 2015. [Google Scholar]
Sunil, E.; Hoekstra, J.; Ellerbroek, J.; Bussink, F.; Vidosavljevic, A.; Delahaye, D.; Aalmoes, R. The influence of traffic structure on airspace capacity. In Proceedings of the ICRAT2016—7th International Conference on Research in Air Transportation, Philadelphia, PA, USA, 20–24 June 2016. [Google Scholar]
Labib, S.N.; Danoy, G.; Musial, J.; Brust, R.M.; Bouvry, P. A Multilayer Low-Altitude Airspace Model for UAV Traffic Management. In Proceedings of the 9th ACM Symposium on Design and Analysis of Intelligent Vehicular Networks and Applications DIVANet’19, Miami, FL, USA, 25–29 November 2019. [Google Scholar] [CrossRef]
D’Agostino, G.; Scala, A. Networks of Networks: The Last Frontier of Complexity; Springer: Berlin, Germany, 2014; Volume 340. [Google Scholar]
Magnani, M.; Rossi, L. The ml-model for multi-layer social networks. In Proceedings of the 2011 International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Kaohsiung, Taiwan, 25–27 July 2011; pp. 5–12. [Google Scholar]
Dickison, M.; Havlin, S.; Stanley, H.E. Epidemics on interconnected networks. Phys. Rev. E 2012, 85, 066109. [Google Scholar] [CrossRef] [PubMed] [Green Version]
Pilosof, S.; Porter, M.A.; Pascual, M.; Kéfi, S. The multilayer nature of ecological networks. Nat. Ecol. Evolut. 2017, 1, 0101. [Google Scholar] [CrossRef] [PubMed] [Green Version]
Gosak, M.; Markovič, R.; Dolenšek, J.; Rupnik, M.S.; Marhl, M.; Stožer, A.; Perc, M. Network science of biological systems at different scales: A review. Phys. Life Rev. 2018, 24, 118–135. [Google Scholar] [CrossRef] [PubMed]
Musmeci, N.; Nicosia, V.; Aste, T.; Di Matteo, T.; Latora, V. The multiplex dependency structure of financial markets. Complexity 2017. [Google Scholar] [CrossRef]
Battiston, F.; Perc, M.; Latora, V. Determinants of public cooperation in multiplex networks. New J. Phys. 2017, 19, 073017. [Google Scholar] [CrossRef]
Gallotti, R.; Barthelemy, M. The multilayer temporal network of public transport in Great Britain. Sci. Data 2015, 2, 140056. [Google Scholar] [CrossRef] [Green Version]
Cardillo, A.; Zanin, M.; Gómez-Gardenes, J.; Romance, M.; del Amo, A.J.G.; Boccaletti, S. Modeling the multi-layer nature of the European Air Transport Network: Resilience and passengers re-scheduling under random failures. Eur. Phys. J. Spec. Top. 2013, 215, 23–33. [Google Scholar] [CrossRef] [Green Version]
Tsiotas, D.; Polyzos, S. Decomposing multilayer transportation networks using complex network analysis: A case study for the Greek aviation network. J. Complex Netw. 2015, 3, 642–670. [Google Scholar] [CrossRef]
Hong, C.; Zhang, J.; Cao, X.B.; Du, W.B. Structural properties of the Chinese air transportation multilayer network. Chaos Solitons Fract. 2016, 86, 28–34. [Google Scholar] [CrossRef]
Jiang, J.; Zhang, R.; Guo, L.; Li, W.; Cai, X. Network Aggregation Process in Multilayer Air Transportation Networks. Chin. Phys. Lett. 2016, 33, 108901. [Google Scholar] [CrossRef]
Labib, S.N.; Brust, M.R.; Danoy, G.; Bouvry, P. On Standardised Localisation and Tracking Systems for UAVs in Smart Cities. In Proceedings of the 17th Annual STS Conference Graz, Critical Issues in Science, Technology and Society Studies, Graz, Austria, 7–8 May 2018. [Google Scholar]
Civil Aviation Administration of China (CAAC)—UTM (UOMS). Available online: https://gutma.org/map/China (accessed on 11 September 2019).
Japan UTM. Available online: https://gutma.org/map/Japan (accessed on 11 September 2019).
AirMap—UAS Traffic Management Platform. Available online: https://www.airmap.com/ (accessed on 11 September 2019).
The Unmanned Air System Traffic Management UTM Directory. Available online: https://www.unmannedairspace.info/wp-content/uploads/2019/06/UTM-directory.-June-2019.-v1.pdf (accessed on 11 September 2019).
Map of International UTM Implementations and Test Sites. Available online: https://gutma.org/map/Main_Page (accessed on 11 September 2019).
Yang, L.; Qi, J.; Song, D.; Xiao, J.; Han, J.; Xia, Y. Survey of robot 3D path planning algorithms. J. Control Sci. Eng. 2016, 2016, 5. [Google Scholar] [CrossRef]
Sanchez-Lopez, J.L.; Wang, M.; Olivares-Mendez, M.A.; Molina, M.; Voos, H. A Real-Time 3D Path Planning Solution for Collision-Free Navigation of Multirotor Aerial Robots in Dynamic Environments. J. Intell. Robot. Syst. 2019, 93, 33–53. [Google Scholar] [CrossRef]
Goerzen, C.; Kong, Z.; Mettler, B. A survey of motion planning algorithms from the perspective of autonomous UAV guidance. J. Intell. Robot. Syst. 2010, 57, 65. [Google Scholar] [CrossRef]
Yang, L.; Qi, J.; Xiao, J.; Yong, X. A literature review of UAV 3D path planning. In Proceedings of the 11th World Congress on Intelligent Control and Automation, Shenyang, China, 29 June–4 July 2014; pp. 2376–2381. [Google Scholar]
Likhachev, M.; Gordon, G.J.; Thrun, S. ARA*: Anytime A* with provable bounds on sub-optimality. In Advances in Neural Information Processing Systems; Mit Press: Vancouver, BC, Canada, 2004; pp. 767–774. [Google Scholar]
Likhachev, M.; Ferguson, D.I.; Gordon, G.J.; Stentz, A.; Thrun, S. Anytime Dynamic A*: An Anytime, Replanning Algorithm. In Proceedings of the ICAPS, Monterey, CA, USA, 5–10 June 2005; Volume 5, pp. 262–271. [Google Scholar]
Nash, A.; Koenig, S.; Tovey, C. Lazy Theta*: Any-angle path planning and path length analysis in 3D. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, Atlanta, GA, USA, 11–15 July 2010. [Google Scholar]
Yahiaoui, S.; Omar, M.; Bouabdallah, A.; Natalizio, E.; Challal, Y. An energy efficient and QoS aware routing protocol for wireless sensor and actuator networks. AEU-Int. J. Electron. Commun. 2018, 83, 193–203. [Google Scholar] [CrossRef] [Green Version]
Danoy, G.; Brust, M.R.; Bouvry, P. Connectivity Stability in Autonomous Multi-level UAV Swarms for Wide Area Monitoring. In Proceedings of the 5th ACM Symposium on Development and Analysis of Intelligent Vehicular Networks and Applications, Cancun, Mexico, 2–6 November 2015; ACM: New York, NY, USA, 2015; pp. 1–8. [Google Scholar] [CrossRef] [Green Version]
Dias, J.C.; Machado, P.; Silva, D.C.; Abreu, P.H. An inverted ant colony optimization approach to traffic. Eng. Appl. Artif. Intell. 2014, 36, 122–133. [Google Scholar] [CrossRef]
Weber, L. International Civil Aviation Organization. An Introduction. Air Space Law 2007, 32, 417. [Google Scholar]
Stöcker, C.; Bennett, R.; Nex, F.; Gerke, M.; Zevenbergen, J. Review of the current state of UAV regulations. Remote Sens. 2017, 9, 459. [Google Scholar] [CrossRef]
Schwithal, A.; Tonhäuser, C.; Wolkow, S.; Angermann, M.; Hecker, P.; Mumm, N.; Holzapfel, F. Integrity monitoring in GNSS/INS systems by optical augmentation. In Proceedings of the Inertial Sensors and Systems (ISS), Karlsruhe, Germany, 19–20 September 2017; pp. 1–22. [Google Scholar]
Cho, J.; Yoon, Y. Assessing the airspace availability for sUAV operations in urban environments: A topological approach using keep-in and keep-out geofence. In Proceedings of the 2018 International Conference on Research in Air Transportation (ICRAT), Barcelona, Spain, 26–29 June 2018. [Google Scholar]
Edelsbrunner, H.; Letscher, D.; Zomorodian, A. Topological persistence and simplification. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, 12–14 November 2000; pp. 454–463. [Google Scholar]
Singh, S.; Joshi, R.P.; Kohli, H. Optimal Route Searching in Networks with Dynamic Weights Using Flow Algorithms. In Proceedings of the 2015 International Conference on Computational Intelligence and Communication Networks (CICN), Jabalpur, India, 12–14 December 2015; pp. 146–155. [Google Scholar] [CrossRef]
IEEE Technical Committee on Networked Robots. Available online: https://www-users.cs.umn.edu/~isler/tc/ (accessed on 8 September 2019).
Motlagh, N.H.; Bagaa, M.; Taleb, T. UAV-based IoT platform: A crowd surveillance use case. IEEE Commun. Mag. 2017, 55, 128–134. [Google Scholar] [CrossRef]
Zhang, J.; Chen, T.; Zhong, S.; Wang, J.; Zhang, W.; Zuo, X.; Maunder, R.G.; Hanzo, L. Aeronautical AdHoc Networking for the Internet-Above-the-Clouds. Proc. IEEE 2019, 107, 868–911. [Google Scholar] [CrossRef]
Guillen-Perez, A.; Cano, M.D. Flying Ad Hoc Networks: A New Domain for Network Communications. Sensors 2018, 18, 3571. [Google Scholar] [CrossRef] [PubMed]
Ollero, A.; Lacroix, S.; Merino, L.; Gancet, J.; Wiklund, J.; Remuss, V.; Perez, I.V.; Gutierrez, L.G.; Viegas, D.X.; Benitez, M.A.G.; et al. Multiple eyes in the skies: Architecture and perception issues in the COMETS unmanned air vehicles project. IEEE Robot. Autom. Mag. 2005, 12, 46–57. [Google Scholar] [CrossRef]
Lagkas, T.; Argyriou, V.; Bibi, S.; Sarigiannidis, P. UAV IoT Framework Views and Challenges: Towards Protecting Drones as “Things”. Sensors 2018, 18, 4015. [Google Scholar] [CrossRef] [PubMed]
Manfredi, S.; Natalizio, E.; Pascariello, C.; Zema, N.R. A packet loss tolerant rendezvous algorithm for wireless networked robot systems. Asian J. Control 2017, 19, 1413–1423. [Google Scholar] [CrossRef]
Li, J.; Zhou, Y.; Lamont, L. Communication architectures and protocols for networking unmanned aerial vehicles. In Proceedings of the 2013 IEEE Globecom Workshops (GC Wkshps), Atlanta, GA, USA, 9–13 December 2013; pp. 1415–1420. [Google Scholar]
Kuipers, F.; Dijkstra, F. Path selection in multi-layer networks. Comput. Commun. 2009, 32, 78–85. [Google Scholar] [CrossRef]
Hart, P.E.; Nilsson, N.J.; Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 1968, 4, 100–107. [Google Scholar] [CrossRef]
Dorigo, M.; Maniezzo, V.; Colorni, A. Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B Cybern. 1996, 26, 29–41. [Google Scholar] [CrossRef]
Hwang, M.H.; Cha, H.R.; Jung, S. Practical Endurance Estimation for Minimizing Energy Consumption of Multirotor Unmanned Aerial Vehicles. Energies 2018, 11, 2221. [Google Scholar] [CrossRef]
Kruskal, W.H.; Wallis, W.A. Use of ranks in one-criterion variance analysis. J. Am. Stat. Assoc. 1952, 47, 583–621. [Google Scholar] [CrossRef]
Wilcoxon, F. Individual comparisons by ranking methods. In Breakthroughs in Statistics; Springer: Berlin, Germany, 1992; pp. 196–202. [Google Scholar]

Figure 1. Role of unmanned aerial vehicle (UAV) within Internet of Things (IoT) as: (a) smart terminal devices that interact with the physical world; (b) aerial base stations and gateways; (c) communication network connected to IoT cloud.

Figure 2. UAV traffic management (UTM) facilitating communication between main stakeholders [22].

Figure 3. Proposed multilayer UTM model of the Class G airspace [22].

Figure 4. Total System Error of a UAV [22].

Figure 5. Airways and Nodes in proposed UTM model [22].

Figure 6. Communicated messages in a distributed and centralised UTM [15].

Figure 7. Example of a 75-Node three layer network and its adjacency matrix.

Figure 8. Impact on traffic performance by varying

p_{r e r o u t i n g}

in GPD (50%, 80%, 100%).

Figure 8. Impact on traffic performance by varying

p_{r e r o u t i n g}

in GPD (50%, 80%, 100%).

Figure 9. Impact on mixed objective traffic performance by varying

p_{r e r o u t e}

in GPD (50%, 80%, 100%).

Figure 9. Impact on mixed objective traffic performance by varying

p_{r e r o u t e}

in GPD (50%, 80%, 100%).

Figure 10. Impact on traffic performance by varying

T_{l} i m

in Local Pheromone Guided (LPG) (80%, 50%, 0%).

Figure 10. Impact on traffic performance by varying

T_{l} i m

in Local Pheromone Guided (LPG) (80%, 50%, 0%).

Figure 11. Performance comparison of Global Offline Static (GOS), GPD and LPG.

Table 1. Experiment parameters.

Parameter	Value
Number of UAVs (experiment 1 & 2)	10, 50, 100, 200, 500
Number of UAVs (experiment 3)	10, 50, 100, 200, 500, 1000, 1500
Number of nodes	100 per layer
Number of layers	3
Edge creation probability	20%
Interlayer energy weight interval	[15,20]
Intralayer energy weight intervals	[5,10], [15,20], [25,30]
Interlayer time weight interval	[1,5]
Intralayer time weight intervals	[25,30], [15,20], [5,10]
Interlayer capacity weight interval	50
Intralayer capacity weight interval	[1,5]
GPD decision probability ( $p_{r e r o u t e}$ )	50%, 80%, 100%
LPG $T_{l i m}$ percentage of $c_{l}^{m a x}$	0%, 50%, 80%

Table 2. Impact on traffic performance from varying

p_{r e r o u t e}

in Global Probabilistic Dynamic (GPD) (50%, 80%, 100%).

Table 2. Impact on traffic performance from varying

p_{r e r o u t e}

in Global Probabilistic Dynamic (GPD) (50%, 80%, 100%).

Traffic	$p_{r e r o u t e}$	Time	Energy	Path Changes	Layer Changes	Queue Counts
Traffic	$p_{r e r o u t e}$	Mean_SD	Mean_SD	Mean_SD	Mean_SD	Mean_SD
10	50%	52.9_12.562	24.3_22.073	1₀	6₀	0₀
	80%	55.22_13.532	24.913_24.122	0.733_0.442	4.4_2.657	0.267_0.442
	100%	59.57_14.195	26.063_27.518	0.233_0.423	1.4_2.541	0.767_0.423
50	50%	72.58_32.991	126.06_60.396	41₀	246₀	0₀
	80%	71.609_31.663	113.490_52.779	31.1_1.578	180.533_12.631	14.067_4.7127
	100%	95.709_54.985	142.730_85.650	19.4_2.260	108.6_13.237	46.767_6.683
100	50%	101.54_44.173	185.78_77.196	91₀	546₀	41₀
	80%	97.807_41.408	168.034_71.125	80.667_3.123	444.8_11.975	53.067_1.999
	100%	119.549_68.633	203.498_112.434	55.533_2.391	311.4_14.881	132.4_13.439
200	50%	184.77_98.680	321.89_152.576	323₀	1146₀	273₀
	80%	174.292_98.3507	293.762_153.836	241.2_4.942	1012.2_9.789	255.767_2.362
	100%	155.051_79.231	274.623_138.601	142.333_3.261	790.667_15.086	344.7_15.775
500	50%	403.158_218.089	692.006_359.752	2219₀	2946₀	2169₀
	80%	362.4707_200.818	626.507_340.444	1474.867_20.884	2746_8.884	2002.067_9.609
	100%	317.376_175.792	560.534_297.477	660.667_23.310	2403.533_23.408	1932.6_5.897

Table 3. Impact on mixed objective traffic performance from varying

p_{reroute}

in GPD (50%, 80%, 100%).

Table 3. Impact on mixed objective traffic performance from varying

p_{reroute}

in GPD (50%, 80%, 100%).

Traffic	$p_{reroute}$	Time	Energy	Path Changes	Layer Changes	Queue Counts
Traffic	$p_{reroute}$	Mean	Mean	Mean	Mean	Mean
10	50%	36.983_16.054	81.483_59.709	0.567_0.668	44_6.120	0₀
	80%	34.693_18.101	64.133_41.679	0.7_0.972	34_6.461	0₀
	100%	35.29_23.037	55.49_42.019	0.066_0.249	30.4_8.346	0₀
50	50%	90.256_48.051	184.011_76.146	19.033_3.231	353.267_3.327	0.1_0.300
	80%	56.010_23.587	122.049_42.648	20.233_3.364	270_3.347	0.2_0.541
	100%	53.612_25.564	119.072_49.721	17.4_3.989	258_2.858	0₀
100	50%	87.818_45.792	143.507_90.842	63.8_2.982	531.867_18.179	6_2.161
	80%	67.753_28.558	105.883_55.172	62.4_4.580	431.8_20.706	4.8_1.939
	100%	67.037_27.559	127.385_78.674	82.967_6.868	439.4_15.928	22.233_2.654
200	50%	113.013_61.736	188.479_113.829	174.5_6.329	1259.2_28.304	17.1_4.962
	80%	97.522_66.314	153.513_139.743	182.067_5.994	1034.6_29.251	16.567_4.064
	100%	79.363_30.984	133.671_67.384	517.5_36.862	731.867_29.662	90.233_7.196
500	50%	160.941_115.246	239.410_170.669	673.9_12.081	3372.933_46.131	548.033_44.961
	80%	149.9787_130.437	232.054_252.268	745.733_17.309	3040.2_60.176	39.867_6.265
	100%	118.104_63.245	180.317_108.839	4177.1_300.999	1705.067_80.250	38.633_6.264

Table 4. Impact on traffic performance from varying traffic threshold in LPG (80%, 50%, 0%).

Traffic	$T_{l i m}$	Time	Energy	Path Changes	Layer Changes	Queue Counts
Traffic	$T_{l i m}$	Mean_SD	Mean_SD	Mean_SD	Mean_SD	Mean_SD
10	80%	35.897_16.054	81.483_59.709	0.567_0.669	44_6.120	0₀
	50%	36.983_21.059	60.211_38.824	2.167_0.523	26.333_2.199	0₀
	0%	41.048_22.902	42.883_31.621	0.033_0.179	19.2_5.5131	0.033_0.179
50	80%	90.256_48.051	184.011_76.146	19.033_3.231	353.267_3.327	0.1_0.303
	50%	58.083_34.847	104.555_38.793	56.2_6.597	256.4_8.788	0.033_0.179
	0%	38.535_23.058	60.263_46.212	3.767_0.558	118.267_13.177	3.767_0.558
100	80%	87.8175_45.792	143.507_90.842	63.8_2.982	531.867_18.179	6_2.165
	50%	82.312_55.216	138.027_68.833	161.767_6.855	604.067_17.257	0.667_0.788
	0%	39.929_22.709	59.784_46.062	7.2_0.653	230_17.400	7.2_0.653
200	80%	113.014_61.736	188.479_113.829	174.5_6.329	1259.2_28.303	17.1_4.962
	50%	91.602_50.154	134.861_81.634	338.967_14.102	1079.4_31.008	3.867_1.857
	0%	40.282_22.734	60.974_46.324	14.867_1.118	465.733_26.967	14.867_1.117
500	80%	160.942_115.246	239.411_170.669	673.9_12.0816	3372.933_46.131	38.633_6.263
	50%	131.893_85.076	191.934_122.321	1218.333_37.382	3355.667_51.543	35.6_6.988
	0%	40.798_22.697	60.925_46.422	37.067_1.672	1154_33.765	37.067_1.672

Table 5. Comparison of traffic performance using GOS, GPD and LPG.

Traffic	Heuristic	Time	Energy	Path Changes	Layer Changes	Queue Counts
Traffic	Heuristic	Mean_SD	Mean_SD	Mean_SD	Mean_SD	Mean_SD
10	GOS	36.6_24.88	33.2_22.836	0₀	16₀	0₀
	GPD	37.005_27.297	37.468_25.579	0₀	17.933_7.006	0₀
	LPG	41.48_28.825	34.636_24.895	0₀	15.467_5.142	0₀
50	GOS	42.48_24.708	36.12_25.274	0₀	80₀	0₀
	GPD	40.075_27.126	38.069_26.758	0.2_0.603	84.6_12.759	0₀
	LPG	38.567_26.827	39.741_27.149	1.267_1.367	92_12.365	0₀
100	GOS	38.96_25.905	42.75_27.849	0₀	196₀	0₀
	GPD	40.551_26.048	40.884_28.378	2.133_1.707	175.667_13.811	0.167_0.453
	LPG	36.05_24.306	47.796_29.8793	13.6_4.957	228.733_8.982	0₀
200	GOS	46.755_31.381	52.42_35.264	0₀	360₀	17₀
	GPD	41.475_25.571	51.0127_32.667	27.8_4.527	420.6_15.512	4.767_2.458
	LPG	34.823_21.419	59.737_31.569	63.167_6.798	585.067_16.426	0₀
500	GOS	80.355_53.447	109.591_73.879	0₀	864₀	300₀
	GPD	54.502_32.649	82.0328_59.460	258.333_20.190	1275_38.084	101.433_10.941
	LPG	45.676_25.424	84.797_41.121	331_24.960	1895.533_49.837	1.1_1.247
1000	GOS	123.007_84.891	189.113_131.816	0₀	1668₀	1372₀
	GPD	76.069_50.318	111.649_101.295	982.433_40.802	2425.933_54.944	441.467_25.967
	LPG	49.867_27.228	82.845_42.786	670.5_33.059	3592.267_57.933	10.433_4.318
1500	GOS	162.340_114.463	264.691_193.237	0₀	2584₀	3097₀
	GPD	93.355_69.075	137.715_142.167	2267.9_81.103	3400.933_75.662	1059.033_66.985
	LPG	59.887_34.968	100.8399_53.280	1220.533_52.787	6051.533_96.466	11.8_4.490

© 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Samir Labib, N.; Danoy, G.; Musial, J.; Brust, M.R.; Bouvry, P. Internet of Unmanned Aerial Vehicles—A Multilayer Low-Altitude Airspace Model for Distributed UAV Traffic Management. Sensors 2019, 19, 4779. https://doi.org/10.3390/s19214779

AMA Style

Samir Labib N, Danoy G, Musial J, Brust MR, Bouvry P. Internet of Unmanned Aerial Vehicles—A Multilayer Low-Altitude Airspace Model for Distributed UAV Traffic Management. Sensors. 2019; 19(21):4779. https://doi.org/10.3390/s19214779

Chicago/Turabian Style

Samir Labib, Nader, Grégoire Danoy, Jedrzej Musial, Matthias R. Brust, and Pascal Bouvry. 2019. "Internet of Unmanned Aerial Vehicles—A Multilayer Low-Altitude Airspace Model for Distributed UAV Traffic Management" Sensors 19, no. 21: 4779. https://doi.org/10.3390/s19214779

APA Style

Samir Labib, N., Danoy, G., Musial, J., Brust, M. R., & Bouvry, P. (2019). Internet of Unmanned Aerial Vehicles—A Multilayer Low-Altitude Airspace Model for Distributed UAV Traffic Management. Sensors, 19(21), 4779. https://doi.org/10.3390/s19214779

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Internet of Unmanned Aerial Vehicles—A Multilayer Low-Altitude Airspace Model for Distributed UAV Traffic Management

Abstract

1. Introduction

2. State of the Art

2.1. Multilayer Networks

2.2. UAV Traffic Management

2.3. Distributed Path Planning

3. Multilayer UTM Model

3.1. Class G Airspace Multilayer Model

3.2. Multilayer Network Model

3.3. UAV Communication

3.4. Operational Example

4. UAV Traffic Optimisation

4.1. Energy-Aware Path Optimisation

4.2. Optimisation Approach

4.2.1. Global Offline Static—UTM (GOS)

4.2.2. Global Probabilistic Dynamic—UTM (GPD)

4.2.3. Local Pheromone Guided—UTM (LPG)

5. Simulation and Results

5.1. Experimental Setup

5.2. Results

5.2.1. Experiment 1: Impact of $p_{r e r o u t i n g}$ on GPD Performance

5.2.2. Experiment 2: Impact of $T_{l i m}$ on LPG Performance

5.2.3. Experiment 3: Performance Comparison of GOS, GPD and LPG

6. Conclusions and Future Work

Author Contributions

Funding

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

Internet of Unmanned Aerial Vehicles—A Multilayer Low-Altitude Airspace Model for Distributed UAV Traffic Management

Abstract

1. Introduction

2. State of the Art

2.1. Multilayer Networks

2.2. UAV Traffic Management

2.3. Distributed Path Planning

3. Multilayer UTM Model

3.1. Class G Airspace Multilayer Model

3.2. Multilayer Network Model

3.3. UAV Communication

3.4. Operational Example

4. UAV Traffic Optimisation

4.1. Energy-Aware Path Optimisation

4.2. Optimisation Approach

4.2.1. Global Offline Static—UTM (GOS)

4.2.2. Global Probabilistic Dynamic—UTM (GPD)

4.2.3. Local Pheromone Guided—UTM (LPG)

5. Simulation and Results

5.1. Experimental Setup

5.2. Results

5.2.1. Experiment 1: Impact of p r e r o u t i n g on GPD Performance

5.2.2. Experiment 2: Impact of T l i m on LPG Performance

5.2.3. Experiment 3: Performance Comparison of GOS, GPD and LPG

6. Conclusions and Future Work

Author Contributions

Funding

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

5.2.1. Experiment 1: Impact of $p_{r e r o u t i n g}$ on GPD Performance

5.2.2. Experiment 2: Impact of $T_{l i m}$ on LPG Performance