Printer Friendly

Improving the indoor localization accuracy for CPS by reorganizing the fingerprint signatures.

1. Introduction

In recent years, wireless sensor networks [1, 2] achieve rapid development, which constitutes the fundamental of cyberphysical 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 [46] 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 Dvalue 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]canperform-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

PL(dB) = PL([d.sub.0]) + 10n log (d/[d.sub.0])+ [X.sub.[sigma], (1) and theoretical average signal received power is given by

[bar.PL] (dB) = [bar.PL] ([d.sub.0]) + 10n log (d/[d.sub.0]). (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:

RSS(d) = [P.sub.tx] + K + 10[eta] log + (d/[d.sub.0] + [omega]. (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.

In our proposed OWKNN algorithm, a simple, efficient, and widely used method is adopted, which is demonstrated in Algorithm 1, where e 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 linkbetween 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


which is predicted by [N.sub.pre] reference parameters before signature waveform, or


which is predicted by [N.sub.pre] reference parameters after signature waveform when reference parameters are insufficient before it, where .RSS/[i] is the ith value, cur is current index in list, [N.sub.pre] is the number of prior parameters, [N.sub.att] is number of RSSI signatures attenuated caused by human interference, and RSSI[[cur].sub.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

[absolute value of RSSI[[cur - 1].sub.predict] - RSSI [cur - 1] I < threshold] && [absolute value of RSSI[[cur].sub.predict] - RSSI [cur]][greater than or equal to] threshold. (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.

The length of receiving RSSI signatures list is assigned to 13 within receiving frequency 4 Hz. It determines that RSSI signatures receiving period is about 3 seconds; meanwhile, human presence on an AP-Receiver link occupies 1 second when moving, which determines [N.sub.att] = 4. So [N.sub.pre] assigned to 3 is reasonable. RSSI signatures attenuation caused by human presence is about 6 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 = 3.5 dB. The D-value of RSSI average value before and after filtering can be 4 x 4 / 13 [approximately equal to] 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 = {[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]}. 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.

3.3. False Capture and Cooperative Localization. The fluctuation of RSSI received presents a zero-mean Gaussian distribution within a 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. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (FC), the probability of false capture with respect to the RSSI signatures list of A[P.sub.x], is computed precisely by


where P(FC) is the probability of false capture by the first 4 values from RSSI[0] to RSSI[3] in the RsSi signatures list of A[P.sub.x] and P([FC.sup.(j) is assumed to be the probability of false capture by 4 signature values from FSS7[j] to RSSI[j + 3] when the prior values before current index, signature values from FSS7[0] to RSSI[j + 2], trigger the condition of false capture by any 4 contiguous RSSI signature values.

It is observed that P([FC.sup.(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([FC.sup.(j)]) and P(FC) is a very minor factor to the RSSI signature fluctuated distribution that impacts little the calculating results. So all P([FC.sup.(j)]) in this algorithm can be replaced by P(FC) and formula (7) can be simplified as


where P(FC) is the probability of false capture byany 4 values from RSSI[i] to RSSI[i + 3]. P(FC) is the probability sum of every false capture waveform that matches with the formula (6) when [N.sub.pre] = 3, or

[absolute value of [V.sub.1] + [V.sub.2] + [V.sub.3]/3 - [V.sub.4] [greater than or equal to] 3.5, (9)

where [V.sub.i] is a random value from -3, -2, -1, 0, 1, 2, 3.

312 groups of vectors, [??] = ([V.sub.1],[V.sub.2],[V.sub.3],[V.sub.4]), are able to match up with the inequality formula (9) in totally [7.sup.4] = 2401 possibilities. Therefore, the equation for computing the probability of false capture is P(FC) = [summation] P([??]), where vectors [??] 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 [user.sub.1] and [user.sub.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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are the Seqs, respectively, to [user.sub.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.sub.x] [not memter of] ([Seq.sub.1][intersection][Seq.sub.2]) is referred to as a false capture. P(CoL), the probability of false capture with respect to A[P.sub.x] to be eliminated, in other words the efficiency of cooperative localization, is computed by


[sigma], which presents the level of fluctuation RSSI signature received, has the dominated influence on the probability of false capture. It becomes bigger when increases. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (FC) is 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 99% in real case, of which distribution data is tested in experiment. P(CoL) is more than 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


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 reflocation'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 4 nearest neighbor ref-locations with respect to user's location are supposed to be the 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 4 nearest ref-locations (4 black locations in Figure 4(b)). Naturally, User.RSSI Avg[i]- Crasher.RSSI 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.

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 [ratio.sub.overiap], 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

ALGORITHM 1: Fingerprinting weight.

for all AP [i] [member of]  User x APs
  for all AP[j] [member of] Ref x APs
  if AP[i] == AP[j]{
  weight+ = 1/([absolute value of User x
  RSSI Avg[i]-Ref x RSSI Avg[j]] + [epsilon]);
  APIntersectionCount ++;}
  weight /= APIntersectionCount;

shown in Figure 5). threshold-[ratio.sub.overlap] is computed by two neighbor ref-locations. [ratio.sub.overlap] < threshold-[ratio.sub.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 e (introduced in Algorithm 1) that confines the ceiling of weight due to [weight.sub.max] = 1/[epsilon] when User.RSSI Avg[i] - Ref.RSSI Avg[j] = 0. index greater than the magnitude of [weight.sub.max] is sufficient to rule

out crasher ref-locations. rw is the weight reevaluated by [ratio.sub.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 2: OWKNN reevaluating, where K = 3,4.

for all AP[i] [member of] User x APs
 for all AP[j] [member of] Ref x APs
 if AP[i] == AP[j] count + +;
 Ref x [ratio.sub.overlap] = count/Ref x APAmount
 if Ref x [ratio.sub.overlap] > threshold.[ratio.sub.overlap]
   Ref-weight x = index x rw, / *Not a crasher*/

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):


where [lambda] and C are constants to ensure k nearest neighbor locations' rw > 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 reflocation is

[S.sub.i] = S ([C.sub.i] [intersection] [C.sub.0])

= 2[r.sup.2] x arcos [d.sub.i]/2r - [d.sub.i] [square root of [r.sup.2 - [d.sup.2.sub.i]/4, [d.sub.i] [member of [0,2r], (13)

where r is the sensing radius and [d.sub.i] = [parallel][O.sub.i] [O.sub.0] [parallel], which is the Euclid distance of two locations.

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:

[S.sub.i] = [pi][r.sup.2] - [pi]rr x [d.sub.i]/2, [d.sub.i][member of] [0,2r]. (14)

The relationship between [w.sub.i] and [d.sub.i] becomes a weighted centroid issue (Figure 7(b)). According to formula (11), equation for O0's location is formed as

[O.sub.0] = [summation].sup.K.sub.i=1] [w.sub.i] x [O.sub.i]/[summation].sup.K.sub.i=1] [w.sub.i] = (15)

Therefore, [d.sub.i] is precisely computed by [w.sub.i] and [O.sub.i] as


where ([x.sub.j], [y.sub.j]) is [O.sub.j]'s location and [w.sub.j] is [O.sub.j]'s weight with respect to [O.sub.0] (Figure 7(b)) and the reweight r[w.sub.i] in Algorithm 2.

In order to obtain the equation of [w.sub.i] computed by [d.sub.i] and [O.sub.i];, formula (16) should be transformed into the inverse function pattern. However, it is not feasible due to the fact that [d.sub.i] is not monotone changing considering all [w.sub.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.sub.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 = 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.sub.3] when [w.sub.2] and [w.sub.4] are changing as the variates and [w.sub.1] is assigned to a fixed value, 1.

The function images of relationship between [S.sub.i] and [w.sub.i] with respect to Figure 8 and formula (14) are demonstrated in Figure 9.

It is observed that increases drastically when [w.sub.2], [w.sub.3], and [w.sub.4] increase in range space that is smaller than [w.sub.1] and presents relative stability in another range space. Generally speaking, shorter [d.sub.i] means bigger ratio of overlap area [S.sub.i], which finally induces higher [w.sub.i].

This scheme obtains an evaluation in exponential pattern computed by [ratio.sub.overlap] as described of formula (12), which received a high-efficiency evaluation result. Finally, the localization formula considered and altered from formula (12) is


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 [ratio.sub.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 [ratio.sub.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.

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 [ratio.sub.overlap] and the stochastic deviation based on APs' density into consideration in a more reasonable method.

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.

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

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 30 meters, which also means receivers sensing area can be modeled as a disk of radius 30 meters, or r = 30 m for formula (13).

(2) 100 APs are deployed randomly in a 100 m x 100 m space area. A receiver can sense 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 x 21 meters, which covers the room serve as reference locations.

(4) 1681 users' locations are formed from a grid of 41 meters x 41 meters, which covers the room to be tested for algorithm performance evaluation.

Several key parameters and crucial conditions of algorithm are computed based on the setting characteristics of scenario. [epsilon] is assigned to 0.01, so index = 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-[ratio.sub.overlap] = 91.67% due to the parameters putting into formula (14). Lower [ratio.sub.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-[ratio.sub.overlap] can be evaluated as 23/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_[ratio.sub.overlap] = 82.14%, overlap APs [greater than or equal to] 16;

(2) threshold_[ratio.sub.overlap] = 75%, 10 [less than or equal to] overlap APs < 16;

(3) threshold_[ratio.sub.ovelap] = 70%, overlap APs < 10.

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

There are comparisons among 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 4 humans semisurrounded; 3: interfered by 8 humans surrounded.

This scheme improves accuracy by 50.02%-58.69%; meanwhile, the standard deviation reduces by 39.75%-45.07%. Accuracy worsens 1.37%-2.35%, 7.43%-10.74%, and 7.77%-9.14%, respectively, to single, semisurrounded, and surrounded interference. Being restored by LWMA, accuracy recovers, respectively, 0.81%-1.20%, 6.60%-9.36%, and 7.10%-7.95% and makes accurate deterioration back around to 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 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.

Conflict of Interests

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


The work presented in this paper was partially financed by the National Natural Science Foundation of China under Grants 61190113 and 61272539 and Zhejiang Provincial Key Innovation Team on Sensor Networks under Grant no. 2009R50046.


[1] L. Lazos and R. Poovendran, "Serloc: robust localization for wireless sensor networks," ACM Transactions on Sensor Networks, vol. 1, no. 1, pp. 73-100, 2005.

[2] J. Wang, Q. Gao, H. Wang, and Y. Han, "Time-of-flight-based radio tomography for device free localization," IEEE Transactions on Wireless Communications, vol. 12, no. 5, pp. 2355-2365, 2013.

[3] S. Rallapalli, L. Qiu, Y. Zhang, and Y.-C. Chen, "Exploiting temporal stability and low-rank structure for localization in mobile networks," in Proceedings of the 16th Annual Conference on Mobile Computing and Networking (MobiCom '10), pp. 161-172, September 2010.

[4] T He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, "Range-Free Localization Schemes for Large Scale Sensor Networks," in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom '03), pp. 81-95, September 2003.

[5] J. Wang, Q. Gao, Y. Yu, P. Cheng, W. Lifei, and H. Wang, "Robust device-free wireless localization based on differential RSS measurements," IEEE Transactions on Industrial Electronics, vol. 60, pp. 5943-5952, 2013.

[6] L. Wu, J. Wang, Q. Gao, and H. Wang, "Towards cognitive device-free localization in wireless networks," in Proceedings of ICCC, 2013.

[7] W. Lewandowski, J. Azoubib, and W. J. Klepczynski, "GPS: primary tool for time transfer," Proceedings of the IEEE, vol. 87, no. 1, pp. 163-172, 1999.

[8] H. Liu, Y. Gan, and J. Yang, "Push the limit of wifi based localization for smartphones," in Proceedings of the 18th Annual International Conference on Mobile Computing and Networking (MobiCom '12), pp. 305-316, 2012.

[9] X. Zheng, G. Bao, R. Fu, and K. Pahlavan, "The performance of simulated annealing algorithms for Wi-Fi localization using google indoor map," in Proceedings of the IEEE Vehicular Technology Conference (VTC '12), pp. 1-5, 2012.

[10] T. S. Rappaport, Wireless Communications: Principles and Practice, Prentice Hall, 1996.

[11] Z. Yang, C. Wu, and Y. Liu, "Locating in fingerprint space: wireless indoor localization with little human intervention," in Proceedings of the 18th Annual International Conference on Mobile Computing and Networking (MobiCom '12), pp. 269-280, 2012.

[12] Y.-C. Cheng, Y. Chawathe, A. LaMarca, and J. Krumm, "Accuracy characterization for metropolitan-scale Wi-Fi localization," in Proceedings of the 3rd International Conference on

Mobile Systems, Applications, and Services (MobiSys '05), pp. 233-245, 2005.

[13] Y. Ji, S. Biaz, S. Pandey, and P. Agrawal, "ARIADNE: a dynamic indoor signal map construction and localization system," in Proceedings of the 4th International Conference on Mobile Systems, Applications and Services (MobiSys '06), pp. 151-164, June 2006.

[14] K. Chintalapudi, A. P Iyer, and V. N. Padmanabhan, "Indoor localization without the pain," in Proceedings of the 16th Annual Conference on Mobile Computing and Networking (MobiCom '10), pp. 173-184, September 2010.

[15] C. Wu, Z. Yang, Y. Liu, and W. Xi, "WILL: wireless indoor localization without site survey," in Proceedings of IEEE INFOCOM, pp. 64-72, 2012.

[16] M. Kim and B. Noble, "Mobile network estimation," in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom '10), pp. 298-309, July 2001.

[17] Y. Gao, J. Niu, R. Zhou, and G. Xing, "ZiFind: exploiting crosstechnology interference signatures for energy-efficient indoor localization," in Proceedings of IEEE INFOCOM, pp. 2940-2948, 2013.

[18] T Bagosi and Z. Baruch, "Indoor localization by WiFi," in Proceedings of the IEEE 7th International Conference on Intelligent Computer Communication and Processing (ICCP '11), pp. 449452, August 2011.

[19] Y. Chen, D. Lymberopoulos, J. Liu, and B. Priyantha, "FM-based indoor localization," in Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services (MobiSys '12), pp. 169-182, 2012.

[20] G. Judd, X. Wang, and P Steenkiste, "Efficient channel-aware rate adaptation in dynamic environments," in Proceedings of the 6th International Conference on Mobile Systems, Applications, and Services (MobiSys '08), pp. 118-131, June 2008.

[21] K. Heurtefeux and F. Valois, "Is RSSI a good choice for localization in wireless sensor network?" in Proceedings of the IEEE International Conference on Advanced Information Networking and Applications (AINA '12), pp. 732-739, 2012.

[22] J. Yang, X. Wang, M. J. Rahman, S. I. Park, H. M. Kim, and Y. Wu, "A new positioning system using DVB-T2 transmitter signature waveforms in single frequency networks," IEEE Transactions on Broadcasting, vol. 58, no. 3, pp. 347-359, 2012.

[23] T Roos, P. Myllymaki, and H. Tirri, "A statistical modeling approach to location estimation," IEEE Transactions on Mobile Computing, vol. 1, no. 1, pp. 59-69, 2002.

[24] P Pivato, L. Palopoli, and D. Petri, "Accuracy of RSS-based centroid localization algorithms in an indoor environment," IEEE Transactions on Instrumentation and Measurement, vol. 60, no. 10, pp. 3451-3460, 2011.

[25] X. Song, F. Yang, L. Ding, and L. Qian, "Weight adjust algorithm in indoor fingerprint localization," in Proceedings of the International Conference on Signal Processing and Communication Systems (ICSPCS '12), pp. 1-5, 2012.

[26] K. Wu, J. Xiao, Y. Yi, M. Gao, and L. M. Ni, "Fila: fine-grained indoor localization," in Proceedings of IEEE INFOCOM, pp. 2210-2218, 2012.

[27] J. Jiang, X. Zheng, Y. Chen et al., "A distributed RSS-based localization using a dynamic circle expanding mechanism," Sensors Journal, vol. 13, no. 10, pp. 3754-3766, 2013.

[28] P Bahl and V. N. Padmanabhan, "RADAR: an in-building RF-based user location and tracking system," in 19th Annual Joint

Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM '00), pp. 775-784, March 2000.

[29] P Bahl and V. N. Padmanabhan, "LANDMARC: indoor location sensing using active RFID," in Proceedings of the 1st IEEE International Conference on Pervasive Computing and Communications (PerCom '03), pp. 407-415, March 2003.

[30] S. Outemzabet and C. Nerguizian, "Accuracy enhancement of an indoor ANN-based fingerprinting location system using kalman filtering," in Proceedings of the IEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC '08), pp. 1-5, September 2008.

Jian Qiu, Xizhe Wang, and Guojun Dai

Institute of Computer Application Technology, Hangzhou Dianzi University, Hangzhou 310018, China

Correspondence should be addressed to Jian Qiu;

Received 1 December 2013; Accepted 8 February 2014; Published 20 March 2014

Academic Editor: Hongke Zhang

Copyright [c] 2014 Jian Qiu et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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(FC)              12.99%   3.50%    0.28%
P[(FC.sup.(1)])    13.75%   3.55%    0.28%
[T.sub.APx] (FC)   75.13%   29.97%   2.77%
P(CoL)             43.55%   91.02%   99.92%
COPYRIGHT 2014 Sage Publications, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article; cyberphysical systems
Author:Qiu, Jian; Wang, Xizhe; Dai, Guojun
Publication:International Journal of Distributed Sensor Networks
Article Type:Report
Date:Jan 1, 2014
Previous Article:Design and implementation of a field inspection management system based on wireless sensor networks.
Next Article:Spectrum sharing in cognitive radio using GSC with suppressed sidelobes.

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters