Name
Title | ||
|---|---|---|
Complexity analysis and heuristic algorithms for radio resource allocation in OFDMA networks |
Abstract | ||
|---|---|---|
In this paper, we address the problem of allocating users to radio resources (i.e. subcarriers) in the downlink of an OFDMA system. In particular, we consider a multi-format resource allocation problem (MF-RAP) in which the link adaptation adjusts the spectral efficiency for each user-subcarrier pair, i.e. for each radio link, in order to minimize the total transmission power while fulfilling a rate request for each user. We propose an integer linear programming (ILP) formulation of the problem and exhaustively discuss the computational complexity. Specifically, we prove that the problem is NP-hard in the strong sense and demonstrate that it is hard to be approximated in polynomial time within a constant factor. Hence, we present heuristic approaches that achieve “reasonably good” solutions in the general case. Computational experiences show that, in comparison with a commercial state-of-the-art ILP optimization solver, the proposed algorithms are effective in terms of solution quality and CPU times. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/CTS.2011.5898899 | ICT |
Keywords | Field | DocType |
ofdm modulation,computational complexity,frequency division multiple access,heuristic programming,integer programming,linear programming,polynomial approximation,radio links,resource allocation,np-hard problem,ofdma network,complexity analysis,heuristic algorithm,integer linear programming,multiformat resource allocation problem,polynomial time approximation,radio link,radio resource allocation,spectral efficiency,transmission power,user subcarrier pair,computer experiment,np hard problem,polynomial time,bandwidth,dynamic programming,link adaptation,resource management,ofdm,polynomials | Link adaptation,Mathematical optimization,Heuristic,Heuristic (computer science),Computer science,Algorithm,Integer programming,Resource allocation,Linear programming,Time complexity,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
978-1-4577-0025-5 | 6 | 0.45 |
References | Authors | |
8 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Belleschi, M. | 1 | 6 | 0.45 |
| Detti, P. | 2 | 6 | 0.45 |
| Andrea Abrardo | 3 | 376 | 47.39 |