Ready to Navigate!

A Methodology for the Estimation of the Time-to-First-Fix

» Download this article (PDF)

Share via:  Slashdot    Technorati    (Inside GNSS)Twitter

After three decades of increasingly widespread use, satellite navigation-based services have changed significantly, especially for general users in the mass market. New technology enablers such as assisted GPS (A-GPS), the use of massively parallel correlation, and the application of advanced positioning techniques have significantly enhanced the time-to-first-fix (TTFF) and sensitivity of today’s receivers.

Although these techniques have increased satisfaction for end users, they could partially mask many particular differences expressed among the various GNSS signals, today and in the future.

These new signals contain many innovations, including the use of longer spreading codes, new modulation techniques, and new navigation message structures using channel-coding techniques.

With such a wide variety of signals, it is essential to define criteria that enable us to understand the main differences among the signals, as well as under which conditions one would perform better than others and their relative suitability for particular applications.

Among the different performance metrics, estimating and comparing the various signals’ TTFF is an excellent tool for evaluating the design trades made on GNSS signal structures, especially those concerning spreading codes and navigation messages.

In this article we propose a methodology to account for and evaluate what happens in a conventional receiver “behind the scenes,” from the very first moment the receiver is switched on, until it is “ready to navigate”.

After presenting a theory that may be applied to any GNSS signal, we discuss simulation results obtained with some GPS and Galileo signals. Our proposed approach can be seen as an extension of the methodology described in the article by J. K. Holmes et alia, listed in the Additional Resources section near the end of this column, where the results are computed for a confidence level of 95 percent.

Definition of TTFF
With the expression time-to-first-fix, we generally refer to the time needed by the receiver to perform the first position fix, starting from the moment it is switched on.

Usually we distinguish among three different TTFF scenarios, depending on the particular status of the receiver when it is started. We refer to cold, warm, or hot starts according to the availability and validity of the data required for computing the navigation solution (satellite almanac and ephemeris parameters, send time of the received signal, previously stored PVT solutions). These three cases can be described as follows:

• Cold Start: No data is stored in the receiver; however, the position solution can be calculated by a full sky search without the use of any almanac data. For the first position fix, clock correction and ephemeris data (CED), together with a GNSS time reference (GST) must be retrieved.
• Warm Start: Valid ephemeris and clock corrections are stored in the device and the receiver just needs to retrieve the GST information from the navigation message.
• Hot Start: The warm start conditions apply; in addition, accurate position and clock error are known. The position solution can be computed without any information from the navigation message.

In addition to the availability of navigation data, TTFF performance depends on the number of visible satellites and the strength of the received signals.

In this study, we performed all our analyses with three baseline assumptions: (1) received signals have high enough C/N₀ (e.g. no bit errors), (2) the number of visible satellites is always sufficient to allow the receiver to perform a first position fix within the standard accuracy requirements; and (3) the receiver uses parallel processing on all the signals coming from the different satellites, as is common in a state-of-the-art receiver today. Under these three conditions the TTFF equals the time needed to process one of the signals coming from the different satellites.

In the following sections we present a methodology for the computation of a 95 percent probability of TTFF. This method may be applied to any GNSS signal.

The approach also may be seen as a generalization of J. K. Holmes’ method, where the TTFF is subdivided into different contributions, each of which may be estimated separately and the combination of which produces the final result.

Contributions to the TTFF
The individual contributions to the TTFF trace to the individual tasks performed by the receiver from the moment it is switched on, until the first valid position solution is reported.

. . .

Acquisition Time
We turn our discussion to the main contributors of the overall TTFF calculation and the theory necessary to compute T_acq, T_track, T_CED+GST, and T_GST.

We treat the acquisition process as a detection problem, usually performed in a navigation receiver by measuring the complex amplitude of the correlator’s output. The test statistic is thus defined and compared with a predefined fixed threshold, indicating whether the signal sought is present.

. . .

Statistical Method
. . . As is well known, the acquisition is performed following a two-dimensional search in frequency and code delay. We need to define the search space and search strategy in order to correctly estimate the acquisition time.

. . .

Statistical Results
In the simulations we performed, we assumed 30,000 correlators for all the three search strategies, common in today’s navigation receivers. Moreover, we assumed a single cell detection probability of 0.9 and a single cell false alarm probability of 10^-3.

The acquisition time for a 95 percent confidence level has been calculated for the five GNSS signals, applying the three different search techniques discussed earlier to each of the cold, warm and hot start cases. Thus, we considered nine different simulation scenarios for each signal.

. . .

Initialization of Tracking Loops
The receiver’s tracking loop (PLL, FLL, and DLL) require, before entering their stable region, a transient time estimated by studying their step response. Even if this time is dependent on the chosen loop bandwidths, generally the settling times of PLL and DLL are significantly shorter compared to the time required by the FLL.

. . .

Frame Synchronization
In today’s GNSS navigation messages, data is arranged in a multi-level structure composed of frames, subframes, messages, pages, and words.

A common feature of the various types of messages is that, after retrieving the navigation bits, a validity check, such as a cyclic redundancy check (CRC), is performed. Considering the number of bits to which this check applies, together with the field containing the checksum, the block of navigation symbols obtained by encoding these bits is called a page.

Usually the page contains also a known sequence of symbols located at the beginning and called the synchronization — or synch — word. For example all the Galileo I/NAV message pages begin with the sequence 0101100000.

The search process leading to the identification of the starting point of a valid page is called frame synchronization. This is generally achieved by the identification of a valid synch word.

. . .

Navigation Data Read Time
The time required to read the data, described by the terms T_CED+GST and T_GST, represents the time needed by the receiver to retrieve the navigation parameters, depending on the start condition.

. . .

Reading a GNSS Nav Message
In order to read the navigation message, we must first make a table of the time needed to read both CED and GST, considering all the possible points where the reading process can start.

. . .

Key Notes: Navigation Data Delivery Versus Retrieval
At this point we want to underline a few aspects regarding the delivery of the different data messages with respect to the time required to retrieve them.

. . .

Simulation Results
. . . the Galileo E1-B and GPS L5 signals show the best TTFF performance for the cold start case, while for the warm and hot start the GPS L1 C/A code outperforms all other signals.

The very low data rate of the Galileo E5a-I signal results in a quite long data read time and, as a consequence, its TTFF performance is the worst for the cold and warm start cases, where data from the message needs to be retrieved.

For the GPS L1C signal, we can see how the poor performance of the acquisition time, due to the long coherent integration and the length of the PRN codes, is counterbalanced by a very short data read time. The GPS L1C signal is, indeed, presenting the shortest data read time because of its particular navigation message structure, which allows for a very short ephemeris repetition time.

Conclusion
We have presented a methodology for the computation of the TTFF for various Galileo and GPS signals while distinguishing the cases of receiver cold, warm, and hot starts. We also considered the main contributions to the TTFF, using simulations, as well as the different acquisition search strategies.

Because the contribution of acquisition time to total TTFF can be substantially decreased by employing new algorithms and technologies, a key factor for a good TTFF performance turns out to be the design of the navigation message structure itself.

The estimates presented in the article were made under the assumption that signals were received with a high enough carrier-to-noise ratio density, such that no bit errors occurred.

We extended our analysis to consider the behavior of the TTFF in low C/N₀ environments. A detailed discussion of these results can be found in the article by M. Paonni et alia (Additional Resources).

Individuals who wish to further investigate the TTFF metric can easily implement our proposed method using GNSS performance simulation tools. We also suggest that this method could be incorporated into GNSS theoretical studies, especially those regarding next-generation systems.

For the complete story, including figures, graphs, and images, please download the PDF of the article, above.  

Acknowledgment
The work on which this paper is based has been performed in the framework of the Galileo Signals Performance Simulation Tool (GASIP) project, funded by the European Commission. The authors want to thank the technical officer of the project, Dr. Frédéric Bastide, for his sustained support during the whole activity. The contents of this paper reflect only the view of the authors.

Additional Resources
[1] Ávila-Rodríguez J. A., and V. Heiries, T. Pany, and B. Eissfeller, “Theory on Acquisition Algorithms for Indoor Positioning,” 12th Saint Petersburg International Conference on Integrated Navigation Systems, Saint Petersburg, Russia, 2005
[2] Borio D., “A Statistical Theory for GNSS Signal Acquisition,” (Doctoral Thesis, Politecnico di Torino, Italy, March 2008)
[3] Borio, D., and L. Camoriano, L. Lo Presti, “Impact of the Acquisition Searching Strategy on the Detection and False Alarm Probabilities in a CDMA Receiver,” IEEE/ION PLANS 2006, San Diego, CA, USA, 25-27 April 2006
[4] Corazza, G.E., “On the MAX/TC Criterion for Code Acquisition and Its Application to DS_SSMA Systems,” IEEE Transactions on Communications, Vol. 44, No.9, September 1996
[5] Holmes, J.K., Spread Spectrum Systems for GNSS and Wireless Communications, Artech House, 2007
[6] Holmes, J.K., and N. Morgan and P. Dafesh, “A Theoretical Approach to Determining the 95% Probability of TTFF for the P(Y) Code Utilizing Active Code Acquisition,” ION GNSS 2006, Fort Worth, Texas, USA, 26-29 September 2006
[7] Mathis, H., and P. Flammant and A. Thiel, “An Analythic Way to Optimize the Detector of a Post-Correlation FFT Acquisition Algorithm,” ION GPS/GNSS 2003, Portland, Oregon, USA, September 9-12, 2003
[8] Paonni M., and M. Anghileri, J.-A. Ávila-Rodríguez, S. Wallner, and B. Eissfeller, “Performance Assessment of GNSS Signals in Terms of Time to First Fix for Cold, Warm and Hot Start,” Proceedings of the ION ITM 2010, January 25-27, 2010, San Diego, California, USA
[9] Polydoros, A., and C.L. Weber, “A unified Approach to Serial Search Spread-Spectrum Code Acquisition – Part I: General Theory,” IEEE Transactions on Communications, Vol COM-32, No. 5, May 1984
[10] Rushanan, J. J., “The Spreading and Overlay codes for the L1C Signal, Navigation: journal of the Institute of Navigation, ISSN 0028-1522 CODEN NAVIB3
[11] Van Dierendonck, A. J., GPS Receivers, in Global Positioning System: Theory and Applications. Vol. I, Edited by B.W. Parkinson and J. J. Spilker Jr., Stanford University, USA, 1995
[12] Won, J.-H., “Studies on the Software-Based GPS Receiver and Navigation Algorithms,” (Ph.D. diss., Ajou University, December 2004)
[13] Won, J.H., and B. Eissfeller, B. Lankl, Schmitz-Peiffer A., Colzi E., “C-Band User Terminal Concepts and Acquisition Performance Analysis for European GNSS Evolution Programme,” ION GNSS 2008, Savannah, GA, USA, September 2008

Manufacturers

The data presented in this article was plotted using MATLAB from The Mathworks, Inc., Natick, Massachusetts, USA.

Copyright © 2010 Gibbons Media & Research LLC, all rights reserved.