Providing Indoor Location in the Real World
In my industry, we have a big challenge. We all intuitively feel that our phones should be able to tell us where we are at all times, including when we're indoors at places like hospitals, shopping centers, and office buildings. But how?
Since GPS works really well outdoors, you might assume the challenge is simply to build a system like GPS, but indoors.
Many companies have been trying to solve this problem for a long time using all sorts of strategies, from using Wifi signals already in the environment, to detecting subtle variations in the Earth's magnetic field, to decoding secret messages flashed by special lightbulbs on the ceiling (this is true).
We have our own approach that uses Bluetooth Low-Energy Beacons. And in this post, I'll reveal our deepest secrets about how it works.
But first, I'd like to talk about how engineers typically approach problems.
The Algorithm
One of my favorite work moments of all time happened while we were at a large and famous museum, creating their first mobile app. The project was being managed by a Big Consulting Company, and their project lead was standing in front of a whiteboard, talking to our development team.
At the time, the museum was using one of the very first indoor location systems (developed by a 3rd party), and it operated by measuring Wifi signals to compute your location. These signals tended to fluctuate dramatically, and the location quality was very poor as a result. In the museum's app, the "blue dot" would float wildly around, jumping 30 feet at a time, and it felt very unreliable.
The Big Consulting Company project lead loosens his tie, then draws out his proposed solution on the whiteboard. He says, "OK guys, we know the locations we're getting from the Wifi system aren't very good. So what we need from you is an ALGORITHM [he writes the word "algorithm" in a big box] that can translate these bad locations into good locations." Here's what it looked like:
I had to kick our lead developer under the table to stop him from saying something that might get us fired.
Answering the Wrong Question
We quickly realized that we, and Big Consulting Co, were too focused on answering the question "How do we improve location accuracy?"
This is the wrong question. It turns out the correct question is "How can we improve the user experience of this app?" Which is a totally different question.
So we came up with some more practical improvements. First we tricked the phone into emitting more Wifi traffic, which had the side effect of generating more bad locations from the system, which we averaged into a less bad location. Then we focused on the UI side, drawing a "blue circle" around the dot to indicate to the user that this isn't their exact location. And we filtered out location updates that were really close to your current one, preventing the dot from wandering around aimlessly like a six year old.
We then redesigned the entire app experience around the assumption that your location just wasn't going to be precise. We focused the "getting directions" experience around going from one big hall full of exhibits to another, instead of all the little steps you take to get there. After all, the hall exits were perfectly well-marked in the space already, you just need to know which one is next.
In the end, we created an app that worked great for users, navigating them successfully to the exhibits they cared about, which was really cool at the time. Normal users just did not care that the blue dot wasn't perfect.
Beacon-Based Location
When Apple announced the iBeacon API, it was more significant than many realized. iOS is an extremely restrictive platform, and this was the first official mechanism by which app developers could "hear" wireless signals from the world around them.
This was a big deal, because until then, the only practical way to get location indoors (besides the only-works-in-the-lab stuff like the blinking lightbulbs) was by using the Wifi network.
Wifi-based location has never been great, because Wifi was never designed for location, and you need to do a lot of collaboration between the phone and the network itself. But what if your company also builds Wifi networks? Well, it turns out you're still at the mercy of the "handset manufacturers" (Apple, Google, Samsung, etc.) since the quality of the Wifi chips and the capabilities exposed to you as an app developer are unpredictable (Android) or severely handicapped (iOS).
Both Google and Apple now have their own proprietary indoor location systems that operate primarily on Wifi. But to use them, you have to agree to give them all your maps and "points of interest" data, which most venues are not interested in doing. You also have to sign up and wait for them to go fly to your facility and walk around with scanning equipment.
So Beacons are the first means by which venues can build a great indoor location experience and deploy it themselves today without worrying about the competing interests of other companies.
How It Works
When we wrote the first prototype of our Beacon-based "blue dot" location system, we were in a hurry. We just wanted to see if the iBeacon API provided decent enough signal values to be usable for location at all. We started with a map and some known x/y positions of Beacons in our office.
We then used the iBeacon "Ranging" API to scan for the Beacons nearest to the phone. Let's say we get a list back containing five beacons, sorted in descending order of signal strength (technically it's RSSI but I'm simplifying here):
- iBeacon at location [30, 10] signal strength 90% - iBeacon at location [40, 15] signal strength 85% - iBeacon at location [55, 19] signal strength 76% - iBeacon at location [20, 29] signal strength 70% - iBeacon at location [10, 43] signal strength 40%
To keep things simple, we take the three Beacons at the top of the list and throw away the others. Then we convert signal strength to a crude estimate of distance and combine the location of the three Beacons, weighted by relative distance.
It worked surprisingly well. Well enough to start developing our Beacon product. We spent most of our remaining time building things like an app to make configuring and deploying Beacons easy and fun. We also made some cool visualization tools to see the signals of surrounding Beacons. And we spent a lot of time making it work on Android.
We ended up shipping the product with the "quick and dirty" algorithm above with very few modifications, mostly around signal averaging. And that's still what we use today.
Every time we hire a new mobile developer, their first task is to try and improve on this location system. As engineers, each one has immediately focused on the "algorithm" part. We've tried lots of complicated math, like least squares, or actual trilateration. But this is basically a hazing exercise, since improving the algorithm is answering the wrong question. In the real world, the signal data is simply too unreliable for the algorithm to really matter all that much.
Instead, we've made actual improvements on the user experience of location by thinking outside the algorithm. For instance, when getting directions, if you're close enough to the pathway, we'll "snap" your blue dot to the routing line.
(Guess what: your phone already does this with wobbly GPS locations when you're driving on roads.)
We also use the phone's accelerometer to detect if the phone is moving. If you're standing still, we try not to move the dot around too much, and we average many seconds worth of signal data to make the location more accurate and stable, and as a result the location feels significantly better.
Designing for the Market
We started Meridian with the question, "How can we provide great location-based mobile app experiences at the places we visit?"
At first glance, it seems like solving indoor location is 90% of the problem. And a lot of companies are focused on just that. But knowing your location is just step one. In order to provide a useful mobile experience, you need the venue to be involved. How useful would a museum app be if it only gave you your x/y position and didn't know anything about, you know, the artwork?
We concluded that our customer had to be the venue itself. The museum; the hospital; the stadium. And we needed to build a complete solution. That meant building not only an indoor location system, but drawing mobile-friendly maps, providing a CMS for points of interest, and even building mobile apps from scratch in many cases, since most customers didn't have any existing app to integrate with.
Now that venues are investing more in their own apps, new startups are filling in the gaps by providing highly specialized solutions for different verticals. We realized early on that we could never make a one-size-fits-all app for everyone, and so we also focused on building a great mobile SDK. Now we have partnerships with startups like VenueNext and Robin, who are building amazing features like in-seat food delivery and conference room booking that use our Beacons under the hood.
As for our location algorithm, it hasn't changed much. Our current efforts have instead been spent making Beacons easier to install and maintain. We created a "Beacon Management" system that uses your Aruba wireless network to keep tabs on up to many thousands of Beacons. And in order to get this technology into even more places, we've now created a standalone device called the Aruba Sensor that will manage your Beacons even if you don't have an Aruba network.
Secret Sauce
We've never been very secretive about our location system. We explain how it works to customers all the time, because it helps when placing Beacons to have a simple and predictable model to work against. If you're not getting a good location in the conference room, it's easy to understand that, oh, if I place another Beacon over here then it'll pull me into the room more reliably.
In fact, I've learned to be generally skeptical of any technology that cannot be clearly explained by someone who claims to understand it. But if a new amazing system does come along that works better and makes more sense, then we'll be happy to use it. After all, location tech by itself isn't the answer—it's delivering a complete product that customers and users love.
