You are here

SPRING - A tool for Advanced GNSS Simulations

Personal land navigation has become one of the most popular and frequently used global navigation satellite systems (GNSS) applications. Especially vehicle navigation contributes widely in day to day life. However, navigation accuracy and precision depend on the type of environment and decrease in urban canyons. The drop of performances is due to the low visibility of GNSS satellites and the high influence of multipath. Therefore, recent technologies have been focused on the improvement of GNSS performances in constrained environments. As a response to the need of a reliable, accurate and precise navigation in urban canyons, Thales Services, in cooperation with French Space Agency (CNES), is developing a GNSS simulator named SPRING. This simulator is currently under development and consists of two components: the first one covers the system volume capabilities on a global or regional area, and the second one performs local simulations in 3D environment, mostly urban canyons. Its main objective is the estimation of positioning accuracy in constrained environments. SPRING simulator allows the estimation of the error due to multipath, taking into account the near environment of the receiver which is represented with 3D models. It joins the capabilities of a GNSS simulator with the performances obtained by the use of the most advanced Information Technologies (IT).

Driven by a common need, GNSS signals propagation simulation has been extensively analyzed by the GNSS community. As a result of these investigations, conclusion was made that such modeling is a complex task, where crucial aspects require greater efforts in order to provide desirable results. The two main difficulties, which greatly impact the robustness of 3D GNSS simulators, have been identified: reliable 3D models and accurate simulation of the GNSS signals propagation.

3D MODELS

In the frame of GNSS simulations, utilization and implementation of 3D models remains a challenge. To conduct local simulations of the GNSS signal propagation, a 3D model representing the receiver close environment has to be taken into account. It should provide reliable information about geometry and parameters that permit to precisely reproduce surrounding area. The importance of models complexity is underlined because of the significance of the type of buildings surfaces in the GNSS signals propagation. Therefore, the 3D model needs to be completed with data concerning material types and structures of the obstacles. Interactions of the GNSS signal with the 3D elements and their associated parameters determine its propagation and influence signals parameters such as strength, phase etc. The high requirements towards 3D models complexity limit the use of them. The simulation of GNSS signal propagation in a 3D environment stayed blocked due to the insufficient calculation capacities of accessible hardware. Attempts to simplify 3D models resulted in a significant decrease of accuracy and precision of the estimated position, whereas the use of rather complex 3D models failed because of unacceptably long durations of computations. The simulation of the GNSS signals in 3D environment is a task where the same processes are applied and repeated on a large amount of data. Therefore, the solution that we have decided to implement in SPRING simulator is to parallelize and accelerate the algorithms with the use of GPU graphical cards.

MULTIPATH IN URBAN CANYONS

Another aspect requiring high implementation efforts in the simulation of GNSS signal propagation is the multipath modeling, which is, in urban canyon environment, a phenomenon that affects largely the GNSS performance. It leads to important deterioration of the precision of the estimated position and the multipath error is an unavoidable source of error that contributes to the User Equivalent Range Error (UERE). This parameter is difficult to model, but crucial in order to describe performance of GNSS. Multiple radio paths between a transmitter and a receiver can occur for various reasons, such as interactions with obstacles on the signal path, reflections from the ground or atmospheric refraction. It is called multipath propagation and can lead to several effects on the received signal. Radio waves are reflected from objects that they meet on their path, such as buildings or elements of natural environment. These groups of objects are represented by parameters (surface roughness, type of the material) that will influence the behavior of the GNSS signal and therefore the final outcome. Reflections that occur from buildings can permit a service to exist, where otherwise the signal would be excessively attenuated by shadowing. On the other hand, reflections cause interferences where shadowing alone would provide adequate attenuation of unwanted signals. In the field of satellite navigation signal reflections contribute to multipath error and decrease positioning accuracy.

REFLECTION FROM A PLANE SURFACE

Surface reflection occurs at an abrupt change in the electrical properties of the medium through which electromagnetic radiation passes. The general situation for a plane smooth surface is shown in Fig. 1. The line A-A’ is the interface between two media of different electrical properties. Radio energy in medium 1 meets this interface at an incidence angle. Part of the incident energy is reflected, subject to geometrical optics, creating a reflected ray. The remaining part will penetrate the medium 2. The change in direction of the penetrating ray is referred to as refraction, and the penetrating ray is often referred as the refracted ray.

Reflection on a plane surface
Reflection and refraction at a plane boundary between two media

REFLECTION AND SCATTERING FROM ROUGH SURFACES

The above explication of the signal reflection problematic has assumed that the reflecting surface is flat and smooth. Such reflections are termed specular, which are analogous to optical reflections in a mirror. In practice, plenty of reflecting surfaces along a signal path, such as walls and roofs of the buildings, will not be smooth. Depending on the degree of surface roughness in relation to the wavelength the effect will vary from specular reflection to diffuse scattering. The assessment, whether reflection of scattering will occur is undertaken with the use of approximate guides, either Rayleigh roughness criterion or, in cases where the specular component is negligible, Lambertian. The combination of specular reflection and diffuse scattering in terms of power flux is presented on Fig. 2. In this simple, approximate model, the incident of the surface will be radiated as a coherent specular reflection, and the remaining power will consist of incoherent radiation in other directions. The directional distribution of the scattered power in Fig. 2 will depend on the angle of incidence, and on the nature and roughness of the surface.

Reflection on rough surface
Combination of specular reflection and diffuse scattering

As already mentioned, Thales Services together with French Space Agency is developing a GNSS simulator named SPRING. One of the aims of this joint activity is to create an innovative and reliable tool that will simulate the propagation of GNSS signals. In SPRING, two simulation levels are previewed: a global service volume simulation and a local simulation with accurate 3D environment modeling.

The global level of the simulator provides the assessment of the performances of navigation systems over a global or a regional area by computing the performances parameters, such as Dilution of Precision (DOP). It allows the analysis of the evolution of navigation performances obtained with the current GNSS constellations and the deployment of new ones. This type of simulation does not need the implementation of 3D models. The figure below shows an example of service volume performances.

Reflection on rough surface
VDOPmap produced by the SPRING simulator

The local level will often represent simulations conducted in urban canyons. Therefore, the environment representation has to be more realistic and must take into account as precisely as possible interactions with local surrounding area, especially multipath. To correctly assess positioning performances, a 3D model of local environment and a realistic propagation modeling are needed.

Studies over the light ray propagation have already been conducted by specialists of the computer graphics. Several techniques focused on obtaining the best possible 3D rendering have been developed. The most common techniques are rasterisation, ray casting and ray tracing. Among these, ray tracing provides the best realism but on the other hand has the highest computation needs.

Due to the fact that light rays and GNSS signals are both electromagnetic waves, they are subject to the same effects. Therefore, ray tracing can be applied to simulate the propagation of the satellites signals. To successfully accomplish this task, it is assumed that the GNSS satellites are considered as light sources, and that the GNSS receiver antenna is the camera that is watching the 3D scene.

RAY TRACING

In order to simulate the GNSS signal in SPRING simulator, the ray tracing has been chosen. Ray tracing is a method of ray propagation that requires an accurate model of the 3D scene. This technique is based on optics physics and models all effects that can occur during the propagation of rays: free-space propagation (direct path), reflection, refraction, diffraction, shadowing etc. It consists in the launching of one ray for each possible direction - tighter the sampling, the more accurate the propagation model is. Each ray is propagated until it intersects an object in the 3D modeled scene.

Depending on the intersected object type, interactions such as reflections, refractions, diffractions are processed and secondary rays are emitted at the intersection point. Again, these rays are propagated until they hit an object on their path. Fig. 4 shows an example of rays’ propagation.

Reflection on rough surface
Ray tracing principle

Interactions can be described for each type of object permitting the non planar surfaces (for instance cones, spheres…) to be processed. That is the reason why very realistic images can be produced with this method. However, a high number of generated rays degrade the performance of the propagation technique in a real time context. Nowadays, this technique is frequently used by graphics designers and the animation movies industry.

OPTIX

To implement the ray tracing method in SPRING simulator, the OptiX engine has been chosen. It is a programmable system designed for highly parallel architectures as NVIDIA GPU. OptiX is a simple but powerful abstract model of ray tracer. This ray tracer employs user-provided programs to control the initiation of rays, intersection of rays with surfaces, shading with materials, and creation of new rays.

The OptiX engine relies on the fact that majority of ray tracing algorithms can be implemented with a use of small set of programmable operations. Its core is a specific compiler that generates a model of ray tracing through combination of algorithms (libraries and ray generation codes provided by developers). It is done together with management of shadows, materials and intersections with the objects in the scene. This mode of operation allows implementation of a diverse set of algorithms and applications, including interactive and offline rendering, applications of artificial intelligence and scientific simulations such as light and radio frequency signals propagations. For this last application, OptiX reaches high performances with a compact object model and optimized compiler.

OptiX is not itself a ray tracer but it is serving as a framework to build ray tracing based applications. Each ray is characterized by user-specified attributes called a payload. Within, payload’s variables such as color, recursion depth, importance and many more are assigned to each ray. These parameters are further used by the CUDA C-based functions developed under OptiX, which is capable to automate the rays’ creation and propagation algorithms. Furthermore, it provides flexible, dynamic dispatch of user-coded functions and inheritance mechanism. These simplifications lead to generic, compact and therefore optimized ray tracing systems.

The ray tracing capabilities provided by OptiX contain several programmable components. These programs are invoked on the GPU during the execution of a generic ray tracing algorithm. The programmable components include:

  • Ray Generation: The entry point into the ray tracing,
  • Exception : Exception handler, invoked for errors,
  • Closest Hit: Called when a traced ray finds the closest intersection point,
  • Any Hit: Called when a traced ray finds a new potentially closest intersection point,
  • Intersection: Implements a ray-primitive intersection test,
  • Miss: Called when a traced ray misses all scene geometry.

SPRING IMPLEMENTATION

The SPRING simulator uses several external tools as seen on the tool architecture schema presented in figure below. The modeling of 3D scene is achieved via Google SketchUp Pro. It allows importation of numerous existing 3D models in various formats such as AutoCAD type, Google Earth, Collada. In order to optimize the simulation performances, these models have to be converted into an internal SPRING format. This task is performed as well with the use of Google SketchUp Pro. Then, the visualization of 3D scene is performed by NVIDIA SceniX that is an effective scene management tool, compatible with NVIDIA GPU. Furthermore, NVIDIA OptiX is used for simulation of the propagation of signals parallelized on GPU.

Reflection on rough surface
SPRING architecture

As already mentioned before, each generated ray is characterized by a payload that contains various parameters (ranging, phasing, number of intersected objects etc). The ray propagation in OptiX starts with generation of a grid of rays, azimuth and elevation separated. The process follows routines and methods implemented in OptiX. Therefore, if a ray intersects any object of a 3D scene, Closest hit function is called and, depending on the object’s material, attenuations and phase rotations are computed. Then, reflected and transmitted rays are emitted. If one of these rays intersects an object, Any hit method is called. In this case, the same steps as in case of Closest hit are performed, unless a maximum number of interactions have been reached. Finally, when a ray does not intersect any object of a scene, the Miss function is called and satellite detection is executed. If a satellite is aimed by the ray; range and receiver power can be computed. In order to detect edges and perform diffraction treatments, an additional post-processing is performed. It is based on correlation of a ray with its eight neighboring rays.

SPRING BENCHMARKS

Several benchmarks have been performed to verify capabilities of SPRING simulator. Constraint environments have been considered as adequate to conduct the preliminary tests for assessment of SPRING performance. All tests have been executed with the use of NVIDIA Quadro 5000 GPU that contains 352 cores for parallel computations.

TOULOUSE CAPITOLE TEST

First preliminary test has been conducted with the use of a 3D model of one of the most known monuments of Toulouse city - Toulouse Capitole that houses nowadays city hall and a theatre. The building is composed of several elements with an interior courtyard, which serves as an urban canyon as can be seen on the following figure.

Reflection on rough surface
Urban canyon in Toulouse Capitole

Each scene reproduced in the simulator is composed of polygons, which are structures that represent a 3D model. The Toulouse Capitole scene was created with 16000 polygons. As planned, the simulation was performed in the internal courtyard of the building. Receiver antenna was virtually placed under a vault, where the sky visibility is very limited, as shown on figure below. Therefore, we expected to have also low GNSS satellites visibility.

Reflection on rough surface
Antenna location in 3D model of Toulouse Capitole

In the frame of conducted simulation test, the rays were launched through an azimuth-elevation grid of 500 x 250 points which resulted in 125000 rays. In the simulator, a single, complete simulation sample is composed of approximately 2 250 000 rays, due to the multiple simulated interactions. During the simulation, SPRING processed 23 millions of rays per second. With such performance, the simulator is capable of processing 9 samples per second.

With the SPRING simulator, an image of a real time antenna mask can be obtained, as shown on figure below. It is a representation of the simulation environment, 360 degrees around the observer. The antenna mask shows the visibility of direct satellites and footprints of indirectly seen satellites, which is presented on the mask image as colored areas.

Reflection on rough surface
Antenna mask at Toulouse Capitole courtyard

The above image of antenna mask shows the visibility of satellites for an observer placed at Toulouse Capitole courtyard. Only one direct line of sight appears in the simulation, which is represented by the blue colored satellite visible on the sky. Other signals were detected at the receiver antenna level due to the reflections from the buildings facades. The satellite geometry shown on the image confirms expected poor GNSS satellites visibility.

MADRID PLAZA MAYOR TEST

Further tests of the SPRING simulator have been conducted with the use of 3D model of Plaza Mayor of Madrid (figure below), a central plaza in the city. The place is rectangular in shape, measuring 129 m by 94 m. It is surrounded by 3 floor buildings with the Casa de la Panaderia in the north, a municipal and cultural building.

Reflection on rough surface
Plaza Mayor in Madrid

The Plaza Mayor scene was modeled with 3350 polygons. To assure a good visibility of the sky, the simulation was performed in the centre of the plaza.

Similar as in the previous test, the rays were launched through an azimuth-elevation grid of 500 x 250 points which resulted in 125000 rays. During the simulation conducted on the Plaza Mayor, SPRING processed over 93 millions of rays per second. Such result gives the possibility to process 41 simulation samples per second.

In comparison with the previous test at Toulouse Capitole urban canyon, the results obtained in the simulation conducted in Plaza Mayor indicate faster scene computation. The outcome is related to the characteristics of the environment, namely the number of interactions within the scene: results improve with the lower number of interactions.

The direct lines of sight that occurred during the simulation on the plaza of Madrid are presented on a 3D view in the Fig. 10. Each visible satellite is displayed with a different color.

Reflection on rough surface
3D view of direct signals reception on Plaza Mayor in Madrid

A real time antenna mask was obtained for an observer virtually placed in Plaza Mayor as shown on the Fig. 11. The observer is placed in area with generally better sky visibility than in the previous test. Therefore, the visibility of GNSS satellites increased to six directly seen satellites. Again, the colored areas shown on the following image represent the footprint of satellites which are not in direct visibility.

Reflection on rough surface
Antenna mask at Madrid Plaza Mayor

Among preliminary benchmarks performed to assess capabilities of SPRING simulator, two have been presented in the article. They consist of various numbers of polygons and represent different simulation context: urban canyon and medium urban area.

It has been proved that computation duration was proportional to the number of detected interactions with the environment and did not depend on the level of details of the 3D model. However, the complexity of a scene has an impact on the scene loading time. In conclusion, the use of highly detailed 3D models will not degrade the computation performances of SPRING simulator.

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer