Abstract
As the dependence of Global Navigation Systems (GNSS) increases, so does a growing demand for GNSS accuracy in urban environments. This research aims to improve navigation in these environments by integrating non-line-of-sight signals, building models, and measured signal to noise ratios in ways not typically used in GNSS positioning. We propose a technique of combining elements of shadow matching, non-line-of-sight signal prediction through ray tracing, and collaborative navigation. A specularity metric is developed, which predicts the likelihood of building reflections resulting in non-line-of-sight signal reception, and is used in conjunction with shadow matching techniques to improve positioning. A framework for implementing these approaches is presented and demonstrated using improved positioning techniques built and tested using real-world data collected in urban surroundings.
1 INTRODUCTION
A growing number of location-based services rely on GNSS technology for navigation. Users depend on these services working reliably in urban areas where conventional methods for GNSS positioning perform poorly due to tall, densely spaced buildings, which block many of the direct line-of-sight (DLOS) GNSS signals. With few DLOS satellites available to form the solution, a stand-alone GNSS receiver cannot obtain accurate positioning. Additionally, the geometry of the satellites that are visible along the DLOS is usually poor due to the nature of urban canyons— that is, DLOS signals along the direction of the city street are likely to be visible, whereas DLOS signals in the across-street direction are likely to be blocked by a wall of tall buildings. Few satellites are visible via the DLOS, but their signals can reach the receiver via the non-line-of-sight (NLOS) path after reflecting off the surrounding buildings. When conventional positioning methods use NLOS signals without taking into account the signal’s indirect path to reach the GNSS user, the position solution is degraded (Groves, 2013; Groves, Jiang, Rudi, & Strode, 2013).
This research focuses on the urban environment of Denver, Colorado. Denver is a moderately sized city, with an approximate population of 700,000 within the city and a larger metropolitan population just under three-million residents. In 2019, Denver was the fifth fastest growing city of the thirty-five largest cities in the United States with populations over one-half million (U. S. C. Bureau, 2019).
Denver’s rapid growth and the accompanying increase in high-rise building developments has created complications for GNSS-dependent commuters. The substantial development of high-rise buildings within the city has caused issues related to poor GPS signal reception. In December 2018, news articles reported unacceptable metro-commuter rail delays attributable to GPS initialization failures at some downtown stops and stations (Aguilar, 2018). Tall office buildings, like those rapidly being built in Denver and other growing cities, are an issue for GPS positioning. They tend to obstruct the DLOS visibility to GNSS satellites. Additionally, the reflective building materials cause strong NLOS signals as the relative permittivity, η′, of glass (η′ = 6.27) is higher than other building materials like concrete (η′ = 5.31) and brick (η′ = 3.75) (International Telecommunication Union—Radiocommunication Sector, 2015).
Improvement of GNSS navigation in urban environments like Denver requires a multifaceted approach. This research presents techniques to enhance GNSS positioning with shadow matching (SM), NLOS prediction, and collaborative localization. We build upon previously developed SM techniques by incorporating our proposed method, which we term as specular matching (SPM). SPM predicts NLOS signal reception by calculating a specularity value to predict reflective regions of the surrounding city.
Our research also focuses on the benefits of using collaborative localization in combination with SM and SPM. Collaborative localization is particularly applicable for navigation in urban environments where GNSS receivers within the span of a city block can potentially experience distinguishably different signal environments. When implementing collaborative localization, we assume the relative receiver positions (relative receiver formation) are known. A relative receiver formation can be applied to the specific example of GNSS receivers implemented in city rail networks as multiple receivers can be positioned in a fixed formation on train cars. But it is expandable to many other applications in GNSS urban navigation, including a network of uncrewed aerial vehicles or a fleet of ground vehicles.
In this paper, we introduce the potential localization improvements through SM and SPM when GNSS receivers work collaboratively. We consider a specific case of collaborative receivers where the relative positions of the receivers are known. We localize the center of the formation by consensus and not by each agent itself. The focus of this paper will not deal with the practical implementation of this collaboration, e.g., communication links, ranging technology, etc. For this study, we assume an implementation that allows for the sharing of data between receivers.
2 BACKGROUND
In recent years, a diverse set of techniques to improve urban navigation, given information regarding the surrounding environment, has been assembled (Adjrad & Groves, 2017a, 2017b; Betaille, Peyret, Ortiz, Miquel, & Fontenay, 2013; Bourdeau, Sahmoudi, & Tourneret, 2012; Bradbury, Ziebart, & Cross, 2007; Groves, 2011; Groves & Adjrad, 2017a, 2017b; Groves & Jiang, 2013; Groves et al., 2013; Groves, Jiang, Wang, & Ziebart, 2012; Hsu, Gu, & Kamijo, 2016; Kbayer, Sahmoudi, & Chaumette, 2015; Kumar & Petovello, 2014; Meguro, 2009; Miura, Hsu, Chen, & Kamijo, 2015; Obst, Bauer, & Wanielik, 2012; Peyraud et al., 2013; Suzuki, 2016; Suzuki & Kubo, 2012; Tanwar & Gao, 2018; Wang, Groves, & Ziebart, 2012a, 2012b, 2015; Wang, Groves, & Ziebart, 2012; Yozevitch & Ben Moshe, 2015). These techniques include 3D models of major cities, made more available within the last decade through organizations like OpenStreetMap (OpenStreetMap) or local government projects like Denver Regional Council of Governments (DRCOG, 2016). Some approaches seek to use the additional model information to mitigate the effects of NLOS signals (Groves & Jiang, 2013; Groves et al., 2013; Meguro, 2009; Obst et al., 2012; Peyraud et al., 2013), while others use the 3D models to effectively incorporate the NLOS signals and use them as additional information for positioning (Bradbury et al., 2007; Groves & Adjrad, 2017; Groves et al., 2012; Suzuki & Kubo, 2012).
SM is a primary method of using a 3D city model to improve GNSS positioning and navigation. SM finds the most likely user location using the visibility predictions from the 3D model compared to the reported GNSS satellite SNR values (Groves, 2011). The underlying concept can be understood by looking at a single satellite’s DLOS visibility. In an urban canyon, the signal from the satellite will be blocked at certain locations and visible to a receiver in other locations within the canyon (Figure 3). If the signal is acquired by the receiver, the user is more likely to be located in regions where the city building model predicts a clear DLOS signal (visible regions), than in a location predicted to have a blocked DLOS (shadowed regions). Conversely, signals that are absent and not acquired by the receiver indicate that the user is more likely at a location where the model predicts the signal to have a blocked DLOS. In this way, the visibility information for a satellite contributes to the position determination regardless of whether its signal is received or absent.
Population increase of the 35 largest cities in the United States (USCB 2019)
Sky plot of the buildings surrounding Denver’s Union Station in 2014 (left) and the sky plot for the same location in 2019 (right)
Diagram of regions that are shadowed and visible to a GNSS satellite in an urban canyon
SM techniques begin by selecting a search region around an assumed position solution. Within that search region, the SM algorithm selects a set of candidate locations at which the building model is used to predict the visibility of each satellite. A scoring scheme compares the visibility predictions to the signal strength values. Each candidate location receives a score that represents the likelihood the GNSS user is located at that particular position. The simplest form of a scoring scheme for SM consists of a binary prediction and a binary observation (Table 1). A satellite is predicted to be invisible or visible to the user at the candidate location based on the city model, and the receiver tracking results classifies whether it is a strong signal or a weak (or not-tracked) signal. Satellites predicted to be invisible with observed signals that are weak or not-tracked receive a score of one. Similarly, satellites predicted to be visible that show strong signals also receive a score of one. In both of these two cases, the observation fits what the visibility calculation predicts. In all other cases, the score assigned by the algorithm is zero. The score, fpos, at each candidate location, p, is a sum of individual scores, fsat, for each satellite, s, of the m satellites above the horizon as shown in Equation (1) (Wang et al., 2012a):
Basic SM Scoring Scheme
1
where SS indicates the particular scoring scheme used. Thus, a candidate location with many observations that match with the model predictions would have a score higher than candidate locations with little consistency between the observations and model. Prior work in SM techniques have shown results with meter-level accuracies in the across-street direction in dense urban areas (Groves & Adjrad, 2017).
Wang et al. (2012a) first introduced optimized scoring schemes to go beyond the binary observation and prediction table and take into account intermediate values. This scheme distinguishes three types of observations: not-tracked, weak signals, and strong signals. It also distinguishes three types of predictions: invisible, diffracted, and visible. Their method uses the term diffracted signals to refer to conditions when the DLOS is blocked but passes within three degrees of the building boundary on the sky plot. This scoring scheme allows the SM algorithm to incorporate weak diffracted signals (Table 2).
Optimized Scoring Scheme
Wang et al. (2015) also introduced another scoring scheme with a higher level of complexity that implements a Bayesian technique in which sample statistics help determine whether a signal is DLOS. This technique determines the probability that a signal is DLOS given the SNR value received and based on a previously observed dataset with a known user location. Wang demonstrated that the probabilistic SM performs better than conventional SM with a binary prediction and observation scoring scheme. However, though this probabilistic approach is rigorous, it requires obtaining SNR test data in a known location to form two separate NLOS and DLOS distributions.
Yozevitch and Ben Moshe (2015) proposed implementing a SM algorithm within a modified particle filter. Particle filters are suitable for SM because there is a defined region of interest and each location within that region is weighted. The implementation of the modified particle filter relies on the velocity magnitude and the shadow matching scoring scheme (simple binary prediction and observation scoring scheme). Though the approach shows promising results in the simulated data, the experimental results from this implementation were found to be inferior due to strong NLOS signals (Yozevitch & Ben Moshe, 2015).
An alternative to SM to improve GNSS positioning is map-aided ranging techniques. Unlike shadow matching, ranging techniques require the use of the GNSS pseudorange measurements of each satellite. However, many techniques resemble shadow matching in the way they consider candidate locations and DLOS prediction. For instance, in one such method proposed by Suzuki (2016), the least-squares solution at each candidate location is computed using only the pseudorange measurements observed from satellites that the city model predicts to be DLOS. The most likely candidate location is chosen as the one closest in distance to its respective, newly computed position solution. The likelihood of each candidate in this method is used as the weight in a particle filter. A different approach proposed by Adjrad and Groves (2017b) selects candidates within a search radius and then computes DLOS visibility of each satellite for each given candidate location. Then the algorithm calculates a new least-squares position solution with weights for each satellite based on the percentage of candidate locations where the satellite is visible through DLOS. The solution assigns larger weights to satellites with a higher percentage of predicted visibility across the search radius and lower weights to frequently blocked satellites.
For many different applications, collaborative localization techniques have been developed to aid the navigation of cooperative, participating agents. Tanwar and Gao (2018) have proposed using SM techniques in conjunction with collaborative localization. In these techniques, the collaborative agents are able to communicate their estimated positions and relative positions to one another (de-centralized) or to a fusion center (centralized). They developed a method of incorporating decentralized collaborative localization with visibility calculations related to SM, and agents measure their inter-agent ranges. The method mitigates SM ambiguities by employing the inter-agent ranging as an additional source in intelligent urban positioning (IUP). In their work, the dataset is simulated, and the method is shown to produce lower RMS positioning error than SM alone.
The methods mentioned in this section highlight a few implementations of SM techniques used to improve urban GNSS positioning that our method expands upon by introducing elements of NLOS prediction and known relative receiver formation collaborative localization. The details of our techniques and the similarities and differences from the previous work mentioned here are discussed in the method section.
3 DATA COLLECTION
To get a realistic set of urban tracking results, we performed three experiments (Exp1, Exp2, and Exp3) in downtown Denver (Figure 4) with several GNSS receivers. The receivers were GNSS-enabled Android phones, running a custom application (Strizic, Akos, & Lo, 2018) that retrieves NMEA message data. NMEA GPGSV messages with position solutions (latitude, longitude, and altitude) and individual satellite signal strength (SNR levels for each PRN used in calculation of position solution) were recorded at approximately one-second intervals.
Map of the locations of the three experiments (top) and the sky plot generated from Google maps imagery for the center of the three experiments (bottom).
The receivers were stationary throughout the entire duration of each experiment. In experiment Exp1, the receiver locations were collocated. In Exp2 and Exp3, the receivers were dispersed along the street block (Table 3). The spacing of the receivers in Exp2 and Exp3 is shown in Figure 5 and Table 3.
Experiment timeframe and receiver locations
Receiver positions in three experiments, Exp1 (left), Exp2 (center), and Exp3 (right). Images obtained from Google Maps
In all experiments, the truth location for the receivers is determined based on landmark positioning with Google maps. The position accuracy for the truth locations is determined to be 1-2 meters, based on the technical specifications of Google imagery and our landmark positioning accuracy (Google, 2020).
4 METHOD
To implement SM and our new methods, we have developed a framework to use readily available Digital Elevation Models (DEMs) and 3D building models to determine visibility conditions within a city (Figure 6) (Strandjord & Axelrad, 2018). In 2016, the DRCOG (2016) used aerial imagery to create the delineation of building footprints in Denver and nearby regions. The building footprints included in the dataset have a building top area of at least 48 square feet, at a height of over 5 feet. The data has a 3-inch resolution and a 6-inch RMSE accuracy. From these datasets, we create 3D triangular meshes defined in an east-north-up coordinate system such that the terrain structure and building model are optimized to support efficient ray tracing using rendering tools from the physically-based ray tracer (PBRT) (Pharr & Humphreys, 2010) software package. The terrain and 3D building faceted models can be quickly ray traced in the form of a k-d tree, which achieves a search time complexity of 𝒪(log n) on average for n facets in the scene.
Framework for software created for analyzing GPS signals in Denver urban environment using Qt and C++. Building model is rendered from software written using OpenGL for visualization. Building model is interrogated from software written using PBRT library of ray-tracing methods. Inputs to software include data from DRCOG, USGS, GNSS_Logger Android app, and GPS broadcast messages.
PBRT is used to trace the signals sent by satellites to a receiver location to determine visibility and detect where signals are obstructed by interceding structures. Using the building model, one can efficiently create a database of visibility sky plots throughout the city of interest; an example of which is shown in Figure 8. SM algorithms rely on this kind of database to evaluate candidate locations. From these visibility predictions, we implement a SM method using the scoring scheme developed by Wang et al. (2012a) and shown in Table 1.
Three-dimensional model of Denver rendered with software framework (left) and the satellite imagery of Denver from Google maps (right). Right image obtained from Google maps
Visibility-boundary sky plot of a location in downtown Denver generated using ray tracing and 3D building model (left) and the corresponding imagery of Denver from Google maps as a sky plot (right)
The overall approach for our new proposed method of SPM consists of using the building model to develop a metric to predict NLOS signal reception, which we term the specularity value (Ωf). SPM predicts NLOS signal reception at a given location based on the likelihood of receiving a specular reflection from surrounding buildings. The proposed SPM method uses a predicted specularity value in conjunction with the predicted visibility to form a scoring scheme that considers both. To achieve this, a sky plot for the specularity value, analogous to the building-boundary sky plot in conventional SM algorithms, is generated and incorporated into a scoring scheme. The new scoring scheme evaluates candidate locations based on the predicted visibility and specularity values in conjunction with the observed signal strengths determined by SNR.
The specularity metric we developed is equal to the percentage of the visible Fresnel zone and reflecting surface overlap. Specifically, we assume that a receiver is likely to track a reflected signal if a large percentage (50%) of the first Fresnel zone is both visible to the receiver and overlaps with the reflecting surface. The 50% threshold has been shown to be a sufficient metric in other applications for predicting surface reflections (Zimmermann, Schmitz, Klingbeil, & Kuhlmann, 2019). The algorithm for determining the specularity metric for each direction in the sky is summarized in Algorithm 1 and illustrated in Figure 9.
Assigning a specularity value to each direction in the sky
Diagram of reflection geometry related to the Fresnel zone and specularity metric.
As summarized in Algorithm 1, to calculate the fraction of the first Fresnel zone that is predicted to be present (visible and reflecting), a scene is sampled by generating a set of rays (ℛ) with origins at the candidate location (A) and directions uniformly distributed over a sphere. The rays intersect surfaces within the scene, and then for each possible satellite direction 
in the sky, we predict how many of the intersection points would result in strong specular reflection points. We predict a strong specular reflection when the intersection point (G) is within the first Fresnel zone and when other objects within the scene do not obstruct the ray with an origin at G and a direction 
towards the satellite. See the Appendix for discussion on finding the specular point and determining whether an intersection point is within the first Fresnel zone.
For each DLOS satellite direction 
, there is a subset (𝒢) of intersection points that are within the first Fresnel zone. We compute the fraction of the Fresnel zone that is predicted to be present by the weighted summation (Equation 2) of intersection points that fit the ellipse equation criterion. In this way, each direction 
in the sky where a satellite could be located is assigned a single value that we refer to as the specularity value, Ωf, that quantifies the likelihood of receiving a specular reflection at a given receiver location, A. Once the intersection point, G, is determined to be within the first Fresnel zone and the path along the direction to the satellite is determined to be unobstructed, it is assigned a weight, w.
2
The weight is inversely related to the solid angle (Ω) that the entire Fresnel ellipse subtends (Figure 9).
3
4
The solid angle is calculated as
5
where SAproj is the projected surface area of the ellipse, and rR is the distance between the receiver location, A, and the specular reflection point, R. The semi-major axis (a), semi-minor axis (b), and angle β related to the Fresnel ellipse are defined in Equations (A4) and (A5) in the Appendix.
Figure 10 depicts an instance where the entire Fresnel zone is predicted to be present on the reflecting surface given the geometry of the candidate location and the satellite direction. For this case, the specularity value will be statistically equal to one.
Diagram of 3D model illustrating the intersection locations within the first Fresnel zones for GPS PRN 31 at 8:32 UTC for receiver location in experiment E1 (left). The intersections are shown in red, and the receiver location is shown as a green sphere. The Google imagery of the experiment location is shown to the right
Figure 11 depicts the geometry for the largest specularity value (Ωf ∼ 2.5) predicted to occur within the three experiments. In this instance, the receiver is predicted to see reflections from four different building surfaces. For the first reflecting surface (labeled 1), the entire Fresnel zone is present. The second and third reflecting surfaces show partial Fresnel zones because the reflecting surfaces are smaller than the extent of the zone. The fourth surface is large enough to contain the entire Fresnel zone, but another building blocks a portion of the reflecting surface and the Fresnel zone overlaps from the receiver. Though multiple reflecting surfaces would complicate the signal environment, our prediction method remains simple and assumes the satellite and receiver geometry would result in a strong reflection due to the high specularity value. The data presented in Figure 12 supports this assumption. In Figure 12, the SNR and specularity values are plotted for GPS PRN 31, a satellite that has a DLOS predicted to be blocked for every receiver for the duration of E2. When the predicted specularity value is greater than 0.5, the receiver predominantly tracks a SNR greater than 35, and this remains true when the specularity value is greater than one.
Diagram of 3D model illustrating the intersection locations within the first Fresnel zones for GPS PRN 31 at 3:58 UTC for receiver R3 in experiment E2 (left). The intersections are shown in red, and the receiver location is shown as a green sphere. The Google imagery of the experiment location is shown to the right.
SNR (top) and specularity value (bottom) time histories for GPS PRN 31 for all four receivers for the entire duration of experiment E2
Figures 10 and 11 each depict the Fresnel zones and corresponding specularity metric (Ωf = 1 and Ωf = 2.5, respectively) for a single satellite direction in the sky. The specularity sky plot is developed to represent the specularity metric for all directions in the sky. Figure 13 depicts three different specularity sky plots with varying levels of complexity. The first panel of Figure 13 depicts a sky plot of the specularity value for each direction in the sky. The second panel simplifies the content from the first panel to show all the regions (shaded) in the sky where the specularity value would be greater than 0.5. The final panel further simplifies the information presented in the sky plot by defining two boundaries (shown solid and dashed) at each elevation angle to delineate regions in the sky where the specularity value is greater than 0.5. A satellite located between the two boundaries (lower in elevation than the solid boundary and higher in elevation than the dashed boundary) is expected to see a strong specular reflection. This final sky plot is the one used in conjunction with the visibility sky plot for SPM. Where the visibility sky plot charts the building boundary at each elevation angle, the specularity sky plot charts the directions, 
, between the two boundaries that result in large specularity values (Ωf > 0.5). For a given candidate location, the SPM method determines whether the DLOS from the location to the satellite is unobstructed or obstructed based on whether the satellite location is above or below the building boundary in the visibility sky plot. Similarly, the method determines whether the candidate location would expect strong reflections or not based on whether the satellite location is between the two boundaries or not in the specularity sky plot. The visibility sky plots and specularity sky plots for each receiver in Exp2 are shown in Figure 14.
Specularity value sky plot (left, middle) and the sky plot of the boundaries for the specularity sky plot with the solid line defining the higher elevation boundary and the dotted line defining the lower elevation boundary (right)
Visibility sky plots (top) showing directions obstructed by buildings (white) for receiver locations (R1-R4) and GPS (G) and GLONASS (R) satellite locations for duration of experiment Exp2 indicated from starting location (•) and ending location (×). Colors correspond to receiver markers shown in Figure 5. The specularity sky plots (bottom) showing directions with regions predicted to have strong specular reflections (shaded) and areas where specularity is weak and reflections are not predicted (white)
The SPM method, which uses both visibility and specularity sky plots, is shown in Table 4. As seen in Table 4, when signals are observed to be not-tracked, the SPM scoring scheme functions the same as the SM scoring scheme: distinguishing only between invisible and visible predictions. However, for tracked signals, the SPM scoring scheme credits both visible locations and invisible locations that have high specularity values. This scoring scheme takes into account that high SNR values would be expected both from DLOS signals in visible regions and NLOS signals in regions with large specularity values even if the satellite DLOS is predicted to be blocked by buildings.
SPM Scoring Scheme
SM+i Scoring Scheme
SPM+i Scoring Scheme
Unlike the prior work done by other researchers on NLOS techniques, SPM does not attempt to detect and discard NLOS signals from satellites. Nor does it recompute a least-squares solution with a predicted delay. Rather, the SPM approach uses the observed SNR from a given satellite and the prediction from a specularity sky plot of the regions where a receiver might expect to see a strong reflection to determine the receiver position. The prediction of an NLOS signal is determined from the building model, and each candidate location has a prediction as to whether to expect an NLOS signal. The approach of using a sky plot instead of a real-time ray-traced interrogation of the building model is similar to that of the SM approach and conducive to limited processing capacities.
We also considered an enhancement to the scoring scheme that relies on additional knowledge. With the current phone receivers used for these experiments, it is not possible to establish whether the strong signals being tracked are from NLOS or DLOS signals. However, if there were an ability to indicate whether the strong SNR values measured were from NLOS or DLOS signals, the SM and SPM methods could use this additional information to further improve positioning. The ability to distinguish NLOS or DLOS signal measurements could be achieved by using more advanced receivers able to distinguish reflected signals perhaps by polarity or by using pseudorange residuals.
Two additional scoring schemes are introduced by supplementing the experimental data obtained in the Denver experiments with an indicator (+i) as to whether the signal is an NLOS signal. To construct this indicator, we mark signals that are strong, predicted to be invisible, and have strong reflections as being NLOS signals. This construction simulates the ability to distinguish NLOS signals from the observed data for our current phone receivers. Scoring scheme SM+i and SPM+i are versions of the SM and SPM scoring schemes, including an NLOS indicator for strong signals.
Lastly, we consider the performance improvement of SM and SPM through collaborative localization when the relative formation of multiple receivers is known. Though collaborative localization typically refers to localization of networked agents, our objective in using collaboration is in localizing the center of the formation and not each individual receiver. A collaborative scoring scheme is calculated at candidate locations for the formation center by summing the score from the individual receiver scores incorporating their known relative positions. The score assigned to a given position is the likelihood that the center of the formation (pc) is located there. The score is a summation over the different receiver scores at the positions relative to the center:
6
where i specifies the receiver and L1, L2, L3, and L4 are the position offsets of the receivers from the formation center.
To quantify the performance of the different proposed methods, we compute scores for each measurement epoch (one second) over a 40-meter radius search space centered on the known average receiver location with 2-meter candidate location grid-spacing for each experiment. SNR values larger than 35 are considered tracked, SNR values less than 25 or not reported in the NMEA message are considered not-tracked, and SNR values ranging from 25 to 35 are ignored in the scoring scheme. Specularity values below 0.5 are considered low specularity, and values at or above 0.5 are considered high specularity. A position is estimated as the average over all grid points receiving the maximum score.
5 ANALYSIS
The SPM scoring scheme method is designed to be able to account for strong SNR values from a satellite with a blocked DLOS in a way that the other conventional scoring schemes cannot. As part of our analysis, we examine how the specularity metric correlates to signal strengths observed in the experiments. We are particularly interested in locations where the DLOS is not visible but the specularity value is high. In urban environments, it is often the case that a receiver is receiving an NLOS signal even when the DLOS visibility to the satellite is limited due to building obstruction. Figure 15 shows three examples observed in our Denver experiments. The DLOS to GLONASS satellite PRN 4 in Exp1, GPS satellite PRN 10 in Exp2, and GPS satellite PRN 5 in Exp3 are all significantly blocked by buildings throughout the duration of the experiments. However, the receivers record high SNR levels for these satellites at various times during the experiment. These high SNR levels correlate with the prediction of high specularity values (Ωf > 0.5).
Satellite SNR values for receivers (left) and the predicted specularity values (right) in experiments Exp1, Exp2, and Exp3
The visibility of the tracked satellites throughout the duration of all three experiments for all receivers is predicted using the 3D building model. In the instances where the satellite is tracked, but the DLOS signal is predicted to be blocked by buildings, there is a positive correlation between signal strength and the specularity value as shown in Figure 16. The analysis shown in Figures 15 and 16 support the choice of using the Fresnel zone overlap to determine locations predicted to have strong specular reflections.
SNR vs specularity value for all tracked satellites expected to be invisible. Gray is all observed data points (∼280,000 data points) and red is the average SNR value for each tenth of a predicted specularity integer value
6 RESULTS
To evaluate the performance of the various positioning methods in our Denver experiments, the distance errors for SM and SPM are calculated as the distance between the known location and the estimated location, and the average of the distance errors over the experiment duration is shown in Figure 17. The SPM method outperforms the conventional SM scoring scheme for each individual receiver for all experiments. In the experiments (Exp2 and Exp3) where the phones are distributed in position, the collaborative solution outperforms the individual receivers in all scoring schemes. However, the collaborative solution for the collocated experiment (Exp1) is statistically worse than that of the individual receivers. The collaborative receiver appears to only perform better when the receivers are spatially dispersed, providing additional information based on their distinct visibility conditions. Note that the error for the single receivers are based on the receivers’ true locations, whereas the error for the collaborative results is computed based on the center of the receiver formation.
Average distance errors for Exp1, Exp2, and Exp3 for the single receiver and the collaborative receiver for the SM and SPM scoring scheme
Figure 18 shows that when additional knowledge indicating whether the signal was DLOS or NLOS is incorporated into the two scoring schemes (SM+i, SPM+i), both methods decrease in average distance error. As expected, the SPM+i method also outperforms the SM+i method in all cases. It should be noted that the error improvement for the methods incorporating the additional knowledge indicator demonstrates an optimistic scenario of improvement in positioning using this method because the measurements were simulated from our model.
Average distance errors for Exp1, Exp2, and Exp3 for a single receiver and the collaborative receiver for the SM+i and SPM+i scoring schemes
Figure 19 shows the candidate location scores for one epoch in each experiment for the four different scoring schemes. The instances depicted illustrate the advantage of incorporating knowledge about areas within the search region where the user would expect a large specularity value. We see that by using the SM method alone, the estimated location of the receiver (black O) is far from the actual location (red X) as is shown in the leftmost panels. The highest scores (yellow) are not in the region of the actual receiver because the signal reflections are not taken into account. The method is giving high scores to locations predicted to have DLOS visibility for satellites with strong SNR values without taking into account the regions predicted to have strong reflections. To illustrate regions where a strong reflection is predicted, Figure 20 depicts the specific geometry for GPS PRN 31 for receiver R4 at 3:47 UTC. Though this satellite is predicted to have a block DLOS, it reports a strong SNR. The specularity value at this location is large, indicating a likely reflection. The SPM scoring scheme gives high scores to candidate locations where a reflection is likely, which results in a more accurate location prediction as is shown in the second column of panels in Figure 19. Including an NLOS indicator (+i) creates high scores at the correct receiver locations for both SM+i and SPM+i schemes. For the SPM+i scheme, the region with a high score is smaller and therefore results in an even more accurate position prediction.
Scores for candidate locations in Exp1 for receiver R1 at 21:46 (top), Exp 2 for receiver R3 at 3:46 UTC (middle), and Exp3 for receiver R3 and 6:27 UTC (bottom) for scoring schemes SM, SPM, SM+i, and SPM+i(left to right). The correct location for the receiver (red X) and the estimated location (black O) based on the scoring scheme are depicted on each plot
Geometries for PRN 31 in Exp2. a. Buildings surrounding receivers in Exp2 obtained from Google Maps. b. 3D rendered building model with DLOS (blue line) to GPS satellite PRN 31 obstructed by building at 3:47 UTC for receiver R4 (green dot). Specular reflections intersection points reaching the receiver from PRN 31 indicated by red spheres. c. Specularity value at each candidate location for PRN 31 at 3:47 UTC with true location indicated by red X
7 CONCLUSION
In summary, we proposed a shadow matching technique that uses a 3D building model to predict significant specular reflections. We incorporate a specularity value into a new SPM scoring scheme to compare tracked SNR values to predicted visibility and specularity and demonstrate its performance through three experiments in downtown Denver, Colorado. The formulation of this method of predicting specular reflections is designed to be similar to the visibility sky plots used in SM for ease of implementation. The specular matching method outperforms the conventional SM scoring scheme. If additional knowledge to distinguish NLOS or DLOS signals is available, both methods are predicted to benefit. Collaborative shadow matching and specular matching when the relative receiver formation is known, further decreases the average distance error when the receivers are not collocated.
A more in-depth investigation of the specularity value and SPM will be pursued by performing additional experiments in diverse regions in Denver using higher performance receivers. Further efforts will focus on the practical implementation of the SPM method, including calculating the computation times and database requirements for the generation and storage of specularity sky plots for all of downtown Denver.
HOW TO CITE THIS ARTICLE
Strandjord KL, Axelrad P, Mohiuddin S. Improved urban navigation with shadow matching and specular matching. NAVIGATION. 2020;67: 547–565. https://doi.org/10.1002/navi.378
ACKNOWLEDGEMENTS
The authors would like to thank Dr. Dennis Akos and his research lab for providing software and hardware relating to the Android phones.
This research was funded through a Draper Fellowship through Charles Stark Draper Laboratory.
APPENDIX
To determine whether the intersection point (G) is within the first Fresnel zone, begin by determining the location of the true specular reflection point (R) on the surface for the satellite (S) and receiver (A) geometry shown in (Figure A.1.
Reflector geometry used to find specular reflection point (R)
To achieve this, first establish a building coordinates system defined by the surface normal 
and the unit upward vector (û):
A1
Next, determine the orthogonal distance from the receiver to the surface (d) and the point (D) representing the projection of the receiver location onto the surface:
A2
where 
is the vector from the intersection point to the receiver location. Finally, the specular reflection point can be written as the sum of the projected receiver location and components in the 
and 
coordinate directions:
A3
Once the specular reflection point is found, determine whether the intersection point, G, is within the first Fresnel zone defined by the ellipse centered at the specular reflection point with semi-major and semi-minor axes 
shown in Figure A.2 (Zimmermann et al., 2019).
Reflector geometry used to determine whether a generic intersection point (G) is within the first Fresnel zone ellipse
The semi-major and semi-minor axes directions and lengths are calculated as
A4
where β is the angle expressed as
A5
and 
and 
are unit vectors. Whether the intersection point G is inside the first Fresnel zone is determined by the equation of an ellipse:
A6
The reflection point G is inside the Fresnel zone if f ≤ 1 and outside if f > 1.
Footnotes
Funding information
Charles Stark Draper Laboratory, Grant/Award Number: OcG6690B
- Received August 23, 2019.
- Revision received April 1, 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.