Optimal feedback allocation algorithms for multi-user uplink

This paper investigates the impact of limited feedback on user throughput in the uplink of a cellular system. We consider scenarios where the base-station has limited feedback resources, which it needs to allocate across the users it serves. We propose a general model that captures the effect of feedback allocation on the achievable rates for a user, which allows us to characterize the rate region for such a system. For unsaturated queueing systems, we show that the optimal feedback allocation policy that stabilizes the queues when possible, involves solving a weighted sum-rate maximization at each scheduling instant. We show that such an online weighted sum-rate maximization policy can also be used for long-term utility maximization, which is applicable to saturated queueing systems. The weighted sum-rate maximization is solved using dynamic programming incurring pseudo-polynomial complexity in the number of users and in the total feedback bit budget. Finally, we show that the widely-studied single-stream multiple-input-multiple-output beamforming/combining physical layer communication strategy induces a special form on the optimal feedback allocation problem, which allows for the development of a polynomial-time approximation algorithm.