Open Access Open Access  Restricted Access Subscription or Fee Access

Spray Routing in Mobile Intermittent Networks

S. Neelakandan, T. Chindrella Priyadharshini

Abstract


The irregularly connected mobile networks are wireless networks where most of the time there does not exist a complete path from the source to the destination. In this transmission, conventional routing schemes would fail, because they try to establish complete end to-end paths, before any data is sent. To deal with this intermittent 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. With this in mind, we look into a number of ―single-copy‖ routing schemes that use only one copy per message, and hence significantly reduce the resource requirements of flooding-based algorithms. We perform a detailed exploration of the single-copy routing space in order to identify efficient single-copy solutions that (i) can be employed when low resource usage is critical, and (ii) can help improve the design of general routing schemes that use multiple copies. We also propose a theoretical framework that we use to analyze the performance of all single-copy schemes presented, and to derive upper and lower bounds on the delay of any scheme.

Keywords


Delay Tolerant Networks, Intermittent Connectivity, Routing.

Full Text:

PDF

References


T. Spyropoulos, K. Psounis, and C. S. Raghavendra, ―Single-copy routing in intermittently connected mobile networks,‖ in Proc. IEEE Conf. Sensor and Ad Hoc Communications and Networks (SECON), 2004, pp. 235–244.

P. Gupta and P. Kumar, ―Capacity of wireless networks,‖ IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388–404, 2000.

H. Wu, R. Fujimoto, R. Guensler, and M. Hunter, ―Mddv: Mobilitycentric data dissemination algorithm for vehicular networks,‖ in Proc. ACM SIGCOMM Workshop on Vehicular Ad Hoc Networks (VANET), 2004.

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 Netw. J., 2003.

Disruption Tolerant Networking. [Online]. Available: http://www. darpa.mil/ato/solicit/DTN/

S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, K.Scott, and H.Weiss, ―Delay-tolerant networking: An approach to interplanetary Internet,‖ IEEE Commun. Mag., vol. 41, no. 6, pp. 128–136, Jun. 2003.

J. Heidemann, W. Ye, J. Wills, A. Syed, and Y. Li, ―Research challenges and applications for underwater sensor networking,‖ in Proc. IEEE Wireless Communications and Networking Conf., 2006.

Delay Tolerant Networking Research Group. 2007 [Online]. Available: http://www.dtnrg.org

J. Scott, P. Hui, J. Crowcroft, and C. Diot, ―Haggle: A networking architecture designed around mobile users,‖ in Proc. IFIP Conf.Wireless On-Demand Network Systems and Services (WONS), 2006.

M. Papadopouli and H. Schulzrinne, ―Seven degrees of separation in mobile ad hoc networks,‖ in Proc. IEEE GLOBECOM, 2000.

C. E. Perkins, Ad Hoc Networking, 1st ed. Reading, MA: Addison- Wesley, 2001.

A. Vahdat and D. Becker, ―Epidemic routing for partially connected ad hoc networks,‖ Duke Univ., Durham, NC, Tech. Rep. CS-200006, Apr. 2000.

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. ACM ASPLOS, 2002.

A. Lindgren, A. Doria, and O. Schelen, ―Probabilistic routing in intermittently connected networks,‖ SIGMOBILE Mobile Comput. Commun. Rev., vol. 7, no. 3, 2003.

X. Zhang, G. Neglia, J. Kurose, and D. Towsley, ―Performance modeling of epidemic routing,‖ in Proc. IFIP Networking, 2006.

J.Widmer and J.-Y. Le Boudec, ―Network coding for efficient communication in extreme networks,‖ in Proc. ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005.

T. Spyropoulos, K. Psounis, and C. S. Raghavendra, ―Efficient routing in intermittently connected mobile networks: The single-copy case,‖ IEEE Trans. Networking, vol. 16, no. 1, Feb. 2008.

W. Zhao, M. Ammar, and E. Zegura, ―A message ferrying approach for data delivery in sparse mobile ad hoc networks,‖ in Proc. MobiHoc, 2004.

Q. Li and D. Rus, ―Communication in disconnected ad hoc networks using message relay,‖ J. Parallel Distrib. Comput., vol. 63, no. 1, pp. 75–86, 2003.

S. Jain, K. Fall, and R. Patra, ―Routing in a delay tolerant network,‖ in Proc. ACM SIGCOMM, Aug. 2004.

E. P. C. Jones, L. Li, and P. A. S.Ward, ―Practical routing in delay-tolerant networks,‖ in Proc. ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005.

M. Grossglauser and D. N. C. Tse, ―Mobility increases the capacity of ad hoc wireless networks,‖ IEEE/ACM Trans. Networking, vol. 10, no. 4, pp. 477–486, Aug. 2002.

T. Spyropoulos, K. Psounis, and C. S. Raghavendra, ―Spray and wait: Efficient routing in intermittently connected mobile networks,‖ in Proc. ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005.

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.

T. Small and Z. Haas, ―Resource and performance tradeoffs in delaytolerant wireless networks,‖ in Proc. ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005.

J. Leguay, T. Friedman, and V. Conan, ―DTN routing in a mobility pattern space,‖ in Proc. ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005.

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, 2003.

F. Tchakountio and R. Ramanathan, ―Tracking highly mobile endpoints,‖ in Proc. ACM Workshop on Wireless Mobile Multimedia (WOWMOM), 2001.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.