9512.net

# A simplified MINQUE procedure for the estimation of variance-covariance components of GPS o

A SIMPLIFIED MINQUE PROCEDURE FOR THE ESTIMATION OF VARIANCE-COVARIANCE COMPONENTS OF GPS OBSERVABLES
Chalermchon Satirapod1 , Jinling Wang 2 , Chris Rizos 2 Department of Survey Engineering Chulalongkorn University, Bangkok, Thailand 10330 School of Surveying and Spatial Information Systems The University of New South Wales, Sydney, Australia 2052 ABSTRACT
Minimum Norm Quadratic Unbiased Estimation (MINQUE) is one of the commonly used methods for the estimation of variance-covariance components. The MINQUE procedure has been successfully used to estimate the variance-covariance components of GPS observations. However, the MINQUE procedure is a big computational burden, and the requirement of having an equal number of variancecovariance components in the estimation step is a major limitation. It is therefore difficult to implement this procedure when the number of observed satellites has changed during an observation period. In this paper, a simplified MINQUE procedure is proposed in which the computational load and time are significantly reduced. The quality of the results obtained is similar to those from the rigorous procedure. Furthermore, the effect of changing the number of satellites on the computations is effectively dealt with.
2 1

INTRODUCTION GPS measurements are typically processed using the least-squares method. To obtain reliable least-squares estimates, however, both the functional model and the stochastic model must be adequately defined. The functional model describes the mathematical relationship between the GPS observations and the unknown parameters, while the stochastic model describes the statistics of the GPS observations (e.g., [7]; [11]). For many surveying applications the functional model is nowadays sufficiently well known. However, the definition of the stochastic model is still a challenging research topic. It has been shown that GPS measurements have a heteroscedastic, space- and time-correlated error structure [17]. Any mis-specifications in the stochastic model may lead to unreliable results (e.g., [1], [2], [5], [13, [16], [17]). Many stochastic modelling procedures, such as one based on the signal-to-noise ratio (SNR) model, or a satellite elevation angle dependent model, or the MINQUE procedure, have recently been proposed. [3] investigated possible weighting schemes for GPS carrier phase observations and found that the SNR model and the satellite elevation angle dependent model are almost numerically equivalent. In [12], a comparative study of two quality indicators, the SNR and the satellite elevation angle, was carried out. This study revealed that in some cases both the use of SNR and satellite elevation angle information failed to reflect the reality of data quality. It is therefore appropriate to investigate a rigorous method for constructing variance-covariance matrices of GPS observations. A comprehensive review of some rigorous methods for estimating the variance components can be found in [4]. Of these methods, the MINQUE procedure is one of those most commonly used. This procedure was successfully introduced by [19] to estimate the variance-covariance components of GPS observations. Moreover, the reliability of the resolved ambiguities and the relative efficiency of baseline estimation were shown to have been significantly improved through the use of the MINQUE

approach. However, the computational burden of this technique is still a significant limitation, as is the requirement to have an equal number of variance-covariance components in the estimation step. The proposed procedure aims to reduce the computational load and the memory usage, and to incorporate the effect of changes in the number of satellites in the computation. The standard MINQUE method is first reviewed. The simplified procedure is then derived and discussed in the subsequent section. Experimental results are presented and discussed, followed by some concluding remarks. EMBEDEMBEDEMBEDEMBEDEMBEDEMBEDEMBEDEMBEDEMBED HYPERLINK HYPERLINKHYPERLINK MINQUE PROCEDURE In the following Gauss-Markov model with n measurements and t unknowns: l = Ax + v C = P ?1 = ∑θ iTi
i =1 k

(1) (2)

l and v are n×1 vectors of the measurements and residuals, respectively; A is the n×t design matrix; x is the t ×1 vector of the unknown parameters; θ1 ,θ2 ,… ,θk are the variance-covariance components of the measurements to be estimated; k is the number of variance-covariance components; and T1 ,T2 ,… ,Tk are the so-called accompanying matrices (see [19], for more details). P is the weight matrix of the observations and C is the variance-covariance matrix of the observations. According to [8] and [9], a minimum norm quadratic unbiased estimation of the linear function of θi (i = 1, 2,…, k ) , i.e., g1 θ1 + g2 θ2 +…+ gkθk , is the quadratic function lTMl if the matrix M is determined by solving the following matrix trace minimum problem: Tr{MCMC } = min Subject to MA = 0, Tr{MTi} = gi (4) (5) (3)

where Tr {} is the trace operator of a matrix. Based on Equations (3), (4) and (5), the variance-covariance components can be estimated as [10]: ? = (θ ? ,θ ? ,..., θ ? ) T = S ?1 q θ 1 2 k where the matrix S = {sij} with sij = Tr{RTiRTj} and the vector q = {qi} with qi = lTRTi Rl (8) (7) (6)

and R = PQvP with Qv = [P-1 - A(A TPA)-1AT] being the adjusted residuals cofactor matrix. R can also be expressed by a partitioned matrix: ? R11 ?R ? 21 ?L ? ? Rm1 R12 L R1m ? R22 L R 2m ? ? L L L ? ? Rm2 L R mm ? (9)

R=

(10)

where m is the number of the observation epoch in a session. Since the relationships between v and l are: v = -QvPl PQvPv = -PQvPl = Pv according to Equations (11) and (12), Equation (8) can be further written as: qi = lTRTi Rl = v TRTi Rv = vTPTiPv (13) (11) (12)

It is noted from Equations (6), (7), (8) and (9) that the estimated variance-covariance components depend on matrix C, which includes the variance-covariance components themselves. Therefore, an iterative process must be performed. Initially, an a priori ?1 is then obtained. value of θi is given by θi0 . With Equation (6), the initial estimate θ ? j as the a priori value, the new In the (j +1)th iteration, using the previous estimate θ estimate is: ? j +1 = S ?1 (θ ? j ) q(θ ? j ) (j = 0,1,2,…) θ (14)

? converges, the limiting value of θ ? will which is called the iterated MINQUE. If θ satisfy the following equation: ? )θ ? = q (θ ?) S (θ which can be further expressed as [10]: ? )Ti } = l T R(θ ? )Ti R(θ ? )l , (i = 1,2,…,k ) Tr{R(θ SIMPLIFIED MINQUE P ROCEDURE It is noted from the above procedure that, when the MINQUE method is used in GPS data processing, the storage of the matrix R may require a huge memory. In addition, the computation relating to this matrix is extensive. (16) (15)

A simplification of the MINQUE procedure can be obtained by replacing the matrix R in Equation (10) by a diagonal matrix R* . The matrix R* has a block-diagonal structure and can be defined as: ? R11 ?0 * R = ? ?L ? ?0 0 R 22 L 0 0 ? L 0 ? ? L L ? ? L Rmm ? L

(17)

In this study, we concentrate on the computational efficiency of the estimation of the variance-covariance matrix. Hence, it is assumed that the temporal correlations between epochs are absent, the weight matrix P and the accompanying matrices Ti have the following structures: P = diag ( Pk ) , ( k = 1, 2, ..., m) Ti = diag (Tik ) , ( k = 1, 2, ..., m) (18) (19)

where Pu = Pv and Tiu = T jv , with u, v = 1, 2...., m . Then, Equations (7) and (13) can be simplified as: sij = Tr{RTiRTj}= ∑ Tr ( Rkk Tik R kk T jk )
k =1 m

(20) (21)

qi = v TPTiPv = ∑ Tr (v kT Pk Tik Pk v k )
k =1

m

Table 1 reveals the advantage of using the matrix R* in the computation in terms of memory usage. It is assumed that 6 satellites are tracked during the observation period, and a 15-second sampling interval is used. Table 1. Comparison of memory usage
Session length (minutes) 5 10 15 20 25 30 35 40 45 50 55 60 Memory usage (kilobytes) MINQUE procedure Simplified procedure 78.1 3.9 312.5 7.8 703.1 11.7 1250.0 15.6 1953.1 19.5 2812.5 23.4 3828.1 27.3 5000.0 31.3 6328.1 35.2 7812.5 39.1 9453.1 43.0 11250.0 46.9

Clearly, from Table 1, the memory usage is substantially reduced with the implementation of the simplified procedure. In addition, it is possible to easily handle the change in the number of satellites during an observation period since the

computation of Equation (20) can be done on an epoch-by-epoch basis. The reduction in the computational time will be discussed in a subsequent section. Matlab-based GPS baseline processing software developed at The University of New South Wales, Sydney, Australia, was used to process the data. The original Matlab codes were downloaded from the Website given in [15]. The Matlab codes for the implementation of the MINQUE and simplified MINQUE procedures can be found in [14]. EXPERIMENTAL DATA To demonstrate the efficiency of the simplified MINQUE procedure, four GPS static baseline data sets have been analysed. The details of the four data sets are presented in Table 2. Table 2. Details of the four experimental data sets
Receivers Baseline length (m) Survey date Satellites Elevation angle (° ) Data interval (sec) Data span (min) Ashtech Z-XII 215 June 7, 1999 02,07,10,13,19,27 83,15,52,71,19,53 15 30 NovAtel Millennium 15 July 10, 2000 02,08,11,13,27 63,68,16,54,49 15 30 Leica system 300 870 Nov 18, 1996 04,14,18,19,24,27,29 41,25,61,71,26,36,30 15 30 Trimble 4000SSE 13,300 Dec 18, 1996 07,14,15,16,18,29 19,53,82,24,18,78 15 30

All data sets were first processed using the whole data span to estimate the true ambiguity values, which were then used to verify the correctness of the resolved ambiguities from subsequent data processing. For the 200m baseline, both Ashtech receivers were mounted on pillars that are part of a first-order terrestrial survey network. The known baseline length between the two pillars is 215.929 ± 0.001m. This will be used as the ground truth to verify the accuracy of the results. For other baselines (15m, 870m, and 13300m), the reference values derived from the whole data span would be used to verify the accuracy of the results. Each data set was divided into three sets of ten minutes. Three solutions for each data set were computed by applying the standard stochastic modelling procedure (assuming that all observations have the same weight and only mathematical correlation is taken into account in this stochastic model), the rigorous procedure and the simplified procedure. ANALYSIS OF RESULTS In ambiguity resolution, the difference between the best and second best ambiguity combination is crucial for the ambiguity discrimination step. The F-ratio is commonly used as the ambiguity discrimination statistic. The larger the F-ratio value, the more reliable the ambiguity resolution. The critical value of the F-ratio is normally chosen to be 2.0 (e.g. [6]). The ambiguity validation test can also be based on the newly developed statistic W-ratio [18]. Similarly, the larger the W-ratio value, the more reliable the ambiguity resolution. The statistics, F-ratio and W-ratio, obtained from the data processing are shown in Figures 1 and 2. In both figures, each subplot represents a receiver type, and each group of columns (I, II, III) represents the solution obtained from an individual session. More details of the results obtained from the MINQUE procedure can be found in [19].

20

20

Standard MINQUE Simplified

15

15

F-ratio

10

F-ratio
I II III

10

5

5

0 a) ASHTECH Z-XII (200m)

0 I II III b) NOVATEL MILLENIUM (15m)

20

20

15

15

F-ratio

10

F-ratio
I II III

10

5

5

0 c) LEICA SYSTEM 300 (870m)

0 I II III d) TRIMBLE 4000SSE (13300m)

Fig 1 F-ratio value in ambiguity validation tests

Standard 40 30 40 30 MINQUE Simplified

W-ratio

20

W-ratio
I II III

20

10

10

0 a) ASHTECH Z-XII (200m)

0 I II III b) NOVATEL MILLENIUM (15m)

40

40

W-ratio

20

W-ratio
I II III

30

30 20

10

10

0 c) LEICA SYSTEM 300 (870m)

0 I II III d) TRIMBLE 4000SSE (13300m)

Fig 2 W -ratio value in ambiguity validation tests

From Figures 1 and 2, the F-ratio and W-ratio values obtained from the rigorous MINQUE and the simplified MINQUE procedures are larger compared to those from the standard procedure. Clearly, the reliability of the resolved ambiguity set is improved. It can also be seen that both the rigorous and the simplified procedures yield very similar numerical results. In the case of the simplified procedure, a larger number of iterations is required but the computational time is significantly reduced. This is due

to the omission of the computation of non-diagonal elements of the matrix R Equations (7) and (8). Table 3 summarises the performance of these procedures terms of computational time. It is also important to note that when the number observations is increased, the computational time is dramatically increased. This more so in the case of the rigorous MINQUE method. Table 3. Comparison of computational time

in in of is

Computational time (seconds) MINQUE procedure Simplified procedure Ashtech (1) – 6 sats 511.37 28.00 Ashtech (2) – 6 sats 932.35 39.00 Ashtech (3) – 6 sats 887.59 36.46 NovAtel (1) –5 sats 152.30 5.13 NovAtel (2) –5 sats 194.27 6.34 NovAtel (3) –5 sats 114.65 3.91 Leica (1) – 7 sats 664.73 27.30 Leica (2) – 7 sats 1338.04 73.31 Leica (3) – 7 sats 514.18 18.75 Trimble (1) – 6 sats 871.47 39.28 Trimble (2) – 6 sats 518.16 21.03 Trimble (3) – 6 sats 346.08 10.08 All solutions are computed using Matlab GPS baseline processing software developed at UNSW on a PentiumII- 366MHz processor.

In the case of the estimated baseline components, the results are compared with the reference values. The differences between the estimated values and the reference values are presented in Table 4. The results show that the rigorous and simplified MINQUE procedures generally produce more reliable estimated baseline components than the standard stochastic modelling procedure. It can also be seen that the simplified MINQUE procedure produces results, which are essentially identical to those obtained from the rigorous MINQUE method.

Table 4. The differences between estimated baseline lengths and the reference values
Baseline 200m (Ashtech) Method Standard Procedure MINQUE Procedure Simplified Procedure 15m (NovAtel) Standard Procedure MINQUE Procedure Simplified Procedure 870m (Leica) Standard Procedure MINQUE Procedure Simplified Procedure 13300m (Trimble) Standard Procedure MINQUE Procedure Simplified Procedure Session I II III I II III I II III I II III I II III I II III I II III I II III I II III I II III I II III I II III Difference in baseline length (cm) 0.3 0.2 0.7 0.1 0.1 0.2 0.1 0.1 0.2 0.0 0.0 0.0 0.0 0.0 -0.1 0.0 0.0 -0.1 0.0 0.1 -0.1 0.3 0.1 -0.1 0.3 0.1 -0.1 0.8 -0.1 -0.7 0.5 -0.4 -0.4 0.5 -0.4 -0.4

CONCLUSIONS The simplified procedure is shown to produce results that are close in quality to those of the rigorous procedure. However, the computational time and the memory requirements of the simplified procedure are much less than those in the case of the rigorous procedure. Furthermore, the effect of a change in the number of satellites on the computation is effectively dealt with. The simplified procedure assumes that there are no large systematic errors in the observations. If large systematic errors exist in the measurements (i.e. E(v) ≠ 0), temporal correlation will need to be taken into account before the simplified procedure is applied. In addition, given a small number of observations, the variance-covariance matrix of estimated baseline components may not be reliably estimated.

ACKNOWLEDGMENTS The authors would like to thank Mr. Clement Ogaja for his assistance with the preparation of this paper. References 1. Cannon, M. E. and Lachapelle, G., 1995. Kinematic GPS Trends-Equipment, Methodologies and Applications, In: Beutler, Hein, Melbourne and Seeber (Ed.): GPS Trends in Precise Terrestrial, Airborne, and Space-borne Applications, IAG Symposium No. 115, Boulder, Colorado, 3-4 July, 161-169. Chen, D. S., 1994. Development of a Fast Ambiguity Search Filtering (FASF) Method for GPS Carrier Phase Ambiguity Resolution, Ph.D Thesis, Department of Geomatics Engineering, University of Calgary, Canada, 98pp. Collins, J.P. and Langley, R.B., 1999. Possible Weighting Schemes for GPS Carrier Phase Observations in the Presence of Multipath. Contract report for the United States Army Corps of Engineers Topographic Engineering Center, No. DAAH04-96-C-0086 / TCN 98151, March. Crocetto, N., Gatti, M. and Russo, P., 2000. Simplified Formulae for the BIQUE Estimation of Variance Components in Disjunctive Observation Groups, Journal of Geodesy, 74, 447-457. Hatch, R. and Euler, H.-J., 1994. Comparison of Several AROF Kinematic Techniques, 7th Int. Tech. Meeting of the Satellite Division of the U.S. Inst. of Navigation GPS ION'94, Salt Lake City, Utah, 20-23 September, 363-370. Euler, H.J. and Landau, H., 1992. Fast GPS Ambiguity Resolution On-the-fly for Real-time Applications , 6th International Symposium on Satellite Positioning, Columbus, Ohio, 17-20 March, 650-659. Leick, A., 1995. GPS Satellite Surveying, John Wiley & Sons, Inc., New York, N.Y., 560pp. Rao, C.R., 1970. Estimation of Heterogeneous Variances in Linear Models, Journal of American Statistical Association, 65, 161-172. Rao, C.R., 1971. Estimation of Variance and Covariance ComponentsMINQUE, Journal of Multivariate Analysis, 1, 257-275. Rao, C.R., 1979. MINQUE Theory and Its Relation to ML and MML Estimation of Variance Components, Sankhya, 41, Series B, 138-153. Rizos, C., 1997. Principles and Practice of GPS Surveying, Monograph 17, School of Geomatic Engineering, The University of New South Wales, 555pp. Satirapod, C. and Wang, J., 2000. Comparing the Quality Indicators of GPS Carrier Phase Observations, accepted for publication in Geomatics Research Australasia. Sauer, D. B., Frei, E. and Beulter, G., 1992. The Importance of Code Measurements in Relative Positioning and Navigation, 5th Int. Tech. Meeting of the Satellite Division of the U.S. Inst. of Navigation GPS ION'92, Albuquerque, New Mexico, 22-24 September, 1043-1051. SNAP, 2001. The SNAP group website: www.gmat.unsw.edu.au/snap/staff/ chalermchon_satirapod.htm Strang, G., and Borre, K., 1997. Linear Algebra, Geodesy, and GPS, WellesleyCambridge Press, Wellesley, Mass., 624pp. Teunissen, P.J.G., 1998. Quality Control and GPS, In Kleusberg A. and GPS Observation Equations and Positioning Concepts, In: Kleusberg, A. and

2. 3.

4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

14. 15. 16.

17. 18. 19.

Teunissen, P.J.G. (eds), GPS for Geodesy (second edition), Springer-Verlag, Berlin Heidelberg New York, 271-318. Wang, J., 1998. Stochastic Assessment of GPS Measurements for Precise Positioning, 11th Int. Tech. Meeting of the Satellite Division of the U.S. Inst. of Navigation GPS ION'98, Nashville, Tennessee, 15-18 September, 81-98. Wang, J., Stewart, M. and Tsakiri, M., 1998. A Discrimination Test Procedure for Ambiguity Resolution On-the-Fly, Journal of Geodesy, 72, 644-653. Wang, J., Stewart, M. and Tsakiri, M., 1998. Stochastic Modelling for Static GPS Baseline Data Processing, Journal of Surveying Engineering, 124(4), 171181.