R. A.
Verfahren zur Selbstkalibrierung von Lokalisationssystemen basierend auf drahtlosen
Sensornetzen
ISBN: 978-3-8428-1453-0
Herstellung: Diplomica® Verlag GmbH, Hamburg, 2011
Zugl. Bayerische Julius-Maximilians-Universität Würzburg, Würzburg, Deutschland,
Diplomarbeit, 2010
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden und der Verlag, die Autoren oder
Übersetzer übernehmen keine juristische Verantwortung oder irgendeine Haftung für evtl.
verbliebene fehlerhafte Angaben und deren Folgen.
© Diplomica Verlag GmbH
http://www.diplomica.de, Hamburg 2011
Inhaltsverzeichnis
1
Einleitung
5
2
SNoW Bat: Ein 3D Lokalisationssystem
7
2.1
SNoW Bat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2
HashSlot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3
Lokalisationsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.3.1
Trilateration und Multilateration . . . . . . . . . . . . . . . .
9
2.3.2
IVoted3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.3
Vergleich der Lokalisationsverfahren . . . . . . . . . . . . . . . 14
2.4
Distanzfilterung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3
Selbstkalibrierungsverfahren
18
3.1
Das Explorer-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.1
Der Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.2
Lokalisierung des mobilen Knotens . . . . . . . . . . . . . . . 20
3.1.3
Kalibrierung der Anker . . . . . . . . . . . . . . . . . . . . . . 23
3.2
Das Include-Exclude-Verfahren
. . . . . . . . . . . . . . . . . . . . . 30
3.2.1
Schritt 1: Einschränkung von A
m
durch Inklusion . . . . . . . 30
3.2.2
Schritt 2: Einschränkung von A
m
durch Exklusion . . . . . . . 31
3.2.3
Schritt 3: Einschränkung der Ankergebiete A
a
i
durch Exklusion 34
3.2.4
Implementierung und Umgang mit fehlerbehafteten Distanzen
34
3.2.5
Voraussetzungen für eine erfolgreiche Einschränkung der Gebiete 39
3.3
Das Distribute & Erase-Verfahren . . . . . . . . . . . . . . . . . . . . 47
3.3.1
Der Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.2
Lokalisationsalgorithmen . . . . . . . . . . . . . . . . . . . . . 50
3.3.3
Konsistente Ankeranordnung und match-Vorgang . . . . . . . 53
3.3.4
Bewertung der Lokalisationen . . . . . . . . . . . . . . . . . . 56
3.3.5
Verbesserung der Lokalisationsgenauigkeit . . . . . . . . . . . 60
3.3.6
Adaptive Kalibrierung . . . . . . . . . . . . . . . . . . . . . . 70
4
Ergebnisse
74
4.1
Kalibrierungs- und Lokalisationsgenauigkeit . . . . . . . . . . . . . . 75
4.2
Vor- und Nachteile der Selbstkalibrierungsverfahren . . . . . . . . . . 79
5
Zusammenfassung und Ausblick
84
3
Literaturverzeichnis
86
Abbildungsverzeichnis
88
Tabellenverzeichnis
90
1 Einleitung
Die Fortschritte der letzten Jahre in der Elektronik und drahtlosen Kommunika-
tion haben die Entwicklung von Netzwerken, bestehend aus kleinen, billigen und
energieeffizienten Sensorknoten ermöglicht. Ein Sensorknoten kann Eigenschaften
der Umgebung, wie z.B. die Temperatur, wahrnehmen, Daten verarbeiten und mit
anderen Sensorknoten kommunizieren, typischerweise über einen Funkkanal. Draht-
lose Sensornetzwerke (engl. wireless sensor networks (WSN)) können Aufgaben in
den verschiedensten Bereichen übernehmen, und es werden immer neue Einsatzorte
gefunden. Einige Beispiele, in denen WSN eingesetzt werden:
· Die Überwachung der Wasserqualität durch Proben ist arbeitsintensiv und
kann deshalb nur lokal erfolgen. WSNs können große Gebiete überwachen und
schneller vor Gefahren warnen.
· Katastrophen-Erkennung: Waldbrände und Wasserfluten können früher er-
kannt und präziser lokalisiert werden, wenn gefährdete Gebiete mit WSNs
überwacht werden.
· Die Ortung von Waren, Fahrzeugen und Personen kann die Verwaltung von
Lagern erleichtern.
Sowohl das Forschungs- als auch das kommerzielle Interesse an WSNs ist in den letz-
ten Jahren exponentiell gestiegen [11]. Das Magazin Technology Review
1
bezeich-
nete im Jahr 2003 drahtlose Sensornetzwerke als eine von "10 emerging technologies
that will change the world"[16].
Obige Beispiele machen aber deutlich, dass Sensordaten häufig erst in Verbindung
mit einer Orts- und Zeitangabe zu gebrauchen sind. Die Position eines Sensorknoten
kann sowohl statisch als auch mobil sein. Während mobile Knoten fortlaufend loka-
lisiert werden müssen, können Knoten mit statischen Positionen einmalig nach der
Installation vermessen werden. Das händische Ermitteln der Positionen für alle sta-
tischen Anker ist allerdings sehr aufwendig und nur mit entsprechendem Equipment
genau. Um die Dauer der Installationsphase zu verkürzen, wurden bereits mehrere
Verfahren zur Selbstkalibrierung untersucht.
1
Technology Review ist ein Magazin des Massachusetts Institute of Technology (MIT), das über
Technologien berichtet, die das Leben verändern.
5
6
1 Einleitung
Capkun et al. haben in [9] ein Verfahren vorgestellt, das auf der Messung von Di-
stanzen zwischen den statischen Knoten basiert. Die Knoten erzeugen lokale Ko-
ordinatensysteme, aus denen anschließend ein globales Koordinatensystem für das
WSN erzeugt wird. In vielen WSN, insbesondere in SNoW Bat [7], kann die Distanz
zwischen zwei statischen Knoten ohne Anpassung der Hardware aber nicht bestimmt
werden.
Für die Lokalisation von Sensorknoten in Freiluft haben Sichitiu and Ramadurai
[19] ein GPS-basiertes Verfahren vorgestellt. Statt jeden Knoten mit einem teuren
GPS-Empfänger auszustatten, wurde nur ein mobiler Knoten mit GPS eingesetzt.
Die Positionen der statischen Knoten wurde durch die Distanz zwischen den stati-
schen und dem mobilen Knoten und der mobilen Position ermittelt. GPS-basierte
Verfahren eignen sich aufgrund des schlechten Empfangs aber nicht für den Einsatz
in Räumen. Desweiteren ist die erreichte Lokalisationsgenauigkeit von 1-2 m unzu-
reichend genau.
Eine höhere Genauigkeit (0,35 m) erzielten Moses et al. [14], durch den Einsatz
von Sensoren, die sowohl die time-of-arrival (TOA) als auch die direction-of-arrival
(DOA) messen konnten. Auch die DOA kann in den meisten WSNs nicht ohne Ver-
änderung der Hardware gemessen werden.
Menegatti et al. haben die Einsatzmöglichkeiten von WSNs in Verbindung mit
AMRs (engl. Autonomous Mobile Robots) untersucht. In [13] haben sie die Selbst-
kalibrierung eines WSN mit einem AMR vorgestellt, der seine Position mit Hilfe von
zwei Odometer an den Antriebsrädern bestimmen kann.
Ziel dieser Arbeit ist die Entwicklung eines Selbstkalibrierungsverfahrens für draht-
lose Sensornetze, das lediglich auf kleinen, kostengünstigen und energieeffizienten
Sensorknoten basiert. Die statischen Knoten sind mit einem Ultraschallempfänger,
die mobilen Knoten mit einem Ultraschallsender ausgestattet. Statische als auch
mobile Knoten besitzen einen Funk-Transceiver zur Kommunikation.
2 SNoW Bat: Ein 3D
Lokalisationssystem
Grundlage dieser Diplomarbeit ist das am Lehrstuhl für Technische Informatik (In-
formatik V) an der Bayerischen Julius-Maximilians-Universität, Würzburg entwi-
ckelte 3D Lokalisationssystem SNoW Bat [7, 15]. In diesem Kapitel wird SNoW
Bat, das Kommunikationsprotokoll HashSlot [1, 5] sowie einige der verwendeten
Lokalisationsalgorithmen vorgestellt.
2.1 SNoW Bat
SNoW Bat ist ein komplett drahtloses WSN und erlaubt präzise und schnelle 3D
Lokalisationen. Es basiert auf SNoW
5
-Sensorknoten [4], die ebenfalls am Lehrstuhl
für Technische Informatik (Informatik V) entwickelt wurden. Jeder Sensorknoten
ist entweder ein statischer Knoten a
i
, mit bekannter Position, auch Anker genannt,
oder ein mobiler Knoten m
j
, mit unbekannter Position. Für die Ortung eines mobilen
Knotens m
j
muss die euklidische Distanz d
i,j
zu mindestens drei Ankern a
i
gemessen
werden. Jeder Anker besitzt einen Ultraschallempfänger, jeder mobile Knoten einen
Ultraschallsender. Anker als auch mobile Knoten besitzen einen Funk-Transceiver
für die Kommunikation. Die Distanz wird nach dem TDoA (engl. time difference
of arrival) Verfahren bestimmt. Der mobile Knoten sendet ein Funkpaket zur Syn-
chronisation und anschließend ein Ultraschallsignal. Das Funksignal breitet sich mit
v
radio
= 299.792.458
m
s
aus (im Vakuum), während das Ultraschallsignal sich wesent-
lich langsamer ausbreitet. Die Ausbreitungsgeschwindigkeit von Ultraschall hängt
stark vom Medium ab, bei 20
C und 101.3 kPa (mittlere Luftdruck der Atmo-
sphäre auf Meereshöhe) beträgt die Geschwindigkeit v
U S
= 343
m
s
. Jeder Anker, der
das Funk- und Ultraschallsignal empfangen hat, kann aus der Zeitdifferenz zwischen
den Ankunftszeitpunkten die Distanz zum mobilen Knoten berechnen. Für eine ge-
naue Distanzberechnung müssen die SNoW
5
-Knoten, also die Ankunftszeitpunkte
der Signale, präzise und unabhängig von der Systemauslastung ermitteln können.
Dies wird in SNoW Bat durch die Interrupt-Zeitstempel des präemptive Echtzeit-
betriebssystems SmartOS [6, 2] erreicht.
Die Anker, die eine Distanz zum mobilen Knoten berechnen konnten, senden ein DV
(engl. distance vector) zum mobilen Knoten zurück. Ein DV enthält u.a. die berech-
7
8
2 SNoW Bat: Ein 3D Lokalisationssystem
nete Distanz als auch die Position des Absenders. Das Kommunikationsprotokoll
HashSlot regelt die Übertragung der DVs zum mobilen Knoten, der sich mit den
empfangen DVs lokalisieren kann. Die Ortung eines mobilen Knotens kann also in
vier Phasen gegliedert werden: 1. Zeitsynchronisation (mittels Funk), 2. Distanzmes-
sung (mit TDoA), 3. DVs zum mobilen Knoten senden und 4. Positionsberechnung.
2.2 HashSlot
Würden alle Anker, die sowohl das Funkpaket als auch das Ultraschallsignal emp-
fangen haben, sofort nach der Berechnung der Distanz beginnen, diese zu senden,
würden sich die Funkpakete der sendenden Anker gegenseitig stören. Ein mögliches
Verfahren, das die Wahrscheinlichkeit für Paketkollisionen von verschiedenen Sen-
dern auf dem gleichen Kanal verringert, ist CSMA/CA (engl. carrier sense multiple
access/collision avoidance). CSMA/CA ist weit verbreitet in der drahtlosen Kom-
munikation, zum Beispiel eingesetzt in der IEEE-Norm IEEE 802.11, bringt jedoch
einige Nachteile für WSNs mit sich. Beispielsweise können Kollisionen nur verringert,
nicht ausgeschlossen werden, und es kann keine feste Zeitspanne für den Empfang
aller Distanzen angegeben werden. Die benötigte Quittierung (ACK) verzögert au-
ßerdem die komplette Kommunikation und verbraucht Energie.
Aus diesem Grund setzt SNoW Bat das TDMA Protokoll (engl. time division mul-
tiple access) HashSlot [1, 5] ein. Jeder beteiligte Anker bekommt einen exklusiven
Übertragungs-Slot zugewiesen, weshalb HashSlot kollisionsfrei ist. Die Slot-Nummer
kann jeder Anker anhand seiner Position autonom berechnen. Voraussetzung für die
Verwendung von HashSlot ist, dass die Anker in einem Gitter angeordnet sind. Eine
präzise Positionierung der Anker ist allerdings nicht nötig, jeder Anker muss sich
lediglich in der richtigen Gitterzelle befinden. Bei einer Gitterzellenlänge von L ist
somit eine Abweichung von
±
L
2
in x- und y-Richtung tolerierbar.
Abbildung 2.1: Anordnung der Anker entlang eines Gitters
In drahtlosen Sensornetzen, in denen ein mobiler Knoten lokalisiert werden soll, ist
die Anordnung der Anker entlang eines Gitters meist sowieso gegeben. Soll eine
flächendeckende Lokalisation möglich sein, müssen an jeder Position, die der mobile
2.3 Lokalisationsalgorithmen
9
Knoten erreichen kann, sich mindestens drei Anker im Ultraschallkegel des mobilen
Knoten befinden.
2.3 Lokalisationsalgorithmen
Im Folgenden wird auf die verwendeten Lokalisationsalgorithmen eingegangen. Alle
vorgestellten Verfahren sind exakte Lokalisationsverfahren, die die Position eines
mobilen Knotens m mit Hilfe von mindestens drei Ankern a
i
sowie den euklidischen
Distanzen d
i
zwischen m und den Ankern a
i
bestimmen. Bei einer 2D-Lokalisation
muss aus der gemessenen Distanz
directdist(m, a
i
) :=
(x
m
- x
a
i
)
2
+ (y
m
- y
a
i
)
2
+ (z
m
- z
a
i
)
2
und der Höhe h der Ankerebene die
grounddist(m, a
i
) :=
(x
m
- x
a
i
)
2
+ (y
m
- y
a
i
)
2
berechnet werden. Damit die folgenden Formeln sowohl für die 2D- als auch die 3D-
Lokalisationen gültig sind, gilt d
i
:=
grounddist(m, a
i
)
bei einer 2D-Lokalisation,
directdist(m, a
i
)
bei einer 3D-Lokalisation.
Abbildung 2.2: 3D- und 2D-Lokalisation
2.3.1 Trilateration und Multilateration
Mit der Trilateration [18] lässt sich die Position eines mobilen Knotens m anhand
von genau drei DVs bestimmen. Die Lokalisation bei einer 2D-Trilateration / 3D-
Trilateration entspricht der Bestimmung eines Schnittpunkts von drei Kreisen /
drei Kugeln mit Radius d
i
, i
{1, 2, 3}, die sich an den Positionen (x
a
i
, y
a
i
) /
10
2 SNoW Bat: Ein 3D Lokalisationssystem
(x
a
i
, y
a
i
, z
a
i
) befinden.
Bei einer 3D-Trilateration existieren meist zwei Schnittpunkte, wovon einer ausge-
schlossen werden kann, da der Schnittpunkt sich außerhalb des Raums befindet. Die
Multilateration [18, 17] ermöglicht es, auch mehr als drei Distanzen und dazuge-
hörige Positionen bei der Lokalisation zu berücksichtigen, was bei fehlerbehafteten
Distanzmessungen zu einer besseren Lokalisationsgenauigkeit führt. Eine Trilatera-
tion entspricht einer Multilateration mit nur drei Distanzen.
Bei exakten Distanzen d
i
zwischen dem mobilen Knoten m und den Ankern a
i
ist mit
der Tri- und Multilateration die exakte Position von m bestimmbar. In der Realität
sind die gemessenen Distanzen d
i
allerdings fehlerbehaftet, es gilt also d
i
= ^
d
i
+e
i
mit
den Messfehlern e
i
und den realen Distanzen ^
d
i
. Für e
i
= 0 können auch keine oder
mehrere Schnittpunkte existieren. Die herkömmliche Lösung für das Problem des
fehlenden eindeutigen Schnittpunkts ist die Verwendung einer Maximum-Likelihood-
Schätzung, die eine Position mit kleinstem mittlerem quadratischen Fehler schätzt.
Dazu wird das Gleichungssystem Ax = b gelöst. Für n Distanzmessungen gilt:
A =
-2
(x
1
- x
n
)
(y
1
- y
n
)
(z
1
- z
n
)
(x
2
- x
n
)
(y
2
- y
n
)
(z
2
- z
n
)
..
.
(x
n
-1
- x
n
) (y
n
-1
- y
n
) (z
n
-1
- z
n
)
x =
x
u
y
u
z
u
b =
(d
2
1
- d
2
n
)
- (x
2
1
- x
2
n
)
- (y
2
1
- y
2
n
)
- (z
2
1
- z
2
n
)
(d
2
2
- d
2
n
)
- (x
2
2
- x
2
n
)
- (y
2
2
- y
2
n
)
- (z
2
2
- z
2
n
)
..
.
(d
2
n
-1
- d
2
n
)
- (x
2
n
-1
- x
2
n
)
- (y
2
n
-1
- y
2
n
)
- (z
2
n
-1
- z
2
n
)
(2.1)
mit der Ankerposition (x
i
, y
i
, z
i
) des i-ten Ankers und der Distanz d
i
[18].
Gilt n > 3, existieren also mehr Gleichungen als Variablen, ist das Gleichungssys-
tem überbestimmt. Damit das lineare Gleichungssystem Ax = b eindeutig lösbar
ist, müssen die Spaltenvektoren der Koeffizientenmatrix linear unabhängig sein. Die
Ankerpositionen (x
i
, y
i
, z
i
) bei einer 2D-Lokalisation dürfen daher nicht kollinear
bzw. bei einer 3D-Lokalisation nicht koplanar sein.
In der Realität befinden sich die Anker allerdings häufig in einer Ebene, beispiels-
weise an der Decke oder dem Boden, weshalb eine 3D-Lokalisation mit obige Glei-
chungen nicht möglich ist.
Zur Bewertung einer Positionsschätzung (x, y, z) nach Trilateration bzw. Multilate-
ration kann die difference function [11, S. 400]
=
n
i
=1
| (x - x
i
)
2
+ (y
- y
i
)
2
+ (z
- z
i
)
2
- d
i
|
2.3 Lokalisationsalgorithmen
11
verwendet werden, die die durchschnittliche Differenz, zwischen den aus der Positi-
onsschätzung ermittelten Distanzen und den gemessen Distanzen berechnet.
Trilateration nach Eckert et al.
Eine weitere Möglichkeit, mehr als drei Anker bei der Lokalisation zu berücksichti-
gen, haben Eckert et al. [10] vorgestellt. Bei n gemessenen DVs werden t
s =
n
3
Teilmengen gebildet. Wurde t < s gewählt, beispielsweise um Berechnungszeit zu
sparen, wählt der Algorithmus die Teilmengen aus, die das größte Dreieck aufspan-
nen. Für jede der t Teilmengen wird mit der Trilateration eine Position x
j
bestimmt,
wobei j =
{1, . . . , t}. Aus den t Positionen x
j
wird abschließend durch koordinaten-
weise Median- bzw. Mittelwertbildung oder durch einen Kalman-Filter eine finale
Position x berechnet.
2.3.2 IVoted3D
Sowohl die Trilateration / Multilateration als auch andere Lokalisationsverfahren
wie die WCL (engl. Weighted Centroid Localization) [8, 18] oder das Min-Max-
Verfahren [12, 18] berücksichtigen die Fehlercharakteristik der empfangenen Distan-
zen nicht. Baunachs IVoted3D-Algorithmus
1
[3] versucht a priori-Wissen über die
Fehlercharakteristik zu nutzen, um falsche Distanzen bei der Lokalisation gar nicht
erst zu berücksichtigen.
Abbildung 2.3 zeigt die Wahrscheinlichkeitsdichtefunktion der Fehlercharakteristik,
die im realen WSN SNoW Bat gemessen wurde und auch im verfügbaren Simulator
implementiert ist. Eine genaue Erklärung der Fehlercharakteristik folgt in Kapitel
2.4. Mit einer Wahrscheinlichkeit von ca. 60% ist der Distanzfehler kleiner als
=
0, 1 und mit ca. 0,5% ist der Distanzfehler kleiner als
-1, 1 oder größer als 1, 1.
IVoted3D versucht, fehlerhafte Distanzen bei der Lokalisation nicht zu berücksich-
tigen, um 3D Lokalisationen mit einer Genauigkeit von
2
3 zu erzielen. Um
dies zu erreichen, sollen nur gemessene Distanzen, die höchstens
± von den realen
Distanzen abweichen, berücksichtigt werden. Die echte Distanz muss also in einem
2 -Schlauch um die gemessene Distanz liegen (siehe Abbildung 2.4 links). Schnei-
den sich zwei -Schläuche im zweidimensionalen, entsteht idealisiert ein Quadrat
(siehe Abbildung 2.4 Mitte) und im dreidimensionalen ein Würfel mit Seitenlänge
2 . Zwei beliebig platzierte Punkte in einem Quadrat oder Würfel können maximal
= 2
d von einander entfernt sein, wobei d
{2, 3} die Dimension angibt und
der Diagonalen entspricht. Wenn die echten Distanzen wirklich maximal
± von
den gemessenen Distanzen abweichen, befindet sich insbesondere der Schnittpunkt
1
Der IVoted3D-Algorithmus wird in der Literatur auch als pVoted-Algorithmus bezeichnet
12
2 SNoW Bat: Ein 3D Lokalisationssystem
Abbildung 2.3: Wahrscheinlichkeitsdichtefunktion der Fehlercharakteristik
der echten Distanzen und somit der Aufenthaltsort des mobilen Knotens, höchs-
tens vom berechneten Schnittpunkt entfernt. Abbildung 2.4 zeigt rechts den im
dreidimensionalen Fall entstehenden Würfel mit Seitenlänge 2 .
Abbildung 2.4: Epsilonschlauch bei fehlerbehafteten Messungen
Der IVoted3D-Algorithmus bildet aus den gemessenen DVs Tripel. Für jedes Tripel
{dv
i
, dv
j
, dv
k
} wird der Schnittpunkt der drei Kugeln an den Positionen a
i
, a
j
und
a
k
, mit den Radien d
i
, d
j
und d
k
berechnet. Damit IVoted3D die Schnittpunkte der
Kugeln effizient bestimmen kann, müssen alle Anker sich in einer Ebene befinden.
Ist dies nicht der Fall, weil die Decke beispielsweise nicht plan ist, können die Anker
dennoch rechnerisch in eine Ebene verschoben werden (siehe Kapitel 3.1.3).
Existiert ein Schnittpunkt der Kugeln, ist dieser eindeutig, bis auf eine Spiegelung
entlang der Ankerebene. Es existieren also höchstens zwei Schnittpunkte, wovon
sich einer außerhalb des Raums befindet. Konnte ein Schnittpunkt ermittelt wer-
den, wird dieser Punkt gespeichert und die Distanz zu allen anderen gespeicherten
2.3 Lokalisationsalgorithmen
13
Schnittpunkten verglichen. Ist die Distanz zwischen zwei Schnittpunkten
, stim-
men diese Schnittpunkte füreinander, und der voter-Zähler für die Schnittpunkte
wird bei beiden Punkten um eins inkrementiert. Aus den so entstandenen Punkt-
wolken wird schließlich mittels WCL [18] der finale Schnittpunkt bestimmt. Dazu
wird der Schnittpunkt mit den meisten Stimmen, also dem höchsten voter-Zähler,
ermittelt und zusammen mit allen Schnittpunkten, die für diesen Punkt gestimmt
haben, eine neue Position aus den gewichteten Koordinaten der Schnittpunkte be-
rechnet.
Zur Bewertung der berechneten Position stellt der IVoted3D-Algorithmus die Me-
triken consistency und precision zur Verfügung. Die consistency bewertet eine Po-
sitionsschätzung anhand der maxV oters, der expV oters und der Anzahl der Stim-
men voters. Der Wert maxV oters gibt die Anzahl der maximal möglichen Stim-
men an, die wiederum von der Anzahl der Distanzen abhängt. expV oter gibt die
Anzahl der erwarteten Stimmen an, die ebenfalls von der Anzahl der Distanzen
sowie der Wahrscheinlichkeit abhängt, dass der Distanzfehler größer ist. Es gilt
consistency
[0 : 1], wobei
consistency
[0 : 0.5]
wenn voters
expV oters
(0.5 : 1]
wenn voters > expV oters.
Abbildung 2.5: Berechnung der consistency
Die precision berücksichtigt den Schnittwinkel der -Schläuche. Abbildung 2.6 zeigt
den Schnitt zweier -Schläuche mit verschiedenen Schnittwinkeln. Die entstandene
Fläche und somit die Unschärfe ist im rechten Schnitt wesentlich größer.
Mit dem IVoted3D Algorithmus kann optional eine Prädiktion der zukünftigen Posi-
tion, anhand der bereits lokalisierten Positionen erstellt werden, die in die folgenden
Lokalisationen mit einfließt. Fährt der mobile Knoten einen Pfad ab, kann durch
die Vorhersage eine signifikante Verbesserung der Lokalisationsgenauigkeit erzielt
14
2 SNoW Bat: Ein 3D Lokalisationssystem
Abbildung 2.6: Schnitt zweier Epsilonschläuche mit verschiedenen Schnittwinkeln
werden. Für die Kalibrierung macht eine Prädiktion allerdings wenig Sinn, denn die
zu kalibrierenden Anker befinden sich nicht auf einem Pfad, und bei einigen Ka-
librierungsmethoden ist auch die Position des mobilen Knoten zufällig, sodass die
Grundlage für eine Prädiktion fehlt. In Kapitel 2.3.3 werden verschiedene Lokalisa-
tionsverfahren mit und ohne Prädiktion gegenübergestellt.
2.3.3 Vergleich der Lokalisationsverfahren
Zum Vergleich der verschiedenen vorgestellten Lokalisationsverfahren wurden 1.000
Lokalisationen auf einem Pfad simuliert. Für alle Verfahren wurde der durchschnittli-
che Positionsfehler f des mobilen Knotens m für die 1.000 Lokalisationen berechnet:
f =
1
n
n
i
=1
(p
real
.x
- p
est
.x)
2
+ (p
real
.y
- p
est
.y)
2
+ (p
real
.z
- p
est
.z)
2
p
real
/ p
est
bezeichnet die echte / geschätzte Position des mobilen Knotens und
n
1.000 gibt die Anzahl der erfolgreichen Lokalisationen an. Der IVoted3D Algo-
rithmus liefert bei stark fehlerbehafteten Distanzmessungen, bei denen kein Schnitt-
punkt entsteht, überhaupt keine Positionsschätzung, weshalb die erfolgreichen Lo-
kalisationen auch kleiner als 1.000 sein können. In Tabelle 2.1 sind die berechneten
durchschnittlichen Fehler sowie die Anzahl der gültigen Lokalisationen für die ver-
schiedenen Verfahren dargestellt. Die angegeben Werte entsprechen dem Mittelwert
aus drei Simulationen.
Sowohl die Trilateration nach Eckert als auch der IVoted3D-Algorithmus können
durch die Prädiktion die Genauigkeit sowie die Anzahl der gültigen Lokalisationen
stark verbessern, da der mobile Knoten einen Pfad abgefahren ist. Desweiteren wird
deutlich, dass gute Distanzschätzungen beim IVoted3D-Algorithmus, unabhängig
von der Prädiktion, mit hoher Wahrscheinlichkeit erkannt werden können und somit
bei großen consistency-Werten eine hohe Genauigkeit erzielt werden kann. Für die
Berechnung des consistency-Wertes benötigt der IVoted3D-Algorithmus allerdings
Kenntnis über die Fehlercharakteristik, die insbesondere bei der Kalibrierung nicht
immer bestimmbar ist.
2.4 Distanzfilterung
15
Verfahren
Fehler f [mm]
gültige Lokalisationen
IVoted3D mit Prädiktion
3,28
997
IVoted3D mit Prädiktion
1,31
748
(consistency
0.33)
IVoted3D ohne Prädiktion
40,75
897
IVoted3D ohne Prädiktion
1,38
113
(consistency
0.33)
2D Trilateration
1.034
1.000
2D Multilateration
11,27
1.000
Trilateration nach Eckert (Median)
5,91
1.000
Trilateration nach Eckert (Kalman)
3,18
1.000
Tabelle 2.1: Lokalisationsalgorithmen im Vergleich
2.4 Distanzfilterung
Bei allen im Folgenden vorgestellten Selbstkalibrierungsverfahren hängt die erreich-
bare Kalibrierungsgenauigkeit stark von den Distanzfehlern ab. Insbesondere beim
Explorer-Verfahren (Kapitel 3.1) müssen Distanzfehler von Anfang an vermieden
werden, da einmal vorhandene Fehler bis zum Schluss der Kalibrierung vorhanden
bleiben. In Kapitel 2.3.2, Abbildung 2.3 wurde bereits die Wahrscheinlichkeitsdich-
tefunktion der Fehlercharakteristik abgebildet.
Circa 60% aller Distanzmessungen besitzen einer Fehler e
[- : + ] = [-0, 1 :
+0, 1]. Diese Fehler sind aufgrund von Fertigungstoleranzen der Ultraschallsen-
der und -empfänger sowie der Timerauflösung der Mikrocontroller und des Echt-
zeitbetriebssystems (1S in SmartOS) etc. nicht vermeidbar. Bei der Bestimmung
der Flugzeit des Ultraschallsignals kann es außerdem passieren, dass die berechnete
Flugzeit um
± eine Periode von der realen Flugzeit abweicht. Die Abweichung von ±
einer Periode entspricht einer Abweichung von
± = ±8, 58 mm. Vereinzelte größe-
re Ausreißer können ebenfalls vorkommen, wenn beispielsweise der Mikrocontroller
eines Ankers bei der Ankunft der Signale sich im Kernelkontext befindet und der
Zeitstempel deshalb nicht rechtzeitig gesetzt werden kann.
Tabelle 2.2 zeigt die gemessenen Fehlerwahrscheinlichkeiten.
Distanzfehler
Wahrscheinlichkeit
[-0, 1 : +0, 1]
58%
[-1, 1 : -0, 1) (+0, 1 : +1, 1]
36, 3%
(- : -1, 1) (+1, 1 : +]
5, 8%
Tabelle 2.2: Wahrscheinlichkeiten für den Distanzfehler ohne Filterung
16
2 SNoW Bat: Ein 3D Lokalisationssystem
Distanzfehler größer 1, 1 oder kleiner
-1, 1 treten also sehr selten auf und können
durch mehrfache Distanzmessung von der gleichen Position erkannt werden. We-
sentlich schwieriger ist die zuverlässige Filterung von Positionsfehlern größer bzw.
kleiner
± . Da die Wahrscheinlichkeit für einen Positionsfehler von 0 mm am größten
ist, kann in den meisten Fällen, die echte Distanz durch mehrfache Distanzmessung
und anschließende Medianbildung gut angenähert werden. Zu jedem Anker a
i
im
Ultraschallkegel wird also eine Folge von Distanzen d
1
, . . . , d
k
gespeichert und der
Median ~
d
i
der Folge berechnet. In mehreren Simulationen hat sich k = 100 als guter
Wert herausgestellt. Bei weniger als 100 Distanzmessungen erhöht sich der durch-
schnittliche Distanzfehler merklich und bei mehr als 100 Distanzmessungen ist nur
noch eine kleine Abnahme des durchschnittlichen Distanzfehlers beobachtbar.
Es existieren allerdings auch Positionen, an denen mehr Distanzen mit einem Posi-
tionsfehler von ca.
± gemessen werden als Distanzen mit einem Positionsfehler von
ca. 0 mm. An diesen Positionen wird daher auch durch den Median ein Distanzfeh-
ler von ca.
± erzeugt. Da bei solchen Distanzfolgen dennoch auch einige Distanzen
mit einem Fehler von ca. 0 mm existieren, hat sich die Filterung von Folgen mit
einer hohen Varianz als sinnvoll erwiesen. Um die eigentliche Varianzberechnung
unabhängig von einzelnen Ausreißern zu machen, werden zuerst die größten und
kleinsten 5% aller Distanzmessungen verworfen. Nur wenn die Varianz der übrigen
90 Distanzen kleiner als eins ist, wird der Median berechnet und mit der geschätzten
Distanz eine Position berechnet.
Um die Effektivität der Distanzfilterung zu untersuchen, wurde eine Simulation mit
2.500 Distanzmessungen an zufälligen Positionen im Raum und perfekten Ankerpo-
sitionen durchgeführt. Abbildung 2.7 zeigt die gemessene Dichtefunktion der Feh-
lercharakteristik ohne und mit Filterung. In Tabelle 2.3 sind die gemessenen Fehler-
wahrscheinlichkeiten nach der Filterung notiert.
Distanzfehler
Wahrscheinlichkeit
[-0, 1 : +0, 1]
99, 6%
[-1, 1 : -0, 1) (+0, 1 : +1, 1]
0, 4%
(- : -1, 1) (+1, 1 : +]
0, 0%
Tabelle 2.3: Wahrscheinlichkeiten für den Distanzfehler mit Filterung
Durch die Filterung können also Distanzfehler
± sehr zuverlässig gefiltert werden.
Große Distanzfehler (> 1, 1 oder <
-1, 1) treten gar nicht mehr auf. Der durch-
schnittliche Distanzfehler konnte in diesem Beispiel von 3,12 mm auf 0,13 mm und
der maximale Distanzfehler von 75,6 mm auf 8,9 mm gesenkt werden.
2.4 Distanzfilterung
17
Abbildung 2.7: Dichtefunktion der Fehlercharakteristik ohne und mit Filterung
3 Selbstkalibrierungsverfahren
Ziel dieser Arbeit war es, Verfahren zur Selbstkalibrierung zu entwickeln, die das
aufwendige, händische Vermessen von Ankern ersetzen sollen. Dazu wurden ver-
schiedene Ansätze und Algorithmen entwickelt, die im folgenden vorgestellt werden.
Alle Verfahren wurden im Simulator locSim v0.9, der vom Lehrstuhl für Technische
Informatik (Informatik V) implementiert wurde, entwickelt und getestet. Es wird
davon ausgegangen, dass die Kalibrierung der echten Hardware ebenfalls PC unter-
stützt laufen kann. Für den eigentlichen Betrieb des WSN ist allerdings kein PC
mehr nötig.
Im Folgenden wird davon ausgegangen, dass sich nur ein mobiler Knoten im WSN
befindet, der mit m bezeichnet wird. SNoW Bat unterstützt allerdings mehrere mo-
bile Knoten, und es können auch alle Verfahren mit mehreren mobilen Knoten an-
gewandt werden.
Mit Ankerknoten oder kurz Ankern werden in der Literatur meist statische Kno-
ten mit bekannter Position bezeichnet. Hier werden sowohl statische Knoten mit
bekannter Position (kalibrierte Anker) als auch Knoten mit unbekannter Positi-
on (unkalibrierte Anker) als Anker bezeichnet. Die n Anker im WSN werden mit
a
i
: i
{1, 2, . . . , n} abgekürzt. Ist eine Unterscheidung notwendig, wird explizit
erwähnt, ob der Anker a
i
seine Position kennt oder nicht.
Bei der Kalibrierung muss für jeden Knoten k zwischen der realen Position und der
geschätzten Position unterschieden werden. Die reale / geschätzte Position wird im
Folgenden mit p
k,real
/ p
k,est
abgekürzt. Distanzmessungen zwischen dem mobilen
Knoten m und einem Anker a
i
sind nur von den realen Positionen abhängig, die
aber unbekannt sind. Die Lokalisationsalgorithmen arbeiten mit den geschätzten
Positionen und versuchen diese so genau zu schätzen, dass der Positionsfehler f
k
=
|p
k,est
- p
k,real
| möglichst klein wird.
3.1 Das Explorer-Verfahren
Die Grundidee dieses Verfahrens ist, die Rollen von statischen und mobilen Kno-
ten zu vertauschen. Ausgehend von mindestens drei Ankern mit bekannter Position
im Ultraschallkegel eines mobilen Knotens m, kann m lokalisiert werden. Bei jeder
18
3.1 Das Explorer-Verfahren
19
Lokalisation werden auch Distanzen zu statischen Knoten gemessen, die ihre Posi-
tion noch nicht kennen. Deren Position kann aber durch drei bekannte Positionen
von m und den gemessenen Distanzen berechnet werden. Im Idealfall kann m so
den kompletten Raum erkunden und auf der Erkundungstour alle statischen Anker
kalibrieren. Einmal vorhandene Positionsfehler werden bei diesem Verfahren aber
immer weiter propagiert. Positions- und Distanzfehler müssen darum von Anfang
an vermieden werden.
Da das Explorer-Verfahren dreidimensionale Kalibrierungen ermöglichen soll, wur-
de für alle Lokalisationen der IVoted3D-Algorithmus verwendet. IVoted3D hat in
mehreren Versuchen bei bekannter Fehlercharakteristik die genauesten Positions-
schätzungen geliefert (siehe Kapitel 2.3.3), und die Metrik consistency ermöglicht
außerdem eine Filterung schlechter Positionsschätzungen, was die Vermeidung von
Positionsfehlern erleichtert.
3.1.1 Der Algorithmus
Algorithm 1: Der Explorer-Algorithmus
1
while room not explored do
2
move mobile node;
// forward on path
3
measure and filter distances;
// (see section 2.4)
4
locate mobile node;
/* all distances are useless without the position of the mobile
node
*/
5
if mobile node not locatable then
6
continue;
7
end
/* each DV containes the mobile position and the distance to an
anchor (calibrated or uncalibrated)
*/
8
store all distance vectores;
9
foreach anchor a do
/* only if more than minDV distance vectores are stored, a
will be localized (minDV
3)
*/
10
if more than minDV DVs to a stored then
11
localize a;
12
end
13
end
14
end
Initial muss der mobile Knoten so platziert sein, dass sich mindestens drei kalibrierte
Anker im Ultraschallkegel des mobilen Knotens befinden. Da jede Distanzmessung
mit einem Fehler behaftet ist, zum Beispiel aufgrund von Fertigungstoleranzen der
20
3 Selbstkalibrierungsverfahren
Ultraschallsender / -empfänger, haben sich fünf kalibrierte Anker als stabiler her-
ausgestellt. Um die auftretenden Fehler in den Distanzmessungen so gut wie möglich
zu eliminieren, werden mehrere Distanzmessungen von der gleichen Position gestar-
tet. Mit Varianzmethoden werden anschließend die Distanzen gefiltert (siehe Kapitel
2.4). Mit 100 Messungen pro Position kann der durchschnittliche Fehler bereits dras-
tisch gesenkt werden. Anhand den Distanzen zu den kalibrierten Ankern kann die
Position des mobilen Knotens mit den in Kapitel 2.3 vorgestellten Lokalisationsver-
fahren bestimmt werden. Kann aufgrund von zu großen Fehlern oder nicht hinrei-
chend vielen kalibrierten Ankern die Position des mobilen Knotens nicht bestimmt
werden, sind alle gemessenen Distanzen nutzlos und können verworfen werden. Im
Falle einer erfolgreichen Lokalisation des mobilen Knotens, werden alle gemessenen
Distanzen zusammen mit der Position des mobilen Knotens gespeichert. Existiert
ein Anker, für den mindestens minDV Distanzen gespeichert wurden, kann dieser
Anker kalibriert werden. Dabei ist minDV
3 ein Parameter, der je nach Fehler-
charakteristik angepasst werden muss. Er muss hinreichend groß gewählt werden,
um einzelne stark fehlerbehaftete Distanzmessungen ausgleichen zu können, darf
aber auch nicht zu groß gewählt werden, weil sonst die Kalibrierung unnötig lange
dauert. Für die Fehlercharakteristik, die in SNoW Bat gemessen wurde und im Si-
mulator implementiert ist, hat sich minDV = 8 als guter Wert herausgestellt. In
allen folgenden Lokalisationen des mobilen Knotens können die neu kalibrierten An-
ker verwendet werden. Nachdem alle Anker, zu denen genügend gemessen Distanzen
existieren, kalibriert wurden, kann der mobile Knoten eine neue Position einnehmen
und von vorne begonnen werden.
Ein weiterer Parameter, der in Abhängigkeit von der Fehlercharakteristik, dem Pfad
des mobilen Knotens und minDV gewählt werden muss, ist die Distanz d
m
, zwi-
schen zwei Positionen des mobilen Knotens auf dem Pfad. Ist d
m
zu klein gewählt,
dauert die Kalibrierung der Anker unnötig lange, und die für die Kalibrierung be-
nötigten minDV Distanzen werden von nah beieinander liegenden Messpunkten
durchgeführt. Im Durchschnitt werden durch weit voneinander entfernte Messpunk-
te allerdings bessere Positionsschätzungen erzielt. Ist d
m
zu groß gewählt, kann es
passieren, dass keine minDV Distanzen zu einem Anker a
i
gemessen werden und
der Anker a
i
nicht kalibriert werden kann. Passiert das bei mehreren Ankern, kann
der mobile Knoten sogar in einen Bereich ohne hinreichend viele kalibrierte Anker
vordringen, weil der Algorithmus den mobilen Knoten, unabhängig von den Kali-
brierungszuständen der Anker, um d
m
auf dem Pfad verschiebt.
3.1.2 Lokalisierung des mobilen Knotens
Aufgrund der fehlerbehafteten Distanzmessungen ist eine Lokalisation des mobi-
len Knotens ohne weitere Filterung der Distanzen nicht hinreichend genau. Große
Distanzfehler führen zu schlechten Positionsschätzungen und somit zu schlecht kali-
brierten Ankern. Da die Ankerpositionen wieder die Grundlage für eine neue Loka-
Ende der Leseprobe aus 91 Seiten
- nach oben
Details
- Arbeit zitieren
- , 2010, Verfahren zur Selbstkalibrierung von Lokalisationssystemen basierend auf drahtlosen Sensornetzen, Hamburg, Bedey Media GmbH, https://www.diplom.de/document/228494
Ähnliche Arbeiten
Kommentare
- Noch keine Kommentare.
Deutschlands größter Sharing Community
Jetzt Zusammenfassungen, Skripte und Klausuren kostenlos downloaden!
Uniturm.de
Ihre Vorteile als Autor
Geld verdienen Für jedes verkaufte Exemplar erhalten Sie Autorenhonorar - bis zu 40%.Kostenlose Buchveröffentlichung
Als eBook-Studie im Original und / oder auf Wunsch zusätzlich als hochwertiges Fachbuch in unserem renommierten Buchverlag.
Renommee als Fachbuchautor
Präsentieren Sie sich als Fachfrau oder Fachmann in Ihrem Fachgebiet und machen Sie sich bekannt.
Persönliche Betreuung
Unser Lektorat wird Sie persönlich betreuen und ist auch telefonisch unter 040-655992-14 erreichbar.
Weltweit im Buchhandel
Ihr Buch ist weltweit im Buchhandel und Online-Buchhandel wie z.B. amazon erhältlich.
Jetzt Autor werden!