一种基于时序信誉的WSNs 恶意节点检测算法*

2015-03-30邢哲源冯秀芳

传感器与微系统 2015年7期

邢哲源，冯秀芳

(太原理工大学计算机科学与技术学院，山西太原030024)

0 引言

无线传感器网络(wireless sensor networks，WSNs)将不同类型传感器置于节点内部，感知周围温度、湿度、压力、光强等并对数据进行收集，具有广泛的应用价值［1］。由于WSNs 的自身特点，导致了其容易受到各种各样的攻击。传统的网络安全策略大多基于密码学，对WSNs 完全防御效果不够理想［8］。

近年来，一种基于信任机制的信誉模型在计算机领域内得到大量的应用。国内学者于2007 年通过贝叶斯公式计算节点信誉值，并以阈值作为判断条件，对恶意节点加以识别［2］;王鹏江等人于2010 年又通过引入“间接信誉”对该模型加以改进［3］;2013 年，由曾梅梅等人提出的灰色马尔科夫信誉评价模型在综合信誉的基础上添加了能量信誉概念［4］;吴正一、李健等人于2014 年又在信誉模型的基础上引入能量因素和环境误差的概念［5］。WSNs 发展，催生出更加隐蔽的新型攻击方式，恶意节点持续不断的攻击行为大大减少，在多数情况下保持与正常节点相同或相似［6］。单纯通过阈值进行判断，可能出现低识别率的问题，而提高阈值容易导致较高的误判率。同时，在WSNs 中正常节点由于通信故障往往会导致出现异常行为记录，从而导致误判。

本文提出一种基于时序的WSNs 信任模型，在原有信誉阈值模型的基础上，引入时序和相似度的概念，通过聚类分析出攻击行为不明显的恶意节点。实验表明:本方案有较好的恶意节点识别率，同时避免了原信誉阈值模型由于提高阈值所导致的正常节点误判率上升的问题。

1 相关定义

1.1 时序信誉和样本信誉值序列与节点信誉值序列

本文所采用的方法是将被视为整体的节点通信行为历史进行等长时间间隔的拆分，在每一个时间间隔处对节点的信誉进行评价，并最终形成时序信誉序列。这一方式在本文中被称之为时序信誉。

对于任意节点x，经过n 个相同的时间间隔Δt 后其所有时间间隔点处的信誉值组成其信誉值序列X={Xt1，Xt2，Xt3，…，Xtn}，n ＞1，称为节点x 的信誉序列X。

样本信誉值序列中每个元素表示正常节点的标准信誉值。样本序列可以记为O={Ot1，Ot2，Ot3，…，Otn}，n ＞1。

1.2 亚攻击节点

多个恶意节点相互协作地针对WSNs 进行具有明确分工的攻击时，通过哨岗节点等方式将具有更高的隐蔽性。攻击节点并不以激增方式盲目地发起攻击，其行为在信誉值上更趋近于正常节点的信誉值，不易被系统发觉。上述节点称为“亚攻击节点”，如图1。

图1 亚攻击节点Fig 1 Sub-attack node

1.3 序列相似度和相似度序列

序列相似度是任意节点x 的信誉值序列X 与样本信誉值序列O 之间的相似度，取值范围在［0，1］之间。使用欧几里得度量(Euclidean metric)对节点信誉序列和样本信誉序列的相似度进行计算。

N 维欧氏空间是一个点集，其每个点x 或者向量X，可以表示为(x［1］，x［2］，x［3］，…，x［n］)，其中，xi(i=1，2，3，…，n)是实数，表示x 的第i 维坐标。两个点A=(a［1］，a［2］，a［3］，…，a［n］)和B=(b［1］，b［2］，b［3］，…，b［n］)之间的距离定义为

对于具有n 个节点的WSNs，其相似度序列为S={s1，s2，s3，…sn］，n 为节点数量。

1.4 K-mediods 聚类算法

本实验采用K-mediods 聚类算法［6］对相似度数据集M进行分析。

1.4.1 K 值的确定

K-medoids 聚类算法的基本思想为:设K 是给定的聚类数目，首先需要确定初始聚类中心，即随机选择K 个代表对象;第二划分聚类，分别计算非代表对象与代表对象的距离并将其分配给距离最近的一个簇，确定初始的聚类划分;最后迭代获得最终聚类结果，通过不断迭代寻找最优的中心点。

1.4.2 中心点的确定

原始中心点随机选择一个非中心点，重新获得聚类结果。如果优化聚类效果，则保存此次替换;反之，恢复原中心点，具体定义为

其中，p 为空间中的点，oi为簇Ci的中心点，E 为所有对象的平方误差和。

在进行新一轮中心的替换后，以新的中心集聚类得到的簇用new Ci=1，2，3，…，k 表示，原来的簇以old Ci=1，2，3，…，k 表示，新旧聚类的评价函数可以分别表示

可以求得代价函数为式(5)

最后根据代价来决定中心点。

1.5 信息的汇聚和处理

WSNs 对所有节点的数据进行汇聚，计算生成信誉值序列X，即网络包含m 个节点，节点信誉值序列由m 个数值组成:为节点x的综合信誉值。

1.6 计算相似度和生成相似度序列

将任意节点的信誉相似度序列和样本序列视为n 维欧氏空间中的两个点，当其欧式距离越大时，表示节点的信誉序列与样本序列之间的相似度越小;反之，其相似度越大。最终即可产生相似度序列S。

1.7 聚类和恶意节点识别

节点的信誉时间序列与基准序列的相似度越高，说明节点行为离恶意节点与正常节点区分的临界点越近;反之，相似度向0 收敛。

通过使用K-mediods 算法找最优聚类，实现对具有亚攻击性节点的识别。这种节点的信誉往往贴近系统阈值，将此属性体现在信誉时间序列与基准序列的相似程度上，从数值上则为相似度接近1。

使用K-mediods 聚类算法对相似度数据集S 进行聚类，识别恶意节点的处理过程。

输入:相似度数据对象的数据集。经过聚类预计得到K 个聚类，每个包含n 个对象。

输出:K 个由像素度极高的对象组成的数据集，使得每个对象与其最近中心点的差异度总和最小，该数据集中心对象的值越接近1，则越接近系统阈值，视为亚攻击节点。

1)初选数据中心:从输入的数据对象中随机选择K 个点，作为初始中心点。

3)迭代优化:对每个非中心点依次执行:用当前点替换其中一个中心点，并依据代价函数计算出由此所产生的总代价，若为负，则保留此次替换;反之，还原中心点。

4)终止迭代:当替换不能再产生更好的聚类划分时，终止迭代。本算法的具体实现过程如图2 所示。

图2 算法流程图Fig 2 Algorithmic flow chart

2 实验分析

在Matlab 中，依照上文的设计，建立了基于时序信誉机制的WSNs 信誉模型，并且验证了算法的有效性。

在WSNs 中随机的设置50 ～300 个节点，其中有1/10节点以0.4 ～0.6 的概率对网络进行攻击;在50 ～300 个时间间隔内，为网络中所有节点生成其信誉序列;通过改变节点数量n、信誉序列长度m，K-mediods 中的参数K，对不同条件下的识别效果进行分析。

2.1 参数对算法性能的影响

不同时序长度m 会对结果产生不同的识别精确度，分别将时序长度m 设置为10，50，100，150，200，250，300，结果如图3 所示。时序长度的增长可以有效地提高识别率，但会导致算法在时间和空间上开销增大。

图3 不同序列长度对识别率的影响Fig 3 Influence of different sequences length on recognition rate

在K-medoids 聚类算法中，K 值的选择对结果有非常明显的影响。K 值的选择一般都由经验确定，再根据实际结果调整，最终选出最优值。

分别将K 取值为2，3，4 对算法进行检验，以识别率和误判率为选择条件，最终确认K 值。综合分析发现:当K=3 时，算法在识别率和误判率两方面都有较好的效果，如图4、图5 所示。

图4 不同K 值对恶意节点识别率的影响Fig 4 Influence of different K value on recognition rate of malicious node

图5 不同K 值对正常节点误判率的影响Fig 5 Influence of different K value on misjudgment rate of normal node

2.2 与信誉阈值模型的性能对比

本算法的设计初衷是对原有的信誉阈值模型的不足加以补充，通过改进来保证信誉阈值模型对更加隐蔽的亚攻击节点进行有效的识别。在信誉阈值机制下，阈值的设定多依赖经验。为对比本算法对原有识别方法的改进，选择多个不同阈值进行仿真，比较识别效果。

在本算法中，需要一个类似判断阈值的信誉参考值，在此折中地将阈值设置为0.5。使用本算法识别出来的恶意节点:一部分是信誉值低于0.5 的节点;另一部分是本算法识别出的亚攻击节点。同时分别使用λ=0.4，0.5，0.6 作为阈值，对恶意节点的识别率进行比较。通过实验可以发现，提高阈值可以提高识别率，但误判率也会提高。而本文算法可以在提高识别率的同时(图6)，保证误判率稳定(图7)。