Performance analysis of mobility-assisted routing

ABSTRACT

Traditionally, ad hoc networks have been viewed as a connected graph over which end-to-end routing paths had to be established.Mobility was considered a necessary evil that invalidates paths and needs to be overcome in an intelligent way to allow for seamless ommunication between nodes.However, it has recently been recognized that mobility an be turned into a useful ally, by making nodes carry data around the network instead of transmitting them. This model of routing departs from the traditional paradigm and requires new theoretical tools to model its performance. A mobility-assisted protocol forwards data only when appropriate relays encounter each other, and thus the time between such encounters, called hitting or meeting time, is of high importance.In this paper, we derive accurate closed form expressions for the expected encounter time between different nodes, under ommonly used mobility models. We also propose a mobility model that can successfully capture some important real-world mobility haracteristics, often ignored in popular mobility models, and alculate hitting times for this model as well. Finally, we integrate this results with a general theoretical framework that can be used to analyze the performance of mobility-assisted routing schemes. We demonstrate that derivative results oncerning the delay of various routing s hemes are very accurate, under all the mobility models examined. Hence, this work helps in better under-standing the performance of various approaches in different settings, and an facilitate the design of new, improved protocols.

REFERENCES

• 1: Delay tolerant networking research group. http://www.dtnrg.org
• 2: D. Aldous and J. Fill. Reversible markov chains and random walks on graphs (monograph in preparation). http://stat-www.berkeley.edu/users/aldous/RWG/book.html
• 3: F. Bai, N. Sadagopan, and A. Helmy. The important framework for analyzing the impact of mobility on performance of routing for ad hoc networks. Elsevier Ad Hoc Networks Journal 1, Nov. 2003.
• 4: Magdalena Balazinska , Paul Castro, Characterizing mobility and network usage in a corporate wireless local-area network, Proceedings of the 1st international conference on Mobile systems, applications and services, p.303-316, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066127]
• 5: Christian Bettstetter, Mobility modeling in wireless networks: categorization, smooth movement, and border effects, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.3, p.55-66, July 2001 [doi>10.1145/584051.584056]
• 6: Christian Bettstetter , Hannes Hartenstein , Xavier Pérez-Costa, Stochastic properties of the random waypoint mobility model: epoch length, direction distribution, and cell change rate, Proceedings of the 5th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570758.570761]
• 7: Christian Bettstetter , Giovanni Resta , Paolo Santi, The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.3, p.257-269, March 2003 [doi>10.1109/TMC.2003.1233531]
• 8: J. Y. L. Boudec and M. Vojnovic. Perfect simulation and stationarity of a class of mobility models. In Proceedings of IEEE INFOCOM 2005.
• 9: 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]
• 10: S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, and K. Scott. Delay-tolerant networking: an approach to interplanetary internet. IEEE Communications Magazine 2003.
• 11: T. Camp,J. Boleng, and V. Davies. Mobility models for ad hoc network simulations. 2,2001.
• 12: R. M. de Moraes, H. R. Sadjadpour, and J. Garcia-Luna-Aceves. Throughput-delay analysis of mobile ad-hoc networks with a multi-copy relaying strategy. In Proceedings of IEEE SECON 2004.
• 13: A. Doria, M. Udn, and D. P. Pandey. Providing connectivity to the saami nomadic community. In Proc. 2nd Int. Conf. on Open Collaborative Design for Sustainable Innovation 2002.
• 14: A. Gamal, J. Mammen, B. Prabhakar, and D. Shah. Throughput-delay tradeoffs in wireless networks. In Proceedings of IEEE INFOCOM 2004.
• 15: 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]
• 16: P. Gupta and P. Kumar. Capacity of wireless networks. Transactions on Information Theory 46(2), 2000.
• 17: P. Gupta and P. R. Kumar. Critical poeer for asymptotic connectivity in wireless networks.In in Stochastic Analysis, Control, Optimization and Applications Birkhauser, Boston, 1998.
• 18: 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]
• 19: W. Hsu and A. Helmy. Impact: Investigation of mobile-user patterns across university campuses using lan trace analysis. Technical Report 2005,University of Southern California.
• 20: Pan Hui , Augustin Chaintreau , James Scott , Richard Gass , Jon Crowcroft , Christophe Diot, Pocket switched networks and human mobility in conference environments, Proceeding 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]
• 21: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 22: Amit Jardosh , Elizabeth M. Belding-Royer , Kevin C. Almeroth , Subhash Suri, Towards realistic mobility models for mobile ad hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939008]
• 23: Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 24: Anders Lindgren , Avri Doria , Olov Schelén, Probabilistic routing in intermittently connected networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.3, July 2003 [doi>10.1145/961268.961272]
• 25: Marvin McNett , Geoffrey M. Voelker, Access and mobility of wireless PDA users, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.4, October 2003 [doi>10.1145/965732.965744]
• 26: M. Neely and E. Modiano. Capacity and delay tradeoffs for ad-hoc mobile networks. IEEE Transactions on Information Theory 51, 2005.
• 27: Alex (Sandy) Pentland , Richard Fletcher , Amir Hasson, DakNet: Rethinking Connectivity in Developing Nations, Computer, v.37 n.1, p.78-83, January 2004 [doi>10.1109/MC.2004.1260729]
• 28: E. Perevalov and R. Blum. Delay limited capacity of ad hoc networks: asymptotically optimal transmission and relaying strategy. In Proceedings of IEEE INFOCOM 2003.
• 29: 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
• 30: R.C. Shah, S. Roy, S. Jain, and W. Brunette. Data mules: Modeling and analysis of a three-tier architecture for sparse sensor networks. Elsevier Ad Hoc Networks Journal 2003.
• 31: G. Sharma and R. Mazumdar. On achievable delay/capacity tradeoffs in mobile ad hoc networks. In Workshop on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (Wi'Opt), 2004.
• 32: G. Sharma and R. R. Mazumdar. Delay and capacity trade-off in wireless ad hoc networks with random way-point mobility. preprint, 2005.
• 33: Tara Small , Zygmunt J. Haas, Resource and performance tradeoffs in delay-tolerant wireless networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.260-267, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080144]
• 34: T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Multiple-copy routing in intermittently connected mobile networks. Technical Report CENG-2004-12, USC, 2004.
• 35: T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Single-copy routing in intermittently connected mobile networks. In Proceedings of IEEE SECON 2004.
• 36: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceeding 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]
• 37: C. Tuduce and T. Gross. A mobility model based on lan traces and its validation. In Proceedings of IEEE INFOCOM 2005.
• 38: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, Apr.2000.
• 39: Yong Wang , Sushant Jain , Margaret Martonosi , Kevin Fall, Erasure-coding based routing for opportunistic networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.229-236, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080140]
• 40: Hao Wu , Richard Fujimoto , Randall Guensler , Michael Hunter, MDDV: a mobility-centric data dissemination algorithm for vehicular networks, Proceedings of the 1st ACM international workshop on Vehicular ad hoc networks, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023875.1023884]
• 41: J. Yoon, M. Liu, and B. Noble. Random waypoint considered harmful. In Proceedings of IEEE INFOCOM 2003.
• 42: X. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance modeling of epidemic routing.Technical Report CMPSCI 05-44, UMass, 2005.
• 43: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]

INDEX TERMS

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

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

General Terms:
Performance, Theory

Keywords:
ad-hoc networks, delay tolerant networks, hitting times, intermittent connectivity, mobility modelling, routing