基于信任度的多路径安全路由研究

伍 春，尤晓建，吕 涛

(西南科技大学国防科技学院，四川 绵阳 621000)

0 引言

在国家基础工业以及国防军工领域中大规模车队有联合行驶与执行任务的需求，车队车辆通过无线通信技术组成专用的车载自组织网络(Convoy Ad Hoc Network，CANET)为车队任务提供信息交互服务.CANET与传统智能交通领域的车载自组网(Vehicular Ad Hoc Network，VANET)不同.VANET是为交通网内所有车辆以及路边设备提供通信[1]，传递交通安全、交通路面情况、娱乐以及商业广告等信息，VANET属于大规模Ad Hoc网络，其研究的重点包括车辆控制、车路协同、网络安全等.[2-3]网络中的车辆运动速度不一、路线各异、大量快速相向行驶，使得VANET的拓扑变化很快.而任务车队组成的CANET属中小规模Ad Hoc网络，网络中的车辆一般沿执行任务路线同向行驶，网络拓扑通常变化缓慢.由于其执行国家安全和国防军工任务的重要性，CANET网络信息传输需要的可靠性与安全性要大大高于普通Ad Hoc网络.Ad Hoc网络特征在于动态自组网，其路由安全是整个网络安全的重要方面.目前，国内外在路由安全方面的主要工作集中在针对不同的路由攻击，设计应对策略和方法，并对现有的主要路由协议进行安全改进.[4-6]文献[7]提出针对AODV协议的安全改进协议R-SAODV，使用非对称密钥加密方法应对大多数的路由攻击，同时引入时间戳以克服重放攻击；斯坦福大学的S.Marti等[8]提出邻节点监测机制(watchdog)加异常节点隔离机制(pathrater)来抑制黑洞攻击；文献[9]对OLSR协议进行改进，在TC分组和HELLO分组中使用基于加密的认证和椭圆曲线数字签名方法来提高路由的安全性；文献[10]提出通过备选路径来应对DoS攻击，其信息收集传输安全性由邻居节点间的会话密钥来保证；文献[11]对基于节点信任策略的ZRP路由协议的安全邻居机制进行改进，以检测MANET网络中的攻击；协议Ariadne[12]基于DSR协议构建安全按需路由，对路由发现和维护采用了消息认证码、广播消息认证TESLA、消息散列3 种安全措施.上述各种方法仅能应对一种或几种特定路由攻击，若将多种方法联合执行，则复杂度大大增加，且应对网络内部攻击的能力较弱.本文研究基于节点和路径信任度的多路径安全路由方法，通过优化减枝的广度优先快速搜索找出多条可达路径，进而对节点和路径的信任度进行评估，基于路径信任度和反馈信息动态调整信息传输路径，能有效应对各种内部攻击如黑洞、虫洞、报文丢弃等，并提高网络在高强度攻击下的生存能力.

1 Ad Hoc多路径路由

车载自组网信息的可靠传输需要具有高可靠性和鲁棒性的路由技术的支持.根据路由的建立机制，Ad Hoc网络一般有先验式(Proactive)、反应式(Reactive)、混合式路由方式.先验式路由又称为表驱动路由，节点检测拓扑结构的变化并及时发送更新消息以维护准确的路由信息，该方式路由时延小，但路由协议开销较大，尤其是网络拓扑变化快时，开销更大.反应式路由又称为按需路由，节点不需要维护及时准确的路由信息，当节点发送报文时，源节点才在网络中发起路由查找过程，找到相应的路由，反应式路由开销小但路由建立的延时较大.从满足可靠性和及时性角度考虑，先验式路由更适合在CANET网络中应用.最优链路状态路由(Optimized Link State Routing，OLSR)[13]是IETF制定的一种标准表驱动路由协议，通过传递链路状态来计算可行路由，部分节点广播控制信息的机制有利于减少网络中控制信息的洪泛.本文在OLSR协议基础上，提出一种安全的多路径路由SMOLSR.

OLSR以传统的LS协议为基础，在全网周期性交换网络拓扑更新和链路状态信息以使每个节点获取全网拓扑信息，并基于最短路径Dijkstra算法获取到目的节点的路由.运行OLSR协议的Ad Hoc网络中，虽然节点掌握了全网拓扑，但路由仅获取单个路径，且通过Dijkstra算法获取路径时没有考虑节点的处理负荷、网络拥塞状态、节点安全性等.针对有高可靠性和安全性要求的车载Ad Hoc网络，通过增加新的机制和算法，对OLSR进行多路径以及安全性的改进以满足业务需求.

文献[14]提出一种基于OLSR和源路由的多路径路由(SR-MPOLSR)算法，为充分利用网络资源，SR-MPOLSR采用了节点独立的原则，即从源节点到目的节点的多条路径之间，没有除源和目的节点外的其他共同节点，但在节点独立多路径的实施过程中，由于使用分步多重Dijkstra算法，导致搜索多路径的能力较差.本文仍采用节点独立多路径策略，提出广度优先与启发式优化减枝结合的多路径搜索方法.OLSR与多路径的SR-MPOLSR都选择Dijkstra算法搜索最短路径，然而在没有考虑链路时延、带宽情况下获取的最短路径本身价值不高，并付出了大量的计算代价，因此，在多路径路由时，快速搜索多条可行路径的方法比追求最短路径与次短路径方法更为合适.SMOLSR使用广度优先搜索的基本方法，当网络节点数较多时，广度优先搜索的计算复杂度还是较高，为提高搜索速度，需要对搜索范围进行减枝处理.一般的Ad Hoc网络的节点分布存在中心密集、边缘稀疏的情况，为充分利用网络节点，搜索更多的节点独立可行路径，在减枝时引入边缘节点优先的启发原则.广度优先搜索时在不同跳数可能搜索到相同节点，此时应用短路径优先原则对搜索进行减枝.另外，为使广度优先全局搜索在减枝优化后尽量保持较好的搜索能力，在搜索过程中采用一步回退机制来应对.SMOLSR通过周期性广播各节点的链路状态信息，掌握全网拓扑，当业务传送需求到来时，进行可达的多路径搜索，具体步骤如下：

步骤1：搜索从源节点到目的节点的第一跳中间节点.

若目的节点为源节点的邻居节点，则找到直接可达路径，路径搜索结束；若目的节点不为源节点邻居，此时将源节点的所有邻居节点作为第一跳中间节点，记入第一跳中间节点集合H1，并依次记录源节点到每个邻居节点的路径q1，q2，….

步骤2：搜索当前跳中间节点到目的节点的下一跳中间节点.

(a) 列出当前跳中间节点的所有邻居节点，去掉已经记入中间节点集合的节点，其他记入下一跳中间节点集合(当前跳为第一跳时，下一跳集合为H2).

(b) 执行带优化减枝的下一跳搜索，为每个当前跳中间节点选择出0～2个下一跳节点.

轮调执行节点的下一跳选择，第一轮执行边缘节点优先的下一跳选择，考察各个可选下一跳节点的度deg(ni)，选择度最小的节点作为下一跳节点并记录；第二轮执行随机选择，为每个当前节点再随机选出不重复的下一跳节点.若当前节点在每一轮下一跳节点选择中均失败，即当前节点无法找到合适的下一跳节点，则针对此节点进行一步回退，寻找可替换的节点再执行下一跳节点搜索操作.

步骤3：搜索到多条源到目的节点的路径，搜索完成.

所有路径搜索过程中，若下一跳节点集合中有目的节点则直接记录保存完整路径，当搜索到设定数量(2～4)的节点独立可达路径或完成全部空间搜索时，多路径搜索任务完成.

2 多路径下基于信任度的安全路由

在网络存在内部攻击时，搜索到的多条可达路径上可能存在恶意节点对传输进行窃听和破坏，需要在这些路径中寻找相对安全的路径进行数据传输.首先，基于已有方法在链路层、网络层、应用层进行攻击证据收集与恶意节点初步判断，如在链路层使用链路相关的公平和可用信息检测节点是否正常；然后，在网络层监听路由查询报文的处理过程，记录下来形成转发表和操作树，判断被监视节点是否按路由规范进行操作；最后，在应用层通过比较一定时间内每个逻辑邻居节点的服务请求数和服务出错次数来判断节点服务状态是否正常.

使用集中判决或分步式判决方法来判断各节点的信任度，节点i的信任度定义为bi=(1-pi)，bi∈[0，1]，其中pi表示节点i为恶意节点的概率.采用集中判决时，仲裁节点收集全网所有节点各个层次的节点攻击性评判指标和证据，在此信息基础上进行判决以得到每个节点是否为恶意节点的概率值，集中判决需要在网络中传输大量的原始攻击证据信息，会占用Ad Hoc网络的较多的带宽资源.采用分步式判决时，网络中的节点根据自己掌握的信息对其他节点(主要是邻居节点)是否为恶意节点进行独立判断，将判断结果传输至网络中的仲裁节点，由仲裁节点按

(1)

在完成网络节点信任度评估基础上，继续进行多条可达路径的信任度评估.本文采用动态路径信任度评估机制，业务传输前基于多条可达路径的初始信任度评估值选择实际传输路径，业务传输过程中监测反馈信息以调整路径信任度，进而调整路径.对路径l经过的节点集合表示为ql，假设路径上各节点是否为恶意节点的事件相互独立，将路径l无任何恶意节点的概率作为路径初始信任度，通过

(2)

得到所有可达路径的信任度，在多路径单传输(Multi-Path Single Transmission，MPST)和多路径多传输(Multi-Path Multi-Transmission，MPMT)两种机制下进行业务信息传输.采用MPST机制时，在信息的传输过程中，源节点仅在多条可达路径中选择和使用一条路径，即

(3)

为选择信任度最高的路径，若存在多条相同信任度路径，则在其中选择最短的一条.采用MPMT机制时，从多条可达路径中选择出信任度高的K条路径(通常K=2，3)，整个业务流过程，不同分组信息在K条路径中独立选择传输路径，使用Boltzmann分布的概率选择策略，选择路径ql的概率为

(4)

其中：τ(τ>0)τ为Boltzmann分布的温度系数，τ越大越趋向于平均选择，τ越小越趋向于贪婪选择；Q表示选出的K条路径的集合.在所有恶意节点均能够准确判断的情况下，MPST机制有利于信息传输的安全，当存在漏检的恶意节点时，采用MPMT机制则更加有助于提高网络生存性.

在信息的传输过程中，引入反馈延迟响应机制，对使用中的路径的信任度进行调整.传输路径上的恶意节点可能全部丢弃分组(如黑洞攻击)或按概率丢弃部分分组(报文丢弃攻击)，正常节点也可能因为链路质量较差或缓存溢出等原因丢失少量分组.为避免正常节点的偶然丢包产生的反馈导致无恶意节点路径的信任度降低，对目的节点的反馈进行延迟的而非实时的响应.在收集一段时间的反馈信息后，进行统计处理和分析，根据分组丢失概率与时间分布，对传输路径和路径信任度进行调整，调整时需要区分恶意节点导致的分组丢失与正常节点的分组丢失.正常节点因缓存溢出原因产生的丢包往往具有突发性，在一段时间内连续丢包，其他时间表现正常，则长时间的平均丢包率仍然较低，正常节点因无线链路质量问题会产生随机的分组丢失，但丢包率一般也较低，因此在反馈延迟响应机制下，通过设定丢包率门限可以较准确地找出恶意节点.在MPST机制下，设置最大允许丢包概率λ，若反馈的丢包率超过设定门限，则在除当前路径外的路径集合中重新选择信任度最高的路径.在MPMT机制下，对丢包率超过门限λ的各条路径执行信任度进行调整，公式为：

(5)

其中λl为设定的延迟时间内在路径l丢失的分组与该路径传输的所有分组的比值，即丢包率.MPST机制下的路径信任度调整降低了不安全路径的信任度，从而进一步降低在该路径上传输分组的数量，其降低的份额通过Boltzmann分布的概率选择策略分配到其他安全路径上.

3 仿真与结果

选择的网路拓扑的场景见图1.在MATLAB环境下，对图1的2个网络拓扑场景下的基于信任度的多路径安全路由算法进行仿真研究.图1(a)的网络在执行多路径搜索后，找到2条节点独立的可达路径，图1(b)的网络搜索到3条节点独立可达路径.

(a)网络拓扑场景1

(b)网络拓扑场景2

为不失一般性，设置1～4个恶意节点随机分布在多条可达路径的中间节点中，具体如表1所示.假设丢包率分别为1，0.3，0.2的恶意节点在节点信任度判断时得到的节点信任度分别为0.2，0.7，0.8.

表1 恶意节点在多条可达路径中间节点的情况

在图1中，在可达路径上均匀随机设置表1列出的恶意节点，得到网络在不同数量的恶意节点情况下的分组平均传输成功率，如图2所示.由图2可知，随着恶意节点数量的增加，网络中分组的传输成功率下降，当网络中的可达路径更多(3条)时，性能优于可达路径较少(2条)的情况.在恶意节点均被正常检测到时，即不存在漏检恶意节点时，对比MPST与MPMT两种传输机制，MPST表现出更好的性能，原因在于在能准确感知和判断网络状态的情况下，MPST仅选择信任度最高的路径策略是最优策略.

当采用MPMT传输机制时，Boltzmann分布中的温度系数τ对各条路径的选择概率有重要影响，图3为温度系数τ取不同值时，MPMT机制下网络传输性能比较.由图3可知，在恶意节点均被正常检测到时，较大的温度系数τ导致MPMT在路径选择时倾向于平均选择，获得网络分组传输成功率性能较低，而较小的温度系数τ导致MPMT在路径选择时倾向于贪婪选择，得到的网络性能较高，当τ足够小时，MPMT的性能接近MPST的性能.在仅存在1个恶意节点，丢包率分别为1(对应横坐标为0.5)和0.3(对应横坐标为1)的情况下，考察MPMT机制的性能.通常情况下，当恶意节点的丢包率更低时，则网络的分组传输性能更高，但在温度系数τ很小时(τ=0.2)，由于其贪婪选择效应，丢包率高的恶意节点的信任度很低，贪婪选择的结果使MPMT几乎不选择丢包率高的路径，使网络在丢包率为1的恶意节点场景下的性能高于丢包率为0.3的恶意节点场景.

图2 不同恶意节点数量下网络的分组传输性能

图3 不同的Boltzmann分布参数下MPMT机制的传输性能

实际网络中存在部分恶意节点漏检的情况，通过增加漏检恶意节点，对此类情况下多路径安全路由算法的性能进行仿真评估.在图1的2路径和3路径网络中，假设有2个已知恶意节点，丢包率为0.2和0.1，分别位于第1，2条路径上，同时假设有1个漏检恶意节点(漏检恶意节点的信任度为1)，其丢包率为0.2/0.4/0.6/0.8/1，位于第2条路径(2路径网络中)或第3条路径上(3路径网络中).图4为漏检恶意节点在不同的丢包率情况下，采用MPST和MPMT机制所得到的网络性能.

由图4可知，漏检恶意节点存在时，采用MPST机制可能选中恶意节点所在路径，此时网络分组传输性能大大降低，尤其是当恶意节点是100%丢包时，传输出现完全中断.MPMT机制在漏检恶意节点存在情况下的性能优于MPST机制，参数τ较大时获得性能更优，显然MPMT机制比MPST机制具有更好的鲁棒性，MPMT机制能在网络存在漏检恶意节点情况下提高网络的生存能力.

图5为MPMT机制下，引入反馈延迟响应，多次进行路径信任度调整后网络分组传输的性能变化.传输路径与恶意节点设置与图4的场景相同，漏检恶意节点的丢包率设定为0.6.在图5a的场景中，当设置的门限λ=0.3时，路径1的丢包率为0.2，路径1的信任度不需要调整，含漏检恶意节点的路径2 的丢包率为0.64，大于门限则引起路径2的信任度调整，调整后网络的分组传输成功率增加.当设置门限λ=0.15时，虽然不含漏检恶意节点的路径1与包含漏检恶意节点的路径2都要进行路径信任度调整，但包含漏检恶意节点路径的信任度调整力度更大，所以性能仍然保持上升.

由图5可知，MPMT使用较小的τ值虽然在首次传输时(信任度调整前)的性能略低于使用较大τ值(τ=1)的情况，但随着反馈延迟响应引起的路径信任度调整的进行，较小τ值(τ=0.2)的MPMT机制下的网络性能快速提升，大大优于较大τ值的情况.另外，由图5可知经过3～4次调整后，网络性能已基本收敛.

5 结论

自组织网络在动态拓扑和面临内部节点攻击情况下，多路径方式可以有效提高网络的性能.在传统的单路径OLSR路由协议基础上，本文提出基于信任度的多路径路由的SMOLSR路由方法.不同于传统的Dijkstra最短路径搜索强调最短最优性，SMOLSR的多路径搜索强调可达性和快速性，使用基本的广度搜索思想，引入启发式减枝处理，快速完成节点独立的多路径搜索.在获得多条可达路径后，基于节点和路径的信任度，从最优性和鲁棒性两个角度出发，设计了MPST和MPMT两种多路径使用机制，达到较好的网络传输安全性与有效性，通过反馈延迟响应处理的引入，进一步提升了应对漏检恶意节点和提高网络生存性的能力.