skip to main content
10.1145/1287853.1287873acmconferencesArticle/Chapter ViewAbstractPublication PagesmobicomConference Proceedingsconference-collections
Article

Crossing over the bounded domain: from exponential to power-law inter-meeting time in MANET

Published: 09 September 2007 Publication History

Abstract

Inter-meeting time between mobile nodes is one of the key metrics in a Mobile Ad-hoc Network (MANET) and central to the end-to-end delay and forwarding algorithms. It is typically assumed to be exponentially distributed in many performance studies of MANET or numerically shown to be exponentially distributed under most existing mobility models in the literature. However, recent empirical results show otherwise: the inter-meeting time distribution in fact follows a power-law. This outright discrepancy potentially undermines our understanding of the performance tradeoffs in MANET obtained under the exponential distribution ofthe inter-meeting time, and thus calls for further study on the power-law inter-meeting time including its fundamental cause, mobility modeling, and its effect. In this paper, we rigorously prove that a finite domain, on which most of the current mobility models are defined, plays an important role in creating the exponential tail of the inter-meeting time. We also prove that by simply removing the boundary in a simple two-dimensional isotropic random walk model, we are able to obtain the empirically observed power-law decay of the inter-meeting time. We then discuss the relationship between the size of the boundary and the relevant time scale of the network scenario under consideration. Our results thus provide guidelines on the design of new mobility models with power-law inter-meeting time distribution, new protocols including packet forwarding algorithms, as well as their performance analysis.

References

[1]
Andersen, S. On the fluctuations of sums of random variables. In Math. Scand. 1 (1953), p. 263.
[2]
Andersen, S. On the fluctuations of sums of random variables. In Math. Scand. 2 (1954), p. 195.
[3]
Boudec, J. L., and Vojnović, M. Random Trip Tutorial. In ACM Mobicom (Sep. 2006).
[4]
BrÉmaud, P. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer-Verlag, 1999.
[5]
Broch, J., Maltz, D., Johnson, D., Hu, Y., and Jetcheva, J. Multi-hop wireless ad hoc networking routing protocols. In ACM Mobicom (Dallas, TX, March 1998).
[6]
Burns, B., Brock, O., and Levine, B. N. MV Routing and Capacity Building in Disruption Tolerant Networks. In Proceedings of IEEE INFOCOM (Miami, FL, March 2005).
[7]
Camp, T., Boleng, J., and Davies, V. A Survey of Mobility Models for Ad Hoc Network Research. In Wireless Communications & Mobile Computing (WCMC) (2002).
[8]
Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Gass, R., and Scott, J. Impact of human mobility on the design of opportunistic forwarding algorithms. In Proceedings of IEEE INFOCOM (Barcelona, Catalunya, SPAIN, 2006).
[9]
Chiang, C., and Gerla, M. On-demand multicast in mobile wireless networks. In Proceedings of the 6th International Conference on Network Protocols (ICNP'98) (Austin, TX, 1998).
[10]
Davies, V. Evaluating mobility models within an ad hoc network. In Master's thesis, Colorado School of Mines (2000).
[11]
Farrell, S., and Cahill, V. Delay- and disruption-tolerant networking. Artech House, 1994.
[12]
Gamal, A. E., Mammen, J., Prabhakar, B., and Shah, D. Throughput-delay trade-off in wireless networks. In Proceedings of IEEE INFOCOM (Hong Kong, March 2004).
[13]
Groenevelt, R., Nain, P., and Koole, G. Message delay in MANET. In Proceedings of ACM SIGMETRICS (New York, NY, June 2004).
[14]
Grossglauser, M., and Tse, D. N. C. Mobility increases the capacity of Ad Hoc wireless networks. IEEE/ACM Transactions on Networking 4 (August 2002), 477--486.
[15]
Hanbali, A., Kherani, A. A., Grenovelt, R., Nain, P., and Altman, E. Impact of mobility on the performance of relaying in Ad Hoc Networks. In Proceedings of IEEE INFOCOM (Barcelona, Catalunya, SPAIN, April 2006).
[16]
Henderson, T., Kotz, D., and Abyzov, I. The changing usage of a mature campus-wide wireless network. In ACM Mobicom (Philadelphia, PA, 2004).
[17]
Hui, P., Chaintreau, A., Scott, J., Gass, R., Crowcroft, J., and Diot, C. Pocket switched networks and the consequences of human mobility in conference environments. In Proceedings of ACM SIGCOMM first workshop on delay tolerant networking and related topics (WDTN-05) (Philadelphia, PA, 2005).
[18]
Hyytia, E., Lassila, P., and Virtamo, J. Spatial node distribution of the random waypoint mobility model with applications. IEEE Trans. Mobile Computing 5 (June 2006), 680--694.
[19]
Johansson, P., Larsson, T., Hedman, N., Mielczarek, B., and Degermark, M. Routing protocols for mobile ad-hoc networks - a comparative performance analysis. In ACM Mobicom (Seattle, Washington, August 1999), pp. 195--206.
[20]
Johnson, D., and Maltz, D. Dynamic source routing in ad hoc wireless networks. T. Imelinsky and H. Korth, editors, Mobile Computing (1996), 153--181.
[21]
Khelil, A., MarrÓn, P. J., and Rothermel, K. Contatct-based mobility metrics for delay-tolerent Ad Hoc Networking. In Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication System (MASCOTS'05) (Atlanta, Georgia, September 2005).
[22]
Kim, M., Kotz, D., and Kim, S. Extracting a mobility model from real user traces. In Proceedings of IEEE INFOCOM (Barcelona, Catalunya, SPAIN, April 2006).
[23]
Leguay, J., Friedman, T., and Conan, V. Evaluating Mobility Pattern Space Routing for DTNs. In Proceedings of IEEE INFOCOM (Barcelona, Catalunya, SPAIN, April 2006).
[24]
Liang, B., and Haas, Z. J. Predictive Distance-Based Mobility Management for PCS Networks. In Proceedings of IEEE INFOCOM (1999), pp. 1377--1384.
[25]
Lin, H., and Antsaklis, P. J. Stability and Stabilizability of Switched Linear System: A Short Survey of Recent Results. In Proceedings of the 2005 IEEE International Symposium on Intelligent Control (2005).
[26]
Lin, X., and Shroff, N. B. The fundamental capacity-delay tradeoff in large mobile ad hoc networks. In Third Annual Mediterranean Ad Hoc Networking Workshop (2004).
[27]
Lindgren, A., Diot, C., and Scott, J. Impact of communication infrastructure on forwarding in pocket switched networks. In Proceedings of the 2006 SIGCOMM workshop on Challenged networks (Pisa, Italy, 2006).
[28]
McNett, M., and Voelker, G. M. Access and mobility of wireless pda user. Tech. rep., Computer Science and Engineering, UC San Diego, 2004.
[29]
Redner, S. A guide to first-passage processes. Cambridge University Press/Cambridge (UK), 2001.
[30]
Royer, E., Melliar-Smith, P. M., and Moser, L. An analysis of the optimum node density for ad hoc mobile networks. In IEEE International Conference on Communication (ICC) (Helsinki, Finland, 2001).
[31]
Sharma, G., and Mazumdar, R. On achievable delay/capacity trade-offs in Mobile Ad Hoc Networks. In Workshop on Modeling and Optimization in Mobile Ad Hoc and Wireless Networks (WIOPT) (Cambridge, UK, March 2004).
[32]
Sharma, G., and Mazumdar, R. Scaling Laws for Capacity and Delay in Wireless Ad Hoc Networks with Random Mobility. In IEEE International Conference on Communication (ICC) (Paris, France, June 2004).
[33]
Sharma, G., Mazumdar, R., and Shroff, N. B. Delay and Capacity Trade-offs in Mobile Ad Hoc Networks: A Global Perspective. In Proceedings of IEEE INFOCOM (Barcelona, Catalunya, SPAIN, August 2006).
[34]
Sharma, G., and Mazumdar, R. R. Delay and Capacity Trade-off in Wireless Ad Hoc Networks with Random Mobility. ACM/Kluwer Journal on Mobile Networks and Applications (MONET) (2004).
[35]
Su, J., Chin, A., Popivanova, A., Goel, A., and de Lara, E. User mobility for opportunistic ad-hoc networking. In Proceedings of the 6th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'04) (English Lake District, UK, 2004).
[36]
Theys, J. Joint Spectral Radius: theory and approximation. PhD thesis, Université catholique de Louvain, Faculté des sciences appliquées, Département d'ingénierie mathématique, 2005.
[37]
Toumpis, S., and Goldsmith, A. Large wireless networks under fading, mobility and delay constraints. In Proceedings of IEEE INFOCOM (Hong Kong, March 2004).

Cited By

View all
  • (2023)Toward Fast and Energy-Efficient Access to Cloudlets in Hostile EnvironmentsIEEE Transactions on Wireless Communications10.1109/TWC.2023.326231122:11(8320-8335)Online publication date: Nov-2023
  • (2022)Cluster based Online Task Assignment for Mobile CrowdsensingICC 2022 - IEEE International Conference on Communications10.1109/ICC45855.2022.9838735(5280-5285)Online publication date: 16-May-2022
  • (2020)AP-Assisted Online Task Assignment Algorithms for Mobile CrowdsensingMobile Networks and Applications10.1007/s11036-020-01579-3Online publication date: 7-Jun-2020
  • Show More Cited By

Index Terms

  1. Crossing over the bounded domain: from exponential to power-law inter-meeting time in MANET

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      MobiCom '07: Proceedings of the 13th annual ACM international conference on Mobile computing and networking
      September 2007
      370 pages
      ISBN:9781595936813
      DOI:10.1145/1287853
      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: 09 September 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. bounded domain
      2. exponential vs. power-law
      3. inter-meeting time distribution
      4. mobile ad-hoc network
      5. time and space scaling

      Qualifiers

      • Article

      Conference

      MobiCom/MobiHoc '07
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 440 of 2,972 submissions, 15%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

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

      Other Metrics

      Citations

      Cited By

      View all
      • (2023)Toward Fast and Energy-Efficient Access to Cloudlets in Hostile EnvironmentsIEEE Transactions on Wireless Communications10.1109/TWC.2023.326231122:11(8320-8335)Online publication date: Nov-2023
      • (2022)Cluster based Online Task Assignment for Mobile CrowdsensingICC 2022 - IEEE International Conference on Communications10.1109/ICC45855.2022.9838735(5280-5285)Online publication date: 16-May-2022
      • (2020)AP-Assisted Online Task Assignment Algorithms for Mobile CrowdsensingMobile Networks and Applications10.1007/s11036-020-01579-3Online publication date: 7-Jun-2020
      • (2020)Fine-Grained Task Distribution for Mobile Sensor Networks with Agent Cooperation RelationshipService-Oriented Computing10.1007/978-3-030-65310-1_28(401-415)Online publication date: 9-Dec-2020
      • (2019)Using Socio-Spatial Context in Mobile Cloud Process Offloading for Energy Conservation in Wireless DevicesIEEE Transactions on Cloud Computing10.1109/TCC.2015.25117367:2(392-402)Online publication date: 1-Apr-2019
      • (2019)Deep Reinforcement Learning-Based Dynamic Service Migration in Vehicular Networks2019 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOBECOM38437.2019.9014294(1-6)Online publication date: Dec-2019
      • (2019)AP-Assisted Online Task Assignment for Mobile Crowdsensing2019 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOBECOM38437.2019.9013513(1-6)Online publication date: Dec-2019
      • (2019)Data Collection in Population Protocols with Non-uniformly Random SchedulerTheoretical Computer Science10.1016/j.tcs.2019.08.029Online publication date: Aug-2019
      • (2018)A Mixed Strategy for a Competitive Game in Delay Tolerant NetworksComputer Performance Engineering10.1007/978-3-030-02227-3_13(190-204)Online publication date: 3-Oct-2018
      • (2017)Empirical Analysis on Temporal Statistics of Pairwise Contact Patterns in Dynamic Human Networks2017 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)10.1109/iThings-GreenCom-CPSCom-SmartData.2017.9(9-16)Online publication date: Jun-2017
      • 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