Advanced
A Rapid Convergent Max-SINR Algorithm for Interference Alignment Based on Principle Direction Search
A Rapid Convergent Max-SINR Algorithm for Interference Alignment Based on Principle Direction Search
KSII Transactions on Internet and Information Systems (TIIS). 2015. May, 9(5): 1768-1789
Copyright © 2015, Korean Society For Internet Information
  • Received : August 01, 2014
  • Accepted : April 20, 2015
  • Published : May 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Zhilu Wu
School of Electronics and Information Engineering, Harbin Institute of Technology Harbin, Heilongjiang 150001- P.R.China
Lihui Jiang
School of Electronics and Information Engineering, Harbin Institute of Technology Harbin, Heilongjiang 150001- P.R.China
Guanghui Ren
School of Electronics and Information Engineering, Harbin Institute of Technology Harbin, Heilongjiang 150001- P.R.China
Gangyi Wang
School of Instrumentation Science and Opto-electronics Engineering, Beihang University Beijing 100191 - P.R.China
Nan Zhao
School of Information and Communication Engineering, Dalian University of Technology Dalian, Liaoning 116024 - P.R.China
Yaqin Zhao
School of Electronics and Information Engineering, Harbin Institute of Technology Harbin, Heilongjiang 150001- P.R.China

Abstract
The maximal signal-to-interference-plus-noise ratio (Max-SINR) algorithm for interference alignment (IA) has received considerable attention for its high sum rate achievement in the multiple-input multiple-output (MIMO) interference channel. However, its complexity may increase dramatically when the number of users approaches the IA feasibility bound, and the number of iterations and computational time may become unacceptable. In this paper, we study the properties of the Max-SINR algorithm thoroughly by presenting theoretical insight into the algorithm and by providing the potential of reducing the overall computational cost. Furthermore, a novel IA algorithm based on the principle direction search is proposed, which can converge more rapidly than the conventional Max-SINR method. In the proposed algorithm, it searches along the principle direction, which is found to approximately point to the convergence values, and can approach the convergence solutions rapidly. In addition, the closed-form solution of the optimal step size can be formulated in the sense of minimal interference leakage. Simulation results demonstrate that the proposed algorithm outperforms the conventional minimal interference leakage and Max-SINR algorithms in terms of the convergence rate while guaranteeing the high throughput of IA networks.
Keywords
1. Introduction
I n current multiuser wireless networks where some resources such as frequency, time, and space are usually shared among different users, interference appears and becomes the bottleneck of the throughput of the system. Many scholars have focused on interference management techniques to eliminate the interference [1] and to maximize the sum rate [2] , and interference alignment (IA) is a novel scheme that can mitigate the interference and thus increase the total throughput significantly [3] . Cadambe and Jafar showed that the degrees of freedom (DoFs) of the multiple-input multiple-output (MIMO) communication system scale proportionally to the number of users by employing IA in the high signal-to-noise ratio (SNR) regime in [4] . The essential idea of IA is to separate the desired signal and interference into different signal subspaces by using the proper precoding matrices and to reconstruct the former as well as to suppress the latter by using the proper decoding matrices [5] . Due to its promising performance in eliminating the interference and increasing the sum rate, IA has become an intensive research topic in recent years [6 - 8] .
The feasibility condition for the K -user IA system of M transmitting antennas, N receiving antennas, and d DoFs was provided by Yetis et al . in [9] as K ≤( M + N )/ d -1. However, the closed-form solutions to IA can be obtained only in some very special situations [10] , and finding the optimal IA solutions still remains an open problem. Schmidt et al . analyzed these challenges in [11] and noted that the number of IA solutions increases dramatically with the number of users and antennas. In addition, the sum rate that different IA solutions can achieve varies considerably, and a brutal search is obviously infeasible due to the large computational cost. Furthermore, this problem was proved to be non-convex and NP-hard in [12] . Therefore, many scholars have developed different strategies to determine the sub-optimal IA solutions. Gomadam et al . developed the minimizing interference leakage (MinIL) algorithm in [13] to seek perfect IA points, and its convergence was proved. However, the MinIL algorithm does not consider the direct channel and might suffer from the loss of the desired signal power. Therefore, a maximal signal-to-interference-plus-noise ratio (Max-SINR) algorithm was proposed in [14] , which aims at maximizing the SINR of each data stream by designing proper precoding and decoding matrices. The minimum mean square error (MMSE) criterion was introduced in [15] and [16] to optimize the sum rate in the broadcast and interference channels, respectively. Shrestha et al . developed the maximal signal-to-leakage-and-noise ratio (Max-SLNR) algorithm in [17] , which has the advantages of best sum capacity in low and moderate SNR regimes, stable performance with respective to antenna order, and not requiring channel reciprocity. The gradient descent method was leveraged in [18] to maximize the sum rate. An excellent survey on the current IA techniques was conducted by Schmidt et al . in [11] , where the objectives, convergence performance, and sum rate of different beamforming strategies are compared in great detail.
Among the current IA algorithms, the Max-SINR method can achieve a high sum rate and has received considerable attention [11 , 19] . As noted in [11] , the Max-SINR algorithm can achieve the maximum DoFs and can converge faster than many other algorithms such as MMSE. In addition, the throughput that the Max-SINR algorithm achieves is considerably higher than that of the MinIL algorithm in the low and medium SNR regimes. However, the iterations and computational time required by the Max-SINR algorithm might increase dramatically when the number of users K is close to the IA feasibility bound ( M + N )/ d -1, especially in the situations of larger M , N , and K . In practical systems, the precoding and decoding matrices should be obtained before the channel state information (CSI) changes, and longer calculating times might cause a misalignment and loss of sum rate when the outdated precoding and decoding matrices are applied.
In this paper, we focus on developing the low-complexity Max-SINR algorithm with rapid convergence. The main contributions of this paper are summarized as follows: 1. The behavior of the Max-SINR algorithm in the neighborhood of the convergence solution is analyzed thoroughly, and it is found that the relationship of the consecutive iteration deviations can be approximately expressed by linear transformations. 2. The principle direction of the transformations is introduced, which can approximately point to the convergence solution. 3. A novel principle direction search (PDS) algorithm is proposed, which can increase the convergence rate and reduce the overall computational cost significantly.
The remaining parts of the paper are organized as follows. In Section 2, the system model is presented. The properties of the traditional Max-SINR algorithm are investigated in Section 3. The proposed PDS algorithm is developed in Section 4. In Section 5, simulation results are provided, followed by the conclusions in Section 6.
Notation: Re{ A }, Im{ A }, A T , A * , A H , Tr[ A ], || A ||, and A (l) represent the real part, imaginary part, transpose, conjugate, conjugate transpose, trace, Frobenius norm, and the l th column of matrix A , respectively.
PPT Slide
Lager Image
denotes the value of matrix A k at the j th iteration. Particularly,
PPT Slide
Lager Image
is the l th column of matrix A k obtained at the j th iteration, and
PPT Slide
Lager Image
is the conjugate transpose of A k(l) . We use ℝ and ℂ to represent the sets of real and complex numbers, respectively. I , ℂ M×N , and ℂℕ( μ , Δ ) denote the identity matrix, M × N complex matrix, and complex Gaussian vector with mean μ and covariance matrix Δ , respectively. The notation ( M × N , d ) K is employed to represent an MIMO interference channel with K users, M transmitting antennas, N receiving antennas, and d data streams.
2. System Model
In this paper, we mainly concentrate on the ( M × N , d ) K channels. For the k th user, the transmitted symbol vector s k ∈ℂ d×1 is first precoded by the transmitting beamforming matrix P k ∈ℂ M×d , and the transmitted signal vector x k ∈ℂ M×1 can be obtained as:
PPT Slide
Lager Image
The transmitted signal vectors of all users will be sent to the receivers, and the received signal vector of the k th user y k ∈ℂ N×1 can be expressed as:
PPT Slide
Lager Image
where z k ∈ℂ N×1 represents the received noise vector with z k ~ℂℕ( 0 , σ 2 I ) and H kj N×M denotes the channel coefficient matrix from transmitter j to receiver k . In this paper, perfect CSI is assumed to be known by each user, and the reader can refer to [20] and [21] for more information on CSI. The receiver k employs the decoding matrix D k ∈ℂ N×d to extract the desired symbol vector and to suppress the interference from other users. The final reconstructed symbol vector of the k th user can be attained as:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
are the desired symbol vector, residual interference, and noise, respectively.
The interference in the network can be eliminated completely if the precoding and decoding matrices satisfy the following conditions:
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
However, when perfect IA cannot be achieved, interference leakage appears, and it can be given by:
PPT Slide
Lager Image
In addition, the desired signal and the interference-plus-noise covariance matrices of the l th data stream of receiver k are defined, respectively, as [14] :
PPT Slide
Lager Image
PPT Slide
Lager Image
Thus the SINR of the l th data stream of receiver k can be calculated as:
PPT Slide
Lager Image
According to the Max-SINR algorithm [14] , the decoding vector that maximizes (10) can be given by:
PPT Slide
Lager Image
Using the channel reciprocity, the channel coefficients matrices, precoding matrices, and decoding matrices in the reciprocal channel are defined, respectively, as:
PPT Slide
Lager Image
Similarly, the desired signal and the interference-plus-noise covariance matrices in the reciprocal channel, i.e. ,
PPT Slide
Lager Image
, can be attained accordingly.
In this paper, we focus on increasing the convergence rate and reducing the computational complexity of the conventional Max-SINR algorithm in the high SNR regime. The properties of the Max-SINR algorithm are studied, and a rapid convergent IA algorithm is proposed.
3. Properties of the Traditional Max-SINR Algorithm
The Max-SINR algorithm is a promising method to approach the channel capacity, and the sum rate it achieves outperforms many other algorithms. In the low to medium SNR regimes where the sum rate is dominated by noise instead of interference, the Max-SINR algorithm can achieve a significantly higher sum rate than many other algorithms. However, in the high SNR regime, the throughput will be determined by interference rather than noise, and the Max-SINR algorithm has to align the interference properly with considerably more iterations and computational time. The large computational cost and long iteration time might constitute a major impediment to its application in practical systems. Therefore, the properties of the Max-SINR algorithm in the high SNR regime will be studied in this section to provide the theoretical foundation of the later proposed rapid convergent algorithm.
- 3.1 The mechanism of the Max-SINR Algorithm
The Max-SINR algorithm, as shown in Algorithm 1 , leverages the channel reciprocity and maximizes the SINR of each data stream alternatively. It is mainly composed of two procedures, i.e. , the forward and backward iterations. The most important point of the algorithm lies in the design of the precoding and decoding matrices. Gomadam et al . [14] did not provide the matrices design mechanism, and we present Theorem 1 to explain that the maximal SINR problem is essentially the optimization of the generalized Rayleigh quotient of matrices A kl and B kl .
PPT Slide
Lager Image
Theorem 1: The unit-norm vector D k(l) in (11) is the generalized eigenvector associated with the maximal generalized eigenvalue of matrices A kl and B kl . In particular, SINRkl in (10) is the maximal generalized eigenvalue. Similarly, this theorem holds for the reciprocal channel.
Proof: From (8) and (11), we have
PPT Slide
Lager Image
Define
PPT Slide
Lager Image
and (17) can be rewritten as:
PPT Slide
Lager Image
Substitute (11) into (19), and the following equation can be satisfied:
PPT Slide
Lager Image
Therefore, θkl is the generalized eigenvalue of matrices A kl and B kl with the corresponding generalized eigenvector of D k(l) . Particularly, θkl is the generalized Rayleigh quotient and equates to SINRkl .
Left-multiply both sides of (20) by
PPT Slide
Lager Image
, and the generalized eigenvalue problem can be equivalent to the ordinary eigenvalue problem, i.e. ,
PPT Slide
Lager Image
Thus, θkl and D k(l) are the eigenvalue and the associated eigenvector of matrix
PPT Slide
Lager Image
, respectively. As H kk P k(l) ∈ℂ N×1 , we have rank( H kk P k(l) )=rank( H kk P k(l) ) H =1. Then,
PPT Slide
Lager Image
Therefore, rank( A kl ) = 1 . Because rank(
PPT Slide
Lager Image
) = rank( A kl ) = 1 ,
PPT Slide
Lager Image
has only one nonzero eigenvalue. Equivalently, there is only one nonzero generalized eigenvalue of matrices A kl and B kl . As θkl equates to SINRkl , it can be shown that θkl >0. Therefore, θkl is the only nonzero generalized eigenvalue of A kl and B kl . Obviously, θkl is the maximal Rayleigh quotient and the maximal SINR. Similarly, the proof above can be extended to the reciprocal channel to show that P k(l) serves as the generalized eigenvector associated with the maximal generalized eigenvalue of matrices
PPT Slide
Lager Image
.
Theorem 1 provides a way for us to change the SINR optimization into a generalized eigenvalue problem, and some interesting properties can also be explored based on this theorem.
- 3.2 The Principle Direction of the Max-SINR Algorithm
In this section, we will develop the principle direction of the Max-SINR method, which will serve as the foundation of the latter proposed rapid convergent algorithm. Based on Theorem 1, we continue to develop Theorem 2 to show that the relationship for the consecutive iteration deviations of the Max-SINR algorithm can be approximately expressed by iteration-independent linear transformations. Properties of the transformations are later studied in Theorem 3 and Property 4. From these theorems, the principle direction of the transformations is then introduced in Theorem 5, and its mechanism for increasing the convergence rate is verified. Finally, because the principle direction cannot be attained directly, a convenient method to approximate the principle direction is developed in Theorem 6.
Before introducing Theorem 2, the following notations have to be defined beforehand. Define the convergence values of
PPT Slide
Lager Image
, respectively. The deviations from the i th iteration to the convergence value, i.e. ,
PPT Slide
Lager Image
, satisfy
PPT Slide
Lager Image
PPT Slide
Lager Image
Next, several column vectors are constructed to represent the overall precoding and decoding vectors as follows:
PPT Slide
Lager Image
In addition, we can separate the real and imaginary parts of the vectors above to construct the associated real vectors, i.e. ,
PPT Slide
Lager Image
PPT Slide
Lager Image
It is obvious that the following relations can be satisfied:
PPT Slide
Lager Image
PPT Slide
Lager Image
The change in the overall deviations
PPT Slide
Lager Image
is studied, and the following theorem can be given:
Theorem 2: In the high SNR regime, if the Max-SINR algorithm can converge to a near IA point, there exists iteration-independent transformations T P ∈ℝ 2MKd×2MKd and T D ∈ℝ 2NKd×2NKd , respectively, that exert on the deviation vectors
PPT Slide
Lager Image
. When
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are located within the small neighborhoods of
PPT Slide
Lager Image
and
PPT Slide
Lager Image
, respectively, the following approximation can be obtained:
PPT Slide
Lager Image
PPT Slide
Lager Image
Proof: See Appendix A.
It is obvious that T D and T P determine the behavior of the Max-SINR algorithm in the neighborhoods around the convergence solutions. Therefore, a thorough analysis on the transformations will be executed in Theorem 3 and Property 4 to provide theoretical insight into the algorithm and to explore the potential of increasing the convergence rate of the Max-SINR algorithm.
Theorem 3: The transformations T D and T P of the Max-SINR algorithm have the same eigenvalues.
Proof: For matrices E ∈ℂ m×n and F ∈ℂ n×m , EF has the same eigenvalues as FE [22] . Therefore, T D = T PD T DP and T P = T DP T PD have the same eigenvalues.
In the ( M × M , d ) K case, define the eigenvalues of T D and T P as { λ 1 , λ 2 ,…, λ 2MKd } and the associated eigenvectors as { e 1 , e 2 ,…, e 2MKd } and { f 1 , f 2 ,…, f 2MKd }, respectively. For the high complexity of T D and T P , their properties are mainly studied by simulations, and one important feature can be observed as follows:
Property 4: In the ( M × M , d ) K channel, the eigenvalues and eigenvectors of T D and T P are real and satisfy:
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
In particular, the last several eigenvalues tend to be zeros.
Here, we refer to the eigenvectors associated with the maximal eigenvalue, i.e. , e 1 and f 1 , as the principle directions. When T D and T P are successively exerted on
PPT Slide
Lager Image
and
PPT Slide
Lager Image
, respectively, the following theorem can be obtained.
Theorem 5: For the ( M × M , d ) K channel in the high SNR regimes, if the Max-SINR algorithm can converge to a near IA point, when
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are located within a small region of
PPT Slide
Lager Image
and
PPT Slide
Lager Image
, they will converge approximately along the principle directions of T D and T P , respectively.
Proof: From Property 4, { e 1 , e 2 ,…, e 2MKd } and { f 1 , f 2 ,…, f 2MKd } can serve as the bases of the 2 MKd real space. Therefore,
PPT Slide
Lager Image
and
PPT Slide
Lager Image
can be expanded as:
PPT Slide
Lager Image
PPT Slide
Lager Image
At the ( i + j )th iteration, from (30), (31), (35), and (36),
PPT Slide
Lager Image
and
PPT Slide
Lager Image
can be given by:
PPT Slide
Lager Image
PPT Slide
Lager Image
From (32), when j is sufficiently large, λ 1 will take the dominant position, i.e. ,
PPT Slide
Lager Image
Then,
PPT Slide
Lager Image
and
PPT Slide
Lager Image
can be approximated by the principle directions as follows:
PPT Slide
Lager Image
PPT Slide
Lager Image
From (28), (29), (40), and (41),
PPT Slide
Lager Image
and
PPT Slide
Lager Image
can be written as:
PPT Slide
Lager Image
PPT Slide
Lager Image
Thus,
PPT Slide
Lager Image
and
PPT Slide
Lager Image
will converge to
PPT Slide
Lager Image
and
PPT Slide
Lager Image
approximately along the principle directions of e 1 and f 1 , respectively.
If the principle directions can be obtained, we can search along these directions and go to the destination directly. However, the principle directions require knowledge of the convergence values, which is impossible to attain beforehand. Nevertheless, the following theorem provides a way for us to approximate the principle directions.
Theorem 6: In the high SNR regime, if the Max-SINR algorithm can converge to a near IA point, when
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are located within a small region of
PPT Slide
Lager Image
and
PPT Slide
Lager Image
, respectively, the principle directions can be approximated by the difference in the consecutive iteration results of the Max-SINR algorithm. In particular, the convergence solutions can be approximated as:
PPT Slide
Lager Image
PPT Slide
Lager Image
Proof: At the ( i + j +1)th iteration, from (42) and (43), the decoding and precoding vectors can be expressed as:
PPT Slide
Lager Image
PPT Slide
Lager Image
Subtract (46) by (42) and (47) by (43), and we have
PPT Slide
Lager Image
PPT Slide
Lager Image
Therefore, the principle directions can be approximated by the difference in the consecutive iterations results. Substitute (48) and (49) into (46) and (47), respectively, and the convergence solutions can be approximated as:
PPT Slide
Lager Image
PPT Slide
Lager Image
Replace i + j +1 with i and - λ 1 /( λ 1 -1) with s . Then, (50) and (51) can be expressed as:
PPT Slide
Lager Image
PPT Slide
Lager Image
Substitute (25) through (27) into (52) and (53), then (44) and (45) can be formulated.
Theorem 6 provides a direct way to approach the convergence solutions. It is expected that the iterations and computational time can be reduced by searching along the principle directions instead of the circuitous route of the Max-SINR algorithm. Based on the analysis in this section, the rapid convergent maximal SINR algorithm is straightforward.
4. The Principle Direction Search Algorithm
The original Max-SINR algorithm has satisfactory performance of a high sum rate. However, in the high SNR regime where the throughput is mainly limited by interference instead of noise, the Max-SINR algorithm will have to align the interference properly at the expense of a large amount of iterations and computational time. Particularly, the complexity will become significantly larger when the number of users is close to the IA feasibility bound ( M + N )/ d -1. Moreover, the complexity of the Max-SINR algorithm will increase with the number of users and antennas. These disadvantages might serve as a bottleneck for the application of the Max-SINR algorithm. In this section, a highly efficient maximal SINR algorithm, namely, a principle direction search algorithm, is proposed based on the theoretical analysis in Section 3 with the advantage of considerably less complexity than the traditional Max-SINR algorithm.
- 4.1 The Procedure of the PDS Algorithm
The procedure of the PDS algorithm is stated in Algorithm 2 . As shown in Theorem 5, the principle direction search can be employed to increase the convergence rate of the Max-SINR algorithm when the current iteration results are located within a small neighborhood of the convergence solutions. In the proposed algorithm, PDS will be started after the intermediate sum rate is higher than the product of the parameter η and the initial sum rate R 1 . The principle directions are attained by the difference in the intermediate results as shown in (44) and (45). In addition, PDS will be executed every ω iterations because some iterations have to be performed so that (39) can be satisfied and the principle direction will point to the convergence solution more accurately.
PPT Slide
Lager Image
- 4.2 The Step Size Calculation
The step size calculation is one of the crucial procedures in the PDS algorithm and plays an important role in increasing the convergence rate. It is desirable that the optimal step size in the sense of maximal SINR or sum rate could be provided analytically. However, the closed-form solution of the optimal step size under this criterion remains unknown. Nevertheless, in the high SNR regime, the sum rate is mainly limited by the interference, and minimal interference leakage can be employed as the optimization objective. In addition, the optimal step size along the principle direction under the minimal interference leakage criterion can be formulated analytically. Therefore, instead of maximizing the sum rate, we minimize the interference leakage by choosing the proper step size.
As shown in (7), (54), (55), (56), and (57), when
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are applied, the interference leakage can be calculated as:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
It is obvious that β 4 >0, and the quartic function (58) must have the global minimal value. Let the derivatives of (58) be zero, i.e. ,
PPT Slide
Lager Image
The cubic equation (68) has three real solutions at most, and the optimal step size is chosen as the real solution that has the smallest function value.
5. Simulation Results
In this section, we evaluate the performances of the proposed PDS algorithm. We assume narrowband frequency non-selective fading channels. Except for the performance evaluation in Fig. 2 , all of the other experiments are averaged over 250 channel realizations. Each element of the channel coefficients is independent and complies with the ℂℕ(0,1) distribution. The parameters of the PDS algorithm are first analyzed and selected through simulations in section 5.1. Then, a comparison of the PDS, MinIL, and Max-SINR algorithms is executed in section 5.2.
- 5.1 Parameter Analysis
As shown in Algorithm 2 , the parameters η and ω can affect the convergence rate of the PDS algorithm. The closed-form solutions of the optimal parameters remain unknown, and simulations are employed to determine them in Fig. 1 .
PPT Slide
Lager Image
Convergence of the average sum rate of the PDS algorithm in (5×5, 1)9 under different parameters with SNR=30 dB
The parameter η determines when the PDS procedure starts. As shown in Theorem 5, the principle direction will approximately point to the convergence solution only when the intermediate iteration results are within a small region of the convergence point. Because the convergence solution is not available beforehand, it is impossible to measure the distance between the intermediate and the convergence points directly. Nevertheless, the sum rate can be leveraged as one type of measure of the distance because it increases as the algorithm approaches the destination. Therefore, we start PDS when the current sum rate is larger than the product of η and R 1 . In this experiment, η is selected as 1, 1.5, 2, 2.5, and 3, and ω is preset to be 10. The convergence of the average sum rate with SNR=30 dB in (5×5, 1) 9 is depicted in Fig. 1 (a). As shown in the figure, the convergence curves with different η nearly overlap, indicating that the algorithm is insensitive to this parameter. In the simulations afterward, the parameter is chosen as η =1.5.
The parameter ω controls the interval for executing PDS. As shown in (39), (40), and (41), the maximal eigenvalue and the principle direction will take the dominating position only after several iterations are executed. Therefore, PDS is performed every ω iterations. In this experiment, ω is selected as 1, 5, 10, and 20, and η is preset to be 1.5. The convergence of the average sum rate with SNR=30 dB in (5×5, 1) 9 is depicted in Fig. 1 (b). As shown in the figure, ω =1 has the worst performance because the non-principle eigenvectors in (37) and (38) cannot be ignored and the principle direction cannot point to the convergence solution properly when only one iteration is performed. On the other hand, if ω is set to be too large, as in the ω =20 case, the PDS algorithm will fail to increase the convergence rate in time, and the performance of ω =20 is inferior to the performances of ω =5 and ω =10. Because ω =5 has the best convergence rate, it will be chosen as the selected interval afterward.
- 5.2 Comparison of Different Algorithms
In this section, the PDS, MinIL, and Max-SINR algorithms are compared. To gain an overview on the efficiency of the PDS algorithm, the convergence curves of the interference leakage and the sum rate during the first several iterations are provided in Fig. 2 for a randomly generated channel realization. In contrast to the smooth and slow variance on the interference leakage and the sum rate of the MinIL and Max-SINR algorithms, there is an instant decrease in interference leakage and an instant increase in sum rate after PDS is applied. Therefore, the PDS algorithm can suppress the interference leakage and increase the sum rate more effectively compared with the MinIL and Max-SINR algorithms.
PPT Slide
Lager Image
Convergence of the interference leakage and sum rate of the PDS, MinIL, and Max-SINR algorithms for a randomly generated channel realization in (10×10, 1)19 with SNR=30 dB
To further compare the convergence rate of the algorithms, the average interference leakage and the sum rate with respect to the computational time for (5×5, 1) 9 are depicted in Fig. 3 . As shown in the figures, the average interference leakage of the MinIL and Max-SINR algorithms decreases in the same pattern during the first several seconds and reaches the level of 3×10 -3 at 2 s. In contrast, the PDS algorithm has a higher convergence rate and can suppress the interference leakage to the level of 2×10 -4 at 2 s. Both the PDS and Max-SINR algorithms converge at the same level of interference leakage, while the former algorithm takes only 3 s compared with the 20 s required by the latter algorithm. Although the MinIL algorithm can achieve a lower level of interference leakage after 8.5 s, its sum rate is considerably inferior to those of the PDS and Max-SINR algorithms. The average sum rate of the PDS algorithm converges at approximately 2 s with a convergence value of 104 bps/Hz, while the Max-SINR algorithm takes as long as 9 s to reach the same sum rate.
PPT Slide
Lager Image
Convergence of the average interference leakage and sum rate of the PDS, MinIL, and Max-SINR algorithms in (5×5, 1)9 with SNR=30 dB
The proposed algorithm can be applied not only to the single data stream channel but also to the multi-data stream scenarios. The convergence of the average sum rate of the algorithms is compared in the (10×10, 2) 9 and (10×10, 4) 4 channels in Fig. 4 . As shown in Fig. 4 (a), the Max-SINR algorithm requires as much as 19.5 s to reach the sum rate of 190 bps/Hz, while the PDS algorithm only takes 6.5 s to reach the same sum rate. For the scenario of even more data streams as shown in Fig. 4 (b), the PDS algorithm can achieve the highest sum rate and exhibit considerably faster convergence rate than the Max-SINR algorithm.
PPT Slide
Lager Image
Convergence of the average sum rate of the PDS, MinIL, and Max-SINR algorithms in (10×10, 2)9 and (10×10, 4)4 with SNR=30 dB
Although we are mainly concerned with the high SNR regime, it is desirable to evaluate the sum rate in terms of different SNRs. As shown in Fig. 5 (a), the average sum rates of the PDS, MinIL, and Max-SINR algorithms with respect to SNR are compared under sufficient iterations of 10,000. It can be seen that both the PDS and Max-SINR algorithms can achieve the same sum rate, which is higher than those of the MinIL algorithm from the low to high SNR regimes. However, these sufficient iterations are nearly impossible for practical applications, and limited iterations are often required. As revealed in Fig. 5 (b), under 100 iterations, both the PDS and Max-SINR algorithms can achieve a higher sum rate than the MinIL algorithm for all SNRs. In the low SNR regime, the PDS and Max-SINR algorithms share the same sum rate. However, the former algorithm can achieve a higher sum rate in the high SNR regime. In addition, the difference in the sum rate between the PDS and Max-SINR algorithms increases with an increase in SNR, from a difference of 2 bps/Hz at SNR=20 dB to 23 bps/Hz at SNR=40 dB. When the number of iterations allowed is even smaller as shown in Fig. 5 (c), the advantage of the PDS algorithm over the MinIL and Max-SINR algorithms is even more significant. Therefore, the proposed PDS algorithm has practical significance in that it can achieve a higher sum rate than the Max-SINR algorithm under limited iterations.
PPT Slide
Lager Image
Average sum rate versus SNR under iterations of 10,000, 100, and 20 for (5×5, 1)9
To further evaluate the performances of the algorithms, the average iterations and computational time under different numbers of users, data streams, and antennas are listed in Table 1 . We consider the ( M × M , d ) K channel with K =2 M / d -1, the maximal user number in the IA networks [9] . All three algorithms are run with sufficient iterations of 10,000, and the final sum rate R can be obtained. Then, we calculate the iterations that are required to reach the sum rate of 0.9 R and 0.99 R as I 0.9 and I 0.99 , respectively. By averaging I 0.9 , I 0.99 , and R over 250 realizations of channel coefficients, we attain I AV0.9 , I AV0.99 , and R AV for each algorithm. Similarly, we can attain T AV0.9 and T AV0.99 for the computational time. In addition, the ratios of the average iteration and computational time between PDS and Max-SINR algorithms are provided in parentheses under the corresponding values of the PDS algorithm in Table 1 . For the single data stream situation, the PDS and Max-SINR algorithms can achieve the same sum rate, which is comparably higher than those of the MinIL algorithm. From the perspective of average iterations, the PDS algorithm can reach the sum rate of 0.9 R AV and 0.99 R AV with only 29~30% and 25~33% of the iterations required by the Max-SINR algorithm. Furthermore, in terms of computational time, the PDS algorithm can reach the sum rate of 0.9 R AV and 0.99 R AV with only 51~55% and 44~61% of the time required by the Max-SINR algorithm. For the multi-data stream situation, the PDS algorithm can achieve a higher sum rate than the Max-SINR algorithm with lower computational complexity and more rapid convergence.
Statistics on the average iterations, computational time, and sum rate of different algorithms for (M×M,d)Kwith SNR=30 dB
PPT Slide
Lager Image
Statistics on the average iterations, computational time, and sum rate of different algorithms for (M×M, d)K with SNR=30 dB
6. Conclusions
In this paper, we have focused on reducing the execution time and computational complexity of the traditional Max-SINR algorithm for IA. The properties of the Max-SINR method have been investigated, and the principle direction has been introduced, which is found to approximately point to the convergence solutions. A rapid convergent low-complexity PDS algorithm has been proposed that approaches the convergence point directly along the principle direction. Furthermore, the analytical form of the optimal step size along this direction has been formulated under the minimal interference leakage criterion. Numerical results have verified that the proposed PDS algorithm can achieve a significantly higher convergence rate and lower overall computational complexity than the conventional MinIL and Max-SINR algorithms while maintaining the high sum rate. This paper has developed a rapid convergent algorithm and provided theoretical insight into the Max-SINR algorithm.
Acknowledgements
We thank the editors and reviewers for their detailed reviews and constructive comments, which have helped to improve the quality of this paper.
BIO
Zhilu Wu is a professor in the School of Electronics and Information Engineering and the dean of the Information Engineering Department at Harbin Institute of Technology (HIT), Harbin, China. He received the B.S. degree in electronic instrument and measurement technology in 1983, M.E. degree in signal and information processing in 1989, and Ph.D. in information and communication engineer in 2008, respectively, from HIT. His research interests include wireless communication, interference alignment, and software radio.
Lihui Jiang received the B.S. degree in science and technology of optical information in 2009 from South China University of Technology, Guangzhou, China. He received the M.E. degree in signal and information processing in 2011 from HIT. He is currently working toward the Ph.D. degree in information and communication at HIT. His research interests include wireless communication, interference alignment, continuous phase modulation, and machine learning.
Guanghui Ren is a professor in the School of Electronics and Information Engineering at HIT. He received the B.S. degree in electronic instrument and measurement technology in 1984 and M.E. degree in signal and information processing in 2003 from HIT. His research interests include wireless communication, interference alignment, image processing, automatic test systems, and parallel computing.
Gangyi Wang is currently a lecturer in the School of Instrumentation Science and Opto-electronics Engineering at Beihang University, Beijing, China. He received the B.S. degree in electronics and information engineering in 2006, the M.E. degree, and Ph.D. degree in information and communication engineering in 2008 and 2013, respectively, from HIT. His research interests include computer vision, interference alignment, and embedded systems.
Nan Zhao is currently an associate professor in the School of Information and Communication Engineering at Dalian University of Technology, Liaoning, China. He received the B.S. degree in electronics and information engineering in 2005, the M.E. degree in signal and information processing in 2007, and the Ph.D. degree in information and communication engineering in 2011, respectively, from HIT. He serves as an Area Editor for the journal "AEÜ -International Journal of Electronics and Communications". He served (or is serving) as a technical program committee (TPC) member for a number of international conferences, e.g., Globecom 2013 & 2014, GreenCom 2013, VTC 2012, etc. His recent research interests include interference alignment, green communications, cognitive radio, and optical communications.
Yaqin Zhao is a professor in the School of Electronics and Information Engineering at HIT. She received the B.S. degree in electronics and information engineering in 1998, M.E. degree in signal and information processing in 2000, and Ph.D. in information and communication engineering in 2008, respectively, from HIT. Her research interests include wireless communication, interference alignment, software radio, and CDMA.
References
Zhang H. , Chu X. , Ma W. , Zheng W. , Wen X. 2012 “Resource allocation with interference mitigation in OFDMA femtocells for co-channel deploymenta,” EURASIP J. Wireless Commun. Netw 2012 (1) 289 -    DOI : 10.1186/1687-1499-2012-289
Shrestha R. , Kim J. M. 2012 “Proportional resource allocation in OFDMA systems based on weighted normalized user's CSI,” IEICE Transactions on Communications E95B (6) 2137 - 2140    DOI : 10.1587/transcom.E95.B.2137
Zhao N. , Yu F. R. , Sun H. , Nallanathan A. , Yin H. 2013 “A novel interference alignment scheme based on sequential antenna switching in wireless networks,” IEEE Trans. Wireless Commun. 12 (10) 5008 - 5021    DOI : 10.1109/TWC.2013.090413.121731
Cadambe V. R. , Jafar S. A. 2008 “Interference alignment and degrees of freedom of the K-user interference channel,” IEEE Trans. Inf. Theory 54 (8) 3425 - 3441    DOI : 10.1109/TIT.2008.926344
Sung H. , Park S.-H. , Lee K.-J. , Lee I. 2010 “Linear precoder designs for K-user interference channels,” IEEE Trans. Wireless Commun. 9 (1) 291 - 301    DOI : 10.1109/TWC.2010.01.090221
Chae H. , Kim K. , Ran R. , Kim D. K. 2013 “A single feedback based interference alignment for three-user MIMO interference channels with limited feedback,” KSII Trans. on internet and information systems 7 (4) 692 - 710    DOI : 10.3837/tiis.2013.04.005
Zhao N. , Yu F. R. , Leung V. C. M. 2015 “Opportunistic Communications in Interference Alignment Networks with Wireless Power Transfer,” IEEE Wireless Commun. 22 (1) 88 - 95    DOI : 10.1109/MWC.2015.7054723
Zhao N. , Yu F. R. , Sun H. “Adaptive Energy-Efficient Power Allocation in Green Interference Alignment Wireless Networks,” IEEE Trans. Veh. Technol. to appear
Yetis C. M. , Gou T. , Jafar S. A. , Kayran A. H. 2010 “On feasibility of interference alignment in MIMO interference networks,” IEEE Trans. Signal Process. 58 (9) 4771 - 4782    DOI : 10.1109/TSP.2010.2050480
Peters S. W. , Heath R. W. 2011 “Cooperative algorithms for MIMO interference channels,” IEEE Trans. Veh. Technol. 60 (1) 206 - 218    DOI : 10.1109/TVT.2010.2085459
Schmidt D. A. , Shi C. , Berry R. A. , Honig M. L. , Utschick W. 2013 “Comparison of distributed beamforming algorithms for MIMO interference networks,” IEEE Trans. Signal Process. 61 (13) 3476 - 3489    DOI : 10.1109/TSP.2013.2257761
Razaviyayn M. , Sanjabi M. , Luo Z.-Q. 2012 “Linear transceiver design for interference alignment: complexity and computation,” IEEE Trans. Inf. Theory 58 (5) 2896 - 2910    DOI : 10.1109/TIT.2012.2184909
Gomadam K. , Cadambe V. R. , Jafar S. A. “Approaching the capacity of wireless networks through distributed interference alignment,” in Proc. of IEEE Global Telecommunications Conference (GLOBECOM) 2008 1 - 6
Gomadam K. , Cadambe V. R. , Jafar S. A. 2011 “A distributed numerical approach to interference alignment and applications to wireless interference networks,” IEEE Trans. Inf. Theory 57 (6) 3309 - 3322    DOI : 10.1109/TIT.2011.2142270
Christensen S. S. , Agarwal R. , Carvalho E. , Cioffi J. M. 2008 “Weighted sum-rate maximization using weighted MMSE for MIMO-BC beamforming design,” IEEE Trans. Wireless Commun. 7 (12) 4792 - 4799    DOI : 10.1109/T-WC.2008.070851
Shen H. , Li B. , Tao M. , Wang X. 2010 “MSE-based transceiver designs for the MIMO interference channel,” IEEE Trans. Wireless Commun. 9 (11) 3480 - 3489    DOI : 10.1109/TWC.2010.091510.091836
Shrestha R. , Bae I. , Kim J. M. 2014 “A leakage-based solution for interference alignment in MIMO interference channel networks,” KSII Trans. on internet and information systems 8 (2) 424 - 442    DOI : 10.3837/tiis.2014.02.006
Santamaria I. , Gonzalez O. , Heath R. W. , Peters S. W. “Maximum sum-rate interference alignment algorithms for MIMO channels,” in Proc. of IEEE GLOBECOM 2010 1 - 6
Xu T. Y. , Xia X. G. 2014 “A diversity analysis for distributed interference alignment using the Max-SINR algorithm,” IEEE Trans. Inf. Theory 60 (3) 1857 - 1868    DOI : 10.1109/TIT.2013.2294830
Han X. , de Almeida A. , Yang Z. 2014 “Channel estimation for MIMO multi-relay systems using a tensor approach,” EURASIP J. Adv. Signal Process. 2014 (1) 163 -    DOI : 10.1186/1687-6180-2014-163
Chen X. , Yuen C. 2014 “Performance Analysis and Optimization for Interference Alignment Over MIMO Interference Channels With Limited Feedback,” IEEE Trans. Signal Process. 62 (7) 1785 - 1795    DOI : 10.1109/TSP.2014.2304926
Wilkinson J. H. 1988 The Algebraic Eigenvalue Problem 1st Edition Oxford Univ. Press New York