View
21
Download
0
Category
Preview:
DESCRIPTION
Topologiekontrolle in Ad-hoc und Sensornetzwerken. Einleitung. Was ist ein Ad-Hoc und Sensorsnetzwerk? Welche Probleme haben Ad-Hoc und Sensornetzwerke? begrenzte Ressourcen Wie kann man diese Probleme lösen? Topologiekontrolle Doch was ist Topologiekontrolle?. - PowerPoint PPT Presentation
Citation preview
Alexander ManeckeInstitut für Informatik FU Berlin15.06.2006
Topologiekontrolle in Ad-hoc und Sensornetzwerken
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 2
Einleitung
• Was ist ein Ad-Hoc und Sensorsnetzwerk?
• Welche Probleme haben Ad-Hoc und Sensornetzwerke?• begrenzte Ressourcen
• Wie kann man diese Probleme lösen? • Topologiekontrolle
Doch was ist Topologiekontrolle?
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 3
Definition: Topologiekontrolle
• Gegeben: Graph G={V,E}
• Gesucht: G‘={V,E‘E}
• so dass wir effizient Routen
• und Laufzeit des Netzwerks erhöht wird
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 4
Geforderte Eigenschaften an Algorithmen der Topologiekontrolle
Eigenschaft/Problem Graphentheorie
Zusammenhang Zusammenhang
Symmetrie Symmetrie
Interferenz z.B. Sparse
Planarität Planarität
Stretch Factors Stretch Factors
Durchsatz ?
Anpassbarkeit
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 5
Stretch factors
• Energy Stretch Factor =
• Distance Stretch Factor
• Hop Stretch Factor
),(
),(
,
max'
vuE
vuE
Vvu G
G
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 6
Beispiel: Energy Stretch Factor
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 7
Energie Stretch Factor
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 8
Energie Stretch Factor
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 9
Energy Stretch Factor
u v
w
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 10
Energy Stretch Factor
u v
w
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 11
Energy Stretch Factor
Aus 1 folgt:
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 12
Energy Stretch Factor
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 13
Stretch factors
Analog Distance- und Hop Stretch Factor:
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 14
Verwendete Graphen
• Kommunikationsgraph
• Unit Disc Graph
• Yao Graph
• Cone-Covering Graph
• Delaunay Triangulierung
• Gabriel Graph
• Relative Neighborhood Graph
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 15
Kommunikationsgraph,Unit Disc Graph
Kommunikationsgraph:• beschreibt welche anderen Zwischenstationen jeweils
erreichbar sind
Unit Disc Graph:•
Im Beispiel:• u ist zu v adjazent• w ist zu v adjazent• aber w ist nicht adjazent zu u
Die folgenden Algorithmen werden immer eingeschränkt auf den Unit Disc Graph betrachtet.
1,, vuEvu
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 16
Yao Graph
• Gegeben: Punktmenge
• Erzeuge für jeden Punkt k Kegel mit dem Winkel α<pi/3
• Cuv := Kegel vom Knoten u in dem v liegt
• )},(),(:,,|),{( vudwudCwVvuvuE uv
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 17
Yao Graph
• Gegeben: Punktmenge
• Erzeuge für jeden Punkt k Kegel mit dem Winkel α<pi/3
• Cuv := Kegel vom Knoten u in dem v liegt)},(),(:,,|),{( vudwudCwVvuvuE uv
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 18
Yao Graph
• Gegeben: Punktmenge
• Erzeuge für jeden Punkt k Kegel mit dem Winkel α<pi/3
• Cuv := Kegel vom Knoten u in dem v liegt)},(),(:,,|),{( vudwudCwVvuvuE uv
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 19
Yao Graph
• Gegeben: Punktmenge
• Erzeuge für jeden Punkt k Kegel mit dem Winkel α<pi/3
• Cuv := Kegel vom Knoten u in dem v liegt)},(),(:,,|),{( vudwudCwVvuvuE uv
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 20
Yao Graph
• Gegeben: Punktmenge
• Erzeuge für jeden Punkt k Kegel mit dem Winkel α<pi/3
• Cuv := Kegel vom Knoten u in dem v liegt
• Nur ungerichtete Kanten in den Yao Graph aufnehmen
)},(),(:,,|),{( vudwudCwVvuvuE uv
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 21
Yao Graph
• Gegeben: Punktmenge
• Erzeuge für jeden Punkt k Kegel mit dem Winkel α<pi/3
• Cuv := Kegel vom Knoten u in dem v liegt
• Nur ungerichtete Kanten in den Yao Graph aufnehmen
)},(),(:,,|),{( vudwudCwVvuvuE uv
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 22
Cone Covering Graph
• Gegeben: Punktmenge
• Nachbarn von u:alle zu u adjazenten Knoten im Unit Disc Graph
• Ordne Nachbarn nach ihrem Abstand zu u
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 23
Cone Covering Graph
• Gegeben: Punktmenge
• Nachbarn von u:alle zu u adjazenten Knoten im Unit Disc Graph
• Ordne Nachbarn nach ihrem Abstand zu u
• Prüfe, ob der Kegel bereits abgedeckt wird
u
Bsp: v ist der nächste Nachbar zu uu betrachtet v als erstes
v
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 24
Cone Covering Graph
• Gegeben: Punktmenge
• Nachbarn von u:alle zu u adjazenten Knoten im unit disc graph
• Ordne Nachbarn nach ihrem Abstand zu u
• Prüfe, ob der Kegel bereits abgedeckt wird
u
v
α
Füge Kante ein, falls der Kegel von v noch nicht abgedeckt wird.
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 25
Cone Covering Graph
• Gegeben: Punktmenge
• Nachbarn von u:alle zu u adjazenten Knoten im Unit Disc Graph
• Ordne Nachbarn nach ihrem Abstand zu u
• Prüfe, ob der Kegel bereits abgedeckt wird
u
v
α
Füge Kante ein, falls der Kegel von v noch nicht abgedeckt wird.
u
v
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 26
Cone Covering Graph
• Gegeben: Punktmenge
• Nachbarn von u:alle zu u adjazenten Knoten im Unit Disc Graph
• Ordne Nachbarn nach ihrem Abstand zu u
• Prüfe, ob der Kegel bereits abgedeckt wird
Kegel von v bereits abgedeckt, Kante nicht hinzunehmen
u
v
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 27
Cone Covering Graph
• Gegeben: Punktmenge
• Nachbarn von u:alle zu u adjazenten Knoten im Unit Disc Graph
• Ordne Nachbarn nach ihrem Abstand zu u
• Prüfe, ob der Kegel bereits abgedeckt wird• Definiere dazu:
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 28
Ergebnis für einen kompletten Graphen
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 29
Delaunay Triangulierung
• Gegeben: Punktmenge
• Prüfe, jede 3-elementige Teilmenge X von Knoten:• Kante einfügen: X erfüllt die Umkreisbedingung• Sonst: verwerfen
• nicht lokal!
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 30
k-lokalisierte Delaunay Triangulierung
• Gegeben: Punktmenge
• Prüfe, für die k-Nachbarschaft von jedem Knoten:• Kante einfügen: X erfüllt die lokale Umkreisbedingung, d.h.,
kein anderer Knoten der k-Nachbarschaft liegt im Umkreis des berechneten Dreiecks
• Sonst: verwerfen
• Üblicherweise k=1 oder k=2
• ist lokal!
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 31
1-DT nicht planar
• xyz und uvw erfüllen 1-DT Eigenschaft
• nicht k-lokalisierte DT würde uwv verwerfen
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 32
Gabriel Graph
• Kante, falls die Umkreisbedingung nicht verletzt wird
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 33
Relative Neighborhood Graph
• Im Schnitt der Umkreise von je zwei Knoten darf kein anderer Knoten liegen:
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 34
Verwendete Graphen
• Kommunikationsgraph
• Unit Disc Graph
• Yao Graph
• Cone-Covering Graph
• Delaunay Triangulierung
• Gabriel Graph
• Relative Neighborhood Graph
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 35
Lokale Algorithmen der Topologiekontrolle
• Cone Based Topology Control (CBTC)
• Delaunay Based Topology Control
• Relative Neighbor Topology Control (XTC)
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 36
Was sind lokale Algorithmen?
• Knoten kann auf Grund seiner Informationen Entscheidung treffen
• Betrachtet höchstens seine Nachbarn
• Nachbarn sind adjazente Knoten im Unit Disc Graph
• Betrachten Algorithmen eingeschränkt auf den Unit Disc Graph
• Gegenteil: zentraler Algorithmus• Ein Knoten trifft für alle Knoten die Entscheidung
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 37
Cone Based Topology Control
• Jeder Knoten teilt Ebene in k Sektoren
• Nächsten Nachbarn in jedem Sektor suchen
• Nach und nach Sendestärke erhöhen
• Keine Position nötig
• Nur Richtung und Sendestärke
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 38
Delaunay Based Topology Control
• Lokalisierte Delaunay Triangulierung
• Grund: nur Nachbarn eines Knoten betrachten
Im Beispiel:
• ABC werden berechnet
• BCD nicht
• ABD nicht
• ACD nicht
• Weil D kennt nur C
• Problem: Kante CD soll nicht verloren gehen
A
B
CD
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 39
Delaunay Based Topology Control
• Schaue Nachbarn an (Entfernung k im Unit Disc Graph)
• Berechne k-lokalisierte Delaunay Triangulierung
• Tausche Ergebnisse mit Nachbarn
• Wenn bestätigt, dann Kante einfügen
• Für 1-Zshg. Knoten Gabriel Graph Kante einfügen
• Benötigt Position seiner Nachbarn!
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 40
Delaunay Based Topology Control
• Für 1-Zshg. Knoten Gabriel Graph Kante einfügen:
• Grund: Triangulierung nicht möglich
• Aber: keine Informationsverlust, deshalb GG-Kante
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 41
Relative Neighbor Topology Control
• Ermittle Nachbarn von u
• Speicher Nachbarn aufsteigend nach Entfernung zu u
• Tausche Liste mit Nachbarn
• Prüfe Bedingung mit erhaltenen Listen
• Bedingung: u vw
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 42
• : Ordnung der Nachbarschaft von u und v
• Wie geht’s?
Relative Neighbor Topology Control
vu ,
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 43
Relative Neighbor Topology Control
A
C
B
D
NA:={C,B,D}NB:={D,C,A}NC:={A,B,D}ND:={B,C,A}
A
C
B
D
NA(D)ND(A)={C,B} -> keine Kante von A nach DNB(D)ND(B)={}
NA(D): Teilmenge der Nachbarschaftsliste von A bis zum Element D
Seminar über Algorithmen: Topologiekontrolle, Alexander Manecke 44
Vielen Dank!
Recommended