一种基于遗传算法的干扰链路选择方法

孟 娟，洪 利，李亚南，韩智明，郭丽丽

（防灾科技学院防灾仪器系 三河 065201）

1 引言

干扰是无线通信面临的关键问题之一，其限制了无线通信系统的吞吐量，降低了无线频谱的利用率。干扰对齐（interference alignment）技术通过将干扰信号压缩到更低维度的信号空间，增加期望信号占据的信号空间维度，能够极大地提高无线通信系统的信道容量。理论上，在K用户干扰信道中，干扰对齐技术能使系统的总自由度比传统正交化干扰管理方式增加K/2倍[1]。在理论上，干扰对齐可在时域[1]、频域[2]、空间域[3,4]、幅度域，甚至复数域中进行。在多用户MIMO(multiple input multiple output,MIMO)系统中，通过预编码技术实现干扰信号在空间域中的对齐，是实际中最容易实现的干扰对齐技术，成为干扰对齐研究的热点[3,4]；在多蜂窝MIMO网络中，干扰对齐技术能够有效消除小区内干扰和小区间干扰，以提高系统的总吞吐量[5,6]。当小区数量较多时，为实现完全干扰对齐，发射机或接收机必须配置大量天线，导致系统变得难以实现。然而在实际的多小区网络中，由于移动终端的随机分布，其与基站间的距离相差较大，也导致小区间干扰有强有弱。当天线配置不足以实现完全干扰对齐时，仅对部分较强的干扰链路进行干扰对齐，也可能取得接近最优的系统性能，但所需要的天线数量将大大降低。然而，当前关于部分干扰对齐的研究主要是基于预先确定的部分拓扑结构，并没有解决如何选择干扰链路的问题[7,8]。参考文献[9]对空间相关蜂窝网络部分干扰对齐进行了研究，但其复杂性过高而难以应用到实际系统中。而参考文献[10]基于移动用户的分布提出了一种基于分组的部分干扰对齐机制，但该算法性能相对较低，并没有充分利用干扰对齐技术的优势。

在部分干扰对齐技术的研究中，如何合理选择最优的干扰链路进行干扰对齐，合理地利用有限的天线资源，是需要重点研究的问题。在对干扰链路选择问题进行建模的基础上，本文提出了一种基于遗传算法的干扰链路选择机制，在给定的天线数量条件下，能够通过部分干扰对齐技术实现更优的系统性能，最后通过仿真分析证明算法的优势。

2 系统模型

设多小区网络中有G个小区，为简化分析，设每个小区中有1个基站和K个移动终端。基站和移动终端分别配置M和N根全向天线。本文仅研究下行链路，且设每个用户的自由度为D。设小区g中的第k个用户为(g,k)，其接收信号为：

其中，式（1）右边第一项为期望信号，第二项为小区内干扰，第三项为小区间干扰，最后一项为噪声。其中xg,k=且为移动终端(g,k)的第d个子数据流。为对移动终端(g,k)的预编码矩阵为移动终端(g,k)的接收重组矩阵。为从基站g’到移动终端(g,k)的信道状态矩阵，且为块衰落信道，其由路径损耗和两部分组成，即小尺度衰落的元素为独立同分布的零均值单位方差随机变量。路径损耗是无线信号传输距离与信号载波频率的函数，单位为dB。本文采用国际电信联盟无线通信局（Radiocommunication Sector of the International Telecommunication Union,ITU-R）提出的信道模型，如下所示：

3 多小区网络部分干扰对齐

3.1 问题描述

对于大规模的多小区网络，要满足完全干扰对齐的可行性条件，必须要在基站或移动端配置足够数量的天线[11]。当天线数量不足以实现完全干扰对齐时，可以仅将部分较强的干扰链路对齐到更低维度的信号空间，而将其他干扰作为加性噪声处理。通过部分干扰对齐，基于有限的天线数量，可以选择性地消除部分干扰信号以获得较高的系统性能。当然，为了实现部分干扰对齐，需要配置一个服务器从其他用户收集信道状态信息 （channel state information,CSI），计算预编码矩阵和接收重组矩阵并发送到相应的基站。具体细节可参考文献[7]，在此不再赘述。

要使移动终端(g,k)获得最优的传输速率，需要求解最优的预编码矩阵与干扰选择标志。在固定干扰选择标志的条件下，若可行性条件满足，可将干扰对齐作为求解最优预编码矩阵和接收重组矩阵的方法，则最优系统设计问题可建模为一个混合整数双层非线性规划问题：

其中fIA为基于干扰对齐设计最优预编码矩阵的函数。式(4)所示的最优化问题中，干扰选择标志的设计依赖于预编码矩阵，而预编码矩阵的设计又依赖于干扰选择标志。这种分层的结构正是双层规划的主要特点。

3.2 基于部分干扰拓扑结构的干扰对齐

式(5)与多小区网络干扰对齐约束条件类似，而针对多小区网络的干扰对齐，学术界提出了多种求解方法[12～14]，由于篇幅限制，在此不再赘述。

4 干扰链路选择

为获得最优的系统吞吐量，必须求解式(4)所示的混合整数双层非线性规划问题。双层规划问题通常难以求解，最简单的线型规划已被证明是强NP难问题。遗传算法（genetic algorithm,GA）是由Holland J H基于生物遗传进化机制提出的一种智能优化算法，它通过模拟物种的遗传与进化过程，能够有效地求解各类复杂优化问题，其求解最优可行解的可行性由模式定理得到保证。由于其简单高效的特点，遗传算法在无线通信中也得到了广泛的应用[15]，因此本文采用遗传算法进行干扰链路的选择。

4.1 遗传算法相关参数和操作定义

4.1.1 遗传算法基本参数

在本文的遗传算法实现中，设种群的大小为popSize，交叉概率为Pc，变异概率为Pm，最大进化代数为maxIA。

4.1.2 染色体编码

4.1.3 染色体校验

需要注意的是，染色体的编码还受到干扰对齐可行性条件的约束，否则函数fIA不能求得最优的发送预编码矩阵和接收重组矩阵，导致系统总容量的下降。由参考文献[7]可知染色体编码必须满足：

不满足式（6）约束的染色体称为奇异染色体。

4.1.4 初始化种群

要保证遗传算法的正常有效进行，在算法初始化阶段，需要生成一定数量的染色体。传统遗传算法一般采用随机生成的方式，但在干扰链路选择中，这种完全随机的办法不利于算法的快速收敛。从提高系统容量的角度，应优先选择较强的干扰链路进行干扰对齐。因此，在初始化过程中，对强干扰链路以较大的概率选中，而对于弱干扰链路给予较小的选中概率，这样在保证种群多样性的同时又提高了初始种群的质量。与此同时，种群的初始化还需要满足染色体的可行性。综上所述，本文采用的种群初始化算法如下所示。

算法1种群初始化算法

步骤1坌1≤g’≤G，计算每个从基站g’到移动终端(g,k)∈的初始化概率：

步骤3初始化染色体s，s为G×G×K的矩阵，且对于s(g’,g,k)，如果链路(g’,g,k)被选中对齐，则置s(g’,g,k)为0，否则置s(g’,g,k)为1。

步骤4若生成的染色体数量达到种群规模，则算法结束，否则转至步骤2。

4.1.5 适度评价

对于确定的干扰链路选择方案，可利用函数fIA求出一组最优发送预编码矩阵和接收滤波矩阵，在此基础上，由式(3)求出系统吞吐量作为适应度评价准则fitness(s)，系统吞吐量越大，则适应度越高。

4.1.6 选择操作

根据计算出的适应度函数，采用轮盘赌的方式随机选择一些染色体构成新的种群，为提高算法收敛的速度，原种群中适应度函数最高的染色体不参与轮盘赌，直接复制到新的种群中。在轮盘赌中，每条染色体被选中的概率为：

4.1.7 交叉操作

采用双亲双子交叉法，以交叉概率Pc在种群中随机选择两个染色体s1和s2，根据链路选择标志为多维矩阵的特点，先将s1和s2拉直为矢量，随机选择交叉点进行交叉，再将得到的矢量还原为G×G×K的矩阵。需要说明的是，交叉操作可能产生奇异染色体，因此交叉之后必须对其进行校验，若为奇异染色体，则重新选择交叉点进行交叉。

4.1.8 变异操作

为提高算法寻优的能力，对染色体的每一位均以变异概率进行变异操作，即通过将该位置的值取反来产生新的个体。与交叉操作类似，变异操作同样有可能产生奇异染色体。因此也必须对新的染色体进行校验，若为奇异染色体，则不发生变异。

4.2 基于遗传算法的干扰链路选择

本文提出的基于GA的干扰链路选择算法如下所示。

算法2基于GA的干扰链路选择算法

步骤1参数初始化。对遗传算法参数进行初始化操作，包括种群数量popSize、变异概率Pc、变异概率Pm、最大进化代数maxIA；

步骤2种群初始化。随机生成数量为popSize的非奇异染色体；

步骤3计算每个个体的适应度函数fitness；

步骤4判断是否满足算法终止条件，若满足条件则转到步骤9；否则转到步骤5。采用复合终止条件，只要满足设定的收敛条件或达到最大进化代数，则视为算法满足终止条件；

步骤5执行选择操作，生成新的种群；

步骤6依概率Pm执行交叉操作；

步骤7依概率Pc按位执行变异操作；

步骤8计算每个个体的适应度函数fitness，转至步骤4；

步骤9输出最优的染色体及相应的发送预编码矩阵和接收重组矩阵。

5 仿真分析

为验证本文提出算法的有效性，本文将算法与完全干扰对齐算法、经典的多小区网络匹配滤波算法[16]、仅相邻小区干扰链路被消除的部分干扰对齐算法所达到的容量进行比较。仿真网络结构为19个六边形多小区网络，其中每个小区内包含1个位于小区中心的基站和2个移动终端。多蜂窝网络干扰对齐的目标是提高小区边缘用户的吞吐量，因此设移动终端位于半径为0.9r～r的环型区域。采用Montecarlo方法随机生成100组小尺度衰落，并计算总吞吐量取平均值。

图1为4种算法小区总吞吐量的比较，其中本文算法实现干扰对齐的干扰链路数量为12，每个小区内移动终端数量K=2，每个用户自由度d=1，小区半径r=500 m。当发送功率小于25 dBm时，本文提出的基于遗传算法的干扰链路选择算法性能与完全干扰对齐基本相同，均低于传统匹配滤波算法。而当发送功率大于25 dBm时，两种干扰对齐算法性能均优于匹配滤波算法。而本文算法性能低于完全干扰对齐，但完全干扰对齐需要配置的天线数量为(G-1)K2d+Kd=74，而本文算法需要的天线数量仅为26，远少于完全干扰对齐所需要的天线数量。匹配滤波算法仅从期望信号功率最大化的角度进行预编码，完全忽略了干扰信号的影响，因此在干扰信号较弱时性能较好，但在干扰信号较强时，则系统吞吐量远低于干扰对齐算法。由图1中还可以看出，当仅考虑基站对相邻小区移动终端的干扰时，系统性能不仅远低于干扰对齐，还低于匹配滤波算法，这说明在多蜂窝网络中，仅对相邻小区间的干扰信号进行消除，是不能达到最优系统性能的。

图1 算法吞吐量性能对比

图2为本文算法与参考文献[10]提出的基于用户分组的部分干扰对齐算法对比。根据参考文献[10]的图2中的系统配置，采用三元组(7,12,1)表示系统由7个小区组成，而每个小区内用户数量为12，且每个用户传输1个数据流。理论上，若采用参考文献[10]算法，每个基站能够实现12个干扰链路对齐并消除干扰，因此仿真中设对齐的干扰链路数量为12。从图2中可以看出，本文所提的算法所获得的系统吞吐量要远高于参考文献[10]的算法，这是因为在本文所提的算法中，接收滤波器能够消除小区的所有用户间干扰；但在参考文献[10]所提算法中，接收滤波器仅能够消除分组内部的用户间干扰，而同小区内部其他组用户产生的用户间干扰会严重降低用户的SINR，从而导致系统吞吐量的降低。

图2 本文算法与参考文献[10]算法对比

6 结束语

在实际多小区网络中，基站端的天线数量往往不足以实现完全干扰对齐，限制了系统整体性能的提升。针对网络中干扰信号衰减非均匀的特性，本文提出了一种基于遗传算法的干扰链路选择算法，选择调度合理的干扰链路进行部分干扰对齐，以达到最优的系统性能。仿真实验表明，本文提出的算法能够以较少的天线数量获得较好的系统性能。但是，本文结论是在没有考虑信道估计和反馈的误差条件下得到的，对包括信道估计、反馈和干扰链路调度在内的系统性能进行综合研究和评估，还需要进一步深入研究。

1 Cadambe R,Jafar S.Interference alignment and degrees of freedom of the K-user interference channel.IEEE Transactions on Information Theory,2008,54(8):3425～3441

2 Suh C,Tse D.Interference alignment for cellular networks.Proceedings of 46th Annual Allerton Conference on Communication,Control,and Computing,Monticello,IL,USA,2008:1037～1044

3 Gomadam K,Cadambe V,Jafar S.A distributed numerical approach to interference alignment and applications to wireless interference networks.IEEE Transactions on Information Theory,2011,57(6):3309～3322

4 章扬,周正,石磊等.基于严格势博弈的干扰对齐.北京邮电大学学报,2013,36(2):50～54 Zhang Y,Zhou Z,Shi L,et al.Interference alignment based on exact potential game.Journal of Beijing University of Posts and Telecommunications,2013,36(2):50～54

5 Suh C,Ho M,Tse D.Downlink interference alignment.IEEE Transactions on Communications,2011,59(9):2616～2626

6 章扬,周正,石磊等.蜂窝网络下行链路单反馈干扰对齐算法研究.电子与信息学报,2012,34(12):2816～2822 Zhang Y,Zhou Z,Shi L,et al.Interference alignment with single feedback for downlink cellular networks.Journal of Electronics & Information Technology,2012,34(12):2816～2822

7 Guillaud M,Gesbert D.Interference alignment in partially connected interfering multiple-access and broadcast channels.Procreedings of IEEE Global Telecommunications Conference(GLOBECOM),Houston,TX,USA,2011:1～5

8 Westreicher M,Guillaud M.Interference alignment over partially connected interference networks:application to the cellular case.Proceedings of IEEE Wireless Communications and Networking Conference:PHY and Fundamentals,Paris,France,2012:647～651

9 Rao X,Ruan L,Lau V K N.Limited feedback design for interference alignment on MIMO interference networks with heterogeneous path loss and spatial correlations.IEEE Transactions on Signal Processing,2013,61(10):2598～2607

10 Zhang W F,Yu Y,Wang C,et al.Partial interference alignment for multi-cell and multi-user MIMO downlink transmission.Proceedings of IEEE 78th Vehicular Technology Conference(VTC Fall),Las Vegas,NV,USA,2013:1～5

11 Liu T T,Yang C Y.On the feasibility of linear interference alignment for MIMO interference broadcast channels with constantcoefficients.IEEE Transactions on Signal Processing,2013,61(9):2178～2191

[12]Shin W,Lee N,Lim J B,et al.On the design of interference alignment scheme for two-cell MIMO interfering broadcast channels.IEEE transactions on Wireless Communications,2011,10(2):437～442

13 Liu T T,Yang C Y.Interference alignment transceiver design for MIMO interference broadcast channels.Proceedings of IEEE Wireless Communications and Networking Conference(WCNC),Shanghai,China,2012:641～646

14 Tang J,Lambotharan S.Interference alignment techniques for MIMO multi-cell interfering broadcast channels.IEEE Transactions on Communications,2013,61(1):164～175

15 张养瑞，李云杰，高梅国.协同干扰资源优化分配模型及算法.系统工程与电子技术,2014,36(9):1744～1749 Zhang Y R,Li Y J,Gao M G.Optimal assignment model and solution of cooperative jamming resources.Systems Engineering and Electronics,2014,36(9):1744～1749

16 Pan Z,Wong K,Ng T.Generalized multiuser orthogonal space-division multiplexing.IEEE transactions on Wireless Communications,2004,3(6):1969～1973