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

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

?

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

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

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

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

無線傳感網(wǎng)；數(shù)據(jù)收集；壓縮感知；不可靠鏈路；矩陣補全技術(shù)

1 引言

WSN因傳感器的低成本、小型化和低功耗等特點，在森林火災(zāi)監(jiān)測、戰(zhàn)場偵察等應(yīng)用場景中具有巨大的應(yīng)用前景。但由于傳感網(wǎng)監(jiān)測環(huán)境復(fù)雜、無線鏈路質(zhì)量低、分組丟失率較高且單個節(jié)點能源受限等原因，使WSN仍受到諸多限制。

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

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

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

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

為此，本文在無線鏈路不可靠條件下，對一個采集周期的數(shù)據(jù)，利用MC技術(shù)恢復(fù)因鏈路不可靠丟失的數(shù)據(jù)；利用節(jié)點的強空間相關(guān)性，對節(jié)點數(shù)據(jù)進(jìn)行CS壓縮，減少網(wǎng)絡(luò)的數(shù)據(jù)傳輸量。本文主要貢獻(xiàn)有以下3點。

1) 對一個時隙內(nèi)的真實數(shù)據(jù)進(jìn)行分析，實驗證明數(shù)據(jù)具有近似低秩的性質(zhì)，且收集一個時隙內(nèi)數(shù)據(jù)，以降低網(wǎng)絡(luò)時延。

2) 利用數(shù)據(jù)的低秩性質(zhì)與空間相關(guān)性，將MC技術(shù)與CS技術(shù)相結(jié)合，提出極稀疏塊觀測矩陣，減小不可靠鏈路對數(shù)據(jù)重構(gòu)的影響，在保證重構(gòu)精度的前提下降低網(wǎng)絡(luò)能耗。

3) 采用GreenOrbs系統(tǒng)真實數(shù)據(jù)，利用仿真軟件Matlab對所提算法進(jìn)行實驗驗證，實驗結(jié)果表明所提算法在鏈路具有50%分組丟失率情況下，仍能保證高重構(gòu)精度。

2 問題描述

2.1 基于壓縮感知的分布式數(shù)據(jù)收集方法

網(wǎng)絡(luò)采用簇型路由結(jié)構(gòu)，整個網(wǎng)絡(luò)劃分為若干個簇，在每個簇內(nèi)使用壓縮感知技術(shù)進(jìn)行數(shù)據(jù)收集，整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)示意如圖1所示。

sink節(jié)點在收到觀測向量后，通過求解凸優(yōu)化問題，求解全簇的觀測數(shù)據(jù)。

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

本文用歸一化平均絕對誤差（NMAE, normalized mean absolute error）衡量數(shù)據(jù)重構(gòu)誤差，即

2.2 矩陣補全技術(shù)

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

圖3 矩陣低秩特性

實驗結(jié)果表明，真實環(huán)境中傳感器感知原始數(shù)據(jù)具有近似低秩的特征，若節(jié)點在數(shù)據(jù)傳輸?shù)倪^程中丟失有一定數(shù)量的分組，即無線鏈路存在分組丟失率，可以利用原始數(shù)據(jù)矩陣的低秩性質(zhì)，通過MC技術(shù)，恢復(fù)出丟失的數(shù)據(jù)分組，減少分組丟失對數(shù)據(jù)傳輸?shù)挠绊憽?/p>

由于傳感網(wǎng)采集的數(shù)據(jù)陣為近似低秩矩陣，令

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

3 算法設(shè)計

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

3.1 極稀疏塊觀測矩陣

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

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

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

3.2 CS-SBM算法

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

⑦ end for

⑧ end for

? end for

圖5 CS-SBM算法流程

算法2 重構(gòu)全網(wǎng)數(shù)據(jù)

4 仿真與分析

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

表1 參數(shù)設(shè)置

圖7 MC恢復(fù)精度與分組丟失率關(guān)系

圖8 不同觀測次數(shù)下算法性能

圖9 觀測次數(shù)與重構(gòu)精度的關(guān)系（P=0.4）

5 結(jié)束語

本文構(gòu)造了SBM矩陣，并采用FFT基作為稀疏基，通過仿真實驗可得，CS-SBM算法可以通過CS技術(shù)重構(gòu)出全網(wǎng)數(shù)據(jù)，但并未理論證明SBM矩陣和FFT基滿足RIP條件，如何從數(shù)學(xué)角度嚴(yán)謹(jǐn)?shù)刈C明所提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數(shù)據(jù)收集算法[J]. 通信學(xué)報, 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-），男，四川南充人，信息工程大學(xué)博士生，主要研究方向為無線自組織網(wǎng)絡(luò)、無線傳感網(wǎng)與路由協(xié)議。

李鷗（1961-），男，陜西寶雞人，博士，信息工程大學(xué)教授、博士生導(dǎo)師，主要研究方向為無線傳感網(wǎng)、認(rèn)知無線電網(wǎng)絡(luò)與無線自組織網(wǎng)絡(luò)。

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

楊延平（1986-），男，河南平頂山人，清華大學(xué)博士后，主要研究方向為無線認(rèn)知通信、網(wǎng)絡(luò)編碼、自適應(yīng)調(diào)制。