ACM Home Page
Please provide us with feedback. Feedback
GPSR: greedy perimeter stateless routing for wireless networks
Full text PdfPdf (1.41 MB)
Source International Conference on Mobile Computing and Networking archive
Proceedings of the 6th annual international conference on Mobile computing and networking table of contents
Boston, Massachusetts, United States
Pages: 243 - 254  
Year of Publication: 2000
ISBN:1-58113-197-6
Authors
Brad Karp  Harvard University/ACIRI
H. T. Kung  Harvard University
Sponsors
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
SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 92,   Downloads (12 Months): 577,   Citation Count: 485
Additional Information:

abstract   references   cited by   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/345910.345953
What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
ABRAMSON, N. The ALOHA system- another alternative for computer communications. AFIPS 37 (1970), 281-285.
2
3
4
 
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
 
9
GABRIEL, K., AND SOKAL, R. A new statistical approach to geographic variation analysis. Systematic Zoology 18 (1969), 259-278.
10
 
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
 
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
18
 
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.
 
20
 
21
22
23
24
 
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

CITED BY  490