CN101516099B - 一种传感器网络异常检测方法 - Google Patents

Abstract

一种传感器网络异常检测方法，对网络进行分簇，各簇中簇头汇聚簇内各单位时间内所有节点的高维数据序列，采用隐马尔科夫模型构建方法构建各单位时间的节点高维数据变迁模型，以模型相似性为分类基准，将各节点高维数据变迁模型进行分类，对于每一类的节点高维数据初始变迁模型，将其包含单位时间内的所有高维数据序列汇聚，再次采用隐马尔科夫模型构建方法构建新的节点高维数据变迁模型，利用新的高维数据变迁模型对簇中进行异常检测。本发明充分利用传感器网络中数据时间和空间相关性，有效减少数据冗余及通信开销，延长传感器节点的寿命，达到异常检测的目的。

Description

一种传感器网络异常检测方法 

技术领域

本发明涉及无线传感器网络，特别是涉及无线传感器网络异常检测的方法。 

背景技术

在无线传感器网络中，大量的原始传感器数据之间一般都有高度的空间或时间相关性，把所有这些数据完全传输到基站节点(Sink)既浪费能量也没有必要。数据融合(data aggregation，或称为数据汇聚)的主要思想就是传输路径上的节点之间进行交互式的协同合作，通过去除相关性冗余来大大压缩数据量，从而以更少的数据表达同样或相当的信息量。 

当前基于传感器网络节点数据空间相关性或时间相关性进行的数据融合已有部分的研究成果，但是并未形成一个理论体系。尤其针对空间相关性和时间相关性的利用都是割裂开来的，没有将空间相关性和时间相关性有机的、系统的结合在一起，从而阻碍了数据融合效率的进一步提高； 

现有的数据融合模型都是局部独立的，对各个局部之间的关系和多层次信息融合没有一个科学的解释和建模。实际上数据之间的相关性是具有层次性的，而且是随着距离的增加而逐渐减弱的，各个局部之间还具有相关性，现有研究都是确定性的划定一个区域或界限为局部，只认定为这部分的数据拥有局部相关性。 

现有的数据融合处理模型首先是关注传感器数据，对于数据反映的被探测事件建模只是进行了简单的处理，这就如同语音编码中的幅值编码和模型编码的差距；另外，现有的数据处理模型对高级应用特性支持不足，如同样是表现温度数据，需要拓扑信息的数据融合研究(如等高线求取) 和仅需要统计信息的数据融合研究采用的方法完全不同，没有统一的数学模型形式。此外针对多重传感数据(如同时表现温度、湿度)的统一数据融合的研究还没有有意义的成果。而这些数据处理的理论、方法，往往需要把原始的低维数据集转化为高维数据集，目前的研究主要局限在低维应用场合，高维数据集的分析和建模工作尚未完全展开；最后，现有的数据处理模型主要集中在使用线性系统来分析和处理数据的空间和时间相关性，例如使用线性预测模型来进行预测从而减少数据传输，但现实的系统往往较为复杂，线性系统模型往往不具有通用性。 

有很多异常值检测算法都是判断传感器节点数据和其相邻节点数据的差值来决定是否是异常值，这样需要的时间较长而且不能保证其准确性。利用数据融合的架构，将异常值检测问题转化成给定数据融合的构架的推理问题，即对于给定序列，根据已有的数据融合的构架推测出其对应的最大可能的状态序列，如果根据已有的模型使用现有的状态序列得到的似然函数值来判断，结果将更实用。 

发明内容

本发明的目的在于提供一种无线传感器网络异常检测方法，充分考虑数据在时间上和空间上的相关性，有效减少数据冗余及通信开销，延长传感器节点的寿命，达到异常检测的目的。 

一种传感器网络异常检测方法，对网络进行分簇，各簇按照如下方法进行异常检测： 

步骤1)簇头汇聚簇内第i个单位时间内所有节点的高维数据序列，以该高维数据序列为训练样本，采用隐马尔科夫模型构建方法构建第i个单位时间的节点高维数据变迁模型，i＝1，2，…，N，N为提取的单位时间数量； 

步骤2)以变迁模型相似性为分类基准，将第1，2，…，N个单位时间的节点高维数据变迁模型进行分类； 

步骤3)对于属于第j类的节点高维数据初始变迁模型，将其对应单 位时间内的所有高维数据序列汇聚，构成新的训练样本，采用隐马尔科夫模型构建方法构建第j类节点高维数据变迁模型，j＝1，2，…，N1，N1为步骤2)得到的分类数； 

步骤4)利用第j类节点高维数据变迁模型对簇中所有节点采集的数据进行异常检测。 

本发明的技术效果体现在： 

(1)多维数据融合。对网络中的高维数据集(如同时包含温度、湿度)进行数据融合，采用HMM模型对高维数据集进行建模，建立适合任何维数的一般数据集的数据融合模型； 

(2)减少冗余，减少开销。本发明充分利用传感器网络采集到数据时间和空间上的相关性，首先通过分簇算法，由空间上的相关性，簇内节点采集到的数据差异不大，以簇为单位进行建模，减少了模型的冗余，也方便对簇内节点采集到的后续数据进行异常检测；考虑时间上的相关性，对模型分类，重新构建新训练样本构建新模型，进一步减少模型的冗余；采用隐马尔科夫模型对高维数据集变迁进行建模，使得在异常检测的过程中从节点无需将采集到的所有数据发送给簇头节点，只需将变迁序列(即采样后的序列)发送给簇头节点，从而大大减少了通信开销。 

附图说明

图1为本发明无线传感器网络结构示意图； 

图2为本发明异常检测方法总体流程图； 

图3为无线传感器网络分簇结果示意图； 

图4为训练样本示意图； 

图5为异常检测结果示意图：图5(a)为3月17号簇中节点二维数据变迁图；图5(b)为3月18号簇中节点二维数据变迁图；图5(c)为3月17号簇中节点二维数据图(不包括节点3，粗线为节点4的变迁曲线)；图5(d)，5(e)，5(f)为3月18号簇中节点二维数据图(不包括节点3，图中的粗线分 别为节点2，7，9的变迁曲线)。 

具体实施方式

为了更加清楚的表明本专利的目的、技术方案和优点，下面结合附图及具体实例对本方法做出详细说明。 

本发明针对无线传感器网络中的异常检测问题，能够对网络中的高维数据集(同时包含温度和湿度的读数)进行数据融合，提取出有用信息，最终得出异常检测结果。 

图1描述了实施例所用传感器网络的布局，实施例中所用的传感器数据，是由英特尔伯克利研究实验室(Intel Berkeley Research lab)采集到1～54个节点从2004年2月28号到4月5号的数据。单位时间为12小时的整数倍，实例中以单位时间为一天(24小时)举例说明。 

图2是实施例的流程示意图，包括以下步骤： 

步骤1根据空间位置的相邻性，对网络进行分簇。 

对于图1所示的网络结构，我们通过以下方法对网络进行分簇：每个节点有一个状态标记位，初始化为0，0表示节点未确定状态，1表示节点已确定自己是簇头节点或者从节点；每个节点有一个层次(leval)标记位，初始化为∞；每个节点还有标记父节点的parent标记位。每个节点在(0，N³)内随机选择自己的临时ID号，其中N表示网络中节点的总数。 

步骤11节点间进行通信，每个节点得到h跳以及h跳以内邻居节点的信息，h可以随意取值，本实验中h取为2。状态标记为0的节点将自己的ID号与标记号为0的h跳以及h跳以内邻居节点的ID号作比较，如果自己的ID号最大，则确认自己为簇头节点，即将leval标记位置为0，表示簇头节点在第0层，并且将自己的状态标记位置为1，进入步骤12。 

步骤12状态标记位为0的所有节点比较自己与间距h跳以及h跳以内的簇头节点的相似性，本发明中我们用相关系数来表示两个节点的相似性，即假设x_k，x₁分别为节点S_k，S₁在一天中读到的序列样本，相关系数r_k，l定义为， 

$r_{k,l}=\frac{E\left(x_k{x}_l\right)-E\left(x_k\right)E\left(x_l\right)}{\sqrt{E\left(x_k^2\right)-E^2\left(x_k\right)}\sqrt{E\left(x_l^2\right)-E^2\left(x_l\right)}}$

其中E()为取均值符号。 

如果相关系数大于相关性阈值，两条曲线相似性越大，相关系数趋近于1，本实验中我们设相关系数大于0.97，节点将自己的状态标记位置为1，节点为从节点。 

步骤13重复步骤11、步骤12，直到网络中的所有节点的状态标记位全为1。 

步骤14每个从节点计算自己和间距一跳范围内所有簇头节点的相似性，找到相关系数最大的簇头节点，如果该相关系数大于相关性阈值，如相关系数大于0.97，则将该从节点的leval标记置为1，该从节点的parent标记置为簇头节点的ID号。 

步骤15leval＝∞的节点得到h及h跳以内范围内leval≠∞的所有节点的信息，选择相似性最大且节点的leval≤h-1的节点S，将该节点的leval标记置为节点s的leval标记+1，该节点的parent标记置为s。 

以上即为簇头节点选举的过程，至此，网络中的节点属于且只属于一个簇，每个簇的最大跳数为h，其中h的大小在程序运行之初可以调整。分簇后的结果图如图3所示。 

接下来，每个簇以簇头为中心，对簇中的数据进行分析处理，得出该簇中的异常检测结果。 

步骤2每个簇采集样本训练隐马尔科夫模型(HMM)，样本包括N天簇中所有节点的数据序列。每个节点隔两个小时采集一个数据值(数据为该节点在两个小时采集到的所有数据的平均值)，一天就有12个值，把这12个值组成的序列作为样本，为了保证训练的稳定性，我们把一个簇中所有节点的序列汇聚到簇头节点训练。用鲍姆-韦尔奇(Baum-Welch)算法迭代计算出这些隐马尔科夫模型的各项参数，包括初始概率向量，状态转移概率矩阵，混合高斯模型的各项参数，混合矩阵等。由附图4(表示3月 1号由节点4，6，7，8，9，10，11，12，13所组成的簇)，我们可以看到同一个簇中数据的变迁曲线基本上是一致的。我们所用的训练序列为多序列，Baum-Welch迭代的结果是使得多个序列在模型中出现概率的总和最大。 

步骤3为了进一步减少模型的冗余，需要把相似的模型进行分类。由于时间上的相关性，即相邻天数簇中一天内高维非线性数据集变迁的曲线相似，可以用K均值算法对以天为单位训练的隐马尔科夫模型进行分类，分类后，将同属一类的模型对应天数的数据汇聚，形成新的训练样本以重新训练隐马尔科夫模型。实验中采用的是用15天的数据用K均值算法分为4类。 

 步骤4给定任何一个簇中所有节点某一天的数据集的所有变迁序列，运用隐马尔科夫里面的前向算法，算出该所有序列分别在步骤3中训练的隐马尔科夫模型中出现概率，取使概率和最大的隐马尔科夫模型，如果某个节点的变迁序列在该模型中出现的概率小于设定的异常判断阈值，则判定该节点的数据为异常。概率越小，跟模型拟合越差，为异常的可能性越大，本实验中设异常判断阈值为0.1。mj表示第j个隐马尔科夫模型，设标号为i的序列在mj中出现的概率为P(i|mj)，该序列长度为Ti，用L(i|mj)＝(1/T_i)log(P(i|mj))表示归一化概率对数所对应的值。我们用3月17号，3月18号的数据去检验步骤三中训练的四个模型的准确性，以由节点4，6，7，8，9，10，11，12，13所构成的簇为例，拟合的结果如表1所示。其中如附图5所示，表一中的数据表示该簇中9个节点2天的数据分别在在模型I，2，3，4中的L(i|mj)。从该表中我们可以看出3月17号的数据跟模型3拟合的最好，3月18号的数据跟模型4拟合的最好。这两天中节点3的温度读数都不正常，为100多度，曲线分别如附图5(a)，附图5(b)所示(实线表示温度曲线，虚线表示电压曲线，加粗的线表示节点3的温度和电压值)；为了便于观察，我们去掉节点3。3月17号，剩下的节点中，节点4的L(i|mj)最小，观察它的曲线变迁图，发现节点4的电压比其它节点高，如附图5(c)所示；3月18号，剩下的节点中，节点2，7，9的L(i|mj)比其他节点小很多，它们的曲线变迁图如附图5(d)，附图5(e)，附图5(f)所示，可以确定为异常节点。 

表一模型拟合0317，0318三天数据结果 

综上所述，一种基于层次决策和隐马尔科夫模型的传感器网络异常检测方法是有效的。 

Claims (3)

1.一种传感器网络异常检测方法，对网络进行分簇，各簇按照如下方法进行异常检测：

步骤1)簇头汇聚簇内第i个单位时间内所有节点的高维数据序列，以该高维数据序列为训练样本，采用隐马尔科夫模型构建方法构建第i个单位时间的节点高维数据变迁模型，i＝1，2，…，N，N为提取的单位时间数量；

步骤2)以变迁模型相似性为分类基准，将第1，2，…，N个单位时间的节点高维数据变迁模型进行分类；

步骤3)对于属于第j类的节点高维数据变迁模型，将其对应单位时间内的所有高维数据序列汇聚，构成新的训练样本，采用隐马尔科夫模型构建方法构建第j类节点高维数据变迁模型，j＝1，2，…，N1，N1为步骤2)得到的分类数；

步骤4)给定簇中所有节点某一天的数据集的变迁序列，运用隐马尔科夫前向算法，算出所有序列分别在第j类的节点高维数据变迁模型的出现概率，取使概率和最大的节点高维数据变迁模型，如果某个节点的变迁序列在该模型中出现的概率小于设定的异常判断阈值，则判定该节点的数据为异常；

所述网络分簇按照如下方式进行：

步骤01未身份标识的节点比较自己与间隔h跳以及h跳以内的邻居节点的ID号，若自身的ID号最大，则将自身身份标识为簇头，层次标记置0；

步骤02未身份标识的节点计算自己与间距h跳以及h跳以内的簇头的相似性，若存在相似性大于相关性阈值，则将该节点身份标识为从节点；

步骤03重复步骤01～02，直到所有节点的身份被标识；

步骤04从节点计算自己与间距一跳的所有簇头的相似性，找到相似性最大的簇头T，如果最大相似性大于相关性阈值，则确认该从节点为簇头T的子节点，并将该从节点的层次标记置1；

步骤05未作层次标记的从节点计算自身与间距h及h跳以内已作层次标记的所有从节点的相似性，选择相似性最大且层次标记≤h-1的从节点S，该从节点的层次标记等于从节点S的层次标记+1，确认该从节点为从节点S的子节点；

步骤06重复步骤05，直到所有从节点的层次标记被赋值；

所述相似性按照如下方式计算：令x_k，x₁分别为节点S_k，S₁在一个单位时间内采集的高维数据序列，相似性r_k，l定义为：

$r_{k,l}=\frac{E\left(x_k{x}_l\right)-E\left(x_k\right)E\left(x_l\right)}{\sqrt{E\left(x_k^2\right)-E^2\left(x_k\right)}\sqrt{E\left(x_l^2\right)-E^2\left(x_l\right)}}$

其中E()表示取均值。

2.根据权利要求1所述的一种传感器网络异常检测方法，所述步骤2)采用K均值算法分类。

3.根据权利要求1所述的一种传感器网络异常检测方法，其特征在于，所述单位时间为12小时的整数倍。

Images