A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks

In this paper we consider the problem of designing a medium access control (MAC) protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming. The wireless network consists of a set of honest and reliable nodes that are within the transmission range of each other. In addition to these nodes there is all adversary. The adversary may know the protocol and its entire history and use this knowledge to jam the wireless channel at will at any time. It is allowed to jam it (1 - epsilon)-fraction of the time steps, for an arbitrary constant epsilon > 0, but it has to make a jamming decision before it knows the actions of the nodes at the current step. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant throughput for the non-jammed time steps under any adversarial strategy above. We also show that our protocol is very energy efficient and that it call be extended to obtain a robust and efficient protocol for leader election and the fair use of the wireless channel.