Abstract
A twofold architecture based on GNSS multipath environment prediction and detection is presented in a context of loosely coupled and tightly coupled IMU/GNSS integration for navigation in urban areas. A signal quality monitoring group of techniques is applied for a platform self-contained effort to detect and exclude multipath-contaminated GNSS signals. Additionally, the sensor integration Kalman filter stochastic model is adjusted on-the-fly based on a GNSS multipath environment map. The map is populated by crowdsourcing and contains the spatial distribution of average carrier-to-noise-density ratio measurements, linked to the probability of non-line-of-sight, multipath-contaminated, diffracted, and attenuated signal reception. To address the map availability issue, a random forest machine learning model is developed to propagate the map to the city areas not directly surveyed by the mapping fleet based on open-access geographic data. The architecture performance is evaluated in the automotive scenario showing 13-17% accuracy improvement compared to a conventional Kalman filter.
1 INTRODUCTION
GNSS-based positioning and navigation in obstructed urban environments is a challenging task. Unlike in open-sky conditions, satellite geometry is degraded due to signal obstruction by buildings, tree foliage, and vehicles. Additionally, GNSS signals are reflected from these objects leading to non-line-of-sight (NLOS) and multipath-contaminated signal reception. Mass-market platforms are typically restricted in size and cost, and the use of sophisticated hardware designed to mitigate multipath is not practical or even possible. Further, modern cities are complex dynamic environments imposing a significant difficulty for the multipath-effect deterministic modelling on the mass-market platform-position computation level.1
To isolate the multipath effect, a series of receiver-autonomous-integrity-monitoring (RAIM)-type consistency checking techniques is proposed with the underlying principle that multipath-contaminated signals produce a less consistent positioning solution. In Jiang et al.,2 solution inconsistencies are detected by comparing a test statistic based on the sum of the squared solution residuals with an empirically determined threshold. If the threshold is exceeded, the measurement with the largest normalized residual is eliminated, and the process is repeated until the test is passed or an insufficient number of measurements is left. This technique is further enhanced by producing a final solution based on the best available measurement subset and the measurements that passed the residual examination, along with the height aiding from the digital terrain model.3 The use of 3D city models has been explored to simulate pseudorange measurements by ray-tracing with the further exclusion of inconsistent measurements4,5 or reaching the positioning solution by comparing coordinates calculated from measured and simulated pseudoranges.6,7
Machine learning is proved to be effective for classification among line-of-sight, NLOS, and multipath-contaminated signals. In Hsu,8 the support-vector-machine classifier for static applications was trained using features such as carrier-to-noise-density ratio, its rate of change, pseudorange residuals, and the difference between the time-differenced pseudorange and pseudorange rate. In a more recent work, such a classifier was designed based on the gradient-boosting decision tree algorithm with only three features: carrier-to-noise-density ratio, pseudorange residuals, and satellite elevation angle.9
Three-dimensional maps outline the shapes of the surrounding buildings, but with limited small feature representation such as road signs and tree foliage. However, such environmental features, including building materials and street anomalies, have a noticeable impact on the positioning solution accuracy.10
Pseudorange multipath detection could be achieved by continuous signal quality monitoring (SQM). The code-minus-carrier (CMC) observable is a metric allowing us to isolate pseudorange multipath, and the regions where multipath is present are characterized by the increased variance of this observable.11,12 By applying statistical testing, SQM detects the change in the properties of the signal quality metrics with the further exclusion or de-weighting of the signals suspected of being multipath-contaminated. Due to the limited reliability of such an approach, a cascaded algorithm combining several monitoring techniques has been explored by Pirsiavash et al.13
Degraded performance of GNSS-only coordinate estimation is addressed by the integration of multiple sensors into a processing engine, including but not limited to inertial measurement units (IMUs), LiDAR, odometers, and barometers.14-16
One of the challenges of sensor integration with GNSS is to first detect a context of operation and then to adapt the integration model and its configuration accordingly.15,17 Kalman filter parameter tuning with respect to the platform behavioral features such as stops, straight motion, lane changes, turns, and roundabouts was demonstrated in the specific case of loosely coupled IMU/GNSS integration.18 Additionally, the statistical parameters of the Kalman filter noise levels have to be adjusted on-the-fly to avoid filter divergence due to inaccurate statistical modelling, the technique known as adaptive Kalman filtering (AKF).19,20 In innovation-based adaptive estimation (IAE) implementation of AKF, the process and measurement noise are adjusted based on the sliding window innovation residual sequence.21,22 The multiple-model adaptive estimation (MMAE) technique runs a bank of Kalman filters in parallel, with each having its own set of parameters for process and measurement noise as well as the weight assigned to each filter. The optimal state estimate is computed based on the weighted combination of the solutions of all the filters. The weight of each filter is then adjusted, so over time, the system converges to the most suitable statistical model.23
Substantial research efforts have been made to design systems exploiting strengths and compensating weaknesses of sensors available for positioning. As an example, in Chiang et al.,16 the standard motion constraints in IMU/GNSS integration are extended with barometric height and drift control routines, allowing mitigation of barometric noise if the platform follows the behavior such that a significant height change is not expected. A complex symbiosis of LiDAR, IMU, and GNSS is demonstrated in Wan et al.,15 where the GNSS ambiguity search space is reduced with the aid of inertial navigation that is in turn constrained by LiDAR.
Our work explores the notion of an IMU/GNSS integration Kalman filter stochastic model adaptation based on the knowledge extracted with crowdsourced GNSS observations directly from a real-world city environment. Modern cities support a variety of mobility solutions, including taxi, car sharing, and public bicycle and scooter sharing fleets, equipped with mass-market GNSS receivers making it possible to collect rich georeferenced data reflecting the impact of an urban environment on GNSS signal propagation. The distribution of average carrier-to-noise-density ratio (C∕N0) levels across the city of Montréal is considered in this study as a metric proportional to the probability of the NLOS, multipath-contaminated, diffracted, and attenuated signal reception and populating a GNSS multipath environment map. Along with the GNSS multipath environment map-aided filter stochastic model adjustment, the CMC and C∕N0 SQM is implemented as a self-contained effort to exclude the multipath-contaminated signals from processing with these two techniques forming a resilient sensor integration architecture. Additionally, the availability issue of the GNSS multipath environment map is addressed by training a random forest model predicting the expected levels of C∕N0 based on the open-access geographic data and propagating the map to the areas with no prior coverage.
The paper is structured as follows. The GNSS multipath environment mapping concept and map propagation model are discussed in Section 2. The implemented SQM multipath detection is described in Section 3. The overview of the proposed architecture is provided in Section 4. The experimental data collection campaign and performance evaluation of the implemented methods are given in Section 5. Finally, the discussion of the method limitations and the potential for future work are outlined in Section 6.
2 MULTIPATH PREDICTION
2.1 GNSS multipath environment mapping concept
The GNSS multipath environment mapping is based on prior investigations provided in Smolyakov et al.24 and is discussed further in this section.
Let us first consider a spatial hexagonal grid with a diameter of the inscribed circle of 25 m arbitrarily applied to the selected urban area (Figure 1A). Given that large volumes of GNSS logs generated by a potential mapping fleet are available in the selected area, it becomes possible to collect an extensive statistical representation of the C∕N0 observations per spatial grid element. Due to satellite geometry change with time, a temporal dimension is added to the map to account for the subsequent variation in the C∕N0 statistics as indicated in Figure 1B, for example, by hour-by-hour changes. Equation (1) illustrates the computation of the average C∕N0 metric 
populating the GNSS multipath environment map.
Spatio-temporal GNSS multipath environment mapping illustration
1
where
A lower level of individual C∕N0 observations is a sign of NLOS, destructive multipath-contaminated, diffracted, and attenuated signal reception.1,25 As a consequence, the mapped 
statistic is representative of expected GNSS signal inconsistencies across the entire area of operation of a positioning platform.
Section 4 contains the proposed application of the 
retrieved from the map for the Kalman filter measurement noise covariance adaptation.
2.2 Data collection campaign and results
In this work, the mapping fleet behavior was replicated by a single data collection vehicle driving repetitively in the limited area of Montréal selected for testing. The mapping GNSS logs collection campaign details are provided in Table 1. The EVK-M8T coordinates output at 2-Hz rate were used in the map populating process. The early morning was chosen for data collection to avoid traffic congestion in the downtown area, maximizing the ratio of the distance traveled to time spent. Following Equation (1), the 
was computed populating the GNSS multipath environment map. Two examples of the generated map are presented in Figure 2A,B.
GNSS multipath environment mapping: data collection campaign details
GNSS multipath environment map illustration
2.3 GNSS multipath environment map prediction
The mapping approach described in Sections 2.1 and 2.2 has a disadvantage of limited map availability. Some city streets are likely to be restricted for the mapping fleet due to road construction, and insufficient statistics could be collected for the roads with less traffic. Moreover, the availability of the mapping fleet for the entire city road network is not guaranteed. These factors limit the potential use of the map, and to overcome the issue, we investigate the prospect of propagating the GNSS multipath environment map to the areas not directly surveyed by the mapping fleet applying machine-learning techniques.
The complexity of a dense urban area for the machine-learning model training is represented by the following open-access geographic data, including the features affecting the GNSS signal propagation and the C∕N0 level specifically:
2D building polygons (vector layer);
road polygons (vector layer);
road types;
LiDAR digital elevation model (DEM) (raster layer);
tree foliage geometries (vector layer).
The feature data layers were converted to raster images with a resolution of 1700 × 1700 pixels, each pixel representing a 2.5 × 2.5 m square of the feature layer assigned with a value. These raster layers are used as inputs for the machine learning model training. Binary pixel values were used to indicate the presence or absence of foliage or of a building object (e.g., in case of building polygons, “1” is assigned when a building is present, and “0” is assigned when no building is present), elevation values were extracted from the LiDAR DEM, and numbers representing road types were assigned to the corresponding raster road data layer pixels. Acting as a label data layer, the real-world GNSS multipath environment map was converted to a raster image of the same dimensions (1700 × 1700 pixels) with each pixel assigned with the corresponding 
. The raster layer illustrations for a selected city area (325 m × 500 m) are provided in Figure 3.
Feature and label data layers representation in raster form for a selected city area
The general scheme of the machine learning is provided in Figure 4. Random forest (RF) is an ensemble machine learning method that is capable of performing both classification and regression tasks using various decision trees (DTs) in a parallel paradigm.26 For each DT, a random sample of the observations is selected for training through a bootstrapping method, which uses some samples in each tree multiple times. Selecting a different set of samples in each tree will end up having a high variance for each tree, while overall, the entire forest will have lower variance, but not at the cost of increasing the bias. Besides, due to the random selection and averaging at the end, the effect of random noise in the observation would be minimized. The two main parameters of the random forest that should be adjusted are the number of trees and the number of variables.27 In our study, a total number of 500 trees was selected in the classification model. Moreover, the square root of the number of input variables was considered to decrease both the computational complexity of the model and the correlation between trees.28
GNSS multipath environment map prediction diagram
The RF model map prediction accuracy has been evaluated by comparing the model predictions with the real-world GNSS multipath environment map for the city territory, labels for which were not used for the RF model training. Here, we make an assumption that when the prediction is less than 1 dB-Hz different from the original GNSS multipath environment map, it is accepted as correct. Based on the assumption above, the RF model produced the 
predictions with 89% accuracy.
3 SIGNAL QUALITY MONITORING
3.1 Background on signal quality monitoring (SQM)
Let us consider an example of a real-world C∕N0 time series collected in Fredericton, NB, in February 2019 while the test vehicle entered, drove through, and exited deep urban canyon road conditions (Figure 5A) with two GPS satellites presented for analysis: satellite G32, with an elevation angle of 81◦; satellite G31, with an elevation angle of 50◦. It can be seen from Figure 5A that the C∕N0 time series is perturbed while navigating in the urban canyon conditions typically experiencing a multipath environment and resulting in a growth of the observable sample variances 
(20 epochs sample size, Figure 5B). The 
is higher than 
likely due to the lower elevation angle of the satellite G32 correlating with the higher probability of multipath contamination.
SQM analysis while moving through a multipath environment: (A) C∕N0 time series; (B) 
time series; (C) C∕N0-based multipath detection flag; (D) CMC time series; (E) 
time series; (F) CMC-based multipath detection flag
If both carrier-phase and pseudorange measurements are available at the given epoch of observations, it is possible to monitor the presence of multipath on pseudorange measurements by forming a CMC observable. Multipath error of the carrier phase is typically smaller than that of the pseudorange by approximately two orders of magnitude; therefore, by differencing the pseudorange and carrier-phase measurements along with the cautious modelling of other error sources, according to Braasch,1 the multipath error could be monitored from the following approximation of the CMC observable:
2
where
The behavior of the CMC observable in the presence of multipath conditions is displayed in Figure 5D. The plot in Figure 5E contains corresponding sample variances (20 epochs sample size) of the CMC observable denoted as 
. Note that the 
time series (Figure 5E) follows a pattern similar to that of 
(Figure 5B), confirming that the statistical analysis of the CMC observable allows for multipath monitoring as well.
3.2 Multipath detection significance test
The analysis of the real-world multipath scenario provided in Section 3.1 suggests that multipath detection could be carried out by monitoring the change of statistical properties of the SQM metrics, namely, C∕N0 and/or CMC observables. In this work, a single-tailed significance test is implemented for such a purpose based on previous research11-13 as follows:
3
where
The 
value is determined empirically for a reference satellite with a high elevation angle in open-sky conditions, the signal from which is expected to be essentially multipath-free.
The following hypotheses are applied: (4)
4
5
where
4 INTEGRATION ARCHITECTURE OVERVIEW
During the development of the architecture, a variety of IMU/GNSS integration configurations were tested with two selected for analysis in this paper: tightly coupled and loosely coupled GPS + Galileo C1C, L1C, and D1C observable processing. Further, sensor integration is discussed in Sections 4.1 and 4.2.
4.1 Loosely coupled IMU/GPS integration
In a standalone GNSS solution, measured pseudorange, pseudorange-rate, and carrier-phase observables are modelled as follows:
6
7
8
where additionally
Table 2 contains the details on the GNSS error source corrections applied. The extended Kalman filter (EKF) is implemented for the GNSS-only position and velocity computation following Groves,29,30 with the state vector xGNSS set as
GNSS processing specifications
9
where
The loosely coupled IMU/GNSS Kalman filter is implemented following Groves,29,31,32 with the state vector xLC set as
10
where
4.2 Tightly coupled IMU/GNSS integration
In our tightly coupled implementation, pseudorange, pseudorange-rate, and carrier-phase observables are modelled according to Equations (6), (7), and (8). The processing method follows Groves,29,31,32 and the EKF state vector xTC is set as
11
Further specifics on the sensor integration routines are omitted here for brevity.
4.3 Multipath detection and prediction scheme
The block diagram of the implemented architecture is shown in Figure 6. The SQM discussed in Section 3 is responsible for the selection of GNSS signals that are least likely to be multipath-contaminated. The C∕N0 and CMC monitoring is performed in parallel followed by the satellite exclusion or de-weighting block. On-the-fly stochastic model adjustment of the Kalman filter is implemented by first performing a spatio-temporal query of the GNSS multipath environment map. If heading information is available in the navigation system, a directional map query is performed to sample only the grid elements holding the 
statistics of the upcoming GNSS environment conditions (Figure 7A). In case the heading is not available, the platform queries the map omni-directionally (Figure 7B). The exact parameters of the map spatial sampling depend on platform dynamics and on the processing technique used. The scaling coefficient γ is then calculated as a function of 
:
Multipath detection and prediction algorithm diagram
GNSS multipath environment map spatial sampling illustration
12
where f is application specific and is designed based on a sensor integration strategy (Section 5.2 contains the description of f applied in this work); and A is the map query area.
The measurement noise covariance is then scaled:
13
where
5 EXPERIMENTAL RESULTS
5.1 Test data collection campaign
The specification and configuration of the equipment used in the data collection campaign is provided in Table 3. Figure 8A-C illustrates the equipment installation in/on the test vehicle. The data collection was performed on August 10, 2019 in Montréal. The test trajectory included a variety of urban conditions with the emphasis on heavily obstructed environments occurring on an estimated 50% of a 7-km trajectory. See Figure 9 for examples of the track environments and Figure 10 for the overview of the track. The NovAtel SPAN system provided the reference trajectory, taken as truth. Two-dimensional absolute errors of our processing architecture were computed by differencing the computed and reference trajectories and the statistical performance expressed as distance root mean square (DRMS) and twice distance root mean square (2DRMS).
Equipment specification, configuration, and placement
Test data collection hardware
Test track urban environments
Data collection track overview. Three-dimensional city view retrieved from Google Earth
5.2 Architecture performance evaluation
Figure 11 illustrates the architecture reaction example to a scenario when the test platform transitioned from Boulevard de Maisonneuve to Rue de la Montagne. At the mark of 44 158 s of day, the 
started to exceed 35 dB-Hz, and the measurements noise scaling coefficient was subsequently decreased according to the rules in Table 4 based on the sigma-ε model of Hartinger and Brunner33 for the tightly coupled integration case and empirically derived for the loosely coupled integration case. In both tightly and loosely coupled conventional Kalman filters, the position solution started to diverge at the 44 175 s of day mark while, when the measurement noise adjustment was enabled, this divergence was compensated in the tightly coupled case (Figure 11D), and faster solution convergence was reached in the loosely coupled case (Figure 11E).
Proposed architecture performance example. (A): 
retrieved by the positioning platform from the GNSS multipath environment map after every filter iteration; (B): PDOP levels; (C): number of tracked satellites; (D): tightly coupled IMU/GNSS 2D error; (E): loosely coupled IMU/GNSS 2D error
Map-aided measurement noise covariance scaling for tightly coupled and loosely coupled IMU/GNSS integration
It is identified that such an approach will not work perfectly in all GNSS signal propagation situations. Figure 12 illustrates an example of a counterproductive map-based measurement noise adjustment that resulted in a 12-m absolute horizontal error growth in the tightly coupled integration case.
Counterproductive measurement noise adjustment example in the tightly coupled integration case. Triangle markers: conventional approach; circle markers: measurement noise adjustment enabled
The absolute 2D error distribution statistics of the architecture performance for the entire testing route are provided in Figure 13. When the architecture was enabled, 13% and 17% horizontal accuracy improvement was observed in tightly coupled (Figure 13A) and loosely coupled (Figure 13B) integration scenarios, respectively.
Absolute 2D error distribution for the entire testing route: comparison among processing methods
6 DISCUSSION AND FUTURE WORK
In navigation scenarios with foreseen GNSS environment changes, the application of a constant measurement noise model is not practical as such an approach does not allow a system to reach a compromise between filter performance in terms of position accuracy and outlier mitigation. The advantage of the GNSS multipath environment map application is the ability to adjust a sensor integration Kalman filter stochastic model ahead of upcoming signal environment conditions. However, current implementation of measurement noise covariance scaling, specifically in tightly coupled integration (Equation (13)) is not optimal as the same scaling coefficient γ is applied to all measurements. The identified possibility of a negative impact on the solution in terms of absolute error (Figure 12) is suspected to originate from factors such as insufficient mapping fleet logs available for processing and the shortcomings of the proposed measurement noise adjustment strategy. While combining this approach with the SQM-based satellite selection shows an adequate accuracy improvement, a more cautious map incorporation into the AKF model is planned.
The prototype scale of our work left out the investigation of the 
metric variation throughout the day due to satellite geometry change. An extensive real-world connected platform logging is needed to perform such an analysis. Note that the data collection for the performance evaluation was started at 08:06:30 am local time, while the map was generated with logs collected between 3 am and 6 am local time. The authors expect some level of map degradation when it is used with the dataset collected outside its production interval (2-h delay in this case). The map degradation evaluation is planned for future work.
The C∕N0 observations used to populate the GNSS multipath environment map are hardware-dependent. The identical hardware installed on all mapping fleet platforms is not guaranteed; therefore, calibration procedures need to be applied before incorporating the C∕N0 observations generated by diverse GNSS receiver and antenna combinations.
Further work is planned to include more environmental features affecting GNSS signals in the machine-learning map prediction, such as traffic density and building materials.
7 CONCLUSIONS
The architecture incorporating platform self-contained SQM for multipath-detection and a GNSS multipath environment map for on-the-fly Kalman filter measurement noise covariance scaling has been discussed. The propagation of the original map covering 10 km2 to areas not directly surveyed with the mapping fleet is achieved by training a random forest model based on open-access geographic data with a map prediction accuracy of 89% being reached. An approximately 13% horizontal accuracy improvement could be expected when the architecture is applied in the tightly coupled and 17% in loosely coupled IMU/GNSS integration on mass-market platforms.
HOW TO CITE THIS ARTICLE
Smolyakov I, Rezaee M, Langley R. Resilient multipath prediction and detection architecture for low-cost navigation in challenging urban areas. NAVIGATION-US. 2020;67: https://doi.org/10.1002/navi.362 397–409.
ACKNOWLEDGMENTS
Our research is supported by the Natural Sciences and Engineering Research Council of Canada. The authors thank Dr. René Landry and Dr. Hamza Benzerrouk of École de technologie supérieure in Montréal for their input on sensor integration development and for providing access to the reference solution equipment.
Footnotes
Funding information Natural Sciences and Engineering Research Council of Canada
- Received November 4, 2019.
- Revision received March 2, 2020.
- Accepted March 6, 2020.
- © 2020 Institute of Navigation
This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
Jump to section
Related Articles
Cited By...
- No citing articles found.