Rechargeable UAV Trajectory Optimization for Real-Time Persistent Data Collection of Large-Scale Sensor Networks
Rui Wang Deshi Li Kaitao Meng






Rechargeable UAV Trajectory Optimization for Real-Time Persistent Data Collection of 
 Large-Scale Sensor Networks

    Rui Wang1, Deshi Li1, and Kaitao Meng2
1Electronic Information School, Wuhan University, Wuhan, China.

2Department of Electronic and Electrical Engineering, University College London, UK.

Emails: 1{ruiwang, dsli}@whu.edu.cn, 2kaitao.meng@ucl.ac.uk

    April 29, 2024
==============================================================================================================================================================================================================================================================




Continuous real-time data collection in wireless sensor networks is crucial for facilitating timely decision-making and environmental monitoring.
Unmanned aerial vehicles (UAVs) have received plenty of attention for collecting data efficiently due to their high flexibility and enhanced communication ability, nonetheless, the limited onboard energy restricts UAVs' application on persistent missions, such as disaster search and rescue.
In this paper, we propose a rechargeable UAV-assisted periodic data collection scheme, where the UAV replenishes energy through the wireless charging platform during the mission to provide persistent information services for the sensor nodes (SNs).
Specifically, the total completion time is minimized by optimizing the trajectory of the UAV to reach the balance among the collecting time, flight time, and recharging time.
However, optimally solving this problem is highly non-trivial due to the non-convex constraints and the involved integer variables.
To address this issue, the formulated problem is decomposed into two subproblems, namely, UAV data collection trajectory optimization and SN clustering and UAV visiting order optimization.
By exploiting the convex optimization techniques and proving the total time is non-decreasing with the cluster number, a periodic trajectory optimization algorithm based on successive convex approximation (SCA) and bisection search is proposed to solve the main problem.
The simulation results show the efficiency of the proposed scheme in practical scenarios and the completion time of the proposed algorithm is on average 39% and 33% lower than the two benchmarks, respectively.



UAVs, data collection, energy limitation, wireless charging, time minimization, trajectory optimization.




§ INTRODUCTION

The continuous real-time sensory data collection of large-scale sensor networks has a major influence on the developments of smart Internet of Things (IoT) in 6G networks <cit.>.
Unmanned aerial vehicles (UAVs) have emerged as indispensable tools for efficient sensing and communication owing to the advantages of high flexibility and enhanced communication ability <cit.>, <cit.>.
Typically, UAV-enable systems can greatly reduce the energy consumption of sensors and increase the data transmission rate by optimizing the UAV trajectory <cit.>.
However, in 6G application scenarios, the explosive growth of data emerging from smart sensors distributed in large-scale networks puts increasing demands for persistent and low-latency data collection.

Existing UAV-assisted data collection works mainly focus on performance optimization when the UAV can complete all tasks in one flight <cit.>, <cit.>, <cit.>, <cit.>. 
For instance, the authors in <cit.> studied a multi-UAV trajectory optimization problem for data collection time minimization, and proposed an efficient algorithm by leveraging the min–max MTSP and convex optimization methods.
The trajectory of UAV and transmit power of sensor nodes (SNs) are jointly optimized in <cit.> to minimize the completion time while ensuring successful data collection from the SNs with limited energy budgets.
Nonetheless, the limited onboard energy greatly affects the performance of the UAV and restricts its application on persistent missions <cit.>.
Additionally, in practice, UAVs are generally not able to complete the tasks without recharging during the mission, especially in large-scale networks <cit.>.
Therefore, energy supplement is essential in UAV-enabled actual applications, which results in the total completion time not only determined by the flight time and collection time of the UAV like previous works <cit.>-<cit.>, but also the recharging time.

To ensure persistent data collection, the near-field inductive wireless charging platform can be deployed for UAV recharging due to the advantages of high efficiency and automation <cit.>, and in this case, the total completion time includes several parts: flying to different targets, collecting data, and flying to the charging platform for recharging. 
To reduce the mission completion time, several conflicting objectives need to be balanced:
Firstly, to reduce the overall time, the UAV can fly faster and collect more SNs at once, which may increase the energy consumption and recharging time. Conversely, designing the trajectory with minimum recharging cost may inevitably result in longer flight time since the UAV will fly slowly. 
Secondly, to reduce the data collection time, the flight time and communication time of the UAV’s collection trajectory need to be balanced since closer proximity to the SN brings higher communication rate but longer flight distance.
Thirdly, to reduce the flight time, the SN cluster and collection order need to be planned carefully for shorter flight distance, but the UAV should return to charge after collecting SNs closer to the charging platform for less time consumption on the return path.
Therefore, to balance the overall contradictions, further in-depth study is needed on the practical charging issue.

With the above consideration, we propose a rechargeable UAV-assisted periodic data collection scheme where all data are periodically collected by clustering of SNs. Different from typical one-flight UAV-assisted systems in <cit.>, our proposed scheme replenishes energy through a wireless charging platform and balances the flying, collecting, and recharging.  
To improve the timeliness of data, we formulate a periodic data collection time minimization problem.
However, solving this optimization problem is highly non-trivial since it is non-convex and involves integer variables closely coupled in the UAV trajectory. 
To address this issue, we propose a two-stage algorithm based on convex optimization and bisection search method by alternating optimization of collection trajectory and flight trajectory to minimize the completion time efficiently.
The main contributions are summarized as follows:

    
  * A rechargeable UAV-assisted periodic data collection scheme is proposed, where a data collection time minimization problem is formulated and decomposed into two subproblems: UAV data collection trajectory optimization and SN clustering and UAV visiting order optimization.
    
  * A successive convex approximation (SCA)-based algorithm is proposed to optimize the UAV data collection trajectory. A bisection search algorithm is proposed to optimize the SN clusters and UAV visiting order, where the total time proves non-decreasing with cluster number.
    
  * Based on alternating optimization of the above two algorithms, a two-stage periodic trajectory optimization algorithm is proposed to minimize the total time.


The rest of the paper is organized as follows. 
In Section 2, the system model and problem formulation are presented. 
In Section 3, the periodic trajectory optimization algorithm is developed. 
In Section 4, simulation results are presented. 
Section 5 concludes this paper.



§ SYSTEM MODEL AND PROBLEM FORMULATION

As shown in Fig. 1, we consider a wireless sensor network with K SNs, denoted by the set 𝒦 = {1,2,...,K}, the Cartesian coordinates of which are known and fixed at w_k∈ℝ^2× 1, k ∈𝒦. A UAV is dispatched to collect data from all SNs and subsequently returns to the wireless charging platform that is located at s∈ℝ^2× 1 for recharging due to limited energy. During one round of data collection from all SNs, suppose that UAV needs to return N times for recharging, so the SNs are partitioned into N non-overlapping clusters, i.e., G_n ∈𝒦, 1 ≤ n ≤ N, ⋃_nG_n=𝒦, G_n_1∩ G_n_2=∅,1 ≤ n_1 ≠ n_2 ≤ N. Here, N is a variable to be optimized. After collecting the data of all nodes in one round, the next round of data collection is cycled in the same way.





 §.§ System Model

In this work, the UAV is assumed to fly at a constant altitude H corresponding to authority regulations and safety considerations. In the collection process of a cluster of SNs, the UAV first takes off from the charging platform to the flight altitude, then collects data, finally the UAV returns to the charging position and lands on the platform for recharging. The UAV is assumed to ascend or descend in constant speed V_a, so the time of ascending and descending is

    T_n,ad = 2H-H_C/V_a,

where H_C denotes the altitude of charging platform. Therefore, the corresponding energy consumption is E_n,ad=P_a(V_a)T_n,ad. P_a is a function of UAV vertical speed,

    P_a(V) = P_0+1/2WV+1/2W√(V^2+W/2ρ A),

where W is the UAV weight.

During the data collection process, the UAV location projected onto the horizontal plane is denoted by q∈ℝ^2× 1, the communication rate  between UAV and SN k is assumed to follow the free-space path loss model as

    R_k = B log_2(1+P_t β_0/σ^2 (H^2+‖q-w_k ‖^2)),

where B is the available bandwidth, P_t is the transmission power of SNs, β_0 is the reference channel power gain at 1m distance and σ^2 is the power of channel noise. To guarantee the successful decoding and quality of service, the signal-to-noise-ratio (SNR) at the UAV, defined by P_t β_0/σ^2 (H^2+‖q-w_k ‖^2), is required to greater than a pre-specified threshold <cit.>. Since SNR is monotonically decreasing with distance between UAV and SNs, this communication requirement can be satisfied by a distance constraint ‖q-w_k ‖≤ d_th, which means the UAV can only receive data from SN k when it located in a circular disc with center w_n and radius d_th.

The UAV trajectory in SNs' communication coverage is represented by M+1 waypoints {q[m]}_m=0^M and M time slots {t[m]}_m=1^M. The length of each segment is sufficiently small, where the distance between the UAV and each SN is approximately unchanged to facilitate the trajectory design. The waypoints of the SN l of the cluster G_n are denoted by {q_n,l[m]}_m=0^M, and the corresponding time slots {t_n,l[m]}_m=1^M. Then the UAV trajectory within the SNs' communication coverage should satisfy the following constraint

    ∑_m=1^M t_n,l[m] B log_2 (1+γ_0/H^2+‖q_n,l[m]-w_n,l‖^2) ≥ Q_n,l,
       ∀ n, ∀ l ∈ G_n,

where Q_n,l is the given SNs' targeting communication requirement and γ_0 ≜P_t β_0/σ^2. Furthermore, the communication time of data collection of G_n is given by T_n,com=∑_l=1^| G_n |∑_m=1^M t_n,l[m], where | G_n | is SNs' number in G_n.

The propulsion power of the UAV is a function of V,

    P(V)=     P_0(1+3V^2/U_tip^2)+P_i(√(1+V^4/4v_0^4)-V^2/2v_0^2)^1/2
        +1/2d_0ρ sAV^3,

where P_0 and P_i represent blade profile power and induced power, respectively. U_tip is the tip speed of the rotor blade. v_0 denotes the mean rotor induced velocity when hovering. d_0 and s are the fuselage drag ratio and rotor solidity, respectively. Also, ρ and A denote the air density and rotor disc area, respectively. Let z_n,l[m] ≜‖q_n,l[m]-q_n,l[m-1] ‖, so the energy consumption of data collection of G_n can be obtained,

    E_n,com = ∑_l=1^| G_n |∑_m=1^M P(z_n,l[m]/t_n,l[m]) t_n,l[m].


The UAV is assumed to keep a fixed speed V_f between the SNs' communication coverage, let [π_n(1),...,π_n(| G_n |)] be a permutation of SNs in G_n, then Γ_n represent UAV visiting order. As a result, the flying time of data collection of G_n can be given by

    T_n,fly =
    1/V_f∑_l=0^| G_n |‖q_π_n(l)[M]-q_π_n(l+1)[0] ‖,

where q_π_n(0)[0]=q_π_n(0)[M]=q_π_n(| G_n |+1)[0]=q_π_n(| G_n |+1)[M]=s, and the corresponding energy consumption is E_n,fly=P(V_f)T_n,fly.

After collecting a cluster of SNs, the UAV will be fully charged for the next cluster collection, and the wireless charging platform adopts constant power charging mode so the charging time is

    T_n,chg = E_n,tot/P_c,

where E_n,tot=E_n,com+E_n,fly+E_n,ad, P_c denotes the charging power, then the total data collection time in G_n is T_n,tot=T_n,com+T_n,fly+T_n,ad+T_n,chg.



 §.§ Problem Formulation

Based on the previous discussions, the periodic data collection time minimization problem can be formulated as follows:

    (P1):   min_N, {x_n,k}, {π_n(l)},{q_n,l[m]}, {t_n,l[m]}∑_n=1^NT_n,tot
    s.t.    (3),
       ‖q_n,l[m]-w_n,l‖≤ d_th, ∀ n ∈ [1,N], ∀ l ∈ G_n, ∀ m, 9a
       ‖q_n,l[m]-q_n,l[m-1] ‖≤min{Δ_max, V_maxt_n,l[m] }, 9b
       ∀ n ∈ [1,N], ∀ l ∈ G_n, ∀ m ∈ [1,M], 
       |z_n,l[m]/t_n,l[m] - z_n,l[m+1]/t_n,l[m+1]|≤ a_max, 9c
       ∀ n ∈ [1,N], ∀ l ∈ G_n, ∀ m ∈ [1,M-1], 
       |z_n,l[0]/t_n,l[0] - V_f |≤ a_max, ∀ n ∈ [1,N], ∀ l ∈ G_n, 9d
       |z_n,l[M]/t_n,l[M] - V_f |≤ a_max, ∀ n ∈ [1,N], ∀ l ∈ G_n, 9e
        E_n,tot≤ E_UAV, ∀ n ∈ [1,N], 9f
        [π_n(1),π_n(2),...,π_n(| G_n |)] ∈ P_n, ∀ n ∈ [1,N], 9g
        G_n = {k|x_n,k=1, k∈𝒦}, ∀ n ∈ [1,N], 9h
        x_n,k∈{0,1}, ∀ n ∈ [1,N], ∀ k ∈ [1,K], 9i
       ∑_n=1^Nx_n,k=1, ∀ k ∈ [1,K], 9j

where x_n,k are binary variables, and x_n,k=1 denotes SN k is associated to G_n, otherwise x_n,k=0. Constraint in (3) ensures the SNs' communication throughput requirements. (9a) denotes the UAV can only collect data in SNs' communication coverage area. The maximum UAV speed and segment length constraint is given by (9b). The maximum UAV accelerated speed is constrained in (9c)-(9e), where a_max denotes the maximum speed difference between two consecutive segments. (9f) represents the UAV energy constraint. In (9g), P_n denotes all possible permutations of visiting order in G_n.

Solving the optimization problem (P1) is highly non-trivial since it is non-convex and involves integer variables. To tackle this challenge, the following result is given.

Lemma 1: The optimal UAV data collection trajectory {q_n,l[m]}, {t_n,l[m]} can be obtained if given the optimal SN clusters N^*, {x^*_n,k} and visiting order {π^*_n(l)} in each cluster.

Proof: With given optimal SN clusters and UAV visiting order in each cluster N^*, {x^*_n,k}, and {π^*_n(l)}. 
The total completion time is decided by the UAV trajectories in SNs' communication coverage and	then the optimal UAV data collection trajectories {q^*_n,l[m]}, {t^*_n,l[m]} can be obtained by N* homogeneous trajectory optimization problems with energy constrain.
With given UAV data collection trajectories {q_n,l[m]}, {t_n,l[m]}, the optimal solution can be obtained with optimal N, {x_n,k}, and {π_n(l)}. 
Hence, with given SN clusters and UAV visiting order, the UAV data collection trajectory can be optimized to obtain the mission completion time. 
With given optimized UAV data collection trajectory, the SN clusters and UAV visiting order can be further optimized to obtain the more optimal mission completion time. 
Alternatively optimizing the UAV data collection trajectory and SN clusters and UAV visiting order, the convergent mission completion time can be obtained. ▪

Inspired by Lemma 1, the problem (P1) will be solved by the optimization of two decomposed subproblems: a UAV data collection trajectory optimization subproblem and an SN clustering and UAV visiting order optimization subproblem. 



§ UAV TRAJECTORY OPTIMIZATION FOR DATA COLLECTION TIME MINIMIZATION

In this section, we first decompose the periodic data collection time minimization problem into two subproblems. Then we discuss solutions to subproblems and propose a periodic trajectory optimization algorithm to solve the main problem.



 §.§ UAV Data Collection Trajectory Optimization

For the given SN clusters and UAV visiting order in each cluster, the periodic data collection time minimization problem is equivalent to solving a series of homogeneous trajectory optimization problems (P2-n) (n=1,2,...,N), i.e.,

    (P2-n):   min_{q_n,l[m]}, {t_n,l[m]} T_n,tot
    s.t.    (3), (9a)-(9f).


To simplify the expression, the subscript n in (P2-n) is omitted, and problem can be rewritten as

    (P3):   min_{q_l[m]}, {t_l[m]} T_tot
    s.t.    (3), (9a)-(9f),

where the objective function is expressed as

    T_tot =   (1/V_f + P(V_f)/P_c V_f) ∑_l=0^| G_n |‖q_π(l)[M]-q_π(l+1)[0] ‖
       + P_0/P_c∑_l=1^| G_n |∑_m=1^M((1+P_c/P_0)t_l[m] + 3/U_tip^2z_l^2[m]/t_l[m]) 
       + P_i/P_c∑_l=1^| G_n |∑_m=1^M(√(t_l^4[m]+z_l^4[m]/4v_0^4)-z_l^2[m]/2v_0^2)^1/2
       + 1/2P_c d_0 ρ sA ∑_l=1^| G_n |∑_m=1^Mz_l^3[m]/t_l^2[m] + (1+P_a(V_a)/P_c)T_ad.


However, the objective function (12) and constraints (3), (9c), (9f) are non-convex. Therefore, we proposed an efficient algorithm to find the high-quality solution to (P4) based on SCA. 
Firstly, we introduce a set of slack variables to tackle the non-convex terms in (P3).
For the objective function in (12) and constraint (9g), we introduce {y_l[m]}, such that y_l[m] = (√(t_l^4[m]+z_l^4[m]/4v_0^4)-z_l^2[m]/2v_0^2)^1/2, which is equivalent to t_l^4[m]/y_l^2[m] = y_l^2[m] + z_l^2[m]/v_0^2.
For constraint (9a), we introduce {A_l[m]},{d_l[m]}, such that A_l^2[m] = t_l[m] log_2(1+γ_0/H^2+d_l^2[m]) and d_l[m] = ‖q_l[m]-w_l‖.
For constraint (9d), we introduce {v_l[m]}, such that v_l[m] = z_l[m]/t_l[m].

With the above manipulations, (P3) can be rewritten equivalently as 

    (P4):   min_{q_l[m]}, {t_l[m]}, {y_l[m]}, {A_l[m]},{d_l[m]},{v_l[m]} T_tot
    s.t.    t_l^4[m]/y_l^2[m]≤ y_l^2[m] + z_l^2[m]/v_0^2, ∀ l ∈ G_n, ∀ m ∈ [1,M], 13a
       ∑_m=1^M A_l^2[m] ≥Q_l/B, ∀ l ∈ G_n, 13b
       A_l^2[m]/t_l[m]≤log_2(1+γ_0/H^2+d_l^2[m]), 13c
       ∀ l ∈ G_n, ∀ m ∈ [1,M], 
       ‖q_l[m]-w_l‖≤ d_l[m],∀ l ∈ G_n, ∀ m ∈ [1,M], 13d
       | v_l[m]-v_l[m+1] |≤ a_max, 13e
       ∀ l ∈ G_n, ∀ m ∈ [1,M-1], 
        v_l[m] ≥z_l[m]/t_l[m],∀ l ∈ G_n, ∀ m ∈ [1,M-1], 13f
       (9b), (9c), (9e), (9f), (9g). 13g


However, the constraints in (13a), (13b), (13c), and (13f) are still complicated and non-convex.
For constraints (13a) and (13b), note that x^2 is a convex function, there is x^2 ≥ x_0^2+2x_0(x-x_0). Therefore, given any point y_l^i[m], z_l^i[m] and A_l^i[m], the constraints in (13a) and (13b) can be tightly written as

    t_l^4[m]/y_l^2[m]≤   y_l^i^2[m]+2y_l^i[m](y_l[m]-y_l^i[m]) 
       - 1/v_0^2(z_l^i^2[m]+2z_l^i[m](z_l[m]-z_l^i[m])),


    ∑_m=1^MA_l^i^2[m] + 2A_l^i[m] (A_l[m]-A_l^i[m]) ≥Q_l/B.


Similarly, since  log_2(1+a/b+x^2) is convex, its global linear lower bound is log_2(1+a/b+x_0^2)-2a/ln2x_0(x-x_0)/(x_0^2+b)(x_0^2+b+a). Therefore, the constraint (13c) has a lower bound as

    A_l^2[m]/t_l[m]≤   log_2(1+γ_0/H^2+d_l^i^2[m]) 
       -2γ_0/ln2d_l^i[m](d_l[m]-d_l^i[m])/(H^2+d_l^i^2[m])+(H^2+d_l^i^2[m]+γ_0).


Based on convex function (x+y)^2 and its lower bound 2(x_0+y_0)(x+y)-(x_0+y_0)^2, constraint (13f) can be tightly written as

    v_l[m]t_l[m]     = 1/2((v_l[m]+t_l[m])^2 - v_l^2[m] - t_l^2[m])
       ≥(v_l^i[m]+t_l^i[m])(v_l[m]+t_l[m]) 
          -1/2(v_l^i^2[m]+t_l^i^2[m])^2 - 1/2v_l^2[m] - 1/2t_l^2[m]
       ≥ z_l[m].


Thus, we can obtain an upper-bounded solution to (P4) by addressing the following convex problem:

    (P5):   min_{q_l[m]}, {t_l[m]}, {y_l[m]}, {A_l[m]},{d_l[m]},{v_l[m]} T_tot
    s.t.    (9a), (9b), (9d), (9e), (9f), (13d), (13e), (14)-(17).


(P5) can be solved using standard convex optimization techniques like CVX. Finally, by successively updating the local point at each iteration via solving (P5),  the algorithm to solve (P3) is obtained and summarized in Algorithm 1.





 §.§ SN Clustering and UAV Visiting Order Optimization

Next, for the given UAV data collection trajectories in SNs' communication coverage, the problem is to find the SN clusters and the visiting order in each cluster, i.e.,

    (P6):   min_N, {x_n,k}, {π_n(l)}(1/V_f + P(V_f)/P_c V_f)∑_n=1^ND_n + NT_0
    s.t.    (9f)-(9j),

where D_n = ∑_l=0^| G_n |‖q_π_n(l)[M]-q_π_n(l+1)[0] ‖, T_0 is constant about UAV takeoff and landing. Since {q_n,l[m]} and {t_n,l[m]} are fixed, and the constraint (9f) can be expressed as

    D_n ≤V_f/P(V_f)(E_max-E_n,com-E_n,ad), ∀ n ∈ [1,N].






Theorem 1: Problem (P6) is NP-hard.

Proof: Note that when N is given in advance, (P6) can be described as an asymmetric distance constrained vehicle routing problem (ADCVRP). Given a set of K points and N vehicles, as well as an asymmetric distance matrix specify the distance from one point to another point. In (P6), the distance matrix can be expressed as d_ij=‖q_i[M]-q_j[0] ‖ and d_ji=‖q_j[M]-q_i[0] ‖, ∀ i,j ∈𝒦∪s, i ≠ j.
Each vehicle starts and returns from the same starting point, each point is visited exactly once by only one vehicle, and there is a limit on the distance each vehicle can travel. The ADCVRP's objection is to minimize the total distance traveled by all vehicles, which is NP-hard. Since (P6) is the ADCVRP with unknown vehicle numbers, which is a more complex version, as a result, (P6) is also NP-hard. ▪

Although (P6) is an NP-hard problem that makes it difficult to find an optimal solution, the solution of (P6) can still be accelerated by searching for the optimal N first.

Lemma 2: The optimal solution to problem (P6) is obtained at the minimum of N in its feasible set.

Proof: In the case that the constraint (20) is satisfied, suppose that for N=N_1, the optimal solution of (P6) is p_N_1^*. When N_2 is larger than N_1, it is equivalent to splitting some loops out of N_1 loops, so the total distance will increase. Furthermore, the second term of the objective function in (P6) increases linearly with N. Therefore, p_N_1^* ≤ p_N_2^*, where p_N_2^* is the optimal solution of (P6) when N=N_2. ▪

Inspired by Lemma 2, the objective function of (P6) is non-decreasing with N, therefore the optimal solution can be found by using bisection search over the cluster number N with constraint (20) holds.
With given N, to tackle the constraint (20) in (P6), it is added to the objective function via the penalty function method, therefore we can formulate

    (P7):   min_{x_n,k}, {π_n(l)}(1/V_f + P(V_f)/P_c V_f)∑_n=1^N D_n + 
       ϵ∑_n=1^Nmax{0, D_n -V_f/P(V_f)(E_max-E_n,com-E_n,ad) }
    s.t.    (9g)-(9j),

where ϵ is the penalty factor, which is set to a large positive number, such that the second term of the objective function in (P7) will be very large when constraint (20) is unsatisfied.

Note that (P7) is an equivalent instance of an asymmetric vehicle routing problem (AVRP), the high-quality approximate solutions can be efficiently found by existing algorithms like a genetic algorithm (GA). Therefore, the problem (P6) can be efficiently solved through bisection search over N and solutions of (P7), the algorithm of solving (P6) is summarized in Algorithm 2.





 §.§ Periodic Trajectory Optimization Algorithm

Based on the discussions in Section 3-A and 3-B, the periodic trajectory optimization (PTO) algorithm is further proposed by alternatively performing the UAV data collection trajectory optimization and SN clustering and UAV visiting order optimization until the objective value of (P1) converges, which is summarized in Algorithm 3.



§ SIMULATION AND RESULTS ANALYSIS

This section provides numerical results to validate the proposed algorithm. 
The UAV altitude is set as H = 100 m and the charging platform altitude is set as H_C = 15 m, we set V_f = 18 m/s, V_a = 6 m/s, a_max = 5 m/s and P_c = 150 W. 
We consider a sensor network with K = 20 SNs in an area of 5 km × 5 km. 
The communication related parameters are set as: B = 1 MHz, P_t = 0.1 W, σ^2 = -110 dBm, β_0 = -60 dB, d_th = 200 m. 
The UAV energy-related parameters are set based on <cit.>.

For evaluation, the proposed algorithm is compared with two benchmarks: a greedy-based algorithm and an optimized Hmode algorithm. In both benchmarks, the UAV collects data by hovering above the SNs. 
The greedy-based algorithm first designs the shortest trajectory that the UAV can collect all the SNs' data in one flight, and then the UAV returns to recharge when its energy is insufficient while flying along the shortest trajectory. 
Compared to the greedy-based algorithm, the optimized Hmode algorithm has optimal SN clusters and UAV visiting orders in each flight.

Fig. 2 shows the UAV trajectories obtained by different algorithms, where the black dots and circles are SNs and their communication coverage, and the triangle represents the wireless charging platform. 
Specifically, the completion time of the benchmarks is 68.2% and 55.4% higher than that of the proposed algorithm, respectively. 
It can be seen that the trajectory obtained by the proposed algorithm is smoother in SNs' communication coverage and returns less for recharging as compared to that obtained by the benchmarks. 
The main reason is that, in the proposed algorithm, the trajectories in SNs' communication coverage achieved the balance between collection and flight time, based on which, the SN clusters and flight path in each cluster are optimized for shorter flight distance and less energy consumption to obtain the UAV trajectory.
Hence, the total complete time achieved by the proposed algorithm is shorter.



It is observed from Fig. 3(a) that the completion time achieved by the proposed algorithm under the two benchmarks decreases as the UAV's maximum energy increases since the UAV can collect more SNs in one flight for performance improvement.
Under different UAV maximum energy, the completion time of the PTO algorithm is on average 38.9% and 34.0% lower than the benchmarks, respectively. 
As the UAV's maximum energy continues to increase, the SN clusters and collection order are fixed, resulting in convergence of completion time.

Fig. 3(b) shows the completion time for different communication throughput requirements. 
It can be seen that with the increase in communication throughput demand, the completion time also increases. 
The main reason is the increase in time for the UAV to collect data from SNs and the recharging time caused by higher energy consumption.
Compared with the greedy algorithm and the optimized Hmode algorithm, the completion time of the proposed PTO algorithm is reduced by 39.1% and 32.0% on average, respectively.



§ CONCLUSION

In this paper, a rechargeable UAV-assisted periodic data collection scheme was proposed to balance the collecting time, flight time, and recharging time. 
Specifically, the UAV data collection trajectory, SN cluster, and UAV visiting order are jointly optimized to minimize the total completion time.
To solve the formulated problem, the problem was decomposed into two subproblems.
By approximating a tight upper bound of the non-convex constraint and proving the total time is non-decreasing with cluster number, a periodic trajectory optimization algorithm based on convex optimization and bisection search method by alternating optimization of collection trajectory and flight trajectory was proposed to minimize the completion time efficiently.
The simulation results verified the efficiency of the proposed scheme in practical scenarios and the completion time of the proposed algorithm is on average 39% and 33% lower than the two benchmarks, respectively.

IEEEtran


