程銀波 司菁菁 候肖蘭

?

適用于無線傳感器網(wǎng)絡(luò)的層次化分布式壓縮感知

程銀波 司菁菁*候肖蘭

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

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

無線傳感器網(wǎng)絡(luò)；分布式壓縮感知；層次化分布式壓縮感知；分簇

1 引言

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

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

2 問題模型

3 層次化分布式壓縮感知

聯(lián)合稀疏模型(Joint Sparsity Model, JSM)的建立是DCS的一個(gè)關(guān)鍵問題。本文基于分簇WSN中傳感器采集數(shù)據(jù)的結(jié)構(gòu)化稀疏特性，構(gòu)建簇內(nèi)JSM與簇間JSM，并在此基礎(chǔ)上研究簇內(nèi)DCS與簇間DCS。

3.1 簇內(nèi)DCS

3.2 簇間DCS

表1 joint BOMP算法的偽代碼

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

(6)

3.3 HDCS的層次化聯(lián)合重構(gòu)

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

4 傳輸能耗與重建復(fù)雜度分析

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

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

(9)

表2 joint BPMMPIP算法的偽代碼

5 仿真結(jié)果與分析

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

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

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

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

圖1 合成數(shù)據(jù)實(shí)驗(yàn)中數(shù)據(jù)量相同時(shí)4種方案的NMSE值比較

圖2 合成數(shù)據(jù)實(shí)驗(yàn)中當(dāng)時(shí)3種HDCS方案的值比較

圖3 實(shí)際數(shù)據(jù)實(shí)驗(yàn)中數(shù)據(jù)量相同時(shí)4種方案的NMSE值比較

圖4 實(shí)際數(shù)據(jù)實(shí)驗(yàn)中當(dāng)時(shí)3種HDCS方案的值比較

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

表3 合成數(shù)據(jù)實(shí)驗(yàn)中HDCS與普通DCS重構(gòu)時(shí)間之比

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

表4 實(shí)際數(shù)據(jù)實(shí)驗(yàn)中HDCS與普通DCS重構(gòu)時(shí)間之比

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

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

6 結(jié)束語

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

由于實(shí)驗(yàn)條件的限制，本文主要利用計(jì)算機(jī)仿真實(shí)驗(yàn)對(duì)HDCS方案進(jìn)行了驗(yàn)證與性能分析，HDCS在實(shí)際WSN上的實(shí)現(xiàn)與性能分析有待進(jìn)一步研究。另一方面，本文設(shè)計(jì)的HDCS方案需要簇頭進(jìn)行簇內(nèi)重構(gòu)與簇間觀測(cè)，因此簇頭的計(jì)算任務(wù)要高于普通DCS。接下來將研究簇頭對(duì)簇內(nèi)采集數(shù)據(jù)的二次觀測(cè)，以減輕簇頭的計(jì)算負(fù)擔(dān)。此外，如何在塊稀疏度未知的情況下實(shí)現(xiàn)HDCS重構(gòu)也是一個(gè)需要繼續(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] 唐宏, 王惠珠. 基于無線信號(hào)不規(guī)則性的無線傳感網(wǎng)層次型拓?fù)淇刂扑惴╗J]. 電子與信息學(xué)報(bào), 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] 司菁菁, 候肖蘭, 程銀波. 基于塊剪枝多路徑匹配追蹤的多信號(hào)聯(lián)合重構(gòu)[J]. 系統(tǒng)工程與電子技術(shù), 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

國家自然科學(xué)基金(61471313, 61303128)，河北省自然科學(xué)基金(F2014203183)，燕山大學(xué)青年教師自主研究計(jì)劃課題(13LGB015)，秦皇島市科學(xué)技術(shù)研究與發(fā)展計(jì)劃(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年生，講師，研究方向?yàn)榉植际接?jì)算.

司菁菁： 女，1980年生，副教授，研究方向?yàn)槎嗝襟w通信與信號(hào)處理.

候肖蘭： 女，1988年生，碩士生，研究方向?yàn)榉植际綁嚎s感知.