Reseach On Routing Algorithms In Delay Tolerant Network

With the advancement in technology, the communication devices with wireless interfaces become more and more universal. In the process, Delay Tolerant Network(DTN) appeared as a special kind of wireless mobile network. Unlike traditional wireless networks, DTN is lack of continuous network connections and is characterized by nodes frequently moving, limited resources, etc. Under limitation of these characteristics of DTN, the routing of DTN becomes very challenging, because it has to deal with network partitioning, long delay and dynamic topology, etc. DTN was originally intended for interplanetary network and have been applied to a series of difficult environments: wireless sensor network, military self-organizing network, vehicle network and social network, and so on. In DTN, a fully connected path from source to destination is unlikely to exist. Therefore, in DTN, message delivery relies on opportunistic routing where nodes use store-carry-and-forward paradigm to route the messages. However, effective forwarding based on a limited knowledge of contact behavior of nodes is still challenging.Firstly this thesis studied an existed probabilistic routing protocol using history of encounters and transitivity(Prophet) in DTN. Then this thesis introduced a extra metric, conditional intermeeting time, which computes the average intermeeting time between two nodes relative to a meeting with a third node using only the local knowledge of the past contacts. This thesis also analyzed the introduced metric and show its significance for routing. Next this thesis introduced contact duration and analyzed its rationality. Finally this thesis made the improvement on probability calculation and forward strategy of Prophet respectively by exploiting contact duration and conditional intermeeting time. The experimental results showed that the improved Prophet effectively reduced the latency, increased the message delivery rate and reduced the network overhead.Secondly on the basis of the improved Prophet, this thesis analyzed deficiency on spray phase and wait phase of Spray and Wait(SW) routing algorithm and then proposed an improved SW routing algorithm based on probability. In spray phase of original SW routing algorithm, nodes blindly spread copies of the message to all the other nodes encountered. Based on this, this thesis proposed an improvement on spray phase of SW routing algorithm. Considering message delivery probability of all nodes with the scope of transmission, it calculated copies of the message to be distributed to every other node applying the formula. Moreover, in wait phase, the nodes carrying copy of the message no longer waited and then directly delivered the destination node. When a node encountered the other node having higher delivery probability and less conditional intermeeting time in the node moving process, it forwarded copy of the message to this node. Simulation results showed that improved routing algorithm had good performance on delivery ratio, average end-to-end latency and network overhead.