Routing in a cyclic mobispace

ABSTRACT

A key challenge of routing in delay tolerant networks (DTNs) is finding routes that have high delivery rates and low end-to-end delays. When oracles are not available for future connectivity, opportunistic routing is preferred in DTNs, in which messages are forwarded to nodes with higher delivery probabilities. We observe that real objects have repetitive motions, but no prior research work has investigated the cyclic delivery probability of messages between nodes. In this paper, we propose to use the expected minimum delay (EMD) as a new delivery probability metric in DTNs with repetitive but non-deterministic mobility. Specifically, we model the network as a probabilistic time-space graph with historical contact information or prior knowledge about the network. We then translate it into a probabilistic state-space graph in which the time dimension is removed. Finally, we apply the Markov decision process to derive the EMDs of the messages at particular times. Our proposed EMD-based routing protocol, called routing in cyclic MobiSpace (RCM), outperforms several existing opportunistic routing protocols when simulated using both real and synthetic traces.

REFERENCES

• 1: V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall, and H. Weiss. Delay-tolerant Network Architecture. In Internet draft: draft-irrf-dtnrg-arch.txt, DTN Research Group, 2006.
• 2: 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
• 3: S. Merugu, M. Ammar, and E. Zegura. Routing in Space and Time in Network with Predictable Mobility. In Technical report: GIT-CC-04-07, College of Computing, Georgia Tech, 2004.
• 4: J. Haas, J. Y. Halpern, and L. Li. Gossip-Based Ad Hoc Routing. In Proc. of IEEE INFOCOM, 2002.
• 5: A. Lindgren, A. Doria, and O. Schelen. Probabilistic Routing in Intermittently Connected Networks. Lecture Notes in Computer Science, 3126:239--254, August 2004.
• 6: Elizabeth M. Daly , Mads Haahr, Social network analysis for routing in disconnected delay-tolerant MANETs, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288113]
• 7: Cong Liu , Jie Wu, Scalable routing in delay tolerant networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288115]
• 8: J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networking. In Proc. of IEEE INFOCOM, 2006.
• 9: 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]
• 10: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 11: R. A. Howard. Dynamic Programming and Markov Processes. The MIT Press, 1960.
• 12: B. Bonet and H. Geffner. Faster Heuristic Search Algorithms for Planning with Uncertainty and Full Feedback. In Proc. of IJCAI, 2003.
• 13: P. Dai and J. Goldsmith. Topological Value Iteration Algorithm for Markov Decision Processes. In Proc. of IJCAI, 2007.
• 14: A. J. Briggs, C. Detweiler, D. Scharstein, and A. Vandenberg-Rodes. Expected Shortest Paths for Landmark-Based Robot Navigation. International Journal of Robotics Research, 23(7-8):717--728, July-August 2004.
• 15: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 16: A. Vahdate and D. Becker. Epidemic Routing for Partially-connected Ad Hoc Networks. In Technical Report, Duke University, 2002.
• 17: 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]
• 18: 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]
• 19: 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
• 20: Utku Günay Acer , Shivkumar Kalyanaraman , Alhussein A. Abouzeid, Weak state routing for large scale dynamic networks, 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.1287888]
• 21: 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]
• 22: CRAWDAD data set. Downloaded from http://crawdad.cs.dartmouth.edu/.
• 23: 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]
• 24: M. Grossglauser and M. Vetterli. Locating Nodes with Ease: Last Encounter Routing in Ad Hoc Networks through Mobility Diffusion. In Proc. of IEEE INFOCOM, 2003.
• 25: Jérémie Leguay , Timur Friedman , Vania Conan, DTN routing in a mobility pattern space, Proceedings 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]
• 26: Libo Song , David F. Kotz, Evaluating opportunistic routing protocols with large realistic contact traces, Proceedings of the second ACM workshop on Challenged networks, September 14-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1287791.1287799]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
cyclic mobispace, delay tolerant networks (DTNs), simulation, trace