改进的马尔科夫模型的异常节点检测算法

黄小龙，蔡 艳，屈迟文+

(1.百色学院 信息工程学院，广西 百色 533000；2.澳门科技大学 信息学院，澳门 999078)

0 引 言

由于移动自组织网络[1]中的各个移动节点都可以随时进出网络，导致移动自组织网络的拓扑结构变化很大。在数据通信过程中，路由需要根据网络拓扑结构的变化而变化。在通信过程中，由于各个移动节点在接收和转发数据包的过程中一直在消耗能量，如果某一移动节点经常被用作中继节点，那么该节点的能量消耗很快，当该节点的能量低于一定值之后，该节点就不具备数据转发的能力，此时该节点就成了异常节点。另外，移动自组织网络中还可能存在入侵的恶意节点，这些节点不仅可以监听移动自组织网络中的通信内容，给传输数据的安全性带来严重威胁；而且恶意节点经常丢弃需要转发的数据包，给数据的可靠传输也带来了很大破坏[2-5]。因此，对于移动自组织网络中的这两类异常节点，需要在构建通信路由时将其隔离，避免其对网络通信的破坏。

现有移动自组织网络的路由协议主要分为两类：一类是表驱动路由协议[6,7]，如DSR路由协议。另一类是按需路由协议[8-11]，如AODV(ad hoc on-demand distance vector routing)路由协议。目前流行的许多路由协议都是在这些路由协议的基础上进行改进而成的。为了在构建路由时检测和隔离异常节点，目前也出现了许多改进的路由协议。如文献[8]针对经典的AODV路由协议进行改进，增加了用数字签名技术，通过对节点的报文进行签名和鉴别来验证节点是否异常，这样可以大幅提高数据传输的安全性，预防恶意节点的攻击；文献[9]也是针对经典的AODV路由协议进行改进，策略是引入公共密钥加密体系，对IP地址进行鉴别，保护路由的安全性，抵御恶意节点的攻击。此类策略尽管对于预防恶意节点攻击具有一定效果，但对于自身出现故障问题的异常节点没有防范措施，因此这类异常节点仍会对移动自组织网络的数据传输性能造成很大影响。

为了进一步解决异常节点引起的移动自组织网络路由性能下降问题，本文提出了一种基于马尔科夫模型的异常节点检测策略。设计思想是将移动自组织网络中各个移动节点的状态转换过程看作一个马尔科夫过程，采用马尔科夫模型预测节点状态，检测节点的异常状态。在此基础上，采用该策略改进AODV路由协议，及时发现并隔离路由中的异常节点，可以有效提高移动自组织网络路由性能，增强数据通信的稳定性。

1 本文策略

本文提出一种基于马尔科夫预测模型的异常节点检测策略，将移动自组织网络中节点的状态转换看作一个马尔科夫过程，采用马尔科夫模型为每一个节点计算一个马尔科夫预测因子，依据马尔科夫预测因子来判断节点是否异常。在经典的AODV路由协议中，应用本文的异常节点检测策略，可以及时发现异常节点，并对异常节点进行隔离，增强路由的稳定性。

本文策略主要包括4个阶段：节点参数提取、行为概率估计、马尔科夫预测因子计算和异常节点检测。详细实现方法描述如下。

1.1 节点参数提取

本文依据无线设备传输的内在广播机制，通过监听各节点及其邻居节点的数据包转发情况以及节点自身的传感器信息来抽取与某一个节点行为相关的参数，包括：

(1)该节点的通信半径，记为R；

(2)该节点的移动速度，记为V；

(3)该节点转发数据包的数量，记为Mf；

(4)该节点接收数据包的数量，记为Mr；

(5)该节点的剩余能量，记为Er；

(6)该节点的转发能力，记为F。

其中，节点的通信半径R、移动速度V、接收数据包数量Mr和转发数据包数量Mf这4个参数都可以直接获取。节点的剩余能量Er和转发能力F两个参数需要依据获取的信息自行计算。计算方法描述如下。

(1)节点剩余能量计算

移动自组织网络中的节点时刻都在消耗能量，但能量的消耗过程是一个非线性过程，静默时消耗能量很少，接收和转发数据包时消耗能量很大。因此，节点接收和转发数据包的次数越多，消耗的能量越多。当能量低于一定阈值之后，节点就不具备数据包收发的能力，此时的节点也是一种异常节点。因此，在检测异常节点之前需要计算节点的剩余能量。为了便于计算，假设节点在一小很短的时间段内的能量消耗是线性的，这样，可以估算能量的平均消耗为

(1)

记节点的初始能量为E，则当前时刻节点的剩余能量可以表示为

(2)

在本文中，时间段Δt取经验值，为Δt=1s。

(2)节点转发能力计算

移动自组织网络中的数据包通常需要多跳传输，对于每一个节点，通过接收上一跳节点发送的数据并转发给下一跳节点来实现数据包的多跳传输。节点的转发能力也就可以通过其转发和接收数据包的比例来衡量，节点转发数据包的数量越多，说明节点的转发能力越强。本文定义的节点转发能力表示为

(3)

后续将依据上述参数来描述一个移动节点在多播通信过程中可能出现的所有行为。

1.2 行为概率估计

首先，本文将移动自组织网络中的节点分为3类：

(1)正常节点：记为N，指可以正常接收、转发数据包的节点；

(2)可疑节点：记为S，指可以接收、转发数据包的节点，但丢包率较高；

(3)异常节点：记为A，指不能接收、转发数据包的节点。

本文结合异常节点检测的应用需求和节点的状态转移过程，定义了6种行为概率，具体为：

(1)受损概率

表示一个正常节点N转换成一个可疑节点S的概率，记为pNS。

(2)直接失效概率

表示一个正常节点N转换成一个异常节点A的概率，记为pNA。

(3)间接失效概率

2.3 两组治疗前后血清CA125和D-二聚体变化比较 动态检测患者胸水中的CA125和血中的D-二聚体变化情况，结果显示在治疗之前，实验组和对照组胸水中的CA125和血中的D-二聚体的差异均无统计学意义（P＞0.05），但在治疗后实验组胸水中CA125和血中D-二聚体均明显低于对照组，差异均有统计学意义（P＜0.05），见表4。

表示一个可疑节点S转换成一个异常节点A的概率，记为pSA。

(4)受损复原概率

表示一个可疑节点S复原成一个正常节点N的概率，记为pSN。

(5)失效直接复原概率

表示一个异常节点A转换成一个正常节点N的概率，记为pAN。

(6)失效间接复原概率

表示一个异常节点A转换成一个可疑节点S的概率，记为pAS。

行为概率依据前一小节获取的节点参数计算。具体地，受损概率与节点转发数据包数量有关，节点转发的数据包越多，接收的数据包越少，说明该节点受损的概率越大，因此，受损概率可以表示为

(4)

直接失效概率和间接失效概率都与数据包的丢包有关，节点丢弃的数据包越多，失效概率越大。两者的区别在于，节点的剩余能量不同，直接失效的节点本身的节点剩余能量还能满足通信需求，而间接失效的节点自身的剩余能量无法满足通信需求。因此，直接失效概率可以表示为

(5)

间接失效概率可以表示为

(6)

式中：TE为能量阈值，取经验值20 J。

受损复原概率与节点剩余能量、节点通信半径和节点移动速度有关。节点剩余能量越大、通信半径越小、移动速度越慢，复原的概率越大。因此，受损复原概率可以表示为

(7)

失效直接复原概率和失效间接复原概率不仅与节点的剩余能量、通信半径和移动速度有关，而且与节点的转发能力有关，节点转发能力越强，其复原的概率越大。因此，失效直接复原概率可以表示为

(8)

失效间接复原概率可以表示为

(9)

1.3 马尔科夫预测因子计算

本文将移动自组织网络中节点的状态转换看作一个马尔科夫过程，采用马尔科夫模型来描述网络中每一个节点的状态转移过程。如图1所示，在通信过程中，移动节点在正常节点(N)、可疑节点(S)和异常节点(A)这3种状态下转换。

图1 节点状态转移过程

在节点状态转移过程中，依据马尔科夫模型，可以构建5个稳态方程，表示为

(10)

其中

pNSψNN=pSNψSA

(11)

于是，可以得到

(12)

其中

px=(pSA+pNA)

(13)

(14)

据此，本文构建马尔科夫预测因子f，表示为

(15)

1.4 异常节点检测

本文依据马尔科夫预测因子f来检测异常节点，节点的马尔科夫预测因子的值越小，越有可能是异常节点。

给定一个阈值Tf，异常节点的判决规则为

(16)

也即，当f

将本文的异常节点检测策略应用到经典的AODV路由协议中，对于路由中的每一个节点，如果检测到某节点为异常节点，则将其从现有的有效路由中剔除，并通知路由上的其它节点对该异常节点进行隔离，避免该节点对数据通信造成破坏。

2 仿真实验与结果分析

为了验证本文方法的性能，本文采用Network Simulator软件进行仿真，测试本文方法及对比方法的性能指标。下面首先介绍仿真环境及参数，然后对比和分析不同方法的仿真结果。

2.1 仿真环境及参数

本文采用Network Simulator软件模拟一个移动自组织网络，仿真参数见表1。

表1 仿真参数

2.2 不同方法的性能对比

下面将本文的异常节点检测方法与文献[8]和文献[9]所述方法进行对比，测试异常节点比例不同时不同方法的异常节点检出率、报文送达率、端到端平均延时以及网络吞吐量4个指标。

(1)异常节点检出率对比

图2展示了不同方法的异常节点检出率与异常节点比例的关系曲线。从中可以看出，在相同的异常节点比例条件下，本文方法的异常节点检出率都是最高的，这说明本文方法可以有效检测异常节点。

图2 异常节点检出率与异常节点比例的关系曲线

图3 报文送达率与异常节点比例的关系曲线

(2)报文送达率对比

图3展示了不同方法的报文送达率与异常节点比例的关系曲线。由图3可见，异常节点比例越高，3种方法的报文送达率指标越低。这是因此异常节点会影响网络通信的稳定性。但是，与文献[8]和文献[9]所述方法相比，本文方法的报文送达率指标随异常节点比例下降的速率非常缓慢，当异常节点比例超过10%时，本文方法的报文送达率指标明显高于其它两种方法。原因是本文方法的异常节点检出率明显高于其它两种方法。

(3)端到端平均延时对比

图4展示了不同方法的端到端平均延时与异常节点比例的关系曲线。同样地，由于本文方法的异常节点检出率高，因此网络通信时丢包率低，从而端到端平均延时也低于所对比的两种方法。

图4 端到端平均延时与异常节点比例的关系曲线

(4)网络吞吐量对比

图5展示了不同方法的网络吞吐量与异常节点比例的关系曲线。由图5可见，在相同的异常节点比例下，本文方法的网络吞吐量明显大于其它两种方法，这是因为本文方法有效检测出了异常节点，保证了网络通信的稳定性，数据包丢失现象相对较少。

图5 网络吞吐量与异常节点比例的关系曲线

综上所述，本文方法可以有效检测移动自组织网络中的异常节点，提高了数据传输的成功率和效率，进而提高了网络通信的稳定性。

3 结束语

本文提出了一种基于马尔科夫预测模型的异常节点检测策略，目标是提高移动自组织网络在异常节点干扰下的路由性能指标。本文的核心思想是借助马尔科夫模型描述节点的状态转移过程。主要工作包括4个部分：①依据无线设备传输的内在广播机制和各移动节点自身的传感器信息，提取与节点状态相关的参数；②针对节点的正常、可疑和异常3种状态，定义了受损概率、直接失效概率、间接失效概率、受损复原概率、失效直接复原概率和失效间接复原概率共6种行为概率；③采用马尔科夫模型来描述各个节点在正常状态、可疑状态和异常状态3种状态下的转移过程，构建了5个稳态方程，进而为每一个节点提取一个马尔科夫预测因子;④对每一个节点的马尔科夫预测因子进行阈值判断，检测异常节点。仿真结果表明，本文策略的异常节点检出率高。在经典的AODV路由协议中应用本文的异常节点检测策略，可以及时发现和隔离异常节点，提高路由的报文送达率和网络吞吐量，降低路由的端到端平均延时，有效降低异常节点对移动自组织网络数据通信的影响，提高移动自组织网络的路由性能。

参考文献：

[1]Zhang J,Wang X,Tian X,et al.Optimal multicast capacity and delay tradeoffs in MANETs[J].IEEE Transactions on Mobile Computing,2014,13(5):1104-1117.

[2]Chang J,Tsou P,Woungang I,et al.Defending against collaborative attacks by malicious nodes in MANETs:A cooperative bait detection approach[J].IEEE Systems Journal,2015,9(1):65-75.

[3]Wei Z,Tang H,Yu FR,et al.Security enhancements for mobile ad hoc networks(MANETs) with trust management using uncertain reasoning[J].IEEE Transactions on Vehicular Technology,2014,63(9):4647-4658.

[4]Liu W,Yu M.AASR:Authenticated anonymous secure routing for MANETs in adversarial environments[J].IEEE Transactions on Vehicular Technology,2014,63(9):4585-4593.

[5]Aggarwal A,Gandhi S,Chaubey N.Performance analysis of AODV,DSDV and DSR in MANETs[J].International Journal of Distributed & Parallel Systems,2014,2(6):353-365.

[6]LI Xiangli,LI Chaochao.DSR protocol based on small world theory and QoS supported[J].Sensors and Microsystems,2014,33(2):43-46(in Chinese).[李向丽,李超超.基于小世界理论和QoS支持的DSR协议[J].传感器与微系统,2014,33(2):43-46.]

[7]Bhatt UR,Nema N,Upadhyay R.Enhanced DSR:An ef-ficient routing protocol for MANET[C]//International Conference on Issues and Challenges in Intelligent Computing Techniques,2014:215-219.

[8]Zapata MG.Secure ad hoc on-demand distance vector routing[J].Acm Mobile Computing & Communication Review Number,2002,6(3):106-107.

[9]Li H,Singhal M.A secure routing protocol for wireless ad hoc networks[C]//Hawaii International Conference on System Sciences,2006.

[10]Bourke T,Glabbeek RV,Höfner P.A mechanized proof of loop freedom of the (untimed) AODV routing protocol[J].Bastien Bernela,2014,8837(6):47-63.

[11]CAO Jie,ZHANG Hualong.Improved AODV protocol on urban vehicular Ad Hoc[J].Journal of Lanzhou University of Technology,2014,40(1):99-103(in Chinese).[曹洁,张华隆.城市车载Ad Hoc网络下改进的AODV协议[J].兰州理工大学学报,2014,40(1):99-103.]