干扰对齐算法

【实例简介】
干扰对齐的的基本算法，比较那种算法更好，优化干扰对齐
2898 EEE TRANSACTIONS ON INFORMATION THEORY. VOL 58, NO 5 MAY 201 hroughput. In particular, suppose transmitter k uses a beam Proof: The proof of the first part is based on a polynomial forming matrix V& to send the signal vector sk to its intended time reduction from the maximum independent set problem receiver he. At the receiver side, receiver k estimates the trans- which is known to be Np-complete. For a given arbitrary graph mitted data vector Sk by using a linear beamforming matrix G=(V, E), where V= K, consider a K user interference Uk,i.e channel that each receiver and transmitter has a single antenna Moreover, the channel coefficients are given b Xk=Vk Sk, 5k-Ufyk 1,ifj=kor(k,j)∈E jk where the data vector sk E Rdk Xi is normalized so that 0. otherwis E(sksk=I, and Sk is the estimate of Sk at hith receiver Vk∈ Rkxdk and Uk∈ R kxak are the beamforming ma- It can be checked that the receiver nodes can only achieve a dof trices at the transmitter and the receiver of user ki, respectively of either 0 or l, and those receiver nodes achieving a doF of 1 form an independent set in G. Thus, the problem of maximizing It is known that the problem of designing optimal beam formers to maximize sum-rate of the system is NP-hard [2 the total achieved dof for the above interference channel is even in the single transmit/receive antenna case. Notice that equivalent to the problem of finding the maximum independent recent works [1]. [2] suggest that the optimal strategy should should Set of vertices in the graph G have interference alignment structure in the high SNR regime In order to prove the second part we use a polynomial reduc- tion from the 3-colorability problem. The latter problem is to de- Therefore, we are led to find a linear transmission-reception termine whether the nodes of a graph can be assigned one of the strategy that can maximize the total degrees of freedom. In three possible colors so that no two adjacent nodes are colored the next section, we provide the complexity analysis of this the same. The 3-colorability problem is known to be NP-Com- problem. Nole that all the results in this paper, including the theoretical results and algorithms, can be easily extended to plete. There are two main steps in the construction In the first step some dummy nodes are added to the channel in order to the complex channel case where the inputs to the channels are force a discrete structure such that each nondummy node may assumed to be complex and circularly symmetric (circularly only choose one of the three possible beamforming vectors. The symmetric signaling) second step is to define the direct channels in order to make a polynomial reduction from the 3-colorability of an arbitrary IIL. NP-HARDNESS OF MAXIMIZING ACHIEVED DOF graph to this problem. More details of the proof are relegated to THROUGH INTERFERENCE ALIGNMENT Appendix a In this section, we show that for a given channel, not only Theorem 1 shows that the problem of checking the achiev the problem of finding the maximum total achievable dof is ability of a given tuple of Dof is Np-hard if all users(or at least NP-hard, but also the problem of checking the achievability of a constant fraction of them) are equipped with at least three an- a given tuple of DoF,(d1,., dK), is NP-hard when there are tennas. Our next result shows that when each user is equipped at least 3 antennas at each node with no more than two antennas the same problem can be solved Notice that the interference alignment conditions in the kth in polynomial time. To this end, we need to define some nota- receiver are tions and make some observations. First of all the interference alignment problem is equivalent to finding the signal subspaces UHkV;=0.j≠k, (1) at the transmitters and the interference subspaces at the receivers rank(UFHkk v:)=dk (2) such that the interference alignment conditions are satisfied,i.e The first equation guarantees that all the interference is in the dk= dim( Sk) subspace orthogonal to Uk while the second one assures that H kkok the signal subspace Hkk vk has dimension dk and is linearly HkyS;kVj≠h independent of the interference subspace In the sequel, we examine the solvability of the above inter- where Sk and Ik denote the signal subspace at the transmitter ference alignment problem(1)-(2)in two different cases ke and the interference subspace at receiver h, respectively. The Theorem 1. For a k user mimo inter ference channel. max- operator_ represents the linear independence of two subspaces imizing the total achieved Dof, namely The first condition implies that the signal space has dimension k while the second condition says that the interference sub space and the received signal subspace must be linearly inde max ∑k HUk, VhJk=1k=1 pendent. Finally, the third condition assures that the interference from other users lies in the interference subspace (which is lin- st. UkHkiv=0.k=1.…,K,j≠k early independent of the signal subspace) rank(UlHkk: vk)=dk,k=1,.,K Notice that in the 2-antenna case. if d and rank(Hkj)=2, and the interference subspace Ik is known, is NP-hard. Moreover, if each node is equipped with at least 3 then S, can be uniquely determined by S=Hki lk, for any antennas, then the problem of checking the achievability of a j*k. Conversely, if S, is known, we can uniquely find the given tuple of DoF, (d1, d2, .. dk), is also NP-hard interference subspace of user h, i.e., Zk Hki,. Thus, by RAZAVTYaYN et al. LINEAR TRANSCEIVER DESIGN FOR INTERFERENCE ALIGNMENT 2899 starting from a node with a known subspace and traversing and the SiNr value for the qth data stream of user k, ?H, is given the interference links with full rank channel matrices, we can by uniquely determine the signal subspaces in the transmitter sides and the interference subspaces at the receiver sides as long as they all have one DoF. Furthermore, if we find a loop uk Hkk of full rank interfering links, the signal subspaces at these ∑ nodes must be the eigenvectors of the composite channel (;r)≠(k.q)uk且kjv matrix of the corresponding loop. To make this point clear, where ug and v i denote the gth column ofUk and Vk, respec- consider a 4-user interference channel. If all interfering links tively. Using a linear MMSE receiver uk, we have are full rank, by starting from transmitter l and using the loop Tx1→Rx2→Tx3→Rx4→Tx1, we have the following relations kolo l +∑玨 H kkk Z2=H2S1:S3=H2312,I4=H43S3,S1=H414 One possible choice of the utility function for the kth user could be the sum of the sinr values of its data streams. i.e Thus, S1 must be an eigenvector of the loop channel matrix H41 H43H23 H21. Therefore, S1 must be an eigenvector of all ∑ loops it is involved in Using this observation and the idea of traversing the full rank interfering channel links, we can estab lish the polynomial solvability of the problem of checking the ∑ k kklo-i+ ∑ Hk VyrTHT. HkAVk achievability of a given tuple of DoF. (r)≠(kq) Theorem 2: For a K-user MIMO interference channel where However, maximizing &k does not lead to the maximization of each transmit/receive node is equipped with at most two an- the total achieved DoF at high SNR. Therefore, we need to in tenna, the problem of checking the achievability of a given troduce another utility function in order to achieve more DoF tuple of DoF is polynomial time solvable for each user. First, we define u(y) 1+- as the utili ty func- Proof: The proof is based on transforming the problem tion of the gth data stream of user k and then, we consider to the polynomial time solvable 2-SAT problem. The latter is lk d(g) as the utility function of user k. Thus, when the problem of determining if, for a given set of clauses(or snr is low uk approximately equals the sum of Sinr values logic constraints) cach involving two Boolean variables, there On the other hand, at high SNR, when alignment is possible and exists a truth assignment to the Boolean variables so that all the there is no interference for the data stream, lk approximately clauses are satisfied. The details of the proof are relegated to equals the achieved dof at receiver k. a similar utility func Appendix B tion is proposed [42] for interference alignment in the one data Note that the NP-hardness result in this section does not Stream per user case. Using the rank one update of the matrix contradict the recent results of [45-[47 which derived easily inverse term in SINR value, we can rewrite lk as checkable necessary and sufficient conditions for the generic feasibility of interference alignment in special MIMO Systems ,S v o2i+ (e.g., symmetric systems with Nk Mk=N for all k). In ∑H H H fact, the NP-hardness result implies that it is impossible to propose an algorithm that converges to an aligned solution in The proposed utility function preserves fairness among different polynomial time for each system configuration and for any set data streams of user k and also closely approximates the sum of of channel matrices(unless P=NP). However, there might still the achieved DoF at high SNR exist a polynomial time algorithm that can solve the problem Directly optimizing linear transceivers Uk's and Vk's re- for special system configurations(e.g, symmetric systems)and quires specification of doFs dk in advance, since the dimension with high probability(e.g. for almost all channel coefficients). of Uk, and Vk depends on dk. To avoid this explicit dependence on dk, we consider optimizing the transmit covariance matrix instead of linear transceivers Uk and Vk. In particular, we write IV. STRATEGIES FOR LINEAR TRANSCEIVER DESIGN the utility function of user k as 1 In this section, we propose several iterative linear transceiver design algorithms for interference channels. USing linear trans = Tr HkKQRh(+∑HQHn ceivers introduced in Section Il. the estimated data stream at receiver k is given b where Qk= q(viy is the transmit covariance matrix K of the k: th user. However, this utility function is not directly sk=U∑H1V1+Um related to the sum-rate yet. In the sequel, we propose a weighting approach to relate the utility function in(3)to the rate of user k 2900 IEEE TRANSACTIONS ON INFORMATION THEORY. VOL 58, NO 5 MAY 201 Consider the well-known weighted sum-rate maximization By plugging back the optimal wo in(6), we immediately see problem the equivalence of (6)and (5). Furthermore, in order to have a distributed approach, we let users update their transmit co- variance matrix independently Therefore, for fixed w K kk=1, nax user k can solve the following optimization problem to update Ck hk (QkJE-1 k-l Its transmit covariance matrix st.Tr(Qk)≤yk,Qk≥0 max ak TrWKHkQkH(a+∑HkQH where nKd(+1Q,耳(GT+∑HQE)1 +∑ a,IrW,H1Q,H(1+∑H1Q j≠k L=1 E≠k is the achievable rate of user k and the coefficient ak denotes st.Tr(Qk)≤pkQk≥0. user k,s weight. USing linear algebra to simplify the objective Unfortunately, this objective function is not convex. To facil- function, the above problem can be reformulated as the fol- Itate optimization, we use an iterative convex approximation lowing equivalent optimization problem: see(5), shown at the approach. More specifically, in each iteration we optimize an bottom of the page, where the term inside the determinant approximation of the original objective function. This approxi linearly related to the utility function in(3). Similar to [40], we mation is based on locally linearizing the(nonconcave) second reformulate the problen (5) by further introducing new opi- term in the objective function, while keeping the first term un- mization variables WkERMXM \%.,K, to obtain changed, i. e, see the equation shown at the bottom of the next the following equivalent optimization problem page, where Qk is the local value of transmit covariance matrix K K iteration and Cik is the d signal covar min akIr(Wrg( Q)-> log det Wk ance matrix at receiver j excluding the kth user's signal, i. e k=1 st.Tr(Qk)≤pkQk≥0 Cik Aoi+hieQehi ≠k where Q=(Q1: Q2:..., QK) and y substituting the above approximation in(8)and simpli lying the resulting optimization problem, we get 9(Q)I-HkQH(1+∑HQH max ak w& Hkk QzHKk(O2I+>Hke Qehte The optimization problem(6)is convex in Wk The first- Tr[BkQ」 order optimality condition of (6)with respect to Wrjkcan st.Tr(Qk)≤pkQk≥0 be written as where [see(1 1), shown at the bottom of the next page]. The ob ak9k(Q)-akWk1=0,vk=1,2,……,K jective function in(10) considers the effect of transmit covari- ance matrix of user k on not only its own rate, but also those of Thus, the optimal Wk is given by thers in the interference channel Similar balanced approaches have been considered in related workS, see [31],[41].[43], and Q [44]. By further simplifying the objective function, we have =I+ Hkk Qk. H(21+∑HkQH min Ck Tr W Ckk( Ckk+ Hkk QHkk TrBk Q Vk=1.2,,K st.Tr(Qk)≤pk:Qk≥0 min ∑ ak log det(1-HQH(+∑HQH {Qk}A-1k=1 s.Tr(Qk)≤pk,Qk≥0 RAZAVTYaYN et al. LINEAR TRANSCEIVER DESIGN FOR INTERFERENCE ALIGNMENT By introducing new optimization variable Y and using the prove that each limit point of this algorithm is a stationary point Schur complement, the above problem can be formulated as of the original problem we need the following two intermediate the following Semidefinite Programming(SDP) form emmas Lemma Ifthe direct channel matrices are full-rank and tall min Ok Tr Y]+ Tr[Bk] (12)the function st.Tr(Qk)≤Pk,Qk>0, /2k-1(Qk)全 Ckk+HkkQkHKk(Wh Ckk)1/2 K (W.Ckk) 1/2 CkT WAHkA QKH(7+∑ Hke Qehke Tr BQ (13) Note that the matrices Wk and Ckk are updated by(7)and (9), respectively. Thus Wk Ckk is Hermitian positive semidef- is strictly concave with respect to symmetric positive semidef inite. Hence, for fixed matrices iWklK1, user h can update inite matrix Qk. Moreover, the objective function of(6)is also its transmit covariance matrix Qk by solving the above SDP strictly convex with respect to Wk problem. In order to implement the algorithm in a distributed manner,each user k needs to have the knowledge of Hkk and Lemma 2: Let[ (Q&: Wk)]k, be a stationary point of (6) chen the point iQkk-1 is a stationary point of (4). Conversely, W which are locally available. In addition, the value of Ckk if Qk /k=1 is a stationary point of(4),then O. W can be measured locally by subtracting its own signal from the k:=1 total transmitted signal. The only difficulty lies in obtaining the is a stationary point of (5), where Wk= gk(Q*-1,ki information about Bk. Note that each term in the summation in (11)can be calculated in receiver locally and receiver can in The proofs of Lemma I and Lemma 2 are given in the turn feedback that term to transmitter ki. In this way, transmitter ppendix c and appendix d, respectively hi can add up all these terms and calculate Bk. Thus the com- Theorem 3: Assuming that the direct channel matrices, Hkk munication overhead of the algorithm is similar to the one in[2] have full column rank, then every limit point of the proposed and [29 algorithm is a stationary point of (4 Note that the second term in( &)is a convex function of Qk Proof: According to Lemma 2, every stationary point of Therefore, the local linear approximation is a lower bound (6) is also a stationary point of (4 ). Therefore, we only need which is tight at the current point Qk. Hence, by solving(12), to prove that every limit point of the proposed algorithm is we minimize a concave lower bound of the original utility a stationary point of (6). To this end let us define the aux function(8). Since the previous iterate Qk is feasible for(8), iliary variable X=[X225, where X2k-1= Qk is the it follows that the system utility function (i.e, the objective updated transmit covariance matrix of user k at ith iteration function of(8)is nondecreasing. Furthermore,(8)is bounded and x2k= wk is the updated weight matrix of user h at ith from above and this implies the sequence of objective function iteration. In particular, we define Qk to be the solution of the values generated by the proposed algorithm converges. The following problem, shown at the bottom of the next page, where following theorem further establishes the iterate convergence f2k-1(Qk; Xi, X2,..., X2k-2, X2k-1, X2k,., x2k)is to a stationary point for the proposed algorithm. In order to the objective function of (10) which is the local concave lower ∑aWH2Q,H(Ck+HQH ≈∑qrWH玨QH(C+HQH) (Cjk+Hjk QkHk). QRHik(Cik+H Hik (Ck+H;kQH)4H1QkH(C小k+H;QkH不)-1 Bk∑H(Ck+H;QkH) ai wiHii Q,H(C+HQH孙)Hx (11) 2902 EEE TRANSACTIONS ON INFORMATION THEORY. VOL 58, NO 5 MAY 201 bound approximation of the objective function in (6)as dis- On the other hand, Xi' +1 is the local maximum of f1(, X'1 cussed in Section IV. Similarly, we define X,k Wi to be Hence the updated weight matrix of user h at iteration i,i.e Tr Vx1fi(XiT: X5)(XI-X <0 2k = wk Argmaxf(Wk: X1,., X2k-1 X2k1X2k:.,X2k) for any feasible point X1. Letting j-oc and using(15), yield where f(; )is the objective function in(6) Trx(x1;x*)(x1-X1≤0 Let X=(X be the tuple of transmit co variance-weight matrices and x* be a limit point of the se- Since f( )and fi( X*) have the same gradient with respect to quence ( g. Therefore, there exists a subsequence of in Xi at point x, it follows that dices 1,i2,.,ij:. such that r|x/x)2(x1-xi)≤0 lim Xj=X -)∞ Repeating the same argument for all k=1, 2..., 2K, we ge First,we will prove that limi -oxT 01 by Tr Vx(x1)(xk-x)≤0.k=12…,2K using contradiction. Suppose the contrary. Hence, by further restricting to a subsequence if necessary, we have By summing up all the equations for all h's we get 彐*>0 such that Trx/(x)(Xx*)≤0 where2=‖x I. Let $i Since which implies the stationarity ofX IS1=1, according to Bolzano-Weierstrass theorem, there A couple of remarks are in order. First, in the proof of The- exists a subset of indices, denoted by 1, and a unit length matrix orem 3 we have only used the strict concavity of function f( such that Consequently, the proof works for other objective functions that have the same property and using similar methods, e. g, 31 1n 2y∈I,j→∞ Second, after solving(12)to get the solution Qk, we can up- date the transmit covariance matrix by using relaxation param- Obviously,0≤n≤ for every e,0≤t.≤L. Moreover,eter0<a≤1,ie.Qk←aQ+(1-c)Qk. It can be since the feasible set is convex, XI+er SI belongs to the shown that the convergence result of Theorem 3 holds even by feasible set. Therefore, according to the definition of X2 j+1 and using a fixed relaxation parameter. using the concavity of f1, we have An alternative to solving(12)at each iteration is to update the transmit covariance matrix in a totally unselfish manner,i.e fi(xi,x2fi(X1+ersi: X solving the following problem f1(Ⅹ1:;x) Tr[ QnI On the other hand, the value of the objective function in(6) is always increasing and bounded from above. Moreover, the st.Tr(Qk)=pk,Qk≥0. (16 feasible set is closed and therefore X is in the feasible set. The objective function in(16) is the same as the second term of Hence, the value of objective function converges to f(X),i.e the objective in(10). It corresponds to the adverse effect ofuser im1(x1;x)=lim/(x1+,x)=/(X*) k to the other users. Hence, each user only cares about its effect →∞ to the other users by minimizing such an objective in each itera Therefore, letting j→∝with;∈in(14) yields tion(unselfish approach). The above problem has a closed form Qk= Pr qg, where g is the eigenvector of Bk cor- f1(X+S1;X)=f(X*),V∈[0. esponding to its minimum eigenvalue. This unselfish approach requires all the users to exhaust all their transmit power, poten Therefore,lim, -ar cl concavity of f1()(cf. Lemma 1) hich contradicts the str tially causing unnecessary interference. Furthermore, it results ij=0, or equivalently, we have in one achieved DoF for each user because Qk is always rank one. In cases that the all-one dof vector is not appropriate either X1 → 7→ (15) because it is nol achievable or because it is too conservative. the 2k-1=Qk =argmax f2k-1(Qk; Xi:x2, Q -2:42k-174-2k X2K) s.t. Tr(Qk<Pk, Qk S RAZAVTYaYN et al. LINEAR TRANSCEIVER DESIGN FOR INTERFERENCE ALIGNMENT 2903 above unselfish strategy cannot lead to the maximization of the 1.initialize with Qk= Ph- I and Wr=I. for all k=1,2,.,K sum of the achieved dofs repeat n general, if we know the dof of each user a priori and al 3.fork=1,2,…,Kdo locate equal power across the data streams we can update the transmit beamformer of user k by solving the following opti- update Wk according to(7) mization problem update Q by solving(12) date Wk: according to(7) min Tr V B V 7. until convergence,orQQ‖≤c s.t. VkVK pk I. dr (17) Fig. 1. An iterative SDP approximation algorithm for sum-rate maximization I. initialize with Vk=0 and wk=l, for all k=1, 2, ..,K This approach lets each transmitter use maximum power and pick a transmit covariance matrix Vk so as to minimize the repeat total interference to other users. It has a closed form solution 3.forh=1,2,……,Kdo VK whose columns are proportional to the eigenvectors ofB 4. update Vk by solving(17) corresponding to its dk smallest eigenvalues, scaled appropri update W& according to(7) ately to satisfy the power budget constraint Another alternative to(12)is the selfish approach where at until convergenc each step, each user only considers its own rate and solves the Fig. 2. The unselfish algorithm for sum doF maximization. following optimization problem ak TrY 26 s.Tr(Qk)≤pk,Qk≥0 Ckh+Hkh HKk(W Ckk)1/2 d (W Ckk V. SIMULATION RESULTS B16 p- Distributed Interfererce Aligment In this section, we present some numerical results comparing 5 14 -- SDP From the decentralized interference alignment (dia)method 2 and Selfish Approach the Max-siNR algorithm [2] with our proposed methods. All 12 一-Max-S|NR numerical results are averaged over 20 channel realizations. In each channel realization the path loss of the channel coefficients are generated using the 3GPP(TR 36 814)evaluation method Mean SNR(dB) ology [48]. We consider 19-hexagonal wraparound cell layout. Fig 3. Sum-rate versus SNR: Ii=4,M=2,d=2 We randomly choose K base stations, each serving a random relay in its own cell at each time slot. Each base station serves different relays in its own cell orthogonally. Therefore, at each selfish and the SDP approach work well in low SNR, but is out time slot the base station-relays form an interference channel. performed by the dia approach in the high SnR region where The relays have fixed locations so the system has enough time to the interference alignment effect begins to kick in. Interestingly, learn the channels. The MIMO channel coefficients are modeled our Unselfish approach for interference alignment outperforms by the standard single tap Rayleigh fading model. We consider the Dia algorithm in the entire practical SNR range. Although linear MMSE receivers and equal power budget as well as equal the dia method and the Unselfish approach both achieve a weight for all users and for all methods To implement DIA, w sum-rate that increases linearly with SNR, the Unselfish ap need to predetermine DoF for all users. In all the simulations proach has a better offset compared to the DIa method DoFs are set to be equal for all users In the first numerical experiment, we consider K =4 base APPENdIX A station-relay pairs, each equipped with M= 2 antennas. The PROOF OF PART TWO IN THEOREM I predetermined degrees of freedom used in the dia method are For an arbitrary graph g with N nodes, we will construct a d1=d2 d d= 2. Fig 3 represents the sum- special MIMO interference channel for which the achievability rate comparison between the proposed methods and DIA. As of one degree of freedom at each user is equivalent to the Fig 3 shows, the proposed methods yield substantially higher 3-colorability of G. In our construction, the MIMO interference sum-rates in this case channel will have two types of users: N main users, each "g It is known that the DIA method works well for the K= equipped with 3 antennas at their transmitters and receivers and M=2, d=1 case [2]. We consider the case of K= 4 trans- 11n dummy users which will be defined later. Hence the total ceiver pairs each equipped with M=3 antennas and one doF number of users is 12N. In the rest of the proof we suppose is considered for each transmitter. As can be seen in Fig 4, the that each user(either the dummy user or the main user) wants 2904 IEEE TRANSACTIONS ON INFORMATION THEORY. VOL 58, NO 5 MAY 201 P--Distributed Interference Alignment ai. 0 SDP Form 一-Max-S|NR 1i,1 aa 2 50 ig. 5. Channels to the dummy receiver li, e 10 20 Mean SnR(dB) ,0,1a,0 Fig 4. Sum-rate versus snr:K=4.M=3.d= 1 to send one data stream in other words we want to check if the b tuple of all ones is achievable by the constructed interference i,1 ,1,1 i0,150 channel or not We divide the dummy users into two groups. The number of 1,2=U i,1,1Si,1 dummy users in the first group is 2N and the number of dummy RX users in the second one is 9 N. Each dummy user in the first Fig. 6. If the dr group has 3 antennas at its receiver and transmitter, while each vi,0, 1Vi, 1, 1 =0 ummy user b;, 1 is supposed to achieve 1 Dof, then dummy user in the second group has two antennas at its trans mitter and receiver. Let us further arrange the 2n dummy users in the first group into N partitions each containing two users Fig. 5 for the case Si.1=(ai.0, 1, ai, 1,1]. Furthermore, we as We denote these subsets as A i =1, . N, Ail=2.We sume that dummy users ai. k, k= 1, 2 do not suffer from any interference also denote the users in the set Ai as ai, 1 and az. 2, and asso ciate them to the ith main user. For notational consistency, we Suppose that user ai. k(k=0, 1, 2)uses the transmit beam denote main user i as @i,0. We will also use ai, k, to denote the forming vector(vik, 1, vi k. 2: vi, k.3). As it is depicted in Fig. 6, ith transmit antenna of user ai, k, where 1< i< N. k=0, 1, 2 the interference received at the dummy receiver ofb e will be and j= 1, 2, 3. Similarly, we partition the set of 9n dumm (19) users in the second group into N subsets Bi,2 each containing exactly 9 dummy users denoted by bi t, with where si, k is the signal user ai. k intends to send. Notice that e= 1,. 9. Each of these 9 dummy users will have two re- the signals which two different users want to transmit are sta ceiving antennas which we denote as bi em, with m=1, 2 tistically independent. As a consequence, if we want to have Now for any fixed i and j, we consider any size-2 subset interference alignment at the receiver of bi., so that this user of tai,k,,:k=0,1,2J,e.g.ai,0.j,ai, 1,;. For each fixed can send its own data stream, it is necessary and sufficient to 2 and 3, there are exactly 3 of these cardinality-z subsets Since have u; k1,, e 2, k 2j 0. Hence, having interference align all e there are 3 different choices of j, we have a total of 9 sub- ment at big for al 9 is equivalent to the fact that sets of this kind for any fixed i. Let us index these 9 subsets users ai k, k=0, 1, 2 cannot send their messages through the by e, e=1,. 9, and assign the eth subset to user bi, e in antennas with the same index, simultaneously. For example, if Bi. Now we define the links in the channel for the users in A vi.0. 1+0 then vi, 1. 1 and vi, 2.1 have to be zero. On the other and Bi. First, the channel matrices of all the direct links for hand, considering the fact that each user needs to send one data any of the dummy users are I(where I is the identity matrix stream, it follows that none of the users ai. k, k=0, 1, 2,can of the appropriate size). In addition, none of the dummy users send their message on two of their antennas simultaneously, be In 1, 2, .. N) cause interference to the other users cause otherwise if for example ai, 0 sends its message on two (which means that the channel gains between their transmit an- antennas, then it would result in insufficient spatial dimension tennas and the other users receive antennas are all zero). now for either ai. 1 or a.i for the aforementioned eth subset which we denote as si. As an immediate consequence of these two facts we have a,ki.je: a;.(i, we connect FiM and ai. k(2).]e to bi, 1 just mentioned, we can conclude thal the transmit bean forIning and to bi 2.2, respectively. Here by connecting a transmit an- vector at each user a i. b,h=0, 1. 2, must be proportional to tenna to a receive antenna we mean that the channel coefficient one of the vectors [1, 0,0,0, 1, 0, or[0, 0, 1. This is true between these two antennas is 1. This situation is shown in the specially for the main user i. As we are not concerned about the RAZAVTYaYN et al. LINEAR TRANSCEIVER DESIGN FOR INTERFERENCE ALIGNMENT constant factors, we have successfully imposed a discrete struc- transmit node i and receive node i is not included in Geven ture on the problem solution so far. Notice that each dummy user if rank(Hii)=2 bi e has a total of 2 dimensions in its receiver. Since we have In what follows, we first consider a simple case which gives aligned the inter ference at each dummy user bi F, these users us the idea of how a loop of rank 2 inter fering channels forces can communicate their data streams easily along the remaining a discrete structure on the choice of signaling subspaces at the dimension left for them in their receivers and remove interfer- transmitters. Then, using this idea, we provide the proof for the ence which lies in the other dimension. Moreover, since in our general case construction the dummy users ai. k, h= 1, 2 do not experience Consider a connected component h of g where all the inter- any interference from other users and their direct channel is i, fering links are full rank and connected i e the induced sub- so these users can easily achieve one degree of freedom. Thus, graph of H over g is connected and contains all the interfering we only need to take care of the main users links ofH. We first argue that h cannot contain the receive node For each of the N main users, we must pick one of the three of any user k with dk = 2. Suppose the contrary. Then the direct transmit beamforming vectors [1,0, 0,[0.1, 0, or 0,0, 1]channel matrix, Hkk, must be full rank. [If Hkk is rank deficient, order to achieve interference alignment at all the main re- then the received signal subspace at receiver k has dimension at eivers. We suppose all the direct channels for the main users, most l, which would make it impossible to achieve dk =2. Hai, are I In order to construct the cross channels, we use the We further claim that h cannot contain any other nodes. Since structure of graphG=(V, E ). For each edge(i, i)in G, we the direct link between the transmit and receive nodes of user set Hii= Hii=I. Otherwise we set Hij= Hj i=0(zero k is not contained in H, it follows that the receive node of user matrix of appropriate size). Consequently, the main users i and h must be connected to another transmit node a in l. Let this j interfere with each other if and only if they are connected node a be associated with a user j( k). Notice that user j to each other in graph G. We claim that achieving interference achieves a doF of at least l(since all zero dof users have been alignment in the above MIMO interference channel is equiva- removed from G). By definition, node a must be connected to lent to 3-colorability of graph G. This is because each user can the receive node of user h via a full rank crosstalk channel ma choose 3 possible beamforming vectors, each corresponding to trix Hki. Thus, user j will cause a nonzero interference sub- a different color. If main user i chooses one of the three pos- space to user h contradicting dk=2. Since all users with doF sible beamforming vectors (or one of the three colors), then this =0 has been removed from graph g, we must have dk =1 for beamforming vector cannot be chosen by any other main users all receive nodes in H. For the other case where node a is a re adjacent to the main user i in the graph G, otherwise the interfer- ceive node of user j, then a is linked to the transmit node of ence would appear in the desired signal space at the receiver of user h via a full rank channel matrix. In this case, user h will main user i. This establishes the equivalence between the 3-col- cause a 2-dimensional interference subspace to user j, making orability of g and the achievability of one degree of freedom it impossible to have di21 for each user in the constructed Mimo interference channel We now assume that all receive nodes inh have one dof Since 3-colorability problem is NP-complete, it follows that the We can start from an arbitrary initial node of H and use breadth problem of checking the feasibility of interference alignment is first search(BFS)to find a spanning tree. Since each user has one NP-hard DoF. the signal and interference spaces of all receive nodes in h are uniquely determined by the signal (or interference)space AppendiX B of the initial node since the initial node is arbitrary this shows PROOF OF THEOREM 2 that the signalinterference spaces for all nodes in H are linearly By assigning zero channel weight if necessary, we can as- related to each other (via some constant composite channel ma sume without loss of generality that all transmitters/receivers trices, see the discussion before Theorem 2). Fixing any one are equipped with exactly two antennas, i.e., Mk=Nk=2, for uniquely determines the resl. For the remaining edges (or links) lI h= 1, 2, .. K. Furthermore, notice that if a user has zero not in the spanning tree, they each create a unique loop in the DoF(dk =0), then we can assign the zero beamforming vector tree. We can compute the composite channel matrices for these to this user and remove it(both its transmitter and receiver) loops(see the discussion before Theorem 2). Notice that each from the system. Thus, we can assume 1 dk 2 for all loop matrix(size 2 x 2) has either one, two or infinitely many ki= 1, 2,., K. We further assume that all the direct channel eigenvectors (when the composite channel matrix is a constant matrices且k, k= 1, 2, .., K, are nonzero. Now the problem multiple of identity matrix). Suppose a loop matrix(starting is to determine whether the given tuple of DoF (d1, d2, ...,d) from a given transmit node, say b, in the loop) has one or two is achievable or not. To this end, we need to define two bipar- unique eigenvectors, then the signal space of node b must be tite graphs over the nodes of the interference channel (one side generated by one of these eigenvectors. In fact, since the beam of the graph consists of transmit nodes and the other consists of forming vectors of nodes in I are linearly related, each loop in the receive nodes). In particular, we construct a bipartite graph H places a restriction on the choice of beamforming vector of G by connecting the transmit node of user i to the receive node node b. thus, for any fixed transmit node b in h, there are mul of user if and only if the channel between them is nonzero, tiple restriction sets, each corresponding to a loop in H caused i.e., Hii#0. Furthermore, we construct a bipartite subgraph by adding an edge to the minimum spanning tree and each con G-(V, E)of G by considering only the full rank links of taining one/two one-dimensional subspaces from which node G, i.e., connecting transmit node i to the receive node ji 6s signal space can be chosen. The receive nodes in H can if and only if rank(H; i)= 2. Notice that the link between achieve interference alignment if and only if these restricted sets 【实例截图】
【核心代码】