What algorithm should I use for wifi geolocation?

Question

School Pickup Use Case (update)

It might be helpful to go into a more concrete use case instead of the original backyard example below. Local law enforcement has started cracking down on use text messaging and cell phone use in school zones. This presents a problem for parents picking up kids after a middle school function. Even for those who flaunt the law, the cell tower quickly becomes overloaded when hundreds of kids call their parents at once. The campus is large, with wifi coverage. It seems like it should be possible to write a mobile app that would allow a cell phone user to send a text message containing a list of wifi signal strengths to a webservice. The web service would then create a location fix and push the message to the parent's on board navigation device. The parent would then drive to the correct location on the campus.

Backyard Use Case (original) When I take my laptop into my backyard and choose "view available networks" I see a list of my 4 neighbors. As I walk around, the relative signal strengths from my neighbors changes.

I'd like to stand with my laptop at known locations in my back yard, click on the map and collect points with 4 different signal strengths.

After collecting a lot (but not too many) of these calibration points, I'd like to then write a program that takes 4 wifi signal strength levels and estimates a location in the form of an error ellipse. The signals might be measured using a different device than the one used to collect the original calibration points.

What algorithm should I use?

I do not want to disturb my neighbors by asking them if I can come in and survey the exact location of their router.

I can assume, however, the location of my neighbors routers does not change.

Answer 1

Check perhaps these papers:

• RADAR: an in-building RF-based user location and tracking system
• WLAN location determination via clustering and probability distributions

Answer 2

It sounds like you don't know the signal locations very well, so you need first to estimate them and then, given those estimates, triangulate your position.

If you want some accuracy and realism, consider adopting a likelihood model for the signal strengths, finding the maximum likelihood, and making a gridded map of the location probability computed from the maximum likelihood estimates. The global maximum on the grid identifies the best estimate of the location and the contours (relative to the maximum) give confidence sets for that location.

A general likelihood model is obtained by positing a formula for the signal attenuation and allowing for error. You won't get very far with a completely general formula (with an angle- and location-dependent attenuation function), so you'll have to simplify. For instance, you might consider a "universal" attenuation function, call it f, so that if the source strength at a WiFi location x equals a then the expected strength at another location y is given by

z(y; x) = a f(|y - x|).

For example, you might consider inverse-square attenuation for which f(t) = 1/t^2 provided the distance t is greater than some small threshold. As another simplification, you might take the strength reading z(y;x) at location y for the source at x to differ from the expected value by a normally-distributed error; assume all errors are independent; and assume they all have the same standard deviation (s). The contribution to the log likelihood of a strength reading z then becomes

L(y,x) = -[(z(y;x) - a f(|y-x|)^2 / s^2 + ln(s)]/2.

The log likelihood to be maximized is the double sum of L(y,x) over all locations y and all sources x. It is a function of the unknown locations, the unknown source intensities, and the unknown standard deviation of the errors. It's straightforward to find the optimal standard deviation and optimal source intensities (take partial derivatives, set those to zero, and solve), but for realistic attenuation functions f you have a non-linear problem for finding the locations. However, in your example it involves only 13 parameters so you should be able to dump it into, say, a multivariate Newton-Raphson optimizer and quickly get a good answer. (The statistics literature is full of methods to solve these kinds of equations.)

If you additionally assume the second device has proportionally greater sensitivity than the data-collection device, it will make little difference in the model I have proposed (because the signal strengths enter multiplicatively). In fact, if you let the errors scale with intensity (so they have standard deviation a *s* rather than s) the difference between devices should be inconsequential.

In order to keep this simple I have skipped over some statistical niceties, such as the fact that this is a multivariate prediction interval problem, not a confidence interval problem. If the amount of error is not great (i.e., s is small), the difference will not be of much consequence.

Answer 3

I just found a tutorial for mapping WiFi networks with Kismet, gpsmap, gdal and GRASS. Search for "Mapping Wifi Networks with Kismet, GDAL, and GRASS" at http://casoilresource.lawr.ucdavis.edu/drupal/book/export/html/96

Answer 4

If you are collecting the location with gps I think you are looking at two differing error factors. one for the gps and the other for signal strength.

Answer 5

Can't you leverage one of the existing WiFi positioning systems such as Skyhook Wireless or Core Location in Apple's iOS? Skyhook allows you to add Wi-Fi MAC addresses to their database manually, iOS collects Wi-Fi MAC addresses automatically using GPS equipped iPhone's.

Answer 6

Kirk,

While I may be wrong, I think you're way over complicating things. Though to be fair, not being from your part of the world I don't know what limitations you're working with in a school campus setting.

While most mobile devices already support GPS and or Cell tower triangulation, for WiFi, SkyHook is the answer for the following reasons: 1. Their database of WiFi locations is HUGE. 2. Every time an application using SkyHook is used, it adds newly found WiFi networks to the database, with position. So the more it's used in an area, the more accurate it becomes. I'd guess that in a high density location like a campus, if there's not already good coverage, it will have in a matter of days of regular use. 3. Some phones use SkyHook as part of their location API's, meaning that more and more normal phone APIs will have this already built in.

To be honest, unless you're wanting this service to be available on laptops (most new browsers have SkyHook built in), most phones now have GPS, which can be accessed via the native phone APIs, be it iOS, Android, WP7 or BlackBerry. The other option would be to make it a mobile web app, which would just use the browser location API, with access to all location tools on the phone anyway.