Spray and forward:Efficient routing based on the Markov location prediction model for DTNs  

作　　者：DANG Fei YANG XiaoLong LONG KePing 

机构地区：[1]Research Center for Optical Internet and Mobile Information Networks （COIMIN）, University of Electronic Science and Technology of China, Chengdu 611731, China [2]School of Computer and Communications Engineering, University of Science and Technology Beijing, Beijing 100083, China

出　　处：《Science China(Information Sciences)》2012年第2期433-440,共8页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant No.60873263);National Basic Research Program of China(Grant No.2007CB310706);National High-Tech Research&Development Program of China(Grant No.2009AA01Z215);New Century Excellent Talents in University(Grant No.NCET-09-0268)

摘　　要：Typical delay tolerant networks （DTNs） often suffer from long and variable delays, frequent connectivity disruptions, and high bit error rates. In DTNs, the design of an efficient routing algorithm is one of the key issues. The existing methods improve the accessibility probability of the data transmission by transmitting many copies of the packet to the network, but they may cause a high network overhead. To address the tradeoff between a successful delivery ratio and the network overhead, we propose a DTN routing algorithm based on the Markov location prediction model, called the spray and forward routing algorithm （SFR）. Based on historical information of the nodes, the algorithm uses the second-order Markov forecasting mechanism to predict the location of the destination node, and then forwards the data by greedy routing, which reduces the copies of packets by spraying the packets in a particular direction. In contrast to a fixed mode where a successful-delivery ratio and routing overhead are contradictory, a hybrid strategy with multi-copy forwarding is able to reduce the copies of the packets efficiently and at the same time maintain an acceptable successful-delivery ratio. The simulation results show that the proposed SFR is efficient enough to provide better network performance than the spray and wait routing algorithm, in scenarios with sparse node density and fast mobility of the nodes.Typical delay tolerant networks （DTNs） often suffer from long and variable delays, frequent connectivity disruptions, and high bit error rates. In DTNs, the design of an efficient routing algorithm is one of the key issues. The existing methods improve the accessibility probability of the data transmission by transmitting many copies of the packet to the network, but they may cause a high network overhead. To address the tradeoff between a successful delivery ratio and the network overhead, we propose a DTN routing algorithm based on the Markov location prediction model, called the spray and forward routing algorithm （SFR）. Based on historical information of the nodes, the algorithm uses the second-order Markov forecasting mechanism to predict the location of the destination node, and then forwards the data by greedy routing, which reduces the copies of packets by spraying the packets in a particular direction. In contrast to a fixed mode where a successful-delivery ratio and routing overhead are contradictory, a hybrid strategy with multi-copy forwarding is able to reduce the copies of the packets efficiently and at the same time maintain an acceptable successful-delivery ratio. The simulation results show that the proposed SFR is efficient enough to provide better network performance than the spray and wait routing algorithm, in scenarios with sparse node density and fast mobility of the nodes.

关 键 词：delay tolerant networks spray and forward Markov position prediction routing algorithm 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] O211.67[自动化与计算机技术—计算机科学与技术]