Innovation: Faster, Higher, Stronger

by OMA | Friday, October 9, 2015

Proposed GNSS Navigation Messages for Improved Performance

By Wentao Zhang and Yang Gao | October 8, 2015, GPS World — Time-To-First-Fix, commonly known by the initialism TTFF, is the elapsed time between the powering on or starting up of a GNSS receiver and when it successfully computes either a two-dimensional (height constrained) or three-dimensional position fix and sets its clock to the correct time. A three-dimensional fix requires simultaneous receiver measurements on the signals from a minimum of four satellites along with the satellites’ positions (ephemerides) and the offsets between the individual satellite clocks and the GNSS system time.

TTFF depends crucially on the availability and timeliness of the satellite ephemerides and clock information when a receiver starts up and, accordingly, there are three types of start-up with correspondingly different TTFF.

A cold start (sometimes also called a factory start) occurs when the receiver has no knowledge of its current position, time or the positions of the satellites and their clock offsets. The receiver must do a blind search of the sky trying different possible Doppler frequency shifts and pseudorange delays for all the satellites in the constellation. Once satellites are found and tracked, the ephemerides and clock information must be collected. This is repeated in each satellite’s navigation message every 30 seconds. In addition, the information on the offset between GNSS system time and UTC must be collected along with the ionospheric delay correction parameters and the almanac (an approximate ephemeris for all active satellites in the constellation) to be used for faster subsequent signal acquisition. This data is only transmitted once in the 12.5-minute-long navigation message. Therefore, the TTFF for a cold start can take up to 12.5 minutes and even longer especially if the GNSS signals are hard to acquire such as in obstructed environments.

A warm start, or what we might call normal operation, occurs when the receiver has some a priori information on its position, the time and the approximate locations of the satellites. Typically, this means knowing the receiver position to within a few hundred kilometers, time to within 10 minutes or so, and a reasonably fresh almanac. Armed with that information, a receiver knows which satellites should be visible to it and can quickly acquire and track satellite signals and obtain the satellite ephemeris and clock information. Since that information is repeated every 30 seconds, TTFF for a warm start can be 30 seconds or less.

A hot start occurs when a receiver is powered on after being off and stationary for a short interval and it therefore has a very good estimate of its position and the current time and valid satellite ephemeris and clock data. TTFF for a hot start, therefore, is typically only a few seconds. This mode of receiver operation would also apply to scenarios where all signals are temporarily lost in road or rail tunnels or where a number of signals are momentarily blocked by obstructions causing a break in position fixing.

Fast first fixes were traditionally only possible when a receiver had a clear view of the sky and could readily acquire the navigation messages. Pseudorange measurements can be made, however, even if satellite signals are somewhat attenuated in strength to the point that navigation messages cannot be acquired. Position fixing in this case would be possible if the receiver could obtain the navigation information from elsewhere. Over the past decade or so, assisted GNSS techniques have been developed to provide frequently refreshed navigation information over cellular telephone networks, for example. But would there be a way to achieve fast first fixes autonomously without reliance on these assisted techniques? Not with the signals presently being transmitted by either the mature or nascent constellations, it seems, but in this month’s column, we look at proposed changes to the way navigation messages are formulated that could result in a future satellite navigation system providing faster fixes effectively giving receivers higher sensitivity and stronger performance.

Despite some differences in their structures, different GNSS broadcast navigation (NAV) messages usually consist of two parts: immediate (primarily ephemeris) and non-immediate (primarily almanac) data. The immediate data is repeated at a much shorter interval than the non-immediate data, and expires much sooner than the non-immediate data. Taking GPS as an example, the civilian navigation (CNAV) messages consist of five subframes with each lasting six seconds, as depicted in FIGURE 1. The first three subframes provide the ephemeris, with the content repeated every 30 seconds and updated every two hours, while the last two subframes provide the almanac for each satellite in 25 pages, with the content updated nominally every six days (according to the GPS Interface Specifications document), but updates are actually daily.


Depending on the accuracy of receiver time and the availability of previously collected ephemerides (the immediate data) when powered on, GNSS user equipment (UE) might experience cold, warm or hot starts, among which the warm start is the most common case. In the widely accepted definition for warm start, no valid ephemeris is available, but the receiver time is roughly known at startup.

As depicted in FIGURE 2, the position fix sequence by a standalone GNSS UE normally consists of signal acquisition, tracking, bit synchronization, frame synchronization, ephemeris downloading, measurements taking and position computation. In performing a regular warm start, signal acquisition usually takes only a few hundred milliseconds for a GPS device in open-sky environments. However, under weak signal conditions, signal acquisition might take much longer (say a few tens of seconds). Once the signal is acquired, the tracking loop is activated, and immediately after the signal is pulled in the process of data-bit synchronization is started. This process takes a few hundred milliseconds to several seconds depending on signal strength and algorithm efficiency. In a stable tracking status, the navigation bits are collected sequentially one by one. Collecting a complete copy of a GPS ephemeris takes about 18 seconds in open-sky environments but may take minutes or even forever in weak signal environments due to an increased bit error rate (BER). As soon as the ephemeris downloading from three to four satellites is completed and the measurements are made, the user position fix usually can be obtained immediately. Therefore, in weak signal environments, the obstacles to fast time-to-first-fix (TTFF) are primarily signal acquisition and ephemeris downloading, and in open-sky environments the obstacle mainly lies in the time needed for ephemeris downloading.


For a GNSS UE in an open-sky environment on the Earth’s surface, the minimum received signal level for GPS L1 is around -130 dBm according to the interface specifications. For other GNSS signals, the nominal received signal levels are approximately the same.

However, in some extreme cases, such as urban canyon, foliage and indoor environments, the signals finally arriving at a receiver’s antenna could be heavily attenuated by 30 dB or even more. Working under such conditions requires GNSS UE to have high-sensitivity capability.

When the GNSS signal strength drops to a certain level, it causes immediate difficulties in the GNSS receiver tracking loop and for ephemeris downloading. Firstly, the parameters of the tracking loop, designed for normal signal strengths, are no longer optimum for either obtaining enough gain for signal detection or for maintaining signal tracking. Secondly, BER increases with decreasing signal strength. When the signal carrier-to-noise-density ratio drops below 27 dB-Hz, even if signal tracking is maintained, the increased BER would make it difficult for successful decoding of NAV messages.

Sensitivity improvements for a GNSS receiver can involve contributions from the antenna, the RF front end and baseband signal processing. In the signal processing, to obtain adequate processing gain in signal-to-noise ratio for signal detection, combined coherent and non-coherent integrations are needed. An approximate relationship for calculating such processing gain is given in Equation (1). Considering that non-coherent integration is subject to squaring loss, for a fixed total integration period (TI), increasing the coherent period (Tc) is more efficient for achieving higher processing gain. However, without knowing the navigation bits, the coherent integration is limited within a 1-bit period or 20 milliseconds for GPS signals.

Eq-3  (1)

To improve sensitivity to -160 dBm, coherent integration over multiple bits is desired. Therefore, valid navigation bits as well as the bit boundaries are needed for data wipe-off. For this purpose, previously collected navigation bits can be directly used if they are still valid or fresh navigation messages from different sources, including ephemeris and almanac, can be used to recover the navigation bits.

GNSS Assistance Technologies
The existing efforts for improving TTFF and sensitivity for GNSS UE include developing assistance systems and implementing new algorithms for UE. The concept of AGPS goes back to the late 1990s when lots of patents were filed and then granted in early 2000s. Seeing the challenges of TTFF and sensitivity for standalone GPS devices, the general idea from the patents is to provide assistance information to GNSS UE, such as time, rough location, a list of visible satellites, the Doppler shift of each satellite, ephemerides and so on, in a way to speed up each stage in the process of a position fix (Figure 2). With a series of AGPS specifications embodied in the 3GPP and Open Mobile Alliance standards since 2001, AGPS-enabled products have become quite popular in the GNSS marketplace.

The assistance data definitely brings enhanced performance in TTFF and sensitivity for GNSS UE, but it is a challenge when network connectivity is not available. A technology often referred to as ephemeris extension (EE) was introduced by Global Locate and SiRF, which enables fast TTFF and high sensitivity for GNSS UE even without network connectivity. According to the descriptions of the long-term orbit used by Broadcom and InstantFix used by CSR, both are based on orbit determination theory and provide alternative ephemerides with a validity period extending to a few days, rather than two hours for the regular GPS ephemerides. As of today, a variety of EE products are available from many companies and research institutes, and EE has become a standard feature for GNSS products in the market place.

Limitations of Existing GNSS Assistance Technologies
In spite of the benefits to TTFF and improved sensitivity, the assisted GNSS (AGNSS) and EE technologies have obvious limitations, as detailed in TABLE 1. Building and maintaining the AGNSS infrastructure require significant efforts and continuous cost. Any AGNSS-capable UE, unlike standalone GNSS UE, are tied to good signals from the subscriber cellular phone networks to get assistance data on time, which substantially limit their areas of operation. The EE technologies consist of server-based and client-based modes. Client-based EE is good for standalone UE, but the accuracy is subject to the validity of the embedded Earth orientation parameters (EOPs), and the quantity and quality of the local data collection. Server-based EE is able to provide better accuracy, but it also needs support from the global infrastructure for data collection and is subject to network connectivity. Table 1 clearly indicates that AGNSS and EE can only be beneficial under certain prerequisite conditions, such as with network connectivity and data availability. In other words, even with the above-described technologies, fast TTFF and high sensitivity may still not be obtainable when those prerequisite conditions are not met, which is not uncommon in practical use.


Suggested New GNSS NAV Messages
The fundamental cause of the problem related to TTFF and sensitivity, in our view, lies in the congenital weakness of the design of the existing GNSS NAV messages. Taking GPS as an example, the contents of GPS subframes 1–3 are updated every two hours, although the ephemeris is valid for up to four hours. It is challenging for standalone GPS UE working in weak signal environments to catch up with such frequent ephemeris updates. Working properly during the past two hours does not mean that the UE can work properly in the next two hours if ephemerides are not downloaded in time. The NAV messages received two hours ago cannot be used for data aiding in the subsequent two hours to improve tracking sensitivity. For startups under normal signal conditions, the UE, if missing the start of subframe 1, have to wait 30 seconds to get to the next subframe 1 to download a complete copy of the ephemeris. Successful startups four hours ago also do not help much to reduce the TTFF in the subsequent startups, as time is needed again for ephemeris downloading.

For other GNSSs, some specifications of their NAV messages are listed in TABLE 3. According to these specification, the downloading of Galileo ephemerides takes at least 30 seconds, and if the start of the first ephemeris page is missed, it will take at least 50 seconds to get a complete copy. So, from this perspective, the Galileo TTFF for standalone devices is expected to be longer than that for GPS. As to BeiDou, given the high degree of similarity between BeiDou D1 and GPS CNAV messages, it is expected that for standalone BeiDou UE, TTFF is also similar to standalone GPS UE. For GLONASS, the downloading takes just about10 seconds, and it will take about 30 seconds to get a complete copy of the ephemeris if the start of the first ephemeris string is missed. Therefore, in this regard, the GLONASS TTFF for standalone devices is expected to be the fastest among the GNSSs. It is worth noting that the GLONASS ephemeris, unlike that of other GNSSs, comprises Cartesian coordinates, velocity components and solar/lunar gravitational accelerations at the reference time, with the content valid over about 0.5 hours. Upon receiving the ephemeris, the UE is to calculate the satellite orbit by numerically integrating the motion equations that include the second zonal geopotential coefficients through a fourth-order Runge-Kutta method. Since the designed NAV messages for GPS, GLONASS, BeiDou and Galileo are all valid for only short periods (see Table 3), they are all subject to the aforementioned limitations.


The common weaknesses in the NAV messages of GPS, GLONASS, BeiDou and Galileo described above can be overcome and fast TTFF and high sensitivity can be facilitated through the design of new NAV messages, when the following guidelines are followed:

  • Update interval, as short as possible
  • Repeat interval, as high as possible
  • Length of ephemeris content, as short as possible
  • Ephemeris life expectancy, as long as possible

Let’s take a closer look at the GPS CNAV messages in terms of the above four guidelines. In the GPS CNAV messages, the primary content includes:

  • Satellite clock
  • Satellite ephemeris
  • Ionosphere information
  • UTC parameters
  • Almanac

Two types of atomic clocks, rubidium and cesium, with stabilities of 10-12 to 10-13are used on the GPS satellites. Given such stabilities, it is possible to have the clock parameters updated at an interval much longer than two hours, without introducing significant errors in the pseudorange observations. For the Keplerian parameters in the GPS ephemerides, they are derived from the fitting of four-hour orbit curves. The orbit, represented by the Keplerian parameters plus perturbation corrections, gives the overall best fitting of the whole orbit segment. If fitting over a longer orbit curve, it would be harder for the fitted orbit to agree well with each small portion of the original orbit. A set of Keplerian orbital parameters can be a good approximation of a short orbit segment (say four hours), but can hardly be the case over a long period (say 24 hours). Frequent updating of the ephemeris content is therefore indispensable in order to guarantee the orbit accuracy using this approach. As a result, there is not much room for extending the ephemeris update interval or equivalently to lower the update frequency.

GPS CNAV messages include ionosphere information using the Klobuchar model, UTC parameters for relating GPS Time to UTC, and the almanac providing the rough orbits for all GPS satellites in service. According to the GPS Interface Specifications, all these messages will be updated at least once every six days, but they are typically updated on a daily basis.

Based on the above analysis, it can be concluded that, in GPS CNAV messages, the only part that changes frequently is the ephemeris (primarily the Keplerian parameters). To facilitate fast TTFF and high sensitivity, we should reduce the update frequency of the GPS CNAV message. For that, the key is to find a way to minimize the update frequency of the ephemerides.

Taking a close look at the satellite orbit may help us find a hint. For a satellite in space, given the initial conditions (position, r, velocity, r-dot, and so on) in Equation (2) at time t, the succeeding orbit, r(t), can be obtained by integrating the accelerations, r-twodots, in Equation (3), as illustrated in Equation (4).

Eq-2  (2)

Eq-3  (3)

Eq-4  (4)

To ensure the accuracy of the derived orbit, r(t), the forces exerted on the satellites that result in the acceleration, r-twodots(t), should be well modeled. The forces are both gravitational and non-gravitational.

Standard gravitational force models embedded in UE can be independently used for years without introducing significant accuracy loss. As to the force of solar radiation, it is related to the reflectivity and attitude of the solar panels of the satellite, which can also be well modeled by some slow-varying and satellite-dependent parameters. If a set of such solar radiation parameter(s) along with some satellite initial conditions (position and velocity) can be provided with a certain period (say one day), the satellite orbit can be derived in the UE through some embedded force models.

By now, we have found what we are looking for — namely, the solar radiation parameter(s) together with the satellite initial condition at a reference time, which can be the ideal content for our new ephemeris that can deliver a long orbit even if updated at a low frequency.

Consider that, at any epoch, the satellite position and velocity expressed in Cartesian form (rr-twodots) can also be identically expressed in Keplerian form through the set of standard elements as is currently done with GPS.

The initial condition expressed in Keplerian form may give a better idea of what the orbit looks like and may have advantages for message encoding and sanity checks when it is adopted as the ephemeris content.

The above fundamental analysis leads us to propose the new GNSS NAV messages provided in TABLE 2, which comply with the previously mentioned guidelines and therefore should be able to inherently facilitate fast TTFF and provide UE with high sensitivity.

Note that the EOP data in the above table, used for relating coordinates in an Earth-centered Earth-fixed (ECEF) frame and those in an Earth-centered inertial (ECI) frame, are slowly varying parameters. The update interval for each part of the new NAV messages in Table 2 is one day, but for the almanac part, the update interval can be possibly extended to a few days similar to that currently used for GPS. In the ephemeris part, the proposed messages contain the six basic Keplerian elements and one solar radiation parameter for a selected reference time (t0). Once the ephemeris is downloaded, the six Keplerian elements can be immediately transformed to Cartesian position, r(t0), and velocity, r-dot(t0), in the ECEF frame, and further converted to the initial condition in the ECI frame to derive the entire orbit through Equation (4).


Compared to the current GPS ephemeris, Table 2 contains many fewer parameters, so it is possible to have the new GNSS ephemeris and clock data packed in only two subframes, assuming that the data rate, word structure and subframe length are the same as for GPS CNAV messages. For the remaining parts listed in Table 2, they can be packed into multiple pages of 2 subframes in a similar way as the pages of subframes 4 and 5 in GPS CNAV messages. Therefore, we have the frame structure of the proposed new GNSS NAV messages as depicted in FIGURE 3. Considering that the contents of the first two subframes play a primary role in TTFF, the pages of subframes 3 and 4 are not further discussed here.


Advantages of the New NAV Messages
The content of the new NAV messages have been proposed in the last section, but the detailed format design is beyond the scope of this article. In TABLE 3, a comparison of the new NAV messages to the current GPS, GLONASS (GLO), BeiDou (BD) and Galileo (GAL) messages is presented. For the convenience of comparisons, the same data rate (50 bits per second [bps]) and the same length of subframe (6 seconds) as for the GPS CNAV messages have been used for the new GNSS NAV messages.

Compared to other GNSS NAV messages, the new NAV messages have a smaller size, but the contained ephemeris has a longer life and, as a whole, the new NAV messages just need to be updated once every 24 hours. To help understand the advantages of the new NAV messages, we have made several comparisons.

Standalone UE, New GNSS vs. GPS. For any new GNSS that deploys the new NAV messages, the UE just need to download the ephemeris from the satellites once in a whole day, whereas current GPS UE need to do it 12 times. In each downloading, it takes about 18 seconds for current GPS UE compared to about 12 seconds for the new GNSS UE. So there is no doubt that, from the TTFF perspective, the new NAV messages have incomparable advantages over the current GPS ones. Once a complete copy of the new NAV messages is downloaded, it can be used for data aiding in tracking loops for the rest of the whole day, even without network connections in weak signal environments. However, for current standalone GPS UE, they have to be in a strong signal environment to acquire fresh NAV messages every two hours. Otherwise there could be no position fix available in the next two hours due to the stale NAV bits and expired ephemerides. So, from a sensitivity point of view, a GNSS with the new NAV messages (referred to as new GNSS below) will also have incomparable advantages over GPS.

Assisted UE, New GNSS vs. GPS. There are three purposes for assistance information for mobile devices: 1) to expedite signal acquisition; 2) to save time in ephemeris downloading; and 3) to have navigation bits for data aiding in the tracking loops. For assisted GPS UE and assisted GNSS UE with the new NAV messages, there is not much difference in the first aspect, as the assistance data, such as a satellite vehicle list, Doppler frequency, code phase, location and time, are common to both. For the second and third purposes, the assistance data sent from the assisting network to the UE are only needed once per day using the new NAV messages because they are updated only once per day. For assisted GPS UE, the assistance data are needed once every 2 hours, which means that GPS UE need frequent network connectivity and more network bandwidth for data transportation. In addition, as the size of a GPS frame is larger than the frame of the proposed new NAV messages, the time delay in transporting the assistance data will be longer in a GPS assistance network.

New GNSS, Standalone vs. Assisted. When the new GNSS NAV messages are deployed, as the messages are only needed to be downloaded once a day, the assisted UE mostly show advantage in sensitivity and the required time for signal acquisition. Since signal acquisition is difficult only when the signal becomes weaker than a certain level, the performance of standalone and assisted new GNSS UE is expected to be comparable under normal signal conditions. Under weak signal conditions, as long as the NAV messages are received once a day, the performance in tracking sensitivities for both standalone and assisted UE is also expected to be comparable.

Feasibility Considerations
Since the proposed update interval for the new NAV messages is 24 hours, a period much longer than that currently used by all constellations, some immediate concerns may arise, such as:

  • Is the orbit/clock derived from the ephemeris good enough for 24 hours?
  • Is the calculation load for deriving satellite orbits affordable for a UE?

The advancement in orbit determination and EE technologies can help relieve the worry on the first concern. For the JPL predicted orbit and clock states, it is claimed that the user range error (URE) of around one meter for one day and URE of less than 10 meters for seven-day predictions can be obtained.

For a future GNSS that deploys the proposed new NAV messages, an orbital determination center (ODC) on the ground should be able to provide orbit predictions better than or at least comparable to those already obtained. Every 24 hours, as the intermediate results of the orbit predictions are obtained in the ODC, the new ephemeris data can be extracted and packed as one part of the new NAV messages. Once uploaded to the satellites and broadcast to GNSS UE on the ground, they can be used in deriving satellite orbits. The accuracies of the orbits/clock finally derived by GNSS UE will be subject to the accuracy of ephemeris, clock coefficients, EOPs and force models embedded in UE.

The EOP data, describing the irregularities of the Earth’s rotation, are needed for coordinate transformations between ECEF and ECI, so the up-to-date EOP data carried in the new NAV messages ensures no accuracy loss in such transformations. For the force models embedded in GNSS UE, accuracy is not a problem as long as they are the same as that used by the ODC.

As to the satellite clock, it is desired that, even if the clock coefficients are updated once per day, the accuracy of the predicted clock is still sufficient for navigation. For the current spaceborne clocks on GPS satellites, they are primarily rubidium atomic clocks with stability not better than about 10-13. The advancement of atomic clock technologies is fast, especially in recent years, and the era of rubidium, cesium and hydrogen maser clocks is evolving to ytterbium and even optical atomic clocks. As of today, atomic clocks as stable as 10-18 have been operated in laboratory settings. A project called the Space Optical Clock aims to put a lattice optical clock with a stability of 10-16 on the International Space Station by 2020. So it is foreseeable that new GNSSs should be able to deploy atomic clocks with stability several orders better than those currently deployed. At the stability of 10-16, the clock will only introduce millimeter-level errors in ranging in a 24-hour period. With such a stable satellite clock, there should be no accuracy concerns with clock data being updated once per day.

Once the broadcast ephemeris is received by a UE, numerical integration can be started to derive the satellite orbit. During the numerical integration, the calculation load is primarily dependent on the following factors: 1) the length of numerical integration; 2) the numerical integration step size; 3) the order of the integrator; and 4) the complexity of local force models. Regarding the run-time necessary for orbital numerical integration on an embedded system, some published results indicate that a three-day prediction (numerical integration) takes only around 0.6 seconds on a 600-MHz processor with floating point unit. So a 12-hour integration would take only about 0.1 seconds on the same platform. As of 2014, for the popular high-end smartphones on the market, the speed of embedded processors ranges from 1.2 to 2.5 GHz with dual- or quad-cores. Considering the drastically growing computation power of mobile processors and the potential of further algorithm optimizations in orbital integration, the calculation load of numerical integration for a 12-hour interval is not at all an issue on a mobile device today, much less in the future.

The GPS system designers four decades ago might not have realized that GPS would become so popular in the 21st century. Fast TTFF and high sensitivity have become standard requirements. The growing power of the application processors has also been beyond the imagination of people 40 years ago. So in their design, fast TTFF and high sensitivity might not have been given too much attention. The GPS modernization program is an attempt to meet the growing expectation on the system performance in the applications for today and the near future. In view of this, there is no reason not to give special considerations to inherently support fast TTFF and high-sensitivity applications when investigating and designing a new GNSS. Certainly, such efforts can be found both in recently launched GPS (Block IIF) and Galileo satellites, such as the pilot channels, but navigation under weak signal conditions for future standalone GPS and Galileo devices is still susceptible to the frequent change of NAV messages (see Table 3).

In this article, we have analyzed the benefits and limitations of the existing technologies (AGNSS and EE) widely adopted to improve TTFF and sensitivity performance, and pointed out the weakness in current GNSSs. Instead of seeking solutions in the user terminal, this article proposes to deploy new NAV messages on future GNSSs, with the contents updated once a day, to inherently facilitate fast TTFF and high sensitivity in the standalone GNSS UE. A future GNSS that uses such new NAV messages will have significant advantages for both standalone and assisted UE.

This article is based, in part, on the paper “New GNSS Navigation Messages for Inherent Fast TTFF and High Sensitivity” presented at the 2015 Pacific PNT Meeting of The Institute of Navigation, held in Honolulu, Hawaii, April 20–23, 2015.