随着网络的发展，无线Mesh网络^[1](wireless Mesh network，WMN)被广泛应用，其安全问题日益突出。由于WMN中的每个节点均可发送和接收数据，并可以与一个或多个对等节点直接通信，故极易受到内部恶意节点攻击。一旦网络中的某个节点被控制，那么控制者便可通过该节点进行内部攻击(如节点访问控制、恶意流量攻击)，造成整个网络瘫痪。控制者也可以利用对等节点间的信任发送虚假路由信息，改变网络拓扑或将正常节点变成恶意节点。因此，如何有效识别WMN恶意节点已经成为目前的研究热点和难点问题。

文[2]提出了基于蚁群行为算法的蚁群优化(ant colony optimization，ACO)路由算法，通过路由表统计的方式，找出对链路通信质量降低影响较大的节点(即恶意节点)，由于WMN网络拓扑变化较快，该方法对恶意节点的检测难以满足实时性要求。文[3]提出了一种计算路由事件周期的无线传感器网络检测方案，通过计算路由事件周期的平均数判断恶意节点，由于无线传感器网络的结构与WMN有显著的差异，在WMN中采用上述方法时检测率并不高。文[4]在防欺骗检测系统的基础上，提出了一种恶意节点检测系统，根据节点间的会话报告构成会话链表集合，通过分析链表集合发现恶意节点。该系统在恶意节点较多时，检测率有所下降且误报率上升。文[5]提出了一种基于网络性能特征序列的聚类检测方法，运用K-means聚类算法对序列进行聚类分析并识别恶意节点。当恶意节点较多时，该算法的复杂度高且检测效率较低。文[6]提出了一种基于跨层监听机制的恶意节点检测算法，使用节点信息挖掘和节点距离估计方法消除节点脱离通信范围对恶意节点检测的影响。该方法网络资源占用率高且对网络性能影响较大。

由于WMN具有链路通信质量易受环境影响、网络拓扑变化较快等特点，上述研究成果还不适用于资源有限、工作环境多变的无线Mesh网络。本文提出一种基于移动Ad-hoc网络更优方案(better approach to mobile Ad-hoc networking，BATMAN)路由协议^[7]的恶意节点检测模型。该模型通过分析源节点消息(originator messages，OGM)生成虚假OGM率和丢包率等参数记录路由变化。在协议规则下对这些参数进行处理，并将其作为节点恶意行为的度量，在网络节点上识别出周围的可疑节点。通过改进的K/N投票算法计算出可疑节点置信值作为恶意节点判定的标准，提高了WMN的恶意节点检测率，降低了误报率。

1 模型设计

本文提出的基于BATMAN路由协议的恶意节点检测模型(malicious node detection model based on BATMAN，MNDMB)由2个模块组成：OGM解析模块、恶意节点判定(malicious node decision，MND)模块。OGM解析模块捕获和解析OGM消息，生成相应参数(虚假OGM率、丢包率)；MND模块处理OGM解析模块产生的参数，判定恶意节点。MNDMB模型结构如图 1所示。

在MNDMB模型中，对网络中恶意节点的检测方法设计如下：

1) 在网络中的各节点安装BATMAN路由协议，各节点周期性发送OGM。

2) 在各节点上运行一个入侵检测系统(intrusion detection systems，IDS)实例Bro^[8]作为OGM解析模块的基础，通过添加自定义功能构成OGM解析模块。该模块在节点的网络接口调用数据包捕获函数^[9](Libpcap)捕获OGM，并对OGM进行解析，获取相应路由参数，计算节点恶意行为度量。

3) 计算的度量值(虚假OGM率、丢包率)作为可疑节点判定模块的输入，将行为度量和预测值(阈值)比较，判断节点行为是否正常，将判定结果作为一致性投票机制的输入。

4) 一致性投票机制采用改进的K/N投票算法^[10]由多节点共同判定发送OGM的节点是否为恶意节点。

2 源节点消息解析 2.1 模块结构

在MNDMB模型中，采用先验式路由协议BATMAN协议作为基础协议。首先，BATMAN路由协议能为WMN提供更高的速率；其次，与常用的优化链路状态路由(optimized link state routing，OLSR)协议相比，BATMAN路由协议具有更高的运行效率且对带宽的占用率更低。

在MNDMB模型中，通过网络中各节点周期性发送的OGM来检测恶意节点。OGM有52个字节，包含源节点地址、转发节点地址和表示OGM更新程度的特殊序列号SN(sequence number)等重要参数。OGM结构如图 2所示。

MNDMB模型主要通过OGM解析模块完成对OGM消息的捕获与分析。本文在MNDMB模型中，采用实时的网络入侵检测系统Bro作为该模块的基础平台，在节点的网络接口通过Libpcap捕获OGM。本文选择Bro是因为它提供了模块化结构，可以在其基础上添加OGM解析算法。

OGM解析模块的组成包括3层：最1层为Libpcap捕获函数层，用于捕获OGM；第2层是事件引擎层，根据端口号发送OGM字段到不同协议分析器，协议分析器解析字段的有效数据帧生成关键数据；第3层是策略脚本解释器，处理第2层产生的数据。OGM解析模块的处理流程如图 3所示。

2.2 解析算法

OGM解析算法即策略脚本解释器。由于本文的主要研究对象是网络内部的恶意节点，其常用的攻击手段包括虚假路由信息注入和数据包丢弃2种，故本文在解析模块中设计了虚假OGM检测算法和丢包检测算法。虚假OGM检测算法用来检测节点通过OGM发送虚假路由信息的行为，丢包检测算法用来检测节点恶意丢弃OGM的行为。

2.2.1 虚假OGM检测算法

该算法采用滑动窗口^[11]和序列号匹配的方法，各节点在接受OGM时维护3个变量：接收窗口大小(receive window size，RWS)、可接收帧序号(largest acceptable frame，LAF)、最近收到的帧序号(last frame received，LFR)，算法流程设计如下。

步骤1 开始假设节点收到的OGM数量和虚假OGM数量均为0，分别记为TFP_ogm=0，FP_ogm=0。

步骤2 当收到具有序列号SN的OGM时，TFP_ogm加1。

步骤3 若LFR < SN≤LAF，说明该OGM的SN在接收窗口内，表明该OGM合法。

步骤4 若SN≤LFR或SN>LAF，说明该OGM的SN不在接收窗口内，则表明该OGM是虚假的，FP_ogm加1。

步骤5 计算固定时间周期内的虚假OGM率R:

$ R = \frac{{{\text{F}}{{\text{P}}_{{\text{ogm}}}}}}{{{\text{TF}}{{\text{P}}_{{\text{ogm}}}}}}. $

(1)

将式(1) 计算得到的R作为MND模块的输入。

2.2.2 丢包检测算法

在BATMAN路由协议中，节点维护一个固定大小的滑动窗口和记录OGM数量的计数表，窗口随收到的OGM的SN更新而移动。在虚假OGM检测算法的基础上，若OGM中的SN在滑动窗口范围内，则节点将接收该OGM，计数表的值加1，滑动窗口不发生移动；若SN大于窗口最大序列号，则滑动窗口会将该SN设为最新序列号，窗口向前移动，计数表的值加1。

算法流程设计如下。

步骤1 源节点发送OGM前，更新SN值，当前计数表的值加1。假设第一个OGM的序列号为1，则每发送一个OGM消息，计数表的值加1，下一个OGM的序列号等于当前计数表的值加1。

步骤2 将SN和其他数据组合生成的OGM发送给其他节点。相邻节点收到源节点发送的OGM，将其中的SN赋给计数表，同时选择转发或者保留该OGM。

步骤3 若SN与当前计数表的值相差大于1，则说明上游节点可能出现了恶意丢包行为。SN与当前计数表的差值即为丢弃的OGM数量。

步骤4 设源节点在一定周期内发送的OGM总数为W_SN，接收OGM的节点计数表的值为W，计算丢包率RD：

$ {\text{RD = }}\frac{{{W_{{\text{SN}}}}-W}}{{{W_{{\text{SN}}}}}}. $

(2)

将式(2) 计算得到的丢包率RD输入MND模块。

3 恶意节点判定

恶意节点判定模块由可疑节点判定(suspicious node determination，SND)模块和协商一致判定(cooperative consensus mechanism，CCM)模块组成。OGM解析模块输出的虚假OGM率和丢包率等数据作为SND模块的输入并与采用非线性回归模型拟合的阈值Th比较，判断节点是否有发送虚假路由信息或者丢包的行为。然后，通过CCM模块，由所有节点投票决定该节点是否是恶意节点。恶意节点判定模块的处理流程如图 4所示。

3.1 可疑节点判定模块

可疑节点判定模块将OGM解析模块的输出值(R、RD)和由非线性回归模型拟合的检测阈值Th (Th_R、Th_RD)进行比较，当某一输出值大于阈值时，则判定节点为可疑节点。

3.1.1 阈值Th的非线性回归模型

在真实Mesh网络中，产生虚假路由信息和造成数据包丢失的原因有很多，例如数据包被丢弃既可能是节点恶意丢包，也可能是链路自然丢包，因此设置合适的阈值非常重要，故在SND模块设计了一个非线性回归模型拟合阈值以提高检测精度。

选择OGM解析模块在一定时间内的n组同类计算数据，设为(t₁, x₁), (t₂, x₂), …, (t_n, x_n)，其中t=(t₁, t₂, …, t_n)和x=(x₁, x₂, …, x_n)表示产生数据的时间和计算值，用该n组数据构造函数X(t), 在满足逼近误差很小的条件下, 可将X(t)表示为

$ X\left( t \right) = \sum\limits_{j = 1}^n {{\lambda _j}{H_j}\left( t \right)} . $

(3)

式(3) 中，根据实际WMN选取和式的总数m(m≤n)和基函数H_j(t)。此处，选择的基函数H_j(t)=t^j-1，则式(3) 可表示为

$ X\left( t \right) = {\lambda _1} + {\lambda _2}t + {\lambda _3}{t^2} + \cdots + {\lambda _m}{t^{m-1}}. $

(4)

通过求解系数向量λ=(λ₁，λ₂，…，λ_m)^T, 得到函数X(t)对应的实际值x的估计值，即阈值Th。

假设节点在t₁~t₄时刻采集的丢包率分别表示为(t₁, RD₁)、(t₂, RD₂)、(t₃, RD₃)、(t₄, RD₄)，使用三次多项式Th(t)=λ₁+λ₂t+λ₃t²+λ₄t³对这4组数据拟合，采样周期t_i的基函数矩阵为

$ \boldsymbol{N = }\left[\begin{gathered} {H_1}\left( {{t_1}} \right)\;\;\;\;{H_2}\left( {{t_1}} \right)\;\;\;{H_3}\left( {{t_1}} \right)\;\;\;{H_4}\left( {{t_1}} \right) \hfill \\ {H_1}\left( {{t_2}} \right)\;\;\;\;{H_2}\left( {{t_2}} \right)\;\;\;{H_3}\left( {{t_2}} \right)\;\;\;{H_4}\left( {{t_2}} \right) \hfill \\ {H_1}\left( {{t_3}} \right)\;\;\;\;{H_2}\left( {{t_3}} \right)\;\;\;{H_3}\left( {{t_3}} \right)\;\;\;{H_4}\left( {{t_3}} \right) \hfill \\ {H_1}\left( {{t_4}} \right)\;\;\;\;{H_2}\left( {{t_4}} \right)\;\;\;{H_3}\left( {{t_4}} \right)\;\;\;{H_4}\left( {{t_4}} \right) \hfill \\ \end{gathered} \right]. $

其中，设矩阵N的每个元素为n_ij=H_j(t_i)。

节点丢包率预测函数的4维向量Th=Th(t₁), Th(t₂), Th(t₃), Th(t₄)^T可表示为

$ {\mathbf{TH}} = \boldsymbol{N\lambda = }\left[\begin{gathered} {H_1}\left( {{t_1}} \right)\;\;\;\;{H_2}\left( {{t_1}} \right)\;\;\;{H_3}\left( {{t_1}} \right)\;\;\;{H_4}\left( {{t_1}} \right) \hfill \\ {H_1}\left( {{t_2}} \right)\;\;\;\;{H_2}\left( {{t_2}} \right)\;\;\;{H_3}\left( {{t_2}} \right)\;\;\;{H_4}\left( {{t_2}} \right) \hfill \\ {H_1}\left( {{t_3}} \right)\;\;\;\;{H_2}\left( {{t_3}} \right)\;\;\;{H_3}\left( {{t_3}} \right)\;\;\;{H_4}\left( {{t_3}} \right) \hfill \\ {H_1}\left( {{t_4}} \right)\;\;\;\;{H_2}\left( {{t_4}} \right)\;\;\;{H_3}\left( {{t_4}} \right)\;\;\;{H_4}\left( {{t_4}} \right) \hfill \\ \end{gathered} \right]\left[\begin{gathered} {\lambda _1} \hfill \\ {\lambda _2} \hfill \\ {\lambda _3} \hfill \\ {\lambda _4} \hfill \\ \end{gathered} \right]. $

在t₁~t₄时刻节点实际的丢包率向量RD=(RD₁, RD₂, RD₃, RD₄)^T，则逼近误差向量δ可表示为

$ \boldsymbol{\delta = N\lambda }-{\mathbf{RD}} $

使用最小二乘法使逼近误差向量δ的范数最小，可以得到：

$ \min \left( {{{\left\| \boldsymbol{\delta } \right\|}^2}} \right) = \sum\limits_{i = 1}^4 {{{\left( {\sum\limits_{j = 1}^4 {{n_{ij}}{\lambda _j}}-{\text{R}}{{\text{D}}_i}} \right)}^2}.} $

(5)

用式(5) 求解||δ||²的微分，令结果为0，即

$ \begin{gathered} \frac{{{\text{d}}{{\left\| \boldsymbol{\delta } \right\|}^2}}}{{{\text{d}}{\lambda _x}}} = \sum\limits_{i = 1}^4 {2\left( {\sum\limits_{j = 1}^4 {{n_{ij}}{\lambda _j}}- {\text{R}}{{\text{D}}_i}} \right){n_{ix}} = 0, } \hfill \\ \;\;\;\;\;\;\;\;\;\;\;\;\;x = \left[{1, 4} \right]. \hfill \\ \end{gathered} $

即

$ \begin{gathered} {\left( {\boldsymbol{N\lambda }-{\mathbf{RD}}} \right)^{\text{T}}}\boldsymbol{N = }{\mathbf{0}}, \hfill \\ {\boldsymbol{N}^{\text{T}}}\left( {\boldsymbol{N\lambda }-{\mathbf{RD}}} \right) = {\mathbf{0}}, \hfill \\ {\boldsymbol{N}^{\text{T}}}\boldsymbol{N\lambda } = {\boldsymbol{N}^{\text{T}}}{\mathbf{RD}}. \hfill \\ \end{gathered} $

基函数H_j(t)=t^j-1, 故矩阵N为满秩矩阵，得到N^TN正定，故存在N^TN的逆矩阵，则

$ \boldsymbol{\lambda } = {\left( {{\boldsymbol{N}^{\text{T}}}\boldsymbol{N}} \right)^{-1}}{\boldsymbol{N}^{\text{T}}}{\mathbf{RD}}. $

至此，得到优化回归系数λ。将优化回归系数λ代入式(4)，得到Th。

3.1.2 可疑节点判定

假设网络中某一节点M收到相邻节点N连续发送的OGM数据包，且经过OGM解析模块的处理。根据节2.2，可以得到节点N的虚假OGM率R_N。将得到的R_N和阈值Th_R比较，判定节点N是否是可疑节点，同时节点M的SND模块向周围节点发送对节点N的检测结果D_N，即:

当R_N>Th_R时，D_N=0, 节点N为可疑节点；

当R_N < Th_R时，D_N=1, 节点N为正常节点；

当R_N=Th_R时，等待下一次检测。

3.2 一致性投票机制

在真实网络中，由于节点之间距离和链路质量不同等原因，单一节点的判定结果可能存在误差，因此需要采取多节点投票决策的方法避免发生此类问题。在CCM中，采用的是一致性投票机制。当WMN中大多数节点判定某节点为可疑节点时，则该节点可被判定为恶意节点。

在实际的投票过程中，应该考虑参与投票的网络各节点监控能力的差异，即置信值。在本文研究中，采用改进的K/N投票算法对参与投票的节点置信值进行计算，即节点的置信值大小取决于其他节点对它的度量结果。置信值是判定恶意节点的重要标准，也是节点参与投票的权重。节点置信值越高，则该节点在投票中的影响越大，反之则越小。

给定一个长度为a的投票节点集合(a个参与协同检测的网络节点)，每个节点的置信值分别为A₁, A₂, …, A_a，则节点M的置信值A_M为

$ {A_M} = \frac{{{A_1}{D_{1M}} + {A_2}{D_{2M}} + \cdots + {A_a}{D_{aM}}}}{{{A_1} + {A_2} + \cdots + {A_a}}}. $

其中: D_iM为第i个节点对节点M的检测结果，A_i为第i个节点的置信值。令置信值加权和为S，则

$ S = {A_1}{D_{1M}} + {A_2}{D_{2M}} + \cdots + {A_a}{D_{aM}}. $

令置信值向量$\boldsymbol{A = }\left[\begin{array}{l} {A_1}\\ {A_2}\\ \; \vdots \\ {A_a} \end{array} \right]$，检测结果向量$\boldsymbol{D = }\left[\begin{array}{l} {D_{1M}}\\ {D_{2M}}\\ \;\; \vdots \\ {D_{3M}} \end{array} \right] $，则S=D^TA。

上述方程中的矩阵可能含有多个零元素，属于大型稀疏矩阵方程组，故用Jacobi迭代求解^[12]，进一步可求得节点M的置信值A_M：

$ {A_M} = \frac{S}{{{A_1} + {A_2} + \cdots + {A_a}}}. $

假设协同检测的网络节点均投了支持票，即D=(1, 1, …, 1)^T，则

$ S = {A_1} + {A_2} + \cdots + {A_a}. $

节点M的置信值为

$ {A_M} = \frac{S}{{{A_1} + {A_2} + \cdots + {A_a}}} = 1. $

类似地：

当A_M>0.5时，说明半数以上的网络节点判定节点M是正常节点，则判定节点M是正常节点；

当A_M < 0.5时，说明半数以上的网络节点判定节点M是可疑节点，则判定节点M是恶意节点；

当A_M=0.5时，则等待下一次投票。这样的判定结果满足少数服从多数的原则。

在CCM模块中，所有节点的置信值初始化为1。设参与检测的节点数为a，则改进的K/N投票算法描述如图 5所示。

4 仿真实验与结果 4.1 模型实现

本文在Bro实例上通过功能添加实现MNDMB模型。技术实现具体过程如下：

1) 编译BATMAN v.2011.1.0路由协议，加载到Bro IDS内核；

2) 在Libpcap捕获函数层添加OGM捕获接口batadv_neigh_node:if_incoming；

3) 在第2层事件引擎层里面设置OGM字段端口号；

4) 在第3层策略脚本解释器设置滑动窗口，根据虚假OGM检测算法及丢包检测算法生成规则，写入事件规则库；

5) 用OGM解析模块的输出数据建立虚假OGM率数据集和丢包率数据集，将数据集作为非线性回归模型的输入，拟合结果作为阈值Th；

6) 用SND模块的输出作为CCM模块的输入，CCM模块的输出作为恶意节点的判定结果。

4.2 仿真环境和实验过程 4.2.1 仿真环境配置

使用网络模拟平台NS2(NS2.35) 实现对WMN的模拟仿真。NS2平台配置过程如下：

1) 生成一个1 000 m×1 000 m的模拟空间，设置追踪文件用来记录数据包传送过程；

2) 生成50个网络节点，设置节点链路长度和传输质量；

3) 设定节点之间的队列长度为30个封包大小；

4) 将协议数据包BATMAN v.2011.1.0添加到NS_home/opt/packet.h的packet_t中；

5) 建立链路连接，设置流生成器cbrgen生成数据流场景；

6) 设定网络仿真的起始和终止时间；

7) 在NS2运行的Linux环境下安装添加了自定义功能的Bro IDS，并通过管道和NS2通信，实验的其他仿真参数如表 1所示。

4.2.2 实验过程

为了模拟WMN网络拓扑变化较快的特点，设置节点以恒定速度向随机的位置移动，到达该位置后静止一段时间，再随机选定一个位置继续移动。NS2平台网络布局如图 6所示。

设置恶意节点数量分别为5、10、15、20、25、30，源节点每10 ms产生1个52 B的OGM消息并广播发送，网络模拟时间为1 000 s，在NS2启动模拟仿真实例后，通过Matlab读取实验数据和结果并记录，然后对数据记录进行检测计算和识别分析。

4.3 实验结果和对比分析 4.3.1 不同采样时间下的MNDMB性能

在MNDMB模型的实现过程中，需要考虑节点捕获OGM消息进行解析的采样周期T。本文将一定时间周期内的OGM采样数据作为输入数据进行分析，因此T的不同可能会对恶意节点识别的效果造成影响。为了选择最佳的采样周期，设定T为100、200、300和400 ms分别进行20次实验。不同采样周期的检测结果如图 7所示。

由图 7可见，在MNDMB模型对恶意节点的识别过程中，当T=400 ms时，恶意节点检测率处在最高水平，但误报率也是最高。当T=100 ms时，恶意节点的误报率最低且检测率也是最低。这是因为采样时间越长，拟合精度越高。对于单一节点来说，恶意行为的识别效果越好，但也有更多临界行为(当丢包率等参数接近检测阈值时)被误判为恶意行为，造成误报率升高。当T=200 ms和T=300 ms时检测率较高且误报率较低，但T=300 ms时的误报率远高于T=200 ms时的误报率，因此当T=200 ms时，MNDMB模型对恶意节点的识别率最高。

4.3.2 模型性能比较

选择T=200 ms的MNDMB模型，通过增加WMN恶意节点数量对网络特征聚类方法^[5](network performance characteristic sequence based-clustering detection method, NPCS-CDM)、可靠自私节点检测^[6](reliable selfish node detection, RSND)方法和MNDMB的恶意节点检测性能进行对比评估。在相同仿真环境下分别加载上述3种模型进行检测实验。以恶意节点检测率和误报率作为评价标准的实验结果如图 8所示。

从图 8a可见，随着恶意节点比例的上升，MNDMB能维持较高的恶意节点检测率，与NPCS-CDM、RSND方法相比，检测率提高了11%以上，主要原因是MNDMB的一致性投票机制发挥了作用，由于网络内所有相邻节点均参与对可疑节点的判定，使得对恶意节点的检测率得到了提高。

图 8b展示了当网络中存在5~30个恶意节点时，MNDMB、NPCS-CDM、RSND方法的误报率。从图 8b可见，随着恶意节点数的增加，MNDMB仍保持较低的误报率，说明该方法受恶意节点数量的影响不大，主要原因是MNDMB中的非线性回归模型能够根据网络环境变化实时调整检测阈值，使得检测过程中恶意节点的误报率降低。

5 结论

本文提出了基于BATMAN路由协议的恶意节点检测模型，通过分析节点行为和采用一致性投票机制识别网络中的恶意节点。通过仿真实验证明了MNDMB的有效性，与NPCS-CDM、RSND方法相比具有更高的恶意节点检测效率。下一步将在目前的MNDMB基础上，研究泛洪攻击的恶意节点检测方法。