{'fraction_non_alphanumeric': 0.02777936880691907, 'fraction_numerical': 0.0048112721232602094, 'mean_word_length': 4.412275263484191, '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': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Lifetime Maximization for UAV-assisted Data Gathering Networks in the Presence of Jamming

Deployment of unmanned aerial vehicles (UAVs) is recently getting significant attention due to a variety of practical use cases, such as surveillance, data gathering, and commodity delivery. Since UAVs are powered by batteries, energy efficient communication is of paramount importance. In this paper, we investigate the problem of lifetime maximization of a UAV-assisted network in the presence of multiple sources of interference, where the UAVs are deployed to collect data from a set of wireless sensors. We demonstrate that the placement of the UAVs play a key role in prolonging the lifetime of the network since the required transmission powers of the UAVs are closely related to their locations in space. In the proposed scenario, the UAVs transmit the gathered data to a primary UAV called \textit{leader}, which is in charge of forwarding the data to the base station (BS) via a backhaul UAV network. We deploy tools from spectral graph theory to tackle the problem due to its high non-convexity. Simulation results demonstrate that our proposed method can significantly improve the lifetime of the UAV network.


I. INTRODUCTION
The utilization of unmanned aerial vehicles (UAVs) is a new concept with a vast majority of applications, such as video monitoring and surveillance, package delivery, and help and rescue in disasters. In wireless networks, the communication capability of UAVs was exploited to use them as aerial base stations and relay nodes [1]- [3]. Recently, deployment of UAVs for data collection from a set of battery limited users has attracted a lot of interest (e.g., [4]- [6]).
In a wireless network, upon having nodes with power constraints, such as mobile users or low power wireless sensors, the efficient utilization of their batteries and prolonging their lifetime are important concerns. The usage of UAVs to increase the time duration of uplink transmissions of wireless devices is a relatively new topic of study. In [4], serving ground nodes via a single UAV acting as an aerial base station (BS) is considered, where the problem of optimizing the UAV placement to maximize the lifetime of wireless devices is studied. In this work, the lifetime is defined as the sum of time durations of uplink transmissions of the ground nodes. A similar problem is studied in [5], where the network comprises a set of ground users and a set of UAVs, and optimize the UAVs' positions and the users' transmission powers are optimized to maximize the minimum lifetime of the ground users. There exists another related body of literature, where the sensing protocol and UAV trajectories are designed to prolong the lifetime of the sensors (see [7] and references therein). None of the above works considers the network lifetime maximization problem involving the battery consumption of the UAVs, where the UAVs act as relays gathering information from ground sensors.
There exists another line of works devoted to efficient leader selection for the UAV swarms and the ground wireless devices. In [8], using a UAV swarm for the scenario of high-quality forest mapping is investigated, where an adaptive and reliable network structure is desirable to maintain swarm connectivity and communicability. To this end, a leader election algorithm is applied to a set of micro UAVs, where the leader gathers information from the swarm, leads the swarm to its destination, and responsible for communicating to a BS. Also, effective usage of leader UAVs for the purpose of collision avoidance of UAV swarms is investigated in [9], where each leader UAV is regarded as the controller and flies independently, and the others follow the leader UAV. In [10], effective cluster head election in UAV-assisted data collection in a wireless sensor network is studied. To save energies and extending the network lifetime, the network is partitioned into groups, each of which that has a leader to communicate communicates with the corresponding UAV. Based on these works, we propose a more comprehensive model, in which the existence of a set of sensors and multiple terrestrial leaders and a set of UAVs with a UAV leader is considered simultaneously.
The novelty and contributions of this work can be summarized as follows. First, we consider a new system model for data collection from a set of terrestrial sensors, where sensors are clustered to multiple groups each associated with a cluster head and a set of UAVs are deployed with a UAV leader for information gathering form the sensors. The leader UAV (with a higher battery capacity and transmission power compared to the rest of UAVs) is in charge of data forwarding to a base station (BS) through backhaul network. Second, we formulate and solve the problem of obtaining the best positions of the collecting UAVs and the UAV leader so as to maximize the lifetime of the network while explicitly considering the existence of multiple sources of interference in the environment.It is among the first work addressing the network lifetime maximization problem considering multiple jammers, and thus also contributes to the literature on UAV-assisted network design in the presence of jammers in the environment (e.g., [11]- [16]).

II. SYSTEM MODEL
We consider a scenario for UAV-assisted data collection, in which there are N UAVs in the sky aiming at collecting information from N clusters of terrestrial low power sensors. In each cluster, the sensors gather the required information and forward it to a primary node, which we call cluster head (CH). The aim of the CH is to collect information from the sensors in the same cluster and transmit it to the leader through UAVs. The main goal of the UAV network is to collect the data of the CHs and transmit it to a base station (BS). In practice, it is preferred that all the UAVs transmit their data to a high power UAV called leader that relays the data to the main BS via a backhaul network. The deployment of the leader is desired from the energy efficiency perspective since it results in prolonging the lifetime of the network.
In a detrimental scenario, the sensors and the UAVs coexist with multiple jammers. The jammers' goal is to generate strong interference to degrade the communication quality of the links from the CHs to the UAVs as well as the links from UAVs to the leader. Nevertheless, the mobility feature of the UAVs allows them to reconfigure their locations and find their optimal 3D locations to avoid the interference caused by the jammer. In this work, we aim to optimize the location of the leader and also those of the data collecting UAVs to improve the lifetime of the network. In our work, we assume that the leader is a high altitude platform (HAP) which has sufficient power and can accommodate the transmission requirement from the data gathering UAVs [17]. Since we assume that the leader is a HAP, there should be a constraint on the altitude of the leader to prevent it from coming to the lower corridor in 3D space (see Fig. 1 for more details). We propose a two step optimization method aiming to prolonging the lifetime of the network. In the first step, we jointly optimize the locations of the data gathering UAVs and the leader to prolong the network operation lifetime. In the second step, given the location of the leader, the locations of the backhaul UAVs are optimized to maximize the lifetime of the backhaul network to deliver the data from the leader to the BS. Another interesting problem is to optimize the positions of the jammers, e.g., [18], which we leave as a future work.
We denote the location of terrestrial jammer j ∈ J by , and the location of UAV n ∈ N by x n = (x n , y n , h n ). In practice, the air to air (A2A) link, i.e., the inter-UAV link, is dominated by the line of sight (LoS) component, while the ground to air (G2A) link, i.e., the link between the CHs and the UAVs, can be considered as either LoS or non line of sight (NLoS). Here, we consider the worst case scenario in which the G2A link is assumed to be NLoS. The inverse of the pathloss coefficients of the link between two nodes p and q is given by [19]: where α 1 and α 2 are the path-loss exponents for LoS and NLoS cases and K o = 4πf c /c, for which f c denotes the carrier frequency and c denotes the speed of light. Also, µ LoS and µ NLoS denote the corresponding attenuation factors [20].

III. PROBLEM FORMULATION FOR UAV LIFETIME MAXIMIZATION
We consider data transmission using the FDMA setting, where the UAVs utilize non-overlapping bandwidths to transmit data to the leader. For each UAV or CH p, 1 ≤ p ≤ N , let B p = B/N denote the designated bandwidth. Consequently, the data rate from node p to node q is given by: where P pq is the transmit power required at node p to satisfy the transmission rate R pq at node q, σ 2 is the variance of the Gaussian noise, and d pq denotes the Euclidean distance between the two indexed nodes and P j , ∀j ∈ J is the jammer transmission power. Let E p denote the battery energy of node p ∈ N ∪ M. We assume that E L denotes the battery energy of the leader, where the battery energy of the leader is much larger than that of the regular UAVs/CHs, i.e., E L E p , ∀p. To maintain a certain quality of communication, each UAV/CH should be able to satisfy the minimum data rate requirement R for the two-hop data transmission between the CHs and the leader through the UAVs. The leader, on the other hand, should be able to satisfy the transmission data rate of at least N × R to the backhaul network. The lifetime of the link between two nodes p and q while delivering the minimum requirement rate R pq is given by: where P c p is a constant power consumption for each UAV/CH which is related to circuit power [21]. Considering (2), the transmission power P pq for node p to satisfy the minimum rate R at node q is given by: Since the leader is a high power HAP UAV, we assume that the bottleneck of the lifetime of the UAV network is determined by the data gathering UAVs and CHs. We define the lifetime of the network as the time duration that all of the links between the nodes can deliver a minimum data rate of R. We formulate the optimization of the lifetime of the network as follows: where x L is the location of the leader. In the above optimization, the objective function aims to maximize the minimum lifetime of the links between the nodes, which is equivalent to maximizing the lifetime of the network. Constraint (5a) ensures that the leader moves in the upper corridor and constraint (5b) guarantees that the UAVs observe a minimum safety distance d min with each other to guarantee the safety and proper flight requirements. The optimization is over both the locations of the regular UAVs and the leader. As can be seen, the location of the leader can have a high impact on the lifetime of the network. It can be verified that the objective function of optimization problem (5) is non-convex. The optimization in (5) is with respect to the locations of the data gathering UAVs and the leader, which is assumed as the first stage in our scheme. The second stage, which is optimization of the locations of the backhaul UAVs can be done similarly in a multi-hop setting, where the leader is fixed and acts as the source and the BS is the destination. In such a case, the leader acts as source and the BS serves as the destination, while the backhaul UAVs serve as the relays.

IV. UAV POSITIONING USING SPECTRAL GRAPH THEORY
The optimization problem (5) is a highly non-convex maxmin problem. To address this problem, we deploy the Cheeger constant of the given network, which is a well-known metric that measures the bottleneck of the network. We define a directed flow graph G = (N , E), where E denotes the set of available edges in the network that correspond to the communications between the nodes. We assume that there exists an edge between node p and node q, where a pq denotes the weight of the edge connecting node p to node q, which is defined as the lifetime of their corresponding link: (6) The generalized adjacency matrix of the network is defined as A = [a pq ]. Let us define the matrix D = diag{β 1 , ..., β N } as the generalized degree matrix of the UAV network with β p = q,q =p a pq . The Laplacian matrix of the network graph is defined as L = D − A. The weighted Cheeger constant is defined as: where the |S| W = i∈S w i is the weighted cardinality with w i ≥ 0 the weight assigned to node i, S is a subset of nodes andS denotes its complement. Also, L W denotes the weighted Laplacian defined as: Note that increasing the Cheeger constant of the network results in decreasing the bottleneck of the network, which is the aim of the optimization problem (5). However, in general, instead of obtaining the Cheeger constant, the algebraic connectivity λ 2 is computed as it is closely related to the Cheeger constant and is also simpler to compute. It is shown in [22] that the following weighted Cheeger's inequality holds where δ max is the maximum node degree, and w min = min i w i . In practice, since computing the Cheeger constant is difficult, we try to maximize λ 2 (L W ) as an alternative according to 9, which is given by: In order to maximize the weighted algebraic connectivity λ 2 (L W ), we move each UAV along the spatial gradient of λ 2 (L W ). Given the instantaneous position of UAV i, its spatial gradient along x-axis is given by: where x f is the Fiedler vector (i.e., the eigenvector corresponding to the second smallest eigenvalue), x f p is the p th component of x f , and p ∼ q means that nodes p and q are connected. To compute (11), we need to obtain weight with respect to x p , which is a transmitter node, one can get: Similarly, the derivative with respect to the position of the receiver node q is given by: For coordinates y and z, the moving directions can be obtained similarly, which are omitted due to space limitations.

V. SIMULATION RESULTS
In this section, we present a set of numerical simulations to evaluate the performance of the proposed method. The simulation parameters are given in Table 1. In Fig. 2, the 3D trajectories and final optimal locations (indicated by the corresponding markers) of the UAVs and the leader are shown, where the first stage optimization for the locations of the data collecting UAVs and the leader is considered. The hyperplane of z = 70 m separates the upper corridor and the lower corridor. In Fig. 2(a), the location of the leader is fixed in the upper corridor and only the locations of the UAVs are optimized in order to improve the lifetime of the network. In Fig. 2(b), the joint optimization of the locations of the UAVs and the leader is considered, while the moving space of the leader is constrained to the upper corridor. Finally, in Fig. 2(c), the locations of the UAVs and the leader are jointly optimized while the leader can move freely in the 3D space. This case can improve the overall performance in terms of lifetime maximization, while it violates the feasibility constraint. We consider this case as a potential upper bound for the performance of the network. In all of the scenarios, the locations of the data gathering UAVs is obtained using the proposed method. In the two latter cases, the black lines in the figures represent the trajectory of the leader. In Fig. 3, the lifetime of the network for the aforementioned cases is compared with a baseline method in which the UAVs are placed on the middle plane between the ground and the upper corridor. The locations of the CHs and jammers are chosen randomly in the area of xy plane [0,100]×[-10,40]. The results shown are averaged over 1000 realizations with 95% confidence intervals. For the baseline method, the altitude of all the UAVs is 35m, while the x and y positions of them are generated randomly. The location of the leader is assumed at the middle of the smallest rectangle in xy plane including all the nodes with altitude 70m. It can be seen that the proposed method can improve the lifetime of the network considerably.
The optimization of the locations of the UAVs in the backhaul network is also important to efficiently deliver the gathered information from the leader UAV to the BS. Given the location of the leader, one can obtain the locations of the backhaul UAVs using a similar approach. This scenario is depicted in Fig. 4, where we optimized the positions of the leader, the data gathering UAVs, and the backhaul UAVs.

VI. CONCLUSION AND FUTURE WORKS
In this paper, we investigated the problem of lifetime maximization of a UAV-assisted data gathering network, where UAV nodes collect data from a set of terrestrial low power wireless sensor nodes in the presence of sources of interference. In the proposed scenario, the UAVs transmit all the collected data to a UAV leader, which is in charge of forwarding the data to the main base station via a backhaul UAV network. We formulated the lifetime maximization of the UAV network as an optimization problem, which turns out to be a highly nonconvex max-min problem. To tackle the problem, we deployed Cheeger constant and algebraic connectivity from the spectral graph theory. Through numerical simulations, we studied the performance of our proposed method. There are many aspects of this problem that deserve further investigation including sensor clustering, cluster head selection, and UAV grouping.