Location based localized alternate, disjoint, multi-path and component routing schemes for wireless networks

ABSTRACT

In this paper we propose four schemes that improve the performance of greedy routing method. In the alternate method, the i-th received copy of message m is forwarded to i-th best neighbor, according to the selected criterion (it fails if number of copies exceeds number of neighbors). In the disjoint method, each intermediate node, upon receiving m, will forward it to its best neighbor among those who never received the message (it fails if no such neighbor exists). In the multi-path method, the source node S forwards m to c best neighbors according to distance from D. Each of c created copies afterwards follows the original, alternate, or disjoint method (these copies may interact since copy numbers are not communicated). Component routing method follows original greedy method until a failure node F. Such node F forwards the message to one node (using distance criteria) in each connected component of its neighbors, and then withdraws from the network for that message m (that is, neighboring nodes will ignore F when forwarding further copies of m). Thus F creates c copies of the message, where c is the number of connected components in the subgraph of its neighbors. All proposed methods are loop-free, have improved delivery rate over greedy method and reduced flooding rates compared to other existing methods. Component routing method guarantees delivery of m in connected graphs (even if the location of D is inaccurate).

REFERENCES

• 1: Lali Barriére , Pierre Fraigniaud , Lata Narayanan, Robust position-based routing in wireless Ad Hoc networks with unstable transmission ranges, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.19-27, July 2001, Rome, Italy [doi>10.1145/381448.381451]
• 2: 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]
• 3: G.G. Finn, Routing and addressing problems in large metropolitan-scale internetworks, ISI Research Report ISU/RR-87-180, March 1987.
• 4: S. Giordano, Mobile ad hoc networks, to appear in: Handbook of Wireless Networks and Mobile Computing (I. Stojmenovic, ed.), John Wiley & Sons, 2001, to appear.
• 5: R. Jain, A. Puri and R. Sengupta, Geographical routing using partial information for wireless ad hoc networks, IEEE Personal Communication, February 2001.
• 6: Stephanie Lindsey , Krishna M. Sivalingam , Cauligi S. Raghavendra, Power optimization in routing protocols for wireless and mobile networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
• 7: Ivan Stojmenovic , Xu Lin, Loop-Free Hybrid Single-Path/Flooding Routing Algorithms with Guaranteed Delivery for Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1023-1032, October 2001 [doi>10.1109/71.963415]
• 8: 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

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, Theory, Verification

Keywords:
localized algorithms, location, routing, wireless networks