Approximationsalgorithmen für Spektrumsallokation und Power Control in Funknetzwerken

Abstract

In einem Funknetzwerk können gleichzeitige Transmissionen aufgrund von Interferenzeffekten kollidieren. Um trotzdem eine zuverlässige Funktionsweise garantieren zu können, sind Algorithmen erforderlich, die die Zugriffe auf das Funkspektrum verwalten. In dieser Arbeit entwerfen und analysieren wir derartige Algorithmen aus der Perspektive der Theoretischen Informatik. Da sich die behandelten Probleme unter den üblichen Annahmen der Komplexitätstheorie nicht effizient exakt lösen lassen, betrachten wir Approximationsalgorithmen. Hierbei verfolgen wir das Ziel, beweisbare Garantien über die Qualität der berechneten Lösung herzuleiten. Im Gegensatz zu den meisten früheren Arbeiten in der Algorithmik modellieren wir die Interferenzbedingungen mit Hilfe des Signal-zu-Interferenz-plus-Rausch-Verhältnisses (signal-to-interference-plus-noise ratio, SINR). Auf diese Weise erlaubt uns das Interferenzmodell, variable Sendeleistungen zu berücksichtigen.