Article summary
On a recent project, we were using iBeacons and Core Location monitoring and ranging to track a user’s location in an indoor space. iBeacons are placed around the space and each iBeacon maps to a real world room or area like “conference room” and “entry area.”
We had a simplifying assumption that beacons, Core Location regions, and real-world regions have a one-to-one-to-one relationship. We were pretty happy with how well it was reporting locations with up to 20 beacon regions, but “Core Location limits to 20 the number of regions that may be simultaneously monitored by a single app.” So we needed to engineer a way around this limit in order to track more than 20 distinct locations in our system.
Where We Were Starting From
A user’s phone was often in range of multiple beacons, so we implemented an algorithm to choose the beacon region that best represents the user’s actual location in physical space. We did this by calculating a likelihood score based on a comparison (see image below) between:
- the distance that CoreLocation ranging reported between the beacon and the user’s device (this field is ‘accuracy’ but in our setup was a workable proxy distance) and
- a configured “radius of interest” value that defined real-world area we want that beacon to represent.
The algorithm then chose the beacon region that had the highest likelihood score and reported that beacon’s region as the user’s location.
We were using a higher power level on iBeacons to get more sensitive accuracy readings, which we were using for distance. However, with the high power level, the iBeacons were visible to the phone far outside the radius of interest. The previous image shows a green circle representing a large area covered by the iBeacon’s signal, outside the radius of interest represented by the blue circle.
When the location tracking app is running in the background on the phone, our approach relies on the fact that when the user enters or exits a monitoring region, the app process ranges for a brief period (though the usual use case for Core Location ranging is with the app running in the foreground rather than the background).
Breaking the Rules
We experimented with two approaches to monitoring more than 20 CoreLocation beacon regions in our app:
Four-color Theorem Approach
Consider our beacons as nodes in a graph, where an edge represents two beacons’ regions being adjacent in real space, and the floor plan as a plane. If we can draw that graph without intersecting edges, the four-color theorem (from the field of graph theory) tells us that we could assign each iBeacon to one of four Core Location regions such that no adjacent iBeacons are in the same Core Location region. Theoretically, when I move between any two beacons, I’ll exit one Core Location region and enter another. The enter and exit monitoring events should trigger the ranging we need to update a user’s location.
This should get us “enter” and “exit” monitoring events as a person moves from beacon to beacon. In practice, we’d probably want more than four to make it easier and to account for overlaps, but there’s a lot of leeway between our theoretical minimum of four and Core Location’s limit of 20.
Neighbors Approach
Assign each beacon 20 or fewer neighbors (the beacons nearest it in space). When a user enters a beacon’s region, update the list of beacons we’re monitoring to that beacon’s neighbor beacons.
The four-color approach seemed attractively elegant and required less programming than the neighbors approach. We could accomplish it just by configuring each beacon’s major numbers. All the beacons in the same Core Location region would have the same major number, and we’d use the beacons’ (shared) UUID and major numbers to define our Core Location regions for monitoring. That way multiple beacons would have the same CoreLocation region, but we’d get the enter and exit monitoring events we needed to range, and we could use ranging to get the distance readings we need to calculate the likelihood score for each beacon the user is in range of.
Experimenting
Like the true test-driven developers we are, we tried out the four-color approach first because we could test it in less than an hour. Knowing that the real world is messier than theory, we anticipated using more than four regions. We set up a test making sure that every pair of adjacent beacons in our test setup were in different regions. What was the result? I had to leave the building before I got the enter and exit events from Core Location monitoring that we needed.
Why did this four-color theorem approach fail? We had run into a design limitation of our algorithm. The beacon power levels were turned up to get a more better accuracy/distance reading, but it meant that their monitoring regions overlapped. They overlapped so much that they took up the entire office.
Even though we can represent our mental model of our real-world regions as a graph on a plane without edges crossing, the Core Location regions (that are larger because of the high power level on the beacons) overlap and cannot be drawn on a plane without edges crossing. So in this case, we can’t apply the four-color theorem to ensure that we can assign all these beacons to just a few Core Location regions.
We tested out the neighbors approach, and found it worked reasonably well in our real world setup. We put in a few more hours of programming to make it work, and considered the 20 region limit broken! In our implementation, we again put pragmatism before the elegance of theory. We could have set up a graph in our database and programmatically determined neighbors using breadth-first search. But what is easier for our end user? Maintaining learning about graphs and maintaining one in a database, or just choosing the x nearest beacons to the beacon in question? We opted for the latter: the team configuring the beacon set up directly configure neighbor relationships, so there’s no breadth-first search or four-color theorem in our implementation. We used some theory for inspiration, but relied on experimentation to choose our implementation.