Algorithmen für Ad-hoc- und Sensornetze - Übung 2 Greedy Routing · Besprechung: Leader Election...

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

Algorithmen fur Ad-hoc- und SensornetzeUbung 2 – Greedy Routing

Fabian Fuchs | 05. November 2015 (Version 1)

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

Uberblick

Organisatorisches

Implementierung der Algorithmen

Besprechung: Leader Election in allgemeinen Graphen

Greedy Routing

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (2/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Organisatorisches

UbungEs sollen ausgewahlte Algorithmen im Netzwerksimulator Sinalgoimplementiert werden

Von den folgenden Ubungsblattern soll mindestens eins in derUbung (teilweise) vorgestellt werden um zur Prufung zugelassenzu werden.

Ubungsblatter auch digital unter: http://i11www.iti.kit.edu/teaching/winter2015/sensornetze/index

Bei Fragen: Email oder SprechstundeDienstag: 13:00-14:00 (kurze Anmeldung erwunscht!)Oder nach Vereinbarung: fabian.fuchs@kit.eduRaum 317, Gebaude 50.34

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (3/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Uberblick

Organisatorisches

Implementierung der Algorithmen

Besprechung: Leader Election in allgemeinen Graphen

Greedy Routing

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (4/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Verwendete Frameworks

Sinalgo: Simulator fur Netzwerkalgorithmen in(Drahtlos-)Netzwerken

Implementiert in Java, dadurch plattformubergreifend nutzbarModularer Aufbau ermoglicht parallele ProjekteNachteil: Implementierung grundlegend andersals auf Sensorknoten

Arduino Uno: Hands-on SensorknotenKomplexere (bzw. oftmals ungewohnte) Umgebung, daher mehrFocus auf Kennenlernen der Plattform, weniger auf Algorithmen.Implementierung in leicht erweitertem C

Aufteilung: 5 Blatter zu Sinalgo, ein Blatt zu Arduino

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (5/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Verwendete Frameworks

Sinalgo: Simulator fur Netzwerkalgorithmen in(Drahtlos-)Netzwerken

Implementiert in Java, dadurch plattformubergreifend nutzbarModularer Aufbau ermoglicht parallele ProjekteNachteil: Implementierung grundlegend andersals auf Sensorknoten

Arduino Uno: Hands-on SensorknotenKomplexere (bzw. oftmals ungewohnte) Umgebung, daher mehrFocus auf Kennenlernen der Plattform, weniger auf Algorithmen.Implementierung in leicht erweitertem C

Aufteilung: 5 Blatter zu Sinalgo, ein Blatt zu Arduino

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (5/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Verwendete Frameworks

Sinalgo: Simulator fur Netzwerkalgorithmen in(Drahtlos-)Netzwerken

Implementiert in Java, dadurch plattformubergreifend nutzbarModularer Aufbau ermoglicht parallele ProjekteNachteil: Implementierung grundlegend andersals auf Sensorknoten

Arduino Uno: Hands-on SensorknotenKomplexere (bzw. oftmals ungewohnte) Umgebung, daher mehrFocus auf Kennenlernen der Plattform, weniger auf Algorithmen.Implementierung in leicht erweitertem C

Aufteilung: 5 Blatter zu Sinalgo, ein Blatt zu Arduino

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (5/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Uberblick

Organisatorisches

Implementierung der Algorithmen

Besprechung: Leader Election in allgemeinen Graphen

Greedy Routing

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (6/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Leader ElectionLeader Election, Knoten pi kennt IDi

sende IDi an alle Nachbarnsetze ID+ ← IDi und parent← ⊥wenn IDs empfangen wurden dann

wahle maximale empfangene ID und zugehorigen Sender swenn ID > ID+ dann

setze ID+ ← ID und parent← ssende Nachricht ”new follower“ an parentsende ID+ an restliche Nachbarn

wenn ”new follower“ empfangen wurde und parent 6= ⊥ dannsende Nachricht ”new follower“ an parenta

aaußer in selber Runde schon geschehen

Ein Knoten mit parent = ⊥ darf sich zum Leader erklaren nachdemzwei Runden keine hohere ID und keine new follower-Nachricht kam.

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (7/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Uberblick

Organisatorisches

Implementierung der Algorithmen

Besprechung: Leader Election in allgemeinen Graphen

Greedy Routing

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (8/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Greedy Routing

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (9/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Geographisches Routing: Problem

Gegeben: Eingebetteter Unit-Disk-Graph G = (V ,E), zwei Knotens, t ∈ V .

Gesucht: Positionsbewusste Routingstrategie, um ein Paket, dasdie Position p(t) enthalt, von s nach t zu bringen.

Es ist erlaubt, ”etwas“ Routinginformationen im Paket zuspeichern (neben der Zielposition)Hier: Anstatt Positionsbewusstsein anzunehmen werden initialdie Positionen unter Nachbarn ausgetauscht.

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (10/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Greedy Routing

Greedy RoutingLeite Paket an den Nachbarn, derdem Ziel am nachsten ist.

Was, wenn es nicht weitergeht????

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (11/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Greedy Routing

Greedy RoutingLeite Paket an den Nachbarn, derdem Ziel am nachsten ist.

Was, wenn es nicht weitergeht?

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (11/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Greedy Routing

Greedy RoutingLeite Paket an den Nachbarn, derdem Ziel am nachsten ist.

Was, wenn es nicht weitergeht?

???

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (11/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Greedy Routing

Greedy RoutingKnoten kennen ihre eigenen Geokoordinaten sowieZielkoordinaten fur PaketePakete enthalten mindestens die ZielkoordinatenPakete werden immer an den “besten” Nachbarn weitergeleitet

ModellSynchrone Runden, synchroner StartPro Runde kann jeder Knoten eine (potentiell unterschiedliche)Nachricht an jeden Nachbarn sendenVerteilung: Random, Grid, Manuell, ...Weiteres: UGD, keine Mobilitat, keine Interference, reliabledelivery, . . .

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (12/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Abschluss

Wir hatten heute:Nachtrag Location Service: MLS (VL 03)Wdh: Organisatorisches zur UbungBesprechung Leader ElectionGreedy Routing

Weitere Fragen?

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (13/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik

Links zur Ubung

Ubungsblatt auf VL-Homepage:http://i11www.iti.uni-karlsruhe.de/teaching/winter2015/sensornetze/index

Sinalgo Tutorial: http://disco.ethz.ch/projects/sinalgo/tutorial/Documentation.html

Sinalgo Framework: VL-Homepage oder Sinalgo Tutorial SeiteGrundgerust fur Leader Election Projekt: VL-Homepage

Tipp: Wer schon mit Arduino rumspielen mochte:https://123d.circuits.io/

Fabian Fuchs – Algorithmen fur Ad-hoc- und Sensornetze

Ubung 2 – Greedy Routing (14/14)Institut fur Theoretische InformatikLehrstuhl Algorithmik