Integer estimation methods for GPS ambiguity resolution: an applications oriented review and improvement

The integer least squares (ILS) problem, also known as the weighted closest point problem, is highly interdisciplinary, but no algorithm can find its global optimal integer solution in polynomial time. We first outline two suboptimal integer solutions, which can be important either in real time communication systems or to solve high dimensional GPS integer ambiguity unknowns. We then focus on the most efficient algorithm to search for the exact integer solution, which is shown to be faster than LAMBDA in the sense that the ratio of integer candidates to be checked by the efficient algorithm to those by LAMBDA can be theoretically expressed by r(m) where r <= 1 and m is the number of integer unknowns. Finally, we further improve the searching efficiency of the most powerful combined algorithm by implementing two sorting strategies, which can either be used for finding the exact integer solution or for constructing a suboptimal integer solution. Test examples clearly demonstrate that the improved methods can perform significantly better than the most powerful combined algorithm to simultaneously find the optimal and second optimal integer solutions, if the ILS problem cannot be well reduced.