Geographic Routing Rik Sarkar Routing in ad hoc networks Obtain route information between pairs of nodes wishing to communicate Proactive protocols maintain routing tables at each node that is updated as changes in the network topology are detected Heavy overhead with high network dynamics caused by link node failures or node movement Not practical for ad hoc networks Routing in ad hoc networks Reactive protocols routes are constructed on demand No global routing table is maintained Due to the high rate of topology changes reactive protocols are more appropriate for ad hoc networks Ad hoc on demand distance vector routing AODV Dynamic source routing DSR However both depend on flooding for route discovery Geographical routing Geographical routing uses a node s location to discover path to that node y Greedy Routing Forward to the neighbor that is nearest to the destination x Geographical routing Assumptions Nodes know their own geographical location Nodes know their 1 hop neighbors Routing destinations are specified geographically a location or a geographical region Each packet can hold a small amount O 1 of routing information Problem with Greedy Routing It can get stuck at a local minimum Exercises What is a hole What is a type of hole for which greedy routing works Face Routing Use a planar graph Keep left hand on the wall walk until hit the straight line connecting source to destination Then switch to the next face Face Routing Keep left hand on the wall walk until hit the straight line connecting source to destination Then switch to the next face s t Face Routing s t Face Routing s t Face Routing s t Face Routing s t Face Routing s t Face Routing s t Face Routing s t Face Routing Properties All necessary information is stored in the message Source and destination positions The node when it enters face routing mode The first edge on the current face Completely local Knowledge about direct neighbors positions is sufficient Faces are implicit Only local neighbor ordering around each node is needed Right Hand Rule What if the destination is disconnected Face routing will get back to where it enters the perimeter mode Failed no way to the destination Guaranteed delivery of a message if there is a path An example of UDG 200 nodes randomly deployed in a 2000 2000 meters region Radio range 250meters Face routing needs a planar graph Compute a planar subgraph of the unit disk graph Preserves connectivity Distributed computation Relative Neighborhood Graph and Gabriel Graph Relative Neighborhood Graph RNG contains an edge uv if the lune is empty of other points Gabriel Graph GG contains an edge uv if the disk with uv as diameter is empty of other points Both can be constructed in a distributed way Planarity of Gabriel Graph Theorem Gabriel graph does not contain crossing edges u Suppose p and q are mid points of xy and uv Also assume zv zu zx zy q x z p v y We want to show pv px or qx qv Planarity of Gabriel Graph Suppose not pv px and Then pv qx px qv qx qv u pv pz zv qx qz zx q x pv qx px qv z p v y Contradiction Relative Neighborhood Graph and Gabriel Graph Claim MST RNG GG Thus RNG and GG are planar and keep the connectivity MST has the same connectivity of UDG An example of GG and RNG GG RNG Two problems remain Both RNG and GG remove some edges a short path may not exist The shortest path on RNG or GG might be much longer than the shortest path on the original network Even if the planar subgraph contains a short path can greedy routing and face routing find a short one Bad news Lower bound of localized routing Any deterministic or randomized localized routing algorithm takes a path of length k2 if the optimal path has length k The adversary decides where the chain wt is Since we store no information on nodes in the worst case we have to visit about k chains and pay a cost of k2 t s Good news greedy forwarding is optimal If greedy routing gets to the destination then the path length is at most O k2 if the optimal path has length k uv is at most k On the greedy path every other node is not visible so they are of distance at least 1 away By a packing lemma there are at most O k2 nodes inside a disk of radius k How is face routing Face routing can be bad O n Adaptive Face Routing Suppose the shortest path on the planar graph is bounded by L hops Bound the search area by an ellipsoid x xs xt L never walk outside the ellipsoid Follow one direction if we hit the ellipsoid turn back In the worst case visit every node inside the ellipsoid About O L2 by the bounded density property Adaptive Face Routing How to guess the upper bound L Start from a small value say st if we fail to find a path then we double L and rerun adaptive face routing By the time we succeed L is at most twice the shortest path length k The number of phases is O log k Total cost O i k 2i 2 O k2 asymptotically Combine Greedy and Face Routing Route greedy till it gets stuck at some node p Switch to face routing When at some node q which is nearer to destination than p switch back to greedy Called Greedy Face Greedy strategy Many Variations on these strategies Beyond point to point routing Multicast to a geographic region Use geographic routing to get to a node in the region Use restricted flooding inside Routing on a curve Route on a parametric curve x t y t The protocols in practice Locations are not always known Communication ranges are not disks Planar graph construction fails Picture Govindan et al Experiment GPSR succeeds in 68 2 directed pairs Alternative Cross link detection protocol Detects crossing links and appropriately does routing on non planar graphs Different Idea Virtual Coordinates Instead of finding actual locations we want to give a coordinate to each node Can we create coordinates so that greedy routing works Rubberband Representation All edges are rubberbands Nail down some nodes and let the graph go Theorem Converges to unique state Rubber band drawing of a graph Rubber band drawing of a graph Rubber band drawing of a graph Examples Rubberband Algorithm Rao Papadimitriou Shenker Mobicom 03 NoGeo A network with 3200 Nodes After 10 iterations After 100 iterations After 1000 iterations Resilience Not all perimeter nodes are known Different shapes Bad cases Tan Bertier Kermarrec Infocom 2009 Question Can you think of a Virtual Coordinate scheme that works better