Jamming-Resilient Message Dissemination in Wireless Networks

This paper initiates the study for the basic primitive of distributed message dissemination in multi-hop wireless networks under a strong adversarial jamming model. Specifically, the message dissemination problem is to deliver a message initiating at a source node to the whole network. An efficient algorithm for message dissemination can be an important building block for solving a variety of high-level network tasks. We consider the hard non-spontaneous wakeup case, where a node only wakes up when it receives a message. Under the realistic SINR model and a strong adversarial jamming model that removes the budget constraint commonly adopted in previous work by the adversary, we present a distributed randomized algorithm that can accomplish message dissemination in $\mathscr{T}(O(D(\log n+\log R)))$ time slots with a high probability performance guarantee, where $\mathscr{T}(U)$ is the number of time slots in the interval from the beginning of the algorithm's execution that contains U unjammed time slots, n is the number of nodes in the network, D is the network diameter, $R$ is the distance with respect to which the network is connected. Our algorithm is shown to be almost asymptotically optimal by lower bound $\Omega(D\log n)$ for non-spontaneous message dissemination in networks without jamming.