Bluetooth positioning based on weighted K-nearest neighbors and adaptive bandwidth mean shift

Abstract

Bluetooth positioning is an important and challenging topic in indoor positioning. Although a lot of algorithms have been proposed for this problem, it is still not solved perfectly because of the instable signal strengths of Bluetooth. To improve the performance of Bluetooth positioning, this article proposes a coarse-to-fine positioning method based on weighted K-nearest neighbors and adaptive bandwidth mean shift. The method first employs weighted K-nearest neighbors to generate multi-candidate locations. Then, the testing position is obtained by applying adaptive bandwidth mean shift to the multi-candidate locations, which is used to search for the maximum density of the candidate locations. Experimental result indicates that the proposed method improves the performance of Bluetooth positioning.

Introduction

Recently, location-based service (LBS) has become a hot topic. People have developed many indoor positioning techniques, such as Wi-Fi, ¹ RFID, ² and ZigBee ³ . With the development of Bluetooth 4.0, ⁴ researchers have shown an increased interest in indoor positioning technology based on Bluetooth.

The most commonly used method in indoor positioning is position fingerprint. ⁵ Generally, this kind of method has two stages, which are offline training and online testing. In offline phase, some reference locations and corresponding signal strengths are stored in a received signal strength indicator (RSSI) database. Online phase is also known as real-time positioning stage, which matches the testing RSSI with database and returns the testing position.

In this article, we use Beacon ⁶ as Bluetooth signal source. Figure 1 shows a picture of Beacon. In the positioning process, Beacons emit Bluetooth signals. Users receive these signals by mobile devices. Then, the location is estimated by matching received signals with the fingerprint database. Figure 2 illustrates the localization process in this article.

Figure 1.

Picture of beacon.

Figure 2.

System architecture of the Bluetooth positioning system.

Classical fingerprint-based localization methods could be classified as probabilistic and deterministic types.

Among all the probabilistic algorithms, Bayes-based positioning algorithm ⁷ estimates the final location by maximizing posteriori probability that tests RSSI vector matching reference RSSIs. Fras et al. ⁸ combine weighted K-nearest neighbors (WKNN) with Bayes for a better localization accuracy. Alfakih et al. ⁹ propose to determine the testing position by approximating the probability distribution of RSSI data using Gaussian mixture model (GMM).

In deterministic algorithms, Rida et al. ¹⁰ develop trilateration-based Bluetooth positioning procedure. This method has a low computational complexity and requires less Beacons. However, this model is inaccurate in Bluetooth positioning because of the instable signal strengths. In addition to this method, a series of methods based on nearest neighbor (NN) are proposed, such as K-nearest neighbors (KNN),^11–14 WKNN,^11,15 and EWKNN (enhanced weighted K-nearest neighbors). ¹⁶ These algorithms are efficient in testing phase and have a relative small positioning error. Among these methods, Shin et al. ¹⁶ report that EWKNN achieves the best performance by selecting a proper K in Wi-Fi positioning. Besides these, Kushki et al. ¹⁷ propose a kernel-based localization algorithm. They developed a selection model of access point and present a kernel-based positioning algorithm.

In fact, because the received Bluetooth signal is instable, it is still challenging to achieve accurate positioning just by Bluetooth RSSI. According to our experiment, although the Bluetooth RSSI vectors drift all the time, the locations generated by classical methods scatter in a small range most of time. We utilize this property in this article, trying to determine a more accurate position based on these scattered locations.

Mean shift ¹⁸ is a nonparametric method, which is widely used for searching max density.^19–21 It is proposed by Fukunaga and Hostetler. ¹⁸ After that, the method is improved in kernel function and weight coefficient. ²² Adaptive bandwidth mean shift (ABMS) ²³ is developed from mean-shift algorithm. It calculates an optimal bandwidth in each iteration.

In this article, we propose a coarse-to-fine Bluetooth positioning method, which combines WKNN and ABMS together. In the coarse-positioning phase, WKNN is used to generate candidate positions. Then, in the fine localization procedure, ABMS is used to determine the final position.

The structure of this article is organized as follows. Section “Proposed positioning method” introduces the proposed positioning method. Section “Experimental result and analysis” shows the experimental result and analysis of the proposed method. Finally, the whole article is concluded in section “Conclusion.”

Proposed positioning method

Framework

This section introduces the proposed algorithm which combines WKNN with ABMS. First, in offline phase, all the reference locations and their corresponding Bluetooth RSSIs are stored in a fingerprint database. During the online phase, a smartphone receives RSSIs from different Beacons at a testing point in real time. Then, WKNN is applied to calculate location. Supposing that total M groups of RSSI vectors are received in online phase, then M candidate coordinates for testing point could be calculated by WKNN. These generated locations compose a candidate location set. Finally, ABMS is adopted to search for the location with highest density from the candidate location set. Figure 3 illustrates the process of proposed method.

Figure 3.

Illustration of the proposed method.

Generating candidate locations by WKNN

Generating single location by WKNN

Let R_p stand for the collected RSSI data at a testing point p over a period of time

$$\begin{array}{c}{R}_p=\left[\begin{array}{cccc}{\alpha }_1^{(p)}\hfill & {\alpha }_2^{(p)}\hfill & \cdots \hfill & {\alpha }_n^{(p)}\hfill \end{array}\right]\hfill \\ =\left[\begin{array}{cccc}{\mathrm{rssi}}_{11}^{(p)}\hfill & {\mathrm{rssi}}_{12}^{(p)}\hfill & \cdots \hfill & {\mathrm{rssi}}_{1n}^{(p)}\hfill \\ \multicolumn{1}{c}{{\mathrm{rssi}}_{21}^{(p)}}& {\mathrm{rssi}}_{22}^{(p)}\hfill & \cdots \hfill & {\mathrm{rssi}}_{2n}^{(p)}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\mathrm{rssi}}_{m1}^{(p)}}& {\mathrm{rssi}}_{m2}^{(p)}\hfill & \cdots \hfill & {\mathrm{rssi}}_{\mathrm{mn}}^{(p)}\hfill \end{array}\right]\hfill \end{array}$$

(1)

where ${\mathrm{rssi}}_{\mathrm{ij}}^{(p)}$ is the received RSSI value at testing point p from the jth Beacon at the ith scanning time. 1 ≤ i ≤ m, 1 ≤ j ≤ n. Here, m is the number of scanning times. n is the number of Beacons. The RSSI data in the ith row of R_p are from different Beacons at the same time. The RSSI data in the jth column of R_p are received from the same Beacon at different time

$${\overline{R}}_p=\left[\begin{array}{cccc}{\overline{\alpha }}_1^{(p)}\hfill & {\overline{\alpha }}_2^{(p)}\hfill & \cdots \hfill & {\overline{\alpha }}_n^{(p)}\hfill \end{array}\right]$$

(2)

$${\overline{S}}_p=\left[\begin{array}{cccc}{\overline{s}}_1^{(p)}\hfill & {\overline{s}}_2^{(p)}\hfill & \cdots \hfill & {\overline{s}}_n^{(p)}\hfill \end{array}\right]$$

(3)

where ${\overline{\alpha }}_j^{(p)}$ and ${\overline{s}}_j^{(p)}$ are the mean and standard deviation of the jth column of R_p.

In the same way, the RSSIs at reference location q over a period of time are denoted as follows

$$\begin{array}{c}{R}_q=\left[\begin{array}{cccc}{\alpha }_1^{\prime (q)}\hfill & {\alpha }_2^{\prime (q)}\hfill & \cdots \hfill & {\alpha }_n^{\prime (q)}\hfill \end{array}\right]\hfill \\ =\left[\begin{array}{cccc}{\mathrm{rssi}}_{11}^{(q)}\hfill & {\mathrm{rssi}}_{12}^{(q)}\hfill & \cdots \hfill & {\mathrm{rssi}}_{1n}^{(q)}\hfill \\ \multicolumn{1}{c}{{\mathrm{rssi}}_{21}^{(q)}}& {\mathrm{rssi}}_{22}^{(q)}\hfill & \cdots \hfill & {\mathrm{rssi}}_{2n}^{(q)}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\mathrm{rssi}}_{c1}^{(q)}}& {\mathrm{rssi}}_{c2}^{(q)}\hfill & \cdots \hfill & {\mathrm{rssi}}_{\mathrm{cn}}^{(q)}\hfill \end{array}\right]\hfill \end{array}$$

(4)

here, because different locations have different counts of scanning times, c and m may have different size.

The mean vector at reference location q could be denoted as follows

$${\overline{R}}_q=\left[\begin{array}{cccc}{\overline{\alpha }}_1^{\prime (q)}\hfill & {\overline{\alpha }}_2^{\prime (q)}\hfill & \cdots \hfill & {\overline{\alpha }}_n^{\prime (q)}\hfill \end{array}\right]$$

(5)

Then, the calculation process ⁷ of the final location is as follows.

First, ${\overline{R}}_p$ and ${\overline{S}}_p$ are standardized by the following formula

$$x_j=\frac{X_j-\min (X)}{\max (X)-\min (X)}$$

(6)

where X represents the vector of ${\overline{R}}_p$ or ${\overline{S}}_p$ , X_j represents the jth value of ${\overline{R}}_p$ or ${\overline{S}}_p$ vector.

Here, we use $\overline{R}{\prime }_p$ and $\overline{S}{\prime }_p$ to represent the standardized vectors of ${\overline{R}}_p$ and ${\overline{S}}_p$ , respectively

$$\overline{R}{\prime }_p=\left[\begin{array}{cccc}{\overline{r}}_1^{\prime (p)}\hfill & {\overline{r}}_2^{\prime (p)}\hfill & \cdots \hfill & {\overline{r}}_n^{\prime (p)}\hfill \end{array}\right]$$

(7)

$$\overline{S}{\prime }_p=\left[\begin{array}{cccc}{\overline{s}}_1^{\prime (p)}\hfill & {\overline{s}}_2^{\prime (p)}\hfill & \cdots \hfill & {\overline{s}}_n^{\prime (p)}\hfill \end{array}\right]$$

(8)

Then, the weight ${\omega }_j^{(p)}$ for the jth Beacon is calculated as follows ⁷

$${\omega }_j^{(p)}=1-\frac{{\overline{r}}_j^{\prime (p)}+{\overline{s}}_j^{\prime (p)}}{2}$$

(9)

Thus, we can get the weighted Euclidean distance d_q between the reference point q and the testing point p

$$d_q=\frac{1}{n}{\left(\sum _{j=1}^n{\omega }_j^{(p)}{|{\overline{\alpha }}_j^{(p)}-{\overline{\alpha }}_j^{\prime (q)}|}^2\right)}^{\frac{1}{2}}$$

(10)

The final location is calculated by WKNN as follows ²⁴

$$Y=\frac{\sum _{q=1}^K\frac{Y_q}{d_q+\epsilon }}{\sum _{q=1}^K\frac{1}{d_q+\epsilon }}$$

(11)

where Y_q is the coordinate of the qth reference point among K NNs, ε is a very small number used to avoid division by zero.

Figure 4 illustrates the positioning process by WKNN (K = 6). The asterisk in this figure is the real position, whose coordinate is (9, 4). In the localization process, six nearest neighbors (blue dots) are selected and the final location (green square) is (7.76, 3.90). The location error is 1.25 m.

Figure 4.

Illustration of positioning process by WKNN (K = 6).

Generating multiple locations by WKNN

Since each RSSI vector can produce one location by WKNN. If we use M groups of RSSI vectors for generating candidate locations, then M candidate locations would be obtained. Figure 5 illustrates the relationship of real location and M candidate locations when M = 50.

Figure 5.

Real and M candidate locations (M = 50).

Positioning by ABMS

ABMS

Here, the M candidate locations are distributed in a two-dimensional area. Ideally, the candidate locations should have high density at the real position. So, the real position could be obtained by searching for the maximum of probability.

The classical mean-shift algorithm can search the position with max density. It has a determined parameter of bandwidth. According to our experiment, a proper bandwidth can reduce the estimation error significantly. While if the bandwidth is not proper, mean-shift algorithm may lead to much larger errors.

To solve this problem, ABMS is adopted to calculate flexible bandwidths in the iteration processes. According to Cheng, ²² the new centroid is calculated by following function in each iteration of ABMS

$$m_{h,G}\left(x\right)=\frac{\sum _{i=1}^n{x}_{i}g\left({\Vert \frac{x-x_i}{h}\Vert }^2\right)}{\sum _{i=1}^{n}g\left({\Vert \frac{x-x_i}{h}\Vert }^2\right)}$$

(12)

where x is the initial centroid position of each iteration. x_i is the ith point in candidate locations, i = 1,2,…,n, n is the number of points. g(·) denotes the profile of kernel G(x). m_h,G(x) is the new generated position.

There are three kinds of common kernel functions, which are Epanechnikov, Uniform, and Normal. These kernels are all tested in this article (see section “Accuracy”). According to our experiment, Normal kernel is selected in this article.

The profile of Normal function is

$$g\left({\Vert \frac{x-x_i}{h}\Vert }^2\right)=\frac{1}{2\pi }\exp (-\frac{1}{2}{\Vert \frac{x-x_i}{h}\Vert }^2)$$

(13)

where h is the bandwidth parameter. It is selected according to experiment

$$h=\exp \left(\frac{1}{s}\right)$$

(14)

here, s is the standard deviation of points at the center of point x in current area

$$s=\sqrt{\frac{1}{n}\sum _{i=1}^n{\Vert x-x_i\Vert }^2}$$

(15)

Positioning by ABMS

The final position is calculated by ABMS on the set of candidate positions, which are obtained by WKNN. The positioning process by ABMS algorithm is given in Algorithm 1.

Algorithm 1 Framework of positioning process by ABMS.
Input: Candidate location set {xi}, which is generated by WKNN based on RSSI vectors;
Output: Final coordinate x.
1: Initialize coordinate x(0), bandwidth h(0), kernel G(x) and ε;
2: for each k∈ [1,N] do
3:  x(k+1) = mh,G(x(k), h(k)) according to equation (12);
4:  Calculate bandwidth h(k+1) by equation (14);
5:  if||x(k+1) − x(k)|| < εthen loop;
6:  endif
7: end for
8: returnx(k+1);

Figure 6 illustrates the positioning result by WKNN and WKNN+ABMS. The green asterisk shows the real position of the receiver. The red square and pink triangle are obtained positions by WKNN and WKNN+ABMS, respectively. In this figure, we can see that the location obtained by WKKN+ABMS is closer to real position than WKNN.

Figure 6.

Illustration of WKNN+ABMS positioning.

Experimental result and analysis

This section introduces the experimental details, result, and analysis.

Experimental details

The experiment is carried out in a computer laboratory of Northeastern University. In this room, 30 Beacons are placed on the ceiling, with a distance of 2 m from each other. The hollow stars in Figure 7 illustrate the distribution of Beacons.

Figure 7.

Distribution of beacons.

In the experiment, a smartphone is used to receive Bluetooth signals emitted from Beacons. In offline phase, we select 24 reference locations, as shown in Figure 8, approximating 2 m apart from each other. In the positioning process, M groups of RSSI vectors are recorded for each testing location.

Figure 8.

Distribution of reference locations.

Occasionally, there would be some missing data in these recorded RSSI vectors. The missing data is treated as 0 dBm in our experiment. And the corresponding data in training database are also set to be 0.

The positioning steps are given as follows. First, a set of candidate locations for each testing point is generated by WKNN. Because we record M RSSI vectors for each testing position in our experiment, the M candidate positions can be obtained by WKNN. Then, ABMS is applied to the M candidate coordinates for a final position. The proposed method is experimented on MATLAB 2014a under Windows 7 operating system.

Accuracy

Figure 9 shows the positioning errors of WKNN method with different K. In this experiment, the mean vector of 50 RSSI vectors are used to construct positioning fingerprint database. Each testing location is calculated using WKNN method. The horizontal axis in Figure 9 shows the index of different testing positions. The curves in this figure illustrates the positioning errors with different K. According to this figure, K = 6 has a minimum standard deviation. So, we set K = 6 in all the following experiment.

Figure 9.

Positioning errors of different test locations by WKNN with different K values.

Figure 10 illustrates the impacts of different kernel functions and bandwidths in ABMS. In this figure, the horizontal axis is bandwidth h, h = [0.5, 0.6, 0.7, 0.8, 0.9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] in our experiments. The vertical axis shows the average positioning error. The curves in this figure demonstrate that with the increasing of h, three curves converge to the same value. However, when h is smaller than 1, the positioning error of the normal kernel is less than the other two obviously. When h is larger than 1, the three curves are quite close. To make the positioning error smallest under different cases, we select normal kernel for positioning.

Figure 10.

Positioning errors with different kernel functions and bandwidths.

Figure 11 shows the positioning error with different counts of RSSI vectors (M). This figure indicates that the positioning error decreases with M. It means that a larger M generally leads to a smaller positioning error. But note that a larger M requires much more computing time and motionless time. So, this parameter should be considered carefully in real applications. We suggest to choose an adaptive M according to the data obtained by other sensors, such as speed and acceleration sensors. In this article, we choose M = 50 in our experiment.

Figure 11.

Positioning errors with different counts of RSSI vectors (M).

Figure 12 shows the performance comparison of proposed WKNN+ABMS and classical positioning methods. The curves in this figure demonstrate that the proposed method achieves the best performance in all of the tested methods.

Figure 12.

Comparison of cumulative distribution of positioning error for different methods.

Table 1 shows some key indicators of positioning error for six different methods. From this table, it can be found that the proposed method has the smallest mean error of 1.3526 m, maximum error of 1.9745 m, and standard deviation of 0.4747 m. And totally, 100.00% of positioning result has a error less than 2 m for the proposed method, which is also the largest in the table.

Table 1.

Positioning error of different methods.

Method	Mean (m)	Max (m)	Standard (m)	≤ 2 m(%)
EWKNN	1.4127	2.1135	0.5523	81.82
Bayes	1.6898	2.8674	0.7000	59.09
Trilateration	2.4263	6.7514	1.6457	40.91
WKNN	1.3842	2.0816	0.5789	81.82
WKNN+Bayes 8	1.8632	4.1231	1.2144	45.45
WKNN+ABMS	1.3526	1.9745	0.4747	100.00

WKNN: weighted K-nearest neighbors; EWKNN: enhanced weighted K-nearest neighbors; ABMS: adaptive bandwidth mean shift.

Bold values represents the performance of proposed method.

Efficiency

The computation time of different methods is given in Tables 2 and 3. The proposed method requires more computing time as can be seen in Tables 1 and 2.

Table 2.

Positioning time of different methods (ms).

Method	Time (ms)
EWKNN	23.366
Bayes	157.958
Trilateration	67.599
WKNN	23.197
WKNN+Bayes 8	156.054

WKNN: weighted K-nearest neighbors; EWKNN: enhanced weighted K-nearest neighbors.

Table 3.

Positioning time of WKNN+ABMS with different groups of RSSI vector (ms).

Groups of RSSI vector	Time (ms)
10	215.077
20	408.834
30	612.426
40	859.960
50	1032.999

WKNN: weighted K-nearest neighbors; ABMS: adaptive bandwidth mean shift; RSSI: received signal strength indicator.

But the proposed method has its advantages in real applications. Since this method has two steps, which estimate coarse positions by WKNN and determine an accurate position by ABMS. These two steps can be used adaptively to meet the needs of different applications:

1. If a positioning process requires fast responses, then the localization process can be calculated just using fewer groups of RSSI vectors by WKNN, even just one group of RSSI vector.

2. If a user keeps static at some place (this can be estimated by sensors of cell phone, such as speed and acceleration sensors), then the positioning result can be calculated more accurately using more groups of RSSI vectors by the proposed WKNN+ABMS method.

What’s more, the proposed model can be used as follows. The target positions are calculated by WKNN without ABMS. When the user keeps static for a while, these calculated positions could be collected directly and processed by ABMS. This process would increase little additional computing time, but it can improve the accuracy of positioning significantly. So, the proposed method is beneficial for real applications.

Conclusion

This article proposes a Bluetooth positioning method based on WKNN and ABMS. First, multiple locations are generated by WKNN. Then, the final position is obtained by ABMS. The experimental result indicates that proposed method achieves a better performance than classical algorithms for Bluetooth positioning.

The main contributions of this article could be concluded as following: (1) This article introduces mean-shift algorithm to positioning problem by searching for max density of candidate locations. (2) To solve the bandwidth problem of mean-shift algorithm, we employ ABMS for final positioning. (3) The method could be used in other positioning problem.