(Near) optimal resource-competitive broadcast with jamming
Seth Lewis Gilbert, Valerie Jean King, Seth Pettie, Ely Porat, Jared Saia, Maxwell Young · 2014
We consider the problem of broadcasting a message from a sender to n ≥ 1 receivers in a time-slotted, single-hop, wireless network with a single communication channel. Sending and listening dominate the energy usage of small wireless devices and this is abstracted as a unit cost per time slot. A jamming adversary exists who can disrupt the channel at unit cost per time slot, and aims to prevent the transmission of the message. Let T be the number of slots jammed by the adversary. Our goal is to design algorithms whose cost is resource-competitive, that is, whose per-device cost is a function, preferably o(T), of the adversary's cost. Devices must work with limited knowledge. The values n, T, and the adversary's jamming strategy are unknown.