DFG Project - Adversarial Models for Wireless Communication

Goals:

The main goal of the proposed research is to investigate adversarial models for the physical layer and to explore the limits of designing provably robust medium access control (MAC) protocols for them. Finding suitable models that on one hand allow the rigorous design and analysis of protocols and on the other hand are useful in practice is a major challenge that has received significant attention in the research community. We will investigate models for wireless communication that promise to cover a wide range of physical layer phenomena and that are yet simple enough so that they are useful in theory. Our adversarial models consist of two parts: network-based interference, which is based on a standard model for the interference caused by transmissions, and adversarial interference, which is additional interference caused by an adversary within the network-based model. Concrete network-based interference models that we intend to study range from the simple unit disk graph (UDG) model, which will be used for initial insights, to the sophisticated signal-to-interference-and-noise-ratio (SINR) model, which will be used to determine how well our MAC protocols may perform in practice. Concrete adversarial interference models range from oblivious adversaries (to abstract from background noise and temporary obstacles) to reactive adversaries (to study jamming attacks).

Publications:

[1] Awerbuch, B.; Richa, A. & Scheideler, C., A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks, Proc. of the 27th ACM Symposium on Principles of Distributed Computing (PODC), 2008, 45-54
[2] Richa, A.; Scheideler, C.; Schmid, S. & Zhang, J., A jamming-resistant MAC protocol for multi-hop wireless networks, Proc. of the 24th Symposium on Distributed Computing (DISC), 2010, 179-193
[3] Scheideler, C.; Richa, A. & Santi, P., An $O(log n)$ Dominating Set Protocol for Wireless Ad-Hoc Networks under the Physical Interference Model, Proc. of the 9th ACM Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc), 2008, 91-100
[4] Richa, A. W.; Scheideler, C.; Schmid, S. & Zhang, J., Self-stabilizing leader election for single-hop wireless networks despite jamming, MobiHoc, ACM, 2011, 15
[5] Richa, A. W.; Scheideler, C.; Schmid, S. & Zhang, J., Competitive and Fair Medium Access Despite Reactive Jamming, ICDCS, IEEE Computer Society, 2011, 507-516 

Our groundwork:

Adaptive Adversarial Jamming in Single-Hop Communication

In [1] we considered the problem of designing a MAC protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming at the physical layer. The wireless network consists of a set of n reliable nodes that are within the transmission range of each other and operate over a single frequency band. All of the nodes are continuously contending for sending a packet on the wireless channel. A node who is sensing the channel may either (i) sense an idle channel (in case no other node is transmitting at that time), (ii) sense a busy channel (in case two or more nodes transmit at the time step), or (iii) receive a packet (in case exactly one node transmits at the time step). In addition to these nodes there is an adversary. We allow the adversary to know the protocol and its entire history and to use this knowledge in order to jam the wireless channel at will at any time (i.e, the adversary is adaptive). We assume that the adversary is only allowed to jam a (1-epsilon)-fraction of the time steps, for an arbitrary constant epsilon > 0, and it has to make a jamming decision before it knows the actions of the nodes at the current step. Our goal was to design a symmetric local-control MAC protocol (i.e., there is no central authority controlling the nodes, and all the nodes are executing the same protocol) that is constant competitive against any (T,1-epsilon)-bounded adversary. We showed that such a protocol indeed exists. It is very simple and self-stabilizing, that is, it can recover from any state. We also showed that the MAC protocol is very energy efficient.

Adaptive Adversarial Jamming under Multi-hop UDGs

In [2] we extended the work in [1] to a preliminary study of multi-hop wireless networks, taking the simplified UDG wireless network model into consideration. As before, we assume that at each time step, a node may either transmit a message or sense the channel, but it cannot do both. In addition to these nodes there is an adaptive adversary (who may control any number of jamming devices). Our goal was to design a symmetric local-control MAC protocol that has a constant-competitive throughput against any (T,1-epsilon)-bounded adversary in any multi-hop network that can be modeled as a UDG. Our main result is a protocol called Jade, which is a slight adaptation of the single-hop protocol above and has the following performance.

Dominating Sets under SINR

In [3], we studied the problem of designing a protocol for the dominating set problem for wireless ad-hoc networks under the SINR model. Our contributions were two-fold: (i) we proposed a new model for wireless communication based on the SINR model which incorporates physical carrier sensing and which generalizes the log-normal shadowing model; and (ii) we demonstrated how to develop and analyze algorithms on top of this model by presenting a local-control algorithm for building a constant density dominating set. A notable feature of our algorithm, which we called TWIN, is that nodes do not need to have any a priori knowledge about the other nodes, not even an estimate on their total number. Under these conditions the TWIN protocol establishes a constant density dominating set in O(log n) communication rounds with high probability, where n is the number of nodes.

Participants:

Collaborating researchers:

Impressum | Webmaster | Letzte Änderungen am : 16.10.2013