On the Complexity of Scheduling in Wireless Networks
By Changhee Joo, Gaurav Sharma, Ness B. Shroff, Ravi R. Mazumdar. ACM/IEEE International Conference on Mobile Computing and Networking, 2006
441 citations recorded by the source corpus.
We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of -hop interference models, under which no two links within a -hop distance can successfully transmit at the same time. For a given , we can obtain a throughput-optimal scheduling policy by solving the well-known maximum weighted matching problem. We show that for , the resulting problems are NP-Hard that cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, for geometric unit-disk graphs that can be used to describe a wide range of wireless networks, the problems admit polynomial time approximation schemes within a factor arbitrarily close to 1. In these network settings, we also show that a simple greedy algorithm can provide a 49-approximation, and the maximal matching scheduling policy, which can be easily implemented in a distributed fashion, achieves a guaranteed fraction of the capacity region for "all ." The geometric constraints are crucial to obtain these throughput guarantees. These results are encouraging as they suggest that one can develop low-complexity distributed algorithms to achieve near-optimal throughput for a wide range of wireless networks.
Subfields: Computer Networks and Communications, Electrical and Electronic Engineering
View Paper: https://www.semanticscholar.org/paper/ad9c55dd38dc51711ab59730e5c1e5e5bf5a4b30
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Mung Chiang
- John C. Doyle
- Steven H. Low
- A. Robert Calderbank
- Yvonne Anne Pignolet
- Olga Goussevskaia
- Amitava Ghosh
- Krishna Chintalapudi
In Electrical and Electronic Engineering
- Mung Chiang
- John C. Doyle
- Steven H. Low
- A. Robert Calderbank
- Yvonne Anne Pignolet
- Olga Goussevskaia
- Amitava Ghosh
- Bhaskar Krishnamachari
Citations in the corpus
- Fast Data Collection in Tree-Based Wireless Sensor Networks (2012, background): “Approximation bounds on JFTSS for single-channel systems and its comparison with multichannel systems are discussed in [22] and [23], respectively.”
- Complexity in geometric SINR (2007, background): “A variety of centralized and decentralized approximation algorithms have been proposed and their quality analyzed for this kind of model [14, 20, 24, 31, 32].”
- Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures (2007, background): “, [12], [14], [78], [121], [150], [151], [164], based on different physical models, e.”