Mobile handset localization by received signal level pattern matching

Abstract

In dieser Arbeit untersuchen wir Positionierungsverfahren, die auf Mustererkennung basieren. Signalstärkemessungen werden dabei zur Charakterisierung der Position herangezogen und mit vorher aufgezeichneten oder simulierten Daten verglichen.<br />Durch eine zeitlich veränderliche Umgebung, durch Mehrwegeausbreitung und durch Unterbrechungen der Sichtverbindung zwischen Sender und Empfänger entstehen allerdings mehrdeutige Charakterisierungen der Position. Um diesem prinzipiellen Problem entgegenzuwirken, modellieren wir jede Position als stochastisches Modell. Dabei verwenden wir Bayessche Netze, um die Abhängigkeiten zwischen den Signalen der empfangenen Basisstationen zu beschreiben.<br />Wir optimieren die Bayessche Netzstruktur solcherart, dass sie Positionen im städtischen Raum bestmöglich repräsentiert. Als Metrik wird dabei die Verbundwahrscheinlichkeit zwischen Modellstruktur und gemessenen Daten an den jeweiligen Positionen verwendet. Dies erlaubt eine objektive Evaluierung der Qualität der Modelle.<br />Wir zeigen, dass a-priori Wissen über die Verteilung der Signalstärkemuster einer Position aus benachbarten Positionen gewonnen werden kann.<br />Weiters wird ein Algorithmus zur Positionsbestimmung, basierend auf den Bayesschen Netzen, mit geringer Latenzzeit vorgestellt. Wir führen dessen Komplexität auf eine einzige Maximierungsaufgabe zurück. Die Berechnung der zugrunde liegenden Daten in Echtzeit ist dabei nicht notwendig.<br />Der Algorithmus wird schließlich mit gängigen Mustererkennungsmethoden und mit satellitenbasierter Positionierung verglichen. Die Ergebnisse zeigen dabei Fehler von 13.75m in 67% und 93.45m in 95% aller Fälle, welche den in den USA vorgeschriebenen Erfordernissen für mobile Notfalldienste entsprechen. Diese schreiben in 67% aller Fälle Fehler kleiner 100m und in 95% aller Fälle Fehler kleiner 300m für netzbasierte Methoden vor.<br />Wir zeigen weiters durch Langzeituntersuchungen von aufgezeichenten Signalstärkemesswerten die Notwendigkeit der regelmäßigen Aktualisierung der Signalstärkemusterdatenbank. Sinnvolle Aktualisierungsintervalle liegen bei etwa 42 Stunden.<br />

In this thesis we investigate pattern-matching-based positioning. Based on signalpower measurements, the position of the mobile is determined by either matching the measured data to pre-stored data in a database or by matching the measured data to simulated data.<br />To allow for the uncertainty about the environment, including time variant scatterers, multipath and non-line-of-sight situations, we apply a stochastic perspective.<br />Propagation effects, which create the ambiguity of the radio frequency patterns, are modelled by the capability of Bayesian networks to encode uncertainty.<br />The Bayesian networks are used to describe the dependencies between the different measured cell identities (serving cells and list of the neighboring cells ranked according to the received power levels) for each position.<br />We optimize the Bayesian model structure to represent positions in urban environment by maximizing the joint probability of the data and the model's structure over all models. This forms not only a view of the relative quality of the candidate models, but it also gives an assessment of the adequacy as an explanation of the data.<br />To include environment-caused physical facts we introduce an adapted prior distribution. This includes no multiple occurrence of a certain cell ID within a single pattern or less received power of more distant base stations.<br />We develop a positioning algorithm whose complexity is reduced to a single maximization of a database data vector, containing one element per node and position of the model. The effort-consuming computations are done off-line, allowing low latency of the positioning.<br />The algorithm is tested and compared against several state-of-the-art positioning methods, including other pattern matching algorithms and satellite based positioning. We achieve an error of 13.75m in 67% of all cases and an error of 93.45m in 95% of all cases in an urban environment. This is fully compliant with the requirements for mobile emergency services in the USA (E911), specifying an error of 100m in 67% of all cases and 300m in 95% of all cases for network-based methods.<br />We further evaluated long-term signal-level measurements revealing a validity of the signal level database of about 42 hours. During that period, it is still possible to determine 50% of all received fingerprints at the measurement site in 90% of all cases.