Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> B. Collision Detection <s> In this paper we evaluate a technique to detect and recover messages from packet collisions by exploiting the capture effect. It can differentiate between collisions and packet loss and can identify the nodes involved in the collisions. This information is provided at virtually no extra cost and can produce significant improvements in existing collision mediation schemes. We characterize this technique using controlled collision experiments and evaluate it in real world flooding experiments on a 36-node sensor network. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> B. Collision Detection <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> BIB002 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> B. Collision Detection <s> Practitioners agree that unreliable links, which sometimes deliver messages and sometime do not, are an important characteristic of wireless networks. In contrast, most theoretical models of radio networks fix a static set of links and assume that these links are reliable. This gap between theory and practice motivates us to investigate how unreliable links affect theoretical bounds on broadcast in radio networks. To that end we consider a model that includes two types of links: reliable links, which always deliver messages, and unreliable links, which sometimes fail to deliver messages. We assume that the reliable links induce a connected graph, and that unreliable links are controlled by a worst-case adversary. In the new model we show an Ω(n log n) lower bound on deterministic broadcast in undirected graphs, even when all processes are initially awake and have collision detection, and an Ω(n) lower bound on randomized broadcast in undirected networks of constant diameter. This separates the new model from the classical, reliable model. On the positive side, we give two algorithms that tolerate unreliability: an O(n3/2 √log n)-time deterministic algorithm and a randomized algorithm which terminates in O(n log2 n) rounds with high probability. <s> BIB003
Despite the assumption of a time-slotted network where nodes are assigned non-conflicting slots, deliberate interference may still occur due to adversarial behavior. A message collision occurs when two or more transmissions interfere with each other. In this case, devices that are listening to the medium are typically assumed to either receive none of the messages being transmitted, or receive a message chosen by an adversary. Of course, in practice, when two simultaneous transmissions occur, the contents of the message are not necessarily lost. Indeed, both signals are received and, in some cases, the stronger signal can be discerned; this is known as the capture-effect BIB001 . However, it is often impossible to reliably separate between multiple transmissions due to fading effects. We point out that in adversarial settings, the utility of collision detection differs from its typical uses in backoffbased protocols for transmitting frames over a wireless channel. Instead, the ability to detect collisions allows correct devices to determine whether an adversary is attempting to thwart communication. As we will see, in many cases this is critical in establishing the successful termination of a communication protocol. The correct modeling of collision detection is an issue of some debate. In practice, channel activity is determined by performing clear channel assessment (CCA)  . In particular, the detection of channel activity is performed via the radio chip using the received signal strength indicator (RSSI)  . If the RSSI value is below the clear channel threshold, then the channel is assumed to be clear. In theory, as we will see, there are several approaches to collision detection that are typically adopted. The collision detection model employed is a design choice that significantly impacts what is feasible under a particular adversarial model. Consequently, this aspect is important to consider when placing a result in context with other results in the area. There are several papers that address the challenges of providing an appropriate mathematical model of wireless interference and collision detection; in particular, the reader is referred to work by Kuhn et al. BIB003 and Chockler et al. BIB002 .