Blog

Satellite Navigation Using Doppler and Partial Pseudorange Measurements

By Nicholas Othieno and Scott Gleason

BEFORE GPS, THERE WAS TRANSIT.  Also known as the U.S. Navy Navigation Satellite System, Transit was the world’s first satellite-based positioning system. It was declared operational in 1968 although it had been in continuous use for the previous five years. The system evolved from the efforts to track the Soviet Union’s Sputnik I, the first artificial Earth-orbiting satellite. By measuring the Doppler frequency shift of the 20-MHz radio signals received from the satellite at a known location, the orbit of the satellite could be worked out. It was then quickly realized that if the orbit of the satellite were known instead, received Doppler data could be used to determine the position of the receiver. Plans for a dedicated satellite navigation system were subsequently drawn up and the first successful test satellite launch occurred in 1960.

Transit navigation required the measurements of the satellite signal’s Doppler shift for a complete pass that could take up to about 18 minutes from horizon to horizon. At the conclusion of the pass, the latitude and longitude of the receiver, the position fix, could be determined. With five operational satellites, the mean time between fixes at a mid-latitude site was around one hour. Eventually, as the orbits of the satellites became better determined, two-dimensional position fix accuracies of several tens of meters were possible from a single satellite pass. By recording data from a number of passes over a few days from a fixed site on land, three-dimensional accuracies better than one meter were possible and Doppler-based control points for mapping were established in many countries and the Canadian north, in particular, saw significant use of Transit for geodetic purposes.

With the advent of GPS and its superior performance, Transit was decommissioned at the end of 1996. And the equivalent Russian satellite Doppler systems have essentially been replaced by GLONASS. However, this hasn’t meant the end of Doppler measurements in satellite navigation. When GPS was being developed, it was determined that Doppler measurements could provide much more accurate receiver velocities than those obtained by simply differencing pseudorange-based position fixes. But what about using Doppler measurements for the position fixes themselves? While they might be good for velocity determination, research in the early 1980s showed that the geometric weakness of GPS Doppler measurement would result in position accuracies at least a couple of orders of magnitude worse than those provided by pseudorange measurements.

So, have we outgrown the use of Doppler measurements for position fixing? Well, it seems not. In this month’s column, we’ll take a look at a GNSS positioning technique that uses admittedly inaccurate Doppler-based position fixes as a first step in producing an accurate fix using just a snapshot of recorded Doppler frequency and code-phase data with no need to decode the navigation message. Old dog, new tricks.

“Innovation” is a regular feature that discusses advances in GPS technology andits applications as well as the fundamentals of GPS positioning. The column is coordinated by Richard Langley of the Department of Geodesy and Geomatics Engineering, University of New Brunswick. He welcomes comments and topic ideas. To contact him, email [email protected].

---

Satellite navigation techniques are evolving to the point where smaller and smaller amounts of data are sufficient to estimate the time and position of the receiver. However, these new processing algorithms require innovative methods to overcome the information that is lost due to a limited duration data set. The field of assisted GNSS (A-GNSS) has boomed in recent years, proposing ways to provide navigation receivers with additional aiding information without the receiver itself having to extract it from the data contained in the off-air signals. These techniques have been wildly successful in advancing the state of the art in satellite navigation. By using nearly omnipresent, real-time Internet connections and propagating on-board ephemeris and clock models, it is possible for many navigation applications to bypass the decoding of the almanac and ephemeris data in the signals themselves. See Further Reading for more information on assisted GNSS.

However, even when using assistance, there are still obstacles that need to be overcome. For example, the shorter the off-air data set that the receiver has to work with, the greater the amount of information normally obtained from the signal that has to be obtained using a different route. In many assisted-GNSS techniques, the satellite ephemeris and clock information is obtained over an external interface. In this case, the receiver needs only to obtain the signal time of transmission from the GNSS signals, which could take between 6 and 12 seconds. For most assisted-GNSS applications, this is not a problem. However, to reduce further the data required, we will need to find an alternative method, which eliminates the need for the signal time of transmission. The first reason for wanting to do this is to reduce to a bare minimum the amount of data the receiver is required to process. The second is to allow the receiver to process limited amounts of data in stand-alone chunks, without decoding the in-signal navigation data in any way. This in turn will allow the receiver to intermittently sample the incoming data stream and process the data and estimate its time and position off-line using a self-contained short-duration snapshot of data.

It has been demonstrated that a receiver position can be estimated using only sub-millisecond code-phase (for the case of GPS L1 C/A-code) measurements and satellite ephemeris and clock data for at least five satellites. This technique is known as time-free or snapshot positioning and reduces the data needed by the receiver to the amount required for the acquisition and tracking loops to converge to a usable code-phase estimate. In this article, we propose a technique whereby the receiver initially estimates its position using Doppler frequency measurements alone and uses this coarse position estimate to satisfy the a priori position requirement needed to perform a time-free estimate. Additionally, as Doppler measurements are influenced by the receiver dynamics, a thorough examination of the errors in Doppler estimation as a function of the receiver velocity is explored.

Technique Overview

The basic processing blocks of a GNSS receiver are well known. In our research, a couple of assumptions are made regarding the overall configuration and availability of assistance data. In our operational configuration, we assume that

• An external interface is used to import satellite ephemeris and clock information for the entire GNSS constellation.
• The receiver acquisition and tracking algorithms are able to acquire the required number of satellites for this technique to work, thus providing the raw code-phase and Doppler measurements.
• The receiver clock is initialized to an accuracy of approximately 20 seconds with respect to GPS System Time.

Notably, the method proposed here does not require the receiver to synchronize and decode the navigation message data in any way, and specifically, it does not need to recover the signal transmission time. In the proposed method, the receiver can start estimating its position as soon as the signal tracking loops have settled to an acceptable accuracy. Importantly, this technique does not require any a priori knowledge of the receiver position.

The combined Doppler/time-free navigation receiver performs the processing steps indicated in Figure 1. Several important differences with regard to traditional GNSS signal processing are important. First, the processing does not assume a continuous data stream as a standard receiver would, but requires only Doppler and code-phase measurements from the tracking loops at a single epoch. Second, the time-free algorithm, like the conventional pseudorange least-squares algorithm, is performed iteratively but with an additional variable of time which causes the estimates of the GNSS satellite positions to change as the time estimate converges.

Doppler Positioning

The method for estimating a GNSS receiver position using Doppler measurements is well known and was first proposed decades ago. This technique never gained much traction in the research and user communities because it was apparent that the accuracy obtained using Doppler measurements was not sufficient for nearly all existing applications. As will be shown below, under good conditions, this technique is capable of estimating the receiver position to within approximately one kilometer. Although estimating a position without range measurements is of interest to some theoretically, practically this level of accuracy was deemed not useful. However, it was observed that this level of accuracy was within the initialization requirements of the time-free position algorithm, thus renewing interest in the technique, not as a useful product itself, but as initialization assistance to the time-free navigation technique discussed below.

The concept of overlapping iso-Doppler lines for the case of two different satellite measurements is shown in Figure 2. The frequency value around the lines of constant Doppler are the frequencies the receiver tracking loops have converged to for each satellite. With at least four satellites (an extra one is needed to solve for the receiver clock drift error), the position of the receiver can be coarsely estimated.

Briefly, the algorithm for determining the receiver position from the Doppler measurements starts by projecting the difference between the satellite and receiver velocity vectors along the normalized view vector, which is in fact the range rate. The range rate is then linked to the tracked Doppler frequencies for each satellite. However, GNSS measurements are notoriously corrupted by the imperfect receiver clocks, which in this case will introduce a bias into the measured range rate. In other words, the range rate is actually the pseudorange rate. We can now form a measurement equation for an individual satellite that includes the pseudorange-rate measurement, the receiver position estimate, the satellite position, the receiver and satellite velocities, and the receiver clock rate error.

As in the case of the traditional pseudorange least-squares position estimation, this equation can be linearized around an initial guess and a series of corrections to that initial guess solved for iteratively. Importantly, the requirements for the initial guess in Doppler positioning (as in the case of pseudorange positioning) are very generous. For receivers below the GNSS constellation, the initial guess for the receiver position can be the center of the Earth. In practice, this effectively eliminates any burden on the receiver to have any a priori knowledge as to its position.

A minimal system of four equations, one for each observed satellite, can be formed and solved recursively to provide estimates of the three position coordinates plus the receiver clock frequency or rate error. As in the case of pseudorange-based position estimation, the overdetermined case of more than four measurements can be readily solved. Note that the solution only contains a receiver clock frequency error, and not a time bias as in the traditional pseudorange solution. The next section demonstrates this technique and assesses the achievable accuracy under different receiver dynamics.

Off-Air Signal Demonstration. The Doppler positioning algorithm was first tested using live off-air signals. These signals were captured using a USB front-end sampler for about 1 minute. This raw sampled data was logged to a file and subsequently processed by our fastGPS software receiver. To act as a truth reference, the sampled data is first processed using the traditional pseudorange least-squares position-estimation technique. This position is then chosen as the true position and the file is once again processed in fastGPS but using the Doppler positioning algorithm described above. Note that the C/A-code pseudorange positioning technique is known to be accurate to the order of several meters. However, achieving high accuracy using the Doppler method is not of large concern as the goal of this initial estimation is to initialize the time-free algorithm and not act as a result in itself. So for the case of this demonstration, it is not useful to compare the Doppler positioning results to those of a pseudorange position estimation. We are principally interested in demonstrating that the errors in Doppler position estimation are within acceptable limits for initializing time-free positioning.

The off-air data was captured in Parc Mont Royal in Montreal, Canada. This data was processed normally and the pseudorange position obtained was used as the reference position for the Doppler positioning results shown in Figure 3. This position was also coarsely verified using a handheld GPS unit.

From Figure 3, it can be seen that the errors are consistently less that 1 kilometer over the duration of the data set. A total of 173 Doppler solutions were performed by the fastGPS receiver as it processed the entire sampled data file. As will be shown later, this error magnitude is well within the limits needed to initialize the time-free algorithm. The errors tend to be largest when the number of tracked satellites is low and the geometric dilution of precision is unfavorable as would be expected. The position error under normal geometries is generally on the order of a kilometer. In this scenario, GPS Time was initialized to within 20 seconds of the true time for each Doppler positioning attempt.

Dynamic Receiver Performance Evaluation. This algorithm was also tested using simulated data to assess its sensitivity to receiver dynamics. The velocity of the receiver directly influences the Doppler positioning solution estimation. This Doppler contribution will directly contribute to the estimation error and needs to be properly assessed. The impact of the receiver velocity on the accuracy of the solution was investigated using a simulated receiver under a range of dynamics conditions. As will be shown below, the accuracy of the Doppler position estimate will limit when it can be used to initialize the time-free position estimate. This is demonstrated by simulating the Doppler position estimation accuracy for a receiver gradually increasing in velocity.

The simulation was performed using our GNSS measurement simulator. This simulator was configured to generate measurements as would be received from a dynamic receiver over several hours. The simulator is initialized using two-line satellite orbital elements provided by the North American Aerospace Defense Command (NORAD) / Joint Space Operations Center and collected on four separate days.

The simulation duration was chosen to provide realistic viewing geometries at an arbitrary receiver location. The simulations were repeated at different times over a period of four days. This insures that the simulated receiver experiences a good representation of measurements under both good and bad satellite geometries. This allows for the best case, worst case, and average performance of the algorithm to be evaluated.

To simulate a receiver with increasing velocity, the receiver was set to move in one specific compass point direction (north, south, east, and west) over the duration of the simulation. The velocity of the receiver was then increased from 5 meters per second up to 40 meters per second in steps of 5 meters per second. Each velocity is maintained for 20 minutes. The receiver simulations ran for 2 hours and 40 minutes. This is sufficient to investigate the effect of velocity on the algorithm, in that four different test cases with different GPS constellation configurations provided sufficient randomness in satellite geometry.

From Figure 4, it can be seen that the error magnitude increases with the increasing velocity of the receiver. This is because the algorithm used for position determination is dependent on the tracked Doppler frequency of the received satellite signals, which are directly influenced by the receiver velocity. From the data generated for all four test cases, it can be shown that the errors in the Doppler position estimation start to exceed the initialization requirements of the time-free position technique at approximately 80 to 100 kilometers per hour. This limitation and how to mitigate it is discussed in more detail later in the article.

Time-Free Position Estimation

As discussed earlier, one of the main goals of this work is to reduce the amount of data that needs to be processed to obtain a position solution. Normally, even in the case of assisted GNSS, the receiver must decode navigation data provided by the transmitted satellite signal. This processing is needed to estimate the GPS Time and signal time of transmission and is critical to the standard pseudorange position-estimation algorithm. The Doppler positioning algorithm does not require the signal transmission time to be decoded from the signal, but it also does not produce results accurate enough to be useful in themselves. However, we use a method that produces a usable estimation accuracy and yet does not need to retrieve the GPS Time from the transmitted signal. This positioning technique is often called time-free or snapshot positioning. The technique is described in the references provided in Further Reading.

In time-free positioning, the position of a receiver is estimated without having to know the precise time of transmission of a GPS signal. This automatically removes the need to extract the time of week (TOW) from the navigation message. This is done by providing an initial guess of position to within a relatively demanding requirement, a fraction of the pseudorandom-noise-ranging-code repeat period. Also affecting the algorithm is the a priori knowledge of time at the receiver. The required accuracy of both of these quantities together is evaluated below. The a priori knowledge of the receiver position presents the more difficult limitation in an assisted-GNSS configuration. For modern receivers with access to the Internet, the time at the receiver can normally be determined to an accuracy of at least tens of seconds.

Assessment of Time-Free a Priori Requirements. Monte-Carlo simulations were run to investigate the behavior of the algorithm with varied a priori receiver position and time errors. These initialization error limits will determine under which conditions the Doppler algorithm position estimation will be suitable.

When the algorithm converges, the position estimates are on the order of what could be expected for a traditional pseudorange solution.

However, the conditions under which the time-free algorithm does not converge need to be properly understood. To accomplish this, a series of Monte-Carlo simulations were run over a wide range of a priori time and position errors. At the start of each time-free positioning attempt, the initial knowledge of the receiver position and time was corrupted by a random amount. After a reasonable number of iterations, the algorithm either converged to a reasonable solution or diverged wildly. The results indicating under what conditions the algorithm converged are plotted to illustrate the convergence region for the time-free algorithm for GPS C/A-code signals. Figure 5 shows that, as expected, the algorithm performs well when the a priori position and time knowledge are good. As these initial errors increase, the solution is more prone to diverge. The area of interest is the robust convergence zone making up a triangle towards the lower left. The Doppler position estimation must provide a solution within this range for the combined technique to work robustly.

In Figure 5, it can be noted that the solution often converges with larger than expected initialization errors (this is being investigated in more detail). However, the region of most interest is that in which the algorithm always converges. The results show that the time-free positioning algorithm will converge reliably with an a priori receiver position that is in error within the neighborhood of 100 kilometers, as long as the receiver time is kept accurate to within a few seconds. Alternatively, the algorithm will converge with a time error of over one minute, with a lessening of the position initialization tolerance down to about 50 kilometers.

Depending on the application and receiver capabilities, a compromise must be chosen to achieve the a priori initialization limits. From the results in Figure 5, it can be seen that for many applications, a Doppler position estimate will be more than sufficient for the a priori position initialization, thus eliminating the need for any a priori position knowledge for many applications with moderate receiver dynamics.

Combined Doppler and Time-Free Positioning

We have shown that Doppler positioning can estimate a receiver position to within about 100 kilometers for receivers in low and medium dynamics environments (at and below approximately 100 kilometers per hour). Importantly, the Doppler positioning algorithm can be performed using an initial estimate of the receiver position at the center of the Earth.

Subsequently, it was shown that time-free positioning requires an a priori position estimate that is accurate to within about 100 kilometers of the true position and a receiver time that is accurate to within a few seconds to assure algorithm convergence. If the a priori position estimate goes beyond 100 kilometers, there is a probability of divergence of the algorithm even with accurate receiver time. A coarse time accuracy threshold of 10 seconds is selected in this case as it is believed that GNSS receivers with assisted-GNSS capability will not have a lot of difficulty syncing their clocks to this accuracy.

The next step is to update the receiver processing steps to allow for the Doppler and time-free algorithms to be integrated together. In the combination algorithm, the Doppler estimation is performed first and then simply fed into the time-free algorithm as shown in Figure 1 and in more detail in Figure 6.

From Figure 6, it can be seen that three inputs are required for the Doppler positioning algorithm: the initialization time estimate, satellite Doppler measurements, and satellite ephemeris and clock information. The time estimate is obtained from the receiver’s clock whose accuracy should be within 10 seconds of the true GPS Time. The satellite Doppler measurements (a minimum of four) are provided by the tracking functions of the receiver. The ephemeris is assumed to be locally stored at the receiver using an assisted-GNSS external data link.

Subsequently, the time-free positioning algorithm then inputs the Doppler estimate as its initial a priori estimate of the receiver position. The existing assisted-GNSS satellite ephemeris and clock information as well as the coarse estimate of the GPS Time kept by the receiver are also available for the time-free estimation.

The code-phase measurements from at least five GNSS satellites form the last piece of the puzzle. They are obtained as a direct output of the receiver delay lock loop. In the case of GPS C/A-code signals, these will be up to 1 millisecond in length, with longer durations possible with other GNSS signals as discussed below.

Operationally, the Doppler positioning module can be run once, tested for convergence, and then the resulting position estimate fed back into the time-free position estimation. However, for our test cases, the Doppler algorithm was used repeatedly to initialize the time-free algorithm to more thoroughly exercise the process.

What proved to be a robust test on the convergence of the time-free algorithm was a simple comparison of the final output to the initial Doppler-determined input. When this difference was below a single code-sequence repeat period, the algorithm had in all cases converged.

The divergent cases regularly produced differences of significantly larger magnitudes.

Comparison to Traditional Estimation. The combined algorithm was tested on multiple sets of off-air data from the U.S., Canada, and the U.K. The root-mean-square error of the horizontal position estimates and the mean geometric dilution of precision during the observations for each of the tested off-air data sets are shown in Table 1. The error magnitudes of the resulting position solutions are on the same order for both the standard pseudorange least-squares and time-free position estimates. This is to be expected, for if the time-free algorithm computes the correct integer milliseconds, the algorithm will converge to nearly the same solution as the traditionally determined pseudoranges since the code-phase measurements are identical. In this comparison, both the pseudorange and combined Doppler/time-free algorithms were started assuming an initial receiver position at the center of the Earth. As a final check that this method provides comparable results to those from the traditional pseudorange case, we directly compared the error magnitudes of the two methods over a stretch of the same data. This will also prove to illustrate how time-free positioning is capable of more quickly estimating the position than other methods since it does not need to decode the satellite signal’s navigation message.