An efficient scheduling algorithm for downlink multi-antenna CDMA systems

We design efficient scheduling algorithms for multiantenna CDMA downlink systems using zero forcing beamforming. Our proposition maximizes the system sum rate and keeps the computational complexity low. We make use of a graph theoretical approach to represent the system as an undirected weighted graph. As a second step, we formulate the scheduling problem as the maximum weight k-colorable subgraph problem. We propose two heuristic solutions to find the users to serve in each time slot in an acceptable polynomial time. Finally we evaluate the efficiency of the proposed schemes by mean of simulations and the results shows the near-optimal performance of the proposed schedulers with very low computational complexity compared to the optimal exhaustive search over all the possible users combinations. Assuming the use of non-orthogonal spreading codes, our proposed algorithms are shown to still have near-optimal performance even in the case of high values of the orthogonality factor.