Fast Multi-Constellation GNSS Satellite Selection: Convex and Mixed-Integer Programming Approaches

A set of fast optimization-based procedures for the selection of an optimal subset of satellites from those within view of a receiver is provided. Resource limitations, the low marginal utility of using an all-in-view navigation solution, and the need for solution separation procedures in safety-critical navigation systems necessitate the use of a smaller subset from a collection of visible satellites. The goal of the present research is the fast selection of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> satellites from among <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$m$</tex-math></inline-formula> that are available such that the selection is maximally informative (having minimum covariance measure) of user position. With many GNSS satellites currently deployed and more than four satellites required for integrity monitoring purposes, brute-force search through all <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{m}C_{k}$</tex-math></inline-formula> options is not a reasonable approach. Satellite geometry and measurement precision are essential metrics in satellite selection; however, much of the literature on this topic has focused on geometry alone. In this work, we jointly account for satellite geometry and measurement precision in a single optimization framework. We present a semidefinite programming (SDP) formulation that considers both geometry and measurement quality. Afterward, we provide a reduction of the SDP form to that of a second-order cone program (SOCP). The SOCP formulation yields significant speed improvements while providing the same solution as the SDP form. Furthermore, we demonstrate exact satellite selection using a mixed-integer SOCP formulation, a first in the literature. Additionally, we show how context-specific constraints for GNSS can be easily incorporated into our selection framework. To illustrate the proposed set of methods, experiments are conducted on real-world multi-constellation GNSS data from GPS, GLONASS, BeiDou, Galileo, and QZSS satellites. For a comparative perspective, we offer an efficient greedy search technique, a genetic algorithm, a globally optimal exhaustive search (where applicable), and an all-in-view strategy.