Reliable and efficient message delivery in delay tolerant networks using rateless codes

ABSTRACT

In this paper, we consider the problem of multiple unicast message delivery in Delay Tolerant Networks (DTNs). Long delays, mobility of nodes, and lack of connectivity that are characteristics of such network make this problem very challenging. Additionally, expiry of packets in a network, considered a useful means of regulating resource consumption, reduces reliability and increases the latency of message delivery. Traditional approaches to message delivery in such networks was based on transmitting multiple copies of entire message blocks. Recently, the application of simple erasure-based codes to messages were considered. This option opened up an interesting area of research. In this paper, we effect reliable message delivery with improved latency even in the presence of packet expiry and intermittent connectivity by applying rateless codes at the source where a message is generated. We perform extensive simulations on a variety of trace data from mobility models such as the UMassDieselNet testbed, an area-based random waypoint model, and a simple campus bus model. Results reveal the superiority of our scheme in comparison to other present schemes.

REFERENCES

• 1: Christian Bettstetter , Hannes Hartenstein , Xavier Pérez-Costa, Stochastic properties of the random waypoint mobility model, Wireless Networks, v.10 n.5, p.555-567, September 2004 [doi>10.1023/B:WINE.0000036458.88990.e5]
• 2: J. Burgess and B. N. Levine. CRAWDAD data set umass/diesel (v. 2006-01-17). Downloaded from http://crawdad.cs.dartmouth.edu/umass/diesel, Jan. 2006.
• 3: Ling-Jyh Chen , Chen-Hung Yu , Tony Sun , Yung-Chih Chen , Hao-hua Chu, A hybrid routing approach for opportunistic networks, Proceedings of the 2006 SIGCOMM workshop on Challenged networks, p.213-220, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162654.1162658]
• 4: C. Di, D. Proietti, I. E. Telatar, T. Richardson, and R. Urbanke. Finite-length analysis of low-density parity-check codes on the binary erasure channel. IEEE Trans. Inform. Theory 48:1570--1579, June 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: Sushant Jain , Michael Demmer , Rabin Patra , Kevin Fall, Using redundancy to cope with failures in a delay tolerant network, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 7: 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
• 8: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing volume 353. Kluwer Academic Publishers, 1996.
• 9: H. Jun, M. Ammar, and E. Zegura. Power management in delay tolerant networks: A framework and knowledge-based mechanisms. In 2nd IEEE Conference on Sensor and Ad Hoc Communication and Networks Sept 2005.
• 10: A. Lindgren, A. Doria, and O. Scheln. Probabilistic routing in intermittently connected networks, 2003.
• 11: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 12: P. Maymounkov and D. Mazieres. Rateless codes and big downloads. Proc. of the 2nd International Workshop on Peer-to-Peer Systems 2003.
• 13: S. Merugu, M. Ammar, and E. Zegura. Routing in space and time in networks with predictable mobility. Technical Report GIT-CC-04-7, Georgia Institute of Technology, 2004.
• 14: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 15: T. J. Richardson and R. L. Urbanke. The capacity of low-density parity-check codes under message-passing decoding. IEEE Trans. Inform. Theory 47:599--618, February 2001.
• 16: Amin Shokrollahi, Raptor codes, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2551-2567, June 2006 [doi>10.1109/TIT.2006.874390]
• 17: M. A. Shokrollahi. Capacity-achieving sequences. in IMA Volumes in Mathematics and its Applications 123:153--166, 2000.
• 18: 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]
• 19: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks, 2000.
• 20: Yong Wang , Sushant Jain , Margaret Martonosi , Kevin Fall, Erasure-coding based routing for opportunistic networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.229-236, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080140]
• 21: Jörg Widmer , Jean-Yves Le Boudec, Network coding for efficient communication in extreme networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.284-291, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080147]
• 22: Wenrui Zhao , Mostafa H. Ammar, Message Ferrying: Proactive Routing in Highly-Partitioned Wireless Ad Hoc Networks, Proceedings of the The Ninth IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS'03), p.308, May 28-30, 2003
• 23: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

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

General Terms:
Algorithms, Performance, Reliability

Keywords:
Poisson process, delay tolerant networks, rateless codes