Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation

详细信息    查看全文

• 作者：Yixin Zhao ; Torbjörn Larsson ; Di Yuan ; Elina Rönnberg…
• 关键词：Localized SC ; FDMA ; Stabilized column generation ; Power minimization ; Integer linear programming ; Uplink scheduling ; Matheuristic
• 刊名：Optimization and Engineering
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：17
• 期：4
• 页码：695-725
• 全文大小：715 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Engineering, general
  Systems Theory and Control
  Environmental Management
  Agriculture
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2924
• 卷排序：17

文摘

We study resource allocation in cellular systems and consider the problem of finding a power efficient scheduling in an uplink single carrier frequency division multiple access system. Due to the discrete nature of this problem and its computational difficulty, particularly in a real-time setting, the use of suboptimal algorithms is common practice. We aim at an effective way of gauging the performance of suboptimal algorithms by finding tight bounds on the global optimum. Toward this end, we first provide a basic integer linear programming formulation. Then we propose a significantly stronger column-oriented formulation and a corresponding column generation method, as well as an enhanced column generation scheme. The latter extends the first scheme through the inclusion of a stabilization technique, an approximate column generation principle, and a tailored heuristic that is embedded in the column generation scheme to find high-quality though not necessarily global optimal solutions. The computational evaluation demonstrates that compared with a poor performance by the integer linear programming formulation, the column generation method can produce near-optimal schedules that enable a sharp bounding interval. The enhanced column generation method significantly sharpens the bounding interval. Hence the column generation approach serves well for the purpose of benchmarking results for large-scale instances.