Challenges of Ray-Tracing for GNSS Applications
"GNSS Solutions” is a regular column featuring questions and answers about technical aspects of GNSS. Readers are invited to send their questions to the columnist, Dr. Mark Petovello, Department of Geomatics Engineering, University of Calgary, who will find experts to answer them. firstname.lastname@example.org
Q: What are the challenges of ray-tracing for GNSS applications?
A: Simulating the propagation and reception of GNSS signals in complex environments is a challenging task. Indeed, the user always has to trade off between the computation time and the reliability of the output. Moreover, the motion of GNSS satellites, atmospheric effects, and building geometry are always difficult to model.
This article describes how ray-tracing methods can produce consistent and reliable output. It also provides an example of validation of a software suite using a graphics processing unit (GPU)–based ray-tracing algorithm to model obscuration and multipath.
Methods for Modeling GNSS Signal Propagation
Several methods exist to compute the propagation of GNSS signals in constrained environments. These are summarized in Figure 1 (see photo at the top of this article for figures 1 - 4) and can be sorted into four categories according to the methods used to model the environment and the propagation.
Pure statistical methods (such as Rayleigh, Rice, Nakagami, and so forth) provide results quickly, but their accuracy and relevance can be low. Moreover, these methods rely on empirical parameters that can be difficult to tune to fit to real environments. Hybrid methods may partially overcome this drawback by using a deterministic approach to define either the environment or the propagation model.
Deterministic methods return accurate data but have two major disadvantages. Firstly, their reliability relies largely on the quality of models (or synthetic environments) used to define the environment (satellites locations, clocks, atmospheric conditions, buildings, vehicles, receiver properties, etc.). Indeed, the user can achieve a Laplace demon for a while only if the environment modelling (3D virtual scene and simulation parameters) perfectly matches reality. Unfortunately, it is not possible to create such a model with limited time and effort. Moreover, these methods are often time-consuming in complex environments such as urban areas.
Pure deterministic methods can be sorted in two categories as shown in Figure 2: full exact (such as Finite Element methods) and asymptotic methods. Unlike full exact methods, asymptotic approaches use approximations to solve the Maxwell equations but with greater efficiency. Specifically, they assume the dimensions of objects are greater than the wavelength of the emitted signal.
Asymptotic methods are divided in two main categories: ray-based and current-based algorithms. The first category uses geometrical optics (GO) and its extension for diffractions (uniform theory of diffraction or UTD) to compute the propagation of the signal whereas the second category relies on physical optics (PO) laws.
The objective of this article is to describe how ray-based asymptotic methods can be chosen to assess the propagation of GNSS signals in constrained environments and explain their added values and limitations.
What is Ray-Tracing?
The equation of the ray is: ray = O + dir⃗ * t
The objective of ray-tracing is to find all the possible paths from the receiver (also called the observer) to the emitter (also called the source), considering a limited number of interactions per emitted rays. A ray-tracer (or ray-tracing algorithm) uses a primary grid to cast primary rays, as shown in Figure 3. Then, it iteratively computes the possible interactions between these rays and the virtual scene (often defined using triangles). If those interactions exist (i.e., if they are compliant with the laws of physics) and if the number of interactions to reach the emitter is below the maximum number of interactions set by the user, a ray (or multipath) is created.
Ray-tracing techniques have two major issues: they require time-consuming algorithms and their accuracy depends on the resolution of the primary grid. Indeed, depending on the complexity of the scene (basically the number of triangles), a combinatorial problem to find the possible multipaths reaching the receiver makes the ray-tracer very slow. That is the reason why the most difficult task to achieve during the coding of a ray-tracing algorithm is to develop acceleration techniques to quicken the computation process.
Several solutions exist to either improve the intersection determination (for instance, based on spatial hierarchies such as bounding volume hierarchies or BVH techniques), or to decrease the number of cast rays (often based on adaptive sampling techniques), or even to replace rays with beams or cones. Moreover, today we can use the resources of a computer’s graphic board to accelerate the computation. Indeed, as ray-tracing can be coded by a large number of primary functions that can be treated simultaneously, it can be easily ported into a GPU.
As for the dependency of a ray-tracing technique’s accuracy on the resolution of the primary grid, details and therefore rays may be missed if the three-dimensional scene is made up of small details. This issue is called aliasing. Aliasing artefacts appear, for instance, in parts of the scene with abrupt changes (such as edges) or in complex areas with lots of constituent objects. Solutions (or anti-aliasing techniques), such as adaptive or stochastic samplings, exist that can deal with this phenomenon.
Ray Tracing for GNSS
As ray-tracing is a deterministic method, specular multipaths can be displayed in 3D and their attributes (receiver power, phase, polarization, Doppler, geometry of the ray, and so forth) are known. It is therefore easy to see the contribution of some part of the environment on the propagation of the signal.
The Synthetic Environment
These synthetic environments may be sorted into three categories:
Validation – Example of Simulated Data
Both software applications communicate in real-time through a TCP/IP protocol. The computation frequency has been set to 10 hertz.
We selected a U.S. street for the simulation and for the measurement campaign with the local environment created from raw data. These raw data, which model the geometry of the large structures (buildings, large objects), have been created using photogrammetry techniques from satellite stereoscopic imagery. The resolution of the input images was 50 centimeters.
Then, we post-processed these data to add geometrical details (buildings windows, doors, street objects, and so on) and to define the building materials. Figure 6 shows how the model evolves from low to high resolution.
Figure 7 compares measured and simulated data when only obscuration has been considered (no multipath). The results of the measurement campaign indicates that general trends are globally reproduced: the simulated levels of the received power are fair for GPS-05 and GLO-09. Regarding GPS-02, the drop of power is caused by the obscuration of the LOS signal as explained by the simulated data. However, the simulated power does not correctly mimic the small variations of power, mainly due to multipath interactions and interferences.
Figure 8 shows the evolution of the simulated carrier-to-noise-density ratio (C/N0) when multipath is considered: a maximum of four reflections and one diffraction per multipath have been modeled and 10 multipaths per channel have been taken into account.
The graphs in Figure 8 show a better consistency between measured and simulated data. The variation of power is more erratic and the visibility of the satellites is similar to actual measurements of signals.
Nevertheless, some discrepancies can be observed in the power level. Several causes can explain such discrepancies, such as quality of the scene (especially for low elevation satellites with only non-LOS reception) or the surrounding traffic during the test (vehicle or pedestrian) and the vegetation (for instance, isolated trees), which have not been modeled in the simulation.
Deterministic simulations never produce data that fits perfectly with real measurements. Indeed, they highly depend on the realism of the synthetic environment, and it is not possible (with limited time and effort) to perfectly mimic a real configuration. However, the added value of using such algorithms is certain when we compare measurements with statistical and deterministic simulations.
Ray-tracing algorithms will not perfectly reproduce what happened or what could/will happen, but they can supply data that match real measurements as closely as possible, according to the quality of the definition of the synthetic environment.
ManufacturersOKTAL Synthetic Environment (OKTAL-SE), Vigoulet-Auzil, France, and the positioning technology business unit of Spirent Communication plc based Paignton, United Kingdom, have recently carried out measurement campaigns to validate the performance of a simulator based on ray-tracing method. SimGEN: the simulator software suite, developed by Spirent, produced the simulation scenario and modeling of the constellation and the receiver. SE-NAV, the propagation kernel, developed by OKTAL-SE, providing SimGEN with all the data needed to model deterministically multipath. SE-NAV uses a proprietary GPU ray-tracing algorithm to compute the obscuration as well as the multipath. The raw data used to create the Synthetic Environment was created by Siradel, Saint-Grégoire., France.
Copyright © 2017 Gibbons Media & Research LLC, all rights reserved.