Welchen Algorithmus sollte ich für die Geolokalisierung über WLAN verwenden?

16

Anwendungsfall für die Schulübernahme (Update)

Es kann hilfreich sein, einen konkreten Anwendungsfall anstelle des ursprünglichen Beispiels für einen Hinterhof zu betrachten. Die örtlichen Strafverfolgungsbehörden haben damit begonnen, die Nutzung von SMS und Mobiltelefonen in Schulgebieten zu unterbinden. Dies stellt ein Problem für Eltern dar, die Kinder nach einer Mittelschulveranstaltung abholen. Selbst für diejenigen, die das Gesetz zur Schau stellen, wird der Zellturm schnell überlastet, wenn Hunderte von Kindern gleichzeitig ihre Eltern anrufen. Der Campus ist groß, mit WiFi-Abdeckung. Anscheinend sollte es möglich sein, eine mobile App zu schreiben, mit der ein Handybenutzer eine SMS mit einer Liste der WLAN-Signalstärken an einen Webservice senden kann. Der Webdienst erstellt dann einen Standortfix und leitet die Nachricht an das Navigationsgerät an Bord des Elternteils weiter. Die Eltern würden dann zur richtigen Stelle auf dem Campus fahren.

Backyard Use Case (Original) Wenn ich meinen Laptop in meinen Backyard bringe und "Verfügbare Netzwerke anzeigen" wähle, wird eine Liste meiner 4 Nachbarn angezeigt. Während ich umhergehe, ändern sich die relativen Signalstärken meiner Nachbarn.

Ich möchte mit meinem Laptop an bekannten Orten in meinem Garten stehen, auf die Karte klicken und Punkte mit 4 verschiedenen Signalstärken sammeln.

Nachdem ich eine Menge (aber nicht zu viele) dieser Kalibrierungspunkte gesammelt habe, möchte ich ein Programm schreiben, das 4 WLAN-Signalstärkenstufen verwendet und eine Position in Form einer Fehlerellipse schätzt. Die Signale werden möglicherweise mit einem anderen Gerät gemessen als dem, mit dem die ursprünglichen Kalibrierungspunkte erfasst wurden.

Welchen Algorithmus soll ich verwenden?

Ich möchte meine Nachbarn nicht stören, indem ich sie frage, ob ich den genauen Standort ihres Routers abfragen kann.

Ich kann jedoch davon ausgehen, dass sich der Standort meiner Router-Nachbarn nicht ändert.

Kirk Kuykendall
quelle
4
Ich denke, dass er nur Triangulationen machen will, nicht Huckepack ...
Marinheiro
Kein Huckepack - nur Signalstärke, was ist legal zu messen, oder? Ich werde das WLAN nicht "googeln" ... blogs.discovermagazine.com/80beats/2010/10/25/…
Kirk Kuykendall

Antworten:

6

Es hört sich so an, als ob Sie die Signalorte nicht sehr gut kennen. Sie müssen sie also zuerst schätzen und dann anhand dieser Schätzungen Ihre Position triangulieren.

Wenn Sie Genauigkeit und Realismus wünschen, sollten Sie ein Wahrscheinlichkeitsmodell für die Signalstärken verwenden, die maximale Wahrscheinlichkeit ermitteln und eine Gitterkarte der aus den Schätzungen der maximalen Wahrscheinlichkeit berechneten Standortwahrscheinlichkeit erstellen. Das globale Maximum im Raster gibt die beste Schätzung der Position an, und die Konturen (relativ zum Maximum) geben Konfidenzsätze für diese Position an.

Ein allgemeines Wahrscheinlichkeitsmodell wird erhalten, indem eine Formel für die Signaldämpfung aufgestellt und Fehler berücksichtigt werden. Mit einer vollständig allgemeinen Formel (mit einer winkel- und ortsabhängigen Dämpfungsfunktion) kommen Sie nicht sehr weit, daher müssen Sie vereinfachen. Zum Beispiel könnten Sie eine "universelle" Dämpfungsfunktion in Betracht ziehen, nennen Sie sie f , so dass, wenn die Quellenstärke an einem WiFi-Standort x gleich a ist, die erwartete Stärke an einem anderen Standort y durch gegeben ist

z (y; x) = af (| y - x |).

Zum Beispiel könnten Sie eine inverse quadratische Dämpfung in Betracht ziehen, für die f (t) = 1 / t ^ 2 ist, vorausgesetzt, der Abstand t ist größer als ein kleiner Schwellenwert. Als weitere Vereinfachung können Sie die Stärkeanzeige z (y; x) an Position y verwenden, damit die Quelle an x durch einen normalverteilten Fehler vom erwarteten Wert abweicht. Nehmen Sie an, dass alle Fehler unabhängig sind. und nehmen an, dass sie alle die gleiche ( n ) Standardabweichung ( en ) haben. Der Beitrag zur logarithmischen Wahrscheinlichkeit einer Festigkeitsablesung wird dann z

L (y, x) = - [(z (y; x) - af (| yx |) ^ 2 / s ^ 2 + ln (s)] / 2.

Die Wahrscheinlichkeit, dass das Protokoll maximiert wird, ist die doppelte Summe von L (y, x) über alle Positionen y und alle Quellen x . Es ist eine Funktion der unbekannten Orte, der unbekannten Quellenintensitäten und der unbekannten Standardabweichung der Fehler. Es ist einfach , die optimale Standardabweichung und optimale Quellenintensitäten (nehmen partielle Ableitungen, diejenigen auf Null und lösen gesetzt) zu finden, aber für realistische Dämpfungsfunktionen f Sie für die Suche nach den Standorten ein nichtlineares Problem haben. In Ihrem Beispiel sind es jedoch nur 13 Parameter, sodass Sie es beispielsweise in einen multivariaten Newton-Raphson-Optimierer kopieren können, um schnell eine gute Antwort zu erhalten. (Die Statistikliteratur ist voll von Methoden zur Lösung dieser Art von Gleichungen.)

Wenn Sie zusätzlich davon ausgehen, dass das zweite Gerät eine proportional höhere Empfindlichkeit als das Datenerfassungsgerät aufweist, hat dies nur einen geringen Einfluss auf das von mir vorgeschlagene Modell (da die Signalstärken multiplikativ eingegeben werden). Wenn Sie die Fehler mit der Intensität skalieren lassen (also die Standardabweichung a * s * statt s ), sollte der Unterschied zwischen den Geräten keine Rolle spielen.

Um dies einfach zu halten, habe ich einige statistische Details übersprungen, beispielsweise die Tatsache, dass es sich um ein multivariates Vorhersageintervallproblem und nicht um ein Konfidenzintervallproblem handelt. Wenn die Fehlermenge nicht groß ist (dh s ist klein), ist der Unterschied nicht von großer Bedeutung.

whuber
quelle
Vielen Dank, Bill, das sieht machbar aus. Bei Laptops ist mir gerade aufgefallen, dass das Signal empfindlich auf die Ausrichtung der Antennen reagiert. Ich bin mir nicht sicher, ob dies bei Mobiltelefonen der Fall ist. Wäre der Standort gut genug für den Anwendungsfall der Mittelschule?
Kirk Kuykendall
Sie können mit der Orientierung umgehen, sie wird jedoch komplizierter und benötigt mehr Messwerte. Verwenden Sie stattdessen das maximale Signal unter allen möglichen Ausrichtungen an jedem Punkt. Der Anwendungsfall der Mittelschule ist insofern eine interessante Variante, als er vorschlägt, die Standorte und Stärken der WLAN-Absender ein für alle Mal zu ermitteln. Danach ist es eine Triangulationsübung. Eine Sorge, die ich habe, ist, dass die Quellenstärken oft unvorhersehbar variieren können. Das kann die Triangulation wirklich vermasseln. Erwägen Sie, einen Einstiegsbildschirm für abgelegene (niedrige) Signale hinzuzufügen, damit diese den Fix nicht ruinieren.
Whuber
0

Wenn Sie die Position mit GPS sammeln, denken Sie, dass Sie zwei unterschiedliche Fehlerfaktoren betrachten. eine für das GPS und die andere für die Signalstärke.

Brad Nesom
quelle
In diesem Zusammenhang könnte Kirk die Standorte in seinem Hinterhof tatsächlich unabhängig überprüfen (dh einfach mehrere GPS-Messwerte von jedem Standort ablesen).
Andy W
0

Können Sie eines der vorhandenen WiFi-Ortungssysteme wie Skyhook Wireless oder Core Location in Apples iOS nicht nutzen? Mit Skyhook können Sie WLAN-MAC-Adressen manuell zu Ihrer Datenbank hinzufügen. IOS erfasst WLAN-MAC-Adressen automatisch mithilfe von mit GPS ausgestatteten iPhones.

Ortwin Gentz
quelle
Dies könnte keine schlechte Idee sein, wenn er herausfinden wollte, wo er ist. Aber er versucht, einen Weg zu finden, um die Standorte der Netzwerke selbst zu sammeln. Darüber hinaus versucht er, seine Position anhand der Stärke der WiFi-Signale zu triangulieren. Ich bin mir nicht sicher, ob die kommerziellen Lösungen das tun.
Jvangeld
@jvangeld: Soweit ich weiß, verwendet Core Location in iOS die Wi-Fi-Signalstärke, um die Position zu triangulieren. Für den erwähnten Fall der Schulübernahme wäre dies der richtige Weg.
Ortwin Gentz
0

Kirche,

Ich liege zwar falsch, aber ich glaube, Sie haben es weit hinter sich gebracht, die Dinge zu komplizieren. Um fair zu sein, nicht aus deinem Teil der Welt zu sein, weiß ich nicht, mit welchen Einschränkungen du auf dem Schulcampus arbeitest.

Während die meisten Mobilgeräte bereits GPS- und / oder Mobilfunk-Triangulation unterstützen, ist SkyHook für WLAN aus folgenden Gründen die Antwort: 1. Ihre Datenbank mit WLAN-Standorten ist RIESIG. 2. Jedes Mal, wenn eine Anwendung mit SkyHook verwendet wird, werden neu gefundene WiFi-Netzwerke mit Position zur Datenbank hinzugefügt. Je mehr es in einem Gebiet verwendet wird, desto genauer wird es. Ich würde vermuten, dass an einem Standort mit hoher Dichte wie einem Campus, der nicht bereits über eine gute Abdeckung verfügt, diese in wenigen Tagen regelmäßig genutzt werden kann. 3. Einige Telefone verwenden SkyHook als Teil ihrer Standort-APIs, was bedeutet, dass in immer mehr normalen Telefon-APIs dies bereits integriert ist.

Um ehrlich zu sein, verfügen die meisten Telefone jetzt über GPS, auf das über die nativen Telefon-APIs zugegriffen werden kann, sei es iOS, Android, WP7 oder Brombeere. Die andere Möglichkeit wäre, es zu einer mobilen Web-App zu machen, die nur die Browser-Standort-API verwendet und trotzdem auf alle Ortungstools des Telefons zugreift.

BlinkyBill
quelle
Ich dachte, Skyhook sammelte Daten über Wardriving. Ich kann mir nicht vorstellen, dass sie auf Schulstraßen fahren, obwohl diese wohl öffentlich sind.
Kirk Kuykendall
Sie haben Recht, aber weil Kunden ihre Datenbank zusätzlich zu ihren kriegerischen Aktivitäten erweitern, werden Sie wahrscheinlich feststellen, dass sie ohnehin eine Abdeckung haben. Sie können jederzeit testen, indem Sie Opera auf Ihren Laptop laden, mit maps.google.com und aktiviertem WLAN auf den Campus gehen und sehen, wo Sie sich befinden.
BlinkyBill