Research on BDS/GPS Integrated Navigation Satellite Selection Algorithm Based on Particle Swarm Optimization

Abstract

In the multi-constellation satellite navigation system, all the visible satellites are used for positioning, which will increase the computation amount of the receiver and affect the real-time positioning. How to quickly and effectively select visible satellites for positioning is a research topic. For this problem, a satellite selection algorithm based on Particle Swarm Optimization (PSO) is proposed. In this method, the visible satellite is numbered, random grouping, and each group as a particle; the velocity-displacement model in the PSO keeps the particles gradually close to the minimum value of the GDOP. Under a series of simulation experiments, the key parameters such as inertia weight factor, acceleration coefficient and maximum velocity of PSO are determined. Besides, local search based on chaos mechanism are introduced, which can avoid the results of PSO algorithm into local optimum. Finally, the performance of satellite selection with PSO is confirmed to be remarkable by the simulation experiments under different numbers of selected satellites. The results show that this method can quickly select satellites under BDS and GPS system, and the result meets receiver positioning accuracy.

1 Introduction

With the development of the Global Positioning System (GPS) of the United States, GLONASS of Russia, Galileo of the EU and BeiDou of China, the number of visible satellites has increased significantly, and the combination of constellations will improve the user’s satellite geometry. Abundant navigation signal source provides the conditions that can improve the performance of the navigation and positioning, but it also brings signal processing burden of the receiver. If all visible satellites are used for positioning, it will be difficult to guarantee the real-time positioning. Therefore, selecting the best set of visible satellites is necessary from the multiple visible satellites, which can improve the accuracy and real-time performance of navigation and positioning.

The measure standard of satellite selection algorithm is the spatial geometry distribution between users and visible satellites. According to the characterization of the spatial distribution between user and visible satellites, dilution of precision is the most widely used in multiple parameters [1]. Among them, the Geometric Dilution of Precision (GDOP) is related to geometry between user and satellites. The smaller its value, the better the spatial geometric distribution and the higher the positioning accuracy. At present, researchers mainly focus on three aspects: the calculation of GDOP [2, 3], the fast satellites selection algorithm based on geometric distribution [4] and the satellites selection algorithm based on genetic algorithm [5, 6]. All of algorithms above mentioned can reduce the calculation of satellites selection to some extent, and get an effective result of satellites selection in shorter time. Similar to genetic algorithm, particle swarm optimization (PSO) is a bionic algorithm. The system forms the initial population by randomly generating a set of solutions. And then, according to the adaptation information of individuals, the algorithm starts to search among the population. Finally, PSO system will find the optimal solution in the search space. The PSO algorithm is well applied in many fields. This paper attempts to apply the PSO algorithm to satellites selection, and the PSO satellites selection model is established. By introducing a local search based on chaos mechanism, the global search ability of the algorithm is improved. The performance of the PSO was also verified by comparing with the results of satellites selection of traversal method. In the case of satellites selection of BDS/GPS, the number of satellites selection is more than 5, so the PSO satellites selection takes less time and has higher efficiency.

2 Calculation Method on DOP

The position of the navigation receiver position consists of the satellite position $(\text{x}_{u} ,{\text{y}}_{u} ,\text{z}_{u} )$ and the pseudo-range $\rho_{i}$ (j = 1, 2, … n, n is the total of visible satellites received by the receiver at the current time), the pseudo-range observation equation is as follows:

$$ \rho_{j} = \sqrt {(\text{x}_{j} - \text{x}_{u} )^{2} + (y_{j} - y_{u} )^{2} + (z_{j} - z_{u} )^{2} } + c(t_{u} - t_{j} ){ + }\varepsilon_{\rho } $$

(1)

$\rho_{j}$ is the value of the pseudo-range observations, $c$ is the speed of the light, $t_{u}$ is the prior time of the receiver relative to the GPS time, $t_{j}$ is the prior time that the jth satellite’s clock relative to the GPS system, $\varepsilon_{\rho }$ is the observed noise of the pseudo-range (including the ionospheric, tropospheric delay and delay caused by multipath effects).

In the process of positioning, the approximate position of the receiver is assumed to be $\hat{\rho }_{j} = (\widehat{\text{x}}_{u} ,\widehat{\text{y}}_{u} ,\widehat{\text{z}}_{u} )$, the estimated clock bias is $\hat{t}_{u}$. The first-order Taylor series expansion of (1) at the receiver approximate position and the clock bias yields the linearized equation:

$$ \Delta \rho_{j} = - \frac{{x_{j} - \widehat{x}_{u} }}{{\rho_{0} }}\Delta x_{u} - \frac{{y_{j} - \hat{y}_{u} }}{{\rho_{0} }}\Delta y_{u} - \frac{{z_{j} - \widehat{z}_{u} }}{{\rho_{0} }}\Delta z_{u} - c\Delta t_{u} + \varepsilon_{\rho } $$

(2)

where, $\rho_{0} = \sqrt {({\text{x}}_{j} - \widehat{\text{x}}_{u} )^{2} + (y_{j} - \hat{y}_{u} )^{2} + (z_{j} - \widehat{z}_{u} )^{2} }$, $\Delta \rho_{j} = \rho_{j} - \hat{\rho }_{j}$, $\Delta x_{u} = x_{u} - \hat{x}_{u}$, $\Delta y_{u} = y_{u} - \hat{y}_{u}$, $\Delta z_{u} = {\text{z}}_{u} - {\hat{\text{z}}}_{u}$, $\Delta t_{u} = t_{u} - \hat{t}_{u}$.

$l_{i} = - \frac{{x_{j} - \hat{x}_{u} }}{{\rho_{0} }}$, $m_{i} = - \frac{{y_{j} - \hat{y}_{u} }}{{\rho_{0} }}$, $n_{i} = - \frac{{z_{j} - \widehat{z}_{u} }}{{\rho_{0} }}$, respectively represent the direction cosine of the jth satellite unit vector from the approximate position. Equation (2) can be written in matrix form:

$$ \Delta \rho = H\Delta X $$

(3)

where,

$$ H = \left[ {\begin{array}{*{20}c} {l_{1} } & {m_{1} } & {n_{1} } & 1 \\ {l_{2} } & {m_{2} } & {n_{2} } & 1 \\ \ldots & \ldots & \ldots & \ldots \\ {l_{n} } & {m_{n} } & {n_{n} } & 1 \\ \end{array} } \right],\,\Delta X = \left[ {\begin{array}{*{20}c} {\Delta x_{u} } \\ {\Delta y_{u} } \\ {\Delta z_{u} } \\ { - c\Delta t_{u} } \\ \end{array} } \right],\,\Delta \rho = \rho_{j} - \hat{\rho }_{j} $$

(4)

The typical implementation of the solution algorithm is an iterative linear least-squares method, assuming that the pseudo-range error is $d\rho$ [1], and the components of the same distribution and independent of each other, the mean squared error equal to the satellite user range error, that is:

$$ \text{cov} (d\rho ) = I_{n \times n} \sigma_{UERE}^{2} $$

(5)

So,

$$ \text{cov} (dX) = (H^{T} H)^{ - 1} H^{T} \text{cov} (d\rho )H(H^{T} H)^{ - 1} = (H^{T} H)^{ - 1} \sigma_{UERE}^{2} $$

(6)

The dilution of the precision can be defined by the symmetric matrix $(H^{T} H)^{ - 1}$, the geometric dilution of the precision GDOP can be defined as the square root of the covariance matrix, and the other commonly used performance indicators are HDOP (Horizontal Dilution of Precision), PDOP (Position Dilution of Precision), TDOP (Time Dilution of Precision).

$$ GDOP = \sqrt {{\text{trace}}\{ (H^{T} H)^{ - 1} \} } $$

(7)

For BDS/GPS dual constellation, due to the different range error performance, it is usually done by appending extra columns in Eq. (4).

$$ H = \left[ {\begin{array}{*{20}c} {l_{G,1} } & {m_{G,1} } & {n_{G,1} } & 1 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ {l_{G,m} } & {m_{G,m} } & {n_{G,m} } & 1 & 0 \\ {l_{B,1} } & {m_{B,1} } & {n_{B,1} } & 0 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ {l_{B,n} } & {m_{B,n} } & {n_{B,n} } & 0 & 1 \\ \end{array} } \right] $$

(8)

In Eq. (8), the subscript G represents the GPS constellation, the number of visible satellites is $1 \ldots m$, subscript B represents the BDS constellation, the number of visible satellites is $1 \ldots n$. GDOP is still calculated using Eq. (7), which is a function only related to the satellite and user geometry layout. The value of GDOP changes with the change of the number of satellites involved in navigation, and decreased monotonously with the increase of satellites. The details are given in [7].

DOP is an important basis for satellites selection algorithm. The smaller the DOP is, the higher the accuracy of positioning resolution is. The satellites selection according to DOP can ensure the positioning accuracy [1].

3 Particle Swarm Optimization Algorithm

Particle Swarm Optimization (PSO), as a hot research topic in many fields, has been successfully applied in multiple fields (including neural network training, power system, communication, image processing, etc.) [8]. The PSO algorithm is a stochastic optimization algorithm based on swarm intelligence. it mimics the foraging behavior of birds. The problem search space is analogized to the flight space of birds, and each bird is abstracted into a particle to represent a candidate solution of the problem, the optimization needs to find the optimal solution is equivalent to looking for food. As a group optimization algorithm proposed by the simulation of biological predation in nature, the PSO algorithm can solve the optimization problem through the cooperation and competition among individuals in the population.

3.1 Basic Principle of PSO Algorithm

PSO is initialized to a random set of random particles (random solutions). In each iteration, the particle updates itself by tracking two “extrema” [9,10,11]. The first one is the optimal solution found by the particle itself, and called the individual extrema (pbest). The other is the optimal solution found by the entire population, and called the global extrema (gbest). After a limited number of iterations, each particle gradually approaches the optimal solution, and eventually finds the optimal solution. Taking the ith particle in d-dimensional search space as an example, its position and velocity are expressed as $X_{i} = [x_{i1} ,x_{i2} , \ldots ,x_{id} ]$, $V_{i} = [v_{i1} ,v_{i2} , \ldots ,v_{id} ]$.

The fitness value of each particle is evaluated by the fitness function, and the best position (pbest) $P_{i} = [p_{i1} ,p_{i2} , \ldots ,p_{id} ]$ after t iterations, and the best position (gbest) found in the population. Then, PSO algorithm updates velocity and position of each particle by follow equations:

$$ v_{i,j} (t + 1) = \omega v_{i,j} (t) + c_{1} r_{1} [p_{i,j} - x_{i,j} (t)] + c_{2} r_{2} [p_{g,j} - x_{i,j} (t)] $$

(9)

$$ x_{i,j} (t + 1) = x_{i,j} (t) + v_{i,j} (t + 1),\quad j = 1, \ldots ,d $$

(10)

where, $\omega$ is the inertial weight factor, $c_{1}$ and $c_{2}$ is acceleration coefficient, $r_{1}$ and $r_{2}$ is a random number that is evenly distributed between 0 and 1. In addition, by setting the velocity limitations $\left[ {v_{\hbox{min} } ,v_{\hbox{max} } } \right]$ and the position range $\left[ {x_{\hbox{min} } ,x_{\hbox{max} } } \right]$ of the particles, the movement of the particles can be appropriately restricted.

Different from genetic algorithm, PSO algorithm uses real number coding, standard PSO algorithm does not have more parameters to be adjusted. The search performance depends on the balance between global search and local improvement, which depends largely on the control parameters of the algorithm, including the size of population, maximum velocity, maximum iteration, inertia weight factor and acceleration coefficient. Standard PSO does not have many parameters to adjust, usually select according to experience [12].

The velocity limitations of particle $V_{\hbox{max} }$ determine the particle’s maximum move distance in an iteration cycle. Shi gives the simulation results of the PSO system optimization experiment, when $V_{\hbox{max} }$ is the alone value of $[2,V_{\hbox{max} } ]$ and the velocity inertia within [0.1, 1.05].

The acceleration factor $c_{1}$ and $c_{2}$ is usually chosen as 2, Clerc recommended the value of $(c_{1} { + }c_{1} )/2$ is 1.494.

Inertia factor $\omega$, the value is generally between (0, 1), Clerc suggested that its value is 0.729, and Riget adopted strategy which decreasing $\omega$ with the different number of iteration.

Termination conditions generally choose to reach the maximum cycle setting, or to meet the predetermined error requirements.

3.2 Chaotic Particle Swarm Optimization Algorithm

In order to make the particle swarm optimization algorithm faster at the optimal search time and avoid falling into the local optimum, the chaos concept, the time-varying inertia weight and the time-varying acceleration coefficient are introduced in PSO [13]. For a given optimization function, CPSO correspond to the search process as chaotic orbit traversal process, the search process has the ability to avoid local extremum, and finally obtain the global optimal solution or satisfactory solution. Optimization based on chaotic sequence includes two key steps:

• (1) Mapping chaos space to the solution space of optimization problem;

• (2) The use of chaotic dynamic characteristics to achieve the solution space search.

Logistic maps are one-dimensional discrete-time nonlinear systems and exhibit quadratic nonlinearity [12]. Logistic mapping is expressed as

$$ x_{i + 1} = f(x_{i} ) = \mu x_{i} (1 - x_{i} )\begin{array}{*{20}c} {} & {i = 0, 1, 2, \ldots } \\ \end{array} $$

(11)

where, $x_{i} \in (0,1)$, when $x_{0} \notin \left\{ {0,0.25,0.5,0.75,1} \right\}$ and $\mu = 4$, the sequence generated by Logistic mapping presents the chaotic dynamic characteristics. Small changes of the initial variables will lead to huge differences in the subsequent tracks.

4 The Steps of PSO Satellites Selection

Suppose at a certain moment, the number of visible satellites is n, and select a certain number of m from them. The GDOP value as small as possible. In the PSO satellites selection, each particle represents a combination of visible satellites, the location of the particle is determined by m elements, each element represents a visible satellite.

• (1) Coding

Randomly array all the visible satellites observed by the receiver at the current time, and then sequentially code the visible satellites from $1, \ldots ,n$ to the next, and the serial numbers correspond to the visible satellites one by one and remain unchanged in subsequent operations.

• (2) Generated initial population randomly

Set the population with M, the initial population of $G_{0} = \{ g_{0i} \} (i = 1, \ldots M)$, each particle $g_{ 0i} = [g_{ 0, 1} ,g_{ 0, 2} , \ldots ,g_{{ 0,{\text{m}}}} ]$ is taken from all visible satellites in initial population. In order to make the number of selected satellites is the same, we must ensure that each element is different in $g_{ 0i}$. Initialization velocity $v_{ 0} = [v_{ 0, 1} ,v_{ 0, 2} , \ldots ,v_{ 0,m} ]$, the subscript “0” means that the particles go through 0th iterations, that means the initial position and velocity. After repeated experiments, it is concluded that, in order to avoid the search results of PSO falling into local optimum, a chaotic sequence is introduced into the initial population. First, a random number $z_{i}$ of (0, 1) is generated, and $z_{i}$ is updated according to formula (11). the chaotic space is mapped to the solution space to be optimized according to the formula $x_{i} = x_{i\hbox{min} } + z_{i} (x_{i\hbox{max} } - x_{i\hbox{min} } )$.

• (3) Fitness calculation

The fitness used in this paper is the GDOP value which is the combination of visible satellites with encoding, and denoted as the target value $f_{t,i}$ of the particle, and the subscript “t” means that the particle go through tth iterations. The particles in the initial population are substituted into the fitness function in turn, and the fitness value of each particle is obtained. choose the smallest fitness value in population as the initial global optimal position gbest and each particle itself position as the initial local optimal position pbest.

• (4) Updated

For each particle, according to the position and velocity update formulas of PSO, the position $g_{t,i}$ and the velocity $v_{t,i}$ of the particle in the population are continuously corrected, and the target value corresponding to $f_{t,i}$ is calculated respectively.

5 Experiment and Simulation Analysis

PSO satellites selection is to solve the GNSS constellations, and the number of satellites selected more than 5. This paper select BDS/GPS dual constellations, the receiver coordinates are [−2279827.3156, 5004704.3094, 3219776.2093], the number of satellites selected is 6. The satellite position is calculated by ephemeris, and the cut-off height angle of the satellite is set as 5°. The simulation time start at 2016.7.31.00:00:00, the simulation duration is 900 s, and the simulation step is 60 s.

In this paper, we use the traversal method to get the GDOP value, and choose its value as a reference. Assuming that the number of all visible satellites is n, then select m visible satellites from them. Thus, the number of combinations are $C_{n}^{m}$. The so-called traversal method is to calculate the GDOP values of combinations one by one, and obtains the minimum value of GDOP. The number of BDS/GPS visible satellites and their corresponding minimum GDOP values are shown in Fig. 1.

Fig. 1

The number of BDS/GPS visible satellite and their min-GDOP

As can be seen in Fig. 1, at the same time, the receiver receives about 18 BDS/GPS visible satellites, take selecting 6 visible satellites from 18 visible satellites as an example, it needs to calculate GDOP values $C_{ 1 8}^{ 6} {\text{ = 18{,}564}}$ times. Each time-consuming about 2.6 s or so.

Set the algorithm parameters according to the PSO satellites selection procedure in Sect. 4: Number of iterations $MaxIt = 5 0$, Inertia coefficient $\omega = 0 . 7 2 9 8$, Acceleration coefficient $c_{ 1} = c_{ 2} = 1. 4 9 6 2$, $V_{\hbox{max} } = 2$. GDOP value is calculated at a certain moment. As the number of iterations increases, the GDOP value changes as shown in Fig. 2.

Fig. 2

GDOP values change with different

Fig. 3

GDOP values change with different number of PSO iterations number of CPSO iterations

By traversing method, the minimum value of GDOP at current moment is 2.25. From the results in the figure, the convergence velocity of PSO algorithm is fast, and the number of iterations is stable around 2.34 when it is less than 10th iterations. Obviously, PSO algorithm emerges “premature” phenomenon (that is trapped in the local optimum). The following uses CPSO algorithm, and the introduction of time-varying inertia weight and time-varying acceleration coefficient. Time-varying inertia weight $\omega$ usually decrease linearly from 0.9 to 0.4, and are expressed as $\omega = \omega_{\hbox{max} } - (\omega_{\hbox{max} } - \omega_{\hbox{min} } ) \times \frac{it}{\text{MaxIt}}$ in the iterative process. $\omega_{\hbox{max} } ,\omega_{\hbox{min} }$ is the maximum and minimum inertia coefficients, respectively; $it,{\text{MaxIt}}$ is the current iteration number and the maximum iteration number. The maximum number of iterations MaxIt is 50. Simulation test at the same moment, the results is obtained in Fig. 3.

It can be seen from this figure that the CPSO algorithm also converges when the number of iterations is less than 10, and effectively improves the disadvantage that PSO satellites selection algorithm fall into the local optimum. When the number of iterations is 50, the time-consuming is 1.512039 s. If the number of iterations is reduced to 15 times, the satellites selection time will be shorter.

The PSO and CPSO is applied to select the satellite, and each result is compared with the results of the traversal method. GDOP calculation error of the new algorithm is shown in Fig. 4.

Fig. 4

The results error of PSO and CPSO select satellites

It can be seen from the figure that the CPSO algorithm has a more stable GDOP error than the standard PSO algorithm. The calculation error of PSO-GDOP is between 0 and 0.5, while the calculation error of CPSO-GDOP is basically stable at 0–0.15.

6 Conclusions

In this paper, we present a method of selecting satellites by the Particle Swarm Optimization (PSO) algorithm. A satellites selection model of PSO is constructed and introducing the concept of chaos, effectively avoids the limitation of the PSO algorithm which is easy to get into the local optimum and improves the system stability. The simulation results show that under the BDS/GPS dual constellations, and the number of satellites selection is more than 5, the satellites selection time of proposed algorithm is shortened to 42.3% than traverse method, and the minimum GDOP calculation error is stable within a certain range, which can quickly select the satellites.