Keywords

1 Introduction

With a common infrastructure such as the Internet, different applications have became available anywhere at any time. It is possible to obtain the instant status information of the person or objects with the positioning systems, Positioning systems are divided into two basic groups, indoor and outdoor. Outdoor satellite-based positioning systems achieve high success by processing more than one satellite information with triangulation. For this, some information is needed like the arrival angle of signals, arrival time of signals and so on. Also, the signals must be within line-of-sight.

Many countries try to implement their own GPS applications. GLONASS [1], Galileo [2], Beidou [3] and IRNSS (NAVIC) [4] can be given as examples for developed applications. Although recommended indoor GPS [5] systems are realized for indoors, it is a disadvantage that the devices used are costly. The search for a high performance, low cost solution continues. There is no standard for any positioning systems. Offered solutions locate people inside a building using radio waves, Bluetooth and infrared signals, magnetic fields, acoustic signals or other sensory information. Indoor positioning is divided into two categories, active and passive. In active positioning, it is the direct transmission of information in positioning by means of a device carried by the users. RFID, Bluetooth, Infrared, ultra-wideband, IEEE 802.11 WLAN are examples of these. In passive systems they do not transfer information directly with any device they carry on them. Differential Air, Computer vision, Device-free Passive systems can be given as examples of passive systems [6]. Fingerprint, is a localization method based on obtaining signal map of place by power of signal of IEEE 802.WLAN. This technique is applied just other sensor data like magnetic field, RFID, Bluetooth.

Fig. 1.
figure 1

Fingerprint algorithm stages

Full size image

The fingerprint consists two step that are called online and offline stage as shown on Fig. 1. Offline phase consists the radio map construction process. Although the offline phase takes a lot of time and effort, it provides high success rate and low cost implementation. Reference points are selected inside the building and Received Signal Strength (RSS) are measured from Wireless Access Points (WAP) with the help of a mobile device. Also Detailed information about reference point as building id, floor id, space name...etc are recorded. RSS measurements can easily affected from noise (objects, people, wheatear.. etc.) to obtain high accuracy in the noisy wireless channel, different mobile devices are used to capture RSS. The signal map is used to generate a positioning model at second stage. The model can be grouped by mathematical formulas. Geometry based methods like triangulation. This method facilitates validation of data through cross verification from two or more sources. Probability based mathematical approaches can be used like Bayesian inference techniques. Machine learning algorithms especially classification methods [7,8,9,10], neural network [11,12,13], deep learning [14,15,16]...etc can be used to create high performed positioning model.

This study is aimed at finding position of a person in indoors by using fingerprint method. At positioning stage, N3 and BNN algorithms based on nearest neighbor approach are applied. Success and error distance of algorithms are tested on two different databases are presented.

2 Use of Wireless Signal Maps

Two different signal maps are used to test the algorithms. The first one is named RFKON and second one is named UJIIndoorLoc. The constructions from which both signal maps are obtained are shown in Fig. 2.

Fig. 2.
figure 2

Red, Green and Blue refers to the building of UJI Riu Sec Campus (top). KIOS Research Center floor plan (down) (Color figure online)

Full size image

The Area was broken into 1.2\(\,\times \,\)1.2 m grid squares and Received Signal Map Strength (RSS) from available Wireless Access Points (WAP) was measured at the center of each grid square to get RFKON [17]. Four different mobile devices are used to capture RSS and the number of reference points appearing in the database is 54. Each recorded measurements attributes and sample values are given at Table 1. 100 dbm means that there is no WAP information at related reference point.

Table 1. Data samples in RFKON
Full size table
Table 2. UJIIndoorLoc signal map attribute information.
Full size table

Second signal map is UJIIndoorLoc [18] which is the biggest multi-building and multi-floor database in the literature and first publicly available database that could be used to make comparisons among different methods shown. Totally 520 WAP data were recorded by more than 20 users using 25 different models of mobile devices. BuildingID is used to identify buildings which could be 3 different value. FloorID is used to identify floors of building. SpaceID is used to identify the particular space (offices, labs, etc.) where the capture was taken. All attribute information is listed at Table 2.

3 Algorithms

In this section, the structure of the N Nearest Neighbor (N3), Binned Neighbor Neighbors (BNN) algorithms [19] and the comparison parameters used to measure the success of the algorithms are presented.

3.1 N Nearest Neighbors (N3)

N3 algorithm is based on nearest neighbours which is take into account all neighbours except k-nearest neighbours. When a test sample is classified, all neighbours are sorted from most similar to the least similar with this a similarity rank vector is acquired. A weight matrix is \(W_{ig}\) calculated to classify the test sample. \(W_{ig}\) is defined as the ith object’s g th class weight and calculated on the Formula 1.

$$\begin{aligned} W_{ig}=\frac{1}{\hat{n}_g}.\sum _{j=1,j\ne i}^{(n-1)}\frac{s_{{ij}}}{r_{ij}^{\alpha }}.\delta _j \,\,\,\,\,\, \delta _j=\left\{ \begin{array}{cc} 1&{}if \,\, C_j=g \wedge \frac{s_{{ij}}}{r_{ij}^{\alpha }}>\varepsilon \\ 0&{}otherwise \\ \end{array}\right. \end{aligned}$$
(1)

\(\hat{n}_{g}\) is the number of neigbors that contribute to the class weight and calculated with the Formula 2. \(r_{ij}\) is a similarity rank and modulated by \(\alpha \) which is a real-values parameter to be optimized in the range [0.1, 2.5]. \(c_{i}\) is the class of the jth object. \(\epsilon \) (e.g., \(10^{-7} \)) is a threshold parameter to define Dirac delta (\(\delta _{i}\)).

$$\begin{aligned} \hat{n}_{g}=\sum _j\delta _{j} \end{aligned}$$
(2)

\(S_{ij}\) is the similarity between ith and jth object and calculated from their distances with Formula 3. \(d_{ij}\) is a distance measure between ith object and jth object.

$$\begin{aligned} S_{ij}=\frac{1}{1+d_{ij}} \end{aligned}$$
(3)

Finally, the calculated \(W_{ig}\) matrix is normalized with Formula 4.

$$\begin{aligned} \acute{W}_{ig}=\frac{W_{ig}}{\sum _g W_{ig}} \end{aligned}$$
(4)

All objects class definition is making with \(\acute{W}_{ig}\) values. These values can be interpreted as fuzzy measures. Maximum \(\acute{W}_{ig}\) value defines ith object class which is predefined at wireless signal map.

3.2 Binned Nearest Neighbors (BNN)

The BNN algorithm works similarly to the KNN algorithm. The test data are classified according to their nearest k neighbors. The BNN algorithm differs from the KNN algorithm in that it is the selection of neighbors used in classification. While k closest neigbors are selected in KNN algorithm, All neighbors are distributed into predefined similarity intervals (bins) and distributes into these intervals in BNN algorithm. Then, the first non-empty bin are chosen as the nearest neighbors in order to being used for prediction. The Prediction is taken as majority vote [19]. The flow diagram of the BNN algorithm is given in Fig. 3.

Fig. 3.
figure 3

The flow chart of the BNN algorithm

Full size image

3.3 Comparison Parameters

Classification algorithm’s performance are compared with different metrics. It affected by number of instances that are correctly classified, number of instances that are incorrectly classified, total number of instances, etc. The metrics which are used to compare performance of different classification algorithms are listed at Table 3.

Table 3. Algorithms comparison parameters
Full size table

4 Implementation and Results

In this study two different fingerprint map is used to test the BNN and N3 algorithms. The UJIndoorLoc dataset contains 21048 measurements (samples) taken from 520 KEN (attributes). However, 3329 measurements were used. The measurements used were re-labeled according to BuildingID, FloorID, and SpaceID, and 174 classes were distributed. RFKON data has 54 reference points recorded with coordinates values and 26 WAP measurements as listed at Table 4.

Table 4. Description of fingerprint signal map
Full size table

In machine learning algorithms; amount of data must be used in training process and amount of data must be used for to test accuracy of model. For this, 80% of data is separated for training, while 20% is for test is used both of fingerprint maps. For RFKON database, 14.784 records are used for training and 3696 records is used for test. This operation is repeated for 100 times so the average accuracy value is calculated. The optimal alpha value for N3 and BNN is determined 0.75. These values gave the highest accuracy according to the test results. Euclidean is used as the distance metric.

Table 5. Test results of BNN and N3 algorithms
Full size table
Fig. 4.
figure 4

Test results

Full size image

Error distance shows the indicates how much error the position of a person is made. Error distance is a measurement may change related to reference point frequency. If frequent intervals of reference points are determined within the building, error distance will be reduced. Error distance of both signal maps is shown in Table 3. Obtained lower error types for RFKON could be a small grid squares as 1.2\(\,\times \,\)1.2 m when measurements are taken at inside building.

5 Conclusion

In this study, two different indoor positioning models were created with fingerprint method. For this; N3 and BNN algorithms were used to define user/objects position and tested with the two different signal maps. RFKON is a data set based on signal strengths consisting of a single building and a single floor. Conversely, the UJIIndoorLoc data set consisting of multi-floor and multi-building signal map has been preferred. Effect of adding different features (building and floor information) to the N3 and BNN algorithms have been examined. When the test results are examined, it is seen that the performance of the algorithms changes according to the signal map. For UJIIndoorLoc, N3 algorithm has higher accuracy than BNN algorithm as shown Table 5. Besides, error distance is lower. N3 algorithm could not show the same performance on RFKON dataset as shown Fig. 4. In single floor data, BNN has high performance and low error distance. Lower accuracy can be obtained at multi floor signal maps than one floor signal map. Floor information affect RSSI captures.

The measurement number of fingerprinting signal data, capturing method, the number of the floor and building of location effects the accomplishment of positioning. The results of these algorithms do not sufficient for localization. For obtaining a more accurate localization system, new classification algorithms and hybrid approaches are required. For this purpose, different sensor data may be included to the system. Measured RSS values when floor information is considered can lead to errors and reduce accuracy.