一种结构化压缩感知中的稀疏度自适应算法

(总第200期)信息通信INFORMATION & COMMUNICATIONS2019(Sum. No 200)一种结构化压缩感知中的稀疏度自适应算法章歆羡，唐加山,卓干兵，卢美玲,杨慧霞(南京邮电大学通信与信息工程学院，江苏南京210003)摘要：大规模多输入多输出(Large-scale MIM0)系统具有极高的频谱利用率和能量效率,是5G关键技术之一。结构化

子空间追踪算法(SSP)采用一种非正交导频并结合无线信道的空时相关性，可以较精确地估计来自基站端大量发送天线

的多个信道,针对该算法需要信道稀疏度作为先验条件的局限性,文章提出了 一种分块稀疏度自适应匹配追踪算法(BAS-

MP)O仿真结果表明，所提出的算法不仅在性能上与SSP算法相当，而且同时还能准确地估计信道的稀疏度。关键词:5G通信；MIM0系统;信道估计；结构化压缩感知;稀疏度自适应中图分类号:TP301.6 文献标识码:A 文章编号：1673-1131(2019)08-0147-04A sparsity adaptive algorithm in structured compressed sensingZhang Xinxian, Tang Jiashan, Zhuo Ganbing, LuMeiling, Yang Huixia(School of Communication and Information Engineering, Nanjing University ofPosts and Telecommunications, Nanjing210003, China) Abstract： Large-scale multi-input and multi-output (Large-scale MIMO) systems are one of the 5G key technologies with ex­tremely high spectrum utilization and energy efficiency.The Structured Subspace Pursuit Algorithm (SSP) using a non-orthogo- nal pilot combined with the space-time correlation of the wireless channel can give an accurate estimation of the multiple chan­nels of a large number of transmit antennas sending from the base station.However,a priority condition of the channel sparsity is required. In order to relax this condition5this note proposes a block sparsity adaptive matching pursuit algorithm (BASMP). The simulation results show that the proposed algorithm not only has the similar performance as the SSP algorithm dose, but also can accurately estimate the sparsity of the channel.Key words： 5G communication;MIMO system;channel estimation;structured compressive sensing;sparsity adaptation度的信号x,不妨设1概述1.1压缩感知压缩感知(CS)是近十多年来工程技术领域的关键技术之 一，它能够通过一个低维度的信号y高概率地恢复一个高维

y = ^x,yeCMxl,^e CMxN, XG C\"\" (1)其中M«No通过CS能够实现上述信号的恢复,前提是

x是一个稀疏信号。自然界的信号大部分是可压缩的,却不一2.3主要算法基于云计算的海量数据挖掘主要依靠SPRINT算法实现, 其主要流程包括决策树的创建和剪枝等。在决策树的创建过

程中，需要进行多次的数据便利，而剪枝过程则不需要，因此

可在实际操作过程中对样本集进行分割，将其分为5个没有 交集的子组，对数据额挖掘算法的准确性进行测试。预测正

确数量多代表算法准确率高。其中第一组样本数量为24123

个，正确数为17525个，第二组样本数量为26825个，正确数

剪枝消耗的时间通常仅为决策树创建时间的百分之一。真正 为18254个，第三组样本数量为20236个，正确数为16254个，

决定算法运行效率的是决策树的创建过程。在SPRINT算法 的应用下，可对数据特征进行充分表征,利用属性表和直方图

第四组样本数量为29254个，正确数为22521个，第五组样本 数量为26525个，正确数为20236个,平均准确率高达.25%。来表示数据结构。其中，属性表可在节点划分过程中进行分

裂，并以属性表为基础构建直方图。在属性表中记录索引、类

3结语综上所述,基于云计算技术实现的海量数据挖掘方法能够

标记,可以在内存之外停留，然后利用直方图表示节点属性类

分布情况。如果属性值为连续数值型，节点与两个直方图相

关，用Cbelow代表已处理样本类型分布，用Cabove代表未处 理样本类型分布，通过不间断的刷新寻找出最佳的点。如

在保证准确率的前提下,大幅度提升数据挖掘效率。而且用户

不需要投入大量的软硬件建设成本，只需要购买云计算服务,即 可进行数据挖掘操作。在云计算技术的支持下,能够满足用户

果属性值属于离散型，只需要利用直方图展示具有此属性值

海量数据挖掘的实际使用需求，是目前较为先进的处理方法。的类分布信息。此外还需要设计算法并行方式，通过加入哈

希表，存储每次节点后的子节点数据信息，并作为节点并

参考文献：［1］ 张菁.云计算技术下海量数据挖掘的实现机制［几安徽水

利水电职业技术学院学报,2018,18(01):62-.行分割依据。在哈希表中包含两类信息，一是决策时的节点

号码，二是当前树节点的子节点号。在算法移植过程中，只需

要对算法进行MapReduce化即可。采取这种算法完成决策树 的创建，可以有效提升算法执行效率。［2］ 苏彦舟.基于云计算的海量数据挖掘研究［J］.电脑迷,2018

(03):196-197.2.4实现效果为验证上述海量数据挖掘方法的实现效果，可采用驾车

风险预测公用数据作为样本训练集，对参保车主信息进行记

［3］ 张捷，封俊红,朱晓姝•云计算环境下海量数据挖掘的优化

方法研究［J］.玉林师范学院学报,2017,38(05):146-151.作者简介:郭扬(19-),男,湖北武汉人,实验师,从事计算机

管理与应用研究。录,创建决策树中的节点信息。为了判断挖掘算法的准确性,

147信息通信定是稀疏的，当存在一个稀疏变换基时，我们可以将一个非稀

疏信号进行稀疏表示，即：x^ee

N

(Z=1cNxN,oe c“xi

2)其中® €(0”册是稀疏变换基,而色G 是稀疏变换基的

第i列,e有个非0的元素，叫做稀疏因子,通常把x = 0O叫做 稀疏度为K的稀疏信号。于是(1)式改写成y = = ^00 = AO (3)此时,y叫观测矩阵,A叫传感矩阵，而A必须以参数(K0)

满足RIP约束叫即对于任意K稀疏信号0,存在常数6丘(0,1),

使得下面的(4)成立(1一刖碣勻|呦詁(1 + 6||硝

(4)在式(3)中求解e实际上是一个优化问题，即：,subject to y = AO(5)但是⑸是NP难的，我们可以用h范数替代I。范数以求

近优解，此时(5)可以变为：0 - arg m填」|外,subject to j = AO (6)关于(6)的求解，可以使用凸优化算法，然而此类算法虽 然计算精度高，但是计算复杂，在实际情况下不容易实现，人

们通常采用贪婪算法来对上述问题进行求解。1.2结构化压缩感知传统的压缩感知是对单个列向量日EC嗣进行求解，现在 考虑求解多个列向量，即畸/岸C™,研究发现当这多个列

向量满足某些特性时，稀疏性是成块状出现的,此时可以将其

看成一个块稀疏信号，相应地对传统的CS理论进行修改，从

原来的求解单个稀疏信号变成求解块稀疏信号，结构化压缩

感知(SCS)由此而来。假设这个列向量非0元素的索引值相

同,现在我们将这些向量按列排列成矩阵岸它心”叭显然，矩阵

X中有K行不为0,我们用Q=supp(x)表示X中非0行的索 引集合。对应有L个观测矩阵{”}二组成FwQ叫,那么⑶式

变为：Y = AX(7)对应(5)式变为：丘=呷

|凶「，subjecttoY = AX(8)这里我们定义4范数囱为：(9)百表示矩阵X的第行，当p=0时，凶仁表示X中非0行的行数，其中q任意取值，同样⑻式也是NP难的，对应可以变

为：艮=吨徳 MP., abject toF = AX

(10)对于不同的p,q取值,存在不同的凸优化算法和结构化贪 婪算法进行求解。1.3问题提出在Large-scale MIM0中,BS和用户需要通过信道状态信 息(CSI)来进行信号检测、预编码和资源分配等，但是随着发

送天线数的增加，在下行链路估计信道变得非常地困难。为 了避开这一问题，现在的研究大多数都采用时分双工(TDD)

148章歆羡等:一种结构化压缩感知中的稀疏度自适应算法模式,BS在上行链路可以相对容易地获取CSI,然后通过信道 的互易性直接将CSI反馈给用户叫这一过程不需要下行链路

信道估计。但是在TDD模式中，通过信道的互易性获取的下 行链路CSI并不是十分精确，甚至有很严重的失真，同时，频 分双工(FDD)才是无线蜂窝系统的主流。大量的研究表明，

无线宽带信道在时延域具有稀疏性，这是因为在无线信号传

播环境中重要散射体的数量有限，所以占据主要功率的多径 数目有限，同时最早的多径到达时间和最晚的多径到达时间

的差值很大，这导致信道的时延扩展很大。无线宽带信道还

表现出空时相关性,结合信道的上述特性，运用结构化压缩感

知理论，我们可以对信道进行精确地估计。关于信道的空时 相关性，下面会逐一介绍。2 Large-scale MIM0信道空时相关性假设一个BS具有M根天线，同时服务U个单天线用户，

现在第k个正交频分复用(OFDM)符号要通过第m根天线发

送给一个指定的用户，那么相应的信道的时域脉冲响应(CIR)

可以表示为：7 =叽(0), hnk (1),也(Z - l)f，1M 加 M M (11)其中L是指最大信道时延扩展，由于无线信道的稀疏

性，在CIR中非0元素的个数K远小于L,即K«L,通常用

supp{g} = {诽”上@)| > 0}二表示毗的支持集，即非0元素 的索引集合。在Large-scale MIM0几何结构中，由于BS处天

线紧凑，天线间距相对于信号传输距离而言很小，不同发射-接 收天线对相关联的信道共享相同的散射体，因此不同发射-接 收天线对的CIR的稀疏模式具有很大的重叠，这就是所谓的

MIM0信道的空间联合稀疏性⑷，即：suPp{*i,i }=supp{/^ }=....=supp^M」

(⑵无线信道还表现出时间联合稀疏性凶,在连续R个OFDM

符号传输过程中，路径增益在不断变化,但是路径延迟相对来

说变化得很慢，可以认为这R个OFDM符号路径延迟相同而

具有相同的稀疏性,这是因为在时变信道中路径增益的相干时

间和载波频率成反比，而路径延迟变化的持续时间和系统带宽 成反比。例如，在LTE系统中，工=2GHz，X =10MHz,路径延

迟变化速率比路径增益慢好几百倍。我们可以得到：supp仇丿} = supp{\"*i} = .... = supp{L+z}, 1M

M (13)i表示第i个OFDM符号。3非正交导频方案我们用{P”}二表示M根天线的导频序列,导频满足

同分布的随机伯努利分布。传统的信道估计是采用正交导频

方案,这种方案基于奈奎斯特定理，不同的天线导频占据不同

的子载波，当发送天线数一多，导频开销线型增长，但是Dai等

人提出了一种非正交导频方案固,这种非正交导频允许不同天

线导频占据相同的子载波，可以大大降低导频开销。图1 (a)

是传统正交导频方案，不同的天线导频占据不同的子载波，同

时用空导频来避免不同天线间的干扰，当天线数量很大时，导

频开销很大。图1(b)是非正交导频，在这种模式中不同天线 导频占据相同的子载波，并且没有了空导频，不同天线导频序

列不一样，即PmHpn。假设一个有M根发送天线的MIM0-

OFDM系统要经过N点IDFT调制，从［0, N-1］中均匀地取出信息通信章歆羡等:一种结构化压缩感知中的稀疏度自适应算法N»个数作为导频索引，记作£1={乩“”...“斗},对于传统的正

交导频方案，总的开销为的一嗣=码，而非正交导频总开销

对©按列重新排列成V，即只需要 Njp—g, = N»。-S

XSJ—

…二

AouenbaijAouenbaij其中 p,=[ey,ey>,...,ey]ec\"乂同时w也可以

看成是由L个子矩阵组成的分块矩阵，所以(16)式可以变为:1 □ data ]

yk=Txk+wk

(19)

；| 因 null pilot \\结合无线信道的时间联合稀疏性，考虑连续R个OFDM 符号传输(R由路径延迟的相干时间决定),那么最终接收的R

； 1 ■ Tx 1 pilot ；

ii ■ Tx2 pilot ' :::■ Tx M pilot 个符号的导频为：Y = TX + W

CIR 矩阵为..XHR-jw C'(20)Tx 1 Tx 2 TxM(a)传统正交导频方案

4系统模型在接收端,经过去除循环前缀和DFT解调后，通过M根 天线传输的第k个OFDM符号的接收导频信号可以表示为：” = £diag{p”}F|aM■(\"1其中C\"，” , P. =diag{p.}e

为主对角线元素的对角阵，F是NxN的DFT矩阵，FL是

取F的前L列组成的子矩阵，同时耳€ 是根据导频索引

理肚C\"乂集合Q从中取出的行组成的子矩阵切即...少3...加 s叫wfC®\"是高斯加性白噪声。同时,(14)式也可以写成”=亦+叫

其中 0=[A©a，弓耳 la” ••我

同时#=[人：,氐,...,殆》丁©€：4。在 Large-scale MIMO 中，

天线数M往往很大而导频数N»很有限，所以N»«ML,要想 通过传统的LS信道估计算法将(16)式中的&计算出来是不可

能的。我们注意到快”』二是稀疏信号,所以&也是稀疏信号, 我们可以通过SCS理论对上进行求解。根据MIMO信道的空 间联合稀疏性，不同的发射-接收天线对之间的CIR具有相同 的支持集，于是我们可以对&进行行变换，组成一个新矩阵,即：总=[召垃I，…，坨(17)

其中力=九(/)如(；)”..，仏表示从二中

以为周期取元素组成的矩阵，所以X*也可以看成是LH的分 块矩阵，每个块矩阵是Mx 1维的,同时这M个元素是全0的

或全部非0的，所以是一个块稀疏信号。同理，我们也可以ixHxixnTx 1 Tx 2 TxM其中『=[几，加，…几+心上宀\"叫做观测矩阵，等效a(b)非正交导频方案表示高斯白噪声矩阵。同时X也可以看成是一

个Lx 1维的块矩阵，每一块是对X按顺序取前M行的MxR

图1传统正交导频和非正交导频的比较维的子矩阵，即：x=[xj,xf,...,x： 丁其中5 BASMP算法实现(21)通过探索式(20)中的结构化稀疏性，基于传统的ASMP 算法问，我们提出了 BASMP算法：输入：双测矩ftr.传I®矩阵p表示将导频序列p”作输出：佶道估计值{心}二7\"初始化，X=0,Loop直到停止条件为宾1. v = vhr

2・4｛/：｛町｝：>「1机/顶｝3. $ = |o5upp(X)L(15)加\"1)* = 1护=&,炉)=云Repeat頁到break或达到最大迭代次数

a. —T), A = IF (｛灿｝：)

(16)=b-r-AusuppC^1)c. Xr = F；F,A；rzaS0曲輕荘)f tf [护 I 21卅％ thenGo to step 1End RepeatEnd Loop根据(14X21將左转化为｛心二对于上述算法，其中(•)■*表示共轨转置，陆表示范数,o

表示o范数，即向量中非o元素的个数，ir(•)表示集合中元

素值最大的前s个元素的索引,T是一个固定的阈值,S是估计149信息通信的稀疏度,V,U,Xr皆为LX 1维的分块矩阵，每一块是顺序取M 行组成的MxR子矩阵。该算法包含两个循环，外循环用来分步估计稀疏度，内

循环步骤类似于SP算法叫每次估计的稀疏度都参与内循

环中信号的重构，因为该算法的残差是单调递减的，如果一

旦发现残差在增加，说明当前稀疏度不适用，于是跳出内循

环，在外循环中估计新的稀疏度。对于算法的停止迭代条 件：内循环的循环次数超过稀疏度s时跳出，当FJL切成立

时外循环跳出，其中严|元人F是的最小值,n表示一种 阈值叫6算法仿真在仿真实验中，通过算法的均方误差(MSE)进行性能评

估,同时与SSP算法何进行比较,MSE公式如下：MSE = EM} (22)仿真参数如下:发送天线数M=,符号数RM,系统带宽

和抽样速率同为10MHz,—个OFDM符号的总载波数N=4096, 导频数NP=800,导频在频域等间隔放置，最大信道时延扩展

L=256,信道模型釆用ITU-VB模型，参数T取2.6。图2 ITU-VB信道模型下的MSE比较7| O Estimation of Sparaity |$ 6.2加85.65.45.25 ---------10 1214

16

18

20 22 24 26 28 30SNR.dB图3 ITU-VB信道模型下的稀疏度估计值通过图2可以得出,尽管SNR=30dB时存在轻微误差，但

150章歆羡等:一种结构化压缩感知中的稀疏度自适应算法是BASMP算法和SSP算法整体来说性能相当；图3是不同

SNR下的稀疏度估计值散点图,ITU-VB是6径信道，即稀疏

度为6,通过图中我们可以看到,BASMP算法每次都能准确估

计稀疏度;该算法的导频总开销比率Y尸为,平均到每 根天线的导频数N肩Np如/M为12.5,理论上恢复一个K稀

疏信号所需的最小开销为2K,当前环境下的N哑已经很接近

极限开销。7结语本文结合Large-scale MIMO信道的空时相关性,运用结

构化压缩感知理论,并采用一种非正交导频模式，基于传统的

ASMP算法，提出了 BASMP算法，相较于需要将信道稀疏度 作为先验条件的SSP算法，所提出的算法可以在保证性能的

情况下自适应地估计稀疏度，在实际工程应用中更容易实现。

必须指出,本文并没有改进SSP算法的MSE性能，后续工作 者可以着重考虑如何在稀疏度自适应的情况下改进性能，同

时不同的导频模式会产生不同的传感矩阵，从而导致不同的 性能,这也是一个大的研究方向。参考文献：[1] Z.Gao. Compressive Sensing Techniques For Next-Gener­

ation Wireless Communications [J]. IEEE Wireless Com­munications,2018 ,25(3): 144-153.[2] Marco F. Duarte; Yonina C. Eldar. Structured Compressed

Sensing: From Theory To Applications [J]. IEEE Transac­

tions On Signal Processing,2011 , 59(9): 4053-4085.[3] M.Pappa;C.Ramesh;Madhushri N.Kumar. Perfbnnance Com­

parison Of Massive MEMO And Conventional MIMO Using

Channel ParametersfC]. WISPNET. Chennai,India:IEEE,2017.[4] Y Barbotin;A.Hormati. Estimation Of Sparse MIMO Chan­

nel With Common Support[J]. IEEE Transactions On Com­munications,2012 ,60(12): 3705-3716.[5] Z. Gao;L. Dai. Structured Compressive Sensing-Based Spatio-

Temporal Joint Channel Estimation For FDD Massive MIMO[J].

IEEE Transactions On Communications^O16,(2): 601-617.[6] L. Dai. Spectrum-Efficient Superimposed Pilot Design Based

On Structured Compressive Sensing For Downlink Large-Scale

MIMO Systems[C]. URSI GAS& Beijing,Chma:IEEE,2014.[7] H.Chen;S.Guo. Pilot Design Schemes For Sparse Channel

Estimation In OFDM Systems [J]. IEEE Transactions On Ve­hicular Technology,2015, (4): 1493-1505.[8] H.Wu;S.Wang. Adaptive Sparsity Matching Pursuit Algor­

ithm For Sparse ReconstructionfJ]. IEEE Signal Processing Letters,2012,19(8): 471-474.[9] W. Dai; O. Milenkovic. Subspace Pursuit For Compressive

Sensing SignalReconstructionfJ]. IEEE Transactions On In­

formation Theory,2009, 55(5): 2230-2249.[10] F.Wan;W. Zhu. Semi-Blind Most Significant Tap Detection For

Sparse Channel Estimation Of OFDM Systems[几 IEEE Trans­

actions On Circuits And Systems,2010,57(3): 703-713.[11] Z.Gao;L.Dai. Structured Compressive Sensing Based Super­

imposed Pilot Design In Downlink Large-Scale MIMO Sys-

tems[J], ELECTRONICS LETTERS,2014,50(12): 9&