基于树搜索算法的多用户 MIMO 系统的自由度分配

高 慧，朱 谦

基于树搜索算法的多用户 MIMO 系统的自由度分配

高 慧，朱 谦

针对最大化多用户 MIMO 系统的和速率的问题，提出了将迭代式干扰对齐技术（Iterative Interference Alignment: IIA）和系统自由度（DoF）分配策略相结合的一种算法。系统的 DoF 分配是通过树搜索算法（Tree search）来实现的。理论分析及实验仿真结果表明，该算法获得的系统容量，接近遍历法（exhausting search：EX）的结果，但是在算法复杂性及收敛时间上明显优于遍历法。

多用户MIMO系统；迭代式干扰对齐；树搜索算法；自由度分配；和速率

0 引言

不断增长的信息传输需求，使得有限的频谱资源日益紧张。已有的研究结果[1，2]表明多输入多输出 (MIMO)技术可在不占用更多频率资源的情况下，极大地提高无线信道的容量。然而，对于多用户MIMO系统，当天线数目及用户数量增加时，多用户干扰会成为制约系统和速率增加的重要因素[3]。

干扰对齐技术通过在接收方给干扰信号分配一部分可用的资源（时间，频率，空间）并迫使所有干扰信号被压缩在这部分空间来消除其对期望信号的影响。Cadambe 和Jafar 的研究表明：干扰对齐技术可使得多用户MIMO系统的自由度达到最大[4]。

以往的研究大都从消除干扰的角度使得多用户MIMO系统获得最大和速率，本文从自由度（Degree of Freedom: DoF）分配这个视角探索DoF分配策略对多用户MIMO系统和速率的影响。

对多用户MIMO系统做DoF分配实是组合优化问题。对于该类问题，通过遍历法（exhausting search：EX）便可选出最优的DoF分配策略。然而，很多组合优化问题是NP完全的，得到

精确解所需的收敛时间随着问题的规模增加呈指数增长。因此有必要缩小搜索空间，提高算法的收敛速度，减少算法计算复杂度。

本文基于IIA[5]技术，将树搜索算法应用到了多用户MIMO系统的DoF 分配策略中。该算法提出了搜索树的概念，将不同的DoF 分配策略抽象为搜索树中的节点。自顶向下逐层搜索可使多用户MIMO系统和速率达到最大的DoF分配策略。文中用黑体表示矩阵或向量，表示矩阵的共轭转置表示的Frobenius 范数,Ι表示单位矩阵。

1 系统模型

多用户MIMO系统如图1所示：

图1 K用户 MIMO 系统的结构

假设系统中有K个用户，信道噪声是高斯的。源节点和目的节点分别配置M和N根天线。假设信道参数与时间和频率无关，K个源节点分别独立地向K个目的节点发送数据，目的节点既能接收到期望信号，也可接收到其他源节点的干扰信号，且用户数据间不共享。由目的节点k到源节点l之间的信道矩阵是所有用户数据X经预编码矩阵及信道矩阵在目的节点k处相加得到接收信号如公式（1）：

令 Ω 表示K用户 MIMO 系统所有可能的DoF分配方式的集合表示一种具体的DoF分配方案，其中表示用户k获得的DoF数目。由于每对源节点-目的节点 可 以 发 送 的 数 据 流 数 目 为因 此

文献[5]提出的迭代式的干扰对齐算法（IIA）可在不用考虑用户数目，获得CSI 的方式以及DoF的分配下获得预编码矩阵 lF与干扰空间的正交基 kC，从而将干扰信号压缩在部分自由度上。

因此，K用户MIMO 系统的和速率可以表达如公式（2）：

将IIA技术与DoF分配策略相结合的目标是最大化多用户MIMO系统的和速率，因此K用户MIMO 系统的和速率的优化规划问题可描述如公式（3）：

2 树搜索（Tree search ）算法

2.1 搜索树的生成

2.1.1 生长

图2 4用户 MIMO 干扰系统（M=2，N=3）的搜索树

图2描述了一个4用户 MIMO 系统的搜索树，假设发射机有2根天线，接收机有3根天线，表示自由度分配方案。则即每个用户最多可获得的自由度数目为2。

为了保证4用户MIMO系统每次都有4个用户在工作，令树的根节点为 [1 1 1 1]。接着依次给每个用户增加一个自由度生成4个子代，分别为[2 1 1 1]，[1 2 1 1]，[1 1 1 2]。重复上述过程直到达到系统自由度总数目的上限。

2.1.2 剪除

图3 剪除后的4用户MIMO系统（M=2，N=3）的搜索树

2.2 算法描述

对于K用户MIMO 系统，由根节点（初始DoF分配策略）出发，依次遍历第二层的所有节点并计算出该层可使系统和速率最大的DoF分配方式，将其作为第三代的父节点，其他节点删除。然后再依次遍历第三层的所有节点，挑选出可使系统和速率最大的DoF分配方式，将其作为下一代的父节点并将其他节点删除。在搜索的过程中，记录每次保存的节点。待搜索树截止生长时从中选出最佳的节点作为最终的DoF分配策略。

因此，基于Tree search算法及IIA,本文给出了可以快速优选出能最大化K用户 MIMO系统和速率的DoF分配算法如见图4所示：

图4 Tree search IIA 算法流程图

Tree search IIA

(5)从搜索过程中保存的所有父亲节点中选出可使系统和速率达到最大的DoF分配作为最终的结果

2.3 算法空间复杂度分析

通过对搜索过程中的节点的判断与处理，Tree search IIA算法的计算空间为与遍历法的计算并计算初始系统和速率；

(2)保存父节点的系统和速率，生成下一代子节点；

(3)计算所有子代成员的系统和速率，选出其中可使系统和速率达到最大的DoF分配作为下一代的父节点；空间相比，明显降低了计算的复杂度。这种优势在系统的用户数目及天线数目增加时更为显著。

3 实验结果与分析

如图5所示：

图5 两种算法在K=4，M=7，N=6时算法性能比较

描述了树搜索算法与遍历法的性能，本例中，树搜索算法所获得的系统和速率距离遍历法获得的精确值的平均误差是0.7284（bit/s/Hz），误差的标准差为0.295（bit/s/Hz）。因此树搜索算法所得到的结果是非常接近遍历法获得的最优解的。然而，就两种算法的收敛时间而言，树搜索算法是遍历法的1/20。因此，树搜索算法在收敛时间上的优势非常可观的，如表1所示：

表1 不同天线数目下树搜索算法和遍历法的计算量比较，K=4，NR=50dB

表1给出了不同天线数目下两种算法的收敛时间及收敛结果比较。表明当天线数目增加时，树搜索算法在收敛时间上的优势更为明显，且收敛结果非常接近最优解。因此树搜索算法在能够达到次最优解的同时，又大大削减了算法的收敛时间。从两种算法的计算空间复杂度角度来看，这是不难理解的。遍历法的计算复杂度是 min(M,N)K，而树搜索算法的算法复杂度只有

4 结论

本文研究了多用户MIMO系统的和速率问题，基于树搜索算法算法及迭代干扰对齐算法提出了一种有效的进行DoF分配的方法。仿真结果表明：Tree search IIA算法不但大大降低了计算复杂度，缩减了收敛时间，而且所获得的次最优解非常接近遍历法的结果。当用户数目或者天线数目增加时，Tree search IIA算法的低复杂度优势更为显著。

[1]Telatar, Emre. Capacity of Multi-antenna Gaussian Channels[J]. European Transactions on Telecommunications, 1999, 10(6):585-595

[2]G. J. Foschini , M. J. Gans. On limits of wireless communications in a fading environment when using multiple antennas[J]. Wireless Personal Communications, 1998, 6: 311-335

[3]Gollakota, Shyamnath and Perli, Samuel David and Katabi, Dina. Interference alignment and cancellation[J]. SIGCOMM Comput. Commun. Rev., 2009,39(4):159-170

[4]Cadambe, V. R., Jafar, S. A.. Interference Alignment and the Degrees of Freedom for the K User Interference Channel[J]. Information Theory,IEEE Transactions on , 2008 54(8):3425-3441

[5]Peters, S.，Heath, R.W.. Interference alignment via alternating minimization[C]. Acoustics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE International Conference on,Taipei，2009

Degrees of Freedom Allocation for Multi-user MIMO System Based on Tree Search Algorithm

Gao Hui, Zhu Qian
(School of Information Science and Technology Fudan University,Shanghai 200433,China)

Considering the problem that maximizing the sum rate of multi-user MIMO system，an algorithm that joints iterative interference alignment and allocation strategies of degrees of freedom (DoF)is proposed in this paper. DoF allocation of multi-user MIMO system is achieved via Tree Search algorithm. Theoretical analysis and simulation results show that the proposed Tree Search algorithm achieves sum rate performance near that of the exhausting search （EX）asymptotically, while the Tree Search algorithm has lower computation complexity and less convergence time.

Multi-User MIMO System ; Iterative Interference Alignment（IIA）; Tree Search Algorithm; Degrees Of Freedom Allocation; Sum Rate

TP311

A

1007-757X(2014)02-0038-03

2014.02.26）

高 慧（1989-），女，安徽省宿州市，复旦大学通信系，硕士研究生。研究方向：无线通信 MIMO 技术，上海，200433朱 谦（1960-），男，上海市，复旦大学通信系，副教授。研究方向：数据通信与网络、无线传感器网络应用，上海，200433