GI-Dagstuhl Research Seminar

Algorithms for Sensor and Ad Hoc Networks

Overview

Thousands of mini computers (in size comparable to a chewing gum), equipped with sensors, are deployed in some terrain. After activation the sensors form a self-organized network and provide data, for example about a forthcoming earthquake.

The trend towards wireless communication affects more and more electronic devices in almost every sphere of life. Conventional networks rely on base stations, and the mobile devices exchange the data in a starlike fashion. In contrast, current research is mainly focused on networks that are completely unstructured, but are nevertheless able to communicate (via several hops) with each other, despite the low coverage of their antennas.

Such systems are called sensor or ad hoc networks, depending on the point of view and the application. Since a few years, these networks are the focus of the networking community. An increasing amount of work in the area of sensor and ad hoc networks is done by theoreticians, from fields including algorithmics, distributed systems, graph theory, and computational geometry. Our goal is to support this growing interest of theoreticians, which we believe is important to provide a deeper understanding of self-organizing networks.

The goal of the seminar is to elaborate the relevant algorithmic aspects of the field and inspire young—and not yet established—researchers. The young researchers get to know each other and initial points of contact for joint research can be worked out.

The participants work on topics based on selected basic literature, which are presented and discussed during the seminar. We want to concentrate on the algorithmically interesting aspects. In particular, we are interested in:

• MAC-Layer
• Security
• Routing
• Cooperation
• Time synchronization
• Data gathering

Further Information

• Call for participation (in German)
• Additional information for participants (restricted access)
• The final product is now available!

About this Series

Since 1997, the Gesellschaft für Informatik (GI) organizes research seminars on hot topics in computer science that are not appropriately represented in textbooks, yet. They are targeted at graduate students and recent PhDs who are interested in learning actively about new developments. Participants are selected mainly according to scientific qualification, i.e. not because of their special area of research, in order to widely spread such developments among academic institutions. The number of participants is typically limited to 20. So far, other GI research seminars have been or are being organized on the following topics:

• Network Analysis (2004, Springer LNCS 3418)
• Game-Theoretic Analyses of the Internet
• Model-based Testing of Reactive Systems
• Validation of Stochastic Systems
• Algorithms for Memory Hierarchies (2002, Springer LNCS 2625)
• Automata, Logic and Infinite Games (2001, Springer LNCS 2500)
• Graph Drawing (1999, Springer LNCS 2025)
• Efficient Methods for Geometric Modelling and Scientific Visualization (1997, proceedings published with Teubner)
• Proof Verification and Approximation Algorithms (1997, Springer LNCS 1367)