- This paper provides an overview of the indoor positioning algorithms based on signal strength received from the Bluetooth Low Energy beacons. A comparative analysis of the considered algorithms on criteria such as effectiveness, independence from the preliminary measurements.
Keywords — Indoor Positioning Algorithms; Bluetooth Low Energy Beacons; iBeacons; RSSI
I.
Currently, there is increasing interest in the possibility of obtaining information about the location of an object. The range of services will expand significantly if user's location information can be provided. The location-based services refer to applications that depend on the user's location to provide services in various categories, including navigation and tracking. Unfortunately, the GPS technology does not specify a location close to walls, buildings, trees, buildings and subways, as the power of the GPS satellite's signal is weak, making it unusable for indoor GPS localization. It is popular to use Wi-Fi hotspots for detecting location in the room. However, given the fact that the walls are an obstacle that affects the signal Wi-Fi access points that data mechanism is not effective. In this case, the quantity and location of Wi-Fi access points are very important when using wireless technology, moreover such a solution is costly.
II.
AIM
The aim of this research is to determine the possibilities of indoor positioning algorithms using BLE beacons. The objectives of the research are the following:
Investigate the range broadcasting of Bluetooth Low
Investigate which indoor positioning algorithms using
Copyright © held by the authors III.
This section describes the basic terms and model of the environment in which positioning algorithms are used. A positioned facility that receives the Bluetooth Low Energy signals is called “agent”. In this case the "agent" means a smartphone. The model of environment includes several beacons and an agent. Without loss of generality, the space is regarded as a flat environment in which there are interferences from walls - floors, diverse signals, etc. There are two types of indoor positioning algorithms. Types of indoor positioning algorithm: A. Without the need for preliminary measurements
B. Preliminary measurements are necessary IV.
The proximity algorithm [
The advantages of this algorithm include the ease of implementation due to the low computational complexity (O(N)) and the necessity to know only the location of the beacons. The obvious disadvantage is very low accuracy. This algorithm is useful as an initial approximation, the result of which can be used for a different algorithm.
The centroid algorithm [
⎧ =
Cartesian coordinates of ith beacon; wi - weight characteristics;
di - refers to the distance between agent and ith beacon and g to
the degree which determines the contribution of beacon; N is
the number of beacons.
1. The stage configuration environment. At this stage, the
power signals in pre-planned locations of all known
active beacons are measured. The information col-lected
is stored in a database with reference to the local or
global coordinate space.
2. Step positioning. At this stage, the signal power
measurements made over the agent are compared with
the information stored in the database, by means of an
algorithm. The algorithm of k-Nearest Neighbors is used
in the paper [
In this paper, formula (6) is used to find the Euclidean
distances between the stored data and real-time data [
In the next step, one pre-planned location point is selected with the smallest Euclidean distance. The value of the coordinates of the pre-planned location points are assigned to the coordinates of the agent. The algorithm of k-Nearest Neighbors is used for choosing multitude pre-planned location points.
The Nearest Neighbor algorithm is a special case of kNearest Neighbors when k = 1. The advantage of using multiple points is to improve the positioning accuracy. There is a possibility to use additional algorithms to approximate location. author
(7)
Where XA, YA – Cartesian coordinates of agent; Xi, Yi is the Cartesian coordinates of ith beacon; k – number of pre-planned location point which have minimal Euclidean distances; wi weight characteristics; Dis - Euclidean distances.
Trilateration Localization
The trilateration algorithm [
This model can be shown as such equation system [
Where , is coordinates of agent; 1, 2, 3, 1, 2, 3 is the coordinates of bea-cons; d1, d2, d3 is the estimated distances.
This system of quadratic equations can be simplified by substituting equation 10 into equation 8 and 9, which will leave two linear equations: 2 ∙ (
− ) ∙ + 2 ∙ ( 2 ∙ ( − ) ∙ + 2 ∙ ( = ( − ( = ( − (
− ) ∙ − ) − ( − )
− ) ∙ − ) − ( − ) − ) − )
The agent coordinates are found by solving equation 11 and equation 12, using Cramer’s rule.
= ( ( − ) − ( − ) − ( − ) − ( − ) − ( − ) 2 ∙ ( − ) 2 ∙ ( − ) − ) 2 ∙ ( 2 ∙ ( − )
2 ∙ ( − ) 2 ∙ ( − ) − ) (8) (9) (10) (11) (12) (13) 2 ∙ ( − ) − ( − ) − ( − ) 2 ∙ ( − ) 2 ∙ ( − ) − ( − ) − ( − ) − ) − ) − ) (14)
The advantages of this algorithm are the low computational complexity and the necessity to know only the location of the beacons. The given algorithm is the most reliable, and its application include GPS and cellular networks. describe one of the tested rooms. A specific environment of 4.64 by 4.64 in meters has been simulated in order to test the algorithms. All electronic devices which could affect the test results have been removed from the rooms. Also in this room, if possible, we collected objects that could reflect or absorb signals. The configuration parameters of BLE beacon:
The algorithms of Proximity
(1.16, 3.48) (2.32, 3.48) (3.48, 3.48) VI.
Figure 2 illustrate the visual result of algorithms performed in Environment 1. 2 3 , 2 8 0 7 ,1 7 , 0 8 8 , 1 0 1 , 1 3 , 0 R E D
2 3 , 2 5 5 , 1 2 5 , 1 8 1 , 0 G R E E N 2 3 , 2 5 9 , 0 8 ,53 ,06 0 B L U E
At the end of experiments, we can confidently say that the fingerprinting localization algorithm requires preliminary measurement, and the average deviation from the actual position is equal to 0.3, 0,68 and 0.95 meters
The results of this algorithm can be improved by reducing the parameter k in the kNN algorithm, the error increases due to the fact that it is not taken into account the distance from the beacon which the greatest signal strength.
The trilateration algorithm and algorithm of Weighted Centroid needs no preliminary measurement as the average deviation from the actual position is 0.97 and 1.01 respectively. The nearest three of four beacons have been used in the experiment for Weighted Centroid and WCWCL-RSSI (Fig.4). The experimental results showed that increase in the number of beacons does not affect the accuracy of determining the position in the experimental room (Fig. 5).
3 0 , 1 R E D 7 3 , 1 3 6 , 0 G R E E N 1 4 , 2 5 4 , 1 B L U E 4 8 , 0
During the experiments, in the room, the four beacons were used for the algorithms of Proximity Localization, Centroid Localization, Weighted Centroid Localization, Trilateration Localization. However, in the corridor, the six beacons have been involved due to the length of the walls. The six beacons have been used for the fingerprinting localization algorithm in both case. Figure 6 shows the average error of the algorithms in the rooms: 1 3 , 2 1 3 , 2 3 , 1 7 9 , 0 3 , 1 7 9 , 0
Fig. 6. The comparison of the error of indoor positioning algorithms in the rooms.
As it can be seen from Figure 6, the Fingerprinting algorithm showed the highest accuracy in determining indoor location, an error which was 0.65 meters whereas the Proximity algorithm showed the worst result and the error was 2.31 meter. Figure 7 shows a calculation error of the algorithms in a corridor:
Fig. 7. The comparison of the error of indoor positioning algorithms (in a corridor)
The experiments conducted in the corridors also showed the best result at the Fingerprinting algorithm. Although fairness it 6 6 , 1 6 6 , 1 5 6 , 0 5 6 , 0 should be noted that the algorithms of Weighted Centroid and Trilateration also have shown good results. The remaining algorithms have a lack, when agent is moving, the result in coordinates is showing outside of the room. In avoidance errors of this type, we propose to create a map of the room and use room boundaries in computing.
Overall, these results can be evaluated as positive because the room has been fully covered by signal. The number of beacons was established from 3 to 6 and during testing it was found that the amount fully covers the room up to 5 meters. It can be stated that:
The range of signal broadcast in the real world does not correspond to the range that has been declared by the manufacturer. It can be mentioned that the signal is practically damped by the wall. For an efficient operation of indoor positioning algorithms, the data obtained from beacons hast ob ef roma 3 m eters’r ange. According to my results, the Fingerprinting algorithm can be used as an indoor positioning algorithm using BLE beacons. The algorithm showed relatively high positioning accuracy that distinguishes from others, however, the main disadvantage is the phase of preconfiguration. The error of calculation is 0.67 meters. In general, we can say that the greater the number of beacons, the better the result of the positioning. From the experimental results, we can conclude the longer the wall, the more the beacons will be required for the correct operation of algorithms with consideration of the maximum range of broadcasting in real environment.