Radio-Frequency Pattern Matching
By Tarun Bhattacharrya, Hassan El-Sallabi, Jian Zhu, Jeff Wu, and Per Enge
Radio-frequency pattern matching (RFPM) is the engine that enables the use of mobile-phone signals to locate wireless devices in any environment, including dense downtown areas and indoors. This exciting technology leverages the power of the database to improve location accuracy to within 50 meters in even the toughest signal environments. Significant advances in RFPM technology have been made over the last 10 years. The system described here is deployed in more than 24 wireless networks to provide the location of E-911 callers and help save lives. For simplicity, we focus on the RFPM using signal strengths even though the technology also works with arrival times, signal-to-noise ratios, differential signal strengths and any signal parameter that varies in a predictable fashion over the coverage area.
Like GPS, RFPM is based on correlation. However, it does not correlate a received spread-spectrum code with a replica code stored in the receiver. Rather, it correlates the signal strength of cell-phone signals measured by the roving phone to a database that contains a map of those signal strengths for the covered area. Consider Figure 1. It shows this key correlation operation. As shown, the database contains a k-vector for each location within the covered area, where the k elements give the estimated strength for the k mobile phone signals that can be received at the given grid point. These k-vectors are typically stored over a 10- or 30-meter grid. This grid of predicted signal strengths is built in advance and is updated only when the topography of the wireless network changes. Thankfully, base stations do not generally move!
The mobile phone provides the network measurement report (NMR) in real time. This report does not require any network hardware or on-phone software beyond that required by the 2G, 3G and LTE standards for all mobile phones. Thus, the Polaris Wireless solution is capable of locating any mobile phone over any air interface. The NMR is also shown in Figure 1. It contains an n-vector of received signal strengths, where k ≥ n. A multiplicity of n-vectors are backhauled to the server that contains the database. They are correlated with the k-vectors, and the estimated location of the mobile phone is the location associated with the maximum correlation.
For Example, San Francisco
Figures 2, 3, and 4 explode the RFPM database for the financial district of San Francisco. Figure 2 is the top view, and the Bay Bridge is shown heading northwest across the Bay. The numbered black dots are some of the base stations in action for this area. Figure 3 digs down one level. It shows the individual k-vectors contained within the database. As shown, this database is based on a 30-meter grid. Figure 4 is a super-zoom that explodes the individual k-vectors. As shown, each of these vectors contains an element for each base station that can be received at the given location. In Figure 4, each element is color coded to correspond to the strength for the signal from the given base station.
Building the Database
RFPM accuracy depends strongly on the quality of the database, which needs to be built with great care. In fact, signal propagation depends on the network topology including:
◾ antenna location, heights, patterns, effective radiated power, tilt, and azimuth
◾ cell type, such as micro-cell, macro-cell, indoor or distributed antenna systems.
Signal propagation also depends on information available from geographical information systems such as:
◾ tree canopy
◾ height of buildings and terrain
◾ topography (water, open area, suburban, urban)
With this data, the signal strength radiating from a base station can be estimated. This is not a simple business. For example, the calculation must identify the points where terrain or buildings interrupts the ray from the transmitter to the receiver. It must also identify the points where these obstacles break the Fresnel zone that surrounds the ray.
Finally, these open-loop predictions are tuned based on a sparse set of measurements. Once tuned, the database is time invariant or nearly so. If minor changes are made to the network topography, the open loop predictions alone are sufficient to accommodate the changes. If network changes are significant, such as the building of many new base stations, then the open-loop predictions must be updated, and a new set of measurements used to tune the predictions.
Figure 5 shows a typical map of signal strengths surrounding one mobile phone in a completely open area. Absent terrain and buildings, the signal strengths vary rather smoothly. Figure 6 is for one of the transmitters in the San Francisco financial district, which is a much more complicated urban environment due to the dense concentration of high-rise buildings and uneven terrain. In this case, the signal-strength signature has a gratifying abundance of detail. This detail enables RFPM to work very well in the complicated signal environments that we find in downtown areas and also indoors. In short, RFPM benefits from the buildings and terrain that hinder satellite measurements.
Performance and Summary
RFPM works well. It provides high accuracy in a in a wide variety of environments. Polaris Wireless routinely tests the accuracy of its solution in urban settings. Table 1 shows the results of such evaluations, based on measurement sets that are not used to tune the database.
These days, robust navigation for downtown and indoors is based on an expanding suite of location technologies. These include: assisted GPS, new satellite constellations (Galileo, GLONASS, Compass, and so on), inertial measurements, Wi-Fi ranging, and signals from low-Earth orbit. RFPM, and its unique reliance on database-derived location, should remain an important part of this mix.
Tarun Bhattacharrya is vice president of research at Polaris Wireless. He earned his Ph.D. in electrical engineering from the Indian Institute of Science.
Hassan El-Sallabi received his D.Sc. in electrical and communications engineering from Helsinki University of Technology, Finland. At Polaris he works on RF propagation modeling.
Jian (JET) Zhu received his Ph.D. in electrical engineering from Georgia Institute of Technology; he is a research engineer at Polaris.
Jeff Wu focuses on algorithm development for propagation modeling at Polaris, and is a Ph.D. candidate in electrical engineering at Stanford.
Per Enge is the Kleiner Perkins professor of engineering at Stanford University, where he directs the Stanford Center for Position, Navigation, and Time. He is also a technical advisor to Polaris Wireless.