Geometric Optics, Duality and Congestion in Sensornets

When many sensors, spread over an area, communicate by shortest-path, straight-line routing, those who are centrally located are overburdened by communication overhead; this is known as the “busy center problem.” To balance the overhead, one could consider routing over curved paths. Choosing paths to optimize worst-case congestion can be expressed as an (infinite-dimensional) linear program, whose dual turns out to be a geodesic problem in geometric optics: Optimum routing is tantamount to light propagation through a medium of varying index of refraction. Alternatively, this can be thought as lowest-cost navigation in a city like London, where the closest to the center you drive the more you are charged. The optimum index of refraction (or price) as a function of the distance from the center is found by the primal-dual algorithm and by solving the appropriate variational equation. Simulations and actual experiments in the Berkeley Intel Lab’s sensornet testbed show that significant reduction and balancing of the congestion load. (Joint work with Richard M. Karp, Lucian Popa, Ion Sttoica, and Afshin Rostami.)

Speaker Details

Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at UC Berkeley. Before Berkeley he taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD. He has written four textbooks and many articles on algorithms, complexity, and their applications to optimization, databases, AI, economics, and the Internet. He holds a PhD from Princeton, and honorary doctorates from ETH (Zurich), the University of Macedonia (Thessaloniki) and the University of Athens. He is a member of the American Academy of Arts and Sciences and of the National Academy of Engineering, and a fellow of the ACM. His novel “Turing (a novel about computation),” was published by MIT Press in 2003.

Date:
Speakers:
Christos Papadimitriou
Affiliation:
University of California, Berkeley

    • Portrait of Jeff Running

      Jeff Running