Fast algorithms for joint power control and scheduling in wireless networks

This paper studies the problem of finding a minimum-length schedule of a power-controlled wireless network subject to traffic demands and SINR (signal-to-interference-plus-noise ratio) constraints. We propose a column generation based algorithm that finds the optimal schedules and transmit powers. The column generation method decomposes a complex linear optimization problem into a restricted master problem and a pricing problem. We develop a new formulation of the pricing problem using the Perron-Frobenius eigenvalue condition, which enables us to integrate link scheduling with power control in a single framework. This new formulation reduces the complexity of the pricing problem, and thus improves the overall efficiency of the column generation method significantly - for example, the average runtime is reduced by 99.86% in 18-link networks compared with the traditional column generation method. Furthermore, we propose a branch-and-price method that combines column generation with the branch-and-bound technique to tackle the integer constraints on time slot allocation. We develop a new branching rule in the branch-and-price method that maintains the size of the pricing problem after each branching. Our branch-and-price method can obtain optimal integer solutions efficiently for example, the average runtime is reduced by 99.72% in 18-link networks compared with the traditional branch-and-price method. We further suggest efficient heuristic algorithms based on the structure of the optimal algorithms. Simulation results show that the heuristic algorithms can reach solutions within 10% of optimality for networks with less than 30 links.