基于重要性分数的CUR矩阵分解识别WSN异常节点

谢丽霞，田宇祺

(中国民航大学 计算机科学与技术学院，天津 300300)

0 引 言

无线传感器网络(wireless sensor networks，WSN)中每个节点可以用于监视封闭环境中的物理数据，并将数据存储起来，通过自组织网络发送到基站[1]。

传感器节点的功率和计算能力等因素的固有限制使传感器节点易产生故障，或受到攻击[2]。因此必须识别WSN中的异常节点，及时进行网络维护以提供可靠和安全的网络功能。WSN中的异常可能是由网络中的传感器发生故障、攻击者的攻击/入侵引起，通过分析网络中与流量相关的属性值来识别[3]。

在数据挖掘和机器学习领域中异常识别被广泛研究。异常识别一般可分为3种方法，第一种方法是使用无监督学习发现异常。Liu等[4]提出一种基于k-均值分类算法的节点识别方法，该方法通过梯度下降和支持向量机两种算法计算节点信誉值以识别异常节点，该方法缺点是识别时间过长。第二种方法是使用监督分类，如常琳等[5]提出一种基于数据驱动的异常识别算法，该算法利用交叉窗口的故障权重识别异常，但该方法仅针对故障异常。Nesrine Berjab等[6]设计一种基于事件-条件-动作规则和模糊逻辑理论的无线传感器网络异常节点识别算法，但当数据量过大时，该方法的异常节点识别率可能会降低。第三种方法是新颖性识别。Kanev等[7]搭建一种基于人工神经网络的异常识别方法，该方法的缺点是需要大量计算。Lopez valcarce等[8]通过最大似然方法来解决噪声数据和矩阵补全问题以识别异常节点，但其攻击的识别精度不高。

上述类型的算法计算量太复杂，无法在内存和功率受限的传感器节点中执行。因此，需要考虑到传感器网络对异常识别的局限性，研究新的算法。

本文提出一种基于重要性分数的CUR低秩矩阵分解WSN异常节点识别方法。该方法可更好拟合网络数据固有的低秩属性，且对于网络数据的缺失和噪声具有较强的鲁棒性。本文的创新点主要为以下两点：①使用一种改进的CUR矩阵分解方法，具体操作是在初始化矩阵时根据重要性分数构造矩阵C、矩阵U、矩阵R。②增加参数ρ，通过计算候选列与选择列的相关性，选择相关性小的候选列构造矩阵。

1 异常节点识别模型设计

具体处理流程如图1所示。

图1 异常节点识别模型

(1)数据获取与处理

获取无线传感器网络的节点流量数据，去除数据中明显异常值并进行归一化处理，然后将处理后的数据输入到下一模块进行属性矩阵重构。

(2)CUR矩阵分解

首先将输入的数据构建为属性矩阵X。然后基于改进的CUR矩阵分解模型，利用重要性分数将属性矩阵X分解为矩阵C、矩阵U、矩阵R这3个矩阵，将3个矩阵相乘得到重构的正常矩阵Y，其中矩阵C、矩阵R是从X的行和列中根据相关性选择的元素组成。最后使用残差算法对属性矩阵和重构矩阵进行残差计算，求出异常矩阵A。

(3)异常节点识别

根据异常矩阵A中节点向量的期望和标准差构建休哈特控制图。图中中线的中心值为列向量的期望，上下控制限为中心值加减标准偏差，以此根据异常矩阵A来捕获属性矩阵与重构矩阵之间的差异，利用上下控制限之间的阈值为标准来判断节点是否发生异常[9]。

2 CUR矩阵分解模型构建

UTXV=∑=diag(σ1，σ2，…σρ)

(1)

此处∑∈Rd×p，ρ=min{d，p}， 同时，diag(·)表示一个对角线上带有指定元素的对角线矩阵。等效于X=U∑VT， 3个矩阵U、V以及X构成∑。σi是X的奇异值，向量ui和vi分别是第i个左和第i个右奇异向量。

2.1 属性矩阵构建

无线传感器网络数据流在被监测的过程中，若某节点的流量数据出现偏差，则该节点可被认为状态异常。在无线传感器网络中通常监测转发率、接受率以及流量数来识别节点的异常表现。3个特征属性具体含义和选择原因如下。

特征属性1 转发数：转发数是在固定时间内某节点将所获得的数据成功转发时所通过的流量数。在WSN中，传感器会相互发送数据信号，节点异常时会发生数据转发异常，因此该属性是判断节点异常的重要依据。

特征属性2 接收数：接收数为在固定时间内某节点完整接收到其它节点数据时通过的流量数，与丢包率类似，但在网络环境没有受到攻击和损坏的情况下，节点的丢包率会接近0。

特征属性3 流量数：流量数为某固定时间间隔内节点通过的流量。该指标反映节点总体流量走向，同样可作为判断节点是否异常的依据。

本文所提出的异常节点识别算法，将从收集的网络节点流量数据中提取出3个特征属性值构建属性矩阵Xd×p。p是网络传感器节点的数量，并且因为节点的异常可能会在多个时间周期中有所表现，所以算法在识别某一周期的异常节点时，会将该周期的前一个周期和后一个周期节点的特征属性值与该周期的属性值同时作为矩阵的列向量，以保证精确识别异常。Xij表示第j个节点中的第i个属性值。

2.2 CUR矩阵分解

构建属性矩阵X后，对X进行矩阵分解以提取矩阵中的正常成分，并将分解后提取的正常成分重构为一个与属性矩阵X尽可能相近的正常矩阵Y，其中重构的矩阵Y代表矩阵X的主模式。然后将矩阵X与矩阵Y做残差运算，可以得到异常矩阵A，A能够反映X的异常成分，进而反映无线传感器网络节点的异常变化，该部分实现过程如式(2)所示

(2)

在矩阵分解时使用CUR分解方法，提取的正常成分将由矩阵C、矩阵U、矩阵R构成，三者计算得到矩阵Y，代入式(2)中，结果如式(3)所示

(3)

矩阵在分解过程中，往往会存在训练过拟化的问题。为解决此问题，在公式中引入L2-1范数和F范数，将其代入式(3)，基于相关性的CUR低秩矩阵分解模型如式(4)所示

(4)

式(4)中，CUR组成的矩阵Y代表无异常情况下的节点数据，矩阵A为异常矩阵。其中L2-1范数和F范数的公式如式(5)、式(6)所示

(5)

(6)

因此，对于属性矩阵X=[X1，X2，…，Xp]， CUR的目标就是将X矩阵分解为3个矩阵C、U、R后得出异常矩阵A，并满足式(4)。

2.3 基于SVD改进的CUR矩阵分解

为构造C(R类似)，本文将为X的每一列计算一个“重要性分数”，并将该分数作为重要性抽样概率分布从X中随机抽样少量列。在CUR矩阵分解中利用诊断回归分析作为探索性数据分析的工具。

为激励选择的重要性抽样分数，矩阵X的第j列可以表示为下式

(7)

其中，r=rank(X)，vξj是第ξ个右奇异向量的第j个坐标的元素值。即X的第j列是所有左奇异向量和奇异值的线性组合，V的第j行的元素是系数。因此，可以将Xj近似为左上k个奇异向量和相应的奇异值的线性组合

(8)

因为寻找的X列同时与所有右上k个奇异向量的跨度相关联，所以计算归一化的统计分数为

(9)

(1)计算v1，…，vk和等式的标准化统计杠杆得分；

(2)保持X第j列的概率为pj=min{1，cπj}；

(3)根据概率Pj返回由X的选定列组成的矩阵C。

在这个过程中，矩阵C包含c′列，其中c′≤c在期望中，c′紧密集中在期望周围。列分数使用X的右上k个奇异向量进行计算，这种计算容易成为列选择运行时间的瓶颈。在秩参数k(1)中，矩阵X的非零元素乘以低次多项式的时间可以呈线性关系。已经验证在列的选择中至少99%的概率可以满足式(10)

(10)

计算CUR矩阵分解的主要算法以任意d×p矩阵、秩参数和误差参数作为输入参数，然后执行以下步骤：

(1)在X上运行列选择算法构造矩阵C；

(2)在XT上运行列选择算法构造矩阵R；

(3)将矩阵U定义为U=C+XR+， 其中C+表示矩阵C的广义逆。

与列选择算法一样，上述算法的运行时间主要由列和行的分数的计算决定。对于C，U和R的构建，可以通过下式验证

(11)

2.4 相关性程度判断

矩阵C的列和矩阵R的行是用于生成数据矩阵的基本向量，这些基本向量之间的相关性越低，向量的表示性越好，因为选择具有高相关性的两列意味着选择相同的基础向量，所以在根据重要性分数选择X的列向量构造矩阵C、R时，需要计算每个候选列与先前选择的列的相关性，只有相关性程度小于参数δ时，才选定该候选列组成矩阵C或矩阵R。Pearson系数是衡量向量相似度的一种方法，输出范围为[-1，1]，0表示不相关，负值表示负相关，正值表示正相关。由于分解过程只需要判断向量的相关性程度，因此对该系数取绝对值，那么对于矩阵中候选列向量S=[S1，S2，…，Sn] 与已被选定组成分解矩阵的向量L=[L1，L2，…，Ln]， 本文中选择Pearson相关性系数计算向量的相关性程度，公式如下

(12)

其中，μ表示均值，σ表示方差，E()表示期望。

2.5 算 法

在本文中使用基于重要性分数改进的CUR方法进行矩阵分解，其具体算法见表1。

表1 构建改进过的CUR方法进行矩阵分解

上述算法主要解决C、U、R矩阵初始化构造问题。在算法中，初始的矩阵R是从矩阵X的多个实际行中选择重构而成，初始的矩阵C列是从属性矩阵X的实际列中选择重构而成，并且U是一个低秩的矩阵。该方法步骤如下：

(1)计算矩阵列向量的重要性分数，并根据重要性分数从属性矩阵X中选定组成矩阵C、R的候选列。

(2)在根据重要性分数选定某候选列后，计算候选列和已被选定组成矩阵的列项的相关性程度，若相关性程度低于阈值参数ρ，才可将该候选列选为新矩阵的列向量。选定指定数量的列后输出矩阵C、矩阵R。

(3)根据矩阵C、R利用矩阵分解模型中的公式计算矩阵U和矩阵A。

2.6 优化训练

初始化矩阵后，采用交替更新的方法，对矩阵U和异常矩阵A进行进一步训练优化。方法为固定其中一个矩阵，代入式(4)进行求导，并使求导结果为0，求得更新后的矩阵后交替优化另一个矩阵。具体方法描述如下：

(1)固定U矩阵更新A矩阵。当U矩阵固定时，式(4)对于A矩阵来说为凸函数，可以表示为式(13)

(13)

对式(13)的A进行求导，并令结果等于零得式(14)，可求得矩阵A

X-A-CUR-αDRA=0

(14)

(2)固定A矩阵更新U矩阵。当A矩阵固定时，式(4)对于U矩阵来说为凸函数，可以表示为式(15)

(15)

对式(15)的U求导并令结果等于零得式(16)

CTCURRT-CTART-CTXRT+λD′UU=0

(16)

3 异常节点识别

将矩阵X分解之后，得到的异常矩阵A为稀疏矩阵，矩阵A为属性矩阵X的异常部分。当各个测量周期，采取均值、标准差或者极差作为统计信息时，节点存在异常的测量周期与正常的测量周期在对应矩阵列向量之间的差别就表现为二者统计信息之间的差别[10-12]。该差别可用休哈特控制图捕捉到。

根据中心极限定理的理论，假设正常节点的属性向量服从正态分布，那么可以通过矩阵A中列向量的均值和方差设置休哈特控制图里的上中下3条控制限，其中中线的中心值取值为列向量的期望，上下控制限的取值为中心值加减标准偏差，以控制限为标准判断节点是否发生异常。如果某个节点的统计数据超过上控制限或低于下控制限，则认为该节点发生异常。

(17)

(18)

(19)

(20)

其中，d3/d2是极差标准差的无偏估计，E(R)表示期望，D(R)表示方差，CL为中心线，UCL和LCL为上下控制限。计算得到UCL以及LCL后，如果某个节点向量的均值超过UCL或者低于LCL，那么这个节点就被判断为异常节点。

4 实验结果分析

基于MATLAB 2018a平台模拟还原无线传感器网络模型，并收集仿真的节点流量属性数据，以识别率和误测率为指标，分析检验本文算法的性能并与其它算法进行对比。

4.1 实验结果对比

仿真过程中运用PEGASIS路由算法来降低能量消耗，减少能量不足对算法的影响。为节省能源，在一个区域中不均匀的部署一些节点，最好的方法是让很少的节点识别周围的环境而不失去精度。无法决定网络在睡眠状态中优先从哪个节点唤醒时，优先选择唤醒来自网格单元的头部节点，其中网格单元由ID表示。网络部署和识别的主要过程如下：①头节点循环识别活动邻居节点的浓度；②如果浓度值超过阈值，这些节点需要激活它们的邻居(如果它们的邻居被激活，则无需再激活它们)，邻居继续识别并重复相同的工作；③如果一个节点及其所有活动邻居的浓度正常，节点应进入睡眠模式；④读数异常的节点向接收节点发送信息。图2为仿真的部分节点的分布图。

图2 仿真节点分布

其中总体节点分布为：x坐标水平方向为-50 m～350 m，y坐标垂直方向为-50 m～350 m，它们的时间间隔均是30 min。

采集数据时，以30 min为一个周期，并对接收和发送的数据以及流量数据进行数值归一化处理。预处理后模拟的无线传感器网络流量近似正常情况下的流量，分布呈周期性分布，如图3所示。从网络流量的角度出发，向个别节点(即矩阵列向量)人工注入一定规则的异常，添加的异常主要分为外部攻击、内部攻击和能耗异常，注入异常后的流量分布如图4所示。对添加异常后的节点数据提取特征属性值，最终生成原始节点属性矩阵X。

图3 原始流量

图4 加入异常后的流量

根据本文所提出的算法，在对矩阵X进行矩阵分解后将使用休哈特控制图确定网络异常节点，如果某个测量点的统计值超过UCL或者低于LCL，那么这个节点就被判断为异常节点，休哈特图识别结果如图5所示。

图5 异常节点识别结果

为验证本算法的有效性，分别采用4种算法进行实验，然后与本文模型的识别结果作对比。4种算法分别是传统的主成分分析法PCA[13]、非负矩阵分析方法NMF[14]、改进的PGNMF方法[15]和最新的基于阈值测量算法[16]。具体结果如图6、图7所示。

图6 5种算法的识别准确率对比

图7 5种算法的误报率对比

本文的算法与其它4种算法的检测准确率比较结果如图6所示。从图6可以看出，当节点故障率在0.05～0.3之间时，5种算法的检测准确率相差不大，都能达到0.96以上，这是由于大部分噪声都在时间关联性识别阶段被过滤掉了；当节点故障率大于0.3时，5种算法的检测准确率都明显下降，但本文所采用的算法(图中为上三角)要明显优于其它4种算法。这主要是因为5种算法都有空间关联性识别阶段，随着故障率的增加，异常节点容易受到未识别到异常事件的邻居节点的影响，转换为正常状态，从而被误认为没有异常事件发生的正常节点。因为本文算法受邻居节点影响小，所以检测准确率比其它方法高。

在误报率方面，本章算法与其它4种算法的比较结果如图7所示。从图7中可以看出，随着节点异常率的升高，本文所采用的算法的误报率明显低于其它4种算法，这是因为该算法充分考虑非时空属性关联对异常事件识别的影响。通过属性关联置信度的计算可以判定待识别点与样本数据属性关联模型的相似程度，从而有效地区分异常事件和干扰因素。

4.2 算法复杂度对比

本文算法主要包括两个步骤：CUR低秩矩阵分解和休哈特控制图识别异常节点。CUR低秩矩阵分解，①矩阵构建的复杂度为O(dp)；②CUR矩阵分解，进行次数为k2的模型训练迭代，所以该步骤复杂度为O(k2vdp)， 其中：d为特征属性的数量，p为传感器节点的数量，v为分解子矩阵的空间维数；因此CUR低秩矩阵分解的时间复杂度为O(dp)+O(k2vdp)=O(k2vdp)。 休哈特控制图识别异常节点，①统计信息计算的时间复杂度为O(dp)； ②控制限设置，只进行数据赋值为O(1)；③异常节点判断，时间复杂度为O(p)； 因此休哈特控制图识别异常节点的时间复杂度为O(dp)+O(1)+O(p)=O(dp)。

因此本文方法总时间复杂度=O(k2vdp)+O(dp)=O(k2vdp)， 对比实验中其它几种方法的时间复杂度如下：PCA方法的处理复杂度为O(dp2)，NMF方法的复杂性为O(k1vdp)，k1为该方法模型训练时的迭代次数，PGNMF方法的复杂性为O(k1dv2)。因为本文引入范数，对模型训练次数进行控制，防止过拟化，所以模型训练的迭代次数k2

5 结束语

本文提出了一种基于改进CUR低秩矩阵分解的无线传感器网络异常节点识别方法，该方法利用网络属性特征、重要性分数和相关度参数改进CUR矩阵分解，使分解后的异常矩阵能更加精准地用来识别节点异常，为WSN中异常节点的识别提供了一种新的思路。仿真实验数据验证了该方法的可行性，与其它传统和新颖的异常识别方法相比，本文算法具有更高的异常识别率，并且稳定性更佳。由于目前提出的基于改进CUR低秩矩阵分解异常节点识别方法不具备实时性，下一步要改进数据输入形式，达到实时识别的目的。