On the complexity of scheduling in wireless networks

Changhee Joo, Gaurav Sharma, Ness B. Shroff, Ravi R. Mazumdar

Research output: Contribution to journalArticlepeer-review

29 Citations (Scopus)


We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of K -hop interference models, under which no two links within a K -hop distance can successfully transmit at the same time. For a given K, we can obtain a throughput-optimal scheduling policy by solving the well-known maximum weighted matching problem. We show that for K>1, 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 K. 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.

Original languageEnglish
Article number418934
JournalEurasip Journal on Wireless Communications and Networking
Publication statusPublished - 2010
Externally publishedYes

Bibliographical note

Funding Information:
This work has been supported in part by the NSF Awards CNS-0626703 and CNS-0721236, and the ARO MURI Award W911NF-08-1-0238, USA, and in part by the New Professor Research Program of KUT (2010), Korea.

ASJC Scopus subject areas

  • Signal Processing
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'On the complexity of scheduling in wireless networks'. Together they form a unique fingerprint.

Cite this