Trilateration in practice: testing indoor positioning with beacons

Beacons are a new technology that enables proximity sensing. They are small, cheap devices that can be detected by smartphones in order to provide location information when GPS is not available. As with all new technologies it pays to work with them hands-on in order to understand their benefits and limitations, so we have started testing them against real-life scenarios.  Because this technology is evolving from month to month, we will try to share results in a timely manner.

The new breed of beacons, based on the Bluetooth Low Energy specification, have the potential to simplify projects that need proximity awareness.  They work by passively broadcasting an identifier that devices such as smartphones can pick up.  Then they can be used as triggers and data sources in any number of mobile apps with little changes. Small initial cost, little maintenance, re-uses, what’s not to love?  Well, maybe some practical limitations at this level of maturity.  For example, many scenarios long dreamed of by retailers, conference hosts or others call for a precise location of the user.  If you want to send the consumer a voucher for a 2-for-1 for the item s/he is looking at, you need to know the location to the inches.  If you want to greet him/her by name, you need a foot or two of precision.  Do beacons provide the stability and accuracy needed for that?  That is what we will investigate in this blog post. If you want the TL;DR spoiler: presence detection is good, but precise positioning not there yet.

To check the precision of the indoor positioning that can be derived by current beacon technology I planned to use triangulation calculations, more accurately called “trilateration” in the case of a 2D implementation. That requires as a basis a measure of the distance from 3 fixed points, the beacons.  However, the findings are that the trilateration could not be performed, because of the lack of accuracy in the measure of the distance from receiver to beacon.  There seem to be four main reasons to that lack of accuracy.

     1) The signal strength of each beacon fluctuates a lot even when the beacon, the receiver and the testing environment are stationary. The noise of the signal data from the beacons was so random that I couldn’t smooth the data to capture important patterns in the data set.

     2) Depending on the way that the user is handling the receiver device, the readings can change a lot as well.

     3) The state and configuration of the beacons such as battery life, advertising interval and broadcasting power impact the readings.

     4) The readings also change with the operating system of the receiver devices.

As a result, I would say that beacon technology is not ready for indoor positioning, tracking, navigation or scenarios that require precise location. For the time being, it would be better to concentrate them on proximity detection, what we can call “presence”. 

Overview

I conducted the same experiments with iOS and with Android as receiver devices.  I tested out three different manufacturer’s beacons: Estimote, Gimbal (Qualcomm) and Tōd, which look as follows roughly at scale.

I used three beacons of the same brand in each test, gave them fixed positions and logged the distance evaluated by the receiver for trilateration calculation and for statistical analysis. To reproduce the test, you can follow the Experimental Setup section below.  For sample results, look into the Test Results section, and for theoretical overview of the methods into the Trilateration section.  And let me know of your findings!

Experimental Setup

• Steps to pre-configure the beacons
  • Estimote  beacons
    • Download Estimote Virtual Beacon app from Apple store
    • Launch the app and click on Beacons button
    • Select any beacon appears on the Beaons in range screen
    • In the Beacon Details screen, click each attribute and enter the value in the setup table below
  • Gimbal beacons
    • Follow the steps in the sections of Create Your Configuration, Apply Configuration To Beacon and Push Configuration To  Beacon. https://gimbal.com/doc/ios_proximity_ibeacon_quickstart.html
  • Tōd  beacons
    • Basic information can be found here: http://opentod.org/uploads/QuickStartGuide.pdf
    • If there is interest, my colleagues or I can post more details separately about how to pre-configure Tōd beacons

• Set up ofthe beacons

• Test room dimensions : L 4.7 m x W 5.9 m x H 2.6 m
  • The test room had no moving objects that could interfere with the experiment.
• Devices
  • LG Nexus 5 with Android 4.4.2
  • iPhone 4S with iOS 7.1
• Test app scan interval: the app scans for beacons every 2 seconds for a duration of 10 minutes.

18 Tests were conducted, i.e., all combinations of:

• 3 different beacon makers: Estimote, Gimbal, Tōd
• 1 SDK: Estimote SDK, used for both iOS7 and Android (Estimote 0.4) – note that I also tested visually the results with the Radius Networks SDK using its iOS app, which gave similar results as the Estimote SDK
• 3 different positioning schemes for the beacons

Test Results

In all tests, the standard deviation of the distance evaluated by the iOS device is smaller than by the Android device. That means that the distance calculated by the iOS device is more stable than by the Android device. 

However, with both receiver devices the measured distance is still far away from the actual distance, as can be seen on the below extracts.

Figure 1 iOS and Android test result1

In addition, as shown on the below figures, the measured distance could be greater than the actual distance or vice versa.

Figure 2 – iOS and Android test result2

A further idea was to understand whether we could get a more precise or trustable measure in a certain range of distances.  I could not prove that. The following charts plot the actual distance and the average of the measured distance using Estimote beacons in this case. The measured distance goes up and down as the actual distance increases.

Figure 3 Data correlation

Trilateration

In my test application, I use trilateration for the implementation, which is the same technique used in a Global Positioning System (GPS). In a nutshell, trilateration is a geometry method to determine your position based on the physical position and relative distances of three referenced points. There are 3 conditions:

• Trilateration works with 3 or more beacons
• Beacon signal strength must be stable
• Each beacon’s signal must intersect with the other two

The practical implementation requires a good deal of mathematics. Again, if there is interest, my colleagues or I can post more about this. 

Test Application

Here is a screenshot of the trilateration test application which runs on Android devices. It displays a floor plan of our office in Montreal. The screen representation is proportional to the actual floor plan. Three Estimote beacons are installed in the room in a fixed position. The signal from each beacon covers the entire room. For this little testing, that means that the condition of having intersection is more than fulfilled, since the 3 signals are superimposed. The app itself was developed using the Estimote SDK.

Normally, the working conditions should be correct, and we should see the red dot moving as we walk around. Unfortunately, that is not the case. The red dot didn’t move most of the time due to the fact that the signal strength of the beacons was not stable at all. The relative distance reported by the app was extremely small even though the physical distance between the device and the beacon was large (a few meters). I also verified separately that repeat experiments in the same conditions measured different signal strengths. 

Summary

Based on these results and the current technology we’ve concluded that beacons are best fit for proximity detection rather than precise location coordinates. For example, you can tell if a person is in a meeting room but not what seat they are sitting at. This still makes them very useful for many indoor location related use cases where you need to Presence rather than Positioning.