Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Differential radio map-based robust indoor localization

12 pages
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.
Voir plus Voir moins

Wang et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:17
RESEARCH Open Access
Differential radio map-based robust indoor
1* 1 1 2 1Jie Wang , Qinghua Gao , Hongyu Wang , Hongyang Chen and Minglu Jin
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
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
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
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)
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
Differential Differential
Transformation Transformation
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
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
dio MapWang et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:17 Page 6 of 12
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