分级结构Adaboost算法在无线传感器网络入侵检测中的应用研究*

杨晓元 ，胡志鹏，魏立线

(1.武警工程学院电子技术系网络与信息安全武警部队重点实验室，西安710086;2.西安电子科技大学网络信息安全教育部重点实验室，西安710071)

无线传感器网络部署区域的开放特性和无线通信的广播特性导致网络极易受到外界的各种攻击，严重威胁着整个网络信息安全与正常使用[1－2]。解决这个问题的办法就是开发无线传感器网络入侵检测系统，以保证网络的正常运行。

对传统网络中的入侵检测技术的研究已经较为成熟。Denning[3]提出了5种统计分析方法，其中常用的有操作模型和马尔科夫模型。Wenke Lee研究组和 Stephanie Forrest研究组[4－5]主要使用数据挖掘的方法，采用人工智能、机器学习等技术自动分析原有的数据，从中挖掘出潜在的模式，并预测出入侵行为。除了以上检测方法外，还有利用神经网络、优先状态自动机、计算机免疫系统和基于代理等技术进行网络的入侵检测[6]。

由于无线传感器节点资源严重受限导致传统网络中的各种入侵检测技术无法运用其中。其主要原因有两个:(1)传统网络中的入侵检测算法大多计算量巨大，单个节点的计算能力不足以完成整个检测过程;(2)传统网络中的入侵检测算法没有考虑数据交互而引起的能量消耗，对于采用无线通信的传感器节点来说，大量的数据交互将迅速耗尽节点的能量，最终导致整个网络的寿命大大减少。所以迫切需要研究新的检测方法，在检测精度上、计算复杂度上、能量消耗都能很好地适用于无线传感器网络。

现有的无线传感器网络入侵检测方法很多，却没有一个统一的标准对检测算法的性能做出合理的评估，导致有些算法一味追求高检测率而没有兼顾能量消耗及时间复杂度等问题。为了统一业内的评价标准，在 Porras和 Debar[7]等人提出的传统网络入侵检测算法性能的评价标准的基础上，针对无线传感器网络资源受限的特点，对其入侵检测系统的评价标准进行了探讨，提出了无线传感器网络入侵检测算法性能的评价标准。

提出了一种改进的Adaboost无线传感器网络入侵检测算法，通过增大权重变化量，减轻下一级训练的负担，从而有效地强化对小类错分样本的学习，然后对比传感器节点数据和已建立的入侵行为特征来判断是否存在入侵行为。采用了分级结构提高了检测算法的实时性，采用了二叉树的方法解决了入侵检测的多分类问题，提出了入侵检测系统数据采集传输协议解决因分级结构带来的通信开销增大的问题。

实验结果表明:本算法的准确性、及时性得到了较大提高，同时具有低能耗性。将数据采集传输协议运用在其它检测算法中，得到了较好的效果。

1 无线传感器网络入侵检测系统的评价标准

无线传感器网络是近年来才发展起来的新兴技术，面临的攻击的威胁很多。尽管人们对无线传感器网络入侵检测系统有了初步的研究，但却没有一个明确的标准来评价其性能。传统网络中对于入侵检测算法的评价标准对如何评价无线传感器网络入侵检测算法的性能有重要的借鉴意义。目前，对于传统网络入侵检测系统的评估是根据Porras等给出的3个评价因素和后来Debar等在此基础上又增加的两个性能评价测度:

准确性 指IDS从各种行为中正确地识别入侵的能力。

处理性 指一个IDS处理数据源数据的速度。

完备性 指IDS能够检测出所有攻击行为的能力。

容错性 由于IDS是检测入侵的重要手段，所以它也就成为很多入侵者攻击的首选目标，IDS自身必须能够抵御对它自身的攻击。

及时性 及时性要求IDS必须尽快地分析数据并把分析结果传播出去，以使系统安全管理者能够在入侵攻击尚未造成更大危害以前做出反应。

如果评价无线传感器网络入侵检测系统套用以上几个指标是不够的，因为无线传感器网络相对于传统网络在能量、计量能力上有很大的差别，所以评价无线传感器网络入侵检测系统必须加上低能耗性。下面对这评价指标进行阐述。

低能耗性 由于无线传感器网络中的节点受到能量的限制，所以要求入侵检测系统必须满足低能量耗的特点，降低能耗可以从两个方面着手，一是降低计算复杂度;二是减少通信开销。

2 无线传感器网络入侵检测算法

2.1 改进的Adaboost算法及其理论分析

Adaboost算法是在每一训练样本都赋予一个权重，代表它被某个分量分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就低;相反，如果某个样本点没有被正确分类，那么它的权重就提高，在构造下一个训练集中，它就会被优先选中。通过这样的方式，AdaBoost算法能够针对性地处理那些较困难样本[8－9]。

在具体实现上，最初令每个样本的权重都相等。对于第k次迭代操作，就根据这些权重来选取样本点，进而训练分类器Ck。然后就根据这个分类器，来提高被它错分的那些样本点的权重，并降低可以被正确分类的样本点的权重。然后，更新过权重的样本集用来训练下一个分类器Ck+1。整个训练过程如此进行下去。由于Adaboost算法简单高效，所以在模式识别方面得到了广泛的应用。本文对传统的Adaboost算法作了改进，通过增大权重变化量、寻找最优分类器等方法，大大减轻下一级的负担，从而提高了检测的准确性与及时性。

改进的Adaboost算法的具体步骤如下;

(1)选取训练样本{(x1，y1)，……，(xn，yn)}，其中xi表示每个入侵检测数据的特征向量，yi为类别标识，yi={0，1，2，3，4}分别代表正常样本和 4 种不同的入侵样本;

(2)初始化权值，每个训练样本具有初始权值wo(i)=1/n，即每个样本的初始权值相同;

(3)for t=1……t;

(a)对于样本向量中的每一种的特征j，采用排列组合的方法，从中任意选取m个特征，训练弱分类器 hj，其分类误差为，(M是被错分的样本的数量);

(b)选择其中具有最小误差的分类器hj;作为ht，并记录其特征;

(d)t++;

(4)最终找到了k个最优分类器，h1……hk。每个分类器的权值为，最后的强分类器的判决函数为:，其中sgn为符号函数;根据H(x)的值可以对样本进行分类。θ为判决阈值，初始值设定为所有弱分类器权值的平均值，即。

2.2 分级分类器的设计

无线传感器节点计算能力有限，如果构造一个强分类器进行检测，势必需要大量的计算时间，而入侵检测又对时实性的要求较高，在满足检测精度的同时又要符合实时性的要求是困难的。为了解决这个问题，采用了分级式的分类器[10]。

首先，每个检测节点广播自己的能量;然后，按照能量的多少对检测节点分级，能量较多的划分为第1级检测节点，次之的划分为第2级检测节点，以此类推，分级数量直到满足所需的检测精度为止。其次，上一检测级内的所有检测节点都对该节点进行检测，将检测结果发送到汇总节点，在汇总节点投票判决该节点是否受到攻击，如果可以确定该节点的数据类型，便直接将其排除或做出相应的入侵响应。如果不能确定，便将其送入第2检测级进行处理。以此类推，至到最后一级。如果最后一级仍无法做出判断，可以简单的认为该节点为异常节点，并做出相应的入侵响应。

靠近前面各级的分类器，只使用小部分重要特征进行判断，结构简单，却对大部分的样本做出了检测;靠近后面各级的分类器，虽然采用大量的特征用来检测，但是由于需要处理的样本数目很少，对于整体运算时间的耗费很小。分级结构的入侵检测系统如图1所示。

图1 分级结构的入侵检测系统框图

2.3 基于二叉树的多分类方法

由于文中所使用的弱分类器h是针对二分类的情况，对于多分类的情况，可以将多类问题分解为多个二分类问题，本文使用二叉树方法，每个分类器可以将一类数据的样本分开。具体的说，就是在一个k类分类问题中，先将k类问题进行排序，将第1类与第2……k类样本进行训练，作为第1个分类器，然后将第2类与第3……k类样本进行训练，作为第2个分类器，最后直到把k类数据分开。以4类分类问题为例，多类分类的二叉树结构如图2所示[11]。

图2 四分类二叉树结构

3 数据采集传输协议

由于采用了检测算法是分级结构，级与级之间的通信是必不可少的，所以不得不考虑级与级之间数据传输所消耗的时间与能量。

传输的数据包有2种方法:第1种方法是本级检测节点只收集本级所要用到的特征数据进行检测，传输给下一检测级的信息是“那些节点为不可确定节点”，处于后一级的节点收到消息后，需要重新收集数据，再做入侵检测，至到最后一级;第2种方法是将采集信息的任务全都交给第一检测级，第一检测级收集各级所需要的所有特征，检测时从中选取本级所需特征，如果本级对某一节点的检测结果为不确定节点，本级节点就将所有特征数据全部传给下一检测级，下一检测级直接从接收到的数据中提取所需特征进行检测，无需重新收集所需数据。

理论分析上述2种方法，采用第1种方法，通信数据量较小，但是实时性不高，需要对数据进行多次收集。采用第2种方法，虽然时效性可能有所提高但是通信量会增大。

为了解决时效性与通信能耗之间的矛盾，提出了数据采集传输协议。协议的具体办法是加入数据采集传输节点，这种节点负责采集检测所需要用到的特征信息，给检测节点发送采集信息，还要与汇总节点通信。

第1步，各检测级中的n个检测节点接收Sink节点上训练好的分类器，作为自身的检测算法。第2步，数据采集传输节点采集检测所需数据，将采集到的按照相应检测级传输给的检测节点。第3步，检测节点对从数据传输节点接收到的数据进行处理;而后将检测结果发送给汇总节点。第4步，汇总结点对各检测节点的检测结果汇总，如果本级的n个检测节点中有r个检测节点都认为该节点未受到攻击或可确定所受到攻击的类型，便直接将其排除或做出相应的入侵响应;如果该节点检测结果经汇总后，各类所得的票数都小r，那么就认为该节点为不可确定节点。此时汇总节点通知数据采集传输节点，向下一检测级的检测节点传输检测所需用到的数据，下一检测级按照上述的方法处理信息，直到最后一级。如果最后一级仍无法确定该节点的状况，那么可以简单的认为该节点为异常节点，并对其做出入侵响应。具体过程如图3所示。

图3 入侵检测示意图

4 分级结构的无线传感器网络入侵检测模型

为了实现分级结构，首先必须建立合适的网络入侵检测模型。

假设无线传感器网络模型是一个随即部署在某区域的无线传感器网络。这个网络可以划分为若干个簇。每个簇内的节点可以划分为簇头节点、普通节点、检测节点和数据采集传输节点，簇头节点负责协调和控制簇内节点及其数据的融合，同时还要负责和Sink节点的通信;检测节点负责检测入侵行为;数据采集传输节点是用来采集传输检测所需数据。

其中Sink节点不受电量、存储空间和计算能力等的限制，可以单独运行一套复杂的入侵检测算法。所以训练分类器、通知各检测节点调整参数都由Sink节点负责。

分级结构中每一个检测级中有n个检测节点和一个汇总节点。检测节点的作用是数据分类;汇总节点的作用是将本级各个检测节点的处理的结果汇总，得到各级最终的检测结果，然后再将不可确定节点的信息传送给数据采集处理节点。

数据采集处理节点的作用是收集各级检测所需用到的数据;将各检测级所需用到的特征从收集到的数据中提取出来后，发送给各个检测级用来检测。

网络的具体结构如图4所示。

图4 网络结构

5 仿真实验

使用MATLAB2010B和NS2作为实验平台，实验用数据由Naval Research实验室提供的无线传感器网络数据集[12－13]，包含了正常流量集{NS1，NS2}和攻击数据集{AS1，AS2，AS3，AS4}。其中 AS1、AS2、AS3、AS4模拟实现了 Passive Sinkhole Attacks(PSA)、Periodic Route Error Attacks(PREA)、Active Sinkhole Attacks(ASA)，DOS等四个攻击场景，其中还包括了大量的正常数据信息。这4大类攻击目前是无线传感器网入侵方式，因此可以使用这5类数据进行实验[13－14]。

5.1 准确性评估

首先随机选取训练用和测试用样本各3000条，其中正常数据占60%，DOS攻击样本点15%，Passive Sinkhole Attacks攻击样本占10%，Periodic Route Error Attacks攻击占10%，Active Sinkhole Attacks攻击占5%。使用这些训练数据训练分类器，随后用测试样本进行性能测试，文中改进的Adaboost算法使用了三级分类器，表1是每一级处理所用特征个数以及经各级测试后可确定样本数的比例。

表1 分级结构各级所用特特征数和可确定样本数

改进的Adaboost的检测率与误检测率如表2所示。

表2 分级结构各级测试结果

为了对改进的Adaboost算法的性能作出准确的评价，将其检测结果与Adaboost算法、与BP网络、SVM、核Fisher线性判别等强分类算法进行比较。其结果如表3和表4所示。

表3 两种Adaboost算法测试结果

表4 各种强分类器测试结果

通过实验数据对比，本文所提出的算法在检测精度上只是略高于Adaboost、SVM、BP网络等算法，这是因为文中只用到了三级分类器，这样的检测率对一般的网络是足够的。如果某网络对检测率要求效高，可以通过增加分级级数来达到目的，但同时也会带来能耗增大的问题。

5.2 能耗评估

当检测节点运行入侵检测系统时，通信增加的能耗要远大于计算增加的能耗，节点传输一个比特数据所耗费的能量要比计算一个比特所耗费的能量高约3个数量级。因此本文讨论能耗问题时只考虑检测过程中的通信能耗[14]。

Chndrakasan[15]提出了一种能量消耗模型:传感器节点发送k比特数据所消耗的能量为

传感器节点接收k比特数据所消耗的能量为

其中εamp是信号放大器的放大倍数，Esend和Erev是发送电路和接收电路的能耗，d是信号的发送距离。

分别对加入和未加入数据采集传输协议的检测系统的能耗情况进行仿真实验。为了能够更客观地评价改进的Adaboost算法的低能耗性，还仿真了采用核Fisher线性判算法的检测节点能耗情况。能耗如图5所示。

图5 两种分类算法的能耗

通过图5可以看出，未加入数据采集传输协议时，采用两种检测算法的检测节点能耗都非常高。加入数据采集传输协议后，节点的能耗都有了明显的降低。虽然改进Adaboost的算法的能耗略高于核Fisher线性判别的能耗。但对其评估时，考虑到及时性、准确，能耗的略高可以忽略。

对检测节点内的能耗的分析，可反映出检测系统可工作的时间。对于整体网络来说，还要对加入检测系统前后网络的生存周期进行比较。

网络生存周期的定义目前主要有2种:第1，当网络中有一个节点能量耗尽，就认为此时就是网络的生存周期;第2，网络中有些存点死亡，但是整个网络还是能继续工作，这样我们也可以认为网络是存在的，此时就是网络的生存周期。文中网络是部署在野外工作环境中的大型网络，所以采用第2种说法更为合适。加入检测系统前后网络的生存周期如图6所示。

图6

从图6中可以看出，加入了检测系统在有入侵情况下，大大提高了网络的生存周期;即便在没有入侵的情况下，也不会对网络的生存周期影响太大。这是因为加入的检测系统自成一体，其中的各个节点所需要的能量来自于自身，不会给网络带来额外能耗。整体网络能耗的略微增加，主要是由入侵响应时删除入侵节点导致的拓扑变化和收接转发检测结果所产生的。

5.3 及时性评估

评价入侵检测算法的性能，仅仅对比检测率与误检率是不科学的，还需要考虑到时间因素。好的检测算法即要满足高的检测率还要满足低的时间消耗。

由于本文中的检测算法是分级结构，所以在时间的计算上，考虑检测用时的同时还需考虑两级之间数据传输所消耗的时间。表5是分级结构各级测试所用时间。

表5 分级结构各级测试所用时间

定义1设分级结构分类器共有n级，各级所用的时间为t1……tn，经各级测试后所能确定数据类型的样本占总数的比例为ω1……ωn，那么分级结构分类器检测所用的加权平均时间为

定义2假设测试样本有m条，分级结构分类器共有n级，经过各级测试后所能确定数据类型的样本占总数的比例为ω1……ωn，那么需要传给下一级检测的样本的数量为，那么分类器检测时的加权平均传输量为，l为一个数据包的包长。

根据IEEE802.15.4中MAC层的数据帧格式，可以将数据包需要分为3类，第1类为检测节向汇总节点发送检测结果，它的包长l可以认为是8个字节，包括2个字节的帧控制域;1个字节的帧序号;2个字节的地址消息;1个字节的MAC层有效数据(检测结果);2个字节的帧检验序列;第2类为汇总节点向数据采集传输节点传送不可确定节点信息，它的包长l可以认为是9个字节，MAC层有效数据为2字节;第3类为数据采集节点向检测节点发送检测用数据，它的包长l需要根据传输的特征向量的大小来确定，一般每一个特征向量的数据大小为1字节。

表6 各级传输所用时间

根据定义1和定义2可以计算出改进的Adaboost算法所用的总时间为T=t1+t2

另外，还将文中算法用时与其它几种算法的用时进行了对比，表7是各种分类器所用时间。

表7 各分类器检测用时间

从表7可以看出改进的Adaboost算法在时间的消耗上远远小于其它各种分类器，从而可以更好的满足无线传感器网络入侵检测对实时性的要求。

6 结论

本文对如何评价无线传感器网络入侵检测系统的性能做出评价标准。提出了一种改进的Adaboost的无线传感器网络入侵检测算法，该算法对比传感器节点数据和已建立的入侵行为特征来判断是否存在入侵行为。虽然本算法具有高效的检测率和高效的实时性，但同时却带来了高能耗的问题，为了解决高能耗，提出了数据采集传输协议。通过理论分析和仿真实验，使用文中提出的评价指标对其性能进行估价。综合准确性、低能耗性、及时性考虑，改进的Adaboost算法的性能要高于其它的检测算法。

另外，为了测评数据采集传输协议的效果，还将其运用在核Fisher线性判别检测算法中，使用本协议后，该算法性能有明显提高，足以证明本协议适用于各种入侵检测算法。

但是，对于评价标准中的处理性、完备性、容错性未能做出定性定量的评价。如何定性定量的评价一个无线传感器网络入侵检测系统的这几个性质是下一步工作的重点。

[1]Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Network:A Survey on Sensor Network[J].IEEE Communications Magazine，2002，40(8):102－114.

[2]Perrig A，Stankovic J，Wagner D.Security in Wireless Sensor Networks[J].Communications of the ACM，2004，47(6):53－57.

[3]Denning D E.An Intrusion Detection Model[J].IEEE Transactions on Software Engineering，1987，13(2):222－232.

[4]Lee W，Stolfo S J，Mok K W.A Data Mining Framework for Building Intrusion Detection Models[C]//Proceedings of IEEE Symposium on Security and Privacy，Oakland，1999.110－116.

[5]Lee W，Stolfo S J，Mok K W.Adaptive Intrusion Detection:A Data Mining Approach[C]//Artificial Intelligence Review.2002，14:533－567.3989.Berlin:Springer-Verlag，2006:293－308.

[6]Rajasegarar S，Leckie C，Palaniswami M，et al.Distributed Anomaly Detection in Wireless Sensor Networks[C]//Proceedings of the 10th IEEE Singapore International Conference on Communication System(ICCS 2006).

[7]王白亮，罗守山，杨义先.入侵检测系统的测试与评估[EB/OL].http://www.netmaker.com/art_8032.html.

[8]张重庆，李明禄，伍民友.数据收集传感器网络的负载平衡网络构建方法[J].软件学报，2007，18(5):1110－1121.

[9]Richard O，DudaPeterE，HartDavid G Stort.Pattern Classification second Edition[M].机械工业出版社，2005.

[10]王勇，陶晓玲.分级结构的AdaBoost入侵检测方法研究[J].西安电子科技大学学报(自然科学版)，2008:263－268.

[11]Perrig A，Szewczyk R，Tygar J D，et al.SPINS:Security Protocols for Sensor Networks[J].Wireless Networks，2002，8(5):521－534.

[12]杜晓通.无线传感器网络络技术与工程应用[M].机械工业出版社，2010.

[13]Downard I.Simulating Sensor Networks in NS-2.Technical Report[R].NRL/FR/5522－04－10073，Naval Research Laboratory，Washington，D.C.，U.S.A.，May 2004.

[14]Yan K Q，Wang S C，Liu C W.A Hybrid Intrusion Detection System of Cluster-Based Wireless Sensor Networks[C]//Proceedings of the International Multi Conference of Engineers and Computer Scientists 2009Ⅰ.

[15]Heinzelman W B，Chndrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[D].IEEE Transaction on Wireless Communications，2002，1(4):660－670.

[16]Onat I，Miri A.An Intrusion Detection System for Wireless Sensor Networks[C]//Proceedings of the IEEE International Conference on Wireless and Mobile Computing，Networking and Communications(WiMOB 2005).