On clustering phenomenon in mobile partitioned networks

ABSTRACT

According to different kinds of connectivity, we can distinguish three types of mobile ad-hoc networks: dense, sparse and clustered networks. This paper is about modeling mobility in clustered networks, where nodes are concentrated into clusters of dense connectivity, and in between there exists sparse connectivity. The dense and sparse networks are extensively studied and modeled, but not much attention is paid to the clustered networks.

In the sparse and clustered networks, an inherently important aspect is the mobility model, both for the design and evaluation of routing protocols. We propose a new mobility model for clustered networks, called Heterogeneous Random Walk. This model is simple, mathematically tractable and most importantly it captures the phenomenon of emerging clusters, observed in real partitioned networks, in an elegant way. We provide a closed-form expression for the stationary distribution of node position and we give a recipe for the "perfect simulation".

Moreover, based on the real mobility trace we provide strong evidence for the main macroscopic characteristics of clustered networks captured by the proposed mobility model. For the very first time in the literature we show evidence for the correlation between the spatial speed distribution and the cluster formation. We also present the results of the analysis of real cluster dynamics caused by nodes' mobility.

REFERENCES

• 1: Aruna Balasubramanian , Brian Levine , Arun Venkataramani, DTN routing as a resource allocation problem, ACM SIGCOMM Computer Communication Review, v.37 n.4, October 2007
• 2: Sven Bittner , Wolf-Ulrich Raffel , Manuel Scholz, The Area Graph-Based Mobility Model and Its Impact on Data Dissemination, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops, p.268-272, March 08-12, 2005 [doi>10.1109/PERCOMW.2005.79]
• 3: Jean-Yves Le Boudec, Understanding the simulation of mobility models with Palm calculus, Performance Evaluation, v.64 n.2, p.126-147, February, 2007 [doi>10.1016/j.peva.2006.03.001]
• 4: T. Camp, J. Boleng, and V. Davies. A Survey of Mobility Models for Ad Hoc Network Research. WCMC: Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2(5):483--502, 2002.
• 5: Augustin Chaintreau , Pan Hui , Jon Crowcroft , Christophe Diot , Richard Gass , James Scott, Impact of Human Mobility on Opportunistic Forwarding Algorithms, IEEE Transactions on Mobile Computing, v.6 n.6, p.606-620, June 2007 [doi>10.1109/TMC.2007.1060]
• 6: Community Resource for Archiving Wireless Data At Dartmouth. http://crawdad.cs.dartmouth.edu.
• 7: J. M. Dietrich Stoyan, Wilfrid S. Kendall. Stochastic geometry and its applications. Chichester {etc.} : Wiley, 1995.
• 8: B. Fan and A. Helmy. Wireless Ad Hoc and Sensor Networks, chapter A Survey of Mobility Models in Wireless Adhoc Networks, pages 1--29. Kluwer Academic Publishers, 2004.
• 9: L. Farnell , W. G. Gibson, Monte Carlo simulation of diffusion in a spatially nonhomogeneous medium: correction to the Gaussian steplength, Journal of Computational Physics, v.198 n.1, p.65-79, 20 July 2004 [doi>10.1016/j.jcp.2003.12.019]
• 10: A. Ferreira. Building a reference combinatorial model for MANETs. IEEE Network, 18(5):24--29, 2004.
• 11: C. W. Gardiner. Handbook of stochastic methods : for physics, chemistry and the natural sciences. Berlin : Springer, 2004.
• 12: G. R. Grimmett and D. R. Stirzaker. Probability and random processes. Oxford : Oxford University Press, 2003.
• 13: Wei-jen Hsu , Kashyap Merchant , Haw-wei Shu , Chih-hsin Hsu , Ahmed Helmy, Weighted waypoint mobility model and its impact on ad hoc networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.1, January 2005 [doi>10.1145/1055959.1055968]
• 14: W.-J. Hsu, T. Spyropoulos, K. Psounis, and A. Helmy. Modeling Time-Variant User Mobility in Wireless Mobile Networks. In IEEE INFOCOM, 2007.
• 15: 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
• 16: 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]
• 17: M. Kim, D. Kotz, and S. Kim. Extracting a mobility model from real user traces. In IEEE INFOCOM, 2006.
• 18: J. Leguay, T. Friedman, and V. Conan. Evaluating Mobility Pattern Space Routing. In IEEE INFOCOM, 2006.
• 19: S. Lim, C. Yu, and C. R. Das. Clustered Mobility Model for Scale-Free Wireless Networks. IEEE Local Computer Networks, pages 231--238, 2006.
• 20: 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]
• 21: Mirco Musolesi , Stephen Hailes , Cecilia Mascolo, Adaptive Routing for Intermittently Connected Mobile Ad Hoc Networks, Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, p.183-189, June 13-16, 2005 [doi>10.1109/WOWMOM.2005.17]
• 22: Mirco Musolesi , Cecilia Mascolo, Designing mobility models based on social network theory, ACM SIGMOBILE Mobile Computing and Communications Review, v.11 n.3, July 2007 [doi>10.1145/1317425.1317433]
• 23: Jörg Ott , Dirk Kutscher , Christoph Dwertmann, Integrating DTN and MANET routing, Proceedings of the 2006 SIGCOMM workshop on Challenged networks, p.221-228, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162654.1162659]
• 24: M. Penrose and A. Pisztora. Large Deviations for Discrete and Continuous Percolation. Adv. Appl. Prob., 28:29--52, 1996.
• 25: H. Risken. The Fokker-Planck equation : methods of solution and applications. Berlin : Springer, 1989.
• 26: R. R. Ronald Meester. Continuum percolation. Cambridge : Cambridge University Press, 1996.
• 27: N. Sarafijanovic-Djukic, M. Piórkowski, and M. Grossglauser. Island Hopping: Efficient Mobility-Assisted Forwarding in Partitioned Networks. In SECON, 2006.
• 28: N. Sarafijanovic-Djukic, M. Piórkowski, and M. Grossglauser. Island Hopping: Efficient Mobility-Assisted Forwarding in Partitioned Networks. Technical report, LCA, 2007.
• 29: P. Sommer. Design and Analysis of Realistic Mobility Model for Wireless Mesh Networks. Master's thesis, ETH Zurich, September 2007.
• 30: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceedings 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]
• 31: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Performance analysis of mobility-assisted routing, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132912]
• 32: 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]
• 33: Vikram Srinivasan , Mehul Motani , Wei Tsang Ooi, Analysis and implications of student contact patterns derived from campus schedules, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161100]
• 34: Diane Tang , Mary Baker, Analysis of a metropolitan-area wireless network, Wireless Networks, v.8 n.2/3, p.107-120, March-May 2002 [doi>10.1023/A:1013739407600]
• 35: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks technical report cs-200006. Technical report, Duke University, 2000.
• 36: Yang Chen , Wenrui Zhao , Mostafa Ammar , Ellen Zegura, Hybrid routing in clustered DTNs with message ferrying, Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking, June 11-11, 2007, San Juan, Puerto Rico [doi>10.1145/1247694.1247710]
• 37: Eiko Yoneki , Pan Hui , ShuYan Chan , Jon Crowcroft, A socio-aware overlay for publish/subscribe communication in delay tolerant networks, Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, October 22-26, 2007, Chania, Crete Island, Greece [doi>10.1145/1298126.1298166]
• 38: 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:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Algorithms, Experimentation, Theory

Keywords:
delay tolerant networks, mobility modeling, partitioned mobile networks