2.08.1.1 Resource allocation in communication networks

Resource allocation is a fundamental task in the design and management of communication networks. For example, in a wireless network, we must judiciously allocate transmission power, frequency bands, time slots, and transmission waveforms/codes across multiple interfering links in order to achieve high system performance while ensuring user fairness and quality of service (QoS). The same is true in wired networks such as the Digital Subscriber Lines (DSL).

The importance of resource allocation can be attributed to its key role in mitigating multiuser interference. The latter is the main performance limiting factor for heterogeneous wireless networks where the number of interfering macro/pico/femto base stations (BS) can be very large. In addition, resource allocation provides an efficient utilization of limited resources such as transmission power and communication spectrum. These resources are not only scarce but also expensive. In fact, wireless system operators typically spend billions of dollars to acquire licenses to operate certain frequency bands. Moreover, the rising cost of electricity for them to operate the infrastructure has already surpassed the salary cost to employees in some countries. Thus, from the system operator’s perspective, efficient spectrum/power utilization directly leads to high investment return and low operating cost (see e.g., [1,2]). The transmission power of a mobile terminal is another scarce resource. In this case, careful and efficient power allocation is the key to effectively prolong the battery life of mobile terminals.

Current cellular networks allocate orthogonal resources to users. For example, in a time-division multiplex access (TDMA) or a frequency-division multiplex access (FDMA) network, users in the same cell transmit in different time slots/frequency bands, and users in the neighboring cells transmit using orthogonal frequency channels. Although the interference from neighboring cells is suppressed, the overall spectrum efficiency is reduced, as each BS only utilizes a fraction of the available spectrum. According to a number of recent studies [3,4] current spectrum allocation strategies are not efficient, as at any given time and location, much of the allocated spectrum appears idle and unused. Moreover, users in cell edges still suffer from significant interference from non-neighboring cells, or pico/femto cells. In addition, for cell edge users the signal power from their own cells are typically quite weak. All of these factors can adversely affect their service quality.

To improve the overall system performance as well as user fairness, future wireless standards [5] advocate the notion of a heterogeneous network, in which low-power BSs and relay nodes are densely deployed to provide coverage for cell edge and indoor users. This new paradigm of network design brings the transmitters and receivers closer to each other, thus is able to provide high link quality with low transmission power [6,7]. Unfortunately, close proximity of many transmitters and receivers also introduces substantial in-network interference, which, if not properly managed, may significantly affect the system performance. Physical layer techniques such as multiple input multiple output (MIMO) antenna arrays and multiple cell coordination will be crucial for effective resource allocation and interference management in heterogeneous networks.

An effective resource allocation scheme should allow not only flexible coordination among BS nodes but also sufficiently distributed implementation. Coordination is very effective for interference mitigation among interfering nodes (e.g., Coordinated Multi-Point (CoMP)), but is also costly in terms of signaling overhead. For example, CoMP requires full BS coordination as well as the sharing of transmit data among all cooperating BSs. In contrast, a distributed resource allocation requires far less signaling overhead and no data sharing, albeit at the cost of possible performance loss. For in-depth discussions of various design issues in heterogenous networks, we recommend the recent articles and books including [7–13].

In this article, we examine several design and complexity aspects of the optimal physical layer resource allocation problem for a generic interference channel (IC). The latter is a natural model for multi-user communication networks. In particular, we characterize the computational complexity, the convexity as well as the duality of the optimal resource allocation problem. Moreover, we summarize various existing algorithms for resource allocation and discuss their complexity and performance tradeoff. We also mention various open research problems throughout the article.

2.08.1.2 Notation

Throughout, we use bold upper case letters to denote matrices, bold lower case letters to denote vectors, and regular lower case letters to denote scalars. For a symmetric (or Hermitian) matrix , the notation (or ) signifies X is positive semi-definite (or definite). User indices are denoted by subscripts, while frequency tone indices are denoted by superscripts. Zero mean normalized complex Gaussian distributions are denoted by .

2.08.1.3 Interference channels

An interference channel (IC) represents a communication network in which multiple transmitters simultaneously transmit to their intended receivers in a common channel. See Figure 8.1 for a graphical illustration of the IC. Due to the shared communication medium, each transmitter generates interference to all the other receivers. The IC model can be used to study many practical communication systems. The simplest example is a wireless ad hoc network in which transmitters and their intended receivers are randomly placed. When all these nodes are equipped with multiple antenna arrays, the channel becomes a MIMO IC. See Figure 8.2 for a graphical illustration of a 2-user MIMO IC. If each transmitter and receiver pair communicates over multiple parallel subchannels, the resulting overall channel model becomes a parallel IC. This parallel IC model can be used to describe communication networks employing Orthogonal Frequency Division Multiple Access (OFDMA) where the available spectrum is divided into multiple independent tones/channels. Networks of this kind include the DSL network or the IEEE 802.11 networks.

Another practical network is the multi-cell heterogenous wireless network. In the downlink of such network a set of interfering transmitters (BSs) simultaneously transmit to their respective groups of receivers. This channel is hitherto referred as an interfering broadcast channel (IBC). The uplink of this network can be modeled as an interfering multiple access channel (IMAC). See Figures 8.3 and 8.4 for graphical illustrations of these two channel models. Note that both IMAC and IBC reduce to an IC when there is only a single user in each cell.

Our ensuing discussions will be focussed on these channel models. We will illustrate key computational challenges associated with optimal resource allocation and suggest various practical resource allocation approaches to overcome them.

2.08.1.4 System model

We now give mathematical description for three types of IC model—the scalar, parallel and MIMO IC models. Let us assume that there are K transmitter and receive pairs in the system, and we refer to each transceiver pair as a user. Let denote the set of all the users.

2.08.2.1 Capacity results for IC model

In this subsection we briefly review some information theoretical results related to the capacity of the interference channel.

Consider a single user point to point additive white Gaussian noise (AWGN) scalar channel in the following form

(8.12)

where are the transmitted signal, the received signal, the channel coefficient, and the Gaussian noise, respectively. Assume that the noise is independently distributed as , and that the signal has a power constraint . An achievable transmission rate R for this channel is defined as the rate that can be transmitted and decoded with diminishing error probability. The capacity of a channel C is the supremum of all achievable rates. Let us define the signal to noise ratio (SNR) of the channel as , then the capacity of the Gaussian channel is given by

(8.13)

We refer the readers’ to the classic books such as Cover Thomas [14] and the online course for an introductory treatment of information theory.

Now consider a 2-user interference channel

(8.14)

The capacity region of this channel is the set of all achievable rate pairs of user 1 and user 2. Unlike the previous point to point channel, the complete characterization of the capacity region in this simplest 2-user IC case is an open problem in information theory. The largest achievable rate region for the interference channel is the Han-Kobayashi region [15], and it is achieved using superposition coding and interference subtraction. Recently, Etkin et al. [16] showed that this inner region is within one bit of the capacity region for scalar ICs. The capacity of the scalar interference channel under strong or very strong interference has been found in [15,17,18]. In particular, in the very strong interference case, i.e., and , the capacity region is given as

(8.15)

where is the transmission rate for user k. This result indicates that in very strong interference case the capacity is not reduced. The references [19,20] include recent results that establish the capacity region for more general MIMO and parallel ICs in the strong interference case. However, for the general case where the interference is moderate, the capacity region remains unknown.

The capacity of a communication channel can be approximated by the notion of degrees of freedom. Recall that in the high SNR regime the capacity of a point to point link can be expressed as

(8.16)

In this case we say the channel has d degrees of freedom. In a 2-user interference channel, the degrees of freedom region can be characterized as follows. Let the sum transmit power across all the transmitters be , and let denote the transmission rate achievable for user k. Then the capacity region of this 2-user channel is the set of all achievable rate tuples . The degree of freedom region for this channel approximates the capacity region, and is defined as (see [21])

(8.17)

The goal of resource allocation is to achieve the optimal performance established by information theory, subject to resource budget constraints. Unfortunately, optimal strategies for achieving the information theoretic limits are often unknown, too difficult to compute or too complicated to implement in practice. For practical considerations, we usually rely on simple transmit/receive strategies (such as linear beamformers) for resource allocation, with the goal of attaining an approximate information theoretic performance bound. The latter can be in terms of the degrees of freedom or some approximate capacity bounds which we describe next.

2.08.2.2 Achievable rate regions when treating interference as noise

Due to the difficulties in characterizing the capacity region and the optimal transmit/receive strategy for a general interference channel, many works in the literature study simplified transmit/receive strategies and the corresponding achievable rate regions. One such simplification, which is well motivated from practical considerations, is to assume that low-complexity single user receivers are used and that the multiuser interference is treated as additive noise. The authors of [22,23] show that treating interference as noise in a Gaussian IC actually achieves the sum-rate channel capacity if the channel coefficients and power constraints satisfy certain conditions. These results serve as a theoretical justification for this simplification. In the rest of this article we will treat interference as noise at the receivers. Let us first review some achievable rate region results for different IC models with this simplified assumption.

2.08.3.1 Problem formulations

A communication system should provide users with QoS guarantees, and fairness through efficient resource utilization. Mathematically, the resource allocation problem can be formulated as the problem of optimizing a certain system level utility function subject to resource budget constraints.

A popular family of utility functions is the so called “-fair” utility functions, which can be expressed as

(8.35)

where denotes the transmission rate of user k. As pointed out in [31], different choices of the parameter give different priorities to user fairness and overall system performance. We list four commonly used utility functions that belong to the family of -fair utility functions:

In terms of overall system performance, these utility functions can be ordered as

(8.36)

In terms of user fairness, the order is reversed. We note that except for the case in which the interference is weak, these utility functions are nonconcave in general. For example, in Figure 8.6 we plot the sum rate utility for a 2-user scalar IC in cases where the interference is either weak or strong. Moreover, in most cases, it is not possible to represent these utility functions as concave ones via a nonlinear transformation. See [32] for an impossibility result in scalar interference channel. This is consistent with the complexity status (NP-hard) of the utility maximization problems [33–35] (see discussions in Section 2.08.3.2).

If we wish to find a resource allocation scheme that maximizes the system level performance, then we need to determine the conditions under which the system level problem is easy to solve. Whenever such conditions are met, efficient system level resource allocation decision can be carried out by directly solving a convex optimization problem. Intuitively, when the crosstalk coefficients are zero or sufficiently small (low interference regime), the utility functions should be concave. It will be interesting to analytically determine how small the crosstalk coefficients need to be in order to preserve concavity.

From a practical perspective, the conditions for the concavity of the utility function (in terms of the crosstalk coefficients) are valuable because they can be used to find high quality approximately optimal resource allocation schemes. In particular, we can use these conditions to partition the users into small groups within which the interference is less and resource allocation is easy. Different groups can be put on orthogonal resource dimensions, because the groups cause too much interference to each other. Ultimately a good resource allocation scheme in an interference limited network will likely involve a hybrid scheme whereby some small groups of users share resources, while different groups are separated from competition.

The lack of concavity (or more generally, the lack of concave reformulation/transformation) has made it difficult to numerically maximize these utility functions for resource allocation. To circumvent the computational difficulties, and to reduce the amount of channel state information required for practical implementation, some researchers have proposed to use alternative utility functions for resource allocation. For example, both the mean squared error (MSE) and the leakage power cost functions have been proposed as potential substitutes for the rate-based utility functions listed above [36–39]. Recently, a number of studies [32,40–42] have characterized a family of system utility functions that, under appropriate transformations, admit concave representations. Such transformations allow the associated utility maximization problems to be easily solvable. We refer the readers to Holger Boche’s web page for details on this topic. Unfortunately these utility functions are not directly related to individual users’ transmission rates, hence the solutions of the associated optimization problems tend to give suboptimal system performance (in terms of the users’ achievable rates). We shall not further elaborate on these resource allocation approaches in this article. Instead, we will focus on the use of above listed rate-based utility functions for resource allocation.

Let us describe several utility maximization problems to be considered in this article.

We note that for the latter two formulations, the minimum rate/SINR requirements provide fairness to the users, while the optimization objectives are aimed at efficient utilization of system resource (e.g., spectrum or power). For both of these two problems, the feasibility of the set of rate/SINR targets needs to be carefully examined, as the rate/SINR requirements may not be simultaneously satisfiable.

2.08.3.2 Complexity of the optimal resource allocation problems

The aforementioned optimal resource allocation problems are nonconvex. However, the lack of convexity does not necessarily imply that the problem is difficult to solve. In some cases, it may be possible for a nonconvex problem to be appropriately transformed into an equivalent convex one and solved efficiently. A principled approach to characterize the intrinsic difficulty of an utility maximization problem is by way of the computational complexity theory [43].

In the following, we summarize a number of recent studies on the computational complexity status of these resource allocation problems. These complexity results suggest that in most cases solving the utility maximization problems to global optimality is computationally intractable as the number of users in the system increases.

Table 8.1 lists the complexity status for resource allocation problems with specific utility functions for the parallel and MISO IC models. Note that the scalar IC model is included as a special case.

Table 8.2 summarizes the complexity status for the minimum rate utility maximization problem and the sum power minimization problem with the QoS constraint in MIMO IC model (i.e., problem (8.41) with min-rate utility and problem (8.44)). Note that the results in Table 8.2 are based on the assumption that all transmitters and receivers use linear beamformers and that each mobile receives a single data stream.

Recall that the MIMO IC is a generalization of the Parallel IC (see Section 2.08.2.2). It follows that the complexity results in Table 8.1 hold true for the MIMO IC model with an arbitrary number of data streams per user. We refer the readers to the author’s web page for recent developments in the complexity analysis as well as other resource allocation algorithms.

2.08.3.3 Algorithms for optimal resource allocation

We now describe various utility maximization based algorithms for resource allocation. These algorithms will be grouped and discussed according to their main algorithmic features. Since the min-rate utility function is non-differentiable, it requires a separate treatment that is different from the other utility functions. We begin our discussion with resource allocation algorithms based on the min-rate utility maximization.

2.08.4.1 Game theoretical formulations

In scenarios where users cannot exchange information explicitly, it is no longer possible to allocate resources using the maximizer of a system wide utility function. Instead, we need to rely on alternative solution concepts for distributed resource allocation. One such concept that is particularly useful in our context is the renowned notion of Nash equilibrium (NE) for a noncooperative game; see [118,119], and the Yale Open Course online. In a noncooperative game, there are a number of players, each seeking to maximize its own utility function by choosing a strategy from an individual strategy set. However, the utility of one player depends on not only the strategy of its own, but also those of others in the system. As a result, when players have conflicting utility functions, there is usually no joint player strategy that will simultaneously maximize the utilities of all players. For such a noncooperative game, a NE solution is defined as a tuple of joint player strategies in which no single player can benefit by changing its own strategy unilaterally.

Mathematically, a K-person noncooperative game in the strategic form is a three tuple , in which is the set of players of the game; is the joint strategic space of all the players, with being player k’s individual strategy space; , where is user k’s utility function. In the above definition we have used to denote player k’s strategy, to denote the strategies of all remaining users. It is clear that player k’s strategy depends on its own strategy as well as those of others . A NE of the game is defined as the set of joint strategies of all the players such that the following inequality is satisfied simultaneously for all players

(8.93)

Clearly at a NE, the system is stable as none of the players has any intention to switch to a different strategy. We define a best response function for each player in the game, as its best strategy when all other players have their strategies fixed

(8.94)

Using this definition, a NE of the game can be alternatively defined as

(8.95)

Figure 8.12 is an illustration of the NE point of a game with 2-player and affine best response functions. This figure also shows how a sequence of best response may enable the players to approach the NE.

Let us illustrate the notion of NE in our 2-user scalar IC model (8.14). Suppose these two users are the players of a game, and their strategy spaces are . Assume that the users’ utility functions are their maximum transmission rates defined in (8.18). Thus, for this example, user 1’s best response function admits a particular simple expression

(8.96)

This says that regardless of user 2’s transmission strategy, user 1 will transmit with full power. The same can be said about user 2. Consequently, the only NE of this game is the transmit power tuple . Obviously, assuming that each user is indeed selfish and they intend to maximize their own utility, the NE point can be implemented without any explicit coordination between the users. Now let us assess the efficiency of such power allocation scheme in terms of system sum rate. In Figures 8.13 and 8.14, we plot the rate region boundary and the NE points for different interference levels. We see that when interference is low, the NE corresponds exactly to the maximum sum rate point. However, when interference is strong, the NE scheme is inferior to the time sharing scheme in which the users transmit with full power in an orthogonal and interference free fashion (e.g., TDMA or FDMA). Nonetheless, it should be pointed out that the NE point can be reached without user coordination, while the time sharing scheme requires the users to synchronize their transmissions.

We refer the readers tothe September 2009 issue of IEEE Signal Processing Magazine for the applications of game theory to wireless communication and signal processing.

2.08.4.2 Distributed resource allocation for interference channels

Early works on distributed physical layer resource allocation in wireless networks largely deal with the scalar IC models. Sarayda et al. [120,121] and Goodman and Mandayam [122] are among the first to cast the general scalar power control problem in a game theoretic framework. They proposed to quantify the tradeoff between the users’ QoS requirements and energy consumption by a utility function in the form:

(8.97)

where is user k’s fixed transmission rate, and is a function of user k’s SINR that characterizes its bit error rate (BER). They showed that any NE point is inefficient in the Pareto sense, i.e., it is possible to increase the utility of some of the terminals without hurting any other terminal. To improve the efficiency of the power control game, they proposed to charge the users with a price that is proportional to their transmit powers. Specifically, each users’ utility function now becomes , where is a positive scalar that can be appropriately chosen by the system operator. They showed that this modified game always admits a NE, and proposed an algorithm that allows the users to reach one of the NEs by adapting their transmit powers in the best response fashion. Meshkati et al. [123,124] extended the above works to the multi-carrier data network. They defined the utility function for each user as

(8.98)

where the function represents the BER of user k, and it incorporates the underlying structure of different linear receivers. However, such multi-carrier power control game is more complicated than the scalar power control game introduced early, and in certain network configurations it is possible that no NE exists (see [123]).

An alternative approach in distributed power control is to directly optimize the individual users’ transmission rates. Consider a K-user N-channel parallel IC model. Assume that each user is interested in maximizing its transmission rate, and again assume that its total transmission power budget is . Then the users’ utility functions as well as their feasible spaces can be expressed as

(8.99)

(8.100)

Fixing , user k’s best response solution is the classical water-filling (WF) solution

(8.101)

where is the dual variable ensuring the sum power constraint, and the operator . Figure 8.15 illustrates the WF solution for user k. We note that in order to compute the WF solution, user k needs to know the terms , which is simply the set of noise-plus-interference (NPI) levels on all its channels. They can be measured locally at its receiver. We refer to this game as a WF game.

Yu et al. [60] is the first to formulate the distributed power control problem as a WF game. The authors proposed an iterative water-filling algorithm (IWFA) in which the following two steps are performed iteratively:

Variations of the IWFA algorithm allow the users to update using different schedules. The following three update schemes have been proposed: (a) simultaneous update, in which all the users update their power in each iteration, see [60,125]; (b) sequential update, in which a single user updates in each iteration, see [125,126]; (c) asynchronous update, in which a random fraction of users update in each iteration, and they are allowed to use outdated information in their computation, see [127]. Regardless of the specific update schedule used, the IWFA algorithm is a distributed algorithm because only local NPI measurements are needed for the users to perform their independent power update.

The properties of the WF game as well as the convergence conditions of the IWFA have been extensively studied. The original work has only provided sufficient conditions for the convergence of the IWFA in a 2-user network. Subsequent works such as [125,126,128–130] generalized this result to networks with arbitrary number of users. Luo and Pang [126] characterized the NE of the water-filling game as the solution to the following affine variational inequality (AVI)

(8.102)

where is a block partitioned matrix with its th block defined as . Using the AVI characterization (8.102), they also showed that the sequential version of the IWFA corresponds to the classical projection algorithm whose convergence to the unique NE of the water-filling game is guaranteed if the following contraction condition is satisfied

(8.103)

where and is the strictly lower and strictly upper triangular part of a matrix given by

(8.104)

Also using the AVI characterization (8.102), the authors of [129,125] further proved that the condition

(8.105)

is sufficient for the convergence of the IWFA as well as the uniqueness of the NE. We refer the readers to [131] for a detailed comparison of various conditions for the convergence of the IWFA. It is worth noticing that all the sufficient conditions for the convergence of IWFA require that the interference among the users are weak. For example, a sufficient condition for (8.105) is

(8.106)

where is a set of constant scalars. Intuitively, this condition says that at the receiver of each user , the power of the useful signal should be larger than the power of total interference. When the interference is strong, IWFA diverges. Leshem and Zehavi [132] provided an example in which all forms of IWFA diverge, regardless of their update schedules. We remark that extending the IWFA so that it converges in less stringent conditions that do not require the interference to be weak is still an open problem. Without any algorithmic modifications, the standard IWFA is only known to converge [126] when the crosstalk coefficients are symmetric

regardless the interference levels.

The IWFA has been recently generalized to MIMO IC model. In the MIMO WF game, the strategy of each user is its transmission covariance matrix . The rate utility function and strategy set for user k can be expressed as

(8.107)

(8.108)

In this case, each user k’s best response is again a water-filling solution, see [133]. Arslan et al. [134] suggested that in each iteration, the users’ covariance can be updated as

(8.109)

where is a set of constants that satisfy and . They claimed that their algorithm converges when the interference is weak, but no specific conditions are given. This work has been generalized by Scutari et al. [131,135], in which rigorous conditions for the convergence of the MIMO IWFA have been derived. In particular, consider a MIMO network in which and the direct link channel matrices are all nonsingular. Define a matrix as

(8.110)

Then the condition is sufficient for the convergence of the sequential/simultaneous/asynchronous MIMO IWFA. This condition is again a weak interference condition, and future work is needed to extend the MIMO IWFA to work in networks without this restriction. We refer the readers to web pages of Yu, Palomar, andPangfor other works related to the WF games and IWFA.

The above parallel and MIMO WF games have been extended in several directions. A series of recent works considered the robustness issue in a WF games. For instance, Gohary et al. [136] considered the WF game in the presence of a jammer. Let us denote user 0 as the jammer and denote its transmission power as . The rate utility function of a normal user k () becomes

(8.111)

Suppose the jammer’s objective is to minimize the utility of the whole system. This can be reflected by its utility function and the strategy set

(8.112)

(8.113)

Gohary et al. [136] proposed a generalized IWFA (GIWFA) algorithm in which the normal users and the jammer all selfishly maximize their respective utility functions. Notice that the selfish maximization problems are all convex. The convergence condition for the GIWFA is

(8.114)

where the matrix is defined in (8.104), and and are constants related to the system parameters. Clearly this condition is more restrictive than those of the original IWFA, for example the condition (8.103). This is partly because the presence of the jammer introduces uncertainty to the NPI that each normal user experiences.

Uncertainty of the NPI is also caused by events such as sudden changes in the number of users in the system or errors of interference measurement at the receivers. Setoodeh and Haykin [137] seek a formulation that takes into consideration the worst case NPI errors. Let denote the power of NPI that user k should have experienced on channel n if no measurement errors occur. Let be the measured NPI value, with representing the NPI uncertainty. Let and suppose it is bounded, i.e., for some . In this robust WF game, the objectives of the users are to maximize their worst case transmission rate. In other words, user ks utility function can be expressed as

(8.115)

This formulation trades performance in favor of robustness, thus the equilibrium solution obtained is generally less efficient than that of the original IWFA. In [138], an averaged version of IWFA was proposed which converges when the error of the NPI satisfies certain conditions. In [139], the authors provided a probabilistically robust IWFA to deal with the quantization errors of the NPI at the receiver of each user. In this algorithm, users allocate their powers to maximize their total rate for a large fraction of the error realization.

Another thread of works such as [58,140–143] generalized the original WF game and the IWFA to interfering cognitive radio networks (CRN). In a CRN, the secondary users (SUs) are allowed to use the spectrum that is assigned to the primary users (PUs) as long as the SUs do not create excessive interference to the primary network. Suppose the secondary network is a K-user N-channel parallel IC. Let denote the set of PUs in the network. Let denote the channel gain from SU k to PU q on channel n. The following aggregated interference constraints are imposed on the secondary network (these constraints are also referred to as the interference temperature-constraints, see [144,145])

(8.116)

where represents the maximum aggregated interference allowed at the receiver of PU q on channel n. The original WF algorithm needs to be properly modified to strictly enforce these interference constraints in the equilibrium. Xie et al. [143] formulated the power allocation problem in this CRN as a competitive market model. In this model, each channel has a fictitious price per unit power, and the users must purchase the transmission power on each channel to maximize their data rates. Scutari et al. [135,146] systematically studied the WF game with interference constraints. For each primary user q, they introduced a set of interference prices . Each SU is charged for their contribution of total interference at PUs’ receiver. Specifically, a SU k’s utility function and feasible set is defined as

(8.117)

(8.118)

where is user k’s transmission rate. The NE of this interference-constrained WF game is the tuple that satisfies the following conditions

Scutari et al. [135,146] derived the conditions for the existence and uniqueness of the NE for this game. Introduce a matrix

(8.119)

where . Then the condition guarantees the uniqueness of the NE. A set of distributed algorithms that alternately update the users’ power allocation and the interference prices were proposed to reach the NE of this game. The MIMO generalization has been considered in [147], whereby both the SUs and PUs are equipped with multiple antennas. Another extension [142] considered the possibility that the SU-PU channels may be uncertain, and formulated a robust WF game that ensures the SU-PU interference constraints are met even in the worst case channel conditions.

All the above mentioned WF games can be categorized as rate adaptive (RA) games, in which the users selfishly maximize their own data rates. One drawback of the RA formulation is that individual users have no QoS guarantees. Alternatively, a fixed margin (FM) formulation allows each user to minimize its transmission power while maintaining its QoS constraint. The FM formulation is more difficult to analyze due to the coupling of the users’ strategy spaces resulted from the QoS constraint. For the parallel IC model, the utility function and the strategy set for user k in a FM formulation can be expressed as

(8.120)

(8.121)

where is the rate target for user k. The solution to the individual users’ utility maximization problems, assuming the feasibility of the rate targets, is again a water-filling solution

(8.122)

where is the water-level that is associated with user k’s rate constraint.

A NE of this FM game (which is usually referred to as the generalized NE due to the coupling of the users’ strategy spaces) is defined as a power vector that satisfies

(8.123)

Similar to the min-power QoS constrained formulation discussed in the previous section, the first thing we need to characterize for this FM game is the feasibility of a given set of rate targets. The following condition is among many of those that have been derived in [148] which guarantee the existence of a bounded power allocation achieving the given set of rate targets

(8.124)

This condition is again a weak interference condition. The following condition is sufficient for the uniqueness of the (generalized) NE of the FM game

(8.125)

where is related to the set of given rate targets. This condition is also sufficient for the convergence of a FM-IWFA in which the users sequentially or simultaneously update their power using the WF solution. Algorithmic extension of this work to the CRN with interference constraints of the form (8.116) has been considered recently in [149]. It remains to see how the FM games and their theoretical properties (e.g., uniqueness of the NE, convergence of the FM-IWFA) can be extended to MIMO CRNs with interference constraints.

We remark that the NE points of the various RA based WF games introduced in this section is generally inefficient, in the sense that the sum rate of the users is often smaller compared with that of the socially optimal solutions.¹ In Figure 8.16, we illustrate such inefficiency of the NE in a parallel IC with and randomly generated channel coefficients. We plot the NE point of the WF game as well as the rate region boundary achieved by the SCALE algorithm. In order to improve the efficiency of the NE, user coordination must be incorporated into the original WF game. The pricing algorithms such as MDP, M-IWF or WMMSE introduced in the previous section are examples of such extensions. In those algorithms, system efficiency is improved due to explicit message exchange and cooperation among the users. Careful analysis is needed to identify the tradeoffs between the improvement of the system sum rate and the signaling overhead. Evidently, when the total number of users in the system is large, a complete cooperation of all users is too costly. An interesting problem is to decide how to partition the users into collaborative groups in a way that strike an optimal tradeoff between system performance and coordination overhead.

a. In the case of for all k, interference alignment is impossible unless

b. In the case of , interference alignment requires

which further implies

 For a given channel realization, to determine whether a given set of DoF tuple is achievable is NP-hard (i.e., exponential effort is likely to be required for large number of users).

 Without channel extensions, the average DoF per user is shown to be at most , which is significantly smaller than when there are a large number of independent channel extensions (see [21]). Here M is the number of antennas at each transmitter and receive. Notice that the average per user DoF of approximately doubles that of the orthogonal approaches (e.g. TDMA or FDMA).

 It requires too many channel extensions to reap the DoF benefit promised by Cadambe and Jafar [21].

 It requires full CSI, which can be difficult for large networks.

 It often requires selecting a set of feasible DoFs for the users a priori, which is difficult.

See Vol. 1, Chapter 3 Discrete-Time Signal and Systems

See Vol. 1, Chapter 12 Adaptive Filters

See Vol. 3, Chapter 19 Array Processing in the Face of Nonidealities