Improving the Indoor Localization Accuracy for CPS by Reorganizing the Fingerprint Signatures

Abstract

This paper firstly represents a survey of recent researches on localization of CPS and analyzes the advantages and limitations of the existing schemes. To overcome the limitations, a novel localization scheme is then proposed, which includes site survey, received signal comparison, and location correction phases. The main improvement of our proposed scheme is to filter the noises and interference added to the received RSSI signal; the detailed procedure is then provided with mathematical analysis. Finally, the experiment and simulation results are presented with analysis.

1. Introduction

In recent years, wireless sensor networks [1, 2] achieve rapid development, which constitutes the fundamental of cyber-physical systems (CPS). In many CPS, sensed data will only be useful with the location information, which is so called location based services (LBS). Therefore, the localization of sensor nodes is essentially important for implementation of WSNs.

Many localization schemes have been introduced, which can be divided into range-based [3] and range-free [4–6] categories. Due to the big difference between indoor and outdoor environment, schemes designed for indoor or outdoor localization are relatively different. Only indoor environment is considered in the scope of this paper.

GPS [7] localization is a mature method nowadays, which uses satellite signals for localization. However, it does not work as well indoors due to the blockage of signals by walls and other barriers. Furthermore, GPS components are relatively expensive and large in size if high precision is required, which is not suitable for sensor nodes. Therefore, other available radio signals indoors are required. Nowadays, with the implementation of huge amount of WiFi [8] access points (APs) all around the world, many shopping malls and other public places offer WiFi signals. People with smart phones and other equipment such as pads or laptops can sense and measure WiFi signals and use them for localization with RSSI signature.

In theory, radio RSSI value decreases with distance increases. Because of multipath fading [9] and other signal attenuations [10], WiFi RSSI signature indoors is not smoothly monotone decreasing. It presents fluctuation in some pattern. Therefore, accurate ranging is not practical without complicated equipment. Therefore, range-based schemes are not good choices in indoor environment. To overcome such big problems, range-free schemes, such as fingerprint-based indoor localization [11–13], are introduced. It actually alters the algorithm kernel from geometry issues into classified issues. Original fingerprint-based localization aims to locate a user to the most likely sampling site, which serves as a reference location in positioning model. This algorithm is widely used for the sake of easy understanding and realization. The impact from random human presence can be offset to a large extent due to the fact that it only selects single ref-location. But the localization accuracy depends on the sampling sites interval and density utterly. The cost of preliminary manual work such as site survey [14, 15] will be increased exponentially once the accuracy needs to be improved.

Through our experiments, it is found that high frequency radio signals, such as WiFi RSSI signatures, are remarkably susceptible to human presence and movement. Human crossing the link between a WiFi AP and an RSSI receiver (AP-Receiver link) causes distortion of RSSI signature values remarkably, rebound after leaving, which causes localization inaccuracy. Furthermore, when there is no human interference, WiFi RSSI signatures present an inherent fluctuation that is a Gaussian distribution [10], which induces localization inaccuracy as well. It gives rise to false capture if the D-value of an RSSI value and its prediction reaches the threshold to determine the location even though there is no human interference. To recover such kind of RSSI signature attenuated waveforms, filtering schemes have to be introduced to eliminate the impact of random human presence, such as exponential weighted moving average (EWMA) [16].

In this paper, to overcome these limitations, a novel scheme called Fingerprint Signature Reorganizing (FSR) is introduced, with Overlap-based Weighted k Nearest Neighbors (OWKNN) algorithm, which is based from WKNN [17, 18]. By using the same interval and density of sampling sites as original scheme, both accuracy and standard deviation of localization can be improved significantly. This scheme is no longer susceptible to human presence [19] and movement as a Linearly Weighted Moving Average (LWMA) [20] scheme is adopted. Cooperative localization based on joint distribution of received APs- $Sequences$ is proposed for further improvement of localization accuracy.

The remainder of this paper is organized as follows. Section 2 outlines the previous work carried out on fingerprint-based localization algorithms, KNN, R-KNN, WKNN algorithms and valuable ideas with respect to localization. The scheme model and algorithms are described in Section 3. Section 4 presents a description of the experiment scenario and gives some practical results. Large scale, high density network simulation is carried out in Section 5 followed by performance evaluation and discussion. Finally, in Section 6, the conclusion and future work are listed.

2. Related Work

In recent researches of indoor localization, WIFI RSSI-based scheme is widely used due to the fact that few extra hardware is required [14, 21]. Although time of signal arrival (ToA) and time difference of signal arrival (TDoA) [22] can perform well outdoors, they suffer great multipath interference and other signal attenuations indoors [9, 10]. As Heurtefeux and Valois [21] mentioned, these solutions require dedicated hardware at both emitters and receiving ends and perform low in energy consumption. They also pointed out the limitations of RSSI-based schemes, such as signal instability and susceptibility to interference. However, if these problems can be solved, or at least partly solved, WiFi RSSI-based schemes are supposed to be applicable with high performance.

To determine the relationship between signal strength and RSSI signature, Rappaport [10] proposed path loss model, which presents log-distance path loss model when signal propagates in open space. Tested signal received power is given by

$$\begin{array}{cc}& PL\left(dB\right)=PL\left(d_{\mathrm{0}}\right)+\mathrm{10}n\hspace{0.17em}\log \left(\frac{d}{d_{\mathrm{0}}}\right)+X_{\sigma },\end{array}$$

(1)

and theoretical average signal received power is given by

$$\begin{array}{cc}& \overline{PL}\left(dB\right)=\overline{PL}\left(d_{\mathrm{0}}\right)+\mathrm{10}n\hspace{0.17em}\log \left(\frac{d}{d_{\mathrm{0}}}\right).\end{array}$$

(2)

These equations keep relatively accuracy in free space propagation.

Other researches [12, 13, 17, 23–27] also proposed path loss model or radio propagation model generally based on log-distance path loss model and their tested RSSI signatures also confirmed the Gaussian distributed random variable model. They adopted different parameters in order to apply to specific scenario or hardware. In [24], authors set an alternative formulation:

$$\begin{array}{cc}& RSS\left(d\right)=P_{tx}+K+\mathrm{10}\eta \hspace{0.17em}\log \left(\frac{d}{d_{\mathrm{0}}}\right)+\omega .\end{array}$$

(3)

Although radio propagation model offers the formula about RSSI and Transmitter-Receiver distance, precise positioning based on it is not feasible particularly indoors. Tanglesome surroundings induce unexpected small-scale attenuation, so trilateration [27] by T-R distances presents deviation because localization accuracy of range-based schemes highly depends on the accuracy of T-R distance estimation. Therefore, fingerprint-based localization [11–13] is widely adopted due to its feature of range-free. Walls, furniture, showcases, and so forth will not change RSSI fingerprint signatures and naturally have little impact on this algorithm as long as they stay statically.

Fingerprint-based localization schemes require a fundamental step called site survey [14, 15] that offers the data sampled serving as a reference locations system. However, the cost of preliminary manual work on site survey is a conspicuous shortage for such schemes. Wu et al. [15] and Chintalapudi et al. [14] proposed their schemes that reach an uplifting outcome; meanwhile, preliminary work lessens radically from site survey. An alternative way is to improve localization accuracy remarkably compared with previous schemes by costing the same in site survey.

Many schemes have been proposed to classify WiFi APs by using correlation coefficients of listened RSSI values, such as centroid [24], WDF [25], KNN [28, 29], R-KNN [17], WKNN [18]. Among which, WKNN is most reasonable in certain cases by focusing on estimating reference locations and their weights. Accuracy is improved significantly compared to original fingerprint. In this paper, OWKNN algorithm is proposed and the overlap ratio of APs between sensed by users and related reference locations is taken into consideration on weights estimation.

It is known that WiFi uses short wave signal, which is susceptible to interference. All the algorithms above perform retrograde in noisy cases, especially deteriorated on OWKNN's weight estimating. Outemzabet and Nerguizian [30] adopted Kalman filtering and Kim and Noble [16] used EWMA to filter noisy values and both of them performed well. This paper opts for LWMA [20] instead for the sake of simplification on computation complexity and codes realization, meanwhile, obtaining almost the same efficiency with respect to RSSI signature values recovering.

3. Scheme and Algorithm Description

In this section, the proposed Fingerprint Signature Reorganizing localization scheme and corresponding algorithms and the mathematical models are described. The main assumptions and key points are listed as follows.

Fingerprint-based localization schemes work according to comparison between user's received RSSI signatures and traversal of reference parameters computed and stored in database sampled from site survey. The similarity level determines the estimating location ultimately. It actually alters the kernel of localization from geometry issues into classification issues. RSSI values received present a Gaussian-like distribution without human interference. So the average values of RSSI signatures is obtained to help get the stable parameters and serve the algorithm efficiently, which is supposed to be closer to the theoretical RSSI signatures. However, in real world, RSSI signatures cannot get rid of the impact of human presence, which gives rise to deviation of the average values and degenerates localization accuracy. LWMA filtering can help recover the scenario back to no interference situation.

3.1. Fingerprint Signature Recognizing Localization Scheme

Although original fingerprint algorithm can offset the impact of random human presence to a large extent due to its position estimating chooses only one reference location sampled from site survey, which is regarded as single NN algorithm as well. The localization accuracy depends utterly on the sampling sites interval and density.

To overcome the limitations and maintain the advantages, a Fingerprint Signature Recognizing (FSR) localization scheme is proposed which only alters slightly from works that existed. Figure 1(a) is the overview of the flowchart of the scheme. Compared with original fingerprint localization scheme (Figure 1(b)), LWMA filtering, cooperative localization, and OWKNN algorithm are introduced to enhance localization performance. The method of estimating reference locations’ weights is the crucial step in fingerprinting algorithm. Many fingerprinting algorithms take the D-value of RSSI signatures to average a user and a reference location received as the basic parameter to compute the weights in an inverse correlation way.

Figure 1

(a) Our scheme. (b) Original scheme.

In our proposed OWKNN algorithm, a simple, efficient, and widely used method is adopted, which is demonstrated in Algorithm 1, where ε is a constant value used to protect computation from division by zero. By obtaining the average $weight$ in fingerprinting, over weighted cases caused by stochastic deviation of APs deployment can be omitted, while the same efficiency in weight evaluating can be achieved.

3.2. Capture and LWMA Filtering

Not every RSSI signature value received is supposed to be replaced in filtering; otherwise the stochastic deviation of several first prior parameters selected will be passed to entire following RSSI values. Human presence on the link between a WiFi AP and an RSSI receiver causes RSSI signature values’ attenuation remarkably, rebound once human leaves (Figure 2(a) received waveform). Such kind of RSSI signature attenuated waveform is supposed to be captured and filtered by LWMA to eliminate the impact of random human presence. The equation is given by

$$\begin{array}{cc}& RSSI{\left[cur\right]}_{predict}=\left[\frac{{{\displaystyle \sum }}_{i=cur-N_{pre}}^{cur-\mathrm{1}}RSSI\left[i\right]}{N_{pre}}\right],\end{array}$$

(4)

which is predicted by $N_{pre}$ reference parameters before signature waveform, or

$$\begin{array}{cc}& RSSI{\left[cur\right]}_{predict}=\left[\frac{{{\displaystyle \sum }}_{i=cur+N_{att}+\mathrm{1}}^{cur+N_{att}+N_{pre}}RSSI\left[i\right]}{N_{pre}}\right],\end{array}$$

(5)

which is predicted by $N_{pre}$ reference parameters after signature waveform when reference parameters are insufficient before it, where $RSSI[i]$ is the ith value, $cur$ is current index in list, $N_{pre}$ is the number of prior parameters, $N_{att}$ is number of RSSI signatures attenuated caused by human interference, and $RSSI[cur{]}_{predict}$ is the predicted value computed by LWMA, which works on the D-value of RSSI and its prediction reaches a $threshold$ . The trigger condition of LWMA filtering, defined as a capture (Figure 2(b)), is given by

$$\begin{array}{cc}& \left|RSSI{\left[cur-\mathrm{1}\right]}_{predict}-RSSI\left[cur-\mathrm{1}\right]\right|<threshold\\ \&\&\left|RSSI{\left[cur\right]}_{predict}-RSSI\left[cur\right]\right|\ge threshold.\end{array}$$

(6)

The two captures are restrained according to an RSSI signature attenuated waveform that is the target to be filtered. Other RSSI signatures present a Gaussian distribution. So the average value nonfiltered is supposed to be feasible for fingerprint algorithm without human interference.

Figure 2

(a) RSSI signature waveform. (b) LWMA analysis.

The length of receiving RSSI signatures list is assigned to $\mathrm{13}$ within receiving frequency $\mathrm{4}$  Hz. It determines that RSSI signatures receiving period is about $\mathrm{3}$ seconds; meanwhile, human presence on an AP-Receiver link occupies $\mathrm{1}$ second when moving, which determines $N_{att}=\mathrm{4}$ . So $N_{pre}$ assigned to $\mathrm{3}$ is reasonable. RSSI signatures attenuation caused by human presence is about $\mathrm{6}\hspace{0.17em}$ dB when it takes place on an AP-Receiver link with distance of 3–5 meters toward the receiver. Once the link becomes longer, there is more probability for human presence on it, which means similar level of interference by sum of human presence. On average, $threshold=\mathrm{3.5}$  dB. The D-value of RSSI average value before and after filtering can be $\mathrm{4}\times \mathrm{4}÷\mathrm{13}\approx \mathrm{1.23}$ , which is multiple of statistic deviation without human interference. Localization accuracy descends more if the attenuation becomes more severe.

A human moving path can cover a list of AP-Receiver links (Figure 3(a)) in real world. It induces a user's interfered $AP$ - $Sequence$ , of which format is $Seq=\{A{P}_{i_{\mathrm{1}}},A{P}_{i_{\mathrm{2}}},\dots ,A{P}_{i_n}\}$ . APs in it are ordered by the sequence to be interfered by human presence. Localization accuracy deteriorates when n, the length of $Seq$ , increases due to the fact that more data is deviated.

Figure 3

(a) Human interference. (b) Temporal-spatial correlation.

3.3. False Capture and Cooperative Localization

The fluctuation of RSSI received presents a zero-mean Gaussian distribution within a $\mathrm{6}$  dB range width. There exists a certain probability that the D-value of an RSSI and its prediction reaches the threshold, which is defined as false capture, without human presence on the AP-Receiver link. LWMA filtering will replace the RSSI signature values that trigger the capture condition coincidentally without interference. $P_{A{P}_x}(FC)$ , the probability of false capture with respect to the RSSI signatures list of $A{P}_x$ , is computed precisely by

$$\begin{array}{cc}& P_{A{P}_x}\left(FC\right)=\mathrm{1}-{\displaystyle \prod }_{j=\mathrm{0}}^{\mathrm{12}-N_{pre}}‍(\mathrm{1}-P\left(F{C}^{\left(j\right)}\right)),\end{array}$$

(7)

where $P(FC)$ is the probability of false capture by the first $\mathrm{4}$ values from RSSI $[\mathrm{0}]$ to RSSI $[\mathrm{3}]$ in the RSSI signatures list of $A{P}_x$ and $P(F{C}^{(j)})$ is assumed to be the probability of false capture by $\mathrm{4}$ signature values from RSSI $[j]$ to RSSI $[j+\mathrm{3}]$ when the prior values before current index, signature values from RSSI $[\mathrm{0}]$ to RSSI $[j+\mathrm{2}]$ , trigger the condition of false capture by any $\mathrm{4}$ contiguous RSSI signature values.

It is observed that $P(F{C}^{(\mathrm{1})})$ is approximated to $P(FC)$ after calculating the parameters of RSSI signature fluctuated distributions based on formula (7) even in worst case (Table 2). The D-value between $P(F{C}^{(j)})$ and $P(FC)$ is a very minor factor to the RSSI signature fluctuated distribution that impacts little the calculating results. So all $P(F{C}^{(j)})$ in this algorithm can be replaced by $P(FC)$ and formula (7) can be simplified as

$$\begin{array}{cc}& P_{A{P}_x}\left(FC\right)=\mathrm{1}-{\left(\mathrm{1}-P\left(FC\right)\right)}^{\mathrm{13}-N_{pre}},\end{array}$$

(8)

where $P(FC)$ is the probability of false capture by any $\mathrm{4}$ values from RSSI $[i]$ to RSSI $[i+\mathrm{3}]$ . $P(FC)$ is the probability sum of every false capture waveform that matches with the formula (6) when $N_{pre}=\mathrm{3}$ , or

$$\begin{array}{cc}& \left|\frac{\left(V_{\mathrm{1}}+V_{\mathrm{2}}+V_{\mathrm{3}}\right)}{\mathrm{3}}-V_{\mathrm{4}}\right|\mathrm{\hspace{0.17em}\hspace{0.17em}}\ge \mathrm{3.5},\end{array}$$

(9)

where $V_i$ is a random value from $-\mathrm{3},-\mathrm{2},-\mathrm{1,0},\mathrm{1,2},\mathrm{3}$ .

312 groups of vectors, $\overrightarrow{V}=(V_{\mathrm{1}},V_{\mathrm{2}},V_{\mathrm{3}},V_{\mathrm{4}})$ , are able to match up with the inequality formula (9) in totally ${\mathrm{7}}^{\mathrm{4}}=\mathrm{2401}$ possibilities. Therefore, the equation for computing the probability of false capture is $P(FC)=\sum ‍P(\overrightarrow{V})$ , where vectors $\overrightarrow{V}$ match with inequation (9). The probabilities in different distribution cases are demonstrated in Table 2.

Given the crowd density in a shopping mall, it has a big probability that two persons closed both have localization requirements at the same time. Single interference source is supposed to affect two closed receivers in a similar pattern due to temporal correlation and spatial correlation, which serve as a ground to cooperative localization. Human presence on AP-Receiver links when moving, as an interference source, which impacts RSSI signatures received from all the APs in real world (as shown in Figure 3(b)). There is an APs intersection between $Seqs$ (proposed in Part B) of $use{r}_{\mathrm{1}}$ and $use{r}_{\mathrm{2}}$ , which is supposed to be interfered from identical source. Cooperative localization eliminates false capture main bases on the joint distribution of data structure $Seqs$ , the interfered $APs$ - $Sequences$ of two adjacent users.

Assume $Se{q}_{use{r}_{\mathrm{1}}}=\{A{P}_{i_{\mathrm{1}}},A{P}_{i_{\mathrm{2}}},\dots ,A{P}_{i_n}\}$ and $Se{q}_{use{r}_{\mathrm{2}}}=\{A{P}_{j_{\mathrm{1}}},A{P}_{j_{\mathrm{2}}},\dots ,A{P}_{j_m}\}$ are the $Seqs$ , respectively, to $use{r}_{\mathrm{1}}$ and user who are close to each other geographically and sense APs at the same time. They are supposed to share every element in $Seqs$ . Any $A{P}_x\notin (Se{q}_{\mathrm{1}}\cap Se{q}_{\mathrm{2}})$ is referred to as a false capture. $P(CoL)$ , the probability of false capture with respect to $A{P}_x$ to be eliminated, in other words the efficiency of cooperative localization, is computed by

$$\begin{array}{l}P\left(CoL\right)=\mathrm{1}-P\left(A{P}_x\in \left(Se{q}_{use{r}_{\mathrm{1}}}\cap Se{q}_{use{r}_{\mathrm{2}}}\right)\right)\\ =\mathrm{1}-P_{A{P}_x}^{\mathrm{2}}\left(FC\right).\end{array}$$

(10)

σ, which presents the level of fluctuation RSSI signature received, has the dominated influence on the probability of false capture. It becomes bigger when increases. $P_{A{P}_x}(FC)$ is $\mathrm{2.77}\%$ in real case, which is nonignorable taking place in a relatively stable situation. Eliminating of false capture is contributory for the final localization accuracy.

Cooperative localization reaches an uplifting outcome. Theoretically, $P(CoL)$ , the efficiency for eliminating false capture, is more than $\mathrm{99}\%$ in real case, of which distribution data is tested in experiment. $P(CoL)$ is more than $\mathrm{40}\%$ in worst case, which is supposed to be a remarkable performance within the assumed worst fluctuated distribution of RSSI signatures.

3.4. Overlap-Based Weighted k Nearest Neighbors Algorithm

KNN-based algorithms evaluate user's location by the relationship among reference locations and their weights; the equation is

$$\begin{array}{cc}& Q_{user}=\frac{{{\displaystyle \sum }}_{i=\mathrm{1}}^K{w}_i·Q_{Re{f}_i}}{{{\displaystyle \sum }}_{i=\mathrm{1}}^K{w}_i}.\end{array}$$

(11)

Weights evaluation of ref-locations is the crucial step of fingerprint-based localization algorithms. Unlike range-based schemes such as trilateration, the location obtained in range-free schemes is not strictly according to geometry, weights evaluation determine the most likely location based on classifying reference locations. Efficiency of such schemes is judged by two key standards.

• (i)

  K nearest neighbour locations are picked out correctly.

• (ii)

  Their weights evaluated are reasonable with respect to user's location.

Algorithm performs well if weights evaluation is high efficiency and the localization accuracy is supposed to be better than range-based schemes due to the low performance in range evaluation indoors.

Many fingerprint-based algorithms take the D-values of RSSI signature average calculated from a user and a ref-location's list as the base number to compute weights in an inverse correlation. But such schemes can confront a big problem that gives rise to a severely incorrect weights evaluation. In Figure 4(a), the $\mathrm{4}$ nearest neighbor ref-locations with respect to user's location are supposed to be the $\mathrm{4}$ black locations. However, there exists a situation that some APs can be on the midperpendicular of the line segment between a user and a relatively far ref-location, which is referred to as a crasher reference location (the blue location in Figure 4(b)). Due to mirror symmetry principle, the crasher's Euclid distances to the APs on the midperpendicular are closer to those of the user than those of the $\mathrm{4}$ nearest ref-locations ( $\mathrm{4}$ black locations in Figure 4(b)). Naturally, $\text{User}$ . $RSSI\hspace{0.17em}Avg[i]-\text{Crasher}.RSSI\hspace{0.17em}Avg[j]$ is almost $zero$ , which can contribute to a high weight in fingerprinting due to the weights estimation in an inverse correlation. Weight of a crasher ref-location can be higher than some of the nearest neighbor ref-locations are supposed to be.

Figure 4

(a) 4 nearest neighbors. (b) Crasher case.

OWKNN algorithm is introduced for both ruling out crasher reference locations and reevaluating weights of nearest reference locations more reasonable. The kernels of this algorithm are demonstrated as shown in Algorithm 2, where   $rati{o}_{overlap}$ , the overlap ratio between sensed APs of a user and a ref-location, is used to distinguish k nearest neighbor ref-locations from crasher ref-locations. Although a crasher ref-location is weighted high in fingerprinting, its overlap ratio of sensed APs with the user is definitely lower than that of k nearest ref-locations with respect to the user (as shown in Figure 5). $threshold\_rati{o}_{overlap}$ is computed by two neighbor ref-locations. $rati{o}_{overlap}<threshold\_rati{o}_{overlap}$ implies that user's location is not in the polygon formed by k nearest neighbor ref-locations expected, of which some can be crashers. This step helps OWKNN algorithm satisfy Standard (i) that k nearest neighbor locations are going to be figured out correctly apart from the rest. $index$ is a constant estimated by ɛ (introduced in Algorithm 1) that confines the ceiling of weight due to $weigh{t}_{\max }=\mathrm{1}/\varepsilon$ when $\text{User}$ . $RSSI\hspace{0.17em}Avg[i]-\text{Ref}.RSSI\hspace{0.17em}Avg[j]=\mathrm{0}$ . $index$ greater than the magnitude of $weigh{t}_{\max }$ is sufficient to rule out crasher ref-locations. $rw$ is the weight reevaluated by $rati{o}_{overlap}$ due to the following geometrical analysis, which verifies the algorithm satisfies Standard (ii) that weights of ref-locations are going to be reevaluated more reasonably.

Algorithm 1: Fingerprinting weight.

for all AP $[i]\in$ User·APs

  for all AP $[j]\in$ Ref·APs

 if AP $[i]==$ AP $[j]$ {

 weight $+=\mathrm{1}/(|$ User·RSSIAvg $[i]-$ Ref·RSSIAvg $[j]|+\epsilon$ );

  $APIntersectionCount$ ++; }

   $weight$ /= $APIntersectionCount$ ;

Algorithm 2: OWKNN reevaluating, where $K=\mathit{3,4}$ .

for all AP $[i]\in$ User·APs

  for all AP $[j]\in$ Ref·APs

  if AP $[i]==$ AP $[j]$   $count++$ ;

Ref· $rati{o}_{overlap}=count/$ Ref·APAmount

if Ref· $rati{o}_{overlap}\ge threshold\_rati{o}_{overlap}$

 Ref· $weight$  ×= $index\times rw$ ;    /*Not a crasher*/

Figure 5

Comparison of overlap APs.

In order to find out the method for weights reevaluation, the analysis of overlapped APs is based on the following assumptions.

• (1)

Sensing area of a receiver is modeled as a disk of radius r.

(2)

The quantity of overlapped WiFi APs sensed at a user's location and a ref-location is in proportion to the overlap area of their sensing ranges.

Therefore, the weights evaluating issue become a geometrical issue through studying the overlap area instead of overlap APs. Formula (12) is simple and supposed to have high efficiency in making OWKNN algorithm qualify to Standard (ii):

$$\begin{array}{cc}& rw={\mathrm{2}}^{[\lambda ·rati{o}_{overlap}]-C},\end{array}$$

(12)

where λ and C are constants to ensure k nearest neighbor locations’ $rw>\mathrm{1}$ . Its precise evaluating method is demonstrated in the following.

The overlap area (Figures 6(a) and 6(b)) of two sensing ranges computed by distance of a user location and a ref-location is

$$\begin{array}{l}{S}_i=S\left(C_i\cap C_{\mathrm{0}}\right)\hfill \\ =\mathrm{2}{r}^{\mathrm{2}}·\text{arccos}\frac{d_i}{\mathrm{2}r}-d_i\sqrt{r^{\mathrm{2}}-\frac{d_i^{\mathrm{2}}}{\mathrm{4}}},\hspace{1em}{d}_i\in \left[\mathrm{0,2}r\right],\hfill \end{array}$$

(13)

where r is the sensing radius and $d_i=\parallel O_i{O}_{\mathrm{0}}\parallel$ , which is the Euclid distance of two locations.

Figure 6

(a) Geometrical relationship. (b) $S_i$ and $d_i$ .

The curve of formula (13) is almost linear especially for the first half (Figure 7(a)), which is used in algorithm. So it can be simplified to a linear pattern for the sake of easier realization both in algorithm and coding:

$$\begin{array}{cc}& S_i=\pi r^{\mathrm{2}}-\frac{\pi r·d_i}{\mathrm{2}},\hspace{1em}{d}_i\in \left[\mathrm{0,2}r\right].\end{array}$$

(14)

Figure 7

(a) Curve of formula (13). (b) Weighted centroid.

The relationship between $w_i$ and $d_i$ becomes a weighted centroid issue (Figure 7(b)). According to formula (11), equation for $O_{\mathrm{0}}$ 's location is formed as

$$\begin{array}{cc}& O_{\mathrm{0}}=\frac{{{\displaystyle \sum }}_{i=\mathrm{1}}^K{w}_i·O_i}{{{\displaystyle \sum }}_{i=\mathrm{1}}^K{w}_i}.\end{array}$$

(15)

Therefore, $d_i$ is precisely computed by $w_i$ and $O_i$ as

$$\begin{array}{cc}& d_i=\frac{\sqrt{{\left({{\displaystyle \sum }}_{j=\mathrm{1}}^K{w}_j\left(x_j-x_i\right)\right)}^{\mathrm{2}}-{\left({{\displaystyle \sum }}_{j=\mathrm{1}}^K{w}_j\left(y_j-y_i\right)\right)}^{\mathrm{2}}}}{{{\displaystyle \sum }}_{j=\mathrm{1}}^K{w}_j},\end{array}$$

(16)

where $(x_j,y_j)$ is $O_j$ 's location and $w_j$ is $O_j$ 's weight with respect to $O_{\mathrm{0}}$ (Figure 7(b)) and the reweight $r{w}_i$ in Algorithm 2.

In order to obtain the equation of $w_i$ computed by $d_i$ and $O_i$ , formula (16) should be transformed into the inverse function pattern. However, it is not feasible due to the fact that $d_i$ is not monotone changing considering all $w_i$ within their entire range space in formula (16). In the following analysis, a concise model (shown in Figure 7(b)) is introduced for the sake of figuring out an efficient evaluation for $w_i$ , which is based on lessening the dimensionality of formula (16) and the restrictions are listed as follows.

• (1)

Reference locations system is formed to grid pattern;

(2)

$K=\mathrm{4}$ , and ref-locations’ interval is assumed to be equal.

The function images with respect to formula (16) restricted by the conditions above are demonstrated in diverse groups of $w_{\mathrm{3}}$ when $w_{\mathrm{2}}$ and $w_{\mathrm{4}}$ are changing as the variates and $w_{\mathrm{1}}$ is assigned to a fixed value, $\mathrm{1}$ .

The function images of relationship between $S_i$ and $w_i$ with respect to Figure 8 and formula (14) are demonstrated in Figure 9.

Figure 8

The curve surfaces of simplified formula (16).

Figure 9

The function curve surfaces of relationship between $w_i$ and $S_i$ .

It is observed that $S_{\mathrm{1}}$ increases drastically when $w_{\mathrm{2}}$ , $w_{\mathrm{3}}$ , and $w_{\mathrm{4}}$ increase in range space that is smaller than $w_{\mathrm{1}}$ and presents relative stability in another range space. Generally speaking, shorter $d_i$ means bigger ratio of overlap area $S_i$ , which finally induces higher $w_i$ .

This scheme obtains an evaluation in exponential pattern computed by $rati{o}_{overlap}$ as described of formula (12), which received a high-efficiency evaluation result. Finally, the localization formula considered and altered from formula (12) is

$$\begin{array}{cc}& Q_{user}=\frac{{{\displaystyle \sum }}_{i=\mathrm{1}}^K{w}_i·index·r{w}_i·Q_{Re{f}_i}}{{{\displaystyle \sum }}_{i=\mathrm{1}}^K{w}_i·index·r{w}_i},\end{array}$$

(17)

which is computed in algorithm when it is not a crasher from judging condition.

4. Scenario Study and Experiment Results

This section describes the characteristics of a general indoor scenario, such as a shopping mall, in which our scheme and algorithms work effectively. The RSSI signatures both within and without human interference through experiment are also demonstrated. The data collected and distributions calculated provide parameters of our algorithms and models.

4.1. WiFi APs Deployment and Its Impact on FSR Scheme

In most shopping malls, free WiFi access is usually offered to customers, which can provide extra services. Given the high popularizing rate of smart phone nowadays, it is feasible to assume that hundreds of smart phones with WiFi devices can help indoor localization.

OWKNN algorithm computes $index$ and $rw$ by $rati{o}_{overlap}$ in a simple, direct method. The analysis is based on the assumption that the quantity of WiFi APs in a given region is in direct proportion to its area. There are several exceptive cases that can impact OWKNN's effectiveness. Low density of APs will cause a severe stochastic deviation in a given region. If there are a handful of APs in the overlap region of two circles (Figure 6(b)), even one AP inside or outside of it can value the $index$ and $rati{o}_{overlap}$ to a large extent. Inhomogeneous deployment of APs can induce the similar consequence. Therefore, WiFi APs’ density and deploy pattern are necessary to be considered. Scenario can be divided into office buildings and shopping malls based on it.

WiFi APs are randomly deployed in office buildings due to unorganized relationship among office owners without considering the high coincidence for overlap of propagation range of WiFi APs. Nearly every office needs at least one WiFi AP on its own due to privacy and information security. The high density of APs can sharply decrease the proportion of stochastic deviation in a given region (Figure 10) due to the large denominator. Through experiments, a WiFi receiver can sense 40–60 APs in an office building in a university.

Figure 10

APs randomly deployed with relatively high density.

The density of WiFi APs in a shopping mall is lower as open access is the only consideration. A receiver can sense 15–30 APs, which can give rise to higher proportion of stochastic deviation in a shopping mall than that in an office building. However, the APs deployment in a shopping mall is not random utterly, but substantially based on grid or cell pattern (Figure 11), which are supposed to be the most economic coverage schemes. The stochastic deviation becomes stable and predictable and that contributes to renew OWKNN algorithm. The $index$ and $rw$ can be computed by taking both $rati{o}_{overlap}$ and the stochastic deviation based on APs’ density into consideration in a more reasonable method.

Figure 11

APs deployed in grid pattern with relatively low density.

4.2. RSSI Signature Attenuated Waveform and Distribution

One of the RSSI signature attenuated waveforms caused by human presence on AP-Receiver links is demonstrated in Figure 2(a). The vast majority of human interference can be captured in waveforms clearly.

Fluctuated distributions of RSSI signatures tested from experiments are collected and calculated to be used as the distribution of real case served in false capture. Several lists of RSSI signatures within different length of AP-Receiver links are demonstrated in Figure 12.

Figure 12

RSSI signatures without human interference.

The WiFi AP hardware and laptop as the receiver are shown in Figure 13.

Figure 13

The experimental equipment.

5. Simulation Setup and Performance Evaluation

In order to examine the efficiency of our advanced fingerprint-based localization scheme, experiments and simulations are carried out based on the following configurations. The entire scenario is set up as follows (APs deployment pattern is similar to Figure 10, the site survey scheme is bases on Figure 14, and the user locations is tested bases on Figure 15).

• (1)

Assume each WiFi AP has the same hardware characteristics (RSSI signatures fluctuation picks Ref case in Table 1) and a radio propagation range of $\mathrm{30}$ meters, which also means receivers sensing area can be modeled as a disk of radius $\mathrm{30}$ meters, or $r=\mathrm{30}$  m for formula (13).

(2)

$\mathrm{100}$ APs are deployed randomly in a 100 m × 100 m space area. A receiver can sense $\mathrm{28}$ APs on average in the middle area of room given APs density and the sensing range. Considering random deployment, it senses 26–30 APs within stochastic deviation.

(3)

The distance between samples in either vertical or horizontal direction is 5 meters in site survey. Therefore, a total of 441 sampling sites are formed from a grid of 21 meters × 21 meters, which covers the room serve as reference locations.

(4)

1681 users’ locations are formed from a grid of 41 meters × 41 meters, which covers the room to be tested for algorithm performance evaluation.

Table 1

RSSI signatures fluctuated distributions in different cases.

Cases	−3	−2	−1	0	1	2	3
Worst	1/7	1/7	1/7	1/7	1/7	1/7	1/7
Ref	5%	10%	20%	30%	20%	10%	5%
Real	0.91%	2.15%	21.71%	53.33%	18.26%	2.77%	0.87%

Table 2

Results with respect to different RSSI signatures distributions.

	Worst	Ref	Real
$P(\text{FC})$	12.99%	3.50%	0.28%
$P({\text{FC}}^{(\mathrm{1})})$	13.75%	3.55%	0.28%
$P_{{\text{AP}}_x}(\text{FC})$	75.13%	29.97%	2.77%
$P(\text{CoL})$	43.55%	91.02%	99.92%

Figure 14

Reference locations in site survey.

Figure 15

Users locations tested.

Several key parameters and crucial conditions of algorithm are computed based on the setting characteristics of scenario. ɛ is assigned to $\mathrm{0.01}$ , so $index=\mathrm{100}$ in OWKNN which is enough to help rule out crasher reference locations but not change the proportion of weights among k nearest neighbor locations. It makes algorithm qualified to Standard (i).

Theoretically, $threshold\_rati{o}_{overlap}=\mathrm{91.67}\%$ due to the parameters putting into formula (14). Lower $rati{o}_{overlap}$ means smaller overlap area and longer distance between two reference locations. 23–29 APs is deployed in sensing APs overlap within stochastic deviation;   $threshold\_rati{o}_{overlap}$ can be evaluated as $\mathrm{23}/\mathrm{28}$ . The other special case is that locations at the edge and corner area of room can be analyzed in a similar method. Therefore, the crucial judging condition of OWKNN due to the scenario appointed is

• (1)

$threshold\_rati{o}_{overlap}=\mathrm{82.14}\%$ , overlap APs ≥ 16;

(2)

$threshold\_rati{o}_{overlap}=\mathrm{75}\%$ , 10 ≤ overlap APs < 16;

(3)

$threshold\_rati{o}_{overlap}=\mathrm{70}\%$ , overlap APs < 10.

Above all, $\lambda =\mathrm{2}$ is enough to ensure $rw>\mathrm{1}$ . The parameters qualify algorithm for Standard (ii). Localization accuracy and standard deviation are demonstrated in Figures 16 and 17.

Figure 16

Localization accuracy.

Figure 17

Standard deviation.

There are comparisons among $\mathrm{9}$ cases both for localization accuracy and its standard deviation—Case 0: no interference; other cases, I: RSSI signatures are interfered but not filtering; F: RSSI signatures interfered are filtered by LWMA; C: colocalization recovers accuracy; 1: interfered by single human; 2: interfered by $\mathrm{4}$ humans semisurrounded; 3: interfered by $\mathrm{8}$ humans surrounded.

This scheme improves accuracy by $\mathrm{50.02}\%\text{–}\mathrm{58.69}\%$ ; meanwhile, the standard deviation reduces by $\mathrm{39.75}\%\text{–}\mathrm{45.07}\%$ . Accuracy worsens $\mathrm{1.37}\%\text{–}\mathrm{2.35}\%$ , $\mathrm{7.43}\%\text{–}\mathrm{10.74}\%$ , and $\mathrm{7.77}\%\text{–}\mathrm{9.14}\%$ , respectively, to single, semisurrounded, and surrounded interference. Being restored by LWMA, accuracy recovers, respectively, $\mathrm{0.81}\%\text{–}\mathrm{1.20}\%$ , $\mathrm{6.60}\%\text{–}\mathrm{9.36}\%$ , and $\mathrm{7.10}\%\text{–}\mathrm{7.95}\%$ and makes accurate deterioration back around to $\mathrm{1}\%$ . Cooperative localization performs efficiency of $10.71\%$ – $20.00\%$ , which is $32.00\%$ – $41.40\%$ further improvement compared with single, semisurrounded interference case.

It verifies that advanced fingerprint-based localization scheme achieves a good accuracy and succeeds in recovering in interfered conditions. Theoretically, efficiency of cooperative localization is supposed to be $\mathrm{91.02}\%$ . However, it does not perform as high as expected due to the relatively severe fluctuation of RSSI in accept case. False capture eliminating only partly recovers the data from false capture deviation to stochastic deviation, which existed within the average of a received RSSI list and impacts localization indirectly. That is the reason why the performance of colocalization is overwhelmed. As long as the fluctuation of RSSI becomes less severe, the smaller stochastic deviation makes colocalization perform better recovering.

6. Conclusion and Future Work

In this paper, an advanced fingerprint-based indoor localization scheme called Reorganizing the Fingerprint Signatures (RFS) for CPS has been introduced. The interference of human presence to localization accuracy has been studied and the corresponding scheme has been implemented. The scheme can also solve the problem of false capture and introduces cooperative localization for further increasing of localization accuracy. The experiment and simulation results show that this scheme can sufficiently improve the localization accuracy.