LOCATION ESTIMATION IN WIRELESS NETWORKS
Except where reference is made to the work of others, the work described in this dissertation is my
own or was done in collaboration with my advisory committee. This dissertation does not include
proprietary or classi ed information.
Yiming Ji
Certi cate of Approval:
Kai H. Chang
Professor
Department of Computer Science and Soft-
ware Engineering
Sa ad Biaz, Chair
Assistant Professor
Department of Computer Science and Soft-
ware Engineering
Min-Te Sun
Assistant Professor
Department of Computer Science and Soft-
ware Engineering
Stephen L. McFarland
Acting Dean
Graduate School
LOCATION ESTIMATION IN WIRELESS NETWORKS
Yiming Ji
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Ful llment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
May 11, 2006
LOCATION ESTIMATION IN WIRELESS NETWORKS
Yiming Ji
Permission is granted to Auburn University to make copies of this dissertation at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
DISSERTATION ABSTRACT
LOCATION ESTIMATION IN WIRELESS NETWORKS
Yiming Ji
Doctor of Philosophy, May 11, 2006
(M.S., Computer Science, Southern Polytechnic State University, 2002)
(M.S., Aerodynamics, Nanjing University of Aeronautics and Astronautics , 1995)
(B.S., Aerodynamics, Nanjing University of Aeronautics and Astronautics , 1992)
169 Typed Pages
Directed by Dr. Sa ad Biaz
Wireless location determination has attracted much attention lately due to its many applications
in mobile (sensor) networking including target tracking and network intrusion detection. However,
it is challenging due to the complexities of the wireless radio propagation characteristics exacerbated
by the mobility of the mobile. In this dissertation, we propose realistic localization mechanisms for
both indoor and outdoor environments.
For the indoor localization, a common practice is to mechanically generate a table showing
the radio signal strength at different known locations in the building. A mobile user?s location at
an arbitrary point in the building is determined by measuring the signal strength at the location in
question and determining the location by referring to the above table using a LMSE (least mean
square error) criterion. Obviously, this is a very tedious and time consuming task. This dissertation
proposes a novel and automated location determination method called ARIADNE. Using a two di-
mensional construction oor plan and only a single actual signal strength measurement, ARIADNE
dynamically generates an estimated signal strength map comparable to those generated manually by
actual measurements. Given the signal measurements for a mobile, a proposed clustering algorithm
iv
searches that signal strength map to determine the current mobile?s location. Extensive experiments
with various deployment strategies have been carried out to evaluate the ARIADNE system at two
different buildings. The results indicate that the ARIADNE system outperforms all other existing
indoor localization schemes.
For outdoor wireless sensor networks, this dissertation proposes two reliable and precise dis-
tributed localization algorithms: iterative multidimensional scaling (IT- MDS) and simulated an-
nealing multidimensional scaling (SA- MDS). It uses only radio communication constraints to infer
node distances, and adapts the multidimensional scaling algorithm (MDS) in the localization re-
search. The research analytically establishes the upper- bound on the estimation error. The proposed
techniques can estimate all node positions even with limited and imprecise network knowledge.
Analysis and test runs show that the proposed methods are independent of the topology randomness
and the range measurement errors. Simulation results for the proposed methods yield an average
estimation error of about 25% of radio transmission range.
Besides the detailed research on localization, recently there has been an increasing interest in
exploring wireless communications, prototypes and measurements on real test- beds. In order to nd
a realistic tuning of simulation models, this research investigates one of the critical fundamentals
- the realistic radio range irregularity (RRI) model - according to the measurements made under
various settings. Using the RRI model, a set of representative localization algorithms are evaluated
and compared. Through detailed analysis and extensive simulations, the dissertation points out how
the localization performance is affected by the use of simplistic models. The RRI model re ects
and highlights the weaknesses of those algorithms and allows the design of countermeasures. This
dissertation also introduces a constrained-greedy forwarding radio propagation method to remedy
the negative effects encountered under actual operating environments.
v
ACKNOWLEDGMENTS
I have had an very exciting time at Auburn University. The learning and research experience
were the best I have ever had. I appreciate all the excellent professors from whom I gained help and
instructions through my study.
First, I would like to express my great appreciation to Dr. Kai Chang. He has always been
patient and quick to response to my needs with cordial advice. It is under his suggestion and
recommendation that I can have the fortune to become a student of Dr. Sa ad Biaz. Also, I am
grateful for the detailed suggestions he contributed to this work.
I thank Dr. Sa ad Biaz for taking me under his tutelage. Working with him, my dream of
becoming a professor was reignited. I was always impressed by his instructions and sharp insights
to technical issues. He introduced me to the eld of wireless engineering and greatly broadened my
understanding in this eld. I would never forget his inspiration and encouragement that helped me
throughout my PhD program. It is a great pleasure to work with Dr. Biaz, and what I have learned
from him will de nitely guide all my life. I highly appreciate his signi cant efforts in helping and
guiding me!
I thank Dr. Min-Te Sun for his excellent advice on my personal development. He is reliable
and always kind to me. I thank him for the great contribution to this dissertation.
I thank Dr. Stanley Reeves from the department of Electrical and Computer Engineering, I
thank him for the reading and detailed comments for this work. It is under his tutelage that I entered
the area of the digital image and multimedia. Although I chose the wireless engineering as my
major, the knowledge from Dr. Reeves will de nitely help me in the future.
vi
Style manual or journal used Journal of Approximation Theory (together with the style known
as auphd ). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speci cally LATEX) together
with the departmental style- le auphd.sty.
vii
TABLE OF CONTENTS
LIST OF FIGURES xi
1 INTRODUCTION 1
1.1 Indoor Localization Systems Research . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Outdoor Localization Systems Research . . . . . . . . . . . . . . . . . . . . . . . 5
2 LITERATURE REVIEW 9
2.1 Distance Measurement Technologies . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Satellite Positioning Technologies . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Network-based Technologies . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Literature Review for Indoor Localization Systems . . . . . . . . . . . . . . . . . 13
2.2.1 Map generation module . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Search module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Similar Indoor Localization Systems . . . . . . . . . . . . . . . . . . . . . 21
2.2.4 Review of Sniffers Deployment Method . . . . . . . . . . . . . . . . . . . 23
2.3 Literature Review for Outdoor Localization Systems . . . . . . . . . . . . . . . . 24
2.3.1 Outdoor Localization Algorithms . . . . . . . . . . . . . . . . . . . . . . 24
2.3.2 Radio Range Irregularity . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3 RESEARCH DETAILS FOR INDOOR LOCALIZATION SYSTEMS 42
3.1 Map Generation Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.1 Floor plan interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.2 Ray tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.3 Radio propagation model . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.1.4 Parameters Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2 Search module: Clustering-based Search Algorithm . . . . . . . . . . . . . . . . . 50
3.2.1 Data Collection and Cluster Preparation Phase . . . . . . . . . . . . . . . 52
3.2.2 Clustering Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3 Mobility Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4 Sniffers Deployment Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4.1 De nition and Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.2 Method to Calculate the Overlapping Area for Multiple Circles/Rings . . . 63
3.4.3 Optimal Sniffers Deployment Method . . . . . . . . . . . . . . . . . . . . 65
viii
4 RESEARCH DETAILS FOR OUTDOOR LOCALIZATION SYSTEMS 73
4.1 De nitions and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.1.1 Deployment Randomness . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.1.2 Estimation Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.1.3 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.1.4 Radio Communication Constraints . . . . . . . . . . . . . . . . . . . . . . 75
4.2 Augmented Multidimensional Scaling . . . . . . . . . . . . . . . . . . . . . . . . 76
4.2.1 Classical and iterative MDS . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.2.2 Simulated Annealing MDS Algorithm . . . . . . . . . . . . . . . . . . . . 79
4.3 MDS Processing Coverage Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.4 Precision Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.4.1 Theoretical Estimates for Multidimensional Scaling Algorithm . . . . . . . 82
4.4.2 Theoretical Estimates for Least Square Algorithm . . . . . . . . . . . . . . 83
4.4.3 Algorithm Precision at Various Perturbations . . . . . . . . . . . . . . . . 86
4.5 Radio Range Irregularity Research . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5.1 Radio Range Analysis and Measurement . . . . . . . . . . . . . . . . . . 88
4.5.2 Radio Range Irregular Model . . . . . . . . . . . . . . . . . . . . . . . . 93
4.5.3 Effect of RRI and Optimization . . . . . . . . . . . . . . . . . . . . . . . 95
4.5.4 Constrained-Greedy Forwarding Radio Propagation Method . . . . . . . . 98
5 APPLIED RESULTS FOR INDOOR LOCALIZATION SYSTEMS 101
5.1 Experiment I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.1.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.1.2 Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.1.3 Radio Propagation Model Validation . . . . . . . . . . . . . . . . . . . . . 103
5.1.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.1.5 Number of Necessary Reference Measurements And Location Dependency 107
5.1.6 Coverage Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.1.7 Localization Performance . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.1.8 Impact on Grid Resolution between Reference Points . . . . . . . . . . . . 112
5.1.9 Mobile User Localization . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.2 Experiment II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.2.1 Sniffers Con guration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.2.2 Signal Strength vs. Distance . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.2.3 Radio Propagation Model Validation . . . . . . . . . . . . . . . . . . . . . 117
5.2.4 Impact of Different Sniffers Position Con guration . . . . . . . . . . . . . 120
5.2.5 Number of Available Sniffers . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2.6 Column/Post Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2.7 Furniture Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.8 Cell-based Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.9 Humidity Effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.2.10 Dynamic SS-MAP Update . . . . . . . . . . . . . . . . . . . . . . . . . . 128
ix
5.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6 APPLIED RESULTS FOR OUTDOOR LOCALIZATION SYSTEMS 131
6.1 Environment and Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.2 Algorithm Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.3 Algorithm Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3.1 Reported performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3.2 Localization Performance under Same Network Environment . . . . . . . 136
6.4 Simulation Results for Radio Range Irregularity . . . . . . . . . . . . . . . . . . . 138
6.4.1 Network setting and localization metrics . . . . . . . . . . . . . . . . . . . 139
6.4.2 Performance under Irregular Radio Networks . . . . . . . . . . . . . . . . 139
6.4.3 Optimized Propagation on Real Networks . . . . . . . . . . . . . . . . . . 143
7 CONCLUSIONS 145
7.1 Indoor Localization Research Conclusion . . . . . . . . . . . . . . . . . . . . . . 145
7.2 Outdoor Localization Research Conclusion . . . . . . . . . . . . . . . . . . . . . 147
BIBLIOGRAPHY 149
x
LIST OF FIGURES
2.1 Signal Strength Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Euclidean propagation model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3 (a) Distance-based approach. (b) Radio pattern based approach. . . . . . . . . . . 34
2.4 (a) Constraint with one-hop beacon message. (b) Constraint with two-hop beacon
message. (c) Old position estimation of a normal node. (d) New estimation by
intersecting the constraint with the old estimate. . . . . . . . . . . . . . . . . . . 36
2.5 MDS localization example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1 ARIADNE system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Original oor plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3 Floor plan interpretation output . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Radio propagation with ray tracing . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.5 Position isolation example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.6 Distance between objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.7 Decision making in tracking mobile user . . . . . . . . . . . . . . . . . . . . . . . 57
3.8 Signal strength vs. range for indoor radio propagation . . . . . . . . . . . . . . . . 59
3.9 Uncertainty area of the indoor location estimation . . . . . . . . . . . . . . . . . . 61
3.10 Uncertainty area of two different sniffers deployment . . . . . . . . . . . . . . . . 61
3.11 Sniffer con guration de nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.12 Area calculation method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.13 Uncertainty area at various con gurations . . . . . . . . . . . . . . . . . . . . . . 66
xi
3.14 Uncertainty area of one con guration at various angles fi . . . . . . . . . . . . . . 67
3.15 Average uncertainty distance at all grid positions in a square area . . . . . . . . . . 69
3.16 Average uncertainty distance of all grid positions within/outside the triangle . . . . 69
3.17 Ideal sniffers deployment method . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.1 Radio communication scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2 SA-MDS and IT-MDS algorithm example . . . . . . . . . . . . . . . . . . . . . . 80
4.3 MDS estimation coverage analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.4 Theoretical estimation errors under various perturbations . . . . . . . . . . . . . . 86
4.5 Signal strength in clear space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.6 Signal strength in forest land . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.7 Signal strength near a tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.8 Signal strength near a stone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.9 Signal strength cross bush . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.10 Radio irregularity model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.11 Routing path under regular and irregular radio transmission . . . . . . . . . . . . . 96
4.12 Routing optimization under irregular radio transmission . . . . . . . . . . . . . . . 99
5.1 Floor plan with sniffers and data validation positions (???: reference positions in
SS-MAP table) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.2 Estimation and comparison with measurements at data validation positions . . . . . 105
5.3 MSE vs. number of reference measurements . . . . . . . . . . . . . . . . . . . . . 107
5.4 Reference Measurement Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.5 Signal strength shaded surface at sniffers A, B, and C . . . . . . . . . . . . . . . . 109
5.6 Grid resolution on the performance of clustering localization . . . . . . . . . . . . 112
xii
5.7 Floor plan with data validation positions . . . . . . . . . . . . . . . . . . . . . . . 115
5.8 Various sniffer deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.9 Indoor RSSI vs. distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.10 Indoor radio propagation model validation . . . . . . . . . . . . . . . . . . . . . . 118
5.11 Average uncertainty distance of the estimation for con guration (c) & (d) . . . . . 122
5.12 Signal Strength of the Sniffer at the lower corner (con guration (d)) . . . . . . . . 123
5.13 Floor plan without construction columns . . . . . . . . . . . . . . . . . . . . . . . 125
6.1 Precision with the anchor ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.2 Precision with randomness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.3 Precision with the 1-Hop range error . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.4 Precision with the accumulated Euclidean error . . . . . . . . . . . . . . . . . . . 134
6.5 Precision analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.6 Comparison with X. Ji?s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.7 Algorithms comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.8 Maximum attenuation on the performance of localization . . . . . . . . . . . . . . 141
6.9 Number of edges on the performance of localization . . . . . . . . . . . . . . . . . 142
6.10 Maximum radio range on the performance of localization . . . . . . . . . . . . . . 143
6.11 Radio propagation optimization on the performance of localization . . . . . . . . . 144
xiii
CHAPTER 1
INTRODUCTION
Recently, the demand for wireless communications has grown tremendously. The increasing
market for information anywhere anytime has been a driving force for the increasing advances in
mobile wireless communication. To meet the anywhere anytime challenge, many issues remain to be
addressed. Location management and mobility management are two critical issues to be analyzed in
order to provide seamless and ubiquitous computing environment for mobile users. Consequently,
many localization systems have recently been proposed (Bulusu, Heidemann and Estrin, 2000 [1];
Bahl and Padmanabhan, 2000 [2]; Chen and Kobayashi, 2002 [3]; Chincholle, Eriksson and Burden,
2002 [4]; Haeberlen et al., 2004 [5]; Niculescu and Nath, 2004 [6]).
To determine the position of a user, three basic methods are available:
1. Range based lateration method, which requires at least three distinct estimates of the distance
from the user to known xed locations (Savarese, 2002 [7]; Savvides, Park and. Srivastava,
2004 [8]; Ji and Zha, 2004 [9]; Hu and Evans, 2004 [10]);
2. Direction based angulation method that involves the direction or angle of arrival of at least
two distinct signals from known locations (Niculescu and Nath, 2004 [11]; Niculescu and
Nath, 2004 [6]);
3. Location ngerprinting method where location dependent signal characteristics (i.e. nger-
prints like signal strength, image, sound, or other unique information) are pre-collected and
stored in a database table. To locate a user, the current ngerprint of the mobile is measured
1
and used to search the database to nd a matching position ( Hills, Schlegel and Jenkins.,
2004 [12]; Krishnan et al. 2004 [13]; Hatami and Pahlavan; 2004 [14]).
The range based lateration and direction based angulation methods are effective for line-of-
sight radio signals, and thus they are mainly used for outdoor localization systems. Due to the
multipath propagation properties of the indoor environment, the method of location ngerprinting
is generally used in indoor location systems.
This dissertation focuses on the design, analysis, and evaluation of both indoor and outdoor
localization systems. The objective is to develop precise and automatic localization systems that do
not depend on special hardware support and incur minimum deployment and maintenance cost.
For both indoor and outdoor environments, this dissertation exploits the wireless technology
between communication nodes. For example, the received signal strength indicator (RSSI) from
off-the-shelf wireless cards is exploited for the localization implementation. In this dissertation,
RSSI is referred as signal strength. This dissertation considers the popular widely deployed 802.11
systems operating in the ISM band (2.4 GHz). However, the developed methodologies may well be
implemented over any RF (radio frequency) technology.
This next two sections respectively introduce the research for the indoor and outdoor localiza-
tion systems. Section 1.1 presents the research for the indoor localization system, and section 1.2
describes the outdoor system.
1.1 Indoor Localization Systems Research
Due to the multipath radio propagation characteristics, the indoor localization research remain
to this day challenging tasks for the research community. If the radio propagation signal strength is
2
tightly correlated with the distance between the transmitter and the receiver, then the location deter-
mination is simple in that only three quadratic equations need to be solved for two unknowns (2-D
environment). Unfortunately, the relationship between the radio signal strength and the distance
is not straightforward for the indoor radio propagation. Additionally, due to the dynamic property
of the indoor radio propagation, the signal strength at the same location varies over time. These
dif culties make a solution of indoor localization quite complex and elusive.
Therefore, the location ngerprinting method is generally more applicable for the indoor envi-
ronment. In this method, the reference signal strength of a mobile user is collected, in advance, at
many locations throughout the site. A database table comprising of the location information along
with the reference signal strengths associated with that location is then built. In this dissertation, we
call the database table as Signal Strength Map table (SS-MAP). If there are total n sniffers, a typical
record in the signal strength map table is in the form of: < locationID;SS1;:::;SSn >, where
LocationID is the tag associated with the location or coordinates on the oor plan, SSj (1 ? j ?
n) is the signal strength sensed by jth sniffer when the user is present at the location correspond-
ing to LocationID. To locate the position of a mobile user, sniffers measure the signal strength
of the received packet and compare with the records in signal strength map table. The position
corresponding to the best match is used to represent the position of the mobile user [2, 3].
For the location ngerprinting method used in the indoor localization research, previous works
either rely on specialized hardware, or require extensive manually measurements. For example,
Krishnan et al [13] presents an adaptable infrastructure-based system that uses the ?stationary emit-
ters? to periodical collection of signal strength at speci c locations on the site. And Haeberlen et al
[5] took 28 man-hours to build a signal strength map that covers an area of 12,000 sq. meters. The
hardware approach usually arouses high cost associated with devices, installation, and maintenance.
3
And the brute force measurement does not take into account the time-varying nature of the indoor
radio signal strength and would necessitate remeasurement to keep track of changes due to variation
in propagation environment like human occupancy, furniture and partition updates. These existing
methods are not practical for general large-scale applications.
Therefore, the goal for this dissertation is to develop an automated and dynamic indoor local-
ization method. The research is interested in a general indoor localization environment where no
special hardware is required thus incurring lower deployment and maintenance cost.
In the dissertation, the research considers the localization of a mobile user on the same oor
where the properties of the indoor partitions are not signi cantly different; or in other words, the
construction materials and the thickness of all walls are similar. This research focuses on the
network-based localization system where the location of the user is determined by the network. In
this system, the user?s signal strength must be sensed by three or more sniffers which are deployed
at known positions.
Much research has been done in this area and many good solutions have been proposed for the
indoor localization system. However, four common problems remain to be solved for most indoor
systems:
1. None of existing systems consider the dynamic property of the indoor radio propagation;
2. No systems systematically evaluate the whole indoor system;
3. All systems require extensive measurement to either manually construct signal strength map
or to estimate the site speci c attenuation parameters;
4. If special hardware is to be used, detailed deployment and maintenance are required.
4
Consequently, most existing indoor systems fail to address the cost and complexity of the system
deployment and maintenance, and they are unsuitable for large-scale deployment. Therefore, an
automated and scalable indoor localization system is highly desirable.
1.2 Outdoor Localization Systems Research
Recently, location-based services have gained considerable attention from both academia and
industry. Current reported applications and services include coverage analysis [15, 16], location-
aware applications [17, 18, 4, 19, 20, 21], environmental monitoring [22, 23], target tracking [24,
25], battle eld surveillance [26], and intrusion detection [27]. In addition, location management
and ef cient routing protocols also require location knowledge (Perlman and Haas, 1999 [28]; Ko
and Vaidya, 2000 [29]).
The mobile?s location at outdoor environment can easily be obtained by GPS enabled systems
with a good precision. However, GPS system is inappropriate for large scale deployment of ad hoc
sensor networks because of constraints in volume, power consumption and cost.
An alternative to GPS is the use of distributed localization algorithms that enable nodes to
determine their relative positions. If absolute positions are necessary, a limited number of nodes
(called anchors) must have the capability of determining their absolute positions. Anchors can get
their absolute position using manual con guration or techniques such as GPS. Much localization
research has been carried out recently using this approach [30, 8, 9, 31, 10].
Based on the reliance on the hardware support, localization algorithms can be classi ed into
two main categories: range-based algorithms and range-free algorithms. Range-based algorithms
rely more on hardware support by applying either one or a combination of TOA, TDOA, AOA,
5
or RSSI technologies. On the contrary, range-free algorithms require less or no hardware support
[31, 32, 33, 34, 35].
Absolute positions are necessary for many applications. But some applications require only
the knowledge of nodes? relative position (without actual physical or absolute position information).
This means that, at least for some applications, the position information can be relative instead of
absolute [36, 37]. Consequently, the localization algorithms can also be categorized as absolute and
relative.
For the traditional outdoor localization research, the research community usually exploits sim-
ple radio propagation models in localization simulations to investigate and evaluate the localization
algorithms and protocols. This simple model assumes spherical radio transmission pattern of xed
range at all wireless nodes [11, 16, 38]. However, results on the eld widely differ from simulation
results. The research community become aware that simplistic models may lead awed proto-
cols. A key reason is that radio propagation is irregular [39, 33]. Pawlikovski et al. [40] surveyed
2200 published network simulation results and identi ed that the simple circular model is popularly
adopted by most researchers and simulators. From experiments, Pawlikowski showed that the ideal
radio model yields results radically different from reality. Kotz et al. [41] reviewed six of the most
used simplistic assumptions and showed their individual impact on the obtained results. Thus, the
credibility of applications/protocols based simplistic model is dubious.
Thus, most existing localization algorithms contain four major problems:
1. Most existing algorithms work only under speci c and restrictive network conditions.
When such conditions are not met, the con dence in location estimates is not satisfactory
and makes key decisions hard and risky;
6
2. Most algorithms require excessive network communications and complex re nement pro-
cedures with multiple computing rounds that are energy inef cient for small devices in ad hoc
networks;
3. Precision evaluation of these algorithms is conducted using different metrics and criteria
making uneasy the comparison of algorithms.
4. Bi-directional communication links are commonly used by most algorithms, where perfect
circular radio pattern (in a 2D environment) and xed radio range are assumed at all nodes.
For a general sensor network, radio transmission range at different nodes is not xed, and the
radio shape is irregular in nature. Consequently, a practical radio model is highly needed, and
the impact of the irregular radio pattern on the localization performance has to be analyzed.
The objective of the outdoor localization research in this dissertation is to develop practical
localization algorithms that work on the most general environment, and the radio transmission shape
could be non-circular. The interest of the research is on wireless sensor networks, where nodes are
randomly deployed at interested environment,
The research assumes that:
1. Some nodes, called anchor nodes, know their physical positions in advance by special de-
ployment or by the use of GPS. The others are called normal nodes.
2. Each node can measure, through the received signal strength indicator (RSSI), the approxi-
mate range to its immediate neighbors.
3. Certain routing optimization mechanisms are employed such that each node only maintain
the least hop counts to a sender.
7
Consequently, the goal of the outdoor localization research in this dissertation is to: 1) develop
a practical localization algorithm that works on the most general environments; and 2) construct a
real test-bed for the wireless research where the radio communication is based on a realistic non-
circular radio pattern model in which the radio range is adjustable according to different operating
environment.
The rest of the dissertation is organized as follows: Chapter 2 presents a literature review for
both indoor and outdoor localization systems. Chapter 3 introduces proposed methodology for the
indoor localization systems, and Chapter 4 describes the detailed research for the outdoor localiza-
tion systems. Chapter 5 discusses applied results for the proposed indoor localization system. Chap-
ter 6 gives the applied results and comparison outcomes for the outdoor localization algorithms, and
Chapter 7 concludes the dissertation.
8
CHAPTER 2
LITERATURE REVIEW
This chapter surveys the related research for both the indoor and outdoor localization systems.
In Section 2.1, we rst introduce various range measurement techniques. Sections 2.2 and 2.3 are
respectively dedicated to the introduction of indoor and outdoor localization systems.
2.1 Distance Measurement Technologies
This section reviews existing distance measurement technologies. Based on the applied hard-
ware and the operating environment, the distance measurement technologies can be categorized into
the following two main categories:
1. Satellite positioning technologies, which include Global Position System (GPS), Differen-
tial GPS (DGPS), Assisted GPS (A-GPS), Wide Area Augmentation System (WAAS), and
Galileo system (European version of GPS);
2. Network-based technologies, which include Time of arrival (TOA), Time difference of arrival
(TDOA), Angle of arrival (AOA), Enhanced observed time difference (E-OTD), and Received
signal strength indicator (RSSI).
The following sections brie y review these measurement techniques.
2.1.1 Satellite Positioning Technologies
? Global Positioning System (GPS), GPS consists of three components: satellites, control
stations, and GPS receivers [42].
9
The GPS system consists of 24 orbiting operational satellites, which can transmit very low
power radio signals that allow any GPS receiver to determine its position on the Earth. Among
the 24 satellites, 21 of them are active at any time, and the rest three are backups.
GPS control system monitors the satellites and providing them with correct orbital and clock
data. There are ve control stations around the world.
In order to determine the position, the receiver needs to know at least four satellites? location
and the distance to them. The approximate location of the satellites is obtained from the
satellites directly. The approximation can be adjusted by using data from control stations.
The distance from the receiver to the satellite is calculated as the product of radio speed and
the radio travel time between them. The travel time is estimated from the difference of the
?pseudo-random? code generated at the same time by the satellite and the receiver. With the
information of four or more satellites, the position of the receiver can be determined.
There are two levels of service provided by GPS. The more-accurate one is Precise Position-
ing Service (PPS), which is only available to authorized users and is intended for military
usage. The less-precise service is Standard Positioning Service (SPS), which is available
for all civil users worldwide without charge or restrictions. According to [43], the position
estimation error for PPS is between 5-10m. The reported SPS horizontal accuracy by U.S.
Department of Defense is of ?100m at 99.5% con dence level and ?300m at 99.9%. In
[44], an error of ?185m in latitude and ?216m in longitude was reported.
? Differential GPS (DGPS), Assisted GPS (A-GPS) and Wide area augmentation system
(WAAS)
10
DGPS is an extension of the GPS system intended to improve the accuracy of the GPS system.
DGPS uses stations to broadcast position correction beacons. With these correction messages,
GPS receivers can correlate them with received satellite signals. This technology effectively
reduces the effect of selective availability (SA) and propagation delay. It is reported that
DGPS provides an estimation with 2 to 10 meters accuracy [45, 46].
A-GPS is a technique that improves the functionality and performance of GPS using only
GPS satellite signals. It works by integrating the classic GPS information with sophisticated
geographic software and mobile/cellular network information. A-GPS is currently widely
used in many systems, and the accuracy in system U-Map is within 5 meters [46].
WAAS is similar to DGPS and it is initially intended to be used for precision ight control
by the Federal Aviation Administration (FAA) and the Department of Transportation. WAAS
system consists of a network of approximately 25 ground reference stations in the USA. And
it provides a very large service area where the DGPS source may not be available. The
reported accuracy is approximately seven meters.
? Galileo system
Galileo is the European version of satellite navigation system, it is a system that both com-
petes and complements with the US GPS system [47].
The fully deployed Galileo system will consist of 30 satellites, with 27 of them operational
and the other three as active reserves. With dual frequencies, Galileo delivers real-time posi-
tioning accuracy of meter range.
11
2.1.2 Network-based Technologies
? Time of Arrival (TOA): This technology works by measuring the arrival time of a known sig-
nal sent from a (mobile) node received at three or more measurement units. Synchronization
of the measurement units is essential. Therefore, this method requires additional measure-
ment hardware unit in the network at the geographical vicinity of the (mobile) node so as to
accurately measure the TOA of the signal bursts. It is reported that the accuracy of TOA is
about 100?200m [48].
? Time Difference of Arrival (TDOA): This technology works similar as TOA in that both
technologies utilize signal propagation time. In TDOA, however, two types of signals are
selected so that their propagation speeds are signi cantly different. When a transmitter sends
two types of signals simultaneously, the receiver can easily detect the difference in the time of
arrival between the two types of signals. The time difference can then be used to compute the
distance between the communication pairs. To deal with multipath problems, TDOA systems
has been historically based on wide-band radio technology. The known accuracy is about
100?200m.
? Enhanced Observed Time Difference (E-OTD):In this method, it is the (mobile) node that
performs the time measurement of beacon signals from nearby base stations. This method
does not require synchronization in the network. The reported accuracy for E-OTD is 50 ?
200m.
? Angle of Arrival (AOA): This method requires special antenna arrays at the base station to
determine the angle of the arriving signal from the mobile node. The angles from two or more
12
base stations can determine the position of the node by the intersection of the signal arrival
directions. The accuracy is 100?200m.
? Received Signal Strength Indicator (RSSI), this method measures the strength of the re-
ceived signal in order to deduce the possible range the signal has propagated from the sender
to the receiver. It is applicable if the transmission power is constant or known in advance.
RSSI is a low accuracy localization method. However, it is simple and doesn?t require extra
equipment. Consequently, it is widely supported by most current wireless devices.
2.2 Literature Review for Indoor Localization Systems
Due to multipath propagation in indoor environments, indoor localization systems generally
require specialized hardware to be deployed. Depending on hardware technologies, indoor local-
ization systems may be broadly classi ed as non-RF and RF based systems.
Non-RF based location systems were designed using a speci c technology independent from
data communication networks. Such location systems exploit 1) infrared (IR) (Active Badge , Want
et al. (1992), [49]); 2) ultrasound, Ward, Jones, and Hopper, (1997) [50, 51, 52]; 3) magnetic eld
[53]; or 4) light (cameras), krumm et al., (2000) [54]. Such early location systems require special-
ized hardware used only for the location determination and incur in general a high deployment and
maintenance cost.
In the recent years, the popular success and widespread deployment of RF 802.11 wireless
networks enticed many researchers to explore existing RF 802.11 wireless network infrastructure to
build location systems. Consequently, RF based indoor positioning systems generally exploit RF
signal strength sensed at reference sniffers or base stations.
13
Emitter A
Emitter C
Emitter B
Sniffer A Sniffer B
Sniffer C
Mobile (M) Mobile (M)
(a) Client?based scheme (b) Network?based scheme
Figure 2.1: Signal Strength Measurement
Oversimplifying, if the signal strength of the radio propagation is tightly correlated with the
distance between emitter and receiver, then location determination would be a trivial problem that
could be solved by one of the following two approaches as illustrated in Figure 2.1.
Figure 2.1(a) illustrates a client-based scheme where three emitters A, B, and C are at known
positions. A mobile (client) would listen successively to the three emitters and would measure the
signal strength from them. If the measured signal strength yields the distance from each emitter to
the mobile, the location of the mobile reduces to the solution of a simple system of three quadratic
equations with two unknowns (assuming the mobile moves in a plan). Note that in this scheme, the
client has an active part in the location process: it measures the signals and infers its location.
A dual approach, the network-based scheme, is illustrated in Figure 2.1(b): three sniffers at
known positions listen to the mobile and measure the signal strength of received packets. It suf ces
to collect the signal strength measurements (over the network!) from the three sniffers to determine
the location using basic calculations. Unfortunately, the relationship between signal strength and
distance is not straightforward and is dynamic in nature: even if a mobile does not move, the sniffers
14
in Figure 2.1(b) will measure the signal strength that varies over time. Moreover, two mobiles that
are quite close may generate signals of signi cantly different strength at the same sniffer. These
dif culties make a solution to location determination quite elusive.
In order to address this problem, researchers proposed a two-step solution: First, establish
a signal strength map SS-MAP where the signal strength at known and predetermined locations is
either manually measured or theoretically estimated, and Second, measure signal strength for a
mobile at a given location and SEARCH the signal strength map SS-MAP for the closest location
that with the best signal strength measurement match.
The RADAR [2] system proposed by Bahl and Padmanabhan is exemplary of such an ap-
proach: the authors adopt a client-based scheme to collect the radio signal strength received from
three base stations at a mobile (method in Figure 2.1(a)) at a selected set of predetermined and
known locations. The scheme records the collected signal strength as a function of location, and
such records constitute what we call a signal strength map SS-MAP. This measured signal strength
map was used by the authors in two different strategies: (1) the rst strategy (they dubbed em-
pirical method ) consists of the mobile sensing the signal strength from the three base stations and
searching for a record in the measured SS-MAP for the best signal strength measurements match;
and (2) the second strategy consists of using a simple propagation model to construct an estimated
SS-MAP that is validated using the measured SS-MAP.
Estimating is more convenient than measuring a SS-MAP especially for a large building. The
estimated SS-MAP is used the same way as the measured SS-MAP in strategy 1. Unfortunately,
the authors [2] report that the rst strategy (i.e., the empirical method ) outperformed the second
strategy that uses the estimated SS-MAP. The key weakness of the second strategy is that the radio
propagation model results in an estimated SS-MAP does not t well the measured one.
15
This dissertation proposes a convenient and scalable network-based location system, and de-
nes two modules corresponding to the above two-step solution. The rst MAP GENERATION
module estimates a signal strength map SS-MAP, and the second SEARCH module determines the
location of the mobile when given the input the current measured signal strength of the mobile.
We introduce related research for the two modules in Section 2.2.1 and Section 2.2.2, respectively;
and Section 2.2.3 reviews the similar indoor localization systems. In Section 2.2.4, we separately
introduce the sniffers deployment in previous research.
2.2.1 Map generation module
A signal strength map (SS-MAP) usually contains a dense grid of locations together with the
measured signal strength at those positions. Considering a total of n sniffers in a network-based
indoor localization system, a typical record in the signal strength map table is in the form of:
< locationID; SS1; :::; SSn >, where locationID is the tag associated with the location or
coordinates on the oor plan, and SSj; (1 ? j ? n) is the signal strength sensed by jth sniffer
when the user is present at the location corresponding to j.
In this research, three sniffers1 (A;B and C) are used to monitor the signal strength of the
mobile user, and the signal strength measurements made by the three sniffers is called one signal
strength measurement triplet. To locate the position of a mobile user, sniffers measure the signal
strength of the received packet and compare the signal strength measurement triplet with the records
in SS-MAP. The position corresponding to the best match is used to represent the position of the
mobile user (Chen and kobayashi, 2002 [3]; Bahl and Padmanabhan, 2000 [2]).
1In Chapter 3, we also consider four or ve sniffers in order to derive an optimal sniffers deployment strategy.
16
To build the signal strength map SS-MAP, most indoor localization systems take the manual
measurement method, which is carried out by manually measurements of signal strength at short
intervals within the building (empirical method). The manual measurement is time-consuming.
Moreover, the manually measurements cannot take into account the time-varying nature of the signal
strength, and would necessitate remeasurement to keep track of changes due to the variation in
propagation environment (ex. Human occupancy, furniture and partition updates).
To address the dynamic property of the radio propagation, Krishnan et al. (2004) [13] presents
an adaptable infrastructure-based system. The system suggests the deployment of ?stationary emit-
ters? to collect signal strength at speci c locations on the site, and thus it is called ?stationary
emitters? method. Apart from the cost associated with the purchase of such devices, installation
issues such as placement and power supply need to be considered for large scale deployment.
Therefore, in order to construct a signal strength map SS-MAP, the empirical method and the
?stationary emitters? method fail to address the cost and complexity of the system deployment and
maintenance. Hence, many research tries to nd a indoor radio propagation model that estimates
the signal strength at reference locations. The next section will separately survey related work for
the radio propagation model.
Indoor Radio Propagation Model
Research on indoor radio propagation is an active eld. A study of indoor radio propagation
characteristics can be found in [55, 56]. A detailed description of earlier radio propagation models
can be found in [57]. Based on the ray tracing technique, several statistical models have been ana-
lyzed recently [58, 59, 12]. When considering the large-scale attenuation model, most researchers
17
model the radio propagation path loss as a function of the attenuation exponent n (Please, see Equa-
tion 2.1), which is two for free space but greater than two for an indoor environment.
P(d)[dB] = P(d0)[dB]?10?n?log10( dd
0
) (2.1)
where P(d) is the power at distance d to the transmitter in meters; P(d0) is the power at a reference
distance d0, usually set to 1.0 meter. n is the attenuation exponent, which is often statistically
determined to provide a best t with measurement readings.
Based on the considered parameters in the radio propagation model, all radio propagation
models can grossly be grouped into three categories: (1) Simple attenuation model; (2) Partition
model; and (3) Site-speci c model.
Simple attenuation model is in the form of Equation 2.1, and it is the base model for the other
models. Hills, Schelegel, and Jenkins [12] used this model as part of an automated design tool to
estimate the coverage areas for a set of APs. With point-by-point measurement, Hills et al. report
that an attenuation exponent of 2.60 yields the best t in the buildings on the Carnegie Mellon
University campus. A difference of 3.0dB between the measurements and estimates is achieved in
most cases.
Different from the simple attenuation model, the partition model reduces the pass loss effect
from the attenuation exponent by additional consideration of the attenuation effects from the in-
door partitions, like walls and oors. Many successful models belong to this group. A couple
of famous examples include Phaiboon?s statistical model [59], and wall attenuation factor model
in RADAR [2]. Phaiboon?s model considers multiple oor environment. The test results show
the estimated signal strength from the partition model agrees better than that of simple attenuation
18
model [59]. In contrast, the RADAR system considers attenuation effects from walls along the di-
rect path between the transmitter and the receiver on the same oor. RADAR?s location search in
the estimated signal strength map SS-MAPyields an average resolution of about 4.3m [2].
Site-speci c model is similar as the partition model except that it relates to path loss with
site-speci c parameters (geometrics, materials, and thickness). Two representative models include
Hassan-Ali and Pahlavan?s probability model [58], and Lott and Forkel?s multi-wall-and- oor model
[60]. Hassan-Ali et al. compared the estimated signal strength with measurements using a probabil-
ity model. The results of mean error of 2.77dB and standard deviation of 2.87dB are obtained [58].
Compared with the other models, the site-speci c model does not depend on special assumption,
so it works on most general building environment. However, it is complex and requires detailed
site-speci c parameters.
All these radio propagation models have the following shortcomings:
1. Tedious and extensive on-site reference measurements are required in order to determine the
building-speci c attenuation exponent and the attenuation coef cients of indoor partitions;
2. The measurements do not consider the dynamic behavior of the indoor radio propagation;
3. They only consider the path loss along the direct path between the transmitter and the receiver;
4. Detailed material characteristics and geometry properties are required if site-speci c model
is to be used.
Hence, in order to construct a signal strength map SS-MAP, most existing RF-based indoor
localization systems are not able to cope with the dynamic property of the indoor radio propagation.
They are unpractical for general large-scale applications. Therefore, to build a practical indoor
19
localization system, it is of particular interest to develop accurate and time-ef cient methods that
dynamically construct site-speci c signal strength map.
2.2.2 Search module
As pointed out earlier, for localization of a wireless user, the signal strength map SS-MAP is
searched based on the signal strength measurements at sniffers in the ?on-line? phase. To search the
SS-MAP table, a general comparison metric is the least mean square error (LMSE).
D = minNk=1f1n(
nX
i=1
(ssm;i ?ssi)2)12g (2.2)
where D is the least mean square error, N is the total number of records in the signal strength map
table, k denotes the kth record in the SS-MAP table; n is the number of sniffers. ssm;i denotes
measured signal strength at sniffer i of the mobile user, and ssi is the signal strength record at a
sniffer i in SS-MAP table. The nearest neighbors in signal space method by Bahl and Padmanabhan
(2000) [61] is essentially this approach.
A problem with LMSE is that two or more very different locations could potentially have same
signal strength, thus additional processing must be carried out in order to select a more accurate
estimate. Therefore, more advanced localization methods are highly desirable.
Prasithsangaree, Krishnamurthy, and Chrysanthis (2002) [62] proposed a closeness elimination
scheme. The main purpose is to nd more than three locations from the SS-MAP table with signal
strength close to the measurement. From these, the three closest positions are selected and their
position average is used to denote the estimated location for the mobile user. Similarly, in [63],
Pandey (2004) et al. used the second lowest MSE to assist the estimation. They found that if the
20
LMSE and the second lowest mean square error are physically adjacent, then the middle of their
locations yields better estimates.
Hatami and Pahlavan (2004) [14] also proposed a modi ed LMSE algorithm, dubbed prior-
itized maximum power. This method sorts measured signal strength in descending order for all
sniffers so that a contribution priority of each sniffer in the mapping procedure is obtained. Accord-
ing to the priority, the estimates are restricted to a set of reference points. Then LMSE or closeness
elimination scheme is used to determine the nal estimates.
Existing search algorithms works on accurate and dense grid signal strength map; and the
search usually nd an exact hit (LMSE) or a small set of positions close to each others (closeness
elimination scheme). In reality, the signal strength map is imperfect. Measurements take time and
the radio propagation is subject to change with environment, therefore, a search on the imprecise SS-
MAP generally returns multiple hits or a set of scattered point clusters. Consequently, an ef cient
search algorithm that works with imperfect signal strength map is highly desirable.
2.2.3 Similar Indoor Localization Systems
The RADAR system [2, 61], the closest to ARIADNE, proposes an indoor radio propagation
model for localization and tracking. Although the system requires extensive measurements and cal-
ibration, the achieved localization performance is not satisfactory. The RADAR radio propagation
model does not fully capture the multipath phenomenon as it only considers radio propagation along
the direct transmission path.
Similarly, Hatami et al. [14] used ray tracing software to generate a reference signal strength
map SS-MAP. The proposed system uses ve APs deployed in a building of 65 ? 48 meter. To
locate a mobile user, two different localization method (LMSE and prioritized maximum power)
21
are evaluated and compared. The results show that the LMSE method provides better estimation
performance for users within the building. However, prioritized maximum power is less susceptible
to reference grid resolution and can achieve better estimates when mobile user resides within the
vicinity area outside of the building. The results from Hatami (Figure 3 in [14]) show a relation of 10
meters complementary cumulative positioning error with 54% probability for prioritized maximum
power method. The research by Hatami [14] mainly focused on localization algorithms targeted at
intruder detection. It uses ray tracing software to construct signal strength map SS-MAP without
introducing the indoor radio propagation model.
Existing indoor localization systems failed to systematically consider the two modules, and
thus when constructing signal strength map table, they either require tedious measurements or have
to rely on special hardware. If the indoor radio propagation model is to be considered, they only
consider the attenuation along the direct transmission path. Therefore, the research on the radio
signal strength module is still a dif cult topic. On the other hand, the search module in existing
systems assumes that the precise and high resolution signal strength map table is available. And the
search is based on the least mean square (LMS) algorithms.
Different from these systems, this dissertation introduces ARIADNE, a new indoor localization
system. It holistically analyzes the indoor localization system by systematically considering two
modules: map generation module and search module. In the map generation module, a new indoor
radio propagation model is proposed; and the search module presents a clustering-based localization
algorithm that works on imprecise radio propagation map tables. The ARIANDE system has been
evaluated in two buildings under various sniffers deployment strategies.
22
Table 2.1: Number of sniffers used in previous research
Researchers and Systems Number of Sniffers Covered area (m?m)
Bahl and Padmanabhan RADAR(basic) [2] 3 43:50?22:50
Bahl and Padmanabhan RADAR (enhanced) [61] 5 42:96?21:84
Hatami and Pahlavan Intruder detection [14] 5 65?48
Agiwal et al. LOCATOR [64] 3 45:11?32
5 68:58?43:90
Krishnan et al. LEASE [7] [13] 6 76:20?53:34
Ladd et al. Localizer [65] 14 ?65?35
Haeberlen et al. Practical localization [5] 33 12,000
2.2.4 Review of Sniffers Deployment Method
During the research, it is found that the sniffers deployment is critical for the performance
of the indoor localization. Since the relation of the signal strength and the distance between the
transmitter-receiver pair is not straightforward for the indoor environment, the sniffers deployment
must rst be designed to provide maximum signal coverage for the site; secondly, the deployment
must also present best discrimination of signal strength for different locations inside the building.
In addition to the consideration of the position con guration, the available of larger number of
sniffers may also improve the precision of the location estimation. Depending on the construction
material and the partition, the effective 802.11 (b) radio range for the indoor transmission is roughly
about 40 ? 50 meters. Table 2.1 surveys the number of sniffers used in the experimental analysis
in related research, and it is shows that the test experiments generally use more sniffers to provide
redundant signal coverage for the experimental site. A large number of deployed sniffers masks or
smooths the requirement for the strategy of the sniffers deployment. However, a large number of
sniffers cause more interference and impose extra cost on hardware and maintenance. Therefore, it
is desirable to deploy just enough sniffers such that a good deployment strategy of minimal sniffers
still provides optimal localization performance.
23
For all experiments, none of the existing research addresses the intrigue of the sniffers deploy-
ment. However, most researchers deploy the sniffer around the perimeter along the test building.
And an interesting observable fact is that NONE of the above systems deploys the sniffers along
a straight line. It appears intuitively that the straight-line deployment will not provide optimal lo-
calization results. Therefore it is of particular importance to derive a theoretical foundation of the
sniffers deployment strategy such that optimal localization is achievable with known precision.
We review in the next section outdoor localization systems.
2.3 Literature Review for Outdoor Localization Systems
Research is currently quite active to provide location information for wireless ad hoc sensor
networks. An ad hoc sensor network is a self-organized and rapidly deployable network. It usually
consists of a large number of unattended sensor nodes that autonomously construct a network and
communicate with each other over multi-hop paths. The unattended nature of the system necessi-
tates a set of mechanisms to assure simple deployment while maintaining the self-organized nature.
In sensor nodes, the location information of a node is often more important than its identity.
In the following sections, we rst introduce, in Section 2.3.1, various localization algorithms,
and in 2.3.2, we introduce the research on the realistic radio range irregularity model that greatly
affects the localization performance.
2.3.1 Outdoor Localization Algorithms
To initialize the positioning process, a common approach is to have the interested node, who
wants to nd out it?s position or to nd an optimal routing path to the destination node, to rst broad-
cast the hello packets to their neighbors. Through communication, neighboring nodes measure the
24
distance between themselves. Based on the distance measurements and the proposed localization
algorithms, all nodes can estimate their relative positions with each other through distributed local-
ization algorithms. In the presence of anchor nodes with known locations, absolute positions of all
nodes can be derived accordingly.
Most of existing algorithms take advantage of mature micro-sensor technology. As introduced
in Section 2.1 at the beginning of this chapter, time of arrival (TOA) measures the travelling time
of radio signals, and time difference of arrival (TDOA) measures the time difference of the radio
signals arrived at various antennas. The two methods are the most common methods for range es-
timation, and they have been applied in many infrastructure based systems (Oshman and Davidson,
1999 [66]; Priyantha, Chakraborty and Balakrishnan, 2000 [52]) and infrastructure free sensor net-
works (Niculescu and Nath, 2001 [67]; Savvides, Han and Strivastava, 2001 [68]; Savvides, Park,
and Srivastava, 2002 [69]). Additionally, angle of arrival (AOA) has been proposed to estimate rel-
ative angles between neighbors (Niculescu and Nath, 2003 [11]). A good survey of these distance
measurement systems can be found in Hightower and Boriello (2001) [70] and Tauber (2002) [71].
Still, another method of measuring the range is through received signal strength indicator (RSSI).
RSSI does not require extra equipment and is widely supported by current transceivers. Conse-
quently, RSSI is commonly adopted by many localization systems (Premaratne, Zhang and Doguel,
2004 [31]; Ji and Zha, 2004 [9]; Bahl and Padmanabhan, 2000 [2]; Sichitiu, Ramadurai and Ped-
dabchagari, 2003 [32]).
Based on the reliance on the hardware support, localization algorithms can be classi ed into
two main categories: range-based algorithms and range-free algorithms. Range-based algorithms
rely more on hardware support by applying either one or a combination of TOA, TDOA, AOA, or
RSSI technologies. A set of representative range-based algorithms include:
25
1. Convex positioning by Doherty et al. [72];
2. Ad-hoc positioning system by Niculescu et al. [67, 11, 36];
3. N-hop multilateration or AHLoS system by Savvides et al. [73, 30, 68, 69, 8];
4. Robust Positioning by Savarese [73, 30];
5. Probabilistic approach by Ramadurai et al. [38, 32];
6. Multidimensional Scaling by Ji et al. [9, 74].
On the contrary, range-free algorithms require less or no hardware support at all (Premaratne,
Zhang and Doguel, 2004 [31]; He, Stankovic and Abdelzaher, 2003 [75]; Sichitiu, Ramadurai and
Peddabchagari, 2003 [32]; Nagpal, Shrobe and Bachrach, 2003 [34]). Three exemplary algorithms
include Nagpal et al.?s Amorphous localization algorithm [34, 35], Premaratne?s GGO algorithm,
and He et al.?s APIT algorithm.
The Amorphous localization algorithm by Nagpal et al. [34, 35] uses Kleinrock?s formula [76]
to estimate the average hop distance in a uniformly deployed network. However, Kleirock?s formula
can only be used in densely deployed networks. For more general networks, special transmitters
may be used to assist the localization procedure. For example, Premaratne et al. in [31] assumes
that anchors can transmit radio signals with multiple level transmission powers. And in [33], He et
al. uses high-powered transmitters. These two transmission methods will let anchors cover much
larger areas. Consequently, with these special transmitters, an anchor can send beacon packets
directly to normal nodes that are far away from the anchor itself. When a normal node obtains
enough information about the surrounding anchor nodes, Premaratne?s method allows the normal
node to estimate its position by grid overlaying all possible regions it may reside in. This method
is called geometric grid overlaying (GGO) in [77]. In contrast, He?s method isolates the area into
26
multiple triangular regions and use approximate a-point-in-triangulation Test (APIT) to obtain the
position estimates.
This dissertation mainly focuses on the range-based algorithms. And in the following sections,
we rst introduce the radio propagation methods, and we describe a set of existing localization
algorithms next.
Radio Propagation Mechanisms
Although some algorithms, like [72], do not explicitly describe the initialization communi-
cation method, most of them allow the anchor nodes to broadcast their position information rst.
When intermediate neighboring nodes receive the beacon message, they record the anchor?s position
information, and then rebroadcast packets to their neighbors with updated hop counts. The process
continues until all anchor nodes? position information is delivered to every node in the network.
To partially alleviate the expensive ooding, several optimization techniques are applied. Some
of them are as follows:
? Flood limit method provided in [78]: This method assumes the normal nodes can derive good
position estimation from a limited number of anchors. Consequently, when a normal node
has recorded enough anchors, it will stop forwarding further information;
? Hop-count method by [30], in this method, if a node receives multiple packets from the same
anchor node, it maintains and rebroadcasts the one with the least hop counts while ignoring
all the rest. This optimization will eventually lead to a shortest path to the anchors.
? Time stamp method by [67], in which a Time To Live (TTL) stamp is appended to each beacon
packet. Out-dated packets are dropped silently.
27
To estimate the distance to anchor nodes, several different methods have been proposed. Based
on the local neighborhood density, in [79] Kleinrock and Silvester provided a formula for the av-
erage distance between nodes. We present later this formula as Kleinrock?s formula. Based on the
information ooding, Niculescu [67] presented three methods: DV-Hop propagation method, DV-
Distance method and Euclidean method. These methods are commonly used in many localization
algorithms. For example, method Hop-Terrain by Savarese is similar to DV-Hop [67]; and method
Sum-dist by Savvides is essentially the DV-Distance method [78].
? DV-Hop or Hop-Terrain propagation method: In this method, each node only communicates
with its immediate neighbors as in distance vector routing. Starting from an anchor node,
hop by hop information propagation allows a node to determine its distance, in hops, to that
anchor.
Note that during the message propagation, each node only maintains and rebroadcasts packets
with the smallest number of hop counts. The minimum hop counts that nodes retain will
eventually be the length of the shortest path to the anchor. The distance to the anchor nodes
is determined as the product of the hop counts and the average hop distance.
The average hop distance is determined by anchor nodes dynamically. When an anchor node
receives a packet containing position information from other anchors, it determines the hop
counts and the actual distance between them, and the average hop distance is obtained by
averaging the distance with corresponding hop counts [67]. To avoid expensive ooding, a
simple method of determining the average hop distance is to use the maximum radio range
directly [30];
The advantage of the DV-Hop method is that it allows fewer anchors for the initial estimation,
and it work well in uniform networks.
28
? DV-Distance or Sum-dist propagation method: This method works similarly to DV-Hop, the
difference is that each node now measures the pair-wise distance between neighboring nodes.
The hop by hop information propagation transmits the cumulative distance instead of hop
counts.
Same as DV-Hop method, each node only selects and rebroadcasts packets with minimum
distance to the anchors. Compared with DV-Hop, this method is sensitive to the measurement
error because of the cumulative effect. However, this method is less coarse than the previous
and may still perform well in randomly deployed networks.
? Euclidean propagation method: This method is based on the local geometry of nodes around
the anchor. It assumes that the network is densely populated.
An anchor node initiates the propagation process by ooding its own position information in
a beacon packet. Upon receiving the message, intermediate nodes can estimate their distance
to the anchor and rebroadcast the message with added distance information of their own.
If node (A) receives messages from two neighbors (B and C) coming from the same anchor
(D), and if the two neighbors (B and C) are also neighbors with each other (shown in Fig-
ure 2.2), then a quadrilateral (ABDC) may be formed with the knowledge of all sides and one
diagonal. Note that node A can estimate its distance to B and C; and the diagonal is the dis-
tance from B to C, which can be determined since B and C are neighbors. The determination
of the other diagonal (AD) is trivial, and the diagonal is the distance from node A to anchor
D.
The algorithm allows all nodes to estimate their distance to the anchor node, and it works
from the inner most circle to the faraway outside like a circular-wave form centered at that
anchor.
29
Figure 2.2: Euclidean propagation model
The advantage of this method is that it obtains precise distance estimation to the anchor node
even under random deployment networks. However, it is complex and only works in high
density networks. Furthermore, the error from pair-wise distance estimation is cumulative.
? Kleinrock?s formula: Kleinrock and Silvester [79] showed that the average hop distance dhop
for a dense network depends only on local neighborhood density N:
dhop = r
1+e?N ?
Z 1
?1
e?N? (arccost?t
p1?t2)
dt
?
(2.3)
Nagpal et al. measured the average hop distance with variance N over several simulations
from a random source [34]. Results validate Kleinrock?s formula that it only slightly under-
estimates the measured average hop distance.
Nagpal further noticed that N of 15 is a critical minimal threshold for achieving low errors in
distance estimation.
30
Range-based Localization Algorithms
After anchor nodes broadcast their location message, each normal node obtains anchors? po-
sition, and the estimated distance to each of them. Based on the distance information, different
localization algorithms can be applied.
Convex Estimation Convex position algorithm models the known peer-to-peer communication
in the network as a set of geometric constraints on the node positions [72]. Radio communication
constraints are a set of geometry rules among the communicating nodes. The constraints can be
radial and angular restrictions or a combination of them that are used to bound the position estimates.
For example, if one node (A) can receive message from another node (B), then the distance between
these two nodes should be less than node B?s radio transmission range. Under these constraints, a
global convex optimization yields a feasible position estimation for all the normal nodes.
Based on connectivity and pair-wise angles between nodes, a linear program can be de ned. A
linear program (LP) is a problem of the form:
Minimize cTx; Subject to :Ax ? b (2.4)
where x is the vector of variables to be solved for, A is a matrix of known coef cients, and c and
b are vectors of known coef cients. The expression cTx is called the objective function, and the
equations Ax ? b are called the constraints. The matrix A is generally not square (usually more
columns than rows), and Ax ? b is therefore quite likely to be under-determined, leaving great
latitude in the choice of x with which to minimize cTx.
31
In two dimension system, the position is represented with pair (x,y), and a vector with all
positions for the above equations can be formed as:
x = [x1 y1 x2 y2 ::: xm ym xm+1 ym+1 ::: xn yn]T
where the rst m entries represents anchor position and the remaining n-m are to be determined.
Geometrically, the connectivity of a network can be represented as a set of convex position
constraints [72]. By utilizing the radio communication constraint models, it is possible to generate
feasible positions for all the nodes in the network.
The Convex algorithm is a centralized algorithm. Through simulation, it is found that:
? For radically constrained connections, using a variable radius instead of a xed radius im-
proves overall estimation performance;
? For angle constrained connections, the angle estimation error affects the position prediction.
If angle measurement can be combined with the distance information, the precision is im-
proved.
? Results from radial and angular methods are not comparable.
Bounding-box or Min-max Method The bounding-box de nes a possible area that a node
may reside in. There are essentially two basic methods. The rst method is a distance based
approach proposed by Savvides [8], which uses the surrounding anchors? positions and the distance
between them. The second method is a radio pattern based approach, which assumes regular circular
radio pattern and constructs the bounding-box containing the overlapping or intersection area of
neighboring nodes [72].
32
? Distance based approach: This is a general method which only assumes the knowledge of
the distance from the estimating node to the anchors. Basically, we can construct a bounding-
box for each surrounding anchor node. The possible area for the normal node is then deter-
mined as the intersection of those anchors? bounding-boxes.
For example, suppose the distance from a normal node X to an anchor node A is d, and A?s
coordinates are (xA,yA), then the bounding-box for X is:
[xA ?d;yA ?d]?[yA +d;yA +d]
If normal node X has multiple surrounding anchor nodes, then the bounding box for X is the
intersection area of all anchor nodes? bounding boxes. The intersecting box is de ned as:
[max(xi ?di);max(yi ?di)]?[min(xi +di);min(yi +di)]
where (xi, yi) is the anchor I?s position, and di is the distance between the normal node X and
the anchor I. In Figure 2.3 (a), node A and node E are anchors. Node B, C, and D are normal
nodes. The bounding area for node D is:
[xE ?d;yE ?d)]?[xA +(a+b+c);yE +d]
The nal estimated position for the normal node is set at the center of the bounding box.
? Radio pattern based approach: Instead of the distance from the estimating normal node
to the surrounding anchors, this approach requires circular radio propagation pattern. That
is, when one normal node receives a beacon packet from a neighboring anchor, it assumes
33
Figure 2.3: (a) Distance-based approach. (b) Radio pattern based approach.
it resides in the circular ring centered at that anchor. Accordingly, the bounding box for the
normal node is the overlapping radio area from the neighboring (anchor) nodes. An example
is shown in Figure 2.3 (b), which shows a rectangular box for node D (anchor nodes A, B,
and C are D?s neighbor).
Note that if the radio wave is circular, the second method is more precise.
Lateration Algorithm Lateration is a form of triangulation that uses least squares to estimate
the position from a set of linearized equations in the form of AX = b.
Specially, from the radio propagation step, each normal node gets an estimated distance (di) to
the anchor nodes with known position (xi, yi). If the normal node?s position is (x,y), then a set of
equations can be expressed as:
8
>>>
>><
>>>
>>:
(x1 ?x)2 +(y1 ?y)2 = d21
...
(xn ?x)2 +(yn ?y)2 = d2n
(2.5)
34
Subtract the last equation from the rst n-1 equations, and reordering the equations, we get
AX = b with:
A =
2
66
66
64
2(x1 ?xn) 2(y1 ?yn)
... ...
2(xn?1 ?xn) 2(yn?1 ?yn)
3
77
77
75 (2.6)
and
b =
2
66
66
64
x21 ?x2n +y21 ?y2n +d2n ?d21
...
x2n?1 ?x2n +y2n?1 ?y2n +d2n ?d2n?1
3
77
77
75 (2.7)
then X can be estimated by least-squares with result: X = (ATA)?1ATb.
The least-squares is ef cient because it minimizes possible range estimation errors accumu-
lated along the propagation path.
Probability Algorithm For an outdoor environment, received signal strength is a function of
distance: the longer distance from the transmitter, the smaller the signal strength. It is noticed in
[38] that the probability distribution of signal strength follows a normal distribution.
The probability algorithm starts with a table that records the signal strength (mean and standard
deviation) with the changing distance. In addition, it assumes the network is fully connected, and
every node in the network is present in the entire space with equal probability.
When a normal node receives a beacon packet directly from an anchor, it estimates itself to be
located on a circular surface centered at that anchor(see Figure 2.4 (a) 2). In Figure 2.4, the x axis
and y axis denote the position in meters, and z axis represents the position probability. Each point
on the circular surface represents a probability distribution at that location. A higher value means
2Adopted from [38]
35
Figure 2.4: (a) Constraint with one-hop beacon message. (b) Constraint with two-hop beacon mes-
sage. (c) Old position estimation of a normal node. (d) New estimation by intersecting the constraint
with the old estimate.
higher probability of the node?s position at that position. Upon estimation, the normal node will add
its ID as well as its estimated mean and standard deviation to a beacon packet, and rebroadcast the
packet to its neighbors.
If the beacon packet comes from other normal nodes, the location constraint for the normal
node is not necessarily Gaussian. Actually, the packet contains a cascaded information of the esti-
mated means and standard deviations of other normal nodes to the anchors. To estimate its position,
the normal node has to process the cascaded distributions by adding all individual estimates (see
Figure 2.4 (b)). The sum of these constraints is similar as the convolution of all the individual
distributions.
After processing the beacon packet, the normal node updates its position by intersecting the
new constraints with the current estimates. If the new estimates improve, it will wait for a speci c
36
period of time and advertise the new position to all neighbors. Figure 2.4 (c) and (d) shows an
example of the procedure. Figure 2.4 (c) gives the formal estimates of a normal node, and (d) shows
the improved results to be advertised.
Multidimensional Scaling Method Multidimensional scaling (MDS) is an exploratory tech-
nique used to analyze the dissimilarity of data on a set of objects. Multidimensional scaling takes
roots in two important traditions within psychology: psychophysics and psychometrics [80, 81],
and it is called as smallest space analysis initially. Now MDS has already encompassed a collec-
tion of methods for general multivariate data analysis. Some excellent textbooks about MDS are
[82, 83, 84].
Classical scaling technique is a metric multidimensional scaling technique [84], and it was
originated in the 1930s by Young and Housholder [85]. Later, Schoenberg (1935) [86] and Young
& Housholder (1938) provided the method for nding the original Euclidean coordinates from the
Euclidean distances. In [9], the authors used classical multidimensional scaling algorithm in wire-
less ad hoc sensor networks for estimating the nodes? positions.
The MDS in [9] let anchors initiate the estimation procedure by broadcasting their position
information to the whole network. Upon receiving a beacon packet, intermediate nodes will mea-
sure pair-wise distances to transmitting neighbors. If the intermediate node is an anchor, it will also
estimate the average hop distance of the network. The average hop distance is determined by divid-
ing the physical distance with the number of hop counts between the two anchors. If one routing
path contains more than three anchors, and at least three anchors are not on a same line, classical
multidimensional scaling can be used to estimate the coordinates of all normal nodes along the path.
Classical MDS works as follows [84]:
37
1) Compute the distance matrix D = [dij]n?n, where dij is the distance between node i and j,
and n is the number of nodes in the path;
2) Compute a matrix J with J = I?e?eT=n, where I is the identity matrix and e = (1;1;:::;1);
3) Double center matrix J with H =?12JD2J;
4) Eigen decomposition matrix H and let H = UVUT , then sort descending the Eigen matrix
V, and change the matrix of U accordingly.
5) Choose an appropriate number of dimensions p. The coordinates of the estimated normal
node in the p dimensional Euclidean space are given as the rst p columns (two columns for
2-D case) in U.
The position information obtained through the above steps is the relative position with each
other. To obtain the physical position of the nodes along the path, the estimated positions from
MDS will, generally, be rotated and/or mirrored according to the reference anchor nodes along the
path. Figure 2.5 shows an example.
Figure 2.5 gives a routing path containing six nodes in 2-Dimensional space, and the x-axis and
y-axis denote the coordinates in x and y direction respectively. The ?+? presents the true positions;
?o? denotes direct estimates through MDS; and ?*? represents the rotated positions from estimates,
which will further shift to the true position.
In summary of the related research for outdoor localization systems, most existing localization
algorithms present good simulation results in their research, however, it is dif cult to appreciate
their performance because almost all algorithms require particular simulation environments (i.e.
at, open space), network conditions (i.e. anchor ratio, node density, static networks), and certain
radio properties (i.e. bidirectional link, circular radio). Therefore, it is necessary to compare and
38
?5 0 5 10 15 20 25 30?5
0
5
10
15
20
25
True position
MDS predicton directly
Rotated prediction
Figure 2.5: MDS localization example
identify the strength of each algorithm under the same network environment. Moreover, to our
best knowledge, there exists no theoretical analysis on the estimation precision bounds for most
localization algorithms. Thus it is very dif cult to make critical decision if only the best estimation
performance is available. Additionally, to identify or to develop an ef cient localization algorithm
that works on the most general environment with known precision is highly desirable.
2.3.2 Radio Range Irregularity
In recent years, localization research on wireless sensor networks has become very active. The
research community usually exploits simple radio propagation models in simulations to investigate
and evaluate a variety of localization algorithms and protocols. This simple model assumes spher-
ical radio transmission pattern of xed range at all wireless nodes [11, 16, 38]. However, results
in the eld widely differ from simulation results. The research community has become aware that
39
simplistic models may lead to awed protocols. A key reason is that radio propagation is irregular
[39, 33]. Pawlikovski et al. [40] surveyed 2200 published network simulation results and concluded
that the simple model is adopted by most researchers and simulators. From experiments, Paw-
likowski showed that the ideal radio model yields results radically different from reality. Kotz et
al. [41] reviewed six of the most used simplistic assumptions and showed their individual impact
on the obtained results. Thus, the credibility of applications/protocols based on simplistic models is
dubious.
However, research on realistic models for the radio range irregularity is still in infancy, and
most researchers mainly focus on these studies: a) To provide more evidence to further quantify this
irregular phenomena [41, 87]; b) To clarify and demonstrate the weakness of the use of the ideal
circular model in existing protocols and algorithms [40, 41]; and c) To develop other algorithms that
are less dependent on the radio shape [77];
In [33], He et al., for the rst time, provided an irregular radio model: degree of irregularity
(DOI). The model assumes an upper and lower bound on the radio propagation range. When a
neighboring node is beyond the upper bound, then it is out of the communication range; and when
it is within the lower bound, the nodes are guaranteed to be within communication range. If the
distance between the neighboring nodes is between these two boundaries, the communication is
dependent on the actual radio range in that direction. In simulation, the particular radio range in
each direction is calculated based on a random number and a pre-assigned irregularity factor. While
this is a good start for the research in this area, the DOI model does not take the environment into
account and this model usually results in undetermined and abrupt changes of range values in all
directions.
40
Zhou et al. [39] extended the DOI model by also considering the radio interference among
devices. The new model is called radio irregularity model (RIM). RIM is based on experimental
results made with a pair of MICA2 motes. RIM was developed to analyze the impact of radio range
irregularity on MAC and routing protocols.
Apart from the complexity and the un-straightforward nature of the dependent path loss model
and energy-fading pattern on the multipath environment, RIM is derived from measurements at a
lower radio frequency below 916 MHz. The conclusions from those experiments may not be equally
applicable for the IEEE 802.11b standard at 2.4 GHz.
Our preliminary measurements on various environments using IEEE 802.11 wireless Ethernet
standard indicate that the radio transmission range at 2.4 GHz UHF (ultra high frequency) band
may not smoothly vary in different directions depending on the presence of obstacles (ex. trees and
stones) in vicinity. This nd is signi cantly different from the conclusion by Zhou et al. [39].
Consequently, it is of particular importance to: 1) research a convenient radio range irregularity
model for IEEE 802.11 that is easily adjustable according to actual operating environment; 2) iden-
tify the impact of the real radio propagation on the performance of existing localization systems;
and 3) explore optimal radio propagation method that can improve the localization performance
even under the irregular radio transmission.
41
CHAPTER 3
RESEARCH DETAILS FOR INDOOR LOCALIZATION SYSTEMS
ARIADNE consists of two modules as illustrated in Figure 3.1 - namely map generation and
search - that are developed in Section 3.1 and Section 3.2, respectively. In Section 3.3, the local-
ization on the indoor mobile user is analyzed. And Section 3.4 introduces the sniffers deployment
method.
3.1 Map Generation Module
Map generation includes multiple steps: Subsection 3.1.1 develops the rst step that consists
of capturing the characteristics of the oor plan and producing a 3-D model necessary for ray trac-
ing. Subsection 3.1.2 explains how ray tracing is used for the determination of the individual ray
contribution to the signal strength on a grid of points. A propagation model is proposed in Subsec-
tion 3.1.3, and its parameters is solved in Subsection 3.1.4 and Subsection 3.1.4 using simulated
annealing.
3.1.1 Floor plan interpretation
The main purpose of the oor plan interpretation is to integrate the geometry acquisition pro-
cess as an automatic procedure. The major task of the interpretation process is to extract the struc-
tural parameters from construction CAD les or oor plan image les.
Structural information is extracted from the picture using basic image processing techniques,
in which a picture is denoted as a matrix. Each element in the matrix has a value corresponding
to the brightness of the pixel at the corresponding position, which is an integer between 0 and 255.
42
Signal strength
map generation
Signal strength map
Location
determination
M(SA,SB,SC)(LR,t)
M(SA,SB,SC)(L,Now)
Floor plan
Location (Now)
(F?PLAN) (SS?MAP)
Figure 3.1: ARIADNE system
The 0 corresponds to black and 255 to white. If the pixel value of the lines in the picture is denoted
by 0, then the grouping of a set of connected 0 value pixels, vertically or horizontally, yields a line.
The wall geometry information is constructed by extending the lines vertically in 2D image
with base coordinates and the oor height. By stacking the wall information at each oor, over-
all structural representation of the building is obtained. Similar to most previous research [88], a
wall/ oor is modelled as a single plane in the middle. The offset between refracted and incident
rays is ignored.
Figure 3.2 shows a site oor plan where ARIADNE was tested. The oor is about 150?120
ft.. Figures 3.3(a) and 3.3(b) display respectively the 2D topview and the 3D view with height
information extracted from the original plan. Geometry information of the walls and oor/ceiling is
stored in a database table for ray tracing.
43
Figure 3.2: Original oor plan
0
10
20
30
40
500 5 10 15 20 25 30 35 40
(a) 2D view
m
m
0
10
20
30
40
50
0 5 10 15 20
25 30 35 40
02
4
(b) 3D view
m
m
m
Figure 3.3: Floor plan interpretation output
44
3.1.2 Ray tracing
Ray tracing (RT) approximates the radio propagation with a nite number of isotropic rays
emitted from a transmitting antenna [89]. For an omnidirectional antenna, each ray is assumed
to transmit with the same amount of energy at the transmitter, and the energy of the rays will be
attenuated at walls or oors due to re ections and transmissions. Ray tracing technique is widely
used to simulate the radio propagation in indoor environment [90, 91, 88].
Ray imaging techniques are used to record each ray from the transmitter to the receiver. In the
ray imaging technique, the transmitter is assumed to be re ected at each surface around it to produce
image transmitters, the re ected rays to the receiver from the real transmitter are considered as direct
paths from the mirror images of the true transmitter. Based on geometrical optics (GO), each ray
from the transmitter to the receiver can be exactly determined. The detailed ray technique is omitted
here for lack of space (a good reference can be found in [90, 92, 93]), but instead, several key points
of ARIADNE are emphasized.
? Similar as the research by Hassan-Ali and Pahlavan in [58] and Bertoni et al. in [94], the
diffraction and scattering effect are neglected in the proposed propagation model because of
the minor contribution of the radio in this band;
? Only rays with power above a xed threshold [95] are considered because highly attenuated
rays do not reach the receiver in reality even though a transmission path exists in theory.
? Similar to [58], the multipath power at receiver is determined as the sum of all individual
powers regardless of the phase of each path.
Figure 3.4 depicts a simple scenario where three rays are shown from the transmitter T to the
receiver R. Each ray ri is composed by multiple segments where distance of the jth segment is dij.
45
T
Rr3 r1
r2
d3,1
d3,2 d3,3
d2,1 d2,2
d1,1
Figure 3.4: Radio propagation with ray tracing
Direct path (ray r1) is denoted by a solid line. The other two paths (ray r2 and r3) are indirect and
contain re ections. The faint dashed line (ray r2) has one re ection and dotted line (ray r3) has two
re ections, respectively. The distances traversed by each ray is also depicted in the gure.
3.1.3 Radio propagation model
As explained in Section 3.1.2, the signal power at the receiver is the accumulated multipath
power from all individual rays from the same transmitter. For each ray, the attenuation path loss
includes three components:
1. The distance-dependent path loss, which is assumed as free space propagation loss;
2. The attenuation due to re ections, which is the product of the re ection coef cient and the
total number of re ections from transmitter to the receiver;
3. The attenuation due to transmission, which is the product of the transmission coef cient and
the total number of transmission walls.
46
Consequently, the model is de ned as:
P =
Nr;jX
i=1
(P0 ?20log10(di)? ?Ni;ref ?fi?Ni;trans) (3.1)
where P is the power (in dB) at receiver, Nr;j is the total number of rays received at the receiver
j; P0 is the power (in dB) at a distance of 1 meter; di, Ni;ref, and Ni;trans represent the total
transmission distance, the total number of re ections and the total number of (wall) transmissions
of the ith ray, respectively. is the re ection coef cient, and fi is the transmission coef cient.
In Figure 3.4, the transmission distances for three rays (r1, r2, and r3) are d1;1, d2;1 + d2;2,
and d3;1 +d3;2 +d3;3, respectively. Ray r2 has one re ection, and ray r3 has two re ections. All
three rays have two wall transmissions.When starting from transmitter T, all three rays are assumed
to hold the same amount of power. With different transmission conditions, the nal signal power
of each individual ray observed at the receiver R are different. And the overall signal power at the
receiver R is the sum of the powers from all received rays.
The site speci c parameters (Nray, di, Ni;ref, and Ni;trans) in Equation 3.1 can be obtained
directly from ray tracing as described in the Section 3.1.2. The other three parameters (P0, , and
fi), in other similar research, are usually derived from tedious measurements. ARIADNE does not
require extensive on site measurements. Instead, simulated annealing (SA) technique is used to
determine optimal values for the three parameters of the proposed model. ONE reference measure-
ment only is required.
3.1.4 Parameters Estimation
To estimate the radio propagation parameters (reference power of the ray P0, re ection co-
ef cient , and transmission coef cient fi), some measurements at reference positions inside the
47
building are needed. If a maximum of n reference measurements are available, a linear system of
Ax = b (derived from equation 3.1) can be used to determine the three unknowns x = [P0 fi]T .
To solve the linear equations, the method of least squares could be used. However, it is dif-
cult. As stated earlier, only rays with power above certain threshold are considered in the radio
propagation model. Or in other words, from ray tracing simulation, a maximum number of N rays
may exist, theoretically, from the transmitter to the receiver. In reality, only n(n < N) rays are ac-
tually received because of the different attenuation along each individual path. Since some rays are
too weak to contribute the energy at receiver, they must be eliminated from the linear system. Such
an elimination process is very dif cult at this stage because of the lack of the energy information
(again, the Chicken and Egg Dilemma). In this research, we use simulated annealing algorithm to
search the optimal value of x = [P0; ; fi]T .
Simulated Annealing Search Algorithm
Simulated Annealing (SA) [96, 97] is a method used to search for a minimum in a general
system. It is based on the process of the way a metal cools down to the optimal state (the annealing
process). SA?s major advantage is an ability of a random search which not only accepts changes that
decrease objective function, but also some changes that increase it. Thus, SA method can achieve
global optimization without getting trapped at a local minima [98].
The original Metropolis scheme [96] indicates that an initial state of a thermodynamic sys-
tem is chosen at energy E and a desired temperature T. Holding at that temperature T, the initial
con guration is perturbed and the change in energy dE is computed. Applying Monte Carlo sam-
pling techniques, the physical annealing process is modelled successfully by computer simulation
48
methods. A convenient formula can be borrowed from thermodynamics:
dP(E) = exp(? E
kT) (3.2)
which expresses the annealing probability dP(E) of a change on energy E at temperature T, where
k is Boltzmann?s constant.
Given initial values of x = [P0 fi]T at a temperature T, the power of each individual ray can
be computed (Equation 3.1). (The initial values can be any positive numbers, however, better values
will minimize the search time. Generally, better values can be derived from literature.) Neglecting
those rays with power below the threshold, and summing the powers of all others, yield the multipath
power at the receiver. The least minimum squared error (Equation 2.2) allows the comparison of the
power estimates tness with the measurements, and henceforth the adjustment of the parameters of
x accordingly.
To adjust the parameters, a random movement is generated by adding a deviate from the
Cauchy distribution to each parameter of x = [P0 fi]T :
xi+1 = xi +T ?tan(bP); i = 1;2;3 (3.3)
The cooling schedule for the temperature T can use a simple method similar to [97]:
Ti+1 = a?Ti; a 2(0;1) (3.4)
Consequently, the Simulated annealing search algorithm can be detailed below:
1) De ne initial values for x = [P0 fi]T .
49
2) De ne the temperature, Tmax for highest temperature and Tmin for the cooling down value;
3) Calculate the annealing probability from Equation 3.2;
4) Update the displacement for the parameters using Equation 3.3;
5) Calculate the tness between the estimates and the measurements using equation 2.2: if a
better agreement is obtained, keep the displacement from the above step; else, keep the dis-
placement with certain probability;
6) Update the temperature T by equation 3.4, and repeat steps 3, 4, and 5 until T < Tmin or
speci ed minimum errors is achieved.
Simulated annealing method can effectively estimate parameter tride x = [P0 fi]T with only
ONE reference measurement.
3.2 Search module: Clustering-based Search Algorithm
To locate a mobile user, the current user?s signal strength measurement triplet is searched from
the signal strength map SS-MAP for a match. Currently, most search algorithms are based on the
LMSE and select a single location as the estimate. This method works if a detailed and precise
SS-MAP for the building is available. As indicated in many papers, the signal strength is observed
to be very dynamic at different measurement times, and to collect a ne-grid signal strength map
is time-consuming for large scale building deployments. Consequently, the LMSE method will not
generate optimal estimates in most circumstances. Therefore, it is dif cult to make a decision if this
method is to be used exclusively.
ARIADNE proposes a clustering-based search algorithm for the indoor localization of a mobile
user based on the following ndings:
50
? ARIADNE constructs ne-grid signal strength map SS-MAP based on the radio propagation
model and the site-speci c geometry of the building;
? The SS-MAP from the propagation model provides real-time estimates without further human
intervention. However, it is only a close t to the measurements, or in other words, it is
imprecise and small estimation errors are expected for some locations;
? Consequently, LMSE may result multiple possible locations in the SS-MAP table, or the
unique location corresponding to the LMSE is not necessarily the right position;
? If a set of positions (corresponding to low mean square error with respect to a predetermined
threshold) is selected, the positions can be grouped into several clusters. The largest cluster
will generally have higher probability to contain the true position for the mobile user.
? The location estimates with the clustering-based search method may provide larger errors
for some positions, however, the overall estimation error gets lowered and the con dence is
improved.
The clustering-based search algorithm is a two-phase search algorithm. The rst phase is
named as data collection and cluster preparation phase, and it is introduced in Subsection 3.2.1,
where a set of candidate locations with lower mean square error within the threshold are selected
and preprocessed with the purpose to neglect isolated locations from the set. The second phase is
clustering phase, and it is presented in Subsection 3.2.2, where the remaining candidate locations
are grouped into several clusters and the center of the largest cluster is chosen as the nal estimate.
51
3.2.1 Data Collection and Cluster Preparation Phase
In this phase, the current signal strength measurement triplet M(SA;SB;SC)(L;Now) of
mobile M at some location L is compared with all records from the estimated SS-MAP. In stead
of selecting only a single location for estimation, ARIADNE select a set of candidate locations
according to a predetermined mean square error (MSE) threshold.
Because of the imprecise nature of the estimated SS-MAP, some of the selected candidate
locations may be scattered around the oor plan. In order to prepare the candidate locations for
clustering, the scattered or isolated (unlikely) location points must be detected and omitted from
the set of candidate locations. The isolated position is characterized by a larger distance from its
location to all other candidate locations. For example, if there are total N candidate locations in
a selected location set, let xi and xj be two location clusters with m and n candidate locations,
respectively, m;n 2 [1;N], and m+n ? N; and let di;j be the minimum pairwise distance from
any member instances of these two clusters.
di;j = min(dist(xi;r;xj;t)) (3.5)
where r and t represent the position instance in cluster xi and xj, respectively; 1 ? r ? m, and
1 ? t ? n. If the candidate location cluster xi has larger distance di;j to every other clusters, it
means that cluster xi is an isolated cluster. If further this cluster contains much smaller populations,
it may be omitted from the candidate location set.
Figure 3.5 shows an example of a set of positions in space. In the gure, position 8 is isolated
from all others; positions 5 and 7 are close to each other and they may be treated as one group which
is again separated from others. Figure 3.6 gives the distance information between (group) positions
52
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
0
0.1
0.2
0.3
0.4
0.5
8
x
4
2
3
1
6
7
5
y
z
Figure 3.5: Position isolation example
for the data set in Figure 3.5. If positions of f1,2,3,4,6g are grouped into one cluster, and positions
f5,7g form a second cluster, then the minimum distance between these two clusters is 0.3340. If
positions of f1 ? 7g are to be grouped into a bigger cluster, and the position 8 is another group,
then the minimum distance between them is 0.8311. For the data set in the example, positions of
f5,7, and 8g may be neglected during this preparation phase.
3.2.2 Clustering Phase
After the cluster preparation phase, most of the remaining positions have neighbors close to
them. Consequently, the main purpose of the clustering phase is to determine the intrinsic grouping
of the set for these positions, and to select the right cluster for the estimates.
To group the set of points in space, two common methods are available. The rst one is an
hierarchical clustering method, and the second one is K-clustering method.
53
1 2 6 3 4 5 7 8
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
positions
distance
0.8311
0.3340
0.1871
0.2171
0.1644
0.1178
0.0865
Figure 3.6: Distance between objects
? The hierarchical clustering method [99] produces a hierarchy tree structure of the original
data set. The leaves are individual elements and internal nodes are sub-clusters. Each level of
the tree represents a partition of the original data set of several sub-clusters. Figure 3.6 is an
example of the hierarchical clustering method.
? K-clustering method searches the best k cluster centroids, and partition the data set by assign-
ing each point to its nearest centroid. K-means clustering [100] is one of the most common
K-clustering algorithm.
The clustering procedure is more observable if hierarchical structure of the original data set is ob-
tained (Figure 3.6). If a minimum of three neighbors are selected (f1,2,6g), it translates to the
closeness elimination scheme addressed by Prasithsangaree in [62]. And if only two neighbors are
chosen (f1,2g), it is the two closest neighboring scheme by Pandey [63]. However it is dif cult
to determine the exact number of neighboring positions that should be selected in order to obtain
54
an optimal estimation. Hence, the idea of clustering is extended to incorporate larger number of
estimates available by ray tracing. The K-means clustering algorithm is an unsupervised learning
method. It starts with randomly selected cluster centers, and the nal clustering performance is
sensitive to them. Similarly, it is dif cult to decide the optimal number of clusters for any given
data set.
Unfortunately, there are no general theoretical solutions for these dif culties. This study
heuristically explores these problems through simulations. It is found that the strict selection of
xed number of neighboring positions using hierarchical clustering algorithm does not yield satis-
fying results in most cases. On the contrary, after neglecting the isolated positions in the preparation
phase, the k-means algorithm generally yields better estimates.
To determine the actual number of clusters, we select one that provides better separation of the
original data as de ned in Equation 3.6.
Dc = min(
NX
i=1
MX
j=1
(xj;i ?xi;ctr)2)1=2) (3.6)
where Dc is the total distance of all locations to the respective cluster centers, a small value rep-
resents better separation for the determined number of cluster. N is the predetermined number of
clusters; M is the maximum number of position points in ith cluster; xj;i denotes the coordinates of
jth position in ith cluster; and xi;ctr is the center coordinates of ith cluster.
The sensitivity of the selection to initial cluster centers is minimized by running the clustering
algorithm multiple times and an averaging result is used.
55
3.3 Mobility Analysis
To monitor a mobile user, a common method is to maintain and analyze a sliding window
with a series of samples of signal strength from the mobile user within a time period. At each
signal strength record, the stationary localization method is used individually. Then all location
information is connected to give the user?s position on a continuous basis.
ARIADNE exploits a similar idea as Abhijit, Ellis, and Fan [101] to track a mobile user in
the building. The method is based on the fact that a mobile user does not move arbitrarily within
the building. Instead, there is correlation between the current position with the previous location,
for example, the distance between two continuous locations can not exceed certain limit. In this
clustering-based search algorithm, the largest cluster is selected to denote the possible location of a
stationary user. If the clustering history is used, the decision criteria may additionally be restricted
with the history information. This may produce better estimates in reality. An example scenario is
shown in Figure 3.7.
In Figure 3.7, the mobile user?s previous location is denoted by P1. Two candidate current
positions are denoted by P2 and P3. If (stationary) clustering-based search algorithm is to be used,
the location of P3 should be selected because of the larger population in the clustering group. How-
ever, the distance between P1 and P3 is beyond the reasonable limit for the mobile user inside the
building within the sampling time period. Consequently, the center at P2 is chosen as the current
location of the mobile user.
One shortcoming for this method is that it requires additional memory to maintain a history
record. Moreover, the position estimation performance relies on the correctness of the history
56
0
5
10
15 0
5
10
15
20
0
5
10
15
20
yx
z
P2
P3
P1
Figure 3.7: Decision making in tracking mobile user
record. If the initial estimation is not prefect, the subsequent position estimation tends to gen-
erate unacceptable results. Consequently, a mechanism to automatically reiterate the localization
algorithm is required.
In this research, two principles are used to restart the localization algorithm:
1. If the history constraint results in a cluster with signi cant smaller populations according to
a predetermined threshold;
2. If the history constraint results in a position on the other side of a partition;
3.4 Sniffers Deployment Analysis
This section addresses the impact of sniffers con guration on the performance of the indoor
localization. The interest is in the following problems: i) how to optimally deploy the sniffers in
57
order to achieve the best precision in location estimation? and ii) for a given deployment, what is
the highest achievable precision bound for the estimation?
This dissertation makes the following assumptions:
1. It does not consider the radio attenuation effect from partitions or obstacles like walls, and
furniture;
2. It does not consider the effect of the radio coverage on the performance of the indoor local-
ization, or it assumes that any mobile users at the interested locations are always effectively
sensed by at least three sniffers;
3. The received signal strength SS for a given location at a sniffer is given:
SS 2[SStrue ?(1??);SStrue ?(1+?)] (3.7)
where SStrue is the true signal strength value (theoretical value) at that location, and ? is
the maximum perturbation of the estimated signal strength from the indoor radio propagation
model.
4. It assumes that the received signal strength SStrue uniquely maps to the range rtrue from the
transmitter at the position to the sniffer, i.e., SS = f(r). Let the ?r be the uncertainty of the
radio range corresponding to the perturbation of the signal strength ?, then the range r is with
the range:
r 2[rtrue ?(1??r);rtrue ?(1+?r)] (3.8)
If r1;r2,and r3 are radii from an interested position P to three sniffers, then the location of
the position P is within the overlapping area of three rings (Please, see Figure 3.11).
58
0 5 10 15 20 25 30 35 40 450
5
10
15
20
25
30
35
175
185
190
190
185
195
175
195
180
200
190
185
205
200
190
185
195
195
215
185
210
200
190
190
205
205
210
200
220
195
215
215
195190
185
210
200
195
190
210
200
205
205
185
x (m)
y (m)
Sniffer
Figure 3.8: Signal strength vs. range for indoor radio propagation
Note that the radio range for the indoor radio propagation is not circular due to the attenuation
from the partitions, and a typical indoor radio transmission is given in Figure 3.8. The gure
shows the oor plan and the received signal strength at a sniffer at difference locations, the
x- and y-axis denote the dimensions for the oor in two directions, and the circular lines
are positions with particular signal strengths where the numbers on the lines are the signal
strength readings. However, by simplify the site speci c attenuation effects, it is potential
to understand the essential relationship between the uncertainty of the localization and the
sniffers deployment strategy.
Therefore, the problem of the sniffers deployment can further be expressed as the following
two statements of problems:
1. Problem a: For a given interested position P, how can we optimally deploy the three sniffers
with radii of r1;r2;r3, such that the coordinates of the given position P could be determined
with minimal uncertainty?
59
2. Problem b: For a oor space with three deployed sniffers, if we do not consider the effect
of the partitions and obstacles, what is the average uncertainty (in meters) of the position
estimation for the oor?
We consider these two problems in Section 3.4.3, and we will further analyze the problem b
in Section 5.2.1 at Chapter 5. For both problems, we rst build a relative coordinate system. In this
system, one of the sniffers xes its position at origin, and by changing the relative positions of the
other two sniffers, we analyze the impact of the sniffers deployment on the localization performance.
We introduce this coordinate system in Section 3.4.1.
3.4.1 De nition and Coordinates
This section de nes the terms that are necessary for the research.
[De nition 1] Uncertainty Area: For a position P covered by three or more sniffers Si; (i =
1;2;:::;n), the uncertainty area for the position P is de ned as the common overlapping area of
multiple rings RSi; (i = 1;2;:::;n) that centered at those sniffers. Suppose a ring surface RSi is
composed by a point set fqRS;ig, then the uncertainty area of the position P is given:
Sua;P =fqRS;1g\fqRS;2g\:::\fqRS;ng (3.9)
Figure 3.9 illustrates the scenario of the deployment for three sniffers of O1;O2;O3 and an
interested position P. If there is no measurement error, the ideal radio range of the three sniffers are
r1;r2;r3, respectively; and consequently the position at the intersection of the three circles is the
location P. Considering the measurement errors, and assume the range perturbations of the three
sniffers are ?i;(i = 1;2;3). Thus the possible sensing area at each sniffer would be a surface of
a circular belt (or a ring surface between radii ri ?(1??i); (i = 1;2;3)), therefore, the probable
60
O1 O2 O1
O3
O2
O3
P
A
B
C
D E
F
d3 d
3 d2
d2
d1
d1
r3
r2r
1
(a) (b)
P
Figure 3.9: Uncertainty area of the indoor location estimation
O1 O2
O3
O1 O2
O3
a = 30o a = 150o
a a
Figure 3.10: Uncertainty area of two different sniffers deployment
location for the position P would be an area, instead of a point, that are formed by the overlapping
of the three rings.
Figure 3.9 (a) is the overall con guration of three sniffers. The interested area within the dotted
rectangle in gure (a) is magni ed and the details are presented in the gure (b), where the possible
location of the position P is given by the surface ABCDEFA.
Figure 3.10 further shows the uncertainty areas for the same position P at two deployment
strategies. It shows that different sniffers deployment methods do affect the uncertainty area of the
61
O1 O2
O3
P
H
a
r1
r2
r3
x
y
r
Figure 3.11: Sniffer con guration de nition
location estimation. And it is obvious that smaller uncertainty area gives more con dence for the
location estimation.
[De nition 2] Deployment Coordinate System for the space: assume three sniffers O1;O2;O3
are deployed on a oor, and the radio ranges from three sniffers to an interested position P are
r1;r2;r3, respectively; and the maximum range perturbation of them is ?r. As indicated in Fig-
ure 3.11, we let the sniffer O1 x its position at the origin, and we randomly select another sniffer
O2 to be on the right side of the x-axis. The y-axis is de ned such that the third sniffer O3 is with
positive coordinate in y direction for the coordination system.
As shown in Figure 3.11, we denote the angle formed by the line of O3O1 and the x-axis fi
and the distance from the sniffer O3 to the origin ?. Therefore, the relative position between the
62
third sniffer O3 and the rest two sniffers can be uniquely determined by the combination of fi and
?. Additionally, the distance from the position P to the x-axis is denoted as H.
[De nition 3] Average Uncertainty Distance dAUD is de ned as the average distance of all
points in the point set of the uncertainty area.
Suppose an uncertainty area SUA contains total n points in the set (Please, see De nition 1 and
Equation 3.9), and dij is the distance between two points i and j, (i;j 2[1;n]; i 6= j), then:
dAUD = averagefdijg (3.10)
[De nition 4] Maximum Uncertainty Distance dMUD is the maximum distance of all points
in the uncertainty area. Follow the above De nition 3, the Maximum Uncertainty Distance is given
as:
dMUD = maxfdijg (3.11)
In the following sections, we rst introduce the method to calculate the Uncertainty Area for the
overlapping rings in Section 3.4.2; then we present the sniffers deployment strategy in section 3.4.3.
3.4.2 Method to Calculate the Overlapping Area for Multiple Circles/Rings
To mathematically formulate the overlapping area of multiple intersecting circles/rings as
shown in Figure 3.11 is very complex because the common surface depends on the relative con-
gurations of the rings. In this dissertation, in stead of presenting a theoretical formula for the
problem, we introduce a straightforward method that can be used to numerically nd the area of
intersection of a number of circles/Rings on a plane.
63
Figure 3.12: Area calculation method
Consider a single circle with the minimal bounding square as shown in Figure 3.12, suppose
the radius of the ring is r, then the area of the circle is ??r2, and the area of the square is 4?r2. If
we slice the space of the square into a grid of positions with ? apart in both the x and y directions.
When the grid resolution becomes smaller, i.e. ? !0, and if one is going to count the total number
of points on grid coordinates within the circle (?(circle)) and within the square (?(square)), the
ratio of them would be approached closer to the ratio of the area of the circle and the bounding
square. Or in other words:
lim
??>0
?(circle)
?(square) =
??r2
4?r2 =
?
4 (3.12)
Similarly, to determine the intersection area of multiple circles on a plane, we developed the
following procedures:
1. Select one circle (assume its radius is r), and slice the bounding square into a collection of
grid positions at ? apart from both x and y directions; and we assume the total number of
points within the square is N;
64
2. Counting the total number of points n that are also within all other circles;
3. The intersection area of all circles is given by 4?r2?nN .
The determination of intersection area of multiple rings/annuluses is similar as the above pro-
cedures except that the n represents the total number of points on the common surface for all rings
(Please, see Figure 3.9).
3.4.3 Optimal Sniffers Deployment Method
This section analyzes the uncertainty area of interested locations under various sniffers de-
ployment methods. The interest is to nd reasonable solutions for the two problems de ned at the
beginning of the Section 3.4, and they are addressed in next two sections.
The Impact of Sniffers Deployment on An Interested position
This section tries to solve the rst problem Problem a, i.e., for an interested position, how to
deploy three sniffers such that the estimation uncertainty for this position is minimal. We proceed as
follows: following the de nition in Figure 3.11, we systematically change the relative position (by
H) between the interested position P and two of the sniffers O1,O2, then at any instance of these
position con guration, we update the third sniffer O3 (by fi), and calculate the uncertainty area for
the position P. The sniffers con guration that generates the minimal uncertainty area is the optimal
deployment method.
The experiment is carried as follows:
1. Randomly deploy three sniffers with range of r1;r2;r3, and assume a perturbation ? for all
the range. The uncertainty area for each sniffer is a ring, which is de ned as the part of the
circle?s space between radii of ri ?(1+?) and ri ?(1??), i = 1;2;3;
65
0 30
60 90
120 150
180
0.2
0.4
0.6
0.8
1
0
0.5
1
a (degree)
H
Uncertainty area
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Figure 3.13: Uncertainty area at various con gurations
2. The ring with the smallest radius is selected as the rst sniffer O1, and the radius of the rst
sniffer r1 is normalized as unit length of 1, i.e., r1 = 1;
3. The second sniffer O2 moves along the right side of the x-axis, such that the distance H from
the point P to the x-axis changes between [0;1];
4. At any con guration of sniffer O1 and O2 for a given distance H, the third sniffer O3 ro-
tates its position around the interested point P. In the experiment, we let the angle fi change
between [0;180].
The normalized uncertainty area for the position P for all con gurations are computed and the
typical results are given in Figure 3.13. In the gure, the x-axis denotes the angle from 0o to 180o,
the y-axis represents the distance of from the point P to x-axis, and the z-axis gives the normalized
uncertainty areas.
Figure 3.14 further illustrates the changes of the uncertainty area (in shaded surface) for a set
of similar con gurations. In this example, the positions of sniffers O1;O2 and the position P are
66
a = 0o a = 30o a = 60o
a = 90o a = 120o a = 150o a = 180o
Figure 3.14: Uncertainty area of one con guration at various angles fi
relatively xed with each other, and the third sniffer O3 rotates around the position P from 0o to
180o. The range perturbation ? for the experiment is 10%.
The gures indicate three major results:
1. when the sniffer 2 O2 moves closer to the sniffer 1 O1 (H goes from 0 to 1), the uncertainty
area for the position P is less affected by the deployment of the third sniffer. Or in other
words, the uncertainty area remains relative stable when H = 0:5 ? 0:9 and fi = 30o ?
150o;
2. For all con gurations of sniffer 1 O1 and 2 O2, the deployment of sniffer 3 O3 at the closer
position to the x-axis gives the largest uncertainty area; or in other words, the linear (or close
to linear) deployment of the three sniffers generates the worst localization performance.
67
3. When the distance between sniffer 1 (O1) and sniffer 2 (O2) are larger (i.e., H? > 0),
the deployment of sniffer O3 at a position of fi ? 60o gives the minimal uncertainty area.
However, when the rst two sniffers (O1 and O2) get closer (i.e., H? > 1), the angle of
fi ?30;and120o ?150o give the better estimation.
Therefore, in order to optimally deploy sniffers for the given positions, the sniffers should
not be aligned, instead, they should be separated from each others in a triangular style. In reality,
in order to minimize the cost of the system deployment (hardware and maintenance), the distance
between deployed sniffers are kept larger so as to provide largest signal coverage. From the above
simulation in this section, it appears that the deployment of the third sniffer at the angle fi ? 60o
is of the most important. Considering similarity of the three sniffers and the positions in space, it
is tempting to conclude that the deployment of three sniffers at equilateral triangle is the best. We
will further address this problem in next section.
Sniffers Deployment Method on Given Floor
This section analyzes the sniffers deployment strategy for a given oor plan. We deploy three
sniffer in various triangle styles from the right triangle, general acute triangles, and to the special
equilateral triangle. At each single deployment, we calculate the overall average/maximum uncer-
tainty distance for all points within and outside of the triangle formed by the three sniffers. For the
analysis in this section, we assume the range perturbation is 10%.
Figure 3.15 shows a scenario when three sniffers are deployed in a square space of 40?40 m2.
For both charts in the gure, the x-axis and y-axis represent the dimension of the space, and the z-
axis in the left chart is the average uncertainty distance at each particular grid position on the
space. The right chart is a contour representation of the left chart, and the number is the uncertainty
68
?15?10
?5 0
5 10
15 20
25 ?15
?10
?5
0
5
10
15
20
25
02
46
8
y(m)
x(m)
Average uncertainty distance
?15
?10
?5
0
5
10
15
20
25
?15
?10
?5
0
5
10
15
20
25
7654
3
6
5
6
4
2
3
3
7
5
6
2
4
2
1
1
1
6
11
7
5
1
4
1
3
1
2
3
2
3
6
5
4
7
2
3
4
5
6
7
(a) (b)
Figure 3.15: Average uncertainty distance at all grid positions in a square area
?5 0 5 10 15?5
0
5
10
15
x (m)
y (m)
606570758085900.5
1
1.5
2
2.5
3
3.5
a (degree)
Average uncertainty distance for all positions
positions within triangle
positions outside triangle
O1 O2
O3O3
Figure 3.16: Average uncertainty distance of all grid positions within/outside the triangle
69
distance in meters. It can be seen that the positions within or close to the boundary of the triangle
(formed by the three sniffers) obtains the smallest average uncertainty distance, i.e., within or
around 1 meters in average; and the positions that are farther away from the triangle get larger
uncertainty, i.e. 2?7 meters depends on the distance to the triangle. This indicates that in order to
achieve optimal localization performance, a set of sniffers should be deployed in a way to provide
maximum coverage for the whole site. Or in other words, any particular interesting positions inside
the building should reside within a triangular surface of three neighboring sniffers.
Figure 3.16 compares 6 different sniffers deployment methods where sniffers O1;O2 xed
their locations, and the third sniffer O3 changes its location and thus the triangles formed by the
three sniffers changes from right triangle to equilateral triangle, i.e., fi = 90o ?! 60o (Please, see
the left chart). At each single deployment, we separate the grid positions for the space into two sets:
the rst set of the positions are within the triangle fPin;ig;i = 1;2;:::;n; and the second set is for
all positions outside of the triangle fPout;jg;j = 1;2;:::;N. Then for each set of positions, we
sum the average uncertainty distance at all positions and make the average distance for the set, i.e.,
DAUD;in set and DAUD;out set, respectively.
Suppose din;(i;j) and dout;(i;j) (i 6= j; i;j = 1;2;:::;n or N) are the pairwise distance of
two points in the two sets, i.e., fPing and fPoutg, respectively, then the overall average uncertainty
distance for the set is de ned as:
DAUD;in set =
P(d
in;(i;j))
n (3.13a)
DAUD;out set =
P(d
out;(i;j))
N (3.13b)
70
Figure 3.17: Ideal sniffers deployment method
The results are given in the right chart in Figure 3.16, where the x-axis is the degree fi as de ned
in Section 3.4.1, and the y-axis is the mean value of the overall average uncertainty distance for the
two point sets.
The Figure 3.15 and Figure 3.16 indicate two important results:
1. Different acute triangles of the sniffers deployment do NOT make much difference for the lo-
cation estimation of the points within the triangle, although the deployment of the equilateral
triangle (fi = 60o) does provide the best localization performance;
2. For a given space, the uncertainty of the localization for positions within & outside of the
triangle makes big difference, and the localization for positions that are outside of the triangle
is not comparable with the positions within the triangle.
Therefore, in order to optimally estimate the positions within the interested building, it is nec-
essary to include the important locations within the surface of a triangle formed by three sniffers.
For a large square oor plan, it is necessary to deploy a set of sniffers (instead of three), and the
deployment may take the mesh format as shown in Figure 3.17, where a set of sniffers are deployed
at semi-grid positions in the space, and thus most positions are within a triangle of three nearest
71
sniffers. The mesh structure (formed by ve sniffers) within the dash-dotted rectangular is the basic
construction block, and only one such block may be required for most (smaller) oor plans in order
to provide good location estimation for all positions within the building.
In Section 5.2.1 at Chapter 5, we will further address this problem and calculate the average
uncertainty distance dAV D and the maximum uncertainty distance dMUD for all available deploy-
ments at the experimental building. We will show that the average uncertainty distance dAV D gives
the theoretical location estimation upper bound. Besides the sniffers deployment, indoor localiza-
tion performance is also dependent on other site speci c parameters, like the radio coverage, the
partitions, and the indoor occupations.
72
CHAPTER 4
RESEARCH DETAILS FOR OUTDOOR LOCALIZATION SYSTEMS
This chapter introduces the methods to solve the problems addressed in Section 1.2 in Chap-
ter 1. We consider the radio communication constraints [72] to infer raw estimates of the position
of a node or the distance between nodes. And we propose two methods that are built upon two ef-
cient algorithms: lateration algorithm [30, 67] and the multidimensional scaling algorithm (MDS)
[84, 85]. We adapt these algorithms to work and yield accurate estimates even with imprecise and/or
incomplete information.
In the following sections, we present the research settings and de nitions in Section 4.1. Sec-
tion 4.2 discusses the proposed localization approach. Section 4.4 presents the precision analysis,
and Section 4.5 introduces a practical irregular radio propagation model.
4.1 De nitions and Assumptions
We consider a static ad hoc wireless network in a unit square area. We assume that all nodes
transmit radio with the same maximum range R (0 ? R ? 1), and that all nodes can measure the
distance to their directly connected neighbors. In addition, we assume the network contains a small
set of anchor nodes with prior knowledge of their positions (the others are called normal nodes). If
there are m anchors for an ad hoc network with total N nodes, the anchor density is de ned as mN .
4.1.1 Deployment Randomness
For a network,if all nodes strictly reside on crosspoints of a coordinate grid then the deploy-
ment randomness is null. Speci cally, the deployment randomness is de ned as the maximum
73
displacement x of each node that can swing from a crosspoint. Starting from a null deployment,
each node is displaced from a crosspoint over a random distance in a random direction. The unit of
the maximum displacement is the radio transmission range [102]. We associate a random number ?i
(? 2[0;1]) with each node ni. For example, if the randomness is x,then the maximum displacement
is x?R,and the displacement of node ni is ?i ?x?R. Similarly, a random number i is assigned for
the direction of the displacement.
4.1.2 Estimation Error
For a set of nodes, we denote the estimation error as the average distance between true positions
and the estimated positions. The estimation error is expressed as a fraction of the radio range. Let
Xi(i = 1;2;:::;n) be the coordinates of n normal nodes where Xi = (xi1;xi2;xi3)T . If cXi are the
estimated coordinates, then the estimation error is given by the Euclidean distance between Xi and
cXi:
err =
Pn
i=1
q
(Xi ?cXi)T(Xi ?cXi)
n?R (4.1)
4.1.3 Fitness Function
Consider a path with n nodes that measure their pair-wise distances. The measured pair-wise
distance of all nodes over this path is denoted by ? = [?i;j;i;j = 1;:::;n;i < j], where ?i;j =
(Xi ?Xj)T(Xi ?Xj). Based on these measurements, a localization algorithm provides estimates
of the positions of the nodes. If the pair-wise distance between the estimates is given by b?, with
b? = [c?i;j;i;j = 1;:::;n];i < j) and c?i;j = (cXi ? cXj)T(cXi ? cXj).
74
Figure 4.1: Radio communication scenarios
The tness function is de ned as the difference between b? and ?, and it is denoted by ,
where:
=
X
i R2). If node B2 hears node A2 only
when A2 uses its highest power with range R1, then B2 is in the circular annulus between R1 and
R2.
Angular constraint refers to the fact that when a node gets the best reception at a certain di-
rection, it can estimate the relative angle to the source transmitter, which may be a cone bounded
by a certain limit [72]. In Figure 4.1 (c), the location of node A3 can be determined with relative
angles of ac and ab. In addition, a small group of neighbors may form a set of triangles with local
geometry constraints to further re ne estimates [11]. In Figure 4.1(d), nodes A, B, C and D are
neighbors along a path from A to D. The distance between A and D is less than 3R. The distance
between A and C, as well as the distance between B and D should be less than 2R. In addition, B
resides in the radio transmission intersection area of A and C, and node C is within the intersection
area of B and D.
4.2 Augmented Multidimensional Scaling
The proposed localization method is a combination approach of the multidimensional scaling
method and the lateration method. Basically, the algorithm works as follows:
1. Using the DV-Hop or Euclidean radio propagation method, anchors start the estimation pro-
cess by broadcasting their position information to the whole network.
2. If a path P contains more than three anchors, the information collected through P is trans-
mitted back to the original anchors for localization procedure.
3. Apply IT-MDS or SA-MDS algorithm for the nodes along the paths, and update the average
hop size iteratively. (The average hop size is to be used by lateration algorithm).
76
4. Apply the lateration algorithm for the rest nodes (not on paths with three or more anchors).
5. Re ne the position estimation using the constraints from neighbors
4.2.1 Classical and iterative MDS
Classical multidimensional scaling (MDS) is a metric MDS technique in 1930s by Young and
Housholder [85]. A good reference for MDS is by Cox and Cox in [84].
To apply the MDS algorithm in the estimation of the nodes? position in a wireless network,
accurate pair-wise distance among all nodes along the transmission path is necessary. If absolute
position is required, each path must contain at least three anchor nodes in order to adjust the relative
position accordingly. However, detailed pair-wise distance is not available in most cases. In reality,
only the following information maybe achievable: 1) The anchors? positions; 2) 1-hop pair-wise
distance; 3) Estimated average hop size; and 4) Hop counts between pairs.
Therefore, iterative approach is proposed to help the location estimation under general localiza-
tion system with incomplete information. With limited pair-wise distance information, we modify
the tness function (equation 4.2) accordingly. Speci cally, we assume the pair-wise distance
matrix ? and b? include only the 1-hop pair-wise distance between nodes along the path, where
? represents the measured 1-hop pair-wise distance and b? denotes the estimates for each iteration.
The reason is that the measured 1-hop pairwise distance is generally more precise than the estimated
n-hop (n > 1) pair-wise distance.
Based on the neighborhood radio communication constraints and the accurate anchors? position
information, the algorithm is able to adjust the pair-wise distance iteratively. At each iteration round,
if the tness function for the estimation is less than the previous step, then the present position
77
estimation is kept for the next loop until speci c requirement is ful lled. Therefore, the main
procedure can be described as follows:
while ( > ?) f
Run MDS algorithm
Communication constraints check
Update the anchors? position
Update the distance among anchors
Compute fitness function
}
The communication constraints check is used to bound the position updates at each MDS
procedure within the iteration loop. Based on the imprecise n, (n > 1) hop pair-wise distance from
hop count, MDS algorithm is likely to yield unrealistic position estimates, therefore, it is necessary
to bound or reposition those estimates using the neighborhood radio communications.
In [9], X. Ji et al. proposed a similar iterative method in their research. The detailed approach
of the two iterative algorithms is different. Specially, the two methods differ as follows: 1) Estima-
tion coverage: For a general network without special deployment, MDS based algorithm does not
provide full coverage estimation for all nodes in the network. We further detail this issue in sec-
tion 4.3 in this chapter; 2) Constraints: We specially consider the radio communication constraints
during each iteration loop; 3) Fitness function: We use adapted tness function without consider-
ing all pair-wise distance; 4) Mechanism: Our localization procedure does not require local maps
to be constructed at all individual normal nodes; 5) Performance: X. Ji?s iterative algorithm doesn?t
always provide optimal estimates.
78
The IT-MDS algorithm works well when the reference anchor nodes are not aligned. In the
implementation, these methods may be used: i) if there are more than three anchors in the path, we
can select the third reference anchor with the longest distance to the line formed by the starting and
the ending nodes; iii) if one node resides on multiple routes and gets estimates more than once, the
nal position estimation for that node is given as the average of all predictions.
4.2.2 Simulated Annealing MDS Algorithm
Simulated Annealing (SA) [96] is an ef cient search method (please, see Section 3.1.4 in
Chapter 3 for details). To combine the SA with MDS algorithm for localization process in a wireless
ad hoc network, we proceed the optimization procedure at each single node, i.e., for a given state
with initial temperature T, all nodes in the path are considered one at a time.
Different from the search procedure in the indoor localization from the signal strength map
table (SS-MAP), in the outdoor localization procedure, a random optimization movement is given
by adding a deviate from the Cauchy distribution to each coordinates (1,2, ..., p) of node?s previous
position Xi in the format as:
xi+1;k = xi;k +T ?tan(P); k = 1;2;:::;p (4.3)
The overall procedure of the SA-MDS algorithm is similar to the search method in Sec-
tion 3.1.4 in Chapter 3. But the tness determination in step 5 is now adapted to use the classical
MDS algorithm (equation 4.2) instead of the least mean square error (LMS). That is, if a lower
tness function is obtained, keep the displacement from the above step; else, keep the displacement
with certain probability.
Accordingly, the main algorithm can be detailed below:
79
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Original position
Estimate by MDS
Estimates by SA?MDS
Estimates by IT?MDS
Figure 4.2: SA-MDS and IT-MDS algorithm example
while ( not cooling down ) f
Random search a node?s position
Run MDS algorithm
Communication constraints check
Evaluate estimation errors
if (errors < previous estimates)
keep change
else
keep change with probability
end
}
A typical SA-MDS example (with IT-MDS) is given in Figure 4.2. The gure shows a path in
a network of unit square area. ?5? represents the estimated positions by SA-MDS method, and ???
shows the estimates from IT-MDS. The true position is denoted by ?+?. The gure shows that the
SA-MDS may achieve similar or even better estimates than the IT-MDS method.
80
1 2 3 4 5 6 7 850
55
60
65
70
75
80
85
90
95
100
Experiment repetition counts
Estimated nodes (%)
Total nodes: 100, anchor 20, Rand factor: 0.4, Radio range: 0.15
Figure 4.3: MDS estimation coverage analysis
4.3 MDS Processing Coverage Analysis
During the study, we found that MDS based algorithms are able to estimate only the positions
for a subset of the nodes in network. The two major facts contribute this partial coverage property:
1) path requirements, where the MDS algorithm requires more than three anchors for a routing path,
and 2) the DV-Hop propagation method only selects the shortest path when routing.
A typical example is given in Figure 4.3, where a set of repetition experiments is carried out
for a network of 100 nodes (20 anchors). The x-axis denotes the experiment repetition, and the
y-axis is the estimated nodes in percentage. The dotted horizontal line is the average estimation
coverage. The results show the MDS algorithm only estimates the position for about 84% nodes
in the network. Generally, if we enlarge the radio transmission range, then fewer nodes will get
estimated.
This necessities two remedies: 1) Another algorithm to estimate positions for the rest nodes in
the network. In this research, we choose lateration algorithm to estimate the positions for the rest
81
nodes, and 2) Anchor deployment strategy. Similar as the research from Savarese [30], Doherty
[72], and Nagpal [34], we manually deploy four anchor nodes at the corner of the testing area.
4.4 Precision Analysis
In this section, we consider the position estimation performance for two basic algorithms: the
least squares (LS) and the multidimensional scaling (MDS). We rst derive the theoretical esti-
mations for the two algorithms, then we consider a simple range measurement error model, and
experimentally outlines the relationship between the localization precision with the range error.
4.4.1 Theoretical Estimates for Multidimensional Scaling Algorithm
Sibson [103] considered the effect of perturbing the distance matrix ? to a matrix ?(?), such
that ?(?) = ?+ ?F + O(?2), where F is a symmetric zero-diagonal matrix. Sibson showed that
the corresponding induced eigenvalue ? and the Eigen vector V will be:
?i(?) = ?i +??i +O(?2) (4.4)
vi(?) = vi +?fi +O(?2) (4.5)
where ?i =?12vTi Fvi, fi = 12(B ??iI)+Fvi + 12(?in)?1(eTFvi)e.
The superscript symbol ?+? denotes pseudo-inverse, that is for a symmetric matrix M, with
spectral decomposition P?kvkvTk , then M+ is the matrix P??1k vkvTk : ?k 6= 0.
Consider a simple perturbation model F where there is a constant off the diagonal and zero on
it: F = ?(eeT ?I). From [103], we can get ?i(?) = ?i + 12?.
82
Substitute F to equation 4.5, it is trivial to derive the Eigen vector vi(?) = vi 1. Consequently,
the perturbation on the coordinate X will be:
xi(?)?xi = (?i + 12?)12vi ??
1
2i vi (4.6)
According to the binomial expansion, we can simplify the coordination perturbation as:
xi(?)?xi = (?i + 12?)12vi ??
1
2i vi
= ?12vi + 12??12(12?)vi +???+(12?)12vi ??
1
2i vi
= 12??12(12?)vi +???+(12?)12vi
?(12?)12vi +O(?) (4.7)
Formula 4.7 gives the position displacement of a node under constant distance perturbation.
The result shows that the constant distance perturbation will not directly alter the directions (Eigen
vectors) of the deployment con guration, however, it does modify the amount of the stretch for those
directions (Eigen values). In other words, the difference of the position coordinates is determined
only by the variation of the Eigen values.
4.4.2 Theoretical Estimates for Least Square Algorithm
This section derives the formula for the least square method that is addressed at Section 2.3.1
in Chapter 2. We assume that three anchors Ai; i = 1;2;3 are available around the interested
position P, and their coordinates are (xi;yi); i = 1;2;3, and the distances from the anchors to the
position P are di ;i = 1;2;3, respectively. Consequently, according to the Equations (2.5), (2.6),
1Proof:fi = 1
2(B??iI)
+Fvi + 1
2(?in)
?1(eTFvi)e = 1
2?(B??iI)
+vi + 1
2(?in)
?1eT(??vi) = 0.
83
and (2.7), the linearized equation of AX = b is with A and b as follows:
A =
2
64(x1 ?x2) (y1 ?y2)
(x1 ?x3) (y1 ?y3)
3
75 (4.8)
and
b = 12 ?
2
64x21 ?x2n +y21 ?y2n +d2n ?d21
x21 ?x23 +y23 ?y23 +d21 ?d23
3
75 (4.9)
Thus, the determinant and the inverse of the matrix A is:
det(A) = x1 ?(y2 ?y3)?x2 ?(y1 ?y3)+x3 ?(y1 ?y2) (4.10)
A?1 = 1det(A)
2
64(y1 ?y3) (y2 ?y1)
(x3 ?x1) (x1 ?x2)
3
75 (4.11)
Consequently, the coordinates of the position P are:
X = 12?det(A)
2
64(y1 ?y3) (y2 ?y1)
(x3 ?x1) (x1 ?x2)
3
75?b
= 12?det(A)
2
64 y1 ??1 +y2 ??2 +y3 ??3
?(x1 ??1 +x2 ??2 +x3 ??3)
3
75 (4.12)
84
where ?i; i = 1;2;3 are:
?1 = x23 ?x22 +y23 ?y22 ?(d23 ?d22) (4.13a)
?2 = x21 ?x23 +y21 ?y23 ?(d21 ?d23) (4.13b)
?3 = x22 ?x21 +y22 ?y21 ?(d22 ?d21) (4.13c)
Now suppose there is a perturbation for the distance of di; (i = 1;2;3) between the anchors
to the interested position, such that the measured distance is:
bdi = di +?i; i = 1;2;3 (4.14)
Then a location estimation error exists between the true position X and the estimated position
bX, and the difference between is:
bX ?X = 1
2?det(A)
2
64?(y1 ??23 +y2 ??13 +y3 ??12)
(x1 ??23 +x2 ??13 +x3 ??12)
3
75 (4.15)
where ?i;j; i;j = 1;2;3; i 6= j are:
?23 = 2d3?3 +?23 ?2d2?2 ??22 (4.16a)
?13 = 2d1?1 +?21 ?2d3?3 ??23 (4.16b)
?12 = 2d2?2 +?22 ?2d1?1 ??21 (4.16c)
85
0 0.1 0.2 0.3 0.4 0.50
0.2
0.4
0.6
0.8
1
1.2
1.4
Range perturbation d
Estimation error
mds
ls
Figure 4.4: Theoretical estimation errors under various perturbations
4.4.3 Algorithm Precision at Various Perturbations
With the analysis from Section 4.4.1 and section 4.4.2, we calculate the theoretical estimation
errors of two algorithms at various range perturbations. The experiment is carried as follows:
1. Randomly generate a con guration of three anchors and one normal position in an unit square
area;
2. Assume the perturbation of the range r is ?, thus the actual range measurement is given as
r = r?(1?rand??);
3. Apply the MDS and LS algorithm to estimate the location of the normal node.
A comparison of the localization estimation is given in Figure 4.4, where the x-axis is the range
perturbation ?, and the y-axis is the relative estimation error in terms of radio range R. In the gure,
the line with circle denotes the estimation of least squares (LS), and the line with ??? represents the
estimation of MDS. The radio range R in this experiment is set to 0.4, and the results show in the
86
gure is the estimation with 95% con dence for over 5,000 simulation runs. The gure indicates
that the LS algorithm achieves better performance when the error of the range measurement is
small; however, when the error of the range measurement becomes larger, the MDS algorithm is
more precise.
In Chapter 6, we will reiterate this problem together with actual simulations. By outlining the
average estimation error at all anchors? con guration, we tentatively build the relation between the
location estimation error and the perturbation for both algorithms, i.e., MDS and Least Square.
4.5 Radio Range Irregularity Research
The research on Radio Range Irregularity (RRI) is based on experiments. The experiments
were carried out on various environments using IEEE 802.11 wireless Ethernet standard, and it
was found that the radio transmission range at 2.4 GHz UHF (ultra high frequency) band may not
smoothly vary in different directions depending on the presence of obstacles (ex. trees and stones)
in vicinity. This observation is signi cantly different from the conclusion by Zhou et al. [39].
Based on this result, this dissertation develops a realistic RRI model that takes into account, for the
rst time, actual effects from various operating environments and heterogeneous properties of the
wireless devices (transmission with different powers).
Based on the new RRI model, this dissertation analyzes the performance of a set of represen-
tative localization algorithms that were initially based on the ideal radio model. These algorithms
include two multidimensional scaling algorithms [77] , bounding box algorithm [8], and lateration
algorithm [30]. Through simulation, it is found that the realistic RRI model greatly degrades the
performance of all algorithms. Specially, the effects can be identi ed in the following ways:
87
1. Radio propagation method: the maximum-distance greedy forwarding approach is not suit-
able anymore [38];
2. Radio coverage pattern: the radio transmission coverage is not circular, consequently the
neighborhood density is different from (or less than) the ideal counterpart [38];
3. Pair-wise hop distance estimation: under realistic environment, there exists no reliable aver-
age hop distance between communicating nodes if no other mechanisms is available [77, 7];
4. Re nement procedure: it is not appropriate to apply the same the re nement procedure with
information from bidirectional connected neighbors [8, 76].
To remedy the adverse effect of the radio irregular propagation on the localization performance,
this dissertation proposes and evaluates an optimized constrained-greedy forwarding radio prop-
agation method. Test results indicate that better location estimation is achievable.
The rest of the introduction is organized as follows: In Section 4.5.1, we present the analysis
for the radio irregularity and the measurement results. Section 4.5.2 introduces the radio irregular-
ity model, and Section 4.5.3 provides an optimized radio propagation method for the localization
algorithms.
4.5.1 Radio Range Analysis and Measurement
The irregularity of the radio propagation is mainly caused by the multipath environment, and
the power heterogeneity of the transmission devices. To conduct experiments, two laptops with
IEEE 802.11b wireless interface were connected in ad hoc mode to measure the signal strength.
One of the laptops is a Compaq Pavilion v2000 with Intel Pro 2100b card, and the other is an HP
Pavilion ze4900 with D-link DWL-G630 C card. We consider three settings in this dissertation:
88
?50
?100dBm
30
210
60
240
90
270
120
300
150
330
180 0
?50
?100dBm
30
210
60
240
90
270
120
300
150
330
180 0
(a) grass covered land (b) Parking lot
Figure 4.5: Signal strength in clear space
1. Forest land with scattered trees of various diameter on a clear ground;
2. Grass-covered land with grass height around 20 cm;
3. Flat and clear parking lot.
The measured signal strength in grass covered land and the parking lot are plotted in Figure
4.5. The left chart ( gure (a)) is the measurement from grass covered land, where the receiver is 30
meters away from the transmitter; and the right chart ( gure (b)) denotes the measurement from a
parking lot, and the distance between the transmitter and the receiver is around 50 meters. In both
charts, the center denotes the position of the transmitter, and the measured signal strength in -dBm
is denoted by the circular ring around it. It can be seen that the measured signal strength at different
directions at xed distance to the transmitter is approximately circular.
Similarly, the signal strength measurements in two different forest-lands are plotted in Fig-
ure 4.6. Figure 4.6(a) depicts the measurements in a wood with the tree density2 of roughly 20, the
2Tree density is determined by the number of trees N in an area of 100 sq. meters.
89
?50dBm ?100dBm
30
210
60
240
90
270
120
300
150
330
180 0
?50dBm
?100dBm
30
210
60
240
90
270
120
300
150
330
180 0
(a) Forest land, tree density: 0.2 (b) Forest land, tree density: 0.3
Figure 4.6: Signal strength in forest land
distance between transmitter and the receiver is about 20 meters. Figure 4.6(b) plots the results of a
wood of 35 tree density, and the distance is 35m. It is clear that the existence of trees heavily affects
the received signal strength.
To estimate the effect of a tree on the received signal strength, a simple experiment (as depicted
on the left chart of Figure 4.7) was carried out. The tree is approximately 60 cm in diameter, and
is roughly 25 meters away from the transmitter. The measurement positions are about 1.0 meter
beyond the tree, and three positions around the ray sector (denoted by dotted lines on left chart)
are considered. The measurement values are given on the right. The x-axis denotes the three
measurement positions, and the y-axis is the signal strength in -dBm. The results indicate that the
tree strongly attenuates the signal power level in the vicinity of the hidden part behind the tree, and
the signal strength does not smoothly vary.
A similar experiment that considers a rock (instead of a tree) was performed. The rock is about
10 meter away from the transmitter, and the receiver is 1.0 meter after the stone (left chart of Figure
4.8). The measurement results are given in the right chart of Figure 4.8. The x-axis denotes the
measurement positions, and they are roughly 3 degree apart; and the y-axis is the signal strength in
90
A B C40
45
50
55
?dBm
A B C
Tree
Transmitter
~25m
Figure 4.7: Signal strength near a tree
-dBm. This chart clearly indicates that the stone greatly affects the received signal strength level,
and the signal strength does not change continuously.
Finally, we measure the signal strength across a dense bush, where the transmitter and the re-
ceiver is about 20 meters apart, and the bush is roughly 1 meters before the receiver. The signal
power is given in Figure 4.9. The x-axis is the measurement positions in degrees to the rst mea-
surement location; and y-axis is the signal strength in dBm. It can be seen that the bush affects the
signal power level irregularly.
In conclusion, the radio propagation at 2.4GHz has the following properties:
1. The radio transmission range is environment dependent. It is roughly circular on a clear space
with hard and at ground (parking lot).
2. The maximum radio range is determined by the transmission power at the transmitter;
3. In eld deployment, the radio transmission is not regular; and the signal strength variation at
different directions is not smooth around obstacles.
91
A B C D E0
10
20
30
40
50
60
70
80
?dBm
A
~10m
B C D E
Transmitter
Stone
Figure 4.8: Signal strength near a stone
0 5 10 15 20 25 30 35 4040
45
50
55
60
65
70
degree
?dBm
Figure 4.9: Signal strength cross bush
92
Smin?ideal
Smax?ideal
S1
S2
Rmax?ideal
Rmin?ideal
R1
R2e2
(a) Radio signal strength model (a) Radio coverage model
e1
Figure 4.10: Radio irregularity model
4. Depending on the obstacles in each direction around the transmitter, the radio coverage area
may be approximated as a collection of propagation sectors starting from that transmitter.
Each sector experiences a speci c attenuation in that direction.
4.5.2 Radio Range Irregular Model
Based on the ndings from experiment, we propose to use a set of triangular sectors to em-
ulate the radio propagation in various directions. Within ONE sector, we assume the ideal radio
transmission: the signal strength level is modeled as a set of arcs with decreasing power towards the
periphery.
To model the radio propagation with diverse obstacles, the ideal circular radio pattern is sliced
into multiple sectors with different signal strength levels. An example is given in Figure 4.10(a),
where the radio power at a given distance is assumed to be within the range between Smax?ideal
and Smin?ideal. To determine the actual radio signal strength, the ideal circular radio shape is
93
modeled as a collection of sectors where each one corresponds to a particular attenuation in that
direction. The number of sectors is environment dependent (an octagon is used in this example). If
the minimum and maximum signal strength values from the polygon are S1 and S2, approximation
of the signal strength values corresponding to Smax?ideal and Smin?ideal respectively, then at each
sector, the signal strength level could be any value between S1 and S2 as shown in Figure 4.10.
For the localization algorithms, the relationship between the radio range and the received signal
strength is exploited. From the signal strength model in Figure 4.10(a), we know that the radio in
one sector has only one signal strength level and the radio in this sector transmits across the same
media. If we assume that the radio transmission range is only related with the signal strength for a
given environment, the radio propagation range on each arc (within a given sector) should be equal.
Thus, the radio coverage is similar as the layout of the signal strength distribution.
Consequently, the radio range irregularity model is depicted in Figure 4.10(b): the ideal max
and minimum radio range are Rmax?ideal and Rmin?ideal, and they correspond to the signal strength
level of Smin?ideal and Smax?ideal respectively. Using the same sector style, the approximate radio
range is between R1 and R2.
Therefore, to analyze wireless protocols and algorithms, the radio irregularity model can be
constructed as follows:
1. Determine the operating environment, and con gure an appropriate polygon that emulates the
radio transmission. Generally, for a at and clear space with no or few obstacles, approxi-
mated circular transmission is expected, thus close to circular range model is used. On the
contrary, for a eld with trees and rocks, a set of sectors according to the obstacle in each
particular direction will provide similar simulation settings;
94
2. Determine the maximum radio transmission range which is related with the transmission
power;
3. Determine the maximum range attenuation " (Please, see Figure 4.10) according to the pos-
sible obstacles around the transmission node;
Let us denote the ideal radio transmission range Rmax?ideal, the number of edge of the polygon N,
and the maximum range attenuation ". The actual transmission range R at each sector is given by:
R = Rmax?ideal ?sin(?(0:5? 1N))+e1?rand?"?e2 (4.17)
where e1 and e2 are two random numbers with values between the ideal circular transmission range
and the approximated polygon at maximum and minimum borders respectively, i.e., e1 = rand?
(Rmax?ideal ?R2) and e2 = rand?(Rmin?ideal ?R1).
We analyze, in the next section, the effect of the radio range irregularity model on localization
algorithms.
4.5.3 Effect of RRI and Optimization
Most localization algorithms aim to determine the physical location information of nodes in
the wireless network, where a limited number of nodes (called anchors) know their absolute posi-
tions. The determination of location information for nodes other than anchors requires the distance
between nodes, especially the distance from normal nodes to anchors. To determine the distance
information, four representative radio propagation methods have been developed (please, see Sec-
tion 2.3.1 in Chapter 2): 1) DV-Hop method [11]; 2) DV-Distance method [11, 8]; 3) Euclidean
95
4
2 3
6
7
11
13
1
5
8
9
10
12
Figure 4.11: Routing path under regular and irregular radio transmission
method [11]; and 4) Kleinrock?s formula [79]. In the next two sections, we brie y analyze the
above radio propagation methods in the irregular radio networks.
DV-Hop method for Irregular radio networks
DV-Hop method allows each node, during message propagation, to only maintain and rebroad-
cast packets with the smallest number of hop counts to original sources. Therefore the nal routing
path is the one with minimal transmission hops (maximum distance greedy forwarding). For the
ideal circular radio propagation, this method usually generates regular routing path among all nodes.
However, under realistic operating environment, the radio transmission is irregular at all nodes, the
routing paths between communicating nodes are also irregular. Therefore, a network-wide average
hop-size is not reliable as the ideal model counterpart. Consequently, the distance estimation be-
tween normal nodes and anchors contains much larger errors, and thus the localization performance
is greatly affected. We explain these using a real routing path in Figure 4.11.
96
Figure 4.11 shows a network of 36 nodes randomly deployed in a unit area. There is a com-
munication starting from node 1 to node 13, and the gure gives two routing path: the solid line
show the ideal path under regular radio transmission, and another path in dotted line under irregular
radio situation. Additionally, the gure shows a direct line (dotted line) between node 1 and node
13, which is the ideal one-hop direct communication.
Two very interesting routing positions are at node 3 and node 6. For the DV-based radio
propagation method, each node only maintains and rebroadcasts packets with the smallest number
of hop counts. This way, the nal routing path is the one with minimal transmission hops, and thus
it is maximum-distance greedy forwarding. As a result, the routing path is fairly close to the direct
dotted line between communicating nodes. Therefore, in the ideal situation, the total hop counts
between node 1 and node 13 is six.
With irregular radio transmission shape, the DV-based method may still work, but a different
propagation path is selected this time. Because node 6 is not the directed neighbor of node 3, in
order to nd a path from node 3 to the destination node 13, the information packets from node 3
have to route back to node 4 (which is not the neighbor of node 2). Similarly, at node 6, the next
routing intermediate node is node 8. Consequently a routing path is constructed irregularly, and total
hop counts between node 1 and node 13 is now eleven, almost as double as the regular counterpart.
Comparing the two routing paths between two communication nodes, the average hop size
estimation is very different. As it can be seen from Figure 4.11, the value of the estimated average
hop distance for the irregular radio transmission network is much smaller. Although relative good
distance estimation may still be obtained for particular routing path, due to the irregularity nature of
various propagation paths, a network-wide average hop size value is not available. Consequently, the
97
pairwise distance estimation at irregular radio transmission networks contains larger errors, which
will nally affect the location estimation performance of all localization algorithms.
Other methods
Similar to the DV-Hop radio propagation method, the distance estimation performance for the
other three methods also degrades.
DV-Distance method is sensitive to the measurement error, and it works just like DV-Hop: it
generates irregular routing path, and consequently it gets unreliable distance estimates.
Euclidean method assumes dense network environment, which will be affected by the irreg-
ular radio transmission. Additionally, the communication link is not bi-directional, thus the local
geometry information may even not be obtainable. This means that the Euclidean method may not
work correctly for some nodes.
We mainly consider the DV-Hop method in this research. Note however, the proposed method-
ology would equally work with the other three methods. And in the next section, we discuss the
corresponding remedy methods on these negative impacts.
4.5.4 Constrained-Greedy Forwarding Radio Propagation Method
In order to obtain reliable distance estimates, it is critical to select a regular routing path for the
communicating nodes. Accordingly, the key point turns out to identify best candidate nodes that are
used to forward packets to the destination. We develop a constrained-greedy forwarding approach
in this research. The idea is to constrain intermediate nodes within an optimal range, i.e. only the
nodes within a predetermined range are selected to forward packets. This way, the possible routing
deviation or irregularities are prevented.
98
1
2
3
4
5
6 7
9
10
11
12 8
Ideal radio range
Constrained radio range
Actual radio range
Figure 4.12: Routing optimization under irregular radio transmission
An example is given in Figure 4.12. The gure depicts a network with 49 nodes in a unit area.
Two different routing paths are given between node 1 and node 8. The rst path 1-2-3-4-5-6-7-8
denotes the routing by the DV-Hop method, and the second path 1-2-3-9-10-11-12-8 represents the
routing by the constrained-greedy forwarding method.
A critical routing node is node 3, where two very different forwarding nodes (4, 9) are to be
selected. Both candidates are within the radio range of node 3, the difference is that node 9 is close
to the center within the predetermined constrained range. It is interesting to see that both paths
contain seven hops, and it is clear that the second path is more regular than the rst one.
In this dissertation, the constrained radio range is determined as the average value of all radio
ranges in different directions. If the operating environment is a clear space, and the radio is close
to circular, then the constrained radio range is the actual transmission circle. On the contrary, if the
environment is complex, the signal strength along some directions may be heavily attenuated, and
thus the transmission range in those sectors is affected. By average the radio range at all directions,
a small constrained radio range is obtained. We let those nodes that are within this constrained radio
99
range to be the candidates for the information forwarding. Note however, the selected candidates
should also within the actual radio range, which is environment dependent.
In reality, when a node wants to transmit a packet, it measures and incorporates its transmis-
sion power in the packet header. Upon receiving the packet, the neighboring nodes measure the
associated signal strength, and compare it with the original transmission power from the header. If
the received signal strength at a node is above a threshold, then the intermediate node assumes that
it is within the constrained radio range, thus it forwards the packet out if the hop count of the packet
is also minimal.
100
CHAPTER 5
APPLIED RESULTS FOR INDOOR LOCALIZATION SYSTEMS
Extensive experiments have been carried out at two very different buildings to evaluate the
ARIANDE system. We present the rst experiment results in Section 5.1, and then Section 5.2
introduces the comprehensive experimental results in another building at Auburn University.
The experiment for the rst building mainly focuses on the overall performance of the ARI-
ADNE system, and the experiment in the second building is mainly interested in the sniffer?s posi-
tion con guration. We start from the experimental setup for both experiments
5.1 Experiment I
5.1.1 Experiment Setup
Figure 5.1 shows the oor plan of the building used for this study. Three sniffers A, B, and C
are deployed inside the building with sniffers A and C deployed close to west and east boundaries
respectively. Sniffer B is slightly south of the center of the building. Each sniffer was implemented
on an IBM T30 ThinkPad running RedHat 9 operating system. Through the AP, sniffers connected
with the global monitor, which is used to process the signal strength data. The global monitor also
stores the signal strength tables and estimates the users? current location based on the signal strength
readings by sniffers A, B, and C.
In order to validate the proposed indoor radio propagation model, the signal strengths were
collected at 30 different locations. A Toshiba laptop with Linksys WAP 11 wireless card was used
for data collection. At each location, about 100 sample packets were emitted at an interval of 0.5
seconds and measured at sniffers A, B, and C. The positions of data collection are marked in
101
Sniffer data validation positions
B
AP
GM
1
A
2 3 4 5 6 7
8
9
11
12 13
10
14 15
20
16
17
18
19
21
22
23
24
25 26
27
28
29
30 C
dx
dy
36.576 m
45.72 m
Figure 5.1: Floor plan with sniffers and data validation positions (???: reference positions in SS-
MAP table)
Figure 5.1 with faint dots as marked from 1 to 30. The ??? denotes grid positions in estimated
SS-MAP table.
The same series of measurements at the 30 locations were repeated on 6 different days noted
in the following as Dayi.ARIADNE radio propagation model (see Section 3.1.3) is evaluated us-
ing the 30 signal strength measurement triplets collected in the building for all 6 days. Note that
ONE of the 30 signal strength triplets is randomly selected to estimate site speci c parameters
in the ARIADNE radio propagation model and then to compute an estimated SS-MAP table for a
speci c set of grid positions. Given the estimated SS-MAP and the measured signal strength triplet
M(SA;SB;SC)(L;Now)for a mobile at some location L, different search localization algorithms
were evaluated.
102
Table 5.1: Measured signal strength indicator variability over days
Day1-2 Day1-3 Day1-4 Day1-5 Day1-6
Max difference 5.48 6.77 6.30 7.18 7.66
Average difference 2.21 2.79 2.46 3.02 2.81
MSE 0.48 0.58 0.55 0.65 0.63
5.1.2 Measurements
The signal strength was collected on six different days at the data collection positions indicated
in Figure 5.1. Taking Day1 as reference, Table 5.1 reports the variability of the signal strength from
day to day: each column Day1?i displays the variability between Day1 and Dayi. The variability is
captured using the maximum and average difference, and the mean square error MSE respectively
de ned as: 8
>>>
>><
>>>
>>:
max diff = maxni=1fabs(SSDayj;i ?SSDayk;i)g
average = meanni=1fabs(SSDayj;i ?SSDayk;i)g
MSE = 1n(Pni=1(SSDayj;i ?SSDayk;i)2)12
(5.1)
where SSDayj;i and SSDayk;i represent the signal strength measurements at location i on jth day
Dayj and kth day Dayk respectively; n is the number of SS triplets (n = 30).
Table 5.1 illustrates the dynamic nature of the indoor signal strength over time. Such a vari-
ability shows that any search localization method on a static signal strength map SS-MAP will in
general perform poorly.
5.1.3 Radio Propagation Model Validation
The parameters [P0; ;fi] of ARIADNE radio propagation model are estimated for a given
day Dayi using ONE randomly selected signal strength measurement triplet among the 30 triplets
from day Dayi. A signal strength measurement triplet is randomly selected because a potential
103
user of ARIADNE may take the reference measurement anywhere in the building. ARIADNE radio
propagation model is then evaluated using the 30 signal strength measurement triplets from the same
day Dayi. The mean square error MSE between estimates and measurements is used to evaluate
the model tness.
The in uence of the maximum number of re ections and the maximum number of traversed
walls on the accuracy of ARIADNE radio propagation model was investigated:
1. As the number of re ections increases, the attenuation of the signal increases. After some
number of re ections, the contribution of power becomes negligible. Based on the simula-
tions, taking into account more than 3 re ections induces heavy computations without any
improvement of the precision or accuracy. This conclusion concurs with other researchers
(Valenzuela, Fortune, and Ling[104]), therefore, the maximum number of re ections is set to
3;
2. A ray path will traverse at most a limited number of walls. As the ray traverses walls on a
direct path, it weakens in power. We call the maximum number of transmission walls MW the
number of walls traversed before the ray dies . From simulations in the building considered
here, no improvement in precision or accuracy is achieved for MW over 20. Results are
reported here for MW taking values 15 and 20 for comparison.
5.1.4 Simulation Results
Extensive simulations were carried out, and the average results of all simulation runs are com-
pared against the 30 signal strength measurement triplets. For each test run, ONE signal strength
measurement triplet is randomly selected as a reference among the 30 measurement triplets. Good
agreement is obtained between the estimated signal strength map and the measured one.
104
5 10 15 20 25 30160
180
200
220
data validation positions (for Sniffer A)
signal strength
estimates
measurements
5 10 15 20 25 30160
180
200
220
data validation positions (for Sniffer B)
signal strength
estimates
measurements
5 10 15 20 25 30160
180
200
220
data validation positions (for Sniffer C)
signal strength
estimates
measurements
Figure 5.2: Estimation and comparison with measurements at data validation positions
Typical comparison results are shown in Figure 5.2 that consists of three plots respectively for
sniffers A, B, and C. For each plot, the x-axis represents the 30 positions from the data collection
and the y-axis denotes the signal strength measured as received signal strength indicator (RSSI). The
maximum number of re ections is 2 and the maximum number of transmission walls transmission
is 20. The points with symbol ??? are the signal strength measurements, and the points with symbol
??? are the estimates.
Table 5.2 reports for Day1 the difference between estimates and measurements and illustrates
the impact on ARIADNE accuracy of the maximum number of re ections (2 or 3) and the maximum
number of transmission walls (15 or 20). Each simulation run uses as reference one signal strength
measurement triplet randomly selected within the 30 data collection positions from Day1. Each
number reported in the table is the result averaged over more than 20 simulation runs.
105
Table 5.2: Radio propagation model veri cation, maximum RSSI=255
Estimation Sniffer A Sniffer B Sniffer C
vs. Measurement Wall:15 Wall:20 Wall:15 Wall:20 Wall:15 Wall:20
2 re ections Max difference 8.2913 8.3820 15.3067 15.3385 9.4413 7.9786
Average difference 3.3916 3.3487 5.3976 6.3310 3.9688 3.1910
MSE 0.7472 0.7472 1.2309 1.3504 0.8525 0.6976
3 re ections Max difference 8.4514 8.8607 15.4559 13.9691 8.7444 8.2063
Average difference 3.5720 3.5842 6.0425 6.1516 3.5482 3.1853
MSE 0.7723 0.7711 1.3343 1.2967 0.7710 0.6886
Table 5.2 shows that results are quite similar for 2 and 3 re ections. This shows that higher
order re ection rays marginally affect power estimation accuracy. This conclusion agrees with
Valenzuela et al.?s results [104]. Consequently in the following test runs, rays are restricted to at
most of two re ections. Table 5.2 also illustrates that the maximum number of transmission walls
of 15 or 20 yield close results.
However, Table 5.2 suggests an interesting observation: estimates for sniffer B are not as good
as estimates for sniffers A and C. The difference is systematic and signi cant. It was observed that
the wireless card at sniffer B always provides lower readings than those of sniffer A and C. Despite
this, the search localization on the estimated signal strength map SS-MAP still works well because
the received signal strength from a mobile user at sniffer B is always comparable with B?s former
readings. So no calibration was done to produce measurement data used in this work.
Finally, Table 5.2 indicates that ARIADNE radio propagation model yields good estimates (the
maximum signal strength difference is within 3% ? 5% of the maximum RSSI, see Figure 5.2): It
is worth noting that the variability over days (see Table 5.1) is quite close to the difference between
estimates and measurements.
106
1 2 3 4 5 6 7 8 9 100
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of reference measurements
MSE
Figure 5.3: MSE vs. number of reference measurements
5.1.5 Number of Necessary Reference Measurements And Location Dependency
In Section 3.1.4, the simulated annealing searching algorithm is used to estimate the parameter
tride of [P0; ;fi] using one reference signal strength measurement triplet. This section addresses
the question whether multiple reference measurement triplets would yield estimates that are closer
to measurements. The answer is surprising: one reference measurement triplet will yield estimates
as good as estimates from 2, 3, or 10 reference measurement triplets.
Figure 5.3 con rms the ndings. The x-axis denotes the number of reference signal strength
measurement triplets used for estimating the parameters of the ARIADNE radio propagation model,
and the y-axis represents the mean square error MSE of signal strength between measurements and
estimates. For each run of x references, x references are randomly selected to be used to estimate
the radio propagation model and construct the signal strength map. Each point on Figure 5.3 is an
average over 20 runs.
107
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 300.7
0.8
0.9
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
data collection positions
Average MSE of Sinffer A, B and C
Figure 5.4: Reference Measurement Selection
To evaluate the impact of the location of the reference measurement on the performance of the
signal strength estimates, the signal strength map is constructed using each individual 30 collected
signal strength measurements. Figure 5.4 provides the average minimum squared error (MSE) for
sniffers A, B, and C when using as reference measurement one of the 30 collected signal strength
measurements. The x-axis is the location number where the signal strength measurement was made.
The y-axis is the average MSE over all sniffers. Results point out that lowest MSE is obtained with
signal strength measurements 15, 17, and 23. These measurements were made, as shown in Fig-
ure 5.1, close to the center of the building. This appears to suggest that the reference measurement
should be made at the center of gravity of the sniffers. We?ll reiterate this problem in the next
experiment where various sniffers deployment con guration are considered.
Note however, for a building with non-uniform walls (i.e. different construction materials
and thickness), or with spatially different (human) occupation, it is not appropriate to only select
a single measurement at a reference position. In this situation, it is necessary to rst identify all
representative regions for the building such that each region has homogeneous construction material
108
0 10
20 30
40 47
0
10
20
30
37
170
180
190
200
210
220
x (m)
y (m)
Signal Strength
0 10
20 30
40 47
0
10
20
30
37
170
180
190
200
210
220
230
x (m)
y(m)
Signal Strength
0 10
20 30
40 47
0
10
20
30
37
170
180
190
200
210
220
x (m)
y (m)
Signal Strength
175
180
185
190
195
200
205
210
215
Figure 5.5: Signal strength shaded surface at sniffers A, B, and C
and in uniform space. Thus a regional SS-MAP can be constructed in advance, and the overall
building based SS-MAP can then be stitched.
It is worth noting that ARIADNE radio propagation model is quite accurate even though the
sniffers are not deployed in an optimal fashion. The next section addresses the poor deployment of
sniffers through a coverage analysis.
5.1.6 Coverage Analysis
The study in this rst experiment does not have access to the sniffers and thus cannot modify
sniffers? deployment. The work presented in this dissertation just exploits a data set collected in the
work [63]. A gross coverage analysis shows that the sniffers are not optimally deployed.
Figure 5.5 provides a coverage map for each sniffer (A, B, and C). In each 3D plot, the xy
plan is the building oor and the z-axis is the estimated signal strength (RSSI). As the reader can
observe, a considerable portion of the area is dark for each sniffer. These dark areas are quite at as
109
Table 5.3: Localization performance of six experimental measurements
Clustering LMSE 2-N 3-N
err std err std err std err std
Day1 2.8372 2.4304 2.7442 2.0349 3.7355 2.9256 3.5412 3.0458
Day2 2.5330 2.2388 3.5297 2.3543 4.5651 3.5070 4.1878 3.2926
Day3 2.7076 2.1568 3.7510 2.6856 4.1948 2.7037 4.0549 2.6667
Day4 2.9063 2.4727 2.9170 2.5019 2.7875 2.5861 2.6399 2.6080
Day5 3.0004 2.5388 3.6431 2.1429 4.3931 2.5808 3.9705 2.5022
Day6 3.1074 1.7975 3.0704 1.7990 3.5920 2.1638 3.5151 2.1886
Avg 2.8487 2.2725 3.2759 2.2531 3.8780 2.7445 3.6516 2.7173
there is not much difference in the signal strength for locations in this area. Figure 5.5 raises a hope
that better results can be achieved with a better deployment of sniffers.
Alternatively, more sniffers could be deployed to provide better coverage for the building.
This way, only the three best signal strength measurements are selected for future applications,
i.e. if the received signal at one monitor is too weak, the sniffer will not report the signal strength
measurement to the global monitor (GM).
5.1.7 Localization Performance
ARIADNE radio propagation model constructs an imprecise signal strength map SS-MAP on
a grid of locations. To locate a mobile M sniffed as M(SA;SB;SC)(L) at a location L, the
signal strength map SS-MAP must be searched for a best match. This section evaluates the Least
Minimum Squared Error, the multiple nearest neighbors, and the proposed clustering-based search
techniques. The impact of the grid resolution is also evaluated.
As explained in Section 2.2.2 and Section 3.2, LMSE picks only the position with LMSE to
the sniffed signal strength of the mobile user. The scheme of multiple nearest neighbors (nearest
neighbors in signal space, closeness elimination scheme), as the name suggests, selects multiple
closest neighbors and computes the average of these neighbors? positions for the estimates. This
110
work evaluates both 2 and 3 nearest neighbors. The Clustering-based search method works similarly
to multiple nearest neighbors technique, however, it is more exible in that it does not restrict or x
the number of neighbors. Instead, the clustering-based search algorithm selects a set of candidate
positions with signal strength close to the mobile user, and group these positions in space into
multiple clusters. Then the algorithm picks the center of the largest cluster as the estimate.
A signal strength map SS-MAP is built over a grid of known locations (reference points) based
on the proposed radio propagation model. The horizontal and vertical distances between reference
points are 0:75 meter and 1:5 meter, respectively (see Figure 5.1). Six different SS-MAPs for the 6
days Dayi were constructed to evaluate the localization performance of the three strategies.
With the sniffed signal strength triplet as an input, the signal strength map SS-MAP is
searched using LMSE, multiple nearest neighbors, or clustering-based techniques. Table 5.3 sum-
marizes the error distance in meters between the real location and the estimated location. The error
and standard deviation are reported for each search method for the six days. The last row provides
an overall average of the six days. The clustering-based localization algorithm in general outper-
forms all other techniques. For a grid positions of 0:75?1:5 meter apart, and for the oor plan
in Figure 5.1, clustering-based method gives the position estimation with average error of 2.8487
meters. The estimation with clustering-based is respectively 14.99%, 36.13% and 28.18% closer
than with other techniques.
Note that the localization performance reported in the table 5.3 is based on a dynamically
estimated SS-MAP over a grid of positions with resolution of 0:75?1:5; and the system has only
three sniffers that are not optimally deployed inside the building (Please, see Section 5.1.6). Thus
we anticipate that better localization performance can be obtained if the system is with optimal
con gurations and ner reference grid resolution (as will be discussed in the next section).
111
Table 5.4: Grid resolution on the performance of Localization
0:75?1:5 m 1:5?1:5 m 3:0?3:0 m
err std err std err std
Avg 2.8487 2.2725 3.2861 2.0494 3.4481 3.5999
1 5 2
3 4
6
7 8 9 10
11 12
13 14 15 16
x
y
D
Figure 5.6: Grid resolution on the performance of clustering localization
5.1.8 Impact on Grid Resolution between Reference Points
This section addresses the question whether a ner resolution grid signal strength map would
yield better accuracy for the cluster-based search technique. A simple example is provided to
explain why ner grid resolution yields better results and simulations con rm this in Table 5.4.
Table 5.4 provides the error and standard deviation for 3 different grid resolutions (in meter):
0:75?1:5, 1:5?1:5, and 3:0?3:0.
Lower estimation error at ner grid resolution is due to more candidate points in the vicinity of
the true position. Figure 5.6 illustrates the impact of grid resolution. In Figure 5.6, the true position
of the mobile user is denoted by ? at point D. If coarse grid resolution is to be used (reference
112
Table 5.5: Mobile vs. static localization
Mobile Static
Path 1-7 2.0798 2.8558
Path 8-11 1.7476 2.6384
Path 16-19,15 2.0742 2.3065
Path 21-25 3.3953 4.9681
Path 27-30 1.3847 1.7620
Avg 2.1363 2.9061
positions at cross points of solid lines), a set of four points (1 ? 4 with sign ? in the gure) may
be selected as the nal cluster group of estimates. The center of this cluster is given at position 8.
Alternatively, if ner grid resolution is to be used (reference positions at cross points of both solid
and dashed lines), then all points in the gure (1?16 with sign * in the gure) may be included in
the nal cluster. And the center will be in position ', which is much closer to the true location of
the mobile user. Hence, ne grid resolution yields better localization performance.
5.1.9 Mobile User Localization
If a user is mobile, better accuracy can be achieved due to geometric constraints and physical
limits (maximum speed, movement patterns along corridors, and users do not step on walls unless
drunk!). As in RADAR, mobility helps improve accuracy. Assume a mobile user is moving along
a corridor in Figure 5.1. The distance limit of the mobile user between two continuous locations
within a sampling period is no more than 5.0 meters. Experiments with mobile users were conducted
in this work. Table 5.5 provides the localization performance for stationary and mobile users.
The path information in Table 5.5 is corresponding to the data collection positions along the
corridor in Figure 5.1. For example, Path 1-7 denotes the scenario of a mobile user moving from
113
position 1 to position 7 along the corridor. The numeric value in the table is the average estima-
tion error in meters for all data collection positions along the path. The bottom row is the overall
localization performance for both cases.
5.2 Experiment II
The second experiment was carried out in a basement at Auburn University from April to
July, 2005. The oor plan is given in Figure 5.7. The positions from 1 to 22 are the measurement
locations for the indoor radio propagation validation, and the three-bit number associated with each
room denotes the of ce number. In this oor, room 101, 107, 109, 112 and 111 are classrooms, room
110 is the computer lab, and the rest rooms are of ces. Typical of ces usually contain computers,
(metal) bookshelves, and (metal) cabinets. The computer lab in 110 is occupied with three rows
of computers, additionally, there are metal bookshelves and cabinets around all four walls. Besides
the normal of ce/classrooms, there are a set of rectangular construction columns, as well as a set of
storage rooms for the air conditioners.
Based on the observation from the rst experiment, this second experiment will mainly focus
on the sniffer position con guration and the oor structure modeling. Therefore, three, four or ve
sniffers will be deployed (Please, see Figure 5.8) in the building to study the deployment on the
performance of the indoor wireless localization. For oor structure modeling, we will try various
methods to model the construction columns and the of ce furniture (i.e. bookshelves and cabinets).
Different from the previous experiment, each sniffer in this experiment was implemented on a
HP Pavilion v2000 with Orinoco Golden card running Linux Fedro II operating system. Through
the AP, sniffers connected with the global monitor by the internal BroadCom wireless interface.
114
1 2 3 4 5 6 7
8 9 10 11 12 13
14 15 16 17 18 19
20 21 22
103
104 107 109 110 112
102
101
105 106 108 111
43.07 m
19.16 m
Figure 5.7: Floor plan with data validation positions
5.2.1 Sniffers Con guration
In order to analyze the sniffer?s position on the performance of the indoor localization, we vary
the number and the position of sniffers. We use three to ve sniffers in this experiment, and a
comprehensive illustration of the deployment details can be seen in Figure 5.8.
As it can be seen from Figure 5.8, we mainly takes ve different deployment con gurations in
the experiment:
1. Linear: con guration (a) and (e);
2. Acute triangle: con guration (c) and (d);
3. Obtuse triangle: con guration (b);
4. Redundant zigzag: con guration (f), (g) and (h);
115
(a) (b) (c) (d)
(e) (f) (g) (h) (i)
Figure 5.8: Various sniffer deployment
5. Semi-grid: con guration (i).
In the following sections, we will rst evaluate adaptability of the indoor radio propagation
model by comparing the estimated signal strength with the actual measurements at all data evalua-
tion positions in the building. Then we construct the signal strength map, and analyze the localiza-
tion performance under various deployment con gurations.
5.2.2 Signal Strength vs. Distance
In order to estimate the relation between the distance and the received signal strength indica-
tor (RSSI) along a straight line inside the building, we carried out two experiments: the rst one
measured the RSSI in the corridor, where there is no walls between the transmitter and the receiver
(line-of-sight); and the second one measured the RSSI within rooms from 101 to 112. The results
are given in Figure 5.9. In both gures, the x-axis is the distance in feet, and the y-axis denotes the
116
0 10 20 30 40 50 60 70 8060
80
100
120
distance (feet)
RSSI
RSSI vs. distance across walls
0 20 40 60 80 10080
90
100
110
120
distance (feet)
RSSI
RSSI vs. distance along corridor
Figure 5.9: Indoor RSSI vs. distance
RSSI. The circle dots are measurement results, and the dashed lines represent the tted trend-lines
of the measurements.
It is obvious that there is no simple relationship between the RSSI and the distance. Comparing
the measurements with the two con gurations (with or without walls), the signal strength attenuation
is higher when there are walls between the transmitter and the receiver. In both cases, the signal
strength decaying slops (attenuation speed) are not linear. The experiments show that the simple
radio propagation attenuation model in Section 5.1.2 may not be suitable for complex building
environments.
5.2.3 Radio Propagation Model Validation
When three sniffers are deployed in the building as shown in gures (a) to (e) in 5.8, the ARI-
ADNE system randomly selects ONE measured signal strength triplet from the 22 data validation
117
2 4 6 8 10 12 14 16 18 20 2260
80
100
120
data validation positions (for Sniffer A)
signal strength
estimates
measurements
2 4 6 8 10 12 14 16 18 20 2260
80
100
120
data validation positions (for Sniffer B)
signal strength
estimates
measurements
2 4 6 8 10 12 14 16 18 20 2260
80
100
120
data validation positions (for Sniffer C)
signal strength
estimates
measurements
Figure 5.10: Indoor radio propagation model validation
positions. Then it regenerates the signal strength for all 22 positions. We validate the proposed radio
propagation model by comparing the estimates with the measurements. Similar as the previous val-
idation in another building in Section 5.1.2, very good agreement is achieved for all con gurations.
A typical comparison is given in Figure 5.10, and the detailed comparisons for the ve con gu-
rations are given in Table 2. In Figure 5.10, the x-axis represents the 22 positions from the data
collection and the y-axis denotes the signal strength measured as received signal strength indicator
(RSSI). Points with ??? are the signal strength measurements, and the points with symbol ??? are
the estimates.
Table 5.6 provides the detailed comparison for all con gurations. The results shown here are
the average difference between estimates and the measurements, and each estimation process uses
only ONE reference measurement that is randomly selected from the 22 positions. Or in other
words, the results are the average values of 22 comparisons. For each sniffer, the comparison gives
118
Table 5.6: Indoor radio propagation model validation for all sniffer con gurations
Sniffer A Sniffer B Sniffer C
err std max dif err std max dif err std max dif
con g (a) 0.9598 0.0930 8.37% 0.7639 0.1040 6.91% 0.9975 0.1205 9.16%
con g (b) 0.7179 0.0734 5.65% 1.0559 0.2381 9.36% 0.8811 0.2728 6.35%
con g (c) 0.9144 0.0795 8.06% 0.7575 0.1079 6.64% 0.8193 0.1382 5.64%
con g (d) 0.7373 0.0862 5.87% 1.0771 0.1359 9.40% 0.9405 0.1755 8.35%
con g (e) 0.8073 0.0934 7.48% 0.9152 0.1412 8.71% 0.8341 0.2582 6.99%
mean square error (MSE), the standard deviation (std), and the maximum relative difference (Max
diff) between the estimates and the measurements.
The maximum relative difference is calculated as the maximum difference between estimates
and the measurements divided by the maximum measured signal strength values. When expressed
by formula, it is in the format:
maximum relative difference = max(abs(SSest ?SSmea))max(SS
mea)
(5.2)
From Figure 5.10 and Table 5.6,it can be seen that the introduced indoor radio propagation
model effectively estimates radio signal strengths: the mean square error (MSE) of between mea-
surements and estimates is less then 1.0, and the relative maximum difference is within 10% for
all con gurations. The results present in this paper are very similar to those of another building
that were reported in Section 5.1.2. Thus we conclude that the radio propagation model proposed
in the ARIADNE system is valid. Comparing the signal strength estimation performance at all
con gurations with three sniffers, it can be seen that there is no preference for the signal strength
estimation on a particular con guration. Or in other words, given any sniffers con guration, the
119
Table 5.7: Localization performance for all sniffer con gurations (Experiment II)
Clustering LMSE 2-N 3-N
err std err std err std err std
con guration (a) 3.7575 2.1063 5.0022 2.6465 4.8774 2.7854 4.1998 2.7869
con guration (b) 4.1758 3.1056 4.4543 2.9503 4.4298 2.9801 4.1149 3.2755
con guration (c) 2.6986 2.0957 3.5987 2.5229 3.4119 2.5004 3.2570 2.0454
con guration (d) 2.8961 1.6098 4.4191 3.1258 4.5212 3.0957 3.3934 1.9603
con guration (e) 4.2239 2.9542 4.4217 3.4447 4.2486 3.3568 4.0814 2.3930
con guration (f) 2.3781 1.7420 4.1639 2.1107 4.1131 2.1008 3.0554 1.6391
con guration (g) 2.2646 1.4928 3.3410 1.8016 3.0167 1.8379 2.8114 1.8875
con guration (h) 2.4235 2.2844 2.9646 1.8999 2.9159 1.8679 3.4603 2.0390
con guration (i) 1.9176 1.8013 3.3090 2.4472 3.0140 2.3437 3.0516 1.9145
signal strength estimation using the proposed radio propagation model, for the same building and
same sniffers, achieves similar precision.
5.2.4 Impact of Different Sniffers Position Con guration
Based on the radio propagation model and the reference, we built a signal strength map (SS-
MAP) over a gird of positions with the resolution of 0.55m in both x and y directions. Similar to
Section 5.1.7, we simulate the localization process with four algorithms, and the results are given
as con guration (a) ? (e) in Table 5.7.
With the estimated signal strength map table, the clustering-based localization algorithm yields
an estimation error of 2:5?4:3m for all con gurations for the complex basement environment. Of
the four algorithms, the clustering method proposed in this paper produces the best results for all
con gurations.
Comparing the localization performance for all con gurations, the con gurations (c) and (d)
yield a much better location estimation performance than all others. The results indicate that the
120
Table 5.8: Average/Maxumum uncertainty distance for the building (Experiment II)
dAUD dMUD standard deviation of dAUD location estimates
con guration (a) 4.8907 12.5976 0.4850 3.7575
con guration (b) 3.0809 8.1816 0.2146 4.1758
con guration (c) 2.0694 5.7051 0.3972 2.6986
con guration (d) 1.7815 4.5425 0.3408 2.8961
con guration (e) 6.3066 13.3697 0.4102 4.2239
con guration (f) 1.4752 4.4445 0.1952 2.3781
con guration (g) 1.4445 4.2666 0.2625 2.2646
con guration (h) 1.5556 4.4927 0.4064 2.4235
con guration (i) 1.1319 3.1726 0.1661 1.9176
sniffers con guration
for experiment I 2.2774 6.1752 0.3888 2.8487
triangular con guration maximizes the discrimination of the signal strength triplet. This outcome
corresponds to the conclusions in Section 3.4 at Chapter 3
In order to understand the intricacy of the sniffers con guration on the indoor localization per-
formance, we compute the average uncertainty distance and the maximum uncertainty distance for
all con gurations from (a) to (e). Then we average the distances at all grid points for the whole
building, and the results are given in Table 5.8. Figure 5.11 additionally shows the average uncer-
tainty distance in z-axis at all grid points for the con guration (c) and (d). In the gures, the x- and
y-axis give the oor plan in two dimensions. Both gures show that the area outside of the triangle
of the three sniffers gives larger average uncertainty distance.
Table 5.8 also gives the average/max uncertainty distance for all other con gurations form
(f) to (i). The forth column is the standard deviation of the average uncertainty distance, and
the fth column is the location estimates for the corresponding sniffers con gurations (adopted
from Table 5.7). Comparing the values in column 2 and column 5, it is found that the errors of
most actual estimates are larger than the average uncertainty distance. Or in other words, the
121
?10 ?5 0
5 10 15
20 25 30
?10
?5
0
5
10
15
0
2
4
6
Average uncertainty distance
?10 ?5 0
5 10 15
20 25 30
?10
?5
0
5
10
15
0
2
4
6
Average uncertainty distance
1
2
3
4
5
6
1
2
3
4
5
y (19.16m)
x (43.07m)
x (43.07m)
y (19.16m)
O1 O2
O3
O1
O2 O3
configure (c)
configure (d)
Figure 5.11: Average uncertainty distance of the estimation for con guration (c) & (d)
average uncertainty distance of the deployment gives the optimal achievable bounds for the indoor
localization performance.
However, there are two exceptions in the con guration (a) and (e). The reason may lie in the
fact that the linear sniffers con guration usually gives two candidate positions at both sides along
the line formed by the sniffers. For an idealized environment without partitions, the two positions
are symmetric along the central line, thus the average uncertainty distance equals the half of the
distance between the two possible positions. In reality, due to the multipath effect of the indoor
radio propagation, there may exist no such symmetric estimation at certain positions. Therefore,
the theoretical average uncertainty distance over-estimates the errors for the aligned deployment
scheme.
The results in Table 5.8 also indicate that the con guration (d) is the most optimal deployment
strategy and the average uncertainty distance is within 2.0 meters. The con guration (c) ranks the
122
010
2030
4045
0
5
10
15
20
0
20
40
60
80
100
120
Signal strength
70
80
90
100
110
120
130
Sniffer
x (m)
y (m)
Figure 5.12: Signal Strength of the Sniffer at the lower corner (con guration (d))
next and the average uncertainty distance is around 2.0 meters. However, comparing con gurations
(c) and (d), the localization performance of (d) is a little worse than that of the con guration (c).
This shows that the sniffers deployment should also consider many other site speci c parameters in
the building. An illustration is given in Figure 5.12, where it gives the signal strength map for one
of the sniffers together with the corresponding oor plan. In the gure, the x-axis and y-axis denote
the oor plan in two dimensions, and z-axis represents the received signal strength at this sniffer.
As shown in the gure, the received signal strength for positions around the opposite corner (lower
right side) is almost at, or in other words, they are indistinguishable. Therefore, the deployment of
this sniffer does not provide optimal signal strength coverage.
Therefore, to achieve optimal localization performance, the sniffers should not be aligned, in-
stead, the deployment should be in acute triangle style in order to produce lower average uncertainty
123
distance for the interested locations. And the con guration must also provide full signal coverage
for the estimated locations.
5.2.5 Number of Available Sniffers
In order to analyze the amount of available sniffers and their deployment strategy on the per-
formance of the indoor localization, we deployed four and ve sniffers inside the building (Figure
5.7) as shown in Figure 5.8 from (f) to (i). We repeated the whole localization process and nally
we obtained the average localization error within 2.50m (see Table 5.7) for all three con gurations.
The improvement is systematic as compared with that of three sniffers in con guration (a) to (e).
This conclusion agrees with the enhancement study from the RADAR system [61].
Similar as the con gurations of three sniffers, we also calculate the average uncertainty dis-
tance for con gurations from (f) to (i), and the results are given in Table 5.8. It can be seen that
the deployment of more sniffers gives much smaller average uncertainty distance. Comparing the
location estimation errors of con gurations from (f) to (h) with four sniffers, the deployment of (h)
is worse than the other two deployments in (f) and (g). It appears that the middle sniffer on the
right side (of the three sniffers) improves the discrimination of the signal strength, however, it is
within the coverage of the triangle formed by the other three sniffers, and therefore its contribution
is limited.
The con guration (i) is in semi-grid style although we could not deploy the sniffers ideally due
to administration restrictions. Initial experimental results in Table 5.8 indicate that this deployment
strategy does provide the best average uncertainty distance and localization performance (within
2.0 meters).
124
101 104 107 109 110 112
102 103 105 106 108 111
Figure 5.13: Floor plan without construction columns
Therefore, if the location-based applications require higher precision indoor localization es-
timation, the deployment of extra redundant sniffers could be a reasonable approach. And if the
sniffers are deployed in the semi-grid style, the location estimation will achieve optimal perfor-
mance.
5.2.6 Column/Post Modelling
We analyze the construction columns on effect of the indoor localization system in this section.
For the same basement show in Figure 5.7, a oor without columns is given in Figure 5.13.
We compare the signal strength estimation performance and the localization performance based
on the sniffer con guration (c) in Figure 5.8. The results are given in Table 5.9 and Table 5.10. From
the two tables, it shows that the construction columns do affect the performance of both the indoor
radio signal strength estimation and the localization, and the consideration of the columns in the
oor plan model will help the indoor localization system.
125
Table 5.9: Signal strength estimation under various oor con gurations using sniffer con guration
(c)
Sniffer A Sniffer B Sniffer C
err std max dif err std max dif err std max dif
Columns 0.9144 0.0795 8.06% 0.7575 0.1079 6.64% 0.8193 0.1382 5.64%
No Columns 1.1020 0.1103 8.76% 0.8758 0.0831 6.70% 1.0490 0.1765 7.56%
Furniture 0.8940 0.1094 7.46% 0.8528 0.1942 6.70% 0.8189 0.1896 6.37%
Table 5.10: Localization performance under various oor con gurations using sniffer con guration
(c)
Clustering LMSE 2-N 3-N
err std err std err std err std
with Columns 2.6986 2.0957 3.5987 2.5229 3.4119 2.5004 3.2570 2.0454
without Columns 2.9628 2.4059 3.6045 2.0442 3.5934 2.1388 4.0710 2.7069
with Furniture 2.5706 2.0910 4.2124 28853 4.2120 2.8343 2.9353 2.0208
5.2.7 Furniture Modelling
As introduced in Section 5.2, some of the rooms (#102 ? #106, and #108) in this basement
are of ces, and the room #110 is computer lab. All of ces contain some furniture (bookshelves and
cabinets); And the computer lab is extremely different from general of ces and classrooms in that it
contains three rows of computers; additionally, there are bookshelves and cabinets around the room
along all four walls (except the door). The furniture is mainly made of metal, and the average height
of them is around 1.70 meters. They should affect or even block the radio propagation.
To consider the furniture?s effect on the indoor localization, we roughly model the furniture
as additional walls along with the oor plan. We repeated the localization process for the sniffer
con guration (c) in Figure 5.8, and the results are also included in Table 5.9 and Table 5.10.
The results show that the consideration of the furniture slightly improves the overall perfor-
mance of the indoor localization system. However, the results also indicate that to simply model
126
Table 5.11: Measured RSSI at different humidity environment
Sniffer A Sniffer B Sniffer C
Max difference 18.0 17.0 9.0
Average difference 7.8091 4.6134 3.1636
MSE 1.8674 1.2782 0.8467
the furniture as additional walls does not optimally capture the radio attenuation effect of the indoor
radio propagation.
Moreover, in this basement, there are three storage rooms and two closets that are used mainly
for air conditioners and sundry goods. We could not access these rooms, therefore the internal
structure is unclear. We believe these storage rooms also affects the performance of the indoor
localization system.
5.2.8 Cell-based Localization
Cell-based localization means that we localize a mobile based on the room resolution instead
of absolute geometry coordinates. In this way, the only requirement is to correctly position a mobile
within a right room without actual consideration of the detail location.
In this experiment, we treat each room as a cell, and the long and the short corridors (between
room #108 and #111) also denote two cells. For the tested positions in this experiment, over 85%
probability is obtained to correctly estimate a mobile within the right room. The only 2 or 3 missed
positions are around the computer lab (#110), and they are usually found in the nearby cells. This
indicates that cell-based localization could be reliably used for some localization based applications;
more over, the correct modelling of the furniture is a necessary in the future research.
127
5.2.9 Humidity Effect
IEEE 802.11b standard uses radio frequency in the 2.4GHz band. Signal of this frequency
is subjected the in uence of the environmental humidity. We conducted an experiment in such an
environment with humidity of over 95%, and we compared the signal strength measurement with
that of normal dry environment (humidity around 30%). The comparison for sniffer con guration
(d) in Figure 5.8 is given in Table 5.11.
Compared with the signal strength measurement variance in the rst experiment (Please, see
Table 5.1), the humidity does greatly affect the signal strength measurement. This again indicates
that dynamic signal strength map SS-MAP construction is necessary for the real-time indoor local-
ization.
5.2.10 Dynamic SS-MAP Update
A ?stationary emitter? as described in [105] judiciously positioned in the building can be used
to be periodically sniffed to provide the reference signal strength measurement to dynamically
generate a real time signal strength map SS-MAP. Such reference device would capture dynamic
changes in the environment. The question is whether the map can be computed fast enough to take
into account swift changes in the building.
The signal strength map SS-MAP table consists a grid of known locations in which the values
of corresponding signal strength are stored. Generally, a higher resolution table is required in order
to obtain better location estimation. Higher grid resolution induces more computation for the con-
struction of the ray tracing from each point to a set of receivers (APs or sniffers). For example, the
approximate time taken to run the ray tracing for 30 positions and 3 sniffers is about 2 hours on a
machine of x86 family processor at 1.4GHz with 256 MB physical memory. However, a building
128
oor plan rarely changes. Therefore, ray tracing can be processed once and ray information can be
stored in advance. The stored ray information can be fed to ARIADNE to generate a dynamic signal
strength map. Given the ray information, the construction of a SS-MAP table with 300 points and 3
sniffers takes less than one minute. So, a dynamic realtime signal strength map is possible as long
as structure conditions in a building remain stable.
5.3 Discussion
To improve the localization performance, the following three problems must be solved.
1. Accurate signal strength readings from all sniffers: In the rst experiment, the readings from
sniffer B contain system error (see Section 5.1.3). The performance of the proposed localiza-
tion scheme should improve for the oor plan in the experiment;
2. Optimal sniffer deployment: In Section 5.1.6, it is found that deployment of the three sniffers
(for the rst experiment) is not optimal. Specially, coverage-insensitive areas do exist at
corners in the studied oor of the building. To improve this, sniffers A and C may be placed
a little closer to the center in y direction (see gure 5.5).
From the second experiment, it shows that the triangular sniffer deployment (con guration (c)
and (d) in Figure 5.8) gives much better localization performance. Additionally, more sniffers
will generally help the performance of the indoor localization system as given in Table 5.7.
And if the sniffers are deployed in the semi-grid style, optimal localization performance can
be achieved.
3. Furniture modelling: As discussed in Section ??, the simple modelling method for the furni-
ture can improve the localization performance, however, to model the furniture as additional
129
walls does not fully capture the attenuation properties of the furniture. Additionally, the clos-
ets and AC storage rooms are not modelled in the second experiment.
4. Grid resolution: The grid resolution of the reference positions in the SS-MAP table affects
the localization performance, and as indicated in Section 5.1.7, ner resolution grid will im-
prove the localization performance. However, ner resolution SS-MAP generally require
more computation for both table construction and the real-time localization.
Thus, the precision of the indoor localization really depends on many parameters (building
structures, sniffer con guration, available sniffers, furniture, grid resolution, and many others), and
it is inappropriate to evaluate the performance of the indoor localization systems only based on the
best reported localization precision.
130
CHAPTER 6
APPLIED RESULTS FOR OUTDOOR LOCALIZATION SYSTEMS
This chapter dedicates to present the simulation results for the outdoor localization algorithms.
Section 6.1 will rst introduce the simulation environment. Section 6.2 presents the simulate results
for the proposed algorithms, in Section 6.3, the dissertation compares the performance of various
localization algorithms, and Section 6.4 introduces the results for the radio range irregularity.
6.1 Environment and Settings
The simulation is built in Matlab (version 6.1). We measure the estimation errors (see sec-
tion 4.1.2) under various network settings. To simulate the ad hoc nature of the network, we run
each test case multiple times with the same network settings, and take the average results for this
dissertation.
For the simulated annealing MDS (SA-MDS) algorithm, we select the initial temperature Tmax
value as the half radio range (i.e. Tmax = R2 ). And for all simulation runs, we use a network of 100
randomly deployed nodes in a unit square area. In addition, the network can update the following
parameters: 1) Anchor node density, 2) Radio transmission range, 3) Deployment randomness, and
4) Range measurement errors.
In the following sections, we rst present the simulation results for MDS, IT-MDS and SA-
MDS algorithms under various network conditions. Then, we outline the reported localization per-
formance from other research groups. In the end, we compare, under the same network settings, the
performance of proposed IT-MDS and SA-MDS algorithms with other representative algorithms.
131
10 20 30 400
0.1
0.2
0.3
0.4
0.5
Anchor percentage
Estimation error
Radio range: 0.15
MDS
IT?MDS
SA?MDS
10 20 30 400
0.1
0.2
0.3
0.4
0.5
Anchor percentage
Estimation error
Radio range: 0.20
MDS
IT?MDS
SA?MDS
Figure 6.1: Precision with the anchor ratio
6.2 Algorithm Simulation Results
To understand the dependency of the estimation precision on the anchor population, we run
the IT-MDS algorithm and the SA-MDS algorithm with different number of anchors in a set of
networks with same network parameters. Figure 6.1 shows the relation between the precision and
the anchor population. The deployment randomness is 0.4. The x-axis of the gure represents
anchor percentage, and the y-axis denotes the estimation errors in term of radio transmission range.
The left chart of Figure 6.1 shows the results of radio range of 0.15, and the right chart shows
that of radio range of 0.2. Both results indicate a trend that more anchors will lead a better perfor-
mance. Figure 6.1 also shows the relation between the estimation error and the radio transmission
range. The result is that both algorithms give better estimates at larger radio transmission range.
Figure 6.2 gives the experimental results of the deployment randomness (x-axis) on the perfor-
mance of the positioning precision (y-axis). It shows MDS based algorithms are insensitive to the
deployment randomness.
132
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10
0.1
0.2
0.3
0.4
0.5
Randomness
Estimation error
Total nodes: 100, Anchors: 25, Radio range 0.2
MDS
IT?MDS
SA?MDS
Figure 6.2: Precision with randomness
0 0.1 0.2 0.3 0.4 0.50
0.1
0.2
0.3
0.4
0.5
Range errors
Estimation error
Total nodes: 100, Anchor: 25, Radio: 0.2, Randomness: 0.4
MDS
IT?MDS
SA?MDS
Figure 6.3: Precision with the 1-Hop range error
133
0 0.1 0.2 0.3 0.4 0.50
0.1
0.2
0.3
0.4
0.5
Accumulated errors
Estimation error MDS
IT?MDS
SA?MDS
Figure 6.4: Precision with the accumulated Euclidean error
To determine the effect of the 1-hop range measurement error on the performance of the estima-
tion precision, we simulate the 1-hop range error for both algorithms. The range error is determined
relatively to the radio range; and to simulate the real situation, we de ne a maximum variance for
all range measurements. The actual range error is determined dynamically during the experiment
by the production of the maximum variance and a random number between -1 and 1. The results
are given in Figure 6.3. It shows that the estimation performance does not signi cantly decrease
with the increasing 1-hop range errors. The main reason may because of the incorporation of the
communication constraints during the iteration. Also we relocate all anchors? positions and ad-
just the corresponding distance among them after each estimation iteration. These procedures can
potentially minimize the range errors.
To measure the accumulated errors for the Euclidean propagation method, we conducted sim-
ilar experiments as for DV-Hop. The results is given in Figure 6.4. The gure shows the increasing
estimation errors when the accumulated errors increase. However, with Euclidean method, both
proposed algorithms give better estimation performance if small error is presented.
134
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.50
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
Range error
Estimation error
LS theoretical
MDS theoretical
It?MDS
SA?MDS
Figure 6.5: Precision analysis
Figure 6.5 shows the theoretical estimation precision for both the MDS and the Least Squares
under constant perturbation (x-axis) (Please, see Section 4.4 in Chapter 4). It also gives the esti-
mation results for IT-MDS and SA-MDS algorithms. The network for the proposed algorithms is a
network with 100 nodes, anchor ratio is 20%, the radio range is 0.2, and the randomness is 0.4. The
results show that the proposed algorithms are fairly robust on the 1-hop pair-wise distance errors
because of the radio communication constraints that have been adopted in the methods. Comparing
the theoretical results for LS and MDS, it shows that the estimation errors for both algorithms are
pretty close, and at larger range measurement error, the location estimation of the LS is a little worse
than that of the MDS algorithm.
In Figure 6.5, it also indicates that when the range error is less than 0.25, the theoretical es-
timation error is less than that of the proposed algorithms. The reason may lie in the fact that the
proposed algorithms use very limited range information between pairwise nodes during the location
estimation.
135
Table 6.1: Reported estimation error in literature
Algorithms Condition & settings Estimation error
Probability algorithm
by Ramadurai and Sichitiu [38] transmission range: 20m 47%
Ad hoc positioning system isotropic topology, 10% anchor 35%
by Niculescu and Nath [67, 36] isotropic topology, 20% anchor 25%
anisotropic topology, 10% anchors 100%
anisotropic topology, 20% anchors 90%
Robust algorithm by Savarese [30] connectivity >7; anchor density >5% 33%
Approximate point-in-triangulation
test (APIT) algorithm by He [33] higher power transmitters at anchors 45?50%
Amorphous algorithm by Nagpal [34] local neighborhood density about 20 20?37%
6.3 Algorithm Comparison
6.3.1 Reported performance
In order to evaluate the localization performance of the proposed algorithms, in this section,
we rst illustrate the reported localization performance from other research groups.
The results are given in Table 6.1. It can be seen that the location estimation performance is
closely related to special network settings. Consequently, it is very dif cult to compare them only
with these values. From the table, it can be seen that the best reported estimation error is within
20%?50% for networks with normal (isotropic) topology.
6.3.2 Localization Performance under Same Network Environment
In this section, we rst compare our IT-MDS and SA-MDS with the iterative MDS algorithm
by X. Ji in [9]. Then we compare the localization performance of the proposed algorithms with
three other representative algorithms under same networks of different deployment randomness.
136
0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.20.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
anchor ratio
Estimation error X. Ji?s results
IT?MDS
SA?MDS
Figure 6.6: Comparison with X. Ji?s algorithm
Figure 6.6 gives the comparison results of our algorithms with the iterative algorithm by X.
Ji. The test environment includes 400 nodes in a unit square area, the distance measurement error
is 0.5 radio range. The x-axis denotes the anchor ratio, and y-axis is the estimation error. X. Ji?s
estimation results is adopted directly from [9]. The simulation results show that the localization
algorithms proposed in this dissertation give better estimation performance.
Figure 6.7 compares various localization algorithms under network environments with different
randomness (see section 2.3.1). The x-axis denotes the network randomness, and y-axis is the
estimation error. The selected Grid overlaying method is the APIT method by He et al [33], and the
bounding box method is by Savvides et al [8].
The test network contains 100 nodes, and anchor ratio is 20%, radio transmission is 0.2. In this
experiment, we use DV-Hop radio propagation method to estimate the distance between communi-
cating nodes. (The setting in this experiment is different from the original testing environment of the
APIT algorithm (by He [33]) where higher power transmitter is used at anchors, so the estimation
performance for this APIT algorithm is a little worse.)
137
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Randomness
Estimation error
Total nodes: 100, Anchors: 20, Radio range 0.2
MDS
IT?MDS
SA?MDS
APIT
BoundingBox
Lateration
Figure 6.7: Algorithms comparison
From Figure 6.7, we can nd that the SA-MDS algorithm performs better than all other algo-
rithms, and the IT-MDS also achieves better estimation performance at larger deployment random-
ness.
For the test run (20% anchors), we nd that SA-MDS and IT-MDS algorithms present 18%?25%
and 25%?30% estimation error, respectively, independent of the deployment randomness. Compare
with the reported localization performance in literature (see Table 6.1), the proposed localization al-
gorithms in this dissertation do yield better estimation performance.
6.4 Simulation Results for Radio Range Irregularity
This section evaluates four localization algorithms under the irregular radio transmission model:
1) Iteration MDS (IT-MDS) and simulated annealing MDS (SA-MDS) (please, see Section 4.2 in
Chapter 4); 2) bounding box algorithm [8]; and 3) lateration algorithm [30]. A detailed survey on
these algorithms can be found in [76].
138
We will rst introduce the network settings and localization metrics in Section 6.4.1, then we
evaluate in Section 6.4.2 these localization algorithms; and in Section 6.4.3, we assess the same
algorithms using the optimized propagation method.
6.4.1 Network setting and localization metrics
1) Network environment: We randomly deploy 100 nodes in a unit square area. We de ne
the node deployment randomness as the maximum displacement, in terms of radio transmission
range, of each node that can swing from the cross-points of a coordinate grid (also see Section 4.1
in Chapter 4).
2) Estimation error: The estimation error is expressed as a fraction of the maximum radio
range. Let Xi(i = 1;2;:::;n) be the coordinates of n normal nodes where Xi = (xi1;xi2;xi3)T .
If cXi are the estimated coordinates, then the estimation error is given by the Euclidean distance
between Xi and cXi:
err =
Pn
i=1
q
(Xi ?cXi)T(Xi ?cXi)
n?R (6.1)
In the charts at this section, we use the y-axis to denote the estimation error; and use x-axis to
represent network environment conditions, such as anchor ratio or deployment randomness.
6.4.2 Performance under Irregular Radio Networks
In this section, we will evaluate the radio irregularity on the performance of a set of represen-
tative localization algorithms. Speci cally, we analyze these parameters: i) number of sectors or the
number of edge of the polygon N; ii) maximum range attenuation "; and iii) maximum ideal radio
range R.
139
Table 6.2: Estimation errors under various irregular attenuation
IT-MDS SA-MDS Bounding-box Lateration
" = 0 0.2408 0.2330 0.2737 0.2371
" = 0:2 0.2437 0.2465 0.2848 0.2770
" = 0:5 0.3367 0.3091 0.3574 0.3322
Overall localization performance under irregular radio transmission
The overall effects of the radio irregularity on the localization estimation performance are given
in Table 6.2. The testing network includes 20% anchors, the maximum radio transmission rage is 0.2
unit, and node deployment randomness is 0.4. The table shows the location estimation under three
different maximum attenuation. The second row (" = 0) represents the ideal case where the radio is
perfectly circular, and the third and the forth rows give the results with maximum attenuation of 0.2
and 0.5 respectively. We use a regular polygon with 16 edges (16 sectors) to simulate the operating
environment.
It is not surprise that higher attenuation generates larger performance degradation. And the
results agree with the conclusion by He et al. in [33].
In Figure 6.8, we show the estimation results of these algorithms at various anchor ratios. The
x-axis denotes anchor ratio, and y-axis denotes the estimation error. And the four charts denote,
respectively, the simulation results for all four algorithms. The network randomness is 0.4, the edge
of the polygon is 16, and the maximum radio transmission range is 0.2. The results indicate that the
increase of the anchor ratio could remedy the negative effect of the irregular radio transmission.
140
10 15 20 25 30 35 400.1
0.15
0.2
0.25
0.3
0.35
0.4
(a) anchor ratio
estimation error
IT?MDS: Rmax=0.2
Atnmax=0.2
Atnmax=0.5
10 15 20 25 30 35 400.1
0.15
0.2
0.25
0.3
0.35
0.4
(b) anchor ratio
estimation error
SA?MDS: Rmax=0.2
Atnmax=0.2
Atnmax=0.5
10 15 20 25 30 35 400.1
0.15
0.2
0.25
0.3
0.35
0.4
(c) anchor ratio
estimation error
BB: Rmax=0.2
Atnmax=0.2
Atnmax=0.5
10 15 20 25 30 35 400.1
0.15
0.2
0.25
0.3
0.35
0.4
(d) anchor ratio
estimation error
ML: Rmax=0.2
Atnmax=0.2
Atnmax=0.5
Figure 6.8: Maximum attenuation on the performance of localization
Number of Sectors on the Localization Performance
To under the environment determined radio sectors (expressed by the polygon edge number)
on the performance of the localization estimation, we change the sector number of the radio trans-
mission, and we include the results in Figure 6.9. Considering the space limitation, these four charts
are on different network conditions. Figure (a) denotes the simulation results of IT-MDS algorithm
with maximum radio transmission range of 0.2, and the maximum attenuation is 0.2. Figure (c)
represents the estimation of bounding-box algorithm at the network of maximum attenuation of 0.5,
and maximum radio range of 0.3. Figure (b) and Figure (d) are on the same network environment
with maximum radio of 0.2, and maximum attenuation of 0.5 respectively.
141
15 20 25 30 35 400.15
0.2
0.25
0.3
0.35
0.4
0.45
(a) anchor ratio
estimation error
IT?MDS: Rmax =0.2, Atnmax: 0.2
15 20 25 30 35 400.15
0.2
0.25
0.3
0.35
0.4
0.45
(b) anchor ratio
estimation error
SA?MDS: Rmax =0.2, Atnmax: 0.5
15 20 25 30 35 400.15
0.2
0.25
0.3
0.35
0.4
0.45
(c) anchor ratio
estimation error
BB: Rmax=0.3, Atnmax: 0.5
15 20 25 30 35 400.15
0.2
0.25
0.3
0.35
0.4
0.45
(d) anchor ratio
estimation error
ML: Rmax=0.2, Atnmax: 0.5
edge=6
edge=8
edge=16
edge=6
edge=8
edge=16
edge=6
edge=8
edge=16
edge=6
edge=8
edge=16
Figure 6.9: Number of edges on the performance of localization
As it can be seen from the charts, when the maximum attenuation is smaller, larger edge num-
ber will generally gives better location estimation performance (Figure (a)). The reason is straight-
forward in that larger number of edge will give almost regular circular radio transmission shape,
and if attenuation is also small, then the radio coverage is larger and it is closer to the ideal radio
transmission.
On the contrary, when the attenuation is larger, the trend is not so clear ( gure (b), (c), and (d)).
And the results in gure (c) show that the bounding-box method is relatively stable and insensitive
to the edge number.
142
10 15 20 25 30 35 400.1
0.15
0.2
0.25
0.3
0.35
0.4
(a) anchor ratio
estimation error
IT?MDS: Atnmax: 0.2
Rmax=0.2
Rmax=0.3
10 15 20 25 30 35 400.1
0.15
0.2
0.25
0.3
0.35
0.4
(b) anchor ratio
estimation error
SA?MDS: Atnmax: 0.5
Rmax=0.2
Rmax=0.3
10 15 20 25 30 35 400.1
0.15
0.2
0.25
0.3
0.35
0.4
(c) anchor ratio
estimation error
BB: Atnmax: 0.5
Rmax=0.2
Rmax=0.3
10 15 20 25 30 35 400.1
0.15
0.2
0.25
0.3
0.35
0.4
(d) anchor ratio
estimation error
ML: Atnmax: 0.5
Rmax=0.2
Rmax=0.3
Figure 6.10: Maximum radio range on the performance of localization
Maximum radio range on the estimation performance
Figure 6.10 gives the location estimation of the four algorithms at two different maximum
radio transmission ranges. The x-axis represents the anchor ratio, and the solid line with circle,
and the dotted line with rectangle denote, respectively, the results at maximum radio of 0.2 and 0.3.
We use 16 edges in this simulation. It is clear that larger maximum radio range will result smaller
estimation error.
6.4.3 Optimized Propagation on Real Networks
In this section, we show the location estimation results using original and optimized propaga-
tion methods for the four methods. In the simulation, we x the anchor ratio at 20%, and change
the randomness from 0.2 to 1.0 (x-axis). The maximum radio transmission is set to 0.2, and the
143
0.2 0.4 0.6 0.8 10.2
0.25
0.3
0.35
0.4
0.45
(a) randomness
estimation error
IT?MDS
0.2 0.4 0.6 0.8 10.2
0.25
0.3
0.35
0.4
0.45
(b) randomness
estimation error
SA?MDS
0.2 0.4 0.6 0.8 10.2
0.3
0.4
0.5
0.6
0.7
(c) randomness
estimation error
BB
0.2 0.4 0.6 0.8 10.2
0.3
0.4
0.5
0.6
0.7
(d) randomness
estimation error
ML
opt
nml
Figure 6.11: Radio propagation optimization on the performance of localization
maximum attenuation is 0.5. The results are given in Figure 6.11. The results using the optimized
propagation method are given in solid line with circles (legend opt) and the results using the DV-Hop
method is given in dotted lines with rectangles (legend nml).
The results indicate that the localization performance degrades when the deployment random-
ness increases. If the optimized propagation method is used, the estimation performance for all
four algorithms is improved. And the average improvements for these four algorithms are 17.72%,
24.69%, 10.67% and 5.33%, respectively.
144
CHAPTER 7
CONCLUSIONS
This dissertation researches the wireless localization problem, and proposes realistic localiza-
tion mechanisms for both the indoor and outdoor environments. For the indoor localization re-
search, the dissertation introduces a new and automated localization tool called ARIADNE. For the
outdoor localization analysis, the dissertation presents two multidimensional scaling (MDS) based
algorithms: the iterative MDS and simulated-annealing MDS. Additionally, a realistic radio range
irregularity (RRI) model is proposed in order to provide real operating test-beds for the wireless
research community.
7.1 Indoor Localization Research Conclusion
The dissertation presents a new and automated indoor localization system: ARIADNE. The
system contains two modules: Signal strength map construction and location search.
In the signal strength map construction module, a new radio propagation model is derived to
enable the creation of the signal strength map for an entire building with minimal manual inter-
vention. The scalable algorithm generates a signal strength map with high accuracy and thus can
be easily deployed to construct these maps for indoor premises. The time varying nature of the
propagation characteristics of the wireless channel poses problems to a signal strength table created
manually. This is because, even though such a table is accurate at a given instant of time, it can
be rendered useless at another instant. The map generation module presented in this dissertation
145
enables the creation, on a demand basis, of a signal strength map automatically and almost instan-
taneously. The resulting map is comparable in accuracy to that of a signal strength map manually
collected at that instant of time.
In the localization search module, a clustering-based localization algorithm is developed to
search the inaccurate signal strength map . Simulation results at two different buildings validate the
algorithms and procedures used in ARIADNE. In addition, if position history information is to be
used, the localization performance for a mobile user is signi cantly improved.
During the research in the indoor localization system, it was found that many parameters could
affect the localization performance. These parameters include: 1) sniffers deployment con gura-
tion, 2) number of available sniffers, 3) signal strength map resolution, 4)furniture modelling, and
5)special building structure modelling. We have found that the following mechanisms could poten-
tially improve the localization performance:
1. Triangular (i.e. not aligned) deployment of the sniffers maximizes the discrimination of the
signal strength triplet in the signal strength map table;
2. The deployment of extra sniffers improves the localization performance;
3. The sniffer deployment should consider the maximum signal strength coverage for the esti-
mated location. Additionally, it is better to cover the important position within the triangular
surface of an equilateral triangle formed by three sniffers. Additionally, the semi-grid sniffers
deployment for large building is optimal;
4. Higher resolution of the signal strength map table improves the localization precision;
146
5. Large furniture, like bookshelf, affects the indoor radio propagation; thus, a simple method
is to model them as additional walls. This will improves the localization performance if no
other mechanisms is available;
6. To model the construction columns as additional walls, in two directions and according to the
thickness of the columns, helps the localization performance; however, the material property
of the column may be different from general indoor partitions.
Thus, the localization precision of the indoor system really depends on many parameters. It is
generally not appropriate to evaluate or to compare the performance of various indoor localization
systems only based on the best reported performance, which may depend on some test-bed with
particular sniffer con gurations.
7.2 Outdoor Localization Research Conclusion
For the outdoor localization research, this dissertation proposes two algorithms, IT-MDS and
SA-MDS, to enable nodes in a wireless network to estimate their positions. Both methods are based
on a combination of multidimensional scaling method and lateration method. Speci cally, IT-MDS
algorithm considers the radio communication constraints, and dynamically adjust node?s positions
during each iteration. SA-MDS algorithm, on the other hand, mimics the way of a metal cooling
down procedure, and optimally locates the nodes in their most likely positions.
If DV-Hop is used, both algorithms are insensitive to the 1-hop range measurement errors.
With extensive simulation runs, results show that both algorithms provide accurate and consistent
estimates no matter how precise each single estimate is. The average estimation errors are roughly
bounded within 40% if a network contains more than 10% anchors and 0.2 radio range is used.
147
With same network settings, the research compares the proposed algorithms with other existing
representation algorithms, the results indicate that the proposed methods yield better estimation
performance.
Together with the localization research, this dissertation also introduces a realistic radio ir-
regularity model in order to provide a realistic test-bed for the wireless research. With the model,
the research analyzes the real irregular routing properties as well as the potential effects of the
model on the distributed localization algorithms. To improve the localization performance, the dis-
sertation proposes a constrained-greedy forwarding radio propagation method to identify a regular
routing path under complex operating environments. Through extensive simulation, the dissertation
points out that although realistic (irregular) radio greatly degrades the performance of most local-
ization algorithms, optimal localization is still possible if more anchors are deployed, and/or if the
constrained-greedy forwarding radio propagation method is adopted.
148
BIBLIOGRAPHY
[1] N. Bulusu, J.Heidemann, and D. Estrin. GPS-less Low Cost Outdoor Localization for Very
Small Devices. IEEE Personal COmmunications Magazine, 7(5):28 34, Oct. 2000.
[2] P. Bahl and V. Padmanabhan. RADAR: An In-Building RF-Based User Location and Track-
ing System. Proc. IEEE Infocom 200, pages 775 784, 2000.
[3] Yongguang Chen and Hisashi Kobayashi. Signal Strength Based Indoor Geolocation. In
Communications, 2002. ICC 2002. IEEE International Conference on. Communications,
2002. ICC 2002. IEEE International Conference on, May 2002.
[4] Didier Chincholle, Mikael Eriksson, and Alex Burden. Location-sensitive services: it?s now
ready for prime time on cellular phones! In Proceedings of the conference on Designing
interactive systems, pages 331 334. ACM Press, 2002.
[5] A. Haeberlen, E. Flannery, A. M. Ladd, A. Rudys, D. S. Wallach, and L. E. Kavraki. Practical
Robust Localization over Large-Scale 802.11 Wireless Networks. In MobiCom, Sept 2004.
[6] Dragos Niculescu and Badri Nath. VOR Base Stations for Indoor 802.11 Positioning. In
MobiCom?04. ACM, Oct. 2004.
[7] Chris Savarese. Robust positioning algorithms for distributed ad-hoc wireless sensor net-
works. Master?s thesis, Berkeley, 2002.
[8] A. Savvides, H. Park, and M. B. Srivastava. The n-hop multilateration primitive for node
localization problems. Journal of Mobile Networks and Applications (MONET), 8:443 451,
2003.
[9] Xiang Ji and Hongyuan Zha. Sensor positioning in wireless ad-hoc sensor networks using
multidimensional scaling. In IEEE INFOCOM, 2004.
[10] Lingxuan Hu and David Evans. Localization for Mobile Sensor Networks. In MobiCom?04.
ACM, Sept 2004.
[11] Dragos Niculescu and Badri Nath, editors. Ad Hoc Positioning System (APS) using AoA, San
Francisco, CA, 2003. IEEE INFOCOM.
[12] Alex Hills, Jon Schlegel, and Ben Jenkins. Estimating Signal Strengths in the Design of an
Indoor Wireless Network. IEEE Trans. on Wireless Communications, 3(1), Jan. 2004.
[13] P. Krishnan, A.S. Krishnakumar, Wenhua Ju, C. Mallows, and S. Ganu. A System for
LEASE: System for Location Estimation Assisted by Stationary Emitters for Indoor Wireless
Networks. In Proceedings of IEEE Infocom 2004, Hong Kong, March 2004.
149
[14] Ahmad Hatami and Kaveh Pahlavan. In building Intruder Detection for WLAN Access.
Position Location and Navigation Symposium, 2004, PLANS 2004, pages 592 597, April
2004.
[15] S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak. Exposure in wireless ad hoc
sensor networks. In In International Conference on Mobile Computing and Networking (Mo-
biCom?01), pages 139 150, Rome, Italy, July 2001.
[16] T. Yan, T. He, and J.A. Stankovic. Differentiated surveillance service for sensor networks.
In Proceeding of First ACM Conference on Embedded Networked Sensor Systems (SenSys
2003), Los Angeles, CA, 2003.
[17] M. Ancona, S. Locati, and A. Romagnoli. Context and location aware textual data input.
In Proceedings of the 2001 ACM symposium on Applied computing, pages 425 428. ACM
Press, 2001.
[18] Keith Cheverst, Nigel Davies, K. Mitchell, and A. Friday. Mobile-awareness: designing for
mobile interactive systems. ACM SIGGROUP Bulletin archive, 22:8 11, April 2001.
[19] Alan Dix, T. Rodden, N. Davies, J. Trevor, A. Friday, and K. Palfreyman. Exploiting space
and location as a design framework for interactive mobile systems. ACM Transactions on
Computer-Human Interaction (TOCHI), in press., 7(3):285 321, Sep. 2000.
[20] Eija Kaasinen. User needs for location-aware mobile services. Personal Ubiquitous Com-
puting, 7(1):70 79, 2003.
[21] K. Cheverst, N. Davis, K. Mitchell, and A. Friday adn C. Efstreatiou. Developing a context-
aware electronic tourist guide: some issues and experiences. In Proceedings of the conference
on Handheld and Ubiquitous Computing (HUC?00), 2000.
[22] D.C. Steere, A. Baptista, D. McNamee, C. Pu, and J. Walpole. Research challenges in envi-
ronmental observation and forecasting systems. In Proceedings of the sixth annual interna-
tional conference on Mobile computing and neting, pages 292 299. ACM Press, 2000.
[23] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao. Habitat monitoring:
application driver for wireless communications technology. In Proceedings of the ACM SIG-
COMM Workshop on Data Communications, pages 20 41, 2001.
[24] H. Wang, J. Elson, L.Girod, D. Estrin, and K. Yao. Target classi cation and localizaiton in
habitat monitoring. In Proceedings of the IEEE ICASSP 2003, Hong Kong, April 2003.
[25] P. Boettcher, J. A. Sherman, and G. A. Shaw. Target localization using acoustic time-
difference of arrival in distributed sensor networks. In Proceedings of SPIE 47th Annual
Meeting, 2002.
[26] E. Howden. Networked sensors for the objective force. In Proceedings of SPIE 47th Annual
Meeting, 2002.
150
[27] R.L.Moses, D. Krishnamurthy, and R. Patterson. An auto-calibration method for unattended
ground sensors. In Proc. ICASSP, pages 2941 2944, May 2002.
[28] M.R. Perlman and Z.J. Haas. Determining the optimal con guration for the zone routing
protocol. IEEE Journal on Selected Areas in Communications, 17(8):1395 1414, Aug. 1999.
[29] Y.B. Ko and N.H. Vaidya. Geotora: A protocol for geocasting in mobile ad hoc networks.
Proceedings of IEEE ICNP 2000, pages 240 250, Nov. 2000.
[30] Chris Savarese, K. Langendoen, and J. Rabaey. Robust positioning algorithms for distributed
ad-hoc wireless sensor networks. Proceedings of the General Track: 2002 USENIX Annual
Technical Conference, pages 317 327, 2002.
[31] K. Premaratne, J. Zhang, and M. Doguel. Location Information-Aided Task-Oriented Self-
Organization of Ad-Hoc Sensor Systems. IEEE sensors Journal, 4(1), Feb. 2004.
[32] M. L. Sichitiu, V. Ramadurai, and P. Peddabchagari. Simple algorithm for outdoor local-
ization of wireless sensor networks with inaccurate range measurements. In Proceedings of
the International Conference of Wireless Networks, Las Vegas, Nevada, USA, June 2003.
CSREA Press 2003.
[33] Tian He, Chengdu Huang, Brian M. Blum, John A. Stankovic, and Tarek Abdelzaher. Range-
free location schemes for large scale sensor networks. MobiCom?03, Sep. 2003.
[34] Radhika Nagpal, H. Shrobe, and J. Bachrach. Organizing a global coordinate system from
local information on an ad hoc sensor network. IPSN?03, April 2003.
[35] Radhika Nagpal. Organizing a global coordinate system from local information on an amor-
phous computer. A.I. Memo 1666, Aug. 1999.
[36] D. Niculescu and B. Nath. Localized positioning in ad hoc networks. IEEE SNPA 2003, May
2003.
[37] S. Capkun, M. Hamdi, and J.-P. Hubaux. GPS-free positioning in mobile ad-hoc networks.
Cluster Computing, 5(2), April 2002.
[38] Vaidyanathan Ramadurai and M. L. Sichitiu. Localization in wireless sensor networks: A
probabilistic approach. In Proc. of the 2003 International Conference on Wireless Networks
(ICWN 2003), pages 275 281, Las Vegas, NV, June 2003.
[39] Gang Zhou, Tian He, S. Krishnamurthy, and J. A. Stankovic. Impact of Radio Irregularity
on Wireless Sensor Networks. In Proceedings of the 2nd international conference on Mobile
systems, applications, and services, June 2004.
[40] K. Pawlikowski, H.-D.J. Jeong, and J.-S.R.; Lee. On credibility of simulation studies of
telecommunication networks. Communications Magazine, IEEE, 40:132 139, Jan 2002.
151
[41] David Kotz, C. Newport, R. S. Gray, J. Liu, Y. Yuan, and C. Elliott. Experimental Eval-
uation of Wireless Simulation Assumptions. In Proceedings of the 7th ACM international
symposium on Modeling, analysis and simulation of wireless and mobile systems, October
2004.
[42] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins. Global Positioning System: Theory
and Practice. Springer-Verlag, 4th edition, 1997.
[43] W. Kumm. GPS Global Positioning System. Bielefeld, Germany:Klasing, 1995.
[44] Jacek Czajewski. The accuracy of the global positioning systems. IEEE Instrumentation &
Measurement Magazine, 2004.
[45] Robin Strahan. Location sensing technologies. In Report No. e-mc2.2.1.1.2002, Department
of Computer Science, University, 2002.
[46] web. http://www.tycoelectronics.com/gps.
[47] web. http://europa.eu.int/comm/dgs/energy transport/galileo/index en.htm.
[48] web. http://www.gps-practice-and-fun.com/a-gps.html.
[49] R. Want, A. Hopper, V. Falcao, and J. Gibbons. The Active badge Location Systems. ACM
Transactions on Information Systems, 10(1):91 102, Jan. 1992.
[50] R. Ward, A. Jones, and A. Hopper. A New Location Technique for the Active Of ce. IEEE
Personal Communications, 4(5):42 47, Oct. 1997.
[51] A. Ward. Sensor-driven Computing. PhD thesis, Cambridge University, U.K., May 1999.
[52] N.B. Priyantha, A. Chakraborty, and H. Balakrishnan. The cricket location-support system.
Proceedings of MOBICOM?00, Aug. 2000.
[53] Ascension technology corporation, http://www.ascension-tech.com.
[54] J. Krumm, S. Harris, B. Meyers, B. Brumitt, M. Hale, and S. Shafer. Multi-camera multi-
person tracking for EasyLiving. In Third IEEE International Workshop on Visual Surveil-
lance, Dublin, Ireland, July 2000.
[55] Homayoun Hashemi. The indoor radio propagation channel. Proceedings of the IEEE, 81(7),
July 1993.
[56] D. Molkdar. Review on radio propagation into and within buildings. Microwaves, Antennas
and Propagation, 138:61 73, Feb 1991.
[57] Theodore S. Rappaport. Wireless Communications: Principles and Practice. Prentice Hall,
1996.
152
[58] M. Hassan-Ali and K. Pahlavan. A new statistical model for site-speci c indoor radio prop-
agation prediction based on geometric optics and geometric probability. Wireless Communi-
cations, IEEE Transactions on, 1:112 124, Jan. 2002.
[59] Supachai Phaiboon. An Empirically Based Path Loss Model for Indoor Wireless Channels
in Laboratory Building. In Proceedings of IEEE TENCON?02, 2002.
[60] M. Lott and I. Forkel. A multi-wall-and- oor model for indoor radio propagation. Vehicular
Technology Conference, IEEE, 1:464 468, May 2001.
[61] Paramvir Bahl, V.N. Padmanabhan, and A. Balachandran. Enhancements to the RADAR
User Location and Tracking System. Technical report, Microsoft Research, WA 98052, Feb.
2000.
[62] P. Prasithsangaree, P. Krishnamurthy, and P.K. Chrysanthis. On indoor position location with
wireless LANs. In Personal, Indoor and Mobile Radio Communications, 2002. The 13th
IEEE International Symposium on, pages 720 724, Sept. 2002.
[63] Santosh Pandey, B. Kim, F. Anjum, and P. Agrawal. Client assisted location data acquisition
scheme for secure enterprise wireless networks. In IEEE WCNC 2005, 2005.
[64] Ankur Agiwal, Parakram Khandpur, and Huzur Saran. Locator: location estimation system
for wireless lans. In Proceedings of the 2nd ACM international workshop on Wireless mobile
applications and services on WLAN hotspots, Oct. 2004.
[65] Andrew M. Ladd, Kostas E. Bekris, Algis Pl Rudys, Dan S. Wallach, and Lydia E. Kavraki.
On the Feasibility of Using Wireless Ethernet for Indoor Localization. June 2004.
[66] Y. Oshman and P. Davidson. Optimization of observer trajectories for bearings-only target
localization. IEEE Transactions on Aerospace and Electronic Systems, 35:892 992, 1999.
[67] D. Niculescu and B. Nath. Ad-hoc positioning system (APS). In GLOBECOM 2001, San
Antonio, Nov. 2001.
[68] Andreas Savvides, Chih-Chieh Han, and Mani B. Strivastava. Dynamic ne-grained local-
ization in ad-hoc networks of sensors. In MOBICOM, Rome, Italy, 2001.
[69] A. Savvides, H. Park, and M. Srivastava. The bits and ops of the n-hop multilateration
primitive for node location problems. First ACM International Workshop on Wireless Sensor
Networks and Application (WSNA), pages 112 121, 2002.
[70] Jeffrey Hightower and Gaatano Boriello. Localization systems for ubiquitous computing.
IEEE Computer Magazine, 34(8):57 66, August 2001.
[71] Joshua A. Tauber. Indoor location systems for pervasive computing. Technical report, MIT,
August 2002.
153
[72] Lance Doherty, Kristofer S. J. Pister, and Laurent E. Ghaoui. Convex position estimation in
wireless sensor netowrks. Proc. of IEEE Inforcom, 3:1655 1663, 2001.
[73] A. Savarese, J. Rabaey, and J. Beutel. Locationing in distributed ad-hoc wireless sensor
networks. In IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP), pages 2037 2040, May 2001.
[74] X. Ji and H. Zha. Multidimensional scaling based sensor positioning algorithms in wireless
sensor networks. In Proceedings of the 1th Annual ACM Conference on Embedded Networked
Sensor Systems, pages 328 329, Nov. 2003.
[75] T. He, J. A. Stankovic, and T.F. Abdelzaher. Speed: A Stateless Protocol for Real-Time
Communication in Sensor Networks. Proceedings of IEEE ICSCS?03, May 2003.
[76] Saad Biaz and Yiming Ji. A Survey and comparison on localisation algorithms for wireless
ad hoc networks. International Journal of Mobile Communications (IJMC), 3(4):374 410,
2005.
[77] Saad Biaz and Yiming Ji. Precise Distributed Localization Algorithms forWireless Networks.
In IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks,
(IEEE WoWMoM 2005). IEEE, June 2005.
[78] K. Langendoen and N. Reijers. Distributed location in wireless sensor networks: A quantita-
tive comparison. Computer Networks, 43:499 518, 2003.
[79] K. Kleinrock and J. Silvester. Optimum tranmission radii for packet radio networks or why
six is a magic number. In in National Telecommunications Conference, pages 4.3.1 4.3.5,
Birmingham, Alabama: IEEE, Dec. 1978.
[80] G. Young and A.S. Householder. A note on multidimensional psycho-physical analysis. In
Psychometrika, 6, pages 331 33, 1941.
[81] L. Guttman. A new approach to factor analysis: the radex. in p. lazarsfeld (ed.). In Mathe-
matical thinking in the behavioral sciences, New York:Free Press, 1954.
[82] T.F. Cox and M.A.A. Cox. Multidimensional scaling. London: Chapman Hall, 1994.
[83] I. Brog and P. groenen. Modern multidimensional scaling: Theory and applications. New
York: Springer, 1997.
[84] Trevor F. Cox and Michael A.A. Cox. Multidimensional Scaling. Chapman and HallCRC, 2
edition, 2001.
[85] G. Young and A.S. Householder. Discussion of a set of points in terms of their mutual
distances. Psychometrika, 3:19 22, 1938.
154
[86] I.J. Schoenberg. Remarks to maurice frechet?s article sur la de nition axiomatique d?une
classe d?espaces vectoriels distancies applicables vectoriellement sur l?espaace de hilbert .
Annals of Maththematics, 36:724 732, 1935.
[87] D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex Be-
havior at Scale: An Experimental Study of Low-Power Wireless Sensor Networks. Technical
report, Technical Report UCLA/CSD-TR 02-0013, 2002.
[88] Zhong Ji, Bing-Hong Li, Hao-XIng Wang, Hsing-Yi Chen, and Tapan K. Sarkar. Ef cient
Ray-Tracing Methods for Propagation Prediction for Indoor Wireless Communications. In
IEEE Antennas and Propatation Magazine, volume 43, April 2001.
[89] H. Kim and H. Ling. Electromagnetic scattering from an inhomogeneous object by ray
tracing. IEEE Trans. Antennas Propagat., 40:517 525, May 1992.
[90] Reinaldo A. Valenzuela. Ray tracing prediction of indoor radio propagation. In Personal,
Indoor and Mobile Radio Communications, 1994. 5th IEEE International Symposium on
Wireless Networks - Catching the Mobile Future., Sept. 1994.
[91] Chang-Fa Yang, Boau-Cheng Wu, and Chuen-Jyi Ko. A Ray-Tracing Method for Modeling
Indoor Wave Propagation and Penetration. IEEE Transaction on Antennas and Propagation,
46(6), June 1998.
[92] A. Falsa , K. Pahlavan, and G. Yang. Transmission Techniques for Radio LAN?s - A Com-
parative Performance Evaluation Using Ray Tracing. IEEE J. on Sel. Areas in Comm.,
14(3):477 491, April 1996.
[93] M. Lott. On the performance of an Advanced 3D Ray Tracing Method. In Proc. of European
Wireless & ITG Mobile Communication, Oct. 1999.
[94] Henry L. Bertoni, Walter Honcharenko, L.R. Maciel, and H. Xia. UHF propagation predic-
tion for wireless personal communications. Proc. IEEE, 82:1333 1359, Sept. 1994.
[95] G. German, Q. Spencer, L. Swindlehurst, and R. Valenzuela. Wireless indoor channel mod-
eling: statistical agreement of ray tracing simulations and channel sounding measurements.
Acoustics, Speech, and Signal Processing, 2001. Proceedings, IEEE Int. Conf. on, 4, May
2001.
[96] N. Metropolis, A.W. Rosenbluth, M. N. Rosenbluth, A.H. Teller, and E. Teller. Equations of
state calculations by fast computing machines. J. Chem. Phys., 21:1087 1092, 1958.
[97] K.A. Dowsland. Simulated annealing. In C. R. Reeves, editor, Modern Heuristic Techniques
for Combinatorial Problems, chapter 2. McGraw-Hill Book Company, Berkshire, 1995.
[98] S. Kirkpatrick, C. D. Gelatt, and M.P. Vecchi. Optimization by Simulated Annealing. Sci-
ence, 220(4598), May 1983.
155
[99] S.C. Johnson. Hierarchical Clustering Schemes. Psychometrika, 2:241-254, 1967.
[100] J. B. MacQueen. Some Methods for classi cation and Analysis of Multivariate Observa-
tions. In Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probabil-
ity, pages 1:281 297. Berkeley, University of California Press, 1967.
[101] Vijay Abhijit, Carla Ellis, and Xiaobo Fan. Experiences with an Inbuilding Tracking System.
In PIMRC, 2003.
[102] Saad Biaz and Yiming Ji. Precise Distributed Localization Algorithms forWireless Networks.
Technical Report CSSE05-02, Auburn University, March 2005.
[103] Robin Sibson. Studies in the Robustness of Multidimensional Scaling: Perturbational Anal-
ysis Classical Scaling. Journal of the Royal Statistical Society. Series B (Methodological),
41(2):217 229, 1979.
[104] R.A. Valenzuela, S. Fortune, and J. Ling. Indoor propagation prediction accuracy and speed
versus number of re ections in image-based 3-D ray-tracing. 48th IEEE Vehicular Technol-
ogy Conferernce, 1:539 543, May 1998.
[105] S. Ganu, A.S. Krishnakumar, and P. Krishnan. Infrastructure-based Location Estimation
in WLAN Networks. IEEE Wireless Communications and Networking Conference (WCNC
2004), 1:465 470, March 2004.
156