[article]
Titre : |
Efficient two-dimensional packing algorithms for mobile WiMAX |
Type de document : |
texte imprimé |
Auteurs : |
Andrea Lodi, Auteur ; Silvano Martello, Auteur ; Michele Monaci, Auteur |
Année de publication : |
2012 |
Article en page(s) : |
pp. 2130-2144 |
Note générale : |
Management |
Langues : |
Anglais (eng) |
Mots-clés : |
Mobile WiMAX Two-dimensional packing Computational complexity Experimental analysis |
Résumé : |
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 𝒩𝒫-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. |
DEWEY : |
658 |
ISSN : |
0025-1909 |
En ligne : |
http://mansci.journal.informs.org/content/57/12.toc |
in Management science > Vol. 57 N° 12 (Décembre 2011) . - pp. 2130-2144
[article] Efficient two-dimensional packing algorithms for mobile WiMAX [texte imprimé] / Andrea Lodi, Auteur ; Silvano Martello, Auteur ; Michele Monaci, Auteur . - 2012 . - pp. 2130-2144. Management Langues : Anglais ( eng) in Management science > Vol. 57 N° 12 (Décembre 2011) . - pp. 2130-2144
Mots-clés : |
Mobile WiMAX Two-dimensional packing Computational complexity Experimental analysis |
Résumé : |
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 𝒩𝒫-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. |
DEWEY : |
658 |
ISSN : |
0025-1909 |
En ligne : |
http://mansci.journal.informs.org/content/57/12.toc |
|