The mobile app team at EDINA recently developed an app for the University of Edinburgh Main Library “Open Doorsâ€� event. This was our first attempt to use Apple’s iBeacon technology in anger, in a real environment. We had done some evaluation of iBeacons previously so had some idea of what to expect, and what not to expect from the technology. Nevertheless, the environment we deployed beacons to, a large open lobby area, was very challenging. We had to create a bespoke detection heuristic to create a reasonable user experience. In this post, I’ll demonstrate the problem and then explain how our algorithm works and discuss is performance, and potential for improvement or alternatives.

The user experience we were after should in theory have been a fairly simple one (you might think).

• We divide the floorplan into non-contiguous zones, ensuring a fair amount of distance (> 5m) between zones.
• As a users enters a zone, we pan to the area on the floorpan viewer and some content (in this case a video) is highlighted.

 

Therefore all we needed to know was which beacon was closest. The exact distance was not that important, so we could ignore inaccuracies in actual distance, so long as we could determine which of the beacons in range was the closest.

1. Where more than one beacon is deployed in the same open floor space, it is very difficult to find positions and range settings where the beacon readings do not collide with one another.
2. Setting a beacon range to a small value (<1 meter) requires the user to position themselves very close to the beacon and it is likely the user will walk through the zone without anything happening.
3. If we set the range to > 1 meter, responsiveness is better, but the reliability of the signals strength readings becomes increasingly inaccurate.
4. For Android devices, the measured distance varies greatly across difference devices, making it hard to set a range value that will create a good user experience for all users, as documented in this excellent ThoughtWorks blog.

 

A brief look at some tracking data should help to visualise the problem.

 

The figure above shows the output from a test we ran in our open plan office space ( not the library – we didn’t have time to capture the data when we were deploying the app in the Library). This data collected on a Nexus 5 is close to what we were hoping for. It shows a user following a route from zone 1 (blue line representing beacon 64404), then entering zone 2 (orange line segment), then entering zone 3 (green), before turning around and returning to zone 2 and finally back to zone 1. We were using Estimote beacons, but rather than using the proprietary Estimate SDK, we used the alt beacon library instead. Listening to the beacons in ranging mode, we receive a batch of beacon readings every second or so, where each beacon in range reports its signal strength from which an estimation of the distance is derived. The data above is pretty good scenario for our use case, as for the most part only one beacon is detected in range at anyone time.  There is a period of 7 seconds between   14:13:04 and 14:13:11, where the ranging data batch includes readings for both beacon 30295 and 64404.

 

As we might expect the readings for the orange beacon gradually increase as we walk away from zone 2 and approach zone 1, while the values for the blue beacon decrease as we approach zone 1. Even though both beacons are in range during this period, we don’t want both beacons to trigger events at the same time. We want the algorithm to decide which zone the user is currently located in even if more than one beacon is in range. Two simple solutions present themselves:

1. Choose the nearest beacon in the batch. In the case above, with the Nexus 5 readings, this would work perfectly. The zone 1 (blue) ENTER event would actually have occurred a second before the one recorded above, and so this simple heuristic would be more responsive than our implementation in this case. You’ll see shortly why we can’t rely on this all the time though.
2. Require a minimum distance before a beacon can trigger an application event. This would not work over the full period above Nexus 5 track (figure 1).  If we choose a threshold of <1 meter, the first time the user enters zone 2 ( the first orange line segment) would not trigger a zone ENTER event as it should. If we raise the threshold to 1.5 meters, then the entry into this is zone 2 is detected, but during the 7 second period shown if figure 2, the zone 1 readings shown in blue would also activate zone ENTER events, colliding with simultaneous ENTER events for zone 2.

 

So at first sight, the simple solution of choosing the closest reading in the batch looks good. But let’s take a look at tracking data for a Moto4G device instead.

The first thing to notice is that the distance range is larger than in the previous example, ranging from 1.3 m to 3.5m for the Motorola device, compared to 0.37m to 1.95m for the Nexus 5. This difference between platforms is another reason why setting a minimum threshold for activation is tricky to get right. As you would expect, we found consistency across iOS devices is much better. The next thing to notice is how patchy the the data can be in places. For some reason, this device recorded hardly any beacon readings at all between a 30 second period between 9:34:37 and 9:35:05. A period that includes the sole reading for zone 3 (green). We are not quite sure why this happens (some feature of the underlying bluetooth implementation for these devices perhaps, or maybe a quirk in the altbeacon library?). What is clear is that patchy scanning data that can cause the “choose the nearest beacon” solution to come undone. Take a look at the highlighted datapoint below.

For the highlighted batch the orange beacon was the only beacon detected in range, so the “closest in batch” heuristic would trigger an ENTER zone event at this point. But the subsequent 3 batches of readings (spanning 3 seconds) have only blue beacons recorded. So the “closest in batch” would immediately trigger a blue ENTER zone event. This is typical behaviour on zone boundaries where readings are patchy and flip between 2 or more beacons in range. It takes 7 seconds before we see both beacons in the same batch of readings, and can pick the closest (orange) without subsequent flip back to blue . This data point is highlighted in the chart below. Note our algorithm, which I’ll explain below, did not trigger the ENTER zone event at this point, but instead has to wait 4 seconds for the next batch of readings. So in this case, the algorithm pays a high price to avoid flipping between zones.

It might be possible to devise a way to mitigate the effect of patchy data and zonal boundaries, by examining the values of beacons over two or three previous batches of ranging scans, instead of relying on just one batch of readings for comparison. There is a danger though that averaging (even when weighting the most recent batch) could slow down the responsiveness of the application. In the case where a single data point is critical, such as the (green) zone 3 ENTER event in the chart above, it’s not clear if we should average the green data point against zero values for previous batches, or just take the current value as the weighted average for the beacon.  It looks like the latter technique would have worked quite well in the case above, but I have not had time to explore this alternative solution properly.

Hopefully this section of the post has helped to explain some of the nuances of deploying beacons as a way of representing zones in an open space. Generally, the “choose the closest in batch” heuristic seems to work quite well, but is not immune to flipping behaviour in places where ranging data is patchy. In the next post, I’ll present the solution we used.

Our solution:

Our solution for dealing with the kind of issues described above, is based on the State pattern. Each beacon is associated with a geofence zone around the beacon, with the beacon registering either an INSIDE (zone)  or OUTSIDE (zone) state. The class representing each zone is called BeaconGeoFence and performs two functions. The first is maintain a BeaconGeofenceState, which subclasses into GeoFenceInsideState and GeoFenceOutsideState. Each BeaconGeoFence can only reference one of these states at a time. The second function that BeaconGeoFence class performs is to implement a BroadcastReceiver that listens for events broadcast by the other BeaconGeoFence zones. The BeaconGeofenceState class implements a single method ( evaluateGeofence ), which determines whether a instance of  BeaconGeoFence should change its state, and then broadcast the result of this evaluation to all other BeaconGeoFence instances.  So the general idea is to create a model where beacons (geofence zones) can broadcast messages to one another and potentially change each others state, based on an evaluation of their own state.

To work through how this works in a bit more detail. Initially, all BeaconGeoFence instances are initialised to the “outside” state with a default radius (6m) defining the geofence zone. When the main application class FloorPlanApplication is initialised, the geofence ranging process is started with a call to
beaconManager.startRangingBeaconsInRegion , which kicks off the scanning process where the didRangeBeaconsInRegion(Collection<Beacon> beacons...) method is called every second or so. The collection of beacons represents the current batch of beacons in range. As explained above, to avoid flipping between beacons within range, we sort the batch by estimated distance and only consider the closest in the batch for evaluation. The corresponding GeofenceBeacon is the only one that has a chance to evaluate and change its state.  What happens next depends on the distance of the selected GeofenceBeacon and on its current state.

If the current state is OUTSIDE, one of two things can happen:

1. if the distance is less than the current radius value for the beacon, the BeaconGeofence changes its state to the GeofenceInsideState and broadcasts an ENTER event to all the other beacons.
2. if the distance is greater than the current radius value for the beacon, the BeaconGeofence does not change its state and broadcasts a STAY_OUTSIDE event to the other BeaconGeofence instances.

In either case, the other BeaconGeofence instances must work out what to do in response to the broadcast event.

1. If an ENTER event is received, the receiving BeaconGeofence must immediately change its state to the OutsideGeoFence state. This action is meant to prevent more than one beacon being in an INSIDE state at the same time. The receiving BeaconGeofence also changes it’s radius threshold value to the value passed by the ENTER event. This ensures that only a beacon that has a distance closer than the one that triggered the ENTER event can produce a subsequent ENTER event.
2. If a STAY_OUTSIDE event is received, the receiving BeaconGeofence instances do not need to change their state, as the closet beacon in the previous batch of readings was not near enough to trigger an ENTER event. But all the beacons increase their radius threshold, to make it easier next time for this or another “outside” BeaconGeoFence to push out the current “inside” beacon.

If on the hand, the closest in batch has an INSIDE state, one of two things below will happen:

1. if the distance is great that the current radius setting for the beacon, the BeaconGeofence changes its state to OUTSIDE and broadcasts an EXIT event
2. if the distance is less than the current radius setting the BeaconGeoFence does not change its state and broadcasts a STAY_INSIDE event to the other BeaconGeoFence instances.

Again, the other BeaconGeofences have to decide how to respond to each broadcast event.

1. For an EXIT event, other beacons do not need to change anything, The purpose of this event is to capture a situation where the user walks out of a zone. As the state has now changed to OUTSIDE,  the device will be able to trigger a new ENTER event if they turn back and enter the zone again.
2. For a STAY_INSIDE event all other beacons change their radius to the latest reading from the INSIDE beacon. The INSIDE beacon still keeps its original ENTER distance radius.

The above algorithm solves two problems we encountered using iBeacons on Android devices. First, the difference in range distances calculated for different devices. In this algorithm, the optimal range (radius) for each Beacon can change from the initial default value, allowing the device to self calibrate. The first ENTER event sets and benchmark range for all the beacons to beat, and subsequent STAY_INSIDE broadcast events reinforces the distance used to evaluate whether a beacon should change its state. The algorithm also handles a situation where a single “outside” beacon is the only beacon in range, so by definition is the closest in the batch. When this BeaconGeofence is evaluated, to produce an ENTER event it has to beat (lower value than) the last distance produced by a previous STAY_INSIDE broadcast – that is it must beat the last known distance of the current “inside” beacon. However, unlike a floating average, this algorithm does not preclude a single reading from generating an ENTER event.

Overall we found this solution worked reasonably well, mostly preventing annoying flipping between zones, even when data was patchy. There was an impact on responsiveness, but not too severe. Looking at a range of log traces, we found the algorithm required an extra scan (typically requiring  1 second per batch) delay, beyond the optimal point for triggering a state transition. So generally, we found the cost was a second or so. If your zones are reasonable large, this is probably an acceptable level of delay, as the user will take a few seconds to walk through the zone and therefore will will provide enough time to trigger an ENTER event. For smaller zones, it is still possible for the user to walk straight through the zone without generating an event. There is clearly still a lot of work to do in tweaking the algorithm, or trying out some alternative techniques, but we did feel we made some progress deploying iBeacons as a way of detecting a device as its moves through non contiguous zones. It will also be useful to check whether the new Android Eddystone protocol produces more consistent behaviour across Android devices.