Geographic Routing with Local Face Information without Planarization
Geographic routing also called position-based routing is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. The paper designs new geographic routing algorithms, namely Greedy Distributed Spanning Tree Routing (GDSTR) and Greedy Embedding Spring Coordinates (GSpring).GDSTR that finds shorter routes and generates less maintenance traffic. 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.