Objekt-Metadaten

Sample-based Probabilistic Estimation for Indoor Positioning and Tracking Under Ranging Uncertainty
Yang, Yuan

Main titleSample-based Probabilistic Estimation for Indoor Positioning and Tracking Under Ranging Uncertainty
Title variationsAbtastungsbasierte probabilistische Schätzung für Indoor-Positionierung und Verfolgung unter der Unsicherheit der Entfernungsmessung
Author(s)Yang, Yuan
Place of birth: Hunan, China
1. RefereeProf. Dr. Marcel Kyas
Further Referee(s)Prof. Dr. Moe Z. Win
KeywordsIndoors positioning; target tracking; Bayesian filtering; Bayesian smoothing; samplebased approximation; frequentist measurement
Classification (DDC)000 Computer Science, knowledge, systems
SummaryDas grundlegende Problem von distanzbasierter Indoor-Lokalisierung, ist die hohe Ungenauigkeit der Distanzmessungen. Die weit verbreitetste Strategie mit diesem Problem umzugehen, ist die probalistische Schaetzung. Da es fuer das nicht-lineare und nicht-gaussche Lokalisierungsproblem keine analytische Loesung gibt, besteht ein wachsendes Interesse in der Untersuchung von Sample-basierten Naeherungen. Sample basierte Naeherungen haben jedoch den Nachteil, dass sie Aufgrund ihrer hohen Komplexitaet und des sampling-Aufwandes im Feld kaum anwendbar sind. Daher ist es das Ziel dieser Arbeit Sample-basierte probalistische Lokalisierungsverfahren zu studieren und einen Optimum zwischen Genauigkeit und Robustheit, Kosten (zeitliche und oertliche Komplexitaet) und Anwendbarkeit (im Sinne der benoetigten Sample-Zahl und Implementierungsaufand) zu finden.

Der wissenschaftliche Beitrag dieser Arbeit findet sich sowohl auf der anwendungs- als auch auf der theoretischen Seite von probalistischen Lokalisierungsverfahren. Die Lokalisierungsverfahren werden mittels aufwaendiger Simulationen, sowie durch Experimente in realistischen Szenarien evaluiert. Als Platform fuer die Experimente dient das funkbasierte Entfernungsmesssystem der Firma Nanotron. Im Detail lassen sich die Beitraege wie folgt zusammenfassen:
- Kapitel 3 charakterisiert die Besonderheiten von Time-Of-Flight basierter Indoor-Distanzmessung. Beispielsweise die Abhaengigkeit des Distanzehlers zu Messzeit und -ort, zu der Anzahl der Anker, zur echten Position der Messung und Einfluesse des menschlichen Koerpers usw. Im Anschluss werden Fehlerverteilungsfunktionen an die Verteilung der Messdaten angepasst, ein Hypothesen-Test sowie eine Model-Verifkation fuer verschiedene parametrische Modelle durchgefuehrt.
- Durch die Einfuehrung von Zustandsbeschraenkungen auf die aktuellen Messung werden vier beschraenkte Sample-Methoden entwickelt (vgl. Kapitel 4), die folgende Vorteile bieten: 1. Reduzierung der benoetigten Samples. 2. Robustheit gegenueber Ausreissern oder Messluecken 3. Es ist nicht mehr noetig alle Samples im Speichern.
- das NLOS Abschwaechungsmodell, welches in Kapitel 4 vorgestellt wird aendern das Fehlermodell der Entfernungsmessung hin zu einer positiv verschobenen rechts auslaufenden Verteilungsfunktion.
- In Kapitel 4 wird die theoretisch- sowie praktisch optimale Ankerplatzierung diskutiert.
- Die vorgeschlagenen Algorithmen bieten eine allgemeine Plattform fuer sequentielle- und nicht sequentielle Lokalisierungsverfahren.
- Um Varianz-Probleme und Sampleausfaelle zu unterdruecken wird ein Glaettungsverfahren vorgestellt, welches auf einem einstufigen Zustand mit Bayesianischer Schaetzung beruht.
ContentList of Notations v
List of Algorithms v
List of Figures vii
List of Tables xi
1 Introduction 1
1.1 What Makes Indoor Positioning Attractive? . . . . . . . . . . . . . . . . . . . . . 1
1.2 Indoor Positioning Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Positioning measurement techniques . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Positioning estimation methods . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 Comparison of positioning systems . . . . . . . . . . . . . . . . . . . . . 6
1.3 Practical Probabilistic Positioning Algorithms . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Practical considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Research Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 Modeling the uncertainty of indoor RF ranging . . . . . . . . . . . . . . . 8
1.4.2 From non-sequential to sequential positioning . . . . . . . . . . . . . . . . 9
1.4.3 NLOS mitigation and smoothing . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Existing Probabilistic Approaches for Range-based Positioning 13
2.1 Bayesian Range-based Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Basis of Bayesian inference . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.2 Dynamical models of Bayesian inference . . . . . . . . . . . . . . . . . . 16
2.2 Approximation to Bayesian Positioning . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Minimum Mean Square Error (MMSE) estimation . . . . . . . . . . . . . 17
2.2.2 Maximum A Posteriori (MAP) estimation . . . . . . . . . . . . . . . . . . 18
2.2.3 Maximum Likelihood (ML) estimation . . . . . . . . . . . . . . . . . . . 19
2.2.4 Least-square (LS) estimation . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Sample-based Probabilistic Positioning . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1 Gaussian-sum approximation . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 Grid-based approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.3 Markov chain Monte Carlo methods . . . . . . . . . . . . . . . . . . . . . 23
2.3.4 Importance sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Sequential position estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Bayesian frame of hidden Markov model . . . . . . . . . . . . . . . . . . 26
2.4.2 Kalman Filter (KF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.3 Grid-based Filter (GF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.4 Particle Filter (PF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3 Characteristics and Frequentist Modeling of Indoor Ranging Uncertainty 37
3.1 TOA Ranging Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.2 Error sources of TOA ranging . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.3 Analytical form of TOA ranging error . . . . . . . . . . . . . . . . . . . . 40
3.2 Testbed Description and Experiment Setup . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Characteristics of Indoor Ranging Uncertainty . . . . . . . . . . . . . . . . . . . . 43
3.3.1 Typical statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.2 Non-Gaussianity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.3 Ranging variation with time and space . . . . . . . . . . . . . . . . . . . . 45
3.3.4 Ranging error versus distance . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.5 Ranging variation of device diversity . . . . . . . . . . . . . . . . . . . . 48
3.3.6 Positive and negative ranging errors . . . . . . . . . . . . . . . . . . . . . 48
3.3.7 NLOS errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4 Frequentist Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.1 Statistical models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4.2 Distribution fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5 Model Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.5.1 Kolmogorov-Smirnov (KS) test . . . . . . . . . . . . . . . . . . . . . . . 55
3.5.2 Maximum entropy principle . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5.3 Influence of ranging models on positioning . . . . . . . . . . . . . . . . . 59
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4 Sample-based Probabilistic Estimation for Indoor Positioning 63
4.1 Aspects of Range-based Positioning . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.1 Error propagation from ranging to positioning . . . . . . . . . . . . . . . . 64
4.1.2 Anchor placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.1.3 Probabilistic positioning methods . . . . . . . . . . . . . . . . . . . . . . 68
4.1.4 Evaluation criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.2 Constrained Sampling Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.2.1 Bounded grid-based approximation . . . . . . . . . . . . . . . . . . . . . 79
4.2.2 Geometric sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.2.3 Polar sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.2.4 Gradual Gaussian approximation . . . . . . . . . . . . . . . . . . . . . . . 97
4.2.5 Results and analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.2.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.3 NLOS Mitigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.3.1 Existing NOLS mitigation . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.3.2 Biased nonparametric measurement models . . . . . . . . . . . . . . . . . 113
4.3.3 Adaptive measurement model . . . . . . . . . . . . . . . . . . . . . . . . 118
4.3.4 Results and analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5 One Time-step Smoothing for Real-time Positioning 125
5.1 Motivation and Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.1.2 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2 One Time-step Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.1 Forward Filtering Backward Smoothing (FFBS) . . . . . . . . . . . . . . . 128
5.2.2 Two Filter Smoothing (TFS) . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.2.3 Smoothed Filtering (SF) . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.3 Combine Linear Smoother with Nonlinear Filtering Output . . . . . . . . . . . . . 134
5.3.1 Moving average . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.3.2 Kalman smoother . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.4 Results and analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.4.1 Quantitative results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.4.2 Positioning behavior and smoothness . . . . . . . . . . . . . . . . . . . . 138
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6 Concluding Remarks 143
6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.2 Suggestions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Bibliography 146
Documents
PDF
If your browser can't open the file, please download the file first and then open it
 
Number of pagesXII, 159 S.
FU DepartmentDepartment of Mathematics and Computer Science
Year of publication2015
Document typeDoctoral thesis
Media type/FormatText
LanguageEnglish
Terms of use/Rights Nutzungsbedingungen
Date of defense2015-03-13
Created at2015-03-20 : 06:26:42
Last changed2015-03-26 : 12:54:03
 
Static URLhttp://edocs.fu-berlin.de/diss/receive/FUDISS_thesis_000000098947
NBNurn:nbn:de:kobv:188-fudissthesis000000098947-7
Statistics
E-mail addressyangyuancsi@gmail.com