,,

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院,?？?570228)

0 概述

在無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)中,參數(shù)信號(hào)大都具有非穩(wěn)定性、不確定性以及大時(shí)滯等特性,導(dǎo)致傳統(tǒng)的修復(fù)方法如多項(xiàng)式遞推法、差分法、卡爾曼濾波法以及最小二乘法在數(shù)據(jù)恢復(fù)效果上并不理想。目前,壓縮感知理論[1]已經(jīng)逐漸被人們使用在信號(hào)恢復(fù)重建工作上,壓縮感知理論是一種別于傳統(tǒng)信號(hào)壓縮理論的一種新理論,它利用信號(hào)的稀疏特性,通過非線性重建的算法來重建信號(hào),并且它能使壓縮過程與采樣過程同時(shí)進(jìn)行,而在壓縮比較大時(shí)也能夠獲得較為理想的恢復(fù)效果。

信號(hào)如何進(jìn)行稀疏表示,測(cè)量矩陣如何構(gòu)造以及重構(gòu)算法如何設(shè)計(jì)是壓縮感知理論的3個(gè)核心內(nèi)容。信號(hào)具有可壓縮性能是壓縮感知理論中的必須要求,而信號(hào)的稀疏表示則是該要求的具體體現(xiàn)。想要獲得較好的可壓縮性,需要依賴稀疏字典的設(shè)計(jì),而為了得到與原始信號(hào)相匹配的優(yōu)化字典,需用應(yīng)用一定的學(xué)習(xí)算法來彌補(bǔ)先驗(yàn)知識(shí)的不足。壓縮采樣后獲取的信息量受到測(cè)量矩陣構(gòu)造的影響,測(cè)量矩陣的有限等距特性[2](Restricted Isometry Property,RIP)是測(cè)量矩陣構(gòu)造的必要條件,在此條件的基礎(chǔ)上專家學(xué)者提出了更廣泛的構(gòu)造原則,在不同的編碼方式與構(gòu)造方式的情況下,都能夠幾乎精確地重構(gòu)原始信號(hào),并且重構(gòu)的信號(hào)具有唯一性。

原始信號(hào)經(jīng)過壓縮采樣,依舊能夠保留其重構(gòu)所必要的信息,但光憑這些信息是遠(yuǎn)遠(yuǎn)不夠的。信號(hào)重構(gòu)問題一直以來就是個(gè)NP難的問題,為了讓信號(hào)重建成為可能,利用了在重構(gòu)過程中,信號(hào)的稀疏性以及信號(hào)具有有限個(gè)的非零系數(shù)這2個(gè)特性。隨著壓縮感知理論的推廣普及以及深入研究,目前出現(xiàn)了各種優(yōu)化的重構(gòu)算法,主要為凸優(yōu)化算法和貪婪算法等,凸優(yōu)化算法包括基追蹤算法(Basis Pursuit,BP)[3]、梯度投影算法[4]、內(nèi)點(diǎn)迭代法[5]等,該類算法在重構(gòu)精度上較有優(yōu)勢(shì)但其運(yùn)算時(shí)間過長(zhǎng)。較為常見的貪婪算法有正交匹配追蹤(Orthogonal Matching Pursuit,OMP)[6]、分段正交匹配追蹤(Stagewise Orthogonal Matching Pursuit,StOMP)[7]、正則化正交匹配追蹤 (Regularized Orthogonal Matching Pursuit,ROMP)[8]、壓縮采樣匹配追 (CompressiveSampling Matching Pursuit,CoSaMP)[9]、子空間追蹤(Subspace Pursuit,SP)[10]和稀疏度自適應(yīng)匹配追蹤 (Sparsity Adaptive Matching Pursuit,SAMP)[11]等,該類算法在運(yùn)算速度上有較好的優(yōu)勢(shì),但其運(yùn)算的精度有限。由于信號(hào)重構(gòu)是用于無線傳感器網(wǎng)絡(luò)這種實(shí)際應(yīng)用中,數(shù)據(jù)需要具有實(shí)時(shí)性,因此數(shù)據(jù)的恢復(fù)重構(gòu)在運(yùn)算速度方面較為重要,而如何在確保運(yùn)算速度的情況下提升數(shù)據(jù)恢復(fù)的精度是本文研究的主要內(nèi)容。

在上述貪婪算法中,除了SAMP算法以外,其余算法需要預(yù)先假設(shè)信號(hào)是稀疏的并規(guī)定稀疏度。然而,在實(shí)際的信號(hào)恢復(fù)重構(gòu)問題中,稀疏度往往很難獲得。因此,本文提出一種改進(jìn)SAMP算法,并借助多屬性間存在的相關(guān)性來協(xié)助數(shù)據(jù)恢復(fù)。

1 壓縮感知理論及其重構(gòu)算法

1.1 壓縮感知理論

(1)

其中,θ被稱作投影系數(shù)向量,θ=ΨTX。如果θ的l0范數(shù)遠(yuǎn)遠(yuǎn)小于N,即非零項(xiàng)有限且很少,那么可以稱信號(hào)向量X在矩陣Ψθ上是稀疏的,即信號(hào)向量X是可壓縮的,信號(hào)向量X的稀疏度用K=‖θ‖l0來表示,其中‖·‖l0表示向量的l0范數(shù)。

在信號(hào)稀疏表示后,需要確定隨機(jī)測(cè)量矩陣ΦM×N,該隨機(jī)測(cè)量矩陣需要擁有RIP特性,并且跟信號(hào)的稀疏基不相關(guān)。確定隨機(jī)測(cè)量矩陣之后,便可對(duì)信號(hào)X進(jìn)行壓縮采樣,其壓縮采樣過程表示為:

Y=ΦM×NX=ΦM×NΨθ

(2)

其中,M為隨機(jī)測(cè)量個(gè)數(shù),向量Y為測(cè)量信號(hào)向量。隨機(jī)測(cè)量個(gè)數(shù)M遠(yuǎn)遠(yuǎn)小于N,即信號(hào)的隨機(jī)測(cè)量過程實(shí)則是對(duì)信號(hào)的壓縮過程。信號(hào)進(jìn)行隨機(jī)測(cè)量后,把得到的結(jié)果用l0范數(shù)優(yōu)化,重新把原始信號(hào)向量X進(jìn)行重構(gòu):

min‖θ‖l0s.t.Y=ΦM×NΨθ

(3)

然而根據(jù)統(tǒng)計(jì)理論和組合優(yōu)化理論得知,組合優(yōu)化是一個(gè)NP問題,當(dāng)N很大時(shí),數(shù)值上無法有效實(shí)現(xiàn),且抗噪聲能力很差,因此,由一些研究者證明l0約束優(yōu)化問題可以轉(zhuǎn)為數(shù)值上容易處理l1約束的凸優(yōu)化問題:

min‖θ‖l1s.t.Y=ΦM×NΨθ

(4)

其中,‖·‖l1表示向量的l1范數(shù)。基于l1范數(shù)凸優(yōu)化算法的系數(shù)重構(gòu)模型一般采用:

min‖X‖l1s.t. ‖Y-ΦM×NX‖l2≤σ

(5)

其中,σ為殘差,‖·‖l2表示向量的l2范數(shù)。即對(duì)式(5)進(jìn)行多次重復(fù)迭代,設(shè)定一個(gè)合理的殘差上限,當(dāng)?shù)蟮臍埐钚∮诘扔跉埐钌舷迺r(shí),用最小二乘法便可求出x的廣義解。

1.2 SAMP算法

鑒于大部分算法都需要已知信號(hào)的稀疏度,而實(shí)際問題中稀疏度往往是未知的,SAMP算法便可很好地解決這種問題。該算法在稀疏度無法確定時(shí),設(shè)定初始步長(zhǎng)與初始稀疏度,在每次迭代后可以得出一個(gè)殘差值,把得出的殘差值進(jìn)行對(duì)比,從而更新步長(zhǎng)以及稀疏度,如此反復(fù)得出稀疏的一個(gè)最優(yōu)估計(jì),實(shí)現(xiàn)信號(hào)的壓縮重構(gòu)。但是該算法仍然有一定的缺陷,如果設(shè)定稀疏度的初始值相對(duì)于實(shí)際值過于偏小,便會(huì)導(dǎo)致迭代次數(shù)增多,即會(huì)影響到運(yùn)算時(shí)間,在實(shí)際應(yīng)用中會(huì)有比較大的影響。如果設(shè)定步長(zhǎng)的初始值相對(duì)于實(shí)際值過于偏大,那么會(huì)導(dǎo)致可能無法獲得真實(shí)稀疏度的值,使結(jié)果存在一定的誤差,從而降低了重構(gòu)精度。因此,需要一種改進(jìn)的算法來解決上述的問題。

2 基于壓縮感知和多屬性協(xié)助的改進(jìn)算法

2.1 改進(jìn)的SAMP算法

為了解決SAMP算法帶來的缺陷,將原稀疏信號(hào)向量X進(jìn)行分塊得到多個(gè)子信號(hào),把分出的子信號(hào)逐一重構(gòu)再合并得出整體的重構(gòu)信號(hào)。由于原始稀疏信號(hào)向量X稀疏度越低在運(yùn)用同樣重構(gòu)算法的前提下重構(gòu)精度越高[12]。如式(6)所示,利用信號(hào)整體是稀疏的,因此,局部也是稀疏的特性,將信號(hào)向量X分為多個(gè)相同長(zhǎng)度的子信號(hào),每一個(gè)子信號(hào)作為一個(gè)統(tǒng)一體來進(jìn)行運(yùn)算。

(6)

由文獻(xiàn)[13]中的理論得,當(dāng)觀測(cè)矩陣ΦM×N滿足RIP性質(zhì)時(shí),可得如下公式:

(7)

其中,F0表示迭代的索引集合的初始值。利用命題成立則其逆否命題也成立的性質(zhì),可得:

(8)

因此,在K0初始化后如果滿足式(8),則K0=K0+s,其中,s為步長(zhǎng),更新F0。重復(fù)式(8)直至條件不成立為止。將此算法命名為分段稀疏度自適應(yīng)匹配追蹤(Stagewise Sparsity Adaptive Matching Pursuit,SSAMP)算法。

2.2 多參數(shù)協(xié)助的改進(jìn)算法

無線傳感器網(wǎng)絡(luò)獲得的參數(shù)屬性一般均為某一系統(tǒng)中的屬性,而系統(tǒng)中的屬性間往往存在一定的聯(lián)系,比如在自然環(huán)境下,室內(nèi)與室外的溫度與濕度間就具有一定的線性關(guān)系[14]。然而這些關(guān)系較為復(fù)雜,在絕多數(shù)情況是無法用一個(gè)簡(jiǎn)單的函數(shù)式子去把它們表示出來。因此,本文使用聯(lián)合稀疏分解的方法把多種參數(shù)的信號(hào)融合并提出共同分量和特征分量2個(gè)部分的方法來表現(xiàn)無線傳感器網(wǎng)絡(luò)中不同屬性間的相關(guān)性。若共同分量比之總體所占比例越高,則這些屬性間的相關(guān)性也就越高。

通過研究信號(hào)群中信號(hào)內(nèi)部和信號(hào)之間的相關(guān)性以及借助分布式信源編碼的思想,文獻(xiàn)[15]針對(duì)不同領(lǐng)域與用途提出了3種聯(lián)合稀疏模型(Joint Sparsity Model,JSM),其中,JSM-1模型十分適合應(yīng)用于無線傳感器網(wǎng)絡(luò)。

假設(shè)在無線傳感器網(wǎng)絡(luò)中多種不同的傳感器組成一個(gè)傳感器群,每個(gè)傳感器群由一個(gè)傳感器節(jié)點(diǎn)來接收數(shù)據(jù)并發(fā)送到匯聚節(jié)點(diǎn)。則在這個(gè)過程中令傳感器節(jié)點(diǎn)一共有P個(gè)以及N個(gè)傳感器組成的傳感器群,即N個(gè)參數(shù)屬性。由于在監(jiān)測(cè)周期內(nèi)有Q個(gè)時(shí)間隙,每個(gè)時(shí)間隙內(nèi)為數(shù)據(jù)采集后各個(gè)節(jié)點(diǎn)采集到的信號(hào)向量的長(zhǎng)度L,因此可以把采集到的數(shù)據(jù)用Q×P的矩陣的形式表示:

(9)

矩陣A的每一列矩陣Xi,i=1,2,…,P表示在該時(shí)間隙內(nèi),一個(gè)傳感器節(jié)點(diǎn)得到的信號(hào)向量,矩陣A的每一行矩陣Xj,j=1,2,…,Q表示在同一采樣時(shí)刻,所有傳感器節(jié)點(diǎn)得到的采樣信息。

在匯聚節(jié)點(diǎn)進(jìn)行稀疏變換可得:

Xi=Ψθ,i=1,2,…,P

(10)

則正交基矩陣Ψ為Xi,i=1,2,…,P的稀疏基。反變換后,寫成矩陣的形式得:

(11)

其中,矩陣B為稀疏變換后系數(shù)稀疏構(gòu)成的矩陣,矩陣θi,i=1,2,…,P表示矩陣B的第i列,矩陣θj,j=1,2,…,Q表示矩陣B的第j行。

利用JSM-1模型進(jìn)行聯(lián)合稀疏表示,則矩陣θi可以寫成另一種形式:

θi=Δc+Δi,i=1,2,…,P

(12)

為了使聯(lián)合稀疏表示后稀疏度達(dá)到最小值,因此問題轉(zhuǎn)化為求下式l0范數(shù)的最小化:

min(‖Δc‖l0+‖Δ1‖l0+…+‖ΔP‖l0)

(13)

設(shè)矩陣Δc(n),n=1,2,…,Q為共同分量的第n個(gè)元素,因此,如若求解稀疏度最小時(shí)對(duì)應(yīng)的共同分量,只需令矩陣Δc(n)等于矩陣B的第n行的P個(gè)元素中出現(xiàn)頻數(shù)最大的元素。

聯(lián)合稀疏后的信號(hào)群矩陣變成如下形式:

(14)

將式(14)向量化,按列堆棧成一個(gè)Q(P+1)×1的列向量得:

(15)

設(shè)‖Δc‖l0=Kc,‖Δi‖l0=Ki,i=1,2,…,P,由共同分量和特征分量的稀疏度,由式(3)可以確定矩陣Δc,Δ1,…,ΔP所需的觀測(cè)值個(gè)數(shù)Mc,M1,…,MP,其對(duì)應(yīng)的隨機(jī)測(cè)量矩陣為Φc,Φ1,…,ΦP,則測(cè)量值向量可以表示為:

Yc=ΦcΔc

Y1=Φ1Δ1

?

YP=ΦPΔP

(16)

(17)

將以上的算法命名為多屬性壓縮感知(Multipara-meter Compressed Sensing,MCS)算法。

3 算法的實(shí)現(xiàn)步驟

輸入

1)觀測(cè)矩陣Φ

2)傳感矩陣Z=ΦΨ

3)觀測(cè)向量X

4)初始步長(zhǎng)s

輸出

矩陣分塊算法[9]如下:

For id_x=1:ceil(a/size);

For id_y=1:ceil(b/size);

XX= X((id_x-1)·size+1:id_x·size,(id_y-1)·

size+1:id_y·size);

X1=ww·sparse(XX)·wwT;x1=full(X1);

y=ΦX1;

For i=1:size;

信號(hào)重構(gòu)步驟如下:

4)令Ck=Ft-1∪Sk,Zt={Zj}(for allj∈Ck);

5)求向量X=Ztθt的最小二乘解:

8)如果殘差rtnew=0,那么停止迭代第3)步～第8)步進(jìn)入第9)步;

(1)如果‖rtnew‖2≥‖rt-1‖2,更新步長(zhǎng)I=I+s,返回第3)步繼續(xù)迭代;

(2)如果前面2個(gè)條件都不滿足,那么Ft=F,rt=rtnew,t=t+1,如果t≤P停止迭代進(jìn)入第9)步,否則返回第3)步繼續(xù)迭代;

矩陣分塊算法如下:

X2(:,i)=x;

End

X3((id_x-1)·size+1:id_x·size,(id_y-1)·

size+1:idid_y·size)=wwT·sparse(X2)·ww

End

End

在上述的步驟中,a是x的行數(shù),b是x的列數(shù),size是分塊的大小,?是空集符號(hào),∪是并集運(yùn)算符號(hào),〈·,·〉是2個(gè)向量求內(nèi)積,abs[·]是求模值,即絕對(duì)值,rt表示迭代殘差,t表示迭代的次數(shù),Ft表示t次迭代的列序號(hào)集合(元素個(gè)數(shù)為I,I等于整數(shù)倍步長(zhǎng)s),Zj表示矩陣Z的第j列,Zt={Zj}(for allj∈Ck)表示通過列序號(hào)集合Ck選出的矩陣Z的列集合(設(shè)矩陣的列數(shù)為It),θt為It×1的列向量。

4 實(shí)驗(yàn)仿真

實(shí)驗(yàn)1SSAMP算法的信號(hào)重構(gòu)效果

本文實(shí)驗(yàn)采用信號(hào)長(zhǎng)度L=256的稀疏信號(hào),觀測(cè)矩陣是壓縮維度為128的高斯隨機(jī)矩陣,非零系數(shù)的大小服從高斯分布。圖1是通過SSAMP算法重構(gòu)的信號(hào)與原始信號(hào)對(duì)比圖,其恢復(fù)殘差ans=1.285e-14,運(yùn)行時(shí)間為0.070 570 s。由于信號(hào)為隨機(jī)生成,每次結(jié)果均不相同,但經(jīng)過多次實(shí)驗(yàn),其恢復(fù)殘差均滿足ans≤3e-14。

圖1 SSAMP算法重構(gòu)信號(hào)效果

實(shí)驗(yàn)2MCS- SSAMP算法的信號(hào)重構(gòu)效果

首先實(shí)驗(yàn)觀測(cè)稀疏度k對(duì)重構(gòu)精度的影響,規(guī)定對(duì)每一個(gè)觀測(cè)值重復(fù)測(cè)驗(yàn)m=128次,得出稀疏度10≤k≤70時(shí)各個(gè)不同算法對(duì)于重構(gòu)精度的影響,如圖2所示。實(shí)驗(yàn)證明,隨著稀疏度k的降低,各個(gè)算法的重構(gòu)精度會(huì)不斷提高,而MCS-SSAMP算法提高的速度明顯快于其他算法,并且當(dāng)稀疏度在k=52時(shí),該算法就已經(jīng)可以達(dá)到重構(gòu)成功的水平,而其他算法達(dá)到重構(gòu)成功水平所需要的稀疏度區(qū)間均小于MCS-SSAMP算法。

圖2 稀疏度與信號(hào)重構(gòu)精度的關(guān)系

其次實(shí)驗(yàn)觀測(cè)測(cè)量數(shù)m對(duì)重構(gòu)精度的影響,令稀疏度k=20,得出測(cè)量數(shù)50≤m≤100時(shí),各個(gè)不同算法對(duì)于重構(gòu)精度的影響,如圖3所示。實(shí)驗(yàn)證明,隨著測(cè)量數(shù)m的增加,各個(gè)算法的重構(gòu)精度會(huì)不斷提高,而MCS-SSAMP算法提高的速度明顯快于其他算法,并且當(dāng)測(cè)量數(shù)m=68時(shí),該算法就已經(jīng)可以達(dá)到重構(gòu)成功的水平,而其他算法達(dá)到重構(gòu)成功水平所需要的測(cè)量數(shù)區(qū)間均小于MCS-SSAMP算法。

圖3 測(cè)量數(shù)與信號(hào)重構(gòu)精度的關(guān)系

5 結(jié)束語

本文研究水產(chǎn)養(yǎng)殖中數(shù)據(jù)的恢復(fù)問題,提出一種數(shù)據(jù)恢復(fù)算法。采用原始稀疏信號(hào)分塊重構(gòu),使用最佳的匯聚節(jié)點(diǎn)確定出共同分量,并進(jìn)行聯(lián)合編碼,降低每輪迭代當(dāng)中要處理的信號(hào)稀疏度,從而用更少的測(cè)量值實(shí)現(xiàn)信號(hào)群的精確重構(gòu)。改進(jìn)的算法在運(yùn)算時(shí)間上,由于對(duì)信號(hào)的初始稀疏度做了初始估計(jì),因此可以有效避免稀疏度的初始值相對(duì)于實(shí)際值過于偏小時(shí),導(dǎo)致迭代次數(shù)增多的問題。實(shí)驗(yàn)結(jié)果表明,該算法降低了運(yùn)算的時(shí)間,使運(yùn)算更加高效,測(cè)定精度更高。今后將著重于研究用何種算法選取效率比較高的次屬性,以進(jìn)行協(xié)助數(shù)據(jù)恢復(fù)的工作。

[1] DONOHO D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[3] CHEN S S,DONOHO D L,SAUNDERS M A.Atomic decomposition by basis pursuit[J].SIAM Review,2006,43(1):129-159.

[4] APPLEBAUM L,HOWARD S D,SEARLE S,et al.Chirp sensing codes:deterministic compressed sensing measure-ments for fast recovery[J].Applied & Computational Harmonic Analysis,2009,26(2):283-290.

[5] ROMBERG J.Compressive sensing by random convolution[J].SIAM Journal on Imaging Sciences,2009,2(4):1098-1128.

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

[7] DONOHO D L,TSAIG Y,DRORI I,et al.Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2012,58(2):1094-1121.

[8] NEEDELL D,VERSHYNIN R.Signal recovery from incomplete and inaccurate measurements via ROMP[J].IEEE Journal of Selected Topics in Signal Processing,2010,4(2):310-316.

[9] NEEDELL D,TROPP J A.CoSaMP:iterative signal recovery from incomplete and inaccurate samples[J].Applied & Computational Harmonic Analysis,2008,26(3):301-321.

[10] DAI W,MILENKOVIC O.Subspacepursuit for compressive sensing signal reconstruction[J].IEEE Transactions on Information Theory,2009,55(5):2230-2249.

[11] DO T T,LU G,NGUYEN N,et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]//Proceedings of Asilomar Conference on Signals,Systems,and Computers.Washington D.C.,USA:IEEE Press,2008:581-587.

[12] 閆 鵬,張志賢,王阿川.基于壓縮感知SAMP算法的改進(jìn)[J].森林工程,2014,30(3):80-83.

[13] 楊 成,馮 巍,馮 輝,等.一種壓縮采樣中的稀疏度自適應(yīng)子空間追蹤算法[J].電子學(xué)報(bào),2010,38(8):1914-1917.

[14] LAWRENCE M G.The relationship between relative humidity and the dewpoint temperature in moist air:a simple conversion and applications[J].Bulletin of the American Meteorological Society,2010,86(2):225-233.

[15] BARON D,DUARTE M F,WAKIN M B,et al.Distributed compressive sensing[C]//Proceedings of International Conference on Acoustics,Speech and Signal Processing.Washington D.C.,USA:IEEE Press,2009:2886-2889.