Embed Size (px)
Citation preview
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: [email protected] 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
