Research On Satellite Time-varying Network Routing Algorithm

In recent years,with the rapid increase in the demand for information transmission by humans,communication technology has developed rapidly and many new results have been achieved.As a platform for information transmission,the network is a crucial part of communication.However,in the process of building a terrestrial network,it is inevitable that it will be limited by the topography.The ground network alone cannot meet the demand of human beings for communication anywhere on the globe.The satellite network communication system,which uses man-made earth satellites as space relay nodes and is built in outer space,can provide a full coverage of the earth's surface and is almost unaffected by geographical factors.To a great extent,it will not suffer natural disasters.As a result,satellite networks have become a major trend in the development of communications networks.However,due to high costs and difficult technical requirements,satellite network resources are still very scarce.With the rapid growth of satellite communications users,how to improve the satellite network throughput so that it can meet the communication needs of more users is an urgent problem to be solved.Therefore,this paper studies the satellite network routing algorithm aiming at maximizing throughput.In order to solve the problem of maximum satellite network throughput,the maximum flow method is generally used for analysis and solution.Its main function is to solve the problem of how to maximize the utilization of the network with limited link capacity.Therefore,obtaining the maximum flow of satellite network has important guiding significance for the maximization of precious rare satellite link resources.This thesis is also based on this idea for research,mainly to do the following work:(1)Analyze the existing satellite time-varying network modeling method for satellite network topology dynamics,mainly including time-sliced static graph model and time aggregated graph model.Then,the time-varying network maximum-flow routing algorithm based on the time-sliced static graph model is introduced,mainly including Ford-Fulkerson algorithm,shortest augmentation path algorithm and general pre-flow advancing algorithm.Finally,the MFRSN of the satellite network's maximum flow routing algorithm based on the time aggregated graph model is introduced.(2)In view of the shortcomings of the existing satellite time-varing network maximum flow routing algorithm based on time-sliced static graph model,combining the idea of pre-flow promotion algorithm,the concept of "equivalent equalization flow division" is proposed to improve the load balancing performance of the algorithm,and a fast convergence strategy is introduced to improve the efficiency of the algorithm.Finally,using the above method,a time-varying network load balancing maximum flow routing algorithm based on time-sliced and pre-flow advancing(TPLMFTN)is proposed.The complexity and accuracy of the algorithm are analyzed.Compared with the previous algorithms,the TPLMFTN algorithm allows the traffic to be more evenly distributed on the satellite link based on the maximum flow,and improves the rationality of the utilization of satellite network resources.Finally,aiming at the degree of load balancing of satellite networks,the balance is used as a measure to compare the performance of the TPLMFTN algorithm and the existing algorithms.(3)Aiming at the shortcomings of the current maximum flow routing algorithm for satellite time-varying network based on the time aggregated graph model,a new method for calculating the single-path throughput of a periodically time-varying network is proposed.In order to more accurately characterize the time-varying characteristics of satellite networks,a periodically time-varying time aggregated graph model is proposed,and a satellite time-varying network optimization model with the goal of maximizing throughput is constructed.Combining the above methods and models,a satellite time-varying network maximum flow routing algorithm based on the equivalent static model(ESMMFSN)is proposed.Finally,using the network throughput as an indicator,the performance of the ESMMFSN algorithm and the MFRSN algorithm is compared through simulation.