Prioritized Maximal Scheduling in Wireless Networks

This paper considers the scheduling problem in wireless networks. The authors focus on prioritized maximal scheduling, where a maximal scheduler chooses the links in an order specified by certain priority. They first analyze the capacity region of a maximal scheduler with fixed priority, where a lower bound is formulated and shown to be tight. Next, they propose both centralized and distributed algorithms to search for the optimal priority for a given arrival rate. The algorithms are optimal in the sense that, if the arrival rate is in the lower bound region of any prioritized maximal scheduling, it is stable under the result of their algorithms.