Title :
Coding-Aware Proportional-Fair Scheduling in OFDMA Relay Networks
Author :
Bin Tang ; Baoliu Ye ; Sanglu Lu ; Song Guo
Author_Institution :
Nat. Key Lab. for Novel Software Technol., Nanjing Univ., Nanjing, China
Abstract :
In recent years, OFDMA relay networks have become a key component in the 4G standards (e.g., IEEE 802.16j, 3GPP LTE-Advanced) for broadband wireless access. When numerous bidirectional flows pass through the relay stations in an OFDMA relay network that supports various interactive applications, plenty of network coding opportunities arise and can be leveraged to enhance the throughput. In this paper, we study the proportional-fair scheduling problem in the presence of network coding in OFDMA relay networks. Considering the tradeoff between performance and overhead, we propose two models, global approach (GA) and local approach (LA), under which the corresponding problems are shown both NP-hard. For the GA model, we show that it cannot be approximated within some constant factor. Hence, we propose a heuristic algorithm with low time complexity. For the LA model, we propose a theoretical polynomial time approximation scheme (PTAS), and also present a practical greedy algorithm with approximation factor of 1/2. Simulation results show that our algorithms can achieve significant throughput improvement over a state-of-the-art noncoding scheme.
Keywords :
3G mobile communication; 4G mobile communication; Long Term Evolution; OFDM modulation; computational complexity; frequency division multiple access; greedy algorithms; network coding; optimisation; polynomial approximation; relay networks (telecommunication); scheduling; 3GPP LTE-Advanced; 4G standards; IEEE 802.16j; NP-hard problem; OFDMA relay networks; PTAS; approximation factor; broadband wireless access; coding-aware proportional-fair scheduling; global approach; greedy algorithm; heuristic algorithm; interactive applications; local approach; network coding; polynomial time approximation scheme; time complexity; Approximation algorithms; Downlink; Network coding; Relays; Scheduling; Throughput; Network coding; OFDMA relay networks; approximation algorithm; proportional-fair scheduling;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
DOI :
10.1109/TPDS.2012.269