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. Motivation. A sensor net consists of hundreds or thousands of nodes Scalability is the issue

Share Presentation

Embed Code

Link

• very dense
• geographic ad hoc routing
• next anticlockwise edge
• routing decisions
• circular radio transmission model
• full graph

sandra_john + Follow

GPSR: Greedy Perimeter Stateless Routing for Wireless Networks

An Image/Link below is provided (as is) to download presentation Download Policy: Content on the Website is provided to you AS IS for your information and personal use and may not be sold / licensed / shared on other websites without getting consent from its author. Content is provided to you AS IS for your information and personal use only. Download presentation by click this link. While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server. During download, if you can't get a presentation, the file might be deleted by the publisher.

Presentation Transcript

1. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks B. Karp, H. T. KungBorrowed some slides from Richard Yang’s
2. 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
3. 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
4. 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
5. Closest to D A Geographic Routing: Greedy Routing S D • Find neighbors who are the closer to the destination • Forward the packet to the neighbor closest to the destination
6. Benefits of GF • A node only needs to remember the location info of one-hop neighbors • Routing decisions can be dynamically made
7. 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
8. 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
9. Right Hand Rule on Convex Subdivision For convex subdivision, right hand rule is equivalent to traversing the face with the crossing edges removed.
10. Right-Hand Rule Does Not Work with Cross Edges z u D • x originates a packet to u • Right-hand rule results in the tour x-u-z-w-u-x w x
11. Remove Crossing Edge z u D • Make the graph planar • Remove(w,z)from the graph • Right-hand rule results in the tour x-u-z-v-x w x
12. 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)
13. 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
14. 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
15. Properties of GG and RNG RNG • RNG is a sub-graph of GG • Because RNG removes more edges • If the original graph isconnected, RNG is also connected GG
16. w Connectedness 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 RNG u v
17. 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
18. 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)
19. greedy fails GPSR Greedy Forwarding Perimeter Forwarding have left local maxima greedy works greedy fails
20. 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 re-planarize for every beacon msg • Also, assumes a circular radio transmission model • In general, it could be harder & more expensive than it sounds
21. 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
22. 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
23. Packet Delivery Success Rate
24. Routing Protocol Overhead
25. 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
26. 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 follow-ups
27. Questions?

• Related
• More by User

Cooperative Diversity Techniques for Wireless Networks

Cooperative Diversity Techniques for Wireless Networks. Arun ‘Nayagam Wireless Information Networking Group (WING) Department of Electrical and Computer Engineering University of Florida. Introduction. Antenna arrays commonly used to achieve receive diversity

1.31k views • 32 slides

Chapter 6 Wireless and Mobile Networks

Chapter 6 Wireless and Mobile Networks. Computer Networking: A Top Down Approach 4 th edition. Jim Kurose, Keith Ross Addison-Wesley, July 2007. . Background: # wireless (mobile) phone subscribers now exceeds # wired phone subscribers!

1.71k views • 114 slides

Principles of Electronic Communication Systems

Principles of Electronic Communication Systems. Third Edition Louis E. Frenzel, Jr. Chapter 21. Wireless Technologies. Topics Covered in Chapter 21. 21-1: Wireless LAN 21-2: PANs and Bluetooth 21-3: ZigBee and Mesh Wireless Networks 21-4: WiMAX and Metropolitan-Area Networks

2.62k views • 65 slides

Chapter 9: Transport Layer and Security Protocols for Ad Hoc Wireless Networks

Introduction Issues Design Goals Classifications TCP Over Ad Hoc Wireless Networks Other Transport Layer Protocols. Security in Ad Hoc Wireless Networks Network Security Requirements Issues and challenges in security Network security attacks Key Management Secure Routing.

4.26k views • 85 slides

Course: Wireless Networks I Topic : A nalysis of MANETs and Network Coding

Course: Wireless Networks I Topic : A nalysis of MANETs and Network Coding. Ubinet Master 2011-2012 L. Sassatelli sassatelli@i3s.unice.fr. Outline. Delay-Throughput trade-offs: Static ad hoc networks under the physical and protocols models Mobile ad hoc networks

1.54k views • 118 slides

Wireless Ad Hoc & Sensor Networks

Wireless Ad Hoc & Sensor Networks. Nordic Radio Symposium 2004 August 16 – 18, 2004 University of Oulu, Finland Presenter: Carlos Pomalaza-Ráez carlos@ee.oulu.fi http://www.ee.oulu.fi/~carlos/NRS_04_Tutorial.ppt. Outline. Mobile Ad Hoc Networks (MANETs) Main features

1.6k views • 117 slides

Routing

CCNA Discovery 2: Chapter 6. Routing. Contents. 6.1: Routing Protocols 6.1.1 : Routing 6.1.2 : Routing Protocols 6.1.3 : RIP, EIGRP, OSPF 6.1.4: Routing Metrics 6.1.5: RIP configuration 6.2: Exterior Routing Protocols 6.2.1 : Autonomous Systems 6.2.2: Routing Across the Internet

1.24k views • 71 slides

Vehicular Ad hoc Networks (VANET)

Vehicular Ad hoc Networks (VANET). Wireless Networks. 2008/10/1. A taxonomy of wireless networks. 4. 2008/10/1. Examples. Ad Hoc Networks. Non-infrastructure Fixed and Mobile Nodes Special Classes of Ad Hoc Networks Vehicular Ad Hoc Networks Wireless Mesh Networks

3.33k views • 78 slides

Multi-Channel Wireless Networks: Theory to Practice

Network-Aware Distributed Algorithms for Wireless Networks Nitin Vaidya Electrical and Computer Engineering University of Illinois at Urbana-Champaign. Multi-Channel Wireless Networks: Theory to Practice. Nitin Vaidya Electrical and Computer Engineering

1.08k views • 95 slides

Chapter 7 Packet-Switching Networks

Chapter 7 Packet-Switching Networks. Chapter 7 Packet-Switching Networks. Network Services and Internal Network Operation Packet Network Topology Datagrams and Virtual Circuits Routing in Packet Networks Shortest Path Routing ATM Networks Traffic Management.

1.8k views • 151 slides

Computer Networks (Graduate level)

Computer Networks (Graduate level). Lecture 10: Inter-domain Routing. University of Tehran Dept. of EE and Computer Engineering By: Dr. Nasser Yazdani. Inter-Domain Routing. Border Gateway Protocol (BGP) Assigned reading [LAB00] Delayed Internet Routing Convergence Sources

1.29k views • 111 slides

Chapter 05 Ad Hoc Networks

Chapter 05 Ad Hoc Networks. Outline. Introduction Unicast routing TCP on Mobile Ad Hoc Networks Selected security issues. 5.1 Mobile Ad Hoc Networks (MANET) Introduction and Generalities. 5.1.1 Mobile Ad Hoc Networks. Formed by wireless hosts which may be mobile

2.23k views • 187 slides

Leader Election and Mutual Exclusion Algorithms for Wireless Ad Hoc Networks.

Leader Election and Mutual Exclusion Algorithms for Wireless Ad Hoc Networks. CPSC 661 Distributed Algorithms Abhishek Gaurav Alok Madhukar. Part 1: Leader Election Algorithms for Wireless Ad Hoc Networks. What is a mobile ad hoc network? Use of Leader election in mobile systems

1.29k views • 103 slides

Wireless Personal area networks WPANs

Wireless Personal area networks WPANs. By Engr. Sherjeel Farooqui. WAN 2G, 3G 2km/link national areas. MAN 802.16 2-6km. PAN 802.15.x 10m. LAN 802.11 100m. Overview of wireless networks. IEEE 802.15 - General. Wireless Personal Area Networks (WPANs) Short Range Low Power

1.42k views • 80 slides

IP Routing

IP Routing. Section A : Introduction to IP Routing Section B : Routing Information Protocol (RIP) (Intra –AS), Open Shortest Path First (OSPF). Section C : CIDR, Inter-AS Routing: BGP (Inter-AS). Section A IP Routing. Routing: Process of choosing a path over which to send packets.

2.09k views • 111 slides

Ch1 Introduction to Wireless Communications & Networks

Ch1 Introduction to Wireless Communications & Networks. Reading materials : [1]Overview of wireless communications [2] 移动通讯词汇（中英）. Outline. Part 1 Introduction to Wireless Communication & Networks Part 2 Applications of Wireless Networks.

1.63k views • 91 slides

Chapter 4: Network Layer

4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6. 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP

1.69k views • 142 slides

WIRELESS SENSOR NETWORKS

WIRELESS SENSOR NETWORKS. `. T opics. Introduction What are WSNs? An example: ESB WSN applications Energy conservation Ad-hoc routing Basic principles Overview of routing protocols Data-centric protocols Rumor Routing Geogra phical protocols. Localization and Positioning

1.54k views • 105 slides

Emerging Concepts and Technologies towards 5G Wireless Networks

Emerging Concepts and Technologies towards 5G Wireless Networks. Halim Yanıkömeroğlu Carleton University Ottawa, Canada. Outline. Part I: 16:00 – 16:45 1. The new wireless 2. Generations of cellular technologies 3. What we know and what we don’t know

1.55k views • 123 slides

Chapter 8: Troubleshooting Converged Networks

Chapter 8: Troubleshooting Converged Networks. CCNP TSHOOT: Maintaining and Troubleshooting IP Networks. Chapter 8 Objectives. Troubleshoot Wireless issues in a converged network supporting wireless devices and clients.

1.48k views • 124 slides

UNIT-7

UNIT-7. Mobile Ad hoc Networks. Contents. Syllabus from chapter 15, 17 in handbook of wireless networks and mobile computing. By Ivan Stojmenovic. MANET overview Properties of MANET MANET applications Routing and various routing algorithms Unicast routing protocols for MANET

1.22k views • 94 slides