Indoor positioning with beacons and mobile devices
Imagine you arrive at an airport for the first time and you are in a hurry to find the gate; or you’re in a museum and are interested in a specific section; or you’re about to meet someone in a big hall but have no idea how to give indications to each other about where to meet: Indoor positioning to the rescue.
Indoor positioning is about viewing your position on a map when you’re inside a building. The issue with the well-known GPS technology is that signals from the satellites are lost when there are walls/ceilings in the middle of their path. It is for this reason that new approaches had to be taken. One of them is using Bluetooth LE beacons and your phones bluetooth antenna to estimate your position relative to the beacons.
Bluetooth LE has a mode to advertise (advertising mode) signals, this mode is used by beacons. There is a mode to receive those signals (scanner mode) that is implemented in your phone.
When the phone receives a signal, it measures its power (RSSI to figure out the distance to the beacon, since the power and distance are proportional.
So far so good, but the issue is that Bluetooth LE is not really a technology thought for measuring distance but for detecting proximity. In fact, the 2.4 GHz signal is so affected by walls/humans/plants/whatever that a human standing in the middle of a device and a beacon can cause a 100% measurement difference.
A common method for estimating position using distance in a N dimensional world is to find N+1 reference points, so in case we want to calculate the position in a 2D floor, we need 3 reference points (beacons in our case). The intersecting point of the three circles will be our position. The method is called trilateration.
The issue with trilateration is when the signal has significant noise, the intersecting point can simply not be there when drawing the circles. No intersecting point means no distance measurement. Also, using more than three beacons to improve the estimated position increases the complexity of the algorithm significantly.
In the Beacons Positioning open source iOS app, I tried to find a satisfactory solution without being too rigorous on pretending to find the exact position of the device. For this, Heat Maps were used and the outcome is a ‘probability’ area that tells where the device may be found. The heat map is filled based on recent past measures.
In the experiment, a big hall of 8m x 18m were used. The beacons were positioned around 2.5m high on the walls.
The following methods were the ones that produced the best results. Depending on your needs and environment, you can try and pick the one that works best for you.
Levenberg Marquadt method
Levenberg Marquadt is a method used to solve non-linear squares problems and showed good results on the positioning problem. It’s not that predictable but works pretty well on positions where the device is quite near to a particular beacon.
It’s an iterative algorithm and consumes a reasonable amount of CPU even when performed several times per second. Keep in mind that variance in CPU consumption will affect not only your app performance, but also battery life.
This method (called “heuristic” in the app) is a pretty simple one. The ad-hoc/heuristic method iterates the room area as a grid and calculates the discrepancy between all the beacons measurements and the current position of the algorithm. The position where the accumulated error is minimum is the estimated position.
It’s more deterministic than the previous one and throws similar outcomes to the trilateration algorithm when noise is minimum. For big areas (where computing could be too demanding), an heuristic method may be included, so instead of ‘brute force’ searching the whole room, some samples are taken and then a gradient to the minimum is deducted.
There are many variables that are part of the environment: the height of the beacons, the amount of people in the room, the shape of the room, refracting areas, etc.
A good idea to try to minimize the error is by tweaking the algorithm variables. You can for instance customize the estimation formula for calculating the distance to the beacons by comparing the empiric results of your context.
The iOS app offers a convenient way to sample the environment by recording a session (e.g: walking a particular path on the room) and then being able to play it anytime later while you tune your parameters and iterate to reach an accurate heat map.
You can perform a similar experiment very easily: locate a few iBeacons in your room, configure within the app the details of the room, specify the beacons IDs and your location will be revealed in the map instantly.
- Use the strongest transmitter power. Stronger signals will end in higher signal to noise ratios.
- Try to put your beacons as high as possible to avoid blocking surfaces.
- The more beacons you use the more accurate the estimate will be.
- Use some noise filtering solution, from basic average of past values to more complex solutions like Kalman or Complementary filters.
Using the previous approaches can work on controlled environments where near perfect precision is not needed. For a further research, more complex solutions using Kalman filters and the motion co-processor of the device may throw more accurate results and thus open the spectrum of indoor positioning applications.