Geographic RoutingRik SarkarRouting 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’slocation to discover path to that node.xyGreedy Routing: Forward to the neighbor that is nearest to the destinationGeographical 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 RoutingIt can get stuck at a local minimumExercises: 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 RoutingFace Routing• Keep left hand on the wall, walk until hit the straight line connecting source to destination.• Then switch to the next face.s tFace RoutingFace Routings tFace RoutingFace Routings tFace RoutingFace Routings tFace RoutingFace Routings tFace RoutingFace Routings tFace RoutingFace Routings tFace RoutingFace Routings t• 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.Face Routing Properties“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 UDG200 nodes randomly deployed in a 2000×2000 meters region. Radio range =250metersFace 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.uvyxpqzSuppose p and q are mid points of xy and uv.Also assume : zv < zuzx < zyWe want to show: pv < px or qx < qvPlanarity of Gabriel Graph• Suppose not : pv > px and qx > qv• Then pv + qx > px + qvuvyxpqzpv < pz + zvqx < qz + zxpv + qx < px + qv-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 RNGGGRNGTwo 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 localizedrouting 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).tsGood 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). asymptoticallyCombine 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 strategyMany Variations on these strategiesBeyond 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 failsPicture : Govindan et al.Experiment• GPSR succeeds in 68.2% directed pairsAlternative:• 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 graphRubber band drawing of a graphRubber band