Brad Karp
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.
- 1.ABRAMSON, N. The ALOHA system- another alternative for computer communications. AFIPS 37 (1970), 281-285.Google Scholar
- 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. Google ScholarDigital 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. Google ScholarDigital 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). Google ScholarDigital 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.Google Scholar
- 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.Google ScholarCross Ref
- 7.FINN, G. G. Routing and addressing problems in large metropolitan-scale intemetworks. Tech. Rep. ISI/RR-87-180, Information Sciences Institute, Mar. 1987.Google ScholarCross Ref
- 8.FLOYD, S., AND JACOBOSON, V. The synchronization of periodic routing messages. IEEE/ACM Transactions on Networking 2, 2 (April 1994), 122--136. Google ScholarDigital Library
- 9.GABRIEL, K., AND SOKAL, R. A new statistical approach to geographic variation analysis. Systematic Zoology 18 (1969), 259-278.Google ScholarCross Ref
- 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). Google ScholarDigital 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.Google Scholar
- 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.Google Scholar
- 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). Google ScholarDigital 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.Google Scholar
- 15.KARP, B. Geographic routing for wireless networks. Presentation at AFOSR MURI ACTCOMM Research Review Meeting, Oct. 1998.Google Scholar
- 16.KARP, B. Greedy perimeter state routing. Invited Seminar at the USCAnformation Sciences Institute, July 1998.Google Scholar
- 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). Google ScholarDigital 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). Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital Library
- 21.PERKINS, C. Ad hoc on demand distance vector (AODV) routing. Interact-Draft, draft-ietf-manet-aodv-04.txt, Oct. 1999. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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). Google ScholarDigital Library
- 25.THE CMU MONARCH GROUP. Wireless and Mobility Extensions to ns-2. http://www, monarch.cs.cmu.edu/cmu-ns.html, Oct. 1999.Google Scholar
- 26.THE VINT PROJECT. The UCB/LBNIdVINT Network Simulator--ns (version 2). http://mash.cs.berkeley, edu/ns.Google Scholar
- 27.TOUSSAINT, G. The relative neighborhood graph of a finite planar set,. Pattern Recognition 12, 4 (1980), 261-268.Google ScholarCross Ref
- 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,Google ScholarCross Ref
- 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. Google ScholarDigital Library
- GPSR: greedy perimeter stateless routing for wireless networks
Recommendations
The Improvement of GPSR Routing Protocol in VANETs
ICECC '12: Proceedings of the 2012 International Conference on Electronics, Communications and ControlAccording 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 TechnologiesOne 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