Projektübersicht

Fragestellungen des Projekts
Im Rahmen des Teilprojekts K5 sollen verschiedene algorithmische Aspekte von Sensor-Aktor-Netzwerken untersucht werden. Der zentrale Schwerpunkt liegt dabei auf Algorithmen, die dazu dienen, den Energieverbrauch von Sensornetzwerken zu reduzieren. Energiegewinnung und -speicherung auf kleinem Raum sind bisher noch nicht effizient genug gelöst, so dass die Energie als knappe Ressource auf einem einzelnen Sensorknoten betrachtet werden kann. Daher ist es wichtig, dass die zur Verfügung stehende Energie sinnvoll verwendet wird, um die mögliche Einsatzdauer der Netzwerke zu optimieren.
Es wurden zwei Teilbereiche aus diesem umfangreichen Gebiet ausgewählt, Optimierung der Lebensdauer und Routing, die als Schwerpunkte für die geplante Forschung in den kommenden Jahren dienen sollen.

Optimierung der Lebensdauer. Die Knoten, aus denen sich ein Sensornetzwerk zusammensetzt, üben ihre Aufgaben alleine und im Zusammenspiel mit anderen Knoten aus. Typischerweise werden aber nicht alle Knoten zu jeder Zeit benötigt. Daher ist es sinnvoll, für jeden einzelnen Knoten einen individuellen Einsatzplan zu erstellen. So kann der Energieverbrauch des gesamten Netzwerks unter Erhaltung der Funktionalität minimiert und damit die Lebensdauer maximiert werden.

Routing. Die Kommunikation zwischen den Sensorknoten ist eine der energieintensivsten Operationen innerhalb eines Sensor-Aktor-Netzwerks. Daher ist es wichtig, möglichst kurze und energieeffiziente Übertragungswege für die zu übermittelnden Informationen zu verwenden. Andererseits dürfen aber einzelne Knoten auch nicht überbeansprucht werden. Außerdem sind die auftretenden Kommunikationsmuster typischerweise anwendungsabhängig und sollten auch berücksichtigt werden.

Im gesamten Themengebiet der Sensor-Aktor-Netzwerke spielt die schnelle Anpassungsfähigkeit an veränderte Topologien (z. B. Ausfall eines Knotens, Bewegung) sowie die dezentrale Planung von Aktionen eine große Rolle. Beides sind wünschenswerte Eigenschaften, die bei klassischen Problemen normalerweise nicht auftauchen oder nur von kleiner Bedeutung sind, und die somit neu erschlossen werden müssen.


Stand der Forschung
Es existiert bereits eine Fülle sowohl praktischer als auch theoretischer Arbeiten auf dem Gebiet der Sensoreinsatzplanung und des Routings, die ihren Schwerpunkt auf die Energie-Effizienz ihrer Algorithmen und damit auf die Verlängerung der Lebensdauer der betrachteten Sensornetzwerke legen. Häufig handelt sich bei den präsentierten Verfahren aber um eher praktisch-orientierte ad-hoc Lösungen, die lediglich empirisch evaluiert worden sind und keine theoretischen Leistungsgarantien bieten, oder aber um rein theoretische Arbeiten, die ihre Lösungen auf zu einfachen, realitätsfernen Modellen aufbauen und bei echten Anwendungsfällen versagen. Diese mangelnde Überschneidung zwischen Theorie und Praxis zieht sich mit wenigen Ausnahmen durch das gesamte Forschungsgebiet.

Theoretische Untersuchungen zur Optimierung der Lebensdauer von Sensornetzwerken, die zur Überwachung von Gebieten eingesetzt werden, wurden z.B. von Calinescu et al. getätigt. Das Problem wird als lineares Programm formuliert und ein Approximationsalgorithmus zu dessen Lösung angegeben. Allerdings gibt es für dieses Problem bisher noch keine allgemeingültigen Komplexitätsuntersuchungen. Lediglich Cardei et al. haben die NP-Härte für einen Spezialfall dieses Überdeckungsproblems bewiesen. Viele dieser Arbeiten verwenden ein sehr einfaches Unit-Disk-Modell zur Modellierung der Netztopologie, die unter anderem als Grundlage für klassische Routingverfahren dient. Dieses sehr abstrakte Modell, aber auch realistischere Modelle können aber die teils chaotischen Gegebenheiten der Realität nur sehr unzureichend repräsentieren. Es existieren aber auch interessante Algorithmen, die keine initialen Annahmen über die Netztopologie benötigen. Hier sei auf das Routing-Verfahren GLIDER verwiesen. Dieser Verfahren ist sehr interessant, da Ansätze klassischer Routingverfahren, Landmarken und Hierarchien, aufgreift und für Sensornetzwerke adaptiert.

Um die Lücke zwischen Theorie und Praxis zu verkleinern, kann zur Analyse von Algorithmen mittlerweile auf sehr ausgereifte Simulatoren (ns-2) und Emulatoren (CMUlab) zurückgegriffen werden. Diese können zwar keine reale Testumgebung vollständig ersetzen, liefern aber in vielen Anwendungsfällen recht realistische Ergebnisse.


Ziele
Die Forschung in diesem Teilgebiet konzentriert sich auf Algorithmen zur Verlängerung der Lebenszeit von Sensor-Aktor-Netzwerken und auf Algorithmen zum Routing in diesen Netzen. Es sollen mehrere konkrete Anwendungsfälle für beide Fragestellungen identifiziert und untersucht werden. Ziel ist es, bestehende Ansätze für diese Anwendungsfälle zu evaluieren und zu verbessern sowie eigene innovative Algorithmen zu entwerfen. Im Vordergrund steht hierbei immer der Anspruch möglichst effiziente Algorithmen zu entwerfen, die gute theoretische Leistungsgarantien bieten. Außerdem ist es uns wichtig, robuste Algorithmen für reale oder zumindest realistische Szenarien zu entwerfen, die nicht nur auf einem vereinfachten Simulator sinnvolle Ergebnisse berechnen können.

Die Umsetzung der geplanten Ziele beinhaltet zunächst das Aufstellen von geeigneten Modellen sowie die mathematische Formulierung der betrachteten Probleme und deren Komplexitätsanalyse. Ausgehend von den theoretischen Ergebnissen werden Algorithmen zur Bestimmung von exakten oder approximativen Lösungen mit festen Qualitätsgarantien nach den Methoden des Algorithm Engineering entworfen. Es werden sowohl zentralisierte als auch verteilte Ansätze verfolgt werden, die theoretisch und experimtentell evaluiert werden.