SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

Open Access Highly Accessed Research

Increasing sum-rate in large-scale cognitive radio networks by centralized power and spectrum allocation

Luxmiram Vijayandran1*, Sang-Seon Byun2, Geir E Øien1 and Torbjörn Ekman1

Author Affiliations

1 Department of Electronics and Telecommunications, Norwegian University of Science and Technology, Trondheim, Norway

2 Shool of Information and Communications, Gwangju Institute of Science and Technology, Gwangju, South Korea

For all author emails, please log on.

EURASIP Journal on Wireless Communications and Networking 2012, 2012:362  doi:10.1186/1687-1499-2012-362


The electronic version of this article is the complete one and can be found online at: http://jwcn.eurasipjournals.com/content/2012/1/362


Received:16 March 2012
Accepted:16 November 2012
Published:11 December 2012

© 2012 Vijayandran et al.; licensee Springer.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

We revisit the widely investigated problem of maximizing the centralized sum-rate capacity in a cognitive radio network. We consider an interference-limited multi-user multi-channel environment, with a transmit sum-power constraint over all channels as well as an aggregate average interference constraint towards multiple primary users. Until very recently only sub-optimal algorithms were proposed due to the inherent non-convexity of the problem. Yet, the problem at hand has been neglected in the large-scale 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 well-known 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 low-complexity 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 state-of-the-art algorithms, SCVX, and the recently proposed global optimum approach, MARL. The salient highlight of ELCI is the relatively fast and very good sub-optimal performance in large-scale CR systems.

Introduction

The throughput maximization in multi-user interference-limited wireless networks has been a long standing major problem, since it is typically non-convex due to complicated interference coupling among different links. In particular, we consider a cognitive radio (CR) system composed of secondary users (SUs) and multi-channel. We aim to maximize the sum-rate 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 [2-4]. In particular Qian et al. proposed one of the very first centralized algorithm MARL in [2]. Before MARL a significant number of sub-optimal 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 signal-to-interference-noise-ratio (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 power-limited or primary interference-limited system). In [9], the multiple access channel approach using successive interference cancelation yields an interference-free formulation, thus the problem becomes convex. In particular, convex problem formulations are highly desired since the global optimum can be obtained using well-developed technics, e.g., the interior-point 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 low-SINR 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 power-limited or primary interference-limited state (i.e., in a mix state). In contrast, other works, e.g., [2,11-15] 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 state-of-the-art centralized algorithms. The algorithm (referred here as SCVX) is based on a successive convexification of the problem using the so-called condensation approximation. While, all the aforementioned algorithms are only sub-optimal, the centralized optimal algorithm [2] Monotonic optimization-bAsed 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 large-scale 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 well-know good sub-optimal SCVX algorithm exhibits non-negligible 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 sub-optimal 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 large-scale settings, called LS-SCVX, 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 Low-Complexity 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 LS-SCVX can be obtained with ELCI but with much lower complexity.

It is well-known 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 sum-rate case. We believe that ELCI as well as the enhanced LS-SCVX can provide in practice good approximate benchmarks in the case of large-scale problems as advocated by distributed algorithms. Note that although stated as an optimal distributed algorithm, the one proposed in [21] do not cope with multi-channel and sum-power constraint over all bands. Similarly, in addition to the fact that the interference constraint is not considered in [20], the adaptation for multi-channel and sum-power constraint is not so straightforward, in particular for large-scale systems (i.e., see ([20], Eq. 13) for the multi-level integral required in the denominator).

We recently proposed an algorithm in [22] to cope with the sum-rate problem. The current article builds on those results while improving the followings; First, the new algorithm has been improved for the case of multi-band varying channels. Second, a low-complexity 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 LS-SCVX, 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 LS-SCVX 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: Bold-face lower-case letters refer to vectors (x); bold-face capital letters refer to matrices (X); single variables are referred to by simple lower-case letters (x); xm,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 (<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M1">View MathML</a>).

System model

Consider a CR network composed of a set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M2">View MathML</a> of secondary transmitters and a set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M3">View MathML</a> of receivers. For the point-to-point ad-hoc network each transmitter communicates with its respective receiver, i.e., M=N. In a cell-based (CB) uplink scenario (i.e., infrastructure-based), several transmitters send data to the associated CR base station (BS), i.e., NM. The information transmission is assumed over K parallel channels with equivalent bandwidth but possibly experiencing different gains. Let <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M4">View MathML</a> denote the channel index set. Inherent to any CR systems, there is a set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M5">View MathML</a> of primary transceiver pairs, using the same K channels. We assume an interference-limited system where each SU experiences interference from any other SUs transmitting on the same channel, i.e., inter-cell and intra-cell 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 pm,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

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M6">View MathML</a>

(1)

thumbnailFigure 1. System model: cell-based uplink and ad-hoc underlay cognitive radio network.N BS/SU receivers, M SU transmitters, L PU pairs, and K channels.

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M7">View MathML</a> is the channel power from the ith transmitter SU to the jth receiver on the kth channel, nm denotes the attributed receiver n of the mth SU such that nm∈{1,…,N}. For the ad-hoc scenario each transmitter m is associated to its predefined receiver nm. For the CB scenario each SU transmitter m selects the besta BS nm. The term <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M8">View MathML</a> denotes the constant noise variance (N0) plus the aggregate interference generated by the primary transmitters at the nmth receiver on the kth channel. It is reasonable to assume that the primary aggregate interference at a secondary receiver (i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M9">View MathML</a>) 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M10">View MathML</a> represents the aggregate interference generated at the mth user’s receiver on channel k created by all other SUs, i.e., from inter-cell as well as intra-cell. Therefore, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M11">View MathML</a> defines the total interference experienced by user m communication on channel k at its receiver, nm.

We now define the main assumptions used in this work. The receiver n can estimate the instantaneous channel <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M12">View MathML</a> from, its respective (in ad-hoc) 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M13">View MathML</a> 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, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M14">View MathML</a>, 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 sum-rate 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:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M15">View MathML</a>

(2)

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M16">View MathML</a>

(3)

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M17">View MathML</a>

(4)

where the received SINR Γm,kis given in (1). The objective (2) is to allocate the resource (i.e., power and channels) such that the sum-rate capacity is maximized. Constraint (3) defines the aggregate average interference power constraint (<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M18">View MathML</a> assumed identical for all PUs for the sake of notation simplicity) for each sub-channel k at each PU receiver l using that channel and denoted by <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M19">View MathML</a>. Constraint (4) defines the total transmit power per SU over all channels. The optimization problem (2) is promptly applicable for the ad-hoc system. Whereas, for the intra-cell 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 non-contiguous channels. Note that the selection of the channels (i.e., spectrum allocation) is directly related to the power levels, i.e., pm,k=0 implies that user m cannot use the kth channel. It is well-known that the sum-rate capacity is a theoretical metric not often used in real networks. However, it provides a useful upper-bound to compare metrics which account for different realistic constraints such as fairness issues (e.g., see [24] which considers the max-min capacity problem for multi-hop CR network with interference constraint).

This problem is known to be NP-complete [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 large-scale problem, LS-SCVX

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 high-SINR 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 posynomialb. 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]

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M20">View MathML</a>

(5)

which is not in a posynomial form due to the denominator. Directly solving this non-linear, non-convex 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 so-called condensation approximation method for the denominator in (5). Let us define <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M21">View MathML</a>, where each <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M22">View MathML</a> corresponds to one element in the summation <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M23">View MathML</a> (i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M24">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M25">View MathML</a>). The condensation approximation is then applied as follows ([11], Eq. 11):

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M26">View MathML</a>

(6)

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M27">View MathML</a>, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M28">View MathML</a>. The power matrix <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M29">View MathML</a> is the solution from the previous step sub-problem (5) in the successive approach. The function <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M30">View MathML</a> which is monomial represents the best local monomial approximation to <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M31">View MathML</a> near <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M32">View MathML</a> in the sense of a first order Taylor approximation [11]. The multiplicative term <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M33">View MathML</a> can be then written in a monomial form (i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M34">View MathML</a>). Now, writing out the MK different multiplications of (M−1) + 1summations of ψ(P) in (5) leads to a posynomial function composed of MMKmonomials (i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M35">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M36">View MathML</a>). The minimization (5) can be finally approximated at every successive step to the minimization of the following posynomial function

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M37">View MathML</a>

(7)

The successive convex approximation simply repeats the GP formulation (7) and solves it using the constraints (3), (4). Let a(i)=ai1,…,aiMKT, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M38','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M38">View MathML</a>, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M39">View MathML</a>. 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 log-sum-exp transformation [10], ([11], Eq. 2). Finally, the convex problem can be, in general, efficiently solved using IPMc with at most polynomial complexity [10].

Although the optimization variable vector in (7) has only MK elements (i.e., P), the posynomial function contains MMK monomials. All the power exponents (e.g., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M40">View MathML</a>) need to be updated at each iteration which correspond to {MMKMK}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 MMK=65536. Using simply one additional SU per cell (i.e., M=6) would require matrices of length 612. 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 log-sum-exp 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 MMKsummations form. Taking X as the new optimization variable matrix such that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M41">View MathML</a>, we get the following convex problem

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M42','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M42">View MathML</a>

(8)

The convexity of the objective function in terms of X is due to the fact that the first element follows the log-sum-exp 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 sub-problem 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 LS-SCVX algorithm.

Enhanced low-complexity iterative approach, ELCI

Further motivated to obtain even lower complexity algorithms, while providing good sub-optimal 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M43','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M43">View MathML</a> PUs (to be defined by the algorithm); third, assume in addition to the objective function the sum-power 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:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M44','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M44">View MathML</a>

(9)

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M45','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M45">View MathML</a>

(10)

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M46','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M46">View MathML</a>

(11)

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,land λ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., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M47','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M47">View MathML</a>). Expanding (9) yields

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M48','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M48">View MathML</a>

which can be further written as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M49','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M49">View MathML</a>

(12)

where Γm,k and Ii,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

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M50">View MathML</a>

(13)

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:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M51','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M51">View MathML</a>

(14)

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M52','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M52">View MathML</a>

(15)

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,lis solved using (14) in (3) as follows:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M53','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M53">View MathML</a>

(16)

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M54','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M54">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M55','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M55">View MathML</a>, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M56','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M56">View MathML</a>. Let us define the function <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M57','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M57">View MathML</a>. We need to solve μk,lsuch that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M58','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M58">View MathML</a>, i.e., a non-linear equation with a unique unknown. It is easy to note from (16) that ambmcm,∀m∈[1,…,M are all non-negatives. Moreover, cm,∀m∈[1,…,M are also non-zero. Thus, the function ζ(μk,l) is strictly decreasing and positive for μk,lpositive. If <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M59','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M59">View MathML</a>, the Equation (16) has no positive solution. In fact, this case means that PU l on channel k is not violated (i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M60','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M60">View MathML</a>). 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 onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M61','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M61">View MathML</a>, 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M62','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M62">View MathML</a> (with, e.g., ε1=10−20). Note that the number of iterations for the bisection search increases as the slope of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M63','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M63">View MathML</a> 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 large-scale 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, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M64','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M64">View MathML</a>∀(m,k) [INIT]

repeat

t=t + 1

Update ∀(m,k): [Block A]

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M65">View MathML</a>

[Block B]

fork=1to Kdo

Set Bduplicate=OFF; Empty set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M66','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M66">View MathML</a> (i.e., setwhich will contain violated PUs)

repeat

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M67">View MathML</a>

if (<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M68','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M68">View MathML</a>) then

if<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M69','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M69">View MathML</a>thenBduplicate=ON else<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M70','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M70">View MathML</a>end if

Compute (∀m): tmpm=(14) with <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M71','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M71">View MathML</a>{need to compute<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M72','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M72">View MathML</a>}

Update (∀m): pm,k(t)=<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M73','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M73">View MathML</a>

end if

until interference constraint (3)satisfied<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M74','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M74">View MathML</a>

end for

[Block C]

Find set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M75','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M75">View MathML</a>

for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M76">View MathML</a>do

Compute (∀k)tmpk=(15){need to computeλm}

Update(∀k): <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M77','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M77">View MathML</a>

end for

until|f(P(t))−f(P(t−1))|≤ε0, ε0>0, (then apply an additional iteration with Final-iteration 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 pm,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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M78','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M78">View MathML</a>.

Block B: For a given channel k, the repeat loop handles sequentially and independently the interference at the current worst interfered PU, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M79','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M79">View MathML</a>. 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M80">View MathML</a>), all the remaining updates in the current repeat loop cannot increase the power (i.e., Bduplicate=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 criteriad is satisfied, i.e., |f(P(t))−f(P(t−1))|≤ε0, the algorithm performs an additional Final-iteration. The Final-iteration 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(tmpk,pm,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 interference-limited update (i.e., (14)) and the sum-power-limited update (i.e., (15)) cases, the iterative method presented in Algorithm 1 basically aims to recombine (yet non-optimal) 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 non-convex, 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 trade-off 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M81','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M81">View MathML</a> 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., sum-rate), but one can note that at samples 25 and 63, MARL slightly outperforms both LS-SCVX 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×104iterations (whereas 15 and 9 iterations for LS-SCVX 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 large-scale settings, we only confront ELCI with LS-SCVX 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 LS-SCVX and ELCI.

thumbnailFigure 2. Close sum-rate performance illustration between MARL, LS-SCVX 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). Cell-based simulation using 100 random channel gain realizations.

thumbnailFigure 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/LS-SCVX

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 non-sparse Hessian, using the quasi-Newton 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 quasi-Newton (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 sub-optimality 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 locally-optimal algorithm with different random initial values. However, like MARL, we always initialize <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M82','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M82">View MathML</a>. 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 NL and the total number of updates (13), (14), and (15) denoted by NU. It is easy to see that only the LGM computations has non-negligible 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 Bduplicate 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 NL=I×(K2L + M) and NU=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 oscillationd. As later shown, comparing ELCI to LS-SCVX algorithm no divergence of the former algorithm has been observed.

Numerical experiments

This section compares through various numerical experiments the performance of ELCI against LS-SCVX.

We define the channel gain such that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M83','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M83">View MathML</a>, where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M84','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M84">View MathML</a> is the distance from the mth SU and the nmth receiver, α is the path loss exponent, and βm,k is a random variable with Gaussian distribution <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M85','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M85">View MathML</a>. The same approach applies for the interference channel <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M86">View MathML</a> 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, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M87','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M87">View MathML</a> dBm, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M88','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M88">View MathML</a> dBm, and N0=−70 dBm. The simulations we provide are for both CB and ad-hoc networks, separately. The purpose of this separation is to independently analyze the ad-hoc 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 ad-hoc case, SUs are randomly placed within a 500 m2 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., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M89','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M89">View MathML</a>). Each PDF is based on 500 random simulations. For additional comparison we also simulate the performance of the cell-based network for the non-varying channels case (i.e., the channel gain for a given link does not vary with k). In Figure 4, we compare ELCI against LS-SCVX where the later is performed using a random initial point, once. In order to overcome, to some extent, the possible sub-optimality of LS-SCVX (inherent to SCVX), we compare in Figure 5 ELCI with the LS-SCVX’s best performance out of 20 simulations with random different initial values. In both Figures 4 and 5, LS-SCVX 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 LS-SCVX (i.e., the worst ratio of only 0.94), and sometimes better. It is also interesting to note that for the non-varying 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 ad-hoc scenarios. Since more point to point communications can exist in the ad-hoc 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.

thumbnailFigure 4. PDF of the sum-rate ratio between ELCI and LS-SCVX’s first trial, for average-scale scenarios. Three settings with M=20and K=25: 1) cell-based (N=4), 2) ad-hoc (N=M), and 3) cell-based with non-varying (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.

thumbnailFigure 5. PDF of the sum-rate ratio between ELCI and LS-SCVX’s best outcome out of 20 trials. Same setting as in Figure 4.

thumbnailFigure 6. PDF of ELCI’s number of iteration. Same setting as in Figure 4.

Figure 7 illustrates the average sum-rate performance of ELCI and LS-SCVX for various large-scale 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 LS-SCVX (i.e., in fact in the log-log 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 ad-hoc system as K becomes very large ELCI has more loss of performance compared to the CB case, but again still minor.

thumbnailFigure 7. Close sum-rate performance illustration between LS-SCVX and ELCI for various large-scale settings, in both CB and ad-hoc networks. Each point is averaged over 50 random realizations.

thumbnailFigure 8. Corresponding time complexity of the experiments in Figure 7. Each point is averaged over 50 random realizations.

Conclusion

The problem of interference-limited sum-rate 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 LS-SCVX of the well-known state-of-the-art sub-optimal algorithm, SCVX, to cope with large problems, while keeping the initial convergence proof unchanged. Second, as a further alternative, we propose a new low-complexity 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 LS-SCVX, ELCI was shown to provide an excellent trade-off for very large-scale 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

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M90','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M90">View MathML</a>

(17)

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:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M91','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M91">View MathML</a>

(18)

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M92">View MathML</a>

(19)

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M93">View MathML</a>

(20)

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M94','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M94">View MathML</a>

(21)

Endnotes

a Simple attribution in terms of the highest channel power. In case each sub-channel have different gains, a SU selects the BS with the best channel averaged over all sub-channels.

b<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M95','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M95">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M96','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/362/mathml/M96">View MathML</a>.

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., cutting-plane method.

d When ε0is 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 Final-iteration.

Competing interests

The authors declare that they have no competing interests.

References

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

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

  3. 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)

  4. 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)

  5. 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)

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

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

  8. 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)

  9. 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)

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

  11. 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)

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

  13. 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)

  14. A Attar, O Holland, M Nakhai, A Aghvami, Interference-limited resource allocation for cognitive radio in orthogonal frequency-division multiplexing networks. IET Commun 2(6), 806–814 (2008). Publisher Full Text OpenURL

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

  16. D Yu, JM Cioffi, Iterative water-filling for optimal resource allocation in OFDM multiple-access and broadcast channels. in Proc, ed. by . IEEE GLOBECOM (San Francisco, 2006)

  17. 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)

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

  19. J Papandriopoulos, J Evans, Low-complexity distributed algorithms for spectrum balancing in multi-user DSL networks. in Proc, ed. by . IEEE ICC (Istanbul, Turkey, 2006)

  20. 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)

  21. 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)

  22. 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)

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

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

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

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

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

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

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

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

  31. A Wachter, LT Biegler, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Programm 106(1), 25–57 (2006). Publisher Full Text OpenURL