Satellite Constellation Design with Multi-Objective Genetic Algorithm for Regional Terrestrial Satellite Network

Cuiqin Dai＊, Guimin Zheng, Qianbin Chen

Chongqing Key Lab of Mobile Communication Technology, Chongqing University of Posts and Telecommunications,Chongqing 400065, China

* The corresponding author, email: daicq@cqupt.edu.cn

Abstract: Constellations design for regional terrestrial-satellite network can strengthen the coverage for incomplete terrestrial cellular network. In this paper, a regional satellite constellation design scheme with multiple feature points and multiple optimization indicators is proposed by comprehensively considering multi-objective optimization and genetic algorithm, and “the Belt and Road” model is presented in the way of dividing over 70 nations into three regular target areas. Following this,we formulate the optimization model and devise a multi-objective genetic algorithm suited for the regional area with the coverage rate under simulating, computing and determining.Meanwhile, the total number of satellites in the constellation is reduced by calculating the ratio of actual coverage of a single-orbit constellation and the area of targets. Moreover, the constellations’ performances of the proposed scheme are investigated with the connection of C++ and Satellite Tool Kit (STK). Simulation results show that the designed satellite constellations can achieve a good coverage of the target areas.

Keywords: regional terrestrial-satellite network; constellation design; multi-objective optimization; genetic algorithm; coverage performance

I. INTRODUCTION

In order to achieve ubiquitous 100% geographic coverage, satellite-based radio access is considered as an effective solution to supplement terrestrial cellular networks, and the terrestrial satellite communication network is introduced as a promising architecture in next generation networks [1-2]. Compared with MEO and GEO, LEO satellite constellation has many advantages of low emission cost,short propagation delay, and strong system survivability and can effectively complete a variety of tasks in a regional terrestrial-satellite network [3].

The satellite constellation contains a number of satellites with coordinated ground coverage, operating together under shared control,synchronized so that they overlap well in coverage [4]. The goal of constellation design is to generate a constellation using a set of parameters, and to achieve the integrated optimization of system performance and cost [5].There are several methods to design satellite constellation based on global coverage [6-10],including Walker Delta model [6], Polar orbit model [7] and Flower constellation model [8-9]. However, the global coverage constellation can only achieve basic communication needs.Different from global coverage, the regional coverage constellation may provide better coverage and higher reliability, ensuring a higher rate of mission success [10-11]. The basic constellation models for regional satellite constellation design is comparatively studied in [10],and a small satellite constellation is designed for Antarctica’s communications in [11].

Satellite constellation optimization design for a given space mission is a complex multi-parametric optimization process. The traditional method of satellite constellation optimization design is to combine the geometry structure of the constellation with the coverage simulated in STK [12]. However, traditional analytical method is not conducive tofind the optimal solution since the objective in constellation design is not unique, nonlinear, and discontinuous [10]. In [13], a multi-objective optimization study is conducted with a genetic algorithm due to its ability to locate a global optimum solution for nonlinear multi-objective problems. The authors in [14] proposed a new non-dominated sorting genetic algorithm to maximize the system performance by solving the formulated multi-objective optimization problem under practical constraints.In [15], the coverage of the north Algerian seismological network is taken as an example of application, a multi objective genetic algorithm is used to make a trade-off between the improvement of the coverage rate, the minimization of the total number of satellites and the reduction of the satellites’ altitude.The authors in [16] define three feature points in the region of China as the target points and three typical constellation schemes are selected to achieve the coverage of the three feature points using multi-objective algorithm. However, to the best of our knowledge, there is no specific unified design approach for a local continuous coverage or surveillance mission over a region.

In this paper, we propose a method of satellite constellation design to realize the coverage of “the Belt and Road” area. Firstly, we construct a regional terrestrial-satellite network model by analyzing the edge of the latitude and longitude of over 70 nations to three coverage areas. Then, an optimized constellation design scheme with genetic algorithm is given by considering the multi-objective problem.Pareto optimal sets are employed to deal with the conflicts due to the presence of multiple cost functions such as the coverage area, the minimum instantaneous coverage, and the total number of satellites. At the same time,the total number of satellites is reduced by comparing the coverage size of the single-orbit constellation to the target areas’. Finally,we simulate the coverage of the defined three target in the STK as well as the multiplicity coverage with n satellites. The results show that the constellations we designed have good performance of “the Belt and Road” area.

The remainder of this paper is organized as follows. Section II presents the regional coverage constellation model. Section III proposes a method to optimize the orbit number as well as the design of the constellation parameters.Section IV details the multi-objective optimization of the constellation design using genetic method. Simulation results about the optimized constellation are given in Section V.The conclusion is drawn in Section VI.

II. REGIONAL COVERAGE CONSTELLATION MODEL

2.1 Regional terrestrial-satellite network

The satellite network can make up for the incomplete coverage of the terrestrial network and enhance the system connectivity. On the one hand, the terrestrial networks provide high quality service for populations in urban areas,while on the other satellite constellations can help to establish connections for low-density populations in suburban or far from the land.Moreover, people spend a large amount of time in vehicles on roads after homes and offi ces [17], the access of satellite make communications smarter for people.

As shown in figure 1, the terrestrial-satellite network consists of several LEO satellite nodes in space segment and some ground stations in ground segment. Users close to a ground station can be directly connected with each other, while users in suburban or ocean connected to any ground station can communicate with satellite constellations. At the same time, when users are far apart, communications can be relayed through satellites.

We study the regional coverage area of China and other 74 countries that signed “the Belt and Road” cooperation documents with China[18]. Among the 74 countries, Egypt, Ethiopia and South Africa belong to Africa, New Zealand belongs to Oceania, while the other countries belong to the Asian region. Table 1 lists the latitude and longitude ranges of the marginal zones within the 74 countries.

The area of “the Belt and Road” is irregular which is not conducive to simulating the coverage of the constellation. In order to simplify the coverage geometry, the area is divided into three targets by its location as it is illustrated in figure 2. Target 1 (T1) is represented by solid polygon which contains over 70 countries of the terrestrial-satellite network, table 2 contains the geographical coordinates of the 4 positions surrounding this area. Target 2 (T2) is the land area of South Africa, and Target 3 (T3) is the New Zealand land area. In addition, due to the large latitude span and the high latitude of Russia, T1 does not contain the complete Russian territory. The coverage of Russia will be considered as a constraint of the selection of the constellation.

2.2 Satellite geometric model

Construction of LEO satellite system is intended to provide a good service to the target area.The premise of providing services is to cover the target area, and the situation of a single satellite coverage is shown in figure 3. Wherein R is the radius of the Earth, h is the satellite orbit altitude, θ is the geocentric angle, φ is the satellite viewing angle, γ is the minimum elevation that is essential to establish a communication link between the satellite and the ground user.

Table I. Longitude and latitude of marginal countries.

Table II. Positions of the terrestrial limits of Target 1 to be covered.

Fig. 1. Terrestrial-satellite network.

Fig. 2. Geographical delimitation of the coverage of “the Belt and Road” terrestrial-satellite network.

Fig. 3. Satellite geometric mode.

The formulas to calculate θ and φ are:

According to geocentric angle, the number of orbit is calculated as:

where the earth radius R=6378.14km , and the Kepler’s constant k=398601.58k m3/s2.

The relationship between satellite operation cycle Tsatand the earth rotation cycle Tnis shown in equation (5):

of which m=1,2,3... for the regression cycle, n is the number of regression cycles.

In general, the minimum number of satellites needed to achieve full coverage of the target area:

Where S is the entire area size due to the target area, and A is the size of a single satellite according to equation (7):

III. SELECTION OF CONSTELLATION PARAMETERS

Constellation is composed of some satellites to complete a specific task. Satellite’s position consists of six orbit parameters: semimajor axis a, inclination i, longitude of ascending node (RAAN) ? , argument of perigee ω,mean anomaly M, and eccentricity e. Wherein, the orbital semi-major axis a and eccentricity e determine the orbital shape, inclination i and RAAN determine the location of orbital plane, argument of perigee determine the semi-major axis direction, mean anomaly determines the satellite’s position with respect to time.

In LEO satellite constellation, satellite orbit altitude and elevation between satellite and terrestrial users affect system performance. The altitude of LEO constellation is selected based on analyzing space radiation environment. It is ruled that the altitudes of LEO satellites are 500～2000km. When the altitude of satellites is below 700km, the life of satellites is short due to the erosive attack of atmosphere drag and oxygen atoms on satellites [12]. In addition,to avoid the inner radiation belt of Van Allen radiation belt ranges between 1500km and 5000km, the altitude of LEO constellation is selected between 700～1500km.

The relationship between the altitude, the regression cycle and the number of regression period can be determined by the equation (4)and (5), as shown in table 3.

According to equation (7), the coverage of a single satellite is linearly related to the altitude. Since the definite regression period is beneficial for monitoring and simulation, the orbit altitude at 1248km with a return period of a day is selected.

In order to effectively overcome the impact of multipath effects and shadow effects, and to ensure the system to provide users with excellent communication services, the elevation angle between satellite and terrestrial users requires at least 10 degrees. Since this paper considers the circular orbit, the value of eccentricity is zero and the argument of perigee ω is also zero.

The area of the three target areas can be calculated in the STK: ST1=8.81543× 107km2,According to equation (1) ～ (3), the number of orbit is 4. There are 8 satellites in each orbit based on equation (6) and (7).

Assuming there is only one satellite in each orbit that can cover the target area, the minimum orbit number equals to the minimum number of satellites that can achieve the full coverage of the target area. The size of constellation is optimized based on the average coverage of a single-orbit constellation.

The optimized orbit number is:

The coverage of the single-orbit constellation is calculated in STK with the determined parameters. The relationship between average coverage and the inclination of the single-orbit constellation is shown in figure 4.

Due to the high latitude range of Target 3,the coverage of the single-orbit constellation to the target area cannot be achieved when the inclination angle is between 0 to 20 degrees.Therefore, the range of inclination angle is selected between 20 to 80 degrees. Within the range of 20 to 80 degrees of the inclination,the average coverage of a single-orbit constellation can reach to 47.1%. According to Equation (8), the optimized number of orbit is three. The total number of satellites reduces to 24 with the decreasing of one orbital. Compared with the traditional method, the proposed method can reduce the number of orbits as well as the total number of the satellites,which reduce launch and maintenance costs.

IV. CONSTELLATION DESIGN USING MULTI OBJECTIVE GENETIC ALGORITHM

The optimization process is based on the use of genetic algorithms. The genetic algorithm is chosen because the gradient of the objective function cannot be defined and the trend of the objective function is very complex. The evolution towards the optimal solution starts from a population of randomly generated individuals.Multi-objective genetic algorithm is a variation of genetic algorithm, which is known to be a robust technique to solve multi-objective optimization, resulting in a Pareto optimal set solution [5].

4.1 Nondominated sorting genetic algorithm

A class of fast and elite multi-objective genetic algorithm was introduced by Deb et al. in 2002 [19]. This new multi-objective genetic algorithm called NSGA-II stands for nondominated sorting genetic algorithm, which uses a fast nondominated sorting and a crowding distance assignment in its algorithm as shown in figure 5.

In thefirst generation, parent population Ptof I individuals creates an offspring population Qtalso in I individuals through the common tournament Selection, Crossover, and Mutation operators. Next, population Rtwith a size of 2I individuals goes through a nondominated sorting. After the first generation, crowded tournament selection is used to select the top I individuals from Rtto form the next generation Pt+1. A solution that wins a tournament has either the highest rank or a better crowding distance parameter. The crowding distance parameter itself is defined as the largest cuboid surrounding a solution.

Fig. 4. The average coverage of the single-orbit constellation.

Table III. The relationship between the altitude and the regression cycle.

4.2 Definition of the optimization problem

Fig. 5. NSGA-II scheme.

Fig. 6. Constellation design process.

The design of a communication system starts with the definition of the user requirements for a given type of communication service.

The percent coverage for any point on the grid is described as the number of points covered, which is divided by the total number of points in the grid. The percent of coverage directly shows the effectiveness of satellite coverage. While the visibility of one satellite is the minimum requirement, the simultaneous visibility of a certain number of satellites which called the multiplicity of satellites can be useful for telecommunications services if satellite diversity is used to improve the performance when the conditions of the communication channel are not good or if a mobile user is located in urban areas where the probability that a satellite is shadowed is high.

The optimization problems are defined as:

1. Maximum area percent coverage

2. Maximization the average multiplicity of satellites

Where k presents the total grid number of the area, L present the sample instants, N present the total number of satellites. The coverage ci,jis evaluated for the i th grid point at the j th sample instant as well as cnpresent the multiplicity coverage with n satellites.

The minimum instantaneous coverage of the constellation is also considered as a constraint of the optimization. Since we define three targets of the area, the number of optimization is three times of the optimization function.

4.3 Constellation optimization design based on multi-objective genetic algorithm

Regional coverage includes multiple target points and multiple objective functions, which is a typical multi-objective optimization problem. The process of the optimization design is shown in figure 6 as following steps:

Step 1 Determine the basic parameters of the MOGA such as the mutation and crossover probability, the population and generation size.Design chromosome structure according to the relationship between the satellites in the same orbit. The constrains are also limited to ensure the communication of the constellation.

Step 2 Make a judgment whether the corresponding constellation for each chromosome has at least one satellite in every orbit to cover the target area. Mark the chromosome structure with the value of 0 or 1 which represent yes or no.

Step 3 The constellation of each chromosome is generated in STK. The performances of the constellation are then evaluated by each STK simulation module. Return the parameters as the value of objective functions to calculate the crowding distance and the rank of each individual.

Step 4 Genetic manipulation of selection,crossover and mutation on each generation of chromosomes. The new generation of chromosomes is returned to Step 2.

A tag value is added to calculate the constellation of each track whether there is a satellite can cover the target area. If the orbital exists any satellite to achieve the coverage, the chromosome is invalid. Instead of compute the performance in STK, mutation and crossover the chromosome directly. We can achieve the prediction of the performance of the constellation in the way of initial judgment, which ensure the evolutionary direction and speed up the convergence.

For satellite constellation design, each chromosome represents a constellation model and the parameters to be optimized are the constellation parameters the inclination angle i, the right ascension of the ascending node(RAAN)? and mean anomaly M. For the other orbital parameters, according to the selection of constellation parameters in Part-III, the altitude of LEO constellation h=1248k m , orbital eccentricity e=0 and the argument of perigee ω=0.

The parameters of an individual to be optimized are represented by a structure called chromosome and a binary coding is adopted here. Assuming that the number of orbits is m and the number of satellites in each orbit is n,then a constellation of a set of orbital parameters can be expressed as:

According to Walker constellation theory,? and M are uniformly distributed for all the constellation. Therefore, the chromosome structure is reduced to

The position of the satellite Smnis expressed as:

Table IV. Basic parameters of constellation and algorithm.

Fig. 7. Distribution of Pareto optimal results of LEO constellation.

Here, the range of ?0and Mm0is [0,??]and [0,?M].

V. SIMULATION RESULTS AND DISCUSSION

Fig. 8. The maximization of minimum instantaneous coverage of the four schemes.

Fig. 9. The coverage of two methods.

In this paper, constellation design process simulation is conducted by interconnecting the C++ and STK. Wefirstly discussed the distribution of Pareto optimal results of LEO constellation. Four representative constellations are then selected from the solution set. In order to illustrate that the selected constellations can achieve better coverage performance, we compare the proposed scheme with the original schemes in [16].

The target region for the Belt and Road area, with 74 countries’ latitude and longitude positions, is used as an input for simulation.The area of interest is divided into three target areas with T1 itself represented as a polygon of boundary points that includes over the 70 countries while T2 and T3 represent South Africa and New Zealand. The three polygons are then divided into a number of grid points with the point granularity of three degrees. The basic parameters are as shown in table 4.

The orbit inclination angle is usually chosen close to the maximum latitude of the area to be covered which is bounded by the limits presented in table 2. Hence, the constraints on the inclination angle i is

The population size is 20, after 100 generations of evolution, the algorithm tends to be stable. A set of Pareto optimal solutions for the low orbit satellite constellation is obtained as shown in figure 7, from which the distribution of pareto optimal solutions is relatively uniform, and the NSGA-II algorithm based on tournament selection has achieved good results.

Considering the optimization functions of three targets, the scheme we put forward in Part IV is executed to find the pareto sets of the constellations. The coverage module in the STK is used to get the corresponding coverage performance index, and the return value is taken as the algorithm. Four representative constellation parameters are selected from the solution set, as shown in table 5. The average multiplicity coverage of the constellation can be as high as 3.2 satellites, which is higher than that of the traditional GEO constellations with three satellites. Figure 8 shows the maximization of the minimum instantaneous coverage of the schemes for the three target areas in each time step.

Table V. Orbital parameters and coverage property of four typical constellation scheme.

Combining table 5 and figure 8, schemes 1～3 have the same maximum area percent coverage of three targets. While scheme 2 has the maximum average multiplicity of China,scheme 3 has the better instantaneous coverage. Scheme 4 is better at both the percent coverage and the average multiplicity, but slightly worse in the property of instantaneous coverage comparing with scheme 2 and 3.

As shown in figure 9, the original schemes 1～3 represent the scheme proposed in [16],the other four schemes are the typical constellation in this paper. Compared to the solution proposed in [16], the coverage property of our scheme is better than [16]. Since [16] selects three points within the region of China as the target, the considered coverage area is signi ficantly small. The coverage of all four schemes is higher than the coverage of the three proposed solutions.

VI. CONCLUSION

Based on the regional terrestrial-satellite network, we proposed a scheme to optimize the parameters in satellite constellation which can maximize the coverage of target areas, the multiplicity coverage with n satellites, and minimize the total number of satellite at the same time. Wefirst define a regional constellation model of “the Belt and Road” area by simplifying over 70 countries into 3 regular areas. According to the average coverage of a single-orbit constellation, the orbit number is reduced as well as the total number of satellites, which reduce the costs of launch and maintenance. The genetic algorithm is used to solve the multi-objective problem with the chromosome length simplified and a Tag Value introduced to make an initial judgment of the coverage to target areas. With the combination of C++ and STK, four typical constellation schemes are selected which can achieve good coverage to “the Belt and Road” target area.

ACKNOWLEDGEMENT

This work was jointly supported by the National Natural Science Foundation in China(No.61601075), the Natural Science Foundation Project of CQ CSTC (No.cstc2016jcyjA0174).