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

?

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

2 問題描述

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

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

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

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

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

2.2 矩陣補(bǔ)全技術(shù)

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

圖3 矩陣低秩特性

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

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

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

3 算法設(shè)計(jì)

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

3.1 極稀疏塊觀測(cè)矩陣

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

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

其簇首收到的觀測(cè)向量的矩陣為

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 不同觀測(cè)次數(shù)下算法性能

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

5 結(jié)束語

本文構(gòu)造了SBM矩陣，并采用FFT基作為稀疏基，通過仿真實(shí)驗(yàn)可得，CS-SBM算法可以通過CS技術(shù)重構(gòu)出全網(wǎng)數(shù)據(jù)，但并未理論證明SBM矩陣和FFT基滿足RIP條件，如何從數(shù)學(xué)角度嚴(yán)謹(jǐn)?shù)刈C明所提SBM矩陣滿足RIP條件是下一步工作重點(diǎn)。

[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é)報(bào), 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

國家科技重大專項(xiàng)基金資助項(xiàng)目（No.2016zx03001010）

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

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

張策（1991-），男，四川南充人，信息工程大學(xué)博士生，主要研究方向?yàn)闊o線自組織網(wǎng)絡(luò)、無線傳感網(wǎng)與路由協(xié)議。

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

童昕（1990-），女，湖北黃岡人，61377部隊(duì)助理工程師，主要研究方向?yàn)槎嗵炀€信號(hào)聯(lián)合處理。

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