Abstract
We revisit the widely investigated problem of maximizing the centralized sumrate capacity in a cognitive radio network. We consider an interferencelimited multiuser multichannel environment, with a transmit sumpower constraint over all channels as well as an aggregate average interference constraint towards multiple primary users. Until very recently only suboptimal algorithms were proposed due to the inherent nonconvexity of the problem. Yet, the problem at hand has been neglected in the largescale setting (i.e., number of nodes and channels) as usually encountered in practical scenarios. To tackle this issue, we first propose an exact mathematical adaptation of the wellknown successive convex geometric programming with condensation approximations (SCVX) to better cope with large systems while keeping the convergence proof intact. Alternatively, we also propose a novel efficient lowcomplexity heuristic algorithm, ELCI. ELCI is an iterative approach, where the constraints are handled alternately based on the special property of the optimal solution, with a particular power update formulation based on the KKT conditions of the problem. In order to demonstrate ELCI’s efficiency we compare it to two stateoftheart algorithms, SCVX, and the recently proposed global optimum approach, MARL. The salient highlight of ELCI is the relatively fast and very good suboptimal performance in largescale CR systems.
Introduction
The throughput maximization in multiuser interferencelimited wireless networks has been a long standing major problem, since it is typically nonconvex due to complicated interference coupling among different links. In particular, we consider a cognitive radio (CR) system composed of secondary users (SUs) and multichannel. We aim to maximize the sumrate capacity of the secondary system, taking into account the average interference constraint at the incumbent primary users (PUs). The centralized radio resource allocation (RRA) is performed at a fusion center (FC).
Although, one of the most widely investigated problems in RRA (see e.g., [1] for an exhaustive review of related problems), only very recently few theoretically optimal algorithms were proposed [24]. In particular Qian et al. proposed one of the very first centralized algorithm MARL in [2]. Before MARL a significant number of suboptimal algorithms were proposed to handle equivalent problems. In order to circumvent the complexity of solving the initial problems, assumptions have often been made to create more tractable ones. High signaltointerferencenoiseratio (SINR) is one of the most employed assumptions (e.g., [5,6]). In the underlay CR setting [7], in addition to the classical transmit power constraint, there exists also the interference constraint (called also interference temperature) toward the primary system. To avoid the complexity of having both constraints, the authors in [8] assume the system to be in such a state that one of the two constraints becomes loose, thus can be omitted (i.e., either transmit powerlimited or primary interferencelimited system). In [9], the multiple access channel approach using successive interference cancelation yields an interferencefree formulation, thus the problem becomes convex. In particular, convex problem formulations are highly desired since the global optimum can be obtained using welldeveloped technics, e.g., the interiorpoint methods (IPM) [10]. However, those assumptions are not always valid. In particular, the opportunistic approach of the CR paradigm in addition to the interference constraint imposed by the primary system can lead to a lowSINR system with heavy interference among SUs, while some SUs can enjoy a surrounding environment free of PUs and other SUs, such that the entire system is neither in the transmit powerlimited or primary interferencelimited state (i.e., in a mix state). In contrast, other works, e.g., [2,1115] have directly handled the problems without major assumptions. Some of the most popular applied approaches are: the iterative waterfilling (e.g., [16,17]), the sequential quadratic programming (e.g., [14]), the Lagrange duality method (e.g., [18]). Many other particular iterative algorithms have been also proposed (e.g., [19]). In particular, the algorithm proposed in [11] has been considered one of the stateoftheart centralized algorithms. The algorithm (referred here as SCVX) is based on a successive convexification of the problem using the socalled condensation approximation. While, all the aforementioned algorithms are only suboptimal, the centralized optimal algorithm [2] Monotonic optimizationbAsed poweR controL (MARL), proposed by Qian et al., is based on recent advances in global optimization, including monotonic optimization and fractional programming. Later, they also proposed a distributed algorithm, aSynchrornous distributEd powEr contRol (SEER) in [20], based on the theory of Gibbs sampling. Note that the authors also proposed in [12] the MAPEL algorithm, very similar to MARL, to cope with the additional minimum rate constraints.
This said, the performance investigations have however been generally neglected in the largescale settings as it is usually encountered in practical scenarios. In particular, as also stated by the same authors in [20], MARL and MAPEL already exhibit a very slow convergence for a problem dimension of less than 8. Thus, large systems become prohibited in complexity. Alternatively, even the wellknow good suboptimal SCVX algorithm exhibits nonnegligible complexity (as later detailed), in particular with multiple channels. Therefore, although theoretically optimal, when it comes to numerical experiments, even with powerful machines, those approaches become quickly limited in terms of the problem size.
Motivated by this issue, we aim to propose algorithms with very good suboptimal performance while exhibiting good scalability. Those familiar with real numerical experiments in RRA are likely to immediately recognize that these two goals are, in general, fairly difficult to achieve together. We first propose a mathematical adaptation of the initial SCVX framework to cope with largescale settings, called LSSCVX, while preserving the SCVX convergence property [11] intact. As a second alternative, taking advantage of an important property of the problem, i.e., the optimal solution lies at the boundary of the feasible region [2], we propose an heuristic iterative algorithm called Enhanced LowComplexity Iterative approach (ELCI). The key idea of ELCI is to handle the different constraints separately, and further use a specific formulation for the iterative power updates based on the Karush–Kuhn–Tucker (KKT) conditions ([10], Section 5.5.3) of the problem. By numerical evaluations we first show that MARL, although theoretically optimal, exhibits large complexity even for small systems; Second, very similar performance to the enhanced LSSCVX can be obtained with ELCI but with much lower complexity.
It is wellknown that the main practical drawback of ELCI, as well as SCVX, MARL or MAPEL is the centralized setting with full channel state information requirement. The current trend is toward distributed approaches for practical implementation purposes and scalability of the network. It is however interesting to quantify the loss of those distributed algorithms compared to the ideal centralized sumrate case. We believe that ELCI as well as the enhanced LSSCVX can provide in practice good approximate benchmarks in the case of largescale problems as advocated by distributed algorithms. Note that although stated as an optimal distributed algorithm, the one proposed in [21] do not cope with multichannel and sumpower constraint over all bands. Similarly, in addition to the fact that the interference constraint is not considered in [20], the adaptation for multichannel and sumpower constraint is not so straightforward, in particular for largescale systems (i.e., see ([20], Eq. 13) for the multilevel integral required in the denominator).
We recently proposed an algorithm in [22] to cope with the sumrate problem. The current article builds on those results while improving the followings; First, the new algorithm has been improved for the case of multiband varying channels. Second, a lowcomplexity and optimal method is proposed to solve for the Lagrange multipliers (LGM), required in the ELCI algorithm. The method being customized for the specific need of the algorithm, the resolution exhibits much faster performance compared to using a general optimization approach (commercial tool) as in [22]. Third, only the initial SCVX provided in [11] was used in [22] such that the numerical experiments were handled with less than only 6 optimization variables. In this article, thanks to LSSCVX, we simulate with over 30 users and 128 channel bands (i.e., 3840 variables). Finally, we also consider the optimal MARL as a comparison for the small size experiments.
The remainder of this article is organized as follows: In Section 2., we define the system model. Section 3. briefly reviews the SCVX approach before describing the LSSCVX adaptation. Section 4. describes the ELCI algorithm. Section 5. reviews the key features of MARL, (LS)SCVX and ELCI. Section 6. provides numerical results to evaluate their performance, before we conclude in Section 7.
Notation: Boldface lowercase letters refer to vectors (x); boldface capital letters refer to matrices (X); single variables are referred to by simple lowercase letters (x); x_{m,n} denotes the variable in the mth row and nth column of matrix X; a constant is defined by a capital letter (X); sets are defined using script capital letters ().
System model
Consider a CR network composed of a set of secondary transmitters and a set of receivers. For the pointtopoint adhoc network each transmitter communicates with its respective receiver, i.e., M=N. In a cellbased (CB) uplink scenario (i.e., infrastructurebased), several transmitters send data to the associated CR base station (BS), i.e., N≤M. The information transmission is assumed over K parallel channels with equivalent bandwidth but possibly experiencing different gains. Let denote the channel index set. Inherent to any CR systems, there is a set of primary transceiver pairs, using the same K channels. We assume an interferencelimited system where each SU experiences interference from any other SUs transmitting on the same channel, i.e., intercell and intracell interferences. The system model is depicted in Figure 1. The PUs’ transmission also contribute to the total interference experienced by the SUs. Let us denote the power matrix by P, where the component p_{m,k}≥0 represents the power allocated to SU m on channel k. The received SINR at the nth receiver from the mth SU transmitter on the kth channel, denoted by Γ_{m,k}, can be defined as
Figure 1. System model: cellbased uplink and adhoc underlay cognitive radio network.N BS/SU receivers, M SU transmitters, L PU pairs, and K channels.
where is the channel power from the ith transmitter SU to the jth receiver on the kth channel, n_{m} denotes the attributed receiver n of the mth SU such that n_{m}∈{1,…,N}. For the adhoc scenario each transmitter m is associated to its predefined receiver n_{m}. For the CB scenario each SU transmitter m selects the best^{a} BS n_{m}. The term denotes the constant noise variance (N_{0}) plus the aggregate interference generated by the primary transmitters at the n_{m}th receiver on the kth channel. It is reasonable to assume that the primary aggregate interference at a secondary receiver (i.e., ) is known if it can distinguish between a secondary and primary signal, e.g., using different pilots. Thus, integrating over the power spectrum densities (PSD) of the PUs’ signals, the total interference from the primary system can be evaluated at each secondary receiver. The sum term represents the aggregate interference generated at the mth user’s receiver on channel k created by all other SUs, i.e., from intercell as well as intracell. Therefore, defines the total interference experienced by user m communication on channel k at its receiver, n_{m}.
We now define the main assumptions used in this work. The receiver n can estimate the instantaneous channel from, its respective (in adhoc) or each (in CB), transmitter m, on each channel k. However, the exact instantaneous interference created by the secondary transmitters to the primary receivers cannot be known, in particular if the primary system does not collaborate. Instead, based on the information given by a deployed wireless sensor network (WSN) (as advocated by, e.g., the SENDORA project [23]), the average interference channel from the mth SU to the lth PU can be assumed known (e.g., based on the approximative location of the receiver, etc.). The maximum aggregate interference power threshold at the PUs, , should be adopted to the known sensitivity of the primary system (e.g., linked to the outage probability of the PUs). As mentioned earlier, the major drawback, in practice, of this centralized configuration is the control overhead between the FC and the SUs.
We now formulate the sumrate problem for the fully synchronized CR system. Assuming that the noise and the interference have Gaussian characteristics, the network utility maximization problem is given as follows:
where the received SINR Γ_{m,k}is given in (1). The objective (2) is to allocate the resource (i.e., power and channels) such that the sumrate capacity is maximized. Constraint (3) defines the aggregate average interference power constraint ( assumed identical for all PUs for the sake of notation simplicity) for each subchannel k at each PU receiver l using that channel and denoted by . Constraint (4) defines the total transmit power per SU over all channels. The optimization problem (2) is promptly applicable for the adhoc system. Whereas, for the intracell CB uplink case, we need to assume that a base station is capable of receiving simultaneously the signals from its associated transmitters interfering each other on noncontiguous channels. Note that the selection of the channels (i.e., spectrum allocation) is directly related to the power levels, i.e., p_{m,k}=0 implies that user m cannot use the kth channel. It is wellknown that the sumrate capacity is a theoretical metric not often used in real networks. However, it provides a useful upperbound to compare metrics which account for different realistic constraints such as fairness issues (e.g., see [24] which considers the maxmin capacity problem for multihop CR network with interference constraint).
This problem is known to be NPcomplete [25], even with one channel and without considering the CR constraint in Equation (3). The main problem is the interference among users. As shown in [26], if the crosstalk interference is larger than some value (see [26]), the optimal RRA is an FDMA type allocation. In fact, if the crosstalk exists but is very small (e.g., imagine very far apart set of transceivers), then the optimal solution could even be obtained using distributed approach (e.g., iterative waterfilling) to converge to a unique Nash equilibrium (NE). If the crosstalk is not negligible, multiple NE points can exist, which can be far from the social optimum.
Adapting SCVX for largescale problem, LSSCVX
In this section, we first briefly derive the convex GP form of our initial problem given by (24) to fit the successive convexification approach as in [11]. We show the exponential increase in monomial summations compared to the simplified highSINR assumption case [6][5] and one frequency band. To overcome this problem, without affecting the convergence property, we combine the approach of [11] with another convexification approach described in [27].
We start by deriving the transformation of (2)–(4) into a formulation following the standard GP form. Like linear programming (LP) or quadratic programming (QP), GP is a type of standard optimization problem [10]. The authors in [11] provide a good understanding about variations in RRA problems, their relation to GP, and possible approximations. In [27], different methods are presented to include fairness constraints. In the literature, GP deals with two types of functions: monomial and posynomial^{b}. In the standard GP problem the objective function and the inequality constraints are posynomial, and the equality constraints are monomial. In the initial optimization problem (2)–(4), the inequality constraints (3) and (4) are already in the right form. However, the initial objective function (2) requires some modifications. Maximizing (2) is equivalent to minimize the following [11]
which is not in a posynomial form due to the denominator. Directly solving this nonlinear, nonconvex problem, and not matching any standard form, is thus difficult. Instead, [11] proposes an approach by successively (iteratively) solving a convex approximation problem obtained using the socalled condensation approximation method for the denominator in (5). Let us define , where each corresponds to one element in the summation (i.e., and ). The condensation approximation is then applied as follows ([11], Eq. 11):
where , and . The power matrix is the solution from the previous step subproblem (5) in the successive approach. The function which is monomial represents the best local monomial approximation to near in the sense of a first order Taylor approximation [11]. The multiplicative term can be then written in a monomial form (i.e., ). Now, writing out the MK different multiplications of (M−1) + 1summations of ψ(P) in (5) leads to a posynomial function composed of M^{MK}monomials (i.e., , ). The minimization (5) can be finally approximated at every successive step to the minimization of the following posynomial function
The successive convex approximation simply repeats the GP formulation (7) and solves it using the constraints (3), (4). Let a^{(i)}=a_{i1},…,a_{iMK}^{T}, , and . All elements of A and b remain unchanged at each iteration, except the coefficient a^{(0)}and b^{(0)}, updated using the Condensation method. Although the standard GP form (7) can be solved, it is not a convex optimization problem. However, any problem in GP standard form can be further transformed into a convex problem using logsumexp transformation [10], ([11], Eq. 2). Finally, the convex problem can be, in general, efficiently solved using IPM^{c} with at most polynomial complexity [10].
Although the optimization variable vector in (7) has only MK elements (i.e., P), the posynomial function contains M^{MK} monomials. All the power exponents (e.g., ) need to be updated at each iteration which correspond to {M^{MK}MK}elements. The size expansion obviously creates a bottleneck. Taking for example the CB scenario where {NMK} equal to {2,4,2} respectively, requires some matrices with length M^{MK}=65536. Using simply one additional SU per cell (i.e., M=6) would require matrices of length 6^{12}. This is obviously not easy to handle for larger system sizes as used in our numerical experiments (i.e., {M=32,K=128}). In order to tackle the exponential increase in monomial summations we next use the convexification approach similar to the one used in [27].
Instead of applying the logsumexp on the GP expression (7) with the extremely large monomials summation in the numerator, we apply it on (7) but using for the numerator the multiplicative form of ψ(P) in (5), instead of the M^{MK}summations form. Taking X as the new optimization variable matrix such that , we get the following convex problem
The convexity of the objective function in terms of X is due to the fact that the first element follows the logsumexp type expression which is convex ([10], p. 72), and the remaining part is linear. Note that in (8), the summations remain over MK elements. Finally, the exact same successive approach with updated condensation approximation is used as previously presented, but the more practical convex problem (8) is solved instead of (7)–(3), (4). Since the same condensation method is used, minimization in (8) is exactly equivalent to the minimization problem of the convex form of (7) with constraints (3), (4). Hence, the convergence property does not change, since each subproblem obtained from the condensation approach, being the GP convex formulation based on (7) or our proposed convex formulation (8), are to be solved optimally. The optimization problem (8) is solved using IPM, for which the gradient and Hessian derivations of the Lagrangian are relegated in the appendix. It is now possible to solve for (2)–(4) using (8) in the case of large problem, which is obviously intractable with (7). We call this approach the LSSCVX algorithm.
Enhanced lowcomplexity iterative approach, ELCI
Further motivated to obtain even lower complexity algorithms, while providing good suboptimal solutions, we present hereafter a novel heuristic algorithm, called, ELCI. ELCI is based on a similar iterative approach proposed in [28], where the authors deal with the same problem defined in (2)–(4) but without the interference constraint (3). The ELCI algorithm is designed to cope with the additional interference constraint, and also provides a fast and efficient method for solving for the required Lagrangian multipliers.
Mathematical bases
We begin by applying the KKT conditions as defined in, e.g., ([10], Section 5.5.3). However, we do not apply it to the complete set of problem given by (2)–(4). Instead, we apply it to three different problems derived from the initial problem: first, assume that there are no constraints (i.e., without both (3) and (4) constraints); second, assume in addition to the objective function the interference constraint (3) is active for a certain set of k channels and some ls of the corresponding set of PUs (to be defined by the algorithm); third, assume in addition to the objective function the sumpower constraint (4) is active for a certain set of m users (to be defined by the algorithm). The reason of this heuristic approach, is to use the important feature of the optimal solution, i.e., it (or they) lies on the boundary of the feasible region [2] (i.e., at least one active constraint). Note that a constraint is said to become an active constraint when the power distribution is such that the inequality (e.g., (3) or (4)) becomes exactly equal. Therefore, the three settings yield the three following problems to be solved:
In (9) none of the constraints are taken into account; in (10) some of the interference constraints of (3) are considered; and in (11) some of the power constraints of (4) are considered. Let us define P^{(I)∗}P^{(II)∗}P^{(III)∗}, the optimal solutions of (9), (10), and (11), respectively, and μ_{k,l}and λ_{m} are the positive LGM. The LGMs are solved in (10) and (11), such that the respective constraints (3) and (4) become active (e.g., ). Expanding (9) yields
which can be further written as
where Γ_{m,k} and I_{i,k} are defined in (1). It is easy to see that solving for P^{(I)∗}in (12) is hard since the power matrix is included in all the SINR functions, Γ. To circumvent this problem, the authors in [28] propose to use an iterative algorithm such that the power update at the next state is given by
where the relation with (12) is easy to see. Following the same approach, the power updates for the two other cases (10) and (11) are given respectively by:
The three power update expressions (13–15) form the mathematical basis of ELCI.
Solving the Lagrangian multipliers
In order to compute (14) and (15), it is first required to evaluate μ_{k,l} and λ_{m}, respectively. We present here a simple and efficient method, optimized for the particular need of ELCI. The solutions are obtained substituting (14) and (15) into (3) and (4) respectively, with equality instead of inequality constraint (i.e., becomes an active constraint).
Let us for example investigate the resolution of μ_{k,l}. For a violated PU l on channel k, μ_{k,l}is solved using (14) in (3) as follows:
where , , and . Let us define the function . We need to solve μ_{k,l}such that , i.e., a nonlinear equation with a unique unknown. It is easy to note from (16) that a_{m}b_{m}c_{m},∀m∈[1,…,M are all nonnegatives. Moreover, c_{m},∀m∈[1,…,M are also nonzero. Thus, the function ζ(μ_{k,l}) is strictly decreasing and positive for μ_{k,l}positive. If , the Equation (16) has no positive solution. In fact, this case means that PU l on channel k is not violated (i.e., ). Thus, this cannot happen since in the ELCI algorithm (to be described shortly) the LGMs computations are only required when the respective constraint is violated (i.e., above the constraint). In the other case, if , a solution exists and can be obtained using for example the simple and fast bisection or golden interval methods [29]. The search is stopped when (with, e.g., ε_{1}=10^{−20}). Note that the number of iterations for the bisection search increases as the slope of in terms of μ_{k,l} tends to 0 (e.g., for very large M or K). Yet, in practice, the bisection or golden methods are very simple and extremely fast, as later confirmed through largescale experiments. The same approach applies for solving λ_{m}.
Algorithm description
The main iterative loop of the algorithm contains three blocks A, B, and C related to the updates (13), (14), and (15), respectively. Block A updates the power without considering any of the constraints, i.e., (3) and (4). Block B updates the power, while only guaranteeing that the interference constraint (3) is satisfied for all PUs on all channels. Block C updates the power, while only guaranteeing that the transmit power constraint (4) is satisfied for all SUs.
Algorithm 1 ELCI Algorithm
Initialize: t=0, ∀(m,k) [INIT]
repeat
t=t + 1
Update ∀(m,k): [Block A]
[Block B]
fork=1to Kdo
Set B_{duplicate}=OFF; Empty set (i.e., setwhich will contain violated PUs)
repeat
ifthenB_{duplicate}=ON elseend if
Compute (∀m): tmp_{m}=(14) with {need to compute}
end if
until interference constraint (3)satisfied
end for
[Block C]
Compute (∀k)tmp_{k}=(15){need to computeλ_{m}}
end for
untilf(P(t))−f(P(t−1))≤ε_{0}, ε_{0}>0, (then apply an additional iteration with Finaliteration mode)
Further details about the algorithm are given as follows:
Block A: In the special case defined by the if statement, using (13) would lead to p_{m,k}(t)=∞. This stems from the fact that there is no one competing with user m on that channel k and none of the constraints (i.e., (3), (4)) are handled in (13). Thus, we constrain to .
Block B: For a given channel k, the repeat loop handles sequentially and independently the interference at the current worst interfered PU, . The independent handling of the PUs means that the update to satisfy the current worst PU could cancel the previously handled worst PU’s interference constraint. within the repeat loop. Thus, if any given PU reappears a second time (i.e., already ), all the remaining updates in the current repeat loop cannot increase the power (i.e., B_{duplicate}=ON).
Block C: The power update in Block C satisfying the power constraint (4) is handled independently from the power update in Block B satisfying the interference constraint (3). As such, power updates from Block C can violate the interference constraint (3). To make the final solution always feasible, after ELCI’s convergence criteria^{d} is satisfied, i.e., f(P(t))−f(P(t−1))≤ε_{0}, the algorithm performs an additional Finaliteration. The Finaliteration assures that all the constraints (i.e., (3) and (4)) are satisfied when terminating the ELCI algorithm thanks to Block C (i.e., through min(tmp_{k},p_{m,k}(t))).
It is interesting to note that the power updates in Blocks B and C, generally, contract the powers to fulfill the different constraints, whereas Block A expand them. Although ELCI separates the interferencelimited update (i.e., (14)) and the sumpowerlimited update (i.e., (15)) cases, the iterative method presented in Algorithm 1 basically aims to recombine (yet nonoptimal) the two independent updates. Thus, ELCI does not only aim one of the two system cases, as opposed to, e.g., [8].
Performance and complexity
MARL
Although the problem in (2)–(4) is nonconvex, three important features enable MARL to optimally solve it, assuming infinite time [2]. One of those important features is the monotonically increasing objective function in terms of SINR. The MARL algorithm constructs a sequence of polyblocks to approximate the SINR region boundary with an increasing level of accuracy. By tuning an error tolerance parameter, a tradeoff between performance and convergence time can also be achieved. However, as explained in [12] the polyblock vertices projection approach does not exploit the shape of the feasible region, but shrink from every side in the continuous domain. The number of iterations and vertices vary with the problem dimension and the shape of the feasible region. Consider for example a CB network, where NMKall equal 2 (see configuration details in Section 6.). Figure 2 compares the three algorithms for 100 random realizations of the channel gains. The three algorithms exhibit very similar performances (i.e., sumrate), but one can note that at samples 25 and 63, MARL slightly outperforms both LSSCVX and ELCI. In Figure 3, we increase M and N to 4 investigate the performance of MARL for one random realization. We obtain the convergence with MARL near 6×10^{4}iterations (whereas 15 and 9 iterations for LSSCVX and ELCI, respectively). With a problem of dimension 8 (i.e., MK), the number of iterations and vertices is already large. With larger dimensions, the number of vertices to accurately define the feasible region can be quite enormous. Thus, unable to perform MARL for the largescale settings, we only confront ELCI with LSSCVX for the remaining large system simulations. Yet, if the objective is to be able to approach arbitrarily close to the optimal (at the expense of an infinite time), the MARL algorithm can fulfill it as opposed to LSSCVX and ELCI.
Figure 2. Close sumrate performance illustration between MARL, LSSCVX and ELCI, for a small CB system. Two adjacent cells of 100 m radius with one SU each (i.e., M=N=2), two channels (i.e., K=2), and one PU pair (i.e., L=1). Cellbased simulation using 100 random channel gain realizations.
Figure 3. Illustration of MARL’s slow convergence for one random small scenario realization. Four adjacent cells of 100 m radius with one SU each (i.e., M=N=4), two channels (i.e., K=2), and one PU (i.e., L=1).
SCVX/LSSCVX
Although the convexification approach in [11] has been generally considered to be quite efficient, it does not necessarily converge to the globally optimal solution(s) due to the condensation approximations. An improper initialization may also impact its optimality performance [2]. Although not addressed in this current article, [30] provides some efficient methods for guessing good initial points. The barrier method (classical IPM), used in this article to solve the convex optimization (8), has the nice property that the number of Newton steps grows very slowly with the problem dimension [10]. However, the computational effort to carry out one Newton step also grows with the dimension. As explained in [31], in general, when exact second derivatives can be computed with reasonable computational effort, it is usually a good idea to use them, since the IPM normally converges in fewer iterations and is more robust. When the problem has a dense Hessian or nonsparse Hessian, using the quasiNewton approximation might be better, even if the number of iterations increases, since the computation time per iteration for the search direction using the exact derivative might be significantly higher. However, since we noticed some losses with the quasiNewton (BFGS) compared to the IPM, we use the latter approach in our simulations where the Hessian for the Lagrangian of (8) is provided as appendix.
ELCI
The suboptimality of ELCI is mainly due to the fact that the constraints (3) and (4) are taken into account in alternation instead of simultaneously. In order to circumvent possible local optima, most of the heuristics algorithms proposed in the literature can repeat the locallyoptimal algorithm with different random initial values. However, like MARL, we always initialize . We now characterize the complexity of ELCI for the worst case behavior. In particular, we focus on the notable total number of LGM computations denoted by N_{L} and the total number of updates (13), (14), and (15) denoted by N_{U}. It is easy to see that only the LGM computations has nonnegligible complexity and vary with the problem size. We define I as the total number of iterations, where one iteration represents the loop composed of Blocks A, B, and C. The size of I is influenced by the number of SUs and channels, as well as the level of interference interaction in the system. In our various simulations I is relatively small (i.e., average range [10–20]). In the worst case, in Block B, all PUs can be violated and processed twice (i.e., using B_{duplicate} in Block B). Thus, Block B needs at the most K2L LGM computations per iteration. It easy to see that Block C needs at the most M LGM computations. Therefore, the ELCI algorithm yields at worst N_{L}=I×(K2L + M) and N_{U}=I×(MK + K2LM + MK).
Although ELCI is not proved to necessarily converge, extensive simulations (i.e., some presented in Section 6.) indicate that the algorithm, always converges, or approximately converges with continuous slight oscillation^{d}. As later shown, comparing ELCI to LSSCVX algorithm no divergence of the former algorithm has been observed.
Numerical experiments
This section compares through various numerical experiments the performance of ELCI against LSSCVX.
We define the channel gain such that , where is the distance from the mth SU and the n_{m}th receiver, α is the path loss exponent, and β_{m,k} is a random variable with Gaussian distribution . The same approach applies for the interference channel characterization. For simplicity we fix L=12, where each randomly located PU node simultaneously transmits (at 10 dBm) and receives, on 2 random channels out of K. The remaining parameters are set such that: α=2, σ=7 dB, dBm, dBm, and N_{0}=−70 dBm. The simulations we provide are for both CB and adhoc networks, separately. The purpose of this separation is to independently analyze the adhoc environment which exhibits more complicated interference couplings compared to a CB network. For the CB case, we set N=4 adjacent cells, with equal number of randomly placed SUs (i.e., M/N) within a cell radius equal to 150 m each. For the adhoc case, SUs are randomly placed within a 500 m^{2} square area, with 10 and 50 m minimum and maximum distance respectively for the SUs pair. These small areas are purposely chosen to create enough complex interference coupling between different links, while the large variance of β_{m,k} implies that channel gains can highly fluctuate among different channels of a given user. Thus, a given user, e.g., the closest to the BS, will not be necessarily allocated all the channels.
In Figures 4 and 5 we set M=20and K=25and provide the PDF (probability density function) of their performance ratio (i.e., ). Each PDF is based on 500 random simulations. For additional comparison we also simulate the performance of the cellbased network for the nonvarying channels case (i.e., the channel gain for a given link does not vary with k). In Figure 4, we compare ELCI against LSSCVX where the later is performed using a random initial point, once. In order to overcome, to some extent, the possible suboptimality of LSSCVX (inherent to SCVX), we compare in Figure 5 ELCI with the LSSCVX’s best performance out of 20 simulations with random different initial values. In both Figures 4 and 5, LSSCVX generally performs better than ELCI, in particular when compared with 20 initial values in Figure 5. Yet, it is also clear that ELCI’s performance is very close to LSSCVX (i.e., the worst ratio of only 0.94), and sometimes better. It is also interesting to note that for the nonvarying channel case, ELCI performs very well. This stems from the fact that the channel distributions and interferences are less random and complex. Figure 6 provides the PDF for the ELCI number of iterations for both the CB and adhoc scenarios. Since more point to point communications can exist in the adhoc system, compared to the CB system with only N BSs, the former scenario yields a higher number of iterations. Yet, in general the number of iterations are rather small, around 10, for the setting at hand, i.e., M=20 and K=25.
Figure 4. PDF of the sumrate ratio between ELCI and LSSCVX’s first trial, for averagescale scenarios. Three settings with M=20and K=25: 1) cellbased (N=4), 2) adhoc (N=M), and 3) cellbased with nonvarying (referred as n. v.) channels (i.e., same channel gain over all K channels for a given link is enforced). Each PDF is based on 500 random realizations.
Figure 7 illustrates the average sumrate performance of ELCI and LSSCVX for various largescale settings. The corresponding time consumption is provided in Figure 8. Each point has been averaged over 50 realizations. While the performance of ELCI in Figure 7 is equal or very close to LSSCVX (i.e., in fact in the loglog scale plot of Figure 7, the difference is almost not visible), the much lower complexity of ELCI is clear from Figure 8. Again, due to more complicated coupling among different links for the adhoc system as K becomes very large ELCI has more loss of performance compared to the CB case, but again still minor.
Figure 7. Close sumrate performance illustration between LSSCVX and ELCI for various largescale settings, in both CB and adhoc networks. Each point is averaged over 50 random realizations.
Conclusion
The problem of interferencelimited sumrate capacity in wireless network has been one of the most widely investigated problem, with and without cognitive radio constraint. Yet, only very recently centralized algorithms like MARL have been proposed yielding the optimal solution. However, in practical numerical experiments MARL cannot cope with large problems. Motivated by this issue, we propose two alternatives. First, we propose a clear mathematical adaptation LSSCVX of the wellknown stateoftheart suboptimal algorithm, SCVX, to cope with large problems, while keeping the initial convergence proof unchanged. Second, as a further alternative, we propose a new lowcomplexity heuristic algorithm, ELCI, based on the fact that the optimal solution lies on the boundary of the feasible region. The key idea of ELCI is to handle the different constraints separately, and further use a specific formulation for the iterative power updates based on the KKT conditions of the problem. Compared to LSSCVX, ELCI was shown to provide an excellent tradeoff for very largescale system applications where both good performance and low complexity is required.
Appendix 1
The Lagrangian function for the optimization problem (8) can be written as
where Φ(X) is the objective function (8), and μ_{k,l},λ_{m}≥0are the Lagrange multipliers related to the constraints (3) and (4), respectively. The gradient and Hessian of the Lagrangian function are given as follows:
Endnotes
^{a} Simple attribution in terms of the highest channel power. In case each subchannel have different gains, a SU selects the BS with the best channel averaged over all subchannels.
^{b} is a posynomial composed of N monomials; p is the optimization variable, where the initial matrix optimization variable P of size {M,K} is simply represented into a vector format p of size {MK,1}; b^{(i)}>0 and .
^{c} IPM is one of the most popular generic approach for solving any convex problems, but one can also use other generic methods, e.g., cuttingplane method.
^{d} When ε_{0}is too small, a continuous small oscillation may appear, and the convergence criteria (i.e., f(P(t))−f(P(t−1))≤ε_{0}) cannot be satisfied. In such a case it suffices to terminate the algorithm and apply the Finaliteration.
Competing interests
The authors declare that they have no competing interests.
References

PC Weeraddana, M Codreanu, M Latvaaho, A Ephremides, Weighted sumrate maximization for a set of interfering links via branch and bound. IEEE Trans. Signal Process 59(8), 3977–3996 (2011)

LP Qian, Y Jun, Monotonic optimization for nonconcave power control in multiuser multicarrier network systems. in Proc, ed. by . IEEE INFOCOM (Rio de Janeiro, Brazil, 2009)

K Eriksson, S Shi, N Vucic, M Schubert, EG Larsson, Globally optimal resource allocation for achieving maximum weighted sum rate. in Proc, ed. by . IEEE GLOBECOM (Fl, Miami, USA, 2010)

CW Tan, S Friedland, SH Low, Spectrum management in multiuser cognitive wireless networks: optimality and algorithm. IEEE J. Sel. Areas Commun 29(2), 421–430 (2011)

Y Xing, CN Mathur, MA Haleem, R Chandramouli, KP Subbalakshmi, Dynamic spectrum access with QoS and interference temperature constraints. IEEE Trans. Mob. Comput 6(4), 423–433 (2007)

Q Jin, D Yuan, Z Guan, Distributed geometricprogrammingbased power control in cellular cognitive radio networks. in Proc, ed. by . IEEE VTC (Barcelona, Spain, 2009)

E Hossain, D Niyato, Z Han, Dynamic Spectrum Access and Management in Cognitive Radio Networks (Cambridge University Press, Cambridge, 2009)

MG Khoshkholgh, K Navaie, H Yanikomeroglu, Impact of the secondary service transmit power constraint on the achievable capacity of spectrum sharing in Rayleigh fading environment. IEEE Commun. Lett 12(12), 856–867 (2008)

L Zhang, Y Xin, YC Liang, HV Poor, Cognitive multiple access channels: optimal power allocation for weighted sum rate maximization. IEEE Trans. Commun 57(9), 2754–2762 (2009)

S Boyd, L Vandenberghe, Convex Optimization (Cambridge University Press, Cambridge, 2004)

M Chiang, C Tan, D Palomar, D O’Neill, D Julian, Power control by geometric programming. IEEE Trans. Wirel. Commun 6(7), 2640–2651 (2007)

LP Qian, YJ Zhang, J Huang, MAPEL: achieving global optimality for a nonconvex wireless power control problem. IEEE Trans. Wirel. Commun 8(3), 1553–1563 (2009)

DI Kim, LB Le, E Hossain, Joint rate power allocation for cognitive radios in dynamic spectrum access environment. IEEE Trans. Wireless Commun 7(12), 5517–5527 (2008)

A Attar, O Holland, M Nakhai, A Aghvami, Interferencelimited resource allocation for cognitive radio in orthogonal frequencydivision multiplexing networks. IET Commun 2(6), 806–814 (2008). Publisher Full Text

Y Ma, D Kim, A Leith, Weighted sum rate optimization of multicell cognitive radio networks. in Proc, ed. by . IEEE GLOBECOM (NewOrleans, USA, 2008)

D Yu, JM Cioffi, Iterative waterfilling for optimal resource allocation in OFDM multipleaccess and broadcast channels. in Proc, ed. by . IEEE GLOBECOM (San Francisco, 2006)

W Yu, G Ginis, JM Cioffi, Distributed multiuser power control for digital subscriber lines. IEEE J. Sel. Top. Signal Process 20(5), 1105–1115 (2002)

W Yu, R Lui, Dual methods for nonconvex spectrum optimization of multicarrier systems. IEEE Trans. Commun 54(7), 1310–1322 (2006)

J Papandriopoulos, J Evans, Lowcomplexity distributed algorithms for spectrum balancing in multiuser DSL networks. in Proc, ed. by . IEEE ICC (Istanbul, Turkey, 2006)

LP Qian, YJ Zhang, M Chiang, Globally optimal distributed power control for nonconcave utility maximization. in Proc, ed. by . IEEE GLOBECOM (Miami, Florida, USA, 2010)

P Hande, S Rangan, M Chiang, X Wu, Distributed uplink power control for optimal SIR assignment in cellular data networks. IEEE/ACM Trans. Network 16(6), 1430–1443 (2008)

L Vijayandran, SS Byun, GE Øien, T Ekman, Increasing sum rate in multiband cognitive radio networks by centralized power allocation schemes. in Proc, ed. by . IEEE PIMRC (Tokyo, Japan, 2009)

SENDORA project EU, FP7 (available at: http://www), . sendora.eu/ webcite

M Girnyk, M Xiao, L Rasmussen, Optimal power allocation in multihop cognitive radio networks. in Proc, ed. by . IEEE PIMRC (Toronto, Canada, 2011)

ZQ Luo, S Zhang, Dynamic spectrum management: complexity and duality. IEEE J. Sel. Top. Signal Process 2, 57–73 (2008)

S Hayashi, ZQ Luo, Spectrum management for interferencelimited multiuser communication systems. IEEE Trans. Inf. Theory 55(3), 1153–1175 (2009)

L Le, E Hossain, Resource allocation for spectrum underlay in cognitive radio networks. IEEE Trans. Wirel. Commun 7(12), 5306–5315 (2008)

C Yih, E Geranotis, Centralized power allocation algorithms for OFDM cellular networks. in Proc, ed. by . IEEE MILCOM (Boston, USA, 2003)

J Nocedal, S Wight, Numerical Optimization (Springer, Berlin, 2006)

J Chinneck, Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods (Springer, Berlin, 2007)

A Wachter, LT Biegler, On the implementation of a primaldual interior point filter line search algorithm for largescale nonlinear programming. Math. Programm 106(1), 25–57 (2006). Publisher Full Text