Innovation: Integrity for safe navigation

February 12, 2020 - By Landon Urquhart, Rodrigo Leandro and Paola Gonzalez

A key feature of a new high-accuracy GNSS correction service

Innovation Insights with Richard Langley

INTEGER VITAE SCELERISQUE PURUS. So wrote the Roman poet Horace at the beginning of one of his odes — one which, incidentally, was sung by college choirs at one time. It is usually translated as “upright of life and free from wickedness” and is just about the only common Latin quotation in which we find the word “integer.”

Besides upright, the word can be translated as unimpaired, perfect or whole. It is this latter meaning that the English mathematician Thomas Digges appropriated to describe whole numbers. The modern mathematics definition of the set of integers includes the additive inverses of the whole numbers plus zero. We have to worry about the integer nature of carrier-phase ambiguities when trying to achieve high-precision GNSS positioning but that is a story for another day.

The Latin word integer is the root of the English word integrity. In everyday speech, integrity means the quality of being honest or trustworthy (and having strong moral principles). But it is also used to describe something that is unimpaired or uncorrupted, especially in regard to electronic data such as that provided by a navigation system.

As I wrote in an Innovation column back in 1999, “The performance of any navigation system is characterized by its accuracy, availability, continuity, and integrity. From a safety point of view, integrity is arguably the most important factor. Without some assurance of a system’s integrity, we have no way of knowing whether the information we receive is correct: How are we to know whether a navigation system is actually achieving its advertised accuracy and not misleading us with faulty information?” Navigation systems that provide safety-of-life services must ensure a very high level of integrity. For example, the Wide Area Augmentation System (WAAS) continuously assesses the integrity of GPS satellite signals as well as its own corrections, warning WAAS users when a failure is encountered within about 6 seconds of failure. This helps to ensure that aircraft do not use misleading data that could potentially create hazards.

And now, high-precision GNSS positioning technology using real-time augmentation is being adopted for autonomous applications in the automotive, rail, aviation and marine industries. These applications need high integrity in their position determinations in addition to high accuracy. As with the pioneering non-autonomous aviation use, augmentation services for the new market will need to monitor many aspects of their service to ensure a high level of integrity including the high-end data processing algorithms, real-time data transmission, end-to-end encryption, and functional safety assurance. This will be a challenging task that will require a multi-disciplinary approach, deep understanding of GNSS error modeling and risk assessment.

In this month’s column, we look at the design, construction, operation and performance of the first safety-critical, high-accuracy augmentation service created specifically for autonomous applications.

In addition to the need for high accuracy, the adoption of high-precision GNSS positioning technology for autonomous applications in the automotive, rail, aviation and marine industries has brought with it the need for high integrity and reliability. GNSS integrity concepts had their beginning in safety-critical applications in the aviation and marine industries, which have used GNSS to provide absolute position for precision runway approach, enroute navigation, port approaches, open sea and coastal waterway navigation.

For precision GNSS users (those using precision or high-end equipment) in the surveying, construction and agriculture industries, the focus has primarily been on accuracy. Over the past decade, real-time networks have been developed to offer sub-2-centimeter performance to end users. Although some integrity information has been provided, it has often been in the form of disturbance indices that network operators can use to inform users of suspected down time or periods of poor performance. But the information lacks a functional safety component. Additionally, this information has not typically been integrated in real time into position engines to aid in the generation of reliable integrity parameters for the end users.

Although GNSS does have limitations, particularly in urban environments, GNSS equipment is one of the few sensor types available to system integrators that can provide absolute position in autonomous applications.

This realization — combined with the further miniaturization, lower power consumption and expansion of inexpensive multi-frequency, multi-constellation GNSS chips capable of real-time-kinematic- (RTK-) style processing — has made the adoption of GNSS for mass-market applications very appealing.

Most mass-market applications don’t have the same accuracy requirements that drive the professional high-precision market. TABLE 1 summarizes applications that can benefit from a high-precision GNSS correction service. In most cases, decimeter-to-meter-level accuracy is typically acceptable. Reliability becomes more critical for these applications.

Table 1. Applications that can benefit from a high-precision GNSS service with integrity. (Data: Sapcorda)

The integrity demand, which we define as the degree of difficulty an application poses to the integrity monitoring system, is based on the required accuracy, availability, failure rate and continuity requirements of the application. Applications with a high integrity demand pose the most difficult challenges.

With the spread of autonomous applications in various areas, the likelihood of liability and legal cases being decided based on PVT data provided by the systems is high. This eventuality brings with it a need for a non-proprietary open standard for ensuring consistent implementation of the integrity information and functional safety along with the separation of end-user and provider responsibility. In this article, we describe the requirements and concepts for a high-precision GNSS correction system with high integrity.

SYSTEM OVERVIEW

Our Sapcorda correction service provides high-precision GNSS correction data on a continental scale. Its core component is an underlying tracking network of reference stations used to generate the precise corrections. The reference stations operate in real time and continuously transmit their data to the data control center. The data control center processes the data, computing orbit, clock, instrumental bias and atmosphere corrections and integrity information, and then encrypting the data before broadcasting it to the end user (see FIGURE 1).

FIGURE 1. High-level description of Sapcorda’s GNSS correction service. (Image: Sapcorda)

The corrections are broadcast in the Safe Position Augmentation for Real Time Navigation (SPARTN) format developed by a consortium of GNSS manufacturers and service providers, via two communication channels, L-band and the internet. The data is then received by the end users who must decrypt it before it is used in processing. The SPARTN correction format consists of a set of messages that broadcast the GNSS corrections in a state-space representation. With our network, Sapcorda can offer a high-accuracy positioning service with fast convergence. An example of positioning performance for a monitoring station in Sapcorda’s European network coverage area is shown in FIGURE 2. The typical accuracy level is close to that of traditional network RTK services.

FIGURE 2. Horizontal position performance for a monitoring site in Europe using Sapcorda’s high-precision service. (Image: Sapcorda)

The system provides coverage for both North America and Europe as shown in FIGURE 3. Unlike traditional local or regional network RTK systems, Sapcorda’s network provides seamless coverage on the continental scale and operates in broadcast-only mode.

FIGURE 3. Initial operation coverage of Sapcorda’s high-precision GNSS correction service. (Image: Sapcorda)

INTEGRITY CONCEPTS

The integrity of a system can be described as the trustworthiness of the positions generated by the position engine. Trustworthiness is defined by the protection level associated with a given solution. Many of the concepts related to GNSS integrity originated from the development of the Wide Area Augmentation System (WAAS). The integrity concept was formalized by the Stanford Integrity Diagram, which outlines the key concepts related to integrity. TABLE 2 defines the terminology surrounding the integrity concept.

Table 2. Integrity terms. (Data Sapcorda)

The integrity risk is the probability that a user will experience a position error larger than the alert limit without an alarm being triggered. When this occurs, the user is in a potentially dangerous situation as the system is providing dangerously misleading information to the user, who is unaware.

The protection levels are computed based on the expected behavior of the error sources encountered in a GNSS positioning system. If the protection level is less than the system’s alert limit, then the system is operating within its normal bounds. If the error sources are not properly monitored or quantified, protection levels become optimistic. This occurs when the true position error, which is typically unknown, exceeds the protection level supplied by the system. When this situation occurs, it is labeled hazardously misleading information (HMI) because the system may believe that its position is more accurate than it truthfully is. If the true position error remains less than the alert limit, then this is classified as misleading information. As the true position is not beyond the alert limit, the operator/system can continue to rely on this information without being in a potentially dangerous scenario.

To define the true integrity risk of the system, it is necessary to understand its error sources, threat models, frequency of occurrences and potential failure modes. Many threats could render a correction service unavailable, including hardware failures, data outages or software bugs, atmospheric anomalies and satellite failures. The following section describes these threats along with the capabilities used for monitoring them.

Error Sources. The primary error sources in high-precision GNSS positioning are described in TABLE 3.

Table 3. GNSS network error sources, their magnitude and mitigation approach. (Data Sapcorda)

Although not mentioned in this table, additional error sources include site displacement effects such as solid earth tides, ocean tide loading and polar tides; carrier-phase wind-up at both the receiver and satellite; and satellite and receiver antenna phase-center variations and relativistic delays. These effects must be consistently modeled at both the server and the end-user for centimeter-level positioning.

Based on the error sources described in Table 3, it is necessary to convert this information into a format that can be used by the position engine to derive protection levels for each solution. How the final protection level is derived by a position engine is not within the scope of this article. For this, several approaches can be used including carrier-phase-based receiver autonomous integrity monitoring (CRAIM), solution separation and others.

The following equation can be used to describe the overall error contribution for each measurement:

where

is the total uncertainty for satellite i

is the uncertainty of the ionosphere model

is the uncertainty of the troposphere model

is the uncertainty of the combined orbit, clock and bias (ephemeris) corrections

is the uncertainty of the measurements in the given environment

The terms , and are derived from the real-time reference network operator while the term must be computed by the end-user receiver. This final term is perhaps the most difficult to determine, particularly for kinematic environments, as the value is highly dependent on antenna quality, multipath and measurement quality.

PERFORMANCE AND RESULTS

We processed 24 hours of data at three stations covered by Sapcorda’s European network and within the red circle shown in FIGURE 5.

FIGURE 5. Location of stationary testing carried out within Sapcorda’s European network. (Image: Sapcorda)

The test stations were situated in an open-sky environment with high-quality geodetic antennas and receivers. The position results and protection levels were derived from Sapcorda’s own position engine.

FIGURE 6. Integrity plots for the horizontal error and protection levels for three stations within Sapcorda’s European network coverage area.(Image: Sapcorda)

FIGURE 6 shows the horizontal component integrity plots for the three stations. The protection levels are computed for the five-sigma level. In all three examples, the protection level can properly bound the horizontal position error. In terms of the measured accuracy, the typical performance observed at the three stations is between 3 and 7 centimeters for the 95th percentile.

In addition to the stationary testing, two kinematic trials were carried out in cooperation with a system integrator. The integrator setup consisted of a commercial RTK receiver and position engine being fed with SPARTN corrections. The equipment was mounted onto the vehicle used for the tests. Both tests were carried out in an urban environment, which introduced measurement outages due to trees, overpasses and urban canyons. FIGURE 7 shows the area in which the kinematic trails were carried out, as well as some of the urban conditions with which the system had to contend.

FIGURE 7. Location of kinematic trials using Sapcorda’s North American correction service and examples of the environment encountered during the testing. (Image: Sapcorda)

FIGURES 8 and 9 show the position performance and integrity plots for the two kinematic trial scenarios. The reference trajectory was computed using a short baseline post-processed kinematic solution computed with a third- party application. The typical accuracy of the Sapcorda-enabled solution was on the order of 2 to 4 centimeters, while the maximum error was 10 centimeters. In both cases, the protection levels were able to properly bound the horizontal position error. Figure 8 shows an area of increased position error, which occurs around the 22.6- to 22.7-hour mark of the day. This period coincides with the image in the bottom right of Figure 7, where the vehicle passes into a difficult environment with overhead trees and walkways, as well as significant shading from a tall building. Even in this type of environment, the protection levels were able to properly bound the horizontal position error.

FIGURE 8a. Horizontal position performance for kinematic trial #1. The red line indicates the 1-sigma error of the position engine. (Image: Sapcorda)

FIGURE 8b. Horizontal position performance for kinematic trial #1: The 5-sigma integrity diagram. (Image: Sapcorda)

FIGURE 9b. Horizontal position performance for kinematic trial #2: The 5-sigma integrity diagram. (Image: Sapcorda)

In addition to the position performance, re-initialization time plays a critical role for precise positioning systems operating in difficult environments. Due to the regular outage and signal blockages, which occur in urban environments, the re-initialization time is critical to providing high availability. Traditional precise point positioning (PPP) systems, even those that perform ambiguity resolution, can take anywhere from 5 to 20 minutes to re-initialize and achieve an acceptable accuracy level (typically 10 centimeters) after a complete outage. Researchers in both academia and industry have developed several methods to reduce this time by “bridging the gap” after outages.

However, these approaches rely on assumptions about either the vehicle trajectory or the stability of the ionosphere before and after outages. The impact of these assumptions on overall integrity have not been adequately studied. Systems that rely on inertial measurement units (IMUs) to constrain the position after an outage introduce a dependency between what should be two independent sensors in the overall system.

FIGURE 10 shows the re-initialization time of the integrator’s position engine when using Sapcorda’s correction service. In this case, the re-initialization time is computed as the time it takes to return to RTK-ambiguity-fixed mode as indicated in the position engine output after an outage. Results based on comparisons against short-baseline RTK positioning showed typical accuracies below 10 centimeters upon re-initialization. In this definition, the time of the outage is included in the overall re-initialization time. In nearly all of the 42 occurrences, the time to re-initialize is less than 10 seconds. This is sufficient to allow an IMU to provide position updates during the GNSS outage.

FIGURE 10. Re-initialization time of the integrator’s position engine enabled by Sapcorda’s correction service. (Image: Sapcorda)

SYSTEM DESIGN CONSIDERATIONS

In addition to understanding GNSS error sources and performance, it is also important to consider the integrity of the entire system. This includes software development processes, hardware selection, data communication standards and security.

Software Design

Aspects needing to be addressed include:

Software Coding Standards. As software is used more and more in safety-critical scenarios, standards have been developed to minimize common errors and failures. Some standards relevant for safety-critical applications development include International Organization for Standardization (ISO) standard 26262 and Motor Industry Software Reliability Association (MISRA) C/C++ coding standards. Many of these standards can be automated via the static analysis tools described below.

Functional Safety. The objective of this analysis is to understand the possible failure modes of a system, how likely they are to occur, and how to mitigate their risk. Several methods can be applied for functional safety analysis. One such approach is failure mode effect analysis (FMEA). In general, functional safety analysis is a complex task requiring a wide range of experience and expertise. Understanding how design or feature choices impact overall failure modes is also critical for simplifying the number of cases and overall system complexity.

Test Coverage. Unit tests provide the fundamental verification that a function can perform its expected task. Coverage analysis tools provide insight into which sections, paths and combinations are being tested. Various metrics are possible, including:

statement coverage: measures the number of executable lines of code that are evaluated
branch coverage: measures which code paths are being evaluated (for example, if statements, both true and false must be covered)
modified condition/decision coverage (MC/DC): in addition to checking all branches, all combinations of branches must be considered.

The degree of effort to meet target coverage metrics greatly varies based on the type of metric chosen.

Code Quality Metrics. Code quality metrics attempt to reduce the complexity of functions and methods in the software. Code quality metrics may include:

cyclomatic complexity scores
establishing the maximum number of control statements within a function
establishing the maximum number of lines or methods called within a single function.

Static Analysis. Static code analysis provides an examination of source code prior to execution. It can detect common implementation issues such as divide-by-zero errors, bounds overrun, poorly defined loops or control statements, among others. Most commercial products provide support for MISRA C/C++ guidelines and other best practices for safety-critical applications.

Automated Testing. Test automation is critical for monitoring performance changes and ensuring high-quality code changes. Critical scenarios such as leap-second changes, week rollovers and ephemeris failures can be logged and then used as part of the automated test plan. And, as bugs emerge, adding additional test scenarios for these is also beneficial.

Data Communication Protocol

One must also consider several aspects related to the transmission of the correction service to users.

Open Source. A standardization of an open-source data communication protocol for mass-market applications allows for a receiving system to employ multiple corrections from more than a single specific provider without requiring independent functional safety requirements. This can provide a much higher level of redundancy than is possible when depending on only a single service provider.

Integrity and Functional Safety. To properly quantify the protection level, it is necessary to provide quality information about the corrections being provided by the service. Employing “do not use” flags ensures users drop satellites that may be unhealthy or performing poorly. General system status messages identifying the cause of a failure are also critical for proper separation of issues between server and recipient.

Encryption and Anti-Spoofing. As the use of GNSS expands, the threat of spoofing has become more significant. Data message encryption must be robust and resilient to protect the user of the data against external threats.

Self-Contained and Repeatable. Replication of events is important for safety-critical applications. A message format used for such applications should be self-contained and not rely on any external sources for factors such as initialization or the expansion of data. This may include the expansion of time-tagged data, or limiting the expansion of ephemeris to a specific Issue of Data Ephemeris (IODE).

SUMMARY

High-precision GNSS correction services for applications requiring both accuracy and integrity will continue to grow. To meet these demands, GNSS correction services that previously focused on accuracy as their primary goal must begin to work toward providing adequate integrity information to provide reliable positions and protection levels. This requires a multidisciplinary approach to achieve an in-depth understanding of GNSS error sources, integrity concepts and functional safety.

End users will benefit from the clear separation of the server and recipient responsibilities and through an open communication standard that facilitates the use of multiple correction service providers and is developed with safety and integrity at its core.

The adoption of formal safety practices, including software development strategies to reduce risk and mitigate errors, is also critical in achieving a reliable and safe high-precision correction service.

ACKNOWLEDGMENT

This article is based on the paper “Integrity for High Accuracy GNSS Correction Services” presented at ION ITM 2019, the 2019 International Technical Meeting of The Institute of Navigation, Reston, Virginia, Jan. 28–31, 2019.

LANDON URQUHART is the R&D engineering manager for Sapcorda Services Inc., with offices in Berlin and Hanover, Germany, and Scottsdale, Arizona, USA. He obtained his M.Sc.E. from the Department of Geodesy and Geomatics Engineering at the University of New Brunswick (UNB), Fredericton, Canada. His research interests are GNSS correction services for mass-market applications.

RODRIGO LEANDRO is the chief technology officer at Sapcorda Services in Scottsdale. He holds a Ph.D. in spatial geodesy from UNB. Dr. Leandro has been active in GNSS R&D for more than 15 years and has served in engineering leadership roles in various companies in the GNSS industry.

PAOLA GONZALEZ is a product engineer at Sapcorda Services and is based in Hanover. She completed her B.Sc. in geodesy at Zulia University in Maracaibo, Venezuela, and her master’s degree in geomatics at Karlsruhe University of Applied Sciences in Karlsruhe, Germany. In the past few years, she has been working in the GNSS industry, focusing mostly on performance analysis, evaluation and verification of different equipment, software and services.

Innovation: Integrity for safe navigation