Joint Base Station Association and Power Control via Benders' Decomposition

Heterogeneous cellular network (Hetnets), where various classes of low power base stations (BS) are underlaid in a macro-cellular network, is a promising technique for future green communications. These new types of BSs can achieve substantial improvement in spectrum-efficiency and energy-efficiency via cell splitting. However, mobile stations perceive different channel gains to different base stations. Therefore, it is important to associate a mobile station with the right BS so as to achieve a good communication quality. Oftentimes, the already-challenging BS association problem is further complicated by the need of transmission power control, which is an essential component to manage co-channel interference in many wireless communications systems. Despite its importance, the joint BS association and power control (JBAPC) problem has remained largely unsolved, mainly due to its non-convex and combinatorial nature that makes the global optimal solution difficult to obtain. This paper aims to circumvent this difficulty by proposing a novel algorithm based on Benders' Decomposition to solve the non-convex JBAPC problem efficiently and optimally. In particular, we endeavor to maximize the system revenue and meanwhile associate every served mobile station with the right BS with the minimum total transmission power. We first propose a single-stage formulation that captures the two objectives simultaneously. The problem is then transformed in a way that can be efficiently solved using the proposed joint BS Association and poweR coNtrol algorithm (referred to as BARN) that is derived from classical Benders' Decomposition. Finally, we derive a closed-form analytical formula to characterize the effect of the termination criterion of the algorithm on the gap between the obtained solution and the optimal one. For practical implementation, we further propose an Accelerated BARN (A-BARN) algorithm that can significantly reduce the computational time. By carefully choosing the termination criterion, both BARN and A-BARN are guaranteed to converge to the global optimal solution.