Research On Optimization Models And Hybrid Evolutionary Algorithms In Networking And Data Transmission Of The BeiDou Global Navigation System

As a navigation satellite system independently constructed and operated by China,the Bei Dou Global Navigation Satellite System can provide all-weather,all-time,highprecision,high-reliability positioning,navigation and timing services worldwide,and has been widely applied in various fields such as transportation,public security and urban governance,and plays an important role in economic and technological development.The construction of the Bei Dou system integrates a series of core technologies.The intersatellite link(ISL)is one of the key core technologies to achieve global navigation for the Bei Dou system.The ISL poses a series of new problems and challenges to the operation and management of the Beidou system.The ISL of the Beidou system has two core functions:inter-satellite ranging and inter-satellite communication.The management of ISL influences the system stability and service quality.This paper focuses on the three optimization problems involving ISL management in the satellite-ground integration networking and data transmission of the Beidou system and designs the optimization models and hybrid evolutionary algorithms for them.The main contents and results of the full text are as follows:(1)An optimized framework for the satellite-ground integration networking and data transmission is designed.The operation processes of the ISL assignment,satellite data downloading and ground data uploading operations in the satellite-ground integration networking and data transmission are described,and the relationship of them are analyzed,which shows that the ISL assignment results are the prerequisite of the other two operations and provides the logical foundation of the full research.The optimization requirements of three operations are analyzed and the performance indicators are listed,which are the basis for the subsequent optimization models.Considering that three optimization problems are all combinatorial optimization problems,a hybrid evolutionary algorithm design framework is proposed,that combines the advantages of construction heuristic algorithms,evolutionary algorithms,and local search algorithms,and guides the design of subsequent optimization algorithms.(2)The model and algorithms of the ISL assignment optimization are studied.First,a mathematical programming model of the ISL assignment optimization problem is established based on the requirements and constraints of the ISL,and the problem is proved as an NP-hard problem by implementing a reduction of edge coloring problem to it.The construction strategy based on graph maximum matching is proposed,and based on it,two hybrid construction algorithms are proposed,where the rolling Weight matching algorithm(RWM)optimizes the ranging objective,and the dynamic weighted multi-objective matching algorithm(DWMOM)optimizes both ranging and communication objectives.With the integration of the graph matching construction strategy with the multi-objective genetic framework,a matching-based multi-objective hybrid genetic algorithm(MMOHGA)is proposed,where the maximum matching algorithm is used to realize single-slot ISL assignment,and the genetic mechanism is used to realize the iterative optimization of multi-slot solutions.Through the experiments based on the Bei Dou navigation network,the results show that the RWM algorithm finds a good solution close to the optimal solution in better time efficiency for the ranging objective;the DWMOM algorithm has achieved better results than the existing methods for both ranging and communication objectives.The MMOHGA algorithm obtains the non-dominated solution set of the problem and provides users with more options.Combining the software module design requirements of the Bei Dou system,the engineering application way of the algorithms is given.(3)The model and algorithm of the satellite data downloading routing optimization are designed.Based on the generation frequency and transmission timeliness of the satellite data,the network capacity limitations have to be considered in the inter-satellite routing design.To describe changes in the data volume on satellites and ISLs,a flow-based model conversion strategy is proposed,that converts the satellite data downloading routing optimization problem into a single-path multi-commodity flow problem with node capacity,and an integer programming model is established.A knowledge-guided hybrid evolutionary algorithm(KGHEA)is proposed,where a path assignment construction algorithm is designed based on the path performance knowledge,evolutionary selection,cross and mutation operators are designed based on the individual performance and structure knowledge,and two local search operators are designed based on the conflict degree and relevance knowledge.Experimental instances of different scales are designed based on the Bei Dou constellation,and experimental results verify the effectiveness of the KGHEA algorithm.At the same time,the influence of different parameters on algorithm performance is analyzed,and the processing method of the algorithm applied to the actual project is described.(4)The model and algorithm of the ground data uplink routing optimization are studied.The number and capacity constraints of node satellites are analyzed,and an integer programming model of the ground data uplink routing optimization problem is established.By implementing the reduction from the P-median problem to it,the ground data uplink routing optimization problem is proved as an NP-hard problem.Then,a hybrid genetic programming algorithm for gene expression(HGPGE)is proposed.The encoding and decoding methods for gene expression are given,and a construction algorithm based on path scoring is proposed where path score is obtained through the mathematical formula generated by the gene expression decoding;11 feature parameters are extracted according to the problem characteristics,and a constant feature parameter is introduced to enhance the gene expression ability;The selection strategy with elite retention,two crossover operators and three mutation operators are defined.Two application scenarios and two solution modes of the HGPGE algorithm are designed.The experimental results verify the effectiveness of the HGPGE algorithm,the applicability of the two solution modes in different application scenarios is analyzed,and the application way of the algorithm in the construction of the Bei Dou project is given.