More Web Proxy on the site http://driver.im/

article

Computational analysis and efficient algorithms for micro and macro OFDMA downlink scheduling

Authors:

Liran KatzirAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 18, Issue 1

Pages 15 - 26

https://doi.org/10.1109/TNET.2009.2022937

Published: 01 February 2010 Publication History

Abstract

Orthogonal frequency-division multiple access (OFDMA) is one of the most important modulation and access methods for the future mobile networks. Before transmitting a frame on the downlink, an OFDMA base station has to invoke an algorithm that determines which of the pending packets will be transmitted, what modulation should be used for each of them, and how to construct the complex OFDMA frame matrix as a collection of rectangles that fit into a single matrix with fixed dimensions. We propose efficient algorithms, with performance guarantee, that solve this intricate OFDMA scheduling problem by breaking it down into two subproblems, referred to as macro and micro scheduling. We analyze the computational complexity of these subproblems and develop efficient algorithms for solving them.

References

[1]

A. Azgin and M. Krunz, "Scheduling in wireless cellular networks under probabilistic channel information," in Proc. ICCCN, Dallas, TX, 2003, pp. 89-94.

[2]

Y. Ben-Shimol, I. Kitroser, and Y. Dinitz, "Two-dimensional mapping for wireless OFDMA systems," IEEE Trans. Broadcast., vol. 52, no. 3, pp. 388-396, Sep. 2006.

[3]

C. Chekuri and S. Khanna, "A polynomial time approximation scheme for the multiple knapsack problem," SIAM J. Comput., vol. 35, no. 3, pp. 713-728, 2005.

[4]

R. Cohen and L. Katzir, "Computational analysis and efficient algorithms for micro and macro OFDMA scheduling," Technion--Israel Inst. of Technol., Tech. Rep. CS-2007-02, 2007.

[5]

R. Cohen and L. Katzir, "A generic quantitative approach to the scheduling of synchronous packets in a shared uplink wireless channel," IEEE/ACM Trans. Netw., vol. 15, no. 4, pp. 932-943, Aug. 2007.

[6]

R. Cohen and L. Katzir, "The generalized maximum coverage problem," Inf. Process. Lett., vol. 108, no. 1, pp. 15-22, 2008.

[7]

R. Cohen, L. Katzir, and D. Raz, "An efficient approximation for the generalized assignment problem," Inf. Process. Lett., vol. 100, no. 4, pp. 162-166, 2006.

[8]

M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.

[9]

A. J. Goldsmith and S. G. Chua, "Variable-rate variable-power MQAM for fading channel," IEEE Trans. Commun., vol. 45, no. 10, pp. 1218-1230, Oct. 1997.

[10]

D. S. Hochbaum, Ed., Approximation Algorithms for NP-Hard Problems. Boston, MA: PWS, 1997.

[11]

Local and Metropolitan Area Networks--Part 16: Air Interface for Fixed Broadband Wireless Access Systems, IEEE Std. 802.16-2004.

[12]

A. Israeli, D. Rawitz, and O. Sharon, "On the complexity of sequential rectangle placement in IEEE 802.16/WiMax systems," in Proc. ESA, Perth, Australia, 2007, pp. 570-581.

[13]

H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems. New York: Springer, 2004.

[14]

S. Khuller, A. Moss, and J. Naor, "The budgeted maximum coverage problem," Inf. Process. Lett., vol. 70, no. 1, pp. 39-45, 1999.

[15]

D. Kivanc, G. Li, and H. Liu, "Computationally efficient bandwidth allocation and power control for OFDMA," IEEE Trans. Wireless Commun., vol. 2, no. 6, pp. 1150-1158, Nov. 2003.

[16]

S. Lu, V. Bharghavan, and R. Srikant, "Fair scheduling in wireless packet networks," IEEE/ACM Trans. Netw., vol. 7, no. 4, pp. 473-489, Aug. 1999.

[17]

S. Nanda, K. Balachandran, and S. Kumar, "Adaptation techniques in wireless packet data services," IEEE Commun. Mag., vol. 38, no. 1, pp. 54-64, Jan. 2000.

[18]

S. Shakkottai and R. Srikant, "Scheduling real-time traffic with deadlines over a wireless channel," Wireless Netw. J., vol. 8, no. 1, pp. 13-26, Jan. 2002.

[19]

M. Shreedhar and G. Varghese, "Efficient fair queueing using deficit round-robin," IEEE/ACM Trans. Netw., vol. 4, no. 3, pp. 375-385, Jun. 1996.

[20]

G. Song and Y. Li, "Cross-layer optimization for OFDM wireless networks, Part I: Theoretical framework," IEEE Trans.Wireless Commun., vol. 4, no. 2, pp. 614-624, Mar. 2005.

[21]

D. Tse and S. Hanly, "Multiaccess fading channels, Part I: Polymatroid structure, optimal resource allocation and throughput capacities," IEEE Trans. Inf. Theory, vol. 44, no. 7, pp. 2796-2815, Nov. 1998.

[22]

P. Viswanath, D. Tse, and R. Laroia, "Opportunistic beamforming using dumb antennas," IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1277-1294, Jun. 2002.

[23]

I. Wong, Z. Shen, J. Andrews, and B. L. Evans, "A low complexity algorithm for proportional resource allocation in OFDMA systems," in Proc. IEEE Int. Signal Process. Syst. Workshop, Austin, TX, Oct. 2004, pp. 1-6.

Cited By

Kilaru S(2019)Effective Periodic Feedback CSI Channel Allocation Under Possible Circumstances in Modern Broadband Wireless NetworksWireless Personal Communications: An International Journal10.1007/s11277-018-6073-y104:3(1133-1148)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11277-018-6073-y
Cohen RGrebla G(2015)Efficient allocation of periodic feedback channels in broadband wireless networksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2014.229805223:2(426-436)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2298052
Cohen RGrebla G(2015)Joint scheduling and fast cell selection in OFDMA wireless networksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2013.229129523:1(114-125)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TNET.2013.2291295
Show More Cited By

Index Terms

Computational analysis and efficient algorithms for micro and macro OFDMA downlink scheduling
1. Networks
  1. Network properties
    1. Network structure
  2. Network services
    1. Network management
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

A low-complexity zero-forcing CFO compensation scheme for OFDMA uplink systems

Similar to the conventional orthogonal frequencydivision multiplexing (OFDM) system, an OFDM multiple access (OFDMA) system will have a carrier frequency offset (CFO) problem. Since CFOs of all users are different, CFO compensation in the OFDMA uplink ...
A two-stage frequency-offset estimation scheme for OFDMA system
NTMS'09: Proceedings of the 3rd international conference on New technologies, mobility and security

In OFDMA multiple access wireless communication systems, carrier frequency offsets between the transmitter and the receiver tend to destroy the orthogonality among subcarriers, and hence, introduces intercarrier interference. A two-stage frequency ...
On the performance of LTE downlink scheduling algorithms: A case study on edge throughput
Highlights
- The main objective of the proposed scheduling algorithm is to increase the edge throughput without sacrificing cell throughput in LTE networks.
Abstract
Radio resource allocation is a crucial task in the LTE networks. To increase the overall user experience, an efficient radio resource allocation algorithm should be utilized. In this work, a new scheduling algorithm has been proposed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 18, Issue 1

February 2010

332 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2010

Revised: 20 November 2008

Received: 25 December 2007

Published in TON Volume 18, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
240
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kilaru S(2019)Effective Periodic Feedback CSI Channel Allocation Under Possible Circumstances in Modern Broadband Wireless NetworksWireless Personal Communications: An International Journal10.1007/s11277-018-6073-y104:3(1133-1148)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11277-018-6073-y
Cohen RGrebla G(2015)Efficient allocation of periodic feedback channels in broadband wireless networksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2014.229805223:2(426-436)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2298052
Cohen RGrebla G(2015)Joint scheduling and fast cell selection in OFDMA wireless networksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2013.229129523:1(114-125)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TNET.2013.2291295
Liu YSong QGuo LWang X(2013)Efficient scheduling algorithms for mixed services in wireless OFDMA systemTelecommunications Systems10.1007/s11235-011-9476-652:4(1945-1960)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1007/s11235-011-9476-6

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents