Kalid's Math and Science Pages

Indoor positioning using 802.11b wireless networks

My new project: indoor positioning on a robot

Introduction

Background: I chose to design an indoor positioning system for my independent work at Princeton. I originally wanted a GPS-like system, but GPS doesn't work indoors! Alternatively, I tried to use a phase-shift system; you can calculate your position based on the phase differences of two transmitters. I decided it was too difficult to make both the transmitter and receiver from scratch. I'd have to build hardware, write an OS, create interface to normal PC, all in less than a semester. A friend showed me a Microsoft Research paper that used wireless networking for indoor positioning. And so it began.

Basic Idea: First, go to various locations and record the signal strengths of various access points (APs) in a table. Later, when you visit a location, compare the signal strengths that you see to the table. The closest entry is probably your location.

My addition: I thought that a directional antenna could improve accuracy. I found a lot of sites describing homebrew antennas, do I decided to use those.

Advantages

Cheap! Wireless card $80, homebrew antenna $5-10 dollars, N pigtail cable $20-40.
Uses existing technology. The most complex part, the card, is easily bought. The antenna is easy to build, and I wrote some software so you don't have to! Intended for use indoors, where a wireless network is easily installed (if not already).
Specify your own level of resolution (more points recorded = better resolution)
Easy setup: Walk around, record some locations, and you are done. Not much external hardware (access points, wireless card, that's it).

Disadvantages

Need to visit locations beforehand. This isn't so bad, since it is indoors, and you aren't spelunking in unknown caves or exploring the Bermuda triangle. Use GPS for that :). It only takes about 10-20 seconds to record a point for decent precision. This is also better than the brute-force IR ActiveBadge system, which makes you install a receiver at every point! However, it still might take a day to setup a large office building. Still, that's not bad.
Not good for frequently changing environments. If walls/floors/furniture are shifting often, signal strengths will vary. This probably isn't likely.
Precision. The longer you wait at a point, the better (I average the signals received). Again, 10 seconds is all you need for resolution of 2-3 meters. This is far better than GPS was before it was unscrambled it for civilian use.

Documents

Slides
- End of semester talk PDF - HTML
Final paper -djvu (300k) - HTML (60k)
- djvu (deja vu) is a PDF-like format, with much better compression. The original PDF was 8MB!
Code
- capture.pl : usage: perl capture.pl positionName
- record.pl usage: perl record.pl

Results

Average case: 1-2 meter resolution.

Informally, the system can resolve to about 10-15 feet with extremely high confidence, with the average case on the order of a meter. I have the feeling that I won't be able to determine an absolute level of precision. Instead, the system may give a resolution and a probability of accuracy, i.e. "You are within X meters of a position with Y% probability." I think that 99% probability will occur at about 15 feet (5 meters). I'd go all metric if I could, but I tend to visualize distances in feet :).

Preliminary results: Signals sampled every second at the same location. Each color is a different access point.