Interference-Aware Path Planning Optimization for Multiple UAVs in Beyond 5G Networks

I. INTRODUCTION

IN the upcoming sixth-generation (6G) networks, it is en-visioned that the use of unmanned aerial vehicles (UAVs)¹ in the form of flying (mobile) base station (FBS)² will play a significant role in augmenting the existing terrestrial wireless network operations in a plethora of different use cases such as information dissemination, on-demand hot spot data coverage and data collection for Internet of things (IoTs) [1]-[2]. Different types of events in urban or hot spot areas where a large number of users flock, e.g., a stadium, festival, parade, etc., might create severe congestion episodes on the network

¹Frequently used abbreviations are summarized in Table I.

²Hereafter, the terms of ‘UAV’ and ‘FBS’ are used interchangeably in the paper.

due to a concurrent high data demand that needs to be served by the fixed cellular network infrastructure. In such use case scenarios, UAV-assisted 5G/6G networks can boost network efficiency and flexibility by providing seamless on-demand ultra high capacity connectivity for elastic traffic in those areas. Moreover, FBSs can complement other areas beyond the coverage area of a terrestrial base station (BS) and support the existing ground-based heterogeneous network (HetNet) owing to their flexible 3D movement [2], [3]. Specifically, in a rural setting, it is easier for the FBS to reach areas with poor network coverage signal in agriculture, industry factories, construction zones, isolated areas, etc. In other words, the FBS can provide intelligent offloading of the data demand, which has a strong spatio-temporal correlation and seamless connectivity between source and destination [8]-[11]. However, these benefits come with a price in which the deployment of the FBS suffers from energy consumption due to its limited battery life when conducting the aforementioned assistance to the fixed network infrastructure. Therefore, some of the most challenging aspects in the deployment of the FBS have been recently paid attention related to reducing the energy with respect to minimizing consumed time (traveling time), optimizing trajectory planning and transmit power control, and maximizing data rate [9], [10]. However, little attention has been placed in orchestrating the trajectories of multiple FBSs, taking into account interference so that possible rendezvous points of the FBSs can be eliminated as the FBSs serve ground users (GUs), which will result in a substantial reduction of co- channel interference.

A. Related Work

The prior works in [12]-[17] proposed the deployment of UAVs as FBSs that use terrestrial BSs as a depot. In that case, FBSs depart for serving GUs and then return to the original BS (depot) after completing the service where battery re-charging can take place since UAVs are powered by onboard battery packs that can provide limited energy.

In the UAV-aided 5G/6G wireless network, a crucial aspect that need to be addressed is the UAV trajectory planning that determines the traveling (flying) path to serve different GUs. This is crucially important since the trajectory planning determines the overall traveling time, delivered service to the GUs, and the consumed energy from UAV [10]. The UAV trajectory planning optimization problem resembles the well- known traveling salesman problem (TSP) [16], [18], [19], as well as the vehicle routing problem (VRP) [17], [20]-[22]. To this end, various different TSP and VRP types of optimization models have been previously used to address the trajectory optimization problem in a spatially large distributed area. To put things in context, under the TSP/VRP context, a traveler or vehicle (in this case, a UAV) aims to find the lowest cost route in terms of distance so that it can visit all locations once and return to the origin (the depot; which in this case is the terrestrial BS); TSP and VRP are well-known NP- hard problems [23], and hence, both suffer from the curse of dimensionality which means that it is highly problematic to efficiently solve medium to large network instances. Interference avoidance and mitigation pertain to the problem of concurrent multiple wireless transmissions using the same channel (co-channel interference). It is of fundamental impor- tance in the design of wireless mobile communications since these networks are, in essence, interference limited. Various works [24]-[33] have addressed interference coordination in the deployment of UAVs in wireless networks. In particular, the works in [24]-[30] have studied the UAV’s trajectory to mitigate the interference. Moreover, a number of previous works [24]-[33] have particularly focused on the issue of power control coordination to improve the aggregate through- put of UAVs.

As a way to enhance the overall performance of the network, it is foreseeable to deploy multiple FBSs so that they coop- eratively serve GUs whilst fulfilling quality of service (QoS) constraints in terms of serving time windows. Furthermore, since the FBS’s onboard energy is considerably limited, they require a terrestrial macro cellular BS acting as a depot, where the FBSs are dispatched and return, which provides the necessary mechanism for the FBS to recharge in order to continue their missions. Despite the fact that this can be deemed as a critical aspect in creating an efficient FBS deployment, only a few studies have focused on this use case scenario [16], [17], [22].

B. Motivation and Contributions

Significant levels of co-channel interference can occur³ in the case of a single-cell and multiple FBSs simultaneously serving GUs in close spatial proximity. This scenario can be generalized for a typical multi-cell wireless network, where FBSs might create critical levels of interference in neighbor cells, i.e., interference between respective GUs at the edge cells caused by the FBSs dispatched from neighbor respec- tive BSs. For the case of a large number of neighboring cells, the network will inevitably require large-scale multi- cell cooperation in order to improve its performance [11]. This motivates the investigation of interference-aware path planning optimization schemes for multiple FBSs in a multi- cell network.

To the best of our knowledge, this is the first work in the design of optimal trajectory planning of multiple FBSs hosted at a terrestrial BS that amalgamates the following aspects in an explicit manner:

³A simple, albeit inefficient, the technique would be to partition radio resources so that different FBSs use orthogonal frequency resources. However, in this paper, to increase spectral efficiency, we assume that all FBSs use the same frequency resources, which is the most challenging use case scenario.

• Interference-aware trajectory planning optimization framework for multiple FBSs using a Hamiltonian path-based formulation in a large distributed area.

• Interference awareness under the unit disk graph (UDG) model; a model that has been widely used in the literature due to its ability to capture interference between adja- cent transmitting nodes [34]-[36], but has not yet been previously applied in the domain of UAV-aided mobile networks.

• QoS support by modeling time windows to serve dif- ferent GUs clustered at other different locations in a single/multi-macro cell network.

• Multiple FBSs deployment from the same macro BS or neighbour macro BSs in a single/multi-macro cell wireless network.

Fig. 1 illustrates the effect of FBS trajectory planning design in reducing interference levels when multiple FBSs serve GUs in a defined area. It is important to highlight that previous, closely related, research works [24]-[33] focused on interference mitigation via transmit power control for a set of links between a UAV and a set of served GUs or terminals, most closely resembling the case shown in Fig. 1(a). However, as illustrated in Fig. 1(b), our proposed interference-aware FBS trajectory planning scheme does not in essence allow that FBSs simultaneously serve GUs at close proximity; hence our focus is complementary to previous research works. In that respect, interference levels can be dramatically reduced and a less strict power control scheme can be utilized due to that reason. Therefore, our proposed scheme using the UDG model and integrated time variables allows for an efficient spatio- temporal orchestration of the FBSs so that overall network performance is increased. Furthermore, as already eluded, note that the proposed work is complementary with previous works since interference mitigation techniques (power control) can still be applied when an FBS hovers to serve a set of GUs. However, our emphasis is on interference avoidance which can allow simple power control techniques to be sufficient, such as fractional power control. This will result in reducing control plane overhead and increase scalability.

Moreover, the prior works [24]-[33] did not consider in- terference between different clusters of GUs distributed in a wireless macro-cell setting. More specifically, prior works [24]-[30] proposed an UAV trajectory optimization to miti- gate interference; however, these works did not consider the provision for optimal path planning design with multiple FBSs via a Hamiltonian path like formulation problem [23]. This is a critical differentiation since such an approach is appropriate to the large macro-cell scenario while at the same time taking into account specific QoS constraints in terms of time windows for serving GUs. Likewise, our focus on optimizing multiple FBSs residing at different macro-BS is considered to reflect a multi- cell network setting. On that frontier, few prior works [37]-[39] have studied the UAV deployment related to a nominal multi-cell wireless network, i.e., multiple depots.

The contributions and the novelties of this paper can be summarized as follows:

• We formulate a novel multiple FBSs trajectory planning optimization problem using a mixed integer linear programming (MILP) by explicitly taking into account interference with the UDG model that avoids the interference by establishing a circular graph. The proposed formulation explicitly models time windows for FBSs serving different clusters that allow different levels of service to be implemented. The goal of the problem is to minimize FBS travel time while increasing overall network capacity in the network.

• With the FBSs trajectory planning optimization problem, we consider use case scenarios representing both a single- cell and a typical multi-cell network where inter-cell interference causes a detrimental effect, especially for GUs located at the cell edge. Hence, the proposed trajec- tory planning optimization provides novel cell boundaries that have not been previously reported in the multi-cell network case by adopting an auxiliary variable [1] that enables FBS routes to be within a given cell. Since the optimization problem is inherently a mixed integer non-linear programming (MINLP), it is linearized by elimination product of variables [40].

• An interference-aware FBS trajectory planning heuristic algorithm is developed using the UDG model. The proposed heuristic algorithm is based on local search techniques (LSTs) [16], [41], which enables scalability with a competitive performance whilst having a low com- putational complexity compared to the optimal solutions.

• Finally, meticulous numerical investigations are presented

via a large number of Monte Carlo simulations to validate the performance of the proposed designs. It is shown that the proposed set of solutions that explicitly embrace inter- ference awareness outperform other benchmark schemes. The proposed approaches achieve a higher aggregate throughput with only a slight loss of travel time than that of the benchmarks.

Notation: The notation used throughout the paper is reported in Table I.

II. SYSTEM MODEL

A. Scenario

The underlying scenario of the UAV-assisted 5G/6G net- work is depicted in Figs. 1 and 3, which includes the opera- tional procedure of multiple FBSs hosted at a single terrestrial BS. The different steps in deploying FBSs are briefly described below,

• Without loss of generality, one and three hexagon cells are considered in the form of a single-cell and a multi- cell network, respectively. Via front-haul links, the cells are connected to the wireless access network and rele- vant cloud-based radio resource controllers where UAV orchestration occurs.

• A set of FBSs resides in a 5G/6G terrestrial macro BS that acts as a depot at the center of each cell. All FBSs are dispatched from a BS and visit all assigned CPs to serve GUs. Then, they return to the (same) BS in order to (re)charge their battery/(re)fuel.

• A cluster point (CP) is defined as the epicenter in the cluster of GUs as shown in Fig. 3. An FBS overflies and hovers at the CP to serve the GUs. A set of CPs are ran- domly distributed within a pre-determined geographical area in both the single-cell and the multi-cell network setting. The location of all CPs is shared with all BSs through the cloud controllers.

• A single FBS only serves each CP. The FBS starts to serve GUs via a downlink transmission scenario by hovering once arriving at the serving CP.

• The FBS equally serves those GUs for a pre-defined time period, which is called as the service time.

• Once the service is completed, an FBS moves to the next CP. When the FBS visited all assigned CPs, it returns to the macro-BS to offload collected data.

B. Network Model

Hereafter, without loss of generality, we assume that FBSs fly with constant velocity denoted as v and utilize the same altitude denoted as h. To fix ideas, the aforementioned UAV- assisted 5G/6G network is modeled as an undirected graph [TeX:] $$\mathcal{G} =(\mathcal{V}, \mathcal{A}), \text { where } \mathcal{V}=\mathcal{V}_{c} \cup \mathcal{V}_{d} \cdot \mathcal{V}_{c}=\{1,2, \cdots, N\}$$ denotes the set of CPs and [TeX:] $$\mathcal{V}_{d}=\{1,2, \cdots, M\}$$ denotes the set of depots (BSs) in 2-dimensional Cartesian coordinate system. [TeX:] $$\mathcal{A}=\{(i, j): i, j \in \mathcal{V}, i \neq j\}$$ is the set of links (routes) which is defined as [TeX:] $$d_{i j}$$, i.e., the Euclidean distance. The travel time that FBSs travel between vertices including CPs and a BS is denoted as [TeX:] $$t_{i j}$$ and it can be calculated by using the distance of the link with the FBS velocity [TeX:] $$v, \text { i.e., } t_{i j}=d_{i j} / v$$. The set of FBSs is denoted by [TeX:] $$\mathcal{K}=\{1,2, \cdots, K\} . \mathcal{C}=\{1,2, \cdots, C\}$$ indicates the set of cells, each of which includes a single BS and several CPs. CP i has time window [TeX:] $$\left[e_{i}, l_{i}\right], \text { where } e_{i} \leq l_{i}$$, during which an FBS starts serving GUs at CP i. Let [TeX:] $$S_{i}$$ be a constant service time when the FBS serves GUs to transmit data at CP i.

C. Air to Ground Channel Model

We adopt the most widely used air to ground channel model in order to calculate signal to interference plus noise ratio (SINR) and estimate the achievable throughput in the network. As detailed in [42] and [43], a user receives three components of signals which are the line of sight (LoS), the strong reflected signals, i.e., none LoS (NLoS) and multiple reflected signals contributing to the so-called multi-path fading. The path loss for the NLoS signal is caused by the shadowing effect and reflection of signals from obstacles, the impact of which is higher than the LoS signal. In this paper, since we are interested in the average signal strength rather than the instantaneous one, we only consider the effects of the LoS and NLoS channel impairments for the air to ground channel model [44].

The path loss for LoS and NLoS links can be represented as follows [42], [44]:

where [TeX:] $$L_{\mathrm{LoS}}$$ and [TeX:] $$L_{\mathrm{NLoS}}$$ are the average path loss in dB for LoS and NLoS links. We assume that an FBS is located at an altitude h and GUs are randomly distributed within a maximum radius of R meters from a point (CP) corresponding to the projection of the FBS onto the ground as described in Fig. 2. In Eqs. (1) and (2), [TeX:] $$\sqrt{.}$$ is expressed as the Euclidean distance between an FBS and a GU, and it indicates the elevation angle with respect to the GU. We consider the case where a GU is at a distant R from the point (CP) and the GU would be covered by two FBSs’s transmit coverage as described in [44Fig. 4]. [TeX:] $$c_{l}$$ is the speed of light and [TeX:] $$f_{c}$$ is the carrier frequency. In addition, [TeX:] $$\xi_{\mathrm{LoS}} \text { and } \xi_{\mathrm{NLoS}}$$ denote the average additional loss to the free space propagation loss which relies on the environment. The probability of LoS connections at the elevation angle of [TeX:] $$\tan ^{-1}(h / R)$$ can be written as [43],

where [TeX:] $$\alpha$$ and [TeX:] $$\beta$$ are constant values which depend on the environment, e,g,. rural, urban, dense urban, etc. In addition to the above, the probability with respect to the NLoS component is expressed as [TeX:] $$\mathbb{P}_{\mathrm{NLoS}}=1-\mathbb{P}_{\mathrm{LoS}}$$.

Finally, the average path loss L as a function of the altitude of the FBS and the radius of the coverage area is given as follows,

Given the above defined air to ground channel model, and assuming a constant transmit power [TeX:] $$P_{t}$$ of an FBS k, then, the received power [TeX:] $$P_{r, i, k}$$ in dB at CP i on the ground terminal can be written as follows,

D. UDG Model

UDG model has been widely used in the literature due to its ability to capture interference between adjacent transmitting nodes in a highly scalable and distributed manner [34]-[36]. This enables the design of efficient algorithms to create an interference disk graph where a set of nodes is connected by an edge if and only if their distance falls within a predefined interference range value. In this paper, the UDG model is described as a disk graph with a certain radius range denoted as [TeX:] $$\theta_{r}$$ from a point of an FBS which is vertically projection to the ground as illustrated in Fig. 2. The FBS travels with the UDG and it can detect other different UDGs traveled with the other FBSs once the UDG overlap the other UDGs (refer to Fig. 3(a)). Also, the location and coverage of UDGs are predictable given CPs and [TeX:] $$\theta_{r}$$ because FBSs with the UDG visit and hover over all CPs until all service is completed. In other words, the overlapping UDGs traveled with FBSs are calculated by Euclidean distance between the FBSs in 2- dimension area, i.e., [TeX:] $$d_{k k^{\prime}}=d_{i j}, k, k^{\prime} \in \mathcal{K}, i, j \in \mathcal{V}_{c}$$.

E. Average Achievable Throughput Measurement

Similar to the work in (5), we evaluate the aggregate achievable throughput (AAT) and SINR value at CPs for multiple FBSs in order to estimate the performance of the network (this aspect is addressed in Section V in detail). Specifically, the achieved SINR can be written as follows,

where [TeX:] $$\mathcal{N}_{0}$$ denotes the white noise power. Thus, we yield the achievable throughput as follows:

where B indicates the transmit bandwidth which has been nor- malized to 1 Hz and and [TeX:] $$\operatorname{SINR}_{i, k, u} \triangleq \operatorname{SINR}_{i, k} \cdot \text { Also, } \Delta_{i, k, u}$$ represents a fractional time slot that can detect a simultaneous overlapping service time period, i.e., [TeX:] $$s_{i}=\sum_{u=1}^{U} \Delta_{i, k, u}, \quad \forall i \in \mathcal{V}_{c,} \forall k \in \mathcal{K} .$$ Hence, the AAT in the network in terms of bps/Hz can be calculated as given by,

III. PROBLEM FORMULATION

A. UAV Trajectory Planning Formulation with Time Window and UDG Model in Cellular Networks

In this section, based on the discussed scenario and afore- mentioned system model, we address the proposed MILP formulation for path optimization with multiple FBSs while aiming to minimize the total FBS flying time with taking into account bounded cell setting. To this end, two decision variables of the model can be defined as follows,

where [TeX:] $$x_{i j k}$$ is binary and [TeX:] $$w_{i} \geq 0$$. We then enumerate several constraints to create an FBS trajectory and time window in the cell network as follows,

The constraints in (11a)-(11d) relate to the FBS trajectory with multiple FBSs in both a single-cell and a multi-cell setting. The constraint in (11a) ensures that an FBS travels from a vertex i to a vertex j, i.e., the link between vertices. The constraint in (11b) ensures that the number of FBSs denoted as [TeX:] $$\delta_{i}$$, which departs and return to BS i, is limited. The constraint in (11c) guarantees that an FBS leaves and arrives at a determined vertex. In other words, it guarantees flow conservation of the FBS route. The constraint in (11d) forces an FBS to visit more than two CPs⁵.

⁴The word ’vertex’ is used to include the expressions of both ’BS’ and ’CP’.

⁵In this paper, we do not consider the trivial case of two CPs.

The constraints in (12a)-(12f) represent time window for the FBS trajectory planning. In the constraints, by utilizing the big-M method [45], [TeX:] $$\lambda$$ is a sufficiently large constant. The constraint in (12a) guarantees the earliest time that an FBS k can start serving at CP i; e0 is the mission start time of an FBS k at the BS. Also, [TeX:] $$t_{i j}$$ denotes the travel time from BS i to CP j, i.e., the link between vertices. The constraint in (12b) ensures the timeline in which the FBS k arrives at CP j after arriving at CP i, serving in the service time s and traveling from the CP i to the CP j. Furthermore, [TeX:] $$s_{i}$$ denotes the service time at CP i. The constraint in (12c) ensures that an FBS k returns to the BS before the maximum window time [TeX:] $$l_{0}$$. Note that the constraints in (12a)-(12c) guarantee no subtours [46] discussed by Miller-Tucker-Zemlin (MTZ) formulation [47]. The constraints in (12d)-(12e) allow to obtain the accurate arrival time of FBSs at each CP. With the accurate arrival time of FBSs at CPs, overlap among serving FBSs can be detected in the time domain. The constraint in (12f) guarantees that GUs at CP i are served by an FBS within the time window, i.e., QoS support.

Based on the above constraints, a mathematical program for the FBS path planning with time windows and the UDG model in a single-cell network, which is also called optimal UAV trajectory planning in a single-cell network (OUT-S), is formulated as follows,

s. t.: (11a)-(11d), (12a)-(12f),

where [TeX:] $$\mathbf{W} \triangleq\left\{w_{i} \mid \forall i \in \mathcal{V}_{c}\right\}, \mathbf{X} \triangleq\left\{x_{i j k} \mid \forall i, j \in \mathcal{V}, \forall k \in \mathcal{K}\right\}$$. The goal of OUT-S is to minimize total travel time (TTT) for all FBS’s trajectories. Then, in order to create the multi-cell use case with predefined cell boundaries, the decision variable x should be revisited because it cannot support a link (route) that belongs to a specific cell [1], i.e., a feasible link in a cell with boundary. Therefore, we adopt the set of an auxiliary variable denoted as [TeX:] $$\mathbf{Q} \triangleq\left\{q_{i j c} \mid \forall i, j \in \mathcal{V}, \forall c \in \mathcal{C}\right\}$$ as given by,

which creates feasible or infeasible FBS routes in the given cell. This represents either feasible routes or infeasible routes, i.e., if a link between vertex i and vertex j is within a given cell c, then [TeX:] $$q_{i j c}=1$$, otherwise [TeX:] $$q_{i j c}=0$$.

By adding this variable, we formulate an FBSs path plan- ning formulation with time windows in a multi-cell network allowing for coverage and boundary of the given cell as a MILP mathematical program. In this case, the FBS path is estimated by defining a decision variable z as given by,

Hence, the CPs and the BS are separated in each set [TeX:] $$C_{m}$$, [TeX:] $$m \in \mathcal{V}_{d}$$. The adjusted multi-cell setting optimization problem can now be formulated as follows.

s. t.: (11a)-(11d), (12a)-(12f), (14)-(15),

where [TeX:] $$\mathbf{Z} \triangleq\left\{z_{i j k} \mid \forall i, j \in \mathcal{V}, \forall k \in \mathcal{K}\right\}$$. We note that since the constraint in (19) is obviously non-linear, the problem (P2) is a MINLP that is thus difficult to be solved directly. Therefore, this constraint is required to be transformed by exploiting an elimination of products technique [40] as given by,

By replacing the constraint in (19) with the constraints in (21a)-(21c), the novel optimization problem with linearization, which is also called optimal UAV trajectory planning in a multi-cell network (OUT-M), is formulated as follows,

s. t.: (11a)−(11d), (12a)−(12f), (14)−(15), (20), (21a)−(21c),

The goal of OUT-M is to minimize the TTT for all FBS’s trajectories. The OUT-M corresponds to optimizing an FBS trajectory only feasible to fly over each given cell. In the problem OUT-M, the constraint in (23) activates links (routes) of the variable z in the network, the number of which is equal to the summation of both the number of CPs (N) and the number of FBSs (K ).

B. Interference-Aware UAV Trajectory Planning Formulation with Time Window under UDG Model

It is worth emphasizing that the above optimal solutions are oblivious to the effects of strong co-channel interference that might be caused by when multiple FBSs visit CPs and serve GUs in close proximity, which has detrimental effects on the achievable data rate for the transmission. An example of such potential occurrence is shown in Fig. 3(a). As can be seen from the figure, there is an overlap on the time domain when FBSs k and [TeX:] $$k^{\prime}$$ visit those two CPs (i and s) fell within the UDG range which also means in close proximity. Therefore, in order to avoid the interference, we propose an FBS interference-aware path planning optimization design with the UDG model to increase overall network performance in terms of the achievable throughput.

To this end, based on the defined preliminaries with the decision variables described in (9), (10), and (17), we additionally define a decision variable y as follows,

where [TeX:] $$i, j(i \neq j) \in \psi_{h}, \psi_{h} \in \Psi \text {, in which } \Psi=\left\{\psi_{1}, \cdots, \psi_{r}\right\}$$ and [TeX:] $$\psi$$ denotes two different CPs that fall within the interference range with the UDG model and hence the two CPs cannot be served simultaneously if they are in close proximity. Thus, the proposed interference-aware FBS path planning formulation with the UDG model and time windows in a single-cell network follows the ones detailed in the previous section with the addition of the following constraints, which is called optimal UAV trajectory planning in a single-cell network with interference awareness (OUT-SIA).

s. t.: (11a)-(11d), (12a)-(12f), (14)-(15),

where [TeX:] $$\mathbf{Y} \triangleq\left\{y_{i j} \mid \forall i, j \in \psi_{h}\right\}$$. The goal of OUT-SIA is to minimize the TTT for all FBS’s trajectories. The constraint in (26) ensures that if the variable [TeX:] $$y_{i j}$$ is 1, then the [TeX:] $$y_{j i}$$ is 0 and vice versa. The constraint in (27) ensures that if the variable [TeX:] $$y_{i j}$$ is 1, then the service at CP i without overlap of the service at CP j under the UDG is guaranteed. The constraint in (28) represents that the variable y is binary.

We also propose an interference-aware FBS path planning formulation with the UDG model and time windows in a multi- cell network, which is also called Optimal UAV Trajectory planning in a Multi-cell network with Interference Awareness (OUT-MIA), as follows,

s. t.: (11a)−(11d), (12a)−(12f), (14)−(15), (20), (21a)−(21c), (23), (26)−(28).

The goal of OUT-MIA is to minimize the TTT for all FBS’s trajectories. The OUT-x⁶ (S/M) is only able to detect where the interference occurs with the UDG model. However, as depicted in the Fig. 3(b), the OUT-MIA is aware of the area and avoid the epicenter where more than two FBSs are simultaneously served in close proximity using the UDG model, and exploits the additional constraints in (26)−(28) to enforce non-overlapping service times on the time domain. In other words, FBSs with the UDG will in turn change their route to avoid the strong interference in the OUT-xIA

⁶The term ‘x’represents both the single-cell indicated by ‘S’ and the multi- cell indicated by ‘M’.

(SIA/MIA). For example, as shown in Fig. 3(b), the FBS [TeX:] $$k^{\prime}$$ travels to the CP r for the service instead of traveling towards the CP s.

IV. PROPOSED SET OF HEURISTIC ALGORITHMS

In this section, we propose both a local search heuristic under the UDG model and an interference-aware local search heuristic under the UDG model, which are called a Heuristic UAV Trajectory planning in single/multi-cell network (HUT- x (S/M)) algorithm and a Heuristic UAV Trajectory planning with Interference-Aware in single/multi-cell network (HUT- xIA (SIA/MIA)) algorithm respectively, as a scale-free one in order to tackle the curse of dimensionality of the underlying optimization problems. The pseudo codes are summarized in Alg. 1 and Alg. 2 respectively. Both heuristic algorithms take interference into consideration by using the UDG model. Also, they exploit the well-known LST, i.e., 2-Opt, Relocate, Swap and Randomization [16], [41], which is appropriate to finding the lowest cost for path planning. The HUT-x only detects interference that cooperatively occurs between FBSs, while the HUT-xIA is aware of the interference and capable of avoiding it. The LST provides FBS routes, which consists of a set of strings of numbers, with a mixture described in [1].

The HUT-xIA iteratively creates string-based FBSs route by using the LST while maintaining avoidance of interference in Repeat-Until loop represented in the Step 6–16 of Alg. 2 until sum(H(j)) == 0 converges. In the loop, if the distance between CP i and j (to be served by each FBS) is shorter than the UDG range [TeX:] $$\theta_{r}, \text { then } \mathcal{J}(i, j)=1 \text {, otherwise, } \mathcal{J}(i, j)=0 \text {. }$$. [TeX:] $$\text { With } \mathcal{J}(i, j)=1 \text {, if the FBS } k^{\prime}$$ serves GUs at CP j while

the FBS k is already serving GUs at CP i, then H(j) = 1, otherwise H(j) = 0. Hence, the loop is repeated until the summation of the H(j) is equal to zero, i.e., interference does not occur at all CPs. Once the loop achieves convergence that creates FBSs routes (paths) with minimizing interference, the final FBSs routes are constructed. Then, the whole process is repeated by the iteration number [TeX:] $$I_{t}$$ and the best path is adopted in greedy manner. To this end, the goal of the algorithm is to improve the total cost in order to find competitive paths with minimization of interference in the case of proximate FBSs.

V. NUMERICAL INVESTIGATIONS

In this section, we provide a wide set of numerical investiga- tions by Monte Carlo simulations to evaluate the performance of the proposed schemes compared to previously proposed techniques by operating with Intlinprog solver in MATLAB.

Table II summarizes system model parameters that have been used for the simulations. We vary the number of CPs

(N), BSs (M) and the radius θr of the UDG model. The CPs incorporating a cluster of GUs are randomly distributed in a large predefined geographical area, i.e., a single-cell and a multi-cell with the cell radius. In the multi-cell, it is worth noticing that the CPs are only distributed in inter-cell areas getting involved at the edge of the cells in the case of high competition of FBS’s service (as shown in Fig. 5).

We adopt an UAV modelled with rotary wings [19]. In [19], the UAV with rotary wings is deployed with two components of energy consumption, i.e., traveling energy and hovering energy. Moreover, the authors [19] derived the optimal velocity of the UAV that minimizes the energy consumption while maximizing the UAV endurance. This modeling can be applied to our system. Therefore, we assume the velocity v of the FBS

is the optimal value, i.e., 10.21 m/s (further details can be seen in [19Fig. 2]).

Without loss of generality, the value of the service time⁷ s at the CPs [TeX:] $$\left(\text { i.e., } s_{i} \triangleq s\right)$$, the altitude h, the transmit bandwidth B, the transmit power [TeX:] $$P_{t}$$ and carrier frequency [TeX:] $$f_{c}$$ of all FBSs are assumed to be identical. Moreover, the number of FBSs (K) are fixed to three as multiple FBSs⁸. The parameterization of [TeX:] $$\alpha, \beta, \xi_{\mathrm{LaS}}$$ and [TeX:] $$\xi_{\mathrm{NLos}}$$ is selected so as to represent a typical urban environment, and the SINR threshold [TeX:] $$\gamma_{\text {th }}$$ is set to 10 dB [44]. Setting an appropriate UDG radius depends on the SINR requirements and hereafter we detail how the SINR requirements are linked with selecting a range [TeX:] $$\theta_{r}$$ for the UDG radius. To this end, in order for [TeX:] $$\operatorname{SINR}_{i, k}>\gamma_{\text {th }}$$ at each CP, we set the UDG range [TeX:] $$\theta_{r}$$ as 250 to 350m, i.e., [TeX:] $$\theta_{r}>\arg \min _{d_{i j}}\left(\mathrm{SINR}_{i, k}>\gamma_{\mathrm{th}}\right), \forall i, j \in \mathcal{V}_{c}$$.

We compare the proposed approaches OUT-xIA and HUT- xIA, which are enabled to be aware of interference, with two baselines which are described below,

• OUT-x (S/M): These schemes have been developed as both the optimal solution (P1) and (P3) in the Sec- tion III-A. They are oblivious of interference, which means that FBSs are not able to avoid strong interference when multiple FBSs simultaneously serve in proximity.

⁷Typically, the service time is considered as a random variable (in most cases an exponential distribution is used and an assumption comes back from the days of telephony). We decided to avoid including another level of randomization from the outset in the numerical investigations so that we flesh out the gains of the proposed solutions in a clearer manner. In essence, we assume a constant service time s that is equal to the mean value of a given exponential function.

⁸The simulation is stopped at 120 minutes running time, which is the case when the following parameters were combined and exceeded these values: N >18, K >3, θr >350.

However, they are still able to detect the interference under the UDG model.

• HUT-x (S/M): These schemes are the local search heuristic algorithm summarized in Alg. 1 based on state of the art techniques, i.e., the LST, [16], [41], which also operates in the same manner as OUT-x.

We note that from the baseline schemes mentioned above, the OUT-S and the HUT-S schemes resemble the widely used conventional schemes, i.e., the single-cell setting and the UAV deployment returning to an original depot without explicitly

taking into account interference as well as considering a multi- cell wireless network [17], [22].

A. FBS Trajectory Analysis

Figs. 4 and 5 illustrate examples of nominal FBSs trajectories with the parameters K=3, N=12, and [TeX:] $$\theta_{r}=300$$ for all different schemes in a single-cell (M = 1) and a multi cell (M = 3) network scenario. Note that the numbers 13, 14, and 15 represent macro BSs that act as depots which are the locations where the FBSs depart and return. The black arrows represent directions of the FBSs and the black dotted circles indicate the spots where interference is detected. To provide a more in-depth analysis in Fig. 5, we zoomed in the edges of the three hexagon cells where FBSs of adjacent BSs are located in close proximity, hence representing the worst-case interference scenario. We note that the OUT-xIA and HUT-xIA schemes manage to completely avoid the interference under the UDG model, while the OUT-x and the HUT-x schemes that are interference-oblivious (i.e., the first without the constraints in (26)−(28) and the second without the Repeat-Until loop in the Steps 6–16 of Alg. 2) cannot eliminate rendezvous points of FBSs (i.e., FBSs in close proximity), hence allowing high levels of interference as shown in Figs. 4 and 5.

Specifically, both the OUT-x and HUT-x schemes create a few areas where strong interference is taking place as depicted by the black dotted circles. Whereas, observe that for the proposed OUT-xIA and HUT-xIA schemes, there are no areas of strong interference (i.e., no rendezvous points) and it is also interesting to notice that the two proposed schemes minimize the interference even though the FBSs utilize different trajectories; in other words, they manage to find paths without increasing total travel time (TTT) in order to provide strong interference avoidance in the network.

B. TTT and AAT Performance

Figs. 6 and 7 show TTT and AAT with respect to the different size of [TeX:] $$\theta_{r}$$ of UDG and the number of N for all schemes. In general, as the number of N is increased, AAT of the proposed OUT-xIA and HUT-xIA turn significantly higher than that of two baselines, OUT-x and HUT-x. Specifically, the gain of AAT of OUT-SIA obtained is around 15.7% when [TeX:] $$\theta_{r}=350, N=18$$ compared to the OUT-S and the gain of AAT of OUT-MIA obtained is around 14.9% when [TeX:] $$\theta_{r}=300$$, N = 9 compared to the OUT-M. Similarly, the AAT of HUT- SIA gained about 14.6% when [TeX:] $$\theta_{r}=300, N=18$$ compared to the OUT-S and the AAT of HUT-MIA gained approximately 20.8% when [TeX:] $$\theta_{r}=350, N=15$$ compared to the HUT-M. In terms of TTT, all schemes generally gained similar values, which means that the overall energy consumption of the FBS is not increased since the majority of it is consumed for the traveling time [10], [19]. The TTT of the multi-cell is generally higher than that of the single-cell as the FBS trajectory is less flexible to be changed in the multi-cell network. Furthermore, as expected, the TTT of HUT-xIA was slightly higher than that of OUT-xIA since HUT-SIA and HUT-MIA are suboptimal solutions.

As the size of [TeX:] $$\theta_{r}$$ is increased, the gain of AAT of all the proposed solutions is generally also increased. Whereas, the computational time of the proposed optimal solutions is exponentially climbed (this is represented in Section V-D). It is interesting to notice that a few of cases of the AAT of HUT- xIA are higher than that of OUT-xIA, e.g., [TeX:] $$\theta_{r}=250,350$$, since the underlying focus is on the objective with minimizing the FBS’s traveling time. Whereas, the TTT of HUT-xIA is always greater than OUT-SIA since HUT-xIA is in essence suboptimal solutions to the objective.

C. Interference Detection and Outage Events

In this subsection, we focus on the number of interference detection events under the UDG model (ID-UDG) per a mission where all FBSs return to the BS as well as provide an analysis of outage events (OE) where the SINR value is compared with [TeX:] $$\gamma \text { th }$$ in each CP. These metrics are measured using the following binary variables,

where [TeX:] $$\forall i \in \mathcal{V}_{c} . \text { Hence, } \mathbb{U}$$, which is defined as the number of ID-UDG, can be given by,

where [TeX:] $$\mathbb{U} \leq N$$. In the similar way, E, which is defined as the • number of OE, can be expressed as,

where [TeX:] $$\mathbb{E} \leq N$$.

Figs. 8 and 9 describe U and E respectively according to the size of [TeX:] $$\theta_{r}$$ and N for all schemes. It is clear that the proposed OUT-xIA and HUT-xIA manage to construct FBS paths with no UDG-based interference, i.e., U = 0, and achieve a SINR greater than the [TeX:] $$\gamma \text { th }$$ value, i.e., E = 0, in the entire simulations. Moreover, it is noticeable that the U and the E values of the OUT-x and the HUT-x have an upward trend as the size of [TeX:] $$\theta_{r}$$ is increasing. Note that the U and the E values of the OUT- M and HUT-M are slightly greater than those of the OUT-S and the HUT-S in general. This is because in the multi-cell scenario, the number of FBSs rendezvous points is increasing and as a result the number of strong interference events is expected to increase.

D. Scalability and Complexity Analysis

We present performance comparison between the optimal solutions and the proposed algorithms in network instances where optimal solutions could be achieved. The computational dimensionality of the optimization problems is as follows,

• [TeX:] $$OUT-S: $|\mathcal{V}|+2\left|\mathcal{V}_{c}\right|+\left|\mathcal{V}_{d}\right|+|\mathcal{K}||\mathcal{V}|+4|\mathcal{K}|\left|\mathcal{V}_{c}\right|\left|\mathcal{V}_{d}\right|+2\left|\mathcal{V}_{c}\right|^{2}+$ $|\mathcal{K}||\mathcal{V}|^{2}$$$

• [TeX:] $$OUT-M: $|\mathcal{V}|+2\left|\mathcal{V}_{c}\right|+\left|\mathcal{V}_{d}\right|+|\mathcal{K}||\mathcal{V}|+4|\mathcal{K}|\left|\mathcal{V}_{c}\right|\left|\mathcal{V}_{d}\right|+$ $2\left|\mathcal{V}_{c}\right|^{2}+3|\mathcal{K}||\mathcal{V}|^{2}+2|\mathcal{K}||\mathcal{C}||\mathcal{V}|^{2}+|\mathcal{K}|\left|\mathcal{V}_{c} \| \mathcal{V}\right|^{2}$$$

• [TeX:] $$OUT-SIA: $|\mathcal{V}|+2\left|\mathcal{V}_{c}\right|+\left|\mathcal{V}_{d}\right|+|\mathcal{K}||\mathcal{V}|+4|\mathcal{K}|\left|\mathcal{V}_{c}\right|\left|\mathcal{V}_{d}\right|+$ $2\left|\mathcal{V}_{c}\right|^{2}+|\mathcal{K}||\mathcal{V}|^{2}+3|\Psi|^{2}$$$

• [TeX:] $$OUT-MIA: $|\mathcal{V}|+2\left|\mathcal{V}_{c}\right|+\left|\mathcal{V}_{d}\right|+|\mathcal{K}||\mathcal{V}|+4|\mathcal{K}|\left|\mathcal{V}_{c}\right|\left|\mathcal{V}_{d}\right|+$ $2\left|\mathcal{V}_{c}\right|^{2}+3|\mathcal{K}||\mathcal{V}|^{2}+2|\mathcal{K}||\mathcal{C}||\mathcal{V}|^{2}+|\mathcal{K}|\left|\mathcal{V}_{c} \| \mathcal{V}\right|^{2}+3|\Psi|^{2} .$$$

These cause substantial increase in the search space, resulting in significant difficulty to obtain optimal solutions for medium to large network instances. Table III shows the effect of parameters K , N , M , and [TeX:] $$\theta_{r}$$ on the complexity and scalability of the simulations. Note the exponential growth of both the decision variables and the number of constraints. However, in terms of the complexity, the HUT-x and the proposed HUT-xIA have [TeX:] $$\mathcal{O}\left(I_{t} N K(N+K)^{2}\right) \text { and } \mathcal{O}\left(I_{t} N K(N+K)^{2} \zeta\right)$$, respectively, which are simply yielded by parameters [TeX:] $$I_{t}, K, N$$ and [TeX:] $$\zeta$$. Specifically, N , K , and [TeX:] $$I_{t}$$ of the complexity represent the effect of the iterations and [TeX:] $$(N+K)^{2}$$ represents the worst case complexity of the LST algorithm, i.e., 2-Opt, in the Alg. 1 and Alg. 2. We note that [TeX:] $$\zeta$$ denotes one iteration of the Repeat- Until loop given in the Steps 6–16 in Alg. 2. A wide set of investigations for the Alg. 2, i.e., HUT-xIA, reveal that we can reach convergence with only few iterations (less than 20 on average in the simulations) and in a computational efficient manner, i.e., 0.5 ms to 5 ms⁹. This implies that a network orchestrator can compute the trajectories of the multiple FBSs in real-time.

In general, since OUT-x and OUT-xIA are in the category of NP-hard (the proof can be seen in the Appendix VI), they require significant higher computational time compared to the HUT-x and HUT-xIA solutions as shown in Table III. Furthermore, the computational time for all solutions has, as expected, a growing trend as the parameters of the network instance increase. To this end, observe that the OUT-xIA scheme is experiencing the highest computational complexity. On the other hand, a key aspect worth pointing out is that both the proposed HUT-xIA algorithms provide competitive solutions in low computation time for large network instances, rendering them amenable for real-time implementation. It is also worth noticing that the computation time of the proposed HUT-SIA is much lower than that of the OUT-SIA, which attained nearly 488.5 times in computational reduction when [TeX:] $$K=3, N=18, M=1, \theta_{r}=350 .$$ Similarly, the computation time of the proposed HUT-MIA is approximately 130.6 times faster than that of the OUT-MIA, when [TeX:] $$K=3, N=18$$ [TeX:] $$M=3, \theta_{r}=350$$. Therefore, by accepting a minimal loss of the network capacity (i.e., optimality of the solution), the performance of both greedy and iterative HUT-xIA algorithms can be deemed as acceptable.

VI. CONCLUSIONS

This paper presents an interference-aware path planning optimization model under Hamiltonian paths with adjustable time windows to allow service differentiation for multiple UAVs operating as flying base stations (FBSs) deployed from a single or multiple macro-BSs acting as their depots in a single or multi-cell mobile network. A key innovative as- pect is that the proposed optimization schemes modeled by MILP formulations and the associated heuristic algorithms incorporate the unit disk graph (UDG) interference model to enable interference avoidance in a highly scale free manner and by doing so they provide FBSs trajectories that minimize aggregate co-channel interference between different serving FBSs, translating in an increased aggregate network capacity. A wide set of numerical investigations reveal that the proposed solutions allow for approximately 21% gains (with 50% maximum gains) in the average achievable throughput (AAT) as well as enabling real-time implementation and low control plane overhead due to the use of the UDG model, whilst being able to maintain a similar level of total traveling time (TTT) compared to interference-oblivious solutions (which means that the overall energy consumption in the network is not increased). The proposed set of solutions have a number of implications in the orchestration of FBSs in beyond 5G networks. We have shown that the interference-aware trajectory planning design can reduce rendezvous points of FBSs and therefore ease aggregate strong interference resulting in simpler and more

⁹We ran a personal computer with Intel i5-4690@3.5GHz and 16GB RAM in the simulation.

efficient closed-loop power control schemes to be utilized as constraints. Moreover, the proposed set of schemes can be included as scalable algorithms in network orchestration procedures related to UAV-aided beyond 5G networks in order to enable an efficient integration of aerial platforms with the fixed network infrastructure.

APPENDIX A PROOF OF NP-HARDNESS

Lemma 1. OUT-x and OUT-xIA are NP-hard problems.

Proof. Recall that the constraints (11a)−(11c) capture the FBSs trajectory route constraints, whilst the constraints (12a)−(12c) ensure that a Hamiltonian cycle is created via sub-tour elimination. Therefore, if we eliminate the time window constraints the problem reduces to the TSP since the objective function seeks for paths with minimal aggregate total travel time. Hence, the underlying optimization problem resembles the conventional VRP and the minimum cost tour concept of TSP. Therefore, both the OUT-x and OUT-xIA optimization problems, as presented in the form of an MILP, encapsulate a TSP-like tour in terms of trajectory planning and as a result they are as hard as the TSP problem and therefore fall into the well-known NP-hard [23] set of problems.