適用于無線傳感器網絡的層次化分布式壓縮感知

程銀波 司菁菁 候肖蘭

?

適用于無線傳感器網絡的層次化分布式壓縮感知

程銀波 司菁菁*候肖蘭

(燕山大學信息科學與工程學院 秦皇島 066004)

分布式壓縮感知(Distributed Compressed Sensing, DCS)是在無線傳感器網絡(Wireless Sensor Network, WSN)中減少數據傳輸量、降低能量消耗的有效手段。該文面向分簇WSN，提出層次化分布式壓縮感知(Hierarchical Distributed Compressed Sensing, HDCS)。在利用簇內DCS消除簇內時間、空間冗余的基礎上，利用簇間DCS消除簇間空間冗余，減少簇頭的數據發(fā)送量。針對分簇WSN采集信號的結構化稀疏特性，建立塊稀疏簇內聯合稀疏模型與塊稀疏簇間聯合稀疏模型，提出HDCS觀測方案與層次化聯合重構算法。仿真結果表明，與普通DCS相比，HDCS在保證重建信號質量的同時，能夠有效減輕簇頭的通信負擔，并顯著降低Sink上的信號重構時間。

無線傳感器網絡；分布式壓縮感知；層次化分布式壓縮感知；分簇

1 引言

有效的分簇結構能夠提高無線傳感器網絡(Wireless Sensor Network, WSN)[1,2]的資源利用率、降低路由復雜度、增強網絡穩(wěn)定性[3,4]。研究表明，在分簇WSN中應用壓縮感知(Compressed Sensing, CS)[5]或分布式壓縮感知(Distributed Compressed Sensing, DCS)[6]技術能夠有效降低網絡中的數據傳輸能耗、延長網絡的工作壽命。然而，現有的研究成果主要基于CS/DCS實現分簇WSN中簇內成員采集數據的壓縮以及簇頭生成(或接收到)的CS/ DCS壓縮數據向Sink的多跳匯聚。例如，文獻[7]研究CS與分簇算法的融合，在分簇算法的基礎上應用CS技術壓縮簇內成員采集的數據，減少網絡中的數據傳輸量。文獻[8]在混合CS模型下研究簇的大小與傳輸數據量的關系。文獻[9-11]研究簇頭CS數據的簇間多跳、多分辨率、層次化路由策略。實際上，在同一監(jiān)測區(qū)域內，不但簇內成員采集的數據間具有時間、空間相關性，相鄰簇間也具有很強的空間相關性。如果能夠在利用DCS去除簇內成員采集數據的時間、空間冗余的基礎上，對各簇簇頭采集到的數據繼續(xù)進行壓縮，去除簇間冗余，則有望進一步降低簇頭的通信負擔，延長網絡的工作壽命。

針對這一問題，本文面向分簇WSN，提出層次化分布式壓縮感知(Hierarchical Distributed Compressed Sensing, HDCS)。首先，研究層次化聯合稀疏模型的構建，利用簇內聯合稀疏模型描述簇內成員采集數據的時間相關性與空間相關性，利用簇間聯合稀疏模型描述同一監(jiān)測區(qū)域內各簇采集數據的空間相關性。進而，研究HDCS的層次化觀測方案，并基于WSN采集信號的結構化稀疏特性，提出HDCS的層次化聯合重構方案。在保證信號重建質量的同時，盡可能減少簇頭轉發(fā)的數據量。最后，利用合成信號和實際WSN測得的溫度信號分析HDCS的性能，并與普通DCS進行比較。

2 問題模型

3 層次化分布式壓縮感知

聯合稀疏模型(Joint Sparsity Model, JSM)的建立是DCS的一個關鍵問題。本文基于分簇WSN中傳感器采集數據的結構化稀疏特性，構建簇內JSM與簇間JSM，并在此基礎上研究簇內DCS與簇間DCS。

3.1 簇內DCS

3.2 簇間DCS

表1 joint BOMP算法的偽代碼

3.2.2 簇間JSM 實驗中發(fā)現，簇頭重建的簇內公共成分系數向量與成員特有成分系數向量仍然具有分塊稀疏特性。據此，本文在混合支撐集模型[13]的基礎上構建塊稀疏簇間JSM，描述同一監(jiān)測區(qū)域內個簇簇內公共成分系數向量的相關性。將建模成簇間公共成分與簇特有成分之和的形式，即

(6)

3.3 HDCS的層次化聯合重構

進一步，本文針對塊稀疏簇間JSM，設計了joint BPMMPIP算法(偽代碼如表2所示)，用于實現的聯合重構。根據式(5)所示的觀測過程，若以傳感矩陣、列塊集合、索引集、觀測向量、簇間公共塊稀疏度、各簇特有塊稀疏度、擴張路徑數、剪枝操作開始的層數和剪枝比例作為輸入，則可基于joint BPMMPIP算法輸出的重構出。

4 傳輸能耗與重建復雜度分析

(1)數據傳輸量分析：設同一監(jiān)測區(qū)域內的個簇中各包含個成員節(jié)點，每個成員單位時間段內采集信號的長度為、生成的觀測值數量為。在HDCS中，每個簇內的個成員需要向簇頭傳輸的總觀測值數量為，與普通DCS相同。若設每個簇頭在進行簇間DCS觀測時生成個簇間公共成分觀測值和個成員特有成分觀測值，則個簇頭需要向Sink傳輸的總觀測值數量為，而在普通DCS方案中，個簇頭需要向Sink匯聚的總觀測值數量為。將與之比表示為

(2)傳輸能耗分析：HDCS與普通DCS的簇內數據傳輸能耗相同，因此本文主要比較兩方案的簇頭數據傳輸能耗。結合文獻[9,11,15,16]中的能耗分析模型，HDCS方案中個簇頭上的數據傳輸總能耗與普通DCS方案中個簇頭上的數據傳輸總能耗可分別表示為

(9)

表2 joint BPMMPIP算法的偽代碼

5 仿真結果與分析

編寫Matlab仿真程序，分別利用隨機合成信號和Intel Berkeley Research Lab真實WSN測得的溫度信號(來自http://db.csail.mit.edu/labdata/ labdata.html)測試本文提出的HDCS的性能，并與普通DCS進行比較。實驗中HDCS采用3種不同的實現方案。方案1利用joint BOMP實現簇內、簇間重構；方案2利用joint BOMP實現簇內重構、利用joint BPMMPIP實現簇間重構；方案3利用joint BPMMPIP實現簇內、簇間重構。在普通DCS方案中，簇內成員的觀測與Sink的重構采用與HDCS方案1中的簇內觀測與簇內重構相同的方法。本文在采樣率相同、傳輸數據量之比的情況下，比較HDCS與普通DCS的重建效果；在采樣率相同、重建效果相同的情況下，通過計算值比較HDCS與普通DCS需要在網絡中傳輸的數據量。仿真計算機的硬件配置為CPU AMD athlon(tm)255，主頻3.11 GHz，內存1.75 GB。軟件環(huán)境為32位Windows7操作系統下的Matlab R2010a。實驗在每個指定采樣率下重復進行100次。以歸一化均方誤差(Normalized Mean Squared Error, NMSE)作為衡量算法重建效果的指標。

由圖1可見，隨著采樣率的增加，4種方案的NMSE值均逐漸降低。在相同采樣率下，HDCS方案的NMSE值要低于普通DCS，且HDCS方案1，方案2，方案3的NMSE值依次降低。這說明，當簇頭傳輸數據量相同時，HDCS具有優(yōu)于普通DCS的重建性能，而且HDCS方案3的重建性能優(yōu)于方案2，方案2的性能優(yōu)于方案1。由圖2可見，在達到相同NMSE值時，HDCS需要在網絡中傳輸的數據量明顯低于普通DCS。而且，隨著采樣率的增加，HDCS與普通DCS需傳輸的數據量之比逐漸降低。例如，當采樣率為0.3時，HDCS方案1，方案2，方案3需要在網絡中傳輸的數據量僅為普通DCS的73.5%, 60.2%和57.6%。

接下來，采用Intel Berkeley Research Lab真實WSN測得的溫度值進行實驗。選取小空間范圍內的傳感器1~30，將傳感器1~5, 6~10, 11~15, 16~20, 21~25, 26~30組成6個簇。將日期2004.03.01-2004.03.07測得的溫度值每隔3.5 min采樣一個點，得到長度為2048的信號。選取sym8小波基作為,和，將,,構造成元素符合高斯分布且每一行經過歸一化處理的隨機矩陣。圖3顯示了當時，3種HDCS方案和普通DCS在相同采樣率下獲得的NMSE值的對比情況。圖4顯示了達到相同的NMSE值()時，3種HDCS方案需要在網絡中傳輸的數據量分別相對于普通DCS的歸一化值，即值。

由圖3可見，當簇頭傳輸數據量相同時，HDCS的NMSE值低于普通DCS，即HDCS具有優(yōu)于普通DCS的重建性能。由圖4可見，當獲得相同的NMSE值時，HDCS需要在網絡中傳輸的數據量要顯著低于普通DCS，而且隨著采樣率的增加，相對值越來越小。例如，當采樣率為0.3時，HDCS方案1，方案2，方案3需要在網絡中傳輸的數據量僅為普通DCS的77.1%, 53.5%和42.2%。

圖1 合成數據實驗中數據量相同時4種方案的NMSE值比較

圖2 合成數據實驗中當時3種HDCS方案的值比較

圖3 實際數據實驗中數據量相同時4種方案的NMSE值比較

圖4 實際數據實驗中當時3種HDCS方案的值比較

最后，比較HDCS與普通DCS在Sink上的重構時間。表3、表4分別展示了在采用合成數據與實際數據進行的實驗中，當時，在部分采樣率下，HDCS方案1，方案2在Sink的重構時間與普通DCS重構時間的比值。HDCS方案3采用的簇間重構算法與方案2相同，因此其在Sink的重構時間與方案2相同。由表3、表4可見，HDCS的重構時間顯著低于普通DCS。此外，表3、表4還表明HDCS方案1的重構時間低于方案2，即joint BOMP算法的運行時間低于joint BPMMPIP算法。

表3 合成數據實驗中HDCS與普通DCS重構時間之比

采樣率0.140.180.220.260.30 HDCS方案10.03300.03540.03670.03740.0412 HDCS方案20.27070.29600.31830.34000.3750

表4 實際數據實驗中HDCS與普通DCS重構時間之比

采樣率0.140.180.220.260.30 HDCS方案10.00850.00970.01100.01220.0131 HDCS方案20.28200.29300.31200.34500.3730

綜合上述仿真實驗結果可見，與普通DCS相比，本文提出的HDCS在保證重建信號質量的同時，能夠明顯降低分簇WSN中簇頭的數據傳輸量，并顯著降低Sink上的信號重構時間。比較本文提出的joint BOMP算法與joint BPMMPIP算法可見，joint BOMP算法的運算時間較低，而joint BPMMPIP算法的聯合重建性能較高。比較3種HDCS實現方案可見，方案1的重構時間最低，方案3的聯合重構性能最高，而方案2能夠在簇頭運算時間與Sink節(jié)點重構性能方面獲得較好的折中。

6 結束語

本文基于分簇WSN的空間結構特性以及傳感器采集數據的結構化稀疏特性研究HDCS。在利用簇內DCS聯合去除簇內成員采集數據的時間冗余與空間冗余的同時，利用簇間DCS去除同一監(jiān)測區(qū)域內多個簇采集數據的空間冗余。構造了塊稀疏簇內JSM，并提出了簇內DCS重構算法joint BOMP；構造了塊稀疏簇間JSM，并提出了簇間DCS重構算法joint BPMMPIP。利用合成信號與WSN實測溫度信號進行的仿真實驗表明，與普通DCS相比，當網絡傳輸數據量相同時，HDCS能夠獲得更高的重建效果；當重建效果相同時，HDCS能夠明顯降低簇頭的數據發(fā)送量。此外，與普通DCS相比，HDCS顯著降低了Sink上的信號重建時間。

由于實驗條件的限制，本文主要利用計算機仿真實驗對HDCS方案進行了驗證與性能分析，HDCS在實際WSN上的實現與性能分析有待進一步研究。另一方面，本文設計的HDCS方案需要簇頭進行簇內重構與簇間觀測，因此簇頭的計算任務要高于普通DCS。接下來將研究簇頭對簇內采集數據的二次觀測，以減輕簇頭的計算負擔。此外，如何在塊稀疏度未知的情況下實現HDCS重構也是一個需要繼續(xù)研究的問題。

[1] CHEN H, SHI Q, TAN R,. Mobile element assisted cooperative localization for wireless sensor networks with obstacles[J]., 2010, 9(3): 956-963. doi: 10.1109/TWC. 2010.03.090706.

[2] CHEN H, GAO F, MARTINS M,. Accurate and efficient node localization for mobile sensor networks[J]., 2013, (18): 141-147. doi: 10.1007/s11036-012-0361-7.

[3] PRASATH K and SHANKAR T. RMCHS: ridge method based cluster head selection for energy efficient clustering hierarchy protocol in WSN[C]. Proceedings of International Conference on Smart Technologies and Management for Computing, Communication, Controls, Energy and Materials, Chennai, India, 2015: 64-70.

[4] 唐宏, 王惠珠. 基于無線信號不規(guī)則性的無線傳感網層次型拓撲控制算法[J]. 電子與信息學報, 2015, 37(9): 2246-2253. doi: 10.11999/JEIT141626.

TANG Hong and WANG Huizhu. Wireless signal irregularity based hierarchical topology control algorithm for wireless sensor networks[J].&, 2015, 37(9): 2246-2253. doi: 10.11999/ JEIT141626.

[5] DONOHO D. Compressed sensing[J]., 2006, 52(4): 1289-1306. doi: 10.1109/ TIT.2006.871582.

[6] BARON D, DUARTE M, SARVOTHAM S,. An information-theoretic approach to distributed compressed sensing[C]. Proceedings of the 43rd Allerton Conference on Communication, Control, and Computing, Monticello, USA, 2005: 814-825.

[7] NGUYEN M and RAHNAVARD N. Cluster-based energy- efficient data collection in wireless sensor networks utilizing compressive sensing[C]. Proceedings of IEEE Military Communication Conference, San Diego, USA, 2013: 1708-1713.

[8] XIE R and JIA X. Transmission-efficient clustering method for wireless sensor networks using compressive sensing[J]., 2014, 25(3): 806-815. doi: 10.1109/TPDS.2013.90.

[9] NGUYEN M, TEAGUE K, and RAHNAVARD N. Inter- cluster multi-hop routing in wireless sensor networks employing compressive sensing[C]. Proceedings of IEEE Military Communication Conference, Baltimore, USA, 2014: 1133-1138.

[10] XU X, ANSARI R, KHOKHAR A,. Hierarchical data aggregation using compressive sensing(HDACS) in WSNs[J]., 2015, 11(3): 1-25. doi: 10.1145/2700264.

[11] LIU D, ZHOU Q, ZHANG Z,. Cluster-based energy- efficient transmission using a new hybrid compressed sensing in WSN[C]. Proceedings of IEEE Conference on Computer Communications Workshops, San Francisco, USA, 2016: 372-376.

[12] ELDAR Y, KUPPINGER P, and BOLCSKEI H. Block- sparse signals: Uncertainty relations and efficient recovery[J]., 2010, 58(6): 3042-3054. doi: 10.1109/TSP.2010.2044837.

[13] SUNDMAN D, CHATTERJEE S, and SKOGLUND M. Distributed greedy pursuit algorithms[J]., 2014, 105(12): 298-315. doi: 10.1016/j.sigpro.2014.05.027.

[14] 司菁菁, 候肖蘭, 程銀波. 基于塊剪枝多路徑匹配追蹤的多信號聯合重構[J]. 系統工程與電子技術, 2016, 38(9): 1993-1999. doi: 10.3969/j.issn.1001-506X.2016.09.05.

SI Jingjing, HOU Xiaolan, and CHENG Yinbo. Joint multi-signal reconstruction based on block pruning multipath matching pursuit[J]., 2016, 38(9): 1993-1999. doi: 10.3969/j.issn.1001-506X.2016. 09.05.

[15] CHEN H, LIU B, HUANG P,. Mobility-assisted node localization based on TOA measurements without time synchronization in wireless sensor networks[J]., 2012, 17(1): 90-99. doi: 10.1007/s11036-010-0281-3.

[16] CHEN H, WANG G, WANG Z,. Non-line-of-sight node localization based on semi-definite programming in wireless sensor networks[J]., 2012, 11(1): 108-116. doi: 10.1109/TWC. 2011.110811.101739.

Hierarchical Distributed Compressed Sensing for Wireless Sensor Network

CHENG Yinbo SI Jingjing HOU Xiaolan

(,,066004,)

Distributed Compressed Sensing (DCS) is an effective means to reduce the amount of data transmission and energy consumption in Wireless Sensor Network (WSN). Hierarchical Distributed Compressed Sensing (HDCS) is proposed for clustering WSN. It eliminates the temporal-spatial redundancies among data collected by the cluster members with the intra-cluster DCS, and eliminates the spatial redundancies among clusters with the inter-cluster DCS. According to the signal’s structured sparsity, a block-sparse intra-cluster joint sparsity model and a block-sparse inter-cluster joint sparsity model are constructed. Then, a hierarchical measurement scheme and a hierarchical joint reconstruction scheme are proposed for HDCS. Experimental results show that compared to general DCS, HDCS can relieve the transmission burden in the network effectively, without lowering the quality of the reconstructed signal. Moreover, it can reduce the signal reconstruction time at the Sink observably.

Wireless Sensor Network (WSN); Distributed Compressed Sensing (DCS); Hierarchical Distributed Compressed Sensing (HDCS); Cluster

TP393

A

1009-5896(2017)03-0539-07

10.11999/JEIT160439

2016-05-03；改回日期：2016-11-23；

2017-01-11

司菁菁 sjj@ysu.edu.cn

國家自然科學基金(61471313, 61303128)，河北省自然科學基金(F2014203183)，燕山大學青年教師自主研究計劃課題(13LGB015)，秦皇島市科學技術研究與發(fā)展計劃(201602A031)

The National Natural Science Foundation of China (61471313, 61303128), The Natural Science Foundation of Hebei Province (F2014203183), The Youth Foundation of Yanshan University (13LGB015), The Science and Technology Plan of Qinhuangdao (201602A031)

程銀波： 男，1978年生，講師，研究方向為分布式計算.

司菁菁： 女，1980年生，副教授，研究方向為多媒體通信與信號處理.

候肖蘭： 女，1988年生，碩士生，研究方向為分布式壓縮感知.