h1

h2

h3

h4

h5
h6
http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png

Approximation and online algorithms for selected network optimization problems = Approximations- und Online-Algorithmen für ausgewählte Netzwerkoptimierungsprobleme



Verantwortlichkeitsangabevorgelegt von Marcel Ochel

ImpressumAachen : Publikationsserver der RWTH Aachen University 2013

UmfangVII, 125 S. : graph. Darst.


Aachen, Techn. Hochsch., Diss., 2013

Zsfassung in engl. und dt. Sprache


Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter


Tag der mündlichen Prüfung/Habilitation
2013-04-30

Online
URN: urn:nbn:de:hbz:82-opus-45634
URL: https://publications.rwth-aachen.de/record/211223/files/4563.pdf

Einrichtungen

  1. Fachgruppe Informatik (120000)
  2. Lehrstuhl für Informatik 1 (Algorithmen und Komplexität) (121110)

Inhaltliche Beschreibung (Schlagwörter)
Optimierung (Genormte SW) ; Approximationsalgorithmus (Genormte SW) ; Online-Algorithmus (Genormte SW) ; Competitive analysis (Genormte SW) ; OFDMA (Genormte SW) ; Scheduling (Genormte SW) ; Packungsproblem (Genormte SW) ; Informatik (frei) ; OFDMA scheduling (frei) ; approximation algorithm (frei) ; network lifetime maximization (frei) ; linear packing (frei) ; online analysis (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
In modernen Kommunikationsnetzen kommt der Optimierung des Energiebedarfs eine hohe Bedeutung zu. In dieser Dissertation untersuchen wir das Ziel optimaler Energienutzung auf zwei fundamentalen Klassen von Netzwerkoptimierungsproblemen: der Netzwerk-Lebenszeitmaximierung und der OFDMA Kanal- und Ratenzuweisung. Wir untersuchen Energieminimierungs- und Datenratenmaximierungsprobleme zunächst im Kontext von Orthogonal-Frequency-Division-Multiplexing (OFDM). In einer grundlegenden Variante des zugehörigen OFDM(A)-Scheduling-Problems sollen Informationen mit einer vorgegebenen Datenrate von einem Sender zu einer Menge von Empfängern auf möglichst energieeffiziente Weise übermittelt werden, wobei eine Anzahl von verschiedenen Frequenzbereichen (Kanälen) zur Verfügung steht. Da verschiedene Informationen an die jeweiligen Empfänger zu verschicken sind, können (aufgrund der entstehenden Interferenz) einzelne Frequenzbereiche nur jeweils einem Empfänger zugewiesen werden. Gesucht ist nun eine Zuweisung der Kanäle zu den Empfängern, so dass eine Datenratenverteilung auf die einzelnen Kanäle mit minimalem Energiebedarf bestimmt werden kann, welche die gegebenen Zieldatenraten für jeden Empfänger erfüllt. In der vorliegenden Arbeit wird erstmalig eine theoretische Worst-Case-Analyse dieser praktisch relevanten Klasse von Netzwerkoptimierungsproblemen durchgeführt, zu der bisher noch keine Komplexitäts- und Approximationsschranken bekannt sind. Wir zeigen, dass obiges Problem bereits auf einer eingeschränkten Instanzklasse für keinen polynomialzeitberechenbaren Faktor approximierbar ist, dass jedoch die natürliche duale Variante dieses Problems, welche darin besteht, für ein gegebenes Gesamtenergiebudget die Zieldatenraten proportional zu maximieren, die optimale Lösung in dieser Klasse beliebig gut approximiert werden kann. Im allgemeinen Fall der OFDMA-Ratenmaximierung beweisen wir Inapproximierbarkeit für jeden Faktor besser als 1/2. Neben einem matching-basierten Algorithmus, welcher einen Approximationsfaktor von 1/m (linear in der Kanalanzahl) erreicht, wird ein Ansatz entwickelt, welcher durch Rundung konvexer Subprobleme eine halbintegrale Lösung der Güte 1/2 berechnet. Im zweiten Teil dieser Dissertation betrachten wir anschließend Energieoptimierung in einer verstärkt impliziten Form: Motiviert vom Entladeverhalten batteriegespeister Sendegeräte in Drahtlos"=Sensornetzwerken untersuchen wir ein neuartiges Online-Modell für allgemeine lineare Pack- und Netzwerk-Lebenszeit-Optimierungsprobleme. Von den Ungenauigkeiten in der Bestimmung der noch zur Verfügung stehenden Energiemenge inspiriert, entwickeln wir ein Online-Modell, welches (im Gegensatz zu bereits existierenden Modellen) erlaubt, Ungewissheiten in Bezug auf die verfügbaren Kapazitäten zu modellieren. Im Rahmen kompetitiver Online-Analyse analysieren wir Algorithmen mit garantierter Lösungsgüte. Die entworfenen Online-Algorithmen weisen die Eigenschaft auf, dass sie auch auf kombinatorischen Packproblemen, welche nicht polynomiell durch ein lineares Programm darstellbar sind, angewendet werden können, da sie nur allgemeine Eigenschaften der zugrunde liegenden linearen Struktur ausnutzen. Dies macht sie insbesondere interessant für den Einsatz bei Netzwerk-Lebenszeit-Optimierungsproblemen. Da sie zudem (gegebenenfalls bekannte) Offline-Approximationsalgorithmen als Subroutine einbinden können und die Online-Gütegarantie dabei nur um den entsprechenden Faktor abnimmt, sind sie auch effizient auf NP-vollständige Probleme anwendbar. Die gezeigten Gütegarantien der entsprechenden Online-Algorithmen übersteigen naivere Herangehensweisen mindestens um einen logarithmischen Faktor (bzgl. des gegebenen Ungenauigkeits-Parameters). Komplementär zeigen wir eine obere Schranke für beliebige deterministische und randomisierte Online-Algorithmen in diesem Online-Modell.

Optimizing energy efficiency is a fundamentally important issue in modern communication networks. In this thesis we study the objective of optimal energy usage on two general classes of wireless network optimization problems, namely network lifetime maximization and OFDMA scheduling. Orthogonal frequency division multiplexing (OFDM) has become an increasingly popular technology in the area of broadband communication. In one of the associated fundamental scheduling problems, data has to be sent from a base station to a collection of terminals using a given set of communication channels where, however, each channel can be assigned to at most one designated terminal. Aside from determining an appropriate feasible assignment, each channel needs to be allocated a communication rate such that - summing over all channels assigned to a single terminal - the total data rate satisfies at least the demand of that terminal. In order to guarantee a successful transmission of data at a certain rate, the transmission power on the corresponding channel has to be large enough. The objective is to minimize the total sum of energy requirements while satisfying the demands of each terminal. This and related problems (called OFDMA scheduling problems) have been intensively studied by the engineering sciences; however, we are the first to conduct a theoretical worst-case analysis of this practically relevant class of network optimization problems for which no lower nor upper bounds on the approximability were known before. While we will show that - already on a very restricted subclass - the problem of minimizing the required transmission power for given data rate demands can not be approximated by any (polynomial time computable) factor, we will also see that the dual objective of proportionally maximizing the data rates for a given total transmission power is approximable arbitrarily close to the optimum on this subclass. On general instances, OFDMA rate-maximization will be shown to be inapproximable by any factor better than 1/2. Complementarily, a simple matching-based 1/m-approximation algorithm will be derived (with m denoting the number of channels). Also a more involved convex programming approach is considered that (aside from its usefulness to derive better performance guarantees for special subclasses) can be used to compute 1/2-approximate half-integral solutions in the general~case. In the second part of this dissertation, we continue with our theoretical study of energy minimization in a more implicit context: Motivated by the behavior of battery depletion in wireless sensor networks we introduce and analyze a novel online model for general linear packing problems, applicable to a broad class of network lifetime maximization problems. Network lifetime maximization aims at sustaining a prespecified communication requirement as long as possible in a given communication network with limited power supplies. Though there exists a vast number of approximation approaches for a large variety of lifetime maximization problems, all previous formulations of network lifetime optimization assume perfect a priori knowledge about the status and future behavior of the energy supplies of each single network node. We relax this assumption by introducing an appropriate multiplicative uncertainty parameter which initially allows only a rough estimation of the energy capacities that becomes more and more accurate when exhausting the corresponding resources. The definition of the online model and the competitive online algorithms developed in this work are independent of the underlying problem structure as long as the corresponding optimization problem can be formulated in terms of a general linear packing program. An advantageous property of the proposed online algorithms is that they do not require any explicit linear programming formulation; hence, they are also suited when algorithmic efficiency is an issue. As the algorithms additionally are approximation factor preserving they can be used as a framework for algorithmically intractable problem classes by applying appropriate offline approximation algorithms. The proven competitive factors of the more sophisticated algorithms outperform naive online algorithms by at least a logarithmic factor with respect to the fixed uncertainty parameter. Complementarily, we show bounds on the competitiveness of arbitrary deterministic or randomized online algorithms in this online model.

Fulltext:
Download fulltext PDF

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
English

Interne Identnummern
RWTH-CONV-143670
Datensatz-ID: 211223

Beteiligte Länder
Germany

 GO


OpenAccess

QR Code for this record

The record appears in these collections:
Document types > Theses > Ph.D. Theses
Publication server / Open Access
Faculty of Computer Science (Fac.9)
Public records
Publications database
120000
121110

 Record created 2013-07-17, last modified 2026-06-11


Fulltext:
Download fulltext PDF
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)