Linköping University Post Print

Fingerprinting Localization in Wireless

Networks Based on
Received-Signal-Strength Measurements:
A Case Study on WiMAX Networks

Mussa Bshara, Umut Orguner, Fredrik Gustafsson and Leo Van Biesen

N.B.: When citing this work, cite the original article.

©2009 IEEE. Personal use of this material is permitted. However, permission to

reprint/republish this material for advertising or promotional purposes or for creating new
collective works for resale or redistribution to servers or lists, or to reuse any copyrighted
component of this work in other works must be obtained from the IEEE.

Mussa Bshara, Umut Orguner, Fredrik Gustafsson and Leo Van Biesen, Fingerprinting
Localization in Wireless Networks Based on Received-Signal-Strength Measurements: A
Case Study on WiMAX Networks, 2010, IEEE TRANSACTIONS ON VEHICULAR
TECHNOLOGY, (59), 1, 283-294.
http://dx.doi.org/10.1109/TVT.2009.2030504

Postprint available at: Linköping University Electronic Press

http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-53824
IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 59, NO. 1, JANUARY 2010 283

Fingerprinting Localization in Wireless Networks

Based on Received-Signal-Strength Measurements:
A Case Study on WiMAX Networks
Mussa Bshara, Student Member, IEEE, Umut Orguner, Member, IEEE,
Fredrik Gustafsson, Senior Member, IEEE, and Leo Van Biesen, Senior Member, IEEE

Abstract—This paper considers the problem of fingerprinting or by both [2], [3]. From this point on, we are going to refer
localization in wireless networks based on received-signal-strength to these measurements as network measurements, regardless
(RSS) observations. First, the performance of static localization of where these measurements have been conducted. Some
using power maps (PMs) is improved with a new approach called
the base-station-strict (BS-strict) methodology, which emphasizes of these measurements are hard to obtain, like TOA, which
the effect of BS identities in the classical fingerprinting. Second, needs synchronization, and some are easy to obtain, like RSS
dynamic motion models with and without road network infor- measurements. Many localization approaches depending on
mation are used to further improve the accuracy via particle network measurements have been proposed in GSM networks
filters. The likelihood-calculation mechanism proposed for the and sensor networks. Most of the works focused on range mea-
particle filters is interpreted as a soft version (called BS-soft) of
the BS-strict approach applied in the static case. The results of
surements depending on TOA, TDOA, and RSS observations;
the proposed approaches are illustrated and compared with an see surveys [2], [4], and [5] and the references therein. These
example whose data were collected from a WiMAX network in a approaches can improve the localization accuracy achieved by
challenging urban area in the capitol city of Brussels, Belgium. using the cell ID. The basic idea in RSS-based localization is
Index Terms—Fingerprinting, Global Positioning System (GPS), to compare all measured RSS values to a model of RSS for
Global System for Mobile Communications (GSM), location-based each position and then determine the position that gives the
service (LBS), navigation, path loss model, positioning, positioning best match. The two most common models are the general
accuracy, power maps (PMs), received signal strength (RSS), road exponential path loss model and a dedicated power map (PM)
network information, SCORE, time of arrival (TOA), WiMAX.
constructed offline for the region of interest. The first alternative
I. I NTRODUCTION is the most common strategy and is the simplest to deploy. The
exponential path loss model is known as the Okumura–Hata

T HERE ARE several ways to position a wireless network

user. GPS is the most popular way; its accuracy meets
all the known location-dependent applications’ requirements.
(OH) model [6], [7], and in a log power scale, it says that the
RSS value linearly decreases with the distance to the antenna.
This is quite a crude approximation, where the noise level is
The main problems with GPS, in addition to the fact that the high and further depends on multipath and non-line-of-sight
user’s terminal must be GPS enabled, are the high battery (NLOS) conditions. In [8], the authors used this alternative to
consumption, limited coverage, and latency. Furthermore, GPS track a target and proposed using different path loss exponents
performs poorly in urban areas near high buildings and inside for the links between the terminal and the base stations (BSs).
tunnels. Another way to position a user is to rely on the wireless The proposed method achieved higher localization accuracy
network itself, by using the available information like the cell than the conventional localization methods that use the same
ID, which has widely been used in Global System for Mobile path loss exponent for all the links. Furthermore, the authors
Communications (GSM) systems, despite its limited accuracy of [9] proposed using an RSS statistical lognormal model and
[1]. Using other network resources (information) like the re- a sequential Monte Carlo localization technique to get better
ceived signal strength (RSS), time of arrival (TOA), or time localization accuracy. The lognormal model was also used in
difference of arrival (TDOA) gives better accuracy but requires [10] to estimate the mobile location, and the authors tried to
making measurements by the wireless terminal (terminal-side mitigate the influence of the propagation environment by using
measurements), by the network (network-side measurements), the differences in signal attenuations.
The second alternative is to determine the RSS values in
Manuscript received January 27, 2009; revised July 3, 2009. First published each point and save these in a database (i.e., a map). This can
August 18, 2009; current version published January 20, 2010. The work of
U. Orguner and F. Gustafsson was supported in part by the SSF Strategic be done using offline measurement campaigns adaptively by
Research Center MOVIII and in part by the Vinnova/FMV TAIS project contribution from users or by using cell planning tools. The
ARCUS. The review of this paper was coordinated by Dr. Y. Gao. advantage of this effort is a large gain in the SNR and less
M. Bshara and L. Van Biesen are with the Department of Fundamental
Electricity and Instrumentation, Vrije Universiteit Brussel, 1050 Brussels, sensitivity to multipath and NLOS conditions. The set of RSS
Belgium (e-mail: [email protected]; [email protected]). values that are collected for each position in the map from
U. Orguner and F. Gustafsson are with the Department of Electrical various BSs is called the fingerprint for that location. The idea
Engineering, Linköping University, 581 83 Linköping, Sweden (e-mail:
[email protected]; [email protected]). of matching observations of RSS to the map of the previously
Digital Object Identifier 10.1109/TVT.2009.2030504 measured RSS values is known as fingerprinting, which proved

0018-9545/$26.00 © 2009 IEEE

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
284 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 59, NO. 1, JANUARY 2010

to provide better performance than the first alternative [1]. In and vt is a noise component. A WiMAX modem does not
[11] and [12], the authors used RSS information in finger- readily provide information for time-delay-based localization,
printing positioning to improve the accuracy obtained by the and therefore, we focus on the path loss constant at . This value
lognormal model. The authors of [13] used fingerprinting to is averaged over one or more pilot symbols to give a sampled
overcome the inconveniences related to the use of the TOA, the RSS observation
angle of arrival, and the RSS lognormal model for positioning.
In this paper, we propose to use fingerprinting localiza- zk = h (xpk ) + ek (2a)

tion depending on RSS-based observations for positioning zk , if zk ≥ ymin
yk = (2b)
and tracking in wireless networks. We first consider classical NaN, if zk < ymin
fingerprinting, and based on the BS identities, we propose
a method to improve fingerprinting performance. The new where k is the sample index (corresponding to time instant t =
method emphasizes the effects of the BS identities in classical t0 + kT , where t0 and T are the time of the first sample (k = 0)
fingerprinting, and it is called the BS-strict method. Then, the and the sampling period, respectively), xpk is the position of
use of dynamic motion models is suggested for further improve- the target, and NaN stands for not a number, representing a
ment. In this regard, we use particle filters (PFs) [14]–[16] with “nondetection” event. This expression includes one determinis-
both unconstrained and road-constrained motion models. The tic position-dependent term h(xpk ) including range dependence,
simultaneous use of the motion models and the road network and ek is the noise that includes fast and slow fading. We also
information has shown to yield quite good estimation perfor- explicitly model the detector in the receiver with the threshold
mance. The special likelihood calculation mechanism that this ymin , since signals that are too weak are not detected.
paper suggests for the dynamic case, which is called the BS- The classical model of RSS measurements is based on the
soft method, is also interpreted as a soft version of the BS- so-called OH model [6], [7], which is given as
strict methodology proposed for the static case. We present  
OH model: zk = PBS − 10α log10 pBS − xpk 2 + ek
our results along with remarks on WiMAX networks, which (3)
were the main motivation and the illustrative case study for this
research. However, our results equally apply to other types of where PBS is the transmitted signal power (in decibels), α is the
networks. The importance of the contributions of this paper can path loss exponent, ek is the measurement noise, and pBS is the
be summarized as follows. position of the antenna; the standard  · 2 norm is used. This
1) The proposed approaches yield direct methodologies for model has been used in many proposed localization algorithms
RSS-based localization balancing the effects of measured [2], [17]. Although it is a global and simple model, there are
RSS values and the BS identities. Increasing the effect several problems associated with using it.
of BS identities in location estimation is particularly 1) The transmitted power needs to be known, which requires
significant when the SNR in the RSS values is low and a protocol and software that allows a higher layer of
the effects of multipath and fading are dominant. applications to access this information.
2) Dynamic localization using PFs gives a seamless inte- 2) The position of the antenna needs to be known. This
gration of fingerprinting-type approaches with dynamical requires first building a database. Second, it requires that
motion models and road network information. the user application be able to access the identification
We also argue that the approaches considered in this paper meet number of each antenna connected to the model. Third,
the requirements of most location-dependent applications. the operators in some countries consider the position of
This paper is organized as follows. The measurement model- their antennas to be classified.
ing methodologies for the RSS measurements are summarized 3) The path loss constant needs to be known, while, in
in Section II. The main building blocks of the proposed meth- practice, it depends on the local environment.
ods, which are different likelihood calculation mechanisms, are An alternative model is based on a local PM (LPM), which is
given as separate algorithms in Sections III and V for the static obtained by observing the measurement yk over a longer time
and dynamic estimation cases, respectively. These algorithms and over a local area. Each LPM item is then computed as a
are used in their corresponding positioning and tracking meth- local average
ods, and their performances are illustrated in Sections IV and
VI, respectively. Conclusions are drawn in Section VII. LPM model: ẑ(x) = Ê(y)
 = Ê (h(x) + e) (4a)
ẑ(x), if ẑ(x) ≥ ymin
ĥ(x) = (4b)
NaN, if ẑ(x) < ymin
II. M ODELING RSS M EASUREMENTS
FOR F INGERPRINTING where the operator Ê denotes the corresponding averaging.
In general, the received signal rt at the time instant t can be LPM provides a prediction of the observation (2) in the same
expressed as way as the OH model in (3) does. However, the LPM should
be considered to be more accurate since it implicitly takes care
rt = at st−τ + vt . (1) of the line-of-sight/NLOS problems that are difficult to handle
[18]. The LPM model also partially includes the effects of slow
Here, s denotes the transmitted (pilot) signal waveforms, at is and fast fading. The total effect can be approximated as a gain in
the radio path attenuation, τ is the distance-dependent delay, SNR with a factor of ten, compared with the OH model; see [2].

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
BSHARA et al.: FINGERPRINTING LOCALIZATION IN WIRELESS NETWORKS BASED ON RSS MEASUREMENTS 285

The collection of averaged measurements ĥ(x) for the same where the values yj are equal to the measured RSS values
position in a single vector gives us the fingerprint ĥ(x) for that from the jth BS or are equal to NaN when there is no value
position, i.e., measured (no detection). The localization can then be done by
Δ T
defining distance measures between the measurement vector y
ĥ(x) = [ ĥ1 (x) ĥ2 (x) · · · ĥNBS (x) ] (5) and the map RSS vectors ĥi . In this paper, we will denote such
measures in the form of likelihoods p(y|ĥi ) of the measurement
where NBS is the number of BSs, and ĥj (x) is the averaged vector y given the RSS vector ĥi , which represents a hypothesis
measurement from the jth BS at the position x. The advantage about the position of the target (i.e., pi ). Note that this notational
of collecting fingerprints in a database is that prior knowledge selection makes sense in the case of dynamic localization where
of the antenna position, transmitted power, or path loss constant probabilistic arguments quite frequently appear. However, even
is not needed, enabling mobile-centric solutions. The price for in the static localization, the use of such a symbol for the
this is the cumbersome task of constructing the LPM. Here, distance measures, in spite of the fact that there is no stochastic
three main alternatives are plausible. reasoning in their definition most of the time, emphasizes the
1) Collect the fingerprints during an offline phase. The similarity of the problems in both cases. How to define the
measurements to be stored have to be collected from all likelihoods is not straightforward and forms the backbone of
possible places where the target can be and under various localization. Once they are defined, the localization procedure
weather conditions at different times in the area under in fingerprinting can mathematically be posed as the maximum-
study. This method gives the most accurate database, but likelihood (ML) estimation problem given as follows:
it is time consuming and expensive.  
2) Use the principle of wardriving [19], where the users x̂
= pî (8)
contribute online to the LPM. The idea is that users with ŷ
positioning capabilities (for instance, GPS) report their
î = arg max p(y|ĥi ) (9)
position and observations (2) to a database [20], [21], 1≤i≤NLPM
which is used to position other users.
3) Predict the fingerprints using Geographical Information where x̂ and ŷ are the estimated x- and y-coordinates of the
System planning tools [2]. Using the radio propagation target.
formulas to predict the RSS values is not as accurate as
measuring them because it is not possible to model all the III. L IKELIHOOD D EFINITIONS FOR S TATIC E STIMATION
propagation effects. As a result, the predicted data are not
as accurate as the measured ones, but they are quite easy In defining the likelihoods used for classical (static) finger-
to obtain. printing [given in (8) and (9)], if the vectors y and ĥi did
In this paper, the first method was adopted, and the WiMAX not have NaN values, then any norm (or normlike functions)
RSS values have been collected from all the possible roads in would do the job. The same would be true in the case where the
the area under study (we assume that the target or the user is places of NaN values and non-NaN values would match in the
using the public road network) during an offline phase. The two vectors. However, it is quite unlikely that this condition is
LPM has been formed from this database as follows. satisfied in any real application. The classical way of defining
Δ the likelihood function is as given in the following algorithm
1) NLPM different grid points denoted as {pi =
[1], [12].
[xi , y i ]T }N i i
i=1 , where x and y denote the x- and
LPM
1) Algorithm 1—Classical Fingerprinting: Ignore the NaN
y-coordinates of the ith point, respectively, have been
values and compute the likelihood as the distance between the
selected on the road network. A maximum distance of
two (sub)vectors, i.e.,
10 m has been left between these LPM points.
p(y|ĥi ) = Γi −1
2) For each piece of data that has been collected, the closest Δ
(10)
LPM grid point has been found.
3) For each LPM grid point i, the vector ĥi (called the “RSS Δ
where Γi = [γ1i , γ2i , . . . , γN
i
]T is the vector whose elements
BS
vector” or fingerprint) is formed such that are defined as
T 
ĥi = [ ĥi1 ĥi2 ··· ĥiNBS ] (6)
γj = yj − ĥj , yj = NaN, ĥj = NaN
i i
i Δ
(11)
0, otherwise.
where ĥij is the mean of the RSS data from the jth BS
assigned to the ith LPM grid point. If there are no RSS The norm  ·  (although, most of the time, its effects might be
data from the jth BS assigned to the ith LPM grid point, negligible) can be selected to be any valid norm or distance. In
we set ĥij = NaN, representing a nondetection. Note our paper, for the comparisons, the standard  · 2 norm is used.
that each fingerprint (or RSS) vector ĥi = ĥ(pi ) is a rep- On the other hand, the nonmatching NaN values, as is going
resentative of the expected RSS values at the position pi . to be shown in this paper, carry valuable information that should
The measured RSS values at the time of localization are then not be neglected in the localization. The information given by
collected in another RSS vector y, which is defined as them can be summarized for two different cases.
1) When the measurement vector y has a NaN value for
y = [ y1 y2 ··· yNBS ]T (7) some BS (this means that the receiver did not get any

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
286 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 59, NO. 1, JANUARY 2010

RSS measurement from that BS), the hypotheses ĥi that

have a value for that BS are unlikely. In other words, the
positions pi that are far from the BS are more likely.
2) When the measurement vector has a value for some BS
(this means that the receiver has got an RSS measurement
from that BS), the hypotheses ĥi that does not have a
value for that BS (these are the RSS vectors ĥi that have
a NaN value for that BS) are unlikely, i.e., the positions
pi that are close to the BS are more likely.
The use of this (in a way) negative information in localiza-
tion to different extents is the main theme of this paper. The
localization hypotheses ĥi having nonmatching NaN values,
which we call nonmatching hypotheses, are punished by our
proposed methods. Two different likelihood calculation mech-
anisms (and, hence, measurement models) are proposed for the
static and dynamic estimation cases, respectively. The static
estimation case involves no assumption of temporal correlation Fig. 1. Area under study (the measurement area). The average distance
of the estimated position values and therefore requires the between two sites is about 1150 m.
full extent of the punishment of the nonmatching hypotheses.
Consequently, we call the likelihood calculation mechanism Fig. 2. In the following sections, fingerprinting as defined in
proposed for this case as the BS-strict approach. The dynamic (8) and (9) is applied to the RSS index (RSSI) and SCORE
estimation case, on the other hand, makes use of a dynamic values where the likelihoods p(y|ĥi ) involved are calculated
motion model for the estimated position values, which enables by either the classical method or the BS-strict approach defined
the positioning algorithm to accumulate information from con- in Section III.
secutive measurements. This requires a softer version of the
BS-strict approach in the sense that it allows for the survival of
the unlikely hypotheses between consecutive times. Hence, we A. Fingerprinting Using RSSI Values
call the proposed algorithm for this dynamical case the BS-soft
In this section, we suppose that the user can accurately mea-
approach.
sure (the same accuracy as the PM) the received power (RSSI
We delay the stochastic derivation of the BS-soft approach
values). This can be done (and has been done in this paper) us-
to Section V and give in the following the BS-strict approach,
ing special calibrated modems with extra software installed, and
which is going to be used in the static estimation in Section IV.
the measurements have to be collected offline, because only one
2) Algorithm 2—BS-Strict: This approach calculates the
channel can be measured at a time. Currently, it is not practical
likelihoods in the same way as Algorithm 1 does, but this time,
to use such modems in applications, but the purpose of using
the elements γji of the vector Γi are defined as
them in this paper is to check the possible achievable accuracy
⎧
⎨ yj − ĥij , yj = NaN, ĥij = NaN in case the user can make such measurements. The validation
i Δ data set was obtained using the trajectory shown in Fig. 3 and
γj = 0, yj = NaN, ĥij = NaN (12)
⎩ was used to position a user. The two mentioned approaches
∞, otherwise.
were applied: the classical fingerprinting (Algorithm 1) and the
Notice that the infinite punishment given to the nonmatching BS-strict fingerprinting (Algorithm 2). The results are shown
NaN values in Algorithm 2 results in the elimination of the in Fig. 4. The BS-strict fingerprinting approach’s performance
corresponding hypotheses because their likelihood will vanish. was significantly better than the classical one due to the fact
Any likelihood-based method using Algorithm 2 will therefore that the BS number is more robust against the noise than RSS
search for the strict match of the NaN and non-NaN values values, i.e., the same BS number will be obtained, regardless of
in the two compared RSS vectors. This methodology will the presence of strong noise, but different RSS values will be
then increase the effects of the BS identities in the estimation collected.
process. The methods based on this algorithm can be more
robust than the ones using the classical algorithm, which relies
only on the measured RSS values. This is because the measured B. Fingerprinting Using SCORE Values
BS identities are much more reliable than the actual measured The SCORE values are used by the standard WiMAX
RSS values under a significant range of effects like weather, modems to evaluate the connection quality between the sub-
NLOS, and fading. scriber station and the available BSs, and they can be collected
without adding any extra software or hardware to the modem.
The advantage of using the SCORE values is the possibility of
IV. F INGERPRINTING L OCALIZATION : T HE S TATIC C ASE
simultaneously obtaining them for all the available BSs, but the
In this paper, the PMs of all available sites in the measure- disadvantage lies in their low accuracy compared with RSSI
ment area shown in Fig. 1 have been generated and plotted in values. The relation between SCORE values and RSSI values

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
BSHARA et al.: FINGERPRINTING LOCALIZATION IN WIRELESS NETWORKS BASED ON RSS MEASUREMENTS 287

Fig. 2. PMs of the three WiMAX sites. (a) Site 1. (b) Site 2. (c) Site 3.

Fig. 3. Used target trajectory.

Fig. 4. Positioning error cdf’s. The two fingerprinting approaches were used
(the classical and the BS-strict) with the available measurements (RSSI and
SCORE).
is given, according to the information provided by the modem
manufacturer, by where the AvgViterbi value is statistically computed from the
Viterbi decoder. This adds an extra challenge for localization
SCORE = (RSSI − 22) − (0.08 × AvgViterbi) (13) services, since even though the performance of the decoder

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
288 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 59, NO. 1, JANUARY 2010

is important for handover decisions, it is only a nuisance estimation method. The algorithm that we will present is based
for localization. Measurements were collected using the same on the following simple assumptions.
trajectory to validate the two fingerprinting approaches (using 1) The elements {yj }N j=1 of the measurement vector y
BS

the same database built using RSSI values). Fig. 4 shows the are conditionally independent, given the database RSS
cumulative distribution function (cdf) of the positioning error. vector ĥi .
Two observations can be made. 2) Matching non-NaN values in the measurement and RSS
1) Using the SCORE values gives less positioning accuracy values satisfy
than using the RSSI values. This is logical because the
yj = ĥij + ej , if yj = NaN and ĥij = NaN (14)
SCORE values are less accurate than RSSI values.
2) The impact of using the BS-strict approach is larger in the where ej ∼ pej (.) represents the measurement noise for
case of SCORE values. The SCORE values are subject to the jth BS.
bigger changes than the RSSI values because the SCORE Using the first assumption, the likelihood p(y|ĥi ) can be
values depend on not only the received power but the written as
quality of the signal determined by the Viterbi decoder
as well.

NBS

p(y|ĥi ) = βij (15)

j=1
V. L IKELIHOOD D EFINITIONS FOR DYNAMIC E STIMATION Δ
where βij = p(yj |ĥij ) is the individual likelihood for the jth
In static estimation, there is no temporal correlation between BS. The different combinations that appear in the analysis due
the consecutively made estimations. In other words, once a to NaN values are separately considered as follows.
measurement ytk is collected at time tk and an estimate x̂pk
1) If yj = NaN (we get a measurement from the jth BS)
of the target position is obtained, in the next time step tk+1 ,
the whole procedure is repeated by using only ytk+1 , and the and ĥij = NaN (the ith hypothesis has LPM data for the
new estimate x̂pk+1 is independent of what x̂pk is. In such a case, jth BS), we have, by assumption 2, that
 
the use of the information stored in the measurement ytk to its βij = pej yj − ĥij (16)
fullest extent is reasonable because by doing this, we achieve
the following. where pej (.) can be selected considering the application
1) We extract most out of a single measurement. requirements. A simple choice is to set
2) Even if we make a mistake in the current estimation,  
βij = N yj ; ĥij , σj2 (17)
the estimation errors cannot accumulate and affect the
subsequent estimations.
where N (yj ; ĥij , σj2 ) denotes a normal density with mean
Consequently, the negative information (i.e., nondetection
ĥij and standard deviation σj evaluated at yj . This cor-
events or NaN values) in the measurements y has been
used to completely eliminate some positioning hypotheses in responds to pej (.) = N (.; 0, σj2 ). If the number of data
Algorithm 2. points averaged for an LPM grid point is greater than,
On the other hand, the dynamical estimation methods, which e.g., ten, then by the central limit theorem, this Gaussian
use models to take advantage of the correlated information likelihood seems to be the most appropriate selection. The
in consecutive position estimations, get their power from the standard deviation σj is a user-selected parameter that
accumulation of the information in the algorithm along the could change from BS to BS.
time. Therefore, the survival of different hypotheses about 2) If yj = NaN (we do not get any measurement from the
the position values is important in such methods for the jth BS) and ĥij = NaN, we then have
 
information-gathering process, which enables higher estima-
βij = P yj < ymin |ĥij (18)
tion performance. Moreover, the complete elimination of some  
hypotheses (like the assignment of infinite cost to nonmatching = P ej < ymin − ĥij (19)
hypotheses in Algorithm 2) can result in error accumulation in  
a recursive procedure because a hypothesis deletion can never = cdfej ymin − ĥij (20)
be compensated for in the future, even if some contrasting
Δ x
evidence appears. Thus, assigning still higher but finite costs where cdfej (x) = −∞ pej (x)dx is the cdf of ej . Here,
to nonmatching hypotheses, hence allowing them (or some while passing from (19) to (20), we assumed that ej is
of them) to survive, is more suitable in dynamic estimation a continuous random variable (i.e., no discontinuity in
procedures. Since such a cost assignment procedure makes its cdf). The probability density function appears in the
the hypothesis punishment softer than that in Algorithm 2 by calculation again as a design parameter. Notice here that,
assigning finite costs to nonmatching hypotheses (compared although it is the same density as that required in the pre-
with the infinite punishment in Algorithm 2, which results in vious case, the density pej (.) can be selected differently
the hypothesis elimination), we call the resulting methodology in each case for design purposes. In fact, as observed from
as the “soft” approach. In the following, we give such a soft several preliminary experiments, the Gaussian selection
likelihood calculation mechanism to be used in a dynamic as in the previous case gives too much (exponential)

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
BSHARA et al.: FINGERPRINTING LOCALIZATION IN WIRELESS NETWORKS BASED ON RSS MEASUREMENTS 289

punishment for the nonmatching hypotheses (i.e., hy- i.e., yj = ĥij1 ), we expect the punishment for i1 to be
potheses corresponding to ĥi for which ĥij = NaN). Such more than the one for i2 , that is, the inequality
a selection would therefore yield a hard approach that
is similar to the BS-strict algorithm. Therefore, another βi1 j ≤ βi2 j (25)
selection has been made, which leads to the softer result
  must be satisfied. Note that, since βi2 j depends on ĥij2
 ĥi  and yj via (17), it can be arbitrarily small. Therefore,
 j 
βij = μ   (21) if βi1 j is selected irrespective of the βi2 j values for the
 ymin 
matching hypotheses, it is a strong possibility that βi1 j
where μ ≤ 1 is a constant design parameter. This se- would happen to be much higher than βi2 j , and hence,
lection, in fact, corresponds to a uniform density for ej a nonmatching hypothesis will be promoted instead of
between the values ymin and −ymin when μ = 0.5/ymin . the matching ones. In fact, in the preliminary simulations
using (24), this caused the matching hypotheses to be
Notice that we always have ymin < ĥij ≤ 0 in this paper,1
discarded. Therefore, for this case, we (give up (24) and)
and therefore, 0 ≤ βij < 1. Since we do not get a mea-
propose the following likelihood calculation method:
surement from the jth BS, we punish the hypotheses that
have LPM values for that BS and note that the larger the βij = min βmj (26)
LPM value (i.e., power), the greater the punishment is, m∈Mj

i.e., βij is smaller.

where the set Mj is given as
3) If yj = NaN and ĥij = NaN (for the ith hypothesis, we do  
Δ
not have any data for the jth BS), then a similar analysis Mj = i|ĥij = NaN . (27)
would be
  The likelihood (26) always satisfies the condition (25),
βij = p yj |ĥij < ymin (22) and hence, the nonmatching hypotheses are punished
  more than or as much as the matching ones. One can
P ĥij < ymin |yj p(yj ) actually replace the punishment factor with any smaller
=   (23)
P ĥij < ymin value. Notice that when there are no hypotheses that have
values for the BS (i.e., the set Mj is empty), arbitrary
which requires the prior likelihood p(yj ) and probability punishing or (24) can be applied.
4) If yj = NaN and ĥij = NaN, then since the vectors are
P (ĥij < ymin ), which are hard to obtain. A straightfor-
matching for the jth BS, one can set βij = 1.
ward approximation can be
  The algorithm outlined is summarized in the following from an
βij ≈ P ĥij < ymin |yj (24) implementation point of view.
1) Algorithm 3—BS-Soft: Suppose the current available hy-
which is simple to calculate in a way similar to (21) but potheses are shown as {ĥi }N i=1 , where Nh represents the num-
h

has been seen to give low performance in preliminary ber of hypotheses.

simulations. The reason for this has been investigated and 1) Calculate the quantities αij for i = 1, . . . , Nh and j =
is found to be that the term calculated using (24) can 1, . . . , NBS as
sometimes be much larger than the terms calculated for   
the hypotheses that actually have a (non-NaN) value for αij = N y j ; ĥ i
j , σ 2
j , yj = NaN, ĥij = NaN (28)
that BS. We are going to illustrate our argument on the NaN, otherwise.
following example case: Suppose that yj = NaN (i.e., we
have collected a measurement from the jth BS) and i1 2) Calculate the quantities βij for i = 1, . . . , Nh and j =
and i2 are two positioning hypotheses such that ĥi1 = ĥi2 1, . . . , NBS using {αij } as
for  = j. Suppose also that ĥij1 = NaN (for the i1 th ⎧
⎪
⎪ 1,  yj = NaN, ĥij = NaN
hypothesis, we do not have any data for the jth BS) and ⎪
⎪  i 
⎪
⎨ μ  ĥj  , yj = NaN, ĥi = NaN
ĥij2 = NaN (for the i2 th hypothesis, we have data for  ymin  j
the jth BS). We would like to calculate the punishing βij = (29)
⎪
⎪  i
terms (likelihoods) βi1 j and βi2 j corresponding to these ⎪ m mj
⎪ min α , y j = NaN, ĥ j = NaN
⎪
⎩
two hypotheses. Since the hypothesis i1 is nonmatching αij , yj = NaN, ĥij = NaN
(in terms of only the jth BS, i.e., yj = ĥij1 ) and the
hypothesis i1 is matching (in terms of only the jth BS, where only numeric values are considered in the
minimization.
N i=1 from {βij } as
3) Calculate the likelihoods {p(y|ĥi )}N h
1 In fact, the data collected in this paper (i.e., {ĥij }i=1 LPM
for j =
1, . . . , NBS ) satisfied this assumption, but in general, the collected data need

NBS
not satisfy it. This is, however, not a restriction because one can always find the i
p(y|ĥ ) = βij (30)
Δ
quantity h̄ = max1≤j≤NBS max1≤i≤NLPM ĥij and subtract it from all the j=1
data and the online measurements when they are collected to obtain equivalent
data and measurements that satisfy the assumption for a value of ymin . for i = 1, . . . , Nh .

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
290 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 59, NO. 1, JANUARY 2010

The punishment terms in the likelihood calculation can be filters [28], of which the unscented Kalman filter [29], [30]
thought of as a softened version of the BS-strict approach is one type, have been shown to be suitable for a much
previously considered in this section. In a way, by assigning larger class of nonlinearities (see the extensive work in [31]).
lower weights to the hypotheses that do not match the measure- These approaches are possible alternatives in the cases where
ment, one lowers their effect in the overall estimate instead of the posterior density of the state is unimodal. On the other
completely discarding them (similar to BS-strict), which can be hand, if one assumes that the user is moving on the road, the
quite harmful in dynamic approaches. state density would be highly multimodal, which can quite
poorly be approximated with a single Gaussian distribution.
Complicating the facts, the measurement function h(.) that is
VI. F INGERPRINTING L OCALIZATION :
represented by the PM is highly nonlinear, and furthermore, it
T HE DYNAMIC C ASE
is discontinuous. Therefore, in this paper, we are going to use
For the positioning methods used in Section IV, one does the relatively recent algorithms in the literature called PFs [14]–
not consider the time information (stamps) available with the [16]. Two PFs are used to track the target (user). The first one
measurements. When the target is localized with good accuracy exploits the target dynamic information (motion model) only,
for one measurement, in the next measurement when the user and the second filter makes use of the public road information
is possibly quite close to the previous location (because only map in addition to the dynamic information. We call these filters
a small amount of time has passed), the previous accurate off-road and on-road PFs for obvious reasons. Knowing that the
localization is completely discarded, and a new localization is user is on the public road network is valuable information for
done based on the new measurement. This is one type of static the positioning of the user. The TeleAtlas maps have been used
target localization, and the dynamic information coming from as assisting data, in addition to the measured data [32].
the fact that the user does not move much between consecutive
measurements is not used. One of the ways to use this extra A. PF
information in localization is to use a dynamic model for the
target (user) position given as PFs are the recursive implementation of Bayesian density
recursions [14]–[16]. The main aim in the method, as in
xtk+1 = ftk+1 ,tk (xtk , wtk+1 ,tk ) (31) many Bayesian methods, is to calculate the posterior density
Δ
of the state xtk given all the measurements yt1:k = {yt1 ,
where we have the following. yt2 , . . . , ytk }; i.e., we calculate the density p(xtk |yt1:k ). While
1) xtk ∈ Rnx is the state of the target at time tk . doing this, the PF approximates the density p(xtk |yt1:k ) with
2) wtk+1 ,tk ∈ Rnw is the process noise representing the a number of state values {xtk }i=1
(i) Np
(called particles) and their
uncertainty in the model between time instants tk and (i) Np
corresponding weights {ηtk }i=1 (called particle weights), i.e.,
tk+1 . If the process noise term is selected to be small, this
means that the target model is known with good accuracy 
Np
(i)
and vice versa. p (xtk |yt1:k ) ≈ ηtk δx(i) (xtk ) . (33)
tk
3) ftk+1 ,tk (., .) is, in general, a nonlinear function of its i=1

arguments. Then, at each time step, the PF needs to calculate the par-
(i) (i) Np
This type of models is generally used in target tracking [22], ticles and weights {xtk , ηtk }i=1 from the previous particles
[23] to model target motion dynamics. At each time instant tk , (i) (i) Np
and weights {xtk−1 , ηtk−1 }i=1 . We are going to use the basic
we get a measurement ytk that is related to the state of the particle filtering algorithm, which is called a bootstrap filter that
target as was first proposed in [33]. At each step of the algorithm, one
ytk = h(xtk ) + vtk (32) can calculate the conditional estimate x̂tk and the covariance
Ptk of the state as
where we have the following. 
Np
Δ (i) (i)
1) h(.) is, in general, a nonlinear function. In our applica- x̂tk = ηtk xtk (34)
tion, it is the PM whose information is collected offline. i=1
The likelihoods p(ytk |xtk ) will be formed from the PM 
Np   T
Δ (i) (i) (i)
using Algorithm 3. The details will be given below in Ptk = ηtk xtk − x̂tk xtk − x̂tk . (35)
Section VI-B2. i=1

2) vtk is the measurement noise representing the quality of It is possible to calculate other types of point estimates, like
our sensors. maximum a posteriori (MAP) estimates [34], from the particles
The state estimation with this type of probabilistic model, and the weights of the posterior state density; however, this
which is given by (31) and (32), is a mature area of research would require a kernel smoothing of the particles in general
[24], [25]. The optimal solution when the functions f (.) and [35]. Note that the PF described is one of the simplest and com-
h(.) are linear and the noise terms wtk+1 ,tk and vtk are Gaussian putationally cheapest algorithms among the more complicated
is the well-known Kalman filter [26]. Some small nonlinearities ones, as given in [36] and [14]. In the following section, we will
can be handled by approximate methods such as the extended describe the specific models and parameters that are used in the
Kalman filter [27], and the methods called sigma-point Kalman two differently (off-road and on-road) implemented PFs.

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
BSHARA et al.: FINGERPRINTING LOCALIZATION IN WIRELESS NETWORKS BASED ON RSS MEASUREMENTS 291

B. Implementation Details of the PFs TABLE I

PARAMETER VALUES U SED FOR A LGORITHM 3
We implemented two different bootstrap PFs using different FOR L IKELIHOOD C ALCULATION

target motion models but with the same measurement model

(i.e., likelihood).
1) State Models: The first PF (called an off-road filter) uses
a classical (nearly) constant-velocity model with state xk =
[pxk+1 , pyk+1 , vk+1
x y
, vk+1 ]T , where variables p and v denote the
position and the velocity of the target, respectively. The motion
model is given by in the following form:
⎡ x ⎤ ⎡ x⎤ ytk = [ y1 y2 ··· yNBS ]T (39)
pk+1   pky  T2 
y
⎢ pk+1 ⎥ I2 Tk+1 I2 ⎢ pk ⎥ k+1
I
⎣ x ⎦= ⎣ x⎦+ 2 2 wk+1 (36) as has also been given in Section II. The likelihood value
vk+1 0 I2 vk Tk+1 I2 (i)
y
vk+1 y
vk p(ytk |xtk ) is calculated using the LPM, as given in the fol-
lowing algorithm:
where wk is a 2-D white Gaussian noise with zero mean and (i)
3) Algorithm 4—Calculation of p(ytk |xtk ):
covariance 52 I2 , and In is the identity matrix of dimension n.
1) Calculate the distance of the particle to all of the LPM
Tk+1 = tk+1 − tk is the difference between consecutive time
grid points as
stamps of the measurements.
The second PF (called an on-road filter) makes use of the dj = ptk − pj
(i)
(40)
road database information. The literature is abundant with a 2
large number of publications on target tracking with road net- (i)
where ptk denotes the vector composed of the position
work information. Although the early studies used approaches (i)
based on multiple-model (extended) Kalman filters [37]–[39], components of xtk .
the PFs, in a short time, have proved to be one of the in- 2) Find the closest point in the LPM to the particle posi-
dispensable tools in road-constrained estimation [40], [41]. tion as
This is confirmed in the large number of publications on the
ĵ = arg max dj . (41)
subject, like [42]–[47], which appeared only during the last 1<j<NLPM
five years. Our approach here considers a single reduced-order
(i)
on-road motion model with a bootstrap filter. The state of the 3) Calculate p(ytk |xtk ) as
PF is denoted by xrk , where r stands for emphasizing road   
 
information, and it is given as xrk = [prk , vkr , irk ]T , where the (i) p ytk |ĥĵ , if dĵ ≤ dthreshold
p ytk |xtk = (42)
scalar variables prk and vkr denote the position and speed values p(ytk |h̄), otherwise
of the target on the road segment, which is identified by the
integer index irk . The following model is used for the dynamics where p(ytk |ĥĵ ) and p(ytk |h̄) are calculated using
of xrk : Algorithm 3, whose specific parameters are given in
⎡ r ⎤ ⎛⎡ r ⎤ ⎞ Table I. In (42), h̄ denotes an NBS vector with all ele-
pk+1 pk+1
⎣ vk+1
r ⎦ = f r ⎝⎣ vk+1
r ⎦ , IRN , wrd ⎠ ments being equal to NaN. dthreshold is a user-selected
k+1 (37)
r r distance threshold that determines the largest distance
ik+1 ik
between a particle and an LPM grid point at which the
where LPM grid point can be used to calculate the likelihood
      T2  of the particle. This is going to be particularly important
prk+1 1 Tk+1 prk k+1
rc in the off-road PF where the particles can frequently go
r = r + 2 wk+1 . (38)
vk+1 0 1 vk Tk+1 outside of the area of interest. In this case, using p(ytk |h̄)
instead of p(ytk |ĥĵ ) implicitly punishes such a particle.
The continuous process noise wkrc is a scalar white Gaussian
We selected dthreshold = 100 m in our simulations.
acceleration noise with zero mean and 0.2-m/s2 standard devi-
ation. The predicted position and speed values, i.e., prk+1 and 4) Initialization: PFs were initialized with a large Gaussian
r
vk+1 , might not be on the road segment indicated by irk . The spread of particles with mean at the true positions and zero
function f r (.) therefore projects the values prk+1 and vk+1 r velocities, i.e.,
r
into the road segment denoted by ik+1 . If there is more than ! x,(i) "
y,(i) T
p0 p0
y,(i) x,(i)
v0 v0 ∼ N (., m0 , P0 ) (43)
one candidate for the next road segment index irk+1 due to the
junctions, the function also selects a random one according to for i = 1, . . . , Np , where
the value of the discrete on-road process noise term wk+1 rd
∈ Δ
{1, 2, . . . , Nr (xk )}, where Nr (xk ) is the number of possible
r r m0 = [ p̄x0 p̄y0 0 0 ]T (44)
Δ
road segments in which the target with on-road state xrk might P0 = diag ([ 1002 1002 10 2 2
10 ]) . (45)
go in the following Tk+1 seconds.
2) Likelihoods: The measurement model is the same for Here, [p̄x0 , p̄y0 ] is the true target coordinates at time t0 , and the
both PFs. At a single time instant tk , the measurement vector is operator diag(.) forms a diagonal matrix from the elements of

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
292 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 59, NO. 1, JANUARY 2010

Fig. 5. Positioning error cdf’s for the proposed fingerprinting approach and the conventional approach (based on the OH model). (a) Using RSSI measurements.
(b) Using SCORE measurements.

the input vector. The results that have been obtained in this pa- fingerprinting methodology in dynamic filtering significantly
per does not change with different initial distribution selection exceeds that of the OH-model-based approach. The perfor-
as long as the initial distribution covers the true target position mance gain with fingerprinting is overwhelming in the off-road
with some probability mass. The initial Gaussian density given case but is still visible in the on-road filters, particularly with the
has a position standard deviation of 100 m, which is, in a way, SCORE measurements where the SNR is lower. It is remarkable
an indirect assumption of prior information for the initial target that the on-road OH-model-based PF is almost equivalent to
position with that quality. It is unfortunately not possible to the off-road fingerprinting-based filter in terms of estimation
initially distribute the particles to the whole area of study and errors, which clearly illustrate the effect of the strong modeling
then start the estimation. This is because in such a case, the capability of the fingerprinting approach.
percentage of the probability mass that is spread around the As a last point, we make a comparison between the results
true position would be too small. Therefore, a suggestion for of the dynamic and the static cases, which are depicted in
the general case, where no prior information of the initial target Fig. 6. A very interesting observation is that, in the high-
position is available, can be to initialize the particles around accuracy parts of the RSSI case, the static approach makes
an initial estimate obtained by the static fingerprinting with the better estimations than the dynamic ones, although the dynamic
first collected measurement. estimation algorithms, in the overall results, are seen to be
In the off-road PF, we directly use the initial particles. On much more robust. Note that there is about a 10-m performance
the other hand, in the on-road PF, which always needs particles loss in the RSSI-based dynamic on-road filter compared to
that are on the road network, the corresponding particles are the static result. We attribute this difference to the fact that
obtained by projecting the ones defined earlier onto the road the static estimation calculates an ML estimate, whereas the
network. dynamic on-road filter calculates a mean square estimate. Since
To compare our fingerprinting-based bootstrap filters, we there are about 10 m between the LPM grid points and the
have implemented two additional (on-road and off-road) boot- PF calculates the likelihood of a particle as the likelihood of
strap PFs that use only the OH model in (3) for likelihood the closest LPM point, there can appear many particles with
calculation. For this purpose, we have estimated transmitted the same weights in a 5-m radius. Calculating the average of
powers (PBS ) and measurement variances for each BS and the these particles, which may be biased toward one side of the
path loss exponent α using the least squares method with our optimal result due to the road constraints, can give an error
previously collected data (which has been used for forming the of about 5 m. Considering the error terms added by averaging
LPM). The estimation results for our fingerprinting-based boot- over all the particles, we can expect an error of about 10 m in
strap filters and OH-model-based bootstrap filters are shown in the result compared with the ML-based static approach, which
Fig. 5. Notice that using SCORE or RSSI measurements with would directly give the position of the most likely LPM grid
the OH model in the off-road filter gives almost the same results point when the SNR is high (like the case with RSSI). The
because the dominating model errors like fading overcome the calculation of the MAP estimate in the PF can be an alternative
effect of the accuracy of the measurements, and the difference for this problem. In the off-road case, since the particles are
is no longer visible. In the on-road case, the difference is even more separated, we can expect this lower performance
more evident. The fingerprinting approach reduces the effect of effect (under a high SNR) to be more visible. Furthermore, we
modeling errors, and therefore, the quality of the measurements think that the lack of road-network information also makes the
gains more importance in the results. The performance of the estimates of the off-road filter suffer from low prior information

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
BSHARA et al.: FINGERPRINTING LOCALIZATION IN WIRELESS NETWORKS BASED ON RSS MEASUREMENTS 293

Fig. 6. Positioning error comparison between (on-road and off-road) dynamic positioning and static positioning. (a) Using RSSI measurements. (b) Using
SCORE measurements.

compared with static estimates, which are always constrained to R EFERENCES

the road segments. Note that, with the SCORE measurements, [1] Cello Consortium Rep. [Online]. Available: http://www.telecom.
which represents a more practical low-SNR case, there are no ntua.gr/cello/documents/CELLO-WP2-VTT-D03-007-Int.pdf
similar important sufferings. In the global behavior (95% lines), [2] F. Gustafsson and F. Gunnarsson, “Possibilities and fundamental limi-
tations of positioning using wireless communication networks measure-
the performance gains with the dynamic approaches make it ments,” IEEE Signal Process. Mag., vol. 22, no. 4, pp. 41–53, Jul. 2005.
clear that these methods should be preferred when highly robust [3] G. Sun, J. Chen, W. Guo, and K. Liu, “Signal processing techniques in
estimators are required. The results show that, for 95% lines, the network-aided positioning: A survey of state-of-the-art positioning de-
signs,” IEEE Signal Process. Mag., vol. 22, no. 4, pp. 12–23, Jul. 2005.
positioning accuracy improvement caused by the motion model [4] S. Gezici, Z. Tian, B. Giannakis, H. Kobayashi, and A. Molisch, “Local-
compared with the static case is about 33% when SCORE ization via ultra-wideband radios,” IEEE Signal Process. Mag., vol. 22,
values are used and about 50% when RSSI values are used. The no. 4, pp. 70–84, Jul. 2005.
[5] D. Li and Y. Hu, “Energy-based collaborative source localization using
localization accuracy improvement achieved by using the road acoustic microsensor array,” J. Appl. Signal Process., vol. 2003, pp. 321–
information compared with the dynamic case is about 50% in 337, Jan. 2003.
the case of SCORE values and about 40% in the case of RSSI [6] Y. Okumura, E. Ohmori, T. Kawano, and K. Fukuda, “Field strength and
its variability in VHF and UHF land-mobile radio service,” Rev. Elect.
values, which indicates the strong effect of the road network Commun. Lab., vol. 16, pp. 9–10, 1968.
information on the localization accuracy. [7] M. Hata, “Empirical formula for propagation loss in land mobile radio
services,” IEEE Trans. Veh. Technol., vol. VT-29, no. 3, pp. 317–325,
Aug. 1980.
VII. C ONCLUSION [8] J. Shirahama and T. Ohtsuki, “RSS-based localization in environments
with different path loss exponent for each link,” in Proc. Veh. Technol.
This paper has discussed the use of fingerprinting positioning Conf., 2008, pp. 1509–1513.
in wireless networks based on the RSS measurements, i.e., [9] W. D. Wang and Q. X. Zhu, “RSS-based Monte Carlo localisation for
RSSI and SCORE, with specific remarks on WiMAX networks. mobile sensor networks,” IET Commun., vol. 2, no. 5, pp. 673–681,
May 2008.
The introduced work has been divided into two main parts: [10] D.-B. Lin and R.-T. Juang, “Mobile location estimation based on differ-
static localization and dynamic localization. In the latter, the ences of signal attenuations for GSM systems,” IEEE Trans. Veh. Tech-
information of the target’s motion model was used with and nol., vol. 54, no. 4, pp. 1447–1454, Jul. 2005.
[11] O. Sallent, R. Agusi, and X. Cavlo, “A mobile location service demon-
without road information. In both approaches, the effect of strator based on power measurements,” in Proc. Veh. Technol. Conf.,
BS identities, which are more robust to propagation effects, Sep. 2004, vol. 6, pp. 4096–4099.
on the estimates has been increased via designing specific [12] K. K. C. Takenga, “Mobile positioning based on pattern-matching and
tracking techniques,” ISAST Trans. Commun. Netw., vol. 1, no. 1, pp. 529–
likelihood calculation mechanisms. The results obtained show 532, Aug. 2007.
that fingerprinting positioning is a strong and robust approach [13] A. Taok, N. Kandil, S. Affes, and S. Georges, “Fingerprinting localiza-
for overcoming the RSS’s high variability. The positioning tion using ultra-wideband and neural networks,” in Proc. Signals, Syst.
Electron., Aug. 2007, pp. 529–532.
accuracy obtained by using the motion model and the road [14] A. Doucet, S. J. Godsill, and C. Andrieu, “On sequential simulation-based
network information is notable. The accuracy improvement was methods for Bayesian filtering,” Stat. Comput., vol. 10, no. 3, pp. 197–
very promising, and new location-dependent applications could 208, 2000.
[15] A. Doucet, N. de Freitas, and N. Gordon, Eds., Sequential Monte Carlo
be seen in the horizon. The positioning accuracy achieved by Methods in Practice. Berlin, Germany: Springer-Verlag, 2001.
using the fingerprinting-positioning approach with the motion [16] S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, “A tutorial on
model and road information can therefore be seen as a further particle filters for on-line non-linear/non-Gaussian Bayesian tracking,”
IEEE Trans. Signal Process., vol. 50, no. 2, pp. 174–188, Feb. 2002.
step toward more accuracy-demanding applications and new [17] A. Heinrich, M. Majdoub, J. Steuer, and K. Jobmann, “Real-time path-loss
types of location-based services. position estimation in cellular networks,” in Proc. ICWN, Jun. 2002.

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.
294 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 59, NO. 1, JANUARY 2010

[18] K.-T. Feng, C.-L. Chen, and C.-H. Chen, “GALE: An enhanced geometry- Mussa Bshara (S’09) received the Bachelor’s de-
assisted location estimation algorithm for NLOS environments,” IEEE gree in electrical engineering from Damascus Uni-
Trans. Mobile Comput., vol. 7, no. 2, pp. 199–213, Feb. 2008. versity, Damascus, Syria, and the M.Sc. degree in
[19] K. Jones and L. Liu, “What where Wi: An analysis of millions of Wi-Fi signal processing and information security from the
access points,” in Proc. IEEE Int. Conf. PORTABLE, May 2007, pp. 1–4. Beijing University of Posts and Telecommunica-
[20] K. Jones, L. Liu, and F. Alizadeh-Shabdiz, “Improving wireless posi- tions, Beijing, China. He is currently working toward
tioning with look-ahead map-matching,” in Proc. 4th Annu. Int. Conf. the Ph.D. degree with the Department of Fundamen-
MobiQuitous, Aug. 2007, pp. 1–8. tal Electricity and Instrumentation, Vrije Universiteit
[21] S. Byers and D. Kormann, “802.11b access point mapping,” Commun. Brussel, Brussels, Belgium.
ACM, vol. 46, no. 5, pp. 41–46, May 2003. His research interests include localization, nav-
[22] Y. Bar-Shalom, X. R. Li, and T. Kirubarajan, Estimation With Applications igation and tracking in wireless networks, sig-
to Tracking and Navigation. New York: Wiley, 2001. nal processing, wireless communications, power line communications, and
[23] S. Blackman and R. Popoli, Design and Analysis of Modern Tracking x digital subscriber line (xDSL) technologies.
Systems. Norwood, MA: Artech House, 1999.
[24] B. D. O. Anderson and J. B. Moore, Optimal Filtering. Englewood Umut Orguner (S’99–M’07) received the B.S.,
Cliffs, NJ: Prentice-Hall, 1979. M.S., and Ph.D. degrees in electrical engineering
[25] P. R. Kumar and P. Varaiya, Stochastic Systems: Estimation, Identification from Middle East Technical University, Ankara,
and Adaptive Control. Englewood Cliffs, NJ: Prentice-Hall, 1986. Turkey, in 1999, 2002, and 2006, respectively.
[26] R. E. Kalman, “A new approach to linear filtering and prediction prob- From 1999 to 2007, he was with the Department
lems,” J. Basic Eng., vol. 82, no. 1, pp. 34–45, Mar. 1960. of Electrical and Electronics Engineering, Middle
[27] A. H. Jazwinski, Stochastic Processes and Filtering Theory. New York: East Technical University, as a Teaching and Re-
Academic, 1970. search Assistant. Since January 2007, he has been
[28] R. Van Der Merwe and E. Wan, “Sigma-point Kalman filters for proba- a Postdoctoral Associate with the Division of Au-
bilistic inference in dynamic state-space models,” in Proc. Workshop Adv. tomatic Control, Department of Electrical Engineer-
Mach. Learn., 2003, p. 377. ing, Linköping University, Linköping, Sweden. His
[29] S. Julier, J. Uhlmann, and H. Durrant-Whyte, “A new method for the non- research interests include estimation theory, multiple-model estimation, target
linear transformation of means and covariances in filters and estimators,” tracking, and information fusion.
IEEE Trans. Autom. Control, vol. 45, no. 3, pp. 477–482, Mar. 2000.
[30] S. Julier and J. Uhlmann, “Unscented filtering and nonlinear estimation,”
Proc. IEEE, vol. 92, no. 3, pp. 401–422, Mar. 2004. Fredrik Gustafsson (S’91–M’93–SM’05) received
[31] R. Van Der Merwe, “Sigma-point Kalman filters for probabilistic infer- the M.Sc. degree in electrical engineering and the
ence in dynamic state-space models,” Ph.D. dissertation, Oregon Health, Ph.D. degree in automatic control from Linköping
Sci. Univ., Portland, OR, 2004. University, Linköping, Sweden, in 1988 and 1992,
respectively.
[32] Digital Mapping and Solutions—Teleatlas. [Online]. Available: http://
Since 2005, he has been a Professor of sensor
www.teleatlas.com
informatics with Department of Electrical Engineer-
[33] N. J. Gordon, D. J. Salmond, and A. F. M. Smith, “A novel approach
ing, Linköping University. From 1992 to 1999, he
to nonlinear/non-Gaussian Bayesian state estimation,” Proc. Inst. Elect. held various positions in automatic control, and from
Eng.—Radar Signal Process., vol. 140, no. 2, pp. 107–113, Apr. 1993. 1999 to 2005, he had a professorship in communi-
[34] H. L. Van Trees, Detection, Estimation, and Modulation Theory, vol. I. cation systems. He is a Cofounder of the companies
New York: Wiley, 1968. NIRA Dynamics and Softube, developing signal processing software solutions
[35] H. Driessen and Y. Boers, “MAP estimation in particle filter tracking,” for the automotive and the music industry, respectively. He is currently an
in Proc. IET Semin. Target Tracking Data Fusion: Algorithms Appl., Associate Editor for the EURASIP Journal on Applied Signal Processing and
Apr. 2008, pp. 41–45. the International Journal of Navigation and Observation. His research interests
[36] M. Pitt and N. Shephard, “Filtering via simulation: Auxiliary particle are in stochastic signal processing and adaptive filtering and change detection,
filters,” J. Amer. Stat. Assoc., vol. 94, no. 446, pp. 590–599, Jun. 1999. with applications to communication, vehicular, airborne, and audio systems.
[37] T. Kirubarajan, Y. Bar-Shalom, K. R. Pattipati, and I. Kadar, “Ground tar- His work in the sensor fusion area involves the design and implementation
get tracking with variable structure IMM estimator,” IEEE Trans. Aerosp. of nonlinear filtering algorithms for localization and navigation and tracking
Electron. Syst., vol. 36, no. 1, pp. 26–46, Jan. 2000. of all kinds of platforms, including cars, aircraft, spacecraft, unmanned aerial
[38] P. J. Shea, T. Zadra, D. Klamer, E. Frangione, and R. Brouillard, “Im- vehicles, surface and underwater vessels, cell phones, and film cameras for
proved state estimation through use of roads in ground tracking,” in Proc. augmented reality.
SPIE Signal Data Process. Small Targets, 2000, vol. 4048, pp. 312–332. Dr. Gustafsson was elected as a member of the Royal Academy of Engineer-
[39] P. J. Shea, T. Zadra, D. Klamer, E. Frangione, and R. Brouillard, “Pre- ing Sciences in 2007. He received the Arnberg prize by the Royal Swedish
cision tracking of ground targets,” in Proc. IEEE Aerosp. Conf., vol. 3, Academy of Science in 2004. He was an Associate Editor for the IEEE
2000, pp. 473–482. T RANSACTIONS ON S IGNAL P ROCESSING from 2000 to 2006.
[40] M. S. Arulampalam, N. Gordon, M. Orton, and B. Ristic, “A variable
structure multiple model particle filter for GMTI tracking,” in Proc. Int.
Conf. Inf. Fusion, Jul. 2002, vol. 2, pp. 927–934. Leo Van Biesen (SM’96) received the Electro-
Mechanical Engineer and the Doctoral (Ph.D.) de-
[41] B. Ristic, S. Arulampalam, and N. Gordon, Beyond the Kalman Filter:
grees from the Vrije Universiteit Brussel (VUB),
Particle Filters for Tracking Applications. London, U.K.: Artech House,
Brussels, Belgium, in 1978 and 1983, respectively.
2004, ch. 10.
Currently, he is a Full Senior Professor with the
[42] M. Ulmke and W. Koch, “Road-mapassistedgroundtargettracking,”IEEE Department of Fundamental Electricity and Instru-
Trans. Aerosp. Electron. Syst., vol. 42, no. 3, pp. 1264–1274, Oct. 2006. mentation, VUB. He teaches courses on fundamental
[43] Y. Cheng and T. Singh, “Efficient particle filtering for road-constrained electricity, electrical measurement techniques, sig-
target tracking,” IEEE Trans. Aerosp. Electron. Syst., vol. 43, no. 4, nal theory, computer-controlled measurement sys-
pp. 1454–1469, Oct. 2007. tems, telecommunication, physical communication,
[44] O. Payne and A. Marrs, “An unscented particle filter for GMTI tracking,” and information theory. His current interests are sig-
in Proc. IEEE Aerosp. Conf., Mar. 2004, vol. 3, pp. 1869–1875. nal theory, PHY layer in communication, time-domain reflectometry, wireless
[45] L. Hong, N. Cui, M. Bakich, and J. R. Layne, “Multirate interacting communications, x digital subscriber line (xDSL) technologies, and expert
multiple model particle filter for terrain-based ground target tracking,” systems for intelligent instrumentation.
Proc. Inst. Elect. Eng.—Control Theory Appl., vol. 153, no. 6, pp. 721– Dr. Van Biesen was the Chairman of the International Measurement Confed-
731, Nov. 2006. eration (IMEKO) TC-7 from 1994 to 2000 and the President Elect of IMEKO
[46] G. Kravaritis and B. Mulgrew, “Variable-mass particle filter for from 2000 to 2003 and has been the Liaison Officer between the IEEE and
road-constrained vehicle tracking,” EURASIP J. Adv. Signal Process., IMEKO. He was the President of IMEKO from 2003 to September 2006. He is
vol. 2008, p. 321 967, Jan. 2008. currently the Chairman of the Advisory Board of IMEKO as the immediate past
[47] M. Ekman and E. Sviestins, “Multiple model algorithm based on particle President. He is also member of the board of Federation des Ingenieurs de
filters for ground target tracking,” in Proc. Int. Conf. Inf. Fusion, Jul. 2007, Telecommunication des Communautées Européens Belgium and Union
pp. 1–8. Radio-Scientifique International Belgium.

Authorized licensed use limited to: Linkoping Universitetsbibliotek. Downloaded on February 5, 2010 at 06:42 from IEEE Xplore. Restrictions apply.