h1

h2

h3

h4

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

Approximation algorithms for spectrum allocation and power control in wireless networks = Approximationsalgorithmen für Spektrumsallokation und Power Control in Funknetzwerken



Verantwortlichkeitsangabevorgelegt von Thomas Keßelheim

ImpressumAachen : Publikationsserver der RWTH Aachen University 2012

UmfangX, 162 S. : Ill., graph. Darst.


Aachen, Techn. Hochsch., Diss., 2012

Zsfassung in dt. und engl. Sprache


Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter


Tag der mündlichen Prüfung/Habilitation
2012-08-06

Online
URN: urn:nbn:de:hbz:82-opus-42969
URL: https://publications.rwth-aachen.de/record/63041/files/4296.pdf

Einrichtungen

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

Inhaltliche Beschreibung (Schlagwörter)
Approximationsalgorithmus (Genormte SW) ; Funknetz (Genormte SW) ; Interferenz (Genormte SW) ; Scheduling (Genormte SW) ; Routing (Genormte SW) ; Verteilter Algorithmus (Genormte SW) ; Informatik (frei) ; approximation algorithms (frei) ; wireless networks (frei) ; scheduling (frei) ; power control (frei) ; SINR (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Funknetzwerke müssen trotz Interferenzeffekten zuverlässig arbeiten. Aus diesem Grund sind Algorithmen erforderlich, die die Zugriffe auf das Funkspektrum verwalten. In dieser Arbeit entwerfen und analysieren wir solche Algorithmen aus der Perspektive der Algorithmik. Hierbei verfolgen wir das Ziel, beweisbare Garantien herzuleiten. Im Gegensatz zu den meisten früheren Arbeiten in der Algorithmik modellieren wir die Interferenzbedingungen mithilfe 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. Im ersten Teil dieser Arbeit betrachten wir die grundlegenden kombinatorischen Optimierungsprobleme.Im Capacity-Maximization Problem ist eine Menge von n möglichen Kommunikationsanfragen gegeben. Von diesen Anfragen muss unter Einhaltung der Interferenzbedingungen eine möglichst große Anzahl ausgew¨ahlt werden. Im Latency-Minimization Problem hingegegen müssen alle Anfragen in möglichst wenigen Zeitschritten bedient werden. Wir untersuchen für beide Probleme sowohl die Variante, dass die Sendeleistungen im Voraus gegeben sind, als auch, dass der Algorithmus die Sendeleistungen auswählt. Für beide Varianten von Capacity Maximization stellen wir Approximationsalgorithmen mit konstantem Approximationsfaktor vor. Für Latency Minimization lassen sich hieraus unmittelbar O(log n)-Approximationen ableiten. Weiterhin analysieren wir einen verteilten Algorithmus für Latency Minimization mit festen Sendeleistungen und zeigen, dass dieser eine O(log² n)-Approximation erreicht. Darüber hinaus können vorhandene Ansätze mit unseren Algorithmen kombiniert werden, um Multi-Hop-Scheduling-Probleme zu lösen. Für diese erreichen wir ebenfalls polylog n-Approximationen. Als zweiten Schritt betrachten wir ein stochastisches Interferenzmodell, das auf Rayleigh-Fading basiert. Durch eine Black-Box-Transformation sind wir in der Lage, alle Ergebnisse zu übertragen. Hierbei verlieren wir nur einen Faktor von O(log* n) im Approximationsfaktor. Das heißt, wir erreichen die ersten O(log* n)-Approximationen für Capacity Maximization und O(log n log* n)-Approximationen für Latency Minimization im Rayleigh-Fading-Modell. Zusätzlich zu diesen theoretischen Analysen stellen wir Simulationsergebnisse für eine Reihe von Approximationsalgorithmen und Heuristiken vor. Diese zeigen, dass die von uns entwickelten Algorithmen zwei wünschenswerte Eigenschaften vereinen: In Bezug auf zufällig erzeugte Instanzen zeigen sie vergleichbare Ergebnisse wie frühere Algorithmen. Im Gegenzug ist jedoch bei unseren Algorithmen die Qualität des Ergebnisses garantiert. Insbesondere ist sichergestellt, dass in keinem Netzwerk nur triviale Lösungen berechnet werden. Im zweiten Teil beschäftigen wir uns mit erweiterten Problemszenarien. Mithilfe von geeigneten Abstraktionen sind wir in der Lage, die Ergebnisse aus dem ersten Teil weiterzuverwenden. Gleichzeitig sind unsere Ergebnisse allgemeiner, weil sie nicht nur auf SINR-basierte Modelle anwendbar sind, sondern auch auf eine Reihe weiterer Modelle, die zuvor in der Algorithmik untersucht wurden. Die erste Problemstellung, die wir behandeln, sind Auktionen für sekundäre Spektrumsmärkte. In diesen Märkten werden Lizenzen über die Sekundärnutzung von aktuell ungenutzten Teilen des Spektrums verkauft. Diese Lizenzen gelten nur kurzzeitig und lokal. Aus diesem Grund müssen sie Interferenz berücksichtigen. Wir stellen Approximationsalgorithmen vor, deren Garantien unter den üblichen Annahmen der Komplexitätstheorie fast optimal sind. Außerdem können diese für Truthful-in-Expectation-Mechanismen eingesetzt werden. Diese stellen sicher, dass kein Bieter davon profitieren kann, eine unwahre Bewertung mitzuteilen. Im anderen erweiterten Szenario untersuchen wir dynamisch auftretende Kommunikationsanfragen innerhalb eines Netzwerks. Wir führen zwei Modelle ein, die es uns erlauben, die Menge der auftretenden Anfragen zu quantifizieren und somit zu beschränken. Darüber hinaus stellen wir eine allgemeine Technik vor, um Algorithmen für das statische Scheduling-Problem in stabile Protokolle zu transformieren. Die Approximationsfaktoren bleiben hierbei erhalten. Abhängig vom angewandten Algorithmus für das statische Problem werden verteilte Protokolle erzeugt.

Wireless networks have to operate despite the effects of interference. Therefore, it is a vital prerequisite to have algorithms that suitably manage wireless spectrum accesses. In this thesis, we design and analyze such algorithms from a theoretical perspective, striving for provable performance guarantees. In contrast to most previous studies in algorithmic theory, interference constraints are stated based on the signal-to-interference-plus-noise ratio (SINR). This way, our interference model allows to take power control into account. That is, transmit powers are individually adjusted with the purpose of minimizing the effects of interference. In the first part of this thesis, we consider the very fundamental combinatorial optimization problems. In the capacity-maximization problem, given a set of n possible communication requests, the task is to select a maximum feasible subset of these requests. In the latency-minimization problem, in contrast, the task is to compute a schedule serving all of the requests using as few time slots as possible. We consider both problems in the variant that transmit powers are given in advance or that they are chosen by our algorithm. For both variants of capacity maximization, we present constant-factor approximations. In the case of latency-minimization, they directly yield centralized O(log n)-approximation algorithms. We also analyze a distributed algorithm for latency minimization with fixed transmit powers and show it to be an O(log² n)-approximation. Furthermore, existing approaches work well together with our algorithms allowing them to be used in multi-hop scheduling scenarios. Here, we also get polylog n approximations. As a second step, we study a more sophisticated, stochastic interference model using Rayleigh fading. We are able to transfer all of our results by presenting a black-box transformation of algorithms, which loses at most a factor of O(log* n) in the approximation factor. Thus, we obtain the first O(log* n)-approximations for capacity maximization and O(log n log* n)-approximations for latency minimization in the Rayleigh-fading model. In addition to these theoretical analyses, we present simulation results for a number of approximation algorithms and heuristics for capacity maximization. They are able to demonstrate that the algorithms we develop combine two favorable properties. With respect to the randomly generated networks in the simulations, they are able to compete with existing algorithms. In contrast to those algorithms, however, for our algorithms we can guarantee the performance. In particular, it never degenerates to a trivial one in any network. In the second part, we deal with two advanced problem scenarios. By using suitable abstractions, we are able to reuse the insights of the first part. At the same time, our results are more general because they do not only apply to SINR-based models but also to a number of further models previously studied in algorithmic research. The first setting we consider are auctions for secondary spectrum markets. In these markets licenses allowing secondary-usage of currently unused parts of the spectrum are being sold. Licenses are valid for short terms and in local areas. Thus, they have to take interference into account. We devise approximation algorithms whose guarantees are almost optimal under standard complexity-theory assumptions. Furthermore, we are able to turn them into truthful-in-expectation mechanisms ensuring that no bidder can benefit from lying about his true valuation. The other advanced problem we study deals with dynamically arising communication requests within a network. By introducing a stochastic and an adversarial injection model, we are able to quantify and to bound the amount of arising requests. Furthermore, we present a general technique to transform latency-minimization algorithms built for the respective static problem into stable protocols guaranteeing delivery in the dynamic setting. Approximation factors are preserved in this transformation. Depending on the applied static algorithm, the obtained protocol also works in a distributed way.

Fulltext:
Download fulltext PDF

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
English

Interne Identnummern
RWTH-CONV-124503
Datensatz-ID: 63041

Beteiligte Länder
Germany

 GO


OpenAccess

QR Code for this record

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

 Record created 2013-01-28, last modified 2022-04-22


Fulltext:
Download fulltext PDF
Rate this document:

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