English

We are considering a wireless network deployed in vast terrain. In this scenario the distances between network parts are expected to be large and thus we assume that parts of the network inevitably become disconnected. We are looking for methods which actively prevent these disconnections. For this purpose we employ mobile robotic relay stations, which form chains in the terrain and forward network communication between its disconnected parts. In particular, we are looking for local and distributed strategies which allow those relay stations to effectively organize into the chains. From a global perspective we also propose algorithms which manage whole chains, minimizing the number of relay stations necessary and their energy consumption. Thereby, we lay an algorithmic foundation for the usage of mobile relay stations to enable communication in sparse networks. The problem is considered on two layers. On the one hand we are concerned with the organization of such communication chains using simple, local and distributed strategies. These are employed by the relays in order to keep up a connected chain with their neighbors. The goal of the relays is to keep the chain as short as possible, although one of its endpoints may move on the terrain. We are able to show that relays which are restricted to measure the relative positions of their neighbors can maintain a chain of length only by a constant factor longer than the optimal one. In the second part of the dissertation we are dealing with the question where to deploy communication chains and how to assign relays to those chains. In this considerations we are aiming at minimizing the energy consumed by the relays to move between different chains.

Deutsch

Wir befassen uns mit der Konnektivität von Netzwerken, die in weitem Gelände eingesetzt werden. Wegen der großen Entfernungen zwischen einzelnen Netzwerkteilen müssen wir davon ausgehen, dass direkte Verbindungen nicht immer aufrechterhalten werden können und das Netzwerk die Konnektivität verliert. Um das zu verhindern schlagen wir vor, mobile Relaisstationen zu benutzen, die Ketten formen und Kommunikation zwischen Netzwerkteilen weiterleiten. Wir suchen lokale und verteilte Strategien, die es den Relaisstationen erlauben, Ketten selbständig zu erhalten. Weiterhin schauen wir aus einer globalen Perspektive, wie Ketten und Relaisstationen geleitet werden können um die Anzahl der benutzten Stationen zu minimieren und den Energiebedarf gering zu halten. Dies stellt eine algorithmische Grundlage für den Einsatz von mobilen Relaisstationen zum Erhalten von Konnektivität dar. Im Rahmen der Arbeit wird das Problem auf zwei Ebenen untersucht. Einerseits beschäftigen wir uns mit der Aufrechterhaltung von Kommunikationsketten durch einfache, lokale und verteilte Strategien. Diese werden von den Verbindungsstationen selber eingesetzt, um zusammen mit den Nachbarn eine zusammenhängende Kette zu bilden. Es ist die Aufgabe der Verbindungsstationen, die Kette trotz der Bewegung eines Endes so kurz wie möglich zu halten. Wir kommen zu dem Schluss, dass eine Strategie dessen Aktionen nur auf Basis der relativen Positionen der Kettennachbarn berechnet werden, eine bis auf konstante Faktoren optimale Lösung darstellt. Im zweiten Teil der Arbeit beschäftigen wir uns mit der Frage, wo Kommunikationsketten eingesetzt werden sollen und auf welche Weise Verbindungsstationen diesen Ketten zugewiesen werden. Dabei soll vor allem der Energieverbrauch der mobilen Verbindungsstationen beim Wechsel der Position der Kette und beim Wechsel zwischen verschiedenen Ketten minimiert werden.