International Journal of Wireless Information Networks,Vol.9,No.3,July2002(᭧2002)
A Probabilistic Approach to WLAN Ur Location Estimation
Teemu Roos,1,3Petri Myllyma¨ki,1Henry Tirri,1Pauli Misikangas,2and Juha Sieva¨nen2
We estimate the location of a WLAN ur bad on radio signal strength measurements performed
by the ur’s mobile terminal.In our approach the physical properties of the signal propagation are
not taken into account directly.Instead the location estimation is regarded as a machine learning
problem in which the task is to model how the signal strengths are distributed in different geographical
areas bad on a sample of measurements collected at veral known locations.We prent a
probabilistic framework for solving the location estimation problem.In the empirical part of the
paper we demonstrate the feasibility of this approach by reporting results of field tests in which a
probabilistic location estimation method is validated in a real-world indoor environment.
KEY WORDS:Location estimation;mobile terminals;WLAN;machine learning;probabilistic modeling. 1.INTRODUCTION ur of the location-aware device.It is often uful to be
able to locate a group of other friends,co-Location-aware computing is a recent interesting workers,or customers.
rearch area that exploits the possibilities of modern The location of a mobile terminal can be estimated communication technology[1–4].Location-aware de-using radio signals transmitted or received by the terminal vices can be located or can locate themlves;by location-[5–11].The problem has various names:location estima-aware rvices we mean rvices bad upon such loca-tion,geolocation,location identification,location deter-tion technologies.Location-aware computing has great mination,localization,positioning,and so on.Some potential in areas such personal curity,navigation,tour-
location estimation methods,such as GPS,are bad on ism,and entertainment.The most obvious location-bad
signals transmitted from satellites,whereas others rely on rvice is the one answering questions like“Where am
terrestrial communication.Additional costs to the rvice I?”and“Where is the nearest shop/bus-stop/fire-exit?”.
provider are minimal in systems bad on existing net-Using graphical and interactive terminals it is possible
work infrastructure.For instance,the cell-ID method,in to implement an application prenting a map labeled with
which the location of the nearest ba station is reported a mark pointing“You are here”.Furthermore,location
as a location estimate,is applicable in most networks. information can also be uful for other people than the
However,the location estimation accuracy of such sys-
tems is often inadequate for many location rvices.
Improving the accuracy of location estimation systems 1Complex Systems Computation Group,Helsinki Institute for Informa-
tion Technology,P.O.Box9800,02015HUT,Finland.cosco.bad on the existing network infrastructure would be hiit.fi very uful,and it is the main motivation of this work. 2Ekahau Inc.,Salomonkatu17B,00100Helsinki,Finland.
We focus primarily on wireless local area networks
3Phone:ϩ358-9-85011286.Fax:ϩ358-9-6949768(WLANs),but most of the ideas and concepts are applica-
155
1068-9605/02/0700-0155/0᭧2002Plenum Publishing Corporation
156Roos,Myllyma¨ki,Tirri,Misikangas,and Sieva¨nen ble to many other networks as well,including tho bad domain,natural loss functions are obtained from the dis-
tance between the location estimate and the true location on GSM/GPRS,CDMA,or UMTS standards.
The traditional,geometric approach to location esti-and its positive powers,in particular the square of the
error.
mation is bad on angle and distance estimates from
which a location estimate is deduced using standard Various machine learning methods can be applied
in the location estimation domain.In ca-bad methods, geometry.We will discuss location estimation from a
point of view that is different from the traditional one.for instance,the training examples or a part thereof are
stored in a databa that is accesd during the location Our probabilistic approach is bad on an empirical model
that describes the distribution of received signal power estimation process.A prime example of a ca-bad
method is the nearest neighbor method,which we will at various locations.The model is ud to estimate the
mobile unit’s location when the received power is discuss in Section3.
To describe an alternative,probabilistic approach, obrved.The u of probabilistic models provides a
natural way to handle uncertainty and errors in signal we will now introduce some notation.We denote random
variables and their values by the same lowerca letters. power measurements.Our approach is very similar to工程建设程序
hope的过去式that ud in[8],but we address the location estimation In particular,l denotes location,and o denotes an obrva-
tion variable or vector.We assume that the obrvation problem in a more general tting whereas Castro et al.
focus on the problem of identifying the room where the variable is a vector of received signal strength values for
a t of access points in a communication network.The ur is in.We also demonstrate the feasibility of our
approach in a systematic empirical ca study in which training data D consists of n examples,denoted by(l i o i),
for i⑀{1,...,n},where n is the number of training an average location estimation accuracy of less than2
meters amples.With a slight abu of notation,we u the
general notation p(и)to denote all probability distribu-The paper is organized as follows:We shall first
explain the basic principles of the probabilistic approach tions,for either discrete or continuous variables.Condi-
tional probabilities are denoted by p(иȊи).
in Section2;more discussion on the probabilistic
approaches to density estimation and predictive modeling In this work we are mainly interested in the u of
probabilistic models for the location estimation problem. in general can be found in[12–15].In Sections3–5we
describe some location estimation methods bad on the In particular,we u models that estimate the probability
distribution of the obrvation variable given the value approach.In Section6we prent a ca study in which
the methods are applied in a real-world indoor test envi-of the location variable.In other words,for any given
location l we can obtain a distribution p(oȊl).By applica-ronment.The conclusions are summarized in Section7.
tion of the Bayes rule,we can then obtain the so-called
posterior distribution of the location:
2.LOCATION ESTIMATION AS A MACHINE火字旁的字
p(lȊo)ϭp(oȊl)p(l)
p(o)
ϭp(oȊl)p(l)
⌺lЈ⑀ᏸp(oȊlЈ)p(lЈ)Ј(1)
LEARNING PROBLEM
Machine learning can be characterized as the task of where p(l)is the prior probability of being at location l
before knowing the value of the obrvation variable,and automatic learning from examples.In location estimation,
machine learning can be ud in the following way.We the summation goes over the t of possible location
values,denoted byᏸ.If the location variable is continu-first collect a t of calibration data consisting of signal
measurements collected from various locations,each ous,the sum should be replaced by the corresponding
integral.The prior distribution p(l)gives a principled measurement labeled with the correct location.The cali-
bration data is ud in constructing a model,which can way to incorporate background information such as per-
sonal ur profiles and to implement tracking.For sim-be later ud as an estimator of the unknown location
given some new signal measurements.In machine learn-plicity we u here only uniform priors that introduce no
bias toward any particular location.Becau the denomi-ing terms,such a procedure is often called pattern recog-
nition or pattern classification.For a classic text on nator p(o)does not depend on the location variable l,it
can be treated as a normalizing constant whenever only pattern recognition e[16].
In the so-called testing pha,location estimation relative probabilities or probability ratios are required.
The term p(oȊl)is called the likelihood function performance is measured using some loss(or error)func-
tion bad on the location estimate and the true location.becau it gives the probability of the obrvation given
the assumed source of the obrvation,in our ca the Testing is bad on a t of test data collected indepen-
dently of the calibration data.In the location estimation location.There are veral implementation possibilities
A Probabilistic Approach to WLAN Ur Location Estimation157 for the estimation of the likelihood function from data. 3.NEAREST NEIGHBOR METHOD
In Sections4and5we prent two examples,the kernel
method and the histogram method.The prior being uni-For comparison purpos we will now prent the form,the likelihood function completely determines the so-called nearest neighbor method.It is bad on some posterior distribution of the location.Therefore it is of context-dependent distance measure that assigns a non-utmost importance to obtain a likelihood function that negative distance value between any two obrvation vec-describes the distribution of the obrvables at all loca-tors.We will u the simple Euclidean distance evaluated tions as well as possible.from obrvation ,the received signal strength In principle it is also possible to obtain a likelihood values of various access points.A special heuristic is function without any calibration data by using knowledge required for handling the missing values associated with of radiowave propagation and the environment.Several the cas in which the signal of some access points are propagation prediction or cell planning tools are available not obrved at all.In this work we cho to simply for the purpo[17–20].A few experiments of location replace the missing values with some constant smaller estimation bad on propagation prediction have been than any of the measured values.Given a t of training prented[5,21].The results correspond to our experi-data and a test obrvation vector,the location estimate ences—which we will not elaborate in the prent is obtained from the training example who obrvation paper—suggesting that the propagation prediction–bad vector has the minimal distance when compared with the methods are competitive
against the traditional,geometric test obrvation;hence the name“nearest neighbor”. methods(e below)but not against the machine learn-The nearest neighbor method has been ud for loca-ing approach.tion estimation[5,22,23].Bahl et al.pre-process the train-The posterior distribution p(lȊo)can be ud to ing data by combining all examples collected from the choo an optimal estimator of the location bad on same location into one training example who obrva-whatever loss function is considered to express the desired tion vector is the mean vector of the combined vectors. behavior.For instance,the squared error penalizes large The pre-processing enables faster location estimation and errors more than small ones,which is often uful.If presumably reduces the effect of random fluctuations in the squared error is ud,the estimator minimizing the the training data.
expected loss is the expected value of the location variable
ޅ[lȊo]ϭ͚lЈ⑀ᏸlЈp(lЈȊo)(2) 4.KERNEL METHOD
assuming that the expectation of the location variable is In the kernel method a probability mass is assigned well ,the location variable a“kernel”around each of the obrvations in the The prented probabilistic approach can be con-training data.Thus the resulting density estimate for an
trasted with the more traditional,geometric approach to obrvation o in location l is a mixture of n
l equally
location estimation ud in methods such as angle-of-weighted density functions,where n
l is the number of
arrival(AOA),time-of-arrival(TOA),and time-differ-training vectors in l: ence-of-arrival(TDOA).In the geometric approach the
signal measurements are transformed into angle and dis-p(oȊl)ϭ1
n1͚
l iϭl
K(o;o i)(3)
tance estimates,from which a location estimate is
deduced using standard geometry.To obtain the angle
where K(и;o i)denotes the kernel function.One widely and distance estimates,one needs implicitly to have a
ud kernel function is the Gaussian kernel
好看风景图
model describing the dependency between the location
and the obrvables,which in our probabilistic tting
K Gauss(o;o i)ϭ
1
Ί2
expϪ(oϪo i)22(4)
corresponds to the likelihood function.One of the draw-
backs of the geometric approach is that there is no princi-
pled way to deal with the incompatibility of the angle whereis an adjustable parameter that determines the
奉献的近义词width of the kernel.Figure1illustrates the effect of the and distance estimates caud by measurement errors
and noi.On the other hand,the geometric approach is parameter.
In our location estimation domain,the density esti-usually computationally very efficient.Nevertheless,in
Section5we prent a probabilistic location estimation mates are constructed for the received signal strength
value.As in the nearest neighbor method,we replace method that is sufficiently efficient for virtually all practi-
cal purpos.the missing values by a small constant.The above one-
158Roos,Myllyma¨ki,Tirri,Misikangas,and Sieva¨nen
5.HISTOGRAM METHOD
The so called histogram method is another method
for estimating density functions.Its u for location esti-
mation has been independently suggested in[7,8,11].The
histogram method is cloly related to discretization of
continuous values to discrete ones.Let us first assume
that the obrvation variable is one-dimensional,and that
the minimum and maximum of the variable are known.
The method requires that we fix a t of ,a t
of non-overlapping intervals that cover the whole range
of the variable from the minimum to the maximum.The
number of the bins,denoted by k,is an adjustable parame-
ter.The density estimate is then a piecewi constant Fig.1.Examples of kernel density estimates with Gaussian kernel and
function where the density is constant within each of different values of the kernel width.The larger the value of,the
smoother the estimate.The obrved values are(0.1,0.11,0.18,0.27,the bins.
0.3,0.32,0.33,0.36,0.6,0.65).In addition to the number of bins,it is obviously
necessary to fix the boundary points of the bins—a choice
that greatly affects the resulting density estimate.For
simplicity,here we u equal-width bins[minϩiw,min dimensional formulas can be extended to multivariateϩ(iϩ1)w],0ՅiϽk,where min is the minimum of ,received power from veral access
the obrvation values,and w is given by(maxϪmin)/k, points,by multiplying the individual probabilities,which
where max is the maximum of the obrvation variable. amounts for an assumption of independence of the obr-
Within the constraints a histogram density is uniquely vations.Although the independence assumption can be
described by k parameters defining the bin probabilities, criticized,it is significantly easier to estimate one-dimen-
<,the value of the density function within each of sional densities than multivariate densities.Moreover,
the bins.
the independence is only assumed ,given the
There are veral alternative ways to determine good location,not globally.In other words,the components of
bin probabilities bad on a t of obrved data.In the the obrvation vector can,and usually do,have depend-
so-called maximum likelihood method,which is probably encies if the value of the location variable is not fixed.
the simplest of them all,the relative frequencies of the In the kernel method the training examples can be
bins are ud as the bin probabilities.A Bayesian solution dealt with in two ways.First,we can group the examples
(for which there are elaborate theoretical justifications, in clusters,each taken to be collected from a single loca-
,[13])is to add a small fraction of the total tion.Alternatively,all the examples can be considered as
probability mass uniformly to all bins.An often reason-being collected from different locations.In the latter ca,
able fraction is given by1/n,where n is the size of all the received signal power density estimates are bad
the obrved data.Such an initial probability in all bins on a single obrvation.In our experiments the latter
prevents the sometimes problematic zero probabilities kernel method produced better results—all the results
that are possible in the maximum likelihood method. reported in Section6were obtained by using this type
Figure2prents examples of histogram densities with of individual kernels.
马槟榔parameters chon using the Bayesian solution.
It is interesting to note that the Euclidean nearest
Using a k bin histogram is in effect equivalent to neighbor method is obtained as a limiting ca from the
discretization into k distinct values,each of which is kernel method with the Gaussian kernel as the kernel
assigned a point mass.The difference between values widthapproaches zero.This can be en by obrving
of density functions versus probability mass functions that the probability p(lȊo)is proportional to the likelihood
disappears as a proportionality factor.The missing values p(oȊl),which is a Gaussian density function.Thus the
can be treated simply as the(kϩ1)th value who proba-probability p(lȊo)is a monotonically decreasing function
bility is estimated along with the non-missing values. of the squared distance between the obrved signal
说普通话
power and the kernel mean.As the inver of the kernel
四级题型分值6.EMPIRICAL RESULTS
widthgrows,the squared error is multiplied by a larger
value and the difference between the most probable loca-To empirically compare the location estimation tion and the other locations grows exponentially.
methods,the nearest neighbor,kernel,and histogram
A Probabilistic Approach to WLAN Ur Location Estimation159
A fair comparison of the performance of different
methods is difficult becau there are no standardized
test procedures in this domain.The empirical results are
affected by decisions such as whether the located terminal
is stationary or moving at a certain speed;whether the
location estimation method keeps track of the location
and exploits measurement history,not just the current
measurement;whether the true location of the terminal
is restricted to points from which calibration data is col-
lected;whether one or veral measurements are ud;
and many more.For instance,Bahl et al.[5]acknowledge
this problem and report veral different accuracies
depending on the exact method by which the accuracy Fig.2.Examples of histogram density estimates with different numbers is measured.The experimental tup described below can of bins.The obrved values(0.1,0.11,0.18,0.27,0.3,0.32,0.33,0.6,be en as a step toward defining a framework that could 0.65)are the same as in Fig.1.
be ud for comparing empirical results obtained by dif-
ferent rearchers.
To eliminate the effect of randomness of human methods were implemented as described above.We
behavior,in this study the training data was collected emphasize that all the adjustable parameters,such as ker-
systematically by using a2-meter grid,and at each grid nel width and number of bins,were permanently fixed
point,which we call calibration points,20obrvations before running any tests or looking at the test data bad
were recorded,each consisting of received signal power only on calibration data.Adjusting the parameters bad
values for all obrved ba stations.This was done twice, on test data and/or test results will usually result in overly
5days in between,resulting in a training data t con-optimistic results.The relative location estimation accura-
taining155calibration points,40obrvations in each. cies of the methods were assd in the following ca
The data gathering was performed by using a standard study.The test area consisted of a typical one-floor office
laptop computer with a WLAN card,and the process (16ϫ40meters)with concrete,wood,and glass struc-
took approximately2hours.The test data were collected tures,and normal environmental conditions varying with
independently on the latter day with the same hardware the number of people in the office and their location,air
by using a similar2-meter grid,but by lecting the test humidity,temperature,etc.There were10access points
points to be as far as possible from the calibration points, from two different vendors.Six of them had two omnidi-
<,to be in the middle of the training grid.At each of rectional antennas,and the other four had one directional
antenna(Fig.3).the120test points,20obrvations were gathered.
Fig.3.The test area ud in the experiments.
160Roos,Myllyma¨ki,Tirri,Misikangas,and Sieva¨nen
Table I Location Estimation Errors(average,50th,67th,and90th per-In the test pha,at each test point the location
centiles in meters)Obtained with the Nearest Neighbor,Kernel,and produced by the tested positioning method was first com-
Histogram Methods Using1or20Test Obrvations(the boldface puted and then compared to the correct coordinates.The
values indicate the best accuracy in each tting).
error was measured by using the Euclidean distance.The
obrvation history was taken into account so that at each
1Test Obrvation
point,after having obrved n test obrvations,the point
Method Average50%67%90% estimate was smoothed to be the average of the corres-
ponding n location estimates.More elaborate tracking
Nearest neighbor 3.71 3.21 4.387.23
Kernel method 2.57 2.28 2.97 4.60 schemes for handling the obrvation history are of cour
Histogram method 2.76 2.32 3.11 5.37 possible,but in this study this simple procedure was
adopted in order to guarantee fairness in the comparison20Test Obrvations
among the three different location estimation methods.
Method Average50%67%90% In Fig.4a we e how the average error(averaged
over all the test points)behaves as a function of the
Nearest neighbor 1.67 1.60 2.04 2.80 length of the history.If the time difference between two Kernel method 1.69 1.56 2.01 3.07 obrvations is,say,100milliconds,we e that in2
Histogram method 1.56 1.45 1.81 2.76 conds(by using a history of20obrvations)the error
drops to approximately1.5meters from the initial3–4
meters obtained without history.With a short history(fast
moving objects),the probabilistic methods were more both in the training data and in the test data.The location
accurate than the nearest neighbor method,while with
accuracy was found to be surprisingly robust with respect
the full history with20obrvations(slowly moving to the number of access points ud:as an illustrative
example,consider Figs.4b and5b in which the average objects),the accuracy was approximately the same(e
also Table I).and90%errors,respectively,are plotted as a function of
Figure5a plots the90percentile error,which means
the length of the history when only three access points
that90%of the test cas fall under this curve.The results were ud.The three access points ud in the experiment
are similar to the average results,which means that the
corresponding to the figures are the three access points
methods are reliable in the n that the variance of the that produced the best results,but in the exhaustive tests
location accuracy is relatively small.
performed it was obrved that the lection of the access
To e how the results change with the number of points is not critical as long as the access points are not
access points ud,we ran a ries of experiments in
located very clo to each other,in which ca three ba
which the data from1–9access points were excluded stations would not be enough to cover the whole test area.
Fig.4.Average location estimation error obtained with the nearest neighbor,kernel,and histogram methods as a function of the length of the history,measured with10active access points(a)and with3access points(b).
