Geometry in Sensor Networks

Summary

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.