Research On Delay-Tolerant Network Routing

Being different from the Internet,many networks used in industry seem far from people's sight,but they play an important role in people's life,such as road inspect network,temporary communication network in disaster etc.These networks have the characteristics such as:the com-munication is on radio,nodes have limited capability,nodes move frequently and the environment is tough etc.People present the concept DTN(Delay-Tolerant Network)to describe these networks and want to establish a suit of protocols accordingly.DTN is defined as an abstract network model in this dissertation,and it's not for all sides of one particular network but for all the networks which possess the characteristic of Delay-Tolerant. Delay-Tolerant means network protocol can work in the challenging environment in which the links among nodes are very unstable,high asymmetric,the nodes' capability differ from each other, the topology of the network is volatile and suffers from long-time partitioning and the traffic's distribution is unpredictable.Essentially,DTN discards the basic assumption in traditional network—the existence of a path between source node and destination node during the delivery process of a packet.Even AODV(Ad hoc On-demand Distance Vector)protocol of MANET(Mobile Ad hoc Network)which deals with the dynamic topology situation needs this assumption—its route discovery procedure can complete only when there exists a path.As an self-organized network,DTN's main problem is routing.DTN actually redefines "path" when it discards the basic assumption in traditional network.In traditional network including MANET,the topology is relatively stable compared with the RTT(Round Trip Time)of a packet, so paths have nothing to do with time during the delivery.In DTN,the topology may have changed after one forwarding—some links break down while new ones appear,so the paths have a time dimension,that is,a path makes sense only when it still exists when the packet arrives one of its ends.As for routing algorithms,the input is not a steady graph but a time-variant graph,and the output is not a path but a sequence of(link,time)duplets.Researchers provide Space-Time graph to describe the topology of DTN.In Space-Time graph,the nodes are in a series of layers,and a layer corresponds to a snapshot of the topology,so a likely path of a packet is from the source in the first layer to the destination in the lower layer(along with time).This dissertation focuses on DTN routing issues.DTN routing protocols can be classified into two classes:protocols that need Oracles(Oracle is a concept to describe transcendental knowledge in DTN)and the others.The use of Oracles is another important difference between DTN and traditional network.Oracle is part of global routing information,and it can't be constructed by routing information exchange protocol as the traditional network does,because DTN's routing algorithm needs the future routing information.By researching the routing protocols of MANET,WSN etc.this dissertation has the contribu-tions to DTN as below:This dissertation provides a mathematical model for the one-hop delay which is the most im-portant parameter in routing information set in DTN.The criterion of choosing the optimal path is delay because small delay means packets spend less time in the network so it can save the capacity of the network.This dissertation puts forward a model of the delay and figures out its components: transmission time,queue time,time before the link's set-up and the propagation time.By consider-ing the link as the service window a new "non-exhaustive queue system with probabilistic vacation" is presented to analyze the relationship among the delay issues.The distribution of queue length and delay,and the relation among the mathematical expectations of these parameters are obtained. The simulations prove the conclusions.This dissertation considers the precision of the Oracles and presents AED(Adaptive Earliest Delivery)algorithm based on standard Earliest Delivery.Earliest Delivery algorithm needs a very strict Oracle,which makes it hard to use.On the other hand,there exist some situations that their links capacity can be obtained in advance,such as satellite network etc.But the Oracle may have a little difference from the real situation,that is,error.So how to analyze the error and how to make protocol survive from the error should be brought into consideration.Firstly,we put forward a model to describe the error.Secondly,we give the function of the packet drop ratio along with error.Finally,we use the standard deviation to modify the metric then present AED.Simulations prove that AED can endure error much better.This dissertation presents a framework PM~3D to detect mobility models based on template operations and a routing model to deal with mobility models.Mobility model is used to describe the characteristics of the mobility of node(s),and it doesn't focus on physical parameters but the macro mobility in large scale.The mobility models are reflected by the up and down state of links) in Space-Time graph.PM~3D is a framework to detect these mobility models and store them in a universal data structure—VL(Visit List).The use of mobility models doesn't depend on routing algorithms,and we provide a set of interfaces to let routing algorithms to visit the VLs and use them in route decision.Simulations prove that PM~3D can detect mobility models,reflect the change of network topology,and improve the delivery ratio.