Research On Mobility Model And Routing In Delay Tolerant Network

In traditional networks, an end-to-end path from the source to the destination node should be found before the message is delivered, and routing algorithms focus on finding a suitable end-to-end path. However, in network environments such as disaster relief and deep space communication, link interruption appears frequently and the existence of end-to-end paths can't be guaranteed because of the adverse communication environment, and the route protocols in traditional networks are no longer applicable. This type of network which has characters of frequent link interruption and long delay is called the Delay Tolerant Network (DTN).In order to deliver messages, DTN utilizes a Store-and-Forward mechanism in which the intermediate node stores messages and forwards them to nodes it encounters. In this manner, messages could be delivered toward the destination hop-by-hop even if no stable end-to-end path exists. As network partition occurs frequently, if only one replica of the message is kept, the message may reach the edge of partitioned network and be failed to be delivered to the destination. In order to increase the message delivery rate, each node can keep forwarded messages and copy them to other nodes it encounters. In this multiple-copy routing manner, several replicas of the same message exist in the network.In both single-copy routing and multiple-copy routing, the message delivery rate depends on the network connectivity and the intermediate node chosen strategy. The network connectivity is a basic requirement for message delivery. If network partition appears continuously, messages would not be delivered successfully, therefore, some controllable nodes should be exploited to improve the network connectivity. On the basis of sufficient network connectivity, message delivery strategies should utilize nodes'mobility characters to increase the message delivery rate and reduce network overhead.Based on the network connectivity and the message forwarding strategy, this dissertation will focus on the deployment of controllable nodes, the mobility model detection for non-controllable nodes and routing algorithms utilizing mobility characters.The main contents and innovations are listed as follows:(1) Analyzed the region topology and coordination mechanism of route design for multiple ferries.In DTN, a type of special controllable node which moves in the network and forwards messages for other node is proposed, and it is called the message ferry because its movement is similar to a ferry boat. Recent research demonstrates that each ferry follows a different movement route can get shorter message delivery delay when the number of ferries is large. In this multiple routes manner, the dissertation divided message delivery into intra-region forwarding and inter-region forwarding. The neighbor relationship of ferries effects the performance of inter-region forwarding, therefore, the region topologies which character the neighbor relationship of ferries should be considered when deploying ferries. The analysis for the message delivery delay and buffer requirements in different region topologies shows that the best region topology is not the same in different number of ferries. According the analysis, a proper region topology could be chosen with given delay and buffer requirement.Through the analysis for the message delivery delay, we found that the multiple routes manner is not always optimal. This dissertation proposed a hybrid deployment manner in which some ferries move with the same route. The analysis shows that the hybrid deployment manner has shorter message delivery delay when the number of normal nodes and ferries satisfies some conditions. Therefore, a proper proportion for hybrid deployed ferries should be chosen according to network parameters and system requirement when deploying message ferries.(2)Proposed a framework for local information based mobility model detection. The framework utilizes the neighbor discovery mechanism to obtain the local connectivity information and detect mobility model in a real-time manner.In wireless networks, most nodes are not controllable, and their mobility should be utilized as much as possible to increase the message delivery rate. The mobility of nodes in real-world network usually has some regularity, and the contact opportunities among nodes could be utilized to assist routing decision if the mobility model of nodes is known. This dissertation proposed a framework for local information based mobility model detection. The detection framework obtains the connectivity matrix through the local connectivity information, and then detects mobility models in a real-time manner according to the connectivity matrix. This framework can detect some typical mobility models, and it has advantages of easy to implement, low overhead and high detection rate. After nodes'mobility models are obtained, routing decision can be optimized. This dissertation proposed a mobility model aware routing algorithm which chooses the traditional routing and the Store-and-Forward mechanism according to the mobility model information dynamically.(3)Proposed a delivery probability prediction based efficient routing algorithm and a buffer management strategy for this type of routing algorithm.The quota-based routing limits the number of message replicas to control overhead. How to increase the message delivery rate with given message replicas is a key problem in quota-based routing. This dissertation analyzed the condition in which the message delivery rate is maximized with the given message replicas, and then proposed a delivery probability prediction based routing algorithm. The proposed routing algorithm predicts delivery probability with the contact opportunities among nodes and allocates the quota of message replicas according to the predicted delivery probability. Because the delivery probability can reflect the contact opportunity of nodes, this manner can utilize the mobility characters and increase message delivery rate, additionally, the algorithm has low overhead as the number of message replicas is limited strictly.The buffer space and communication bandwidth is limited in DTN, and a proper buffer management is necessary to decide the message transmission order and drop order. The dissertation proposed a delivery gain aware buffer management strategy according to the characters of the quota-base routing. The proposed buffer management strategy estimates the message delivery gain using the quota of message replicas and the life time of messages, and then determines the transmission order and drop order of messages according to the message delivery gain. The proposed strategy can improve routing performance significantly in the quota-based routing because the characters of the quota-based routing is considered.