Research on satellite selection algorithm in ship positioning based on both geometry and geometric dilution of precision contribution

Abstract

With the networking of four Global Navigation Satellite Systems, the combination of multi-constellation applications has become an inevitable trend, and there will be more and more visible satellites that can be participated in ship positioning. However, the computational complexity increases sharply, which greatly improves the load capacity of the receiver’s data processor and reduces the output frequency of the positioning result. To achieve the balance between positioning accuracy and computational complexity, a new fast satellite selection algorithm based on both of geometry and geometric dilution of precision contribution is proposed. Firstly, this article analyzes the geometry characteristics of the least visible satellites has minimum geometric dilution of precision that meet the positioning requirements and makes clear the layout of their elevation angles and azimuth angles. In addition, it derives the relationship of geometric dilution of precision and the visible satellites layout and gets geometric dilution of precision contribution of each satellite. Finally, based on the observation data of JFNG tracking station of the Multi-Global Navigation Satellite System (GNSS) Experiment trial network, the positioning error and the elapsed time of GPS/Beidou Satellite Navigation System and GPS/Beidou Satellite Navigation System/Russian Global Orbiting Navigation Satellite System (GLOANSS) are compared. Simulation results show that the algorithm solves the problem that there are a lot of matrix multiplications and matrix inversions in the traditional satellite selection algorithm, and the new algorithm can reduce computational complexity and increase receiver processing speed.

Keywords

GNSS geometry GDOP contribution satellite selection BDS ship positioning

Introduction

When ships are sailing at sea, precise navigation and positioning not only determine the navigation efficiency of the ships but also the safety of the ships. The four Global Navigation Satellite Systems (GNSSs) that are currently on-orbit operation include the American GPS, the Russian GLONASS, the European Galileo system, and the Chinese Beidou Satellite Navigation System (BDS).¹ With the networking of four GNSSs, the number of navigation satellites in space has been increasing, over 100 satellites will circumnavigate the earth in the future. The number of visible satellites will increase while positioning with combination of multi-GNSS, which greatly improves the load capacity of the receiver’s data processor and reduces the output frequency of the positioning result, thus the issue of satellite selection is particularly important. Generally, the satellite selection algorithm is to select the fixed number of satellites whose constellation layout is better according to the Geometric Dilution of Precision (GDOP) in positioning calculation. Scholars at home and abroad have made a lot of research on the method of rapidly calculating GDOP and satellite selection algorithm in the multi-GNSS positioning. One general method is deduced from the positioning equations, which is obtained by performing a series of matrix operations on the observation matrix. The precision of this closed-form calculation is high, but the computational burden increases significantly with the number of visible satellites.^2,3 In recent years, machine learning methods such as genetic algorithm and support vector machine algorithm are used to solve GDOP calculation problems,^4
–6 but they all have a common problem, that is, parameter selection problem. When the parameters are chosen properly, a good result can be obtained. All of these parameters are inputs based on experience, but there is not a very proper solution to this problem. At present, there are some mature methods of satellite selection, such as the best GDOP method, the maximum tetrahedron volume method, and the maximum orthogonal projection method.^7
–9 How to balance the contradiction between computation and calculation accuracy is still a research hot spot. Firstly, this article summarizes the distribution of elevation angles and azimuth angles of the best geometry based on the geometry characteristics of the best visible satellites combination. Then, considering the contribution of each visible satellite to GDOP, a fast satellite selection algorithm based on geometry and GDOP contribution is proposed. Finally, the algorithm is simulated and analyzed with the actual measured data of Jiufeng Tracking station of Wuhan Province of China (JFNG) tracking station of the Multi-GNSS Experiment (MGEX) trial network.

Relationship between GDOP and geometry for multi-GNSSs

For GNSS, the accuracy of the user’s position obtained by the receiver depends on the geometry of visible satellites and the pseudo-range error. Where the geometry of that is reflected by GDOP, and the smaller the value, the higher the positioning accuracy. After the time-space coordinates are unified, the GDOP of multi-GNSSs and its observation matrix H can be expressed as¹⁰

GDOP = \sqrt{trace {({H_{n}}^{T} H_{n})}^{- 1}}

Supposing that n_i is the visible satellites number of the ith system, and the total number of visible satellites in the multi-GNSSs is

n = n_{GPS} + n_{GLONASS} + n_{GAL} + n_{BDS}

H_n is an n × 7 dimensional matrix, and H_i represents the first three columns of the observation matrix of the ith system, where $i = GPS, GLONASS, GAL, BDS$ , thus

H_{n} = [\begin{matrix} H_{GPS} & 1_{GPS} & 0_{GPS} & 0_{GPS} & 0_{GPS} \\ H_{GLO} & 0_{GLO} & 1_{GLO} & 0_{GLO} & 0_{GLO} \\ H_{GAL} & 0_{GAL} & 0_{GAL} & 1_{GAL} & 0_{GAL} \\ H_{BDS} & 0_{BDS} & 0_{BDS} & 0_{BDS} & 1_{BDS} \end{matrix}]

where subscripts GPS, GLONASS, Galileo System (GAL), and BDS represents GPS, GLONASS, Galileo system, and BDS. In the last four columns of H_n, 1 _i and 0 _i are respectively the i-dimensional column vectors, which are used to solve four different system clock differences

[\begin{matrix} H_{i} & 1_{i} \end{matrix}] = [\begin{matrix} a_{x 1} & a_{y 1} & a_{z 1} & 1 \\ a_{x 2} & a_{y 2} & a_{z 2} & 1 \\ a_{x 3} & a_{y 3} & a_{z 3} & 1 \\ a_{x 4} & a_{y 4} & a_{z 4} & 1 \end{matrix}]

where a_xi, a_yi, and a_zi are related to the elevation and azimuth angle of the visible satellite.

Assuming that position of the ith visible satellite in East–North–Up (ENU) coordinate system is $(x_{L i}, y_{L i}, z_{L i})$ , then the elevation angle $E L_{i}$ and the azimuth angle A_i can be expressed as follows

E L_{i} = {tan}^{- 1} (\frac{z_{L i}}{\sqrt{x_{L i}^{2} + y_{L i}^{2}}})

A_{i} = {tan}^{- 1} (\frac{x_{L i}}{y_{L i}})

The matrix in equation (4) can be rewritten as

[\begin{matrix} H_{i} 1_{i} \end{matrix}] = [\begin{matrix} cos E L_{1} sin A_{1} & cos E L_{1} cos A_{1} & cos E L_{1} & 1 \\ cos E L_{2} sin A_{2} & cos E L_{2} cos A_{2} & cos E L_{2} & 1 \\ cos E L_{3} sin A_{3} & cos E L_{3} cos A_{3} & cos E L_{3} & 1 \\ cos E L_{4} sin A_{4} & cos E L_{4} cos A_{4} & cos E L_{4} & 1 \end{matrix}]

From the formula above and the formula of GDOP calculation, as can be seen that the GDOP value is only related to the elevation angle and azimuth angle of the visible satellite, so we can combine the elevation angle, azimuth angle, and geometry of visible satellites to research on satellite selection algorithm.^11,12 In addition, from the best geometry satellite selection algorithm, it can be seen that the key problem is the GDOP calculation.

GDOP contribution

The value of GDOP varies with the number of satellites chosen for positioning calculation from visible satellites. However, there is a certain regularity between the change of GDOP value and the number of satellites.

Assuming that H_n is an observation matrix of n satellites, let $H_{n} = {[h_{1}, h_{2}, \dots, h_{n}]}^{T}$ , the observation matrix that the ith satellite is removed from the n satellites is $H_{n - 1}^{i}$ , and the relationship between the two matrices is as follow¹³

H_{n}^{T} W_{n} H_{n} = H_{n - 1}^{i} +^{T} W_{n - 1}^{i} H_{n - 1}^{i} + h_{i}^{T} w_{i} h_{i}

Recording ${(H_{n}^{T} W_{n} H_{n})}^{- 1}$ as G_n, then

{GDOP}^{2} = trace G_{n}

From Sherman–Morrison formula, it can be obtained as follows

\begin{array}{l} G_{n - 1}^{i} = {(H_{n - 1}^{i} +^{T} W_{n - 1}^{i} H_{n - 1}^{i})}^{- 1} \\ = {(H_{n}^{T} W_{n} H_{n} - h_{i}^{T} w_{i} h_{i})}^{- 1} \\ = G_{n} + G_{n} h_{i}^{T} w_{i} {(1 - h_{i} G_{n} h_{i}^{T} w_{i})}^{- 1} h_{i} G_{n} \end{array}

where $(1 - h_{i} G_{n} h_{i}^{T} w_{i})$ is a scalar recorded as Κ_i, then

\begin{matrix} {GDOP}_{n - 1}^{i}^{2} = trace G_{n - 1}^{i} \\ = trace G_{n} + trace (G_{n} h_{i}^{T} w_{i} h_{i} G_{n} / Κ_{i}) \\ = {GDOP}_{n}^{2} + trace (G_{n} h_{i}^{T} w_{i} h_{i} G_{n} / Κ_{i}) \end{matrix}

From the formula (11), it can be seen that the ith satellite contribution to GDOP of all of n visible satellites is

Δ G = trace (G_{n} h_{i}^{T} w_{i} h_{i} G_{n} / Κ_{i})

To determine the sign of $trace (G_{n} h_{i}^{T} w_{i} h_{i} G_{n} / Κ_{i})$ , making singular value decomposition of $H_{n - 1}^{i}$ , then

H_{n - 1}^{i} = U S V^{T}

where U and V are orthogonal matrices of $(n - 1) \times (n - 1)$ and $(m + 3) \times (m + 3)$ , respectively, and S is a diagonal matrix of $(n - 1) \times (m + 3)$ .

Substituting formula (13) into formula (8) and making the same orthogonal variation on both sides of the formula, then using the Sherman–Morrison formula¹⁴

\begin{array}{l} {V^{T} (H_{n}^{T} W_{n} H_{n}) V}^{- 1} \\ = {V^{T} ({(U S V^{T})}^{T} W_{n - 1}^{i} U S V^{T}) V + V^{T} h_{i}^{T} w_{i} h_{i} V}^{- 1} \\ = {(Z + v w_{i} v^{T})}^{- 1} = Z^{- 1} - \frac{1}{1 + v^{T} Z^{- 1} w_{i} v} Z^{- 1} v w_{i} v^{T} Z^{- 1} \end{array}

where $Z = S^{T} W_{n - 1}^{i} S = diag (z_{11}, z_{22}, \dots, z_{(m + 3) \times (m + 3)}), | v = V^{T} h_{i}^{T} = {[\begin{matrix} v_{1} & v_{2} & \dots & v_{(m + 3)} \end{matrix}]}^{T}$ .

Orthogonal transform does not change the trace of the matrix, so

\begin{array}{l} trace ({(H_{n - 1}^{i} +^{T} W_{n - 1}^{i} H_{n - 1}^{i})}^{- 1}) = trace (Z^{- 1}) \\ = trace {{(V^{T} (H_{n}^{T} W_{n} H_{n}) V)}^{- 1}} + trace (k v_{z} w_{i} {v_{z}}^{T}) \\ = trace ({(H_{n}^{T} W_{n} {H_{n}}^{n})}^{- 1}) + trace (k v_{z} w_{i} {v_{z}}^{T}) \end{array}

where $v_{z} = Z^{- 1} v, trace (k v_{z} w_{i} v_{z}^{T}) = k w_{i} {\sum_{i = 1}^{m + 3} (\frac{v_{i}}{z_{i i}})}^{2} \equiv q > 0, k = 1 / (1 + \sum_{i = 1}^{m + 3} \frac{v_{i}^{2}}{z_{i i}})$ , then

{GDOP}_{n - 1}^{i}^{2} = {GDOP}_{n}^{2} + q > {GDOP}_{n}^{2}

The above formula shows that GDOP decreases with the increase of the number of satellites. Therefore, in the process of positioning, if the satellite has no faults, all visible satellite should be selected as possible for positioning calculation. However, when the number of visible satellites is large, the positioning calculation burden will be heavy. And GDOP does not decrease indefinitely with the increase of the number of satellites. As the number of satellites increases to some extent, the decrease of the number of satellites is not obvious.

From formula (12), we can get the following conclusion: the less $Δ G_{i}$ is, the smaller the effect of the ith satellite on GDOP_n is, and the removal of this satellite has little effect on the original GDOP. Thus, we can choose the satellites whose $Δ G_{i}$ is larger to get a better geometry distribution. By sorting $Δ G_{i}$ , choosing some visible satellites to calculate GDOP can reduce the dimension of observation matrix and the complexity of matrix inversion calculation, and it can also improve computational efficiency. The statistical experiment shows that when the value of $Δ G_{i} / G D O P_{n} > λ$ (λ is 0.15–0.20) and the ith satellite is removed,^13,14 the GDOP value of the combination varies greatly, so that we can add the terminal condition to eliminate the relative satellite through the loop.

Algorithm design

From the analysis above, it can be seen that selecting satellites based on geometry and GDOP contribution can not only increase the speed of satellite selection but also can select the combination with better geometry. The flow chart of satellite selection algorithm based on geometry and GDOP contribution is shown in Figure 1.

Figure 1.

Flow chart of satellite selection. ENU: East-North-Up; GDOP: geometric dilution of precision.

The general idea is as follows: firstly, select the satellites that meet the basic positioning requirements with a good geometric layout according to the elevation angles and azimuth angles, so that it can increase the initial satellite selection speed; secondly, based on GDOP contribution, the satellites whose GDOP contribution is smaller are eliminated step by step, but the positioning performance need to meet the setting criteria. Specific steps are as follows

Step 1: Obtain the total number of visible satellites and calculate the position coordinates in the Earth-Centered-Earth-Fixed (ECEF) coordinate system of each satellite;

Step 2: Convert the coordinates of the visible satellites from the ECEF coordinate system to the ENU coordinate system;

Step 3: Calculate the elevation and azimuth of all visible satellites and select the satellites with largest and the second maximal elevation angle as the top satellite to be selected. Check the difference between that of the two satellites, if it is less than 10°, select them as top satellites, if not, select only the satellite with the largest elevation angle as the top satellite¹⁵;

Step 4: Calculate the distance between the position of all visible satellites and that of the top satellite with the largest elevation angle and select the satellite with furthest from the distance as the first bottom satellite;

Step 5: With the exception of the selected satellites, calculate the difference of other satellites’ elevation angles and that of the first bottom satellite, and the satellites whose absolute value of the difference less than α are selected. To make the geometry better, the elevation angles of the bottom satellites should be in the same range, that is, the smaller α, the better the result. Generally, α is less than 30°. The initial value of α is 5°, the step γ is 5°, the total number l is recorded for each selection, if $l \geq m + 1$ (m is the number of GNSSs participating in the calculation), go to step 6, otherwise, continue to step 5 after the step α is increased;

Step 6: Calculate the difference between the azimuth angles of the visible satellites obtained in step 5 and that of the first bottom satellite and then calculate the difference between their absolute values and $k \frac{360}{m + 2}$ ( $k = 1 : (m + 1)$ ), the lowest difference satellite is selected in turn to obtain $(m + 1)$ bottom satellites. Thus, satellite selection based on geometry is to the end, the total number of selected satellites is $(m + 3)$ or $(m + 4)$ , it can meet the basic requirements of multi-GNSS positioning;

Step 7: Calculate Δ_G of the remaining visible satellites and then sort them according to the size of Δ_G, select the satellite with the smallest value of Δ_G;

Step 8: According to the determined conditions, if $Δ G_{i} / GDO P_{n} > λ$ (λ is taken as 0.2 in this article), satellite selection is to the end, otherwise, exclude the visible satellite with the smallest value of Δ_G, then repeat steps 7 and 8.

Simulation analysis

The observation data of JFNG tracking station of the MGEX network is selected to analyze. The data in the 342nd day of 2014 is selected. Two programs are respectively tested, GPS/BDS and GPS/BDS/GLONASS. The comparison of the positioning error and the elapsed time before and after satellite selection is made using the observation data of JFNG tracking station for 24 h statistically. The results are shown in Figures 2 to 5, where vertical error is taken as an example for the positioning error.

Figure 2.

Comparison of vertical positioning error before and after satellite selection based on GPS/BDS. BDS: Beidou Satellite Navigation System.

Figure 3.

Comparison of elapsed time before and after satellite selection based on GPS/BDS. BDS: Beidou Satellite Navigation System.

Figure 4.

Comparison of vertical positioning error before and after satellite selection based on GPS/BDS/GLONASS. BDS: Beidou Satellite Navigation System.

Figure 5.

Comparison of elapsed time before and after satellite selection based on GPS/BDS/GLONASS. BDS: Beidou Satellite Navigation System.

In the figures and table (Table 1) above, BSS stands for Before Satellite Selection, ASS stands for After Satellite Selection. From the results above, it can be seen that for the dual constellations combination of GPS and Beidou regional service system, with the satellite selection method, the mean and root mean square (RMS) values of positioning error in the vertical direction are both slightly increased, but the average time consumption is greatly reduced. This is also true for the combination of GPS/BDS/GLONASS, the purpose of this method is to select as few as visible satellites with less calculation fast, while having less impact on positioning accuracy.

Table 1.

Performance comparison of different programs.

	GPS/BDS		GPS/BDS/GLONASS
	BSS	ASS	BSS	ASS
Mean (m)	4.827	5.283	2.983	3.341
RMS (m)	5.292	5.651	3.039	3.517
Mean elapsed time (ms)	15.336	3.591	25.126	6.523

BDS: Beidou Satellite Navigation System; BSS: before satellite selection; ASS: after satellite selection.

Conclusion

In this article, to analyze the geometric characteristics of the best visible satellites combination, the layout of the elevation angles and azimuth angles of that is summarized. The satellite selection algorithm based on the best geometry is optimal, but it has a large amount of calculation and consumes long time. Therefore, a fast satellite selection algorithm based on both of geometry and GDOP contribution is proposed in this article. Firstly, according to elevation angles and azimuth angles, satellites with better geometry are selected to meet the basic positioning requirements and thus the initial satellite selection speed is improved. In addition, according to the GDOP contribution, the satellite with less contribution is gradually eliminated, so that the positioning performance meets the established criteria. Finally, this article selects the observation data of JFNG tracking station to simulate. On the premise of sacrificing a small amount of positioning accuracy, the simulation results show that the algorithm effectively solves the problem of matrix multiplication and matrix inversion in the best geometry algorithm and reduces the amount of computation and it can meet the real-time requirement of high dynamic users. The algorithm can be extended to satellite selection in any multiple constellation combination.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation, China (Grant No. 61502257), the Natural Science Foundation of Shanxi Province, China (Grant No. 201801D221210), and the 333 Academic Start Funding for Talents of NUC (Grant No. 13011911).

ORCID iD

Pengfei Zhang

References

Zhang

. Time scales and time transformations among satellite navigation systems. In: The 3 rd China Satellite Navigation Conference (CSNC2012), Guangzhou, China, 15–17 May 2012, pp. 491–502. Berlin: Springer.

Zhang

Huang

Zhang

. A new satellite selection algorithm for GPS Navigation. J UEST China 2000; 29(3): 221–224.

Huo

Miao

Zhao

. GDOP Estimation method in tightly coupled integrated navigation system. Trans Beijing Instit Techno 2014; 34(8): 831–835.

. Genetic programming for the approximation of GPS GDOP. In: Proceedings of the ninth international conference on machine learning and cybernetic, Qingdao, China, 24–26 February 2010, pp. 2944–2949. New York, NY, USA: IEEE.

. A comparative study on regression models of GPS GDOP using soft-computing technique. In: Proceedings of the 2009 IEEE international conference on fuzzy systems (Fuzz-IEEE 2009), Jeju Island, South Korea, 20–24 August 2009, pp. 1513–1516. New York, NY, USA: IEEE.

Song

Xue

Kang

. A novel method for optimum global positioning system satellite selection based on a modified genetic algorithm. PLOS One 2016; 11(3): 1–14.

Blanco-Delgado

Nunes

. Satellite selection method for multi-constellation GNSS using convex geometry. IEEE Trans Veh Technol 2010; 59(9): 4289–4297.

Liu

Zhao

Gao

. A fast satellite selection algorithm for GPS/BD Integrated Navigation System. Elect Optics Control 2017: 24(3): 32–35.

Nie

Gao

Wang

. A new method for satellite selection with controllable weighted PDOP threshold. Surv Rev 2017; 49(355): 285–293.

10.

Chen

Zhang

. A fast satellite selection approach for satellite navigation system. Chinese J Elect 2010; 38(12): 2887–2891.

11.

Deng

. GPS satellite selection algorithm based on elevation angle and GDOP. Digital Commun 2010; (4): 47–50.

12.

Cai

. An satellites selection algorithm based on elevation and azimuth. Ship Elect Eng 2009; 29(11): 73–75.

13.

Zhang

. A modified satellite selection algorithm based on satellite contribution for GDOP in GNSS. In: International conference on mechanical and electronic engineering (ICMEE 2012), Hefei, China, 23–24 June 2012, pp. 415–421. Berlin: Springer.

14.

Cong

Tan

. Satellite selection algorithm to improve precision and real-time performance of GPS positioning. Syst Eng Electron 2008; 30(10): 1914–1917.

15.

Zhang

. Research on fast satellite selection algorithm based on geometry. In: The 4th China satellite navigation conference (CSNC 2013), Lecture Notes in Electrical Engineering, 2013, 243, pp. 545–554.