Throughput maximization on the downlink of a CDMA system

We propose a rate scheduling algorithm to maximize the network throughput of a variable data rate CDMA system and prove its optimality. The system uses OVSF (orthogonal variable spreading factor) codes and the algorithm finds the optimum rate assignments on the binary code tree under constraints on the total transmit power and minimum QoS (rate) requirement of each user. The algorithm is optimal in the sense that it maximizes the total network throughput within the constraints and achieves this with minimum possible power. The algorithm works in a greedy fashion and has a polynomial time complexity of O(N), where N is the number of users. We also extend our results to a more general set of combinatorial optimization problems where the user rates can be any integer multiples of a basic rate (such as multi-code CDMA), not necessarily the set of rates on the binary tree structure, but the optimal solutions are still greedy achievable.