应用于Ad hoc网络的安全多路径路由方法

摘要

本发明公开了一种应用于Ad hoc网络的安全多路径路由方法，包括：计算节点的邻居节点的攻击因子值；基于所述攻击因子值和基于所述攻击因子的多路径安全路由协议进行节点的多路径路由。因此，本发明实现了在源节点(也称之为第一节点)和目的节点(也称之为第二节点)之间建立安全的多路径数据传输通道，并且能够在可能受到攻击或者发起攻击的节点对网络造成实质性破坏的时候，提前发起路径维护进程，降低网络维护的通信开销。

说明书

技术领域

本发明属于无线通信安全领域，具体地本发明涉及一种将节点、路径以及路径集的受攻击可能性转化为一种称之为攻击因子的安全度量，并将其应用于Ad hoc网络的安全多路径路由方法。

背景技术

目前，移动网络的快速演进和移动通信产品的大量涌现，推动了移动计算机无线接入技术，特别是移动无线自组织(Ad hoc)网络相关技术的发展。Ad hoc网络作为移动计算的一种特殊形式，是由一系列动态主机节点所临时组成的自治多跳无线网络，它可以不依赖于预先架设好的网络基础设施而独立存在。Ad hoc网络中的所有节点地位平等，可以在网络中自由移动，并且每个节点都同时充当了主机和路由器两种角色。Ad hoc网络的特点在于可以不受地理条件和时间的约束，迅速地建立在那些不适合架设有线网络或架设有线网络的代价过于昂贵的地区，实现随时随地的自由通信。正因为Ad hoc网络自身的诸多优点，使得其可以广泛应用于军事、救灾、科学考察、医疗等多个领域中。Ad hoc网络被认为是下一代移动通信系统解决方案中最有希望被采用的末端网络，是未来移动通信技术的核心组成部分之一。

Ad hoc网络的关键技术之一就是路由协议的设计。目前在Ad hoc网络中所广泛采用的路由协议是AODV、DSR等单路径路由协议。这些单路径路由协议的优势在于它们的简单性，但是这种简单性从根本上限制了协议性能的提升空间。

这是由于，Ad hoc网络中的带宽、节点能量等资源总是相当有限的；同时，在链路上以及在路由器处的拥塞也会在Ad hoc网络中造成较大延迟。如果数据包全部都在同一条路径上发送，当某条链路拥塞或者断开时，通过该链路发送的所有数据就都必须由新的路径发送，既造成了网络的不稳定，重建路径的过程也相当费时。因此单路径路由协议不但不能在负载较轻时充分利用资源，而且当网络发生拥塞或者链路断开时也不能很好地重新选择合适路径。显然，在充分利用网络带宽，以及避免链路和路由器的拥塞方面，单路径路由协议有着先天的缺陷。同时，随着网络性能的提高，单路径路由协议也无法满足路由可靠性和节点节能等方面的更高要求。

最新研究结果显示，在Ad hoc网络中更适合采用多路径路由协议。多路径路由协议是指为任意一对通信节点同时提供多条可用的路径，并允许节点主机自主选择如何使用这些路径。多路径路由的目标通过探测每条路径的状况，如丢包率，来推断网络的拥塞程度，并据此调整对各路径的使用。多路径是作为单个最短路径的替代而被提出用来分散网络流量，减轻拥塞，提高网络的容错能力。换句话来说，多路径路由是用多条好的路径来代替单条最好的路径。多路径路由协议在可靠性、带宽聚合、负载平衡、能量保护等方面比起单路径路由协议都具有明显的优势。

尽管多路径路由协议比起单路径路由协议有诸多优势，但其设计也存在着一些安全隐患，容易导致Ad hoc网络遭受来自于网络内外部的攻击，使得路由协议的效率降低，以下是当前多路径路由协议的设计中存在的主要问题：

1)在路径选择中忽视了对于安全性的考察。源节点或者目的节点在已经建立的多条路径中进行选择的时候，往往仅以路径经过的跳数最少或者路径建立所需的时延最小作为路径的选择依据，而并没有考虑到，对于Ad hoc网络这样比较脆弱的网络，更应该保证路径是由可靠节点组成，路径不会因为遭受攻击而频繁断链，因为断链之后的恢复过程既增加了时延，也带来大量的网络通信开销；

2)对节点安全性的度量没有形成量化。通常判断节点是否安全，是根据在该节点上是否有一些正在遭受攻击的现象发生，或者该节点是否具有某些恶意节点的特征。但是目前并没有一个准确的度量依据来衡量不同节点之间的安全性差异，这导致一些节点其他方面正常，仅仅可能因为网络拥塞的原因转发包失败就被当作了不安全节点。因此，需要建立一个对节点安全性的全面、准确的量化度量机制，反映不同节点的安全性差异，实现差异化管理；

3)对节点安全性的考察缺乏预见性。当前安全路由协议中，对于节点的安全性考察是在节点已经受到攻击或者已经转变为恶意节点之后才做出的，等到发现安全性较差的节点才将其排除出网络的时候，该节点已经对正常的网络运行造成了实质性破坏，这样网络只能通过事后大量的通信开销才能恢复过来。因此有必要能够预先探测出安全性可能会降低的节点，在它们对网络造成实质性破坏之前将它们从网络中隔离出去；

4)对安全性的考察仅限于节点层面。在多路径路由协议中，源节点和目的节点通常需要维护的是整条路径，而不是路径上的某一个节点。源节点或者目的节点选路的时候不仅要确保路径上某一个节点是安全，还要确保整条路径是安全的，因此需要将对单节点的安全性衡量推广到对路径的安全性衡量，对于多路径路由协议，由于最终成为数据通道的通常是一个路径集，因此还要进一步将对路径的安全性衡量推广到对路径集的安全性衡量。

发明内容

本发明的目的是为了解决现有技术中多路径路由协议设计中在安全性方面存在的诸多不足，提出了一种基于攻击因子的应用于Ad hoc网络的安全多路径路由方法，其中将节点当前以及未来遭受攻击或者发起攻击的可能性转换为一个安全度量，称为攻击因子(Attacking Factor)，简称为AF。为了达到上述目的，本发明提供了一种应用于Ad hoc网络的安全多路径路由方法。该方法包括：

计算节点的邻居节点的攻击因子值；

基于所述攻击因子值和基于所述攻击因子的多路径安全路由协议进行节点的安全多路径路由。

进一步地，所述计算节点的邻居节点的攻击因子值为：从一跳范围内的邻居节点处收集运行状况信息；根据所述运行状况信息计算出攻击因子值并保存。

进一步地，所述运行状况信息包括节点的吞吐量、收发包比例、响应时间、节点的利用率、周边稠密度和任务队列，所述计算出攻击因子值为根据AIF＝η₁*P_T+η₂*P_IO+η₃*P_R计算攻击影响因子(AIF)，其中P_T为节点的吞吐量、P_IO为收发包比例、P_R为响应时间，η₁+η₂+η₃＝1，η₁、η₂和η₃为P_T、P_IO、P_R在攻击影响因子AIF所占的比重系数；再根据ATF＝τ₁*P_U+τ₂*P_N+τ₃*P_Q计算攻击诱惑因子(ATF)，其中P_U为节点的利用率、P_N为周边稠密度和P_Q为任务队列，τ₁+τ₂+τ₃＝1，τ₁，τ₂和τ₃为P_U、P_N、P_Q在攻击诱惑因子ATF中所占的比重系数，最后根据AF＝α*AIF+β*ATF计算攻击因子(AF)，其中AIF为攻击影响因子，ATF为攻击诱惑因子和AF为节点攻击因子，以及α+β＝1，α，β分别代表AF对于AIF以及ATF的置信度。

进一步地，所述基于攻击因子的多路径安全路由协议具体为，在单路径安全路由协议(SAODV)的路由消息上增加路由节点列表字段、排除节点列表字段、下一跳节点列表字段、攻击因子列表字段和攻击因子哈希值字段。

进一步地，所述进行节点的安全多路径路由为：

第一节点发起包括路由节点列表、排除节点列表、下一跳节点列表、攻击因子列表和攻击因子哈希值字段的路由请求消息；

中间节点接收所述路由请求消息并检查所述路由请求消息的有效性，经检查有效后缓存所述路由请求消息的摘要；

中间节点更新所述路由请求消息的字段并转发；

第二节点从所述攻击因子列表字段中提取出路径上所有中间节点的攻击因子值；

根据$\left(\begin{array}{c}{H_{\mathrm{AF}}}^{\prime }=\mathrm{hash}(K_{\mathrm{sd}},{\mathrm{AF}}_A)\\ {H_{\mathrm{AF}}}^{\prime }=\mathrm{hash}({H_{\mathrm{AF}}}^{\prime },{\mathrm{AF}}_B)\\ ...\\ {H_{\mathrm{AF}}}^{\prime }=\mathrm{hash}({H_{\mathrm{AF}}}^{\prime },{\mathrm{AF}}_D)\end{array}\right)$递归计算出攻击因子哈希值，并和所述路由请求消息中携带的攻击因子哈希值比较，如果相等，证明攻击因子列表在传输的过程没有被篡改。如果不相等，则所述路由请求消息被丢弃；

第二节点从中间节点转发过来的多条路由请求消息的路由列表字段中提取出多条有效路径，构造出节点不相交的路径集；

第二节点生成并发送携带有构造的路径集的信息的路由回复消息。

进一步地，所述中间节点接收所述路由请求消息检查所述路由请求消息的有效性，经检查有效后缓存所述路由请求消息的摘要为：

步骤10，检查所述路由请求消息的上一跳节点的攻击因子值是否超过了危险阈值，如果超过则丢弃路由请求消息；否则执行步骤20；

步骤20，计算所述路由请求消息的摘要，同保存在缓存的摘要比较，如果有相同的则丢弃路由请求消息；否则执行步骤30；

步骤30，检查自己是否在路由请求消息的下一跳字段中，如果不在，丢弃该路由请求消息；否则执行步骤40；

步骤40，检查路由请求消息的路由节点列表字段、排除节点列表字段、下一跳字段中是否存在重复的节点ID，如果存在，丢弃该路由请求消息，否则通过有效性检查。

进一步地，所述中间节点进行更新所述路由请求消息的字段并转发为：

挑选攻击因子值低于危险阈值的邻居节点加入合格邻居集；

中间节点将自己的ID附到路由节点列表字段末尾，将下一跳字段中除自己以外的节点ID附到排除节点列表字段的末尾；用合格邻居集中的节点ID替代下一跳字段，并删去其中和更新后的路由节点列表字段、下一跳字段中重复的节点ID；将更新后的下一跳字段中的一个邻居节点的攻击因子值附在攻击因子列表字段的末尾；

根据所述攻击因子哈希值字段及式H_{AF_new}＝hash(H_{AF_old}，AF_N)计算转发到不同邻居节点的更新后的所述路由请求消息中的新的攻击因子哈希值字段；其中AF_N是新加入到攻击因子列表字段中的邻居节点的攻击因子值，H_{AF_old}是路由请求消息更新前的攻击因子哈希值字段，H_{AF_new}是路由请求消息更新后的攻击因子哈希值字段。

进一步地，所述第二节点生成并发送携带有路径集信息的路由回复消息后还包括：

中间节点处理所述路由回复消息发送给第一节点；

第一节点确定中间节点的最终攻击因子值，计算路径及路径集的攻击因子，构造符合自身安全需求的合格路径集集合，从合格路径集集合选择最终的数据传输通道。

进一步地，所述中间节点处理所述路由回复消息为：

步骤1，检查上一跳节点的攻击因子值是否超过了危险阈值，如果超过，则执行步骤2；否则执行丢弃所述路由回复消息；

步骤2，检查所述中间节是否在所述路由回复消息的路由列表字段中，如果不在，则执行丢弃该RREP消息；否则执行步骤3；

步骤3，检查所述路由回复消息的路由列表字段中上一跳和下一跳节点是否属于所述中间节点的邻居节点，如果不是，则丢弃该RREP消息；否则执行步骤4；

步骤4，将路由列表字段中下一跳节点最新的攻击因子值附在攻击因子列表字段中相应节点的原攻击因子值的后面，并计算相应的攻击因子哈希值字段。

因此，本发明实现了在源节点(也称之为第一节点)和目的节点(也称之为第二节点)之间建立安全的多路径数据传输通道，并且能够在可能收到攻击或者发起攻击的节点对网络造成实质性破坏的时候，提前发起路径维护进程，降低网络维护的通信开销。

附图说明

图1是本发明基于攻击因子的多路径安全路由协议的消息字段示意图；

图2为本发明中基于所述攻击因子值进行节点的安全多路径路由的具体流程图；

图3为本发明步骤202检查RREQ消息有效性，通过检查后才缓存该RREQ消息摘要；步骤203更新RREQ消息相关字段的流程图；

图4为本发明中间节点收到RREP消息后执行的流程图；

图5为本发明源节点路由选择的流程图；

图6本发明引入的滑动窗口机制的示意图。

具体实施方式

本发明通过提供计算节点的邻居节点的攻击因子值；并基于所述攻击因子值，提供了一种应用于Ad hoc网络的安全多路径路由方法。

本发明中主要提出了将节点当前以及未来遭受攻击或者发起攻击的可能性转换为一个安全度量，称为攻击因子(Attacking Factor)，简称为AF。攻击因子具有如下特点：

1)攻击因子给予了不同节点间安全性相互比较的一个量化的参考依据；

2)节点的攻击因子不仅反映了节点当前遭受攻击或者发起攻击的可能性，也反映了节点未来遭受攻击或者发起攻击的可能性，这使得对于节点的安全性度量具有了预见性，可以帮助提前进行路径的维护操作，减少了路径断链之后才发起路径维护带来的通信开销；

3)确定了节点的攻击因子后，将其进一步推广到节点所在路径的攻击因子以及该路径所在的路径集的攻击因子，可以衡量一条路径以及一个路径集的安全性，这样对于安全性的考察就不仅限于节点层面，不仅更加全面，也更加符合路由协议选路的要求；

4)当路径以及路径集的攻击因子确定后，多路径路由协议的选路依据更多地向安全性侧重，源节点和目的节点可以根据自身的安全需求灵活选择路径作为数据传输通道，而不是局限在传统的基于路径建立时延的这类选路原则上。

所述计算节点的邻居节点的攻击因子值为：从一跳范围内的邻居节点处收集运行状况信息；根据所述运行状况信息计算出攻击因子值并保存。所述运行状况信息包括节点的吞吐量、收发包比例、响应时间、节点的利用率、周边稠密度和任务队列，为计算出所述攻击因子AF，首先根据AIF＝η₁*P_T+η₂*P_IO+η₃*P_R计算攻击影响因子AIF，其中P_T为节点的吞吐量、P_IO为收发包比例、P_R为响应时间，η₁+η₂+η₃＝1，η₁、η₂和η₃为P_T、P_IO、P_R在攻击影响因子AIF所占的比重系数；再根据ATF＝τ₁*P_U+τ₂*P_N+τ₃*P_Q计算攻击诱惑因子ATF，其中P_U为节点的利用率、P_N为周边稠密度和P_Q为任务队列，τ₁+τ₂+τ₃＝1，τ₁，τ₂和τ₃为P_U、P_N、P_Q在攻击诱惑因子ATF中所占比重系数，最后根据AF＝α*AIF+β*ATF计算攻击因子AF，其中AIF为攻击影响因子，ATF为攻击诱惑因子和AF为节点攻击因子，以及α+β＝1，α，β分别代表AF对于AIF以及ATF的置信度。

下面详细介绍攻击因子值的计算：

(1)攻击影响因子AIF

当节点如果受到了攻击，其性能变化主要表现在以下几个方面：

1)节点的吞吐量

节点的吞吐量指在不丢包的情况下，单位时间内节点能够接收处理的包的最大数量，用N_T表示。节点的吞吐量下降，意味着节点的处理能力下降，可能受到了拒绝服务类(DoS)攻击，或者节点为了节省自身能量，有意地减少了收包的数量；

2)节点的收发包比例

节点的收发包比例指在单位时间内，节点发出的包和收到的包的数目的比例，用R_IO表示。如果节点的收发包比例过低，意味着节点有大量的请求不能及时处理，即节点的处理能力下降，可能受到了拒绝服务类(DoS)攻击，也可能是节点已经转变为恶意节点，故意将一部分包丢弃，发起了黑洞类攻击；

3)节点的响应时间

节点的响应时间指节点在收到了来自于邻居节点运行状况信息查询请求，即Hello消息后给予回应的时间，用T_R表示。节点的响应时间过长甚至不响应，意味着节点可能已经被攻击者所控制，不能再参与到正常的路由进程中去了。

需要指出的是，以上3种性能的下降，并不一定代表节点当前受到了攻击或者是已经转变为恶意节点，比如节点响应时间过长，也可能是由于网络拥塞造成的，或者是节点的能量不足所致，因此是有着一定的错判概率的，这也是传统的判定节点是否安全的方法中所普遍存在的问题。所以，本发明定义一个当前受攻击概率参数，这个当前受攻击概率参数代表了如果节点出现了其中一种性能的下降，可以将其判定为正在受到攻击，是不安全节点的概率。上述3种性能分别对应的当前受攻击概率参数如下：P_T是节点的吞吐量下降所代表的节点当前受攻击概率参数；P_IO是节点的收发包比例下降所代表的节点当前受攻击概率参数；P_R是节点的响应时间上升所代表的节点当前受攻击概率参数。

攻击影响因子AIF是节点正在受到攻击或者发起攻击的可能性，以上3种性能的下降都会增加这种可能性，但是在不同的实际应用环境中，3种性能的下降对应的当前受攻击概率参数在决定攻击影响因子AIF时所占的比重是不一样的。例如：在对节点的响应时间要求较高的场合，概率参数P_R所占的比重就会高于其他两种概率参数。因此本发明中还定义了3种当前受攻击概率参数在AIF中所占的比重系数η₁、η₂和η₃。

最终的攻击影响因子AIF的表达式如下：

AIF＝η₁*P_T+η₂*P_IO+η₃*P_R                              式(1)

其中η₁+η₂+η₃＝1

(2)攻击诱惑因子ATF

攻击者通常都是在网络中到处搜寻可能造成网络破坏最大化的攻击目标。尽管Ad hoc网络是一个无中心全分布式的网络，但是仍可能有一些节点因为自身性能的突出或者多次参与到路由进程中，成为了网络运作的热点，对这样的节点进行攻击，对网络造成的破坏程度比对一般节点要大。般来说，在以下特征上表现突出的节点，未来极有可能成为恶意攻击的目标：

1)节点的利用率

节点利用率指单位时间内节点参与到路由进程中的次数，用R_U表示，节点的利用率越高，意味着节点频繁参与到路由及数据转发等网络活动中，拥有丰富的路由信息资源；

2)节点的周边稠密度

节点的周边稠密度指节点一跳范围内的邻居节点数目，用N_N表示。节点的周边稠密度越高，意味着节点和邻居节点的交互也会十分频繁；

3)节点的任务队列

节点的任务队列指节点正有待处理的消息数量，用N_Q表示。节点的任务队列越长，意味着节点是所在区域中的一个关键节点，正在负责处理来自邻居节点的大量请求。

R_U、N_N及N_Q越高，代表节点的网络活动频繁，这样的热点在未来受到攻击的可能性也最大。同当前受攻击概率参数一样，本发明中也定义了未来受攻击概率参数，代表了节点以上3种性能特征上比较出众的话，可以判定其未来可能收到攻击，成为不安全节点的概率。以上3种特征对应的未来受攻击概率参数如下：P_U是节点的利用率高所代表的未来受攻击概率参数，P_N是节点的周边稠密度大所代表的未来受攻击概率参数，P_Q是节点的任务队列长所代表的未来受攻击概率参数。

攻击诱惑因子ATF是节点未来受到攻击的可能性，以上3种特征的表现突出都会增加这种可能性。同攻击影响因子AIF一样，在不同的实际应用环境中，3种特征的表现突出对应的未来受攻击概率参数在决定攻击诱惑因子ATF时所占的比重也是不一样的。因此本发明中还定义了3种未来受攻击概率参数在ATF中所占的比重系数τ₁，τ₂和τ₃。

最终的攻击诱惑因子ATF的表达式如下：

ATF＝τ₁*P_U+τ₂*P_N+τ₃*P_Q                               式(2)

其中τ₁+τ₂+τ₃＝1

(3)攻击因子AF

在取得攻击影响因子AIF和攻击诱惑因子ATF后，可以得到节点最终的攻击因子AF。

AF＝α*AIF+β*ATF                                       式(3)

其中α+β＝1，α，β分别代表AF对于AIF以及ATF的置信度。

实际应用环境中可能会有不止以上3种节点性能的下降以及3种特征的突出影响到攻击影响因子AIF以及攻击诱惑因子ATF的确定，是可以灵活地调整上述确定依据的，只要保证所有确定依据所对应的概率参数和为1即可，这也是本发明的特点之一。

本发明在Ad hoc网络的单路径安全路由协议(SAODV)的路由消息基础上增加了基于攻击因子的多路径消息扩展字段，使得其可以应用于建立安全的路径集中，即构成了多路径攻击因子安全路由协议。如图1所示多路径攻击因子安全路由协议，新加消息字段为在图中显示的路由节点列表(RouteList)，排除节点列表(ExcludeList)，下一跳(NextHop)节点列表，攻击因子列表(AFList)以及攻击因子哈希值(AF Hash)共5个字段，其余字段为现有单路径安全路由协议(SAODV)中的字段，在此不再赘述。这5个字段会随着路由消息在网络中的传输发生改变。网络中每个节点都有一个唯一的标识符ID。

a)RouteList：动态记录了路径经过的节点ID；

b)ExcludeList：动态记录了被排除在路由进程之外的节点ID；

c)NextHop：动态记录了接收路由消息的下一跳节点ID；

d)AFList：动态记录了经过的中间节点的攻击因子AF值，是源节点及目的节点进行攻击因子相关计算的主要来源；

e)AF Hash：动态记录了对AFList字段进行哈希计算的结果，用于给源节点及目的节点验证AFList是否在路由消息传输的过程遭到篡改。

在本发明中，路由请求消息(RREQ)以及路由回复消息(RREP)都将使用以上的消息格式。

如图2所示为本发明一应用于Ad hoc网络的安全多路径路由方法的流程图，其中根据多路径攻击因子安全路由协议基于所述攻击因子值进行节点的多路径路由具体过程为：

步骤201，第一节点发起包括路由节点列表、排除节点列表、下一跳节点列表、攻击因子列表和攻击因子哈希值等字段的路由请求消息；具体为：源节点在生成路由请求消息后，不同于传统的Ad hoc路由协议向邻居节点广播路由请求消息RREQ，在本发明中源节点及后来的中间节点只是选择其中攻击因子AF值低于AF_d的邻居节点向其发送RREQ。

在源节点发出的RREQ中，5个新增消息字段的取值如下：

a)RouteList只记录了源节点ID；

b)ExcludeList为空；

c)NextHop记录了源节点的所有邻居节点中攻击因子AF值低于AF_d的节点ID；

d)AFList记录了NextHop字段中一个邻居节点的攻击因子AF值，发往不同邻居节点的RREQ中的AFList字段中记录着对应节点的AF值；

e)AF Hash记录了对AFList字段进行哈希计算的结果H_AF，如式(4)所示

H_AF＝hash(K_sd，AF_N)                                      式(4)

其中AF_N是从AFList中选定的一个邻居节点的AF值，K_sd是源节点和目的节点间的共享密钥，hash(*)是哈希函数。

步骤202，中间节点接收所述路由请求消息检查所述路由请求消息的有效性，经检查有效后缓存所述路由请求消息的摘要；

步骤203，中间节点更新所述路由请求消息的字段并转发；

步骤204，第二节点从攻击因子值列表中提取出路径上所有中间节点的攻击因子值；

步骤205，根据$\left(\begin{array}{c}{H_{\mathrm{AF}}}^{\prime }=\mathrm{hash}(K_{\mathrm{sd}},{\mathrm{AF}}_A)\\ {H_{\mathrm{AF}}}^{\prime }=\mathrm{hash}({H_{\mathrm{AF}}}^{\prime },{\mathrm{AF}}_B)\\ ...\\ {H_{\mathrm{AF}}}^{\prime }=\mathrm{hash}({H_{\mathrm{AF}}}^{\prime },{\mathrm{AF}}_D)\end{array}\right)$递归计算出攻击因子哈希值，并和所述路由请求消息中携带的攻击因子哈希值比较，如果相等，证明攻击因子值列表在传输的过程没有被篡改继续执行步骤206，如果不相等，则执行步骤200：所述路由请求消息被丢弃；

步骤206，第二节点从中间节点发送的路由列表提取出各自的有效路径，构造出节点不相交的路径集；在一个设定的时间内，目的节点收到的m条真实有效的RREQ消息RREQ₁，...，RREQ_m，并提取出各自的RouteList字段RouteList₁，...，RouteList_m，即m条有效路径。目的节点从这m条路径中构造出节点不相交的路径集。节点不相交的路径集即各路径上的中间节点ID没有重复的。最终得到的节点不相交路径集可能不止一个。设满足节点不相交条件的有k条路径，则节点不相交多路径集可以表示为

如果构造出多个路径集，这些路径集可以表示为一个路径集的集合{DisjointSet1，DisjointSet2，DisjointSet3，...}。

步骤207，第二节点生成并发送携带有构造的路径集的信息的路由回复消息。

其中，中间节点收到RREQ消息后执行以下两部分算法，第一部分步骤202检查RREQ消息有效性，通过检查后才缓存该RREQ消息摘要；第二部分步骤203更新RREQ消息相关字段并转发。

如图3所示，步骤202算法第一部分的步骤如下：

步骤301，检查向自己发送RREQ消息的上一跳节点的AF值是否超过了AF_d，如果超过，则执行步骤300：丢弃该RREQ消息；如否，则执行步骤302；

步骤302，计算该RREQ的摘要，同保存在缓存的摘要比较，如果有相同的则执行步骤300丢弃该RREQ消息；否则执行步骤303；

步骤303，检查自己是否在RREQ消息的NextHop字段中，如果不在，则执行步骤300，丢弃该RREQ消息；否则执行步骤304；

步骤304，检查RREQ消息的RouteList、ExcludeList和NextHop三个字段中是否存在重复的节点ID，如果存在，则执行步骤300，丢弃该RREQ消息；否则步骤305通过有效性检查。

以上4步完成了对于RREQ消息的有效性检查，检查通过之后就可以将该条RREQ消息保存到节点的缓存之中，如图3所示，再继续进行第二部分算法。

步骤306，挑选AF值低于AF_d的邻居节点加入合格邻居集；

步骤307，更新原RREQ消息中5个新增字段，具体为：

将自己的ID附到原RouteList字段末尾；

将原NextHop字段中除自己以外的节点ID附到原ExcludeList字段的末尾；

用合格邻居集中的节点ID替代原NextHop字段，并删去其中和新的RouteList、NextHop两个字段重复的节点ID；

将新的NextHop字段其中一个邻居节点的AF值附在原AFList字段的末尾，因此发往不同邻居节点的RREQ消息的AFList字段也相应有所不同；

根据原AF Hash字段及式(5)计算转发到不同邻居节点的RREQ消息中的新的AF Hash字段；

H_{AF_new}＝hash(H_{AF_old}，AF_N)                              式(5)

其中AF_N是新加入到攻击因子列表字段中的邻居节点的攻击因子值，H_{AF_old}是路由请求消息更新前的攻击因子哈希值字段，H_{AF_new}是路由请求消息更新后的攻击因子哈希值字段。

其余中间节点都将执行以上步骤。

在步骤207所述第二节点生成并发送携带有构造的路径集的信息的路由回复消息后还包括：

中间节点处理所述路由回复消息发送给第一节点；

第一节点确定中间节点的最终攻击因子值，计算路径及路径集的攻击因子，构造符合自身安全需求的合格路径集集合，从合格路径集集合选择最终的数据传输通道。

下面介绍上述过程：

1)中间节点处理路由回复消息，中间节点收到RREP消息后执行以下步骤，如图4所示：

步骤401，检查上一跳节点AF值是否超过了AF_d，如果超过，则执行步骤400，丢弃该RREP消息；否则执行步骤402；

步骤402，检查自己是否在RREP消息的RouteList字段中，如果不在，则执行步骤400，丢弃该RREP消息；否则执行步骤403；

步骤403，检查RREP消息中RouteList字段中自己的上一跳和下一跳节点是否属于自己的邻居节点，如果不是，则执行步骤400丢弃该RREP消息；否则执行步骤404；

步骤404，将RouteList字段中下一跳节点最新的AF值附在AFList字段中相应节点的原AF值的后面，并计算相应的AF Hash字段。

2)源节点路由选择

源节点在收到RREP消息后将根据其中携带的路径集信息构造出符合自身安全需求的路径集，即最终的数据传输通道。如图5所示源节点路由选择的流程图，源节点将执行以下步骤：

步骤501，确定中间节点的最终AF值；

如上所述，RREP消息的AF List字段中每个节点都有在路由请求阶段和路由回复阶段中邻居节点给其的AF评价，将路由请求阶段给出AF值记为AF_pre，路由回复阶段给出的AF值记为AF_next。为防止恶意节点在传输过程中蓄意提高其它节点的AF值，源节点根据式(6)决定中间节点的最终AF值。

$\mathrm{AF}=\left(\begin{array}{c}{\mathrm{AF}}_{\mathrm{next}},{\mathrm{AF}}_{\mathrm{next}}\le {\mathrm{AF}}_{\mathrm{pre}}\\ \frac{{\mathrm{AF}}_{\mathrm{next}}+{\mathrm{AF}}_{\mathrm{pre}}}{2},{\mathrm{AF}}_{\mathrm{next}}>{\mathrm{AF}}_{\mathrm{pre}}\end{array}\right)$         式(6)

步骤502，计算路径及路径集的攻击因子；

定义P_route(N)为拥有N个中间节点的路径的攻击因子，P_set(M)为拥有M条路径的路径集的攻击因子。

如果路径表示为Route＝{S，n₁，n₂，…，n_N，D}，则

P_route(N)＝1-(1-AF₁)...(1-AF_N)                        式(7)

在此基础上，如果节点不相交路径集表示为DisjointSet＝{Route₁，…，Route_M}，则

$\mathrm{Pset}\left(M\right)=\underset{i=1}{\overset{M}{\Pi }}{P}_{\mathrm{routei}}\left(N\right)$        式(8)

步骤503，源节点构造符合自身安全需求的合格路径集集合；

设源节点对于多路径集的安全需求为τ_set，即最后作为数据传输通道的路径集的P_set(M)不能超过τ_set。

如果RREP消息携带的路径集集合信息为{DisjointSet₁，DisjointSet₂，DisjointSet₃，...}。选取DisjointSet₁为例，DisjointSet₁＝{Route₁，...，Route_M}。先计算其中各条路径的P_route(N)，不妨设P_route1(N)≤P_route2(N)≤...≤P_route3(N)，再计算DisjiontSet₁的P_set(M)。

源节点比较P_set(M)和τ_set，如果P_set(M)＞τ_set，则从DisjiontSet₁去掉Proute(N)最高的路径Route_M，再计算新的P_set(M)直至该P_set(M)＜τ_set，并将最后得到的DisjiontSet₁加入到合格路径集集合中；

步骤504，从合格路径集集合选择最终的数据传输通道；

源节点从合格路径集集合中选择P_set(M)最小的路径集，作为源目的节点间的数据通道。源节点根据自身要求选择路径集，这样既保证了源节点拥有自主选择路径的能力，同时也保证了即便携带在RREP消息中的路径信息在中途被截取，攻击者也不能以此确定最终数据传输通道。

在路由回复阶段之后，源节点和目的节点间的路由建立正式完成，开始相互发送数据，节点进入了路由维护阶段。

本发明引入了滑动窗口机制对邻居节点进行监控，预测邻居节点的安全性，如图6所示。滑动窗口从低到高保存着一个邻居节点最近一段时间内的AF值，其中头部的AF值最低，尾部的AF值最高。如果最新的AF值低于头部的AF值，则将新的AF值放入滑动窗口头部，并清空后面的窗口；如果新AF值高于尾部AF值，则将新AF值保存到原滑动窗口的尾部，且前面的所有窗口中保存的AF值都向头部方向滑动一个窗口，原先头部所保存的AF值被移出。

一旦邻居节点最新的AF值高于危险阈值(AF_d)，将此时的AF值标记为AF_R，链路进入了警报状态，但还不必发起路由维护进程，因为存在着误报的可能性。如果接下来收到的该节点的AF值仍高于AF_d且呈上升趋势，使得AF_R滑动到了滑动窗口头部的时候，才会发出路由维护RRER消息。这样就在保证了在抢先发起路由维护进程的同时，最大限度地降低了误报的可能。滑动窗口的窗口数目可以根据实际需要进行调整。

本发明通过将节点的安全性量化为攻击因子，使得路由进程中可以避免将数据和消息路由到高攻击因子的节点，即安全性低的节点上，最终形成的路径和路径集都是攻击因子低的节点，使得这些路径和路径集受到攻击而断链的可能性大大降低；攻击因子的确定依据来源于节点的各方面特征，而且可以根据实际应用的需要，对这些确定依据灵活调整，使得它们能够更全面、准确地反映节点当前及未来的安全状况；攻击因子的计算复杂度较低，所有的计算都是线性计算，且节点只需要维护自身周边一跳范围内的节点的攻击因子，因此适合在节点的计算能力及存储空间都有限的Ad hoc网络中使用；通过引入攻击因子，形成了对节点、路径、路径集3个层次的安全性考察，能够更全面地反映网络的安全状况，从而制定相适应的选路策略。

并且本发明通过在仿真工具OPNET下编写代码，对本发明进行仿真实验。仿真实验证明，在采用了该安全多路径路由方法的Ad hoc网络中，即使有相当比例的恶意节点存在，也不会对正常的路由进程产生太大影响，提高了路由建立的效率。

最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围，其均应涵盖在本发明的权利要求范围当中。