Aging rules: what does the past tell about the future in mobile ad-hoc networks?

ABSTRACT

The study in mobile ad-hoc networks (MANET) is facing challenges brought by recent discovery of non-exponential behavior of the inter-contact time distribution of mobile nodes. In this paper, we analyze various characteristics of the relative mobility of a random pair of nodes in MANET to show that they produce inter-contact time with different aging properties. First, by fixing one node and resorting to the random walks on directed graphs, we mathematically prove that under four classes of stochastic mobility patterns, the resulting inter-contact times have constant/decreasing/increasing failure rate and new-better-than-used property. Then, we consider the case when both nodes are mobile and use simulation results to uncover the aging property of their inter-contact times under random waypoint models and random walk mobility models. This aging property tells us how to correctly relate the past experience of mobile nodes with their future behavior, thereby allowing tremendous opportunities brought by the memory structure in the non-exponential inter contact time, which would be impossible under the widely assumed exponentially distributed (memoryless) inter-contact time. As an application of our results, we establish for the first time that the approach based on exponential inter-contact time assumption can either under-estimate or over-estimate the actual system performance, under different stochastic mobility patterns indexed by their aging properties. Our results on aging properties also provide theoretic guidelines on how to exploit the memory structure toward better design of protocols under general mobility.

REFERENCES

• 1: David Aldous and Jim Fill. Reversible Markov Chains and Random Walks on Graphs. 2002. Draft chapters.
• 2: J.Y. Le Boundec and M. Vojnovic. Perfect simulation and stationarity of a class of mobility models. In IEEE Infocom, Miami, FL, March 2005.
• 3: John Burgess, Brian Gallagher, David Jensen, and Brian Neil Levine. Maxprop: Routing for vehicle-based disruption-tolerant networks. In IEEE Infocom, Barcelona, Catalunya, SPAIN, August 2006.
• 4: 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]
• 5: Han Cai , Do Young Eun, Toward stochastic anatomy of inter-meeting time distribution under general mobility models, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374655]
• 6: T. Camp, J. Boleng, and V. Davies. A Survey of Mobility Models for Ad Hoc Network Research. In WCMC, 2002.
• 7: Carl D. Meyer, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 8: 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 IEEE Infocom, Barcelona, Catalunya, SPAIN, 2006.
• 9: V. Davies. Evaluating mobility models within an ad hoc network. In Master's thesis, Colorado School of Mines, 2000.
• 10: Henri Dubois-Ferriere , Matthias Grossglauser , Martin Vetterli, Age matters: efficient route discovery in mobile ad hoc networks using encounter ages, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778446]
• 11: Michele Garetto , Emilio Leonardi, Analysis of random mobility models with PDE's, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132914]
• 12: B. Gnedenko and I. Usharkov. Probabilistic Reliability Engineering. John Wiley & Son, 1995.
• 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: Matthias Grossglauser and Martin Vetterli. Locating nodes with ease: last encounter routing in ad hoc networks through mobility diffusion. In IEEE Infocom, San Francisco, March 2003.
• 16: 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]
• 17: 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]
• 18: 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]
• 19: Stratis Ioannidis and Peter Marbach. A brownian motion model for last encounter routing. In IEEE Infocom, Barcelona, Spain, April 2006.
• 20: Apoorva Jindal , Konstantinos Psounis, Performance analysis of epidemic routing under contention, Proceedings of the 2006 international conference on Wireless communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada [doi>10.1145/1143549.1143657]
• 21: 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]
• 22: D. Johnson and D. Maltz. Dynamic source routing in ad hoc wireless networks. T. Imelinsky and H. Korth, editors, Mobile Computing, pages 153--181, 1996.
• 23: 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]
• 24: J. Keilson. Markov Chain Models -- Rarity and Exponentiality. Springer-Verlag, New York, 1979.
• 25: D.G. Kendall. Unitary dilations of one-parameter semi-groups of Markov transition operators, and the corresponding integral representations for Markov processes with a countable infinity of states. Proc. London math. Soc., 3(9):417--431, 1959.
• 26: Masaaki Kijima. Markov Processes for Stochastic Modeling. Chapman and Hall, 1997.
• 27: Chin-Diew Lai , Min Xie , R. E. Barlow, Stochastic Ageing and Dependence for Reliability, Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 28: P. Nain, D. Towsley, B. Liu, and Z. Liu. Properties of random direction models. In Proceedings of IEEE INFOCOM, Miami, FL, March 2005.
• 29: A. Natarajan, M. Motani, and V. Srinivasan. Understanding urban interactions from bluetooth phone contact traces. In Proceedings of PAM 2007, Louvain-la-neuve, Belgium, April 2007.
• 30: S.M. Ross. Stochastic Processes. John Wiley & Son, New York, 1983.
• 31: Natasa Sarafijanovic-Djukic and Matthias Grossglauser. Last encounter routing under random waypoint mobility. In Networking'04, Athens, Greece, May 2004.
• 32: G. Sharma and R.R. Mazumdar. Delay and Capacity Trade-off in Wireless Ad Hoc Networks with Random Mobility. ACM/Kluwer Journal on Mobile Networks and Applications (MONET), 2004.
• 33: 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]
• 34: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, p.79-85, March 19-23, 2007 [doi>10.1109/PERCOMW.2007.108]
• 35: Douglas Brent West. Introduction to Graph Theory. Prentice Hall College Div, 1995.
• 36: Xiaolan Zhang , Jim Kurose , Brian Neil Levine , Don Towsley , Honggang Zhang, Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing, 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.1287876]

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:
aging property, failure rate, inter-contact time, mobile ad-hoc network, random walk on directed graph