The Global Positioning System (GPS) consists of a constellation of 24 high-altitude satellites with very accurate atomic clocks, along with a global network of satellite tracking stations and sophisticated ground processing stations, that together provide precise navigation coordinates to any user who possesses a small, readily available GPS receiver.
The precision that is achieved depends on
and other factors.
In most cases civilian users (whose receivers can read only unencrypted, intentionally corrupted GPS signals) can expect navigation accuracy on the order of 50-100 meters. The advertised accuracy for users with military receivers, which read the encrypted GPS signals, is 16 meters. Coalition forces in Desert Shield / Desert Storm relied heavily on GPS, and U.S. military authorities praised GPS effusively for its effectiveness as a force multiplier in that conflict.
Loral Federal Systems (formerly IBM Federal Systems Division) in Gaithersburg, Maryland has been intimately involved with GPS from its concept validation phase through operations and maintenance. People in this group analyzed the physical dynamics, designed the mathematical algorithms and associated software, and performed the system integration work that culminated in the GPS ground control segment.
APL was used over the years in most major aspects of GPS design and analysis. Early in the full-scale development phase, APL was used to model the initial GPS system design, to perform design tradeoffs, to model and test candidate algorithms, and to perform error analyses to estimate future system performance. In later phases APL was used to monitor and analyze actual GPS system performance, to compare it with theoretically achievable performance, and to analyze and isolate anomalies [Allan].
Each GPS satellite continually broadcasts a signal that says, in effect, “According to my atomic clock, the time is now t.” Also each satellite periodically broadcasts a current, precise estimate of its orbital elements. These elements are determined by ground processing, using precise observations of the satellite by a global network of tracking stations whose locations have been precisely surveyed. In addition, each satellite clock is monitored and regularly calibrated by ground-based processing. All these estimates and calibrations are regularly uploaded to each satellite, which in turn regularly broadcasts them to users [Hofmann-Wellenhof, Logsdon].
Thus, in effect, a user’s GPS receiver hears the message, “At time t, by my clock, my 3-dimensional position was P.” A typical user is in direct line-of-sight of several GPS satellites simultaneously, so these messages are received from several satellites almost simultaneously.
Thus, a straightforward time-difference-of-arrival computation is sufficient to compute a user’s position quite accurately. The user’s receiver measures the time of signal arrival inaccurately, but that error isn’t significant because it is consistent across satellites. The algorithm built into the receiver estimates the user’s clock error along with the user’s 3-dimensional position. All that is required is a good simultaneous view of at least four GPS satellites.
For users with military GPS receivers, the main sources of error in computing 3-dimensional user position are as follows:
Several of these errors can be partially compensated for by the position estimation algorithm in the user’s receiver, but residual errors remain. A significant factor in the final result is how recently the satellite ephemerides have been estimated and how recently the satellite clocks have been calibrated. If these uploaded estimates are not refreshed at least daily, the resulting navigation accuracy for military users is degraded.
Civilian users face an additional source of error that dwarfs all of these. The unencrypted signals provided for civilian users have been corrupted by Selective Availability (SA) noise [Braasch], which in essence means that an unpredictable and significant error signal, usually equivalent to tens of meters of position displacement, has been added to the time signal that is broadcast from each satellite. This is the primary source of the advertised degradation in navigation accuracy for civilian users.
The presence of this SA noise generally makes it futile to design very sophisticated position estimation algorithms for civilian receivers. Without some procedure to estimate the SA noise, it is hardly worth the effort to compensate for the smaller errors listed above. The following is a generic user position estimation algorithm for a civilian GPS receiver [DoD]. (SOLVE is a subfunction that mainly computes the position of each GPS satellite, and is not listed here.)
x„ESTIMATE parms (rcvtime tdelay wephem c)„parms © inputs: ---------------------------------------------------------------- © rcvtime = time of receipt of signals according to receiver clock (sec) © tdelay = n-vector of measured transmission times (sec) from © satellites to receiver © wephem = downloaded satellite ephemerides and clock calibrations © c = speed of light (m/sec) © outputs: © x = 4-vector of (3-d user position, user clock bias error) © ------------------------------------------------------------------------- x„4½0 © initialized states (m) iter„0 L0:iter„iter+1 © ------- Filter iteration loop ---------------------- t„tdelay-x[4]÷c © adjust measured delay by user clock bias error (secf pr)„SOLVE(rcvtime wephem t) © secf = 3-by-n matrix of satellite positions (m) at time rcvtime © pr = n-vector of pseudoranges (m) from user to satellites © corresponding to time delays t d„secf-[1]3†x © line-of-sight vectors from user to each sat (m) dist„(+šd×d)*.5 © distances from user to each sat (m) h„(-³d÷[2]dist),1 © gradient matrix x„x+(pr-dist)Žh © state update (iterative least square batch filter) …(iter<4)/L0 © ------- End loop ------------------------------------
Civilian GPS receivers are now commonly used to achieve superb navigation accuracy within predetermined local areas. The usual approach is to fix a GPS receiver in a precisely surveyed position and use it as a reference for other nearby receivers. In particular, the reference receiver is used to estimate the relative instantaneous bias errors in the clocks of all the GPS satellites in view. These estimates are then used to correct the signals that are read by nearby receivers. This approach is called Differential GPS.
The effect of this method is to compensate not only for the SA noise that was added to the time signal from each satellite, but also for most other errors. Whatever errors the reference receiver produces that originate from tropospheric and ionospheric transmission delays, earth tides, relativistic effects and satellite ephemerides will apply almost identically to any other nearby receiver. I.e., such errors are “aliased” into the estimated satellite clock bias errors, and hence are canceled when the satellite clock estimates are applied to nearby receivers.
Even the differences in calibration between receiver clocks have no effect on these results. The main errors that are different between (identically designed) receivers in the local area are multipath errors, which are typically less than a meter.
In addition, using this method the satellite clock calibrations are being performed in real time, rather than being computed and refreshed only every few hours or daily. For all these reasons, Differential GPS using civilian receivers can be used to achieve navigation accuracies that are superior to those achieved by users with military receivers alone.
However, as a user moves away from the reference receiver, viewing a different combination of GPS satellites than are viewed by the reference receiver, the accuracy of Differential GPS sharply degrades. Some users have long desired a generalization of Differential GPS that could provide superb navigational accuracy over wide geographical areas. The remainder of this paper discusses this concept further, and describes the particular real-time prototype of such a system that our group has implemented, mostly in APL2.
Generalizing the concept of Differential GPS requires the coordinated processing of nearly simultaneous signals from a network of GPS “ground station” receivers [Mueller]. These ground stations are widely separated and their geolocations must be precisely known. Each of the ground station receivers reads the signals from all GPS satellites in its field of view, and transmits these input signals in real time to a central processor. The central processor uses these signals to compute instantaneous corrections to the clocks of all GPS satellites that are in the network’s field of view [Beisner 1995]. These corrections are then communicated to users in near-real time. The frequency of these computations and communications is approximately once per second.
It is shown below that for users in northern midlatitudes, such processing can reliably produce user navigation errors of less than three meters of vertical error, 95 percent of the time.
Wide Area Differential GPS requires much more sophisticated processing algorithms than does simple Differential GPS. This is because there is considerably less aliasing of error sources into the estimates of satellite clocks when multiple ground stations are involved. Any error source that does not alias in this way will generate inconsistency across the network, and will increase user navigation error, unless it is accounted for precisely.
For example, signal propagation delays from tropospheric and ionospheric effects [Yunk] cancel almost perfectly (and hence can be ignored) when only one ground station is involved and only local users are served. However, when multiple ground stations are involved across a wide area, these delays must be modeled precisely if navigation errors are to remain small for users throughout the area. A similar statement may be made, at least in part, regarding errors in estimated orbital elements, relativity effects and earth tides.
Finally, the ground station clocks all have different bias errors and drift rates. This introduces a further processing complication that is not present in single-station processing. In particular, it complicates the underlying philosophical question of what time reference should be used when all ground station clocks are of similar quality.
In order to test the concept of Wide Area Differential GPS, a simulator was developed using APL2. The objective of the simulator is to provide system navigation performance predictions for candidate systems configured with different networks of satellites (GPS plus postulated new satellites) and ground stations. The simulator has considerable flexibility for specifying the system configuration: the user can specify the number and initial ephemeris of each satellite, the number and location of each ground station, and the clock type (crystal, rubidium, or cesium) and its performance parameters for each ground station receiver and satellite clock. Clock offset errors, SA, and pseudorange (PR) measurement noise, key error sources upon which navigation performance strongly hinges, were modeled in the simulator.
The main components of the simulator are:
A typical simulation run produces performance statistics for satellite position errors and clock offset errors at the time of use by a navigator. These statistics can then be transformed to navigational performance using equations for position estimation that are similar to (but considerably more sophisticated than) the user algorithm listed above.
The data simulator is comprised of data generators for the satellite orbits, the clock noise for satellite and ground station clocks, the SA noise for GPS satellites, and pseudorange (PR) measurements for all ground-station-satellite combinations. The orbit generator permits specification of the initial satellite ephemeris, and then propagates all satellites along Keplerian orbits using the “f and g expressions” [Battin]. The clock noise generator simulates white frequency and frequency random walk noise for crystal and atomic clocks. The SA noise generator is based on the RTCA model [RTCA], a standard model for SA noise that is used in the GPS community. This generator also includes a data smoother, which, in combination with the RTCA model, allowed us to match the SA statistics observed by Chao and Parkinson [Chao] for PR measurements and their first and second differences. Following the generation of orbits and various types of noises for each element (satellite and ground station) in the system, PR measurements are simulated for each ground-station-satellite pair whenever the satellite is in view of its paired ground station. Finally, Gaussian noise is added to the PR measurements to account for receiver noise as well as other imperfectly modeled error sources such as signal propagation delays that are due to tropospheric and ionospheric effects.
An extended Kalman filter is used to estimate orbits and long-term clock offsets and drifts for all system elements in the configuration. This is performed at a relatively low rate (approximately once per hour). At each one-second measurement time the instantaneous clock offsets are estimated using a weighted least squares estimator. One of several alternative predictors is then applied to propagate the instantaneous clock offsets forward 8 seconds to the nominal time of use. Statistical measures of performance are then accumulated for the orbit and clock offset predictions relative to (simulated) truth.
The performance results produced by this simulator gave us confidence to proceed to a demonstration system that processes real GPS signals. The prototype estimation and prediction algorithms used in the simulator formed the basis from which this demonstration system was developed and refined.
As this APL simulation matured, timing benchmarks showed that the processing time (on our IBM RISC System/6000 model 580) was considerably less than the time being simulated. Thus we began to believe that our processing algorithms could be implemented in real time and still remain in APL2. This was quite surprising to some, since APL has a longstanding reputation among application developers in the wider community for being slow. However, armed with this knowledge, we now proceeded more confidently to build our real-time APL prototype.
In March 1995 colleagues on our project recorded live GPS signals simultaneously over a two-hour period from five Ashtech Z-12 receivers (located in Maryland, Florida, Utah and California). We then began to adapt the algorithms from the simulation described above to process this recorded sensor data.
Reading this recorded (binary) sensor data into APL2 and converting it to APL2 numeric form turned out, as expected, not to be difficult. However, a previous attempt to read this data by another software product had failed, and this made us wary. Therefore, we focused on the APL2 routines that converted binary data into usable form. In particular, we studied the functions PCFI, IEEEFI, PCII and IEEEFI in the public workspace 1 UTILITY. And lo, we learned to our surprise (not being programmers in the strict sense) that binary representations of fixed point and floating point numbers are different on PCs than on workstations. We silently thanked IBM’s APL2 developers for making this fact obvious to the casual observer, and we proceeded without further delay to read and process our recorded data.
Having successfully demonstrated the processing of recorded data, the team turned its attention to developing a real time demonstration system. A wide area differential GPS network was set up consisting of five monitor stations located at: Akron, Ohio; Atlanta, Georgia; Gaithersburg, Maryland; Owego, New York; and Scranton, Pennsylvania. The central processing (master) site was established at Gaithersburg.
Each monitor station employs an Ashtech Z12 GPS receiver in conjunction with a standard ISA personal computer. The master station consists of an AIX workstation (an IBM RISC System/6000 model 580) tied to an AIX network. The monitor stations are connected to the master station via 28 kilobaud modems and standard voice telephone lines.
Special software was written, running on the personal computer at each monitor station, which controls the receiver, receives data at one second intervals from the receiver, selects the data of interest and formats it in ASCII. The data is transmitted to the master station over a telephone line by means of a standard personal computer communications package.
A standard AIX communications package, running on the workstation at the master station, receives the monitor station data. Five incarnations of the program run simultaneously, each accepting data transmitted from its corresponding monitor station. These five data streams are then piped to a custom program (written in C) that merges the data from all stations and blocks it by time. This pseudorange measurement data, ephemeris data, and miscellaneous data is then logged to disk and piped to the APL processing software also running on the workstation.
The APL software executes the wide area differential GPS algorithms. These algorithms were developed by the team based on months of experience with the APL simulator, the recorded data and live data. The results are displayed live and in color with custom APL2 software based on auxiliary processor AP207.
The display shows plots of user east, north and vertical location error. Any of the five monitor stations may be designated as the user. Statistics are shown at periodic intervals for mean error, root-mean-square error and 95th percentile error for both GPS and wide area differential GPS.
As suggested above, named pipes became our media of choice to communicate the GPS signals from the C program (described above) into APL2. This communication was performed in real time, one set of merged signals per second from all satellite-receiver combinations. The following code listings illustrate how we opened the named pipe and began the communication process.
N OPENPIPE A © Opens a file for read only. If file does not exist an error occurs. © N must be a positive integer and is optional; if not defined N„1 © N can be used when referencing the file after it has been opened. © A must be a character vector of the form '[/path]filename[ ,code]' –(0=ŒNC 'N')/'N„1' CLOSE N ‘SH N –'CZ',(N„•N),'„''PR,',(((A¬' ')Ÿ¯1²~A¹' ,')/A),'''' © Modified line © –'CZ',(N„•N),'„''IR,',(((A¬' ')Ÿ¯1²~A¹' ,')/A),'''' © Original line ‘CHK–'CZ',N –'EZ',N,'„DZ',N
© Begin reading a named pipe from a C program ("meter")
HOST 'ps -ef > fn.ft' © Create list of names of active processes
A„‘FM 'fn.ft' © Read the list into variable A
HOST 'rm fn.ft' © Erase file fn.ft
I„L/¼½L„Ÿ/'meter'ºA © Identify which are "meter" processes
…(0=½I)/L2 © If none, go around
K„0
L1:K„K+1
AN„' ' NEST A[I[K];] © Get name of Kth "meter" process
HOST 'kill -9 ',•2œAN © Kill it
… (K<½I)/L1
L2: HOST 'rm meter.pipe' © Erase the pipe
HOST 'mknod meter.pipe p' © Create the pipe anew (and empty)
HOST 'sleep 5; ','meter &' © Wait 5 seconds and start meter
1 OPENPIPE 'meter.pipe,D' © Open the pipe for reading
RC„ŒDL 2 © Delay 2 seconds
© Continue processing © Process the output from meter
The following two charts illustrate the display output of our GNSS prototype and the corresponding navigation accuracies achieved.
The first chart shows the vertical and horizontal errors that were actually achieved during a specific half-hour segment of a live demonstration of GNSS that was conducted on December 14, 1995. The receivers at Akron, Atlanta, Owego and Scranton were taken to be the network of ground stations, and the receiver at Gaithersburg was deemed to be the “user”. The instantaneous vertical navigation error for this user was 2.0 meters at 95 percentile, and the maximum such error was less than 3.0 meters during this time. This was a typical result during the several hours of this live demonstration. Results have also been very similar to this when a different receiver among the five has been chosen to be the “user”.
The second chart illustrates the contrasting standalone performance of the Gaithersburg GPS receiver during this time.
The instantaneous vertical navigation error at 95 percentile was 101 meters, and the average such error was 32 meters. These results are completely dominated by the presence of unestimated SA noise.
APL2 was used successfully to implement a real-time prototype of a Wide Area Differential GPS system. This prototype has been repeatedly demonstrated for several hours at a time, with excellent and stable navigation accuracy and with no software-caused outages.
This was the first significant real-time application that our organization has developed using APL2. In retrospect, this choice of language was ideal.
Within broad limits, APL has become a very competitive language for real-time software development, particularly in a rapid prototyping environment. Whenever conditions on a project have the approximate character described above, and especially in the case of a tight development schedule, we believe APL should be considered as the primary development language. It certainly worked well for us.
We thank the management of Loral Federal Systems-Gaithersburg for supporting this project, and we gratefully acknowledge the contributions of our colleagues to the success of this project:
Richard Angelo
Howard Bergstrom
Gabriel Chang
Ming Chien
Dwight Divine
Sherman Francisco
Arthur Gower
Mark Greenlee
Neils Hansen
Brian Helmey
Peter Hoch
Charles Kengla
Timothy Parker
Michael Patrick
Todd Phelps
David Winfield
Bruce Zuver
The following sources describe and illustrate our extensive use of APL on other national projects.