Algorithmen

Ausgewählte Algorithmen zur Positonsbestimmung:

Nachfolgend sind die Positionierungsalgorithmen aufgezählt, die auch in der MaWIPS zum Einsatz gekommen sind.

  • Nearest Neighbor in Signal Space (NNSS)
  • k-Nearest Neighbor in Signal Space (k-NNSS)
  • History Monitoring Algorithmus (HMA)
  • Multilayer Perzeptron (MLP)

 

Nearest Neighbor in Signal Space (NNSS):

Der Nearest Neighbor in Signal Space (NNSS) Algorithmus wurde erstmals im Jahre 2000 von Microsoft Research implementiert. Dieser basiert auf dem einfachen Nearest Neighbor (NN) Algorithmus. Das Ziel ist die Auswahl eines Signalmusters aus den Referenzdaten, dessen größte Ähnlichkeit zu der aktuellen Messung aufweißt. Als Basis wird eine Trainingsdatenmenge aus einem Merkmalsraum benötigt, in diesem Falle sind dies die gesammelten Signalmuster aus der Trainingsphase. Eine Stichprobe mit den Elementen ri, i = 1, … , M sind den Klassen Mi, i = 1, … , M zugeordnet und besitzen den Umfang Ti. Die gesamte Trainingsdatenmenge hat den Umfang:

Trainingsdatenmenge

Zusätzlich wird ein Abstandsmaß benötigt, das zur Bestimmung des Abstandes zwischen zwei Merkmalsvektoren des gleichen Typs eingesetzt werden kann. Hier wird das euklidische Abstandsmaß verwendet, das folgende Form aufweißt:

euklidische Abstandsmaß

Dieses wird aus einem bestimmten Merkmalsvektor (ri,n) aus der Trainingsdatenmenge und einen zu vergleichenden Merkmalsvektor (rn) aus einer Momentanmessung berechnet. Dabei gilt:

Merkmalsvektor

Ist das kleinste euklidische Abstandsmaß (d) aus dem Merkmalsraum ermittelt wurden, ist dieses unmittelbar der nächste Nachbar der Momentanmessung. So lautet die Unterscheidungsfunktion:

Unterscheidungsfunktion

Demzufolge werden dessen verknüpften Positionsdaten ausgewählt und der unbekannten Position zugeordnet.

Tabelle euk. Abstand

Die obenstehende Tabelle beschreibt drei Signalmuster (ID 12, 18 und 23) die in der Trainingsphase aufgenommen wurden und ein aktuell aufgezeichnetes Muster (ID 0) aus der Positionierungsphase. Anhand des euklidischen Abstandsmaßes, welches für jedes Signalmuster berechnet wurde, wird das Kleinste bestimmt. In diesem Fall wird der Eintrag mit der ID 23 als nächster Nachbar ermittelt und dessen Positionsdaten dem aktuellen Messdatum zugeordnet.
Die Genauigkeit des Nearest Neighbor Algorithmus wird von Microsoft Research, wie in der untenstehende Tabelle dargestellt, mit einer mittleren Abweichung von 2,94 Meter bei 50 % aller Fälle angegeben.

NNSS Ergebnisse

Die Ergebnisse aus obensteheneder Tabelle wurden in einem Operationsgebiet mit einer Größe von 980 m2 und 70 Referenzmessungen erreicht. Es sind in der Trainings- und Positionierungsphase jeweils drei Access Points eingesetzt wurden.

Nearest Neighbor in Signal Space (k-NNSS):

Ein weiterer Algorithmus ist der k-Nearest Neighbor in Signal Space (k-NNSS) Algorithmus, der auf dem Basisalgorithmus NNSS aufbaut. Diese Variante bedient sich der k nächsten Nachbarn im Merkmalsraum, um die Position zu berechnen. Dies bedeutet, dass mehr als ein Signalmuster aus den Referenzdaten gesucht wird, welches die größte Ähnlichkeit mit dem aktuellen Messdatum aufweißt. Dazu wird ebenfalls das euklidische Abstandsmaß verwendet und über die gesamte Trainingsdatenmenge berechnet.

kNNSS Nachbarn

Nun werden die Nachbarn mit dem k kleinsten Abständen herangezogen und dessen zugeordneten Positionsdaten gemittelt. Die vorhergehende Abbildung illustriert diesen Sachverhalt mit k=3 ausgewählten Nachbarn (N1, N2, N3) mit dem kleinsten euklidischen Abstand. Der Punkt G stellt dabei die gemittelte Position dar und T die Stelle an der die Messung von Signalstärken erfolgte.

Im Gegensatz zum NNSS Algorithmus, welcher nur einen von drei Punkten aus der Abbildung der unbekannten Position zuordnen kann, wird durch die Mittelung der Positionsdaten eine höhere Genauigkeit erreicht. Der k-Nearest Neighbor in Signal Space Algorithmus wur- de von Microsoft Research implementiert und auf seine Genauigkeit untersucht. Nachfolgen- de Tabelle veranschaulicht das Verhältnis zur Anzahl von benachbarten Referenzpunkten und der daraus resultierenden mittleren Abweichung. Das verwendete Operationsgebiet beruht auf dem Aufbau wie aus Abschnitt NNSS, sowie drei eingesetzte Access Points in der Trainings- und Positionierungsphase.

kNNSS Ergebnisse

Bei k = 3 ist zu sehen, das die mittlere Abweichung starke Unterschiede zu einen bzw. fünf Nachbarn aufweißt. Die Ursache liegt in der Nähe der Nachbarn im Signalmuster. Diese zeigen zwar eine große Ähnlichkeit zu den aktuell gemessenen Signalmuster, jedoch liegen die physikalischen Koordinaten der jeweiligen Nachbarn weit auseinander. Bedingt durch die nachfolgende Mittelung der Positionsdaten, entsteht die signifikante Abweichung zum realen Standort.

History Monitoring Algorithmus(HMA):

Die Positionsbestimmung eines beweglichen Objektes kann anhand seines Bewegungsmuster bestimmt werden. Dabei handelt es sich um die Aufzeichnung von Positionsdaten aus vorangegangenen Ermittlungen, die bei der aktuellen Bestimmung der Position mit einfließen. Dadurch wird eine sprunghafte Veränderung der momentanen Position zu einer willkürlich weit entfernten verhindert. Auf dieser Grundlage basiert der von der Duke University entwickelte History Monitoring Algorithmus, kurz HMA. Der Grundgedanke war, den beschriebenen k-NNSS Algorithmus weiter zu verbessern und eine Tracking Möglichkeit zu schaffen. Der History Monitoring Algorithmus besteht aus einem History Vektor der Größe h und fünf Teilschritten, die nachfolgend beschrieben werden:

  • 1. Während das Objekt in Bewegung ist, werden periodisch Signalstärken gemessen, zum Beispiel eine Sekunde.
  • 2. Mit Hilfe des k-Nearest Neighbor in Signal Space Algorithmus werden die k nächsten Nachbarn bestimmt. Der Parameter k muss vordefiniert und konstant sein.
  • 3. Der History Vektor wird mit der Gruppe der k nächsten Nachbarn aktualisiert, indem der älteste Eintrag gelöscht und der Neuste an den Anfang des Vektors geschrieben wird.
  • 4. Berechnung des kürzesten Pfades beginnend von der Ältesten bis zur neusten Gruppe mithilfe einer einfachen Metrik (euklidische Abstandsmaß).
  • 5. Der Startpunkt des kürzesten Pfades ist die momentane Position des Objektes.
  • 6. Kontinuierliche Wiederholung der Teilschritte eins bis fünf.

Die nachfolgende Abbildung illustriert den History Monitoring Algorithmus. Der kürzeste Pfad ist als Linie dargestellt und dij bezeichnet den euklidischen Abstand zwischen den einzelnen Gruppen (Rahmen). Dieser kann auch als physikalischer Abstand der Positionen verstanden werden.

Um die Genauigkeit des HMA zu erhöhen, werden in der Trainingsphase mögliche Verbindungen zwischen den einzelnen Positionen festgelegt. Dies bedeutet, das der Aufbau des Operationsgebietes berücksichtigt werden kann, um eine Bewegung zum Beispiel durch Wände zu vermeiden. So wird für jede Position deren mögliche Nachbarpositionen bestimmt und gespeichert. Diese werden bei der Onlinephase ausgelesen und mit der aktuellen Messung verglichen, ob eine Verbindung bestehen kann. Ist dies nicht der Fall, wird die aktuelle Messung verworfen und eine neue vorgenommen.

Operationsgebiet

In der obenstehenden Abbildung ist ein Operationsgebiet zu sehen, welches einen Weg zwischen der Position 11 und der Position 8 beschreibt. Es besteht keine direkte Verbindung, sodass nur ein Weg über die Positionen 10 und 9 möglich wäre. Anhand einer aktuellen Messung, welche die Position 7 unter den nächsten Nachbarn ermittelt, wäre diese somit ausschließbar. Demzufolge wird der nächste passende Nachbar gesucht und verglichen.

Da es jedoch in der Praxis zu Fehlmessungen kommen kann, wird der Algorithmus um eine Neustartfunktion erweitert. Diese verhindert, das sich das Suchfenster in die falsche Richtung verschiebt und dadurch keine Position bestimmt werden kann. Dabei wird die Anzahl der Versuche erfasst und bei einer Überschreitung eines bestimmten Schwellwertes der Algorithmus neu gestartet. Dadurch erhält der HMA eine höhere Sicherheit bei der Ermittlung der Position.

hma Ergebnisse

Es wird die Größe des History Vektor von h = 6 und die Anzahl der Nachbarn von k = 3 als guter Kompromiss angesehen. Um so größer der History Vektor, desto höher der Rechenaufwand und demzufolge eine ungewünscht hohe Latenzzeit. Die obenstehende Tabeller zeigt die Genauigkeit des History Monitoring Algorithmus aus Versuchen der Duke University unter Verwendung von drei Zugriffspunkten.

Multilayer Perzeptron (MLP):

Als weiteres Verfahren kann ein mehrlagiges Perzeptron (MLP) mit Backpropagation-Algorithmus zur Positionsbestimmung eingesetzt werden. Dieses mehrlagige Perzeptron ist ein vorwärtsgekoppeltes neuronales Netzwerk und besteht aus drei oder mehr Schichten. Die letzte Schicht ist die Ausgabeschicht (Output-Layer). Sie stellt die einzige sichtbare Neuronenausgabe außerhalb des neuronalen Netzwerkes dar. Dementsprechend werden davorliegende Schichten als verdeckte Schichten (Hidden-Layer) bezeichnet, da diese keine Ausgaben liefern. Jede Schicht beinhaltet eine bestimmte Anzahl von Neuronen, die auch als Knoten bezeichnet werden. Dabei wird jedes Neuron mit den der folgenden Schicht verbunden, wie es die nachstehende Abbildung veranschaulicht. Entsprechend kann dieses neuronale Netzwerk als gerichteter Graph aufgefasst werden. Die Verbindungen zwischen den Neuronen werden als Kanten benannt und besitzen unterschiedliche Gewichte. Diese haben Einfluss auf die nachfolgenden Schichten und stellen daher das eigentliche Wissen dar.

Als Aktivierungsfunktion der Knoten wird eine sigmoide Funktion (siehe Abbildung 1) verwendet, da es sich hierbei um kognitive Prozesse handelt. Sie hat den Vorteil, das der Aktivitätslevel nach oben und nach unten begrenzt wird, sowie zu jeder Zeit differenzierbar ist. Sie weißt dabei folgende Form auf:

sigmoide Funktion

Die Aktivierungsfunktion stellt den Zusammenhang zwischen der Eingabe und dem Aktivitätslevel des jeweiligen Neurons dar.

Liniendiagrammsigmoide Funktion
Abb. 1 Liniendiagramm sigmoide Funktion

Die Vorteile der benannten sigmoiden Aktivierungsfunktion sind die Voraussetzung für den eingesetzten Backpropagations-Algorithmus. Mithilfe des Algorithmus werden die Gewichte angepasst, welches das Lernverfahren darstellt. Dabei wird dieses Verfahren in drei Schritte unterteilt:

1. Schritt: Forward-Pass
Der Eingabeschicht werden die entsprechenden Eingabemusterverktoren zugewiesen. Anschließend werden die Netzeingaben der Hiddenschichten bis hin zur Ausgabeschicht mit der Formel ( 1 ) berechnet sowie die jeweilige Netzausgabe mit der Formel ( 2 ).

AusgabeFormel 1
Formel 1

Hierbei bezeichnet netj die Netzeingabe, xi die Eingabe des Neurons i, wij die Gewichtung zwischen Neuron i und Neuron j, sowie n die Anzahl der Eingaben.

NetzausgabeFormel 2
Formel 2

2. Schritt: Fehlerbestimmung
Berechnung des mittleren quadratischen Fehlers des aktuellen Musters. Überschreitet der Fehler einen bestimmten Schwellwert, folgt der Backward-Pass, ansonsten wird die Lernphase beendet. Die Berechnung geschieht mit der Formel:

Fehlerberechnungsformel 3
Formel 3

dabei gilt, n sei die Anzahl der Muster, tj die tatsächliche Ausgabe und oj die berechnete Ausgabe.

3.Schritt: Backward-Pass
Für den Backward-Pass wird die 1. Ableitung der sigmoiden Funktion benötigt, die wie folgt lautet:

1. Ableitung sigmoide Funktion
Formel 4

Es wird für jedes Neuron der Ausgabeschicht der Fehler anhand der Formel ( 5 ) berechnet.

Fehlerberechnung Ausgabeschicht
Formel 5

Im Anschluss wird für alle Neuronen in der letzten Hiddenschicht der Fehler mit nachfolgender Formel berechnet:

Fehlerberechnung Hiddenschicht
Formel 6

Dabei bezeichnet δk den Fehler des aktuellen Neurons, den Fehler des Neurons aus der nächsten Schicht ωij und δj das Gewicht des aktuellen Neurons zum Neuronen der nächsten Schicht. Danach erfolgt die Anpassung der Gewichte mit einem Gradientenabstiegsverfahren. Hierbei wird mit einem zufälligen gewählten Gewicht begonnen. Folgend wird der Gradient bestimmt und anschließend um eine vorbestimmte Lernrate abgestiegen. Die so erhaltene Gewichtsänderung liefert den Gewichtsvektor, in dem wiederum der Gradient bestimmt wird. Dieses Verfahren wiederholt sich bis ein lokales Minimum erreicht ist.

Es wurde das unter dem Namen konjungierter Gradientenabstieg (conjugate gradient descent) bekannte Verfahren verwendet, das wie folgt definiert ist:

Gradientenabstiegsverfahren
Formel 7

Die Variable n bestimmt die Lernrate, α definiert die Schrittweite und Δ ωij die Gewichtsänderung

Um das mehrlagige Perzeptron anzulernen, wird eine bestimmte Anzahl von Trainingsdaten- sätzen dem Netz übergeben. Nach erfolgreichen Lernverfahren, wie oben beschrieben, ist das Netz trainiert und kann eingehende Muster klassifizieren. Die Eingabemuster bestehen bei der Positionsbestimmung mittels Wireless LAN aus den Signalstärken der jeweiligen Access Points. Die Ausgabe des Netzwerkes kann in Koordinaten erfolgen, die zwei- oder dreidimensional sind. Bedingt durch die sigmoidsche Funktion, dessen Wertebereich zwischen 0 und 1 liegt, müssen die Werte im Vorfeld skaliert werden. Dies geschieht unter Verwendung folgender Formel:

Skalierungsformel
Formel 8

Hierbei wird ein Wertebereich zwischen 0,1 und 0,9 gewählt, um zu verhindern, das das Netz zum Stillstand kommen kann. Dabei steht x für den Originalwert und y für den neuen skalierten Wert. Die Variablen xmax und xmin stehen jeweils für den maximalen und minimalen Wert des verwendeten Merkmals. Zum Beispiel liegen die Signalstärken im Bereich von -10 dBm und -90 dBm. Als Vorteil gegenüber den anderen Verfahren wird der geringere Speicherverbrauch benannt.

Die zu erwartende Genauigkeit wird mit einer mittleren Abweichung von 2,09 m unter Verwendung von fünf Access Points beschrieben. Als Operationsgebiet wurde ein Gebäude mit einer Grundfläche von ca. 800 m2 verwendet und an 154 vorbestimmten Messpunkten Signalmuster aufgenommen. Diese wurden dem verwendeten neuronalen Netz mit Single Hidden-Layer übergeben, wie es die Abbildung x.y illustriert. Die Eingabeschicht besteht aus maximal fünf Neuronen, die jeweils mit einer Signalstärke eines Access Point getestet werden. Der Hidden-Layer besitzt 16 Neuronen, die das beste Ergebnis lieferten. Weiterhin besteht die Ausgabeschicht aus zwei Neuronen, die die x- bzw. y-Koordinate repräsentieren.

Als positive Verbesserung der Genauigkeit des neuronalen Netzwerkes wird eine Kombination mit dem History Monitory Algorithmus vorgeschlagen, wie es nachfolgende Tabelle verdeutlicht.

MP Ergebnisse

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.