Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Link reversal algorithms provide a simple mechanism for routing in mobile ad hoc networks. These algorithms maintain routes to any particular destination in the network, even when the network topology changes frequently. In link reversal, a node reverses its incident links whenever it loses routes to the destination. Link reversal algorithms have been studied experimentally and have been used in practical routing algorithms, including [8].This paper presents the first formal performance analysis of link reversal algorithms. We study these algorithms in terms of work (number of node reversals) and the time needed until the network stabilizes to a state in which all the routes are reestablished. We focus on the full reversal algorithm and the partial reversal algorithm, both due to Gafni and Berstekas [5]; the first algorithm is simpler, while the latter has been found to be more efficient for typical cases. Our results are as follows:(1) The full reversal algorithm requires O(n²) work and time, where n is the number of nodes which have lost the routes to the destination.(2) The partial reversal algorithm requires O(n • a^* + n²) work and time, where a^* is a non-negative integer which depends on the state of the network. This bound is tight in the worst case, for any a^*.(3) There are networks such that for every deterministic link reversal algorithm, there are initial states which require requires ω(n²) work and time to stabilize. Therefore, surprisingly, the full reversal algorithm is asymptotically optimal in the worst case, while the partial reversal algorithm is not, since a^* can grow arbitrarily large.

REFERENCES

• 1: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 2: Ioannis Chatzigiannakis , Sotiris E. Nikoletseas , Paul G. Spirakis, An Efficient Communication Strategy for Ad-hoc Mobile Networks, Proceedings of the 15th International Conference on Distributed Computing, p.285-299, October 03-05, 2001
• 3: M. S. Corson and A. Ephremides. A distributed routing algorithm for mobile radio networks. In Proceedings of the IEEE Military Communications Conference (MILCOM '89), October 1989.
• 4: M. Scott Corson , Anthony Ephremides, A distributed routing algorithm for mobile wireless networks, Wireless Networks, v.1 n.1, p.61-81, Feb. 1995 [doi>10.1007/BF01196259]
• 5: E. M. Gafni and D. P. Bertsekas. Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE trans. on commun., COM-29:11--18, 1981.
• 6: Navneet Malpani , Jennifer L. Welch , Nitin Vaidya, Leader election algorithms for mobile ad hoc networks, Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, p.96-103, August 11-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345848.345871]
• 7: V. Park and M. S. Corson. A performance comparison of the temporally-ordered routing algorithm and ideal link-state routing. In Proceedings of IEEE International Symposium on Systems and Communications, June 1998.
• 8: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 9: C. E. Perkins. Ad Hoc Networking. Addison Wesley, 2000.
• 10: Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
• 11: Comparative Performance Evaluation of Routing Protocols for Mobile, Ad hoc, Proceedings of the International Conference on Computer Communications and Networks, p.153, October 12-15, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Performance, Theory

Keywords:
ad hoc networks, gafni-berstekas, link reversal routing