Sage Journals: Discover world-class research

Abstract

Indoor localization based on existent WiFi signal strength is becoming more and more prevalent and ubiquitous. Unfortunately, the WiFi received signal strength (RSS) is susceptible by multipath, signal attenuation, and environmental changes, which is the major challenge for accurate indoor localization. To overcome these limitations, we propose the cluster k-nearest neighbor (KNN) algorithm with 5 G WiFi signal to reduce the environmental interference and improve the localization performance without additional equipment. In this paper, we propose three approaches to improve the performance of localization algorithm. For one thing, we reduce the computation effort based on the coarse localization algorithm. For another, according to the detailed analysis of the 2.4 G and 5 G signal fluctuation, we expand the real-time measurement RSS before matching the fingerprint map. More importantly, we select the optimal nearest neighbor points based on the proposed cluster KNN algorithm. We have implemented the proposed algorithm and evaluated the performance with existent popular algorithms. Experimental results demonstrate that the proposed algorithm can effectively improve localization accuracy and exhibit superior performance in terms of localization stabilization and computation effort.

1. Introduction

Recently, indoor localization achieved through wireless network signal and mobile devices has received much attention. It can provide an accurate localization in indoor environment, such as shopping malls, airports, hospitals, subways, and university campuses. For outdoor localization environment, global navigation satellite systems (GNSS) such as GPS [1, 2] have been used in a wide range of applications including tracking, transport navigation, and guidance. Although GPS works extremely well in outdoor localization, unfortunately, it does not perform well in indoors, urban canyons, construction and basement, and places close to the wall as the signal from the GPS satellites is too weak to come across most construction, thus making GPS hard for indoor localization. Attempting to find the accurate indoor localization, many indoor localization technologies are proposed, such as infrared [3], ultrawideband (UWB) [4], ultrasonic [5], Bluetooth [6], Radio Frequency Identification (RFID) [7], Zigbee [8], frequency modulation (FM) broadcast [9, 10], geomagnetism [11], and Wireless Fidelity (WiFi) [12–16].

The mobile computing technology and the increasing availability of WiFi networks have enabled more accurate localization in indoor environments. Most WiFi-based indoor localization models for commercial uses are based on received signal strength. WiFi-based localization systems have several advantages. Firstly, in terms of cost effect, the WLAN deployment of localization algorithms does not need any additional hardware as network interface cards measure signal strength values from all wireless access points (APs) in range of the receiver. Therefore, RSS needed for localization can be obtained directly from network interface cards that are included in most mobile devices. Due to the ubiquity of WiFi networks, this mode of localization provides a particularly cost-effective solution for offering location based service (LBS) in commercial and residential indoor environments. For the low cost and wide availability without the need for additional hardware, the WiFi indoor localization is becoming increasingly prevalent and ubiquitous.

There are different choices for the localization measurement methods, such as time of arrival (TOA) [17, 18], time difference of arrival (TDOA) [19], angle of arrival (AOA) [20], channel state information (CSI) [21, 22] and received signal strength (RSS) [23–26]. RSS is generally the feature of choice for indoor WiFi localization due to its low cost without the need for additional hardware at our mobile devices.

Most RSS-based indoor localization approaches adopt fingerprint algorithm as the basic scheme of indoor localization. Even though fingerprint algorithm has been successful in many localization systems [14, 24, 27, 28], it exhibits several challenges when considering real indoor environment.

(i)

Environmental variations and interferences: ideally, signal variations should only be affected by distance. The longer the distance to an access point (AP), the smaller the RSS. However, interferences and some undesired effects such as reflection can make the system detect a signal at a smaller RSS being closer to the AP. These may be caused by different set of conditions. The fingerprint is sensitive to environmental changes such as an object moving into the building, diffraction, and reflection, which result in changes in signal propagation.

(ii)

2.4 G as an unlicensed spectrum: this means that different hardware and applications apart from WiFi can freely use this spectrum to bring interference and noise. The most common electrical equipment which uses this frequency and can interfere with WiFi is microwaves that are the household electronic devices to emit interference in the 2.4 G band, Bluetooth devices, telecommunications devices, wireless security cameras, wireless speakers, and so on.

(iii)

The time-consuming offline training phase to build the fingerprint map: during the fingerprint collection phase, there are enough empirical manual measurements to build fingerprint map.

In this work, in order to reduce the manual effort during the calibration phase, we have exploited a computer-aided software, which allows us to automatically build the fingerprint map. This software consists of leading in the indoor layout and then exploiting fingerprint automatically at each reference point based on the application software. For solving the problem of the signal is unsteadiness, we propose an indoor localization system using the cluster KNN algorithm; it aims at both reducing the interference to improve localization accuracy based on 5 G signal and using cluster KNN algorithm to reduce the computation effort but improve the localization accuracy and stabilization.

The remainder of this paper is organized as follows: Section 2 discusses how related work available in the literature approaches such issues. A brief description of indoor localization system is presented in Section 3. Section 4 describes the coarse and precise localization algorithm in detail. The characteristics of 2.4 G and 5 G band signal are analysed in Section 5. The experiment results and evaluations through implementation are listed in Section 6. Finally, Section 7 concludes the paper.

2. Related Work

2.1. Fingerprint Collection

The major problem of fingerprint algorithm is the exhaustive survey needed to build the fingerprint map, a task that requires substantial cost and time. Another important issue of this fingerprint map is that a recalibration is needed every time the environment changes.

There are mainly two methods to build fingerprint map, empirical manual measurement [14, 15] and computed analytically based on the signal propagation model [12, 25, 29]. Because signal propagation model is easily affected by environmental changes, normally, the fingerprint map is built with manual effort. In this phase, the fingerprint map is surveyed for all the reference points (RPs). Basically, fingerprint map is a database of reference points at predefined points (coordinates) coupled with various radio signal strength characteristics, for example, RSS, signal angles, or propagation time called signal fingerprint. Step by step, for every fingerprint, there must be a measurement that includes the information about all positions and their received signal strength.

The popular researches highlight the strong needs of approaches aiming at reducing the time associated with the offline training phase of fingerprint algorithm. In [30], the need of an approach capable of reducing the heavy effort of the training phase is indicated as one of the key challenges in fingerprint. In [31], it is proposed that a valid training phase is hardly bearable since it requires collecting a large number of fingerprints. To reduce such fingerprint, it is presented to trade localization error against time, thus reducing the time needed to train the fingerprint map [31]. Homoplastically, it has been proposed in [32] that a huge amount of received signal strength is usually required for training and, typically, much time is necessary to collect such amount of training fingerprint. For this reason, it has been stated in [32] that a reduction of the manual effort can be achieved by minimizing the sampling time at each reference point (RP) and by limiting the number of positions to sample. Nevertheless, this simple approach makes inaccurate fingerprint map, which decreases the accuracy of the location estimation [32].

Attempting to develop training methods that try to reduce the training phase of fingerprint map have been proposed in [33, 34]. Some works also propose training the fingerprint by using a mobile device such as a smartphone, employing WiFi scans transparently to the user [35]. In order to reduce the manual effort during the calibration phase, we have defined a computer-aided approach, which allows us to automatically build the fingerprint map. In this system, a software application is developed to build the fingerprint map. It is developed based on Android Java development kit 1.7.0 and Android software development kit 4.4. The general steps of the software application are as follows.

(i)

Open the software application and import indoor workspace plan.

(ii)

Select points as reference points in the indoor map, collect real-time RSS, and store it in fingerprint map.

(iii)

After collecting fingerprint information of all reference points, if the indoor environment changes, we should reconstruct fingerprint map, only selecting brush-fire reference points and renovating the fingerprint map.

(iv)

Click the “localization” button and we should obtain our immediate position.

2.2. Matching Algorithm

During the last years, several fingerprint localization algorithms have been proposed. The key idea of fingerprint algorithm is to find the optimal nearest neighbor points. In an attempt to find the best matching algorithm and try to improve the localization accuracy, many researchers propose the nearest neighbor (NN), k-nearest neighbor (KNN) [36], weighted k-nearest neighbor (WKNN) [37], Bayesian probabilistic model (BPM) [38], artificial neural network (ANN) [39], and support vector machine (SVM) [40, 41] to obtain the optimal nearest neighbor points.

Although the above algorithms can achieve adequate localization performance, the computing and memory requirements have to be taken into consideration. While it is true that smart mobile devices are high capable machines, the users themselves do not want an application that takes gigabytes of data just to improve accuracy in localization. So a tradeoff between accuracy and complexity of algorithm is needed. In order to satisfy the acceptable localization accuracy, but with low computation effort, we propose an efficient indoor localization system.

In our proposed system, the localization includes coarse and precise localization phases. The coarse phase is to reduce the computation, and then further localization uses cluster KNN algorithm. With the society developing and wireless network popularizing, the constructions are larger and more complex; it indicates that the fingerprint map is larger and larger. During the online localization phase, if we match the real-time RSS with the whole fingerprint map, the computation is too large for efficient localization. For reducing the computation effort and localization time, the coarse localization algorithm is proposed to reduce matching fingerprint data by the detected APs. Besides, by realistic experiment, we find that the same value RSS points are scattered sometimes. This phenomenon should cause large localization error. By comparison with current localization algorithms, the cluster KNN algorithm can remove the discrete nearest neighbor points and obtain optimal nearest neighbor points.

3. System Architecture

As in most fingerprint approaches, the proposed system consists of an offline training and an online localization phase. The offline training phase is responsible for collecting signal strength from each reference point (RP) and then recording it in the fingerprint database. At the online localization phase, the mobile devices collect the real-time measurement RSS and compare it with the available fingerprint in the database.

3.1. Offline Training Phase

During the offline training phase, a designer of a fingerprint localization system has to deal with two distinct problems as follows.

(i)

Fingerprint collection: this includes how to efficiently obtain fingerprint map in the large and complex indoor construction.

(ii)

Search of the optimal APs placement: this includes how many APs are there and where they have to be placed to obtain an optimal localization accuracy.

There are three distinct problems that we should consider in the fingerprint collection: first, how to reduce the time of collection; second, how to reconstruct the fingerprint map efficiently when the indoor environment changes; third, how to extract the fingerprint characteristic of reference points. In our system, the fingerprint map is built by the developed software application, and the detailed steps are showed in Section 2.1. The software application not only builds fingerprint map conveniently but also renews partial fingerprint information of reference points without reconstructing the whole fingerprint map. During the fingerprint collection, we select RSS as fingerprint characteristic and choose media access control (MAC) as identity of different APs. Because the service set identifier (SSID) of AP may change artificially in realistic life, the MAC is sole for every AP. The raw set of RSS time samples are collected from $AP i$ at $RP j$ with orientation o by software automatically. Since RSS varies noticeably due to interferences and environment conditions, several consecutive RSS measurements need to be collected at each reference point with a period of time. Then, the average of the $RSS$ time samples is computed and stored in fingerprint database. Such fingerprint map can be represented by $Ω^{(o)}$

\begin{matrix} Ω^{(o)} = (\begin{pmatrix} γ_{1,1}^{(o)} & γ_{1,2}^{(o)} & \dots & γ_{1, N}^{(o)} \\ γ_{2,1}^{(o)} & γ_{2,2}^{(o)} & \dots & γ_{2, N}^{(o)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ γ_{L, 1}^{(o)} & γ_{L, 2}^{(o)} & \dots & γ_{L, N}^{(o)} \end{pmatrix}), \end{matrix}

(1)

where $γ_{i, j}^{(o)}$ is a fingerprint from $AP i$ at $RP j$ with orientation o, for $i = 1,2, \dots, L$ , $j = 1,2, \dots, N$ , and $o \in σ = {f o r w a r d, b a c k}$ . L is the total number of $AP$ s, and N is the number of RPs.

The placement of the APs consists of identifying the optimal APs placement, which achieves a reasonable radio signal coverage of the workspace. In general, increasing the number of APs can improve the localization accuracy, but in terms of economic investment it increases deployment costs and the amount of time for the RSS collection from all APs while establishing localization infrastructure and fingerprint map. However, the goodness of a placement pattern highly depends on the specific workspace conditions, such as wall positions and materials, space topography, noise sources, and the stream of people in the workspace.

In [42], the experimental performance shows that if we place the APs in symmetric positions distributed over the experimental workspace in such a way that the average signal power is high, it is likely to be one of the best choices to reduce localization error. In order to reduce the noise as far as possible, if the APs can be deployed by ourselves, it is better to be distributed evenly around the workspace as frontal way.

3.2. Online Localization Phase

The online localization phase consists of coarse localization and precise localization. The goal of the coarse localization phase is to reduce the impossible regions from all the fingerprint map. Thus, it removes partial impossible fingerprint and reduces the computation effort of the precise localization phase. The greater the fingerprint map is, the bigger the reduction impossible regions are as is shown in Section 6.2. In the precise localization phase, the localization is computed by using the cluster KNN algorithm. A detailed introduction is given in the following.

4. The Efficiency of Cluster KNN

4.1. Coarse Localization

Due to the wide deployment of APs, the total number of detectable APs is generally much greater than that required for localization, which leads to redundant computations. Furthermore, unreliable APs with large RSS variances may also lead to biased estimation and reduce the stability of the localization accuracy. This motivates the use of APs selection techniques to select a subset of available APs for coarse localization. Since the mobile devices detect different number of APs in different region, the detected APs can be used to coarse localization.

The coarse localization is processed by comparing the detected APs to infer the rough localization region. The real-time measurement RSS can be represented as the columns of $γ_{k, s}^{(o)} = [γ_{1, s}^{(o)}, γ_{2, s}^{(o)}, \dots, γ_{L, s}^{(o)}]^{T}$ , $s \in N$ , where the superscript T denotes transposition. Search for the $γ_{k, s}^{(o)}$ from the fingerprint map $Ω^{(o)}$ based on the detected APs. If a fingerprint includes all the detected APs, we can infer that the mobile devices are in this region. The algorithm is represented as in Alogrithm 1.

Algorithm 1: Coarse localization algorithm.

Require: fingerprint map $Ω^{(o)}$ ;

Require: a real time measurement RSS $γ_{k, s}^{(o)}, γ_{k, s}^{(o)} \in γ_{i, j}^{(o)}$ , $i = 1, \dots, L$ , $j = 1, \dots, N$ ;

Ensure: coarse localization region $Ω^{{(o)}^{'}}$ ;

(1) the undetected AP $γ_{i, j}^{(o)} \leftarrow 100$ ;

(2) while $γ_{k, s}^{(o)} \neq n u l l$ do

(3) if $γ_{k, s}^{(o)} = 100$ then

(4) the unknowed point is not adjacent to k-st AP;

(5) delete k;

(6) else

(7) the unknowed point is adjacent to k-st AP;

(8) store k;

(9) end if

(10) end while

(11) count all k;

(12) return coarse localization region $Ω^{{(o)}^{'}}$ ;

4.2. Precise Localization

The major challenge for accurate RSS-based localization comes from the variations of RSS due to the dynamic and unpredictable nature of radio channel, and the RSS is easily affected by environmental changes, such as shadowing and multipath. It is variable that the RSS is received from the same point at different time, so the real-time measurement RSS is not too credible for accurate localization. To decrease the effect with variational signal and analysis upon 2.4 G and 5 G WiFi signal, we get that absolute value of signal fluctuation is under 5 dBm as is shown in Figure 1, and about 93% fluctuation is within 5 dBm in all the fluctuations of measurement (2.4 G and 5 G band signal). In our experiment, the 5 G signal fluctuation is all within 5 dBm, and about 86% fluctuation is within 5 dBm in the 2.4 G signal. To avoid the inaccurate nearest neighbor points match with unauthentic real-time RSS, prior to conducting localization algorithm, the RSS is expanded by ±5 dBm, and then it used for localization.

Figure 1

Signal fluctuation.

In addition, the ecumenic signal propagation model is

\begin{matrix} L_{p} (dBm) = L_{p} (d_{o}) + 10 n lo g_{10} (\frac{d}{d_{0}}) + X_{σ}, \end{matrix}

(2)

where $L_{p} (d_{o})$ parameter represents the path loss at a reference distance $d_{0}$ , typically one meter. n is the constant propagation value, d is the distance between the transmitter and the receiver devices, and $X_{σ}$ is a Gaussian random variable with mean $0$ and standard deviation σ. From the signal propagation model, when the mobile devices are equidistant from the AP in line of sight, the mobile devices receive the same signal strength. This phenomenon should cause large error for localization. In Figure 2, the same color points represent the qualified nearest neighbor points; if the localization algorithm is processed based on all the qualified points, the localization error will be very large.

Figure 2

The distribution of qualified nearest neighbor points.

In our experiment, the range of signal strength is between −30 dBm and −99 dBm, and all the RSS of undetected APs represents −100 dBm. Many different RPs have the same value of RSS in the fingerprint map; if we use traditional nearest neighbor algorithms to find the optimal matching RPs, it will produce large error for localization. For the sake of searching the optimal matching RPs, not only the value of RSS but also the relationship of RPs is considered. In the offline training phase, the fingerprint map is collected in sequential order, and not only the subscript of RPs does represent the serial number but also the j implies the relationship of RPs. Generally, the coterminous RPs have analogical value of RSS, and in the process of searching for the nearest neighbor points the real-time RSS should be matched with the coterminous RPs that have the analogical value of RSS. The detailed algorithm is represented as in Algorithm 2.

Algorithm 2: Precise localization algorithm.

Require: coarse localization region $Ω^{{(o)}^{'}}$ ;

Require: a real time measurement RSS $γ_{k, s}^{(o)}, γ_{k, s}^{(o)} \in γ_{i, j}^{(o)}$ , $i = 1, \dots, L$ , $j = 1, \dots, N$ ;

Ensure: precise localization coordinate $(\hat{x}, \hat{y})$ ;

(1) for all $γ_{k, s}^{(o)'} = γ_{k, s}^{(o)} \pm 5$ dBm do

(2) end for

(3) for all ManDist $(γ_{k, s}^{{(o)}^{'}}, Ω^{{(o)}^{'}}) =$ $\sum_{i = 1}^{n}$ $| γ_{k, s}^{{(o)}^{'}} - Ω^{{(o)}^{'}} |$ do

(4) end for

(5) obtain nearest neighbor points set $γ_{k, n}^{(o)}$ ;

(6) while $Θ = (γ_{k, n_{a}}^{(o)}, γ_{k, n_{b}}^{(o)}, γ_{k, n_{c}}^{(o)}) = n u l l$ do

(7) if $\min (n_{α}, n_{β}, n_{θ}) = (| n_{a} - n_{b} | + | n_{b} - n_{c} |) \leq (| n_{α} - n_{β} | + | n_{β} - n_{θ} |), (α, β, θ) \in n$ then

(8) $\min (s, (n_{a}, n_{b}, n_{c})) = (| s - n_{a} | + | s - n_{b} | + | s - n_{c} |) \leq (| s - n_{α} | + | s - n_{β} | + | s - n_{θ} |), (α, β, θ) \in n$ ;

(9) obtain the optimal nearest neighbor points set $Θ = (γ_{k, n_{a}}^{(o)}, γ_{k, n_{b}}^{(o)}, γ_{k, n_{c}}^{(o)})$ ;

(10) else

(11) continue;

(12) end if

(13) end while

(14) return precise localization coordinate $(\hat{x}, \hat{y}) =$ $((x_{n_{a}} + x_{n_{b}} + x_{n_{c}}) / 3, (y_{n_{a}} + y_{n_{b}} + y_{n_{c}}) / 3)$ ;

According to precise localization algorithm, we select three optimal nearest neighbor points $n_{a}$ , $n_{b}$ , and $n_{c}$ as localization; the ultimate localization estimation is represented as $(\hat{x}, \hat{y})$ :

\begin{matrix} \hat{x} = \frac{1}{3} ({x_{n}}_{a} + {x_{n}}_{b} + {x_{n}}_{c}), \\ \hat{y} = \frac{1}{3} ({y_{n}}_{a} + {y_{n}}_{b} + {y_{n}}_{c}) . \end{matrix}

(3)

5. Accurate Localization Based on 5 G WiFi Signal

The indoor radio environment is quite complex. Because the 2.4 G is no permit limitation band, a wide variety of equipment use the band at the same time. It is unavoidable to be interfered by the same frequency equipment that has been introduced in Section 1. The interference signal will generate signal fluctuation when we detect the WiFi signal from surrounding access points.

The entry level speed of 5 G WiFi is 433 Mbps, which is at least three times compared to that of the 2.4 G WiFi, and the high performance of 5 G WiFi can reach more than 1 Gbps. The high transmission rate can satisfy users’ daily surfing needs and provide stable and high quality signal as well.

In this section, we explore the impact of frequency band (2.4 G and 5 G) to evaluate the localization accuracy. While 2.4 G signal is the only band originally used for WiFi, increasingly 5 G signal is also used despite of its poorer propagation characteristics resulting from higher frequency operation. As the 5 G frequency band is less crowded, there is far more spectrum available in 5 G band. From a WiFi fingerprint localization system perspective, in a typical environment today with APs using both 2.4 G and 5 G bands, a measurement RSS collected during either the offline training phase or the online localization phase will likely include a mix of 2.4 G and 5 G APs.

Figure 3 shows that the signal strength of 5 G is stronger than that of 2.4 G. Generally, stronger signal is more stable, and stable signal can guarantee the high localization accuracy.

Figure 3

Received signal strength from different APs.

Besides this, from Figures 4 and 5, we can get that the 5 G signal is more stable than that of 2.4 G in the same environment. From 30-st RP to 35-st RP, the locus of 30-st RP~35-st RP in Figures 4 and 5 indicates the 5 G signal has poorer propagation characteristics resulting from higher frequency operation.

Figure 4

Signal fluctuation at all the RPs for 2.4 G WiFi signal.

Figure 5

Signal fluctuation at all the RPs for 5 G WiFi signal.

Today more and more APs have double frequency band, and the 5 G signal seems to be much more suitable for indoor localization than 2.4 G signal. Due to a lack of cochannel interference, it can be feasible to use more stable RSS for the purpose of accurate localization. So the 5 G signal is selected as localization estimation in our localization system.

6. Experiments and Evaluations

6.1. Experiments Setup

In this section, we present the implementation and experimental evaluations of the proposed system. The fingerprint database is collected by the smartphones; its network card can detect both 2.4 G and 5 G signals. The workspace is equipped with WiFi environment by five TP-LINK WDR6300 routers that can emit 2.4 G and 5 G WiFi signal. The total area is 36 × 25.8 meters, consisting of hallways and some classrooms. We collect 40 reference points evenly from the hallways region and obtain WiFi fingerprint database using smartphone with the application software that is our developed mobile software application to collect RSS and build the fingerprint map automatically. When collecting the fingerprint map, the smartphones are kept at the same height of approximately an adult's breast and sometimes rotated horizontally at the same position to face different directions. In particular, for the RPs data, 20 samples at each RP with a rate of 1 sample/second are collected by a user walking through the hallway area.

6.1.1. Performance Metric

Besides that, according to [9, 43], Manhattan distance performs slightly better than Euclidean distance, and our workspace is a regular rectangle; we use the Manhattan distance as the standard of error analysis. The Manhattan distance is an expression of geometric metric space. It is defined as the sum of the absolute differences of values in a real-time measurement RSS from fingerprint as indicated by the following equation:

\begin{matrix} ManDist (γ_{k, s}^{(o)}, γ_{i, j}^{(o)}) = \sum_{j = 1}^{N} |γ_{k, s}^{(o)} - γ_{i, j}^{(o)}|, \end{matrix}

(4)

where ManDist(·,·) is the Manhattan distance function; $γ_{k, s}^{(o)}$ is the real-time measurement RSS; $γ_{i, j}^{(o)}$ is one of fingerprint databases.

6.1.2. Algorithms Compared

We run the following algorithms for comparison.

(i)

k-nearest neighbor (KNN): this is the most popular used algorithm, due to its excellent tradeoff between accuracy and computation complexity. It obtains the k nearest neighbors in the online localization phase, in signal space, among the known fingerprint maps. “k” is a parameter adapted to each localization system to obtain better performance.

(ii)

Weighted k-nearest neighbor (WKNN): the procedure is similar to the k-nearest neighbor. The only difference is that the average of the coordinates is a weighted average.

(iii)

Fuzzy logic: it is used to select which points are the most important to calculate the final coordinates of the current position and to assess their corresponding weight in the average. As for the other algorithms, the first step, after acquiring the current value of the received signal strength, is to determine the distance in the signal domain between the current position and all the points that make part of the fingerprint map. The next step is to transform these distance values into grades of membership;, that is, the fuzzification is made.

(iv)

Bayesian histogram method: the probabilistic method is more complex is and based on the Bayes rule. It is classified as the kernel method and histogram method generally. In the kernel method, a probability mass is assigned to a kernel around the data observed; the probability is then computed using a kernel function. The histogram method (used in our experiments) uses bins or value categorization to cover all measurement range; according to these bins, we can then calculate the probability (existence of an AP in a certain position); thus each AP will appear with different probability and we can estimate the location according to the probabilities.

6.2. The Performance of Computation Effort

In the coarse localization phase, the approximate localization region is inferred by the detected APs. According to the detected APs, remaining fingerprint database cannot include the detected APs, so we do not need to match the remaining fingerprint database, which can reduce the computation effort heavily in the precise localization phase. And the larger the fingerprint database is, the more efficient it is. From Figures 6 and 7, we can find that not all the APs can be detected in each point.

Figure 6

Detected APs from all RPs (2.4 G).

Figure 7

Detected APs from all RPs (5 G).

Supposing that every unknown point can detect 5 APs and there are 40 RPs, as the number of RPs increases, the algorithm shows greater efficiency. And the computation effort is reduced dramatically while the fingerprint map increases as is shown in Figure 8.

Figure 8

Matching efficiency with the increased RPs.

6.3. The Performance of Localization Accuracy

From Section 4, the 5 G signal is more stable than 2.4 G; if both signals can be received by our mobile devices, the 5 GHz signal should have priority to be used for localization estimation. To fair evaluate the performance of our proposed algorithm as is described in detail in Section 3, we compare the proposed algorithm with KNN, WKNN, fuzzy logic, and histogram algorithm, and the localization error of CDF (cumulative distribution function) is showed in Figures 9 and 10. It demonstrates that the cluster KNN algorithm obtains the superior localization accuracy in both 2.4 G and 5 G WiFi signals.

Figure 9

Distribution of the localization error for 2.4 G WiFi signal.

Figure 10

Distribution of the localization error for 5 G WiFi signal.

From Figure 11, regardless of 2.4 G and 5 G signal, the average error of cluster KNN is the smallest of all algorithms. The 2.4 G average errors of KNN, WKNN, fuzzy logic, histogram, and cluster KNN algorithm are 4.5700, 4.3840, 4.6213, 4.5483, and 1.4700, respectively. The 5 G average errors of the above algorithms are 2.7475, 3.2122, 2.5450, 3.7895, and 1.1500, respectively (In this study, in order to simplify the expression of error, the distance between two neighbor RPs is defined as one unit error, and all the error data omit unit.).

Figure 11

Localization mean error for 2.4 G and 5 G WiFi signal.

6.4. The Performance of Localization Stabilization

In addition, we also analyse the variance to evaluate the localization stabilization. Besides localization accuracy, the localization stabilization is also important for localization system. In our experiment, the 2.4 G variances of KNN, WKNN, fuzzy logic, histogram, and cluster KNN algorithm are 11.6129, 11.5713, 11.6833, 7.6819, and 1.8560, respectively. The 5 G variances of the above algorithms are 9.3477, 9.4714, 9.3102, 7.5370, and 1.1500, respectively, as is showed in Figure 12. The smaller the variance is, the more stable the localization presents. It indicates that not only localization accuracy but also localization stabilization is improved with cluster KNN algorithm (In this study, in order to simplify the expression of variance, the distance between two neighbor RPs is defined as one unit error, and all the variance data omit unit.).

Figure 12

Variance of localization error for 2.4 G and 5 G WiFi signal.

7. Conclusion

This paper focuses on improving the localization accuracy, stabilization, and reducing the computation effort by the proposed localization system that consists of coarse and precise localization. In the coarse localization, we use the detected APs to infer the coarse localization region. It can eliminate the impossible fingerprint database to reduce the computation effort. Besides, the fingerprint map is built by smartphone with our developed software application automatically. It improved efficiency of system operation enormously. In the precise localization, we propose two approaches to improve the localization accuracy and stabilization. By analysing the change rule of WiFi signal, about ±5 dBm of fluctuation is in the 2.4 G and 5 G signal, so the real-time measurement RSS is not so accurate as localization estimation. The real-time measurement RSS is firstly expanded by ±5 dBm and then used for the matching with the fingerprint map. In order to select the optimal nearest neighbor points, we use the relationship of RPs to eliminate the discrete nearest neighbor points. Experimental results indicate that the proposed algorithm is the most accurate and stable of all comparative algorithms. In addition, our experiment also demonstrates that the 5 G WiFi signal is more stable for indoor localization.

In the future, we intend to perform this system to apply it in larger indoor construction, as well as to investigating the performance of the proposed algorithm in more complex environment and the multilayered buildings.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This work was supported by the National Natural Science Foundation of China under Grant Project nos. 61232004 and 61103085.

References

Hofmann-Wellenhof

Lichtenegger

Collins

Hofmann-Wellenhof

Lichtenegger

Collins

Global positioning system. theory and practice

Global Positioning System. Theory and Practice 1993 1

Vienna, Austria

Springer

387

Bulusu

Heidemann

Estrin

GPS-less low-cost outdoor localization for very small devices

IEEE Personal Communications 2000 7 5 28 34

10.1109/98.878533

2-s2.0-0034291601

Lee

Chang

Park

Ryu

Jeong

S.-G.

Park

J. W.

Lee

H. C.

Hong

K.-S.

Lee

M. H.

Indoor positioning system based on incident angles of infrared emitters

Proceedings of the 30th Annual Conference of IEEE Industrial Electronics Society (IECON ’04)

November 2004

Busan, Republic of Korea

2218 2222

10.1109/IECON.2004.1432143

Shahi

Aryan

West

J. S.

Haas

C. T.

Haas

R. C. G.

Deterioration of UWB positioning during construction

Automation in Construction 2012 24 72 80

10.1016/j.autcon.2012.02.009

2-s2.0-84860292372

Filonenko

Cullen

Carswell

Investigating ultrasonic positioning on mobile phones

Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN ’10)

September 2010

IEEE

1 8

10.1109/ipin.2010.5648235

2-s2.0-78650724767

Lou

Liu

Bluetooth aided mobile phone localization: a nonlinear neural circuit approach

ACM Transactions on Embedded Computing Systems 2014 13 4 78

Becerik-Gerber

Performance-based evaluation of RFID-based indoor location sensing solutions for the built environment

Advanced Engineering Informatics 2011 25 3 535 546

10.1016/j.aei.2011.02.004

2-s2.0-79960182786

Luoh

ZigBee-based intelligent indoor positioning system soft computing

Soft Computing 2014 18 3 443 456

10.1007/s00500-013-1067-x

2-s2.0-84897580923

Chen

Lymberopoulos

Liu

Priyantha

Indoor localization using FM signals

IEEE Transactions on Mobile Computing 2013 12 8 1502 1517

10.1109/tmc.2013.58

2-s2.0-84880155186

10.

Moghtadaiee

Dempster

A. G.

Indoor location fingerprinting using fm radio signals

IEEE Transactions on Broadcasting 2014 60 2 336 346

10.1109/tbc.2014.2322771

2-s2.0-84901102001

11.

Chung

Donahoe

Schmandt

Kim

I.-J.

Razavai

Wiseman

Indoor location sensing using geo-magnetism

Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services (MobiSys ’11)

July 2011

141 154

10.1145/1999995.2000010

2-s2.0-79961084039

12.

Bisio

Cerruti

Lavagetto

Marchese

Pastorino

Randazzo

Sciarrone

A trainingless WiFi fingerprint positioning approach over mobile devices

IEEE Antennas and Wireless Propagation Letters 2014 13 832 835

10.1109/lawp.2014.2316973

2-s2.0-84900854786

13.

Alsindi

Chaloupka

AlKhanbashi

Aweya

An empirical evaluation of a probabilistic rf signature for wlan location fingerprinting

IEEE Transactions on Wireless Communications 2014 13 6 3257 3268

10.1109/twc.2014.041714.131113

2-s2.0-84898723017

14.

Yang

Liu

Smartphones based crowdsourcing for indoor localization

2014

10.1109/TMC.2014.2320254

15.

Danalet

Farooq

Bierlaire

A Bayesian approach to detect pedestrian destination-sequences from WiFi signatures

Transportation Research Part C: Emerging Technologies 2014 44 146 170

10.1016/j.trc.2014.03.015

2-s2.0-84899678139

16.

Campos

R. S.

Lovisolo

De Campos

M. L. R.

Wi-Fi multi-floor indoor positioning considering architectural aspects and controlled computational complexity

Expert Systems with Applications 2014 41 14 6211 6223

10.1016/j.eswa.2014.04.011

2-s2.0-84901406686

17.

Heidari

Pahlavan

A new statistical model for the behavior of ranging errors in TOA-based indoor localization

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ’07)

March 2007

Kowloon, Hong Kong

IEEE

2564 2569

10.1109/wcnc.2007.477

2-s2.0-36348962059

18.

Tseng

P.-H.

Feng

K.-T.

Lin

Y.-C.

Chen

C.-L.

Wireless location tracking algorithms for environments with insufficient signal sources

IEEE Transactions on Mobile Computing 2009 8 12 1676 1689

10.1109/TMC.2009.75

2-s2.0-70350618766

19.

Bocquet

Loyez

Benlarbi-Delaï

Using enhanced-TDOA measurement for indoor positioning

IEEE Microwave and Wireless Components Letters 2005 15 10 612 614

10.1109/LMWC.2005.855392

2-s2.0-27144506637

20.

Lim

C.-H.

B. P.

Robust methods for AOA geo-location in a real-time indoor WiFi system

Journal of Location Based Services 2008 2 2 112 121

10.1080/17489720802415189

2-s2.0-55149087034

21.

Xiao

Chen

Luo

L. M.

CSI-based indoor localization

IEEE Transactions on Parallel and Distributed Systems 2013 24 7 1300 1309

10.1109/TPDS.2012.214

2-s2.0-84878513014

22.

Yang

Zhou

Liu

From RSSI to CSI: indoor localization via channel response

ACM Computing Surveys 2013 46 2, article 25

10.1145/2543581.2543592

2-s2.0-84892653858

23.

Jaffe

Wax

Single-site localization via maximum discrimination multipath fingerprinting

IEEE Transactions on Signal Processing 2014 62 7 1718 1728

2-s2.0-84896466608

10.1109/tsp.2014.2304923

24.

Feng

W. S. A.

Valaee

Tan

Received-signal-strength-based indoor positioning using compressive sensing

IEEE Transactions on Mobile Computing 2012 11 12 1983 1993

10.1109/TMC.2011.216

2-s2.0-84867888352

25.

Ficco

Esposito

Napolitano

Calibrating indoor positioning systemswith low efforts

IEEE Transactions on Mobile Computing 2014 13 4 737 751

10.1109/TMC.2013.29

2-s2.0-84897835005

26.

Jiang

M. H.

Liang

An improved indoor localization of wifi based on support vector machines

International Journal of Future Generation Communication and Networking 2014 7 191 206

10.14257/ijfgcn.2014.7.5.16

27.

Shekhar

Xiong

Indoor positioning system

Encyclopedia of GIS 2008

New York, NY, USA

Springer

566

10.1007/978-0-387-35973-1628

28.

Liu

Darabi

Banerjee

Liu

Survey of wireless indoor positioning techniques and systems

IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews 2007 37 6 1067 1080

10.1109/tsmcc.2007.905750

2-s2.0-36248934122

29.

Molina-García

Calle-Sánchez

Alonso

J. I.

Fernández-Durán

Barba

F. B.

Enhanced in-building fingerprint positioning using femtocell networks

Bell Labs Technical Journal 2013 18 2 195 211

10.1002/bltj.21613

2-s2.0-84883434056

30.

Kushki

Plataniotis

K. N.

Venetsanopoulos

A. N.

Kernel-based positioning in wireless local area networks

IEEE Transactions on Mobile Computing 2007 6 6 689 705

10.1109/TMC.2007.1017

2-s2.0-34247603598

31.

King

Haenselmann

Effelsberg

Deployment, calibration, and measurement factors for position errors in 802.11-based indoor positioning systems

Location-and Context-Awareness 2007

Springer

17 34

32.

Chai

Yang

Reducing the calibration effort for probabilistic indoor location estimation

IEEE Transactions on Mobile Computing 2007 6 6 649 662

10.1109/TMC.2007.1025

2-s2.0-34247587286

33.

Steiner

Wittneben

Efficient training phase for ultrawideband-based location fingerprinting systems

IEEE Transactions on Signal Processing 2011 59 12 6021 6032

10.1109/TSP.2011.2166390

2-s2.0-81455128158

34.

Yang

Liu

Locating in fingerprint space: wireless indoor localization with little human intervention

Proceedings of the 18th Annual International Conference on Mobile Computing and Networking

August 2012

269 280

10.1145/2348543.2348578

2-s2.0-84866633671

35.

Chon

Lane

N. D.

Cha

Zhao

Automatically characterizing places with opportunistic crowdsensing using smartphones

Proceedings of the 14th International Conference on Ubiquitous Computing (UbiComp ’12)

September 2012

Pittsburgh, Pa, USA

481 490

10.1145/2370216.2370288

2-s2.0-84867449261

36.

Torteeka

Chundi

Indoor positioning based on Wi-Fi fingerprint technique using fuzzy K-nearest neighbor

Proceedings of the 11th International Bhurban Conference on Applied Sciences and Technology (IBCAST ’14)

January 2014

Islamabad, Pakistan

461 465

10.1109/ibcast.2014.6778188

2-s2.0-84898985042

37.

Shin

Lee

J. H.

Lee

Kim

H. S.

Enhanced weighted K-nearest neighbor algorithm for indoor Wi-Fi positioning systems

Proceedings of the 8th International Conference on Computing Technology and Information Management (ICCM ’12)

April 2012

574 577

2-s2.0-84867006611

38.

Madigan

Einahrawy

Martin

R. P.

W.-H.

Krishnan

Krishnakumar

Bayesian indoor positioning systems

Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’05)

2005

IEEE

1217 1227

39.

Zhou

Tang

Multilayer ANN indoor location system with area division in WLAN environment

Journal of Systems Engineering and Electronics 2010 21 5 914 926

10.3969/j.issn.1004-4132.2010.05.028

2-s2.0-78149351797

40.

Z.-L.

C.-H.

J. K.-Y.

Leung

K. R. P. H.

Location estimation via support vector regression

IEEE Transactions on Mobile Computing 2007 6 3 311 321

10.1109/tmc.2007.42

2-s2.0-33847748649

41.

Jiang

M. H.

Liang

Qin

Peng

X. R.

An indoor localization of wifi based on support vector machines

Advanced Materials Research 2014 926

Trans Tech Publications

2438 2441

42.

Baala

Zheng

Caminada

The impact of AP placement in WLAN-based indoor positioning system

Proceedings of the 8th International Conference on Networks (ICN ’09)

March 2009

Gosier, France

12 17

2-s2.0-67650677704

10.1109/icn.2009.50

43.

Farshad

Marina

M. K.

Garcia

F. J.

A microscopic look at wifi fingerprinting for indoor mobile phone localization in diverse environments

Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN '13)

2013

IEEE

1 10

5 G WiFi Signal-Based Indoor Localization System Using Cluster k -Nearest Neighbor Algorithm

Abstract

1. Introduction

2. Related Work

2.1. Fingerprint Collection

2.2. Matching Algorithm

3. System Architecture

3.1. Offline Training Phase

3.2. Online Localization Phase

4. The Efficiency of Cluster KNN

4.1. Coarse Localization

Algorithm 1: Coarse localization algorithm.

4.2. Precise Localization

Algorithm 2: Precise localization algorithm.

5. Accurate Localization Based on 5 G WiFi Signal

6. Experiments and Evaluations

6.1. Experiments Setup

6.1.1. Performance Metric

6.1.2. Algorithms Compared

6.2. The Performance of Computation Effort

6.3. The Performance of Localization Accuracy

6.4. The Performance of Localization Stabilization

7. Conclusion

Footnotes

Conflict of Interests

Acknowledgment

References