Date Added: Dec 2011
The authors consider a general class of low complexity distributed scheduling algorithms in wireless networks, maximal scheduling with priorities, where a maximal set of transmitting links in each time slot are selected according to certain pre-specified static priorities. The proposed scheduling scheme is simple, which is easily amendable for distributed implementation in practice, such as using Inter-Frame Space (IFS) parameters under the ubiquitous 802.11 protocols. To obtain throughput guarantees, they first analyze the case of maximal scheduling with a fixed priority vector, and formulate a lower bound on its stability region and scheduling efficiency. They further propose a low complexity priority assignment algorithm, which can stabilize any arrival rate that is in the union of the lower bound regions of all priorities.