Estimation based erasure-coding routing in delay tolerant networks

ABSTRACT

Wireless Delay Tolerant Networks (DTNs) are intermittently connected mobile wireless networks. Some well-known assumptions of traditional networks are no longer true in DTNs, which makes routing in DTNs a challenging problem. We observe that mobile nodes in realistic wireless DTNs may always have some mobility pattern information which can be used to estimate one node's ability to deliver a specific message. This estimation can greatly enhance the routing performance in DTNs. Furthermore, we adopt an alternative way to generate redundancy using erasure coding. With a fixed overhead, the erasure coding can generate a large number of message-blocks instead of a few replications, and therefore it allows the transmission of only a portion of message to a relay. This can greatly increase the routing diversity when combined with estimation-based approaches. We have conducted extensive simulations to evaluate the performance of our scheme. The results demonstrate that our scheme outperforms previously proposed schemes.

REFERENCES

• 1: D. B. Amin Vahdat. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, April 2000.
• 2: S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, keith Scott, and H. Weiss. Delay-tolerant networking: An approach to interplanetary Internet. IEEE Communications Magazine, June 2003.
• 3: 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]
• 4: Pan Hui , Augustin Chaintreau , James Scott , Richard Gass , Jon Crowcroft , Christophe Diot, Pocket switched networks and human mobility in conference environments, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.244-251, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080142]
• 5: 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
• 6: 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. SIGOPS Oper. Syst. Rev., 36(5):96--107, 2002.
• 7: Jérémie Leguay , Timur Friedman , Vania Conan, DTN routing in a mobility pattern space, Proceeding 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]
• 8: 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]
• 9: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 10: 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.
• 11: Mehul Motani , Vikram Srinivasan , Pavan S. Nuggehalli, PeopleNet: engineering a wireless virtual social network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080855]
• 12: T. Spyropoulos, K. Psounis, and C. Raghavendra. Single-copy routing in intermittently connected mobile networks. In Secon'04: The First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, October 2004.
• 13: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceeding 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]
• 14: T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Multi-copy routing in intermittently connected mobile networks. Technical report, USC, 2004.
• 15: K. Tan, Q. Zhang, and W. Zhu. Shortest path routing in partially connected ad hoc networks. In Globecom'03: IEEE 2003 Global Communications Conference, 2003.
• 16: 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]
• 17: Yu Wang , Hongyi Wu, Replication-Based Efficient Data Delivery Scheme (RED) for Delay/Fault-Tolerant Mobile Sensor Network (DFT-MSN), Proceedings of the Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, p.485, March 13-17, 2006 [doi>10.1109/PERCOMW.2006.118]
• 18: Z. Zhang. Intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges. IEEE Survey and Tutorial, first quarter, 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, Design

Keywords:
delay tolerant network, erasure coding, routing protocol