We study network utility maximization (NUM) in the context of cellular single station association (SSA) policies, which assigns each mobile user (MU) to a single base station (BS). We measure an SSA policy in terms of the induced alpha-proportional fairness utility of each users downlink rate, summed over all users. The general SSA NUM problem involves choosing an optimal association from MUs to BSs as well as an optimal allocation of BS resources to associated MUs. Finding an exact solution to such centralized user association problems is well-known to be NP-hard. Our contributions are as follows: i) we give an explicit solution for the optimal BS allocation for a given SSA, which establishes SSA NUM as a purely combinatiorial problem; ii) we establish the integrality gap for the association problem to be one, and prove the relaxation to be a non-convex optimization problem; iii) we provide both centralized and distributed greedy algorithms for SSA, both with and without the exchange of instantaneous rate information between users and stations. Our numerical results illustrate performance gains of three classes of solutions: i) SSA solutions obtained by greedy rounding of multi-station associations (a centralized convex program), ii) our centralized and distributed greedy algorithms with/without rate information exchanged, and iii) simple association heuristics.
Download