Multilateration: Indoor-Positionsbestimmung mit Bluetooth Low Energy 1/2

Die Nutzung von Navigationsanwendungen ist heute sehr weit verbreitet und häufig gefragt. Unter freiem Himmel ist die Positionierung mittels Satellitennavigation wie beispielsweise Galileo oder GPS die etablierte Lösung. Da innerhalb von Gebäuden allerdings kein zuverlässiger Satellitenempfang besteht, muss die Positionsbestimmung dort auf andere Weise erfolgen. Während meiner Bachelorarbeit im vergangenen Jahr setzte ich mich vor allem mit dem Thema der Positionsbestimmung mit Bluetooth Low Energy (BLE) auseinander.
Die wichtigsten Erkenntnisse möchte ich nun in zwei Blogbeiträgen kurz wiedergeben. Dabei gehe ich auf zwei verschiedene Ansätze zur Positionsbestimmung ein: Multilateration und Fingerprinting (zu Teil 2). Ziel war herauszufinden, wie sich die Positionsbestimmung mit handelsüblichen Smartphones umsetzen lässt, statt mit spezieller Hardware.

Testszenario zur Evaluation

Um die beiden Verfahren vergleichen zu können, habe ich ein Bereich des Büros von synyx mit BLE-Beacons versehen. Wie in der Grafik zu sehen ist, habe ich einen möglichst heterogenen Bereich mit sowohl einem langen Flur und Meetingräumen als auch einem offeneren Pausenbereich gewählt. An den schwarz markierten Positionen habe ich Beacons angebracht und an den grünen Positionen habe ich Messungen der Beacon-Signale aufgezeichnet, die ich dann zur Evaluation verwendet habe.

Grundriss der Räume des Testsetups mit Markierungen der Positionen der BLE-Beacons und der Positionen der Messungen für die Evaluation.

Herausforderungen

In diesem Experiment habe ich untersucht, wie präzise die Positionsbestimmung unter schwierigen Umständen funktioniert. Damit gemeint ist einerseits eine heterogene Umgebung mit vielen Wänden, Türen und anderen Objekten, die zur Dämpfung und Reflexion von Signalen führen. Andererseits verwendete ich einfache, handelsübliche BLE-Beacons. Zum Einsatz kamen Beacons der Hersteller RadBeacon und Blukii, sowie bereits vorhandene Acer-Tablets, welche als virtuelle Beacons fungierten.

Prinzip Multilateration

Voraussetzung für die Multilateration sind Beacons, welche sich in der Umgebung befinden und deren Positionen bekannt sind. Die Beacons senden regelmäßig Signale, die von den Clients, beispielsweise Smartphones, empfangen werden.

Bei der Multilateration werden am Client zunächst die Signalstärken der sendenden Beacons erfasst. Anhand dieser Signalstärken werden die Distanzen zu den jeweiligen Beacons abgeleitet. Betrachtet man nun die Distanzen als Kreise mit gegebenem Radius und der jeweiligen Beacon-Position als Ursprung (P1, P2, P3), ergibt sich der Schnittpunkt aller Kreise als die gesuchte Position. Im Idealfall schneiden sich alle Kreise an einem Punkt. Um die Position im zweidimensionalen Raum eindeutig bestimmen zu können, sind mindestens drei Beacons notwendig. Daher ist dieses Verfahren auch unter dem Namen “Trilateration” bekannt.

Multilateration

Distanzbestimmung

Die Distanz zwischen Empfänger und Sender kann mit der folgenden Formel berechnet werden (siehe Grafik). Hierbei beschreibt RSSI (Received Signal Strength Indicator) die Signalstärke bei Empfang des Signals in dBm (Dezibelmilliwatt). Der Wert txPower dient zur Kalibrierung und repräsentiert den RSSI bei genau einem Meter Abstand. In meinem Experiment ergab sich für  die meisten Beacons ein Wert zwischen -60 und -65 dBm. Die “Raumkonstante” N beschreibt die Ausbreitung des Signals im Raum bzw. in der Umgebung. Je mehr Objekte vorhanden sind, welche die Signalausbreitung dämpfen, desto höher ist die Konstante. Dieser Wert muss empirisch ermittelt werden (durch Ausprobieren). Im leeren Raum wäre N=2, in den Räumlichkeiten bei synyx wurden bei einem Wert von ca. 3 die besten Ergebnisse erzielt. Die Werte txPower und N sind somit die Drehschrauben zum Kalibrieren der Distanzbestimmung.

Distanz-Formel

Erkenntnisse

Die durchschnittliche Genauigkeit der Positionsbestimmung betrug 3,8 Meter. Die hohen Abweichungen waren größtenteils der Tatsache geschuldet, dass sich in der Testumgebung viele Objekte befinden, welche die Signalausbreitung stark beeinflussen und somit die Distanzberechnung verfälschen. Außerdem wurden die Signalstärken durch das “Frequency Hopping” beeinflusst. Frequency Hopping ist Teil des BLE-Standards und bezeichnet das regelmäßige zufällige Wechseln der Sendefrequenz. Die unterschiedlichen Frequenzen führen zur unterschiedlichen Ausbreitung im Raum und somit zu unterschiedlichen Empfangsstärken. In der folgenden Grafik sind die Schwankungen des Frequency Hopping bei gleichbleibender Distanz zu sehen. Der blaue Graph zeigt die rohen RSSI-Daten, der grüne Graph stellt hier den Median dar. Die Anwendung von Median- und Durchschnittsfilter konnte die starken Schwankungen des Frequency-Hopping jedoch nicht  ausgleichen.

RSSI im zeitlichen Verlauf

In der folgenden Grafik sind die Werte beim Vorbeigehen an einem Beacon dargestellt. In den rohen RSSI-Daten lässt sich das Annähern und anschließende Entfernen vom Beacon bereits erkennen. Der hier im grünen Graphen dargestellte Durchschnittsfilter kann das Rauschen des Signals glätten, wobei auch eine gewisse Latenz damit einhergeht.

RSSIs in Bewegung

Fazit und Ausblick

Für das Szenario der Navigation in Büroräumen ist die Multilateration ohne weitere Optimierung nicht geeignet. Bei den Abweichungen in der Positionsbestimmung kann nicht eindeutig zu einem Meetingraum navigiert werden. Dennoch kann das Verfahren Multilateration die richtige Wahl sein, wenn die Umgebung weniger Störfaktoren aufweist oder die Genauigkeit der Positionsbestimmung ausreichend ist.

Im folgenden Blogbeitrag werde ich auf das Verfahren Fingerprinting eingehen.
Spoiler: Es ist genauer!