基于不平衡擴展模型的火災信息分布式壓縮感知

莊哲民 吳力科 路小波

(1汕頭大學電子系，汕頭 515063)

(2東南大學自動化學院，南京 210096)

基于不平衡擴展模型的火災信息分布式壓縮感知

莊哲民1吳力科1路小波2

(1汕頭大學電子系，汕頭 515063)

(2東南大學自動化學院，南京 210096)

針對無線傳感網絡數據傳輸與計算的不均衡而導致部分節點能耗大的問題，首先結合圖論中二部圖思想，將不平衡擴展模型應用在分布式壓縮感知上，并設計出一種與該架構相對應的分布式算法.該算法通過一個列稀疏度確定的稀疏隨機二值矩陣決定節點之間是否實現數據傳輸，從而將傳輸和計算任務平均分散在各個節點，并利用二階錐形規劃法對融合中心的數據進行重構.最后，在火災場中利用不平衡擴展模型的分布式壓縮感知網絡進行仿真實驗，并對算法的優越性和網絡的節能性作出詳細分析.在仿真過程中，通過分析均方誤差和信噪比證明所提出的模型不僅在降低節點能耗上有較好的效果，而且在有噪聲環境中可以很好地保證信號的重構性能.

無線傳感網絡;分布式壓縮感知;不平衡擴展模型;稀疏測量矩陣

大規模無線傳感網絡中傳感器節點的能量和帶寬均有限，因此，在滿足服務質量的前提下降低網絡開銷已成為急需解決的問題.近年來提出的壓縮感知理論要求數據在某個轉換域上只要滿足一定的稀疏度就可對數據有效壓縮，而對于大規模傳感網絡，節點間數據一般具有空間相關性，這個特性使得該數據在某個轉換域上滿足稀疏度要求，因此可把壓縮感知理論應用于分布式傳感網絡中，從而降低無線傳感網絡的開銷.

目前，雖然分布式壓縮感知的研究才剛剛開始，但是利用分布式壓縮感知的特點增加信號的可壓縮性，降低信號的重構誤差已是學者們關注的問題.文獻［1］從分布式數據的空間相關性出發，通過調整傳感器的節點位置增加信號的可壓縮性，減小信號的恢復誤差，從而增加無線傳感網絡中數據傳送的效率;文獻［2］利用分布式數據的空間相關性建立一個聯合稀疏模型，該模型不僅減少傳感網絡中融合中心的數據量，同時分析了重構誤差和壓縮比之間的關系.文獻［1－2］利用信號樣本的空間相關性，雖然增加信號可壓縮性的同時減小了信號的重構誤差，但并未考慮緩解局部節點能耗大的問題.文獻［3］利用多跳技術將測量數據按照最短路徑的方式依次在節點間進行傳輸，在減少網絡總能耗的前提下使各個節點平均分擔傳輸任務，但由于其選擇稠密測量矩陣，使得單個節點傳輸的數據量依然很大.文獻［4］選擇多值稀疏測量矩陣減少節點間的通信量，但由于稀疏測量矩陣的多值性，導致節點需要額外的運算，而且稀疏隨機映射對分布式數據有特殊要求，因為分布式數據稀疏度過大會引起信息丟失.由以上分析可知，文獻［3－4］雖然在一定程度上能緩解節點能耗大的問題，但仍存在著諸多不足.

針對上述問題，1996年 Sipser等［5］提出用擴展模型建立線性錯誤校正編碼簇減少解碼時間，這類編碼稱為低密度奇偶校驗碼(low-density paritycheck codes);Berinde等［6］把擴展編碼應用到壓縮感知領域中，從而減小編碼的復雜度.但這些理論模型只限于單個信號的壓縮感知，并沒有深入地對分布式信號的處理進行研究.本文將不平衡擴展模型產生(0，1)二值稀疏測量矩陣的原理結構應用于分布式壓縮感知中，提出一種基于不平衡擴展模型［7］的分布式壓縮感知新的理論模型.不平衡擴展模型是一個簡單的二部圖，它可以利用該二部圖的2個互不相交頂點子集來確定測量矩陣，不同子集中的頂點關聯與否決定測量矩陣元素是否為1，從而構建一個只包含(0，1)的二值稀疏矩陣，這里的2個不同頂點子集分別為數據節點和編碼節點，而連接不同子集頂點間的邊代表數據傳輸鏈路.由于該二值矩陣的稀疏化程度很高，并且只有當測量矩陣中的元素為1時才對數據節點所采集到的數據進行傳輸，因此該方案既大量地減小了數據節點傳輸到編碼節點的數據量，也減少了由于使用其他測量矩陣所造成數據預處理過程中額外的數乘運算，最終減少了數據節點的計算負荷.

1 壓縮感知理論

在壓縮感知中，一個最基本的問題是如何構造高效的測量矩陣，根據y=φx可知信號重建的實質是利用M維測量信號y和測量矩陣φ，然后采用一定的算法重建出N(N＞M)維信號的過程.因此，正確構建測量矩陣在獲取測量向量和重建信號的過程中起著重要作用.以下將簡單講述測量矩陣的相關知識:

1)隨機矩陣.目前應用在壓縮感知［7］或分布式壓縮感知的測量矩陣主要是稠密的隨機矩陣，典型的稠密測量矩陣φ包括有高斯(Gaussian)隨機分布測量矩陣和伯努利(Bernoulli)隨機分布測量矩陣.由文獻［5］可知，稠密隨機測量矩陣僅需要O(Klog(N/K))個測量值就能保證重構信號在性能上逼近壓縮信號的最優值.但是由于稠密矩陣元素的稠密性，應用到分布式壓縮感知中會存在以下問題:①由于傳感器節點數目多，導致數據測量的計算量較大;② 節點間的數據傳輸量大;③ 使用線性規劃方法進行解碼的計算復雜度達到O(N3).考慮到稠密測量矩陣的這些缺點，本文采用稀疏的測量矩陣代替稠密的測量矩陣，在保證重構性能的前提下減少數據測量和壓縮的計算量及數據傳輸量.稀疏測量矩陣的基本構造方式如下:首先生成一個零元素的矩陣φ∈0M×N，M＜N，在矩陣φ的每一個列向量中，隨機選取d個位置元素，然后對所選取位置的值賦1.

2)RIP特性.測量矩陣φ∈RM×N和向量集合T∈{1，2，…，N}，若集合 T 中非零元素個數小于或等于稀疏度，則矩陣φT為測量矩陣φ由集合T中元素所指示的列向量構成大小為的子矩陣，如果存在常數 δk∈(0，1)使不等式成立，就稱矩陣φ具有K項RIP性質.RIP［8］給出了存在確定解的充要條件，即要想信號完全重構，必須保證觀測矩陣不把2個不同的K項稀疏信號映射到同一個采樣集合中，這就要求從觀測矩陣中抽取的每M個列向量構成的矩陣是非奇異的.一個RIP-p矩陣等同于不平衡網絡在分布式壓縮感知中的鄰接矩陣，因此，本文中需要解決的一個重要問題是使構建的測量矩陣滿足RIP的理論特性.

3)測量數.在壓縮感知中，測量數和信號的稀疏度有密切的關系.例如高斯隨機測量矩陣需要的測量數為M≥cKlog(N/K)，貝努利隨機測量矩陣測量數為M≈2Kln(N)，部分正交測量矩陣測量數為M≥cK(log(N))6等.并且，測量數還與計算的復雜度、重構的精度緊密相關，例如先構建非自適應線性測量矩陣，再利用鏈追蹤算法恢復信號，需要的測量數為O(Klog2N)，相應算法復雜度為O(Klog2Nlog2K)［6］;或者先構建范德蒙德測量矩陣，再利用線性規劃算法恢復信號，需要2K個測量值來恢復稀疏度為k的信號［5］，相應的算法復雜度為O(K2).由上可知，測量數的控制貫穿于壓縮感知理論研究的整個過程，并且直接影響著無線傳感網絡的能耗.

2 基于不平衡擴展模型的分布式壓縮感知

2.1 分布式壓縮感知的網絡架構

不平衡擴展模型［5，9－10］是一種特殊的二部圖［11］，它廣泛應用于理論分析和實際問題的解決中，特別是在節點間的通信、降低編碼錯誤率和減小計算復雜度方面.本文將不平衡擴展模型應用到分布式壓縮感知中，設計基于不平衡擴展器的分布式傳感網絡模型，進一步討論計算復雜度、誤差和能耗等問題.

不平衡擴展模型包含頂點集和邊集，頂點集又可分為2個互不相交的子集，并且每條邊的2個頂點分屬不同的子集.定義一個(k，ε)不平衡擴展模型G=(A，B，E)，頂點子集A稱為數據節點集合，頂點子集B稱為編碼節點集合，邊集E是數據節點向編碼節點傳輸數據的鏈路;其中，數據節點數編碼節點數，每個數據節點的度為d;設集合A的任意節點子集為使得數據節點子集的鄰域滿足，這里的ε是擴展常數.不平衡擴展模型是在m＜n的基礎上提出的，且m越小，不平衡的程度越大，信號恢復的難度也相應加大，因此，需要嚴格控制數據節點的度d和編碼節點數m.文獻［12］提出在k，ε，n＞0 時，存在普通常數 θ0＞0，使得數據節點的度滿足不等式:

頂點子集B的編碼節點數m滿足不等式:

另外，E可以用一個測量矩陣φ∈Rm×n(m?n)表示:

式中，i=1，2，…，m;j=1，2，…，n.

如果數據節點采集到的數據x∈Rn在某個轉換域內是k項稀疏，稀疏系數為s，可得到［14］

假使測量矩陣 φ∈Rm×n(m＜n)是由(3k，ε)不平衡擴展模型產生的，s1∈Rn是k項稀疏信號，s2∈Rn是2k項稀疏信號，φs1=φs2.存在信號z，滿足

那么z∈Rn是3k項稀疏信號.由式(4)得到可以推出s1=s2，‖z‖1=0.

由上可得(3k，ε)不平衡擴展模型產生的鄰接矩陣不存在3k項稀疏的零向量.即對于任意k項稀疏信號s1∈Rn，通過優化算法求出y=φs1的唯一解.

2.2 分布式算法

假設無線傳感網絡數據節點數為n，編碼節點數為m，不平衡擴展模型產生的稀疏測量矩陣φ∈Rn×m.在本文算法中，令第j個傳感器本地產生的隨機測量矩陣元素和傳輸數據分別為φij和xj，從而每個編碼節點計算和存儲的數據相應為.分布式算法流程如圖1所示，具體的步驟如下:

圖1 分布式算法流程

①數據節點j在本地產生稀疏度為k的隨機二值向量{φ1j，φ2j，…，φmj}.當 φij=1 時，數據節點j把采集的數據xj傳送到編碼節點i，編碼節點i保存xj;當φij=0時，數據節點不做任何操作，直至完成所有的j(1≤j≤n)操作.

②當編碼節點對接收到的所有數據值進行累加求和后，若融合節點對編碼發送請求，則編碼節點發送數據.

本文中設定數據節點的度d=2，即測量矩陣φ中每一列的非零個數為2，因此，數據節點j本地生成列向量{φ1j，φ2j，…，φmj}的稀疏度為k(k=2m).根據重構誤差需要適當調整編碼節點數，但由于數據節點產生稀疏向量的稀疏度k是確定的，因此增加編碼節點數并不影響數據節點與編碼節點之間的通信量.但假設數據節點j本地產生的是高斯列向量{φ1j，φ2j，…，φmj}，則需要傳送m次數據，當增加編碼節點的個數，節點間的通信量也隨著增加.從上述分析可得:①無線傳感網絡的傳輸任務分散在各個數據節點上，避免了使用多跳路由技術引起的距離融合中心近局部節點失效的問題;②由于不平衡擴展模型將輸入節點分為數據節點與編碼節點，分別完成編碼與存儲步驟，將傳輸和計算任務平均分散在各個節點，從而極大地提高了輸入節點的工作效率，避免了常規方法節點編碼過程中部分節點工作的不平衡問題.

3 融合節點中數據的重構算法

對于二維信號x∈Rn×n，定義［13－15］

則x每一點離散梯度的幅值和為

然后可以通過搜索最小求解x，即

式(9)可重寫為

定義不等式函數，用標準的對數障礙法將式(10)轉化成一系列線性約束函數，即

其中，τl＞ τl－1，隨著 τl增大，式(11)的解xl逼近式(10)的解x*.具體解決步驟為:

① 輸入可行的初始點x0，t0，偏差η，參數μ=10，初始值 τ1，l=1.

② 再利用① 求解的xl－1作為初始點，采用全變量牛頓法解式(11)，得到xl，其中l為已迭代的次數.

③ 如果n/τl＜η，結束程序并輸出xl.否則設置 τl+1= μτl，l=l+1，重復②.

④ 如果迭代次數，則跳出循環并輸出xl.

4 實驗仿真和分析

為驗證基于不平衡擴展模型的分布式壓縮感知網絡的可行性，本文設定在開放的無限環境中，存在水平往右風向，構建一個從初始時刻以一定擴散系數向四周散發煙氣的火源點，在32 m×32 m的平面中構建基于不平衡擴展模型的無線傳感網絡，整個平面均勻分布著n=1 024個氣體傳感器節點.為了能夠證明不平衡擴展模型應用在分布式壓縮感知上，可以提高計算效率和降低網絡系統的能耗，首先，將對無線傳感網絡進行能耗分析，在此基礎上，通過實驗比較重構信號的均方誤差和信噪比，證明不平衡擴展網絡模型不僅可以節省網絡能耗，而且較好地保證了信號的重構性能.

4.1 分布式傳感網絡能耗分析

在無線傳感器網絡中，由于傳感器節點需要電池供電，因此降低節點能耗成為組建無線傳感網絡優先考慮的因素.本文構建的基于不平衡模型的分布式壓縮感知正是針對無線傳感網絡節點能耗大提出的，而傳感器節點耗電的模塊有傳感模塊、處理器模塊和無線通信模塊.

1)處理器模塊能耗.常用的高斯隨機測量向量中的元素值需要與數據值做相乘運算，再將得到的結果進行傳輸，因此每個數據節點都需要進行相乘運算并傳輸數據;但本文構建的網絡模型的每個傳感節點只需檢測產生的稀疏測量向量元素是否為1，從而決定是否傳輸數據;比較兩者，本文構建的網絡模型最終通過減少處理器模塊的計算量來實現運算能耗的降低.

2)無線通信模塊.傳感器節點的絕大部分能量消耗在無線通信模塊上，因此無線通信模塊設計的合理程度決定節點能耗的大小.在利用高斯隨機向量時，單個數據節點需要發送的數據包個數為m，因此無線通信模塊要消耗大量能量.本文中，盡管使用了稀疏隨機測量矩陣，但由于其多值性，測量矩陣的非零項元素以概率出現，所以每個數據節點平均傳送的數據包的個數為O(logn)，在大規模傳感網絡中，n值一般較大，數據包的傳送個數也相應較大.本文從減少節點間通信的數據量出發，將單個數據節點產生的二值向量的稀疏度設定為k(本文中k=8，設置為4，6，16等整數對結果影響不大)，在減少重構誤差的情形下，增加編碼節點數并不會導致數據節點與編碼節點間通信量的增大，因為單個數據節點只傳輸k個數據包，在大規模傳感網絡中，顯然有k＜O(logn)［5］.所以本文構建的基于不平衡擴展模型的分布式壓縮感知網絡不僅能通過增加編碼節點數使信號的重構誤差減小，而且它在節能方面尤為突出.

4.2 網絡模型重構性能分析

由于常用的高斯測量矩陣具有高效壓縮信號和重構誤差小的優點，因此用該矩陣與本文中網絡模型構建的稀疏測量矩陣進行對比，論證本文模型的合理性.其步驟如下:①對信號進行測量和重建仿真;②對比信號的重建質量，其中信號重建的質量評價標準包括信噪比和均方誤差.假設一個m×n的原始信號x，算法所重建的信號為，則

1)信噪比

2)均方誤差

本文中測量矩陣產生的原理與參數設置如下:①高斯隨機測量矩陣參數設置.每個數據節點隨機產生m=512個高斯向量.②稀疏測量矩陣參數設置.每個數據節點產生稀疏度k=8，長度為512的二值向量.

考慮在有噪聲環境下數據在傳輸過程中總有乘性或加性的噪聲污染，為更好模擬實際環境，在數據節點傳輸數據的過程中添加了均值為0、方差為1的高斯白噪聲，并分別利用高斯測量矩陣和稀疏測量矩陣對火源點在不同位置的數據樣本進行測量以及重構，從而獲得在不同火源點上信號重構的信噪比和均方誤差值，如表1所示.從表1可以看出，在采用不平衡擴展模型提高計算效率、降低能耗的基礎上，在同一數據樣本集下，稀疏測量矩陣與高斯測量矩陣相比，獲得的測量值都能完美重構原信號，所得到重構信號的信噪比和均方誤差都無明顯差別.

表1 火源點處于不同位置情況下測量矩陣性能比較

從圖2可看出，隨著測量數增大，在稀疏隨機矩陣和高斯隨機矩陣下重構的信噪比都呈遞增趨勢，但前者比后者的趨勢更為明顯.從圖3同樣可以看出，在測量數較小(即小樣本時)且存在高斯噪聲的情況下，稀疏隨機矩陣同樣表現出較好的重構性能，即在這種情況下，稀疏隨機矩陣優化算法依然顯示出其算法上的優越性.

圖2 測量數與信噪比的關系曲線

圖3 測量數與均方誤差的關系曲線

5 結語

針對大規模無線傳感網絡在火災信息收集中的節點能量有限和帶寬有限問題，提出基于不平衡擴展模型的分布式壓縮感知網絡，進而把數據的傳輸任務均衡分布于各個數據節點間.通過算法的理論分析和網絡的能耗分析表明，該網絡模型在減少數據節點運算量和數據節點與編碼節點間數據傳輸量的同時，較大地節省了功耗，延長了傳感網絡的工作壽命.實驗的仿真結果也表明，本文中構建的網絡模型應用在有噪環境中有著較好的重構性能.在本文中，只利用了無線傳感網絡節點間的空間相關性進行數據壓縮與重構，下一步的研究應考慮如何在結合時間相關性和空間相關性的基礎上建立模型，進一步減小節點間數據傳輸量的同時提高信號的重構性能.

［1］Mhmudimanesh M，Khelil A，Suri N.Reordering for better compressibility:efficient spatial sampling in wireless sensor networks［C］//The Third IEEE International Conference on Sensor Network，Ubiquitous，and Trustworthy Computing.Newport Beach，CA，USA，2010:50－57.

［2］Hu Haifeng，Yang Zhen.Spatial correlation-based distributed compressed sensing in wireless sensor networks［C］//Wireless Communications Networking and Mobile Computing.Chengdu，China，2010:1－4.

［3］Luo Chong，Wu Feng，Sun Jun，et al.Compressive data gathering for large-scale wireless sensor networks［C］//Proceedings of the15th Annual International Conference on Mobile Computing and Network. Beijing， China，2009:145－156.

［4］Wang Wei，Garofalakis M，Ramchandran K W.Distributed sparse random projections for refinable approximation［C］//Proceedings of the Sixth International Symposium on Information Processing in Sensor Networks.Cambridge，MA，USA，2007:331－339.

［5］Sipser M，Spielman D A.Expander codes［J］.IEEE Transaction on Information Theory，1996，42(6):1710－1722.

［6］Berinde R，Gilbert A C，Indyk P，et al.Combining geometry and combinatorics:a unified approach to sparse signal recovery［C］//46th Annual Allerton Conference on Communication，Control，and Computing.Urbana-Champaign，IL，USA，2008:798－805.

［7］Xu Weiyu，Hassibi Babak.Efficient compressive sensing with deterministic guaranteesusing expandergraphs［C］//IEEE Information Theory Workshop.Tahoe City，CA，USA，2007:414－419.

［8］Otero Daniel，Arce Gonzalo R.Generalized restricted isometry property for alpha-stable random projections［C］//IEEE International Conference on Acoustics，Speech and Signal Processing.Prague，Czech Republic，2011:3676－3679.

［9］Yuen K，Liang B，Li B.A distributed framework for correlated data gathering in sensor network［J］.IEEE Trans-actions on Vehicular Technology，2008，57(1):578－593.

［10］Jafarpour Sina，Xu Weiyu，Hassibi Babak，et al.Efficient and robust compressed sensing using optimized expander graphs［J］.IEEE Transactions on Information Theory，2009，55(9):4299－4308.

［11］Lan Lihui，Ju Shiguang，Jin Hua.Anonymizing social network using bipartite graph［C］//Information Sciences on Computational and International Conference.Washington，DC，USA:IEEE Computer Society，2010:993－996.

［12］de Castro Yohann.Error prediction and variable selection via unbalance［J］.Statistics Theory，2010，4:1－15.

［13］Emmanuel Candes，Romberg Justin.L1-MAGIC:recovery of sparse signals via convex programming［EB/OL］.(2009-01-22)［2011-08］.http://users.ece.gatech.edu/justin/l1magic/downloads/l1magic.pdf.

［14］石光明，劉丹華，高大化，等.壓縮感知理論及研究進展［J］.電子學報，2009，37(5):1070－1081.

Shi Guangming，Liu Danhua，Gao Dahua，et al.Advances in theory and application of compressed sensing［J］.Acta Electronica Sinica，2009，37(5):1070－1081.(in Chinese)

［15］Kang Jian，Tang Liwei，Zuo Xianzhang，et al.Distributed compressed sensing-based data fusion in sensor networks［C］//First International Conference on Pervasive Computing Signal Processing and Applications.Harbin，China，2010:1083－1086.

Distributed compressed fire signal sensing based on unbalance expander

Zhuang Zhemin1Wu Like1Lu Xiaobo2

(1Department of Electronics，Shantou University，Shantou 515063，China)
(2School of Automation，Southeast University，Nanjing 210096，China)

In wireless sensor networks，the huge power consumption of part of nodes brings great hardship for various applications，which is caused by the unbalanced data transmission and calculation.To solve this problem，using bipartite graph thought in graph theory，distributed compressive sensing network architecture based on unbalanced expander is proposed.Meanwhile the distributed algorithm corresponding to the architecture is designed.This algorithm decides whether or not to transmit data through a fixed column sparse degree sparse random bipartite matrix，then decentralize the transmission and calculation mission to every node equally and reconstruct the data in fusion center by using secondorder cone programming.Finally the distributed compressive sensing network based on unbalanced expander is applied to the fire ground simulation experiment and the superiority of the algorithm and the energy conservation of the network are analyzed in detail.In the process of simulation，through analysis of the mean square error and signal-to-noise ratio，it is proved that the proposed model not only has good effect on reducing nodes'energy consumption but also ensures the performance for the signal reconstruction in noisy case.

wireless sensor networks;distributed compressive sensing;unbalance expander model;sparse measurement matrix

TP393

A

1001－0505(2013)01-0039-06

10.3969/j.issn.1001－0505.2013.01.008

2012-06-21.

莊哲民(1965—)，男，博士，教授，zmzhuang@stu.edu.cn.

國家自然科學基金面上資助項目(61070152)、廣東省重大科技計劃項目資金資助項目(2011A080404005)、汕頭大學科研基金資助項目(NTF10012).

莊哲民，吳力科，路小波.基于不平衡擴展模型的火災信息分布式壓縮感知［J］.東南大學學報:自然科學版，2013，43(1):39－44.［doi:10.3969/j.issn.1001－0505.2013.01.008］