As a result of the implementation, we have created applications for mobile operating systems such as Android and iOS, so that users can determine their positioning in the place, and a route to selected points of the place.
By way of introduction
Determining the positioning of BLE (Bluetooth Low Energy) receiver signals, or in our case a smartphone running the Android or iOS, is based on the analysis of signals power received from the beacon of known positionings. By known positioning, we mean such an application that uses a database of beacons spatial positioning, where each of them has determined an unambiguous positioning. Together with signal power received from the beacon, the following data is collected:
- the power of beacon transmitter, interpreted as the reference power at a distance of 1m
- identification in the data set that enables unambigous identification of an appliances
While drawing up a solution, we have considered three methods of determing the positioning:
- "fingerprinting" - a method involving collecting reference data in the operational environment. On the basis of collected data, the positioning is determined. We have developed own variant of this method, which uses Wi-Fi signals. The undeniable disadvantage of this technique is that it requires a laborious process of collecting reference data in the target environment. What is more, it is also characterized by the so-called drift, that makes reference measurements repeated periodically.
- assigning individual zone for each transmitter. This method requires the least advanced algorithm, which offers low positioning accuracy. This method is the best, if the implementation environment enables to assembly transmitters at regular intervals. We have applied this method in another implementation, which did not require such accuracy, as described in the case of the passenger facility.
- triangulation, based on information about transmitters distance. We have chosen this method during implementation because of its flexibility in terms of deployment of signal sources, its theoretical possibility of achieving more accurate results than by applying the aforementioned methods.
In this method, the receiver application uses data about the positioning of all beacons described in two dimensions. The power received from each beacon is converted into the distance, that the received signal has travelled. Such data collection enables to determine the likely positioning of the receiver.
Conlusions of implementation of the positioning algorithm based on BLE
1. Implement a method for distance calculation of BLE signal
We have achieved sufficient accuracy of positioning by implementing a popular method for distance calculation from the transmitter with value of transmitted and received power.
This method comes from the beacons usage library "Android Beacon Library" available on the Apache 2.0 license: https://github.com/AltBeacon/android-beacon-library. More information: http://stackoverflow.com/questions/20416218/understanding-ibeacon-distancing. The main reason why this method has been applied is the fact that the application will be available to a broad group of appliances, which function in diverse environments. Certainly, a better and own method of distance calculation was possible to create, but it would have been dedicated to specific phones and applied in conditions similar to those in which it was developed. In practice, appliances features are so diverse and conditions in public places differ from lab conditions as referred to in section 2 of our experience. On the basis of this implementation, we can easily draw up a relation graph between the distance of the transmitting beacon and the power of received signal, for example as below for three different power settings of the transmitter.
2. The method of distance calculation from the transmitter gives only approximate values
The first conclusion that arises after implementing and testing this method in the lab is the fact that this method gives only approximate values. The actual distance relation of the received signal is a non-deterministic function of many factors; some of them are listed below
- different phones have different antennas, which output affects the accuracy of precision calculation
- the received power depends on the orientation of the receiving antenna relative to the transmitting antenna. Changing the orientation of phone in the area means that the calculation of received power wil be also changed
- the environment of wave propagation varies over time and depends on many factors such as properties of the room in which we are. As an example if the room is made of metal and glass elements, it causes waves reflection and their unpredicttable propagation
- assembly of beacons on certain types of columns result in complete change in relation of received signal power from the distance
- the interference of other signals. The band of BLE signal coincides with the frequency of WiFi network (2.4 GHz), which interferes and affects the accuracy of the power
- the number of people in one room. A human being consists mostly of water, which largely absorbs electromagnetic waves of frequencies reserved for WiFi and BLE. Signal fluctuations can be observed when group of people pass through one room
- the architecture of the room. We have put a lot of effort into the appropriate choice of parameters and positioning of beacons for the hall, that is equipped with an entresol. The entresol is a separate room and in terms of architecture it is a separate hall. Unfortunately, it is not in terms of the propagation of electromagnetic waves, for which the hall with an entresol means one room. In the entresol you can observe the expected decline in power with distance from the beacon while outside the entresol the power turns out to be so strong, as if the receiver is not in the entresol, but close to the transmitter.
3. Analysis of sample series to be required in order to determine positioning
If BLE transmitters and receivers are at a standstill, and the signal propagation environment does not change, we can observe some constant changes of received power. Amplitudes of changes and their dynamics enable to determine even the approximate distance of beacon on the basis of a single sample. Subsequent readings may differ from each other so that the distance determined on this basis may differ from each other by 50%. This observation raises our awareness to difficulty achieving an accurate positioning determination of BLE signal receiver. In terms of positioning determination of the receiver advanced statistical processing of sample series of the received signals is crucial. To determine the actual distance of beacon you need to analyze the history of received signals. While developing a solution to the problem, you must choose between a more accurate determination of accurate distance and quick reactions to its changes. You must also remember that this is only one of several steps of the algorithm as well as that target appliances have limited calculation power. The simplest possible calculations are the best. Meanwhile, a desirable solution is such that requires clearly more advanced calculation for better quality.
The chart showing the power of not-processed samples (white line) and the power of stabilized samples (the red line). Our solution enabled to reduce the amplitude of fluctuation over three times as in the attached chart. Also it had a positive effect on the rate of changes, while maintaining an acceptable dynamic power of changes after processing in real changes of beacon distance from the receiver. While developing a solution we have determined that it is crucial for beacons to transmit the signal often enough. Otherwise, the collection of sample series to be determined as single power level after processing can take too long to maintain satisfactory responsiveness of the algorithm. We do not recommend to exceed the transmission interval of 300 ms. We have also determined that analyzed sample series do not have fixed size. The applicatMulti-step positioning algorithm with correction methods implementation ion of phone accelerometer readings after removing the gravitational acceleration enables to determine if the receiver is at a standstill and whether it is necessary to apply stronger series to determine the received power. You should also remember that series changes in size should take place in a smooth manner so as not to cause sudden changes in output power.
4. Multi-step positioning algorithm with correction methods implementation
The positioning algorithm is a multi-step process, where one step means the analysis of sample series in order to estimate the distance of each BLE "visible" transmitter. Then a selection of samples is done. The quality of the final result is strongly influenced by determining which samples have valuable information. Pre-selection is based on filtering the samples using the criterion of time in which they were received from the beacon. Then, samples with too weak signal are removed. Such samples can come from a distant or close beacon, but are covered by some obstacles. Practical trials have shown that determining a fixed threshold power is meaningless. We have developed a method for choosing the strongest signal, which enables to adapt to the situation. This means that the power threshold depends on the current layout "visible" beacon. The next step is to determine the floor on which the receiver is. Most often, due to a muffled floor, this process is not complicated. However, the algorithm was meant to cope with identification whether the user is on the entresol, the place without barriers to signals coming from places located near and below. We have planned to apply the triangulation, but it turned out that its use is related to the loss of a large part of valuable information. Finally, we have applied another method of determining its own positioning based on the distance from specific points. Its distinguishing feature is granting weight to signals according to their power. This processing has been introduced with the knowledge that there is a relation between the signal power and the confidence that it should be trusted. The last step is the correction involving erasing any easily visible errors, including:
- location beyond the hall. In order to do this, in the algorithm you must include the shape of the hall and exclude any unattainable positioning, for example: positioning on a wall or beyond it;
- too long distance between subsequent designated positionings of the user. The correction calculation of the speed with which the receiver had to travel to be in a new positioning and it excludes any "teleportation" possibilities
- positioning at the wrong floor. The user will take a certain amount of time to change the floor and you should exclude unrealistically short amount of time to change floors.
Summary
As it turned out during the implementation of positioning based on 1500 beacons in public places of over 100 000 square meters on several levels, you need to design a multi-step algorithm for determining the positioning. While creating this algorithm, you must take into account any processing steps of sample series of the signal beacon, the selection of relevant data, the application of weights to them, and implementation of any necessary adjustments. The user positioning in relation to the fixed infrastructure of the hall as well as the application of the inertial sensor are crucial features of the correction algorithm. The most difficult part of this implementation was a compensation step of environmental effects on the signal transmitted by beacons, which means reflection of waves from glass and metal surface, interference with WiFi signal, or the effect of groups of people who pass through the room. An important conclusion is that the implementation and testing of the algorithm in the lab in the company can have completely different results than in real environment. The most important information is the fact confirming that the applied technology is practical and reasonable to be used for geo-positioning in closed facilities.
For further questions about algorithm positionings, please contact directly with the authors of the article: office@inovatica.com
Darek i Bogumił / Inovatica
