# QoS-Aware Multilayer UAV Deployment to Provide VoWiFi Service over 5G Networks

Authors: Vicente Mayor; Rafael Estepa; Antonio Estepa
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Drones equipped with wireless network cards can provide communication services in open areas. This paper proposes a hierarchical two-layered network architecture with two types of drones according to their communication equipment: Access and Distribution. While access drones provide WiFi access to ground users, distribution drones act as WiFi-to-5G relay forwarding packets into the 5G Core Network. In this context, we formulate a novel optimization problem for the 3-D initial placement of drones to provide Voice over WiFi (VoWiFi) service to ground users. Our optimization problem finds the minimum number of drones (and their type and location) to be deployed constrained to coverage and minimum voice speech quality. We have used a well-known metaheuristic algorithm (Particle Swarm Optimization) to solve our problem, examining the results obtained for different terrain sizes (from25m×25m to 100m×100m) and ground users (from 10 to 100). In the most demanding case, we were able to provide VoWiFi service with four distribution drones and five access drones. Our results show that the overall number of UAVs deployed grows with the terrain size (i.e., with users’ sparsity) and the number of ground users.


---

## Body

## 1. Introduction

Unmanned Aerial Vehicles (UAVs), also known as drones, have been widely studied in the literature for the last decade partly due to their versatility, which lets UAVs be used in different domains [1]. The application considered in this paper is the UAV-assisted deployment of wireless communication services in open areas [2, 3]. UAVs equipped with communication electronics have been proposed in the past as mobile base stations or access points to enhance wireless coverage, improve capacity or reliability in existing infrastructure, or even replace damaged infrastructure in emergency situations [4, 5].Provisioning a communication service to ground users typically requires the deployment of a UAV-to-ground access network and, if not in place, a UAV-to-UAV and/or UAV-to-infrastructure network or backhaul [6]. Most research papers tend to focus on only one of these networks and its associated communication technology (e.g., WiMAX [7], cellular 3/4G [8], or 5G [9] for the backhaul and cellular for the access network). Clearly, ground users’ devices must share the radio technology in the access network, which could be a problem in practice often overlooked (e.g., scarcity of 5G users or the involvement of a telco operator). For this reason, some works have also suggested the use of WiFi [10–12] for the UAV-to-ground access network due to its low complexity, ubiquity (e.g., smartphones, tablets and some IoT devices), and independence from operators. UAV-enabled WiFi deployments bring new opportunities when creating provisional communications infrastructure in SAR (Search and Rescue) missions, which is actively investigated in scientific literature nowadays [12, 13]. However, designing a WiFi access network requires dealing with signal coverage and Quality of Service (QoS) issues at the IEEE 802.11 MAC sublayer. This challenge is translated to the problems addressed in the literature, such as 3-D placement, trajectory planning, energy efficiency, coverage, or backhaul connectivity [6, 14].In this paper, we propose using UAVs to form a two-level hierarchical network that relays between IEEE 802.11 (WiFi) and cellular 5G for providing VoIP over WiFi (VoWiFi) service to ground users (see Figure1). Access network drones implement WiFi, while distribution/backhaul drones implement a gateway between WiFi and 5G. This combination of technologies leverages the high bandwidth of 5G (up to 1 Gbps) to aggregate VoIP traffic flows in a low number of 5G radio links, reducing the number of mobile subscriptions and costs in 5G equipment. In this scenario, we address the problem of the initial 3-D placement of the UAVs in both networks. As Masroor et al. put it [4], “the placement of UAVs is an important parameter of resource management as this can affect the transmit power, coverage, and the QoS of the system.” More specifically, we propose a new optimization problem that considers constraints about signal coverage and QoS and finds the minimum number of drones that need to be deployed, their position, and type (i.e., access network—A-UAV—or distribution-network—D-UAV). This work extends our previous research [15, 16], where we studied the deployment of drones to form a WiFi access network for VoIP services. Now, we integrate the access network into a 5G Core Network using a second layer of drones that hove at a higher altitude and aggregate the VoIP traffic flows. Note that in this scenario, the quality of service depends not only on the congestion level of the access network but also on the distribution network and 5G operator backbone SLAs (Service Level Agreement). As such, UAVs’ optimal position may depend on users’ location, VoIP capacity, and backbone link capacity.Figure 1
Proposed scenario.The main contributions of this paper are as follows:(i)
We mathematically formulate a new problem for the optimal deployment of UAVs that includes coverage and QoS constraints in the access (WiFi), distribution (WiFi), and backbone (5G) networks.(ii)
We propose a novel network reference architecture for the proposed scenario that provides seamless Voice over WiFi (VoWiFi) access to the 5G Core Network.(iii)
We provide an analytical model to estimate the speech quality in our multilayered scenario. Our models assume realistic traffic conditions such as heterogeneous and nonsaturated stations.(iv)
We use a metaheuristic search method (i.e., Particle Swarm Optimization) to solve the previous optimization problem.The remainder of the paper is as follows. Section2 presents a state-of-the-art analysis of UAV optimization problems for communications services. Then, Section 3 elaborates on the proposed network architecture and the voice quality assessment method. The proposed optimization problem is defined in Section 4, and Section 5 presents a solution search method based on a well-known meta-heuristics algorithm (Particle Swarm Optimization). Then, we examine the solutions obtained for different scenarios in Section 6 and analyze the performance. Finally, Section 7 summarizes the paper by providing conclusions and future work.


## 2. Related Works

The optimal placement of UAVs has been identified as an open challenge in the context of communication services that use drones as base stations (BS) or relaying nodes in 2D, 3D, single-, and multi-UAV environments [5]. Table 1 summarizes the state of the art in UAV optimal location optimization problems for wireless coverage provisioning and clarifies how our work is different from related works. Works in Table 1 are classified in terms of (a) their objective function, (b) optimization variables (e.g., initial placement, trajectory, or resource allocation), and (c) any other constraints or considerations that might restrict its usage to a concrete scenario.Table 1
Related work comparison.
Ref.Objective functionVariablesNetwork technologiesConsiderationsPlacementTrajectoryResource allocationAccessBackboneSINRBWSpeech qualityEnergy[17]max. throughput✓✗✗FDMAFDMA✓✗✗✗[18]max. throughput✓✗✓CellularCellular✓✗✗✓[19]max. throughput✓✗✓CellularCellular✓✓✗✗[20]max. downlink rate✓✗✓CellularCellular✓✗✗✗[21]min. maximum traffic demand✓✗✓CellularCellular✓✗✗✗[22]min. path loss✓✗✓NOMACellular✓✗✗✓[23]min. transmit power or max. rate✓✗✓NOMACellular✓✗✗✓[24]min. UAVs and max. coverage✓✓✓CellularCellular✓✓✗✗[25]min. UAVs and max. coverage✓✓✓CellularCellular✓✓✗✗[26]max. energy efficiency✗✓✗mmWaveCellular✓✗✗✓[27]min. power allocation✗✓✓OFDMAOFDMA✓✗✗✓[28]min. energy consumption✗✓✓CellularCellular✓✗✗✓[29]max. spectrum and energy eff.✗✓✓TDDTDD✗✗✗✓[30]max. spectrum and energy eff.✗✓✓TDDTDD✗✗✗✓[31]max. minimum throughput✗✓✓CellularCellular✗✓✗✗[32]max. minimum user rate✗✓✓OFDMAOFDMA✓✗✗✗[33]max. minimum user rate✗✓✓TDMATDMA✓✗✗✓[34]max. end-to-end throughput✗✓✓CellularCellular✓✗✗✓[35]max. end-to-end throughput✗✓✓CellularCellular✓✗✗✓[36]min. outage probability✗✓✓CellularCellular✓✗✗✓[15]min. UAVs and user radio energy✓ (single-layer)✗✓WiFiN/A✓✓✓✓[16]min. UAVs and UAVs’ energy✓ (single-layer)✗✓WiFiN/A✓✓✓✓This papermin. UAVs and user coverage✓ (multilayer)✗✓WiFi5G✓✓✓✗Optimal UAV placement for wireless coverage counts with a good deal of optimization problems in the literature. For example, Li et al. [17] propose to maximize throughput via power allocation and 3D placement for indoor communications. Maximizing the throughput has also been addressed in [18], where the authors suggest a 3D UAV placement and power allocation optimization problem based on software-defined cellular networks, or in [19] that also employs software-defined cellular networks but using rate instead of power allocation. Similarly, Yin et al. [20] suggest deploying a cellular network (FDMA) by maximizing the downlink rate under three optimization variables: user association, resource allocation, and UAV placement. Other authors [21] suggest combining UAV placement with user association in order to minimize the maximum traffic demand at UAVs, achieving a fair traffic distribution among them; or the deployment of NOMA (Nonorthogonal Multiple Access) networks to mitigate the path loss (i.e., maximize received signal strength) or energy consumption due to transmit power [22, 23], respectively. Finally, in [24, 25], the authors propose to minimize the number of deployed UAVs while finding the positioning that maximizes the coverage area while forming a robust backbone network.Besides optimal initial positioning, trajectory optimization (i.e., a series of discrete points of a flying path that drones follow in a continuous movement while providing wireless network coverage [4]) has also been widely addressed, mainly focusing on energy efficiency. Chakareski et al. [26] proposed an energy-efficient framework for deploying mmWave 5G cellular networks, in [27, 28], the authors proposed a joint optimization problem for trajectory and power allocation, and finally, [29, 30] present a joint spectrum and energy efficiency optimization problem. Through put maximization optimization via trajectory has also been proposed in several works. Hu et al. [31] proposed a resource and trajectory optimization problem by introducing user scheduling and bandwidth allocation; and [32, 33] proposed to combine trajectory with radio resource allocation in vehicular and UAV-enabled relaying systems. Finally, other works such as [34, 35] proposed to maximize the end-to-end rate by considering trajectory power allocation optimization while deploying multi-hop relay networks. Finally, [36] proposed to minimize the probability of outage through a joint power allocation and trajectory optimization problem.Few works have addressed the provision of VoIP service with drones. To the best of our knowledge, only our previous work [15, 16] has done it considering a single-layer of drones to set up a WiFi access network. In both papers, radio coverage and speech quality constrained the 3D multi-UAV placement optimization problem, seeking the minimum deployment costs (i.e., number of UAVs deployed). Between solutions with the same number of drones, we chose the one that minimized users’ radio energy or UAVs energy, respectively. However, both works addressed only the WiFi access network, leaving the distribution and backbone networks for future research. This paper takes a step further by considering a two-layered hierarchical network that performs access, distribution, and connection to the backbone using two different radio technologies: WiFi and 5G. Regarding the objective function, we propose to find the minimum number of deployed UAVs (independently of their type) needed to maximize user coverage. In light of Table 1, we can state that our work differs from those found in the literature in three main aspects: (a) a multilayered UAV placement that performs traffic aggregation, (b) more realistic constraints for real-time voice speech quality by modelling the MAC sublayer of the access network, and (c) the deployment of a WiFi access network instead of a cellular-based one, hence minimizing any compatibility issues regarding user smartphones.


## 3. Proposed Scenario and QoS Assessment

As shown in Figure1, our scenario consists of a two-level hierarchical network that relays between IEEE 802.11 (WiFi) networks (i.e., for access and distribution) and cellular 5G backhaul links. The QoS experienced by users will be influenced by packet loss and delay in these networks. This section is devoted to defining the network architecture and the analytical model used to estimate the speech quality experienced by users in our scenario.


### 3.1. Network Architecture

Figure2 illustrates the proposed network architecture. The network entities (from left to right) are as follows:
(i)
Ground users are equipped with WiFi-compliant terminals (e.g., smartphones) operating at the 2.4 GHz band associated to the Access Point installed at A-UAVs.(ii)
A-UAVs play a double role: (a) for users, they act as access points (at the 2.4 GHz band), and (b) they are associated with the distribution (second) layer of drones through another WiFi connection at 5 GHz.(iii)
D-UAVs behave as WiFi APs for associated A-UAVs, and they also provide a backbone link to the 5G network. As such, D-UAVs are seen as 5G User Equipment (UE) maintaining a connection to the 5G Core Network (i.e., GTP-U tunnels).Figure 2
Network reference architecture.In the previous architecture, the speech quality experienced by users is impaired on each subnetwork due to the medium access control mechanism and network congestion. The following section elaborates on the proposed QoS assessment method considered in this paper (E-Model).


### 3.2. Voice Quality Assessment

Voice quality assessment has been studied during the last decades [37]. Some of the approaches suggested in the literature to measure or estimate speech quality, such as P.863 or P.563, require invasive monitoring (e.g., sampling the original voice signal). On the contrary, the E-model [38] is an analytical model that allows one to estimate the speech quality assuming additive impairments to the quality. The E-model provides a quality score, namely, the R factor, that ranges from 0 (poor) to 100 (excellent) that is calculated as follows [15, 39, 40]:
(1)R=R0−Ie+95−IePplPpl/BurstR+Bpl⏟Ie,eff−0.024d+0.11·d−177.3·Hd−177.3⏟Id.In the previous equation, two impairments (Ie,eff and Id) are subtracted from the maximum achievable quality (R0), which is a representation of the Signal-to-Noise Ratio.Ie,eff represents a combination between impairment equipment parameter at zero packet loss (Ie) and a function that depends on Ie, the packet loss rate, and packet loss behavior. Ie is a codec-dependent constant associated with codec compression degradation (a list of values from ITU-T codecs were presented in ITU-T Rec. G.113 Appendix I), Bpl represents the codec packet loss robustness, which also has a specific value for each codec (listed in ITU-T Rec. G117 Appendix I), Ppl represents the packet loss rate (in %) in the WiFi channel, and finally, BurstR characterizes the burst ratio (i.e., equals 1 if the packet loss is random and greater otherwise). In this paper, we use the G.711 codec (Ie=0 and Bpl=25.1) and assume random losses (i.e., BurstR=1).The latest impairment,Id, is associated with the delay in the communication chain. A widely accepted approximation for Id can be obtained from one-way delay in the communication path d, where H is the Heaviside function (Hx=0 for x<0 and Hx=1 for x>0. In our case, x=d−177.3. The one-way delay d (in milliseconds) includes all additive delays from source to destination, which depend on the network topology and the chosen codec (i.e., packetization delay).In order to solve Equation (1), one has to model both network performance parameters (i.e., network delay d and the packet loss rate Ppl). Since our scenario consists of WiFi access and distribution networks and a backhaul 5G link, the overall delay and packet loss ratio should be
(2)Ppl=1−1−Ppl,a1−Ppl,d1−Ppl,b,(3)d=dp+da+dd+db,where (a), (d), and (b) subscripts refer to impairments at the access, distribution (i.e., influenced by IEEE 802.11 physical and MAC sublayer), and backhaul link, respectively. Finally dp accounts for the packetization delay, which could be assumed as a constant (e.g., 20 ms for G.711 codec).The previous performance metrics can be estimated for the IEEE 802.11 network through well-known analytical models (see [15, 16]) that enable the prediction of the packet loss ratio and delay in the WiFi network just by defining the number of stations, traffic models (i.e., packet size and frequency), and stations’ received signal strength. On the other hand, 5G links performance can be assumed to be included in the Service Level Agreement with the telco provider [41], so one can easily obtain Ppl,b and db.


## 3.1. Network Architecture

Figure2 illustrates the proposed network architecture. The network entities (from left to right) are as follows:
(i)
Ground users are equipped with WiFi-compliant terminals (e.g., smartphones) operating at the 2.4 GHz band associated to the Access Point installed at A-UAVs.(ii)
A-UAVs play a double role: (a) for users, they act as access points (at the 2.4 GHz band), and (b) they are associated with the distribution (second) layer of drones through another WiFi connection at 5 GHz.(iii)
D-UAVs behave as WiFi APs for associated A-UAVs, and they also provide a backbone link to the 5G network. As such, D-UAVs are seen as 5G User Equipment (UE) maintaining a connection to the 5G Core Network (i.e., GTP-U tunnels).Figure 2
Network reference architecture.In the previous architecture, the speech quality experienced by users is impaired on each subnetwork due to the medium access control mechanism and network congestion. The following section elaborates on the proposed QoS assessment method considered in this paper (E-Model).


## 3.2. Voice Quality Assessment

Voice quality assessment has been studied during the last decades [37]. Some of the approaches suggested in the literature to measure or estimate speech quality, such as P.863 or P.563, require invasive monitoring (e.g., sampling the original voice signal). On the contrary, the E-model [38] is an analytical model that allows one to estimate the speech quality assuming additive impairments to the quality. The E-model provides a quality score, namely, the R factor, that ranges from 0 (poor) to 100 (excellent) that is calculated as follows [15, 39, 40]:
(1)R=R0−Ie+95−IePplPpl/BurstR+Bpl⏟Ie,eff−0.024d+0.11·d−177.3·Hd−177.3⏟Id.In the previous equation, two impairments (Ie,eff and Id) are subtracted from the maximum achievable quality (R0), which is a representation of the Signal-to-Noise Ratio.Ie,eff represents a combination between impairment equipment parameter at zero packet loss (Ie) and a function that depends on Ie, the packet loss rate, and packet loss behavior. Ie is a codec-dependent constant associated with codec compression degradation (a list of values from ITU-T codecs were presented in ITU-T Rec. G.113 Appendix I), Bpl represents the codec packet loss robustness, which also has a specific value for each codec (listed in ITU-T Rec. G117 Appendix I), Ppl represents the packet loss rate (in %) in the WiFi channel, and finally, BurstR characterizes the burst ratio (i.e., equals 1 if the packet loss is random and greater otherwise). In this paper, we use the G.711 codec (Ie=0 and Bpl=25.1) and assume random losses (i.e., BurstR=1).The latest impairment,Id, is associated with the delay in the communication chain. A widely accepted approximation for Id can be obtained from one-way delay in the communication path d, where H is the Heaviside function (Hx=0 for x<0 and Hx=1 for x>0. In our case, x=d−177.3. The one-way delay d (in milliseconds) includes all additive delays from source to destination, which depend on the network topology and the chosen codec (i.e., packetization delay).In order to solve Equation (1), one has to model both network performance parameters (i.e., network delay d and the packet loss rate Ppl). Since our scenario consists of WiFi access and distribution networks and a backhaul 5G link, the overall delay and packet loss ratio should be
(2)Ppl=1−1−Ppl,a1−Ppl,d1−Ppl,b,(3)d=dp+da+dd+db,where (a), (d), and (b) subscripts refer to impairments at the access, distribution (i.e., influenced by IEEE 802.11 physical and MAC sublayer), and backhaul link, respectively. Finally dp accounts for the packetization delay, which could be assumed as a constant (e.g., 20 ms for G.711 codec).The previous performance metrics can be estimated for the IEEE 802.11 network through well-known analytical models (see [15, 16]) that enable the prediction of the packet loss ratio and delay in the WiFi network just by defining the number of stations, traffic models (i.e., packet size and frequency), and stations’ received signal strength. On the other hand, 5G links performance can be assumed to be included in the Service Level Agreement with the telco provider [41], so one can easily obtain Ppl,b and db.


## 4. Problem Definition

In this section, we state the terminology, main assumptions, and a formal definition of the problem of optimal placement under the scenario illustrated in Figures1 and 2.


### 4.1. Terminology

Table2 summarizes the notation used in this paper. We use three sets to represent distribution drones (D), access drones (A), and ground users (U). The location of each element in these sets is represented in Cartesian’s coordinates: d⟶, a⟶, and u⟶, respectively.Table 2
System terminology summary.
SymbolExampleDescriptionDd⟶1,d⟶2,⋯,d⟶DSet of D-UAVs’ locationsD∣D∣Number of deployed D-UAVsd⟶ixi,yi,ziCartesian coordinates of thei-th D-UAVAa⟶1,a⟶2,⋯,a⟶ASet of A-UAVs’ locationsA∣A∣Number of deployed A-UAVsa⟶jxj,yj,zjCartesian coordinates of thej-th A-UAVUu⟶1,u⟶2,⋯,u⟶USet of ground users’ locationsU∣U∣Number of ground usersu⟶kxk,yk,zkCartesian coordinates of thek-th userLet us introduce some functions that will be recurrently used in this paper:(i)
The coverage function,Cx⟶, represents the set of stations associated with a specific UAV-mounted AP identified by its location, e.g. x⟶. For example:
(a)
Cd⟶i represents the set of A-UAVs associated with the i-th D-UAV.(b)
Ca⟶j represents the set of users associated with the j-th A-UAV.(c)
C=∑i=1ACa⟶i represents the number of users covered by the system (and hence associated to any A-UAV).(ii)
The speech quality function,Rd⟶i,a⟶j, provides the speech quality experience by users associated with the j-th A-UAV (see Equation (3)) which in turn is associated with the i-th D-UAV. This function takes into account the level of congestion in the access and distribution networks(iii)
The uplink throughput function,Sd⟶i, provides the aggregated throughput (in Mb/s) handled by the i-th D-UAV. Clearly, it cannot exceed the maximum throughput achievable by the 5G link (Smax).


### 4.2. Assumptions

For the sake of tractability, the following assumptions are made:(i)
Ground users are confined in a flat outdoor terrain with known dimensions. Their position is also known (this could be implemented through users’ smartphone’s GPS or image processing).(ii)
Users’ calls go through a compatible VoIP application that uses a known audio codec.(iii)
APs’ channelization is arranged in such a manner that the interference between adjacent radio channels is negligible. By using directional antennas, one could simply adjust the radio beam pattern to minimize inter-UAV interference.(iv)
Ground users could potentially be simultaneously on a call. Thus, each A-UAV will not have more users associated than its VoIP Capacity [42] (maximum number of simultaneous calls under a guaranteed QoS). Then, VoIP Capacity is a harder constraint than coverage and will play a decisive role in determining the number of A-UAVs deployed.


### 4.3. Optimization Problem

The formal definition of our optimization problem is stated in(4)minD,AD+A+1−CUsubjecttoCU≥CminRd⟶i,a⟶j≥Rmin,∀d⟶i∈D,a⟶j∈Cd⟶i,Sd⟶i≤Smax,∀d⟶i∈D,d⟶i∈XD,∀d⟶i∈D,a⟶i∈XA,∀a⟶i∈A,D≤Dmax,A≤Amax,whereXD and XA stand for the collection of valid positions for distribution and access UAVs, respectively; so one could restrict flying zones or establish a range of valid altitudes for each type of UAV.The previous expression optimizes the location of Distribution and Access UAVs (D, A, respectively) that minimizes the total number of UAVs deployed (D+A) while maximizing user coverage (C/U) subject to the following constraints:
(i)
User coverage ratio,C/U, must exceed a threshold (Cmin).(ii)
Offered speech quality,Rd⟶i,a⟶j∀d⟶i∈D,a⟶j∈Cd⟶i, must be greater than a threshold (Rmin).(iii)
D-UAVs uplink throughput,Sd⟶i∀d⟶i∈D, must be lower than 5G links capacity (Smax).Observe that the analytical expression in Equation (4) is composed of two terms: (D+A) which is an integer (always ≥2 since we need to deploy at least one drone of each kind) and (1−C/U) which represent the rate of uncovered users. The latter is a real number always less than 1 (e.g., a coverage of 80% would provide 0.2) and, as such, is subordinated to the first (which is an integer). So minimizing the number of drones in the solution always takes precedence over coverage (which is already a problem constraint). Thus, the second term is only used to break the deadlock between various solutions with the same number of drones (the one with greater coverage is preferred).


## 4.1. Terminology

Table2 summarizes the notation used in this paper. We use three sets to represent distribution drones (D), access drones (A), and ground users (U). The location of each element in these sets is represented in Cartesian’s coordinates: d⟶, a⟶, and u⟶, respectively.Table 2
System terminology summary.
SymbolExampleDescriptionDd⟶1,d⟶2,⋯,d⟶DSet of D-UAVs’ locationsD∣D∣Number of deployed D-UAVsd⟶ixi,yi,ziCartesian coordinates of thei-th D-UAVAa⟶1,a⟶2,⋯,a⟶ASet of A-UAVs’ locationsA∣A∣Number of deployed A-UAVsa⟶jxj,yj,zjCartesian coordinates of thej-th A-UAVUu⟶1,u⟶2,⋯,u⟶USet of ground users’ locationsU∣U∣Number of ground usersu⟶kxk,yk,zkCartesian coordinates of thek-th userLet us introduce some functions that will be recurrently used in this paper:(i)
The coverage function,Cx⟶, represents the set of stations associated with a specific UAV-mounted AP identified by its location, e.g. x⟶. For example:
(a)
Cd⟶i represents the set of A-UAVs associated with the i-th D-UAV.(b)
Ca⟶j represents the set of users associated with the j-th A-UAV.(c)
C=∑i=1ACa⟶i represents the number of users covered by the system (and hence associated to any A-UAV).(ii)
The speech quality function,Rd⟶i,a⟶j, provides the speech quality experience by users associated with the j-th A-UAV (see Equation (3)) which in turn is associated with the i-th D-UAV. This function takes into account the level of congestion in the access and distribution networks(iii)
The uplink throughput function,Sd⟶i, provides the aggregated throughput (in Mb/s) handled by the i-th D-UAV. Clearly, it cannot exceed the maximum throughput achievable by the 5G link (Smax).


## 4.2. Assumptions

For the sake of tractability, the following assumptions are made:(i)
Ground users are confined in a flat outdoor terrain with known dimensions. Their position is also known (this could be implemented through users’ smartphone’s GPS or image processing).(ii)
Users’ calls go through a compatible VoIP application that uses a known audio codec.(iii)
APs’ channelization is arranged in such a manner that the interference between adjacent radio channels is negligible. By using directional antennas, one could simply adjust the radio beam pattern to minimize inter-UAV interference.(iv)
Ground users could potentially be simultaneously on a call. Thus, each A-UAV will not have more users associated than its VoIP Capacity [42] (maximum number of simultaneous calls under a guaranteed QoS). Then, VoIP Capacity is a harder constraint than coverage and will play a decisive role in determining the number of A-UAVs deployed.


## 4.3. Optimization Problem

The formal definition of our optimization problem is stated in(4)minD,AD+A+1−CUsubjecttoCU≥CminRd⟶i,a⟶j≥Rmin,∀d⟶i∈D,a⟶j∈Cd⟶i,Sd⟶i≤Smax,∀d⟶i∈D,d⟶i∈XD,∀d⟶i∈D,a⟶i∈XA,∀a⟶i∈A,D≤Dmax,A≤Amax,whereXD and XA stand for the collection of valid positions for distribution and access UAVs, respectively; so one could restrict flying zones or establish a range of valid altitudes for each type of UAV.The previous expression optimizes the location of Distribution and Access UAVs (D, A, respectively) that minimizes the total number of UAVs deployed (D+A) while maximizing user coverage (C/U) subject to the following constraints:
(i)
User coverage ratio,C/U, must exceed a threshold (Cmin).(ii)
Offered speech quality,Rd⟶i,a⟶j∀d⟶i∈D,a⟶j∈Cd⟶i, must be greater than a threshold (Rmin).(iii)
D-UAVs uplink throughput,Sd⟶i∀d⟶i∈D, must be lower than 5G links capacity (Smax).Observe that the analytical expression in Equation (4) is composed of two terms: (D+A) which is an integer (always ≥2 since we need to deploy at least one drone of each kind) and (1−C/U) which represent the rate of uncovered users. The latter is a real number always less than 1 (e.g., a coverage of 80% would provide 0.2) and, as such, is subordinated to the first (which is an integer). So minimizing the number of drones in the solution always takes precedence over coverage (which is already a problem constraint). Thus, the second term is only used to break the deadlock between various solutions with the same number of drones (the one with greater coverage is preferred).


## 5. Problem Resolution

The optimization problem in (4) can be solved through metaheuristics search algorithms. In our previous work [15, 16], we demonstrated the effectiveness of Genetic Algorithm and Particle Swarm Optimization, comparing their results with exhaustive search. For simplicity’s sake, and given our previous experience, we will use a PSO algorithm (further proposed by other authors [43]) in this paper.


### 5.1. Search Algorithm

Algorithm1 contains the pseudocode of the search algorithm used to solve the optimization problem in (4). The input of the algorithm is the set of valid positions for UAVs (X), the set of ground users’ location (U), and the problem constraints (Dmax, Cmin, Rmin, Smax). This algorithm looks for the optimal location of UAVs (D, A) that meets the problem constraint and increases the number of drones (A, and D) until a valid solution is found. For a given number of drones (D≤A), their positioning is jointly optimized by the SolveOptim_PSO function.Algorithm 1: Search algorithm pseudocode.
Input:X, U, Dmax, Cmin, Rmin, SmaxOutput:D, AInitialization:A=0, D=0whileA=A+1andA≤AmaxdoD=0;whileD=D+1andD≤A≤DmaxdoD, A = SolveOptim_PSO U,D,AifD≠∅andA≠∅thenreturnD, Aendendendreturn∅On each iteration, the SolveOptim_PSO (see Algorithm2) is called to find the optimal location (D∗, A∗) for the specified number of UAVs (i.e., D and A input parameters), returning an empty set if the problem constraints cannot be met. During execution, candidate locations (i.e., particles) are randomly created (CreateParticles), evolved (UpdateParticle), and evaluated (Check) following a common Particle Swarm Optimization approach:
(i)
The CreateParticles function returns a set of particles randomly generated,P, by considering the collection of valid positions (X) and the number of Distribution and Access UAVs, D and A, respectively. Each element in P represents a candidate set of locations for all UAVs, so they can be decomposed into the D and A sets(ii)
The UpdateParticle function updates the set of particles (P) by considering the best-found location for each particle (P∗)(iii)
The Check function contains the fitness evaluation that returns a score for a given location. Then, the algorithm evaluates if the candidate position is valid (fi>0), and if it improves the best-found location for that particle (fi<fi∗). If so, the best-found location for that particle is updated(iv)
The algorithm finishes when the exit criterion is achieved (e.g., the overall improvement between two consecutive generations is lower than10−3). It returns the location for Distribution and Access UAVs (D∗ and A∗) if any, or an empty set otherwiseAlgorithm 2: Particle Swarm Optimization function
(SolveOptim_PSO)Input:X, U, D, A, Cmin, Rmin, SmaxOutput:D∗, A∗Initialization:D∗=∅, A∗=∅P = CreateParticles X,D,AP∗ = Pwhile !(exit criteria met) dofor particle i=1to∣P∣doPi = UpdateParticle X,Pi,Pi∗;Di,Ai = Pi;/∗ Evaluate the i-th particle        ∗/fi = Check (U, Di, Ai)if (fi>0andfi<fi∗) then/∗ Update if better          ∗/Pi∗=Pi;fi∗=fi;iffi<minfthen/∗ Update if best         ∗/D∗,A∗=PiendendendendreturnD∗, A∗The next section elaborates on the fitness evaluation procedure (Check function); the reader can find rest of the PSO-related functions in our previous work [16], along with some implementation details.


### 5.2. Fitness Evaluation (Check Function)

For every candidate solution (i.e.,D, A), a fitness score has to be calculated based on the optimization problem. Let us define the score of a particle (i.e., candidate solution) as f:
(5)f=D+A+1−CU,ifconstraintsaresatisfied,−CU,otherwise,where constraints refers to coverage, quality of service, and throughput evaluation.


#### 5.2.1. Coverage Evaluation

Checks if the total number of covered users (C) is greater than the threshold (Cmin). It uses the coverage function, Cx⟶i, that returns a set of locations of associated Stations for an Access Point located at x⟶i (i.e., in Cartesian coordinates).This function can be applied to any AP in the system (i.e., both D-UAVs and A-UAVs). For example, (6) represents the coverage function for the i-th D-UAV (d⟶i), but it can be adapted for any A-UAV just by replacing d⟶ and a⟶ with a⟶ and u⟶, respectively.
(6)Cd⟶i=α⟶k∈ARSSId⟶i,α⟶k≥RSSIminSINRd⟶i,α⟶k≥SINRminRSSId⟶i,α⟶k>RSSId⟶i,α⟶j∀α⟶k≠α⟶jThe previous expression returns the subset of stations that (a) are compliant with RSSI and SINR minimum thresholds and (b) have the greatest signal intensity. Then, RSSI and SINR can be calculated as follows.(i)
The Received Signal Strength Indicator (RSSI) depends on the distance and angle between the transmitter and the receptor. Equation (7) represents the RSSI calculus (in dBm). In this expression, an initial transmission power is considered (Ptx), further adding power gains (G) and subtracting any losses (L).(7)RSSIx⟶,y⟶=Ptx+Gθx,y−L∥x⟶−y⟶∥,θx,y,(8)Gθ=10log1010Gmax/20·cos2θ,(9)Ld,θ=PLoSθLLoSd+PNLoSθLNLoSd,where 8 represent a simple gain pattern of an antenna (limited byGmax) and L represents a path loss expression widely proposed in air-to-ground channel models [44–46]. It considers that ground users receive three different groups of signals: (a) Line-of-Sight (LoS), (b) Non-Line-of-Sight (NLoS), and (c) other reflected components which cause multipath fading. Each group has its own probability of occurrence depending on the environment, density, height, and elevation angle. According to [47], the probability of fading is significantly lower than the probability of receiving the LoS (PLoS) and NLoS (PNLoS) components, so we will neglect it for simplicity. LLoS and LNLoS represent the average path loss for LoS and NLoS components, respectively, and can be expressed as [44]
(10)LLoSd=20log104πfcdc+ξLoS,(11)LNLoSd=20log104πfcdc+ξNLoS,where the first term accounts for the free space propagation lossξLoS and ξNLoS represent any additional losses due to the environment (a list of values can be found in [45]) and fc is the channel frequency.Finally, the probability of receiving each component is given by [48]
(12)PLoSθ=11+αe−βθ·180/π+βα,(13)PNLoSθ=1−PLoSθ,whereα and β are environment-dependent constants (e.g., rural and urban) as defined in [45] (e.g., α=β=0 for no buildings).
(i)
The Signal-to-Interference-plus-Noise-Ratio (SINR) can be calculated by subtracting every noise and cochannel interference from the received signal strength. LetZ be the collection of APs operating at an overlapping channel (channel planning is out of the scope of this paper). Then, SINR can be expressed as(14)SINR=PrxN+∑k∈ZIk,wherePrx represents the received signal power, N accounts for the noise, and each Ik∀k∈Z stands for the received interference from any overlapping transmissions. Since we assume that the sources of interference are negligible due to a correct channel planning, SINR can be reduced to SNR and it can be calculated as
(15)SINRdBx⟶,y⟶=RSSIx⟶,y⟶−F−NdB,(16)NdB=−174+10log10CBW,whereN is the noise, F accounts for the receiver’s noise figure, and CBW stands for the signal bandwidth, which depends on the IEEE 802.11 standard revision under consideration.


#### 5.2.2. Speech Quality and Throughput Evaluation

The goal of this evaluation is to guarantee that (a) the speech quality, given by the QoS functionRd⟶i,a⟶j for every D-UAV–A-UAV association in the system, is over a minimum threshold (Rmin) and (b) that the aggregated throughput at D-UAVs do not exceed the maximum capacity of 5G links (Smax). Both constraints can be formally represented as (17) and (18), respectively.
(17)Rd⟶i,a⟶j≥Rmin,∀d⟶i∈D,∀a⟶j∈Cd⟶i,(18)Sd⟶i≤Smax,∀d⟶i∈D.To verify these constraints, one has to estimate end-to-end performance parameters such as packet loss ratio, delay, and effective throughput. Then, as introduced in Section3.2, the end-to-end speech quality (e.g., see R factor in (1)) can be estimated through the E-model. This requires to know the end-to-end packet loss ratio (Ppl) and delay (d). Moreover, Ppl and d can be further decomposed (see Equations (2) and (3)) considering the three networks traversed in the proposed network architecture: (a) the WiFi access network, (b) the WiFi distribution network, and (c) the 5G link SLA. Notice that the delay and loss in the 5G link can be agreed with the service provider (i.e., the telco operator) and hence can be seen as constant values. However, the first two (WiFi networks) have to be estimated.To derive the VoIP Capacity of any AP in our system, we extend Bianchi’s Markov-chain analytical model [49] of the IEEE 802.11 MAC sublayer performance. Our analytical model takes the location of the access point (e.g., a⟶) and its associated stations (Ca⟶) as input parameters and returns a τ expression for each contending station as its probability of transmission attempt. The output of our analytical model can be used to derive the estimated delay, packet loss ratio, and aggregated throughput at a given AP as follows:
(19)LWiFia⟶=1−1−FERa⟶τa⟶∏u⟶∈Ca⟶1−τu⟶Ca⟶·λ·ET,(20)DWiFia⟶=EBa⟶·ET,(21)SWiFia⟶=∑u⟶∈Ca⟶1−FERu⟶τu⟶∏i⟶≠u⟶∈S1−τi⟶ET·LPDU,whereFERa⟶ stands for the average Frame Error Rate at the access point, which can be derived from its SINR and Modulation and Coding Scheme (MCS); EB is the expected number of back-off slots that a packet waits before transmission; and ET is the average slot duration and it can be calculated by averaging the duration of each type of event (e.g., transmission, collision) with its probability. The reader is encouraged to read a more detailed derivation of all these parameters in our previous works [15, 16, 40]. Finally, λ and LPDU represent the number of packets transmitted per second and their payload length, respectively (e.g., 50 packets/second and 160 Bytes for G.711 codec).Finally, (2) and (3) can be completed as
(22)Ppl=1−1−LWiFid⟶i1−LWiFia⟶j1−L5G−SLA,(23)d=20ms+DWiFid⟶i+DWiFia⟶j+d5G−SLA,where 20 ms accounts for the packetization interval for the G.711 codec. Once computed,Ppl and d can be further substituted in (1) to obtain R.


#### 5.2.3. Computational Complexity

In terms of computational complexity, the most demanding procedure in our heuristic search is the fitness evaluation (Check function). If we assume thatD is upper bounded by A and that the maximum number of calls to the Check function is upper bounded in our heuristics, the computational complexity of the SolveOptim_PSO function can be expressed as OA·U; hence, the computational complexity of Algorithm 5.1 can be expressed as OD·A2·U.


## 5.1. Search Algorithm

Algorithm1 contains the pseudocode of the search algorithm used to solve the optimization problem in (4). The input of the algorithm is the set of valid positions for UAVs (X), the set of ground users’ location (U), and the problem constraints (Dmax, Cmin, Rmin, Smax). This algorithm looks for the optimal location of UAVs (D, A) that meets the problem constraint and increases the number of drones (A, and D) until a valid solution is found. For a given number of drones (D≤A), their positioning is jointly optimized by the SolveOptim_PSO function.Algorithm 1: Search algorithm pseudocode.
Input:X, U, Dmax, Cmin, Rmin, SmaxOutput:D, AInitialization:A=0, D=0whileA=A+1andA≤AmaxdoD=0;whileD=D+1andD≤A≤DmaxdoD, A = SolveOptim_PSO U,D,AifD≠∅andA≠∅thenreturnD, Aendendendreturn∅On each iteration, the SolveOptim_PSO (see Algorithm2) is called to find the optimal location (D∗, A∗) for the specified number of UAVs (i.e., D and A input parameters), returning an empty set if the problem constraints cannot be met. During execution, candidate locations (i.e., particles) are randomly created (CreateParticles), evolved (UpdateParticle), and evaluated (Check) following a common Particle Swarm Optimization approach:
(i)
The CreateParticles function returns a set of particles randomly generated,P, by considering the collection of valid positions (X) and the number of Distribution and Access UAVs, D and A, respectively. Each element in P represents a candidate set of locations for all UAVs, so they can be decomposed into the D and A sets(ii)
The UpdateParticle function updates the set of particles (P) by considering the best-found location for each particle (P∗)(iii)
The Check function contains the fitness evaluation that returns a score for a given location. Then, the algorithm evaluates if the candidate position is valid (fi>0), and if it improves the best-found location for that particle (fi<fi∗). If so, the best-found location for that particle is updated(iv)
The algorithm finishes when the exit criterion is achieved (e.g., the overall improvement between two consecutive generations is lower than10−3). It returns the location for Distribution and Access UAVs (D∗ and A∗) if any, or an empty set otherwiseAlgorithm 2: Particle Swarm Optimization function
(SolveOptim_PSO)Input:X, U, D, A, Cmin, Rmin, SmaxOutput:D∗, A∗Initialization:D∗=∅, A∗=∅P = CreateParticles X,D,AP∗ = Pwhile !(exit criteria met) dofor particle i=1to∣P∣doPi = UpdateParticle X,Pi,Pi∗;Di,Ai = Pi;/∗ Evaluate the i-th particle        ∗/fi = Check (U, Di, Ai)if (fi>0andfi<fi∗) then/∗ Update if better          ∗/Pi∗=Pi;fi∗=fi;iffi<minfthen/∗ Update if best         ∗/D∗,A∗=PiendendendendreturnD∗, A∗The next section elaborates on the fitness evaluation procedure (Check function); the reader can find rest of the PSO-related functions in our previous work [16], along with some implementation details.


## 5.2. Fitness Evaluation (Check Function)

For every candidate solution (i.e.,D, A), a fitness score has to be calculated based on the optimization problem. Let us define the score of a particle (i.e., candidate solution) as f:
(5)f=D+A+1−CU,ifconstraintsaresatisfied,−CU,otherwise,where constraints refers to coverage, quality of service, and throughput evaluation.


### 5.2.1. Coverage Evaluation

Checks if the total number of covered users (C) is greater than the threshold (Cmin). It uses the coverage function, Cx⟶i, that returns a set of locations of associated Stations for an Access Point located at x⟶i (i.e., in Cartesian coordinates).This function can be applied to any AP in the system (i.e., both D-UAVs and A-UAVs). For example, (6) represents the coverage function for the i-th D-UAV (d⟶i), but it can be adapted for any A-UAV just by replacing d⟶ and a⟶ with a⟶ and u⟶, respectively.
(6)Cd⟶i=α⟶k∈ARSSId⟶i,α⟶k≥RSSIminSINRd⟶i,α⟶k≥SINRminRSSId⟶i,α⟶k>RSSId⟶i,α⟶j∀α⟶k≠α⟶jThe previous expression returns the subset of stations that (a) are compliant with RSSI and SINR minimum thresholds and (b) have the greatest signal intensity. Then, RSSI and SINR can be calculated as follows.(i)
The Received Signal Strength Indicator (RSSI) depends on the distance and angle between the transmitter and the receptor. Equation (7) represents the RSSI calculus (in dBm). In this expression, an initial transmission power is considered (Ptx), further adding power gains (G) and subtracting any losses (L).(7)RSSIx⟶,y⟶=Ptx+Gθx,y−L∥x⟶−y⟶∥,θx,y,(8)Gθ=10log1010Gmax/20·cos2θ,(9)Ld,θ=PLoSθLLoSd+PNLoSθLNLoSd,where 8 represent a simple gain pattern of an antenna (limited byGmax) and L represents a path loss expression widely proposed in air-to-ground channel models [44–46]. It considers that ground users receive three different groups of signals: (a) Line-of-Sight (LoS), (b) Non-Line-of-Sight (NLoS), and (c) other reflected components which cause multipath fading. Each group has its own probability of occurrence depending on the environment, density, height, and elevation angle. According to [47], the probability of fading is significantly lower than the probability of receiving the LoS (PLoS) and NLoS (PNLoS) components, so we will neglect it for simplicity. LLoS and LNLoS represent the average path loss for LoS and NLoS components, respectively, and can be expressed as [44]
(10)LLoSd=20log104πfcdc+ξLoS,(11)LNLoSd=20log104πfcdc+ξNLoS,where the first term accounts for the free space propagation lossξLoS and ξNLoS represent any additional losses due to the environment (a list of values can be found in [45]) and fc is the channel frequency.Finally, the probability of receiving each component is given by [48]
(12)PLoSθ=11+αe−βθ·180/π+βα,(13)PNLoSθ=1−PLoSθ,whereα and β are environment-dependent constants (e.g., rural and urban) as defined in [45] (e.g., α=β=0 for no buildings).
(i)
The Signal-to-Interference-plus-Noise-Ratio (SINR) can be calculated by subtracting every noise and cochannel interference from the received signal strength. LetZ be the collection of APs operating at an overlapping channel (channel planning is out of the scope of this paper). Then, SINR can be expressed as(14)SINR=PrxN+∑k∈ZIk,wherePrx represents the received signal power, N accounts for the noise, and each Ik∀k∈Z stands for the received interference from any overlapping transmissions. Since we assume that the sources of interference are negligible due to a correct channel planning, SINR can be reduced to SNR and it can be calculated as
(15)SINRdBx⟶,y⟶=RSSIx⟶,y⟶−F−NdB,(16)NdB=−174+10log10CBW,whereN is the noise, F accounts for the receiver’s noise figure, and CBW stands for the signal bandwidth, which depends on the IEEE 802.11 standard revision under consideration.


### 5.2.2. Speech Quality and Throughput Evaluation

The goal of this evaluation is to guarantee that (a) the speech quality, given by the QoS functionRd⟶i,a⟶j for every D-UAV–A-UAV association in the system, is over a minimum threshold (Rmin) and (b) that the aggregated throughput at D-UAVs do not exceed the maximum capacity of 5G links (Smax). Both constraints can be formally represented as (17) and (18), respectively.
(17)Rd⟶i,a⟶j≥Rmin,∀d⟶i∈D,∀a⟶j∈Cd⟶i,(18)Sd⟶i≤Smax,∀d⟶i∈D.To verify these constraints, one has to estimate end-to-end performance parameters such as packet loss ratio, delay, and effective throughput. Then, as introduced in Section3.2, the end-to-end speech quality (e.g., see R factor in (1)) can be estimated through the E-model. This requires to know the end-to-end packet loss ratio (Ppl) and delay (d). Moreover, Ppl and d can be further decomposed (see Equations (2) and (3)) considering the three networks traversed in the proposed network architecture: (a) the WiFi access network, (b) the WiFi distribution network, and (c) the 5G link SLA. Notice that the delay and loss in the 5G link can be agreed with the service provider (i.e., the telco operator) and hence can be seen as constant values. However, the first two (WiFi networks) have to be estimated.To derive the VoIP Capacity of any AP in our system, we extend Bianchi’s Markov-chain analytical model [49] of the IEEE 802.11 MAC sublayer performance. Our analytical model takes the location of the access point (e.g., a⟶) and its associated stations (Ca⟶) as input parameters and returns a τ expression for each contending station as its probability of transmission attempt. The output of our analytical model can be used to derive the estimated delay, packet loss ratio, and aggregated throughput at a given AP as follows:
(19)LWiFia⟶=1−1−FERa⟶τa⟶∏u⟶∈Ca⟶1−τu⟶Ca⟶·λ·ET,(20)DWiFia⟶=EBa⟶·ET,(21)SWiFia⟶=∑u⟶∈Ca⟶1−FERu⟶τu⟶∏i⟶≠u⟶∈S1−τi⟶ET·LPDU,whereFERa⟶ stands for the average Frame Error Rate at the access point, which can be derived from its SINR and Modulation and Coding Scheme (MCS); EB is the expected number of back-off slots that a packet waits before transmission; and ET is the average slot duration and it can be calculated by averaging the duration of each type of event (e.g., transmission, collision) with its probability. The reader is encouraged to read a more detailed derivation of all these parameters in our previous works [15, 16, 40]. Finally, λ and LPDU represent the number of packets transmitted per second and their payload length, respectively (e.g., 50 packets/second and 160 Bytes for G.711 codec).Finally, (2) and (3) can be completed as
(22)Ppl=1−1−LWiFid⟶i1−LWiFia⟶j1−L5G−SLA,(23)d=20ms+DWiFid⟶i+DWiFia⟶j+d5G−SLA,where 20 ms accounts for the packetization interval for the G.711 codec. Once computed,Ppl and d can be further substituted in (1) to obtain R.


### 5.2.3. Computational Complexity

In terms of computational complexity, the most demanding procedure in our heuristic search is the fitness evaluation (Check function). If we assume thatD is upper bounded by A and that the maximum number of calls to the Check function is upper bounded in our heuristics, the computational complexity of the SolveOptim_PSO function can be expressed as OA·U; hence, the computational complexity of Algorithm 5.1 can be expressed as OD·A2·U.


## 5.2.1. Coverage Evaluation

Checks if the total number of covered users (C) is greater than the threshold (Cmin). It uses the coverage function, Cx⟶i, that returns a set of locations of associated Stations for an Access Point located at x⟶i (i.e., in Cartesian coordinates).This function can be applied to any AP in the system (i.e., both D-UAVs and A-UAVs). For example, (6) represents the coverage function for the i-th D-UAV (d⟶i), but it can be adapted for any A-UAV just by replacing d⟶ and a⟶ with a⟶ and u⟶, respectively.
(6)Cd⟶i=α⟶k∈ARSSId⟶i,α⟶k≥RSSIminSINRd⟶i,α⟶k≥SINRminRSSId⟶i,α⟶k>RSSId⟶i,α⟶j∀α⟶k≠α⟶jThe previous expression returns the subset of stations that (a) are compliant with RSSI and SINR minimum thresholds and (b) have the greatest signal intensity. Then, RSSI and SINR can be calculated as follows.(i)
The Received Signal Strength Indicator (RSSI) depends on the distance and angle between the transmitter and the receptor. Equation (7) represents the RSSI calculus (in dBm). In this expression, an initial transmission power is considered (Ptx), further adding power gains (G) and subtracting any losses (L).(7)RSSIx⟶,y⟶=Ptx+Gθx,y−L∥x⟶−y⟶∥,θx,y,(8)Gθ=10log1010Gmax/20·cos2θ,(9)Ld,θ=PLoSθLLoSd+PNLoSθLNLoSd,where 8 represent a simple gain pattern of an antenna (limited byGmax) and L represents a path loss expression widely proposed in air-to-ground channel models [44–46]. It considers that ground users receive three different groups of signals: (a) Line-of-Sight (LoS), (b) Non-Line-of-Sight (NLoS), and (c) other reflected components which cause multipath fading. Each group has its own probability of occurrence depending on the environment, density, height, and elevation angle. According to [47], the probability of fading is significantly lower than the probability of receiving the LoS (PLoS) and NLoS (PNLoS) components, so we will neglect it for simplicity. LLoS and LNLoS represent the average path loss for LoS and NLoS components, respectively, and can be expressed as [44]
(10)LLoSd=20log104πfcdc+ξLoS,(11)LNLoSd=20log104πfcdc+ξNLoS,where the first term accounts for the free space propagation lossξLoS and ξNLoS represent any additional losses due to the environment (a list of values can be found in [45]) and fc is the channel frequency.Finally, the probability of receiving each component is given by [48]
(12)PLoSθ=11+αe−βθ·180/π+βα,(13)PNLoSθ=1−PLoSθ,whereα and β are environment-dependent constants (e.g., rural and urban) as defined in [45] (e.g., α=β=0 for no buildings).
(i)
The Signal-to-Interference-plus-Noise-Ratio (SINR) can be calculated by subtracting every noise and cochannel interference from the received signal strength. LetZ be the collection of APs operating at an overlapping channel (channel planning is out of the scope of this paper). Then, SINR can be expressed as(14)SINR=PrxN+∑k∈ZIk,wherePrx represents the received signal power, N accounts for the noise, and each Ik∀k∈Z stands for the received interference from any overlapping transmissions. Since we assume that the sources of interference are negligible due to a correct channel planning, SINR can be reduced to SNR and it can be calculated as
(15)SINRdBx⟶,y⟶=RSSIx⟶,y⟶−F−NdB,(16)NdB=−174+10log10CBW,whereN is the noise, F accounts for the receiver’s noise figure, and CBW stands for the signal bandwidth, which depends on the IEEE 802.11 standard revision under consideration.


## 5.2.2. Speech Quality and Throughput Evaluation

The goal of this evaluation is to guarantee that (a) the speech quality, given by the QoS functionRd⟶i,a⟶j for every D-UAV–A-UAV association in the system, is over a minimum threshold (Rmin) and (b) that the aggregated throughput at D-UAVs do not exceed the maximum capacity of 5G links (Smax). Both constraints can be formally represented as (17) and (18), respectively.
(17)Rd⟶i,a⟶j≥Rmin,∀d⟶i∈D,∀a⟶j∈Cd⟶i,(18)Sd⟶i≤Smax,∀d⟶i∈D.To verify these constraints, one has to estimate end-to-end performance parameters such as packet loss ratio, delay, and effective throughput. Then, as introduced in Section3.2, the end-to-end speech quality (e.g., see R factor in (1)) can be estimated through the E-model. This requires to know the end-to-end packet loss ratio (Ppl) and delay (d). Moreover, Ppl and d can be further decomposed (see Equations (2) and (3)) considering the three networks traversed in the proposed network architecture: (a) the WiFi access network, (b) the WiFi distribution network, and (c) the 5G link SLA. Notice that the delay and loss in the 5G link can be agreed with the service provider (i.e., the telco operator) and hence can be seen as constant values. However, the first two (WiFi networks) have to be estimated.To derive the VoIP Capacity of any AP in our system, we extend Bianchi’s Markov-chain analytical model [49] of the IEEE 802.11 MAC sublayer performance. Our analytical model takes the location of the access point (e.g., a⟶) and its associated stations (Ca⟶) as input parameters and returns a τ expression for each contending station as its probability of transmission attempt. The output of our analytical model can be used to derive the estimated delay, packet loss ratio, and aggregated throughput at a given AP as follows:
(19)LWiFia⟶=1−1−FERa⟶τa⟶∏u⟶∈Ca⟶1−τu⟶Ca⟶·λ·ET,(20)DWiFia⟶=EBa⟶·ET,(21)SWiFia⟶=∑u⟶∈Ca⟶1−FERu⟶τu⟶∏i⟶≠u⟶∈S1−τi⟶ET·LPDU,whereFERa⟶ stands for the average Frame Error Rate at the access point, which can be derived from its SINR and Modulation and Coding Scheme (MCS); EB is the expected number of back-off slots that a packet waits before transmission; and ET is the average slot duration and it can be calculated by averaging the duration of each type of event (e.g., transmission, collision) with its probability. The reader is encouraged to read a more detailed derivation of all these parameters in our previous works [15, 16, 40]. Finally, λ and LPDU represent the number of packets transmitted per second and their payload length, respectively (e.g., 50 packets/second and 160 Bytes for G.711 codec).Finally, (2) and (3) can be completed as
(22)Ppl=1−1−LWiFid⟶i1−LWiFia⟶j1−L5G−SLA,(23)d=20ms+DWiFid⟶i+DWiFia⟶j+d5G−SLA,where 20 ms accounts for the packetization interval for the G.711 codec. Once computed,Ppl and d can be further substituted in (1) to obtain R.


## 5.2.3. Computational Complexity

In terms of computational complexity, the most demanding procedure in our heuristic search is the fitness evaluation (Check function). If we assume thatD is upper bounded by A and that the maximum number of calls to the Check function is upper bounded in our heuristics, the computational complexity of the SolveOptim_PSO function can be expressed as OA·U; hence, the computational complexity of Algorithm 5.1 can be expressed as OD·A2·U.


## 6. Results

We have used our PSO-based search algorithm to find optimal solutions in different scenarios. This section begins with a100m×100m scenario and 60 ground users for illustrative purposes. Then, we explore other scenarios changing the terrain size (from 25m×25m to 100m×100m) and the number of users (from 10 to 100).


### 6.1. Example Solution

This section provides a first example solution in a100m×100m terrain with 60 ground users randomly placed. The rest of the parameters used are listed in Table 3. Such settings are common to all experiments in this section unless otherwise specified.Table 3
Input parameters.
ParameterValueUsers60Size100m×100mVoIP codecG.711 (20 ms interval)D-UAVs’ WiFi802.11ac at 5 GHz (80 MHz)A-UAVs’ WiFi802.11n at 2.4 GHz (20 MHz)D-UAVs’ altitude10,35 mA-UAVs’ altitude40,55 mRSSImin−82 dBmSNRmin20 dBRmin65Cmin90%L5G−SLA1%d5G−SLA5 msSmax1 Gb/sThe PSO-based search algorithm in Algorithm2 has been implemented in Matlab 2020a, providing the results shown in Figure 3. In this scenario, four A-UAVs and two D-UAVs are required to cover 58 of the 60 ground users while guaranteeing a minimal speech quality of 65 (R factor).Figure 3
Example solution.In Figure3, ground users are represented with circles filled with color (if covered) or not (if uncovered). Each ground user is associated with an A-UAV of the same color whose location has been derived from the algorithm. Finally, each A-UAV is associated with a D-UAV in a similar manner. As such, colors represent the final association between different layers. According to Figure 3, two 5G links would suffice to serve the 58 ground users under coverage.


### 6.2. Numerical Analysis

In this section, we examine the solutions found in several scenarios. In particular, the number of ground users has been increased from 10 to 100 (in steps of 10) in four square terrain sizes (25m×25m, 50m×50m, 75m×75m, and 100m×100m). Each experiment (i.e., scenario) has been repeated 30 times to obtain a 95% confidence interval by randomly placing ground users uniformly along the terrain. Finally, Figure 4 illustrates the average value of the results obtained with the corresponding confidence interval.Figure 4
Numerical results.
(a)
Number of deployed D-UAVs(b)
Number of deployed A-UAVs(c)
Speech quality(d)
Percentage of covered users(e)
Average RSSI at ground users(f)
Average area covered by A-UAVsFigures4(a) and 4(b) show the optimal number of D-UAVs and A-UAVs, respectively, for different numbers of users (U) and terrain sizes. At first sight, it can be observed that the overall number of UAVs tends to grow when either the terrain size or the number of users increases.If we take a closer look into the50m×50m series, the number of A-UAVs experiences a steep growth after 20 users. This effect is due to network congestion, so more UAVs are required to satisfy the speech quality constraints. This behavior is reaffirmed in Figure 4(c), which represents the speech quality, and shows that speech quality degrades when more users are added to the system. Indeed, after 70 users, more D-UAVs are required to aggregate the traffic from the access network so that QoS is not negatively affected. In our results, it is likely that each D-UAV associates with up to three A-UAV hence reducing the number of 5G links required to provide the service. Although this behavior is similar various terrain sizes, the final number of UAVs changes with user sparsity (m2/U); if the terrain is increased with the same number of ground users, UAVs have to cover a larger area to satisfy coverage constraints (C/U≥Cmin); hence, the number of drones is driven by the signal coverage constraint instead of the speech quality constraint.Figure4(d) shows the percentage of users covered in each scenario. Our results suggest that larger areas tend to provide lower ratios of user coverage due to a greater distance between users and A-UAVs. This, in turn, penalizes the path loss. Figure 4(e) represents the average received signal strength (RSSI) for each series of experiments. As illustrated, the RSSI increases with the number of ground users. This is attributable to the fact that requiring more A-UAVs to meet the speech quality requirements (e.g., reduce congestion) also produces UAVs located closer to users, hence increasing RSSI values. As a consequence, the effective area covered by each A-UAV is reduced (see Figure 4(f)).


### 6.3. Computational Performance

The previous series of experiments have also been analyzed in light of computational performance. To this end, we measured the average time spent during the execution of the algorithm. Figure5 illustrates the execution time in seconds for the same series of experiments in an Intel Core™ i5-4460 processor with 8GB of RAM.Figure 5
Performance analysis.The results shown in Figure5 suggest that the execution time increases with user density (U/m2) for a given terrain size, so more dense scenarios require more CPU time. However, the execution time is almost linear when solving low user-density scenarios (e.g., 100m×100m). In all cases, the results were obtained in less than 100 seconds.


## 6.1. Example Solution

This section provides a first example solution in a100m×100m terrain with 60 ground users randomly placed. The rest of the parameters used are listed in Table 3. Such settings are common to all experiments in this section unless otherwise specified.Table 3
Input parameters.
ParameterValueUsers60Size100m×100mVoIP codecG.711 (20 ms interval)D-UAVs’ WiFi802.11ac at 5 GHz (80 MHz)A-UAVs’ WiFi802.11n at 2.4 GHz (20 MHz)D-UAVs’ altitude10,35 mA-UAVs’ altitude40,55 mRSSImin−82 dBmSNRmin20 dBRmin65Cmin90%L5G−SLA1%d5G−SLA5 msSmax1 Gb/sThe PSO-based search algorithm in Algorithm2 has been implemented in Matlab 2020a, providing the results shown in Figure 3. In this scenario, four A-UAVs and two D-UAVs are required to cover 58 of the 60 ground users while guaranteeing a minimal speech quality of 65 (R factor).Figure 3
Example solution.In Figure3, ground users are represented with circles filled with color (if covered) or not (if uncovered). Each ground user is associated with an A-UAV of the same color whose location has been derived from the algorithm. Finally, each A-UAV is associated with a D-UAV in a similar manner. As such, colors represent the final association between different layers. According to Figure 3, two 5G links would suffice to serve the 58 ground users under coverage.


## 6.2. Numerical Analysis

In this section, we examine the solutions found in several scenarios. In particular, the number of ground users has been increased from 10 to 100 (in steps of 10) in four square terrain sizes (25m×25m, 50m×50m, 75m×75m, and 100m×100m). Each experiment (i.e., scenario) has been repeated 30 times to obtain a 95% confidence interval by randomly placing ground users uniformly along the terrain. Finally, Figure 4 illustrates the average value of the results obtained with the corresponding confidence interval.Figure 4
Numerical results.
(a)
Number of deployed D-UAVs(b)
Number of deployed A-UAVs(c)
Speech quality(d)
Percentage of covered users(e)
Average RSSI at ground users(f)
Average area covered by A-UAVsFigures4(a) and 4(b) show the optimal number of D-UAVs and A-UAVs, respectively, for different numbers of users (U) and terrain sizes. At first sight, it can be observed that the overall number of UAVs tends to grow when either the terrain size or the number of users increases.If we take a closer look into the50m×50m series, the number of A-UAVs experiences a steep growth after 20 users. This effect is due to network congestion, so more UAVs are required to satisfy the speech quality constraints. This behavior is reaffirmed in Figure 4(c), which represents the speech quality, and shows that speech quality degrades when more users are added to the system. Indeed, after 70 users, more D-UAVs are required to aggregate the traffic from the access network so that QoS is not negatively affected. In our results, it is likely that each D-UAV associates with up to three A-UAV hence reducing the number of 5G links required to provide the service. Although this behavior is similar various terrain sizes, the final number of UAVs changes with user sparsity (m2/U); if the terrain is increased with the same number of ground users, UAVs have to cover a larger area to satisfy coverage constraints (C/U≥Cmin); hence, the number of drones is driven by the signal coverage constraint instead of the speech quality constraint.Figure4(d) shows the percentage of users covered in each scenario. Our results suggest that larger areas tend to provide lower ratios of user coverage due to a greater distance between users and A-UAVs. This, in turn, penalizes the path loss. Figure 4(e) represents the average received signal strength (RSSI) for each series of experiments. As illustrated, the RSSI increases with the number of ground users. This is attributable to the fact that requiring more A-UAVs to meet the speech quality requirements (e.g., reduce congestion) also produces UAVs located closer to users, hence increasing RSSI values. As a consequence, the effective area covered by each A-UAV is reduced (see Figure 4(f)).


## 6.3. Computational Performance

The previous series of experiments have also been analyzed in light of computational performance. To this end, we measured the average time spent during the execution of the algorithm. Figure5 illustrates the execution time in seconds for the same series of experiments in an Intel Core™ i5-4460 processor with 8GB of RAM.Figure 5
Performance analysis.The results shown in Figure5 suggest that the execution time increases with user density (U/m2) for a given terrain size, so more dense scenarios require more CPU time. However, the execution time is almost linear when solving low user-density scenarios (e.g., 100m×100m). In all cases, the results were obtained in less than 100 seconds.


## 7. Conclusion and Further Steps

This paper has dealt with the creation of a drone-assisted VoWiFi communication service, which could be of use in cases such as emergency situations or covering live events that lack better alternative infrastructure. We have defined a new optimization problem for the deployment of drones to create a two-layer network (access and distribution) connected to 5G. Our problem is aimed at finding the minimum number of drones (and their type and location) required to deploy the service constrained to a minimum user coverage and speech quality.Using a PSO-based search algorithm, we have calculated the optimal solution for terrains up to100m×100m and 100 users with moderate computational resources. The overall number of UAVs tends to increase with the terrain size (i.e., with users’ sparsity) or with the number of users. The next step planned is to explore new applications in this field: (a) to implement a model-based Call Admission Control (CAC) algorithm in UAVs, so new calls can be rejected if the network is saturated; and (b) to explore new applications of the 3-D UAV optimal placement, such as quality-guaranteed videocalls or IoT sensing through drones, that might require a different network architecture.



---

*Source: 3110572-2022-01-28.xml*