Structure Discovery and Information Brokerage in Sensor Networks

March 15, 2006
Leonidas J. Guibas | Stanford University

Sensor networks are distributed systems embedded in a physical space. This embedding, as well as the nature of the physical laws governing the phenomena observed or monitored by the network, can greatly influence the design of system architectures and information processing paradigms for such systems. In this talk we describe a number of lightweight tools for discovering the structure of the network at a high level, or of the signal landscapes it observes, and then distributing a small amount of this global knowledge to each node. We use this local data for globally-aware, efficient naming and routing, information dissemination and aggregation, and information discovery. We argue that this helper information blends well with current architecture proposals such as SP-SNA or Tenet, and is robust to low-level link volatility and other transient network effects. A number of the proposed techniques incorporate ideas from algebraic topology, computational geometry, and partial differential equations.

Speaker Details

Leonidas Guibas obtained his Ph.D. from Stanford in 1976, under the supervision of Donald Knuth. His main subsequent employers were Xerox PARC, MIT, and DEC/SRC. He has been at Stanford since 1984 as Professor of Computer Science, where he heads the Geometric Computation group within the Graphics Laboratory. He is also part of the AI Laboratory and the Bio-X Program. Professor Guibas’ interests span computational geometry, geometric modeling, computer graphics, computer vision, robotics, ad hoc communication and sensor networks, and discrete algorithms — all areas in which he has published and lectured extensively. At Stanford he has developed new courses in algorithms and data structures, geometric modeling, geometric algorithms, sensor networks, and biocomputation. Professor Guibas is an ACM Fellow.