Research On Multi-policy Routing Protocols In A Delay Network

As a new challenging network architecture, Delay Tolerant Networks(DTNs) are characterized by strong node mobility, frequent network topology partitions, extremely high end-to-end delivery latency, etc. In this case, it is difficult to maintain a stable end-to-end path between the source and the destination. Consequently, successful message transmissions are facing great challenges in DTNs. To solve the lack of end-to-end paths and provide reliable communication services, DTN architecture introduces a bundle layer between application layer and transport layer, and then adopts a “store-carry-forward” routing model to deliver message hop by hop until encountering the final destination. In this case, message's successful delivery greatly depends on the relay node selection strategy. Meanwhile, the lack of paths and high delivery latency result in a large number of messages stored in the network. However, DTNs are usually deployed in extreme environments, and node storage resource, link bandwidth, etc. are strictly limited, which also make message management mechanisms become a challenging issue.In this paper, we study design effective DTNs routing algorithms starting with node selection strategy and message management mechanism. The main research contents include the follows:(1) We study nodes' interaction patterns, find potential social relations between nodes and depict nodes' cluster attributes. And then by dividing nodes into different groups, we flood message copies in target regions with a flooding model based on groups, which greatly reduces message redundancy and network overhead.(2) We study nodes' moving patterns, and then predict the next encounter time between nodes. By taking into account the next communication time and message's remaining time-to-live, we study a utility function to evaluate the probability that a given message can be successfully delivered. Then we design an efficient probabilistic routing to select the optimal relays. In addition, we take message's delivery probability as the optimal target and further model message management mechanism as a 0-1 knapsack optimization problem. And finally, we obtain the optimal solutions by the backtracking algorithm and branch and bound strategy.(3) We study node's community attribute and depict node's moving trajectory among communities so as to deliver message to the target community by locating the destination. Besides, we study local collaborative storage strategy to share storage resource of the nodes that reside in the same community. In this way, message is stored within the target community until encountering the final destination.(4) We study to turn the original network composed of nodes into a network composed of communities and further model it as a community graph model so as to find a socially connected end-to-end path between the source and the destination. And in this case, message's routing process is divided into two phases: inter-community routing and intra-community routing.Extensive simulations are conducted and the results show the rationality and efficiency of the works in this paper. The proposed four routing algorithms achieve great advantages in improving message delivery ratio, reducing network overhead, decreasing end-to-end delivery latency, etc., thus significantly improving the routing performance in DTNs.