From an algorithmic point of view, systems based on wireless communication pose unique challenges that are not present in standard networks. Wireless devices may move around and communication between these devices can be disrupted for several reasons including obstacles, background noise, and interference problems due to transmissions from the own wireless network, from a malicious jammer trying to disrupt communication, as well as coexisting networks using the same frequency band. 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 and deserves significant research efforts.
We will investigate models for wireless communication that cover a wide range of physical layer phenomena and that are yet simple enough so that they are useful in theory and practice. In contrast to prior algorithmic approaches, our approach will be to model communication problems due to physical layer issues (such as ackground noise, obstacles, jammers, etc.) with the help of an adversary, and to develop medium access (MAC) protocols that are provably robust against these adversaries. Such an approach has many interesting applications. First, it allows for more general scenarios for the background noise than previous approaches as it covers bursty situations that might be due to some temporary obstacle or operation of a machine that creates interference. Second, the adversarial model would also allow us to determine how robust a protocol is against wireless jamming attacks, which are a real threat to standard protocols such as the 802.11 family or networks of simple sensing wireless devices (where traditional physical layer techniques cannot be successfully applied). Finally, the adversarial model may allow us to abstract from interference problems due to transmissions of far away devices in the wireless network. In addition, we will also focus on important applications such as leader election and broadcasting.
Since wireless networks are a component of many widespread and/or critical systems, the proposed research will have an impact in several respects, including immediate applications to emergency services, the military, and local area networks in hazardous areas. Moreover, the proposed research will also have an impact in solidifying the international collaboration with the U. of Paderborn, Germany, and in advancing education and enhancing diversity.
One of the biggest challenges in larger scale implementations of ad-hoc networks comprised of wireless nodes is the mitigation of interference generated by the wireless signal of the network nodes themselves and also interference generated by external sources (e.g., due to environmental conditions, such as rain, or due to intentional jamming of the wireless signal by malicious nodes, a.k.a. a jammers). In order to be able to design protocols that are provably robust against interference, we first devised models for wireless communication that cover a wide range of physical layer phenomena and that are yet simple enough so that they are useful in theory and practice. In contrast to prior algorithmic approaches, we model communication problems due to physical layer issues (such as background noise, obstacles, jammers, etc.) with the help of an adversary. We then propose medium access (MAC) protocols that are provably robust against these adversaries. Such an approach has many interesting applications. First, the adversary allows us to study more general scenarios for the background noise than using, for example, stochastic assumptions, as it covers bursty situations that might be due to some temporary obstacle or operation of a machine that creates interference. Second, the adversarial model also allows us to determine how robust a protocol is against wireless jamming attacks, which are a real threat to standard protocols such as the 802.11 family or networks of simple sensing wireless devices. Finally, the adversarial model may allow us to abstract from interference problems due to transmissions of far away devices in the wireless network. 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. We developped a suite of protocols that can handle even the sophisticated signal-to-interference-and-noiseratio (SINR) model for network-based interference, and also sophiscated models on how an external adversary ("jammer") might decide to generate interference at individual nodes in the network at different levels over time. Concrete adversarial interference models that we investigated are (i) oblivious adversaries, which create adversarial interference that is independent of the actions of the MAC protocol (e.g., an adversary may be used to abstract from background noise and temporary obstacles); (ii) semi-oblivious adversaries, which create adversarial interference that depends on the actions of the MAC protocol without intentionally trying to disrupt the protocol (e.g., those adversaries can be used to model interference due to coexisting networks); (iii) adaptive adversaries, that adaptively jam the wireless channel based on past information about its state (e.g., these can be used to model adaptive malicious jammers); (iv) reactive adversaries, that jam the wireless channel based on past and current information about its state (e.g., these adversaries can be used to model more sophisticated malicious jammers). We mainly focused on the throughput achievable by our MAC protocols under our adversarial models: all of our proposed protocols achieve constant-competitive throughput. On top of that, we are interested in protocols that are fair, adaptive and self-stabilizing. Finally, we will also focus on important applications such as leader election and broadcasting. Intellectual Merit: Designing provably robust wireless network protocols is a challenging area due to the sophisticated adversarial communication models that have to be used in order to correctly model reality. On top of this, we must heavily rely on randomization in order to protect the network against adaptive adversarial jamming. In order to be able to analyze the resulting stochastic (or, in some cases, non-stochastic) processes, we have to develop and use sophisticated mathematical techniques which may be of independent interest. All of the results obtained in this project were published at top-quality conferences and journals in Networking and Theoretical Computer Science. Broader Impact: The research conducted through this project had an impact in several respects, such as: (i) bridging the gap between theory and practice, in the sense that our adversarial jamming/interference-resistant MAC protocols will be simple enough to have a high impact in practice, with immediate applications to emergency services, the military, local area networks in hazardous areas, etc.; (ii) international collaboration, since we will further foster the successful collaboration with Prof. Scheideler and the U. of Paderborn, Germany; (iii) multidisciplinary activities, since adversarial modeling, wireless networks and self-stabilization span many different areas; (iv) advancing education and enhancing diversity at ASU.
