Spray and wait: an efficient routing scheme for intermittently connected mobile networks

ABSTRACT

Intermittently connected mobile networks are sparse wireless networks where most of the time there does not exist a complete path from the source to the destination. These networks fall into the general category of Delay Tolerant Networks. There are many real networks that follow this paradigm, for example, wildlife tracking sensor networks, military networks, inter-planetary networks, etc. In this context, conventional routing schemes would fail.To deal with such networks researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention, which can significantly degrade their performance. Furthermore, proposed efforts to significantly reduce the overhead of flooding-based schemes have often be plagued by large delays. With this in mind, we introduce a new routing scheme, called Spray and Wait, that "sprays" a number of copies into the network, and then "waits" till one of these nodes meets the destination.Using theory and simulations we show that Spray and Wait outperforms all existing schemes with respect to both average message delivery delay and number of transmissions per message delivered; its overall performance is close to the optimal scheme. Furthermore, it is highly scalable retaining good performance under a large range of scenarios, unlike other schemes. Finally, it is simple to implement and to optimize in order to achieve given performance goals in practice.

REFERENCES

• 1: Delay tolerant networking research group. http://www.dtnrg.org.
• 2: Disruption tolerant networking. http://www.darpa.mil/ato/solicit/DTN/.
• 3: Sensor networking with delay tolerance (sendt). http://down.dsg.cs.tcd.ie/sendt/.
• 4: D. Aldous and J. Fill. Reversible markov chains and random walks on graphs. (monograph in preparation.). http://stat-www.berkeley.edu/users/aldous/RWG/book.html.
• 5: Allan Beaufour , Martin Leopold , Philippe Bonnet, Smart-tag based data dissemination, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570749]
• 6: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 7: S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, and K. Scott. Delay-tolerant networking: an approach to interplanetary internet. IEEE Communications Magazine, 41:128--136, 2003.
• 8: X. Chen and A. L. Murphy. Enabling disconnected transitive communication in mobile ad hoc networks. In Proc. of Workshop on Principles of Mobile Computing, colocated with PODC'01, Aug. 2001.
• 9: A. Doria, M. Udon, and D. P. Pandey. Providing connectivity to the saami nomadic community. In Proc. 2nd Int. Conf. on Open Collaborative Design for Sustainable Innovation, Dec. 2002.
• 10: O. Dousse, P. Thiran, and M. Hasler. Connectivity in ad-hoc and hybrid networks. In Proc. of Infocom, June 2002.
• 11: 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]
• 12: R. Durrett. Probability: Theory and Examples. Duxbury Press, second edition, 1995.
• 13: Natalie Glance , Dave Snowdon , Jean-Luc Meunier, Pollen: using people as a communication medium, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.35 n.4, p.429-442, March 2001 [doi>10.1016/S1389-1286(00)00183-3]
• 14: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 15: 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
• 16: David B. Johnson , David A. Maltz , Josh Broch, DSR: the dynamic source routing protocol for multihop wireless ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 17: 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
• 18: Qun Li , Daniela Rus, Communication in disconnected ad hoc networks using message relay, Journal of Parallel and Distributed Computing, v.63 n.1, p.75-86, January 2003 [doi>10.1016/S0743-7315(02)00033-3]
• 19: 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]
• 20: M. Mauve, J. Widmer, and H. Hartenstein. A survey on position-based routing in mobile ad-hoc networks. IEEE Network, 10(6):30--39, 2001.
• 21: C. E. Perkins, E. M. Belding-Royer, and S. R. Das. Ad-hoc on-demand distance vector routing. IETF MANET DRAFT, 2002.
• 22: Narayanan Sadagopan , Fan Bai , Bhaskar Krishnamachari , Ahmed Helmy, PATHS: analysis of PATH duration statistics and their impact on reactive MANET routing protocols, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778444]
• 23: 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, 1:215--233, Sept. 2003.
• 24: T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Multiple-copy routing in intermittently connected mobile networks. Technical Report CENG-2004-12, USC, 2004.
• 25: T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Single-copy routing in intermittently connected mobile networks. In Proc. of IEEE Secon'04, 2004.
• 26: Yu-Chee Tseng , Sze-Yao Ni , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Wireless Networks, v.8 n.2/3, p.153-167, March-May 2002 [doi>10.1023/A:1013763825347]
• 27: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, Apr. 2000.
• 28: 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

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

General Terms:
Algorithms, Performance

Keywords:
ad-hoc networks, delay tolerant networks, intermittent connectivity, routing