Proceedings of The 23rd World Multi-Conference on Systemics, Cybernetics and Informatics (WMSCI 2019)

Construction and Management of Fingerprint
Database with Estimated Reference Locations for
WiFi Indoor Positioning Systems
Myat Hsu Aung, Hiroshi Tsutsui, and Yoshikazu Miyanaga
Graduate School of Information Science and Technology, Hokkaido University
Kita 14, Nishi 9, Kita-ku, Sapporo, Hokkaido 060-0814, JapanA BSTRACT

ment signal such as received signal strength (RSS), time ofarrival (TOA), and time difference of arrival (TDOA) from
WiFi devices [6, 9]. In our previous work [10], we proposeda fingerprint method based IPS using estimated reference
locations. In case of fingerprint based IPS, the informationof access points (APs) reachable from the user’s location isused for estimating the user’s location by comparing it withthe pre-stored data in the database. Such user’s information
is called a fingerprint. As for the database, since we need tostore the information of APs reachable from a lot of knownreference locations, this database creation requires a significant
cost. Focusing on the difficulty of database creation, we aretrying to develop a method to create the database of reference
point information which does not require precise reference
point locations.
In our previous paper, the propose method when the fingerprint database is created using received signal strength
indicator (RSSI) values, there are some problems in accuracy
to estimate the device position. Because RSSI values fluctuatewith various effects such as spatial and temporal variations ofinterference, hardware variations, and environmental effects
such as human presences [11]. Another difficulty is that the
database depends on the APs, which means new installations
and replacements of APs have a significant impact on theestimation accuracy. Considering these issues, not only the
database creation but also how to manage the database after
the database creation is essential.
In this paper, we focus on the database creation of WiFi
based IPS using estimated reference locations. We are trying tocreate the fingerprint database with multiple data sets from two
devices that contain the different sampling points in different
data collection day. The multiple data sets are merged to create
the single database. In the proposed method, we use the meanshift clustering algorithm [12] to get merged reference points
from the multiple data sets. We present the accuracy evaluationof the proposed system with different types of database which
are constructed by all data set of each day and each device,
and all data set of both device from different data collectionthat includes and excludes the testing data.

In this paper, we propose a positioning system for indoor
environments based on WiFi fingerprint methods. In fingerprint methods, the database construction is important for the
position estimation performance. We created the fingerprint
database by gathering pairs of media access control (MAC)
addresses and received signal strength indicator (RSSI) at
each estimate reference location. In this proposed method,reference devices are moving at a constant speed with a simple
direction that can be estimated the location of each reference
point. The multiple data sets are collected in same areas tocreate the fingerprint database. The location of reference points
are slightly different with each other. We use the mean-shift
clustering algorithm to get merged reference points from themultiple data sets. We manage to update the database using theuser’s input data in different time duration. We created fourtypes of fingerprint database and evaluated the user’s position
estimation. The results show that the user’s position can be
estimated with an average accuracy error of 1.8 m.
Keywords: WiFi indoor positioning, Fingerprint, Received
signal strength (RSS), and Mean-shift clustering
1. I NTRODUCTION
Recently, positioning systems have become indispensable
not only for navigation and tracking but also for various
location-based applications. The global positioning system(GPS) is most popular and suitable technology for outdoor
positioning system. However, the large error occurs in indoor
environment because the GPS signal becomes weak when they
penetrate the construction materials [1]–[4]. The accuracy ofindoor positioning remains the greatest challenges in real-time
applications. Also, a flexible and low-cost indoor positioning
system is highly demanded. For indoor positioning systems(IPS), RF signals from wireless devices such as WiFi, Bluetooth, and radio frequency identification (RFID) devices canbe utilized to estimate mobile device positions [5]–[8]. Amongthem, we focus on the most cost-effective method that is WiFibased IPS since the WiFi coverage is getting higher due tothe significantly increasing number of private or public WiFi
access points in metropolitan areas.
There are various position algorithms in WiFi-based IPS
such as trilateration and fingerprinting that are using measure-

2. P ROPOSED FINGERPRINT METHOD
The proposed approach estimates user locations based on
fingerprint methods utilizing WiFi signal strength measure-7

Proceedings of The 23rd World Multi-Conference on Systemics, Cybernetics and Informatics (WMSCI 2019)

for each merged reference point i0 are calculated by averaging
RSSI values of the reference points in the corresponding meanshifted cluster. Let us denote the set of MAC-RSSI
pairs for
merged reference point i0 by Pi0 = Mi0 , Ri0 . The list of theset of merged reference points Pi0 is stored in the database as
P . Note that the number of merged reference points i0 depends
on the thresholds parameter r to calculate means in the meanshift algorithm.

Database construction (offline phase)
Data collection
Mean-shift
AP1{{M11,R11},{M12,R12},...} clustering Fingerprint databasealgorithm
AP
2{{M21,R21},{M22,R22},...}

AP3{{M31,R31},{M32,R32},...}

Constant speed

Application Screenshot

M1, R1
M2, R2
M3, R3

Location Estimation
In the following, we explain our location estimation approach. This approach is same as our previous paper [10].
In the user position localization part, user’s mobile device
samples the MAC address and the RSSI value of each AP
available from the current user’s position. This sample can bedenoted by using the similar notation as follows,• the set of MAC addresses at the user’s position u:
Mu = {Mu1 , Mu2 , . . . , MuNu },where Nu is the number of available access points,• the RSSI values paired with Mu :Ru = {Ru1 , Ru2 , . . . , RuN }, and,• the set of MAC-RSSI pairs at the user’s position:Pu = Mu , Ru .
This Pu is the input of the position estimation algorithm andthe algorithm estimates user’s location by using Pu and P .
Note that P is the database. The procedure of the user’s
position estimation is the following.
(1) Pick up reference points which include at least one MAC
address of user’s input and create the set of such reference
points. This set is described by(1)
S = i Mu ∩ Mi 6= ∅ .

Reference Point

User's Input Data{{Mu1,Ru1},{Mu2,Ru2},{Mu3,Ru3},...}

Position estimation algorithm
Find best matching fingerprint

User position localization (online phase)

Estimated position

Fig. 1: The overview of the proposed system.
ment. Figure 1 shows the overview of the proposed system.
The total system consists of a database construction part
(offline phase) and a user position localization part (online
phase). In the offline phase, RSSI values from available APs
are collected at each specific position in target area. Such
positions are called reference points. The collected RSSI
values for each reference point is stored in a fingerprint
database. In the online phase, the real-time position of a user
is estimated using the input set of current RSSI values that arecollected by the user’s mobile device and compared with thosein the fingerprint database using location estimation algorithm.
Construction of fingerprint database(2) Create the list of unique MAC addresses included theabove set of reference points. which is related to the input
data.
[
M0 =
Mi
(2)

First using WiFi scanning Android application, the training
data for database construction are collected in the target areathat include pairs of media access control (MAC) addresses
and RSSI values which can be obtained from reachable APs
for each reference point. These MAC-RSSI pairs are gathered
every specific period such as one second with walking at aconstant speed to estimate the actual location of each reference
point. The absolute timestamps for each pair is also collected.
The locations where MAC-RSSI pairs are sampled can be
regarded as reference points for each data set. As a result,a set of pairs of MAC addresses and RSSI values for eachreference point is stored as a fingerprint in the database.
Let the set of MAC addresses Mi = {Mi1 , Mi2 , . . . , MiNi }for reference point i, where the number of access points
available at reference point i is given by Ni . The RSSI values
paired with Mi is denoted by Ri = {Ri1 , Ri2 , . . . , RiNi }. We
denote the set of MAC-RSSI pairs for reference point i by
Pi = Mi , Ri .
In this proposed approach, multiple data sets are used tocreate the database that are collected same area but different
sampling rate due to speed change. The multiple data sets
are merged using mean-shift clustering algorithm. The list of
MAC-RSSI pairs for the reference point i from multiple data
sets can get using mean-shift clustering algorithm. RSSI valuesi∈S(3) Create location vector, that is, fingerprint, for user’s input
and references points selected in step (1). The location
vector is given as the RSSI values list for corresponding
MAC address list created in step (2). If no RSSI value isavailable for a MAC address, the element is set ∅.
(Ruj if Mj0 ∈ Mu
Vu = {Vuj }, Vuj =(3)∅otherwise
where Mj0 ∈ M 0 . Similarly, as for selected references
points, the location vectors are created by(
Rij if Mj0 ∈ Mi
Vi = {Vij }, Vij =(4)∅otherwise
where Mj0 ∈ M 0 and i ∈ S.
(4) Calculate vector distances Dui between user’s input vector
Vu and all reference vectors Vi .
(5) Output the position û = argmini Dui as the estimateduser’s position.

8

Proceedings of The 23rd World Multi-Conference on Systemics, Cybernetics and Informatics (WMSCI 2019)

Error
Lower limit

Error
Lower limit

0.4
0.2
0
-0.2
-0.4

Error
Lower limit

0.4
0.2
0
-0.2
-0.4
0

0.2 0.4 0.6 0.8
Normalized position

10(a) Condition A.

0.2 0.4 0.6 0.8
Normalized position

1

Error
Lower limit0

0.2 0.4 0.6 0.8
Normalized position

Error
Lower limit

10

0.2 0.4 0.6 0.8
Normalized position

10(a) Condition A.

0.2 0.4 0.6 0.8
Normalized position

Error
Lower limit

1

Error
Lower limit
0.4
0.2
0
-0.2
-0.4

0

0.2 0.4 0.6 0.8
Normalized position(c) Condition C.

1(b) Condition B.
Error
Lower limit0

0.2 0.4 0.6 0.8
Normalized position

10

0.2 0.4 0.6 0.8
Normalized position

1(d) Condition D.

slow 2, fast and reverse for each device and each day, resulting
16 data sets in total. Note that the shape of the walking path
is a rectangle and that the starting point and the end point issame. The walking distance is about 120 m.
In the fingerprint database creation, all data sets are mergedusing mean-shift clustering algorithm to create the database.
The number of samples are different with each other due to
speed change. Therefore, timestamp normalization is required.
Assuming that the number of samples is Nk in an obtained
data set and that the timestamp of each sample is given by tk ,k = 0, 1, . . . , N − 1, the normalized timestamp is given by,tk − t0, k = 0, 1, . . . , Nk − 1.
(5)
Lk =tNk −1 − t0(b) Condition B.

0.4
0.2
0
-0.2
-0.4

1

Fig. 4: Evaluation 3 results.

Error
Lower limit

1

0.2 0.4 0.6 0.8
Normalized position(c) Condition C.

0.4
0.2
0
-0.2
-0.4
0.2 0.4 0.6 0.8
Normalized position

0.2 0.4 0.6 0.8
Normalized position

0.4
0.2
0
-0.2
-0.4
0

(d) Condition D.

Error
Lower limit

0

Error
Lower limit

Fig. 2: Evaluation 1 results.

0

1

0.4
0.2
0
-0.2
-0.4

(c) Condition C.

0.4
0.2
0
-0.2
-0.4

0.2 0.4 0.6 0.8
Normalized position(a) Condition A.

0.4
0.2
0
-0.2
-0.4
0

0.4
0.2
0
-0.2
-0.4

(b) Condition B.

0.4
0.2
0
-0.2
-0.4

Error
Lower limit

0.4
0.2
0
-0.2
-0.4

Note that L0 = 0, LNk −1 = 1, and 1 corresponds to 120 m.
Lk is regarded as the estimated reference point location.
The user’s position is estimated by the WiFi-based positioning
approach based on these estimated reference points.
We created four types of database to test data sets. We
denote these types as Conditions A, B, C, and D as listed
below.
Cond. A uses all data sets including a test input data set,
Cond. B uses all data sets excluding a test input data set,
Cond. C uses data sets from same device for test, andCond. D uses data sets from the other device for test.
We denote three types of evaluation in Figs. 2, 3, and 4
as listed below.
Evaluation 1 uses 8 data sets including a test input data set
in the day 1,
Evaluation 2 uses 8 data sets except one used as a test input
data set in day 2,
Evaluation 3 uses all 16 data sets including test input data,
andThe types of the databases and their accuracy evaluation results
are shown in Table I. In this table, the data set number 1 to 81(d) Condition D.

Fig. 3: Evaluation 2 results.

3. E XPERIMENTAL RESULTS
In our previous research, we developed an Android application which gathers MAC-RSSI pairs of available APs every
specific period aiming database construction and location
estimation algorithm development. By using this application,
data were collected on the 11th floor of Graduate Schoolof Information and Science Technology Building, Hokkaido
University. In this experiment, we used two Android devices,(A) HTC One (M7) and (B) Nexus 7 (2013). The data isgathered by walking at constant slow speed (slow 1 and slow2), a faster speed, and in the reverse direction. Considering
the effect of APs which are replaced new one, we collected
the information of the reachable APs in reference point indifferent two days. We obtained 4 data sets that are slow 1,

9Proceedings of The 23rd World Multi-Conference on Systemics, Cybernetics and Informatics (WMSCI 2019)

TABLE I: Database types and their accuracy evaluation results.
Normalized error
Condition
Data sets used to create the database
Ave error
Max error
Cond. A
1
2
3
4
5
6
7
8
0.018
0.147
Cond. B
1
3
4
5
6
7
8
0.019
0.217
1
Cond. C
1
2
3
4
0.017
0.234
Cond. D
5
6 7
8
0.033
0.175
Cond. A
9
10
11
12
13
14
15
16
0.017
0.093
Cond. B
9
11
12
13
14
15
16
0.017
0.214
2
Cond. C
9
10
11
12
0.015
0.224
Cond. D
13
14
15
16
0.043
0.486
Cond. A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0.015
0.106
Cond. B
1
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0.015
0.107
3
Cond. C
1
2
3
4
9
10
11
12
0.012
0.108
Cond. D
5
6 7
8
13
14
15
16
0.035
0.208
In this table to show the valuations of our evaluations, we assume that data set 2 is used for testing.
The average error values are averaged ones over all tests while the maximum error values are maximum values of all tests.
Evaluation

are colleced in day 1, and 9 to 16 are in day 2. The data set 2 isused for testing for all types of database for exemplifying theconditions in the table. The average error values are averaged
over all tests while the maximum values are maximum valuesof all tests.
Figs. 2, 3, and 4 show the normalized errors of testing data
set 2 for different condition of database creation. As for themean-shift parameter of r, we used 0.01 of normalized timestamps considering the number of obtained reference points foreach data set. Note that, in these figures, the lower limit errors
due to the discrete reference points are also included.
We summarize the averaged and maximum normalized
error for each condition as follows. As for Evaluation 1, thenormalized error of Condition A (includes the testing data)
is smaller than Condition B (excludes the testing data). The
average error of Condition D is larger than Condition B due
to the different device to testing data. In Evaluation 2, thedatabase is created form the data of different day to thetesting data. As we can see from the table, similar results
are obtained to those of Evaluation 1. Evaluation 3 results
show the accuracy where the combination of data sets fromtwo days data collection is used to create the database. As
for Conditions A and B in Evaluation 3, the average error
is 0.015 in the normalized error, which corresponds to about
1.8 m. Condition B shows the large maximum error since
the database does not contain the user’s input data set. In
Condition D, it can be seen that the user’s position error islarger than the other. This is because the database is createdfrom the different device from that for testing data. As results,
the average error can be reduced due to the management of
the database creation.

location without any precise reference point locations. This
proposed approach can be reduced the accuracy error due
to the estimation accuracy evaluation results. In the previous
work, the accuracy error is large because of the database areconstructed using one data set. The user’s position can be also
estimated or compensated by using embedded inertial sensors
in mobile phones, which is listed as one of our future works.
R EFERENCES[1] S. Panzieri, F. Pascucci, and G. Ulivi, “An outdoor navigation
system using GPS and inertial platform,” IEEE/ASME Transactions on
Mechatronics, vol. 7, no. 2, pp. 134–142, Jun. 2002.
[2] V. Honkavirta, T. Perälä, S. Ali-Löytty, and R. Piché, “A comparative
survey of WLAN location fingerprinting methods,” in Proc. Positioning,
Navigation and Communication (WPNC), Mar. 2009, pp. 243–251.
[3] B. Molina, E. Olivares, C. E. Palau, and M. Esteve, “A multimodal
fingerprint-based indoor positioning system for airports,” IEEE Access,vol. 6, pp. 10 092–10 106, Jan. 2018.
[4] A. Solin, S. Srkk, J. Kannala, and E. Rahtu, “Terrain navigation in themagnetic landscape: Particle filtering for indoor positioning,” in 2016
European Navigation Conference (ENC), May 2016, pp. 1–9.
[5] W. K. Zegeye, S. B. Amsalu, Y. Astatke, and F. Moazzami, “WiFi
RSS fingerprinting indoor localization for mobile devices,” in Proc.
UEMCON, Oct. 2016, pp. 1–6.
[6] M. E. Rusli, M. Ali, N. Jamil, and M. M. Din, “An improved indoor
positioning algorithm based on RSSI-trilateration technique for internetof things (IOT),” in Proc. International Conference on Computer andCommunication Engineering, Jul. 2016, pp. 72–76.
[7] H. Jun-Ho and S. Kyungryong, “An indoor location-based control systemusing bluetooth beacons for IoT systems,” Sensors, vol. 17, no. 12, 2017.
[8] D. A. Savochkin, “Simple approach for passive RFID-based trilateration
without offline training stage,” in Proc. 2014 IEEE RFID Technology andApplications Conference (RFID-TA), Sep 2014, pp. 159–164.
[9] G.Retscher, “Fusion of location fingerprinting and rrilateration based on
the example of differential WI-FI positioning,” Sep. 2017, pp. 377–384.
[10] Myat Hsu Aung, H. Tsutsui, and Y. Miyanaga, “An accuracy evaluationof WiFi based indoor positioning system using estimated reference
locations,” in Proc. International Workshop on SmartInfo-Media Systems
in Asia (SISA), Sep. 2017, pp. 321–326.
[11] Y. Chapre, P. Mohapatra, S. Jha, and A. Seneviratne, “Received signal
strength indicator and its analysis in a typical WLAN system (shortpaper),” in Proc. 38th Annual IEEE Conference on Local Computer
Networks, Oct. 2013, pp. 304–307.
[12] K. Fukunaga and L. Hostetler, “The estimation of the gradient of adensity function, with applications in pattern recognition,” IEEE TIT,
vol. 21, no. 1, pp. 32–40, Jan. 1975.

4. C ONCLUSION
In this paper, we proposed a positioning system for indoor environments based on WiFi fingerprint method. The
fingerprint databases were constructed from different data
sets obtained by gathering MAC-RSSI pairs using reference
devices moving at a constant speed. To get merged reference
points from the multiple data sets, the mean-shift clustering
algorithm is used in this paper. Estimation accuracy evaluation
results show that the proposed approach can estimate user’s

10