GPSR: Greedy Perimeter Stateless Routing for Wireless NetworksMotivationScalability metricsAssumptionsGeographic Routing: Greedy RoutingBenefits of GFGreedy Forwarding does NOT always workSlide 8Right Hand Rule on Convex SubdivisionSlide 10Slide 11Make a Graph PlanarSlide 13Slide 14Properties of GG and RNGConnectedness of RNG GraphExamplesGreedy Perimeter Stateless Routing (GPSR)GPSRImplementation IssuesPerformance evaluationSlide 22Packet Delivery Success RateRouting Protocol OverheadRelated WorkSlide 26Questions?1GPSR: Greedy Perimeter Stateless Routing for Wireless NetworksB. Karp, H. T. KungBorrowed some slides from Richard Yang’s2MotivationA sensor net consists of hundreds or thousands of nodesScalability is the issueExisting ad hoc net protocols, e.g., 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 routing3Scalability metricsRouting protocol msg costHow many control packets sent?Per node stateHow much storage per node is required?E2E packet delivery success rate4AssumptionsEvery node knows its locationPositioning devices like GPS LocalizationA source can get the location of the destination802.11 MACLink bidirectionality5Geographic Routing: Greedy RoutingSDClosest to DA- Find neighbors who are the closer to the destination- Forward the packet to the neighbor closest to the destination6Benefits of GFA node only needs to remember the location info of one-hop neighborsRouting decisions can be dynamically made7Greedy 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 succeedGF fails8Dealing 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 maze9Right Hand Rule on Convex SubdivisionFor convex subdivision, right hand rule is equivalent to traversing the face with the crossing edges removed.10Right-Hand Rule Does Not Work with Cross EdgesuzwDx x originates a packet to u Right-hand rule results in the tour x-u-z-w-u-x11Remove Crossing EdgeuzwDxMake the graph planar Remove (w,z) from the graph Right-hand rule results in the tour x-u-z-v-x12Make a Graph PlanarConvert a connectivity graph to planar non-crossing graph by removing “bad” edgesEnsure the original graph will not be disconnectedTwo types of planar graphs: •Relative Neighborhood Graph (RNG)•Gabriel Graph (GG)13Relative Neighborhood GraphConnection uv can exist if w  u, v, d(u,v) < max[d(u,w),d(v,w)]not empty  remove uv14Gabriel GraphAn edge (u,v) exists between vertices u and v if no other vertex w is present within the circle whose diameter is uv.w  u, v, d2(u,v) < [d2(u,w) + d2(v,w)]Not empty  remove uv15Properties of GG and RNGRNG is a sub-graph of GGBecause RNG removes more edgesIf the original graph isconnected, RNG is also connectedRNGGG16Connectedness of RNG GraphKey observationAny edge on the minimumspanning tree of the originalgraph is not removedProof by contradiction: Assume (u,v) is such an edge but removed in RNGuvw17• 200 nodes• randomly placed on a 2000 x 2000 meter region• radio range of 250 m•Bonus: remove redundant, competing path  less collisionFull graph GG subset RNG subsetExamples18Greedy Perimeter Stateless Routing (GPSR)Maintenanceall nodes maintain a single-hop neighbor tableUse RNG or GG to make the graph planarAt source: mode = greedyIntermediate node:if (mode == greedy) {greedy forwarding;if (fail) mode = perimeter;}if (mode == perimeter) {if (have left local maxima) mode = greedy; else (right-hand rule);}19GPSRGreedy Forwarding Perimeter Forwardinggreedy failshave left local maximagreedy worksgreedy fails20Implementation IssuesGraph planarizationRNG & GG planarization depend on having the current location info of a node’s neighborsMobility may cause problemsRe-planarize when a node enters or leaves the radio range•What if a node only moves in the radio range?•To avoid this problem, the graph should be re-planarize for every beacon msgAlso, assumes a circular radio transmission modelIn general, it could be harder & more expensive than it sounds21Performance evaluationSimulation in ns-2Baseline: DSR (Dynamic Source RoutingRandom waypoint modelA node chooses a destination uniformly at randomChoose velocity uniformly at random in the configurable range – simulated max velocity 20m/sA node pauses after arriving at a waypoint – 300, 600 & 900 pause times2250, 112 & 200 nodes22 sending nodes & 30 flowsAbout 20 neighbors for each node – very denseCBR (2Kbps)Nominal radio range: 250m (802.11 WaveLan radio)Each simulation takes 900 secondsTake an average of the six different randomly generated motion patterns23Packet Delivery Success Rate24Routing Protocol Overhead25Related WorkGeographic and Energy Aware Routing (GEAR), UCLA Tech Report, 2000Consider remaining energy in addition to geographic location to avoid quickly draining energy of the node closest to the destinationGeographic probabilistic routing, International workshop on wireless ad-hoc networks, 2005Determine the packet forwarding probability to each neighbor based on its location, residual energy, and link reliability26Beacon vector routing, NSDI 2005Beacons know their locationsForward a packet towards the beaconA Scalable Location Service for Geographic Ad Hoc Routing, MobiCom ’00Distributed location serviceLandmark routingPaul F. Tsuchiya. Landmark routing: Architecture, algorithms and issues. Technical Report MTR-87W00174, MITRE Corporation, September 1987.Classic work with many