Message passing resource allocation for the uplink of multi-carrier multi-format systems

We propose two novel distributed resource allocation (RA) schemes for the uplink of a cellular multi-carrier multi-format system based on the message passing (MP) technique. In the proposed approaches each transmitter iteratively sends and receives information messages to/from the base station with the goal of achieving an optimal RA strategy. The exchanged messages are the solution of small distributed allocation problems. Hence, despite the NP-hardness of the original RA problem, they distribute the computational effort in the cell among all the transmitters and the base station. Specifically, the first algorithm combines MP with a dynamic programming formula solved at each step, while the second method initially solves to optimality a simplified single-format RA via MP, and eventually performs format allocation to satisfy the rate constraints. Compared to alternatives, numerical results assess the validity of MP-based schemes both in terms of efficiency and complexity.