Upload
dokiet
View
214
Download
0
Embed Size (px)
Citation preview
INSTITUT FUR THEORETISCHE INFORMATIK - LEHRSTUHL FUR ALGORITHMIK (PROF. WAGNER)
Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten
Fabian Fuchs | 5. Nov. 2015 (Version 1)
KIT – Universitat des Landes Baden-Wurttemberg undnationales Großforschungszentrum in der Helmholtz-Gemeinschaft www.kit.edu
Thema heute: Lokalisierung
Warum wir Knotenpositionen brauchenZuordnung der Daten (was tun, wenn’s brennt?)GeoroutingTopologiekontrolle...
Was tun, wenn (alle/einige/viele) Knoten ihre Positionen nichtkennen, weil
GPS/Galileo nicht zur Verfugung stehtist schwer, groß, teuer (verglichen mit SmartDust)kostet Energiefunktioniert nicht uberall (drinnen, im Wald)ist nicht besonders genau
jedem Knoten die Position einprogrammieren nicht geht
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (2/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Thema heute: Lokalisierung
Warum wir Knotenpositionen brauchenZuordnung der Daten (was tun, wenn’s brennt?)GeoroutingTopologiekontrolle...
Was tun, wenn (alle/einige/viele) Knoten ihre Positionen nichtkennen, weil
GPS/Galileo nicht zur Verfugung stehtist schwer, groß, teuer (verglichen mit SmartDust)kostet Energiefunktioniert nicht uberall (drinnen, im Wald)ist nicht besonders genau
jedem Knoten die Position einprogrammieren nicht geht
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (2/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Uberblick
Uberblick: Entfernungs- und Richtungsschatzung
Lokalisierung mit Ankerknoten
Ankerfreie Lokalisierung: Virtuelle KoordinatenKomplexitatsbetrachtungenHeuristiken zur ankerfreien Lokalisierung
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (3/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Was man alles messen kann
EntfernungenZusammenhang im Kommunikationsgraphen
sehr grobe Information uber benachbarte Lage von KnotenRSSI: Received Signal Strength Indicator
Sendestarke bekannt ⇒ Distanz lasst sich theoretisch schatzenin der Praxis recht ungenau
ToA: Time of ArrivalBestimmung von Signallaufzeiten (roundtrip time)
TDoA: Time Difference of ArrivalLaufzeitvergleiche zweier Signale (z. B. Radio / Ultraschall)
RichtungenAoA: Angle of Arrival
Phasenverschiebung in Antennenarraysgerichtete Antennen
Zusatzhardware (Laser etc.)
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (4/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Was man alles messen kann
EntfernungenZusammenhang im Kommunikationsgraphen
sehr grobe Information uber benachbarte Lage von KnotenRSSI: Received Signal Strength Indicator
Sendestarke bekannt ⇒ Distanz lasst sich theoretisch schatzenin der Praxis recht ungenau
ToA: Time of ArrivalBestimmung von Signallaufzeiten (roundtrip time)
TDoA: Time Difference of ArrivalLaufzeitvergleiche zweier Signale (z. B. Radio / Ultraschall)
RichtungenAoA: Angle of Arrival
Phasenverschiebung in Antennenarraysgerichtete Antennen
Zusatzhardware (Laser etc.)
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (4/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Uberblick
Uberblick: Entfernungs- und Richtungsschatzung
Lokalisierung mit Ankerknoten
Ankerfreie Lokalisierung: Virtuelle KoordinatenKomplexitatsbetrachtungenHeuristiken zur ankerfreien Lokalisierung
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (5/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Lokalisierung mit Ankerknoten
Wenn GPS/Einprogrammieren so teuer ist, reicht es vielleicht, wenneinige Knoten, sogenannte Ankerknoten, ihre Position kennen?
Wenn jeder Knoten genug Anker ”sieht“:
Trilateration bei bekannten EnfernungenDrei Anker fur eindeutige Lokalisierung
Triangulation bei bekannten WinkelnZwei Anker fur eindeutige Lokalisierung
Bei gestorten Werten und/oder mehr AnkernLeast Squares Verfahren etc.→ Schatztheorie
Was, wenn wir nur wenige Anker haben? Einige Knoten haben dannvielleicht keine Anker in ihrer Nachbarschaft!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (6/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Lokalisierung mit Ankerknoten
Wenn GPS/Einprogrammieren so teuer ist, reicht es vielleicht, wenneinige Knoten, sogenannte Ankerknoten, ihre Position kennen?
Wenn jeder Knoten genug Anker ”sieht“:
Trilateration bei bekannten EnfernungenDrei Anker fur eindeutige Lokalisierung
Triangulation bei bekannten WinkelnZwei Anker fur eindeutige Lokalisierung
Bei gestorten Werten und/oder mehr AnkernLeast Squares Verfahren etc.→ Schatztheorie
Was, wenn wir nur wenige Anker haben? Einige Knoten haben dannvielleicht keine Anker in ihrer Nachbarschaft!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (6/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Lokalisierung mit Ankerknoten
Wenn GPS/Einprogrammieren so teuer ist, reicht es vielleicht, wenneinige Knoten, sogenannte Ankerknoten, ihre Position kennen?
Wenn jeder Knoten genug Anker ”sieht“:
Trilateration bei bekannten EnfernungenDrei Anker fur eindeutige Lokalisierung
Triangulation bei bekannten WinkelnZwei Anker fur eindeutige Lokalisierung
Bei gestorten Werten und/oder mehr AnkernLeast Squares Verfahren etc.→ Schatztheorie
Was, wenn wir nur wenige Anker haben? Einige Knoten haben dannvielleicht keine Anker in ihrer Nachbarschaft!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (6/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Lokalisierung mit Ankerknoten
Wenn GPS/Einprogrammieren so teuer ist, reicht es vielleicht, wenneinige Knoten, sogenannte Ankerknoten, ihre Position kennen?
Wenn jeder Knoten genug Anker ”sieht“:
Trilateration bei bekannten EnfernungenDrei Anker fur eindeutige Lokalisierung
Triangulation bei bekannten WinkelnZwei Anker fur eindeutige Lokalisierung
Bei gestorten Werten und/oder mehr AnkernLeast Squares Verfahren etc.→ Schatztheorie
Was, wenn wir nur wenige Anker haben? Einige Knoten haben dannvielleicht keine Anker in ihrer Nachbarschaft!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (6/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Lokalisierung mit wenigen Ankern
Typisches VorgehenKnoten schatzen Abstande/Richtungen zu Ankern uber mehrereHops und wenden dann Triangulation/Trilateration an.
Furchtbar viele Verfahren und Heuristikenunklare Problemstellung
Dichte, Verteilung von Ankerknoten
Was kann man aus algorithmischer Sicht beitragen?
Im folgenden nehmen wir immer an, dass wir keine weiterenMessungen haben, sondern nur den Verbindungsgraphen und dasUDG-Modell.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (7/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Algorithmus HOP
IdeeIn großen Unit-Disk-Graphen konnte die Lange eines kurzestenWeges stark genug mit der Entfernung korrellieren!
1 Berechne Hop-Distanz zu AnkerknotenBroadcasts von Ankerknoten genugen
2 Wahle Position so, dass Abstande der Hop-Distanz bestmoglichentsprechen
Wie gut funktioniert ein solcher Ansatz?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (8/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Algorithmus HOP
IdeeIn großen Unit-Disk-Graphen konnte die Lange eines kurzestenWeges stark genug mit der Entfernung korrellieren!
1 Berechne Hop-Distanz zu AnkerknotenBroadcasts von Ankerknoten genugen
2 Wahle Position so, dass Abstande der Hop-Distanz bestmoglichentsprechen
Wie gut funktioniert ein solcher Ansatz?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (8/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Kompetitivitat: Vorbereitung
Problem: UDG-Lokalisierung anhand von AnkerknotenGegeben: Unit-Disk-Graph G = (V ,E) mit entsprechender
Einbettung p : V → R2, Ankerknoten VA ⊂ V mitbekannten Positionen
Gesucht: Knotenpositionen p : V → R2 mit geringen Fehlern
Err(v) := ‖p(v)− p(v)‖ .
In die Berechnung der p(v) durfen keine p(v) fur einv 6∈ VA einfließen!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (9/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Optimalitat, Kompetitivitat
Definition: Optimaler AlgorithmusEin optimaler Algorithmus wahlt zu einem Graphen G undAnkerpositionen die Knotenpositionen, die den maximalen Fehleruber alle moglichen Einbettungen minimieren.
Das muss nicht leicht sein, ist aber ein guter Vergleich:Kein Algorithmus ist im worst-case besser!
Definition: KompetitivitatEin Algorithmus ALG heißt c-kompetitiv, wenn immer gilt:
ErrALG(v) ≤ c · ErrOPT(v) + k
fur alle v ∈ V und ein k ∈ R.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (10/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Optimalitat, Kompetitivitat
Definition: Optimaler AlgorithmusEin optimaler Algorithmus wahlt zu einem Graphen G undAnkerpositionen die Knotenpositionen, die den maximalen Fehleruber alle moglichen Einbettungen minimieren.
Das muss nicht leicht sein, ist aber ein guter Vergleich:Kein Algorithmus ist im worst-case besser!
Definition: KompetitivitatEin Algorithmus ALG heißt c-kompetitiv, wenn immer gilt:
ErrALG(v) ≤ c · ErrOPT(v) + k
fur alle v ∈ V und ein k ∈ R.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (10/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Kompetitivitat von HOP
SatzHOP ist bereits in einer Dimension nicht kompetitiv.
1
ε
12 + ε1
2εA Bv
Fur bel. k setze Anker A = 0, B = (k − 1)(1 + ε) + k( 12 + ε)
Jeder Algo, der nur Hops zahlt, setzt v bestenfalls in die Mitte!macht ein Algo es besser, drehen wir die Instanz um!Fehler in Θ(k)!
Ist das bereits optimal?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (11/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Kompetitivitat von HOP
SatzHOP ist bereits in einer Dimension nicht kompetitiv.
(k − 1)(1 + ε)
ε 2εA B
k( 12 + ε)
v
Fur bel. k setze Anker A = 0, B = (k − 1)(1 + ε) + k( 12 + ε)
Jeder Algo, der nur Hops zahlt, setzt v bestenfalls in die Mitte!macht ein Algo es besser, drehen wir die Instanz um!Fehler in Θ(k)!
Ist das bereits optimal?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (11/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Kompetitivitat von HOP
SatzHOP ist bereits in einer Dimension nicht kompetitiv.
ε 2ε
A B
k hops k hops
(k − 1)(1 + ε) k( 12 + ε)
v
Fur bel. k setze Anker A = 0, B = (k − 1)(1 + ε) + k( 12 + ε)
Jeder Algo, der nur Hops zahlt, setzt v bestenfalls in die Mitte!macht ein Algo es besser, drehen wir die Instanz um!Fehler in Θ(k)!
Ist das bereits optimal?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (11/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Kompetitivitat von HOP
SatzHOP ist bereits in einer Dimension nicht kompetitiv.
ε 2ε
A B
k hops k hops
(k − 1)(1 + ε) k( 12 + ε)
v
Fur bel. k setze Anker A = 0, B = (k − 1)(1 + ε) + k( 12 + ε)
Jeder Algo, der nur Hops zahlt, setzt v bestenfalls in die Mitte!macht ein Algo es besser, drehen wir die Instanz um!Fehler in Θ(k)!
Ist das bereits optimal?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (11/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Kompetitivitat von HOP
SatzHOP ist bereits in einer Dimension nicht kompetitiv.
ε 2ε
A B
k hops k hops
k-1 skips k/2 skips
112 + ε1
v
Definition: SkipFur einen Graph G = (V ,E) bilden zwei Knoten u,w ∈ V einen Skip,falls {u,w} 6∈ E und ∃v , so dass {u, v}, {v ,w} ∈ E .
Skips belegen Mindestabstande!In diesem Fall grenzen sie die Position bis auf O(kε) ein!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (12/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Kompetitivitat von HOP
Definition: Skip-PfadEin Pfad A = v0,u1, v1, . . . ,us, vs = v ist ein Skip-Pfad der Lange szwischen A und v , wenn wenn
dG(A, vi) < dG(A, vi+1)
dG(vi , vi+1) > 1 (also (vi , vi+1) 6∈ E)Die Lange eines langsten solchen Pfades ist die Skip-Entfernung vonv zu A.
Hops sind obere Schranke an Entfernung zum Anker.Skips sind untere Schranke!
Wie berechnet man Hop- und Skip-Distanzen?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (13/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Kompetitivitat von HOP
Definition: Skip-PfadEin Pfad A = v0,u1, v1, . . . ,us, vs = v ist ein Skip-Pfad der Lange szwischen A und v , wenn wenn
dG(A, vi) < dG(A, vi+1)
dG(vi , vi+1) > 1 (also (vi , vi+1) 6∈ E)Die Lange eines langsten solchen Pfades ist die Skip-Entfernung vonv zu A.
Hops sind obere Schranke an Entfernung zum Anker.Skips sind untere Schranke!
Wie berechnet man Hop- und Skip-Distanzen?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (13/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Erinnerung: Hop-Berechnung
Wie berechnet man Hop-Distanzen?jeder Knoten v startet mit hv =∞.hort ein Knoten v von einem Nachbarn u mithu + 1 < hv , verringert er hv zu hv = hu + 1.wenn ein Knoten sein hv verringert, teilt er das allenNachbarn mit.Startschuss: Ankerknoten verringert seinen Abstand auf hA = 0.
Wenn man hops zu mehreren Ankern berechnen will, muss derjeweilige Anker Teil der Nachricht sein!
Ich, v habe meinen hop-Abstand zu Anker A auf hvreduziert.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (14/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Erinnerung: Hop-Berechnung
Wie berechnet man Hop-Distanzen?jeder Knoten v startet mit hv =∞.hort ein Knoten v von einem Nachbarn u mithu + 1 < hv , verringert er hv zu hv = hu + 1.wenn ein Knoten sein hv verringert, teilt er das allenNachbarn mit.Startschuss: Ankerknoten verringert seinen Abstand auf hA = 0.
Wenn man hops zu mehreren Ankern berechnen will, muss derjeweilige Anker Teil der Nachricht sein!
Ich, v habe meinen hop-Abstand zu Anker A auf hvreduziert.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (14/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Wie berechnet man Skips?
jeder Knoten v startet mit sv = −1.hort ein Knoten v von einem Nicht-Nachbarn u mitsu + 1 > sv , erhoht er sv zu sv = su + 1.wenn ein Knoten sein sv erhoht, teilt er das allenZwei-hop-Nachbarn mit.Startschuss: Jeder Nachbar v des Ankerknoten und A selbsterhoht seinen Abstand auf sv = 0.
Wie verhindert man ”Aufschaukeln“?Beleg fur Erhohung sind nur Nicht-Nachbarn u, dieecht zwischen v und Anker A liegenDann liegt ein Nachbar mit niedrigeremHop-Abstand dazwischen! 1
A0 001
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (15/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Wie berechnet man Skips?
jeder Knoten v startet mit sv = −1.hort ein Knoten v von einem Nicht-Nachbarn u mitsu + 1 > sv , erhoht er sv zu sv = su + 1.wenn ein Knoten sein sv erhoht, teilt er das allenZwei-hop-Nachbarn mit.Startschuss: Jeder Nachbar v des Ankerknoten und A selbsterhoht seinen Abstand auf sv = 0.
Wie verhindert man ”Aufschaukeln“?Beleg fur Erhohung sind nur Nicht-Nachbarn u, dieecht zwischen v und Anker A liegenDann liegt ein Nachbar mit niedrigeremHop-Abstand dazwischen! 1
A0 0011
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (15/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Wie berechnet man Skips?
jeder Knoten v startet mit sv = −1.hort ein Knoten v von einem Nicht-Nachbarn u mitsu + 1 > sv , und zwar uber einen Nachbarn w 6= A mit hw < hv ,erhoht er sv zu sv = su + 1.wenn ein Knoten sein sv erhoht, teilt er das allenZwei-hop-Nachbarn mit.Startschuss: Jeder Nachbar v des Ankerknoten und A selbsterhoht seinen Abstand auf sv = 0.
Wie verhindert man ”Aufschaukeln“?Beleg fur Erhohung sind nur Nicht-Nachbarn u, dieecht zwischen v und Anker A liegenDann liegt ein Nachbar mit niedrigeremHop-Abstand dazwischen! 1
A0 0011
v uw
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (15/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Algorithmus HS (Hop & Skip)
1 Berechne Hop-Distanz zu allen Ankerknoten2 Berechne Skip-Distanz zu allen Ankerknoten3 Schneide Intervalle aus Skip- und Hop-Distanz fur alle Anker4 Wahle Punkt, der uber das verbleibende Intervall den moglichen
Fehler minimiert (s < distE(A, v) ≤ h)
Satz (ohne Beweis)HS ist 1-kompetitiv in einer Dimension. [O’Dell, Wattenhofer, 2005].
Man kann zeigen, dass wirklich jede Position im Schnitt derIntervalle angenommen werden kann
In zwei Dimensionen: Fehlende Kompetitivitat von HOP bleibt, abervon HS bleibt nur die Idee, auch untere Schranken fur die Lange vonPfaden zu verwenden.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (16/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Algorithmus HS (Hop & Skip)
1 Berechne Hop-Distanz zu allen Ankerknoten2 Berechne Skip-Distanz zu allen Ankerknoten3 Schneide Intervalle aus Skip- und Hop-Distanz fur alle Anker4 Wahle Punkt, der uber das verbleibende Intervall den moglichen
Fehler minimiert (s < distE(A, v) ≤ h)
Satz (ohne Beweis)HS ist 1-kompetitiv in einer Dimension. [O’Dell, Wattenhofer, 2005].
Man kann zeigen, dass wirklich jede Position im Schnitt derIntervalle angenommen werden kann
In zwei Dimensionen: Fehlende Kompetitivitat von HOP bleibt, abervon HS bleibt nur die Idee, auch untere Schranken fur die Lange vonPfaden zu verwenden.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (16/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Uberblick
Uberblick: Entfernungs- und Richtungsschatzung
Lokalisierung mit Ankerknoten
Ankerfreie Lokalisierung: Virtuelle KoordinatenKomplexitatsbetrachtungenHeuristiken zur ankerfreien Lokalisierung
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (17/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Ankerfreie Lokalisierung
Viele Anwendungen funktionieren mit plausiblen Koordinaten so gutwie mit echten (Georouting, ...).
Ohne Ankerknoten kann es keine echte Lokalisierung gebenFreiheitsgrade je nach Eingabe
Verschiebungen (immer)Drehungen (fehlende absolute Richtungsinformation)Spiegelungen (fehlende Richtungsinformation)Skalierungen (fehlende Entfernungsinformation)
schon das Wissen, es mit UDG/qUDG zu tun zu haben, tragtEntfernungsinformation!
Vorsicht: plausible Koordinaten konnen auch vollig von derRealitat abweichen!Trotzdem: Oft sind plausible Koordinaten besser als keine!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (18/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Unit-Disk-Graph Einbettung
Wenn wir davon ausgehen, dass ein Graph ein Unit-Disk-Graph ist,wie schwer ist es dann, eine Einbettung zu finden, die das belegt?
(Erinnerung: Eigenschaft UDG zu sein ist unabhangig von der Einbettung!)
Mindestens so schwer, wie zu entscheiden, ob ein Graph einUnit-Disk-Graph ist!
Angenommen wir haben Algorithmus, um UDGs einzubettenwende Algo auf irgendeinen Graphen an und teste, ob Ausgabeden Graphen als UDG einbettet
(das sind hochstens zusatzliche O(n2) Operationen)
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (19/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Unit-Disk-Graph Einbettung
Wenn wir davon ausgehen, dass ein Graph ein Unit-Disk-Graph ist,wie schwer ist es dann, eine Einbettung zu finden, die das belegt?
(Erinnerung: Eigenschaft UDG zu sein ist unabhangig von der Einbettung!)
Mindestens so schwer, wie zu entscheiden, ob ein Graph einUnit-Disk-Graph ist!
Angenommen wir haben Algorithmus, um UDGs einzubettenwende Algo auf irgendeinen Graphen an und teste, ob Ausgabeden Graphen als UDG einbettet
(das sind hochstens zusatzliche O(n2) Operationen)
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (19/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Unit-Disk-Graph Erkennung
Problem: UDG-ErkennungEntscheide, ob ein gegebener Graph G = (V ,E) ein Unit-Disk-Graphist.
SatzUnit-Disk-Graph-Erkennung ist NP-schwer.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (20/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Erinnerung: Reduktion
Beweis der NP-Schwere von A durch Reduktion1 Nimm bekanntes NP-schweres Problem B.2 Zeige, dass es Abbildung von Instanzen von B auf Instanzen vonA gibt, die
in Polynomialzeit berechenbar ist,Ja/Nein-Instanzen auf Ja/Nein-Instanzen abbildet
Dann muss unser Problem auch NP-schwer seinMit einem Algo fur unser Problem plus Polynomialzeit kann manein NP-schweres Problem losen
⇒ Dann kann man jedes NP-schwere Problem damit losen
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (21/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Erinnerung: Erfullbarkeitsproblem
3SATISFIABILITY
Es ist NP-schwer, zu entscheiden, ob eine Formel in KonjunktiverNormalform (KNF) erfullbar ist, auch unter der Einschrankung, dass
jede Klausel nur drei Literale enthaltjedes Literal in maximal drei Klauseln erscheint(diese Forderung gehort nicht zum ublichen 3-SAT Problem!)
Bsp: (x1 ∨ x2 ∨ x3) ∧ (x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x3 ∨ x4)
Wie bilden wir eine solche Formel auf einen Graphen ab, der genaudann ein UDG ist, wenn die Formel erfullbar ist?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (22/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Erinnerung: Erfullbarkeitsproblem
3SATISFIABILITY
Es ist NP-schwer, zu entscheiden, ob eine Formel in KonjunktiverNormalform (KNF) erfullbar ist, auch unter der Einschrankung, dass
jede Klausel nur drei Literale enthaltjedes Literal in maximal drei Klauseln erscheint(diese Forderung gehort nicht zum ublichen 3-SAT Problem!)
Bsp: (x1 ∨ x2 ∨ x3) ∧ (x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x3 ∨ x4)
Wie bilden wir eine solche Formel auf einen Graphen ab, der genaudann ein UDG ist, wenn die Formel erfullbar ist?
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (22/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schritt 1: Orientierbarer Graph
(x1 ∨ x2 ∨ x3) ∧ (x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x3 ∨ x4)
x1
C1
C2
C3
x1 x2x2 x3x3 x4x4
Formel ist erfullbar⇔ es gibt Kantenrichtungen mitfur jede Klausel C gilt outdeg(x) ≥ 1fur jede Variable x gilt: indeg(x) = 0 oder indeg(x) = 0
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (23/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schritt 1: Orientierbarer Graph
(x1 ∨ x2 ∨ x3) ∧ (x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x3 ∨ x4)
x1
C1
C2
C3
x1 x2x2 x3x3 x4x4
Formel ist erfullbar⇔ es gibt Kantenrichtungen mitfur jede Klausel C gilt outdeg(x) ≥ 1fur jede Variable x gilt: indeg(x) = 0 oder indeg(x) = 0
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (23/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schritt 2: Gadgets
(x1 ∨ x2 ∨ x3) ∧ (x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x3 ∨ x4)
x1
C1
C2
C3
x1 x2x2 x3x3 x4x4
Klassischer Gadgetbeweis: Baue Struktur nach ausVariablen, Klauseln, Drahten und Kreuzungenso dass gultige Einbettungen genau gultigen Orientierungenentsprechen
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (24/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Einbettungen von Kreisen
LemmaEnthalt ein Graph einen knoteninduzierten Kreis, muss der in jederEinbettung als Unit-Disk-Graph planar eingebettet werden.
knoteninduzierter Kreis: Menge von Knoten, die als Kreisverbunden sind (keine weiteren Kanten!)sollte uns bekannt vorkommen!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (25/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schritt 2.1: Drahte
� £�B���n������� �}������������ §£�B������ 3
bL
aL
dL
cL
bR
cR
aR
dR
�Oß�èJíYå�ã� 0�õCâYãaâYçJå�ß��wç�ä*áüécñ[ú$ßÖå�ã�æ4ç�ð»ê°çJäYãwäLá��ïLåréwú$ä�ú$ßÖá�â �°çJá�â(á�ãwå�ð»ßÖä;écñ¸àGç�å�ßÖã¬ä*á�ãEï��
"�çEú ïLçKú.ãºòLäYçEú á�â°éEáoá�âYã �°ãEéJï�àTß�ä á�âYã�ú$ßÖå�ãºú$ß�ñÖñ@�ùã�ãwð!�°ãEïYï*ã§ï ß�ä á�âYã�æwécè�ãEàoçcëá�â�ã"ú$ß�å�ã»ß�ä�éEä0�9å�ãEéEñÖß��Eécá�ßÖçJä �8õCâYãUécä°à=úCãwåa߸àtöOá�â;écáoé�à�á�âYß�äYè�àaà�áüécä°ï5öGú.ã»ïLç]äYç�á�òLäYçEú�ôõCâYã à�çJñ�íYá�ß�çJä éJï*ç�êYá�ãEï�ßÖä�á�âYßóàCê°écê°ãwå�ßóàCá�çUéJïYï]ðUçJå�áüécå � ãwøLá�åüéT÷�ã¬å�á�ßóæ4ãEà � écå�ç�íYä°ï]á�âYãâYß�äYèJã�÷�ãwå�á�߸ætãEà�éJàoà�â�çcú$ä�ß�ä �^ßÖèJí�å�ã;0�ô � , çJå�áréEå- ]߸àoé]úîé���çcë¿æ4çJä;à�á�åüécß�äYßÖäYè9é �°ãEé�ï á�ç
�^ßÖèJí�å�ã50�� <kßÖå�ã�ú$ßÖá�âºðUçJå�áüécåæ4ãwå�áréEßÖä(æ¬écèJã§àÀë�çJå�éEñÖñ^å�ãEéEñÖß��Eécá�ßÖçJä;à4ô¦õCâYãoã��©ãEæ4á¦çcë.á�âYã�ð»ç�å�áüécå¦ß¸à�á�ç�à�íYå�å�ç�íYä°ï]ãEé�æ¾â�âYßÖäYè�ã÷�ãwå�á�ãwø�ú$ßÖá�â à�ð�éEñÖñæwéEèJãEàtô]õCâ�ã �°ãEéJï�éEä°ï�æ¾â;écßÖä9ãEï*è�ãEà�æ¬écäYäYç�áoæ4å�ç�à�à�écä�9çcë¦á�â�ã�éJïYïLãEïæwéEèJã»ãEïLèJãEà��A-5ã¬ð»ð�é�-(à=ßÖä°æ4ã�á�â�ã �°ãEéJï�߸à�ßÖä°ïLãwê°ãwä°ï*ãwäLá�çEë�éEñÖñ.æwéEèJã�÷�ãwå�á�߸æ4ã§à�écä°ï�á�âYãærâ°écß�ä»ß¸àßÖä°ï*ã¬êùã¬ä°ï*ãwäLáçcë�écñÖñ �YíYá.á�âYã�á=ú.ç�âYß�äYèJã�÷�ã¬å�á�ßóæ4ãEàtôOЦñ¸à�ç�ö*äYã¬ßÖá�â�ãwåCá�âYã��°ãEéJï»äYç�åCá�âYãærâ°écß�ä»÷�ãwå�á�ãwøoæ¬écä �°ã�ãwð!�ùã§ïYï*ãEï�ß�ä°à�ßóï*ã�éEä0�Uçcë^á�â�ã�æwécè�ãEàCætå�ãEéEá�ãEï ���á�âYã�ðUçJå�áüécå.à�ß�ä°æ4ã�éEñÖñà�í;æ¾â æwécè�ãEà�éEå�ã %E(¡æwécè�ãEà4ô,8�á$ßóàÀâ;écårï]á�ç»à=ãwã�á�âYã�í�ä°ï*ãwå�ñ��LßÖäYè�à=á�å�í;æ4á�íYå�ã�çEëá�âYã æ4çJðUêùç�äYãwäLáràß�ë�ð»çJå�árécå$÷�ã¬å�á�ßóæ4ãEà.écå�ã�à=âYçEú$ä[ô¦õCâYã�å�ãwð�éEßÖäYß�äYè�æ4çJðUêùç�äYãwäLá¦ï*߸éEèJåüécð�àtöùá�âYãwå�ãtë�çJå�ã�ö°ï*ç»äYç�áà�â�çcú éEä0�(ðUçJå�áüécå�÷�ã¬å�á�ßóæ4ãEàtö �YíYáaá�âYã�� à�âYç�íYñ¸ï<�ùã�íYä°ïLãwårà=á�ç�çLï�á�ç �ùã�êYå�ãEà�ãwäLáwô , çJå�árécå�ßóàécñóà�ç�å�ã���íYß�å�ãEï"ú$â�ãwä�á�ú.ç�æ4çJðUêùç�äYãwäLárà$éEå�ãaæ4çJä�äYãEæ4á�ãEï5ô
<Kã à�é���á�â°éEá�á�â�ã�� *�å�ãEà=ê[ô �»ö �$ö l+5$á�ã¬å�ð»ß�ä°écñ©ß¸à���Û4Ô½þtÓLÕ�þ�× �/*�å�ãEà=ê[ô Kö�f�ö � 5.ß�ë<ßÖáüà�°ãEéJï<*½ñóéE�°ãwñÖñ�ãEï �m5߸àCãwð!�°ãEïYï*ã§ï"ßÖä°à=߸ï*ãìßÖárà¦æwéEèJã�ö°éEä°ïºá�â°écá$ß�á$߸àCçJå�ßÖãwäLá�ã§ï� *�å�ãEà=ê[ô �Cö � öf 5<çJá�âYãwå�ú$ßóà�ã�ô<õCâYã�êYå�çJê°ãwå�á�ßÖã§àWçcë^á�âYã�æwéEèJãEà.écä°ï»á�âYã�ðUçJå�áüécå.ãwä°à�í�å�ã¦á�â°éEáwö*ß�ë^á�âYã � *½å�ã§à�ê[ô�»ö��$ö�l�5Gá�ã¬å�ð»ß�ä°écñYßóàGçJå�ß�ãwäLá�ãEï���*½å�ãEà�ê!ô Kö f"ö � 5rö�á�â�ãwä"ß�árà � *�å�ãEà=ê[ô ��ö�laö �b5^á�ãwå�ð»ßÖä°éEñécñóà�ç»ßóàCçJå�ßÖãwäLá�ãEï �/*�å�ãEà=ê[ô Kö f"ö�� 5üô?��ç�á�ã�á�â°éEá�ßÖá$ßóà�éEñ¸à=ç»ê°ç�à�à=ß��Yñ�ã�ë�ç�å�á�âYã�� *�å�ãEà=ê[ô �b5á�ã¬å�ð»ß�ä°écñ©á�ç!�ùãaçJå�ßÖãwäLá�ãEï� *�å�ãEà=ê[ô � 5$éEä°ïºá�âYã � *½å�ãEà�ê!ô�l+5îá�ãwå�ð»ßÖä°éEñ°á�ç!�ùãaçJå�ßÖãwäLá�ãEï �*½å�ãEà�ê!ôFf 5ìà�ß�ð"íYñ�áréEäYãwçJí;à�ñ���ôoõCâY߸à�ãwä°à=íYå�ãEà�á�â°écá écá�ñ�ãEéJà=á�çJäYã»á�ãwå�ðUßÖä°éEñOßóà�ïLßÖå�ã§æ4á�ãEï(éwúîé �ë�å�ç�ð á�â�ã�ú$ß�å�ã�ô
����� ������� ����Ð�à�æ¬écä<�ùãUà�ã¬ãwä]ë�å�ç�ðJ�OßÖè�íYå�ã!$Lö�á�âYã�èJåréEêYâ(ë�çJåaæ4çJå�äYãwåüà¿ßóà�écñóà�ç éºà=á�å�ßÖäYè�çcë>�°÷�ã �m(,æ¬écèJã§à4ôõCâYã�ætçJå�ä�ãwå �±à�á=ú.ç�á�ãwå�ðUßÖä°éEñ¸àGéEå�ã¦ñ¸éE�°ãwñ�ñÖãEï���éEä°ï �?ßÖä �Oß�èJíYå�ã�$LôõCâYã�ç�á�âYã¬åCá�â�å�ãwãìæ4çJå�äYãwåüàæwéEä �°ãoç��Yáüécß�äYãEïQë�å�çJðG�OßÖè�íYå�ã�$ ���å�ãwñóéE�°ãwñÖñ�ßÖäYè�� éJà�� *¡écä°ï]ã¬øYærâ°écä�èJßÖä�è"ñóéE�°ãwñ �� �ú$ßÖá�âu� 45röYçJå �kéJà:l *¡écä°ï�ãwø�æ¾â°éEäYèJß�äYèoñ¸é��°ãwñ ��� ú$ßÖá�â7u���5röYç�å?�ùç�á�â[ôîÐ�è�éEßÖä[öYá�âYã�êYå�ç�êùã¬å�á�ß�ãEà$çcëæwéEèJãEà$ãwä°à=íYå�ãEàCá�â°écáìécá$ñ�ãEéJà=á$çJäYãaá�ãwå�ð»ßÖä;écñ°ß¸à$ï*ß�å�ãEætá�ãEï»éwúîé ��ë�å�çJð á�âYãaæ4ç�å�äYãwå¬ô
Kreise als Kafige und Stabilisatorenin Kafigen nur sehr begrenzt Platz!je zwei Kafige durch zwei adjazenteGelenkknoten verbundenStabilisatoren auf folgenden Folienweggelassen
jeder Kafig kann nur einen blauen Knotenaufnehmen
zeigt Richtung des Drahtes an
� £�B���n������� �}������������ §£�B������ �-
����� � � � ��� � � � � ����� ��� �-����� � �����çEú á�â°écáaéEñÖñæ4ç�ð»ê°çJäYã¬ä*áüà�â°éw÷�ã �°ãwãwä ï*ãEà�ætå�ß��°ãEï©ö5úCã�æwéEäKê�å�ãEà=ãwä*áaéEäKãwø�écðUêYñÖãaà�â�çcú$ß�äYèâYçEúVæ4ç�ð»ê°çJäYãwäLáràéEå�ã�æ4ç�äYäYãEætá�ãEï5ô ��çJá�ã�á�â°écá.á�ãwå�ð»ßÖä;écñ¸à<écñÖúîé��YàGâ°éw÷�ã¦á�âYãìà�éEð»ã�à=á�å�í°æ4á�í�å�ã��é �°ãEé�ï�÷�ãwå�á�ãwø9æ4çJä�äYãEæ4á�ãEï á�ç(á=úCç]â�ßÖäYè�ã»÷�ãwå�á�߸æ4ã§àC�0�9é(ærâ°éEßÖä9÷�ãwå�á�ãwø5ô7�Oß�èJíYå�ã ��K9à�âYçEú¦àâYçEú¤á=úCç�ætçJð»ê°çJä�ãwä*áüàCéEå�ãoætçJäYäYã§æ4á�ãEï©ö*á=úCç�æ4ç�å�äYã¬åràCßÖä�á�âY߸à$æwé�à�ã�ô
b
ca d
�Oß�èJíYå�ã;��K)�(õCú.ç�æ4ç�äYäYãEæ4á�ãEï�æ4çJå�äYãwåüà4ôkõCâYã �Äá�ã¬å�ð»ß�ä°écñçcëaá�âYã�ñÖçEúCãwå�ætçJå�ä�ãwå"â;éJà �ùã¬ãwä߸ïLãwä*á�ß��°ã§ï"ú$ßÖá�âºá�âYã � á�ãwå�ðUßÖä°éEñùçEëGá�âYã�íYêYê°ãwåìæ4çJå�äYãwå¬ô
2Àã§æwécñ�ñ�á�â°éEá(é�ñÖß�á�ãwåüécñ�ætçJð»ê°çJä�ãwä*áUßÖäVá�âYã9èJå�߸ïVï*åréwú$ßÖä�è â;éJà�ÜJÕ a �cØtÕ3C�á�ãwå�ð»ßÖä;écñ¸àtöú$âYãwå�ãEéJà[ãEé�æ¾â�ñÖß�á�ãwåüécñ�çEë°á�âYãá�å�íYá�âoà�ã¬á�á�ß�äYèìæ4çJð»ê°ç�äYãwäLá^éE�°çE÷�ãWâ;éJà�þ��cܧ?4Õ½ÿ�A�CÀá�ãwå�ðUßÖä°éEñ¸à4ô!õCâYãíYäLí°à�ã§ï�á�å�í�á�â�à�ã¬á�á�ß�äYè�á�ãwå�ð»ß�ä°écñóà[écå�ã�äYç�áæ4ç�äYäYãEæ4á�ãEï�á�çìá�âYã¦æwéEèJãEà^çcë^éEä0�açJá�âYãwåæ4ç�ð»ê°çJäYã¬ä*áßÖä#b @ ô%8,ä(á�âYã§à�ãUæwéJà=ãEà4ö[á�â�ãoßÖä°æ4ßóï*ãwäLá�á�ãwå�ðUßÖä°éEñi�°ãEé�ï ð�é���à�ß�ð»êYñ�� �°ã��ré��°à�ç�å8�°ãEï;��]á�âYããwá�âYãwå- LöYß�ë^á�âYãaéJïcû�é�æ4ãwäLá$ñÖßÖá�ãwåréEñ�C�(,æwéEèJãa߸àCçLæwæ4í�êYßÖãEï»ß�ä]éoå�ã§écñÖß��Eécá�ßÖç�ä[ô�O�"& &� � 75Þ°þCÚ�Û�Ü4ÝYÞ%bM@�Þ�ÜcØ¿Ü"Ûrþ�ÜJÿ�Ô��¬ÜJÕ,Ô���Ó�Ô �¿Ü�ÓY× ��Ó*ÿ�AoÔ ��Õ Þ°þìÑLÓY×*þtÛrÿ AJÔ¸Ó�ÚoÚ�Û4Ô¸×�×�Û�Ü��<Ô¸ÓJÚÔ�Ø���ÛtÔ½þtÓ*աܧ¦4ÿÖþH:6<#%!�!>=g� *�ß�÷�ãwä(é�å�ãEéEñÖß��Eécá�ßÖçJä!ö5çJå�ßÖãwäLá�á�â�ã"è�å�߸ï9ï*åüé§ú$ß�äYè�á�ãwå�ð»ßÖä;écñ¸à$ãwø�éJæ4á�ñ�� éJà�á�âYã�å�ã§écñ�(ß��§écá�ß�çJä�á�ã¬å�ð»ß�ä°écñóà4ô^õCâYãaï*ã��°ä�ßÖá�ß�çJä�çcë<çJå�ßÖãwäLáréEá�ß�çJä»ë�çJå$å�ãEécñ�ß��EéEá�ßÖç�ä»á�ã¬å�ð»ß�ä°écñóàWãwä°à=íYå�ã§àCá�â°éEáæ4ç�ä°ï*ßÖá�ßÖç�ä°à�� # �� 'KéEä°ï � # �� ��écå�ã»ð»ãwá¬ô�õCâYã»ä°éEá�íYå�ã"çEë¦á�âYã»ú$ß�å�ã�ö^æ4ç�å�äYã¬åwöGætå�ç�à�às(�çE÷�ãwåwöécä;ïgæ4ñóécí°à=ã(æ4ç�ð»ê°çJäYãwäLárà�ã¬ä°à�íYå�ãEàoá�â°éEá»æ4ç�ä°ï*ß�á�ßÖç�ä � # ���� ßóà�ð»ãwáwô �Oß�ä°écñ�ñ���öGá�âYã]ä°éEá�íYå�ãçcë¦á�âYã»á�å�íYá�â�à�ãwá�á�ß�äYè(æ4ç�ð»ê°çJäYã¬ä*á�ãwä°à=íYå�ã§à�æ4ç�ä°ï*ßÖá�ßÖç�ä � # ���� ߸à�ð»ãwá¬ô�õCâ°écáa߸à4ö^á�âYãUèJå�ßóïï*åüé§ú$ß�äYè�߸àCçJå�ßÖãwäLáré��YñÖãìß�ë>bM@(â°é�à�éoå�ãEéEñÖß��Eécá�ßÖçJä!ô
��çEúké�à�à�í�ð»ã�á�â°écá.á�âYã¦á�ã¬å�ð»ß�ä°écñóà�çEë^á�âYã¦èJå�߸ï�ï*åréwú$ßÖä�è�â°éw÷�ã?�°ãwãwä�çJå�ßÖãwäLá�ãEï©ô+�Yå�ç�ðdá�âYßóàúCãaú$ßÖñ�ñGæ4ç�ä°à�á�å�í°ætá�é»å�ãEéEñÖß��§écá�ß�çJä�ë�çJå�bA@Gô�õCâYßóà�å�ãEéEñÖß��Eécá�ßÖçJä�â°éJà�é"í�äYßÖá�çEëîï*߸à=árécä;æ4ãoã���í°écñá�ç ��%Lôb����íYßÖ÷�écñ�ãwäLá�ñ���öJï*ß�÷*ßóï*ãìécñÖñ©æ4ç�ç�årï*ß�ä°écá�ãEà �� ��%�ë�ç�å$é�íYäYßÖáçEë<ï*߸à=árécä;æ4ã�ã���í°écñ°á�ç �Jô�-5ã¬áá�â�ã�ñ�çEúCãwå.ñÖã4ë�á$è�å�߸ï�æ4ç�å�äYã¬å$â°éw÷�ã�ø0(O��æ4ç�ç�årï*ß�ä°écá�ãEà* %*ö4% 5üô
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (26/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schritt 2.2: Klauseln
��K ������������ ��������������������
aT dT
cT
bT
aR
dR
bR
bB
aB dB
�Oß�èJíYå�ã;�aD0�A=ñ¸éEí°à�ã æ4çJðUêùç�äYãwäLá���ï*åüéwú$ägú$ßÖá�â � éEä°ï � á�ãwå�ð»ßÖä°éEñCç�å�ßÖã¬ä*á�ãEï Kö$éEä°ï lá�ã¬å�ð»ß�ä°écñ°çJå�ßÖãwäLá�ã§ï�� ô
�OßÖè�íYå�ã!��C0�?=ñ¸écí;à�ã�á�ãEà�á�ßÖäYè�ætçJð»ê°çJä�ãwä*á.ú$ßÖá�â �°ç�á�á�ç�ðÒá�ãwå�ð»ßÖä°éEñ©æwécêYê°ãEï
Im wesentlichen ein Kafig, der 2 blaue Knoten aufnehmen kann⇒ Mind. einer der 3 ausgehenden Drahte ist auswarts gerichtet!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (27/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schritt 2.3: Variablen
� £�B���n������� �}������������ §£�B������ �C
� *Cå�ãEà�ê!ô�9öNf"ö � 5rö[á�âYã¬ä(á�âYã�� *½å�ã§à�ê[ô���öNl�ö �b5�á�ãwå�ðUßÖä°éEñ^écñ¸à=ç]ßóà�çJå�ßÖãwäLá�ãEï �1*½å�ã§à�ê[ôKöNf�ö � 5üô "�çEúCãw÷�ã¬åwö°ßÖá�ßóà¿ê°ç�à�à�ß��YñÖãoë�çJå�á�âYã�� éEä°ï �Òá�ãwå�ð»ßÖä;écñ¸à$à=ßÖð�íYñÖáüécäYã¬çJí°à=ñ���á�ç �°ãçJå�ßÖãwäLá�ã§ï écä°ï �Nå�ãEà=êùã§æ4á�ß�÷�ãwñ���ô : ß�ð»ßÖñóécå�ñ���ö[ßÖáa߸à�ê°ç�à�à�ß���ñÖã»ë�çJåoá�âYã � éEä°ï l á�ãwå�ð»ß�ä°écñóàà�ß�ð"í�ñÖáréEäYãwç�í°à�ñ��oá�ç!�ùã�ç�å�ßÖã¬ä*á�ãEï�� écä;ï{fdå�ã§à�ê°ãEæ4á�ßÖ÷�ãwñ���ô
���>� � ����������� �������
õCâYãaá�å�í�á�â(à=ãwá�á�ßÖäYèUæ4ç�ð»ê°çJäYãwäLá¦ß¸à¦à�âYçEú$ä]ß�ä��Oß�èJíYå�ã �&�Jô:8,árà$âYãEécå�á�߸à¦éoê°écß�å�çEë$ætçJäYäYã§æ4á�ãEï
aTL dTL
aL
dL
aBL dBL aBR dBR
aR
dR
aTR dTR
�Oß�èJíYå�ãA���&��õCâYã(á�å�íYá�âVà�ãwá�á�ß�äYè�æ4ç�ð»ê°çJäYãwäLá�� ï*åréwú$äkú$ßÖá�âká�âYã�C�(,ætñÖí°à=á�ãwå�ßÖäká�âYã�C�(,æwéEèJãæ4ç�å�å�ã§à�ê°çJä°ïLßÖäYè�á�ç�á�âYã�íYä�äYãwè�éEá�ãEï�ñÖß�á�ãwåüécñ,ôCE(¡æwéEèJãEàtô»õCâYãUæwécè�ã"ç�äKá�âYãoñÖãtë�á�æ4çJå�å�ãEà=ê°çJä°ïYà�á�ç�á�â�ã"íYä�äYãwè�éEá�ãEï(ñÖß�á�ãwåüécñéEä°ï(á�âYãUæwécè�ã"ç�äá�â�ã"å�ßÖèJâLá�á�ç�á�âYã�äYãwè�écá�ã§ïKñÖß�á�ãwåüécñ,ôUÐÄætñÖí°à=á�ãwå�çcëîá�âYå�ãwã�ßÖä°ï*ã¬êùã¬ä°ï*ãwäLá��ùã§éJïYà�߸à�ætçJäYäYã§æ4á�ãEïú$ßÖá�â»á=úCçaærâ°écß�ä �°ãEé�ïYàCá�çaá�âYãìæ4çJðUð»çJäoâYß�äYèJã¦çcë<á�â�ã�C�(,æwéEèJãEàtô : ßÖä°æ4ã¦á�â�߸àæ4ñÖí;à�á�ã¬åWßóàGßÖä»ç�äYãçcëîá�âYãoá=ú.çFCE(¡æwécè�ãEà�ßÖä9éEä0��å�ãEéEñÖß��§écá�ß�çJä[ö©ßÖá�ï*ßóà�êYñóéJæ4ã§à�éEñÖñGß�ä°æ4߸ïLãwä*áìà�ß�äYèJñ�ã �°ãEéJïYàtö[ãwä°à�í�å�ßÖä�èá�â;écáìécñÖñ!éJà�à�çLæ4ßóécá�ã§ï]á�ãwå�ð»ßÖä°éEñ¸àécå�ã�çJå�ß�ãwäLá�ãEï�éwú$é��"ë�å�çJð á�âYã�CE(¡æwécè�ã�ô
����� ����� �����
õCâYã�æ4ñóécí°à=ã]á�ã§à�á�ß�äYè9æ4ç�ð»ê°çJäYãwäLá�ßóà"à=âYçEú$ägß�ä �^ßÖèJí�å�ã<��DLô 8,árà�âYãEéEå�á�߸àoé9à�ß�äYèJñ�ã D�(,æ¬écèJã�ô: ß�ä°æ4ã�á�âYßóà�æ¬écèJã æwécä æ4çJäLáréEßÖä écá¦ð»ç�à=á$á�ú.ç"ß�ä°ï*ãwê°ãwä;ï*ãwäLá?�ùã§éJïYàtö5ßÖá$ð�í°à�á@�°ãoá�â°éEá�éEá�ñ�ãEéJà=áçJä�ã�á�ãwå�ðUßÖä°éEñ5߸àCç�å�ß�ãwä*á�ãEï»éwú$é��"ë�å�çJð ß�áwô
8½ë<é�á�ã¬å�ð»ß�ä°écñYßóàWäYç�á$í°à�ã§ï"ßÖä»á�âYã�è�å�߸ïUï*åréwú$ßÖä�èYöYá�â�ã�æ4çJå�å�ãEà=ê°çJä°ï*ß�äYèoèJåüécêYâ�æ4ç�ð»ê°çJäYã¬ä*áá�ã¬å�ð»ß�ä°écñ°ß¸à �üæwécê�êùã§ï� ���éEêYê°ãwä°ï*ß�äYè»é!%E(¡æwéEèJã�á�ç�ßÖá¬ô �OßÖè�íYå�ã ��C"à=âYçEú¦à�é�æ4ñóécí°à=ã�á�â°écá$â;éJàçJä�ã"á�ãwå�ð»ß�ä°écñ[ú$ß�á�â9æwéEê�éEä°ï(ð»çJå�árécå *,æ4ç�íYñ¸ï*ä � á�å�ãEà�ßóà�á�5üôoõCâYßóà�ãwä°à=íYå�ãEà�á�â°écá�á�â�ãoá�ãwå�ð»ßÖä°éEñ߸à¦çJå�ß�ãwäLá�ãEï9Õe���GÜ�Û�×cئá�âYã�æ4ñóécí°à=ã�ö°á�âYãwå�ã���ºë�çJåüæ4ßÖä�è»çJäYãoçEë$á�âYã�å�ãwð�écß�äYßÖä�è"á�ãwå�ð»ß�ä°écñóàCá�ç �°ãçJå�ßÖãwäLá�ã§ï»éwú$é�� ��»å�ãEïLí°æ4ßÖä�èoá�âYãaæwéEê°éJæ4ß�á��"çEëá�âYã�D�(,æwéEèJã��0�»ç�äYã�ô
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (28/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schritt 2.4: Kreuzungen
��D ������������ ��������������������
aL
dL
cLbL
aR
dR
cR bR
bTcT
dTaT
aB dB
bB
cB
�Oß�èJíYå�ã ��%0� õCâYã»ætå�ç�à�às(�çE÷�ãwåaæ4çJð»ê°ç�äYãwäLá���ïLåréwú$ä�ú$ßÖá�âKá�âYã��décä;ï �Òá�ãwå�ð»ßÖä°éEñ¸à$çJå�ßÖãwäLá�ãEïKö°éEä°ïºá�âYã �géEä°ï;l8á�ãwå�ð»ßÖä°éEñ¸àGçJå�ßÖãwäLá�ã§ï{f�ôFabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze
VL 05 – Lokalisierung und virtuelle Koordinaten (29/40)Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schwere UDG-Erkennung
SatzUnit-Disk-Graph-Erkennung ist NP-schwer.
Zu 3SAT-Formel konstruiere Graphen G wie beschrieben
Eine erfullende Belegung der Variablen verrat uns eine eineEinbettung als UDG
Knotenpositionen ubernehmen wir dann aus unseren Zeichnungender Gadgetsnur die Einbettung der roten Elemente passen wir an
Eine Einbettung als UDG verrat uns eine erfullende Belegungder Formel
Die exakten Knotenpositionen sind dann nicht wichtigkombinatorische Einbettung der roten Elemente reicht!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (30/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Unit-Disk-Graph-Approximation
Wenn es schwer ist, einen Graphen als UDG einzubetten, kommtman dann wenigstens ”dicht“ heran? Definiere Qualitat einerEinbettung p als
q(p) :=max{u,v}∈E ‖p(u)− p(v)‖min{u,v}6∈E ‖p(u)− p(v)‖
q(p) ≤ 1: Einbettung belegt UDG, sonst nur1/q(p)-Quasi-Unit-Disk-Graph!
Man kann den Beweis noch so ”aufbohren“, dass er folgendeReduktion liefert:
Formel erfullbar⇒ Graph einbettbar mit q < 1Formel nicht erfullbar⇒ Graph nicht einbettbar mit q <
√2.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (31/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Was genau bedeutet das?
Es ist NP-schwer, einen Unit-Disk-Graphen zu erkennenalso gibt es keinen Polynomialzeitalgorithmus, der UDGentsprechend einbettet.
Es ist auch schwer, zu erkennen, ob man einen Graphen mitQualitat <
√2 einbetten kann
Also sind auch 1/√
2-Quasi-Unit-Disk-Graphen schwer zuerkennenDamit ist auch UDG-Approximation schwer!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (32/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Beste bekannte Approximation
Satz (ohne Beweis)Es gibt einen Algorithmus mit polynomieller Laufzeit, der mit hoherWahrscheinlichkeit eine Einbettung mit Qualitat inO(log2.5 n
√log log n) berechnet.
Mit hoher W’keit: p > 1− 1/nGanz grobe Skizze:
1 LP-Losung liefert echte Metrik auf Knoten(Definitheit, Dreiecksungleichung)
2 Knoten werden geschickt in Rn eingebettet3 Einbettung wird zufallig auf den R2 projiziert4 Ergebnis wird nach festen Regeln verfeinert
(z.B. Erzwingen von Minimaldistanzen)
Gleich mehrere schwere Geschutze!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (33/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Noch ein schweres Problem
Satz (ohne Beweis)Es ist NP-schwer, zu erkennen, ob man einen Graphen mitvorgegebenen Kantenlangen einbetten kann. Das gilt auch noch,wenn man sich auf UDGs einschrankt.
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (34/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Weitere Ergebnissen
Wenn man Richtungen und Entfernungen kennt, ist Lokalisierungleicht (klar)
schon beliebig kleine Fehler machen das Problem schweres macht keinen Unterschied, ob man sich auf UDGs einschrankt
Wenn man nur Richtungen kennt, kann man in Polynomialzeiteine entsprechende Einbettung finden
wenn man aber nach einer entsprechenden UDG-Einbettung fragt,wird’s schwer!
Das Finden plausibler Koordinaten ist schon in den meistenidealisierten Fallen schwer!
Heuristiken fur dichte Graphen gehen davon aus, dass plausibleLosungen ”ziemlich“ eindeutig sind!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (35/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Weitere Ergebnissen
Wenn man Richtungen und Entfernungen kennt, ist Lokalisierungleicht (klar)
schon beliebig kleine Fehler machen das Problem schweres macht keinen Unterschied, ob man sich auf UDGs einschrankt
Wenn man nur Richtungen kennt, kann man in Polynomialzeiteine entsprechende Einbettung finden
wenn man aber nach einer entsprechenden UDG-Einbettung fragt,wird’s schwer!
Das Finden plausibler Koordinaten ist schon in den meistenidealisierten Fallen schwer!
Heuristiken fur dichte Graphen gehen davon aus, dass plausibleLosungen ”ziemlich“ eindeutig sind!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (35/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Weitere Ergebnissen
Wenn man Richtungen und Entfernungen kennt, ist Lokalisierungleicht (klar)
schon beliebig kleine Fehler machen das Problem schweres macht keinen Unterschied, ob man sich auf UDGs einschrankt
Wenn man nur Richtungen kennt, kann man in Polynomialzeiteine entsprechende Einbettung finden
wenn man aber nach einer entsprechenden UDG-Einbettung fragt,wird’s schwer!
Das Finden plausibler Koordinaten ist schon in den meistenidealisierten Fallen schwer!
Heuristiken fur dichte Graphen gehen davon aus, dass plausibleLosungen ”ziemlich“ eindeutig sind!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (35/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Eine Heuristik: AFL(Anchor-Free Localization)
GrundideeKraftebasierte Verfahren minimieren lokalenStress iterativ ∑
{u,v∈E}
(‖u, v‖ − `uv )2
ProblemLokale Optima konnen Uberlappungenaufweisen!
Losung?Finde uberlappungsfreie Initiallosung!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (36/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Eine Heuristik: AFL(Anchor-Free Localization)
GrundideeKraftebasierte Verfahren minimieren lokalenStress iterativ ∑
{u,v∈E}
(‖u, v‖ − `uv )2
ProblemLokale Optima konnen Uberlappungenaufweisen!
Losung?Finde uberlappungsfreie Initiallosung!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (36/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Eine Heuristik: AFL (Initiallosung)
1 Finde vier extremale und einen zentralen KnotenUN ,UW ,US ,UE ,UC
2 Bestimme Hop-Entfernungen zu diesen Knoten3 Bette Knoten anhand von Polarkoordinaten ein
ρv = dG(v ,uC) θv = arctandG(v ,UN)− dG(v ,US)
dG(v ,UW )− dG(v ,UE)
Funktioniert nicht so gut,wenn das Gebiet komplexerwird!
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (37/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Weitere heuristische Ideen
Dichte Netze erlauben gute lokaleLosungen
viele lokale Losungen zu berechnen skaliertgut!setze Losungen iterativ oder hierarchischzusammen
Erkennen von inneren Knoten undRandknoten
Ausnutzen von lokalen StrukturenAusnutzen von statistischen Eigenschaften
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (38/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Weitere heuristische Ideen
Dichte Netze erlauben gute lokaleLosungen
viele lokale Losungen zu berechnen skaliertgut!setze Losungen iterativ oder hierarchischzusammen
Erkennen von inneren Knoten undRandknoten
Ausnutzen von lokalen StrukturenAusnutzen von statistischen Eigenschaften
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (38/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Zusammenfassung
Ankerbasierte Lokalisierungfast ausschließlich Schatztheorie oder Heuristikenkaum algorithmische Analyse (wegen unklarer Parameter?)Ausnahme: Hop/HS zu eindimensionaler Lokalisierung
Ankerfreie Lokalisierungklarere algorithmische Problemevor allem NegativergebnisseHeuristiken fur dichte Graphen, aber ohne Garantien
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (39/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Literatur
1 R. O’Dell, R. Wattenhofer: Theoretical aspects ofconnectivity-based multi-hop positioning. In: TheoreticalComputer Science 344:1, pp. 47-68, 2005
2 H. Breu, D.G. Kirkpatrick: Unit Disk Graph Recognition isNP-Hard. In: Computational Geometry. Theory and Applications9, 1993
3 F. Kuhn, T. Moscibroda, R. Wattenhofer: Unit Disk GraphApproximation. In: ACM Joint Workshop on Foundations ofMobile Computing (DIALM-POMC), 2004
Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 05 – Lokalisierung und virtuelle Koordinaten (40/40)
Institut fur Theoretische InformatikLehrstuhl Algorithmik