Dokument: Graph Connectivity with Respect to Wireless Ad-Hoc Sensor Networks
| Titel: | Graph Connectivity with Respect to Wireless Ad-Hoc Sensor Networks | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=38993 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20160719-093259-8 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Hoffmann, Stefan [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Wanke, Egon [Gutachter] Prof. Dr. Rothe, Jörg [Gutachter] | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibungen: | This thesis deals with problems that are related to graph connectivity and emerge from wireless ad-hoc multi-hop networks.
The so-called {\sc Neighborhood Broadcast} problem describes the task of distributing a message across the neighborhood of a node $v$ under the assumption that $v$ %this particular node $v$ will not contribute to the solution. This routing problem occurs during route repair and collaborative decision making and is solved by presenting the $k$-HBF protocol for a positive integer $k$. It is proven that the protocol is successful, if $k\ge 2d-1$ and $v$ is $d$-locally connected, meaning that the $d$-hop neighborhood of $v$ induces a connected subgraph. It is also shown that the set of nodes participating in the execution is optimal under all protocols that are restricted to the same topology information, i.e. that every participating node also has to participate in every protocol that guarantees delivery. Simulations based on commonly used wireless network graph models demonstrate a high success rate for low values of $k$. The question of how to determine, in linear time, the minimum integer $d$ such that a vertex in a given graph is $d$-locally connected is also answered and it is discussed how this algorithm can be implemented in a distributed environment. Due to the relationship to local connectivity, several graph theoretic problems related to topology control are considered to investigate possibilities for increasing local connectivity during network design. Special attention is given to graph augmentation in this context, i.e. the question of how many edges have to be added to a given graph in order to make the $1$-hop neighborhood of every vertex induce a connected subgraph, a problem that is split into two different versions: The {\em strong} augmentation problem considers the neighborhoods of the augmented graph, while the {\em weak} augmentation problem is concerned with the original neighborhoods of the given graph. It is shown that the corresponding decision problems for both versions are NP-complete and an algorithm is developed and analyzed that approximates the weak augmentation problem within a factor of $1 + ln(\Delta)$, where $\Delta$ denotes the maximum vertex degree of the graph. It is also shown that computing the maximum connected induced subgraph, in which every vertex is $1$-locally connected, is NP-complete and that the same result holds for deleting a maximum number of edges while preserving the $1$-locally connected property. % for all vertices. Finally, wireless networks with two distinct power levels are considered. Assuming that each node can increase transmission power to reach an additional set of neighbors yields the question of how many nodes have to use increased power to achieve connectivity of the network. This thesis presents a family of approximation algorithms for this NP-complete problem that allows gradually incrementing approximation quality by providing increased computational power.Diese Arbeit besch\"aftigt sich mit Zusammenhangsproblemen, die aus der Betrachtung von Funknetzwerken resultieren. Es wird u.a. die Frage beantwortet wie eine Nachricht an alle Nachbarn eines Knotens $v$ verteilt werden kann, unter der Annahme, dass $v$ nicht zur Erf\"ullung dieser Aufgabe beitr\"agt. Dieses Problem tritt z.B. bei der Reparatur von Routingwegen oder der gemeinsamen Entscheidungsfindung auf und wird durch Angabe des sog. $k$-HBF Protokolls mit Parameter $k\in\mathbb{N}$ gel\"ost. Es wird bewiesen, dass das Protokoll erfolgreich die Nachricht verteilt, wenn $k\ge 2d-1$ gilt und $v$ $d$-lokal zusammenh\"angend ist, d.h. dass die $d$-Hop Nachbarschaft von $v$ einen zusammenh\"angenden Graphen induziert. Es wird auch gezeigt, dass $k$-HBF bzgl. der verwendeten Knoten optimal ist: Jeder beteiligte Knoten muss von jedem Protokoll verwendet werden, das die Verteilung garantiert und auf die gleichen Topologieinformationen beschr\"ankt ist. Empirische Auswertungen zeigen zudem hohe Erfolgsraten f\"ur kleine Werte von $k$. Au\ss{}erdem wird untersucht wie sich die kleinste Zahl $d$, so dass ein gegebener Knoten $d$-lokal zusammenh\"angend ist, in Linearzeit bestimmen l\"asst und wie dieses Verfahren verteilt implementiert werden kann. Ausgehend von dieser Verbindung zum lokalen Zusammenhang werden anschlie\ss{}end graphentheoretische Probleme analysiert, mit Hilfe derer diese Eigenschaft durch Topologiekontrolle beeinflusst werden kann. Besondere Beachtung erh\"alt dabei die Frage wie viele zus\"atzliche Kanten eingef\"ugt werden m\"ussen, damit die $1$-Hop Nachbarschaft jedes Knotens einen zusammenh\"angenden Teilgraphen induziert, wobei sich zwei Varianten dieses Augmentierungsproblems ergeben: In der {\em starken} Version werden die Nachbarschaften im erweiterten Graphen betrachtet, in der {\em schwachen} Version die Nachbarschaften im urspr\"unglichen Graphen. Es wird gezeigt, dass beide Varianten NP-vollst\"andig sind und wie die schwache Version mit einem Faktor von $1 + ln(\Delta)$ approximiert werden kann, wobei $\Delta$ den maximalen Knotengrad bezeichnet. Ebenfalls NP-vollst\"andig sind die Frage nach dem gr\"o\ss{}ten zusammenh\"angenden induzierten Teilgraphen, in dem alle Knoten $1$-lokal zusammenh\"angend sind und die Frage, wie viele Kanten entfernt werden k\"onnen ohne diese Eigenschaft zu verletzen - letzteres wieder in zwei Varianten. Abschlie\ss{}end werden Funknetzwerke mit zwei Sendest\"arken betrachtet. Die Annahme jeder Knoten k\"onne durch Erh\"ohung der Sendeleistung zus\"atzliche Nachbarn erreichen, wirft die Frage auf, wie viele Knoten mit h\"oherer Leistung senden m\"ussen, damit ein zusammenh\"angendes Netzwerk entsteht. F\"ur dieses NP-vollst\"andige Problem wird ein parametrisierter Approximationsalgorithmus vorgestellt, der eine schrittweise Erh\"ohung der Approximationsg\"ute auf Kosten zus\"atzlicher Rechenleistung erm\"oglicht. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Algorithmen und ihre Anwendungen | |||||||
| Dokument erstellt am: | 19.07.2016 | |||||||
| Dateien geändert am: | 19.07.2016 | |||||||
| Promotionsantrag am: | 25.05.2016 | |||||||
| Datum der Promotion: | 15.07.2016 |
