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, and
$R$
is the distance with respect to which the network is connected. Our algorithm is shown to be almost asymptotically optimal by the lower bound
$\Omega (D\log n)$
for non-spontaneous message dissemination in networks without jamming.