Rainer, D. (2018). Geometrische Zufallsgraphen und ihre Anwendungen [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2018.50320
geometric random graph; Poisson process; WiFi networks
en
Abstract:
Die Graphentheorie ist ein Teilgebiet der Mathematik, welches sich aus realen Fragestellungen im 18. Jahrhundert entwickelte und heutzutage Lösungen für viele unterschiedliche Anwendungsgebiete bietet. Etwas jünger ist die Theorie der geometrischen Zufallsgraphen, welche im 20. Jahrhundert von Gilbert zur Untersuchung von Kommunikationsnetzwerken eingeführt wurde - hier sind die Graphen nicht mehr ausschließlich rein mathematische Objekte, sondern Objekte in einem geometrischen Raum, in welchen die Lage der Knoten und die Distanz der Knoten eine große Rolle spielen. In dieser Arbeit werden in Kapitel 2 geometrische Zufallsgraphen eingeführt und grundlegende asymptotische Eigenschaften des Graphen G(X_n, r_n) für bestimmte Folgen r_n untersucht. Diese Analysen spielen auch für reale Anwendungen eine große Rolle, da man bei der Verwendung von geometrischen Zufallsgraphen oft bestimmte Eigenschaften, wie beispielsweise den Zusammenhang des Graphen garantieren muss, damit er sinnvoll als Modell für die Anwendungen verwendet werden kann. In Kapitel 3 werden nun verschiedene, ausgewählte Anwendungen von geometrischen Zufallsgraphen in der Untersuchung von ad-hoc WiFi Netzwerke erläutert und verschiedene bekannte Resultate zusammengefasst: Betrachtet man Wurm-Epidemien in ad-hoc WiFi Netzwerken, so können diese Epidemien mit einem auf geometrische Zufallsgraphen basierenden Modell analysiert werden, wobei diese Resultate, welche in Abschnitt 3.3 präsentiert werden, helfen sollen, die Verbreitung von Computerwürmern in solch Netzwerken zu verstehen als auch im Weiteren zu verhindern. Anschließend wird in Abschnitt 3.4 noch ein Routing-Protokoll für die Datenübertragung in ad-hoc WiFi Netzwerken vorgestellt, wobei hier für die Analyse ebenfalls auf geometrische Zufallsgraphen zurückgegriffen wird.
de
Graph theory is a subdomain of mathematics, which arose out of real questions and problems in the 18th century. Today it offers different solutions for various problems and areas. The theory of random geometric graphs, which is younger, was introduced in the 20th century by Gilbert to investigate the theory of communication networks. Random geometric graphs aren't anymore only abstract mathematical objects, but objects in a geometric space where the locations of the vertices and the distance of the vertices to each other has an important role. In this thesis random geometric graphs get introduced and motivated in chapter 2 and some asymptotic properties of the graph G(X_n, r_n) are given for specific limiting regimes r_n. These properties are important in real applications as well, as for simulations various properties of the random geometric graphs have to be ensured to use them as a useful model for the desired applications. In chapter 3 some applications of random geometric graphs in the area of ad-hoc WiFi networks are explained and given: Is there a worm-epidemy in an ad-hoc network, it's possible now to analyse these epidemies by a model based on random geometric graphs. The results, which are given in section 3.3 should help to understand the propagation of worms and prevent propagation of them. In section 3.4 a routing protocol for communication in an ad-hoc network is presented - the analysis of this protocol is done with a model based on random geometric graphs as well.
en
Additional information:
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers