Geographic Routing Systems for Wireless Networks

Project Overview

Geographic routing algorithms are attractive for wireless ad hoc networks because they have been shown to scale better than other alternatives: they require per-node state independent of network size, dependent only on network density. More recently, geographic routing algorithms have been proposed for use as a routing primitive for static sensor networks, as building blocks for data storage and flexible query processing in sensor networks, and even as a fallback routing mechanism for reduced state routing in the Internet.

However, the correctness of all currently proposed geographic routing algorithms relies on idealized assumptions about radios and their resulting connectivity graphs. We use testbed measurements to show that these idealized assumptions are grossly violated by real radios, and that these violations cause persistent failures in geographic routing, even on static topologies. Having identified this problem, we then fix it by proposing the Cross-Link Detection Protocol (CLDP), which enables provably correct geographic routing on arbitrary connectivity graphs. We confirm in simulation and further testbed measurements that CLDP is not only correct but practical: it incurs low overhead, exhibits low path stretch, always succeeds in real, static wireless networks, and converges quickly after topology changes.

People

Publications

Lazy Cross-Link Removal for Geographic Routing, Young-Jin Kim, Ramesh Govindan, Brad Karp, Scott Schenker, Proceedings of the ACM Conference on Embedded Networked Sensor Systems (Sensys), November 2006 [PDF]

On the Pitfalls of Geographc Face Routing, Young-Jin Kim, Ramesh Govindan, Brad Karp, Scott Schenker, Proceedings of the Third ACM/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIAL-M-POMC 2005), Sep., 2005 [PDF]

Geographic Routing Made Practical, Young-Jin Kim, Ramesh Govindan, Brad Karp, Scott Schenker, Proceedings of the USENIX Symposium on Networked Systems Design and Implementation, May 2005 [PDF]

Reduced State Routing in the Internet, Ramakrishna Gummadi, Nupur Kothari, Young-Jin Kim, Ramesh Govindan, Brad Karp, Scott Shenker, Proceedings of Hotnets-III, 2004 [PDF]

Practical and robust geographic routing in wireless networks, Young-Jin Kim, Ramesh Govindan, Brad Karp, Scott Schenker, Technical Report 04-832, Department of Computer Science, University of Southern California, 2004 [PDF]

Presenations

Young-Jin Kim.ACM SenSys'06 conference talk. Boulder, CO. Nov, 2006.

Young-Jin Kim.USENIX NSDI'05 conference talk. Boston, MA. May, 2005.

Young-Jin Kim.Poster at CENS 3rd Annual Research Review. UCLA. Oct/28/2005.

Software

CLDP software combined with GPSR running on Mica can be downloaded [ here]


Last Modified: 15 Jan 2006