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. A. Beaufour, M. Leopold, and P. Bonnet. Smart-tag based data dissemination. In Proc. ACM Inter. Workshop on Wireless Sensor Nets and Applications(WSNA), Sept. 2002.]]
6. J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Mobile Computing and Networking, pages 85--97, 1998.]]
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. H. Dubois-Ferriere, M. Grossglauser, and M. Vetterli. Age matters: efficient route discovery in mobile ad hoc networks using encounter ages. In Proc. ACM MobiHoc'03, June 2003.]]
12. R. Durrett. Probability: Theory and Examples. Duxbury Press, second edition, 1995.]]
13. N. Glance, D. Snowdon, and J.-L. Meunier. Pollen: using people as a communication medium. Computer Networks, 35(4):429--442, Mar. 2001.]]
14. M. Grossglauser and D. N. C. Tse. Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Transactions on Networking., 10(4):477--486, 2002.]]
15. S. Jain, K. Fall, and R. Patra. Routing in a delay tolerant network. In Proc. ACM/ Sigcomm, Aug. 2004.]]
16. D. B. Johnson, D. A. Maltz, and J. Broch. Ad hoc networking, chapter 5 - DSR: the dynamic source routing protocol for multihop wireless ad hoc networks. Addison-Wesley, 2001.]]
17. 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. In Proc. ASPLOS'02, Oct. 2002.]]
18. Q. Li and D. Rus. Communication in disconnected ad hoc networks using message relay. Journal of Parallel and Distributed Computing., 63(1):75--86, 2003.]]
19. A. Lindgren, A. Doria, and O. Schelen. Probabilistic routing in intermittently connected networks. SIGMOBILE Mobile Computing and Communications Review, 7(3):19--20, 2003.]]
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. N. Sadagopan, F. Bai, B. Krishnamachari, and A. Helmy. Paths: analysis of path duration statistics and their impact on reactive manet routing protocols. In Proc. of MobiHoc'03, pages 245--256, June 2003.]]
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. 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, 8(2/3):153--167, 2002.]]
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, and E. Zegura. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In Proc. MobiHoc'04, 2004.]]

Index Terms

• Networks

  • Network protocols

    • Network layer protocols

      • Routing protocols

  • Network types

    • Mobile networks

    • Wireless access networks