GPSR: Greedy Perimeter Stateless Routing for Wireless Networks B. Karp, H. T. Kung Borrowed some slides from Richard Yang’s 1 .Motivation Ì A sensor net consists of hundreds or thousands of nodes r | GPSR: Greedy Perimeter Stateless Routing for Wireless Networks B. Karp, H. T. Kung Borrowed some slides from Richard Yang’s Motivation A sensor net consists of hundreds or thousands of nodes Scalability is the issue Existing ad hoc net protocols, ., DSR, AODV, ZRP, require nodes to cache e2e route information Dynamic topology changes Mobility Reduce caching overhead Hierarchical routing is usually based on well defined, rarely changing administrative boundaries Geographic routing Use location for routing Scalability metrics Routing protocol msg cost How many control packets sent? Per node state How much storage per node is required? E2E packet delivery success rate Assumptions Every node knows its location Positioning devices like GPS Localization A source can get the location of the destination MAC Link bidirectionality Geographic Routing: Greedy Routing S D Closest to D A Find neighbors who are the closer to the destination Forward the packet to the . | GPSR: Greedy Perimeter Stateless Routing for Wireless Networks B. Karp, H. T. Kung Borrowed some slides from Richard Yang’s Motivation A sensor net consists of hundreds or thousands of nodes Scalability is the issue Existing ad hoc net protocols, ., DSR, AODV, ZRP, require nodes to cache e2e route information Dynamic topology changes Mobility Reduce caching overhead Hierarchical routing is usually based on well defined, rarely changing administrative boundaries Geographic routing Use location for routing Scalability metrics Routing protocol msg cost How many control packets sent? Per node state How much storage per node is required? E2E packet delivery success rate Assumptions Every node knows its location Positioning devices like GPS Localization A source can get the location of the destination MAC Link bidirectionality Geographic Routing: Greedy Routing S D Closest to D A Find neighbors who are the closer to the destination Forward the packet to the neighbor closest to the destination Benefits of GF A node only needs to remember the location info of one-hop neighbors Routing decisions can be dynamically made Greedy Forwarding does NOT always work If the network is dense enough that each interior node has a neighbor in every 2 /3 angular sector, GF will always succeed GF fails Dealing with Void: Right-Hand Rule Apply the right-hand rule to traverse the edges of a void Pick the next anticlockwise edge Traditionally used to get out of a maze Right Hand Rule on Convex Subdivision For convex subdivision, right hand rule is equivalent to traversing the face with the crossing edges removed. Right-Hand Rule Does Not Work with Cross Edges u z w D x x originates a packet to u Right-hand rule results in the tour x-u-z-w-u-x Remove Crossing Edge u z w D x Make the graph planar Remove (w,z) from the graph Right-hand rule results in the tour x-u-z-v-x Make a Graph Planar Convert a connectivity graph to planar non-crossing
