Research On DTN Routing Algorithm Based On Time-varying Graph

Recently,many countries and companies pay more attention to the application of space network,which induces the boom of construction of space network and study of key technology.Routing algorithm,in some ways,is the key factor to operate network efficiently.Therefore,it is important to design an efficient routing algorithm for space network.Space network is a typical Delay Tolerant Networks(DTNs),which has high link delay and intermittent connectivity,so using traditional Internet protocol would cause the low link utilization,and it would be tough to guarantee the quality of service.Although NASA has proposed CGR(contact graph routing)algorithm to adapt the DTNs environment,it still has many problems and the ability of service guarantee is not as well as considered.In view of the feature of space network and the demand of efficient routing algorithm,this paper's works are mainly as follows:Firstly,this paper analyzes the shortage of traditional static graph theory in DTNs.Based on the shortage that it is difficult to make good use of network resource by using static graph theory and the problem of packet loss caused by high link error rate in DTNs,combined with the demand of Qo S guarantee with single service,this paper designs a DTNs Reliable Link Capacity Routing Algorithm based on Time-varying Graph(TDRR).By using the storage time aggregated graph and analyzing the effect of link error rate,TDRR introduces the residual capacity correction model and the edge capacity correction model of storage time aggregated graph,fixed the ratio of link capacity when sending data,which improves the reliability of routing algorithm with storage time aggregated graph model.In addition,by using maximum-flow algorithm,TDRR could transfer single service to multipath with lower delay and higher delivery rate.Finally,with MATLAB simulation,this paper compares the performance between TDRR and Dijkstra,and shows that TDRR has a better performance.Secondly,considering the effect of link error rate and traffic volume,this paper designs a DTNs Routing Algorithm based on Service Sensitive(SSDR).SSDR introduces the topology updating mechanism of multi-service concurrency and that mechanism is able to queue and process the demand of multi-service and then update network topology in real time,which decreases the probability for multi-service to compete resources.Also,SSDR introduces a routing table format for DTNs,taking the feature of intermittent connectivity into consideration,which makes store-and-forward during data transmission with high efficiency possible.Finally,with MATLAB simulation,this paper compares the performance between SSDR and CGR(contact graph routing),and shows that SSDR has a better performance.Finally,in order to verify the performance of aforementioned routing algorithms,this paper designs and implements a routing algorithm simulation software in DTNs,and implements aforementioned routing algorithms into the software.In addition,this paper designs a testing scenarios based on LEO applications,builds simulation platform,runs the routing algorithm simulation software in DTNs in that simulation platform,and tests the function of the software and the performance of the routing algorithms,which provides platform support for the construction of the space-ground integrated information network in the future.