{'fraction_non_alphanumeric': 0.03640188019145329, 'fraction_numerical': 0.00834925200145951, 'mean_word_length': 4.390720814531991, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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 multi-user 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 p 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.


I. INTRODUCTION
In wireless networks, independent fading of users can be exploited for multi-user diversity. In arbitrary fading channels, the optimal user scheduling method that maximizes the sum throughput both in uplink [1] and downlink [2] is to select the user who has the largest channel gain at each time slot. Although the above scheduling method can maximize the sum throughput, it may cause a fairness problem among users located at different distances from the base station (BS) because the BS tends to select users who are closer to it more frequently due to their higher average signal-to-noise ratios (SNRs). Several approaches exist to solve the fairness problem in user scheduling. These approaches have adopted two different criteria: throughput-based fairness [3]- [7] and resource-based fairness [8]- [11]. Different systems may adopt different fairness criteria according to their design objectives. The basic idea of scheduling with throughput-based fairness is to select the user who maximizes the system throughput, while satisfying a given throughput fairness criterion. For example, the proportional fairness scheduler (PFS) [5], originally proposed in the context of game theory [12], maximizes the product of throughput of users. However, the long term average throughput of PFS cannot be derived and thus we cannot determine how much resources to allocate to each user with PFS even in stationary Rayleigh fading channels [7]. Therefore, PFS does not provide a predictable system performance. A scheduler designed to achieve throughput-based fairness in a wireless system may allow users with bad channel conditions to occupy most resources, which degrades the throughput performance of other users.
On the other hand, with resource-based fairness the required amount of resources are assigned to each user and the throughput obtained from the resources assigned to each user depends on the average SNR, channel statistics, transmission techniques, etc. Hence, the user who has a higher average SNR or a better transmission technique can achieve a higher throughput. In this paper, we focus on scheduling algorithms with resource-based fairness. The round-robin scheduling (RRS) algorithm [13] is the simplest scheduling algorithm with resource-based fairness, which can control the assignment of time fractions for user access, referred as channel access ratios (CARs) of users in this paper. However, RRS cannot exploit multi-user diversity in wireless communication systems. Another scheduling method in this category is user selection based on normalized SNR (NSNR) [14]. Due to its analytical tractability, NSNR has been extensively investigated [10], [15]. However, NSNR cannot guarantee equal CARs among users when SNR distributions of users are different from each other. Liu et al. proposed a scheduling algorithm that maximizes the sum throughput of users given their CAR requirements [8].
Moreover, several scheduling algorithms that assign channel resources to users based on the cumulative distribution function (CDF) values of channel gains have been proposed in independent studies including the CDF-based scheduling (CS) algorithm [16], the distribution fairness scheduling algorithm [17], and the score-based scheduling algorithm [18]. In CS [16], the throughput of each user can be obtained independently, and thus CS is robust to variations of system parameters such as traffic characteristics and number of users in a cell [19]. With these useful properties, CS has been studied under various network scenarios such as multi-user multi-input multi-output [20], multi-cell coordination [21], and cheating of CDF values [22]. CS was also extended to operate over heterogeneous systems where real-time and best effort traffic coexists [23]. The concept of CS was also applied to medium access control to resolve collisions as well as exploit multi-user diversity in single-hop [24] and multi-hop [25] networks. Although many studies on CS exist, the throughput characteristics of CS in cellular downlink have not been fully investigated.
For equally weighted users, all users require the same CAR, and CS selects the user with the largest CDF value among users in each time slot. When all users have the same channel statistics and average SNRs, the user selection policies of CS [16], Liu's scheduling algorithm [8] and the distribution fairness scheduling algorithm [17] are identical. However, for unequally weighted users who require diverse CARs due to different service priorities, quality-of-service (QoS), or pricing policy, etc., the user selection policies of these scheduling algorithms are quite different from each other 1 . Liu's scheduling algorithm maximizes the sum throughput of all users in a cell, while the distribution fairness scheduling algorithm maximizes the sum of the CDF values of the selected users. However, the literature gives no indication of the unique property of CS, which distinguishes it from Liu's scheduling algorithm and the distribution fair scheduling algorithm under unequally weighted users. Note that these algorithms can satisfy the CAR requirements of users but show different throughput performance. This phenomenon motivates us to reconsider the fairness aspects of these algorithms especially for unequally weighted users, because they were originally proposed to address the fairness issue when exploiting multi-user diversity. Satisfying CAR requirements of users is important in terms of resource-based fairness but it is not enough to capture all aspects of fairness among users. We need another fairness criterion to address an additional fairness aspect among users.
A primary goal of many scheduling algorithms is to exploit multi-user diversity in wireless communication systems, and thus the degree of achieved multi-user diversity for users can be another consideration for fairness. There has not been any suitable metric in previous studies on resource sharing, which measures the degree of achieved multi-user diversity. In this paper, therefore, we propose a novel fairness criterion called qualitative fairness index (QFI) to measure the degree of achieved multi-user diversity for users under the resource sharing constraints. QFI is a positive value smaller than 1 and a scheduling algorithm is considered to be well designed for fairly exploiting multi-user diversity if its QFI approaches the maximum value of 1. While we show that QFI gives a measure of the degree of achieved multi-user diversity considering unequally weighted users, we note that other measures of the degree of achieved multi-user diversity may exist.
In this paper, we investigate the fairness problem among users in two aspects: quantitative fairness and qualitative fairness. Quantitative fairness stands for satisfaction on the CAR requirements, while qualitative fairness refers to the quality of the assigned resources to users or satisfaction on the degree of achieved multi-user diversity. A fair scheduler should satisfy both fairness criteria. It has previously been shown that RRS, CS, Liu's scheduling algorithm and the distribution fairness scheduling algorithm all satisfy the arbitrary CAR requirements of users, which means that they can provide quantitative fairness among users. We further investigate the qualitative fairness aspects of these algorithms and observe that CS shows a better performance than other algorithms in terms of qualitative fairness. Hence, we can conclude that superior qualitative fairness is property that distinguishes CS from other scheduling algorithms.
In order to exploit multi-user diversity, CS requires all users to feed their CDF values back to the BS in each time slot as in other scheduling algorithms. For practical systems, the overhead of such feedbacks is a challenging issue especially when a large number of users exist in a cell. Therefore, it is of great interest to design a feedback reduction scheme for CS to reduce the number of users sending feedback in each time slot. Several threshold-based feedback reduction schemes [11], [26], [27] have been proposed for various scheduling methods such as PFS and NSNR. However, none of these schemes supports different CARs among users, as CS does. Consequently, these feedback reduction schemes cannot be applied to CS.
In this paper, we first analyze the throughput characteristics of CS, which has not been fully investigated in previous studies. For example, for Nakagami-m fading channels, we derive the analytical expression of the throughput and investigate the effects of the average SNR, the shape parameter m, and the channel access ratio on the throughput gain. We also propose a novel feedback reduction scheme for CS, which is based on a single threshold even with unequally weighted users. It is shown that the average feedback overhead of the proposed scheme is smaller than − ln p, where p indicates the probability that no user satisfies the threshold condition. Finally, we extensively investigate the fairness aspect of CS. Especially, we focus on the qualitative fairness of CS for a given CAR requirement. We show that CS yields a relatively better qualitative fairness, compared with other scheduling algorithms that can control the CARs.
The rest of this paper is organized as follows: Section II introduces the system model and reviews CS. Section III analyzes the throughput performance of CS. Section IV presents the threshold-based feedback reduction scheme and analyzes its performance. Section V introduces the concept of qualitative fairness and discusses the qualitative fairness of CS. Section VI presents the numerical results. Finally, conclusions are drawn in Section VII.

II. SYSTEM MODEL
We consider the downlink of a cell with a BS and n users. At each time slot, the BS selects one user to receive its transmission. The transmit power of the BS is assumed to be constant in each time slot. The BS and the users are each assumed to have a single antenna. In time slot t, the received signal at the i-th user is given as where y(t) ∈ C T consists of T received symbols, x(t) ∈ C T is the T transmitted symbols, h i (t) ∈ C is the channel gain from the BS to the i-th user, and z i (t) ∈ C T is a zeromean circular-symmetric Gaussian random vector (z i (t) ∼ CN (0, σ 2 I T )). C denotes set of complex numbers and I T denotes the identity matrix of size T . The transmit power of the BS is set to P , i.e., E[|x(t)| 2 ]/T = P . We assume a blockfading channel where the channel gain is constant during T symbols and independently changes between time slots. Different users may have different channel statistics. The received SNR of the i-th user is given by γ i (t) = P |h i (t)| 2 /σ 2 . Let F i (γ) denote the CDF of the SNR of the i-th user, which can be obtained from long-term observations by the user. In each slot, the BS transmits training signals to facilitate the users' observations on the CDF. If we consider F i (γ) as a general function of γ and define the corresponding output value as U i = F i (γ), U i is also a random variable which is transformed from γ through function F i (γ In this paper, we assume that all users' channels are stationary and the channel statistics of each user are assumed to be independent from those of other users. Equation (2) indicates that all users' CDF values have the same uniform distribution while their CDFs may not be identical 2 . CS exploits this property in fair multi-user scheduling.
Let w i (> 0) denote the weight of the i-th user. The weight indicates the user's CAR compared to other users, which means that the ratio between the i-th and j-th users' channel access opportunities is given by w i /w j . If there are n users in the system, the i-th user's CAR is α i = wi n j=1 wj . With CS, the feedback information of the i-th user is [F i (γ i (t))] 1 w i at time slot t and the index of the user selected at the BS is given by arg max i∈{1,2,...,n} It has been shown in [16] that this scheduling algorithm yields a CAR of α i for the i-th user. Note that with CS, the users are in charge of observing the CDFs through long-term observations and calculating the CDF values for feedback in each time slot while the BS only compares the information sent from the users in each time slot and does not need to know all users CDFs.

III. THROUGHPUT CHARACTERISTICS OF CS
In order to investigate the throughput performance of CS, we first analyze the SNR distribution of the selected user. We start with the following lemma.
Lemma 1: Let F (γ) be the SNR distribution of a user and α(∈ [0, 1]) be the CAR of the user. With CS, the SNR distribution of the user given it is selected is expressed as: Proof: Let (w 1 , w 2 , ..., w n ) be the weight vector of n users. The i-th user feeds back the value of [F i,t (γ i (t))] 1 w i to the BS. Then, the feedback information received at the BS in each time slot is given by (U n ) and the BS selects the user with the largest value of the feedback information. Then, the probability that the i-th user is selected is given as: (5) Thus, the CAR of the i-th user is given by α i = w i / n j=1 w j . If all users have identical weights, the CAR of each user is equal to 1/n. The SNR distribution of the i-th user given it is selected is expressed as: To investigate the throughput behavior of CS, we first define the following function: where x and α are values taken in [0, 1], F (γ) is the SNR distribution, which is an increasing function of γ, F −1 (x) is the inverse function of F (γ), and R(γ) is the data rate function corresponding to the instantaneous SNR value. We assume R(γ) is an increasing function of γ since a higher SNR enables a higher data rate in general. If S(x, α) < ∞, we can obtain the following properties and we will use them to find the interesting throughput behavior of CS later.
For a given CAR of a user α, we define throughput gain (g CS ) as the throughput ratio of CS to RR. Based on Properties 1 and 2, we obtain the following result.
Theorem 1: With CS, the throughput of a user experiencing arbitrary stationary fading channel increases as its CAR increases, but the throughput gain decreases as the CAR increases.
Proof: Let α and F (γ) be the CAR and the SNR distribution of a user, respectively. The throughput of the user with CS is given as: Applying Property 1 with x = 0, we can observe that S CS is an increasing function of α. In other words, the throughput decreases as the CAR decreases. In practice, the CAR decreases as the number of users increases in a cell. Similarly, the throughput of the user with RRS is given as: where E[R] indicates the average data rate for the user, defined as S(0, 1) from (1). The throughput gain is expressed as: From Property 2 with x = 0, the throughput gain increases as the CAR decreases. Furthermore, if we apply Property 2 with x = 0, then we can also observe that S CS is larger than S RRS , which means that CS always provides a higher throughput than RRS; i.e., the throughput gain is always larger than 1. Although CS provides a better throughput performance than RRS, it does not guarantee the optimal throughput for a given CAR. For example, we consider the cellular downlink where there exist two users in the cell and the channel of the first user is Rayleigh distributed, while the channel of the second user is constant. Both users are assumed to have the same CAR, which is equal to 1/2. Since the achievable data rate of the second user is constant at any time, the throughput of the first user is maximized when the BS selects it if F 1 (γ 1 ) > 1/2 where γ 1 denotes the SNR of the first user. For a given CAR, the optimal throughput of a user is obtained by the following lemma 3 : Lemma 2: Let F (γ) and R(γ) be the SNR distribution and the data rate function of a user, respectively. For a given CAR requirement α, the throughput of the user is upper bounded by Proof: See Appendix B. The above lemma implies that, for a given CAR of α, the optimal scheduling algorithm in terms of throughput is to select the user with SNR such that F (γ) ≥ 1 − α. Based on Properties 3 and 4 with x = 1 − α, we observe that the throughput upper-bound decreases as the CAR decreases. We define another throughput gain as: The throughput gain of the upper-bound in (12) increases as the CAR decreases. The following theorem states the throughput relationship between CS and the optimal scheduling algorithm: Theorem 2: If the supported data rate of a user has a maximum value, the throughput of CS approaches the throughput upper-bound as the CAR decreases to zero. In other words, for a given condition that R(γ) = R th for γ > γ 0 , we obtain Proof: See Appendix C. In practice, the supported number of levels of the modulation and coding scheme (MCS) is finite and the maximum data rate is limited. Hence, CS can achieve the throughput upperbound as the CAR tends to zero. If the data rate function has no upper limit, then the throughput of a user with CS yields the following behavior: Theorem 3: For a given CAR requirement α and no upper limit for the data rate function, the throughput of CS is upperbounded by S UB (α) and is lower-bounded by: Furthermore, if lim α→0 S UB (α) = 0, the throughput gain of CS has the following characteristics: If lim γ→∞ R(γ) = ∞, then the throughput gain g CS (α) tends to infinity as α decreases to zero. Proof: See Appendix D. According to Theorem 3, an SNR distribution with large values of F −1 (1 + α ln α) and F −1 (1 − α) yields a high throughput gain with CS when the CAR is small enough. Fig. 1 shows the CDF of the received SNR of a user in Nakagami-m fading channel when the average SNR is set to 0 dB. When α is small enough, for the example where α = 0.1 in the figure, both F −1 (1 + α ln α) = F −1 (0.77) and F −1 (1 − α) = F −1 (0.9) become smaller as the shape parameter m increases, which means that the throughput gain of CS decreases as the shape parameter increases. On the other hand, the outage probability, which is the performance metric of interest in many wireless systems, decreases as the shape parameter increases. If we set the SNR threshold for the outage to 0.5 in the figure, the outage probability decreases from 0.39 to 0.02 as the shape parameter m increases from 1 to 10. Thus, there is a tradeoff between low outage probability and high throughput gain. For a representative example, in the rest of this section, we analyze the throughput of a user with CS in Nakagami-m fading channels. We assume the data rate function as R(γ) = log 2 (1 + γ), which is the Shannon capacity. In Nakagami-m fading channels, the SNR distribution of a user follows the Gamma distribution whose probability density function (pdf) is given as: where m denotes the shape parameter, γ denotes the average SNR, and Γ(m) indicates the Gamma function defined as ∞ 0 e −y y m−1 dy. If m is a positive integer, the corresponding CDF is expressed as: If K = 1 α and K is an integer, by extending the analysis in [10], the universal throughput function, S(x, α), can be expressed as: where the term γ th is the SNR satisfying F m,γ (γ th ) = x, the term c(j, k) is defined as: and the term T (γ th , j, θ) is defined as: where the exponential integral function of the first kind is defined as E 1 (y) = ∞ y e −t t dt. Thus, based on (19), the values of S RRS (α), S CS(α) , and S UB (α) can also be obtained.
It is well known that a larger number of users result in a higher multi-user diversity. Conventionally, this phenomenon has been observed by investigating the increasing scale of the sum throughput when the number of users increases to infinity in cellular systems [5], [28], [29] and cognitive networks [30], [31]. The increasing scale represents how fast the throughput increases as the number of users in a network increases. Since we consider resource-based fairness in this paper, we alternatively investigate the increasing scale of the throughput gain of each user when the number of users increases to infinity or, equivalently, the CAR decreases to zero. The inverse function of F m,γ (γ) is given as [9]: When α approaches to 0, the upper-and lower-bound of the throughput gain with CS is given as in Nakagami-m fading channels. Therefore, extending Theorem 3, we have the following remark: Remark 1: In Nakagami-m fading channels, the throughput gain of CS increases with the optimal scale of as α decreases to zero. With equally weighted users, the increasing scale is given by log 2 e·ln ln(n)

E[R]
as n increases to infinity, where n indicates the number of users in a cell.
If the term ln ln( 1 α ) is not large enough, the value ln( γ m ) also affects the throughput gain as shown in (23) and (24), i.e., the effect of the average SNR γ and the shape parameter m is not negligible. In this case, we have the following remark: since the effect of m on the throughput gain is negligible. Moreover, if γ → ∞ and ln γ ≫ ln ln( 1 α ), we have g UB ≈ g LB ≈ log 2 (γ) E[R] ≈ 1. Thus, no throughput gain is expected in the high SNR regime. On the other hand, if γ is not large enough, the shape parameter m may affect the throughput gain. A larger shape parameter reduces the throughput gain of CS as shown in (23) and (24).

IV. FEEDBACK REDUCTION FOR CS
CS requires all users to feed their CDF values back to the BS at each time slot, which may cause severe feedback overhead as the number of users in a cell increases. Several thresholdbased feedback reduction schemes [11], [26], [27] have been proposed for various scheduling algorithms such as PFS and NSNR. However, none of these schemes supports different CARs among users, as CS does. Consequently, these feedback reduction schemes cannot be applied to CS. In this section, we propose CS-FR, a novel feedback reduction scheme for CS, to reduce the feedback overhead. To the best of our knowledge, CS-FR is the first feedback reduction scheme that considers diverse users who require different CARs in scheduling.

A. Threshold Design and Channel Access Ratio
For equally weighted users in a cell, since all users send feedback information that is identically and uniformly distributed between [0, 1], we can simply set the same threshold η th for all users to achieve the identical CAR. If the feedback information of the i-th user, U i , is larger than η th , the i-th user sends U i to BS. If no user satisfies the condition, the BS does not receive any feedback information from the users and it selects a user in a RRS manner. When no feedback happens in the slot, we call such a slot a no-feedback (NFB) slot. We further define a slot in which more than one users send feedback to the BS as a feedback (FB) slot. For unequally weighted users, the difficulty in determining the thresholds is to satisfy the CARs in both FB and NFB slots. Intuition tells us that different users may have different threshold values due to their different weights. However, we show in the following theorem that it is possible to satisfy the CARs of different users with the same threshold η th for all users.
Theorem 4: The CARs of the users with CS-FR are still maintained if the threshold of all user is set to p 1/ n j=1 wj , where p and w j denote the NFB probability and the weight of the j-th user, respectively.
Proof: Given the threshold η th for all users, the i-th user feeds back the value U 1 w i i if it is larger than η th . With this setting, we show that the CAR of the i-th user in the NF slots is equal to α i = wi n j=1 wj . With the proposed threshold setting for CS-FR, the NFB probability is given by: For a given NFB constraint p, the threshold η th can be set to p 1/ n j=1 wj . Hence, the selection probability for the i-th user in each FB slot is Pr{user i is selected|FB slot} = Pr{user i is selected, the slot is FB slot} In the NFB slots, the users are selected with RRS (or random scheduling) so that the CAR α i for the i-th user is still maintained. Thus, the total CAR for the i-th user is Note that we do not assume any specific channel distribution in Theorem 4 and it can be applied to any channel distribution. Notably, selecting the same threshold value for all users who have different CARs substantially simplifies the system design and implementation.

B. Feedback Overhead
In this subsection, we consider the average feedback overhead with CS-FR.
Theorem 5: With CS-FR, the average feedback overhead in each slot is upper-bounded by n 1 − p 1 n , where p denotes the NFB probability. The equality holds when all users are equally weighted. Another upper-bound of the feedback overhead is given by − ln p, which is valid regardless of the number of users and the weights of users.
Proof: For the i-th user, the average feedback overhead in each slot is given as: The average feedback overhead in each slot in a cell is given as: Since f (x) = p x is a convex function of x in a region 0 < p < 1, we have The equality holds when α 1 = α 2 = ... = α n , i.e., all users have the same weight. Using the fact that x(1 − p 1 x ) is an increasing function over x for x > 0 and 0 < p < 1, and

C. Throughput analysis
In order to analyze the throughput characteristic of CS-FR, we first investigate the SNR distribution for a user given that it is selected.
Theorem 6: With CS-FR, if a user's SNR distribution is F (γ), its CAR is α ∈ [0, 1], and the NFB probability is p, the SNR distribution given this user is selected is obtained as Proof: See Appendix E. We also define the following throughput function for analyzing the throughput of CS-FR.
Proof: See Appendix A. Based on (32), the throughput of CS-FR is calculated as We can observe that the throughput of any user depends on its CAR α and the NFB probability p and is independent from other users. From Property 6, we can conclude that S CS−FR is an increasing function of p. Hence, there is no optimal threshold for CS-FR and, in order to obtain a higher throughput, we should reduce the value of p. When p = 0, CS-FR is identical to CS while CS-FR is identical to RRS when p = 1. Thus, CS-FR always shows a better throughput performance than RRS and a worse throughput performance than CS. Compared to CS, the lower-and upper-bound throughputs of CS-FR are characterized by the following theorem: Theorem 7: The lower-and upper-bound of S CS−FR (α, p) are given as Proof: For the proof of the lower-bound, see Appendix F, which applies Properties 4 and 5. The upper-bound can be obtained from Property 6 where the case of x = 0 stands for S CS (α).
From the lower bound, we can conclude that the throughput loss ratio of CS-FR to CS is smaller than the NFB probability p. Note that Theorem 7 is applicable to any data rate function and channel statistics. Theorem 5 and Theorem 7 lead to the following remarks for CS-FR: Remark 3: 1) There is a tradeoff between throughput and feedback overhead. A larger feedback overhead gives a higher throughput because they are both decreasing functions of p.
2) The feedback overhead is upper-bounded by the negative natural logarithm of the throughput loss ratio, i.e., if each user can tolerate the throughput loss of at most p compared to CS, we can design CS-FR with the average feedback overhead smaller than − ln p.
In the case of Nakagami-m fading channels, we can apply (19) to derive the throughput performance of CS-FR.

V. FAIRNESS ASPECT OF CS
Although CS satisfies the CAR requirements and has interesting properties as discussed in Sections III and IV, the specific property of CS that distinguishes it from Liu's scheduling algorithm and the distribution fairness scheduling algorithm, both of which also satisfy the CAR requirements of users, has not been considered in the literature. In this section, we compare the fairness aspects of those algorithms as they were all proposed for fair resource assignment in multi-user systems. Before we investigate the fairness aspect in detail, we first introduce Liu's scheduling algorithm [8] and the distribution fairness scheduling algorithm [17]. In Liu's scheduling algorithm, BS selects a user in each slot by using the following criterion: arg max i∈{1,2,...,n} where the offset c i is determined in order to satisfy the given CAR requirements. Liu's scheduling algorithm maximizes the sum throughput for the given CAR requirements of users. In the distribution fairness scheduling algorithm, the BS selects a user in each slot by using the following criterion: arg max i∈{1,2,...,n} where the offset d i is determined in order to satisfy the given CAR requirements. The distribution fairness scheduling algorithm maximizes the sum of the CDF values of the selected users. All of CS, Liu's scheduling algorithm, and the distribution fairness scheduling algorithm satisfy the CAR requirements, but they result in different throughput performance to users because of their diverse user selection policies. Note that these three algorithms were originally proposed to address the fairness issue when exploiting multi-user diversity in wireless communication systems. If fairness is defined as the satisfaction of the CAR requirements, all three algorithms are equally fair. However, the different throughput performance of these algorithms motivates us to reconsider the fairness issue for the scheduling algorithms that can satisfy the CAR requirements. While CAR is apparently an important fairness criterion, it is not enough to capture all aspects of fairness among users. On the other hand, the degree of achieved multiuser diversity can be another consideration for fairness of users. A fair scheduling algorithm may aim at an identical degree of multi-user diversity for all users. Users may feel unfair if the degrees of achieved multi-user diversity of users are different, even though users satisfy their required CARs. In characterizing the degrees of achieved multi-user diversity, we take the following two considerations: • Exploiting multi-user diversity means that the BS selects a user when its channel has a high quality. Hence, a criterion to measure the quality of assigned resource is required. The CDF value of SNR is a possible candidate because it represents the quality of the channel gain with a real number in [0, 1] and it is independent on the average SNRs and the SNR distributions. We define D(α) as the average CDF value of a user given that the user is selected, and it represents the quality of the assigned resource in this paper. Then, it is expressed as where F sel (γ) is the SNR distribution given that the user is selected. A larger value of D(α) indicates a better quality of assigned resource in the average sense. SNR itself (or data rate achieved from the assigned resource) cannot be the index of quality of assigned resource because different users have different average SNRs and different SNR distributions. Thus, directly comparing the SNR values of users results in unfairness among users. • It is well known that a larger number of users in a cell provides a higher multi-user diversity. Since a larger number of users can be interpreted as a smaller CAR for each user, a user with a smaller CAR has a higher potential of exploiting multi-user diversity. Therefore, we take into account the different potentials from the different CARs of users. Lemma 2 gives us a guideline for characterizing this potential. It tells us that the best quality of assigned resource for a given CAR α is obtained by selecting the user whose SNR is larger than F −1 (1 − α). Let D UB (α) denote the upper-bound of the average CDF value obtained by this optimal scheduling algorithm, which is given as and obtained by replacing R(γ) by F (γ) in (11). The closeness of D(α) to D UB (α) means a higher degree of multi-user diversity is achieved. Hence, we define the degree of achieved multi-user diversity for a user as the ratio of D(α) to D UB (α). It is expressed as: The upper-bound in (40) can be obtained by simply replacing R(γ) by F (γ) in Appendix B. Given the CAR requirement α of a user, I D (α) represents the degree of achieved multiuser diversity with scheduling. A fair scheduling algorithm should provide similar values of I D for all users in spite of their diverse CAR requirements. If I D (α) approaches 1, we can consider that the scheduling algorithm optimally exploits multi-user diversity. Since the primary objective of the scheduling algorithms considered in this paper is to exploit multi-user diversity, a good scheduling algorithm also maximizes all users' I D values, i.e., maximizes I D,min = min i∈{1,2,...,n} A good scheduling algorithm not only provides similar values of I D for all users, but also maximizes I D,min . We define I D,min as the QFI of a scheduling algorithm in this paper. It is notable that a QFI around 1 implicitly means that the I D values of all users are similar to each other because they have to be larger than I D,min and smaller than 1 by definition. For systems with diverse users who require different CARs, now we can investigate the fairness among these users by utilizing two aspects: quantitative fairness and qualitative fairness. Quantitative fairness indicates the satisfaction of users CAR requirements, while qualitative fairness refers to the satisfaction on the quality of the assigned resources to users. Qualitative fairness is closely related to the degrees of achieved multi-user diversity for users. A fair scheduler should satisfy both criteria as much as possible. Note that QFI in (41) is not the only fairness criterion to measure the degree of achieved multi-user diversity, but is one possible candidate which is considered in this paper.
Theorem 8: If the CAR of a user is α, the degree of achieved multi-user diversity with CS is given by Proof: For a user with CAR of α, the average CDF value given the user is selected with CS is calculated as Consequently, the corresponding I D value is calculated as It is easy to check that all the scheduling algorithms considered in this section strictly satisfy quantitative fairness, but provide different qualitative fairness defined in (40) due to their different user selection policies. We shall investigate the qualitative fairness of these scheduling algorithms in more detail in Section VI.

VI. NUMERICAL RESULTS
We first investigate the throughput and fairness aspects of CS, Liu's scheduling algorithm and the distribution fairness scheduling algorithm. From the user selection policies of the scheduling algorithms shown in (3), (36) and (37), we can easily check that they show identical throughput performance when all users have the same CAR requirement, experience the same fading channel, and have the same average SNR. To investigate their differences, we first consider a system with two asymmetric users: one user experiences a Rayleigh fading channel and the other experiences an Nakagami-m fading channel with m = 4. The average SNR of both users is set to 0dB and the sum of their CARs is 1. Fig. 2 shows the sum throughput performance when the CAR of the first user is varied. We can see that all the algorithms show better throughput performance than RRS.
Liu's scheduling algorithm shows the best sum throughput performance as it is designed for maximizing sum throughput. However, it does not mean that Liu's scheduling algorithm maximizes individual users' throughput, which will be observed from Fig. 3. Moreover, although there exists some differences, the CDF-based scheduling, Liu's scheduling algorithm and the distribution fairness scheduling algorithm show similar sum throughputs. Fig. 3 shows the throughput gain of each user when the user's CAR is varied. Note that the x-axis label in Fig. 3 is the CAR of the user being observed but not the first user's CAR. As all the algorithms' throughput gains are larger than 1, they always show better performance than RRS. Moreover, the throughput gains of Liu's and the distribution fairness scheduling algorithms also increase as the CAR decreases, which is the property of CS shown in Theorem 1. We can see that CS shows a better throughput gain performance than Liu's and the distribution fairness scheduling algorithms when the user's CAR becomes smaller. When a user's throughput gain of CS is larger than that of Liu's scheduling algorithm, the other user's throughput gain of Liu's scheduling algorithm should be larger than that of CS since Liu's scheduling algorithm maximizes sum throughput. Hence, Liu's scheduling algorithm does not always provide the best throughput performance for all users. As the throughput performance of CS is independent from the number of users contending for the channel and other users' channel statistics as indicated by (8), the results of CS shown in Fig. 3 are also valid for any stationary system where there exists a user experiencing Nakagami-m fading with m = 1, 4 and having the average SNR of 0dB.
From Fig. 3, we can observe that the throughput gain of CS is very close to the upper-bound. Although we did not include the figure, we have also investigated the ratio between the throughput of CS and the throughput upper-bound. CS can achieve at least 88% and 93% throughput performance compared to the upper-bound when m = 1, 4, respectively, for all values of the channel access ratios in [0, 1]. When the average SNR is set to 10dB, it is observed that CS achieves at least 91% and 95% throughput performance compared to the upper-bound throughput when m = 1, 4, respectively.
In order to investigate the fairness aspects, we plot Fig. 4, which shows the respective values of I D for RRS, CS, Liu's scheduling algorithm and the distribution fairness scheduling algorithm when the CAR requirements of the first and second users are 0.7 and 0.3. In this scenario, we can observe that Liu's and the distribution fairness scheduling algorithms favor the first user in exploiting multi-user diversity, whereas CS enables both users to exploit multi-user diversity in a more balanced manner. As discussed in Section III, Rayleigh fading provides a higher throughput gain compared to Nakagami-m fading channel with m = 4. Hence, the first user is able to better exploit multi-user diversity and contribute more additional throughput than the second user with Liu's scheduling algorithm, which aims to maximize the total throughput under the CAR constraints. This is why Liu's scheduling algorithm shows the largest gap between the two users among the scheduling algorithms considered. As expected, RRS shows the worst performance. As RRS does not exploit multi-user diversity, D(α) is always constant at 1/2. Since D UB (α) decreases as α increases, the first user who requires a higher CAR shows a better I D (α) value than the second user. Fig. 5 shows the values of I D,min for CS, Liu's scheduling algorithm, the distribution fairness scheduling algorithm and RRS for varying CAR of the first user. CS yields relatively good qualitative fairness for any CAR requirement as shown in Fig. 5. Notably, CS shows a predictable lower-bound of I D,min , 8/9, as proven by Theorem 8 while neither Liu's scheduling algorithm nor the distribution fairness scheduling algorithm can guarantee any lower-bound of I D,min , which varies over the number of competing users and the users' CAR requirements. From the viewpoint of qualitative fairness, RRS shows the worst performance as it does not exploit multi-user diversity and the value of I D,min ranges between [ 1 2 , 2 3 ].   6 shows the throughput gains of the two users with CS, Liu's scheduling and the distribution fairness scheduling algorithm when both users' average SNRs varied from 0dB to 20dB and the CAR is set to 0.1 for the user being observed. The throughput gain decreases as the average SNR or the shape parameter increases as shown in Remark 2. We can observe the tradeoff between CS and Liu's scheduling algorithm over different SNRs and CARs. Fig. 7 shows the average feedback overhead for when the NFB probability is varied from 0 to 1 and all the users are equally weighted. The average feedback overhead is defined as the number of users who send feedback information to the BS. The feedback overhead of CS-FR decreases as the NFB probability increases. From the figure, we can observe that a large feedback overhead is required as the number of users in a cell increases for a given NFB probability. If the NFB probability is 2%, i.e., p = 0.02, the average feedback overhead are 2.71, 3.24, 3.84, and 3.91 when there are 5, 10, 100, and ∞ users in a cell, respectively. Fig. 8 shows the feedback overhead ratios with equally weighted users when the NFB probability is varied from 0 to 1. The average feedback ratio represents the ratio of the average number of users sending feedback information to BS with CS-FR over the total number of users. Note that this equally weighted case yields an upper-bound for the unequally weighted case as discussed in Section IV-B. From the figure we can observe that a larger NFB probability reduces the feedback overhead more significantly. If the NFB probability is 2%, i.e., p = 0.02, the average feedback ratio is equal to 54.3%, 32.4%, and 3.8% when n = 5, 10, 100, respectively. Therefore, for given a NFB probability, CS-FR reduces the feedback overhead significantly as the number of users increases. Fig. 9 shows the throughput gain of CS and CS-FR for varying 1/α. For equally weighted users, 1/α is equal to the number of users in the system. The average SNR of the user being observed is set to 0dB. We can observe that the throughput gain of CS-FR increases as 1/α increases and a larger NFB probability reduces the throughput gain with CS-FR. In Nakagami-m fading channels, CS-FR yields a larger throughput gain with small m compared with CS since users experiencing more channel fluctuations obtain a higher throughput gain compared to a user with less fluctuations. Fig. 10 shows the throughput gains of CS-FR for various NFB probabilities over a Rayleigh fading channel, which is a special case of a Nakagami-m fading channel with m = 1, with the average SNR = 0dB. We can observe that a smaller CAR and a smaller NFB probability yield a larger throughput gain. Fig. 11 shows the throughput ratio between CS-FR and CS in the same environment. We can observe that a smaller CAR yields a smaller value of throughput ratio. Thus, if CS-FR is applied, a user with a smaller CAR is more prone to a throughput loss compared to a user with a larger CAR. A similar trend can also be observed from the lowerbound throughput of CS-FR shown in (35) since the formula, 1 − p + αp 1−α , is an increasing function of α.

VII. CONCLUSIONS
In this paper, we have investigated the fundamental performance limits of CS in terms of throughput, fairness, and feedback overhead. We have rigorously characterized the  throughput behavior of CS. The throughput upper-bound of general schedulers for a given SNR distribution, data rate function, and channel access ratio has been derived and CS has been proven to achieve the upper-bound when the data rate function has the upper limit and the CAR decreases to zero. The lower-and upper-bound of the throughput gain with CS have also been analyzed. We have further proposed CS-FR, a novel feedback reduction technique for CS. With CS-FR, a single threshold is sufficient to satisfy the diverse CARs of all users, and the feedback overhead is upper-bounded by − ln p where p represents the probability that no user satisfies the threshold condition. We have also investigated the throughput characteristics and observed that the throughput loss due to feedback reduction relative to the throughput with full feedback is upper-bounded by − ln p. Finally, we have proposed the concept of qualitative fairness in order to more thoroughly investigate fairness among various schedulers, and shown that CS achieves relatively better qualitative fairness, compared with the other existing scheduling algorithms.
(48) The second inequality comes from the increasing property of R(γ).

F. Proof for Property 6
For the decreasing property, we show that the derivative of the function is smaller than or equal to 0.
where the inequality comes from the increasing property of the functions R(γ) and F (γ).

APPENDIX B PROOF OF LEMMA 2
Let g(γ) (0 ≤ g(γ) ≤ 1) be the selection probability where γ indicates the SNR of the user. The CAR is equal to α and we have ∞ 0 g(γ)dF (γ) = α.

APPENDIX E SNR DISTRIBUTION OF THE SELECTED USER WITH CS-FR
Given that the i-th user is selected, its SNR distribution in the NFB slots is derived as F i,Sel,NFB (γ) = Pr{γ i < γ|user i is selected, the slot is a NFB slot} = Pr{γi<γ,user i is selected, the slot is a NFB slot} Pr{user i is selected, the slot is a NFB slot} = αi Pr γi<γ, U where we have used the fact η wi th = p αi from (25). The SNR distribution in the FB slots is derived as F i,Sel,FB (γ) = Pr{γ i < γ|user i is selected, the slot is a FB slot} = Pr{γi<γ,user i is selected, the slot is a FB slot} Pr{user i is selected, the slot is a FB slot} = Pr{γi<γ, U if γ ≥ F −1 i (p αi ).