S-MAPEL: Monotonic optimization for non-convex joint power control and scheduling problems

In interference-limited wireless networks where simultaneous transmissions on nearby links heavily interfere with each other, power control alone is not sufficient to eliminate strong levels of interference between close-by links. In this case, scheduling, which allows close-by links to take turns to be active, plays a crucial rule for achieving high system performance. Joint power control and scheduling that maximizes the system utility has long been a challenging problem. The complicated coupling between the signal-to-interference ratio of concurrently active links as well as the flexibility to vary power allocation over time gives rise to a series of non-convex optimization problems, for which the global optimal solution is hard to obtain. This paper is a first attempt to solve the non-convex joint power control and scheduling problems efficiently in a global optimal manner. In particular, it is the monotonicity rather than the convexity of the problem that we exploit to devise an efficient algorithm, referred to as S-MAPEL, to obtain the global optimal solution. To further reduce the complexity, we propose an accelerated algorithm, referred to as A-S-MAPEL, based on the inherent symmetry of the optimal solution. The optimal joint-power-control-and-scheduling solution obtained by the proposed algorithms serves as a useful benchmark for evaluating other existing schemes. With the help of this benchmark, we find that on-off scheduling is of much practical value in terms of system utility maximization if "off-the-shelf" wireless devices are to be used.