Making evildoers pay: Resource-competitive broadcast in sensor networks

Abstract

Consider a time-slotted, single-hop, wireless sensor network consisting of n correct devices and and f·n Byzantine devices where f ≥ 0 is any constant; the Byzantine devices may or may not outnumber the correct ones. There exists a trusted sender Alice who wishes to deliver a message m over a single channel to the correct devices. There is also an evil user Carol who controls the Byzantine devices and uses them to disrupt the communication channel. For a constant k ≥ 2, the correct and Byzantine devices each possess a meager energy budget of O(n 1/k), Alice and Carol each possess a limited budget of Õ;(n 1/k), and sending or listening in a slot incurs unit cost. This setup captures the inherent challenges of guaranteeing communication despite scarce resources and attacks on the network. Given this Alice versus Carol scenario, we ask: Is communication of m feasible and, if so, at what cost? We develop a protocol which, for an arbitrarily small constant ε > 0, ensures that at least (1-ε)n correct devices receive m with high probability. Furthermore, if Carol's devices expend T energy jamming the channel, then Alice and the correct devices each spend only Õ(T 1/(k+1)). In other words, delaying the transmission of m forces a jamming adversary to rapidly deplete its energy supply and, consequently, cease attacks on the network. © 2012 ACM.