Research On Space-based Network Routing Algorithm Based On Time-varying Graph

In the future 6G era,Space-Air-Ground-Ocean(SAGO)integration is the inevitable trend of the development of heterogeneous networks with high bandwidth and large capacity.Global coverage and ubiquitous connectivity are the inherent needs of diversified 6G terminal services such as Internet of things,emergency communication and telemedicine.With the advantages of wide area coverage,high reliability and strong flexibility,the space-based network with low earth orbit(LEO)satellites as the main body has gradually become the key to realize SAGO integration and meet the needs of 6G services.However,the time-varying topology of LEO satellite network limits the improvement of routing performance,which makes it difficult to effectively ensure the quality of service(Qo S)of space-based network.Time varying graph(TVG)is an effective theoretical tool to model the time-varying topology and resource distribution of satellite networks.Efficient and reliable routing algorithm is the key to improve the Qo S of space-based network.Therefore,taking space-based network as the background,this thesis studies the space-based network routing algorithm based on time-varying graph,and simulates and analyzes the proposed algorithms.Firstly,the concept,parameters and related characteristics of satellite network are introduced,and a coordinate graph(CG)model for LEO satellite network is designed.Aiming to the characteristics of satellite network,combined with the on-orbit operation characteristics of satellite,this thesis introduces the satellite orbit parameters,systematically classifies the satellite network according to the orbit height,structural characteristics and networking form,and analyzes the characteristics of LEO satellite constellation from the regularity of topology and the time variability of inter-satellite link(ISL).In order to describe the time-varying satellite network,a CG model is designed.The model can model the three-dimensional topology and resource distribution of LEO polar orbit constellation in two-dimensional Cartesian coordinate system.Secondly,in order to reduce the end-to-end(E2E)delay,a joint minimum hop and earliest arrival(MHEA)algorithm is proposed from the two aspects of hop number and one-hop delay.In order to reduce hop count,the unit displacement vector(UDV)is defined in the CG model to represent the minimum unit of the path,and a minimum hop(MH)routing model is designed to calculate the E2 E minimum hop count.In order to reduce one-hop delay,an earliest arrival(EA)strategy is designed.When calculating the E2 E path in the MH routing model,each satellite that receives the forwarding task independently selects the satellite that meets the earliest arrival time of the task as the next hop node,so as to obtain the local shortest delay path.The simulation results show that the proposed algorithm not only reduces the route count,hop count and delay,but also improves the file delivery ratio,which verifies the feasibility and correctness of the proposed algorithm.Finally,in order to solve the global shortest delay path,a minimum hop binary tree pruning traversal based earliest arrival(MHBTEA)path searching algorithm is proposed.Based on the MH routing model,the algorithm constructs a minimum hop binary tree(MHBT)with the source node as the root node and the destination node as the leaf node.Any path from the root node to the leaf node is the minimum hop path.The traditional preorder traversal method of binary tree is improved,and a pruning traversal algorithm is proposed to search all paths from the root node to the leaf node in the minimum hop binary tree to obtain the minimum hop path set.Then,an earliest arrival path search algorithm is proposed.In the minimum hop path set,the path satisfying the task’s earliest arrival at the destination node is regarded as the global shortest delay path.Simulation results show that the proposed algorithm further reduces the path delay and improves the file delivery ratio than the joint minimum hop and earliest arrival(MHEA)algorithm,which verifies the feasibility and correctness of the proposed algorithm.