Info Com 2000
Info Com 2000
Info Com 2000
<
(
(
,
\
,
,
(
j
C nW WAF C
C nW WAF nW
d
d
n dBm d P dBm d P
o
o
*
*
log 10 ] )[ ( ] )[ (
between the transmitter and the receiver, and then applied
simple linear regression to determine the parameters of the
model [Jai91].
Table 2 contains the numerical values of the model
parameters for the three base stations considered separately
and when taken together. We note that the values for the
path loss exponent (n) and the reference signal strength (P
do
)
for all three base stations are similar despite their different
physical locations and surroundings. This result is
encouraging since it indicates that the parameter values are
not tied to the specific location of the base stations. The
values of P
do
are higher than those published by the
manufacturer [Roa96] (for d
0
= 1 meter) because our WAF
model does not account for multipath propagation. The
values of the path loss exponent are smaller than those
reported in previous work on indoor radio propagation
modeling [Rap96]. However, they are consistent with our
expectations since we compensate the measured signal
strength for attenuation due to obstructions, and since we do
not consider multipath (which can boost the signal strength
at a given location). R
2
represents the coefficient of
determination, which is a useful measure for indicating the
goodness of regression [Jai91]. The high values of R
2
(on a
scale of 0 to 1) suggest that there is a good match between
the estimated and the measured values of the signal strength.
Another value of interest shown in the table is the mean
squared error (MSE). These numbers reinforce the
observation that the WAF propagation model fits the
measured data well.
BS
1
BS
2
BS
3
All
P
do
57.58 56.95 64.94 58.48
n 1.53 1.45 1.76 1.523
R
2
0.81 0.65 0.69 0.72
MSE 10.49 13.98 7.34 9.82
Table 2 Parameter estimates using linear regression
The final column in Table 2 shows the values for P
do
and n when the data from all the transmitter-receiver pairs
(i.e., all three base stations) was combined. The motivation
for this was to determine a value of P
do
and n that could be
used for all base stations without overly affecting the result.
The advantage of using a common value is that it avoids the
need for individual measurements of each base station as
they are installed in the network, thus greatly reducing the
cost of system setup. We can then use these values to
estimate the signal strength at various points within the
building.
Figure 9 illustrates how the predicted values of the
signal strength generated with the propagation model (after
compensating for wall attenuation) compares with the actual
measurements. We observe a good match between the two.
While this plot is for one of the three base stations, plots for
the other two base stations exhibit a similar match.
4.2.3 Results using the Propagation Model
To determine the performance of location estimation
with the signal propagation modeling method, we used the
model to compute the signal strength at a grid of locations on
the floor. We then used this data set as the search space for
the NNSS algorithm.
Considering the median (50
th
percentile), the
propagation method provides a resolution of about 4.3 m,
compared to a resolution of 2.94 m for the empirical method
and 8.16 m for the strongest base station method (Table 1).
For the 25
th
percentile the propagation method provides a
resolution of 1.86 m compared to 1.92 m for the empirical
method and 4.94 m for the strongest base station method.
0
5
10
15
20
25
30
35
40
45
50
1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70
Sample
S
i
g
n
a
l
S
t
r
e
n
g
t
h
(
d
B
m
)
Figure 9 Predicted versus measured signal strength.
While the propagation method is not as accurate as the
empirical method, it is significantly better than the strongest
BS and random methods. Thus, even without extensive
empirical measurements, RADAR based on the propagation
model alone would significantly outperform the strongest
base station method proposed in [Hod97].
4.2.4 Summary of Radio Propagation Method
The WAF propagation model provides a cost effective
means for user location and tracking in an indoor RF
wireless network. The model is cost effective in the sense
that it does not require detailed empirical measurements to
generate a signal strength map and consequently has a low
set up cost. A significant result from Section 4.2.2 is that the
parameters for the wall attenuation propagation model are
similar across base stations despite the latter being in
different locations. This suggests that the entire system can
be relocated to a different part of the building, but the same
parameter values can be used to model propagation and
thereby determine a users location.
5 Discussion and Future Work
We discuss extensions to the RADAR system that
would help improve its robustness and accuracy. Due to
space constraints, we keep our discussion brief.
We are investigating how user-mobility profiles can
supplement signal strength information in locating and
tracking users. A profile specifies a priori likelihood of user
location and/or movement patterns, which can be derived
from history [Liu98], calendar information, building layout,
etc.
We are also investigating base station-based
environmental profiling to make RADAR robust in the face
of large-scale variations in the RF signal propagation
environment (caused, for instance, by the varying number of
people in a building during the course of a day). Instead of
recording just one set of signal strength measurements, we
record multiple sets at different times of the day. The base
stations probe the channel periodically to determine the
current conditions, and accordingly pick the data set that is
most appropriate for these conditions.
6 Conclusions
In this paper, we have presented RADAR, a system for
locating and tracking users inside a building. RADAR is
based on empirical signal strength measurements as well as a
simple yet effective signal propagation model. While the
empirical method is superior in terms of accuracy, the signal
propagation method makes deployment easier.
We have shown the despite the hostile nature of the
radio channels, we are able to locate and track users with a
high degree of accuracy. The median resolution of the
RADAR system is in the range of 2 to 3 meters, about the
size of a typical office room.
Our results indicate that it is possible to build an
interesting class of location-aware services, such as printing
to the nearest printer, navigating through a building, etc., on
an RF wireless LAN, thereby adding value to such a
network. This, we believe, is a significant contribution of our
research.
Our eventual plan is to combine location information
services with the RADAR system and deploy this within our
organization.
Acknowledgements
We would like to thank Stephen Dahl for his help in
setting up our experimental testbed, and the anonymous
reviewers for their perspicacious comments.
References
[ATC98] http://www.ascension-tech.com
[Azu93] R. Azuma, Tracking Requirements for Augmented
Reality, Communications of the ACM, Vol. 36, No. 7, pp: 50-
51, July 1993
[Ber96] S. Berchtold, D. A. Keim, H. P. Kriegel, The X-tree: An
Index Structure for High-Dimensional Data,, Proc. VLDB,
1996
[CG93] T. W. Christ, P. A. Godwin, "A Prison Guard Duress Alarm
Location System", Proc. IEEE International Carnahan
Conference on Security Technology, October 1993
[Cor90] T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction
to Algorithms, The MIT Press, 1990
[Fol90] Foley, van Dam, Feiner, and Hughes, Computer Graphics
Principles and Practice, 2nd Edition, Addison-Wesley, 1990
[GPS99] P. Enge, and P. Misra, Special Issue on GPS: The Global
positioning System, Proc. of the IEEE, pp. 3-172, January
1999
[Gut84] A. Guttman, R-Trees: A Dynamic Index Structure for
Spatial Searching, ACM, 1984
[Har94] A. Harter and A. Hopper, A Distributed Location System
for the Active Office, IEEE Network, January 1994
[Has93] H. Hashemi, The Indoor Radio Propagation Channel,
Proceedings of the IEEE, Vol. 81, No. 7, pages 943-968 July
1993
[Hod97] T. D. Hodes, R. H. Katz, E. S. Schreiber, and L. Rowe,
Composable Ad Hoc Mobile Services for Universal
Interaction, MobiCom 97 Proceedings, pp: 1-12, September
1997
[Jai91] R. Jain, The Art of Computer Systems Performance
Analysis, John Wiley, 1991
[Liu98] T. Liu, P. Bahl, "Mobility Modeling, Location Tracking,
and Trajectory Prediction in Wireless ATM Networks", IEEE
JSAC, Vol. 16, No. 6, pp. 922-936, August 1998
[Maa97] H. Maass, Location-Aware Mobile Applications based on
Directory Services, MobiCom 97, pp. 23-33, September
1997
[Nel98] G. J. Nelson, Context-Aware and Location Systems,
Ph.D. Theses, University of Cambridge, Computer Lab., UK.,
Jan. 1998
[Ous94] J. K. Ousterhout, Tcl and the Tk Toolkit, Addison-
Wesley Professional Computing Series, 1994
[Ric44] S. O. Rice, Mathematical analysis of Random Noise, Bell
Systems Technical Journal, Vol. 23 (1944), & Vol. 24 (1945)
[Rap96] T. S. Rapport, Wireless Communications Principles and
Practice, IEEE Press, 1996
[Roa96] Digital RoamAbout 915/2400 DS/PC Card and ISA
Network Adapter: Installation and Configuration, DEC, April
1996
[Sei98] T. Seidl, H. P. Kriegel, Optimal Multi-Step k-Nearest
Neighbor Search, Proc. ACM SIGMOD, 1998
[Sei92] S. Y. Seidel and T. S. Rapport, 914 MHz path loss
prediction Model for Indoor Wireless Communications in
Multi-floored buildings, IEEE Trans. on Antennas &
Propagation, Feb. 1992
[Tek98] S. Tekinay, Wireless Geolocation Systems and Services,
Special Issue of the IEEE Communications Magazine, April
1998
[Wal96] L. Wall, T. Christiansen, R. L. Schwartz, Programming
Perl, OReilly & Associates, Inc., 1996
[Wan92] R. Want, A. Hopper, V. Falcao, J. Gibbons., The Active
Badge Location System, ACM Transactions on Information
Systems, Vol. 40, No. 1, pp. 91-102, January 1992