Abstract

In recent years, there has been a tremendous surge of interest in the design and analysis of efficient protocols for wireless networks. Yet, while a multiplicity of protocols for routing, scheduling, and other coordination tasks have been proposed, there is still relatively little known about many of the foundations that govern coordination and computation in wireless networks. In this talk, I will give an overview over some recent work on algorithmic aspects of wireless networks and I will highlight their connections to fundamental distributed computing problems.

In the first part, I will focus on the problem of clustering in wireless networks, which can facilitate routing and media access control, and helps in improving energy-efficiency. I will discuss how clusters can be computed by the wireless nodes in a provably efficient way, and how the underlying model impacts the theoretical possibilities and limitations of distributed algorithms for this problem. Starting from well-known clean and abstract graph models for wireless communication, I will move towards more realistic and harsher radio network models and show that even for these models, efficient algorithms with provable worst-case guarantees can be designed.

Unfortunately, graph-based models are inherently incapable of capturing crucial aspects of wireless communication, especially when it comes to scheduling. In the second part of the talk, I will therefore focus on algorithmic worst-case results for an even harsher communication model, the signal-to-noise-plus-interference (SINR) model. I will introduce the 'scheduling complexity' as a measure for quantifying the achievable efficiency of wireless scheduling protocols. Intuitively, the scheduling complexity captures the amount of time required to schedule a set of requests. As it turns out, all intuitive and currently employed scheduling protocols in multi-hop radio networks perform significantly below the theoretical limits in certain networks, even for simple request sequences. On the other hand, a careful assignment of time slots and power levels to nodes can guarantee in every network that complicated requests are scheduled quickly.