Continuous Indoor Positioning: GNSS, Wi-Fi, and MEMS Dead Reckoning

By J. Blake Bullock, Mahesh Chowdhary, Dimitri Rubin, Donald Leimer, Greg Turetzky, and Murray Jarvis

A new chip fuses input from several sensors, using the best combination at any given time to maximize coverage and accuracy while keeping power draw to a minimum. This produces continuous position availability in indoor environments, as demonstrated by performance measurements in real-world test environments.

Users of GPS receivers in smartphones and many other consumer electronic devices expect these devices to work in all environments, including dense urban canyons, parking garages, and indoors, enabling a wide range of location-based services such as mapping, search, tracking, and navigation. Recent advancements in assisted-GPS (A-GPS) technology have enabled improved positioning indoors, but GPS receivers are still not sensitive enough to determine position everywhere that users go.

Several consumer products now use GLONASS and assisted-GLONASS (A-GLONASS) measurements to improve coverage and accuracy of GPS receivers. We refer to such combo receivers as GNSS receivers here. GLONASS measurements have similar characteristics to GPS measurements in that they are subject to blockage and multipath. In dense urban canyons, GLONASS measurements help to improve availability and accuracy of a position solution. However,GLONASS provides little performance improvement indoors.

Various emerging technologies for indoor positioning use installed wireless transmitters as beacons for making measurements for positioning. Existing Wi-Fi access points (APs) can be used in this way to determine position when indoors. Other solutions include the emerging Bluetooth Smart transmitters, GSM, 3G, and other mobile phone transmitters, the NextNav network, and other dedicated beacons for indoor positioning. Each technology has advantages and disadvantages for use as an indoor solution, to be discussed here.

The SiRFstarV location chip with SiRFusion combines A-GPS and A-GLONASS advances with Wi-Fi positioning and dead reckoning using low-cost micro-electro-mechanical systems (MEMS) sensors. Smartphones, tablets, cameras, fitness products, and other consumer electronics are equipped with an increasing array of MEMS sensors including accelerometers, magnetometers, gyroscopes, and barometers. The SiRFstarV chip acts as a gateway to receive input from all available MEMS sensors so that the output signals can be combined with the GPS, GLONASS, and Wi-Fi measurements that give absolute position. The observations from all these sources are fused together using a Kalman Filter. Smart location management makes use of the best combination of sensors at any given time to maximize coverage and accuracy while keeping power draw to a minimum. This produces continuous position availability in indoor environments.

Target Performance and Use Cases

The last 10 years have seen great improvements in GPS positioning indoors, primarily driven by the mobile market and the FCC E911 directive to be able to locate mobile-phone users. Today, it is possible to locate a mobile phone indoors using A-GPS, advanced forward link trilateration (AFLT), or Wi-Fi positioning. Typically it takes several seconds to determine a fix indoors, and the accuracy is not as good as outside. It is also not feasible to get continuous position updates for use in tracking, fitness, or navigation systems.

Wi-Fi positioning has improved the availability of fixes indoors and also the time to get a fix. However, today AP positioning is based on surveys that have been done using GPS vehicles outside, so the determined positions tend also to be outside, even when the mobile device is indoors.

To reliably deliver indoor positioning, the positioning system must be able to:
◾    Determine position quickly — within a few seconds.
◾    Determine position accurately — within 5–10 meters, circular error probable (CEP) 50 percent.
◾    Determine position updates at 1 Hz.
◾    Preserve battery life.

Cameras have very different uses than handsets. Typically, a camera is off until the user is ready to take a picture or video. When a picture is taken, theposition can be recorded and used to geotag the image with the location, date, and time. For this use case, the positioning system needs to be able to determine position indoors quickly and with low power, but continuous updates at 1 Hz are not needed.

Fitness products use location for recording distance traveled, speed, elevation, calorie counting, and showing a track of running or cycling workouts. Users value good accuracy and a fast startup time when they are about to begin a workout. The positioning system needs to be able to determine position continuously, but not necessarily show the position updates in real time.

Battery life for a typical assest-tracking device is extremely important, as is the ability to locate the asset in any environment. Continuous position updates are not needed. A typical feature of asset-tracking systems is the ability to set a geofence boundary, used for generating alerts. The positioning system needs to determine position periodically and compare with the geofence. If the position is outside the geofence, an alert is sent to the user.

GNSS Positioning

Positioning algorithms on the SiRFstarV Quad-GNSS combine range measurements from all-in-view GPS, GLONASS, QZSS, and SBAS satellites. The chip is hardware-ready to enable Galileo and Compass measurements with a future software update. Immunity to interference, cross-correlation, and multipath impairments are provided to achieve very high sensitivity, which is critical for indoor positioning. Nevertheless, the utility of reception sensitivities below –165 dBm has been found to have limited value for all but static cases, due to the very long integration times required to make reliable measurements. Increasing the number of independent range measurements helps improve indoor positioning, and using multiple constellations is a key enabler to provide them.

The improvement in indoor positioning by using multiple constellations is similar to the improvement in urban canyon positioning, since the impairments are similar.

One significant difference is that multipath delays for indoor environments are typically much shorter, and conventional mitigation methods cannot be applied without a very wide RF bandwidth. The shorter delays therefore produce lower signal levels due to phase cancellations and pseudorange bias errors, which are recognized as multipath errors and reduced as part of the chip’s measurement processing. While the advantage of augmenting GPS measurements with GLONASS is typically 20 to 40 percent improvement in position accuracy in urban canyon environments, it shrinks to only 7 to 15 percent indoors. Even with GLONASS measurements, the position is frequently shown outside of the building.

Figure 1 shows the results of an indoor walk test with a SiRFstarV receiver using GPS and GLONASS. The test was done on multiple floors of a three-story commercial building. Table 1 shows a summary of the performance metrics as determined by stopping at benchmark locations during the test. Fixes are available nearly 97 percent of the time. The addition of GLONASS tracking increased the average number of satellite measurements from 7.3 to 9.9 and improved the horizontal and vertical accuracy by about 7 to 15 percent. The horizontal accuracy is about 11.5 meters, 50 percent CEP. However, more than half the fixes are shown outside of the building.

Table 1. Impact of GLONASS on indoor positioning.

This test had high availability, but many environments cannot provide GNSS signals with sufficient energy to obtain position fixes. While the use of multiple constellations improves the accuracy and availability of the GNSS fixes, additional position sources are needed to achieve suitable availability and accuracy for continuous indoor positioning.

MEMS Pedestrian Dead Reckoning

Pedestrian dead-reckoning (PDR) logic is realized using integration of MEMS sensors with the SiRFstarV GNSS receiver, which has a dedicated I2C port designed to interface with MEMS sensors. A data-acquisition task collects sensor data and performs low-level error checking, timing synchronization, and buffering of the data from various sensors. This data is sent periodically to the process where a sensor data handler prepares it for further processing.

Acceleration data is processed by the context (or user mode) detection algorithm to determine the dynamic state of the user (or receiver) in order to select appropriate position-determination algorithms and associated motion parameters used by these algorithms. The PDR algorithm is employed when the user mode is classified as walking, fast-walking, jogging, stationary, climbing/descending stairs, elevator, and escalator.

The generalized navigation equation can be written as

  (1)

where vⁿ_e is ground velocity in navigation frame, C^nb  is direction cosine matrix relating body reference frame to navigation frame, f _b is specific force, ωⁿ_en is turn rate of Earth, ωⁿ_en is body rate, and gⁿ_l  is local gravity vector expressed in navigation frame. This equation (in navigation frame) relates the ground speed of an object to measured specific force and measured body rate. The generalized navigation equation, when integrated twice, transforms from the acceleration of the platform into position represented in North and East reference frame, results in Equation 2,

  (2)

where, s(t) is displacement and ψ(t) is heading. In the case of pedestrian motion, velocity and heading can be assumed to be constant during the interval when a step is taken. With this assumption, the integral form of Equation 2 can be rewritten as a difference equation with piece-wise linear approximation.

  (3)

This equation describes a method of dead reckoning (DR) that is based on step counting rather than integration of acceleration and angular rate. This PDR process consists of three important components: the previously known absolute position of the user at time t-1 (E_t-1, N_t-1), the stride length or distance traveled by the user since time t-1 (), and the user’s heading (ψ) since time t-1. The coordinates (Et, Nt) of a new position with respect to a previously known position (E_t-1, N_t-1) can be computed as shown in Equation 3. The position initialization of the PDR process can be accomplished using any or a combination of absolute positioning technologies such as GNSS, Wi-Fi, or GSM.

Performance of PDR algorithms is dependent on obtaining calibrated MEMS inertial sensor data continuously. Calibration of sensors is accomplished through collecting and processing sensor data for user motion of device in Earth’s gravity and magnetic field. Accelerometer and gyroscope calibration logic utilize the knowledge of device stationary condition. Magnetic sensor calibration logic requires that various axes of sensor are exposed to Earth’s magnetic field vector at the user location. With the given time and location estimate, the Earth’s magnetic field parameters are computed using the World Magnetic Model. Normal use of a mobile device would result in rotations in various Euler planes thereby applying Earth’s magnetic field to various axes of magnetic sensor. Earth’s magnetic field parameters are also used to detect occurrences of magnetic disturbances. Magnetic sensor measurements are de-weighted for the PDR process during such magnetic disturbances.

The essential logic components that affect the performance of PDR positioning system are: calibration of sensors, step detection, determination of walking direction, positioning fusion logic, and orientation of phone while walking. Typical phone users will have the phone in a pocket, in a belt clip, in a purse or bag, in their hands looking at it, or up to their ear in a conversation. The PDR algorithms need to be able to perform robustly in any of these orientations.

With PDR, an absolute position can be propagated as a user moves on foot. Due to the error growth characteristics of typical MEMS devices used in consumerelectronics, the estimated path deviates from the actual path as a function of distance traveled. The error growth is typically on the order of 10 percent of distance traveled, especially in the presence of magnetic disturbances. This level of error growth makes MEMS PDR unsuitable as the sole positioning solution when indoors. Periodic absolute positioning updates are required to correct the path and to allow additional calibration.

Wi-Fi Positioning

Opportunistic positioning using observed Wi-Fi signals is a well established method of absolute positioning in GNSS-denied environments. Off-the-shelf Wi-Fi access point hardware is not well suited to positioning using timing observations, therefore the chip under discussion uses observed signal strengths together with the broadcast unique identifiers (BSSIDs) as the basis for the Wi-Fi positioning sub-system. Signal strength information is by its nature asymmetric. A strong observation of a Wi-Fi AP indicates that one is near it, but it is not safe to infer from a weak observation that you are far away. This is because weak observations may be due to, for example, occlusion, fading, or antenna orientation. This means that the performance of Wi-Fi positioning varies considerably with location and time, especially in areas with many pedestrians.

There are several limitations to Wi-Fi positioning. The first is that since it is opportunistic, there is no guarantee of performance. Fortunately, AP density is typically highest in the areas where Wi-Fi positioning is most needed, namely, deep indoors and in dense urban areas. Secondly, there is no guarantee that APs will remain in the same locations. APs may be attached to mobile devices, or AP equipment may simply be moved. This leads to a requirement for the database of AP locations to be dynamically monitored and continuously improved. Lastly, the location of the APs is not known a priori, and hence there needs to be some independent means of locating the APs in order for them to be used for positioning. The CSR server implementation uses the other technologies present, namely GNSS and MEMS, to generate this information. This avoids the need to manually survey areas where Wi-Fi positioning coverage is required.

The chip supports Wi-Fi receive (sniffing) and positioning via scanning of the ISM band to detect any broadcast 802.11b Barker codes on any of the 14 channels. This process takes approximately 100 milliseconds/channel, producing a scan time of 300 milliseconds for the three primary channels, or a scan time of 1.4 seconds for a systematic scan of the entire band.

The usual configuration is for the SiRFstarV chip to be connected to the CSR Positioning Center (CPC) server via software running on a host processor in the device. On request, the CPC can then provide the device with all the APs known to be in the vicinity of the user. This data is sent as a sequence of spatially contiguous sets of APs in a tiled structure. The benefit of serving tiles to the user, rather than user’s position or only the APs instantaneously detected, is that the client device can subsequently operate independently with only occasional server contact. In fact, since the chip supports on-board storage of the AP tile information, it can also operate for extended periods without waking up the host, a feature useful for low-power geo-fencing and other location functions.

Another important aspect of the CPC is that is supports crowd-sourced learning of Wi-Fi APs. Client SiRFusion devices submit anonymous sets of Wi-Fi signal strength data and associated BSSIDs, together with contemporaneous GNSS and relative information from the MEMS devices. By collating all the information available in an area across users, the system is able to calculate the most likely locations for Wi-Fi APs and hence generate tiles available to provide to all users. Unlike crowd-sourced systems based on GNSS alone, CSR also uses relative data from MEMS PDR to extend the coverage area of the crowd-sourcing indoors. This produces better Wi-Fi positioning performance indoors.

Sensor Fusion

The GNSS, Wi-Fi, and MEMS PDR solutions offer varying levels of accuracy, coverage, and reliability. CSR has developed SiRFusion, a Kalman filter-based fusion engine in the SiRFstarV device, to combine all these location inputs. Sensor fusion is a critical component and does the job of fusing the multiple sources of position information to provide a single best estimate of position and confidence to the user. It takes as input absolute positions from GNSS and Wi-Fi and also any relative information derived from the MEMS PDR sub-system. Figure 2 illustrates the major components of SiRFusion.

Figure 2. Major components of SiRFusion.

To determine how to weight and smooth the different inputs, it is crucial that the individual input technologies provide reliable estimates of their confidence and correlation. As an example, we mentioned earlier that the quality of Wi-Fi positioning is variable and is best when strong APs are seen. A high quality Wi-Fi position, signified by a high confidence value, will cause the fusion filter to be strongly biased towards this positioning source. When the Wi-Fi position quality subsequently deteriorates, this is reflected in a lower position confidence, and hence the fusion filter down-weights Wi-Fi influence. In turn, this allows dominance of the MEMS PDR input until another sufficiently high-quality absolute position allows the filter to correct. The net effect of this behavior is that the MEMS bridges the position output smoothly between high-quality absolute position fixes and to a first approximation, any low-grade information is ignored. Another benefit is that individual Wi-Fi positions can be jumpy, because on an individual scan there is considerable variation in the audible APs and their signal strengths. Sensor fusion with MEMS PDR helps to smooth this out, providing a continuous trajectory and a more satisfying user experience.

Another job of the fusion engine is to transition smoothly from indoors where Wi-Fi and MEMS PDR dominate, to outdoors where GNSS dominates. This happens automatically in the fusion filter with the GNSS becoming increasingly dominant outdoors as GNSS confidence improves. Conversely, the Wi-Fi position accuracy will typically decrease outdoors and the dominant technology will therefore gradually dominate the solution. When technologies are not being used they can be switched off or placed in a maintenance mode to reduce unnecessary power consumption.

Performance Results

CSR has developed a demo platform with SiRFstarV and SiRFusion in a modified HTC Google Nexus One handset with Android. Figure 3 shows a modulewith the receiver and MEMS devices; the module is mounted inside the HTC phone shown in Figure 4. The data log includes PDR output, Wi-Fi positioning, GNSS positioning, and the combined sensor-fusion solution.

Figure 3. Module with MEMS devices.

Figure 4. HTC Google Nexus test phone.

A series of tests were carried out in Tokyo Station in Tokyo, Japan. The tests shown here were all done on the B1F level in the shopping area adjacent to the station. This area is two levels below the tracks and is below ground. There are no windows, and there was no GNSS reception. The environment also has lots of magnetic anomalies due to tracks, trains, elevators, escalators, and many people in motion, which affects Wi-Fi signals. Each plot shows an indoor map superimposed on the Google Earth image of the area. The narrow aisles in the map are about 5 meters wide. The map is used for presenting results only; it was not used to do map-aiding or map-matching.

AP harvesting and learning was done in this area before the tests were conducted. In each test, the phone is turned on, and SiRFusion uses Wi-Fi measurements and data from the AP database to determine the initial position without any assistance from GNSS. In each case, the initial position was determined within 1–3 seconds.

In Figure 5, the route walked is shown by the straight green line, with the start point in the lower left corner. Wi-Fi positioning is shown in red, the yellow isthe MEMS PDR solution, and the blue shows the SiRFusion solution, which in this case is combining Wi-Fi and PDR. The Wi-Fi position is not available every second and at times has discontinuities of several meters. This is due to the signal variability as discussed previously. The PDR solution shows a gradual drift that is more than 25 meters off track in places. This is not an issue for SiRFusion, as only the relative positioning is used from the PDR output. The SiRFusion solution shows a smooth continuous output that has a maximum cross-track error of about 7 meters. Note that the error of the SiRFusion solution does not follow the PDR solution. The absolute positioning provided by the Wi-Fi fixes keeps the solution on track.

Figure 5. Tokyo Station test showing Wi-Fi (red squares), PDR (light green squares), and SiRFusion output (blue); straight green line shows true path followed.

Figure 6 introduces a test with several turns in the corridors. The path walked is marked by the red flags, and took just under six minutes. The fusion solution is shown in blue. The start point was in the lower left. The fusion solution was able to detect each of the turns made while walking. The shape of the path clearly follows the marked path walked. The largest deviation from the path was ~7 meters. Typically, the solution was within 5 meters of the path walked.

Figure 6. Tokyo Station test showing turns; red flgas mark actual path, blue is SiRFusion output.

Figure 7 shows another path through the corridors, this time just over seven minutes in duration. Again, the fusion solution shows each turn correctly and in this case, the maximum cross-track error is about 5 meters. Figure 8 shows the same path, but with the output from three separate walks shown in green. A cold start was done before each walk. The results agree closely, showing high repeatability between test runs.

Figure 7. Tokyo Station test showing turns; legend as per Figure 6.

Figure 8. Tokyo Station test repeatability; light green shows three successive SiRFusion test runs.

To obtain a quantitative measure of the performance accuracy, the locations of several points in the Valley Fair Mall in Santa Clara, California, were determined. During several independent test runs in the mall, the tester went to each designated test point and indicated a marker in the log. The measured positions were compared with the determined positions to generate the performance statistics shown in Table 2. The cross-track error was 3.2 meters 50 percent CEP and 13.1 meters 95 percent CEP. These levels agree with the estimated results determined from the maps in the Tokyo tests.

Table 2. Accuracy test, Santa Clara Mall.

These tests show excellent results in availability, accuracy, stability, and repeatability. The availability is near 100 percent, with the only missing fixes being the first couple of seconds on startup. The position accuracy is sufficient to guide a user to the correct storefront, terminal, or track in a complicated indoor environment. The smooth continuous output can be used for voice guidance applications.

Applications

Continuous indoor positioning enables important consumer and commercial applications including indoor search, navigation, social networking, andadvertising on mobile devices, indoor geotagging on camera devices, indoor workout monitoring on fitness devices, and asset tracking.

Mobile Devices. Search, mapping, and navigation are popular uses for smartphones, tablets, and other mobile devices. These services are even more powerful when taken indoors in shopping centers, airports, train stations, and other public places. In a large shopping area, a consumer can search for the nearest store with items of interest and get walking directions to that store. He or she may receive a coupon or ad relevant to the store or item that they searched for. Business owners are interested in targeted mobile ads to help connect with interested shoppers.

Camera Devices. Location capability is emerging on camera devices for geotagging the location where a photo was taken so that it can be embedded with other meta-data in the image file. Geotagged photos can be easily shown on maps, sorted by location, and shared with others. Indoor positioning enables geotags to work inside as well as outside, completing the coverage availability.

Fitness Devices. Fitness watches and other workout tracking products use location to measure distance traveled, calories burned, steps taken, and plot workout tracks on maps. With indoor positioning, indoor workouts can also be included in consumers’ data analysis as they track a wider variety of workout types.

Machine-to-Machine and Asset Tracking. The benefits of indoor location extend the asset-tracking model from fleets of trucks and automobiles to include all types of valuable assets, from children to pets to merchandise and even data. It is valuable to provide an individual with their own location, but it is even more valuable to provide the location of objects that are somewhere else in an M2M application. The low-power, ubiquitous location capability of SiRFstarV and SiRFusion allows very small tags with months of battery life to be attached to virtually any object and in combination with an appropriate communication link (cellular, Wi-Fi or BLE) report that position to the CPC. From there, a cloud-based location service to carriers, retailers, malls, government agencies and others can add location to their product mix. This service can even be extended to provide data security so that sensitive corporate information could only be accessed by devices within an authorized area, and not in a public place such as an airport. By making ubiquitous location information available on almost any imaginable platform, the use cases are nearly limitless.

Conclusion

Sensor fusion algorithms have been developed and refined to address the problem of determining position indoors. Performance testing shows that the position availability approaches 100 percent, and accuracy exceeds 10 meters, 50 percent CEP. The fusion technology is suitable for integrating in a wide range of consumer and commercial devices. The solution uses existing wireless infrastructure and can be deployed around the world with no new equipment to install or surveying to perform. The self-learning capability adapts to changes in the signal environment.

Acknowledgments

Seiji Ishikawa and Shinya Ohno of CSR performed the testing in Tokyo Station and were instrumental in preparation and analysis.

ST Microelectronics provides the MEMS sensors used in much of CSR SiRFusion testing.

J. Blake Bullock was senior product manager responsible for CSR’s next generation of GNSS solutions. He has now transferred to Samsung System LSI Business and is responsible for GNSS and indoor positioning solutions. He holds a M.Sc. degree in geomatics engineering from the University of Calgary, an MBA from Arizona State University, and several patents in LBS and navigation.

Mahesh Chowdhary is senior director MEMS technology at CSR where he works on the integration of GPS, MEMS sensors, and wireless technologies. As founder and CTO of Acculeon, he pioneered the use of GPS and MEMS sensors in vehicle safety applications. He received his Ph.D. in Applied Science from The College of William and Mary, Williamsburg, Virginia.

Dimitri Rubin is senior director at CSR and is responsible for the development of the SiRFusion system. He has worked in the wireless communication field for 24 years.

Don Leimer is managing the GNSS Advanced Development group at CSR. Mr. Leimer has led and contributed to numerous commercial and military GNSS developments including GPS Phase I.

Greg Turetzky is senior director for location and technology strategy in CTO office at CSR. He has an M.S. in computer science from Johns Hopkins and holds a number of patents in GPS.

Murray Jarvis is a consultant research and development engineer at CSR. He holds a Ph.D. in physics and has worked on a variety of positioning technologies including GNSS, cellular and Wi-Fi.