Power Control for AP-Based Wireless Networks Under the SINR Interference Model: Complexity and Efficient Algorithm Development
In this paper, the power control problem is considered for access-point based wireless networks under the SINR interference model. This problem is NP hard in terms of the number of APs in the network, and if not designed properly can have high polynomial complexity in terms of the power levels. The authors first separate the overall problem into two sub-problems using the primal-dual method. They then develop an efficient algorithm under the SINR-interference model that uses only two power levels to solve a sub-problem of the overall power control problem, which they call the Utility-Independent Power Control (UIPC) sub-problem. This approach allows the optimality gap of the UIPC sub-problem to be bounded.