Joint Throughput Maximization and Fair Uplink Transmission Scheduling in CDMA Systems

The corresponding constraints in terms of the power index can be represented as follows:

Note that in the objective function we represent the rate as a function of power index , where

which converts the power index into transmission rate and can be easily derived from (14) by replacing with .

In the following, let denote the set that contains all the power and rate vectors that satisfy constraints (7) and (8) and . The elements and represent the transmit power and rate of the th user in the th vector. Similarly, we define another set containing the power and rate vectors that satisfy constraints (19), (20), and (21). By definition, it is obvious that any power and rate vector is feasible. However, since in constraint (21), may take a value, that is, close to 1 , the required transmit power could also accordingly become larger than maximum allowable transmit power if we simply look at the result from (15). The following proposition states that if perfect power control is assumed, for any rate (or power index) vector that satisfies constraints (19), (20), and (21), there always exists a feasible transmit power vector.

Proposition 2.

If the power index assignment for all backlogged users satisfies constraints (19), (20), and (21), there always exists a feasible transmit power assignment, that is, for .

Proof.

Let vector be the power index vector that satisfies constraints (19), (20), and (21). Denote the sum of all power indices in vector . From the definition of power index capacity, the power index capacity of each user is and . Based on Definition 1 and (17), we have the following relation:

Hence, for any user , the transmit rate may be chosen within range

which still satisfies the above inequality and proves this proposition. The power control of the CDMA system will choose the minimal transmit power, that meets the required SINR.

The following proposition proves that the two sets and contain the same elements, which means that (19), (20), (21) and (7), (8) impose the same constraints over our problem.

Proposition 3.

Any vector is also included in set , while any vector is also included in set .

Proof.

Suppose that , and therefore it satisfies constraints (7), (8). It is apparent that . Since, as shown earlier, constraints (7), and (8) can also be represented by (13) [25], also satisfies (13). Using function (22), we can convert the rate vector into the corresponding power index vector . Let . For a feasible power and rate vector, with known ( [25]), we can find each user power index capacity . Since satisfies (13), based on Proposition 2 and the definition of power index capacity, we conclude that . That means that the assigned powers and rates in also satisfy the constraints (19), (20), and (21). Therefore, .

Let us consider vector . As before, the rate vector part can be converted to corresponding power index vector . Let and hence due to constraints (19), (20), and (21). Note that for the case where , . Based on the previous discussion, we can easily conclude that the power vector is feasible. Therefore,

which satisfies (13)), for user , . Therefore, .

The above proposition shows that the optimal solution can also be obtained with the new constraints since they define the same solution set. Please note that, as mentioned before, the fairness constraints in the original problem are replaced by parameters . The choice of the proper values of that maintain fairness is discussed in detail later in this paper.

Among the new constraints, the right-hand sides of inequalities (19) and (20) are not fixed values, but are functions of the selected target system load . Hence, whether or not the final solution is feasible also depends on the choice of . For any value of , there could be many feasible solutions among which one will be the optimal. Moreover, there must exist an optimal system load that can achieve the overall best solution. It is natural to regard the objective as the function of system load , , and thus is the local optimal result at some specific . The maximum is achieved when . The ultimate objective of the proposed method is to find this optimal and the optimal power index assignment vector under it.

In Sections 3.2 and 3.3, we propose a two-step approach to solve the optimization problem (17)–(20). More specifically, in the first step (Section 3.2), we assume a fixed and then given that fixed parameter we propose a simple method (greedy algorithm) trying to find the optimal set of users to receive service. However, this optimality is not a global optimality. In general, as mentioned before, could get any value within the interval . The global optimal solution can be obtained when parameter is chosen to be the optimal one . The actual objective of the second step of our approach (Section 3.3) is to find this optimal , by which the global optimal set of users that will be scheduled to receive service can be identified.

Before obtaining the best system load, we first discuss how to find the local best solution. Assuming that the value of is known, the right-hand sides of (19) and (20) can be determined. Combining the two constraints together, we can express the optimization problem (18) by replacing with , as follows:

Note that (26) is a nonlinear continuous knapsack problem with the taking continuous values between 0 and 1. In general, solving this type of problem is proven to be difficult or even impossible in some cases [27]. However, Proposition 1 limits the transmit power of a user , to either or for the optimal solution. This condition provides a possible method to solve the above nonlinear knapsack problem. Without loss of generality, we suppose that the optimal solution is when the first users transmit at their maximum power, , . The optimal system load is . The following theorem states that the power index of an individual user is equal to its power index capacity under , that is, .

Theorem 1.

Let the optimal solution allow users to transmit at their maximum power and the system achieves the system load . The power index that an individual user received in this case is equal to its power index capacity, that is, .

Proof.

For those users whose transmit powers are zero, the corresponding power index capacities are also zero. Therefore, their power indices are zero as well. Without loss of generality, we assume that the users under consideration are identified as follows: . Based on Proposition 1, we have

Performing some manipulations in these equations, we have

Letting , we obtain as

From the definition of power index capacity, we find that .

With reference to the optimal solution of problem (26), we can prove the following theorem.

Theorem 2.

The optimal solution of the constrained optimization problem (26) can be obtained by solving the following linear 0-1 knapsack problem:

Proof.

Since for user , we present the objective function of (26) as follows:

Based on Proposition 1, we know that the optimal solution is achieved when the transmit power of a user is either or . According to Theorem 1, in terms of power index that means that users are assigned either their power index capacity or 0 for the chosen system load . In the above relation (31), the solution for is either 1 or 0. Therefore, we can modify (31) as follows without changing the final optimal solution:

where .

Instead of solving for the optimal solution of the above integer knapsack problem (30), which is in principle NP-hard, we utilize a greedy algorithm (GA) in order to obtain an approximate solution. Let denote the result achieved by the approximate solution, while and denote the corresponding results of the optimal solutions for the integer and continuous knapsack problems, respectively. It has been proven that [28]. Furthermore, let

which is a constant value for an individual user. Let us further suppose that all backlogged users are sorted in descending order according to , that is, for . If it is not the case, these values can be sorted in time through an efficient procedure. Thus, the optimal continuous solution of problem (30) is given by

An algorithm that finds the critical point within time in a system with users is provided in [28]. Based on solution (34), the greedy algorithm (GA) obtains the approximate solution as follows:

where

It has been shown in [28] that in worst case . Let represent the result that corresponds to the integer solution of (32) when is assigned a value from , and be the result when . From the definition of , we know that is the maximum value among all , that is, . Based on Proposition 1 and the analysis in the previous subsection, it is easy to find that    . Therefore, when the optimal system power index is chosen, . Since and the equality holds only when , and the optimal solution can be obtained.

As we discussed in the last subsection the optimal solution of problem (26) depends on the selected system load . Relation (17) shows that the power index capacity increases as decreases. At the first point when , the power index capacity reaches its largest value and then it decreases linearly following the value of . Although a smaller value of may increase the single user power index capacity at some range, the finally achieved objective function could be low due to the small system load . On the other hand, setting large reduces the individual user power index capacity as (17) indicates. The consequence of smaller power index capacity is that more users are required to share , and probably a small objective function should be used due to the concavity of function that converts the power index to throughput. Therefore, whether or not the objective function reaches its maximum value depends not only on the value of the system load , but also on how it is shared among the candidate users. There must exist an optimal value of system load that can achieve the maximum weighted rate.

Let the power index vector denote the optimal solution, which can be found through the method described in the previous section for a given specific value of . Apparently, is a function of . The objective function (18) is the sum of individual weighted rates that are obtained from using function . Therefore, can also be regarded as a function of . Let be the function that gives the maximum value of the sum of weighted rates at . Then the original optimization problem can be rewritten as follows:

The optimal solution of the above problem and its corresponding power index assignment by (34) with provides the final optimal solution of (18).

Problem (37) is a simple unconstrained maximization problem that searches for the maximum within the interval . The disadvantage of (37) is that it does not have an explicit expression. Hence, algorithms that rely on the first- or second-order derivatives will not be applicable in this case. Therefore, the searching process depends on the result of (34). Note that every time when a new value of is chosen, the order of may be different from that of previous .

The time of calculating the best result for a newly chosen , including the time of reordering the users (if needed), is easily obtained as if is assumed to be large enough. Moreover, there are many possible local maximum points within the range . The final optimal must be a global best value. Although in [29] many searching algorithms on how to locate the minimum/maximum solution within a range are described, to make these algorithms effective there must be only one extreme point in the specified range. However, in general it is not possible to know the range which contains only the global optimal value. Thus, an exhaustive search within would be needed. However, the following proposition provides a lower bound with respect to the searching range instead of 0 in order to restrict the corresponding feasible searching range.

Proposition 4.

The lower bound of the feasible searching range is given by

Proof.

With the decrease of the target system load , the individual power index, provided by (14)), will keep increasing till reaches the point for user , that is . With respect to user , if its power index . is given by , which varies with different users since their are not likely the same. Let be the minimum among all 's. Once all backlogged users will have the same power index capacities . Define a small increment and let . Apparently, for all users their power indices will all have small increment such that . Maintaining the previous power index assignment and giving to any backlogged user will help increase the objective function (18). We hence can keep adding to till it reaches , which proves this proposition.

Since the optimal can reside between and , we need to calculate a series of sample values after every interval . Apparently, the smaller the the more samples we get and thereby the more accurate is the obtained result. On the other hand, it also increases the required computational time and power.

Therefore, in practice we only use reasonably small in order to reduce the corresponding computational power and complexity, while still obtain a good approximation of the optimal solution. It should be noted though that in theory when becomes infinitely small the above methodology can be used to find the optimal solution. Specifically, there exists an algorithm with complexity of that guarantees the finding of the optimal solution, however its high complexity limits its applicability for real-time computations and can be used only for benchmarking purposes. Let us assume that the order in (34) is known and fixed. Under this condition, there are only possible results satisfying the optimal condition in Proposition 1, that is, try the maximum transmission power in the fixed order with number of users from 1 to . The maximum result is the optimal one. For any two users in the possible system load range from , their order of will change at most three times. Therefore, there are totally order changes for users. Every order change requires first the sorting operation and then the comparison operation that have complexity of and respectively, which makes the overall complexity of this method .

The optimal algorithm is described as follows.

Based on the definition of power index capacity in (17), the above equation will have at most three solutions.

Once the order is fixed in the range at step (2), the method provided in Section 3.2 that finds the best local solution can be applied here, which will provide the largest , , users with this fixed order. The only difference is that the target system load is not provided directly by a specific known value , but lies within a specific range. Based on Proposition 1, according to which the users allowed to transmit will use their maximum transmission power, we perform rounds of calculation in step (3) and compare the results to find the optimal users.

As mentioned before, fairness is controlled by the vector . When changing the values of , we are actually pursuing a set of optimal fixed values that balance the rate of users with varying channel conditions and hence keep fairness. Since we do not know in advance the exact distribution of the channel conditions, and the number of users may also change, it is difficult to obtain vector in advance. Therefore, a real-time algorithm is required that is capable of converging toward , while maintaining the asymptotic fairness. Stochastic approximation algorithm has been proven to be effective in estimating such parameters. Note that this algorithm has been implemented in [14, 15] in order to solve similar problems. Generally, the stochastic approximation algorithm is a recursive procedure for finding the root of a real-value function . In many practical cases, the form of function is unknown. Therefore, the result with the input variable cannot be obtained directly. Instead, the observations of the results, sometimes with noise, will be taken. It has been proven that the root of can be estimated with the observation by the following procedure:

where , . We can simply let . In most situations, the value of may not be directly available, but instead the , where is the observation noise. In this case, the above approximation approach still applies, with the observed value replaced by . The convergence of to the root requires .

Here, we define our function as follows:

whose root will make which satisfies the fairness condition (3). The noise observation in our case is:

It is easy to prove that the mean of noise . Therefore, the value of is then recursively obtained by

However, need to know the mean of total system throughput . We use a smoothed value to approximate and update as follows:

where is the smooth factor which determines how the estimated follows the change of actual achieved system throughput. In the remaining of the paper, throughout the performance evaluation of our approach, the value is chosen. The numerical results presented in Sections 4.2.2 and 4.2.3, with respect to the convergence of 's and the achievable fairness, demonstrate that such a method is very effective in approximating the optimal values of and therefore controlling and maintaining fairness.

In this section, we evaluate the performance of the proposed method in terms of the achievable fairness and throughput, via modeling and simulation. Furthermore, to better understand the performance of the proposed scheduling algorithm-in the following we refer to as throughput maximization and fair scheduling (MAX-FAIR)—we compare it with the maximum throughput (MAX) scheme [16], which achieves the maximum total uplink throughput by allowing only the best users in terms of their received power to transmit, and with the HDR algorithm [7, 9], which is a single user scheduling algorithm. The principles and operation of HDR basically refer to a proportional fair scheduling scheme, which can be used in the uplink scheduling to demonstrate the one-at-a-time proportional fair scheduling. Following the HDR principles the transmission of a single user at a given time slot is scheduled, with the data rates and slot lengths varying according to the specific channel condition. In the MAX scheme parameter, is determined by iteratively comparing the throughput of best users, , where is the total number of users. The throughput achieved by MAX scheme is regarded as the upper bound throughput in the uplink CDMA scheduling. On the other hand, since HDR achieves temporal fairness, we consider it here to mainly observe the difference between temporal fairness and throughput fairness and their corresponding advantages in specific cases.

Throughout our numerical study, we consider a single cell DS-CDMA multirate system with multiple active users. All active users are continuously backlogged during the simulation and generate packets with average size of 320 bytes. The maximum transmission power is assumed the same for all users, that is, , while the system chip rate is as defined in IS-95 and the required SINR is  dB for data service, the same for all users. The transmission time is divided into 1 millisecond equal length slots, which is the algorithm scheduling interval, while the simulation lasts for slots.

To study the impact of the channel condition variations on the system throughput and fairness performance, we model the channels through an 8-state Markov-Rayleigh fading channel model [30]. According to this model, the channel has equal steady-state probabilities of being in any of the eight states. We also assume that the coherent time is much larger than the length of a time-slot, hence the channel state is assumed to be constant within a time slot. At the beginning of each time slot, the channel model decides to transit to a new state, which can only be itself or one of its neighbor states, that is, from state to or . Table 1 summarizes the state transition probabilities for all the eight states.

Furthermore, four different cases with respect to the ranges of the average SNRs that are assigned to the various users are considered. Specifically, Table 2 presents the corresponding ranges and lists the assignment of the average SNRs for each user for a seven-user scenario, under all these cases. The four different cases represent four different scenarios with respect to the SNR as follows (from top to bottom): large SNR range with low SNR users, low SNR, middle SNR, and high SNR. In the next subsection, we evaluate the performance of MAX-FAIR, MAX, and HDR methods under all four cases and compare their corresponding achieved throughput and fairness.

In most of the numerical results presented in the next subsection, unless otherwise is explicitly indicated, all users are assumed to have the same weight. Such a scenario allows us to better understand and compare the achievable performances of the various scheduling schemes, when users have different channel conditions. However, the operation and effectiveness of the proposed MAX-FAIR policy is also demonstrated in an environment, where users present different weights.

The numerical results presented in Sections 4.2.1 and 4.2.2 refer mainly to the impact of some of the parameters associated with the proposed MAX-FAIR algorithm on its operation and achievable performance and allow us to obtain a better understanding of its operational characteristics and properties. Then in Sections 4.2.3 and 4.2.4, comparative results about the achievable throughput and fairness of the MAX-FAIR, MAX and HDR algorithms are presented.

Figure 1 shows the sensitivity of the weighted throughput achieved by the MAX-FAIR algorithm as a function of the number of samples used to obtain these values. The last point in the horizontal axis corresponds to the optimal value. It should be noted that in the vertical axis, the depicted weighted throughputs are normalized over the optimal value. Moreover, the different curves provided in this figure correspond to different combinations of the SNR ranges and the number of active users. As can be seen, the more samples we choose, the closer is the obtained maximum value to the optimal value, which clearly presents the tradeoff between the accuracy and the required computational power, as discussed before in Section 3.3. For instance, we observe that in the cases with small SNR range (e.g., [0,1] dB), even 20 samples are sufficient to get satisfactory results, while for the cases with larger SNR range (e.g., [−3,3] dB), more samples may be required.

Furthermore, as it can be observed from this figure, for the case of [0,1] dB, the larger the number of active users in the system, the less sensitive is the achievable maximum result to the number of samples (i.e., the slope of the corresponding curve becomes smoother as the number of active users increases). On the other hand, when there are users with high SNR values (e.g., [−3,3] dB), the increasing number of active users makes the achieved throughput drop slightly for small number of samples. This difference in the system behavior is closely related to a different number of simultaneously served users, under different SNR ranges and channel conditions, as depicted by the different observed service patterns in Figure 2.

Specifically, in Figure 2, we present the probabilities of the number of simultaneously served users in each scheduling cycle. For this experiment, we consider 40 backlogged users in the system and perform 200 trials. In each trial, users are randomly assigned the SNRs in the designated SNR range, following the 8-state model [30] described in Section 4.1. We observe that when there are users having high SNR values, for example, in the cases of [−3,3] dB and [2,4] dB, only a small number of users (at most 2 in this experiment), are served concurrently. However, in the case that all users have small SNR values, for example, in the case of [−4,−2] dB, the number of simultaneously served users increases significantly (it is distributed between 4 and 17 in our case as can be seen by Figure 2). Such user distribution indicates that in the case that a single user cannot consume all the system resources (e.g., the case where users have low SNR values), more users will be scheduled simultaneously in order to achieve a more efficient resource utilization and as a result increase the total system throughput. This also demonstrates the advantage of our proposed scheduling algorithm over the one-by-one scheduling algorithms that have been proposed in literature. As a result, with respect to Figure 1, for the case of [0,1] dB, multiple users are scheduled to reach the maximal throughput. Increasing the number of active users enables the system to schedule more available candidates to achieve higher throughput, and therefore the achievable result is less sensitive to the number of samples. However, for the case [−3,3] dB at most only 1 or 2 users are scheduled for simultaneous transmission. In the following experiments and numerical results, we adopt the accuracy of 100 samples, which is sufficient to reach 95% of the optimal-weighted throughput.

As described in Sections 2.1 and 3.4, parameters 's are used to represent the fairness constraints in our optimization problem formulation. Figure 3 shows the dynamic change of parameters 's as the system and time evolve, for two different cases that correspond to two different SNR ranges. A seven-user scenario is considered, while for demonstration purposes for each case the corresponding values of only two representative users are presented—one user with strong channel and one user with weak channel. As mentioned before, all the users are assigned the same weight in order to more clearly demonstrate the influence of the channel conditions on 's. It can be seen by this figure that the converged values of 's have the effect of compensating users with the weak channels and reducing the priority of users with strong channels in the scheduling policy. In fact, the converged values of 's will make both users (weak and strong) to gain proper system resources and therefore achieve fair throughput. Please note that it is the relative values of 's that control the priority of accessing the system resources, and not their absolute values. Furthermore, it should be noted that the lower the average SNR of a weak user, the larger the gap between the weak user and a strong user, which has negative impact on the achievable system throughput, as we will see in the following subsection.

Figure 4 shows the average throughputs of all the users under the MAX-FAIR, MAX, and HDR methods, for a seven-user scenario where the average SNR range is [−3,3] dB and the corresponding average SNR assignments to the seven users are as shown in Table 2. In order to better demonstrate the tradeoff between the computational complexity and the achievable throughput of MAX-FAIR approach, we obtained the corresponding results under two different cases with respect to the number of power index samples (i.e., 20 and 100 samples). As observed in this figure the MAX-FAIR with 100 power index samples achieves slightly higher throughput, however it requires five times the computational power of the MAX-FAIR with 20 power index samples.

When compared to other two scheduling schemes, MAX-FAIR presents the best throughput-fairness performance (balances the achievable throughput of all users) despite the variable channel conditions of the different users, which indicates that the fairness is well maintained under the proposed scheduling algorithm. As mentioned before in the paper, the main objective of HDR is to achieve temporal fairness. Therefore, under HDR scheduling each user throughput is closely related to its channel conditions. That is why in Figure 4 we observe that users 1, 2, and 3 have smaller throughput than users 4, 5, and 6, while user 7 has the largest throughput under the HDR scheme. Under the MAX algorithm, user 7 consumes most of the system resources and achieves much higher throughput than the rest of the users due to the fact that the objective of MAX algorithm is to achieve the highest possible total system throughput, without however considering the fairness issue. In Figure 5, we further measure and evaluate the fairness performance by the standard deviation of the average throughput under all the four different SNR cases. Among the three algorithms, MAX-FAIR algorithm has the smallest deviation for all the different cases under consideration, while the corresponding values change only slightly from case to case. We also find that in general the standard deviation increases as the SNRs become higher. This happens because small fluctuation of results in larger throughput change, if all the users have higher SNR levels.

Figure 6 compares the corresponding average system throughputs of the three algorithms under evaluation, for the different SNR ranges (cases). As we expected, MAX-FAIR outperforms HDR in most cases due to the simultaneous scheduling of multiple users, as has been demonstrated in Figure 2, and consequently results in higher resource utilization. However, in the case of SNR range of [−3,3] dB, MAX-FAIR achieves slightly lower throughput than the HDR. The reason of that resides in the different fairness criteria considered and satisfied in these two algorithms, namely, the throughput fairness and temporal fairness. If we examine again Figure 3, we notice that users that have low average SNR (−3 dB) (e.g., users 1, 2, and 3) finally converge to a high , which enables them to have equal opportunity to transmit under the MAX-FAIR scheduling policy. Due to their weak channel conditions, their average throughputs will be low and hence the total system throughput will become lower because of the satisfaction of the throughput fairness constraint. However, as explained before since access time is not the only resource to be shared among the users in these systems, considering throughput fairness instead of temporal fairness is more meaningful in these systems and environments, despite the slightly lower total throughput that can be achieved in some cases under this consideration. One possible alternative solution is to relax the fairness constraint if the QoS permits it. Our experiments have demonstrated that after relaxing fairness to 85% of its original requirement, the MAX-FAIR catches up and outperforms the HDR.

In order to obtain a more in-depth understanding of the MAX-FAIR fairness operation, in Figure 7, we present the achieved average throughputs for all the seven users under MAX-FAIR scheme, for a scenario where the SNR range is assumed to be [−3,3] dB, and the users are assigned different weights. The different weights can be considered as the mapping of different QoS requirements. In this scenario, users 1 and 4 have weight 1, users 2 and 5 have weight 2, while users 3, 6, and 7 have weight 4. Figure 7 demonstrates that the MAX-FAIR successfully schedules the transmissions and distributes the resources so that the various users achieve throughput according to their corresponding assigned weights. Specifically users with weights 2 and 4 obtain, respectively, two times and four times the throughput achieved by users with weight 1. In this figure, we also present (on the right-hand side vertical axis) the converged values of parameters 's. Here, the different values of 's reflect both the channel condition variations and the weight differences. Please note that the relationship between and weight is not linear due to the nonlinearity between the allocated resources and throughput.

Figure 8 shows the achieved total system throughput under MAX and MAX-FAIR algorithms as a function of the number of backlogged users, for the case where the users SNRs are located within [0,1] dB range. Please note that as mentioned before MAX algorithm provides the maximum uplink transmission throughput without considering the fairness property, and therefore is assumed to provide the upper bound throughput in uplink scheduling. From this figure, we can clearly observe the great advantage of the proposed MAX-FAIR approach and its ability to achieve very high throughput, while still maintaining fairness. When the number of backlogged users reaches a certain level, for example, 35 in this experiment, the throughput becomes flat for both MAX-FAIR and MAX, which means that the chances of improving the throughput by opportunistic scheduling with multiple users have been fully utilized.

In this paper, the CDMA uplink throughput maximization problem, while maintaining throughput fairness among the various users, was considered. It was shown that such a problem can be expressed as a weighted throughput maximization problem, under certain power and QoS requirements, where the weights are the control parameters that reflect the fairness constraints. A stochastic approximation method was presented in order to effectively identify the required control parameters. The numerical results presented in the paper, with respect to the convergence of the control parameters and the achievable fairness, demonstrated that this method is very effective in approximating the optimal values and therefore controlling and maintaining fairness. Furthermore, the concept of power index capacity was used to represent all the corresponding constraints by the users power index capacities at some certain system power index. Based on this, the optimization problem under consideration was converted into a binary knapsack problem, where the optimal solution can be obtained through a global search within a specific range.

The performance of the proposed policy in terms of the achievable fairness and throughput was obtained via modeling and simulation and was compared with the performances of other scheduling algorithms. The corresponding results revealed the advantages of the proposed policy over other existing scheduling schemes and demonstrated that it achieves very high throughput, while satisfies the QoS requirements and maintains fairness among the users, under different channel conditions and requirements.