Reasonable routing in delay/disruption tolerant networks
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
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.
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
