Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Communication Complexity and Leader Election: <s> We consider routing security in wireless sensor networks. Many sensor network routing protocols have been proposed, but none of them have been designed with security as a goal. We propose security goals for routing in sensor networks, show how attacks against ad-hoc and peer-to-peer networks can be adapted into powerful attacks against sensor networks, introduce two classes of novel attacks against sensor networks sinkholes and HELLO floods, and analyze the security of all the major sensor network routing protocols. We describe crippling attacks against all of them and suggest countermeasures and design considerations. This is the first such analysis of secure routing in sensor networks. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Communication Complexity and Leader Election: <s> In this paper we consider the problem of designing a medium access control (MAC) protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming. The wireless network consists of a set of honest and reliable nodes that are within the transmission range of each other. In addition to these nodes there is an adversary. The adversary may know the protocol and its entire history and use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-epsilon)-fraction of the time steps, for an arbitrary constant epsilon>0, but it has to make a jamming decision before it knows the actions of the nodes at the current step. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant throughput for the non-jammed time steps under any adversarial strategy above. We also show that our protocol is very energy efficient and that it can be extended to obtain a robust and efficient protocol for leader election and the fair use of the wireless channel. <s> BIB002 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Communication Complexity and Leader Election: <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> BIB003
The authors evaluate the number of times a node needs to transmit a message. It turns out that this quantity is rather small at O(log 3 N/γ 2 ). However, it appears that the amount of listening time is significant as each node v must listen to the channel in order to detect idle or single-message time slots in order to modify p v . Detecting an idle channel can be done through CCA methods and would likely consume only a negligible amount of energy. However, if the node detects activity on the channel, the transceiver must be activated in order to determine whether the message is successfully being sent (a single-message slot) or a collision has occured. At this point, the node must incur the substantial receive state cost. Therefore, over the execution of the protocol, the listening costs might be substantial. Finally, the authors illustrate how their MAC protocol can be applied to solve the leader election problem in the presence of a (T, 1 − )-bounded adversary. In particular, they give a leader election protocol that, with high probability, elects a leader within O( Richa et al. BIB003 In the immediately previous work by Awerbuch et al. BIB002 , we saw that it is possible to obtain good throughput against a jamming adversary in a single-hop network. In this subsequent work, Richa et al. BIB003 look at achieving a similar result for multi-hop networks. Again, the jamming adversary is (T, 1 − )-bounded. The authors also define a k-uniform adversary as follows. Consider partitioning nodes into k sets. A k-uniform adversary is one whose jamming capabilities are such that in each of the k sets, either all or none of the nodes are jammed. For example, a 1-uniform adversary jams either all or none of the nodes in the network, while a n-uniform adversary can decide whether or not to jam each node individually. The same network assumptions are made regarding synchronization and the ability to detect activity on the channel. However, a key difference is that the network under consideration is now a unit disk graph (UDG). Under this model, two nodes u, v ∈ V can communicate if they are within a normalized distance of 1 from each other. Richa et al. provide a symmetric MAC protocol for multi-hop networks called JADE with the following important property. Assume that JADE is run for Ω(T log n/ + (log 4 n/(γ ) 2 )) time steps and, again, γ = O(1/(log T + log log n)). Then JADE is constant competitive with high probability in n so long as (1) the adversary is 1-uniform and the UDG is connected or (2) every node has at least 2/ neighbors. The authors also demonstrate that if (1) the UDG is not connected or (2) the adversary is 2-uniform and there exist nodes with o(1/ ) neighhors, then there are situations where JADE is constant competitive with high probability. The JADE protocol is somewhat more complicated than its single-hop counterpart in BIB002 but is still relatively simple to state. Each node v holds a probability value p v , a threshold value T v and a counter value c v . For a positive fixed parameter p ≤ 1/24, each node initiates the protocol with T v = 1, c v = 1 and p v =p. In each round, each node v transmits with probability p v . If v does not transmit, then it acts according to the following cases: (1) if v detects that the channel is idle, Finally, if there is no round in the last T v rounds where (1) v sensed a successful message transmission or BIB001 detected that the channel was idle, then 1/(4γ) }. While much of the JADE protocol is motivated by the same reasoning in the previous section describing BIB002 , the analysis is significantly different. The authors also provide some preliminary simulation results to illustrate the effectiveness of their protocol. Under both uniform and normal distributions for node placement with n = 500, JADE demonstrates a normalized throughput of roughly 0.3 and 0.25, respectively. Moreover, in the case of the uniform distribution, the convergence to the constant throughput value is shown to be rapid, achieving the peak throughput within roughly 200 rounds. A couple final comments are in order. First, as with the protocol of BIB002 , JADE requires nodes to spend a substantial amount of time listening to the channel in order to detect either successful transmissions or idle time slots. An interesting question is whether there exists a constant-competitive multihop MAC protocol that is more energy efficient. Second, the focus here is on the UDG model, and it is worth considering whether JADE might be modified for other topologies; indeed, the authors conjecture that such an extension is possible.