MagicMap Verfahren

aus Nomads, der freien Wissensdatenbank

zur MagicMap Übersicht

Das hybriden Ortungskonzept des an der HU Berlin entwickelten Funkortungssystems MagicMap enthält eine Normalisierung, um unterschiedliche Methoden der Distanzschätzung integrieren zu können. Zur Distanzschätzung können verschiedene Technologien zum Einsatz kommen, z.Zt. gibt es Implementationen für WLAN, GSM, Bluetooth und ZigBee. Dabei erfolgt die Fusionierung der Ortungsdaten nicht wie bislang üblich auf der Ebene der Objektkoordinaten, sondern bereits auf Ebene der Rohdaten der Sensoren. Dieses neue Verfahren erlaubt eine erhebliche Verbesserung der Genauigkeit und Abdeckung der Ortung.

Darüber hinaus werden die zur Laufzeit ermittelten Sensordaten zur Funksignalcharakteristik mit apriori bekannten Informationen über die Inhouse-Umgebung und damit Beschränkungen der möglichen Wege mit stochastischen Zusatzinformationen über das Bewegungsverhalten kombiniert. Dies wird zur weiteren Verbesserung der Ortungsgenauigket um ein Konzept ergänzt, dass statt der bisher üblichen punktuellen Ortung eine pfadbasierte Ortung gestattet. Hierbei werden punktuelle Ortungsschätzungen nicht mehr isoliert betrachtet und bewertet, sondern im Kontext des vorausgegangenen Bewegungspfades. Das Konzept umfasst eine Hypothesenevaluierung, wobei mögliche Pfade (Hypothesen) generiert und mit den erfassten Signalcharakteristiken, dem Umgebungsmodell sowie dem Bewegungsmodell abgeglichen werden. Dabei findet die Pfadauswertung über eine akkumulierte Bewertung der Einzelpunkte in einem Simulated Annealing-Algorithmus statt.

Ortungsverfahren von MagicMap

Distanzschätzung zwischen Sendern und Empfängern

Signalstärkebasiert: Jeder teilnehmende Peer-Knoten misst die Signalstärke der empfangbaren Knoten (Access Points oder andere Peers). Um stochastische Einflüsse auszugleichen, wird die empfangene Signalstärke S_i,j (Received Signal Strength) am Empfänger i für den Sender j als Mittelwert über mehrere Messungen bestimmt.

Aus den Messungen werden Schätzungen für E_i (Empfindlichkeit des Empfängers i) und P_j (Leistung des Senders j) berechnet. Dadurch werden die über verschiedene Funktechnologien erfassten Signalstärke-Messdaten hardwareunabhängig normalisiert und eine zugehörige Schätzung der physikalischen Distanz aufgrund der erwarteten Streckendämpfung a(d) bestimmt (siehe Distanzschätzung unten). Damit entsteht ein Graph mit (gerichteten) Kanten zwischen sendenden und Signalstärke-messenden Knoten.

Laufzeitbasiert: Hierzu gibt es verschiedene Ansätze, die Signallaufzeitendifferenzen zu messen. Da die Signale in 1 Nanosekunde bereits 30cm zurücklegen, muss die Zeitdifferenzmessung sehr genau sein. Hierzu arbeiten wir an einer Integration entsprechender Systeme.

Normalisierung: Da es viele verschiedene Technologien gibt, auf deren Basis geortet werden kann, müssen die Daten für eine bessere Vergleichbarkeit und einfachere Berechnung normalisiert werden.

Probabilistisches Graph-Mapping aufgrund von Distanzschätzungen

MagicMap nutzt nun eine iterative Suche, um die Positionen zu berechnen. Eine Mindestmenge an festen Parametern muss dazu vorgegeben sein, um den Suchraum einzugrenzen. Dazu können beispielsweise Knoten fixiert werden, deren Position bekannt ist. Alternativ oder ergänzend können Referenzmessungen an bekannten Position angegeben werden. Zusäzlich können durch den Nutzer weitere Parameter fest vorgegeben oder bestimmte Freiheitsgrade (z.B. die Sendeleistung aller APs sei gleich) beschränkt werden. Die freien Parameter (Positionen der Knoten, Dämpfungskoeffizient, etc.) werden nun periodisch zufällig leicht verändert und nach ihrer Wahrscheinlichkeit, wie gut sie die Messungen erklären, bewertet. Die wahrscheinlichste Konstellation wird als Ausgangsbasis für die nächste Iteration ausgewählt. Zur Annäherung an die wahrscheinlichste Konstellation wird die Summe der quadrierten Fehler der Kantenlängen (geschätzte Soll-Länge versus angezeigte Ist-Länge) minimiert.

Die Schrittweite für die randomisierten Variationen wird je nach Entfernung zum Optimum (kein Fehler) angepasst. Mit jedem Iterationsschritt sollte die Konstellation wahrscheinlicher und damit die Positionsschätzungen besser werden. Dabei erfolgen ständig Updates der Sigalstärkeinformationen sowie erneute Korrekturen der Positionsschätzungen. Schrittweise konvergiert der Graph so zu einer weitgehenden Übereinstimmung mit den realen Positionen. In Ausnahmefällen kann es vorkommen, dass das Verfahren nicht konvergiert (z.B. weil nicht genügend a priori Information angegeben wurde oder weil ein "Dead End" erreicht wurde - eine Sackgasse als lokales Minimum ohne monoton fallenden Weg zum globalen Minimum). Dazu werden Hinweise zur Güte der angezeigten Lösung visualisiert (Farben der Kanten und Knoten zeigen Widersprüche auf). Daraufhin kann ein User ggf. eingreifen.

Die Position bezogen zu Referenzmessungen wird dabei als gewichteter Mittelwerte zu den k nächsten Nachbarn ermittelt (weighted average k-nearest neigbour). Die Güte der Referenzmessungen altert dabei (Obsoleszenzrate) abhängig von der Dynamik des Szenarios. Durch Berücksichtigung von Korrelationen zu bestimmten Referenzzeiträumen kann sich MagicMap in bestimmten Grenzen an periodische (wiederkehrende) Veränderungen der Infrastruktur anpassen – etwa an den Ausfall von Access Points oder an Wettereinflüsse. Bei nicht-periodischer Dynamik (z.B. umherfahrende Gabelstapler) sind hingegen wiederholte Einmessungen oder dedizierte Sniffer-Knoten nötig.

Besondere Eigenschaften des Algorithmus

Der Algorithmus liefern ohne langwierige Kalibrierung akzeptable Resultate (bereits ohne vorherige Erstellung einer Signalstärkenkarte). Dazu müssen die Positionen einiger Access Points bekannt sein.
Referenzmessungen können die Genauigkeit des Algorithmus erhöhen.
Die Ortung funktioniert auch nur mit Referenzmessungen, d.h. ohne Kenntnis der Position der Access Points.

Mathematische Grundlagen

a - (attenuation) materialspezifischer Dämpfungskoefizient als Leistungsverlust je Strecke in dB/m. In MagicMap wird zur Vereinfachung ein Dämpfungskoeffizient spezifische je Karte bestimmt. Dies bedingt, dass man beim Anlegen von Karten nur Areale mit homogener Dämpungscharakteristik einschließen sollte und z.B. Indoor/Outdoor Areale besser in getrennten Karten erfasst. Denn natürlich funktioniert diese Vereinfachung schlecht bei inhomogener Dämpfung, beispielsweise wenn sich bebaute Bereiche und Freiräume abwechseln, etwa bei U-förmigen Gebäudekomplexen oder Innenhöfen.
a(d) - Streckendämpfung nach Durchstrahlung der Distanz d durch ein Material mit Dämpfungskoeffizient a
P_j - Leistung des Ausgangssignals des Senders j in mW bzw. dBm. Ein typischer Wert für die Sendeleistung von WLAN Accesspoints ist circa 35mW. Oft ist die Leistung einstellbar. (Richt-)Antennen können die Leistung bündeln.
S_i,j - gemessene Leistung am Empfänger i bezogen auf den Sender j in mW bzw. dBm. Direkt am Accesspoint kann man auf ca. -10 dBm kommen, die bereits nach 2-3 Metern auf ca. -40 dBm abfallen, die Übertragung funktioniert typischerweise bis ca. -80 dBm (abhängig von Störgrößen. Volle Übertragungsrate gelingt nur bei einem Signal/Rauschverhältnis von mindestesn 10 dB, bei SNR unter 6 dB bricht die Verbindung ab). Eine Messung der Signalstärke gelingt noch bis ca. -90 dBm (die Empfindlichkeit ist Geräte- und Antennen-abhängig).
dB - 1 Bel entspricht dem Leistungsverhältnis 10:1. Wegen der handlicheren Zahlenwerte ist die Angabe in Dezibel (dB) üblich. So ergibt sichfür das Leistungsverhältnis von P₁ und P₀:

$a = 10 \cdot \lg \frac{P_1}{P_2}dB \,$

dBm - Dezibel MilliWatt. Dekadisch logarithmierte Leistungsskala bezogen auf 1 mW, d.h. 0 dBm entsprechen 1mW. Jeweils 3 dB entsprechen etwa einer Verdopplung, 20 dB einem Faktor 100.

Kanten als Distanzschätzungen

Die Signalstärke liefert ein Maß für die Entfernung des Clients vom Access Point.
Ausbreitung des Signals wird als kugelförmig angenommen. Die Entfernung ist damit der Radius r dieser Kugel.
- Das stimmt nicht mit der realen Ausbreitung überein: Antennen strahlen in der Fläche mehr ab als in der Vertikalen.
- Die reale Ausbreitung am Dipol sieht aus wie ein Doughnut: in der Mitte ein Loch und dann radial aufblähend.
- Energiestromdichte S (Energie pro Zeiteinheit pro Flächeneinheit)
- $S=\frac{q^2 d^2_0 \omega^4 \sin^2 \vartheta}{16 \pi^2 \varepsilon_0 c^3 r^2} \sin^2(\omega(t-r/c)) \,$
- wobei $\vartheta$ Winkel gegen die Dipolachse, $r$ Radius
- mit $a=\frac{q^2 d^2_0 \omega^4 }{16 \pi^2 \varepsilon_0 c^3} \,$ und $\max{\sin^2(\omega(t-r/c))}=1 \,$ ergibt sich
- $S=a \frac{\sin^2 \vartheta}{r^2}\,$
- $r=\sqrt{a \frac{\sin^2 \vartheta}{S}}\,$
- S ist proportional zur Signalstärke in Watt
- WLAN Adapter liefern Signalstärke s in dBm
- $s=10 \cdot \log \frac{bS}{1mW}\,$
- $S=10^{s/10} \cdot 1mW/b \,$
- $r=\sqrt{a \frac{\sin^2 \vartheta}{10^{s/10} \cdot 1mW/b}}\,$
- $r=\sqrt{ab/1mW}\sqrt{\frac{\sin^2 \vartheta}{10^{s/10}}}\,$
- $r=\sqrt{ab/1mW}\sin \vartheta \frac{1}\sqrt{{10^{s/10}}}\,$
- $r=\sqrt{ab/1mW} \sin( \vartheta) {10^{-s/10}}^{0{,}5}\,$
- $r=\sqrt{ab/1mW}0{,}5 \cdot \sin( \vartheta) \cdot 10^{-s/10}\,$
- $\sqrt{ab/1mW}{0{,}5}=k\,$
- $r=k \cdot \sin( \vartheta) \cdot 10^{-s/10}\,$
Die Entfernung des Clients wird mit einer Aufenthaltswahrscheinlichkeit beschrieben. Annäherungsweise wird eine Normalverteilung verwendet.
- Das stimmt nicht mit der realen Ausbreitung überein: Die Wahrscheinlichkeitsverteilung ist auf einer Seite begrenzt (zur Antenne)
- pi 12:05, 7. Jul 2006 (CEST): daher Lognormalverteilt ggf. besser. Die analytische Herleitung vernachlässigt einige Einflüsse, insbesondere die Material-Dämpfung, aber auch Reflektionen. Wichtig ist daher eine empirische Verifikation. Siehe dazu auch die Studienarbeit von Michael Menz.
Für die Wahrscheinlichkeit p, dass der Client sich in Entfernung r vom Access Point befindet, gilt:

$p = \frac{1}{\sqrt{2\pi\sigma^2} } e ^ {- \frac {(r-\mu)^2} {2 \sigma^2} }\,$

Für den Erwartungswert μ wird eine geeignete Entfernung aus der Signalstärke bestimmt.
- Wie oben beschrieben: -10dB ist direkt am Access Point, -90dB ist das schwächste, messbare Signal.
- Die Abnahme der Signalstärke ist nicht linear. Sie soll später durch eine empirisch ermittelte Funktion wiedergegeben werden.
- Kurze Evaluierung ergab:

Entfernung(m)	Signal(dB)	$-(35 \cdot log(3x+1)+10)$	$0,3 \cdot 10^{-0,026 \cdot signal} - 0,5$
0	-10	-10	0,045910258
0,3	-20	-19,75637603	0,493393364
1	-30	-31,0720997	1,307678758
2	-40	-39,5784314	2,789434588
4	-45	-48,98801733	3,937325165
6	-50	-54,75637603	5,485786945
10	-60	-62,19765928	10,39234164

Für die Varianz $σ 2$ wird aus der angenommen Entfernung ein Wert bestimmt: In Access Point Nähe ändern sich die Feldstärken sehr rasch, daher sollte hier eine kleine Varianz angenommen werden. Weiter entfernt sind die Änderungen nicht mehr so deutlich und die Varianz sollte größer gewählt werden.

pi 20:50, 1. Sep 2006 (CEST): sollte exakt ausgerechnet werden. Ist keine Information über den speziellen Client bekannt, kann man über alle gegebenen Messungen mitteln. Ansonsten muss man schaun, welche Varianzen sich für die spezifische Ausstattung des Clients ergeben.

Reference Points

Für Referenzpunkte wird eine Distanz zum Client definiert. Möglichkeiten sind:
- Differenz der Signalstärken aller gemeinsam gesehenen Access Points. Je größer die Differenz, desto weiter weg.
Alternative kann auch ab drei Reference Points die Position der Access Point durch Triangulation bestimmt werden. So könnte man durch wenige Basismessungen schon eine Grundeinstellung erzeugen, bei der dann die Access Point Positionen manuell oder durch mehr Messungen genauer bestimmt werden können.
Wenn die Position der Access Points bekannt ist, kann die Information der Referenz Point auch nur für Messungen angewandt werden, wenn Client und Renference Point sich auf dem gleichen Winkel (oder ähnlichem) vom Access Point befinden.

pi 20:54, 1. Sep 2006 (CEST): Lieber so: Unter der Annahme, dass APs und Clients an der gegebeben Position sind wird diese Position bewertet. Der Algorithmus nähert sich dann iterativ. Liegt Referenzpunkt nahe der Linie zwischen AP und Client wird er stärker gewichtet als wenn er weit von der Linie entfern ist. Zunächst probieren wir hier den Effekt einer einfachen Heuristik. Später kann man versuchen das Optimum rasuzukriegen (ich befürchte aber, das ist sehr schwierig).

Suche nach dem Aufenthaltsort

Die Aufenthaltswahrscheinlichkeit bei Berücksichtigung mehrerer Access Point ist dann der Mittelwert aller Wahrscheinlichkeiten.
Aus der Menge aller Aufenthaltswahrscheinlichkeiten wird dann das Maximum gesucht.
Mögliche Suchalgorithmen:
- Simulated Annealing
- Tabu Search

Umrechnung der Entfernung in Kartenkoordinaten

Sind auf der Karte zwei oder mehr Georefernzpunkte definiert, wird die Entfernung hieraus berechnet.
Andernfalls wird die Entfernung aus der Signalstärke und aus der Karte zu den bekannten Access Points bestimmt. Das Verhältnis wird gemittelt und als Skalierungsgrundlage genommen.

pi 20:56, 1. Sep 2006 (CEST): es gibt auch den Fall, dass Länge und Breite einer Karte gegeben sind (ohne Georeferenz)

Simulated Annealing

Wikipedia: Simulated Annealing

Basisiteration


s := s0; e := E(s)                           // Initial state, energy.
sb := s; eb := e                             // Initial "best" solution
k := 0                                       // Energy evaluation count.
while k < kmax and e > emax                  // While time remains & not good enough:
  sn := neighbour(s)                         //   Pick some neighbour.
  en := E(sn)                                //   Compute its energy.
  if en < eb then                            //   Is this a new best?
    sb := sn; eb := en                       //     Yes, save it.
  if random() < P(e, en, temp(k/kmax)) then  //   Should we move to it?
    s := sn; e := en                         //     Yes, change state.
  k := k + 1                                 //   One more evaluation done
return sb                                    // Return the best solution found.

State

Ein Punkt im dreidimensionalen Raum auf der geladenen Karte


s := Point3D(x, y, z)                        // State

kmax

Anzahl der maximalen Iteration. Muss geeignet gewählt werden. Am Anfang eher groß, bei einer bekannten Lösung kann wahrscheinlich reduziert werden.

emax

Energie eines Zustandes, der "gut genug" ist. Ebenfalls geeignet gewählt. Evtl kann reduziert werden.

erstmal nicht so wichtig, der Algorithmus terminiert auch nach kmax Iterationen.

Energy E(s)

Die Summe aller Gegenwahrscheinlichkeiten, dass sich der Client in dieser Entfernung vom jeweiligen Access Point befindet. Sorum definiert, weil Simulated Annealing den energieärmsten Zustand sucht. Evtl nicht Summe sondern Mittelwert.


e := 0
foreach AccessPoint in SeenAccessPoints(Client)
    e := e + 1 - AufenthaltsWahrscheinlichkeit(AccessPoint, s)
foreach ReferencePoint in ReferencePoints(Client)
    e := e + 1 - AufenthaltsWahrscheinlichkeit(ReferencePoint, s)
return e

neighbour(s)

Gradientbasierter Nachbar kritischste Funktion

muss einen Graph liefern, mit dem alle Zustände erreichbar sind.

wähle eine zufälligen Nachbar in einem Bereich um die aktuelle Position.

Verkleiner diesen Bereich mit jeder Iteration

1. Iteration: gesamte Karte

letzte Iteration: 1 Punkt

multipliziere den Bereich bei jeder Iteration mit einem konstanten Faktor < 1

Faktor = Anzahl.der.Iteration-te Wurzel aus 1/Anfangsgröße

random()

Gleichverteilte Zufallszahl zwischen 0 und 1.

temp(r)

Temperatur

Spezifiert wie wahrscheinlich es ist, zu einer schlechteren Lösung zu wechseln. Muss mit wachsender Iterationszahl abnehmen.

Vielleicht einfach kmax/k (anders als oben)

Oder


t0 := Initialtemperatur
1 > p > 0
t(k) := t(k-1) * p

Übergangswahrscheinlichkeitsfunktion P(e, en, t)

original formulation of the method by Kirkpatrick


if en < e
    return 1
else
    return exp((e − en )/t)

JUNG

Knoten

Jeder Client, AccessPoint, Referenzpunkt ist ein Knoten

Kanten

Client-AccessPoint
- Signalstärke gemessene
- linear auf Kantenlänge umgesetzt
- Die Signalstärken zwischen -30 dB bis -100 dB werden dabei auf Werte von 0 bis 70 skaliert

    public static double signalLevelToStrength(double signalLevel){
       double result = Math.abs(signalLevel);
       result -= Constants.MAX_SIGNALLEVEL; //vom Signallevel 30 abziehen
       // Wir stehen quasi auf dem AP drauf und geben deshalb eine Stärke von 100 zurück
       if (result < 0.0) return Constants.MIN_SIGNALLEVEL;
       //mit 100 multiplizieren und durch 70 teilen, dadurch liegen alle Werte zwischen 0 und 70
       result = result * Constants.MIN_SIGNALLEVEL / (Constants.MIN_SIGNALLEVEL - Constants.MAX_SIGNALLEVEL);
       if (result > Constants.MIN_SIGNALLEVEL) {
           result = Constants.MIN_SIGNALLEVEL;
           System.out.println(Constants.MIN_SIGNALLEVEL + " überschritten");
       }
       return result;

- Skalierung mit Kalibrierungsfaktor über fixierte Knoten
  - nichtfixierte gehen nicht ein
  - Berechnung der Kalibrierungsfaktoren:

    private void adjustCallibration(boolean clientOrLocation, double length, double desiredLength, boolean notFixed){
       if (notFixed) return;
       // Verhältnis von angezeigter zu berechneter Kantenlänge berechnen
       double d = (length + 1) / (desiredLength + 1);
       // falls beide Knoten der Kante Client- oder LocationNodes sind 
       if (clientOrLocation) {
           if (d < 0.95) {
               // der übergebene Wert wird auf den aktuellen Kalibrierungsfaktor addiert
               settings.adjustLocationCalibration(-Math.max(Math.abs(len - desiredLen) / 200, 0.001));
           } else if (d > 1.05) {
               settings.adjustLocationCalibration(Math.max(Math.abs(len - desiredLen) / 200, 0.001));
           }
       // ansonsten: mindestens einer der Knoten ist ein AccessPointNode
       } else {
           if (d < 0.95) {
               settings.adjustAccessPointCalibration(-Math.max(Math.abs(len - desiredLen) / 200, 0.001));
           } else if (d > 1.05) {
               settings.adjustAccessPointCalibration(Math.max(Math.abs(len - desiredLen) / 200, 0.001));
           }
       }
    }

Referenzpunkt-AccessPoint
- genauso wie Client-AccessPoint

Client-Referenzpunkt
- Ähnlichkeitsmaß
- Signalstärken vom Client werden mit denen von RP verglichen
- in beiden vorhandenen APs werden Signalstärken Differenz gebildet und summiert.
- unterschiedlich gesehene AP Signalstärken werden aufaddiert, mit faktor multipliziert und auf die Distanz addiert
  - Faktor (Constants.PENALTY_FACTOR)konstant, experimental 0.01, empirisch

       if (ReferencePointOrClient1 && ReferencePointOrClient2) {
           // Zwischen zwei Orten/Clients
           HashSet<AccessPointNode> same = new HashSet<AccessPointNode>();
           HashSet<AccessPointNode> diff = new HashSet<AccessPointNode>();
           AccessPointSeerNode ap1 = (AccessPointSeerNode) node1;
           AccessPointSeerNode ap2 = (AccessPointSeerNode) node2;
           // Füllt same und diff mit den gemeinsam gesehenen, bzw nicht gesehenen AccessPoints
           findAccessPoints(ap1, ap2, same, diff);
           // Kein gemeinsamer Access Point, beide Punkte liegen weit auseinander
           if (same.size() == 0) return 1000.0;
           if (same.size() == 1) {
               if (diff.size() == 0) return 0.0;
               return 1000.0;
           }
           // Erstellen der Vektoren für die Distance-Funktion
           Iterator it = same.iterator();
           double a[] = new double[same.size()];
           double b[] = new double[same.size()];
           int c = 0;
           while (it.hasNext()) {
               AccessPointNode ap = (AccessPointNode) it.next();
               a[c] = Math.abs(ap1.getSignalLevelForAccessPoint(ap));
               b[c] = Math.abs(ap2.getSignalLevelForAccessPoint(ap));
               ++c;
           }
           // Die Verhältnise zwischen allen Vektorelementen ausrechnen
           int n = same.size();
           int m = (n * (n - 1)); // Länge der entstehenden Vektoren
           double[] v1 = new double[m];
           double[] v2 = new double[m];
           c = 0;
           for (int i = 0; i < a.length - 1; ++i)
               for (int j = i + 1; j < a.length; ++j) {
                   v1[c] = a[i] / a[j];
                   v2[c] = b[i] / b[j];
                   c++;
                   v1[c] = a[j] / a[i];
                   v2[c] = b[j] / b[i];
                   c++;
               }
           // v1 enthält nun Signalverhältnisse von ap1
           // v2 enthält nun Signalverhältnisse von ap2
           // Distanz der einzelnen Arraywerte, aufaddiert und durch die Anzahl dividiert
           double distance = MagicMetric.mda.distance(v1, v2);
           // Bestrafung nicht gemeinsam gesehener AccessPoints
           it = diff.iterator();
           double penalty = 0.0;
           while (it.hasNext()) {
               AccessPointNode ap = (AccessPointNode) it.next();
               penalty += (Constants.MIN_SIGNALLEVEL + ap1.getSignalLevelForAccessPoint(ap)); // 0.0 wenn ap1 nicht ap sieht
               penalty += (Constants.MIN_SIGNALLEVEL + ap2.getSignalLevelForAccessPoint(ap)); // 0.0 wenn ap2 nicht ap sieht
           }
           return (distance + penalty * Constants.PENALTY_FACTOR) * 10.0;

Veränderungen am JUNG Framework

Vertex-Listener
Graphische Anpassungen
fixierte Knoten?
- setFix -> dontMove
nicht relevant für Ortung

JUNG Funktionen

Springlayout
- Iteration über Kanten
- Iterationsschritt
  - Knoten wird je nachdem in welche Richtung er gedrückt/gezogen wird von Kante auf der Karte verschoben
  - Schrittgröße hängt von Differenz gewünscht/real ab
  - wird multipliziert mit Energie
  - Energie = Federkraft
  - nichtfixiert Energie = 0.001 Client-Nichtfix AP
  - fix AP - Client = 1
  - ab gewisser Entfernung 30

  public double getForce(Vertex v1, Vertex v2){
       double result = 1.0 / 3.0;
       Node node1 = findNode(v1);
       Node node2 = findNode(v2);
       int t1 = node1.getType();
       int t2 = node2.getType();
       // Client oder Location
       boolean c1 = (t1 == NodeModelConstants.NODETYPE_CLIENT);
       boolean c2 = (t2 == NodeModelConstants.NODETYPE_CLIENT);
       boolean l1 = (t1 == NodeModelConstants.NODETYPE_LOCATION);
       boolean l2 = (t2 == NodeModelConstants.NODETYPE_LOCATION);
       boolean a1 = (t1 == NodeModelConstants.NODETYPE_ACCESSPOINT);
       boolean a2 = (t2 == NodeModelConstants.NODETYPE_ACCESSPOINT);
       boolean a1fix = (a1 && node1.isFix());
       boolean a2fix = (a2 && node2.isFix());
       boolean a1var = (a1 && !node1.isFix());
       boolean a2var = (a2 && !node2.isFix());
       if (a1var && c2 || a2var && c1)
           // Variable APs so gut wie ignorieren
           result = 1.0 / 1000.0;
       else {
           if ((a1fix && c2 || a2fix && c1)) result = 1.0;
           if (l1 && c2 || l2 && c1) {
               Edge e = v1.findEdge(v2);
               if (e == null) e = v2.findEdge(v1);
               if (e != null) {
                   double l = this.lf.getLength(e); // Lï¿½nge zwischen Client und Location
                   if (l > 0.001)
                       result = 30.0 / l;
                   else
                       result = 30.0;
               }
           }
       }
       return result;
   }

- - beschränkt durch Maximale Schrittweite

Von "http://wiki.informatik.hu-berlin.de/nomads/index.php/MagicMap_Verfahren"

Seitenkategorien: MagicMap

Views

'Persönliche Werkzeuge

Anmelden

Suche

Werkzeuge