一种抗信道相关性的高效MIMO检测算法
2016-05-27邱梦婷罗汉文
邱梦婷, 赵 普, 俞 晖, 罗汉文
(上海交通大学 电子信息与电气工程学院,上海 200240)
一种抗信道相关性的高效MIMO检测算法
邱梦婷, 赵普, 俞晖, 罗汉文
(上海交通大学 电子信息与电气工程学院,上海 200240)
摘要:多输入多输出(MIMO)技术作为新一代移动宽带通信的核心技术,面临着天线数目增大带来的系统增益和高信道相关性导致的检测误码之间的矛盾.对此提出一种新的格基规约(LR)辅助的K-Best算法,由于经LR处理后K-Best算法中每一个父节点的子节点不确定,本文采用基于需求的扩展方案扩展子节点,并基于候选最小堆的排序算法降低排序复杂度,平均时间复杂度从O(KNlog2(KN))降低至O(Klog2K),空间复杂度从O(KN)降低至O(K).并且针对经LR处理后,星座图不再是有限的所带来的检测误码,提出了一种越界控制方案提高检测的准确率.仿真结果表明,越界控制方案使得算法在高信道相关性下其误码率(BER)性能得到了3 dB的增益.并且本算法与最大自然ML算法仅有1 dB的差距,算法复杂度远小于ML算法,仅仅随着天线数呈线性增长,是一种适用于大规模天线系统的高效的MIMO检测算法.
关键词:MIMO; 信道相关性; 格基规约; K-Best
0引言
近年来,由于多输入多输出(MIMO)能够为数据速率、信号可靠性等提供巨大的增益,使其被很多顶尖的无线标准所选中,成为新一代移动宽带通信的核心技术.而增大MIMO系统中的天线数会带来性能的提升,比如大规模MIMO技术就是利用大规模的天线系统使得吞吐量和能量的效率大幅度提高.随着对5G关键技术研究的深入,大规模MIMO技术备受无线通信领域的关注.但是天线数的增加会导致信道相关性增大,在高信道相关性下,各种非最优的MIMO检测算法性能大幅度降低.虽然最大似然(ML)检测[1]的算法性能不会受到信道相关性的影响,但其复杂度随着天线数目呈指数增长.所以在 MIMO系统中,随着天线数目的增多,信道相关性成为制约性能增益的一大要素.
针对降低信道相关性的问题,Yao等人[2]最早提出格基规约(Lattice Reduction,LR)技术,用于2×2的MIMO场景,得到了较好的抗信道相关性的结果.而后文献[3]利用LLL算法将LR应用到更高维的MIMO系统中,其运算复杂度仅仅是天线维度的多项式,相比ML检测,复杂度大大降低.文献[4]指出LR辅助的各类非最优检测算法(包括线性检测、K-Best算法[5]和球形译码算法)性能与ML算法接近,并且复杂度更低,可用于MIMO系统中的抗信道相关性的MIMO检测.文献[6]通过对早期基于需求的扩展方案作改进得到了算法复杂度的降低.文献[7-8]分别在复数域和实数域提出不同的信道自适应的LR辅助的K-Best MIMO检测器,降低了算法的复杂度,提高了系统的能量效率.文献[9]提出了一种基于最小均方误差的LR辅助的固定复杂度球形译码器算法,通过减小根节点扩展子节点中搜索树的层数大幅度降低算法复杂度,并且在单个子节点扩展中采用基于最小均方误差的LR辅助的连续干扰消除,保证了算法的性能与ML算法相接近.
针对信道相关性的增大导致非最优检测算法性能大幅度降低,而ML算法复杂度过高的问题,作者提出了一种新的LR辅助的K-Best算法,通过格基规约(LR)变换生成正交性更好的新信道矩阵.针对K-Best算法中的扩展子节点和选出K个最佳子节点分别提出了降低复杂度的方案,并且提出了一种越界控制方案用来提高检测的准确率.作者提出的算法对信道相关性的变化具有较强的鲁棒性,误码率BER性能和ML算法很接近,并且复杂度远小于ML算法,是一种用于抵抗天线数目增多带来的信道相关性增大的高效MIMO检测算法.
1MIMO系统模型
(1)
式中H={Hij}NRi=1NTj=1代表NR×NT维的信道矩阵,其中元素为独立的零均值复数高斯随机变量,方差为1.v=[v1,v2,…,vNT]T代表NR维的独立同分布的加性高斯白噪声随机变量,服从分布vi~Nc(0,σ2).
(2)
假设MIMO接收端信道估计模块可以提供信道的准确估计.
另外,为了信号处理的便利,在描述实际信号处理中需要应用MIMO系统的实数模型,即将一个复数的NR×NT的MIMO系统用一个实数的2NR×2NT的MIMO系统建模.
2格基规约算法
2.1MIMO系统中的格基规约基本原理
MIMO检测器需先对信道矩阵H做QR分解,即H=QR,其中Q为NR×NT维的正规正交阵,R为NT×NT维的上三角矩阵.然后对接收信号做如下变换,
z=QHy=QHHs+QHv=Rs+w.
(3)
由于QH为正规正交阵,噪声w依然为白噪声,没有增强噪声.进一步的MIMO检测过程为:
(4)
(5)
(6)
2.2LLL算法
LLL算法是首先由Lenstra,Lenstra和Lovsz[10]在1982年提出来的,在LR的概念提出之后,文献通过在LLL算法之前对信道矩阵应用排序QR分解来降低LLL算法的运算复杂度.LLL算法的核心思想是通过迭代减法操作以及列交换操作获得最短的基向量,即获得正交性最好的基向量.
3LR算法辅助的K-Best算法
K-Best算法[5]是一种近优的非线性检测算法,它保证了独立于SNR的固定吞吐量,并且性能接近于ML检测.通过LR算法最大化信道矩阵的正交性,可以提高K-Best算法的性能,使其接近于ML最优检测的性能.
3.1K-Best算法简述
为了方便表述,依然将MIMO的实数模型表述为:
(7)
经过类似于2.1的变换,MIMO检测方程为:
(8)
PED的递归计算方法为:
(9)
(10)
3.2LR算法辅助的K-Best检测算法流程
LR算法辅助的K-Best检测算法的伪代码如下:
输入:信道矩阵H,接收信号y,候选点数目K,
输出:MIMO检测判决输出
1.平移缩放
2.格基规约以及QR分解
3.初始化
4.扩展与排序
Forl=2NT-1:-1:1,
{Cl,Dl}=Find_K_Best_Children(Cl+1,Dl+1),
End.
5.检测
上述算法流程中,Find_K_Best_Children(Cl+1,Dl+1)函数的执行过程如下:
函数名称:{Cl,Dl}=Find_K_Best_Children(Cl+1,Dl+1),
输入:Cl+1,Dl+1,
输出:Cl,Dl,
1)κl=Ø,
2) 找到Cl+1中每个节点的最佳子节点集合作为初始的Cl,
3) 计算相应的PED,获得Dl,
Fort=1:K,
End.
3.3越界控制方案
接收信号经过处理后的表达式为:
(11)
图1 越界检测错误示意图
所以,在K-best算法输出K个最优的叶子节点后增加上述越界控制方案,从而得出更为准确的判决符号.计算K-Best算法输出的K个最优的叶子节点相应的父辈节点,获得K条具有最小欧式距离的路径,从这K条路径里选出符合上述xB的条件的最优路径.
3.4基于需求的低复杂度扩展方案
的在传统的K-best检测器中,搜索树每一层的每一个父节点的子节点数目以及数值是已知并且确定的,而LR处理破坏了这个规律,导致LR和K-best算法难以联合实现,并且随着天线数目增加,这个问题将更加复杂.为此,提出一个动态生成最优子节点的方法,即为基于需求的扩展方案,用于降低子节点扩展的复杂度.
该方案主要用于快速地找出某一节点的第m个最佳子节点,其中m=1,2,…….假设已知第l+1层的k个节点,由集合κl+1表示.对于κl+1中某一节点,能够最小化el(S(l))的子节点是其最佳的子节点,即
(12)
(13)
(14)
3.5基于候选最小堆的排序方案
需从每一层父节点扩展的KN个子节点中选出最佳的K个子节点,快速排序算法的平均运算时间复杂度为O(KNlog2(KN)),空间复杂度为O(KN),复杂度较高.为此提出一种基于候选最小堆的排序方案,用于降低寻找K个最佳子节点的运算复杂度.
候选最小堆是由第l层的候选节点所构成的最小化堆,其表现形式为一个节点构成的数组,长度为k,数组元素的索引为1,2,…,k.候选最小堆中的元素满足下述关系:
(15)
其中,ai表示候选最小堆中索引为i的元素,是堆中的某个节点,那么堆顶元素a1即为当前Cl中具有最小PED值的节点.
图2 利用候选最小堆寻找上一层最优子节点的算法步骤流程图
利用候选最小堆寻找上一层最优子节点的算法步骤流程图如图2所示.
图2中,对Cl,Dl的初始化和更新均按照Find_K_Best_Children(Cl+1,Dl+1)函数进行,更新候选最小堆即取出当前堆顶元素,放入新元素,再根据式(15)重新排列最小堆元素.
建立候选最小堆的时间复杂度为O(K),空间复杂度为O(K).每次在候选最小堆中压入新的节点时,更新最小堆的时间复杂度为O(log2K).因此,对于k个父节点完成上述更新操作的平均时间复杂度为O(Klog2K),空间复杂度为O(K).
4仿真结果分析
本节对LR辅助的K-Best检测算法及其各改进方案进行仿真,并分析仿真结果、比较算法性能.
收端与发端的天线均配置为8×8.在链路中,采用Turbo码作为信道编码,16QAM作为基带调制方式,信道相关性按照LTE标准中所述方法生成,K-Best检测过程中的参数K为16.最终的仿真结果为仿真5000个数据包所得的结果.
图3(a)、(b)所示为采样Turbo编码并且信道相关性分别为低和高时,各检测方案之间的比较.图3中,“K-best”指传统K-best算法,“K-best LR”是指LR联合K-best算法(结合3.4和3.5所述的两种改进方案),“K-best LR Advanced”是指在“K-best LR”的基础上加上3.3所述的越界控制方案.由图3可知,在不同的信道相关性情况下,随着信噪比的变化,各算法的BER性能的变化趋势以及相互之间的关系是一样的,只是在信道相关性较低时各算法的性能均优于信道相关性高的情况.“K-best”的BER性能随着信噪比增大的恶化程度明显增大,而“K-best LR”和“K-best LR Advanced”的BER性能与“ML”很接近,最大仅有约0.5 dB的差距.而“K-best”与“ML”在信噪比较低的情况下差距较小,随着信噪比的增大,其差距越来越明显.在BER = 10-2量级上,“K-best LR Advanced”相较“K-best LR”具有更优的BER性能,且约3dB的增益.“ML”和“K-best LR Advanced”的BER性能相近,“ML”算法的性能略优于“K-best LR Advanced”算法,在BER = 10-2量级上,约有1dB的性能优势.但鉴于“K-best LR Advanced”的低复杂度和可实现性,“K-best LR Advanced”算法依旧具有更高的实用价值.
图3 各K-best算法的BER性能比较
5结论
作者提出了一种新的LR辅助的K-Best算法,首先对信道矩阵进行格基规约变换,同时发送信号的星座点随之发生变化,但是新的信道矩阵具有更好的正交性.然后算法使用了基于需求的扩展方案扩展K-Best算法中每一个父节点的子节点,以及基于候选最小堆的排序算法从所有子节点中选出K个最佳子节点,此排序算法不需要对所有子节点作排序,复杂度大幅度降低.寻找每一层K个最佳子节点的平均时间复杂度从O(KNlog2(KN))降低至O(KlogK),空间复杂度从O(KN)降低至O(K).并且提出了越界控制方案用于解决由于LR处理导致星座图无限带来的误码,仿真结果表明,在高信道相关性下,该方案为算法的BER性能带来了3 dB的增益,并且与ML算法相差仅1 dB.同时,作者指出,降低搜索树最上面几层(最后进行判决的几层)的继承节点数,并不会影响检测性能,并且能够进一步降低算法的复杂度,但是在实际系统中,在应用这种减小迭代次数的方法时应与越界控制方案进行折衷考虑.本算法是一种对信道相关性的变化具有较强鲁棒性的高效的MIMO检测算法,可以用于大规模MIMO系统,复杂度仅随着天线数呈线性增长.
参考文献:
[1]Agrell E,Eriksson T,Vardy A,et al.Closest point search in lattices [J].IEEE Transactions on Information Theory,2002,48(8):2201-2214.
[2]Yao H,Wornell,Gregory W.Lattice-reduction-aided detectors for MIMO communication systems [C]//IEEE:Global Telecommunications Conference.Taipei:IEEE,2002.
[3]Windpassinger C,Fischer R F H.Low-complexity nearmaximum-likelihood detection and precoding for MIMO systemsusing lattice reduction [C]//IEEE.Information Theory Workshop.Paris:IEEE,2003.
[4]Aubert S,Nasser Y, Nouvel F.Lattice Reduction-Aided Minimum Mean SquareError K-Best Detection for MIMO Systems [C]//IEEE.2012 International Conference on Computing,Networking and Communications(ICNC).Maui:IEEE,2012.
[5]Kwan-wai W,Chi-ying T,Cheng R S K,et al.A VLS Iarchitecture of a K-bestlattice decoding algorithm for MIMO channels [C]//IEEE.IEEE International Symposium on Circuits and Systems.Phoenix-Scottsdale:IEEE,2002.
[6]Zhou Q,Ma X L.An Improved LR-aided K-Best Algorithm for MIMO Detection [C]//IEEE.2012 International Conference on Wireless Communications & Signal Processing (WCSP).Huangshan:IEEE,2012.
[7]Sheikh F,Szabo-Wexler E,Rahman M,et al.Channel-adaptive complex K-best MIMO detection using lattice reduction [C]//IEEE.2014 IEEE Workshop on Signal Processing Systems (SiPS).Belfast:IEEE,2014.
[8]Rahman M,Rohani E,Choi G S.An iterative soft decision based adaptive K-best decoder without SNR estimation [C]//IEEE.2014 48th Asilomar Conference on Signals,Systems and Computers.Pacific Grove:IEEE,2014.
[9]Kim H,Lee H,Kim J.MMSE-Based Lattice-Reduction-Aided Fixed-Complexity Sphere Decoder for Low-Complexity Near-ML MIMO Detection [C]//IEEE.2015 IEEE International Workshop on Local and Metropolitan Area Networks (LANMAN).Beijing:IEEE,2015.
[10]Lenstra A K,Lenstra H W,Lov′asz L.Factoring polynomials with rational coefficients [J].Mathematische Annalen,1982,261(4):515-534.
(责任编辑:包震宇)
An efficient MIMO detection algorithm with theresistance to channel correlation
QIU Mengting, ZHAO Pu, YU Hui, LUO Hanwen
(School of Electronic Information and Electrical Engineering,Shanghai JiaoTong University,Shanghai 200240,China)
Abstract:MIMO,the core technology of next generation wireless broadband communication,is faced with the contradiction between the system gain benefit by increasing antennas and the detection error due to high channel correlation.Therefore,we propose a new Lattice-Reduction(LR)-assisted K-Best algorithm.Since the children nodes of every parent node are uncertain after LR processing,on-demand expansion scheme is adopted to expand children nodes,and the sorting algorithm based on minimum candidate heap is used to decrease the sorting complexity.Then the average time complexity is decreased from O(KNlog2(KN)) to O(Klog2K),and the spatial complexity is decreased from O(KN) to O(K).In order to solve the problem of detection error caused by no longer limited constellation map after LR processing,a boundary control scheme is put forward to improve the detection accuracy.Simulations show that with the aid of boundary control,the BER performance has obtained 3dB gain when channel correlation is high.And the proposed algorithm only lost 1dB gain compared to ML algorithm with much smaller computational complexity,the complexity is only linearly increased with the number of antennas.So this proposed efficient algorithm is suitable for large scale antenna system.
Key words:MIMO; channel correlation; lattice reduction; K-Best
中图分类号:TN 929.5
文献标志码:A
文章编号:1000-5137(2016)02-0172-08
通信作者:俞晖,中国上海市闵行区东川路800号,上海交通大学电子信息与电气工程学院,邮编:200240,E-mail:yuhui@sjtu.edu.cn.
基金项目:国家科技重大专项“TD-LTE/FDD-LTE/TD-SCDMA/WCDMA/GSM多模基带商用芯片研发”(2013ZX03001007-004)
收稿日期:2015-09-29