January 26 – 31 , 2014, Dagstuhl Seminar 14051

Algorithms for Wireless Communication


Guy Even (Tel Aviv University, IL)
Magnús M. Halldórsson (Reykjavik University, IS)
Yvonne-Anne Pignolet (ABB Corporate Research – Baden-Dättwil, CH)
Christian Scheideler (Universität Paderborn, DE)

For support, please contact

Dagstuhl Service Team


Dagstuhl Report, Volume 4, Issue 1 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents


The last decades have seen an ever growing interest in wireless communication networks and their applications. Wireless networks pose many algorithmic challenges for various reasons: Realistic wireless signal propagation and interference models are very complex and therefore hard to use in rigorous algorithmic research, and this is further complicated by emerging technologies such as MIMO (multiple-input and multiple-output). Also, reasonable models for the dynamics and mobility in these networks can be quite complex and are not yet well-understood. Furthermore, standard complexity measures such as time and space are not sufficient any more as energy consumption is also a critical aspect that cannot be neglected. Many protocols for wireless networks have already been proposed by the research community, but most of them have only been studied in simulations or analyzed using rather simple models. So there is doubt whether any of these protocols would actually work in practice.

The purpose of this Dagstuhl seminar was to bring together computer scientists of different backgrounds to review and discuss models and algorithmic approaches in order to obtain a better understanding of the capabilities and limitations of modern wireless networks and to come up with more realistic models and approaches for future research on wireless networks that may then be investigated in joint research projects. The mix of the participating people resulted in fruitful discussions and interesting information exchange. The structure of the seminar took advantage of these different backgrounds by focusing on themed talks and open discussions.

The program included an eclectic mix of algorithmic and systems perspectives, modeling issues and emerging networking techniques, and explorations of the limits and possibilities of fundamental problems.

Discussions of models ranged from simple graph-based communication and interference models, to stochastic models, adversarial interruptions and jamming, dynamic networks and uncertainty formulations, and variations and extensions of signal-strength models.

Presentations from the systems perspective included managing environmental factors affecting measurements, robust predictions of channel capacities, efficiency of backpressure routing, issues in emerging heterogeneous radio environmental contexts, and robots controlled via wireless communication.

New dimensions at different networking layers included MIMO, network coding, interference cancellation, directional antennas and cognitive radio networks.

Finally, new results were presented on various related classic problems including broadcast, local broadcast, game theory, coding, routing, positioning, and connectivity.

  Creative Commons BY 3.0 Unported license
  Guy Even, Magnús M. Halldórsson, Yvonne-Anne Pignolet, and Christian Scheideler


  • Data Structures / Algorithms / Complexity
  • Mobile Computing
  • Networks


  • Distributed algorithms
  • Wireless networks
  • Wireless communication models

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support