Seminar: Perlen der Theoretischen Informatik

Titel der Arbeit: Obere und Untere Schranken der Laufzeit beim Broadcasting in Funknetzwerken.

Abstract:

Diese Arbeit untersucht die Zeit, die eine Nachricht ausgehend von einer Quelle benötigt um alle Teilnehmer eines Multi-Hop Funknetzwerks zu erreichen (Broadcast). Dabei wird davon ausgegangen, dass die Topologie der Netzwerke nicht bekannt ist und es in der Regel keinen direkten Weg (1-Hop) von der Quelle zu allen anderen Knoten gibt. Außerdem wird angenommen, dass ein Knoten nur dann eine Nachricht erhält wenn genau einer seiner Nachbarn diese Nachricht abschickt. Bei mehreren Sender kommt es zu einer Kollision. Ebenfalls wird angenommen, dass die Knoten solche Kollisionen nicht erkennen können, d.h. sie können den Fall das kein Nachbar sendet nicht von dem Fall, dass mehrere Nachbarn senden unterscheiden. Die Kommunikation der hier vorgestellten Protokolle läuft synchronisiert in Zeitabschnitten ab.

Es wird ein randomisiertes Protokoll vorgestellt, dass für den Broadcast einer Nachricht in eben solchen Netzwerken, mit Wahrscheinlichkeit 1 − eps, O((D + log n/eps) ∗ log n) Zeitabschnitte benötigt, wobei n die Anzahl der Knoten und D der Durchmesser des Netzwerks ist. Ferner wird bewiesen, dass für das Broadcasting von beliebigen deterministischen Protokollen eine untere Schranke Omega(n) für die Anzahl der benötigten Zeitabschnitte existiert.

Diese Schranke gilt sogar für Netzwerke mit Durchmesser gleich 3. Diese beiden Ergebnisse zeigen einen exponentiellen Unterschied in der Laufzeit bei randomisierten und deterministischen Protokollen.

BroadcastingFunknetzwerke.pdf