MCJQfcflSITV OF MORATUWA. SRI LANK.. 
~ " ftflORATUWA 
Integrat ion of F ingerpr int ing and Tri laterat ion A lgor i thms 
for 
I m p r o v e d Indoor Local izat ion 
Integration of Fingerprinting and Trilateration Algorithms 
for Improved Indoor Localization 
This dissertation was submitted to the Department of Electronic & 
Telecommunication Engineering, University of Moratuwa in partial fulfillment of 
the requirements for the 
Degree of M.Sc. in Telecommunications 
Department of Electronic & Telecommunication Engineering 
University of Moratuwa 
Supervisor 
Prof. Dileeka Dias 
Nilushika Shironi Kodippili *G2.t - 3 ^ | QO^^) 
June, 2010 
University of Moratuwa 
1 0 2 8 7 4 
102874 
DECLARATION 
I certify that this dissertation does not incorporate without 
acknowledgement any material previously submitted for a degree in any 
University to the best of my knowledge and believe that it does not 
contain any material previously published, written or orally 
communicated by another person or myself except where due reference is 
made in the text. I also hereby give consent for my dissertation, i f 
accepted, to be made available for photocopying and for inter-library 
loans, and for the title and summary to be made available to outside 
organizations. 
Signature of the Candidate 
Date: June, 2010 
To the best of my knowledge, the above particulars are correct. 
Supervisor 
in 
ABSTRACT 
Integration of Fingerprinting and Trilateration Algorithms for 
Improved Indoor Localization 
Nilushika Shironi Kodippili , Dept. of Electronic and Telecommunicat ion Engineering 
Supe rv i so r : Prof. Dileeka Dias 
K e y w o r d s : Indoor localization, positioning algorithm, positioning accuracy, 
performace indicators, commercial applications, fingerprinting, trilateration, 
deployment, radio propagation 
Many useful commercial , educational, security and health-care applications of 
location-awareness related to navigation, tracking and detection of people and objects 
have been developed through out the history. However the demand for the location 
information has been limited to outdoor applications until many indoor localization 
requirements appeared recently with the emergence of ubiquitous computing. 
The indoor applications inherently call for higher positioning accuracy than those of 
outdoor. The existing sophisticated outdoor localization techniques like A-GPS do not 
perform satisfactorily in indoors due to the poor satellite signal coverage and the 
signal propagation complexities in indoor environments. On the other hand, though a 
number of different indoor techniques have been implemented and tested hitherto, 
none of those techniques have displayed satisfactory overall performance adequate for 
large scale deployment of commercial applications. 
The key performance indicator of positioning techniques is the positioning accuracy, 
which is quantified in terms of error distance. This research was focused on 
integrating two existing basic positioning algorithms, fingerprinting and trilateration, 
with a view to improving the performance with respect to positioning accuracy as 
well as cost, complexity, response time and implementation aspects etc. 
The fingerprinting has been used to identify few locations of known coordinates and 
signal strengths, closer to the target location. The final position estimation is done by 
applying the trilateration technique over the range between the selected known 
locations and the target location. The signal propagation model employed in this 
technique reproduces the real signal propagation behaviour accurately since it is 
being applied over a short range and hence the distances calculated using the signal 
propagation model are fairly accurate. Consequently a better estimation of the 
location can be derived without getting affected by typical practical problems 
associated with unpredictable nature inherent to the radio signal propagation. 
This research thesis describes the design and implementation of the proposed 
integrated algorithm in an indoor W L A N environment to evaluate its performance in 
comparison with the basic techniques it is derived from. The proposed technique 
estimates the location of an object accurately within 1.1 m in less than a second with 
manageable training grid size at almost no additional cost. The overall satisfactory 
performance suitable for generic commercial applications demonstrated by the 
proposed technique could be a good foundation for ubiquitous deployment of indoor 
localization applications. 
iv 
4 
DEDICATION 
To all who encouraged me to pursue my higher studies 
v 
ACKNOWLEDGEMENTS 
I am grateful to my close friends Walpola, Sandamalee, Kasuni and Ganesh, those 
who emphasized that I should pursue my higher studies in parallel to busy office 
schedules I have been involved with in relation to my job at Sri Lanka Telecom. 
I express my gratitude to management of Sri Lanka Telecom who released me on 
Fridays on study leave to attend to lectures conducted at university of Moratuwa 
during the first academic year of the MSc degree course. 
I thank my colleagues in the MSc batch, Amritha, Anagi. Deviga, Damith and 
Sameera who shared the knowledge and valuable resources with me during the entire 
t ime period of studies. 
My heartfelt gratitude is expressed to Prof. Dileeka Dias who has been my favourite 
teacher since my undergraduate studies though she is unaware of it, for her kindness, 
support, understanding which put me on the right track from time to time. She has 
been a great backup throughout all this time for successfully completing the course 
requirements as well as the research work under her supervision. I am still amazed 
about her humbleness and humanity. I wonder being such a highly reputed intellectual 
in the country bound by a tight routine how down to earth she is and how easily she 
spares her valuable time answering our problems. 
I sincerely thank my teachers at university of Moratuwa, specially Dr. Pasqual, Mr. 
Kithsiri Samarasinghe and Dr. Thilakumara who extended their helping hands 
whenever needed. 
1 convey my special thanks to Prof. Mrs. Dayawanse, though she did not directly 
involve with my post graduate studies, who extended her kind wishes and 
encouragements from the time she provided a recommendation on me for the 
enrolment to MSc course to date whenever I met her on the way. 
I thank and much appreciate the non-academic staff of the department, who always 
provided their fullest support in every matter their help was needed in such a cordial 
VI 
manner which is not a behaviour frequently found in typical government office 
environment. 
Kasun Pathirana who I convey my special thanks to, has been more a brother than a 
friend who helped me with the development of the software application related to my 
research work. 
I appreciate my good friends Nadira, Bindu, Kosala and Thusitha those who inquired 
on the progress of my studies and the research work from time to time and 
encouraged me to complete the MSc degree. 
Finally it is with deepest gratitude and love that I remember my parents, the two 
sisters and younger brother for all their love, dedication and support on my education 
all over the time without which I would not have been in this position today. 
vii 
TABLE OF CONTENTS 
DECLARATION Ill 
ABSTRACT IV 
DEDICATION V 
ACKNOWLEDGEMENTS VI 
TABLE OF CONTENTS VIII 
LIST OF FIGURES XIII 
LIST OF TABLES XV 
INTRODUCTION 1 
1.1 B a c k g r o u n d 1 
1 .2 L i t e r a t u r e S u r v e y 2 
± 1.3 P e r f o r m a n c e I n d i c a t o r s 5 
1 .3 .1 Accuracy 5 
1 . 3 . 2 Precision 6 
1 . 3 . 3 Cost 6 
1 . 3 . 4 Ease of deployment 7 
1 .3 .5 Complexity 7 
1 . 3 . 6 Response time 7 
1 . 3 . 7 Efficiency 7 
1 . 3 . 8 Scalability 8 
1 . 3 . 9 Availability 8 
1.4 S c o p e o f t h e R e s e a r c h 8 
1.5 I m p l e m e n t a t i o n o f t h e P r o p o s e d A l g o r i t h m 9 
1.6 O u t c o m e 1 2 
1.7 O r g a n i z a t i o n o f t h e T h e s i s 1 3 
POSITIONING TECHNIQUES AND SYSTEMS 14 
2 .1 I n t r o d u c t i o n 1 4 
2 . 2 G l o b a l P o s i t i o n i n g S y s t e m (GPS) 1 4 
2 . 3 W L A N B a s e d L o c a l i z a t i o n T e c h n i q u e s 1 4 
viii 
r 
2.3.1 Cell Identification 15 
2.3.1.1 Functionality 15 
2.3.1.2 Performance 15 
2.3.2 Trilateration 16 
2.3.2.1 Functionality 16 
2.3.2.1.1 Signal propagation model 18 
2.3.2.2 Performance 19 
2.3.3 Fingerprinting 20 
» 2.3.3.1 Functionality 20 
2.3.3.1.1 KNN algorithm 21 
2.3.3.2 Performance 22 
2.3.4 Neural Networks 23 
2.3.4.1 Functionality 23 
2.3.4.2 Performance 24 
2.3.5 Robot Localization 24 
A. 
2.3.5.1 Functionality 24 
» 2.3.5.1.1 Global localization 25 
2.3.5.1.2 Pose maintenance 26 
2.3.5.2 Performance 27 
2.4 I m p r o v e m e n t s t o l o c a t i o n f i n g e r p r i n t i n g a l g o r i t h m 28 
2.4.1 KWNN (K weighted nearest neighbours, k>=2) 28 
2.4.2 Viterbi-like algorithm for continuous user tracking 28 
2.4.3 AP based environmental profiling scheme 30 
2.4.4 Radio Map Locations Clustering 31 
2.4.4.1 Explicit Clustering (Joint Clustering) 31 
2.4.4.2 Implicit Clustering (Incremental Triangulation algorithm) 31 
2.4.5 Light AP 32 
2.4.6 Extension to 3D space 32 
2.4.7 Interpolated Map Grid (IMG) 33 
2.4.8 Hybrid method of fingerprinting and trilateration 33 
2.5 WLAN B a s e d L o c a t i o n S u p p o r t S y s t e m s 34 
2.5.1 RADAR 35 
2.5.2 The Horus System 35 
IX 
2 . 5 . 3 3 D - i D (Pin-Point) RF Tag System 3 5 
2 . 5 . 4 The Daedalus project 3 6 
2 . 6 C e l l u l a r M o b i l e N e t w o r k s B a s e d L o c a t i o n S u p p o r t S y s t e m s 3 6 
2 . 6 . 1 Place Lab system 3 7 
2 . 7 I n f r a r e d B a s e d L o c a t i o n S u p p o r t S y s t e m s 3 7 
2 . 7 . 1 Active Badge 3 7 
2 . 8 U l t r a s o u n d B a s e d L o c a t i o n S u p p o r t S y s t e m s 3 8 
2 . 8 . 1 Cricket 3 8 
2 . 8 . 2 Active Bat 3 9 
2 . 9 O t h e r c o m m e r c i a l s y s t e m s 3 9 
2 . 9 . 1 SpotON 3 9 
2 . 9 . 2 Easy Living 3 9 
2 . 9 . 3 Smart Floor 4 0 
2 . 9 . 4 Motion Star 4 0 
PROPOSED POSITIONING ALGORITHM 41 
3 .1 O v e r v i e w 4 1 
3 . 2 I n i t i a l A p p r o x i m a t i o n o f t h e L o c a t i o n 4 1 
3 . 3 F r a m e w o r k f o r t h e F i n a l L o c a t i o n E s t i m a t i o n 4 2 
3 . 4 F i n a l E s t i m a t i o n o f L o c a t i o n 4 4 
3 . 4 . 1 Event no. 1 4 6 
3 . 4 . 1 . 1 Event no. i 4 7 
3 . 4 . 1 . 2 Event no.s ii, iii and v 4 8 
3 . 4 . 1 . 3 Event no.s iv, vi and vii 4 9 
3 . 4 . 1 . 4 Event no. viii 5 0 
3 . 4 . 2 Event no.s 2 , 3 and 5 5 1 
3 . 4 . 2 . 1 Event no. i 5 1 
3 . 4 . 2 . 2 Event no. ii and iii 5 2 
3 . 4 . 2 . 3 Event no. iv 5 3 
3 . 4 . 3 Event no.s 4 , 6 and 7 5 3 
3 . 4 . 3 . 1 Event no. i 5 4 
3 . 4 . 3 . 2 Event no. ii 5 5 
3 . 4 . 4 Event no.8 5 5 
X 
3.5 O t h e r I m p l e m e n t e d A l g o r i t h m s 57 
3.5.1 KNN for £=1,2,3,4 57 
3.5.2 KWNN for £=1,2,3,4 58 
SYSTEM ARCHITECTURE 59 
4.1 H a r d w a r e a n d S o f t w a r e m o d u l e s 59 
4.1.1 Terminal based approach 59 
4.1.2 Test bed 59 
4.1.3 Application software 60 
4.1.3.1 Training phase 60 
4.1.3.2 Positioning phase 62 
4.1.3.3 Analysis phase 63 
4.2 M e t h o d o l o g y 64 
4.2.1 Training the system with RP coordinates 64 
4.2.2 Measurement of RSS 66 
4.2.3 Database generation 67 
4.2.4 Positioning testing 70 
4.2.5 Testing data analysis 71 
EXPERIMENT AND RESULTS ANALYSIS 73 
5.1 T e s t s c e n a r i o s 73 
5.1.1 Identifying the applicable path loss exponent (n) 73 
5.1.2 Identifying the attenuation loss (La) of the environment 74 
5.1.3 Positioning accuracy of the proposed technique compared to other 
techniques 74 
5.1.4 Effect of the training grid size 74 
5.1.5 Effect of number of samples per reference point 75 
5.1.6 Effect of the orientation of the mobile terminal 75 
5.2 T e s t r e s u l t s a n a l y s i s 75 
5.2.1 Identifying the effect of La and n 75 
5.2.2 Comparison of positioning accuracy and precision 76 
5.2.3 Effect of grid size 77 
5.2.4 Cumulative distribution of positioning error 78 
5.2.5 Effect of number of samples per reference point 80 
xi 
PRACTICAL PROBLEMS 82 
6 .1 I n t r o d u c t i o n 8 2 
6 . 2 T h e e f f e c t o f w i r e l e s s c h a n n e l c h a r a c t e r i s t i c s 8 2 
6 . 3 T h e e f f e c t o f d y n a m i c e n v i r o n m e n t a l c h a n g e s 8 3 
6 . 4 D e p l o y m e n t a n d o p e r a t i o n a l c o s t 8 4 
6 . 5 S y s t e m t r a i n i n g 8 4 
6 . 6 A l i a s i n g 8 5 
6 . 7 E f f e c t o f m u l t i p l e c h a n n e l s 8 5 
6 . 8 T h e e f f e c t o f m u l t i p l e f l o o r s 8 6 
6 . 9 W i r e l e s s s e c u r i t y 8 6 
DISCUSSION 87 
7 .1 G e n e r i c p e r f o r m a n c e r e q u i r e m e n t s o f l o c a l i z a t i o n s y s t e m s 8 7 
7 . 2 P e r f o r m a n c e o f t h e p r o p o s e d a l g o r i t h m 8 8 
7 . 2 . 1 Positioning Accuracy 8 8 
7 . 2 . 2 Precision of location estimation 8 8 
7 . 2 . 3 Size of the training grid 8 9 
7 . 2 . 4 Number of readings per location 8 9 
7 . 2 . 5 Number of access points 9 0 
7 . 2 . 6 Orientation of the mobile terminal 9 0 
7 . 2 . 7 Simplicity, response time and cost 9 0 
7 . 2 . 8 Limitations 9 1 
7 . 3 G e n e r a l p r a c t i c a l issues 9 1 
7 . 3 . 1 Effect of WLAN characteristics 9 1 
7 . 3 . 2 Aliasing 9 1 
7 . 3 . 3 Temporal changes to signal strength 9 2 
7 . 3 . 4 Effect of manufacture hardware 9 2 
7 . 4 E n h a n c e m e n t s 9 2 
7 . 5 C o n c l u s i o n 9 3 
BIBLIOGRAPHICAL REFERENCES 96 
xii 
LIST OF FIGURES 
Fig. 1.2.1. The architecture of RSS based positioning systems 4 
Fig. 1.2.2. The function of K.NN algorithm 5 
Fig. 1.3.1. Accuracy and precision of positioning 6 
Fig. 1.4.1. The basic concept of the proposed positioning algorithm 9 
Fig. 1.5.1. Implementation of the proposed positioning technique 11 
Fig. 2.3.1. Basic cell identification method 15 
Fig. 2.3.2. Improved cell identification using TA information 16 
Fig. 2.3.3. Lateration technique can be improved with AOA information 17 
Fig. 2.3.4. Trilateration technique 17 
Fig. 2.3.5. Database correlation in (a) KNN and (b) Probabilistic algorithms 21 
Fig. 2.3.6 The function of neural networks method 24 
Fig. 2.3.7. The basic function of robot localization 27 
Fig. 2.4.1. The function of the Viterbi-like algorithm 29 
Fig. 2.4.2. AP based environmental profiling 30 
Fig. 3.3.1. Calculating the distance between the NN and the target position 43 
Fig. 3.4.1. All possible cases resulting from the orientation and relative radii of the 3 circles... 44 
Fig. 3.4.2. The layout of the proposed positioning algorithm 45 
Fig. 3.4.3. Each 2 circles of all the 3 pairs either intersect (fully/partially) or just touch at one 
point : 46 
Fig. 3.4.4. Each 2 circles of all the 3 pairs either intersect partially or just touch at one point..47 
Fig. 3.4.5. Each 2 circles of 2 pairs either intersect partially or just touch at one point while 
the 2 circles of other pair intersect fully 49 
Fig. 3.4.6. Each 2 circles of 2 pairs fully intersect while the 2 circles of the other pair either 
intersect partially or just touch at one point 50 
Fig. 3.4.7. Each 2 circles of all 3 pairs fully intersect 50 
Fig. 3.4.8. Each 2 circles of any 2 pairs either intersect (fully/partially) or just touch at one 
point while the 2 circles of the other pair are disintegrated 5 1 
Fig. 3.4.9. Each 2 circles of the 2 intersecting pairs of circles either intersect partially or just 
touch at one point 52 
Fig. 3.4.10. Two circles of one pair either intersect partially or just touch at one point while 
the 2 circles of the other pair fully intersect 52 
Fig. 3.4.11. Each 2 circles of both intersecting pairs fully intersect 53 
Fig. 3.4.12. Two circles of one pair either intersect (fully/partially) or just touch at one point 
while the circles of the other 2 pairs are disintegrated 54 
xiii 
Fig. 3.4.13. Two circles of the intersecting pair either intersect partially or just touch at one 
point 54 
Fig. 3.4.14. The 2 circles of the intersecting pair fully intersect 55 
Fig. 3.4.15. All the 3 circles are disintegrated from each other 56 
Fig. 3.4.16. Centres of the circles are equally spaced 56 
Fig. 3.4.17. Two pairs of centres are equally spaced and are closely spaced than the other pair 57 
Fig. 3.4.18. Only one pair of centres corresponds to the shortest inter-circle distance 57 
Fig. 4.1.1. Experimental set up 60 
Fig. 4.1.2. Training the system with RP coordinates 61 
Fig. 4.1.3. RSS Scan by Network Stumbler at RPs 62 
Fig. 4.1.4. The Estimated location is indicated on the map 63 
Fig. 4.1.5. Input the true location against the estimated location 64 
Fig. 4.2.1. Small training grid used in the experiment 65 
Fig. 4.2.2. Large training grid derived from the small training grid 65 
Fig. 4.2.3. RSS scan being exported to a txt file 66 
Fig. 4.2.4. The system training process 67 
Fig. 4.2.5. Format of the table of RPs 68 
Fig. 4.2.6. Format of the table of RSS 68 
Fig. 4.2.7. Format of the table of positioning analysis data 69 
Fig. 4.2.8. Format of the table of calculated Euclidean distances 69 
Fig. 4.2.9. Format of table of calculated distances (R) between selected NNs and estimated 
position 70 
Fig. 4.2.10. Tested positions 70 
Fig. 4.2.11. Positioning Process 72 
Fig. 5.2.1. Cumulative Distribution Function of error distance for small training grid 79 
Fig. 5.2.2. Cumulative Distribution Function of error distance for large training grid 80 
Fig. 5.2.3. The average relative RSS from different APs for varying scan time periods 80 
Fig. 5.2.4. The average number of records per AP against the scan time period 81 
x i v 
LIST OF TABLES 
Table 3.4.1. All possible events resulted from the check of intersection between each pair of 
circles 46 
Table 3.4.2. Possible events from the check of whether circles intersect fully or partially 47 
Table 3.4.3. Possible events from the check of whether the circles intersect fully or partially.... 51 
Table 3.4.4. Possible events from the check of whether the circles intersect fully or partially.... 54 
Table 5.2.1. Mean error distance (in m) for varying La and n values 76 
Table 5.2.2. Error distance variance (in m) for varying La and n values 76 
Table 5.2.3. Positioning accuracy (in m) obtained with different positioning algorithms 77 
Table 5.2.4. Mean and varience of error distance (in m) for different training grid size 78 
Table 5.2.5. Improvement of position estimation with reduced grid size 78 
xv