GPSR: Greedy Perimeter Stateless Routing for Wireless Networks

ppt
Số trang GPSR: Greedy Perimeter Stateless Routing for Wireless Networks 27 Cỡ tệp GPSR: Greedy Perimeter Stateless Routing for Wireless Networks 305 KB Lượt tải GPSR: Greedy Perimeter Stateless Routing for Wireless Networks 0 Lượt đọc GPSR: Greedy Perimeter Stateless Routing for Wireless Networks 3
Đánh giá GPSR: Greedy Perimeter Stateless Routing for Wireless Networks
4.7 ( 19 lượt)
Nhấn vào bên dưới để tải tài liệu
Để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

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     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 routing 2 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 3 Assumptions  Every node knows its location  Positioning devices like GPS  Localization  A source can get the location of the destination  802.11 MAC  Link bidirectionality 4 Geographic Routing: Greedy Routing Closest to D S A D - Find neighbors who are the closer to the destination - Forward the packet to the neighbor closest to the destination 5 Benefits of GF  A node only needs to remember the location info of one-hop neighbors  Routing decisions can be dynamically made 6 Greedy Forwarding does NOT always work GF fails  If the network is dense enough that each interior node has a neighbor in every 2/ 3 angular sector, GF will always succeed 7 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 8 Right Hand Rule on Convex Subdivision For convex subdivision, right hand rule is equivalent to traversing the face with the crossing edges removed. 9 Right-Hand Rule Does Not Work with Cross Edges z u D  w x originates a packet to u Right-hand rule results in the tour x-u-z-w-u-x  x 10 Remove Crossing Edge z u D Make w the graph planar Remove x (w,z) from the graph Right-hand rule results in the tour x-u-z-v-x  11 Make 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) 12 Relative Neighborhood Graph  Connection uv can exist if w  u, v, d(u,v) < max[d(u,w),d(v,w)] not empty  remove uv 13 Gabriel 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 uv 14 Properties of GG and RNG  RNG is a sub-graph of RNG GG  Because RNG removes more edges GG  If the original graph is connected, RNG is also connected 15 Connectedness of RNG Graph  Key observation  Any edge on the minimum spanning tree of the original graph is not removed  Proof by contradiction: Assume (u,v) is such an edge but removed in RNG w u v 16 Examples Full graph GG subset RNG subset • 200 nodes • randomly placed on a 2000 x 2000 meter region • radio range of 250 m •Bonus: remove redundant, competing path  less 17 Greedy 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); } 18 GPSR greedy fails Greedy Forwarding greedy works Perimeter Forwarding have left local maxima greedy fails 19 Implementation 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 replanarize for every beacon msg  Also, assumes a circular radio transmission model  In general, it could be harder & more expensive than it sounds 20 Performance 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 times 21  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 patterns 22 Packet Delivery Success Rate 23 Routing Protocol Overhead 24 Related 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 reliability 25  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 MTR87W00174, MITRE Corporation, September 1987.  Classic work with many follow-ups 26 Questions? 27
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.