# IWKNN: An Effective Bluetooth Positioning Method Based on Isomap and WKNN

Authors: Qi Wang; Yingying Feng; Xiangde Zhang; Yanrui Sun; Xiaojun Lu
Journal: Mobile Information Systems
 (2016)

---

## Abstract

Recently, Bluetooth-based indoor positioning has become a hot research topic. However, the instability of Bluetooth RSSI (Received Signal Strength Indicator) promotes a huge challenge in localization accuracy. To improve the localization accuracy, this paper measures the distance of RSSI vectors on their low-dimensional manifold and proposes a novel positioning method IWKNN (Isomap-based WeightedK-Nearest Neighbor). The proposed method firstly uses Isomap to generate low-dimensional embedding for RSSI vectors. Then, the distance of two given RSSI vectors is measured by Euclidean distance of their low-dimensional embeddings. Finally, the position is calculated by WKNN. Experiment indicates that the proposed approach is more robust and accurate.


---

## Body

## 1. Introduction

Positioning is a basic requirement in people’s daily life. It is the basis of LBS (Location-Based Service) [1, 2]. Generally, positioning problems could be classified as outdoor and indoor. The outdoor positioning mainly uses GPS (Global Positioning System), GPRS (General Packet Radio Service), and so forth, while the indoor positioning mostly utilizes short range signals, such as Wi-Fi (Wireless-Fidelity) [3, 4] and Bluetooth [5–7]. And the testing position is determined based on the received signals. These positioning technologies have been widely used in different kinds of applications.Beacon is a commonly used Bluetooth signal source. Figure1 shows a picture of beacon. It is small and low-power Bluetooth dissipation equipment. It can work for even two years just with a fastener battery. So beacon can be placed without too many restrictions, having broad prospects of application.Figure 1
A picture of beacon.This paper aims to improve the accuracy of Bluetooth-based indoor positioning, when beacons are preplaced at some given places in a room. A smart device is used to receive these signals. Then the position of device can be calculated based on received Bluetooth RSSI data.Classical positioning methods could be classified as two types. One is function-based model. This kind of method is mostly developed based on signal propagation function [8, 9], for example, trilateration algorithm [10, 11] and IoT (Internet of Things) [12]. This kind of model requires an estimated signal propagation function. If the positions of emitters are given, then any testing location could be calculated based on RSSI data and signal propagation function. This kind of method does not need to store the vast RSSI data of reference positions. The localization accuracy relies on the measurement error of signal propagation function. The less the error is, the more accurate the localization is. Because the signal intensity of beacon is instable, the error of signal propagation model would be relatively large. So it is inaccurate to localize a Bluetooth receiver by this kind of method.The other kind of method could be described as classification algorithm, which is built up based on position fingerprint. Figure2 illustrates general positioning process based on fingerprint. Lemic et al. [13] and Jaffre et al. [14] determine the final position by KNN (K-Nearest Neighbor). They find the nearest K reference positions to calculate unknown position according to Euclidean distance of RSSI vectors. Caso et al. [15] develop WKNN (Weighted K-Nearest Neighbor) for 3D positioning by weighting each nearest neighbor. Besides this, Shin et al. [16] propose EWKNN (Enhanced WeightedK-Nearest Neighbor) by making parameter K variable to improve the positioning performance.Figure 2
Positioning process based on fingerprint.Cheng et al. [17] introduce SVM (Support Vector Machine) to classify the RSSI vectors. Mu et al. [18] classify the RSSI data by ANN (Artificial Neural Network). Zhe [19] develops a positioning method based on Bayes method. He uses more flexible models to estimate distributions of beacon signals. Fras et al. [20] proposed a new method that combines Bayes and WKNN. Alfakih et al. [21] develop a positioning algorithm based on GMM (Gaussian Mixture Model). They calculate the probability that the testing RSSI belongs to each reference RSSI data. The final location is calculated by sum of weighted coordinates of reference locations. Different from Bayes method, GMM is to calculate the probability based on Gaussian Mixture function.Kim et al. [22] and Thuong et al. [23] estimate the positioning performance for KNN algorithm. Jaffre et al. [14] compare KNN and Bayes positioning method with several different distance measurements and value K. Experimental result states that KNN and Euclidean distance can get the smallest mean positioning error when K
=
4. Zhang et al. [24] use beacons as emitter and compare the positioning performance of ANN, SVM, and improved KNN. The paper reports that the improved KNN algorithm has the highest positioning accuracy.Because of the instability of Bluetooth, received RSSI vectors have a large variety. This means that RSSI vectors of faraway positions may have smaller Euclidean distances than that of neighborhood. It leads to choosing a faraway reference position as candidate location sometimes. This enlarges the localization error of Euclidean distance based methods, such as KNN and WKNN. So just using Euclidean distance to measure similarity of RSSI vectors is not accurate. Bluetooth positioning requires a more robust distance measurement method.Manifold learning [25] finds the low-dimensional embedding for high-dimensional data. Researchers have proposed different algorithms for manifold learning, such as MDS (Multidimensional Scaling) [26], LLE (Locally Linear Embedding) [27], and Isomap [28]. The geodesic distance is a useful distance metric of Isomap in manifold learning. It can be used to measure the similarity of high-dimensional vectors. Figure 3 illustrates the comparison of Euclidian and geodesic distances.Figure 3
The difference of geodesic distance and Euclidean distance.We consider Bluetooth indoor positioning as a high-dimensional data matching problem. Calculate low-dimensional embeddings for the training and testing RSSI data. Use the Euclidian distance of low-dimensional embeddings to measure the approaching extent of two given RSSI vectors. The final location is calculated by WKNN. Figure4 demonstrates the flow chart of proposed method.Figure 4
The block diagram of the proposed algorithm.Figure5 illustrates the comparison of positioning results of WKNN and proposed IWKNN. Figure 5(a) gives a localization illustration by WKNN based on Euclidian distance, while Figure 5(b) shows a positioning process by proposed IWKNN. In Figure 5, the red rectangles are real testing positions. The pink dots are selected K nearest training positions (K
=
4). The green hollow dots are obtained final position. Figure 5 shows that the proposed method can select more proper nearest positions than WKNN, achieving a better localization.Figure 5
Positioning by WKNN and proposed IWKNN.
(a)
Positioning by WKNN (K
=
4)
(b)
Positioning by proposed IWKNN (K
=
4)This paper is organized as follows: Section2 introduces the mathematical model of indoor positioning problem. Section 3 illustrates the proposed localization algorithm based on Isomap and WKNN. Section 4 shows the experimental result and analysis. Section 5 concludes the whole paper.


## 2. The Mathematical Model of Bluetooth Positioning

This section presents the mathematical model of Bluetooth positioning problem.Here, let us consider a general Bluetooth positioning problem. We establish a rectangular coordinate system in a region.m beacons are distributed evenly in this area. Then a cell phone in this region would receive and measure RSSIs from all beacons. They can be grouped as a RSSI vector. The Bluetooth positioning problem is to determine the coordinate of cell phone in the rectangular coordinate system.Suppose there are totaln reference positions. Administrator should record Bluetooth RSSI at each reference position for a period of time. When a user is standing at some place in this area, he can measure the Bluetooth RSSI by cell phone or other equipment. Then the coordinate of person can be calculated based on the newly measured and recorded RSSI data.Letx
i represent the coordinate of ith reference location; x
i
=
[
a
i
,
b
i
], i
=
1
,
…
,
n. r
s
s
i
i
j
t is the RSSI received from the jth beacon at the ith reference position at time t. α
i
t is a vector composed of RSSI on the ith reference location from different beacons at time t; α
i
t
=
[
r
s
s
i
i
1
t
,
r
s
s
i
i
2
t
,
…
,
r
s
s
i
i
m
t
]
T, i
=
1
,
…
,
n. Here, m is the number of beacons. n is the number of reference locations.If the RSSI data are separately received at timet
=
t
1
,
t
2
,
…
,
t
l, then the matrix of RSSI data for ith reference locations could be written as(1)
α
i
t
1
,
α
i
t
2
,
…
,
α
i
t
l
=
r
s
s
i
i
1
t
1
r
s
s
i
i
1
t
2
⋯
r
s
s
i
i
1
t
l
r
s
s
i
i
2
t
1
r
s
s
i
i
2
t
2
⋯
r
s
s
i
i
2
t
l
⋮
⋮
⋱
⋮
r
s
s
i
i
m
t
1
r
s
s
i
i
m
t
2
⋯
r
s
s
i
i
m
t
l
.Letα
¯
i be the fingerprint of the ith reference location; then(2)
α
¯
i
=
r
s
s
i
¯
i
1
,
r
s
s
i
¯
i
2
,
…
,
r
s
s
i
¯
i
m
T
=
1
l
∑
j
=
1
l
r
s
s
i
i
1
t
j
,
∑
j
=
1
l
r
s
s
i
i
2
t
j
,
…
,
∑
j
=
1
l
r
s
s
i
i
2
t
j
T
.Here, i
=
1,2
,
…
,
n.For any unknown testing positionx
→
=
[
a
,
b
], the received RSSI vector α
x at x
→ could be written as(3)
α
x
=
r
s
s
i
x
1
,
r
s
s
i
x
2
,
…
,
r
s
s
i
x
m
T
.Then the localization problem could be expressed by the following formula:(4)
a
^
,
b
^
=
T
α
¯
1
,
α
¯
2
,
…
,
α
¯
n
,
α
x
.Here, T is the positioning function to be determined, which projects a RSSI vector to coordinate of position. This problem is generally solved by positioning fingerprint methods. These kinds of methods are mostly developed based on the Euclidean distance of RSSI vectors, such as KNN [13, 14], WKNN [15], and EWKNN [16]. This paper develops a performance enhanced positioning method, which employs low-dimensional embedding distance to measure the similarity of RSSI vectors and use WKNN to determine unknown testing location.


## 3. Proposed Method

This section presents the proposed positioning method IWKNN. Firstly, the low-dimensional embeddings of reference and testing RSSI vectors are calculated by Isomap. Then, the unknown testing position is generated according to distances of low-dimensional embeddings by WKNN.


### 3.1. Overview

As an important method in manifold learning, Isomap can find the low-dimensional embedding for high-dimensional manifold. It can keep the neighborhood structure of high-dimensional manifold in a low-dimensional space.LetA be a set, which is composed of (
n
+
1
) RSSI vectors.(5)
A
=
α
¯
i
,
α
x
∣
i
=
1,2
,
…
,
n
.
A
⊂
R
m.SupposeB is a low-dimensional embedding of A; B
=
{
β
i
,
β
x
∣
i
=
1
,
…
,
n
}, where B
⊂
R
m
′ and m
′
<
m.Letf be a smooth embedding projection from B to A, f
:
B
→
A, satisfying α
i
=
f
(
β
i
) (for all i
=
1,2
,
…
,
n) and α
x
=
f
(
β
x
).Here, the low-dimensional embedding is calculated by Isomap. The distance of RSSI vectors is measured by Euclidian distance of their low-dimensional embeddings. Finally, the unknown testing position is calculated based on low-dimensional distances by WKNN.


### 3.2. Geodesic Distance of High-Dimensional Data

Assume all the elements inA are from the same manifold. Ideally, any element in A can be linearly expressed by its neighborhood points. We connect each point in A to its M nearest neighbors (M is a predetermined parameter). Then an undirected weighted graph is constructed. Thus, a distance matrix of this graph could be generated by Euclidean distance. The edge weight for given two points α
i and α
j is d
E
(
i
,
j
)
=
α
i
-
α
j.According to Isomap algorithm [28], the shortest distance of any two high-dimensional RSSI vectors is used as geodesic distance. It can be calculated by Floyd’s algorithm [28], which is shown in (6)
D
G
=
d
G
i
,
j
k
=
d
E
i
,
j
k
=
0
min
⁡
d
G
i
,
j
k
-
1
,
d
G
i
,
k
k
-
1
+
d
G
k
,
j
k
-
1
k
≥
1
.Here, k
=
0
,
…
,
n
+
1.


### 3.3. Low-Dimensional Embedding

Then a low-dimensional embedding could be calculated as follows [28]:(7)
τ
D
=
H
S
H
-
2
,where S
i
j
=
(
D
i
j
2
), H
=
I
-
(
1
/
(
n
+
1
)
)
E
E
T, I is a unit matrix, and E
=
[
1,1
,
…
,
1
]
T.Letλ
1
,
λ
2
,
…
,
λ
m
′ be the largest m
′ eigenvalues of τ
(
D
) (in descending order) and their corresponding eigenvectors be u
1
,
u
2
,
…
,
u
m
′. Then all of the vectors in set B could be obtained by [28](8)
β
1
,
β
2
,
…
,
β
n
,
β
x
=
λ
1
u
1
,
λ
2
u
2
,
…
,
λ
m
′
u
m
′
T
.Then the low-dimensional embedding ofA
=
{
α
¯
1
,
α
¯
2
,
…
,
α
¯
n
,
α
x
} is B
=
{
β
1
,
β
2
,
…
,
β
n
,
β
x
}.


### 3.4. Distance of Low-Dimensional Embedding

The training low-dimensional fingerprint of theith reference point is [
β
1
,
β
2
,
…
,
β
n
]. The testing low-dimensional vector is β
x. The distance of β
i
(
i
=
1,2
,
…
,
n
) and β
x is measured by Euclidian distance.(9)
d
i
=
β
i
-
β
x
.


### 3.5. Positioning by WKNN

According to WKNN [15], let d
p
1
,
d
p
2
,
…
,
d
p
K stand for the K minimum values in {
d
1
,
d
2
,
…
,
d
n
}. Then the reference coordinates [
a
p
j
,
b
p
j
],  j
=
1
,
…
,
K, are selected as candidate reference locations. Finally, the coordinate of testing position [
a
^
,
b
^
] is estimated by the following formula [15]:(10)
a
^
,
b
^
=
1
∑
j
=
1
K
w
j
∑
j
=
1
K
w
j
a
p
j
,
b
p
j
,where(11)
w
j
=
1
d
p
j
+
c
.Here, c is a relative small positive number.


## 3.1. Overview

As an important method in manifold learning, Isomap can find the low-dimensional embedding for high-dimensional manifold. It can keep the neighborhood structure of high-dimensional manifold in a low-dimensional space.LetA be a set, which is composed of (
n
+
1
) RSSI vectors.(5)
A
=
α
¯
i
,
α
x
∣
i
=
1,2
,
…
,
n
.
A
⊂
R
m.SupposeB is a low-dimensional embedding of A; B
=
{
β
i
,
β
x
∣
i
=
1
,
…
,
n
}, where B
⊂
R
m
′ and m
′
<
m.Letf be a smooth embedding projection from B to A, f
:
B
→
A, satisfying α
i
=
f
(
β
i
) (for all i
=
1,2
,
…
,
n) and α
x
=
f
(
β
x
).Here, the low-dimensional embedding is calculated by Isomap. The distance of RSSI vectors is measured by Euclidian distance of their low-dimensional embeddings. Finally, the unknown testing position is calculated based on low-dimensional distances by WKNN.


## 3.2. Geodesic Distance of High-Dimensional Data

Assume all the elements inA are from the same manifold. Ideally, any element in A can be linearly expressed by its neighborhood points. We connect each point in A to its M nearest neighbors (M is a predetermined parameter). Then an undirected weighted graph is constructed. Thus, a distance matrix of this graph could be generated by Euclidean distance. The edge weight for given two points α
i and α
j is d
E
(
i
,
j
)
=
α
i
-
α
j.According to Isomap algorithm [28], the shortest distance of any two high-dimensional RSSI vectors is used as geodesic distance. It can be calculated by Floyd’s algorithm [28], which is shown in (6)
D
G
=
d
G
i
,
j
k
=
d
E
i
,
j
k
=
0
min
⁡
d
G
i
,
j
k
-
1
,
d
G
i
,
k
k
-
1
+
d
G
k
,
j
k
-
1
k
≥
1
.Here, k
=
0
,
…
,
n
+
1.


## 3.3. Low-Dimensional Embedding

Then a low-dimensional embedding could be calculated as follows [28]:(7)
τ
D
=
H
S
H
-
2
,where S
i
j
=
(
D
i
j
2
), H
=
I
-
(
1
/
(
n
+
1
)
)
E
E
T, I is a unit matrix, and E
=
[
1,1
,
…
,
1
]
T.Letλ
1
,
λ
2
,
…
,
λ
m
′ be the largest m
′ eigenvalues of τ
(
D
) (in descending order) and their corresponding eigenvectors be u
1
,
u
2
,
…
,
u
m
′. Then all of the vectors in set B could be obtained by [28](8)
β
1
,
β
2
,
…
,
β
n
,
β
x
=
λ
1
u
1
,
λ
2
u
2
,
…
,
λ
m
′
u
m
′
T
.Then the low-dimensional embedding ofA
=
{
α
¯
1
,
α
¯
2
,
…
,
α
¯
n
,
α
x
} is B
=
{
β
1
,
β
2
,
…
,
β
n
,
β
x
}.


## 3.4. Distance of Low-Dimensional Embedding

The training low-dimensional fingerprint of theith reference point is [
β
1
,
β
2
,
…
,
β
n
]. The testing low-dimensional vector is β
x. The distance of β
i
(
i
=
1,2
,
…
,
n
) and β
x is measured by Euclidian distance.(9)
d
i
=
β
i
-
β
x
.


## 3.5. Positioning by WKNN

According to WKNN [15], let d
p
1
,
d
p
2
,
…
,
d
p
K stand for the K minimum values in {
d
1
,
d
2
,
…
,
d
n
}. Then the reference coordinates [
a
p
j
,
b
p
j
],  j
=
1
,
…
,
K, are selected as candidate reference locations. Finally, the coordinate of testing position [
a
^
,
b
^
] is estimated by the following formula [15]:(10)
a
^
,
b
^
=
1
∑
j
=
1
K
w
j
∑
j
=
1
K
w
j
a
p
j
,
b
p
j
,where(11)
w
j
=
1
d
p
j
+
c
.Here, c is a relative small positive number.


## 4. Experimental Result and Analysis

### 4.1. Experimental Details

The experiment is carried out in a laboratory of Northeastern University. The laboratory room is7
×
18
m
2. A 6
×
18
m
2 subarea is used as experimental area.In our experiment, beacons are used to emit Bluetooth signals, whose parameters were adjusted referencing [5–7]. The emitting interval is set with 2 HZ and power of −8 db. Samsung Galaxy S3 is used to receive Bluetooth signals at a frequency of 1 Hz.Figure6 shows the positions of beacons and reference locations. The hollow dots in Figure 6(a) show the layout of 30 beacons. They are placed evenly on the ceiling with mean distance of 2 meters. All the beacons are recorded with MAC address and positions. The solid dots in Figure 6(b) show the layout of 24 reference positions with mean distance of 2 meters on the ground.Figure 6
The layout of beacons and reference positions.
(a)
The positions of beacons
(b)
The reference positionsTo build a usable training fingerprint, RSSI data is recorded for 200 seconds at each reference position. And Kalman filter [29] is used to preprocess RSSI data.Considering that a person may move fast with a cell phone, we just use one vector of RSSI data for positioning. In this paper, 74 testing positions are used in our experiment. These positions are distributed evenly with one-meter distance in the6
×
18
m
2 experimental area.


### 4.2. Selection ofM and m
′

In Isomap algorithm,M and m
′ are important parameters, which are the count of nearest neighbors and dimension of low-dimensional embedding. To select a proper M and m
′, some experiments are carried out firstly.Table1 shows the positioning errors with different M. As can be seen from the table, when M is between 15 and 21, the maximum and mean positioning errors are relatively small and stable. According to our experiment, the proposed method achieves minimum mean error when M
=
20.Table 1
The positioning errors with differentM.
M
Max error (m)
Mean error (m)
Min error (m)
Std error (m)
3
4.991
1.668
0.026
0.919
4
5.389
1.657
0.230
1.006
5
5.086
1.620
0.093
0.952
6
3.851
1.796
0.473
0.907
7
4.112
1.723
0.326
0.828
8
4.278
1.910
0.335
0.953
9
4.317
1.936
0.027
1.056
10
3.400
1.865
0.078
0.818
11
5.187
2.037
0.424
1.094
12
5.806
1.983
0.389
1.148
13
4.290
1.942
0.377
1.009
14
5.388
1.938
0.292
0.971
15
3.814
1.672
0.278
0.791
16
3.815
1.592
0.303
0.775
17
3.528
1.635
0.334
0.726
18
4.516
1.732
0.297
0.841
19
3.602
1.635
0.331
0.864
20
3.605
1.516
0.001
0.782
21
3.600
1.618
0.117
0.776
22
4.601
1.655
0.350
0.976
23
4.590
1.622
0.345
0.934
24
4.902
1.633
0.345
0.982Table2 shows the mean positioning error with different M and m
′. M is assigned between 15 and 21. m
′ varies from 2 to 15. In this table, we can find that when m
′ is between 4 and 6, the mean positioning error is relatively small.Table 2
The mean positioning error with differentm
′.
m
′
/
M
15
16
17
18
19
20
21
2
1.778
1.772
1.957
1.807
1.895
2.004
1.920
3
1.856
1.710
1.811
1.735
1.680
1.801
1.712
4
1.770
1.744
1.687
1.663
1.601
1.573
1.529
5
1.672
1.592
1.635
1.732
1.635
1.516
1.618
6
1.625
1.523
1.712
1.736
1.657
1.597
1.617
7
1.741
1.600
1.705
1.703
1.761
1.675
1.609
8
1.751
1.585
1.703
1.783
1.614
1.731
1.594
9
1.770
1.695
1.718
1.843
1.639
1.730
1.593
10
1.778
1.686
1.666
1.825
1.672
1.682
1.606
11
1.785
1.676
1.718
1.823
1.749
1.695
1.559
12
1.764
1.618
1.722
1.776
1.665
1.646
1.584
13
1.742
1.577
1.695
1.761
1.630
1.635
1.592
14
1.736
1.633
1.697
1.755
1.653
1.675
1.615
15
1.745
1.638
1.674
1.741
1.678
1.702
1.606According to these experiments, we setM
=
20 and m
′
=
5 in this paper.


### 4.3. The Effectiveness of Isomap

The effectiveness of Isomap is firstly examined in our Bluetooth localization experiment. We compare the performance of WKNN and EWKNN [16] and their Isomap enhanced versions. WKNN is separately tested with K
=
3,4
,
…
,
9. And the threshold of EWKNN is mean of distance vector.Figure7 shows the error distribution of different methods. In Figure 7, the first-column figures illustrate the error distributions of original methods. The second column shows the error distribution of Isomap enhanced methods. The third column shows the differences of original and Isomap enhanced methods. From Figure 7, we can find that the error distribution of developed Isomap enhanced methods (IWKNN and IEWKNN) is more concentrated in the low error region than original methods (WKNN and EWKNN).Figure 7
Error distributions of original and Isomap enhanced methods.Figure8 illustrates the cumulative probability of error distribution for different methods. The curves in these figures demonstrate that the Isomap enhanced methods (IWKNN and IEWKNN) achieve better performance than original methods (WKNN and EWKNN).Figure 8
Cumulative error distribution of original and Isomap enhanced methods.
(a)
WKNN and IWKNN (K
=
3)
(b)
WKNN and IWKNN (K
=
4)
(c)
WKNN and IWKNN (K
=
5)
(d)
WKNN and IWKNN (K
=
6)
(e)
WKNN and IWKNN (K
=
7)
(f)
WKNN and IWKNN (K
=
8)
(g)
WKNN and IWKNN (K
=
9)
(h)
EWKNN and IEWKNNFinally, the performance of all tested methods is given in Table3. According to this table, Isomap almost improves all of positioning indicators clearly. The best values of important indicators are given in bold font. The minimum of max error is 4.994, which is obtained by IWKNN with K
=
9. The minimum of mean error is 1.463, which is obtained by IWKNN with K
=
4. The minimum of min error is 0.0005, which is obtained by IWKNN with K
=
3 and IEWKNN. The minimum of std error is 0.674, which is obtained by IWKNN with K
=
7. The maximum of “ratio of error less than 2 meters” is 78.96
%, which is obtained by IWKNN with K
=
5. This table supports the effectiveness of proposed Isomap enhanced positioning methods.Table 3
The positioning error of original and Isomap enhanced methods.
Method
Max error (m)
Mean error (m)
Min error (m)
Std error (m)
≤2 m (%)
WKNN(
K
=
3
)
7.000
1.505
0.0008
0.772
73.99%
IWKNN(
K
=
3
)
5.046
1.481
0.0005
0.758
75.58%
WKNN(
K
=
4
)
6.558
1.508
0.001
0.732
74.49%
IWKNN(
K
=
4
)
7.110
1.463
0.002
0.710
76.05%
WKNN(
K
=
5
)
6.803
1.541
0.014
0.712
76.12%
IWKNN(
K
=
5
)
6.162
1.478
0.036
0.693
78.96%
WKNN(
K
=
6
)
6.045
1.581
0.002
0.707
71.45%
IWKNN(
K
=
6
)
5.216
1.512
0.011
0.680
77.08%
WKNN(
K
=
7
)
5.774
1.631
0.023
0.703
69.18%
IWKNN(
K
=
7
)
5.273
1.558
0.041
0.674
74.27%
WKNN(
K
=
8
)
5.135
1.689
0.023
0.721
65.50%
IWKNN(
K
=
8
)
5.138
1.604
0.066
0.683
70.77%
WKNN(
K
=
9
)
5.447
1.749
0.019
0.739
61.51%
IWKNN(
K
=
9
)
4.994
1.660
0.032
0.703
67.14%
EWKNN
7.000
1.502
0.002
0.756
74.26%
IEWKNN
5.046
1.477
0.0005
0.743
76.04%According to Table3, we suggest K
=
4 or 5 for small mean positioning error and large “ratio of error less than 2 meters.”


### 4.4. Comparison with Different Methods

In order to test the performance of proposed method more clearly, we compare the proposed IWKNN (K
=
4) with six different positioning methods.Figure9 compares the performances of different methods. From this table, we can see that Bayes method has the best performance in the low error part, and the proposed IWKNN performs best in almost all the remaining part.Figure 9
The cumulative error distribution of different methods.Table4 illustrates the positioning error of different methods. According to this table, GMM, Bayes, and WKNN-Bayes’s max errors are better than other methods. But the improved Bayes method proposed by Fras et al. [20] can generate small max, mean, and std errors. The proposed IWKNN has the minimal mean error and maximal “ratio of error less than 2 meters.”Table 4
The positioning error of different methods.
Method
Max error (m)
Mean error (m)
Min error (m)
Std error (m)
≤2 m (%)
Triangulation
11.443
2.592
0.0288
1.616
41.80%
IoT [12]
7.576
3.077
0.0331
1.482
27.72%
GMM [21]
12.880
3.506
0
1.965
65.03%
Bayes
14.318
2.391
0
1.611
44.46%
WKNN-Bayes [20]
8.062
2.031
0
1.116
53.42%
WKNN
6.558
1.508
0.001
0.732
74.49%
IWKNN
7.110
1.463
0.002
0.710
76.05%


## 4.1. Experimental Details

The experiment is carried out in a laboratory of Northeastern University. The laboratory room is7
×
18
m
2. A 6
×
18
m
2 subarea is used as experimental area.In our experiment, beacons are used to emit Bluetooth signals, whose parameters were adjusted referencing [5–7]. The emitting interval is set with 2 HZ and power of −8 db. Samsung Galaxy S3 is used to receive Bluetooth signals at a frequency of 1 Hz.Figure6 shows the positions of beacons and reference locations. The hollow dots in Figure 6(a) show the layout of 30 beacons. They are placed evenly on the ceiling with mean distance of 2 meters. All the beacons are recorded with MAC address and positions. The solid dots in Figure 6(b) show the layout of 24 reference positions with mean distance of 2 meters on the ground.Figure 6
The layout of beacons and reference positions.
(a)
The positions of beacons
(b)
The reference positionsTo build a usable training fingerprint, RSSI data is recorded for 200 seconds at each reference position. And Kalman filter [29] is used to preprocess RSSI data.Considering that a person may move fast with a cell phone, we just use one vector of RSSI data for positioning. In this paper, 74 testing positions are used in our experiment. These positions are distributed evenly with one-meter distance in the6
×
18
m
2 experimental area.


## 4.2. Selection ofM and m
′

In Isomap algorithm,M and m
′ are important parameters, which are the count of nearest neighbors and dimension of low-dimensional embedding. To select a proper M and m
′, some experiments are carried out firstly.Table1 shows the positioning errors with different M. As can be seen from the table, when M is between 15 and 21, the maximum and mean positioning errors are relatively small and stable. According to our experiment, the proposed method achieves minimum mean error when M
=
20.Table 1
The positioning errors with differentM.
M
Max error (m)
Mean error (m)
Min error (m)
Std error (m)
3
4.991
1.668
0.026
0.919
4
5.389
1.657
0.230
1.006
5
5.086
1.620
0.093
0.952
6
3.851
1.796
0.473
0.907
7
4.112
1.723
0.326
0.828
8
4.278
1.910
0.335
0.953
9
4.317
1.936
0.027
1.056
10
3.400
1.865
0.078
0.818
11
5.187
2.037
0.424
1.094
12
5.806
1.983
0.389
1.148
13
4.290
1.942
0.377
1.009
14
5.388
1.938
0.292
0.971
15
3.814
1.672
0.278
0.791
16
3.815
1.592
0.303
0.775
17
3.528
1.635
0.334
0.726
18
4.516
1.732
0.297
0.841
19
3.602
1.635
0.331
0.864
20
3.605
1.516
0.001
0.782
21
3.600
1.618
0.117
0.776
22
4.601
1.655
0.350
0.976
23
4.590
1.622
0.345
0.934
24
4.902
1.633
0.345
0.982Table2 shows the mean positioning error with different M and m
′. M is assigned between 15 and 21. m
′ varies from 2 to 15. In this table, we can find that when m
′ is between 4 and 6, the mean positioning error is relatively small.Table 2
The mean positioning error with differentm
′.
m
′
/
M
15
16
17
18
19
20
21
2
1.778
1.772
1.957
1.807
1.895
2.004
1.920
3
1.856
1.710
1.811
1.735
1.680
1.801
1.712
4
1.770
1.744
1.687
1.663
1.601
1.573
1.529
5
1.672
1.592
1.635
1.732
1.635
1.516
1.618
6
1.625
1.523
1.712
1.736
1.657
1.597
1.617
7
1.741
1.600
1.705
1.703
1.761
1.675
1.609
8
1.751
1.585
1.703
1.783
1.614
1.731
1.594
9
1.770
1.695
1.718
1.843
1.639
1.730
1.593
10
1.778
1.686
1.666
1.825
1.672
1.682
1.606
11
1.785
1.676
1.718
1.823
1.749
1.695
1.559
12
1.764
1.618
1.722
1.776
1.665
1.646
1.584
13
1.742
1.577
1.695
1.761
1.630
1.635
1.592
14
1.736
1.633
1.697
1.755
1.653
1.675
1.615
15
1.745
1.638
1.674
1.741
1.678
1.702
1.606According to these experiments, we setM
=
20 and m
′
=
5 in this paper.


## 4.3. The Effectiveness of Isomap

The effectiveness of Isomap is firstly examined in our Bluetooth localization experiment. We compare the performance of WKNN and EWKNN [16] and their Isomap enhanced versions. WKNN is separately tested with K
=
3,4
,
…
,
9. And the threshold of EWKNN is mean of distance vector.Figure7 shows the error distribution of different methods. In Figure 7, the first-column figures illustrate the error distributions of original methods. The second column shows the error distribution of Isomap enhanced methods. The third column shows the differences of original and Isomap enhanced methods. From Figure 7, we can find that the error distribution of developed Isomap enhanced methods (IWKNN and IEWKNN) is more concentrated in the low error region than original methods (WKNN and EWKNN).Figure 7
Error distributions of original and Isomap enhanced methods.Figure8 illustrates the cumulative probability of error distribution for different methods. The curves in these figures demonstrate that the Isomap enhanced methods (IWKNN and IEWKNN) achieve better performance than original methods (WKNN and EWKNN).Figure 8
Cumulative error distribution of original and Isomap enhanced methods.
(a)
WKNN and IWKNN (K
=
3)
(b)
WKNN and IWKNN (K
=
4)
(c)
WKNN and IWKNN (K
=
5)
(d)
WKNN and IWKNN (K
=
6)
(e)
WKNN and IWKNN (K
=
7)
(f)
WKNN and IWKNN (K
=
8)
(g)
WKNN and IWKNN (K
=
9)
(h)
EWKNN and IEWKNNFinally, the performance of all tested methods is given in Table3. According to this table, Isomap almost improves all of positioning indicators clearly. The best values of important indicators are given in bold font. The minimum of max error is 4.994, which is obtained by IWKNN with K
=
9. The minimum of mean error is 1.463, which is obtained by IWKNN with K
=
4. The minimum of min error is 0.0005, which is obtained by IWKNN with K
=
3 and IEWKNN. The minimum of std error is 0.674, which is obtained by IWKNN with K
=
7. The maximum of “ratio of error less than 2 meters” is 78.96
%, which is obtained by IWKNN with K
=
5. This table supports the effectiveness of proposed Isomap enhanced positioning methods.Table 3
The positioning error of original and Isomap enhanced methods.
Method
Max error (m)
Mean error (m)
Min error (m)
Std error (m)
≤2 m (%)
WKNN(
K
=
3
)
7.000
1.505
0.0008
0.772
73.99%
IWKNN(
K
=
3
)
5.046
1.481
0.0005
0.758
75.58%
WKNN(
K
=
4
)
6.558
1.508
0.001
0.732
74.49%
IWKNN(
K
=
4
)
7.110
1.463
0.002
0.710
76.05%
WKNN(
K
=
5
)
6.803
1.541
0.014
0.712
76.12%
IWKNN(
K
=
5
)
6.162
1.478
0.036
0.693
78.96%
WKNN(
K
=
6
)
6.045
1.581
0.002
0.707
71.45%
IWKNN(
K
=
6
)
5.216
1.512
0.011
0.680
77.08%
WKNN(
K
=
7
)
5.774
1.631
0.023
0.703
69.18%
IWKNN(
K
=
7
)
5.273
1.558
0.041
0.674
74.27%
WKNN(
K
=
8
)
5.135
1.689
0.023
0.721
65.50%
IWKNN(
K
=
8
)
5.138
1.604
0.066
0.683
70.77%
WKNN(
K
=
9
)
5.447
1.749
0.019
0.739
61.51%
IWKNN(
K
=
9
)
4.994
1.660
0.032
0.703
67.14%
EWKNN
7.000
1.502
0.002
0.756
74.26%
IEWKNN
5.046
1.477
0.0005
0.743
76.04%According to Table3, we suggest K
=
4 or 5 for small mean positioning error and large “ratio of error less than 2 meters.”


## 4.4. Comparison with Different Methods

In order to test the performance of proposed method more clearly, we compare the proposed IWKNN (K
=
4) with six different positioning methods.Figure9 compares the performances of different methods. From this table, we can see that Bayes method has the best performance in the low error part, and the proposed IWKNN performs best in almost all the remaining part.Figure 9
The cumulative error distribution of different methods.Table4 illustrates the positioning error of different methods. According to this table, GMM, Bayes, and WKNN-Bayes’s max errors are better than other methods. But the improved Bayes method proposed by Fras et al. [20] can generate small max, mean, and std errors. The proposed IWKNN has the minimal mean error and maximal “ratio of error less than 2 meters.”Table 4
The positioning error of different methods.
Method
Max error (m)
Mean error (m)
Min error (m)
Std error (m)
≤2 m (%)
Triangulation
11.443
2.592
0.0288
1.616
41.80%
IoT [12]
7.576
3.077
0.0331
1.482
27.72%
GMM [21]
12.880
3.506
0
1.965
65.03%
Bayes
14.318
2.391
0
1.611
44.46%
WKNN-Bayes [20]
8.062
2.031
0
1.116
53.42%
WKNN
6.558
1.508
0.001
0.732
74.49%
IWKNN
7.110
1.463
0.002
0.710
76.05%


## 5. Conclusion

This paper presents an Isomap enhanced localization method IWKNN. The proposed method combines Isomap and WKNN for Bluetooth positioning. Firstly, we calculate low-dimensional embeddings for RSSI data by Isomap. Then, the distance of different RSSI vectors is measured by Euclidean distance of these low-dimensional embeddings. Finally, the unknown testing position is calculated by WKNN. Experiment indicates the distances of low-dimensional embeddings are more robust than those of high-dimensional ones. And the proposed IWKNN is robust and effective.The main contribution of this paper could be concluded as follows:(
1
) introduce Isomap to Bluetooth positioning problem; (
2
) use low-dimensional embeddings to represent high-dimensional RSSI data; (
3
) adopt distances of low-dimensional embeddings to measure the distance of RSSI vectors; (
4
) combine Isomap with WKNN for Bluetooth positioning.



---

*Source: 8765874-2016-11-30.xml*