## Abstract

In the multi-GNSS era, the observable satellites are more than needed and the benefit of processing more than enough satellites is marginal. It is thus desired to select a subset of satellites so that the receiver operation complexity and navigation performance can be balanced. In the paper, performance requirements in navigation accuracy and integrity are represented in terms of a performance index and the performance-based satellite selection is to determine the satellite combination to minimize the performance index. A linear matrix inequality (LMI) relaxation approach is developed to solve the problem and render candidates of satellites. The proposed approach quantifies the significance of each satellite on the resulting performance metric and, more importantly, provides a lower bound in satellite selection for performance-based navigation. The generalizations of the proposed approach in multi-epoch satellite selection is also discussed. Examples are provided to illustrate the effectiveness of the proposed approach.

## 1 INTRODUCTION

In the multi-GNSS (global navigation satellite system) era, the number of navigation satellites from GPS, GLONASS, Galileo, BDS, QZSS, IRNSS, and so forth is more than one hundred (Kaplan & Hegarty, 2017; Morton et al., 2020). Yet, if all visible satellites are used in the navigation processing, the demands on the computational load and power consumption are high while improvement on performance is marginal. Thus, in practice, it is desired to investigate the issue of GNSS satellite selection with the aim of selecting a subset of satellites for navigation processing with little degradation on performance. The paper aims to provide a general formulation of the performance-based satellite selection problem and propose a numerically feasible method for the selection of satellites.

Many satellite selection methods have been investigated in the past. It is known that high elevation satellites are less susceptible to errors due to atmosphere and multipath, one may thus rank the satellites in terms of their elevations and pick some high elevation satellites for navigation. In contrast, the geometric distribution of satellites is another important factor to be considered in affecting the navigation performance. As the navigation error is typically expressed as a product of the dilution of precision and user equivalent range error (Parkinson, 1996), the geometric dilution of precision (GDOP) or its variations such as the position dilution of precision is often employed as a criterion in satellite selection. Indeed, as the GDOP serves as an amplification factor in relating ranging error to navigation error, based on the GDOP consideration, some low elevation satellites may be included to enhance the geometric strength and numerical condition in navigation processing. The GDOP is known to be inversely proportional to the volume of the tetrahedron formed by the ends of unit user-to-satellite vectors (Hsu, 1994; Yarlagadda et al., 2000). Consequently, the subset of satellites can be determined by maximizing the tetrahedron/polyhedron volume (Kihara & Okada, 1984) or the convex hull (Balanco-Delgado & Nunes, 2010a) formed by the observation vectors. Alternatively, the concept of the optimal geometric distribution of satellites can be adopted to shed light on the selection of satellites (Zhang & Zhang, 2009). One can also examine the angles of pair-wise observation vectors to scrutinize the satellites for removal (Park & How, 2001; Phatak, 2001; Liu et al., 2009; Wei et al., 2012). Some variations of the above concepts have been discussed by Roongpiboonsopit and Karim (2009) and Swaszek et al. (2017).

The selection approaches can be categorized as either combinatorial or iterative. The brute force method is to perform an exhaustive search to examine every combination. Such a method leads to the optimal configuration at the expense of search time. To avoid the complexity in the combinatorial search, many heuristic and iterative procedures have been proposed. Essentially, there are two types of iterative procedures in GNSS satellite selection: one is the constructive paradigm and the other is the reductive paradigm. The former attempts to include some satellites to the selection list that enhances the performance while the latter aims to remove some satellites from a candidate list with a graceful degradation of performance. In the recursive approach, the reductive paradigm is often preferred since the all-in-view covariance matrix is typically nonsingular and, as a result, numerical stability can be better maintained. Among these reductive schemes, the so-called greedy algorithm which performs removal one-at-an-iteration is often used as the matrix inversion can be simplified through the Schur complement technique. In comparison, the inclusive paradigm often starts with a four-satellite configuration that corresponds to the maximum volume.

More recently, as satellites from multiple constellations may be brought to bear and the error characteristics of different constellations and satellites may not be similar, a weighted GDOP is adopted as a criterion in satellite selection (Balanco-Delgado & Nunes, 2010b; Nie et al. 2016; Sairo et al., 2003). As satellite selection is also deemed important in integrity monitoring, criteria such as the vertical protection level, horizontal protection level, or their weighted combination have been investigated by Walter et al. (2016) and Meng et al. (2015). Finally, some evolutionary learning methods have been proposed for satellite selection (Simon & El-Sherief, 1995; Xia et al., 2020).

In the paper, the GNSS satellite selection problem is tackled through a rigorous formulation and a numerically feasible approach. The main contributions are

Navigation performance is often measured in terms of accuracy, integrity, continuity of service, and availability (Kaplan & Hegarty, 2017). It is shown that navigation accuracy in terms of mean squared error and integrity in terms of an upper bound on the protection level can be characterized by a performance metric that is affected by satellite distribution and measurement error characteristics, leading to a general satellite selection formulation.

The performance-based satellite selection problem is formulated as an optimization problem in which a 0/1 vector that dictates the selection of satellites is to be determined.

A semi-definite relaxation or linear matrix inequality (LMI) relaxation approach is developed to render a computationally feasible procedure. More exactly, the search space is relaxed from a 0/1 integer vector to a bounded real vector. As a result, the satellite selection problem is formulated as an optimization problem with a linear objective function and subject to LMI constraints. The optimization problem becomes a semi-definite program (Boyd et al., 1994; Vandenberghe & Boyd, 1996) and can be solved efficiently as the problem is of polynomial complexity and methods such as the interior point method (Nesterov & Nemirovsky, 1994; Wright, 1997) can be used.

Solving the semi-definite programming problem results in a real score vector that represents the significance of each satellite on the performance metric. This score vector reveals some insights for the selection of satellites.

In addition to providing candidates for the selection of the subset of satellites, the LMI relaxation approach results in a lower bound on the objective function. Such a low bound which appears to be new in the satellite selection literature characterizes the achievable performance for a given number of satellites in theory. In contrast, existing methods render a set of satellite candidates without knowing the discrepancy between the achievable and achieved performance. Alternatively, the LMI-based method can be formulated to reveal the information on the minimal number of satellites that are needed to provide a level of assured navigation performance.

It is shown that the proposed relaxation approach can be generalized to multi-epoch satellite selection to balance the navigation performance and implementation complexity. The latter addresses not only the number of satellites but also the frequency of switching from one epoch to another. It is shown that the LMI-based approach can be generalized to take multi-epoch observations into accounts so that the issue of channel re-allocations in the receiver can be addressed.

The remaining of the paper is organized as follows. In Section 2, the GNSS satellite selection problem is formulated as an optimization problem which considers the effects of satellite distributions, measurement error characteristics, and the desired performance aims. In Section 3, an LMI-based approach is developed to address the optimization problem. The properties of the proposed method are discussed. A generation of the satellite selection approach to account for observations at multiple epochs is then presented. Simulation examples are provided in Section 4 to illustrate the design approaches. In Section 5, concluding remarks are given.

## 2 GNSS SATELLITE SELECTION: PROBLEM FORMULATION

In this section, the GNSS satellite selection problem is discussed. The performance metric on navigation performance about accuracy and integrity is first described. The satellite selection problem is then formulated in which the effect of the selection process on the performance metric is depicted.

### 2.1 Performance Metric

Let *m* be the number of GNSS constellations under consideration and *n* be the number of observable satellites. The linearized multi-GNSS positioning equations for the determination of position and time can be formulated as follows (Kaplan & Hegarty, 2017; Misra & Enge, 2006)

1

where ** y** is the pseudo-range measurement vector of dimension

*n*,

**is the position vector of dimension 3,**

*x***is the receiver clock bias vector of dimension**

*b**m*,

**is the measurement noise vector of dimension**

*v**n*,

**is the**

*H**n*× 3 observation matrix, and

**is the**

*L**n*×

*m*clock association matrix. The

*i*-th row of the observation matrix

**is the unit-length vector from the**

*H**i*-th satellite to the receiver. In contrast, the

*i*-th row of the clock association matrix

**is the unit vector of dimension**

*L**m*in which the

*j*-th entry is 1 if this measurement is associated with the

*j*-th constellation. Suppose that the measurement noise

**is of zero mean with covariance matrix**

*v***, then the minimal variance estimate of the unknown position and clock bias vectors for the linear model Equation (1) is given by (Mendel, 2008)**

*R*2

where ** G** = [

**] is the design matrix. Define the position estimation error as and clock estimation error as , then by substituting Equation (1) into Equation (2), the estimation error is given by and the error covariance matrix becomes where E{∘} stands for the expectation operator (Mendel, 2008). Consequently, the mean squared error is given by:**

*H L*3

where trace stands for the trace of a matrix which is the summation of all diagonal elements of the matrix.

In the paper, the following performance metric which is a weighted combination of the estimation errors is considered.

4

In this performance metric Equation (4), * Q_{x}* and

*are positive semi-definite matrices which are selected to reflect the performance requirements on different components of the position estimation error and clock estimation error. Let*

**Q**_{c}*and*

**C**_{x}*be factors that are obtained from*

**C**_{c}*and*

**Q**_{x}*, respectively, through Cholesky factorization or singular value decomposition such that and (Strang, 2016). Then, it can be shown that the performance metric in Equation (4) can be expressed as:*

**Q**_{c}5

where . Further, let ** W** be a matrix that satisfies

*R*^{−1}=

*W*^{T}

**, the performance metric in Equation (5) becomes:**

*W*6

In the above performance metric, the matrix ** W** is governed by the noise covariance matrix, the matrix

**is related to the distribution of satellites, and**

*G***is used to reflect the performance requirement.**

*P*It is remarked that in the special case when both ** P** and

**are identity matrices, the performance metric Equation (6) is indeed the square of the GDOP. The use of**

*W***and**

*P***allows a more flexible design formulation for performance assessment. For example, by setting**

*W***as the identity matrix, i.e.,**

*P***=**

*P**, and adjusting*

**I****to represent measurement errors, the performance metric Equation (4) or Equation (6) is the same as the mean squared error Equation (3). Methods for the selection of**

*W***or**

*W***can be found in Misra and Enge (2006), Tiberius (1999), and Walter and Enge (1995). For simplicity, it is hereafter assumed that covariance matrix**

*R***is a positive definite diagonal matrix as for some variances . Thus, the matrix**

*R***is given as . In contrast, the matrix**

*W***is generally at the disposal of the user in quantifying the desired navigation performance. For example, if the timing accuracy is to be assessed, then one can set**

*P**= 0 and*

**C**_{x}*=*

**C**_{c}*. On the other hand, if the position estimation error is of interest and the position vector is coordinated in the east-north-up (ENU) frame, then by setting*

**I***as the zero matrix, the performance metric becomes:*

**C**_{c}7

Where , and are the variances along the east, north, and up directions, respectively. The variables , and in Equation (7) are cross-covariance terms. Clearly, one can then specify the matrix * C_{x}* for the desired positioning accuracy in the ENU frame.

In the sequel, we will adopt concepts in matrix inequality to bound the performance matrix. It can be shown that the performance metric Equation (6) is bounded as follows:

8

for any matrix ** M** that satisfies:

9

The notation is interpreted in the sense of matrix definiteness. That is, Equation (9) implies that the matrix * M*–

*P*^{T}(

**G**^{T}

*W*^{T}

**)**

*WG*^{−1}

**is a positive semi-definite matrix (Strang, 2016). In Equation (9), the matrix**

*P***is unstructured and trace(**

*M***) is an upper bound on the performance metric. In the optimization problem or satellite selection, the matrix**

*M***serves as a parameter matrix in the search space. In GNSS RAIM (receiver autonomous integrity monitoring), a performance metric is given by (Walter et al., 2016):**

*M*10

where HPL and VPL are horizontal protection level and vertical protection level, respectively. The VPL is related to through VPL = *K _{v}σ_{u}* where

*K*depends on the integrity risk. Also, the HPL which is the radius of a circle in the horizontal plane that bounds the navigation solutions can be computed as HPL =

_{v}*K*where

_{h}λ*K*is a function of the allocated integrity risk and λ is the semimajor axis of the error ellipse which is indeed the minimal λ such that . From Equation (7), this implies that the integrity requirement can be achieved by finding

_{h}**of the form for some**

*M**m*

_{1}and

*m*

_{3}such that trace(

**) ≥ J**

*M*_{RAIM}with .

In summary, the performance metric Equation (6) is a general term in representing the performance in satellite navigation. It characterizes the navigation accuracy and, through the argument of inequality, it also governs the navigation integrity. The matrix ** P** and, to some extent, the matrix

**can be specified to reflect the performance on position error, clock error, and integrity.**

*W*### 2.2 Satellite Selection Problem

In the multi-GNSS era, there are abundant satellites that can be observed. In practice, if all satellites in view are used, the receiver is subject to a high computational load and power consumption. Thus, it is desired to have a satellite selection scheme to process only a subset of the observable satellites. Let *k* be the number of satellites to be selected from *n* satellites in view. Define as the set of diagonals, 0/1 integer *n* × *n* matrices with *k* elements of 1. A matrix ** s** in the set

**S**can be used to characterize the selection scheme through

11

A selection matrix ** s** in

**S**is called an admissible matrix. The selection can also be characterized in terms of a set that contains the indices of the satellites that are selected. In this case, the selection set

**is defined as**

*s***= {**

*s**i*|

*s*= 1}. Further, one can define as the complement of

_{i}**, that is, . Under the selection**

*s***or**

*S***, the part of the measurement Equation (1) that is processed becomes**

*s***=**

*Qy***+**

*QHx***+**

*QLb***where**

*Qv***is a**

*Q**k × n*matrix that contains non-zero rows of

**. Note that the covariance matrix of the equivalent noise**

*S***is**

*Qv**and the resulting minimum variance estimate is given by:*

**QRQ**^{T}12

The matrices *Q*^{T}(*QRQ*^{T})^{−1}** Q** and

*W*^{T}

**are identical because both are diagonal matrix and their (**

*SW**i*,

*i*)-th elements are if

*s*is 1 and become 0 if

_{i}*s*is 0. This implies that the covariance matrix of the estimation error (

_{i}

*G*^{T}

*Q*^{T}(

*QRQ*^{T})

^{−1}

**)**

*QG*^{−1}can be expressed as (

*G*^{T}

**W**^{T}

**)**

*SWG*^{−1}and, consequently, the performance metric under satellite selection becomes:

13

The above equation exhibits the relationship between the selection matrix ** s** and the performance metric. Clearly, if all satellites are used, then

*J*in Equation (13) is the same as

_{s}*J*in Equation (6). The satellite selection problem thus aims to determine the selection matrix

**so that the performance metric Equation (13) is minimized. More exactly, given**

*s***,**

*G***, and**

*P***, the satellite selection problem is formulated as:**

*W*14

It is remarked that a brute force method in tackling the problem Equation (14) is to perform an exhaustive search for all admissible ** s**. The number of elements in the set

**S**or the number of candidates to be searched is which can be significant when

*n*is large. For example, if

*n*= 30 and

*k*= 12, then the number of candidates is 86,493,225. Therefore, an exhaustive search is deemed not practical. In the next section, an LMI-based method is proposed.

## 3 LMI-BASED SATELLITE SELECTION

In the section, the GNSS satellite selection problem Equation (14) is reformulated in terms of a matrix inequality that is linear on the unknown and a relaxation technique is then used to cast the satellite selection problem as a semi-definite programming problem. In Section 3.1, the single epoch satellite selection is discussed. The properties of the proposed method and resulting solutions are elaborated. As many existing satellite selection methods are iterative, the LMI-based method is then re-stated as an iterative method in Section 3.2. Some remarks on the comparisons with the existing methods are made. In Section 3.3, another extension of the LMI-based method is presented to account for the processing of measurements at multiple epochs.

### 3.1 Single Epoch Satellite Selection

Recall that the satellite selection problem is formulated as the determination of an admissible ** S** such that the performance metric is minimized. In the following, in addition to

**, an upper bound of the performance metric is also considered in the satellite selection process. More precisely, the satellite selection problem in Equation (14) is stated as the determination of an admissible**

*S***and a matrix**

*S***so that trace(**

*M***) is minimized subject to the following condition:**

*M*15

Through the Schur complement technique (Boyd et al., 1994), the matrix inequality Equation (15) can be rewritten as:

16

Even though the dimension of the underlying matrix is increased, Equation (16) is beneficial in two aspects: the matrix inversion operation is removed and, more importantly, the matrix inequality is linear on the unknown matrices ** S** and

**. One can then state the satellite selection problem as follows:**

*M*17

subject to Equation (16).

The problem Equation (17) involves a linear objective function and linear constraints of the unknowns. Yet, the fact that the selection matrix ** s** is a 0/1 integer matrix remains difficult to deal with when

*n*is large. To account for the problem, define to represent any real diagonal matrix whose diagonal elements are bounded between 0 and 1 and the summation of the diagonal elements is not greater than

*k*. The set

**U**is a relaxation of

**S**as any matrix

**in**

*s***S**is also an element of

**U**. It is noted that

**S**is a discrete set while

**U**is a real convex set. Note that the diagonal elements of the selection matrix

**are the vertices of an**

*s**n*-dimensional hypercube. In contrast, the diagonal elements of the matrix

**U**are in a convex set of the

*n*-dimensional hypercube that is further subject to a linear or hyperplane constraint due to trace(

**)≤**

*U**k*. Figure 1 illustrates the two sets

**S**and

**U**for

*n = 3*and

*k = 2*. The set

**S**contains the three vertices in red while the set

**U**is the hypercube that is bounded by the shaded plane. Through the relaxation, instead of finding a 0/1 integer matrix

**, a real diagonal matrix**

*s***is determined.**

*U*The LMI relaxation approach for satellite selection is thus be stated as follows. Given the design matrix ** G**, the projection matrix

**, and the weighting matrix**

*P***, find**

*W***and**

*M***so as to**

*U*18

subject to

19

Note that the constraints in the above, ** U** ∈

**and Equation (19), are linear on the unknowns and the objective function in Equation (18) is a linear function of the unknown**

*U***. Thus, the problem is a semi-definite program. A semi-definite programming problem involves the optimization of a linear function subject to LMI constraints. The semi-definite programming problem can be solved efficiently due to the convexity in the optimization problem, the polynomial complexity, and the existence of solution approaches such as the interior point method (Boyd et al., 1994; Vandenberghe & Boyd, 1996). Thus, the proposed LMI relaxation method is numerically feasible for satellite selection. A software tool that can be used to solve the problem is Matlab LMI toolbox (Gahinet et al., 1995). It is also remarked that the above formulation can be easily generalized to problems in which the matrix**

*M***is structured as discussed previously for performance metric in Equation (10). Imposing a constraint on**

*M***does not introduce difficulties as far as the solution approach is concerned.**

*M*Let ** U*** and

*** be the optimal arguments of Equation (18). One can then determine the selection matrix from by a sorting process or ranking operation. The value reveals insights of the satellite selection problem and can indeed be regarded as a score in quantifying the significance of the**

*M**i*-th satellite on the overall performance metric. If is close to 1, then the inclusion of the

*i*-th satellite in the selection list may enhance the information content, thereby reducing the performance metric. Conversely, a small means that the corresponding satellite is less significant. Hence, the selection matrix can be obtained by setting as 1 if is among the leading

*k*elements. In addition to ranking, one can collect a subset of candidates based on the scores and perform an in-depth search accordingly. For example, if

*n*= 30 and

*k*= 12, one can pick the top 15 satellites from

*** after solving Equation (18). Afterwards, an exhaustive search is performed and the number of candidates in this search is 455, which is manageable.**

*U*Once the selection matrix ** S*** is determined, the performance level can be assessed as in view of Equation (13). Therefore, by solving the LMI optimization problem Equation (18), two performance levels can be obtained. The first is the optimal trace(

***) and the other is the performance level . As an admissible**

*M***belongs to the set of**

*s***U**, one can infer that the optimal performance by any admissible selection matrix satisfies the following inequalities:

20

Thus, the proposed LMI relaxation method provides both lower and upper bounds of the optimal configuration. The lower bound reveals the achievable performance in theory and the upper bound renders an attainable performance by using the selection ** S***. Figure 2 depicts this situation when the problem is solved for different

*k*so that the lower and upper bounds are obtained. The curves are illustrated as continuous in the figure for simplicity. For a specified number of satellites, the solving of Equation (18) results in a lower bound and the ranking of the solution yields an upper bound. The optimal performance metric versus number of satellites curve is bounded by the two curves. It is reminded that the optimal curve is computationally demanding to obtain. Existing satellite selection methods typically render a performance metric vs number of satellites that is over the optimal curve. In practice, no information is available about the difference between the performance of the selected configuration and the optimal performance. The LMI-based method yields a lower bound in the solution process and this lower bound reveals the discrepancy between the attainable performance and the theoretic optimal performance.

The performance metric is a monotonically non-increasing function of the number of satellites as illustrated in Figure 2. A variation of Equation (18) can be formulated to assess the relationship from a different perspective. It is desired to find the minimal number of satellites that can render a prescribed performance level. Let *γ*^{2} be the bound on the performance metric and , the problem can be cast as a semi-definite program:

21

subject to Equation (19) and

22

Once the problem is solved, it is claimed that the number of satellites that is required to yield the performance level must be greater than or equal to trace(** U**). This solution of the problem Equation (21) is also marked in Figure 1. The information is useful in channel allocation in GNSS receiver operation.

### 3.2 Iterative Methods

The selection of satellites is often accomplished through an iterative procedure in trading off performance and complexity. Assume that the selection set ** s** contains

*n*distinct elements and it is desired to include additional

_{s}*I*satellites to the selection set. Let

**be the**

*W*_{s}*n*concatenation of the rows of

_{s}× n**that are indexed in**

*W***and be the (**

*s**n*–

*n*) ×

_{s}*n*matrix that contains the rows of

**that are indexed in the complementary set . Each step in the iterative procedure can be formulated as the determination of**

*W***and so as to minimize trace(**

*M***) subject to 0≤**

*M**u*≤1, trace(

_{i}**)≤**

*U**I*, and:

23

In the above, the scalar *I* serves as a bound on the satellites to be included in the iteration step. If the number of satellites to be selected is prescribed as *k*, then the scalar *I* should be bounded by *k*–*n _{s}*. Note that for the problem Equation (18), the unknown matrix

**contains**

*U**n*variables to be determined. In contrast, the number of unknown variables of the matrix

**in the above iteration step is**

*U**n*–

*n*. Based on the above discussions, an iterative approach for GNSS satellite selection is devised as follows.

_{s}Initialize the selection set

as the empty set.*s*Determine the complementary set and find the corresponding

and .*W*_{s}Solve the LMI problem by finding

and where*M**n*is the cardinal number of_{s}such that trace(*s*) is minimized subject to 0 ≤*M**u*≤ 1, trace(_{i}) ≤*U**I*, and Equation (23).Select some satellites from based on the optimal

*u*and update the selection set_{i}.*s*If the cardinal number of

is*s**k*, exit; otherwise, go to Step 2.

The iterative procedure allows an incremental buildup of the selection set. One can initialize the procedure with an empty selection list since numerical problem associated with matrix inversion is alleviated. Alternatively, methods such as Kihara and Okada (1984), Hsu (1994), Yarlagadda et al. (2000), and Balanco-Delgado and Nunes (2010a) can also be used to initialize the iteration. In this procedure, the optimization in Step 3 can be accomplished by using efficient semidefinite programming tools. In contrast, Step 4 attempts to select some satellites from the complementary set based on the score *u _{i}*. There are several options that can be employed through ranking, thresholding, or their combination. As mentioned before, one can sort

*u*, and select a certain number, say

_{i}*I*, of satellites from the leading indices. Alternatively, one can compare

*u*against a threshold and the corresponding satellite is selected if

_{i}*u*is greater than the threshold. The threshold can be priori specified. It is also remarked that the gap between the sorted

_{i}*u*can be used to facilitate the determination of the threshold. Further, the selection of satellites can be made by combining the relative order of

_{i}*u*and absolute value of

_{i}*u*. As the average value of

_{i}*u*is , the threshold is advised to be between and . Such a strategy will guarantee that at least one additional satellite is selected so that the overall procedure will converge in finite iterations.

_{i}Alternatively, one may start with all satellites-in-view and de-select some satellites progressively. Such an arrangement implies that the number of unknown variables in the LMI problem is reduced in each iteration. More precisely, let ** c** be the candidate set that contains

*n*elements and the goal is to de-select

_{c}*I*satellites from the set while the performance is not degraded too significantly. Let

*be the*

**W**_{c}*n*concatenation of the rows of

_{c}× n**that are indexed in**

*W***, the problem can thus be formulated as the determination of**

*c***and so as to:**

*M*24

subject to:

25

In the problem Equation (24), the matrix ** U** is

*n*diagonal matrix that satisfies 0 ≤

_{c}× n_{c}*u*≤ 1 and trace(

_{i}**) ≥**

*U**n*. This allows the removal of

_{c}– I*I*satellites in one iteration. Note that if the number of satellites to be removed in each iteration is one, then the matrix

**can be expressed as where**

*U**is the unit vector in which the*

**e**_{i}*i*-th entry is one and the other entries are zeros. Based on the matrix inversion lemma, it is known that:

26

The satellite to be removed can then be determined by evaluating and ranking the second term on the right-hand side of Equation (25) for each * e_{i}*. This one-at-an-iteration approach is termed as the greedy algorithm or greedy reduction. Both the greedy reduction and LMI reduction in Equation (24) reveal that the performance metric is increased by removing satellites, making it possible to trade-off between performance metric and number of satellites in an explicit manner. There are, however, two fundamental distinctions between the two methods. In the greedy reduction method, the search space is constrained to be some vertices of the

*n*dimensional hypercube constituted by

_{c}**. The search space of the LMI reduction method is typically a hypersurface that contains the vertices. As for the solutions, the LMI reduction results in an**

*U**n*dimensional vector with entries bounded between 0 and 1 that entails the significance of each satellite while the greedy reduction simply yields a 0/1 vector with no additional quantitative information.

_{c}### 3.3 Multi-Epoch Satellite Selection

One stated objective of satellite selection is to reduce the number of satellites to be processed to save computational load and power consumption. In practice, the reduction of the number of satellites is often accompanied by the fact that low elevation satellites are more likely to be selected, which, in turn, implies that the receiver may be subject to frequent switching between different optimal configurations. Indeed, existing GNSS satellite selection approaches are typically epoch-based, which may result in frequent switching of satellites between different epochs. It is thus desired to find a satellite selection scheme that works for some consecutive epochs without compromising too much on the worst-case performance metric. The proposed LMI relaxation technique can be generalized to account for this multiple epoch satellite selection problem. Let * G_{t}*,

*, and*

**P**_{t}*be the design matrix, projection matrix, and weighting matrix at epoch*

**W**_{t}*t*, respectively. Then, the multiple epoch satellite selection problem can be stated as the finding of a set of

*M**, a real selection matrix*

_{t}**, and a scalar**

*U**γ*

^{2}as follows:

27

subject to:

28

29

The above optimization problem involves more unknown variables and more constraints. Yet, it can still be solved by using semi-definite programming tools. The resulting bound *γ*^{2} is an upper bound on the performance metric at each and every epoch.

## 4 SIMULATION ANALYSES

In the section, simulation examples are provided to illustrate the proposed LMI-based techniques in GNSS satellite selection.

### 4.1 Example 1

In the first example, a three-constellation satellite selection problem is considered. The receiver is located at Tainan, Taiwan and the almanacs of GPS, Galileo, and Beidou satellites on August 2, 2022 are used to form the design matrix ** G**. Figure 3 depicts the sky plot of the satellites at one epoch in which nine GPS satellites, five Galileo satellites, and 24 Beidou satellites are observed. The total number of observable satellites is 38. In this example, both

**and**

*W***are assumed to be the identity matrices. Thus, the satellite selection problem is the minimal GDOP problem. Four approaches are considered in the following. The first approach is the exhaustive search method in which each and every combination is examined to assess the performance. The configuration that corresponds to the minimal performance metric is selected. This method is known to be time consuming; yet, it establishes the optimal achievable performance level for benchmarking. The optimal performance as a function of the number of satellites is depicted in Figure 4. The second approach is based on the LMI relaxation technique. With respect to different**

*P**k*, the optimization problem Equation (18) is solved to render the optimal performance of trace(

***) and the matrix**

*M****. Consequently,**

*U**k*satellites are selected by sorting the elements of

*** to give the corresponding selection matrix**

*U****. In actuality, the second approach leads to two performance curves as a function of**

*S**k*, one is trace(

***) which is labeled as ‘LMI’ and the other is which is labeled as**

*M**LMI*+

*ranking*. The third and fourth methods are the iterative methods discussed in Section 3.2. The iteration begins with all satellites in view and gradually reduces the number of satellites. Both the LMI-based reduction method and the so-called greedy reduction method are applied and the results are also depicted in Figure 4. It is clearly observed that the LMI-based approach yields a lower bound on the performance curve. This lower bound is close to the optimal one when the number of satellites being selected is high,

*k ≥ 15*in this case. In contrast, there may exist some discrepancy between the lower bound and the optimal performance through exhaustive search when

*k*is small. The LMI+ranking, LMI reduction, and greedy reduction approaches provide satellite selection sets that can be used in the receiver. When the number of satellites is large, the performance of these three methods is relatively close. In this example, the LMI reduction method appears to outperform the other two methods when

*k*is small.

To better assess the LMI-based method Equation (18), the optimized ** U***, the assigned

***, and the optimal selection configuration at different**

*S**k*are illustrated in Figures 5, 6, and 7. In each row of these figures, satellites of the optimal selection configuration are illustrated in terms of blue bars, the scores due to

*** are illustrated in terms of red bars, selected satellites of the LMI reduction are depicted in terms of yellow bars, and the indices of the corresponding**

*U**** are labeled under the horizontal axis. Thus, when**

*S**k*is 6, the optimal configuration is characterized by the satellites with identification numbers 5, 6, 11, 14, 22, and 31. The satellite identification numbers from the LMI-based method are 3, 6, 11, 14, 22, and 27. Also, the LMI reduction method yields the following satellite identification numbers: 3, 6, 11, 14, 22, and 27, which are the same as those of the LMI-based method. In general, there is a high degree of similarity between the optimal selection configuration and

***. A closer examination also reveals that as**

*S**k*varies, the selection

*** does not experience a significant variation. In comparison, the exhaustive search may lead to abrupt change of satellites. Finally, it is noted from Figures 6 and 7 that for**

*S**k*at 19 or larger, the three approaches result in the same satellite list.

### 4.2 Example 2

The second example considers the satellite selection for integrity in which the performance metric in Equation (10) is adopted. Figure 8 depicts the number of satellites for a duration of 12 hours at Tainan, Taiwan on August 2, 2022. The number of observable GNSS satellites including GPS, QZSS, Galileo, Beidou, and GLONASS satellites varies. The GNSS measurement errors are modeled as discussed in (Misra & Enge, 2006) in which ephemeris error, clock error, receiver noise, multipath effect, ionospheric error, and tropospheric error are considered. The variances of ionospheric and tropospheric errors depend on the elevation angle and appropriate mapping functions Misra and Enge (2006) are used in the analysis. Based on the ephemeris and the error model, the matrices * G_{t}* and

*at different epochs for the application of single and multiple epoch satellite selection are determined. The matrices*

**W**_{t}**are the same at different epochs with its submatrix and the variables**

*P*_{t}*K*and

_{h}*K*are 5.33 and 6, respectively (Walter, Blanch & Kropp, 2016). The single-epoch approach solves Equation (18) at every two-minute epoch. The multi-epoch approach catenates the data and solve Equation (24) to determine the satellite list at an interval of half an hour or 15 epochs. Figure 9 depicts the performance metrics as a function of time when the number of selected satellites is 20.The performance of the multi-epoch approach is slightly inferior to that of the single-epoch approach. In the subplots of the figure, the instants at which there are satellite changes or switches are depicted as vertical bars. The number of switches of the multi-epoch approach is 24 while that of the epoch-based approach is 227. The single-epoch approach leads to more frequent switches. The example also demonstrates that the LMI relaxation approach can be used in trading-off performance and number of switches.

_{v}## 5 CONCLUSION

The paper formulates the GNSS satellite selection problem as a combinatorial optimization problem that depends on the satellite distribution, measurement error characteristics, and performance aim. An LMI relaxation technique is developed to tackle the problem and it is shown that the problem can indeed be regarded as an optimization of the linear function that is subject to LMI constraints. By using semi-definite programming tools, the problem can be solved efficiently. The LMI relaxation approach provides scores about the contribution of satellites on the performance metric and satellites can be selected accordingly. Moreover, both upper and lower bounds can be obtained for satellite selection and performance assessment. The generalization of the LMI relaxation approach for multi-epoch satellite selection is also discussed. It is believed that the proposed approach brings a more rigorous treatment of the satellite selection problem and will be beneficial in multi-GNSS navigation and performance assessment.

## HOW TO CITE THIS ARTICLE

Juang, J-C. (2023). performance-based GNSS satellite selection: A linear matrix inequality (LMI) approach. *NAVIGATION, 70*(2). https://doi.org/10.33012/navi.582

## ACKNOWLEDGMENTS

The research is supported by the Ministry of Science and Technology (MOST), Taiwan under grant MOST 111-2221-E-006-218-MY2.

This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.