Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> Broadcasting is a process of transmitting a message held in one node of a communication network to all other nodes. Links of the network are subject to randomly and independently distributed faults with probability0 <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> Over the past decade, mobile computing and wireless communication have become increasingly important drivers of many new computing applications. The field of wireless sensor networks particularly focuses on applications involving autonomous use of compute, sensing, and wireless communication devices for both scientific and commercial purposes. This paper examines the research decisions and design tradeoffs that arise when applying wireless peer-to-peer networking techniques in a mobile sensor network designed to support wildlife tracking for biology research.The ZebraNet system includes custom tracking collars (nodes) carried by animals under study across a large, wild area; the collars operate as a peer-to-peer network to deliver logged data back to researchers. The collars include global positioning system (GPS), Flash memory, wireless transceivers, and a small CPU; essentially each node is a small, wireless computing device. Since there is no cellular service or broadcast communication covering the region where animals are studied, ad hoc, peer-to-peer routing is needed. Although numerous ad hoc protocols exist, additional challenges arise because the researchers themselves are mobile and thus there is no fixed base station towards which to aim data. Overall, our goal is to use the least energy, storage, and other resources necessary to maintain a reliable system with a very high `data homing' success rate. We plan to deploy a 30-node ZebraNet system at the Mpala Research Centre in central Kenya. More broadly, we believe that the domain-centric protocols and energy tradeoffs presented here for ZebraNet will have general applicability in other wireless and sensor applications. <s> BIB002 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> Sensor networks are designed especially for deployment in adverse and non-accessible areas without a fixed infrastructure. Therefore, energy conservation plays a crucial role for these networks. We propose to utilize solar power in wireless sensor networks, establishing a topology where, changing over time, some nodes can receive and transmit packets without consuming the limited battery resources. We propose and evaluate two protocols that perform solar-aware routing. The presented simulation results show that both protocols provide significant energy savings when utilizing solar power. The paper shows that incorporating the solar status of nodes in the routing decision is feasible and results in reduced overall battery consumption. <s> BIB003 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> We consider the fault-tolerant consensus problem in wireless ad hoc networks with crash-prone nodes. We develop consensus algorithms for single-hop environments where the nodes are located within broadcast range of each other. Our algorithms tolerate highly unpredictable wireless communication, in which messages may be lost due to collisions, electromagnetic interference, or other anomalies. Accordingly, each node may receive a different set of messages in the same round. In order to minimize collisions, we design adaptive algorithms that attempt to minimize the broadcast contention. To cope with unreliable communication, we augment the nodes with collision detectors and present a new classification of collision detectors in terms of accuracy and completeness, based on practical realities. We show exactly in which cases consensus can be solved, and thus determine the requirements for a useful collision detector.We validate the feasibility of our algorithms, and the underlying wireless model, with simulations based on a realistic 802.11 MAC layer implementation and a detailed radio propagation model. We analyze the performance of our algorithms under varying sizes and densities of deployment and varying MAC layer parameters. We use our single-hop consensus algorithms as the basis for solving consensus in a multi-hop network, demonstrating the resilience of our algorithms to a challenging and noisy environment. <s> BIB004 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> Wireless networks are built upon a shared medium that makes it easy for adversaries to launch jamming-style attacks. These attacks can be easily accomplished by an adversary emitting radio frequency signals that do not follow an underlying MAC protocol. Jamming attacks can severely interfere with the normal operation of wireless networks and, consequently, mechanisms are needed that can cope with jamming attacks. In this paper, we examine radio interference attacks from both sides of the issue: first, we study the problem of conducting radio interference attacks on wireless networks, and second we examine the critical issue of diagnosing the presence of jamming attacks. Specifically, we propose four different jamming attack models that can be used by an adversary to disable the operation of a wireless network, and evaluate their effectiveness in terms of how each method affects the ability of a wireless node to send and receive packets. We then discuss different measurements that serve as the basis for detecting a jamming attack, and explore scenarios where each measurement by itself is not enough to reliably classify the presence of a jamming attack. In particular, we observe that signal strength and carrier sensing time are unable to conclusively detect the presence of a jammer. Further, we observe that although by using packet delivery ratio we may differentiate between congested and jammed scenarios, we are nonetheless unable to conclude whether poor link utility is due to jamming or the mobility of nodes. The fact that no single measurement is sufficient for reliably classifying the presence of a jammer is an important observation, and necessitates the development of enhanced detection schemes that can remove ambiguity when detecting a jammer. To address this need, we propose two enhanced detection protocols that employ consistency checking. The first scheme employs signal strength measurements as a reactive consistency check for poor packet delivery ratios, while the second scheme employs location information to serve as the consistency check. Throughout our discussions, we examine the feasibility and effectiveness of jamming attacks and detection schemes using the MICA2 Mote platform. <s> BIB005 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> How efficiently can a malicious device disrupt communication in a wireless network? Imagine a basic game involving two honest players, Alice and Bob, who want to exchange information, and an adversary, Collin, who can disrupt communication using a limited budget of β broadcasts. How long can Collin delay Alice and Bob from communicating? In fact, the trials and tribulations of Alice and Bob capture the fundamental difficulty shared by several n–player problems, including reliable broadcast, leader election, static k–selection, and t–resilient consensus. We provide round complexity lower bounds—and (nearly) tight upper bounds—for each of those problems. These results imply bounds on adversarial efficiency, which we analyze in terms of jamming gain and disruption–free complexity. <s> BIB006 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> Wireless sensor networks are built upon a shared medium that makes it easy for adversaries to conduct radio interference, or jamming, attacks that effectively cause a denial of service of either transmission or reception functionalities. These attacks can easily be accomplished by an adversary by either bypassing MAC-layer protocols or emitting a radio signal targeted at jamming a particular channel. In this article we survey different jamming attacks that may be employed against a sensor network. In order to cope with the problem of jamming, we discuss a two-phase strategy involving the diagnosis of the attack, followed by a suitable defense strategy. We highlight the challenges associated with detecting jamming. To cope with jamming, we propose two different but complementary approaches. One approach is to simply retreat from the interferer which may be accomplished by either spectral evasion (channel surfing) or spatial evasion (spatial retreats). The second approach aims to compete more actively with the interferer by adjusting resources, such as power levels and communication coding, to achieve communication in the presence of the jammer. <s> BIB007 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <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> BIB008 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> This paper discusses hardware design principles for long-term solar-powered wireless sensor networks. We argue that the assumptions and principles appropriate for long-term operation from primary cells are quite different from the solar power case with its abundant energy and regular charging cycles. We present data from a long-term deployment that illustrates the use of solar energy and rechargeable batteries to achieve 24x7 operation for over two years, since March 2005. <s> BIB009 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> Fault-tolerant broadcasting in the message passing and radio models is considered under a probabilistic failure model. At each step, the transmitter of each node may fail with fixed constant probability p<1, and failures are independent. Both node-omission and malicious transmission failures are studied. Our goal is to establish conditions on feasibility and to estimate the (synchronous) time complexity of almost-safe broadcasting (i.e., broadcasting which is correct with probability at least 1-1/n for n-node graphs and for sufficiently large n) under these scenarios. If only node-omission failures are assumed, almost-safe broadcasting is feasible for any p<1, in both communication models. For malicious transmission failures, almost-safe broadcasting in the message passing model is feasible iff p<1/2, and in the radio model it is feasible iff p<(1-p)^@D^+^1, where @D is the maximum degree of the network. For the time complexity of almost-safe broadcasting, a number of upper and lower bounds are given in the various models. <s> BIB010 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> We consider the problem of reliable broadcast in a wireless network in which nodes are prone to failure. Each node can fail independently with probability p. Failures are permanent. The primary focus is on Byzantine failures, but we also handle crash-stop failures. We consider two network models: a regular grid, and a random network. Our necessary and sufficient conditions for the Byzantine failure model indicate that p should be less than frac12, and the critical node degree is Theta(dmin+(lnn/ln(1/2p))+ln(1/2(1-p))) (where dmin is the minimum node degree associated with a non-empty neighborhood, and is a small constant). For a random network we prove that, for failure probability less than frac12, the critical average degree for reliable broadcast is O(lnn/frac12-p+frac12ln(1/2(1-p))). We briefly discuss the issue of crash-stop failures for which we have results that improve upon previously existing results for this model, when p approaches 0. We also identify an interesting similarity in the structure of various known results in the literature pertaining to a set of related problems in the realm of connectivity and reliable broadcast. <s> BIB011 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> Reliable broadcast can be a very useful primitive for many distributed applications, especially in the context of sensoractuator networks. Recently, the issue of reliable broadcast has been addressed in the context of the radio network model that is characterized by a shared channel, and where a transmission is heard by all nodes within the sender’s neighborhood. This basic defining feature of the radio network model can be termed as the reliable local broadcast assumption. However, in actuality, wireless networks do not exhibit such perfect and predictable behavior. Thus any attempt at distributed protocol design for multi-hop wireless networks based on the idealized radio network model requires the availability of a reliable local broadcast primitive that can provide guarantees of such idealized behavior. We present a simple proof-of-concept approach toward the implementation of a reliable local broadcast primitive with probabilistic guarantees, with the intent to highlight the potential for lightweight scalable solutions to achieve probabilistic reliable local broadcast in a wireless network. <s> BIB012 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> Time synchronization is critical in sensor networks at many layers of their design. It enables better duty-cycling of the radio, accurate and secure localization, beamforming, and other collaborative signal processing tasks. These benefits make time-synchronization protocols a prime target of malicious adversaries who want to disrupt the normal operation of a sensor network. In this article, we analyze attacks on existing time synchronization protocols for wireless sensor networks and we propose a secure time synchronization toolbox to counter these attacks. This toolbox includes protocols for secure pairwise and group synchronization of nodes that either lie in the neighborhood of each other or are separated by multiple hops. We provide an in-depth analysis of the security and the energy overhead of the proposed protocols. The efficiency of these protocols has been tested through an experimental study on Mica2 motes. <s> BIB013 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> In this paper, we study the performance of the IEEE 802.11 MAC protocol under a range of jammers that covers both channel-oblivious and channel-aware jamming. We study two channel-oblivious jammers: a periodic jammer that jams deterministically at a specified rate, and a memoryless jammer whose signals arrive according to a Poisson process. We also develop new models for channel-aware jamming, including a reactive jammer that only jams non-colliding transmissions and an omniscient jammer that optimally adjusts its strategy according to current states of the participating nodes. Our study comprises of a theoretical analysis of the saturation throughput of 802.11 under jamming, an extensive simulation study, and a testbed to conduct real world experimentation of jamming IEEE 802.11 using GNU Radio and USRP platform. In our theoretical analysis, we use a discrete-time Markov chain analysis to derive formulae for the saturation throughput of IEEE 802.11 under memoryless, reactive and omniscient jamming. One of our key results is a characterization of optimal omniscient jamming that establishes a lower bound on the saturation throughput of 802.11 under arbitrary jammer attacks. We validate the theoretical analysis by means of Qualnet simulations. Finally, we measure the real-world performance of periodic and memoryless jammers using our GNU radio jammer prototype. <s> BIB014 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> In this paper, we study the wireless synchronization problem which requires devices activated at different times on a congested single-hop radio network to synchronize their round numbering. We assume a collection of n synchronous devices with access to a shared band of the radio spectrum, divided into F narrowband frequencies. We assume that the communication medium suffers from unpredictable, perhaps even malicious interference, which we model by an adversary that can disrupt up to t frequencies per round. Devices begin executing in different rounds and the exact number of participants is not known in advance. We first prove a lower bound, demonstrating that at least Ω(log2n/(F-t)loglogn + Ft/F-t logn) rounds are needed to synchronize. We then describe two algorithms. The first algorithm almost matches the lower bound, yielding a running time of O(F/F - t log2n + Ft/F - t logn) rounds. The second algorithm is adaptive, terminating in O(t′ log3n) rounds in good executions, that is, when the devices begin executing at the same time, and there are never more than t′ frequencies disrupted in any given round, for some t′ <s> BIB015 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> One threat in wireless multi-hop networks is jamming the wireless channel. Jamming is easy to implement but nevertheless can have severe impact on the performance of the network. To study the impact of different jamming attacks as well as different detection approaches simulative evaluation is performed for scalability and reproducibility reasons. However, realistic propagation modeling in the simulator is often neglected. In this paper, we describe our integration of jamming attacks into the new realistic IEEE802.11 MAC and physical layer ofns-2. Based on this we evaluate different detection metrics: RSSI standard deviation, carrier sensing time, and expected packet delivery rate. In contrast to the related work thresholds for the metrics are dynamically and adaptively parametrized. In contrast to other studies that do not consider realistic MAC and physical models in our evaluation the carrier sensing time with dynamic thresholds shows best results. <s> BIB016 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> This paper presents a simple local medium access control protocol, called JADE, for multi-hop wireless networks with a single channel that is provably robust against adaptive adversarial jamming. The wireless network is modeled as a unit disk graph on a set of nodes distributed arbitrarily in the plane. In addition to these nodes, there are adversarial jammers that know the protocol and its entire history and that are allowed to jam the wireless channel at any node for an arbitrary (1 - e)-fraction of the time steps, where 0 < e < 1 is an arbitrary constant. We assume that the nodes cannot distinguish between jammed transmissions and collisions of regular messages. Nevertheless, we show that JADE achieves an asymptotically optimal throughput if there is a sufficiently dense distribution of nodes. <s> BIB017 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> This paper deals with broadcasting in a network with t-locally bounded Byzantine faults. One of the simplest broadcasting algorithms under Byzantine failures is referred to as a certified propagation algorithm (CPA), which is the only algorithm we know that does not use any global knowledge of the network topology. Hence, it is worth focusing on a graph-theoretic parameter such that CPA will work correctly. Using the theory of maximum adjacency (MA) ordering, a new graph-theoretic parameter for CPA is proposed. Within a factor of two, this parameter approximates the largest t such that CPA works for t-locally bounded Byzantine faults. <s> BIB018 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> We consider message-efficient broadcast tolerating Byzantine faults in a multi-hop wireless sensor network. Assuming a grid network where all nodes have a communication range of $r$, and a single neighborhood contains at most $t$ dishonest and collision-capable (bad) nodes, each with a message budget $m_f$, we investigate the minimum message budget $m$ that each honest (good) node must have in order to achieve reliable broadcast. We consider three cases: (1) $m_f$ is known in advance and $m$ is homogeneous among all good nodes, (2) $m_f$ is known in advance and $m$ is heterogeneous among good nodes, (3) $m_f$ is unknown. For the first two cases, we present possibility results and broadcast protocols that have message costs within twice the lower bound. For the third case, we present a coding scheme that helps verify the integrity of messages at a receiving node without using any cryptographic techniques. This code leads to a {\em reactive local broadcast} primitive that has probabilistic reliability guarantees. Combined with a previously proposed scheme, it results in a broadcast protocol for $t <s> BIB019 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <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> BIB020 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> In this project, we explore the possibility of deploying networked sensors on the Ocean's surface, to monitor depth and temperature, as well as other valuable environmental parameters. Sea depth monitoring is a critical task to ensure the safe operation of harbors. Traditional schemes largely rely on labor-intensive work and expensive hardware. We present a new solution for measuring the sea depth with Restricted Floating Sensors. To address the problem of node localization on the changeable sea environment, we propose Perpendicular Intersection (PI), a novel mobile-assisted localization scheme. In the OceanSense project, we propose the concept of passive diagnosis as well as the PAD approach which is both lightweight and adaptive to network dynamics. The OceanSense system has been working for over 16 months and provides large amounts of valuable data about the sea. <s> BIB021 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Summary of Results and Discussion <s> Imagine that Alice wants to send a message m to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is capable of blocking this channel. Furthermore, there is a cost of S dollars to send on the channel, L dollars to listen on the channel and J to block the channel. How much will Alice and Bob need to spend in order to guarantee transmission of m? This problem abstracts many types of conflict in information networks including: jamming attacks in wireless networks and distributed denial-of-service (DDoS) attacks on the Internet, where the costs to Alice, Bob and Carol represent an expenditure of energy or network resources. The problem allows us to quantitatively analyze the economics of information exchange in an adversarial setting and ask: Is communication cheaper than censorship? We answer this question in the affirmative by showing that it is significantly more costly for Carol to block communication of m than for Alice to communicate it to Bob. Specifically, if S, L and J are fixed constants, and Carol spends a total of B dollars trying to block m, then Alice and Bob must spend only O(Bφ - 1 + 1)=O(B.62+1) dollars in expectation to transmit m, where φ = (1 + √5)/2 is the golden ratio. Surprisingly, this result holds even if (1) B is unknown to both Alice and Bob; (2) Carol knows the algorithms of Alice and Bob, but not their random bits; and (3) Carol has total knowledge of past actions of both players. Finally, we apply our work to two problems: (1) DoS attacks in wireless sensor networks and (2) application-level DDoS attacks in a wired client-server scenario. Our applications show how our results can provide an additional tool in mitigating such attacks. <s> BIB022
To begin, all such models seem to agree on the use of a synchronized and discrete notion of time. Transmissions occur in fixed length time slots and all deivces must typically agree on the beginning and ending of such slots. However, in the context of real-world deployments, it is far from clear whether this property will hold true. Gilbert et al. BIB006 go some distance in addressing the problem where nodes may activate without a notion of a common start time. On the other hand, clock synchronization schemes have been proposed, even in adversarial settings BIB015 , BIB013 , and so this provides some justification for a synchronization assumption. The ability of nodes to detect collisions appears to have a clear effect on the feasibility of certain tasks. For instance, in a single-channel network, the unforgeability of silence assumption introduced by Gilbert et al. BIB006 , and used again by King et al. BIB022 , seems necessary in order to achieve communication between two parties. However, in multi-channel networks, so long as t < C, it seems that several fundamental communication tasks are feasible without the need for collision detection. It is also important to note that the issue of whether or not to assume collision detecion is not a simple binary feature of these models. For example, in the work by Dolev et al.  , collision detection is not assumed; however, when a collision does occur, it is assumed that all transmissions are lost and the receiver hears nothing. This is in contrast to the more challenging model where the adversary can decide which message is delivered upon a collision, which might be the case if we wish to account for the capture effect. Moreover, other notions regarding the accuracy of collision detectors have been examined, along with their impact on the consensus problem, by Chockler et al. BIB004 . With regards to the type of adversary modeled, we can argue that the reactive adversary aligns well with reality. For starters, RSSI requries negligible energy and can be executed several times within a typically-sized time slot. Therefore, it is reasonable to assume a determined malcontent can detect activity in real-time and then decide to jam. Indeed, reactive adversaries pose a serious threat as their effectiveness has been clearly demonstrated BIB005 , BIB016 , BIB014 , BIB007 and typically many models make this worst case assumption on the power of the adversary. Furthermore, although it is often not explicitly stated, most results that tolerate a reactive adversary are also able to tolerate an adaptive adversary. Given this state of affairs, it seems that future models should strive to obtain results in this context. In discussing potential future work, it is important to keep in mind that the study of adversarial interference in sensor networks is fast-moving; exciting and surprising results are sure to emerge. However, from the surveyed works above, we can recognize several aspects that deserve attention. For starters, a logical step that seems absent in many of the surveyed works is an extension to multi-hop networks. Technology permitting, sensor networks of considerable size may be deployed at which point a complete-graph will no longer be an accurate model of communication. The work of Richa et al. BIB017 demonstrates that, while a multi-hop extension may not require a radically new protocol, the corresponding analysis can be challenging and require new techniques. Many protocols we surveyed have tended to neglect receivestate costs and, instead, have focused on message complexity. Are there ways to make existing protocols more energy efficient? Conversely, are there limits (lower bounds) on the energy efficiency of protocols for certain fundamental problems such as reliable broadcast, consensus, leader election and various types of gossiping? On the other hand, with regards to energy efficiency, it is important to keep in mind that this concern is motivated by current technology. For example, there has been a significant amount of work done on sensor network devices that can harvest solar energy in order to replenish their respective energy supplies BIB003 , BIB009 . To date, theoretical models and the algorithmic implications of such technology have not been fully explored. The adversarial models we have surveyed here treat interference in a fairly simplistic fashion where the success or failure of communication depends solely on the actions of the adversary. The range of interference is also simplified in that these models consider communication between a pair of nodes in isolation. Of course, such an approach is employed Demonstrates an -gossip protocol in a multi-channel network. Protocol can be modified to tolerate Byzantine players. Analysis restricted to deterministic oblivious algorithms and single-hop networks. The value of t, or an upper bound on t, seems necessary for the protocol to function. Table II summarizes key aspects and the main findings of the models examined in this section. There is a clear progression of results in this area and we take some time to discuss these now as well as discuss possible future research directions. As mentioned in Section II-D, the work on reliable broadcast can be categorized by the fault model adopted: the probabilistic scenario or the locally-bounded scenario. Starting with the probabilistic scenario, we see initial work with single-hop networks by Berman BIB001 with transient failures, then work by Pelc and Peleg BIB010 (in tree topologies) with permanent Byzantine faults, and then finally the transition to multi-hop networks under the grid model by Bhandari and Vaidya BIB011 . The first two works share similarities in the propagation of the message via groups of devices for p < 1/2 and correctness is proved, in part, by using Chernof bounds. Curiously, this has been a technique adopted by several Byzantine fault-tolerant peer-to-peer systems, also under the probabilistic scenario. This is an example of a technique that spans both the wireless and wired domains of ad-hoc networks and we refer the interested reader to the excellent survey paper by Urdaneta et al.  . The third work is also closely related; while it does not rely as explicitly on groups of devices, such sets do exist and correctness again relies, in part, on Chernoff bounds, with a focus in the analysis on n → ∞. The body of work on the locally-bounded scenario is larger and primarily centers about the grid model, although arbitrary topologies are considered by Pelc and Peleg  and Ichimura and Shigeno BIB018 . We can see that initial work focuses on feasibility; specifically, establishing upper and lower bounds on t for which reliable broadcast can be achieved. Subsequently, the aspects of jamming, communication complexity, latency, and energy efficiency are addressed. In each of these cases, we see progress being made in tackling increasingly difficult adversarial models. The initial work of Koo et al. BIB008 shows that reliable broadcast is feasible with optimal tolerance so long as the instances of message collisions and spoofing are bounded and known ahead of time. Later, Bertier et al. BIB019 and Alistarh et al.  push things further by achieving reliable broadcast even when the adversary's budget is unknown. In contrast to the potentially inefficient proactive protocol of Koo et al. BIB008 , both of these results provide reactive strategies that deliver the message as soon as the adversary terminates its interference; consequently, the message complexity is improved. Furthermore, Alistarh et al.  provide bounds on latency which, interestingly, bear resemblance to the latency results of Pelc and Peleg BIB010 . In terms of energy efficiency, again receive state costs seem to be mostly ignored with the exception of King et al. BIB020 , BIB020 . In contrast to the works surveyed in Section III, the unreliability of wireless communication is largely ignored by these works and Bhandari and Vaidya address this practical issue in BIB012 . Along the same lines, it may be of interest to investigate reliable broadcast outside of the grid model and, even, outside of arbitrary graph topologies. For instance, one might examine reliable broadcast with adversarial interference under the SINR model. The experimentation of Alistarh et al.  demonstrates that theoretical analyses do not always match up with performance and it might be of interest to know whether more realistic interference and transmission propagation models can reduce this discrepancy. Another interesting aspect that has not received much attention is that of mobility in the context of Byzantine faulttolerant reliable broadcast. Several real-world sensor networks are deployed in scenarios where devices are not static such as monitoring wildlife on land BIB002 or collecting data on ocean currents BIB021 where devices may be mobile within a localized area. In some sense, the grid model accounts for mobility as a fault may be interpreted as the absence of a node as it moves within a local area. However, this aspect has not been examined explicitly and more precise models can surely be examined. For example, mobility might obey migration patterns or be dictated by predictable environmental phenomenon, in contrast to a worst case selection of faulty locations chosen by an adversary.