Path set selection in mobile ad hoc networks

ABSTRACT

Topological changes in mobile ad hoc networks frequently render routing paths unusable. Such recurrent path failures have detrimental effects on the network ability to support QoS-driven services. A promising technique for addressing this problem is to use multiple redundant paths between the source and the destination. However while multipath routing algorithms can tolerate network failures well their failure resilience only holds if the paths are selected judiciously. In particular the correlation between the failures of the paths in a redundant path set should be as small as possible. However selecting an optimal path set is an NP-complete problem. Heuristic solutions proposed in the literature are either too complex to be performed in real-time or too ineffective or both. This paper proposes a multipath routing algorithm called Disjoint Pathset Selection Protocol (DPSP) based on a novel heuristic that in nearly linear time on average picks a set of highly reliable paths. The convergence to a highly reliable path set is very fast and the protocol provides flexibility in path selection and routing algorithm. Furthermore DPSP is suitable for real-time execution with nearly no message exchange overhead and with minimal additional storage requirements. This paper presents evidence that multipath routing can mask a substantial number of failures in the network compared to single path routing protocols and that the selection of paths according to DPSP can be beneficial for mobile ad hoc networks since it dramatically reduces the rate of route discoveries.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: M.O. Ball. "Complexity of network reliability." Networks 10 153--165 1980.
• 3: R.E. Barlow and F. Proschan. Statistical theory of reliability and life testing. Silver Spring 1981.
• 4: Timothy B. Brecht , Charles J. Colbourn, Lower bounds on two-terminal network reliability, Discrete Applied Mathematics, v.21 n.3, p.185-198, October 1988 [doi>10.1016/0166-218X(88)90065-0]
• 5: Charles J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, Inc., New York, NY, 1987
• 6: R. Dube C.D. Rais K.Y. Wang and S.K. Tripathi. "Signal Stability-Based Adaptive Routing (SSA) for Ad Hoc Mobile Networks." IEEE Personal Communications p.36--45 Feb. 1997.
• 7: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 8: L.R. Ford D.R. Fulkerson. Flows in networks. Princeton University Press 1962.
• 9: Gavin Holland , Nitin Vaidya, Analysis of TCP performance over mobile ad hoc networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.219-230, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313540]
• 10: Yih-Chun Hu , David B. Johnson, Caching strategies in on-demand routing protocols for wireless ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.231-242, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345952]
• 11: V.A. Kaustov E.I. Litvak I.A. Ushakov. "The computational effectiveness of reliability estimates by the method of nonedge-intersecting chains and cuts." Soviet Journal on Computing and Systems Science 24: 59--62 1986.
• 12: Dexter C. Kozen, The design and analysis of algorithms, Springer-Verlag New York, Inc., New York, NY, 1992
• 13: J.B. Kruskal. "The number of simplices in a complex." Mathematical Optimization Techniques UC Press 251--278 1963.
• 14: S.J. Lee M. Gerla. "Split multi-path routing with maximally disjoint paths in ad hoc networks." Proceedings of ICC 2001 Helsinki Finland June 2001.
• 15: S.J. Lee M. Gerla. "AODV-BR: Backup routing in ad hoc networks." Proceedings of IEEE WCNC 2000 Chicago IL Sept. 2000.
• 16: B. Liang Z.J. Haas. "Predictive distance-based mobility management for PCS networks." Proceedings of IEEE Infocom'99 New York City NY March 1999.
• 17: A.B. McDonald T.F. Znati. "A mobility-based framework for adaptive clustering in wireless ad hoc networks." IEEE Journal on Selected Areas in Communications vol. 17 No 8 Aug. 1999.
• 18: A. Nasipuri S.R. Das. "On demand multipath routing for mobile ad hoc networks." Proceedings of the IEEE International Conference on Computer Communication and Networks (ICCCN'99) Boston MA Oct. 1999.
• 19: M.R. Pearlman Z.J. Haas. "Determining the optimal configuration of the Zone Routing Protocol." IEEE Journal on Selected Areas in Communications vol. 17 No 8 Aug. 1999.
• 20: M.R. Pearlman Z.J. Haas. "Improving the performance of query-based routing protocols through 'diversity injection'." Proceedings of IEEE Wireless Communications and Networking Conference 1999 (WCNC'99) New Orleans LA Sept. 1999.
• 21: Marc R. Pearlman , Zygmunt J. Haas , Peter Sholander , Siamak S. Tabrizi, On the impact of alternate path routing for load balancing in mobile ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 22: J Scott Provan, The complexity of reliability computations in planar and acyclic graphs, SIAM Journal on Computing, v.15 n.3, p.694-702, August 1986 [doi>10.1137/0215050]
• 23: J.S. Provan M.O. Ball. "The complexity of counting cuts and of computing the probability that a graph is connected." SIAM Journal on Computing 12: 777--788 1983.
• 24: V. Raman. "Finding the best edge-packing for two-terminal reliability is NP-hard." Journal of Combinatorial Math. and Comb. Computing 9: 91--96 1991.
• 25: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 26: A. Rosenthal. "Computing the reliability of complex networks." SIAM Journal of Applied Mathematics 32 (1977) pp. 384.
• 27: M. Sanches P. Manzoni and Z.J. Haas. "Determination of critical transmission range in ad hoc networks." Proceedings of Multiaccess Mobility and Teletraffic for Wireless Communications (MMT'99) Venice Italy October 68 1999.
• 28: Douglas R. Shier, Network reliability and algebraic structures, Clarendon Press, New York, NY, 1991
• 29: Chai-Keong Toh, Associativity-Based Routing for Ad Hoc Mobile Networks, Wireless Personal Communications: An International Journal, v.4 n.2, p.103-139, March 1997 [doi>10.1023/A:1008812928561]
• 30: A. Tsirigos and Z.J. Haas. "Multipath Routing in the Presence of Frequent Topological Changes." IEEE Communications Magazine p. 132--138 Nov. 2001.
• 31: I.A. Ushakov E.I. Litvak. "An upper and lower estimate of the parameters of two-terminal networks." Engineering Cybernetics 15: no.1 1977.
• 32: L.G. Valiant. "The complexity of enumeration and reliability problems." SIAM Journal of Computing 8: 410--421 1979.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

General Terms:
Algorithms, Reliability

Keywords:
mobile ad hoc networks, path set selection, reliability