Approximation algorithms for spectrum allocation and power control in wireless networks

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.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2012

Author dc:creator

• Keßelheim, Thomas

Contributors dc:contributor

• Vöcking, Berthold

• info:eu-repo/classification/ddc/004
• Approximationsalgorithmus
• Funknetz
• Interferenz
• Scheduling
• Routing
• Verteilter Algorithmus
• Informatik
• approximation algorithms
• wireless networks
• power control
• SINR

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124503%22

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:63041