Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> The dynamic and lossy nature of wireless communication poses major challenges to reliable, self-organizing multihop networks. These non-ideal characteristics are more problematic with the primitive, low-power radio transceivers found in sensor networks, and raise new issues that routing protocols must address. Link connectivity statistics should be captured dynamically through an efficient yet adaptive link estimator and routing decisions should exploit such connectivity statistics to achieve reliability. Link status and routing information must be maintained in a neighborhood table with constant space regardless of cell density. We study and evaluate link estimator, neighborhood table management, and reliable routing protocol techniques. We focus on a many-to-one, periodic data collection workload. We narrow the design space through evaluations on large-scale, high-level simulations to 50-node, in-depth empirical experiments. The most effective solution uses a simple time averaged EWMA estimator, frequency based table management, and cost-based routing. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> In a wireless, multi-hop sensor network, choosing transmission power levels has an important impact on energy efficiency and network lifetime. Two algorithms for dynamically adjusting transmission power level on a per-node basis are proposed here. Network lifetime, convergence speed as well as resulting network connectivity are used as figures of merit for these two algorithms. They have been evaluated in an indoor sensor environment. The network lifetime metrics of these two local algorithms are also benchmarked against power control algorithms using global information. We show that these local algorithms outperform fixed power level assignment and that the lifetime achieved by them is usually within a factor of two of globally computed solution while being scalable. <s> BIB002 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> In this paper, we investigate the impact of radio irregularity on the communication performance in wireless sensor networks. Radio irregularity is a common phenomenon which arises from multiple factors, such as variance in RF sending power and different path losses depending on the direction of propagation. From our experiments, we discover that the variance in received signal strength is largely random; however, it exhibits a continuous change with incremental changes in direction. With empirical data obtained from the MICA2 platform, we establish a radio model for simulation, called the Radio Irregularity Model (RIM). This model is the first to bridge the discrepancy between spherical radio models used by simulators and the physical reality of radio signals. With this model, we are able to analyze the impact of radio irregularity on some of the well-known MAC and routing protocols. Our results show that radio irregularity has a significant impact on routing protocols, but a relatively small impact on MAC protocols. Finally, we propose six solutions to deal with radio irregularity. We evaluate two of them in detail. The results obtained from both the simulation and a running testbed demonstrate that our solutions greatly improve communication performance in the presence of radio irregularity. <s> BIB003 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> All analytical and simulation research on ad~hoc wireless networks must necessarily model radio propagation using simplifying assumptions. We provide a comprehensive review of six assumptions that are still part of many ad hoc network simulation studies, despite increasing awareness of the need to represent more realistic features, including hills, obstacles, link asymmetries, and unpredictable fading. We use an extensive set of measurements from a large outdoor routing experiment to demonstrate the weakness of these assumptions, and show how these assumptions cause simulation results to differ significantly from experimental results. We close with a series of recommendations for researchers, whether they develop protocols, analytic models, or simulators for ad~hoc wireless networks. <s> BIB004 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> In this paper we investigate the performance of mica2 and mica2dot Berkeley motes by means of an extensive experimental analysis. This study is aimed at analyzing the main elements that characterize the performance of a sensor network, e.g., power consumption in different operating conditions, impact of weather conditions, interference between neighboring nodes, etc. Even if the analysis is related to a specific technology it provides some general useful information. Specifically, we found that the transmission range of mote sensor nodes decreases significantly in the presence of fog or rain. We also investigated the interference between neighboring nodes and, based on the experimental results, we propose a channel model for mote sensor nodes. This model is very similar to the channel model of IEEE 802.11 networks. <s> BIB005 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> Much work has focused on the Byzantine Generals (or secure broadcast) problem in the standard model in which pairwise communication is available between all parties in the network. Some research has also explored the problem when pairwise channels exist only between selected pairs of players, or under the assumption of "k-cast channels" shared by all subsets of players of size k. However, none of these models are appropriate for radio networks in which a player can communicate only by multicasting a message which is then received by all players within some radius r (i.e., the neighbors of the transmitting node). Yet, as far as we are aware, obtaining secure broadcast in radio networks in the presence of a Byzantine adversary has not been studied before.This paper corrects this omission, and provides the first analysis of secure broadcast in radio networks for the case of Byzantine adversaries. We note that secure broadcast is impossible in the presence of an omnipotent adversary. To bypass this barrier, we make the following assumption: there exists a prefixed schedule for players to communicate and everyone (including corrupted ones) adheres to this schedule. Under this assumption, we give a simple broadcast protocol which is provably secure whenever the adversary corrupts at most 1 4 r(r+√rover2 + 1)-3 neighbors (roughly a 1/4π fraction) of any honest player. On the other hand, we show that it is impossible to achieve secure broadcast when the adversary corrupts ⌈1/2 r(2r+1)⌉ (roughly a 1/π fraction) neighbors of any honest player. <s> BIB006 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> Theorists and practitioners have fairly different perspectives on how wireless broadcast works. Theorists think about synchrony; practitioners think about backoff. Theorists assume reliable communication; practitioners worry about collisions. The examples are endless. Our goal is to begin to reconcile the theory and practice of wireless broadcast, in the presence of failures. We propose new models for wireless broadcast and use them to examine what makes a broadcast model good. In the process, we pose some interesting questions that help to bridge the gap. <s> BIB007 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> We consider the use of distributed source and network coding in networks of redundant, unreliable sensors. A design algorithm is described for distributed joint source and network coding that creates an optimal balance between compression efficiency and network robustness. <s> BIB008 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> Recently, several MAC protocols, such as S-MAC and T-MAC, have exploited scheduled sleep/wakeup cycles to conserve energy in sensor networks. Until now, most protocols have assumed all nodes in the network were configured to follow the same schedule, or have assumed border nodes would follow multiple schedules, but those cases have not been evaluated. The paper develops two new algorithms to control and exploit the presence of multiple schedules to reduce energy consumption and latency. The first one is the global schedule algorithm (GSA). Through experiments, we demonstrate that, because of radio propagation vagaries, large sensor networks have very ragged, overlapping borders where many nodes listen to two or more schedules. GSA is a fully distributed algorithm that allows a large network to converge on a single global schedule to conserve energy. Secondly, we demonstrate that strict schedules incur a latency penalty in a multi-hop network when packets must wait for the next schedule for transmission. To reduce latency in multi-hop paths, we develop the fast path algorithm (FPA). FPA provides fast data forwarding paths by adding additional wake-up periods on the nodes along paths from sources to sinks. We evaluate both algorithms through experiments on Berkeley motes and demonstrate that the protocols accomplish their goals of reducing energy consumption and latency in large sensor networks. <s> BIB009 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <s> We undertake a systematic experimental study of the effects of concurrent packet transmissions in low-power wireless networks. Our measurements, conducted with Mica2 motes equipped with CC1000 radios, confirm that guaranteeing successful packet reception with high probability in the presence of concurrent transmissions requires that the signal-to-interference-plus-noise-ratio (SINR) exceed a critical threshold. However, we find a significant variation of about 6 dB in the threshold for groups of radios operating at different transmission powers. We find that it is harder to estimate the level of interference in the presence of multiple interferers. We also find that the measured SINR threshold generally increases with the number of interferers. Our study offers a better understanding of concurrent transmissions and suggests richer interference models and useful guidelines to improve the design and analysis of higher layer protocols. <s> BIB010 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <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> BIB011 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Popular Abstraction: Discussion of the Grid Model <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> BIB012
Theoretical treatments of radio networks have attracted a measure of skepticism from practitioners  , BIB007 and there are several aspects of the grid model that warrant discussion. The following issues are cause for concern: Broadcast Region: Experiments with real-world deployments demonstrate that a broadcast region is not well-characterized by a circle of radius r with p located at the center BIB003 , BIB004 . In fact, the region successfully receiving a broadcast is often dynamic, changing constantly depending on nearby sources of electromagnetic interference, power irregularities, features of the terrain, and weather conditions. Network Synchrony: The model assumes the existence of a predefined schedule known to all nodes in the network. It is conceivable that such a schedule might be programmed into the nodes before deployment. However, use of a schedule presupposes a synchronous network where each node is able to determine its allotted time slot. Moreover, this synchrony must be maintained throughout the lifetime of the network so either there can be no significant clock drift over time or there must be a mechanism in place to maintain synchronization. Network Topology: The use of a grid allows for an elegant analysis of the system. However, this layout is unrealistic for many settings. Despite these concerns, there are a number of results in the literature that perhaps redeem the model. Some experimental work has demonstrated that the range of transmission is fairly reliable up to a certain distance δ BIB005 ; therefore, it may be reasonable to take r = δ. Other experimental studies have shown that communication is reliable so long as the signal-tointerference-plus-noise-ratio exceeds a threshold value BIB010 ,  ; therefore, a transmission power above this threshold yields reliable communication. Broadcast inconsistencies due to weather or terrain are harder to rationalize; however, such failures may be handled through more robust transmission algorithms such as described in BIB008 . Moreover, the irregularity of the broadcast neighborhood has been studied BIB005 , BIB003 , BIB001 , BIB002 along with a number of techniques for ameliorating the unreliability of the wireless medium. Regarding synchronization, this has been demonstrated experimentally without faults in BIB009 and, in the presence of an adversary, this has been examined in BIB012 , BIB011 . In the course of this survey, we will see several works that generalize from the grid to arbitrary topologies. Koo BIB006 A number of works have examined the problem of reliable broadcast under a model where devices communicate via pairwise channels or multi-cast. However, in sensor networks, neither model is appropriate as a message is received by all devices within the radius of transmission and the work in BIB006 is the first to address reliable broadcast in this context. Koo places his results in the context of radio networks rather than sensor networks. The distinction is irrelevant to our purposes as these results apply equally to sensor networks which possess a transceiver in addition to sensing equipment. Radio networks are more general as they are not necessarily equipped with sensing apparatus and may not be subject to the same energy constraints as sensor networks. While Koo provides both novel upper and lower bound results, it is perhaps the latter which is most important given subsequent improvements to the former and the idealized nature of the grid model discussed previously in Section IV. This result is stated as: Broadcast is impossible in the L ∞ metric if t ≥ 