The Long Weekend Website

iPhone Background GPS: Accurate to 500 meters, not enough for foot traffic

By Mark on July 22nd, 2010 in Technobabble
Tags: gps, ios4, iPhone, location monitoring

This is the third article in a series on iOS4′s new background location monitoring functionality using an iPhone 3GS (see the first and second article).

We scoured the Internet for the answer to this question: “how far is far enough for the phone to execute my app in the background?”. In other words, does this technology make sense yet?

So, I conducted a 12-day test using 8 devices (seven 3GSes and an iPhone 4), and here I present the cold, hard data.

I like dessert first, so here’s a pretty graphic. Next, assumptions and observations. Finally, methodology & analysis rambles on at the end.

Assumptions

• This test focused on three locales: Melbourne, Australia (4 devices); Tokyo, Japan (3 devices); and Chicago, United States (2 devices) — that’s nine because one guy went to Chicago from Tokyo!
• These areas are urban; minimal suburban and rural data is included (our testers travelled outside of these cities occasionally). We assume the results are indicative of an urban environment.

Initial Observations & Hypotheses

• After travelling 2,500 meters (1.55 miles), there is a 95% probability that the iPhone 3GS will execute your application in the background. Often times, movement of 500 or even 250 meters was enough, but it’s not predictable nor reliable.
  
• Background location events are “accurate to 500 meters“. Not 501, not 499. If your app consistently requires greater accuracy than 500 meters, you will have to combine background readings with an active GPS reading, which will greatly impact battery life for your application.
• Train stations often have cellular towers installed in them, so travelling by train generates relatively predictable location events.  GPS coordinates were received even when the phone was underground in a train station in Tokyo, because it sources the data from towers, not satellites.
• Travelling by car (particularly freeway) generates relatively predictable location events; it is relatively easy to travel a few kilometers in a short span of “user time” (what the user perceives to be as a long time).
• Location events are often generated at fixed intervals along a routine path. Notably, users who commuted along the same route tended to generate events in the same (approximate) locations on different days.  Since cellular towers are used to calculate position, and the towers are in fixed locations, this made sense. The downside: “holes” in between.
• It is easier to convince complete strangers to be study participants than your own girlfriend when the topic is “location monitoring”. However, I still need to collect more girlfriend data points before I can say so with statistical significance. Also, it should be noted that even talking about inane concepts like “collecting girlfriend data points” appears to negatively influence the procurement of said data points.

If you’re interested in the technical bits, read on. Warning: code and method calls abound.

The Prototype & Test Period

Allan and I wrote a prototype using the new SDK (4.0). It registered as a “location” background app using the UIBackgroundModes plist key, and when executed in the background, it would:

• Instantiate a CLLocationManager object in the app delegate.
• Receive the updated location event via the didUpdateToLocation:fromLocation: delegate method.
• Send the new location data, an accuracy reading, the user’s battery level, and a timestamp to the Long Weekend server, requiring no user interaction.

Key points of note is that the application did not cache anything, so if the user had no network connection at the time, we would be missing those data points.  That said, location events are generated in response to cellular tower changes, so it is unlikely that many events were generated during these times.

The test began on July 7th; I summarized the data on July 19th for this report.

Data Analysis

There were a total of 1,140 location events reported to our server from 8 devices during that period. 214 of the events were generated when the application was active (e.g. the user had purposefully opened it). When active, the application made use of startUpdatingLocation, not background monitoring, so we excluded those to leave 926 data points.

Also, CLLocationManager has a tendency to report multiple events in a very short span of time, even in the background (less than 10 seconds apart). I am not yet sure why this is, but it could be due to Core Location’s caching scheme. Usually, when this happened, the second event would be much more accurate than the first reading (move from 500 to 80 meters, for example).

A few of those “initial fix” data points have been removed from the set, as their accuracy was low, and the phone immediately “corrected” by sending a second event. After removing these, we had 851 events.

Finally, each location coordinate was compared to the one preceding it (tracing a path of the user) for each device. We calculated the difference in distance and time between events based on the coordinates and timestamps of each event.

Distance Travelled Between Background Location Events

Let’s have that distance graph once again:

The yellow line is the aggregate percentage of all points (right Y-axis), the maroon bars are the number of data points for each “bin” in the distribution. Note that the bin numbers are “less than or equal to”. This means that 122 data points were between 751-1000 meters.

What we see quickly is that it’s not a normal distribution, but there are patterns.

First, 41 data points that have a change in location of 10 meters or less. I speculate (with no data analysis to back it up) that these events are additional “one more time” events when CLLocationManager sent another event very quickly. My screening did not catch them all.

Next, there are a large number of events between 101-250 meters, but only half as many between 251-500 meters. I have one speculation – but I am really not sure.  Could it be that when a user happens to be on a “boundary” between two towers, they are bouncing back and forth, and the phone generates excess events despite not moving very far?

Overall, we can see that 95% of all the location events are happening inside of the 2,500 meter mark. That has been the question I’ve wanted to answer: “How far does the user have to move before I’m relatively confident his or her phone will notify my app about the change?”

Note the growing trend towards the end of the data set.  One Japan-based user rode Japan’s bullet train (shinkansen). When I graphed these points specifically, I saw that that user went into a tunnel (read: no network access), and came out of it 30 kilometers later (this happened repeatedly). Not surprisingly, that phone also won the land-speed record for the data set.

The sparseness of that data subset (~20km intervals) could also be explained if the bullet train were too fast for Apple’s cell tower algorithm to catch up (US-based companies rarely engineer for high speed train travel!). This is pure speculation, admittedly. I’d like to know the real answer. Cupertino? Anyone?

Timespan Between Background Location Events

Here’s the time graph. Note that the cumulative growth function (read: the yellow line) is very similar to the distance graph.

Also note the “long tail”. Ross came up with one the reason why this was happening: when users go home for the day, their location won’t change until the next morning, ostensibly. 20,000 seconds is 5.5 hours, so this seems plausible. The same would go for coming & going from the office.

Our prototype software was smart in one sense: if you turned off your phone and turned it back on, the data would be treated as a separate “set” (thus resetting the timer/counter between points). However, if users left their phones on overnight (common), it keeps the same session.

Distance Versus Time

85% of the events occurred within 600 seconds (10 minutes) and 6 kilometers. That data has been graphed above to look for correlations. We didn’t find any – but you can draw a rectangle from the origin to 2km and 200 seconds (3 and 1/3 minutes) to see that most data points lie here – most events are generated when people are moving.

Also, anecdotal testing indicates that foot traffic may not move significantly enough for this technology to be Totally Awesome.  That said, people don’t usually walk 2 kilometers – especially us Americans, who probably can’t tell you how far a kilometer is anyhow.

GPS Reading Accuracy Data

I ran a distribution of all of the accuracy readings. I found something odd. Let’s see if you can find it.

When I looked at the data closely (not just the distribution), I noticed that most of those readings are 500 meters on the dot (54% of all readings, to be exact). I wonder what Apple’s code inside Core Location looks like. I’ll wager a guess:

- (CLLocationDistance) accuracyInBackground
{
  if (_planetsArePerfectlyAlignedToStevesHouse)
    return arcrandom();
  else
    return 500.0f;
}

Okay, jokes aside – it’s basically 500. Apparently, when you get multiple readings right in a row, you can get numbers as low as 11 meters of accuracy. But it’s 500 meters. That’s what you should expect. What is interesting is why it’s always 500 exactly. Does anyone else think that this is fishy?

(And no, I know what you’re thinking – my desiredAccuracy property in CLLocationManager is not set to 500.  If you RTFM, you’ll see that background location events ignore that flag anyhow.)

So What Does It All Mean

I’ve already stated the observations/conclusions above, but I’ll synthesize further, since you’ve actually made it this far (gold star for you!).

500 meter accuracy means that for the point Core Location returns, you could actually be 500 meters in any direction from that spot.  Since a location event is only delivered once every kilometer, you’d need a full 2KM minimum of movement to assume that a user has passed, or will pass, a given location.

So much for Apple’s dry cleaning.  I’m already a mile down the road, Steve.  But there is hope for startMonitoringSignificantLocationChanges!

Pathfinding techniques at the code level, as well as keeping users inside your app will win the background location game (when the user launches the app, you can get accurate coordinates – so the longer the user stays inside the app, the better the “feeling” of the background behavior).

And that’s exactly what we’re doing at Long Weekend, right now: making that app.  Updates to come.

[UPDATE: I've received enough enquiries here and elsewhere that I've finally put in the effort to make some of the source code used in this experiment publicly available via an MIT-style license (=do whatever you want with it, but don't blame me, and include my copyright notice in the code if you change/redistribute/use). Please understand that we cannot offer the full Xcode project here as it's proprietary. The 2 classes included in the file are my CLLocationManager delegate class, and a logger class used to log events to a web server.]