Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front Comput Sci Chin    0, Vol. Issue () : 327-334    https://doi.org/10.1007/s11704-011-0139-2
Reasonable routing in delay/disruption tolerant networks
Haizheng YU1,2(), Jianfeng MA2, Hong BIAN3
1. College of Mathematics and System Sciences, Xinjiang University, Urumqi 830046, China; 2. Key Laboratory of Computer Network and Information Security, Xidian University, Xi’an 710071, China; 3. School of Mathematical Sciences, Xinjiang Normal University, Urumqi 830054, China
 Download: PDF(249 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Delay/disruption tolerant networking (DTN) is an approach to networking where intermittent connectivity exists: it is often afforded by a store and forward technique. Depending on the capability of intermediary nodes to carry and forward messages, messages can be eventually delivered to their destination by mobile nodes with an appropriate routing protocol. To have achieved a successful delivery, most DTN routing protocols use message duplication methods. Although messages are rapidly transferred to the destination, the redundancy in the number of message copies increases rapidly. This paper presents a new routing scheme based on a stochastic process for epidemic routing. Message redundancy is efficiently reduced and the number of message copies is controlled reasonably. During the contact process of nodes in the network, the number of message copies changes, and according to the variability in the number of copies, we construct a special Markov chain, birth and death process, on the number of message copies then calculate and obtain a stationary distribution of the birth and death process. Comparing the theoretical model with the simulation we have performed we see similar results. Our method improves on time-to-live (TTL) and anti-packet methods, in both redundancy and delivery success efficiency.

Keywords delay/disruption tolerant networks (DTN)      routing algorithm      Markov chain      message redundancy     
Corresponding Author(s): YU Haizheng,Email:haizhengyu@gmail.com   
Issue Date: 05 September 2011
 Cite this article:   
Haizheng YU,Jianfeng MA,Hong BIAN. Reasonable routing in delay/disruption tolerant networks[J]. Front Comput Sci Chin, 0, (): 327-334.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-011-0139-2
https://academic.hep.com.cn/fcs/EN/Y0/V/I/327
1 Fall K. A delay-tolerant network architecture for challenged internets. In: Proceedings of 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications . 2003, 27-34
2 Fall K, Farrell S. Dtn: An architectural retrospective. IEEE Journal on Selected Areas in Communications , 2008, 26(5): 828-836
doi: 10.1109/JSAC.2008.080609
3 McMahon A, Farrell S. Delay- and disruption-tolerant networking. IEEE Internet Computing , 2009, 13(6): 82-87
doi: 10.1109/MIC.2009.127
4 Zhang Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges. IEEE Communications Surveys and Tutorials , 2006, 8(1): 24-37
doi: 10.1109/COMST.2006.323440
5 Delay-tolerant networking research group. http://www.dtnrg.org/
6 Small T, Haas Z J. Resource and performance tradeoffs in delay-tolerant wireless networks. In: Proceedings of 2005 ACM SIGCOMM workshop on Delay-tolerant networking .2005, 260-267
7 Wang Z K, Yang X Q. Birth and death processes and Markov chains. Beijing: Science Press, 2006
8 Vahdat A, Becker D. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University . 2000
9 Spyropoulos T, Psounis K, Raghavendra C S. Efficient routing in intermittently connected mobile networks: the single-copy case. IEEE/ACM Transactions on Networking , 2008, 16(1):63-76
doi: 10.1109/TNET.2007.897962
10 Spyropoulos T, Psounis K, and Raghavendra C S. Efficient routing in intermittently connected mobile networks: the multiple-copy case. IEEE/ACM Transactions on Networking , 2008, 16(1): 77-90
doi: 10.1109/TNET.2007.897964
11 Spyropoulos T, Psounis K, Raghavendra C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In: Proceedings of 2005 ACM SIGCOMM workshop on Delay-tolerant networking . 2005, 252-259
12 Lindgren A, Doria A, Schelén O. Probabilistic routing in intermittently connected networks. In: Proceedings of 1st International Workshop on Service Assurance with Partial and Intermittent Resources. 2004, LNCS , 2004, 3126: 239-254
13 Matsuda T, Takine T. (p,q)-epidemic routing for sparsely populated mobile ad hoc networks. IEEE Journal on Selected Areas in Communications , 2008, 26(5): 783-793
doi: 10.1109/JSAC.2008.080605
14 Shah R C, Roy S, Jain S, Brunette W. Data mules: modeling and analysis of a three-tier architecture for sparse sensor networks. Ad Hoc Networks , 2003, 1(2-3): 215-233
doi: 10.1016/S1570-8705(03)00003-9
15 Zhao W, Ammar M, Zegura E. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In: Proceedings of 5th ACM International Symposium on Mobile Ad hoc Networking and Computing . 2004, 187-198
16 Tang L, Zheng Q, Liu J, Hong X. Selective message forwarding in delay tolerant networks. Mobile Networks and Applications , 2009, 14(4): 387-400
doi: 10.1007/s11036-008-0096-7
17 Seligman M, Fall K, Mundur P. Storage routing for DTN congestion control. Wireless Communications and Mobile Computing , 2007, 7(10): 1183-1196
doi: 10.1002/wcm.521
18 Jain S, Fall K, Patra R. Routing in a delay tolerant network. In: Proceedings of 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications .2004, 145-158
19 Walker B D, Glenn J K, Clancy T C. Analysis of simple counting protocols for delay-tolerant networks. In: Proceedings of 2nd ACM workshop on Challenged networks . 2007, 19-26
20 Groenevelt R, Nain P, Koole G. The message delay in mobile ad hoc networks. Performance Evaluation , 2005, 62(1-4): 210-228
doi: 10.1016/j.peva.2005.07.018
21 Groenevelt R. Stochastic models for ad hoc networks. Dissertation for the Doctoral Degree . Sophia Antipolis: INRIA, 2005
22 Zhang X, Neglia G, Kurose J, Towsley D. Performance modeling of epidemic routing. Computer Networks , 2007, 51(10): 2867-2891
doi: 10.1016/j.comnet.2006.11.028
[1] Yue WU,Chao LU,Yunji CHEN. A survey of routing algorithm for mesh Network-on-Chip[J]. Front. Comput. Sci., 2016, 10(4): 591-601.
[2] Xin LI, Zhe LI, . A MANET accessing Internet routing algorithm based on dynamic gateway adaptive selection[J]. Front. Comput. Sci., 2010, 4(1): 143-150.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed