Linear iterative strategies to identify and overcome malicious links in wireless networks

S Sundaram, Shai Revzen, G Pappas

Automatica, vol. 48, no. 11, pp. 2894-2901, 2012

Abstract

We consider a network where every node has a value that we wish to disseminate to all other nodes. A certain number of communication links between nodes are allowed to be under the control of an attacker who maliciously chooses the messages carried by these links. We study linear iterative strategies that disseminate information despite such attacks. In such strategies, at each time-step each node in the network broadcasts a value to its neighbors that is a linear combination of its previous value and the values received from its neighbors. As long the number of incoming links to any node and the total number of other nodes with incoming malicious links is no greater than f , we show that linear strategies are almost always resilient to malicious behavior provided that vertex-connectivity of the network is at least 2f + 1. Furthermore, we show that each node can identify the exact set of malicious links that directly enter that node, and can communicate this information to the other nodes via the linear strategy.

BibTeX

@article{sundaram-2011-lis,
  author = {Sundaram, S and Revzen, Shai and Pappas, G},
  title = {Linear iterative strategies to identify and overcome malicious links in wireless networks},
  journal = {Automatica},
  year = {2012},
  volume = {48},
  number = {11},
  month = nov,
  pages = {2894-2901},
  doi = {10.1016/j.automatica.2012.06.072},
}