Distribution of path durations in mobile ad hoc networks and path selection

ABSTRACT

We investigate the issue of path selection in multihop wireless networks with the goal of identifying a scheme that can select a path with the largest expected duration. To this end, we first study the distribution of path duration. We show that, under a set of mild conditions, when the hop count along a path is large, the distribution of path duration can be well approximated by an exponential distribution even when the distributions of link durations are dependent and heterogeneous. Second, we investigate the statistical relation between a path duration and the durations of the links along the path. We prove that the parameter of the exponential distribution, which determines the expected duration of the path, is related to the link durations only through their means and is given by the sum of the inverses of the expected link durations. Based on our analytical results, we propose a scheme that can be implemented with existing routing protocols and select the paths with the largest expected durations. We evaluate the performance of the proposed scheme using ns-2 simulation.

REFERENCES

• 1: Christian Bettstetter , Christian Wagner, The Spatial Node Distribution of the Random Waypoint Mobility Model, Mobile Ad-Hoc Netzwerke, 1. deutscher Workshop über Mobile Ad-Hoc Netzwerke WMAN 2002, p.41-58, March 25-26, 2002
• 2: [2] J. Chang and L. Tassiulas, "Energy conserving routing in wireless ad hoc networks," in Proc. IEEE INFOCOM, Mar. 2000, vol. 1, pp. 22-31.
• 3: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 4: [4] P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.
• 5: Yijie Han , Richard J. La , Armand M. Makowski , Seungjoon Lee, Distribution of path durations in mobile ad-hoc networks: Palm's theorem to the rescue, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.12, p.1887-1900, 24 August 2006 [doi>10.1016/j.comnet.2005.10.005]
• 6: [6] Y. Han and R. J. La, "Maximizing path durations in mobile ad hoc networks," presented at the 40th Annu. Conf. Information Sciences Systems, Princeton, NJ, Mar. 2006.
• 7: [7] D. P. Heyman and M. J. Sobel, Stochastic Models in Operations Research, Volume I. New York: McGraw-Hill, 1982.
• 8: [8] D. B. Johnson and D. A. Maltz, "Dynamic source routing in ad hoc wireless networks," Mobile Comput., pp. 153-181, 1996.
• 9: [9] R. J. La and Y. Han, "Distribution of path durations in mobile ad hoc networks and path selection," [Online]. Available: http://www.ece.umd.edu/~hyongla/publication.htm
• 10: Jean-Yves Le Boudec, Understanding the simulation of mobility models with Palm calculus, Performance Evaluation, v.64 n.2, p.126-147, February, 2007 [doi>10.1016/j.peva.2006.03.001]
• 11: [11] M. R. Leadbetter, "On extreme values in stationary sequences," Z. Wahrscheinlichkeitstheorie verw. Gebiete, vol. 28, pp. 289-303, 1974.
• 12: [12] M. R. Leadbetter, "Extremes and local dependence in stationary sequences," Z. Wahrscheinlichkeitstheorie verw. Gebiete, vol. 65, pp. 291-306, 1983.
• 13: 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
• 14: [14] C. E. Perkins, Ad-Hoc Networking. Reading, MA: Addison-Wesley Longman, 2000.
• 15: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.234-244, Oct. 1994
• 16: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 17: [17] V. Rodoplu and T. Meng, "Minimum energy mobile wireless networks," IEEE J. Sel. Areas Commun., vol. 17, no. 8, pp. 1333-1344, Aug. 1999.
• 18: Narayanan Sadagopan , Fan Bai , Bhaskar Krishnamachari , Ahmed Helmy, PATHS: analysis of PATH duration statistics and their impact on reactive MANET routing protocols, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778444]
• 19: [19] G. S. Watson, "Extreme values in samples from m-dependent stationary processes," Ann. Math. Statist., vol. 25, pp. 798-800, 1954.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design

Keywords:
mobile ad hoc networks, routing control, stochastic analysis