Bodenständig

Auch ohne GPS lässt sich in Städten die Position eines mobilen Gerätes genau genug bestimmen, um den Besitzer zum nächsten Kino, Supermarkt oder Rendezvous zu führen – ganz ohne spezielle Hardware.

Lässt man ein Notebook in einer städtischen Umgebung nach WLAN-Stationen suchen, so findet es in kürzester Zeit eine ganze Reihe von Netzwerken. Die Informationen über Signalstärken und Kennungen der fremden Funknetze darf man völlig legal benutzen, um die eigene Position auf ein paar Meter genau zu bestimmen. Dazu genügt das pure Vorhandensein von ein paar Access Points und eine Datenbank, die Daten über deren Standorte beherbergt.

Aber auch in Innenräumen hat die Lokalisierung per WLAN einigen Charme, etwa auf einer Messe. Außer der Messegesellschaft betreiben viele Aussteller WLANs an ihren Ständen und sorgen so für eine Vielzahl an Access Points in den Hallen. Vor Messebeginn schreitet man zum Einmessen einmal die Hallen ab und sammelt dabei Referenzdaten. Anhand dieser Datenbasis können die Besucher mit Hilfe ihrer eigenen PDAs ihre Position auf dem Gelände bestimmen. Eine Routenplaner-Software führt sie auf dem kürzesten Weg zum gewünschten Stand.

In Bürogebäuden, auf Werksgeländen und in Fertigungshallen kann das Wissen über den Aufenthaltsort mobiler Geräte beispielsweise helfen, Betriebsabläufe zu verbessern und damit Kosten zu sparen. Im Unterschied zu fremden WLANs in der Öffentlichkeit erlaubt das drahtlose Firmennetz darüber hinaus die kostengünstige Kommunikation mit einem zentralen Server. Das macht die Integration in die Unternehmenssoftware vergleichsweise einfach.

Obwohl es mit GPS ein öffentlich verfügbares und gebührenfreies Ortungssystem gibt, spricht einiges für die Positionsbestimmung per WLAN: Sie funktioniert nicht nur wie GPS bei freier Sicht zum Himmel, sondern auch in Gebäuden oder Straßenschluchten. Außerdem sind WLAN und GSM in städtischen Umgebungen nahezu überall präsent. Bahnhöfe, Hotels, Cafés und Büros bieten öffentliche WLAN-Zugangspunkte und Internet-Provider haben in den vergangenen Jahren WLAN-Router für DSL-Anschlüsse zu Niedrigstpreisen verkauft. Zu guter Letzt setzen viele Firmen ebenfalls auf WLAN. Mancherorts befinden sich zehn und mehr Stationen in Reichweite. In der Nürnberger Innenstadt beispielsweise funken auf einer Fläche von drei Quadratkilometern über 7000 Stationen.

Ausgangspunkt

In jedem Netz, das aus relativ kleinen, stationären Zellen besteht, lässt sich die Position der Teilnehmer mit einfachen Mitteln grob bestimmen. Als erste Näherung dient der Standpunkt der Zelle oder das Kreissegment, das die jeweilige Zelle abdeckt. Dies nennt man "Cell of Origin"-Verfahren. Alternativ zur aktuell verwendeten Basisstation lässt sich auch die Station mit der höchsten Signalstärke (Received Signal Strength) verwenden. Ist zur Stationskennung ein Standort hinterlegt, nimmt das Endgerät diesen als aktuelle Position an. Die erreichbare Genauigkeit ist höchst unterschiedlich und hängt stark von der Sendeleistung und Richtcharakteristik des Senders ab.

In GSM-Netzen kennt zumindest der Dienstanbieter den exakten Ort sowie Abstrahlwinkel jeder Funkzelle. Damit lässt sich die Position weiter eingrenzen. Allerdings haben GSM- oder UMTS-Zellen nicht selten einen Radius von ein bis zwei Kilometern und liefern so nur eine recht geringe Genauigkeit.

Anders als bei Mobilfunknetzen gibt es keinen Anbieter, der deutschlandweit ein flächendeckendes WLAN betreibt und daher die Aufstellungsorte ausreichend vieler Access Points kennt. Für die Ortung per WLAN braucht man daher gesondert ermittelte Referenzdaten. Diese können lokal im Endgerät oder auf einem zentralen Server liegen. Typischerweise liegt die Reichweite eines Access Point zwischen 15 und 100 Metern. Befindet er sich in einem Gebäude, sinkt sie auf 10 bis 30 Meter. In städtischen Straßenzügen mit hohen Gebäuden sind durch die Richtwirkung der Bauten Reichweiten von bis zu 300 Metern nicht selten. Die Genauigkeit der WLAN-Lokalisierung nach dem "Cell of Origin"-Verfahren ist dadurch stark von der Umgebung abhängig.

Schwankungen

Um die Genauigkeit zu erhöhen, kann man auch die Signalstärke auswerten. Sie erlaubt eine Schätzung der minimal und maximal möglichen Entfernung zur aktuellen Basisstation. Der wahrscheinliche Aufenthaltsort liegt somit zwischen zwei konzentrischen Kreisen mit dem Standort der Basisstation als Zentrum. Die Schwierigkeit dieses Verfahrens liegt darin, dass der Zusammenhang zwischen dem Signalstärkeabfall und der Distanz zum Sender nur für ungehinderte Ausbreitung bekannt ist.

Im realen Umfeld schwächen etwa Wände oder Decken das Signal je nach Material deutlich ab. Streuungen und Reflexionen bewirken eine stark inhomogene Ausbreitung. Die Signalstärke kann bereits innerhalb weniger Zentimeter um den Faktor zwei schwanken.

Einfache mathematische Modelle können die Komplexität der realen Umgebung nur ungenau abbilden. Ein theoretischer Ansatz, um diesen Effekt bei WLAN zumindest in Gebäuden näherungsweise mathematisch zu erfassen, führt einen materialabhängigen Wanddämpfungsfaktor ein. Dazu sind allerdings detaillierte Umgebungspläne mit Materialeigenschaften nötig, die in der Regel nicht vorliegen. Wegen dieser Fehler lohnt eine Distanzschätzung im Innenbereich meist nicht.

Nimm zwei – und mehr

Im Außenbereich sind die Fehler bei freier Sicht geringer und es bietet sich an, das Vorgehen um mehrere Basisstationen zu erweitern. Je mehr Basisstationen empfangbar sind, desto genauer kennt man den Aufenthaltsort des mobilen Endgeräts. Dieses als Multilateration bekannte Verfahren kommt beispielsweise im von Intel unterstützten Placelab-Projekt zur WLAN-Lokalisierung zum Einsatz. Placelab realisiert eine Lokalisierung WLAN-fähiger Endgeräte in Städten, wobei eine zentrale Datenbank Auskunft über die Standorte der Access Points gibt.

Mit Multilateration sind in Innenstädten unter günstigen Bedingungen für WLAN Genauigkeiten von 20 bis 40 Metern erreichbar. Jedoch müssen die exakten Standorte der WLAN-Stationen bekannt sein, was im öffentlichen Bereich mit einer Vielzahl fremder Stationen selten gegeben ist. In GSM-Netzen lässt sich so eine Genauigkeit von 70 bis 100 Metern erreichen.

Fingerabdrücke

Genauer ist das sogenannte Referenzpunkt- oder Fingerprinting-Verfahren. Die Grundidee: An jedem Ort lassen sich Signale mehrerer WLAN-Basisstationen mit unterschiedlicher Signalstärke messen. Empfängt man mindestens die Signale von vier bis fünf Access Points, so kennzeichnen die Messwerte den Ort eindeutig. Dieser elektronische Fingerabdruck besteht aus einer Liste von für jedes WLAN-Gerät eindeutigen MAC-Adressen und den zugehörigen Signalstärken. Wo die Basisstationen stehen, spielt keine Rolle.

Existiert eine Datenbank, die Fingerabdrücken eine Postion zuordnet, so besteht die Lokalisierung aus zwei Schritten: dem Suchen nach passenden Fingerabdrücken in der Datenbank sowie dem Gewichten und Kombinieren der Kandidatenpositionen zu einer Positionsschätzung.

In der Abgleichsphase berechnet das Programm für jeden in der Datenbank gespeicherten Fingerabdruck die Differenzen aus den hinterlegten Signalstärken und den für den jeweiligen Access Point aktuell gemessenen. Fingerabdrücke mit geringen Unterschieden passen gut zu den aktuellen Messwerten und sind somit sehr wahrscheinlich. Die besten Kandidaten kommen für die Positionsberechnungsphase in die engere Wahl.

In großen Arealen nimmt die Distanzberechnung zu allen Fingerabdrücken viel Zeit in Anspruch. Eine Vorauswahl ist daher wichtig, damit der Abgleich möglichst performant abläuft. Die letzte berechnete Position des Endgeräts gibt bereits einen Anhaltspunkt, digitale Umgebungskarten können die Zahl der Kandidaten weiter einschränken. Eine solche Bereichseinschränkung birgt jedoch auch Gefahren. Liegt die geschätzte Position grob daneben, kann sich die Positionierung nicht mehr erholen und bleibt an der "besten falschen" Position hängen. Daher gilt es immer, auch die absolute Qualität der Kandidatenpositionen zu prüfen. Ist die Qualität des besten Kandidaten zu schlecht, beginnt die Abgleichsphase ohne Bereichseinschränkung von vorne. An ihrem Ende erhält man eine kleine Anzahl wahrscheinlicher Aufenthaltsorte (Kandidatenpositionen).

Positionsberechnung

In der Positionsberechnungsphase berechnet man aus den Kandidatenpositionen die Position des Endgeräts. Im einfachen Fall ergibt sie sich aus dem gewichteten Mittelwert der Kandidatenpositionen. Je geringer der Unterschied zur aktuellen Messung, umso höher das Gewicht des Kandidaten für die Mitteilung. Die mittleren Positionierungsfehler liegen bei nur wenigen Metern.

Komplexere Methoden bedienen sich statistischer Verfahren. Die Grundidee dabei ist, Fehler in den einzelnen Positionsschätzungen auszugleichen, indem man den bisher zurückgelegten Weg im Nachhinein betrachtet, etwa mit Bewegungsschätzungen mit Hilfe des Kálmán-Filters. Er prognostiziert auf der Basis der letzten Positionen die Bewegungsrichtung, Geschwindigkeit und Beschleunigung. Der Abgleich zwischen Prognose und berechneter Position kann unplausible Bewegungen und Sprünge erkennen und korrigieren.

Digitale Karten

Die Berechnung des wahrscheinlichsten Wegs kann auch Zusatzinformationen wie Umgebungskarten einbeziehen. Die Genauigkeit der Lokalisierung erhöht sich dadurch signifikant.

Digitale Karten können entweder aus möglichen Laufwegen bestehen (Positivkarten), nur nicht betretbare Bereiche enthalten (Negativkarten) oder die baulichen Bedingungen wie Stockwerke, Wände oder Türen repräsentieren (Realkarten). Bei der Fahrzeugnavigation ist es üblich, Positivkarten einzusetzen. Diese enthalten Straßen und Wege sowie wichtige Metadaten wie die Fahrrichtung in Einbahnstraßen oder Geschwindigkeitsbegrenzungen. Positivkarten sind hier sinnvoll, da die befahrbaren Straßen und Wege nur einen Bruchteil der Fläche eines Landes einnehmen.

In Gebäuden, Hallen oder auf Werksgeländen sind Laufwege dagegen nur durch wenige Hindernisse begrenzt. Hier bieten sich Negativ- oder Realkarten an. Während Positivkarten für die Fahrzeugnavigation in mehreren Standardformaten kommerziell erhältlich sind, hat sich für Karten in und um Gebäude bisher kein Standard entwickelt.

Übung macht den Meister

Die Stärke des Fingerprintings liegt in der Berücksichtigung umgebungsspezifischer Eigenschaften. Mehr noch: Das Fingerprinting-Verfahren profitiert nachgerade von einer inhomogenen Signalausbreitung, bedingt durch Häuser, Wände, Durchgänge und andere Hindernisse. In einem Gang von einem Meter Breite beispielsweise macht sich die Positionierungsungenauigkeit vorwiegend entlang der Laufrichtung bemerkbar, nicht jedoch in der Breite. Ein Innenbereich ist daher am besten mit zwei bis vier Meter Genauigkeit im Mittel beschrieben, jedoch mindestens raumgenau. Die Lokalisierung ist auch in mehrstöckigen Gebäuden problemlos möglich und die Unterscheidung von Ebenen durch die meist sehr massive Bauweise der Stockwerksdecken sehr sicher, sofern auf jeder Etage genug Access Points senden.

Viel hilft aber nicht viel: Es genügt, in jedem Raum einen Fingerabdruck zu ermitteln und keine Lücken von mehr als fünf bis zehn Metern (innen) beziehungsweise 15 bis 25 Metern (außen oder in Hallen) zu lassen. In der Praxis zeigt sich, dass dichtere Referenzpunktwolken das Ergebnis nicht merklich verbessern, aber den Rechenaufwand beim Lokalisieren deutlich erhöhen.

Das manuelle Sammeln von Fingerabdrücken ist jedoch nur in begrenzten Arealen praktikabel. Das Fraunhofer IIS (Institut für Integrierte Schaltungen) setzt in Innenstädten für diesen Zweck auf sogenannte Einmessboxen. Sie besitzen eine GPS-Einheit in Kombination mit präzisen Inertialsensoren (zum Beispiel Beschleunigungssensoren und elektronische Kompasse). Diese Einmessboxen können ohne manuellen Eingriff Fingerabdrücke sammeln, wenn man sie durch die Stadt bewegt.

Die Lokalisierung über Differential GPS erlaubt auch in Städten eine Positionsbestimmung mit einer mittleren Genauigkeit von wenigen Dezimetern, die dank der Inertialsensorik auch bei Ausfall des GPS-Signals noch bis zu 10 Minuten weiter besteht. Überdachte Passagen beispielsweise stellen damit für die Einmessbox kein Problem dar. In der Nürnberger Innenstadt haben die Boxen beispielsweise bei Messfahrten fast 40.000 Fingerabdrücke gesammelt. Aktuell wird die Innenstadt auf einer Fläche von 25 Quadratkilometern vermessen.

Die Umgebung ändert sich

Selbst bei unveränderter Infrastruktur können sich die Ausbreitungsbedingungen verändern. Beispielsweise kommen durch das Ein- und Auslagern von Gütern in einer Lagerhalle Hindernisse hinzu oder verschwinden. Bereits nach kurzer Zeit spiegeln daher die trainierten Referenzdaten die aktuellen Verhältnisse nur noch grob wider – die Genauigkeit sinkt.

Einen Weg, mit dieser Dynamik umzugehen, hat das Fraunhofer IIS zusammen mit der Firma SEP Logistik AG realisiert. SEP nutzt die WLAN-Lokalisierung zur Positionsbestimmung von Gabelstaplern in Warenlagern. Das System berechnet den optimalen Weg eines anstehenden Fahrauftrags für einen Palettentransport und teilt den Transportauftrag einem Gabelstapler zu. Für die Lokalisierung des Gabelstaplers kommt ein Fingerprinting-System zum Einsatz. Da der aktuelle Standort jeder Palette in allen drei Dimensionen bekannt ist, können bei jedem Aufladen aktuelle Referenzdaten für den Standort aufgezeichnet werden. So bleibt die Fingerabdruckdatenbank aktuell.

Kommen und Gehen

Im öffentlichen Bereich unterliegt die WLAN-Infrastruktur noch häufigeren Änderungen: Anwohner stellen neue Access Points auf oder ziehen mit ihren Geräten um. Manche WLANs werden per Zeitschalter nur zu bestimmten Tageszeiten aktiviert oder für die Dauer eines Urlaubs abgeschaltet. Bauliche Veränderungen beeinflussen die Signalausbreitung.

Ein Algorithmus mit erweiterter Abgleichsphase löst auch dieses Problem. Er erkennt gegenüber den Referenzdaten hinzugekommene oder fehlende Stationen. Diese Daten kann der Nutzer als Aktualisierungsvorschläge an einen Dienst übermitteln und bekommt im Gegenzug aktuelle Referenzdaten für die Lokalisierung. Die Aktualisierungsvorschläge werden zentral bewertet, mit den Rückmeldungen anderer Nutzer verglichen und zur Pflege der Referenzdatenbank verwendet. Das Verfahren erfasst die Dynamik in der dezentralen innenstädtischen WLAN-Infrastruktur und minimiert den Aufwand zur Pflege der Referenzdatenbasis.

In der Praxis

Prominentes Beispiel ist derzeit Apples iPhone, das zur Ortung unter anderem auf den Dienstanbieter Skyhook setzt. Demgegenüber steht das Fraunhofer IIS, das Mitte Januar in Nürnberg ein stadtweites Testsystem gestartet hat, um im öffentlichen Raum neue Anwendungen auf der Grundlage der Ortung per WLAN zu erproben. Dabei werden in erster Linie Anbieter von Location Based Services, Hersteller von Endgeräten, Kartenlieferanten und Netzbetreiber ihre Komponenten und Dienste im Realbetrieb testen.

Das Tochterunternehmen IT2media von Müller Medien und Map and Route realisieren zum Beispiel ortsabhängige Dienste wie Taxiruf, Restaurantführer, Apotheken-, Hotel- und Parkplatzsuche. Die T-Systems plant auf Basis der autarken WLAN-Lokalisierung, ihren Geschäfts- und Industriekunden neue Dienste wie eine Fahrzeugführung auf Betriebsgeländen anzubieten. Die Cruso AG und Gaschba arbeiten an Lokalisierungs- und Hilfsdiensten für touristische Führungssysteme und Rollatoren, die VAG Verkehrs-Aktiengesellschaft Nürnberg an einer spurgenauen Lokalisierung von Bussen zur verbesserten Einsatzplanung in Betriebshöfen.

Endanwender können über die angebotenen Location Based Services die WLAN-Lokalisierung nutzen. Die vom Fraunhofer IIS entwickelte Software sichert dabei dem Nutzer eine autarke Lokalisierung auf seinem mobilen Endgerät zu. Auch kann er – wie von GPS gewohnt – eine kontinuierliche Lokalisierung nutzen, allerdings mit dem Bonus, dass auch in Gebäuden eine metergenaue Ortung funktioniert.

Die Testumgebung ist offen für weitere Partner. Nach einer ersten Betriebsphase werden diese und weitere Dienste auf andere deutsche und europäische Städte ausgedehnt. Die Ergebnisse des großflächigen Tests sollen auch als Grundlage für eine international angestrebte Standardisierung der Schnittstellen für ortsabhängige Dienste dienen.

Die Firma Skyhook verrät die Details ihres Verfahrens nicht, gibt aber an, auf Fingerprinting zu setzen. Hierzu führt die Firma regelmäßig Messfahrten mit speziellen Messfahrzeugen durch, die einmal pro Sekunde die empfangenen Signalstärken zusammen mit den MAC-Adressen, einem Zeitstempel und dem Ort erfassen. Die Datenbasis umfasst derzeit rund 23 Millionen Access Points und ihre Standorte in insgesamt 2800 Städten. Bislang hat Skyhook vor allem Städte in den USA erfasst.

In Deutschland gibt es den Skyhook-Dienst bislang nur in einigen Großstädte wie Berlin, Hamburg, Frankfurt und Hannover, wobei er lediglich in Berlin einigermaßen flächendeckend ist. Skyhook verspricht eine Genauigkeit von bis zu 20 Metern. Es kommt derzeit unter anderem für die Lokalisierungsdienste von Apples iPhone und des iPod touch zum Einsatz. Das Skyhook-System kann wie die Lösung des Fraunhofer IIS einen GPS-Empfänger simulieren und so auch mit handelsübliche Navigationsanwendungen kooperieren.

Datenbanken wie mobileaccess.de oder wigle.net sammeln seit Jahren weltweit die Positionen von Access Points. Die wigle.net-Community hat beispielsweise durch Wardriving-Fahrten und andere Messungen mittlerweile über elf Millionen WLANs eingetragen. Die Datenbank ist frei zugänglich und könnte prinzipiell auch als Basis für ein Multilaterionsverfahren zur Positionsbestimmung genutzt werden. In deutschen Städten reicht die Datendichte jedoch oftmals nicht für eine akzeptable Genauigkeit aus. (bbe/ola)

Literatur

[1] Jean-Marie Zogg, Dusan Zivadinovic, GPS im Haus, Ortung per Handy: Funktion und Verfeinerung, c't 20/04, S. 222