Jamming attacks for wireless networks have been an active area of research for many years [1]- [6]. The majority of this work focuses on either jamming single communication links or considers a flat network structure. Recent work has considered jammer placement problems that take into account the topology of a wireless network. Ref. [7] places jammers to disrupt network traffic flows, while [8] considers node mobility techniques for jamming of flows and anti-jamming.
In a mesh or ad hoc network, jamming attacks that target individual links may fail because these networks often have a self-healing property because ad hoc routing can be used to reroute traffic around jammed links. Thus, in our previous research [9]- [12], we have focused on jamming attacks that can partition a wireless network into multiple disconnected subnetworks. The problem of jammer placement to partition a wireless is complicated by several facts. First, connectivity is a global property of a wireless network that depends on the topology of the network. Second, the set of wireless links that will be blocked by a jammer is highly sensitive to the particular location of that jammer in Euclidean space. Third, the search space for jammer locations is the entire Euclidean space being considered -for our work, we have constrained the search to the real plane. In light of these issues, in our previous work we have reduced the complexity of finding optimal jammer placements by constraining the potential jammer locations to the locations of nodes in the network being jammed. However, this may make the jammer placement suboptimal and is also not realistic, as in many real scenarios, the jammer locations must be kept secret from the communicators.
In this paper, we develop a technique to find a set of jammer locations when the jammers can be placed at any locations in the real plane. Our approach is based on the observation that it is not necessary to consider many possible jammer locations because they are either:
• suboptimal, because there are better locations that jam a proper superset of the jammed nodes if a jammer were placed at one of those locations, or • redundant, because there are other jammer locations that jam the same set of nodes. The main contributions of this work are: 1) We present two algorithms that find a set of candidate jammer locations (CJLs) in the real plane based on finding minimum covering disks in a depth-first search through the network. 2) We prove that an optimal jammer placement in the CJLs is also optimal among all jammer placements in the real plane, in the sense that no jammer placement in the real plane can achieve a lower cardinality for the objective of partitioning the network to some specified degree.
The network model, jammer model, and jammer placement objective are describe in Section II. In Section III we present two algorithms for finding the CJLs and prove the optimality of the CJLs for the jamming problem we consider. In Section IV, we review algorithms to find optimal or suboptimal jammer placements from a discrete set of locations. The performance of these algorithms is assessed via simulation results in Section V. The paper is concluded in Section VI.
We consider communication networks in the real plane, where the network can be modeled as a simple Euclidean graph G(V, E) with the radios as the vertices V and the communication link as the edges E ⊆ V × V. Each v i ∈ V has an associated location (x i , y i ) ∈ R 2 , and nodes v i and v j share an edge if radios i and j can communicate directly. For convenience, we let the Euclidean distance between two vertices v i and v j with locations (x i , y i ) and (x j , y j ), respectively, be denoted by d E (v i , v j ). This model can be used for a variety of wireless nonfading and fading channel models. For the purposes of this paper, we will consider a protocol model, where
We consider the effect of the placement of jammers on the topology of the communication network. Following our previous work [9], [10], [12], we also use a protocol model for the effect of the jammer, such that there is a jamming radius r j such that any radio at a distance less than or equal to r j of a jammer will be unable to communicate with its neighbors.
The jammer placement problem can be formulated as follows. Let G(V, E) be the network before jammer placement and let
be a set of jammer placements when there are N J jammers. Let H = H(V , E ; G, J ) be the residual network that is left after jammers at positions in J disrupt the communications in the original network G. Then H is specified by its remaining vertices V and edges E , which can be determined from
For the remaining nodes in V , we aim to find a partition
Here, K is the minimum number of disconnected clusters and b i bounds the number of nodes in cluster i. To simplify exposition, we bound the residual cluster cardinalities by
Let J O be the jammer placement set with minimum cardinality that achieves the specified partitioning goal. The generalized jammer placement problem is defined on network G(V, E) and number of cluster K as finding:
An example illustrating jammer placement to partition a network of 100 nodes into two residual subnetworks with fewer than 50 nodes each is shown in Fig. 1. The example network is created as a random geometric graph, with an edge between any two nodes within a fixed communication distance. A node is jammed if it is within the same communication distance of a jammer. Two jammers, located at the center of the large shaded circles, are sufficient to partition this network. The jammers disrupt communication at all of the red/circle nodes, and result in two residual partitions, indicated by blue/square and green/triangle nodes, respectively. For non-trivial networks, problems related to searching for edge/vertex separator are usually N P-Complete or N P-Hard [13], [14] even with strict constraints on network complexity [15]. We also observed such high computational demand in our previous research [10]. In the situation where searching for optimal jammer placement solution is not feasible, we developed a suboptimal searching technique [12] which offers orders of magnitudes speed improvement with close-tooptimal solutions.
As previously described in Section I, not every location in the plane needs to be considered for jammer placement. This motivates us to find a set of candidate jammer locations (CJLs), such that a minimum-cardinality jammer placement over the CJLs will have the same cardinality as a minimumcardinality jammer placement over the entire real plane.
We introduce some notation used in our algorithm. We define an augmented disk d i as a tuple of values d i = ((x i , y i , r i ), v i ), where (x i , y i ) represents the center of a closed disk in the plane, r i represents the radius of the disk, and v i ⊆ V denotes the set of vertices in G that lie within the specified disk. Let D = {d 0 , d 1 , . . .} denote a set of such augmented disks. We define a partial order on the d i by
Extending the notation of [16], let md(v) be the (augmented) closed disk of smallest radius that contains all v i ∈ v;
i.e., md(v) = ((x, y, r), v), where (x, y, r) satisfy
Algorithm 1 uses a depth-first search (DFS) starting from the entire network to find a set of CJLs by finding consecutively smaller subsets of the network. Algorithm 2 also finds a set of CJLs but reduces complexity compared to Algorithm 1 by using a sequence of depth-first searches starting from neighborhoods of the network nodes. In the following, we prove that Algorithm 1 and Algorithm 2 with stopping radius γ = r j find a set of CJLs that are sufficient to find an optimal solution to the problem defined in Section II-B. First,
) and push to S; / * depth-first search * / while S is not empty do v = S.pop(); we introduce some preliminary results. Because of space constraints, proofs are omitted for the results that are simple to prove.
. But the minimum disc containing a set of vertices is determined solely by the vertices on the boundary of the disc [16].
Next we show that if we take any vertex set and create an augmented vertex set by adding the vertex to it that results in the smallest increase in the radius of the enclosing minimum disk, then any other vertex not in the augmented vertex set will not be in the open minimum disk containing the augmented vertex set.
Lemma 1. Let G = (V, E) be a simple Euclidean graph, and v ⊆ V be given. Let
(2)
Proof. Let u satisfy (2), and suppose there is z / ∈ v ∪ {u} such that z ∈ md (v ∪ {u}).
Consider the vertex set w = v ∪ {z}.
If the two disks are the same, then by Lemma 1, z ∈ B(v ∪ u), which contradicts z ∈ md (v ∪ {u}). If the two disks are not the same, then the intersection of the two disks can be contained in a smaller disk [16]. Since by assumption z ∈ md (v ∪ {u}), z must lie in the intersection of the two disks, which means that u was not the solution to (2).
Thus, we conclude that it must be that z / ∈ md (v ∪ {u}).
Lemma 2. Let G = (V, E) be a simple graph, and v ⊆ V be given. Then v will be found at one of the vertices of the DFS tree in Algorithm 1 with stopping radius γ ≤ md(v).
Proof. From the set v, find v. By definition v is within radius md(v).
First we note that if v is on the DFS search tree with stopping radius γ = 0, then v is on the DFS search tree with stopping radius γ ≤ md(v), since the specified stopping radius will only remove vertex sets w that satisfies md(w) < γ.
Let w 0 = v. If w 0 = V, then let i = 1 and: 1)
Step 1: Find a node u satisfying (2), and let w i = w i-1 ∪ {u}. By Lemma 1, at each step u ∈ B(w). 2) Step 2: If w i = V, stop. Otherwise, let i = i + 1 and return to step 1. Let n denote the value of i at the end of the iterations. Note that w i and w i-1 differ by one vertex that is on the boundary of w i . Thus w n , w n-1 , . . . , w 0 is a sequence of vertices on the DFS tree from the root at w n = V to w 0 = v. Theorem 1. Let G = (V, E) be a simple Euclidean graph, and v ⊆ V be given. If v can be covered by a jammer with jamming radius r j , then the DFS tree found by Algorithm 1 with γ = r j contains at least one disk d = ((x, y, r), w) such that v ⊆ w. Thus, the nodes in v can be jammed by placing at jammer at (x, y), the center of the disk d that is on the DFS tree found by Algorithm 1.
Proof. By Lemma 2, v is on the DFS tree with stopping radius γ ≤ md(v). As in Lemma 2, label the vertex sets from v to the root of the DFS tree as w 0 = v, w 1 , . . . , w n = V.
If | md(V)| < r j , then md(V) satisfies the theorem. Otherwise, |w 0 | ≤ |w 1 | ≤ . . . ≤ |w n |. Thus there must be some set w j such that |w j | ≤ r j but |w j+1 | > r j . By Lemma 2, this w j+1 will be found by the DFS search with γ = r j , and w j will also be found by the DFS since the DFS search continues to the first level where |w i | ≤ γ. This w j satisfies the theorem. Lemma 3. If v ⊆ V ∈ G can be enclosed by a circle with radius r and centered at (x, y), then for ∀v ∈ v, v ⊆ N 2r v Proof. Let (x, y) denote the center of the circle with radius r that contains v. Then ∀v ∈ v, d E (v i , (x, y)) ≤ r. By the triangle inequality,
Then by definition, v ⊆ N 2r v for ∀v ∈ v. Theorem 2. Let G = (V, E) be a simple graph, and v ⊆ V be given. If v can be covered by a jammer with jamming radius r j , then ∃d = ((x, y, r), w) with v ⊆ w such that d is on the DFS tree found by Algorithm 2 with γ = r j . Thus, the nodes in v can be jammed by placing at jammer at (x, y). Theorem 3. Let j be a set of jamming locations in the real plane, j i ∈ R 2 . Then for each location, j i ∈ j, there is at least one alternative location k i corresponding to one of the augmented disks found by either Algorithm 1 or Algorithm 2, such that the jammer placed at k i will jam a superset of the nodes jammed by a jammer placed at j i . Thus, the centers of the augmented disks found by Algorithm 1 or Algorithm 2 are sufficient to find an jamming strategy of minimum cardinality.
Proof. For each jamming location j i , find the set of vertices v i that would be jammed. By applying Algorithm 1 or Algorithm 2, Theorem 1 and Theorem 2 guarantee that the DFS trees created will contain at least one vertex set that is a superset of v i . Chose any such vertex set w and call the minimum disk containing that set md(w) = ((x w , y w , r w ), w). Thus, the jammer at j i can be replaced with a jammer at (x w , y w ) with no loss of optimality. Since this can be done for every j i ∈ j, any solution j with j i ∈ R 2 can be replaced with a solution of equal cardinality where the locations correspond to the centers of minimum disks on a DFS search tree created by either Algorithm 1 or Algorithm 2. Thus these algorithms produce a candidate set of points from which can be found a solution of minimum cardinality that jams a superset of the nodes of the solution j.
In our previous work [10], [12], we have developed optimal and suboptimal approaches to find a minimum cardinality jammer placement over a constrained set. These formulations naturally extend to using the centers of the D found by Algorithm 1 instead of the locations of the network nodes. We briefly review those algorithms here.
For network G(V, E) and D, we introduce the jamming graph G J (V J , E J ), in which
Note that V D is the set of the central locations of all CJLs in D, and E J is the edge set in which an edge between nodes i and k indicates that a jammer placed at location of node i will block all reception at node placed at location k, and vice versa. Let A (J) denote the adjacency matrix for G J , with A (J) i,k = 1 if there is an edge connecting nodes i and k and A (J) i,k = 0, otherwise. We say that an edge (link) is jammed if at least one of the nodes connected to the link is jammed. Let N = |V| and N D = |V D |.Note that, in jamming graph G J , nodes in V are labeled from 1 to N and nodes in V D are labeled from N + 1 to N + N D .
As we have shown in Theorem 3, placing jammers solely on locations included in V D is sufficient for finding the jammer placement solution with minimum cardinality.
We first introduce some notation that is used in the optimal approach. Jammers are restricted to be placed at the locations of one of the nodes or CJLs. Let x be the binary vector with length |V D |, which indicates whether a jammer should be placed at location of CJL. And let y (k) be the binary vector with length N , where k ∈ {0, . . . , K} with K is the number of clusters. Let y (0) denote a special cluster that includes all nodes being jammed by at least one jammer in J . Hence y
Then in [10], the optimal formulation of jammer placement problem with CJL is formulated as the binary integer linear program (ILP):
x ≥ 1 (4)
i -
i -y
x i , y
Fig. 2. Distributions of ratio between the size of augmented disk set and network order Fig. 3. Average size of integer programming under both formulations comparing to network order and order of G J
The size of our optimal ILP formulations is (K + 1) × N + |V D |. The distribution of the ratio between |V D | and |V| for a set of 1000 random network topologies (see Section V for details) is shown in Fig. 2 as a violin plot. For most networks with order up to 300, the number of CJLs doesn't go beyond 2N , which doesn't affect the size of ILP as significantly as K when K ≥ 2.
Solving a large integer programming problem can be computationally intensive. So, we also present results for a suboptimal jammer placement algorithm developed in [12] that
• finds an edge separator E S that partitions G into K clusters via multi-resolution graph cut, and • finds the optimal jamming set (OJS), which is the minimum cardinality jammer placement that jams at least one vertex of each edge in the edge separator, via an ILP of size much smaller than that considered in Section IV-A.
Readers are referred to [12] for details of this approach.
The average sizes (in terms of the number of variables) for the integer programs used in both the optimal and suboptimal formulations are compared in Fig. 3 for 1000 random network topologies (again, see Section V). For reference, the cardinalities of the original network and the CJLs are shown. The average ILP size for the suboptimal approach is much smaller than for the optimal approach and has a much lower rate of growth. The average ILP size for the suboptimal approach is even smaller than the network order for networks with over 100 nodes.
In this section, we compare the performance and running time of jammer placement algorithms using the CJLs with that of jammer placement at only the network nodes' locations. All simulations are programmed in Python with the network analysis module NetworkX and the Gurobi integer linear programming solver. The simulations were executed on computers with a 3.1GHz Intel Core i7 CPU with 8MB cache and 16GB RAM running Ubuntu 16.04 LTS. All figures show the performance averaged over 1000 different network topologies.
The simulation results are all for graphs generated using the Random Geometric Graph (RGG):
Each simulation topology is generated by randomly placing nodes in the region [0, n 100 ) × [0, n 100 ) and then creating edges for all pairs of vertices u and v if they are within the communication radius, d E (u, v) ≤ r c . This graph models a scenario in which:
• Radios are homogeneous with identical spatial density, equal transmit power, omnidirectional antennas, and equal noise figure. • The channel obeys an exponential path-loss model.
• The jamming radius is equal to the communication radius (r j = r c = 0.15). For all the simulations, the objective is to partition the network into 4 disconnected subnetworks, with the cardinality of each subnetwork constrained to be no more than one-fourth the original network order.
We first consider the effectiveness of using the CJLs for jammer placement instead of using the locations of the network nodes, V. As shown in Fig. 4, by using the CJLs as the set of possible jammer locations, the average number of jammers required to achieve the network partition objective is reduced for both optimal and suboptimal search algorithms for finding a minimum cardinality jammer placement. More details of the relative performance are also shown in Table I; the performance of the optimal solver is not listed for networks of over 100 nodes because of the extremely long times required to find such solutions. The results in Table I (top of next page) show that the average number of jammers required is reduced by up to 21%, with typical improvements around 12% to 14% for the suboptimal solver. The performance of the suboptimal solver with the CJLs is only slightly worse than the performance of the optimal solver without the CJLs. The average time needed to find the CJLs for networks with different sizes is shown in Table II. The average time to solve for the CJLs is less than 30 seconds for networks with up to 100 nodes, but an average of approximately 17 minutes is needed for networks with 500 nodes. The total time to solve the jammer placement problem will depend on the time to find the CJLs plus the time to determine the optimal jammer placements over the CJLs, which is larger than the original problem of placing the jammers at the locations of the communicators.
The suboptimal approaches to solving the jammer placement problem are capable of reducing the execution time by orders of magnitudes [12]. This reduction in execution time still holds with the CJLs. Table III shows that for networks with up to 500 nodes, a jammer placement solution can still be found within a few milliseconds, with or without CJLs, which is almost negligible compared to the time needed to find the CJLs or solve the ILP optimally.
Table IV compares the average execution times of solving the original (without the CJLs) ILP optimally with that of searching for the CJLs. The results show that as the network size grows, the time needed to optimally solve the ILP grows much faster than the time to find the CJLs. In combination with the performance results above, these results suggest that finding the CJLs and then using the suboptimal solver for the larger jammer placement problem may offer a good tradeoff between performance and complexity.
In this paper, we developed an approach to finding a minimum cardinality jammer placement to partition a wireless network when jammers can be placed anywhere in the real plane. Our approach is based on finding a set of candidate jammer locations (CJLs) that are a sufficient search space for a minimum cardinality jammer placement. We develop two depth-first search algorithms to find the CJLs, and we evaluate the effects on performance and running time of using the CJLs in comparison to our previous approach of constraining jammers to be placed at the locations of the network nodes. The results show that by extending the search space to the CJLs, the average number of jammers required to partition a wireless network is decreased by approximately 10% to 20%, at the expense of an increase in complexity that is primarily attributable to the time to find the CJLs.