Thursday, March 12, 2009

ETech: All the Ways To Find You

I'm in "All The Ways to Find You: GPS and other Wireless Signals" with Nick Brachet from Skyhook Wireless the people that do that sort of thing...

Nick Brachet

Nick is going to talk today about all the ways to find and locate a phone, laptop or desktop at any time. First, the easiest and most fun location technology, where is the storm

Count the seconds between the time you see a lightning strike, and the time you hear thunder, divide by 3. The result is the distance to the storm in kilometers...

A lot of location systems work this way, they know the location of a fixed point, and they measure your distance to that point.

To unambiguously locate you you need at least three reference point, the more points you have the more accurate your location can be pinned down. In practice of course you never know anything exactly, so even with multiple references point you always have a error.

A GPS receiver measures the distance to a satellite by calculating the time it takes for a signal to travel from the satellite to the receiver. But what is the satellite's time? what is my time? A fourth satellite is needed for time synchronisation. But where are the satellites, precisely? As well as a time stamp each navigational message includes the position of the satellite and its path in its orbit, and a subset of the almanac - data about the other satellites in orbit, including a rough position. However the ephemeris (and the almanac) may be delivered via other mechanisms, e.g. backhaul via the cell phone network.

For location technology there are many metrics, one of these is how long it takes to get a location fix. With GPS on a cold start it takes on average 23 seconds, with a warm start, where the time and ephemeris is still valid the time-to-fix is much less, around 4.2 seconds on average. Faint signals (-135dBm and lower) complicate decoding process and may cause the receiver to drop frames, increasing the time-to-fix.

Typical GPS receivers need -140dBm or better, and cannot decode below -145dBm. Outside you normally get a signal from -125 to -130dBM. Inside in your home you get a signal from between -135 to -145dBM, however in a high-rise building the signal will go down to typically between -135 to -160dBm.

Accuracy is very important, and there are many factors contribute to error, the most important is timing inaccuracy. One of the biggest problems is multi-path signals, the satellite signals bouncing off surfaces (building, planes, etc). End-user accuracy is typically 10-30m in a good area. That's not generally good enough, onboard navigation systems generally fix your position by assuming your car is actually on a road.

Moving on to Wi-Fi positioning. There are hundreds of millions of access-points around, so it's easy to determine your location? Okay, but we need to trilaterate. We need the distance to at least 3 access-points and the exact position of the access-points. It turns out there is a quadratic relationship between the signal strength you receive and the distance to the access point. So in practice, distance to an access-point can be estimated by measuring received signal strength. The second problem is solved by driving, and walking around neighbourhoods, malls, campuses and collecting Wi-Fi signal fingerprints, then calculate each access-point's position by (reverse) trilateration.

Conventional wisdom for the range of an access point is about 500ft, but some times they have much larger coverage, some over a kilometer wide. This can happen for many reasons, perhaps the signal is boosted, but perhaps the signal is just bouncing off water, or there was just nothing in the way to prevent the signal propagating. The access point might be in a high-rise building.

The time-to-fix in network mode, where the client collects the Wi-Fi fingerprints, but the location is calculated remotely. However in tiling mode, where the client has a small portion of the database cached locally, and your location is calculated locally the time-to-fix can be sub-second.

Coverage in Europe

So Wi-Fi positioning an GPS positioning complement each other very well...

Accuracy, distance to access-points is only an estimate and we have unmanaged reference points, and access points do move. But many readings compensate. The end-user accuracy is typically 20 to 30m in good coverage areas.

...and we're done.