{'fraction_non_alphanumeric': 0.04970837751855779, 'fraction_numerical': 0.009853305054789678, 'mean_word_length': 4.0940805761872605, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Technical Report for A Joint User Scheduling and Trajectory Planning Data Collection Strategy for the UAV-assisted WSN

Unmanned aerial vehicles (UAVs) are usually dispatched as mobile sinks to assist data collection in large-scale wireless sensor networks (WSNs). However, when considering the limitations of UAV's mobility and communication capabilities in a large-scale WSN, some sensor nodes may run out of storage space as they fail to offload their data to the UAV for an extended period of time. To minimize the data loss caused by the above issue, a joint user scheduling and trajectory planning data collection strategy is proposed in this letter, which is formulated as a non-convex optimization problem. The problem is further divided into two sub-problems and solved sequentially. Simulation results show that the proposed strategy is more effective in minimizing data loss rate than other strategies.


I. INTRODUCTION
By introducing an unmanned aerial vehicle (UAV) as a mobile sink into large-scale wireless sensor networks (WSNs), efficient and effective data collections can be achieved for sensor nodes (SNs) that are deployed in hard-to-reach non-urban areas. In this way, the UAV can establish direct communication links through the Line of Sight (LoS) air-to-ground channels to the served SNs, and thus the communication quality and the lifetime of the WSN can both be improved.
UAV-assisted WSNs have attracted growing interest in recent years. The existing works mainly focus on optimizing the UAV trajectory and SNs' running parameters to improve the network performances. Zeng et al. [1], [2] formulate the UAV trajectory planning as a non-convex optimization problem, and solve it by a successive optimization method. Zhan et al. [3]- [5] further incorporate other critical parameters of wireless communications into their optimization process, including the status of the SNs, communication outage probability, error estimation, etc., and propose a variety of UAV path planning strategies accordingly. Furthermore, not limited to WSNs, UAVs have been widely applied to various wireless communication scenarios [7]- [9], and yield promising results.
However, considering that a UAV with limited mobility and communication capabilities can only serve a finite number of SNs at a time, user (i.e. SN) scheduling is therefore a critical issue for WSNs consisting of a large number of SNs, which may cause some SNs to lose the data they just sampled due to storage exhaustion [10] as they cannot offload their data to the UAV for a long time. Such a critical issue has often been ignored in previous studies by assuming either 1) that the UAV can communicate with all SNs in the scenario all the time [1], [2], [6]- [8]; 2) that the UAV only serve one user (SN) at a time [3]- [5], [9], which are not always valid in real-life applications.
To fill the above research gap, a joint user scheduling and trajectory planning data collection strategy for a UAV-assisted large-scale WSN is proposed in this letter, which is executed in a time-division manner. At each time slot, a UAV will schedule the users (i.e. SNs) to communicate with at the next time slot and determine the next way-point to collect the data from the involved SNs. Meanwhile, the orthogonal frequency division multiple access (OFDMA) technology is also considered in the UAV-SNs communication processes, which enables concurrent multi-SN transmissions through flexible bandwidth allocation. Specially, different from existing OFDMA-WSN studies [11], [12] that focus on optimizing the allocation of wireless resource blocks (e.g. communication channels) in a static network scenario, the communication system changes all the time as the UAV moves in this letter, which can be treated as an important complement to existing OFDMA-WSN researches.

A. System Model
Consider an area of interest (AoI) where |Ω all | SNs are randomly and evenly distributed. For each SN i in the AoI, its location (i.e. L i = [L x (i), L y (i)] ∈ R 2×1 ) is fixed and has been prestored in the UAV. The data queue length of SN i at time slot t, denoted as B i (t), depends on both the data sampling rate (i.e. s) and the data uploading throughput with the UAV (i.e. T hr i (t)), which is given as Notice that if the queue length B i (t) exceeds the storage capacity B, the data sampled later will be discarded due to the storage exhaustion. In addition, it is assumed that the data queue of SN i can be estimated by the UAV based on the known sampling rate and the historical communication records with each SN.
In order to facilitate analysis, the behaviors of the UAV during the entire data collection process is modeled in a timedivision manner, so that the trajectory of the UAV can be represented as a serial of way-point coordinates {L u (t)} T t=1 , of which L u (t) = [L ux (t), L uy (t)] denotes the way-point coordinate of the UAV projected on the ground at the t-th time slot (obtained through the equipped GPS), and the flight duration T of the UAV in a data collection task should meet the following condition, namely where T e is the maximum flight time of the UAV. Meanwhile, the displacement of the UAV from the t − 1-th time slot to the t-th time slot is governed by where V max denotes the maximum speed of the UAV and τ is the interval of adjacent time slots. Assume that the UAV is flying at the constant altitude H, and the projected distance between the UAV and SN i at time slot t is measured as d u,i (t) = ||L i − L u (t)||. Thus the communication rate of SN i at time slot t can be expressed as where α i denotes the real-time reference channel power gain at d u,i = 1m in time slot t and p denotes the transmission power that is configured as the same value initially. In addition, due to the fact that the distance between the SNs communicating with the UAV is relatively close and τ in (3) is short enough, the channel status (i.e. σ 2 i ) between each UAV-SN communication link is assumed to be the same and remain unchanged throughout a time slot. Therefore, it is also assumed that any SN i can establish a reliable communication connection with the UAV whenever where d c is the average effective communication distance † between SN and UAV projected on the 2D plane. Meanwhile, by adopting OFDMA technology, the UAV can pre-divide communication resources into n equal and orthogonal resource blocks in advance, of which the bandwidth allocated to each communication SN is W (in (4)). In this way, the UAV using OFDMA technology can support concurrent data transmissions with up to n surrounding SNs that meet the condition in (5) at each time slot t, which is formulated as where Ω o (t) denotes the set of SNs chosen by the UAV to communicate with at time slot t. So, the throughput of SN i at time slot t is given by in which τ c denotes the duration of a data communication process within one time slot, which is assumed that τ c τ . † A UAV-ground communication link is considered reliable if r i (t) ≥ , and given the same environment, the rate threshold mainly depends on the communication distance.

B. Problem Formulation
Under the considered application scenario § , each SN i ∈ Ω all will first store the sampled data in the storage with data queue length B i (t), and wait for the UAV to perform the data collection task. However, when considering the physical limitations of the UAV in maneuvering (i.e. the constraints (2), (3)) and communication capacities (i.e. the constraints (5), (6)) in a large-scale AoI, it can be expected that only a group of SNs can communicate with the UAV at the same time, which may cause some SNs to discard the data just sampled due to exhaustion of storage space [10] because they cannot communicate with the UAV for a long time. The amount of data be discarded by SN i at the t-th time slot is given by Therefore, our goal is to design a data collection strategy for the UAV-assisted WSN to minimize the data loss rate η due to storage exhaustion during the entire data collection task, which is given as

III. AN EFFICIENT STRATEGY TO SOLVE PROBLEM P1
For the sake of non-convexity of the objective function and constraints ((4), (6)), it is hard to solve problem P1 using general optimization methods. In this section, we proposed a joint User scheduling and Trajectory planning Strategy (named as UTS) to approximate solve problem P1 in an efficient way, in which the original problem will be divided into two subproblems and solved successively.
Assume the location of the UAV at time slot t−1 is given as L u (t−1). To reduce the amount of data loss at time slot t (i.e. i∈Ω all D i (t)), the most intuitive way is regarding SNs with the smallest sum of available storage space within the current coverage area as the communication objects (i.e. Ω o (t)) at the next time slot t, and then finding the optimal next waypoint (i.e. L u (t)) to achieve the maximum data throughput with the SNs in Ω o (t) for further releasing their storage space, which can be modeled as sub-problem sP1 and sub-problem sP2, respectively.

A. Solve Sub-Problem sP1
Searching for a SN set which is within the coverage range (i.e. jointly considering the moving capability (3) and the reliable communication distance (5)) of the UAV and owns the smallest sum of available storage space under the constraints of communication resources (i.e. (6)) at time slot t is the goal of problem sP1, which is formulated as s.t. (1), (3), (5), (6). § Notice that our work can also extended to the scenario with the probabilistic LoS channel model [13], [14]. However, due to the page limit, corresponding details are given in section IV of our technical report[].
However, due to the fact that problem sP1 cannot be solved efficiently using general optimization methods, a heuristicbased method is considered here to obtain a sub-optimal solution with a reasonable computational complexity. First of all, the location constraints of SNs in Ω o (t) (i.e. (3) and (5)) are re-expressed as following forms, namely Therefore, with a given L u (t − 1), problem sP1 can be rephrased as the following geometry problem sP1*: Problem sP1*: With a given big circular area C b with L u (t − 1) as its center and V max τ + d c as its radius (see (10)), how to get an optimal circular area C s with d c as its radius (see (11)) inside C b which covers at most n SNs (see (6)) with the smallest sum of available storage space. Then, the set of the involved n SNs are regarded as the Ω o (t) that we are searching for. The graphical illustration is shown in Fig. 1(a) † .
Instead of traversing virtually infinite number of smaller circles with radius d c inside C b , an efficient search method is proposed, which constructs several alternative circular areas with radius d c and picks out the one with the best performance. Then, SNs within the chosen optimal circular area are set as a sub-optimal solution of problem sP1*, which is graphically represented in Fig. 1(b). Meanwhile, the corresponding pseudo code of the proposed search method is given in Algorithm. 1. Construct the search region F(i) based on the SN i and SN k.

5:
Find the optimal circular area C * (i) with radius as d c inside F(i), and put the top n − 2 SNs with the smallest available storage space from C * (i) into Ω opt(i) . 6: end for 7: Output: Pick out the SN set Ω o (t) from {Ω opt(i) |i ∈ Ω dmax−dc } based on (9).
Further details on steps 3 − 5 of Algorithm. 1 are given as follows.
Step 3:The main idea in this step is to find a SN (denoted as SN k) that owns the smallest available storage space and also can communicate with the UAV together with each SN i ∈ Ω dmax−dc , which can be formulated as the following problem, namely (12) † In order to facilitate the analysis, it is assumed that Vmaxτ is larger than dc here. However, even for some special cases where Vmaxτ is smaller than dc, it is only necessary to update the SN set Ω dmax−dc and its related definition mentioned in Algorithm. 1 as Ω dmax : the set of SNs which are within distance Vmax × τ from Lu(t − 1) Note that (12) is a necessary condition that a SN j can communicate with the UAV with the SN i in the time slot t, which is adopted here to expand the search range as much as possible.
Step 4: The main idea in this step is to construct a search region F(i) that clarifies the range of SNs that can communicate with the UAV together with SN i and SN k.
At first, two big circular areas are constructed with the coordinates of SN i and SN k (i.e. L i and L k ) as their centers individually and with 2d c as their radii, which are illustrated as the two biggest black circles in Fig. 1(b). Then, according to (12), it is straightforward to prove that SNs located in the overlapping area (denoted as O(i)) of the constructed two circles can communicate with the UAV either with SN i or SN k. The overlapping area O(i) is shown as the blue area in Fig. 1(b).
Proposition 1: With the given distance between SN i and SN k, i.e., d i,k = ||L i − L k ||, any SN j attempting to communicate with a UAV simultaneously with SN i and SN k must meet the condition where d j,i denotes the distance between SN j and SN i. Proof: It is straightforward to prove the above result by the Pythagorean theorem. Here we denote the both end regions of O(i), i.e., the gaps between O(i) and the circles of radii d c passing through SN i and SN k at the same time, as D 1 (i) or D 2 (i) (shown in Fig. 1). According to Proposition 1, it is easy to prove that the SNs located in D 1 (i) or D 2 (i) cannot communicate with UAV together with SNs i and k. Therefore, the search region F(i) can be obtained by F(i) O(i) − D 1 (i) − D 2 (i).
Step 5: The main idea in this step is to obtain an optimal circular area C * (i) inside the search region F(i), and then put the top n − 2 SNs with the smallest available storage space from C * (i) into Ω opt(i) . In order to reduce the computational complexity and cover the area of F(i) as much as possible, here we construct five alternative circular areas, i.e., {C m (i)|m ∈ {1, · · · , 5}} with radius d c inside the region F(i), and select the one with the best performance. Among {C m (i)|m ∈ {1, · · · , 5}}, C 1 (i) and C 2 (i) denote the circular areas with distinct centers while touching both SN i and SN k simultaneously. Then, C 3 (i) (or C 4 (i)) is denoted as a circular area that touch SN k (or i) and with its corresponding center being collinear with SN i (or k). C 5 (i) is the circular area with its center located at the midpoint of SNs i and k. Based on L i and L(k), the center coordinates of areas C 1 (i) and C 2 (i) are respectively derived as in which V = |d 2 c − 1 4 d 2 i,k |, and the center coordinates of areas C 2 (i) and C 3 (i) are respectively derived as in which M( ) ∈ {max( ), min( )}. Note that the selection of the above operators (i.e. ∓ and functions {max( ), min( )}) are determined by the relative positions between SN i and SN k, which can be obtained by simple geometry calculations. Meanwhile, note that if the distance between SNs i and k is equal to 2d c , then the aforementioned area, i.e. {C m (i)|m ∈ {1, · · · , 5}} will be merged into one. Finally, set the circular area that has the smallest sum of available storage space from its top n − 2 SNs from {C m (i)|m ∈ {1, · · · , 5}} as C * (i).
Computational complexity analysis: step 2 requires O(N R ) to traverse all SNs in Ω dmax−dc , of which N R represents the average number of SNs in a circular area with a radius of V max × τ − d c .
Step 3 requires O(N r ) to search for the partner SN, in which N r represents the average number of SNs in a circular area with a radius of d c .
Step 4 only involves simple calculations.
Step 5 requires O(N 2 r ) to sort the SNs in each generated circular area C m (i), m ∈ {1, · · · , 5}, and requires O(5) to pick the one with the best performance. Finally, step 7 requires O(N R ) to obtain the optimal SN set from {Ω opt(i) |i ∈ Ω dmax−dc } by comparing the sum of available storage space.
In summary, the computational complexity of the proposed search method is O(N R × (N r + 5 * N 2 r + 5) + N R ), which is considered as practical and highly desirable for the application scenarios under studied in this letter.

B. Solve Sub-Problem sP2
After obtaining the SN set Ω o (t) by executing Algorithm 1, sub-problem sP2 is to get the optimal way-point for the UAV at the t-th time slot with the given location L u (t − 1), so that the maximum data throughput between the UAV and SNs in Ω o (t) can be obtained. The problem sP2 is formulated as sP2 : max By substituting (4) into the above problem, the objective function can be expressed as Obviously, function (15) is convex with respect to d 2 i,u (t), instead of the next way-point of the UAV (i.e. L u (t)). Meanwhile, due to the fact that the first order Taylor expansion of a convex function is the global under-estimator at any point, thus we expand r i (t) = W log 2 (1 + α i p σ 2 i (H 2 +d 2 u,i (t)) ) in (15) with an initial point d 2 i,ui (t) = ||L i − L ui (t)|| 2 in terms of the first-order Taylor expansion as r i (t) = r i (t, L ui (t)) + r i (t, L ui (t)) * ∆d(t) + ε, in which ), , Here, if we substitute (16) without item ε into original problem, sP2 will be transformed to a convex optimization problem (denoted as sP2*) with respect to L u (t) due to the fact that other items are all constants with the initial point d i,ui (t). Therefore, problem sP2* can be solved by using general convex optimization methods.
Meanwhile, to reduce the impact of ignoring ε when transforming sP2 to sP2*, an intuitive method is to choose an initial coordinate L ui (t) which is very likely to be close to the optimal coordinate L u (t), so that the ε = ∞ n=2 r n i (t,dui(t)) n! ∆d(t) n can be negligible as ∆d(t) tends to 0. Therefore, considering the scheduled SN set Ω o (t) obtained by Algorithm. 1, one can initialize L ui (t) as the mean of the coordinates of SNs in Ω o (t), which ensures communication distances from the UAV to all SNs in Ω o (t) are balanced and shorter than d c .

IV. EXTENSION IN PROBABILISTIC LOS CHANNELS
Here we discuss how to further extend this letter to probabilistic LoS channel scenarios. In this case, the waypoint of the UAV in time slot t should be updated to q u (t) = [L u (t), L uz (t)] T ∈ R 3×1 in a given 3-D space. Then, as designed in [13], [14], the LoS probability at each time slot t can be modeled as a function of the UAV-SN elevation angle, which can be expressed in the form of where θ k,t denotes the angel between the UAV and SN k in time slot t, which is given by where α and β are modeling parameters to be specified. Then, the corresponding NLoS probability can be obtained by In this case, the large-scale channel power gain between the UAV and SN k in the time slot t, including both the path loss and shadowing, can be modeled as where denote the channel power gains in LoS and NLoS cases, respectively. Meanwhile, d k,t can be calculated as Considering that the goal of this letter is to design a data collection strategy for the UAV-assisted WSN to minimize the data loss rate η due to storage exhaustion during the entire data collection task. So, in each time slot t − 1, the UAV will schedule a set of SNs (denoted as Ω o (t)) which owns the smallest sum of available storage space under the constraints of communication resources (i.e. (6)), and then searches for the next optimal waypoint (i.e. q u (t)) of the UAV to maximize the data transmission throughput based on the probability LoS channel model. Obviously, the former issue can still be solved by the Algorithm 1 we designed, while the latter issue can be modeled as the following optimization problem. where The problem P2 can be solved by methods proposed in [13], [14].

V. NUMERICAL RESULTS
A simulated UAV-assisted WSN application scenario has been developed to validate the performances of the proposed strategy UTS. It is assumed that there is only one UAV with a fixed altitude to ground H = 20m and its maximal speed V max = 30m/s, and a WSN with |Ω all | = 200 SNs being uniformly and randomly distributed in a square AoI. For each SN deployed in AoI, the initial length of the data queue follows a Poisson distribution with λ = 10 kbits, and the storage capacity is B = 30 kbits. The parameters of the communication model are configured as follows, i.e., bandwidth W = 5MHz, noise power δ 2 = −100dBm, transmission power p = 0.05W, the reference channel power gain α i follows a random uniform distribution with range [-55dB, -50dB], the average efficient communication radius d c = 10m, the number of wireless resources n = 4, the duration of each time slot is τ = 1s where τ c = 0.1s, and the maximum flight time of the UAV T e = 600s.
For benchmarking, a Random Flight Strategy (RFS) and a Greedy Flight Strategy (GFS) have been introduced in the simulations, in which RFS chooses the next way-point randomly, and then sets the adjacent SNs with the smallest sum of available storage space as the communication objects. In contrast, GFS chooses the location of the SN with the smallest available storage space within the feasible moving area as its next way-point, and then selects the communication SNs with the same criterion as RFS. The performance comparisons between the strategies mainly focus on the following three aspects, namely sampling rate ( Fig. 2 (a)), scene scale ( Fig. 2  (b)), and running time (Fig. 2 (c)).
As shown in the above simulation results, the proposed UTS shows significant advantages in reducing data loss in multiple scenarios. Compared with RFS without the user scheduling process and GFS with the single-SN greedy scheduling, UTS considers searching for a group of SNs with the greatest overall data loss risk for communication scheduling before performing data collection tasks, which is especially important for a large-scale WSN. In addition, UTS also optimizes each waypoint in the trajectory to increase the data throughput with the scheduled SNs, which leads to the throughput of the UTS at each waypoint being nearly 3 times of those in the other two strategies. In this way, more storage space of involved SNs is released and the efficiency of data collection mission can also be guaranteed.

VI. CONCLUSION
In this letter, a UAV-assisted data collection strategy has been proposed, which takes into account the user scheduling and trajectory planning of the UAV to reduce the data loss rate in the large-scale WSN. Simulation results have shown that networks with the proposed strategy can yield higher performance than those with other strategies under tests.