Abstract

Delay Tolerant Networks (DTNs) have evolved from Mobile Ad Hoc Networks (MANET). It is a network, where contemporaneous connectivity among all nodes doesn’t exist. This leads to the problem of how to route a packet from one node to another, in such a network. This problem becomes more complex, when the node mobility also is considered. The researchers have attempted to address this issue for over a decade. They have found that communication is possible in such a challenged network. The design of routing protocol for such networks is an important issue. This work surveys the literature and classifies the various routing approaches.

References

• A. Balasubramanian, B. N. Levine, and A. Venkataramani, “Dtn routing as a resource allocation problem,” ACM SIGCOMM, 2007.
• C. Boldrini, M. Conti, M. and A. Passarella, “Impact of social mobility on routing protocols for opportunistic networks,” Proceedings of the First IEEE WoWMoM Workshop on Autonomic and Opportunistic Networking (AOC), 2007.
• C. Boldrini, M. Conti, I. Iacopini, and A. Passarella. “HiBOp: a History Based Routing Protocol for Opportunistic Networks,” Proceedings of IEEE WoWMoM, 2007.
• C. Boldrini, M. Conti, and A. Passarella, “Modelling data dissemination in opportunistic networks,” Proceedings of ACM Workshop on Challenged Networks (CHANTS), 2008.
• C. Boldrini, M. Conti and A. Passarella, “ContentPlace: Social-aware Data Dissemination in Opportunistic Networks,” MSWiM’08, October 27–31, 2008.
• J. Burgess, B. Gallagher, D. Jensen, and B. Levine, “Maxprop: Routing for vehicle-based disruption-tolerant networks,” Proceedings of INFOCOM, 2006.
• B. Burns, O. Brock and B. N. Levine, “MV routing and capacity building in disruption tolerant networks,” Proceedings of IEEE INFOCOM, 2005.
• A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott, “Impact of Human Mobility on Opportunistic Forwarding Algorithms,” IEEE Transactions on Mobile Computing (INFOCOM 2006), 2007, pp. 606–620.
• I. Chatzigiannakis, S. Nikoletseas and P. Spirakis, “Analysis and Experimental Evaluation of An Innovative and Efficient Routing Protocol for Ad- Hoc Mobile Networks,” Lecture Notes in Computer Science, vol. 1982, 2001, pp. 99–111.
• I. Chatzigiannakis, S. Nikoletseas, N. Paspallis, P. Spirakis and C. Zaroliagis, “An Experimental Study of Basic Communication Protocols in Ad-Hoc Mobile Networks,” Proceedings of the 5th Workshop on Algorithmic Engineering, 2001.
• L.-J. Chen, C.-H. Yu, T. Sun, Y.-C. Chen and H.-H. Chu, “A hybrid routing approach for opportunistic networks,” ACM SIGCOMM Workshop on Challenged Networks, 2006.
• E. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant MANETs,” Proceedings of MobiHoc, 2007.
• J. Davis, A. Fagg, and B. Levine, “Wearable computers as packet transport mechanisms in highly partitioned ad hoc networks,” Proceedings of 5 IEEE International Symposium on Wearable Computers, Zurich, Switzerland, 2001.
• A. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, “Epidemic algorithms for replicated database maintenance,” Proceedings of the Sixth Symposium on Principles of Distributed Computing, 1987, pp. 1–12.
• H. Dubois-Ferriere, M. Grossglauser and M. Vetterli, “Age matters: Efficient route discovery in mobile ad hoc networks using encounter ages,” Proceedings of ACM OBIHOC, 2003.
• F. Ekman, A. Keränen, J. Karvo and J. Ott, “Working Day Movement Model,” MobilityModels’08, May 26, 2008.
• F. Farahmand, I. Cerutti, A. N. Patel, Q. Zhang and J. P. Jue, “Relay node placement in vehicular delay-tolerant networks,” IEEE Global Telecommunications Conference - GLOBECOM 2008, vol. 27, no. 1, November 2008, pp. 2514-2518.
• R. H. Frenkiel and T. Innielinski, “Infostations: The joy of ‘manytime, many-where’ communications,” Journal on Mobile Computing, May, 1996.
• D. Goodman, J. Borras, N. Mandayam and R. Yates, “INFOSTATIONS: A new system model for data and messaging services,” IEEE VTC’97, volume 2, May 1997, pp. 969–973.
• R. Groenevelt, P. Nain, and G. Koole, “The message delay in mobile ad hoc networks Performance Evaluation,” 62(1-4):210–228, Oct. 2005.
• M. Grossglauser, and D. N. Tse, “Mobility Increases the Capacity of Ad Hoc Wireless Networks,” IEEE/ACM Transactions on Networking, Vol. 10, No. 4, August 2002, pp. 477-486.
• M. Grossglauser and M. Vetterli, ‘Locating nodes with EASE: last encounter routing in ad hoc networks through mobility diffusion,” Proceedings of the 22nd IEEE Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM), 2003.
• Y. Gu, D. Bozdag, E. Ekici, F. Ozguner and C.-G. Lee, “Partitioning based mobile element scheduling in wireless sensor networks,” Proceedings of the 2nd Annual IEEE Conference on Sensor and Ad Hoc Communications and Networks, 2005.
• Y. Gu, D. Bozda˘g and E. Ekici, “Mobile Element Based Differentiated Message Delivery in Wireless Sensor Networks,” Proceedings of the 2006 International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM'06) 2006.
• http://www.haggleproject.org/index.php/Main_Page
• A. Al Hanbali, P. Nain, and E. Altman, “Performance of ad hoc networks with two-hop relay routing and limited packet lifetime,” Proc. of IEEE/ACM ValueTools, Pisa, Italy, Oct. 2006.
• K. A. Harras, K. C. Almeroth, and E. M. Belding-Royer, “Delay tolerant mobile networks (dtmns): Controlled flooding in sparse mobile networks,” IFIP Networking, 2005.
• K. Harras and K. Almeroth, “Inter-regional messenger scheduling in delay tolerant mobile networks,” Proceedings of WoWMoM'06, June 2006.
• P. Hui, J. Crowcroft, and E. Yoneki, “Bubble rap: social-based forwarding in delay tolerant networks,” Proceedings of MobiHoc, 2008, pp. 241–250.
• S. Ioannidis, A. Chaintreau, and L. Massoulie, “Optimal and scalable distribution of content updates over a mobile social network,” Proceedings of INFOCOM, 2009.
• S. Jain, K. Fall, and R. Patra, “Routing in a delay tolerant network,” Proceedings of ACM SIGCOMM, 2004.
• S. Jain, M. Demmer, R. Patra and K. Fall, “Using Redundancy to Cope with Failures in a Delay Tolerant Network,” SIGCOMM’05, August 22–26, 2005.
• D. Jea, A. Somasundara and M. Srivastava, “Multiple controlled mobile elements (data mules) for data collection in sensor networks,” DCOSS, 2005.
• E. P. C. Jones, L. Li, and P. A. S.Ward, “Practical routing in delay-tolerant networks,” Proceedings of ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005.
• E. P. C. Jones, L. Li, J. K. Schmidtke and P. A. S.Ward, “Practical Routing in Delay-Tolerant Networks,” IEEE Transactions on Mobile Computing, Vol. 6, No. 8, Aug. 2007.
• P. Juang, H. Oki, Y.Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, “Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with Zebranet,” Proceedings of ACM ASPLOS, 2002.
• A. Kansal, A. A. Somasundara, D. D. Jea, M. B. Srivastava and D. Estrin, “Intelligent fluid infrastructure for embedded networks,” ACM MobiSys 2004, 2004.
• J. Leguay, T. Friedman and V. Conan, “Evaluating MobySpace Based Routing Strategies in Delay Tolerant Networks,” Universit´e Pierre et Marie Curie, Laboratoire LiP6–CNRS, Thales Communications.
• J. Leguay, T. Friedman and V. Conan, “Evaluating Mobility Pattern Space Routing for DTNs,” Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM), April 2006.
• Y. Liao, K. Tan, Z. Zhang, and L. Gao, “Combining Erasure-coding and Relay Node Evaluation in Delay Tolerant Network Routing,” Microsoft Technical Report, MR-TR, 2006.
• Y. Liao, K. Tan, Z. Zhang, and L. Gao, “Estimation based erasure coding routing in delay tolerant networks,” International Wireless Communications and Mobile Computing Conference, 2006.
• Y. Lin, B. Liang, and B. Li, “Performance Modeling of Network Coding in Epidemic Routing,” MobiOpp’07, June 11, 2007.
• A. Lindgren, A. Doria, and O. Schelen, “Probabilistic routing in intermittently connected networks,” ACM SIGMOBILE CCR, 7(3), 2003, pp. 19–20.
• A. G. Miklas, K. K. Gollu, K. K.W. Chan, Stefan Saroiu, K. P. Gummadi and E. Lara, “Exploiting Social Interactions in Mobile Systems,” UbiComp 2007, pp. 409–428.
• M. Musolesi and C. Mascolo, “A Community Mobility Model for Ad Hoc Network Research,” Proceedings of ACM/SIGMOBILE REALMAN, 2006.
• M. Musolesi and C. Mascolo, “CAR: Context-aware Adaptive Routing for Delay Tolerant Mobile Networks,” IEEE Transactions on Mobile Computing, Feb 2009.
• E. C. R. de Oliveira and C´ elio V. N. de Albuquerque, “NECTAR: A DTN Routing Protocol Based on Neighbourhood Contact History,” SAC’09 March 2009.
• R. Ramanathan, R. Hansen, P. Basu, R. Rosales-Hain and R. Krishnan, “Prioritized Epidemic Routing for Opportunistic Networks,” MobiOpp’07, June 11, 2007.
• G. Sandulescu and S. Nadjm-Tehrani, “Opportunistic DTN Routing with Window-aware Adaptive Replication,” AINTEC’08, November 18–20, 2008.
• R. C. Shah, S. Roy, S. Jain, and W. Brunette, “Data Mules: Modeling and Analysis of a Three-tier Architecture for Sparse Sensor Networks”, Elsevier Ad Hoc Networks Journal, 2003.
• M. Shin, S. Hong and I. Rhee, “DTN Routing Strategies using Optimal Search Patterns,” CHANTS’08, September 15, 2008.
• T. Small and Z.J. Haas, “The Shared Wireless Infostation Model – A New Ad Hoc Networking Paradigm (or Where there is a Whale, there is a Way),” MobiHoc ’03, June 2003
• A. A. Somasundara, A. Ramamoorthy and M. B. Srivastava, “Mobile element scheduling for efficient data collection in wireless sensor networks with dynamic deadlines,” Proceedings of the 25th IEEE International Real Time Systems Symposium 2004, 2004.
• T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Single-copy Routing in Intermittently Connected Mobile Networks,” First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 2004, pp. 235-244.
• T. Spyropoulos, K. Psounis, and C. Raghavendra, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” Proceedings of 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 2005, pp 252–259.
• T. Spyropoulos, K. Psounis and C. Raghavendra, “Performance analysis of mobility-assisted routing,” Proceedings of MobiHoc, 2006, pp. 49–60.
• V. Srinivasan, M. Motani and W. T. Ooi, “Analysis and Implications of Student Contact Patterns Derived from Campus Schedules,” MobiCom’06, September 23–26, 2006.
• J. Su, A. Chin, A. Popivanova, A. Goely and E. Lara, “User Mobility for Opportunistic Ad-Hoc Networking,” 6th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), Dec. 2004.
• K. Tan, Q. Zhang and W. Zhu, “Shortest Path Routing in Partially Connected Ad Hoc Networks,” IEEE Globecom, 2003.
• M. M. B. Tariq, M. Ammar and E. Zegura, “Message ferry route design for sparse ad hoc networks with mobile nodes,” ACM MobiHoc ‘06, May 22-25, 2006.
• Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, “The Broadcast Storm problem in a mobile ad hoc network,” Wireless Networks, vol. 8, no. 2/3, 2002.
• A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hoc networks,” Technical Report CS-200006, Duke University, 2000.
• Y. Wang, S. Jain, M. Martonosi, and K. Fall, “Erasure coding based routing for opportunistic networks,” Proceedings of ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005.
• J. Widmer and J.-Y. L. Boudec, “Network coding for efficient communication in extreme networks,” Proceedings of ACMSIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005.
• E. Yoneki, P. Hui and J. Crowcroft, “Visualizing Community Detection in Opportunistic Networks,” CHANTS’07, September 14, 2007.
• E. Yoneki, P. Hui, S. Chan, and J. Crowcroft, “A socio-aware overlay for publish/subscribe communication in delay tolerant networks,” Proceedings of MSWiM, 2007, pp. 225–234.
• Q. Yuan, I. Cardei, and J. Wu, “Predict and Relay: An Efficient Routing in Disruption-Tolerant Networks,” MobiHoc ’09, May 2009.
• W. Zhao and M. Ammar, “Proactive routing in highly-partitioned wireless ad hoc networks,” 9th IEEE International Workshop on Future Trends of Distributed Computing Systems, May, 2003.
• W. Zhao, M. Ammar and E. Zegura, “A message ferrying approach for data delivery in sparse mobile ad hoc networks,” Proceedings of MobiHoc, 2004, pp 187-198.
• W. Zhao, M. Ammar and E. Zegura, “Controlling the Mobility of Multiple Data Transport Ferries in a Delay-Tolerant Network,” INFOCOM, 2005.
• W. Zhao, Y. Chen, M. Ammar, M. D. Corner, B. N. Levine, and E. Zegura, “Capacity enhancement using throwboxes in dtns,” IEEE MASS, October 2006.