Scheduling in Wireless Networks with Rayleigh-Fading Interference
Authors:
- 26 August 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 14 (7) , 1503-1514
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.Keywords
Funding Information
- DFG (3831/3-1)
- DFG
- DFG
- German Academic Exchange Service
This publication has 25 references indexed in Scilit:
- Improved algorithms for latency minimization in wireless networksTheoretical Computer Science, 2011
- Throughput Analysis of Fading Sensor Networks with Regular and Random TopologiesEURASIP Journal on Wireless Communications and Networking, 2005
- A Network Information Theory for Wireless Communication: Scaling Laws and Optimal OperationIEEE Transactions on Information Theory, 2004
- Capacity regions for wireless ad hoc networksIEEE Transactions on Wireless Communications, 2003
- Mobility increases the capacity of ad hoc wireless networksIEEE/ACM Transactions on Networking, 2002
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- The capacity of wireless networksIEEE Transactions on Information Theory, 2000
- The Weighted Majority AlgorithmInformation and Computation, 1994
- On the Capacity of Multihop Slotted ALOHA Networks with Regular StructureIEEE Transactions on Communications, 1983
- Packet Radio Performance Over Slow Rayleigh Fading ChannelsIEEE Transactions on Communications, 1980