Topologiekontrolle in Ad-hoc und Sensornetzwerken

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?


Definition: Topologiekontrolle

• Gegeben: Graph G={V,E}

• Gesucht: G‘={V,E‘E}

• so dass wir effizient Routen

• und Laufzeit des Netzwerks erhöht wird


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


Stretch factors

• Energy Stretch Factor =

• Distance Stretch Factor

• Hop Stretch Factor

),(

),(

,

max'

vuE

vuE

Vvu G

G


Beispiel: Energy Stretch Factor


Energie Stretch Factor


Energie Stretch Factor


Energy Stretch Factor

u v

w



u v

w



Aus 1 folgt:




Stretch factors

Analog Distance- und Hop Stretch Factor:


Verwendete Graphen

• Kommunikationsgraph

• Unit Disc Graph

• Yao Graph

• Cone-Covering Graph

• Delaunay Triangulierung

• Gabriel Graph

• Relative Neighborhood Graph


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


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


Yao Graph



• Cuv := Kegel vom Knoten u in dem v liegt)},(),(:,,|),{( vudwudCwVvuvuE uv


Yao Graph





Yao Graph





Yao Graph




• Nur ungerichtete Kanten in den Yao Graph aufnehmen

)},(),(:,,|),{( vudwudCwVvuvuE uv


Yao Graph




• Nur ungerichtete Kanten in den Yao Graph aufnehmen

)},(),(:,,|),{( vudwudCwVvuvuE uv


Cone Covering Graph


• Nachbarn von u:alle zu u adjazenten Knoten im Unit Disc Graph

• Ordne Nachbarn nach ihrem Abstand zu u


Cone Covering Graph




• Prüfe, ob der Kegel bereits abgedeckt wird

u

Bsp: v ist der nächste Nachbar zu uu betrachtet v als erstes

v


Cone Covering Graph


• Nachbarn von u:alle zu u adjazenten Knoten im unit disc graph



u

v

α

Füge Kante ein, falls der Kegel von v noch nicht abgedeckt wird.


Cone Covering Graph





u

v

α

Füge Kante ein, falls der Kegel von v noch nicht abgedeckt wird.

u

v


Cone Covering Graph





Kegel von v bereits abgedeckt, Kante nicht hinzunehmen

u

v


Cone Covering Graph




• Prüfe, ob der Kegel bereits abgedeckt wird• Definiere dazu:


Ergebnis für einen kompletten Graphen


Delaunay Triangulierung


• Prüfe, jede 3-elementige Teilmenge X von Knoten:• Kante einfügen: X erfüllt die Umkreisbedingung• Sonst: verwerfen

• nicht lokal!


k-lokalisierte Delaunay Triangulierung


• 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!


1-DT nicht planar

• xyz und uvw erfüllen 1-DT Eigenschaft

• nicht k-lokalisierte DT würde uwv verwerfen


Gabriel Graph

• Kante, falls die Umkreisbedingung nicht verletzt wird


Relative Neighborhood Graph

• Im Schnitt der Umkreise von je zwei Knoten darf kein anderer Knoten liegen:


Verwendete Graphen

• Kommunikationsgraph

• Unit Disc Graph

• Yao Graph

• Cone-Covering Graph

• Delaunay Triangulierung

• Gabriel Graph

• Relative Neighborhood Graph


Lokale Algorithmen der Topologiekontrolle

• Cone Based Topology Control (CBTC)

• Delaunay Based Topology Control

• Relative Neighbor Topology Control (XTC)


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


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


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



• 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!



• Für 1-Zshg. Knoten Gabriel Graph Kante einfügen:

• Grund: Triangulierung nicht möglich

• Aber: keine Informationsverlust, deshalb GG-Kante


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


• : Ordnung der Nachbarschaft von u und v

• Wie geht’s?


vu ,



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


Vielen Dank!

Documents

Topologiekontrolle in Ad-hoc und Sensornetzwerken