ANALYSIS OF THE OPTIMAL STRATEGY FOR WLAN LOCATION DETERMINATION SYSTEMS
Moustafa A. Youssef∗, Ashok Agrawala
{moustafa, agrawala}@cs.umd.edu
Abstract
This paper presents a general analysis for the performance of WLAN location determination systems.
WLAN locations determination systems estimates the user location using software-based techniques in
a WLAN environment. We present an analytical method for calculating the average distance error and
probability of error of WLAN location determination systems. These expressions are obtained with
no assumptions regarding the distribution of signal strength or the probability of the user being at a
specific location, which is usually taken to be a uniform distribution over all the possible locations in
current WLAN location determination systems. We use these expressions to find the optimal strategy to
estimate the user location and to prove formally that probabilistic techniques give more accuracy than
deterministic techniques, which has been taken for granted without proof for a long time. The analytical
results are validated through simulation experiments and we present the results of testing actual WLAN
location determination systems in an experimental testbed. We also study the effect of the assumption
that the user position follows a uniform distribution over the set of possible locations on the accuracy
∗Also affiliated with Alexandria University, Egypt.
of WLAN location determination systems. Knowing the probability distribution of the user position can
reduce the number of access points required to obtain a given accuracy. However, with a high density of
access points, the performance of a WLAN location determination system is consistent under different
probability distributions for the user position which can be used to reduce the energy consumed in the
location determination algorithm and the time required to build the user profile. Keywords – optimal WLAN positioning strategy, WLAN location determination, WLAN simulation 1. Introduction
1 WLAN location determination systems use the popular 802.11 [1] network infrastructure to determine
the user location without using any extra hardware (any device, such as laptops and PDAs, equipped with
a wireless card can be tracked). This makes these systems attractive in indoor environments where tra-
ditional techniques, such as the Global Positioning System (GPS) [2], fail to work or require specialized
hardware. Many applications have been built on top of location determination systems to support perva-
sive computing. These include [3] location-sensitive content delivery, direction finding, asset tracking,
In order to estimate the user location, a system needs to measure a quantity that is a function of
distance. Moreover, the system needs one or more reference points to measure the distance from. In the
case of the GPS system, the reference points are the satellites and the measured quantity is the time of
arrival of the satellite signal to the GPS receiver, which is directly proportional to the distance between
the satellite and the GPS receiver. In case of WLAN location determination systems, the reference points
are the access points and the measured quantity is the signal strength, which decays logarithmically with
distance in free space. Unfortunately, in indoor environments, the wireless channel is very noisy and
the radio frequency (RF) signal can suffer from reflection, diffraction, and multipath effect [4, 5], which
makes the signal strength a complicated function of distance. To overcome this problem, WLAN location
determination systems tabulate this function by sampling it at selected locations in the area of interest.
This tabulation has been know in literature as the radio map, which captures the signature of each access
point at certain points in the area of interest.
1An earlier version of this paper appeared in the 2004 Communication Networks and Distributed Systems Modelling and
WLAN location determination systems usually work in two phases: offline phase and location deter-
mination phase. During the offline phase, the system constructs the radio map. In the location determi-
nation phase, the vector of samples received from each access point (each entry is a sample from one
access point) is compared to the radio map and the “nearest” match is returned as the estimated user
location. Different WLAN location determination techniques differ in the way they construct the radio
map and in the algorithm they use to compare a received signal strength vector to the stored radio map
in the location determination phase.
In this paper, we present a general analysis of the performance of WLAN location determination
systems. In particular, we present a general analytical expression for the average distance error and
probability of error of WLAN location determination systems. These expression are obtained with noassumptions regarding the distribution of signal strength or user movement profile. We use these ex-
pressions to find the optimal strategy to use during the location determination phase to estimate the user
location. We base our optimality criteria on minimizing the probability of error, which is the probability
that the system gives an incorrect estimate at any location. This measure is useful in comparing the
performance of different WLAN location determination systems. We use the error expressions to prove
formally that probabilistic techniques give more accuracy than deterministic techniques, which has been
taken for granted without proof for a long time. We validate our analysis through simulation experi-
ments and discuss how well it models actual environments. We also present an analysis of the effect of
the assumption that the user location is uniformly distributed over the set of all possible locations on the
performance of the location determination systems. Our results show that a WLAN location determina-
tion system can avoid unnecessary calculations, and hence reduce power consumption, depending on the
density of access points in the area of interest. For the rest of the paper we will refer to the probability
distribution of the user location as the user profile.
To the best of our knowledge, our work is the first to analyze the performance of WLAN location
systems analytically, provide the optimal strategy to select the user location, and study the effect of the
user profile on the performance of WLAN location determination systems.
The rest of this paper is structured as follows. Section 2 summarizes the previous work in the area of
WLAN location determination systems. Section 3 presents the analytical analysis for the performance
of WLAN location determination systems. In Section 4, we validate our analytical analysis through
simulation and provide experiments to test the effect of the user profile on the performance of location
determination systems. Section 5 concludes the paper and presents some ideas for future work. 2. Related Work
Radio map-based techniques can be categorized into two broad categories: deterministic techniques and
probabilistic techniques. Deterministic techniques, such as [6–8], represent the signal strength of an
access point at a location by a scalar value, for example, the mean value, and use non-probabilistic
approaches to estimate the user location. For example, in the Radar system [6] the authors use nearest
neighborhood techniques to infer the user location. On the other hand, probabilistic techniques, such
as [5, 9–14], store information about the signal strength distributions from the access points in the radio
map and use probabilistic techniques to estimate the user location. For example, the Horus system from
the University of Maryland [5,9–11] uses the stored radio map to find the location that has the maximum
probability given the received signal strength vector.
All these systems base their performance evaluation on experimental testbeds which may not give
a good idea of the performance of the algorithm in different environments. The authors in [9, 10, 13]
showed that their probabilistic technique outperformed the deterministic technique of the Radar sys-
tem [6] in a specific testbed and conjectured that probabilistic techniques should outperform determin-
istic techniques. This paper presents a general analytical method for analyzing the performance of dif-
ferent techniques. We use this analytical method to provide a formal proof that probabilistic techniques
outperform deterministic techniques. Moreover, we show the optimal strategy for selecting locations in
Most of the current WLAN location determination systems assume that the user has an equal prob-
ability of being at any location in the set of radio map locations (uniform user profile). Moreover, the
systems that take user profile into account, for example [12], do not analyze the effect of the user profile
on performance. Instead, they provide the performance of the overall system without showing the effect
of the user profile separately. This papers studies the effect of this uniform user profile assumption on
the performance of the location determination systems. The results show that under certain conditions,
using the user profile to estimate the location may lead to unnecessary computation overhead. 3. Analytical Analysis
In this section, we give an analytical method to analyze the performance of WLAN location determi-
nation techniques. We start by describing the notation used throughout the paper. We provide two
expressions: one for calculating the average distance error of a given technique and the other for cal-
culating the probability of error (i.e. the probability that the location technique will give an incorrect
3.1. Notation
We consider an area of interest whose radio map contains N locations. We denote the set of locations as
L. At each location, we can get the signal strength from k access points. We denote the k-dimensional
signal strength space as S. Each element in this space is a k-dimensional vector whose entries represent
the signal strength reading from different access points. Since the signal strength returned from the
wireless cards are typically integer values, the signal strength space S is a discrete space. For a vector
represents the estimated location returned by the WLAN location determination technique
A when supplied with the input s. For example, in the Horus system [9, 10], f ∗
location l ∈ L that maximizes P (l|s). Finally, we use Euclidean(l1, l2) to denote the Euclidean distance
between two locations l1 and l2. 3.2. Average Distance Error
We want to find the average distance error (denoted by E(DErr)). Using conditional probability, this
E(DErr|l is the correct user location)P (l is the correct user location)
where P (l is the correct user location) depends on the user profile.
We now proceed to calculate E(DErr|l is the correct user location). Using conditional probability
E(DErr|l is the correct user location)
E(DErr|s, l is the correct user location)P (s|l is the correct user location)
Euclidean(f ∗ (s), l)P (s|l
where Euclidean(f ∗ (s), l)
represents the Euclidean distance between the estimated location and the
(2) says that to get the expected distance error given we are at location l, we need to get the weighted
sum, over all the possible signal strength values s ∈ S, of the Euclidean distance between the estimated
Euclidean(f ∗ (s), l)P (s|l
is the correct user location)P (l is the correct user location)
Note that the effect of the location determination technique is summarized in the function f ∗
to find the function that minimizes the probability of error. We differ the optimality analysis until after
we present the probability of error analysis. 3.3. Probability of Error
In this section, we want to find an expression for the probability of error which is the probability that
the location determination technique will return an incorrect estimate. This can be obtained from (3) by
noting that every non-zero distance error (represented by the function Euclidean(f ∗ (s), l)
an error. More formally, we define the function:
g(x) = 1 : x > 0
The probability of error can be calculated from (3) as:
g(Euclidean(f ∗ (s), l))P (s|l
is the correct user location)P (l is the correct user location)
In the next section, we will present a property of the term g(Euclidean(f ∗ (s), l))
to get the optimal strategy for selecting the location. 3.4. Optimality
We will base our optimality analysis on the probability of error. Lemma 1 For a given signal strength vector s, g(Euclidean(f ∗ (s), l)) will be zero for only one locationl ∈ L and one for the remaining N − 1 locations.Proof For a given signal strength vector s, the location determination technique will return a single
location. If this location matches the correct location l, the distance error will be zero and hence the
function g. If not, the distance error will be greater than zero and the function g will equal one. The
estimated location f ∗ (s)
can only match one of the possible N locations.
The lemma states that only one location will give a value of zero for the function g(Euclidean(f ∗ (s), l))
in the inner sum. This means that the optimal strategy should select this location in order to minimize
the probability of error. This leads us to the following theorem. Theorem 1 (Optimal Strategy) Selecting the location l that maximizes the probability P (s|l)P (l) is both a necessary and sufficient condition to minimize the probability of error.Proof [Sufficient part] Selecting the location that maximizes the probability P (s|l)P (l) will lead to
making the function g in the inner sum of (4) equals zero for this probability. Since this technique
removes the maximum probability for all s ∈ S, this minimizes the overall probability of error. [Necessary part] By contradiction: Assume not, then there exist an optimal strategy A1 that for at
least one signal strength vector s, selects a location l1 that does not have the maximum probability for
P (s|l)P (l), ∀l. Let the probability of error using this strategy be E1. Consider another strategy A2 that
take the same decisions as A1 except for the signal strength vector s, where it returns the location l2
that maximizes the product P (s|l)P (l), ∀l. Let the probability of error using this strategy be E2. Since
E2 − E1 = P (s|l1)P (l1) − P (s|l2)P (l2) < 0, this contradicts our assumption that A1 is optimal.
Theorem 1 suggests that the optimal location determination technique should store in the radio map the
signal strength distributions to be able to calculate P (s|l). Moreover, the optimal technique needs to
know the user profile in order to calculate P (l). Corollary 1 Deterministic techniques are not optimal. Proof Since deterministic techniques do not store any information about the signal strength distribution
at each location, it follows from Theorem 1 that they are not optimal.
Note that we did not make any assumption about the independence of access points, user profile, or
signal strength distribution in order to get the optimal strategy.
A major assumption by most of the current WLAN location determination systems is that all user
locations are equi-probable. In this case, P (l) = 1 and Theorem 1 can be rewritten as:
Corollary 2 If the user is equally likely to be at any location of the radio map locations l in L, then selecting the location l that maximizes the probability P (s|l) is both a necessary and sufficient conditionto minimize the probability of error.Proof The proof is a special case of the proof of Theorem 1.
This means that, for this special case, it is sufficient for the optimal technique to store the histogram
of signal strength at each location. This is exactly the technique used in the Horus system [9, 10].
Fig. 1 shows a simplified example illustrating the intuition behind the analytical expressions and the
theorems. In the example, we assume that there are only two locations in the radio map and that at each
location only one access point can be heard whose signal strength, for simplicity of illustration, follows
a continuous distribution. The user can be at any one of the two locations with equal probability. For the
Horus system (Fig. 1.a), consider the line that passes through the point of intersection of the two curves.
Since for a given signal strength the technique selects the location that has the maximum probability, the
error if the user is at location 1 is the area of curve 1 to the right of this line. If the user is at location 2,
Figure 1: Expected error for the special case of two locations
the error is the area of curve 2 to the left of this line. The error probability is half the sum of these two
areas as the two locations are equi-probable. This is the same as half the area under the minimum of the
For the Radar system (Fig. 1.b), consider the line that bisects the signal strength space between the
two distribution averages. Since for a given signal strength the technique selects the location whose
average signal strength is closer to the signal strength value, the error if the user is at location 1 is the
area under curve 1 to the right of this line. If the user is at location 2, the error is the area under curve
2 to the left of this line. The error probability is half the sum of these two areas as the two locations are
equi-probable (half the shaded area in the figure).
From Fig. 1, we can see that the Horus system outperforms the Radar system since the expected error
for the former is less than the latter (by the hashed area in Fig. 1.b). The two systems would have the
same expected error if the line bisecting the signal strength space of the two averages passes by the
intersection point of the two curves. This is not true in general. This has been proved formally in the
We provide simulation and experimental results to validate our results in Section 4.
Figure 2: Plan of the floor where the experiment was conducted. Readings were collected in thecorridors (shown in gray). 4. Experiments 4.1. Testbed
We performed our experiment in a floor covering a 20,000 square feet area. The layout of the floor is
shown in Fig. 2. Both techniques were tested in the Computer Science Department wireless network.
The entire wing is covered by 12 access points installed in the third and fourth floors of the building.
For building the radio map, we took the radio map locations on the corridors on a grid with cells
placed 5 feet apart (the corridor’s width is 5 feet). We have a total of 110 locations along the corridors.
On the average, each location is covered by 4 access points.
We used the mwvlan driver and the MAPI API [15] to collect the samples from the access points. 4.2. Simulation Experiments
In this section, we validate our analytical results through simulation experiments. For this purpose, we
chose to implement the Radar system [6] from Microsoft as a deterministic technique and the Horus
system [9, 10] from the University of Maryland as a probabilistic technique that satisfy the optimality
criteria as described in Corollary 2. We start by describing the experimental testbed that we use to
validate our analytical results and evaluate the systems. 4.2.1. Simulator
We built a simulator that takes as an input the following parameters:
• the radio map locations’ coordinates. • the signal strength distributions at each location from each access point (constructed from 300
• the distribution over the radio map locations that represents the steady state probability of the user
being at each location (user profile).
The simulator then chooses a location based on the user location distribution and generates a sig-
nal strength vector according to the signal strength distributions at this location. The simulator feeds
the generated signal strength vector to the location determination technique. The estimated location is
compared to the generated location to determine the distance error.
The next section analyze the effect of the user profile on the performance of the location determination
systems. We validate our analytical results in all the experiments. 4.2.2. Effect of User Profile on Performance
We made three experiments that differ in how heterogeneous is the user profile:
• Profile 1: The user has equal probability of being at any location (uniform user profile). • Profile 2: The user can be in one of two groups of locations. The probability of being in one group
is twice the probability of being in the second group. The user has equal probability of being at
• Profile 3: The user has an exponentially damping distribution of being at different radio map
locations. More specifically, the probability of being at location i is given by:
(1)N−1 : i = N
Figure 3: Performance of the Horus and Radar systems under a uniform user profile (profile 1).
The heterogeneity of the user profile increases as we move from profile one to profile three. The
purpose of these simulation experiments is to study the effect of the assumption that the user location
follows a uniform distribution over all possible locations on the performance of the location determi-
nation systems. The next subsections show the results of these experiments. For all experiments, we
obtained the analytical results from (3) and (4). Uniform user location distribution: This is similar to the assumption taken by the Horus system.
Therefore, the Horus system should give optimal results. Figures 3 shows the probability of error and
average distance error (analytical and simulation results) respectively for the Radar and the Horus sys-
tems. The figure shows that the analytical expressions obtained are consistent with the simulation results.
Moreover, the Horus system performance is better than the Radar system as predicted by Corollary 2.
The Horus system performance is optimal under the uniform distribution of user location. Heterogeneous user profile distributions: This experiment study the case where a location deter-
mination system assumes that the user location follows a uniform distribution over all possible locations
while the actual distribution is not.
Figures 4 and 5 show the probability of error and average distance error for profiles 2 and 3 respec-
tively. The figures compares the Radar system, Horus system, and the optimal strategy which takes the
user profile into account. The figures show that as the heterogeneity of the user profile increases (from
profile 2 to profile 3), the performance of the location determination systems deviates from the optimal
strategy. Fig. 5 shows that the knowledge of the user profile is critical for environments where the num-
Figure 4: Performance under user profile 2.
Figure 5: Performance under user profile 3.
ber of access points deployed is limited and the heterogeneity of user profile is high. The figure shows
that, for one access point, the optimal strategy gives an average distance error of about 2.25 feet while
the strategies that does not take the user profile into account gives an average distance error of about
27 feet. However, as the number of access points increases, the difference between the performance of
the location determination systems and the optimal strategy decreases. As the number of access points
increases, the information the location determination system gets about the user location increases and
dominates the information from the user profile. The Horus system maintains its superior performance
Figure 6: CDF for the distance error for the two systems. 4.3. Measurements Experiments
In our simulations, we assumed that the test data follows the signal strength distributions exactly. This
can be considered as the ideal case since in a real environment, the received signal may differ slightly
form the stored signal strength distributions. Our results however are still valid and can be considered
as an upper bound on the performance of the simulated systems. In order to confirm that, we tested the
Horus system and the Radar system in an environment where the test set was collected on different days,
time of day and by different persons than those in the training set.
Fig. 6 shows the CDF of the distance error for the two systems. The figure shows that the Horus sys-
tem (a probabilistic technique) significantly outperforms the Radar system (a deterministic technique)
5. Conclusions and Future Work
We have provided two novel contributions to the area of WLAN location determination systems. First,
we presented an analytical method for studying the performance of WLAN location determination sys-
tems. The method can be applied to any of the WLAN location determination techniques and does not
make any assumptions about the signal strength distributions at each location, independence of access
points, nor the user profile. Second, we studied the effect of the user profile on the performance of the
WLAN location determination systems.
We used the analytical method to obtain the optimal strategy for selecting the user location. The
optimal strategy must take into account the signal strength distributions at each location and the user
We used simulation experiments to validate the analytical results and to study the effect of user profile
on the performance of the location determination systems. The results show that incorporating the user
profile in the location determination system can enhance the accuracy significantly when the available
hardware is limited. However, with a reasonable number of access points that can be heard at each
location, the performance of the location determination system is consistent under different user profiles.
In this case, the location determination system can assume a uniform user profile, which reduces the
computational requirements of the algorithm, without degrading the system accuracy and saves the time
In our simulations, we assumed that the test data follows the signal strength distributions exactly. This
can be considered as the ideal case since in a real environment, the received signal may differ slightly
form the stored signal strength distributions. Our results however are still valid and can be considered
as an upper bound on the performance of the simulated systems. We confirmed that through actual
implementation in typical environments.
For future work, the method can be extended to include other factors that affects the location deter-
mination process such as averaging multiple signal strength vectors to obtain better accuracy, using the
user history profile, usually taken as the time average of the latest location estimates, and the correlation
between samples from the same access points. cation determination systems. References
[1] The Institute of Electrical and Inc. Electronics Engineers. IEEE Standard 802.11 - Wireless LAN Medium Access
Control (MAC) and Physical Layer (PHY) specifications. 1999.
[2] P. Enge and P. Misra. Special issue on GPS: The Global Positioning System. Proceedings of the IEEE, pages 3–172,
[3] G. Chen and D. Kotz. A Survey of Context-Aware Mobile Computing Research. Technical Report Dartmouth Computer
Science Technical Report TR2000-381, 2000.
[4] William Stallings. Wireless Communications and Networks. Prentice Hall, first edition, 2002.
[5] M. Youssef and A. Agrawala. Small-Scale Compensation for WLAN Location Determination Systems. In IEEE WCNC
[6] P. Bahl and V. N. Padmanabhan. RADAR: An In-Building RF-based User Location and Tracking System. In IEEEInfocom 2000, volume 2, pages 775–784, March 2000.
[7] A. Smailagic, D. P. Siewiorek, J. Anhalt, D. Kogan, and Y. Wang. Location Sensing and Privacy in a Context Aware
Computing Environment. Pervasive Computing, 2001.
[8] P. Krishnan, A.S. Krishnakumar, Wen-Hua Ju, Colin Mallows, and Sachin Ganu. A system for lease: Location estima-
tion assisted by stationary emitters for indoor rf wireless networks. In IEEE Infocom, March 2004.
[9] M. Youssef, A. Agrawala, A. U. Shankar, and Sam H. Noh. A Probabilistic Clustering-Based Indoor Location Deter-
mination System. Technical Report UMIACS-TR 2002-30 and CS-TR 4350, University of Maryland, College Park,March 2002. http://www.cs.umd.edu/Library/TRs/.
[10] M. Youssef, A. Agrawala, and A. U. Shankar. WLAN Location Determination via Clustering and Probability Distribu-
tions. In IEEE PerCom 2003, March 2003.
[11] Moustafa Youssef and Ashok Agrawala. Handling samples correlation in the horus system. In IEEE Infocom, March
[12] P. Castro, P. Chiu, T. Kremenek, and R. Muntz. A Probabilistic Location Service for Wireless Network Environments. Ubiquitous Computing 2001, September 2001.
[13] T.Roos, P.Myllymaki, H.Tirri, P.Misikangas, and J.Sievanen. A Probabilistic Approach to WLAN User Location Esti-
mation. International Journal of Wireless Information Networks, 9(3), July 2002.
[14] A. M. Ladd, K. Bekris, A. Rudys, G. Marceau, L. E. Kavraki, and D. S. Wallach. Robotics-Based Location Sensing
using Wireless Ethernet. In 8th ACM MOBICOM, Atlanta, GA, September 2002.
http://www.cs.umd.edu/users/moustafa/Downloads.html. Moustafa Youssef is a research associate in the Department of Computer Science at the Uni-versity of Maryland at College Park. He received his B.Sc. and M.Sc. in Computer Sciencefrom Alexandria University, Egypt in 1997 and 1999 respectively and the Ph.D. degree incomputer science from University of Maryland in 2004. His research interests include lo-cation determination technologies, pervasive computing, energy-aware computing, sensornetworks, and protocol modeling. Dr. Moustafa is a life fellow for the Egyptian Societyfor Talented, an elected member of the honor society Phi Kappa Phi, among others. He is amember of various professional societies such as IEEE, IEEE Computer Society, IEEE Com-munication Society and ACM Sigmobile. Dr. Moustafa is the recipient of the 2003 Universityof Maryland Invention of the Year award for his Horus work. Ashok Agrawala is a professor at the University of Maryland at College Park. In 2001, hestarted the Maryland Information and Network Dynamics (MIND) Lab which carries outresearch and development activities in partnership with the industry. He received a BE degreein 1963 and a ME in 1965 from the I.I.Sc, Bangalore; and a Master of Arts and a Ph.D. degreein Applied Mathematics from Harvard University in 1970. Prof. Agrawala is the authorof seven books, 6 patents (awarded or pending), and over 240 papers and is a recognizedauthority in the research and use of the management of time in real-time processing and clocksynchronization applications. He has developed a few location determination techniques andseveral other innovative technologies for systems and networks which are in different stagesof deployment. Prof. Agrawala is a Fellow of the IEEE and Senior Member of the ACM.

Drugs of Abuse Assays Cross-Reactivity Manual by Trade Name, June 2005 COMPOUND (Trade Name) COMPOUND (Generic Name) Acetaminophen (See also Paracetamol) Acetaminophen (See also Paracetamol) Hydrocortisone Nifedipine Methylenedioxymethamphetamine (MDMA) Positive for Methamphetamine (mAMP) and Ecstasy (MDMA) Dexamphetamine Sulphate Positive for Amphetamine (AMP) De

www.dietitiansonthego.ca [email protected] (506)848-2141 June 2010 Happy Summer! I NSIDE TH IS I SSUE S ummer is officially here! Not only does that mean holidays and vacations for most of us, but tons of local 1 Happy Summer! f resh fruits and veggies. I had my first taste of local s trawberries this week - the sweet taste of summer!