基于量子粒子群優(yōu)化算法的壓縮感知數(shù)據(jù)重構(gòu)方法*

劉洲洲,李艷平

(1.西安航空學(xué)院,西安 710077;2.菏澤學(xué)院計算機與信息工程系,山東 菏澤 274015)

?

基于量子粒子群優(yōu)化算法的壓縮感知數(shù)據(jù)重構(gòu)方法*

劉洲洲1*,李艷平2

(1.西安航空學(xué)院,西安 710077;2.菏澤學(xué)院計算機與信息工程系,山東 菏澤 274015)

針對傳感器監(jiān)測對象特點,將壓縮感知理論應(yīng)用于數(shù)據(jù)壓縮過程以降低通信能耗,并根據(jù)現(xiàn)有壓縮感知數(shù)據(jù)重構(gòu)算法存在的重構(gòu)精度受稀疏度影響較大的缺點,在分析了壓縮感知數(shù)據(jù)重構(gòu)原理后,提出了將原始信號按固定長度進(jìn)行分幀處理以減少算法解空間的數(shù)量,并將量子理論中的編碼方式應(yīng)用于粒子群優(yōu)化算法,提出了基于量子粒子群優(yōu)化算法的壓縮感知數(shù)據(jù)重構(gòu)方法QP-CSDR。算法根據(jù)傳感器監(jiān)測對象特點,從統(tǒng)計學(xué)角度出發(fā)對粒子群優(yōu)化算法中的粒子初始位置及粒子群更新方式加以改進(jìn),以提高數(shù)據(jù)重構(gòu)精度。仿真實驗結(jié)果表明,在稀疏度小于50的條件下,QP-CSDR算法相對已有算法在重構(gòu)精度方面性能提升20%～40%,該算法已應(yīng)用于微地震及音頻監(jiān)測系統(tǒng)中,經(jīng)實際檢驗算法在保證數(shù)據(jù)精度的前提下延長系統(tǒng)壽命2倍～4倍左右。

量子理論;粒子群優(yōu)化算法;壓縮感知;數(shù)據(jù)重構(gòu)

壓縮感知是目前數(shù)據(jù)壓縮的重點研究方向,能夠以高壓縮比對數(shù)據(jù)進(jìn)行壓縮,并通過數(shù)據(jù)重構(gòu)算法對數(shù)據(jù)實現(xiàn)重構(gòu)。國外對如何將壓縮感知應(yīng)用于無線傳感器網(wǎng)絡(luò)及相關(guān)數(shù)據(jù)重構(gòu)方法進(jìn)行了大量研究[1-2]。數(shù)據(jù)重構(gòu)算法的關(guān)鍵問題在于如何快速的、準(zhǔn)確的從已知的低維數(shù)據(jù)中恢復(fù)出高維數(shù)據(jù)。目前壓縮感知數(shù)據(jù)重構(gòu)算法主要分為兩類[3]:第1類算法則是基于最小化l1范數(shù)的算法,包括基追蹤算法BP(Basis Pursuit)[4],線性規(guī)劃算法LP(Linear Programming)[5]等。這類算法具有重建精度高的優(yōu)點,但其算法的復(fù)雜度較高,且執(zhí)行效率低,使用性較差;第2類是基于最小化l0范數(shù)的方法,即貪婪算法,包括正交匹配追蹤算法OMP(Orthogonal Matching Pursuit)[6]、正則化正交匹配算法ROMP(Regularized Orthogonal Matching Pursuit)[7]、壓縮采樣匹配追蹤算法CoSaMP(Compressive Sampling Matching Pursuit)[8]、迭代硬閾值算法IHT(Iterative Hard Thresholding)[9]、基于感知字典的迭代硬閾值算法SDIHT(Sending Dictionary-based Iterative Hard Thresholding)[10]、基于混沌量子免疫克隆算法的正交匹配算法OMP-QICA(Orthogonal Matching Pursuit based on Quantum-inspired Immune Clonal)[11]、基于遺傳算法的壓縮感知重構(gòu)算法[12]、稀疏度K自適應(yīng)的稀疏自適應(yīng)匹配追蹤算法SAMP(Sparsity Adaptive Matching Pursuit)[13]等,這類算法主要通過迭代更新當(dāng)前估計來優(yōu)化信號恢復(fù)情況,在原始信號稀疏度較小的情況下具有很好的重構(gòu)精度及重構(gòu)速度,但對于稀疏度較高的信號重構(gòu)問題卻無能為力。

粒子群優(yōu)化算法PSO(Particle Swarm Optimization)是目前國內(nèi)外的研究熱點[14-16],在問題尋優(yōu)的過程中要比其他經(jīng)典算法具有更好的優(yōu)勢及可行性,應(yīng)用于N-P完全問題,PSO算法也取得了比以往算法更好的效果。盡管PSO算法具有自身的優(yōu)勢,但在實際應(yīng)用中還是常出現(xiàn)陷入局部極值等現(xiàn)象。應(yīng)用于壓縮感知數(shù)據(jù)重構(gòu)過程中常出現(xiàn)適應(yīng)度較低但重構(gòu)誤差極大的情況。

針對這些不足,將量子免疫克隆理論帶入粒子群優(yōu)化算法,提出基于量子理論的粒子群優(yōu)化算法QP-CSDR(Quantum-inspired immune clonal based Particle Swarm Optimization in Compressed Sensor Data Reconstruction)并將其應(yīng)用于壓縮感知數(shù)據(jù)重構(gòu)過程中。旨在利用量子免疫克隆算法中的種群生成方法以及種群更新方法來實現(xiàn)種群擴張,為粒子群優(yōu)化算法提供更廣泛、更豐富的粒子位置,擴大了搜索空間,提高了局部搜索能力,避免算法陷入局部最優(yōu)出現(xiàn)早熟現(xiàn)象。

1 數(shù)據(jù)重構(gòu)算法

1.1 固定長度分幀

固定長度分幀方式就是將原始長信號按照固定的數(shù)據(jù)長度分為若干幀。假設(shè)信號采集端采集的原始信號長度為N,則按算法設(shè)定的幀長度n將原始信號分為frame=ceil(N/n)個幀,每個幀內(nèi)包含的非零元素個數(shù)不等。舉例說明:

假設(shè)原始信號x為:

0 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0

其原始信號長度為30,按每幀長度為5個數(shù)據(jù)分幀,則可分為以下6個幀:

0 0 0 1 1 | 1 0 1 0 1| 0 1 0 0 1 | 0 0 0 1 0 | 1 1 0 1 0| 0 1 0 0 0

這種方法的特點是每幀的長度相同,而稀疏度不同。

(1)

則根據(jù)概率論相關(guān)知識可知:其重建概率為:

(2)

(3)

以上述數(shù)據(jù)為例,表1顯示未分幀及分幀后的原始信號x中非零元素位置組合數(shù)量(為計算簡便,這里假設(shè)數(shù)據(jù)為均勻分布):

表1 固定長度分幀前后非零元素位置組合數(shù)量

可以看出,較短的分幀長度會降低組合數(shù)量,但在實際過程中會因為分幀長度過短導(dǎo)致幀數(shù)量增加,導(dǎo)致通信包數(shù)量急劇增加,提高了通信開銷,造成網(wǎng)絡(luò)擁塞,使分幀方法的實用性降低。而當(dāng)n取值過大時,雖然能夠減少通信包數(shù)量,降低通信開銷,但也會造成非零元素位置組合數(shù)量急劇增加,降低了數(shù)據(jù)的重構(gòu)概率。

1.2 改進(jìn)的量子粒子群優(yōu)化算法

假設(shè)初始狀態(tài)下,PSO系統(tǒng)中的每個粒子的位置不能確定,每個粒子位置的量子位狀態(tài)是隨機的,可以為0或1,也可為0到1間的任意隨機數(shù),其狀態(tài)表示為公式:

|Ψ〉=α|0〉+β|1〉

(4)

式中:α,β表示相應(yīng)狀態(tài)出現(xiàn)概率的兩個復(fù)數(shù),其關(guān)系為α2+β2=1。

具有m個量子比特位的粒子群可以描述為式(5):

(5)

式中:t表示種群代數(shù)。結(jié)合信號重構(gòu)的應(yīng)用實際考慮,m表示數(shù)據(jù)長度。規(guī)模為n的粒子種群表示為:

Q(t)={q1,q2,…,qn}

Q(t)即為信號重構(gòu)的解空間。

從統(tǒng)計學(xué)角度看,傳感器監(jiān)測的物理對象特征多服從正態(tài)分布,因此在理論中不應(yīng)當(dāng)僅簡單的假設(shè)為均勻分布,設(shè)其幅值xi∈[min,max],可設(shè)其位置的概率密度函數(shù)為式(6):

(6)

式中:αi為隨機數(shù),則粒子的初始化位置xi編碼規(guī)則如式(7):

xi=0.5×[max(1+T(αi))+min(1-T(αi))]

(7)

粒子的當(dāng)前最優(yōu)位置Pi的更新及速度的更新方式與經(jīng)典PSO算法中相應(yīng)參數(shù)的更新方式完全相同,即:

(8)

(9)

式中:f(·)為目標(biāo)函數(shù),在數(shù)據(jù)重構(gòu)算法中,將式(3)作為目標(biāo)函數(shù),通過不斷生成解x并與壓縮后數(shù)據(jù)Y進(jìn)行比較,從而不斷逼近原始數(shù)據(jù)。

量子粒子群算法中,當(dāng)長時間搜索不到全局最優(yōu)解時,種群需要進(jìn)行更新,這里我們借鑒全干擾交叉操作。假設(shè)一個種群包含5個長度為8的抗體,其具體交叉方法見表2。

表2 全干擾交叉操作

下面給出基于QP-CSDR算法壓縮感知數(shù)據(jù)重構(gòu)方法的執(zhí)行步驟。

1.3 數(shù)據(jù)重構(gòu)過程

本文提出的基于量子粒子群優(yōu)化的壓縮感知數(shù)據(jù)重構(gòu)算法流程圖如圖1所示。

圖1 算法流程圖

算法具體過程如下:

①將原始數(shù)據(jù)按長度n進(jìn)行分幀處理。通過遍歷算法記錄各幀稀疏度spratio;②在問題空間中,根據(jù)式(7)及原始信號稀疏度spratio初始化粒子群中各粒子的位置,使得粒子位置的稀疏度與原始信號稀疏度相同;③根據(jù)式(3)計算粒子的當(dāng)前適應(yīng)度,并與前一次迭代的適應(yīng)度值進(jìn)行比較,若當(dāng)前適應(yīng)度值小于前一次迭代的適應(yīng)度值,則根據(jù)粒子的位置更新為粒子當(dāng)前的最優(yōu)位置;④根據(jù)式(9)計算群體當(dāng)前的全局最優(yōu)位置;⑤比較當(dāng)前全局最優(yōu)位置與前一次迭代的全局最優(yōu)位置,若當(dāng)前全局最優(yōu)位置更好,則群體的全局最優(yōu)位置更新為當(dāng)前值;⑥根據(jù)式(8)、式(9)計算隨機點的速度及新位置;⑦若迭代次數(shù)達(dá)到一定閾值后,適應(yīng)度值仍未達(dá)到要求,則使用全干擾交叉方式,將粒子位置進(jìn)行全局交叉,然后重新計算全局最優(yōu)值及局部最優(yōu)值;⑧重復(fù)步驟②～步驟⑥,直至滿足一定的結(jié)束條件;⑨將所有重構(gòu)信號按幀序列組合完整的重構(gòu)信號。

2 實驗及分析

試驗場地選擇在秦始皇帝陵博物院K9801號坑旁,監(jiān)測對象為微地震信號。為使結(jié)果更加清晰,同一實驗地點處布設(shè)兩個硬件結(jié)構(gòu)相同的無線傳感器節(jié)點,一個傳輸未壓縮信號,另一個傳輸壓縮信號。將兩類數(shù)據(jù)導(dǎo)入計算機,并通過MATLAB運行程序?qū)χ貥?gòu)的壓縮信號進(jìn)行評估,并同時監(jiān)測節(jié)點的工作時長。

2.1 分幀結(jié)果分析

固定長度分幀的實驗結(jié)果如圖2所示。

圖2 N=5時的數(shù)據(jù)重構(gòu)結(jié)果

當(dāng)N=5時,原始數(shù)據(jù)共分為40個幀,信號壓縮比為200∶59,近乎達(dá)到3∶1。考慮通信中,每幀數(shù)據(jù)包需要額外增加2個字節(jié)原始幀長度和稀疏度信息,原始數(shù)據(jù)長度為400byte,壓縮后數(shù)據(jù)長度為118byte,額外通信開銷為80byte,實際數(shù)據(jù)壓縮比率為198∶400=0.495。重建信號的精度為98.5%。可以看出,由于每個幀內(nèi)僅有5個數(shù)據(jù),因此其重構(gòu)精度大大提高,QP-CSDR算法能夠?qū)?shù)據(jù)進(jìn)行高精度重構(gòu)。但N=5時分幀數(shù)量過多,通信開銷較大,因此實際應(yīng)用中效果較差。

如圖3所示,當(dāng)N=10時,原始數(shù)據(jù)共分為20個幀,信號壓縮比為200∶59,約為3∶1。原始信號長度為400byte,壓縮后信號長度為118byte,考慮通信中,每幀數(shù)據(jù)包需要額外增加兩個字節(jié)原始幀長度和稀疏度信息,額外通信開銷為40byte,實際數(shù)據(jù)包長度壓縮比率為158∶400=0.395。重建信號的精度為90%。可以看出,幀長度N=10時,算法的重構(gòu)精度有所下降,主要是因為重構(gòu)解空間數(shù)量較多,算法全局搜索能力下降所影響,N=10時的分幀數(shù)量有所減少,因此額外通信開銷降低。

圖3 N=10時的數(shù)據(jù)重構(gòu)結(jié)果

如圖4所示當(dāng)N=20時,原始數(shù)據(jù)共分為10個幀,信號壓縮比為200∶66,約為3.3∶1?？紤]通信中,每幀數(shù)據(jù)包需要額外增加兩個字節(jié)原始幀長度和稀疏度信息,額外通信開銷為20byte,實際數(shù)據(jù)包長度壓縮比率為142∶400=0.355。重建信號的精度為87%。可以看出,N=20時雖然額外通信開銷很少,但其數(shù)據(jù)重構(gòu)精度也隨之下降,難以達(dá)到系統(tǒng)要求,因此實用性不高。

圖4 N=20時的數(shù)據(jù)重構(gòu)結(jié)果

2.2 同類算法對比分析

圖5中顯示的是在各稀疏度條件下,不同算法的性能對照(不考慮通信開銷)。

圖5 同類算法實驗結(jié)果對比

可以看出在稀疏度較小的條件下,各類算法都具有較好的數(shù)據(jù)恢復(fù)精度。而在稀疏度大于30后,OMP算法的數(shù)據(jù)恢復(fù)性能急劇下降,SDIHT及BIHT算法在稀疏度大于40后也出現(xiàn)了明顯的下降趨勢,而QP-CSDR算法在稀疏度大于45后出現(xiàn)明顯下降,特別是n=5時的QP-CSDR算法在稀疏度50時仍能保持近90%的恢復(fù)概率,這也說明了分幀長度對于數(shù)據(jù)恢復(fù)精度的影響還是很明顯的:分幀長度越短,解空間數(shù)量越少,數(shù)據(jù)重構(gòu)精度越高,反之則解空間數(shù)量越多,數(shù)據(jù)重構(gòu)精度越低。

圖6 同類算法實驗結(jié)果對比

圖6中顯示的分別是針對稀疏度為0.2的原始信號,在壓縮比率為0.3和重構(gòu)精度為90%的條件下不同算法的性能對照(不考慮通信開銷)。

可以看出在兩種情況下,N=5時本算法的壓縮比率和數(shù)據(jù)重構(gòu)精度都是較高的。N=10時的算法性能與QICA-OMP和RAMP[12]算法相近。N=5時的算法性能與ROMP算法和SAMP算法差異不大,在壓縮比率和數(shù)據(jù)重構(gòu)精度方面都較OMP算法好。由于OMP算法本身具有重構(gòu)精度不高的特點,因此在同等重構(gòu)精度條件下性能不好,幾乎以1∶1的方式才能對原始信號進(jìn)行高精度重構(gòu)。

2.3 網(wǎng)絡(luò)實驗性能結(jié)果

網(wǎng)絡(luò)的性能結(jié)果如表3所示。監(jiān)測對象為微地震信號及音頻信號,采樣速率分別為10sample/s和200sample/s.節(jié)點為不進(jìn)行數(shù)據(jù)壓縮的傳感器節(jié)點及N=10時的固定長度分幀。兩個傳感器的采集速率均為10sample/s,每采集200個數(shù)據(jù)的時長為20s,均采用4 400mAh,3.6VDC的鋰電池供電。發(fā)送能耗按照30μJ/bit計算,共計實驗10組,統(tǒng)計其平均值。

微地震信號條件下,壓縮后的傳感器節(jié)點的通信能耗比未壓縮之前降低了1/5,。而考慮到計算能耗,接收能耗以及待機能耗等因素,節(jié)點的實際壽命延長至3.69倍左右。

音頻信號條件下,壓縮后的傳感器節(jié)點的通信能耗比未壓縮之前降低了1/3左右?？紤]到計算能耗等因素,節(jié)點的實際壽命延長至2倍左右,之所以小于微地震信號實驗的原因在于音頻信號處理所需的計算能耗更高。

表3 微地震網(wǎng)絡(luò)性能結(jié)果

3 結(jié)論

本文提出了基于量子粒子群優(yōu)化算法的壓縮感知數(shù)據(jù)重構(gòu)方法QP-CSDR。文章首先針對壓縮感知數(shù)據(jù)重構(gòu)原理進(jìn)行分析,提出將原始數(shù)據(jù)進(jìn)行固定長度分幀,以減少重構(gòu)空間解的數(shù)量,然后將粒子群優(yōu)化算法應(yīng)用于壓縮感知數(shù)據(jù)重構(gòu)過程中。在此基礎(chǔ)上,根據(jù)網(wǎng)絡(luò)監(jiān)測對象的統(tǒng)計學(xué)特點對粒子群的粒子位置的初始化進(jìn)行了改進(jìn),提高了各種稀疏度條件下的數(shù)據(jù)重構(gòu)精度。實驗結(jié)果表明,改進(jìn)后的量子粒子群算法能夠在稀疏度低于50的條件下以高精確度重構(gòu)數(shù)據(jù),與現(xiàn)有算法相比,重構(gòu)精度提高10%～30%左右。實際實驗結(jié)果表明,算法能夠?qū)鬏敂?shù)據(jù)進(jìn)行高比例壓縮,減少了通信數(shù)據(jù)量、降低了通信能耗,以微地震信號為檢測對象時,系統(tǒng)壽命延長了3.7倍、以音頻信號為監(jiān)測對象時,系統(tǒng)壽命延長了2倍左右。

[1] Kaneko M,Al Agha K. Compressed Sensing Based Protocol for Interfering Data Recovery in Multi-Hop Sensor Networks[J]. IEEE Communications Letters,2014,18(1):42-45.

[2] Mecklenbrauker C F,Gerstoft P,Panahi A,et al. Sequential Bayesian Sparse Signal Reconstruction Using Array Data[J]. IEEE Transactions on Singal Processing,2014,61(24):6344-6354.

[3] Figueiredo M,Nowak R,Wright S. Gradient Projection for Sparse Reconstruction:Application to Compressed Sensing and Other Inverse Problems[J]. IEEE Journal of Selected Topics in Singal Processing,2007,1(4):586-597.

[4] Tropp J,Gilbert A. Signal Recovery from Random Measurements via Orthogonal Matching Pursuit[J]. IEEE Transctions on Information Theory,2008,53(12):4655-4666.

[5] Needell D,Vershynin R. Greedy Signal Recovery and Un-Certainty Principles[J]. Proceddings of the Conference on Computational Imaging,2008:1-12.

[6] Needell D,Vershynin D. Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit[J]. Foundations of Computational Mathematics,2009,9(3):318-334.

[7] D Needell R Vershynin. Signal Recovery from Incomplete and Inaccurate Measurements via Regularized Orthogonal Matching Pursuit[J]. IEEE Journal of Selected Topics in Processing,2010,4(2):310-316.

[8] 軒春青,軒志偉,陳保立. 基于最小二乘與粒子群算法的壓力傳感器動態(tài)補償方法[J]. 傳感技術(shù)學(xué)報,2014,27(10):1363-1367.

[9] 高偉,趙博,周廣濤. 基于帶約束人工蜂群算法和平均Hausdorff距離的重力匹配方法[J]. 傳感技術(shù)學(xué)報,2014,27(1):74-78.

[10] Needell D,Tropp J A. CoSaMP:Iterative Signal Recovery from Incomplete and Inaccurate Samples[C]//ACM Technical Report 2008-01,California Institute of Technology,Pasadena,2008:93-100.

[11] 解志斌,于謙,沈斌,等. 一種新的基于粒子群優(yōu)化的雙簇頭分簇路由算法[J]. 傳感技術(shù)學(xué)報,2013,26(8):1135-1139.

[12] 劉亞新,趙瑞珍,胡紹海,等. 用于壓縮感知信號重建的正則化自適應(yīng)匹配追蹤算法[J]. 電子與信息學(xué)報,2010,32(11):2713-2717.

[13] Tropp J,Lu Gan,Nam Nguyen,et al. Sparsity Adaptive Matching Pursuit Algorithm for Practical Compressed Sensing[C]//42nd Asilomar Conference on Signals,Systems and Computers,2008:581-587.

[14] Ho S L,Shiyou Yang,Guangzheng Ni,et al. A Quantum-Based Particle Swarm Optimization Algorithm Applied to Inverse Problems[J]. IEEE Transactions on Magnetics,2013,49(5):2069-2072.

[15] Hirano H,Yoshikawa T A Study on Two-Step Search Based on PSO to Improve Convergence and Diversity for Many-Objective Optimization Problems[C]//IEEE Congress on Evolutionary Computation,2013:1854-1859.

[16] 劉美,徐小玲,黃道平. 應(yīng)用粒子群優(yōu)化分配WSN多目標(biāo)跟蹤節(jié)點任務(wù)[J]. 傳感技術(shù)學(xué)報,2010,23(9):1334-1339.

劉洲洲(1981-),男,山西運城人,博士研究生,講師,2004、2007年于西北工業(yè)大學(xué)獲得學(xué)士、碩士學(xué)位,主要從事無線傳感器網(wǎng)絡(luò)方面的研究,liuzhouzhou8192@126.com;

李艷平(1976-),女,山東鄆城人,工學(xué)碩士,講師。主要研究方向為智能算法,lyp5506@126.com。

Perceptual Data Reconstruction for Compressed Sensing Based onQuantum Behaved Particle Swarm Optimization*

LIUZhouzhou1*,LIYanping2

(1.Xi’an Aeronautical University,Xi’san 710077,China;2.Department of Computer and Information Engineering,Heze University,Heze Shandong 274015,China)

According to wireless sensor network monitoring object features,the compressed sensing theory is applied to data compression to reduce the communication energy. Considering that reconstruction accuracy of existing data reconstruction in compressed sensing can be easily influenced by sparsity,after analysis of compressed sensing data reconstruction principle,with sub-frame processing the original signal in fixed length to reduce the solution space,and applying quantum theory encoding in Particle Swarm Optimization,Compressed Sensing Data Reconstruction that based on Quantum-behaved Particle Swarm Optimization appears. According to wireless sensor network monitoring object features,this algorithm improves the accuracy of the data reconstruction by improving particle initial position and update mode in Particle Swarm Optimization from Statistics. Simulation results show that under conditions of sparsity less than 50,QP-CSDR gets 20%～40% performance improvement on Reconstruction accuracy comparing to existing algorithms. Now the algorithm has been applied to micro-earthquakes and audio monitoring system,and in actual inspection,the actual system life is extended about 2～4 times with assurance data accuracy.

wireless sensor network;quantum theory;particle swarm optimization algorithm;compressed sensor;data reconstruction

項目來源:國家自然科學(xué)基金項目(No.61103242)

2014-07-29 修改日期:2015-02-05

C:7230

10.3969/j.issn.1004-1699.2015.06.011

TP393

A

1004-1699(2015)06-0836-06