Abstract
GNSS ambiguity resolution is the key issue in the high-precision relative geodetic positioning and navigation applications. It is a problem of integer programming plus integer quality evaluation. Different integer search estimation methods have been proposed for the integer solution of ambiguity resolution. Slow rate of convergence is the main obstacle to the existing methods where tens of ambiguities are involved. Herein, integer search estimation for the GNSS ambiguity resolution based on the lattice theory is proposed. It is mathematically shown that the closest lattice point problem is the same as the integer least-squares (ILS) estimation problem and that the lattice reduction speeds up searching process. We have implemented three integer search strategies: Agrell, Eriksson, Vardy, Zeger (AEVZ), modification of Schnorr–Euchner enumeration (M-SE) and modification of Viterbo-Boutros enumeration (M-VB). The methods have been numerically implemented in several simulated examples under different scenarios and over 100 independent runs. The decorrelation process (or unimodular transformations) has been first used to transform the original ILS problem to a new one in all simulations. We have then applied different search algorithms to the transformed ILS problem. The numerical simulations have shown that AEVZ, M-SE, and M-VB are about 320, 120 and 50 times faster than LAMBDA, respectively, for a search space of dimension 40. This number could change to about 350, 160 and 60 for dimension 45. The AEVZ is shown to be faster than MLAMBDA by a factor of 5. Similar conclusions could be made using the application of the proposed algorithms to the real GPS data.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agrell E, Eriksson T, Vardy A, Zeger K (2002) Closest point search in lattices. IEEE Trans Inf Theory 48: 2201–2214
Babai L (1986) On Lováasz’ lattice reduction and the nearest lattice point problem. Combinatorica 6: 1–13
Bartkewitz T (2009) Improved lattice basis reduction algorithms and their efficient implementation on parallel systems. Diploma thesis, Ruhr University, Germany
Buist PJ (2007) The baseline constrained LAMBDA method for single epoch, single frequency attitude determination applications. In: Proceedings of ION GPS, p 12
Chang X, Yang X, Zhou T (2005) MLAMBDA: a modified LAMBDA algorithm for integer least-squares estimation. J Geod 79: 552–565
Chen D (1994) Development of a fast ambiguity search filtering (FASF) method for GPS carrier phase ambiguity resolution. UCGE Reports 20071, PhD dissertation
Chen D, Lachapelle G (1995) A comparison of the FASF and least-squares search algorithms for on-the-fly ambiguity resolution, navigation. J Inst Navig 42(2): 371–390
Cohen CE (1996) Attitude determination. In: Parkinson BW, Spilker JJ (eds) Global positioning system: theory and applications II. AIAA, Washington, pp 519–538
Cohen H (1995) A course in computational algebraic number theory. Springer, Berlin
Coveyou RR, Macpherson RD (1967) Fourier analysis of uniform random number generations. J ACM 14(1): 100–119
Damen MO, El Gamal H, Caire G (2003) On maximum-likelihood detection and the search for the closest lattice point. IEEE Trans Inf Theory 49(10): 2389–2402
Fincke U, Pohst M (1985) Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math Comput 44(170): 463–471
Frei E, Beutler G (1990) Rapid static positioning based on the fast ambiguity resolution approach “FARA”: theory and first results. Manuscr Geod 15: 325–356
Golub GH, Van Loan CF (1996) Matrix computations, 3rd edn. The Johns Hopkins University Press, Baltimore
Grafarend EW (2000) Mixed integer-real valued adjustment (IRA) problems. GPS Solut 4: 31–45
Grotschel M, Lovász L, Schrijver A (1993) Geometric algorithms and combinatorial optimization. Springer, Berlin
Guruswami V, Micciancio D, Regev O (2005) The complexity of the covering radius problem. Comput Complex 14: 90–121
Hanrot G, Stehle D (2007) Improved analysis of Kannan’s shortest lattice vector algorithm. In: Advances in cryptology—crypto 2007, proceedings. A. Menezes, vol 4622, pp 170–186
Hassibi A, Boyed S (1998) Integer parameter estimation in linear models with applications to GPS. IEEE Trans Signal Proc 46: 2938–2952
Hassibi B, Vikalo H (2005) On the sphere-decoding algorithm I. expected complexity. IEEE Trans Signal Proc 53: 2806–2818
Hermite C (1850) Extraits de lettres de M. Hermite à M. Jacobi sur diff′erents objets de la th′eorie des nombres. J Reine Angew Math 40: 279–290
Kannan R (1983) Improved algorithms for integer programming and related lattice problems. Paper presented at the conference proceedings of the annual ACM symposium on theory of computing, pp 193–206
Kannan R (1987) Algorithmic geometry of numbers. Annu Rev Comput Sci 16: 231–267
Kim D, Langley RB (2000) A search space optimization technique for improving ambiguity resolution and computational efficiency. Earth Planets Space 52(10): 807–812
Korkine A, Zolotareff G (1873) Sur les formes quadratiques. Math Annalen 6(3): 366–389 (in French)
Lagrange JL (1773) Recherches d’arithmetique. Nouveaux Memoires de l’Academie de Berlin
Langley RB, Beutler G, Delikaraoglou D, Nickerson B, Santerre R, Vanicek P, Well DE (1984) Studies in the application of the GPS to differential positioning. Technical Report No. 108, University of New Brunswick, Canada
Lenstra AK, Lenstra HW, Lovász L (1982) Factoring polynomials with rational coefficients. Math Ann 261: 513–534
Liu LT, Hsu HT, Zhu YZ, Ou JK (1999) A new approach to GPS ambiguity decorrelation. J Geod 73: 478–490
Micciancio D, Goldwasser S (2002) Complexity of lattice problems: a cryptographic perspective. Kluwer international series in engineering and computer science, vol 671. Kluwer Academic Publishers, Boston
Minkowski H (1905) Diskontinuitätsbereich für arithmetische Äquivalenz. J Rreine Angew Math 129: 220–274 (in German)
Mow WH (2003) Universal lattice decoding: principle and recent advances. Wirel Commun Mobile Comput 3(5): 553–569
Nguyen PQ, Stehlé D (2004) Low-dimensional lattice basis reduction revisited (extended abstract). In: Proceedings of the 6th international algorithmic number theory symposium (ANTS-VI), lecture notes in computer science, vol 3076. Springer, Berlin, pp 338–357
Nguyen PQ, Stehlé D (2009) An LLL algorithm with quadratic complexity. SIAM J Comput 39(3): 874–903
Nguyen PQ, Stern J (2001) The two faces of lattices in cryptology. In: Proceedings of CALC ’01, lecture notes in computer science, vol 2146. Springer, Berlin, pp 146–180
Pohst M (1981) On the computation of lattice vector of minimal length, successive minima and reduced bases with applications. ACM SIGSAM Bull 15: 37–44
Pujol X, Stehle D (2008) Rigorous and efficient short lattice vectors enumeration. In: Advances in cryptology—Asiacrypt 2008 J Pieprzyk, vol 5350, pp 390–405
Schnorr CP, Euchner M (1994) Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math Program 66: 181–199
Steinfeld R, Pieprzyk J, Wang H (2007) Lattice-based threshold changeability for standard Shamir secret-sharing schemes. IEEE Trans Inf Theory 53: 2542–2559
Teunissen PJG (1993) Least-squares estimation of the integer GPS ambiguities. Invited lecture, section IV theory and methodology, IAG general meeting, Beijing, China. Also in Delft Geodetic Computing Centre LGR series, No. 6, p 16
Teunissen PJG (1994) A new method for fast carrier phase ambiguity estimation. In: Proceedings of the IEEE PLANS’94, Las Vegas, NV, 11–15 April 1994, pp 562–573
Teunissen PJG (1995) The least-squares ambiguity decorrelation adjustment: a method for fast GPS ambiguity estimation. J Geod 70: 65–82
Teunissen PJG (1996) An analytical study of ambiguity decorrelation using dual frequency code and carrier phase. J Geod 70: 515–528
Teunissen PJG (1997) A canonical theory for short GPS baselines, parts I–IV. J Geod 71:320–336, 389–401, 486–501, 513–525
Teunissen PJG (1998a) GPS carrier phase ambiguity fixing concepts. In: Teunissen P, Kleusberg A (eds) GPS for geodesy, 2nd edn. Springer, Berlin, pp 317–388
Teunissen PJG (1998b) Success probability of integer GPS ambiguity rounding and bootstrapping. J Geod 72: 606–612
Teunissen PJG, De Jonge PJ, Tiberius CC (1997) The least-squares ambiguity decorrelation adjustment: its performance on short GPS baselines and short observation spans. J Geod 71: 589–602
Viterbo E, Boutros J (1999) A universal lattice code decoder for fading channels. IEEE Trans Inf Theory 45(5): 1639–1642
Wei Z (1986) Positioning with NAVSTAR, the global positioning system. Report No. 370, Department of Geodetic Science and Surveying, The Ohio State University, Columbus, OH
Xu PL (1998) Mixed integer observation models and integer programming in geodesy. J Geod Soc Jpn 44: 169–187
Xu PL (1999) Spectral theory of constrained second-rank symmetric random tensors. Geophys J Int 138(1): 1–24
Xu PL (2001) Random simulation and GPS decorrelation. J Geod 75: 408–423
Xu PL (2002) Isotropic probabilistic models for directions, planes and referential systems. Proc R Soc Lond Ser A 458(2024): 2017–2038
Xu PL (2006) Voronoi cells, probabilistic bounds and hypothesis testing in mixed integer linear models. IEEE Trans Inf Theory 52: 3122–3138
Xu PL, Grafarend E (1996) Statistics and geometry of the eigenspectra of three-dimensional second-rank symmetric random tensors. Geophys J Int 127(3): 744–756
Xu PL, Cannon E, Lachapelle G (1995) Mixed integer programming for the resolution of GPS carrier phase ambiguities. Paper presented at IUGG95 assembly, Boulder, 2–14 July
Zhao W, Giannakis GB (2005) Sphere decoding algorithms with improved radius search. IEEE Trans Commun 53(7): 1104–1109
Zhou Y (2010) A new practical approach to GNSS high-dimensional ambiguity decorrelation. GPS Solut. doi:10.1007/s10291-010-0192-6
Author information
Authors and Affiliations
Corresponding author
Additional information
An erratum to this article can be found at http://dx.doi.org/10.1007/s00190-011-0518-3.
Electronic Supplementary Material
The Below is the Electronic Supplementary Material.
Rights and permissions
About this article
Cite this article
Jazaeri, S., Amiri-Simkooei, A.R. & Sharifi, M.A. Fast integer least-squares estimation for GNSS high-dimensional ambiguity resolution using lattice theory. J Geod 86, 123–136 (2012). https://doi.org/10.1007/s00190-011-0501-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00190-011-0501-z