A Sliding Window Fusion Location Algorithm
Based On WI-FI/PDR
Ning-Xin ZHOU ⋆ Xin-Yue FAN Peng-Cheng XIA Fei ZHOU
Chongqing Key Laboratory of Optical Communication and Networks, Chongqing
University of Posts and Telecommunications, Chong Qing, China.
Abstract. In order to improve the accuracy of indoor localization, this
paper presents a fusion positioning algorithm using the sliding window
method based on Wi-Fi and PDR. The algorithm can not only provide
the user’s initial position accurately, but also correct the position error of
the indoor turning points, so it can correct the cumulative error generated
by PDR and improve the positioning accuracy. The experiment results
show that the average localization error of the proposed algorithm is
lower than Wi-Fi ngerprinting approach and PDR approach. At the
same time, the error of turning point has been greatly corrected.
Keywords: Wi-Fi PDR Fusion Position Initial Location
1
Introduction
With the rise of location-based services (LBS), the demand for indoor position-
ing is becoming more and more intense. The global positioning system (GPS) [3]
does not apply to indoor complex environment [1]. With the popularity of wire-
less local area network (WLAN) in the indoor environment, Wi-Fi RSS-based
indoor positioning technology has become a research hotspot. The concept of
location fingerprint was proposed by the RADAR system of Microsoft Research
Institute firstly [2], which is based on the received signal strength indication
(RSSI) method, and use k-nearest neighbor (KNN) algorithm [7]-[8] to improve
the positioning accuracy. However, due to the complex indoor environment and
the volatility of the RSSI signal, the positioning accuracy of indoor positioning
technology based on Wi-Fi is not high. With the popularity of smart phones,
the Pedestrians Dead Reckoning (PDR) [6] method using inertial sensor is also
used for indoor positioning. But this method can produce accumulative error.
Therefore, researchers have proposed a new method based on the fusion of Wi-Fi
and PDR. In [4], an intelligent fusion algorithm is proposed, which uses the data
of Wi-Fi and PDR to accurately determine the initial position of the user, thus
⋆ Z. Zhou, X. Fan, P. Xia, F. Zhou are with the Key Laboratory of Optical
Communication and Networks, School of Communication and Information Sys-
tem, Chongqing University of Posts and Telecommunications, 400065, Chong
Qing,
(e-mail: zhou-ning-xin@foxmail.com; fanxy@cqupt.edu.cn;
xiapengcheng1205@foxmail.com; zhoufei@cqupt.edu.cn.)
China.
2
Ning-Xin ZHOU Xin-Yue FAN Peng-Cheng XIA Fei ZHOU
it can avoid the positioning error produced by the inaccurate positioning of the
initial position. However, the method is more complicated and it needs many
data. In [5], a segmented fusion localization algorithm is proposed, which uses
a fixed size window to integrate the data of Wi-Fi and PDR, so it can improve
positioning accuracy conveniently. However, because the window size cannot be
changed during the process of localization, the positioning error of turning point
is still large.
Therefore, aiming at the shortage of the above algorithms in these literatures,
this paper proposes a sliding window algorithm. The algorithm can conveniently
and accurately determine the initial position of the user, and then uses a variable-
size sliding window method, which effectively reduces the positioning error from
the turning point and effectively improve the overall accuracy.
2 Related Work
2.1 RSS-based Fingerprinting Method
Currently, the most pervasive solution for Wi-Fi RSS-based positioning is the
wireless fingerprinting scheme. In this paper, we use K-nearest neighbor (KNN)
algorithm to calculate the Euclidean distance with the average RSS value in
offline phase:
dj =
(RSSi RSSji)2
j = 1; 2; :::; n
(1)
vuut m∑
i=1
The next step is finding the K minimum distances as the nearest neighbors.
The user’s location is calculated as follows:
(xi; yi)
i=1
(2)
k∑
(bx;by) =
1
k
xk = x0 +
yk = y0 +
k−1∑
k−1∑
k=1
2.2 PDR Method
Modern smartphones are equipped with inertial measurement units (IMUs).
Pedestrian dead reckoning method use IMUs to track or position. When the
user’s initial position I0 = (x0; y0) has been known, the user’s location is calcu-
lated as follows:
dk sin k
dk cos k
(3)
Where dk represents the length of each step, k denotes the heading direction
of the k-th step.
k=1
A Sliding Window Fusion Location Algorithm
3
3 Fusion Algorithm
3.1
Initial Location
The initial location estimated by the RSS-based Wi-Fi positioning system may
be inaccurate. The PDR system cannot provide initial location. Hence, a new
method is proposed in this paper to determine the user’s initial location.
(a)
(b)
Fig. 1. Determination of the initial location
w and L(2)
Refer to Fig.1. When L(1)
w are estimated and if L(1)
w , l1, l2
can be estimated accurately, we can infer that the initial location of the user
is located at the circumference with the center L(1)
w and radius l1. We can also
infer that the initial location of the user is located at the circumference with the
center L(2)
w and radius l2. We can infer the initial moving direction based on the
distribution of the Wi-Fi positioning results. A linear regression model is used
to find a linear regression line, which can be used to represent the users moving
tendency. Let the linear regression function be:
w ,L(2)
A = (m; n) = arg min
m,n
h=1
The intersection of the two circles and the linear regression line is the initial
position I = (m; n).
If L(1)
w ,L(2)
w ,l1,l2 can not be estimated very accurately, we make a perpendicu-
lar line from the intersection of two circles to the linear regression line. The foot
N∑
N∑
i=1
(
i=1
a =
b =
N (
x(i)
w y(i)
y = ax + b
N∑
N∑
y(i)
w )
N∑
i=1
2
i=1
2
x(i)
w )
x(i)
w )(
N∑
i=1
i=1
x(i)
w )(
w )−(
N∑
N∑
N∑
w )−(
x(i)2
w )−(
N∑
N∑
y(i)
{
√(
w )−(
x(i)2
m x(h)
N (
i=1
i=1
i=1
i=1
w
x(i)
w )
)2
+
N (
i=1
x(i)2
w )(
2∑
(4)
(5)
(6)
w y(i)
x(i)
w )
(
n y(h)
w
)2 lh
}
InitialPosition1wL2wL1NwLNwL1l2lInitialPosition1wL2wL1NwLNwL1l2lIntersectionPoint
4
Ning-Xin ZHOU Xin-Yue FAN Peng-Cheng XIA Fei ZHOU
of the perpendicular is the initial position. The initial location can be calculated
as:
I=(x0; y0) = (
m + an ab
;
am + a2n + b
a2 + 1
a2 + 1
)
(7)
3.2 Sliding Window Fusion Algorithm
In addition to the cumulative error generated by the PDR system, the indoor
corners are prone to produce large errors relative to other approximate straight-
line. In this paper, a sliding window fusion algorithm is proposed, which can
reduce the error at the corner and improve the positioning accuracy. The specific
method is as follows:
Step 1: Set the step number n to zero. The initial location I=(x0; y0) has
been calculated in 3.1 section. Set the size of the window as p and the sliding
interval as q.
Step 2: The user’s position result of RSS-based fingerprinting method at the
step n is labeled as Iw = (xw; yw). The result of PDR system is marked with
Ipdr = (xpdr; ypdr).
(
Step 3: The fusion of the PDR results and fingerprinting results. The user’s
position result of the presented fusion scheme at the step n is marked with
I n = (xn; yn). The details of the fusion process is described as follows:
(1): For step n (n = 1; ; p 1),I n=Ipdr.
(2): For step n (n = p; ; p + q 1). Assume that the average of fingerprint-
)
)
. The middle step of the fusion
ing results in the first window is I (1)
result in the first window is I (1)
step in the first window is I (1)
I (1)
i
range mi(1). The equations are as follows:
a ; y(1)
x(1)
a
m ; y(1)
x(1)
m
x(1)
; y(1)
i
. The previous step of the medium
. The distance between I (1)
is denoted by range ai(1). The distance between I (1)
m and I (1)
(
(
is denoted by
i =
m =
a =
)
and
a
i
i
x(1)
a =
xn
w y(1)
a =
yn
w
1
p
p−1∑
√(
√(
n=0
1
p
p−1∑
(
(
n=0
)2
)2
)2
)2
range ai(1)=
a x(1)
x(1)
m x(1)
x(1)
Then, the weighting coefficients as follows:
range mi(1)=
i
i
+
+
i
a y(1)
y(1)
m y(1)
y(1)
i
Hence, the new initial position in the first window is updated as:
1=range ai(1)
1=range ai(1) + 1=range mi(1)
K (1) =
x(1)
ini =
y(1)
ini =
(
(
1 K (1)
1 K (1)
) x(1)
) y(1)
m + K (1) x(1)
m + K (1) y(1)
a
a
(8)
(9)
(10)
(11)
(12)
A Sliding Window Fusion Location Algorithm
5
Then, we can calculated the function algorithm positioning results of the step
n∑
n (n = p; ; p + q 1) as follows:
n∑
xn = x(1)
ini +
v=2
yn = y(1)
ini +
v=2
dv sin v; n = p; ; p + q 1
dv cos v; n = p; ; p + q 1
(13)
(3): To determine the heading angle. If the heading angle is 60
◦ 180
◦
,
change the size of p and q.
p = p 2i
i = 1; 2; ; n
q = q h h = 1; 2; ; n
(14)
Otherwise the size of p and q does not change.
Step 4: After achieving the fusion positioning result of the step n, the window
slides q steps in the direction of movement. Then, repeat Step 3 to calculate the
other window data until the user stops.
Fig. 2. Example of sliding window
4 Experiments and Analysis
We choose the ninth floor of Information and Technology Building in Chongqing
University of Posts and Telecommunications as our experiment area, as shown
in Figure.3.
To evaluate the performance of fusion algorithm, we compare the fusion al-
gorithm with the PDR approach and Wi-Fi RSS-based fingerprinting approach.
The positioning error is the distance between the estimated location and the real
location. The positioning error is calculated as:
√(
)2
(
)2
y ∼
y
pos error =
x ∼
x
+
(15)
Fingerprinting positioning resultSliding window
6
Ning-Xin ZHOU Xin-Yue FAN Peng-Cheng XIA Fei ZHOU
Fig. 3. True Path
Refer to Fig.3. The blue line represents the true path, and the red dot rep-
resents turning point. In our experiment, the size of window is set to 7, 7/3, 5
and 5/3, which represent the four parameters of positioning simulation.
(a) Path 1
(b) Positioning error
Fig. 4. Comparison of PDR and fusion algorithm when the size of window is 5
Refer to Fig. 4. When the size of window is 5, we can find that the method
proposed in this paper can correct the cumulative error generated by PDR and
can correct the deviated track.
COMPARISON OF MEAN DISTANCE ERRORS IN THREE METHOD
TABLE I
Method
Fusion Position
Mean distance error(m)
1.28
PDR
2.07
Wi-Fi
3.72
Table 1 shows the average position errors of different methods in Path 1.
Compared with the others, the proposed algorithm reduces the average posi-
tioning error by about 38% 65%.
AP1AP2AP3AP412Turning Point 1Turning Point 3Turning Point 4Turning Point 5Turning Point 20510152025012345678910(m)(m)The size of sliding window is 5 Initial locationProposed algorithmTrue pathPDR05101520253000.511.522.533.54Sequence number of tested pointsError of every point(m)Positioning error of the two methods PDRproposed algorithm
A Sliding Window Fusion Location Algorithm
7
(a) Path 2
(b) Positioning error
Fig. 5. Comparison of PDR and fusion algorithm when the size of window is 5/3
As shown in Fig.4 and Fig.5, once the size of the sliding window reduces
from 5 to 3 near the turning point, the positioning error near the turning point
is obviously decreased and the deviated track is corrected more obviously.
COMPARISON OF TURNING POINT POSITION ERROR (M) ABOUT FOUR SIZE
OF WINDOW
TABLE II
point1
point2
point3
point4
point5
Average
Position
Error
size 7
size 7/3
size 5
size 5/3
1.92
1.72
1.66
0.41
0.76
0.77
0.61
0.53
1.03
0.77
0.85
0.66
1.49
0.15
0.61
0.31
1.83
0.52
1.26
0.70
1.28
0.76
1.20
0.50
As shown in Table 2, when the size of window is set to 7, the average position
error of the proposed method is 1.28m. Then we reduce the overall size of the
sliding window from 7 to 5, but it cannot effectively improve the positioning
accuracy. According to the proposed method, the size of window reduces to 3
near the turning points, and it reduces the average position error by about 41%,
which can obviously show that the variable-size sliding window method can
correct the position error of the indoor turning points. So the proposed method
can correct the cumulative error generated by PDR and improve the positioning
accuracy.
5 Conclusion
In this paper, we propose a sliding window algorithm which fuses the positioning
information of PDR system and Wi-Fi fingerprint database to estimate the user’s
05101520012345678910(m)(m)The size of sliding window is 5/3 Initial locationProposed algorithmTrue pathPDR05101520253000.511.522.533.54Sequence number of tested pointsError of every point(m)Positioning error of the two methods PDRproposed algorithm
8
Ning-Xin ZHOU Xin-Yue FAN Peng-Cheng XIA Fei ZHOU
position and reduce the error at the turning point, so as it can eliminate the
cumulative error and reach the stable and continuous positioning trajectory.
To demonstrate the effectiveness of the proposed algorithm, the experiments
were on the ninth floor of Information and Technology Building in Chongqing
University of Posts and Telecommunications. The experiment results show that
the sliding window algorithm can effectively reduce the error at the turning point,
correct the cumulative error of PDR and improve the positioning accuracy and
stability.
Acknowledgments. This work was supported by the National Natural Science
Foundation of China (61471077).
References
1. Agarwal, N., Basch, J., Beckmann, P., Bharti, P., Bloebaum, S., Casadei, S., Chou,
A., Enge, P., Fong, W., Hathi, N., Mann, W., Sahai, A., Stone, J., Tsitsiklis, J.,
Van Roy, B.: Algorithms for gps operation indoors and downtown. GPS Solutions
6(3), 149{160 (2002)
2. Bahl, P., Padmanabhan, V.N.: Radar: an in-building rf-based user location and
tracking system. In: INFOCOM 2000. Nineteenth Joint Conference of the IEEE
Computer and Communications Societies. Proceedings. IEEE. pp. 775{784 vol.2
(2000)
3. Capkun, S., Hamdi, M., Hubaux, J.P.: Gps-free positioning in mobile ad hoc net-
works. Cluster Computing 5(2), 157{167 (2002)
4. Chen, L.H., Wu, H.K., Jin, M.H., Chen, G.H.: Intelligent fusion of wi- and inertial
sensor-based positioning systems for indoor pedestrian navigation. Sensors Journal
IEEE 14(11), 4034{4042 (2014)
5. Hu, Y., Liao, X., Lu, Q., Xu, S., Zhu, W.: A segment-based fusion algorithm of
wi ngerprinting and pedestrian dead reckoning. In: 2016 IEEE/CIC International
Conference on Communications in China (ICCC). pp. 1{6 (July 2016)
6. Kourogi, M., Ishikawa, T., Kurata, T.: A method of pedestrian dead reckoning using
action recognition. In: Position Location and Navigation Symposium. pp. 85{89
(2010)
7. Peterson, L.: K-nearest neighbor. Scholarpedia 4(2) (2009)
8. Tran, Q., Tantra, J.W., Foh, C.H., Tan, A.H., Yow, K.C., Qiu, D.: Wireless indoor
positioning system with enhanced nearest neighbors in signal space algorithm. In:
Vehicular Technology Conference, 2006. Vtc-2006 Fall. 2006 IEEE. pp. 1{5 (2006)