Energy-Efficient UAVs Deployment for QoS-Guaranteed VoWiFi Service

sensors Article Energy-Efficient UAVs Deployment for QoS-Guaranteed VoWiFi Service Vicente Mayor * , Rafael Estepa , Antonio Estepa and Germán Madinabeitia Department of Telematics Engineering, Universidad de Sevilla, 41092 Seville, Spain; [email protected] (R.E.); [email protected] (A.E.); [email protected] (G.M.) *Correspondence: [email protected] Received: 2 June 2020; Accepted: 7 August 2020; Published: 10 August 2020   Abstract: This paper formulates a new problem for the optimal placement of Unmanned Aerial Vehicles (UAVs) geared towards wireless coverage provision for Voice over WiFi (VoWiFi) service to a set of ground users confined in an open area. Our objective function is constrained by coverage and by VoIP speech quality and minimizes the ratio between the number of UAVs deployed and energy efficiency in UAVs, hence providing the layout that requires fewer UAVs per hour of service. Solutions provide the number and position of UAVs to be deployed, and are found using well-known heuristic search methods such as genetic algorithms (used for the initial deployment of UAVs), or particle swarm optimization (used for the periodical update of the positions). We examine two communication services: (a) one bidirectional VoWiFi channel per user; (b) single broadcast VoWiFi channel for announcements. For these services, we study the results obtained for an increasing number of users confined in a small area of 100 m 2 as well as in a large area of 10,000 m 2 . Results show that the drone turnover rate is related to both users’ sparsity and the number of users served by each UAV. For the unicast service, the ratio of UAVs per hour of service tends to increase with user sparsity and the power of radio communication represents 14–16% of the total UAV energy consumption depending on ground user density. In large areas, solutions tend to locate UAVs at higher altitudes seeking increased coverage, which increases energy consumption due to hovering. However, in the VoWiFi broadcast communication service, the traffic is scarce, and solutions are mostly constrained only by coverage. This results in fewer UAVs deployed, less total power consumption (between 20% and 75%), and less sensitivity to the number of served users. Keywords: UAV; voice over IP; wireless LAN; IEEE 802.11; voice over IP over WiFi; VoWiFi; quality of service; energy 1. Introduction Unmanned Aerial Vehicles (UAVs) for wireless communications have experienced rapid growth in a broad range of application domains [ 1 ]. On-board communication devices enable UAVs to enhance coverage, capacity, reliability or energy efficiency of wireless networks. However, note that the drone communication technology has a decisive impact on the data rate and range usable in the mission [ 2 ]. The predominant technology in UAV-related literature is cellular (i.e., UAVs are used as aerial base stations) [ 3 ], but it is not uncommon to find studies with other communication technologies for UAV-to-ground communication such as WiFi [4–6] or Bluetooth [7]. This work takes WiFi as enabling technology for UAV-to-ground communication. WiFi provides a data range of 11 Mbps–1 Gbps and a range of up to 250 m (depending on the revision). Deploying UAVs for wireless networks brings in new opportunities, such as creating a provisional communication infrastructure in Search and Rescue (SAR) missions [ 1 , 8 ]. However, it also brings multiple challenges such as optimal 3D placement, performance analysis, path planning, backhaul Sensors 2020,20, 4455; doi:10.3390/s20164455 www.mdpi.com/journal/sensors Sensors 2020,20, 4455 2 of 32 connectivity, or energy limitation, just to name a few [ 3 , 9 ]. In this work, we deal with the challenge of optimal multi-UAV 3D placement in the context of creating a provisional WLAN (i.e., UAVs are used as aerial Access Points—AP) to provide ground users with VoIP over WiFi (VoWiFi) service. A distinctive characteristic of this service is that 3D placement has to consider not only coverage (e.g., [10,11]) but also VoIP speech quality [ 12 ] since the mac-sublayer of the communication protocol limits the number of simultaneous VoIP flows that APs can handle with quality of experience (for example, an AP performing IEEE 802.11 b can handle a maximum of 15 simultaneous calls [ 13 ], even though the number of stations associated to such AP could be multiple times greater). This limit is known as VoIP capacity [14–16]. UAV’s optimal 3D placement is a challenging task that has received significant attention from the research community [ 3 , 9 , 17 , 18 ]. The problem has to take into account multiple factors such as the terrain, location of users, UAV-to-ground channel characteristics or radio interference between UAVs, and in our case, the Quality of Service (QoS). According to Sharkoor et at. [ 19 ], another factor to be carefully taken care of “when deploying UAVs is their flight time and energy constraints”. Indeed, the authors provide an excellent literature review with emphasis on the energy efficiency perspective, dissecting the factors affecting energy consumption in UAVs such as UAV placement, UAV-user association, flight-time, mobility, trajectory, and UAV communication and mechanical energy. Although optimal 3D placement has been extensively addressed, the comparison between works is difficult as they have different objective functions and constraints. In general, we can classify them roughly as (a) those that minimize the number of UAVs deployed [ 20 – 23 ] (i.e., minimize deployment cost); (b) those maximize energy efficiency or battery lifetime [ 24 – 26 ] (i.e., UAV endurance [27]). Energy-aware UAV optimal deployment problems typically considering the power consumption due to either radio communication [ 25 , 26 ] or mechanical energy [ 24 ] using energy consumption models [ 28 , 29 ]. The reader is encouraged to read the surveys [ 2 , 19 , 30 ] for a more detailed list of works and references that address the problem of 3D placement with emphasis in energy consumption. 1.1. Motivation Long-duration activities may require hot replacement of drones due to battery exhaustion. In this work, we would like to deploy aerial APs to provide VoWiFi service to ground users in an outdoor long-duration activity (e.g., concert or similar longer 20–25 min) that will likely require hot replacement of drones due to battery exhaustion. In this context, the following considerations should be taken into account: • Besides coverage, the multi-UAV 3D optimal placement has to consider VoWiFi speech quality for which the mac-sublayer of the communication protocol is crucial. To the best of our knowledge, the only work that has considered this factor [ 12 ] sets the focus only in minimizing the number of UAVs deployed (among solutions with a similar number of drones, the one that extended the battery life of served users was chosen) disregarding energy efficiency in UAVs. • The number of UAVs required for the mission depends not only on the UAVs initially deployed but also on the number of UAVs launched to replace those in battery exhaustion. Thus, besides minimizing the number of UAV initially deployed, we should also seek the placement that maximizes the UAVs operation lifespan, considering UAV communication and mechanical energy. • Long-duration events should consider users’ mobility. So besides the initial 3D placement, there should be a method in place so that UAVs dynamically relocate themselves for service continuity. Sensors 2020,20, 4455 3 of 32 1.2. Contribution of This Paper This paper defines and solves a new optimization problem that finds the number and position of UAVs to be deployed over an area to provide VoWiFi service to a set of ground users. Our optimal 3D placement minimizes the number of UAVs deployed over time (i.e., rate of drones per hour of service) while satisfying coverage and QoS constraints. The contributions of this paper can be summarized as follows: • We mathematically formulate a new UAV optimal deployment problem that accounts for UAVs turnover rate, coverage, and quality of service. • We provide an analytical model that predicts the speech quality in a IEEE 802.11 WLAN for a set of VoIP traffic sources. • We provide an analytical model that predicts UAV energy expenditure due to wireless communications. This information is used along with flight energy consumption to predict UAVs endurance. • We solve the UAV optimal deployment problem using well-known heuristic methods such as genetic algorithm and particle swarm optimization. 2. Related Works Multiple survey papers address the optimal placement of UAVs for wireless communications. In this section, we scrutinize four recent surveys and complement them with other related works applicable. Our goal is to clarify how our work compares with state of the art. The authors in [ 2 ] review the literature for multiple drone applications such as drone base-stations, search and rescue, or surveillance and monitoring, which is challenging due to the disparity of goals and constraints. Regarding energy efficiency and 3D placement, in [ 26 ], the authors suggest an algorithm that minimizes the transmit power for the 3D placement of one drone and assess their approach by simulation. The 3D placement of one aerial base station was also proposed in [ 25 ]. In this case, the authors proposed a placement algorithm to maximize the number of covered users using the minimum transmit power. In both cases, only the power related to radio communication was taken into account. In [ 31 ] the authors propose a placement algorithm for a set of UAV-mounted 5G aerial base stations that maximizes the capacity boost provided by the UAVs in each considered time frame and extends the battery life of the served mobile users. Unfortunately, the authors did not model the energy consumption, stating that “intuitively, less power is needed if the Gateway is closer to the users”. In a context similar to ours, in [ 12 ], we proposed a 3D placement algorithm that minimized the number of aerial APs deployed to provide VoWiFi to ground users. To the best of our knowledge, this is the only related work in which speech quality has been considered a constraint. However, the minimization subject was the number of UAVs launched, and only among solutions with a similar number of drones, the algorithm selected the layout that extended the battery life of served users, overlooking the power expenditure in UAVs. The survey paper [ 3 ] addresses the use of UAVs for wireless networks. The paper provides state of the art in the optimal deployment of UAVs as flying base stations. In their previous work [ 32 ], the authors addressed the optimal deployment and mobility of multiple UAVs for energy-efficient data collection, minimizing the total transmit power of IoT devices (i.e., ground users) during UAVs trajectories. Other works such as [ 18 , 22 , 23 , 33 – 38 ] address the 3D optimal placement problem considering coverage of ground users through different approaches, but disregard energy efficiency. Some of these works consider interference between UAVs [33]. Another excellent paper is [ 30 ], where the authors survey recent research addressing 1–3D placement optimization for aerial base stations. The authors highlight the diversity of objectives in the optimization problem, such as maximizing the system capacity, minimizing the required number of UAVs [ 34 ], or minimizing the total transmit power of the entire aerial system [ 39 ]. The algorithms used for the optimal placement included force brute search [ 37 ], Genetic Algorithms [ 40 ], K-means clustering [ 41 ] or transport theory [ 39 ]. This survey also provides a review of power-efficient operation Sensors 2020,20, 4455 4 of 32 of aerial base stations emphasizing that researchers typically work on either reducing communication energy (i.e., minimizing transmission power) of either the drone or ground users [ 17 ], or reducing mechanical energy of UAVs. The latter requires to count with an energy consumption model [ 21 ], which largely depends on hovering. As the authors put it, “one solution to control the energy consumption of UAVs is to regulate their height. However, changing the height might reduce the performance of UAVs”. This trade-off is also applies to this work and it will be addressed in the next section. Finally, the survey provides a list of testbeds and real experiments in the literature. Interestingly, although most UAV communication research focuses on deploying UAVs as aerial base stations (i.e., cellular technology such as 3G/4G/5G), most testbeds use WiFi (IEEE 802.11 b/g/a) as communication protocol such as in this work. Only in [ 19 ] one can find a literature review with particular emphasis on the energy-efficiency perspective. Besides pointing to +20 other UAV communication-related existing surveys, the authors discuss the main factors affecting UAVs’ energy consumption. One of these factors is UAV placement. As such, the authors review energy-efficiency algorithms for optimal UAV placement in the literature. [ 42 ] suggests using Machine Learning for the optimal placement of UAV-mounted base stations given a predicted traffic demand. In their approach, they first find the optimal partitions of service areas. Then, the optimal location of each UAV that minimizes the total power consumption is derived. While the authors model the transmit power of UAVs deployed, they fail to use a mechanical energy model and simply minimize the UAVs travel distance, assuming that the mechanical power is proportional to it. [ 43 ] proposes a solution to minimize UAV’s mechanical and communication energies while integrating cognitive radio technology. The optimization problem is solved using a deterministic algorithm based on the Weber formulation and its performance is compared to that of a meta-heuristic algorithm, namely particle swarm optimization algorithm (PSO). In this case, the authors model the total energy consumption of a drone with two components, the hover and transmission energies. Finally, Table 1compares the main related works with our proposal. This work’s uniqueness lies in a new objective function for the problem of multi-UAV optimal 3D placement. The consideration of WiFi and its mac-sublayer on the speech quality (as a constraint) can only be found in [ 12 ]. However, [ 12 ] does not model the energy consumption in the UAVs and has a different objective function, as so does other works that model the mechanical and communication power in UAV-installed base stations such as [42,43]. Sensors 2020,20, 4455 5 of 32 Table 1. Comparison of main works related to 3D optimal placement of UAVs for communication. Paper Objective Multi-UAV UAV-to-Ground UAV UAV User Speech Quality Technology Mechanical Power Radio Power Radio Power Constraint [26] minimize transmit power no cellular no yes no no [25] maximize coverage with minimum transmit power no cellular no yes no no [31] maximize capacity and extend battery life of mobile users yes cellular no yes yes no [32] minimize transmit power of mobile users (deployment and mobility) yes cellular no no yes no [22] minimize number of UAVs yes cellular no no no no [39] minimize the total transmit power of the entire aerial system yes cellular no yes no no [42] minimize total power consumption given predicted traffic yes cellular yes yes no no [43] minimize total power consumption yes cognitive radio yes yes no no [12] minimize number of UAVs yes WiFi no no yes yes this paper minimize the ratio between the number of UAVs and UAVs’ endurance yes WiFi yes yes no yes Sensors 2020,20, 4455 6 of 32 3. QoS and UAVs Endurance in VoWiFi Networks The optimization problem addressed in this work provides the number and position of a set of UAVs to the deployed over a known area to provide WoWiFi service to a set of ground users at known locations. Our objective function minimizes the ratio of drones per hour required to provide this service constrained to user’s coverage and user’s speech quality (i.e., QoS). In this section, we study the relationship between drone position, QoS, and UAV endurance. Figure 1illustrates two UAV-mounted APs providing VoWiFi to ground users (note that only the UAV-to-user communication is considered and the communication between UAVs or with the data network backhaul is taken for granted). On the leftmost part, a lower-altitude drone provides coverage to four users. Their traffic (red lines show VoIP traffic flows) is aggregated at the aerial AP. This traffic load may influence the QoS perceived by these users and the UAV’s power consumption due to the transmission/reception of packets. The rightmost UAV is covering eight ground users so its AP aggregates more traffic which may have an impact on the QoS perceived by ground users. Hovering at a higher altitude and servicing more users will likely result in more energy expenditure due to both hovering and more transmission/reception. Thus, the rightmost drone is expected to be replaced earlier than the leftmost drone due to earlier battery exhaustion. This simple example illustrates how the decision variables of the optimization problem (i.e., number and position of drones) have an impact on both, the level of speech quality perceived by VoIP users and UAVs’ energy expenditure. Next, we provide the analytical expressions used to model VoWiFi’s QoS and UAV’s energy expenditure as both aspects are central in the problem’s objective function. Access network (IEEE 802.11) QoS1 PWR1 QoS2 < QoS1 PWR2 > PWR1 Backhaul network Figure 1. UAV-based VoWiFi network. 3.1. Modeling QoS in VoWiFi Each aerial AP and its associated stations can be studied as an independent IEEE 802.11 system, as illustrated in Figure 2. Although all stations have a common Medium Access Control protocol (i.e., MAC sub-layer), the Modulation and Coding Scheme (MCS) set on each station is automatically self-configured seeking, the greatest possible data bit-rate achievable with the present signal strength. Table 2shows different MCSs defined for OFDM modulations (e.g., 802.11 a/g) and the minimum signal strength required for each one. Sensors 2020,20, 4455 7 of 32 Table 2. 802.11 sensitivity relations for OFDM modulations with 20 MHz channels. Modulation Coding Rate Data Rate Sensitivity (Mb/s) (dBm) BPSK 1/2 6 −82 BPSK 3/4 9 −81 QPSK 1/2 12 −79 QPSK 3/4 18 −77 16-QAM 1/2 24 −74 16-QAM 3/4 36 −70 64-QAM 2/3 48 −66 64-QAM 3/4 54 −65 RADIO CHANNEL 802.11 MAC 802.11 PHY IP 802.11 MAC 802.11 PHY IP UDP VoIP USER 1 802.11 MAC 802.11 PHY IP UDP VoIP USER 2 802.11 MAC 802.11 PHY IP UDP VoIP USER N Backhaul network RSSI1 SNR1 RSSI2 SNR2 RSSIN SNRN Figure 2. Communication system for each drone. VoIP is a mature technology that counts with several methods for the assessment of voice quality [ 44 ]. At the planning stage, the method predominantly used in the literature for QoS assessment is the E-Model [ 45 ] since it allows one to estimate the speech quality coming down to the effect that the VoIP traffic load has on network performance in terms of packet loss and delay. The E-model provides a quality score termed R factor from 0 (poor) to 100 (excellent) which can be readily obtained using the following expression [12,46,47]: R=R0−Ie+ (95 −Ie)Ppl Ppl BurstR +Bpl | {z } Ie,eff −(0.024d+0.11 ·(d−177.3)·H(d−177.3)) | {z } Id (1) where: •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 behaviour. 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 Sensors 2020,20, 4455 8 of 32 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 packet loss if 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). •Id accounts for impairments 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 ( 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 the delay in the WiFi network plus 20 ms for the packetization interval of the codec. All terms in Equation (1) are known but the network delay d and packet loss rate Ppl . The values for these two factors will be obtained from our WiFi mac-sublayer analytical model for each UAV deployed (we assume that backhaul networks do not introduce any negative impacts into QoS (i.e., infinite bandwidth), or it can be considered as a constant in R ) (and its associated users). R is one of our objective function constraints, and its computation will be addressed in Section 5.2.2. 3.2. Modeling UAV Endurance Endurance can be described as the total time taken during the flight ( TFlight ) until the depletion of the UAV’s battery. High-power performance commercial UAVs are typically powered by LiPo batteries, whose energy density varies between 150 and 300 Wh/Kg. In this work, the UAV energy expenditure will consider two factors: flight and radio communication, being the former dominant in the energy budget. According to [ 28 ], the energy (in Wh) associated with flying can be broken down into three different flight stages: EFlight =EClimb +ETranslational +PHover ·THover | {z } EHover (2) where EClimb stands for the energy associated with vertical climbing, ETranslational is the energy spent in lateral transitions, and EHover accounts for the energy spent while hovering (i.e., static). As proved in [ 48 ], the hovering factor is dominant and overshadows the other two, and thus, the expression in Equation (2) can be simplified to its last term. Besides Equation (2) , the other contributing factor to energy consumption is the power spent on the radio used by the VoWiFi service. ERadio =EWiFi +EBackhaul (3) where EWiFi represents the energy consumed by the wireless IEEE 802.11 card of the aerial AP, and EBackhaul accounts for the energy consumed by the radio link used for the backhaul network. Assuming that network cards are not running power saving mechanisms, the first term of Equation (3) (EWiFi) can be further decomposed as: EWiFi =PWiFi ·TFlight =ρtx ·Ttx +ρrx ·Trx +ρidle ·Tidle (4) where Ttx , Trx and Tidle stand for the time spent by the network interface card on transmission, reception and idle states respectively (their sum must be TFlight ); and ρtx , ρrx and ρidle stand for the respective power consumption coefficients (which depend on the network interface card). The time taken on each state depends on the traffic processed at the AP during the flight, which in turn depends on the VoIP traffic pattern, the MCS used at each station, and retransmissions that may occur due to noise or collisions. In Appendix Awe derive closed-form expressions for the temporal factors in Equation (4) for the IEEE 802.11 mac sub-layer. Regarding the second factor in Equation (3) , (the backhaul radio link is out of the scope of our this work and the radio power will depend on the particular technology used. However, the assumption Sensors 2020,20, 4455 9 of 32 indicated in Equation (5) is acceptable for the sake of completeness) we can assume that in general, it will be proportional to the WiFi consumption, as expressed in Equation (5): EBackhaul =K·PWiFi | {z } PBackhaul ·TFlight (5) where K is a constant that represents the relation between both radio consumptions. For the remainder of this paper we use K=1 so PBackhaul =PWiFi. Therefore, the total energy Espent by the UAV can be expressed as in Equation (6): E=EFlight +EWiFi +EBackhaul | {z } ERadio (6) Finally, assuming hovering as the dominant factor in Equation (2) , the UAV’s expected flight duration (in hours) can be expressed as: TFlight =EBattery PHover +(1+K)·PWiFi (7) where EBattery represents the battery energy in Watts per hour. TFlight is one of the factors of our objective function and its computation will be addressed in greater detail in Section 5.2.3. 4. Problem Statement 4.1. Terminology and Assumptions As in most related works, we discretize the flying space, as illustrated in Figure 3. The collection of edges of the grid form a set of R3 coordinates denoted as P . These edges define potential locations for UAVs. Each UAV mounts one AP. As such, the words UAV and AP may be used interchangeably for the remainder of this work. (x1, y1, z1) (x2, y2, z2) Figure 3. UAVs placement scenario. Sensors 2020,20, 4455 16 of 32 Finally, one can solve the non-linear equation system formed by Equations (21) and (26) . Since the downlink performance is the dominant factor in QoS as demonstrated in [ 13 ], the packet loss and delay (the small queue assumption allows us to neglect the queuing delay and DEL can be approximated by the channel access delay) at the access point (tagged as i=AP ) will represent the worst case. As such, it will be used to calculate the QoS for the set S . Then, the packet loss ratio and delay can be expressed as: PL =1−1−FER(AP)τ(AP)∏|S| j=1,j6=AP 1−τ(j) λ(AP)E[T](29) DEL =E[B(AP)]·E[T](30) Substituting PL and (DEL + 20 ) (recall that the delay includes the a codec packetization delay of 20 ms) in the terms Ppl and d from Equation (1) provides the output of the QoS_Eval function: the Rfactor. 5.2.3. Endurance Evaluation (Endurance_eval function) This function estimates the expected UAV’s endurance. As introduced in Section 3, the flight duration has two main components: the power (in Watts) required to hover the drone ( PHover ), and the power consumption at both radio links (i.e., recall from Section 3.2 that it was proportional to PWiFi). PHover in rotor-based aircrafts can be easily derived from the Momentum Theory [29] as: PHover =g3 2 ηpsrpp2NRρaπm3 2(31) where g accounts for gravity acceleration, m represents the mass of the aircraft, ηps is the rotorcraft propulsion system efficiency, NR is the number of rotors, rp represents the radius of each rotor and finally ρa represents the density of air. NR , rp and ηps are UAV-specific. While the first two are fixed and can be readily obtained from manufacturer manuals, the latest is variable (although a constant value is generally adopted) and requires experimental estimation [48]. Regarding PWiFi at the access point, the power can be expressed as: PWiFi =1 E[T]·JσPi |{z} idle interval +Jtx,s Ptx,s +Jtx,e Ptx,e +Jtx,c Ptx,c | {z } transmission interval +Jrx,s Prx,s +Jrx,e Prx,e +Jrx,c Prx,c | {z } reception interval (32) where Jσ represents the energy spent during an idle interval; Jtx,s , Jtx,e , and Jtx,c represent the average energy consumption (in Joules) during a successful, erroneous or collided transmission at the access point respectively; and Jrx,s , Jrx,e and Jrx,c represent the expected energy consumption during a successful, erroneous or collided reception respectively. The terms Pi , Ptx,s , Ptx,e , Ptx,c , Prx,s , Prx,e and Prx,c indicate the probability of such events. A detailed expression of the factors in (32) based on the traffic and our model of the mac-sublayer is deduced in Appendix A. Finally, the expected flight duration TFlight of a particular drone can be calculated by substituting the expressions of PFlight and PWiFi in Equation (7). Sensors 2020,20, 4455 17 of 32 5.3. Example Solution This section offers a first example solution and validates the models used in the previous section with the network-simulator ns-3. We define a scenario where 40 ground users are randomly placed in a square area of (100 m × 100 m). The parameters used in the scenario are listed in Table 3. Unless otherwise specified, such settings are common to all experiments in this paper. The solution to the optimization problem has been found by implementing Algorithm 1 in Matlab R  . A graphical representation of the solution is provided in Figure 4. Notice that different colors represent different WiFi associations between users and UAVs. The scenario (including the UAVs) has been simulated with the ns-3 network simulator. In the simulation, no interferences between APs have been considered and transmission buffer sizes have been set to one packet to match the small queue assumption made in Section 5.2.2. The results obtained are summarized in Table 4, which shows the most relevant performance measurements (location, flight time, quality level and radio power). We have performed 30 runs of simulations and the results presented represent average values. The results in Table 4indicate that the solution meets both coverage and speech quality constraints, and the QoS and energy models used in Algorithm 1are aligned with simulation results, which validates the models proposed in Section 5.2.2. Table 3. Example solution input parameters. IEEE Standard Scenario Traffic Constraints Energy Revision 802.11 n Users 40 Calls/hour/user 5 RSSImin −82 dBm EBattery 60 Wh GI 800 ns Size 100 m ×100 m Call length 180 s SNRmin 20 dB PHover 120 W Preamble Greenfield X-Y-Z step 1 m VoIP codec G.711 Rmin 65 ρtx 16 W Bandwidth 20 MHz Altitude layers {10, .. ., 40} m On/Off times CBR Cmin 0.9 ρrx 9.7 W Retries 7 Prop. Exponent 3.3 Packet interval 20 ms ρidle 9.7 W 1 0 10 20 100 30 z (m) 40 90 80 2 100 70 90 60 80 y (m) 50 70 3 60 x (m) 40 50 30 40 30 20 20 10 10 00 Drone Associated users Non covered users Figure 4. Example solution. Table 4. Algorithmic and simulation results. Drone xi|C(i)|TFlight Algorithm 1/ Simulation (min)RPRadio (W) 1(69, 77, 14)12 25.61 89 / 88 20.56 / 20.27 2(83, 22, 30)11 25.64 90 / 89 20.42 / 20.16 3(24, 36, 26)14 25.56 87 / 85 20.86 / 20.53 Sensors 2020,20, 4455 18 of 32 6. Solving a Dynamic Scenario So far, we have applied the GA-based search algorithm in Section 5for solving the problem of the initial deployment of drones to provide service to a set of users who are assumed to be static at known positions. However, in some activities (e.g., outdoor concerts), users are free to move within a bounded area. Consequently, the problem constraints may not hold after a while due to users’s movement unless deployed UAVs are continuously relocated. One approach to do this is to perform periodic updates of the user’s positions every T=Tsample seconds, (re)solve the optimization problem, and update UAVs locations, as illustrated in Figure 5. A central assumption in this approach (and our work hypothesis) is that the set of UAVs initially deployed and their position will suffer small changes (assuming that the trajectories always minimize UAVs displacement) if the sampling period is short enough. 0 t T = Tsample 2T 3T 4T 1 1 2 3 23 Tsolve Trelocate Figure 5. Dynamic scenario. Between two consecutive relocation periods T , one has to consider the relocation delay, (i.e., drones updated their location), that includes: • The time required to solve the problem, Tsolve , which in turn depends on the performance of the algorithm used to find the solution to the problem. • The time required to relocate UAVs, Trelocate , which depends on the distance traveled by UAVs and their speed. Small UAVs typically travel at speeds below 15 m/s [30]. Under the assumption that AUVs will complete self relocation quickly due to high speed and short distance, the main limiting factor for a fast sampling of user positions is the time required to solve the problem. For this reason, we want to reduce the execution time of the search algorithm for periodic relocation. According to [ 65 ], search algorithms based on Particle Swarm Optimization (PSO) tend to be computationally more efficient than GA-based algorithms due to faster converge. However, although both metaheuristics provide similar effectiveness (i.e., solution quality), it is also known that PSO is more prone than GA to get stuck on local solutions. For this reason, we propose to use the GA-search algorithm from Section 5only for the initial deployment, but then use a PSO-based algorithm to solve the UAVs placement for the remainder of the mission. PSO algorithms have been successfully used to solve optimal 3D placement of UAVs before [43]. 6.1. Periodical Search Algorithm: PSO Particle Swarm Optimization (PSO) is a heuristic search method inspired by bird flocking or fish schooling’s social behaviour. In PSO, each candidate solution is represented as a particle that moves around in the search-space towards better solutions. Initially, a collection of particles with random positions in the search-space is created. Each particle is represented by its position (i.e., collection of characteristics, similar to individuals in GA), and a velocity. On each iteration, each particle updates its position based on its velocity, its best known position, and the global best location. Sensors 2020,20, 4455 19 of 32 Algorithm 3: PSO-based search pseudocode. Input: D,Lold (old location), P,U,{wk},Dmax,Cmin,Rmin Output: L∗(new location), f∗ obj (obj. value) Initialization:L∗=Lold,f∗ obj =Inf /* Create the initial swarm */ W= PSO_InitSwarm (Lold); B=W;// Initialize best-known locations F(i) = Inf ∀i;// Initialize best-known obj. function values while !(exit criteria met) do for particle i =1to |W|do /* Update the i-th particle */ W(i)= PSO_UpdateParticle (W(i)); /* Evaluate the i-th particle */ hfobj,C,Ri= Check (D,W(i),U,{wk}); /* Record results */ if fobj <F(i)and C≥Cmin and R≥Rminthen B(i) = W(i);// Update best-known particle’s location F(i) = fobj;// Update best-known particle’s obj. function value if fobj <f∗ obj then L∗=W(i);// Store best-known global position f∗ obj =fobj; end end end end Algorithm 3shows the pseudocode for our PSO-based search algorithm. The input of the algorithm is the previous positioning ( D and Lold ), the set of ground users ( U ) and their location ( {wk} ), the set of edges ( P ), coverage ( Cmin ) and quality ( Rmin ) constraints, and the maximum number of drones ( Dmax ). The algorithm assumes that the number of deployed drones ( D ) does not change between two consecutive executions, and relocates them. To do so, it initializes the swarm of particles ( W ) with the function PSO_InitSwarm around the previous positioning ( Lold ). Then, each particle is updated through the function PSO_UpdateParticle, which receives as input the best known position for that particle. Then, the candidate position ( X ) is evaluated through the function Check from Section 5. Finally, if the particle improves its result, we store the new position as W(i) and, if the best solution is improved, we record it at L∗ , which is the output of the algorithm. This procedure is repeated until the exit criteria is met. PSO implementation and its functions (PSO_InitSwarm and PSO_UpdateParticle) is discussed in Appendix C. 6.2. Convergence Speed In this section, we compare the convergence speed of our two heuristics (GA and PSO) to validate PSO’s faster convergence speed and justify its use for periodical relocation of UAVs. We have performed the following experiment. We have placed 100 users on different sized areas (from 1000 to 10,000 m 2 ). Ground users move according to a correlated random walk model (the rest of the settings are shown in Table 3). Each user moves at a walking speed of 5.3 km/h with a probability of 0.8, and in such case, the direction remains unchanged with probability 0.8. Users rotate 180 degrees when they reach the area bounds. Algorithm 1is used for the initial deployment, and the number of drones deployed D remains unchanged for the remainder of the simulation (15 min). To achieve Sensors 2020,20, 4455 20 of 32 this, we limit subsequent solutions to the best solution found with D drones (even though problem constraints were not satisfied). Every 30 s ( T= 30), we update drones’ location by executing one of the resolution methods: (a) GA, or (b) the PSO-based search we introduced in this section. Figure 6 illustrates the obtained results (x-axis represents the sparsity of users in m 2 /U). With every new solution, drones are relocated (considering a speed of 60 Km/h) so that the sum of the distances traveled by all drones is the minimum possible. 10 20 30 40 50 60 70 80 90 100 m2/U 20 40 60 80 100 120 average resolution time GA PSO Figure 6. Resolution time (Tsolve). Results prove that using the PSO-based algorithm significantly improves the convergence speed, reporting up to an 80% improvement in the resolution time. With the PSO-based search, the resolution time ( Tsolve ) never takes longer than 25 s, which validates its use with our preferential sampling time ( T= 30 s). Results also show that scenarios with high user sparsity are easier to solve, and the algorithm takes less time to converge to solutions. 7. Numerical Results This section provides a numerical analysis of the results obtained with our optimal placement method for two different VoWiFi communication services. •Individual VoIP channels. Each ground user has an independent bidirectional VoIP channel. •Broadcast channel. Every ground user receives a single shared unidirectional VoIP flow. For each communication service, we solve our optimal 3D placement problem for an increasing number of users confined in a small area of 100 m2as well as in a large area of 10,000 m2. The results provided are the average of 30 simulation runs and exhibit a 95% confidence interval. On each run, users’ location was randomly generated. 7.1. Individual VoIP Channels In this experiment, each user has an individual bidirectional VoIP channel. We vary the number of ground users from 10 to 100 over two terrain sizes (100 m 2 and 10,000 m 2 ) using the parameters listed in Table 3. We want to study the evolution of fobj (i.e., the average rate of drones per hour of service), the power spent on communications PRadio and the total required power (i.e., radio communication and hovering). Figure 7b illustrates the drone turnover rate ( fobj ) in UAVs/hour. As introduced in Section 4, this value is the ratio between the number of drones D and the average flight duration ¯ TFlight . Results suggest that scenarios with large user sparsity ( m2/U ) tend to demand more of drones. For example, from 10 to 50 users, the 10,000 m 2 scenario requires more drones to satisfy the coverage constraint (C≥Cmin ·U) than that of 100 m2. The average drone flight duration was around 25 min. Sensors 2020,20, 4455 21 of 32 20 40 60 80 100 users 0 5 10 15 fobj (drones/hour) 100m2 10000m2 (a) Required drones per hour. 20 40 60 80 100 users 16 18 20 22 24 Radio power (W) 100m2 10000m2 (b) Avg. radio power. 10 20 30 40 50 60 70 80 90 100 users 0 200 400 600 total power (W) PFlight + PRadio (100m2) PFlight + PRadio (10000m 2) (c) Total power (sum). Figure 7. Results for the individual VoIP channels experiment. Figure 7b shows the average power spent in communications (i.e., PRadio ). In this graph, we can identify two behaviours: • For less than 50 users, drones spend more radio power in the smaller scenario than in the larger one. This can be explained as follows: while in the bigger scenario up to (1−Cmin)·U users can be excluded from coverage by locating drones far away from them, the smaller one has not enough terrain for the drones to exclude people ( C=U ), which in turn increases the average number of users associated to each aerial AP. • For more than 50 users, the previous behaviour gets inverted when the user density is high enough. This is attributable to solutions where drones are placed at higher altitudes. In general, drones increase their altitude to cover a larger area (i.e., antenna directivity), which in turn reduces the received signal strength and the achievable data bit-rate (i.e., a slower MCS is selected), so the time to complete data transmission is longer which translates into higher energy consumption. Finally, Figure 7c represents the total power used by all UAVs broken down into mechanical power (i.e., PFlight ) and communications power (i.e., PRadio ). In our experiment, PWiFi represents between the 14% and 16% of the total power expenditure, scaling with user density. This ratio is highly dependent on drone characteristics and the power consumption of the radio network interfaces. A careful selection of these aspects is a key factor for reducing the number of required UAVs per hour of service. 7.2. Broadcast Channel Our second experiment considers a single broadcast VoWiFi channel. This is a one-way communication service could be used for announcements to ground users. To compare both VoWiFi communication services, we set up the same range of users and terrain sizes as in our previous experiment (and continue using the settings listed in Table 3). As a particularity, broadcast channels are transmitted using the lowest available bit-rate modulation (i.e., MCS 0 in IEEE 802.11n) to maximize coverage. Figure 8shows the results obtained for fobj , PWiFi and the total power consumption. The average drone turnover rate ( fobj ) shown in Figure 8a depends on the size of the terrain, but the number of served users does not affect negatively since the problem constraint related to QoS is no longer an obstacle due to the scarce traffic load (i.e., there is only one traffic flow from the AP to all its associated users). Figure 8b shows that the power spent in radio communications is close to the power consumption of the radio idle state ( PRadio ≈ 2 ·ρidle ). This shows that the channel occupation is very low. Indeed, the codec G.711 requires a throughput of 64 Kbps (around 80 Kbps at the physical layer), and the available data bit-rate is 6.5 Mbps. As a result, PRadio represents a 14% of the total power (see Figure 8c). Sensors 2020,20, 4455 22 of 32 20 40 60 80 100 users 0 5 10 15 fobj (drones/hour) 100m2 10000m2 (a) Required drones per hour. 20 40 60 80 100 users 16 18 20 22 24 Radio power (W) 100m2 10000m2 (b) Avg. radio power. 10 20 30 40 50 60 70 80 90 100 users 0 200 400 600 total power (W) PFlight + PRadio (100m2) PFlight + PRadio (10000m 2) (c) Total power (sum). Figure 8. Results for the broadcast VoIP channels experiment. Finally, let us compare the total required power in both experiments (see Figures 7c and 8c). Since the VoWiFi broadcast service require fewer drones than the individual, the total power consumption is also improved. Energy savings are reduced up to 20% on the largest scenario and up to a 75% on the small one. As expected, energy savings increase with user density and thus, QoS-constrained scenarios take advantage of replacing individual VoIP channels with a unique broadcast channel. 7.3. Comparing with Other Approaches As shown in Section 2, several research works have addressed UAVs’ optimal 3D deployment for communications. Unfortunately, comparing our results with these works is very difficult due to: (a) the objective function and constraints are different; (b) the radio access network (WLAN versus cellular) is also different, which affects coverage and QoS. But for the sake of completeness, we compare our results with the following approaches: • A search method based on K-means clustering that seeks the minimum number of UAVs that satisfies the optimization problem in this paper, Equation (9) . K-means clustering has also been used for 3D optimal placement in [41]. • Our previous work [ 12 ] for optimal 3D placement in search and rescue missions. This GA-based search algorithm is the only related work that has comparable constraints (i.e., speech quality in WiFi) although the objective function is not the same and does not model UAVs endurance (see Table 1for details). For the comparison, we vary the number of ground users from 10 to 100 over a 10,000 m 2 terrain, using the rest of parameters we listed in Table 3(some parameters, such as coverage ratio, are not supported by our previous work [ 12 ]). Then, we analyze the evolution of the drone turnover rate ( fobj ) and the total power expenditure (i.e., adding the power of all UAVs in the solution). Figure 9illustrates how the UAV turnover rate (left axis) and the total power expenditure (right axis) change while the number of ground users increases. As expected, both variables are interrelated, and scale up with the number of ground users. Results suggest that our new proposal can reduce both, UAVs turnover rate and energy consumption. Compared to the K-means search method, our method saves 60% of the energy consumption for U= 10, and 80% for U= 100. Compared to [ 12 ], our method also provides energy savings, although this is reduced up to 22%. In general, our method also reduces the number of UAVs per hour required to complete the mission (e.g., reduced from 9 to 7 in U=70). Sensors 2020,20, 4455 23 of 32 10 20 30 40 50 60 70 80 90 100 users 5 10 15 20 25 30 35 40 45 50 fobj (drones/hour) 0 300 600 900 1200 1500 1800 2100 2400 2700 3000 Total power (W) this paper [12] K-Means Figure 9. Comparison against other approaches. 8. Conclusions and Future Research This paper formulates a new problem for the UAVs’ optimal 3D placement to offer VoWiFi services with guaranteed speech quality to ground users confined in a known area. Our objective function minimizes the ratio between the number of UAVs initially deployed and their average endurance expectation, providing the layout that requires fewer drones per hour of service. Solutions are found using two well-known search methods: (a) a genetic algorithm is proposed for the initial deployment, and (b) a particle swarm optimization algorithm is proposed for updating UAVs’ location in scenarios with users mobility. A numerical analysis compares the results of our optimal placement algorithm for unicast and broadcast VoWiFi services. Our results for the unicast service show that the drone turnover rate is related to both, users’ sparsity and the number of associated users to each drone. In terms of energy consumption, radio communications represent between a small part (between 14% and 16%) of the total power consumption depending on the density of users served per drone. Large areas tend to locate drones at higher altitudes, which increases UAVs’ mechanical energy consumption. The broadcast VoWiFi service generates a very low traffic load, which translates into a significant reduction of UAVs deployed and total power consumption (between 20% and 75%), and less sensitivity to the number of served users. The next step in our work is to consider two new aspects in this field: (a) interferences between APs, so that overlapping channels could negatively impact on QoS; and (b) using 5G instead of WiFi as the enabling technology for the UAV-to-Ground access network. Author Contributions: Conceptualization, V.M. and R.E.; methodology, V.M.; software, V.M.; validation, V.M., R.E. and A.E.; formal analysis, V.M. and R.E.; investigation, V.M. and R.E.; resources, G.M.; data curation, V.M.; writing—original draft preparation, A.E. and V.M.; writing—review and editing, A.E. and V.M.; visualization, V.M.; supervision, R.E.; project administration, R.E.; funding acquisition, R.E.. All authors have read and agreed to the published version of the manuscript. Funding: This work is partially funded by the research grant number 2020/00000172 from the Regional Government of Andalusia (European FEDER 2014–2020 Andalusia Tech program). Conflicts of Interest: The authors declare no conflict of interest. Appendix A. Consumption Events on WiFi The expected energy consumption per slot can be computed by averaging each consumption event with its probability of occurrence as proposed in Equation (32) . Each state on the WiFi NIC (transmission, reception or idle) presents a different power consumption termed as ρtx , ρrx and ρidle ; Sensors 2020,20, 4455 24 of 32 respectively. In addition, some frame exchanges may last longer that others depending on their result (success, collision or corruption). Consequently, the following events can be identified: The absence of transmission attempts results into an idle channel event, whose consumption (in Joules) is represented by J(j) σ for the j-th station (notice that consumptions may differ between stations and access points) and its probability of occurrence Pi is common to every station in the network: Pi= S ∏ j=11−τ(j)(A1) J(j) σ=ρ(j) idle ·σ(A2) A successful packet transmission event happens when a single station attempts to transmit while the rest remain silent. Let us define its consumption by J(j) tx,swith a probability of P(j) tx,s: P(j) tx,s=1−FER(j)·P(j) s(A3) J(j) tx,s=ρ(j) tx ·T(j) tx,data +ρ(j) rx ·Tack +ρ(j) idle ·(SIFS +2δ+DIFS)(A4) where P(j) srepresents the probability of success of station j: P(j) s=τ(j)|S| ∏ i=1, i6=j1−τ(i)(A5) We consider a corrupted transmission event when a transmission does not collide but fails due to noise influence: P(j) tx,e=FER(j)·P(j) s(A6) J(j) tx,c=ρ(j) tx ·Tdata|c+ρ(j) idle ·(EIFS +δ)(A7) Analogously, the probability that station j suffers a collision transmission event is given by P(j) tx,c , whose consumption is defined by J(j) tx,c: P(j) tx,c=τ(j)· 1− S ∏ i=1, i6=j1−τ(i)!(A8) J(j) tx,c=ρ(j) tx ·Tdata|c+ρ(j) idle ·(EIFS +δ)(A9) The reception probabilities can be derived from the aforementioned transmission probabilities. Notice that stations and access points may behave different. For example, the successful packet reception event is characterised by consumption J(j) rx,swith probability P(j) rx,s:    P(j) rx,s=∑S i=1, i6=jP(i) tx,s, if j=AP P(j) rx,s=P(AP) tx,s·λ(j) rx /λ(AP), if j6=AP (A10) J(j) rx,s=ρ(j) rx ·T(j) rx,data +ρ(j) tx ·Tack +ρ(j) idle ·(SIFS +2δ+DIFS) (A11) Sensors 2020,20, 4455 25 of 32 In addition, stations may hear frames whose destination are not themselves, we term this event as overhear:    P(j) o,s=0, if j=AP P(j) o,s=∑S i=1, i6=jP(i) tx,s−P(j) rx,s, if j6=AP (A12) J(j) o,s=ρ(j) rx ·Tdata|s+ρ(j) rx ·Tack +ρ(j) idle ·(SIFS +2δ+DIFS) (A13) Corrupted receptions (to any destination) can be calculated by summing external corruption transmission events: P(j) rx,e= S ∑ i=1, i6=j P(i) tx,e(A14) J(j) rx,c=ρ(j) rx ·Tdata|c+ρ(j) idle ·(EIFS +δ)(A15) Finally, the event on hearing collisions (to any destination) can be calculated as follows: P(j) rx,c=1−Pi−P(j) tx,c− S ∑ i=1 P(i) s(A16) J(j) rx,e=ρ(j) rx ·Tdata|e+ρ(j) idle ·(EIFS +δ)(A17) The previous expressions rely on transmission and reception times, which depend on the data bit-rate and the operation mode (individual VoIP channels or broadcast): •One individual VoIP bi-directional channel per station:        T(j) tx,data = PLCP +L(j) header +L(j) data/R(j) b, if j6=AP T(j) tx,data =∑S i=1, i6=jλ(i)·T(i) tx,data/λ(j), if j=AP (A18) T(j) rx,data =T(j) tx,data (A19) •One unique broadcast channel:    T(j) tx,data =0, if j6=AP T(j) tx,data =PLCP +L(j) header +L(j) data/R(j), if j=AP (A20) (T(j) rx,data =T(AP) tx,data, if j6=AP T(j) rx,data =0, if j=AP (A21) where Rb (physical data bit-rate) depends on the MCS and R corresponds to the lowest bit-rate (i.e., at MCS 0). Finally, the ACK duration is constant and given by: Tack =PLCP +Lack R(A22) Sensors 2020,20, 4455 32 of 32 56. Zhu, J.; Fapojuwo, A.O. A new call admission control method for providing desired throughput and delay performance in IEEE802. 11e wireless LANs. IEEE Trans. Wirel. Commun. 2007,6, 701–709. [CrossRef] 57. Pong, D.; Moors, T. Call admission control for IEEE 802.11 contention access mechanism. In Proceedings of the GLOBECOM’03—Global Telecommunications Conference, San Francisco, CA, USA, 1–5 December 2003; Volume 1, pp. 174–178. 58. Zhao, Q.; Tsang, D.H.; Sakurai, T. Modeling nonsaturated IEEE 802.11 DCF networks utilizing an arbitrary buffer size. IEEE Trans. Mob. Comput. 2011,10, 1248–1263. [CrossRef] 59. Duffy, K.; Ganesh, A.J. Modeling the impact of buffering on 802.11. IEEE Commun. Lett. 2007 ,11, 219–221. [CrossRef] 60. Malone, D.; Duffy, K.; Leith, D. Modeling the 802.11 distributed coordination function in nonsaturated heterogeneous conditions. IEEE/ACM Trans. Netw. 2007,15, 159–172. [CrossRef] 61. Laddomada, M.; Mesiti, F.; Mondin, M.; Daneshgaran, F. On the throughput performance of multirate IEEE 802.11 networks with variable-loaded stations: Analysis, modeling, and a novel proportional fairness criterion. IEEE Trans. Wirel. Commun. 2010,9, 1594–1607. [CrossRef] 62. Duffy, K.R. Mean field Markov models of wireless local area networks. Markov Process. Relat. Fields 2010 , 16, 295–328. 63. Pei, G.; Henderson, T.R. Validation of ns-3 802.11b PHY Model; Technical Report; Boeing Research and Technology: Seattle, WA, USA, 2009; Available online: http://www.nsnam.org/~pei/80211b.pdf (accessed on 10 August 2020). 64. Guangyu Pei, T.R.H. Validation of OFDM Error Rate Model in ns-3; Technical Report; Boeing Research and Technology: Seattle, WA, USA, 2010. 65. Hassan, R.; Cohanim, B.; De Weck, O.; Venter, G. A comparison of particle swarm optimization and the genetic algorithm. In Proceedings of the 46th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference, Austin, TX, USA, 18–21 April 2005; p. 1897. 66. Dengiz, B.; Altiparmak, F.; Smith, A.E. Local search genetic algorithm for optimal design of reliable networks. IEEE Trans. Evol. Comput. 1997,1, 179–188. [CrossRef] 67. Kennedy, J.; Eberhart, R. Particle swarm optimization. In Proceedings of the ICNN’95-International Conference on Neural Networks, Perth, WA, Australia, 27 November–1 December 1995; Volume 4, pp. 1942–1948. 68. Mezura-Montes, E.; Coello, C.A.C. Constraint-handling in nature-inspired numerical optimization: Past, present and future. Swarm Evol. Comput. 2011,1, 173–194. [CrossRef] 69. Pedersen, M.E.H. Good Parameters for Particle Swarm Optimization; Technical Report HL1001; Hvass Laboratory: Copenhagen, Denmark, 2010; pp. 1551–3203. c 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).