id,collection,dc.contributor.author,dc.contributor.contact,dc.contributor.firstReferee,dc.contributor.furtherReferee,dc.contributor.gender,dc.date.accepted,dc.date.accessioned,dc.date.available,dc.date.issued,dc.description,dc.description.abstract[de],dc.format.extent,dc.identifier.uri,dc.identifier.urn,dc.language,dc.rights.uri,dc.subject,dc.subject.ddc,dc.title,dc.title.translated[de],dc.type,dcterms.accessRights.dnb,dcterms.accessRights.openaire,dcterms.format[de],refubium.affiliation[de],refubium.mycore.derivateId,refubium.mycore.fudocsId "ff853178-1f0c-4ee3-a3e5-81cf43881e30","fub188/14","Yang, Yuan","yangyuancsi@gmail.com","Prof. Dr. Marcel Kyas","Prof. Dr. Moe Z. Win","w","2015-03-13","2018-06-08T01:17:02Z","2015-03-20T08:29:14.538Z","2015","List 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","The critical problem in range-based indoor positioning is the severe ranging uncertainty, which typically resorts to the probabilistic perspective. Since there is no analytical solution to the nonlinear and non-Gaussian positioning problem, the research trends have moved towards exploring sample-based approximations in the probabilistic frame. However, the sample-based methods are generally inaccessible for application not only because of the high complexity, but also for the sampling difficulty and divergence. This thesis studies the sample-based probabilistic positioning to achieve the trade in performance (accuracy and robustness), cost (time and space complexity), and usability (in terms of the required number of samples and implementation difficulty). The work of this thesis covers both the theoretical and practical sides of sample-based probabilistic algorithms positioning. The proposed algorithms are tested by extensive simulations and real-world experiments on the Nanotron platform. Specifically, the contributions of this thesis can be summarized in the following: (a) Chapter 3.3 characterizes the indoor TOF ranging, i.e., the relationship of the ranging error to time, space, anchor connectivity and the ground truth of the ranging, etc. Then, intensive distribution fitting, hypothesis test, and model verification of different parametric models are carried out. (b) Via the imposition of the state constraints from the most recent observation, four constrained sampling methods are developed (see Chapter 4), with the advantages, including: 1) effectively reduces the sample size; 2) suppress sample degeneracy and impoverishment without resampling; 3) no requirement of keeping all samples’ properties in memory. (c) The NLOS mitigation proposed in Chapter 4 refines the measurement model as a positively biased and right-tail distribution. (d) Both the theoretical and practical anchor deployment are suggested in Chapter 4. (e) To address the estimation instability and sparsity problems, the one time-step smoothing methods are incorporated in the sample-based Bayesian estimation.||Das 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.","XII, 159 S.","https://refubium.fu-berlin.de/handle/fub188/13183||http://dx.doi.org/10.17169/refubium-17381","urn:nbn:de:kobv:188-fudissthesis000000098947-7","eng","http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen","Indoors positioning||target tracking||Bayesian filtering||Bayesian smoothing||samplebased approximation||frequentist measurement","000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme","Sample-based Probabilistic Estimation for Indoor Positioning and Tracking Under Ranging Uncertainty","Abtastungsbasierte probabilistische Schätzung für Indoor-Positionierung und Verfolgung unter der Unsicherheit der Entfernungsmessung","Dissertation","free","open access","Text","Mathematik und Informatik","FUDISS_derivate_000000016775","FUDISS_thesis_000000098947"