Algorithmen fur¨ Ad-hoc- und Sensornetze · eine optimale Losung bis auf einen Faktor 2.¨ Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze¨ VL 04 – Topologiekontrolle

INSTITUT FUR THEORETISCHE INFORMATIK - LEHRSTUHL FUR ALGORITHMIK (PROF. WAGNER)

Algorithmen fur Ad-hoc- und SensornetzeVL 04 – Topologiekontrolle

Fabian Fuchs | 04. Nov. 2015 (Version 2)

KIT – Universitat des Landes Baden-Wurttemberg undnationales Großforschungszentrum in der Helmholtz-Gemeinschaft www.kit.edu

http://www.kit.edu

Topologiekontrolle

Was kann man gewinnen, indem man Kommunikation einschrankt?

Fabian Fuchs – Algorithmen fur Ad-hoc- und SensornetzeVL 04 – Topologiekontrolle (2/35)

Institut fur Theoretische InformatikLehrstuhl Algorithmik

Topologiekontrolle

TopologiekontrolleTopologiekontrolle bezeichnet alle Techniken, die die Menge deraktiven Links zwischen Knoten verringern, um Eigenschaften desKommunikationsnetzes herzustellen, ohne andere Eigenschaften zuzerstoren.

Zwei grundsatzliche AnsatzeVerringern der Sendeleistung der KnotenBeschrankung auf ausgewahlten Subgraphen

Ziel: Genug, aber nicht zu viel abschalten!In der Regel Balance zwischen mehreren Eigenschaften.



Topologiekontrolle

TopologiekontrolleTopologiekontrolle bezeichnet alle Techniken, die die Menge deraktiven Links zwischen Knoten verringern, um Eigenschaften desKommunikationsnetzes herzustellen, ohne andere Eigenschaften zuzerstoren.

Zwei grundsatzliche AnsatzeVerringern der Sendeleistung der KnotenBeschrankung auf ausgewahlten Subgraphen

Ziel: Genug, aber nicht zu viel abschalten!In der Regel Balance zwischen mehreren Eigenschaften.



Uberblick

Topologiekontrolle zur Sendeleistungsminimierung

Lokale Topologiekontrolle und SpannereigenschaftenGeometrisch definierte Graphen und ihre EigenschaftenXTC — Lokale Topologiekontrolle

Topologiekontrolle zur InterferenzminimierungVon leichten und schweren Problemen...



Wiederholung: Sendeleistung

ErinnerungSendet ein Knoten mit Sendeleistung P,empfangt ein Knoten in Entfernung d das Signalmit einer Starke P/dα (2 < α ≤ 6). Ein Knotenkann ein ungestortes Signal dekodieren, wenneine bestimmte Starke uberschritten wird.

Geeignet normiert heißt das: Knoten u erreicht Knoten v genaudann, wenn Pu ≥ d(u, v)α.



Kommunikationsgraph

DefinitionZu einer Menge von Knoten V in der Ebene ist eine Reichweiten-zuweisung eine Abbildung RA : V → R+. Sie induziert einengerichteten Kommunikationsgraphen GRA = (V ,E) mit(u, v) ∈ E ⇔ d(u, v) ≤ RA(u)

entspricht SendeleistungszuordnungPA(v) = RA(v)α

eine Reichweitenzuordnung heißt uniform,wenn allen Knoten dieselbe Reichweitezugeordnet wird.

Kommunikationsgraph dann symmetrisch!



Kommunikationsgraph







Kommunikationsgraph







Maxpower-Graph

DefinitionDer Maxpower-Graph ist der Graph der sich ergibt, wenn man jedenKnoten mit allen Knoten verbindet, mit denen er kommunizierenkann, wenn beide mit maximaler Sendeleistung Pmax (d.h. maximalerReichweite) senden.

Maxpower-Graph ist Unit-Disk-Graph

Topologiekontrolle macht vor allem dannSinn, wenn man davon ausgeht, dass derMaxpower-Graph ”zu dicht“ ist.



Sendeleistung vs. Zusammenhang

Wie stark kann man die Reichweite der Knoten verringern, ohne dassder Kommunikationsgraph unzusammenhangend wird?

Minimale uniforme Sendeleistung fur ZusammenhangGegeben: Zusammenhangender Maxpower-Graph G = (V ,E).Gesucht: Minimale uniforme Reichweitenzuordnung RA, so dass

GRA zusammenhangend ist.



Minimale Spannbaume

Minimaler SpannbaumSei G = (V ,E) ein zusammenhangender Graph und w : E → R+

eine Gewichtsfunktion. Ein Minimaler Spannbaum (MST) ist einSpannbaum T ⊆ E , der

∑T w(E) minimiert.

LemmaDie minimale uniforme Reichweite fur Zusammenhang entspricht dermaximalen Lange einer Kante in einem minimalen Spannbaum T miteuklidischem Abstand als Gewichtsfunktion.

Gibt es einen zusammenhangenden Graphen nur mit kurzeren Kanten,dann gibt es auch einen Spannbaum T ′ nur mit kurzeren Kanten.Entferne die langste Kante aus T und fuge die Kante aus T ′ hinzu, diedie beiden Teilbaume verbindet. Das verringert das Gesamtgewicht in Tim Widerspruch zu ”T ist MST“.



Minimale Spannbaume

Minimaler SpannbaumSei G = (V ,E) ein zusammenhangender Graph und w : E → R+

eine Gewichtsfunktion. Ein Minimaler Spannbaum (MST) ist einSpannbaum T ⊆ E , der

∑T w(E) minimiert.

LemmaDie minimale uniforme Reichweite fur Zusammenhang entspricht dermaximalen Lange einer Kante in einem minimalen Spannbaum T miteuklidischem Abstand als Gewichtsfunktion.

Gibt es einen zusammenhangenden Graphen nur mit kurzeren Kanten,dann gibt es auch einen Spannbaum T ′ nur mit kurzeren Kanten.Entferne die langste Kante aus T und fuge die Kante aus T ′ hinzu, diedie beiden Teilbaume verbindet. Das verringert das Gesamtgewicht in Tim Widerspruch zu ”T ist MST“.



MSTs verteilt berechnen

Bestimmung minimale uniforme Sendeleistung fur Zusammenhang?Berechne MST, propagiere maximale Kantenlange

Satz (vorerst ohne Beweis...)Es gibt einen verteilten Algorithmus zur Bestimmung eines MinimalenSpannbaums mit Laufzeit in O(n) und NachrichtenkomplexitatO(n log n + m).

MSTs sind extrem wertvoll, im Hinterkopf behalten!

Das lost das Reichweitenzuordnungsproblem fur uniformeReichweiten. Was ist, wenn wir unterschiedliche Sendeleistungenzulassen und den Durchschnitt minimieren wollen?



MSTs verteilt berechnen

Bestimmung minimale uniforme Sendeleistung fur Zusammenhang?Berechne MST, propagiere maximale Kantenlange

Satz (vorerst ohne Beweis...)Es gibt einen verteilten Algorithmus zur Bestimmung eines MinimalenSpannbaums mit Laufzeit in O(n) und NachrichtenkomplexitatO(n log n + m).

MSTs sind extrem wertvoll, im Hinterkopf behalten!

Das lost das Reichweitenzuordnungsproblem fur uniformeReichweiten. Was ist, wenn wir unterschiedliche Sendeleistungenzulassen und den Durchschnitt minimieren wollen?



Reichweitenzuordnung

Problem: Energieoptimale ReichweitenzuordnungGegeben: Zusammenhangender Maxpower-Graph G = (V ,E)

Gesucht: (Nicht-uniforme) Reichweitenzuordnung RA mitminimaler Gesamtleistung

∑v∈V RA(v)α, bei der GRA

stark zusammenhangend ist.

minimiert auch durchschnittliche Sendeleistungmuss nicht unbedingt symmetrisch sein (nicht-uniform!)



Gute und schlechte Nachricht...

Die schlechte zuerst...

Satz (ohne Beweis)Die Bestimmung einer energieoptimalen Reichweitenzuordnung istNP-schwer.

...und jetzt die gute:

SatzIst T ein minimaler Spannbaum in G fur w(u, v) = d(u, v)α, dannapproximiert

RAT (u) := maxu,v∈T

d(u, v)

eine optimale Losung bis auf einen Faktor 2.



Gute und schlechte Nachricht...

Die schlechte zuerst...

Satz (ohne Beweis)Die Bestimmung einer energieoptimalen Reichweitenzuordnung istNP-schwer.

...und jetzt die gute:



d(u, v)




Beweis, Teil I

LemmaSei T ein MST und RA eine optimale Losung fur die energieoptimaleReichweitenzuordnung. Es gilt∑

v∈V

RA(v)α >∑

u,v∈T

d(u, v)α .

Gewicht eines MSTs ist untere Schranke fur optimale LosungBeweis:

Betrachte gerichteten Graphen GRAwahle bel. Knoten u und zu u gerichteten Baum TRA in GRA.Fur jede Kante in (u, v) ∈ TRA ist RA(u) ≥ d(u, v).∑

v∈V RA(v)α >∑

(u,v)∈TRAd(u, v)α ≥

∑u,v∈T d(u, v)α

(ungerichtet ist TRA ein Spannbaum)



Beweis, Teil II

LemmaSei T ein (beliebiger) Baum in G. Dann ist∑

v∈V

RAT (u)α ≤ 2∑

u,v∈T

d(u, v)α

Erinnerung: RAT (u) = maxu,v∈T d(u, v)Beweis:

fur jedes v ∈ V ist

RAT (v)α =(

maxu,v∈T

d(u, v))α

= maxu,v∈T

d(u, v)α ≤∑

u,v∈T

d(u, v)α

⇒∑

v∈V RAT (v)α ≤∑

v∈V ,u,v∈T d(u, v)α = 2∑

u,v∈T d(u, v)α



Beweis (Zusammenbau)



d(u, v)


Aus Teil I:∑

v∈V RA(v)α >∑

u,v∈T d(u, v)α

Aus Teil II:∑

v∈V RAT (u)α ≤ 2∑

u,v∈T d(u, v)α

⇒ ∑v∈V

RAT (u)α < 2∑v∈V

RA(v)α



Uberblick






TK durch Auswahl von aktiven Links

Topologiekontrolle durch Beschrankung aufKommunikationsteilgraphen G′

Gegeben einen Maxpower-Graph, was spricht dafur bestimmteKanten zu ignorieren? Was spricht dagegen?



”Neutrale Anforderungen“

SymmetrieVoraussetzung fur viele ProtokolleEinfach herzustellen?

Lokale DefinitionVerteilte Berechnungschnelle Anpassung bei Mobilitat



”Neutrale Anforderungen“

SymmetrieVoraussetzung fur viele ProtokolleEinfach herzustellen?

Lokale DefinitionVerteilte Berechnungschnelle Anpassung bei Mobilitat



Grunde fur Einschrankungen

PlanaritatVereinfacht Routing

Geringer KnotengradSenkt Overheaddurchschnittlich oder im Maximum



Grunde fur Einschrankungen

PlanaritatVereinfacht Routing

Geringer KnotengradSenkt Overheaddurchschnittlich oder im Maximum



Grunde gegen Einschrankungen

1

1

11

1

1

21

= 2

0.5

0.8

0.45 0.35

0.450.9

1.250.9

= 1.39

0.25

0.64

0.20250.1125

0.20250.81

0.51750.5175

= 1

Erhalt von ZusammenhangWege konnen sich verlangern

DefinitionDer Spannfaktor eines Teilgraphen G′ istmaximale Verhaltnis der Langen derkurzesten Wege zwischen zwei Knotena,b in G′ und G.

Lange eines Pfades P dabeiAnzahl der Kanten

∑P 1

Euklidische Lange∑

P d(u, v)Kosten (Energie)

∑P d(u, v)α

Nachbarn in G zu betrachten reicht



Grunde gegen Einschrankungen

1

1

11

1

1

21

= 2

0.5

0.8

0.45 0.35

0.450.9

1.250.9

= 1.39

0.25

0.64

0.20250.1125

0.20250.81

0.51750.5175

= 1

Erhalt von ZusammenhangWege konnen sich verlangern

DefinitionDer Spannfaktor eines Teilgraphen G′ istmaximale Verhaltnis der Langen derkurzesten Wege zwischen zwei Knotena,b in G′ und G.

Lange eines Pfades P dabeiAnzahl der Kanten

∑P 1

Euklidische Lange∑

P d(u, v)Kosten (Energie)

∑P d(u, v)α

Nachbarn in G zu betrachten reicht



Erinnerung: Gabriel Graph

Gabriel GraphEine Kante ist im GG gdw. der Umkreis derKante keine weiteren Knoten enthalt.

GG von UDG:einfach lokal zu entscheidenplanar, zshg., Durchschnittsgrad?Maximalgrad n − 1! (Warum?)Entfernungsspannfaktor O(

√n) (o.B.)

Energiespannfaktor 1! (fur α ≥ 2)



Energiespannfaktor GG-Einschrankung

SatzSchrankt man einen zusammenhangenden UDG (V ,E) auf Kantendes GG ein, bleiben (fur α ≥ 2) alle energieoptimalen Pfade erhalten.

Beweis:Annahme: Es gibt u, v ∈ E , so dass gunstigster Pfad wegfalltwahle solches Paar mit minimalem Abstandgunstigster Pfad muss direkte Verbindung gewesen sein

⇒ u, v ist weggefallen wegen eines Knotens im Umkreisdann war die direkte Verbindung nicht der gunstigster Weg(α ≥ 2!)



Delaunay-Triangulierung

Delaunay-TriangulierungEin Dreieck ist in der DT gdw. der Umkreiskeine weiteren Knoten enthalt.

DT von UDG:nicht lokal konstruierbarplanar und trianguliert (ohne Beweis)

⇒ Durchschnittsgrad konstantGG ist Teilgraph von DT (o.B.)Entfernungsspannfaktor O(1) (o.B.)



Relative-Neighborhood-Graphen

Relative-Neighborhood-GraphEine Kante u, v ist im RNG gdw. beideKnoten keinen gemeinsamen, naherenNachbarn haben.

RNG von UDG:einfach lokal zu entscheidenMaximalgrad 6 (mit Tie-Breaking)Entfernungs- undEnergiespannfaktor n − 1RNG ist Teilgraph von GG



Euklidischer MST

EMSTMST mit euklidischen AbstandenzusammenhangendTeilgraph des RNG:Kanten, die nicht im RNG sind, sindauch nicht im MST



Geometrische Graphen, Inklusionen

MST RNG GG DT

planar planar planar planarzshg zshg zshg zshg

DurGrad 2 O(1) O(1) 6MaxGrad 6 6 n − 1 n − 1Entf. n-1 n-1 O(

√n) O(1)

Energ. n-1 n-1 1 1lokal — X X —



(Noch mehr Graphen: Yao-Graph)

Yao-GraphJeder Knoten partitioniert Nachbarn in k Segmenteund wahlt dichtesten in jedem Segment.Kantenrichtungen werden dann symmetrischerganzt.

lokal konstruierbarMaximalgrad n − 1Konstante Spannfaktoren



Lokale Protokolle

Braucht man unbedingt Knotenpositionen, um von diesenUberlegungen zu profitieren?

Was, wenn Knoten nur irgendein symmetrisches Maß fur dieGute ihrer Nachbarn kennen?

Entfernung (dicht=gut)Energie (billig=gut)Verbindungsqualitat (gut=gut)

Was, wenn die Kosten nicht nur von den Positionen abhangen,sondern es Hindernisse gibt?

MST gehen immer noch (aber nicht schnell), was geht sonst?



XTC: RNG ohne Geometrie

XTC-Algorithmus1 Jeder Knoten erstellt ein Ranking seiner Nachbarn nach Gute2 Knoten teilen ihre Rankings den Nachbarn mit3 ein Link u, v wird ignoriert, wenn es einen Knoten w gibt, den

u besser rankt als v und umgekehrt.

fur euklidische Abstande: Teilgraph des RNG⇒ planar, Maximalgrad,...

Exakt RNG, falls keine Ties

symmetrisch (per Definition)zusammenhangendsehr einfach umzusetzen



Uberblick






Interferenz vs. Zusammenhang

Erinnerung InterferenzWenn Knoten senden, dann storen sie den Empfang anderer Knoten.Ziel von Topologiekontrolle kann auch sein, interferenzminimaleTeilgraphen zu identifizieren.

8

Wie viele Knoten ”stort“ eineKante?

2

Wieviele Senderadienuberdecken einen Knoten?

Welcher symmetrische, zusammenhangende Graph minimiert diemaximale Interferenz?



Ein boses Beispiel

Alle bisherigen Topologien enthalten Verbindungen zu dichtestenNachbarn, wie schlecht kann das sein?

i i+ 1

2i



Ein boses Beispiel


Ω(n)



Ein boses Beispiel


Ω(n)



Ein boses Beispiel


O(1)



Place your bets!

Gesucht: Ungerichteter zusammenhangender Graph auf einer Mengevon Punkten, der die maximale Interferenz / Summe der Interferenzminimiert. Wo ist das leicht, wo ist das NP-schwer? Bei Kanten- oderKnoteninterferenz?

8

Wie viele Knoten ”stort“ eineKante?

2

Wieviele Senderadienuberdecken einen Knoten?



Place your bets!

Gesucht: Ungerichteter zusammenhangender Graph auf einer Mengevon Punkten, der die maximale Interferenz / Summe der Interferenzminimiert. Wo ist das leicht, wo ist das NP-schwer? Bei Kanten- oderKnoteninterferenz?

8

Wie viele Knoten ”stort“ eineKante?Leicht! MST mit Interferenzals Kantengewicht!

2

Wieviele Senderadienuberdecken einen Knoten?NP-schwer! (ohne Beweis)



Zusammenfassung

Topologiekontrolle ist Kompromiss widerspruchlicher Zielemanchmal sind die Ziele noch nicht einmal klar formuliert!

Topologiekontrolle zum EnergiesparenWahl minimaler Sendeleistungen, ohne Zusammenhang zuverlieren

TK durch lokale Entscheidungen gegen unnotige LinksSpanner-Eigenschaften vs. Grad, Planaritat, ..Schnitt geometrischer Graphen mit MaxPower-GraphRNG/XTC: auch ohne Geometrie noch hilfreich

Topologiekontrolle zur Minimierung der Interferenzselbst bei einfachen Modellen uberraschend schwer



Literatur

1 Paolo Santi: Topology Control in Wireless Ad Hoc and SensorNetworks, Wiley, 2005

2 L. Kirouses, E. Kranakis, D. Krizanc, A. Pelc: Power consumptionin packet radio networks. In: Theoretical Computer Science 243,289–305, 2000

3 R. Wattenhofer, A. Zollinger: XTC: A practical topology controlalgorithm for ad-hoc networks. In: 18th IEEE InternationalParallel and Distributed Processing Symposium (IPDPS’04),IEEE Press, 2004

4 M. Burhart, P. von Rickenbach, R. Wattenhofer, A. Zollinger:Does Topology Control Reduce Interference?. In Proceedings ofThe 5th ACM International Symposium on Mobile Ad HocNetworking and Computing (MobiHoc ’04)



Documents

Algorithmen fur¨ Ad-hoc- und Sensornetze · eine optimale Losung bis auf einen Faktor 2.¨ Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze¨ VL 04 – Topologiekontrolle