Article

Free access

GPSR: greedy perimeter stateless routing for wireless networks

Authors:

H. T. KungAuthors Info & Claims

MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking

Pages 243 - 254

https://doi.org/10.1145/345910.345953

Published: 01 August 2000 Publication History

Abstract

We present Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet's destination to make packet forwarding decisions. GPSR makes greedy forwarding decisions using only information about a router's immediate neighbors in the network topology. When a packet reaches a region where greedy forwarding is impossible, the algorithm recovers by routing around the perimeter of the region. By keeping state only about the local topology, GPSR scales better in per-router state than shortest-path and ad-hoc routing protocols as the number of network destinations increases. Under mobility's frequent topology changes, GPSR can use local topology information to find correct new routes quickly. We describe the GPSR protocol, and use extensive simulation of mobile wireless networks to compare its performance with that of Dynamic Source Routing. Our simulations demonstrate GPSR's scalability on densely deployed wireless networks.

References

[1]

ABRAMSON, N. The ALOHA system- another alternative for computer communications. AFIPS 37 (1970), 281-285.

[2]

BHARGHAVAN, A., DEMERS, S., SHENKER, $., AND ZHANG, L. MACAW: A media access protocol for wireless LANs. In Proceedings of the SIGCOMM '94 Conference on Communications, Architectures, Protocols, and Applications (Sept. 1994), pp. 212-225.

Digital Library

[3]

BOSE, P., MORIN, P., STOJMENOVi(~, I., AND URRUTIA, J. Routing with guaranteed delivery in ad hoc wireless networks. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DialM '99), Aug. 1999.

Digital Library

[4]

BROCH, J., MALTZ, D., JOHNSON, D., HU, Y., AND JETCHEVA, J. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Proceedings of the Fourth Annual A CM/IEEE International Conference on Mobile Computing and Networking (MobiCom '98) (Dallas, Texas, USA, Aug. 1998).

Digital Library

[5]

CALl, F., CONTI, M., AND GREGORI, E. IEEE 802.11 wireless LAN: capacity analysis and protocol enhancement. In Proceedings of lEEE INFOCOM 1998 (San Francisco, California, March/April 1998), p. 142.

[6]

CHANDRAKASAN, A., AMIRTHARAJAH, R., CHO, $., GOODMAN, J., KONDURI, G., KULIK, J., RABINER, W., AND WANG, A. Design considerations for distributed microsensor systems. In Proceedings of the IEEE 1999 Custom Integrated Circuits Conference (CICC '99) (May 1999), pp. 279-286.

[7]

FINN, G. G. Routing and addressing problems in large metropolitan-scale intemetworks. Tech. Rep. ISI/RR-87-180, Information Sciences Institute, Mar. 1987.

[8]

FLOYD, S., AND JACOBOSON, V. The synchronization of periodic routing messages. IEEE/ACM Transactions on Networking 2, 2 (April 1994), 122--136.

Digital Library

[9]

GABRIEL, K., AND SOKAL, R. A new statistical approach to geographic variation analysis. Systematic Zoology 18 (1969), 259-278.

[10]

HAAS, Z., AND PEARLMAN, M. The performance of query control schemes for the zone routing protocol. In Proceedings of the SIGCOMM '98 Conference on Communications Architectures, Protocols and Applications (Sept. 1998).

Digital Library

[11]

IEEE COMPUTER SOCIETY LAN MAN STANDARDS COMMITTEE. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Std. 802.11-1997, 1997.

[12]

JOHNSON, D. B., AND MALTZ, D. B. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, T. Imielinski and H. Korth, Eds. Kluwer Academic Publishers, 1996, ch. 5, pp. 153-181.

[13]

KAHN, J. M., KATZ, R. H., AND PiSTER, K. S. J. Mobile networking for smart dust. In Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '99) (Seattle, WA, USA, Aug. 1999).

Digital Library

[14]

KARN, P. MACA--a new channel access method for packet radio. In Proceedings of the 9th Computer Networking Conference (Sept. 1990), pp. 134-140.

[15]

KARP, B. Geographic routing for wireless networks. Presentation at AFOSR MURI ACTCOMM Research Review Meeting, Oct. 1998.

[16]

KARP, B. Greedy perimeter state routing. Invited Seminar at the USCAnformation Sciences Institute, July 1998.

[17]

Ko, Y., AND VAIDYA, N. Location-aided routing in mobile ad hoc networks. In Proceedings of the Fourth Annual A CM/IEEE International Conference on Mobile Computing and Networking (MobiCom '98) (Dallas, Texas, USA, Aug. 1998).

Digital Library

[18]

LI, J., JANNOTTI, J., DECOUTO, D., KARGER, D., AND MORRIS, R. A scalable location service for geographic ad-hoc routing. In Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000) (Boston, MA, USA, Aug. 2000).

Digital Library

[19]

MALTZ, D., BROCH, J., JETCHEVA, J., AND JOHNSON, O. The effects of on-demand behavior in routing protocols for multihop wireless ad hoc networks. IEEE Journal on Selected Areas in Communications 17, 8 (Aug. 1999), 1439-1453.

Digital Library

[20]

PARK, V., AND CORSON, M. A highly adaptive distributed routing algorithm for mobile wireless networks. In Proceedings of the Conference on Computer Communications (IEEE lnfocom) (Kobe, Japan, Apr. 1997), pp. 1405-1413.

Digital Library

[21]

PERKINS, C. Ad hoc on demand distance vector (AODV) routing. Interact-Draft, draft-ietf-manet-aodv-04.txt, Oct. 1999.

Digital Library

[22]

PERKINS, C., AND BHAGWAT, P. Highly-dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. In Proceedings of the SiGCOMM '94 Conference on Communications, Architectures, Protocols, and Applications (London, UK, Sept. 1994), pp. 234-244.

Digital Library

[23]

SALTZER, J., REED, D. P., AND CLARK, D. End-to-end arguments in system design. ACM Transactions on Computer Systems 2, 4 (Nov. 1984), 277-288.

Digital Library

[24]

SHEPARD, T. A channel access scheme for large dense packet radio networks. In Proceedings of the SIGCOMM '96 Conference on Communications Architectures, Protocols and Applications (Aug. 1996).

Digital Library

[25]

THE CMU MONARCH GROUP. Wireless and Mobility Extensions to ns-2. http://www, monarch.cs.cmu.edu/cmu-ns.html, Oct. 1999.

[26]

THE VINT PROJECT. The UCB/LBNIdVINT Network Simulator--ns (version 2). http://mash.cs.berkeley, edu/ns.

[27]

TOUSSAINT, G. The relative neighborhood graph of a finite planar set,. Pattern Recognition 12, 4 (1980), 261-268.

[28]

WARD, A., JONES, A., AND HOPPER, A. A new location technique for the active office. IEEE Personal Communications 4, 5 (Oct. 1997), 42-47,

[29]

ZAUMEN, W., AND GARCIA-LUNA ACEVES, J. Dynamics of distributed shortest-path routing algorithms. In Proceedings of the SIGCOMM '91 Conference on Communications Architectures, Protocols and Applications (Sept. 1991), pp. 31--42.

Digital Library

Cited By

Lousada EFigueiredo F(2024)An approach for offloading with multi-hop considerations in an RSU signal overlay settingRevista de Gestão e Secretariado10.7769/gesec.v15i4.373915:4(e3739)Online publication date: 24-Apr-2024
https://doi.org/10.7769/gesec.v15i4.3739
R. MM. J(2024)Comprehensive Study on Routing in FANETIntelligent Decision Making Through Bio-Inspired Optimization10.4018/979-8-3693-2073-0.ch011(195-217)Online publication date: 24-May-2024
https://doi.org/10.4018/979-8-3693-2073-0.ch011
Duenas Santos CMezher AAstudillo León JCardenas Barrera JCastillo Guerra EMeng J(2024)Q-RPL: Q-Learning-Based Routing Protocol for Advanced Metering Infrastructure in Smart GridsSensors10.3390/s2415481824:15(4818)Online publication date: 25-Jul-2024
https://doi.org/10.3390/s24154818
Show More Cited By

GPSR: greedy perimeter stateless routing for wireless networks
1. Networks
  1. Network protocols
    1. Network layer protocols
  2. Network types

Recommendations

The Improvement of GPSR Routing Protocol in VANETs
ICECC '12: Proceedings of the 2012 International Conference on Electronics, Communications and Control

According to characteristics that the vehicles move fast and topology changes quickly in Vehicular Ad hoc Networks (VANETs), a novel routing protocol GMGP based on the location is proposed for VANETs, it is predicting the changes of the neighboring ...
Performance of GPSR and AOMDV in WSNs with Uncontrolled Mobility

Emergence and evolution of Wireless Sensor Networks (WSNs) opened the door for the development of many applications. Mobile Wireless Sensors Networks (MWSNs) is a subclass of WSNs in which some or all sensors are mobile. Although such mobility has ...
A New Improved GPSR (GPSR-kP) Routing Protocol for Multimedia Communication over Vehicular Ad hoc Network
BDAW '16: Proceedings of the International Conference on Big Data and Advanced Wireless Technologies

One of the main constraint in front of Vehicular Ad hoc Networks (VANETs) is delivering the data in efficient time. This paper provides an improved Greedy Perimeter Stateless Routing protocol (GPSR) to enhance the video quality transmission over VANETs. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking

August 2000

300 pages

ISBN:1581131976

DOI:10.1145/345910

Chairmen:
Raymond Pickholtz
George Washington Univ., Washington, DC
,
Sajal K. Das
Univ. of Texas at Arlington, Arlington
,
Ramon Caceres
AT&T Labs
,
J. J. Garcia-Luna-Aceves
Univ. of California, Santa Cruz, Santa Cruz

Copyright © 2000 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation
SIGCOMM: ACM Special Interest Group on Data Communication
SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing
IEICE: Inst of Electronics, Info & Communication Engineers
IFIP WG 6.3: IFIP WG 6.3

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

MobiCom00

Sponsor:

SIGMETRICS
SIGCOMM
SIGMOBILE
IEICE
IFIP WG 6.3

MobiCom00: The 6th Annual International Conference on Mobile Computing and Networking

August 6 - 11, 2000

Massachusetts, Boston, USA

Acceptance Rates

MobiCom '00 Paper Acceptance Rate 28 of 226 submissions, 12%;

Overall Acceptance Rate 440 of 2,972 submissions, 15%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5,391
Total Citations
View Citations
11,074
Total Downloads

Downloads (Last 12 months)797
Downloads (Last 6 weeks)78

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lousada EFigueiredo F(2024)An approach for offloading with multi-hop considerations in an RSU signal overlay settingRevista de Gestão e Secretariado10.7769/gesec.v15i4.373915:4(e3739)Online publication date: 24-Apr-2024
https://doi.org/10.7769/gesec.v15i4.3739
R. MM. J(2024)Comprehensive Study on Routing in FANETIntelligent Decision Making Through Bio-Inspired Optimization10.4018/979-8-3693-2073-0.ch011(195-217)Online publication date: 24-May-2024
https://doi.org/10.4018/979-8-3693-2073-0.ch011
Duenas Santos CMezher AAstudillo León JCardenas Barrera JCastillo Guerra EMeng J(2024)Q-RPL: Q-Learning-Based Routing Protocol for Advanced Metering Infrastructure in Smart GridsSensors10.3390/s2415481824:15(4818)Online publication date: 25-Jul-2024
https://doi.org/10.3390/s24154818
Lee SHeo KKim MKim DChoi H(2024)Multiple-Junction-Based Traffic-Aware Routing Protocol Using ACO Algorithm in Urban Vehicular NetworksSensors10.3390/s2409291324:9(2913)Online publication date: 2-May-2024
https://doi.org/10.3390/s24092913
Kumar MRaw R(2024)RC-LAHR: Road-Side-Unit-Assisted Cloud-Based Location-Aware Hybrid Routing for Software-Defined Vehicular Ad Hoc NetworksSensors10.3390/s2404104524:4(1045)Online publication date: 6-Feb-2024
https://doi.org/10.3390/s24041045
Chen HLuo FZhou JDong Y(2024)Multi-Objective Optimized GPSR Intelligent Routing Protocol for UAV ClustersMathematics10.3390/math1217267212:17(2672)Online publication date: 28-Aug-2024
https://doi.org/10.3390/math12172672
Alsalami OYousefpoor EHosseinzadeh MLansky J(2024)A Novel Optimized Link-State Routing Scheme with Greedy and Perimeter Forwarding Capability in Flying Ad Hoc NetworksMathematics10.3390/math1207101612:7(1016)Online publication date: 28-Mar-2024
https://doi.org/10.3390/math12071016
Chen LLiu GZhu XLi X(2024)A Heuristic Routing Algorithm for Heterogeneous UAVs in Time-Constrained MEC SystemsDrones10.3390/drones80803798:8(379)Online publication date: 6-Aug-2024
https://doi.org/10.3390/drones8080379
Marwein PNath Sur SGao XKandar D(2024)Recent Survey on Internet of Vehicles: Architecture, Applications, Challenges, and Its SolutionsJournal of Testing and Evaluation10.1520/JTE2023009552:1(731-753)Online publication date: 1-Jan-2024
https://doi.org/10.1520/JTE20230095
Bekal PKumar PMane PPrabhu G(2024)A comprehensive review of energy efficient routing protocols for query driven wireless sensor networksF1000Research10.12688/f1000research.133874.312(644)Online publication date: 4-Jun-2024
https://doi.org/10.12688/f1000research.133874.3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents