司菁菁, 候肖蘭, 程銀波

(燕山大學(xué)信息科學(xué)與工程學(xué)院, 河北 秦皇島 066004)

?

基于塊剪枝多路徑匹配追蹤的多信號(hào)聯(lián)合重構(gòu)

司菁菁, 候肖蘭, 程銀波

(燕山大學(xué)信息科學(xué)與工程學(xué)院, 河北 秦皇島 066004)

針對(duì)多路徑匹配追蹤(multipath matching pursuit,MMP)無(wú)法利用稀疏信號(hào)的結(jié)構(gòu)信息、迭代層數(shù)較高時(shí)計(jì)算復(fù)雜度較大等問(wèn)題,提出了一種適用于重構(gòu)塊稀疏信號(hào)的塊剪枝多路徑匹配追蹤算法。該算法以原子塊作為路徑擴(kuò)張的節(jié)點(diǎn),在一定迭代層數(shù)后引入剪枝操作,極大地降低了數(shù)據(jù)運(yùn)算量。進(jìn)而,針對(duì)多觀測(cè)向量(multiple measurement vector,MMV)問(wèn)題,提出了MMV塊剪枝MMP算法,用以實(shí)現(xiàn)無(wú)線傳感網(wǎng)小范圍內(nèi)多傳感器信號(hào)的聯(lián)合重構(gòu)。實(shí)驗(yàn)表明,塊剪枝MMP的重構(gòu)性能優(yōu)于MMP,MMV塊剪枝MMP的聯(lián)合重構(gòu)性能優(yōu)于MMV塊A*正交匹配追蹤、MMV子空間匹配追蹤和MMV正交匹配追蹤。

分布式壓縮感知; 多觀測(cè)向量; 塊稀疏; 多路徑匹配追蹤

0　引　言

物聯(lián)網(wǎng)是當(dāng)今信息科學(xué)領(lǐng)域一個(gè)迅速發(fā)展的新方向。無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSN)作為物聯(lián)網(wǎng)的重要支撐,近年來(lái)受到了業(yè)界研究者的廣泛關(guān)注。WSN通過(guò)布置在一定區(qū)域內(nèi)的多個(gè)傳感器節(jié)點(diǎn)組成網(wǎng)絡(luò),靈活方便地監(jiān)測(cè)區(qū)域內(nèi)的環(huán)境變化,在軍事、民用、環(huán)境監(jiān)測(cè)等領(lǐng)域具有重要的實(shí)際應(yīng)用價(jià)值。然而,節(jié)點(diǎn)資源(能量、存儲(chǔ)空間、計(jì)算能力等)有限是限制WSN應(yīng)用的一個(gè)主要因素。如何降低WSN中數(shù)據(jù)采集與傳輸?shù)馁Y源消耗是一個(gè)值得深入研究的問(wèn)題。

分布式壓縮感知(distributed compressed sensing,DCS)[1]將適用于單個(gè)信號(hào)壓縮與重構(gòu)的壓縮感知(compressed sensing,CS)理論擴(kuò)展到多個(gè)信號(hào),實(shí)現(xiàn)了多信號(hào)的分布式壓縮與聯(lián)合重構(gòu)。DCS技術(shù)的應(yīng)用能夠有效減少WSN中的數(shù)據(jù)采集量,從而節(jié)約存儲(chǔ)空間,提高傳輸效率,降低數(shù)據(jù)采集與傳輸過(guò)程中的能量消耗[2]。

多觀測(cè)向量(multiple measurement vector,MMV)問(wèn)題[3-4]是DCS理論的一個(gè)重要研究方向,解決的是具有相同支撐集的多個(gè)稀疏信號(hào)的聯(lián)合重構(gòu)問(wèn)題。在WSN小范圍內(nèi),多個(gè)傳感器檢測(cè)到的溫度、濕度等信號(hào)通常具有很強(qiáng)的相關(guān)性,在利用稀疏基(例如小波基)表示時(shí),它們的顯著系數(shù)通常出現(xiàn)在大致相同的位置處。可見(jiàn),WSN小范圍內(nèi)多傳感器采集信號(hào)的聯(lián)合重構(gòu)問(wèn)題可以看作是一個(gè)MMV問(wèn)題。另一方面,傳感器采集信號(hào)在稀疏基上通常是塊稀疏的,即非零系數(shù)是成簇出現(xiàn)的[5]。因此,針對(duì)MMV問(wèn)題的塊稀疏信號(hào)聯(lián)合重構(gòu)算法的研究在WSN中具有重要的實(shí)際應(yīng)用價(jià)值。

貪婪迭代算法因其具有重建速度快等優(yōu)點(diǎn),成為實(shí)用研究中最受關(guān)注的一類(lèi)CS重建算法。在標(biāo)準(zhǔn)CS理論下,針對(duì)塊稀疏信號(hào)的貪婪迭代類(lèi)重構(gòu)算法有塊稀疏匹配追蹤(block matching pursuit,BMP)算法、塊稀疏正交匹配追蹤(block orthogonal matching pursuit,BOMP)算法[6]、基于約束等距的塊稀疏匹配追蹤算法[7]、非均勻塊稀疏信號(hào)盲重構(gòu)算法[8]、塊A*正交匹配追蹤(block A*orthogonal matching pursuit,BA*OMP)算法[9]、子空間匹配追蹤(subspace matching pursuit,SMP)算法[10]等。然而,目前針對(duì)MMV問(wèn)題的貪婪迭代類(lèi)塊稀疏信號(hào)聯(lián)合重構(gòu)算法僅僅有較少文獻(xiàn)提及。文獻(xiàn)[9]將BA*OMP算法應(yīng)用于MMV問(wèn)題,提出了MMV塊A*正交匹配追蹤(BA*OMP for MMV,BA*OMPMMV)算法。文獻(xiàn)[11]針對(duì)塊稀疏信號(hào),將SMP算法分別應(yīng)用到MMV模型和廣義多觀測(cè)向量(generalized multiple measurement vector,GMMV)模型中,提出了SMP-MMV算法和SMP-GMMV算法。

本文首先針對(duì)塊稀疏信號(hào)的重構(gòu)問(wèn)題,在多路徑匹配追蹤(multipath matching pursuit,MMP)算法[12]的基礎(chǔ)上,提出了塊剪枝多路徑匹配追蹤(block pruning multipath matching pursuit,BPMMP)算法。該算法利用了塊稀疏信號(hào)的結(jié)構(gòu)信息,在獲得良好重建效果的同時(shí),極大地降低了數(shù)據(jù)處理量,既適用于信號(hào)塊稀疏度已知的情況,也適用于塊稀疏度未知的情況。進(jìn)而,針對(duì)MMV問(wèn)題提出了MMV塊剪枝多路徑匹配追蹤(block pruning multipath matching pursuit for MMV,BPMMPMMV)算法,用以實(shí)現(xiàn)WSN小范圍內(nèi)多傳感器信號(hào)的聯(lián)合重構(gòu)。利用合成信號(hào)和Intel Berkeley Research Lab[13]的WSN實(shí)測(cè)溫度信號(hào)進(jìn)行的仿真實(shí)驗(yàn)表明,BPMMP算法的重構(gòu)性能優(yōu)于MMP算法,BPMMPMMV算法的聯(lián)合重構(gòu)性能優(yōu)于BA*OMPMMV、SMP-MMV和MMV正交匹配追蹤 (orthogonal matching pursuit for MMV, OMPMMV)算法[14],且其運(yùn)行時(shí)間顯著低于BA*OMPMMV、SMP-MMV和SMP-GMMV。

1　MMV問(wèn)題和塊稀疏信號(hào)

1.1MMV問(wèn)題

MMV問(wèn)題解決的是具有相同支撐集的多個(gè)稀疏信號(hào)的聯(lián)合重構(gòu)問(wèn)題[15]。設(shè)n個(gè)共享支撐集的稀疏信號(hào)構(gòu)成信號(hào)集X=[x1,x2，…,xn]∈RN×n,觀測(cè)矩陣A∈RM×N。多觀測(cè)向量Y=[y1,y2,…,yn]∈RM×n可表示[3]為

Y=AX

(1)

式中,xi和yi分別表示X和Y的第i(i=1,2,…,n)列;N和M分別表示每個(gè)信號(hào)xi的維數(shù)和每個(gè)觀測(cè)向量yi的維數(shù)。

任何MMV問(wèn)題都可以通過(guò)奇異值分解和降維操作轉(zhuǎn)換為標(biāo)準(zhǔn)形式的MMV問(wèn)題[15]。

(2)

式中,‖X‖0=|suppX|,多觀測(cè)向量Y是滿秩的,即rank(Y)=n≤‖X‖0。

當(dāng)考慮噪聲時(shí),MMV模型可表示[15]為

(3)

式中,E∈RM×n表示觀測(cè)噪聲。

1.2塊稀疏信號(hào)

在信號(hào)處理領(lǐng)域的許多實(shí)際應(yīng)用問(wèn)題中,稀疏信號(hào)中的非零值、零值是成塊出現(xiàn)的,稱(chēng)這類(lèi)信號(hào)為塊稀疏信號(hào)[16-18]。為定義塊稀疏,將信號(hào)x表示[9]為

(4)

式中,d表示塊的長(zhǎng)度;P表示塊的數(shù)量;x[p]表示第p(p=1,2,…,P)塊;N=Pd。若x中非零塊的個(gè)數(shù)為K,則稱(chēng)信號(hào)x是塊K稀疏的[16]。當(dāng)d=1時(shí),塊稀疏信號(hào)等同于普通的稀疏信號(hào)。

當(dāng)對(duì)形如式(4)所示的塊稀疏信號(hào)進(jìn)行壓縮感知觀測(cè)時(shí),對(duì)觀測(cè)矩陣A進(jìn)行相應(yīng)劃分[9]。

(5)

式中,ai表示A的第i(i=1,2,…,N)列;A[p]表示A的第p(p=1,2,…,P)列塊(原子塊)。

2　BPMMPMMV算法

MMP算法用節(jié)點(diǎn)代表一個(gè)原子,用路徑代表用以重構(gòu)原始信號(hào)的候選原子子集(以原子索引集合的形式表示),將最優(yōu)路徑的搜索問(wèn)題建模成組合學(xué)中的樹(shù)形搜索問(wèn)題,并基于貪婪迭代算法實(shí)現(xiàn)最優(yōu)路徑的快速搜索。MMP算法的重構(gòu)性能優(yōu)于正交匹配追蹤 (orthogonalmatchingpursuit,OMP)、分段式正交匹配追蹤 (stagewiseorthogonalmatchingpursuit,StOMP)、子空間追蹤 (subspacepursuit,SP)等經(jīng)典CS重構(gòu)算法[12]。然而,MMP算法需要事先確知信號(hào)的稀疏度,且當(dāng)信號(hào)稀疏度較大時(shí),迭代層數(shù)較多、候選路徑較多、計(jì)算復(fù)雜度較高。另一方面,MMP算法無(wú)法利用信號(hào)的結(jié)構(gòu)稀疏信息,不適用于塊稀疏信號(hào)的重構(gòu)。此外,在實(shí)驗(yàn)中發(fā)現(xiàn),MMP算法在一定迭代層數(shù)之后,一些候選路徑雖然已經(jīng)明顯呈現(xiàn)出重建殘差較大的問(wèn)題,但是迭代過(guò)程依然會(huì)義無(wú)返顧地為這些路徑搜索下一原子,實(shí)現(xiàn)路徑擴(kuò)展,而這些路徑在最后一層對(duì)應(yīng)的候選路徑一般也具有較高的重建殘差,不會(huì)成為最優(yōu)解?？梢?jiàn),在迭代搜索過(guò)程進(jìn)行到一定程度之后,那些已經(jīng)表現(xiàn)出重建性能不佳的路徑,若繼續(xù)參加迭代,不但對(duì)最終的重建結(jié)果沒(méi)有太大幫助,反而浪費(fèi)了大量的運(yùn)算時(shí)間與數(shù)據(jù)存儲(chǔ)空間。針對(duì)以上問(wèn)題,本文在MMP算法的基礎(chǔ)上引入樹(shù)枝修剪操作,提出了適用于塊稀疏信號(hào)重構(gòu)的BPMMP算法。

2.1BPMMP算法

BPMMP算法將觀測(cè)矩陣劃分成長(zhǎng)度相等、重疊長(zhǎng)度相等的原子塊,以原子塊為單位進(jìn)行路徑擴(kuò)張。用路徑代表重構(gòu)原始信號(hào)的候選原子塊集合(以原子塊索引集合的形式描述)。結(jié)合基于樹(shù)形結(jié)構(gòu)的路徑擴(kuò)張與貪婪迭代算法,實(shí)現(xiàn)重建原始信號(hào)的最優(yōu)原子塊集合的快速搜索。在迭代層數(shù)達(dá)到Γ值之后,對(duì)搜索樹(shù)進(jìn)行剪枝操作,根據(jù)重建殘差對(duì)當(dāng)前層搜索到的候選路徑進(jìn)行篩選,去掉1/α比例沒(méi)有希望成為最優(yōu)解的候選路徑,使它們不參加后續(xù)層的路徑擴(kuò)展,有效減少運(yùn)算時(shí)間與存儲(chǔ)空間的浪費(fèi)。

MMP算法和BPMMP算法的計(jì)算量均主要集中于觀測(cè)矩陣與重建殘差的乘積。此矩陣與向量乘積的計(jì)算次數(shù)取決于迭代層數(shù)和每層候選路徑的數(shù)量,而迭代層數(shù)與信號(hào)的稀疏度有關(guān)。設(shè)塊稀疏信號(hào)x的稀疏度為K*、塊稀疏度為K,K*>K。利用MMP算法與BPMMP算法重建x的平均迭代層數(shù)分別為O(K*)和O(K)。在第k層迭代中(k≥Γ),MMP和BPMMP算法的最大候選路徑數(shù)分別為L(zhǎng)k和Lk(1-1/α)k-Γ。每條候選路徑在進(jìn)行擴(kuò)張時(shí)最多需要M×N次乘法運(yùn)算?？梢?jiàn),MMP的復(fù)雜度為O(MNK*LK*),而B(niǎo)PMMP的復(fù)雜度為O(MNKLK(1-1/α)K-Γ),明顯低于MMP。

圖1　BPMMP算法樹(shù)形搜索結(jié)構(gòu)與剪枝操作舉例Fig.1　An example of tree-structured path searching and pruning in BPMMP

2.2BPMMPMMV算法的實(shí)現(xiàn)

為了求解塊稀疏信號(hào)的MMV問(wèn)題,本文在BPMMP算法的基礎(chǔ)上,進(jìn)一步提出了BPMMPMMV算法。該算法利用了BPMMP算法的路徑擴(kuò)張與剪枝機(jī)制,但針對(duì)MMV問(wèn)題的求解,對(duì)原子塊選擇、信號(hào)集重構(gòu)以及殘差更新等操作進(jìn)行了修改。

(6)

(7)

此外,在求取最小殘差路徑、剪枝篩選路徑、判斷迭代停止條件等操作中,BPMMPMMV算法均針對(duì)MMV模型,利用Frobenius范數(shù)代替了BPMMP算法中的歐幾里得范數(shù)。

BPMMPMMV算法的偽代碼如表1所示。

表1　BPMMPMMV算法的偽代碼

3　實(shí)驗(yàn)結(jié)果及分析

編寫(xiě)Matlab仿真程序,分別利用隨機(jī)合成信號(hào)和WSN中多傳感器的實(shí)測(cè)溫度信號(hào)測(cè)試本文提出的BPMMP算法和BPMMPMMV算法的重構(gòu)性能,并分別與MMP、SMP、BA*OMP算法和OMPMMV、BA*OMPMMV、SMP-MMV、SMP-GMMV算法進(jìn)行比較。仿真計(jì)算機(jī)的硬件配置為CPUAMDathlon(tm)×255,主頻3.11GHz,內(nèi)存1.75GB。軟件環(huán)境為32位Windows7操作系統(tǒng)下的MatlabR2010a。以歸一化均方誤差(normalizedmeansquarederror,NMSE)和準(zhǔn)確重構(gòu)率(accuratereconstructionrate,ARR)作為衡量算法重構(gòu)性能的指標(biāo)。

NMSE與ARR的定義式[9]分別為

(8)

(9)

3.1利用BPMMP算法和BPMMPMMV算法重構(gòu)合成信號(hào)的實(shí)驗(yàn)

本節(jié)以隨機(jī)塊稀疏信號(hào)作為實(shí)驗(yàn)對(duì)象。參數(shù)設(shè)置如下:原始信號(hào)中的非零值服從[0,1]上的均勻分布,信號(hào)長(zhǎng)度N=500,MMV模型的信號(hào)個(gè)數(shù)n=10,信號(hào)觀測(cè)值的維數(shù)M根據(jù)采樣率設(shè)置,觀測(cè)矩陣A中的元素符合高斯分布N(0,1/N),且A的每一行均經(jīng)過(guò)歸一化處理。合成信號(hào)的稀疏度為30,支撐隨機(jī)分布在5個(gè)集中的位置,每個(gè)位置支撐的個(gè)數(shù)是隨機(jī)的。原子塊的大小d=4,重疊原子數(shù)為2。實(shí)驗(yàn)在不同采樣率下進(jìn)行,每個(gè)采樣率下重復(fù)進(jìn)行500次。這里以采樣率[0.1,0.2]區(qū)間為例展示實(shí)驗(yàn)結(jié)果。

(1)BPMMP算法與MMP、SMP、BA*OMP算法的比較

圖2顯示了在不考慮噪聲影響的情況下,BPMMP算法與MMP、SMP和BA*OMP算法的NMSE值和ARR值的對(duì)比情況。

圖2　無(wú)噪聲時(shí)BPMMP算法與MMP、SMP和BA*OMP算法重構(gòu)性能的比較　Fig.2　Reconstruction performance comparison of BPMMP with MMP, SMP and BA*OMP in the absence of noise

由圖2可見(jiàn),在無(wú)噪聲影響的情況下,與MMP算法相比,BPMMP算法的NMSE值更低、ARR值更高。這說(shuō)明,與MMP算法相比,BPMMP算法具有更高的重構(gòu)性能,更適用于塊稀疏信號(hào)的重建。圖2還表明,BPMMP算法的重構(gòu)性能優(yōu)于同樣適用于重構(gòu)塊稀疏信號(hào)的SMP算法,且當(dāng)采樣率大于0.11之后,BPMMP算法的重構(gòu)性能不低于BA*OMP算法。

以原子塊為單位進(jìn)行路徑擴(kuò)充以及剪枝操作的引入必然使得BPMMP算法的運(yùn)行時(shí)間顯著低于MMP算法。表2顯示了在不考慮噪聲影響的情況下,在不同采樣率下,BPMMP算法的運(yùn)行時(shí)間分別與BA*OMP算法和SMP算法運(yùn)行時(shí)間的比值。由表2可見(jiàn),在采樣率大于0.12之后,BPMMP算法的運(yùn)算時(shí)間低于BA*OMP算法與SMP算法。

表2　無(wú)噪聲時(shí)BPMMP算法運(yùn)行時(shí)間分別與BA*OMP算法和SMP算法運(yùn)行時(shí)間的比值

(2) BPMMPMMV算法與BA*OMPMMV、SMP-MMV、SMP-GMMV和OMPMMV的比較

圖3、圖4分別顯示了在不考慮噪聲影響和當(dāng)SNR=10 dB時(shí)在采樣率[0.1,0.2]范圍內(nèi)BPMMPMMV、BA*OMPMMV、SMP-MMV、SMP-GMMV和OMPMMV 5種算法的NMSE值和ARR值的變化情況。由圖3、圖4可見(jiàn),在無(wú)噪聲影響或當(dāng)SNR=10 dB時(shí),對(duì)于隨機(jī)合成的MMV模型塊稀疏信號(hào),BPMMPMMV算法的聯(lián)合重構(gòu)性能明顯優(yōu)于OMPMMV算法與SMP-MMV算法;在采樣率超過(guò)0.12之后,BPMMPMMV算法的聯(lián)合重構(gòu)性能高于SMP-GMMV算法;在采樣率超過(guò)0.11之后,BPMMPMMV算法的聯(lián)合重構(gòu)性能不低于BA*OMPMMV算法。

圖3　無(wú)噪聲時(shí)5種算法重構(gòu)性能的比較Fig.3　Performance comparison of five reconstruction algorithms in the absence of noise

在上述5種聯(lián)合重建算法中,BPMMPMMV算法和BA*OMPMMV算法的重建性能較高。下面在不考慮噪聲影響的情況下比較BPMMPMMV算法和BA*OMPMMV算法的資源消耗。實(shí)驗(yàn)中發(fā)現(xiàn),當(dāng)NMSE值達(dá)到10-2時(shí),BPMMPMMV和BA*OMPMMV需要的觀測(cè)值數(shù)量M分別為60和64;當(dāng)NMSE值達(dá)到10-3時(shí),BPMMPMMV和BA*OMPMMV需要的觀測(cè)值數(shù)量分別為64和70;當(dāng)NMSE值達(dá)到10-30時(shí),BPMMPMMV和BA*OMPMMV需要的觀測(cè)值數(shù)量分別為66和76?？梢?jiàn),當(dāng)BPMMPMMV算法和BA*OMPMMV算法達(dá)到相同NMSE值時(shí),前者比后者需要更少的觀測(cè)值。因此,與BA*OMPMMV算法相比,BPMMPMMV算法能夠降低數(shù)據(jù)采集與傳輸過(guò)程中的能量消耗,減少存儲(chǔ)空間占用,節(jié)約資源。

圖4　SNR=10 dB時(shí)5種算法重構(gòu)性能的比較Fig.4　Performance comparison of five reconstruction algorithms when SNR=10 dB

表3、表4分別給出了在無(wú)噪聲影響和當(dāng)SNR=10 dB時(shí),BPMMPMMV算法運(yùn)行時(shí)間分別與BA*OMPMMV、SMP-MMV、SMP-GMMV算法運(yùn)行時(shí)間的比值。由表3、表4可見(jiàn),在不考慮噪聲影響和當(dāng)SNR=10 dB時(shí),對(duì)于重構(gòu)隨機(jī)合成的MMV模型塊稀疏信號(hào),BPMMPMMV算法的運(yùn)行時(shí)間明顯低于BA*OMPMMV、SMP-MMV和SMP-GMMV算法。

表3　無(wú)噪聲時(shí)BPMMPMMV分別與BA* OMPMMV、SMP-MMV、SMP-GMMV運(yùn)行時(shí)間的比值

表4　SNR=10 dB時(shí)BPMMPMMV與BA*OMPMMV、SMP-MMV、SMP-GMMV運(yùn)行時(shí)間的比值

3.2利用BPMMPMMV算法重構(gòu)多傳感器實(shí)測(cè)溫度信號(hào)

本節(jié)采用Intel Berkeley Research Lab真實(shí)傳感器網(wǎng)絡(luò)的實(shí)測(cè)溫度值進(jìn)行實(shí)驗(yàn)。選取小空間范圍內(nèi)的傳感器1、2、3、4、6、7、8、9、10和11這10個(gè)傳感器。將2004年3月1日到2004年3月7日內(nèi)傳感器測(cè)得的溫度值每隔3.5 min采樣一個(gè)點(diǎn),得到長(zhǎng)度為2 048的溫度信號(hào)。選取sym8小波基。將觀測(cè)矩陣構(gòu)造為元素符合高斯分布且每一行均經(jīng)過(guò)歸一化處理的隨機(jī)矩陣。

分別在不考慮噪聲影響和在信噪比SNR=10 dB、15dB、20 dB的情況下,比較BPMMPMMV、BA*OMPMMV、SMP-MMV、SMP-GMMV和OMPMMV這5種算法的聯(lián)合重建性能。表5給出了當(dāng)SNR=10 dB時(shí),5種算法NMSE值的對(duì)比情況。表6給出了當(dāng)SNR=10 dB時(shí),BPMMPMMV算法運(yùn)行時(shí)間分別與BA*OMPMMV、SMP-MMV和SMP-GMMV算法運(yùn)行時(shí)間的比值。

表5　SNR=10 dB時(shí)5種算法NMSE值的對(duì)比

由表5可見(jiàn),當(dāng)SNR=10 dB時(shí),對(duì)于重構(gòu)實(shí)際WSN測(cè)得的溫度信號(hào),適用于重構(gòu)塊稀疏信號(hào)的BPMMPMMV、BA*OMPMMV、SMP-MMV和SMP-GMMV算法的聯(lián)合重構(gòu)性能明顯優(yōu)于OMPMMV算法。比較BPMMPMMV、BA*OMPMMV、SMP-MMV和SMP-GMMV 4種算法可見(jiàn),BPMMPMMV算法的聯(lián)合重構(gòu)性能優(yōu)于BA*OMPMMV和SMP-MMV算法,而與SMP-GMMV算法基本相當(dāng)。然而,SMP-GMMV算法采用的是GMMV模型,即對(duì)不同信號(hào)采用不同的觀測(cè)矩陣,因此會(huì)增加觀測(cè)矩陣存儲(chǔ)與傳輸?shù)某杀尽?/p>

由表6可見(jiàn),當(dāng)SNR=10 dB時(shí),對(duì)于重構(gòu)實(shí)際WSN測(cè)得的溫度信號(hào),BPMMPMMV算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)低于BA*OMPMMV、SMP-MMV和SMP-GMMV算法。在無(wú)噪聲影響、SNR=15dB、20 dB等情況下進(jìn)行的實(shí)驗(yàn)也得到了相同的結(jié)論。

表6　SNR=10 dB時(shí)BPMMPMMV分別與BA*OMPMMV、SMP-MMV和SMP-GMMV運(yùn)行時(shí)間的比值

由上述實(shí)驗(yàn)結(jié)果可見(jiàn),從聯(lián)合重構(gòu)性能與運(yùn)行時(shí)間兩方面綜合考慮,與BA*OMPMMV、SMP-MMV、SMP-GMMV和OMPMMV算法相比,BPMMPMMV算法更適用于實(shí)現(xiàn)WSN小范圍內(nèi)多傳感器采集信號(hào)的聯(lián)合重構(gòu)。

4　結(jié)　論

本文針對(duì)MMP算法不能利用信號(hào)的塊稀疏結(jié)構(gòu)且迭代次數(shù)較多時(shí)產(chǎn)生極大數(shù)據(jù)量的問(wèn)題,提出了BPMMP算法,在獲得良好重建效果的基礎(chǔ)上,極大地降低了運(yùn)行時(shí)間。進(jìn)而,針對(duì)MMV問(wèn)題進(jìn)一步改進(jìn),提出了適用于在MMV模型下重構(gòu)塊稀疏信號(hào)的BPMMPMMV算法。利用合成信號(hào)與Intel Berkeley Research Lab實(shí)際WSN測(cè)得的溫度信號(hào)進(jìn)行的仿真實(shí)驗(yàn)表明,BPMMPMMV算法具有優(yōu)于BA*OMPMMV、SMP-MMV和OMPMMV算法的聯(lián)合重構(gòu)性能,并且其運(yùn)行時(shí)間顯著低于BA*OMPMMV、SMP-MMV和SMP-GMMV算法,更適用于WSN小范圍內(nèi)多傳感器采集數(shù)據(jù)的聯(lián)合重構(gòu)。

本文設(shè)計(jì)的BPMMP算法在固定的迭代層數(shù)之后,從每層搜索出的候選路徑集中去除固定比例的路徑。如何在迭代過(guò)程中適時(shí)地對(duì)搜索樹(shù)進(jìn)行適度修剪是一個(gè)需要進(jìn)一步研究的問(wèn)題。

[1] Baron D, Duarte M F, Sarvotham S, et al. An information-theoretic approach to distributed compressed sensing[C]∥Proc.ofthe43rdAllertonConferenceonCommunication,Control,andComputing, 2005: 814-825.

[2] Youness N, Hassan K. Energy preservation in large-scale wireless sensor network utilizing distributed compressive sensing[C]∥Proc.ofthe10thIEEEInternationalConferenceonWirelessandMobileComputing,NetworkingandCommunications, 2014: 251-256.

[3] Chen J, Huo X. Theoretical results on sparse representations of multiple measurement vectors[J].IEEETrans.onSignalProcessing, 2006, 54(12): 4634-4643.

[4] Davies M E, Eldar Y C. Rank awareness in joint sparse recovery[J].IEEETrans.onInformationTheory, 2012, 58(2): 1135-1146.

[5] Eldar Y C, Mishali M. Block-sparsity and sampling over a union of subspaces[C]∥Proc.ofthe16thInternationalConferenceonDigitalSignalProcessing, 2009: 1-8.

[6] Eldar Y C, Kuppinger P, Bolcskei H. Block-sparse signals: uncertainty relations and efficient recovery[J].IEEETrans.onSignalProcessing, 2010, 58(6): 3042-3054.

[7] Chen P, Wang C, Meng C. Block compressive sampling matching pursuit based on restricted isometry property[J].SystemsEngineeringandElectronics, 2015, 37(2): 239-245. (陳鵬, 王成, 孟晨. 基于約束等距的塊稀疏壓縮采樣匹配追蹤算法[J].系統(tǒng)工程與電子技術(shù), 2015, 37(2): 239-245.)

[8] Tian P W, Kang R Z, Yu H Y. Compressive sampling of non-uniform block sparse signals and the blind recovery algorithm[J].JournalofElectronics&InformationTechnology, 2013, 35(2): 445-450. (田鵬武, 康榮宗, 于宏毅. 非均勻塊稀疏信號(hào)的壓縮采樣與盲重構(gòu)算法[J].電子與信息學(xué)報(bào), 2013, 35(2): 445-450.)

[9] Lian Q S, Liu F, Chen S Z. A joint reconstruction algorithm for multiple sensor data based on block A*orthogonal matching pursuit[J].JournalofElectronics&InformationTechnology, 2013, 35(3): 721-727. (練秋生, 劉芳, 陳書(shū)貞. 基于塊 A*正交匹配追蹤的多傳感器數(shù)據(jù)聯(lián)合重構(gòu)算法[J].電子與信息學(xué)報(bào), 2013, 35(3): 721-727.)

[10] Ganesh A, Zhou Z. Separation of subspace-sparse signal: algorithms and conditions[C]∥Proc.oftheIEEEInternationalConferenceonAcoustics,Speech,andSignalProcessing, 2009: 3141-3144.

[11] Joshi A, Kannu P A. On recovery of block sparse signals from multiple measurements[C]∥Proc.oftheIEEEInternationalConferenceonAcoustics,Speech,andSignalProcessing, 2014: 7163-7167.

[12] Kwon S, Wang J, Shim B. Multipath matching pursuit[J].IEEETrans.onInformationTheory, 2014, 60(5): 2896-3001.

[13] Bodik P, Hong W, Guestrinc, et al. Intel Berkeley Lab WSN[EB/OL].[2015-6-28]. http:∥db.csail.mit.edu/labdata/labdata.html.

[14] Ding J, Chen L, Gu Y. Performance of orthogonal matching pursuit for multiple measurement vectors[C]∥Proc.oftheIEEEChinaSummitandInternationalConferenceonSignalandInformationProcessing, 2013: 67-71.

[15] Kim J M, Lee O K, Ye J C. Compressive MUSIC: revisiting the link between compressive sensing and array signal processing[J].IEEETrans.onInformationTheory, 2012, 58(1): 278-301.

[16] Gishkori S, Leus G. Compressed sensing for block-sparse smooth signals[C]∥Proc.oftheIEEEInternationalConferenceonAcoustic,SpeechandSignalProcessing, 2014: 4166-4170.

[17] Wimalajeewa T, Eldar Y C, Varshney P K. Subspace recovery from structured union of subspaces[J].IEEETrans.onInformationTheory, 2015, 61(4): 2101-2114.

[18] Wang Y G, Liu Z, Jiang W L, et al. Block sparse signal recovery with synthesized multitask compressive sensing[C]∥Proc.oftheIEEEInternationalConferenceonAcoustic,SpeechandSignalProcessing, 2014: 1030-1034.

Joint multi-signal reconstruction based on block pruning multipath matching pursuit

SI Jing-jing, HOU Xiao-lan, CHENG Yin-bo

(SchoolofInformationScienceandTechnology,YanshanUniversity,Qinhuangdao066004,China)

Considering the disadvantages of ignoring signal’s structured sparsity and the high complexity in high iterative layers in multipath matching pursuit (MMP), the block pruning multipath matching pursuit (BPMMP) is proposed to reconstruct the block-sparse signal. In this algorithm, an atomic block serves as a node in the path expansion, and branch pruning operation is introduced after a certain number of iterations. Thus, BPMMP reduces the data processing cost greatly. Moreover, for multiple measurement vector (MMV) problem, BPMMP for MMV (BPMMPMMV) is proposed. It can achieve joint signal reconstruction for multiple sensors within a small range in the wireless sensor network. Experimental results show that BPMMP outperforms MMP on the reconstruction performance, and BPMMPMMV achieves higher joint reconstruction performance than block A*orthogonal matching pursuit for MMV, subspace matching pursuit for MMV and orthogonal matching pursuit for MMV.

distributed compressed sensing (DCS); multiple measurement vector (MMV); block sparsity; multipath matching pursuit (MMP)

2015-09-23；

2016-02-21；網(wǎng)絡(luò)優(yōu)先出版日期：2016-07-05。

國(guó)家自然科學(xué)基金(61471313，61303128)；河北省自然科學(xué)基金(F2014203183)；河北省高等學(xué)?？茖W(xué)技術(shù)研究項(xiàng)目(Q2012087);燕山大學(xué)青年教師自主研究計(jì)劃(13LGB015)資助課題

TN 919.8

A

10.3969/j.issn.1001-506X.2016.09.05

司菁菁(1980-),女,副教授,博士,主要研究方向?yàn)閴嚎s感知、網(wǎng)絡(luò)編碼。

E-mail:sjj@ysu.edu.edn

候肖蘭(1988-),女,碩士研究生,主要研究方向?yàn)榉植际綁嚎s感知。

E-mail:houxiaolanqian@163.com

程銀波(1978-),男,講師,博士,主要研究方向?yàn)榉植际接?jì)算。

E-mail:cyb@ysu.edu.cn

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160705.1722.004.html