基于矩阵补全的无线传感器网络收集数据重建方法*

陈正宇,胡国兵,姜志鹏

(金陵科技学院电子信息工程学院,南京 211169)

基于矩阵补全的无线传感器网络收集数据重建方法*

陈正宇*,胡国兵,姜志鹏

(金陵科技学院电子信息工程学院,南京 211169)

许多自然科学研究都利用无线传感器网络收集环境数据。收集数据的完整性和准确性决定科研结果的可靠性。然而,数据收集过程中通常会出现数据丢失和数据错误等问题。为提升收集数据的可用性,需要从含有错误元素的不完整数据集中恢复丢失的数据。利用环境数据的低秩特性,提出一种基于弹性网正则化的结构化噪声矩阵补全算法(EnRMC),既能实现丢失数据的有效恢复,也能精确判断收集到错误数据的传感器节点。利用真实数据进行仿真,实验结果表明算法性能优于现有算法,能以较高的精度重建环境数据。

感器网络;数据收集;矩阵补全;数据重建

在环境、农作物生长和生物习性监测等科学研究中,通常需要利用无线传感器网络收集的感知数据来开展科学研究[1-2]。相关研究和决策的准确性依赖于收集数据的完整性和正确性[3]。然而,由于无线传感器网络的固有特性,数据收集过程中会出现数据丢失和数据错误[4]。例如,在伯克利Intel项目[5]中,通过3个星期的观察,发现接近40%的数据丢失和8%的数据错误[6]。因此,利用收集到的含有错误元素的不完整数据集重建环境数据具有重要的意义。

传统的缺失数据恢复方法是利用收集数据之间的时空相关性实现缺失数据的恢复,如各类插值算法等。这些算法在数据丢失率较低的情况下效果较好,当数据丢失率升高时,恢复性能急剧下降[7]。近几年,随着矩阵补全理论的广泛应用,文献[8]首次提出利用矩阵补全技术进行数据收集,将数据恢复问题建模成缺失数据矩阵的补全问题,实现较小的恢复误差。在文献[8]基础上,文献[9]提出空时压缩数据收集方法STCDG,利用数据的瞬时稳定性,在求解矩阵补全的最优解时提供稳定性约束,实现更低的恢复误差。文献[10]分析了无线传感器网络收集数据丢失模式,利用收集数据的低秩特性、时间和空间相关性等特征,提出一种缺失数据恢复方法。文献[11]提出联合矩阵补全和稀疏限定的数据恢复方法DRMCSC,将传感器网络数据稀疏约束和矩阵补全结合在一个优化问题中,并设计交替最小化算法,实现缺失数据的恢复。以上这些算法仅考虑丢失数据的恢复问题,对于无线传感器网络收集数据的错误问题,以及数据错误对缺失数据恢复精度的影响均没有考虑。对于错误数据的检测问题,已有研究通常利用数据相关性和统计特性来检测错误数据。文献[12-13]分别提出基于直方图和基于收集数据统计特性的Outlier数据检测方法。文献[14]提出利用序列检测方法来发现传感器网络中的错误数据。文献[15]研究异常收集数据和链路中断的存在对数据收集精确度的影响,并基于压缩感知理论辨别和纠正异常收集数据,从而推断中断链路。上述这些算法都没有考虑数据丢失对于错误数据检测的影响。

本文利用无线传感器网络收集环境数据矩阵的低秩特性,将含有错误收集数据情况下缺失数据恢复问题建模为结构化噪声矩阵补全问题,并提出一种基于弹性网正则化的结构化噪声矩阵补全算法(Elastic-net Regularization based Matrix Completion with Structral Noise,EnRMC)。EnRMC算法能以较高的精度恢复缺失数据,同时能辨识出含有错误数据的传感器节点。

1 系统模型与问题描述

1.1 系统模型

假设监测区域内有N个传感器节点{v1,v2,…,vN},用于感知不同类型的环境数据。采用周期性数据收集策略。每个收集时间间隔为τs,也称为一个时隙。假设监测总时间为T个时隙,则对于某一类环境数据,总的数据量为N×T个。用X表示收集的环境数据矩阵,即

X=(X(i,j))N×T

(1)

式中:X(i,j),i=1,2,…N,j=1,2,…T,表示节点vi,在第j个时隙收集到的某一类环境数据。由于存在数据丢失,Sink节点得到的是一个有很多元素丢失的不完全矩阵,称为采样矩阵,用S表示。该矩阵的任意元素可以表示为:

(2)

我们定义Ω⊆[N]×[T]([N]={1,…,N},T={1,…,T})为采样元素在采样矩阵中的下标索引集合。PΩ(·)为正交投影算子,表示当(i,j)∈Ω时,Sij为采样元素,即有:

PΩ(S)=PΩ(X)

(3)

除数据丢失外,某些传感器节点收集的数据容易出现错误,也就是收集数据矩阵某些行的数据元素容易发生错误。可将错误数据表示为原始环境数据叠加上噪声值。假设第i个传感器,在第j个时隙收集的数据发生错误,设这个错误值为Rij,可以表示为:

Rij=Xij+Zij

(4)

式中:Xij为原始环境数据,Zij为噪声值。对于这类行元素的错误问题,可视为采样矩阵受到行形式的结构化噪声污染。将Sink节点最终收集的数据矩阵称为收集数据矩阵,记为R,则有:

PΩ(R)=PΩ(X+Z)

(5)

式中:Z为行形式的结构化噪声矩阵。

1.2 问题描述

数据重建就是利用Sink节点收集到的数据矩阵R来重建环境数据矩阵X。基于文献[9-10]分析的环境数据矩阵的低秩特性,将数据重建问题建模为矩阵补全问题[16]。为了有效地平滑结构化噪声,将其带来的不利影响尽可能降到最低,引入矩阵L2,1范数正则化参数到标准矩阵补全问题。对目标函数施加正则化约束,从而将含有错误数据条件下的无线传感器网络缺失数据恢复问题建模为基于L2,1范数正则化的结构化噪声矩阵补全问题:

(6)

式中:R∈n1×n2为收集数据,X为优化矩阵,Z为噪声矩阵,‖X‖*为X的核范数,‖Z‖2,1为矩阵Z的L2,1范数,用来平滑结构化噪声;λ是一个用来平衡结构化噪声和矩阵低秩程度的可调参数。

2 算法设计

为了增加结构化噪声矩阵补全问题式(6)求解的稳定性,引入弹性网正则化技术[17]到矩阵补全问题中,提出一种基于弹性网正则化的结构化噪声矩阵补全算法(EnRMC)。EnRMC算法采用Frobenius范数正则化控制解的稳定性,首先将问题(6)松弛为如下近似问题(7):

(7)

式中:‖·‖F为矩阵Frobenius范数,参数τ用来调整弹性网正则化项对原问题的扰动程度。易知该问题的Lagrangian函数为:

(8)

进一步,由于该问题为凸集合上的凸优化问题且满足Slater条件,因此强对偶性成立,其全局最优解(X*,Y*,Z*)满足:

(9)

可采用如下交替迭代方法求解(X*,Y*,Z*):

(10)

下面依次给出计算Xk+1,Zk+1和Yk+1的具体步骤:

在求解子问题1之前先给出如下定义和定理:假设矩阵X∈n1×n2的奇异值分解(SVD)为X=UΣVT,Σ=diag({σi|1≤i≤min(n1,n2)}),若矩阵X的秩为r,即Σ=diag({σi|1≤i≤r且σ1≥σ2≥…≥σr>0}),如果τ≥0,则τ对应的奇异值阈值算子定义为:Dτ(X)=USτ(Σ)VT,其中Sτ(Σ)=diag({max(0,σi-τ)|i=1,2,…,r})[18]。

定理1[18]对任意τ,μ>0,Z∈n1×n2,有

证明略,详见文献[18].

将式(8)代入子问题1得到:

根据定理1可得:Xk+1=Dτ(PΩ(Yk))。

显然,子问题2可以一般化为如下优化问题:

求解优化上述问题时,由于矩阵D依赖于目标变量Z,因此D也是未知变量,从而导致函数tr(ZTDZ)仍然不可微。因此,提出一种交替更新算法来求解该问题,即:在每一次迭代中,首先固定变量D求目标变量Z,然后再根据求得的Z更新D,直到算法收敛时迭代结束。

应用梯度下降法可得:

Yk+1=Yk+δPΩ(R-Xk+1-Zk+1)。

算法1 EnRMC

输入:R,λ,τ和δ,最大迭代次数max_K,max_T。

1 INITIALIZEX0=0,Z0=0;

2Y0=PΩ(R-X0-Z0);

3 FORk=0 to max_K

4 (U,Σ,V)=svd(Yk);

5Xk+1=USτ(Σ)VT;

6 INITIALIZED0=I;

7 FORt=1 to max_T

10t=t+1;

11 END FOR

12Yk+1=Yk+δPΩ(R-Xk+1-Zk+1);

13k=k+1;

14 END FOR

3 仿真实验

3.1 实验条件

为了便于阐述,给出一些基本定义。设n为收集数据矩阵中丢失的数据元素个数,则pn=n/(N×T)为数据丢失率。未丢失数据的比例为ps=1-pn,也称为数据采样率。m表示存在错误收集数据的传感器节点数。将存在错误收集数据的传感器节点占所有传感器节点的比例称为传感器节点故障率,记pm=m/N。为了评估算法性能,采用Intel室内项目[5]的真实数据进行算法验证。采用温度数据作为实验数据,收集52个传感器节点在连续300个时隙中采集的数据,即N=52,T=300,环境数据矩阵为XN×T。利用XN×T合成得到收集数据矩阵RN×T。具体过程为:

步骤1 根据数据采样率ps,随机产生采样元素的下标索引集合Ω。依据Ω从环境数据矩阵XN×T中采样元素,得到合成数据矩阵RN×T,满足:

步骤2 基于传感器节点故障率pm,确定存在错误收集数据的传感器节点数m=|pm×N|,从RN×T中随机选取m行,并将这m行中50%的非零元素叠加随机噪声Zij。假设错误数据的下标索引集合为。得到最终的合成数据矩阵RN×T,满足:

式中:Zij是均值为0,方差为δ2的正态分布随机变量,即Zij～N(0,δ2)。

通过上述两个步骤可以得到用于实验的收集数据矩阵RN×T。执行算法后,将恢复的数据矩阵和环境数据矩阵XN×T进行对比,来衡量算法性能。对于λ,τ和δ等可调参数自适应设置的理论研究还没有展开,本文依据所处理问题的先验知识对可调参数进行交叉验证。

3.2 性能参数定义

为了衡量算法性能,给出一些性能参数的定义。

(1)缺失元素恢复误差εM,表示恢复缺失环境数据的精确程度。其可以表示为:

(11)

(12)

式中:E表示收集数据矩阵中含有错误数据的行的集合。

图1 不同数据丢失率下的缺失元素恢复误差

3.3 仿真结果和分析

将本文提出的EnRMC算法与DRMCSC[11]和STCDG[9]进行对比分析。对比数据是15次随机实验结果的平均值。图1给出在不同数据丢失率的情况下,算法恢复性能对比。设置传感器节点故障率15%,数据丢失率pn在10%到95%之间。为了便于观察算法性能,将恢复误差通过两张图片显示。图1(a)设置数据丢失率从10%到80%,以10%递增。图2(b)设置数据丢失率从80%到95%,以5%递增。如图1所示,所有算法对缺失元素的恢复误差随着数据丢失率的增加而增加,但EnRMC算法对缺失元素恢复误差明显低于其他算法。在数据丢失率比较低的情况下,几种算法恢复误差都较小;当数据丢失率超过85%时,恢复误差急剧增加。在数据丢失率比较高的时候,EnRMC相比于其他算法有着更明显的优势。

图2给出不同传感器节点故障率的情况下,算法性能对比。图2中,设置数据丢失率pn=50%,传感器节点故障率从5%到50%,每次递增5%。随着含有错误数据传感器节点数量的增加,所有算法对缺失元素的恢复误差也随之增加,但EnRMC始终优于其他算法,并且当传感器节点故障率增加时,EnRMC的优越性更加明显。

图2 不同故障率下缺失元素恢复误差

图3 不同故障率下含错数据行整体恢复误差

4 结论

针对无线传感器网络数据收集过程中出现的数据丢失和数据错误等问题,提出一种存在数据错误和缺失的无线传感器网络收集数据重建方法。该方法利用环境数据矩阵低秩特性,将无线传感器网络收集数据重建问题建模为结构化噪声矩阵补全问题,并设计一种基于弹性网正则化的结构化噪声矩阵补全算法,实现缺失数据的恢复和含错误数据传感器节点的识别。实验结果表明,该方法可以显著提高环境数据的重建精度。本文后续工作将包括利用收集数据矩阵的时间和空间相关性进一步提升数据恢复精度。

[1] Gao Hong,Fang Xiaolin,Li Jianzhong,et al. Data Collection in Multi-Application Sharing Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2015,26(2):403-412.

[2] Habib C,Makhoul A,Darazi R,et al. Self-Adaptive Data Collection and Fusion for Health Monitoring Based on Body Sensor Networks[J]. IEEE Transactions on Industrial Informatics,2016,12(6):2342-2352.

[3] Xiang L,Luo J,Rosenberg C. Compressed Data Aggregation:Energy-Efficient and High-Fidelity Data Collection[J]. IEEE/ACM Transaction on Networking,2013,21(6):1722-1735.

[4] Kamal A R M,Bleakley C,Dobson S. Packet-Level Attestation(PLA):a Framework for in-Network Sensor Data Reliability[J]. ACM Transaction on Sensor Networks,2013,9(2):1-19.

[5] Intel 室内项目. http://www.select.cs.cmu.edu/data/labapp3/index.html.

[6] Koushanfar F,Potkonjak M. Markov Chain-Based Models for Missing and Faulty Data in MICA2 Sensor Motes[C]//The 4th IEEE Conference on Sensors,Irvine,California,USA,2005:1430-1434.

[7] Kong Linghe,Xia Mingyuan,Liu Xiaoyang,et al. Data Loss and Reconstruction in Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2014,25(11):2818-2828.

[8] Cheng Jie,Jiang Hongbo,Ma Xiaoqiang,et al. Efficient Data Collection with Sampling in WSNs:Making Use of Matrix Completion Techniques[C]//2010 IEEE Global Communications Conference,Miami,Florida,USA,2010:1-5.

[9] Cheng Jie,Ye Qiang,Jiang Hongbo,et al. STCDG:An Efficient Data Gathering Algorithm Based on Matrix Completion for Wireless Sensor Networks[J]. IEEE Transaction on Wireless Communication,2013,12(2):850-861.

[10] Kong Linghe,Xia Mingyuan,Liu Xiaoyang,et al. Data Loss and Reconstruction in Sensor Networks[C]//IEEE INFOCOM 2013,Turin,Italy,2013:1654-1662.

[11] He Jingfei,Sun Guiling,Zhang Ying,et al. Data Recovery in Wireless Sensor Networks with Joint Matrix Completion and Sparsity Constraints[J]. IEEE Communications Letters,2015,19(12):2230-2233.

[12] Sheng Bo,Li Qun,Mao Weizhen,et al. Outlier Detection in Sensor Networks[C]//The 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc)Montreal,Quebec,Canada,2007:219-228.

[13] Ding Min,Cheng Xiuzhen. Robust Event Boundary Detection in Sensor Networks—A Mixture Model Based Approach[C]//IEEE INFOCOM 2013,Rio de Janeiro,Brazil,2013:2991-2995.

[14] Guo Shuo,Zhong Ziguo,Chen Jiming,et al. Detecting Faulty Nodes with Data Errors for Wireless Sensor Networks[J]. ACM Transactions on Sensor Networks,2014,10(3):1-27.

[15] Tang Yu,Zhang Bowu,Jing Tao,et al. Robust Compressive Data Gathering in Wireless Sensor Networks[J]. IEEE Transactions on Wireless Communications,2013,12(6):2754-2761.

[16] 陈蕾,杨庚,陈正宇,等. 基于结构化噪声矩阵补全的Web服务QoS预测[J]. 通信学报,2015,36(6):49-59.

[17] Li Hong,Chen Na,Li Luoqing. Error Analysis for Matrix Elastic-Net Regularization Algorithms[J]. IEEE Transactions on Neural Networks and Learning Systems,2012,23(5):737-748.

[18] Cai J F,Candes E J,Shen Z. A Singular Value Thresholding Algorithm for Matrix Completion[J]. SIAM Journal of Optimization,2010,20(4):1956-1982.

DataReconstructioninWirelessSensorNetworksBasedonMatrixCompletion*

CHENZhengyu*,HUGuobing,JIANGZhipeng

(School of Electronic and Information Engineering,Jinling Institute of Technology,Nanjing 211169,China)

Many natural science researches use Wireless Sensor Networks(WSNs)to collect environmental data,and use it for scientific research. The integrity and accuracy of the collected data determine the reliability of the results. However,data loss and error usually occur during the process of data collection. Therefore,it is necessary to design an effective method to recover the missing data from the incomplete and erroneous sensory data. Based on the low-rank feature of environmental data,we design an Elastic-net Regularization based on Matrix Completion with Structural Noise(EnRMC)algorithm for reconstructing data. The proposed approach can not only effectively recover the missing data,but also exactly detect the sensor nodes with erroneous data. The simulation results show that the proposed algorithm is superior to the existing algorithms,and can reconstruct the environmental data with high precision.

wireless sensor networks;data collection;matrix completion;data reconstruction

10.3969/j.issn.1005-9490.2017.06.027

项目来源:江苏省基础研究计划(自然科学基金)项目(BK20130096,BK20161516,BK20161104);金陵科技学院高层次人才工作启动项目(jit-b-201527)

2017-07-09修改日期2017-07-20

TP311

A

1005-9490(2017)06-1466-06

陈正宇(1978-),男,江苏淮安人,汉族,博士,副教授,金陵科技学院电子信息工程学院副院长,研究领域为无线传感器网络数据收集与管理,zych@jit.edu.cn。