# What algorithm should I use for wifi geolocation?

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.

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.

• Thanks Bill, this looks doable. With laptops I just realized the signal is sensitive to antennae orientation. Not sure if this is true with cell phones. Would the location fix be good enough for the middle school use case? – Kirk Kuykendall Oct 26 '10 at 16:38
• You can handle orientation but it gets more complicated and would need more readings. Consider instead using the maximum signal among all possible orientations at each point. The middle school use case is an interesting variant in that it suggests doing your best to identify the WiFi sender locations and strengths once and for all. After that it's a triangulation exercise. One concern I have is that source strengths can vary, often unpredictably. That can really screw up the triangulation. Consider adding an initial screen for outlying (low) signals so they don't ruin the fix. – whuber Oct 26 '10 at 16:51

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

• – radek Dec 21 '10 at 22:40

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.

• In this context Kirk could actually verify the locations in his back yard independently (i.e. just take multiple GPS readings from each location). – Andy W Oct 25 '10 at 15:22

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.

• This might not be a bad idea if he wanted to figure out where he is. But he is trying to figure out a way to collect the locations of the networks himself. Moreover, he is trying to triangulate his position based on the strength of the WiFi signals. I am not sure if the commercial solutions do that. – jvangeld Dec 11 '10 at 4:30
• @jvangeld: As far as I understand, Core Location in iOS uses the Wi-Fi signal strength to triangulate the position. For the mentioned school pickup case, it would be the way to go. – Ortwin Gentz Dec 11 '10 at 23:58

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.

• I thought skyhook collected data via wardriving. I can't imagine them driving onto school roads, though I suppose those are public. – Kirk Kuykendall Dec 22 '10 at 3:29
• You're correct, but because clients 'expand' their database in addition to their war-driving, you'll probably find they have coverage anyway. You could always test by loading up Opera onto your laptop, go on campus with maps.google.com and WiFi enabled, and see where it puts you. – BlinkyBill Dec 27 '10 at 3:47