Queue-based sub-carrier grouping for feedback reduction in OFDMA systems

Sub-carrier grouping is a popular feedback reduction approach for orthogonal-frequency-division multiple-access (OFDMA) systems that has been adopted into fourth-generation standards such as 3GPP Long Term Evolution (LTE). Feedback reduction is motivated by the fact that the bandwidth expenditure in acquiring full information in a downlink OFDMA system scales as the product of the number of users and the number of OFDMA bands. As this is infeasible in most systems, sub-carrier grouping calls for users to report a single channel state value per predesignated group of OFDM bands. Such an approach would reduce the amount of feedback by a factor that is equal to the size of the group, albeit at a loss in throughput. In this paper, we propose a throughput-optimal joint sub-carrier grouping and data scheduling policy that makes decisions based on queue-lengths and channel states in each time slot. The feedback allocation or sub-carrier grouping policy, inspired by the current approach in LTE, operates under a total feedback budget and must periodically decide a sub-carrier grouping size for each user that obeys this resource constraint. However, as we show, the optimal allocation algorithm has complexity that, in general, scales exponentially in the number of users. Thus, we turn our attention to the important issue of computational efficiency and propose a greedy algorithm that allocates full feedback bandwidth to a constant-sized subset of users based on the network state. We evaluate the performance of this simple approach through extensive numerical experiments. We show that under asymmetric arrival rate settings, our greedy algorithm is within 10% of the optimal (throughput-wise) when consuming only 25% of the full feedback bandwidth while paying only a logarithmic (in the number of users) price in control overhead.