Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 07151

Geometry in Sensor Networks

( Apr 09 – Apr 13, 2007 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



Networks of smart sensors offer exciting new possibilities for achieving sensory omnipresence: tiny, inexpensive, untethered sensor devices can measure and observe various environmental parameters, thereby allowing real-time and fine-grained monitoring of physical spaces around us. In order to realize this vision, however, several challenging research problem must be solved, many of which involve geometry due to the embedded nature of sensor devices. The aim of this seminar, held from April 10 to April 13, 2007, was to bring together experts from several areas of computer science and mathematics for discussions and exchange of ideas on the role of geometry in the evolution of sensor networks.

Enabled by recent advances in micro-electronics and fabrication, a new generation of integrated embedded devices, called smart sensors, has emerged that seems capable of realizing the long-cherished vision of sensory omnipresence or ubiquitous awareness. Through collaboration and ad hoc wireless networking, a collection of such devices can provide real-time, fine-grained sensing, monitoring, and actuation across large geographical areas. A key fact distinguishing sensor networks from other networked systems is that sensor nodes are \emph{embedded} in the physical environment in which they function. For instance, unlike more traditional networks such as the Internet or the phone network, communication in sensor networks is dictated less by the desires of the end nodes and more by the geography of the sensor field and the associated signal landscapes, as well as the overall network task. As a result, geometry plays a fundamental and crucial role in all aspects of the sensor network, including their design and operation. In particular, the network must discover its own geometry through self-localization of nodes, construct a lightweight and self-organizing naming and routing structure using virtual or physical coordinates, exploit physical embedding to perform information aggregation and dissemination etc. Motivated by these observations, the discussion during the workshop focused largely on techniques of a geometric or topological character that are particularly relevant to sensor networks.

We give a brief roundup of the excellent presentations: Pilu Crescenzi presented Bluetooth connectivity problems stemming from unavailable neighbor information. Leszek Gasieniec discussed how to escape the quadratic lower bound in geo-routing by including pre-processed information. Erik Jan van Leeuwen exhibited better approximation algorithms for disk graphs with bounded ply. Bastian Katz presented a new sensor network localization heuristic based on recursively applying rigidity theory, and discussed noisy measurements. Andrzej Pelc surveyed results on broadcasting in radio networks. Zvi Lotker discussed the MST of random geometric graphs, and its connection to the upper box dimension. Leonidas Guibas discussed how to aggregate data from sparse events by double rulings. Anish Arora continued presenting results about data aggregation with data of nearby nodes being fresher. Jie Gao presented new sensor network localization heuristics by means of rigidity theory, similarly as Bastian Katz. Jung-Geon Park discussed localization in a mobile environment. Alex Kroeller and Sandor Fekete first showed their video on sensor networks, and then presented new results on energy constrained flow problems. Michael Elkin gave new insights into distributed sparse spanner constructions in a dynamic model. Lata Narayanan presented an impossibility result for geo-routing in 3D, and a complementing possibility result for "$2\frac{1}{2}$D." Andrea Richa and Christian Scheideler presented SIT, a new model beyond the unit disk graph, and a new algorithm for dominating sets in this model, using only constant storage. Li Erran Li investigated how much it helps to communicate with two power levels. Paolo Santi discussed new theoretical and practical insights in topology control. Shakhar Smorodinsky surveyed various results in conflict-free coloring. Alon Efrat gave a talk on sensor coverage, with a survey on the related art gallery problem.

One common and recurring theme in many talks and discussions was the lack of an appropriate model for sensor networks. For instance, many theoretically elegant results for routing in ad hoc wireless networks have been derived using the idealized unit-disk model, which fails to capture the intricate reality of radio transmission.

An open problem session was held on April 10, 2007, the first day of the workshop. Several participants (Roger Wattenhofer, Evangelos Kranakis, Li Erran Li, Paolo Penna, Zvi Lotker, Leonidas Guibas) posed specific technical problems that have defied progress. Many of these problems elicited significant discussion among the participants, and in some cases participants even pointed to known or related results in their fields.

A general discussion forum was held on the last evening of the seminar, April 12, 2007, to speculate about the promising future directions of research in this young and emerging field. Many people felt that sensor networks are significantly different from general-purpose networks (such as the Internet) and a close coupling of applications and the networking will be important, unlike the Internet that advocates a clean separation of different layers.

In conclusion, the seminar offered a great opportunity for researchers with different, but overlapping, interests to share their expertise, and engage in intellectually stimulating discussions about the important future directions. The format of the workshop provided an ideal environment to question various assumptions in each others' work, find ideas and inspiration in their results, and get a better, more holistic, sense of how different areas of expertise can contribute to this emerging technology. Geometric approaches, through concepts and techniques, offer a number of opportunities in sensor networks to address problems at structural, functional and application levels. It is our belief that the exchange of ideas among the participants of this workshop will impact how they approach their future research in sensor networks and influence the field.

  • Anish Arora (Ohio State University - Columbus, US)
  • Pierluigi Crescenzi (University of Florence, IT) [dblp]
  • Alon Efrat (University of Arizona - Tucson, US) [dblp]
  • Michael Elkin (Ben Gurion University - Beer Sheva, IL)
  • Sándor Fekete (TU Braunschweig, DE) [dblp]
  • Jie Gao (SUNY - Stony Brook, US) [dblp]
  • Leszek A. Gasieniec (University of Liverpool, GB)
  • Leonidas J. Guibas (Stanford University, US) [dblp]
  • Alexander Hall (University of California - Berkeley, US)
  • Riko Jacob (TU München, DE) [dblp]
  • Bastian Katz (KIT - Karlsruher Institut für Technologie, DE)
  • Evangelos Kranakis (Carleton University - Ottawa, CA)
  • Danny Krizanc (Wesleyan Univ. - Middletown, US)
  • Alexander Kröller (TU Braunschweig, DE)
  • Li Erran Li (Bell Labs - Murray Hill, US)
  • Zvi Lotker (Ben Gurion University - Beer Sheva, IL)
  • Friedhelm Meyer auf der Heide (Universität Paderborn, DE) [dblp]
  • Lata Narayanan (Concordia University - Montreal, CA)
  • Jun Geun Park (MIT - Cambridge, US)
  • Andrzej Pelc (Université du Québec en Outaouais, CA)
  • Paolo Penna (University of Salerno, IT)
  • Andréa Richa (Arizona State University - Tempe, US) [dblp]
  • Paolo Santi (CNR - Pisa, IT)
  • Christian Scheideler (TU München, DE) [dblp]
  • Michiel Smid (Carleton University - Ottawa, CA)
  • Shakhar Smorodinsky (The Hebrew University of Jerusalem, IL)
  • Subhash Suri (University of California - Santa Barbara, US) [dblp]
  • Erik Jan van Leeuwen (CWI - Amsterdam, NL) [dblp]
  • Dorothea Wagner (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Roger Wattenhofer (ETH Zürich, CH) [dblp]
  • Peter Widmayer (ETH Zürich, CH) [dblp]

  • Networks
  • algorithms
  • mobile computing

  • sensor networks
  • computational geometry