An optimal jamming strategy to partition a wireless network

Wireless communication systems are susceptible to jamming attacks, and a large body of research has investigated jamming and anti-jamming strategies for single communication links. However, attacking single links may not be sufficient to disrupt communications in a network, which may route traffic around jammed links. To date, there has been little research on jamming to disrupt an entire network. In this paper, we consider the problem of determining how to efficiently place jammers to minimize the number of jammers needed to disrupt a network by partitioning it into a specified number of disconnected subnetworks, each of which is limited in size. We formulate this problem as an optimal clustering problem on a graph and show that the clustering problem can be solved exactly as a binary integer linear program (ILP). Since the complexity of the ILP increases rapidly with the size of the network, we also solve the ILP via harmony search, a meta-heuristic algorithm. Harmony search offers the ability to tradeoff between complexity and performance. In the scenarios where comparison between the two algorithms is feasible, the harmony search provides close-to-optimal performance with a much lower time complexity.