Research On The Maximum Flow Model And Algorithm For Damaging Time-Varying Networks

The time-varying network maximum flow problem aims to solve for the total network flow whose arc capacity varies with time.Realistic networks are often in impairment environments,such as computer networks where signal fluctuations can lead to data loss.The existing maximum flow algorithms cannot consider both time-varying factors and impairment environments.Therefore,this paper proposes the idea of using neural network to simulate the maximum flow network to send pulses,and designs a series of neural network algorithms to solve the problem for different impairment environments.The experimental results show that the proposed algorithms can not only obtain the approximate exact solution of the maximum flow problem of the damage time-varying network,but also have a higher computational speed due to the parallel computing feature.The main research contents are as follows.First,a wastage-group neural network model algorithm is proposed for the maximum flow problem of the damage time-varying network.The damage in this problem refers to the loss of flow when the flow passes through the lossy arc,and the time-varying refers to the change of arc capacity with time.The time-varying network environment is complex,and the flow loss due to lossy arcs further increases the difficulty of solving the problem.The wastage-group neural network algorithm uses a grouping strategy that splits the time-varying network into static subnetworks,simplifying the network environment and maximizing the flow by avoiding the flow passing through the loss arc as much as possible.The algorithm consists of two parts.The subnet-pulse neural network algorithm is used to split the network into a collection of subnets.The node-mark neural network algorithm is used to compute the subnetwork flows.Experimental results on data sets such as the U.S.water network show that the wastage-group neural network algorithm can obtain an exact solution and has a faster computational speed than other algorithms in large networks.Second,a regret-index neural network model algorithm is proposed for the maximum flow problem in fuzzy damage time-varying networks.The problem aims to solve the maximum flow of time-varying networks with uncertain flow loss rate,where the fuzzy damage means that the flow loss is a fuzzy range.The arc capacity in time-varying networks is time-dependent,and the fuzzy flow loss further increases the difficulty of path order selection.The minimum regret mechanism used by the regret-index neural network algorithm splits the time-varying network into static paths and selects the paths in order according to the minimum regret degree,which achieves the purpose of maximizing the network flow.The algorithm consists of three parts:the path-pulse neural network algorithm for obtaining path loss information,the path regret degree calculation based on the loss information,and the update network flow algorithm for calculating the path flow.Experimental results on datasets such as U.S.wireless networks show that the regret-index neural network algorithm has a smaller error rate and faster computing speed.Third,an available-flow neural network model algorithm is proposed for the dynamic topological impairment time-varying network maximum flow problem.The problem aims to solve the maximum flow of time-varying networks with unknown topology,where the dynamic topology refers to the random reduction of arcs in the network.The difficulty of solving feasible paths in the unknown network structure is increased by the topology change,which leads to the difficulty of calculating the maximum flow of the network.The available-flow neural network algorithm is able to determine the network structure from the return signal and calculate the subnetwork flow at different moments separately.The algorithm consists of two parts: the back-information neural network algorithm for determining the network topology and disassembling the subnets,and the single-path neural network algorithm for calculating the subnetwork flow.Experimental results on datasets such as the US wireless network show that the available-flow neural network algorithm can obtain accurate solutions in all cases and has a faster computational speed compared to other algorithms.