Titelaufnahme

Titel
Information dissemination in random networks / Sérgio Armindo Lopes Crisóstomo
Weitere Titel
Information dissemination in random networks
VerfasserLopes Crisóstomo, Sérgio Armindo
Begutachter / BegutachterinBarros, João ; Bettstetter, Christian
Erschienen2012
UmfangXXIX, 125 S. : graph. Darst.
HochschulschriftKlagenfurt, Alpen-Adria-Univ., Diss., 2012
Anmerkung
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
Zsfassung in dt. und span. Sprache
SpracheEnglisch
Bibl. ReferenzOeBB
DokumenttypDissertation
Schlagwörter (DE)Information Dissemination / zufallsbasierte Algorithmen / Flooding-Algorithmus / drahtlose Sensornetze / Network Coding / Graphentheorie / zufällige Netzwerke / stochastische Geometrie
Schlagwörter (EN)information dissemination / probabilistic algorithms / flooding algorithms / wireless sensor networks / network coding / graph theory / random networks / stochastic geometry
URNurn:nbn:at:at-ubk:1-6137 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Information dissemination in random networks [1.97 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Die vorliegende Dissertation beschÃ$ftigt sich mit der Dissemination von Information in einem Kommunikationsnetzwerk mit Broadcast-Kanal. Die zentrale Frage, welcher wir uns in dieser Arbeit widmen, ist wie man eine Nachricht ausgehend von einem Quellknoten effizient an alle anderen Knoten im Netzwerk verteilt. Hierbei verfolgen wir zwei Hauptziele: (1) Die Nachricht soll mit hoher Wahrscheinlichkeit alle Knoten im Netzwerk erreichen; (2) Es sollen so wenige Ébertragungen wie mÃglich stattfinden.

In diesem Zusammenhang wenden wir uns hauptsÃ$chlich Algorithmen zur probabilistischen Dissemination von Information zu. Wir modellieren Kommunikationsnetzwerke als Zufallsgraphen, die auf stochastischen Prozessen beruhen. Wir verwenden Methoden der Graphentheorie sowie der stochastischen Geometrie um Disseminationsalgorithmen basierend sowohl auf Nachrichtenweiterleitung als auch auf Network Coding zu analysieren.

Unser erstes Resultat ist eine analytische Studie von probabilistischem Flooding. In dieser Studie zeigen wir, wie die netzwerkweite Weiterleitungswahrscheinlichkeit gewÃ$hlt werden soll, sodass eine Nachricht mit hoher Wahrscheinlichkeit alle Knoten im Netzwerk erreicht.

Als nÃ$chstes widmen wir uns der Frage, welche Vorteile ein probabilistischer Flooding-Algorithmus basierend auf Network Coding gegenÃber klassischen Methoden hat. Dabei wird die Network-Coding Methode mit dem weit verbreiteten MultiPoint Relay-Algorithmus verglichen. Der Vergleich erfolgt mittels analytischer und numerischer Methoden. Schlussendlich verwenden wir die Erkenntnisse der oben beschriebenen Studien dazu, um ein vernetztes Sensor-Aktuator-System zu entwerfen, welches als Notfallschutzsystem innerhalb von GebÃ$uden zum Einsatz kommen soll. Es soll Personen den kuerzesten sicheren Pfad zu den NotausgÃ$ngen anzeigen. Das Auffinden dieser Pfade erfolgt dabei verteilt basierend auf den Messungen der einzelnen Knoten, die Ãber das gesamte Netzwerk disseminiert werden.

Zusammenfassung (Englisch)

This dissertation focuses on the study of information dissemination in communication networks with a broadcast medium. The main problem we address is how to disseminate efficiently a message from a source node to all other network nodes. In terms of efficiency we target two goals: (1) to deliver a source message to all network nodes with high probability; and (2) to use as few transmissions as possible for a given target reachability.

In this context, our main focus is devoted to probabilistic dissemination algorithms. Modeling networks as random graphs, which are built from stochastic processes, and using methods from graph theory and stochastic geometry we address both replication based and network coded information dissemination approaches.

The first contribution is an analytical study of probabilistic flooding which answers the question of which is the minimum common network-wide forwarding probability each node should use such that a flooded message is obtained by all nodes with high probability. Next, we address the question of which benefits can be expected from network coded based probabilistic flooding. We compare these benefits with the ones from the well established replication based MultiPoint Relay flooding. The study of their efficiency is performed both by analytical techniques and numerical methods.

Finally, we apply the insights gained from the study of information dissemination algorithms to the design of a sensor-actuator networked system for emergency response in indoor scenarios. The system guides people to the exits of a building via the shortest safe paths, computed autonomously by each node whenever a new measurement collected by a sensor is flooded throughout the network.

Statistik
Das PDF-Dokument wurde 13 mal heruntergeladen.