Predict and relay: an efficient routing in disruption-tolerant networks

ABSTRACT

Routing is one of the most challenging open problems in disruption-tolerant networks (DTNs) because of the short-lived wireless connectivity environment. To deal with this issue, researchers have investigated routing based on the prediction of future contacts, taking advantage of nodes' mobility history. However, most of the previous work focused on the prediction of whether two nodes would have a contact, without considering the time of the contact. This paper proposes predict and relay (PER), an efficient routing algorithm for DTNs, where nodes determine the probability distribution of future contact times and choose a proper next hop in order to improve the end-to-end delivery probability. The algorithm is based on two observations: one is that nodes usually move around a set of well-visited landmark points instead of moving randomly; the other is that node mobility behavior is semi-deterministic and could be predicted once there is sufficient mobility history information. Specifically, our approach employs a time-homogeneous semi-markov process model that describes node mobility as transitions between landmarks. Landmark transition and sojourn time probability distributions are determined from nodes' mobility history. A simulation study shows that this approach improves the delivery ratio and also reduces the delivery latency compared to traditional DTN routing schemes.

REFERENCES

• 1: I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks. In IEEE Communications Magazine, 2002.
• 2: Eric Brewer , Michael Demmer , Bowei Du , Melissa Ho , Matthew Kam , Sergiu Nedevschi , Joyojeet Pal , Rabin Patra , Sonesh Surana , Kevin Fall, The Case for Technology in Developing Regions, Computer, v.38 n.6, p.25-38, June 2005 [doi>10.1109/MC.2005.204]
• 3: N. Banerjee, M. Corner, and B. Levine. An energy-efficient architecture for dtn throwboxes. In Proceedings of IEEE INFOCOM, 2007.
• 4: 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]
• 5: Pan Hui , Jon Crowcroft , Eiko Yoneki, Bubble rap: social-based forwarding in delay tolerant networks, 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.1374652]
• 6: 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
• 7: R. Shah, S. Jain, S. Roy, and W. Brunette. Data mules: Modeling a three-tier architecture for sparse sensor networks. In Tech. Rep. IRS-TR-03-001, Intel Research Seattle, 2003.
• 8: Sensor networking with delay tolerance (SeNDT). http://down.dsg.cs.tcd.ie/sendt/.
• 9: Jie Wu , Mingming Lu , Feng Li, Utility-Based Opportunistic Routing in Multi-Hop Wireless Networks, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, p.470-477, June 17-20, 2008 [doi>10.1109/ICDCS.2008.90]
• 10: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. In Tech. Rep. CS-200006, Duke University, 2000.
• 11: J. Burgess, B. Gallagher, D. Jensen, and B.N. Levine. Maxprop: Routing for vehicle-based disruption-tolerant networks. In Proceedings of IEEE INFOCOM, 2006.
• 12: Ionut Cardei , Cong Liu , Jie Wu , Quan Yuan, DTN Routing with Probabilistic Trajectory Prediction, Proceedings of the Third International Conference on Wireless Algorithms, Systems, and Applications, p.40-51, October 26-28, 2008, Dallas, Texas [doi>10.1007/978-3-540-88582-5_7]
• 13: J. Ghosh, S.J. Philip, and C. Qiao. Sociological orbit aware location approximation and routing (solar) in dtn. Technical report, State University of New York at Buffalo, April 2005. 2005-12.
• 14: K. Lee, M. Le, J. Haerri, and M. Gerla. Louvre: Landmark overlays for urban vehicular routing environments. In Proceedings of IEEE WiVeC, 2008.
• 15: Jungkeun Yoon , Brian D. Noble , Mingyan Liu , Minkyong Kim, Building realistic mobility models from coarse-grained traces, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134699]
• 16: Cong Liu , Jie Wu, Routing in a cyclic mobispace, 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.1374665]
• 17: X. Chen and A. L. Murphy. Enabling disconnected transitive communication in mobile ad hoc networks. In Proceedings of ACM POMC, 2001.
• 18: 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]
• 19: 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]
• 20: Tara Small , Zygmunt J. Haas, Resource and performance tradeoffs in delay-tolerant wireless networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.260-267, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080144]
• 21: T. Spyropoulos, K. Psounis, and C.S. Raghavendra. Single-copy routing in intermittently connected mobile networks. In Proceedings of IEEE SECON, 2004.
• 22: 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
• 23: 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]
• 24: K. Harras, K. Almeroth, and E. Belding-Royer. Delay tolerant mobile networks (DTMNs): Controlled flooding schemes in sparse mobile networks. In Proceedings of Netwoking, 2005.
• 25: 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]
• 26: X. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance modeling of epidemic routing. In Proceedings of IFIP Networking, 2006.
• 27: B. Burns, O. Brock, and B.N. Levine. Mv routing and capacity building in disruption tolerant networks. In Proceedings of IEEE INFOCOM, 2005.
• 28: J. LeBrun, C. Chuah, and D. Ghosal. Knowledge based opportunistic forwarding in vehicular wireless ad hoc networks. In Proceedings of VTC Spring, 2005.
• 29: J. Leguay, T. Friedman, and V. Conan. Evaluating mobility pattern space routing. In Proceedings of IEEE INFOCOM, 2006.

INDEX TERMS

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

General Terms:
Algorithms, Measurement, Performance

Keywords:
disruption-tolerant networks (dtns), landmarks, prediction, routing, time-related markov model