Tag: personal navigation

By Paul D. Groves, Lei Wang, and Marek K. Ziebart

GNSS positioning in dense urban areas is unreliable, with accuracy particularly poor in the cross-street direction. One solution is shadow matching, a new positioning technique that uses 3D building models to predict which satellites are visible from different locations and compares this with the measured satellite visibility to determine position. This article presents test results of a preliminary shadow-matching algorithm in a London urban canyon and discusses the practical implementation of the technique

Poor GNSS positioning accuracy is common in urban canyons where tall buildings block the direct line-of-sight (LOS) signals from many, sometimes most, of the satellites, effectively casting GNSS shadows over the adjacent terrain. Without direct signals from four or more satellites, an accurate position solution cannot be determined. Sometimes, a degraded position solution can be obtained by using signals that can only be received by reflection off a building, known as non-line-of-sight (NLOS) signals.

Using GLONASS in addition to GPS considerably enhances direct signal availability, and the ongoing deployment of Galileo and Compass will enhance it further. However, an urban canyon affects the geometry of the available GNSS signals as well as their number. Signals with lines of sight going across the street are much more likely to be blocked by buildings than signals with lines of sight going along the street (see Figure 1). As a result, the signal geometry, and hence the positioning accuracy, will be much better along the direction of the street than across the street. For example, for a building-height-to-street-width ratio of three and direct signals from four GNSS constellations, the cross-street position uncertainty can exceed 20 meters, while the along-street uncertainty is within 5 meters.

This level of accuracy is good enough for some applications but not others. Knowing which side of the street a pedestrian on is useful for visitor guidance and location-based advertising, while it is critical for guiding the blind and visually impaired and for augmented-reality applications. Similarly, lane-level positioning is important for advanced intelligent transportation systems that can direct individual vehicles in order to maximize traffic flow and prioritize emergency vehicles.

Improving GNSS positioning in urban canyons requires lateral thinking. If it’s not possible to calculate a sufficiently accurate position solution using the visible satellites, why not use the nonvisible satellites as well? This is exactly what shadow matching does. If you know where the buildings are and how big they are, you can deduce positional information from the knowledge that certain signals are blocked.

This requires a 3D model of a city’s buildings. These are becoming more accurate and widely available and have already been used to predict GNSS signal availability and multipath interference.

The principle of shadow matching is simple. Due to obstruction by buildings in urban canyons, signals from many GNSS satellites will be receivable in some parts of a street, but not others. Where each direct signal is receivable can be predicted using a 3D city model. Consequently, by determining whether a direct signal is being received from a given satellite, the user can localize their position to within one of two areas of the street. Figure 2 illustrates this. By considering other satellites, the position solution may be refined further, producing a much more accurate cross-street position solution than available from conventional GNSS positioning in this environment. Thus the observed signal shadowing is matched with the predicted shadowing to determine position.

This concept of shadow matching, has been proven by mathematical modeling. Satellite visibility predictions using a 3D city model of London have been validated with real-world observation, demonstrating the practical potential of shadow matching. Here, shadow matching is brought from proof of concept one step further to practical demonstration. A preliminary but complete implementation of shadow matching has been developed and tested in London using real-world GPS and GLONASS measurements. The algorithm is described first, followed by the test results. We then discuss dealing with different types of signal propagation that occur in urban areas. and how to implement shadow matching in real time on a platform such as a smartphone.

Shadow-Matching Algorithm

A basic shadow matching algorithm may be broken down into four steps:

• Perform standard point positioning (SPP) using GNSS pseudo-ranges to obtain an approximate user position.
• Define the search area for the shadow-matching position solution, generating a set of possible user positions close to the approximate position solution.
• Predict satellite visibility at each candidate position using the 3D city model.
• Evaluate the similarity between predicted and observed satellite visibility at each position. The candidate position with the best match is deemed to be the shadow-matching solution. This process can be conducted epoch by epoch, so the GNSS user can be either static or dynamic.

Conventional Positioning. In the first step, SPP using GNSS pseudo-ranges is conducted to acquire an initial user position. In an urban environment, the accuracy will often be poor, partly due to contamination by NLOS signals. Consistency checking may be used to identify the NLOS signals and, where possible, remove them from the position solution.

Candidate Position Determination. As discussed earlier, signal geometry and hence positioning accuracy will be much better along the direction of the street than across the street. Therefore, in this preliminary shadow-matching algorithm, the along-street component of SPP solution is used as a reference to generate a set of possible user positions that vary in across-street direction only (shown by the two mobile phones beside the SPP solution on the opening page of this article).

A more advanced shadow-matching algorithm would also consider candidate positions in the along-street direction and would vary the size of its search area based on an assessment of the quality of the SPP solution. The smaller the search area, the more efficient the shadow-matching algorithm will be. However, the search area must be large enough to contain the true position. Further research is needed to determine the optimum search area.

Satellite Visibility Prediction. At each candidate position, the two-step building boundary method predicts satellite visibility from the 3D city model. First, a building boundary from a GNSS user’s perspective is determined for each azimuth (from 0 to 360°) as a series of elevation angles. The results from this step show where the building boundaries are located within an azimuth-elevation sky plot. Figure 3 shows an example of a building boundary computed from a possible user location. Once the building boundary has been computed, it may be stored and reused.

Next, each satellite elevation is compared with the building boundary elevation at the same azimuth. The satellite is predicted to be visible if it is above the building boundary. If the satellite is just within the building boundary, a potentially diffracted signal can be predicted. However, this feature was not included in the preliminary shadow-matching algorithm described here. A software toolkit for determining satellite visibility was developed in C++.

Figure 4 shows the relationships between its processes.

The building boundary approach is efficient where a great number of satellite visibility tests are performed at the same location. For real-time visibility determination, building boundaries may be pre-computed over a grid of possible user locations and stored. However, there is an alternative. Instead of computing building boundaries, each satellite LOS can be directly compared with the city model to determine if it is blocked by buildings. This single LOS method is more efficient overall where only a few satellite visibility tests are performed at a given location. However, for real-time, it imposes a much higher processing load than using pre-computed building boundaries.

In practice, either method may be employed, depending on the situation. For real-time shadow matching, the trade-off is between a higher processing load for the single LOS method and greater data storage for the building boundary method. For non-real-time visibility determination, the trade-off depends on the number of tests required at each location.

Matching Prediction and Observation. The final step, evaluating the similarity between predicted and observed satellite visibility at each position and identifying the best match as the shadow matching solution, comprises three functions: satellite matching, position scoring, and position comparison.

Satellite matching determines for each satellite the degree of similarity between the predicted satellite visibility and the real observation. Figure 5 shows the simple satellite matching function deployed for this study. For each satellite above a pre-set elevation mask angle, if the prediction agrees with the observation, the score is one; otherwise, the score is zero.

Future research will be conducted to extend the matching function so that different scores are produced for signals predicted to be in the diffraction region and signals observed with low and medium signal-to-noise levels.

Position scoring evaluates the overall degree of match between predicted and observed satellite visibility for each possible user position, summing up the satellite matching scores for each candidate position to give a position score.

Finally, position comparison selects the candidate position with the highest overall score and outputs this as the position solution. However, sometimes there is more than one candidate. Further research is needed to find the optimum way of determining a positioning solution with associated error bounds from a grid of shadow-matching scores.

Figure 6 summarizes the shadow-matching process.

Experimental Verification

We used a 3D city model of the Aldgate area of central London to test shadow matching. The model has a high level of detail and decimeter-level accuracy.

The software toolkit developed for this study stores and processes 3D city model data using Virtual Reality Modeling Language (VRML), an international standard format. Model data in other formats can be transformed to VRML. Buildings in VRML format are represented by structures, which in turn comprise polygons (normally triangle meshes).

Methodology. Experimental data were collected in a highly built-up area in central London, using two multi-constellation survey-grade GNSS receivers, logging 1 Hz data simultaneously (note that shadow matching does not require two receivers). As shown in Figure 7, they were set up on the north and south sidewalks of Fenchurch Street.

For the first step of shadow matching, software was used to conduct SPP processing using GPS and GLONASS signals. Only L1 pseudo-ranges were used to acquire an initial user position. It can be seen in Figure 7 that the conventional SPP solutions have significant offsets from the true positions (16–31meters for receiver A and 18–24 meters for receiver B). As receiver B suffers more signal blockage from buildings, it has fewer epochs with four or more satellites in view, so fewer successful SPP GNSS solutions were obtained. Although they have significant offsets in the across-street direction, they are consistent and agree much more with the receivers’ true positions in the along-street direction. This result verifies the assumption made in the shadow-matching algorithm that the accuracy of the along-street SPP positioning solution is much better than in the across-street direction.

Four candidate user positions were selected using the common along-street position of the conventional SPP solution. They are distributed across the sidewalks and vehicle lanes, on both sides of the street. Figure 8 illustrates this. Note that candidate 3 is the true position of receiver A and candidate 0 is the true position of receiver B.

Satellite visibility was predicted individually for each of the four positions. Then each was compared with the real data observed from the two GNSS receivers. Figure 8 shows part of the architectural city model of London used to predict the satellite visibility.

Results. The experimental results are shown in three stages: the satellite visibility comparison between prediction and observation, the candidate position scoring function, and the success rate for each candidate location. The primary success criterion is whether the algorithm is able to determine the correct side of the street. A secondary aim is to test whether the algorithm can distinguish between the sidewalk and vehicle lane on the same side of the street.

To show the degree of agreement or disagreement between the predicted and observed satellite visibilities, time series for each of the four candidate positions are compared with each of the two receivers’ experimental data. The results are shown in eight graphs. Figure 9 compares data from receiver A for each of four possible user locations. Figure 10 shows the same comparison for receiver B. The time window was from 13:56:30 to 14:06:30 (UTC). G denotes GPS satellites and R refers to GLONASS satellites.

In Figure 9, the green and blue dots indicate an agreement between prediction and observation for the candidate user position, while the orange and red colors represent their disagreement. Thus, a larger number of cases of green and blue indicate a better match between the candidate user location and the observations. Therefore, such a candidate is more likely to be close to the receiver’s true position.

Figures 9 and 10 clearly show that the closer the candidate position is to the true position, the greater the agreement between predictions and observations.

Even at the correct candidate location, there is not complete agreement between the observations and predictions. A number of signals were observed but not predicted. These had signal-to-noise levels 8 dB or more lower than the predicted signals and are most likely due to reflection and/or diffraction.

However, shadow matching does not require complete agreement in order to work. In this test, no signals were predicted but not observed at the correct location.

To complete shadow matching, we evaluate each candidate position by summing up the number of satellites common to both the predictions and real observations. Figure 11 and Figure 12 show the results of the summation for receivers A and B, respectively.

It is clear from Figure 11 that among four possible user positions, point 3 is the one with the highest agreement score with the observations from receiver A. As shown in the right-bottom graph, for about half the epochs, visibility predictions for all 12 satellites above the masking angle match the real observations.

As shown in Figure 12, for receiver B, the time series of the agreement score is generally better at the true location (Point 0) than at other points. However, the level of agreement between predictions and observations is not as good as at receiver A‘s location.

To judge the performance of shadow matching, the selection rate of each of the four candidate user positions for each of the two receivers was computed by dividing the number of times that position was selected by shadow matching by the number of epochs. Where the same score was attained for two or more positions, each position was considered partially selected. For example, if two positions have the same score, then each of them is considered half-selected.

The selection rate results are shown in Figure 13. For receiver A, the shadow matching algorithm correctly indicated the true position among the four candidates 100 percent of the time. This means the algorithm successfully distinguished between the two sides of the street, and further distinguished between a user on the sidewalk and a user in the vehicle lane. For receiver B, the algorithm identified the correct side of the street (Points 0 and 1) 94.65 percent of the time, and the correct location among the four candidates in 81.29 percent of the epochs evaluated.

Taking the average of the two test sites, the correct side of the street was identified 97.3 percent of the time and the correct position from the four candidates 90.6 percent of the time.

Practical Implementation

The basic shadow-matching algorithm operates under the assumption that GNSS signals are either directly visible or blocked by a building. However, in reality, signals can also be received via indirect paths due to reflection or diffraction. This was observed at both locations during the tests. As shadow matching seeks the position with the best match, rather than looking for a perfect match, it can tolerate a certain number of these signals and still identify the correct position.

These tests were performed using survey-grade user equipment with a relatively high tracking threshold, so the weakest signals are not observed. Furthermore, the antenna has strong polarization discrimination so exhibits a low gain for reflected signals. However, for shadow matching to be practical, it should also work on a smartphone, which typically combines a high-sensitivity receiver with a linearly polarized antenna, which does not distinguish between direct and reflected signals. Consequently, a smartphone receiver is likely to observe more reflected and diffracted signals.

NLOS reflected and diffracted signals are weaker than directly-received signals, so the shadow-matching algorithm could be modified such that only signals received above a certain signal-to-noise threshold are classified as observed. However, this would introduce a new problem: signals  received via a direct LOS path but attenuated by a person’s body would be classified as not observed, even though they would be predicted to be visible at the correct location. The same problem would occur where the LOS coincides with a direction in which the antenna is weak. Consequently, to get the best performance from shadow matching, several different categories of observed signal should be considered in the scoring matrix.

Diffraction occurs when the LOS is just inside the building boundary. Therefore, the 3D city model can be used to predict when a diffracted signal may be received. However, it cannot easily be used to predict the signal-to-noise level of that signal because diffraction patterns are complex. Therefore, shadow matching can potentially be improved by adding a third prediction category for diffraction. Figure 14 shows a posssible optimized scoring matrix with values between 0 and 1 for the new categories to be determined empirically, possibly as functions of the measured signal-to-noise. Different scoring matrices may be suited to pedestrian and vehicle applications and to different user equipment designs.

Directly-received signals are also affected by multipath interference. However, this will not normally impact shadow matching as it does not affect whether a signal is received or not.

Shadow matching has been demonstrated using both GPS and GLONASS measurements. The more signals available for shadow matching, the better the expected accuracy and reliability. Thus, the addition of Galileo, Compass, and regional systems, including SBAS, should improve performance. However, further research is needed to determine whether shadow matching using GPS alone is viable. Combining data from multiple epochs should also improve shadow matching performance, particularly where the user is moving.

A practical shadow-matching algorithm must be implementable in real time on a mobile device. Three models maybe considered.

• A network-based solution, whereby GNSS measurements are transmitted to a server, which stores the building boundary data, computes a solution and then sends it to the user.
• A handset-based solution, where the shadow-matching algorithm is run on the handset, which also stores the building boundary data.
• A hybrid model, whereby the shadow-matching algorithm runs on the handset, but the building boundary data is streamed from a server as and when required.

Using stored or streamed building boundaries, fewer than fifty comparison and addition operations are required to calculate an overall shadow-matching score for one candidate position with two GNSS constellations. Therefore, shadow matching may be performed in real time on a mobile device with several hundred candidate positions, where necessary.

Without any data compression, about 300 bytes are required to store a building boundary with a 1° resolution. If a 2×2 meter grid spacing is used for the candidate positions, a 1-kilometer long, 20-meter wide street will contain 5000 grid points, requiring 1.5 MB of data storage. By exploiting the similarities both between neighboring azimuths in the same building boundary and between building boundaries at neighboring grid points, substantial data compression should be achievable; possibly up to a factor of ten.

Therefore, a standard 4 GB flash drive could store building boundary data for 2,500–25,000 kilometers of road network. For comparison, the Greater London metropolitan area contains about 15,000 km of road. However, as shadow matching is only useful in streets where conventional GNSS positioning is poor, the database need only contain building boundary data for these streets, maybe 10 percent of the total. Therefore, it should be practical to preload a mobile device with shadow-matching data for several cities, which could be kept up-to-date via the internet.

An alternative model is to download the building boundary data from a network server as required. A conventional GNSS position solution or Wi-Fi fix should be able to localize position to within 1,000 grid points, requiring 30–300 kB of building boundary data to be downloaded in order to perform shadow matching. This takes less than two seconds using a 3G mobile phone connection with an average data rate.

In practice, shadow matching, would be implemented as part of a wider intelligent urban positioning system. This shadow-matching algorithm assumes that the user is outdoors. Indoor operation, if viable, would require a different approach. It is necessary to determine the error bounds of the conventional GNSS position solution, not only to determine the search area for shadow matching, but decide whether shadow matching should be performed at all. For example, in a completely open-sky environment, shadow matching will fail, but a good position solution will be obtainable conventionally.

There are other ways in which 3D city models could be used to improve GNSS positioning. For example, they could aid identification of NLOS and multipath-contaminated signals and, in principle, even correction of NLOS ranging measurements. Intelligent urban positioning can also incorporate additional sensors, such as odometers on cars and cell phone signals, WiFi and inertial sensors for pedestrian users.

Next Steps

Three potential future lines of research stem from this work: improving the initialization from conventional GNSS positioning, improving of satellite visibility predictions with ambiguous observations, and optimizing the position determination from the shadow-matching scores. In addition, performance will be evaluated over a wider range of environments.

Acknowledgments

The authors gratefully acknowledge Kimon Voutsis for his support with the experiments. This work has been jointly funded by the University College London Engineering Faculty Scholarship Scheme and the Chinese Scholarship Council. This article is based on a paper presented at the 2011 European Navigation Conference in London, organized by the Royal Institute of Navigation.

Manufacturers

The tests used two Leica Viva GS15 GNSS receivers. Leica Geo-office software performed SPP processing of GPS and GLONASS signals. ZMapping Ltd. supplied the London 3D model.

---

Paul Groves is a member of the academic faculty at University College London (UCL), where he leads the Space Geodesy and Navigation Laboratory’s program of research on robust navigation and positioning. He is also author of the book Principles of GNSS, Inertial, and Multisensor Integrated Navigation Systems.

Lei Wang is a Ph.D. student at UCL. He received a Bachelor’s degree in geodesy and geomatics from Wuhan University in 2010. His current research interests are GNSS-based positioning techniques for urban canyons.

Marek Ziebart is professor of space geodesy, director of the Space Geodesy and Navigation Laboratory, and vice dean for research of UCL Engineering.