Abstract: This study presents a Novel Distributed Iterative Interference Alignment (NDIIA) algorithm for three-user M-antenna multiple-input multiple-output interference channels which can approach very close to the Degree of Freedom (DoF) upper bound. NDIIA algorithm achieves the great sum capacity improvement offered by interference alignment. NDIIA algorithm loosens the global channel knowledge assumption in previous research works and NDIIA assumes that only local channel knowledge is available to each receiver. Compared with Gomadam-Jafar algorithm, NDIIA algorithm lets each receiver guide one interfering transmitter to update its interfering signal’s coding vectors instead of updating the desired signal’s coding vectors which perfectly aligns with the other interfering signal’s coding vectors. Based on the reciprocity property of wireless networks, the NDIIA algorithm achieves interference alignment based on the idea of interference regulation. Simulation results suggest that the NDIIA algorithm can achieve perfect interference alignment with high probability and is effective and efficient to approach the DoF upper bound.
INTRODUCTION
General interference channel capacity is a long-term problem to be in suspense in network information theory. In order to gain insights into transmission strategy, many researchers have turned to characterizing the Degree of Freedom (DoF) which is also known as capacity pre-log or multiplexing gain (Zheng and Tse, 2003). Under such considerations, the DoF can be defined as:
| (1) |
where, d is the DoF, Csum is the sum network capacity and r is the Signal to Noise Ratio (SNR). As a result, the capacity can be written as:
| (2) |
where, f(x) = ○(g(x)) denotes:
and the ○(log(ρ)) becomes negligible compared to the d-log(ρ) in the high SNR regime.
Recent works on interference channels suggest that the Gaussian interference channels capacity can only be achieved by coding across transmitters based on the interference alignment viewpoint (Jafar and Shamai, 2008; Maddah-Ali et al., 2008; Perlaza et al., 2008; Zhuang et al., 2011). Interference alignment is usually considered as the novel idea of jointly designing the coding vectors at transmitters, so that the interference each receiver observes overlaps inside half of the observation signal space, leaving the remaining half space interference-free. This shows the cake-cutting view of resource allocation among co-existing wireless systems is sub-optimal and the network capacity can be greatly improved compared to current prevalent orthogonal access technologies (Zhou et al., 2012). Based on observing the trend of the use of Multiple-Input Multiple-Output (MIMO) systems in future wireless networks, NDIIA algorithm for a three-user M-antenna MIMO interference channel is proposed. MIMO systems not only increase the achievable DoF compared to single antenna systems but they are also easier to do interference alignment because the random MIMO fading matrices does not need infinite long symbol extension of the channel to do interference alignment.
According to the survey, the only distributed interference alignment algorithm in previous research works is Gomadam-Jafar algorithm which was proposed in (Gomadam et al., 2008). The Gomadam-Jafar algorithm assumes only local channel knowledge is available to each receiver and updates the coding vectors of desired signal, so that the desired signal is in the signal subspace with least interference. The feasibility of interference alignment was also discussed. Gomadam-Jafar algorithm as shown could not achieve perfect interference alignment while each transmitter is fully loaded with the maximum possible data stream number and the streams can be reliably transmitted to the corresponding receivers. The authors there proposed a metric called ‘weighted leakage interference’ to estimate the performance of proposed algorithm and showed that the leakage interference is not zero in the desired signal space (thus cannot achieve the DoF upper bound).
This study proposes a NDIIA algorithm for three-user M-antenna MIMO interference channels which can approach extremely, close to the DoF upper bound. The main difference between NDIIA algorithm and Gomadam-Jafar algorithm is, instead of updating the desired signal’s coding vectors, NDIIA algorithm lets each receiver guide one interfering transmitter to update its interfering signal’s coding vectors so that they perfectly align with the other interfering signal’s coding vectors. The adopted methodology involves projecting interfering signal’s coding vectors from one signal subspace to another signal subspace. Such a signal subspace method is a direct realization of interference alignment based on the idea of interference regulation and thus has faster convergence speed and performs better than Gomadam-Jafar algorithm.
Simulation results show that the NDIIA algorithm can achieve perfect interference alignment, i.e., zero leakage interference, with high probability and sufficient number of iterations. It is observed that the more complex the channel matrices are (with more antennas on each transmitter/receiver), the more iteration it needs to do interference alignment using the proposed NDIIA algorithm. It is also showed that the penalty on the achievable DoF due to limited number of iterations or delay constraint is negligible compared to the great performance improvement it offers which is a promising result for this technology to be adopted for practical use. Moreover, the proposed NDIIA algorithm will converge much faster if loosening the perfect interference alignment constraint (by allowing 1 DoF loss compared to the DoF upper bound) slightly while still maintaining relatively large DoF improvement compared to orthogonal access technologies.
In order to give a clearer motivation of this work, related researches are summarized by their main contributions which either characterize the DoF for various network models or develop achievable schemes to realize the corresponding DoF improvements.
Degree of freedom: Cadambe and Jafar (2008a), the authors there show that for a fully connected K-user interference channel with time-varying or frequency selective channel coefficients and M antennas at each transmitter/receiver, the total achievable DoF is almost surely KM/2, i.e., each user can get half of the DoF as there is no interference at all. This is a promising result because it tells us prevalent orthogonal access transmission strategies are not optimal, especially in the DoF point of view when the SNR is high. Furthermore, in (Cadambe et al., 2008), an interference alignment example for the deterministic model of a K-user interference channel is proposed, where the channel coefficients have special properties to aid the alignment. While an analogy between the deterministic channel model and the propagation delay example in (Cadambe and Jafar, 2007) is drawn, the DoF of general deterministic Kuser interference channels, where the channel coefficients are randomly drawn from a continuous distribution, still remains an open problem.
Jafar and Fakhereddin (2007), for a two-user MIMO interference channel with M1, M2 antennas at transmitters 1, 2, N1, N2 antennas on the corresponding receivers and global channel knowledge at each transmitter/receiver, the total DoF is min{M1+M2, N1+N2, max(M1, N2), max(M2, N1)}. Moreover, it is also shown as in (Cadambe and Jafar, 2008b) that transmitter cooperation does not provide any benefit in terms of the total achievable DoF, because the gains of transmitter cooperation through constructing a fully cooperative broadcast channel can be entirely offset by the cost of setting up the cooperation. For some wireless network models like fully connected SxRxD network, etc., relays, perfect feedback to source nodes, full duplex operation and noisy cooperation cannot improve the DoF and can only increase the capacity up to ○(log(ρ)) (Cadambe and Jafar, 2008a).
For a more general K-user MxN MIMO interference channel, it is shown in (Gou and Jafar, 2008b) that when:
integer, the total achievable DoF is min(M, N) if K≤R and:
if K>R. As a constructive proof shown in (Gou and Jafar, 2008a), for a four-user single-input multiple-output interference channel where each transmitter has a single antenna and each receiver has two antennas, the total achievable DoF is 8/3 almost surely. Based on the reciprocity alignment property as shown in (Jafar and Fakhereddin, 2007), this result also applies to the four-user multiple input single-output interference channels.
Interference alignment schemes: Jafar and Fakhereddin (2007), Cadambe et al. (2008) and Gou and Jafar (2008b), several closed form solutions for designing the coding vectors to achieve the total DoF upper bound were proposed for various types of interference channels with different antenna configurations and channel matrices forms. These solutions are similar since they all try to align the interference each receiver observes into the same signal subspace and use zero forcing techniques to extract the desired signal in the remaining interference-free signal subspace. The main drawback is that they require global channel knowledge at each transmitter which may generate overwhelming overhead in practice. Another issue is that for a K-user single antenna interference channel, the total DoF upper-bound can only be achieved through infinite long symbol extension of the channel and may suffer performance loss over finite symbol extension of the channel due to delay or complexity constraints, etc. Further, a distributed interference alignment algorithm was proposed in Gomadam et al., 2008 to resolve the impractical global channel knowledge assumption problem. Based on the reciprocity property of wireless networks, an iterative algorithm which updates the desired signal’s coding vectors at each iteration was proposed. Although, this algorithm loosens the global channel knowledge assumption, it is not possible to do perfect interference alignment to achieve the DoF upper bound. In addition, it is more suitable for two-way communications with reciprocal channels and the speed of convergence and feasibility of interference alignment without reciprocal channels are not clear. This study tries to resolve those existing problems for Gomadam-Jafar algorithm. The proposed NDIIA algorithm is able to do perfect interference alignment and achieve the DoF upper bound with high probability and without the reciprocal channels requirement.
SYSTEM MODEL
Throughout this study, lowercase letters are used to denote scalars, uppercase letters to denote vectors and bold uppercase letters to denote matrices.
The three-user M-antenna MIMO interference channel is comprised of three transmitters Ti, i = 1, 2, 3 and three receivers Ri, i = 1, 2, 3 where each transmitter/receiver has M antennas and each Ti has independent messages to be sent to Ri, for i = 1, 2, 3. A fully connected three-user two antenna MIMO interference channel example is shown in Fig. 1, in which the solid lines denote the desired signals and the dashed lines denote the interference signals from the transmitters to the receivers. The input-output relations for such a three-user M-antenna MIMO interference channel is:
| (3) |
where, in the tth time slot, Y[j](t) and Z[j](t) are the Mx1 received signal vector and circularly symmetric additive white Gaussian noise vector with zero mean and unit variance at receiver j. X[i](t) is the Mx1 transmitted signal vector at transmitter i with power constraint E[||X[i](t)||]≤P and H[ij](t) is the MxM channel matrix between transmitter Ti and receiver Rj, where the entries in H[ij](t) are independent and identically distributed (i.i.d.) Rayleigh fading channel coefficients.
| Fig. 1: | MIMO interference channel for the three-user
two-antenna case |
Finally, it can be assumed that only local channel knowledge is available to each receiver, i.e., only H[ij](t), i = 1, 2, 3 is available to receiver Rj.
Jafar and Fakhereddin (2007), it has been shown that for a three-user M-antenna MIMO interference channel, the total DoF is:
i.e., on average, each transmitter has only:
DoF to send its data reliably to the corresponding destination. Thus, the original message should be encoded by:
linearly independent streams as:
| (4) |
Where:
is a:
matrix containing:
orthonormal basis vectors:
and
vector containing:
independent symbols:
for i = 1, 2, 3. Here only one case is considered when M is even while similar input-output relations and precoding at transmitters can be done by using two-symbol extension of the channel when M is odd. Thus, the case is omitted when M is odd for mathematical simplicity. Finally, it is assumed that the existing physical links are all quasi-static flat fading which means the channels gains are constant during each time interval under consideration but change independently between different time intervals and thus omit the time index in all the following expressions.
ITERATIVE INTERFERENCE ALIGNMENT ALGORITHM
In order to achieve the total DoF upper bound, the interference signal must be perfectly aligned at each receiver so that it only occupies half of the signal space and leaves the other half interference-free. Thus, the following conditions must be simultaneously satisfied:
| (5) |
| (6) |
| (7) |
| (8) |
| (9) |
| (10) |
Note that the randomness of MIMO channel matrices ensures that each H[ij], i, j = 1, 2, 3 is full rank with probability 1 which further means conditions Eq. 5, 7, 9 are naturally satisfied almost surely. Since, the only information available to each receiver is its local channel knowledge, the task to design the interference alignment coding vectors is reduced to: at receiver Rj, j = 1, 2, 3, use H[ij] to design V[i], i = 1, 2, 3 in order to satisfy the interference alignment conditions Eq. 6, 8, 10. Moreover, because H[ij], i, j = 1, 2, 3 are invertible almost surely, Eq. 6, 8, 10 can be further writed as:
| (11) |
| (12) |
| (13) |
From linear algebra, it can be known that:
| (14) |
and:
| (15) |
where, [•]+ denotes the generalized inverse operation of a matrix. From Eq. 4, it is known that:
| (16) |
Thus, combining Eq. 11-13 and 14-15, it can be written as:
| (17) |
| (18) |
| (19) |
where, T1 = (H[21])-1H[31], T2 = (H[32])-1H[12] and T3 = (H[13])-1H[23].
Because AA+ is a projection whose range is the subspace which is spanned by the columns of A, from Eq. 17-19, it is known that:
| (20) |
| (21) |
| (22) |
Given Eq. 16 and the fact that Ti, i = 1, 2, 3 are full rank matrices almost surely, it is known that:
| (23) |
Similarly:
| (24) |
| (25) |
Thus, combining Eq. 20-22 and 23-25, it is known that the interference alignment conditions Eq. 6, 8, 10 are equivalent to:
| (26) |
| (27) |
| (28) |
In order words, this is a set of necessary and sufficient conditions to achieve perfect interference alignment.
It is observed that T1, T2 and T3 are based only on local channel knowledge available to receiver R1, R2 and R3 respectively. Thus, in order to satisfy Eq. 26, receiver R1 guiding transmitter T2 updates V[2] by projecting it to the subspace spanned by the columns of T1V[3]. This will ensure condition Eq. 26 to be satisfied which is equivalent to condition Eq. 6 being satisfied. Because it is not expected that the new updated coding vectors V[2] to contradict interference alignment condition Eq. 5, oblique projection is used as:
| (29) |
Where:
| (30) |
| (31) |
| (32) |
and Q*1 is used to denote the matrix conjugated transposition operation of Q1. This oblique projection will project V[2] to the subspace which is spanned by the columns of T1V[3] along the direction which is parallel to the subspace spanned by the columns of (H[21])-1H[11]V[1]. In other words, because the direction of the projection is parallel to the subspace spanned by the columns of the desired signal (H[21])-1H[11]V[1], the resulting interference signal subspace from transmitter T2 is included in the interference signal subspace from transmitter T3 and is disjoint with the desired signal subspace from transmitter T1. Similar operations can be done at the other two receivers, i.e., receiver R2 guides transmitter T3 to update V[3] by projecting it to the subspace spanned by the columns of T3V[1] and receiver R3 guides transmitter T1 to update V[1] by projecting it to the subspace spanned by the columns of T3V[2].
Thus, instead of selfishly maximizing the desired signal dimensionality, this study a cognitive approach and let each receiver guide one interfering transmitter to minimize its interference signal dimensionality. It is proposed that iterative interference alignment algorithm is shown in Algorithm 1.
|
Algorithm 1: |
Iterative interference alignment algorithm |
Proof of convergence: Intuitively, because the projection operation can only reduce the dimensionality of the interference signal subspace, the dimensionality of the desired signal subspace can only be increased in every iteration. Since, there is a total DoF upper bound, the algorithm must converge in finite steps. More formally, the total weighted leakage interference metric is used as in (Gomadam et al., 2008) to show the convergence of the proposed iterative interference alignment algorithm. Due to limited space, the proof is just sketched here.
The total weighted leakage interference at receiver Rj, for j = 1; 2; 3, is defined as:
| (33) |
where, U[j] denotes the receiving filter bank at receiver Rj. From the oblique projection in Eq. 29, it can be easily seen that at receiver R1:
| (34) |
| (35) |
Thus, if choosing the receiving filter bank U[1] as:
| (36) |
it can be immediately ensured that:
| (37) |
and:
| (38) |
Moreover, the randomness of MIMO fading channels together with Eq. 35 tell us:
| (39) |
| (40) |
From Eq. 15, it is also known that:
| (41) |
| (42) |
which means rank:
Thus, if choosing proper receiving filter bank U[1], the total weighted leakage interference at receiver R1 will be zero, i.e., I[1]w = 0 while maintaining the desired signal occupy half of the signal space. Similar conclusions can be drawn for receivers R2 and R3.
Thus, the oblique projection EQj|Sj together with the receiver filter bank U[j] will null the total weighted leakage interference at receiver Rj and the sum of total weighted leakage interference at all receivers will also be monotonically reduced. Since, the sum of total weighted leakage interference at all receivers is lower bounded by 0, the convergence of the proposed algorithm is thus guaranteed.
SIMULATION RESULTS
Here, a numerical evaluation of the proposed iterative interference alignment algorithm is given as well as some useful observations.
It is first noted that Gomadam-Jafar algorithm in Eq. 10 is not able to do perfect interference alignment (measured by non-zero leakage interference) when each transmitter is fully loaded with maximum possible number of data streams that can be reliably transmitted to the corresponding receivers and thus cannot achieve the DoF upper bound. Moreover, the performance will be further degraded if the reciprocal channels condition is not satisfied. The performance of Gomadam-Jafar algorithm is shown as in Fig. 2.
In contrast, the algorithm this study proposed is able to achieve perfect interference alignment (conditions Eq. 5-10 are satisfied) and thus achieve the DoF upper bound, with high probability and without reciprocal channels condition. From Fig. 3 and 4, it is easy to see perfect interference alignment can be achieved with high probability and small number of iterations. As a result, the percentage of leakage interference in the desired signal space will be zero with high probability, as shown in Fig. 2. It is also observed that the proposed algorithm needs more iterations to achieve perfect interference alignment as the channel matrices become more complex (with more antennas at each transmitter/receiver) while perfect interference alignment is extremely difficult to achieve under some particular channel conditions.
| Fig. 2: | Average percentage of leakage interference
in the desired signal space as a function of number of antennas at each
transmitter or receiver |
Although, it is not able to give a theoretical explanation why this will happen, it is shown in Fig. 5 that the penalty on the achievable DoF due to limited number of iterations is negligible compared to the great performance improvement and it can be approached very close to the achievable DoF upper bound.
It is observed that if slightly loosening the perfect interference alignment constraint (by allowing 1 DoF loss compared to the achievable DoF upper bound), interference alignment is much easier to achieve to further reduce the number of iterations and achieve faster convergence. As shown in Fig. 6-8 near-perfect interference alignment is very easy to achieve almost surely with relatively small number of iterations compared to perfect interference alignment.
| Fig. 3: | Probability of successful perfect interference alignment |
| Fig. 4: | Average No. of iterations for perfect
interference alignment |
| Fig. 5: | Average achievable degree of freedom
for perfect interference alignment |
| Fig. 6: | Probability of successful near-perfect interference alignment |
| Fig. 7: | Average No. of iterations for near-perfect interference alignment |
| Fig. 8: | Average achievable degree of freedom
for near-perfect interference alignment |
Although, the sum capacity improvement is not as significant as perfect interference alignment, it may be more desirable for practical applications like sensors networks with limited battery life and processing ability, etc.
DISCUSSION AND CONCLUSION
In this study, a NDIIA algorithm for three-user M-antenna MIMO interference channels has been proposed. The NDIIA algorithm uses only the local channel knowledge at each receiver and takes a cognitive approach to guide one interfering transmitter to minimize the interference signal dimensionality instead of selfishly maximizing the desired signal dimensionality. Compared to Gomadam-Jafar algorithm, the NDIIA algorithm is able to achieve perfect interference alignment when each transmitter is fully loaded with maximum possible number of data streams that can be reliably transmitted to the corresponding receivers. Simulation results show that the proposed algorithm is effective and efficient to approach the total degree of freedom upper bound and more importantly, offers great improvement compared to orthogonal access transmission strategies. Although, the proposed iterative interference alignment algorithm has great performance improvement for three-user M-antenna MIMO interference channels, it is not a direct extension for interference channels with more than three users. This is because the NDIIA algorithm is based on the idea of interference regulation and there is more interference needed to be regulated for cases with more than three users. A circular interference regulation rule may help to achieve perfect interference alignment and the investigation will be presented in the future research work.
1Foundation items: The National Natural Science Foundation of China (No.61001092); Shenzhen Municipal Science and Technology Planning Program for Basic Research (No. JCY201110022); Natural Scientific Research Innovation Foundation in Harbin Institute of Technology (No.HIT.NSRIF.2011078)