Dustin Eversmann

Interferenzminimierung in eindimensionalen Sensornetzen

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Diplom
Abgabedatum: 05.04.2013

Kurzbeschreibung

Das Ziel dieser Arbeit war die Entwicklung eines Polynomialzeitalgorithmus zur Interferenzminimierung in eindimensionalen Sensornetzen. Diese Minimierung soll die Anzahl erneuter Übertragungen und somit den Energieverbrauch reduzieren.

Es wird die bereits gezeigte obere Schranke der optimalen Interferenz von 2logn auf logn + 1 und somit annähernd auf das Optimum gesenkt. Ausgehend von dem bereits gezeigten Zusammenhang zwischen optimalen Lösungen und binären Suchbäumen werden neue Erkenntnisse über die Struktur optimaler Lösungen gewonnen sowie Zusammenhänge aufgezeigt und damit eine Vermutung widerlegt.

Darauf aufbauend werden Algorithmen vorgestellt, die sich unterschiedlicher Methoden bedienen und unter denen sich ein Verfahren mit quasi-polynomieller Laufzeit befindet. Da kein Polynomialzeitalgorithmus gefunden wurde, werden darüber hinaus diverse Heuristiken vorgestellt und die Bearbeitung einer weiterführenden Fragestellung nahegelegt.