Crystallized Rate Regions for MIMO Transmission

The multicell uplink interference MIMO channel is considered in this paper. Without loss of generality and for the sake of clarity, the channel model consists in the 2-user 2-cell scenario, in which each user (denoted as the Mobile Terminal (MT)) communicates with his own Base Station (BS) causing interference to the neighboring cell (see Figure 1(a)). Each MT is equipped with (transmit) antennas, and each BS has (receive) antennas. Moreover, user can transmit data with maximum total power . Perfect channel knowledge in all MTs is assumed. In order to ease the analysis, we limit our derivation to the MIMO case (see Figure 1(b)), where both the transmitter and the receiver use only two antennas.

User transmits the signal vector through the multipath channel , where

The channel matrix consists of the actual values of channel coefficients , which define the channel between transmit antenna at the th MT and the receive antenna at the th BS. In the considered 2-user MIMO case, only four channel matrices are defined, that is, , (which describe channel between the first MT and first BS or second MT and second BS, resp.), , and (which describe the interference channel between first MT and second BS and between second MT and first BS, resp.). Additive White Gaussian Noise (AWGN) of zero mean and variance is added to the received signal. Receiver observes the useful signal, denoted as , coming from the th user. Moreover, in the interference scenario, receiver ( ) receives also interfering signals from other users located at the neighboring cell . Interested readers can find solid contribution on the interference channel capacity in the rich literature, for example, [1, 2, 22, 23]. When interference is treated as noise, the achievable rates for 2-user interference MIMO channel are defined as follows [22]:

where and denote the rate of the first and second user, respectively, denotes transpose conjugate of matrix , is the determinant of matrix , and is the th user data covariance matrix, that is, and . We define the rate region as .

One can state that the formulas presented above allow us to calculate the rates that can be achieved by the users in the MIMO interference channel scenario in a particular case when no specific MIMO transmission technique is applied. Such approach can be interpreted as a so-called Transmit Selection Diversity (TSD) MIMO technique [16], where the BS can decide between one of the following strategies: to put all of the transmit power to one antenna ( strategies, where is the number of antennas), to be silent (one strategy), or to equalize the power among all antennas (one strategy).

When the channel is known at the transmitter, the channel capacity can be optimized by means of some well-known MIMO transmission techniques. Precisely, one can decide for example to linearize (diagonalize) the channel by the means of Eigenvalue Decomposition (EvD) or Singular Value Decomposition (SVD) [16, 17, 24]. Such approach will be denoted hereafter as SVD-MIMO. Moreover, in order to avoid or minimize the interference between the neighboring users within one cell, BS can precode the transmit signal. In such a case, the sets of properly designed transmit and receive beamformers are used at the transmitter and receiver side, respectively. The precoders can be either calculated continuously based on the actual channel state information from all users or can be defined in advance (predefined) and stored in a form of a codebook, from which the optimal set of beamformers is selected for each user based on its channel condition. The later approach is proposed in the Long Term Evolution (LTE) standard where for the MIMO case a specific codebook is proposed [20]. Similar assumption is made for the so called Per-User Unitary Rate Control (PU²RC) MIMO systems, where the set of beamformers is calculated [18, 21]. Since the process of finding the set of transmit and receive beamformers is usually time and energy consuming and require accurate Channel State Information (CSI), the optimal approaches (where the precoders are calculated based on the actual channel state) are replaced by the above-mentioned list of predefined beamformers stored in a form of a codebook. Since the number of precoders is limited, the performance of such approach could be worse than the optimal one, particularly in the interference channel scenario. Based on this observation, new techniques of generation of the set of beamformers have been proposed. One of them is called random-beamforming [19, 25], since the set of precoders is obtained in a random manner. At every specified time instant, a new set of beamformers is randomly generated, from which the subset of precoders that optimize some predefined criteria is selected. Simulation results given in [19, 25] and Section 5.1 show that assuming such approach, one can achieve the global extremum in particular when the codebook size is large. When the set of randomly generated beamformers is used, the set of receive beamformers has to be calculated at the receiver. Various criteria can be used, just to mention the most popular and academic ones: Zero-Forcing (ZF), MinimumMean Squared Error (MMSE), or Maximum-Likelihood (ML) [16, 17]. In our simulation, we consider the combination of these methods, that is, ZF-MIMO, MMSE-MIMO, and ML-MIMO, with three different codebook generation methods—one of the size , that is, generated randomly (denoted hereafter as RAN- ), one defined as proposed for LTE and one specified for PU RC-MIMO. In other words, the abbreviation ZF-MIMO-LTE describes the situation when the transmitter uses the LTE codebook and the set of receive beamformers is calculated using the ZF criterion.

However, let us stress that (2) has to be modified when one of the precoding techniques (including SVD method, which is a particular case of precoding) is applied. Thus, the general equations for the achievable rate computation are defined as follows:

where and denote the set of receive and transmit beamformers, respectively, obtained for the th user. In a case of SVD-MIMO, the above-mentioned vectors are obtained by the means of singular value decomposition of the channel transfer matrix whereas for the other precoded MIMO systems, the set of receive coefficients is calculated as follows [23]:

()for zero-forcing receiver

()for MMSE receiver

()for the ML receiver the elements of receive beamformers are equal to 1 (in other words, no receive beamforming is used).

The last Hermitian conjugate in (4) and in (5) is due to the assumed definition of the achievable user rates in (3).

For comparison purposes, the spatial waterfilling technique will be considered [26], where the transmit power is distributed among the antennas based on the waterfilling algorithm. The spatial waterfilling approach will be denoted hereafter as SWF-MIMO.

In [8], the achievable rate regions in the 2-user SISO scenario have been studied, where the authors have treated the interference as Gaussian noise. It has been stated that the rate region for the general -user channel is found to be the convex hull of the union of hyper-surfaces [7], which means that the rate regions entirely encloses a straight line that connects any two points which lie within the rate region bounds. In the 2-user case, the rate regions can be easily represented as the surface limited by the horizontal and vertical axes and the boundaries of the 2-dimensional hypersurface (straight lines). Let us stress that the same conclusions can be drawn for the MIMO case. We will then discuss various achievable rate regions for the interference MIMO channel. We will analyze the properties of the rate regions introduced below in three cases: when the results are averaged over 2000 channel realizations (Case ) and for specific channel realizations (Cases and ).

Similar analysis can be applied for the SVD-MIMO case. In such a situation, the BS can also select one of the four strategies defined in the previous subsection however, the precoder is computed in an (sub) optimal way by the means of SVD based on the information on the channel transfer function. The channel transfer functions that define the channel between user in the th cell and the th BS in a th cell are assumed to be unknown by the neighboring BSs. An exemplary plot of the achievable rate region for 2000 channel realizations is presented in Figure 5. One can observe that the obtained rate region is concave, thus the time-sharing approach seems to provide better results. As in a TSD-MIMO case, the obtained results are characterized by a higher number of corner points (degrees of freedom) when compared to the Single-Input/Single-Output (SISO) transmission. The transmitter can select one of the corner points in order to optimize some predefined criteria (like minimization of interference between users). The spatial waterfilling line is also shown in this figure which matches the line (i.e., the line when both users choose the third strategy with equally distributed power among transmit antennas every time and control the transmit power to maximize the capacity). Let us stress the difference between the SWF-line and the SVD frontier line. The former is obtained as follows: user 1 transmit with the maximum allowed power using SWF technique and at the same time user 2 increases its power from 0 to . Next, the situation is reversed—the second user transmits with maximum allowed power and user 1 reduces the transmit power from to 0. In other words, the covariance matrix is simply the identity matrix multiplied by the actual transmit power. Contrary to this case, the SVD frontier line represents the maximum possible rates that can be achieved by both users for every possible realization of the covariance matrix , whose trace is less or equal to the maximum transmit power, and when precoding based on SVD of the channel transfer function has been applied. The frontier line defines the maximum theoretic rates that can be achieved by both users. One can observe that although both lines start and end at the same points of the achievable rate region, the influence of interference is significantly higher in the SWF approach.

The methodology proposed in the previous sections can be also applied in a case of OFDM transmission. In such a case, the interferences will be observed only in a situation, when the neighboring users transmit data on the same subcarrier. Two achievable rate regions for OFDM transmission are presented below that is, in Figure 6, the rate region averaged over 2000 different channel realizations is shown, and in Figure 7, the rate region achieved for one arbitrarily selected channel realization are presented (in particular, the channel between the first user and its BS was worse than the second user-channel attenuation was higher, and the maximum transmit power of the second user was twice higher than for the first one). In both figures, the time-sharing lines are plotted. Moreover, the curves that show the rate region boundaries when the users play one specific strategy all the time are shown (represented as the dashed lines in the figure).

The obtained results are similar to those achieved for the MIMO case. However, some significant differences can be found, like the difference in the achievable rates in general—the maximum achievable rates are lower in a OFDM case comparing to the MIMO scenario.

The idea of the crystallized rate regions has been introduced in [8] and can be understood as an approximation of the achievable rate regions by the convex time-sharing hull, where the potential curves between characteristic points (e.g., , , and in Figure 2) are replaced by the straight lines connecting these points.

One can observe from the results shown in Figure 4 that for the MIMO case, the crystallized rate region for the 2-user scenario has much more characteristic points (i.e., the points where both users transmit with the maximum power for selected strategy) than in the SISO case (see [8] for comparison). In order to create the convex hull, only such points can be selected, which lie on the frontier line. Moreover, the selection of all characteristic points that lie on border line could be nonoptimal, thus only a subset of these points should be chosen for the time-sharing approach (compare Figures 3 and 4).

Let us denote each point in the rate region as , that is, ,   and ,   . Point in Figure 2 can be defined as that is, user one transmits with the maximum total power and the second user is silent; point , as ; that is, the first user does not transmit any data and the second user transmits with the maximum total power; point is defined as ; that is, both users transmit with the maximum total power. One can observe that these points are corner (characteristic) points of the achievable rate region. In the 2-user TSD-MIMO channel, there exist 15 points, which refer to any particular combination of the possible strategies. In general, for the -user MIMO case, there exist points; that is, the th user can put all power to one antenna ( possibilities), divide the power equally among the antennas (one possibility), or be silent (one possibility). We do not take into account the case when all users are silent. In a SISO case, and the number of strategies is limited to two (i.e., the division of the power equally among all antennas denotes that all the power is transmitted through the antenna).

Following the approach proposed in [8], we state that instead of power control problem in finding the metrics , the problem becomes finding the appropriate time-sharing coefficients of the corner points. For the 2-user TSD-MIMO case, we will obtain 15 points, that is, for ,   , which fulfill . In our case, the time-sharing coefficients relate to the specific corner points; that is, the coefficient defines the point, where user 1 choose the strategy and user 2 selects the strategy . Consequently, (2) can be rewritten as in (6), where denotes the th user covariance matrix while choosing the strategy . Let us stress that any solution point on the crystallized rate border line (frontier) will lie somewhere on the straight lines connecting any of the neighboring characteristic points.

Similar conclusions can be drawn for the precoded MIMO systems, where (6), that defines the achievable rate in a time-sharing approach, has to be rewritten in order to include the transmit and receive beamformers set (see (7))

Let us formulate the LP problem of finding the optimal time-sharing coefficients . Following [28, 29] and for the sake of simplicity, we limit the problem to the sum-rate maximization (the weighted sum) as presented below:

where denotes the expectation over the set of all probabilities. We can limit ourselves into 2-users 2-BSs scenario with strategies. In such a case, the LP problem can be presented as follows:

where is the utility for player when the joint action pair is and is the corresponding joint probability for that action pair. The first correlated equilibrium constraint can be presented in matrix form with the following inequality:

Then, the augmented form of a LP problem can be formulated as

where and are vectors corresponding to the slack variables.

Let us denote a simplex of as . Assuming transmit-receive antennas or equivalently codewords in the codebook, the solution of the LP problem formulated above is one of the vertexes of the polyhedron (i.e., ( )-hedron), where the number of vertexes is equal to and each vertex is .

Several of the vertexes correspond to the Nash Equilibrium (NE), specifically the ones that are the solution if ,   is the largest among all . However, it may be more beneficial when all players cooperate; that is, for ,   , especially in case of severe interference between the players, thus the correlated equilibrium may be the optimal strategy.

A well-known Simplex algorithm [13] can be applied to solve the formulated problem, but the number of necessary operations is extremely high, especially when the number of available strategies increases. Moreover, extensive signaling might be necessary to provide all the required information to solve the presented problem. Thus, a distributed and iterative learning solution is more suitable to find the optimal time sharing coefficients.

To resolve any conflicts between users, the Vickrey-Clarke-Groves (VCG) auction mechanism design is employed, which aims to maximize the utility , , defined as

where is the rate of user , and the cost is evaluated as

Hence, for the considered scenario with two users the payment costs for user 1 can be defined as

where and are the covariance matrices corresponding to the strategies and selected by user 1 and user 2, respectively, what is denoted . The payment cost follows by symmetry. Thus, the VCG utilities can be calculated using

where and for the considered cases are defined as in (19), (22), and (24), respectively.

In the investigated TSD-MIMO scenario, no transmit and receive beamforming is applied, and the considered strategies represent the transmit antenna selection mechanism. Hence, the VCG utilities can be calculated as in (19). The first part of both equations presents the achievable rate (payoff) of the th user if no auction theory is applied (no cost is paid by the user for starting playing). On the other hand, last two parts express the price (defined as 18) to be paid by the th user for playing the chosen strategy

Since the precoding vectors in case of TSD-MIMO correspond to the selection of one of the available transmit antennas (or the selection of both with equal power distribution), there are only four strategies are available to users, which correspond to the following covariance matrices:

When selecting the strategy corresponding to user decides to remain silent. On the contrary, and correspond to the situation when user decides to transmit on antenna 1 or antenna 2, respectively. Finally, is the covariance matrix representing the strategy when user transmits on both antennas with equal power distribution.

One may observe that the proposed general mechanism design can be used to investigate the performance of OFDM transmission on the interference channel. This is the case when the channel matrices , are diagonal, so the specific paths represent the orthogonal subcarriers. Similarly to the previous subsection, first parts of the equations present the achievable rate (payoff) of the th user if no auction theory is applied (no cost is paid by the user for starting playing). Next, last two parts defines the price (defined as 18) to be paid by the th user for starting playing the chosen strategy. It is worth mentioning that since the above-mentioned matrix is diagonal one can easily apply the eigenvalue decomposition (or singular value decomposition) to reduce the number of required operations. Hence, for the considered 2-user scenario the cost for user can be evaluated as in (21), and the VCG utilities can be defined as in (22). For the sake of clarity, let us provide the interpretation of selected variables in the equations below for the OFDM case: is the channel coefficient that characterizes the channel on the th subcarriers between the th and the th user and is the th diagonal element from the considered covariance matrix of the th user

Obviously, the idea of correlated equilibrium and of application of the auction theorem, described in the previous subsections, can be applied also for the precoded MIMO case. However, beside the straightforward modification of the equations describing the payment cost (see (23)), and VCG utilities (see (24)) the set of possible strategies has to be interpreted in a different way. However, following the way provided in the previous subsections, one can interpret the equations presented below in more detailed way. Thus, the first part of (24) presents the achievable rate (payoff) of the th user if no auction theory is applied (no cost is paid by the user for starting playing), whereas last two parts express the price (defined as 18) to be paid by the th user for starting playing the chosen strategy

In the previous cases (i.e., TSD-MIMO and OFDM), the selection of one of the predefined strategies means that the BS selects first, second, or both antennas for transmission or is silent. In the SVD-MIMO case, the selection of the covariance matrix by the BS has an interpretation of choosing one of the calculated singular values (obtained as the result of singular value decomposition of the transfer channel matrix). Thus, for example, by choosing the strategy corresponding to means that we choose the first singular value and—in consequence—the transmit and receive precoding vector that correspond to this singular value. Moreover, selection of the third strategy corresponding to has a meaning that no specific precoding has to be applied. Such, situation can occur in a presence of high interference between adjacent cells. It has to be stressed that selection of the first strategy will be preferred since the precoding vectors that correspond to this particular singular value maximize the channel capacity. However, this statement can be no longer valid in a strong interference case. The obtained results show that in such a situation, the proposed algorithm (that will be described later) converges to global optimum when the second or even third strategy is selected.

Different interpretation of the user strategies has to be defined for the ZF/MMSE/ML-MIMO transmission when the codebook of size is used. In such a case, the number of strategies has to be increased from 4 (as in TSD-MIMO case) to , that is, the player (BS) can choose to be silent (one strategy), not to use any specific beamformer (second strategy), or to use one of the predefined and stored in a codebook strategies (remaining strategies).

In [8], the regret-matching learning algorithm is proposed to learn in a distributive fashion how to achieve the correlated equilibrium set in solving the VCG auction. Since in [8] the interference channel with only one transmit and one receive antenna per user is considered, there are only two distinct binary actions and at every time . However, in case of the considered MIMO interference channel with configuration, there are more actions possible. Hence, the regret of user at time for playing action instead of other actions is

where

where is the cardinality of the set of all actions available to user , is the utility at time , and is the vector specifying the other users actions. is the average payoff that user would have obtained if it had played other action than every time in the past. Other definitions of average payoff are possible, for example, finding the maximum value of average payoffs of all strategies other than . The details of the regret-matching learning algorithm are presented in Algorithm 1. According to the theorem presented in [14], if every user plays according to the proposed learning algorithm, then the found probability distribution should converge on the set of correlated equilibrium as .

Initialize arbitrarily probability for user ,

For

( ) Let be the action last chosen by user , and as the other actions

( ) Find the as in(26)

( ) Find the average regret for playing instead of any other action as in(25)

   

( ) Calculate the factor value as:

( ) Find the probability distribution of the actions for the next period, defined as:

 If  for all   ,

,

  

   Find where . Set:

To validate the correctness of the proposed idea, the 2-user MIMO system has been simulated. In Figure 8, the crystallized rate region in the interference limited case has been shown, that is, the case when strong interference between antennas exist. The channel matrices for this case have been set as

that implies that the first user observe strong interferences from the second user only on the second antenna while on the first antenna only the useful signal is received, and vice versa—the second users observes strong interference signal only on the first antenna. Such configuration explicitly leads toward choosing the strategy and by the first and second user, respectively, when the TSD-MIMO is considered. This is shown in Figure 8, where the solid line corresponds to the frontier lines. One can observe that indeed—the learned solution is that the regret matching algorithms converges to the point . In other words, both users shall transmit with the maximum power all the times using the strategies and , respectively.

In this figure, additional frontier lines of the possible rate regions when the users choose one (not optimal) of the possible strategies are presented; that is, the dotted line represents the frontier line when both users choose the strategy all the time. This line corresponds to the interference limited SISO scenario in [8]. The dashed lines show the achievable rate regions boundaries, when one user plays the strategy all the time, while the other transmit the whole power through one antenna.

In Figure 9, the achievable rate region for the noise limited scenario is presented, that is, both users observe the interferences coming from the neighboring cells, but the power of the interferences is significantly smaller than the power of the useful signal. In this figure, all 15 characteristic points have been presented, as well as the achievable rate region boundaries (dotted lines) when both players select one specific strategy and use them all the time. As expected, the learned point, that is, the point at the time-sharing line, that is, indicated by the regret-matching algorithm, corresponds to selecting the strategy by both users all the time.

Moreover, in Figures 10 and 11 the convergence of the rate-matching algorithm in terms of number of iterations in the interference limited TSD-MIMO scenario has been presented. The same channel matrices have been used as in (27). One can notice that the algorithm have found the optimal solution extremely fast. Indeed, after around 10 iterations the learned point fits ideally to the optimum solution and remains unchanged.

Similar conclusions can be drawn for the precoded MIMO case. The rate region obtained for the SVD-MIMO case for a particular channel realization is presented in Figure 12. The interpretation of any point in the SVD rate region is as follows: both base stations use singular value decomposition in order to linearize the channel and the total transmit power is within the range . Channel transfer matrices have been arbitrarily selected as follows:

that means that both users have good channel characteristic within their cells (no significant interference exist between the first transmit and second receive antenna as well as between second transmit and first receive antenna). However, first user causes strong interference on the second receive antenna of the second user, and the second users disturb significantly the signal received by the first user in his first antenna.

Analyzing the presented results one can observe that the obtained rate region is concave thus the time-sharing approach can provide better performance than continuous power control scheme (i.e., when both users transmit all the time and regulate the interference level by the means of the value of transmit power). The potential time-sharing Lines are presented in this figure. For the comparison purposes the line obtained for spatial waterfilling MIMO case has been plotted in Figure 12 (dotted line). The line has been derived in the following way: starting from point (where user 2 does not transmit and user 1 uses the maximum power with the SWF technique) user 2 increases the total transmit power up to the maximum value, when both users transmit with the maximum total power point is reached; finally user 1 decreases the transmit power from the maximum value to zero reaching the point . Moreover, the power control line has been presented—it is the case when both users selects wrong strategy achieving extremely low rates. In is worth mentioning that the learned points obtained for various MIMO techniques have been marked in the described figure. One can observe that for the optimal case (SVD technique) algorithm converges to the point . Slightly worse results have been obtained for TSD-MIMO, where no specific precoding has been performed. The worse results, but still in the vicinity of the point , are for the random beamforming technique when 8 various precoders have been stored in a codebook and maximum likelihood method is used at the receiver.

The same simulation have been carried out for other channel, when significant interference exist between all transmit and all receive antennas between th user and th BS. The channel transfer matrices have been selected as below:

The obtained rate region, potential time-sharing lines, spatial waterfilling line and exemplary power control line, as well as some learned points (for the same MIMO techniques as described in the previous case) have been presented in Figure 13. One can observe that in such a case one of the learned points is close to the optimal one (Point ). However, this point is reached for random beamforming technique with maximum-likelihood method used at the receiver.

Specific rate values obtained for the considered MIMO implementations are given in Tables 1 and 2 for channel definitions (28) and (29), respectively. The results obtained for all RAN-8 scenarios (i.e., ZF, MMSE, and ML and when the codebook size is equal to 8) have been averaged over 1000 randomly generated codebooks. One can observe that for all cases, when the regret-matching algorithm has been applied, the obtained rates are similar to each others and relatively close to the optimal solution. Only for the ZF/MMSE-MIMO cases when the random beamforming approach has been used, the averaged results are significantly worse because of high dependency of algorithms efficiency on the actual set of transmit beamformers. If the randomly generated set of beamformers is well defined (i.e., at least one precoder matches the actual channel conditions for th user); the achieved rate is also close to the optimal point (see the maximum obtained values for one particular channel realization).

The efficiency of the random beamforming technique strongly depends on the number of precoders. However, the higher number of precoders the higher the complexity of the algorithm. Thus, in order to present the relation between the random beamforming technique efficiency and the codebook size the computer simulation have been carried out for the particular channel realization defined as above. The results, presented in Figure 14, have been obtained for 1000 various codebook realizations for each codebook size. One can observe that the obtained rate for both users increase logarithmically as the number of precoders increases.

In order to assess the efficiency of the proposed solution, the achievable sum rates versus the number of antennas have been compared for two cases: when the results have been obtained by application of the proposed regret-matching algorithm and by solving the linear programming problem defined in Section 3.1. Two simulation scenarios have been selected for the 2-user 2-BSs MIMO configuration: TSD-MIMO and SVD-MIMO. The spatial waterfilling MIMO approach has been also considered for the comparison purposes. The Simplex algorithm [13] has been applied to solve the linear programming problem. The results obtained for the strong interference channel (similar to the one defined for MIMO in (27)) are presented in Figure 15. One can observe that in both cases (linear programming and regret matching) the achieved sum rates are identical for both strategies when the number of antennas is higher than 2. Only for MIMO case the proposed distributed solution performs slightly worse in terms of the achieved sum rate. It is particularly worth mentioning that the global optimum is reached in both cases. Similar results have been obtained also for the spatial waterfilling case. Let us stress that the complexity of the Simplex method is known to be polynomial whereas the complexity of the proposed regret-matching algorithm is linear [28]. In other words, the optimal solution is found at lower computation cost.