Abstract: In order to achieve real-time selection of navigation satellites in multi-constellations navigation system, a novel satellite selection method named Genetic Satellite Selection Method (GSSM) is proposed. Combined with the basic idea of genetic algorithm and the feature of multi-constellations navigation system, a fast crossover operator and mutation operation is described. The experiment results show that, in the satellites selection process, the GSSM can effectively reduce 98.9% computation comparing to the traditional optimal Geometric Dilution of Precision (GDOP) method. From the view of the overall navigation system, it can also reduce almost 73% computation.
INTRODUCTION
In recent years, satellite navigation system has been playing an increasing role in various areas of the society. From now on, more than 100 navigation satellites work in the space, coming from GPS, GLONASS, Galileo and COMPASS. For the better positioning accuracy and system reliability, the multi-constellations navigation has become a hot issue. But on the other hand, the computation of navigation system will sharply increased with more satellites. In most case, the traditional satellites selection method can’t meet the real-time requirement in the multi-constellations navigation system, especially for the high dynamic environment (Zhang et al., 2000; Li et al., 2007; Zhang et al., 2007; Jin et al., 2009).
This study propose a novel satellite selection method based on genetic algorithm, including the visible satellites selection method, a fast crossover and mutation design which will effectively reduce the computation of navigation system to meet the real-time requirement in the multi-constellations environment.
GENETIC SATELLITE SELECTION METHOD
Mathematical description of satellite selection: In satellite navigation system, the purpose of satellite selection is to select the optimum subset of satellites which can provide the best navigation result. The mathematical description is under below:
| • | n∈N, m∈N and n>m |
| • | ∃Xk = [xn xn-1…x1], xj = 1 or 0, j = 1,…, n: meeting |
| • | to find X0∈{Xk}, meeting GDOP(X0) = min{GDOP(Xk)≤GDOPT} |
where, n is the number of visible satellites; m is the number of selected satellites; k is the number of m-satellite subset; Xk is the selected satellites scenario; GDOP(Xk) is GDOP of Xk; X0 is the selected satellite solution GDOPT; is the GDOP threshold which meets positioning accuracy requirement.
Coding scheme: Satellite selection scenario uses binary encoding. Each visible satellite is treated as a gene and is assigned a binary value ‘1’ or ‘0’. ‘1’ of Xk = [xn…xj…x1] indicates that the corresponding satellite is selected.
Fitness function: The objective function of satellite selection (Eq. 1):
| (1) |
where, X represents the scheme of satellite selection.
The fitness function in GSSM is as follows (Eq. 2):
| (2) |
where, GDOPmax and GDOPmin denote the maximum and minimum of GDOP of current population, respectively, ε is a constant, ε∈(0,1).
Crossover operators: According to the characteristics of satellite selection, the number of selected satellites should be the constant. A new crossover operator named One Matched Crossover (OMX) is proposed. Under the constraint, it will ensure that all of the crossover offspring will not out of the range of parent and it can also guarantee that the satellites with better GDOP will not be eliminated.
We suppose m is the numbers of selected satellites. The steps of OMX can be described as follows:
| Step 1: | Two individuals (parents) are randomly selected with a probability pc, called the crossover probability. And then randomly generating an integer of 1~(m-1), the integer represents the numbers which will be used to cross those selected satellites. That means the selected satellites whose serial number is lower will be utilized in crossover operator |
| Step 2: | Produce original offspring by interchanging the badge of selected satellites of parents |
| Step 3: | Ascertain the mapping relationship of interchanged satellites |
| Step 4: | Legalize offspring based on the mapping relationship |
A specific example of OMX is demonstrated below. Assuming there are 16 visible satellites and 8 satellites need to be selected.
| • | Select two individuals randomly |
| Parent 1: | 0111100101110000, the serial number of selected satellites is: 15, 14, 13, 12, 9, 7, 6, 5 |
| Parent 2: | 0001100101011110, the serial number of selected satellites is: 13, 12, 9, 7, 5, 4, 3, 2 |
The integer 6 has been generated randomly.
| • | Produce original offspring by interchanging the latter 6 selected satellites |
| Child 1: | 0110000101011110, the serial number of selected satellites is: 15, 14, 9, 7, 5, 4, 3, 2 |
| Child 2: | 0001100101110000, the serial number of selected satellites is: 13, 12, 9, 7, 6, 5 |
| • | Ascertain the mapping relationship: |
| • | Legalize the offspring based on the mapping relationship |
From the above, we can know the satellite 13 and 12 of Parent 2 should be replaced with satellite 2 and 4, respectively and the exchanged satellites will be maintained. Then two legal offspring (feasible solutions) are reconstructed as follows:
| Child 1: | 0110000101011110, the serial number of selected satellites is: 15, 14, 9, 7, 5, 4, 3, 2 |
| Child 2: | 0001100101111010, the serial number of selected satellites is: 13, 12, 9, 7, 6, 5, 4, 2 |
Mutation operator: Simile to the crossover operator, mutation operator also has to guarantee that the number of selected satellites of individual has exactly the same quantity in satellite selection. According to the requirement, a kind of new mode, dual genes ‘01’ relative mutation, is proposed in GSSM.
Assuming the number of visible satellites is n, the detailed operating steps of this mutation operator are as follows:
| Step 1: | An individual Cp is selected randomly with a certain probability pm known as the mutation probability |
| Step 2: | A random integer g1 is generated with 1~n interval |
| Step 3: | Judge the type of the g1th gene of individual Cp. If the g1th gene is 0, another integer g2 (g2≠g1) is generated randomly with 1~n interval and it ought to ensure that the g2th gene of individual Cp is 1. Otherwise, if the g1th gene is 1, the corresponding gene of integer g2 should be 0 |
| Step 4: | Change the g1th and g2th genes of individual Cp (a 0 is converted to 1 and vice versa) |
| Fig. 1: | Flowchart of GSSM |
Selection strategy: The population size in satellite selection is smaller and the preferable constellations ought not to be eliminated. So, a lager sample space is employed in GSSM. It can ensure that parents and offspring have the same competition chance. The roulette wheel selection is utilized to obtain the new crossover and mutation population. The selection strategy can improve the performance of genetic algorithm by increasing crossover probability and mutation probability and selection will not cause too much random variation by high crossover probability and mutation probability.
Termination principle of GSSM: The computational process will be terminated when the GDOP of the individual meets the constraint min GDOP(Xk)}≤GDOPT. Furthermore, in order to ensure the efficiency of iterative operation, a maximum evolutional generation is also defined.
Figure 1 shows the flowchart of GSSM.
EXPERIMENT RESULTS
Basing on the compatible GPS/COMPASS receiver platform, we implement the semi-physical simulation of the method proposed in this paper. The satellite data is generated from the navigation signal source which contains 32 GPS satellites and 12 COMPASS satellites. The navigation receiver is implemented on the FPGA and DSP.
Performance analysis of GSSM under different GDOPT: GDOPT decides the accuracy of navigation system. In order to meet the availability requirement of the satellite navigation system, Position Dilution of Precision (PDOP) should not be more than 6 (Kaplan and Hegarty, 2007). We analyze the performance of GSSM under different GDOPT (2.5, 3, 3.5, 4, 4.5, 5, 5.5 and 6). The number of selected satellites is taken as 8 to meet the system fault detection.
According to RTCA D0-2229D standard, the mask angle is assumed to be 5°. Simulation time is 24 h. The sampling interval is 5s. Based on twenty-seven stations of Crustal Moment Observation Network of China, we do the simulation of OMX under the GPS and COMPASS dual-constellation navigation system.
Analysis of validity: Figure 2-5 shows the temporal variation of GDOP and GDOPT within 24 h in SUIY, TASH, YONG and XIAA station after satellite selection under GDOPT 2.5, 3, 4 and 6. Table 1 is a statistical analysis of GDOP
From Fig. 2-5 and Table 1, the following conclusions can be drawn:
| • | The |
| • | The temporal variation of GDOP after satellite selection is smooth for the four observatories station |
| • | The probability of GDOP after satellite selection less than GDOPT increased with the increase of GDOPT. When GDOPT is between 2.5 and 4, almost all case (96.99%) is meet GDOP requirement. When GDOPT is between 4 and 6, no case is failed |
Analysis of computation complexity of satellite selection: Figure 6-9 shows the temporal variation of evolution algebra Ng for satellite selection within 24 h in SUIY, TASH, YONG and XIAA station with different GDOPT. Table 2 is a statistical analysis of Ng.
From Fig. 6-9 and Table 2, the following conclusions can be drawn:
| • | The Ng of satellite selection decreases with the increase of GDOPT |
| • | When GDOPT = 6, only one evolution is needed to finish satellite selection |
| • | When GDOPT = 4, 98% satellite selection can be finished within 3 evolutions at most |
| • | When GDOPT = 3, 98% satellite selection can be finished within 6 evolutions and 95% satellite selection can be finish within 2 evolutions |
| • | When GDOPT = 2.5, most satellite selection needs much more evolutions |
| Fig. 2(a-d): | GDOP and GDOPT after satellite selection (GDOPT = 2.5). (a) SUIY, (b) TASH, (c) XIAA and (d) YONG |
| Table 1: | GDOP Statistics after satellite selection under different GDOPT |
Analysis of computation complexity of overall navigation: In satellite navigation system, the observation equation is (Eq. 3):
| (3) |
where,
| (4) |
| Fig. 3(a-d): | GDOP and GDOPT after satellite selection (GDOPT = 3). (a) SUIY, (b) TASH, (c) XIAA and (d) YONG |
| Table 2: | Ng Statistics of satellite selection under different GDOPT |
| Remark: Ng0.95 is a minimum evolution algebra which meeting p(GDOP≤GDOPT). ≥0.95 Ng0.98 is a minimum evolution algebra which meeting p(GDOP≥GDOPT) ≥0.98 | |
| Table 3: | Amount of computation to position statistics |
Equation 4 is the least squares method. There is five-dimensional state variables, for dual constellation integrated navigation system, Isys = 5. The average number of visible satellites approximately equal to 19. The number of selected satellites is taken as 8. Table 3 give the amount of calculation of the least square estimation algorithm (number of iterations is assumed for 50 times). We can conclude that the amount of addition decreases 72.3% and the amount of multiplication decreases 71.4%.
Performance compared with GSSM and optimal GDOP method: The purpose of the optimal GDOP method of satellite selection is to find the subset with minimal GDOP in all satellite subsets.
| Fig. 4(a-d): | GDOP and GDOPT after satellite selection (GDOPT = 4). (a) SUIY, (b) TASH, (c) XIAA and (d) YONG |
| Table 4: | GDOP Statistics after satellite selection |
GSSM cares about the final positioning accuracy instead of the GDOP which will reduce the complexity of computation. Therefore, when comparing these two methods, we should focus on the complexity under the same discrepancy of GDOP after satellite selection. In the comparative analysis, the number of selected satellites is taken as 5. And GDOPT is taken as 6; the number of selected satellites is taken as 8.
Comparison of GDOP after satellite selection: Figure 10 shows the temporal variation of GDOP after satellite selection in GSSM and GDOP with the optimal GDOP method. Table 4 is a statistical analysis of GDOP. The following conclusions can be drawn:
| • | The |
| • | The GDOP after satellite selection with the GSSM were less than the optimal GDOP method which probability not less than 77.4% |
Comparison of Computation for satellite selection: Table 5 shows the statistical analysis of NGDOP which is the number of calculations of GDOP for satellite selection. The following conclusions can be drawn:
| • | The NGDOP for satellite selection with the GSSM were less than the minimum NGDOP for satellite selection with the optimal GDOP method 98.90, 98.90, 98.90 and 99.27%, respectively for the four observatories station |
| • | The average value of NGDOP for satellite selection with the GSSM were less than the optimal GDOP method 99.93, 99.89, 99.93 and 99.95%, respectively for the four observatories station |
| Fig. 5(a-d): | GDOP and GDOPT after satellite selection (GDOPT = 6). (a) SUIY, (b) TASH, (c) XIAA and (d) YONG |
| Fig. 6(a-d): | Ng after satellite selection (GDOPT = 2.5). (a) SUIY, (b) TASH, (c) XIAA and (d) YONG |
| Fig. 7(a-d): | Ng after satellite selection (GDOPT = 3). (a) SUIY, (b) TASH, (c) XIAA and (d) YONG |
| Table 5: | Statistics of NGDOP in the two kinds of method |
| Fig. 8(a-d): | Ng after satellite selection (GDOPT = 4). (a) SUIY, (b) TASH, (c) XIAA and (d) YONG |
| Fig. 9(a-d): | Ng after satellite selection (GDOPT = 6). (a) SUIY, (b) TASH, (c) XIAA and (d) YONG |
| Fig. 10(a-d): | GDOP after satellite selection by utilizing two kinds of method and their difference. (a) SUIY, (b) TASH, (c) XIAA and (d) YONG |
CONCLUSION
To reduce the computation of satellites selection, a novel satellite selection method, named Genetic Satellite Selection Method, is proposed based on genetic algorithm in the paper. With the help of the fast coding scheme and fitness function process, it can effectively accelerate the satellite selection under the GPS/COMPASS multi constellation navigation system. Our experiment result shows the GSSM is not only improving the real-time performance of navigation system, but also still meeting the accuracy of locating requirement.