Efficiency of time-differential positioning algorithms and geometric impacts in wireless networks

Abstract

Im Rahmen dieser Arbeit werden Möglichkeiten untersucht, asynchrone drahtlose Netzwerkgeräte, an die keine speziellen Hardware- oder Softwareanfoderungen gestellt werden, mittels Differenzlaufzeitverfahrens (TDOA) passiv zu lokalisieren. Dabei wird auf ein standardisiertes kabelloses Netzwerk und ein verteiltes System synchronisierter lauschender Empfängerstationen zurückgegriffen, welche die Ankunftszeitpunkte der von drahtlosen Netzwerkgeräten ausgesendeten Signale bestimmen. In der Literatur existieren verschiedenste Vorgehensweisen, um Näherungslösungen des zugrundeliegenden nichtlinearen -- und im Normalfall außerdem überbestimmten -- Gleichungssystems zu bestimmen. Ausführliche systematische Untersuchungen zu praktisch erreichbarer Genauigkeit und den Anforderungen an den Rechenaufwand verschiedener Methoden fehlen jedoch.<br />Basierend auf den Anforderungen lokal begrenzter Lokalisierungssysteme, geometrischen Aspekten, und aus der Analyse existierender Methoden gewonnenen Erkenntnissen, wird ein neuer direkter Algorithmus zur Punktbestimmung vorgestellt. Dieser wird bezüglich der erreichbaren Genauigkeit und des Rechenaufwandes mit einem weiteren direkten Algorithmus, der auf der bekannten Lösung von Bancroft beruht, und einem iterativen Algorithmus basierend auf dem gängigen Gauß-Newton Verfahren verglichen. Die Genauigkeitsanalyse wird primär anhand von Monte Carlo Simulationen in einer eigens entwickelten Simulationsumgebung durchgeführt. Unter Verwendung eines an die benutzte Hardware angepassten Fehlermodells wird sowohl die erreichbare Genauigkeit der geschätzten Position als auch der mit den verschiedenen Ansätzen verbundene Rechenaufwand gemessen an den notwendigen Fließkommaoperationen (FLOPs) eingehend untersucht und verglichen.<br />Zusätzlich werden Kombinationen der verschiedenen Varianten im Sinne der iterativen Verbesserung einer direkten Lösung untersucht, und in die Vergleiche mit einbezogen. In einem systematischen Feldtest werden die Ergebnisse anschließend einer experimentellen Validierung unterzogen.<br />Dabei werden für ein handelsübliches WLAN Gerät mit Hilfe eines neuartigen und speziell dafür entwickelten Systems aufeinander abgestimmter WLAN Sendeempfänger erreichbare Positionsgenauigkeit und benötigter Rechenaufwand systematisch untersucht. Im geometrischen Teil dieser Arbeit wird die notwendige Anzahl an Basisstationen eruiert, sowie deren Abhängigkeit von der geforderten Genauigkeit und verschiedenen Einflussfaktoren auf Sys\-tem\-ebe\-ne. Zudem werden kritische Konfigurationen, singuläre Anordnungen von Basisstationen und der Geometrie entspringende Mehrdeutigkeiten untersucht. Dazu werden Lösungen vorgeschlagen und angewendet. Um die Fortpflanzung von Fehlern in den Zeitmessungen zu Positionsfehlern gering zu halten, werden geeignete fehlertolerante Anordnungen von Basisstationen vorgeschlagen und analysiert, indem die Verringerung der Positionsgenauigkeit durch Ausfall einzelner Basisstationen untersucht wird. Ausgehend von den Ergebnissen der Simulationen und des Feldtests wird ein Algorithmus zur Implementierung vorgeschlagen, der auf den zuvor untersuchten Algorithmen aufbaut und dynamischen Wechsel zwischen verschiedenen Varianten in Abhängigkeit der Systemlast vorsieht, um die Positionsgenauigkeit den zur Verfügung stehenden Ressourcen dynamisch anzupassen.<br />

This work investigates the possibilities of passive time-differential positioning of asynchronous wireless network devices without specific hardware or software requirements for these devices. This is achieved by utilization of a standardized wireless network and a distribution system of synchronized base stations, which intercept wireless signals and record their times of arrival (TOAs). The location of such devices can be estimated through the positioning schemes of hyperbolic positioning and pseudoranging, which in the context of time-based positioning are commonly referred to as time difference of arrival (TDOA). In the literature, there are numerous approaches, using various methods for deriving approximate solutions to the underlying nonlinear and usually overdetermined system of polynomial equations. Furthermore, the information about practically achievable accuracy and computational requirements of those approaches is scarce and incomplete.<br />In this thesis, a new algorithm is described through an analysis based on the requirements of locally installed positioning systems, on geometrical aspects, and on existent methods. Its estimation efficiency and computational efficiency are directly compared to those from variants of the direct Bancroft and the iterative Gauss-Newton method. The performance evaluation is primarily achieved through Monte Carlo simulations in a self-developed simulation environment. By the use of a certain error model matching the used hardware, not only the spatial accuracy for typical scenarios is derived, but also a thorough analysis and comparison of computational expenditure---measured in floating point operations (FLOPs)---is conducted. Furthermore, consecutive combinations of the new algorithm and the Bancroft method with the Gauss-Newton method are evaluated and included in the comparisons. The geometrical analysis includes the dependency of the minimum number of base stations on various environmental factors as well as on the required level of accuracy. Additionally, critical configurations, singular formations of base stations, and ambiguities originating from the geometry are investigated, and solutions to solve them are proposed and applied. In order to minimize error propagation from time measurements to resulting position, suitable fault-tolerant geometrical layouts of base stations in overdetermined systems are proposed and analyzed. The latter includes assessment of the deterioration of the system's accuracy in presence of faulty base stations. In a systematic field test, the results are experimentally validated by locating an off-the-shelf WLAN device with a dedicated system of synchronized novel dedicated WLAN transceivers. The final algorithm for implementation allows dynamic switching between the different methods depending on the accuracy of the positioning system in relation to the available computing resources.<br />