DTN routing strategies using optimal search patterns

ABSTRACT

Biologists have long shown that the mobility patterns of many foraging animals and insects are similar to Levy walks and Levy walks are an optimal search strategy when target objects (i.e., food sources) are sparse and their locations are not known in advance. In this paper, we apply Levy walk patterns to routing in delay tolerant networks (DTN). In DTNs, message forwarding nodes often do not have full information about the whereabout of message destinations. Using the optimality property of Levy walks, we devise two styles of routing strategies. One is an active strategy using message ferries (MF) where the movement of MFs can be controlled to have a Levy walk pattern in order for them to maximize the opportunity of meeting the destinations and the other is a passive strategy in which the movement of nodes cannot be controlled, but messages are forwarded in such a manner that their forwarding patterns mimic the Levy walk patterns. We show through simulation that (1) both strategies are very effective when knowledge about destinations (i.e., contact history, trajectory or locations of destinations) is highly limited and (2) they complement existing utility-based routing which excels when such knowledge is available.

REFERENCES

• 1: 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]
• 2: R. P. D. Atkinson, C. J. Rhodes, D. W. Macdonald, and R. M. Anderson. Scale-free dynamics in the movement patterns of jackals. OIKOS, 98(1):134--140,2002.
• 3: Aruna Balasubramanian , Brian Levine , Arun Venkataramani, DTN routing as a resource allocation problem, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 4: T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2(5):482--502, March 2002.
• 5: Kevin Fall, A delay-tolerant network architecture for challenged internets, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863960]
• 6: 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]
• 7: 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]
• 8: 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
• 9: J.Leguay, T.Friedman, and V.Conan. Dtn routing in a mobility pattern space. In ACM SIGCOMM Workshop on DTN, 2003.
• 10: J.Voit. The Statistical Mechanics of Financial Markets. Springer, 2005.
• 11: K. Lee, B. C. Jung, I. Rhee, S. Chong, and D. K. Sung. Revisiting the transmission range model in mobile networks based on ieee 802.11a/g. Technical Report, http://netsys.kaist.ac.kr/main/publications, 2008.
• 12: J. Ott and M. Pitkanen. Dtn-based content storage and retrieval. In The First WoWMoM Workshop on Autonomic and Opportunistic Communications (AOC), 2007.
• 13: G. Ramos-Fernandez, J. L. Mateos, O. Miramontes, G. Cocho, H. Larralde, and B. Ayala-Orozco. Levy walk patterns in the foraging movements of spider monkeys (ateles geo®royi). Behavioural Ecology and Sociobiology, 55:223--230, 2004.
• 14: A. M. Reynolds. Optimal scale-free searching strategies for the location of moving targets: New insights on visually cued mate location behaviour in insects. Physics Letters A, 2006.
• 15: I. Rhee, M. Shin, S. Hong, K. Lee, and S. Chong. Human mobility patterns and their impact on delay tolerant networks. In ACM HotNets, Atlanta, US, 2007.
• 16: I. Rhee, M. Shin, S. Hong, K. Lee, and S. Chong. On the levy walk nature of human mobility. In IEEE INFOCOM, 2008.
• 17: K. Scott and S. Burleigh. Bundle protocol specification. Internet experimental RFC 5050, 2007.
• 18: M. F. Shlesinger, G. M. Zaslavsky, and U. Frisch. Levy Flights and Related Topics in Physics. In Lecture Notes in Physics. Number 450. Springer Verlag, Berlin, 1995.
• 19: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Efficient routing in intermittently connected mobile networks: the single-copy case, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.63-76, February 2008 [doi>10.1109/TNET.2007.897962]
• 20: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Efficient routing in intermittently connected mobile networks: the single-copy case, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.63-76, February 2008 [doi>10.1109/TNET.2007.897962]
• 21: Muhammad Mukarram Bin Tariq , Mostafa Ammar , Ellen Zegura, Message ferry route design for sparse ad hoc networks with mobile nodes, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132910]
• 22: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, 2000.
• 23: G. M. Viswanathan, V. Afanasyev, S. V. Buldyrev, E. J. Murphy, P. A. Prince, and H. E. Stanley. Levy flights search patterns of wandering albatrosses. Nature, 381:413--415, 1996.
• 24: G. M. Viswanathan, S. V. Buldyrev, S. Havlin, M. G. E. da Luz, E. P. Raposo, and H. E. Stanley. Optimizing the success of random searches. Nature, 401:911--914, October 1999.
• 25: Z. Zhang. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges. IEEE Communications Surveys & Tutorials, 2006.
• 26: W. Zhao, Y. Chen, M. Ammar, M. D. Corner, B. N. Levine, and E. Zegura. Capacity enhancement using throwboxes in dtns. In IEEE MASS, October 2006.

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:
Algorithms, Performance

Keywords:
delay tolerant networks, mobility model, routing performance