Toward stochastic anatomy of inter-meeting time distribution under general mobility models

ABSTRACT

Recent discovery of the mixture (power-law and exponential) behavior of inter-meeting time distribution of mobile nodes presents new challenge to the problem of mobility modeling and its effect on the network performance. Existing studies on this problem via the average inter-meeting time become insufficient when the inter-meeting time distribution starts to deviate from exponential one. This insufficiency necessarily leads to the increasing difficulty in the performance analysis of forwarding algorithms in mobile ad-hoc networks (MANET). In this paper, we analyze the effect of mobility patterns on the inter-meeting time distribution. We first identify the critical timescale in the inter-meeting distribution, at which the transition from power-law to exponential takes place, in terms of the domain size and the statistics of the mobility pattern. We then prove that stronger correlations in mobility patterns lead to heavier (non-exponential) 'head' of the inter-meeting time distribution. We also prove that there exists an invariance property for several contact-based metrics such as inter-meeting, contact, inter-any-contact time under both distance-based (Boolean) and physical interference (SINR) based models, in that the averages of those contact-based metrics do not depend on the degree of correlations in the mobility patterns. Our results collectively suggest a convex ordering relationship among inter-meeting times of various mobility models indexed by their degrees of correlation, which is in good agreement with the ordering of network performance under a set of mobility patterns whose inter-meeting time distributions have power-law 'head' followed by exponential 'tail'.

REFERENCES

• 1: A. Al-Hanbali, A. A. Kherani, and P. Nain. Simple models for the performance evaluation of a class of two-hop relay protocols. In Proc. of IFIP Networking 2007, May 2007.
• 2: V. Balakrishnan, G. Nicolis, and C. Nicolis. Recurrence time statistics in deterministic and stochastic dynamical systems in continuous time: a comparison. Phys. Rev. E, 61(3):2490--2499, Mar 2000.
• 3: S. Bandyopadhyay, E. J. Coyle, and T. Falck. Stochastic properties of mobility models in mobile ad hoc networks. IEEE Transactions on Mobile Computing, 6(11), 2007.
• 4: J. Y. Le Boudec and M. Vojnovic. Perfect simulation and stationarity of a class of mobility models. In Proceedings of IEEE INFOCOM, Miami, FL, March 2005.
• 5: Han Cai , Do Young Eun, Crossing over the bounded domain: from exponential to power-law inter-meeting time in MANET, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287873]
• 6: T. Camp, J. Boleng, and V. Davies. A Survey of Mobility Models for Ad Hoc Network Research. In WCMC, 2002.
• 7: A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of human mobility on the design of opportunistic forwarding algorithms. In Proceedings of IEEE INFOCOM, Barcelona, Catalunya, SPAIN, 2006.
• 8: V. Davies. Evaluating mobility models within an ad hoc network. In Master's thesis, Colorado School of Mines, 2000.
• 9: Olivier Dousse , François Baccelli , Patrick Thiran, Impact of interferences on connectivity in ad hoc networks, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.425-436, April 2005 [doi>10.1109/TNET.2005.845546]
• 10: R. Durrett. Probability : Theory and Examples. Duxbury Press, Belmont, CA, second edition, 1996.
• 11: Robin Groenevelt , Philippe Nain , Ger Koole, Message delay in MANET, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 12: 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]
• 13: Zygmunt J. Haas , Tara Small, A new networking model for biological applications of ad hoc sensor networks, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.27-40, February 2006 [doi>10.1109/TNET.2005.863461]
• 14: M. Kac. On the notion of recurrence in discrete stochastic processes. Bulletin of the American Mathematical Society, 53:1002--1010, 1947.
• 15: Thomas Karagiannis , Jean-Yves Le Boudec , Milan Vojnović, Power law and exponential decay of inter contact times between mobile devices, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287875]
• 16: A. Muller and D. Stoyan. Comparison Methods for Stochastic Models and Risks. John Wiley & Son, 2002.
• 17: P. Nain, D. Towsley, B. Liu, and Z. Liu. Properties of random direction models. In Proceedings of IEEE INFOCOM, Miami, FL, March 2005.
• 18: S. Redner. A guide to first-passage processes. Cambridge University Press/Cambridge (UK), 2001.
• 19: E. Royer, P. M. Melliar-Smith, and L. Moser. An analysis of the optimum node density for ad hoc mobile networks. In IEEE International Conference on Communication (ICC), Helsinki, Finland, 2001.
• 20: G. Sharma, R. Mazumdar, and N. B. Shroff. Delay and Capacity Trade-offs in Mobile Ad Hoc Networks: A Global Perspective. In Proceedings of IEEE INFOCOM, Barcelona, Catalunya, SPAIN, August 2006.
• 21: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Efficient routing in intermittently connected mobile networks: the multiple-copy case, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.77-90, February 2008 [doi>10.1109/TNET.2007.897964]
• 22: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.252-259, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080143]
• 23: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Performance analysis of mobility-assisted routing, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132912]
• 24: A. Vahdat and D. Becker. Epidemic Routing for Partially-Connected Ad Hoc Networks. Technical report, Duke University Technical Report CS-200006, April 2000.
• 25: Xiaolan Zhang , Giovanni Neglia , Jim Kurose , Don Towsley, Performance modeling of epidemic routing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.10, p.2867-2891, July, 2007 [doi>10.1016/j.comnet.2006.11.028]

INDEX TERMS

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

General Terms:
Theory

Keywords:
first passage time, inter-meeting time distribution, mobile ad-hoc network, stochastic ordering