skip to main content
10.1145/1374618.1374655acmconferencesArticle/Chapter ViewAbstractPublication PagesmobihocConference Proceedingsconference-collections
research-article

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

Published: 26 May 2008 Publication History

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]
H. Cai and D. Y. Eun. Crossing Over the Bounded Domain: From Exponential to Power-law Inter-meeting Time in MANET. In ACM Mobicom, Montreal, Canada, Sept. 2007.
[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]
O. Dousse, F. Baccelli, and P. Thiran. Impact of interferences on connectivity in ad hoc networks. IEEE/ACM Trans. Netw., 13(2):425--436, 2005.
[10]
R. Durrett. Probability : Theory and Examples. Duxbury Press, Belmont, CA, second edition, 1996.
[11]
R. Groenevelt, P. Nain, and G. Koole. Message delay in MANET. In Proceedings of ACM SIGMETRICS, New York, NY, June 2004.
[12]
M. Grossglauser and D. N. C. Tse. Mobility increases the capacity of Ad Hoc wireless networks. IEEE/ACM Transactions on Networking, 4:477--486, August 2002.
[13]
Z. J. Haas and T. Small. A new networking model for biological applications of ad hoc sensor networks. IEEE/ACM Trans. Netw., 14(1):27--40, 2006.
[14]
M. Kac. On the notion of recurrence in discrete stochastic processes. Bulletin of the American Mathematical Society, 53:1002--1010, 1947.
[15]
T. Karagiannis, J.-Y. Le Boudec, and M. Vojnovic. Power law and exponential decay of inter contact times between mobile devices. In ACM Mobicom, Montreal, Canada, Sept. 2007.
[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]
T. Spyropoulos, K. Psounis, and C. Raghavendra. Efficient Routing in Intermittently Connected Mobile Networks: The multi-copy case. to appear in IEEE/ACM Transactions on Networking, Feb. 2008.
[22]
T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In WDTN-05, Philadelphia, PA, 2005.
[23]
T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Performance analysis of mobility-assisted routing. In ACM Mobihoc, Florence, Italy, May 2006.
[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]
X. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance modeling of epidemic routing. Comput. Networks, 51(10):2867--2891, 2007.

Cited By

View all
  • (2021)Trust-based Friend Selection Algorithm for navigability in social Internet of ThingsKnowledge-Based Systems10.1016/j.knosys.2021.107479232:COnline publication date: 28-Nov-2021
  • (2020)Social Internet of Things: The collaboration of Social Network and Internet of Things and its Future2020 2nd International Conference on Advances in Computing, Communication Control and Networking (ICACCCN)10.1109/ICACCCN51052.2020.9362847(535-539)Online publication date: 18-Dec-2020
  • (2020)Social characteristics-based routing algorithm for a mobile social networkComputing10.1007/s00607-020-00843-4Online publication date: 9-Oct-2020
  • Show More Cited By

Index Terms

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

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing
      May 2008
      474 pages
      ISBN:9781605580739
      DOI:10.1145/1374618
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 26 May 2008

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. first passage time
      2. inter-meeting time distribution
      3. mobile ad-hoc network
      4. stochastic ordering

      Qualifiers

      • Research-article

      Conference

      MobiHoc08
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 296 of 1,843 submissions, 16%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 22 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2021)Trust-based Friend Selection Algorithm for navigability in social Internet of ThingsKnowledge-Based Systems10.1016/j.knosys.2021.107479232:COnline publication date: 28-Nov-2021
      • (2020)Social Internet of Things: The collaboration of Social Network and Internet of Things and its Future2020 2nd International Conference on Advances in Computing, Communication Control and Networking (ICACCCN)10.1109/ICACCCN51052.2020.9362847(535-539)Online publication date: 18-Dec-2020
      • (2020)Social characteristics-based routing algorithm for a mobile social networkComputing10.1007/s00607-020-00843-4Online publication date: 9-Oct-2020
      • (2018)Shared Rate Process for Mobile Users in Poisson Networks and ApplicationsIEEE Transactions on Information Theory10.1109/TIT.2017.278190964:3(2121-2141)Online publication date: Mar-2018
      • (2016)On temporal variations in mobile user SNR with applications to perceived QoS2016 14th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt)10.1109/WIOPT.2016.7492954(1-8)Online publication date: May-2016
      • (2016)Content-centric wireless networks with limited buffersIEEE/ACM Transactions on Networking10.1109/TNET.2014.236193524:1(299-311)Online publication date: 1-Feb-2016
      • (2016)Resource-Aware Photo Crowdsourcing Through Disruption Tolerant Networks2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2016.18(374-383)Online publication date: Jun-2016
      • (2016)Applicability assessment of terahertz information showers for next-generation wireless networks2016 IEEE International Conference on Communications (ICC)10.1109/ICC.2016.7511129(1-7)Online publication date: May-2016
      • (2016)Performance analysis of simultaneous communications in bacterial nanonetworksNano Communication Networks10.1016/j.nancom.2016.02.0028(55-67)Online publication date: Jun-2016
      • (2015)Modeling and Analysis of Single-Hop Mobile CloudletAdvances in Mobile Cloud Computing Systems10.1201/b19128-7(231-256)Online publication date: 19-Nov-2015
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media