Mobility profile based routing within intermittently connected mobile ad hoc networks (ICMAN)

ABSTRACT

Routing in Intermittently Connected Networks (ICN) is a challenging problem due to the time varying nature of network connectivity. In this work, we focus on a special class of ICN formed by mobile ad hoc users called ICMAN. A recent study of wireless users' mobility traces revealed that users usually move between a small set of socially significant places called "hubs" to form so-called "sociological orbits" [6]. To exploit the knowledge about such mobility profiles, we propose a hub-level routing method, and two versions of user-level routing methods. We compare these approaches with Epidemic routing [21] to highlight the advantages of sociological orbit aware routing within ICMAN in terms of achieving a higher throughput and a lower overhead.

REFERENCES

• 1: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 2: Bai, F., Sadagopan, N., and Helmy, A. Important: a framework to systematically analyze the impact of mobility on performance of routing protocols for adhoc networks. Proceedings of IEEE INFOCOM '03 2 (March 2003), 825--835.
• 3: Bollobás, B. Random graphs, second ed., vol. 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2001.
• 4: Burns, B., Brock, O., and Levine, B. N. Mv routing and capacity building in disruption tolerant networks. In Proceedings of IEEE INFOCOM '05 (March 2005).
• 5: Dijkstra, E. W. A note on two problems in connexion with graphs. Numerische Mathematik 1 (1959), 269--271.
• 6: Joy Ghosh , Matthew J. Beal , Hung Q. Ngo , Chunming Qiao, On profiling mobility and predicting locations of wireless users, Proceedings of the second international workshop on Multi-hop ad hoc networks: from theory to reality, May 26-26, 2006, Florence, Italy [doi>10.1145/1132983.1132993]
• 7: Ghosh, J., Philip, S. J., and Qiao, C. Sociological orbit aware location approximation and routing in manet. In Proceedings of IEEE Broadnets '05, Boston, MA (October 2005). Also presented as a Poster at ACM MobiHoc '05, Champaign, IL (May 2005).
• 8: Glance, N., Snowdon, D., and Meunier, J.-L. Pollen: using people as a communication medium. First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA02) 35, 4 (March 2001), 429--442.
• 9: 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]
• 10: 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]
• 11: 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
• 12: 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
• 13: Knoblauch, R. L., Pietrucha, M. T., and Nitzburg, M. Field Studies of Pedestrian Walking Speed and Start-Up Time. Transportation Research Board Records, 1538 (1996).
• 14: Michael Krivelevich , Van H. Vu, Choosability in random hypergraphs, Journal of Combinatorial Theory Series B, v.83 n.2, p.241-257, November 2001 [doi>10.1006/jctb.2001.2053]
• 15: Jérémie Leguay , Timur Friedman , Vania Conan, DTN routing in a mobility pattern space, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.276-283, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080146]
• 16: Lindgren, A., Doria, A., and Schelen, O. Poster: Probabilistic routing in intermittently connected networks. Proceedings of The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2003) (June 2003).
• 17: Samal, S. Mobility pattern aware routing in mobile ad hoc networks. MS Thesis, Virginia Polytechnic Institute and State University (May 2003).
• 18: Shah, R., Roy, S., Jain, S., and Brunette, W. Data mules: Modeling a three-tier architecture for sparse sensor networks. IEEE SNPA Workshop (May 2003).
• 19: 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]
• 20: William Su , Sung-Ju Lee , Mario Gerla, Mobility prediction and routing in ad hoc wireless networks, International Journal of Network Management, v.11 n.1, p.3-30, January–February 2001 [doi>10.1002/nem.386]
• 21: Vahdat, A., and Becker, D. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University (April 2000).
• 22: Ghosh, J., Yoon, S., Ngo, H. Q., and Qiao, C. Sociological Orbit for Efficient Routing in Intermittently Connected Mobile Ad Hoc Networks. University at Buffalo, Technical Report, CSE Dept. TR-2005-19 (April 2005).
• 23: Wang, Y., and Wu, H. Dft-msn: The delay/fault-tolerant mobile sensor network for pervasive information gathering. To appear in IEEE INFOCOM'06, Barcelona, Spain (April 2006).
• 24: Williams, A. Cycling Speed. Article in Peak Performance Online (http://www.pponline.co.uk/encyc/0065.htm), 65.
• 25: Xiang Zeng , Rajive Bagrodia , Mario Gerla, GloMoSim: a library for parallel simulation of large-scale wireless networks, Proceedings of the twelfth workshop on Parallel and distributed simulation, p.154-161, May 26-29, 1998, Banff, Alberta, Canada
• 26: Zhao, W., Ammar, M., and Zegura, E. Controlling the mobility of multiple data transport ferries in a delay-tolerant network. In Proceedings of IEEE INFOCOM '05 (March 2005).

INDEX TERMS

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

General Terms:
Algorithms, Design, Human Factors, Performance

Keywords:
intermittently connected networks, mobility aware routing protocols, performance, sociological orbits