［蘇艷濤　檀童和　李志立］

新技術(shù)·新業(yè)務(wù)

一種新穎的低復(fù)雜度稀疏信道估計(jì)算法實(shí)現(xiàn)

［蘇艷濤檀童和李志立］

摘要在無(wú)線通信中，信道估計(jì)是獲取精確接收信號(hào)的重要技術(shù)。近年來(lái)，一種新的方法：壓縮感知(Compressed Sensing, CS)，被用來(lái)估計(jì)信道。與傳統(tǒng)的信道估計(jì)相比，它大大減少了導(dǎo)頻的使用，提高了系統(tǒng)的頻譜利用率。但是，CS的高計(jì)算復(fù)雜度使得它很難應(yīng)用到實(shí)際中。雖然正交匹配追蹤(Orthogonal Matching Pursuit, OMP)的提出減少了CS的計(jì)算復(fù)雜度，但是它的執(zhí)行效率仍然較低。因此，文章將廣義的OMP(Generalized Orthogonal Matching Pursuit, GOMP)算法應(yīng)用到信道估計(jì)中，通過(guò)高效的原子選擇實(shí)現(xiàn)算法復(fù)雜度的降低，同時(shí)保證信道估計(jì)的精度。仿真結(jié)果證明了它的有效性。

關(guān)鍵詞：信道估計(jì) 壓縮感知 計(jì)算復(fù)雜度 原子 重建

蘇艷濤

男，重慶郵電大學(xué)通信與信息工程學(xué)校碩士研究生，主要研究方向基于壓縮感知的無(wú)線信道估計(jì)。

檀童和

男，重慶郵電大學(xué)通信與信息工程學(xué)校碩士研究生，主要研究方向路網(wǎng)位置隱私保護(hù)算法。

李志立

男，重慶郵電大學(xué)通信與信息工程學(xué)校碩士研究生，主要研究方向信號(hào)檢測(cè)與無(wú)線定位。

引言

由于地理環(huán)境的復(fù)雜性和無(wú)線信道的多變性，無(wú)線信號(hào)在傳輸?shù)倪^(guò)程中可能會(huì)經(jīng)歷多徑傳播和多普勒頻移，進(jìn)而引起頻率選擇性衰落和時(shí)間選擇性衰落。為了在接收端獲得精確的接收信號(hào)，需要計(jì)算準(zhǔn)確的信道狀態(tài)信息(Channel State Information, CSI)，為此，必須預(yù)先估計(jì)信道沖擊響應(yīng)(Channel Impulse Response, CIR)。目前，獲得CIR最常用的方法是基于參考信號(hào)或者導(dǎo)頻的信道估計(jì)方法。

傳統(tǒng)的基于導(dǎo)頻的信道估計(jì)方法有最小二乘法、最小均方誤差(Minimum Mean-squared Error, MMSE)法和離散傅里葉變換(Discrete Fourier Transform, DFT)法。傳統(tǒng)的信道估計(jì)方法沒(méi)有利用信道的稀疏性，造成頻譜資源的浪費(fèi)。隨著研究的不斷深入，大量文獻(xiàn)表明，無(wú)線信道本身往往呈現(xiàn)出稀疏性?；贑S的信道估計(jì)利用了無(wú)線信道的稀疏性，提高了系統(tǒng)的頻譜利用率。截止到目前，針對(duì)基于CS的信道估計(jì)，已經(jīng)出現(xiàn)了很多算法：基于l1范數(shù)最小化的基追蹤(Basis Pursuit, BP)算法[1]、基于貪婪迭代思想的匹配追蹤(Matching Pursuit, MP)算法和OMP算法[2-3]等。其中OMP算法具有重構(gòu)精度高、計(jì)算速度快的優(yōu)點(diǎn)。

近年來(lái)，國(guó)內(nèi)外的研究者把研究重點(diǎn)放在了信道估計(jì)精度的提高上。針對(duì)超寬帶（Ultra Wideband， UWB）信道，A.H. Muqaibel提出了與實(shí)際場(chǎng)景更加接近的稀疏字典，通過(guò)提高超寬帶信道的稀疏度來(lái)提高接收信號(hào)的精度[4]；Baohao Chen將卡爾曼濾波應(yīng)用到了信道估計(jì)中，從而達(dá)到了提升估計(jì)性能的目的[5]；此外，還有很多研究者通過(guò)最佳化導(dǎo)頻設(shè)置來(lái)達(dá)到提高估計(jì)精度的目的[6-7]。

實(shí)際上，利用目前已經(jīng)出現(xiàn)的信道估計(jì)算法，信道估計(jì)的精度已經(jīng)達(dá)到很高的水平，算法的復(fù)雜度已經(jīng)成為其走向?qū)嶋H應(yīng)用的最大障礙。然而，截止到目前，只出現(xiàn)了很少的文獻(xiàn)是關(guān)于復(fù)雜度減少的。文獻(xiàn)[8]提出了一個(gè)改進(jìn)的OMP算法（MOMP），在保證信道估計(jì)精度的同時(shí)減少了算法復(fù)雜度，然而它假設(shè)信道的抽頭具有緊密性，這對(duì)于實(shí)際用于具有局限性；文獻(xiàn)[9]針對(duì)稀疏信道估計(jì)提出了一個(gè)基于壓縮感知的擴(kuò)展圖，使得計(jì)算復(fù)雜度減少到了，其中M是導(dǎo)頻數(shù)量，N是信道長(zhǎng)度，但文獻(xiàn)[9]的算法容易受到噪聲影響。

前面提到的OMP算法具有重構(gòu)精度高、計(jì)算速度快的優(yōu)點(diǎn)，但是對(duì)于實(shí)際應(yīng)用來(lái)說(shuō)，其計(jì)算復(fù)雜度仍然較高。為獲得更加高效的信道估計(jì)，本文提出將GOMP算法[10]應(yīng)用到稀疏信道估計(jì)中來(lái)。GOMP算法是OMP算法的改進(jìn)算法，通過(guò)在每次迭代的過(guò)程中選取多個(gè)原子來(lái)大幅度提高算法的運(yùn)算速度，同時(shí)較好的保證信道估計(jì)的精度。實(shí)驗(yàn)仿真驗(yàn)證了GOMP算法在估計(jì)精度和復(fù)雜度方面的有效性。

在本文里，粗體的大寫字母和小寫字母分別表示矩陣和向量；AT是由矩陣A的各列組成的子矩陣，對(duì)應(yīng)于集合T中的各元素；分別表示矩陣A的共軛轉(zhuǎn)置和轉(zhuǎn)置；表示的l2范數(shù)；A, h表示向量h與矩陣A做內(nèi)積運(yùn)算；h?表示向量h的估計(jì)。

1　壓縮感知理論

壓縮感知理論的提出是信號(hào)處理領(lǐng)域的一次革命性突破，它打破了奈奎斯特采樣定理對(duì)數(shù)據(jù)處理的束縛，大大提高了系統(tǒng)效率。CS理論的應(yīng)用前提是信號(hào)具有稀疏性，即在一組觀測(cè)信號(hào)中，只有很少一部分是非零值或者占優(yōu)勢(shì)的值。大量的研究和觀測(cè)數(shù)據(jù)表明，無(wú)線信道本身往往呈現(xiàn)出很強(qiáng)的稀疏性，這為CS應(yīng)用到信道估計(jì)中奠定了基礎(chǔ)。下面給出標(biāo)準(zhǔn)的CS測(cè)量模型：

引理1：對(duì)任意K稀疏向量t，如果存在一個(gè)常數(shù)δK∈(0,1)，使得

在本文所提的算法中，測(cè)量值的個(gè)數(shù)M是一個(gè)很重要的因素。Tropp和Gilbert通過(guò)大量仿真得出結(jié)論：當(dāng)

滿足(3)式時(shí)，運(yùn)用OMP算法就可以以很大的概率將t從(1)式中重構(gòu)出來(lái)[12]。

2　問(wèn)題陳述

我們考慮一個(gè)長(zhǎng)度為N，稀疏度為K的稀疏信道，發(fā)送導(dǎo)頻個(gè)數(shù)為M，它們的位置用表示，則基于CS的稀疏信道估計(jì)關(guān)系式可表示為

這里，A=[ a1, a2,L, aN]是一個(gè)M× N的矩陣，其中ai是A的列向量，對(duì)比式(1)可以看出：y，A，h就是CS理論中的測(cè)量值，測(cè)量矩陣和稀疏信號(hào)。獲得接收導(dǎo)頻向量y之后，采取一定的恢復(fù)算法，就可以將信道h從y中恢復(fù)出來(lái)。

我們采用OMP算法對(duì)信道h進(jìn)行重建。OMP算法是貪婪算法的一種，它可以從觀測(cè)值中高效穩(wěn)定的將稀疏信號(hào)恢復(fù)出來(lái)。OMP算法的核心思想是使殘差rt最小，在每次循環(huán)迭代中采用貪婪策略選擇原子然后根據(jù)選擇的原子集合AΛt進(jìn)行稀疏重建和殘差更新。一般算法循環(huán)K次，即可獲得原信號(hào)的稀疏重建。表1是OMP算法的執(zhí)行步驟。

仔細(xì)研究表1中的OMP算法可以發(fā)現(xiàn)，整個(gè)算法的關(guān)鍵在于尋找信道h的K個(gè)非零值對(duì)應(yīng)的原子，即匹配原子，只要這K個(gè)匹配原子找到了，通過(guò)步驟③的最小二乘估計(jì)就可實(shí)現(xiàn)h的精確重建。OMP算法的大部分時(shí)間都消耗在了尋找匹配原子，即步驟①上。它的效率非常低，我們用(7)式進(jìn)行說(shuō)明

這里，C是一個(gè)包含N個(gè)引腳的集合，一個(gè)引腳對(duì)應(yīng)一個(gè)原子。由于N值往往比較大，因此通過(guò)算法1中的步驟①做N次相關(guān)獲得C會(huì)消耗比較多的時(shí)間。然而OMP算法并沒(méi)有充分利用C中的N個(gè)引腳，而是只取其中最大的一個(gè)，把其他引腳完全舍棄，這樣不僅浪費(fèi)資源，而且使得算法收斂較慢。隨著算法循環(huán)迭代次數(shù)的增加，OMP算法的缺點(diǎn)更加凸顯出來(lái)。

表1　算法1

3　GOMP算法

為了解決OMP算法收斂慢的缺點(diǎn)，本文將GOMP算法應(yīng)用到稀疏信道估計(jì)中。不同于OMP算法，GOMP算法在每次循環(huán)迭代中選取n (n 1≥)個(gè)原子，即從C中選取前n個(gè)最大值的引腳，然后根據(jù)選取的原子進(jìn)行稀疏估計(jì)和殘差更新。這樣，我們不僅充分利用了引腳集合C，而且加快了算法收斂，從而從整體上提升算法的運(yùn)行效率。關(guān)于n的取值，我們給出引理2。

引理2：在GOMP算法中，假設(shè)每次迭代選擇n個(gè)原子，則當(dāng)n滿足(8)式所示的關(guān)系時(shí)，GOMP算法可以實(shí)現(xiàn)原稀疏信道的重建[10]。

這里，K和M分別是信道的稀疏度和導(dǎo)頻的個(gè)數(shù)。

GOMP算法的具體實(shí)現(xiàn)如表2。

為了方便理解，我們給出GOMP算法執(zhí)行的示意圖，如圖1。

由圖1可知，GOMP算法的信道重建也是一個(gè)循環(huán)迭代過(guò)程。由于GOMP算法每次迭代選取n個(gè)原子，因此一般情況下算法循環(huán)K/ n次即可完成原稀疏信道的精確重建，這大大縮短了運(yùn)行時(shí)間，提高了算法的執(zhí)行效率。

表2　算法2

圖1　GOMP算法

4　仿真分析

為了證明所提算法的有效性，我們給出算法的均方誤差(Mean Square Error, MSE)仿真和運(yùn)行時(shí)間仿真，并與傳統(tǒng)的LS算法、MMSE算法、OMP算法作比較，隨后給出算法的復(fù)雜度分析。

4.1MSE仿真

考慮一個(gè)長(zhǎng)度為N =496，稀疏度為K =12的稀疏信道。導(dǎo)頻采用高斯導(dǎo)頻，為了保證信道的精確重建，選取M =256。噪聲采用復(fù)高斯白噪聲。此外，考慮到引理2，令原子選擇個(gè)數(shù)分別為n =2,5,9。仿真中采用歸一化的MSE，結(jié)果如圖2和圖3。

圖2是在不同的信噪比下，各個(gè)算法的MSE性能仿真。從圖中可以看出，隨著信噪比的增大，各算法的MSE逐漸下降，即信道重構(gòu)的精度越來(lái)越高。與傳統(tǒng)的算法相比，GOMP算法的重構(gòu)精度不僅遠(yuǎn)遠(yuǎn)好于LS算法，而且與OMP算法很接近。甚至在n =2時(shí)，GOMP算法完全可以和OMP算法相媲美。這證明了我們提出的算法在估計(jì)精度方面的有效性。

圖3是在稀疏度發(fā)生變化的情況下，各算法的MSE性能仿真。從圖中可以看出，隨著K值的不斷增大，信道估計(jì)的精度越來(lái)越低。這是由于隨著K的增加，信道變得越來(lái)越不稀疏，而導(dǎo)頻的數(shù)目卻沒(méi)有隨之增加，導(dǎo)致我們不能獲得足夠的信道信息，從而導(dǎo)致估計(jì)誤差的增大。值得注意的是，隨著K值的增加，雖然算法的性能出現(xiàn)了下降，但是GOMP算法卻一直很好的“跟隨”了OMP算法，這表明GOMP算法在不同的稀疏度下具有穩(wěn)健性。此外，雖然在圖2和圖3中MMSE算法的估計(jì)精度最好，但由于其計(jì)算復(fù)雜度過(guò)大，實(shí)際中一般不采用。我們可以將MMSE算法的MSE曲線作為估計(jì)精度的下限。

圖2　不同信噪比下的MSE性能比較

圖3　不同稀疏度下的MSE性能比較

4.2運(yùn)行時(shí)間仿真

這一節(jié)，我們給出算法的運(yùn)行時(shí)間仿真。仿真參數(shù)設(shè)置為：SNR= 5dB，M =512，K =12。仿真結(jié)果如圖4。由于MMSE算法的復(fù)雜度太大，因此仿真中沒(méi)有考慮MMSE算法。

由圖4可以看出，GOMP算法在運(yùn)行時(shí)間上具有良好的表現(xiàn)。其中GOMP(n = 5,9 )只占了OMP算法運(yùn)行時(shí)間的近1/ 2，也就是說(shuō)它可以節(jié)約超過(guò)50%的時(shí)間。隨著信道長(zhǎng)度的增加，GOMP算法的優(yōu)越性更加明顯。

此外，我們給出算法的平均迭代次數(shù)仿真，如圖5。從圖中可以看出，在不同的稀疏度下，GOMP算法的迭代次數(shù)都少于OMP算法。由于算法的復(fù)雜度與迭代次數(shù)密切相關(guān)，因此圖5的仿真結(jié)果不僅再次證明了GOMP算法在復(fù)雜度方面的優(yōu)越性，而且還證明了算法在不同的稀疏度下具有穩(wěn)健性。

圖4　同信道長(zhǎng)度下的運(yùn)行時(shí)間比較

圖5 不同稀疏度下的迭代次數(shù)比較

綜合以上仿真可以看出，針對(duì)GOMP算法，當(dāng)n值越小，信道估計(jì)的精度越高，但算法的執(zhí)行效率卻越低；當(dāng)n值越大，算法的執(zhí)行效率越高，但算法的估計(jì)精度卻越低。因此在實(shí)際應(yīng)用中，我們要根據(jù)估計(jì)精度和運(yùn)行效率的實(shí)際需求來(lái)適當(dāng)?shù)剡x取n值。

4.3復(fù)雜度分析

這一節(jié)，我們給出GOMP算法的復(fù)雜度分析，從理論層面證明算法的優(yōu)越性。文獻(xiàn)[10]指出，GOMP算法的復(fù)雜度可近似地表示為，其中s為迭代次數(shù)。由于OMP算法是GOMP算法在n =1時(shí)的特殊情況，因此OMP算法的復(fù)雜度可以表示為：

在GOMP算法中，迭代次數(shù)s和原子選擇個(gè)數(shù)n都比較小，因此其復(fù)雜度可以記作O( sMN )，而OMP算法的復(fù)雜度為O( KMN )。從圖5可以看出s往往比K小很多，也就是說(shuō)，GOMP算法在計(jì)算復(fù)雜度方面更具有優(yōu)越性。

5　結(jié)論

本文針對(duì)現(xiàn)有的信道估計(jì)方法計(jì)算復(fù)雜度較大的問(wèn)題，提出將GOMP算法應(yīng)用到稀疏信道估計(jì)中去。受益于有效的原子選擇方法，GOMP算法不僅具有良好的估計(jì)精度，而且可以大大降低信道估計(jì)所需的時(shí)間。特別是GOMP(n = 5,9 )可以實(shí)現(xiàn)節(jié)約50%以上的運(yùn)行時(shí)間，計(jì)算機(jī)仿真和理論分析證明了它的有效性。因此，GOMP算法很有希望成為未來(lái)無(wú)線通信中信道估計(jì)的備選方案。

參考文獻(xiàn)

1Jianzhong Huang, C. R. Berger, Shengli Zhou. Comparison of basis pursuit algorithms for sparse channel estimation in underwater acoustic OFDM [C]. OCEANS 2010 IEEE, 2010: 24-27

2Teng Sun, Zhiqun Song, Yongjie Zhang. Matching pursuit based sparse channel estimation using pseudorandom sequences [C]. Millimeter Waves (GSMM), 2012 5th Global Symposium on. IEEE, 2012: 33-37

3N. Aboutorab, W. Hardjawana, B. Vucetic. Application of compressive sensing to channel estimation of high mobility OFDM systems [C]. Communications (ICC), 2013 IEEE International Conference on. IEEE, 2013: 4946-4950

4A.H. Muqaibel, M.T. Alkhodary. Practical application of compressive sensing to ultra-wideband channels [J]. Communications, IET, 2012, 6(16): 2534-2542

5Baohao Chen, Qimei Cui, Fan Yang. A novel channel estimation method based on Kalman filter compressed sensing for time-varying OFDM system [C]. Wireless Communications and Signal Processing (WCSP), 2014

Sixth International Conference on. IEEE, 2014: 1-5

6Jungchieh Chen, Chaokai Wen, Pangan Ting. An efficient pilot design scheme for sparse channel estimation in OFDM systems [J]. Communications Letters, IEEE, 2013, 17(7): 1352-1355

7Xiang Ren, Wen Chen, Meixia Tao. Compressed channel estimation with joint pilot symbol and placement design for high mobility OFDM systems [C]. High Mobility Wireless Communications (HMWC), 2014 International Workshop on. IEEE, 2014: 38-42

8Ziji Ma, Hongli Liu, T. Higashino. Low-complexity channel estimation for ISDB-T over doubly-selective fading channels [C]. Intelligent Signal Processing and Communications Systems (ISPACS), 2013 International Symposium on. IEEE, 2013: 114-118

9Junjie Pan, Feifei Gao. Efficient channel estimation using expander graph based compressive sensing [C]. Communications (ICC), 2014 IEEE International Conference on. IEEE, 2014: 4542-4547

10Jian Wang, Seokbeop Kwon, Byonghyo Shim. Generalized orthogonal matching pursuit [J]. Signal Processing, IEEE Transactions on, 2012, 60(12): 6202-6216

11E. J. Candes. The restricted isometry property and its implications for compresses sensing [J]. Comptes Rendus Mathematique, 2008, 346(9): 589-592

12J. A. Tropp, A. C. Gilbert. Signal recovery from random measurements via orthogonal matching pursuit [J]. Information Theory, IEEE Transactions on, 2007, 53(12): 4655-4666

DOI:10.3969/j.issn.1006-6403.2016.01.005

收稿日期：（2015-12-08）