无线Mesh网络中基于复权马尔可夫链的安全路由协议

冯媛媛 易 欣 赵 丽

1(四川工程职业技术学院电气信息工程系 四川 德阳 618000)2(山西大学软件学院 山西 太原 030013)

0 引 言

机会路由OR(Opportunistic Routing)[1]算法是一组单播或组播的路由算法，它可以确保无线网络中端到端之间分组路由的可靠性和有效性。与传统的路由方案如DSV、AODV、OLSR等[2]不同，OR算法在路由过程的每一跳中，仅选择一个节点作为下一跳的实际转发器。同时向其传输数据包目的地和相邻节点子集，作为潜在的下一跳转发器。OR算法中的路由操作分为两个阶段：候选点选择和候选点协调。其中，候选点选择方法近年来受到研究者的高度重视。在候选选择过程中使用不同的度量和参数，例如节点之间的通信链路的质量、节点的地理位置以及潜在候选点的可信度等因素。

科研人员对OR中候选节点的选择和协调方法进行了大量研究[3-4]。例如，极端机会路由(ECOR)[5]是一种基于OR算法的路由算法，这种路由使用预期传输计数(ETX)作为候选选择的度量。简单机会自适应路由算法(SOAR)[6]同样使用ETX指标进行候选选择，源节点和目标节点之间的最短路径使用ETX度量来计算，然后通过添加接近最短路径的节点来选择候选集合。最低成本机会路由(LCOR)[7]是另一种OR算法，这种路由使用预期任意路径传输(EAX)度量来选择候选节点，该算法能够通过对网络拓扑图进行分析，进而发现最佳候选集合。与LCOR类似，文献[8]提出一种代表最小传输选择的MTS算法，同样使用EAX度量来进行候选点的选择。与这些只考虑候选节点之间链路质量的算法不同，有一类算法考虑了节点的地理位置：文献[9]提出的DPOR算法通过考虑每个候选点到目的地的距离来选择候选集；在其改进版本DPOR[10]算法中，节点之间的链路传递概率和距离组合用于定义候选选择的度量；文献[11]和DPOR算法类似，也使用链路质量和节点的地理位置来精确地选择其下一跳转发器。另外，还有一些考虑其他因素的算法。例如，文献[12]提出了一种传输延迟有效的OR算法，提高了能量效率；文献[13]在路由数据包传达至目的地的过程中，考虑了服务质量的计算。

目前，大多数研究主要关注可靠性方面，也就是说这些OR算法都遵循一个假设，即网络中的所有节点都是良性的协作节点。然而，在实际情况下，网络中可能会出现恶意节点，对无线网络中的通信性能造成破坏性影响。例如，拒绝服务(DoS)攻击[4]，其中当恶意节点作为其他节点的下一跳转发器时，这些节点倾向于丢弃所有收到的分组，并降低网络性能。

目前，OR算法中恶意节点的影响尚未引起足够的重视。因此，本文使用复权马尔可夫链构建一种基于OR的无线Mesh网络的新模型，用于检测系统中存在的恶意节点，防止其转发数据包。其主要创新点在于：

(1) 采用了一种最新的马尔科夫链技术，即复权马尔可夫链来进行节点预测；

(2) 通过复权马尔可夫链将机会路由中的恶意攻击方式进行建模，通过状态概率的计算来预测恶意节点。

1 路由中的安全问题

除可靠性要求之外，对于安全性的考虑也非常重要。在存在恶意节点的情况下，即使是最可靠的路由算法，在网络中也不能有效的运行。研究表明，采用密码方案是针对恶意节点的一种有效防御机制，它可以保证节点之间数据传输的安全性和完整性。但是，当涉及到逐跳路由中的节点协作时，就可能引入一系列不当行为。例如，一些恶意节点可能会在网络中注入虚假信息，或者阻止节点间的协作。

路由攻击包括黑洞攻击、灰洞攻击和蠕虫攻击。在黑洞攻击(即DoS攻击)中，黑洞节点会传输错误的路由信息，试图说服网络中的其他节点选择它们作为路由中的下一跳节点，从而试图吸收尽可能多的数据包，并将它们丢弃。灰洞攻击是黑洞攻击的一个特殊变体。灰洞攻击中，节点倾向于有选择地丢弃一些接收的数据包并转发其他数据包。在蠕虫攻击中，位于不同地区的两个恶意节点相互串连，攻击网络。一旦恶意节点收到一个数据包，就通过一个私有信道把这个包发送到另一个区域，其他恶意节点将在其他区域重发数据包。

为了防御路由攻击，科研人员提出了不同的方法。例如，为了识别网络中不合作的节点，并相应地将其隔离，提出信任和信誉管理协议。文献[14]和文献[15]提出了利用无线网络中节点之间的直接、间接交互构建一些信任和信誉模型。文献[16]则引入机会网络的信任计算方法，接收方节点通过发送正反馈消息(PFM)来确认机会网络中另一个节点的合作性质。

2 复权马尔可夫链

马尔可夫链[17]可以根据事件在以前某个时段的状态转移概率为基础，预测该事件将来的状态变化概率，它主要包括时间参数集T={0,1,2,…}和状态参数集E={0,1,2,…}。而在实际应用环境中，常用的是齐次马尔可夫链[18]。假设参数u,k∈T，则：

Pij(u;k)∈E

(1)

式中：Pij(u;k)表示在u时刻，一个随机事件的状态i在通过k步状态转移计算后变成状态j的概率，且该事件的状态i发生在u时刻。

齐次马尔可夫链在使用过程中将各种状态转移步长看作是同一个值，并不能得到准确的状态预测结果。而复权马尔可夫链对各个步长区别对待，引入权重的概念，将各个状态的预测概率当作权重值，再根据对应的状态均值，实现数值预测。复权马尔可夫链的具体步骤如下：

(1) 创建对象序列的状态分级标准，根据聚类法、频率曲线法等划分不同的状态，并确立对象序列的所属状态。

(2) 对于指标值序列x1,x2,…,xn，当其状态由i变为状态j时，经历的频数用fij表示，且i,j∈E。然后计算出各个状态的转移规律，从而得出步长的状态转移频数矩阵。

(3) 转移概率Pij(i,j∈E)可以定义为第i行第j列的元素fij与各行总和的比值，如下式所示：

(2)

式中：m表示指标值序列中可能呈现的状态数量，m∈E。

(4) 边际概率P.j可以定义为fij的第j列之和与各行各列的总和的比值，如下式所示：

(3)

统计量X2在序列长度足够大时可表示为：

(4)

(5) 利用式(5)计算步长的自相关系数：

(5)

(6) 根据式(6)将各步长的自相关系数规范化：

(6)

式中：wk表示规范化后的自相关系数，c表示最大步长。

(8) 利用加权算法求和同一状态的不同预测概率，可得该状态的预测概率：

(7)

(8)

3 路由中恶意攻击的马尔可夫链模型

OR方法中的路由操作可以使用复权马尔可夫链进行精确建模，复权马尔可夫链中的每个状态都使用一个元组来定义，该元组包含节点标识符和特定节点中发生的重传次数。文献[19]提出的模型是评估网状网络OR性能的一般模型，但这种模型不适用于包含恶意节点的网络。在很多情况下，由于硬件或软件故障等原因，节点并不能像预期的那样参与路由操作。本文提出了一种修改的OR算法模型，该模型在网络中含有恶意节点的情况下使用复权马尔可夫链。表1为本文所使用的符号和含义。

假设网络中存在M个恶意节点，它们都可能执行对应的不合作行为。其中黑洞节点收到数据包后会将其恶意丢弃，但其却宣称转发成功，并向所有其他候选点发送确认消息，指示它已经转发了分组数据。因此，前一跳和所有其他候选点需要阻止这样的分组转发，防止数据包永久丢失。

构建一个N=5、K=3、M=1和C=2的线性拓扑结构。在这个模型中，假设所有节点之间的距离相等，并且一个节点(ID=2)是唯一的恶意黑洞节点，即恶意节点可以收到所有数据包。为此，这样的节点可以模拟为复权马尔可夫链中的吸收状态。更具体地说，一旦系统达到吸收状态，它将保持在该状态，并不再发生状态之间的转换。如图1所示，由于ID=2的节点会丢弃对象，因此一旦系统达到状态(2,0)，将不能把分组转发到目的地，也不会重传。考虑到这一点，以及M个恶意节点的存在，可以计算系统中的状态数量S：

S=(N-M-1)×(K+1)+M+2

(9)

吸收状态的数量将等于M+2，对应于M个恶意节点，以及一个失败和一个成功状态。此外，所提出的模型中瞬态的数量为(N-M-1)×(K+1)。一旦复权马尔可夫链中的所有状态都是已知的，就有可能创建一个包含状态间转移概率的随机矩阵。使用该矩阵，可以提取所需的网络参数，例如数据包传输率、丢包率等。

图1 存在黑洞节点时的线性拓扑模型

图2 转移概率矩阵

当网络中恶意节点的数量较多，特定节点的所有候选都可能成为恶意节点。在这种情况下，由发送节点发送的所有数据包将被候选节点恶意丢弃，即在复权马尔可夫链中数据包成功到达目标节点的可能性为零，即源节点和目的节点之间不存在路径。

4 基于马尔可夫链模型的丢包率预测

4.1 计算转移概率矩阵

(10)

(2)达到与其他候选对象相对应的状态(除了最高优先级候选节点)：在这种情况下，从状态(i,j)转换到状态(i′,j′)时，i′不是节点i的最高优先级候选。此时状态的转换概率可以用下式表示：

(3) 达到重传或失败相对应的状态：如果在传输过程中没有候选点接收到数据包，发送节点倾向于执行重传，最多发生K次重传。在这之后，如果没有候选点接收到数据包，则从网络中永久丢弃该节点。计算重传或包传输失败的概率用下式表示：

(12)

4.2 丢包率的计算

通过计算每个与恶意节点相关的从初始状态到达吸收状态的概率，然后将它们组合起来得到丢包率。通过丢包率的预测来判别一个节点是否为恶意节点。

显然，OR算法中的初始状态与产生数据包的源节点有关。式(13)显示了OR的初始状态。从初始状态V经过h次转换之后到达任意状态的概率可以使用ph来表示，初始状态表示为：

V=[1 0 … 0]

(13)

本文假设网络中只有一个节点作为源节点，即ID=0节点。这个节点就有必要计算到达与恶意节点相关的每个吸收状态的概率，矩阵V×Ph中的元素(0，BHi)表示恶意节点BHi接收且丢弃数据包的概率。那么，所有恶意节点丢弃的数据包的总体比率如式(14)所示,其中M是恶意节点的数量。由此可以确定达到成功或失败状态的概率，这些值分别代表到达目的地的概率或分组失败的概率。

(14)

5 仿真分析

利用NS 2.35仿真软件构建仿真环境，分别将本文提出的模型与经典的三种OR算法(MTS算法[8]、POR算法[9]和DPOR算法[10])进行比较。其中，MTS使用节点之间的链路传递概率来选择候选，其证明了可以根据期望的传输次数(ETX)选择最佳的候选集合。POR算法则考虑了候选节点的地理位置，为每个节点选择候选集合。DPOR中候选点的选择不仅考虑了它们的位置，还考虑了链接的质量。

在仿真过程中引入了黑洞攻击，一旦恶意节点接收到分组，就会通知所有其他候选点(以及前一跳节点)它已经接收并转发该分组。其他候选点和前一跳节点会假定该分组已经发送，并且让这些节点放弃发送或重发分组。

5.1 仿真设置

本文使用阴影衰落传播模型进行节点之间的无线通信，参数如表2所示。对于单个传输的分组，使用下式计算信号接收到的功率：

(15)

式中：d表示传播距离，Pr(d)表示距离d处的接收功率，用分贝表示，即单位为dBW，Pt表示发射功率，Gt表示发射天线的增益，Gr表示接收天线的增益，λ是信号波长，β是系统损耗，XdB代表均值为零、标准偏差为σdB的高斯随机变量。当发送一个数据包时，如果接收节点的接收功率大于或等于一个阈值，比如RXThresh，节点可以成功接收数据包。因此，可以使用文献[10]中的方式计算在距离d处节点x和y之间的传递概率，如下式所示：

linkprob(x,y)=Probability(Pr(d)≥10log10(RXThresh))

(16)

表3列出了仿真研究中使用的所有参数。为深入研究各种参数的影响，选择三个不同的参数进行实验，包括恶意节点数量、节点密度和最大候选数量。所有参数都设置为默认值，然后每次更改一个参数，计算丢包率、数据包传输率和跳数。

表3 仿真参数

5.2 结果分析

5.2.1恶意节点数量对性能的影响

本节介绍恶意节点数量对网络丢包率和传输率性能的影响，其中恶意节点的数量从0变为15。由以下仿真结果可知，恶意节点会对网络性能参数产生显着的破坏性影响。

(1) 丢包率。图3显示了恶意节点数量对丢包率的影响。丢包率表示为恶意节点丢弃的数据包总数与生成的数据包总数的比例。显然，随着恶意节点数量的增加，丢包率也会随之上升。这是因为当网络中存在更多的恶意节点时，算法中选择这些节点作为候选点的概率增加，因此这些恶意节点有更多机会通过捕获数据分组来攻击网络，并相应地丢弃数据包。

在现有的三种算法中，POR算法有最低的丢包率。POR算法的重点是最小化每个数据包的跳数，这么做降低了恶意节点接收数据包的概率。而在MTS算法中，由于整体传输数据包较少，恶意节点捕获数据包的可能性也较小，其丢包率相应较低。而本文提出的算法中丢包率最低，这是因为本文通过复权马尔可夫链来检测恶意节点，能够有效避开恶意节点转发数据，但是当恶意节点数量较多时，会出现不得不通过其转发数据的情况。

图3 恶意节点数量对丢包率的影响

(2) 传输率。图4显示了恶意节点数量对数据包传输率的影响。传输率是目标节点接收数据包总数与生成的数据包总数的比例。由图4可知，增加恶意节点的数量将导致所有算法的传输率下降，因为恶意节点数量的增加将导致捕获和丢弃的数据包数量增加，这显然会导致传输率较低。

在现有的三种算法中，POR算法的传输率受恶意节点的影响较大，这是因为该算法能够减少在源和目的地之间接收分组的潜在跳数；MTS算法具有较好的传输率性能。本文算法在传输率方面同样获得了最佳的性能。

图4 恶意节点数量对数据包传输率的影响

5.2.2节点密度对性能的影响

本小节研究节点密度变化对网络性能的影响。对于这种评估，网络尺寸将从300×300平方米变为1 000×1 000平方米，而恶意节点的数量都设置为6个节点。

(1) 丢包率。图5显示了网络大小变化对丢包率的影响。通过扩大网络规模，各种算法的丢包率都是上升到一定水平后开始下降。因为对于较小的网络，例如300×300平方米，源与目的地之间的路径更短，分组数据需要较少的跳数就能到达目的地。这降低了恶意节点接收数据包的可能性。相比之下，通过扩大网络大小，在路由数据包传递到目的地的过程中涉及到更多的节点，这为恶意节点捕获更多的数据包提供了更多的机会。但是，当网络规模过大时，比如1 000×1 000平方米，节点之间的平均距离也增大，因此，由于无线信道的阻塞，网络中会有大量的数据包丢失。虽然恶意节点仍然可能被其他节点选为潜在的候选对象，但是只有较少的数据包能够到达目的地。其中，POR算法性能较好，DPOR算法性能最差，本文算法同样获得了最佳性能。

图5 网络大小对丢包率的影响

(2) 传输率。图6显示了网络大小变化对传输率的影响。增加网络规模时，各种算法的传输率都逐渐下降。其原因是恶意节点会捕获和丢弃一些接收到的数据包，并且随着网络规模的扩大，节点之间的距离也越来越大，数据包丢失的可能性也越来越大，因此，更少的数据包将有机会成功传输到目的地。其中，MTS算法的数据传输性能较佳，DPOR算法的数据传输性能最差，POR算法的数据传输性能整体优于DPOR算法，这是由于POR算法将尝试减少源和目的地之间的跳数，这就使得接收到恶意节点的数据包的可能性减小，传输比率提高。本文算法获得了与MTS算法相似的性能。

图6 网络大小对数据包传输率的影响

5.2.3最大候选节点数量对性能的影响

在这种情况下，候选的最大数目从1个节点变为6个节点，其他参数则设置为其默认值。

(1) 丢包率。图7显示了最大候选节点数量对丢包率的影响。当候选点数目超过2个时，DPOR算法的丢包率变化并不明显，而POR算法的丢包率呈现明显上升的趋势，这是因为少数候选点由于传播模型中的分组丢失和能量损失而导致丢失大量分组。事实上，增加候选集中节点的数量会减少数据包丢失的机会，同时增加选择更多恶意候选的可能性。当候选点数量从1变化到3时，MTS算法的丢包率呈现略微下降的趋势，当候选节点数量大于3时，丢包率几乎不变。与DPOR算法相比，MTS算法中恶意节点可以捕获更少的数据包。本文算法中，能够有效识别恶意节点，所以在候选节点数量变化时，丢包率保持在较低的水平。

图7 最大候选节点数量对丢包率的影响

(2) 传输率。图8为最大候选节点数量对数据包传输率的影响。在POR算法中，随着候选数目的增加，分组丢失的概率减小，而算法尝试通过选择离目的地最近的节点来减少跳数。因此，将数据包发送到目的地的可靠性增加，相应的数据包传输率也增加。当候选集的最大数目少于3个节点时，POR算法表现出较差的传输率。DPOR算法将地理信息与节点之间的链路传递概率结合起来，具有较好的传输率。当候选点数量从1变化到3时，POR和DPOR算法的传输率逐渐增加，直到候选点的数量大于3个时，传输率趋于稳定。总的来说，MTS算法在传输率方面的性能较好。由于本文算法受候选节点数量的影响较小，所以传输率也保持在一个较高的水平。

图8 最大候选节点数量对数据包传输率的影响

6 结 语

本文研究了无线网络中恶意节点对机会路由算法的影响，利用复权马尔可夫链设计并实现了一个新的分析模型来演示恶意节点的存在。另外，为了检测恶意节点，引入了一种计算丢包率的方法。在设计了机会路由算法后，将黑洞攻击作为恶意行为的一个例子，设计并实施了一套综合的性能评估方案，对本文算法和三种经典的机会路由算法进行了仿真分析。结果表明，本文提出的模型能够有效检测恶意节点，提高网络性能。