一种基于贪婪基追踪算法的压缩感知超宽带信道估计方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于贪婪基追踪算法的压缩感知超宽带信道估计方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
【摘要】超宽带系统信道在特定的场景下，可表现出较强的稀疏特性。考虑IEEE 802.15.4a提供的UWB信道参考模型，选取其中稀疏特性较强的信道场景作为背景，结合压缩感知理论对信道估计进行了研究。研究中着重考虑了压缩感知过程的信号重构算法，将一种贪婪的基追踪算法应用到信道模型的重构过程，计算机仿真结果表明信道的稀疏性能够得到准确表达，且稳定性和计算效率均比较理想。
【关键词】超宽带 信道估计 稀疏信道 压缩感知 贪婪基追踪
1 概述
超宽带（UWB，Ultra-WideBand）又称为脉冲无线电通信，是一种短距离的无线高速通信技术，具有超高带宽、传输速率高、功耗小、安全性高、多径分辨能力强等特点[1-2]。与传统的使用载波调制的通信系统不同，脉冲UWB通信系统采用脉冲间隔为ns级且严格受控的超短时脉冲直接对发送数据进行调制，这就决定了其占用带宽极宽（GHz级）、耗电小的特点。与此同时，超高的带宽对UWB数字接收机的采样速率和存储空间也提出了苛刻的要求。
为了消除码间干扰等因素的影响，对UWB系统进行信道估计是必要的。对于UWB系统，由于其信号功率谱密度很低，主要对整个系统在低信噪比环境下的信道估计性能感兴趣。传统的信道估计方法，如LS（最小二乘法，Least-Square）、MMSE（最小均方误差，Minimum-Mean-Square Error）等没有考虑信道的稀疏特性，假设信道为密集多径，利用均方误差信息或一、二阶统计量来估计信道参数，易受噪声影响，估计的准确性和有效性不高。对于室内密集多径传播环境，UWB信道的多径分量可达上千条，然而各条路径分量的信号能量并不均匀，能量显著的分量只有几十个左右[3]。因此可以认为在特定情形下，UWB信道是可以表现出明显的稀疏特性的，其信道估计可以采用压缩感知技术。压缩感知理论是Donoho和Candes等人于2004年提出的，该理论表明，当信号具有稀疏性或可压缩性时，通过采集少量的信号投影值就可实现信号的准确或近似重构[4-6]。目前，已经有一些研究将压缩感知技术应用到稀疏信道的估计中。文献[3]提出了一般化的UWB稀疏信道模型及信道估计方法，针对发送脉冲设计了特殊的稀疏字典，进一步加强了信号的稀疏性，重构算法采用匹配追踪（MP，Matching Pursuit）算法；在文献[7]中，作者利用UWB信号在时域的稀疏性提出一种基于压缩感知的信道估计和信号检测算法，在信号的重构步骤中采用基追踪（BP，Basis Pursuit）算法，其仿真结果表明采用压缩感知技术的信道估计在均方误差性能上明显优于传统的LS算法。这些重构算法基本可以归为两类，一类是以BP方法为代表的最小范数法，一类是以匹配追踪为代表的贪婪算法。这两类重构算法各有优缺点，BP方法所需观测点少，精度高，可以保证解的L1范数最小，但是算法的计算负担大，速度慢，在实际中不适合应用于实时高速传输；贪婪算法实现简单，收敛快速，适合求解大规模问题，但需要更多的采样点来逼近原始信号，得到的仅为近似解，且在低信噪比的情况下重构失败概率较高。因此，如何设计出计算复杂度低、稳定且所需观测数较少的重构算法已成为目前压缩感知理论的一个热点问题[8]。
Huggins和Zucker等人于2006提出的贪婪基追踪算法（GBP，Greedy Basis Pursuit）很好地解决了上述问题，该算法兼具BP法和贪婪算法的优点，可以极大提高信号重构的精度和效率[9]。为了验证GBP对于UWB稀疏信道估计的适用性，本文将采用这种重构算法来进行压缩感知的UWB信道估计。
2 UWB系统信道模型
IEEE 802.15. 4a提供了9种不同场景下的信道参考模型CM1～CM9[10]，其单位冲激响应如图1。不难发现，在一些场景中，信道响应可表现出明显的稀疏特性，如图1（a）描述的是室内居住环境下发送机覆盖范围从7m至20m的信道，且收发机彼此在视线范围内，容易看出CM1信道中接近零的点占绝大多数，换句话说，非零点个数或能量显著的抽头个数（设为K）很小。
不失一般性，假设UWB系统的信道模型为
其中，βk（t）和τk（t）分别表示第k径信号在时刻t的信道增益和时延。本文以CM1信道为例（即在室内环境，收发机距离短且相对运动小），可以假设信道的相干时间远远大于UWB信号的符号周期，信道响应在一个或几个符号周期内是时不变的，写成离散时间信道模型，即为
其中L=τmax/Tsp是离散时间信道长度，τmax和τs分
别为最大时延和系统采样间隔。信道的稀疏性体现在信道增益向量[h0，h1，…，hL-1]中非零元素或能量显著的元素个数远小于信道长度，即K
考虑一个无噪的UWB信道估计模型
这里，p（t）是一个持续时间在纳秒（ns）级的超窄脉冲。在实际应用中，脉冲形式应符合FCC辐射掩蔽标准，本文不作讨论。
3 压缩感知技术及其在UWB信道估计
中的应用
在这一节，介绍压缩感知技术应用于UWB信道估计的原理。首先明确“字典（dictionary）”和“原子（atom）”的概念：在压缩感知理论中，可以将“字典”理解成一组完备的基，其每一个列向量称为一个“原子”。文献[11]表明，为了获得信号更加稀疏的表示，可以将这个完备的基扩展到过完备的程度，称其为“过完备字典”或“冗余字典”。显然，过完备字典的各原子之间不需要满足正交性，事实上，任何一组完备的基也可看作是一组冗余度为0的过完备基。有了这个概念，考虑一个离散信号X∈RN×1在某个有Z个原子的过完备字典D=[d1，d2，…，dZ]中可以表示为一个K-稀疏的系数向量aZ×1（K
注意下标si∈{S}，{S}表示仅被选择的原子在字典中的序号的集合。由上式，显然，a是X在过完备基D下的等价表示。在信号的接收端，用一个观测矩阵Φ∈RM×N来观测信号X，得到一个观测值这里，=ΦD称做全息字典。求解式Y=ΦX的逆问题是一个欠定问题，但由于a是K-稀疏的，可以利用一些稀疏分解算法求解Y=a的逆问题得到稀疏系数向量a，再由式（4）得到X。文献[4][5][12]证明了当满足以下受限等距特性（RIP，Restricted Isometry Property）准则时，可以保证K个稀疏系数能由Y的M个观测值准确恢复。
这个准则实际上保证了观测矩阵不会把2个或2个以上不同的K-稀疏信号映射到同一个采样集合中，这要求从观测矩阵中抽取出的任意M个列向量构成的矩阵是非奇异的[8]。同时，根据文献[4][12]，当观测矩阵Φ为一个随机的独立同分布的高斯矩阵时，并且观测数M≥cKlog2（N/K）（c是一个很小的常数，在文献[13]中取为1），便能够以很高的概率满足RIP准则。
在恢复稀疏系数向量a，即重构的过程中，比较成熟的算法主要分为两大类：最小范数法（Lp-Norm Minimization）和贪婪算法（Greedy algorithm）。
（1）最小范数法
为得到稀疏系数a，最直接的方法是求解下面的最小L0范数问题，
然而求解上式是一个NP-hard问题，幸运的是L0最小范数和L1最小范数在一定条件下会产生相同的解[14-15]，于是式（7）的问题可转化为求解
基追踪（BP，Basis Pursuit）就是一个典型的求解L1最小范数下最优化问题的原理（注意BP本身并不是一种算法，而是一种优化原理），其利用了最小L1范数优化问题与线性规划问题（LP，Linear Programming）的等价性，将线性规划中的一些经典算法引入到求解L1最小范数问题中，最著名的比如由Dantzig单纯形法和内点法，衍生出BP-Simplex算法和BP-Interior算法[15]。限于篇幅原因，此处省略对这两种算法的详细介绍。
BP方法虽可行，但实际应用中计算复杂度过高，难以适用于实时性较高的系统中；此外，文献[8]指出，由于L1范数无法区分稀疏系数尺度的位置，有可能出现能量搬移的现象。
（2）贪婪算法
另一类重构算法是基于贪婪迭代思想的算法，这类算法易于实现且计算速度相较于BP方法有极大提高。具有代表性的有匹配追踪（MP，matching pursuit）[16]及其一些改进算法，如正交匹配追踪（OMP，Orthogonal Matching Pursuit）[17，18]、压缩采样匹配追踪（CoSaMP，Compressive Sampling Matching Pursuit）[19]、正则化正交匹配追踪（ROMP，Regularized Orthogonal Matching Pursuit）[20]。
这类方法的相似之处在于，初始化一个残差和原子索引集，每一次迭代过程中，通过内积运算从全息字典中寻找一个或几个与残差相关度最高（最匹配）的原子来更新残差和索引集，并逐步逼近稀疏系数向量a，当达到设定迭代次数或残差值达到一定精度时算法停止，由a的估计值得到原始信号X。
需要指出的是，贪婪算法在理论上通常假定稀疏系数向量a的稀疏度K为已知，但是在实际应用中，多数情况下K是未知的，因此为了提高计算精度，通常需要取较BP更多的采样数，然而这样又提高了计算复杂度，因此在贪婪算法中，计算精度和复杂度不可避免的成为一对矛盾。
（3）压缩感知应用于UWB信道估计
若无线信道的单位冲激响应可表现出明显的稀疏特性，则采用压缩感知技术来估计信道通常的做法是，在发送端发送一个单位脉冲p（t）或一个脉冲间隔大于信道长度的脉冲串激励信道，为简单起见，本文采用一个单独的、高斯脉冲高阶导数形式的脉冲p（t）=Cp1（t）exp（-t2/2σ2），其中C和σ为常数，p1（t）为高斯脉冲p0（t）=Cexp（-t2/2σ2）求高阶导后关于t的多项式。则接收端得到脉冲响应
4 GBP重构算法
GBP是一种使用过完备字典来计算信号稀疏表示的算法，此算法来源于计算几何学，证明了稀疏表达系数的L1-范数最小化过程与寻找信号矢量和字典凸壳的交集的过程是相互等价的。GBP算法集成了传统的MP算法和BP算法的优点，既有MP算法实现简单、收敛快速、近似性良好的优点，同时能够像BP算法一样稳定（可用于MP算法计算失败的情形），保证解的稀疏度最小。
与BP算法将最小L1-范数法简化为线性规划问题不同，GBP算法在实现上更像MP算法，采用贪婪迭代的方式选择原子。与MP算法相比，GBP算法有两个主要的不同之处：（1）在每次迭代中，采用一种基于计算几何学的新型准则去选择下一个原子；（2）在后续的迭代中，允许丢弃前面迭代过程所选择的错误或较差原子，这是MP算法所做不到的。在文献[9]中，Patrick S. Huggins等人通过实验已证明了GBP算法可以解出L1范数最小的信号表达，并且在计算速度上快于现有的线性规划方法，尤其在解决带有过完备字典的高维问题中，其优势更加明显。附录给出了GBP算法的流程伪代码，关于增减原子的具体内容参见文献[9]。
5 仿真结果及分析
如图2所示，为了验证GBP重构算法应用于UWB信道估计的准确性和有效性，以IEEE 802.15.4a提供的室内信道模型CM1为例进行信道估计仿真，信道参数见文献[10]，其它仿真参数为：系统采样间隔0.125ns，离散信道长度1000点，用于信道估计的训练序列采用单个的高斯二阶导数形式脉冲p（t），其不同的时延版本集合作为过完备字典D。若以表示估计误差，则仿真结果表明：不考虑噪声情况下，观测点数为信道长度的50%时，信道估计值的误差在10-15数量级；观测点数为信道长度的25%时，信道估计值的误差在10-2数量级，且计算时间在多项式时间内完成。
此外，在考虑噪声情况下，本文分别用GBP算法、BP算法以及OMP算法对同一信道进行估计，以如下定义的归一化均方误差（NMSE，normalized mean-square-error）衡量估计性能（其中为的估计值）
在采样点数为信道长度的30%时，三种压缩感知方法与传统的LS方法的性能表现如图3，在小信噪比的情况下，三种压缩感知方法对噪声的抑制能力的优劣顺序为GBP>BP>OMP，这是由于GBP算法能够通过迭代在全局找到比BP方法更好的原子组合，而OMP算法在噪声影响较大的情况下无法较为精确地逼近原始信号，随着信噪比的提升，OMP算法近似性好的优点逐渐得到体现，三种算法的性能表现趋于相同；另一方面，传统的LS方法虽在SNR=-5dB时性能优于三种压缩感知方法，但随着信噪比的增大其性能并没有显著提升。在计算效率上，通过计算机仿真计时，如图4，可以看出OMP方法的计算效率与传统的LS方法几乎相当；BP方法效率最低，不适合用于信号的实时高速传输。然而，可以明显地看出GBP算法在BP和OMP之间取了一个良好的折中，而且能够像OMP算法一样在多项式时间内收敛，避免了BP方法计算时间上的不可控性。
6 结论
本文针对IEEE 802.15.4a的UWB信道模型所表现出的稀疏特性，提出了一种将GBP算法（贪婪基追踪算法）应用到基于压缩感知的信道估计中的策略，理论分析表明GBP算法同时具有BP法（范数法）和MP法（贪婪算法）的优点，并通过仿真对比了基于压缩感知的信道估计算法与传统LS算法的估计精度和计算效率，证明了GBP算法在UWB系统的信道估计中具有良好的性能表现。如何进一步提升压缩感知UWB信道估计重构算法的精度和计算效率，并且自适应地应用于实际的UWB系统中、感知信道响应的稀疏度，还有待于进一步研究。
参考文献：
[1] Porcino D， Hirt W. Ultra-wideband radio technology： potential and challenges ahead[J]. Communications Magazine， IEEE， 2003，41（7）： 66 - 74.
[2] Di Benedetto M G， Kaiser T， et al. In UWB Communication Systems-A comprehensive overview[M]. New York： Hindawi Publishing Corporation， 2006.
[3] Paredes J L， Arce G R， Zhongmin Wang. Ultra-wideband compressed sensing： Channel estimation[J]. Selected Topics in Signal Processing， IEEE Journal of， 2007，1（3）： 383 -395.
[4] Donoho D L. Compressed sensing[J]. Information Theory， IEEE Transactions on， 2006，52（4）： 1289-1306.
[5] CANDES E. Compressive sampling[C]. Proceedings of the International Congress of Mathematicians， 2006.
[6] 喻玲娟，谢晓春. 压缩感知理论简介[J]. 电视技术， 2008，32（12）： 16-18.
[7] 张先玉，刘郁林，王开. 超宽带通信压缩感知信道估计与信号检测方法[J]. 西安交通大学学报， 2010： 88-91.
[8] 石光明，刘丹华，等. 压缩感知理论及其研究进展[J]. 电子学报， 2009，37（5）： 1070-1081.
[9] Huggins P S， Zucker S W. Greedy basis pursuit[J]. Signal Processing， IEEE Transactionson， 2007，55（7）： 3760-3772.
[10] Andreas F Molisch， Kannan Balakrishnan， et al. IEEE802.15.4a channel model–Final report[R]. 2004.
[11] Rauhut H， Schnass K， Vandergheynst P. Compressed sensing and redundant dictionaries[J]. Information Theory， IEEE Transactions on， 2008，54（5）： 2210-2219.
[12] Candes E J， Romberg J， Tao T. Robust uncertainty principles： exact signal reconstruction from highly incomplete frequency information[J]. Information Theory， IEEE Transactions on， 2006，52（2）： 489-509.
[13] 沙威. “压缩传感”引论[EB/OL].（2008-11-20）.http：//www.eee.hku.hk/～wsha/Freecode/Files/Compressive_Sensing.pdf.
[14] Yaakov Tsaig， David L Donoho. Extensions of compressed sensing[J]. Signal Processing， 2006，86（3）： 549-571.
[15] Scott Shaobing Chen， David L Donoho， Michael A Saunders. Atomic decomposition by basis pursuit[J]. SIAM Review， 2001，43（1）： 129-159.
[16] Mallat S G， Zhifeng Zhang. Matching pursuits with time-frequency dictionaries[J]. Signal Processing， IEEE Transactions on， 1993，41（12）：3397-3415.
[17] Pati Y C， Rezaiifar R， Krishnaprasad P S. Orthogonal matching pursuit： recursive function approximation with applications to wavelet decomposition[C]. In Signals， Systems and Computers， 1993. 1993 Conference Record of The Twenty-Seventh Asilomar Conference on， 1993： 40-44.
[18] Tropp J A， Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. Information Theory， IEEE Transactions on， 2007，53（12）： 4655-4666.
[19] Needell D， Troppb J A. CoSaMP： Iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis， 2009，26（3）： 301-321.
[20] Needell Deanna， Roman Vershynin. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]. Foundations of Computational Mathematics， 2009，9： 317-334.