On a game theoretic approach to capacity maximization in wireless networks
Authors:
- 1 April 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 3029-3037
Abstract
We consider the capacity problem (or, the single slot scheduling problem) in wireless networks. Our goal is to maximize the number of successful connections in arbitrary wirelessnetworks where a transmission is successful only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. We study a game theoretic approach towards capacity maximization introduced by Andrews and Dinitz (INFOCOM 2009) and Dinitz (INFOCOM 2010). We prove vastly improved bounds for the game theoretic algorithm. In doing so, we achieve the first distributed constant factor approximation algorithm for capacity maximization for the uniform power assignment. When compared to the optimum where links may use an arbitrary power assignment, we prove a O(log Δ) approximation, where Δ is the ratio between the largest and the smallest link in the network. This is an exponential improvement of the approximation factor compared to existing results for distributed algorithms. All our results work for links located in any metric space. In addition, we provide simulation studies clarifying the picture on distributed algorithms for capacity maximization.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Wireless Capacity with Oblivious Power in General Metrics2011
- Distributed Algorithms for Approximating Wireless Network Capacity2010
- Distributed Contention Resolution in Wireless NetworksLecture Notes in Computer Science, 2010
- Capacity of Arbitrary Wireless Networks2009
- Improved Algorithms for Latency Minimization in Wireless Networks2009
- A measurement study of interference modeling and scheduling in low-power wireless networks2008
- Wireless Link Scheduling With Power Control and SINR ConstraintsIEEE Transactions on Information Theory, 2006
- The Complexity of Connectivity in Wireless Networks2006
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- The capacity of wireless networksIEEE Transactions on Information Theory, 2000