Fundamental Limits of CDF-Based Scheduling: Throughput, Fairness, and Feedback Overhead

"In this paper, we investigate fundamental performance limits of cumulative distribution function (CDF)-based scheduling (CS) in downlink cellular networks. CS is known as an efficient scheduling method that can assign different time fractions for users or, equivalently, satisfy different channel access ratio (CAR) requirements of users while exploiting multiuser diversity. We first mathematically analyze the throughput characteristics of CS in arbitrary fading statistics and data rate functions. It is shown that the throughput gain of CS increases as the CAR of a user decreases or the number of users in a cell increases. For Nakagami-m fading channels, we obtain the average throughput in closed form and investigate the effects of the average signal-to-noise ratio, the shape parameter m, and the CAR on the throughput performance. In addition, we propose a threshold-based opportunistic feedback technique in order to reduce feedback overhead while satisfying the CAR requirements of users. We prove that the average feedback overhead of the proposed technique is upper-bounded by -ln p, where is the probability that no user satisfies the threshold condition in a cell. Finally, we adopt a novel fairness criterion, called qualitative fairness, which considers not only the quantity of the allocated resources to users, but also the quality of the resources. It is observed that CS provides a better qualitative fairness than other scheduling algorithms designed for controlling CARs of users."This work was supported by the Canadian Natural Sciences and Engineering Research Council (NSERC) under Grant STPGP 396756 and the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education under Grant 2013R1A1A2A10004905. This paper has been published in part in the Proceedings of the IEEE International Conference on Communications (ICC), Budapest, Hungary, June 9-13, 2013. (Corresponding author: B. C. Jung.