Indoor Positioning Using Adaptive KNN Algorithm Based Fingerprint Technique

Abstract

In this paper, an experiment of the indoor position location is applied to one floor of the selected building which is chosen as a case study. Four Access Points (APs) of 2.4 GHz are mounted on the experimented area. Their locations are determined using Ekahau Site Survey software to ensure the building is fully covered. A fingerprinting method is utilized as a localization algorithm to estimate the coordinate of the user. This method consists of two stages, namely disconnected data preparing stage and the on-line situating stage. The first one is applied by creating a Radio Map (RM) with 58 Reference Point (RP) in the tested area. A database included the Received Signal Strength (RSS) from all directions of each RP is recorded using Net Surveyor 0.2 Package. In the second phase, K-Nearest Neighbor (KNN) method with fix value of K is applied to estimate the position location. The results show that the average absolute error between actual and estimated coordination equal to 1.796044 m and average elapsed time equal 0.030439 s, which is unacceptable in our opinion because the localization system must be more accurate. To address this problem, a proposed improvement on KNN algorithm with a variable K is presented in this paper. The idea is to vary the value of K according to the difference between the measured signals and the corresponding value of the stored database. The results show that the adapted algorithm led to a significant decrease of 46% and 52% for absolute error and elapsed time respectively.

1 Introduction

The location-based service alludes to the applications that rely upon a client’s position to give services such as structure real-time locating and safety [1]. The Global Positioning System (GPS) is broadly utilized in outdoor environments around the plant and can give an accuracy around 10 m [2] but it does not work well in the indoor environments due to multi-path problems.

An Indoor Positioning System (IPS) is a way to locate objects or individuals inside a building using radio waves, acoustic signals, magnetic fields, or other tactile information gathered by cell phones. IPS may be integrated with other technologies such as Wi-Fi access points and Magnetic locations to measure the distance from RPs nodes that have known positions. The IPS inside buildings is done either effectively determine cell phones or give surrounding area or environmental context for devices to discover the sensed signal. Position information is an important side of a cell phone context [3]. Wi-Fi network infrastructure is found in many public facilities and can be utilized for indoor situating. In addition, the pervasiveness of Wi-Fi capable devices made this approach, particularly cost-effective.

IPS has been addressed by many researchers for indoor position applications like in [4], the researcher proposed an alternative and novel path to indoor positioning, that signals are combined from multiple sensors. By focusing on visible and inertial sensors that are ubiquitously found in mobile devices. The results confirm that it can be solved the multi-path and unpredictable signal absorption problems. In [5], the researchers got the solution to the complexity of the indoor environment to get a low-cost and accurate situating system remains open by using the Wi-Fi-based technique that can enhance the position performance from the bottleneck in ToA/AoA. The outcomes demonstrated that the Wi-Fi-based location can accomplish 1 m exactness with no equipment change in commercial Wi-Fi products. Such method appears to be superior to the regular solutions to both academia and industry concerning and the trade-off between the cost and complexity of the system. Also, in [6], the researcher proposed an algorithm to implement an IPS relying on the Bluetooth and to merge it into the Global Positioning Module (GPM) which used to uphold the education in the Institute of services science at the University of Geneva. The work compares the signal strengths of surrounding Bluetooth devices to a database of measurements taken over the indoor territory, in order to assess the client’s position. Through an assessment of the system, an exactness about 1.5 m has been gotten. Finally, in [7], it has been proposed an accurate fingerprinting based indoor positioning algorithm with three methods or technologies such as triangulation method, fingerprinting technique and Cell-ID technique. The results showed that the accuracy of the proposed method is 86%, which is better than the accuracy of fingerprinting method 72.58%, and triangulation method 45.63%.

This paper attempt to develop an indoor position sensing system using fingerprint methodology and integrated environment. A special KNN algorithm is adopted for position prediction by collecting the RSSs for multiple RPs, each one with two levels to improve the accuracy of location estimation as compared with a conventional KNN algorithm.

The rest of this paper is structured as follows. Section 1 explains the fingerprinting technique. In Sect. 2 explains our suggested a special KNN algorithm with higher accuracy. Finally, Sect. 3 concludes the conclusion.

2 Proposed Algorithm

2.1 The Disconnected Data Preparing Stage

In this research, the second floor of Communication Engineering/Mosul University building is used as a case study. Smart Drawn software is applied to draw the building was allocated to the experiment as shown in (Fig. 1).

Fig. 1.

The selected building covered by the grid.

To determine the best locations of APs in the study area, an Ekahau Site Survey was used to ensure the building was covered. Note that only four APs are chosen which decorated as a green point in Fig. 2. Each one having two antennas and operated by 2.4 GHZ frequency. To build the RM to the targeted area, 58 RPs have been chosen from the total study area. Net Surveyor 0.2 Package is used to measure and record signal strength named S₁, S₂, S₃ and S₄ received from the APs and arrangement those recorded values as a row in a database for each reading to create RSSs_(train) array as.

Fig. 2.

Conventional KNN algorithm with K constant.

$$ RSS_{(Train)} = \left( {\begin{array}{*{20}c} {S_{1,1} } & {S_{1,2} } & {S_{1,3} } & {S_{1,4} } \\ \vdots & \vdots & \vdots & \vdots \\ {S_{N,1} } & {S_{N,2} } & {S_{N,3} } & {S_{N,4} } \\ \end{array} } \right)_{Nx4} $$

(1)

Where RSSs_(train) represent all stored values of signal strength and N is the number of recorded signals in a database. An AutoCAD package version 2011 is used to calculate the coordinates of each RP and store those coordinates (x_i, y_i) corresponded to its values of signals stored in advance where $i = 1, 2, 3, 4 \ldots N$ as.

$$ RSS_{(Train)} = \left( {\begin{array}{*{20}c} {S_{1,1} } & {S_{1,2} } & {S_{1,3} } & {S_{1,4} } \\ \vdots & \vdots & \vdots & \vdots \\ {S_{N,1} } & {S_{N,2} } & {S_{N,3} } & {S_{N,4} } \\ \end{array} } \right)_{Nx4} \left( {\begin{array}{*{20}c} {X_{1,1} } & {Y_{1,2} } \\ \vdots & \vdots \\ {X_{N,1} } & {Y_{N,2} } \\ \end{array} } \right)_{Nx2} $$

(2)

To build enough strong database, 32 readings have been gathered at each RP with four directions (8 readings for each orientation) and two levels for each trend (4 readings for each level). To make ensure that most values of signals strength are recorded and the sample can represent as a matrix as.

$$ Sample_{j} = \left( {\begin{array}{*{20}c} {S_{1,1} } & {S_{1,2} } & {S_{1,3} } & {S_{1,4} } \\ \vdots & \vdots & \vdots & \vdots \\ {S_{32,1} } & {S_{32,2} } & {S_{32,3} } & {S_{32,4} } \\ \end{array} \left| {\begin{array}{*{20}c} {X_{j} } & {Y_{j} } \\ \vdots & \vdots \\ {X_{j} } & {Y_{j} } \\ \end{array} } \right.} \right)_{32x4} $$

(3)

Where samples represent the number of readings for each RP and j is the number of RPs $j = 1, 2, 3, 4 \ldots 58$.

Conventional KNN algorithm with constant K = 3 is applied to estimate the location of MS as shown in (Fig. 2).

The on-Line Situating Stage.

In this phase, Wi-Fi has been used to interface an MS carrying by a person with a Base Station (BS) to estimate his unknown location. The RSSs values will be measured by an MS from four APs and send these values to the BS to apply the conventional KNN algorithm and calculate the user’s location. The BS will evaluate (x, y) position and sends back to MS. To calculate the time required to find k neighbours (elapsed time) and absolute error of such algorithm, 18 Test Points (TPs) in different places in the targeted area are chosen and got the results shown in Table 1.

Table 1. Evaluate absolute error and elapsed time for conventional KNN algorithm.

Such an algorithm has an average absolute error equal to 1.796044 m and average elapsed time equal 0.030439 s. (Figure 3) Shows the schemes of absolute error and elapsed time.

Fig. 3.

The absolute error and the elapsed time of conventional KNN (x-axis represents the test point number).

The results show there are large differences between actual coordinates and estimated coordinates, which lead inaccuracy in locating the targeted person due to signal fluctuation in the testing area and the value of k neighbour is constant.

Adaptive KNN Algorithm.

Due to the large error in locating MS according to the results that shown in Table 1, an adaptive KNN is proposed by varying the value of K according to the Euclidean distance between the measured signals and the previously stored entries. Where the similarity distance has been exploited to make it adaptable by adding new neighbour or removing existing neighbour according to a threshold (threshold is an acceptable distance between the measured and pre-stored signal strength) especially for this building.

The results of the modified algorithm show that the time required to find K nearest neighbours is long due the large numbers of entries into the database and there was a fluctuation in the received signal due to the movement towards people in the tested area. To solve this problem, the tested area is divided into sub-regions as shown in (Fig. 4) that illustrates each sub-region with a different symbol. This will lead to a reduction in the time required to determine the location of the user as well as control the pulse of the signal fluctuation.

Fig. 4.

The targeted area is divided into four sub-regions.

The new adaptive KNN algorithm as shown in (Fig. 5) was tested by choosing the same previous TPs in the targeted area. The results are listed in Table 2.

Fig. 5.

The adaptive KNN algorithm.

Table 2. Evaluate absolute error and elapsed time of adaptive KNN algorithm.

The results show that the average absolute error of the proposed algorithm is equal to 0.817706 m. In addition, an average elapsed time equal to 0.015885 s. (Figure 6) shows the schemes for absolute error and elapsed time for each TP as compared with a conventional KNN algorithm, where a black colour represents the results of conventional KNN and red colour represent the results of adaptive KNN algorithm.

Fig. 6.

Comparison of the results, (a) absolute error and (b); elapsed time (x-axis represents the test point number). (Color figure online)

The results show there is a slight difference between actual and estimated coordinates of MS that lead to decrease average absolute error from 1.796044 m to 0.817706 m and average elapsed time from 0.030439 s to 0.015885 s. So, the new adaptive algorithm can optimize the MS localization by reducing average absolute error and elapsed time in half.

3 Conclusions

In this paper, an experimenter fingerprint algorithm based on KNN method has been presented to estimate the unknown position of MS. The results show that an unacceptable error is achieved by applying KNN with fixed K number. It was noted that the variable K was varied according to the distance between the measured signals and the previously stored entries in the database. The results confirm that the proposed algorithm achieved reasonable results by reducing the average absolute error from 1.796044 m to 0.817706 m and average elapsed time from 0.030439 s to 0.015885 s.