We provide distributed algorithms for the radio resource allocation problem in multicell downlink multi-input single-output systems. Specifically, the problems of (1) minimizing total transmit power subject to signal-to-interference-plus-noise ratio (SINR) constraints of each user and (2) SINR balancing subject to total transmit power constraints are considered. We propose a consensus-based distributed algorithm and the fast solution method via alternating the direction method of multipliers. First, we derive a distributed algorithm for minimization of total transmit power. Then, in conjunction with the bracketing method, a distributed algorithm for SINR balancing is derived. Numerical results show that the proposed distributed algorithms achieve the optimal centralized solution.
The online version of this article (doi:10.1186/1687-1499-2014-1) contains supplementary material, which is available to authorized users.
Competing interests
The authors declare that they have no competing interests.
1 Introduction
We provide distributed algorithms for the problem of resource allocation for multicell downlink systems with linear precoding. The base stations (BSs) are assumed to have multiple antennas while all the users are equipped with single antenna. Full channel state information is assumed to be available at both the BSs and the users, and all the users share the same frequency bandwidth. Under this setting, we consider the following two optimization problems: P1 - minimization of the total transmission power subject to minimum signal-to-interference-plus-noise ratio (SINR) constraints of each user, and P2 - SINR balancing subject to total transmit power constraint of BSs.
Several centralized algorithms for problems P1 and P2 have been proposed in the literature. See, e.g.,[1‐6] for problem P1 and[7‐10] for problem P2. Unfortunately, the centralized method is not practical for the resource allocation due to high overhead required for collecting all channel state information at the central processing unit. Therefore, to share the workload of the central controller and to overcome impelling backhaul overhead, the distributed algorithm is desirable in practice.
Anzeige
Distributed methods for problem P1 for multiple-input and single-output (MISO) multicell wireless systems have been proposed in[11‐15]. The algorithm in[11] is based on uplink-downlink duality, where the minimum power downlink beamformers designing problem is solved using a dual uplink problem. The algorithm in[11] is a multicell generalization of the algorithm proposed in[16] for the single-cell case. In[12] dual decomposition method is adopted, and the algorithm in[13] is based on primal decomposition. Both in primal and dual decomposition methods[17], the master problem is solved using an iterative method such as the subgradient method[18]. Even though problem P1 is a convex problem and can be easily solved via primal or dual decomposition (see,[12, 13]), the convergence speed of those algorithms are slow and highly sensitive on the subgradient step size[18]. A game theoretic approach is considered in[14].
Problem P2 is a quasiconvex problem[16]. Thus, the centralized method based on bisection search[19] is commonly used, e.g.,[10, 16]. Combining the bisection search and the uplink-downlink SINR duality, a distributed algorithm is proposed in[20]. The algorithm in[20] is a hierarchical iterative algorithm which consists of outer and inner iterations, where the bisection search is carried out in the outer iteration and uplink-downlink SINR duality is used for the inner iteration.
The alternating direction method of multipliers (ADMM) is a simple but powerful algorithm that is well suited to distributed convex optimization. ADMM combines the benefits of dual decomposition and augmented Lagrangian methods[21]. Hence, ADMM is numerically stable than dual decomposition and hence suitable for many practical optimization problem[21]. Due to superior stability properties and decomposability, ADMM has been applied to a wide rage of applications, such as compressed sensing[22], image restoration[23], signal processing[15, 24, 25], etc.; see[21] for the recent survey. In many applications, the ADMM method has been observed to converge fast[21, 26, 27]; and when the objective function is strongly convex and Lipschitz continuous, ADMM can even guarantee the liner rate of convergence[28, 29].
The main contribution of the paper is to propose consensus-based distributed algorithms for problems P1 and P2, and the fast solution method via ADMM[21]. The ADMM turns the original problem into a series of iterative steps, namely, local variable update, global variable update, and dual variable update[21]. The local variable and dual variable updates are carried out independently in parallel by all BSs, while the global variable update is carried out by BS coordination. In this paper, we first derive distributed algorithm for problem P1. Then, we extend the formulation of problem P1 to derive the distributed algorithm for problem P2. In particular, we recast the problem into a more tractable form and combine bracketing method (e.g., golden ratio search)[30, 31] with ADMM to derive the distributed algorithm for problem P2.
Anzeige
Recently, for problem P1, by considering the uncertainty in the channel measurements, an algorithm based on ADMM has been proposed in[15]. In our paper, we consider perfect channel state information (CSI) and use the consensus technique to solve the problem. Then, we apply ADMM to derive the distributed algorithm. The consensus technique can be easily decomposed into a set of subproblems suitable for distributed implementation[21, 24]. Hence, the algorithm formulation in this paper is more intuitive than that provided in[15]. It is worth noting that this paper extends our recent work[32] to SINR balancing problem (i.e., problem P2). In addition, for problem P1, we show that the proposed distributed algorithm converges to the optimal centralized solution. Moreover, for problem P1, we also provide a method to find the ADMM penalty parameter that leads faster convergence of the algorithm.
Note that problem P2 is a quasiconvex problem. To the best of our knowledge there is no convergence theory to the ADMM method for a quasiconvex problem. However, if each step of the ADMM iteration is tractable, the ADMM algorithm can still be used to derive (possibly suboptimal) distributed methods for problem P2[21], Chapter 9. Though these methods are not provably optimal, our numerical results show that the proposed algorithm converged to the optimal solution in all simulated cases.
The remainder of this paper is organized as follows. The considered MISO system model and problem formulation are described in Section 2. The distributed algorithm for sum power minimization (P1) is derived in Section 3. Next, in Section 4, we derive the distributed algorithm for SINR balancing problem (P2). The numerical results are presented in Section 5, and Section 6 concludes our paper.
Notations: All boldface lower case and upper case letters represent vectors and matrices, respectively, and calligraphy letters represent sets. The notation denotes the set of complex T-vectors, |x| denotes the absolute value of the scalar x, ∥x∥2 denotes the Euclidean norm of the vector x, I denotes the identity matrix, and denotes the complex circular symmetric Gaussian vector distribution with mean m and covariance matrix C. The superscripts (·)H and (·)⋆ are used to denote a Hermitian transpose of a matrix and a solution of an optimization problem, respectively.
2 System model and problem formulation
A multicell MISO downlink system, with N BSs each equipped with T transmit antennas, is considered. The set of all BSs is denoted by, and we label them with the integer values n = 1, …, N. The transmission region of each BS is modeled as a disc with radius RBS centered at the location of the BS. Single data stream is transmitted for each user. We denote the set of all data streams in the system by, and we label them with the integer values l = 1, …, L. The transmitter node (i.e., the BS) of l th data stream is denoted by tran(l), and the receiver node of l th data stream is denoted by rec(l). We have, where denotes the set of data streams transmitted by n th BS. Note that the intended users of the data streams transmitted by each BS are necessarily located inside the transmission region of the BS (see Figure1).
The antenna signal vector transmitted by n th BS is given by
(1)
where and represent the information symbol and the transmit beamformer associated to l th data stream, respectively. We assume that dl is normalized such that E|dl|2 = 1. Moreover, we assume that the data streams are independent, i.e., for all l ≠ j, where.
The signal received at rec(l) can be expressed as
(2)
where is the channel matrix between tran(j) and rec(l), and nl is circular symmetric complex gaussian noise with variance. Note that the second right hand term in (2) represents the intra-cell interference and the third right hand term represents the out-of-cell interference. The received SINR of l th data stream is given by
(3)
where represents the power of the out-of-cell interference from n th BS to rec(l).
The out-of-cell interference term in (3) (i.e.,) prevents resource allocation on an intra-cell basis and demands BS cooperation/coordination. To avoid unnecessary coordination between far apart-located BSs, we make the following assumption: transmission from n th BS interfere the l th data stream (transmitted by BS b ≠ n) only if the distance between n th BS and rec(l) is smaller than a threshold Rinta. The disc with radius Rint centered at the location of any BS is referred to as the interference region of the BS (see Figure1). Thus, if n th BS located at a distance larger than Rint to rec(l), the associated znl components are set to zerob. Based on the assumption above, we can express Γl as
where is the set of out-of-cell interfering BSs that are located at a distance less than Rint to rec(l). For example, in Figure1a, we have,, and for all l ∈ {1, 3, 4, 5, 6, 7}. Moreover, it is useful to define the set of all data streams that are subject to the out-of-cell interference, i.e.,. For example, in Figure1a, we have.
The total transmitted power of the multicell downlink system can be expressed as
Assuming that the SINR Γl is subject to the constraint Γl ≥ γl for each user, the problem of minimizing the total transmitted power (i.e., P1) can be expressed as
(4)
with variables andc.
Providing fairness among the users with per BS power constraint (i.e.,) is another important resource allocation problem. One wayd of providing fairness among the users is by maximizing the minimum SINR (i.e., P2)[16], which can be formulated as
(5)
where the variables are and. Finally, to improve the readability of the paper, we summarize a list of sets used in this paper in Table1.
Table 1
Summary of a list of sets
Set
Description
Set of all BSs
Set of all data streams
Set of data streams transmitted by n th BS
Set of out-of-cell BSs interfering to l th data stream
Set of all data streams that are subject to the out-of-cell
interference
Set of links for which BS n acts as the out-of-cell interferer
Set of links in BS n that are affected by the out-of-cell
interference
3 Sum power minimization
In this section, we derive a distributed algorithm for problem (4), i.e., P1. First, we equivalently reformulate the original problem (4) in a form of global consensus problem. Then, we derive the proposed distributed algorithm based on ADMM[21].
3.1 An equivalent reformulation: sum power minimization
We start by reformulating sum power minimization problem (4) as
(6)
where the variables are and. Problems (4) and (6) are equivalent as it can be easily shown (e.g., by contradiction) that the second inequality holds with equality at the optimal point.
Recall that in problem (6) represents power of the out-of-cell interference caused by n th BS at rec(l), and hence, variable znl couples exactly two BSs (i.e., BS n and BS tran(l)). We use consensus technique to distribute problem (6) over the BSs. The method consist of introducing local copies of the coupling variables znl for all, at each BS (see Figure2).
Figure 2
Illustration of BS coupling, and introducing local copies to decouple a problem. BS 2 and BS 3 are coupled with BS 1 due to coupling variables z2l and z3l, respectively. To distribute the problem, local copy x1, 2l of z2l at BS 1 and local copy x2, 2l of z2l at BS 2 are introduced. Similarly, local copy x1, 3l of z3l at BS 1 and local copy x3, 3l of z3l at BS 3 are introduced.
×
Let us define xk,nl as the local copy of znl at BS k. Thus for each znl, we make two local copies, i.e., xn,nl at BS n and xtran(l),nl at BS tran(l). Then, problem (6) can be written equivalently in a global consensus form as
(7)
with variables,, and. Note that in the SINR constraints of problem (7), we have replaced zbl by the local copy xn,bl and used. In the second inequality constraints of (7), we have replaced znl by the local copy xn,nl. The last set of equality constraints of (7) are called consistency constraints, and they enforce the local copies {xk,nl}k ∈ {n, tran(l)} to be equal to the corresponding global variable znl.
Problem (7) is not a convex problem. However, by following the approach of[16], Section IV-B, problem (7) can be equivalently cast in the form of convex problem. To do this, let us define the matrix obtained by concatenating the column vectors ml. Then, by following the approach of[16], Section IV-B, problem (7) can be equivalently reformulated in the form of convex problem as
(8)
with variables,, and, where vector, the matrix hjl in the second set of constraints denotes the channel from BS n to link l (i.e., the index j in the second set of constraints denotes an arbitrary link in), and the notation ≽SOC denotes the generalized inequalities with respect to the second-order cone[16, 19].
In problem (8), the objective function and the first set of inequality constraints are separable in (one for each BS). Also, it can be easily shown that the second set of inequality constraints of (8) are separable in. To do this, let us denote the set of links for which BS n acts as an out-of-cell interferer, i.e.,. Then, by noting that the sets, and are identical, the second set of inequality constraints of (8) can be written as
(9)
which is separable in. Observe that without the consistency constraints, problem (8) can now be easily decoupled into N subproblems, one for each BS.
We next express problem (8) more compactly. To do this, we first express the consistency constraints of problem (8) more compactly by using vector notations, which denote a collection of the local and global variables associated with BS n. By using the equivalence between the sets and, let us express the consistency constraints of problem (8) as
(10)
In the first set of equalities of (10), is a set of local variables that are associated with BS n. Similarly, to find a set of local variables that are associated with BS n in the second set of equalities of (10), let us define the set of links in BS n that are affected by the out-of-cell interference, i.e.,. Then, by noting that the set, we can rewrite (10) as
(11)
Clearly, in the second set of equalities of (11)e, is a set of local variables that are associated with BS n.
We now denote (11) compactly using vector notation. Let us define vectors xn and zn asf
(12)
Then, (11) can be compactly written as
(13)
Note that xn is a collection of the local variables that are associated with BS n, and zn is a collection of the global variables that are associate with the components of variable xn.
Furthermore, for the sake of brevity, let us define the following set
(14)
and the following function
(15)
Then by using notations (13), (14), and (15), consensus problem (8) can be written compactly as
(16)
where the variables are Mn, xn, and zn for all.
3.2 Distributed algorithm via ADMM: sum power minimization
In this section, we derive distributed algorithm for problem (16). The proposed algorithm is based on ADMM[21]. We start by writing the augmented Lagrangian[33] for problem (16) as
(17)
where are the dual variablesg associated with the equality constraints of (16), and ρ>0 is a penalty parameter that adds the quadratic penalty to the standard Lagrangian L0 for the violation of the equality constraints of problem (16).
Each iteration of ADMM algorithm consists of the following three steps[21]
(18)
(19)
(20)
where superscript i is the iteration counter. Steps (18) and (20) are completely decentralized, and hence, they can be carried out independently in parallel in each BS. Note that each component of zn couples two local variables that are associated with the adjacent BSs (see, consistency constraint of problem (8))h. Thus, step (19) requires to gather the updated local variables and the dual variables from all N BSs. In the sequel, we first explain in detail to solve the ADMM steps in (18) and (19). Then, we summarize the proposed ADMM based distributed algorithm.
The local variable update in (18) is a solution of the following optimization problem
(21)
with variables Mn and xn. Here, we write instead of to lighten the notation. Let vn = (1 / ρ)un (i.e., vn is a scaled dual variable). Then by using notations (14) and (15), problem (21) can be equivalently expressed as
(22)
with variables and xn, where is a subset of xn (see (12)), the matrix hjl in the second set of constraints denotes the channel from BS n to link l (i.e., the index j in the third set of constraints denotes an arbitrary link in), and the notation ≽SOC denotes the generalized inequalities with respect to the second-order cone[16, 19]. Note that in the objective function of (22)i, we have dropped a constant term since it does not effect the solution of the problem.
Moreover, by writing problem (22) in the epigraph form, and then following the approach of[16], Section IV-B, problem (22) can be equivalently reformulated in the form of second-order cone program (SOCP) as
(23)
with variables t, Mn, and xn. Let us denote t⋆,, and the solutions of problem (23), then the update and.
Now, we turn to the second step of ADMM algorithm and provide a solution for the global variable update (19). The update is a solution of the following optimization problem
(24)
with variable. By using the notations in (12), and further noting equalities (13) and the equality constraints of problem (8) are equivalent, problem (24) in the components of xn, zn, and un can be expressed as
(25)
with variable, where are the dual variables associated with the equality constraints of problem (7)j.
Problem (25) decouples across znl, since the objective function is separable in znl for all. Moreover, the objective function of problem (25) is quadratic in znl. Hence, by setting the gradient of (25) with respect to znl equal to zero, we can get the solution which can be expressed as
(26)
for all. Therefore, the update for all. Moreover, by substituting in (20)k, we can show that the sum of the dual variables is equal to zero. Thus, the update further simplifies to
(27)
for all. Hence, the global variable update is simply the average of its local copies and.
Finally, we summarize the proposed ADMM-based distributed algorithm for sum power minimization problem (8) in Algorithm 1.
Algorithm 1 Proposed ADMM-based distributed algorithm for sum power minimization
The first step initializes the algorithm. Step 2 updates the local variables of each BS by solving problem (23). Step 2 is completely decentralized. In step 3, the neighboring BSs that are coupled by variable znl, i.e., BS n and BS tran(l), exchange their local copies and. In step 4, each BS update the global variable. Note that the global variable update in its component is simply the average of the local copies (27). In step 5, the dual variables are updated by each BS, by solving (20). Step 6 checks the stopping criterial, and the algorithm stops if the stopping criteria is satisfied. Otherwise, the algorithm continues in an iterative manner. A method to find the feasible solution at each iteration of Algorithm 1 is provided in Section 3.3. Note that in deriving Algorithm 1, we have considered perfect CSI in all relevant channels between BSs and receivers. The impact of imperfect CSI in the derivation of the algorithm can be found in[15].
3.3 Finding feasible solution at each iteration of Algorithm 1
In many practical applications, we have to stop the distributed algorithm after a finite number of iterations before converging the algorithm. On the other hand, the intermediate solutions provided by Algorithm 1 do not necessarily result feasible solution. In particular, the SINR constraints of problem (4) may not hold since the local copies xn,nl and xtran(l),nl that correspond to the global variable znl for all may not be equal. Thus, we can get SINR Γl ≤ γl as a solution of step 2 of Algorithm 1 for some.
At the cost of solving one additional subproblem by each BS in each iteration, we can find a set of feasible beamformers Mn for all. For this, in order to make the local copies xn,nl and xtran(l),nl equal, we fix them to the consensus value (i.e., and) for all. Then, solve problem (23) in variables t and Mn by each BS, which can be expressed as
(28)
where. Note that at iteration i the set of beamformer is feasible for the original problem (4), if problem (28) is feasible for all BSs.
3.4 Convergence of Algorithm 1 to the global optimum of problem P1
The convergence of Algorithm 1 to the global optimal solution of problem P1 (i.e., problem (4)) can be established by using proposition[34], Proposition 4.2.
First, by applying proposition[34], Proposition 4.2 to problem (16), we can show that the ADMM Algorithm 1 converges to the global optimal solution of problem (16) (note that problem (16) is compact representation of problem (8)). Next, we note that the phase of the optimization variable in problems (8) and (4) do not change the objective and the constraints of both problems. Thus, the optimal solution obtained by Algorithm 1 for problem (8) is also optimal for problem (4) (i.e., problem P1).
4 SINR balancing
In this section, we derive a distributed algorithm for problem (5), i.e., P2. As before in the sum power minimization problem, we begin by reformulating problem (5) in the global consensus form. Then, we apply ADMM[21] to derive the distributed algorithm.
4.1 An equivalent reformulation: SINR balancing
We start by equivalently reformulating SINR balancing problem (5) in the epigraph form[19] as
(29)
with variables γ,, and.
We now follow a similar approach as in the Section 3.1 to express problem (29) in a global consensus form (i.e., we introduce the local copies of the coupling variables γ and znl for each BS). Since the SINR variable γ couples all BSs via a SINR constraints, we introduce local copies αn for each BS such that αn = γ for all. For the out-of-cell interference variable znl, we introduce local copies xk,nl and xtran(l),nl, respectively, for BS n and BS tran(l) as in problem (7). Then, problem (29) in the global consensus form can be expressed equivalently as
(30)
with variables γ,,,, and. Note that in the second set of inequality constraints, we use the equivalence between the sets and (see (10)).
Now, we express problem (30) more compactly. Note that except the third inequality constraints and the last equality constraints of problem (30), the constraint set of problem (30) is identical to that of problem (7). Hence, we can use variables Mn, xn, and zn to define the set Cn as given in (31)
(31)
and the following indicator function In(Mn, xn, αn)
(32)
Then, by using notations (31) and (32), consensus problem (30) can be rewritten compactly as
(33)
with variables γ and. Furthermore, by noting that (from the second equality constraints of (33)), problem (33) can be expressed equivalently as
(34)
with variables γ and.
4.2 Distributed algorithm via ADMM: SINR balancing
To derive the ADMM algorithm, we first form the augmented Lagrangian[33] of problem (34). Let un and vn be the dual variables associated with the first and second consensus constraints of problem (34), respectively. Then, the augmented Lagrangian can be written as
(35)
where ρ > 0 is the penalty parameter. Each iteration of ADMM consists of the following steps[21]
(36)
(37)
(38)
(39)
Note that the first step is completely decentralized. Each BS updates the local variables by solving the following optimization problem
(40)
with variables αn, Mn, and xn. Let vn = (1 / ρ)un and λn = (1 / ρ)vn, then by combining the linear and quadratic terms of the objective functionm, problem (40) can be written as
(41)
with variables αn, Mn, and xn. Note that in the objective function of (41), constant terms and are dropped, since they do not affect the solution of the optimization problem.
Problem (41) is not a convex problem, due to the indicator function In(Mn,xn,αn) is a function of nonconvex set (see (31)). However, for fixed αn, set is a convex set, and hence, problem (41) can be solved easily. Therefore, to solve problem (41), we first find the optimal and then find and.
For fixed αn, let us denote the optimal value function of problem (41) as
(42)
(43)
where (43) follows by noting that αn / N and are independent of the optimization variables Mn and xn. Then, the optimal value of problem (41) is given by
(44)
For ease of presentation, let us express the optimal value function p(αn) in (43) as
(45)
where is the optimal value of the following optimization problem
(46)
with variables xn and. Note that to write (46), we have used the notations defined in (31) and (32).
Let the interval denote the range of feasible αn for problem (46). Note that the optimal value is a nondecreasing function of (see Appendix 1). Based on this observation, in Appendix 1, we have provided the condition for which p(αn) is a unimodal function and propose the bracketing method[30, 31] to solve problem (44). In Algorithm 2, we summarize the bracketing method (golden ratio search)[30], Section 8.1 to find the optimal for problem (44).
Algorithm 2 Bracketing method to find optimal for problem (44)
Next, we find and that are associated with by solving problem (46). By writing problem (46) in the epigraph form, and then following the approach of[16], Section IV-B, problem (46) can be formulated equivalently in the form of SOCP as
(47)
with variables t, xn, and Mn, where is a subset of xn (see (12)), the matrix hjl in the third set of constraints denotes the channel from BS n to link l (i.e., the index j in the third set of constraints denotes an arbitrary link in). Note that to write problem (46) in the SOCP form (47), we first took the square root of the objective function of (46). Hence, the optimal value of problem (46) is given by t⋆2 (i.e.,), where t⋆ is the solution of problem (47).
We now turn to the second step of ADMM in (37), where the global variables and γi+1 are updated. By dropping the constant terms which do not affect the solution, problem (37) can be written as
(48)
with variables and γ.
Problem (48) is separable in variables and γ. Note that minimization of problem (48) with respect to yields problem (24), and hence, the solution is given by (27). Here, we provide the solution for γ. Minimization of problem (48) with respect to γ yields the following optimization problem
(49)
Problem (49) is an unconstrained quadratic optimization problem in γ. Therefore, by setting the gradient of problem (49) with respect to γ equal to zero, we can get
(50)
Hence, the update γi+1 = γ⋆. Moreover, by substituting γi+1 in (39), we can show that the sum of the dual variables is equal to zero. Thus, the update γi+1 (i.e., (50)) further simplifies to
(51)
We now summarize the proposed ADMM-based distributed algorithm for SINR balancing problem in Algorithm 3.
Algorithm 3 Proposed ADMM-based distributed algorithm for SINR balancing
The computational steps of Algorithm 3 is similar to that of Algorithm 1. As in Algorithm 1, step 1 initializes the algorithm. Step 2 updates the local variables. In step 3, BSs exchange their local copies to update the global variables. Local copies and are exchanged between the adjacent BS n and BS tran(l), while local copy αn is broadcasted to all other BSs. Steps 4 and 5 updates the global and dual variables, respectively. Note that steps 2, 4, and 5 are completely decentralized. Step 6 checks the stopping criterian. A method to find the feasible solution at each iteration of Algorithm 3 is provided in next section.
4.3 Finding feasible solution at each iteration of Algorithm 3
Note that at each step of Algorithm 3, the locally obtained SINR αn for all are not necessarily balanced (i.e., αn for all are not necessarily equal). So, we can take the global variable γi, which is the average of αn for all, as the intermediate solution of Algorithm 3. However, due to the difference in the local copies at BS n and at BS tran(l), and the maximum transmit power constraint of the BSs, the intermediate solution γi may not be feasible for all BSs.
Therefore, it is necessary to check the feasibility of γi to use it as the intermediate solution at each step of Algorithm 3. The SINR γi is feasible for BS n, if their exist a feasible solution of problem (47) for αn = γi and given out-of-cell interference value xn. Thus, we set αn = γi and for all (i.e., αn and xn are set equal to the consensus value). Then, check the feasibility of problem (47) by each BS in between steps 4 and 5 of Algorithm 3, which is equivalent to the following SOCP feasibility problem
(52)
with variable, where is a subset of xn (see (12)), the matrix hjl in the third set of constraints denotes the channel from BS n to link l (i.e., the index j in the third set of constraints denotes an arbitrary link in). Note that γi is feasible for the original problem (5) only if problem (52) is feasible for all BSs. Thus, in Algorithm 3, we can update the feasible SINR as
(53)
where.
5 Numerical example
In this section, we numerically evaluate the performance of proposed Algorithms 1 and 3. In our simulations, two multicell wireless networks as shown in Figure1 are considered. In the case of first network (i.e., Figure1a), there are N = 2 BSs with T = 4 antennas at each one. The distance between the BSs is denoted by DBS. In the case of second network (i.e., Figure1b), there are N = 7 BSs with T = 6 antennas at each one. The BSs are located such that they form the hexagon, and the distance between the BSs is denoted by DBS. We assume that BSs have circular transmission and interference regions, where the radius of the transmission region of each BS is denoted by RBS, and the radius of the interference region of each BS is denoted by Rint. For simplicity, we assume 4 users per cell in the first network, and three users per cell in the second network. The location of users associated with BSs is arbitrarily chosen as shown in Figure1.
We assume an exponential path loss model, where the channel matrix between BSs and users is modeled as
where djl is the distance from the transmitter of data stream j (i.e., BS tran(j)) to the receiver of data stream l (i.e., user rec(l)), d0 is the far field reference distance[35], η is the path loss exponent, and is arbitrarily chosen from the distribution (i.e., frequency-flat fading channel with uncorrelated antennas). Here, we refer an arbitrarily generated set of fading coefficients as a single fading realization.
We assume that the maximum power constraint is same for each BS, i.e., for all, and σl = σ for all. We define the signal-to-noise ratio (SNR) operating point at a distance r as
(54)
In our simulations, we set d0 = 1, η = 4, σ2 = 1, p 0max / σ2 = 45 dB, SNR(Rint) = 0 dB, SNR(RBS) = 5 dB, and DBS = 1.5 × RBS.
To illustrate the convergence behavior of Algorithm 1, we consider a single fading realization and run the algorithm for both networks shown in Figure1. For a comparison, we consider a dual decomposition-based distributed algorithm (DDA) proposed in[12]. For DDA[12], we consider fixed step size α to solve the master problem (see in[12]), which is based on the subgradient method[18].
Figure3 shows the normalized power accuracy |pi - p⋆| / p⋆, where pi is the objective value at i th iteration, and p⋆ is the optimal objective value obtained by using centralized algorithm[16], Section IV. SINR target is set to γl = 5 dB for all. DDA[12] plots are drawn for the subgradient step size α = 10,50,100. For Algorithm 1, the penalty parameter is set to ρ = 0.5β, β, 2β, where β depends on the problem parameters (detailed in Appendix 2) and it is defined as
(55)
Figure 3
Normalized accuracy versus iteration. Normalized power accuracy versus iteration for SINR γl = 5 dB for all: (a) Multicell network 1; (b) Multicell network 2.
×
Results show that the proposed Algorithm 1 converges much faster than DDA[12]. For example, in both multicell networks, Algorithm 1 can achieve normalized power accuracy 10-2 in less than 10 iterations. However, in order to gain the same accuracy (i.e., normalized power accuracy 10-2), DDA[12] requires more than 200 iterations for all simulated cases in both networks. Results also show that Algorithm 1 performs very well for a wide range of values of ρ. Hence, Algorithm 1 is less sensitive to the variation of values of ρ, while the results show that the convergence speed of DDA[12] is quite sensitive to the variation of the subgradient step size α.
In order to see the average behavior of the proposed Algorithm 1, we next consider fading case. Here, we run Algorithm 1 for 500 fading realizations with the algorithm parameter ρ = 2β for both networks shown in Figure1. We first present the feasibility rate of the proposed algorithm, and then, we provide the average performance of the algorithm.
Figure4 shows the feasibility rate of Algorithm 1 versus iteration for SINR target γl = 5 dB and 15 dB for all. For a comparison, we consider DDA[12] with the subgradient step size α = 50. Plots are drawn for the first 50 iterations. Results show that the proposed algorithm can achieves the feasible solution for all channel realizations (for multicell network 1a, the proposed algorithm achieves the feasible solution for all simulated cases; and for multicell network 1b, the feasibility rate improves with the iteration). However, for DDA[12] feasibility rate depends on the network size and the SINR target. For example, in the case of small network and low SINR target (i.e., multicell network 1a and SINR target γl = 5 dB), DDA[12] can achieve the feasible solution for all simulated cases. But, with increase in the SINR target and the network size, the feasibility rate of DDA[12] drops significantly. For example, in multicell network 1b for SINR target γl = 15 dB, DDA[12] is not able to find a feasible solution for any of the fading realization.
Figure 4
Feasibility rate versus iteration. Feasibility rate versus iteration for SINR target γl = 5 dB and 15 dB for all: (a) Multicell network 1; (b) Multicell network 2.
×
Figure5 shows the average sum power versus iteration for multicell network 1a. The SINR target γl is set to 15 dB for all. For a comparison, we consider centralized algorithm[16], Section IV and DDA[12]. DDA[12] plots are drawn for the subgradient step size α = 10, 50. For a fair comparison of Algorithm 1, DDA[12], and the centralized algorithm[16], Section IV, the plots are drawn for the fading realizations that are feasible for all considered algorithms. Results show that the convergence speed of proposed Algorithm 1 compared with DDA[12] is fast and can achieves the centralized solution in less than ten iterations.
Figure 5
Multicell network 1: Average sum power versus iteration. Multicell network 1: Average sum power versus iteration for SINR target γl = 15 dB for all.
×
Figure6 shows the average sum power versus SINR target for multicell network 1b. For a comparison, we consider centralized algorithm[16], Section IV. To note a fair progress of the proposed algorithm for a wide SINR target values, each curve is averaged for the fading realizations that are feasible for all the SINR values. Plots are drawn for the average sum power at iteration number 10 and 50. Results show that the proposed Algorithm 1 can achieve the centralized solution over the wide rage of SINR target values.
Figure 6
Multicell network 2: Average sum power versus SINR. Multicell network 2: Average sum power versus SINR for ρ = 2β.
×
We next evaluate the performance of Algorithm 3 for SINR balancing problem (P2). We, first, consider single fading realization and run the algorithm for both networks shown in Figure1. As a benchmark, we consider centralized optimal algorithm proposed in[16], Section V. In the simulation, we set SNR = 5 dB, and for Algorithm 2, we set ε = 0.1, and for all. Plots are drawn for ρ = 0.5,1,2.
Figure7 shows the progress of the global variable γ by iteration. Note that the global variable γ is the average of SINR values that is obtained independently by all N BSs (see (51)). Results show that for all considered values of ρ, Algorithm 3 can obtain SINR γ that converges to the optimal centralized solution. Since γ is the average of the SINR values obtained independently in all N BSs, the intermediate values of γ may not be feasible for all BSs before the algorithm converges. For example, the value of γ for ρ = 0.5 is clearly infeasible at the iteration step i = {4, 5, 6, 7, 8} in Figure7a. Therefore, to illustrate the convergence of feasible γ, we define the following metric
(56)
where is the best feasible SINR value at i th iteration, and is the feasible SINR at t th iteration (53). Figure8 shows the behavior of by iteration. Results show that Algorithm 3 can obtain the feasible values of γ that converges to the centralized solution. For example, with ρ = 0.5, the algorithm converges to the centralized solution in just tenth iterations in Figure8a.
Figure 7
Evolution of average SINR for different algorithm parameterρ. Progress of global variable γ for SNR = 5 dB: (a) Multicell network 1; (b) Multicell network 2.
Figure 8
Evolution of an average best SINR, that is feasible for all BSs. Feasible SINR versus iteration for SNR = 5 dB: (a) Multicell network 1; (b) Multicell network 2.
×
×
Figure9 shows the SINR for different SNR valueso. Each curve is averaged over 300 fading realizations. In the simulation, penalty parameter ρ is set to 0.5. Plots are drawn for the SINR obtained at iteration number 20, 30, and 50 of Algorithm 3. Results show that the proposed Algorithm 3 can achieve close to the centralized solution over the wide range of SNR values without any tuning of ρ.
Figure 9
Feasible SINR versus SNR. Feasible SINR versus SNR for ρ = 0.5: (a) Multicell network 1; (b) Multicell network 2.
×
6 Conclusion
We have provided distributed algorithms for the radio resource allocation problems in multicell downlink multi-input single-output systems. Specifically, we have considered two optimization problems: P1 - minimization of the total transmission power subject to signal-to-interference-plus-noise ratio (SINR) constraints of each user, and P2 - SINR balancing subject to total transmit power constraint of BSs. We have proposed consensus-based distributed algorithms, and the fast solution method via alternating direction method of multipliers. First, we have derived a distributed algorithm for problem P1. Then, in conjunction with the bracketing method, the algorithm is extended for problem P2. Numerical results show that the proposed distributed algorithms converge very fast to the optimal centralized solution.
Endnotes
a Similar assumptions are made, e.g., in[36] in the context of arbitrary wireless networks.
b The value of Rint is chosen such that the power of the interference term is below the noise level, and this commonly used approximation is made to avoid unnecessary coordinations between distant BSs. The appropriate value of Rint can be chosen to trade off between the required backhaul signaling and the optimality of the solution. The effect of nonzero znl terms can be accurately modeled by changing the statistical characteristics of noise nl at rec(l). However, those issues are extraneous to the main focus of the paper.
c In problem (4) and (5), the set is a collection of znl for which the l th user is inside the interference region of BS n. Thus, the constrained for unconsidered out-of-cell interference term (i.e.,) for l th user that is outside the interference region of BS n is dropped in problem (4) and (5).
d A more general SINR balancing problem which can set priority of users (keeping the SINR values of data stream to a fixed ratios)[6], Section IV-C can be formulated. To simplify the presentation, we consider maximization of the minimum SINR. Note that the proposed decentralized method can be easily generalized to the more general problem considered in[6], Section IV-C.
e Note that. Hence, tran(l) = n for all.
f To simplify the presentation, here we have used a slight abuse of notation, i.e., we have considered that the sets in (12) are ordered.
g Let be the dual variables associated with the equality constraints of problem (8), then by following steps (10) to (12), one can easily express.
h Variable znl (component of zn) couples two local variables xn,nl (component of xn) and xtran(l),nl (component of xtran(l)). Hence, in step (19) to update znl coordination between BS n and BS tran(l) is required.
i For convenience, we can combine the linear and quadratic terms of problem (21) as.
j Note that are the dual variables associate with the consistency constraints of problem (16). By following steps (10) to (12), we can easily show.
k Note that (20) in the components of un, xn, and zn can be expressed as for all.
l In ADMM algorithm, standard stopping criteria is to check primal and dual residuals[21]. However, it is often the case that ADMM can produce acceptable results of practical use within a few tens of iteration[21]. As, finite number of iteration is more favorable for practical implementation, we adopt fixed number of iteration to stop the algorithm.
m For convenience we can combine the terms in problem (40) as a) and b).
n In ADMM algorithm, standard stopping criteria is to check primal and dual residuals[21]. However, it is often the case that ADMM can produce acceptable results of practical use within a few tens of iteration[21]. As, finite number of iteration is favorable for practical implementation, we adopt fixed number of iteration to stop the algorithm.
o For fixed radius RBS in Figure1, different SNRs (i.e., different SNR(RBS)) are obtained by changing in (54).
pThe interval denotes the range of feasible αn for problem (46).
Appendices
Appendix 1
In this appendix, we propose the bracketing method[30, 31] to solve problem (44). Let us start by combining the second (linear) and third (quadratic) terms of (45) as
(57)
Without loss of generality, let us drop the constant term of (57) and simplify it as
(58)
where.
Note that the optimal value is nondecreasing function ofp. To see that, let and be the feasible set of problem (46) for and, respectively. If, then it is easy to see that. Hence, the optimal value for all and. Furthermore, there exists a partition of as such that
(59)
where c is the optimal solution of problem (46) for αn = 0.
Next, we propose to use bracketing method[30, 31] to find the infimum of function p(αn) on the interval. First, in Lemma 1, we show that the function p(αn) is a unimodal function on the interval for the condition: C) θ ≤ ϕ.
Lemma 1.The function p(αn),
(60)
is a unimodal function on the interval for the condition C.
Proof:
1.
For the case θ ≤ 0, the proof is trivial, since p(αn) is a sum of two increasing functions on the interval .
2.
For the case θ > 0, let us partition as . On the interval αn∈ [0, θ], the function takes a constant value c. On the interval , the function is a nondecreasing function. Hence, the function p(αn) is a sum of affine and convex functions on the interval [0,θ], and a sum of nondecreasing and increasing functions on the interval . Thus, the function p(αn) is a unimodal function. □
Lemma 1 implies that for the condition C (i.e., θ ≤ ϕ), the infimum of the function p(αn) can be obtained optimally by using bracketing method[30, 31].
For the case condition C is not satisfied (i.e., ϕ ≤ θ), let us partition as. On the interval αn∈ [0,ϕ], the function p(αn) is a decreasing function (since takes a constant value c, and (αn - θ)2 is a decreasing function). On the interval, the function p(αn) is an increasing function (since is nondecreasing function and (αn - θ)2 is increasing function). On the interval αn ∈ [ϕ, θ], analytically expressing the curvature of p(αn) is difficult, since the curvature of function depends on the numerical parameters. This implies that for the case ϕ ≤ θ, the infimum of the function p(αn) lies on the interval [ϕ, θ], i.e.,
(61)
Thus in the case ϕ ≤ θ (i.e., if condition C is not satisfied), the solution of problem (61) obtained by using bracketing method[30, 31] lies at most (θ - ϕ) away from the optimal solution. However, in all of our numerical simulations, we have always noted that the function p(αn) is a unimodal function. In that case, problem (61) is solved optimally by bracketing method[30, 31]. Moreover, the convergence of the proposed Algorithm 3 (see numerical example, Section 5) to the centralized solution shows that bracketing method can be used to solve problem (44).
Appendix 2
The ADMM method is guaranteed to converge for all values of its penalty parameter ρ[21]. However, the rate of convergence of ADMM algorithm is sensitive to the choice of the penalty parameter ρ. In practice, the ADMM penalty parameter ρ is either tuned empirically for each specific application, or set equal to 1 by normalizing the problem data set[21], Chapter 11. Note that in Algorithm 1, to solve the local variable update (22), we can normalize the problem data (i.e., sum power by normalizing factor βn > 0 and set ρ = 1, which is equivalent to set ρ = βn in Algorithm 1, if the problem data (i.e., sum power is not normalized. To elaborate further, let us express equivalently the local variable update (22) as
(62)
with variables and xn, where βn > 0 is the normalizing factor, is a subset of xn (see (12)), the matrix hjl in the second set of constraints denotes the channel from BS n to link l (i.e., the index j in the third set of constraints denotes an arbitrary link in), and the notation ≽SOC denotes the generalized inequalities with respect to the second-order cone[16, 19].
For problem (62), the optimal choice of βn is. However, before the convergence of Algorithm 1, we do not have optimal beamformers (i.e.,). Thus, in our simulation, to estimate βn, we ignore the interference and noise terms and find beamforming vector that achieves the required SINR threshold γl, which can be expressed as
Hence, the normalizing factor βn for problem (62) can be written as
Furthermore, we find, and set ρ = β for Algorithm 1.
Acknowledgements
This research was supported by the Finnish Funding Agency for Technology and Innovation (Tekes), Nokia Solutions and Networks, Anite Telecoms, Renesas Mobile Europe, and Elektrobit.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Competing interests
The authors declare that they have no competing interests.
, and we label them with the integer values n = 1, …, N. The transmission region of each BS is modeled as a disc with radius RBS centered at the location of the BS. Single data stream is transmitted for each user. We denote the set of all data streams in the system by
, and we label them with the integer values l = 1, …, L. The transmitter node (i.e., the BS) of l th data stream is denoted by tran(l), and the receiver node of l th data stream is denoted by rec(l). We have, where denotes the set of data streams transmitted by n th BS. Note that the intended users of the data streams transmitted by each BS are necessarily located inside the transmission region of the BS (see Figure1).
