Practical scheduling schemes with throughput guarantees for multi-hop wireless networks

In wireless communication systems, the interference between links results in a challenging scheduling problem. A K-hop interference model is defined as one for which no two links within K-hops can successfully transmit at the same time (note that IEEE 802.11 DCF corresponds 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 interference constraints. Previous work has mainly focused on developing scheduling algorithms with performance guarantees for the primary interference model (K=1)(K=1). For K⩾2K⩾2, the problem is NP-Complete and cannot be approximated within a constant factor by any polynomial time algorithm. Our algorithm achieves at least a constant fraction (1/3) of the capacity region under any K-hop interference model. The simplicity of the solution and low control complexity makes it highly amenable for practical implementation. Simulation results show that when the communication overhead is taken into account, the delay characteristics of the proposed scheme may be better than the ideal optimal scheduler (given the prices at all the links, the ideal scheduler computes the optimal schedule instantaneously).