After Hours

Geographic Routing Without Planarization

Date Added: Jan 2011
Format: PDF

The authors present a new geographic routing algorithm, the Greedy Distributed Spanning Tree Routing (GDSTR), that finds shorter routes and generates less maintenance traffic than previous algorithms. While geographic routing potentially scales well, it faces the problem of what to do at local dead ends where greedy forwarding fails. Existing geographic routing algorithms handle dead ends by planarizing the node connectivity graph and then using the right-hand rule to route around the resulting faces.