Weight-RSS: A Calibration-Free and Robust Method for WLAN-Based Indoor Positioning

Abstract

Wi-Fi fingerprinting has become a promising solution for indoor positioning with the rapid deployment of WLAN and the growing popularity of mobile devices. In fingerprint-based positioning, the received signal strengths (RSS) from WLAN access points (APs) usually are regarded as positioning fingerprint to label physical location. However, the RSS variance caused by heterogeneous devices and dynamic environmental status will significantly degrade the positioning accuracy. In this paper, we first show the RSS variance based on a real dataset and analyze the relation existing in the RSS raw values. Then, we utilize both the raw RSS values and their relation to construct a new stable and robust fingerprint for indoor positioning. Experiment results indicate that our method can solve the RSS variance problem without any manual calibration.

1. Introduction

Indoor positioning has gained an increasing attention since location information is fundamental for many context-aware applications in ubiquitous computing [1–3]. With the rapid development of WLAN infrastructure, fingerprint-based method based on Wi-Fi RSS has become a promising approach for indoor positioning. In general, previous literatures based on Wi-Fi RSS can be divided into two categories: radio propagation model-based methods [4, 5] and fingerprint-based methods [6–8]. The radio propagation model-based methods use more than three known anchors to estimate location with triangulation. For instance, for estimating and tracking the key parameters of RSS propagation model in indoor environment, Bruno et al. [9] used an adaptive Bayesian framework to deal with unpredictable effects such as intercalibration and fading of radio signal. However, this kind of method cannot achieve acceptable performance due to the complex propagation phenomena (e.g., multipath fading, shadowing) of radio signals in indoor environment.

On the other hand, the principle of fingerprint-based methods is well understood [8], which uses the RSS values as fingerprint to label physical locations. In general, the localization process can be divided into two phases. (1) Offline phase: in this phase, a human surveyor with mobile device walks around in indoor environment to collect a set of RSS values for constructing fingerprint map; (2) online phase: this phase finds the closest match in the fingerprint map based on the RSS values scanned by the test device as estimation location. Most of Wi-Fi fingerprint-based algorithms assume that the devices used for constructing fingerprint map and estimating location are identical [10]. However, the RSS value at the same physical location from different devices may be incompatible, which pose a challenge in designing localization algorithms [11]. Even though using the same device for constructing fingerprint map and estimating location, the RSS values may be different due to environment changes or human mobility [12], which also lead to poor positioning accuracy.

In this paper, we propose weight-RSS, a calibration-free solution to solve the RSS variance caused by device heterogeneity and complex environment factors. The principle of weight-RSSI is that although the RSS values at a fixed location may be variance caused by different devices or environment factors, the relation between the RSS values is more stable than the values themselves. In other words, if the RSS value of AP A is found to be less than that of AP B, the less than relation is the same for different devices or different environment status. Therefore, both the RSS values and their relation are useful to estimate location. A real dataset collected with four different mobile devices is used to evaluate weight-RSS with the other three methods; the experiment results indicate weight-RSS performs better than the other three methods. Since our method constructs new positioning fingerprint based on the raw RSS values and their relation to eliminate the impact of RSS variance, it does not require manually calibrating each new device. Therefore, weight-RSSI is calibration-free method without any extra calibration effort.

The rest of this paper is organized as follows. Section 2 surveys some related works of dealing with RSS variance problem in indoor positioning. Section 3 describes our methodology in detail. Experimental results and discussion are reported in Section 4. Finally, we present our conclusions and future works in Section 5.

2. Related Work

Previous approaches for handling the variance among RSS values fall into two categories: manual calibration approaches based on device mapping [13–15] and calibration-free approaches based on constructing new positioning fingerprint [16–18].

2.1. Calibration Approaches Based on Device Mapping

These approaches attempt to manually calibrate RSS values for each new device by a linear transformation function, which adjusted RSS values when constructing fingerprinting map for different devices. For example, Laoudias et al. [13] used the existing fingerprint map to create the RSS histogram of the train device and update the test devices' RSS histogram according to the observed RSS value. Figuera et al. [15] described a calibration procedure by assuming the averaged relationship between the RSS measured by different devices is linear; then they used a linear least-squares to calibrate RSS values. Obviously, this kind of approach needs to calibrate RSS variance for each new test device, which is impractical and time-consuming with the increasing number of new mobile devices.

2.2. Calibration-Free Approaches Based on Positioning Fingerprint

The kind of approach constructs new positioning fingerprint instead of the raw RSS values to mitigate the impact of RSS variance. Dong et al. [16] proposed a novel positioning method, namely, DIFF, which utilizes the RSS differences between pairs of APs instead of absolute RSS values to construct fingerprinting map, but this method may suffer from dealing with a space of large dimensions according to [17]. However, this kind of approach will lose the discriminative information related to homogeneous devices, since it constructs new fingerprint instead of the raw RSS values. Therefore, the positioning performance of this kind of method is not always better than the raw RSS values or even worse with homogeneous devices.

In a nutshell, the first approach solves the RSS value's variance problem by finding the linear transformation with an additional learning phase. However, manual calibration phase is unrealistic with numerous new devices. Additionally, the RSS variance caused by device heterogeneous is not always linear relationship [18]. The second approach solves this problem by constructing a new positioning fingerprint that may lose the discriminative characteristics of homogeneous devices.

Recently, some literatures have been proposed from different perspectives to overcome the RSS variation problem. For example, Villarubia et al. [19] proposed a novel approach which uses multiple classifiers and RSS intensity maps for indoor positioning. Similarly, Zhu et al. [20] proposed a multiagent fusion algorithm which combines multiple classifiers for indoor positioning. In addition, hybrid indoor localization systems [21, 22] which combine information from various sensors are also proposed for solving this problem.

3. Indoor Positioning Algorithm

In this section, we first describe the RSS variance problem and then analyze the relation of RSS values based on experiment results. Then we utilize the relation to construct a new positioning fingerprint for indoor positioning.

3.1. The RSS Variance and Relation

Due to lack of standardization and normalization, mobile devices embedded with different hardware or software perform significantly distinct on scanning RSS values. Figure 1 clearly shows that the RSS values collected by four different devices vary a lot with each other at a fixed physical location. We can observe from Figure 1 that the shapes of MI 2S and Nexus 7 are almost the same, and the RSS values of the two devices have about 10 (dBm) difference. Thus, the RSS variance between MI 2S and Nexus 7 can be solved by a linear mapping function, such as the method in [13]. Nonetheless, for the RSS variance between Ascend P6 and GALAXY S3, pairwise linear transformation alone does not solve the problem. In addition, we found even those RSS values that are scanned by the same devices vary over time at a fixed location, which is obviously shown in Figure 2. The reason is the radio signals are subjected to interference and affected by environmental status. In addition, we found even those RSS values scanned by the same devices vary over time at a fixed location since the radio signals are subject to interference and affected by environmental status, which is obviously shown in Figure 2. Figure 2 shows the RSS values of three APs (AP A, AP B, and AP C) received in the same location from 10:00 pm to 12:00 pm of a day; the samples collection frequency is 0.2 Hz and obtained 1440 samples.

Figure 1

The RSS values are detected by five heterogeneous devices at the same location.

Figure 2

The RSS values from three APs at the same location.

On the other hand, we observed that the relation of the RSS values from different APs are quite more stable than the RSS values themselves according to Figures 1 and 2. For instance, it can be seen from Figure 1 that the relation for the five devices is the same: ${\text{RSS}}_{\text{AP}\mathrm{7}}>{\text{RSS}}_{\text{AP}\mathrm{2}}>{\text{RSS}}_{\text{AP}\mathrm{3}}>{\text{RSS}}_{\text{AP}\mathrm{4}}>{\text{RSS}}_{\text{AP}\mathrm{9}}>{\text{RSS}}_{\text{AP}\mathrm{6}}>{\text{RSS}}_{\text{AP}\mathrm{1}}$ > ${\text{RSS}}_{\text{AP}\mathrm{8}}>{\text{RSS}}_{\text{AP}\mathrm{5}}\mathrm{\hspace{0.17em}\hspace{0.17em}}>{\text{RSS}}_{\text{AP}\mathrm{10}}{\text{RSS}}_{\text{AP}\mathrm{11}}>{\text{RSS}}_{\text{AP}\mathrm{12}}$ . Moreover, the relation that ${\text{RSS}}_{\text{AP}\hspace{0.17em}\text{A}}>{\text{RSS}}_{\text{AP}\hspace{0.17em}\text{B}}>{\text{RSS}}_{\text{AP}\hspace{0.17em}\text{C}}$ holds for 98.76% of the total samples.

To analyze the above phenomenon, we introduce the radio propagation model [23] in indoor environment, as shown in

$$\begin{array}{cc}& \text{RSS}\left(d\right)=\text{RSS}\left(d_{\mathrm{0}}\right)+\mathrm{10}\lambda {\log }_{\mathrm{10}}\frac{d}{d_{\mathrm{0}}}+X.\end{array}$$

(1)

In this model, d denotes the distance between the transmitter (e.g., a WLAN AP) and the receiver (e.g., a smartphone) and $\text{RSS}(d)$ is the total path loss of d measured in Decibel (dBm); similarly, $\text{RSS}(d_{\mathrm{0}})$ is the path loss of the reference distance $d_{\mathrm{0}}$ (usually 1 m). The coefficient λ depends on the environment status, while X is a Gaussian random variable with zero mean, reflecting the attenuation caused by flat fading.

According to the propagation model, different RSS values detected by devices reflect the same relation indicating their distance to APs. In a nutshell, the RSS values weaken as the distance grows. We also carried out an experiment in our experimental floor plan (see in Figure 3) to validate this inference. The inference holds for 95.63% of 3280 samples obtained for 164 locations by 4 devices. Thus, we can infer that the relation among the RSS values from different APs is mainly affected by the distance between the APs and the detecting device, which is quite stable for different devices or environment status. Therefore, we can utilize the relation among RSS values to original RSS values, namely, weight-RSS, which both use the RSS values' discriminative information of heterogeneous devices and their relation for positioning.

Figure 3

The layout environment that we performed our experiments in.

3.2. Location Algorithm Based on Weight-RSS

In our location system, the fingerprint map is extracted by the RSS values and their relation obtained from training devices RSS in the offline phase. Location can be estimated by matching all the RSS values and the RSS values relation from the test device with all the entries of the fingerprint map. Obviously, this method could construct the fingerprint map capable for heterogeneous devices without any manual calibration effort.

Formally, assume there are totally m APs deployed in an indoor environment and the physical space of the indoor environment is modelled as a finite space $L=\{l_{\mathrm{1}}(x_{\mathrm{1}},y_{\mathrm{1}}),l_{\mathrm{2}}(x_{\mathrm{2}},y_{\mathrm{2}}),\dots ,l_n(x_n,y_n)\}$ . The RSS values received from all APs at a location $l_j$ can be represented as a row vector $R_j=(r_j^{\mathrm{1}},r_j^{\mathrm{2}},\dots ,r_j^i,\dots ,r_j^m)$ , where $r_j^i$ stands for the RSS value received from AP i at location $l_j$ . Then, the weight-RSS of location $l_j$ is defined as

$$\begin{array}{cc}& D_j=\left\{\left(r_j^{\mathrm{1}},s\left(r_j^{\mathrm{1}}\right)\right),\left(r_j^{\mathrm{2}},s\left(r_j^{\mathrm{2}}\right)\right),\dots ,\left(r_j^m,s\left(r_j^m\right)\right)\right\},\end{array}$$

(2)

where $s(r_j^i)$ is the index of $r_j^i$ after $R_j$ is sorted as descending order. For example, the RSS values from GALAXY S3 are $R=(-\mathrm{58},-\mathrm{38},-\mathrm{39},-\mathrm{48},-\mathrm{62},-\mathrm{56}$ , $-\mathrm{33},-\mathrm{59},-\mathrm{50},-\mathrm{63},-\mathrm{64},-\mathrm{66})$ in Figure 1; then we can calculate the weight-RSS of R as $D=\{(-\mathrm{58,7}),(-\mathrm{38,2}),(-\mathrm{39,3}),(-\mathrm{48,4}),(-\mathrm{62,9}),(-\mathrm{56,6}),(-\mathrm{33,1}),(-\mathrm{59,8}),(-\mathrm{50,5})$ , $(-\mathrm{63,10}),(-\mathrm{64,11}),(-\mathrm{66,12})\}$ according to (2).

For $D_{\mathrm{tr}}$ from fingerprint map and $D_{\text{te}}$ from a test device, their weighting factor $W_{\mathrm{tr},\text{te}}$ is calculated as

$$\begin{array}{cc}& W_{\mathrm{tr},\text{te}}=\left\{w_{\mathrm{1}},w_{\mathrm{2}},\dots ,w_m\right\},\end{array}$$

(3)

where $w_i$ is calculated as

$$\begin{array}{cc}& w_i=\mathrm{1}-\frac{\left|s\left(R_{\mathrm{tr}}^i\right)-s\left(R_{\text{te}}^i\right)\right|}{\max \left\{s\left(R_{\mathrm{tr}}^i\right),s\left(R_{\text{te}}^i\right)\right\}},\hspace{1em}\mathrm{1}\le i\le m.\end{array}$$

(4)

Then, the Euclidean distance $\text{Dist}\hspace{0.17em}(D_{\mathrm{tr}},D_{\text{te}})$ between $D_{\mathrm{tr}}$ and $D_{\text{te}}$ can be calculated as

$$\begin{array}{cc}& \text{Dist}\left(D_{\mathrm{tr}},D_{\text{te}}\right)=\sqrt{{\displaystyle \sum }_{i=\mathrm{1}}^m‍w_i{\left(r_{\mathrm{tr}}^i-r_{\text{te}}^i\right)}^{\mathrm{2}}}.\end{array}$$

(5)

In this paper, we use Nearest Neighbor based on weight-RSS to estimate location; the coordinates of the best match location are regarded as positioning result. The location algorithm is shown in Algorithm 1.

Algorithm 1: The positioning algorithm based on weight-RSS.

Input: Fingerprint Map $$M=\{D_1,D_2,\dots ,D_n\}$$ and

    RSS values scanned from test device $$R_{?}=\{r^1,r^2,\dots ,r^m\}$$

Output: the estimation location $$l^{*}$$

(1) Generate weight-RSS $$D_{R_{?}}$$ of $$R_{?}$$ according to (1)

(2) For $$i=\mathit{1,2},\dots ,n$$

(3)   Calculate the weighting factor $$W_i(D_{R_{?}},D_i)$$ according to (2)

(4)   Calculate Dist $$(D_i,D_{R_{?}},W_i)$$ according to (3)

(5)   Update the minimum value $${\text{Dist}}_{\min }$$ and record the corresponding $$D_i$$

(6) End

(7) Return $$l^{*}=\arg {\min }_l{\text{Dist}}_{\min }(D_i)$$

4. Experiment

4.1. System Setup

In this section, we establish our experimental environment for evaluating the performance of the proposed method. The experiments are carried out on the first floor of the science building four at the Zhejiang University City College, as shown in Figure 3. The whole area is divided into 164 grids for constructing the fingerprint map, and the distance between every two neighboring grids is 1 meter. In offline phase, mutual RSS values from 12 IEEE 802.11b APs are used to construct the fingerprint map.

In total, four heterogeneous devices including 3 smartphones and 1 Tablet PC participated in this experiment, as shown in Table 1.

Table 1

Devices used for experiment.

Devices	Manufacturer	Embedded OS
GALAXY S3	Samsung Electronics	Android 4.0.4
Ascend P6	Huawei	Android 4.2
MI 2S	Xiaomi Tech	Android 4.1
Nexus 7	Asus	Android 4

In the offline phase, we carried each device with sample rate 0.2 Hz and stayed 25 seconds at each grid to collect a dataset with 3280 samples. For an undetected AP, its RSS value is set to 100 (dBm). In addition, we averaged datasets per 5 samples to reduce the effect of random noise.

In order to examine the impact of RSS variance caused by device heterogeneity and environment status, we used an Ascend P6 and GALAXY S3 as train devices to collect RSS and to construct fingerprint map for indoor environment. Then, two additional devices, a Nexus 7 and a MI 2S, are utilized as the test devices.

4.2. Evaluation and Analysis

In the experiments, the positioning performances of the following 4 methods are compared: the proposed method (denoted by weight-RSS), the nearest neighbor using RSS as fingerprint (denoted by RSS-NN) [8], DIFF that uses the difference of signal strength between pairs of APs as fingerprint (denoted by DIFF-NN) [16], and the self-calibration using RSS histograms to fit a linear mapping between the test and train device (denoted by HIST-RSS) [13], respectively. In these experiments, we defined the positioning error as the Euclidean distance between the estimated location and the actual location of the test device.

Figure 4(a) shows the positioning performance under heterogeneous devices, in which an Ascend P6 acted as train device and a MI 2S acts as test device. Specifically, two-meter location accuracy of RSS-NN is 52.03%, while the proposed method, DIFF-NN, and HIST-RSS are 71.25%, 67.08%, and 58.74%, respectively. Based on the results, it can be seen that all the three calibration methods perform better than the raw RSS fingerprint with heterogeneous devices, and the proposed method achieved the highest cumulative probability (71.25%) compared to other methods for two-meter location accuracy. The reason is because DIFF-NN and HIST-RSS only consider the offset variation in the linear RSS mapping function between the training device and the test device, but only linear RSS mapping cannot solve the RSS variations caused by other factors, such as human mobility and environment status. Figure 4(b) shows the positioning performance under homogeneous devices with an Ascend P6 acting as both train device and test device; the two-meter location accuracy of the four methods is 78.25% (weight-RSS), 65.71% (DIFF-NN), 69.34% (HIST-RSS), and 67.71% (RSS-NN), respectively. It shows that the RSS-NN without any calibration achieved the highest performance improvement (15.68%). But the performances with DIFF-NN and HIST-RSS are not always much better than the original RSS (RSS-NN) or even worse with homogeneous devices, which indicate that the improvement of the two methods may be obtained at the expense of discriminative information related to homogeneous devices. On the contrary, our proposed method utilizes the relation hidden in the raw RSS values to calibration RSS variance without mapping the original RSS values.

Figure 4

The cumulative error distribution with Ascend P6 acting as train devices when MI 2S is used as the test device (a) and Ascend P6 is used as test device (b).

For verifying the inference derived from Figure 4, we repeated similar experiments with a GALAXY S3 and a Nexus 7. The experiment of Figure 5(a) investigates the influence of heterogeneous devices with a GALAXY S3 acting as train device and a Nexus 7 acting as test device; we can obtain the conclusions similar to Figure 3 that all the three calibration methods perform much better than the origin RSS with heterogeneous devices, and the proposed method achieved the best performance. Figure 5(a) shows the performance under homogeneous devices with a GALAXY S3 acting as both train and test device, and the experiment results are also similar to Figure 4(a). The difference is the performances of DIFF-NN and HIST-RSS in Figure 5(a) are inferior to those in Figure 4(a). The reason is that the linear RSS mapping function between the Ascend P6 and the MI 2S is smaller than that between the GALAXY S3 and the Nexus 7, which means that RSS variance caused by device heterogeneous in the mapping function is larger when the GALAXY S3 acted as train device and Nexus 7 is used as the test device. Therefore, DIFF-NN and HIST-RSS which based on the linear RSS mapping depend on the types of the training device and test device.

Figure 5

The cumulative error distribution with GALAXY S3 acting as train devices when Nexus 7 is used as test device (a) and GALAXY S3 is used as the test device (b).

Furthermore, both the experiments in Figures 4(b) and 5(b) indicate that the performances with DIFF-NN and HIST-RSS are not always much better than the original RSS (RSS-NN) with homogeneous devices. The reason is these improvement methods lost the discriminative characteristics related to homogeneous devices.

Figure 6 shows the positioning performance with Ascend P6 and GALAXY S3 is used as train devices; the four devices act as test devices. As shown in both Figures 6(a) and 6(b), all the three calibration methods achieved a significant performance improvement compared to the original RSS in heterogeneous situation, while DIFF-NN and HIST-NN perform similarly or even worse compared to the origin RSS in homogeneous situation. On the contrary, the proposed method performs much better than the original RSS in both heterogeneous situation and homogeneous situation.

Figure 6

Comparison of mean distance errors with the four methods when (a) an Ascend P6 and (b) a GALAXY S3 are used as the train devices and the other four kinds of devices are used as test devices.

5. Conclusion

Location information plays a crucial role in various context-aware ubiquitous applications. For indoor positioning method based on RSS fingerprint, a major challenge is the RSS variance due to devices heterogeneity and environment status, which will significantly degrade the positioning accuracy. In this paper, we proposed weight-RSS, a new indoor positioning algorithm which utilizes the relation of RSS values to construct more stable fingerprint instead of the raw RSS values to deal with the RSS variance. The relation in the order of RSS values from different APs at a fixed location is more stable than the values themselves. The experiments were carried out in a real environment, the results indicate that the proposed method is superior to DIFF-NN, HIST-RSS, and the original RSS values. Finally, weight-RSS can be easily applied to non-WiFi signals, especially those which natively provide RSS values.

As future work, we plan to evaluate the performance of our method in a large scale environment and utilize various useful sensor information (e.g., accelerometer, gyroscope, and compass) from smartphone to further improve the positioning accuracy.