3D building model-assisted snapshot positioning algorithm

Abstract

A method for constructively using non-line-of-sight GNSS signals from a snapshot of signal samples for positioning of users in urban areas is presented here. Using a 3D building model and a ray-tracing algorithm, the number of reception paths and the corresponding path delays of reflected signals are predicted, across a rid of candidate positions. These predictions are then used to compute a least squares fit to the GNSS receiver’s correlator outputs, and the position with smallest residuals is selected as the position estimate. Using data collected along 3.5 km of road in downtown Calgary, Canada, where buildings reach heights of over 200 m, the root-mean-square position error is below 10 m in the along-track and across-track directions. Compared to two pseudorange-based receivers, the proposed method yields RMS error improvements of at least 31% in the along-track direction, 63% in the across-track direction, and 53% in the horizontal plane.

Introduction

The day-by-day increase in popularity of global navigation satellite system (GNSS) is evidenced by the increasing number of applications from mobile phones to aircraft landing. GNSS has emerged as a mainstream technology for navigation for several outdoor applications, maintaining high reliability and accuracy demands even while using low-cost portable devices. The recent trend is toward extending GNSS-based applications to urban canyon environments (Bourdeau et al. 2012; Groves 2011; Petovello and He 2016; Sahmoudi et al. 2014; Suzuki and Kubo 2013; Xie and Petovello 2015). In such environments, poor satellite visibility (i.e., a limited number of signals can be tracked), poor dilution of precision (DOP), and signal reflections from nearby buildings conflate to reduce the accuracy of standalone GNSS-based navigation systems. Reflected or non-line-of-sight (non-LOS or NLOS) signals, when combined with the direct LOS signals, create unwanted multipath effects that remain the dominant source of error (Braasch 2001; Ward et al. 2006; Xie and Petovello 2015). Multipath cannot be removed by differential techniques, thus limiting positioning accuracy in multipath prone areas (Ercek et al. 2006; Misra and Enge 2011; Ward et al. 2006). Several techniques have been proposed for detection and mitigation of multipath signals whose methodologies can be broadly categorized as follows:

• Integration with other sensors/systems, most notably inertial navigation systems (INS), where the complementary characteristics of each system are exploited (Groves et al. 2007; Petovello et al. 2008a; Soloviev and Graas 2009; Soloviev et al. 2011).

• Modified GNSS receiver processing strategies to improve signal processing/tracking such as vector-tracking, ultra-tight integration with INS, maximum likelihood tracking, and block processing methods (Petovello et al. 2008b; Uijt de Haag 1999; Graas et al. 2009; Weill 2010; Xie and Petovello 2012).

• Use of multi-constellation GNSS to increase the number of measurements and reduce the DOP (Groves et al. 2013; O’Driscoll et al. 2010).

• Adoption of signal parameter estimation techniques (He and Petovello 2013; Sokhandan 2013; Van Nee 1995).

In addition, 3D building models (3DBMs), which are digital representations of cities containing relevant geospatial information (Frere et al. 1998), have recently been used to improve positioning performance in urban areas. Approaches can be roughly divided into three categories, either with or without additional sensors: (1) GNSS-free approaches, (2) NLOS signal identification, estimation, and/or exclusion (but without compensation), and (3) constructive use of NLOS signals.

GNSS-free approaches include the use of 3DBM and images for skyline-based positioning without any GNSS data (Petovello and He 2016; Ramalingam et al. 2009, 2010).

The second category encompasses a range of techniques that identify, estimate, and/or exclude NLOS signal information without attempting to compensate the solution for their effect. Excluding measurements can be effective at minimizing position errors, but often leads to poor satellite geometry. Bradbury et al. (2007) simulated multipath effect using a 3DBM to identify valid reflectors. Obst et al. (2012) used a 3DBM along with vehicle’s onboard odometer to detect and predict GNSS multipath situations in urban areas. Kumar and Petovello (2015) showed how 3DBMs could be used for multipath parameter estimation.

The third category aims to use the NLOS signal information in a constructive manner and includes several different approaches. The concept of shadow matching was proposed by Groves (2011), which categorizes signals as LOS or NLOS, largely based on carrier-to-noise density ratio (C/N ₀) information, and then uses this classification for determining the user’s position using 3DBM-predicted satellite visibility. Several other works have since expanded on this approach. Adjrd and Groves (2015) incorporated height aiding with shadow matching algorithm; Wang et al. (2015) improved the implementation efficiency of basic shadow matching for use in real-time applications; Yozevitch and Ben Moshe (2015) extended shadow matching by incorporating a particle filter-based weighting scheme for LOS/NLOS classification; Ahmad et al. (2013) and Bourdeau et al. (2012) used 3DBM and a ray-tracer to correct NLOS-based pseudoranges and incorporate these corrected measurements with LOS-based pseudoranges; Miura et al. (2013) and Suzuki and Kubo (2013) proposed a positioning method using corrected pseudorange with the help of a 3DBM; Gu et al. (2015) and Hsu et al. (2016a, b) used 3DBM for correcting pseudorange and comparing it with observed pseudorange to estimate position in urban canyons.

Previous research utilizing NLOS signals constructively using 3DBMs can be categorized as either shadow matching based or pseudorange based, where the latter is directly based on continuously tracking a signal or indirectly depends on output from continuously tracking receivers (in terms of reliable C/N ₀ estimate). However, snapshot-based positioning approaches (Fernandez-Hernandez and Borre 2016 and Qian et al. 2008) are increasing in popularity relative to continuously tracking receivers. Using a snapshot of GNSS data, the authors have previously demonstrated a signal delay matching technique for improved positioning accuracy in urban canyons, utilizing all NLOS signals constructively (Kumar and Petovello 2014). Unfortunately, that approach was limited in its ability to separate/estimate the LOS and NLOS signals.

In this paper, we describe a novel 3DBM-assisted positioning algorithm that provides accurate and reliable positioning in deep urban canyons by constructively using NLOS signals, using a snapshot of GNSS data. Compared with previous work, the proposed approach has the following novelties/contributions:

• 1. Whereas previous algorithms used pseudoranges and/or C/N ₀ estimates as inputs, the proposed approach uses raw correlator outputs generated from short snapshots of GNSS samples. In turn, this offers the following advantages:

  • By only using snapshots of data, the proposed method can be more power efficient (compared to signal tracking), can be used on an as-needed basis, and can provide a solution more quickly because a C/N ₀ estimate is unnecessary. Although previous work has demonstrated the constructive use of NLSO signals using corrected pseudoranges (such as Hsu et al. 2016a, b and Miura et al. 2013), this still requires the signal be tracked over time.

  • Obviating tracking loops avoids issues such as loss of lock due to signal attenuation and/or user motion, tracking loop instabilities (Graas et al. 2009), cross-correlation tracking, locking on to side peaks, and filtering effects when NLOS-only signals are received/tracked.

  • Using all correlator information avoids the loss of information resulting from reducing all correlator data into a single pseudorange (or code phase) measurement (He and Petovello 2014).

• 2. The approach does not perform LOS/NLOS characterization using C/N ₀ data, which is known to be ambiguous for this purpose (Ahmad et al. 2013). Moreover, in order to get a reliable C/N ₀ estimate in weak signal environments, tracking of the signal is required, which has limitations as mentioned in point 1 above. The proposed method uses ray-tracing to predict relative path delays and uses these as a priori information for estimating the received signal parameters from all correlator outputs thus making more complete use of all available information (He and Petovello 2014).

• 3. Because the approach uses relative path delay information, it is virtually unaffected by traditional GNSS error sources (receiver clock, atmospheric errors, orbit errors, etc.) since these are nearly exactly the same across multiple received paths.

• 4. In principle, the algorithm can compute a position using as little as one satellite, albeit with limited accuracy.

The primary objective of this paper is to introduce and evaluate a snapshot-based positioning algorithm that uses 3DBM data to constructively use NLOS signals to derive position solutions in urban canyon environments. The algorithm is tested and analyzed using real data collected in downtown Calgary, Canada, and is compared with results of traditional GNSS positioning algorithms. The contributions of this research are twofold. First, we introduce a novel 3DBM-assisted snapshot-based positioning algorithm that utilizes all NLOS signals constructively and validate its performance using real-world data. Second, we directly compare results against those from a commercial high-sensitivity receiver and demonstrate error reductions of at least 31 and 63% in the along-track and across-track directions, respectively. Moreover, results from the proposed method were obtained independently from epoch to epoch, suggesting that the use of a filter (e.g., a Kalman filter) would yield even smaller positioning errors.

Methodology

At a high level, the proposed algorithm is based on matching the observed signal parameters present in a GNSS receiver’s correlator outputs, with predicted signal parameters obtained from a 3DBM and a ray-tracing algorithm. By predicting the signal parameters at several candidate points, the candidate point closest to the true point should yield best agreement with the observed correlator outputs and that point will be declared as the final position estimate. Algorithm details are provided in the following section.

3DBM-assisted snapshot positioning algorithm

The block diagram of the 3DBM-assisted snapshot positioning algorithm is shown in Fig. 1 and consists of the following steps:

Fig. 1

High-level block diagram of 3DBM-assisted snapshot positioning algorithm

• 1. Obtain an approximate initial position using any available method (e.g., a standard GNSS receiver or WiFi).

• 2. Define a position grid (PG) around the initial position obtained in Step 1. Using the uncertainty of the initial position, the size of the PG is made large enough to contain the true position with sufficiently high probability. Each point in the PG is referred as a candidate point (CP).

• 3. Using a 3DBM, knowledge of satellite position (readily available from GNSS aiding sources) and a ray-tracing algorithm (“ray-tracer”), predict the following at each CP: (1) the availability of the LOS signal and (2) the number of NLOS signals along with their corresponding path delay(s) relative to LOS. Collectively, these values are referred to as the “predicted signal parameters” in the following.

• 4. Obtain correlator outputs from a GNSS receiver using a snapshot of signal samples. The correlator outputs contain the true signal parameters (including any LOS or NLOS signals) corresponding to the true location of the receiver and are thus referred to as observations, or “observed signal parameters,” in the following. In this work, we only consider the signal power (Z); ${\rm Z} = I^{2} \, + \, Q^{2}$ where I and Q are the in-phase and quadrature-phase correlator outputs, respectively, but the algorithm is amenable to using I and Q separately. The implementation used for this paper generates a grid (or block) of correlators spanning a range of code phase and Doppler values.

• 5. Match the predicted and observed signal parameters as described in the following subsection. Although a grid of correlators is generated, the peak correlator output is identified and only the correlators from the Doppler shift corresponding to the largest value in the correlator grid are extracted and used (i.e., we only use correlators spaced in the time, or code phase domain at a single frequency). In other words, a block of correlators is not required if a sufficiently good estimate of the signal Doppler is available (e.g., from aiding sources).

In summary, the algorithm predicts the received signal parameters at various positions within an area deemed likely to contain the true position and then selects the position whose predicted parameters most closely match what was observed. In the interest of space, details for Steps 1–4 are provided in Kumar and Petovello (2014) and are not repeated here. Step 5 is described in the next subsection.

Although not used in this work, the Doppler shift of the signal could conceivably be used to also estimate velocity, but this is left as future work.

Matching predicted and observed signal parameters

Matching of the observed and predicted signal parameters is performed using least squares (LSQ) residuals, and the CP with the smallest residuals (among all CPs) is selected as the final position estimate.

The first step is to use the total number of predicted signal paths (i.e., number of NLOS paths and the LOS path, if present) to select the mathematical model for the correlator outputs (“correlator model”) that, in turn, is used as the mathematical model for LSQ estimation. Since we observed a maximum of three signal paths at any given time instant in our data, the signal models are limited to the one-, two-, and three-path models as shown in Table 1, but increased number of paths could be considered, if necessary. In the table, subscripts 1–3 respectively correspond to the signals with shortest path, second shortest path, and third shortest path; A _n represents the signal amplitude of the n-th signal path after correlation; δ _nm is carrier phase difference between the n-th and m-th signal paths; τ _n is the absolute code delay corresponding to n-th signal path; R(τ _k ) is the autocorrelation function of the ranging code; $\tau_{\text{k}} = \tau_{\text{nco}} - \tau_{\text{n}}$ is delay; τ _nco is the locally generated code phase; and ς is noise. The correlator model proposed by Sharp et al. (2009) was compared against the correlator model from a Spirent simulator, and a correlation coefficient of approximately 0.99 was obtained, which is sufficient for this application (Kumar and Petovello 2015) although other well-fitting models could be used instead. For reasons that will be obvious below, we only estimate the absolute code phase of the shortest path and estimate the delay of all longer paths relative to the shortest path (even if the shortest path is NLOS), that is, τ _n  = τ ₁ + Δτ _n for n > 1.

Table 1 Correlator model and states for different signal path

The second step is to initialize the state vector (state vectors for each model are shown in Table 1) using the predicted relative path delay estimates, Δτ _n for n > 1. The corresponding a priori covariance matrix of the states P ₀ is also initialized based on the accuracy of the 3DBM used for the relative path delay predictions; states not corresponding to relative path delay are given an a priori variance of infinity. The LSQ estimates of the state vector are then obtained using iterative least squares as:

$$\delta X = (H^{T} W^{ - 1} H\text{ } + \text{ }P_{0}^{ - 1} )^{ - 1} H^{T} W^{ - 1} \delta z$$

(1)

where δX is the error in the current state estimates, H is the Jacobian matrix of the observations, W is measurement noise covariance matrix, and δz is the misclosure vector. The “ Appendix” Observation Matrix provides detailed expressions of H and W matrices.

The a priori covariance matrix is particularly important since without it the LSQ algorithm would theoretically converge to the same estimate for all CPs. In turn, the residuals for all CPs would be the same, meaning that the various CPs would be indistinguishable from each other in the context of the proposed positioning algorithm. The a priori covariance effectively limits how much a path delay estimate can change from its predicted value, meaning that predicted path delays with larger errors will converge to a more erroneous final estimate, thus yielding larger residuals.

It is also noted that the a priori covariance can help deal with under-determined estimation problems. This is not applicable in this work since our testing used 61 correlators in the time (code phase) domain, which is more than enough to estimate any of the state vectors in Table 1.

The final step is to compute the root-sum-of-square (RSS) of residuals for each CP for each satellite. The RSS of residuals at each CP is then root-sum-summed across all satellites at a given epoch to yield an overall RSS value. The CP with the smallest overall RSS is selected as the final position estimate. Using the above approach, if the signal model is correctly parameterized at all CPs, the LSQ residuals will nominally be smallest for the CP closest to the true location and will increase for CPs further from the true location. However, since the number of predicted signal paths may be different for different CPs, it is possible that the LSQ model will be either over- or under-parameterized (relative to the true signal). The effect of these two cases is as follows:

An under-parameterized model (i.e., predicting fewer signal paths that are actually received) will yield much larger residuals than a correctly parameterized model. In other words, no special steps are needed to handle this specific case.

The over-parameterized model (i.e., predicting more signal paths that are actually received) will yield artificially small residuals because of the increased degrees of freedom. Since incorrectly predicting the total number of signal paths will only occur at incorrect CPs, this situation needs to be identified in order to avoid accidentally selecting these “incorrect CPs” as the final estimate.

With this in mind, an over-parameterized model should estimate a very small (ideally zero) amplitude for signal paths that are not actually present in the observed data, and a threshold for the multipath-to-direct ratio (MDR _n  = A _n /A ₁ for n > 1) is used to identify over-parameterization. The MDR threshold was selected using the simulations described in Kumar and Petovello (2015). In summary, these consisted of simulating 21,000 correlator grids corresponding to different NLOS signal characteristics (i.e., relative amplitude, delay, and phase with respect to LOS signal as well as different number of paths). For each simulated correlator grid, LSQ estimates were then obtained using all of the models in Table 1, thus including under-, over-, and correctly parameterized solutions. The cumulative distribution function (CDF) of the estimated MDR for the different solutions is shown in Fig. 2 where all over- and under-parameterized results are grouped together; for example, over-parameterizing a single-path case with two- and three-path models is shown together since the degree/extent of over-parameterization is irrelevant. Based on these results, if the computed MDR falls below 0.09, an over-parameterization is detected and that CP’s RSS of residuals is set to a very large value.

Fig. 2

Cumulative distribution function (CDF) of estimated MDR values for over-parameterized, correctly parameterized, and under-parameterized cases

Before presenting the results, a short discussion of the algorithm’s expected performance will be helpful. As shown in Kumar and Petovello (2014), predicted delays vary most quickly in the direction perpendicular to a reflector. It follows, therefore, that the (dis)agreement between the predicted and observed signals (as reflected in the LSQ residuals) will vary most quickly in this direction as well. In other words, the algorithm is expected to be more sensitive in this direction. Extending this logic to urban canyons, since reflectors (buildings) are typically parallel to the direction of travel and on either side of the user, the algorithm is expected to be most sensitive (i.e., give the best results) in the across-track direction.

Data collection and processing

The algorithm was tested with data collected in downtown Calgary, Canada. The data collection setup consisted of a NovAtel SPAN-LCI reference system, a National Instruments (NI) front-end for L1 intermediate frequency (IF) sample recording at 20 Msps, a NovAtel antenna, and a base station. The differential GNSS/INS reference trajectory was obtained from NovAtel’s Inertial Explorer software using a tightly coupled forward and backward smoothing configuration and is shown in the upper plot in Fig. 3. The vehicle traveled with a maximum speed of about 15 m/s, and the trajectory spanned approximately 3.5 km of road and included deep and mild urban environments; the lower plot in Fig. 3 shows the percent of sky visible as computed from the 3DBM at the reference position. Positions were also logged from a u-blox 6 receiver for comparison purposes.

Fig. 3

Downtown Calgary data collection trajectory. Top figure shows the trajectory along with the building heights, and the bottom figure shows the percentage sky visibility at each location

The IF data were processed using the University of Calgary’s GSNRx™ software receiver (Petovello et al. 2009), and the correlator outputs were saved to file at a rate of 1 Hz. The version of GSNRx™ used was based on a block processing strategy which was suitable for generating multiple correlators. The parameter configuration for the block processing is summarized in Table 2, although a selection of results with different parameters are briefly presented later for comparison purposes. For this work, only the GPS C/A code signal was used.

Table 2 Summary of processing parameters

The coherent integration time was initially selected to be 100 ms to ensure high signal-to-noise ratios during algorithm development. In order to enable longer coherent integration, the base station data were used for bit wipe-off. The PG was only defined in the horizontal plane, and the vertical position was constrained to the true height of the receiver. Although this was done primarily to limit the number of computations, it is nevertheless a reasonable implementation since the height of the user could also be estimated from the 3D model, assuming that the user is on the ground (or a fixed height above it).

The 3DBM spanned an area surrounding downtown Calgary and was purchased from 3D CAD browser (www.3dcadbrowser.com) in the “Wavefront Advanced Visualizer” format. The model has a quoted accuracy of 3 m and contained 400,668 polygons. The model was obtained by first extracting building footprints and then associating a height to each building—as such, details about building facades are not provided. A MATLAB-based reader was used to extract all vertex coordinates, transform them to the WGS 84 reference system, and store them for later processing. The ray-tracer was implemented in MATLAB using a simple ray-triangle intersection model (Bradbury et al. 2007). The rays were launched from the satellite toward each polygon in the model. Using the method described in Kumar and Petovello (2014), only those paths for which the signal reached the receiver, either directly or after a single bounce, were considered. The path delay of each reflected signal relative to LOS was also recorded; if necessary, these were differenced to yield delays relative to the shortest NLOS path. As noted above, double- or triple-bounce reflections (or more) are not predicted and may thus limit the number and quality of matches with the observed data.

In order to test the feasibility of the algorithm and to reduce processing requirements, the initial user position was replaced with the “true” position from the reference trajectory. The inherent assumption with this approach is that if the receiver’s estimated position were used with a larger PG (to accommodate the corresponding uncertainty in the estimate), the selected position would be the same as with a smaller PG. This assumption has been confirmed with empirical testing (shown later), and hence, the results presented are also indicative of what is possible without a reference solution.

Finally, to be truly indicative of snapshot-based positioning algorithms, the results presented below do not include any filtering (e.g., Kalman filtering). By extension, filtering of the results should improve the overall performance, although this was not evaluated as part of this work.

Experimental results and analysis

Before presenting the statistics and performance comparison with other receivers for the entire trajectory, an in-depth analysis for two different points along the trajectory is presented to highlight key findings. The two points have sky visibilities of 25 and 65% and are shown in Fig. 4; the upper pictures show the surrounding buildings, and the lower plots are the idealized skyplots showing sky (blue) and buildings (gray) as computed from the 3DBM.

Fig. 4

Points considered for detailed analysis; upper figures show the surrounding environment with the approximate user location represented as a white triangle and the lower figures are skyplots showing sky (blue) and buildings (gray) computed from the 3DBM

Detailed analysis of point 1 (25% sky visibility)

Figure 5 shows the RSS of residuals at each CP for different PRNs for point 1 [RSS values are normalized to the range of (0, 1) to simply plotting]. The first thing to notice is that the RSS values are nearly binary in nature (PRN 31 is an exception and is discussed below). Higher RSS values (red) correspond to under- and over-parameterized CPs; lower RSS values (blue) correspond to correctly parametrized CPs (there are small variations within the blue regions, but these are not distinguishable at this scale).

Fig. 5

RSS of residuals for different PRNs at point 1

Next, the “shape” of the RSS plots differs between satellites because of the different locations of the satellites relative to the user and surrounding buildings. The left half of the plot for PRN 1 is a good example of this: Each of the three blue regions corresponds to an area where the predicted signal reflects off of a different building. The other PRNs have different patterns because their predicted signals involve different buildings. The exception to this is PRN 31, which is predicted to have a single path at all CPs. The single-path model does not receive any a priori information (i.e., no predicted relative path delays), so the LSQ estimate is completely unconstrained and converges to the same solution at all CPs; hence, there are no variations in the RSS values (and the normalized RSS value will be unity). In other words, the proposed algorithm only makes use of reflected signals and does not use LOS signals at all (including LOS data are left as future work). With this in mind, PRN 11 was also a single-path satellite and is thus not shown. These plots also demonstrate that a position estimate can be obtained using only a single satellite with multiple paths; for the results shown, using either PRN 1, PRN 14, or PRN 22 only yields position errors of 4.5, 9.8, and 5.4 m, respectively.

Figure 6 shows the overall RSS across all satellites at each CP, and the final position estimate is indicated with a white star. In this case, despite only using information from three satellites, the position estimate has an error of 3.6 m, about 1 m across-track and 3 m along-track (the vehicle was moving east/west). This contrasts with traditional GNSS methods where the across-track error in urban canyons is typically larger than the along-track error due to poor across-track satellite geometry/visibility (Groves 2011; Ward et al. 2006) but is consistent with the expected performance (see closing paragraph of the “Methodology” section). The final point is that the blue area containing the smallest RSS values spans a relatively small region, about 2–3 m in each horizontal direction. This suggests that the solution is fairly strong in both the along- and across-track directions although quantifying the solution uncertainty is left for future work.

Fig. 6

Overall RSS of residuals from all PRNs and final estimated position (white star) at the point 1

Detailed analysis of point 2 (65% sky visibility)

The RSS of residuals for three different PRNs and the overall RSS at point 2 are shown in Figs. 7 and 8, respectively. In addition to the satellites shown in Fig. 7, PRNs 11, 22, and 31 were single-path satellites and thus not shown.

Fig. 7

RSS of residuals from PRN 1, 14, and 32 at Point 2

Fig. 8

Overall RSS of residuals from all PRNs and final estimated position (white star) at the Point 2

Comparing these results with those of point 1, it is obvious that RSS patterns are quite different and that they are more widely spread in the east/west direction (direction of travel). The reason for this is that there are fewer buildings that come into play at this location, and the buildings are located on only one side of the road (see Fig. 4). This means that CPs in the along-track direction predict similar path delays and hence the variability of the residuals is much smaller. It is therefore not surprising that the position error (8.4 m) is larger than at point 1 (3.6 m). This uncertainty is indirectly shown in Fig. 8 where the area with the smallest RSS value is much more spread in the along-track direction.

Analysis of entire trajectory

To extend the above analysis, Fig. 9 shows the horizontal position error with respect to sky visibility for all points in the data set. Results from two traditional pseudorange-based receivers are shown for comparison: One is a high-sensitivity version of our GSNRx™ software receiver, and the other is a u-blox 6 receiver. For the proposed algorithm, there is a clear relationship between position error and sky visibility with lower sky visibility yielding more accurate position estimates. This is opposite of what is expected (and observed) with traditional GNSS receivers, which perform better as sky visibility increases.

Fig. 9

Horizontal error with respect to sky visibility for proposed algorithm and two pseudorange-based high-sensitivity receivers

It is also worth noting that the two pseudorange-based receivers contain large biases for sky visibilities ranging from about 30–50%; this is almost certainly caused by the receivers’ position filters “locking on” to a poor (biased) solution that is only corrected once the receiver reaches an area with more and better measurements. Although this suggests there may be room for improving the pseudorange-based receivers, it also shows the benefit of the proposed algorithm. Specifically, the proposed method provides better results in most cases despite using a snapshot-based approach (thus offering power savings) and no filtering. By extension, filtering the results from the proposed solution would likely yield even better performance.

The error statistics for all the three solutions are summarized in Table 3, and the corresponding improvement of the proposed method’s RMS errors is shown in Table 4. Overall, error statistics of the proposed algorithm are best among all solutions. Moreover, the improvement in the across-track accuracy is profound (31 or 63%, at least) due to the inherent weakness of pseudorange-based methods in this regard. Interestingly, the along-track error of the proposed algorithm is also better than that of the other receivers with RMS position error improvements of at least 31%. Finally, the horizontal error of the proposed algorithm is 53–71% better than what is possible with traditional methods. Collectively, these results demonstrate that the proposed algorithm is a viable alternative to pseudorange-based algorithms in urban canyon environments.

Table 3 Summary of error statistics for different solutions

Table 4 RMS positioning improvement using the proposed algorithm

Discussion

As a preliminary assessment of the sensitivity of the algorithm, the data were reprocessed using two separate changes in the processing parameters listed in Table 2:

• Using 20 ms coherent integration yields an RMS horizontal error of 14.1 m, 14% higher than for 100 ms of coherent integration due to the lower signal-to-noise ratios involved.

• Using 5 m CP spacing with PGs of size ±15 and ±100 m yields RMS position errors of 15.4 and 15.8 m, respectively. Although the larger CP spacing increases in RMS relative to Table 3, increasing the grid size to accommodate larger position uncertainties does not adversely affect performance. A larger PG can therefore avoid situations where the PG does not contain the true position, for which the proposed algorithm would still select the CP with the smallest overall RSS and would be biased.

Finally, although not done here, 3DBM data could be integrated with GNSS in other ways and the algorithm presented here should be compared against such approaches to assess the relative metrics and drawbacks. For example, the 3DBM could be used with traditional pseudorange measurements to apply height constraints; apply constraints on the direction of travel; and remove signals with no LOS signals and/or many NLOS signals. Such implementations may offer benefits in terms of simplicity but may not use NLOS signals constructively. Such comparisons, although use 3DBM, are beyond the scope of this paper and are left as future work.

Conclusions

This paper presents a 3D building model-assisted technique that uses a snapshot of GNSS data and non-line-of-sight signals to derive a user’s position in urban canyons. The feasibility of the proposed algorithm was evaluated using real data collected in downtown Calgary, Canada. Key findings include:

• The proposed algorithm provides more accurate position estimates in areas with low sky visibility (as low as 20% above 0° elevation). RMS position errors in the along-track and across-track directions were both below 10 m (with slightly better across-track performance), and the RMS horizontal error was 12.4 m.

• Compared with traditional pseudorange-based approaches from two different receivers, RMS position errors were improved by at least 31, 63, and 53% in the along-track direction, across-track direction, and horizontal plane, respectively.

Collectively, results show that the proposed method is a viable alternative/improvement to pseudorange-based approaches in urban areas and offers great potential for enabling the expansion of GNSS-based applications to such environments. Furthermore, with low cost of 3DBMs, the proposed algorithm is a possible answer for increasing demand of low-cost positioning solution in urban environments, ranging from lane-level driving to guiding visually impaired pedestrian.

Appendix

Observation matrix (H)

This appendix shows the observation matrix for different path models. Using states and observation models from Table 1, the observation matrix for different path model can be derived as below.

In following equations of observation matrix, we have used the following notations:

$$R^{'} \left( {\tau_{k} } \right) = \frac{{\partial R\left( {\tau_{k} } \right)}}{{\partial \tau_{k} }}$$

where R(τ _k ) is the autorotation function as

$$R(\tau_{k} ) = A_{c} \times \left( {1 - \sqrt {\left( {\tau_{nco} - \tau_{k} } \right)^{2} + \sigma^{2} } } \right)$$

where A _c is a constant and obtained from simulations, and σ corresponds to bandwidth loss; details are explained in Sharp et al. (2009). As explained in the Methodology section, R(τ _k ) = R(τ ₁ + Δτ _k ); k > 1.

One-path signal model

$$\frac{\partial Z}{{\partial A_{1} }} = \left( {2 \times A_{1} \times R^{2} \left( {\tau_{1} } \right)} \right)$$

$$\frac{\partial Z}{{\partial \tau_{1} }} = \left( {2 \times A_{1}^{2} \times R\left( {\tau_{1} } \right) \times R^{'} \left( {\tau_{1} } \right)} \right)$$

Two-path signal model

$$\frac{\partial Z}{{\partial A_{1} }} = \left( {2 \times A_{1} \times R^{2} \left( {\tau_{1} } \right)} \right) + \left( {2 \times A_{2} \times R\left( {\tau_{1} } \right) \times R\left( {\tau_{2} } \right) \times \cos \left( {\delta_{12} } \right)} \right)$$

$$\begin{aligned} \frac{\partial Z}{{\partial \tau_{1} }} = \left( {2 \times A_{1}^{2} \times R\left( {\tau_{1} } \right) \times R^{'} \left( {\tau_{1} } \right)} \right) + \left( {2 \times A_{1} \times A_{2} \times \cos \left( {\delta_{12} } \right) \times \left( {R^{'} \left( {\tau_{1} } \right) \times R\left( {\tau_{2} } \right) + R^{'} \left( {\tau_{2} } \right) \times R\left( {\tau_{1} } \right)} \right)} \right) \\ + \left( {2 \times A_{2}^{2} \times R\left( {\tau_{2} } \right) \times R^{'} \left( {\tau_{2} } \right)} \right) \\ \end{aligned}$$

$$\frac{\partial Z}{{\partial A_{2} }} = \left( {2 \times A_{2} \times R^{2} \left( {\tau_{2} } \right)} \right) + \left( {2 \times A_{1} \times R\left( {\tau_{1} } \right) \times R\left( {\tau_{2} } \right) \times \cos \left( {\delta_{12} } \right)} \right)$$

$$\frac{\partial Z}{{\partial \Delta \tau_{2} }} = \left( {2 \times A_{2}^{2} \times R\left( {\tau_{2} } \right) \times R^{'} \left( {\tau_{2} } \right)} \right) + \left( {2 \times A_{1} \times A_{2} \times R\left( {\tau_{1} } \right) \times R^{'} \left( {\tau_{2} } \right) \times \cos \left( {\delta_{12} } \right)} \right)$$

$$\frac{\partial Z}{{\partial \delta_{12} }} = - \left( {2 \times A_{1} \times A_{2} \times R\left( {\tau_{1} } \right) \times R\left( {\tau_{2} } \right) \times \sin \left( {\delta_{12} } \right)} \right)$$

Three-path signal model

$$\frac{\partial Z}{{\partial A_{1} }} = \left( {2 \times A_{1} \times R^{2} \left( {\tau_{1} } \right)} \right) + \left( {2 \times A_{2} \times R\left( {\tau_{1} } \right) \times R\left( {\tau_{2} } \right) \times \cos \left( {\delta_{12} } \right)} \right) + \left( {2 \times A_{3} \times R\left( {\tau_{1} } \right) \times R\left( {\tau_{3} } \right) \times \cos \left( {\delta_{13} } \right)} \right)$$

$$\begin{aligned} \frac{\partial Z}{{\partial \tau_{1} }} = \left( {2 \times A_{1}^{2} \times R\left( {\tau_{1} } \right) \times R^{'} \left( {\tau_{1} } \right)} \right) + \left( {2 \times A_{2}^{2} \times R\left( {\tau_{2} } \right) \times R^{'} \left( {\tau_{2} } \right)} \right) + \left( {2 \times A_{3}^{2} \times R\left( {\tau_{3} } \right) \times R^{'} \left( {\tau_{3} } \right)} \right) \\ + \left( {2 \times A_{1} \times A_{2} \times \cos \left( {\delta_{12} } \right) \times \left( {R^{'} \left( {\tau_{1} } \right) \times R\left( {\tau_{2} } \right) + R^{'} \left( {\tau_{2} } \right) \times R\left( {\tau_{1} } \right)} \right)} \right) \\ + \left( {2 \times A_{2} \times A_{3} \times \cos \left( {\delta_{23} } \right) \times \left( {R^{'} \left( {\tau_{2} } \right) \times R\left( {\tau_{3} } \right) + R^{'} \left( {\tau_{3} } \right) \times R\left( {\tau_{2} } \right)} \right)} \right) \\ + \left( {2 \times A_{1} \times A_{3} \times \cos \left( {\delta_{13} } \right) \times \left( {R^{'} \left( {\tau_{1} } \right) \times R\left( {\tau_{3} } \right) + R^{'} \left( {\tau_{3} } \right) \times R\left( {\tau_{1} } \right)} \right)} \right) \\ \end{aligned}$$

$$\frac{\partial Z}{{\partial \delta_{12} }} = - \left( {2 \times A_{1} \times A_{2} \times R\left( {\tau_{1} } \right) \times R\left( {\tau_{2} } \right) \times \sin \left( {\delta_{12} } \right)} \right)$$

$$\frac{\partial Z}{{\partial A_{2} }} = \left( {2 \times A_{2} \times R^{2} \left( {\tau_{2} } \right)} \right) + \left( {2 \times A_{1} \times R\left( {\tau_{1} } \right) \times R\left( {\tau_{2} } \right) \times \cos \left( {\delta_{12} } \right)} \right) + \left( {2 \times A_{3} \times R\left( {\tau_{2} } \right) \times R\left( {\tau_{3} } \right) \times \cos \left( {\delta_{23} } \right)} \right)$$

$$\begin{aligned} \frac{\partial Z}{{\partial \Delta \tau_{2} }} = \left( {2 \times A_{2}^{2} \times R\left( {\tau_{2} } \right) \times R^{'} \left( {\tau_{2} } \right)} \right) + \left( {2 \times A_{1} \times A_{2} \times R\left( {\tau_{1} } \right) \times R^{'} \left( {\tau_{2} } \right) \times \cos \left( {\delta_{12} } \right)} \right) \\ + \left( {2 \times A_{2} \times A_{3} \times R^{'} \left( {\tau_{2} } \right) \times R\left( {\tau_{3} } \right) \times \cos \left( {\delta_{12} } \right)} \right) \\ \end{aligned}$$

$$\frac{\partial Z}{{\partial \delta_{23} }} = - \left( {2 \times A_{2} \times A_{3} \times R\left( {\tau_{2} } \right) \times R\left( {\tau_{3} } \right) \times \sin \left( {\delta_{23} } \right)} \right)$$

$$\frac{\partial Z}{{\partial A_{3} }} = \left( {2 \times A_{3} \times R^{2} \left( {\tau_{3} } \right)} \right) + \left( {2 \times A_{2} \times R\left( {\tau_{2} } \right) \times R\left( {\tau_{3} } \right) \times \cos \left( {\delta_{23} } \right)} \right) + \left( {2 \times A_{1} \times R\left( {\tau_{1} } \right) \times R\left( {\tau_{3} } \right) \times \cos \left( {\delta_{13} } \right)} \right)$$

$$\begin{aligned} \frac{\partial Z}{{\partial \Delta \tau_{3} }} &= \left( {2 \times A_{3}^{2} \times R\left( {\tau_{3} } \right) \times R^{'} \left( {\tau_{3} } \right)} \right)\\ & \quad + \left( {2 \times A_{2} \times A_{3} \times R\left( {\tau_{2} } \right) \times R^{'} \left( {\tau_{3} } \right) \times \cos \left( {\delta_{23} } \right)} \right) \\ &\quad + \left( {2 \times A_{1} \times A_{3} \times R\left( {\tau_{1} } \right) \times R^{'} \left( {\tau_{3} } \right) \times \cos \left( {\delta_{13} } \right)} \right) \\ \end{aligned}$$

and δ ₁₃ = δ ₁₂ + δ _23.

Measurement noise covariance matrix (W)

The W matrix defined below is a fully populated matrix, where off-diagonal elements are correlated according to the ranging code’s autocorrelation function. Assuming n observations (correlator outputs) for a given satellite, the matrix can be written as:

$$W = \sigma^{2} \begin{array}{*{20}l} 1 \hfill & {R(\tau_{2} )} \hfill & \ldots \hfill & {R(\tau_{n - 1} )} \hfill & {R(\tau_{n} )} \hfill \\ {R(\tau_{1} )} \hfill & 1 \hfill & \ldots \hfill & {R(\tau_{n - 1} )} \hfill & {R(\tau_{n} )} \hfill \\ \ldots \hfill & \ldots \hfill & \ldots \hfill & \ldots \hfill & \ldots \hfill \\ {R(\tau_{1} )} \hfill & {R(\tau_{2} )} \hfill & \ldots \hfill & 1 \hfill & {R(\tau_{n} )} \hfill \\ {R(\tau_{1} )} \hfill & {R(\tau_{2} )} \hfill & \ldots \hfill & {R(\tau_{n - 1} )} \hfill & 1 \hfill \\ \end{array}$$

where R(τ _i ) is the value of the autocorrelation function at the code phase delay corresponding to the ith correlator and σ is variance of the measurement post-correlation, as defined in Chapter 6 of Van Diggelen (2009).