GPS fast constellation selection based on 3-SAT subset

A fast constellation selection method named '3-SAT subset' is presented for reducing the large amount of computation when a sudden change occurs in the sky view in high-accuracy GPS navigation system. The GDOP (Geometric Dilution of Precision) recursive formula is deduced by use of the Sherman-Morrison formula to reduce matrix inversion operation. Moreover, efficient storage and search strategy of LLRB-Tree (Left Leaning Red-Black Tree) algorithm is used to assist rapid creation of optimal 4-SAT combinations and get the minimal GDOP. With respect to the traditional GDOP constellation selection, the amount of floating-point operations per second (FLOPs) can be reduced by more than half when the number of visualization satellites increases, and almost equals 0 when the number decreases. The experimental results show that, 3-SAT subset method can effectively reduce the time consumption at the mutation of constellations and improve the real-time performance accordingly.