On the complexity of scheduling in wireless networks

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. We define a K-hop interference model as one for which no two links within K hops can successfully trans- mit at the same time (Note that IEEE 802.11 DCF cor- responds to a 2-hop interference model.). For a given K, a throughput-optimal scheduler needs to solve a maximum weighted matching problem subject to the K-hop interfer- ence constraints. For K = 1, the resulting problem is the classical Maximum Weighted Matching problem, that can be solved in polynomial time. However, we show that for K > 1, the resulting problems are NP-Hard and cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, we show that for spe- cific kinds of graphs, that can be used to model the underly- ing connectivity graph of a wide range of wireless networks, the resulting problems admit polynomial time approxima- tion schemes. We also show that a simple greedy matching algorithm provides a constant factor approximation to the scheduling problem for all K in this case. We then show that under a setting with single-hop traffic and no rate control, the maximal scheduling policy considered in recent related works can achieve a constant fraction of the capacity region for networks whose connectivity graph can be represented using one of the above classes of graphs. These results are encouraging as they suggest that one can develop distributed algorithms to achieve near optimal throughput in case of a wide range of wireless networks.