Paper Info
Title
Efficient Two-Dimensional Packing Algorithms for Mobile WiMAX
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.
Year
DOI
Venue
2011
10.1287/mnsc.1110.1416
Management Science
Keywords
Field
DocType
efficient two-dimensional packing algorithms,dimitris bertsimas,thorough computational analysis,system model,mobile wimax,optimization characteristic,nokia siemens networks,processing budget,theoretical analysis,mobile wimax system,processing power,experimental analysis,computational complexity
Base station,Economics,Mathematical optimization,Packing problems,Scheduling (computing),Algorithm,WiMAX,Heuristics,Operator (computer programming),Telecommunications link,Computational complexity theory
Journal
Volume
Issue
ISSN
57
12
0025-1909
Citations 
PageRank 
References 
11
0.60
8
Authors
8
Name
Order
Citations
PageRank
Andrea Lodi12198152.51
Silvano Martello22362218.73
Michele Monaci3104960.78
Claudio Cicconetti438831.10
Luciano Lenzini5100081.89
Enzo Mingozzi61055100.39
Carl Eklund7121.00
Jani Moilanen8252.30