Graduiertenkolleg 1194 "Selbstorganisierende Sensor-Aktor-Netzwerke"

K2.2: Algorithmische Aspekte drahtloser Sensornetze

Motivation

Viele Aufgaben der Kommunikation und Selbstorganisation in Sensor-Aktor-Netzen haben einen ausgeprägten kombinatorischen und geometrischen Kern, der sich aus der netzartigen Kommunikationsstruktur und der räumlichen Verteilung der Knoten ergibt. Dieser geometrische Kern konnte in der Vergangenheit bereits vielfältig genutzt werden, um neuartige Paradigmen und Algorithmen mit beweisbaren Eigenschaften zu entwickeln. Ein Beispiel hierfür sind geographische Routingverfahren. Einige für Sensornetze charakteristische Aspekte wie die verteilte Lösung anfallender Probleme und die Skalierbarkeit im Sinne einer nicht mit der Netzgröße wachsenden Belastung einzelner Knoten standen bereits in der Vergangenheit im Zentrum algorithmischer Überlegungen. Andere wichtige Aspekte wurden algorithmisch bisher entweder stark vereinfacht oder blieben sogar unberücksichtigt; darunter die gegenseitige Störung gleichzeitig stattfindender Übertragungen durch Interferenz und die Dynamik solcher Netze, denen Knoten spontan beitreten können oder in denen Knoten aufgrund des begrenzten Energiebudgets oder äußerer Einwirkung ausfallen können. Durch äußere Einflüsse und Mobilität der Knoten ist außerdem die Struktur des Kommunikationsnetzes zeitlichen Veränderungen unterworfen. In diesem Teilprojekt soll vor allem betrachtet werden, wie sich diese Aspekte algorithmisch in der Koordination und Strukturierung der Kommunikation in Sensornetzen berücksichtigen lassen, also in den Bereichen Scheduling und Topologiekontrolle:

Scheduling

Durch zeitliche Koordination der Kommunikation zwischen nahen Knoten des Netzes in Form fester Schedules kann eine kollisionsfreie und energieeffiziente Nutzung des drahtlosen Kanals garantiert werden. Die Berechnung solcher Schedules wiederum hängt stark von der oft anwendungsspezifischen Struktur der zu koordinierenden Kommunikation ab und davon, wie sich Übertragungen gegenseitig stören, also von der Umgebung bzw. von der Wahl des Interferenzmodells. In dynamischen Netzen besteht die neuartige Herausforderung darin, Schedules nicht einmalig zu berechnen, sondern bei Bedarf an geänderte Bedingungen anzupassen.

Topologiekontrolle

Die gezielte Beeinflussung der Netzstruktur durch Anpassung der Sendeleistungen oder allgemeiner durch Ausdünnung des Kommunikationsnetzes macht es möglich, bestimmte wünschenswerte strukturelle Eigenschaften herzustellen, ohne dabei andere Eigenschaften stark zu verschlechtern. Zu den erhaltenswerten Eigenschaften gehören etwa die Kosten für den Transport einer Nachricht zwischen beliebigen Endknoten oder vorhandene Redundanz und damit verbundene Robustheit des Netzes gegenüber Knotenausfällen. Angestrebte Eigenschaften zielen in der Regel auf eine gute Ausnutzung des drahtlosen Kanals: Störungen zwischen Übertragungen sollen gering gehalten werden, Kollisionen verhindert oder eine Koordination von Übertragungen vereinfacht werden.