Title: Scheduling in Wireless Networks with Rayleigh-Fading Interference
Abstract: We study approximation algorithms for optimization of wireless spectrum access with n communication requests when interference conditions are given by the Rayleigh-fading model. This model extends the deterministic interference model based on the signal-to-interference-plus-noise ratio (SINR) using stochastic propagation to address fading effects observed in reality. We consider worst-case approximation guarantees for the two standard problems of capacity maximization and latency minimization. Our main result is a generic reduction of Rayleigh fading to the deterministic non-fading model. It allows to apply existing algorithms for the non-fading model in the Rayleigh-fading scenario while losing only a factor of O(log* n) in the approximation guarantee. This way, we obtain the first approximation guarantees for Rayleigh fading and, more fundamentally, show that non-trivial stochastic fading effects can be successfully handled using existing and future techniques for the non-fading model. We generalize these results in two ways. First, the same results apply for capacity maximization with variable data rates, when links obtain (non-binary) utility depending on the achieved SINR. Second, for binary utilities, we use a more detailed argument to obtain similar results even for distributed and game-theoretic approaches. Our analytical treatment is supported by simulations illustrating the performance of regret learning and, more generally, the relationship between both models.
Publication Year: 2015
Publication Date: 2015-07-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 32
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot