Jamming-aware optimization for UAV trajectory design and internet of things devices clustering

In [7], anti-jamming trajectory design for the UAV under a jamming attack in Wireless Sensor Networks is investigated. The goal is to maximize the average data rate for the ground users in the presence of a malicious ground jammer. In [8], the authors proposed a scheme for UAV communication with ground users in the presence of multiple jammers. The aims of this scheme are optimizing the UAV trajectory and maximizing the energy efficiency of the UAV. UAV relaying schemes are proposed in [6] and [9] to relay the data from the On Board Unit (OBU) in vehicular ad-hoc networks (VANETs) when the designated Roadside Unit (RSU) is under a jamming attack. The UAV relays the message of the user to another RSU not suffering from the jamming attack.

In [10], the authors proposed an UAV-aided anti-jamming framework for cellular networks. The UAV uses reinforcement learning methods to choose the relay policy for users in the cellular networks. To resist the jamming attack, the UAV relays the traffic of the jammed base station to a backup base station. In [11], UAV path planning and the signal-to-interference-plus-noise ratio (SINR) is maximized when a jammer exists in the network. A Bayesian Stackelberg game is proposed in [12] to mitigate the problem of jamming in UAV communication networks. The work considers the incomplete information regarding the co-channel interference in the UAV communication networks. The jammer acts as the leader and the users function as followers in the proposed game. Accordingly, the users select their transmission power policies such that the effect of the jammer is mitigated.

The authors in [13] considered an anti-jamming communication in a UAV swarm in the presence of jamming. The UAV exploits the degree-of-freedom in frequency, motion, antenna and spatial domain to optimize its data reception, while a jammer is attacking the network. In [14] and [15], the authors proposed a joint optimization for the transmission power and the UAV trajectory in anti-jamming communication networks. A Stackelberg framework and Q-learning-based anti-jamming scheme are utilized to solve the optimization problems.

In [16], the authors proposed a fair data collection scheme for intelligent transportation systems. The storage devices are clustered, then the UAV collects the data from the cluster heads. For fair data collection, the UAV controls its speed such that it slows down when the cluster size is large. This helps in providing the cluster head of the large cluster more time for sending its larger data messages. In [17], UAV is utilized to collect data from sensor clusters and charge the sensors using wireless energy transfer technology. The sensors are located in harsh terrains, and the objective for the UAV is to maximize the data collection from the sensors.

The authors in [18] considered the problem of data collection for large scale wireless sensor networks. They proposed to cluster the sensors into clusters, where the forwarding rule within the cluster is based on the value of the information and the power of the nodes. The value of the information concept means that the value of the event is highest when it first happens, where the value of information decreases with time. The UAV is used to collect the data from the cluster heads. The objective is to maximize the value of information of the collected data. In [19], an energy-efficient and fast data collection scheme is designed to gather sensing information from sensors. A UAV collects data from sensors located in hilly terrains, where it acts as a data mule. Energy-efficient distributed clustering algorithm is utilized to cluster the sensors, then a modified tabu search algorithm is used to optimize the UAV position. In [20], the authors proposed to use a UAV for data collection in dense wireless sensor networks. Projection-based Compressive Data Gathering is used to reduce the number of transmissions and energy consumptions. The sensor nodes are clustered and the forwarding tree is built such that the sum of total transmission power and the UAV flight distance is minimized.

In [21], the work studied the data ferrying problem using a UAV to deliver the collected data between separate and unconnected points. The goal is to improve delay-tolerant communication while collecting and ferrying data. It is shown that considering the radio propagation in designing the routing path of the UAV can reduce the delay significantly. On the other hand, transmission mode between two nodes can be direct, through a relaying process or by data ferrying. Accordingly, the authors in [22] optimize the selection of transmission mode based on several parameters, such as the distance between the nodes and the tolerable delay. Moreover, the work in [23] integrates nonparametric learning with path planning in UAV-based data ferrying communications. Radio environment is observed and the UAV improves the communication model over time. This results in a more accurate plan for the UAV path.

Data ferrying mechanism is proposed in [24] to collect data from isolated location and offloads within a certain tolerable delay. The problem is formulated, where the objective is to minimize the distance traveled by the UAV. In [4], an energy-efficient scheme for collecting and forwarding the collected data from isolated remote fields is proposed. Each field is associated with a UAV that conveys the sensing data of that field and delivers it to a sink node. The delivery of the data can be directly from the field to the sink node or through cooperative UAVs. The objective is to maximize the minimum battery level among all UAVs to prolong the lifetime of the network.

The authors in [25] proposed to utilize a UAV for data collection from IoT devices in the presence of a jammer. Intelligent Reflecting Surface (IRS) is employed to assist in improving the signal reception by the UAV. The proposed scheme aims in enhancing energy efficiency by jointly optimizing the beamforming of the RIS, power allocation, scheduling and planning the UAV trajectory. The authors in [26] studied how to maximize the lifetime of a UAV-assisted network when there are multiple sources of interference. The UAV collects data from distributed sensors in presence of jamming, where the authors assume that the clusters of the IoT devices and their CHs are given. In [27], a data collection framework is proposed that utilizes multiple UAVs in wireless sensor networks. Given the locations of the sensor nodes, these nodes are clustered based on k-means clustering and the CHs are selected. Then, the number of used UAVs and their trajectories such that the flight time is minimized.

A UAV-based data collection system for sensors located in a straight line is introduced in [28]. The speed of the UAV and the sensors’ transmission powers is optimized. The objective is to minimize the total flight time. Another UAV-based data collection system for collection data from ground sensors is introduced in [29]. The goal is to minimize the mission time while considering the UAV trajectory, velocity, altitude and link scheduling. Similarly, mission completion time is minimized for a UAV-based data collection system introduced in [30]. In addition, the UAV charges the ground terminals using wireless power transfer. Accordingly, the proposed work considered optimizing the UAV trajectory, transmission scheduling and charging. In [31], data collection from time-constrained IoT devices using a UAV is investigated. The objective is to maximize the number of served IoT devices within a certain period of time restricted by a deadline.

Many anti-jamming techniques are investigated in the literature, e.g., in [5], including the use of UAVs to mitigate the jamming attacks. Although the UAV provides an effective method to alleviate the jamming attack, the UAV may suffer from the scalability issue when it is required to collect data from a large number of IoT devices. By jointly designating a jamming aware IoT devices clustering and UAV path planning, the UAV can serve more IoT devices under a jamming attack in a shorter time. To the best of our knowledge, there is no existing work investigating a jointly jamming-aware IoT device clustering and UAV path planning.

Table 1 presents a comparison between the most relevant works and our proposed scheme. Our goal is to minimize the time required for data collection from the IoT devices using a UAV and in the presence of a jammer. Instead of visiting all IoT devices to collect data from them, the IoT devices are clustered and only the CHs are visited by the UAV. Interestingly, we proposed a jamming-aware clustering such that the UAV can collect the data from the CHs successfully even with a presence of the jammer. Therefore, we compared our work with the other works based on the consideration for (1) Data Collection (DC), (2) Flight Time Minimization (FTM), (3) Jamming-aware system (JA) and (4) Clustering (C). To the best of our knowledge, this is the first work aiming at minimizing the UAV mission completion time for data collection process in the presence of a jamming attack by optimizing the UAV routing trajectory and jamming-aware clustering. As shown in Table 1, none of the existing related works jointly considered minimizing the UAV flight time while optimizing its path during data collection and considering a jamming-aware clustering. Most of the existing-related works either focus on data collection in the presence of a jammer without considering the clustering to minimize the mission completion time or focus on data collection but without the consideration for the jamming attack. We compare our joint clustering and UAV path planning with other works such as optimizing the trajectory and clustering separately and with no clustering. The results presented in the Simulation Results Section (Section “Simulation results”) show that our proposed work reduces the required time by the UAV to complete its data collection task.

With adoption of the UAV data collection in the IoT, jamming attacks for the communication between on ground IoT devices and a flying UAV is a critical challenge. Without mitigating this challenge, utilizing the UAV in data collection can be an inefficient and unreliable method. Therefore, we propose in this paper a jamming-aware scheme for clustering the IoT devices and routing the UAV such that the UAV collects the data from all CHs successfully. Accordingly, the UAV can withstand a jamming attack from a ground jammer in the IoT.

The contributions of our paper can be summarized as follows:The remainder of this paper is organized as follows. We introduce the system model in Section “System model”. Then, we formulate our problem mathematically in Section “Problem formulation”. Section “Problem solution” presents our proposed Algorithm for solving the optimization problem. Then, we show the simulation results in Section “Simulation results” and conclude our paper in Section “Conclusion”.

To model the uplink transmission from the CHs and the jammer to the UAV, we utilize a probabilistic ground-to-air channel model [33]. This model provides the LoS probability based on the elevation angle. We assume that the UAV hovers over the location of the CH during the data collection process, i.e., the elevation angle between a transmitting CH and the receiving UAV is \(90^\circ \). Accordingly, the LoS probabilities for the uplink channel between the UAV and a CH located at location i or the jammer located at location J are given, respectively, by [33]andwhere q and v are parameters related to the environment and \(\theta _{iJ}\) is the elevation angle between the jammer located at location J and the UAV when it is above location i. Therefore, the probabilities for the uplink channel between a CH located at location i or the jammer located at location J being NLoS are given, respectively, as follows:and

We assumed that there is a hostile jammer trying to jam the uplink communications between the CH and the UAV, as shown in Fig. 1. Accordingly, the CHs are selected such that the received signal by the UAV from the CHs withstand the noise generated by the jammer. Hence, the Signal-to-Interference-plus-Noise Ratio (SINR) of the signal received by the UAV should be greater than a threshold \(\overline{\gamma }\). Moreover, we assume that the location of the jammer can be derived using a jammer localization method with a high accuracy [32].

The uplink communication between a ground terminal (an IoT device or the jammer) and the UAV can be Line-of-Sight (LoS) or Non-Line-of-Sight (NLoS). Hence, we have four possibilities for the status of the links between the CH and the UAV and the link between the jammer and the UAV: Based on these four possibilities, we calculate the SINR for the signal transmitted by a CH located at location i and received by the UAV, respectively, as follows [7]:where \(\gamma _{i}^{q}\) is the SINR for the signal sent by a CH located at location i and received by the UAV, and \(q \in \{\text {NN, Nl, LN, LL} \}\). N and L refer to the NLoS and LoS channels between a ground terminal (CH or the jammer) and the UAV, respectively. \(\beta _0\) is the channel power at 1 m reference distance, \(P^{IoT}\) and \(P^J \) are the transmission powers of the IoT device and the jammer, respectively, \(\alpha _L\) and \(\alpha _N\) are average path loss exponents for LoS and NLoS links, respectively, \(\sigma ^2\) is the power of the additive white Gaussian noise (AWGN) at the receiver, u is NLoS additional signal attenuation factor, and \(\hat{d_{iJ}}\) is the distance between the UAV and the jammer when the UAV is hovering above location i.

When the UAV is hovering over location i, the expected SINR for the signal transmitted by a CH located at location i, is given by

The UAV is required to collect data from all IoT devices and relay it to a communication network when it arrives at its final location \(\beta \). Instead of collecting data directly from each single IoT device, the IoT devices are clustered, and the UAV collects data directly from the CHs. This process helps the UAV to expedite its data collection process. The CHs form clusters with radius not greater than \(\epsilon \) meter. Within each cluster, the IoT devices forward their data to their CH. The CH receives data from its cluster members and stores it along with its data. Then, it waits for the UAV to arrive and relays the whole data of the cluster to the UAV.

We assume that the IoT devices of each cluster communicate with their CH using different channels than the uplink channel used by the CHs to communicate with the UAV. Hence, there is no interference between the communication within the clusters and the uplink communication between the CHs and the UAV. We consider an unfriendly jammer that generates noise to the uplink transmission (ground-to-air communication to the UAV) of some surrounding CHs. Hence, the clusters should be formed such that the CHs’ uplink transmission to the UAV withstand the noise generated by the jammer.

For a successful reception of the message set by a CH located at location i to the UAV, the expected SINR of the signal received by the UAV should be greater than or equal to a threshold \(\overline{\gamma }\), that isOnce the condition above is satisfied, the UAV can successfully receive the message from the CH. Accordingly, the cluster is formed such that the SINR of the signal transmitted by the CH to the UAV satisfies the condition in Eq. (10).

In Fig. 2,  3,  4,  5,  6 and Fig. 7, we present two scenarios for IoT devices clustering and UAV routing. These scenarios illustrate how a jamming attack affects IoT devices clustering and the UAV’s trajectory. Figure 2 shows IoT devices distributed over an area of \(x^{max} \; m \times y^{max} \; m\) meters, where Table 2 describes the symbols used in the figures of this section. First, we cluster the IoT devices and assign a CH to each cluster as shown in Fig. 3. Then, the UAV visits only the CHs to collect data and flies to its final location as depicted in Fig. 4.

Assume that a jammer starts jamming the uplink channels dedicated for transmissions from CHs to the UAV as shown in Fig. 5. Three CHs are affected by the jamming signals (located inside the blue highlighted shade), where the jammer generates noise that affects the successful reception by the UAV. Therefore, the IoT devices are re-clustered, as presented in Fig. 6, such that the UAV can successfully receive the messages sent by all CHs. Finally, Fig. 7 presents the flying trajectory of the UAV, which avoids the areas under the jamming attack. By comparing Figs. 4 and  7, it is shown that the flying trajectory under a jamming attack results in a longer UAV routing path.

We assume that the UAV is located initially at location \(\alpha \). All CHs’ data are ready to be collected before the UAV starts its mission. Hence, the UAV should start flying in the first time slot to finish its task as soon as possible, that iswhere \(L_{ij}(t)\) is a binary variable that equals one only when the UAV moves from location i to location j during slot t. After finishing the data collection from all CHs, the UAV flies to its final location \(\beta \). Accordingly, the UAV should go to the final location \(\beta \) during a certain time slot, that isNote that the UAV should not go back to its initial location nor fly to another location after reaching the final location. Therefore, we haveandDuring each time slot, the UAV either flies between two points or stays at the same location. HenceGiven that the UAV has visited location \(i \in N \backslash \beta \), it leaves that location only once and does not come back to it again. Therefore, we use the following constrain:When the UAV is visiting an intermediate node j during slot t, where \(j \in N \backslash (\alpha \cup \beta )\), it leaves location j to another location during the next time slot. HenceThe max distance that the UAV can travel between two locations i and j is restricted by the following constraint:where \(d_{ij}\) is the distance between location i and location j.

Let \(\hat{L_i}(t)\) be a binary variable that equals to one only when the UAV reached location i by the end of time slot t, that isThe UAV can receive a message successfully from a CH located at location i only when the expected SINR of the received signal is not below a certain threshold \(\overline{\gamma }\). Therefore, we add the following constraint:where \(T_i^{tx}(t)\) is a binary variable that equals one only when the message sent by the CH located at location i during slot t is received successfully by the UAV.

The goals of the clustering constraints are: (1) Minimizing the points that the UAV needs to visit by visiting only the CHs and (2) Clustering the IoT devices such that the transmitted messages from the CHs to the UAV are successfully received by the UAV. Let \(U_i^c\) and \(H_i^c\) be binary variables, where \(U_i^c=1\) and \(H_i^c=1\) only when the IoT device located at location i belongs to cluster c and the CH of cluster c, respectively. Since each IoT device can be a member to only one cluster, we add the following constraint:Within each cluster, only one IoT device can be a CH. Hence, we haveIn addition, The IoT device cannot be a CH for more than one cluster, that isWhen there is an IoT device belonging to a cluster, there must be a CH for that cluster. Therefore, we include this constraint to our formulation:Moreover, the distance from each IoT device within a certain cluster to its CH should not be greater than the cluster radius \(\epsilon \). Accordingly, we haveIf an IoT device is selected to be a CH for a cluster, this device must transmit its cluster’s messages to the UAV during a time slot, that isNote that the variable \(T_h^{tx}(t)\) is related to the SINR threshold \(\overline{\gamma }\) as shown in constraint (38). Therefore, \(T_h^{tx}(t) = 0\) when \(\overline{\gamma } \le \mathbb {E}[\gamma _{h}]\). Consequently, \(\sum \nolimits _{c \in C} H_h^c = 0\) when \(T_h^{tx}(t) = 0\). Accordingly, the IoT device h will not be a CH transmitting to the UAV when \(\overline{\gamma } \le \mathbb {E}[\gamma _{h}]\). We conclude that the clustering method used is jamming-aware and mitigates the effects of the jamming attack.

Our objective is to minimize the arrival time of the UAV to its final location \(\beta \). Accordingly, we minimize the index of the time slot in which the UAV arrives at its final location. In other words, we minimize the maximum time slot index t for the variable \(\hat{L_{\beta }}(t)\) when \(\hat{L_{\beta }}(t)=1\). Hence, the mathematical model for our optimization problem is given bysubject to:The Objective function and constraint (28) ensure that we minimize the maximum time slot index t in which \(\hat{L_{\beta }}(t)=1\). Note that \(\hat{L_{\beta }}(t)=1\) when the UAV reaches its final location \(\beta \). The remaining constraints are described in subsections 3.1 and 3.2.

The formulated problem in subsection 3.3 is nonlinear due to the product of \(U_i^c\) and \(H_h^c\) in constraint (44). To facilitate solving this problem, we linearize it by linearizing constraint (44). Therefore, we introduce a new binary variable \(\eta (i,h,c)\), where \(\eta (i,h,c) = U_i^c H_h^c\). Therefore, we add the following three constraints to make \(\eta (i,h,c) = U_i^c H_h^c\):andThen, we replace constraint (44) byAccordingly, we reformulate the optimization problem in subsection 3.3 by the following:subject to:

Constraints (28–43), (45)

A Genetic Algorithm (GA) [35] is a metaheuristic search algorithm that is inspired by natural selection and genetics. The algorithm starts by initial feasible population, iteratively selects the best solutions and performs some GA operations to discover better solutions in the next iterations until a stopping condition is reached. The main elements of GAs are described as follows [35]:A simple genetic algorithm includes the following main steps [35]:

In this subsection, we propose a jamming-aware genetic algorithm for UAV trajectory planning and IoT device clustering. Based on the location of the jammer, the IoT devices are clustered and the CHs are selected such that the UAV is able to receive the messages from the CHs when the UAV hovers above them. Our proposed algorithm is based on the concepts of the genetic algorithms. The population consists of popSize chromosomes, and each chromosome is represented by a vector of IoT devices’ indices with a certain order.

Figure 8 shows the flowchart of the JA-RC algorithm (Algorithm 1). First, the JA-RC algorithm starts by initializing a random population of size popSize chromosomes. Then, certain genes in each chromosome are selected to be CHs and each CH is associated with certain IoT devices located within the distance \(\epsilon \). After selecting the CHs for each chromosome, the cost of each chromosome is calculated using a fitness function, Eq. (57), that we will describe below. Then, we set the cost of the chromosome to infinity when we find that one or more CHs in the chromosome suffer from harmful interference. This step aims in eliminating the selection of the solution that is not feasible. After that, we find the chromosome that has the lowest cost and set it to be the best current solution. Finally, Algorithm 2 is used to perform selection, crossover and mutation operations. Once the stopping condition is met, Algorithm 1 terminates. Otherwise, Algorithm 1 iterates until the stopping condition is met. After each iteration, Algorithm 1 derives new solutions and tests them to discover new candidate solutions.

Figure 9 shows the flowchart of Algorithm 2 that is used by Algorithm 1 to perform selection, crossover and mutation operations. Algorithm 2 starts by shuffling the population randomly. The goal of this step is to improve the chance of discovering a better solution. Then, each 4 consequent chromosomes in the population is grouped in one group. Consequently, a pair of chromosomes in each group are selected and crossover operations are performed over them. In addition, mutation operations are performed between chromosomes within each group. Finally, we get a new modified population of chromosomes that can be used by Algorithm 1 to discover more solutions.

Let POP be a matrix of size \(popSize \times |I |\), where each row represents a certain chromosome. In addition, the binary matrix POPch of size \(popSize \times |I |\) represent the CHs of each chromosome in the population. In other words, the indices associated with the ones in row p of the matrix POPch represent the CHs when chromosome p is selected.

Let \(\Omega _p\) be a vector containing the cluster heads that the UAV needs to visit in order when chromosome p is selected from the population. To evaluate the solution of each chromosome p, the following Faintness Function FF(p) is used in our algorithm:where \(d_{\alpha \; l_{\Omega _p(1)}}\) is the distance from the initial location of the UAV (\(\alpha \)) to the first CH in the vector \(\Omega _p\), \(d_{l_{\Omega _p(i)} \; l_{\Omega _p(i+1)}}\) is the distance between the \(i^{th}\) CH and the \((i+1)^{th}\) CH in the vector \(\Omega _p\), and \(d_{l_{|\Omega _p |\; \beta } }\) is the distance between the last CH in \(\Omega _p\) and the final location of the UAV (\(\beta \)).

Algorithm 1 shows the required steps of Jamming-Aware UAV Routing and IoT Devices Clustering Algorithm (JA-RC). The maximum number of iterations of Algorithm 1 is MaxIter, and the population size is popSize. First, we initialize the minimum cost, MinCost, among all chromosomes in the population, as shown in step 3. In steps 4–5, the IoT device associated with the first index in chromosome p is selected as a CH for the first cluster. Then, we set \(\overline{r}\) in step 6 to the distance between the first selected CH in chromosome p to the IoT device associated with index 2 of chromosome p. In steps 7–22, we check the remaining IoT devices in chromosome p and decide whether to include the IoT device to an already existing cluster or make it a CH to a new cluster.

In step 8, we calculate the distance, \(\overline{d}\), between the recently selected CH and the \(m^{th}\) IoT device in chromosome p. If the distance \(\overline{d} \le \overline{r}\) and \(\overline{d} \le \epsilon \), then include the \(m^{th}\) IoT device in chromosome p to the recently created cluster. Otherwise, create a new cluster and make the \(m^{th}\) IoT device in chromosome p a CH as shown in steps 12–20. In Step 23, we create a list of CHs for the \(p^{th}\) chromosome, \(\Omega _p\). In steps 24–28, we check the feasibility of the selected solution then calculate the fitness function accordingly. If there is a CH in \(\Omega _p\) such that the UAV cannot successfully receive the message from becuase the jamming interference, then the solution of chromosome p is not feasible and the cost of the solution is \(\infty \), i.e., \(TotalCost(p) = \infty \). Otherwise, TotalCost(p) is calulated based on the fitness function FF(p) defined in Eq. (57).

After deriving the cost of each candidate solution in the population, we find the best solution, BestSolution, among all derived solutions, as shown in steps 30–33. Then, the chromosomes in the population are modified to discover more solutions in the next iterations. We use Algorithm 2 to select chromosomes and perform crossover and mutation operations. Then, Algorithm 1 repeaters its steps 2–34 iteratively to search for a better solution after getting a new generation for the population.

Algorithm 2 shows how we get a new generation of chromosomes. In step 1, the rows (i.e., chromosome) in the population matrix (POP) are shuffled randomly. Then, we divide in step 2 the rows of the POP matrix into groups of four rows, i.e., the number of groups are \(\lceil \frac{popSize}{4} \rceil \). The steps 4–5 shows how we perform order crossover operations [36] on two randomly selected chromosomes in group g. We select two integer numbers a and b randomly such that \(a<b\), then we perform an order crossover operation the genes indexed from index a to index b. The order crossover makes sure that no repeated IoT device indices appear in the child chromosome. We perform order crossover rather than the typical crossover operation to make sure that each chromosome does not contain duplicate elements. When the chromosome contains duplicate IoT device indices, the resulting clustering may miss some IoT devices. Hence, it may provide an infeasible solution.

In steps 6–7, Algorithm 2 performs mutation operations over each group g of chromosomes. The algorithm performs circular shift, element replacement and flipping the elements for the indices between a and b as shown in step 6, 7 and 8, respectively. The fourth line of the group g is kept without a modification. The order crossover and mutation operations are performed over all \(\lceil \frac{popSize}{4} \rceil \) groups to create a new generation of chromosomes. Then Algorithm 1 utilizes the new generation of chromosomes to search for a better solution.