Wang et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:17

http://jwcn.eurasipjournals.com/content/2011/1/17

RESEARCH Open Access

Differential radio map-based robust indoor

localization

1* 1 1 2 1Jie Wang , Qinghua Gao , Hongyu Wang , Hongyang Chen and Minglu Jin

Abstract

While wireless local area network-based indoor localization is attractive, the problems concerning how to capture

the signal-propagating character in the complex dynamic environment and how to accommodate the receiver

gain difference of different mobile devices are challenging. In this article, we solve these problems by modeling

them as common mode noise and develop a localization algorithm based on a novel differential radio map

approach. We propose a differential operation to improve the performance of the radio map module, where the

location is estimated according to the difference of received signal strength (RSS) instead of RSS itself. The particle

filter algorithm is adopted to realize the target localization and tracking task. Furthermore, to calculate the particle

weight at arbitrary locations, we propose a local linearization technique to realize continuous interpolation of the

radio map. The indoor experiment results demonstrate the effectiveness and robustness of our approach.

Keywords: Indoor localization, differential radio map, RSS, particle filter

Introduction RSS measurements from various access points (APs) at

Ubiquitous computing and communication have become each cell, and thus a mobile device can be localized by

popular with the development of wireless communica- matching the observed RSS vector with the radio map.

tion technology over the last decade. The need for loca- In the indoor environment, the RF signal propagation is

tion information to capture contexts and configure unpredictable and affected by several factors, such as

them into the computing and communication processes, the presence and movement of human beings, relocation

coupled with the unavailability of global positioning sys- of furniture, multi-path fading, humidity and tempera-

tem (GPS) in indoor environment, has triggered ture variations, and closing or opening doors. In such a

increased research interest in indoor localization. dynamic environment, the radio map obtained in one

Recently, numerous localization systems have been time period may not be applicable to other time periods.

developed based on the received signal strength (RSS) of To solve this problem, Chen et al. [9] built multiple

the wireless local area networks (WLANs). The advan- radio maps under various environmental conditions and

tage of these systems is that the cost of deploying a spe- used sensors to identify the current environment so as

cialized infrastructure is avoided. However, building an to select the most approximate map. Yin et al. [10] off-

indoor localization system based on WLAN is a challen- set the variational environmental factors by adding some

ging problem due to the complex indoor signal propaga- reference points as sniffers to capture the dynamic char-

tion character and different hardware solutions of acters of the environment and rebuilt the radio map

with regression method. Although these methods par-different mobile devices.

tially overcome the negative effect of dynamic environ-Radio map-based approach is the most widely adopted

method to realize indoor localization [1-11]. The essen- ment, the need for specific infrastructures, such as the

tial idea is to construct the radio map by dividing the environmental sensors and sniffers, makes these meth-

whole deployment area into cells and then collecting the ods impractical. More recently, Fang and Lin [11]

adopted a temporal sequence of RSS samples as the

* Correspondence: wangjie@dlut.edu.cn character vector of the radio map so as to overcome the

1Faculty of Electronic Information and Electrical Engineering, Dalian multipath problem. While this approach demonstrates

University of Technology, No.2 Linggong Road, Ganjingzi District, Dalian,

the effectiveness for the multipath effect, it is of littleLiaoning Province 116024, People’s Republic of China

Full list of author information is available at the end of the article

© 2011 Wang et al; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons Attribution

License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium,

provided the original work is properly cited.Wang et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:17 Page 2 of 12

http://jwcn.eurasipjournals.com/content/2011/1/17

use for other problems. The question of how to adapt to and Seco et al. [15] reviewed the indoor localization

the dynamic complex environment without any addi- algorithms from the aspect of mathematic. In this sec-

tional infrastructure is a promising and challenging pro- tion, we give a brief overview of some key research find-

blem. Because with the changing of environment, it is ings in this area. Considering the needs of building the

most likely that the RSS measurements in one location radio map, we divide the methods into map-based and

from different APs are prone to shift in the same direc- non-map based algorithms.

tion, we can model the dynamic of the indoor environ- The principle of the radio map based method is to fin-

ment as the common mode noise. Inspired by the fact gerprint each cell of the deployment area with a RSS

that differential signals are widely used in the circuit measurement vector from various APs. A mobile device

design to restrain the common mode noise, we adopt is then localized by matching the observed RSS against

the difference of RSS from different APs as the charac- the radio map. To the best of our knowledge, radio

teristic signal of the radio map. Suppose the RSS mea- map-based indoor localization was first introduced by

surement vector from three APs are (RSS , RSS , RSS ). Bahl and Padmanabhan [1]; they proposed the well-1 2 3

Instead of treating it as the fingerprint to realize locali- known RADAR system and realized the localization

zation, we adopt the differential vectors (RSS -RSS , using the deterministic fingerprint. Since then some1 2

RSS -RSS , RSS -RSS ) as fingerprint. Compared with schemes have been proposed to reduce the manual cali-1 3 2 3

the traditional RSS vector, the differential vector can be bration effort and make the radio map more robust so

effectively adapted to the dynamic indoor environment. as to improve the localization accuracy. To reduce man-

Furthermore, it can accommodate the receiver gain dif- ual effort, Deasy and Scanlon [2] proposed a technique

ference of different mobile devices. We are aware that to estimate the radio map using a signal propagation

the receiver gains of even the same type of devices are model. They used an instrument to measure the signal

different, let alone different types of devices. If the propagation model parameters and built the simulated

device used in the localization phase is different from radio map automatically. Compared with the traditional

that used in the radio map building phase, then the esti- measured radio map, although the building of the simu-

mation error will be increased dramatically. Because the lated radio map is time efficient, the localization accu-

difference of receiver gain offsets the RSS measurements racy degenerates significantly. Tsai et al. [3] also

in the same direction, we can also model it as common adopted the signal propagation model and the interpola-

mode noise. tion technique to build the map. Chai and Yang [4] pro-

In this article, we propose a novel robust indoor loca- posed a scheme to reduce the sample location in the

lization algorithm under the framework of Bayesian fil- radio map building phase so as to reduce the manual

ter. The particle filter (PF) [12,13] is adopted to achieve effort and developed an interpolation technique to effec-

the localization and tracking task, which makes full use tively patch a radio map. Philipp [5] introduced a colla-

of the history observation to improve the estimation borative way to build the radio map with the

accuracy. The differential radio map is used for building collaboration of users, each user could create and man-

the observation likelihood for the PF algorithm so as to age the map, and the whole map can be built gradually

solve the dynamic environment and different receiver with the participation of more and more users. Recently,

gain problem. For the sake of predicting signal strength Chintalapudi et al. [6] also developed a collaborative

measurements at arbitrary locations so as to calculate localization system named EZ which did not require any

particle weight and improve localization accuracy, we knowledge about the RF environment. EZ adopted an

also adopt a local linearization technique to realize con- improved genetic algorithm to solve the constraint

tinuous interpolation of the radio map. equations defined by signal propagation models so as to

This article is organized as follows. Section II provides calculate the parameters of the APs and training points.

a brief overview of the indoor localization problem. In However, it requires the mobile device equipped with

Section III, the definition of the differential radio map is GPS, and it can work well only if there are enough APs

given, and the localization architecture is described from to provide excellent coverage. In order to make the

the view of system. The detailed implementation of our radio map more informative, Wu et al. [7] adopted the

differential radio map-based PF algorithm is presented probability distribution function (PDF) as the fingerprint

in Section IV. Section V validates our algorithm by eva- of the map. Youssef and Agrawala [8] also employed a

luations. Finally, the conclusion is drawn in Section VI. stochastic description of the radio map. As has been dis-

cussed above, with the purpose of adapting the radio

Related works map to the dynamic environment, Chen et al. [9], Yin et

Indoor localization with WLAN has been an active al. [10], and Fang and Lin [11] have made some pioneer-

ing research contributions. As a continuation of theseresearch area in the last decade. Honkavirta et al. [14]

schemes, our proposed approach adopts the differentialpresented a survey of location fingerprinting methods,Wang et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:17 Page 3 of 12

http://jwcn.eurasipjournals.com/content/2011/1/17

radio map to make the algorithm more robust and a training cells with their vertices set as the training

local linearization technique to realize continuous inter- points. Then, we perform off-line training to record RSS

polation of the radio map. measurements transmitted by each AP and store these

Besides the above research studies, some schemes measurements into the radio map. The radio map has

based on the deterministic and proba-bilistic framework the following form:

have also been developed. Lim et al. [16] used the trun-

Map = {p , R |i=1, ...,M}, R = {R |j ∈ N }, (1)i i i ij icated singular value decomposition to calculate the sig-

nal-distance map (SDM) based on the online where M is the total number of training points, p andi

measurements between the APs. Although the dynamic R indicate the location and fingerprint of the ith train-i

SDM makes it possible to capture the challenging ing point, respectively, N is the detected AP list at thei

dynamic indoor environment, the requirements of the ith training point, R is a Gaussian PDF represented byij

high AP density and the modification of commercial 2 2N(μ , σ ) σij with the mean μ , and covariance ,whichijij ij

AP’s software make the scheme impractical. Hossain et

is used to approximate the RSS measurements collected

al. [17] proposed a robust localization algorithm that

at the ith training point and transmitted by the jth AP.

could make use of multiple wireless techniques.

Unlike the traditional radio map which adopts the fin-

Schwaighofer et al. [18] first adopted the Gaussian pro-

gerprint R directly for localization, we adopt the differ-icess (GP) as a non-parametric tool to realize the

¯ential fingerprint which takes the R as input, and it isRi iapproximation of the radio map of cellular network. Fer-

calculated as follows:

ris et al. [19] introduced the GP into the WLAN-based

indoor localization. Compared with other regression ¯R = {R −R |j ∈ N , j = m}, R =max{R |j ∈ N }, (2)i ij im i im ij i

models, the GP takes into account the noise of the

where R is the strongest RSS measured at the ithimobservation and provides the ability to approximate

training point (the measurement with lower ID isnonlinear signal propagation model. Madigan et al. [20]

adopted when equal RSSs are measured), and R -R isij imadopted a Bayesian hierarchical approach to realize

2 2N(μ − μ ,σ + σ )represented by ij im .indoor localization, which eliminated the need of know- ij im

ing the locations of the training points. Huang et al. In theory, the propagation of radio signal is regulated

[21] proposed a similar Bayesian algorithm and intro- by a certain principle. The shadowing model is widely

duced the stochastic properties of measurement errors adopted to approximate the signal propagation character

and the reliability of the measurement data into the fac- in the indoor circumstance. With this model, R isij

tor graph framework so as to improve the accuracy. defined by

Wymeersch et al. [22] also proposed a Bayesian localiza-

R = G+P −L − 10βlog d +v, (3)ij j j ij10tion algorithm and took the cooperation of the nodes

into consideration to improve the accuracy. Feng et al. where G is the receiver gain, P is the transmittingj

[23] employed the compressive sensing theory to analyze power (dBm)ofthe jth AP, L is the signal attenuationj

the localization problem. The localization problem is power (dBm)atthedistanceof1m, b is the path loss

modeled as a sparse question and can be solved by the exponent, d is the Euclidean distance between the ithij

L1 minimization. While these methods cut down the training point and jth AP, and v represents the measure-

measurement effort and partially adapt to the dynamic ment noise. G + P -L is always represented by onej j

environment, they still require effort in terms of placing symbol and is called the received power at the distance

sniffers, modifying commercial AP’s software, obtaining of 1 m in other studies. To analyze the feature of the

the knowledge of AP placement, and of complex differential operation, we use three symbols to represent

computation. each factor here. The dynamic indoor environment

always causes the change of parameters L and b,andj

Differential radio map and system architecture the change of these parameters incur the change of the

In this section, we define the differential radio map and R As for different types of device, the receiver gain Gij.

analyze its ability to restrain the dynamic environmental is different, and thus the change of device causes the

noise and receiver gain difference. The architecture of change of R , as well.ij

the proposed localization system is presented thereafter. The differential RSS is calculated as

R −R =(P −P ) −(L −L ) − 10β(log d −log d )+v˜,ij im j m j m ij im (4)Differential radio map 10 10

The construction of the differential radio map is almost

where P -P is a constant which does not changej mthe same as that of the traditional radio map, except

with environment. While L and L change with thej mthat a differential operation module is introduced. First,

environment, they always offset to the same direction.

we divide the deployment area into equal square

Wang et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:17 Page 4 of 12

http://jwcn.eurasipjournals.com/content/2011/1/17

Consequently, the change of L -L is not significant estimation of time instantt- 1, p (x |y ) and p (x |y )j m t t-1 t t

compared with the change of L and L .Asfor10b are the prior and posterior PDF estimations of timej m

(log d - log d ), since log d - log d is less instant t, respectively.10 ij 10 im 10 ij 10 im

than log d and log d , the change must be insignif- The localization system follows the framework of10 ij 10 im

icant, too. From Equation 4, we can see that the term G Bayesian filter [12,13] and estimates the posterior PDF

is eliminated in the expression. Therefore, the differen- of the location recursively conditioned on all the mea-

tial RSS scheme is immune to the dynamic indoor envir- surements, y ,...,y . The essential of the Bayesian filter is1 t

onment, and can solve the problem caused by different the prediction process and observation update process,

receiver gains of multi-devices. which are defined as follows:

To validate the above theoretical analysis, we placed

two different types of mobile devices at the same loca- p(x |y )= p(x |y )p(x |x )dx , (5)t t−1 t−1 t−1 t t−1 t−1

tion and collected RSS measurements from two APs

located at different places. We used an Intel 4965AGN

p(y |x )p(x |y )t t t t−1wireless card and a TP-LINK TL-WN322G wireless p(x |y)= , (6)t t

card to gather RSS. There is a door between the p(y |x )p(x |y )dxt t t t−1 t

cards and APs, and we closed the door in the time

where the term p (x |x )representsthemotiont t-1instant 15-45. We define Int1 and Int2 as the RSS mea-

model, which describes the motion of the mobile device,surements, respectively, from AP1 and AP2 by

and p (y |x ) represents the observation likelihoodt t4965AGN, TP1 and TP2 as the RSS measurements by

model, which describes the likelihood of observing a dif-TL-WN322G, Int_dif as the differential signal of Int1

ferential RSS measurement vector y at a location x.Wet tand Int2, and TP_dif as the signal of TP1

describe the detailed models in the next section.and TP2. Figure 1 demonstrates that the change of the

differential RSS is quite insignificant compared with the

Implementation of the algorithm

change of RSS. It can also be seen that while the differ-

This section first gives a brief introduction of the PF

ence of the RSS measurements from the same AP with

algorithm, and then defines the motion model and

different devices is remarkable, the difference of differ-

observation model in detail.

ential RSS measurements is almost the same. The aver-

age differences between Int1 and TP1, Int2 and TP2 are

10.5 and 11.3, respectively, while that between Int_dif PF algorithm for localization and tracking

and TP_dif is only 0.8. Bayesian filter algorithms [24] have achieved great suc-

cess in handling the localization and tracking problem

System architecture through the sequential estimation of target’s state, coop-

The system flow of the proposed differential radio map- eration with the movement modeling, prior distribution

based localization system is plotted in Figure 2, where xt prediction, and posterior distribution estimation. Among

is the current estimated location information, y is thet these Bayesian filter algorithms, the PF algorithm

current observation, p (x |y )istheposteriorPDFt-1 t-1 [12,13] has emerged as a popular choice because of its

unique ability in dealing with the complex non-Linear

and non-Gaussian estimation problem. For these rea-

sons, we adopt the PF algorithm for localization in this

article. The PF algorithm approximates the probability

distribution of the estimated target with several

weighted particles, and deals with the sequential estima-

tion by carrying out a series of particle-propagating

i i

operations. Let {x , w |i=1, ..., N}denoteaparticlet t

iset, where x isasampleof x with associated normal-tt

iized weight . Then, the posterior PDF p (x |y)canbew t tt

approximated as

i ip(x |y ) ≈ w δ x −x ,t t tt t (7)

i=1

where δ () is the Dirac delta function. Suppose we

Figure 1 RSS measurements of different devices from different have the proposal distribution q (x |x , y ), then thet t-1 t

APs. ipredicted location x can be generated based on thet

Wang et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:17 Page 5 of 12

http://jwcn.eurasipjournals.com/content/2011/1/17

AP AP AP

Differential Differential

Transformation Transformation

Likelihood

Calculation

px y px y px y()() () tttt−−11 tt−1

Figure 2 Architecture of the localization system.

i two-dimensional location state x can be represented byprevious location x and the latest observation y as ttt−1

(X,Y). Suppose the location states of the previous twofollows: t t

time instants are, x and x , the predicted velocity ˆvt-2 t-1 t

i i ix ∼ q(x |x , y ), i=1, ..., N. (8)t and direction of the mobile device can be estimatedt t t−1 αt

as follows:iand w is given byt

2 2i i i v = min (X −X ) +(Y −Y ) ,v , (10)t t−1 t−2 t−1 t−2 maxp(y |x )p(x |x )t t t t−1i iw ∝ w . (9)t t−1 i iq(x |x ,y )tt t−1

Y −Yt−1 t−2Most articles in the literature define the proposal dis- α = arctan , (11)t

X −Xt−1 t−2tribution as q (x |x , y)= p (x |x ), which only consid-t t-1 t t t-1

ers the motion model and neglects the latest observation

where v is the velocity threshold of the mobilemax

y . For simplicity, we follow this scheme. Interestedt device and generally set as 1m/s. The motion model of

readers could find out the methods of designing

the particles can be written as

advanced proposal distribution in [25]. Now, the ques-

ii i i i ition is how to define the motion model p(x |x ) and X X +v cos(α )t +ntt t−1 t t−1 t t= , (12)i i i ii Y Y +v sin(α )t +nthe observation likelihood model p(y |x ) for the tt t t−1 t tt

particles.

where n is the noise,t π πi iv ∈ [0.6v,1.4v ],α ∈ α − ,α + . The new parti-t t t tt tMotion model 6 6

Speaking in general, the motion model of the mobile cles are generated in the fan-shaped area. Meanwhile, to

devices in the indoor environment is untraceable, and cope with the circumstance such as the swerve of the

the velocity and direction of the mobile device are hard mobile device, we randomly select 80% particles that

to estimate. In [19], Ferris et al. used a voronoi graph to participate in the prediction defined by Equation 12,

aid the motion prediction. Although the performance of and let the rest 20% particles randomly move in the cir-

the prediction is improved, it needs detailed floor plan cular area, with the last estimation as center and v asmax

of the building which is impractical and inconvenient. radius.

Jin et al. [26] adopted dead reckoning sensors to make

prediction, which needs the additional expensive sen- Observation likelihood model

sors. Based on the principle of making the system as In order to calculate the likelihood of the particles at

universal as possible, we define the motion model purely arbitrary locations, the first thing that should be solved

based on the historical motion information. We consider is to fulfill the radio map with the ability of representing

only two-dimensional localization, and the extension to the RSS measurements at arbitrary locations. The radio

map defined by Equation 1 is a discrete map, and onlythe three-dimensional scenario is straightforward. The

aR

dio MapWang et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:17 Page 6 of 12

http://jwcn.eurasipjournals.com/content/2011/1/17

the RSS fingerprints of the training points are recorded. where n is the number of detected APs. The exponent

We adopt a linearization technique to predict RSS mea- 1/n is used to smooth the likelihood so as to avoid the

surements at arbitrary locations. Within each of the occurring of overconfident estimate. We calculate the

square training cells, we use a hyperplane to approxi- observation likelihood values for all the particles and

i imate the RSS measurements of every AP. The 3D plane adopt as the new particle weight, and then,w p(y |x )t tt−1

equation includes (x, y, r) coordinate, where (x, y)isthe normalize it to ensure the summation of weights is

2D location, and r is RSS measurement. The equation is equal to 1.

defined as With the normalized weighted particle set

i i{x ,w |i=1,...,N}, the location estimation x can bett ta ×x+a ×y+a ×r = c,x y r (13)

N i icalculated as x = x w.Toavoidtheoccurrenceoft t twhere a , a,and a are the coefficients of the planex y r i=1

equation, and c is a non-zero constant and set as 1 in degeneration problem, we adopt the adaptive systematic

this article. The RSS measurements of the four vertices resample method [25] for further optimizing the quality

and their locations are known, therefore, they can be of the particles. The outline of our differential radio

used to calculate the coefficients of the hyperplane map-based Bayesian localization (DRMBL) algorithm is

equation. Suppose the locations of the four vertices are summarized in Table 1.

(x , y ), (x , y ), (x , y ), and (x y ), the mean values of1 1 2 2 3 3 4, 4

the RSS measurements from one AP are r , r , r,and Experimental evaluation1 2 3

r . We have a constraint matrix in the following form: In this section, we start by giving a detailed presentation4

of our testbed. Then, we evaluate the proposed improve-

A ·B = C, (14)

ment strategies under different conditions. For simplicity

and comparison, the deterministic fingerprint-basedwhere

RADAR algorithm adopts the weighted k-nearest neigh-⎡ ⎤ ⎡ ⎤

⎡ ⎤x y r 11 1 1 bor technique, abbreviated as KNN, and the algorithmax⎢ ⎥ ⎢ ⎥x y r 12 2 2 that adopts probabilistic fingerprint localization techni-⎢ ⎥ ⎣ ⎦ ⎢ ⎥A = , B = a , C = . (15)y⎣ ⎦ ⎣ ⎦x y r 13 3 3 que is abbreviated as PL. Furthermore, to evaluate thearx y r 14 4 4 effectiveness of our differential strategy, the differential

strategy is also applied to the KNN and PL algorithms.

The coefficients of the hyperplane equation can be

We define the improved algorithms as DRMKNN and

solved with the least square algorithm as

DRMPL, respectively.−1 -1 TT T , where () and () represent the matrixB = A A A C

inverse and transpose, respectively. After building the Experiment setup

hyperplane equation for every AP in each of the square To evaluate the performance of our algorithm, we per-

training cells, the mean value of RSS fingerprint at an formed realistic experiment on the second floor of the

arbitrary location can be calculated with Equation 13, Electronic Information building of Dalian University of

and the average value of the four vertices’ covariance is

set as the covariance of the location.

Table 1 DRMBL algorithmiFor the particle x, we first judge which training cell itt

1. Initialization: t=0,1belongs to and calculate the RSS fingerprint vector

Adopt the estimation of RADAR as the initial estimation.based on the hyperplane equation, and then, we trans-

2. While (t>1) doform the RSS fingerprint vector and the current,

2.1 Prediction updateobserved RSS measurement vector to their differential

A. Estimate the velocity and direction using Equations 10 andform. Suppose the differential fingerprint for the jth AP

112N(μ¯ , σ¯ )is ij , the observed differential RSS measure-ij B. Make prediction using Equation 12

o¯ment from the jth AP is , then the likelihood for thej 2.2 Observation update

2jth AP is N(o¯ ;μ¯ , σ¯ ). Suppose the RSS measurementsj ij A. Calculate the observation likelihood function of eachij

particle with Equation 16from different APs are independent, the observation

B. Calculate the normalized weight for each particlelikelihood can be expressed as

2.3 Adopt the weighted mean of the particles as the current

⎛ ⎞1/n location estimationn

i 2 2.4 Resample, if necessary⎝ ⎠p(y |x)= N(o¯ ;μ¯ , σ¯ ) , (16)t j ijt ij

Endj=1