Fixed point theorems of GPS carrier pha ambiguity resolution and
their application to massive network processing:Ambizap
Geoffrey Blewitt1
坎特伯雷故事集
Received5April2008;revid22July2008;accepted3September2008;published23December2008.
[1]Preci point positioning(PPP)has become popular for Global Positioning System
(GPS)geodetic network analysis becau for n stations,PPP has O(n)processing time,yet
solutions cloly approximate tho of O(n3)full network analysis.Subquent carrier
pha ambiguity resolution(AR)further improves PPP precision and accuracy;however,
full-network bootstrapping AR algorithms are O(n4),limiting single network solutions to n
<100.In this contribution,fixed point theorems of AR are derived and then ud to
develop‘‘Ambizap,’’an O(n)algorithm designed to give results that cloly approximate
full network AR.Ambizap has been tested to n%2800and proves to be O(n)in this
range,adding only$50%to PPP processing time.Tests show that a98-station network is
resolved on a3-GHz CPU in7min,versus22h using O(n4)AR methods.Ambizap
features a novel network adjustment filter,producing solutions that precily match O(n4)
full network analysis.The resulting coordinates agree to(1mm with current AR
methods,much smaller than the$3-mm RMS precision of PPP alone.A2000-station
global network can be ambiguity resolved in$2.5h.Together with PPP,Ambizap enables
rapid,multiple reanalysis of large ,$1000-station EarthScope Plate
Boundary Obrvatory)and facilitates the addition of extra stations to an existing network
solution without need to reprocess all data.To meet future needs,PPP plus Ambizap is
designed to handle$10,000stations per day on a3-GHz dual-CPU desktop PC.
londonbridge
Citation:Blewitt,G.(2008),Fixed point theorems of GPS carrier pha ambiguity resolution and their application to massive network processing:Ambizap,J.Geophys.Res.,113,B12410,doi:10.1029/2008JB005736.
1.Introduction
[2]Since1994,when the International GNSS Service (IGS)became operational[Beutler et al.,1994;Dow et al., 2005],the analysis of the global GPS network(GGN)by veral IGS analysis centers has consistently delivered high-accuracy satellite orbit positions and satellite clock bias. The,in turn,have allowed investigators to compute accurate ground station positions for both regional-and global-scale networks[Moore,2007].U of the products have enabled scientific discoveries and monitoring capabil-ities,with scientific contributions to plate tectonics,the earthquake cycle,glacial isostatic adjustment,crustal and mantle rheology,and surface mass , Blewitt,2007].
[3]As of2008,data from$2800continuously operating GPS stations around the world including400IGS stations are routinely downloaded from IGS and regional data centers for subquent analysis at University of Nevada, Reno(UNR)(Figure1).As full network least squares computations scale as O(n
3),this pos a significant barrier to the full exploitation of all available data.Since its invention by Zumberge et al.[1997],PPP has become popular for regional GPS network processing,becau processing time scales linearly with the number of sta-tions,O(n),and PPP cloly reproduces an O(n3)full network solution(in fact,it exactly reproduces the solution for the subt of stations ud initially for orbit and clock determination).
[4]In GPS positioning,resolution of the integer cycle ambiguity in the carrier pha data can significantly im-prove positioning precision and accuracy,particularly in the east component for equatorial to midlatitude stations [Blewitt,1989].Theoretical properties of ambiguity resolu-tion are here exploited to derive a very rapid algorithm, which is then applied to GPS network solutions that have first been derived by preci point positioning(PPP). However,the processing time for full network ambiguity resolution generally scales as O(n4),thus the main practical advantage of PPP can be lost.
[5]Motivating this study was the idea that theoretical properties of ambiguity resolution might point the way to O(n)processing schemes.A reasonable condition for such schemes to be acceptable is that the differences between optimal and suboptimal solutions should be statistically insignificant(‘‘near optimal’’).Here a new algorithm is developed to apply ambiguity resolution to a GP
S network with O(n)computation time,which has been demonstrated
JOURNAL OF GEOPHYSICAL RESEARCH,VOL.113,B12410,doi:10.1029/2008JB005736,2008 Click
Here
for
Full
Article
1Nevada Bureau of Mines and Geology and Seismological Laboratory,
University of Nevada,Reno,Nevada,USA.
Copyright2008by the American Geophysical Union.
0148-0227/08/2008JB005736$09.00高考下午几点开始几点结束
up to n %3000at a rate of $5s per station on a 3-GHz processor.
2019考研
2.Theoretical Considerations
2.1.Overview
[6]As a general strategy let us ek to partition an n -station network solution into a number O (n )of lf-contained computational blocks giving results that can be asmbled as O (n ).Our practical definition of O (n )can be relaxed to allow for higher-order effects common for minor necessary tasks,such as O (n log n )sorting,provided they add a negligible percentage of processing time for n <104.As a general guide to developing an accurate algorithm,it is important to consider theoretical properties of GPS net-works subject to full network ambiguity resolution.This ction briefly discuss theoretical considerations only,so as to clearly parate it from the specific implementation.Although theoretical considerations generally require some level of necessary rigor,the real proof of their validity in this context will be empirical,with demonstrated accuracy and computation times.
[7]In mathematics,a ‘‘fixed point theorem’’is a state-ment that,under certain conditions,operator F (x )will have at least one fixed point satisfying F (x )=x .A fixed point theorem might also specify what the fixed points are or how to find them [Shashkin ,1991].In the context of this paper,F reprents the
‘‘bias-fixing operator,’’which us ambiguity resolution to adjust double difference bias to perfect values (with zero variance),and thus update other correlated parameters.Here we ek a fixed point for the mapping of parameters from their initial PPP estimates to their bias-fixed estimates.
[8]Since parameter ts can always be transformed into another equivalent t (that is complete and linearly inde-pendent),let us consider linear transformations ~s =L s that satisfy F (~s )=~s ,for arbitrary values of parameters s.As shown in ction 2.2,there exists such a fixed point which can be interpreted as the weighted mean centroid of the network.Moreover,it is shown that under conditions
common for permanent GPS networks,balines that have already been bias fixed are innsitive to the bias fixing of other balines in the network.Taken together,the fixed points suggest a strategy of constructing a network solution out of n À1bias-fixed baline vectors (relative coordinates between station pairs),where the initial PPP solutions provide an absolute position to the network.
[9]This ction also explores the stochastic nature of large bias-fixed networks,considering that an O (n )algo-rithm must abandon the computation of the full network covariance matrix.As will be shown,it is remarkable that a block diagonal reprentation of the covariance matrix is almost exact for large networks.Finally,the lection an optimal t of n À1balines is addresd by considering t
he theory of Euclidean minimum spanning trees,with the goal of lecting an algorithm that contributes a negligible fraction of the overall processing time.
2.2.Fixed Point Theorem 1:Centroid
[10]For an n -station network,let us start with n indepen-dent station solutions from PPP,which can be written as vectors s i with covariance matrices C i for stations i 2{1,...,n }.Let vectors s i include station coordinates and single-difference carrier pha bias between all satellites in common view.The dimensions of all s i and the order of parameters in s i are assumed to be identical for all stations.(The conquences of noncommon visibility will be addresd in paragraph 16.)
[11]Let us define the bias fixing operator F (L s )as the mapping of any linear combination of parameters from their initial PPP solution to a bias-fixed solution,as a result of ambiguity resolution of differences in the single-difference bias.Now the first fixed point theorem is stated:
Theorem 1
s C
英语词性缩写
X
i
C À1
i s i )F
s ðÞ¼ s ð1Þ
where C [P i C i À1]
À1=Var( s ).By definition,the covariance matrices C i =Var(s i )are understood to be constant,referring to the values given by PPP (but the values of s i in equation (1)can be from either before or after bias fixing).Simply put,the weighted mean parameter vector (‘‘centroid’’)is a fixed point with respect to bias fixing.
[12]It is sufficient to prove that the centroid is not correlated with differences in station parameters,by invok-ing the block diagonal nature of the formal covariance matrix from PPP:
Cov s ;s i Às j ÀÁ¼ C X k
C À1k
Cov s k ;s i ðÞÀCov s k ;s j ÀÁÂü C X k C À1k d ki C i ÀC À1k d kj C j Âü C C À1i C i ÀC À1j C j h i ¼0
ð2Þ
hence proving theorem 1.
[13]Now let us assume the lemma that correlations between two variables will remain zero if a new measure-ment is a function of only one of the two variables.
Since
Figure 1.Number of continuous GPS stations per day routinely analyzed at UNR versus date.The upper red curve reprents all stations,and the lower green curve the subt that are official IGS stations.
ambiguity resolution reprents only a measurement of parameter differences,this leads to the corollary:
Cov s ;s 0i Às 0j ¼0
ð3Þ
where the primes indicate solutions after ambiguity
resolution.
[14]Another corollary of the theorem is that the vari-ance of the centroid C =Var( s )is not changed by F .
Therefore,to compute the absolute location of a bias fixed network,all that is required is already available in the form of n statistically independent PPP solutions and O (n )computations.
[15]One problem in applying equation (1)is that the station coordinate components of the fixed point vector are linear combinations of all parameters,including station coordinates and bias parameters.It would be much more convenient if a weighted average of station coordinate triplets alone provided a fixed point.It is now shown that this condition is satisfied when the PPP covariance matrices for all stations are the same to within any positive scale factor.For this ‘‘assumption of similar covariances,’’let us write
C À1i
¼w i C
À1ð4Þ
where the scalar weights satisfy
P
i
小学校长竞聘演讲稿w i =1.In this ca,
equation (1)reduces to
s
X
i
w i s i
ð5Þ
As the order of parameters are the same in all vectors s i and
s ,the computations of weighted average of individual parameters are decoupled in equation (5).Therefore,under the assumption of similar covariances,the weighted mean station coordinates can be computed without reference to the bias parameters.
[16]The assumption of similar covariances requires that
obrvation schedules for bias-fixed balines are similar (but the data rates do not need to be the same),and that there is reasonable common visibility of satellites.In practice it is recommended that algorithms derived from this theory only be applied to sites with data ts of equal duration,for example,continuously operating sites with full (or nearly full)24-h data ts.It is also recommended that algorithms be designed to lect nearest neighbor stations to conduct ambiguity resolution,both to maximize common visibility,and to maximize probability of success in ambiguity resolution.
[17]Since the absolute position of a bias fixed network can be computed as O (n ),what remains is the computation of the relative positions of stations in the network,which theoretically is completely specified by n À1baline vectors.This suggests that O (n )computation of the network may be possible given the computation of n À1suitable bias-fixed baline vectors.‘‘Suitable’’baline vectors would need to replicate,or very cloly approximate,the relative coordinates derived by full network ambiguity resolution.Furthermore,assuming such suitable baline vectors can be computed,theorem 1implies that to compute s ,as defined by equation (1),we can choo to u either the original PPP solutions s i or the solutions s 0=F (s )derived from the suitable baline vectors,together with the original PPP covariance matrices.
2.3.Fixed Point Theorem 2:Balines
[18]Consider a network solution initialized by PPP,where a single baline is then bias fixed to produce parameter vectors s i 0and s j 0,which include both station coordinates and bias.As explained previously,let us make the assumption of similar covariances.Let the bias fixing operator F (defined in ction 2.1)then be applied to the entire network.
Theorem 2^s 0ij s 0i Às 0j )F ^s 0ij
¼^
s 0ij ð6Þ
Simply put,the bias-fixed solution of baline parameters is
independent of bias fixing of other balines in the network.[19]To prove this,consider bias fixing stations i and j to an independent PPP solution s k for any k 2{i ,j },as shown in Figure 2.From equation (3),
四级英语文章Cov s k À s ij ;s 0i Às 0j
¼0
ð7Þ
where s ij is the centroid of stations i and j,defined by equation (1).Thus,adding any independent information on
(s k À
s ij )(alone)has no effect on ^s ij 0
.Expanding the term (s k À
s ij )results in the weighted average of two baline parameter vectors from station k :
s k À s ij ¼s k À C
X
p 2i ;j f g
C À1
p s p
¼ CC À1i s k Às 0i ÀÁþ CC À1j s k Às 0j男生青春痘治疗方法
免费经期卫生用品
ð8
Þ
Figure 2.Diagram illustrating the geometry ud in the proof of theorem 2,showing the bias fixing of a third station s k to an existing bias fixed baline (s i 0Às j 0),by resolving ambiguities to the centroid of that baline s ij .
Now applying equation (4)(the assumption of similar covariances),equation (8)becomes
s k À s ij ¼w i s k Às 0i ÀÁþw j s k Às 0
j
ð9Þ
where w i +w j =1and s ij =w i s i +w j s j .As was the ca for
ction 2.2,the assumption of similar covariances decouples the linear combinations of bias from the station coordinates,so making it possible to resolve ambiguities and bias fix equation (9).There are only two linearly independent balines in a three-station subnetwork,and one of tho balines (s i 0Às j 0)is already bias fixed;thus the other two balines can be constructed as linear
combinations of (s i 0Às j 0)and (s k À
s ij ):s k Às 0i ÀÁ¼s k À s ij ÀÁþw j s 0j Às 0
i s k Às 0j ¼s k À
s ij ÀÁþw i s 0i Às 0
j ð10Þ
Therefore additional bias fixing of (s k 0À s ij 0
)is equivalent to bias fixing the entire three-station subnetwork (Figure 2).This fact,together with equation (7)demonstrates that the first bias fixed baline vector is innsitive to additional bias fixing in the network.
[20]Note that equation (9)was only constructed to prove the theorem,so we do not literally need to bias fix this linear combination of balines.According to the theorem,ba-lines can be individually bias fixed,then combined together to approximate cloly the full network solution,provided the conditions of common visibility outlined in ction 2.2are cloly met.
2.4.Stochastic Properties of Large Bias-Fixed Networks
[21]Consider the cross covariance between station posi-tions of different stations.To get an idea of how this cross covariance changes a function of the number of bias-fixed stations n ,let us assume that all station covariance matrices from PPP are identical C i C ,which allow us to write the inver variance of the centroid as a function of n :
C
À1n ðÞ¼n C À1ð11Þ
Now let us assume that,after bias fixing,all cross
covariances are equal,and all variances are equal,and assume they are functions of n :
X n ðÞ Cov x 0i ;x 0
j ¼i
V n ðÞ Var x 0i ÀÁ¼Cov x 0i ;x 0i
ÀÁ
ð12Þ
which us the previous result that the variance matrix of the centroid remains constant under bias fixing.As a corollary of theorem 2,the variance B of the relative position for a baline that is already bias fixed remains constant as the network grows:
B var x 0i Àx 0
j ¼i ¼2V n ðÞÀX n ðÞ½
ð13Þ
The following lemma will now be ud,which can be verified by taking the mean of both sides (which is allowed
becau the left hand side must be identical for all stations)
and by applying x 0=
x (from theorem 1):Cov x 0i ; x ÀÁ
¼Var x ðÞ¼ C
ð14Þ
Expanding both sides by substituting equations (11)and
(12)gives us
C
¼1=n ðÞC ¼Cov x 0i ;
x ÀÁ
¼1=n ðÞ
X
j
Cov x 0i ;x 0j ¼1=n ðÞV n ðÞþn À1ðÞX n ðÞ½ ð15Þ
Substituting equation (13)and rearranging gives
X n ðÞ¼1
n
C ÀB =2ðÞ
lim n !1
X n ðÞ¼0
ð16Þ
V n ðÞ¼B =2þ1
n
C ÀB =2ðÞfun什么意思
lim n !1
V n ðÞ¼B =2
ð17Þ
where the constant term (C ÀB /2)>0is equal to half the variance reduction in relative position due to bias fixing,and so is positive definite.Thus X (1)=0and V (1)=B /2,which is half the variance of the bias-fixed relative position.[22]Thus the correlation between different station posi-tions is inverly proportional to the number of stations,and becomes negligible for large networks n >102(as can be verified in practice).Therefore,in the limit of large n ,the ambiguity resolution from a new station to a large network only affects that station’s coordinates.
[23]The above stochastic properties of large bias-fixed networks lend further evidence to suggest that accurate O (n )algorithms are feasible.Clearly,O (n 4)full network algo-rithms when applied to large networks waste their time computing the off-diagonal elements of the covariance matrix,when theory predicts that they tend to vanish and so hold negligible information content.This suggests it is reasonable to reprent the final covariance matrix of station coordinates as block diagonal (of triplets),for which the number of computed elements is O (n )(as is the ca for PPP).2.5.Theory of Optimal Baline Selection
[24]As the goal is to maximize the probability of cor-rectly resolving the ambiguities,let us lect the t of n À1balines that minimize the sum of distances between n stations (a geometrical version of the ‘‘traveling salesman problem’’).This is known as the Euclidean minimum spanning tree (EMST).An exact solution to the EMST is given by Kruskal’s ‘‘greedy’’algorithm [Kruskal ,1956],which starts with each station as its own disjoint tree in a ‘‘forest’’(the union of all trees),then grows the trees by iteratively adding the next shortest baline that does not destroy the tree by forming a cycle (i.e.,does not already have both stations within the same tree).The algorithm stops when all stations are in one tree.The problem is that
Kruskal’s algorithm is unacceptably slow at O(b log n)= O(n2log n)(R.Sedgewick and K.Wayne,Minimum span-ning tree,lecture notes for Computer Science Cour226: Algorithms and Data Structures,2007,available at www.cs.princeton.edu/cours/archive/fall07/cos226/lectur-es.html),where b=n(nÀ1)/2is the number of possible balines that can be formed from n stations.
[25]The solution to this problem us the Delauney triangulation on the sphere,which can be computed in O(n log n)[Renka,1997].The Delauney triangulation is the mathematical dual of the V ornoi diagram,which is con-structed of n polygons,each centered on station,defining the nearest neighbor station for every possible query point [Aurenhammer,1991].Station pairs are defined as nea
rest neighbors if their geodesic cross only one shared V oroi edge.This defines a b(3nÀ6)t of balines[Renka, 1997].
[26]The Delauney triangulation has the relevant mathe-matical property that is a supergraph of the EMST [Aurenhammer,1991].This means that all balines of the EMST are balines of the Delauney triangulation of the stations.Therefore the EMST solution of nÀ1balines is a subt of the b(3nÀ6)balines from the Delauney triangulation,so the problem reduces to finding this subt. It follows that Kruskal’s algorithm can be ud to find the EMST as a subt of the Delauney triangulation in O(b log n)=O(n log n).Therefore the combined algorithm is also O(n log n)(where log n<4in our GPS univer).This not quite the O(n)theoretical performance we ek,how-ever in practice it proves to add negligible((1%)compu-tation time for networks of n<104.This is becau the computation time is completely dominated by the bias fixing of nÀ1independent balines,even though this part of the computation is O(n).
[27]For our problem,optimal baline lection is a little more complicated than solving for the EMST,becau it might not be possible to resolve ambiguities successfully on a specific baline,and alternative spanning trees must be found.When ambiguity resolution fails,a pitfall to avoid is the testing all possible alternative balines,as this could end up being an O(n2)computation.
Fortunately,the Delau-ney triangulation limits the number of balines to b(3nÀ6),and so keeps the computation at O(n log n).
[28]Interestingly,this points to a mechanism that might result in overall computation time better than O(n)(which is emingly impossible).Consider the ca of globally dis-tributed stations.As the number of stations n increas,so the average baline length decreas,and so the number of ambiguity resolution failures decrea.Therefore,the num-ber of balines that require bias fixing computations might range from the Delauney triangulation limit of b%(3nÀ6) for small n,to b%nÀ1for large n.Since bias fixing dominates the computation time,in theory it is possible to have computation times smaller than O(n)(as a general rule, becau in practice,this will depend on specific details of the network geometry).
2.6.Summary of Theoretical Results
[29]The following now summarizes what has been learned from theoretical considerations,under assumptions that should be reasonably well satisfied by continuous GPS networks.(1)When bias fixing a network(or partly bias fixing anywhere inside a network),the centroid of that network remains fixed.(2)Estimates of the bias-fixed relative coordinates between any pair of stations are inn-sitive
to bias fixing elwhere in the network.(3)As n becomes large,the final covariance matrix resulting from full network bias fixing tends toward a block diagonal structure.(4)Selection of an optimal t of nÀ1balines to connect the network can be computed in O(n log n),which for n<104has a computation time that is negligible compared to O(n)bias-fixing computations.
[30]Synthesizing the theoretical results brings the con-clusion that independent bias fixing of nÀ1balines together with initial PPP covariance matrices for each station can be ud to construct the full network bias fixed solution for n stations and covariance matrix to a very good approximation.This summarizes the theoretical rationale for the design of the Ambizap algorithm,which is the topic of ction3.
[31]The stated assumptions led to recommendations as to situations when this theory may or may not be applicable, with the key recommendation being that bias fixing should be applied to the shortest balines between stations that have the same nominal obrvation schedules.Ultimately, the validity of applying the theory in practice must be proved empirically,as shown in ction4.
3.Implementation:Ambizap
3.1.Design Overview
[32]As discusd in ction2.6,the fixed point theorems imply that a complete network solution can be constructed as O(n)by a two-step procedure:(1)bias fix the vectors of nÀ1linearly independent balines and(2)perform a network adjustment that minimizes distortion in the bias-fixed balines,while maintaining alignment with the original PPP solutions.The output covariance matrix from the network adjustment should only include the block matrices for each individual station.This suggests that the network adjustment in step2should be performed using blocking techniques to avoid unnecessary computation of off-diagonal covariance elements.Having a minimal t of nÀ1balines,in turn,suggests a kind of network estimation filter that steps through the network tree,ba-line-by-baline(analogous to the more familiar epoch-by-epoch Kalman filter).
[33]The algorithm Ambizap has been encoded(and made freely available to rearchers),which is a stand-alone computer program consisting of a C-shell script driving FORTRAN-compiled executables.The software reads in individual station PPP solutions,and outputs individual station bias-fixed solutions(including covariance matrices) that cloly approximate the output of an O(n4)full network ambiguity resolution analysis.The software reads and writes data files in formats consistent with GIPSY OASIS II,but in principle the algorithm could be adapted to work with any PPP-capable software.The only internal depen-dence on GIPSY OASIS II modules is the core ambig
uity resolution engine,‘‘Ambigon’’[Blewitt,1989]which is only applied at the single baline level.In principle, Ambigon could be substituted for another core engine. [34]The three key design requirements of Ambizap were that(1)except for ancillary tasks that take negligible
