Fingerprinting systems are a simple and efficient way to build positioning systems for Location Based Services (LBS) applications in smartphones. The technologies that can be used for radio frequency fingerprinting with off-the-shelf smartphones are Wi-Fi, which has been deeply studied, and Bluetooth Low Energy (BLE), which is receiving more attention in the last years. This work presents an improvement in deterministic fingerprinting using a filtering process and a new function to compute the Weighted k Nearest Neighbours (Wk-NN) location algorithm. Results with a BLE data set show that these improvements reduce the localization error and give a simple way to build a fingerprinting positioning system for smartphones with an average precision of less than a meter.
Fundamentals of Fingerprinting and k-NN algorithm
WLAN and WPAN fingerprinting are based on the Receive Signal Strength Indicator (RSSI)
which measures, in a logarithmic scale, the signal power attenuation [
Probabilistic approaches are based on a Maximun A Posteriori (MAP) position estimation.
For the fingerprint distribution two main approaches can be used: parametric and non-parametric
estimations. Parametric estimation tries to map the data to know analytical distributions, such
as Gaussian or log-normal [
However, in deterministic approaches position estimation is achieved through the selection of
a set of poins, known as Reference Points (RP), with fingerprints similar to the RSSI measure
in a localization phase and a positioning algorithm. In this section the basic formulation of a
deterministic fingerprinting with the k-NN algorithm presented in works such as [
In the area of interest a set of points, the RPs, whose positions have to be perfectly known,
must be chosen. These points will be denoted as ri with i = 1, 2, .., M and determine the system
ground truth. The RPs, as well as the beacons location, must be scattered enough to characterize
the system properly. The radio map creation begins once the beacons have been placed and the
RPs have been chosen. This stage of the process is called offline phase. Using a smartphone as a
receiver, the RSSI of all available signals in each RP are measured. There could be points where
a beacon signal is missing or not strong enough to read the RSSI [
As mentioned above, the RSSI measurements are highly unstable, so for the same position and signal, values can be very different. Thus, it is required to take more than one measurement in each position to compensate for this effect. A filtering process is needed to take a representative measure for each AP in each RP. The most common filtering process are the mean, the maximum and minimum RSSI value.
The proposed filtering process performs the average of all the RSSI measurements over the same RP, despite they come from measurements taken at different times but with the same beacon’s setup and positions. The mean value for all the signals in a reference point is denoted Mri +mri 2 as RSSIri = Pj ψri,j , the maximum value is Mri , the minimum is mri and let δri = be the average of the latest two. The final value taken into the data base is: Ψri = δ + RSSIri
In a second stage, called online phase, an user in an unknown position, rq, asks for a
localization by taking a RSSI vector using. This consult vector is compared with all the information
stored in the data base using a metric distance function. Most of the related works use the
Euclidean distance but it has been proved that other metrics, such as the Sorensen distance, perform
better [
k Pi=1 wri ri
k
Pi=1 wri
An improvement of this algorithm is done using a weighted average, which leads to the Weighted k-Nearest Neighbours (Wk-NN) method. In Wk-NN not all elements contribute the same in the final position computation, then a function is needed to calculated a weight for each RP. This function will be called the weight function equation. Eq. (3) shows the Wk-NN output where wri is the weight associated with position ri.
The weight is a function of the metric distance and must fulfill two conditions: elements with a closer distance to the minimum must have a weight close to one and those furthest away must tend to zero. Thus, the output is more similar to those with a smaller distance, penalizing those further away. In this work two different weight functions, Eq. (4) and Eq. (5) introduced from [24] and [25] respectively, are proposed. In both equations dq,k+1 is the distance between the query vector and the k + 1 element in the database once it has been ordered, and dq,1 is the closest one. A new combined weight function, is proposed by the authors in Eq. (6). Both in k-NN and Wk-NN, the best number of neighbours to be considered is undetermined beforehand. wri = dq,k+1 − dq,i dq,k+1 − dq,1 wri = dq,k+1 − dq,i · dq,k+1 + dq,1 dd,k+1 − dq,1 dq,k+1 + dq,i v wri = uu dq,k+1 − dq,i
dq,k+1+dq,1 t ddk+1−dq,1 dq,k+1+dq,i · dq,k+1 − dq, i dq,k+1 − dq,1 3 3 3.1
Since data collection for fingerprinting environment creation is a very resource and time
consuming task [
For the fingerprinting simulation, the RPs are randomly divided into training and test subsets, using 60% and 40% for each group respectively. This data split process is done once for the library and for the laboratory, and kept during all the experiments. The results of these simulations are shown using a Cumulative Distribution Function (CDF) which shows the distribution of the error obtained in each localization. When no filtering process has been applied to measurements will be indicated as raw data. The effects of using raw data against filtered over the same RPs are now analysed. A comparative result using k = 72 for raw data and k = 6 for filtered ones is depicted in Fig. 1 for the BQ (a) and A6 (b) phones. Similar results are obtained using other transmission powers in the laboratory data set. Note that the same value of k cannot be used in both cases since the number of elements in the database is reduced when data is filtered, so after data filtering the maximum value for k is the number RPs. Fig. 1 shows that using average values over RP gives an overall better result. The error distribution median has been reduced by 1.5 m compared with k−NN over unfiltered data and the maximum error in more than 9 m. 1 0.9 0.8 0.7 0.6 ) (x0.5 F 0.4 0.3 0.2 0.1 00 1 0.9 0.8 0.7 0.6 ) (x0.5 F 0.4 0.3 0.2 0.1 00
Raw data Mean Filter
Proposed Filter 6
Error (m) (b) A5 2 4 8 10 12 2 4
6
Error (m) (a) Bq
Raw data Mean Filter
Proposed Filter 8 10
12
Each one of these k closer vectors contributes the same to the final output position. The higher this value, the closer the output position will be to the center of mass of RPs distribution when k-NN is used over filtered data. Above simulations are compared now with a weighted average, Wk-NN as described in Section II.
Fig. 2 illustrates the performance of the two algorithms. As can be seen, Wk-NN performs better than the k-NN over filtered data. The output result using k-NN gets closer to the center 1 0.9 0.8 0.7 0.6 ) (x0.5 F 0.4 0.3 0.2 0.1 00 1 0.9 0.8 0.7 0.6 ) (x0.5 F 0.4 0.3 0.2 0.1 00 k-NN
Wk-NN 1.5 2
Error (m) of mass of the RPs distribution when the k parameter increases, meanwhile, this effect is reduced with the weighted average because the most distant elements (in the RSSI vector space) have a smaller weight. A new comparative between the proposed filter and the mean filter are shown in Fig. 3 where it can be seen that the proposed filter performs better.
This simulations are repeated with all phones available in the library data set and all transmission powers in the laboratory obtaining the similar results. The effect of the k parameter in the Wk-NN is presented in Fig. 5. The above simulation has been repeated for the A5 and BQ phones for different k values, from 1 (cell ID) to 9. Results for both phones are shown in Fig. 5.
This figure shows that the error for k = 1 is bounded, thus the output is one of the RPs and the error can never be greater than the distance among two consecutives RP. When k is increased, the function moves to the right and the average quality of the location decreases. For both phones it is found that the best result is obtained when k is around 5, but it is not exactly the same for both. For instance, the best result is given by k = 5 for the A5 and by k = 6 for the BQ.
Finally the effects of the weighted function are studied. The weighted functions shown in Eq. 4, 5 and 6 are now compared. Simulations are repeated for the library data set and the BQ phone. A comparative study is shown in Fig. 4 for k = 6 and 7, which shows that the new proposed function (W-3) works better than the other two 100% of the time with k = 7 and around 60% with k = 6. 4
The results obtained in the previous simulations provide useful information about how to build a deterministic fingerprinting system for WLAN and WPAN networks.
The key in the radio map construction is the characterization between the real positions and the vectors in the RSSI space. Due to smartphone RSSI measurements are highly unstable just one is not enough to characterized the system. Thus, measurements must be repeated in each 1 0.9 0.8 0.7 0.6 ) (x0.5 F 0.4 0.3 0.2 0.1 00 1 0.9 0.8 0.7 0.6 ) (x0.5 F 0.4 0.3 0.2 0.1 00 0.5 1
2 1.5
Error (m)
1.5
Error (m) position. However, making more measurements in all the RP drastically increase the time spent in radio map construction and consequently the battery drain through this process. As mentioned in Section 2, the RSSI distribution does not follow a Gaussian bell, with a well-defined average and median values. Since the characterization of the RSSI distribution remains unsolved, the correct filtering process used cannot be optimized. The proposed filtering process takes into account the dispersion of the measurements when the distribution is not symmetrical.
The second major issue considered in this work is the difference between k-NN and Wk-NN for final location computation. k-NN algorithm performs poorly compared with the weighted version once the data have been filtered however, results are no very different when both are W-1 W-2 W-3 W-1 W-2 W-3 1.5 Error (m)
1.5
Error (m) used with raw measurements. This is caused by the stochastic nature of the RSSI measurements, which makes individual measurements not to have enough information. Furthermore, since the final output of the proposed system is a linear combination of the RPs, how these points are choose highly affect the final output, because different selections can change the set of accessible points and possible correlations between coordinates.
The number of neighbours (k) for the algorithm is different in each situation (k-NN and Wk-NN) but also in simulations between different locations and phones. It is not possible to determine beforehand what is the value providing the best result in each location and with each experimental setup. The weighted functions proposed in this work provide a better result in all the experiments although some issues must be pointed. First, the result is no exactly the same for all the k values. There is a relation between the metric distance and weighted distance that has not been explored completely yet. The effect of the weighted function is less important than the filtering process effect and the Wk-NN use.
It must be said that in most fingerprinting experiments, the used technology -Wi-Fi or BLEis not designed for that purpose. Nor BLE neither the smartphones (hardware and software) are designed to make fast RSSI reading for localization. 5
In this work new considerations about how to improve an indoor localization system with Bluetooth Low Energy (BLE) and deterministic fingerprinting have been presented. A data filtering process and the Weighted k-Nearest Neighbours (Wk-NN) instead of the k Nearest Neighbours (k-NN) have been proposed, with specific proposals for the weight functions.
Simulations have shown that using a filtering process over measurements taken in the same RP, even at different times, can significantly reduce the error in fingerprinting positioning. Maximum errors have been reduced in 65% and the median error in 40%. Results have shown that a weighted average performs better when a k-NN algorithm is used, but only when data have been filtered. This improvement reduces the error by 60% compared with the k-NN. The error in the simulations with Wk-NN and filtered data has been reduced by more than 80% for both median and maximum error when compared with the k-NN and raw data fingerprinting simulations.
As part of the currently ongoing work, the authors are working in an improvement of the algorithm based on the physical characteristics of the RSSI to correctly design the mathematical steps involved. Mainly, the RSSI distribution over measurements to correctly define a filtering process and the combination between the metric and weighted function used in the k-NN algorithm.