Inverse beacon positioning

Indoor positioning is a very popular topic recently, mostly due to the iBeacon technology promoted by Apple, and adopted by other vendors. Most of the research on indoor location involves a set of fixed beacons on well-known positions, and a moving beacon signal receiver. What if the beacon was moving, and the receivers were fixed?

Such a scenario can have many uses, where it is beneficial that the positioned object is as simple as possible, e.g. tracking shopping cart movement in a mall. It is much easier to equip each cart with a beacon, than with a device capable of calculating the distance.

In my setup, I was tracking movement of an Estimote beacon with the help of three Raspberry Pi agents placed in my living room (which is about 4m x 5m wide). Each Raspberry Pi is equipped with:

photo

The RPis listen to all Bluetooth Low-energy advertisement packets, and send them to a ZeroMQ pub socket. That part of the code is in C, and partly follows hcitool from bluez. ZeroMQ was a good fit here because of its ease of use and many language bindings (including C and Java). You also don’t have to worry about connecting or reconnecting, the publishers and subscribers can be started and stopped at any time, and things work as expected.

On the other end, a Scala-based GUI subscribes to the three RPi publishers (ZeroMQ sub socket), parses and filters the packets (not all advertisements are in the iBeacon format) and feeds them to the positioning algorithms. The results are then displayed on the screen.

Each agent receives about 7-10 advertisement packets (and RSSI measurements) per second from each beacon.

2014-04-24_0925

I implemented two approaches to positioning. The first is based on trilateration. Basing on the measured RSSI, it is possible to approximate the distance to the beacon, and hence determine a circle, on which the beacon must be. Having three such measurements, it is possible to estimate the position in a 2D plane. As the readings aren’t exact, and there’s most probably no unique intersection point, I used the SimplexOptimizer from commons-math, to determine a point from which distance to the three circles is minimal.

To accomodate for temporary signal strength variations, I used an average of the 10 last readings of the RSSI per agent.

The second approach uses a neural network. First, I placed the beacon at a couple of well-known locations (storing the coordinates of that location), and stored the stream of measurements for a minute. Repeating the process several times, I got about 7 thousand training examples (tuples of three measurments from three different agents and the real location). Then I trained a neural network, implemented using Encog; I got the smallest error when the input contained 4 most recent readings per agent (so 12 inputs), and the single hidden layer had 80 neurons. The output was a pair of coordinates.

You can see the results on the video below:

  • the red squares are the fixed agents, receiving the beacon signals
  • the green circle is the position of the beacon as estimated by trilateration
  • the blue circle is the position as estimated by the neural network approach
  • the yellow square is the target location to which I am currently moving the beacon

Initially the beacon is in the center. Then I’m marking the position where the beacon is going to be moved, and move the beacon.

As you can see, the results are not very accurate. The neural network learned very well when the beacons are very close to an agent, but gives erroneous results when it is further away. On the other hand, trilateration works much better when the beacon is at some distance from the agents (you can see the movement when it happens), but fails to capture the fact the a beacon is very close to a given agent.

To sum up, while this approach cannot be used to precisely determine the location of a beacon, it can be used to get a rough estimation on where the beacon is. Also certainly both the neural network, and the trilateration algorithm can be improved for better accuracy, and the results combined to get a better approximation. Other approaches, like particle filtering, could be implemented as well.

Update: raw data containing RSSI measurements and approximate beacon positions is available here.

  • Brian Topping

    Great work! I was on your blog for the very nice Scala macros post and clicked in here. Hadn’t really had time to dig how iBeacon worked, so happy to have run across this.

  • http://encausse.net/ Jean-Philippe Encausse

    Very Interesting ! Thanks !

    – Did you digg deeper since April ?
    – Did you try smaller Estimote beacons ?
    – Is beacon location (signal strengh) noticeable when you move ?

  • http://www.warski.org/ Adam Warski

    I didn’t do much more work with beacon-based positioning. We only did a conference app using beacons (https://softwaremill.com/android-ios-ibeacon-conference-app/), but that’s a much more traditional beacon use-case :).

    I also didn’t try the new Estimote stickers (I assume that’s what you mean), but I did try the same experiment back in April with Gimbal beacons, much to the same results.

    The signal strength is noticeable when you move, as you can get a very rough position approximation, however when you move closer to the device, it reaches the maximum and stays at that value (so “close” and “very close” are indistinguishable). The further you go the strength decreases, but you also get a lot of noise, plus it is also vulnerable to physical obstacles (e.g. the human body ;) ).

  • http://encausse.net/ Jean-Philippe Encausse

    Thanks ! Did you find other projects like yours ? I was looking for a simple way to track iBeacon with a Pi and figure out someone or an object moves (geolocation is awesome)

    I also see Estimote has an accelerometer, but I don’t understand how to get these data too ? Why they did that if iBeacon goal is to be a beacon for phones ??

  • http://www.warski.org/ Adam Warski

    You can communicate with the beacon to get the accelerometer readings using BLE (the data is not broadcast as part of the iBeacon advertisement). I’m sure there’s a tutorial somewhere, though I didn’t try it in practice (though I did try reading temperature from Gimbal beacons, and they were simply transmitting two types of advertisements).

    I’m not aware of any other efforts to do moving-beacon positioning, but I’ll be curious to hear about your experiences!

  • http://encausse.net/ Jean-Philippe Encausse

    In fact accelerometer of Estimote is private date ATM.

    I played with python script and mobile to compare Estimote and StickNFind. I notice changes in RSSI but as you said I get weird result

    The first close to me is just below the RSSI (50/74) and at 2.5M are at 80/74 it ‘s interesting to see it’s not accurate may be it’s firmware problem ?

    It’s good for geofencing but no more

  • http://www.warski.org/ Adam Warski

    On a related note, Estimote just released Estimote Indoor: http://estimote.com/indoor/

    Looks very interesting, though I didn’t test it yet.