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.

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.