在无线传感器网络(wireless sensors network,WSN)中,节点的位置信息无论对于环境监测和预报、目标跟踪等实际应用领域,还是基于地理位置的拓扑结构控制、路由算法等协议都起着重要的作用。但在实际应用中,传感器节点通常被布置于无人维护或者维护较困难的物理环境下,节点的定位过程容易受到来自内部或是外部的攻击,导致WSN产生错误或无效的定位结果[1]。
网络节点受到攻击的形式可以分为内部、外部攻击2种。内部攻击是攻击者通过俘获节点来获得信息密钥等信息,可以通过数据加密等方式进行防范;外部攻击是指恶意节点通过在物理和链路层上采用阻挡、反射等手段对信号进行干扰,或者在网络层采用重放、篡改报文的方式制造假象,典型的攻击方式有移位、重放、阻塞、虫洞攻击等,而常规的基于加密或变频等安全机制难以防御上述类型的攻击[2]。近年来,研究者提出了许多节点安全定位及恶意节点的检测算法,见文献[3]。然而,这些方法只是将恶意节点造成的影响降低或是检出后剔除,并没有对其攻击的类型进行后续的分析及识别,从而为以后有针对性地处理位置攻击事件,有效保障网络安全带来了不利影响。
支持向量机(support vector machine,SVM)是一种基于统计学习理论的分类算法,由于在分类问题的良好表现,已被应用于无线传感器网络领域的识别和检测问题。文献[4]基于SVM提出了一种入侵检测算法,该系统把网络拓扑分成簇头、簇成员和Sink 3层结构,每层均能根据SVM的训练结果进行入侵检测的判断。文献[5]利用SVM算法能够在高维空间对非线性样本进行分类的优点,通过各传感器节点估测其与锚点间的距离作为特征向量,最终对未知节点所属立方体空间进行分类来实现定位未知节点。以上算法都是集中式求解的,如果应用于能量与计算能力均受到限制的传感器网络,会出现大批节点的能量耗尽并失效;而且基于传统向量机分类器,对于不同数据的适应性较差。因此,研究具有高效识别能力,并能根据数据特征灵活改变的分布式算法具有重要的现实意义。
本文设计了一种分布式的交替方向-Lp范数支持向量机(ADM-PSVM)定位攻击类型识别算法。该算法将p范数支持向量机作为识别的核心算法,通过引入分布式计算中的交替方向乘子法,将其计算过程分布于网络的不同检测节点,再利用邻居节点的位置、能量信息将迭代过程进行传递。由于该算法充分利用了支持向量机分类器优良的分类特性,同时也利用了ADMM迭代快速的特性,因此能在分布式的网络环境中对定位中的攻击行为进行准确而快速的识别。
1 WSN定位攻击识别模型构造 1.1 WSN定位攻击特点分析假设网络中存在n个未知节点S1,S2,…,Sn,每个节点的实际位置表示为(xSi,ySi),i=1,2,…,n;另外有m个锚节点B1,B2,…,Bm,每个锚节点的位置表示为(xBj,yBj),j=1,2,…,m。未受到攻击时,某一未知节点S1在通信范围内共存在未知节点p个,锚点q个,因此计算出S1到未知节点及锚点之间的距离估计值分别为di,i=1,2,…,p,dj,j=1,2,…,q。
本文以未知节点S1定位过程中,受到4种外部攻击而成为恶意节点A1为例,逐类分析其节点间距离以及邻居节点信息的变化。①重放攻击时,恶意节点A1将锚节点B1发往未知节点S2、S3的位置数据截取之后,随后重新发给它们,误让S2、S3认为A1是锚节点B1,而原来节点S1的ID信息不广播,其他邻居节点将不再发现S1。②在虫洞攻击中,攻击方在距离S1较远的某一个位置通过一个低延迟的连接接收锚节点以及未知节点发来的位置与距离信息,并在A1处重放它们,此时A1增加的距离信息分别为di,i=p+1,p+2,…,p+u,dj,j=q+1,q+2,…q+v。③阻塞攻击时,在节点A1周围通过阻挡等手段削弱锚节点Bj发送至其他节点S2、S3的信号强度,使B1到锚节点之间的距离dj增加,并使A1与其相邻所有节点的信号强度减弱或是消失。④移位攻击即攻击者重新放置未知节点S1,导致S1的距离信息di,i=1,2,…,p,dj,j=1,2,…,q的取值重新改变。
经上述分析可知各种攻击类型对于未知节点S1与其他未知节点或是锚节点的距离均会产生一定程度影响。将这些含有攻击特征的数据投射到一个二维平面后,如果能找到几条直线可以将这几类数据分开,那么这些直线就相当于最优分类平面,攻击类型识别问题进而可以转化为求解多个受约束的凸二次规划问题。本文根据以上分析,基于支持向量机和分布式迭代算法,研究在WSN网络环境下,根据数据类型的不同且依赖相邻节点间相互协作的分布式识别攻击类型的方法。
1.2 基于线性支持向量机的分类模型在一个有限空间Rn里,假定有n个已标记的训练样本,其样本集表示为{xi,yi},其中xi∈RN,yi∈{1,-1},i=1,2,…,n。在线性可分情况下,SVM的目的就是找到一个最优超平面,能将数据集中的2类样本完全分开并使2类数据点到超平面的间隔最大,寻找该最优分类面的问题可转化为以下最优问题[6]:
对于具有可分结构的凸规划问题,其模型如下:
交替方向乘子法按照如下顺序依次更新变量w、z以及乘子u,第k次的各个变量迭代更新步骤为[7]:
本文在(2)式和(5)~(7)式的基础上进行改进,首先加入Lp范式约束,其中0 <p≤2;同时考虑到后续的分布式分类计算,将原问题乘常数2,使其依然等价于问题(1)。从而提出的p范数ADMM-SVM分类算法的目标函数和约束条件改写为如下形式
改写之后,问题(7)将可以用2个节点求解,因为等式约束保证了任何一个节点优化得到的可行解与另外一个节点的解一致。因此,将其中的一项进行改写后,得到
依据交替方向乘子法,第k次迭代步更替步骤可以写为:
如同在集中式SVM的情况下,问题(8)将通过其对偶问题解决,为了达到这个目标,引进拉格朗日乘子α(k),并根据文献[8],(9)对应的增广拉格朗日函数为
注意到上述目标函数中含有‖w‖pp,所以为了顺利求得其对偶问题,必须保证在每一次迭代中w(k)值的有效性。因此引入向量V来表示‖w‖pp,得:
在算法实现过程中,一旦解出w1(k-1),即将V=|w1(k-1)|p-2作为下一次迭代的目标函数中V=|w1(k)|p-2的近似值代替,这样每一次迭代依然是标准的二范数SVM优化问题,而在初次迭代中,任意置一个初值或由二范数SVM作为w1(0)的初值;另外,由于0 <p≤2,则p-2 <0,为了保证w1为正,在计算过程中将负号提取出来,完成后再将负号加上。
根据KKT条件,得到
把上述条件代入L′({w1(k)},{ξin(k)},{av2(k)}{α1(k)}),其对应的对偶问题可以表示为:
同理,(10)式对应的拉格朗日函数为
其对偶问题可以表示为:
基于p范数的ADMM算法的支持向量机迭代步骤(9)~(11)被为归纳为算法1,在相邻的节点中执行的示意图如图 1所示。进行迭代的2个相邻节点自身的能量都大于设定的阈值,并已知惩罚因子C和参数η,然后分别依次设定初始的σi1(0)、σi2(0)、w1(0)、v2(0)、α(0),2个节点首先开始计算第k次迭代的矩阵Nj×Nj维的矩阵[σ1Tdiag{y}X-α(k)](V+η)-1[σ1diag{y}XT-α(k)]及[σ2Tdiag {y}X-α(k)](U-η)-1[σ2diag{y}XT-α(k)],然后2个节点与输入的样本训练集{xi,yi}更新其对偶问题的σi1(k)、σi2(k)值,继续再计算w1(k)、v2(k)的值,当计算完成后,将σi1(k)、w1(k)赋值于节点2,最后更新出α(k+1)。这时根据转发规则,如果2个节点的剩余能量都大于其初始能量比较的阈值时,其继续进行k+1轮迭代,否则,将选择一个距离低于能量阈值节点距离更近且具有更高能量水平的邻居节点,向其传递σi2(k)、v2(k)、α(k+1)值,同时,原来的第2个节点就变成了第1个节点,负责迭代计算σi1(k+1)、w1(k+1)。
3 实验仿真与结果分析 3.1 仿真设置及训练、测试样本获取为检验ADM-PSVM算法的有效性,在MATLAB里对了定位攻击场景进行模拟。假设将600个未知节点以及150个信标节点随机部署点到300 m×300 m的区域,每个节点的剩余能量分配为随机值,通信半径设置为20 m,其定位机制采用文献[9]提出的非测距MDS-MAP算法。按照以下步骤产生识别所需的训练及测试数据集:
1)将网络探测区域划分成边长为60 m的网格单元,使每个网格平均覆盖2~3跳范围内的节点。
2)未受攻击条件下,利用最短路径法分别计算网格内部各未知节点间以及未知节点与信标间的相异性矩阵B1、B2,相异性矩阵定义为B=-JD2J/2,其中D为各节点间平方距离矩阵,J=E-N-1gI,E为N阶单位矩阵,g=IT,I为N阶全一矩阵。每个节点依序号取B1、B2中对应的一行共同构成向量Xnor。
3)从未知节点中取120个节点作为恶意节点,划分为移位、重放、阻塞、虫洞攻击4种类型并实施攻击,在干扰环境下重新计算相异性矩阵,并将节点得到的新一组向量定义为Xatt。
4)以2种环境下产生的相异性矩阵的差的绝对值Xtest=|Xnor-Xatt|形成一组训练特征向量。
5)重复步骤1~4,将形成的向量作为测试样本。
实验中,将上述数据集生成步骤重复5次,总共产生6 000组样本,其中训练样本和测试样本各占50%。为了将本算法应用到多类型攻击识别问题,本文采用目前应用比较广泛的1-v-1-SVM多类识别结构[1]。惩罚因子C=1,η=1,而范数值p对于各类型攻击识别时,从初值0.2,终值2,以等差增加0.2的方式,依次进行测试。
3.2 实验结果与分析ADM-PSVM算法和C-SVM算法对训练集测试样本的识别结果如表 1所示,其中ADM-PSVM的识别率取所有范数p值下正确识别样本数与测试样本数之比之中的最大值。由表 1可以看出,本文提出的算法比传统的标准C-SVM算法具有更好的识别精度。由于本文方法采用范数作为约束条件,不但控制了最优化问题解的稀疏性,也有效选择了与相应攻击类型标签高度相关的特征向量,减小了识别错误率;同时对目标函数使用较低阶次的范数约束,降低了原优化问题对异常值的敏感性,相比起传统的SVM方法,ADM-PSVM避免了个别测距噪声的影响,具有更优优越的性能;在算法训练时间方面,本文提出的算法明显少于C-SVM的训练数据,尤其是当训练数据量较大时,使用ADM-PSVM有明显优势。对于2种算法均在识别过程中出现误差,经分析有以下影响因素:(1)网络测距误差。识别结果中有很多随机产生的无规律识别错误,这些都是由于在估计每对节点距离时,其采用的是最短路径算法,导致在节点分布不均匀的网络中测量距离与实际距离的偏差较大,所引起的相异性矩阵误差所导致。(2)特征样本采集不全。某一种攻击类型被识别为另一种是由于在训练样本获取阶段,网格的划分隔离了某些攻击类型的影响区域,特征向量无法完全获取所有遭受攻击的节点的数据。
数据集目标类 | 训练集数/测试集数 | ADM-PSVM | C-SVM | ||
训练时间/ 测试时间 | 识别率/(%) | 训练时间/测试时间 | 识别率/(%) | ||
虫洞 | 600/600 | 5.47/0.32 | 93.35 | 21.38/3.33 | 83.33 |
重放 | 600/600 | 4.90/0.21 | 91.62 | 20.45/2.26 | 81.67 |
阻塞攻击 | 600/600 | 4.12/0.30 | 95.00 | 22.24/4.45 | 88.33 |
移位攻击 | 600/600 | 5.07/0.20 | 93.71 | 21.11/2.38 | 85.00 |
正常节点 | 3600/3600 | 8.24/0.62 | 94.84 | 36.84/5.47 | 90.63 |
图 2分别给出了恶意节点数目从120增加至180时,各范数p值对应的所有类型节点的识别准确率。从图 2a)、b)显示的结果可以看出,从整体上,对于不同数目恶意节点的攻击环境下,ADM-PSVM算法在p∈[0.2,1.4]或p∈[0.2,1.6]时,对于各类型节点的识别准确率随着p值的增加而逐渐升高;而在其余的范围内,均出现一定幅度下降,在p=2时,其下降幅度最大。以图 2a)中的重放攻击识别为例,算法从0.2增加到0.8时,其识别率仅仅增长了2%,在p=1.4时,识别率增长到最大值91.67%,原因是较低的范数值降低了目标函数对测试集中异常值的敏感性,避免了类似测距误差的影响。但是当范数值选取过大时,当p=2,目标函数选择了所有特征,包含了其他无关的特征以及噪声,导致识别的准确率下降到80%。另外从图 2b)可以看出,在节点总数不变的情况下,当恶意节点的数目增加到180时,各个类型的训练样本数目也相应增加,使分类器获得了更多的判别信息,提高了分类器的整体识别准确率。
图 3分别给出2个范数值p约束下,带有不同惩罚因子η的ADM-PSVM算法对于虫洞攻击训练样本的经验风险误差的影响,恶意节点数目为120。从图 3各子图可以看出:2幅图的误差收敛曲线趋势相似,并且当范数值p=1.6时,ADM-PSVM算法的分类经验风险误差较p=1时有所下降;其次,算法在η=2时,经过了一小段迭代后,分类器的经验风险误差开始逐渐趋于平稳。但是当η值过大时,不仅经验风险误差有所上升,且收敛迭代过程不平稳,迭代曲线出现了明显波动,这表示分类器出现了过度拟合训练数据的现象。虽然ADM-PSVM算法对于η的所有取值均会收敛,但是过大的η值阻碍了收敛速率,因此不同的参数值η会对分类器的训练结果造成一定的影响。
4 结 论为了快速而准确地对传感器网络定位过程中进行攻击的恶意节点进行分类,本文提出了分布式ADM-PSVM节点定位攻击类型识别方法。不同于传统的集中式支持向量机分类器,该算法能将原有的识别问题分解为2个独立的子问题,并能够根据节点能量剩余情况转移迭代运算参数,从而将整体计算任务分配到了不同的节点上;而且ADM-PSVM还引入任意p范数约束的条件,在选择不同的范数p的,不仅在一定程度上选择了相关性更强的特征向量,也降低了由于噪声等干扰造成的影响,增强了分类器的识别性能及稳定性。通过在非测距定位机制下产生的攻击数据集的实验表明,本文提出的ADM-PSVM别算法取得了更优越的识别性能且降低了计算的时间复杂度。
[1] | 刘华博, 崔建明, 戴鸿君. 基于多元分类的无线传感器网络恶意节点检测算法[J]. 传感技术学报, 2011, 24(5): 771-777 Liu Huabo, Cui Jianming, Dai Hongjun. Multivariate Classification-Based Malicious Node Detection for Wireless Sensor Network[J]. Chinese Journal of Sensor and Actuators, 2011, 24(5): 771-777 (in Chinese) |
Cited By in Cnki (11) | |
[2] | Sun Bo, Shan Xuemei, Wu Kui, Yang Xiao. Anomaly Detection Based Secure In-Network Aggregation for Wireless Sensor Networks[J]. IEEE Systems Journal, 2013, 7(1): 13-25 |
Click to display the text | |
[3] | Zeng Yingpei, Cao Jiannong, Xie Li. Secure Localization and Location Verification in Wireless Sensor Networks: A Survey[J]. Journal of Supercomputing, 2013, 64(3):685-701 |
Click to display the text | |
[4] | 汪淑丽. 基于支持向量机的无线传感器网络的入侵检测系统[J]. 传感器与微系统, 2012, 31(7): 73-76 Wang Shuli. Intrusion Detection System for WSNS Based on SVM[J]. Transducer and Microsystem Technologies, 2012, 31(7): 73-76 (in Chinese) |
Cited By in Cnki (9) | |
[5] | 刘健, 沈海斌. 无线传感器网络的三维定位算法研究[J]. 传感器与微系统,2013,32(9): 66-71 Liu Jian, Shen Haibin. Study on 3D Localization Algorithm for WSNS[J]. Transducer and Microsystem Technologies, 2013, 32(9): 66-71 (in Chinese) |
Cited By in Cnki (11) | |
[6] | Chen Jinhu, Takiguchi Tetsuya, Ariki Yasuo. A Robust SVM Classification Framework Using PSM for Multi-Class Recognition[J]. Eurasip Journal on Image and Video Processing, 2015, 1: 1-12 |
Click to display the text | |
[7] | Boley Daniel. Local Linear Convergence of the Alternating Direction Method of Multipliers on Quadratic or Linear Programs[J]. SIAM Journal on Optimization, 2013, 23(4): 2183-2207 |
Click to display the text | |
[8] | Xu M H, Wu T. A Class of Linearized Proximal Alternating Direction Methods[J]. Optimization Theory and Applications, 2011: 321-337 |
Click to display the text | |
[9] | Lu Xiaopei. MDS-Based Wormhole Detection Using Local Topology in Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks, 2012, 2012: 1-9 |
Click to display the text |