張源峰，孫海信，顏佳泉，蒯小燕

（1.廈門大學水聲通信與海洋信息技術(shù)教育部重點實驗室，福建 廈門361005；2.閩西職業(yè)技術(shù)學院電氣工程系，福建 龍巖364021）

隨著通信及信號處理技術(shù)、傳感器技術(shù)和計算機技術(shù)的發(fā)展，無線傳感器網(wǎng)絡（wireless sensor networks，WSN）越來越受到人們的關(guān)注.WSN一般包括傳感器節(jié)點、匯聚點和任務管理節(jié)點，它通過在環(huán)境中布置多個傳感器，協(xié)作地感知、采集和處理所覆蓋的網(wǎng)絡區(qū)域的監(jiān)測對象的信息，并將這些來自不同時間和不同信息源的信息傳遞到匯聚點，進行多傳感器數(shù)據(jù)信息融合技術(shù)處理，最后通過互聯(lián)網(wǎng)或者衛(wèi)星將信息送達任務管理節(jié)點.用戶可通過管理節(jié)點對傳感器網(wǎng)絡進行設(shè)置和管理，發(fā)布實時監(jiān)測任務及采集存儲監(jiān)測數(shù)據(jù)［1］.然而，恰恰因為WSN具有大量傳感器節(jié)點，可以實時感知和采集環(huán)境的變化信息，使其受到能耗、存儲空間和計算能力的限制.如何有效地實現(xiàn)WSN中的低能量消耗、低計算復雜度和存儲空間的節(jié)省，正是WSN亟待解決的難題.

傳統(tǒng)的信號獲取和處理過程主要包括采樣、壓縮、傳輸和解壓縮4個部分，其采樣過程必須遵循奈奎斯特采樣頻率，這種方式采樣數(shù)據(jù)量大，先采樣后壓縮，浪費了大量的傳感元、時間和存儲空間［2］.相較之下，壓縮感知理論針對可稀疏表示的信號，能夠?qū)?shù)據(jù)采集和數(shù)據(jù)壓縮合二為一，可以用遠遠少于Nyquist采樣定理所需的采樣點數(shù)恢復出原信號.其中CS重構(gòu)算法的研究是CS理論的關(guān)鍵環(huán)節(jié)，CS重構(gòu)算法的研究對于WSN以及資源受限和大數(shù)據(jù)的采樣系統(tǒng)具有重大的研究意義，它可以有效地減少采樣傳感器的數(shù)目，同時降低每個傳感器的能耗、存儲空間和計算復雜度.

CS利用了信號的時間或者空間相關(guān)性，只研究單個信號的稀疏、壓縮和重構(gòu)問題；WSN是一個分布式多傳感器信號采集和數(shù)據(jù)融合的網(wǎng)絡，顯然CS理論無法滿足其要求.然而分布式壓縮感知研究多個信號的聯(lián)合重構(gòu)問題，它充分利用了信號內(nèi)部和信號之間的相關(guān)結(jié)構(gòu)，每個獨立的傳感器信號都能在某一特定的正交稀疏基下稀疏表示，每個傳感器通過測量到的信號映射到另一個與稀疏基不相關(guān)的基上進行獨立編碼，然后將少量的投影結(jié)果傳輸?shù)絽R聚點，然后通過重構(gòu)算法重構(gòu)出每個傳感器信號［3］.

本文介紹了CS理論，同時介紹了正交匹配追蹤算法［4］和前向預測正交匹配追蹤（look ahead orthogonal matching pursuit，LAOMP）算法；針對 LAOMP中的前向參數(shù)L只能固定選定，其中前向參數(shù)是每次迭代選擇的潛力原子的個數(shù)，使得計算量非常大，提出了一種自適應前向預測正交匹配追蹤（adaptive look ahead orthogonal matching pursuit，ALAOMP）算法，在每次迭代過程中，對L進行自適應選擇，并通過仿真實驗驗證了，在不同信號觀測噪聲比下，ALAOMP算法的性能優(yōu)于LAOMP算法.

1 CS理論

對于一個有限長度為N的一維離散信號f，f∈RN，信號f在稀疏基｛ψi｝Ni＝1上是K稀疏的，可以表示為一組標準正交基｛ψi｝Ni＝1的線性組合，則f可以表示為

其中，K為稀疏度，K＜N；s是信號f的加權(quán)系數(shù)序列，si＝〈f，ψi〉＝ψiTf；ψ＝｛ψi｝iN＝1，ψ 為稀疏基，ψi為列向量，ψ∈RN×N.CS是一個線性測量過程：將K稀疏的的信號f與感知向量組｛φj｝jN＝1做內(nèi)積運算，產(chǎn)生觀測信號yj＝〈f，φj〉；各個yj組成一個M×1的觀測向量y，以φjT作為觀測矩陣Φ 的行，即將信號f投影到觀測矩陣Φ（Φ∈RM×N）上得到觀測向量y，線性測量過程表達式為

由于y的維數(shù)遠遠低于f的維數(shù)，方程（2）有無窮多個解，即該問題是欠定的，很難重構(gòu)出原始信號.但是如果系數(shù)s中只有K個非零值，同時觀測矩陣滿足 約 束 等 距 特 性 （res－tricted isometric property，RIP），即對于任意K稀疏度的信號f，存在常量0≤δk＜1，有

理論證明，信號重構(gòu)可以由測量矩陣y求解最優(yōu)l0范數(shù)得到，當考慮噪聲時，CS重構(gòu)模型可表示為

求解最優(yōu)l0范數(shù)的問題，實際上是一個欠定問題，在多項式上很難求解.因此，相關(guān)學者提出了其他的求解方法，如基追蹤算法、迭代貪婪追蹤算法和最小全變分法等.

為了確定理想的信號f，需要決定Φ中的哪一列（即原子）加入到觀測向量y，OMP算法［3］的主要思想是以貪婪的方式選擇原子，在每次迭代中，選擇Φ中與y剩余部分最相關(guān)的列，即選擇一個與上次迭代殘差內(nèi)積最大的原子，然后更新原子候選集、估計信號和殘差；判斷是否滿足迭代終止條件，是，則輸出估計信號，否，則繼續(xù)反復迭代［4］.

2 LAOMP和ALAOMP算法

2.1 LAOMP算法

在標準OMP算法中，選擇當前迭代的新原子沒有考慮到依賴于所選擇的原子對所有迭代最終完成時OMP性能的影響，新原子的選擇對未來迭代的影響 是 盲 目 的，因 此，Saikat Chatterjee 等［5］提 出LAOMP算法，該算法在OMP算法的基礎(chǔ)上加入了前向預測策略，即一個原子的選擇是通過評估其對最終性能指標的影響，即所有迭代結(jié)束時最小擬合殘差.LAOMP算法的主要思想如下：在每次迭代中先選擇L個與上次殘差內(nèi)積最大的原子，其中L表示前向參數(shù)；然后依次預測這L個原子對最終迭代殘差的影響，將L個原子中使得最終殘差模值最小的原子加入支撐集，然后更新原子候選集、估計信號和殘差.LAOMP算法流程圖如圖1所示.前向預測策略可以由前向殘差（look ahead residual，LAR）子算法［6］完成，具體描述如下：

算法1：LAR子算法

輸入：觀測矩陣Φ，觀測向量y，稀疏度為K，上次迭代原子支撐集I，新選定的原子索引i.

初始化：當前迭代原子支撐集Ik＝Ik∪i，近似系數(shù)y，殘差，迭代次數(shù)

迭代過程：

1）迭代次數(shù)更新：k＝k＋1；

2）確定新增原子索引并將其索引加入原子支撐集：

3）更新近似系數(shù)及殘差：

4）迭代停止判斷條件：

其中rk為當前迭代殘差，rk－1為前次迭代殘差.滿足上式，則迭代終止；否則，返回步驟1）繼續(xù)執(zhí)行.

為了使用LAR子算法，定義前向預測殘差LAR函數(shù)如下：設(shè)y∈RM，Φ∈RM×N，稀疏度為K，先前迭代的原子支撐集為I，當前迭代的新增原子索引為i，則最終輸出殘差r∈RM可以用下式表示：

圖1 LAOMP算法流程圖Fig.1 Flow chart of LAOMP algorithm

2.2 ALAOMP算法

在LAOMP算法中，正是因為前向參數(shù)L的引入，及外部L次循環(huán)及K次外部迭代和前向預測策略子算法中的內(nèi)部迭代，使得LAOMP算法計算復雜度及計算量相當?shù)拇?；同時，LAOMP對于最具潛力的L個原子的選定，其中前向參數(shù)L只能在程序初始化中人為地設(shè)定固定值，通過仿真實驗發(fā)現(xiàn)，這L個降序排列的原子中，存在某兩個相鄰原子衰落大以及其相關(guān)性低，固定的前向參數(shù)反而成為選擇最具潛力原子的缺陷.本文給出了一種ALAOMP算法，提出了一種自適應選擇前向參數(shù)L的方法，以保證所選擇的L個原子是最佳的，從而實現(xiàn)降低算法的計算復雜度.L個原子的選定由自適應前向參數(shù)（adaptive look ahead parement，ALAP）子算法完成，具體描述如下：

算法2：ALAP子算法

輸入：觀測矩陣Φ，觀測向量y，上一次迭代殘差r1，L＝1；

1）計算出所有原子與殘差的內(nèi)積絕對值，即

2）對product向量進行降序排列，計算相鄰原子之間的相對誤差，如下式：

relative＿error（i）＝｜val（i）－val（i－1）｜／val（i），其中，val為原子與殘差內(nèi)積絕對值product向量降序排列后的向量；

3）計算相鄰原子的相對誤差變化率，即

4）滿足條件error＿rate≥τ，終止循環(huán)，否則執(zhí)行L＝L＋1；同時設(shè)定L的上限T，滿足L≥T終止程序.

輸出：前向參數(shù)L.

自適應前向參數(shù)函數(shù)定義如下：設(shè)y∈RM，Φ∈RM×N，稀疏度為K，上一次迭代殘差r1，殘差r1∈RM，則ALAP算法函數(shù)為：

那么ALAOMP算法可以描述如下：

算法3：ALAOMP算法

輸入：觀測矩陣Φ，觀測向量y，稀疏度K；

定義：n＝［n1，n2，…，nL］t，j＝［j1，j2，…，jl］t；

迭代過程：

1）迭代次數(shù)更新，k＝k＋1；自適應找到與ΦtrK－1幅值最大的L個原子的索引j，且j?Ik－1，執(zhí)行ALAP函數(shù)：L＝ALAP（y，Φ，r1）；

2）預測這L個原子對最終迭代殘差的影響，執(zhí)行內(nèi)部循環(huán)，循環(huán)次數(shù)為L，內(nèi)部循環(huán)語句為rr＝LAR（y，Φ，K，Ik－1，jl），nl＝‖rr‖2，其中nl為迭代到原子索引jl時最終殘差的范數(shù)；

3）支撐集更新：最終殘差的范數(shù)n中最小元素的索引號為l，選擇使得殘差最小，

原子索引號為ik＝jl，更新支撐集Ik＝Ik－1∪ik；

5）如果滿足‖rk‖2＞‖rk－1‖2或者k＞K，則k＝k－1，退出迭代.

2.3 計算復雜度分析

OMP的計算復雜度為O（MNK），LAOMP的計算復雜度為O（MNK2L），其中O（g）表示算法計算復雜度的階次，它是衡量算法在運行時間方面的效率.因此我們可以明顯地看出，前向參數(shù)L的變大會增加算法的計算復雜度.在第i迭代時，L的大小決定了在本次迭代中執(zhí)行LAR子算法的次數(shù)，同時LAR子算法的計算量相當于運行一個稀疏度為（K－i）的OMP算法，因此前向參數(shù)L決定了LAOMP算法和ALAOMP算法的計算復雜度.由于LAOMP中前向參數(shù)L是固定的，同時ALAOMP的ALAP子算法減少了前向參數(shù)L，使得ALAOMP算法的計算復雜度比LAOMP算法低；

3 實驗結(jié)果及分析

定義信號噪聲觀測比［7］（signal to measurement noise ratio，SMRN）為：

其中w為觀測噪聲.

為了驗證基于ALAOMP算法的重構(gòu)性能，在信號加噪的情況下，設(shè)計了兩組實驗：1）在SMRN＝10 dB情況下，對比ALAOMP算法和LAOMP算法的重構(gòu)性能；2）在SMRN＝20dB情況下，對比ALAOMP算法和LAOMP算法的重構(gòu)性能.為了衡量算法的重構(gòu)性能，定義了信號重構(gòu)信噪比（signal to reconstruction noise ratio，SRNR）和平均支撐勢誤差（average support cardinality error，ASCE）這兩個性能指標［7］.其中，SRNR用于測試信號重構(gòu)性能，它的定義為：

ASCE主要測試的是支撐集的重構(gòu)性能，其具體定義如下：

從ASCE定義可知，ASCE值越小表示支撐集的重構(gòu)準確度越高.

仿真參數(shù)設(shè)置如下：信號的長度N＝500，稀疏度K＝20，LAOMP算法的前向參數(shù)L＝3，ALAOMP算法的前向參數(shù)L≤3，τ＝5，仿真次數(shù)n＝500.當SMRN＝10dB時，ALAOMP算法和LAOMP算法的信號重構(gòu)準確度和支撐集的重構(gòu)準確度如圖2所示.當SMRN＝20dB時，ALAOMP算法和LAOMP算法的信號重構(gòu)準確度和支撐集的重構(gòu)準確度如圖3所示.

圖2 SMNR＝10dB時ALAOMP算法和LAOMP算法性能對比Fig.2 Comparison of performance between ALAOMP and LAOMP algorithm when SMNR＝10dB

仿真結(jié)果表明，在加入自適應選擇前向參數(shù)后，在所有迭代中ALAOMP算法前向參數(shù)選擇總數(shù)的平均值明顯低于LAOMP，即ALAOMP的計算復雜度低于LAOMP.同時ALAOMP算法的SRNR值始終高于LAOMP算法，其ASCE值始終低于LAOMP算法，即ALAOMP算法的信號重構(gòu)性能及支撐集性能始終優(yōu)于LAOMP算法.

4 結(jié) 論

本文通過仿真驗證了使用前向預測的LAOMP算法信號重構(gòu)性能及支撐集重構(gòu)性能明顯優(yōu)于OMP算法.同時驗證了，文中提出的ALAOMP算法結(jié)合了前向預測策略和自適應選擇前向參數(shù)的優(yōu)點，相比只采用前向預測策略的LAOMP算法，能夠用相比較低的計算復雜度，獲得優(yōu)于LAOMP算法的信號重構(gòu)性能及支撐集重構(gòu)性能.實驗證明，這種自適應前向預測正交匹配追蹤算法是實用有效的.

［1］Mei H，Sun H，En C，et al.Impulsive noise mitigation and doubly selective channels estimation for underwater acoustic OFDM with compressed sensing［J］.Journal of Convergence Information Technology，2013，8（9）：78－87.

［2］Sun H，Shen W，Wang Z，et al.Joint carrier frequency offset and impulse noise estimation for underwater acoustic OFDM with null subcarriers［C］∥Oceans，2012.Hampton Roads，USA：IEEE，2012：1－4.

［3］Mei H，Haixin S，En C，et al.Joint Interference mitigation with channel estimated in underwater acoustic OFDM system［J］.TELKOMNIKA Indonesian Journal of Electrical Engineering，2013，11（12）：7423－7430.

［4］Tropp J A.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2007，53（12）：4655－4666.

［5］Chatterjee S，Sundman D，Skoglund M.Look ahead orthogonal matching pursuit［C］∥Acoustics，Speech and Signal Processing （ICASSP），2011IEEE International Conference on.Prague，Czech Republic：IEEE，2011：4024－4027.

［6］Swamy P B，Ambat S K，Chatterjee S，et al.Reduced look ahead orthogonal matching pursuit［C］∥Communications（NCC），2014Twentieth National Conference on.Kanpur：IEEE，2014：1－6.

［7］Chatterjee S，Sundman D，Vehkapera M，et al.Projectionbased and look－ahead strategies for atom selection［J］.Signal Processing，2012，60（2）：634－647.