**Optimization and Communication in UAV Networks**

Editors

**Christelle Caillouet Nathalie Mitton**

MDPI • Basel • Beijing • Wuhan • Barcelona • Belgrade • Manchester • Tokyo • Cluj • Tianjin

*Editors* Christelle Caillouet Universite C´ ote d'Azur ˆ France Inria France

Nathalie Mitton

*Editorial Office* MDPI St. Alban-Anlage 66 4052 Basel, Switzerland

This is a reprint of articles from the Special Issue published online in the open access journal *Sensors* (ISSN 1424-8220) (available at: https://www.mdpi.com/journal/sensors/special issues/UAV net).

For citation purposes, cite each article independently as indicated on the article page online and as indicated below:

LastName, A.A.; LastName, B.B.; LastName, C.C. Article Title. *Journal Name* **Year**, *Article Number*, Page Range.

**ISBN 978-3-03943-310-0 (Hbk) ISBN 978-3-03943-311-7 (PDF)**

c 2020 by the authors. Articles in this book are Open Access and distributed under the Creative Commons Attribution (CC BY) license, which allows users to download, copy and build upon published articles, as long as the author and publisher are properly credited, which ensures maximum dissemination and a wider impact of our publications.

The book as a whole is distributed by MDPI under the terms and conditions of the Creative Commons license CC BY-NC-ND.

## **Contents**

## **About the Editors**

**Christelle Caillouet** has served as Associate Professor at University of Cote d'Azur since ˆ September 2011 and is a member of the joint team Coati between the I3S (CNRS, University of Nice-Sophia Antipolis) laboratory and Inria. She completed her MSc in Optimization and Game Theory at University Paris VI in 2006, and Ph.D. in Computer Science at University of Nice Sophia Antipolis in 2009. Her research interests are focused on optimization, linear programming, and algorithmics as applied to telecommunication networks (such as wireless mesh networks and backhaul networks) and biological networks.

**Nathalie Mitton** received her M.Sc. and Ph.D. degrees in Computer Science from INSA Lyon in 2003 and 2006, respectively. She received her Habilitation a diriger des recherches (HDR) in 2011 from ` Universite Lille 1. She is currently an Inria Full Researcher since 2006, and has served as Scientific ´ Head of the Inria FUN team from 2012, which is focused on small computing devices like electronic tags and sensor networks. Her research interests focus on self-organization from PHY to routing for wireless constrained networks. She has published her research in more than 30 international revues and more than 100 international conferences. She is involved in the setup of the FIT IoT LAB platform (http://fit-equipex.fr/,https://www.iot-lab.info), the H2020 CyberSANE and VESSEDIA projects, and in several program and organization committees such as Infocom 2019 and 2020, PerCom 2019 and 2020, DCOSS 2019, Adhocnow 2015–2019, ICC (since 2015), Globecom (since 2017), Pe-Wasun 2017, and VTC (since 2016). She also supervises numerous Ph.D. students and engineers.

## **Preface to "Optimization and Communication in UAV Networks"**

Nowadays, Unmanned Aerial Vehicles (UAVs) have received growing popularity in the Internet-of-Things (IoT) which often deploys many sensors in a relatively wide region. Current trends focus on deployment of a single UAV or a swarm of it to generally map an area, perform surveillance, monitoring or rescue operations, collect data from ground sensors or various communicating devices, provide additional computing services close to data producers, etc. Applications are very diverse and call for different features or requirements. But UAV remain low-power battery powered devices that in addition to their mission, must fly and communicate. Thanks to wireless communications, they participate to mobile dynamic networks composed of UAV and ground sensors and thus many challenges have to be addressed to make UAV very efficient. And behind any UAV application, hides an optimization problem. There is still a criterion or multiple ones to optimize such as flying time, energy consumption, number of UAV, quantity of data to send/receive, etc.

This book, which is a Special Issue of the Sensors journal, deals with the wedding of optimization and communication in UAV networks. We hope you will enjoy it. We wish you a pleasant reading.

> **Christelle Caillouet, Nathalie Mitton** *Editors*

### *Editorial* **Optimization and Communication in UAV Networks**

**Christelle Caillouet 1,2,\*,† and Nathalie Mitton 1,\*,†**

Received: 2 September 2020; Accepted: 3 September 2020; Published: 4 September 2020

**Abstract:** Nowadays, Unmanned Aerial Vehicles (UAVs) have received growing popularity in the Internet-of-Things (IoT) which often deploys many sensors in a relatively wide region. Current trends focus on deployment of a single UAV or a swarm of it to generally map an area, perform surveillance, monitoring or rescue operations, collect data from ground sensors or various communicating devices, provide additional computing services close to data producers, etc. Applications are very diverse and call for different features or requirements. But UAV remain low-power battery powered devices that in addition to their mission, must fly and communicate. Thanks to wireless communications, they participate to mobile dynamic networks composed of UAV and ground sensors and thus many challenges have to be addressed to make UAV very efficient. And behind any UAV application, hides an optimization problem. There is still a criterion or multiple ones to optimize such as flying time, energy consumption, number of UAV, quantity of data to send/receive, etc

**Keywords:** UAV; drones; wireless; self-organization; optimization; swarm; communication; algorithms

#### **1. Introduction**

With new technological advances, UAVs are becoming a reality and are attracting more and more attention. UAVs or drones are flying devices that can be remotely controlled or, more recently, completely autonomous. They can be used alone or as a fleet, and in a large set of applications: from rescue operations to event coverage going through servicing other networks such as sensor networks for replacing, recharging, or data offloading. They are hardware-constrained since they cannot be too heavy and rely on batteries. Depending on their use (alone or in a swarm) and the targeted applications, they must evolve differently and meet different requirements (energy preservation, delay of covering an area, coverage, limited number of devices, etc.) with limited resources (energy, speed, etc.). Yet, their use still raises a large set of new exciting challenges, in terms of trajectory optimization, positioning, when they are used alone or in cooperation, coordination, and communication when they evolve in a swarm, just to name a few. This Special Issue was calling for any new original submissions that deal with UAV or UAV swarm optimization or communication aspects. Among the numerous submissions, only twelve of them have been selected after a rigorous selection process. The main themes that arise from them are: (i) ground data collection from the air, (ii) control of UAV swarm UAV-based Mobile Edge Computing and (iii) application-driven UAV based measurements.

In the following, we sum up the contributions of the papers published to this Special Issue for each category to then conclude by drawing future challenges and still open issues.

#### **2. Ground Data Collection from the Air and Path Planning**

It is becoming more and more common to imagine having data sensed from ground wireless sensors collected by UAV to alleviate wireless peer-to-peer communications between ground sensors and reduce their energy consumption. However, such a paradigm raises a set of new challenges such as how to prioritize the sensors to visit, how to optimize the time to collect all data by visiting all devices, etc. This is an exciting optimization problem. Works [1–4] propose different approaches to address this issue with different perspectives. Different criteria are considered to plan the trajectory of the UAV and different functions are optimized.

Reference [1] proposes to visit the nodes in a given order and for a variable time that depend on a node priority, while in [2], the authors aim to maximize the data collection utility by jointly optimizing the communication scheduling and trajectory of each UAV. The data collection utility is determined by the amount and value of the collected data and a novel trajectory planning algorithm is designed to maximize it. The author of [3] focuses on the problem of minimizing the mission completion time (flying time and hovering time) for a multi-UAV system in a monitoring scenario while ensuring that the information of each sensor is collected. As for [4], the authors aim to improve the secrecy performance of cellular-enabled unmanned aerial vehicle communication networks through an aerial cooperative jamming scheme.

#### **3. Control of UAV Swarm**

When more than a drone is required, a swarm of UAVs can be deployed. Although bringing more performances in terms of coverage and connectivity, new optimization challenges pop up due to the difficulty to control and scale such swarms both in a distributed or centralized way. References [5–8] tackle these numerous challenges going from connectivity maintenance to swarm control.

Reference [5] studies the different factors that may impact the accuracy and efficiency of an unmanned aerial vehicle (UAV) swarm coordination. The authors propose a mathematical data model to demonstrate the fundamental properties of antenna arrays and study the performance of the data collection system framework. Numerical examples and practical measurements are provided to demonstrate the feasibility of the proposed data collection system framework using an iterative-MUSIC algorithm and benchmark theoretical expectations.

Reference [6] deals with multi-UAV systems where the UAV autonomy is much smaller than the time to complete their mission. The authors thus introduce a UAV replacement procedure as a way to guarantee ground users' connectivity over time, formulating the practical UAV replacements problem in moderately large multi-UAV swarms and proves it to be an NP-hard problem in which an optimal solution has exponential complexity. Reference [7] focuses on the maintenance formation with time-varying shape of a swarm proposing a virtual leader approach while [8] investigates a stochastic model of the UAV Swarm system with multiplicative noises.

#### **4. UAV Enabled Mobile Edge Computing**

The potential offered by the abundance of sensors, actuators, and communications in the Internet of Things (IoT) era is hindered by the limited computational capacity of local nodes. However, the latter do not necessarily always have the capacity to offload data to an edge server. In such a case, mobile edge servers can go to them thanks to the deployment of UAV-assisted Multi-access Edge Computing systems, which raises new challenging optimization and networking issues as addressed in [9,10].

Reference [9] proposes to provide an Unmanned Aerial Vehicle (UAV)-assisted Multi-access Edge Computing (MEC) system based on a usage-based pricing policy for allowing the exploitation of the servers' computing resources while the authors of [10] introduce the DRUID-NET perspective, aiming to adapt to a rapidly varying demand by applying different tools from Automata and Graph theory, Machine Learning, Modern Control Theory, and Network Theory combined.

#### **5. Application-Driven UAV Based Measurements**

In such cases, the application that has asked for UAV deployment comes with very specific constraints and requirements and calls for specific optimization models. Reference [11,12] gives two such examples dedicated respectively for three-dimensional measurements and surveillance.

For instance, Reference [11] aims to provide a comparative analysis of the precision of ground geodetic data versus the three-dimensional measurements from unmanned aerial vehicles (UAV), while establishing the impact of herbaceous vegetation on the UAV 3D model. A constraint to take into account in this application is the fact that herbaceous vegetation can impede the establishment of the anthropogenic roughness of the surface and deteriorates the identification of minor surfaces.

Reference [12] focuses on UAV cooperative surveillance networks and introduces the use of complex field network coding (CFNC) for this application. According to whether there is a direct communication link between any source drone and the destination, the information transfer mechanism at the downlink is set to one of two modes, either mixed or relay transmission, and two corresponding irregular topology structures for CFNC-based networks are proposed. Theoretical analysis and simulation results with an additive white Gaussian noise (AWGN) channel show that the CFNC obtains a throughput as high as 1/2 symbol per source per channel use. Results show that CFNC applied to the proposed irregular structures under the two transmission modes can achieve better reliability due to full diversity gain as compared to that based on the regular structure.

#### **6. Conclusions**

As you can notice, challenges in UAV networks are huge, numerous and heterogeneous. They are concerning different aspects of the deployment of drones, from path trajectory to connectivity maintenance going through energy management. Much of them have been addressed with optimization tools but there remain a lot of open issues and research directions. Contributions presented in this special issue are only a first step to pave the way towards even more exciting investigations.

**Funding:** This research received no external funding.

**Conflicts of Interest:** The authors declare no conflict of interest.

#### **References**

c 2020 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/).

## *Article* **Priority-Based Data Collection for UAV-Aided Mobile Sensor Network**

#### **Xiaoyan Ma 1, Tianyi Liu 2,\*, Song Liu 1, Rahim Kacimi 3 and Riadh Dhaou 4**

Received: 31 March 2020; Accepted: 25 May 2020; Published: 27 May 2020

**Abstract:** In this work, we study data collection in multiple unmanned aerial vehicle (UAV)-aided mobile wireless sensor networks (WSNs). The network topology is changing due to the mobility of the UAVs and the sensor nodes, so the design of efficient data collection protocols is a major concern. We address such high dynamic network and propose two mechanisms: prioritized-based contact-duration frame selection mechanism (PCdFS), and prioritized-based multiple contact-duration frame selection mechanisms (PMCdFS) to build collision-free scheduling and balance the nodes between the multi-UAV respectively. Based on the two mechanisms, we proposed a Balance algorithm to conduct the collision-free communication between the mobile nodes and the multi-UAVs. Two key design ideas for a Balance algorithm are: (a) no need of higher priority for those nodes that have lower transmission rate between them and the UAV and (b) improve the communication opportunity for those nodes that have shorter contact duration with the UAVs. We demonstrate the performance of proposed algorithms through extensive simulations, and real experiments. These experiments using 15 mobile nodes at a path with 10 intersections and 1 island, present that network fairness is efficiently enhanced. We also confirm the applicability of proposed algorithms in a challenging and realistic scenario through numerous experiments on a path at Tongji campus in Shanghai, China.

**Keywords:** wireless sensor networks; multiple unmanned aerial vehicles; mobile nodes; data collection; collision-free

#### **1. Introduction**

Unmanned Aerial Vehicle-aided wireless sensor networks (UAV-aided WSN) have gained more and more interest due to their many applications in monitoring, surveillance, and exploring in healthcare, agriculture, industry, and military [1–5]. Among UAVs' applications, one of the key functions is the data collection [6–11]. These works focus on deterministic topology where the nodes are deployed statically, and the locations of the sensors are known. The data collection issues addressed on dynamic topology, which are usually used in applications such as maritime detection, traffic surveillance, and wilderness rescuing where the targets are moving and no static sensors are deployed in advance, are seldom covered.

The main difference between the static network and mobile network are: the transmission opportunities for nodes that are within the coverage of the UAV are different. In static case, all covered nodes are static, the relative velocity (*vr*) between the nodes and the UAV are the same. Thus, the contact durations (CD) between them with the UAV depend on the relative distance (*dr*) between them (*CD* = *dr vr* , see [12,13] for more details). The relative distances almost have no difference if the UAV flies at a higher altitude. However, in mobile case, when the nodes move at different velocities, the

CD are different greatly even the relative distance is the same. Intuitively, the shorter the CD between them, the smaller the opportunities for the mobile node to communicate with the UAV. When the CD is very short, the mobile node may have no opportunity to communicate with the UAV if no attention is paid on the CD between it with the UAV. Thus, a contact-duration-based data collection algorithm should be designed for such context despite a large array of existing data collection algorithms (see Section 2. related works) on UAV-aided static WSNs.

The impact factors of the CD between mobile nodes and the UAV include two aspects: (a) the relative distance between the sensor and the UAV, and (b) the relative velocity between them. Priority-based Frame Selection (PFS) [14,15] is a one-hop mechanism based on the relative distance according to which the nodes are divided into different priority groups. Communications are conducted from higher to lower priorities. A multi-hop highest velocity opportunistic algorithm which is based on relative velocity between mobile nodes and the UAV is proposed in [16]. The ones that have higher velocity have longer CD with the UAV, therefore were selected as forwarded nodes. In our previous work [12,13], we studied the data collection maximization issues in single UAV enabled mobile WSN where the pre-defined path is a straight path without comparison with existing works and real experiments. The curve path and multi-UAVs aspects are also not covered in the previous work. Thus, a large room for enhancing the network performance still exists.

In this work, we focus on multi-UAV aided mobile WSN, Figure 1, where the nodes are deployed on mobile bicycles and move along a pre-defined curve path. Considering that, in the context of the nodes move along a path, two UAVs are enough to cover all mobile nodes when (as in Figure 1) *UAV*1 take-off from the original point of the path and fly along the path, *UAV*2 take-off from the end-point of the path and fly along the path. Data collection issues in such contexts contain two aspects. End-to-end data collection is a very complex problem. In this paper, we focus on the access link. As the literature, on this kind of link between the sensors and the UAV [6,7], still does not propose efficient solutions. The access link suffers from the synchronization problem due to the high dynamic network, the coordination between the mobile nodes and the multi-UAVs. Providing the opportunity of communication to the nodes that have a very short duration with the UAVs reduces the congestion risk. On the other hand, extensive literature can be referred to, on the second link, on the backhaul link, between the UAVs and gateways [17]. The second link is also challenging on several levels such as the data security, the security of UAVs, and the dimensioning of the backhaul. In our previous work [18,19], we focused on the backahul link with the satellite system. The proposed algorithms on mobile mules, in [18,19] are applicable for UAV-aided sensor networks. Moreover, because that the collected data (considering the value of data and distinguish the data collected from each sensor) could be stored in SD cards embedded on the UAV, thus, in this work, we focus on the access link. The data collection optimization objectives in such context include two aspects: (i) maximizing the number of collected packets, and (ii) maximizing the number of nodes that successfully send at least one packet during the collection period. Our main purpose is to jointly maximize the two aspects through formulating the dynamic parameters. Our main contributions are summarized as follows:

one-hop and slotted mechanism which is used to allocate the time-slot for the nodes that covered only by one of the UAVs.

**Figure 1.** An illustration of the unmanned aerial vehicle (UAV)-aided data collection for a mobile wireless sensor network. The exemplar trajectory of the *UAV*1 is shown as: Waypoint *P*1 *S* → Waypoint *P*1 1 → Waypoint *P*1 2 → Waypoint *P*1 3 → Waypoint *P*1 4 → Waypoint *P*1 5 → Waypoint *P*1 6 → Waypoint *P*1 *E*.

The remainder of this paper is organized as follows: in the next section, we discuss previous related work. Section 3 presents the system model and the problems formulated. Section 4 present the proposed algorithms. Section 5 evaluated the proposed algorithms through extensive simulations and real experiments. Section 6 concludes this paper and gives some future work suggestions.

#### **2. Related Works**

There exists an extensive array of research on data collection in UAV-aided WSN with different objectives ranging from completion time minimization [20], power controlling [21], trajectory distance minimizing [22] to energy consumption minimization [23,24]. We classify these existing data collection algorithms by two criteria: (i) Static or mobile nodes, and (ii) sensors are deployed along a path or deployed within an interesting area. In (i), algorithms are differentiated by whether the sensors mobile or not because the dynamic parameters brought by the movement of nodes in the network structure have a much greater impact on the system performance. In (ii), algorithms are differentiated by whether the nodes deployed along a path or not. The nodes deployed along a given path [12,13,25,26] so the UAV trajectory planning has very little impact on the network performance.

(i) Data collection algorithms addressed on mobile nodes. There are many works on studying how to collect data from WSN. The authors in [4,9,27–29] review these works. According to the [4,9,27–29], most of these algorithms only based on the mobile sink or only focused on mobile sensors. In our previous works [12,13,16], we studied how to use UAV to collect data from mobile nodes based on an assumption that both the nodes and the UAV move along a straight path with constant speeds. The case where both the UAV and the nodes move in a curved path is not considered. Numerous researches have been done on statically deployed networks [6,7,11,14,15,20,24,25,30–40].

(ii) Most of the aforementioned data collection algorithms can also be classified according to the deployed status of the nodes. Authors in [12,13,16,25,34] studied how to use UAV to collect data from nodes that deployed along a straight path. Especially in [25], the nodes deployed on a straight line, and the UAV flies over this line to collect data from nodes. In such context, the trajectory of the UAV is dependent on the path (or line) and has a light impact on the performance if the path is long enough. For instance, in [25], the authors aim to minimize the flight time through jointly optimizing the transmit power of nodes, the UAV speed and the transmission intervals. For the case that nodes are deployed within the area of interest, one of the main issues is to plan the UAV's trajectory so as to enhance the network performance. Numerous research has been done on the UAV trajectory planning issues [6,7,20,24,30–40]. These works are different from the optimization method and objective function because of different scenarios. They are mainly classified into two types: single-UAV trajectory planning [6,7,24,30–34] and multi-UAV trajectory planning [20,35–40].

The first is the single-UAV trajectory planning. Authors in [33] use a UAV for the mobile edge computing system. They minimize the maximum delay of all ground users through jointly optimizing the offloading ratio, the users' scheduling variables, and UAV's trajectory. While, in [24], the authors aim to minimize the maximum energy consumption by optimizing the trajectory of a rotary-wing UAV. The authors utilize a UAV to collect data from IoT devices with each has limited buffer size and target data upload deadline [6]. In this study, the data should be transmitted before it loses its meaning or becomes irrelevant. To maximize the number of served IoT devices, they jointly optimize the radio resource allocation and the UAV's trajectory.

The second is the multi-UAV trajectory planning. Multi-UAVs were used as mobile base stations to provide service for ground users in [38]. They aim to maximize the minimum throughput of ground users by optimizing the trajectory for each UAV. Scholars in [20] employ multi-UAVs to collect data from nodes. Through jointly optimizing the trajectories of UAVs, wake-up association and scheduling for sensors, they minimize the maximum mission completion time of all UAVs. The authors studied a multiple casting network utilizing the UAV to send files to all ground users [37]. They aim to minimize the mission completion time of the UAVs through designing the UAV's trajectory. Meanwhile, the proposed algorithms guarantee that each ground user can successfully recover the file. In urban applications, the authors proposed a risk-aware trajectory planning algorithm [36] for multi-UAVs. Under the same test scenarios, authors in [39] aim to minimize the mission time by planning the trajectory of each UAV. The scholars exploit the nested Markov chains to analyze the probability for successful data transmission [40]. They propose a sense-and-send mechanism [40] for real-time sensing missions, and a multi-UAVs enabled Q-learning algorithm for decentralized UAV trajectory planning.

In other cases. The authors in [11] use a single UAV to collect data from harsh terrains. Due to the large scale of the detection area, the network has a high demand for power. They adopted a rechargeable mechanism to extend the lifetime of the UAV so as to enhance the collection period. The PFS mechanism in [14,15] is based on the nodes' positions for the data collection in single-UAV aided static sensor networks. The nodes are divided into different priority groups according to two steps: (i). increasing group and decreasing group (Figure 2). The nodes within the decreasing group was given higher priority than the ones within the increasing group. (ii). For each group in (i), the nodes were divided into sub-groups according to which power level does it belong to. The sets of nodes within "power level 1" in the increasing group and in the decreasing group are denoted by S1 *a*,*I* and S1 *a*,*D*, respectively. The priority values for nodes within S1 *a*,*I* and S1 *a*,*D* are denoted by *P*1 *a*,*I* and *P*1 *a*,*D*, respectively. The authors give high priority to those nodes that are within high power level (Figure 2), and applied opposite actions to the increasing and decreasing groups: (a) in the increasing group, the nodes within high power level was given high priority value; (b) in the decreasing group, the nodes within lower power level were given high priority. After these actions, almost all nodes at the best channel conditions have been considered.

Table 1 presents the key focuses and the key difference of our proposed algorithms from existing algorithms. Although a lot of research has been done on data collection, there is still room to enhance the network performance through balancing the dynamic parameters in the first link in mobile sensor networks.

**Table 1.** Summary of related works.

**Figure 2.** The Priority Frame Selection (PFS) mechanism.

#### **3. System Model and Problem Formulation**

#### *3.1. System Model*

This paper considers a UAV-assisted mobile sensor network which has *N* mobile bicycles with each equipped a sensor, and *M* UAVs with each equipped a sensor (as illustrated in Figure 1, where *M* = 2). S = {*S*1, *S*2, ··· , *SN*} is the set of mobile sensors. *N* nodes move along a pre-defined path (path length is denoted as *L*) with each has a speed *vi*. The UAV *Ui* is dispatched to collect data from mobile sensors at a given height *hi* and speed *vi u* along a predefined trajectory (Figure 1).

The trajectory consists of a few line segments that contain the waypoint start and waypoint end (e.g., in Figure 1, waypoint *Pi S* and waypoint *Pi E* in the trajectory of *UAVi*, *i* = 1, 2), and *k* intermediate waypoints (e.g., in Figure 1, waypoint *Pi* 1, waypoint *Pi* 2, waypoint *Pi* 3, waypoint *Pi* 4, waypoint *Pi* 5 and waypoint *Pi* 6 in the trajectory of *UAVi*, *i* = 1, 2). Let P*i* = {*Pi S*, *Pi* 1, *Pi* 2, ··· , *Pi k*, *Pi E*} denote the set of all waypoints of *UAVi*. The coordinates for each waypoint *Pi m* is denoted by *Pi m*(*xi m*, *yi m*, *hi*). The UAV's flight time between any two waypoints *Pi m* and *Pi n* is given by,

$$\lambda\_{m,n}^i = \frac{\left\| \left| P\_m^i - P\_n^i \right| \right\|}{\upsilon\_n^i}, \quad P\_{m'}^i P\_n^i \in \mathbb{P}\_i. \tag{1}$$

The collection period of the *UAVi* is the duration from waypoint *Pi* 1 to the waypoint *Pi E*. It is denoted by *Ti*,

$$T\_i = \Sigma\_{m=1}^{k-1} \lambda\_{m,m+1}^i + \lambda\_{k,E}^i. \tag{2}$$

The trajectory length for *UAVi* is,

$$L\_i = \Sigma\_{m=1}^{k-1} \parallel P\_{m+1}^i - P\_m^i \parallel + \parallel P\_E^i - P\_k^i \parallel \,. \tag{3}$$

Generally, in a given path, the coordinates (x-axis and y-axis) of the waypoints for the UAVs are the same except the height (z-axis). For instance, the point (*xi m*, *yi m*, *hj*) is one of the waypoints for *UAVj* (i.e., *Pj m*(*xi m*, *yi m*, *hj*) ∈ P*j*) if *Pi m*(*xi m*, *yi m*, *hi*) ∈ P*i*. Thus, we have *Li* = *Lj*. Intuitively, the straighter the pre-defined path, the smaller the Δ*L* (Δ*L* = |*L* − *Li*|). The larger the number of waypoints, the smaller the Δ*L*. Major notations used in this work are defined in Table 2.

**Table 2.** Major notations used in this article.

To well present the impact of the dynamic parameters on the system, we using homogeneous UAVs (*vi u* = *v*) to reduce the influence brought by UAVs' speeds. Accordingly, the collecting period is denoted by *T*, and *T* = *Ti*.

#### *3.2. Discrete Time Mechanism*

Considering the waypoint selection and beacon sending, we introduce a discrete-time mechanism where the collecting period *T* is divided into *Nts* time-slots with each lasting *α* time units, *Nts* = - *T α* , where · is the rounding down function. It is assumed that the time-slots are indexed as 1, 2, ··· , *Nts*, and T = {*t*1, *t*2, ··· , *tNts*} (Figure 3). It is worth note that, in each time slot, a sensor could communicate only with one UAV. For example, in *tk*, *Si* communicate with *UAVm*, and *Sj* communicate with *UAVn* (*i* = *j* and *m* = *n*).

**Figure 3.** An illustration of studied scenario.

From Figure 1, the nodes that are covered by the *UAVi* and deployed nearly complete to communicate with the *UAVi*. For instance, *Sm*, *Sn*, *Sk* in Figure 1 complete to communicate with the *UAV*1. Meanwhile, there are more than one UAV within the range of one node. For example, *Sk* in Figure 1 with the range of both *UAV*1 and *UAV*2. The *Sk* should choose one from them to send packets. Hence, how to balance the communication between nodes and the UAVs so as to maximize the data collection is a challenging task.

#### *3.3. Data Collection Protocols Using UAV*

In this paper, we present a distributed method for the data collection issues in UAV-aided mobile sensor networks as follows. The collection period *T* is divided into *Nts* time slots. At the beginning of every time slot (Figure 4), UAV sends a beacon message to tell the mobile nodes that UAV is coming. The beacon includes the UAV's information, e.g., the aerial height, speed, etc. The new comers send a JOIN message which includes the sensors' information to the UAV to update the network topology. The UAV judges whether the nodes are within its range or not according to these messages. Then, it calculates the contact duration, the relative distance, and the potential time slots for each node that successfully sends the JOIN message. According to the time slot allocation algorithms that we proposed in Section 4, the UAV provides scheduling for the covered sensors, and broadcasts them a scheduling message which contains the assignment of the time-slots. Having received the scheduling message, every sensor transmits its data in its own time slots.

**Figure 4.** The procedure of allocating.

#### 3.3.1. Collecting Packets

Allocating the *Nts* time slots to individual mobile sensors under the proposed mechanism is equivalent to maximizing the usage of time slots. Let

$$N\_{\rm ts,a}(i,j,k) = \begin{cases} 1 & \mathcal{U}AV\_i \text{commuuricate with } S\_j \text{int}\_k\\ 0 & \text{otherwise.} \end{cases}$$

The data collection maximization problem is to maximize the number of collected packets, *Np*,

$$N\_p = \sum\_{i=1}^{M} \sum\_{j=1}^{N} \sum\_{k=1}^{N\_{ls}} N\_{ts,a}(i, j, k) \cdot \sigma\_{i\bar{j}k} \cdot D\_r \cdot \alpha \ . \tag{4}$$

time

where *Dr* is the transmission rate, and

$$
\sigma\_{ijk} = \begin{cases} 1 & \text{successfully transmission} \\ 0 & \text{otherwise.} \end{cases}
$$

Our objective is to balance the communication between the two UAVs and *N* mobile nodes to maximize the overall data collection utility. Therefore, the optimization problem can be formulated as,

$$\left\{ \begin{array}{l} \mathcal{O}\_1 \\ \end{array} \right. \quad \mathrel{\mathop{:}} \max\_{\left\{ \begin{array}{l} S\_p \in \mathbb{S}, t\_k \in \mathbb{T} \end{array} \right\}} \left\{ N\_p \right\} \,, \tag{5}$$

$$\text{s.t.} \qquad \sum\_{k=1}^{N\_{\text{ts}}} \mathcal{N}\_{\text{ts},a}(i, j, k) \le \mathcal{N}\_{\text{ts}}, \forall i, j \,\,. \tag{6}$$

$$\sum\_{j=1}^{N} \mathcal{N}\_{ts,d}(i, j, k) \le \mathcal{N}\_{\prime} \,\forall i, k\_{\prime} \tag{7}$$

$$\sum\_{i=1}^{M} N\_{ts,a}(i,j,k) \le M \text{ } \forall j,k \tag{8}$$

$$\sum\_{i=1}^{M} \sum\_{j=1}^{N} \sum\_{k=1}^{N\_{\rm ts}} \mathbf{N}\_{\rm ts,a}(i,j,k) \le M \cdot \mathbf{N}\_{\rm ts}, \forall i, j \,. \tag{9}$$

Constraints (6)–(8) imply that, in a given time-slot, a UAV chooses only one node to collect data, and one node selects only one UAV to send data. Constraint (9) ensures that, in a given time-slot, no more than two communications happen between UAVs and mobile nodes.

#### 3.3.2. The Number of Nodes that Successfully Send Packets to the UAV

During the communication between the UAVs and mobile nodes, the sensors transmission state contains: have no opportunity to send packets, have an opportunity to send but fail to transmit, and successfully send data to the UAVs. The larger number of nodes (*Nnode*) that successfully transmit packets, the higher the system performance. Thus, to enhance the number of nodes that successfully send data to the UAVs is one of the key points in designing data collection algorithms.

Let matrix *IM*×*N*×*Nts* is given by,

$$I\_{ijk} = N\_{ts,a}(i,j,k) \cdot \sigma\_{ijk} \cdot i\_{\prime} \qquad \mathcal{U} \\ \text{A} \\ V\_{i} \in \mathbb{U}, \\ S\_{j} \in \mathbb{S} \\ \\ and t\_{k} \in \mathbb{T}.$$

The elements in matrix *I* are the node ID. Then, we can obtain the number of nodes that successfully transmit at least one packet,

$$N\_{nodc} \stackrel{\triangle}{=} Hist(I). \tag{10}$$

where "*Hist*" is used to calculated the number of different elements in the *I* matrix. The *Nnode* maximization problem can be regarded as the formulated problem,

$$\beta\mathcal{P}\_2: \max\_{S\_f \in \mathbb{S}, t\_k \in \mathbb{T}} \{N\_{node}\}\_\prime \tag{11}$$

$$\text{s.t.} \qquad \sum\_{k=1}^{N\_{\text{tr}}} \mathcal{N}\_{\text{ts},a}(i, j, k) \le \mathcal{N}\_{\text{ts}}, \forall i, j \,\,. \tag{12}$$

$$\sum\_{j=1}^{N} N\_{ts,a}(i,j,k) \le N \text{ } \forall i,k \text{ } \tag{13}$$

$$\sum\_{i=1}^{M} N\_{ts,a}(i,j,k) \le M \text{ } \forall j,k \,\,\, \tag{14}$$

$$\sum\_{i=1}^{M} \sum\_{j=1}^{N} \sum\_{k=1}^{N\_{ts}} N\_{ts,a}(i\_{\prime}j\_{\prime}k) \le M \cdot N\_{ts} \; \forall i\_{\prime}j \; . \tag{15}$$

When *i* = 1 (single-UAV enabled sensor network), it is a classical NP-hard problem that we have studied in [12,13]. When *i* = 2 (multi-UAV enabled sensor network), this problem is also an NP-hard combinatorial maximization problem [41]: under the given conditions, its objective is to select items which have unique weight and value to maximize the total value.

#### **4. Proposed Algorithms**

In this section, we study how to balance the communication between multi-UAVs and mobile nodes, and we propose a balance mechanism. For the two cases, multiple nodes within the range of both two UAVs and multiple nodes only with the range of only one UAV, we propose two algorithms: PCdFS (Section 4.2) and PMCdFS (Section 4.3) algorithms.

#### *4.1. Balance Algorithm between UAVs and Mobile Nodes*

In a given time slot *tk* (*tk* ∈ T), there are multiple nodes within the range of the UAV. The nodes that are potentially for *UAV*1 and *UAV*2 are denoted by S1 *kB* and S2 *kB* respectively. When S1 *kB* ∩ S2 *kB* = ∅, there is no node within the range of the *UAV*1 and *UAV*2 at the same time. In this case, we propose PCdFS mechanism (see Section 4.2 for more details) to balance the communications between S1 *kB* and *UAV*1, S2 *kB* and *UAV*2 respectively. When S1 *kB* ∩ S2 *kB* = ∅, and S1,2 *kB* - S1 *kB* ∩ S2 *kB*. Then,

$$\mathbb{S}^{1,o}\_{kB} \triangleq \mathbb{S}^1\_{kB} - \mathbb{S}^{1,2}\_{kB\ \prime} \tag{16}$$

$$\mathbb{S}\_{kB}^{2,\rho} \triangleq \mathbb{S}\_{kB}^2 - \mathbb{S}\_{kB}^{1,2} \tag{17}$$

S1,*o kB* and S2,*o kB* denote the sensors set only within the range of the *UAV*1 and *UAV*2 respectively. We use the PCdFS mechanism to balance the communications between S1,*o kB* and *UAV*1, S2,*o kB* and *UAV*2 respectively. For the nodes within S1,2 *kB* , we proposed the PMCdFS algorithm to balance between | S1,2 *kB* | mobile nodes and multi-UAVs. The Balance algorithm is detailed in Algorithm 1.

**Algorithm 1** Balance Algorithm.

**Input:** Initial deployed information of nodes and UAVs

**Output:** *Np, Nnode* 1: *Np* = *Nnode* = 0, *k* = 1, *Tnow* = 0; 2: **Step 1. Synchronization;** 3: UAV sends *k*-th 'Beacon' message; 4: Network update, obtain the S1 *kB* and S2 *kB* ; 5: **Step 2. Data Communication;** 6: **while** *Tnow* < *T* **do** 7: Let S1,2 *kB* - S1 *kB* ∩ S2 *kB*, S1,*o kB* - S1 *kB* − S1,2 *kB* , and S2,*o kB* - S2 *kB* − S1,2 *kB* ; 8: **if** S1,2 *kB* = ∅ **then** 9: Apply PCdFS mechanism (Algorithm 2) to balance the communication between S1,*o kB* and *UAV*1, S2,*o kB* and *UAV*2 respectively; 10: **else** 11: Apply PMCdFS algorithm (Algorithm 3) for the balancing between mobile nodes in S1,2 *kB* and multi-UAVs, and obtain S1 *kB* and S2 *kB* through PMCdFS algorithm; 12: Apply PCdFS mechanism (Algorithm 2) to balance the communication between S1,*o kB* and *UAV*1, S2,*o kB* and *UAV*2 respectively; 13: **end if** 14: Update *Tnow*, *k*, *Np* and *Nnode*; 15: **end while** 16: **return** *Np* and *Nnode*;

*4.2. Priority-Based Contact-Duration Frame Selection Mechanism*

In the PCdFS mechanism, the priority areas division includes two steps: (i) divide the nodes into different groups according to their power level. For example, the nodes are divided into two groups and three groups in Figures 3 and 5, respectively. In Figure 3, *Si*1 and *Si*2 are within the same priority area (level 2), *Si*3 , *Si*4 and *Si*5 are within level 2. If we take more priority levels into account, e.g., 3 levels as in Figure 5, *Si*1 and *Si*2 belong to level 1, *Si*4 is in level 2, *Si*3 and *Si*5 are in level 3. The more levels, the more detailed group. (ii) For each group, the nodes are given different priority according to their contact duration with the UAV. The ones that have short CD with the UAV are given higher priority values. In PCdFS, different nodes are given different priority values except the case that more than one node have the same CD with the UAV. In PCdFS, it makes the nodes facing a connection lose with the UAV highly concerned. In addition, PCdFS provides the nodes within a higher power level to send data exactly at the moment of their good channel condition so as to reduce the packet's loss. The PCdFS algorithm is detailed in Algorithm 2.

**Figure 5.** Priority areas.

**Algorithm 2** Prioritized-based contact-duration frame selection mechanism (PCdFS) Algorithm.

**Input:** Initial deployed information of nodes and UAVs, S1 *kB*, S2 *kB*, *Np*, *Nnode*.

**Output:** *Np, Nnode*

priority area, *tk* allocated to the one (e.g., *Sik* for *UAV*1, and *Sjl* for *UAV*2) which has the shorter contact duration with the UAV.

#### *4.3. Priority-Based Multiple-Contact-Duration Frame Selection Mechanism*

The PMCdFS algorithm is used to balance the communications between the UAVs and nodes when these nodes are within the range of the multi-UAVs at the same time. Intuitively, the longer the CD between the nodes and the UAV, the higher the opportunity to send packets to the UAV. Thus, it increases the transmission opportunity of the node if it was arranged to the UAV which has a longer CD between it and the UAV. The PMCdFS is detailed in Algorithm 3. Through the PMCdFS algorithm, we obtain the sensors set in which all nodes only compete to communicate with a single UAV (*UAV*1 or *UAV*2). Then, we apply the PCdFS algorithm to conduct the communication among them. The proposed algorithms are summarized in Table 3.

**Algorithm 3** Prioritized-based multiple contact-duration frame selection mechanisms (PMCdFS) algorithm.

**Input:** Initial deployed information of nodes and UAVs, S1,2 *kB* , S1 *kB*, S2 *kB*.

**Output:** S1 *kB and* S2 *kB*

1: **for** ∀*Si* ∈ S1,2 *kB* **do**

2: Calculate the *contact duration* between *Si* and the *UAV*1 (denoted as *Ti*,1), the *UAV*2 (denoted as

```
Ti,2), respectively;
3: if Ti,1 < Ti,2 then
4: S2
          kB = S2
                kB ∪ {Si} ;
5: else
6: S1
          kB = S1
                kB ∪ {Si} ;
7: end if
8: end for
9: return S1
          kB and S2
                   kB;
```

In the following, we will evaluate the proposed algorithms through different configurations, and compare our proposed algorithms with the existing algorithm (PFS).

#### **5. Implementation and Evaluation**

We implement the algorithms in both simulations and real experiments as following.

#### *5.1. Simulations*

We conduct the simulations in MATLAB/Simulink where the UAV fly (5 min) along a path (the path is 10 m wide). The simulated priority groups are {2, 3, 4, 5} groups. The other simulation parameters are presented in Table 4, the final results are given by the mean of 30 simulation runs. Considering that, the PFS mechanism is proposed and examined based on a single-UAV sensor network. To compare it to the proposed algorithm, we use *M* = 1 in the simulations in Sections 5.1.1–5.1.4. In Section 5.1.5, we compare our proposed algorithms when using single UAV and multiple UAVs. All the simulations are summarized in Table 5.

**Table 4.** Simulation parameters.

**Table 5.** Summary of simulations.

#### 5.1.1. Impact of Priority Level Changes

Figure 6 presents the impact of varying the number of priority groups. The more priority groups, the smaller number of collected packets. The number of collected packets is much improved at two priority groups division as compared to five priority groups division. That is because the nodes in lower priority groups may have changed their state when it was their turn to send packets. The introduction of contact duration provides high priority to them so as to overcome a part of this issue, thus more packets were collected in PCdFS algorithm.

**Figure 6.** Impact of priority area change. In these simulations, the proposed algorithm is the combination of proposed Balance and prioritized-based contact-duration frame selection mechanism (PCdFS) algorithms.

It also can be concluded that at a larger number of priority groups, a smaller number of nodes were within the highest priority group. Then, the smaller number of nodes have opportunities to send packets, which is unfair for the network. The number of nodes that successfully sent at least one packet in the proposed Priority-based Contact-duration Frame Selection mechanism was 16.2 times larger than in the PFS mechanism which is because the dynamic parameters are concerned in the proposed algorithm.

In the following, in both simulations and real experiments, the number of priority groups is fixed at 2.

#### 5.1.2. Varying Beacon Intervals

Figure 7 shows that both *Np* and *Nnode* were much improved when the inter-beacon duration at 2 s. Indeed, the longer the beacon intervals, the smaller the number of beacons sent. Thus, the number of network synchronizations is reduced so that nodes were seldom detected during collecting. No node will be detected if no beacon is sent.

**Figure 7.** The impact of inter-beacon duration on network performance. In these simulations, the proposed algorithm is the combination of proposed Balance and PCdFS algorithms.

#### 5.1.3. Impact of UAV's Parameters Changes

Figure 8 shows the impact of the total number of collected packets for varying the UAV speed and fly height. The network achieves the optimal (*Nnode* = 46.5 of 30 simulations) when the fly height is 15 m (Figure 8a). In this simulation, the UAV speed is 10 ms−1, and the size is 200 with nodes speeds vary from 1 ms−1 to 10 ms−1. Due to using fixed *Dr*, the flight height had very slight impact on both *Np* and *Nnode*. The contact duration which was given by the relative distance between the nodes and the UAV was highly affected by the fly height. Hence, the PCdFS algorithm presents a difference from the PFS mechanism when the fly height is 95 m. Compared to *Np*, the *Nnode* was affected much when the fly height is larger than 75 m. There is clearly a difference between the two mechanisms when the gap between different fly heights exceeds 50 m.

The change of the UAV speed has a huge impact on both the total number of collected packets and the number of nodes that successfully send packets to the UAV Figure 8b. When the gap between the UAV speed and the maxi speed of all nodes is very small, the network performance is optimal. In this studied scenario, the maxi speed for all nodes is 10 ms−1, thus, the performance is optimal when the UAV speed is 10 ms−1. When *Vuav* > 10 ms−1, the higher the *Vuav*, the bigger gap between the UAV speed and the nodes' speeds, the shorter contact duration between them, then, the less opportunities for nodes to communicate with the UAV. Then, the smaller number of packets sent to the UAV, the more it was unfair for the network.

**Figure 8.** Network performance for varying UAV' parameters: flight height and speed. In these simulations, the proposed algorithm is the combination of proposed Balance and PCdFS algorithms. (**a**) The number of collected packets for the network for varying fly height of the UAV. The number of nodes that successfully send packet to the UAV in the same scenario. (**b**) The number of collected packets for the network for varying UAV' speed. The number of nodes that successfully send packet to the UAV for varying the speed of the UAV.

#### 5.1.4. Scalability

Figure 9 shows the impact of the network size on system performance. In this study, the flight height is 15 m and UAV's speed is 10 ms−1 and the size vary from 5 to 200 with nodes' speeds vary from 1 ms−1 to 10 ms−1.

The larger the network size, the larger number of nodes has the opportunity to communicate with the UAV, thus, the larger number of packets were sent to the UAV. When the size was larger than 30, each time-slot has successful communication, thus, the number of collected packets in the PFS mechanism keeps steady. It keeps increasing in the PCdFS algorithm until it reaches the transmission upper bound of the collection time. The *Nnode* increased steadily in the proposed algorithm. The *Nnode* when *N* = 200 in the proposed algorithm is 11.34 times larger than when *N* = 5 while it is almost the same in the PFS mechanism. Hence, the proposed algorithm shows high scalability in terms of sensors density.

**Figure 9.** Evaluation of proposed algorithm (the combination of proposed Balance and PCdFS algorithms) on network size.

#### 5.1.5. Comparison between Multi-UAVs and Single-UAV

Figure 10 presents the impact of proposed algorithms on the network size. "Alg1/*UAV*1" simulate the combination of proposed Balance and PCdFS algorithms on the *UAV*1 which takes-off from the original point of the path, while "Alg1/*UAV*2" simulate the same combination algorithms on the *UAV*2 which takes-off from the endpoint (the midline of the path) of the path. *UAV*1 fly in the same direction as the nodes while *UAV*2 fly in the opposite direction. Intuitively, the average contact duration between the *UAV*1 and the nodes is longer than the average value between *UAV*2 and the nodes. Thus, the communication conducted in the *UAV*1 case works better than in *UAV*2. There is no doubt that the multi-UAVs work better than single UAVs in data collection issues because of more opportunity provided for mobile nodes.

**Figure 10.** The impact of *UAV*1, *UAV*2 and multi-UAVs of proposed algorithm on network size. In these simulations, "Alg1" is the combination of proposed Balance and PCdFS algorithms, "Alg2" is the combination of proposed prioritized-based multiple contact-duration frame selection mechanisms (PMCdFS), PCdFS, and Balance algorithms.

#### *5.2. Real Experiment*

#### 5.2.1. Set Up

We study a path in Tongji University (Jiading Campus) as in Figure 11a. It is 5 meters wide and 1200 m long, with several intersections and 1 island (Figure 11a). In these experiments, the UAV equips a Pixhawk autopilot system [42,43] (as shown in Figure 11b) so as to fly along a predefined path at a given height. The UAV controlled through a ground station (Figure 12) where the flight height, speed and the packet transmission are controlled. We implement 15 bicycles move along the path with each equips a Pixhawk to simulate the communications based on proposed algorithms (Figure 11c). These nodes start with a random distance from the original point (point A in Figure 11a). Their locations and speeds are expressed in the NED coordinate system, as presented in Figure 11a.

**Figure 11.** Presentation of the studied path and hardware in experiments. (**a**) Experiments path in Tongji University-Jiading Campus. (**b**) The UAV employed with a Pixhawk autopilot system. (**c**) The Pixhawk autopilot system deployed on a bicycle.

**Figure 12.** A screen shot from ground control station.

Pixhawk has built-in MAVLINK protocol [44], the protocol No.24 (GPS\_RAW\_INT) [44] is used as the "beacon" packet (including the speed and location of the UAV) for the UAV, whose interval can be configured (e.g., in the following experiments, the beacon intervals is set at 2 s). For mobile nodes, the protocol No.24 (GPS\_RAW\_INT) is used as the "update" packet (including the speed and location of the mobile node). We modified and reused the protocol No.36 (SERVO\_OUTPUT\_RAW) [44] as the "scheduling" packet (which stores the sensor ID and time-slot ID for the collision-free communication between nodes and the UAV) for the UAV. Each MAVLINK packet contains a system ID field so we can use it to identify the sender. The pixhawk also has a log system so the GPS information, as well as the received packet number and time, is stored in the on-board SD card.

Figure 13 presents the movements for *UAV*1 (only one UAV is used in real experiments) where the fly height is 15 m, with control speeds of 5 ms−1 (Figure 13a) and 3 ms−1 (Figure 13b) according to Pixhawk. In the studied experiments, the UAV flew at 15 m and 30 m. Figure 14 is an example to present the instantaneous speeds and trajectories for 5 nodes (Node 1 to Node 5) according to the Pixhawk.

To make the UAV fly along this path, we set four waypoints along the path as shown in Figure 12. In the experiments, the UAV start from *Point*1 to achieve its given speed (it is 5 ms−1 in Figure 12) to *Point*2, *Point*3 and the ending point (*Point*4). In Pixhawk autopilot system, the UAV will hover on the waypoint and ending point for 2 s. That is why in the Figure 13a, the UAV speed is lower than 5 ms−1 at *P*2 and *P*3. In Figure 13b, both the height and instantaneous speed of UAV have a shock between the *Point*3 and *Point*4 because of the influence of wind. The wind has an impact on the dynamic parameters so as to affect the relative velocity between the mobile node and the UAV, the network performance affected accordingly. However, it cannot be control during experiments.

**Figure 13.** Presentation of the movements for UAV when it fly at 15 m with 3 ms−1 and 5 ms−1 in ground station. (**a**) The movements for UAV flying at 15 m, and its speed is 5 ms−1 in ground control station. (**b**) The movements for UAV flying at 15 m, and its speed is 3 ms−1 in ground control station.

**Figure 14.** The movements for five nodes. (**a**) Instantaneous speeds of five nodes over time. (**b**) Trajectories of five nodes.

#### 5.2.2. Results

Figures 15 and 16 show the experiments results under the proposed algorithms, the combination of the Balance algorithm and the PCdFS algorithm. From Figure 15, the number of collected packets in simulation is almost two times larger than in the experiments because of the impacts of hardware and environments are not considered in simulations. The flying height has a significant impact on the number of collected packets in experiments, especially when *Nnode* is steady between different heights. The higher the height, the larger number of nodes in both PFS and proposed algorithms. The number of collected packets of the proposed algorithm in size 15, *h* = 30 m is more than twice than in *h* = 15 m. The system performance increase as the size increase. The larger the network, the more nodes have opportunities to send packets, the more packets were collected. The number of collected packets in the proposed algorithm (when *h* is 15 m) is 1.2 times larger than in the PFS algorithm.

From Figure 16, it can be found that the UAV's speed has little impact on data collection in real experiments. This is because the UAV's speed is set at 3 ms−1 and 5 ms−1 because of the battery constrictions and the campus constrictions. The nodes' speeds are between 2 ms−1 and 5 ms−1 also (Figure 14). Thus, the relative velocity between the UAV and mobile nodes is very small. The number of collected packets presented in Figure 16 keep the same conclusions as in simulations in Section 5.1.3 where the UAV fly at 5 ms−1 and 10 ms−1.

The flight height almost has no influence on the number of nodes that successfully transmit packets to the UAV, as presented in both Figures 15 and 16, which are the same as in Section 5.1.3.

**Figure 15.** The impact of network size, and flying height over the system performance. In these experiments, the beacon interval is fixed at 2 s according to the simulation results in Figure 7.

**Figure 16.** The impact of network size, and UAV's speed over the system performance. In these experiments, the beacon interval is fixed at 2 s. All the results are based on the combination of Balance and PCdFS algorithms.

#### *5.3. Discussions*

According to the aforementioned simulations, the beacon interval and the UAV speed have a huge impact on network performance. The shorter the beacon interval, the better the system performance. The UAV speed is constrained by the node speed. The smaller the relative velocity between them, the higher the network performance. It keeps the same conclusions as in the real experiment. In real experiments, the data collection is well conducted when the UAV speed is set at 5 ms−1 which is very close to the average speed of mobile nodes. Compare to the other dynamic parameters, the number of priority levels has a steady impact on data collection in the simulations. From the movements of the nodes in Figure 14, it can be seen that the difference between the trajectories of nodes is very small because the road width is 5 m and the road length is 1200 m.

Compare Figure 13a,b, it also can be found that, the fly time in 3 ms−1 is 1.56 times as in 5 ms−1 while the speed increase by 66.67% (from 3 ms−1 to 5 ms−1). In the studied scenario, there are very small differences between the trajectories when UAV fly at 3 ms−1 and 5 ms−1 because the UAV follow the same path which width is very short compared to its length. Thus, the fly time is mainly dependent on the speed of the UAV. In other words, the slower the UAV fly, the higher energy consumption of the battery energy. From Figure 16, we notice that, the data collection has very little difference when UAV fly at 3 ms−1 and 5 ms−1. Therefore, under given constrictions, the higher the fly speed of the UAV, the more saved battery energy.

The fly height has very little impact on data collection in simulations because of the same transmission rate is adopted. However, the fly height has a huge impact on data collection in experiments because a real and complex antenna system are conducted among the transmissions between the node and the UAV. The higher the flying height, the less interference from external factors (e.g., buildings, etc.). Thus, the better the transmission, the higher the network performance.

#### **6. Conclusions**

In this paper, we developed two mechanisms: PCdFS and PMCdFS. PCdFS mechanism is used to build the scheduling communications when the nodes are only covered by one of the UAVs. PMCdFS is used to balance the communication between the nodes and multi-UAVs when these nodes within the range of multi-UAVs at the same time. Based on the two mechanisms, we proposed the Balance algorithm which highly enhances the network fairness in the applications where both the nodes and the collectors are mobile. Two key mechanisms for designing Balance algorithm are: (i) divide the interesting areas into different priority areas and (ii) provide an independent priority value for each node in the same priority group according to their contact duration with the UAVs. We examined the performance of proposed algorithms through extensive simulations, and real experiments. In the experiments, we used 15 mobile nodes at a path with several intersections and one island at the Tongji campus in Shanghai, China. We also confirm the applicability of the proposed algorithm in a challenging and realistic scenario through numerous experiments. Both simulation results and experiment results present that the proposed PCdFS algorithm enhanced the network performance efficiently. The backhaul dimensioning is an interesting problem that we will address in our future work. It depends on the used backhaul type (either satellite or terrestrial) and on the allocation that is reserved to the network slice dedicated for Machine Type Communication (MTC) traffic.

**Author Contributions:** Conceptualization, X.M., T.L., R.K., and R.D.; methodology, X.M. and T.L.; software, X.M. and T.L.; validation, X.M. and T.L.; formal analysis, X.M. and T.L.; resources, T.L.; data curation, X.M. and T.L.; writing–original draft preparation, X.M. and T.L.; writing–review and editing, X.M., T.L., R.K. and R.D.; funding acquisition, S.L. All authors have read and agreed to the published version of the manuscript.

**Funding:** This research received no external funding.

**Conflicts of Interest:** Authors declare no conflict of interest.

#### **References**

© 2020 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/).

## *Article* **Trajectory Planning for Data Collection of Energy-Constrained Heterogeneous UAVs**

**Zhen Qin 1, Chao Dong 2,\*, Hai Wang 1, Aijing Li 1, Haipeng Dai 3 and Weihao Sun 1 and Zhengqin Xu 1**

Received: 29 September 2019; Accepted: 7 November 2019; Published: 8 November 2019

**Abstract:** Nowadays, Unmanned Aerial Vehicles (UAVs) have received growing popularity in the Internet-of-Things (IoT) which often deploys many sensors in a relatively wide region. Since the battery capacity is limited, sensors cannot transmit over a long distance. It is necessary for designing efficient sensor data collection mechanisms to prolong the lifetime of the IoT and enhance data collection efficiency. In this paper, we consider a UAV-enabled data collection scenario, where multiple heterogeneous UAVs with different energy constraints are employed to collect data from sensors. The value of data depends on the importance of the monitoring area of the sensor and the freshness of collected data. Our objective is to maximize the data collection utility by jointly optimizing the communication scheduling and trajectory of each UAV. The data collection utility is determined by the amount and value of the collected data. This problem is a variant of multiple knapsack problem, which is a classical NP-hard problem. First, we transform the initial problem into a submodular function maximization problem under energy constraints, and then we design a novel trajectory planning algorithm to maximize the data collection utility, while accounting for different values of data and different energy constraints of heterogeneous UAVs. Finally, under different network settings, the performance of the proposed trajectory planning algorithm is evaluated via extensive simulations. The results show that the proposed algorithm can obtain maximum data collection utility.

**Keywords:** unmanned aerial vehicles; trajectory planning; sensors; data collection utility

#### **1. Introduction**

Thanks to its tremendous application potentials in civilian, commercial and military related fields, the Internet of things (IoT) has attracted increased attention in many applications, e.g., natural disaster prediction, smart city, environmental monitoring, and reconnaissance [1–5]. The IoT often deploys many energy-constrained sensors in a relatively wide region. The task of the sensor is to collect data from the monitoring area, and then it uses multi-hop transmission mode to transmit data to the base station or sink node. Since the battery capacity is limited, sensors cannot transmit over a long distance. It is necessary for designing efficient sensor data collection mechanisms to prolong the lifetime of the IoT and enhance data collection efficiency [6].

In order to achieve efficient data collection, more and more people exploit Unmanned Aerial Vehicles (UAVs) to collect data from sensors, which will probably be a prospective technology for realizing the future IoT [6,7]. The heterogeneity and multi-domain nature of UAVs are indispensable in the IoT environment [8–10]. Thus, it is necessary for the IoT environment to use multiple heterogeneous UAVs with different capabilities. Different from traditional Wireless Sensor Networks (WSNs), the UAV-enabled data collection system uses mobile data collection devices installed on UAVs to communicate with sensors directly through the UAV-sensor channels, which are dominated by line-of-sight (LoS). UAVs can move towards the sensors and establish reliable connections with them due to their flexible deployment and high mobility [11]. UAV-enabled data collection system can reduce the energy consumption of sensors and improve the throughput and coverage.

There are many studies on studying how to use UAVs to collect reliable data from sensors. They mainly focus on two aspects of optimization. On the one hand, some works focus on solving the energy limitation problem of sensors in WSN [6,12–14]. They aim to optimize the wake-up schedule of sensor nodes, reduce the transmission power of sensors or improve the energy efficiency of data collection. However, these works rarely consider the value of data and distinguish the data collected from each sensor. For example, in reconnaissance application, the monitoring data of enemy command center is more important than that of living area. The value of data depends on the importance of monitoring area of the sensor and elapsed time after the previous collecting time (i.e., the freshness of collected data). On the other hand, some works focus on improving energy efficiency of UAV system [15–17]. They mainly aim to optimize the deployment of UAV, the trajectory of UAV, and the velocity of UAV. In these works, they use a single UAV or homogeneous UAVs. There are few studies that consider multiple heterogeneous UAVs with different energy constraints and power efficiency. Multiple heterogeneous UAVs can not only solve the energy limitation problem of a single UAV, but also fully utilize the capability characteristics of heterogeneous UAVs to implement complementary performance.

In this paper, we study a UAV-enabled data collection scenario, where multiple heterogeneous UAVs with different energy constraints are employed to collect data from sensors. The UAVs are responsible for transmitting data from sensors to the base station or sink node. We aim to maximize the data collection utility by planning trajectories of UAVs. The data collection utility is calculated by the value of data and amount of data. The value of data collected from the sensor depends on the importance of the monitoring area of the sensor and the freshness of collected data. Our problem contains three main technical challenges:

To solve this problem, we transform the initial problem into a submodular function maximization problem under energy constraints, and then, to maximize the data collection utility, we propose a novel trajectory planning algorithm. The main contributions of this paper are summarized as follows:

• Sufficient simulations are performed to demonstrate the validity and applicability of the proposed algorithm. The data collection utility of our algorithm can be increased by 134% at most, and the proposed algorithm is the closest to the optimal scheme compared with other algorithms.

The rest of this paper is organized as follows. In Section 2, we introduce the related work about the UAV-enabled data collection system and trajectory planning. In Section 3, we present the system model and problem formulation. Then we propose a solution for the formulated problem in Section 4. Simulation results are provided and analyzed in Section 5. Discussion is provided in Section 6. Finally, we conclude the paper in Section 7.

#### **2. Related Work**

#### *2.1. UAV-Enabled Data Collection*

There are many works on studying how to use the UAV to collect data from sensors. In [20], the authors considered that UAVs were used for collecting imagery information from nodes, and then, the UAVs transmitted information to the ground station. They proposed a predictive compression policy to maximize the end-to-end image quality. Gong et al. utilized a UAV to collect data from sensors which are deployed on a straight line [16]. The authors minimized the flight time of the UAV from a starting location to an ending location, and they jointly optimized the transmit power of sensors, the speed of the UAV and the data collection intervals. Ebrahimi et al. considered a scenario where UAVs collected the data in dense WSNs [6]. The authors used a novel solution methodology which is called projection-based Compressive Data Gathering (CDG). CDG aggregated data from sensors to the selected projection nodes which acted as cluster heads. Next, the UAV transferred the aggregated data from selected nodes to the sink node. In [21], the authors proposed a novel UAV-assisted backscatter communication. The UAV collected data from terrestrial backscattering tags, and then uploaded the collected data when it flied to the coverage area of the base station. Liu et al. proposed a UAV trajectory design for data collection to reduce redundant data and improving energy efficiency [22]. In [23], the authors deployed multi-UAV to serve vehicles on a highway. They utilized UAVs to deliver critical data to the vehicles crossing the given highway segment. By planning the trajectory of each UAV and optimizing the radio resource allocation, they aimed to minimize the number of UAVs to serve all vehicles. Sanaa et al. deployed UAVs as base stations to provide instant recovery via temporary wireless coverage [24]. They minimized the number of UAVs and optimized the positions of them in selected locations to enhance performance. Yang et al. studied a UAV-enabled data collection system, in which the UAV was employed to gather data from ground users. The sensors have limited battery and lower power. To prolong the lifetime of sensors, UAVs can move close to sensors to collect their information with minimum transmit power [11]. However, these works rarely consider distinguishing the data collected from each sensor. The value of data collected from each sensor is different, which depends on the importance of the monitoring area of the sensor and the freshness of collected data.

#### *2.2. Trajectory Planning*

Although people have strong interest in UAVs, studies on the location optimizing and trajectory planning of UAVs are still in progress. These studies are different in the optimization method and objective function because they assume different environments. These works are mainly divided into two types: single UAV trajectory planning and multi-UAV trajectory planning. Hu et al. considered a UAV used for the mobile edge computing system, where the mobile UAV equipped with computing resources provided service for many ground users [13]. By jointly optimizing the ratio of offloading tasks, the trajectories of UAVs, and the user scheduling variables, the authors minimized the maximum delay of all users. In the IoT system, Zhan et al. used a rotary-wing UAV for collecting the data from the IoT devices [14]. Under the energy constraint of the UAV, the authors minimized the maximum energy consumption of all IoT devices. Moataz et al. utilized a UAV to collect data from time-constrained IoT

devices [25]. These devices with limited buffer sizes had their own target data upload deadline, and thus data needed to be collected before it lost its value. Their goal was to maximize the number of served IoT devices by jointly optimizing the radio resource allocation and the trajectory of the UAV. This paper took into account the change in the value of data. It provided a basis for us to consider the value of a sensor's data. Hu et al. studied a UAV-enabled wireless power system, where the UAV provided wireless energy supply for ground users with a linear topology. The authors maximized the minimum received energy of ground users by optimizing the trajectory of the UAV [26]. They first presented the globally optimal one-dimensional (1D) trajectory solution to the minimum received energy maximization problem. Zeng et al. studied a multicasting system which utilized the UAV to transmit the file to all ground users [27]. By designing the UAV's trajectory, the authors minimized the mission completion time of the UAV. Meanwhile, they guaranteed that each ground user can successfully recover the file. However, in some applications, a single UAV has been unable to meet the demands of missions. There are many works on studying how to design the trajectories of multi-UAV. Under urban environments, in order to minimize the risk to the population, the authors proposed a risk-aware trajectory planning algorithm for multi-UAV [28]. Islam et al. proposed a task-oriented trajectory planning scheme for multi-UAV [29]. The UAVs taken autonomous decisions to find their trajectories for flying to the mission area while avoiding collision to barriers. In [30], the authors aimed to minimizing the mission time by planning the trajectory of each UAV, while satisfying the time requirements. Under the same test scenarios, Christian et al. presented advancements over the A\* and the smoothing algorithms [31]. Hu et al. exploited the nested Markov chains to analyze the probability for successful data transmission, and then, for real-time sensing missions, the authors proposed a sense-and-send protocol [32]. To solve the decentralized UAV trajectory planning problem, they proposed a multi-UAV Q-learning algorithm. Wu et al. used multi-UAV as mobile base stations which provided the service to the ground users [33]. The authors optimized the trajectory of each UAV to maximize the minimum throughput of ground users. Zhan et al. employed multi-UAVs to collect data from sensors in WSN [17]. By jointly optimizing the trajectories of UAVs, wake-up association and scheduling for sensors, the author minimized the maximum mission completion time of all UAVs. However, there are few studies that consider multiple heterogeneous UAVs with different energy constraints and power efficiency. Multi-heterogeneous UAVs not only can solve the energy limitation problem of a traditional single UAV, but also make use of the capability characteristics of heterogeneous UAVs to achieve complementary performance.

#### **3. System Model and Problem Formulation**

#### *3.1. System Model*

#### 3.1.1. Network Model

We consider a UAV-enabled data collection scenario, where *k* heterogeneous UAVs with different energy constraints are used for collecting the data from sensors to a remote base station or sink node as shown in Figure 1. In the UAV-enabled data collection system, since sensors are employed in a large area, it is inconvenient for the UAVs to fly over each sensor to collect data. In order to achieve efficient and scalable performance, more and more people adopt a clustering approach in WSN. In this paper, an overlapping clustering method is used for dividing the sensors on the ground [34,35]. Sensors transmit data to cluster heads, and then UAVs move towards cluster heads to collect data. The characteristic of overlapping clustering is that a sensor may belong to multiple clusters at the same time, which is different from traditional clustering algorithms. The cluster head can receive data from all sensors in its coverage. In other words, the sensor will transmit its data to each cluster head which it belongs to. For example, if a sensor fits in two overlapping clusters, it will transmit its data to two cluster heads. Establishing overlapping clusters can improve the success rate and robustness of data collection. For convenience, Table 1 provides major notations used in this paper.

**Table 1.** Major notations.

The UAV, sensor and cluster head sets are denoted as *U* = {*u*1, ..*ui*.., *uk*}, *S* = {*s*1, ..*sj*..,*sn*} and *C* = {*c*1, ..*ca*.., *cm*}, respectively. In addition, ground sensors can be partitioned into *m* sets, *S*1, *S*2, ...*Sm*. Each UAV *ui* is constrained with an energy budget Emax,*i*. In this paper, the UAV mainly consumes communication-related energy and propulsion energy [36–38]. The communication-related energy is used for transmitting the collected data. The propulsion energy includes motion energy and hovering energy. The UAV consumes motion energy for flying between clusters, and hovering energy for hovering at cluster heads to collect data.

**Figure 1.** Monitoring scenario.

#### 3.1.2. Propulsion Energy Consumption Model

The motion energy is spent to overcome the gravity and drag forces caused by forward motions and wind. The motion energy consumption is calculated by minimum motion power *p*min,*m* and the length of a UAV's trajectory [38,39]. It can be expressed as

$$E\_{m,i} = \frac{p\_{m,i} \cdot b\_i}{\upsilon\_i} = \frac{p\_{\min,m} \cdot b\_i}{\eta\_i \cdot \upsilon\_i} \, \, \, \, \tag{1}$$

where *pm*,*i* is the actual motion power consumption of UAV *ui*, *ηi* is the UAV's power efficiency, *vi* is the velocity of the UAV *ui* and *bi* is the length of trajectory *Li*.

The hovering energy consumption depends on the hovering time and actual hovering power *ph*,*i*. The actual hovering power relates to the power efficiency and minimum hovering power *p*min,*h*. The minimum hovering power relates to the density of air, diameter, thrust and the number of rotors [39,40]. The hovering time is calculated by amount of data *Na*,*i* which is collected from cluster head *ca* by UAV *ui* and data transmission rate *Ra*,*i* between cluster head *ca* and UAV *ui*. Therefore, the hovering energy consumption of UAV *ui* for collecting data from cluster head *ca* can be calculated by

$$E\_{h,i}^{a} = \frac{p\_{h,i} \cdot N\_{a,i}}{R\_{a,i}} = \frac{p\_{\min,h} \cdot N\_{a,i}}{\eta\_i \cdot R\_{a,i}}.\tag{2}$$

In this paper, we mainly consider that UAVs are used for data collection application. This kind of applications commonly used small rotary-wing UAVs. For example, the mass of UAV is 2.07 kg, the number of rotors is 4, and the rotor diameter is 0.254 m [38]. According to references [39,40], the minimum motion power is set to 388.32 J/s, and the minimum hovering power is set to 308 J/s.

#### 3.1.3. Communication-Related Energy Consumption Model

The communication-related energy consumption for transmitting data cannot be ignored when the transmission distance or the amount of data is large. The energy consumed for successful transmitting wireless data is affected by the channel between source and destination nodes, the transmission distance and other factors like interference, fading and noises. The communication energy consumption for transmitting *Na*,*i* bits over distance *d* can be calculated by [41]

$$E^{a}\_{c,i} = N\_{a,i} \cdot d^{a} \cdot e\_{x\_{\prime}} \tag{3}$$

where *ex* and *α* are constants which depends on the characteristics of the communication channel. *ex* is unit energy consumption which represents the energy consumption for transmitting one bit, measured in *J*/(*mα* · *bit*), and *α* is the path loss exponent which depends on the data transmission environment.

#### 3.1.4. Utility Model

The data collection utility is calculated by the value of data and the amount of data. The value of data depends on the importance of the monitoring area of the sensor and the freshness of collected data. In fact, the importance of the monitoring area has different performance metrics in different applications and scenarios. For example, the importance of the monitoring area can be defined by traffic [42].

To calculate the data collection utility, we first define the value of data. On the one hand, the value of data collected from the sensor depends on the importance of monitoring area of the sensor. In this paper, the initial value of data from *sj* is defined as *V*0 *j* = *V*max *j* . Once the data of sensor *sj* is collected, the value of data collected from *sj* is set to *V*min *j* . For any sensor *sj* and *sj* , if the monitoring area of sensor *sj* is more important than the monitoring area of sensor *sj* , the relations can be expressed by

$$V\_j^{\max} \geqslant V\_{j'}^{\max} \geqslant V\_j^{\min} \geqslant V\_{j'}^{\min}.\tag{4}$$

On the other hand, the value of data collected from sensor *sj* depends on elapsed time after the previous collecting time (i.e., the freshness of collected data). For each sensor *sj*, recovery interval *Tj* is different which depends on the importance of the monitoring area and the required monitoring interval of the sensor. At time *t*, the value of data collected from sensor *sj* can be denoted as [43]

$$V\_{\vec{j}}(t) = \begin{cases} A \times \exp(t - t'\_{\vec{j}}) + B, & \text{if } |t - t'\_{\vec{j}}| \le T\_{\vec{j}} \\ V\_{\vec{j}}^{\text{max}}, & \text{otherwise} \end{cases},\tag{5}$$

$$\begin{cases} \begin{array}{c} A = \frac{V\_j^{\max} - V\_j^{\min}}{\epsilon^{\frac{1}{j}} - 1}, \\ B = V\_j^{\min} - A, \end{array} \end{cases} \tag{6}$$

where *t j* is the time of previous data collection from sensor *sj*. As we can see from Equation (5) and Equation (6), when the sensor's data is collected by one UAV, the value of data will decrease to the minimum value. As time elapses, the value of data increases exponentially until it reaches its maximum value. After the value of data reaches the maximum value, it remains until the sensor's data is collected by UAVs again.

In this paper, sensors transmit data to cluster heads, and then UAVs move towards cluster heads to collect data. The data collection utility mainly depends on the amount of data and its value. The data collection utility of the selected cluster head *ca* which is served by a UAV *ui* can be given by

$$q\_{a,i} = \sum\_{s\_j \in S\_a} N\_{a,i}(s\_j) \cdot V\_j(t\_{a,i})\_\prime \tag{7}$$

where *Sa* is the set of all sensors in cluster *ca*, *Na*,*i*(*sj*) represents the amount of data of sensor *sj* included in cluster head *ca* which is served by UAV *ui*. Meanwhile, since the time of data collection is relatively short, we do not consider the changes of the data's amount and value in the process of data collection. *ta*,*i* represents the time when a UAV *ui* starts to collect data from cluster head *ca*. The data collection utility of UAV *ui* can be calculated by

$$Q\_i = \sum\_{c\_d \in P\_i} q\_{a, i\prime} \tag{8}$$

where *Pi* is the set of cluster head that is served by UAV *ui*. Therefore, the overall utility of data collection mission can be calculated by

$$Q(P) = \sum\_{i=1}^{k} Q\_i = \sum\_{i=1}^{k} \sum\_{c\_a \in P\_i} q\_{a,i} \,. \tag{9}$$

#### *3.2. Problem Formulation*

In this paper, the flying altitude of the UAVs is assumed to be a constant altitude *H*. We assume that *r* = (*xr*, *yr*, *H*) is the initial location of all UAVs. The total energy consumption *Ei* includes the hovering energy consumption, motion energy consumption and communication energy consumption, which can be expressed by

$$E\_i = E\_{m,i} + E\_{l,i} + E\_{c,i} \,. \tag{10}$$

Denote the trajectory of UAV *ui* projected on the ground as *li*(*t*)=[*xi*(*t*), *yi*(*t*)]*T* ∈ R2×1, where 0 ≤ *t* ≤ *T*. The trajectory of each UAV is subject to the velocity constraints, which can be given by

$$\left\| \left\| \dot{l}\_i(t) \right\| \right\| \le \upsilon\_{\text{max}}, \forall i, t \in [0, T], \tag{11}$$

where · *li*(*t*) is the time derivative of *li*(*t*) and *v*max is the maximum velocity of UAVs.

Our goal is to plan the trajectories of heterogeneous UAVs with different energy constraints to maximize the overall data collection utility. Therefore, the optimization problem can be formulated as

$$P1: \max\_{P \in \mathcal{C}, L\_i, 1 \le i \le k} Q(P) \tag{12}$$

$$\text{s.t.} \quad E\_i \le E\_{\text{max}, i\prime} \forall i,\tag{13}$$

$$\left\|\dot{l}\_{i}(t)\right\| \leq \upsilon\_{\text{max},\prime} \forall i, t \in [0, T], \tag{14}$$

$$L\_i(0) = L\_i(T) = r\_\prime \forall i,\tag{15}$$

$$\left||L\_i(t) - L\_{i'}(t)\right|| \ge d\_{\text{min}\_{\prime}} \forall i \ne i', t \in [0, T]. \tag{16}$$

where *P* represents the selected cluster heads, *Li* represents the trajectory of UAV *ui*, *r* is the initial location of all UAVs and *d*min denotes the minimum distance between UAVs to ensure collision avoidance. Constraint (13) implies the energy consumption of UAV *ui* cannot be greater than its maximum energy constraint Emax,*i*. In (15), it ensures that each UAV needs to return to initial location *r* by the end of data collection mission. When all UAVs fly at the same altitude *H*, the trajectories of UAVs are also constrained by collision avoidance (16).

#### **4. Solution**

#### *4.1. Hardness Analysis*

The formulated problem combines two-level optimizations. The objective of upper level optimization is to select cluster heads and the objective of lower level optimization is to design trajectories for energy-constraint heterogeneous UAVs. The results of each level optimization problem would directly affect another level optimization. If we select cluster heads without considering trajectory planning, it will consume much motion energy. If we do not consider to select appropriate cluster heads in trajectory planning, the data collection utility will not be maximized. Therefore, the two-level optimizations are coupled with each other and cannot be solved separately.

Without considering the motion energy consumption, the upper cluster head selection problem can be regarded as a simplified form of the formulated problem

$$P2: \max\_{P \in \mathcal{C}, L\_i, 1 \le i \le k} Q(P) \tag{17}$$

$$\text{s.t.} \quad E\_{\text{lt},i} + E\_{\text{c.f.}} \le E\_{\text{max},i\text{.} \forall i} \forall i,\tag{18}$$

$$\left\|\dot{l}\_i(t)\right\| \le \upsilon\_{\text{max}, \prime} \forall i, t \in [0, T], \tag{19}$$

$$L\_i(0) = L\_i(T) = r\_\prime \,\forall i,\tag{20}$$

$$\|\|L\_i(t) - L\_{i'}(t)\|\| \ge d\_{\text{min}} \,\forall i \ne i', t \in [0, T]. \tag{21}$$

This problem can be modeled as a multiple capacity-constraint knapsack problem. When *k* = 1, this problem is a knapsack problem, which is a classical NP-hard problem. Therefore, when the value of *k* is greater than 1, our problem is also NP-hard. The knapsack problem is a combinatorial optimization problem: under the given weight limit, its objective is to select items which have unique weight and value to maximize the total value [18,19].

In addition, if we consider the motion energy consumption, we would calculate the *k* closed trajectories including all cluster heads in the selected set *P*. This problem can be formulated as multiple Travelling Salesman Problem, which is also a NP-hard problem. Therefore, the original optimization problem is difficult to solve, which combines two coupling NP-hard problems.

#### *4.2. Submodular Analysis*

To solve this problem, we transform the initial problem into the problem of maximizing a submodular function with energy constraints. We prove the data collection utility function has three tractable properties: submodularity, nonnegativity and monotonicity. We first give some definitions to facilitate further analysis.

**Definition 1.** *(monotonicity, nonnegativity, and submodularity) given a finite set* Ψ*, a submodular function is a set function f* : 2Ψ → *R. f is called monotonicity (nondecreasing), nonnegativity, and submodularity if and only if it can satisfy the following requirements, respectively.*

**Theorem 1.** *The constructed objective function is submodular, monotone and nonnegative.*

**Proof.** According to the definition of the data collection utility function, *Q*(*P*) ≥ 0, then it is nonnegative.

The data collection utility *Q*(*P*) increases as the number of cluster heads collected by UAVs increases. According to the utility model, for the set *X* ⊆ *Y* ⊆ *C*, we can obtain the following inequation

$$Q(X) \le Q(Y),\tag{22}$$

where implies *Q*(*P*) is monotone. Next, we prove that *Q*(*P*) is a submodular function by proving the following inequation

$$Q(X \cup \{\mathfrak{c}\}) - Q(X) \ge Q(Y \cup \{\mathfrak{c}\}) - Q(Y), \\ X \subseteq Y \subseteq \mathbb{C}, \mathbf{x} \in \mathbb{C} \backslash Y, \tag{23}$$

where *X* and *Y* represent the set of cluster heads in WSN. We denote *SX* as the sensors covered by the set of cluster heads *X*. We prove the inequation under two cases.

*Case 1* (*Sc* ∩ *SY* = ∅): In this case, the data of sensors included in the newly added cluster has never been collected. Therefore, the value of data of sensors covered by cluster head *c* can reach their maximum value *V*max. We can obtain

$$Q(X \cup \{\mathfrak{c}\}) - Q(X) = Q(Y \cup \{\mathfrak{c}\}) - Q(Y). \tag{24}$$

*Case 2* (*Sc* ∩ *SY* = ∅): In this case, the data of some sensors included in the newly added cluster has been collected. Once the data of sensor is collected, the value of data will be set to *V*min. Therefore, we can obtain

$$Q(X \cup \{\varepsilon\}) - Q(X) \ge Q(Y \cup \{\varepsilon\}) - Q(Y). \tag{25}$$

Therefore, we prove that *Q*(*P*) is a submodular function. To solve this problem, the initial problem is transformed into a submodular function maximization problem with energy constraints. We propose a novel trajectory planning algorithm which refers to the idea of [44,45]. It aims to maximize the overall data collection utility, while accounting for cluster head selection and differnent energy constraints of heterogeneous UAVs.

#### *4.3. Algorithm*

Based on the submodular function, we jointly consider the upper level optimization and lower level optimization, and then we design a simple but efficient algorithm referring to the idea of [44,45]. The algorithm attempts to select appropriate cluster heads to collect data and design the collecting sequence. The core idea of our algorithm is to iteratively select a new cluster head *cj* by greedy method, which has the maximum utility-cost ratio. For example, in iteration *j*, the selected cluster head can be expressed as follows

$$\mathcal{L}\_{\mathcal{I}'} = \underset{\mathcal{c} \in I \backslash P\_{j-1}}{\text{arg}\max} \frac{Q(P\_{j-1} \cup \{\mathcal{c}\}) - Q(P\_{j-1})}{E(P\_{j-1} \cup \{\mathcal{c}\}) - E(P\_{j-1})}.\tag{26}$$

Algorithm 1 consists of a parent loop and a child loop. After inputting and initializing relative parameters, we use the parent loop to select cluster heads and plan trajectories (Line 2–Line 12). When all cluster heads have been traversed, the parent loop is no longer executed. In the parent loop, there is a child loop for selecting the cluster head which has the maximum utility-cost ratio (Line 3–Line 7). In each iteration, we use Algorithm 2 to calculate the energy cost and the trajectory, which considers the energy constraint of each UAV. The utility and energy cost are calculated according to the previously selected cluster heads plus possible cluster head *cj*, and then, we pick up the cluster head with the highest utility ratio (Line 7). Afterwards, we check whether the UAVs satisfy the respective energy constraints (Line 8–Line 10). Next, it deletes this cluster head and starts next parent loop. Each parent loop returns a solution which is better than previous solution and the nature of the result depends on the quality of Algorithm 2. Finally, we can obtain the selected cluster heads *P* and the trajectories of UAVs *L* which satisfy the respective energy constraints.

#### **Algorithm 1** Cluster Head Selection and Trajectory Planning Algorithm

**Input:** Cluster head set *C*, energy constraints Emax,*i*, 1 ≤ *i* ≤ *k*. **Output:** Selected cluster heads *P* ⊆ *C* and *k* trajectories of UAVs. 1: Initialize *I* ← *C*, *P*0 ← ∅, *E*(*P*0) ← 0, *Q*(*P*0) ← 0, *L* ← ∅, *j* ← 1; 2: **while** *I* = ∅ **do** 3: **for** *i* = 1 to |*I*| **do** 4: Calculate *Q*(*Pj*−1 ∪ {*ci*}) and *Q*(*Pj*−1); 5: Using Algorithm 2 to get the trajectories and the energy cost *E*(*Pj*−1 ∪ {*ci*}); 6: **end for** 7: *cj* = arg max *c*∈*I Q*(*Pj*−1∪{*c*})−*Q*(*Pj*−1) *E*(*Pj*−1∪{*c*})−*E*(*Pj*−1) ; 8: **if** *E*(*Pj*−1 ∪ {*cj*}) = *Inf* **then** 9: *Pj* ← *Pj*−1 ∪ {*cj*}, *j* ← *j* + 1, *L* ← *Lcj* ; 10: **end if** 11: *I* ← *I*\*cj* ; 12: **end while**

13: Output *P* ← *Pj*−1, *L*.

**Algorithm 2** Multiple Energy-constrained Heterogeneous UAV Trajectory Planning Algorithm

**Input:** *P*, Emax,*i*, 1 ≤ *i* ≤ *k*, starting location *r*.

**Output:** *k* trajectories of UAVs and the energy cost *E*.

1: Initialize *Y* ← *P*, *E* ← ∅, MAXE = 0, *L* ← ∅;

```
4: for i = 1 to |ζ| do
```

```
7: Use the TSP algorithm to calculate the energy cost Ei,j and the trajectory Li,j which covers
```
all cluster heads in *Xi* ∪ *cj*;

```
8: if Ei.j ≤ Emax,i then
9: Xi ← Xi ∪ cj, Ei ← Ei,j, Li ← Li,j;
10: end if
11: end for
12: Y ← Y\Xi, E ← E + Ei, L ← L ∪ Li;
13: end for
14: if Y = ∅ then
15: E =Inf ;
16: end if
17: end while
```
#### **5. Simulation Results**

In this paper, our algorithm aims to maximize the data collection utility by optimizing the trajectory of each UAV. The data collection utility is calculated by the value and amount of data. The value of data depends on the importance of the monitoring area of the sensor and the freshness of collected data.

#### *5.1. Simulation Setup*

We consider a mission area of size 1 km × 1 km. The simulations are performed according to parameters specified in Table 2 [38–41]. The time requirement for data uploading is not a constant. It can be changed depending on the amount of data and data transmission rate. In fact, sensors continuously monitor the area and generate new data. However, since the time of data collection is relatively short, we do not consider the changes of data's amount and value in the process of data collection. We assume that communication links between UAVs and sensors are dominated by the LoS links where the channel quality mainly depends on the UAV-sensor distance [16,33,46]. Meanwhile, since the UAVs fly at a fixed altitude, we can set the data transmission rate to be 2 Mbps. Furthermore, the simulation results are averaged over extensive simulation runs.

#### *5.2. Baseline Setup*

To demonstrate the performance of the proposed UAV trajectory planning algorithm (UE), we compare and implement the following four benchmark schemes:

#### *5.3. Different Number of Sensors*

In this simulation, we set the number of UAVs to 3. Figure 2 shows the trend of data collection utility as the number of sensors changes. We can observe that the data collection utility gradually increases as the number of sensors increases. Our algorithm achieves almost the same performance

with the optimal scheme when the number of sensors is small. However, the gap between our algorithm and the optimal scheme increases as the number of sensors increases, from 5.2% to 66.6%. Meanwhile, the proposed algorithm shows better performance when the number of sensors is large. Compared with RAN algorithm, the data collection utility of our algorithm is improved by 103%–134%. This is reasonable since it chooses the data collection points with the highest utility-cost ratio each time, which saves the energy of UAVs and improves the data collection utility of UAVs. Compared with EC algorithm, the data collection utility of our algorithm is improved by 49%–62%. Because our algorithm considers the value of data when selecting cluster heads, not only the amount of data collection. Furthermore, GU algorithm chooses a cluster which has the most data collection utility. However, it does not consider the energy consumption for collecting data from this cluster. Compared with the GU algorithm, the data collection utility of our algorithm is improved by 72%–102%. Our proposed algorithm makes reasonable and effective use of UAV's energy to collect more valuable data of sensors.

**Figure 2.** Different Number of Sensors.

In Figure 3, we illustrate the convergence of our algorithm under different number of sensors. From the figure, we note that our algorithm achieves fast convergence in three cases. Meanwhile, we can obtain that the number of iterations of the proposed algorithm is related to the number of sensors.

**Figure 3.** Convergence of UE Algorithm (*n* = 20, 60, 120.)

#### *5.4. Different Number of UAVs*

In this simulation, the number of sensors is set to 100. As shown in Figure 4, as the number of UAVs increases, the advantages of our algorithm are more obvious. This is because we fully consider the energy constraint and power efficiency of each UAV in trajectory planning. Therefore, as the number of heterogeneous UAVs increases, the data collection utility gradually increases, and our algorithm is closer to the optimal scheme than other three algorithms. The data collection utility of the optimal scheme is 17.6%–38.9% higher than that of our algorithm. In practical applications, we should consider the mission requirements and existing equipment to dispatch an appropriate number of UAVs to perform mission. Using too many UAVs may bring economic pressure and reduce the energy efficiency. Figure 5 shows the convergence of the proposed algorithm under different number of UAVs. We can observe that our algorithm achieves fast convergence. Meanwhile, we can also find that the number of UAVs has little effect on the convergence of the proposed algorithm.

**Figure 4.** Different Numberof UAVs.

**Figure 5.** Convergence of UEAlgorithm (*k* = 2, 5, 9).

#### *5.5. Different Mission Area Sizes*

Figure 6 shows the trend of data collection utility as the size of mission area changes. We set the number of sensors to 100, and the number of UAVs to 3. We assume the mission area is a square area, and the variable in this simulation is the side length of the mission area. As shown in Figure 6, with the expansion of the mission area, the data collection utility gradually decreases. This is reasonable since the UAVs need to consume more energy to fly between data collection points when the sensors are distributed in a large mission area. Under this scenario, the energy used for data collection will be reduced, leading to the decrease of data collection utility. However, when the mission area is large, the data collection utility of our algorithm is also higher than other algorithms. For example, when the mission area is 1500 m × 1500 m, the data collection utility of our algorithm is 52%–134% higher than compared algorithms. Meanwhile, the data collection utility of the optimal scheme is 8.7%–35.1% higher than that of our algorithm as the mission area expands. In Figure 7, we illustrate the convergence of our algorithm under different mission area sizes. We can see that the algorithm can converge quickly in different data collection areas.

**Figure 6.** Different Mission Area Sizes.

**Figure 7.** Convergence of UE Algorithm (800 m, 1200 m, 1500 m).

#### *5.6. Trajectories of UAVs*

In this subsection, we use Figure 8 to show the resulting trajectories by each of the algorithms. The serial number of the cluster represents the importance of its coverage area. UE algorithm chooses the data collection points with the highest utility-cost ratio each time, which saves the energy of UAVs and improves the data collection utility of UAVs. Compared with the other three algorithms, our algorithm takes into account the data collection utility and the energy consumption.

**Figure 8.** Trajectories of Three UAVs.

#### **6. Discussion**

In this paper, we mainly focus on two-dimensional trajectory planning of UAVs. In fact, it is worthwhile to optimize UAV's altitude. However, the optimization of flight altitude will bring some challenges. First, the ascend and descend of UAVs will bring extra energy consumption. Second, the flight altitude of UAVs can influence the quality of communication channel. Third, it will bring new optimization variables and increase the search space. We need to further study to solve these problems. In the future, to further improve the performance of multi-UAV data collection system, we will present a new design framework of three-dimensional UAV trajectory.

#### **7. Conclusions**

In this paper, we consider exploiting UAVs to collect data from sensors. The value of data collected from each sensor is different. It depends on the importance of the monitoring area of the sensor and the freshness of collected data. To improve the data collection utility, we optimize the trajectory planning, communication scheduling and sensor node association. The data collection utility is determined by the amount and value of data. First, we formulate this problem as a variant of multiple knapsack problem, which is a classical NP-hard problem. We transform the initial problem into the problem of maximizing a submodular function under energy constraints. To maximize the data collection

utility, we propose a novel trajectory planning algorithm, while accounting for different value of data and different energy constraints of heterogeneous UAVs. Sufficient simulations are performed to demonstrate the validity and applicability of the proposed algorithm. The results show that the data collection utility of our algorithm can be increased by 134% at most.

**Author Contributions:** Conceptualization, Z.Q., C.D. and H.W.; methodology, H.D. and Z.Q.; software, A.L. and W.S.; validation, Z.Q. and C.D.; formal analysis, H.W. and A.L.; investigation, A.L., W.S. and Z.X.; writing–original draft preparation, Z.Q.; writing–review and editing, C.D., H.D. and A.L.

**Funding:** This work was supported in part by the National Natural Science Foundation of China under Grants (No. 61931011, No. 61872178, No. 61827801, No. 61702545, No. 61702525, and No. 61631020), in part by the Fundamental Research Funds for the Central Universities No.<PHONE_NUMBER>79, and in part by the Natural Science Foundation of Jiangsu Province under Grant No. BK20181251.

**Conflicts of Interest:** The authors declare no conflict of interest.

#### **References**

c 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/).

## *Article* **Completion Time Minimization for Multi-UAV Information Collection via Trajectory Planning**

#### **Zhen Qin 1, Aijing Li 1, Chao Dong 2,\*, Haipeng Dai 3 and Zhengqin Xu 1**

Received: 5 August 2019; Accepted: 16 September 2019; Published: 18 September 2019

**Abstract:** Unmanned Aerial Vehicles (UAVs) are widely used as mobile information collectors for sensors to prolong the network time in Wireless Sensor Networks (WSNs) due to their flexible deployment, high mobility, and low cost. This paper focuses on the scenario where rotary-wing UAVs complete information collection mission cooperatively. For the first time, we study the problem of minimizing the mission completion time for a multi-UAV system in a monitoring scenario when considering the information collection quality. The mission completion time includes flying time and hovering time. By optimizing the trajectories of all UAVs, we minimize the mission completion time while ensuring that the information of each sensor is collected. This problem can be formulated as a mixed-integer non-convex one which has been proved to be NP-hard. To solve the formulated problem, we first propose a hovering point selection algorithm to select appropriate hovering points where the UAVs can sequentially collect the information from multiple sensors. We model this problem as a BS coverage problem with the information collection quality in consideration. Then, we use a min-max cycle cover algorithm to assign these hovering points and get the trajectory of each UAV. Finally, with the obtained UAVs trajectories, we further consider the UAVs can also collect information when flying and optimize the time allocations. The performance of our algorithm is verified by simulations, which show that the mission completion time is minimum compared with state-of-the-art algorithms.

**Keywords:** wireless sensor networks; unmanned aerial vehicle; mission completion time; trajectory planning

#### **1. Introduction**

Due to their tremendous application potentials in military and civilian related applications, Wireless Sensor Networks (WSNs) have attracted increasing research interest in many fields, such as industrial process control, environmental monitoring, and battlefield surveillance [1–4]. Generally, WSNs are composed of small, battery-limited sensors which cannot transmit over a long distance [5]. There is a great interest recently in utilizing rotary-wing Unmanned Aerial Vehicles (UAVs) as mobile information collectors in WSNs [6–8]. They can move towards the sensors and establish reliable connections with them due to their high mobility and flexible deployment [9]. Rotary-wing UAVs are equipped with propellers that enable them to hover over fixed locations. This advantage makes them suitable candidates for mobile information collectors as they can hover over sensors to collect information [10,11]. Nowadays, with the popularity of WSNs, a single UAV cannot meet the demands of monitoring missions over larger monitoring areas. Information collection of WSNs with multi-UAV

cooperation is more desired. Currently, there are two types of methods to collect the information from WSNs with multiple UAVs. The first is to use static UAVs to form a network to cover all sensors, which is suitable for small area monitoring [12–15]. The second is to use mobile UAVs to cover a larger area [16–18]. As shown in Figure 1, we mainly focus on the second scenario in this paper.

**Figure 1.** Monitoring scenario.

For many WSNs applications, the timeliness of monitoring information is critical. Therefore, the mission completion time of multi-UAV cooperative information collection is very important. For example, in a city security monitoring system, if the control center gets fire information as soon as possible, the city may avoid serious economic loss and casualties. In traffic monitoring applications, real-time road information helps cars effectively avoid traffic congestion. In this paper, the mission completion time includes flying time and hovering time, both of which are related to the trajectory planning of the UAVs. Therefore, the trajectories need to be carefully planned such that UAVs can complete theirs missions quickly and satisfy the communication requirements along their entire trajectory. By optimizing the trajectory of each UAV, we pursue minimizing the mission completion time of multi-UAV system.

Some works have studied how to minimize a single UAV's the mission completion time [16,17,19–21]. However, these works cannot be used for information collection with multi-UAV directly. In fact, a multi-UAV system requires solving two sub-problems, task assignment and trajectory optimization. Generally, we cannot address one of problems individually because the two sub-problems are tightly coupled. If task assignment is not considered in trajectory planning, it may result in unreasonable task assignment. For example, a UAV may be responsible for too many tasks, which can lead to longer mission completion time. If trajectory optimization is not considered in task assignment, it may result in long flying distance, which may also lead to longer mission completion time. Therefore, we cannot solve the two sub-problems separately. In other words, we cannot assign tasks first, and then apply the algorithm of a single UAV to solve this problem. Since we use a multi-UAV system to collect information, the completion time of the entire mission is the time of all tasks completed by UAVs. In other words, it is the maximum completion time among the UAVs. The completion time of a UAV is mainly divided into two parts, flying time and hovering time. As shown in Figure 1, we give a toy example illustrating flying time and hovering time. The flying time is the time taken for the UAV to fly from point A to point B. The hovering time is the time for the UAV staying at the hovering point (A or B) to collect information from sensors. There are two

main differences from previous works. First, some works only consider flying time or only consider hovering time in UAV-enabled network [22–24]. Second, some works assume that UAVs only collect information from sensors when hovering [25–30]. If flying time is fully utilized, the mission completion time can be reduced. Therefore, we consider that the UAVs can collect information when they are hovering and flying.

In this paper, our objective is to plan the trajectories of all UAVs to minimize the mission completion time, while ensuring that the information of each sensor is collected. Rotary-wing UAVs can collect information when they are hovering and flying. This problem can be formulated as a mixed-integer non-convex problem. Since the problem involves infinitely many variables over time, it is difficult to optimize trajectories, and hovering and flying communication scheduling at the same time. To tackle this problem, we propose an improved fly-hover-fly trajectory planning algorithm. We first propose a hovering point selection algorithm to get hovering points. Then, based on these hovering points, we plan the trajectory of each UAV. Intuitively, it can use the algorithm of Multiple Traveling Salesman Problem (MTSP) to plan the trajectories of multi-UAV. However, MTSP's goal is to minimize the total completion time of multi-UAV. Different from MTSP, our problem aims to collect all sensors' information with multi-UAV such that the maximum completion time among UAVs is minimized. By using the Base Station (BS) coverage algorithm and min-max cycle cover algorithm, we select appropriate hovering points where the UAVs can sequentially collect the information from multiple sensors and get the trajectory of each UAV. Finally, based on the obtained trajectories, we propose an effective method to optimize UAVs hovering and fly-collection time allocations. The main contributions of this paper are summarized as follows:

The rest of this paper is organized as follows. In Section 2, we introduce the related work. The system model and problem formulation are presented in Section 3. Then, we propose the FHF algorithm to optimize the hovering points and obtain the trajectories in Section 4. In Section 5, we optimize the time allocations. Simulation results are provided and analyzed in Section 6. Discussion is provided in Section 7. Finally, we conclude the paper in Section 8.

#### **2. Related Work**

#### *2.1. Single UAV's Mission Completion Time Problem*

There are many studies on minimizing a single UAV's mission completion time. In [16], the authors studied a UAV-enabled multicasting system and planned the trajectory of the UAV for minimizing mission completion time, while ensuring that ground terminals successfully recovered files. To reduce the single UAV's mission completion time and periodic flight duration, Zhang et al. [17]

optimized the trajectory of UAV and communication resource allocation, while satisfying the data requirement of ground users. Zhang et al. [19] focused on a scenario where a single UAV communicated with multiple ground base stations. They aimed to minimize the mission completion time by planning the trajectory of UAV, while the UAV was also subject to practical communication connectivity constraint with ground base stations. One of the most important reconnaissance missions of the UAV is to take pictures of interesting targets in a wide area. Under this scenario, Lim et al. [20] proposed a trajectory generation algorithm for reconnaissance UAV with time constraints. Zhang et al. [21] proposed sparse *A*∗ search approach for a single UAV route planning with time constraints. It can be seen that the above works only discuss a single UAV's mission completion time in different scenarios. However, these works cannot be used for information collection with multi-UAV directly. Therefore, the mission completion time problem of multi-UAV is worth being further studied.

#### *2.2. Multi-UAV's Mission Completion Time Problem*

There are some studies on completing missions by multi-UAV within the specified time. Pohl et al. [31] studied the routing of multi-UAV, while the trajectories of UAVs met the constraints of total path cost optimization, total mission time, enemy radar avoidance, and time on target. This work aimed to minimize the total distance by planning trajectories. Shi et al. [32] proposed a statistical physics method for UAVs cooperative reconnaissance mission planning, while the trajectories satisfied the reconnaissance time requirements. However, in many applications, it is more important to complete the missions as soon as possible. In [23], the authors introduced a geometric path planning method and proposed a resource allocation algorithm for multi-UAV. However, they only considered the flying time. Hayat et al. [33] optimized the trajectory of each UAV and synchronized multi-UAV so that the UAVs can fly to the next task only after all UAVs had completed their previous task. Mousavi et al. [34] aimed to form UAV coalition formation to reduce the mission completion time. Wang et al. [35] found the optimal schedule to perform diverse missions of different time windows at various locations using fixed-wing heterogeneous UAVs. The solutions of minimizing the mission completion time for multi-UAV system are not directly applicable to our problem.

#### **3. System Model and Problem Formulation**

#### *3.1. System Model*

As shown in Figure 1, we consider a monitoring scenario where multiple rotary-wing UAVs are employed to collect information from sensors whose distributions follow the homogeneous Poisson Point Process. Traditionally, sensors transmit their monitored information to a base station via multi-hop transmissions. Therefore, a sensor is required to not only transmit its own information, but also relay the information of other sensors. As a consequence, the sensors battery may drain quickly and the multi-hop network connection may be lost [22]. By utilizing the UAVs as mobile information collectors, sensors can directly send monitored information to UAVs. However, as UAVs have limited on-board battery, it is important to reduce the completion time needed for the information collection mission. In this paper, we aim to minimize the maximum completion time among all UAVs by optimizing the trajectories of UAVs to complete the information collection mission as soon as possible. We assume the UAVs fly at a fixed altitude. The UAV collects information from sensors via time-division multiple access (TDMA) that means the UAV only communicates with at most one sensor at each time. Meanwhile, we consider a scenario where ground users are mainly composed of sensors. The extension to the three-dimensional (3D) trajectory planning and other multiple access schemes will be left for our future work. For convenience, Table 1 provides major notations used in this paper.

**Table 1.** Major notations .

The UAV and sensor sets are denoted as *U* Δ = {*u*1, ..., *uk*} and *P* Δ = {*p*1, ...., *pn*}, respectively. Considering a 3D Cartesian coordinate system, sensor *pj* is fixed at *cj* = (*xj*, *yj*, 0). Denote the trajectory of UAV *ui* projected on the ground as *li*(*t*)=[*xi*(*t*), *yi*(*t*)]*T* ∈ R2×1, where 0 ≤ *t* ≤ *T*. The trajectory of each UAV should satisfy the following constraint

$$l\_i(0) = l\_i(T), \forall i. \tag{1}$$

which means that the UAVs need to fly back to their starting location by the end of monitoring mission. Furthermore, the trajectory of each UAV is subject to the velocity constraints, which can be given by

$$\left\| \dot{l}\_i(t) \right\| \le \upsilon\_{\text{max}}, \forall i, t \in [0, T], \tag{2}$$

where *v*max denotes the maximum velocity of UAVs and · *li*(*t*) is the time derivative of *li*(*t*). As multi-UAV fly at the constant altitude, the trajectory of each UAV is expected to satisfy the collision avoidance constraint [36]

$$\|\|l\_i(t) - l\_{i'}(t)\|\| \ge d\_{\text{min}} \,\forall i \ne i', t \in [0, T], \tag{3}$$

where *d*min is the minimum distance between the UAVs for avoiding collision. In addition, the time-varying distance between UAV *ui* and sensor *pj* can be expressed as

$$d\_{i,j}(t) = \sqrt{H^2 + \left(\mathbf{x}\_i(t) - \mathbf{x}\_j\right)^2 + \left(y\_i(t) - y\_j\right)^2}.\tag{4}$$

Due to scattering and ground reflection, the communication channels between UAVs and sensors include both Line-of-Sight (LoS) and Non-Line-of Sight (NLoS) links [16]. The UAV–ground link channel is characterized by the presence of strong LoS path. The Rician channel model is an appropriate choice, as it can effectively reflect the combination of scattering and LoS that exists in the links between the UAVs and sensors [13]. In this paper, we consider the more practically Rician fading channels between the UAVs and sensors [13,16,37–39]. The instantaneous channel gains between the UAV *ui* and sensor *pj* can be expressed as [16,37]

$$h\_{i,j}(t) = \sqrt{\beta\_{i,j}(t)} g\_{i,j,\prime} \tag{5}$$

where *gi*,*j* is the small-scale fading coefficient. *βi*,*j*(*t*) is the average channel power gain, which can be expressed by [16,37]

$$\beta\_{i,j}(t) = \beta\_0 d\_{i,j}^{-a}(t) = \frac{\beta\_0}{\left[H^2 + (x\_i(t) - x\_j)^2 + (y\_i(t) - y\_j)\right]^{a/2}},\tag{6}$$

where *α* is the path loss exponent and *β*0 denotes the average channel power gain at the reference distance *d*0 = 1*m*. *gi*,*j* is a random variable that corresponds to the effects of the small-scale fading such that *E gi*,*j* 2 = 1, which can be given by [16,37]

$$g\_{i,j} = \sqrt{\frac{K\_R}{K\_R + 1}} \mathbf{g} + \sqrt{\frac{1}{K\_R + 1}} \mathbf{\bar{g}}\_{\prime} \tag{7}$$

where *KR* is the Rician factors of the channel and *g* denotes the deterministic LoS channel component with |*g*| = 1. *g*˜ represents the random scattered component which is a zero-mean unit-variance circularly symmetric complex Gaussian (CSCG) random variable. For Rician fading, the cdf of  *gi*,*j* 2 is explicitly represented as [37,38]

$$F\_{\left|\mathcal{G}\_{ij}\right|^2}(\mathbf{x}) = 1 - Q\_1(\sqrt{2K\_{\mathcal{R}}}, \sqrt{2(K\_{\mathcal{R}} + 1)\mathbf{x}}),\tag{8}$$

where *Q*1(*a*, *b*) is the standard Marcum-Q function. We assume that *p* is the transmission power of sensors. The instantaneous channel capacity is expressed as [36]

$$R\_{i,j}(t) = B \log\_2(1 + \frac{p|h\_{i,j}(t)|^2}{\sum\_{m=1, m \neq j}^n p|h\_{i,j}(t)|^2 x\_m(t) + \sigma^2}),\tag{9}$$

where *B* is the channel bandwidth and *σ*2 denotes the white Gaussian noise power at the receiver. The term *n* ∑ *m*=1,*m*=*j p*|*hi*,*m*(*t*)| 2 *xm*(*t*) in Equation (9) represents the co-channel interference caused by the transmissions of other sensors in time *t*. We denote a binary variable *xm*(*t*) to indicate whether sensor *pm* transmits information to UAVs at time *t*, which can be given by

$$\mathbf{x}\_m(t) = \begin{cases} 1 & p\_j \text{ transmits information to UAVs} \\ 0 & \text{otherwise} \end{cases} \tag{10}$$

The maximum communication radius projected on the ground is expressed by *r*, which depends on the maximum communication distance *d*max *U*−*S* and UAV altitude *H*, which is determined as [15,40]

$$r = \sqrt{d\_{ll-S}^{\max} ^2 - H^2} \,\text{}$$

*Sensors* **2019**, *19*, 4032

We assume that the UAVs fly at a determined altitude *H* when they collect information from the sensors. Therefore, *r* mainly depends on the maximum communication distance. To successfully collect information from sensors, the received power of UAV must be higher than or equal to the minimum decodable power *pU*,min [40]. The maximum communication distance between the sensor and the UAV can be calculated as

$$d\_{ll-S}^{\text{max}} = \sqrt{\frac{G\_S^t \cdot G\_{ll}^r \cdot \lambda^2 \cdot p}{\left(4\pi\right)^2 \cdot p\_{ll,\text{min}}}},\tag{12}$$

where *Gt S* is the transmit antenna gain of the sensor, *Gr U* is the receive antenna gain of the UAV. *λ* represents the wavelength of the signal transmitted by a sensor which is calculated by the frequency of signal. Based on the maximum communication radius *r*, the communication condition can be expressed as

$$\left\|\left|l\_i(\mathbf{t}) - \mathbf{c}\_j'\right|\right\| \le r,\tag{13}$$

where *cj* is the coordinate representation of sensor *pj* on a two-dimensional plane. It is worth noting that, if UAV *ui* needs to collect information from sensor *pj* at time *t*, in order to ensure reliable transmission, the distance between them must satisfy Equation (13).

We define a binary variable *fi*,*j*(*t*), and it indicates whether sensor *pj* is served by UAV *ui* at time *t*

$$f\_{i,j}(t) = \begin{cases} 1 & \text{ $u\_i$ } \text{ collect information from  $p\_j$ } \\ 0 & \text{otherwise} \end{cases} \tag{14}$$

The binary variables specify not only the communication scheduling across the different time, but also the association between UAVs and sensors. In this paper, the UAV collects information from sensors via TDMA that means the UAV only communicates with at most one sensor at each time. Meanwhile, each sensor is served by only one UAV at a time instance, but can be served by different UAVs over different time slots. These constraints can be expressed as

$$\sum\_{j=1}^{n} f\_{i,j}(t) \le 1, \forall i, j,\tag{15}$$

$$\sum\_{i=1}^{k} f\_{i,j}(t) \le \mathbf{1}\_{\prime} \forall i, j,\tag{16}$$

Furthermore, the total amount of data *R*¯ *j* transmitted from sensor *pj* to UAV *ui* is a function of UAV trajectory *li*(*t*), which is expressed as

$$\bar{R}\_{j}(l\_{i}(t)) = \int\_{0}^{T} B \log\_{2}(1 + \frac{p\left|h\_{i,j}(t)\right|^{2}}{\sum\_{m=1, m \neq j}^{n} p\left|h\_{i,j}(t)\right|^{2}x\_{m}(t) + \sigma^{2}}) f\_{i,j}(t)dt. \tag{17}$$

#### *3.2. Problem Formulation*

The throughput requirement corresponding to sensor *pj* is assumed to be *Cj* bits. By optimizing the trajectories of UAVs, our objective is to minimize mission completion time, while ensuring that the information of sensors is collected. The mission completion time refers to the time taken by all UAVs to complete respective tasks. The completion time of a UAV is mainly divided into two parts, flying time and hovering time. Therefore, the completion time of a single UAV can be represented as

$$T\_i = T\_F^i + T\_{H'}^i \tag{18}$$

where *Ti F* represents the flying time and *Ti H* represents the hovering time.

We denote **F** = { *fi*,*j*(*t*), ∀*i*, *j*, *t*} and **L** = {*li*(*t*), ∀*i*, *t*}. Assuming the sensors' locations are given, we aim to minimize the mission completion time by jointly optimizing the UAVs' trajectories (i.e., **L**), communication scheduling and association (i.e., **F**). Define *T*(**F**, **L**) = max 1≤*i*≤*k Ti* as the mission completion time which is a function of **F** and **L**. The optimization problem can be formulated as

$$\min\_{\mathbf{F}, \mathbf{L}, \{T\_H\}, \{T\_F\}} \quad T \tag{19}$$

$$\text{s.t.}\quad l\_i(0) = l\_i(T), \forall i,\tag{20}$$

$$
\bar{\mathcal{R}}\_{\rangle} \cong \mathbb{C}\_{\rangle}, \forall j, \tag{21}
$$

$$\sum\_{i=1}^{k} f\_{i,j}(t) \le 1, \forall i, j, t \in [0, T], \tag{22}$$

$$\sum\_{j=1}^{n} f\_{i,j}(t) \le 1, \forall i, j, t \in [0, T], \tag{23}$$

$$\left\| \left\| \dot{l}\_i(t) \right\| \right\| \le \upsilon\_{\max} \,\,\forall i, t \in [0, T]\_\prime \tag{24}$$

$$\|\|l\_i(t) - l\_{i'}(t)\|\| \ge d\_{\text{min}} \,\forall i \ne i', t \in [0, T], \tag{25}$$

$$0 \le \left| \left| l\_i(t) - c\_j' \right| \right| f\_{i,j}(t) \le r\_\prime \forall i, j, t \in [0, T]. \tag{26}$$