PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Pricing-Based User Association for Downlink Heterogeneous Cellular Networks

Kaiming Shen, Wei Yu

arXiv:1407.4694v2cs.NIcs.IT

TL;DR

The paper studies proportional-fair user association in downlink HetNets, where conventional max-SINR association can produce poor load balancing. It develops distributed pricing and dual coordinate-descent methods, extending them to power control and beamforming, with comparable performance at lower complexity and improved traffic balancing.

  • Problem

    Proportional-fair HetNet association must balance users across BSs, but max-SINR association ignores traffic patterns and the joint association-and-power problem is mixed discrete and nonconvex.

  • Method

    The paper uses utility-minus-price association with dual coordinate-descent price updates, then iteratively combines association with power optimization and per-cell WMMSE beamforming.

  • Results

    The proposed methods improve low-rate users and load balancing, achieve comparable power-control performance with much lower complexity, and retain nearly the performance of network-wide WMMSE for beamforming.

  • Takeaways & Limitations

    Distributed pricing provides a parameter-free, asynchronous association mechanism that can be combined with power control and beamforming while avoiding excessive BS handover.

Abstract

from arXiv · show

This paper considers the optimization of the user and base-station (BS) association in a wireless downlink heterogeneous cellular network under the proportional fairness criterion. We first consider the case where each BS has a single antenna and transmits at fixed power, and propose a distributed price update strategy for a pricing-based user association scheme, in which the users are assigned to the BS based on the value of a utility function minus a price. The proposed price update algorithm is based on a coordinate descent method for solving the dual of the network utility maximization problem, and it has a rigorous performance guarantee. The main advantage of the proposed algorithm as compared to the existing subgradient method for price update is that the proposed algorithm is independent of parameter choices and can be implemented asynchronously. Further, this paper considers the joint user association and BS power control problem, and proposes an iterative dual coordinate descent and the power optimization algorithm that significantly outperforms existing approaches. Finally, this paper considers the joint user association and BS beamforming problem for the case where the BSs are equipped with multiple antennas and spatially multiplex multiple users. We incorporate dual coordinate descent with the weighted minimum mean-squared error (WMMSE) algorithm, and show that it achieves nearly the same performance as a computationally more complex benchmark algorithm (which applies the WMMSE algorithm on the entire network for BS association), while avoiding excessive BS handover.

I. INTRODUCTION

The paper addresses proportional-fair user association in downlink HetNets, where max-SINR association can cause poor load balancing. It develops distributed pricing-based methods for fixed-power association and its extensions to power control and beamforming.

  • I. INTRODUCTION: HetNet deployment requires jointly setting tier-specific transmit powers and user associations, especially when small cells serve traffic hotspots.Small cells can off-load macro-cell traffic, but association becomes more complex with MIMO beamforming and spatial multiplexing.
  • I. INTRODUCTION: Max-SINR association ignores traffic patterns and can produce poor load balancing across macro, pico, and femto BSs.The problem is particularly important because pico and femto BSs are often deployed in high-density hotspots.
  • I. INTRODUCTION: The paper proposes dual coordinate descent for distributed pricing-based association, replacing parameter-dependent synchronized subgradient price updates.The method is designed to be independent of parameter choices and implementable asynchronously across BSs.
  • I. INTRODUCTION: The framework extends joint association optimization to BS power control and to multi-antenna beamforming with spatial multiplexing.The paper positions these extensions within proportional-fair network utility maximization rather than power-minimization objectives.
  • I. INTRODUCTION: For joint association and power control, the proposed iterative approach has comparable performance to a dual-optimization benchmark with substantially lower computational complexity.The paper also reports that pricing-based association alleviates load imbalance, whereas max-SINR tends to exacerbate it under power control.
  • I. INTRODUCTION: For multi-antenna networks, association and beamforming are decoupled into two stages, reducing complexity while avoiding excessive BS handover.The first stage determines association and power control; the second applies per-cell WMMSE beamforming.

3) Joint BS Association and Beamforming:

The SISO formulation models one-BS-per-user association under proportional fairness, with rates determined by resource sharing and channel conditions. The fixed-power simplification isolates the discrete association problem before introducing distributed pricing updates.

  • II. BS ASSOCIATION PROBLEM FOR SISO NETWORKS: The network contains L single-antenna BSs and K single-antenna users sharing total bandwidth W with frequency reuse one.Each user is associated with one BS at a time.
  • II. BS ASSOCIATION PROBLEM FOR SISO NETWORKS: Under proportional fairness, round-robin scheduling allocates each of k_j users associated with BS j a 1/k_j share of its total time-frequency resource.This yields the user rate used in the association formulation for constant, flat-fading channels and flat transmit PSD.
  • II. BS ASSOCIATION PROBLEM FOR SISO NETWORKS: The rate model includes an SNR gap Γ representing practical coding and modulation effects.The supplied formulation describes Γ as the SNR gap determined by the coding and modulation schemes.
  • II. BS ASSOCIATION PROBLEM FOR SISO NETWORKS: The optimization jointly selects binary association variables x_ij and BS transmit powers p_j to maximize the sum log-utility across users.The formulation also retains k_j as an optimization variable, although it is determined by the association variables.
  • 3) Joint BS Association and Beamforming:: The full association-and-power problem is mixed discrete and nonconvex, so the paper first studies association with transmit PSD levels fixed a priori.Power control is treated in a subsequent section.
  • 3) Joint BS Association and Beamforming:: The fixed-power section introduces a pricing approach and a coordinate-descent price-update method for solving the resulting association problem.The price-update method is presented as a way to solve the simplified fixed-power problem.

B. Lagrangian Dual Analysis

The paper formulates BS association through Lagrangian duality, interpreting dual variables as BS-specific prices. Users select the BS maximizing utility minus price, while prices balance loads, although discrete association can create a duality gap.

  • Dual interpretation: Dual variables µ_j act as BS-specific prices in the Lagrangian formulation of the association problem.This pricing interpretation motivates distributed pricing approaches for BS association.
  • User association: Each user associates with the BS maximizing its utility a_ij minus the BS price µ_j.The resulting association rule follows directly from the analytic maximization of the Lagrangian.
  • Dual formulation: The paper explicitly writes the Lagrangian dual problem and uses its closed-form dual objective to derive a price-update method.The dual variables are introduced for the BS-load and auxiliary constraints before forming the dual function.
  • Price updates: The proposed alternative updates prices by coordinate descent on the dual rather than by the previously used subgradient method.The method exploits the particular form of the dual objective.
  • Duality gap: Because association is discrete, solving the dual need not solve the primal problem and a positive duality gap can exist.The dual optimum can nevertheless produce good primal associations; ties may require heuristic resolution.

C. Subgradient Method

The subgradient method alternates updates of ν and the BS prices µ, converging to the dual optimum but depending strongly on step-size and synchronization choices.

  • Update structure: With fixed µ, ν is updated by minimizing a differentiable convex dual function, while µ updates use subgradients because the dual function is nondifferentiable in µ_j.The algorithm updates µ and ν iteratively in sequential order.
  • Update structure: The method combines alternating minimization between µ and ν with subgradient updates on µ.A full subgradient implementation would also update ν by a subgradient, but the described method uses alternating minimization there.
  • Convergence: Because the dual problem is convex, the subgradient method is guaranteed to converge to the globally optimal solution of the dual problem.This guarantee concerns the dual problem, not necessarily the discrete primal association problem.
  • Convergence: Convergence speed depends heavily on the step size α(t), with diminishing step sizes potentially converging slowly in practice.The self-adaptive baseline also introduces parameters including γ_t, ρ, β, δ_1, and δ.
  • Distributed implementation: Distributed subgradient updates require synchronized BS price updates using the same step size to ensure convergence.This synchronization requirement is identified as a significant implementation drawback.

D. Dual Coordinate Descent (DCD) Method

The DCD method minimizes the dual objective one BS price at a time while updating the auxiliary variable ν, enabling asynchronous price updates with guaranteed convergence of the iterative objective sequence.

  • Coordinate updates: DCD fixes all but one dual variable and chooses each µ_j so the left derivative is nonpositive and the right derivative is nonnegative.The coordinate objective combines a continuous piecewise-linear function with an exponential function.
  • Algorithm: Each user selects the BS maximizing utility minus price, while BS prices are iteratively adjusted to balance loads.This provides the operational interpretation of the DCD updates.
  • Algorithm: The algorithm alternates coordinate-wise µ_j updates, a ν update, and recovery of user-BS associations from the utility-minus-price rule.Ties are resolved when necessary after the dual objective converges.
  • Asynchronous implementation: BSs may update prices in arbitrary order without synchronization, and every dual update makes the objective nonincreasing.The method is therefore guaranteed to converge as an iterative algorithm.
  • Scope and limitation: DCD is not guaranteed to reach the global dual optimum because the dual objective is nondifferentiable, and a duality gap can remain.Its convergence point nevertheless provides fairly good solutions to the original association problem.
  • Relation to prior methods: The method generalizes the auction algorithm’s one-to-one assignment setting to the N-to-one BS association problem.The connection is made through the paper’s interpretation of BS association as a generalized assignment problem.

E. Duality Gap Bound

The dual coordinate descent analysis provides an analytical bound on the duality gap for BS association, while pricing-based association and power control address load imbalance under changing transmit powers.

  • Duality-gap analysis: The DCD objective has a nonzero duality gap because integer constraints prevent guaranteed global optimality, but the dual function remains an upper bound.The bound is tightest when the dual variables are dual optimal.
  • Duality-gap analysis: The optimal duality gap can be expressed analytically in closed form.
  • Duality-gap analysis: A BS contributes no duality gap when its user count satisfies k_j = e^(µ_j−ν−1).With ties, the gap is minimized by choosing k_j as close to this value as possible.
  • Iterative association and power control: The joint association and power-control method alternates pricing-based association under fixed powers with utility-maximizing power control under fixed association.The association step targets load balancing, while power control targets interference mitigation.
  • Iterative association and power control: Max-SINR association can exacerbate load imbalance during power-control iterations, whereas pricing-based association reduces users at a heavily priced BS.When one BS raises power because it serves many users, max-SINR can attract still more users to it.

B. Direct Dual Optimization for Joint BS Association and Power Control

The paper develops a direct dual approach for joint BS association and power control by alternating association and power optimization, using multiple starting points to approach the nonconvex problem’s global solution. It is more complex than the iterative method but serves as a benchmark that the simpler method nearly matches.

  • Direct dual optimization: The direct dual method optimizes BS association and transmit power jointly under fixed dual variables, but the resulting problem is nonconvex and discrete.
  • Direct dual optimization: The proposed solver alternates association optimization at fixed power with power optimization at fixed association.Because this need not reach a global optimum, multiple initial points are used to improve the solution.
  • Dual optimization: Bisection on each µ_j implements the dual coordinate-descent update when the straightforward fixed-power coordinate step no longer applies.
  • Dual optimization: Multiple random starting points provide a way to find a near-globally optimal solution for the overall joint problem.
  • Comparison: The direct dual method has much higher complexity, while simulations indicate that the simpler iterative association and power-control method performs very close to it.
  • MIMO setting: In the MIMO formulation, each BS has a fixed total power constraint, and up to M_j users can be spatially multiplexed simultaneously.

1) Beamforming via WMMSE with Fixed BS Association:

For fixed BS association, the beamforming problem is solved through an equivalent WMMSE formulation, while prior joint methods use penalization that can impose higher complexity and heuristic parameter dependence. The proposed design instead decouples association from beamforming.

  • Fixed-association beamforming: With fixed user-BS association, weighted rate-sum maximization reduces to a beamforming design problem solvable through an equivalent WMMSE problem.
  • Prior joint optimization: The prior penalized WMMSE approach incorporates BS association at each time instant but does not guarantee that association remains fixed over time.
  • Prior joint optimization: The prior joint BS-association WMMSE method requires updates across every BS-user pair and depends heavily on a heuristically chosen penalty parameter.
  • Proposed decoupling: The proposed approach decouples BS association and beamformer optimization into two subproblems, reducing computational complexity and avoiding frequent BS handover.

1) BS Association Stage:

The first stage estimates channel quality through a SISO representation of the MIMO channel, then applies joint association and power control before selecting users for the WMMSE stage. Candidate reduction substantially lowers beamforming complexity.

  • BS Association Stage: The association stage applies joint BS association and power control using a SISO channel representation scaled by each BS’s antenna count.The optimized powers assist association and scheduling, then are further optimized during beamforming.
  • Scheduling and Beamforming Stage: The WMMSE stage operates only on selected users, rather than updating beamformers for every potential user within each cell.
  • BS Association Stage: The algorithm selects S_j potential users at each BS according to estimated weighted rate ω_i x_ij R~_ij, with S_j greater than M_j.
  • Complexity Analysis: Under fixed association, conventional WMMSE has per-step complexity O(K^2MN^2 + K^2M^2N + KM^3 + KN^3).Here K is the total number of users, with equal BS antenna count M and user antenna count N.
  • Complexity Analysis: The prior joint association-WMMSE method increases the WMMSE user factor by L, producing complexity O(L^2K^2MN^2 + L^2K^2M^2N + LKM^3 + LKN^3).
  • Complexity Analysis: The proposed method reduces each WMMSE iteration to O(S^2MN^2 + S^2M^2N + SM^3 + SN^3), where S = Σ_j S_j and S ≪ K ≪ LK.The first-stage complexity is ignored because it is typically very fast.

VI. SIMULATION RESULTS

Simulations compare distributed dual coordinate descent (DCD), subgradient, max-SINR, and power-control methods for proportional-fair BS association. DCD converges rapidly under fixed powers, while iterative DCD with power control improves utility and avoids the excessive complexity of direct dual optimization.

  • BS Association Under Fixed Powers: 56 iterations brought DCD within 10^-1 of the optimum, whereas subgradient convergence was sensitive to parameter settings.The fixed-power experiment used a 7-cell wrap-around SISO network with one macro-BS, three pico-BSs, and 30 users per cell.
  • BS Association Under Fixed Powers: The 50th-percentile user rate increased by about 33% over max-SINR after 56 iterations.Both DCD and subgradient improved low-rate users through traffic off-loading to pico-BSs; subgradient remained parameter dependent.
  • BS Association Under Fixed Powers: DCD and two subgradient variants achieved almost identical numerical utility, while subgradient-2 and max-SINR were inferior.The reported duality-gap bound was about 0.45, indicating DCD was close to the global optimum in this example.
  • Joint BS Association and Power Control: With power control, alternating DCD and power optimization improved utility incrementally, whereas max-SINR utility decreased after the second iteration.The power-control problem is nonconvex, so convergence to a local optimum is expected.
  • Joint BS Association and Power Control: Direct dual optimization performed best but required approximately 1000 power-control calls per dual-variable update, versus one call per iteration for iterative DCD.Better-performing methods suppressed overly high macro-BS transmit power and generally associated more users with pico-BSs.

C. Joint BS Association and Beamforming

The paper evaluates a two-stage BS association and WMMSE beamforming method against max-SINR and network-wide joint WMMSE baselines. It achieves substantial gains over max-SINR and nearly matches the complex benchmark while keeping association fixed.

  • Joint BS Association and Beamforming: The two-stage method substantially improved max-SINR association in a MIMO network with four antennas at each BS and two antennas per user.The candidate-user parameter S was tested at 4, 6, and 8.
  • Joint BS Association and Beamforming: The utility gain was almost doubled when S = 8, with only marginal improvement beyond S = 8.This result was reported for the case with four transmit antennas.
  • Joint BS Association and Beamforming: The comparison with joint BS association and WMMSE used a smaller network because network-wide WMMSE was impractical on a 7-cell, 28-BS network.The smaller simulation had 3 macro-BSs, 4 pico-BSs, and 105 user terminals.
  • Joint BS Association and Beamforming: Joint BS association and WMMSE caused approximately 24 association switchings per beamforming update and involved about one-quarter of users in handover per time slot.The two-stage method kept BS association completely fixed.

APPENDIX A PROOF OF PROPOSITION 1

The appendix establishes a performance bound for the primal solution recovered from optimized dual variables and describes Newton’s method for power optimization under fixed association. It uses duality and local derivative-based updates to support the algorithmic analysis.

  • Proof of Proposition 1: The DCD limit defines dual variables, recovers the primal association solution with tie-breaking, sets each BS load from its assigned users, and computes corresponding user rates.The recovered quantities are used in the subsequent bound derivation.
  • Proof of Proposition 1: The proof uses association and price optimality conditions to derive the relevant inequalities before applying weak duality.Weak duality supplies g(µ, ν) ≥ fo(X∗, R∗) for the optimal primal solution.
  • Newton’s Method for Power Optimization: For fixed user association, the appendix formulates power optimization as maximizing the sum of log user rates.The objective is evaluated as f_power(p), with derivatives taken with respect to each BS power.
  • Newton’s Method for Power Optimization: Newton’s method uses only diagonal Hessian entries to reduce inversion complexity, modifies the step for incremental updating, and selects step size by backtracking line search.The overall update applies the resulting steps to all BS power variables.
Loading 1407.4694v2…