21C3 Schedule Release 1.1.7

21st Chaos Communication Congress
Lectures and workshops

Speakers
Picture of Peter Ibach Peter Ibach
Schedule
Day 1
Location Saal 3
Start Time 19:00 h
Duration 01:00
INFO
ID 232
Type Lecture
Track Hacking
Language german
FEEDBACK

Positionsbezogene Ad-hoc Kollaboration über WLAN

Wir haben ein System zur Positionsbestimmung mobiler Systeme basierend auf WLAN Signalstärke-Auswertung entwickelt. Es arbeitet rein softwarebasiert, d.h. bei den mobilen Systemen ist außer einer konventionellen WLAN-Karte keine weitere Hardware erforderlich. Die WLAN Access Points können beliebig verteilt bzw. ggf. sogar mobil sein und es sind weder Eingriffe an der AP-Hardware noch an der Software nötig.

Unsere Versuche am Uni-Campus Berlin-Adlershof zeigen in typischen Büroumgebungen eine Positionierungsgenauigkeit im einstelligen Meter-Bereich. Die Softwarekomponenten des Positionierungssystems stehen zum freien Download zur Verfügung und können für Experimente oder Anwendungen genutzt werden.

Das Internet drängt in den mobilen Bereich. 2005 wird die Milliardengrenze der vernetzten Menschen und Geräte überschritten werden. 2007 werden es 1,5 Milliarden Nutzer sein, wobei dann bereits geschätzte 70% überwiegend drahtlosen Zugang haben werden. Die Anwendungen in einem "drahtlosen und allgegenwärtigen Netzt" werden sich dabei verändern: Typischerweise spielt die Position und die Interaktion mit der räumlich nahen Umgebung bei der mobilen Nutzung eine viel stärkere Rolle. Dies wird eine enge Verzahnung von physikalischen und informatorischen Prozessen mit sich bringen. Navigationslösungen weisen uns heute bereits den Weg durch den Verkehrsdschungel. Geoinformationsdienste und weitere Location Based Services warten auf expandierende Märkte. In wenigen Jahren werden voraussichtlich viele Milliarden mobiler und eingebetteter Systeme – einschließlich durch RFID-Chips bestückte Konsumobjekte – einen weit gehenden Echtzeitüberblick über Positionen und Zustände von Menschen und Objekten ermöglichen. Wir begegnen bei diesen Entwicklungen, die dramatische Veränderungen unserer Geschäfts- und Alltagsprozesse bedeuten werden, einer Reihe von Zukunftsängsten aber auch Chancen und technologischen Herausforderungen.

Drahtlose Ortung ist dabei eine der Schlüsseltechnologien. Satelliten-Ortung und terrestrische Ortung in GSM-Mobilfunknetzen haben bislang diesen Bereich geprägt. Diese Techniken lassen allerdings einige Wünsche offen. Erwünscht werden vor allem Systeme, die gleichzeitig Outdooor und Indoor-Ortung bei geringen Kosten, hoher Genauigkeit, globaler Einsatzfähigkeit und problemloser Interoperabilität ermöglichen. Um dies zu erreichen, kommen vermehrt Ortungstechniken auf, die sich auf WLAN-Infrastrukturen im ohne Anmeldung nutzbaren 2,4 GHz Frequenzband stützen und ohne spezielle Hardwareerweiterungen auskommen. Durch ausgeklügelte Algorithmen sind Indoor-Ortungsgenauigkeiten in typischen Büroumgebungen bis zu 1 m erreichbar. Diverse Anbieter treten mit unterschiedlichen Verfahren bereits in dieses Marktsegment, das sich kurz vor dem Sprung in den Massenmarkt befindet.

Wir haben am Institut für Informatik der HU-Berlin ein System zur WLAN-Positionsbestimmung entwickelt, dass Signalstärkecharakteristiken der empfangbaren Access Points und Peers auswertet und daraus auf die eigene Position schließt. Die Genauigkeit steigt dabei mit der Zahl vorvermessener Referenzpunkte (Pre Calibration). Schon wenige mit ihrer Signalcharakteristik erfasste Referenzpunkte reichen aus (in unserem Gebäude etwa 10 je Etage), um in typischen Büroumgebungen Positionsgenauigkeiten auf Raumgranularität, d.h. mit einer Genauigkeit von etwa 1-5 m zu erreichen. Referenzpunkte erhält man dadurch, dass die Nutzer per Point-andClick innerhalb einer auf ihren mobilen Geräten dargestellten Karte ihre aktuelle Position angeben. (Wir gehen gegenwärtig davon aus, dass alle Nutzer in der Lage sind, die Position akkurat einzugeben. Aber wir denken bereits über Erweiterungen nach, ob und wie sich eine Fehleingabe ggf. erkennen und tolerieren läßt.) Für diese Ortsangabe werden dann die aktuellen Signalstärkemessungen incl. eines Zeitstempels archiviert. Das Archiv wird in der gegenwärtigen prototypischen Implementation auf einem Server verwaltet. Zu Testzwecken ohne Verfügbarkeitsgarantie kann dazu unser Server von der HU-Berlin genutzt werden (phl.informatik.hu-berlin.de). Auch die Server-Software ist frei zum Download verfügbar, so dass eigene Server aufgesetzt werden können. Die Client-Server-Kommunikation wird aber in Zukunft durch eine reine Peer-to-peer-Lösung ersetzt. Die Ortung funktioniert in beliebigen WLANInfrastrukturen, wobei die Genauigkeit mit größerer Dichte und Zahl von Access Points, teilnehmenden Peer-Systemen und vorkalibrierten Referenzpunkten steigt.

Durch den kooperativen Austausch von vermessenen Referenzpunkten können Peers Ihre Position auch dann bestimmen, wenn sie selbst noch nicht an diesem Ort waren. Soweit wir wissen, bieten wir mit diesem kooperativen Austausch von Referenzmessungen das erste Signalstärke-basierte Ortungsverfahren an, das eine Positionierung auch in unbekannten Umgebungen ermöglicht – was für die meisten Positions-basierten Anwendungen unerlässlich ist. (Die Positionsbestimmung funktioniert aber ansonsten auch gut Stand-alone, ohne weitere PeerTeilnehmer oder den Zugriff zu einem Server). Eine Korrelationsanalyse erlaubt es dabei, die von den Peers mit oft sehr unterschiedlicher Hardware (verschiedene WLAN-Karten oder Antennen) ermittelten Signalstärke-Messdaten, so aufeinander umzurechnen, dass Peers wechselseitig durch den Austausch von Messdaten ihre Positionierungsgenauigkeit verbessern.

Das angewendete probabilistische Verfahren stellt die von einem Peer gemessenen Signaldifferenzen ins Verhältnis zu den räumlichen Abständen zwischen dem Peer und allen weiteren, mit einer Signalcharakteristik und einer Positionsschätzung bekannten stationären oder mobilen Referenzpunkte (also alle bekannten aktuellen Werte von Access Points oder Peers sowie die mit einem Zeitstempel versehene Referenzmesspunkte). Durch eine MaximumLikelyhood-Schätzung ermittelt dabei ein Peer seine wahrscheinlichste Position so, dass die Summe der quadrierten Abweichungen zu den Referenzobjekten minimal wird. Alle Objekte zusammen bilden so einen Graph, dessen Kanten die Differenzen der Signalcharakteristiken repräsentieren. Die Abstandfunktion der Signalcharakteristiken ist so gewählt, dass die Kantenlängen eine gute Schätzung der räumlichen Distanz liefert.

Natürlich stören Hindernisse sowie Richtwirkungen der Antennen die Korrelation von Signalstärkedifferenz und räumlicher Distanz zum Teil erheblich. So lange aber mehrere Signalquellen parallel beobachtbar sind, und ausreichend viele, dicht liegende Referenzpunkte vermessen sind, gleichen sich die Effekte statistisch so aus, dass sich überraschend gute Positionsschätzungen ergeben – wie unsere Experimente bestätigen.

Dabei geht die Genauigkeit der Referenzmessung sowie die Korrelation der remoten Hardware zur eigenen Hardware durch eine Gewichtung der Messdaten ein. Ein selbst lernendes Verfahren (Auto Calibration), dass "Alterung" der Messwerte und schwankende Korrelationen zu bestimmten Referenzzeiträumen berücksichtigt, erlaubt es ferner, sich auch ohne manuelle Eingriffe in bestimmten Grenzen an sich verändernde Bedingungen der Infrastruktur anzupassen – etwa an den Ausfall von Access Points oder an die Veränderung der Signalbedingungen durch Wettereinflüsse.

Unter der Bedingung, dass sich alle Objekte auf einer Ebene befinden kann der sich ergebende Graph auf eine Map (GIF-Bild) der Räumlichkeiten projiziert werden. (Wir arbeiten noch an der Erweiterung auf dreidimensionale Visualisierung für mehrgeschossige Gebäude bzw. bergiges Terrain mit großen Höhenunterschieden.) Eine Justierung der Map erfolgt durch Angabe von absoluten Referenzpunkten, für die Geokoordinaten bekannt sind. Bewegen sich die Peers nicht zu dynamisch, stabilisiert sich der Graph nach kurzer Zeit und man erhält in der Map einen Überblick über die eigene Position sowie die Positionen der anderen Peers (falls diese Ihre Daten freigeben). Durch eine präzise Justierung der Map lassen sich leicht für jede Position Geokoordinaten berechnen, so dass Anwendungen, die sonst eine GPS-Satellitenortung voraussetzen, auch ohne GPS nutzbar werden. Der kooperative Austausch von Referenzdaten prädestiniert das Verfahren für Anwendungen, die auf räumlicher Nähe basierende ad-hoc Teambildung und Zusammenarbeit erfordern.

Für den Teilnehmerkreis beim CCC dürfte das Verfahren insbesondere deshalb interessant sein, da es "peer controlled" ist. Anders als bei anderen drahtlosen Positionierungs-Systemen im 2,4 GHz Frequenzband wird die eigene Position vom jeweiligen Peer selbst bestimmt, statt durch externe Überwachung ermittelt. Jeder Peer hat die volle Hoheit über seine Positionsdaten und kann festlegen, unter welchen Bedingungen und an wen die Daten weitergeleitet werden und ob dies anonym, unter einem Pseudonym oder voll identifizierbar stattfindet. Entsprechende peer-topeer Kommunikation mit einer speziellen Access Control Policy, die dazu nach bestimmten Regeln die Freigabe von Positionsdaten organisiert (z.B. Freigabe nur zu den Arbeitszeiten an autorisierte Kollegen) ist Gegenstand zukünftiger Arbeiten (noch nicht implementiert).