Post on 18-Sep-2018
transcript
INSTITUT FUR THEORETISCHE INFORMATIK - LEHRSTUHL FUR ALGORITHMIK (PROF. WAGNER)
Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering
Markus Volker | 06. Juni 2012 (Version 2)
KIT – Universitat des Landes Baden-Wurttemberg undnationales Großforschungszentrum in der Helmholtz-Gemeinschaft www.kit.edu
Uberblick
Data Gathering (kurze Einfuhrung)Ein Name, viele Probleme
Aggregation von Funktionen auf SensorwertenAnfragen und FunktionsklassenRandomisierung und Schranken
Scheduling von Data Gathering TreesEinsammeln von großen DatenmengenEnergiesparen durch Koordination des Funkkanals
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (2/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Data Gathering
”Einsammeln von Daten (in einer Senke)“ kann heißen
EreignismeldungenKnoten mit kritischen Werten teilen das mitoft nur einzelne Pakete
) Geringer Verkehr, Optimierungsziel z. B. geringe Latenz
Antworten auf Anfragen) Verkehr stark abhangig von Art/Frequenz der Anfrage
Permanenter Fluss von Datenjeder Knoten schickt regelmaßig Sensorwerte Richtung Senke
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (3/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Optimierungsebenen
Topologiekontrolle / Power ControlMSTs, Shortest-Path-Trees, etc.Auswahl einer geschickten Topologie kann jeweiligen Zweckunterstutzen, Zeit / Energie sparen usw
Datenaggregationbei vielen Anfragen mussen nicht alle Sensordaten zur Senke, umeine Information bereitzustellen
Scheduling von Ubertragungen und SchlafzyklenAbsprache spart Energie: Kein standiges Mithoren von fremdenNachrichten!
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (4/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Uberblick
Data Gathering (kurze Einfuhrung)Ein Name, viele Probleme
Aggregation von Funktionen auf SensorwertenAnfragen und FunktionsklassenRandomisierung und Schranken
Scheduling von Data Gathering TreesEinsammeln von großen DatenmengenEnergiesparen durch Koordination des Funkkanals
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (5/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Anfragen an ein Netzwerk
Anfragen an ein Sensornetz ahneln oft denen an Datenbanken:
”Gib mir die Koordinaten der zehn Knoten mit der hochstenTemperatur“
TinyDB und ahnliche Services unterstutzen Anfragesprachen mitSQL-ahnlicher Syntax.
typischerweise Fluten der Anfrage, Aggregation der Antwortentlang eines Baumes
beliebig komplexe Anfragen, aber einige Primitive
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (6/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Aggregationsmodell
Voraussetzungenjeder Knoten enthalt genau einen Sensorwert
(nur zur Vereinfachung)ein zur Senke gerichteter Spannbaum ist gegeben
Durchmesser Djede Nachricht darf nur 1-2 Elemente enthalten
(allgemeiner: O(1) Elemente)
Anfragefunktionen sind unabhangig davon, welcher Knotenwelches Element halt
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (7/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Gegeben ein (Anfrage-)Baum, in dem jeder Knoten genau einenSensorwert halt, was ist die einfachste Anfrage, die man sichvorstellen kann?
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (8/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Distributive Funktionen
Eine (berechenbare) Funktion f auf einer Menge M von Elementen(das sind die Sensorwerte!) heißt distributiv, wenn es ausreicht, wennf (M1), f (M2), . . . fur eine Partition M1,M2, . . . von M bekannt ist, umf (M) zu berechnena.
aPartition: M ist die disjunkte Vereinigung der Mi
Beispiele fur distributive Funktionen:Maximum: f (M) = maxi f (Mi) (Minimum genauso)Summe: f (M) =
Pi f (Mi)
Anzahl der Elemente mit bestimmter Eigenschaft: f (M) =P
i f (Mi)
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (9/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Aggregation Distributiver Funktionen
Distributive Funktionen lassen sich mit ⇥(n) Nachrichten in ⇥(D)
Schritten verteilt berechnen.
Klassischer Flooding-Echo-AnsatzSenke schickt Anfrage, jeder Knoten gibt die Anfrage an Kinderweiter.Blatter antworten mit FunktionswertInnere Knoten aggregieren ihren Funktionswert und den ihrerTeilbaume
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (10/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Gegeben ein (Anfrage-)Baum, in dem jeder Knoten genau einenSensorwert halt, was ist eine einfache nicht-distributive Anfrage?
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (11/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Algebraische Funktionen
Eine (berechenbare) Funktion f auf einer Menge M von Elementen(das sind die Sensorwerte!) heißt algebraisch, wenn es ausreicht, dieFunktionswerte einer konstanten Anzahl distributiver Funktionen furM zu kennen.
Haufigstes Beispiel: Durchschnittlicher WertSumme / Anzahl aller Elemente
k -großtes Element fur festes kdistributive Funktionen hangen voneinander ab!
Aggregation mit ⇥(n) Nachrichten in ⇥(D) Zeit.
gibt es was Schlimmeres?
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (12/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Holistische Funktionen
Berechenbare Funktionen auf einer Menge M von Elementen, dienicht algebraisch sind, werden holistisch genannt.
Median, k -großtes Elementz.B. in ”Durchschnitt der 10% großten Werte“
Ist das wirklich schwerer? Vorschlage?
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (13/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Aufwarmubung
Wie wahle ich in ⇥(D) Schritten gleichverteilt ein zufalliges Elementaus?
Berechne Anzahl der Elemente unterjedem Knoten
Flute Anfrage nach Zufallselement,Knoten v mit Teilbaumgroßen n1, . . . , nk
gibt mit Wahrscheinlichkeit1/(1 +
Pki=1 ni) seinen Wert zuruck
leitet die Anfrage mit W’keitnj/(1 +
Pki=1 ni) in Teilbaum j .
n1 n2 n3
v
In O(D) Schritten kann ich auch ein zufalliges Element aus allenElementen in einem Intervall (a, b) ziehen! (Klar?)
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (14/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Ein randomisierter Algorithmus
Mit dem Ziehen von zufalligen Elementen kann man eine binareSuche nachbauen, um den Median zu finden (k-großtes Elementgeht analog).
1 setze a = �1, b = 12 bestimme zufalliges Element x mit Wert (a, b)3 bestimme, wie viele Elemente großer als x sind
mehr als die Halfte der Elemente: a xweniger als die Halfte der Elemente: b xgenau die Halfte: x ist Median
4 gehe zu 2 (Schritte 2,3 sind eine Runde!)
Jede Runde dauert nur ⇥(D) Schritte!) O(D log n) erwartete Laufzeit.
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (15/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Pipelining und Analyse
In ⇥(D) Schritten/Runde kann ich ja noch viel mehr machen!
suche parallel nach t = D zufalligen Elementenletztes Element kommt nach O(D) Runden an, da t 2 O(D)
Anfragen zum Zahlen der Elemente in sich ergebendenIntervallen werden in aufeinanderfolgenden Schritten geschickt) parallele Berechnung in O(D) Schrittenjede Runde reduziert die Anzahl der Elemente in (a, b) erwartetauf weniger als 1/D-tel!
D Zufallswerte
a
b
Median (nicht unbedingt in der Mitte von (a, b)!)
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (16/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Pipelining und Analyse
In ⇥(D) Schritten/Runde kann ich ja noch viel mehr machen!
suche parallel nach t = D zufalligen Elementenletztes Element kommt nach O(D) Runden an, da t 2 O(D)
Anfragen zum Zahlen der Elemente in sich ergebendenIntervallen werden in aufeinanderfolgenden Schritten geschickt) parallele Berechnung in O(D) Schrittenjede Runde reduziert die Anzahl der Elemente in (a, b) erwartetauf weniger als 1/D-tel!
Satz (ohne so richtig formalen Beweis)Der randomisierte Algorithmus benotigt mit hoher Wahrscheinlichkeitnur O(logD n) Runden, also O(D logD n) Schritte und O(D n logD n)Nachrichten.
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (16/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Was ist das wert?
Satz (ohne so richtig formalen Beweis)Der randomisierte Algorithmus benotigt mit hoher Wahrscheinlichkeitnur O(logD n) Runden, also O(D logD n) Schritte und O(D n logD n)Nachrichten.
Fur D 2 ⌦(nd) fur ein 0 < d 1 ist
logD n logcnd n =
log2 nlog2(cnd
)
=
log2 nlog2 c + d log2 n
1/d
) außer bei fast konstantem Durchmesser in O(D) Schritten undO(D n) Nachrichten!
das ist offensichtlich asymptotisch zeitoptimalwie sieht es mit dem allgemeinen Fall aus?
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (17/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Untere Schranke
BemerkungBester bekannter deterministischer Algorithmus hat LaufzeitO(D log2
D n).
Randomisierter Algorithmus ist echt besser!
Satz (beweisen wir gleich!)Jeder deterministische Algorithmus benotigt zur Bestimmung desMedians im worst-case ⌦(D logD n) Schritte.
gilt auch fur randomisierte Algorithmenist noch schwerer zu analysieren
der randomisierte Algorithmus ist also auch allgemein optimal!
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (18/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Eine erste Naherung
LemmaZwei Knoten, die jeweils N Elemente halten und pro Runde BElemente und beliebige Zusatzinformationen austauschen durfen,benotigen im worst-case ⌦(log2B N) Runden, um den gemeinsamenMedian zu ermitteln.
Nimm 2N beliebige Elemente, N = 2b
wurfle b Zufallswerte Xi 2 {0, 1}Wenn X0 = 1, teile N/2 großteElemente zu u und N/2 kleinste zu v ,sonst umgekehrt!Wenn X1 = 1, teile N/4 nachstgroßteElemente zu u, N/4 nachstkleinsteElemente zu v , sonst umgekehrt, usw.
uv
0 2N
sortierte Werte
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (19/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Eine erste Naherung
LemmaZwei Knoten, die jeweils N Elemente halten und pro Runde BElemente und beliebige Zusatzinformationen austauschen durfen,benotigen im worst-case ⌦(log2B N) Runden, um den gemeinsamenMedian zu ermitteln.
Nimm 2N beliebige Elemente, N = 2b
wurfle b Zufallswerte Xi 2 {0, 1}Wenn X0 = 1, teile N/2 großteElemente zu u und N/2 kleinste zu v ,sonst umgekehrt!Wenn X1 = 1, teile N/4 nachstgroßteElemente zu u, N/4 nachstkleinsteElemente zu v , sonst umgekehrt, usw.
uv
0 2N
X0 = 1
sortierte Werte
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (19/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Eine erste Naherung
LemmaZwei Knoten, die jeweils N Elemente halten und pro Runde BElemente und beliebige Zusatzinformationen austauschen durfen,benotigen im worst-case ⌦(log2B N) Runden, um den gemeinsamenMedian zu ermitteln.
Nimm 2N beliebige Elemente, N = 2b
wurfle b Zufallswerte Xi 2 {0, 1}Wenn X0 = 1, teile N/2 großteElemente zu u und N/2 kleinste zu v ,sonst umgekehrt!Wenn X1 = 1, teile N/4 nachstgroßteElemente zu u, N/4 nachstkleinsteElemente zu v , sonst umgekehrt, usw.
uv
0 2N
sortierte Werte
X1 = 0
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (19/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Zwei kleine Beobachtungen..
Beobachtung IWenn ein Knoten den Median kennt, kennt er alle Xi !
Zahle die Elemente, die in u großer sind.N/2 oder mehr) X0 = 1...
Beobachtung IIDie Zusatzinformationen konnen sich nur aus den Vergleichenzwischen Elementen ergeben, die einem Knoten bekannt sind.
Vergleiche zwischen us Elementen und Elementen, die v schongeschickt hatVergleiche zwischen vs Elementen und Elementen, die u schongeschickt hat
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (20/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
..und eine große Erkenntnis
LemmaZwei Knoten, die jeweils N Elemente halten und pro Runde BElemente und beliebige Zusatzinformationen austauschen durfen,benotigen im worst-case ⌦(log2B N) Runden, um den gemeinsamenMedian zu ermitteln.
Beweisskizze (nur fur B = 1)betrachte ”abwechselndes“ Senden von einzelnen Elementenegal, welches Element u an v zuerst schickt, im schlimmsten Fallenthalt es keine Information uber X0 hinaus!
z.B.: als erstes schickt u Element aus seiner kleineren Halfte,schlecht fur X0 = 0danach gehts weiter fur X1
) mindestens log2 N Elemente mussen ausgetauscht werden
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (21/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Zuruck zur unteren Schranke
Lemma (im Prinzip ist das unser Satz)Fur jedes D � 3 gibt es eine Instanz, in der die Bestimmung desMedians ⌦(D logD n) Schritte benotigt.
wir betrachten folgende Instanz mit D 2 ⇥(n)
u1 v1D� 3
v2u2
u v
> n/4 > n/4)
D� 3
u v
die D � 3 Knoten enthalten keine Elemente (das macht es nurleichter!)in Runde 1 kann nichts sinnvolleres passieren, als dass u und vdie Elemente von allen Satelliten erhalten
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (22/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Ein letzter Schritt
Lemma (im Prinzip ist das unser Satz)Fur jedes D � 3 gibt es eine Instanz, in der die Bestimmung desMedians ⌦(D logD n) Schritte benotigt.
Wir haben das auf eine Instanz zuruckgefuhrt, in der zwei Knotenmind. n/4 Elemente halten und durch einen Pfad der Lange D � 2getrennt sind.
Anschnallen! Wir nehmen an, dass u und v in Runden zu jeD � 2 Schritten D � 2 Elemente an alle anderen Knoten schickenkonnen.
Daraus konnten u und v das Verhalten der Knoten auf dem Pfadsogar rekonstruieren!
) Die Annahme kann das Problem nur vereinfachen!
Schlussfolgerung?
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (23/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
und eine letzte Schlussfolgerung
Wir machen es uns fur diese Instanz nur leichter,u1 v1D� 3
v2u2
u v
> n/4 > n/4
wenn u und v alle Werte der Satelliten kennen und wenn manannimmt, dass die beiden sich in Runden mit je D � 2 Schrittengenau D � 2 Elemente zuschicken konnen.
Wir wissen, dass zwei Knoten mit je N = n/4 Elementen, diesich pro Runde B = D � 2 Elemente schicken konnen,
⌦(log2D�4 n/4) 2 ⌦(logD n)
Runden benotigen.unsere Runden hier dauern D � 2 Schrittedas beweist die untere Schranke von ⌦(D logD n)!
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (24/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Uberblick
Data Gathering (kurze Einfuhrung)Ein Name, viele Probleme
Aggregation von Funktionen auf SensorwertenAnfragen und FunktionsklassenRandomisierung und Schranken
Scheduling von Data Gathering TreesEinsammeln von großen DatenmengenEnergiesparen durch Koordination des Funkkanals
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (25/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Einsammeln von Daten, Szenario
Sensorknoten sammeln Datenviele Pakete je Knoten,
P= N
Bei Bedarf wird eine Anfrage geflutetspannt Kurzeste-Wege-Baum aufDaten sollen schnell zur Senke fließen
Einschrankungen:Knoten haben keinen/wenig zusatzlichenSpeicher (Rohdaten oft extern gespeichert)Ubertragungen konnen nicht beliebigparallel stattfinden, ohne sich zu storen(Interferenzmodell)
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (26/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Einsammeln von Daten, Szenario
Sensorknoten sammeln Datenviele Pakete je Knoten,
P= N
Bei Bedarf wird eine Anfrage geflutetspannt Kurzeste-Wege-Baum aufDaten sollen schnell zur Senke fließen
Einschrankungen:Knoten haben keinen/wenig zusatzlichenSpeicher (Rohdaten oft extern gespeichert)Ubertragungen konnen nicht beliebigparallel stattfinden, ohne sich zu storen(Interferenzmodell)
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (26/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Einsammeln von Daten, Szenario
Sensorknoten sammeln Datenviele Pakete je Knoten,
P= N
Bei Bedarf wird eine Anfrage geflutetspannt Kurzeste-Wege-Baum aufDaten sollen schnell zur Senke fließen
Einschrankungen:Knoten haben keinen/wenig zusatzlichenSpeicher (Rohdaten oft extern gespeichert)Ubertragungen konnen nicht beliebigparallel stattfinden, ohne sich zu storen(Interferenzmodell)
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (26/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Einsammeln von Daten, Szenario
Sensorknoten sammeln Datenviele Pakete je Knoten,
P= N
Bei Bedarf wird eine Anfrage geflutetspannt Kurzeste-Wege-Baum aufDaten sollen schnell zur Senke fließen
Einschrankungen:Knoten haben keinen/wenig zusatzlichenSpeicher (Rohdaten oft extern gespeichert)Ubertragungen konnen nicht beliebigparallel stattfinden, ohne sich zu storen(Interferenzmodell)
r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (26/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Einsammeln von Daten, Szenario
Sensorknoten sammeln Datenviele Pakete je Knoten,
P= N
Bei Bedarf wird eine Anfrage geflutetspannt Kurzeste-Wege-Baum aufDaten sollen schnell zur Senke fließen
Einschrankungen:Knoten haben keinen/wenig zusatzlichenSpeicher (Rohdaten oft extern gespeichert)Ubertragungen konnen nicht beliebigparallel stattfinden, ohne sich zu storen(Interferenzmodell)
r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (26/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Einsammeln von Daten, Szenario
Sensorknoten sammeln Datenviele Pakete je Knoten,
P= N
Bei Bedarf wird eine Anfrage geflutetspannt Kurzeste-Wege-Baum aufDaten sollen schnell zur Senke fließen
Einschrankungen:Knoten haben keinen/wenig zusatzlichenSpeicher (Rohdaten oft extern gespeichert)Ubertragungen konnen nicht beliebigparallel stattfinden, ohne sich zu storen(Interferenzmodell)
r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (26/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Einsammeln von Daten, Szenario
Sensorknoten sammeln Datenviele Pakete je Knoten,
P= N
Bei Bedarf wird eine Anfrage geflutetspannt Kurzeste-Wege-Baum aufDaten sollen schnell zur Senke fließen
Einschrankungen:Knoten haben keinen/wenig zusatzlichenSpeicher (Rohdaten oft extern gespeichert)Ubertragungen konnen nicht beliebigparallel stattfinden, ohne sich zu storen(Interferenzmodell)
r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (26/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Motivation Scheduling
Die meiste Energie in Sensornetzen geht nicht verloren, weil so vielDaten zu ubertragen sind, sondern weil Knoten zu oft wach sind undden Kanal uberwachen!
Feste Schedules verhindern das!Jeder Knoten weiß, wann er horen und wann er senden mussHenne-Ei-Problem: Wie verabredet man einen Schedule?
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (27/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schedule-Set-Up
ModellIn einem Anfragebaum darf jeder Knoteneinmalig ein Paket mit O(log N) Bits an jedenNachbarn schicken, um sich auf einen Schedulezu einigen.
Einzig sinnvolles Schema:Convergecast zur Senke hinBroadcast von der Senke weg r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (28/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Schedule-Set-Up
ModellIn einem Anfragebaum darf jeder Knoteneinmalig ein Paket mit O(log N) Bits an jedenNachbarn schicken, um sich auf einen Schedulezu einigen.
Einzig sinnvolles Schema:Convergecast zur Senke hinBroadcast von der Senke weg r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (28/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Erinnerung / Wiedereinstieg
Knoten haben Paketeggf. viele pro Knoten,
P= N
Kurzeste-Wege-Baum (in Hops) gegeben
gesucht: Zeitplan, wer wann sendet bzw.weiterleitet
leicht zu verabreden (das werden wir nichtzeigen)kein Knoten soll mehr als ein Paket puffernmussenparallele Ubertragungen durfen sich nichtstoren
r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (29/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
k -Hop-Interferenz
k -Hop-InterferenzIm Modell der k -Hop-Interferenz kann einKnoten eine Nachricht eines Nachbarn genaudann empfangen, wenn der Nachbar der einzigeaktive Sender im Radius von k Hops ist.
Wir suchen nur Schedules, die in diesemModell kollisionsfrei sind!
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (30/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Baume mit k -lagenbeschrankterInterferenz
k -lagenbeschrankte InterferenzEin Anfragebaum hat k -lagenbeschrankteInterferenz, wenn ein Knoten u die Nachrichteines Kindes immer empfangen kann, wenn vder einzige aktive Sender in den Lagenhu � k . . . hu + k ist.
Kurzeste-Wege-Baume haben beik -Hop-Interferenz k -lagenbeschrankteInterferenz!Jeder Sender, der einen Knoten u storenkonnte, hat maximal Abstand k im Graphenund kann dann auch nur eineHohendifferenz von k im Baum haben!
r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (31/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Untere Schranke
LemmaIn jedem gultigen Schedule darf in derb(k + 1)/2c-Nachbarschaft der Senke zu jedemZeitpunkt nur maximal ein aktiver Sender sein.
Beweis:Die Empfanger haben jeweils nur Abstandb(k + 1)/2c � 1 zur Senke.damit haben ”falsche“Sender-Empfanger-Paare Abstand
2 · b(k + 1)/2c � 1 k
) Die wurden sich storen!
r h
b(k+
1)/2
c
k = 3
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (32/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Untere Schranke
LemmaBezeichnet hu die Entfernung von Knoten u zurSenke und pu die Anzahl der Pakete, die u amAnfang enthalt, benotigt jeder gultige SchedulemindestensX
u2V
(pu · min{hu, b(k + 1)/2c})
Zeiteinheiten.Jedes Paket von einem Knoten u in Entfernunghu zur Senke schlagt mit mindestensmin{hu, b(k + 1)/2c} Zeiteinheiten ”zu Buche“, indenen es von einem Knoten in der b(k + 1)/2c-Nachbarschaft der Senke gesendet wird!
r h
b(k+
1)/2
c
k = 3
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (33/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
2-Phasen-Algorithmus
Nur Pakete, die dicht an der Senke sind,schlagen in unterer Schranke mit ihrerEntfernung zu Buche, weit entfernte Paketetrotzdem nur mit b(k + 1)/2c Zeitslots.
Idee!Das konnen wir nachbauen! Wir geben zweiSchedules an, die nacheinander ablaufen.
1 Einsammeln aller weit entfernter Pakete mit
”Pipelining“2 Einsammeln aller Pakete in der
k + 2-Hop-Nachbarschaft der Senke ohneparallele Ubertragungen
r h
b(k+
1)/2
c
k = 3
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (34/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
2-Phasen-Algorithmus
Nur Pakete, die dicht an der Senke sind,schlagen in unterer Schranke mit ihrerEntfernung zu Buche, weit entfernte Paketetrotzdem nur mit b(k + 1)/2c Zeitslots.
Idee!Das konnen wir nachbauen! Wir geben zweiSchedules an, die nacheinander ablaufen.
1 Einsammeln aller weit entfernter Pakete mit
”Pipelining“2 Einsammeln aller Pakete in der
k + 2-Hop-Nachbarschaft der Senke ohneparallele Ubertragungen r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (34/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
2-Phasen-Algorithmus
Nur Pakete, die dicht an der Senke sind,schlagen in unterer Schranke mit ihrerEntfernung zu Buche, weit entfernte Paketetrotzdem nur mit b(k + 1)/2c Zeitslots.
Idee!Das konnen wir nachbauen! Wir geben zweiSchedules an, die nacheinander ablaufen.
1 Einsammeln aller weit entfernter Pakete mit
”Pipelining“2 Einsammeln aller Pakete in der
k + 2-Hop-Nachbarschaft der Senke ohneparallele Ubertragungen r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (34/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitet
Knoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitet
Knoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r
5
5
5
5
5
4 1
1 2
1
7
7
7
7
4 3
4
1 2
3
2
1 1
12
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r
5
5
5
5
4 1
1 2
1
7
7
7
7
4 3
4
1 2
3
2
1 1
0-60 0 + 5N
5
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r
5
5
5
5
4 1
1 2
1
7
7
7
4 3
4
1 2
3
2
1 1
0-60
1 + 5N
0 + 5N
26-561-21
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r
5
5
5
4 1
1 2
1
7
7
4 3
4
1 2
3
2
1 1
0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
3-23
4-24
5-25
6-21 26
7 12-17
13
28-58
29-59
30-45 50-60
31-46
32 37-42
51-61
52-57
38 53
3 + 5N
4 + 5N
0 + 5N
1 + 5N
2 + 5N
3 + 5N
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
3-23
4-24
5-25
6-21 26
7 12-17
13
28-58
29-59
30-45 50-60
31-46
32 37-42
51-61
52-57
38 53
3 + 5N
4 + 5N
0 + 5N
1 + 5N
2 + 5N
3 + 5N
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
3-23
4-24
5-25
6-21 26
7 12-17
13
28-58
29-59
30-45 50-60
31-46
32 37-42
51-61
52-57
38 53
3 + 5N
4 + 5N
0 + 5N
1 + 5N
2 + 5N
3 + 5N
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
3-23
4-24
5-25
6-21 26
7 12-17
13
28-58
29-59
30-45 50-60
31-46
32 37-42
51-61
52-57
38 53
3 + 5N
4 + 5N
0 + 5N
1 + 5N
2 + 5N
3 + 5N
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
3-23
4-24
5-25
6-21 26
7 12-17
13
28-58
29-59
30-45 50-60
31-46
32 37-42
51-61
52-57
38 53
3 + 5N
4 + 5N
0 + 5N
1 + 5N
2 + 5N
3 + 5N
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
3-23
4-24
5-25
6-21 26
7 12-17
13
28-58
29-59
30-45 50-60
31-46
32 37-42
51-61
52-57
38 53
3 + 5N
4 + 5N
0 + 5N
1 + 5N
2 + 5N
3 + 5N
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
3-23
4-24
5-25
6-21 26
7 12-17
13
28-58
29-59
30-45 50-60
31-46
32 37-42
51-61
52-57
38 53
3 + 5N
4 + 5N
0 + 5N
1 + 5N
2 + 5N
3 + 5N
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt
r0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
3-23
4-24
5-25
6-21 26
7 12-17
13
28-58
29-59
30-45 50-60
31-46
32 37-42
51-61
52-57
38 53
3 + 5N
4 + 5N
0 + 5N
1 + 5N
2 + 5N
3 + 5N
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt r0-60
1 + 5N
0 + 5N
26-561-21
2 + 5N2-22 27-57
3-23
4-24
5-25
6-21 26
7 12-17
13
28-58
29-59
30-45 50-60
31-46
32 37-42
51-61
52-57
38 53
3 + 5N
4 + 5N
0 + 5N
1 + 5N
2 + 5N
3 + 5N
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase I - Pipelining entfernter Pakete
Jeder Knoten lernt, wieviele Pakete mit Hoheuber k + 2 ersendet/weiterleitetKnoten senden in einemIntervall alle k + 2 Slots
die Senke sendet“virtuell” in den Slots0, k + 2, . . .ein Knoten, der sendet,empfangt im nachstenSlot
Fur jedes Paket werdenk + 2 Slots benotigt r
h
k+
2h>
k+
2
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (35/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Phase II - Einsammeln naher Pakete
Lemma (ohne Beweis)Fur Baume mit konstant beschrankter Hohekann ein Schedule verabredet werden, in dem injedem Zeitschritt genau ein Paket ubertragenwird!
zentral ist das ohnehin einfachjeweils linkester dichtester Knoten mitPaketen schickt Paket auf den Weg..
das lasst sich auch verteiltdurchnummerieren (ohne Beweis)
r
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (36/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Analyse
SatzDer 2-Phasen-Algorithmus benotigt hochstens 4 mal sovieleZeitschritte wie ein optimaler Schedule!
Phase I: Jedes Paket mit hu > k + 2 schlagt mit k + 2Zeitschritten zu Buche (Pipelining!)Phase II: Jedes Paket mit hu k + 2 schlagt mit hu Zeitschrittenzu Buche (exklusives Senden)
) Gesamtzeit: X
u2V
(pu · min{hu, k + 2})
min{hu, k + 2} k+2b(k+1)/2c min{hu, b(k + 1)/2c}
k+2b(k+1)/2c 4
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (37/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Zum Mitnehmen
Data Gathering ist ein Hauptzweck vieler Sensornetzeleider auch eine vielschichtige Herausforderung
Datenaggregationgeschickte Verarbeitung im Netz kann Anfragen beschleunigenbei Primitiven einigermaßen gut verstandenbei komplexeren (Datenbank-)Operationen noch viele offeneFragen!
Koordination / SchedulingKlare Schedules sparen Mithoren und unnotige Aktivzeiten
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (38/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik
Literatur
1 Fabian Kuhn, Thomas Locher, Roger Wattenhofer: Tight Boundsfor Distributed Selection. In: 19th ACM Symposium onParallelism in Algorithms and Architectures (SPAA), 2007
2 Bastian Katz, Steffen Mecke, Dorothea Wagner: EfficientScheduling of Data Harvesting Trees. In: Proceedings of the 4thInternational Workshop on Algorithmic Aspects of WirelessSensor Networks (ALGOSENSORS), 2008
Markus Volker – Algorithmen fur Ad-hoc- und SensornetzeVL 07 – Data Gathering (39/39)
Institut fur Theoretische InformatikLehrstuhl Algorithmik