Beschreibung
Ein Sensornetzwerk ist ein Verbund vieler kleiner, verteilter Recheneinheiten -- den Sensorknoten. Diese Knoten kommunizieren drahtlos miteinander und sind üblicherweise mit nur sehr beschränkten Ressourcen (Rechenleistung, Speicherplatz, Batteriekapazität) ausgestattet.
Sensornetze sind ideal dafür geeignet, weitläufige Gebiete zu überwachen. Hierfür werden viele Sensorknoten zufällig über die zu beobachtende Fläche verteilt. Oft sind dies weit mehr als für eine lückenlose Überdeckung notwendig sind. Deshalb können Knoten abgeschaltet werden, bis sie benötigt werden. Durch diese Maßnahme lässt sich die Überwachungsdauer des gesamten Sensornetzes teils beträchtlich erhöhen, bevor eine lückenlose Überdeckung durch Knotenausfall nicht mehr garantiert werden kann.
Thema der Arbeit
Ziel der Arbeit ist der Entwurf eines Verfahrens zur Berechnung optimaler Einsatzpläne für die Gebietsüberwachung durch Sensorknoten. In einem weiteren Schritt soll das Verfahren anschließend als Baustein für einen komplexeren PTAS-Algorithmus verwendet werden.
Die Berechnung der optimalen Einsatzpläne soll mit linearer Programmierung erfolgen. Die korrekte Aufbereitung der Eingabedaten und die geschickte Verwendung des Solvers stellen bereits interessante Aufgaben dar. In diesem Rahmen können anschließend auch einfach weitere Anforderungen untersucht werden, die an einen optimalen Einsatzplan gestellt werden.
Vorraussetzungen
- Interesse an Algorithmen und Datenstrukturen, sowie solide Kentnisse auf diesen Gebieten
- Gute Programmierkentnisse in C++
Gebotenes
- Mitarbeit an einem echten Forschungsthema
- Einblick in Verfahren zur Gebietsüberwachung und lineare Programmierung
