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

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: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 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: On-Demand Multicast in Mobile Wireless Networks, Proceedings of the Sixth International Conference on Network Protocols, p.262, October 13-16, 1998
• 10: Davies, V. Evaluating mobility models within an ad hoc network. In Master's thesis, Colorado School of Mines (2000).
• 11: Stephen Farrell , V. Cahill, Delay- and Disruption-Tolerant Networking, Artech House, Inc., Norwood, MA, 2006
• 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: 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
• 14: 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]
• 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: Tristan Henderson , David Kotz , Ilya Abyzov, The changing usage of a mature campus-wide wireless network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023739]
• 17: Pan Hui , Augustin Chaintreau , James Scott , Richard Gass , Jon Crowcroft , Christophe Diot, Pocket switched networks and human mobility in conference environments, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.244-251, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080142]
• 18: Esa Hyytia , Pasi Lassila , Jorma Virtamo, Spatial Node Distribution of the Random Waypoint Mobility Model with Applications, IEEE Transactions on Mobile Computing, v.5 n.6, p.680-694, June 2006 [doi>10.1109/TMC.2006.86]
• 19: Per Johansson , Tony Larsson , Nicklas Hedman , Bartosz Mielczarek , Mikael Degermark, Scenario-based performance analysis of routing protocols for mobile ad-hoc networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.195-206, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313535]
• 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: Abdelmajid Khelil , Pedro Jose Marron , Kurt Rothermel, Contact-Based Mobility Metrics for Delay-Tolerant Ad Hoc Networking, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.435-444, September 27-29, 2005 [doi>10.1109/MASCOT.2005.20]
• 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: Anders Lindgren , Christophe Diot , James Scott, Impact of communication infrastructure on forwarding in pocket switched networks, Proceedings of the 2006 SIGCOMM workshop on Challenged networks, p.261-268, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162654.1162664]
• 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: Jing Su , Alvin Chin , Anna Popivanova , Ashvin Goel , Eyal de Lara, User Mobility for Opportunistic Ad-Hoc Networking, Proceedings of the Sixth IEEE Workshop on Mobile Computing Systems and Applications, p.41-50, December 02-03, 2004 [doi>10.1109/MCSA.2004.29]
• 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).

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:
bounded domain, exponential vs. power-law, inter-meeting time distribution, mobile ad-hoc network, time and space scaling