Lazy cross-link removal for geographic routing

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. Net-