Geographical Region Summary Service for geographical routing

ABSTRACT

Geographical routing requires a distributed location dissemination or location database system to provide forwarding location information. In this paper, we propose a novel location dissemination system called "Geographical Region Summary Service" (GRSS). Mobile nodes in GRSS proactively disseminate aggregated forwarding locations as summaries of node IDs in a defined region. Each node in the network knows either the exact location of every other node, or the region it resides in. Packet forwarding decisions can be made independently at each node. Node only need to maintain state proportional to the logarithm of the network diameter.

REFERENCES

• 1: Stefano Basagni , Imrich Chlamtac , Violet R. Syrotiuk , Barry A. Woodward, A distance routing effect algorithm for mobility (DREAM), Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.76-84, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288254]
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 4: CMU Monarch Group. CMU Monarch extensions to ns. http://www.monarch.cs.cmu.edu/.
• 5: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.254-265, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 6: G. G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI/RR-87-180, March 1987.
• 7: D. B. Johnson. Routing in ad hoc networks of mobile hosts. In Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pages 158-163, December 1994.
• 8: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks, chapter 5, pages 153-181. Kluwer Academic Publishers, 1996.
• 9: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 10: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 11: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 12: Michael Mitzenmacher, Compressed bloom filters, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.144-150, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384004]
• 13: Timothy J. Shepard, A channel access scheme for large dense packet radio networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.219-230, August 28-30, 1996, Palo Alto, California, United States
• 14: Ivan Stojmenovic , Mark Russell , Bosko Vukojevic, Depth First Search and Location Based Localized Routing and QoS Routing in Wireless Networks, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.173, August 21-24, 2000
• 15: UCB/LBNL/VINT. Network simulator ns (version 2). http://www.isi.edu/nsnam/ns/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Performance