Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Yes No <s> We study the problem of achieving global broadcast in a radio network where a node can multicast messages to all of its neighbors (that is, nodes within some given distance r), and up to t nodes in any single neighborhood may be corrupted. Previous work assumes that corrupted nodes can neither cause collisions nor spoof addresses of honest nodes. In this work, we eliminate these assumptions and allow each faulty node to cause a (known) bounded number of collisions and spoof the addresses of arbitrary other nodes. We show that the maximum tolerable t in this case is identical to the maximum tolerable t when collisions and address spoofing are not allowed. Thus, by causing collisions and spoofing addresses an adversary may be able to degrade the efficiency of achieving broadcast, but it cannot affect the feasibility of this task. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Yes No <s> Many wireless standards and protocols today, such as WLAN and Bluetooth, operate on similar frequency bands. While this permits an efficient usage of the limited medium capacity, transmissions of nodes running different protocols can interfere. This paper studies how to design node discovery algorithms for wireless multichannel networks which are robust against contending protocols on the shared medium. We pursue a conservative approach and consider a Byzantine adversary who prevents the communication of our protocol on t channels in a worst-case fashion. Our model also captures disruptions controlled by an adversarial jammer . This paper presents algorithms for scenarios where t is not known. The analytical findings are complemented by simulations providing evidence that the proposed protocols perform well in practice. <s> BIB002 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Yes No <s> We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem which we call the Bad Santa problem. Our results on this problem apply for any situation where: (1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and (2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a $\Theta(\sqrt{n})$ expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log ∗ n) times (i.e. in O(log ∗ n) rounds each consisting of the n time slots), then listening to O(log ∗ n) expected number of time slots suffices. We show that this is near optimal. ::: ::: We describe an application of our result to the popular grid model for a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message m, all awake nodes within L ∞ distance r receive m. In this model, up to $t 0, we can achieve an even better energy savings. In particular, if we allow each node to send O(log ∗ n) times, we achieve reliable broadcast with each node sending O(nlog 2|m|+(log ∗ n)|m|) bits and receiving an expected O(nlog 2|m|+(log ∗ n)|m|) bits and, after broadcasting a fingerprint of m, each node is awake for only an expected O(log ∗ n) time slots. Our results compare favorably with previous protocols that required each node to send Θ(|m|) bits, receive Θ(n|m|) bits and be awake for Θ(n) time slots. <s> BIB003
Establish a shared secret after nodes have been deployed in a multi-channel network when the adversary can jam t < C channels. Applies to single-hop networks and the round complexity for establishing a shared key grows as O(nt 3 log n) and so may rapidly increase with the power of the adversary. Meier et al. BIB002 Random, Adaptive, Reactive Examine feasibility and communication complexity of reliable broadcast when both correct and adversarial nodes have a bounded message budget. The demonstrated protocol allows correct nodes to have a smaller budget than that required by the protocol given by Koo et al. BIB001 . Listening costs are not addressed. King et al. BIB003 , BIB003 Byzantine locally-bounded scenario No n/a Look at energy-efficient reliable broadcast. Achieve quadratic improvement in energy efficiency over previous protocols with optimal tolerance, and achieves at least an exponential increase in energy efficiency for t < (1 − )(r/2)(2r − 1). The model used does not incorporate jamming or spoofing, and latency is not fully examined. Alistarh et al.  Reactive Jammer, Byzantine locally-bounded scenario