Abstract

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

Geographic techniques promise highly scalable any-toany routing in wireless sensor networks. In one thread of research on geographic routing, researchers have explored robust, distributed graph planarization. Arguing that such planarization techniques have high overhead, researchers have more recently pursued a thread in which they propose precomputation of routing structures (e.g., hull trees and grids) to achieve low-overhead geographic routing. In this paper we introduce a third approach, LCR, that does not involve any precomputation of distributed routing structures, nor full a priori planarization. Instead, LCR removes non-planarities lazily only when they interfere with correct geographic routing. Lazy removal of link crossings results in an order of magnitude or more lower overhead than any previously proposed approach.

@inproceedings{Kim06,
	author = {Young-Jin Kim and Ramesh Govindan and Brad Karp and Scott Shenker},
	title = {{Lazy Cross-Link Removal for Geographic Routing}},
	booktitle = "Proceedings of the ACM Conference on Embedded Networked Sensor Systems (Sensys)",
	year = "2006",
	month = "November",
	address = "Boulder, Colorado, USA",
}