GPSR: Greedy Perimeter Stateless Routing for Wireless Networks

Chia sẻ: Hoang Huy Dong | Ngày: | Loại File: PPT | Số trang:27

Thêm vào BST

Báo xấu

98
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: GPSR: Greedy Perimeter Stateless Routing for Wireless Networks

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 Scalability is the issue r Existing ad hoc net protocols, e.g., DSR, AODV, ZRP, require nodes to cache e2e route information r Dynamic topology changes r Mobility Ì Reduce caching overhead r Hierarchical routing is usually based on well defined, rarely changing administrative boundaries r Geographic routing • Use location for routing 2
Scalability metrics Ì Routing protocol msg cost r How many control packets sent? Ì Per node state r How much storage per node is required? Ì E2E packet delivery success rate 3
Assumptions Ì Every node knows its location r Positioning devices like GPS r Localization Ì A source can get the location of the destination Ì 802.11 MAC Ì Link bidirectionality 4
Geographic Routing: Greedy Routing Closest to D S D A - 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 onehop 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: RightHand Rule Ì Apply the righthand rule to traverse the edges of a void r Pick the next anticlockwise edge r 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
RightHand Rule Does Not Work with Cross Edges z u D x originates a packet to u  w Right-hand rule results in the  tour x-u-z-w-u-x x 10
Remove Crossing Edge z u D Make the graph planar w Remove (w,z) from the graph x Right-hand rule results in the  tour x-u-z-v-x 11
Make a Graph Planar  Convert a connectivity graph to planar noncrossing graph by removing “bad” edges Ensure the original graph will not be disconnected r Two types of planar graphs: r • Relative Neighborhood Graph (RNG) • Gabriel Graph (GG) 12
Relative Neighborhood Graph Ì Connection uv can exist if ∀w ≠ u, v, d(u,v)
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)
Properties of GG and RNG RNG Ì RNG is a subgraph of GG Because RNG removes more r edges GG Ì If the original graph is connected, RNG is also connected 15
Connectedness of RNG Graph Ì Key observation r Any edge on the minimum spanning tree of the original graph is not removed r 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 collision 17
Greedy Perimeter Stateless Routing (GPSR) Ì Maintenance all nodes maintain a singlehop neighbor table r Use RNG or GG to make the graph planar r Ì At source: mode = greedy r Ì Intermediate node: if (mode == greedy) { r greedy forwarding; if (fail) mode = perimeter; } if (mode == perimeter) { if (have left local maxima) mode = greedy; else (righthand rule); } 18
GPSR greedy fails Greedy Forwarding Perimeter Forwarding have left local maxima greedy works greedy fails 19
Implementation Issues Ì Graph planarization r RNG & GG planarization depend on having the current location info of a node’s neighbors r Mobility may cause problems r Replanarize 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 r r In general, it could be harder & more expensive than it sounds 20