QoS based scheduling in the downlink of multi-user wireless systems (extended)

Frame aggregation is a MAC-layer technology proposed in 802.11n WLAN. The base station can serve two or more users in one frame simultaneously, which can improve MAC-layer efficiency by reducing the transmission time for preamble and frame headers, and the random backoff period for successive frame transmissions. This fact enables us to design a more QoS-aware scheduler from the MAC layer. In this paper, we first formulate the scheduling problem with frame aggregation into a knapsack problem that is shown NP hard. Then we propose a simple approximation algorithm (LUUF) based on the unit urgency concept. Our analysis shows that the complexity of LUUF is O(nlogn)O(nlogn) and it achieves an approximation ratio of F′/FmaxF′/Fmax. We then show that in practice the complexity can be further reduced to O(n)O(n) and the approximation ratio can be made very near to 1, which makes LUUF a promising candidate for wireless systems that support frame aggregation. We also conduct simulations comparing LUUF with the widely used Round-Robin scheduler and find that LUUF can significantly improve the quality of service for various numbers of users and different maximum aggregation frame sizes.