Xiaolong Xu,*,Yu Tang,Xinheng Wang2,and Yun Zhang

1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.School of Computing,University of the West of Scotland,Paisley PA1 2BE,United Kingdom

Variance-based finge print distance adjustment algorithm for indoor localization

Xiaolong Xu1,*,Yu Tang1,Xinheng Wang2,and Yun Zhang1

1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;
2.School of Computing,University of the West of Scotland,Paisley PA1 2BE,United Kingdom

The multipath effect and movements of people in indoor environments lead to inaccurate localization.Through the test,calculation and analysis on the received signal strength indication(RSSI)and the variance of RSSI,we propose a novel variance-based finge print distance adjustment algorithm(VFDA). Based on the rule that variance decreases with the increase of RSSI mean,VFDA calculates RSSI variance with the mean value of received RSSIs.Then,we can get the correction weight.VFDA adjusts the finge print distances with the correction weight based on the variance of RSSI,which is used to correct the finge print distance.Besides,a threshold value is applied to VFDA to improve its performance further.VFDA and VFDA with the threshold value are applied in two kinds of real typical indoor environments deployed with several Wi-Fi access points.One is a quadrate lab room,and the other is a long and narrow corridor of a building. Experimental results and performance analysis show that in indoor environments,both VFDA and VFDA with the threshold have better positioning accuracy and environmental adaptability than the current typical positioning methods based on thek-nearest neighbor algorithm and the weightedk-nearest neighbor algorithm with similar computational costs.

indoor localization,finge print localization,received signal strength indication(RSSI)variance,finge print distance.

1.Introduction

With the development and widespread of mobile devices and technologies,the demand for location-based service is becominghigherin bothindoorandoutdoorenvironments. People are pursuing more and more efficien and accurate positioning technologies and novel solutions for locationbased services.

The global positioning system(GPS)has already been able to provide accurate positioning and navigation functions outdoors.However,it is not suitable for indoor localization.The current approaches of indoor localization are based on the infrared ray,the radio frequency identifi cation(RFID),or the wireless fidelit(Wi-Fi),etc.Indoor localization has wide application prospect at complex and large public indoor environments,such as airports,hospitals,shopping malls and museums.

According to the difference of positioning principles, indoor positioning technologies can be roughly classifie into three types:the positioning technologies based on hardwaredevice,the positioningtechnologiesbased on the signaltransmissionmodelandthepositioningtechnologies based on the received signal strength indication(RSSI) [1–4].The positioning technologies based on hardware device usually need certain special auxiliary equipment, and calculate the physical location according to the information from the equipment,which easily leads to a cost increase and process complication.The positioning technologies based on the signal transmission model calculate the distance between the sender and the receiver by calculating the time of signal transmission.Thus,it can get the receiver’s physical location using a known emission source.Its limitation is that the signal does not always transmit along a straight line,because there are all kinds of obstacles between signal emission sources and receivers, which leads to complex reflection refraction,diffraction and inaccurate positioning.The whole process of the positioning technologies based on RSSI can be divided into two phases:the training phase and the positioning phase. During the training phase,it is needed to collect RSSIs of access points(APs)with certain physical addresses at every reference point(RP),which will be stored in order to build a fingerprin database(FD).During the positioning phase,it is also neededto collect RSSIs to match information in the FD for the purpose of getting the optimum information and realizing the localization.The representative RSSI-based positioning technologies are based on thenearest neighbor(NN)algorithm or the k-nearest neighbor (KNN)algorithm,which are easily affected by the multipath effect[2,3].

To sum up,the performanceof indoor localization technologies still has a huge improvement space,especially in positioning accuracy,environmental adaptability,hardware cost,and energy consumption.

In this paper,we are committed to develop a novel variance-based indoor fingerprin positioning method.The main contributions are summarized as follows:

(i)We implementexperimentsintwotypicalpositioning areas.We collect RSSIs,and analyze the relationship between the mean values and the variances.From the experimental results and the analysis,we fin out that the mean values increase with the variance decreasing,which means that the mean values of RPs far from APs are smaller than the mean values of RPs close to APs.

(ii)From the further study on the relationship between mean values and variances for AP,we fin out that this relationship is approximately linear.This relationship indicates that bigger signal values are more stable,and it can be used to decrease error of RSSIs.

(iii)Based on the abovediscoveries,we proposea novel variance-based fingerprin distance adjustment algorithm (VFDA).Different confidence are assigned to different RPs according to the variance of current locations.Compared with the current typical positioning methods based on KNN and the weighted k-nearest neighbor(WKNN) algorithm,VFDA can greatly decrease positioning errors and improve the positioning performance.

(iv)It is possible that received signal strength values deviate from its real values due to few times of collecting RSSIs when positioning.We utilize a threshold value to avoid useless calculation of fingerprin distance,which can decrease the effect of occasional signal strength fluc tuation,thus improving the positioning performance.

The rest of this paper is organized as follows.Some related algorithms and technologies are introduced in Section 2.The experiments and analysis,a new fingerprin distance definitio and the workfl wof VFDA are stated in Section 3.How to apply the thresholdto VFDA to improve the localization performance is stated in Section 4.Experimental results and performance analysis are provided in Section 5.Finally,Section 6 concludes this paper.

2.Related works

Positioning in indoor wireless environments is growing rapidly in importance and gains commercial interests in context-aware applications.

Milioris et al.introduced two indoor positioning techniques utilizing signal-strength(SS)fingerprint collected from APs[1].The approach employs a statistical representation of the received SS measurements by means of a multivariate Gaussian model by considering a discretized grid-like form of the indoor environment and by computing probability distribution signatures at each cell of the grid.At run time,the system compares the signature at the unknown position with the signature of each cell by using the Kullbac-Leibler divergence(KLD)between their corresponding probability densities.The second approach applies compressive sensing(CS)to perform the sparsitybased accurate indoor localization,while reducing signifi cantly the amount of information transmitted from a wireless device,possessing limited power,storage,and processing capabilities,to a central server.

Ault etal.introducedNN andKNNintolocalization[2]. If k=1,KNN will be the same as NN.The positioningalgorithm based on KNN can reach a high positioning accuracy.However,in some complex environments,the signal of transmission could be blocked,and the multipath effect makes the signal far fromAP unstable.Intensefluctuation of signals may lead to improperly choosing of candidate location points in a database,resulting in inaccurate positioning.

The effect of the number of APs on the performance of indoor localization was researched in[3]and[4].The experimental results in[3]show that the number of APs in the training phase should be equal or close to the number of AP in the positioning phase as much as possible, the number of APs should be more than four,and the distance of RPs ought to be two meters at least,otherwise the positioning result may be inaccurate.Koweerawong proposed a method to estimate the RSSI fingerprin of a specifi location from a set of neighboring re-measured RSSI fingerprints called“feedbacks”[5].The proposed method searches for new feedbacks and some necessary old RSSI fingerprint in the cut-off area and then applies plane-interpolation to calculate new RSSI fingerprint for a specifi location.

Reference[6]focuses on the properties of RSSI of ZigBee-based wireless sensor network,which can also be used to implement indoor location systems.The study collected a set of measurementsamples in a closed roomfrom an implementationofindoorlocalizationapplicationbased ontheZigBeeclusterlibraryframework.Themeasurement data are analyzed for their statistical parameters.The results are compared with the known properties of RSSI of wireless local area network reported in[6].The insight of RSSI’s properties obtained in this work could be used to improve the localization application using ZigBee-based wireless sensor network.Wu et al.studied the unexploited RF signal characteristics,leveraged user motions to con-struct radio floo plan,and then designed an indoor localization approach based on off-the-shelf Wi-Fi infrastructure and mobile phones[7].Lee et al.proposed a mapping system to build the RSSI-based fingerprin database for indoor localization[8].The mapping system has been developed practically to achieve two main objectives,fast and accurate radio-map construction.A map building algorithmwas proposedin[8]employingthe scan-matching, the graph-basedoptimization,and the probabilisticmedian filte with the gathered environmental data.

Li et al.used the concept of key reference tags to eliminate redundant reference tags of the system in real time location phase[9].Key reference tags can help to obtain the signal strength values of all referencetags by searching a database established in the off-line data collection phase. This approach uses fewer RFID reference tags without affecting the overall performance.Ferdous et al.surveyed the current technologies and algorithms used to identify and localize disable people simultaneously,and summarizes the localization approaches based on video cameras, RFIDs,andwearabledevices[10].Apositioningalgorithm based on the time of arrival(TOA)was proposed in[11], with which the distance from the emission source to the receiver can be calculated accurately.Tan pointed out that althoughTOAis notcompletelyrelatedtosignals,themultipath effect still leads to inaccurate localization[12].That is to say,due to the inevitable problem of bad base station layout,thepositioningalgorithmbasedonTOAmayeasily cause the problem of non-line of sight(NLOS).

Wang et al.proposed an RSSI-based infrastructure-free localization algorithm[13],which is based on Wi-Fi signals and able to reduce the database construction cost.By picking the hot spot,the algorithm can effectively alleviate the interference from other wireless signals in the nearby region,and can also enhance the RSSI-based matching algorithm and hence improves the localization accuracy. Rong et al.presented a mathematical model for localization average error[14],in which calculating the positioning error of the mathematical expectation of the targeted area shows how the number of access points,the distribution of access points,the grid spacing and the number of nearby neighbors influenc the positioning accuracy.

Fang et al.proposed to use the robust parameter of RSSI to reduce the error brought about by the multipath effect[15],which can reduce the rate of positioning error from 42%to 29%without any additional instrument.In fact,we are inspired by[15]to study further to improve the fingerprint-base localization algorithm.Lim et al.proposed to extract the robust signal feature from measured RSSIs so that the multipath effect can be mitigated efficientl[16].In[17],the popular IEEE802.11WLANis utilizedalongwitha micro-electromechanical system(MEMS)-based reduced inertial sensors system(RISS)to provide an accurate and smooth positioning system for wheeled vehicles inside buildings based on Wi-Fi RSSI.Lin et al.provided the preliminary results of WiFi positioning in a WiFi-Bluetooth-coexisting environment[18].RSSI is introduced as an observation applied to WiFi positioning.Then,[18]presents the basis of a fingerprintin approach to WiFi positioning and the interference in the WiFi-Bluetooth-coexisting environments.Yeha et al.proposed an adaptive-weighting locating mechanism within wireless heterogeneous networks [19],which enhances GPS’s ability to receive signals in buildings and precision in estimating locations.The multipath effect leads to large signal deviation,distance calculating error and positioning inaccuracy.In order to solve the problem of the multipath effect,a positioning method based on WKNN was proposed in[20],which assigns a weight to every RSSI received for calculating Euclidean distance as fingerprin distance.When the fingerprin distanceis calculated,biggerRSSIs will beassignedwith bigger weights.The performance of WKNN-based positioning is better than those methods based on KNN.

Reference[21]presents RADAR,a RF-based system for locating and tracking users inside buildings.RADAR operates by recording and processing signal strength information at multiple base stations positioned to provide overlapping coverage in the area of interest.It combines empirical measurements with the signal propagation model to determine the user’s location and thereby enable location-aware services and applications.

Reference[22]presents the design and implementation of Horus,a WLAN location system.Horus aims at two goals:high accuracy and low computational cost.Horus identifie different causes for the wireless channel variations and addresses them to achieve the high accuracy.It uses location-clustering techniques to reduce the computational requirements of the algorithm.Lightweight Horus cansupporta largenumberofusersbyrunningthelocating algorithm at clients.Reference[22]presents the different componentsofHorusandevaluatesits performanceontwo test beds.Experimental results show that Horus has less than 0.6 meter error on the average and its computational cost is better than other WLAN location systems.Moreover,Horus can also be applied to other location systems to enhance their accuracy.

Wang et al.used smartphone WiFi signals to track human queues[23],which takes a minimum infrastructure approach and thus utilizes a single monitor placed close to the service area along with transmitting phones.The strategy extracts unique features embeddedin the signal tracesto infer the critical time points when a person reaches the head of the queue and finishe his/her service,and from these inferences a person’s waiting and service times can be derived.

Reference[24]presents that the wireless data collected in mobile environments provide tremendous opportunities to build new applications in various domains such as vehicular ad hoc networks and mobile social networks.Storing the data decentralized in wireless devices brings major advantages over centralized ones.To facilitate effective access control of the wireless data in the distributed data storage,a fully decentralized key management framework was proposed by utilizing a cryptography-based secret sharing method in[24].The secret sharing method splits the keys into multiple shares and distributes them to multiple nodes.However,due to node mobility,these key shares may not be available in the neighborhood when they are needed for key reconstruction.To address this challenge, Zhenget al.proposedthetransitiveprediction(TRAP)protocol[24]that distributes key shares among devices that are traveling together,and developedthree key distribution schemes that utilize the correlation relationship embedded among devices that are traveling together.The key distribution schemes maximize the chance of successful key reconstruction and minimize the communication overhead.

Rappaport et al.introduced the wireless channel model in indoor localization[25]as follows:

where d is the distance between the device and the AP.As a general rule,d0is assigned 1 m in the positioning stage, PL(d)is the received signal power at distance d,PL(d0) is the signal power at distance d0,and Xσis the measured noise and n is the index loss of paths.

The indoor positioning channel model can be described as follows:

where x(t)is the transmitted signal,y(t)is the received signal,τkis the transmission delay of the kth path,ak(t)is the attenuation of the kth path,v(t)is the Gaussian noise in channel,and L is the total number of multipath.

In the indoor environment,the delay τkand the attenuation ak(t)vary with time because of the objects.It leads to large variances of received signals.When the terminal device is far from APs or there exists NLOS,this phenomenon will be more obvious.In this case,the second part of(2)will be very large or very small,which will lead to a verylarge varianceof RSSI.In contrast,if the terminal device is very close to the APs,y(t)is mainly affected by the firs part of(2),and the variance of RSSI is small.

3.VFDA

3.1 Problem analysis

Firstly,we implement several rounds of experiments in the real indoor environment to collect and analyze data about the signal fluctuation at the reference position caused by multipath effects.During the process of data collection, the factors of object moving and blocking are fully taken into account to make the test more realistic and credible. The data collection,measurement and analysis are mainly basedonwirelessroutersasAPs andmobileterminalswith the Wi-Fi function.The mobile terminals can move freely, and scan the RSSI values of APs continuously.Three real indoor environments are constructed with Wi-Fi access points deployed.Two of them are quadrate rooms,and another one is a long and narrow corridor of a building.We collect data of signals in both scenarios,and analyze the relationship between mean values of signals and variances of RSSI at any RP.

Liu et al.tested how some orientation affects the RSS readings due to blocking and reflectio of radio signals by human bodies,including user’s facing orientation,holding phone positions,number of samples taken at each location andtime of the day[26].Experimentalresults in[26]show that the positioning result varies with these factors changing.In our experimental environments,fve APs are deployed and the fingerprin database is built.The distances of RPs are set 0.6 m and 1 m for testing positioningresults. Each RP collects 300 values of RSSI during the training phase.During the following data analysis process,eight positioning test points are taken to calculate variances and mean values.At each point,we collect 20 sets of data.We also take the time of the day into consideration and implement experiments in different time of the day,as the RSSI varies with the time changing.

As shown in Fig.1,both in the morning and at night, the variances increase with the mean values of RSSI decreasing.The strength of signals at the RP closed to AP is stronger,and the signal fluctuatio is smaller.Besides, in the quadrate rooms,the location points with low RSSI values which are far from APs have larger RSSI fluctua tions,and the variances are also bigger.Through the linear match,we can fin the variances and the mean values are approximately in a linear relationship.

According to the analysis above,we can draw the conclusionthatthe variancesof RSSI varywiththe differences of RSSI values and distances.If a mobile terminal is farfrom an AP,the measured RSSI at that point is low,has a large variance and becomes unreliable.If KNN is used to calculate fingerprin distances,and different RSSIs will be given different confidenc based on the measured mean valuesandvariances,theeffectoflargevariancemaybereduced.That is why VFDA is proposed in this paper,which determines the adjusting weight based on the linear relationship between RSSI variances and mean values so as to adjust the measured RSSIs with high variances.

Fig.1 Relationship between mean values and variances

3.2Fingerprint distance

The KNN-based localization algorithm is based on RSSI. Inthetrainingphase,RSSIsofAPs arecollectedandstored in the fingerprin database.In the positioning phase,EuclideandistancesbetweenRSSIs storedinthedatabaseand RSSIs just measuredwill be calculated,andadoptedas fin gerprintdistances.Thenthesmallestkvaluesoffingerprin distances will be chosen with their corresponding coordinates to calculate the average value as the positioning result[4].The KNN-based localizationalgorithmdefine the fingerprin distance as:

whereNis the total number of AP stations,riis theith signal value measured in the positioning phase,sijis theith AP’s RSSI at thejth RP,andD(j)is the fingerprin distance between RSSIs measured in the positioning phase and the training phase at thejth RP.

From the fingerprin distance definitio of KNN,it is easy to fin that all RSSIs collected are with the same configuration There is obviously a shortcoming that if an RSSI collected is distant to its expected mean value due to the multipath effect,the fina fingerprin distance will be larger,but other collected values are still normal.This occasionalerrorwillmakeKNNunabletochoosetheoptimalkRP to achieve accurate localization.

Since the error of measurement cannot be avoided completely,we need to reduce the effect of error measurement and rely on these RSSI values close to those values collected in the training phase and stored in the fingerprin database to make positioning results accurate.

Due to the reason above,we defin a new improved fin gerprint distance as follows:

wherediis the adjustingweightassignedto each measured RSSI valueri.Credibility is introducedhere for evaluating the credible level of the accuracy of fingerprin distance. When calculatingfingerprin distance,it is necessary to assign high credibilityto accurate measuredRSSI values and low credibilityto inaccurateones.Thus,the positioningresults can be adjusted effectively.

We have two key problems to deal with:one is how to judge whether a measurement is accurate or not;the other is how to get the optimum adjusting weight to efficientl reduce the error of fingerprin distance.

3.3Measurement errors

Measurement errors can be found during the positioning phase.However,the level of error is not given directly by the measurement value itself.So we need to get a large amount of detailed information from the fingerprin database.As the above experiment analysis shows,there exists a linear relationship between the variance and the mean value as

whereV aris the variance of measurement value,Meanrepresents the mean value of measurement,anda,bareparameters of the linear relationship equation.In the positioning phase,measurement values are calculated with(5) to getV ar.

3.4Adjusting weight

The basic idea of adjusting weight is to assign higher weights to measurements with smaller errors,and assign lower weights to those with bigger errors.So we should separate RPs close to APs from those distant to APs in order to choose thek-nearest RPs more correctly.

According to the relationship between the variance and the mean value of RSSI,variances tend to be large while RSSI mean values are small,and can be calculated with (3).In order to reduce errors caused by large variances, small weights should be assigned to them,and the reciprocal of variances can be used as the weight.

It is necessary to point out that although there is only variances in(4),the calculation of variances needs mean values.Though the calculation of variances used the approximate linear relationship and the variance cannot be exactly accurate,this method is surely qualitative to reach the target of adjusting error.

The calculation method of adjusting weight is as follows:

whereV ariis the variance of RSSI measured from theith AP,and the total weight should satisfy

3.5Establishment of the finge print database

Based on the definitio provided with(4),we propose VFDA,which also consists of two phases,the training phase and the positioning phase.

In the training phase,the fingerprin database is established to store information as the matching basis of the positioning phase.The process of the fingerprin database establishment includes two steps:

Step 1The mobile terminal scans signals at reference locations to collect RSSIs from APs,and stores the coordinates(x,y)of physical locations,mean values,and variances into the database.

Step 2The server calculates parametersaandb,and then stores them in the database.

In the positioning phase,VFDA uses RSSI values,(3) and parametersaandbto calculate the current RSSI variances in order to get the adjusting weights.

3.6Process of VFDA

With VFDA,the mobile terminal scans and collects signals fromNAPs at any RP within the positioning area, gets several sets of RSSI values,and then gets the mean value of each RSSI.

The process of VFDA includes the following steps:

Step 1Estimate the variances of RSSIs with the mean values of measurement and(3).

Step 2Use(4)to calculate the adjusting weights.

Step 3Use(2)to calculate the fingerprin distances.

Step 4Obtain the physical location of the mobile terminal.

To sum up,VFDA obtains fingerprin distances via calculating the Euclidean distance,uses arrays to store parametersaandbof each AP,and travels through the list of the mean values of signals,multiplied by the adjusting weights,and finall gets the corrected fingerprin distances.

4.VFDA with the threshold value

4.1The threshold value of RSSI

According to the calculation and analysis for the positioning process above,we know that the measured received signal strength value may deviate from its real value due to few times of collecting RSSIs during positioning.In other words,though RSSIs are corrected with large deviations when calculatingdiwith(6),but the deviations are not consideredwhen calculatingri?sijwith(4).Therefore,it is necessary to utilize a threshold value to avoid large deviations for some APs when calculatingri?sij.Countercjis set 0 as its initial value.Ifri?sijis more than the thresholdvalue,cjwill be added1,and the thresholdvalue will be assigned tori?sij.Finally,ifcjreaches a rated value,this related point will be ignored.

4.2Workfl w

The purpose of setting the threshold value is to avoid useless calculation of fingerprin distances,which may decreasetheeffectsofoccasionalsignalstrengthfluctuations The following is the detailed process of VFDA with the threshold value:

(i)Workfl w in the training phase

Step 1The mobile terminal scans signals and collects RSSIsfromAPs.Theterminalsavesthecoordinates(x,y), the average values and the variance values of RSSIs in the database.

Step 2The server calculates the parametersa,bwith the average values and the variance values of RSSIs for all APs,and these values are also saved in the database.

Step 3For each related point,according to RSSI from

APs,the server calculates the absolute value between the averagevalueofRSSI andcollectedRSSI valuesfortherelatedpoints,andchoosesthemaximumvalueas thethreshold value:

whererssinis thenth collected RSSI value for theith AP at thejth related point.

(ii)Workfl w in the positioning phase(as shown in Fig.2)

Fig.2 Workfow during the positioning phase

Step 1Estimate the variances of RSSIs with the mean values of the measurement and(5).

Step 2Use(6)to calculate the adjusting weights.

Step3Calculate|ri?sij|,andthencompareit withTj. If|ri?sij|≥Tj,|ri?sij|=Tj,and add 1 tocj.Finally, ifcj≥4,do not implement the calculation of fingerprin distance forthis related point and rule out the possibility of it becoming the nearest neighbor point.

Step 4The related point which is not been ruled out would be calculated with(4).

5.Experiments and performance analysis

5.1Experimental environment

WechosethreerealindoorenvironmentswithWi-Fi access points already deployedas the experimentalenvironments. Two of them are quadrate rooms of different measurements,where walking people and obstacles bring about lots of random factors.Another is a long and narrow corridor of a building,which has fewer obstacles and moving objects,i.e.less interference.

Koweerawong et al.has already proved the influenc of the number of AP[3].In our indoor environments,fve TP-LINK TL-WR720N wireless routers are taken as APs. Several mobile terminals are installed with Android OS andthe Wi-Fi module,andthe terminalcan scanWi-Fi signals and collect RSSIs.The mobile terminals are equipped with 16 GB ROM,1 GB RAM and an Exynos 4412 CPU with 4 cores.The distance between any two neighbor reference points is all set 0.6 m or 1 m.And these emission resources are set against walls.In the training phase,each RP for each AP collects 300 RSSI values.

5.2Positioning accuracy indicators

When testing the positioning accuracy of an algorithm,the mostcommonindicatorforevaluatingthepositioningerror is theerrorof distance:

wherexlandylare real coordinates of physical locations, andxrandyrare results obtained via experiments.

We measure and obtain ten sets of data,and draw fgures of the cumulative distribution function(CDF)as the indicator of positioning capability.

5.2Experiments in two lab rooms

KNN is one of the most popular algorithms used in fingerprint-base indoorlocalization approaches[2,3],and the positioningalgorithmbased on WKNN has a better positioning accuracy[20].In this paper,we compare VFDA andVFDAwiththethresholdvaluewiththepositioningalgorithmsbased on KNN and WKNN throughexperiments.

Firstly,we implement several rounds of experiments in two quadrate lab rooms with different sizes,as shown in Fig.3,Fig.4 and Fig.5 show the real path and the paths based on experimental results with the four algorithms in the two lab rooms.

Fig.3 Indoor localization maps

Fig.4 Results with four algorithms in Room 1

Fig.5 Real path and the paths based on experimental results with four algorithms in Room 2

Fig.4 and Fig.5 shows that the paths based on experimental results with VFDA and VFDA with the threshold value are more accurate than the positioning algorithms based on KNN and WKNN,which indicates that both VFDA and VFDA with the threshold value have better positioning performances than the positioning algorithms based on KNN and WKNN.

TheCDF showsthepositioningerrorsdistributioninexperiments.For example,(x,y)in the figur meansY(x)=P(X|X≤x),and it shows the percentage of the positioning results that errors are smaller thanx.

Table 1 shows part CDFs of the four algorithms in the same lab rooms.The firs part of this table shows part data of CDFs in Room 1,while the second part of it shows part data of CDFs in Room 2.

Table 1 indicates that both VFDA and VFDA with the thresholdvaluehavesmallercumulativeerrorsthanthe positioning algorithms based on WKNN and KNN.VFDA with the threshold value has even lower positioning cumulative errors than VFDA.Fig.6 shows the CDFs of these four algorithms in the lab rooms.

As shown in Table 1 and Fig.6,all positioning errors of WKNN and KNN are less than 13 m,and most of them are less than 6 m;while VFDA and VFDA with the thresholdvalue ensure that all positioning errors are less than 4 m, 80%of which are even less than 3 m.Briefl,VFDA is more stable and accurate than KNN and WKNN.The VFDA with the threshold value has a little improvementto VFDA.

Table 1 CDFs of the four algorithms in two lab rooms(Part)

Fig.6 CDFs of four algorithms in two lab rooms

5.3 Experiments in corridor

We choose a corridor of a building as another typical indoor environment to test our algorithms.Fig.4 shows the real location and locations based on experimental results with these four algorithms in the corridor.

Table 2 shows ten groups of CDFs of four algorithms in the corridor,which indicates that VFDA has smaller cumulative errors than WKNN and KNN.VFDA with the thresholdvaluehasevensmallerpositioningcumulativeerrors than VFDA.Fig.7 is the CDF of the four algorithms in the corridor.

Table 2 CDFs of the four algorithms in the corridor

Fig.7 The real location and locations based on experimental results with these four algorithms in the corridor

Fig.8 shows that these fouralgorithms all have accurate localization results in the corridor due to less interference thanthelab room.However,thepathsofVFDAandVFDAwith the threshold value are more accurate than the algorithms based on KNN and WKNN,indicating that VFDA and VFDA with the threshold value have better positioning performances than the algorithms based on KNN and WKNN.

Fig.8 CDFs of the four algorithms in the corridor

From Fig.6 and Fig.8,we can fin out that VFDA and VFDA with the threshold value has a higher positioning accuracy than the algorithms based on WKNN and KNN, especially in complex environments.

5.4 Analysis on computing cost

VFDA needs to use(5)to calculate variances,parameters and adjusting weights in the positioning phase,which brings the extra computing cost.However,the time complexities of the four algorithms are almost the same.

Table 3 shows the computing costs of these four methods.The firs line of the table shows the ROM usage,the second line shows RAM usage percentages,the third line shows the time for positioning,and the last line shows the remaining power of the battery after one hour positioning. FromTable 3,we canfin thatthecomputingcostsofthese four methods are similar.

Table 3 Computing costs of the four algorithms

6.Conclusions

Unstable RSSI values caused by the multipath effect lead to the inaccuracy of indoor localizations.In order to solve this problem,we propose a method based on the relationship between variances and mean values to adjust fingeprintdistances.Fromthe experimentalresults andthe analysis,we fin out that the mean values increase with the variance decreasing,which means that the mean values of RPs far from APs are smaller than the mean values of RPs close toAPs.Fromthe furtherstudyon therelationshipbetween the mean value and the value for certain AP,we fin out that this relationship is approximately linear.

Based on above discoveries,we put forward an improvedindoorfingerprin positioningapproachVFDA,and then enhance the performance of VFDA with the threshold value.We assign different confidenceto different RPs according to the variance of current locations.Comparedwith KNN and WKNN,our proposedalgorithmscan greatly decrease positioning errors and improve the positioning performance.In the future,we are going to integrate Wi-Fi and RFID together to realize more accurate localization based on the data fusion.

[1]D.Milioris,G.Tzagkarakis,A.Papakonstantinou,et al.Lowdimensional signal-strength fingerprint-base positioning in wireless LANs.Ad hoc Network,2014,12(1):100–114.

[2]A.Ault,X.Zhong,E.J.Coyle.K-nearest neighbor analysis of received signal strength distance estimation across environments.Proc.of the 1st Workshop on Wireless Network Measurements,2005:1023–1032.

[3]C.Koweerawong,K.Wipusitwarakun,K.Kaemarungsi.Indoor localization improvement viaadaptive RSS fingerprintin database.Proc.oftheInternational Conference onInformation Networking,2013:412–416.

[4]J.Machaj,P.Brida,B.Tatarova.Impact of the number of access points in indoor fingerprintin localization.Proc.of the 20th International Conference on Radioelektronika,2010: 1–4.

[5]C.Koweerawong,K.Wipusitwarakun,K.Kaemarungsi.Indoor localization improvement via adaptive RSS fingerprint ing database.Proc.of the 10th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology,2013:412–416.

[6]K.Kaemarungsi,R.Ranron,P.Pongsoon.Study of received signal strength indication in ZigBee location cluster for indoor localization.Proc.of the 10th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology,2013:1–6.

[7]C.S.Wu,Z.Yang,Y.H.Liu,et al.WILL:Wireless indoor localization without site survey.IEEE Trans.on Parallel and Distributed Systems,2013,24(4):839–848.

[8]Y.C.Lee,S.H.Park.RSSI-based fingerprin map building for indoor localization.Proc.of the 10th International Conference on Ubiquitous Robots and Ambient Intelligence,2013:292–293.

[9]W.F.Li,J.Wu,D.Wang.A novel indoor positioning method based on key reference RFID tags.Proc.of the IEEE Youth Conference on Information,Computing and Telecommunication,2009:42–45.

[10]S.Ferdous,K.Vyas,F.Makedon.A survey on multi-person identificatio and localization.Proc.of the 5th International Conference on Pervasive Technologies Related toAssistive Environments,2012.DOI:10.1145/243097.2413143.

[11]H.Liu,H.Darabi,P.Banerjee,et al.Survey of wireless indoor positioning techniques and systems.IEEE Trans.on Systems,Man,and Cybernetics,Part C:Applications and Re-views,2007,37(6):1067–1088.

[12]F.Tan,X.Lu,S.L.Tu.Location fingerprin system based on TOA.Computer Systems and Applications,2010,19(3):137–141.

[13]X.J.Wang,Z.Xue,Y.P.Zen,et al.Design of infrastructurefree Wi-Fi indoor localization.Journal on Communications, 2012,33(Z2):240–243.

[14]X.F.Rong,N.Yang.Location error analysis and simulation of location fingerprintin technology based on RSSI.Journal of Xi’an Technological University,2010,6(1):574–578.(in Chinese)

[15]S.H.Fang,T.N.Lin,K.C.Lee.A novel algorithm for multipath fingerprintin in Indoor WLAN environments.IEEE Trans.on Wireless Communications,2008,7(9):3579–3588.

[16]J.S.Lim,W.H.Jang,G.W Yoon,et al.Radio map update automation for Wi-Fi positioning systems.IEEE Communications Letters,2013,17(4):693–696.

[17]M.M.Atia,M.Korenberg,K.Noureldin.A Wi-Fi-aided reduced inertial sensors-based navigation system with fast embedded implementation of particle filteringProc.ofthe 8th International Symposium on Mechatronics and its Applications, 2012:1–5.

[18]P.Lin,L.Jingbin,R.Guinness,et al.The evaluation of Wi-Fi positioning ina Bluetooth and Wi-Ficoexistence environment.Proc.of the International Conference on Ubiquitous Positioning,Indoor Navigation,and Location Based Service,2012: 1–6.

[19]S.C.Yeha,W.H.Hsu.Adaptive-weighting schemes for location-based services over heterogeneous wireless networks.Proc.of the Vehicular Technology Conference,2010: 1–4.

[20]B.Shin,J.H.Lee,T.J.Lee,et al.Enhanced weighted K-nearest neighbor algorithm for indoor Wi-Fi positioning systems.Proc.of the 8th International Conference on Computing Technology and Information Management,2012:24–26.

[21]P.Bahl,V.N.Padmanabhan.RADAR:an in-building RF-based user location and tracking system.Porc.of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies,2000:775–784.

[22]M.Youssef,A.Agrawala.The Horus location determination system.Wireless Networks,2008,14(3):357–374.

[23]Y.Wang,J.Yang,H.B.Liu,et al.Measuring human queues using WiFi signals.Proc.of the 19th Annual International Conference on Mobile Computing&Networking,2013:235–238.

[24]X.Y.Zheng,Y.Y Chen,H.Wang,et al.Neighborhood prediction based decentralized key management for mobile wireless networks.Wireless Networks,2013,16(9):1387–1406.

[25]T.S.Rappaport.Wireless communications:principles and practice.Beijing:Publishing House of Electronics Industry, 2004.

[26]H.B Liu,Y.Gan,J.Yang.Push the limit of WiFi based localization for smartphones.Proc.of the 18th annual international conference on Mobile computing and networking,2012:305–316.

Biographies

Xiaolong Xuwas born in 1977.He received his B.S.degree in computer and its applications, M.S.degree in computer software and theories and Ph.D.degree in communications and information systems from Nanjing University of Posts &Telecommunications,Nanjing,China,in 1999, 2002 and 2008,respectively.He worked as a postdoctoral researcher at Station ofElectronic Science and Technology,Nanjing University of Posts&Telecommunications from 2011 to 2013.He is currently a professor in College of Computer,Nanjing University of Posts&Telecommunications.He is a senior member of China Computer Federation.His current research interests include cloud computing,mobile computing,intelligent agent and information security.

E-mail:xuxl@njupt.edu.cn

Yu Tangwas born in 1989.He received his B.S. degree in computer science and technology from Nanjing University of Posts&Telecommunications, Nanjing,China,in 2012.He is currently a postgraduate student majored in software engineering.His current research interests include mobile computing and in door localization technologies.

E-mail:1012041122@njupt.edu.cn

Xinheng Wangwas born in 1968.He received his B.Eng.and M.S.degrees in electrical engineering from Xi’an Jiaotong University,Xi’an,China,in 1991 and 1994,respectively,and Ph.D.degree in computing and electronics from Brunel University, Uxbridge,U.K.,in 2001.He is currently a professor of networks with the School of Computing,University of the West of Scotland,Paisley,U.K.His current research interests include wireless networks,Internet of things,converged indoor positioning,cloud computing,and applications of wireless and computing technologies for health care.He has close engagement with industry.

E-mail:Xinheng.Wang@uws.ac.uk

Yun Zhangwas born in 1963.He received his B.S. degree in computer communication at Beijing University of Posts&Telecommunications,Beijing, China,M.S.degree in communications and information systems at Nanjing University of Posts& Telecommunications,Nanjing,China,and Ph.D.degree in computer and its applications at Suzhou University,Suzhou,China,in 1985,1991 and 2009,respectively.He is currently a professor in College of Computer,Nanjing University of Posts&Telecommunications.He is a member of China Computer Federation.His current research interests include cloud computing,mobile computing and SDN.

E-mail:zhangyun@njupt.edu.cn

10.1109/JSEE.2015.00130

Manuscript received October 30,2014.

*Corresponding author.

This work was supported by the National Natural Science Foundation of China(61202004;61472192),the Special Fund for Fast Sharing of Science Paper in Net Era by CSTD(2013116),and the Natural Science Fund of Higher Education of Jiangsu Province(14KJB520014).