基于Jacobi ADMM的傳感網分布式壓縮感知數據重構算法

李國瑞 孟 婕 彭三城 王 聰

1(東北大學計算機科學與工程學院 沈陽 110819)2(廣東外語外貿大學語言工程與計算實驗室 廣州 510006)

無線傳感器網絡通常由部署在監測區域的若干無線傳感器節點構成，每個傳感器節點通過感知環境信息，并將其處理后以無線多跳的方式傳輸至Sink節點[1].無線傳感器節點通常部署在無人值守的野外區域或復雜的工業控制現場，更換電池極為不便.同時，無線傳感器節點的計算、存儲和能量等各項資源極為有限，因此，將傳感器節點采集到的監測數據壓縮后再進行傳輸可有效地延長無線傳感器網絡的存活周期.目前，無線傳感器網絡中的數據壓縮與重構技術已成為該領域研究中的核心問題之一[2-3].

時空關聯分析預測[4]與分布式壓縮編碼[5]是傳統無線傳感器網絡中采用的2類數據壓縮技術，但兩者均需在節點中執行復雜的運算，同時還需在網絡中傳輸大量的同步參數.因此，存在明顯的弊端[6].近年來，壓縮感知(compressed sensing， CS)理論作為信號處理領域中一個備受關注的研究熱點，以遠低于Nyquist采樣定理規定的方式壓縮數據，并通過求解優化問題實現稀疏或可壓縮數據的精確重構，從而為傳感網中的數據壓縮與重構研究提供了一個新的方向[7].

經典的壓縮感知理論僅支持單個信號的壓縮與重構，然而在大規模監測網絡中同一個區域內的多個信號之間存在一定的相關性[8].因此，Baron等人[9]在壓縮感知理論的基礎上進行了擴充，把對單個信號的壓縮采樣擴展到了對信號群的壓縮采樣，提出了分布式壓縮感知(distributed compressed sensing， DCS)理論.該理論包含3種典型的聯合稀疏模型(joint sparse model， JSM)，與經典的壓縮感知理論相比，由于其充分發掘了信號的內相關性和互相關性，可以有效地節約信號觀察數量，并提高信號的重構精度.

目前，分布式壓縮感知重構算法主要包括集中式重構和分布式重構2類算法.其中，集中式重構算法的研究較為成熟，典型的算法包括同步正交匹配追蹤(simultaneous orthogonal matching pursuit, SOMP)算法[10]、同步子空間追蹤(simultaneous subspace pursuit, SSP)算法[11]和同步壓縮采樣匹配追蹤(simultaneous compressive sampling matching pursuit, SCoSaMP)算法[12]等.然而，由于集中式重構算法需要將各個監測節點的感知數據傳輸至統一的數據中心進行集中式重構，不但對網絡的帶寬、延時和節點的能耗要求較高，而且各級監測/控制節點不能直接獲取重構結果.因此，無法滿足無線傳感器網絡的實際應用需求.

分布式重構算法采用分布式計算模式避免了上述問題，通過在部分簇頭節點之間交換公共信息，并以迭代的方式更新個體信息，從而實現信號群的高精度壓縮數據重構.Li等人[13]通過改進集中式的壓縮采樣匹配追蹤算法和子空間追蹤算法，提出了分布式協同子空間追蹤(decentralized and collabora-tive subspace pursuit， DCSP)算法，并進行了詳細的理論分析和驗證.Xu等人[14]基于交替方向乘子法迭代求解信號群中的公共部分和個體部分，從而實現了分布式的壓縮數據重構.然而，該方案在簇頭節點數量大于等于3時無法確保迭代重構的收斂性，還具有一定的局限性.

本文針對無線傳感器網絡的分布式數據收集應用場景，采用分布式壓縮感知理論中的JSM-1模型，通過在優化問題的目標函數中增加近似項以確保分布式壓縮數據重構的收斂性，從而設計了一種基于Jacobi ADMM的分布式壓縮數據重構算法.該算法通過在簇頭節點間迭代交換公共信息以提取相關感知數據的公共部分，并在各個簇頭節點內部更新各自的獨立部分，從而實現無線傳感網中相關感知數據的分布式壓縮重構.實驗結果表明，與現有其他重構算法相比，本文所提出的算法具有更高的數據重構精度.

1 研究背景

1.1 分布式壓縮感知理論

y=Φf+e,

(1)

y=Ax+e，

(2)

(3)

隨后再利用變化基Ψ將x還原至原始空間得到，其中ε>0為重構誤差.由于式(3)為NP難問題[16]，通常將其松弛為l1最小化問題進行求解：

(4)

xi=zc,i+zi.

(5)

由于公共部分為所有節點所共有，即zc,1=zc,2=…=zc,n，因此可將該式表示為

(6)

令

則在分布式壓縮感知中l1最小化問題(即式(4))可表示成：

(7)

1.2 ADMM算法

ADMM算法主要用于求解多變量優化問題，目前已被廣泛應用于大規模分布式網絡系統的優化計算領域[17].ADMM算法解決問題的一般形式為

minf(x)+g(z),
s.t.Ax+Bz=d，

(8)

(9)

其中，ρ為懲罰參數，u為拉格朗日乘子.

2 系統模型

Fig.1 The network system model圖1 網絡系統模型

本文提出的分布式數據重構算法適用于層次結構的無線傳感器網絡，其系統模型如圖1所示：

整個無線傳感器網絡由大量簇成員節點和簇頭節點構成.簇成員節點在采集到感知數據后利用相應的測量矩陣進行投影壓縮，并將壓縮后的數據傳輸至各自的簇頭節點[18].簇頭節點匯集本簇內的壓縮數據后運行本文所提出的分布式壓縮數據重構算法，從而以分布式方式在無線傳感器網絡內實現壓縮數據的重構操作.

3 基于分布式壓縮感知的數據重構算法

在無線傳感器網絡中，為求解分布式壓縮數據重構問題(即式(7))，首先構造增廣拉格朗日函數：

(10)

(11)

(12)

α(k+1)=α(k)+νγ(ZcB)，

(13)

其中，ν為懲罰參數.通過求解子問題(即式(11)和式(12))即可在重構出無線傳感器網絡中的感知數據.

算法1.基于Jacobi ADMM的分布式壓縮數據重構算法.

輸入：感知矩陣Ai、測量信號yi；

輸出：稀疏信號xi.

① 初始化拉格朗日乘子α，懲罰參數μ，γ，ν，公共部分zc,i和個體部分zi，內層迭代次數閾值kth和外層迭代次數閾值lth，殘差閾值r；

③ whilek

⑦ 根據式(13)更新α；

⑧k=k+1；

⑨ end while

⑩ 通過求解子問題式(12)更新獨立部分zi；

4 實驗結果與分析

為了驗證本文所提出的算法在無線傳感器網絡中的數據重構性能，本節分別利用合成數據集和真實數據集進行實驗驗證.其中，合成數據集由Matlab軟件仿真合成，真實數據集選用了黑河流域中游生態水文數據集[22]和City Pulse空氣污染物數據集[23].在衡量算法性能時，使用相對均方誤差(relative mean square error， RMSE)進行度量，用τ表示，其定義為

(14)

1) 分布式重構算法[14].該算法屬于分布式數據重構算法，通過將數據分解成公共部分和個體部分，利用ADMM算法進行迭代重構.

2) 分布式貝葉斯算法[24].該算法屬于分布式數據重構算法，通過將數據分解成公共部分和個體部分，利用變分貝葉斯推斷進行迭代重構.

3) SSP算法[11].該算法屬于集中式數據重構算法，利用相同的稀疏基，通過改進子空間追蹤貪婪算法進行迭代重構.

4) SCoSaMP算法[12].該算法屬于集中式數據重構算法，利用相同的稀疏基，通過改進壓縮采樣匹配追蹤貪婪算法進行迭代重構.

Fig.2 Influence of m on the data reconstruction accuracy圖2 觀測信號長度m對數據重構性能的影響

4.1 合成數據實驗

在生成合成數據集時，首先隨機生成m×n的高斯矩陣作為測量矩陣Ai，然后從中隨機挑選k個小于n的索引并隨機生成稀疏信號xi，最后利用投影運算yi=Aixi+ei生成測量信號yi，其中ei為高斯隨機噪聲.

圖2展示了在采樣率m/n=40%、稀疏度k=0.05n的條件下，本文算法與其余4種算法的數據重構性能比較.從圖2可以看出，本文算法具有最高的數據重構精度.同時，所有壓縮數據重構算法的重構誤差都隨著觀測信號長度m的增加而降低，并逐漸趨于穩定.另外，所有將數據分解成公共部分和個體部分的分布式算法在數據重構精度方面均優于基于貪婪思想的集中式算法.

圖3展示了稀疏信號群中個體部分數量對5種數據重構算法的數據重構精度的影響.實驗的參數為m=96，n=240，k=15.從圖3可以看出，本文算法依然具有最高的數據重構精度.同時，所有壓縮數據重構算法的重構誤差都隨著個體部分數量的增加而降低.顯然，信號群中的信號越相似，重構算法重構時越容易，因此重構精度也就越高.另外，從圖3還可以看出，信號群中個體部分數量對分布式算法的影響較大，而對基于貪婪思想的集中式算法影響較小.

Fig.3 Influence of number of innovation components on the data reconstruction accuracy圖3 個體部分數量對數據重構性能的影響

表1展示了5種壓縮數據重構算法在不同簇頭節點數量N和觀測信號長度m條件下的相對均分誤差.從表1可以看出，本文算法具有最高的數據重構精度.同時，所有算法的數據重構誤差都隨著簇頭節點數量N和觀測信號長度m的增加而降低.但是，簇頭節點數量N的變化對數據重構誤差的影響不顯著.

圖4和圖5分別展示了本文算法在與圖3相同的實驗參數條件下稀疏度k和通信簇頭數量c對數據重構精度的影響.從圖4和圖5可以看出，本文算法的數據重構誤差隨著稀疏度k的增加而逐漸升高，隨著通信簇頭數量c的增加而逐漸降低.顯然，信號的稀疏度越高，數據重構算法的重構難度越大，因此本文算法的數據重構精度也就相應越低.同時，互相通信的簇頭節點越多，對信號群中公共部分的計算越精確，因此本文算法的數據重構精度也就越高.

Table 1 Influence of N and m on the Data Reconstruction Accuracy表1 簇頭節點數N與觀測信號長度m對數據重構精度的影響

Fig.4 Influence of k on the data reconstruction accuracy圖4 稀疏度k對數據重構性能的影響

Fig.5 Influence of c on the data reconstruction accuracy圖5 通信簇頭數量c對數據重構性能的影響

4.2 真實數據實驗

在真實數據集實驗中，首先基于黑河流域中游生態水文數據集對比本文算法與其余4種數據重構算法的數據重構性能.實驗中使用了離散小波變換基對原始數據進行稀疏表示，實驗參數為n=128，μ=16，γ=0.5，N=35.

圖6展示了5種算法在該數據集上的數據重構誤差.從圖6可以看出，本文算法具有最高的數據重構精度.同時，所有壓縮數據重構算法的重構誤差都隨著采樣率的增加而降低.顯然，采樣率越高，數據重構算法的重構難度越低，因此數據重構的誤差也就相應越低.

Fig.6 Data reconstruction accuracy of the ecological hydrological dataset in the middle reaches of the Heihe river圖6 黑河流域中游生態水文數據集的數據重構精度

圖7展示了所有壓縮數據重構算法在City Pulse空氣污染物數據集上的數據重構誤差，其中選用了NO2濃度數據，除簇頭節點數量N取值修改為25外其余實驗參數與圖6保持一致.基于該數據集的實驗結論與基于黑河流域中游生態水文數據集的結論一致，本文算法依然展現出最高的數據重構性能.

Fig.7 Data reconstruction accuracy of the City Pulse air pollutant dataset圖7 City Pulse空氣污染物數據集的數據重構精度

5 結束語

本文提出了一種適用于無線傳感器網絡的分布式壓縮數據重構算法.該算法采用分布式壓縮感知理論中的JSM-1模型，通過將信號分解為公共部分和個體部分，并在交替方向乘子法中引入近似項求解，從而實現無線傳感器網絡的分布式數據收集操作.實驗過程中分別使用合成數據集和真實數據集進行驗證，結果表明，本文所提出的算法在數據重構精度方面優于現有的分布式壓縮數據重構算法.在未來的工作中，將重點考慮如何引入邊緣計算技術以實現大規模物聯網中的分布式壓縮數據重構.