Efficient Two-Dimensional Packing Algorithms for Mobile WiMAX

Andrea Lodi (), Silvano Martello (), Michele Monaci (), Claudio Cicconetti (), Luciano Lenzini (), Enzo Mingozzi (), Carl Eklund () and Jani Moilanen ()
Additional contact information
Andrea Lodi: Department of Electronics, Computer Science and Systems, University of Bologna, 40136 Bologna, Italy
Silvano Martello: Department of Electronics, Computer Science and Systems, University of Bologna, 40136 Bologna, Italy
Michele Monaci: Department of Information Engineering, University of Padova, 35131 Padova, Italy
Claudio Cicconetti: Intecs S.p.A., 56121 Pisa, Italy
Luciano Lenzini: Department of Information Engineering, University of Pisa, 56010 Pisa, Italy
Enzo Mingozzi: Department of Information Engineering, University of Pisa, 56010 Pisa, Italy
Carl Eklund: Nokia Siemens Networks, FI-02610 Espoo, Finland
Jani Moilanen: Nokia Siemens Networks, FI-02610 Espoo, Finland

Management Science, 2011, vol. 57, issue 12, 2130-2144

Abstract: We present the result of research, developed within Nokia Siemens Networks, to solve the downlink sub-frame allocation problem in Mobile WiMAX (IEEE 802.16) technology in its full complexity, while simultaneously fulfilling real-life constraints on processing power and delay. We describe the IEEE 802.16 standard, and introduce two system models. A theoretical analysis of the two-dimensional packing problems originated by such models shows that they are both NP-hard in the strong sense. From a practical point of view, the processing budget for scheduling in the base station was estimated to be 1 ms on a state-of-the-art PC. Thus, we introduce two highly efficient heuristics that were developed to handle the system practically. A thorough computational analysis of their optimization characteristics and a system-level evaluation in realistic scenarios proved that the algorithms offer significant capacity gain in Mobile WiMAX systems that translate to increased operator revenues. This paper was accepted by Dimitris Bertsimas, optimization.

Keywords: Mobile WiMAX; two-dimensional packing; computational complexity; experimental analysis (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1110.1416 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:57:y:2011:i:12:p:2130-2144

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().