Realization of Maximum Flow in DTN and Application in CGR

The maximum flow problem based on contact graph in DTN is very important for routing and data planning. Common topological graphs with non-sequential changes include Dinic, ISAP and other deterministic algorithms for solving the maximum flow between two nodes. But these algorithms cannot be directly applied to topological networks with time series changes. At present, Iosifidis.G has given a solution to this problem based on the time expansion graph, but his method requires high storage space, and the increase in the number of nodes means increasing high time complexity accordingly. In this paper, we propose a method of dismantling and reconstructing the graph to solve the maximum flow problem in the continuously changing network. Compared with the SP algorithm of Iosifidis.G, this method does not require equal time slot splitting of each node, and uses discretization to reduce the scale of the graph.  Finally, we add this algorithm to CGR to optimize DTN data transmission, improve data delivery rate and reduce unnecessary link occupation. The experimental results show that the optimized CGR can increase by 3% on average delivery rate, reducing link usage by 4%.