# An Intersatellite Link Assignment Design for Megaconstellation Based on NSGA-II

Authors: Yadi Zhai; Yihua Hu; Yong Wang; Zhi Lin; Yan Zhang; Qingsong Zhao; Dong Li
Journal: Wireless Communications and Mobile Computing
 (2023)

---

## Abstract

The exploitation of intersatellite links (ISLs) makes the LEO satellite constellation based Internet service widely favored due to its advantages of low-latency and high-speed communications. However, considering the time-varying network topology, limited on-board resources, and high node failure probability, the design of link assignment has become one of the key challenges for the future megaconstellation. To solve this problem, we adopt the idea of modified finite state automaton (FSA) to model the LEO satellite network and use nondominated sorting genetic algorithm (NSGA-II) to optimize the minimum residual capacity and the maximum transmission delay. The simulation results show that our method is more invulnerable and flexible, which is fit for megaconstellations. This work can provide comprehensive guidance on intersatellite link assignment for future megaconstellations.


---

## Body

## 1. Introduction

With the rapid development of satellite technologies, satellite network has become a hot spot of the next-generation Internet for its advantage of seamless coverage and high throughput [1–7]. Compared to geostationary earth orbit (GEO) satellites and medium earth orbit (MEO) satellites, low earth orbit (LEO) satellites operate on lower orbits of 500 to 2000 kilometers, which brings lower transmission delay and higher bandwidth for the satellite-ground links. Besides, the size, cost, and power consumption of user terminals become much lower and more economic.Megaconstellations consist of hundreds to tens of thousands of LEO satellites, and the usage of intersatellite link (ISL) makes them contact each other directly without using assets on earth. Application areas range from high data rate services for banking, education, health services, communication support during natural disasters, and potentially military users.As for these attractive advantages, there has been increasing focus on the construction of megaconstellations. Countries and enterprises all over the world have shown growing interests on seizing orbit resources of LEO satellite constellation. Recent LEO satellite systems, such as Iridium-NEXT [8] and Starlink [9], have been put into use to provide high-speed and low-latency broadband Internet across the globe, while more projects are in plan or under construction.However, the high-speed movement and high loss rate of LEO satellites leads to a highly dynamic network topology. Thousands of satellites distribute on multiple orbital planes; thus, ISLs between satellites on different planes change periodically due to the angle limitations of satellite-borne antennas. The huge amount of satellites also makes them easy to break down inside or be crashed by space junk, which is hard to be quickly replaced and repaired, forcing changes in the topology. For example, most satellites of the first-generation Iridium system have reached their lifetime limit and turned disabled. The invulnerability need of LEO satellite network puts forward higher requirements for link assignment. An efficient link assignment scheme should satisfy the balancing of traffic requirements and high transfer rate.In most existing works, link assignment strategies followed the idea of finite state automaton (FSA) to divide the satellite network’s system period into intervals in which network topology is regarded as static [10]. Researchers have used different algorithms to optimize different link assignment metrics, while optimization objectives vary from one to multiple. Yan et al. [11] optimized the satellite communication delay with the simulated annealing algorithm. For navigation satellite systems, Dong et al. [12] considered two optimal objectives: network delay and position dilution of precision (PDOP). Yang et al. [13] proposed a new algorithm named SNTG-ACA to obtain a more stable satellite network topology. Ren et al. [14] proposed a satellite link assignment optimization algorithm based on reinforcement learning to improve the overall performance of satellite networks.As in the work of predecessors, multiobjectives in the optimization problem were only simplified to single objective by setting weight for each optimization function; we propose a new method using nondominated sorting genetic algorithm II (NSGA-II) to optimize the link assignment of LEO satellite network in this article. This paper is aimed at improving the network topology invulnerability and reducing transmission delay at the same time, and the proposed scheme overcomes the shortage of traditional FSA and fits well with megaconstellations.This paper is organized as follows: in Section2, we discuss the details of the constellation’s system model. The optimization design is briefly introduced in Section 3. In Section 4, we explain the solution and we proposed based on NSGA-II. Simulation results and comparisons with other strategies of an example megaconstellation are given in Section 5. We conclude this paper in Section 6.


## 2. Constellation Modeling

### 2.1. Establishment of Potential ISLs

In most LEO satellite networks, there are up to 4-8 ISLs per satellite to nearby satellites, depending on the number of onboard antennas. According to the structure of ISLs, LEO satellite constellation can be divided into Polar constellation and Walker constellation, also known as the Star Pattern Constellation and Delta Pattern Constellation. Figure1 shows the regular topology of Walker constellation, where Si,j represents the jth satellite on the ith orbital plane. As for Walker constellation, ISLs are through radio frequency or laser links with a wide bandwidth, which are mainly divided into intraplane ISLs and interplane ISLs. The intraplane ISL is the link between the satellite and the nearest two or four satellites in the same orbit plane, which remains unchanged during the mobility of satellites. The interplane ISL is the link between the satellite and the satellite on another orbit plane. Interplane ISLs are dynamically variable during satellite operation because the link connectivity between satellites changes at different times. Therefore, interplane ISLs need to be disconnected and reconnected.Figure 1
Regular topology of Walker constellation.The establishment of potential ISLs is based on the geometric visibility between satellites. In Figure2, to ensure visibility, the length LAB of ISL between satellite A and B should satisfy
(1)LAB<Lmax=R+hA2−R2+R+hB2−R2,where Lmax is the maximum length of the ISL, R represents the sum of the earth’s radius and the height of the ionosphere, and hA and hB are the altitude of the satellites.Figure 2
Geometric visibility constraints between satellites.To build an interplane ISL, the pair of satellites has to stay mutually visible for a while to remain the link connection unchanged. For example, if two satellites satisfy formula (1) now but are moving in the opposite direction, then the ISL between them cannot maintain during the state. We considered a potential ISL exists if and only if the two satellites are visible to each other both at the start and the end of a state.


### 2.2. FSA State Division

Despite the high-speed movement, the positions of LEO satellites remain periodic. The system period (S) of LEO satellite network is defined as the least common multiple of the orbit period and the earth period (i.e., 24 h) and is divided into equal-length states [10]. As each state reaches the same after several periods, the number of states to consider is finite. The link assignment problem of LEO satellite networks can be simplified into a set of generation problems of static topology, and it can be easily calculated offline as a link assignment table with the parameters of the constellation.However, if we calculate each state separately, the link changes might be too frequent, resulting in higher communication delay. A relatively stable network topology has better survivability and helps reduce computing resources, so we should choose a proper link assignment scheme from Pareto optimal solutions, depending on the state of the previous step. Especially, LEO satellites operate with a higher speed at 20,000 km/h, so a proper division of FSA state should make the length of a state no more than the minimum link duration time, and we estimate it by the time it takes for one satellite to reach the position of the next satellite in the same orbit. For a Walker constellation withNL orbital planes and ML satellites each plane operating at a period of T, the maximum length of FSA state is defined as
(2)tmax=TML.


## 2.1. Establishment of Potential ISLs

In most LEO satellite networks, there are up to 4-8 ISLs per satellite to nearby satellites, depending on the number of onboard antennas. According to the structure of ISLs, LEO satellite constellation can be divided into Polar constellation and Walker constellation, also known as the Star Pattern Constellation and Delta Pattern Constellation. Figure1 shows the regular topology of Walker constellation, where Si,j represents the jth satellite on the ith orbital plane. As for Walker constellation, ISLs are through radio frequency or laser links with a wide bandwidth, which are mainly divided into intraplane ISLs and interplane ISLs. The intraplane ISL is the link between the satellite and the nearest two or four satellites in the same orbit plane, which remains unchanged during the mobility of satellites. The interplane ISL is the link between the satellite and the satellite on another orbit plane. Interplane ISLs are dynamically variable during satellite operation because the link connectivity between satellites changes at different times. Therefore, interplane ISLs need to be disconnected and reconnected.Figure 1
Regular topology of Walker constellation.The establishment of potential ISLs is based on the geometric visibility between satellites. In Figure2, to ensure visibility, the length LAB of ISL between satellite A and B should satisfy
(1)LAB<Lmax=R+hA2−R2+R+hB2−R2,where Lmax is the maximum length of the ISL, R represents the sum of the earth’s radius and the height of the ionosphere, and hA and hB are the altitude of the satellites.Figure 2
Geometric visibility constraints between satellites.To build an interplane ISL, the pair of satellites has to stay mutually visible for a while to remain the link connection unchanged. For example, if two satellites satisfy formula (1) now but are moving in the opposite direction, then the ISL between them cannot maintain during the state. We considered a potential ISL exists if and only if the two satellites are visible to each other both at the start and the end of a state.


## 2.2. FSA State Division

Despite the high-speed movement, the positions of LEO satellites remain periodic. The system period (S) of LEO satellite network is defined as the least common multiple of the orbit period and the earth period (i.e., 24 h) and is divided into equal-length states [10]. As each state reaches the same after several periods, the number of states to consider is finite. The link assignment problem of LEO satellite networks can be simplified into a set of generation problems of static topology, and it can be easily calculated offline as a link assignment table with the parameters of the constellation.However, if we calculate each state separately, the link changes might be too frequent, resulting in higher communication delay. A relatively stable network topology has better survivability and helps reduce computing resources, so we should choose a proper link assignment scheme from Pareto optimal solutions, depending on the state of the previous step. Especially, LEO satellites operate with a higher speed at 20,000 km/h, so a proper division of FSA state should make the length of a state no more than the minimum link duration time, and we estimate it by the time it takes for one satellite to reach the position of the next satellite in the same orbit. For a Walker constellation withNL orbital planes and ML satellites each plane operating at a period of T, the maximum length of FSA state is defined as
(2)tmax=TML.


## 3. Optimization Design of Link Assignment

### 3.1. Multiobjective Optimization

A multiobjective optimization problem involves more than one objective function that are to be minimized or maximized. In mathematical terms, a multiobjective optimization problem can be formulated as(3)min/maxx∈Xfix,i=1,2,⋯,n,subjecttogjx≥0,j=1,2,⋯,J,hkx=0,k=1,2,⋯,K,where the integer n≥2 is the number of objective functions, fix stands for the objective functions to be minimized or maximized, and the set X is the feasible set of decision vectors, which is typically X⊆ℝn but it depends on the n-dimensional application domain. The feasible set is typically defined by a set of constraint functions, which is expressed as gjx and hkx.Different from single-objective optimization, in multiobjective optimization, there is usually no feasible solution that can optimize all objective functions simultaneously. Therefore, we focus on the solutions that cannot be improved in any of the objective functions without degrading at least one of the other objectives. In mathematical terms, a feasible solutionx1∈X is said to dominate another solution x2∈X, or in other words, x2 is dominated by x1, if
(1)
solutionx1 is no worse than x2 in all objectives(2)
solutionx1 is strictly better than x2 in at least one objectiveA solutionx∗∈X (and the corresponding outcome fx∗) is called Pareto optimal if it is not dominated by any other solutions. The nondominated set of the entire feasible decision space is called Pareto optimal outcomes, denoted by X∗, and the boundaries defined by the set of all points mapped from it is called Pareto optimal front or Pareto optimal frontier.


### 3.2. Problem Description

We formulate the link assignment problem as a multiobjective optimization problem. The ISL assignment matrix of the satellite network is set as the optimization variable, and the problem is aimed at maximizing the minimum residual capacity and minimizing the maximum transmission delay. We simplify the objective functions to minimize the maximum link traffic and link length. Details are as follows:Variables:N number of satellitesNt number of ISLs per satelliteTij traffic requirements between satellite i and jxijmn carried traffic by source-destination pair m,n that passes through link i,jVij visibility between satellite i and jLij link connectivity between satellite i and jdij the shortest length of link i,jfij total carried traffic on link i,jωi potential traffic demand density level of the grid where satellite i is locatedBoth the visibility matrix and the link assignment matrix contain only 0 and 1 elements:(4)Vij=1,ifsatelliteiandjarevisible,0,otherwise,Lij=1,iflinki,jisestablished,0,otherwise.Objective functions:(5)minimizemaxdij,minimizemaxfij.Constraints:(6)∑jLij≤Nt,Lij=Lji,Lij≤Vij,fij=∑xijmn,xijmn=Tmn,Tij=ωi∗ωjdij.Constraint 7 limits the number of ISLs per satellite to no more than the number of antenna beams. Constraint 8 represents that links between satellites are bidirectional, i.e., if a link from satellitei to satellite j is established, both satellites can connect and communicate with the other. Constraint 9 is to ensure that an ISL can be established only when the two satellites are visible. Constraint 10 shows the calculation of potential traffic requirements between satellites. As it is associated with the link length and traffic density of the area where the endpoint satellites are located, we use the data of gridded world GDP [15] to estimate the economic state of different regions. As demonstrated in Figure 3, the world map is divided into 24×12 grids with a number from 1 to 10 each that represents the potential traffic demand density level of the area. Constraint 11 means that the carried traffic generated by satellite m and n that passes through link i,j is only determined by traffic requirements between source and destination. Constraint 12 gives the total carried traffic on link i,j.Figure 3
Estimation of world traffic density.


## 3.1. Multiobjective Optimization

A multiobjective optimization problem involves more than one objective function that are to be minimized or maximized. In mathematical terms, a multiobjective optimization problem can be formulated as(3)min/maxx∈Xfix,i=1,2,⋯,n,subjecttogjx≥0,j=1,2,⋯,J,hkx=0,k=1,2,⋯,K,where the integer n≥2 is the number of objective functions, fix stands for the objective functions to be minimized or maximized, and the set X is the feasible set of decision vectors, which is typically X⊆ℝn but it depends on the n-dimensional application domain. The feasible set is typically defined by a set of constraint functions, which is expressed as gjx and hkx.Different from single-objective optimization, in multiobjective optimization, there is usually no feasible solution that can optimize all objective functions simultaneously. Therefore, we focus on the solutions that cannot be improved in any of the objective functions without degrading at least one of the other objectives. In mathematical terms, a feasible solutionx1∈X is said to dominate another solution x2∈X, or in other words, x2 is dominated by x1, if
(1)
solutionx1 is no worse than x2 in all objectives(2)
solutionx1 is strictly better than x2 in at least one objectiveA solutionx∗∈X (and the corresponding outcome fx∗) is called Pareto optimal if it is not dominated by any other solutions. The nondominated set of the entire feasible decision space is called Pareto optimal outcomes, denoted by X∗, and the boundaries defined by the set of all points mapped from it is called Pareto optimal front or Pareto optimal frontier.


## 3.2. Problem Description

We formulate the link assignment problem as a multiobjective optimization problem. The ISL assignment matrix of the satellite network is set as the optimization variable, and the problem is aimed at maximizing the minimum residual capacity and minimizing the maximum transmission delay. We simplify the objective functions to minimize the maximum link traffic and link length. Details are as follows:Variables:N number of satellitesNt number of ISLs per satelliteTij traffic requirements between satellite i and jxijmn carried traffic by source-destination pair m,n that passes through link i,jVij visibility between satellite i and jLij link connectivity between satellite i and jdij the shortest length of link i,jfij total carried traffic on link i,jωi potential traffic demand density level of the grid where satellite i is locatedBoth the visibility matrix and the link assignment matrix contain only 0 and 1 elements:(4)Vij=1,ifsatelliteiandjarevisible,0,otherwise,Lij=1,iflinki,jisestablished,0,otherwise.Objective functions:(5)minimizemaxdij,minimizemaxfij.Constraints:(6)∑jLij≤Nt,Lij=Lji,Lij≤Vij,fij=∑xijmn,xijmn=Tmn,Tij=ωi∗ωjdij.Constraint 7 limits the number of ISLs per satellite to no more than the number of antenna beams. Constraint 8 represents that links between satellites are bidirectional, i.e., if a link from satellitei to satellite j is established, both satellites can connect and communicate with the other. Constraint 9 is to ensure that an ISL can be established only when the two satellites are visible. Constraint 10 shows the calculation of potential traffic requirements between satellites. As it is associated with the link length and traffic density of the area where the endpoint satellites are located, we use the data of gridded world GDP [15] to estimate the economic state of different regions. As demonstrated in Figure 3, the world map is divided into 24×12 grids with a number from 1 to 10 each that represents the potential traffic demand density level of the area. Constraint 11 means that the carried traffic generated by satellite m and n that passes through link i,j is only determined by traffic requirements between source and destination. Constraint 12 gives the total carried traffic on link i,j.Figure 3
Estimation of world traffic density.


## 4. Solution Based on NSGA-II

### 4.1. Advantages of NSGA-II

In 2002, Deb et al. [16] proposed a nondominated sorting-based multiobjective evolutionary algorithm called NSGA-II. Compared to NSGA, NSGA-II has shown its unique advantage in the following three aspects:
(1)
NSGA-II uses a fast nondominated sorting method to reduce the computational complexity of the algorithm fromOMN3 to OMN2 (where M is the number of objectives and N is the population size), which makes it computationally cheaper for large population sizes(2)
The elite strategy is used to merge the parent individual and the offspring individual, and then, the nondominated sorting is carried out, which makes the search space larger. When generating the next generation of parent population, the individuals with higher priority are selected in order, and the crowding degree is used in the same level individuals to ensure that the excellent individuals can have a greater probability to be retained(3)
NSGA-II deprecates the concept of sharing that needs to specify the sharing radius and uses a crowded-comparison approach instead as a standard for selecting excellent individuals in the same level individuals, which ensures the diversity of individuals in the population and is conducive to individual selection, crossover, and mutation throughout the intervalIn existing works on link assignment, the weighted sum method was usually adopted to solve multiobjective optimization problems with low complexity. However, it is difficult to set the weight vectors to obtain a Pareto optimal solution in a desired region in the objective space, and it cannot find certain Pareto optimal solutions in the case of a nonconvex objective space. NSGA-II does not rely on any user-defined parameter for maintaining diversity among population members and gives better results for megaconstellations with a larger search space.


### 4.2. Problem Formulation

Although the optimization of all ISLs may contribute to better results, for the purpose of reducing algorithm complexity and improving link stability, we consider the intraplane ISLs unchanged during the optimization. Figure4 shows the flow chart of optimization process based on NSGA-II. Firstly, we initialize a set of random link assignments as a population and evaluate the fitness (rank) of every individual. Then, by randomly selecting a pair of best nondominated individuals as parents, the offspring population is generated using crossover or mutation operator. A more outperformed link assignment has a greater probability to be chosen. Parent population and offspring population are combined into a new one and sorted using fast nondominated sorting algorithm. Finally, repeat the above steps until the stop criterion is met and output the Pareto optimal front. Through taking XOR operation of the current link assignment matrix and the other one, the number of changed links can be calculated. Compared with the solution of previous state, the one with the fewest number of changed links will be selected.Figure 4
Flow chart of optimization process.In order to avoid the situation that the satellite network is disconnected due to randomly generated links, the network connectivity will be judged when calculating the objective functions. If not, the function value is set to infinity and will be automatically removed when filtering the population.


## 4.1. Advantages of NSGA-II

In 2002, Deb et al. [16] proposed a nondominated sorting-based multiobjective evolutionary algorithm called NSGA-II. Compared to NSGA, NSGA-II has shown its unique advantage in the following three aspects:
(1)
NSGA-II uses a fast nondominated sorting method to reduce the computational complexity of the algorithm fromOMN3 to OMN2 (where M is the number of objectives and N is the population size), which makes it computationally cheaper for large population sizes(2)
The elite strategy is used to merge the parent individual and the offspring individual, and then, the nondominated sorting is carried out, which makes the search space larger. When generating the next generation of parent population, the individuals with higher priority are selected in order, and the crowding degree is used in the same level individuals to ensure that the excellent individuals can have a greater probability to be retained(3)
NSGA-II deprecates the concept of sharing that needs to specify the sharing radius and uses a crowded-comparison approach instead as a standard for selecting excellent individuals in the same level individuals, which ensures the diversity of individuals in the population and is conducive to individual selection, crossover, and mutation throughout the intervalIn existing works on link assignment, the weighted sum method was usually adopted to solve multiobjective optimization problems with low complexity. However, it is difficult to set the weight vectors to obtain a Pareto optimal solution in a desired region in the objective space, and it cannot find certain Pareto optimal solutions in the case of a nonconvex objective space. NSGA-II does not rely on any user-defined parameter for maintaining diversity among population members and gives better results for megaconstellations with a larger search space.


## 4.2. Problem Formulation

Although the optimization of all ISLs may contribute to better results, for the purpose of reducing algorithm complexity and improving link stability, we consider the intraplane ISLs unchanged during the optimization. Figure4 shows the flow chart of optimization process based on NSGA-II. Firstly, we initialize a set of random link assignments as a population and evaluate the fitness (rank) of every individual. Then, by randomly selecting a pair of best nondominated individuals as parents, the offspring population is generated using crossover or mutation operator. A more outperformed link assignment has a greater probability to be chosen. Parent population and offspring population are combined into a new one and sorted using fast nondominated sorting algorithm. Finally, repeat the above steps until the stop criterion is met and output the Pareto optimal front. Through taking XOR operation of the current link assignment matrix and the other one, the number of changed links can be calculated. Compared with the solution of previous state, the one with the fewest number of changed links will be selected.Figure 4
Flow chart of optimization process.In order to avoid the situation that the satellite network is disconnected due to randomly generated links, the network connectivity will be judged when calculating the objective functions. If not, the function value is set to infinity and will be automatically removed when filtering the population.


## 5. Performance Analysis

### 5.1. Simulation Environment

We selected a LEO constellation with 20 satellites for simulation, and its detailed configurations are shown in Table1. In the simulation, our parameter setting is based on the most common Walker constellation pattern, and the orbit period guarantees that it operates on low earth orbit. The AGI System Tool Kit (STK) is used to calculate the latitude, longitude, and altitude position of all satellites in each state. As the ISL antenna beam is usually wide enough, the orbit drift can be ignored. The system period of the satellite network is 24 h, and we divide it into 288 equal-length states (for 5 minutes each) and compare the results.Table 1
Configurations of LEO satellite network for simulation.
ParameterValueNumber of satellites20Number of orbital plane4Number of satellites per orbital plane5Number of ISLs per satellite4Orbit period2 hConstellationWalkerIn the experiment, a regular link assignment and the simulated annealing (SA) algorithm-based link assignment proposed by [10] are adopted as benchmark schemes, and we also adopt the shortest path algorithm to calculate the routing.


### 5.2. Simulation Results

Figure5 illustrates the Pareto fronts at different number of iterations, and Figure 6 shows the value of each objective function. As the Pareto front at each iteration consists of a set of solutions, the average value is used to describe the overall trend. In Figure 6, both optimization objectives start from a larger value and gradually converge to a steady value. During the process of iteration, the value may rise because of newly created solutions that are not dominated by others but perform poorly on one of the objective functions. Both of them reach stability when the number of iterations exceeds 700. We set the maximum number of iterations at 1000 to ensure both solutions can converge. The Pareto front reaches a stable value in the fluctuation, which indicates that the diversity of the population can be guaranteed and local optimization can be avoided.Figure 5
Pareto fronts at different number of iterations.Figure 6
Value of objective functions at different number of iterations.
(a)
Value of maximum link traffic(b)
Value of maximum link lengthFigure7 shows the different structures of the topology generated by three methods. Satellites in the simulation are numbered 1 to 20 and divided into groups of five. For example, satellites No. 1 to No. 5 form a group and they are in the same orbital plane. The regular topology and the SA algorithm-based method ensure that each satellite has exact 4 ISLs. However, as NSGA-II introduces mutation operation when generating the offspring, and some satellites contain only 2 or 3 ISLs, but the link assignment results in a better balanced overall structure. SA algorithm-based topology also has satellites that do not establish links with their nearest neighbor in the same orbital plane, such as satellite No. 17; it neither connects with satellite No. 16 nor No. 18.Figure 7
Different topology generated by the three methods.
(a)
Regular(b)
SA algorithm(c)
NSGA-IIThe average link change comparison is shown in Table2. Compared to the link assignment scheme based on SA algorithm, our method only optimizes the two interplane ISLs and selects the most familiar solution relative to the previous state; thus, the results show that our method has lower average changed links and a more stable topology.Table 2
Comparison of average changed links in the system period.
Link assignment methodAverage link changesRegular0SA algorithm101.25NSGA-II43.67As for the two optimal objectives, it is shown in Figures8 and 9. Our method outperforms the regular link assignment in minimizing the maximum link traffic, while basically the same as the results of the method based on SA algorithm. Due to the optimization of link traffic, the regular topology has a lower maximum link length than the other two methods, in which our method shows better results at most of the time and has a more stable numerical trend in the whole system period. On the whole, our method shows its advantages on balancing optimal targets and saving onboard resources by avoiding massive link switches.Figure 8
Maximum link traffic at different FSA state.Figure 9
Maximum link length at different FSA state.


## 5.1. Simulation Environment

We selected a LEO constellation with 20 satellites for simulation, and its detailed configurations are shown in Table1. In the simulation, our parameter setting is based on the most common Walker constellation pattern, and the orbit period guarantees that it operates on low earth orbit. The AGI System Tool Kit (STK) is used to calculate the latitude, longitude, and altitude position of all satellites in each state. As the ISL antenna beam is usually wide enough, the orbit drift can be ignored. The system period of the satellite network is 24 h, and we divide it into 288 equal-length states (for 5 minutes each) and compare the results.Table 1
Configurations of LEO satellite network for simulation.
ParameterValueNumber of satellites20Number of orbital plane4Number of satellites per orbital plane5Number of ISLs per satellite4Orbit period2 hConstellationWalkerIn the experiment, a regular link assignment and the simulated annealing (SA) algorithm-based link assignment proposed by [10] are adopted as benchmark schemes, and we also adopt the shortest path algorithm to calculate the routing.


## 5.2. Simulation Results

Figure5 illustrates the Pareto fronts at different number of iterations, and Figure 6 shows the value of each objective function. As the Pareto front at each iteration consists of a set of solutions, the average value is used to describe the overall trend. In Figure 6, both optimization objectives start from a larger value and gradually converge to a steady value. During the process of iteration, the value may rise because of newly created solutions that are not dominated by others but perform poorly on one of the objective functions. Both of them reach stability when the number of iterations exceeds 700. We set the maximum number of iterations at 1000 to ensure both solutions can converge. The Pareto front reaches a stable value in the fluctuation, which indicates that the diversity of the population can be guaranteed and local optimization can be avoided.Figure 5
Pareto fronts at different number of iterations.Figure 6
Value of objective functions at different number of iterations.
(a)
Value of maximum link traffic(b)
Value of maximum link lengthFigure7 shows the different structures of the topology generated by three methods. Satellites in the simulation are numbered 1 to 20 and divided into groups of five. For example, satellites No. 1 to No. 5 form a group and they are in the same orbital plane. The regular topology and the SA algorithm-based method ensure that each satellite has exact 4 ISLs. However, as NSGA-II introduces mutation operation when generating the offspring, and some satellites contain only 2 or 3 ISLs, but the link assignment results in a better balanced overall structure. SA algorithm-based topology also has satellites that do not establish links with their nearest neighbor in the same orbital plane, such as satellite No. 17; it neither connects with satellite No. 16 nor No. 18.Figure 7
Different topology generated by the three methods.
(a)
Regular(b)
SA algorithm(c)
NSGA-IIThe average link change comparison is shown in Table2. Compared to the link assignment scheme based on SA algorithm, our method only optimizes the two interplane ISLs and selects the most familiar solution relative to the previous state; thus, the results show that our method has lower average changed links and a more stable topology.Table 2
Comparison of average changed links in the system period.
Link assignment methodAverage link changesRegular0SA algorithm101.25NSGA-II43.67As for the two optimal objectives, it is shown in Figures8 and 9. Our method outperforms the regular link assignment in minimizing the maximum link traffic, while basically the same as the results of the method based on SA algorithm. Due to the optimization of link traffic, the regular topology has a lower maximum link length than the other two methods, in which our method shows better results at most of the time and has a more stable numerical trend in the whole system period. On the whole, our method shows its advantages on balancing optimal targets and saving onboard resources by avoiding massive link switches.Figure 8
Maximum link traffic at different FSA state.Figure 9
Maximum link length at different FSA state.


## 6. Conclusions

In this paper, we have proposed a new link assignment scheme, which is suitable for megaconstellations. The idea of modified FSA was proposed to model the link assignment problem into a set of multiobjective optimization problems. The transmission delay and link capability were taken as the optimization targets, and as more satellites result in a larger search space, NSGA-II was used to accelerate convergence. By selecting the most appropriate solution from Pareto optimal front according to the determined link assignment of the previous state, the number of changed links is reduced, leading to a more stable network topology. The results may contribute to the design of link assignment in future construction of megaconstellations.In our further work, we plan to take emergency events into consideration, such as node failure and link congestion, and apply a more realistic simulation environment. We also plan to increase the number of objectives to be optimized and explore new optimization algorithms.



---

*Source: 5977121-2023-02-11.xml*