A navigation satellite selection algorithm for optimized positioning based on Gibbs sampler

Abstract

In various applications of satellite navigation and positioning, it is a key topic to select suitable satellites for positioning solutions to reduce the computational burden of the receiver in satellite selection system. Moreover, in order to reduce the processing burden of receivers, the satellite selection algorithm based on Gibbs sampler is proposed. First, the visible satellites are randomly sampled and divided into a group. The group is regarded as an initial combination selection scheme. Then, the geometric dilution of precision is chosen as an objective function to evaluate the scheme’s quality. In addition, the scheme is updated by the conditional probability distribution model of the Gibbs sampler algorithm, and it gradually approaches the global optimal solution of the satellite combination with better geometric distribution of the space satellite. Furthermore, an “adaptive perturbation” strategy is introduced to improve the global searching ability of the algorithm. Finally, the extensive experimental results demonstrate that when the number of selected satellite is more than 6, the time that the proposed algorithm with the improvement of “adaptive perturbation” takes to select satellite once is 43.7% of the time that the primitive Gibbs sampler algorithm takes. And its solutions are always 0.1 smaller than the related algorithms in geometric dilution of precision value. Therefore, the proposed algorithm can be considered as a promising candidate for satellite navigation application systems.

Keywords

Navigation satellite selection geometric dilution of precision Gibbs sampler adaptive perturbation

Introduction

The BeiDou navigation satellite system (BDS) is a new system that provides positioning, navigation, and timing services for the entire Asia Pacific region since 2012, and the ultimate goal is to be used globally in 2020.¹ As it is widely used, its service demand will also increase. The BDS plays an increasingly important role in our work and daily life. How to effectively use BDS to serve us is necessary and meaningful work. The selection of BeiDou satellite combination is a very important part of it.

In observation space, the number of observable BeiDou satellites can usually reach to 12–16 or even more in total.² In the navigation and positioning application, a set of satellites with a better spatial structure needs to be selected from all visible satellites for positioning. The precision factor (geometric dilution of precision (GDOP)) is commonly used to measure the geometrical distribution of satellite space. It is obtained by matrix multiplication and inversion calculation, which takes a long time. If a satellite combination with good spatial distribution is selected quickly from all visible satellite combinations, the number of GDOP calculations could be reduced, and the time-consuming required for satellite selection could be reduced.^3,4 Therefore, it is necessary to select the right satellite subset from observable ones for solving the problem in the various applications mentioned above. The problem of satellite selection has attracted many academicians to study. The key to solving this problem is to quickly eliminate redundancy from the many observable satellites and select effective satellites. Therefore, we have designed a satellite selection algorithm to improve the timeliness of satellite selection.

Previous research found that the positioning precision is affected by the selected satellite combination, and the performance of the satellite combination can be reflected by the GDOP value.⁵ The smaller the GDOP value, the better the satellite selection result and the higher the positioning precision.⁶ Based on the above findings, the minimum GDOP value (MGV) algorithm, the largest tetrahedron volume algorithm, and the maximum orthogonal projection were found and widely used. For the traditional algorithms,⁷ the amount of calculation increases significantly with the increase in the number of observable satellites.⁸ Furtherly, the largest tetrahedron volume algorithm, and the maximum orthogonal projection are mainly used for exactly four-satellite subset selection. Therefore, these algorithms are usually not applied to engineering projects directly. In recent years, a lot of researchers proposed machine learning (ML) algorithms to solve the satellite selection problem.^9,10 In addition to the shortcomings of these algorithms themselves such as easy to trap into local optimum, difficult to implement large-scale training samples, how to set appropriate parameters is also a difficult problem. Besides, neural network (NN) ideas are proposed for satellite selection algorithms,^11,12 which usually gives an approximate answer, and its results also depend on training process. Different training samples produce different results. In this article, in order to reduce the computational complexity and improve the timeliness, the Gibbs sampler algorithm is improved to make it suitable for BeiDou satellite selection scene.

This article is organized as follows. The related work analysis is described in section “Related work,” which compares the selection results of the traditional satellite selection algorithm and the recently proposed satellite selection algorithm, to pave the way for the algorithm proposed in this article. The related terminologies are described in section “Related terminologies,” which mainly introduces the main technical parameters for BeiDou satellite positioning and Gibbs sampler algorithm. The problem of satellite selection is described in section “The problem of navigation satellite selection,” and it is proposed that satellite selection is a combinatorial optimization problem. The details of Gibbs sampler algorithm to solve the satellite selection problem are described in section “Using improved Gibbs sampler algorithm to select optimal BeiDou satellite combination.” The experimental results are described in section “Experiment,” and the statistics and analysis are obtained from the amount of experimental data. The summary and conclusion of this article are described in section “Conclusion.” The future scope of this article is described in section “Future scope.”

Related work

As mentioned above, GDOP value is one of the main performance index to judge the quality of selected satellite subset. The original satellite selection algorithm is to minimize the GDOP value of satellite subset, which is called the MGV algorithm.¹³ In this algorithm, all possible satellite subsets are selected from all observable satellites, then select the one with the MGV as the optimal subset.¹⁴ Simple permutation and combination calculations mainly involved in it. As the number of satellites increases, the computational complexity of this algorithm will also increase greatly.¹⁵ Besides, the calculation of GDOP value of each satellite subset requires a large amount of matrix multiplication and inversion operations.¹⁶ Given the above description, we can see that it has extremely poor real-time performance, which is difficult to apply in high dynamic navigation and positioning scenes. To relieve the calculation burden, some quasi-optimal GDOP algorithms are proposed.

G Ou and colleagues¹⁷ proposed a recursive satellite selection algorithm to expand the selected satellite subset sequentially. M Wei et al.¹⁸ proposed a new algorithm that makes use of two satellites’ comparability and the distribution characteristic of satellites with high or low elevation to select satellites. D Roongpiboonsopit and HA Karimi¹⁹ proposed a multi-constellations satellite selection algorithm (MCSSA). The MCSSA considers the geometric arrangements of observable satellites and selects the ones that spread evenly over the observed sky view. M Zhang and J Zhang²⁰ put forward an idea that selects a satellite subset in a view whose geometry is close to the best as the optimal satellite combination. However, these algorithms usually used to select the sub-optimal satellite subset merely. Besides, the positioning precision of navigation and positioning are not satisfied.

It can be seen that satellite selection performance of the MGV algorithm is poor, then other optimized satellite selection algorithms are put such as maximize the volume of sagittal tetrahedron of satellite subset.^21–24 The algorithm is to select the combination with the largest volume in the polyhedron made up of the observable satellites and the receiver. The larger the volume, the smaller the GDOP value. This algorithm traverses the satellite combination corresponding to each satellite and calculates the volume of the tetrahedron of each combination, so the calculation is large. Similarly, another algorithm named the maximum orthogonal projection is proposed.²⁵ However, the two algorithms are only suitable for selecting four satellites from all observable satellites. The calculation amount of the two algorithms is $C_{n}^{4}$ ; $n$ is the number of observable satellites. As the number of observable satellites increases, the calculation amount and time-consuming in satellite selection will increase, affecting the real-time performance of positioning. Many scholars have begun to study new improved algorithms to avoid massive calculations.

In recent years, ML algorithms such as genetic algorithm (GA) and support vector machine (SVM) algorithm are used to solve GDOP value–based calculation problems. In 2010, MR Mosavi²⁶ proposed that GA is used to achieve satellite selection. GA has the ability of fast random search. However, the local search ability of GAs is poor, which brings time-consuming in implementation of the algorithm, and low efficiency in the late evolution. In practical applications, the algorithms are prone to cause premature convergence problems.²⁷ The researchers have made a lot of improvements to the GA algorithm, which improves the precision of the algorithm.^10,28–30 However, because many parameters need to be configured in the process of calculation, the satellite selection speed will also slow down as the number of observable satellites increases. N Zarei³¹ proposed that artificial NN is used to solve GDOP value without calculating the inverse matrix. It is based on the learning properties of artificial neurons but only gives an approximate rather than an exact answer. The performance of the above algorithms also depends on the training time and the amount of training data. DJ Jwo and CC Lai³² presented an NN-based navigation satellite subset selection algorithm to reduce the training time of back propagation neural network (BPNN). A Hamed and M Mohammad-Reza³³ proposed improved back propagation (BP) algorithms, including resilient BP that has greater precision and less calculation time. Even if the idea of classification is used to simplify the problem, these algorithms still need to calculate the GDOP value of each satellite subset from all possible subsets.³⁴ Besides, this classification thought can only roughly classify crucial values of each satellite subset to an approximate range.

In order to avoid the shortcomings of the above existing algorithms, this article proposes a navigation satellite selection algorithm for optimized positioning based on Gibbs sampler to effectively improve the timeliness of BeiDou satellite selection and the positioning precision of BeiDou satellite.

Related terminologies

In various applications of BeiDou satellite navigation and positioning, in order to ensure the positioning precision, selecting suitable $n (n \geq 4)$ BeiDou satellites from several observable BeiDou satellites for solution is needed.^35,36 The study shows that when the observation error is constant, the difference of the geometry relationship between the observation point and the $n$ BeiDou satellites participating in the positioning will directly affect the positioning precision.³⁷ The final solution of the BeiDou navigation positioning equation can be expressed as follows

Δ X = GDOP \cdot Δ ρ

(1)

where $Δ X$ is the position error and $Δ ρ$ is the observation error; GDOP(geometrical dilution of precision) is the geometric precision attenuation factor. GDOP reflects the spatial geometry relationship between the observation site and BeiDou satellites. The study shows that when the observation error is constant and its value is within an acceptable range, the GDOP value is proportional to the position error. So the smaller the GDOP value, the higher the positioning accuracy.³⁸

The GDOP value can be solved effectively by the method proposed in this article, which is based on the Gibbs sampler algorithm proposed by German in 1984. Its most significant feature is the construction of a Markov chain of this algorithm by constructing a conditional distribution sequence along a series of complementary directions. The algorithm is suitable for a distributed solution of discrete multi-dimensional problems.^39,40 The problem of BeiDou satellite combination is to find the optimal combination among all BeiDou satellites in order to minimize the GDOP value of the selected BeiDou satellite combination, which belongs to a kind of discrete combinatorial optimization problem. The distribution function of Gibbs sampler is as follows

π_{T} (X) = \frac{1}{Z_{T}} e^{- \frac{1}{T} ε (X)}

(2)

where $X$ denotes a state vector of the system, $Λ$ denotes the set of all state vectors, and $X \in Λ$ . $T$ represents temperature and $T > 0$ . The energy function $ε (X)$ represents the energy of the state vector $X$ , $0 < ε (X) < + \infty$ . $Z_{T} = \sum_{X' \in Λ} e^{- 1 / T ε (X')}$ and $π_{T} (X) \in [0, 1]$ .

Gibbs sampler updates its state vector in the following way: Suppose that the state vector $X$ is divided into d components. Let the state vector in the tth iteration be $X^{(t)} = (x_{1}^{(t)}, \dots, x_{d}^{(t)})$ , then for any one $i (1 = 1, 2, \dots, d)$ in the t+ 1th iteration, sample $x_{i}^{(t + 1)}$ in the state space according to the conditional probability distribution $p (x_{i} | x_{1}^{(t + 1)}, \dots, x_{i - 1}^{(t + 1)}, x_{i + 1}^{(t)}, \dots, x_{d}^{(t)})$ . After updating the state vector many times according to the above steps, the state vector $X^{(0)}, X^{(1)}, \dots, X^{(t)}, \dots, X^{(t + 1)}, \dots$ approximately obeys the target distribution $π$ . Gibbs sampler could ensure that the system starts from a random state vector and eventually converges to the target distribution. As can be seen from the Gibbs sampler distribution function, the smaller the value of the energy function of a certain state, the greater the selection probability. Based on the optimized target, the energy function is constructed to calculate the selection probability of BeiDou satellites. Then the best BeiDou satellite combination is selected with the smallest GDOP value according to the probability.

The problem of navigation satellite selection

Take the study of BeiDou satellite as an example, the selection of the optimal satellite set is a combinatorial optimization problem; select n from m observable satellites as a combination, that is, select the combination with the smallest GDOP value from $C_{m}^{n}$ possible combinations. Based on the above principle, we propose the following problem model.

Define $S = {1, 2, . . ., m}$ as the index set of $m$ observable satellites, $s$ represents each satellite in set $S$ and $s \in S$ . Now we have the geocentric coordinates of $M$ observable satellites $Q = [X, Y, Z]$ . And define $p = [x, y, z]$ as the geocentric coordinate of the observation point. The coordinate of each observable satellite is relative to the position of the observation point. The satellite selection optimization problem is to search the optimal from $S$ using the coordinates information

where $J$ is the minimum number of satellites to ensure the precision of satellite positioning, usually is 4. And $G$ function represents the objective function for given Q, p and . Since Q and p are known, the G function value can be computed by shown as following definition.

Definition 1

GDOP function: GDOP of one satellite combination is calculated with the detailed coordinate values of selected satellites and observable satellites. It is an important performance index that could reflect the positioning precision. The smaller the GDOP value, the higher the positioning precision. This article aims to minimize the GDOP value of the satellite subset using Gibbs sampler algorithm with the help of “adaptive perturbation” strategy (improved Gibbs sampler).

The main points of the proposed algorithm are introduced as follows. First, the satellite selection problem is described as a combination optimization problem, and the objective function and search space are defined. Then Gibbs sampler is incorporated to solve the problem. Meanwhile, “adaptive perturbation” strategy is designed to improve the global searching ability of the algorithm. In this algorithm, GDOP value of each satellite combination is used to compute the corresponding energy function value, which will be utilized to consider its selection probability. The “adaptive perturbation” strategy mainly includes changing satellite selection probability by changing weighting coefficient value. The proposed algorithm can be considered as a promising candidate for satellite navigation application systems. BeiDou satellite was selected as an example in this article, and a number of suitable BeiDou satellites were selected from the observable satellites relative to the observation point. Usually, the number of observable satellites in satellite navigation system is about 15 at a certain time.⁴¹ It has been proved that when the loss of positioning accuracy is not well, the calculation amount could be reduced effectively after selecting a suitable number of well-distributed satellites.^42,43

Calculate the azimuth and elevation angle of the observable satellites

Set the observation point as the origin, the long axis of the earth ellipsoid as the X-axis, the short half axis of the earth ellipsoid as the Y-axis, and the normal of the earth ellipsoid as the Z-axis, thus, the carrier coordinate system is constructed.^44,45 And the carrier coordinates of each satellite can be presented as $[\begin{matrix} x_{s}^{c} & y_{s}^{c} & z_{s}^{c} \end{matrix}]^{T}$ . The superscript $c$ represents the coordinate is in the carrier coordinate system. $M$ independent geocentric coordinates in coordinate set $Q$ correspond to each satellite $s$ : $[\begin{matrix} x_{s} & y_{s} & z_{s} \end{matrix}]^{T}$ . By coordinate system transformation, we can obtain the carrier coordinates $[\begin{matrix} x_{s}^{c} & y_{s}^{c} & z_{s}^{c} \end{matrix}]^{T}$ of the observable satellites from the geocentric coordinates of the observable satellites and the observation point

[\begin{matrix} x_{s}^{c} \\ y_{s}^{c} \\ z_{s}^{c} \end{matrix}] = H \times [\begin{matrix} x_{s}^{e} - x^{e} \\ y_{s}^{e} - y^{e} \\ z_{s}^{e} - z^{e} \end{matrix}]

(4)

where $H$ is the transformation matrix between the carrier coordinate system and the geocentric coordinate system

H = [\begin{matrix} - \sin B^{p} \cos L^{p} & - \sin B^{p} \sin L^{p} & \cos B^{p} \\ - \sin L^{p} & \cos L^{p} & 0 \\ \cos B^{p} \cos L^{p} & \cos B^{p} \cos L^{p} & \sin B^{p} \end{matrix}]

(5)

where $B^{p}, L^{p}$ are the earth latitude and longitude of the observation point. The relationship between the satellite coordinates $x_{s}^{c}, y_{s}^{c}, z_{s}^{c}$ in the carrier coordinate system and the azimuth angle $A_{s}$ and elevation angle $E_{s}$ of the satellite is given as follows

[\begin{matrix} x_{s}^{c} \\ y_{s}^{c} \\ z_{s}^{c} \end{matrix}] = ρ [\begin{matrix} \cos E_{s} \cos A_{s} \\ \cos E_{s} \sin A_{s} \\ \sin E_{s} \end{matrix}]

(6)

where $ρ = \sqrt{{(x_{s}^{c})}^{2} + {(y_{s}^{c})}^{2} + {(z_{s}^{c})}^{2}}$ . The azimuth angle $A_{s}$ and the elevation angle $E_{s}$ of the satellite $s$ are obtained as follows

A_{s} = \arctan (\frac{y_{s}^{c}}{x_{s}^{c}})

(7)

E_{s} = \arctan (\frac{z_{s}^{c}}{\sqrt{{(x_{s}^{c})}^{2} + {(y_{s}^{c})}^{2}}})

(8)

Calculate the state matrix of the BeiDou satellites and construct the objective function

Let the selected satellite combination be then the azimuth and elevation angles of the BeiDou satellites are ${A_{S_{1}}, A_{S_{2}}, \dots, A_{S_{n}}}$ and ${E_{S_{1}}, E_{S_{2}}, \dots, E_{S_{n}}}$ , respectively; the state matrix of the BeiDou satellite combination is calculated using equation (9)

Use equation (10) to obtain the GDOP value of the BeiDou satellite combination as the objective function of the problem

where the $trace$ function represents the trace of the matrix; according to the research, the smaller the objective function value , the better the performance of the satellite combination $N$ .

Determining the network model of the satellite combination

Definition 2

Network model: As shown in Figure 1, a two-dimensional space is constructed, and each column contains $m$ observable satellites; let $O_{ip}$ denote the ith observable satellite node in the pth dimension with $i = 1, 2, \dots, m$ and denote $O_{jq}$ the jth observable satellite in the qth dimension node with $q = 1, 2, \dots, n$ ; define $D = {d_{1}, d_{2}, \dots, d_{n}}$ as dimensions set; define $C = {c_{1}, c_{2}, \dots, c_{m}}$ as observable BeiDou satellites set; $D \to C :$ In the network model of BeiDou satellites optimization selection, $n$ satellites in the $M$ BeiDou visible satellite set $C$ are selected from the dimension set $D$ to form a BeiDou satellite combination selection scheme .

Figure 1.

Schematic diagram of network model.

Using improved Gibbs sampler algorithm to select optimal BeiDou satellite combination

Gibbs sampler algorithm and BeiDou satellite selection problem

Gibbs sampler is an algorithm used to obtain a series of observation samples. The Gibbs sampler algorithm continuously updates the satellite combination selection scheme through random sampling to optimize the objective function. When a certain condition is satisfied or the number of iterations reaches the maximum, the iteration is terminated and the final combination scheme is obtained.^46,47 Preliminary research has shown that it has innate advantages such as sensitivity and rapid convergence in solving such complex combination optimization problems.^48,49 The method to solve the BeiDou satellite combination selection problem is to find the optimal BeiDou satellite combination among all observable satellites so that its GDOP value reaches to the smallest, which belongs to discrete combination optimization problems. Improved Gibbs sampler algorithm was used to calculate the selection probability of each BeiDou satellite and complete the optimization of the BeiDou satellite combination according to the probability so that it could converge to the optimal or near optimal set of BeiDou satellites.

The specific steps of improved Gibbs sampler algorithm for selecting the optimal BeiDou satellite combination

Define $L$ as the number of iterations, let $L_{\max}$ be the maximum number of iterations, and initialize $L = 1$ ; let denote a initial selection scheme for BeiDou satellite combination, which means that in the Lth iteration, dimension set $D$ randomly selects n satellites from m BeiDou visual satellite set $C$ as a group. Then the state of each dimension in the initial selection scheme of BeiDou satellite combination in the Lth iteration is known.

The optional BeiDou satellite record table is defined as $R$ , which means the set $C$ composed of $m$ BeiDou observable satellites except the number of selected visual satellites in initial selection scheme of BeiDou satellite combination. Define the number of BeiDou satellites in the optional BeiDou satellite record table $R$ as $p = m - n$ ; initialize $i = 1$ ; define variable $k$ and initialize $k = 1$ ; $R_{k}$ represents the BeiDou satellite record table after the kth iteration, then initialize $R_{k} = R$ .

After the kth update, the kth BeiDou observable satellite is selected from the optional BeiDou satellite record table $R_{k}$ to obtain the state $a_{L, K} (d_{i})$ of the $d_{i}$ of the ith dimension, and the BeiDou satellite combination selection scheme is obtained after the kth update of the state $a_{L, K} (d_{i})$ of the $d_{i}$ of the ith dimension in the Lth iteration; The local energy $ε_{L, K} (a_{L, K} (d_{i}), a'_{L} (d_{j})_{j \in B_{i}})$ corresponding to the BeiDou satellite combination selection scheme is given by

where $B_{i}$ is the set of the subscripts of the remaining $(n - 1)$ dimensions with the except of $d_{i}$ of the ith dimension in dimension $D$ . When $i = 1$ , $B_{i} = 2, 3, \dots, n$ ; when $i \geq 2, B_{i} = 1, 2, \dots, i - 1, i + 1, \dots, n$ ; $a'_{L} (d_{j})_{j \in B_{i}}$ is all the states of the remaining $(n - 1)$ dimensions after that the ith dimension $d_{i}$ in initial selection scheme of BeiDou satellite combination is removed from dimension set $D$ ; is the combination of $n$ BeiDou satellites selected in BeiDou satellite combination selection scheme , and is the $GDOP$ value of the objective function of ; the distribution function of Gibbs sampler is given by

π_{T} (X) = \frac{1}{Z_{T}} e^{- \frac{1}{T} ε (X)}

(12)

where $X$ represents a state vector of the system, $Λ$ represents a set of all state vectors, $X \in Λ$ . $T > 0$ represents temperature, and energy function $ε (X)$ represents the energy of state vector $X$ , $0 < ε (X) < + \infty$ . $Z_{T} = \sum_{X' \in Λ} e^{- \frac{1}{T} ε (X')}$ , $π_{T} (X) \in [0, 1]$ .

Gibbs sampler updates its state vector by assuming that the state vector $X$ is divided into $f$ components, that is, $X = (x_{1}, x_{2}, \dots, x_{f})$ . Let the state vector $X^{t} = (x_{1}^{t}, x_{2}^{t}, \dots, x_{f}^{t})$ in the tth iteration, then for any $u (u = 1, 2, \dots, f)$ in the $t + 1$ iteration, the conditional probability distribution $p (x_{u} | x_{1}^{(t + 1)}, x_{2}^{(t + 1)}, \dots, x_{u - 1}^{(t + 1)}, x_{u + 1}^{(t + 1)}, \dots, x_{f}^{(t)})$ is used to sample $x_{u}^{(t + 1)}$ in the state space. The above probability distribution can be obtained by Gibbs sampler distribution function.

It can be proved that the state vectors $X^{(0)}, X^{(1)}, \dots, X^{(T)}, X^{(T + 1)}, \dots$ approximately obey the target distribution $π$ by updating the state vectors sufficiently according to the above steps. In this way, the goal of sampler random samples from a given distribution is achieved. Gibbs sampler is a mechanism that ensures that the system starts with a random state vector and eventually converges to the target distribution. From the Gibbs sampler distribution function, it can be seen that the smaller the energy function value of a state, the greater the probability of selection. From equations (11) and (12), the probability after the kth update of the state $a_{L, K} (d_{i})$ of the $d_{i}$ of the ith dimension in the Lth iterations is given by

\begin{matrix} μ_{L, K} (a_{L, K} (d_{i})) = \\ \frac{\exp (- \frac{1}{T} ε_{L, K} (a_{L, K} (d_{i}), a'_{L} {(d_{j})}_{j \in B_{i}}))}{\sum_{a_{L, K} (d_{i}) \in C} \exp (- \frac{1}{T} ε_{L, K} (a_{L, K} (d_{i}), a'_{L} {(d_{j})}_{j \in B_{i}}))} \end{matrix}

(13)

where $T$ is the temperature coefficient in the Gibbs sampler distribution function and has $T > 0$ ; $d_{i}$ updates its state according to the state of the remaining $(n - 1)$ dimensions in BeiDou satellite combination selection scheme . That is, in the case where the number of BeiDou satellites selected in the remaining $(n - 1)$ dimension is known, the remaining BeiDou satellites were selected in $C$ according to the probability function $μ_{L, K} (a_{L, K} (d_{i}))$ to complete a status update. At the same time, it can be seen that the lower the local energy corresponding to a certain state, the more likely $d_{i}$ is to select it. In order to make the algorithm converge better to BeiDou satellite selection scheme with global minimum energy, an improved strategy of “adaptive perturbation” is given by

\begin{matrix} μ_{L, K} (a_{L, K} (d_{i})) = \\ \frac{1}{σ} \exp (- \frac{ε_{L, K} (a_{L, K} (d_{i}), a'_{L} (d_{j})) {(1 + \frac{g}{2 \cdot g_{\max}})}^{g}}{T}) \end{matrix}

(14)

\begin{matrix} σ = \sum_{a_{L, K} (d_{i}) \in C} \\ \exp (- \frac{1}{T} ε_{L, K} (a_{L, K} (d_{i}), a'_{L} (d_{j})) {(\frac{g + 2 \cdot g_{\max}}{2 \cdot g_{\max}})}^{g}) \end{matrix}

(15)

where $g$ is a perturbation scale and is defined as follows $g = {\begin{matrix} g + 1, & g + 1 \leq g_{\max} \\ g_{\max}, & others \end{matrix}$ Obviously, when the optimal solution obtained at the initial stage of the algorithm is still evolving without introducing the perturbation scale, it does not affect the probability of selecting BeiDou satellite for $d_{i}$ of the ith dimension. When the optimal solution obtained by the algorithm does not improve significantly after $N C_{con}$ ( $N C_{con}$ is positive integer) cycles, the perturbation effect starts to occur when the possible local minimum occurs. The local energy $(a_{L, K} (d_{i}), a'_{L} (d_{j})_{j \in B_{i}})$ of $d_{i}$ in the ith dimension is significantly increased, so the possibility of selecting BeiDou satellite that selected previously for $d_{i}$ in the ith dimension is reduced, and it tends to explore new solutions. In the case that the optimal solution is still not improved, the perturbation action is accelerated, which makes the solution more easily jump out of the local minimum. In addition, in order to ensure the convergence speed of the algorithm, $g_{\max}$ is introduced to control the perturbation scale.

In the Lth iteration, the selected BeiDou satellite number of the state $a_{L, K} (d_{i})$ of the ith dimension $d_{i}$ in the kth update is removed from the optional BeiDou satellite record table $R_{k}$ after the kth update, to obtain the optional BeiDou satellite record table $R_{k + 1}$ after the $k + 1 th$ update. Then assign $P - 1$ to $P$ . If $k < p$ is valid, then $k + 1$ is assigned to $K$ and new $K$ . Otherwise, make the probability set $μ_{L} = (μ_{L, 1} (a_{L, 1} (d_{i})), μ_{L, k}$ $(a_{L, k} (d_{i})), \dots, μ_{L, P} (a_{L, P} (d_{i})))$ for the state of the ith dimension $d_{i}$ in the kth update in the Lth iteration, and an observable BeiDou satellite for $d_{i}$ of the ith dimension is selected according to the probability set, which is represented by $a_{L} (d_{i})$ . To judge whether $i < n$ is valid or not, if it is valid, the state of the ith dimension for initial selection scheme of BeiDou satellite combination obtained in the Lth iteration will updated to $a'_{L} (d_{i}) = a_{L} (d_{i})$ . Then assign $i + 1$ to $i$ and new $i$ . Otherwise, the dimension set $D$ in the Lth iteration chooses the BeiDou satellite combination selection scheme formed by n satellites in the set $C$ composed of $m$ BeiDou observable satellites. If $L \geq L_{\max}$ , then make the selection scheme set

for BeiDou satellite combination formed by $n$ satellites in the set $C$ composed of $m$ BeiDou observable satellites. And choose the selection scheme for BeiDou satellite combination with the lowest objective function value as the optimal scheme from the scheme set ; Otherwise, assign $L + 1$ to $L$ and new $L$ .

Based on the discussion above, a flowchart that describes the operation steps of the algorithm intuitively is presented in Figure 2. The main process of improved Gibbs sampler algorithm is shown in Figure 3. Figure 3 highlights improvement measures added to the basic Gibbs sampler algorithm. It is a perturbation mechanism applied to the desired heuristic factor, in order to prevent the algorithm from falling into local optimum.

Figure 2.

Flowchart of the proposed algorithm.

Figure 3.

Improved Gibbs sampler algorithm process diagram.

Experiment

In order to verify the performance of the proposed algorithm, three algorithms are compared, including the traditional traversal algorithm, Gibbs sampler algorithm, and Gibbs sampler algorithm with the help of “adaptive perturbation” strategy (improved Gibbs sampler algorithm). The GDOP value is respectively computed via VC++software running on a Linux server with 8 Intel Xeon CPUs at 2.66 GHz, 3GB memory. We make use of high-precision global navigation satellite system (GNSS) receiver to collect raw data for 4 h. Considering its validity, we only choose 8000 continuous data from the raw data, including ephemeris data and observation data of 15 satellites in view. Two sets of experiments are conducted. In the first set, we set time as an argument and observe the change of GDOP value. In the second set, we set iteration number as argument and observe the change of GDOP value.

From the three ephemeris diagrams shown in Figure 4, We can see the results of the three algorithms in the same set of experiments, which are reflected by specific GDOP values. They are the best combination of six satellites selected from 15 observable satellites. More specifically, color of solid sphere in Figure 4 is used to represent satellite status, red means the satellite is selected, and blue means the satellite is not selected. The value marked in the solid sphere is satellite number. It can be seen that satellites numbered #142, #144, #150, #151, #152, and #154 were selected using traditional traversal algorithm, and its GDOP value is 2.6901 (Figure 4(a)); satellites numbered #142, #144, #149, #150, #151, and #152 are selected using Gibbs sampler algorithm, and its GDOP value is 2.9414 (Figure 4(b)); satellites numbered #142, #144, #149, #150, #151, and #154 are selected using improved Gibbs sampler algorithm, and its GDOP value is 2.8227 (Figure 4(c)).

Figure 4.

Satellite selection results of three algorithms in some moment: (a) GDOP = 2.6901, (b) GDOP = 2.9414, and (c) GDOP = 2.8227.

In order to further distinguish the advantages and disadvantages of the three algorithms, 20 sets of experiments were carried out; the average of the experimental results is shown in Table 1. From Table 1, we can see that the average GDOP values of satellite subset are 2.6965, 2.9585, and 2.821, respectively, which are obtained by the three algorithms, respectively. It has been proved that the traditional traversal algorithm can achieve approximate optimal solution with almost smallest GDOP value (2.6965) but with almost biggest time-consuming (15.655 s) because of its large amount of calculation. Thus, it is difficult to be used in real-time-based navigation and positioning system. Both Gibbs sampler and improved Gibbs sampler algorithm have reached the approximate optimal solution with the GDOP values of 2.9585 and 2.821, respectively. However, since they are optimized algorithms, they can obtain approximate optimal solutions in an acceptable time range, which has important practical application value.

Table 1.

The average value of satellite selection results of three algorithms in 20 sets of experiments.

Algorithm	GDOP	Calculation time (s)
Traditional traversal algorithm	2.6965	15.655
Gibbs sampling algorithm	2.9585	10.124
Improved Gibbs sampling algorithm	2.821	4.425

GDOP: geometric dilution of precision.

Figure 5 intuitively presents the experimental results in Table 1. In each group of experiments, traditional traversal algorithm can obtain the optimal solution (the MGV); improved Gibbs sampler algorithm is superior to Gibbs sampler algorithm for its solutions are always 0.1 smaller than that in GDOP value.

Figure 5.

Comparison of GDOP values for 20-set of experiment in three algorithms.

The stability of the algorithm in a certain period of time can also be used as a criterion for evaluating the performance of the algorithm. Figure 6 shows that changes in GDOP value calculated by the two algorithms in 2 h. It can be seen that GDOP value of the satellite subset using improved Gibbs sampler algorithm is smaller than that using Gibbs sampler algorithm most of the time. Furthermore, the GDOP value of the satellite subset selected by the improved algorithm is more similar to the optimal algorithm, which is shown in the red curve in Figure 6. The above experimental results verified that the improved Gibbs sampler algorithm in this article has better performance and higher stability in practical application.

Figure 6.

Variation in GDOP values of two algorithms within 2 h.

In addition, we made statistics about the relationship between GDOP value and iteration index over 100 random realizations by the two algorithms mentioned above, which is shown in Figure 7. As illustrated in Figure 7, for improved Gibbs sampler algorithm, when the index of iterations reaches 35, the optimal GDOP value emerges. However, for Gibbs sampler algorithm, the optimal GDOP value does not appear until the number of iterations is 50, 15 iterations more than the former algorithm. Furthermore, the proposed algorithm with the improvement of “adaptive perturbation” outperforms primitive Gibbs sampler algorithm by up to 72.6%, and its solutions are always 0.1 smaller than the related algorithms in GDOP value. Obviously, the designed “adaptive perturbation” strategy can improve the global searching ability of the Gibbs sampler algorithm and achieve approximate optimal solution, with low complexity and fast convergence.

Figure 7.

Variation of GDOP value with the increase of iterations over 100 random realizations.

Conclusion

In this article, the satellite selection problem is described as a combination optimization problem. Then, Gibbs sampler–based navigation satellite selection algorithm is proposed. A fast satellite selection was achieved using the proposed algorithm, and the number of calculations for the GDOP value is reduced. According to simulation experiments on the algorithm, the results are as follows: (1) When the number of selected satellite is 6, the time that the proposed algorithm with the improvement of “adaptive perturbation” takes to select satellite once is 4.425 s, 43.7% of the time that the primitive Gibbs sampler algorithm takes. (2) The “adaptive perturbation” strategy could improve the global searching ability of the algorithm. (3) The GDOP value that the proposed algorithm with the improvement of “adaptive perturbation” calculate is 2.8, 0.1 smaller than that calculated by the primitive Gibbs sampler algorithm. The extensive experimental results demonstrate that the algorithm can achieve the approximate optimal satellite combination in real time with almost smallest GDOP.

Future scope

BeiDou satellite has been widely used in the navigation and positioning of aircraft, ships and vehicles, time service, and other fields. In various applications of BeiDou satellite navigation and positioning, the result of satellite selection will directly affect the positioning precision, so the satellite selection algorithm is of great significance for it. The satellite selection algorithm proposed in this article has the advantages of low complexity, high execution efficiency, and good timeliness. Compared with single constellation, the number of visible satellites was increased in multi-constellation, but the method of satellite selection is similar. Thus, the algorithm proposed in this article can also be applied to multi-constellation integrated navigation system in the future.

Footnotes

Handling Editor: Ashish Kr Luhach

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 is supported by the National Natural Science Foundation of China under grant nos. 61971178, 61701161; the Fundamental Research Funds for the Central Universities under grant nos 219JZ2018YYPY0301 and PA2018GDQT0016; the Technology Innovation Guidance Project (Fund) of Shaanxi Province under grant no. 2020CGHJ-002; the Science and Technology Major Project of Anhui Province under grant no. 18030901015.

ORCID iD

Na Xia

References

Ren

Zhang

Xie

, et al. Global ionospheric modelling using multi-GNSS: BeiDou, Galileo, GLONASS and GPS. Sci Rep 2016; 6: 33499.

Shi

, et al. Positioning system based satellite communication and Chinese Area Positioning System (CAPS). Chin J Astron Astrophys 2008; 8(6): 611–635.

Meng

Zhu

Wang

. A new fast satellite selection algorithm for BDS-GPS receivers. In: SiPS 2013 proceedings, Taipei City, Taiwan, 16–18 October 2013, pp.371–376. New York: IEEE.

Huang

Chris

Craig

. Satellite selection with an end-to-end deep learning network. GPS Solut 2018; 22(4): 108.

Zhu

. A novel satellite selecting algorithm for BeiDou navigation satellite system. In: 2015 international conference on wireless communications & signal processing (WCSP), Nanjing China, 15–17 October 2015, pp.1–4. New York: IEEE.

Zhu

. Calculation of geometric dilution of precision. IEEE Trans Aero Electron Syst 1992; 28(3): 893–895.

Zhuo

. A new method of selecting GPS satellites. J Astronaut Metro Meas 2009; 29(2): 54–56.

Zhanc

. A fast satellite selection algorithm: beyond four satellites. IEEE J-STSP 2009; 3(5): 740–747.

Mosavi

. Applying genetic algorithm to fast and precise selection of GPS satellites. Asian J Appl Sci Eng 2011; 4(3): 229–237.

10.

Zhu

. An optimal satellite selection model of global navigation satellite system based on genetic algorithm. In: Sun

Yang

Guo

(eds) 2018 China satellite navigation conference (CSNC). Singapore: Springer, 2018, pp.585–595.

11.

Simon

El-Sherief

. Navigation satellite selection using neural networks. Neurocomputing 1995; 7(3): 247–258.

12.

Azami

Sanei

. GPS GDOP classification via improved neural network trainings and principal component analysis. Int J Electron 2014; 101(9): 1300–1313.

13.

Chen

Huang

Lin

, et al. Applying geometric dilution of precision approximation to adaptive neural network learning for precise mobile station positioning. In: 2018 international conference on machine learning and cybernetics (ICMLC), Chengdu, China, 15–18 July 2018, pp.474–479. New York: IEEE.

14.

Milliken

Zoller

. Principle and operation of NAVSTAR and system characteristics. Navigation 1978; 25(2): 95–106.

15.

Mosavi

Divband

. Calculation of geometric dilution of precision using adaptive filtering technique based on evolutionary algorithms. In: 2010 international conference on electrical and control engineering, Wuhan, China, 25–27 June 2010, pp.4842–4845. Piscataway, NJ: IEEE Press.

16.

Tian

Zhang

, et al. A new satellite selection algorithm in GNSS. In: 2013 6th international conference on information management, innovation management and industrial engineering, Xi’an, China, 23–24 November 2013, pp.81–84. New York: IEEE.

17.

Peng

. Fast satellite selection method for multi-constellation global navigation satellite system under obstacle environments. IET Radar Sonar Navigation 2014; 8(9): 1051–1058.

18.

Wei

Wang

. A new satellite selection algorithm for real-time application. In: 2012 international conference on systems and informatics (ICSAI2012), Yantai, China, 19–20 May 2012, pp.2567–2570. New York: IEEE.

19.

Roongpiboonsopit

Karimi

. A multi-constellations satellite selection algorithm for integrated global navigation satellite systems. J Intell Transport S 2009; 13(3): 127–141.

20.

Zhang

. A fast satellite selection algorithm: beyond four satellites. IEEE J-ST SP 2009; 3(5): 740–747.

21.

Kong

Mao

. BDS/GPS satellite selection algorithm based on polyhedron volumetric method. In: 2014 IEEE/SICE international symposium on system integration, Tokyo, Japan, 13–15 December 2014, pp.340–345. New York: IEEE.

22.

Hsu

. Relations between dilutions of precision and volume of the tetrahedron formed by four satellites. In: Proceedings of 1994 IEEE position, location and navigation symposium (PLANS’94), Las Vegas, NV, 11–15 April 1994, pp.669–676. New York: IEEE.

23.

Blanco-Delgado

Duarte Nunes

Seco-Granados

. On the relation between GDOP and the volume described by the user-to-satellite unit vectors for GNSS positioning. GPS Solut 2017; 21(3): 1139–1147.

24.

Yuan

Zhuo

. Method of selecting GPS satellites and its test analysis. Chinese Inertial Technol 2008; 16(4): 445–447.

25.

Nie

Gao

Wang

, et al. A new method for satellite selection with controllable weighted PDOP threshold. Surv Rev 2016; 49: 1–9.

26.

Mosavi

. Applying genetic algorithm to fast and precise selection of GPS satellites. Asian J Appl Sci 2011; 4(3): 229–237.

27.

Waiming

Xiaoxuan

Wei

, et al. A two-phase genetic annealing method for integrated earth observation satellite scheduling problems. Soft Comput 2019; 23(1): 181–196.

28.

. Genetic programming for the approximation of GPS GDOP. In: 2010 international conference on machine learning and cybernetics, Qingdao, China, 11–14 July 2010, pp.2944–2949. New York: IEEE.

29.

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.

30.

Song

, et al. Multi-constellation star selection method based on genetic algorithm. J Astronaut 2015; 36(3): 300–308.

31.

Zarei

. Artifcial intelligence approaches for GPS GDOP classification. Int J Comput Appl 2014; 96(16): 16–21.

32.

Jwo

Lai

. Neural network-based GPS GDOP approximation and classification. GPS Solut 2007; 11(1): 51–60.

33.

Hamed

Mohammad-Reza

. Classification of GPS satellites using improved back propagation training algorithms. Wireless Pers Commun 2013; 71(2): 789–803.

34.

Zhang

Wang

Guo

. Research on combined model based on multi-objective optimization and application in time series forecast. Soft Comput 2019; 23: 11493–11521.

35.

Han

Qiao

, et al. Choosing the constellation layout of Chinese regional satellite positioning system. Chinese Sci: Series G 2008; 12: 1671–1686.

36.

Wang

Jiang

. Fast satellite selection algorithm based on satellite elevation angle and satellite contribution for geometry dilution of precision in GPS/BEIDOU. In: 37th China control conference, 25 July 2018, Wuhan, China, pp.4859–4862.

37.

Tang

Xia

. Time-optimized satellite selection algorithm in GPS navigation positioning. National Nannin, China: Computer Technology and Application, 2009.

38.

Wang

Huang

, et al. Analysis of optimal constellation selection for satellite positioning error. J Xi’an Jiaotong Univ 2007; 10: 86–89.

39.

Liu

Jin

Liu

, et al. A joint estimation algorithm of MUSIC multidimensional parameters based on Gibbs sampling. Sensor Microsyst 2008; 27(6): 62–65.

40.

Kuang

. Research on new method of motif finding based on Gibbs sampling algorithm. Chengdu, China: University of Electronic Science and Technology of China, 2007.

41.

Lim

Choi

Kim

, et al. Land vehicle positioning in urban area by integrated GPS/BeiDou/OBD-II/MEMS IMU. In: 2016 IEEE international conference on intelligent transportation engineering (ICITE), Singapore, 20–22 August 2016. New York: IEEE.

42.

Shi

, et al. The principle of the positioning system based on communication satellites Sci China G 2009; 52(3): 472–488.

43.

Shi

Zheng

Lou

. Research and evaluation of BDS real-time wide-area precise positioning service system. Acta Geodaetica Cartographica Sinica 2017; 46: 1354–1363.

44.

Lee

Sunwoo

. Fast GPS-DR sensor fusion framework: removing the geodetic coordinate conversion process. IEEE T Intell Transp 2016; 17(7): 2008–2013.

45.

Shi

Liu

. Detection on navigation deception signals based on INS and GNSS attitude measurement. In: Ninth China satellite navigation academic annual conference, Heilongjiang, China, 23 May 2018, pp.1–5.

46.

Geweke

Tanizaki

. Bayesian estimation of state-space models using the Metropolis–Hastings algorithm within Gibbs sampling. Comput Stat Data Anal 2001; 37(2): 151–170.

47.

Chen

Guo

Fan

, et al. An improved Gibbs sampling algorithm based on more accurate position weight matrices learned from sequence and gene expression/ChIP-chip data. Bioinformatics 2008; 24(9): 1121–1128.

48.

Jiang

Pan

Nan

, et al. Gibbs-sampling-based CRE bias optimization algorithm for ultradense networks. IEEE T Veh Technol 2017; 66(2): 1334–1350.

49.

Koltcov

Nikolenko

Koltsova

. Gibbs sampler optimization for analysis of a granulated medium. Tech Physics Lett 2016; 42(8): 837–839.