{'fraction_non_alphanumeric': 0.05612438376943497, 'fraction_numerical': 0.01312518434247672, 'mean_word_length': 4.191622005906158, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 14, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
UAV-Enabled Wireless Power Transfer: Trajectory Design and Energy Optimization

This paper studies a new unmanned aerial vehicle (UAV)-enabled wireless power transfer (WPT) system, where a UAV-mounted mobile energy transmitter (ET) is dispatched to deliver wireless energy to a set of on-ground energy receivers (ERs). We investigate how the UAV should optimally exploit its mobility via trajectory design to maximize the energy transferred to all ERs during a finite period. First, we consider the maximization of the sum energy received by all ERs by optimizing the UAV's trajectory subject to its maximum speed constraint. We obtain its optimal solution, which shows that the UAV should hover at one single fixed location during the whole period. However, the sum-energy maximization incurs a"near-far"fairness issue. To overcome this issue, we consider a different problem to maximize the minimum received energy among all ERs. We first consider an ideal case by ignoring the UAV's maximum speed constraint, and show that the relaxed problem can be optimally solved via the Lagrange dual method. Then, for the general case with the UAV's maximum speed constraint considered, we propose a new successive hover-and-fly trajectory motivated by the optimal trajectory in the ideal case, and obtain efficient trajectory designs by applying the successive convex programing (SCP).


I. INTRODUCTION
Radio frequency (RF) transmission enabled wireless power transfer (WPT) is a promising solution to provide perpetual and cost-effective energy supplies to low-power electronic devices, and it is anticipated to have abundant applications in future Internet-of-things (IoT) wireless networks (see, e.g., [3], [4] and the references therein). In conventional WPT systems, dedicated energy transmitters (ETs) are usually deployed at fixed locations to send RF signals to charge distributed energy receivers (ERs) [5] such as low-power sensors or IoT devices. However, due to the severe propagation loss of RF signals over long distance, the performance of practical WPT systems for wide coverage range is fundamentally constrained by the low end-to-end power transmission efficiency. As a consequence, in order to provide ubiquitous wireless energy accessibility for massive low-power ERs distributed in a large area, fixed-location ETs need to be deployed in an ultra-dense manner. This, however, would tremendously increase the cost, and thus hinder the large-scale implementation of future WPT systems. In the literature, various approaches have been proposed aiming to alleviate this issue by enhancing the WPT efficiency at the link level, including multi-antenna energy beamforming [6]- [12], energy scheduling [13], [14], and energy waveform optimization [15], [16]. Different from these prior studies, in this paper we tackle this problem from a fundamentally new perspective at the system level, i.e., we propose a radically novel architecture for WPT systems by utilizing unmanned aerial vehicles (UAVs) as mobile ETs.
UAV has drawn significant research interests recently due to its wide range of applications, including surveillance and monitoring, aerial radar and camera, cargo delivery, communication platforms, etc. Particularly, mounted with miniaturized communication transceivers, low-altitude UAVs can be used as aerial mobile base stations (BSs) or relays to help enhance the performance of terrestrial wireless communication systems (see, e.g., [17] and the references therein). By optimizing the UAV's trajectory jointly with communication scheduling, the air-to-ground link distances between the UAV and its served ground users can be effectively shortened, thus significantly improving the system throughput [18], [19]. Motivated by UAV-assisted wireless communications, in this paper we propose a new UAVenabled WPT architecture as illustrated in Fig. 1. With the proposed architecture, a group of UAVs are dispatched as mobile ETs that fly above the serving area to cooperatively charge a set of distributed ERs on the ground. We assume that these ERs have fixed locations that are a priori known for the UAV trajectory design. By exploiting the fully controllable mobility of the UAVs via trajectory design, the proposed system is expected to significantly improve the WPT performance, while reducing the number of required ETs as compared to the conventional WPT systems with ETs deployed at fixed locations. Notice that there have been some prior works (e.g., [20], [21]) that considered the use of moving ground vehicles as mobile charging stations to wirelessly charge sensor nodes. Different from ground vehicles that have only limited mobility in a two-dimensional (2D) area usually with a large number of ground obstacles, UAVs can be more flexibly deployed and moved in the three-dimensional (3D) free space. Furthermore, compared to terrestrial wireless channels that typically suffer from various impairments such as shadowing and fading in addition to path loss, UAVs usually possess better channels to ground ERs due to the higher chance of having moderate-distance line-of-sight (LOS) links with them.
A fundamental question to be addressed for the proposed UAV-enabled WPT systems is as follows: how to jointly optimize the trajectories of multiple UAVs so as to maximize the energy transferred to all ERs in a fair manner? This question, however, has not yet been studied in the literature to our best knowledge, and it is non-trivial to be addressed, even for the simplest scenario with one UAV and two ERs [1]. Notice that in this basic setup, the transferred power from the UAV to the two ERs critically depends on the UAV's trajectory or locations at different time. For example, when the UAV moves from one ER to the other, their received power will decrease and increase, respectively, thus resulting in an interesting power trade-off between them.
For the purpose of exposition, in this paper we focus on the UAV-enabled multiuser WPT system with one UAV/ET and K > 1 ERs, while leaving the general scenario with more than one UAVs/ETs for our future work. Under the considered setup, we aim to find the optimal UAV trajectory to maximize the amount of energy transferred to the K ERs during a finite charging period, subject to the UAV's maximum speed constraint. To our best knowledge, this work is the first that explores the UAV's trajectory design for WPT performance optimization. The main results of this paper are summarized as follows.
First, we consider the UAV's trajectory optimization in the horizontal plane with a fixed altitude above the ground to maximize the sum received energy of all ERs. Despite that this problem is non-convex and involves an infinite number of variables, we derive its optimal solution, which shows that the UAV should hover at one single fixed optimal location during the whole charging period, and the optimal hovering location can be obtained via a 2D exhaustive search.
In particular, we obtain the optimal hovering location in closed-form for the special case with K = 2 ERs. It is shown that when the distance between the two ERs is smaller than a certain threshold, the optimal hovering location is exactly above the middle point between the two ERs; whereas when their distance is larger than the threshold, the optimal hovering location is closer to one ER than the other. In general, the sum-energy maximization with the optimal fixed hovering location incurs a severe "near-far" fairness issue, especially for a network spanning over a large area, as the near ERs in close proximity to the UAV can receive significantly more energy than the far-away ERs.
Next, to resolve the fairness issue, we consider an alternative problem to maximize the minimum received energy among all ERs via trajectory optimization. This problem is more challenging to solve than the previous sum-energy maximization. To obtain useful insight and a performance upper bound, we first consider an ideal case by assuming that the UAV maximum speed constraint can be ignored. 1 In this case, the problem is shown to satisfy the so-called timesharing condition in [24], and thus can be optimally solved via the Lagrange dual method. The obtained optimal solution reveals that the UAV should hover over an optimal set of fixed locations, with optimal hovering time allocations among them. For the special case of K = 2 ERs, the closed-form solution is also obtained and compared against that for sum-energy maximization.
Last, we consider the above min-energy maximization problem for the general case with the 1 Notice that this assumption holds approximately if the charging duration and/or the UAV maximum speed are sufficiently large.
UAV's maximum speed constraint considered. Inspired by the optimal multi-location-hovering solution in the ideal case, we propose a successive hover-and-fly trajectory design, where the UAV successively hovers at a given set of hovering locations (e.g., using the optimal set of hovering locations obtained in the ideal case if the charging duration is sufficiently large) each for a certain duration, and flies with the maximum speed between these hovering locations. The total flying time is minimized by finding the path with the shortest traveling distance to visit all of these hovering locations. The proposed trajectory is proved to be optimal for the case of K = 2, and also asymptotically optimal for K > 2 if the charging duration is sufficiently large so that the total flying time becomes asymptotically negligible. Furthermore, we also propose a successive convex programming (SCP)-based algorithm to obtain a locally optimal solution to the min-energy maximization problem with K > 2. By employing the successive fly-and-hover trajectory as the initial point, the SCP-based algorithm iteratively refines the UAV trajectory to improve the max-min energy of all ERs until convergence.
It is worth noting that in the preliminary work [1], we considered the UAV-enabled WPT system in the case with K = 2 ERs and characterized the achievable region of the received energy by the two ERs via UAV trajectory optimization; while in [2], we studied the min-energy maximization for the case with K > 2 ERs. Different from the above two prior studies, this paper provides a more comprehensive study on both the sum-energy and min-energy maximization problems for the general case with K ≥ 2 ERs.
The remainder of this paper is organized as follows. Section II presents the system model of the UAV-enabled WPT system. Section III presents the optimal solution to the sum-energy maximization problem. Section IV presents the optimal solution to the min-energy maximization problem when the UAV maximum speed constraint is ignored. Section V presents the proposed solutions to the min-energy maximization problem with the maximum UAV speed constraint considered. Section VI provides numerical results to validate the effectiveness of our proposed trajectory designs. Finally, Section VII concludes this paper.

II. SYSTEM MODEL
We consider a UAV-enabled multiuser WPT system, where a UAV is dispatched to deliver wireless energy to K ≥ 2 ERs located on the ground. Let K {1, . . . , K} denote the set of ERs.
Each ER k ∈ K has a fixed location on the ground, denoted by (x k , y k , 0) in a 3D Euclidean coordinate, which is assumed to be known to the UAV a priori for its trajectory design. We consider a finite charging period with duration T , denoted by T [0, T ]. At each time instant t ∈ T , the UAV is assumed to fly at a fixed altitude H > 0 above the ground, whose timevarying location is denoted as (x(t), y(t), H). We assume that the initial and final UAV locations at time t = 0 and t = T are not pre-determined, but can be freely optimized. 2 Denote by V in meter/second (m/s) the maximum possible speed of the UAV. We then have the maximum speed constraint at each time instant expressed as withẋ(t) andẏ(t) denoting the time-derivatives of x(t) and y(t), respectively.
We assume that the wireless channel between the UAV and each ER is LOS-dominated, so that the free-space path loss model similarly as in [17], [18] is adopted. At time t ∈ T , the channel power gain from the UAV to ER k ∈ K is modeled as is their distance and β 0 denotes the channel power gain at a reference distance of d 0 = 1 m. Assuming that the UAV has a constant transmit power P , the received RF power by ER k at time t is thus given by The total energy received by each ER k ∈ K over the whole charging period is a function of the UAV's trajectory {x(t), y(t)}, which can be written as Note that at each ER, the received RF signals are converted into direct current (DC) signals for energy harvesting via rectifiers [7]. In practice, the RF-to-DC conversion is generally non-linear and the conversion efficiency critically depends on the received RF power and waveform at the ER (see, e.g., [4], [15], [22]). To the authors' best knowledge, a generic model to accurately characterize the non-linear RF-to-DC conversion efficiency is not available yet, but in general the harvested DC power monotonically increases with the received RF power. Therefore, for simplicity, in this paper we consider the received RF power in (2) and the resultant received energy in (3) by ERs prior to RF-to-DC conversion as the performance metrics.

III. SUM-ENERGY MAXIMIZATION
In this section, we consider the maximization of the sum received energy of all ERs over the charging period, by optimizing the UAV's trajectory {x(t), y(t)} subject to the speed constraints in (1). The problem can be expressed as Problem (P1) involves an infinite number of optimization variables, i.e., x(t)'s and y(t)'s over continuous time t. Furthermore, (P1) is a non-convex optimization problem as the objective function is a non-concave function with respect to the trajectory {x(t), y(t)}. Therefore, (P1) is generally difficult to be optimally solved. In the following, we first present the optimal solution to (P1) for the general case with arbitrary value of K ≥ 2 in Section III-A, and then consider (P1) for the special case with K = 2 in Section III-B to draw more insights.

A. Optimal Solution to Problem (P1)
For the ease of description, given the UAV's location x(t) and y(t) at a given time t, we define the sum-power received by all the K ERs as Accordingly, the sum-energy received by the K ERs over the whole charging period is Let x ⋆ and y ⋆ denote an optimal UAV location that maximizes the function ψ(x, y), i.e., (x ⋆ , y ⋆ ) = arg max x,y ψ(x, y).
As the function ψ(x, y) is non-concave with respect to x and y, it is generally difficult to find the closed-form expression of x ⋆ and y ⋆ . Fortunately, ψ(x, y) in problem (6) only has two variables x and y. Besides, it is not difficult to show that x ⋆ and y ⋆ should satisfy x ≤ x ⋆ ≤ x and y ≤ y ⋆ ≤ y, respectively, where This is because if (x ⋆ , y ⋆ ) lies outside the box specified above, we can always increase the energy transferred to all the K ERs by moving (x ⋆ , y ⋆ ) into the box. As a result, we can adopt a 2D exhaustive search over the box region [x, x] × [y, y] to find (x ⋆ , y ⋆ ). 3 Notice that the optimal solution of x ⋆ and y ⋆ to problem (6) is generally non-unique.
Given x ⋆ and y ⋆ , we have the following proposition.
Proposition 3.1: The optimal trajectory solution to problem (P1) is given as Proof: See Appendix A.
Proposition 3.1 indicates that the UAV should hover at one single fixed location (x ⋆ , y ⋆ , H) during the whole charging period, referred to as single-location hovering. Due to the nonuniqueness of the optimal solution x ⋆ and y ⋆ to problem (6), such an optimal hovering location (x ⋆ , y ⋆ , H) is non-unique in general, as will be shown in an example given in the next subsection for the case of K = 2. However, this single-location-hovering solution can lead to a severe "nearfar" fairness issue in multiuser WPT, as the near ERs in close proximity to the optimal hovering location can receive significantly more energy than the far ERs, especially in a large network with many ERs that are sufficiently separated from each other. To overcome this issue, in Section IV we will consider an alternative problem formulation to maximize the minimum received energy among all ERs to ensure their fairness. Before that, in the following subsection, we derive the optimal solution to problem (P1) in closed-form for the special case of K = 2 ERs to provide more insights on the sum-energy maximization problem.

B. Special Case with K = 2 ERs
In the special case with K = 2, without loss of generality we assume x 1 = −D/2, x 2 = D/2, and y 1 = y 2 = 0, where D denotes the distance between the two ERs. Based on Proposition 3.1, in this case, the UAV should hover at a fixed location (x ⋆ , y ⋆ , H) above the line between the two ERs with y ⋆ = 0. Therefore, it only remains to find x ⋆ .
Towards this end, we first re-express the received power by ER 1 and ER 2 as follows, given Accordingly, the function ψ(x, y) in (4) can be simplified aŝ As a result, finding x ⋆ is equivalent to determining the maximizer ofψ(x), i.e., x ⋆ = arg max xψ (x).
Based on Lemma 3.1, the optimal solution x ⋆ to maximizeψ(x) is found. By using this result together with Proposition 3.1, we have the following proposition to solve (P1) for K = 2.

Proposition 3.2:
In the special case of K = 2, the optimal solution to (P1) is given as follows.
For illustration, Fig. 2 shows the optimal hovering location x ⋆ , with x ⋆ (t) = x ⋆ , ∀t ∈ T , versus the distance D between the two ERs in the case of H = 5 m. It is observed that x ⋆ = 0 the other symmetric optimal hovering location) when D > 2H/ √ 3. It is also observed that as D increases, x ⋆ becomes closer and eventually converges to D/2. These observations are consistent with Proposition 3.2. Furthermore, notice that it follows from (12) that lim D→∞ x ⋆ = lim D→∞ ξ = D/2, which can be intuitively explained as follows. When the distance between the two ERs is sufficiently large, the UAV should hover above one of the two ERs to maximize the transferred energy to it, which in turn maximizes the sum-energy transferred to both ERs. In this case, the energy transferred to the other ER becomes negligible. This thus leads to a severe near-far fairness issue between the two ERs.

IV. MIN-ENERGY MAXIMIZATION WITHOUT UAV SPEED CONSTRAINT
In this section, to overcome the aforementioned fairness issue in the sum-energy maximization, we consider an alternative performance metric, namely the min-energy maximization. Specifically, we maximize the minimum received energy among all the K ERs via optimizing the UAV's trajectory {x(t), y(t)}, subject to the maximum speed constraints in (1). In general, this problem is formulated as Problem (P2) is a non-convex optimization problem, and it is more difficult to solve than the sumenergy maximization problem (P1). In particular, the single-location-hovering optimal solution of (P1) given in Proposition 3.1 is no longer valid for (P2). To tackle (P2), in this section we first consider an ideal case by ignoring the UAV speed constraints in (1) and solve the relaxed problem optimally. In practice, the speed constraints in (1) can be ignored if the charging duration T and/or the maximum UAV speed V are sufficiently large (see Proposition 5.1 for a more rigorous argument). For ease of presentation, we rewrite problem (P2) without the constraint (1) in the following problem, denoted by (P3).
In Section V, we will consider the general case of (P2) with the UAV speed constraints (1) included, and propose efficient solutions to (P2) based on the optimal solution obtained for (P3).

A. Optimal Solution to Problem (P3)
Problem (P3) can be equivalently expressed in the following problem by introducing an auxiliary variable E.
Though problem (P3.1) is non-convex, it can be shown that it satisfies the so-called time-sharing condition in [24]. Therefore, the strong duality holds between (P3.1) and its Lagrange dual problem. As a result, we can optimally solve (P3.1) by using the Lagrange dual method [23].
Let λ k ≥ 0, k ∈ K, denote the dual variable associated with the constraint in (13) for the kth ER. Then the Lagrangian associated with (P3.1) is given as Accordingly, the dual function of (P3.1) is given by for which the following lemma holds.

Lemma 4.1:
In order for the dual function f ({λ k }) to be upper-bounded from above (i.e., Based on Lemma 4.1, the dual problem of (P3.1) is given by Then, we can solve problem (P3.1) by equivalently solving its dual problem (D3.1). Let the feasible set of {λ k } characterized by the constraints in (16) and (17) as X . In the following, we first solve problem (15) to obtain f ({λ k }) under any given feasible dual variables {λ k } ∈ X , then solve (D3.1) to find the optimal {λ k } to minimize f ({λ k }), and finally construct the optimal primal solution to (P3.1).
In the above, (19) consists of an infinite number of subproblems, each corresponding to a time instant t. Let the optimal solutions to (18) and (19) be denoted by E {λ k } , as well as and y {λ k } (t), ∀t ∈ T , respectively.
As for subproblem (18), since 1 − k∈K λ k = 0 holds for any given {λ k } ∈ X , its objective value is always zero. In this case, we can choose any arbitrary real number as the optimal solution E ({λ k }) for the purpose of obtaining the dual function f ({λ k }).
On the other hand, note that the subproblems in (19) are identical for all time instant t ∈ T .
Therefore, we can drop the time index t and re-express each problem in (19) as Similarly as for problem (6), problem (20) has two optimization variables, and the optimal solution of x {λ k } and y {λ k } satisfies x ≤ x {λ k } ≤ x and y ≤ y {λ k } ≤ y, with x, x, y, and y given in (7). As a result, we can adopt a 2D exhaustive search over the box region [x, x] × [y, y] to find the optimal x {λ k } and y {λ k } . Accordingly, the optimal solution to problem (19) is given by Note that the optimal solution of x {λ k } and y {λ k } to (20) is generally non-unique, and we can arbitrarily choose any one of them for obtaining the dual function f ({λ k }). 4 By substituting (15), the dual function f ({λ k }) is obtained. 4 When the optimal solution x {λ k } (t)'s, y {λ k } (t)'s, and E ({λ k }) are not unique, they may not be optimal for the primal problem (P3.1) after the dual problem is solved. As a result, an additional step is required to obtain the optimal primal solution of E, x(t)'s, and y(t)'s to (P3.1), as will be shown later in Section IV-A3.

3) Constructing Optimal Primal Solution to (P3.1):
Based on the optimal dual solution {λ * k } to (D3.1), we need to obtain the optimal primal solution to (P3.1), denoted by {x * (t)}, {y * (t)}, and E * . It is worth noting that when using the Lagrange dual method to solve problem (P3.1) via the dual problem (D3.1), the optimal solution to problem (15) under the optimal dual solution is the optimal primal solution to (P3.1), if such a solution is unique and primal feasible [23]. On the other hand, when the optimal (15) are non-unique, they may not be feasible nor optimal to problem (P3.1) in general. In the latter case, we need to time-share among these non-unique optimal solutions as follows to construct the optimal primal solution {x * (t)}, {y * (t)}, and E * to (P3.1).
With the optimal dual solution {λ * k }, suppose that problem (20) has a total number of Γ ≥ 1 optimal location solutions to maximize denote the corresponding received power at each ER k ∈ K when the UAV stays at the location (x * γ , y * γ , H). In this case, proper time-sharing among the Γ solutions is necessary for constructing the optimal primal solution to (P3.1). Time-sharing means that the UAV should hover at each of these different locations for a certain portion of the total duration T . Let τ γ denote the optimal hovering duration at (x * γ , y * γ , H). Then, the optimal τ * γ 's, together with the  2) Update {λ k } using the ellipsoid method by noting that the subgradient of f ({λ k }) is s 0 (λ 1 , . . . , λ K ) [25]. c) Until {λ k } converge with a prescribed accuracy. d) Set λ * k ← λ k , ∀k ∈ K. e) Output: Obtain all the Γ optimal locations to maximize the function ψ {λ * k } (x, y) as (x * 1 , y * 1 ), . . . , (x * Γ , y * Γ ); then solve the LP in (22) to obtain {τ * γ } Γ γ=1 and E * ; and finally obtain the optimal trajectory solution of {x * (t), y * (t)} to problem (P3.1) or (P3) as in (23). maximum min-energy E * , can be obtained by solving the following problem.
Note that problem (22) is a linear program (LP), which can be solved by using standard convex optimization techniques [23]. As a result, the optimal solution of E * to (P3.1) is found. Finally, we obtain the optimal trajectory solution of {x * (t), y * (t)} to (P3.1) (and thus (P3)), which is given in the following proposition based on the above time-sharing property, with the proof omitted for brevity.
Remark 4.1: Note that Proposition 4.1 implies that to maximize the min-energy transferred to the K ERs, the UAV should hover above a number of fixed locations during the charging period, and the optimal hovering locations (i.e., x * γ 's and y * γ 's) are generally different from the locations of the ERs (i.e., x k 's and y k 's). We refer to such a design as multi-location hovering. Different from the single-location hovering for sum-energy maximization, the result here shows that the UAV should in general hover over different locations so as to balance the energy transferred to all ERs.

B. Special Case with K = 2 ERs
To provide more insights, in this subsection we consider the min-energy maximization in the special case with K = 2 ERs, by assuming x 1 = −D/2, x 2 = D/2, and y 1 = y 2 = 0, similarly as in Section III-B. In this case, by setting y(t) = 0, ∀t ∈ K, problem (P3) can be simplified as

Proposition 4.2:
The optimal solution to problem (P3-2ER) is given as follows by considering two different cases: with ξ given in (12).
Proof: See Appendix C.
By comparing Proposition 4.2 versus Proposition 3.2, it is observed that in the case with K = 2 ERs, each of the optimal hovering locations for the min-energy maximization is also optimal for the corresponding case in the sum-energy maximization. Thus, the achieved sumenergy in problem (P3-2ER) is identical to that in (P1) when K = 2. This implies that without the maximum UAV speed constraint, the multi-location-hovering solution to (P3-2ER) can maximize the sum-energy received by the two ERs, while ensuring their energy fairness thanks to the time sharing. Nevertheless, it is worth noting that in the general case with K > 2, the optimal hovering locations for (P3) are generally different from that for (P1). This is due to the fact that x ⋆ and y ⋆ are the maximizer of the sum-power ψ(x, y), but x * γ 's and y * γ 's are the maximizers of the weighted sum-powerψ {λ k } (x(t), y(t)), which is different from ψ(x, y) if any two λ k 's are not identical in the case of K > 2.

V. MIN-ENERGY MAXIMIZATION WITH UAV SPEED CONSTRAINT
In this section, we consider the general min-energy maximization problem (P2) by including the practical UAV maximum speed constraints in (1). This problem is difficult to be solved globally optimally in general with K > 2. To tackle this problem, we propose two suboptimal solutions inspired by the optimal solution obtained previously for problem (P3) in the ideal case without the UAV maximum speed constraint.

A. Successive Hover-and-Fly Trajectory Design for Problem (P2)
In this subsection, we propose a successive hover-and-fly trajectory design to solve problem (P2) based on the optimal solution obtained for (P3) in the ideal case. Recall that the optimal solution to (P3) corresponds to Γ optimal hovering locations, i.e., {(x * γ , y * γ , H)} Γ γ=1 . In the proposed trajectory design with the maximum speed constraint, the UAV sequentially hovers at each of these locations for a certain duration and flies from one location to another with the maximum speed V . As a result, to find the optimal successive hover-and-fly trajectory, we need to first determine the UAV's traveling path to visit all the Γ locations with the minimum flying distance so as to minimize the total flying time, and then optimize the hovering time at each of these locations for the remaining time in the charging duration. For ease of description, let d γ,ζ (x * γ − x * ζ ) 2 + (y * γ − y * ζ ) 2 denote the distance between the γth hovering location (x * γ , y * γ , H) and the ζth hovering location (x * ζ , y * ζ , H). We define a binary variable f γ,ζ for any γ, ζ ∈ {1, . . . , Γ}, γ = ζ, where f γ,ζ = 1 indicates that the UAV should fly from the γth hovering location (x * γ , y * γ , H) to the ζth hovering location (x * ζ , y * ζ , H), and f γ,ζ = 0 otherwise. The trajectory design problem thus becomes determining {f γ,ζ } to minimize Γ γ=1 Γ ζ=1,ζ =γ f γ,ζ d γ,ζ , provided that each of the Γ locations is visited exactly once. The flying distance minimization problem considered here is reminiscent of the well-known traveling salesman problem (TSP) (see, e.g., [26]- [28]), with the following difference. In the standard TSP, the salesman (or equivalently the UAV of our interest) needs to return to the origin city (the initial hovering location) after visiting all these cities (or hovering locations here); but our flying distance minimization problem does not have such a requirement since the initial and final hovering locations can be optimized. Fortunately, it has been shown in [29] that our flying distance minimization problem can be transformed to the standard TSP as follows. First, we add a dummy hovering location, namely the (Γ + 1)-th hovering location, whose distances to all the existing Γ hovering locations are 0, i.e., d Γ+1,γ = d γ,Γ+1 = 0, ∀γ ∈ {1, . . . , Γ}. Note that this dummy hovering location is a virtual node that does not exist physically. Then, we obtain the desirable traveling path by solving the standard TSP problem for the Γ + 1 hovering locations, 5 and then removing the two edges associated with the dummy location. For the obtained traveling path, we define the permutation π(·) over the set {1, . . . , Γ}, such that the UAV first visits the π(1)-th hovering location, followed by the π(2)-th, the π(3)-th, until the π(Γ)-th hovering location at last. In this case, the resulting flying distance and flying duration with the maximum speed V are given as D fly = Γ−1 γ=1 d π(γ),π(γ+1) , and T fly = D fly /V , respectively. We denote the corresponding trajectory as {x(t),ŷ(t)} T fly t=0 . It is worth noting that the above traveling path is only feasible when the charging duration T is no smaller than T fly , i.e., T ≥ T fly , since otherwise the charging duration is not sufficient for the UAV to visit all the Γ hovering locations. In the following, we first determine the hovering time allocation over different locations in the case with T ≥ T fly , and then refine the trajectory design in the case with T < T fly . Q k (x(t),ŷ(t))dt, with Q k (·, ·) given in (2). Also, recall that Q k (x * γ , y * γ ) denotes the received power at ER k ∈ K when the UAV hovers at the location (x * γ , y * γ , H). Then the optimal hovering durations, denoted as τ * * γ 's, together with the corresponding maximum min-energy of the K ERs, denoted by E * * , 5 Note that although the TSP is an NP-hard problem in combinatorial optimization, various heuristic and approximation algorithms have been proposed to give efficient high-quality solutions for it (see, e.g., [26]- [28]). In particular, it has been shown in [28] that the TSP problem can be formulated as a binary integer program, by incorporating a set of constraints to ensure there is only a single tour connecting all visited locations. The binary integer program can be solved via CVX [30] by using the Mosek solver that supports the integer program (see https://mosek.com/ for details).

2) Hovering Time Allocation When
can be obtained by solving the following LP.
Proof: When T ≫ T fly , the flying time is negligible and thus the successive hover-andfly trajectory is equivalent to the optimal multi-location-hovering solution to (P3). In this case, the objective value achieved by the successive hover-and-fly trajectory for (P2) is asymptotically approaching the optimal value of (P3), which actually serves as the upper bound for that of (P2). Therefore, the proposed trajectory design is asymptotically optimal for (P2) when T ≫ T fly .

3) Trajectory Redesign When T < T fly :
In this subsection, we consider the case when T < T fly .
In this case, the UAV traveling path {x(t),ŷ(t)} T fly t=0 based on the TSP solution is no longer feasible since the charging time is not sufficient for the UAV to visit all the Γ hovering locations. To address this issue, we first find the solution to (P2) when T is sufficiently small (i.e., T → 0) such that the UAV can only hover at one single location, and then reconstruct a modified successive hover-and-fly trajectory for the case of T < T fly .
First, when T → 0, the UAV should hover at one single fixed location, denoted by (x fix , y fix , H), where x fix and y fix can be obtained by solving the following problem via a 2D exhaustive search over (x, x) × (y, y).
Next, we reconstruct the trajectory as follows by down-scaling the previously obtained travel-  Table I to find the Γ hovering locations {(x * γ , y * γ , H)} Γ γ=1 . b) Add a dummy hovering location, namely the (Γ + 1)-th hovering location, and set its distances to all the existing Γ hovering locations as 0.
where κ = T /T fly < 1 denotes the linear scaling factor. Note that when T → 0, we have κ → 0, and the above redesigned trajectory reduces to hovering at one single fixed location (x fix , y fix , H); while T → T fly , we have κ → 1, and the above redesigned trajectory becomes identical to the TSP-based trajectory {(x(t),ŷ(t), H)} T fly t=0 . We summarize the overall algorithm for the proposed successive hover-and-fly trajectory design as Algorithm 2 in Table II, for both the cases of T ≥ T fly and T < T fly .

4) Optimality in the Case With K = 2 ERs:
In the special two-ER case with x 1 = −D/2, x 2 = D/2, and y 1 = y 2 = 0, the min-energy maximization problem with the maximum speed constraint is simplified as follows by setting y(t) = 0, ∀t ∈ T .
(P2-2ER) : max As it has been shown in Proposition 4. In other words, the optimal UAV trajectory is Proposition 5.2: The above successive hover-and-fly trajectory solution is optimal for problem (P2-2ER) in the case of K = 2 ERs .
Proof: See Appendix D.

B. SCP-Based Trajectory Design for Problem (P2)
In this subsection, we develop an alternative SCP-based algorithm to find a locally optimal solution to problem (P2). Note that the SCP-based trajectory design has been studied for throughput or energy efficiency maximization for UAV-enabled wireless communication systems [18], [19], but the results cannot be directly applied for UAV-enabled WPT systems considered in this paper. With the SCP-based trajectory design, we first discretize the whole charging duration into a finite number of N time slots, each with duration ∆ = T /N. Note that the duration ∆ is chosen to be sufficiently small, such that we can assume that the UAV location is approximately unchanged during each slot n, which is denoted as (x[n], y[n], H), n ∈ N {1, . . . , N}. In this case, the received energy by each ER k ∈ K at slot n is given bŷ where the constraints in (31) correspond to the discretized version of the maximum speed constraints in (1). Note that the constraints in (31) are all convex but the objective function in (30) is not concave. Therefore, problem (30) is a non-convex optimization problem.
For the non-convex optimization problem (30), we obtain a locally optimal solution by proposing an SCP-based algorithm, which is operated in an iterative manner to successively maximize a lower bound of the objective function in (30) The inequalities in (32) Note that the functionÊ As a result, problem (35) is a convex optimization problem, and thus can be optimally solved by standard convex optimization techniques such as the interior point method [23]. Furthermore, as shown in Lemma 5.1, the objective function in problem (35) serves as a lower bound for that in problem (30). Therefore, after each iteration i, the objective function of problem (30) achieved by {x (i) [n], y (i) [n]} monotonically increases [18]. As problem (30) has a finite optimal value, the SCP-based algorithm in (35) will converge to a locally optimal solution to problem (30)  In this case, the SCP-based trajectory design can always achieve a performance no worse than the successive hover-and-fly trajectory design, as will be validated by the numerical results later.

VI. NUMERICAL RESULTS
In this section, we provide numerical results to evaluate the performance of our proposed trajectory designs. In the simulation, we set β 0 = −30 dB, H = 5 m, and P = 40 dBm. For all simulations given below, we consider the average received power by the ER, which is obtained by normalizing the total received energy by the charging duration T .

A. Sum-Energy Maximization
This subsection evaluates the performance of our proposed optimal solution for the sumenergy maximization problem (P1). First, we consider the case with K = 2 ERs, where x 1 =  −D/2, x 2 = D/2, and y 1 = y 2 = 0, with D denoting the distance between the two ERs.
Note that Proposition 3.2 indicates that when D > 2H/ √ 3 = 5.77 m, there are two optimal single-location-hovering solutions to (P1). In the simulation, we choose the one with x ⋆ (t) = −ξ, y ⋆ (t) = 0, ∀t ∈ T (with ξ given in (12)), such that the single hovering location is closer to ER 1 than ER 2. Fig. 3 shows the average received power versus D. When 0 ≤ D ≤ 2H/ √ 3, it is observed that the average received power by ER 1 or ER 2 is identical. This is because in this case, the optimal solution is obtained by letting the UAV hover above the middle point between the two ERs during the whole charging period (see Proposition 3.2). On the other hand, when D > 2H/ √ 3, it is observed that as D increases, the average received power by ER 1 (the ER closer to the UAV) increases, while that by ER 2 (the ER farther away from the UAV) decreases.
This is due to the fact that as D increases in this case, the optimal hovering location (selected in this example) becomes closer to ER 1. Accordingly, the average sum received power of the two ERs is dominated by the received power of ER 1, and the near-far fairness issue becomes more severe as D becomes larger.
Next, we consider a UAV-enabled WPT system with K = 10 ERs, whose locations are shown in Fig. 4. In this figure, the green triangle indicates the optimal hovering location for sum-energy maximization (i.e., (x ⋆ , y ⋆ , H) given in (6)). It is observed that this hovering location is close to ERs 7-10, but far away from other ERs, especially ER 1. Fig. 5 shows the corresponding average received power by each individual ER. It is observed that ERs 7-10 receive much higher energy than the other ERs, which illustrates the near-far fairness issue in the sum-energy maximization for this multiuser WPT system with more than two ERs.

B. Min-Energy Maximization
In this subsection, we evaluate the performance of our proposed trajectory designs for the minenergy maximization problem (P2). First, we consider the case with K = 2 ERs. Fig. 6 shows the average received power by each ER with the optimal trajectory obtained by solving problem (P2-2ER), with different values of the maximum UAV speed V and the charging duration T .
It is observed that when D ≤ 2H/ √ 3 = 5.77m, the static UAV design (with V = 0) achieves the same performance as the mobile UAV design, regardless of V and T . By contrast, when D > 5.77m, the proposed mobile UAV design achieves higher received power than the static UAV design (with the UAV fixed at (0, 0, H)), and the performance gain becomes more pronounced as D increases. Furthermore, it is observed that as the UAV's maximum speed V increases, the average max-min received power by the ERs increases, as the traveling time between the two ERs becomes less significant.
Next, we consider the min-energy maximization problem for the UAV-enabled WPT system in Fig. 4 with K = 10 ERs. Note that besides the single-location-hovering solution for the sum-energy maximization problem (P1), Fig. 4 also shows the multi-location-hovering solution for problem (P3) without the UAV speed constraint, as well as the proposed successive hoverand-fly trajectory design and the SCP-based trajectory design for problem (P2) with the UAV speed constraint considered, by assuming T = 20s. First, it is observed that there are Γ = 4 optimal hovering locations for the min-energy maximization problem (P3), which are close to ERs 1-2, ER 3, ERs 4-6, and ERs 7-10, respectively. This clearly shows that when the ERs are close to each other (e.g., ERs 7-10), then the UAV should hover above one single location above them for charging them more efficiently. It is also observed that the SCP-based trajectory design and the successive hover-and-fly trajectory design both visit the Γ optimal hovering locations.
Furthermore, it is observed that the SCP-based trajectory in general deviates from the successive hover-and-fly trajectory when flying from one hovering location to another. Fig. 7 shows the max-min average power received by all ERs in the 10-ER WPT system in Fig. 4 versus the charging duration T , for our proposed trajectory designs, as compared to the following two benchmark schemes.
• Single-location hovering for minimum energy maximization: During the whole charging period, the UAV hovers at a fixed location (x fix , y fix , H) obtained in (26).
• Successive hover-and-fly over all ERs: In this successive hover-and-fly scheme, instead of optimizing the UAV's hovering locations, they are simply set as the K locations above the K ERs. This scheme can be implemented by using Algorithm 2 via replacing Fig. 7, the upper bound corresponds to the optimal value achieved by (P3) with the UAV's maximum speed constraints ignored. It is observed that the two proposed trajectory designs, namely the successive hover-and-fly and the SCP-based trajectory designs, outperform the singlelocation-hovering design, and achieve higher average max-min average power as T becomes large. When T ≥ 15 s, the proposed successive hover-and-fly and the SCP-based trajectory designs also outperform the successive hover-and-fly trajectory over all the ERs. Furthermore, it is observed that the SCP-based trajectory achieves better performance than the successive hover-and-fly trajectory, and converges to the upper bound, when T becomes large.

VII. CONCLUSION
This paper studies a new UAV-enabled multiuser WPT system. We exploit the mobility of the UAV to maximize the energy transferred to all ERs over a given charging period by optimizing the UAV's trajectory under its practical speed constraint. First, we consider the sum-energy maximization of all ERs and obtain the optimal solution to this problem, which shows that the UAV should hover at only one fixed location during the whole charging period. However, this single-location-hovering solution may lead to unfair performance among ERs due to their different distances from the UAV. To achieve fairness among all ERs, we consider an alternative   problem to maximize the minimum energy transferred to all ERs. We first consider the relaxed problem by ignoring the UAV speed constraints and derive the optimal solution, which shows that the UAV should hover over multiple fixed locations with optimal hovering time allocations among them. Based on this solution, we further propose two new trajectory designs for solving the min-energy maximization problem in the general case with the UAV speed constraint considered.
Numerical results show that the proposed UAV-enabled WPT system with optimized UAV trajectory significantly enhances the WPT performance over the conventional WPT system with fixed ETs, and yet achieves fair energy delivery to ERs. In future work, we will extend our study to the general multi-UAV scenario with joint trajectory design for multiple UAVs to optimize their cooperative WPT performance.

A. Proof of Proposition 3.1
First, we consider a relaxed problem of (P1) in the ideal case by ignoring the speed constraints in (1). By using (5), the relaxed problem can be written as Due to the relaxation of the constraints (1), the optimal value of problem (36) serves as an upper bound for that of (P1). It is evident that problem (36) can be decomposed into different subproblems as follows: ψ(x(t), y(t)), ∀t ∈ T , where each subproblem corresponds to a time instant t. By comparing (6) and (37), it is evident that x(t) = x ⋆ and y(t) = y ⋆ is the optimal solution to problem (37) for any t ∈ T . Therefore, {x ⋆ (t), y ⋆ (t)} given in (8) is indeed the optimal solution to problem (36).
Next, it is evident that {x ⋆ (t), y ⋆ (t)} given in (8) is always feasible to problem (P1), since the optimal location is fixed and thus no UAV flying is needed. Furthermore, the objective value achieved by {x ⋆ (t), y ⋆ (t)} for problem (P1) is the same as the optimal value for problem (36).
Since the optimal value of problem (36) is an upper bound of that of (P1), we can conclude that {x ⋆ (t), y ⋆ (t)} is indeed the optimal solution to (P1). Therefore, Proposition 3.1 is proved.

B. Proof of Lemma 3.1
The first property ofψ(x) can be easily shown and the detail is thus omitted here. In the following, we prove the second and third properties forψ(x). Note that the first-order derivative ofψ(x) can be obtained aŝ Then we consider the two cases with D ≤ 2H/ √ 3 and D > 2H/ √ 3, respectively.
By combining the above properties, this lemma is proved.

C. Proof of Proposition 4.2
First, it is evident that at the optimal solution {x * (t)} to (P3-2ER), the received energy at the two ERs must be equal. Furthermore, if the UAV stays at a location (x, 0, H) for a certain duration, then it should stay at the symmetric location (−x, 0, H) for the same duration, since otherwise, we can always increase the min-energy of the two ERs by adjusting the two locations to be symmetric. As a result, without loss of optimality, we only need to consider the following symmetric trajectory {x(t)} satisfying Based on (38), it follows from (9), (10), and (33) that the received energy values at the two ERs are identical, i.e.,Ê whereψ(x(t)) is given in (11). Accordingly, we can re-express problem (P3-2ER) as Based on Lemma 3.1, if D ≤ 2H/ √ 3, then the optimal solution to (40) is given by x * (t) = 0, ∀t ∈ [0, T /2). If D > 2H/ √ 3, then the optimal solution is x * (t) = −ξ, ∀t ∈ [0, T /2). By also choosing x * (t) = ξ, ∀t ∈ [T /2, T ) due to symmetry and using (38), this proposition is proved.

D. Proof of Proposition 5.2
For K = 2, the optimality of the successive hover-and-fly trajectory can be easily proved in the case of D ≤ 2H/ √ 3. Therefore, in the following, we focus on the proof for the case of First, similarly as Proposition 4.2 for problem (P3-2ER), the optimal trajectory solution to (P2-2ER) should satisfy the symmetric property in (38). In this case, problem (P2-2ER) is reexpressed as follows based on (39). Combining the above result with the optimal symmetric trajectory in (38), this proposition is thus proved.