Date Added: Dec 2009
Optimal scheduling for concurrent transmissions in rate-non-adaptive wireless networks is NP-hard. Optimal scheduling in rate-adaptive wireless networks is even more difficult, because, due to mutual interference, each flow's throughput in a time slot is unknown before the scheduling decision of that slot is finalized. The capacity bound derived for rate-non-adaptive networks is no longer applicable either. In this paper, the authors first formulate the optimal scheduling problems with and without minimum per-flow throughput constraints. Given the hardness of the problems and the fact that the scheduling decisions should be made within a few milliseconds, they propose two simple yet effective searching algorithms which can quickly move towards better scheduling decisions.