A Convex Optimization Approach to Satellite Selection for Global Navigation Satellite System (GNSS) Receivers

Abstract

This paper presents a new approach to satellite selection for Global Navigation Satellite System (GNSS) receivers. With the advent of a large number of navigation satellites, it is desirable for GNSS receivers to have efficient means of selecting an optimal subset (from ones in view) to compute a position solution. A principled approach using a formulation closely related to the theory of optimal experiment design is demonstrated. The resulting problem is a Boolean optimization problem which has combinatorial complexity. Convex relaxation is used to reduce this complexity and frame the problem as one of semidefinite programming (SDP), which is a convex optimization problem. In almost all cases considered in the experiments, the proposed method provides selections that are exactly the same as that of the best possible selections found by brute force search. Computational times for the proposed technique are in the order of tens of milliseconds regardless of subset size. Furthermore, the present approach is extensible in that it can accommodate constraints depending on the application at hand or on prior knowledge. The method is illustrated on a real-world multi-constellation GNSS dataset.