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

Research Article QoS-Aware Multilayer UAV Deployment to Provide VoWiFi Service over 5G Networks Vicente Mayor , Rafael Estepa , and Antonio Estepa Department of Telematics Engineering, Escuela Superior de Ingenieros, Universidad de Sevilla, C/Camino de los Descubrimientos s/ n, 41092 Sevilla, Spain Correspondence should be addressed to Vicente Mayor; [email protected] Received 15 October 2021; Revised 20 December 2021; Accepted 3 January 2022; Published 28 January 2022 Academic Editor: Nagendra Kumar Copyright © 2022 Vicente Mayor et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. 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 (from 25m × 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. 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 twolevel hierarchical network that relays between IEEE 802.11 Hindawi Wireless Communications and Mobile Computing Volume 2022, Article ID 3110572, 13 pages https://doi.org/10.1155/2022/3110572 (WiFi) and cellular 5G for providing VoIP over WiFi (VoWiFi) service to ground users (see Figure 1). 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 trafficflows 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-net- work—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 trafficflows. 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. 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. Section 2 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. 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 softwaredefined 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 5G Core Network Backbone Network Distribution Network (D-UAVs) 5G WiFi (5 GHz) WiFi (2.4 GHz) Access Network (A-UAVs) Figure 1: Proposed scenario. 2 Wireless Communications and Mobile Computing 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 Table 1: Related work comparison. Ref. Objective function Variables Network technologies Considerations Placement Trajectory Resource allocation Access Backbone SINR BW Speech quality Energy [17] max. throughput ✓✗ ✗FDMA FDMA ✓✗ ✗ ✗ [18] max. throughput ✓✗ ✓Cellular Cellular ✓✗ ✗ ✓ [19] max. throughput ✓✗ ✓Cellular Cellular ✓✓ ✗ ✗ [20] max. downlink rate ✓✗ ✓Cellular Cellular ✓✗ ✗ ✗ [21] min. maximum traffic demand ✓✗ ✓Cellular Cellular ✓✗ ✗ ✗ [22] min. path loss ✓✗ ✓NOMA Cellular ✓✗ ✗ ✓ [23] min. transmit power or max. rate ✓✗ ✓NOMA Cellular ✓✗ ✗ ✓ [24] min. UAVs and max. coverage ✓✓ ✓Cellular Cellular ✓✓ ✗ ✗ [25] min. UAVs and max. coverage ✓✓ ✓Cellular Cellular ✓✓ ✗ ✗ [26] max. energy efficiency ✗✓ ✗mmWave Cellular ✓✗ ✗ ✓ [27] min. power allocation ✗✓ ✓OFDMA OFDMA ✓✗ ✗ ✓ [28] min. energy consumption ✗✓ ✓Cellular Cellular ✓✗ ✗ ✓ [29] max. spectrum and energy eff.✗✓ ✓TDD TDD ✗✗ ✗ ✓ [30] max. spectrum and energy eff.✗✓ ✓TDD TDD ✗✗ ✗ ✓ [31] max. minimum throughput ✗✓ ✓Cellular Cellular ✗✓ ✗ ✗ [32] max. minimum user rate ✗✓ ✓OFDMA OFDMA ✓✗ ✗ ✗ [33] max. minimum user rate ✗✓ ✓TDMA TDMA ✓✗ ✗ ✓ [34] max. end-to-end throughput ✗✓ ✓Cellular Cellular ✓✗ ✗ ✓ [35] max. end-to-end throughput ✗✓ ✓Cellular Cellular ✓✗ ✗ ✓ [36] min. outage probability ✗✓ ✓Cellular Cellular ✓✗ ✗ ✓ [15] min. UAVs and user radio energy ✓(singlelayer) ✗✓WiFi N/A ✓✓ ✓ ✓ [16] min. UAVs and UAVs’ energy ✓(singlelayer) ✗✓WiFi N/A ✓✓ ✓ ✓ This paper min. UAVs and user coverage ✓ (multilayer) ✗✓WiFi 5G ✓✓ ✓ ✗ 3Wireless Communications and Mobile Computing 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 Figure 1, 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. Figure 2 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). 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 Rfactor, that ranges from 0 (poor) to 100 (excellent) that is calculated as follows [15, 39, 40]: 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. Ieis 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, BurstRcharacterizes 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 Idcan be obtained from one-way delay in the communication path d, where His the Heaviside function (HðxÞ=0 for x<0 and HðxÞ=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 dand 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 Ppl =1−1−Ppl,a  1−Ppl,d  1−Ppl,b  ,ð2Þ R=R0−Ie+95−Ie ðÞ Ppl Ppl/BurstR  +Bpl |fflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl} Ie,eff −0:024d+0:11 · d−177:3 ðÞ ·Hd−177:3 ðÞðÞ |fflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl} Id :ð1Þ 4 Wireless Communications and Mobile Computing d=dp+da+dd+db,ð3Þ 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 dpaccounts 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,band 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 Figures 1 and 2. 4.1. Terminology. Table 2 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. Let us introduce some functions that will be recurrently used in this paper: (i) The coverage function, Cðx !Þ, represents the set of stations associated with a specific UAV-mounted AP identified by its location, e.g. x !. For example: (a) Cðd ! iÞrepresents the set of A-UAVs associated with the i-th D-UAV. (b) Cða ! jÞrepresents the set of users associated with the j-th A-UAV. (c) C=∑A i=1jCða ! iÞj represents the number of users covered by the system (and hence associated to any A-UAV). (ii) The speech quality function, Rðd ! 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, Sðd ! 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 802.11 MAC 802.11PHY 802.11 MAC 802.11 PHY 5G-UE 5G-AN VoWiFi terminals VoIP PDU Layer (IP, UDP...) 802.11 STA 802.11 AP 5G MAC 5GPHY SDAP PDCP RLC L2 L1 GTP-U UDP IP 5G-UPF + 802.11 MAC 802.11 PHY PDU Layer (IP, UDP...) 5G MAC 5GPHY SDAP PDCP RLC PDU Layer (IP, UDP...) L2 L1 GTP-U UDP IP 802.11 MAC 802.11 PHY VoIP PDU Layer (IP, UDP...) DN Data Network 5G Core Network 5G 802.11 MAC 802.11 PHY 802.11 MAC 802.11 PHY Access-layer UAV IEEE 802.11ac (5 GHz) 802.11 Bridge Distribution-layer UAV IEEE 802.11n (2.4 GHz) Figure 2: Network reference architecture. 5Wireless Communications and Mobile Computing decisive role in determining the number of A- UAVs deployed. 4.3. Optimization Problem. The formal definition of our optimization problem is stated in min D,AD+A ðÞ +1−C U  subject to C U≥Cmin Rd ! 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, ð4Þ where XDand XAstand 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, Rðd ! i,a ! jÞ∀d ! i∈D,a ! j∈C ðd ! iÞ, must be greater than a threshold (Rmin). (iii) D-UAVs uplink throughput, Sðd ! 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 ≥2since 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. Algorithm 1 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. On each iteration, the SolveOptim_PSO (see Algorithm 2) is called to find the optimal location (D∗,A∗)for Table 2: System terminology summary. Symbol Example Description Dd ! 1,d ! 2,⋯,d ! D  Set of D-UAVs’locations D∣D∣Number of deployed D-UAVs d ! ixi,yi,zi fg Cartesian coordinates of the i-th D-UAV Aa ! 1,a ! 2,⋯,a ! A no Set of A-UAVs’locations A∣A∣Number of deployed A-UAVs a ! jxj,yj,zj no Cartesian coordinates of the j-th A-UAV Uu ! 1,u ! 2,⋯,u ! U no Set of ground users’locations U∣U∣Number of ground users u ! kxk,yk,zk fg Cartesian coordinates of the k-th user 6 Wireless Communications and Mobile Computing the specified number of UAVs (i.e., Dand Ainput 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, Dand A, respectively. Each element in Prepresents a candidate set of locations for all UAVs, so they can be decomposed into the Dand Asets (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<f∗ i). 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 than 10−3). It returns the location for Distribution and Access UAVs (D∗and A∗) if any, or an empty set otherwise 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: f= D+A ðÞ +1−C U  , if constraints are satisfied, −C U, otherwise, 8 > > < > > :ð5Þ 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, Cðx ! 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. Cd ! i  =α ! k∈A RSSI d ! i,α ! k  ≥RSSImin SINR d ! i,α ! k  ≥SINRmin RSSI d ! i,α ! k  >RSSI d ! i,α ! j  ∀α ! k≠α ! j  8 > > > > > > > > < > > > > > > > > : 9 > > > > > > > > = > > > > > > > > ; ð6Þ Input: X,U,Dmax,Cmin,Rmin,Smax Output: D,A Initialization: A=0,D=0 while A=A+1and A≤Amax do D=0; while D=D+1and D≤A≤Dmax do D,A= SolveOptim_PSO ðU,D,AÞ if D≠∅and A≠∅then return D,A end end end return ∅ Algorithm 1: Search algorithm pseudocode. (SolveOptim_PSO) Input: X,U,D,A,Cmin,Rmin,Smax Output: D∗,A∗ Initialization: D∗=∅,A∗=∅ P= CreateParticles ðX,D,AÞ P∗=P while !(exit criteria met)do for particle i=1to ∣P∣do Pi= UpdateParticle ðX,Pi,P∗ iÞ; ½Di,Ai=Pi; /∗Evaluate the i-th particle ∗/ fi= Check (U,Di,Ai) if (fi>0and fi<f∗ i)then /∗Update if better ∗/ P∗ i=Pi; f∗ i=fi; if fi< min ðfÞthen /∗Update if best ∗/ ½D∗,A∗=Pi end end end end return D∗,A∗ Algorithm 2: Particle Swarm Optimization function 7Wireless Communications and Mobile Computing The 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). RSSI x !,y !  =Ptx +Gθx,y  −L∥x !−y !∥,θx,y  ,ð7Þ Gθ ðÞ = 10 log10 10Gmax/20 · cos2θ  ,ð8Þ Ld,θ ðÞ =PLoS θ ðÞ LLoS d ðÞ +PNLoS θ ðÞ LNLoS d ðÞ ,ð9Þ where 8 represent a simple gain pattern of an antenna (limited by Gmax) and Lrepresents 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] LLoS d ðÞ = 20 log10 4πfcd c  +ξLoS,ð10Þ LNLoS d ðÞ = 20 log10 4πfcd c  +ξNLoS,ð11Þ 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 fcis the channel frequency. Finally, the probability of receiving each component is given by [48] PLoS θ ðÞ =1 1+αe−βθ·180/π+βα ,ð12Þ PNLoS θ ðÞ =1−PLoS θ ðÞ ,ð13Þ where αand βare environment-dependent constants (e.g., rural and urban) as defined in [45] (e.g., α=β=0for 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. Let Zbe 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 SINR = Prx N+∑k∈ZIk ,ð14Þ where Prx represents the received signal power, N accounts for the noise, and each Ik∀k∈Zstands 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 SINR dB x !,y !  = RSSI x !,y !  −F−N dB,ð15Þ NjdB =−174 + 10 log10 CBW ðÞ ,ð16Þ where Nis the noise, Faccounts 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 function Rðd ! 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. Rd ! i,a ! j  ≥Rmin, ∀d ! i∈D,∀a ! j∈Cd ! i  ,ð17Þ Table 3: Input parameters. Parameter Value Users 60 Size 100m × 100m VoIP codec G.711 (20 ms interval) D-UAVs’WiFi 802.11ac at 5 GHz (80 MHz) A-UAVs’WiFi 802.11n at 2.4 GHz (20 MHz) D-UAVs’altitude 10, 35 ½ m A-UAVs’altitude 40, 55 ½ m RSSImin −82 dBm SNRmin 20 dB Rmin 65 Cmin 90% L5G−SLA 1% d5G−SLA 5ms Smax 1Gb/s 8 Wireless Communications and Mobile Computing Sd ! i  ≤Smax, ∀d ! i∈D:ð18Þ 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 Section 3.2, the end-to-end speech quality (e.g., see Rfactor 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 dcan 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 (Cða !Þ) 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: LWiFi a !  =1− 1−FER a ! ðÞ  τa ! ðÞ Qu !∈Ca ! ðÞ 1−τu ! ðÞ  Ca !  ·λ·ET ½ , ð19Þ DWiFi a !  =EBa ! ðÞ hi ·ET ½ ,ð20Þ SWiFi a !  =〠 u !∈Ca ! ðÞ 1−FER u ! ðÞ  τu ! ðÞ Qi !≠u !∈S1−τi !   ET ½ 0 B B @ 1 C C A·LPDU, ð21Þ where FERða !Þstands for the average Frame Error Rate at the access point, which can be derived from its SINR and Modulation and Coding Scheme (MCS); E½Bis the expected number of back-offslots that a packet waits before transmission; and E½T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 Ppl =1−1−LWiFi d ! i  1−LWiFi a ! j  1−L5G−SLA ðÞ  , ð22Þ d=20ms+DWiFi d ! i  +DWiFi a ! j  +d5G−SLA,ð23Þ where 20 ms accounts for the packetization interval for the G.711 codec. Once computed, Ppl and dcan 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 that Dis upper bounded by Aand that the maximum number of calls to the Check function is upper bounded in our heuristics, the computational complexity D-UAV A-UAV Associated users Non covered users 50 50 40 30 20 10 0 100 100 80 60 40 20 0 0 z (m) y (m) x (m) Figure 3: Example solution. 9Wireless Communications and Mobile Computing