A Three-Sensor Model for Indoor Localization

Chaitanya Gharpure Vladimir Kulyukin John Nicholson
Computer Science Assistive Technology Laboratory
Department of Computer Science
Utah State University
Logan, UT 83422-4205

ABSTRACT

A three-sensor model is presented for localizing visually impaired navigators indoors. The model uses Markov localization to fuse Wi-Fi signals, digital compass readings, and readings from a computer processor clock. It is experimentally shown that the digital compass and the processor clock improve the Wi-Fi localization accuracy.

KEYWORDS

Visual impairment, assisted navigation, indoor localization, Wi-Fi, compass, sensor fusion

BACKGROUND

There are approximately 11.4 million visually impaired people in the United States [1]. Finding and navigating a path in unknown indoor environments is a major hurdle towards achieving universal access for visually impaired people. Localization, i.e., the ability to determine one's current position with respect to a critical landmark, is an integral part of wayfinding. Many approaches to localization rely on the Global Positioning System (GPS) [2]. However, GPS does not work indoors. Other approaches which use infrared signals and Braille also have their limitations. Talking Signs© [3] has not been widely used due to the high cost of installation. While the Talking Braille infrastructure [4] requires that every BRL sign in the building be equipped with a special chip and powered. There is also the limitation of direct line of sight for infrared devices.

Recently, several researchers attempted to use Wi-Fi signals for indoor localization [5][6][7][8]. Triangulation, Bayesian classification, Monte Carlo sampling, and wireless fingerprinting are just a few of the many approaches to indoor wireless localization that have been tried. In [9], the authors characterize the limits of a variety of approaches to indoor localization using signal strengths from 802.11 routers. They show that a median error of 10ft and a 97 th percentile of 30ft are expected in a good algorithm and high sampling rate. They also suggest that adding additional hardware or altering the model of the environment is the only alternative to improve the localization performance. However, Wi-Fi localization has two distinct advantages: existing infrastructure and low cost.

HYPOTHESIS

It is hypothesized by the investigators that the addition of two sensors, a digital compass and a processor clock, improves the Wi-Fi localization accuracy. Time stamps from the processor clock are used as a crude simulation of a pedometer. It is assumed that the user is walking at a constant speed.

METHOD

Figure 1: USU Old Main Building Fourth Floor map d (Click image for larger view)

Our method consists of three steps: 1) obtain the physical distances between all adjacent locations, 2) collect the wireless training data at selected locations, and 3) use Markov localization at run time to fuse readings from the Wi-Fi card, the digital compass and the processor clock.

The method was evaluated on the 4-th floor of the Old Main Building at Utah State University. Wi-Fi signals are digitized with Kismet©, an open source wireless network detector, sniffer, and intrusion detection system. Signal strengths were collected at each location in each possible direction of travel at that location. This training data were collected in two sets: first, with 5 Wi-Fi sensors and for 2 minutes at each location and direction and second, with 10 Wi-Fi access points, for 30 seconds at each location and direction. The test runs were also run differently for the two sets. Every sensor sample during the test run consisted of the Wi-Fi signal strength values, compass reading, timestamp, and actual location. A Wi-Fi signature of one access point for a location is calculated from the training data is represented as a Gaussian distribution.

The digital compass was briefly calibrated for the environment. It was found that the ranges for the four directions were as follows: North (N): 290 to 360 degrees, South (S): 100 to 200 degrees, East (E): 0 to 100 degrees, and West (W): 200 to 290 degrees. A single sample of sensor readings taken at run time looks as follows: 56 0 109 89 70 270 962589259.590108 , where the first five fields represent the signal strength values for the five Wi-Fi access points. The sixth field is the digital compass reading and the last field is the timestamp obtained from the processor clock.

Equation 1. d (Click image for larger view)

Markov localization is used at run time. It is assumed that the starting location is known. Thus the initial probability distribution is Dirac where the probability of being at the starting location is 1, and everything else is 0. The probabilities of all locations are updated after every sensor reading using the recursive Bayesian update rule shown in equation 1-a. The sensor model is the maximum likelihood (ML) estimate of the Wi-Fi signal strength values at a given location. The ML of a sample of Wi-Fi signal values for a location L is calculated using equation 1-b.

According to the Markov assumption, the action model represents the probability of being at a location L, given the previous action. In our case, the action is the distance traveled since the last update. A constant walking speed of 1.2 m/sec is assumed. Thus distance traveled will be d = 1.2 * (T curr - T prev ), where T curr is the current timestamp, and T prev is the timestamp at previous update. Location probabilities in the action model are calculated using equation 1-c. The denominator in equation 1-a, represents the normalization constant. The timer is reset every time the direction changes or the probability of the winning location reaches a particular threshold.

RESULTS

As seen from Table 1, the localization performance is highest for set 1 when all sensors were used. Bad localization with Wi-Fi in the second set is because the training data was collected only for 30 seconds at each location, in a single session. Table 2 shows the localization accuracy at individual locations using all sensors for set 1. The clock and the compass together give good localization performance for both sets. It was also observed that the performance with the clock and the compass deteriorates in long hallways with multiple locations. This is because of the variable walking speed within a run.

DISCUSSION

The results seem encouraging for further research. Assuming constant walking speed, high localization performance can be achieved by fusing Wi-Fi signals with readings from the processor clock and digital compass. It is hoped that a real pedometer will improve localization and eliminate the constant speed assumption. Wi-Fi localization appears to give high accuracy at locations that are far apart.

REFERENCES

1. LaPlante, M. P. & Carlson, D. (2000). Disability in the United States: Prevalence and Causes. Washington, DC: U.S. Department of Education.
2. http://www.senderogroup.com/gpsflyer.htm. "What is GPS-Talk?" Sendero Group, LLC .
3. Marston, J. & Golledge, R. (2000) Towards an Accessible City: Removing Functional Barriers for the Blind and Visually Impaired: A Case for Auditory Signs. Technical report, Santa Barbara, CA: Department of Geography.
4. Ross, D. (2004). Talking Braille: Making Braille Signage Accessible at a Distance. Proceedings of RESNA 2004, Orlando, FL.
5. Ladd, A. M., et. al. (2004). On the Feasibility of Using Wireless Ethernet for Indoor Localization. IEEE Transactions on Robotics and Automation, Vol. 20, No. 3, June 2004.
6. 6. Kulyukin, V. & Nicholson, J. (2005). Wireless Localization Indoors With Wi-Fi Access Points. Proceedings of RESNA 2005, Atlanta, GA.
7. Letchner, J., et. al. (2005). Large Scale Localization from Wireless Signal Strength.
8. Haeberlen, A., et. al. (2004). Practical Robust Localization Over Large-Scale 802.11 Wireless Networks. In proceedings of MobiCom, Philadelphia, Pennsylvania, Sept. 2004.
9. Elnahrawy, E., Li, X. & Martin, R. P. (2004). The Limits of Localization Using Signal Strength: A Comparative Study. In proceedings of IEEE SECON, Oct. 2004.

ACKNOWLEDGMENTS

The study was funded, in part, by two Community University Research Initiative (CURI) grants from the State of Utah (2004-05 and 2005-06) and NSF Grant IIS-0346880. All grants were awarded to the second author.

Author Contact Information:

Chaitanya Gharpure
Computer Science Assistive Technology Laboratory
Department of Computer Science
Utah State University
4205 Old Main Hill
Logan, UT 84322-4205
Office Phone (435) 512-4560
EMAIL: cpg@cc.usu.edu .