基于壓縮感知與矩陣補全技術的WSN數據收集算法

張策，李鷗，童昕，楊延平

?

基于壓縮感知與矩陣補全技術的WSN數據收集算法

張策1，李鷗1，童昕2，楊延平3

（1. 信息工程大學信息系統工程學院，河南 鄭州 450001；2. 61377部隊，廣東 深圳 518000；3. 清華大學電子系，北京 100084）

WSN無線鏈路不可靠，分組丟失現象普遍存在，且基于壓縮感知（CS）數據收集算法對分組丟失十分敏感。首先，通過實驗對分組丟失率和基于CS數據重構精度關系進行定量研究，提出極稀疏塊觀測矩陣，在降低每輪數據采集能耗的同時，也保持觀測矩陣的近似低秩性質。其次，結合矩陣補全（MC）技術與CS技術，提出基于極稀疏塊觀測矩陣的壓縮感知數據收集算法，在一個采集周期內進行數據收集，利用MC技術恢復丟失數據，減少分組丟失對數據收集的影響；利用CS技術重構全網數據，減少數據收集量，降低節點在數據收集時所需能耗，延長網絡壽命。仿真分析表明，所提算法在分組丟失率小于50%的情況下能夠保證高精度重構全網數據，抵抗不可靠鏈路。

無線傳感網；數據收集；壓縮感知；不可靠鏈路；矩陣補全技術

1 引言

WSN因傳感器的低成本、小型化和低功耗等特點，在森林火災監測、戰場偵察等應用場景中具有巨大的應用前景。但由于傳感網監測環境復雜、無線鏈路質量低、分組丟失率較高且單個節點能源受限等原因，使WSN仍受到諸多限制。

近年來，面向不可靠鏈路的傳感網數據收集方法受到研究者的關注。文獻[1]提出經典丟失數據補全算法——KNN（K-nearest-neighbor）算法，KNN簡單地利用丟失數據的個最近鄰居數據，估計丟失數據，算法復雜度低但精度差。文獻[2]中提出的MSSA算法利用嵌入式自協方差矩陣，實現無參數和自適應數據恢復，被廣泛應用于恢復地理數據。這些算法在僅有少量數據丟失的情況下有效，但在鏈路十分不可靠的傳感網中，分組丟失率較高，此時，這些傳統的數據恢復算法性能較差。

隨著壓縮感知（CS, compressive sensing）理論[3,4]的提出，一些研究者開始將CS應用于WSN數據收集，利用原始數據的空間相關性，有效地減少數據傳輸能耗，且具有天然的能耗均衡特性，能克服能量洞問題，延長網絡壽命；基于壓縮感知的數據收集算法具有數據重構過程復雜但壓縮過程簡單的特點、適合傳感器節點低信息處理能力和能源受限的特點。文獻[5]基于壓縮感知，提出了CDG（compressive data gathering）算法，該算法利用數據的稀疏性和空間相關性，通過減少數據收集量有效地降低數據傳輸能耗。文獻[6]將CS技術與最小路徑樹路由協議相結合，以降低整個數據傳輸路徑上的能耗。文獻[7]為了減少葉節點和距離葉節點較近的中間節點的通信量，提出了混合壓縮感知（hybrid-CS）數據收集方法，僅對一部分通信量高的父節點使用壓縮感知技術，減少網絡數據通信量。文獻[8]結合CS技術與Leach分簇路由，計算全網最優簇首個數，使簇首均勻分布于網絡中，以減少網絡能耗。

以上基于CS數據收集算法在鏈路可靠的情況下，均可有效降低網絡能耗，且重構精度較高。但在實際傳感網中，由于節點部署環境復雜和節點收發數據功耗限制等因素，導致無線鏈路質量低、網內分組丟失率高。在分布式壓縮感知數據收集算法中，一個分組的丟失，會影響參與本次數據收集的所有節點，導致重構數據精度較低，重構數據無法使用。高分組丟失率使傳統的基于CS的數據收集算法失效。文獻[9]考慮了樹型路由中不可靠鏈路對壓縮感知的影響，所提算法設定參與數據收集的節點比例，在有分組丟失率的鏈路下，基于收到的數據分組構造觀測矩陣，不觀測發生分組丟失的節點，抵抗不可靠鏈路。但在該算法中，數據分組仍通過最短路由傳輸，能耗不均衡現象仍然存在。文獻[10]在簇型路由中，針對輕負載下的鏈路不可靠，建立隨機分組丟失模型，提出CS-NTSC（neighbor topology spatial correlation prediction based CS data gathering）算法，利用鄰居拓撲矩陣預測丟失數據，減小錯傳的影響；針對重負載下的鏈路不可靠，建立節點偽失效模型，并提出CS-SSDG（sparse schedule for CS data gathering）算法，通過改變觀測矩陣稀疏度，避免觀測出錯數據，弱化不可靠鏈路的影響。

矩陣補全（MC, matrix completion）技術是近幾年新興的一種技術，利用矩陣的低秩特性，恢復矩陣中丟失的數據，將MC技術應用于WSN數據收集，可以減少數據的采集量。文獻[11]單一地利用MC技術壓縮恢復數據，減少網絡通信量，延長網絡壽命；將MC數據恢復過程的NP-hard問題轉化為可解的、復雜度低的最優化問題。但該算法沒有分析真實數據的近似低秩性，且在樹型路由下，網絡能耗不均情況仍然存在。文獻[12]結合CS和MC，利用MC補全數據傳輸時丟失的數據，利用數據的時間相關性進行CS數據壓縮，達到抵抗不可靠鏈路、減少節點傳輸能耗的目的。但當網絡數據采集周期長、網內受同一事件影響時，節點采集數據的時間相關性會很弱、空間相關性強，在時間上進行CS數據壓縮，其恢復精度較低，且算法時間復雜度高。每個節點在采集完所有時隙的數據后進行數據處理傳輸，網絡時延大。

為此，本文在無線鏈路不可靠條件下，對一個采集周期的數據，利用MC技術恢復因鏈路不可靠丟失的數據；利用節點的強空間相關性，對節點數據進行CS壓縮，減少網絡的數據傳輸量。本文主要貢獻有以下3點。

1) 對一個時隙內的真實數據進行分析，實驗證明數據具有近似低秩的性質，且收集一個時隙內數據，以降低網絡時延。

2) 利用數據的低秩性質與空間相關性，將MC技術與CS技術相結合，提出極稀疏塊觀測矩陣，減小不可靠鏈路對數據重構的影響，在保證重構精度的前提下降低網絡能耗。

3) 采用GreenOrbs系統真實數據，利用仿真軟件Matlab對所提算法進行實驗驗證，實驗結果表明所提算法在鏈路具有50%分組丟失率情況下，仍能保證高重構精度。

2 問題描述

2.1 基于壓縮感知的分布式數據收集方法

網絡采用簇型路由結構，整個網絡劃分為若干個簇，在每個簇內使用壓縮感知技術進行數據收集，整個網絡的拓撲結構示意如圖1所示。

sink節點在收到觀測向量后，通過求解凸優化問題，求解全簇的觀測數據。

在數據傳輸過程中，由于復雜的監測環境、鏈路擁塞或沖突造成無線鏈路不可靠，存在一定的誤碼率與分組丟失率，對于誤碼率，當節點發生錯傳時，若接收節點通過信道譯碼無法恢復發生的錯傳位，接收節點將丟棄錯傳數據分組。本文假設節點一旦接收含錯數據分組即丟棄，不進行糾錯，因此，本文所假設的分組丟失率包含發生錯傳和丟失2種情況，節點未成功接收完整無錯的數據分組即分組丟失。在簇型網絡中，若節點的數據分組x丟失，則簇首得到的觀測向量為

本文用歸一化平均絕對誤差（NMAE, normalized mean absolute error）衡量數據重構誤差，即

2.2 矩陣補全技術

其中，，，指標集 。由于矩陣的秩函數是非連續、非凸的，求解式(5)是一個NP-hard問題，其求解復雜度呈指數級增長，最廣泛的做法是將秩函數凸松弛到核范數，轉換為凸優化問題，即

圖3 矩陣低秩特性

實驗結果表明，真實環境中傳感器感知原始數據具有近似低秩的特征，若節點在數據傳輸的過程中丟失有一定數量的分組，即無線鏈路存在分組丟失率，可以利用原始數據矩陣的低秩性質，通過MC技術，恢復出丟失的數據分組，減少分組丟失對數據傳輸的影響。

由于傳感網采集的數據陣為近似低秩矩陣，令

本文采用EDCA（efficient data collection approach）算法[11]求解式（10）。

3 算法設計

針對無線鏈路有分組丟失情況，提出基于極稀疏塊觀測矩陣的壓縮感知數據收集算法（CS-SBM, CS data gathering algorithm based on sparsest block measurement matrix），結合MC技術與CS技術，在不重傳的前提下，對一個采集周期數據進行數據收集，利用MC技術恢復丟失數據，減少分組丟失對數據收集的影響，利用CS技術重構全網數據，減少數據收集量，降低節點在數據收集時所需能耗，延長網絡壽命。

3.1 極稀疏塊觀測矩陣

在簇內，成員節點根據存儲的稀疏觀測向量元素是否為0來判斷是否參與本輪數據收集。在數據傳輸過程中若有分組丟失，則簇首收到的數據并不完整，此時可以利用MC技術恢復丟失數據。

其中，表示的第列。SBM矩陣使每輪數據收集僅有一個節點參與，降低了數據采集能耗，且觀測矩陣為全網原始矩陣的塊矩陣，保持了矩陣的低秩性。

其簇首收到的觀測向量的矩陣為

3.2 CS-SBM算法

CS-SBM算法流程如圖5所示，具體步驟如下。

⑦ end for

⑧ end for

? end for

圖5 CS-SBM算法流程

算法2 重構全網數據

4 仿真與分析

圖6 CS-SBM算法性能（M=625）

表1 參數設置

圖7 MC恢復精度與分組丟失率關系

圖8 不同觀測次數下算法性能

圖9 觀測次數與重構精度的關系（P=0.4）

5 結束語

本文構造了SBM矩陣，并采用FFT基作為稀疏基，通過仿真實驗可得，CS-SBM算法可以通過CS技術重構出全網數據，但并未理論證明SBM矩陣和FFT基滿足RIP條件，如何從數學角度嚴謹地證明所提SBM矩陣滿足RIP條件是下一步工作重點。

[1] COVER T, HART P. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967, 13(1): 21-27.

[2] ZHU H, ZHU Y, LI M, et al. SEER: metropolitan-scale traffic perception based on lossy sensory data[C]//IEEE INFOCOM 2009. 2009: 217-225.

[3] DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[4] BARANIUK R. Compressive sensing[J]. IEEE Signal Processing Magazine, 2007, 56(4): 4-5.

[5] LUO C, WU F, SUN J, et al. Compressive data gathering for large-scale wireless sensor networks[C]//The 15th Annual Int Conf on Mobile Computing and Networking. 2009: 145-156.

[6] LUO C, WU F, SUN J, et al. Efficient measurement generation and pervasive sparsity for compressive data gathering[J]. IEEE Transactions on Wireless Communications, 2010, 9(12): 3728-3738.

[7] LUO J, XIANG L, ROSENBERG C. Does compressed sensing improve the throughput of wireless sensor networks?[C]//IEEE International Conference on Communications (ICC 2010). 2010: 1-6.

[8] WU X, XIONG Y, HUANG W, et al. An efficient compressive data gathering routing scheme for large-scale wireless sensor networks[J]. Computers and Electrical Engineering, 2013, 39(6): 1935-1946.

[9] WU X, YANG P, JUNG T, et al. Compressive sensing meets unreliable link: sparsest random scheduling for compressive data gathering in lossy WSN[C]//The 15th ACM Int Symposium on Mobile Ad Hoc Networking and Computing. 2014: 13-22.

[10] 張策, 張霞, 李鷗, 等. 不可靠鏈路下基于壓縮感知的WSN數據收集算法[J]. 通信學報, 2016, 37(9): 131-141.

ZHANG C, ZHANG X, LI O, et al. Compressive sensing based data gathering algorithm over unreliable links in WSN[J]. Journal on Communications, 2016, 37(9): 131-141.

[11] CHENG J, JIANG H, MA X, et al. Efficient data collection with sampling in WSNs: making use of matrix completion techniques[C]// Global Telecommunications Conference. 2010: 1-5.

[12] FRAGKIADAKIS A, ASKOXYLAKIS I, TRAGOS E. Joint compressed-sensing and matrix-completion for efficient data collection in WSNs[C]//International Workshop on Computer Aided Modeling and Design of Communication Links and Networks. 2014: 84-88.

[13] CANDES E, RWCHT B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9(6): 717-772.

[14] CHENG J, YE Q, JIANG H, et al. STCDG: an efficient data gathering algorithm based on matrix completion for wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2013, 12(2): 850-861.

[15] LAKHINA A, PAPAGIANNAKI K, CROVELLA M, et al. Structural analysis of network traffic flows[J]. ACM SIGMETRICS Performance Evaluation Review, 2004, 32(1): 61-72.

[16] ZHANG Y, ROUGHAN M, WILLINGER W, et al. Spatio-temporal compressive sensing and internet traffic matrices[C]//ACM SIG COMM 2009 Conference on Data Communication. 2009: 267-278.

WSN data gathering algorithm based on compressivesensing and matrix completion technique

ZHANG Ce1, LI Ou1, TONG Xin2, YANG Yanping3

1. School of Information Systems Engineering, PLA Information Engineering University, Zhengzhou 450001, China 2. 61377 Unit, Shenzhen 518000, China 3. Department of Electronic Engineering, Tsinghua University, Beijing 100084, China

The unreliable links and packet losing are ubiquitous in WSN. The performance of data collection algorithm based on compressive sensing is sensitive to packet losing. Firstly, the relationship between packet loss rate and CS-based reconstruction precision was analyzed, and the sparsest block measurement (SBM) matrix was formulated to keep the data gathering consumption smallest and make sure the low-rank property of measurements. Then, combined with the matrix completion (MC) and compressive sensing (CS), the CS data gathering algorithm based on sparsest block measurement matrix (CS-SBM) algorithm was proposed. CS-SBM gathered data in a period and recovered the loss data based on MC to weaken the impact of packet loss on data gathering. CS-SBM reconstructed data based on CS to reduce measurement number and energy consumption and prolong the network lifetime. Simulation analysis indicates that the proposed algorithm reconstruct the whole data with high-accuracy under 50% packet loss rate, resisting unreliable links effectively.

WSN, data gathering, compressive sensing, unreliable link, matrix completion technique

TP393

A

2017-10-12；

2018-01-17

童昕，tongrour@foxmail.com

國家科技重大專項基金資助項目（No.2016zx03001010）

The National Science and Technology Major Project of China (No.2016zx03001010)

10.11959/j.issn.1000-436x.2018034

張策（1991-），男，四川南充人，信息工程大學博士生，主要研究方向為無線自組織網絡、無線傳感網與路由協議。

李鷗（1961-），男，陜西寶雞人，博士，信息工程大學教授、博士生導師，主要研究方向為無線傳感網、認知無線電網絡與無線自組織網絡。

童昕（1990-），女，湖北黃岡人，61377部隊助理工程師，主要研究方向為多天線信號聯合處理。

楊延平（1986-），男，河南平頂山人，清華大學博士后，主要研究方向為無線認知通信、網絡編碼、自適應調制。