GPS World

Category: Research & Development

  • Innovation: Hunting for GNSS Echoes

    Innovation: Hunting for GNSS Echoes

    Analysis of Signal Tracking Techniques for Multipath Mitigation

    By Antonio Fernández, Mariano Wis, Pau Closas, Carles Fernández-Prades, José A. García, Francesca Zanier, and Massimo Crisci

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    GETTING RID OF A NUISANCE. No, I’m not talking about your neighbor’s barking dog or the IT guy when he shows up to fiddle, yet again, with your computer. I’m talking about multipath. What is multipath, you ask? Herewith, Multipath 101. When a radio signal travels from a transmitting antenna to a receiving antenna, it will follow a direct line-of-sight path. But the signal might also travel to the receiving antenna after being reflected off a nearby building, say, resulting in a delayed signal or echo along with the line-of-sight one. Those of us of a certain age will remember ghost images on the screens of TVs connected to “rabbit ears” or outdoor antennas. That was multipath. These days, with TV signals primarily delivered by cable and satellite, we don’t see multipath much anymore. But we do hear it in our cars, from time to time, while listening to FM radio. Although the FM “capture effect” provides some margin against multipath, it is not uncommon to lose stereo reception or to experience fading out of the signal while driving in built-up areas as a result of reflections.

    This same multipath phenomenon also affects GNSS signals. Unlike satellite TV antennas, the antennas feeding our GNSS receivers are omnidirectional. So we have the possibility of not only receiving a direct, line-of-sight signal from a GNSS satellite but also any indirect signal from the satellite that gets reflected off nearby buildings or other objects or even the ground. The related phenomena of diffraction and scattering can also generate multipath signals.

    In a GNSS receiver, the line-of-sight and multipath signals combine to corrupt tracking of the line-of-sight signal resulting in increased pseudorange and carrier-phase measurement errors.

    GNSS antenna and receiver manufacturers have developed techniques to minimize some of the impact of multipath on the GNSS observables. And tracking of some of the newer GNSS signals is a bit more resistant to multipath. But multipath, at some level, is still a problem looking for a better solution.

    This brings us to ARTEMISA, which stands for Advanced Receiver Techniques: Multiprocessing Algorithms. It’s a European initiative to develop techniques to minimize the effects of multipath in GNSS receivers. For those of you who are a little rusty on your Greek mythology, Artemis (or Artemisa in Spanish — after all, she was a woman) was the Greek goddess of the hunt. You might better know her Roman equivalent: Diana. Her parents were Zeus and Leto, and Apollo was her twin brother. She is often depicted carrying a bow and arrows. How appropriate a name for a project whose goal is to try to kill off the effects of multipath in GNSS receivers.

    In this month’s column, the team of researchers involved with ARTEMISA describe their efforts to generate synthetic multipath for GPS L1 and Galileo E1 signals and to test different signal tracking techniques in a simulated receiver to see which techniques best minimize the effects of multipath on positioning solutions and which might be feasible candidates for incorporating in real receivers. The hunt is on.

    GNSS navigation in urban environments is usually challenged by a number of effects such as multipath and weak signal conditions. In particular, the pernicious effects of multipath on signal tracking and system accuracy are widely known. To mitigate these effects, there is a series of techniques that range from modified antenna design to combining the GNSS receiver with other sensors or subsystems. Another possibility is to implement advanced tracking techniques specifically designed for these purposes. Such techniques usually impose computational load and implementation complexity, which make them hard to implement in an application-specific-integrated-circuit-based receiver. However, given the current advances in computer technology and the possibilities of field-programmable-gate-array- (FPGA-)based hardware, it is possible to implement these new techniques in an operational receiver.

    We have studied this possibility as part of the ARTEMISA project, carried out by DEIMOS Space and the Centre Tecnològic de Telecomunicacions de Catalunya, and supervised by the European Space Agency’s European Space Research and Technology Centre. We have implemented and tested a series of innovative techniques that are able to cope with, and even to estimate, multipath (MP) parameters, using a simulated software receiver based on the GRANADA (Galileo Receiver Analysis and Design Application) GNSS blockset for MathWork’s Simulink graphical programming language tool. These techniques are based on the maximum likelihood principle (as implemented in the Multipath Estimating Delay Lock Loop) or on online Bayesian techniques for the estimation of multipath (as implemented in the Multipath Estimating Particle Filter), involving architectural modifications of the tracking loops (as in vector tracking loops), or even constituting a new paradigm in receiver design (direct position estimation).

    Our effort in this project has focused on two main tasks. The first task is the design and development of the simulation platform, the techniques to be tested, and a multipath model representative of the urban environment. The second task involves a simulation campaign that has been carried out to test the different techniques and to contrast the results obtained against the legacy delay lock loop / phase lock loop (DLL/PLL) tracking loop schemes. This article describes these tasks and some of the results we have obtained so far.

    Keep in mind that at the time of writing, ARTEMISA is still ongoing. Therefore, more results are expected up until the end of the project.

    Simulation Platform

    The simulation platform has been developed in Matlab/Simulink with DEIMOS Engenharia’s GRANADA GNSS Blockset. This blockset is a collection of Simulink models and blocks that can be used to design and simulate any kind of GNSS receiver. The main block is the Factor Correlator Model (FCM), which implements the set of correlators through an analytical (set of equations) model. Carrier phase, code misalignment, autocorrelation function, and even the correlated noise and the multipath at the output of every virtual correlator are simulated for a given input trajectory. On the other hand, the tracking loops are implemented as independent modules representative of an actual receiver. This semi-analytical approach has the advantage of performing a fast simulation of the correlator output without the need for implementing the baseband correlation operation. In addition, its implementation in Simulink allows for the development of innovative tracking schemes. This approach also matches with the ARTEMISA project concept, where a series of innovative tracking loops has been implemented with the aim of replacing or improving conventional PLL/DLL schemes.

    The main architecture of the simulation platform is shown in FIGURE 1. We use an external trajectory file to generate the reference data that will be used with the FCM block to generate the correlator output that will feed the tracking loop blocks. These trajectory files are also used to feed the multipath scenario generators, to test each technique under a number of defined scenarios so that we can assess their performances and find their limitations under multipath.

    Figure 1. ARTEMISA simulation platform architecture.
    Figure 1. ARTEMISA simulation platform architecture.

    We used two statistical models for the description of the signal propagation: the Controlled Stochastic Channel Model (CSCM), which is a modification of the Land Mobile Satellite channel developed by Pérez-Fontán, and the well-known Land Mobile Channel Model, developed by the German Aerospace Center (Deutsches Zentrum für Luft- und Raumfahrt or DLR); see Further Reading. These models generate a series of scenario files, which can be loaded into the FCM to introduce the multipath effects in the correlator output.

    These two statistical models are complementary. The CSCM model allows the user to set the multipath channel characteristics to be able to stress the tracking technique, while the DLR model permits evaluation of the technique’s response in realistic conditions.

    A deterministic user-defined multipath generator was implemented to check the response of the tracking techniques under well-defined multipath conditions. The Multipath Error Envelope (MPEE) was also computed to evaluate the response of the technique under one echo with varying delay conditions.

    The purpose of this article is not to explain all the developments performed with the platform. It focuses on the results obtained with the deterministic and statistical channel model. For this reason, the development of the CSCM generator will be explained in detail.

    Controlled Stochastic Channel Model

    The CSCM module was specifically created for this project. Its purpose is to generate a stochastic channel, but with the capability to control the multipath power levels and the number of echoes generated in the scenario, thus creating a set of realistic multipath signals, but with the capability of being easily controlled by the user. Time series for multipath echoes are generated, following a Rice or Rayleigh stochastic model, but the mean power levels, the amplification K factors, and the power switching times are chosen by the user.

    The model allows the selection of the number of satellites (channels) that are generated in the model, the sampling period (related to the loop integration time), the length of the simulation, the receiver speed, the signal carrier frequency, and channel specific parameters such as the number of echoes, the average delay of the echoes and the decay slope (echo power loss ratio with signal delay).

    One of the parameters the user can set implicitly is the multipath echo lifetime. What the user really sets is the channel transition time, or the time during which the channel keeps the multipath configuration. Every time the transition time is changed, a series of multipath echoes are canceled and other ones appear. This set of disappearing/appearing echoes is performed in pairs in such a way that the transition between echoes is smooth. FIGURE 2 illustrates this mechanism.

    Figure 2. CSCM echoes smooth transition.
    Figure 2. CSCM echoes smooth transition.

    When an echo is disappearing (a red one in the figure), its associated echo is at its maximum value (a blue scatterer). In the next interval, a new echo appears in a different delay position (a green one) and the associated scatterer begins to decrease its power. This mechanism allows the user to easily associate the transition time to half the multipath echo lifetime.

    Simulation Plan

    The simulation plan is structured into different stages. The first stage of the simulation plan is based on the controlled multipath environment, with specific tests for each technique. The purpose of this stage is the tuning up of the techniques. As an example, for the Multipath Estimating Delay Lock Loop (MEDLL) technique, parameters such as the precorrelation bandwidth, the number of MEDLL iterations or the number of assumed multipath echoes are parameters that are adjusted after these tests are carried out. Another purpose of this first stage is to check the performance of the techniques under deterministic, fully controlled multipath. Parameters like signal-to-multipath ratio, multipath delay, and the number of multipath echoes can be controlled at any time.

    Another test is the generation of the multipath envelope error plot. The utility of this test is to find the optimal configuration of the correlator position for each kind of signal, which is a trade-off between the obtained root-mean-square error (RMSE) and the number of correlators. This procedure is repeated for each signal considered in the plan.

    The next stage of the simulation plan is the test with the CSCM model. This test consists of the generation of a series of scenarios characterized by the stochastic model, the number of echoes, and the user receiver dynamics. Scenarios presented in this article are shown in TABLE 1. Two types of user environments are defined: one for pedestrian and one for vehicular receivers. The dynamics (user speed) define the integration (sampling time) and the multipath Doppler spread. The stochastic model parameters include the type of stochastic model for the line-of-sight signal (LOSS) and multipath echoes, mean power level, and amplification K factor. These scenarios represent a moderate multipath level with four echoes.

    Table 1. CSCM scenarios in the simulation plan.
    Table 1. CSCM scenarios in the simulation plan.

    Each scenario was run with different settings of carrier-to-noise-density ratio (C/N0) and with all the signals that were planned for the project: GPS L1 C/A, GPS L5, Galileo E1 and Galileo E5. In this article, we focus on L1 band signals, analyzing the results for GPS L1 and Galileo E1.

    Table 2. GNSS signals considered in the analysis.
    Table 2. GNSS signals considered in the analysis.

    The final stage in the simulation plan is testing each technique under realistic channel conditions with the DLR model. In this case, an urban scenario is set, assuming two types of receiver dynamics (a pedestrian user and a vehicular user). No more details about this stage are given because these tests are currently ongoing.

    Technique Descriptions

    After an initial evaluation of the candidate techniques, the following techniques were selected for implementation and testing in the project.

    Multipath Estimating Delay Lock Loop. MEDLL was proposed by Van Nee (see Further Reading). It is a robust statistical approach to the multipath problem, where the maximum likelihood principle is applied to a signal model consisting of LOSS and M-1 multipath rays or echoes. The key idea is to perform the estimation of the whole set of parameters of the incoming signals (that is, amplitude, delay, and phase) in an iterative manner. When their amplitudes, time delays, and carrier phases are estimated, the effect of the reflections in the correlation can be removed. Applying standard assumptions, the maximization of the likelihood function yields a set of interrelated equations from which one can estimate iteratively the LOSS and multipath parameters. The implementation of MEDLL considers a similar architecture as conventional DLLs, although in practice more than three correlators per loop are required for effective multipath mitigation. Despite its demanding requirements in terms of a large number of correlators and computational load, MEDLL was successfully implemented in NovAtel receivers because of its excellent performance in multipath mitigation.

    The contributions of all signals (that is, LOSS and an unknown number of echoes) are not calculated simultaneously from the outset. First, the contribution of only one signal is calculated, then the contribution of a second signal is added with the contributions of both signals being optimized, then the contribution of a third signal is added and the contributions of all three signals are optimized, and so on. The process is repeated until a suitable stop criterion is fulfilled. A possible approach for deciding when to stop adding more rays to the signal model is to detect when the error increases; that is, observing that the signal-to-residual ratio when considering an extra path decreases with respect to the case of not considering it, or reaching a maximum number of considered paths, which is a design parameter of this technique.

    Multipath Estimating Particle Filter. The MEPF shares with MEDLL the philosophy of estimating the parameters of multipath to mitigate its effect. The main difference is that in this case the statistical principle is not the ML (as in MEDLL) but Bayesian filtering. Here the term Bayesian means that the algorithm is using some sort of a priori information regarding these parameters (such as interdependencies and time evolution models). Therefore, instead of assuming that each integration period is independent of the others, a first-order Markov process is assumed for the unknown parameters (that is, amplitude, delay, and phase). The resulting problem is formulated as a nonlinear state-space model and can be solved by means of a Rao-Blackwellized particle filtering method.

    The MEPF has a relatively high computational load, which is a function of the number of particles (Np), the number of correlation points, and the number of rays to be estimated (M). In all cases, the larger the values the more computationally demanding the algorithm is. According to the simulations performed, configurations with Np larger than 2000 are not worthwhile, because it implies a high computational cost and the results do not improve significantly the accuracy of a GNSS receiver. Also notice that the dimension of the state-space to be estimated is 3 × M ([amplitude, phase, delay] × M), and thus estimating an additional multipath ray implies augmenting the dimensionality by three. Theoretically, the convergence results of particle filters are independent of the dimensionality of the problem. However, it is agreed that in practice these methods fail when the problem increases in dimension. Therefore, setting M larger than 5 is not reasonable since the number of particles required for convergence would be too large to consider its implementation in a receiver.

    Vector Tracking Loops. A conventional GNSS receiver consists of several parallel scalar DLLs, each of which independently estimates the individual pseudoranges. The parallel set of measured pseudoranges (plus Doppler or accumulated delta range measurements on the carrier) are then fed to a Kalman filter estimator, and thus each DLL effectively produces an independent estimate for each of the N pseudoranges for each of the N satellites. However, not all of their measurements are truly independent, although they are treated as such by the DLL, and if there are more than four measurements being made and four or fewer unknowns, the system is overdetermined. Furthermore, the geometry of the satellite-user paths generally prevents the measurements from being truly independent.

    The concept of vector tracking loops firstly appeared in the early 1980s. Recently, the method has attracted the attention of many researchers (see Further Reading) due to its good performance in weak signal scenarios.

    In this article, we present the implementation of a vector tracking loop that works with pseudorange and pseudorange-rate measurements and provides estimations for position, velocity, receiver clock error, and receiver clock drift. The vector loop has been integrated in a basic receiver based on the classical DLL and PLL/frequency lock loop (FLL)-assisted architecture, acting as an overlay procedure, which activates automatically once the basic receiver has obtained the first position fix. Then, the position/velocity/time solution is used to jointly estimate the synchronization parameters (time delay and carrier phase) for each of the received GNSS signals by means of an extended Kalman filter, and those values are re-injected into the tracking loop. By using position for deriving such synchronization parameters, the algorithm exploits the problem’s inherent geometric constraints, processing all the channels jointly and providing robustness in scenarios with weak receiving power, high multipath, or fast fading.

    Direct Position Estimation. Although the conventional two-step position determination is the approach taken traditionally, it is seen to have a number of drawbacks. In contrast, direct position estimation (DPE for short) proposes an alternative where the estimation of a user’s position is performed directly from the received and sampled signal, thus avoiding intermediate steps and jointly considering signals from all satellites when estimating the position solution. By merging the two-step approach into a single estimation problem, DPE addresses some of the inherent drawbacks of the conventional approach where the dependencies between channels are efficiently exploited, in the sense that signals from visible satellites are jointly processed to obtain the user’s position. At the time of writing, this technique is being implemented and its analysis is left for future publications.

    Results

    Not all the results that we have obtained have been included in this article; only the most relevant ones for L1/E1 CBOC and BPSK signals are given.

    MEDLL. Optimal Correlator Configuration. As stated previously, the test consisted of executing different correlator configurations. TABLE 3 shows the correlator configuration ID, the number of correlation samples, and the location of the late correlators with respect to the prompt one and normalized to the chip time (Tc). The corresponding early samples are defined analogously. For all these configurations, it is assumed that there is a correlator at zero chips.

    Inn-table3a
    Table 3. MEDLL correlator configurations tested.

    These configurations were selected in order to test different possibilities as regular spacing between correlators (MP31, MP61, or MP91), setting the correlators to inflexion points of the autocorrelation function (ACF) (NC37 or NC43 for CBOC modulation), or variable spacing (as configurations AR01 to AR05 and GE01) that optimize the number of correlators. The results of the tests can be observed in FIGURE 3 for a BPSK(1) signal and for a CBOC(6,1,1/11) signal.

    Figure 3. MPEE for MEDLL with BPSK and CBOC signals for different correlator configurations (Tc=chip time).
    Figure 3. MPEE for MEDLL with BPSK and CBOC signals for different correlator configurations (Tc=chip time).

    In general, it is observed that the greater the number of correlators, the smaller is the spacing and therefore, the area covered by the multipath error envelope is smaller. However, the greater the number of correlators, the greater is the processing time. Therefore, it is necessary to find an optimal configuration that best fits the multipath variation.

    After having analyzed the tests for these configurations, we found that the optimal configurations are AR01 for the BPSK signal and NC37 for the CBOC(6,1,1/11) signal. These configurations are shown in FIGUR 4, and were used for the remaining tests.

    Figure 4. Correlator configurations for CBOC and BPSK signals.
    Figure 4. Correlator configurations for CBOC and BPSK signals.

    CSCM. As mentioned in the simulation plan description, the tests for a pedestrian and a vehicular user in a moderate multipath environment were performed with a scenario file generated with the CSCM tool. These scenarios are characterized by a series of multipath echo levels, number of echoes, and specific stochastic models that are detailed in Table 1. In this table, the pedestrian scenario is known as SP1 and the vehicular scenario is shown as SV1. The results with these scenarios are presented in this article.

    The RMSE for range estimates in these scenarios is shown in FIGURE 5 for SP1 and SV1. For comparison, these plots show also the theoretical lower bound (Nunes bound) computed for each technique.

    Figure 5. Range RMSE for MEDLL in pedestrian and vehicular scenarios.
    Figure 5. Range RMSE for MEDLL in pedestrian and vehicular scenarios.

    The plots show that MEDLL outperforms the conventional DLL results above a minimum C/N0 value. This happens beyond 32 dB-Hz for a CBOC signal and 35 dB-Hz for a BPSK(1) signal for low dynamics (pedestrian) environments.

    In the case of vehicle scenarios such as SV1, it is observed that it requires significantly higher values of C/N0 in order to outperform the DLL RMSE. This result makes the technique impractical for vehicular applications.

    Time Performance. A collateral result that has been obtained with CSCM scenarios is the time performance of the technique, compared to the legacy DLL/PLL scheme. The ratios of the execution times needed for the techniques have been computed. This is an indicative measure of the computational load.  The time performance of MEDLL with the selected correlator configuration against DLL is 10:1. That is, 10 times more time is required for the MEDLL technique than the DLL to run the same scenario. It is also observed that the ratio for BPSK modulation is slightly larger than the ratio for the CBOC signal, because more correlators are used in that case.

    MEPF. Performance Under Controlled Channel. FIGURE 6 shows an example of the performance of the MEPF technique tested in a controlled channel environment.

    Figure 6. Results of the MEPF in the controlled multipath environment with 2 and 3 estimated rays including the line-of-sight. For comparison purposes, DLL/PLL results are also included (blue line in upper plot).
    Figure 6. Results of the MEPF in the controlled multipath environment with 2 and 3 estimated rays including the line-of-sight. For comparison purposes, DLL/PLL results are also included (blue line in upper plot).

    It can be observed how the DLL/PLL technique has an error, which grows as the number of rays is increased. However, when the MEPF is applied, it can be observed how the technique is capable of dealing with a multipath-changing environment despite the fact that it is varying in time with the number of rays increasing. It can also be noticed that the response of the technique is practically the same independent of the number of estimated rays (M). These results were achieved with a BPSK signal and 500 particles.

    Covariance Matrix Adjustment. Before starting the specific test for the evaluation of the scenario performance, it is necessary to calibrate the particle filter. The calibration procedure consists of the adjustment of the process covariance matrix. The observation covariance can be adjusted, simply by analyzing the raw observables, or it can even be done automatically.

    The critical point is the adjustment of the states’ covariance. It has been observed that an improper adjustment of the covariance may cause an increment in the range RMSE or even the divergence of the filter. For that reason, a systematic procedure for the adjustment of the covariance matrix has been followed. This procedure evaluates the performance using different configurations of the covariance matrices of the line-of-sight and multipath parameters in two stages, and allows us to find a set of optimal values for each scenario.

    Optimal Correlator Configuration. We also analyzed the optimal correlator configuration for the MEPF technique. A number of configurations in Table 3 were used under CSCM scenarios. It was found that the correlator configuration does not have a strong influence on the performance of the MEPF technique. It is worth mentioning that in cases where fewer than five correlators were used, the performance degraded. Despite the weak influence of the range RMSE with the correlator configuration, it was observed that there is a minimum for the BPSK signal that can be chosen for the MEPF technique (MP31). For the CBOC signal, the same configuration used for MEDLL is finally chosen (NC37), provided that it is the optimal configuration that balances range RMSE and the number of correlators.

    Number of Particles. It is important to notice that an initial set of tests was performed with 500 particles. However, it was found that by increasing the number of particles to 2000, the performance of the technique with CSCM was remarkably better. Because of this, for the remaining tests using the CSCM, this number of particles was the default value. Using a higher number is not worthwhile since results are not much improved and the computational load becomes too high.

    CSCM Results. The range RMSE results for the pedestrian scenario SP1 with the MEPF technique are shown in FIGURE 7. In this case, it is observed that for the CBOC signal, MEPF outperforms the DLL/PLL technique for low C/N0 values. This result could not be reproduced for the BPSK signal because of the adjustment of the covariance matrix, which in this test was optimized for CBOC.

    Figure 7. Range RMSE for MEPF and pedestrian scenario.
    Figure 7. Range RMSE for MEPF and pedestrian scenario.

    These promising results for CBOC open the possibility of using this technique in applications where the LOSS is very weak or where the multipath signals are very strong. More tests with this technique are currently being executed for a better adjustment of covariance settings for BPSK.

    Time Performance. The previous time performance analysis was performed with the MEPF technique. The performance ranges among 180:1 and 340:1, when compared to DLL/PLL schemes using three correlation samples. The extremely long time required to simulate the scenario makes this technique inadvisable for implementation within an operational receiver using current technology.

    VTL. CSCM Results. The same CSCM scenarios were performed for the VTL technique, but using a multi-channel receiver. Results for pedestrian SP1 and vehicular SV1 scenarios are shown in FIGURE 8.

    Figure 8. Position RMSE for VTL with pedestrian and vehicular scenarios.
    Figure 8. Position RMSE for VTL with pedestrian and vehicular scenarios.

    It must be noted that, in order to perform fair comparisons, the results of ordinary DLL/PLL tracking used a conventional KF for the computation of the position instead of the least squares module available in the GRANADA GNSS Blockset.

    In our numerical simulations, a significant improvement in the performance of VTL with respect to the DLL/PLL+KF scheme was not observed in pedestrian environments, due to the low dynamics. Under those dynamic conditions, both systems exhibited similar (statistically equivalent) behavior.

    In the case of scenario SV1, the velocity applied to the receiver was higher than in the pedestrian case, and the VTL exhibited a remarkable improvement over the DLL/PLL+KF-based receiver. For the BPSK modulation, it was observed that for low values of C/N0 , the VTL performs better than DLL/PLL+KF. However, for stronger signals, both techniques have the same behavior as shown for the pedestrian scenario results. On the other hand, for the CBOC modulation, it is observed that VTL performs better than DLL/PLL+KF for the whole range of C/N0 values. The precorrelation bandwidth was set to 8 MHz in the case of BPSK, while for CBOC it was set to 14 MHz. That wider bandwidth of the CBOC receiver has an impact in the estimation of the measurements covariance matrix. In can be observed that in such higher dynamic stress conditions, the VTL outperformed DLL/PLL+KF in our numerical simulations.

    It must be mentioned that for all the simulations, we assumed the same C/N0 for all satellites. However, we plan to run tests with LOSS fading (variation of C/N0). It is expected that the VTL technique will show its advantage in those simulations.

    It was also observed that settings of the KF covariance have an important effect on the results. This covariance must be adjusted according to the multipath signal level. Therefore, a calibration operation, which adapts the KF to a particular scenario should be performed. While the measurement covariance matrix can be adaptively estimated from the output of the DLLs and the PLLs, the process covariance matrix should be adjusted depending on the trajectory characteristics.

    Time Performance. The time performance analysis also shows that the time performances of VTL and DLL/PLL+KF are very similar. Only a small increment of 15% of the computational cost for vehicular scenarios has been observed. This makes this technique a good candidate to be implemented in an operational software-based receiver.

    Results Overview

    After analyzing the current results from the different techniques, some general conclusions on their performance can be made.

    MEDLL can be useful to mitigate and improve the pseudorange measurement provided that the C/N0 value is greater than a threshold value. An intuitive reasoning for this is that the estimation of multipath rays is easier at high C/N0 values. Below this value, the MEDLL technique does not present an important advantage over ordinary DLL/PLL given the time performance it has (a ratio of 10:1). MEDLL is especially well-suited for static and pedestrian environments.

    MEPF is a technique that still needs research before it can be used operatively. Results show that it works quite well for low C/N0 values when compared to DLL/PLL. Results show that for the CBOC signal, at least 2000 particles are needed to give good results for low C/N0 values. However, its time performance is very poor (around 200:1 with respect to DLL with 2000 particles)

    VTL does not present an advantage in the pseudorange measurement domain, but it clearly improves the position solution with respect to a classical DLL/PLL+KF tracker. This improvement is remarkable under dynamic conditions. It is also observed that the time performance is very similar to the DLL/PLL+KF one. Therefore this technique is a good candidate for implementation in a receiver prototype based on embedded hardware, an FPGA implementation, or software-based radio.

    For the sake of completeness, a performance comparison in the range domain of the different techniques with the BPSK and CBOC signals for the pedestrian SP1 scenario are presented in FIGURE 9. The metric used is the range RMSE.

    Compared Range RMSE for different techniques: pedestrian scenario with BPSK(1) and CBOC(6,1,1/11) signals.
    Figure 9. Compared range RMSE for different techniques: pedestrian scenario with BPSK(1) and CBOC(6,1,1/11) signals.

    Conclusions and Future Work

    This article has presented a series of innovative multipath-estimating techniques using non-conventional approaches in the tracking algorithms. These non-conventional approaches are based on maximum likelihood (MEDLL) or non-linear online filtering algorithms (MEPF). Alternative approaches in the positioning algorithms have also been analyzed (VTL and DPE).

    To check the performance of these techniques, we have developed a simulation platform, able to carry out deterministic multipath simulations, in which the multipath environment can be controlled deterministically, and stochastic simulations based on tested multipath models (CSCM and DLR). The CSCM model is capable of simulating realistic multipath environments but with the capability to control the multipath ray parameters and the number of these rays. The DLR model allows us to perform simulations based on the conditions in realistic urban environments.

    This article has focused on the CSCM model. It shows simulations for a pedestrian and a vehicular scenario that represent typical dynamic conditions for each kind of user.

    These results show that the MEDLL technique performs very well in a static multipath environment under low dynamics with good visibility conditions.

    Concerning the MEPF, it has been found that the adjustment of the covariance for the observables is very important for achieving good results for the range RMSE. If this adjustment is done well, the results for low values of C/N0 outperform the ordinary DLL/PLL technique. This adjustment has been successfully achieved for a CBOC signal, but a BPSK signal still requires additional work. This may open the possibility of using this technique in applications in which the LOSS is very weak.

    It has also been observed that the VTL technique is very effective in high dynamics applications and noisy environments, provided that the internal KF process noise covariance has been properly estimated. VTL also shows a performance very similar to the DLL/PLL+KF scheme in mild-condition scenarios. That makes this technique a good candidate for implementation in a real-time software-based receiver.

    Finally, it is necessary to remark that ARTEMISA is still a work in progress. An extensive simulation campaign in a realistic urban environment under different conditions using the DLR multipath model is ongoing. In addition to the techniques presented in this article, other advanced techniques such as direct position estimation are under evaluation.

    Acknowledgments

    The ARTEMISA project, funded by the European Space Agency (ESA) is being carried out by DEIMOS Space, with the Centre Tecnològic de Telecomunicacions de Catalunya as subcontractor. The content of the present article reflects solely the authors’ views and by no means represents official ESA policy.

    The authors of this article would like to thank Tiago Peres, Joao Silva, and Pedro Silva from DEIMOS Engenharia; José Antonio Pulido from DEIMOS Space; and Roberto Prieto-Cerdeira from ESA’s European Space Research and Technology Centre for their support in the adaptation of the GRANADA GNSS Blockset and the simulation platform to the requirements of the techniques and multipath environments tested in the project.

    ANTONIO FERNANDEZ co-founded DEIMOS Space with headquarters in Madrid, in 2001, where he is currently in charge of the GNSS Business Unit.

    MARIANO WIS is currently working for DEIMOS Space as a project engineer in the GNSS Business Unit. He is also a Ph.D. candidate in the Aerospace Science and Technology Program of Universitat Politècnica de Catalunya in Barcelona.

    PAU CLOSAS is a senior research associate and head of the Statistical Interference Department in the Communications Systems Division of the Centre Tecnològic de Telecomunicacions de Catalunya (CTTC) in Barcelona.

    CARLES FERNANDEZ–PRADES is serving as head of the Communications Systems Division at CTTC, where he holds a position as senior researcher.

    JOSE A. GARCIA is with the Radio Navigation Systems and Techniques Section at the European Space Agency’s European Space Research and Technology Centre (ESA/ESTEC) in Noordwijk, The Netherlands.

    FRANCESCA ZANIER is also with the ESA/ESTEC Radio Navigation Systems and Techniques Section.

    MASSIMO CRISCI is the head of the ESA/ESTEC Radio Navigation Systems and Techniques Section.

    FURTHER READING

    • ARTEMISA

    “ARTEMISA: New GNSS Receiver Processing Techniques for Positioning and Multipath Mitigation” by A.J. Fernandez, J.A. Pulido, M. Wis, F. Zanier, R. Prieto-Cerdeira, M. Crisci, P. Closas, and C. Fernández-Prades in Proceedings of Navitec 2012, the 6th ESA Workshop on Satellite Navigation Technologies, and the European Workshop on GNSS Signals and Signal Processing, Noordwijk, The Netherlands, December 5–7, 2012, doi: 10.1109/NAVITEC.2012.6423092.

    • GRANADA GNSS Blockset

    “Factored Correlator Model: A Solution for Fast, Flexible, and Realistic GNSS Receiver Simulations” by J.S. Silva, P.F. Silva, A. Fernández, J. Diez, and J.F.M. Lorga in Proceedings of ION GNSS 2007, the 20th International Technical Meeting of the Satellite Division of The Institute of Navigation, Fort Worth, Texas, September 25–28 2007, pp. 2676-2686.

    • Signal Propagation Statistical Models

    “A Location and Movement Dependent GNSS Multipath Error Model for Pedestrian Applications” by A. Steingass, A. Lehner, and F. Schubert in Proceedings of ION GNSS 2009, the 22nd International Technical Meeting of The Satellite Division of the Institute of Navigation, Savannah, Georgia, September 22–25, 2009, pp. 2284-2296.

    “Statistical Modeling of the LMS Channel” by F.P. Fontan, M. Vazquez-Castro, C.E. Cabado, J.P. Garcia, and E. Kubista in IEEE Transactions on Vehicular Technology, Vol. 50, No. 6, November 2001, pp. 1549–1567, doi: 10.1109/25.966585.

    • Multipath Estimating Delay Lock Loop

    “The Multipath Estimating Delay Lock Loop: Approaching Theoretical Accuracy Limits” by R.D.J. Van Nee, J. Siereveld, P. C. Fenton, and B. R. Townsend in Proceedings of PLANS 1994, the Institute of Electrical and Electronics Engineers Position, Location and Navigation Symposium, Las Vegas, Nevada, April 11–15, 1994, pp. 246–251, doi: 10.1109/PLANS.1994.303320.

    • Multipath Estimating Particle Filter

    “Nonlinear Bayesian Tracking Loops for Multipath Mitigation” by P. Closas, C. Fernández-Prades, J. Diez, and D. de Castro in International Journal of Navigation and Observation, Vol. 2012, Article ID 359128, 15 pages, 2012, doi:10.1155/2012/359128.

    • Vector Tracking Loops

    Modeling and Performance Analysis of GPS Vector Tracking Algorithms by M. Lashley, Ph.D. dissertation, Auburn University, Auburn, Alabama, December 2009.

    “A VDLL Approach to GNSS Cell Positioning for Indoor Scenarios” by F.D. Nunes, F.M.G. Sousa, and N. Blanco-Delgado in Proceedings of ION GNSS 2009, the 22nd International Technical Meeting of the Satellite Division of The Institute of Navigation,  Savannah, Georgia, September 22–25, 2009, pp. 1690–1699.

    • Direct Position Estimation

    “Maximum Likelihood Estimation of Position in GNSS” by P. Closas, C. Fernández-Prades, and J.A. Fernández-Rubio in IEEE Signal Processing Letters, Vol. 14, No. 15, May 2007, pp. 359-362, doi: 10.1109/LSP.2006.888360.

    • Some Previous Innovation Columns on Multipath Mitigation

    “Under Cover: Synthetic-Aperture GNSS Signal Processing” by T. Pany, N. Falk, B. Riedl, C. Stöber, J.O. Winkel, and F.-J. Schimpl in GPS World, Vol. 24, No. 9, September 2013, pp. 42–50.

    “Multipath Minimization Method: Mitigation Through Adaptive Filtering for Machine Automation Applications” by L. Serrano, D. Kim, and R.B. Langley in GPS World, Vol. 22, No. 7, July 2011, pp. 42–48.

    “Multipath Mitigation: How Good Can it Get With the New Signals?” by L.R. Weill, in GPS World, Vol. 14, No. 6, June 2003, pp. 106–113.

    “GPS Signal Multipath: A Software Simulator” by S.H. Byun, G.A. Hajj, and L.W. Young in GPS World, Vol. 13, No. 7, July 2002, pp. 40–49.

    “Conquering Multipath: The GPS Accuracy Battle” by L.R. Weill in GPS World, Vol. 8, No. 4, April 1997, pp. 59–66.

     

  • Innovation: Getting Closer to Everywhere

    Innovation: Getting Closer to Everywhere

    Accurately Tracking Smartphones Indoors

    By Ramsey Faragher and Robert Harle

    If we wish to obtain consistently usable positions indoors using a mobile phone, we can augment its GPS or GNSS receiver with other unfettered sensing technologies such as gyroscopes and accelerometers supplemented by radio signals of opportunity. But is all of this actually feasible? The authors have conducted tests of a multi-system approach to positioning indoors with favorable results.

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    IS GPS REALY A GLOBAL POSITIONING SYSTEM? Well, that depends on your definition of “global.” If it means that GPS operates well all over the world in environments where it was designed to work, then, yes, it is a global system. But, if you define global as meaning that GPS operates well everywhere not only outdoors with a clear view of the sky but also indoors and in other restricted environments, then (as some have argued), GPS is not truly global.

    So why doesn’t GPS work (for the most part) indoors? Our mobile phones do and they use similar bits of the electromagnetic spectrum. The basic problem is that the signals from GPS (and other GNSS) satellites are just too weak to easily penetrate buildings. They are more than strong enough to yield excellent positioning, navigation, and timing (or PNT) results if the antenna connected to the receiver can “see” the satellites unobstructed. But even outdoors, trees, buildings, and mountains can block the signals from one or more satellites at a time. And indoors, the signals are usually attenuated by walls, floors, and ceilings so much that a conventional receiver cannot lock onto them.

    Receiver manufacturers have developed more sensitive receivers that can operate, at least to some degree, indoors but with a good antenna. And receiver chips or modules with this more sensitive technology are often found in modern mobile phones. But they don’t typically provide reliable indoor positioning because they are being used with inexpensive, suboptimal antennas. Some potential improvement in indoor positioning capability is possible by supplying the receiver with satellite orbit and clock information through the mobile network rather than having the receiver acquire this information directly from the satellite signals. This assisted-GNSS technique allows a receiver to work with weaker signals. But it is not a panacea. Gaps or holes still exist for positioning indoors or in other obstructed environments, prompting one industry wag to liken GNSS coverage to Swiss cheese.

    So, what are we to do if we wish to obtain consistently usable positions indoors using a mobile phone? As we will see in this month’s column, we can augment or bypass its GPS or GNSS receiver with other unfettered sensing technologies such as gyroscopes and accelerometers. These devices can be made very small using microelectromechanical technology and are already included in some mobile phones.

    However, there are some issues with these devices for positioning, not the least of which is rapid position drift. We can restrain the drift by using magnetometers, for example – also present in some mobile phones. We can also use radio signals of opportunity to help in the positioning – signals available in the phone such as multi-generation mobile signals, Bluetooth, and Wi-Fi through their signal strength “fingerprints.” But is all of this actually feasible?

    The authors of the article in this month’s column have conducted tests of such a multi-system approach to positioning indoors with quite favorable results. Are we at the stage of accurate positioning (and tracking) everywhere? Not quite, but we are getting closer.

    “Innovation” is a regular feature that discusses advances in GPS technology and its 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.

    In recent years, there has been increasing interest in ubiquitous positioning — accurate location fixes in any environment, outdoors and indoors. We have all become used to the availability and performance of global navigation satellite systems (GNSS) for accurate outdoor radio positioning with a reasonable degree of reliability and availability. However, indoor radio positioning is more challenging because GNSS signals do not penetrate buildings well, and we must instead rely on local infrastructure and other available inputs to aid the user.

    Indoor radio positioning is, however, available to the general public today through the use of signal strength fingerprint databases managed and provided by third-party providers such as Skyhook. These typically use Wi-Fi and cellular signals because of their ubiquity and the prevalence of appropriate receiver circuits in consumer devices. The user can also access the fingerprint database through these media. These systems, therefore, have two clear constraints: the database must have been previously built via some form of survey process, and the user must have a data connection available to obtain it. A more scalable system would not rely on such constraints, and would instead develop its own database during operation.

    The benefits of such a system are significant: it can provide location-based services, situational awareness, and asset tracking in new and unknown environments for consumers, emergency services, the military, lone workers, security personnel, and autonomous vehicles. There is no requirement for a data link to function, nor any prior surveying of the radio environment, nor any other prior knowledge such as a floor plan or map. However, the system can also be used to quickly and easily generate maps of the radio environment or floor plans, which can be beneficial for organizations wishing to provide positioning services to the public using a simpler positioning method; that is, this method can be used to rapidly survey an area and generate a signal fingerprint database for other users to exploit. Best of all, all of this can be achieved today in real time using an app for a consumer smartphone.

    The Digital Swiss Army Knife

    The last couple of decades have seen steady improvements in a variety of sectors that have led to new and flexible navigation capabilities — and all of these improvements can now be found in the little chunks of silicon, plastic, and glass in our pockets and handbags. Moore’s Law and the miniaturization of electronics have enabled us all to carry handheld programmable supercomputers around with us every day. Microelectromechanical systems technologies and the demand for better gaming and augmented reality experiences on our smartphones mean that any new phone contains the same types of sensors for enhancing user experiences that cruise missiles and smartbombs use to ensure they hit their targets precisely.

    Finally, your smartphone contains more radios than you probably realize. GPS (or GNSS); 2G, 3G, and 4G network radios; near field communications, like RFID; Bluetooth; Wi-Fi; and even a VHF FM chip might be tucked away in there somewhere. The near future is likely to bring a “whitespace” radio (using re-assigned vacated spectrum) along with a 60-GHz wireless USB transceiver. We are bathed in a phenomenal number of radio signals as we go about our daily lives, completely oblivious to the rich tapestry we are walking through — an invisible, permanent, detailed map just waiting to be sensed by our smartphones and annotated for our navigation purposes.

    So, just what is possible with a commodity smartphone and its arsenal of features?

    Pedestrian Motion Modeling

    We can begin with the accelerometers, magnetometers, gyroscopes and barometers found in recent smartphones. These sensors collectively form an inertial measurement unit (IMU) that can be used to track the motion of a user through any environment, regardless of the availability of GNSS (at least in theory).

    Unfortunately, there are many stumbling blocks in the way for any new navigator starting down this road. The standard approach for inertial navigation involves using the gyroscopes to maintain an estimate of the orientation of the device relative to the Earth, and to integrate the accelerometer measurements to calculate the system velocity and subsequently the change in position with each measurement update. A key aspect of this process is the removal of the effect of gravity, which requires us to estimate the value of the local gravity field strength (which varies with location across the globe) and its direction (which we do based on the estimated orientation of the device according to the gyroscopes). There are inevitably some errors associated with the estimates of both of these quantities.

    In addition, the sensors themselves suffer noise, biases, instabilities, non-linearities, and other effects that only decrease the system performance further. These errors accumulate over time because the position and orientation estimates at any moment depend on the cumulative sum of all measurements since the start of the journey. The result is rapid and unbounded growth in position and orientation error. The cost of the sensors is, of course, tightly correlated with their quality, and so the rate at which the navigation performance degrades. The quality of the sensors in smartphones is so low that this approach is rendered useless within the first few seconds of use. To make progress we must apply regular position corrections to the system by applying external constraints or incorporating external sensor measurements.

    Alternative. GNSS measurements provide constraints and corrections for inertial navigation systems, but here we are considering operating indoors where these are unavailable or severely degraded. An alternative solution for most smartphone users is to use the inertial sensors in a different manner, within a so-called pedestrian dead- reckoning (PDR) approach. Here, it is assumed that the device being tracked is held by (or attached to) someone walking in a manner that can be modeled. The inertial sensors are not now used to reproduce the full 3D motion of the device at the update rate of the sensors, but instead used simply to detect stepping motions and to infer that the user has moved some number of steps. Looking for patterns in the accelerometer data where minimum and maximum thresholds are exceeded within a certain time window is a surprisingly robust step counter when the user walks “normally” (more complicated actions such as side steps and stumbles require more complex algorithms). The smartphone can estimate its orientation by fusing together its gyroscope (which offers good short-term orientation-tracking) and its magnetic compass (good long-term orientation-tracking with periodic fluctuations from local magnetic anomalies). The step length of the user (a surprisingly consistent quantity) and any bias in the gyro-smoothed compass heading can both be measured and modeled during periods of GNSS availability such that the best possible estimates are available when GNSS is lost.

    FIGURE 1 shows the functional flow diagrams for a strapdown inertial navigation system (top) and a PDR system (bottom). Note that the PDR scheme accumulates error more slowly than the INS scheme (involves fewer integrations over lower-rate data) but is heavily dependent on the performance of the gait recognition, floor-change detection, and step-length-estimation algorithms.

    FIGURE 1. Functional flow diagrams for a strapdown inertial navigation system (top) and a pedestrian dead-reckoning system (bottom).
    FIGURE 1. Functional flow diagrams for a strapdown inertial navigation system (top) and a pedestrian dead-reckoning system (bottom).

    However, PDR techniques still accumulate error, resulting in gradual position drift, but with much higher performance than would be achieved by integrating the raw data in the traditional INS manner. Typical PDR schemes can track the user with an accuracy of a few percent of the distance walked, although this performance degrades with any un-modeled motions that confuse the step detector, such as infrequent backward or sidesteps. So how do we deal with this issue?

    Machine Learning

    The accuracy of PDR schemes is dependent on the validity of the pedestrian motion model. Any un-modeled action has the potential to generate false positive events in the step detector and hence contribute to position error. Users may stoop, crawl, jump, hop, or shake their device while static — motions that are all very difficult to unambiguously discriminate in raw sensor data.

    There are many approaches to solving this problem of gait recognition, and most exploit machine learning techniques. The basic principle of supervised machine learning is that a large set of labeled training data (that is, lots of manually categorized data of each type) is analyzed by a computer in order to extract patterns, statistics, or certain measurement sequences from the inertial sensor measurements that reveal the type of step that was taken. In unsupervised learning, the clusters and categories within the data must be found by the algorithms themselves.

    The outputs from such algorithms are typically thresholds, signatures, and other learned metrics that can be installed in a smartphone and used to dynamically classify movements. It is also possible to deploy the learning algorithms on the device itself so that it can learn what the particular user’s signatures are to permit better step and gait detection (like training a speech-recognition program to understand your accent). A simple example of this is running an error-state Kalman filter while GNSS signals are available to determine the user step length and to detect any background compass bias that is corrupting the system.

    A problem yet to be resolved for PDR schemes is a basic physical one: the laws of physics are the same for an object at rest as for one moving at constant speed. This means that it is theoretically possible for a suitably skilled person to simulate the “already moving at constant velocity” version of any of these motions while static by moving the device in just the right manner, effectively spoofing as many steps or motions as they like. The opening and closing phases of a journey (that is, the very first and last steps) are critical in distinguishing real and spoofed motion if only inertial sensing is used to disambiguate real and spoofed motion through an environment. We will, however, return to this problem in a moment.

    Simultaneous Localization and Mapping

    The application of machine learning can be extended to the entire indoor navigation problem using a technique called Simultaneous Localization and Mapping (SLAM). A key aspect here is the hypothesis that there are some measurements that can be taken within an indoor environment that vary rapidly on the spatial scale but only slowly on a temporal scale. These opportunistic measurements are typically of radio signal strength  (Wi-Fi, cellular, television, VHF FM, and so on) and magnetic field strength, although in principle many other metrics could be used such as light level and temperature. They are deemed to be opportunistic because they already exist in the environment and have not been generated specifically for this positioning system. Moving along a corridor is expected to result in a particular sequence of measurements that is repeatable on the next visit to that corridor with a confidence based on the time since the last visit. Tight agreement is expected within the next few minutes, close agreement within the next few days, and so on. It is not expected that these fingerprints will necessarily be valid for months or years, as objects may move around the environment; for example, large items may be relocated and Wi-Fi access points may be moved. The ability to exploit the expectation of high repeatability over short time periods of a few hours is the key to developing a system that can learn about its environment and improve its performance during use.

    As the device moves through the indoor environment (with position estimate driven by the PDR estimation), the opportunistic fingerprints are captured and stored. If the device returns to a region it has been in before, then it will record a sequence of measurements that will agree closely with the previous sequence that was recorded in the past. This provides a constraint to the system: whatever path was taken in between, it has converged with a section of its historical path and “closed a loop.” Any offset in these two path sections at this point reveals the inertial error that has accumulated during this loop. The system can therefore correct its own inertial error growth, allowing extended operations in GNSS-denied areas.

    Fingerprint Maps. The gathered opportunistic measurements can also be used to generate fingerprint maps of the areas that can be shared with other users to allow them to accurately position themselves within those areas in the future, reducing everyone’s reliance on PDR schemes and removing the need for environments to be manually surveyed for their environmental maps. The maps are automatically calibrated and corrected by the SLAM process. As more users operate in the environment and more data accumulate it is easier to identify and remove erroneous data that does not fit into the consensus being formed by the “intelligence of crowds.” This opportunistic navigation scheme can also feed back into the PDR scheme to aid with motion detection — as fingerprints are expected to vary on a fine spatial scale as users move through an environment. They can be used to detect when a PDR device is in reality static, but being moved in a manner that is erroneously triggering the step-detection routine.

    FIGURE 2 shows a plot of the magnetic-field-strength variations recorded during four walks down the same corridor of a building at four different times of day on four different days. The traces have been manually aligned by the clear drop in field strength at step number 40. A fixed step length was assumed, and the relative stretching evident across the traces is due to small differences in walking speeds across the tests. Step-length changes can be estimated using changes in the stepping frequency, and the typical step length can be observed and calibrated during periods of GNSS availability.

    FIGURE 2. Repeatability tests of the magnetic field strength from four walks along an indoor corridor at four different times during the day on four different days.
    FIGURE 2. Repeatability tests of the magnetic field strength from four walks along an indoor corridor at four different times during the day on four different days.

    There are two distinct classes of SLAM algorithm for PDR. The most common class involves an iterative batch process applied after the data have been collected (that is, offline). This process (which might be least-squares fitting or maximum likelihood estimation, for example) identify loop closure points and provide an optimal joint estimation of the path taken by the user that satisfies these constraints and the raw odometry data as much as possible. The
    Wi-Fi SLAM approaches, Gaussian Processes Latent Variables and GraphSLAM, both use such schemes. The results are typically robust, but the offline processing stage can be lengthy.

    SLAM can, however, be performed in real time, even on a smartphone, by exploiting an efficient multi-hypothesis scheme. As the user moves, we retain multiple hypotheses for their position and, crucially, record the history of each hypothesis. This is typically done using a particle filter, where each particle represents a unique hypothesis. In this context, we must store the tree of ancestors for each particle at each epoch. When we detect a loop closure, we prune the history to remove all hypotheses that did not result in a loop closure at that point and therefore dynamically correct our errors. Note that each particle can even be assigned different parameter values, such as step length or heading bias, and if a gait detection scheme cannot confidently identify the type of step taken, new particles representing every possible user motion at that epoch can be generated.

    Occupancy Grid. Rather than running a specific loop closure algorithm, an occupancy grid is used, whereby the environment is defined by a grid of small cells, for example, one meter by one meter squares. As each particle propagates, representing a hypothesis of the user path, it posts its identity and the current step number into the occupancy grid. As the user continues to move, the particles check the grid cells they move through for any previous visits. If a particle has visited a cell before, the current sensor measurements are compared to those recorded at the time of the last visit. If there is close agreement (typically scored using metrics such as the Euclidean or Mahalanobis distances) then that particular particle is given a high weight. Conversely, poor agreement results in a low weighting.

    The entire particle cloud can be reweighted accordingly with low-scoring particles being killed and high-scoring particles being duplicated. The result is the particle cloud collapsing towards the region of close agreement between old and new sensor measurements. Because the occupancy grid contains the historical path of each particle stored via their IDs and step-number sequence, when a reweighting of particles occurs, the historical path of the user is updated and improved accordingly along with the current estimate of the user’s location.

    The SLAM estimate can be improved by many types of observations, not just loop closures. If the user moves outside and confident GNSS locations become available, these can also be used to reweight the particle cloud. If the user moves into a region where the floor plan of the building is available to the positioning engine, particles can be pruned whenever they try to cross walls. If desired, even direct user interaction such as manually tapping the map on the smartphone display could be used to provide a position estimate and so constrain the particle cloud.

    FIGURE 3 shows six stages from a walk around the corridors of a building using an indoor positioning smartphone app to track the user. The red dashed line shows the trace using just the PDR scheme, which exhibits gradual degradation in positioning accuracy. The green solid line shows the trace using SLAM to constrain the PDR error growth using magnetic anomalies and Wi-Fi signal strengths.

    FIGURE 3A.
    FIGURE 3A.
    FIGURE 3B.
    FIGURE 3B.
    FIGURE 3C.
    FIGURE 3C.
    FIGURE 3D.
    FIGURE 3D.
    FIGURE 3E.
    FIGURE 3E.
    FIGURE 3F.
    FIGURE 3F.

    Visual Odometry

    A further modern advance is in computer vision: the use of cameras and algorithms to monitor and interpret features in the environment. The movement of features within the field of view from frame to frame can be used to determine the motion of the camera if it is assumed that the majority of the objects tracked through the view are actually static in the environment. Consistency checks between features allow those corresponding to other moving objects to be filtered out.

    The result of this visual odometry scheme is the ability to determine the speed and heading changes of the camera by observing the optical flow of the environment. As with PDR approaches, integrating over visual odometry measurements results in motion tracking with much slower reduction in accuracy over time and distance than for systems built upon traditional IMU integration (accelerometers and gyroscopes) alone. If specific objects or features can be uniquely identified and recognized when seen again in the future, then SLAM techniques can also be applied. At the moment, smartphones are powerful enough to apply computer vision techniques and calculations at moderate update rates of a few frames per second. As smartphones become more powerful, or if mobile operating systems will, in future, permit these computer vision algorithms to be deployed on the dedicated graphical processing units, or even perhaps if devices such as Google Glass result in the deployment of dedicated computer vision chips within devices, we will see computer vision coupled with augmented reality move to the forefront of smartphone navigation.

    The Future

    Our desire for accurate positioning and tracking anywhere will never go away. The availability of cheap, accurate GPS over the last decade has resulted in accurate positioning, navigation, and timing not only being something we take for granted, but something society has come to depend upon. The positioning capabilities of our smartphones will continue to improve, not only because of the new developments and capabilities described above, but because of new infrastructure developments.

    The In-Location Alliance is a large consortium of companies including big names like Nokia and CSR who are defining standards for Bluetooth and other beacon-based positioning technologies for dedicated deployments in indoor environments such as shopping centers, airports, and museums. The new 4G LTE signal structure also contains a dedicated ranging signal to permit traditional timing-based positioning schemes to be easily deployed using these new cellular standards. All infrastructure-based schemes incur costs associated with deployment and maintenance that ultimately limit their scope of deployment; opportunistic schemes are the key to truly ubiquitous positioning.

    While billions of dollars are being spent worldwide on deploying and maintaining new GNSS, there will always be scenarios and environments where these weak signals are blocked or severely corrupted. In these cases, opportunistic sensing powered by smart algorithms running on consumer devices costing a few hundred dollars will be there to fill those gaps.

    Ramsey Faragher is a senior research associate at the University of Cambridge and an associate editor for the journal of the Royal Institute of Navigation. Previously he was a principal scientist at the BAE Systems Advanced Technology Centre, near Chelmsford in the United Kingdom, where he developed the NAVSOP GNSS-denied positioning system. His research interests include opportunistic positioning, sensor fusion, and machine learning.

    Robert Harle is a senior lecturer at the University of Cambridge with research interests in positioning, sensor fusion, and wireless sensor networks. He has worked on indoor positioning since 2000, developing a series of infrastructure-based and infrastructure-free solutions.

    FURTHER READING

    • Simultaneous Localization and Mapping

    “SmartSLAM – An Efficient Smartphone Indoor Positioning System Exploiting Machine Learning and Opportunistic Sensing” by R.M. Faragher and R.K. Harle in Proceedings of ION GNSS+ 2013, the 26th International Technical Meeting of the Satellite Division of The Institute of Navigation, Nashville, Tennessee, September 16–20, 2013 (in press).

    “Opportunistic Radio SLAM for Indoor Navigation Using Smartphone Sensors,” by R. Faragher, C. Sarno, and M. Newman in Proceedings of PLANS 2012, Institute of Electrical and Electronics Engineers / Institute of Navigation Position, Location and Navigation Symposium, Myrtle Beach, South Carolina, April 23–26, 2012, pp. 120-128.

    “Efficient, Generalized Indoor WiFi GraphSLAM” by J. Huang, D. Millman, M. Quigley, D. Stavens, S. Thrun, and A. Aggarwal in Proceedings of 2011 IEEE International Conference on Robotics and Automation, Shanghai, May 9–13, 2011, pp. 1038–1043, doi: 10.1109/ICRA.2011.5979643.

    “WiFi-SLAM Using Gaussian Process Latent Variable Models” by B. Ferris, D. Fox, and N. Lawrence in Proceedings of IJCAI-07, the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6–12, 2007, R. Sangal, H. Mehta, and R. K. Bagga (Eds.), published by Morgan Kaufmann Publishers Inc., San Francisco, California, pp. 2480–2485.

    “Simultaneous Map Building and Localization for an Autonomous Mobile Robot” by J.J. Leonard and H.F. Durrant-Whyte in Proceedings of IROS’91, Institute of Electrical and Electronics Engineers / Robotics Society of Japan International Workshop on Intelligence for Mechanical Systems, Osaka, Japan, November 3–5, 1991, pp. 1442–1447, doi: 10.1109/IROS.1991.174711.

    • Integrated Indoor Navigation

    “A Survey of Indoor Inertial Positioning Systems for Pedestrians” by R. Harle in IEEE Communications Surveys & Tutorials, Vol. 15, No. 3, 2013, pp. 1281–1293, doi: 10.1109/SURV.2012.121912.00075.

    Principles of GNSS, Inertial, and Multisensor Integrated Navigation Systems, Second Edition, by P.D. Groves, published by Artech House, Boston, Massachusetts, 2013.

    • Wi-Fi Positioning

    “Wi-Fi Azimuth and Position Tracking Using Directional Received Signal Strength Measurements” by J. Seitz, T. Vaupel, S. Haimerl, J.G. Boronat, and J. Thielecke in Proceedings of 2012 Workshop on Sensor Data Fusion: Trends, Solutions, Applications, Bonn, September 4–6, 2012, pp. 72–77, doi: 10.1109/SDF.2012.6327911.

    “Comparison of WiFi Positioning on Two Mobile Devices” by P.A. Zandbergen in Journal of Location Based Services, Vol. 6, No. 1, 2012, pp. 35–50, doi: 10.1080/17489725.2011.630038.

    • Step Length and Pedestrian Navigation

    “Step Length Estimation Using Handheld Inertial Sensors” by V. Renaudin, M. Susi, and G. Lachapelle in Sensors, Vol. 12, No. 7, 2012, pp. 8507–8525, doi: 10.3390/s120708507.

    • Computer Vision and Navigation

    “Improving the Accuracy of EKF-Based Visual-Inertial Odometry” by L. Mingyang and A.I. Mourikis in Proceedings of 2012 IEEE International Conference on Robotics and Automation, Saint Paul, Minnesota, May 14–18, 2012, pp. 828–835, doi: 10.1109/ICRA.2012.6225229.

    • Machine Learning

    Information Theory, Inference and Learning Algorithms by D.J.C. MacKay, published by Cambridge University Press, Cambridge, U.K., 2003.

    • Mobile Phone GPS Antenna Performance

    “Mobile-Phone GPS Antennas: Can They Be Better?” by T. Haddrell, M. Phocas, and N. Ricquier in GPS World, Vol. 21, No. 2, February 2010, pp. 29–35.

     

  • Innovation: Under Cover

    Innovation: Under Cover

    Synthetic-Aperture GNSS Signal Processing

    By Thomas Pany, Nico Falk, Bernhard Riedl, Carsten Stöber, Jón O. Winkel, and Franz-Josef Schimpl

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    A SYNTHETIC APERTURE? WHAT’S THAT? Well, an aperture in optics is just a hole or opening through which light travels. Those of us into photography know that the amount of light reaching the camera’s imaging sensor is controlled by the shutter speed and the size of the lens opening or aperture (called the f-stop). And a correct combination of the aperture setting and shutter speed results in a correct exposure.  For an optical telescope, its aperture is the diameter of its main, light-gathering lens or mirror. A larger aperture gives a sharper and brighter view or image.

    In the radio part of the electromagnetic spectrum, the term aperture refers to the effective collecting (or transmitting) area of an antenna. The gain of the antenna is proportional to its aperture and its beamwidth or resolution is inversely proportional to it.

    Astronomers, whether using optical or radio telescopes, often seek higher and higher resolutions to see more detail in the objects they are investigating. Conventionally, that means larger and larger telescopes. However, there are limits to how large a single telescope can be constructed. But by combining the light or radio signals from two or more individual telescopes, one can synthesize a telescope with a diameter equal to the baseline(s) connecting those telescopes. The approach is known as interferometry. It was first tried in the optical domain by the American physicist Albert Michelson who used the technique to measure the diameter of the star Betelgeuse. Radio astronomers developed cable- and microwave-connected interferometers and subsequently they invented the technique of very long baseline interferometry (VLBI) where atomic-clock-stabilized radio signals are recorded on magnetic tape and played back through specially designed correlators to form an image. (VLBI has also been used by geodesists to precisely determine the baselines between pairs of radio telescopes even if they are on separate continents.)

    A similar approach is used in synthetic-aperture radar (SAR). Mounted on an aircraft or satellite, the SAR beam-forming antenna emits pulses of radio waves that are reflected from a target and then coherently combined. The different positions of the SAR, as it moves, synthesize an elongated aperture resulting in finer spatial resolution than would be obtained by a conventional antenna.

    But what has all of this got to do with GNSS? In this month’s column, we take a look at a novel GNSS signal-processing technique, which uses the principles of SAR to improve code and carrier-phase observations in degraded environments such as under forest canopy. The technique can simultaneously reject multipath signals while maximizing the direct line-of-sight signal power from a satellite. Along with a specially programmed software receiver, it uses either a single conventional antenna mounted, say, on a pedestrian’s backpack for GIS applications or a special rotating antenna for high-accuracy surveying. Want to learn more? Read on.

    “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.

    Over the past few years, we have been developing new GNSS receivers and antennas based on an innovative signal-processing scheme to significantly improve GNSS tracking reliability and accuracy under degraded signal conditions. It is based on the principles of synthetic-aperture radar. Like in a multi-antenna phased-array receiver, GNSS signals from different spatial locations are combined coherently forming an optimized synthetic antenna-gain pattern. Thereby, multipath signals can be rejected and the line-of-sight received signal power is maximized. This is especially beneficial in forests and in other degraded environments.

    The method is implemented in a real-time PC-based software receiver and works with GPS, GLONASS, and Galileo signals. Multiple frequencies are generally supported.

    The idea of synthetic-aperture processing is realized as a coherent summation of correlation values of each satellite over the so-called beam-forming interval. Each correlation value is multiplied with a phase factor. For example, the phase factor can be chosen to compensate for the relative antenna motion over the beam-forming interval and the resulting sum of the scaled correlation values represents a coherent correlation value maximizing the line-of-sight signal power. Simultaneously, signals arriving from other directions are partly eliminated.

    Two main difficulties arise in the synthetic-aperture processing. First, the clock jitter during the beam-forming interval must be precisely known. It can either be estimated based on data from all signals, or a stable oscillator can be used. In one of our setups, a modern oven-controlled crystal oscillator with an Allan variance of 0.5 × 10-13 at an averaging period of 1 second is used. Second, the precise relative motion of the antenna during the beam-forming interval must be known. Again it can be estimated if enough sufficiently clean signals are tracked. The antenna trajectory is estimated directly from the correlator values as shown later in this article. In more severely degraded environments, the antenna may be moved along a known trajectory. We are developing a rotating antenna displacement unit. (see FIGURE 1). The rotational unit targets forestry and indoor surveying applications. The relative motion of the antenna is measured with sub-millimeter accuracy.

    FIGURE 1. Artist’s impression of the synthetic-aperture GNSS system for surveying in a forest.
    FIGURE 1. Artist’s impression of the synthetic-aperture GNSS system for surveying in a forest.

    After beam-forming, the code pseudoranges and the carrier phases are extracted and used in a conventional way. That is, they are written into Receiver Independent Exchange (RINEX) format files and standard geodetic software can be used to evaluate them. In the case where the artificial movement antenna is used, the GNSS signal processing removes the known part of the movement from the observations, and the observations are then like those from a static antenna. As a result, common static positioning algorithms, including carrier-phase ambiguity fixing, can be applied. The presented method therefore prepares the path for GNSS surveying applications in new areas. An important point is the mechanical realization of the antenna movement. This has to be done in a cost-efficient and reliable way. Lubrication-free actuators are used together with magnetic displacement sensors. The sensors are synchronized to the software receiver front end with better than 1 millisecond accuracy. The rotating antenna uses slip rings to connect the antenna elements. The rotating antenna can also be used to map the received signal power as a function of elevation and azimuth angles. This is beneficial for researchers. For example, it could be used to estimate the direction of arrival of a spoofing signal or to determine which object causes multipath in an indoor environment. For the latter purpose, the rotating antenna can be equipped with left-hand and right-hand circularly polarized antennas on both ends of the rotating bar. The rotating antenna is mounted on a geodetic tripod. See Further Reading for reports of initial studies of the rotating antenna.

    Tracking Modes

    The synthetic-aperture tracking scheme can be extended to different user-motion schemes or sensor-aiding schemes allowing a wide range of applications. This is reflected in the algorithm implementation within the modular structure of the software receiver. The base module “µ-trajectory & Clock Estimator” in Figure 2 prepares the synthetic-aperture tracking scheme. Different implementations derive from this base class. Each derived module is used for a different user motion scheme and makes use of a different sensor.

    FIGURE 2. Different µ-trajectory motion estimators used by the synthetic-aperture processing.
    FIGURE 2. Different µ-trajectory motion estimators used by the synthetic-aperture processing.

    Basically, the modules differ in the way they estimate the relative antenna motion over the beam-forming interval. This relative motion is called the µ-trajectory. Usually the µ-trajectory covers time spans from a few hundreds of milliseconds to a few seconds.

    The µ-trajectories have the following characteristics:

    • The pedestrian motion estimator does not rely on any sensor measurements and fits a second-order polynomial into the user µ-trajectory of a walking pedestrian. A second-order polynomial is good for representing the motion for up to a quarter of a second.
    • The sensor input to the rotating antenna estimator is the relative angular displacement of the rotating antenna. The estimator estimates the absolute direction, which is stable in time. Thus the number of µ-trajectory parameters equals one.
    • The vertical antenna motion estimator retrieves the vertical position of the antenna and does not estimate any µ-trajectory parameters. Only clock parameters are estimated.
    • Finally, the inertial navigation estimator uses accelerometer and gyro measurements and estimates the 3D user motion. The µ-trajectory parameters consist of accelerometer biases, the gyro biases, attitude errors, and velocity errors. The estimation process is much more complex and exploits the timely correlation of the parameters.

    Signal Processing Algorithm

    Two kinds of (related) carrier-phase values occur in a GNSS receiver: the numerically controlled oscillator (NCO) internal carrier phase  ocarrot1  and the carrier phase pseudorange ocarrot, which is actually the output of the receiver in, for example, RINEX  format files. Both are a function of time t and when expressed in radians are related via Equation (1):

    Inno-eq1    (1)

    Here, fo denotes the receiver internal nominal intermediate frequency (IF) at which all signal processing takes place. The output carrier-phase pseudorange ocarrot is an estimate of the true carrier-phase pseudorange , which, in turn, relates to the geometric distance to the satellite by the following standard model:

    inno-eq2   (2)

    This model applies to each signal propagation path separately; that is, a separate model can be set up for the line-of-sight signal and for each multipath signal. In Equation (2), λ denotes the nominal carrier wavelength in meters, ρ(t) is the geometric distance in meters between transmitting and receiving antennas, fRF is the nominal carrier frequency in hertz, dtsat(t) and dtrec(t) are the satellite and receiver clock errors in seconds, N is the carrier-phase ambiguity, and T(t) contains atmospheric delays as well as any hardware delays in meters. Here, no measurement errors are included, because we are considering the relationship between true values.

    Defining now a reference epoch t0, we will describe a procedure to obtain an improved carrier-phase estimate  for this epoch using data from an interval [t0 – TBF, t0]. The beam-forming interval TBF can be chosen to be, for example, 0.2–2 seconds but should be significantly longer than the employed predetection integration time (the primary one, without beam forming).

    Correlator Modeling. In this sub-section, the relationships between phase, correlator values, and geometric distances will be established. These relationships apply for each propagation path individually. In the next section these relationships will be applied to the total received signal, which is the sum of all propagation paths plus thermal noise. To model the correlator output we assume that any effect of code or Doppler-frequency-shift misalignment on carrier-phase tracking can be neglected. This is reasonable if the antenna motion can be reasonably well predicted and this prediction is fed into the tracking loops as aiding information. Then the prompt correlator output is given as

    inno-eq3.   (3)

    Again, any noise contribution is not considered for the moment. Here a(t) denotes the signal amplitude and d(t) a possibly present navigation data bit. The carrier phase difference Δφ is given as

    Inno-eq4  (4)

    where φ(t) is the true carrier phase and φNCO(t) is the NCO carrier phase used for correlation.

    We now split the geometric line-of-sight distance into an absolute distance, the satellite movement and a relative distance:

    Inno-eq5  (5)

    For the example of the rotating antenna, t0 might be the epoch when the antenna is pointing in the north direction. The term ρ0(t0) is the conventional satellite-to-reference-point distance (for example, to the rotation center) and ρsat(t0,t) accounts for the satellite movement during the beam-forming interval.

    The term Δρµ(t) is the rotational movement and may depend on the parameter µ. The parameter µ represents, for the rotating antenna, the absolute heading but may represent more complex motion parameters. The absolute term ρ0(t0) is constant but unknown in the beam-forming interval. We assume that approximate coordinates are available and thus Δρµ(t) can be computed for a given set of µ (that is, the line-of-sight projection of the relative motion is assumed to be well predicted even with only approximate absolute coordinates). The same applies also to ρsat(t0,t).

    Let’s assume that the NCOs are controlled in a way that the satellite movement is captured as well as the satellite clock drift and the atmospheric delays:

    Inno-eq6. (6)

    Then

    Inno-eq7(7)

    and

    Inno-eq8.(8)

    Thus the correlator output depends on the absolute distance of the reference point to the satellite at t0, the relative motion of the antenna, the receiver clock error, the received amplitude and the broadcast navigation data bits. Satellite movement and satellite clock drift are absent.

    Let us now denote m as the index for the different satellites under consideration. The index k denotes correlation values obtained during the beam-forming interval at the epoch tk. Then:

    Inno-eq9.(9)

    If multiple signal reflections are received and if they are denoted by the indices m1, m2, … , then the correlator output is the sum of those:

    Inno-eq10.(10)

    For the following, m or m1 denotes the line-of-sight signal and mn with n > 1 denoting multipath signals.

    Estimation Principle. It seems natural to choose receiver clock parameters dtrec and trajectory parameters µ in a way that they optimally represent the receiver correlation values. This approach mimics the maximum likelihood principle. The estimated parameters are:

    Inno-eq11.(11)

    Data bits are also estimated in Equation (11). Once this minimization has been carried out, the parameters µ and dtrec are known as well as the data bits. The real-time implementation of Equation (11) is tricky. It is the optimization of a multi-dimensional function. Our implementation consists of several analytical simplifications as well as a highly efficient implementation in C code. The pedestrian estimator has been ported to a Compute-Unified-Device-Architecture-capable graphics processing unit exploiting its high parallelism.

    Equation (11) realizes a carrier-phase-based vector tracking approach and the whole µ-trajectory (not only positions or velocity values) is estimated at once from the correlation values. This optimally combines the signals from all satellites and frequencies. The method focuses on the line-of-sight signals as only line-of-sight signals coherently add up for the true set of µ-trajectory and clock parameters. On the other hand, multipath signals from different satellites are uncorrelated and don’t show a coherent maximum.

    Purified Correlator Values. The line-of-sight relative distance change Δρµm(t) due to the antenna motion is basically the projection of the µ-trajectory onto the line-of-sight. Multipath signals may arrive from different directions, and delatp  is the antenna motion projected onto the respective direction of arrival.

    Let the vector trident  denote the phase signature of the nth multipath signal of satellite m based on the assumed µ-trajectory parameters µ:

    Inno-eq12.(12)

    Projecting the correlator values that have been corrected by data bits and receiver clock error onto the line-of-sight direction yields:

    Inno-eq13. (13)

    The correlator values Q are called purified values as they are mostly free of multipath, provided a suitable antenna movement has been chosen. This is true if we assume a sufficient orthogonality of the line-of-sight signal to the multipath signals, and we can write:

    Inno-eq14.(14)

    where K is the number of primary correlation values within the beam-forming interval. The projection onto the line-of-sight phase signature is then

    Inno-eq15.(15)

    Thus the purified correlator values represent the unknown line-of-sight distance from the reference point to the satellite. Those values are used to compute the carrier pseudorange. The procedure can similarly also be applied for early and late correlators. The purified and projected correlation values represent the correlation function of the line-of-sight signal and are used to compute the code pseudorange.

    Block Diagram

    This section outlines the block diagram shown in Figure 3 to realize the synthetic-aperture processing. The signal processing is based on the code/Doppler vector-tracking mode of the software receiver.

    FIGURE 3. Synthetic-aperture signal processing.
    FIGURE 3. Synthetic-aperture signal processing.

    The scheme has not only to include the algorithms of the previous section but it has also to remove the known part of the motion (for the rotating antenna, say) from the output observations. In that case, the output RINEX observation files should refer to a certain static reference point. This is achieved by a two-step process.

    First, the known and predictable part of the motion is added to the NCO values. By doing that, the correlation process follows the antenna motion to a good approximation, and the antenna motion does not stress the tracking loop dynamics of the receiver. Furthermore, discriminator values are small and in the linear region of the discriminator. Second, the difference between the current antenna position and the reference point is projected onto the line-of-sight and is removed from the output pseudoranges and Doppler values. For further details on the processing steps of the block diagram, see the conference paper on which this article is based, listed in Further Reading.

    Pedestrian Estimator

    We tested the synthetic-aperture processing for pedestrians on a dedicated test trial and report the positing results in this section. These results are not final and are expected to improve as more GNSSs are included and general parameter tuning is performed.

    Test Area. To test the pedestrian estimator, we collected GPS L1 C/A-code and GLONASS G1 signals while walking through a dense coniferous forest. The trees were up to 30–40 meters high and are being harvested by a strong local lumber industry. The test was carried out in May 2012. We staked out a test course inside the forest and used terrestrial surveying techniques to get precise (centimeter accuracy) coordinates of the reference points. Figure 4 shows a triangular part of the test course.

    FIGURE 4. Triangular test course in a forest.
    FIGURE 4. Triangular test course in a forest.

    Measurement data was collected with a geodetic-quality GNSS antenna fixed to a backpack. This is a well-known style of surveying. We used a GNSS signal splitter and a commercial application-specific-integrated-circuit- (ASIC-) based high-sensitivity GNSS receiver to track the signals and to have some kind of benchmark. The algorithms of this ASIC-based receiver are not publicly known, but the performance is similar to other ASIC-based GNSS receivers inside forests.

    We came from the west, walked the triangular path five times, left to the north, came back from the north, walked the triangular path again five times clockwise, and left to the west. We note that the ASIC-based receiver shows a 3–5 meter-level accuracy with some outliers of more than 10 meters. We further note that the use of the geodetic antenna was critical to achieve this rather high accuracy inside the forest.

    µ-trajectory Estimation. As mentioned before, the pedestrian estimator uses a second-order polynomial to model the user motion over an interval of 0.2 seconds. If we stack the estimated µ-trajectories over multiple intervals, we get the relative motion of the user. An example of the estimated user motion outside (but near) the forest is shown in Figure 5.

    FIGURE 5. Estimated relative user trajectory over 5 seconds outside the forest; user walking horizontally.
    FIGURE 5. Estimated relative user trajectory over 5 seconds outside the forest; user walking horizontally.

    The figure clearly shows that the walking pattern is quite well estimated. An up/down movement of ~10 cm linked to the walking pattern is visible. Inside the forest, the walking pattern is visible but with less accuracy.

    Synthetic-Aperture Antenna Pattern. It is possible to estimate the synthetic antenna gain pattern for a given antenna movement (see “Synthetic Phased Array Antenna for Carrier/Code Multipath Mitigation” in Further Reading). The gain pattern is the sensitivity of the receiver/antenna system to signals coming from a certain direction. It depends on the known direction of the line-of-sight signal and is computed for each satellite individually. It adds to the normal pattern of the used antenna element.

    We assume that the system simply maximizes the line-of-sight signal power for an assumed satellite elevation of 45° and an azimuth of 135°. We model the pedestrian movement as horizontal with a constant speed of 1 meter per second, and an up/down movement of ± 7.5 centimeters with a period of 0.7 seconds. Employing a beam-forming interval of 2 seconds yields the synthetic antenna gain pattern of Figure 6.The pattern is symmetric to the walking direction. It shows that ground multipath is suppressed.

    FIGURE 6. Synthetic antenna aperture diagram for a walking user and beam-forming interval of 2 seconds.
    FIGURE 6. Synthetic antenna aperture diagram for a walking user and beam-forming interval of 2 seconds.

    Positioning Results. Our receiver implements a positioning filter based on stacking the estimated µ-trajectory segments. As already mentioned, the stacked µ-trajectory segments represent the relative movement of the user. GNSS code pseudorange observations are then used to get absolute coordinates. Basically, an extended Kalman filter is used to estimate a timely variable position offset to the stacked µ-trajectory segments. The Kalman filter employs a number of data-quality checks to eliminate coarse outliers. They are quite frequent in this hilly forested environment.

    The positioning results obtained are shown in Figure 7. They correspond to the same received GPS+GLONASS signal but three different beam-forming intervals (0.2, 1, and 2 seconds) have been used. The position output rate corresponds to the beam-forming interval. Blue markers correspond to the surveyed reference positions, and the yellow markers are estimates when the user is at those reference markers. For each marker, there are ten observations.

    FIGURE 7. Estimated user trajectory with 0.2, 1, and 2 seconds beam-forming interval (blue: surveyed reference markers).
    FIGURE 7. Estimated user trajectory with 0.2, 1, and 2 seconds beam-forming interval (blue: surveyed reference markers).

    The triangular walking path is clearly visible. We observe a bias of around 3 meters and a distance-root-mean-square of 1.2 meters if accounting for this bias (the values refer to the 2-second case). The reason for the bias has not yet been investigated. It could be due to ephemeris or ionospheric errors, but also possibly multipath reflections.

    For the short beam-forming interval of 0.2 seconds, we observe noisier walking paths, and we would also expect less accurate code observations. However, the code observation rate is highest in this case (5 Hz), and multipath errors tend to average out inside the Kalman filter. In contrast, the walking paths for the 1-second or 2-second case are straighter. The beam-forming seems to eliminate the multipath, and there are fewer but more precise observations.

    Artificial Motion Antennas

    The rotating antenna targets surveying applications. It fits standard geodetic equipment. The antenna is controlled by the software receiver, and the rotational information is synchronized to the received GNSS signal.

    Synthetic-Aperture Antenna Pattern. With the same methodology as referenced previously, it is possible to estimate the synthetic antenna gain pattern. We assume that the pattern simply maximizes the line-of-sight signal power for an assumed satellite elevation angle of 45° and an azimuth of 135°. We use a rotation radius of 50 cm. The antenna has a really high directivity, eliminating scattered signals from trees. The gain pattern is symmetric with respect to the horizon and ground multipath of perfectly flat ground would not be mitigated by the synthetic aperture. Ground multipath is only mitigated by the antenna element itself (for example, a small ground plane can be used). However, mostly the ground is not flat, and in that case the rotating antenna also mitigates the ground multipath.

    Results with a Simulator. The rotating antenna has been tested with simulated GNSS signals using an RF signal generator. The signal generator was configured to start with the antenna at rest, and at some point the antenna starts rotating with a speed of 15 revolutions per minute. Six GPS L1 C/A-code signals have been simulated.

    The signal-processing unit has to estimate the antenna state (static or rotating) and the north direction. The quality of the estimation can be visualized by comparing the complex argument of the prompt correlator values to the modeled correlator values. Two examples are shown in FIGURES 8 and 9. In Figure 8, the differences are at the millimeter level corresponding to the carrier-phase thermal noise. This indicates that the absolute heading and receiver clock parameters have been estimated to a high precision.

    FIGURE 8. Carrier-phase residuals for all satellites observed with the rotating antenna without multipath. Time is in seconds and all data contributing to the RINEX observation record has been considered.
    FIGURE 8. Carrier-phase residuals for all satellites observed with the rotating antenna without multipath. Time is in seconds and all data contributing to the RINEX observation record has been considered.
    FIGURE 9. Carrier-phase residuals for all satellites observed with the rotating antenna with multipath. Time is in seconds and all data contributing to the RINEX observation record has been considered.
    FIGURE 9. Carrier-phase residuals for all satellites observed with the rotating antenna with multipath. Time is in seconds and all data contributing to the RINEX observation record has been considered.

    If multipath from a reflection plane is present (see Figure 9), the phase residuals show the multipath reflection. For example, around t = -0.65 seconds in the figure, the antenna is moving parallel to the reflection plane and the phase residuals are constant over a short time span. As the distance of the antenna to the reflection plane changes, the phase residuals start to oscillate. Generally, the estimation of the absolute heading and of the receiver clock parameters works even with strong multipath signals, but the parameters are not as stable as in the multipath-free case.

    In the case when the antenna is rotating, signal processing has to remove the rotation from the code and carrier observations. To check if this elimination of the artificial motion is done correctly, we use carrier-smoothed code observations to compute a single-point-positioning solution. Only if the antenna is rotating can the system estimate the absolute heading and refer the observations to the rotation center. Before that point, the observations refer to the antenna position. The antenna position and the rotation center differ by the radius of 0.5 meters. Since the position is stable for t > 100 seconds, we conclude that the elimination of the artificial motion has been done correctly.

    Conclusion

    We are in the process of developing positioning solutions for degraded environments based on principles of synthetic-aperture processing. The tools target operational use as an end goal, supporting standard geodetic form factors (tripods) and the software receiver running on standard laptops, and producing data in standardized formats (such as RINEX or the National Marine Electronics Association (NMEA) standards).
    Acknowledgments

    The research leading to the results reported in this article received funding from the European Community’s Seventh Framework Programme (FP7/2007-2013) under grant agreement No. 287226. This support is gratefully acknowledged. It also received funding from the Upper Bavarian Administration Aerospace Support Program under the contract number 20-8-3410.2-14-2012 (FAUSST), which is also thankfully acknowledged. This article is based on the paper “Concept of Synthetic Aperture GNSS Signal Processing Under Canopy” presented at the European Navigation Conference 2013, held in Vienna, Austria, April 23–25, 2013.

    Manufacturer

    The research described in this article used an IFEN SX-NSR GNSS software receiver and an IFEN NavX-NCS RF signal generator. The rotating antenna displacement unit was designed and manufactured by Blickwinkel Design & Development.

    THOMAS PANY works for IFEN GmbH in Munich, Germany, as a senior research engineer in the GNSS receiver department. He also works as a lecturer (Priv.-Doz.) at the University of the Federal Armed Forces (FAF) Munich and for the University of Applied Science in Graz, Austria. His research interests include GNSS receivers, GNSS/INS integration, signal processing and GNSS science.

    NICO FALK received his diploma in electrical engineering from the University of Applied Sciences in Offenburg, Germany. Since then, he has worked for IFEN GmbH in the receiver technology department, focusing on signal processing, hardware, and field-programmable-gate-array development.

    BERNHARD RIEDL received his diploma in electrical engineering and information technology from the Technical University of Munich. Since 1994, he has been concerned with research in the field of real-time GNSS applications at the University FAF Munich, where he also received his Ph.D. In 2006, he joined IFEN GmbH, where he is working as the SX-NSR product manager.

    JON O. WINKEL is head of receiver technology at IFEN GmbH since 2001. He studied physics at the universities in Hamburg and Regensburg, Germany. He received a Ph.D. (Dr.-Ing.) from the University FAF Munich in 2003 on GNSS modeling and simulations.

    FRANZ-JOSEF SCHIMPL started his career as a mechanical engineer and designer at Wigl-Design while studying mechanical engineering. In 2002, he founded Blickwinkel Design & Development with a focus on prototyping and graphic design.

    FURTHER READING

    • Authors’ Conference Paper

    “Concept of Synthetic Aperture GNSS Signal Processing Under Canopy” by T. Pany, N. Falk, B. Riedl, C. Stöber, J. Winkel, and F.-J. Schimpl, Proceedings of ENC-GNSS 2013, the European Navigation Conference 2013, Vienna, Austria, April 23–25, 2013.

    • Other Publications on Synthetic-Aperture GNSS Signal Processing

    “Synthetic Aperture GPS Signal Processing: Concept and Feasibility Demonstration” by A. Soloviev, F. van Graas, S. Gunawardena, and M. Miller in Inside GNSS, Vol. 4, No. 3, May/June 2009, pp. 37–46. An extended version of the article is available online: http://www.insidegnss.com/node/1453  

    “Demonstration of a Synthetic Phased Array Antenna for Carrier/Code Multipath Mitigation” by T. Pany and B. Eissfeller in Proceedings of ION GNSS 2008, the 21st International Technical Meeting of The Institute of Navigation, Savannah, Georgia, September 16–19, 2008, pp. 663-668.

    “Synthetic Phased Array Antenna for Carrier/Code Multipath Mitigation” by T Pany, M. Paonni, and B. Eissfeller in Proceedings of ENC-GNSS 2008, the European Navigation Conference 2013, Toulouse, France, April 23–25, 2008.

    • Software Receiver

    “Software GNSS Receiver: An Answer for Precise Positioning Research” by T. Pany, N. Falk, B. Riedl, T. Hartmann, G. Stangl, and C. Stöber in GPS World, Vol.  23, No. 9, September 2012, pp. 60–66.

     

  • Innovation: Getting a Grip on Multi-GNSS

    Innovation: Getting a Grip on Multi-GNSS

    The International GNSS Service MGEX Campaign

    INNOVATION INSIGHTS by Richard Langley
    INNOVATION INSIGHTS by Richard Langley

    By Oliver Montenbruck, Chris Rizos, Robert Weber, Georg Weber, Ruth Neilan, and Urs Hugentobler

    GPS IS ALMOST 40 YEARS OLD. While mass consumer use of GPS began only within the past decade or so, GPS was “born” during the Labor Day weekend of 1973, when about a dozen military officers and industry analysts under the leadership of Brad Parkinson met to consolidate the concept for a single satellite-based navigation system for the U.S. Department of Defense. Their proposal for NAVSTAR GPS was approved on December 22, 1973. The first satellite to be launched under the GPS program, on July 14, 1974, was the Naval Research Laboratory’s Navigation Technology Satellite (NTS) 1. NTS-2 followed, with a launch on June 23, 1977. These satellites carried payload components similar to those to be used on the subsequent GPS Block I or Navigation Technology Satellites. The first Block I satellite was launched on February 22, 1978, and was followed by nine others. With the launch of the Block II and IIA Operational Satellites and with 24 satellites on orbit, Initial Operational Capability was declared on December 8, 1993. Following testing, Full Operational Capability (FOC) was announced on July 17, 1995.

    Whether in reaction to the development of GPS or simply to fulfill the requirement for a system with similar capabilities for its armed forces, the former Soviet Union developed the Global’naya Navigatsionnaya Sputnikovaya Sistema or GLONASS. The first GLONASS satellite was launched on October 12, 1982. By early 1996, a fully populated FOC constellation of 24 satellites was in orbit, but the number of operational satellites dwindled to a handful due to lack of financial support. Eventually the needed funds started flowing again and on December 8, 2011, FOC was again achieved and subsequently maintained.

    With the announcement of FOC and the removal of the accuracy-limiting policy of Selective Availability on May 2, 2000, widespread consumer use of GPS took off.

    And now GPS is approaching middle age. And like for some humans approaching that milestone desirous of change, a GPS renewal or modernization is under way. New civil and military signals are being transmitted by the Block IIR-M and IIF satellites along with the legacy signals pioneered by the Block I satellites. And new GNSS signals are now coming from the satellites orbited for the Chinese BeiDou Navigation Satellite System, the Japanese Quasi-Zenith Satellite System, and Europe’s Galileo, as well as those from satellite-based augmentation systems. Although it will be some years before full constellations will be transmitting these signals, scientists and engineers are already monitoring and analyzing the new signals to learn how best to use them and how to integrate subsets of them for a wide variety of applications in positioning, navigation, and timing.

    In this month’s column, we learn the details of the effort established by the International GNSS Service to support the study of these new signals: the Multi-GNSS Experiment.

    “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, see the “Contributing Editors” section on page 4.

    Over the past four decades, GPS has evolved from a primarily military navigation system into an indispensable tool not only for society at large, but also for geodetic research and global monitoring of the Earth. And within the past decade, the world of satellite navigation has experienced dramatic changes. With GLONASS, a second GNSS has achieved full operational status; GPS is introducing modernized civil and encrypted navigation signals; and a variety of new navigation constellations are being built up in Asia and Europe.

    As of early 2013, Europe has successfully launched a total of four Galileo In-Orbit Validation (IOV) satellites, which are undergoing testing in parallel to the build up and verification of the ground segment. The satellites routinely transmit signals at four frequencies (E1, E5a, E5b, and E6) and offer a variety of publicly accessible pilot and data signals. As a unique feature, Galileo enables tracking of the alternative binary-offset-carrier (AltBOC) signal in the combined E5a+E5b band, which offers superior noise and multipath performance.

    Meanwhile, the Chinese BeiDou Satellite Navigation System (BDS; formerly known as Compass) has completed the first stage of its system deployment and declared a regional navigation service for the Asia-Pacific region operational. A total of 14 functioning satellites have been launched so far, which includes five satellites in geostationary orbit (GEO), five satellites in inclined geosynchronous orbit (IGSO), and four in medium-altitude Earth orbit (MEO). These satellites transmit signals in three frequency bands (B1, B2, B3), and tracking of the corresponding open service (OS) signals is already supported by a variety of GNSS receivers. With the release of a B1 OS Interface Control Document (ICD) at the end of 2012, the BeiDou navigation message has become publicly accessible, and users throughout the Asia-Pacific region can now benefit from BeiDou as a supplementary or stand-alone navigation system.

    The Japanese Quasi-Zenith Satellite System (QZSS) has, so far, only launched a single satellite but recent political decisions have paved the way for the build up of a mini-constellation of IGSO and GEO satellites. Aside from a high level of compatibility with GPS, QZSS has introduced new signals such as the modernized L1 Civil (L1C) signal and the L-band Experiment (LEX) signal (also known as L6) for high-precision point positioning in the E6 band. Along with this unique set of navigation signals, QZSS provides innovative service features such as the L1 Sub-meter-class Augmentation with Integrity Function (L1-SAIF or L1S) message. Also, QZSS precedes GPS in offering the new Civil Navigation (CNAV) message on L2C and L5, as well as the CNAV2 message on L1C. Long before their planned use in GPS, these messages are now broadcast on a routine basis and contain novel information such as inter-frequency corrections and Earth-orientation parameters.

    Last, but not least, GPS has now a total of four Block IIF satellites in orbit that transmit an operational L5 signal for aviation users (and others) and which fly a new generation of highly stable rubidium clocks. While neither L2C nor L5 are transmitted by a full constellation, users and investigators can gradually familiarize themselves with these new signals that will enable encryption-free dual-frequency navigation services for aeronautical and other civil applications.

    Within the International GNSS Service (IGS), more than 200 worldwide agencies have, for many years, pooled resources and permanent GNSS station data to generate precise GNSS products in support of Earth science research, multidisciplinary applications, and education. So far, this service has been restricted to two systems — namely, GPS and GLONASS. In recognition of the rapidly evolving GNSS landscape, the IGS has set up the Multi-GNSS Experiment (MGEX) to explore and promote the use of new navigation signals and constellations. It will enable an early familiarization with new GNSS, identify and overcome relevant challenges, and prepare use of emerging navigation systems in routine IGS products. MGEX comprises the build-up of a new network of sensor stations, the characterization of the user equipment and space segment, the development of new concepts and data processing tools, and the generation of early data products for Galileo, QZSS, and BeiDou. MGEX is coordinated by the IGS Multi-GNSS Working Group (MGWG), which interacts closely with other IGS entities, such as the RINEX WG, the Antenna WG, the Data Center WG, and the Infra-structure Committee.

    The article starts out with a description of the MGEX network that formed the starting point and initial focus of the overall MGEX project. Following a description of system characterization activities, the current status of multi-GNSS data products and ongoing efforts for the development of new standards for multi-GNSS-related work within the IGS are presented.

    Network

    Following a call-for-participation released in the summer of 2011, the build up of a new international network of multi-GNSS sensor stations was initiated and has grown substantionally in a short time. By the end of 2012, the MGEX network had comprised approximately 50 stations supporting at least one of the new navigation systems (Galileo, BeiDou, and QZSS) in addition to the legacy GPS, GLONASS, and SBAS systems. At last count, the network now includes 75 stations.

    The bulk of the stations is provided by IGS partners  such as Bundesamt für Kartographie und Geodäsie (BKG), Centre National d’Etudes Spatiales (CNES), Deutsches GeoForschungsZentrum (GFZ), Deutsches Zentrum für Luft- und Raumfahrt (DLR), Geoscience  Australia (GA), the Geospatial Information Authority of Japan (GSI), Institut National de l’Information Géographique et Forestière (IGN), and the Swedish National Land Survey (Lantmaeteriverket, LMV), that have upgraded existing sites with new, multi-GNSS-capable receivers and antennas or started to deploy new multi-GNSS networks (such as the COperative Network for GNSS Observation (CONGO) or CNES’s REseau GNSS pour l’IGS et la Navigation (REGINA) network).

    As shown in FIGURE 1, the present set of MGEX stations exhibits almost global coverage, even though a concentration in Europe and a reduced coverage in the Americas and the western Pacific are obvious. However, this situation is expected to improve soon with announced contributions from Geoscience Australia, the Multi-GNSS Monitoring Network (MGM-net) of the Japan Aerospace Exploration Agency (JAXA), and other stations. While most MGEX sites support tracking of Galileo satellites, only a subset of stations provides data for QZSS and BeiDou. In particular, the regional BeiDou constellation (that is, the GEO and IGSO) satellites are not well covered by the current network.

    Fig1_new
    Figure 1. Distribution of MGEX stations supporting tracking of QZSS (blue), Galileo (red), and BeiDou (yellow) as of June 2013.

    Further MGEX sites are encouraged and the nomination of sites is still possible through the MGEX submission form under the provision of relevant improvements to the capabilities, coverage, and homogeneity of the overall network.

    In terms of equipment, five basic receiver types and seven basic antenna types are employed at the MGEX stations (see TABLES 1 and 2). Observation types provided by the individual receivers have been compiled from summary reports generated by the Astronomical Institute of the University of Bern (AIUB) as part of their routine monitoring of RINEX 3 observation files from MGEX stations.

    Table 1. Receiver types in use within the MGEX network (status as of June 2013). Observation types for Galileo (E), BeiDou (C), and QZSS (J) are based on RINEX 3 observation codes as reported in the submitted data files (frequency bands: 1=L1/E1, 2=L2/B1, 5=L5/E5a, 6=E6/B3, 7=E5b/B2, 8=E5ab; signals: C = C/A-code, I = data, Q = pilot, X = data+pilot). They do not necessarily indicate the full tracking capabilities supported by the receivers but rather the observations made available to MGEX users from the respective stations.
    Table 1. Receiver types in use within the MGEX network (status as of June 2013). Observation types for Galileo (E), BeiDou (C), and QZSS (J) are based on RINEX 3 observation codes as reported in the submitted data files (frequency bands: 1=L1/E1, 2=L2/B1, 5=L5/E5a, 6=E6/B3, 7=E5b/B2, 8=E5ab; signals: C = C/A-code, I = data, Q = pilot, X = data+pilot). They do not necessarily indicate the full tracking capabilities supported by the receivers but rather the observations made available to MGEX users from the respective stations.
    Table 2. Antenna types employed within the MGEX network (as of June 2013).
    Table 2. Antenna types employed within the MGEX network (as of June 2013).

    Note that no common standard has yet evolved in terms of supported signals and observation types. This causes certain restrictions for data analysis and product generation. As an example, Galileo orbit and clock products will (at least initially) be based on E1/E5a observations due to a limited coverage of E5b and E5ab tracking.

    Selected sites (such as UNB and USNO) offer multiple receivers in short- or zero-baseline configurations to facilitate equipment characterization. Further such installations will be added to the MGEX network at the time of the proposed extensions.

    While all stations contribute data to offline archives hosted by the Crustal Dynamics Data Information Service (CDDIS), IGN, and BKG for the MGEX project, a selected subset also supports real-time analyses (see FIGURE 2). All real-time streams utilize the Networked Transport of RTCM via Internet Protocol (NTRIP), which has emerged as a standard for real-time GNSS data exchange. A dedicated MGEX caster is hosted by BKG in Frankfurt, where native raw data streams received from the individual sites are converted and encoded in the RTCM3 Multiple-Signal-Message (MSM) format.

    Figure 2. Distribution of MGEX real-time stations supporting tracking of QZSS (blue), Galileo (red), and BeiDou (yellow) as of June 2013.
    Figure 2. Distribution of MGEX real-time stations supporting tracking of QZSS (blue), Galileo (red), and BeiDou (yellow) as of June 2013.

    RTCM3-MSM will enable a harmonized framework for multi-GNSS real-time operations and ensure a seamless conversion to the RINEX3 offline data format. The new MGEX NTRIP caster provides a basis to gain early experience with the new MSM format and facilitates a timely adaptation of user software. This is further supported through freeware software modules for data conversion provided by BKG.

    System Characterization

    While a systematic quality control of the MGEX data has not yet started, first performance assessments of both the ground and space segment have been reported in the literature (see Further Reading). Overall, the measurement quality of the employed multi-GNSS receivers is found to be comparable or even superior to established GPS reference stations. A high performance is, in particular, obtained for unencrypted signals with high chipping rates and bandwidths such as the GPS/QZSS L5 and Galileo AltBOC.

    By way of example, FIGURE 3 illustrates the elevation-angle-dependency of pseudorange errors for BeiDou tracking with a Trimble NetR9 receiver as used at numerous MGEX stations. Aside from the expected variation of receiver noise, the analysis reveals a systematic code bias that varies by 0.4-0.6 meters from horizon to zenith and can best be attributed to spacecraft internal multipath.

    Figure 3. Code noise and elevation-dependent biases for BeiDou tracking.
    Figure 3. Code noise and elevation-dependent biases for BeiDou tracking.

    An interesting opportunity for system characterization is provided by triple-frequency observations (GPS+QZSS L1/L2/L5, BeiDou B1/B2/B3, Galileo E1/E5a/E5b) made available by a subset of the MGEX network.  A thermal variation of inter-frequency biases has earlier been identified for the GPS Block IIF satellites, but a high level of consistency is demonstrated for QZSS, BeiDou, and Galileo (see FIGURE 4).

    Figure 4. Triple-frequency combination of Galileo IOV-3 observations.
    Figure 4. Triple-frequency combination of Galileo IOV-3 observations.

    Products

    While the newly established MGEX network forms a mandatory prerequisite for multi-GNSS work within the IGS, the MGEX campaign supports a wider range of activities, which are now being established. Foremost, the generation of orbit and clock products for the new constellations is promoted in coordination with new and established IGS analysis centers.

    Initial Galileo IOV products have been provided by CNES/CLS, CODE, and GFZ since mid-2012, and a combined Galileo+QZSS product has been added by Technische Universität München (TUM). Aside from the MGEX network, some of these solutions make complementary use of proprietary multi-GNSS networks to compensate existing coverage limitations and achieve an improved product quality.

    TABLE 3 compares selected MGEX orbit products for the Galileo IOV satellites, while FIGURE 5 shows a time series of the difference between the TUM and CODE orbit products for IOV-1 (E11).

    Inn-Table3
    Table 3. Inter-comparison of selected MGEX orbit products for the Galileo IOV satellites. (IOV-1 (E11), DOY 323-329, 2012). Orbit differences (mean ± standard deviation) in radial (R), along-track (T) and cross-track (N) directions are provided in the upper right cells, 3D RMS position differences in the lower left. All values are in units of meters.
    Figure 5. Difference of MGEX Galileo IOV-1 (E11) orbit products from TUM and CODE for DOY 232-239, 2012 (R: radial direction, T: along-track direction, N: cross-track direction).
    Figure 5. Difference of MGEX Galileo IOV-1 (E11) orbit products from TUM and CODE for DOY 232-239, 2012 (R: radial direction, T: along-track direction, N: cross-track direction).

    TABLE 4 shows the residuals of Galileo IOV-1/2 satellite laser ranging measurements (mean ± standard deviation) relative to the GNSS-based orbit products (days of year (DOY) 323-329, 2012).

    Inn-Table4
    Table 4. Satellite laser ranging residuals (mean ± standard deviation) for Galileo IOV-1/2 orbit products (DOY 323-329, 2012). Units are centimeters.

    FIGURE 6 shows a time series of the differences between TUM orbit products for QZS-1 and precise ephemerides computed by the Japan Aerospace Exploration Agency (JAXA) for DOY 027-033, 2013. It demonstrates consistency at the 0.5-meter level, which already represents an important accomplishment, given the sparse subset of QZSS-capable MGEX stations available at the time. Further improvements are expected as the MGEX network continues to grow.

    Figure 6. Comparison of TUM MGEX orbit products of QZS-1 with precise ephemerides of JAXA for DOY 027-033, 2013.
    Figure 6. Comparison of TUM MGEX orbit products of QZS-1 with precise ephemerides of JAXA for DOY 027-033, 2013.

    Concerning the Chinese BeiDou system, which has now reached initial operational capability for a regional service, early orbit and clock determination results have been reported by various Chinese and European researchers using data from dedicated regional sensor station networks. An effort will be made to promote the extension of the BeiDou tracking capabilities within the MGEX network and to make MGEX-only or mixed network-based orbit and clock products for BeiDou accessible to a wider user community through the MGEX data centers.

    Given the late public availability of Galileo and BeiDou broadcast navigation messages, the MGEX orbit and clock products constitute a significant promotion for the early use of all available navigation systems. Aside from initial positioning experiments, they provide a basis for the in-depth characterization of both the space and user segment, and, it is hoped, will facilitate an improved interaction with system providers. Early applications of MGEX multi-GNSS products and observations have, for example, been reported at conferences and in journals (see Further Reading).

    Standardization

    In support of MGEX, the Multi-GNSS WG interacts closely with other IGS working groups to coordinate data formats, processing standards, and applicable models for use in multi-GNSS work. Examples include necessary RINEX 3 and RTCM3 extensions for full support of new GNSS signals and tracking modes as well as the rapidly growing set of diverse broadcast navigation data.

    Another focus of current work addresses the proper modeling of antenna offsets and phase patterns for receiver and satellite antennas, along with documentation of constellation-specific spacecraft coordinate systems and attitude modes. This work is performed in close coordination with the IGS Antenna WG. Among others, conventional antenna phase center offsets (see TABLE 5) have been agreed upon, which will enable consistent processing of MGEX observations until the release of official information by the Galileo and BeiDou program offices.

    Table 5. Conventional antenna offsets from the spacecraft center of mass for processing Galileo IOV and BeiDou observations. All values refer to the spacecraft coordinate system. Units are meters.
    Table 5. Conventional antenna offsets from the spacecraft center of mass for processing Galileo IOV and BeiDou observations. All values refer to the spacecraft coordinate system. Units are meters.

    Public Outreach

    As a central point for exchange of MGEX-related information with the user community, a dedicated website has been established at the IGS Central Bureau (see FIGURE 7). The new website provides an overview of available MGEX data and products with direct links to the respective archives at IGS data and product centers. Furthermore, users are provided with up-to-date information on the status of the emerging navigation satellite systems as well as recommended parameters (such as antenna offsets) for harmonized and consistent processing of MGEX observations.

    Figure 7. Homepage of the IGS Multi-GNSS Experiment at http://igs.org/mgex.
    Figure 7. Homepage of the IGS Multi-GNSS Experiment at http://igs.org/mgex.

    Through individual members, the Multi-GNSS WG is  represented on other boards and bodies such as the International Committee on GNSS, the International Association of Geodesy, and the Multi-GNSS Asia project.

    Summary and Conclusions

    As part of its continued effort to provide the highest quality data and products for all satellite navigation systems, the IGS has initiated the Multi-GNSS Experiment. MGEX supports early work with new signals and constellations. It enables a timely preparation of IGS analysis centers as well as the user community to expand from GPS/GLONASS towards full multi-GNSS processing.

    Within the first year of MGEX, substantial progress has already been made. In particular, a global network of multi-GNSS receivers has been established in parallel with the existing core IGS network and by upgrading existing sites with new multi-GNSS equipment. The MGEX network forms the backbone for all other activities, such as system characterization and product generation. Aside from offline data provisions, a substantial fraction of MGEX stations are already offering real-time data streams, which paves the way for a rapid extension of the upcoming IGS real-time pilot service to Galileo and possibly other constellations. A limited number of analysis centers have already started to provide orbit and clock products for Galileo and/or QZSS as a basis for precise positioning applications. In addition to initial positioning experiments, they will provide a basis for the in-depth characterization of both the space and user segment, and help facilitate an improved interaction with system providers.

    Upcoming activities will focus on the systematic incorporation of the BeiDou navigation satellite system. While BeiDou is the third constellation to reach an operational system status after GPS and GLONASS, it is not well covered by the current MGEX tracking network. Along with the targeted incorporation of BeiDou-capable reference stations (particularly in the Asia-Pacific region), the generation and provision of related orbit and clock products will be promoted to facilitate a timely use of BeiDou by the geodetic community.

    Subject to active participation by a sufficient number of analysis centers, the MGEX project will eventually transition into an IGS pilot project offering operational data products of Galileo, QZSS, and BeiDou within the next few years.

    OLIVER MONTENBRUCK is the head of the GNSS Technology and Navigation Group at DLR’s German Space Operations Center. He chairs the IGS Multi-GNSS Working Group and coordinates the MGEX Multi-GNSS Experiment.

    CHRIS RIZOS is a professor at the University of New South Wales, Sydney, Australia; president of the International Association of Geodesy; co-chair of the Multi-GNSS Asia Steering Committee; and a member of the executive and governing board of the IGS.

    ROBERT WEBER is an associate professor at the Department of Geodesy and Geoinformation, TU Vienna, and former chair of the IGS GNSS Working Group.

    GEORG WEBER is the scientific director in the Department of Geodesy at the German Federal Agency for Cartography and Geodesy (BKG). He is a member of the IGS Real-time Working Group and the Radio Technical Commission for Maritime (RTCM) Services Special Committee (SC) 104 on Differential Global Navigation Satellite Systems (DGNSS).

    RUTH NEILAN is the director of the Central Bureau of the IGS, vice-chair of the Global Geodetic Observing System Coordinating Board, and co-chair of Working Group D, Reference Frames, Timing and Applications, of the United Nation’s International Committee on GNSS.

    URS HUGENTOBLER is a professor at the Institute of Astronomical and Physical Geodesy, TUM, Munich. He is the chair of the IGS Governing Board.

    FURTHER READING

    • The IGS MGEX Campaign
    “The IGS MGEX Experiment as a Milestone for a Comprehensive Multi-GNSS Service” by C. Rizos, O. Montenbruck, R. Weber, G. Weber, R. Neilan, and U. Hugentobler in Proceedings of The Institute of Navigation 2013 Pacific PNT Meeting, Honolulu, Hawaii, April 23 –25, 2013, pp. 289–295.

    “Multi–GNSS Working Group” by O. Montenbruck in International GNSS Service Technical Report 2012, edited by R. Dach and Y. Jean and published by the IGS Central Bureau, April 2013. Pp. 163–170.

    “IGS M-GEX – The IGS Multi-GNSS Global Experiment” by R. Weber, U. Hugentobler, and R. Neilan in Proceedings of the 3rd International Colloquium on Scientific and Fundamental Aspects of the Galileo Programme, Copenhagen, 31 August – 2 September, 2011.

    • Initial Monitoring and Analysis Results from MGEX
    “CNES Computes Real-Time Decimeter-Accuracy Orbits with Galileo” on GPS World website, May 30, 2013.

    “Initial Assessment of the COMPASS/BeiDou-2 Regional Navigation Satellite System” by O. Montenbruck, A. Hauschild, P. Steigenberger, U. Hugentobler, P. Teunissen, and S. Nakamura in GPS Solutions, Vol. 17, No. 2, April 2013, pp. 211–222, doi: 10.1007/s10291-012-0272-x.

    “Orbit and Clock Determination of QZS-1 Based on the CONGO Network” by P. Steigenberger, A. Hauschild, O. Montenbruck, C. Rodriguez-Solano, and U. Hugentobler in Navigation – Journal of The Institute of Navigation, Vol. 60, No. 1, Spring 2013, pp. 31–40.

    “Galileo IOV-3 Broadcasts E1, E5, E6 Signals” by O. Montenbruck and R. Langley in GPS World, Vol. 24, No. 1, January 2013, pp. 18, 27.

    “Precise Positioning with Galileo Prototype Satellites: First Results” by R.B. Langley, S. Banville, and P. Steigenberger in GPS World, Vol. 23, No. 9, September 2012, pp. 45–49.

    Oral and Poster Presentations at the International GNSS Service Analysis Center Workshop 2012, Olsztyn, Poland, July 23–27, 2012:

    • GNSS Signal Structures
    Quasi-Zenith Satellite System Navigation Service: Interface Specification for QZSS (IS-QZSS), V1.5, Japan Aerospace Exploration Agency, March 27, 2013.

    BeiDou Navigation Satellite System Signal In Space Interface Control Document – Open Service Signal B1I, Version 1.0, China Satellite Navigation Office, December 2012.

    European GNSS (Galileo) Open Service: Signal In Space Interface Control Document, Ref : OS SIS ICD, Issue 1.1, September 2010.

    • RTCM and NTRIP Formats
    Differential GNSS (Global Navigation Satellite Systems) Services, Version 3, RTCM 10403.2, published by Radio Technical Commission for Maritime Services, Arlington, Virginia, February 1, 2013.

    “The RTCM Multiple Signal Messages: A New Step in GNSS Data Standardization” by A. Boriskin, D. Kozlov, and G. Zyryanov in Proceedings of ION GNSS 2012, the 25th International Technical Meeting of The Satellite Division of the Institute of Navigation, Nashville, Tennessee, September 17–21, 2012, pp. 2947–2955.

    “Networked Transport of RTCM via Internet Protocol (Ntrip) – IP-Streaming for Real-time GNSS Applications” by G. Weber, D. Dettmering, H. Gebhard, and R. Kalafus in Proceedings of ION GPS 2005, the 18th International Technical Meeting of the Satellite Division of The Institute of Navigation, Long Beach, California, September 13–16, 2005, pp. 2243–2247.

  • Innovation: GNSS Spoofing Detection

    Innovation: GNSS Spoofing Detection

    Correlating Carrier Phase with Rapid Antenna Motion

    By Mark L. Psiaki with Steven P. Powell and Brady W. O’Hanlon

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    IT’S A HOSTILE (ELECTRONIC) WORLD OUT THERE, PEOPLE. Our wired and radio-based communication systems are constantly under attack from evil doers. We are all familiar with computer viruses and worms hiding in malicious software or malware distributed over the Internet or by infected USB flash drives. Trojan horses are particularly insidious. These are programs concealing harmful code that can lead to many undesirable effects such as deleting a user’s files or installing additional harmful software. Such programs pass themselves off as benign, just like the “gift” the Greeks delivered to the Trojans as reported in Virgil’s Aeneid. This was a very early example of spoofing. Spoofing of Internet Protocol (IP) datagrams is particularly prevalent. They contain forged source IP addresses with the purpose of concealing the identity of the sender or impersonating another computing system.

    To spoof someone or something is to deceive or hoax, passing off a deliberately fabricated falsehood made to masquerade as truth. The word “spoof” was introduced by the English stage comedian Arthur Roberts in the late 19th century. He invented a game of that name, which involved trickery and nonsense. Now, the most common use of the word is as a synonym for parody or satirize — rather benign actions. But it is the malicious use of spoofing that concerns users of electronic communications.

    And it is not just wired communications that are susceptible to spoofing. Communications and other services using radio waves are, in principle, also spoofable. One of the first uses of radio-signal spoofing was in World War I when British naval shore stations sent transmissions using German ship call signs. In World War II, spoofing became an established military tactic and was extended to radar and navigation signals. For example, German bomber aircraft navigated using radio signals transmitted from ground stations in occupied Europe, which the British spoofed by transmitting similar signals on the same frequencies. They coined the term “meaconing” for the interception and rebroadcast of navigation signals (meacon = m(islead)+(b)eacon).

    Fast forward to today. GPS and other GNSS are also susceptible to meaconing. From the outset, the GPS P code, intended for use by military and other so-called authorized users, was designed to be encrypted to prevent straightforward spoofing. The anti-spoofing is implemented using a secret “W” encryption code, resulting in the P(Y) code. The C/A code and the newer L2C and L5 codes do not have such protection; nor, for the most part, do the civil codes of other GNSS. But, it turns out, even the P(Y) code is not fully protected from sophisticated meaconing attacks.

    So, is there anything that military or civil GNSS users can do, then, to guard against their receivers being spoofed by sophisticated false signals? In this month’s column, we take a look at a novel, yet relatively easily implemented technique that enables users to detect and sequester spoofed signals. It just might help make it a safer world for GNSS positioning, navigation, and timing.

    “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, see the “Contributing Editors” section on page 4.

    The radionavigation community has known about the dangers of GNSS spoofing for a long time, as highlighted in the 2001 Volpe Report (see Further Reading). Traditional receiver autonomous integrity monitoring (RAIM) had been considered a good spoofing defense. It assumes a dumb spoofer whose false signal produces a random pseudorange and large navigation solution residuals. The large errors are easy to detect, and given enough authentic signals, the spoofed signal(s) can be identified and ignored.

    That spoofing model became obsolete at The Institute of Navigation’s GNSS 2008 meeting. Dr. Todd Humphreys introduced a new receiver/spoofer that could simultaneously spoof all signals in a self-consistent way undetectable to standard RAIM techniques. Furthermore, it could use its GNSS reception capabilities and its known geometry relative to the victim to overlay the false signals initially on top of the true ones. Slowly it could capture the receiver tracking loops by raising the spoofer power to be slightly larger than that of the true signals, and then it could drag the victim receiver off to false, but believable, estimates of its position, time, or both.

    Two of the authors of this article contributed to Humphreys’ initial developments. There was no intention to help bad actors deceive GNSS user equipment (UE). Rather, our goal was to field a formidable “Red Team” as part of a “Red Team/Blue Team” (foe/friend) strategy for developing advanced “Blue Team” spoofing defenses.

    This seemed like a fun academic game until mid-December 2011, when news broke that the Iranians had captured a highly classified Central Intelligence Agency drone, a stealth Lockheed Martin RQ-170 Sentinel, purportedly by spoofing its GPS equipment. Given our work in spoofing and detection, this event caused quite a stir in our Cornell University research group, in Humphreys’ University of Texas at Austin group, and in other places. The editor of this column even got involved in our extensive e-mail correspondence. Two key questions were: Wouldn’t a classified spy drone be equipped with a Selective Availability Anti-Spoofing Module (SAASM) receiver and, therefore, not be spoofable? Isn’t it difficult to knit together a whole sequence of false GPS position fixes that will guide a drone to land in a wrong location? These issues, when coupled with apparent inconsistencies in the Iranians’ story and visible damage to the drone, led us to discount the spoofing claim.

    Developing a New Spoofing Defense

    My views about the Iranian claims changed abruptly in mid-April 2012. Todd Humphreys phoned me about an upcoming test of GPS jammers, slated for June 2012 at White Sands Missile Range (WSMR), New Mexico. The Department of Homeland Security (DHS) had already spent months arranging these tests, but Todd revealed something new in that call: He had convinced the DHS to include a spoofing test that would use his latest “Red Team” device. The goal would be to induce a small GPS-guided unmanned aerial vehicle (UAV), in this case a helicopter, to land when it was trying to hover. “Wow”, I thought. “This will be a mini-replication of what the Iranians claimed to have done to our spy drone, and I’m sure that Todd will pull it off. I want to be there and see it.” Cornell already had plans to attend to test jammer tracking and geolocation, but we would have to come a day early to see the spoofing “fun” — if we could get permission from U.S. Air Force 746th Test Squadron personnel at White Sands.

    The implications of the UAV test bounced around in my head that evening and the next morning on my seven-mile bike commute to work. During that ride, I thought of a scenario in which the Iranians might have mounted a meaconing attack against a SAASM-equipped drone. That is, they might possibly have received and re-broadcast the wide-band P(Y) code in a clever way that could have nudged the drone off course and into a relatively soft landing on Iranian territory.

    In almost the next moment, I conceived a defense against such an attack. It involves small antenna motions at a high frequency, the measurement of corresponding carrier-phase oscillations, and the evaluation of whether the motions and phase oscillations are more consistent with spoofed signals or true signals. This approach would yield a good defense for civilian and military receivers against both spoofing and meaconing attacks. The remainder of this article describes this defense and our efforts to develop and test it.

    It is one thing to conceive an idea, maybe a good idea. It is quite another thing to bring it to fruition. This idea seemed good enough and important enough to “birth” the conception. The needed follow-up efforts included two parts, one theoretical and the other experimental.

    The theoretical work involved the development of signal models, hypothesis tests, analyses, and software. It culminated in analysis and truth-model simulation results, which showed that the system could be very practical, using only centimeters of motion and a fraction of a second of data to reliably differentiate between spoofing attacks and normal GNSS operation.

    Theories and analyses can contain fundamental errors, or overlooked real-world effects can swamp the main theoretical effect. Therefore, an experimental prototype was quickly conceived, developed, and tested. It consisted of a very simple antenna-motion system, an RF data-recording device, and after-the-fact signal processing. The signal processing used Matlab to perform the spoofing detection calculations after using a C-language software radio to perform standard GPS acquisition and tracking.

    Tests of the non-spoofed case could be conducted anywhere outdoors. Our initial tests occurred on a Cornell rooftop in Ithaca, New York. Tests of the spoofed case are harder. One cannot transmit live spoofing signals except with special permission at special times and in special places, for example, at WSMR in the upcoming June tests. Fortunately, the important geometric properties of spoofed signals can be simulated by using GPS signal reception at an outdoor antenna and re-radiation in an anechoic chamber from a single antenna. Such a system was made available to us by the NASA facility at Wallops Island, Virginia, and our simulated spoofed-case testing occurred in late April of last year. All of our data were processed before mid-May, and they provided experimental confirmation of our system’s efficacy. The final results were available exactly three busy weeks after the initial conception.

    Although we were convinced about our new system, we felt that the wider GNSS community would like to see successful tests against live-signal attacks by a real spoofer. Therefore, we wanted very much to bring our system to WSMR for the June 2012 spoofing attack on the drone. We could set up our system near the drone so that it would be subject to the same malicious signals, but without the need to mount our clumsy prototype on a compact UAV helicopter. We were concerned, however, about the possibility of revealing our technology before we had been able to apply for patent protection. After some hesitation and discussions with our licensing and technology experts, we decided to bring our system to the WSMR test, but with a physical cover to keep it secret. The cover consisted of a large cardboard box, large enough to accommodate the needed antenna motions. The WSMR data were successfully collected using this method. Post-processing of the data demonstrated very reliable differentiation between spoofed and non-spoofed cases under live-signal conditions, as will be described in subsequent sections of this article.

    System Architecture and Prototype

    The components and geometry of one possible version of this system are shown in FIGURE 1. The figure shows three of the GNSS satellites whose signals would be tracked in the non-spoofed case: satellites j-1, j, and j+1. It also shows the potential location of a spoofer that could send false versions of the signals from these same satellites. The spoofer has a single transmission antenna. Satellites j-1, j, and j+1 are visible to the receiver antenna, but the spoofer could “hijack” the receiver’s tracking loops for these signals so that only the false spoofed versions of these signals would be tracked by the receiver.

    Figure 1. Spoofing detection antenna articulation system geometry relative to base mount, GNSS satellites, and potential spoofer.
    Figure 1. Spoofing detection antenna articulation system geometry relative to base mount, GNSS satellites, and potential spoofer. Photo: Mark L. Psiaki with Steven P. Powell and Brady W. O’Hanlon

    The receiver antenna mount enables its phase center to be moved with respect to the mounting base. In Figure 1, this motion system is depicted as an open kinematic chain consisting of three links with ball joints. This is just one example of how a system can be configured to allow antenna motion. Spoofing detection can work well with just one translational degree of freedom, such as a piston-like up-and-down motion that could be provided by a solenoid operating along the za articulation axis. It would be wise to cover the motion system with an optically opaque radome, if possible, to prevent a spoofer from defeating this system by sensing the high-frequency antenna motions and spoofing their effects on carrier phase.

    Suppose that the antenna articulation time history in its local body-fixed (xa, ya, za) coordinate system is ba(t). Then the received carrier phases are sensitive to the projections of this motion onto the line-of-sight (LOS) directions of the received signals. These projections are along  Eq-rj1, Eq-rj, and  Eq-r-j+1 in the non-spoofed case, with Eq-rj  being the known unit direction vector from the jth GNSS satellite to the nominal antenna location. In the spoofed case, the projections are all along Eq-rsp, regardless of which signal is being spoofed, with Eq-rsp being the unknown unit direction vector from the spoofer to the victim antenna. Thus, there will be differences between the carrier-phase responses of the different satellites in the non-spoofed case, but these differences will vanish in the spoofed case. This distinction lies at the heart of the new spoofing detection method. Given that a good GNSS receiver can easily distinguish quarter-cycle carrier-phase variations, it is expected that this system will be able to detect spoofing using antenna motions as small as 4.8 centimeters, that is, a quarter wavelength of the GPS L1 signal.

    The UE receiver and spoofing detection block in Figure 1 consists of a standard GNSS receiver, a means of inputting the antenna motion sensor data, and additional signal processing downstream of the standard GNSS receiver operations. The latter algorithms use as inputs the beat carrier-phase measurements from a standard phase-locked loop (PLL).

    It may be necessary to articulate the antenna at a frequency nearly equal to the bandwidth of the PLL (say, at 1 Hz or higher). In this case, special post-processing calculations might be required to reconstruct the high-frequency phase variations accurately before they can be used to detect spoofing. The needed post-processing uses the in-phase and quadrature accumulations of a phase discriminator to reconstruct the noisy phase differences between the true signal and the PLL numerically controlled oscillator (NCO) signal. These differences are added to the NCO phases to yield the full high-bandwidth variations.

    We implemented the first prototype of this system with one-dimensional antenna motion by mounting its patch antenna on a cantilevered beam. It is shown in FIGURE 2. Motion is initiated by pulling on the string shown in the upper left-hand part of the figure. Release of the string gives rise to decaying sinusoidal oscillations that have a frequency of about 2 Hz.

    Figure 2. Antenna articulation system for first prototype spoofing detector tests: a cantilevered beam that allows single-degree-of-freedom antenna phase-center vibration along a horizontal axis. Photo: Mark L. Psiaki with Steven P. Powell and Brady W. O’Hanlon
    Figure 2. Antenna articulation system for first prototype spoofing detector tests: a cantilevered beam that allows single-degree-of-freedom antenna phase-center vibration along a horizontal axis. Photo: Mark L. Psiaki with Steven P. Powell and Brady W. O’Hanlon

    The remainder of the prototype system consisted of a commercial-off-the-shelf RF data recording device, off-line software receiver code, and off-line spoofing detection software. The prototype system lacked an antenna motion sensor. We compensated for this omission by implementing additional signal-processing calculations. They included off-line parameter identification of the decaying sinusoidal motions coupled with estimation of the oscillations’ initial amplitude and phase for any given detection.

    This spoofing detection system is not the first to propose the use of antenna motion to uncover spoofing, and it is related to techniques that rely on multiple antennas. The present system makes three new contributions to the art of spoofing detection: First, it clearly explains why the measured carrier phases from a rapidly oscillating antenna provide a good means to detect spoofing. Second, it develops a precise spoofing detection hypothesis test for a moving-antenna system. Third, it demonstrates successful spoofing detection against live-signal attacks by a “Humphreys-class” spoofer.

    Signal Model Theory and Verification

    The spoofing detection test relies on mathematical models of the response of beat carrier phase to antenna motion. Reasonable models for the non-spoofed and spoofed cases are, respectively:

    Eq-1b  (1a)

    Eq-1a(1b)

    where Eq-0jk is the received (negative) beat carrier phase of the authentic or spoofed satellite-j signal at the kth sample time Eq-tjmk . The three-by-three direction cosines matrix A is the transformation from the reference system, in which the direction vectors Eq-rj  and Eq-rsp are defined, to the local body-axis system, in which the antenna motion ba(t) is defined. λ is the nominal carrier wavelength. The terms involving the unknown polynomial coefficients Eq-Bj0, Eq-Bj1 , and Eq-Bj2 model other low-frequency effects on carrier phase, including satellite motion, UE motion if its antenna articulation system is mounted on a vehicle, and receiver clock drift. The term Eq-nj0k is the receiver phase noise. It is assumed to be a zero-mean, Gaussian, white-noise process whose variance depends on the receiver carrier-to-noise-density ratio and the sample/accumulation frequency.

    If the motion of the antenna is one-dimensional, then ba(t) takes the form Eq-ba1, with Eq-ba being the articulation direction in body-axis coordinates and ra(t) being a known scalar antenna deflection amplitude time history. If one defines the articulation direction in reference coordinates as Eq-ra , then the carrier-phase models in Equations (1a) and (1b) become

    Eq-2a   (2a)

    Eq-2b  (2b)

    There is one important feature of these models for purposes of spoofing detection. In the non-spoofed case, the term that models the effects of antenna motion varies between GPS satellites because the Eq-rj direction vector varies with j. The spoofed case lacks variation between the satellites because the one spoofer direction Eq-rsp replaces Eq-rj for all of the spoofed satellites. This becomes clear when one compares the first terms on the right-hand sides of Eqsuations (1a) and (1b) for the 3-D motion case and on the right-hand sides of Equations (2a) and (2b) for the 1-D case.

    The carrier-phase time histories in FIGURES 3 and 4 illustrate this principle. These data were collected at WSMR using the prototype antenna motion system of Figure 2. The carrier-phase time histories have been detrended by estimating the Eq-Bj0, Eq-Bj1 , and Eq-Bj2 coefficients in Equations (2a) and (2b) and subtracting off their effects prior to plotting. In Figure 3, all eight satellite signals exhibit similar decaying sinusoid time histories, but with differing amplitudes and some of them with sign changes. This is exactly what is predicted by the 1-D non-spoofed model in Equation (2a). All seven spoofed signals in Figure 4, however, exhibit identical decaying sinusoidal oscillations because the Eq-rsp-tra term in Equation (2b) is the same for all of them.

    Figure 3. Detrended carrier-phase data from multiple satellites for a typical non-spoofed case using a 1-D antenna articulation system.
    Figure 3. Detrended carrier-phase data from multiple satellites for a typical non-spoofed case using a 1-D antenna articulation system.

     

    Figure 4. Multiple satellites’ detrended carrier-phase data for a typical spoofed case using a 1-D antenna articulation system.
    Figure 4. Multiple satellites’ detrended carrier-phase data for a typical spoofed case using a 1-D antenna articulation system.

    As an aside, an interesting feature of Figure 3 is its evidence of the workings of the prototype system. The ramping phases of all the signals from t = 0.4 seconds to t = 1.4 seconds correspond to the initial pull on the string shown in Figure 2, and the steady portion from t = 1.4 seconds to t = 2.25 seconds represents a period when the string was held fixed prior to release.

    Spoofing Detection Hypothesis Test

    A hypothesis test can precisely answer the question of which model best fits the observed data: Does carrier-phase sameness describe the data, as in Figure 4? Then the receiver is being spoofed. Alternatively, is carrier-phase differentness more reasonable, as per Figure 3? Then the signals are trustworthy.

    A hypothesis test can be developed for any batch of carrier-phase data that spans a sufficiently rich antenna motion profile ba(t) or ρa(t). The profile must include high-frequency motions that cannot be modeled by the  Eq-Bj0, Eq-Bj1 , and Eq-Bj2quadratic polynomial terms in Equations (1a)-(2b); otherwise the detection test will lose all of its power. A motion profile equal to one complete period of a sine wave has the needed richness.

    Suppose one starts with a data batch that is comprised of carrier-phase time histories for L different GNSS satellites: Eq-0jk for samples k = 1, …, Mj and for satellites j = 1,…, L. A standard hypothesis test develops two probability density functions for these data, one conditioned on the null hypothesis of no spoofing, H0, and the other conditioned on the hypothesis of spoofing, H1.  The Neyman-Pearson lemma (see Further Reading) proves that the optimal hypothesis test statistic equals the ratio of these two probability densities. Unfortunately, the required probability densities depend on additional unknown quantities. In the 1-D motion case, these unknowns include the Eq-Bj0, Eq-Bj1 , and Eq-Bj2 coefficients, the dot product Eq-rsp-tra, and the direction Eq-tra  if one assumes that the UE attitude is unknown. A true Neyman-Pearson test would hypothesize a priori distributions for these unknown quantities and integrate their dependencies out of the two joint probability distributions. Our sub-optimum test optimally estimates relevant unknowns for each hypothesis based on the carrier-phase data, and it uses these estimates in the Neyman-Pearson probability density ratio. Although sub-optimal as a hypothesis test, this approach is usually effective, and it is easier to implement than the integration approach in the present case.

    Consider the case of 1-D antenna articulation and unknown UE attitude. Maximum-likelihood calculations optimally estimate the nuisance parameters  Eq-Bj0, Eq-Bj1 , and Eq-Bj2  for j = 1, …, L for both hypotheses along with the unit vector Eq-tra for the non-spoofed hypothesis, or the scalar dot product Eq-nsix for the spoofed hypothesis. The estimation calculations for each hypothesis minimize the negative natural logarithm of the corresponding conditional probability density. Because  Eq-Bj0, Eq-Bj1 , and Eq-Bj2 enter the resulting cost functions quadratically, their optimized values can be computed as functions of the other unknowns, and they can be substituted back into the costs. This part of the calculation amounts to a batch high-pass filter of both the antenna motion and the carrier-phase response.

    The remaining optimization problems take, under the non-spoofed hypothesis, the form:

    find:      Eq-tra    (3a)

    to minimize:       Eq-Jnonsp  (3b)

    subject to:             Eq-rasmall   (3c)

    and, under the spoofed hypothesis, the form:

    find:      η    (4a)

    to minimize:   Eq-Jspn      (4b)

    subject to:     Eq-111 .   (4c)

    The coefficient Eq-rj44 is a function of the deflections Eq-Pat for k = 1, …, Mj, and the non-homogenous term Eq-zj4 is derived from the jth phase time history Eq-0jk for k = 1, …, Mj. These two quantities are calculated during the  Eq-Bj0, Eq-Bj1, Eq-Bj2 optimization. The constraint in Equation (3c) forces the estimate of the antenna articulation direction to be unit-normalized. The constraint in Eq. (4c) ensures that η is a physically reasonable dot product.

    The optimization problems in Equations (3a)-(3c) and (4a)-(4c) can be solved in closed form using techniques from the literature on constrained optimization, linear algebra, and matrix factorization. The optimal estimates of Eq-tra and η can be used to define a spoofing detection statistic that equals the natural logarithm of the Neyman-Pearson ratio:

    Eq-y-small(5)

    It is readily apparent that γ constitutes a reasonable test statistic: If the signal is being spoofed so that carrier-phase sameness is the best model, then ηopt will produce a small value of  Eq-Jsp-nbecause the spoofed-case cost function in Equation (4b) is consistent with carrier-phase sameness. The value of Eq-Jnonsp-r, however, will not be small because the plurality of  Eq-rj directions in Equation (3b) precludes the possibility that any Eq-tra estimate will yield a small non-spoofed cost. Therefore, γ will tend to be a large negative number in the event of spoofing because Eq-Jnonsp-r >> Eq-Jsp-n is likely. In the non-spoofed case, the opposite holds true: Eq-ropt  will yield a small value of Eq-Jnonsp-r, but no estimate of η will yield a small Eq-jspn2, and γ will be a large positive number because  Eq-Jnonsp-r<< Eq-Jsp-n.

    Therefore, a sensible spoofing detection test employs a detection threshold γth somewhere in the neighborhood of zero. The detection test computes a γ value based on the carrier-phase data, the antenna articulation time history, and the calculations in Equations (3a)-(5). It compares this γ to γth. If γ ≥ γth, then the test indicates that there is no spoofing. If γ < γth, then a spoofing alert is issued.

    The exact choice of γth is guided by an analysis of the probability of false alarm. A false alarm occurs if a spoofing attack is declared when there is no spoofing. The false-alarm probability is determined as a function of γth by developing a γ probability density function under the null hypothesis of no spoofing p(γ|H0). The probability of false alarm equals the integral of p(γ|H0) from γ = Eq-infinity to γ = γth. This integral relationship can be inverted to determine the γth threshold that yields a given prescribed false-alarm probability

    A complication arises because p(γ|H0) depends on unknown parameters, Eq-tra  in the case of an unknown UE attitude and 1-D antenna motion. Although sub-optimal, a reasonable way to deal with the dependence of p(γ|Eq-tra,H0) on Eq-tra is to use the worst-case Eq-tra for a given γth. The worst-case articulation direction Eq-rawc maximizes the p(γ|Eq-tra,H0) false-alarm integral. It can be calculated by solving an optimization problem. This analysis can be inverted to pick γth so that the worst-case probability of false alarm equals some prescribed value. For most actual Eq-tra values, the probability of false alarm will be lower than the prescribed worst case.

    Given γth, the final needed analysis is to determine the probability of missed detection. This analysis uses the probability density function of g under the spoofed hypothesis, p(γ|η,H1). The probability of missed detection is the integral of this function from γ = γth to γ = +Eq-infinity2. The dependence of p(γ|η,H1) on the unknown dot product η can be handled effectively, though sub-optimally, by determining the worst-case probability of false alarm. This involves an optimization calculation, which finds the worst-case dot product ηwc that maximizes the missed-detection probability integral. Again, most actual η values will yield lower probabilities of missed detection.

    Note that the above-described analyses rely on approximations of the probability density functions p(γ|Eq-tra,H0) and p(γ|η,H1). The best approximations include dominant Gaussian terms plus small chi-squared or non-central chi-squared terms. It is difficult to analyze the chi-squared terms rigorously. Their smallness, however, makes the use of Gaussian approximations reasonable.

    We have developed and evaluated several alternative formulations of this spoofing detection method. One is the case of full 3-D ba(t) antenna motion with unknown UE attitude. The full direction cosines matrix A is estimated in the modified version of the non-spoofed optimal fit calculations of Equations (3a)-(3c), and the full spoofing direction vector Eq-bsp is estimated in the modified version of Equations (4a)-(4c). A different alternative allows the 1-D motion time history ρa(t) to have an unknown amplitude-scaling factor that must be estimated. This might be appropriate for a UAV drone with a wing-tip-mounted antenna if it induced antenna motions by dithering its ailerons. In fixed-based applications, as might be used by a financial institution, a cell-phone tower, or a power-grid monitor, the attitude would be known, which would eliminate the need to estimate Eq-tra or A for the non-spoofed case.

    Test Results

    The initial tests of our concept involved generation of simulated truth-model carrier-phase data Eq-0jk using simulated Eq-Bj0, Eq-Bj1 , and Eq-Bj2 polynomial coefficients, simulated satellite LOS direction vectors Eq-rj for the non-spoofed cases, a simulated true spoofer LOS direction Eq-rsp for the spoofed cases, and simulated antenna motions parameterized by Eq-tra and ρa(t). Monte-Carlo analysis was used to generate many different batches of phase data with different random phase noise realizations in order to produce simulated histograms of the p(γ|Eq-tra, H0) and p(γ|η,H1) probability density functions  that are used in false-alarm and missed-detection analyses.

    The truth-model simulations verified that the system is practical. A representative calculation used one cycle of an 8-Hz 1-D sinusoidal antenna oscillation with a peak-to-peak amplitude of 4.76 centimeters (exactly 1/4 of the L1 wavelength). The accumulation frequency was 1 kHz so that there were Mj = 125 carrier-phase measurements per satellite per data batch. The number of satellites was L = 6, their Eq-rj LOS vectors were distributed to yield a geometrical dilution of precision of 3.5, and their carrier-to-noise-density ratios spanned the range 38.2 to 44.0 dB-Hz. The worst-case probability of a spoofing false alarm was set at 10-5 and the corresponding worst-case probability of missed detection was 1.2 ´ 10-5. Representative non-worst-case probabilities of false alarm and missed detection were, respectively, 1.7 ´ 10-9 and 1.1 ´ 10-6. These small numbers indicate that this is a very powerful test. Ten-thousand run Monte-Carlo simulations of the spoofed and non-spoofed cases verified the reasonableness of these probabilities and the reasonableness of the p(γ|Eq-tra, H0) and p(γ|η,H1) Gaussian approximations that had been used to derive them.

    The live-signal tests bore out the truth-model simulation results. The only surprise in the live-signal tests was the presence of significant multipath, which was evidenced by received carrier amplitude oscillations that correlated with the antenna oscillations and whose amplitudes and phases varied among the different received GPS signals. As a verification that these oscillations were caused by multipath, the only live-signal data set without such amplitude oscillations was the one taken in the NASA Wallops anechoic chamber, where one would not expect to find multipath. The multipath, however, seems to have negligible impact on the efficacy of this spoofing detection system.

    FIGURES 5 and 6 show the results of typical non-spoofed and spoofed cases from WSMR live-signal tests that took place on the evening of June 19–20, 2012. Each plot shows the spoofing detection statistic γ on the horizontal axis and various related probability density functions on the vertical axis. This statistic has been calculated using a modified test that includes the estimation of two additional unknowns: an antenna articulation scale factor f and a timing bias t0 for the decaying sinusoidal oscillation eq-pa. The damping ratio ζ and the undamped natural frequency wn are known from prior system identification tests.

    Figure 5. Spoofing detection statistic, threshold, and related probability density functions for a typical non-spoofed case with live data.
    Figure 5. Spoofing detection statistic, threshold, and related probability density functions for a typical non-spoofed case with live data.

     

    Figure 6. Performance of a typical spoofed case with live data: spoofing detection statistic, threshold, and related probability density functions.
    Figure 6. Performance of a typical spoofed case with live data: spoofing detection statistic, threshold, and related probability density functions.

    The vertical dashed black line in each plot shows the actual value of γ as computed from the GPS data. There are three vertical dash-dotted magenta lines that lie almost on top of each other. They show the worst-case threshold values γth as computed for the optimal and ±2σ estimates of t0: t0opt, t0opt+2σt0opt, and t0opt-2σt0opt. They have been calculated for a worst-case probability of false alarm equal to 10-6. An ad hoc method of compensating for the prototype system’s t0 uncertainty is to use the left-most vertical magenta line as the detection threshold γth. The vertical dashed black line lies very far to the right of all three vertical dash-dotted magenta lines in Figure 5, which indicates a successful determination that the signals are not being spoofed. In Figure 6, the situation is reversed. The vertical dashed black line lies well to the left of the three vertical dash-dotted magenta lines, and spoofing is correctly and convincingly detected.

    These two figures also plot various relevant probability density functions. Consistent with the consideration of three possible values of the t0 motion timing estimate, these are plotted in triplets. The three dotted cyan probability density functions represent the worst-case non-spoofed situation, and the dash-dotted red probability functions represent the corresponding worst-case spoofed situations. Obviously, there is sufficient separation between these sets of probability density functions to yield a powerful detection test, as evidenced by the ability to draw the dash-dotted magenta detection thresholds in a way that clearly separates the red and cyan distributions. Further confirmation of good detection power is provided by the low worst-case probabilities of false alarm and missed detection, the latter metric being 1.6 ´ 10-6 for the test in Figure 5 and 7 ´ 10-8 for Figure 6.

    The solid-blue distributions on the two plots correspond to the ηopt estimate and the spoofed assumption, which is somewhat meaningless for Figure 5, but meaningful for Figure 6. The dashed-green distributions are for the Eq-tra estimate under the non-spoofed assumption. The wide separations between the blue distributions and the green distributions in both figures clearly indicate that the worst-case false-alarm and missed-detection probabilities can be very conservative.

    The detection test results in Figures 5 and 6 have been generated using the last full oscillation of the respective carrier-phase data, as in Figures 3 and 4, but applied to different data sets. In Figure 3, the last full oscillation starts at t = 3.43 seconds, and it starts at t = 2.11 seconds in Figure 4. The peak-to-peak amplitude of each last full oscillation ranged from 4-6 centimeters, and their periods were shorter than 0.5 seconds. It would have been possible to perform the detections using even shorter data spans had the mechanical oscillation frequency of the cantilevered antenna been higher.

    Conclusions

    In this article, we have presented a new method to detect spoofing of GNSS signals. It exploits the effects of intentional high-frequency antenna motion on the measured beat carrier phases of multiple GNSS signals. After detrending using a high-pass filter, the beat carrier-phase variations can be matched to models of the expected effects of the motion. The non-spoofed model predicts differing effects of the antenna motion for the different satellites, but the spoofed case yields identical effects due to a geometry in which all of the false signals originate from a single spoofer transmission antenna. Precise spoofing detection hypothesis tests have been developed by comparing the two models’ ability to fit the measured data.

    This new GNSS spoofing detection technique has been evaluated using both Monte-Carlo simulation and live data. Its hypothesis test yields theoretical false-alarm probabilities and missed-detection probabilities on the order of 10-5 or lower when working with typical numbers and geometries of available GPS signals and typical patch-antenna signal strengths. The required antenna articulation deflections are modest, on the order of 4-6 centimeters peak-to-peak, and detection intervals less than 0.5 seconds can suffice.

    A set of live-signal tests at WSMR evaluated the new technique against a sophisticated receiver/spoofer, one that mimics all visible signals in a way that foils standard RAIM techniques. The new system correctly detected all of the attacks. These are the first known practical detections of live-signal attacks mounted against a civilian GNSS receiver by a dangerous new generation of spoofers.

    Future Directions

    This work represents one step in an on-going “Blue Team” effort to develop better defenses against new classes of GNSS spoofers. Planned future improvements include 1) the ability to use electronically synthesized antenna motion that eliminates the need for moving parts, 2) the re-acquisition of true signals after detection of spoofing, 3) the implementation of real-time prototypes using software radio techniques, and 4) the consideration of “Red-Team” counter-measures to this defense  and how the “Blue Team” could combat them; counter-measures such as high-frequency phase dithering of the spoofed signals or coordinated spoofing transmissions from multiple locations.

    Acknowledgments

    The authors thank the following people and organizations for their contributions to this effort:  The NASA Wallops Flight Facility provided access to their anechoic chamber. Robert Miceli, a Cornell graduate student, helped with data collection at that facility. Dr. John Merrill and the Department of Homeland Security arranged the live-signal spoofing tests. The U.S. Air Force 746th Test Squadron hosted the live-signal spoofing tests at White Sands Missile Range. Prof. Todd Humphreys and members of his University of Texas at Austin Radionavigation Laboratory provided live-signal spoofing broadcasts from their latest receiver/spoofer.

    Manufacturers

    The prototype spoofing detection data capture system used an Antcom Corp. (www.antcom.com) 2G1215A L1/L2 GPS antenna. It was connected to an Ettus Research (www.ettus.com) USRP (Universal Software Radio Peripheral) N200 that was equipped with the DBSRX2 daughterboard.

    MARK L. PSIAKI is a professor in the Sibley School of Mechanical and Aerospace Engineering at Cornell University, Ithaca, New York. He received a B.A. in physics and M.A. and Ph.D. degrees in mechanical and aerospace engineering from Princeton University, Princeton, New Jersey. His research interests are in the areas of GNSS technology, applications, and integrity, spacecraft attitude and orbit determination, and general estimation, filtering, and detection.

    STEVEN P. POWELL is a senior engineer with the GPS and Ionospheric Studies Research Group in the Department of Electrical and Computer Engineering at Cornell University. He has M.S. and B.S. degrees in electrical engineering from Cornell University. He has been involved with the design, fabrication, testing, and launch activities of many scientific experiments that have flown on high altitude balloons, sounding rockets, and small satellites. He has designed ground-based and space-based custom GPS receiving systems primarily for scientific applications.

    BRADY W. O’HANLON is a graduate student in the School of Electrical and Computer Engineering at Cornell University. He received a B.S. in electrical and computer engineering from Cornell University. His interests are in the areas of GNSS technology and applications, GNSS security, and GNSS as a tool for space weather research.

    VIDEO

    Here is a video of Cornell University’s antenna articulation system for the team’s first prototype spoofing detector tests.

    FURTHER READING

    • The Spoofing Threat and RAIM-Resistant Spoofers

    “Status of Signal Authentication Activities within the GNSS Authentication and User Protection System Simulator (GAUPSS) Project” by O. Pozzobon, C. Sarto, A. Dalla Chiara, A. Pozzobon, G. Gamba, M. Crisci, and R.T. Ioannides, in Proceedings of ION GNSS 2012, the 25th International Technical Meeting of The Institute of Navigation, Nashville, Tennessee, September 18–21, 2012, pp. 2894-2900.

    “Assessing the Spoofing Threat” by T.E. Humphreys, P.M. Kintner, Jr., M.L. Psiaki, B.M. Ledvina, and B.W. O’Hanlon in GPS World, Vol. 20, No. 1, January 2009, pp. 28-38.

    Vulnerability Assessment of the Transportation Infrastructure Relying on the Global Positioning System – Final Report. John A. Volpe National Transportation Systems Center, Cambridge, Massachusetts, August 29, 2001.

    • Moving-Antenna and Multi-Antenna Spoofing Detection

    “Robust Joint Multi-Antenna Spoofing Detection and Attitude Estimation by Direction Assisted Multiple Hypotheses RAIM” by M. Meurer, A. Konovaltsev, M. Cuntz, and C. Hattich, in Proceedings of ION GNSS 2012, the 25th International Technical Meeting of The Institute of Navigation, Nashville, Tennessee, September 18–21, 2012, pp. 3007-3016.

    “GNSS Spoofing Detection for Single Antenna Handheld Receivers” by J. Nielsen, A. Broumandan, and G. Lachapelle in Navigation, Vol. 58, No. 4, Winter 2011, pp. 335-344.

    • Alternate Spoofing Detection Strategies

    “Who’s Afraid of the Spoofer? GPS/GNSS Spoofing Detection via Automatic Gain Control (AGC)” by D.M. Akos, in Navigation, Vol. 59, No. 4, Winter 2012-2013, pp. 281-290.

    “Civilian GPS Spoofing Detection based on Dual-Receiver Correlation of Military Signals” by M.L. Psiaki, B.W. O’Hanlon, J.A. Bhatti, D.P. Shepard, and T.E. Humphreys in Proceedings of ION GNSS 2011, the 24th International Technical Meeting of The Institute of Navigation, Portland, Oregon, September 19–23, 2011, pp. 2619-2645.

    • Statistical Hypothesis Testing

    Fundamentals of Statistical Signal Processing, Volume II: Detection Theory by S. Kay, published by Prentice Hall, Upper Saddle River, New Jersey,1998.

    An Introduction to Signal Detection and Estimation by H.V. Poor, 2nd edition, published by Springer-Verlag, New York, 1994.

  • Innovation: Evil Waveforms

    Innovation: Evil Waveforms

    Generating Distorted GNSS Signals Using a Signal Simulator

    By Mathieu Raimondi, Eric Sénant, Charles Fernet, Raphaël Pons, Hanaa Al Bitar, Francisco Amarillo Fernández, and Marc Weyer

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    INTEGRITY.  It is one of the most desirable personality traits. It is the characteristic of truth and fair dealing, of honesty and sincerity. The word also can be applied to systems and actions with a meaning of soundness or being whole or undivided. This latter definition is clear when we consider that the word integrity comes from the Latin word integer, meaning untouched, intact, entire — the same origin as that for the integers in mathematics: whole numbers without a fractional or decimal component.

    Integrity is perhaps the most important requirement of any navigation system (along with accuracy, availability, and continuity). It characterizes a system’s ability to provide a timely warning when it fails to meet its stated accuracy. If it does not, we have an integrity failure and the possibility of conveying hazardously misleading information. GPS has built into it various checks and balances to ensure a fairly high level of integrity. However, GPS integrity failures have occasionally occurred.

    One of these was in 1990 when SVN19, a GPS Block II satellite operating as PRN19, suffered a hardware chain failure, which caused it to transmit an anomalous waveform. There was carrier leakage on the L1 signal spectrum. Receivers continued to acquire and process the SVN19 signals, oblivious to the fact that the signal distortion resulted in position errors of three to eight meters. Errors of this magnitude would normally go unnoticed by most users, and the significance of the failure wasn’t clear until March 1993 during some field tests of differential navigation for aided landings being conducted by the Federal Aviation Administration. The anomaly became known as the “evil waveform.”

    (I’m not sure who first came up with this moniker for the anomaly. Perhaps it was the folks at Stanford University who have worked closely with the FAA in its aircraft navigation research. The term has even made it into popular culture. The Japanese drone-metal rock band, Boris, released an album in 2005 titled Dronevil. One of the cuts on the album is “Evil Wave Form.” And if drone metal is not your cup of tea, you will find the title quite appropriate.) Other types of GPS evil waveforms are possible, and there is the potential for such waveforms to also occur in the signals of other global navigation satellite systems. It is important to fully understand the implications of these potential signal anomalies. In this month’s column, our authors discuss a set of GPS and Galileo evil-waveform experiments they have carried out with an advanced GNSS RF signal simulator. Their results will help to benchmark the effects of distorted signals and perhaps lead to improvements in GNSS signal integrity.

    “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.

    GNSS signal integrity is a high priority for safety applications. Being able to position oneself is useful only if this position is delivered with a maximum level of confidence. In 1993, a distortion on the signals of GPS satellite SVN19/PRN19, referred to as an “evil waveform,” was observed. This signal distortion induced positioning errors of several meters, hence questioning GPS signal integrity. Such events, when they occur, should be accounted for or, at least, detected.

    Since then, the observed distortions have been modeled for GPS signals, and their theoretical effects on positioning performance have been studied through simulations. More recently, the models have been extended to modernized GNSS signals, and their impact on the correlation functions and the range measurements have been studied using numerical simulations. This article shows, for the first time, the impact of such distortions on modernized GNSS signals, and more particularly on those of Galileo, through the use of RF simulations. Our multi-constellation simulator, Navys, was used for all of the simulations.

    These simulations are mainly based on two types of scenarios: a first scenario, referred to as a static scenario, where Navys is configured to generate two signals (GPS L1C/A or Galileo E1) using two separate RF channels. One of these signals is fault free and used as the reference signal, and the other is affected by either an A- or B-type evil waveform (EW) distortion (these two types are described in a latter section).

    The second type of scenario, referred to as a dynamic scenario, uses only one RF channel. The generated signal is fault free in the first part of the simulation, and affected by either an A- or B-type EW distortion in the second part of the scenario. Each part of the scenario lasts approximately one minute.

    All of the studied scenarios consider a stationary satellite position over time, hence a constant signal amplitude and propagation delay for the duration of the complete scenario.

    Navys Simulator

    The first versions of Navys were specified and funded by Centre National d’Etudes Spatiales or CNES, the French space agency. The latest evolutions were funded by the European Space Agency and Thales Alenia Space France (TAS-F). Today, Navys is a product whose specifications and ownership are controled by TAS-F. It is made up of two components: the hardware part, developed by ELTA, Toulouse, driven by a software part, developed by TAS-F.

    The Navys simulator can be configured to simulate GNSS constellations, but also propagation channel effects. The latter include relative emitter-receiver dynamics, the Sagnac effect, multipath, and troposphere and ionosphere effects. Both ground- and space-based receivers may be considered.

    GNSS Signal Generation Capabilities. Navys is a multi-constellation simulator capable of generating all existing and upcoming GNSS signals. Up to now, its GPS and Galileo signal-generation capabilities and performances have been experienced and demonstrated. The simulator, which has a generation capacity of 16 different signals at the same time over the entire L band, has already been successfully tested with GPS L1 C/A, L1C, L5, and Galileo E1 and E5 receivers.

    Evil Waveform Emulation Capabilities. In the frame of the ESA Integrity Determination Unit project, Navys has been upgraded to be capable of generating the signal distortions that were observed in 1993 on the signals from GPS satellite SVN19/PRN19. Two models have been developed from the observations of the distorted signals.

    The first one, referred to as Evil Waveform type A (EWFA), is associated with a digital distortion, which modifies the duration of the GPS C/A code chips, as shown in FIGURE 1. A lead/lag of the pseudorandom noise code chips is introduced. The +1 and –1 state durations are no longer equal, and the result is a distortion of the correlation function, inducing a bias in the pseudorange measurement equal to half the difference in the durations. This model, based on GPS L1 C/A-code observations, has been extended to modernized GNSS signals, such as those of Galileo (see Further Reading). In Navys, type A EWF generation is applied by introducing an asymmetry in the code chip durations, whether the signal is modulated by binary phase shift keying (BPSK), binary offset carrier (BOC), or composite BOC (CBOC).

    FIGURE 1. Theoretical L1 C/A code-chip waveforms in the presence of an EWFA (top) and EWFB (bottom).
    FIGURE 1. Theoretical L1 C/A code-chip waveforms in the presence of an EWFA (top) and EWFB (bottom).

    The second model, referred to as Evil Waveform type B (EWFB) is associated with an analog distortion equivalent to a second-order filter, described by a resonance frequency (fd) and a damping factor (σ), as depicted in Figure 1. This failure results in correlation function distortions different from those induced by EWFA, but which also induces a bias in the pseudorange measurement. This bias depends upon the characteristics (resonance frequency, damping factor) of the filter. In Navys, an infinite impulse response (IIR) filter is implemented to simulate the EWFB threat. The filter has six coefficients (three in the numerator and three in the denominator of its transfer function). Hence, it appears that Navys can generate third order EWF type B threats, which is one order higher that the second order threats considered by the civil aviation community. Navys is specified to generate type B EWF with less than 5 percent root-mean-square  (RMS) error between the EWF module output and the theoretical model. During validation activities, a typical value of 2 percent RMS error was measured. This EWF simulation function is totally independent of the generated GNSS signals, and can be applied to any of them, whatever its carrier frequency or modulation.

    It is important to note that such signal distortions may be generated on the fly — that is, while a scenario is running. FIGURE 2 gives an example of the application of such threat models on the Galileo E1 BOC signal using a Matlab theoretical model.

    FIGURE 2. Theoretical E1 C code-chip waveforms in the presence of an EWFA (top) and EWFB (bottom).
    FIGURE 2. Theoretical E1 C code-chip waveforms in the presence of an EWFA (top) and EWFB (bottom).

    GEMS Description

    GEMS stands for GNSS Environment Monitoring Station. It is a software-based solution developed by Thales Alenia Space aiming at assessing the quality of GNSS measurements. GEMS is composed of a signal processing module featuring error identification and characterization functions, called GEA, as well as a complete graphical user interface (see online version of this article for an example screenshot) and database management.

    The GEA module embeds the entire signal processing function suite required to build all the GNSS observables often used for signal quality monitoring (SQM). The GEA module is a set of C/C++ software routines based on innovative-graphics-processing-unit (GPU) parallel computing, allowing the processing of a large quantity of data very quickly. It can operate seamlessly on a desktop or a laptop computer while adjusting its processing capabilities to the processing power made available by the platform on which it is installed. The GEA signal-processing module is multi-channel, multi-constellation, and supports both real-time- and post-processing of GNSS samples produced by an RF front end.

    GEMS, which is compatible with many RF front ends, was used with a commercial GNSS data-acquisition system. The equipment was configured to acquire GNSS signals at the L1 frequency, with a sampling rate of 25 MHz. The digitized signals were provided in real time to GEMS using a USB link.

    From the acquired samples, GEMS performed signal acquisition and tracking, autocorrelation function (ACF) calculation and display, and C/N0 measurements. All these figures of merit were then logged in text files.

    EWF Observation

    Several experiments were carried out using both static and kinematic scenarios with GPS and Galileo signals.

    GPS L1 C/A. The first experiment was intended to validate Navys’ capability of generating state-of-the-art EWFs on GPS L1 C/A signals. It aimed at verifying that the distortion models largely characterized in the literature for the GPS L1 C/A are correctly emulated by Navys.

    EWFA, static scenario. In this scenario, Navys is configured to generate two GPS L1 C/A signals using two separate RF channels. The same PRN code was used on both channels, and a numerical frequency transposition was carried out to translate the signals to baseband. One signal was affected by a type A EWF, with a lag of 171 nanoseconds, and the other one was EWF free. Next, its amplified output was plugged into an oscilloscope. The EWFA effect is easily seen as the faulty signal falling edge occurs later than the EWF-free signal, while their rising edges are still synchronous. However, the PRN code chips are distorted from their theoretical versions as the Navys integrates a second-order high pass filter at its output, meant to avoid unwanted DC emissions. The faulty signal falling edge should occur approximately 0.17 microseconds later than the EWF-free signal falling edge.

    A spectrum analyzer was used to verify, from a spectral point of view, that the EWFA generation feature of Navys was correct. For this experiment, Navys was configured to generate a GPS L1 C/A signal at the L1 frequency, and Navys output was plugged into the spectrum analyzer input. Three different GPS L1 C/A signals are included: the spectrum of an EWF-free signal, the spectrum of a signal affected by an EWF type A, where the lag is set to 41.1 nanoseconds, and the spectrum of a signal affected by an EWF type A, where the lag is set to 171 nanoseconds. As expected, the initial BPSK(1) signal is distorted and spikes appear every 1 MHz. The spike amplitude increases with the lag.

    EWFA, dynamic scenario. In a second experiment, Navys was configured to generate only one fault-free GPS L1 C/A signal at RF. The RF output was plugged into the GEMS RF front end, and acquisition was launched. One minute later, an EWFA distortion, with a lag of 21 samples (about 171 nanoseconds at 120 times f0, where f0 equals 1.023 MHz), was activated from the Navys interface.

    FIGURE 3 shows the code-phase measurement made by GEMS. Although the scenario was static in terms of propagation delay, the code-phase measurement linearly decreases over time. This is because the Navys and GEMS clocks are independent and are drifting with respect to each other.

    FIGURE 3. GEMS code-phase measurements on GPS L1 C/A signal, EWFA dynamic scenario.
    FIGURE 3. GEMS code-phase measurements on GPS L1 C/A signal, EWFA dynamic scenario.

    The second observation is that the introduction of the EWFA induced, as expected, a bias in the measurement. If one removes the clock drifts, the bias is estimated to be 0.085 chips (approximately 25 meters). According to theory, an EWFA induces a bias equal to half the lead or lag value. A value of 171 nanoseconds is equivalent to about 50 meters.

    FIGURE 4 represents the ACFs computed by GEMS during the scenario. It appears that when the EWFA is enabled, the autocorrelation function is flattened at its top, which is typical of EWFA distortions. Eventually, FIGURE 5 showed that the EWFA also results in a decrease of the measured C/N0, which is completely coherent with the flattened correlation function obtained when EWFA is on.

    FIGURE 4. GEMS ACF computation on GPS L1 C/A signal, EWFA dynamic scenario.
    FIGURE 4. GEMS ACF computation on GPS L1 C/A signal, EWFA dynamic scenario.
    FIGURE 5. GEMS C/N0 measurement on GPS L1 C/A signal, EWFA dynamic scenario.
    FIGURE 5. GEMS C/N0 measurement on GPS L1 C/A signal, EWFA dynamic scenario.

    Additional analysis has been conducted with Matlab to confirm Navys’ capacity. A GPS signal acquisition and tracking routine was modified to perform coherent accumulation of GPS signals. This operation is meant to extract the signal out of the noise, and to enable observation of the code chips. After Doppler and code-phase estimation, the signal is post-processed and 1,000 signal periods are accumulated. The result, shown in FIGURE 6, confronts fault-free (blue) and EWFA-affected (red) code chips. Again, the lag of 171 nanoseconds is clearly observed. The analysis concludes with FIGURE 7, which shows the fault-free (blue) and the faulty (red) signal spectra. Again, the presence of spikes in the faulty spectrum is characteristic of EWFA.

    FIGURE 6. Fault-free vs. EWFA GPS L1 C/A signal.
    FIGURE 6. Fault-free vs. EWFA GPS L1 C/A signal.
    FIGURE 7. Fault-free vs. EWFA GPS L1 C/A signal power spectrum density.
    FIGURE 7. Fault-free vs. EWFA GPS L1 C/A signal power spectrum density.

    EWFB, static scenario. The same experiments as for EWFA were conducted for EWFB. Fault-free and faulty (EWFB with a resonance frequency of 8 MHz and a damping factor of 7 MHz) signals were simultaneously generated and observed using an oscilloscope and a spectrum analyzer. The baseband temporal signal undergoes the same default as that of the EWFA because of the Navys high-pass filter. However, the oscillations induced by the EWFB are clearly observed.

    The spectrum distortion induced by the EWFB at the L1 frequency is amplified around 8 MHz, which is consistent with the applied failure.

    EWFB, dynamic scenario. Navys was then configured to generate one fault-free GPS L1 C/A signal at RF. The RF output was plugged into the GEMS RF front end, and acquisition was launched. One minute later, an EWFB distortion with a resonance frequency of 4 MHz and a damping factor of 2 MHz was applied. As for the EWFA experiments, the GEMS measurements were analyzed to verify the correct application of the failure. The code-phase measurements, illustrated in FIGURE 8, show again that the Navys and GEMS clocks are drifting with respect to each other. Moreover, it is clear that the application of the EWFB induced a bias of about 5.2 meters on the code-phase measurement. One should notice that this bias depends upon the chip spacing used for tracking. Matlab simulations were run considering the same chip spacing as for GEMS, and similar tracking biases were observed.

    FIGURE 8. GEMS code-phase measurements on GPS L1 C/A signal, EWFB dynamic scenario.
    FIGURE 8. GEMS code-phase measurements on GPS L1 C/A signal, EWFB dynamic scenario.

    FIGURE 9 shows the ACF produced by GEMS. During the first minute, the ACF looks like a filtered L1 C/A correlation function. Afterward, undulations distort the correlation peak.

    FIGURE 9. GEMS ACF computation on GPS L1 C/A signal, EWFB dynamic scenario.
    FIGURE 9. GEMS ACF computation on GPS L1 C/A signal, EWFB dynamic scenario.

    Again, additional analysis has been conducted with Matlab, using a GPS signal acquisition and tracking routine. A 40-second accumulation enabled comparison of the faulty and fault-free code chips. FIGURE 10 shows that the faulty code chips are affected by undulations with a period of 244 nanoseconds, which is consistent with the 4 MHz resonance frequency. This temporal signal was then used to compute the spectrum, as shown in FIGURE 11. The figure shows well that the faulty L1 C/A spectrum (red) secondary lobes are raised up around the EWFB resonance frequency, compared to the fault-free L1 C/A spectrum (blue).

    FIGURE 10. Fault-free vs EWFB GPS L1 C/A signal.
    FIGURE 10. Fault-free vs EWFB GPS L1 C/A signal.

     

    FIGURE 11. Fault-free vs EWFB GPS L1 C/A signal power spectrum density.
    FIGURE 11. Fault-free vs EWFB GPS L1 C/A signal power spectrum density.

    Galileo E1 CBOC(6, 1, 1/11). In the second part of the experiments, Navys was configured to generate the Galileo E1 Open Service (OS) signal instead of the GPS L1 C/A signal. The goal was to assess the impact of EWs on such a modernized signal.

    EWFA, static scenario. First, the same Galileo E1 BC signal was generated using two different Navys channels. One was affected by EWFA, and the other was not. The spectra of the obtained signals were observed using a spectrum analyzer. The spectrum of the signal produced by the fault-free channel shows the BOC(1,1) main lobes, around 1 MHz, and the weaker BOC(6,1) main lobes, around 6 MHz. The power spectrum of the signal produced by the EWFA channel has a lag of 5 samples at 120 times f0 (40 nanoseconds). Again, spikes appear at intervals of f0, which is consistent with theory. The signal produced by the same channel, but with a lag set to 21 samples (171.07 nanoseconds) was also seen. Such a lag should not be experienced on CBOC(6,1,1/11) signals as this lag is longer than the BOC(6,1) subcarrier half period (81 nanoseconds). This explains the fact that the BOC(6,1) lobes do not appear anymore in the spectrum.

    EWFB, static scenario. The same experiments as for EWFA were conducted for EWFB. Fault-free and faulty (EWFB with a resonance frequency of 8 MHz and a damping factor of 7 MHz) signals were simultaneously generated and observed using the spectrum analyzer. The spectrum distortion induced by the EWFB at the E1 frequency was evident. The spectrum is amplified around 8 MHz, which is consistent with the applied failure.

    EWFA, dynamic scenario. The same scenario as for the GPS L1 C/A signal was run with the Galileo E1 signal: first, for a period of one minute, a fault-free signal was generated, followed by a period of one minute with the faulty signal. GEMS was switched on and acquired and tracked the two-minute-long signal. Its code-phase measurements, shown in FIGURE 12, reveal a tracking bias of 6.2 meters. This is consistent with theory, where the set lag is equal to 40 nanoseconds (12.0 meters). GEMS-produced ACFs show the distortion of the correlation function in FIGURE 13. The distortion is hard to observe because the applied lag is small.

    FIGURE 12. GEMS code-phase measurements on Galileo E1 pilot signal, EWFA dynamic scenario.
    FIGURE 12. GEMS code-phase measurements on Galileo E1 pilot signal, EWFA dynamic scenario.
    FIGURE 13. GEMS ACF computation on Galileo E1 pilot signal, EWFA dynamic scenario.
    FIGURE 13. GEMS ACF computation on Galileo E1 pilot signal, EWFA dynamic scenario.

    A modified version of the GPS signal acquisition and tracking Matlab routine was used to acquire and track the Galileo signal. It was configured to accumulate 50 seconds of fault-free signal and 50 seconds of a faulty signal. This operation enables seeing the signal in the time domain, as in FIGURE 14. Accordingly, the following observations can be made:

    • The E1 BC CBOC(6,1,1/11) signal is easily recognized from the blue curve (fault-free signal).
    • The EWFA effect is also seen on the BOC(1,1) and BOC(6,1) parts. The observed lag is consistent with the scenario (five samples at 120 times f0 ≈ 0.04 chips).
    • The lower part of the BOC(6,1) seems absent from the red signal. Indeed, the application of the distortion divided the duration of these lower parts by a factor of two, and so multiplied their Fourier representation by two. Therefore, the corresponding main lobes should be located around 12 MHz. At the receiver level, the digitization is being performed at 25 MHz; this signal is close to the Shannon frequency and is therefore filtered by the anti-aliasing filter.
    FIGURE 14. Fault-free vs EWFA Galileo E1 signal.
    FIGURE 14. Fault-free vs EWFA Galileo E1 signal.

    The power spectrum densities of the obtained signals were then computed. FIGURE 15 shows the CBOC(6,1,1/11) fault-free signal in blue and the faulty CBOC(6,1,1/11) signal, with the expected spikes separated by 1.023 MHz.

    FIGURE 15. Fault-free vs. EWFA Galileo E1 signal power spectrum density.
    FIGURE 15. Fault-free vs. EWFA Galileo E1 signal power spectrum density.

    It is noteworthy that the EWFA has been applied to the entire E1 OS signal, which is B (data component) minus C (pilot component). EWFA could also affect exclusively the data or the pilot channel. Although such an experiment was not conducted during our research, Navys is capable of generating EWFA on the data component, the pilot component, or both.

    EWFB, dynamic scenario. In this scenario, after one minute of a fault-free signal, an EWFB, with a resonance frequency of 4 MHz and a damping factor of 2 MHz, was activated. The GEMS code-phase measurements presented in FIGURE 16 show that the EWFB induces a tracking bias of 2.8 meters. As for GPS L1 C/A signals, it is to be noticed that the bias induced by EWFB depends upon the receiver characteristics and more particularly the chip spacing used for tracking.

    FIGURE 16. GEMS code-phase measurements on Galileo E1 pilot signal, EWFB dynamic scenario.
    FIGURE 16. GEMS code-phase measurements on Galileo E1 pilot signal, EWFB dynamic scenario.

    The GEMS produced ACFs are represented in FIGURE 17. After one minute, the characteristic EWFB undulations appear on the ACF.

    FIGURE 17. GEMS ACF computation on Galileo E1 pilot signal, EWFB dynamic scenario.
    FIGURE 17. GEMS ACF computation on Galileo E1 pilot signal, EWFB dynamic scenario.

    In this case, signal accumulation was also performed to observe the impact of EWFB on Galileo E1 BC signals. The corresponding representation in the time domain is provided in FIGURE 18, while the Fourier domain representation is provided in FIGURE 19. From both points of view, the application of EWFB is compliant with theoretical models. The undulations observed on the signal are coherent with the resonance frequency (0.25 MHz ≈ 0.25 chips), and the spectrum also shows the undulations (the red spectrum is raised up around 4 MHz).

    FIGURE 18. Fault-free vs EWFB Galileo E1 signal.
    FIGURE 18. Fault-free vs EWFB Galileo E1 signal.
    FIGURE 19. Fault-free vs. EWFB Galileo E1 signal power spectrum density.
    FIGURE 19. Fault-free vs. EWFB Galileo E1 signal power spectrum density.

    Conclusion

    Navys is a multi-constellation GNSS simulator, which allows the generation of all modeled EWF (types A and B) on both GPS and Galileo signals. Indeed, the Navys design makes the EWF application independent of the signal modulation and carrier frequency.

    The International Civil Aviation Organization model has been adapted to Galileo signals, and the correct application of the failure modes has been verified through RF simulations. The theoretical effects of EWF types A and B on waveforms, spectra, autocorrelation functions and code-phase measurements have been confirmed through these simulations.

    For a given lag value, the tracking biases induced by type A EWF distortions are equal on GPS and Galileo signals, which is consistent with theory.

    Eventually, for a given resonance frequency-damping factor combination, the type B EWF distortions induce a tracking bias of about 5.2 meters on GPS L1 C/A measurements and only 2.8 meters on Galileo E1 C measurements. This is mainly due to the fact that the correlator tracking spacing was reduced for Galileo signal tracking (± 0.15 chips instead of ± 0.5 chips). (Additional figures showing oscilloscope and spectrum analyzer screenshots of experimental results are available in the online version of this article.)

    Acknowledgments

    This article is based on the paper “Generating Evil WaveForms on Galileo Signals using NAVYS” presented at the 6th ESA Workshop on Satellite Navigation Technologies and the European Workshop on GNSS Signals and Signal Processing, Navitec 2012, held in Noordwijk, The Netherlands, December 5–7, 2012.

    Manufacturers

    In addition to the Navys simulator, the experiments used a Saphyrion sagl GDAS-1 GNSS data acquisition system, a Rohde & Schwarz GmbH & Co. KG RTO1004 digital oscilloscope, and a Rohde & Schwarz FSW26 signal and spectrum analyzer.

    MATHIEU RAIMONDI is currently a GNSS systems engineer at Thales Alenia Space France (TAS-F). He received a Ph.D. in signal processing from the University of Toulouse (France) in 2008.

    ERIC SENANT is a senior navigation engineer at TAS-F. He graduated from the Ecole Nationale d’Aviation Civile (ENAC), Toulouse, in 1997.

    CHARLES FERNET is the technical manager of GNSS system studies in the transmission, payload and receiver group of the navigation engineering department of the TAS-F navigation business unit. He graduated from ENAC in 2000.

    RAPHAEL PONS is currently a GNSS systems engineering consultant at Thales Services in France. He graduated as an electronics engineer in 2012 from ENAC.

    HANAA AL BITAR is currently a GNSS systems engineer at TAS-F. She graduated as a telecommunications and networks engineer from the Lebanese Engineering School of Beirut in 2002 and received her Ph.D. in radionavigation in 2007 from ENAC, in the field of GNSS receivers.

    FRANCISCO AMARILLO FERNANDEZ received his Master’s degree in telecommunication engineering from the Polytechnic University of Madrid. In 2001, he joined the European Space Agency’s technical directorate, and since then he has worked for the Galileo program and leads numerous research activities in the field of GNSS evolution.

    MARC WEYER is currently working as the product manager in ELTA, Toulouse, for the GNSS simulator and recorder.

     

    Additional Images

    GEMS graphical interface.
    GEMS graphical interface.
    Observation of EWF type A on GPS L1 C/A signal with an oscilloscope.
    Observation of EWF type A on GPS L1 C/A signal with an oscilloscope.
    Impact of EWF A on GPS L1 C/A signal spectrum for 0 (green), 41 (black), and 171 (blue) nanosecond lag.
    Impact of EWF A on GPS L1 C/A signal spectrum for 0 (green), 41 (black), and 171 (blue) nanosecond lag.
    Observation of EWF type A on GPS L1 C/A signal with an oscilloscope.
    Observation of EWF type A on GPS L1 C/A signal with an oscilloscope.
    Impact of EWF B on GPS L1 C/A signal spectrum for Fd = 8 MHz and σ = 7 MHz.
    Impact of EWF B on GPS L1 C/A signal spectrum for fd = 8 MHz and σ = 7 MHz.
    Impact of EWF A on Galileo E1 BC signal spectrum for 0 (green), 40 (black), and 171 (blue) nanosecond lag.
    Impact of EWF A on Galileo E1 BC signal spectrum for 0 (green), 40 (black), and 171 (blue) nanosecond lag.
    Navys hardware equipment – Blackline edition.
    Navys hardware equipment – Blackline edition.

    Further Reading

    • Authors’ Conference Paper

    “Generating Evil WaveForms on Galileo Signals using NAVYS” by M. Raimondi, E. Sénant, C. Fernet, R. Pons, and H. AlBitar in Proceedings of Navitec 2012, the 6th ESA Workshop on Satellite Navigation Technologies and the European Workshop on GNSS Signals and Signal Processing, Noordwijk, The Netherlands, December 5–7, 2012, 8 pp., doi: 10.1109/NAVITEC.2012.6423071.

    • Threat Models

    “A Novel Evil Waveforms Threat Model for New Generation GNSS Signals: Theoretical Analysis and Performance” by D. Fontanella, M. Paonni, and B. Eissfeller in Proceedings of Navitec 2010, the 5th ESA Workshop on Satellite Navigation Technologies, Noordwijk, The Netherlands, December 8–10, 2010, 8 pp., doi: 10.1109/NAVITEC.2010.5708037.

    “Estimation of ICAO Threat Model Parameters For Operational GPS Satellites” by A.M. Mitelman, D.M. Akos, S.P. Pullen, and P.K. Enge in Proceedings of ION GPS 2002, the 15th International Technical Meeting of the Satellite Division of The Institute of Navigation, Portland, Oregon, September 24–27, 2002, pp. 12–19.

    • GNSS Signal Deformations

    “Effects of Signal Deformations on Modernized GNSS Signals” by R.E. Phelts and D.M. Akos in Journal of Global Positioning Systems, Vol. 5, No. 1–2, 2006, 9 pp.

    “Robust Signal Quality Monitoring and Detection of Evil Waveforms” by R.E. Phelts, D.M. Akos, and P. Enge in Proceedings of ION GPS-2000, the 13th International Technical Meeting of the Satellite Division of The Institute of Navigation, Salt Lake City, Utah, September 19–22, 2000, pp. 1180–1190.

    “A Co-operative Anomaly Resolution on PRN-19” by C. Edgar, F. Czopek, and B. Barker in Proceedings of ION GPS-99, the 12th International Technical Meeting of the Satellite Division of The Institute of Navigation, Nashville, Tennessee, September 14–17, 1999, pp. 2269–2271.

    • GPS Satellite Anomalies and Civil Signal Monitoring

    An Overview of Civil GPS Monitoring by J.W. Lavrakas, a presentation to the Southern California Section of The Institute of Navigation at The Aerospace Corporation, El Segundo, California, March 31, 2005.

    • Navys Signal Simulator

    “A New GNSS Multi Constellation Simulator: NAVYS” by G. Artaud, A. de Latour, J. Dantepal, L. Ries, N. Maury, J.-C. Denis, E. Senant, and T. Bany in  Proceedings of ION GPS 2010, the 23rd International Technical Meeting of the Satellite Division of The Institute of Navigation, Portland, Oregon, September 21–24, 2010, pp. 845–857.

    “Design, Architecture and Validation of a New GNSS Multi Constellation Simulator : NAVYS” by G. Artaud, A. de Latour, J. Dantepal, L. Ries, J.-L. Issler, J. Tournay, O. Fudulea, J.-M. Aymes, N. Maury, J.-P. Julien , V. Dominguez, E. Senant, and M. Raimondi in  Proceedings of ION GPS 2009, the 22nd International Technical Meeting of the Satellite Division of The Institute of Navigation, Savannah, Georgia, September 22–25, 2009, pp. 2934–2941.

  • Innovation: Interfacing Clearly

    Innovation: Interfacing Clearly

    A New Approach to the Design and Development of Global Navigation Satellite Systems

    By Daniele Gianni, Marco Lisi, Pierluigi De Simone, Andrea D’Ambrogio, and Michele Luglio

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    MY FIRST DEGREE is in applied physics from the University of Waterloo. Founded in 1957, Waterloo was one of the first universities to introduce co-operative education. Co-operative education (or “co-op” as it is commonly known) is a program that uses both classroom study and temporary jobs to provide students with practical experience. Applied Physics was a co-op program and I worked in both industry and research environments including stints at Philips Electronics and the Atomic Energy of Canada Limited’s Chalk River Laboratories.

    Both on campus and on the job, I met fellow co-op students from a variety of disciplines including mathematics (computer science) and various branches of engineering. One of those was systems design engineering or systems engineering for short. At that time, I really didn’t know much about systems engineering except that it was an all-encompassing branch of engineering and the most challenging of all of the engineering programs at Waterloo — at least according to the students in the program.

    Systems engineering is an interdisciplinary field of engineering focusing on the design and management of complex engineering projects. According to the International Council on Systems Engineering, systems engineers establish processes “to ensure that the customer and stakeholder’s needs are satisfied in a high quality, trustworthy, cost efficient and schedule compliant manner throughout a system’s entire life cycle. This process is usually comprised of the following seven tasks: State the problem, Investigate alternatives, Model the system, Integrate, Launch the system, Assess performance, and Re-evaluate [or, SIMILAR, for short].”

    Central to the systems engineering process and the end-product design is the generation of models. Many types of system models are used, including physical analogs, analytical equations, state machines, block diagrams, functional flow diagrams, object-oriented models, computer simulations, and even mental models. (If you want to learn a bit about mental and other kinds of models, including how to fix radios by thinking, you could do no better than to look at some of Richard Feynman’s writings including the eminently readable “Surely You’re Joking, Mr. Feynman!”: Adventures of a Curious Character.)

    As aids to the modeling process, systems engineers have developed specialized modeling languages including the Unified Modeling Language (UML) and the Systems Modeling Language (SysML). These are graphical-based languages that can be used to express information or knowledge about systems in a structure that is defined by a consistent set of rules. Both UML and SysML are widely used in systems engineering. However, both are limited when it comes to representing the signal-in-space (SIS) interfaces for global navigation satellite systems.

    In this month’s column, a team of authors affiliated with the Galileo project discusses the Interface Communication Modeling Language, an extension of UML that allows engineers to clearly represent SIS interfaces, critical for the design of GNSS receivers.

    “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, see the “Contributing Editors” section on page 4.

    In this article, we present the results of ongoing research on the use of a modeling language, namely Interface Communication Modeling Language (ICML), for signal-in-space (SIS) interface specification of global navigation satellite systems (GNSS). Specifications based on modeling languages (also known as model-based specifications) have proven to offer a wide range of benefits to systems engineering activities, for supporting system interoperability, reducing design risk, automating software development, and so on. We argue that similar benefits can be obtained for satellite navigation systems and receivers, if a model-based approach is used for defining and expressing the SIS interface specification. In particular, we outline how a model-based SIS interface specification can support the identification of solutions to two key issues: GNSS interoperability and the design of GNSS receivers, particularly Galileo receivers. Both issues are becoming increasingly central to the Galileo program since it entered the In-Orbit-Validation (IOV) phase and is steadily approaching the 2014 milestone, when the first early services — the Open Service (OS) and the Search and Rescue Service — will be provided to users.

    GNSS interoperability concerns the integration of different GNSS with the purpose of being used together, along with regional positioning systems, to provide a seamless navigation capability and improved services in terms of availability, continuity, accuracy, and integrity, for example. GNSS interoperability should be addressed in terms of intra-GNSS interoperability and GNSS-receiver interoperability. The intra-GNSS interoperability concerns the data exchanged among the GNSS, including coordination to guarantee data coherence and consistency over time. For example, GNSS may need to share terrestrial reference frames and constantly synchronize their global time references. On the other hand, GNSS-receiver interoperability concerns the capability of the receiver to use independent GNSS signals for the computation of positions globally. This capability implicitly requires that the receiver computations are decoupled from the SIS interface of any particular GNSS. A key condition to achieve this decoupling is that the SIS interface specification is available in a consistent, unambiguous, and possibly standard format, which can support engineers to more effectively design interoperable receivers. A model-based SIS interface specification would considerably facilitate this as it enables designers to use the processing capabilities of a computer system for the verification of the specification consistency and completeness, for example. Moreover, a model-based SIS interface specification would ease the visual and electronic inspection of the data messages, therefore facilitating the automatic identification of different data representations for the same orbital and temporal parameters.

    The design of GNSS receivers, and particularly those for Galileo, is increasingly of interest, and a model-based SIS interface specification can similarly support the definition of future solutions. For Galileo, specifically, the receiver design is critical to support the marketing strategies that are promoting the use of Galileo services. Key issues underlying any marketing strategy concern the Galileo receiver market appealing from a cost-to-performance ratio point of view. As Galileo receivers may require new design and adaptation of existing software (SW) or hardware (HW), as well as new production chains, higher costs — in particular non-recurring ones — are likely to occur for the production of the Galileo receivers with respect to the well-established GPS receivers. As a consequence, limitations may be experienced in market penetration and in the growth velocity of Galileo receivers’ share of the receiver market. In turn, this may hinder the estimated economic return for the Galileo project.

    Preventing and counteracting this possibility is therefore a critical issue if we aim to achieve the widest possible success of the Galileo project. Market barriers inherently originate from the following needs:

    • Designing new SW and HW solutions for Galileo receivers;
    • Reusing existing SW and HW for GPS receivers;
    • Converting existing production chains to the new Galileo-specific SW and HW solutions.

    GNSS receivers often use established mathematical models that can determine the receiver position from a fundamental set of parameters, such as satellite orbit and system time. As a consequence, the intrinsic representation of the parameter set is a major factor in the adaptation of the existing design and implementation of SW and HW solutions.

    To reduce the impact of the above needs, a model-based SIS interface specification may play a pivotal role in several ways, such as:

    • reducing ambiguities in the Galileo SIS interface specification;
    • enhancing the communication with the involved stakeholders;
    • linking the SIS interface specification to the design schemas of GNSS receivers — particularly Galileo ones — for tracing the interface elements onto the receiver functional and physical schema, thereby supporting the reuse and adaptation of existing HW and SW solutions;
    • supporting the model-based design of security solutions for blocking, jamming, and spoofing.

    Galileo Project

    In October 2012, the final two IOV satellites were launched into orbit, completing the designed configuration for the Galileo IOV phase — the initial stage of the Galileo constellation development. In this phase, preliminary validation tests will be performed and the initial navigation message will be broadcast to the Galileo ground segment for further validation. Shortly after the conclusion of this phase, a series of launches will take place to gradually deploy the remaining 26 satellites that will form the Galileo Full Operational Capability (FOC) configuration. Currently, the Galileo Early Open Service (EOS) is expected to be available by the end of 2014. The EOS will provide ranging capabilities and will enable receiver manufacturers to begin to design and test their technological solutions for Galileo receivers and Galileo overlay services, such as search and rescue.

    In the meantime, the European GNSS Agency has been established and assigned the governance of the Galileo sub-systems, including activities such as:

    • initiating and monitoring the implementation of security procedures and performing system security audits;
    • system infrastructure management, maintenance, improvement, certification, and standardization, and service provision;
    • development and deployment of activities for the evolution and future generations of the systems, including procurement activities;
    • contributing to the exploitation of the systems, including the marketing and promotion of applications and services, including market analysis.

    With the now-rapid development of the Galileo project, it becomes increasingly important to support the receiver manufacturers in the design and implementation of global navigation solutions based on the Galileo services. This is necessary to guarantee the widespread use of the Galileo services, particularly in an increasingly crowded GNSS panorama.

    Model-Based Systems Engineering

    Model-based systems engineering (MBSE) is predicated on the notion that a system is developed by use of a set of system models that evolve throughout the development lifecycle, from abstract models at the early stages down to the operational system. A visual presentation is provided by FIGURE 1, which shows the roles of MBSE approaches within the systems engineering V-shaped process. Specifically, the MBSE approaches enable the designer to effectively trace the requirements and design alternatives on the descending branch of the “V.” For the same characteristics, MBSE facilitates the verification through a model repository that interconnects not only the design products, but also the stakeholders involved in the entire process. In addition, MBSE approaches support the automatic generation of the documentation and of other artifacts, particularly software. All of these capabilities eventually enable the validation of the implementation activities on the ascending branch of the V-process. Also, in this case, MBSE and the model repository play a major role in connecting design to implementation, and users and designers to developers.

    FIGURE 1. Systems engineering V-process supported by an model-based systems engineering with model repository (courtesy of the INCOSE Survey).
    FIGURE 1. Systems engineering V-process supported by an model-based systems engineering with model repository (courtesy of the INCOSE Survey).

    Main Concepts. MBSE approaches are gaining increasing popularity with the widespread adoption of standard modeling languages, such as Unified Modeling Language (UML) and Systems Modeling Language (SysML).

    UML is a formally defined general-purpose graphical language and is mainly used in the context of software systems development. It has been developed and is being managed by the Object Management Group and is the core standard of the Model Driven Architecture (MDA) effort, which provides a set of standards to shift from code-centric to model-driven software development. By use of an MDA-based approach, a software system is built by specifying and executing a set of automated model transformations.

    SysML is defined as an extension of UML and provides a general-purpose modeling language for systems engineering applications (See FIGURE 2). SysML supports MBSE approaches in the development of complex systems that include hardware, software, information, processes, personnel, and facilities.

    FIGURE 2. UML-SysML relationships. (UML 2 is the second generation version of UML introduced in 2005.)
    FIGURE 2. UML-SysML relationships. (UML 2 is the second generation version of UML introduced in 2005.)

    Advantages. With respect to the conventional document-based approaches, MBSE approaches present the following advantages:

    • Conformance to standard specifications and availability of development tools;
    • Increased level of automation due to the formal specification and execution of model transformations that take as input a model at a given level of abstraction and yield as output a refined model at a lower level of abstraction;
    • Better understanding of the system in its operational context;
    • Support for simulation activities at different levels of detail and at different development stages, from concept exploration to dynamic system optimization;
    • Support for the coherent extension of standard modeling languages to adapt them to a specific target or domain.

    These capabilities have motivated and have been sustaining an increasing trend of moving from document-centric to model-centric systems engineering.

    ICML Language

    UML and SysML are widely used languages for MBSE. A plethora of tools and technologies are available to compose models, transform models into documents, derive software products from models, and share and reuse models by means of repositories. However, neither of these languages offers capabilities for the representation of SIS interfaces, which are the critical interfaces for the design of Galileo receivers. For this reason, we have introduced ICML: a modeling language that can enable a full MBSE approach for the design of Galileo receivers. Moreover, ICML extends UML, and therefore it can integrate with system specifications based on compliant technologies as well as be used within standard tools.

    Layout of Interface Specification. The typical layout of ICML-based interface specification is shown in FIGURE 3. The specification covers the definition of both the message structure and conversion processes. The message structure consists of five abstraction levels, and describes how the data is structured within the message. The conversion processes describe how the data values are transformed between adjacent levels of the message specification.

    FIGURE 3. Layout of ICML-based interface specifications.
    FIGURE 3. Layout of ICML-based interface specifications.

    The message structure is defined at five levels: Data Definition, (Logical) Binary Coding, Logical Binary Structure, Physical Binary Coding, and Physical Signal, each covering specific aspects of the SIS interface specification.

    For example, the Data Definition level covers the specification of the logical data structure, which includes the data items composing the message information. A data item is either of application or control type. An application data item represents a domain-specific concept that conveys the information expected by the message recipient. On the other hand, a control data item represents a domain-independent concept that can support the correctness and integrity verification of the associated application data items. A data item can also be associated with semantic and pragmatic definitions. The former specifies the meaning of the data item and the latter specifies the contextual interpretation for the semantic definition.

    Analogously, the Binary Coding level covers the specification of the binary coding for each of the data items defined at the above level. For a data item, the binary coding is represented as a binary sequence and it includes at least a sequence identifier, the semantic definition, and the pragmatic definitions. Similarly to the above level, the semantic and pragmatic definitions enrich the interface specification, conveying an accurate representation of the binary coding.

    The conversion processes describe the activities to be performed for deriving message values between adjacent levels of the above structural specification. As shown in Figure 3, eight processes should be defined to specify all the conversions between adjacent levels. For example, the DataDefinition2BinaryCoding process defines the activities to be performed for the derivation of the logical binary sequences representing data values. Similarly, the LogicalBinary2PhysicalBinary process defines the activities for the implementation of convolution or encryption algorithms on the logical binary sequence. However, these processes do not always need to be explicitly defined. In particular, if the implementation of a process is trivial or standard, a textual note referring to an external document may suffice for the specification purposes.

    The first prototypal version of ICML has been implemented and can be used within the open source TopCased tool. The prototypal version is available under the GNU General Public License (GPL) v3.0 from the ICML project website. We applied the profile and developed the example ICML-based specification given below.

    Galileo-Like Specification. An ICML-based specification of a Galileo-like OS interface, concerning only the above-defined level 3, would display as shown in FIGURE 4. This figure specifically details a part of a reduced F/NAV (the freely accessible navigation message provided by the E5a signal for the Galileo OS) structure consisting of one data frame made up of two F/NAV subframes.

    FIGURE 4. Example of ICML-based specification of an F/NAV-like message structure at the Logical Binary Coding level.
    FIGURE 4. Example of ICML-based specification of an F/NAV-like message structure at the Logical Binary Coding level.

    Benefits. ICML can bring the above-mentioned MBSE benefits to support GNSS interoperability and to GNSS and Galileo receiver design. For example, ICML can:

    • provide a reference guideline for structuring the specification data and thus facilitating the communication between the Galileo SIS designers and the receiver producers;
    • ease visual inspection of the specification for verification purposes and for the identification of data incompatibilities of two GNSS systems;
    • convey the data semantics as well as the measurement units, to guarantee that the binary data from different GNSS are correctly decoded and interpreted;
    • support syntactical model validation using existing tools;
    • provide support for future advance exploitation by means of a machine-readable data format.

    In particular, the availability of a machine-readable format is also the basis for advanced use cases that can exploit the capabilities of modern computer technologies.

    Advanced Future Use Cases. In line with the above-mentioned MBSE model exploitations, we foresee a number of possible exploitation cases:

    • Automatic generation of the interface specification documents;
    • Collaborative development of the interface specification;
    • Automatic completeness and consistency checking of the interface specification;
    • Integration of SIS specifications with model-driven simulation engineering approaches for the simulation of single- and multi-GNSS receivers;
    • Integration of SIS specifications with receiver design models in SysML, for requirements traceability and reuse of existing GNSS solutions.

    The automatic generation of interface specification documents can be an important capability during the lifecycle of a specification. For example, the specification may be updated several times during the interface design, and the textual documentation may need to be produced several times. Using a model-based approach, it is possible to automate the error-prone activities related to the document writing as well as other important functions such as specification versioning.

    Complex system specifications are often the product of collaborating teams, which may occasionally be geographically dispersed. Using a model-based approach, the interface specification can be stored within a version control system that can be concurrently accessed by team members.

    Completeness and consistency checking is also a manual activity, which demands a high degree of mental attention, and it is consequently highly error prone. Once the specification is available in a machine-readable format, the checking can be easily automated by specifying the verification rules that the interface model must satisfy.

    Existing technologies support the simulation of single- and multi-GNSS receivers. As the SIS specification has a major impact on the internal structure of the receiver, the interface specification is a key input for developing GNSS simulators as well as for determining the boundary properties of the input signal into the receiver, including the admitted analog signal and the format of the digital data.

    Moreover, the model-based interface specification can be integrated with a receiver design schema in SysML. This would be important to provide traceability between the interface requirements and the receiver’s functional and physical components. In the following section, we provide an outline for a preliminary integration between the interface specification and the receiver design.

    Designing Galileo Receivers

    Model-based interface specifications can support the design of Galileo receivers in several ways. For example, a specification can provide a link between Galileo requirements down to the Galileo receiver specifications, as shown in FIGURE 5.

    FIGURE 5. Links between ICML and SysML specifications.
    FIGURE 5. Links between ICML and SysML specifications.

    This capability may be useful in several scenarios. In particular, we have identified three scenarios. Scenario 1 consists of the identification of the receiver requirements that are introduced or modified by the Galileo OS SIS, with respect to existing GPS receivers. Scenario 2 concerns the linking between the ICML specification and the receiver functional schema to identify how a Galileo receiver will differ from existing GPS solutions. Scenario 3 is a development of Scenario 1 and Scenario 2, in which the physical schema definition and the physical components identification (HW and SW) may further exploit the ICML-based approach for supporting the reuse of existing GPS components.

    Below, we detail Scenario 2, introducing a simplified receiver functional schema in SysML and linking the above ICML example to the schema.

    Example Functional Schema. In this section, we illustrate a preliminary SysML representation for a simplified GNSS receiver. However, the figures are meant for exemplification purposes only and are not to be considered fully realistic and detailed for real GNSS receivers. Nevertheless, the SysML hierarchical modeling capabilities can be used to further refine the model, up to a potentially infinitesimal level of detail.

    A GNSS receiver functional schema has been derived from A Software-Defined GPS and Galileo Receiver: A Single-Frequency Approach (see Further Reading) and its equivalent SysML internal block diagram (IBD) is shown in FIGURE 6.

    FIGURE 6. High-level receiver internal block diagram (functional schema).
    FIGURE 6. High-level receiver internal block diagram (functional schema).

    In particular, the IBD illustrates the functional blocks (instances and types) and connections among these blocks that define the GNSS receiver. In particular, each of these block types is also described in other diagrams, in which the designers can specify the operations performed by the block, the attributes of the block, the referred properties, and the defined values, for example.

    In this short article, we have particularly focused on the navigation data decoder. The data decoder is defined by a Block Definition Diagram (BDD) and an IBD, which are shown in FIGURES 7 and 8, respectively.

    FIGURE 7. Navigation data decoder block definition diagram.
    FIGURE 7. Navigation data decoder block definition diagram.
    FIGURE 8. Navigation data decoder internal block diagram.
    FIGURE 8. Navigation data decoder internal block diagram.

    In particular, the BDD indicates that the navigation data decoder is composed of four types of blocks: shift buffer, parity checker, binary adder, and data item retriever. The shift buffer receives the incoming physical sequence of bits, which is subsequently verified by the parity checker. The verified sequence is then processed to retrieve the standard binary format from the SIS-specific logical coding for the data item. This function is guided by the data item retriever, which stores the defined properties of each incoming data item, in the form of a physical sequence of bits (level 1). As a consequence, the navigation data decoder is involved with data defined at several of the above-defined ICML levels. From this description, it is also possible to sketch the preliminary IBD diagram of Figure 8.

    Using a model-based approach, it becomes easier to establish links between interface elements and the functional blocks in the receiver schema.

    Moreover, these links can also be decorated with a number of properties that can be used to further describe the type of the relationship between the interface element and the functional block. The link identification is important to the receiver design in several ways. For example, linking the interface elements to the receiver functional blocks, it becomes easier to identify which functional blocks are affected by each element of the SIS interface. Moreover, the tracing can be transitively extended to the physical schema, enabling the receiver designers to more immediately identify which physical components can be reused and which ones must be replaced in existing GNSS solutions.

    We exemplify the tracing of interface elements on the above data decoding functional schema in FIGURE 9. This figure shows the navigation data decoder’s BDD in conjunction with ICML level 3 elements (with a white background). As in Figure 7, the relationships are drawn in red, including a richer set of relationship qualifiers. For example, the <<use>> qualifier indicates that the originating block uses the data specified in the connected ICML element. Similarly, the <<consumes>> qualifier indicates that the originating block takes in input instances of the ICML element. ICML level 4 elements are also relevant to this BDD; however, they are not shown for the sake of conciseness.

    FIGURE 9. Linking level 3 elements to the navigation data decoder block definition.
    FIGURE 9. Linking level 3 elements to the navigation data decoder block definition.

    Conclusions

    Galileo receivers may face market barriers that are inherently raised by the costs linked with the introduction of new technologies with respect to the existing GPS ones. In this article, we have advocated that a model-based SIS interface specification can help mitigate possible extra costs in several ways. For example, the model-based interface specification can ease the communication among stakeholders, promote the reuse and adaptation of existing GPS software and chipsets, and support the implementation of receiver-side multi-GNSS interoperability. With the objective of supporting model-based interface specifications, we have designed ICML, which has been provided with a UML profile implementation in an open-source modeling tool. We have also shown an excerpt of a possible model-based specification for a simplified Galileo OS interface. Moreover, we have outlined how the model-based specification can integrate with SysML models of GNSS receivers and support the reuse and adaptation of existing solutions. A preliminary identification of potential exploitations and further benefits is also included. Further research is ongoing to generalize the existing ICML language to more complex types of SIS interfaces.

    Acknowledgments

    The authors would like to thank the students Serena Annarilli and Carlo Di Bartolomei (University of Rome Tor Vergata) for implementing the first prototype version of the ICML profile. The authors would also like to thank Marco Porretta, European Space Agency (ESA) / European Space Research and Technology Centre (ESTEC), for the suggestions of the GNSS example. The ICML project has been partially sponsored by the ESA Summer of Code in Space Initiative, edition 2012. No endorsement is made for the use of ICML for the official Galileo SIS interface specification.

    DANIELE GIANNI is currently a requirement engineering consultant at EUMETSAT in Germany. EUMETSAT is the European operational satellite agency for monitoring weather, climate and the environment. Gianni received a Ph.D. in computer and control engineering from University of Rome Tor Vergata (Italy), in the field of modeling and simulation, in 2007. He has previously held research appointments at ESA, Imperial College, and Oxford University.

    MARCO LISI is currently GNSS services engineering manager at ESA’s Directorate of Galileo Programme and Navigation- Related Activities at ESTEC in Noordwijk, The Netherlands. He was previously responsible for system engineering, operations, and security activities in the Galileo project. He is also a special advisor to the European Commission on European space policies. Lisi has over thirty years of working experience in the aerospace and telecommunication sectors, holding management positions in R&D, and being directly involved in a number of major satellite programs, including Artemis, Meteosat Operational, Meteosat Second Generation, Globalstar, Cosmo-Skymed, and more recently Galileo.

    PIERLUIGI DE SIMONE is currently working on system assembly, integration, and verification for the Galileo mission in ESA. He has worked on many software developments in the fields of graphics, safe mode software, and visual programming. He has worked on many space missions including Helios, Meteosat, Metop, Cosmo-Skymed, and Galileo. His main interests are in modeling paradigms and cryptography and he holds a master’s degree in physics from University of Rome Tor Vergata.

    ANDREA D’AMBROGIO is associate professor of computer science at the University of Rome Tor Vergata. He has formerly been a research associate at the Concurrent Engineering Research Center of West Virginia University in Morgantown, West Virginia. His research interests are in the areas of engineering and validation of system performance and dependability, model-driven systems and software engineering, and distributed simulation.

    MICHELE LUGLIO is associate professor of telecommunication at University of Rome  Tor Vergata. He works on designing satellite systems for multimedia services both mobile and fixed.  He received the Ph.D. degree in telecommunications in 1994.

    FURTHER READING

    • Interface Communication Modeling Language (ICML)

    ICML project website.

    “A Modeling Language to Support the Interoperability of Global Navigation Satellite Systems” by D. Gianni, J. Fuchs, P. De Simone, and M. Lisi in GPS Solutions, Vol. 17, No. 2, 2013, pp. 175–198, doi: 10.1007/s10291-012-0270-z.

    •  Use of ICML for GNSS Signal-in-Space Interface Specification

    “A Model-based Signal-In-Space Interface Specification to Support the Design of Galileo Receivers” by D. Gianni, M. Lisi, P. De Simone, A. D’Ambrogio, and M. Luglio in Proceedings of the 6th ESA Workshop on Satellite Navigation Technologies and European Workshop on GNSS Signals and Signal Processing (NAVITEC), Noordwijk, The Netherlands, December 5–7, 2012, 8 pp., doi: 10.1109/NAVITEC.2012.6423066.

    “A Model-Based Approach to Signal-in-Space Specifications for Designing GNSS Receivers” by D. Gianni, J. Fuchs, P. De Simone, and M. Lisi in Inside GNSS, Vol. 6, No. 1, January/February 2011, pp. 32–39.

    • Related Modeling Languages

    The Unified Modeling Language Reference Manual, 2nd edition, by G. Booch, J. Rumbaugh, and I. Jacobson, published by Addison-Wesley Professional, an imprint of Pearson Education, Inc., Upper Saddle River, New Jersey, 2005.

    A Practical Guide to SysML: The Systems Modeling Language, 2nd edition, by S. Friedenthal, A. Moore, and R. Steiner, published by Morgan Kaufman and the Object Management Group Press, an imprint of Elsevier Inc., Waltham, Massachusetts, 2012.

    • Systems Engineering

    Systems Engineering: Principles and Practice, 2nd edition, by A. Kossiakoff, W.N. Sweet, S.J. Seymour, and S.M. Biemer, published by John Wiley & Sons, Inc., Hoboken, New Jersey, 2011.

    Survey of Model-Based Systems Engineering (MBSE) Methodologies, INCOSE-TD-2007-003-02, published by Model Based Systems Engineering Initiative, International Council on Systems Engineering, Seattle, Washington, 2008.

    • GNSS Receiver Operation

    A Software-Defined GPS and Galileo Receiver: A Single-Frequency Approach by K. Borre, D.M. Akos, N. Bertelsen, P. Rinder, and S.H. Jensen, published by Birkhäuser Boston, Cambridge, Massachusetts, 2007.

    • Galileo Status and Plans

    “Status of Galileo” (Galileo System Workshop) by H. Tork in the Proceedings of ION GNSS 2012, the 25th International Technical Meeting of the Satellite Division of The Institute of Navigation, Nashville, Tennessee, September 17–21, 2012, pp. 2474–2502.

    “Galileo Integrated Approach to Services Provision” (Galileo System Workshop) by M. Lisi in the Proceedings of ION GNSS 2012, the 25th International Technical Meeting of the Satellite Division of The Institute of Navigation, Nashville, Tennessee, September 17–21, 2012, pp. 2572–2596.

    European GNSS (Galileo) Open Service Signal in Space Interface Control Document, Issue 1.1, European Union and European Space Agency, September 2012.

     

  • Innovation: A Better Way

    Innovation: A Better Way

    Monitoring the Ionosphere with Integer-Leveled GPS Measurements

    By Simon Banville, Wei Zhang, and  Richard B. Langley

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    IT’S NOT JUST FOR POSITIONING, NAVIGATION, AND TIMING. Many people do not realize that GPS is being used in a variety of ways in addition to those of its primary mandate, which is to provide accurate position, velocity, and time information.

    The radio signals from the GPS satellites must traverse the Earth’s atmosphere on their way to receivers on or near the Earth’s surface. The signals interact with the atoms, molecules, and charged particles that make up the atmosphere, and the process slightly modifies the signals. It is these modified or perturbed signals that a receiver actually processes. And should a signal be reflected or diffracted by some object in the vicinity of the receiver’s antenna, the signal is further perturbed — a phenomenon we call multipath.

    Now, these perturbations are a bit of a nuisance for conventional users of GPS. The atmospheric effects, if uncorrected, reduce the accuracy of the positions, velocities, and time information derived from the signals. However, GPS receivers have correction algorithms in their microprocessor firmware that attempt to correct for the effects. Multipath, on the other hand, is difficult to model although the use of sophisticated antennas and advanced receiver technologies can minimize its effect.

    But there are some GPS users who welcome the multipath or atmospheric effects in the signals. By analyzing the fluctuations in signal-to-noise-ratio due to multipath, the characteristics of the reflector can be deduced. If the reflector is the ground, then the amount of moisture in the soil can be measured. And, in wintery climes, changes in snow depth can be tracked from the multipath in GPS signals.

    The atmospheric effects perturbing GPS signals can be separated into those that are generated in the lower part of the atmosphere, mostly in the troposphere, and those generated in the upper, ionized part of the atmosphere — the ionosphere. Meteorologists are able to extract information on water vapor content in the troposphere and stratosphere from the measurements made by GPS receivers and regularly use the data from networks of ground-based continuously operating receivers and those operating on some Earth-orbiting satellites to improve weather forecasts.

    And, thanks to its dispersive nature, the ionosphere can be studied by suitably combining the measurements made on the two legacy frequencies transmitted by all GPS satellites. Ground-based receiver networks can be used to map the electron content of the ionosphere, while Earth-orbiting receivers can profile electron density. Even small variations in the distribution of ionospheric electrons caused by earthquakes; tsunamis; and volcanic, meteorite, and nuclear explosions can be detected using GPS.

    In this month’s column, I am joined by two of my graduate students, who report on an advance in the signal processing procedure for better monitoring of the ionosphere, potentially allowing scientists to get an even better handle on what’s going on above our heads.

    Representation and forecast of the electron content within the ionosphere is now routinely accomplished using GPS measurements. The global distribution of permanent ground-based GPS tracking stations can effectively monitor the evolution of electron structures within the ionosphere, serving a multitude of purposes including satellite-based communication and navigation.

    It has been recognized early on that GPS measurements could provide an accurate estimate of the total electron content (TEC) along a satellite-receiver path. However, because of their inherent nature, phase observations are biased by an unknown integer number of cycles and do not provide an absolute value of TEC. Code measurements (pseudoranges), although they are not ambiguous, also contain frequency-dependent biases, which again prevent a direct determination of TEC. The main advantage of code over phase is that the biases are satellite- and receiver-dependent, rather than arc-dependent. For this reason, the GPS community initially adopted, as a common practice, fitting the accurate TEC variation provided by phase measurements to the noisy code measurements, therefore removing the arc-dependent biases. Several variations of this process were developed over the years, such as phase leveling, code smoothing, and weighted carrier-phase leveling (see Further Reading for background literature).

    The main challenge at this point is to separate the code inter-frequency biases (IFBs) from the line-of-sight TEC. Since both terms are linearly dependent, a mathematical representation of the TEC is usually required to obtain an estimate of each quantity. Misspecifications in the model and mapping functions were found to contribute significantly to errors in the IFB estimation, suggesting that this process would be better performed during nighttime when few ionospheric gradients are present. IFB estimation has been an ongoing research topic for the past two decades are still remains an issue for accurate TEC determination.

    A particular concern with IFBs is the common assumption regarding their stability. It is often assumed that receiver IFBs are constant during the course of a day and that satellite IFBs are constant for a duration of a month or more. Studies have clearly demonstrated that intra-day variations of receiver instrumental biases exist, which could possibly be related to temperature effects. This assumption was shown to possibly introduce errors exceeding 5 TEC units (TECU) in the leveling process, where 1 TECU corresponds to 0.162 meters of code delay or carrier advance at the GPS L1 frequency (1575.42 MHz).

    To overcome this limitation, one could look into using solely phase measurements in the TEC estimation process, and explicitly deal with the arc-dependent ambiguities. The main advantage of such a strategy is to avoid code-induced errors, but a larger number of parameters needs to be estimated, thereby weakening the strength of the adjustment. A comparison of the phase-only (arc-dependent) and phase-leveled (satellite-dependent) models showed that no model performs consistently better. It was found that the satellite-dependent model performs better at low-latitudes since the additional ambiguity parameters in the arc-dependent model can absorb some ionospheric features (such as gradients). On the other hand, when the mathematical representation of the ionosphere is realistic, the leveling errors may more significantly impact the accuracy of the approach.

    The advent of precise point positioning (PPP) opened the door to new possibilities for slant TEC (STEC) determination. Indeed, PPP can be used to estimate undifferenced carrier-phase ambiguity parameters on L1  and L2, which can then be used to remove the ambiguous characteristics of the carrier-phase observations. To obtain undifferenced ambiguities free from ionospheric effects, researchers have either used the widelane/ionosphere-free (IF) combinations, or the Group and Phase Ionospheric Calibration (GRAPHIC) combinations. One critical problem with such approaches is that code biases propagate into the estimated ambiguity parameters. Therefore, the resulting TEC estimates are still biased by unknown quantities, and might suffer from the unstable datum provided by the IFBs.

    The recent emergence of ambiguity resolution in PPP presented sophisticated means of handling instrumental biases to estimate integer ambiguity parameters. One such technique is the decoupled-clock method, which considers different clock parameters for the carrier-phase and code measurements. In this article, we present an “integer-leveling” method, based on the decoupled-clock model, which uses integer carrier-phase ambiguities obtained through PPP to level the carrier-phase observations.

    Standard Leveling Procedure

    This section briefly reviews the basic GPS functional model, as well as the observables usually used in ionospheric studies. A common leveling procedure is also presented, since it will serve as a basis for assessing the performance of our new method.

    Ionospheric Observables. The standard GPS functional model of dual-frequency carrier-phase and code observations can be expressed as:

    In-E1   (1)

    In-E2    (2)

    In-E3   (3)

    In-E4   (4)

    where Φi j is the carrier-phase measurement to satellite j on the Li link and, similarly, Pi j is the code measurement on Li. The term In-Pj is the biased ionosphere-free range between the satellite and receiver, which can be decomposed as:

    In-E5   (5)

    The instantaneous geometric range between the satellite and receiver antenna phase centers is ρ j. The receiver and satellite clock errors, respectively expressed as dT and dtj, are expressed here in units of meters. The term Tj stands for the tropospheric delay, while the ionospheric delay on L1 is represented by I j and is scaled by the frequency-dependent constant μ for L2, where In-u=. The biased carrier-phase ambiguities are symbolized by  and are scaled by their respective wavelengths (λi). The ambiguities can be explicitly written as:

    In-E6   (6)

    where Ni j is the integer ambiguity, bi is a receiver-dependent bias, and bi j is a satellite-dependent bias. Similarly, Bi and Bi j are instrumental biases associated with code measurements. Finally, ε contains unmodeled quantities such as noise and multipath, specific to the observable. The overbar symbol indicates biased quantities.

    In ionospheric studies, the geometry-free (GF) signal combinations are formed to virtually eliminate non-dispersive terms and thus provide a better handle on the quantity of interest:

    In-E7   (7)

    In-E8   (8)

    where IFBr and IFB j represent the code inter-frequency biases for the receiver and satellite, respectively. They are also commonly referred to as differential code biases (DCBs). Note that the noise terms (ε) are neglected in these equations for the sake of simplicity.

    Weighted-Leveling Procedure. As pointed out in the introduction, the ionospheric observables of Equations (7) and (8) do not provide an absolute level of ionospheric delay due to instrumental biases contained in the measurements. Assuming that these biases do not vary significantly in time, the difference between the phase and code observations for a particular satellite pass should be a constant value (provided that no cycle slip occurred in the phase measurements). The leveling process consists of removing this constant from each geometry-free phase observation in a satellite-receiver arc:

    In-E9   (9)

    where the summation is performed for all observations forming the arc. An elevation-angle-dependent weight (w) can also be applied to minimize the noise and multipath contribution for measurements made at low elevation angles. The double-bar symbol indicates leveled observations.

    Integer-Leveling Procedure

    The procedure of fitting a carrier-phase arc to code observations might introduce errors caused by code noise, multipath, or intra-day code-bias variations. Hence, developing a leveling approach that relies solely on carrier-phase observations is highly desirable. Such an approach is now possible with the recent developments in PPP, allowing for ambiguity resolution on undifferenced observations. This procedure has gained significant momentum in the past few years, with several organizations generating “integer clocks” or fractional offset corrections for recovering the integer nature of the undifferenced ambiguities. Among those organizations are, in alphabetical order, the Centre National d’Études Spatiale; GeoForschungsZentrum; GPS Solutions, Inc.; Jet Propulsion Laboratory; Natural Resources Canada (NRCan); and Trimble Navigation. With ongoing research to improve convergence time, it would be no surprise if PPP with ambiguity resolution would become the de facto methodology for processing data on a station-by-station basis. The results presented in this article are based on the products generated at NRCan, referred to as “decoupled clocks.”

    The idea behind integer leveling is to introduce integer ambiguity parameters on L1 and L2, obtained through PPP processing, into the geometry-free linear combination of Equation (7). The resulting integer-leveled observations, in units of meters, can then be expressed as:
    In-E10   (10)
    where In-NJ1 and In-NJ2 are the ambiguities obtained from the PPP solution, which should be, preferably, integer values. Since those ambiguities are obtained with respect to a somewhat arbitrary ambiguity datum, they do not allow instant recovery of an unbiased slant ionospheric delay. This fact was highlighted in Equation (10), which indicates that, even though the arc-dependency was removed from the geometry-free combination, there are still receiver- and satellite-dependent biases (br and b j, respectively) remaining in the integer-leveled observations. The latter are thus very similar in nature to the standard-leveled observations, in the sense that the biases br and b j replace the well-known IFBs. As a consequence, integer-leveled observations can be used with any existing software used for the generation of TEC maps. The motivation behind using integer-leveled observations is the mitigation of leveling errors, as explained in the next sections.

    Slant TEC Evaluation

    As a first step towards assessing the performance of integer-leveled observations, STEC values are derived on a station-by-station basis. The slant ionospheric delays are then compared for a pair of co-located receivers, as well as with global ionospheric maps (GIMs) produced by the International GNSS Service (IGS).

    Leveling Error Analysis. Relative leveling errors between two co-located stations can be obtained by computing between-station differences of leveled observations:

    In-E11   (11)

    where subscripts A and B identify the stations involved, and εl is the leveling error. Since the distance between stations is short (within 100 meters, say), the ionospheric delays will cancel, and so will the satellite biases (b j) which are observed at both stations. The remaining quantities will be the (presumably constant) receiver biases and any leveling errors. Since there are no satellite-dependent quantities in Equation (11), the differenced observations obtained should be identical for all satellites observed, provided that there are no leveling errors. The same principles apply to observations leveled using other techniques discussed in the introduction. Hence, Equation (11) allows comparison of the performance of various leveling approaches.

    This methodology has been applied to a baseline of approximately a couple of meters in length between stations WTZJ and WTZZ, in Wettzell, Germany. The observations of both stations from March 2, 2008, were leveled using a standard leveling approach, as well as the method described in this article. Relative leveling errors computed using Equation (11) are displayed in Figure 1, where each color represents a different satellite. It is clear that code noise and multipath do not necessarily average out over the course of an arc, leading to leveling errors sometimes exceeding a couple of TECU for the standard leveling approach (see panel (a)). On the other hand, integer-leveled observations agree fairly well between stations, where leveling errors were mostly eliminated. In one instance, at the beginning of the session, ambiguity resolution failed at both stations for satellite PRN 18, leading to a relative error of 1.5 TECU, more or less. Still, the advantages associated with integer leveling should be obvious since the relative error of the standard approach is in the vicinity of -6 TECU for this satellite.

    FIGURE 1 Relative leveling errors between stations WTZJ and WTZZ on March 2, 2008: (a) standard-leveled observations and (b) integer-leveled observations.
    FIGURE 1. Relative leveling errors between stations WTZJ and WTZZ on March 2, 2008: (a) standard-leveled observations and (b) integer-leveled observations.

    The magnitude of the leveling errors obtained for the standard approach agrees fairly well with previous studies (see Further Reading). In the event that intra-day variations of the receiver IFBs are observed, even more significant biases were found to contaminate standard-leveled observations. Since the decoupled-clock model used for ambiguity resolution explicitly accounts for possible variations of any equipment delays, the estimated ambiguities are not affected by such effects, leading to improved leveled observations.

    STEC Comparisons. Once leveled observations are available, the next step consists of separating STEC from instrumental delays. This task can be accomplished on a station-by-station basis using, for example, the single-layer ionospheric model. Replacing the slant ionospheric delays (I j) in Equation (10) by a bilinear polynomial expansion of VTEC leads to:

    In-E12    (12)

    where M(e) is the single-layer mapping function (or obliquity factor) depending on the elevation angle (e) of the satellite. The time-dependent coefficients a0, a1, and a2 determine the mathematical representation of the VTEC above the station. Gradients are modeled using Δλ, the difference between the longitude of the ionospheric pierce point and the longitude of the mean sun, and Δϕ, the difference between the geomagnetic latitude of the ionospheric pierce point and the geomagnetic latitude of the station. The estimation procedure described by Attila Komjathy (see Further Reading) is followed in all subsequent tests. An elevation angle cutoff of 10 degrees was applied and the shell height used was 450 kilometers. Since it is not possible to obtain absolute values for the satellite and receiver biases, the sum of all satellite biases was constrained to a value of zero. As a consequence, all estimated biases will contain a common (unknown) offset. STEC values, in TECU, can then be computed as:

    In-E13     (13)

    where the hat symbol denotes estimated quantities, and  is equal to zero (that is, it is not estimated) when biases are obtained on a station-by-station basis. The frequency, f1, is expressed in Hz. The numerical constant 40.3, determined from values of fundamental physical constants, is sufficiently precise for our purposes, but is a rounding of the more precise value of 40.308.

    While integer-leveled observations from co-located stations show good agreement, an external TEC source is required to make sure that both stations are not affected by common errors. For this purpose, Figure 2 compares STEC values computed from GIMs produced by the IGS and STEC values derived from station WTZJ using both standard- and integer-leveled observations. The IGS claims root-mean-square errors on the order of 2-8 TECU for vertical TEC, although the ionosphere was quiet on the day selected, meaning that errors at the low-end of that range are expected. Errors associated with the mapping function will further contribute to differences in STEC values. As apparent from Figure 2, no significant bias can be identified in integer-leveled observations. On the other hand, negative STEC values (not displayed in Figure 2) were obtained during nighttimes when using standard-leveled observations, a clear indication that leveling errors contaminated the observations.

    FIGURE 2 Comparison between STEC values obtained from a global ionospheric map and those from station WTZJ using standard- and integer-leveled observations.
    FIGURE 2. Comparison between STEC values obtained from a global ionospheric map and those from station WTZJ using standard- and integer-leveled observations.

    STEC Evaluation in the Positioning Domain. Validation of slant ionospheric delays can also be performed in the positioning domain. For this purpose, a station’s coordinates from processing the observations in static mode (that is, one set of coordinates estimated per session) are estimated using (unsmoothed) single-frequency code observations with precise orbit and clock corrections from the IGS and various ionosphere-correction sources. Figure 3 illustrates the convergence of the 3D position error for station WTZZ, using STEC corrections from the three sources introduced previously, namely: 1) GIMs from the IGS, 2) STEC values from station WTZJ derived from standard leveling, and 3) STEC values from station WTZJ derived from integer leveling. The reference coordinates were obtained from static processing based on dual-frequency carrier-phase and code observations. The benefits of the integer-leveled corrections are obvious, with the solution converging to better than 10 centimeters. Even though the distance between the stations is short, using standard-leveled observations from WTZJ leads to a biased solution as a result of arc-dependent leveling errors. Using a TEC map from the IGS provides a decent solution considering that it is a global model, although the solution is again biased.

    FIGURE 3 Single-frequency code-based positioning results for station WTZZ (in static mode) using different ionosphere-correction sources: GIM and STEC values from station WTZJ using standard- and integer-leveled observations.
    FIGURE 3. Single-frequency code-based positioning results for station WTZZ (in static mode) using different ionosphere-correction sources: GIM and STEC values from station WTZJ using standard- and integer-leveled observations.

    This station-level analysis allowed us to confirm that integer-leveled observations can seemingly eliminate leveling errors, provided that carrier-phase ambiguities are fixed to proper integer values. Furthermore, it is possible to retrieve unbiased STEC values from those observations by using common techniques for isolating instrumental delays. The next step consisted of examining the impacts of reducing leveling errors on VTEC.

    VTEC Evaluation

    When using the single-layer ionospheric model, vertical TEC values can be derived from the STEC values of Equation (13) using:

    In-E14    (14)

    Dividing STEC by the mapping function will also reduce any bias caused by the leveling procedure. Hence, measures of VTEC made from a satellite at a low elevation angle will be less impacted by leveling errors. When the satellite reaches the zenith, then any bias in the observation will fully propagate into the computed VTEC values. On the other hand, the uncertainty of the mapping function is larger at low-elevation angles, which should be kept in mind when analyzing the results.

    Using data from a small regional network allows us to assess the compatibility of the VTEC quantities between stations. For this purpose, GPS data collected as a part of the Western Canada Deformation Array (WCDA) network, still from March 2, 2008, was used. The stations of this network, located on and near Vancouver Island in Canada, are indicated in Figure 4. Following the model of Equation (12), all stations were integrated into a single adjustment to estimate receiver and satellite biases as well as a triplet of time-varying coefficients for each station. STEC values were then computed using Equation (13), and VTEC values were finally derived from Equation (14). This procedure was again implemented for both standard- and integer-leveled observations.

    FIGURE 4. Network of stations used in the VTEC evaluation procedures.
    FIGURE 4. Network of stations used in the VTEC evaluation procedures.

    To facilitate the comparison of VTEC values spanning a whole day and to account for ionospheric gradients, differences with respect to the IGS GIM were computed. The results, plotted by elevation angle, are displayed in Figure 5 for all seven stations processed (all satellite arcs from the same station are plotted using the same color). The overall agreement between the global model and the station-derived VTECs is fairly good, with a bias of about 1 TECU. Still, the top panel demonstrates that, at high elevation angles, discrepancies between VTEC values derived from standard-leveled observations and the ones obtained from the model have a spread of nearly 6 TECU. With integer-leveled observations (see bottom panel), this spread is reduced to approximately 2 TECU. It is important to realize that the dispersion can be explained by several factors, such as remaining leveling errors, the inexact receiver and satellite bias estimates, and inaccuracies of the global model. It is nonetheless expected that leveling errors account for the most significant part of this error for standard-leveled observations.

    For satellites observed at a lower elevation angle, the spread between arcs is similar for both methods (except for station UCLU in panel (a) for which the estimated station IFB parameter looks significantly biased). As stated previously, the reason is that leveling errors are reduced when divided by the mapping function. The latter also introduces further errors in the comparisons, which explains why a wider spread should typically be associated with low-elevation-angle satellites. Nevertheless, it should be clear from Figure 5 that integer-leveled observations offer a better consistency than standard-leveled observations.

    FIGURE 5 VTEC differences, with respect to the IGS GIM, for all satellite arcs as a function of the elevation angle of the satellite, using (a) standard-leveled observations and (b) integer-leveled observations.
    FIGURE 5. VTEC differences, with respect to the IGS GIM, for all satellite arcs as a function of the elevation angle of the satellite, using (a) standard-leveled observations and (b) integer-leveled observations.
    Conclusion

    The technique of integer leveling consists of introducing (preferably) integer ambiguity parameters obtained from PPP into the geometry-free combination of observations. This process removes the arc dependency of the signals, and allows integer-leveled observations to be used with any existing TEC estimation software. While leveling errors of a few TECU exist with current procedures, this type of error can be eliminated through use of our procedure, provided that carrier-phase ambiguities are fixed to the proper integer values. As a consequence, STEC values derived from nearby stations are typically more consistent with each other. Unfortunately, subsequent steps involved in generating VTEC maps, such as transforming STEC to VTEC and interpolating VTEC values between stations, attenuate the benefits of using integer-leveled observations.

    There are still ongoing challenges associated with the GIM-generation process, particularly in terms of latency and three-dimensional modeling. Since ambiguity resolution in PPP can be achieved in real time, we believe that integer-leveled observations could benefit near-real-time ionosphere monitoring. Since ambiguity parameters are constant for a satellite pass (provided that there are no cycle slips), integer ambiguity values (that is, the leveling information) can be carried over from one map generation process to the next. Therefore, this methodology could reduce leveling errors associated with short arcs, for instance.

    Another prospective benefit of integer-leveled observations is the reduction of leveling errors contaminating data from low-Earth-orbit (LEO) satellites, which is of particular importance for three-dimensional TEC modeling. Due to their low orbits, LEO satellites typically track a GPS satellite for a short period of time. As a consequence, those short arcs do not allow code noise and multipath to average out, potentially leading to important leveling errors. On the other hand, undifferenced ambiguity fixing for LEO satellites already has been demonstrated, and could be a viable solution to this problem.

    Evidently, more research needs to be conducted to fully assess the benefits of integer-leveled observations. Still, we think that the results shown herein are encouraging and offer potential solutions to current challenges associated with ionosphere monitoring.

    Acknowledgments

    We would like to acknowledge the help of Paul Collins from NRCan in producing Figure 4 and the financial contribution of the Natural Sciences and Engineering Research Council of Canada in supporting the second and third authors. This article is based on two conference papers: “Defining the Basis of an ‘Integer-Levelling’ Procedure for Estimating Slant Total Electron Content” presented at ION GNSS 2011 and “Ionospheric Monitoring Using ‘Integer-Levelled’ Observations” presented at ION GNSS 2012. ION GNSS 2011 and 2012 were the 24th and 25th International Technical Meetings of the Satellite Division of The Institute of Navigation, respectively. ION GNSS 2011 was held in Portland, Oregon, September 19–23, 2011, while ION GNSS 2012 was held in Nashville, Tennessee, September 17–21, 2012.

    SIMON BANVILLE is a Ph.D. candidate in the Department of Geodesy and Geomatics Engineering at the University of New Brunswick (UNB) under the supervision of Dr. Richard B. Langley. His research topic is the detection and correction of cycle slips in GNSS observations. He also works for Natural Resources Canada on real-time precise point positioning and ambiguity resolution.

    WEI ZHANG received his M.Sc. degree (2009) in space science from the School of Earth and Space Science of Peking University, China. He is currently an M.Sc.E. student in the Department of Geodesy and Geomatics Engineering at UNB under the supervision of Dr. Langley. His research topic is the assessment of three-dimensional regional ionosphere tomographic models using GNSS measurements.

    FURTHER READING

    • Authors’ Conference Papers

    “Defining the Basis of an ‘Integer-Levelling’ Procedure for Estimating Slant Total Electron Content” by S. Banville and R.B. Langley in Proceedings of ION GNSS 2011, the 24th International Technical Meeting of the Satellite Division of The Institute of Navigation, Portland, Oregon, September 19–23, 2011, pp. 2542–2551.

    “Ionospheric Monitoring Using ‘Integer-Levelled’ Observations” by S. Banville, W. Zhang, R. Ghoddousi-Fard, and R.B. Langley in Proceedings of ION GNSS 2012, the 25th International Technical Meeting of the Satellite Division of The Institute of Navigation, Nashville, Tennessee, September 17–21, 2012, pp. 3753–3761.

    • Errors in GPS-Derived Slant Total Electron Content

    “GPS Slant Total Electron Content Accuracy Using the Single Layer Model Under Different Geomagnetic Regions and Ionospheric Conditions” by C. Brunini, and F.J. Azpilicueta in Journal of Geodesy, Vol. 84, No. 5, pp. 293–304, 2010, doi: 10.1007/s00190-010-0367-5.

    “Calibration Errors on Experimental Slant Total Electron Content (TEC) Determined with GPS” by L. Ciraolo, F. Azpilicueta, C. Brunini, A. Meza, and S.M. Radicella in Journal of Geodesy, Vol. 81, No. 2, pp. 111–120, 2007, doi: 10.1007/s00190-006-0093-1.

    • Global Ionospheric Maps

    “The IGS VTEC Maps: A Reliable Source of Ionospheric Information Since 1998” by M. Hernández-Pajares, J.M. Juan, J. Sanz, R. Orus, A. Garcia-Rigo, J. Feltens, A. Komjathy, S.C. Schaer, and A. Krankowski in Journal of Geodesy, Vol. 83, No. 3–4, 2009, pp. 263–275, doi: 10.1007/s00190-008-0266-1.

    • Ionospheric Effects on GNSS

    “GNSS and the Ionosphere: What’s in Store for the Next Solar Maximum” by A.B.O. Jensen and C. Mitchell in GPS World, Vol. 22, No. 2, February 2011, pp. 40–48.

    “Space Weather: Monitoring the Ionosphere with GPS” by A. Coster, J. Foster, and P. Erickson in GPS World, Vol. 14, No. 5, May 2003, pp. 42–49.

    “GPS, the Ionosphere, and the Solar Maximum” by R.B. Langley in GPS World, Vol. 11, No. 7, July 2000, pp. 44–49.

    Global Ionospheric Total Electron Content Mapping Using the Global Positioning System by A. Komjathy, Ph. D. dissertation, Technical Report No. 188, Department of Geodesy and Geomatics Engineering, University of New Brunswick, Fredericton, New Brunswick, Canada, 1997.

    • Decoupled Clock Model

    “Undifferenced GPS Ambiguity Resolution Using the Decoupled Clock Model and Ambiguity Datum Fixing” by P. Collins, S. Bisnath, F. Lahaye, and P. Héroux in  Navigation: Journal of The Institute of Navigation, Vol. 57, No. 2, Summer 2010, pp. 123–135.

     

  • Innovation: Getting Control

    Innovation: Getting Control

    Off-the-Shelf Antennas for Controlled-Reception-Pattern Antenna Arrays

    By Yu-Hsuan Chen, Sherman Lo, Dennis M. Akos, David S. De Lorenzo, and Per Enge

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    THE ANTENNA IS A CRITICAL COMPONENT OF ANY GNSS RECEIVING EQUIPMENT. It must be carefully designed for the frequencies and structures of the signals to be acquired and tracked. Important antenna properties include polarization, frequency coverage, phase-center stability, multipath suppression, the antenna’s impact on receiver sensitivity, reception or gain pattern, and interference handling. While all of these affect an antenna’s performance, let’s just look at the last two here.

    The gain pattern of an antenna is the spatial variation of the gain, or ratio of the power delivered by the antenna for a signal arriving from a particular direction compared to that delivered by a hypothetical isotropic reference antenna. Typically, for GNSS antennas, the reference antenna is also circularly polarized and the gain is then expressed in dBic units.

    An antenna may have a gain pattern with a narrow central lobe or beam if it is used for communications between two fixed locations or if the antenna can be physically steered to point in the direction of a particular transmitter. GNSS signals, however, arrive from many directions simultaneously, and so most GNSS receiving antennas tend to be omni-directional in azimuth with a gain roll-off from the antenna boresight to the horizon.

    While such an antenna is satisfactory for many applications, it is susceptible to accidental or deliberate interference from signals arriving from directions other than those of GNSS signals. Interference effects could be minimized if the gain pattern could be adjusted to null-out the interfering signals or to peak the gain in the directions of all legitimate signals. Such a controlled-reception-pattern antenna (CRPA) can be constructed using an array of antenna elements, each one being a patch antenna, say, with the signals from the elements combined before feeding them to the receiver. The gain pattern of the array can then be manipulated by electronically adjusting the phase relationship between the elements before the signals are combined. However, an alternative approach is to feed the signals from each element to separate banks of tracking channels in the receiver and form a beam-steering vector based on the double-difference carrier-phase measurements from pairs of elements that is subsequently used to weight the signals from the elements before they are processed to obtain a position solution. In this month’s column, we learn how commercial off-the-shelf antennas and a software-defined receiver can be used to design and test such CRPA arrays.

    “Innovation” features discussions about advances in GPS technology, its applications, and the fundamentals of GPS positioning. The column is coordinated by Richard Langley, Department of Geodesy and Geomatics Engineering, University of New Brunswick. To contact him with topic ideas, email him at lang @ unb.ca.

    Signals from global navigation satellite systems are relatively weak and thus vulnerable to deliberate or unintentional interference. An electronically steered antenna array system provides an effective approach to mitigate interference by controlling the reception pattern and steering the system’s beams or nulls. As a result, so-called controlled-reception-pattern-antenna (CRPA) arrays have been deployed by organizations such as the U.S. Department of Defense, which seeks high levels of interference rejection.

    Our efforts have focused on developing a commercially viable CRPA system using commercial off-the-shelf (COTS) components to support the needs of Federal Aviation Administration (FAA) alternative position navigation and timing (APNT) efforts. In 2010, we implemented a seven-element, two-bit-resolution, single-beam and real-time CRPA software receiver. In 2011, the receiver was upgraded to support all-in-view, 16-bit-resolution with four elements.

    Even though we can implement these CRPA software receivers in real time, the performance of anti-interference is highly dependent on the antenna array layout and characteristics of the antenna elements. Our beamforming approach allows us to use several COTS antennas as an array rather than a custom-designed and fully calibrated antenna. The use of COTS antennas is important, as the goal of our effort is to develop a CRPA for commercial endeavors — specifically for robust timing for the national airspace. Hence, it is important to study the geometry layout of the individual antennas of the array to assess the layouts and to determine how antenna performance affects the array’s use.

    In our work, we have developed a procedure for calculating the electrical layouts of an antenna array by differential carrier-phase positioning. When compared to the physical layout, the results of electrical layouts can be used to determine the mutual coupling effect of each combination. Using the electrical layout, the resultant gain patterns can be calculated and used to see the beamwidth and the side-lobe issue. This is important as these factors have significant effects on anti-interference performance. This study focuses on understanding the performance effects of geometry and developing a method for describing the best geometry.

    We adopted three models of COTS antenna and two possible layouts for a four-element array. Then, signal collection hardware consisting of four Universal Software Radio Peripheral (USRP) software-defined radios and one host personal computer was assembled to collect array data sets for each layout/antenna combination. Our developed CRPA software receiver was used to process all data sets and output carrier-phase measurements.

    In this article, we will present the pattern analysis for the two selected layouts and describe how we collected the experimental data. We’ll then show the results of calculating the electrical spacing for the layouts are compare them to the physical layouts. Lastly, we’ll show the resulting patterns, discuss the antenna mutual coupling effects, and give our conclusions.

    Antenna Array Pattern Analysis

    Pattern is defined as the directional strength of a radio-frequency signal viewed from the antenna. The pattern of an antenna array is the product of the isotropic array factor and the isolated element pattern. We assume that the pattern of each element is identical and only consider the isotropic array factor. FIGURE 1 shows the coordination of an antenna array. The first element is set as a reference position. The x-axis is the east direction, the y-axis is the north direction, and the z-axis is the up direction. The baseline vector of the ith antenna is given by I-pi and I-r is the unit vector to the satellite.

    I-Fig1
    Figure 1. Antenna array geometry and direction of satellite. Array elements are identified as E#1, E#2, E#3, and E#4.

    The isotropic array factor is given by

    I-Eq1   (1)

    where λ is wavelength, and Ai is a complex constant. Currently, we only implement a four-element-array CRPA software receiver in real time. Hence, we analyze two kinds of layout of half-wavelength four-element arrays: a symmetrical Y array and a square array. Each antenna is separated from its nearest neighbor by a half wavelength. FIGURE 2 shows photos of the two layouts. FIGURE 3 shows the physical layouts.

    I-Fig2
    Figure 2. Photos of antenna arrays (left: Y array; right: square array).
    I-Fig3top
    Figure 3A. Physical layout of antenna arrays (Y array).
    I-Fig3bottom
    Figure 3B. Physical layout of antenna arrays (square array).

    The antenna patterns towards an elevation angle of 90 degrees, computed using equation 1 and the design layouts, are shown in FIGURE 4. One of the key characteristics of a pattern is the beamwidth, which is defined as the angle with 3-dB loss. FIGURE 5 shows the patterns in elevation angle where the beamwidth of the Y layout is 74 degrees and 86 degrees for the square layout. A narrow beamwidth will benefit anti-interference performance particularly if the interference is close to the direction of a target satellite.

    I-Fig4
    Figure 4. Patterns of antenna arrays (left: Y array; right: square array).
    FIGURE 5 Pattern beamwidths of Y and square arrays (3 dB beamwidth shown).
    Figure 5. Pattern beamwidths of Y and square arrays (3 dB beamwidth shown).
    Specifications of COTS Antennas

    Typically, the COTS antenna selection is determined by high gain and great out-of-band rejection. TABLE 1 shows the specifications of the three antenna models used in this article. These antennas are all patch antennas. The antennas are equipped with surface-acoustic-wave filters for rejecting out-of-band signals. A three-stage low noise amplifier with over 30 dB gain is also embedded in each antenna.

    I-T1
    Table 1. Specifications of COTS antennas used.
    Signal Collection Hardware and Experimental Setup

    The hardware used to collect the antenna array datasets is shown in FIGURE 6 with block-diagram representation in FIGURE 7. The hardware includes a four-element antenna array, four USRP2 software radio systems and one host computer. The signal received from the COTS antenna passes to a USRP2 board equipped with a 800–2300 MHz DBSRX2 programmable mixing and down-conversion daughterboard. The individual USRP2 boards are synchronized by a 10-MHz external common clock generator and a pulse-per-second (PPS) signal. The USRP2s are controlled by the host computer running the Ubuntu distribution of Linux. The open-source GNU Radio software-defined radio block is used to configure USRP2s and collect datasets. All USRP2s are configured to collect the L1 (1575.42 MHz) signal. The signals are converted to near zero intermediate frequency (IF) and digitized to 14-bit complex outputs (I and Q).

    I-Fig7
    Figure 6. Photo of the signal collection hardware.
    I-Fig6
    Figure 7. Block diagram of the signal collection hardware.

    The sampling rate is set as 4 MHz. The host computer uses two solid state drives for storing data sets. For our study, a 64-megabytes per second data transfer rate is needed. The fast solid state drives are especially useful when using high bandwidth signals such as L5, which will require an even higher data streaming rate (80 megabytes per second per channel).

    To compare the physical and electrical layouts of the antenna arrays, we set up the signal collection hardware to record six data sets for the two layouts and the three antenna models as shown in TABLE 2. All of the data sets were five minutes long to obtain enough carrier-phase measurements for positioning.

    I-T2
    Table 2. Experimental setups.
    Logging Carrier-Phase Measurements

    To calculate the precise spacing between the antenna elements, hundreds of seconds of carrier-phase measurements from each element are needed. The collected data sets were provided by our in-house-developed CRPA software receiver. The receiver was developed using Visual Studio under Windows. Most of source code is programmed using C++. Assembly language is used to program the functions with high computational complexity such as correlation operations. The software architecture of the receiver is depicted in FIGURE 8. This architecture exploits four sets of 12 tracking channels in parallel to process each IF signal from an antenna element. Each channel is dedicated to tracking the signal of a single satellite. The tracking channels output carrier-phase measurements to build the steering vectors for each satellite. The Minimum Variance Distortionless Response (MVDR) algorithm was adopted for adaptively calculating the weights for beamforming. Here, there are 12 weight sets, one for each satellite in a tracking channel, for the desired directions of satellites.

    Figure 8. Block diagram of the software architecture.
    Figure 8. Block diagram of the software architecture.

    Using the pre-correlation beamforming approach, the weights are multiplied with IF data and summed over all elements to form 12 composite signals. These signals are then processed by composite tracking channels. Finally, positioning is performed if pseudoranges and navigation messages are obtained from these channels. FIGURE 9 is the graphical user interface (GUI) of the CRPA software receiver. It consists of the channel status of all channels, carrier-phase differences, positioning results, an east-north (EN) plot, a sky plot, a carrier-to-noise-density (C/N0) plot and the gain patterns of the array for each tracked satellite. In the figure, the CRPA software receiver is tracking 10 satellites and its positioning history is shown in the EN plot. The beamforming channels have about 6 dB more gain in C/N0 than the channels of a single element. In each pattern, the direction with highest gain corresponds to the direction of the satellite. While the CRPA software receiver is running, the carrier-phase measurements of all elements and the azimuth and elevation angle of the satellites are logged every 100 milliseconds. Each data set in Table 2 was processed by the software receiver to log the data.

    FIGURE 9 Screenshot of the controlled-reception-pattern-antenna software-receiver graphical user interface.
    Figure 9. Screenshot of the controlled-reception-pattern-antenna software-receiver graphical user interface.
    Electrical Layout of Antenna Array – Procedure

    The procedure of calculating the electrical layout of an antenna array is depicted in FIGURE 10. The single-difference integrated carrier phase (ICP) between the signals of an element, i, and a reference element, j, is represented as:

    I-Eq2   (2)

    where rkij is differential range toward the kth satellite between the ith and jth antenna elements (a function of the baseline vector between the ith and jth elements), δLij is the cable-length difference between the ith and jth antenna elements, Nkij is the integer associated with Φkij , εkij and  is the phase error. The double-difference ICP between the kth satellite and reference satellite l is represented as:
    I-Eq3   (3)

    The cable-length difference term is subtracted in the double difference. Since the distances between the antenna elements are close to one wavelength, equation (3) can be written as:
    I-Eq4   (4)

    where i-rk is the unit vector to satellite k, pij is the baseline vector between the ith and jth elements. By combining all the double-difference measurements of the ijth pair of elements, the observations equation can be represented as:
    I-Eq5      (5)

    From the positioning results of composite channels, the azimuth and elevation angle of satellites are used to manipulate matrix G. To solve equation (5), the LAMBDA method was adopted to give the integer vector N. Then, pij  is solved by substituting N into equation (5). Finally, the cable-length differences are obtained by substituting the solutions of N and pij into equation (2).

    This approach averages the array pattern across all satellite measurements observed during the calibration period.

    FIGURE 10 Procedure for calculating antenna-array electrical spacing.
    Figure 10. Procedure for calculating antenna-array electrical spacing.
    Electrical Layout of Antenna Array – Results

    Using the procedure in the previous section, all electrical layouts of the antenna array were calculated and are shown in FIGURES 11 and 12. We aligned the vectors from element #1 to element #2 for all layouts. TABLE 3 lists the total differences between the physical and electrical layouts. For the same model of antenna, the Y layout has less difference than the square layout. And, in terms of antenna model, antenna #1 has the least difference for both Y and square layouts. We could conclude that the mutual coupling effect of the Y layout is less than that of the square layout, and that antenna #1 has the smallest mutual coupling effect among all three models of antenna for these particular elements and observations utilized.

    FIGURE 11 Results of electrical layout using three models of antenna compared to the physical layout for the Y array.
    Figure 11. Results of electrical layout using three models of antenna compared to the physical layout for the Y array.
    I-Fig12
    Figure 12. Results of electrical layout using three models of antenna compared to physical layout for the square array.
    Table 3. Total differences between physical and electrical layouts.
    Table 3. Total differences between physical and electrical layouts.

    To compare the patterns of all calculated electrical layouts, we selected two specific directions: an elevation angle of 90 degrees and a target satellite, WAAS GEO PRN138, which was available for all data sets. The results are shown in FIGURES 13 and 14, respectively. From Figure 13, the beamwidth of the Y layout is narrower than that of the square layout for all antenna models. When compared to Figure 5, this result confirms the validity of our analysis approach. But, in Figure 14, a strong sidelobe appears at azimuth -60º in the pattern of Y layout for antenna #2. If there is some interference located in this direction, the anti-interference performance of the array will be limited. This is due to a high mutual coupling effect of antenna #2 and only can be seen after calculating the electrical layout.

    I-Fig13
    Figure 13. Patterns of three models of antenna and two layouts toward an elevation angle of 90 degrees.
    I-Fig14
    Figure 14. Patterns of three models of antenna and two layouts toward the WAAS GEO satellite PRN138.
    Conclusions

    The results of our electrical layout experiment show that the Y layout has a smaller difference with respect to the physical layout than the square layout. That implies that the elements of the Y layout have less mutual coupling. For the antenna selection, arrays based on antenna model #1 showed the least difference between electrical and physical layout. And its pattern does not have a high grating lobe in a direction other than to the target satellite.

    The hardware and methods used in this article can serve as a testing tool for any antenna array. Specifically, our methodology, which can be used to collect data, compare physical and electrical layouts, and assess resultant antenna gain patterns, allows us to compare the performances of different options and select the best antenna and layout combination. Results can be used to model mutual coupling and the overall effect of layout and antenna type on array gain pattern and overall CRPA capabilities. This procedure is especially important when using COTS antennas to assemble an antenna array and as we increase the number of antenna elements and the geometry possibilities of the array.

    Acknowledgments

    The authors gratefully acknowledge the work of Dr. Jiwon Seo in building the signal collection hardware. The authors also gratefully acknowledge the Federal Aviation Administration Cooperative Research and Development Agreement 08-G-007 for supporting this research. This article is based on the paper “A Study of Geometry and Commercial Off-The-Shelf (COTS) Antennas for Controlled Reception Pattern Antenna (CRPA) Arrays” presented at ION GNSS 2012, the 25th International Technical Meeting of the Satellite Division of The Institute of Navigation, held in Nashville, Tennessee, September 17–21, 2012.

    Manufacturers

    The antennas used to construct the arrays are Wi-Sys Communications Inc., now PCTEL, Inc. models WS3978 and WS3997 and PCTEL, Inc. model 3978D-HR. The equipment used to collect data sets includes Ettus Research LLC model USRP2 software-defined radios and associated DBSRX2 daughterboards.

    Yu-Hsuan Chen is a postdoctoral scholar in the GNSS Research Laboratory at Stanford University, Stanford, California.

    Sherman Lo is a senior research engineer at the Stanford GNSS Research Laboratory.

    Dennis M. Akos is an associate professor with the Aerospace Engineering Science Department in the University of Colorado at Boulder with visiting appointments at Luleå Technical University, Sweden, and Stanford University.

    David S. De Lorenzo is a principal research engineer at Polaris Wireless, Mountain View, California, and a consulting research associate to the Stanford GNSS Research Laboratory.

    Per Enge is a professor of aeronautics and astronautics at Stanford University, where he is the Kleiner-Perkins Professor in the School of Engineering. He directs the GNSS Research Laboratory.

    FURTHER READING

    • Authors’ Publications

    “A Study of Geometry and Commercial Off-The-Shelf (COTS) Antennas for Controlled Reception Pattern Antenna (CRPA) Arrays” by Y.-H. Chen in Proceedings of ION GNSS 2012, the 25th International Technical Meeting of The Institute of Navigation, Nashville, Tennessee, September 17–21, 2012, pp. 907–914 (ION Student Paper Award winner).

    “A Real-Time Capable Software-Defined Receiver Using GPU for Adaptive Anti-Jam GPS Sensors” by J. Seo, Y.-H. Chen, D.S. De Lorenzo, S. Lo, P. Enge, D. Akos, and J. Lee in Sensors, Vol. 11, No. 9, 2011, pp. 8966–8991, doi: 10.3390/s110908966.

    “Real-Time Software Receiver for GPS Controlled Reception Pattern Array Processing” by Y.-H. Chen, D.S. De Lorenzo, J. Seo, S. Lo, J.-C. Juang, P. Enge, and D.M. Akos in Proceedings of ION GNSS 2010, the 23rd International Technical Meeting of The Institute of Navigation, Portland, Oregon, September 21–24, 2010, pp. 1932–1941.

    “A GNSS Software Receiver Approach for the Processing of Intermittent Data” by Y.-H. Chen and J.-C. Juang in Proceedings of ION GNSS 2007, the 20th International Technical Meeting of The Institute of Navigation, Fort Worth, Texas, September 25–28, 2007, pp. 2772–2777.

    • Controlled-Reception-Pattern Antenna Arrays

    “Anti-Jam Protection by Antenna: Conception, Realization, Evaluation of a Seven-Element GNSS CRPA” by F. Leveau, S. Boucher, E. Goron, and H. Lattard in GPS World, Vol. 24, No. 2, February 2013, pp. 30–33.

    “Development of Robust Safety-of-Life Navigation Receivers” by M.V.T. Heckler, M. Cuntz, A. Konovaltsev, L.A. Greda, A. Dreher, and M. Meurer in IEEE Transactions on Microwave Theory and Techniques, Vol. 59, No. 4, April 2011, pp. 998–1005, doi: 10.1109/TMTT.2010.2103090.

    Phased Array Antennas, 2nd Edition, by R. C. Hansen, published by John Wiley & Sons, Inc., Hoboken, New Jersey, 2009.

    • Antenna Principles

    “Selecting the Right GNSS Antenna” by G. Ryley in GPS World, Vol. 24, No. 2, February 2013, pp. 40–41 (in PDF of 2013 Antenna Survey.)

    “GNSS Antennas: An Introduction to Bandwidth, Gain Pattern, Polarization, and All That” by G.J.K. Moernaut and D. Orban in GPS World, Vol. 20, No. 2, February 2009, pp. 42–48.

    “A Primer on GPS Antennas” by R.B. Langley in GPS World, Vol. 9, No. 7, July 1998, pp. 50-54.

    • Software-Defined Radios for GNSS

    “A USRP2-based Reconfigurable Multi-constellation Multi-frequency GNSS Software Receiver Front End” by S. Peng and Y. Morton in GPS Solutions, Vol. 17, No. 1, January 2013, pp. 89-102.

    “Software GNSS Receiver: An Answer for Precise Positioning Research” by T. Pany, N. Falk, B. Riedl, T. Hartmann, G. Stangl, and C. Stöber in GPS World, Vol. 23, No. 9, September 2012, pp. 60–66.

    “Simulating GPS Signals: It Doesn’t Have to Be Expensive” by A. Brown, J. Redd, and M.-A. Hutton in GPS World, Vol. 23, No. 5, May 2012, pp. 44–50.

    Digital Satellite Navigation and Geophysics: A Practical Guide with GNSS Signal Simulator and Receiver Laboratory by I.G. Petrovski and T. Tsujii with foreword by R.B. Langley, published by Cambridge University Press, Cambridge, U.K., 2012.

    “A Real-Time Software Receiver for the GPS and Galileo L1 Signals” by B.M. Ledvina, M.L. Psiaki, T.E. Humphreys, S.P. Powell, and P.M. Kintner, Jr. in Proceedings of ION GNSS 2006, the 19th International Technical Meeting of The Institute of Navigation, Fort Worth, Texas, September 26–29, 2006, pp. 2321–2333.

  • Innovation: Getting at the Truth

    Innovation: Getting at the Truth

    A Civilian GPS Position Authentication System

    By Zhefeng Li and Demoz Gebre-Egziabher

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    MY UNIVERSITY, the University of New Brunswick, is one of the few institutes of higher learning still using Latin at its graduation exercises. The president and vice-chancellor of the university asks the members of the senate and board of governors present “Placetne vobis Senatores, placetne, Gubernatores, ut hi supplicatores admittantur?” (Is it your pleasure, Senators, is it your pleasure, Governors, that these supplicants be admitted?). In the Oxford tradition, a supplicant is a student who has qualified for their degree but who has not yet been admitted to it. Being a UNB senator, I was familiar with this usage of the word supplicant. But I was a little surprised when I first read a draft of the article in this month’s Innovation column with its use of the word supplicant to describe the status of a GPS receiver.

    If we look up the definition of supplicant in a dictionary, we find that it is “a person who makes a humble or earnest plea to another, especially to a person in power or authority.” Clearly, that describes our graduating students. But what has it got to do with a GPS receiver? Well, it seems that the word supplicant has been taken up by engineers developing protocols for computer communication networks and with a similar meaning. In this case, a supplicant (a computer or rather some part of its operating system) at one end of a secure local area network seeks authentication to join the network by submitting credentials to the authenticator on the other end. If authentication is successful, the computer is allowed to join the network. The concept of supplicant and authenticator is used, for example, in the IEEE 802.1X standard for port-based network access control.

    Which brings us to GPS. When a GPS receiver reports its position to a monitoring center using a radio signal of some kind, how do we know that the receiver or its associated communications unit is telling the truth? It’s not that difficult to generate false position reports and mislead the monitoring center into believing the receiver is located elsewhere — unless an authentication procedure is used. In this month’s column, we look at the development of a clever system that uses the concept of supplicant and authenticator to assess the truthfulness of position reports.

    “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. Contact him at lang @ unb.ca.

    This article deals with the problem of position authentication. The term “position authentication” as discussed in this article is taken to mean the process of checking whether position reports made by a remote user are truthful (Is the user where they say they are?) and accurate (In reality, how close is a remote user to the position they are reporting?). Position authentication will be indispensable to many envisioned civilian applications. For example, in the national airspace of the future, some traffic control services will be based on self-reported positions broadcast via ADS-B by each aircraft. Non-aviation applications where authentication will be required include tamper-free shipment tracking and smart-border systems to enhance cargo inspection procedures at commercial ports of entry. The discussions that follow are the outgrowth of an idea first presented by Sherman Lo and colleagues at Stanford University (see Further Reading).

    For illustrative purposes, we will focus on the terrestrial application of cargo tracking. Most of the commercial fleet and asset tracking systems available in the market today depend on a GPS receiver installed on the cargo or asset. The GPS receiver provides real-time location (and, optionally, velocity) information. The location and the time when the asset was at a particular location form the tracking message, which is sent back to a monitoring center to verify if the asset is traveling in an expected manner. This method of tracking is depicted graphically in FIGURE 1.

    FIGURE 1. A typical asset tracking system. Source: Richard Langley
    FIGURE 1. A typical asset tracking system.

    The approach shown in Figure 1 has at least two potential scenarios or fault modes, which can lead to erroneous tracking of the asset. The first scenario occurs when an incorrect position solution is calculated as a result of GPS RF signal abnormalities (such as GPS signal spoofing). The second scenario occurs when the correct position solution is calculated but the tracking message is tampered with during the transmission from the asset being tracked to the monitoring center. The first scenario is a falsification of the sensor and the second scenario is a falsification of the transmitted position report.

    The purpose of this article is to examine the problem of detecting sensor or report falsification at the monitoring center. We discuss an authentication system utilizing the white-noise-like spreading codes of GPS to calculate an authentic position based on a snapshot of raw IF signal from the receiver.

    Using White Noise as a Watermark

    The features for GPS position authentication should be very hard to reproduce and unique to different locations and time. In this case, the authentication process is reduced to detecting these features and checking if these features satisfy some time and space constraints. The features are similar to the well-designed watermarks used to detect counterfeit currency.

    A white-noise process that is superimposed on the GPS signal would be a perfect watermark signal in the sense that it is impossible reproduce and predict. FIGURE 2 is an abstraction that shows how the above idea of a superimposed white-noise process would work in the signal authentication problem. The system has one transmitter, Tx , and two receivers, Rs and Ra. Rs is the supplicant and Ra is the authenticator. The task of the authenticator is to determine whether the supplicant is using a signal from Tx or is being spoofed by a malicious transmitter, Tm. Ra is the trusted source, which gets a copy of the authentic signal, Vx(t) (that is, the signal transmitted by Tx). The snapshot signal, Vs(t), received at Rs is sent to the trusted agent to compare with the signal, Va(t), received at Ra. Every time a verification is performed, the snapshot signal from Rs is compared with a piece of the signal from Ra. If these two pieces of signal match, we can say the snapshot signal from Rs was truly transmitted from Tx. For the white-noise signal, match detection is accomplished via a cross-correlation operation (see Further Reading). The cross-correlation between one white-noise signal and any other signal is always zero. Only when the correlation is between the signal and its copy will the correlation have a non-zero value. So a non-zero correlation means a match. The time when the correlation peak occurs provides additional information about the distance between Ra and Rs.

    Unfortunately, generation of a white-noise watermark template based on a mathematical model is impossible. But, as we will see, there is an easy-to-use alternative.

    FIGURE 2. Architecture to detect a snapshot of a white-noise signal. Source: Richard Langley
    FIGURE 2. Architecture to detect a snapshot of a white-noise signal.

    An Intrinsic GPS Watermark

    The RF carrier broadcast by each GPS satellite is modulated by the coarse/acquisition (C/A) code, which is known and which can be processed by all users, and the encrypted P(Y) code, which can be decoded and used by Department of Defense (DoD) authorized users only. Both civilians and DoD-authorized users see the same signal. To commercial GPS receivers, the P(Y) code appears as uncorrelated noise. Thus, as discussed above, this noise can be used as a watermark, which uniquely encodes locations and times. In a typical civilian GPS receiver’s tracking loop, this watermark signal can be found inside the tracking loop quadrature signal.

    The position authentication approach discussed here is based on using the P(Y) signal to determine whether a user is utilizing an authentic GPS signal. This method uses a segment of noisy P(Y) signal collected by a trusted user (the authenticator) as a watermark template. Another user’s (the supplicant’s) GPS signal can be compared with the template signal to judge if the user’s position and time reports are authentic. Correlating the supplicant’s signal with the authenticator’s copy of the signal recorded yields a correlation peak, which serves as a watermark. An absent correlation peak means the GPS signal provided by the supplicant is not genuine. A correlation peak that occurs earlier or later than predicted (based on the supplicant’s reported position) indicates a false position report.

    System Architecture

    FIGURE 3 is a high-level architecture of our proposed position authentication system. In practice, we need a short snapshot of the raw GPS IF signal from the supplicant. This piece of the signal is the digitalized, down-converted, IF signal before the tracking loops of a generic GPS receiver. Another piece of information needed from the supplicant is the position solution and GPS Time calculated using only the C/A signal. The raw IF signal and the position message are transmitted to the authentication center by any data link (using a cell-phone data network, Wi-Fi, or other means).

    FIGURE 3. Architecture of position authentication system. Source: Richard Langley
    FIGURE 3. Architecture of position authentication system.

    The authentication station keeps track of all the common satellites seen by both the authenticator and the supplicant. Every common satellite’s watermark signal is then obtained from the authenticator’s tracking loop. These watermark signals are stored in a signal database. Meanwhile, the pseudorange between the authenticator and every satellite is also calculated and is stored in the same database.

    When the authentication station receives the data from the supplicant, it converts the raw IF signal into the quadrature (Q) channel signals. Then the supplicant’s Q channel signal is used to perform the cross-correlation with the watermark signal in the database. If the correlation peak is found at the expected time, the supplicant’s signal passes the signal-authentication test. By measuring the relative peak time of every common satellite, a position can be computed. The position authentication involves comparing the reported position of the supplicant to this calculated position. If the difference between two positions is within a pre-determined range, the reported position passes the position authentication.

    While in principle it is straightforward to do authentication as described above, in practice there are some challenges that need to be addressed. For example, when there is only one common satellite, the only common signal in the Q channel signals is this common satellite’s P(Y) signal. So the cross-correlation only has one peak. If there are two or more common satellites, the common signals in the Q channel signals include not only the P(Y) signals but also C/A signals. Then the cross-correlation result will have multiple peaks. We call this problem the C/A leakage problem, which will be addressed below.

    C/A Residual Filter

    The C/A signal energy in the GPS signal is about double the P(Y) signal energy. So the C/A false peaks are higher than the true peak. The C/A false peaks repeat every 1 millisecond. If the C/A false peaks occur, they are greater than the true peak in both number and strength. Because of background noise, it is hard to identify the true peak from the correlation result corrupted by the C/A residuals.

    To deal with this problem, a high-pass filter can be used. Alternatively, because the C/A code is known, a match filter can be designed to filter out any given GPS satellite’s C/A signal from the Q channel signal used for detection. However, this implies that one match filter is needed for every common satellite simultaneously in view of the authenticator and supplicant. This can be cumbersome and, thus, the filtering approach is pursued here.

    In the frequency domain, the energy of the base-band C/A signal is mainly (56 percent) within a ±1.023 MHz band, while the energy of the base-band P(Y) signal is spread over a wider band of ±10.23 MHz. A high-pass filter can be applied to Q channel signals to filter out the signal energy in the ±1.023 MHz band. In this way, all satellites’ C/A signal energy can be attenuated by one filter rather than using separate match filters for different satellites.

    FIGURE 4 is the frequency response of a high-pass filter designed to filter out the C/A signal energy. The spectrum of the C/A signal is also plotted in the figure. The high-pass filter only removes the main lobe of the C/A signals. Unfortunately, the high-pass filter also attenuates part of the P(Y) signal energy. This degrades the auto-correlation peak of the P(Y) signal. Even though the gain of the high-pass filter is the same for both the C/A and the P(Y) signals, this effect on their auto-correlation is different. That is because the percentage of the low-frequency energy of the C/A signal is much higher than that of the P(Y) signal. This, however, is not a significant drawback as it may appear initially. To see why this is so, note that the objective of the high-pass filter is to obtain the greatest false-peak rejection ratio defined to be the ratio between the peak value of P(Y) auto-correlation and that of the C/A auto-correlation. The false-peak rejection ratio of the non-filtered signals is 0.5. Therefore, all one has to do is adjust the cut-off frequency of the high-pass filter to achieve a desired false-peak rejection ratio.

    FIGURE 4. Frequency response of the notch filter. Source: Richard Langley
    FIGURE 4. Frequency response of the notch filter.

    The simulation results in FIGURE 5 show that one simple high-pass filter rather than multiple match filters can be designed to achieve an acceptable false-peak rejection ratio. The auto-correlation peak value of the filtered C/A signal and that of the filtered P(Y) signal is plotted in the figure. While the P(Y) signal is attenuated by about 25 percent, the C/A code signal is attenuated by 91.5 percent (the non-filtered C/A auto-correlation peak is 2). The false-peak rejection ratio is boosted from 0.5 to 4.36 by using the appropriate high-pass filter.

    FIGURE 5. Auto-correlation of the filtered C/A and P(Y) signals. Source: Richard Langley
    FIGURE 5. Auto-correlation of the filtered C/A and P(Y) signals.

    Position Calculation

    Consider the situation depicted in FIGURE 6 where the authenticator and the supplicant have multiple common satellites in view. In this case, not only can we perform the signal authentication but also obtain an estimate of the pseudorange information from the authentication. Thus, the authenticated pseudorange information can be further used to calculate the supplicant’s position if we have at least three estimates of pseudoranges between the supplicant and GPS satellites. Since this position solution of the supplicant is based on the P(Y) watermark signal rather than the supplicant’s C/A signal, it is an independent and authentic solution of the supplicant’s position. By comparing this authentic position with the reported position of the supplicant, we can authenticate the veracity of the supplicant’s reported GPS position.

    FIGURE 6. Positioning using a watermark signal. Source: Richard Langley
    FIGURE 6. Positioning using a watermark signal.

    The situation shown in Figure 6 is very similar to double-difference differential GPS. The major difference between what is shown in the figure and the traditional double difference is how the differential ranges are calculated. Figure 6 shows how the range information can be obtained during the signal authentication process. Let us assume that the authenticator and the supplicant have four common GPS satellites in view: SAT1, SAT2, SAT3, and SAT4. The signals transmitted from the satellites at time t are S1(t), S2(t), S3(t), and S4(t), respectively. Suppose a signal broadcast by SAT1 at time t0 arrives at the supplicant at t0 + ν1s where ν1s is the travel time of the signal. At the same time, signals from SAT2, SAT3, and SAT4 are received by the supplicant. Let us denote the travel time of these signals as ν2s, ν3s, and ν4s, respectively. These same signals will be also received at the authenticator. We will denote the travel times for the signals from satellite to authenticator as ν1a, ν2a, ν3a, and ν4a. The signal at a receiver’s antenna is the superposition of the signals from all the satellites. This is shown in FIGURE 7 where a snapshot of the signal received at the supplicant’s antenna at time t0 + ν1s includes GPS signals from SAT1, SAT2, SAT3, and SAT4. Note that even though the arrival times of these signals are the same, their transmit times (that is, the times they were broadcast from the satellites) are different because the ranges are different. The signals received at the supplicant will be S1(t0), S2(t0 + ν1s – ν2s), S3(t0 + ν1s – ν3s), and S4(t0 + ν1s – ν4s). This same snapshot of the signals at the supplicant is used to detect the matched watermark signals from SAT1, SAT2, SAT3, and SAT4 at the authenticator. Thus the correlation peaks between the supplicant’s and the authenticator’s signal should occur at t0 + ν1a, t0 + ν1s – ν2s + ν2a, t0 + ν1s – ν3s + ν3a, and t0 + ν1s – ν4s + ν4a.

    Referring to Figure 6 again, suppose the authenticator’s position (xa, ya, za) is known but the supplicant’s position (xs, ys, zs) is unknown and needs to be determined. Because the actual ith common satellite (xi , yi , zi ) is also known to the authenticator, each of the ρia, the pseudorange between the ith satellite and the authenticator, is known. If ρis is the pseudorange to the ith satellite measured at the supplicant, the pseudoranges and the time difference satisfies equation (1):

    ρ2s – ρ1s= ρ2a – ρ1a – ct21 + cχ21      (1)

    where χ21 is the differential range error primarily due to tropospheric and ionospheric delays. In addition, c is the speed of light, and t21 is the measured time difference as shown in Figure 7. Finally, ρis for i = 1, 2, 3, 4 is given by:

    I-Eq-2 Source: Richard Langley  (2)

    FIGURE 7. Relative time delays constrained by positions. Source: Richard Langley
    FIGURE 7. Relative time delays constrained by positions.

    If more than four common satellites are in view between the supplicant and authenticator, equation (1) can be used to form a system of equations in three unknowns. The unknowns are the components of the supplicant’s position vector rs = [xs, ys, zs]T. This equation can be linearized and then solved using least-squares techniques. When linearized, the equations have the following form:

    Aδrs= δm       (3)

    where δrs = [δxs,δys,δzs]T, which is the estimation error of the supplicant’s position. The matrix A is given by

    I-MatrixA Source: Richard Langley

    where I-ei is the line of sight vector from the supplicant to the ith satellite. Finally, the vector δm is given by:

    I-Eq-4 Source: Richard Langley(4)

    where δri is the ith satellite’s position error, δρia is the measurement error of pseudorange ρia or pseudorange noise. In addition, δtij is the time difference error. Finally, δχij is the error of χij defined earlier.

    Equation (3) is in a standard form that can be solved by a weighted least-squares method. The solution is

    δrs = ( AT R-1 A)-1 AT R-1δm     (5)

    where R is the covariance matrix of the measurement error vector δm. From equations (3) and (5), we can see that the supplicant’s position accuracy depends on both the geometry and the measurement errors.

    Hardware and Software

    In what follows, we describe an authenticator which is designed to capture the GPS raw signals and to test the performance of the authentication method described above. Since we are relying on the P(Y) signal for authentication, the GPS receivers used must have an RF front end with at least a 20-MHz bandwidth. Furthermore, they must be coupled with a GPS antenna with a similar bandwidth. The RF front end must also have low noise. This is because the authentication method uses a noisy piece of the P(Y) signal at the authenticator as a template to detect if that P(Y) piece exists in the supplicant’s raw IF signal. Thus, the detection is very sensitive to the noise in both the authenticator and the supplicant signals. Finally, the sampling of the down-converted and digitized RF signal must be done at a high rate because the positioning accuracy depends on the accuracy of the pseudorange reconstructed by the authenticator. The pseudorange is calculated from the time-difference measurement. The accuracy of this time difference depends on the sampling frequency to digitize the IF signal. The high sampling frequency means high data bandwidth after the sampling.

    The authenticator designed for this work and shown in FIGURE 8 satisfies the above requirements. A block diagram of the authenticator is shown in Figure 8a and the constructed unit in Figure 8b. The IF signal processing unit in the authenticator is based on the USRP N210 software-defined radio. It offers the function of down converting, digitalization, and data transmission. The firmware and field-programmable-gate-array configuration in the USRP N210 are modified to integrate a software automatic gain control and to increase the data transmission efficiency. The sampling frequency is 100 MHz and the effective resolution of the analog-to-digital conversion is 6 bits. The authenticator is battery powered and can operate for up to four hours at full load.

    FIGURE 8a. Block diagram of GPS position authenticator. Source: Richard Langley
    FIGURE 8a. Block diagram of GPS position authenticator.

    Performance Validation

    Next, we present results demonstrating the performance of the authenticator described above. First, we present results that show we can successfully deal with the C/A leakage problem using the simple high-pass filter. We do this by performing a correlation between snapshots of signal collected from the authenticator and a second USRP N210 software-defined radio. FIGURE 9a is the correlation result without the high-pass filter. The periodic peaks in the result have a period of 1 millisecond and are a graphic representation of the C/A leakage problem. Because of noise, these peaks do not have the same amplitude. FIGURE 9b shows the correlation result using the same data snapshot as in Figure 9a. The difference is that Figure 9b uses the high-pass filter to attenuate the false peaks caused by the C/A signal residual. Only one peak appears in this result as expected and, thus, confirms the analysis given earlier.

    FIGURE 9a. Example of cross-correlation detection results without high-pass filter. Source: Richard Langley
    FIGURE 9a. Example of cross-correlation detection results without high-pass filter.
    FIGURE 9b. Example of cross-correlation with high-pass filter. Source: Richard Langley
    FIGURE 9b. Example of cross-correlation with high-pass filter.

    We performed an experiment to validate the authentication performance. In this experiment, the authenticator and the supplicant were separated by about 1 mile (about 1.6 kilometers). The location of the authenticator was fixed. The supplicant was then sequentially placed at five points along a straight line. The distance between two adjacent points is about 15 meters. The supplicant was in an open area with no tall buildings or structures. Therefore, a sufficient number of satellites were in view and multipath, if any, was minimal. The locations of the five test points are shown in FIGURE 10.

    FIGURE 10. Five-point field test. Image courtesy of Google. Source: Richard Langley
    FIGURE 10. Five-point field test. Image courtesy of Google.

    The first step of this test was to place the supplicant at point A and collect a 40-millisecond snippet of data. This data was then processed by the authenticator to determine if:

    • The signal contained the watermark. We call this the “signal authentication test.” It determines whether a genuine GPS signal is being used to form the supplicant’s position report.
    • The supplicant is actually at the position coordinates that they say they are. We call this the “position authentication test.” It determines whether or not falsification of the position report is being attempted.

    Next, the supplicant was moved to point B. However, in this instance, the supplicant reports that it is still located at point A. That is, it makes a false position report. This is repeated for the remaining positions (C through E) where at each point the supplicant reports that it is located at point A. That is, the supplicant continues to make false position reports.

    In this experiment, we have five common satellites between the supplicant (at all of the test points A to E) and the authenticator. The results of the experiment are summarized in TABLE 1. If we can detect a strong peak for every common satellite, we say this point passes the signal authentication test (and note “Yes” in second column of Table 1). That means the supplicant’s raw IF signal has the watermark signal from every common satellite. Next, we perform the position authentication test. This test tries to determine whether the supplicant is at the position it claims to be. If we determine that the position of the supplicant is inconsistent with its reported position, we say that the supplicant has failed the position authentication test. In this case we put a “No” in the third column of Table 1. As we can see from Table 1, the performance of the authenticator is consistent with the test setup. That is, even though the wrong positions of points (B, C, D, E) are reported, the authenticator can detect the inconsistency between the reported position and the raw IF data. Furthermore, since the distance between two adjacent points is 15 meters, this implies that resolution of the position authentication is at or better than 15 meters. While we have not tested it, based on the timing resolution used in the system, we believe resolutions better than 12 meters are achievable.

    Table 1. Five-point position authentication results. Source: Richard Langley
    Table 1. Five-point position authentication results.

    Conclusion

    In this article, we have described a GPS position authentication system. The authentication system has many potential applications where high credibility of a position report is required, such as cargo and asset tracking. The system detects a specific watermark signal in the broadcast GPS signal to judge if a receiver is using the authentic GPS signal. The differences between the watermark signal travel times are constrained by the positions of the GPS satellites and the receiver. A method to calculate an authentic position using this constraint is discussed and is the basis for the position authentication function of the system. A hardware platform that accomplishes this was developed using a software-defined radio. Experimental results demonstrate that this authentication methodology is sound and has a resolution of better than 15 meters. This method can also be used with other GNSS systems provided that watermark signals can be found. For example, in the Galileo system, the encrypted Public Regulated Service signal is a candidate for a watermark signal.

    In closing, we note that before any system such as ours is fielded, its performance with respect to metrics such as false alarm rates (How often do we flag an authentic position report as false?) and missed detection probabilities (How often do we fail to detect false position reports?) must be quantified. Thus, more analysis and experimental validation is required.

    Acknowledgments

    The authors acknowledge the United States Department of Homeland Security (DHS) for supporting the work reported in this article through the National Center for Border Security and Immigration under grant number 2008-ST-061-BS0002. However, any opinions, findings, conclusions or recommendations in this article are those of the authors and do not necessarily reflect views of the DHS. This article is based on the paper “Performance Analysis of a Civilian GPS Position Authentication System” presented at PLANS 2012, the Institute of Electrical and Electronics Engineers / Institute of Navigation Position, Location and Navigation Symposium held in Myrtle Beach, South Carolina, April 23–26, 2012.

    Manufacturers

    The GPS position authenticator uses an Ettus Research LLC model USRP N210 software-defined radio with a DBSRX2 RF daughterboard.

    Zhefeng Li is a Ph.D. candidate in the Department of Aerospace Engineering and Mechanics at the University of Minnesota, Twin Cities. His research interests include GPS signal processing, real-time implementation of signal processing algorithms, and the authentication methods for civilian GNSS systems.

    Demoz Gebre-Egziabher is an associate professor in the Department of Aerospace Engineering and Mechanics at the University of Minnesota, Twin Cities. His research deals with the design of multi-sensor navigation and attitude determination systems for aerospace vehicles ranging from small unmanned aerial vehicles to Earth-orbiting satellites.

    FURTHER READING

    • Authors’ Proceedings Paper

    “Performance Analysis of a Civilian GPS Position Authentication System” by Z. Li and D. Gebre-Egziabher in Proceedings of PLANS 2012, the Institute of Electrical and Electronics Engineers / Institute of Navigation Position, Location and Navigation Symposium, Myrtle Beach, South Carolina, April 23–26, 2012, pp. 1028–1041.

    • Previous Work on GNSS Signal and Position Authentication

    “Signal Authentication in Trusted Satellite Navigation Receivers” by M.G. Kuhn in Towards Hardware-Intrinsic Security edited by A.-R. Sadeghi and D. Naccache, Springer, Heidelberg, 2010.

    “Signal Authentication: A Secure Civil GNSS for Today” by S. Lo, D. D. Lorenzo, P. Enge, D. Akos, and P. Bradley in Inside GNSS, Vol. 4, No. 5, September/October 2009, pp. 30–39.

    “Location Assurance” by L. Scott in GPS World, Vol. 18, No. 7, July 2007, pp. 14–18.

    “Location Assistance Commentary” by T.A. Stansell in GPS World, Vol. 18, No. 7, July 2007, p. 19.

    • Autocorrelation and Cross-correlation of Periodic Sequences

    “Crosscorrelation Properties of Pseudorandom and Related Sequences” by D.V. Sarwate and M.B. Pursley in Proceedings of the IEEE, Vol. 68, No. 5, May 1980, pp. 593–619, doi: 10.1109/PROC.1980.11697. Corrigendum: “Correction to ‘Crosscorrelation Properties of Pseudorandom and Related  Sequences’” by D.V. Sarwate and M.B. Pursley in Proceedings of the IEEE, Vol. 68, No. 12, December 1980, p. 1554, doi: 10.1109/PROC.1980.11910.

    • Software-Defined Radio for GNSS

    “Software GNSS Receiver: An Answer for Precise Positioning Research” by T. Pany, N. Falk, B. Riedl, T. Hartmann, G. Stangle, and C. Stöber in GPS World, Vol. 23, No. 9, September 2012, pp. 60–66.

    Digital Satellite Navigation and Geophysics: A Practical Guide with GNSS Signal Simulator and Receiver Laboratory by I.G. Petrovski and T. Tsujii with foreword by R.B. Langley, published by Cambridge University Press, Cambridge, U.K., 2012.

    “Simulating GPS Signals: It Doesn’t Have to Be Expensive” by A. Brown, J. Redd, and M.-A. Hutton in GPS World, Vol. 23, No. 5, May 2012, pp. 44–50.

    A Software-Defined GPS and Galileo Receiver: A Single-Frequency Approach by K. Borre, D.M. Akos, N. Bertelsen, P. Rinder, and S.H. Jensen, published by Birkhäuser, Boston, 2007.

  • Innovation: Getting Along

    Innovation: Getting Along

    Collaborative Navigation in Transitional Environments

    By Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    COLLABORATION,  n. /kəˌlæbəˈreɪʃən/, n. of action. United labour, co-operation; esp. in literary, artistic, or scientific work — according to the Oxford English Dictionary. Collaboration is something we all practice, knowingly or unknowingly, even in our everyday lives. It generally results in a more productive outcome than acting individually. In scientific and engineering circles, collaboration in research is extremely common with most published papers having multiple authors, for example.

    The term collaboration can be applied not only to the endeavors of human beings or other living creatures but also to inanimate objects, too. Researchers have developed systems of miniaturized robots and unmanned vehicles that operate collaboratively to complete a task. These platforms must navigate as part of their functions and this navigation can often be made more continuous and accurate if each individual platform navigates collaboratively in the group rather than autonomously. This is typically achieved by exchanging sensor measurements by some kind of short-range wireless technology such as Wi-Fi, ultra-wide band, or ZigBee, a suite of communication protocols for small, low-power digital radios based on an Institute of Electrical and Electronics Engineers’ standard for personal area networks.

    A wide variety of navigation sensors can be implemented for collaborative navigation depending on whether the system is designed by outdoor use, for use inside buildings, or for operations in a wide variety of environments. In addition to GPS and other global navigation satellite systems, inertial measurement units, terrestrial radio-based navigation systems, laser and acoustic ranging, and image-based systems can be used.

    In this month’s article, a team of researchers at The Ohio State University discusses a system under development for collaborative navigation in transitional environments — environments in which GPS alone is insufficient for continuous and accurate navigation. Their prototype system involves a land-based deployment vehicle and a human operator carrying a personal navigator sensor assembly, which initially navigate together before the personal navigator transitions to an indoor environment. This system will have multiple applications including helping first responders to emergencies. Read on.

    “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, see the “Contributing Editors” section on page 6.

    Collaborative navigation is an emerging field where a group of users navigates together by exchanging navigation and inter-user ranging information. This concept has been considered a viable alternative for GPS-challenged environments. However, most of the developed systems and approaches are based on fixed types and numbers of sensors per user or platform (restricted in sensor configuration) that eventually leads to a limitation in navigation capability, particularly in mixed or transition environments.

    As an example of an applicable scenario, consider an emergency crew navigating initially in a deployment vehicle, and, when subsequently dispatched, continuing in collaborative mode, referring to the navigation solution of the other users and vehicles. This approach is designed to assure continuous navigation solution of distributed agents in transition environments, such as moving between open areas, partially obstructed areas, and indoors when different types of users need to maintain high-accuracy navigation capability in relative and absolute terms.

    At The Ohio State University (OSU), we have developed systems that use multiple sensors and communications technologies to investigate, experimentally, the viability and performance attributes of such collaborative navigation. For our experiments, two platforms, a land-based deployment vehicle and a human operator carrying a personal navigator (PN) sensor assembly, initially navigate together before the PN transitions to the indoor environment.

    In the article, we describe the concept of collaborative navigation, briefly describe the systems we have developed and the algorithms used, and report on the results of some of our tests. The focus of the study being reported here is on the environment-to-environment transition and indoor navigation based on 3D sensor imagery, initially in post-processing mode with a plan to transition to real time.

    The Concept

    Collaborative navigation, also referred to as cooperative navigation or positioning, is a localization technique emerging from the field of wireless sensor networks (WSNs). Typically, the nodes in a WSN can communicate with each other using wireless communications technology based on standards, such as Zigbee/IEEE 802.15.4. The communication signals in a WSN are used to derive the inter-nodal distances across the network. Then, the collaborative navigation solution is formed by integrating the inter-nodal range measurements among nodes (users) in the network using a centralized or decentralized Kalman filter, or a least-squares-based approach.

    A paradigm shift from single to multi-sensor to multi-platform navigation is illustrated conceptually in Figure 1. While conventional sensor integration and integrated sensor systems are commonplace in navigation, sensor networks of integrated sensor systems are a relatively new development in navigation. Figure 2 illustrates the concept of collaborative navigation with emphasis on transitions between varying environments. In actual applications, example networks include those formed by soldiers, emergency crews, and formations of robots or unmanned vehicles, with the primary objective of achieving a sustained level of sufficient navigation accuracy in GPS-denied environments and assuring seamless transition among sensors, platforms, and environments.

    Source: Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak
    Figure 1. Paradigm shift in sensor integration concept for navigation.
    Source: Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak
    Figure 2. Collaborative navigation and transition between varying environments.

    Field Experiments and Methodology

    A series of field experiments were carried out in the fall of 2011 at The Ohio State University (OSU), and in the spring of 2012 at the Nottingham Geospatial Institute of the University of Nottingham, using the updated prototype of the personal navigator developed earlier at the OSU Satellite Positioning and Inertial Navigation Laboratory, and land-based multisensory vehicles. Note that the PN prototype is not a miniaturized system, but rather a sensor assembly put together using commercial off-the-shelf components for demonstration purposes only.

    The GPSVan (see Figure 3), the OSU mobile research navigation and mapping platform, and the recently upgraded OSU PN prototype (see Figure 4) jointly performed a variety of maneuvers, collecting data from multiple GPS receivers, inertial measurement units (IMUs), imaging sensors, and other devices. Parts of the collected data sets have been used for demonstrating the performance of navigation indoors and in the transition between environments, and it is this aspect of our experiments that will be discussed in the present article.

    Source: Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak
    Figure 3. Land vehicle, OSU GPSVan.
    Source: Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak
    Figure 4. Personal navigator sensor assembly.

    The GPSVan was equipped with navigation, tactical, and microelectromechanical systems (MEMS)-grade IMUs, installed in a two-level rigid metal cage, and the signals from two GPS antennas, mounted on the roof, were shared among multiple geodetic-grade dual-frequency GPS receivers. In addition, odometer data were logged, and optical imagery was acquired in some of the tests.

    The first PN prototype system, developed in 2006–2007, used GPS, IMU, a digital barometer, a magnetometer compass, a human locomotion model, and 3D active imaging sensor, Flash LIDAR (an imaging light detection and ranging system using rapid laser pulses for subject illumination). Recently, the design was upgraded to include 2D/3D imaging sensors to provide better position and attitude estimates indoors, and to facilitate transition between outdoor and indoor environments. Consequently, the current configuration allows for better distance estimation among platforms, both indoors and outdoors, as well as improving the navigation and tracking performance in general.

    The test area where data were acquired to support this study, shown in Figure 5, includes an open parking lot, moderately vegetated passages, a narrow alley between buildings, and a one-storey building for indoor navigation testing. The three typical scenarios used were:
    1)    Sensor/platform calibration: GPSVan and PN are connected and navigate together.
    2)    Both platforms moved closely together, that is, the GPSVan followed the PN’s trajectory.
    3)    Both platforms moved independently.

    Source: Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak

    Image-Based Navigation

    The sensor of interest for the study reported here is an image sensor that actually includes two distinct data streams: a standard intensity image and a 3D ranging image, see Figure 6. The unit consists primarily of a 640 × 480 pixel array of infrared detectors. The operational range of the sensor is 0.8–10 meters, with a range resolution of 1 centimeter at a 2-meter distance.

    Source: Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak
    Figure 6. PN captured 3D image sequence from inside the building.

    In this study, the image-based navigation (no IMU) was considered. To overcome this limitation, the intensity images acquired simultaneously with the range data by the unit were leveraged to provide crucial information. The two intensity images were processed utilizing the Scale Invariant Feature Transform (SIFT) algorithm to identify matching features between the pair of 2D intensity images.

    The SIFT algorithm has been primarily applied to 1D and 2D imagery to date; the authors are not aware of any research efforts to apply SIFT to 3D datasets for the expressed purpose of positioning. Analysis at our laboratory supported well-published results regarding the exceptional performance of SIFT with respect to both repeatability and extraction of the feature content. The algorithm is remarkably robust to most image corruption schema, although white noise above 5 percent does appear to be the primary weakness of the algorithm. The algorithm suffers in three critical areas with respect to providing a 3D positioning solution. First, the algorithm is difficult to scale in terms of the number of descriptive points; that is, the algorithm quickly becomes computationally intractable for a large number (>5,000) of pixels. Secondly, the matching process is not unique; it is exceptionally feasible for the algorithm to match a single point in one image to multiple points in another image. Finally, since the algorithm loses spatial positioning capabilities to achieve the repeatability, the ability to utilize matching features for triangulation or trilateration becomes impaired. Owing to the noted issues, SIFT was not found to be a suitable methodology for real-time positioning based on 3D Flash LIDAR datasets.

    Despite these drawbacks, the intensity images offer the only available sensor input beyond the 3D ranging image. As such, the SIFT methodology provides what we believe to be a “best in class” algorithmic approach for matching 2D intensity images. The necessity of leveraging the intensity images will be apparent shortly, as the schema for deriving platform position is explained.

    The algorithm has been developed and implemented by the second author (see Further Reading for details). The algorithm utilizes eigenvector “signatures” for point features as a means to facilitate matching. The algorithm is comprised of four steps:
    1)    Segmentation
    2)    Coordinate frame transformation
    3)    Feature matching
    4)    Position and orientation determination.

    The algorithm utilizes the eigenvector descriptors to merge points likely to belong to a surface and identify the pixels corresponding to transitions between surfaces. Utilizing an initial coarse estimate from the IMU system, the results from the previous frame are transformed into the current coordinate reference frame by means of a Random Sampling Consensus or RANSAC methodology. Matching of static transitional pixels is accomplished by comparing eigenvector “signatures” within a constrained search window. Once matching features are identified and determined to be static, the closed form quaternion solution is utilized to derive the position and orientation of the acquisition device, and the result updates the inertial system in the same manner as a GPS receiver within the common GPS/IMU integration. The algorithm is unique in that the threshold mechanisms at each step are derived from the data itself, rather than relying upon a-priori limits. Since the algorithm only utilizes transitional pixels for matching, a significant reduction in dimensionality is generally accomplished and facilitates implementation on larger data frames.

    The key point in this overview is the need to provide coarse positioning information to the 3D matching algorithm to constrain the search space for matching eigenvector signatures. Since the IMU data were not available, the matching SIFT features from the intensity images were correlated with the associated range pixel measurements, and these range measurements were utilized in Horn’s Method (see Further Reading) to provide the coarse adjustment between consecutive range image frames. The 3D-range-matching algorithm described above then proceeds normally.

    The use of SIFT to provide the initial matching between the images entails the acceptance of several critical issues, beyond the limitations previously discussed. First, since the SIFT algorithm is matching 2D features on the intensity image; there is no guarantee that the matched features represent static elements in the field of view. As an example, SIFT can easily “match” the logo on a shirt worn by a moving person; since the input data will include the position of non-static elements, the resulting coarse adjustment may possess very large biases (in position). If these biases are significant, constraining the search space may be infeasible, resulting in either the inability to generate eigenvector matches (worst case) or a longer search time (best case). Since the 3D-range-matching algorithm checks the two range images for consistency before the matching process begins, this can be largely mitigated in implementation. Secondly, the SIFT features are located with sub-pixel location, thus the correlation to the range pixel image will inherently possess an error of ± 1 pixel (row and column). The impact of this error is that range pixels utilized to facilitate the coarse adjustment may in fact not be correct; the correct range pixel to be matched may not be the one selected. This will result in larger errors during the initial (coarse) adjustment process. Third, the uncertainty of the coarse adjustment is not known, so a-priori estimates of the error ellipse must be made to establish the eigenvector search space. The size and extent of these error ellipses is not defined on-the-fly by the data, which reduces one of the key elements of the 3D matching algorithm. Fourth, the limited range of the image sensor results in a condition where intensity features have no associated range measurement (the feature is out of range for the range device). This reduces the effective use of SIFT features for coarse alignment. However, using the intensity images does demonstrate the ability of the 3D-range-matching algorithm to generically utilize coarse adjustment information and refine the result to provide a navigation solution.

    Data Analysis

    In the experiment selected for discussion in this article, initially, the PN was initially riding in the GPSVan. After completing several loops in the parking lot (the upper portion of Figure 5), the PN then departed the vehicle and entered the building (see Figure 7), exited the facility, completed a trajectory around the second building (denoted as “mixed area” in Figure 5), and then returned to the parking lot.

    Source: Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak
    Figure 7. Building used as part of the test trajectory for indoor and transition environment testing; yellow line: nominal personal navigator indoor trajectories; arrows: direction of personal navigator motion inside the building; insert: reconstructed trajectory section, based on 3D image-based navigation.

    While minor GPS outages can occur under the canopy of trees, the critical portion of the trajectory is the portion occurring inside the building since the PN platform will be unable to access the GPS signal during this portion of the trajectory. Our efforts are therefore focused on providing alternative methods for positioning to bridge this critical gap.

    Utilizing the combined intensity images (for coarse adjustment via SIFT) and the 3D ranging data, a trajectory was derived for travel inside the building at the OSU Supercomputing Facility. There is a finite interval between exiting the building and recovery of GPS signal lock during which the range acquisition was not available; thus the total extent of travel distance during GPS signal outage is not precisely identical to the travel distance where 3D range solutions were utilized for positioning. We estimate the distance from recovery of GPS signals to the last known 3D ranging-derived position to be approximately 3 meters. Based upon this estimate, the travel distance inside the building should be approximately 53.5 meters (forward), 9.5 meters (right), and 0.75 meters (vertical). Based upon these estimates, the total misclosure based upon 3D range-derived positions is provided in Table 1. The asterisk in the third row indicates the estimated nature of these values.

    Source: Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak
    Table 1. Approximate positional results for the OSU Supercomputing Facility trajectory.

    The average positional uncertainty reflects the relative, frame-to-frame error reported by the algorithm during the indoor trajectory. This includes both IMU and 3D ranging solutions. The primary reason for the rather large misclosure in the forward and vertical directions is the result of three distinct issues. First, the image ranging sensor has a limited range; during certain portions of the trajectory the sensor is nearly “blind” due to lack of measurable features within the range. During this period, the algorithm must default to the IMU data, which is known to be suspect, as previously discussed. Secondly, the correlation between SIFT features and range measurement pixels can induce errors, as discussed above. Third, the 3D range positions and the IMU data were not integrated in this demonstration; the range positions were used to substitute for the lost GPS signals and the IMU was drifting. Resolving this final issue would, at a minimum, reduce the IMU drift error and improve the overall solution.

    A follow-up study conducted at a different facility was completed using the same platform and methodology. In this study, a complete traverse was completed indoors forming a “box” or square trajectory, which returned to the original entrance point. A plot of the trajectory results is provided in Figure 8. The misclosure is less than four meters with respect to both the forward (z) and right (x) directions. While similar issues exist with IMU drift (owing to lack of tight integration with the ranging data), a number of problems between the SIFT feature/range pixel correlation portion of the algorithm are evident; note the large “clumps’ of data points, where the algorithm struggles to reconcile the motions reported by the coarse (SIFT-derived) position and the range-derived position.

    Source: Dorota A. Grejner-Brzezinska, J.N. (Nikki) Markiel, Charles K. Toth and Andrew Zaydak
    Figure 8. Indoor scenario: square (box) trajectory.

    Conclusions

    As demonstrated in this paper, the determination of position based upon 3D range measurements can be seen to have particular potential benefit for the problem of navigation during periods of operation in GPS-denied environments. The experiment demonstrates several salient points of use in our ongoing research activities. First, the effective measurement range of the sensor is paramount; the trivial (but essential) need to acquire data is critical to success. A major problem was the presence of matching SIFT features but no corresponding range measurement. Second, orientation information is just as critical as position; the lack of this information significantly extended the time required to match features (via eigenvector signatures). Third, there is a critical need for the sensor to scan not only forward (along the trajectory) but also right/left and up/down. Obtaining features in all axes would support efforts to minimize IMU drift, particularly in the vertical. Alternatively, a wider field of view could conceivably accomplish the same objective. Finally, the algorithm was not fully integrated as a substitute for GPS positioning and the IMU was free to drift. Since the 3D ranging algorithm cannot guarantee a solution for all epochs, accurate IMU positioning is critical to bridge these outages. Fully integrating the 3D ranging solution with a GPS/IMU/3D schema would significantly reduce positional errors and misclosure.

    Our study indicates that leveraging 3D ranging images to achieve indoor relative (frame-to-frame) positioning shows great promise. The utilization of SIFT to match intensity images was an unfortunate necessity dictated by data availability; the method is technically feasible but our efforts would suggest there are significant drawbacks to this application, both in terms of efficiency and positional accuracy. It would be better to use IMU data with orientation solutions to derive the best possible solution. Our next step is the full integration within the IMU to enable 3D ranging solutions to update the ongoing trajectory, which we believe will reduce the misclosure and provide enhanced solutions supporting autonomous (or semi-autonomous) navigation.

    Acknowledgments

    This article is based on the paper “Cooperative Navigation in Transitional Environments,” presented at presented at PLANS 2012, the Institute of Electrical and Electronics Engineers / Institute of Navigation Position, Location and Navigation Symposium held in Myrtle Beach, South Carolina, April 23–26, 2012.

    Manufacturers

    The equipment used for the experiments discussed in this article included a NovAtel Inc. SPAN system consisting of a NovAtel OEMV GPScard, a Honeywell International Inc. HG1700 Ring Laser Gyro IMU, a Microsoft Xbox Kinect 3D imaging sensor, and a Casio Computer Co., Ltd. Exilim EX-H20G Hybrid-GPS digital camera.

    DOROTA GREJNER-BRZEZINSKA is a professor and leads the Satellite Positioning and Inertial Navigation (SPIN) Laboratory at OSU, where she received her M.S. and Ph.D. degrees in geodetic science.

    J.N. (NIKKI) MARKIEL is a lead geophysical scientist at the National Geospatial-Intelligence Agency. She obtained her Ph.D. in geodetic engineering at OSU.

    CHARLES TOTH is a senior research scientist at OSU’s Center for Mapping. He received a Ph.D. in electrical engineering and geoinformation sciences from the Technical University of Budapest, Hungary.

    ANDREW ZAYDAK is a Ph.D. candidate in geodetic engineering at OSU.

    FURTHER READING

    ◾ The Concept of Collaborative Navigation

    “The Network-based Collaborative Navigation for Land Vehicle Applications in GPS-denied Environment” by J-K. Lee, D.A. Grejner-Brzezinska and C. Toth in the Royal Institute of Navigation Journal of Navigation; in press.

    “Positioning and Navigation in GPS-challenged Environments: Cooperative Navigation Concept” by D.A. Grejner-Brzezinska, J-K. Lee and C. K. Toth, presented at FIG Working Week 2011, Marrakech, Morocco,  May 18-22, 2011.

    “Network-Based Collaborative Navigation for Ground-Based Users in GPS-Challenged Environments” by J-K. Lee, D. Grejner-Brzezinska, and C.K. Toth in Proceedings of ION GNSS 2010, the 23rd International Technical Meeting of the Satellite Division of The Institute of Navigation, Portland, Oregon, September 21-24, 2010, pp. 3380-3387.

    ◾ Sensors Supporting Collaborative Navigation

    “Challenged Positions: Dynamic Sensor Network, Distributed GPS Aperture, and Inter-nodal Ranging Signals” by D.A. Grejner-Brzezinska, C.K. Toth, J. Gupta, L. Lei, and X. Wang in GPS World, Vol. 21, No. 9, September 2010, pp. 35-42.

    “Positioning in GPS-challenged Environments: Dynamic Sensor Network with Distributed GPS Aperture and Inter-nodal Ranging Signals” by D.A. Grejner-Brzezinska, C. K. Toth, L. Li, J. Park, X. Wang, H. Sun, I.J. Gupta, K. Huggins and Y. F. Zheng (2009): in Proceedings of ION GNSS 2009, the 22nd International Technical Meeting of the Satellite Division of The Institute of Navigation, Savannah, Georgia, September 22-25, 2009, pp. 111–123.

    “Separation of Static and Non-Static Features from Three Dimensional Datasets: Supporting Positional Location in GPS Challenged Environments – An Update” by J.N. Markiel, D. Grejner-Brzezinska, and C. Toth in Proceedings of ION GNSS 2007, the 20th International Technical Meeting of the Satellite Division of The Institute of Navigation, Fort Worth, Texas, September 25-28, 2007, pp. 60-69.

    ◾ Personal Navigation

    “Personal Navigation: Extending Mobile Mapping Technologies Into Indoor Environments” by D. Grejner-Brzezinska, C. Toth, J. Markiel, and S. Moafipoor in Boletim De Ciencias Geodesicas, Vol. 15, No. 5, 2010, pp. 790-806.

    “A Fuzzy Dead Reckoning Algorithm for a Personal Navigator” by S. Moafipoor, D.A. Grejner-Brzezinska, and C.K. Toth, in Navigation, Vol. 55, No. 4, Winter 2008, pp. 241-254.

    “Quality Assurance/Quality Control Analysis of Dead Reckoning Parameters in a Personal Navigator” by S. Moafipoor, D. Grejner-Brzezinska, C.K. Toth, and C. Rizos in Location Based Services & TeleCartography II: From Sensor Fusion to Context Models, G. Gartner and K. Rehrl (Eds.), Lecture Notes in Geoinformation & Cartography, Springer-Verlag, Berlin and Heidelberg, 2008, pp. 333-351.

    “Pedestrian Tracking and Navigation Using Adaptive Knowledge System Based on Neural Networks and Fuzzy Logic” by S. Moafipoor, D. Grejner-Brzezinska, C.K. Toth, and C. Rizos in Journal of Applied Geodesy, Vol. 1, No. 3, 2008, pp. 111-123.

    ◾ Horn’s Method

    “Closed-form Solution of Absolute Orientation Using Unit Quaternions” by B.K.P. Horn in Journal of the Optical Society of America, Vol. 4, No. 4, April 1987, p. 629-642.

  • Innovation: Easy Peasy, Lemon Squeezy

    Innovation: Easy Peasy, Lemon Squeezy

    Satellite Navigation Using Doppler and Partial Pseudorange Measurements

    By Nicholas Othieno and Scott Gleason

    GPS World photo
    INNOVATION INSIGHTS by Richard Langley

    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.

    Credit: Nicholas Othieno and Scott Gleason
    FIGURE 1. A Doppler/time-free GNSS receiver block diagram.

    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.

    Credit: Nicholas Othieno and Scott Gleason
    FIGURE 2. Illustration of the isolines of constant Doppler for one and two GNSS satellites. Sv and Uv are the satellite and receiver velocity vectors, respectively. ϴ is the angle between the velocity difference vector and the vector pointing from the satellite to the receiver. The figure on the right shows the intersection of Doppler ellipses for the two satellites.

    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.

    Nicholas Othieno and Scott Gleason
    FIGURE 3. Doppler position estimation with off-air signals. East-north position for a stationary receiver at 18:04 UTC, October 28, 2010.

    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.

    Nicholas Othieno and Scott Gleason
    FIGURE 4. Doppler positioning solution error for a receiver with increasing velocity moving southwards at 09:16 UTC, April 19, 2011.

    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.

    Nicholas Othieno and Scott Gleason
    FIGURE 5. Monte-Carlo simulation results for time-free failure cases over a range of a priori position and time errors.

    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.

    Nicholas Othieno and Scott Gleason
    FIGURE 6. Processing stages in time-free positioning initialized by Doppler positioning.

    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.

    Nicholas Othieno and Scott Gleason

    TABLE 1. Root-mean-square (R.M.S.) error and geometrical dilution of precision (GDOP) for off-air GPS data sets used with the fastGPS software receiver.

    Table 1. Root-mean-square (R.M.S.) error and geometrical dilution of precision (GDOP) for off-air GPS data sets used with the fastGPS software receiver.

    Figure 7 shows the performance for the combined Doppler/time-free and traditional pseudorange methods together for a period of 34 seconds. As shown, the combined Doppler/time-free positioning algorithm provides receiver position estimates that are comparable in error magnitude to the traditional method. Similar results were obtained for all of the other off-air data sets at our disposal.

    Nicholas Othieno and Scott Gleason
    FIGURE 7 Comparison of position estimation error magnitudes for time-free and traditional pseudorange-based position estimations. Error magnitudes for both methods tested on the Montreal off-air data set.

    Concluding Remarks

    In this article, we have demonstrated that that a GNSS receiver can estimate its position using a snapshot of sampled data and no knowledge of the position of the receiver in low and medium dynamics environments. This addresses an existing limitation of the time-free GNSS navigation technique and facilitates new receiver designs based on limited sampled data sets, notably those using software-based processing techniques. It has been shown that by roughly estimating the receiver position using Doppler measurements with no knowledge of the receiver position, a time-free position estimation can be robustly performed. The limitations on this combined method are due mainly to the dynamic environment of the receiver, which will degrade the rough Doppler position estimate. Nevertheless, this technique will work for a wide range of GNSS applications. Additionally, Monte-Carlo simulations have been performed that show that this combined technique is robust within the stated dynamics limitations and initialization requirements of the time-free method for GPS C/A-code signals.

    Overcoming the Velocity Limitation. The degradation of the Doppler estimation for receivers at higher velocity can be addressed in a number of ways. The most direct correction to this problem is the inclusion of a simple inertial device on the receiver. This will provide a coarse estimate of the receiver velocity that then can be included in the Doppler estimation and would result in position accuracies using Doppler on the order of 1 kilometer in nearly all dynamic receiver cases (limited only by the capability of the inertial sensor).

    The second possibility is to wait for the next generation of GNSS signals to solve the problem for us. Several new GNSS signals (some of which are already being transmitted by active satellites) have been designed with code repeat periods of significantly longer than 1 millisecond (see FIGURE 8). The 1-millisecond code repeat period effectively limits the Doppler estimation error to what was shown above.

    Nicholas Othieno and Scott Gleason
    FIGURE 8. Comparison of code-phase repeat period ambiguities for various GNSS signals.

    Longer repeat periods will correspondingly increase the tolerance of the time-free a priori initialization. Some of the next generation GNSS signals and their respective code repeat periods will be significantly longer than GPS L1 C/A-code. For example, the 20-millisecond code repeat period of the new GPS L2 civil signal corresponds to approximately a 6,000-kilometer repeat length, and an integer 20-millisecond ambiguity of normally only three or four. This will make the construction of the full pseudorange from a 20-millisecond tracking-loop measurement much easier in the presence of larger errors in the a priori position knowledge.

    Discussion. Our work provides a useful method to greatly reduce the processing load in a GNSS receiver, and eliminates the task of decoding GNSS navigation data and the need to have coarse position information. These two advantages together provide a useful step in the development of a dramatically different approach in GNSS signal processing and position estimation. As opposed to existing GNSS receivers, which continually process the incoming signals, this technique allows for strict management of the incoming data and position estimation outputs. This management is well suited for applications that are required to remain off or in a low-power state for long and intermittent periods. Using this technique, any platform can estimate its position by operating the GNSS receiver for a short (snapshot) period of time. The logged data captured during this brief time can then be processed in real time or archived and processed later as the application demands. Applications such as animal tracking or long-duration vehicle tracking, where a position needs to be tracked over a long period using extremely challenging power resources, will benefit notable from this new technique.

    Software demonstrating the algorithms discussed above can be downloaded free of charge from http://gnssapplications.org/, including Chapter 3 (on the GNSS simulator) and Chapter 5 (on the fastGPS receiver).

    Acknowledgments

    This article is based on the paper “Combined Doppler and Time Free Positioning Technique for Low Dynamics Receivers” presented at PLANS 2012, the Institute of Electrical and Electronics Engineers / Institute of Navigation Position, Location and Navigation Symposium held in Myrtle Beach, South Carolina, April 23–26, 2012.

    Manufacturer

    Tests were conducted using a SparkFun (www.sparkfun.com ) SiGe GN3S USB front end.

    NICHOLAS OTHIENO was an M.A.Sc. student in the Department of Electrical and Computer Engineering at Concordia University, Montreal, Canada. His research was in the area of software-based GNSS techniques and applications.

    SCOTT GLEASON has been an assistant professor in the Department of Electrical and Computer Engineering at Concordia University since 2010. He received his B.S. degree in electrical and computer engineering from the State University of New York at Buffalo, an M.S. in engineering from Stanford University, and a Ph.D. from the University of Surrey in England. He has worked in the areas of astronautics, remote sensing, and GNSS for more than 15 years, including time at NASA’s Goddard Space Flight Center and Stanford’s GPS Laboratory, and the National Oceanography Centre, Southampton, England.

     

    FURTHER READING

    • Authors’ Publications

    “Combined Doppler and Time Free Positioning Technique for Low Dynamics Receivers” by N. Othieno and S. Gleason in Proceedings of PLANS 2012, the Institute of Electrical and Electronics Engineers / Institute of Navigation Position, Location and Navigation Symposium held in Myrtle Beach, South Carolina, April 23–26, 2012, pp. 60–65.

    Combined Doppler and Time-Free Navigation for Low Dynamics Receivers by N. Othieno, M.A.Sc. thesis, Department of Electrical and Computer Engineering, Concordia University, Montreal, Canada, April 2012.

    • Assisted GNSS

    A-GPS: Assisted GPS, GNSS, and SBAS by F. van Diggelen, published by Artech House, Boston, Massachusetts, 2009.

    “Assisted GPS: A Low-Infrastructure Approach” by J. LaMance, J. DeSalas, and J. Järvinen in GPS World, Vol. 13, No. 3, March 2002, pp. 46–51.

    • New GNSS Signals

    “New Navigation Signals and Future Systems in Evolution” by A.R. Pratt, Chapter 17 in GNSS Applications and Methods, eds. S. Gleason and D. Gebre-Egziabher, Artech House, Boston, Massachusetts, 2009.

    • Software GNSS Receivers and Simulators

    “Software GNSS Receiver: An Answer for Precise Positioning Research” by T. Pany, N. Falk, B. Riedl, T. Hartmann, G. Stangl, and C. Stöber in GPS World, Vol. 23, No. 9, September 2012, pp. 60–66.

    Digital Satellite Navigation and Geophysics: A Practical Guide with GNSS Signal Simulator and Receiver Laboratory by I.G. Petrovski and T. Tsujii with foreward by R.B. Langley, published by Cambridge University Press, Cambridge, U.K., 2012.

    “GNSS Navigation: Estimating Position, Velocity, and Time” by S. Gleason and D. Gebre-Egziabher, Chapter 3 in GNSS Applications and Methods, eds. S. Gleason and D. Gebre-Egziabher, Artech House, Boston, Massachusetts, 2009.

    “A GPS Software Receiver” by S. Gleason, M. Quigley, and P. Abbeel, Chapter 5 in GNSS Applications and Methods, eds. S. Gleason and D. Gebre-Egziabher, Artech House, Boston, Massachusetts, 2009.

    “A Real-Time Software Receiver for the GPS and Galileo L1 Signals” by B.M. Ledvina, M.L. Psiaki, T.E. Humphreys, S.P. Powell, and P.M. Kintner Jr. in Proceedings of ION GNSS 2006, the 19th International Technical Meeting of the Satellite Division of The Institute of Navigation, Fort Worth, Texas, September 26–29, 2006, pp. 2321–2333.

    “Architecture of a Reconfigurable Software Receiver” by G.W. Heckler and J.L. Garrison in Proceedings of ION GNSS 2004, the 17th International Technical Meeting of the Satellite Division of The Institute of Navigation, Long Beach, California, September 21–24, 2004, pp. 947–955.

    • Use of Doppler Measurements in GNSS Positioning and Navigation

    “Doppler-Aided Positioning: Improving Single-Frequency RTK in the Urban Environment” by M. Bahrami and M. Ziebart in GPS World, Vol. 22, No. 5, May 2011, pp. 47–56.

    “Instantaneous Real-Time Cycle-Slip Correction for Quality Control of GPS Carrier-Phase Measurements” by D. Kim and R.B. Langley in Navigation, Vol. 49, No. 4, Winter, 2002–2003, pp. 205-222.

    “The Principle of a Snapshot Navigation Solution Based on Doppler Shift” by J. Hill in Proceedings of ION GPS 2001, the 14th International Technical Meeting of the Satellite Division of The Institute of Navigation, Salt Lake City, Utah, September 11–14, 2001, pp. 3044–3051.

    “Measuring Velocity Using GPS” by M.B. May in GPS World, Vol. 3, No. 8, September 1992, pp. 58–65.

    “Geometrical Aspects of Differential GPS Positioning” by P. Vaníček, R.B. Langley, D.E. Wells, and D. Delikaraoglou in Bulletin Géodésique, Vol. 58, No. 1, 1984, pp. 37–52, doi: 10.1007/BF02521755.