基于动态可信度的QoS路由优化与仿真

余思东，黄 欣，潘绍明

(1.广西农业职业技术学院 现代教育技术与网络信息中心,南宁 530007;2.广西科技大学 电气与信息工程学院，柳州 545006)

0 引 言

服务质量路由(Quality of Service Routing,QoSR)一直是工业界所关注的热点[1-3]。而当前有关QoS路由的研究，都是基于网络环境是可信网络环境这个前提。但是，现实中这种前提是难以成立的，主要原因在于：Internet具有开放互联特性，使得任何潜在威胁能够方便、便捷地接入，且潜在威胁具有多样性、隐藏性等特点；Internet设计初期，只考虑数据高效传输，而忽略数据传输过程中的安全机制，从而不能确保用户使用安全；据统计，2015年国家互联网应急中心(CNCERT)就检测到10万多个恶意软件、木马及僵尸网络控制端试图攻击或控制Internet上服务器及主机，网络安全问题时有发生，导致网络环境不可信。面对如此复杂Internet环境，有关可信QoS路由相关技术的研究迫在眉睫。

文献[4-5]中认为可信QoS路由指任何网络环境下，都能为用户提供具有服务质量保证的路由，且该路由可信、可控、可管，可预知。其目的在于，优化网络安全环境，提高网络安全服务能力。

由于网络节点是信息传输主体，因而一直都是被攻击的主要对象。文献[6]中指出网络节点是构建网络结构的主要组成部分，当网络节点危险系数具有一定比例但低于某个阈值时，网络环境将出现滞后服务现象；当网络节点危险系数超过某个阈值时，整个网络安全环境极度危险。因此，网络节点可信的QoS路由研究是可信QoS路由研究领域的重心。

1 相关的研究工作

当前关于网络节点可信的QoS路由研究主要挑战之一，如何在网络节点动态条件下，对网络节点进行评估，并依据评估结果选择一条或多条可信路由。现有的研究成果只考虑网络节点是静态的，并没有考虑网络节点动态变化特性。如文献[7]中提出一种网络节点可信QoS路由算法，该算法基于区间形式描述用户所需及可信所需的模糊性，并根据此定义及已有滑动窗口和窗台的信任控制机制理论并结合满意度函数建立模型，同时提出适合该模型的狩猎搜索可信路由算法。文献[8]中在集中式路由基础上构建一种适合低连接度结构的域内保护路由算法，通过构建备份路径，解决集中式路由面临的低连接度环境下游网络节点失效问题。文献[9]中基于贝叶斯理论提出一种网络节点信任机制，该机制通过概率公式对待测节点的通信行为结果进行评估，具有一定的主观性和随机性。文献[10]中提出一种自适应性路由算法，该算法分别把可信度与QoS满意度作为优化目标，从多目标优化角度解决可信路由问题。文献[11]中针对移动自组织网络中移动节点主体及其信息传递安全性问题，提出一种基于博弈的移动节点信任评估模型。

以上研究成果的思路是首先构建某种方法评估网络节点可信度，然后在可信度满足阈值的网络节点集合中选择QoS路由。但以上算法都具有共同不足之处，容易产生网络节点可信度评估误差问题。可信度评估误差指网络节点行为在动态发生变化，下一时刻行为产生的结果必将影响上一时刻评估值。即网络节点在上一时刻评估的可信度值，在下一时刻可能发生变化。由于以上评估方法并不具备动态评估特性，容易造成提供的可信QoS路由存在安全隐患。

本文从全局协同角度，提出一种基于元胞自动机及复杂网络SI扩散理论的启发式路由算法(Heuristic Algorithm Based on Cellular Automaton and SI，HACASI)，该算法具有动态评估机制，从而保证具备动态提供可信QoS路由能力。

2 模型及问题描述

元胞自动机是离散型动力系统模型[12]，具有结构简单、易于扩展等特点，元胞之间依据局部变化规则协同合作，能够模拟全局网络环境演化过程，并能够预测下一时刻网络环境。但元胞自动机只是一种框架模型，并不提供具体的变化规则。SI模型是基于传染病扩散的传播模型[13]，能够模拟危险网络节点，恶意传播信息过程。两者相结合能够模拟网络节点通信扩散过程，预测下一时刻网络环境及各个网络节点状态。

2.1 模型

构建一个8元系统模型：LCA={D,RS,RM，R,f,FLAG,RS’,f’}:系统中每个元胞代表一个网络节点，网络节点之间的边界条件定义为周期型。D为网络空间维数(为方便讨论在此定义为二维空间)，RS={可信，不可信}表示网络节点状态集合，当网络节点可信时FLAG为1，否则为0。RM为当前网络节点邻居状态集合，RM={RM1,RM2,…,RMn}，n表示邻居节点总数。R为节点邻居半径，当R=1时定义为网络节点直连下一跳，f为网络节点状态演变规则集，FLAG为网络节点状态标志集合，FLAG为网络节点状态标志集合，当网络节点可信时FLAG为1，否则为0。RS’为网络节点扩展状态集合，f’ 为扩展演化规则集，初始时RS’和f’处于未激活状态。

(1)网络节点演变规则。对于任意节点i，根据SI模型定义，如果其为不可信节点，则以后状态永远无法改变(不在本文讨论范围)。本文主要讨论的是可信网络节点，其受不可信节点影响，可转变为不可信状态，也可依据一定规则维持原有可信状态。

具体情况如下：假设网络节点i在时刻t状态为St(i)，在下一时刻t+1状态变化为：

(1)

式中:Flag(i)为节点i状态标志;St+1(i)为节点i在下一时刻处于可信状态;It+1(i)为节点i在下一时刻处于不可信状态，Qcom通信强度阈值，comt(i)为在时刻t节点i直连通信强度(与邻接节点通信强度)，且：

(2)

式中:β1、β2为系数，NDt(i)表示在时刻t节点i对外通信强度，Trt(k)表示在时刻t与节点i通信的节点k可信度。且：

NDt(i)=∑jαjFW(wij)

(3)

式中：αj为系数；FW()为权重函数；wij为节点对之间权重。

对任意节点k，在时刻t可信度为：

(4)

式中：η1、η2为系数;Frt(k)为在时刻t节点k的通信频率;x为变量。

(2)网络稳态规则。设参数T’∈(0,TE)为时间参数，其中：TE>0为正整数，对任意节点i，在T’ 范围内其状态标志Flag(i)不再改变，即Flag集合内，Flag(i)保持不变，则称网络环境达到稳态。

2.2 问题描述

在网络环境达到稳态条件下，寻找一条从源节点Vs到目的节点Vt的可信路径ps，在可信路径上的每个中间网络节点必须可信，且各项度量参数(包括带宽bw、延迟dl、延迟抖动jt、丢包率ls等)需满足用户服务要求：

Q:ps

(5)

(6)

式中：bw(Ubw)、dl(Udl)、jt(Ujt)、ls(Uls)分别表示其相应的阈值，Vi表示ps中间传输节点。

3 算法设计

为使计算方便，对式(5)中每个网络节点度量参数(链路上的度量参数归并到网络节点上)进行归一化变换，合并成一个加性度量参数。根据文献[14]中研究，式(5)中凹性参数(带宽)可通过剪枝策略对不满足要求的链路(网络节点之间的边)进行排除，乘性参数可通过对数变化，转化为加性参数，则可信路由问题可转换为：

(7)

(8)

式中:wj>0,j=1,2,…,为网络节点上各个度量参数权重;f(xj)，j=1,2,… 为所对应的各个加性度量参数函数值;δj为各个加性度量参数对应的阈值。

基于式(6)提出HACASI算法，具体实现如下：

步骤1初始化8元网络模型为二维空间模型，网络节点边界为周期性，网络节点半径为1，定义网络节点状态集合RS和状态标志集合FLAG，设置时间参数T’，设置起始网络节点Vs和终点网络节点Vt。

步骤2在时间T′内，依据演化规则式(1)～(4)，对每个网络节点进行状态调整，并对其相应的状态标志更新。

步骤3当网络模型达到稳态时，激活RS′ 和f′，遍历集合FLAG中所有FLAG为1的网络节点，设置其扩展状态集RS′={遍历，未遍历} ，并初始化为未遍历状态。

步骤4对任意网络节点Vi，在时刻t，根据扩展演化规则集f′计算如下：

若Vi为已遍历状态，则当前状态保持不变；

若Vi为未遍历状态，根据式(6)中合并度量参数，计算Vs和Vi之间的合并度量参数权重D(Vs,Vi)(如果Vi与Vs不能直连或不能经过已遍历网络节点达到，则设为无穷大)；

步骤5网络节点Vi与直连未遍历网络节点相互交换D(Vs,Vi)信息，并进行大小排序，设数组变量Array_D保存排序结果。

步骤6在Array_D中挑选使得D(Vs,Vi)最小的网络节点Vi并设置为已遍历状态，并从Array_D中删除Vi，由Vs记录下跳节点Vi。

步骤7如果Vi=Vt且其相应的约束满足条件，则退出；否则进入Step8。

步骤8对所有未遍历过的网络节点Vj，如果D(Vs,Vj)>[D(Vs,Vi)+D(Vi,Vj)] 则按照公式D(Vs,Vj)=[D(Vs,Vi)+D(Vi,Vj)]更新(D(Vi,Vj)参考步骤4中(2))，并返回步骤4。

4 仿真实验

实验硬件：服务节点30个，每个服务节点配置CPU为intel 酷睿 I7-6500U，内存8GB，硬盘256GB，操作系统为Linux Ubuntu Server。对于每个服务节点都可配置多个虚拟机环境。

网络结构：Waxman[15]模型随机生成两种网络拓扑结构。随机生成具有53节点，68链路拓扑结构(简称NetOne)。

对于该网络结构，在每条链路上随机产生n个度量参数，链路上度量参数值随机产生，同时每个度量参数的约束随机产生。

实验指标：① 节点可信比(Node Trusty Precision Rate,NTPR),该指标主要衡量网络节点被攻击后，在下一时刻评价网络节点可信，总体预测成功比例。② 可信QoS路由成功率(Trusty QoS Routing Success Rate,TRSR),该指标主要检测算法计算出的路由结果是否满足用户需求且保证路由是可信的。

测量手段：对NetTest，实验仿真时间总长为90 s，每隔18 s随机模拟产生一次对网络节点的攻击。

根据以上实验定义，分别验证本文提出的算法HACASI与算法HTRA[7]和算法AHPSO[10]的NTPR和TRSR性能。

NTPR实验结果如下：

图1中，横坐标表示实验时间，纵坐标表示NTPR。实验仿真时间达到36 s处且经过2次模拟攻击后，HACASI算法的NTPR平均维持在90.6%左右，HTRA算法和AHPSO算法的NTPR分别维持在88%和89.3%。但实验仿真时间达到72s和90s处且经过3～5次以上模拟攻击后，HACASI算法的NTPR平均维持在78%左右，HTRA算法和AHPSO算法的NTPR分别维持在68.5%和69.8%，识别率分别提高了13.9%和11.7%。

图1 NetTest模拟环境实验结果1

图2中，横坐标表示实验时间，纵坐标表示NTPR。实验仿真时间达到52 s处且经过2次模拟攻击后，HACASI算法的NTPR平均维持在93%左右，HTRA算法和AHPSO算法的NTPR分别维持在87.8%和88.2%。但实验仿真时间达到130 s处且连续经过3次以上模拟攻击后，HACASI算法的NTPR平均维持在76.3%左右，HTRA算法和AHPSO算法的NTPR分别维持在63%和64.8%，识别率分别提高了21%和17.7%。

图2 NetTest模拟环境实验结果2

TRSR实验结果如下：

图3中，横坐标表示实验时间，纵坐标表示TRSR。实验仿真达到36 s且经过2次模拟攻击后，HACASI算法的TRSR平均维持在93.5%左右，HTRA算法和AHPSO算法的TRSR分别维持在91%和90.6%。但实验仿真达到90 s且连续经过3次模拟攻击后，HACASI算法的TRSR平均维持在77.4、3%左右，HTRA算法和AHPSO算法的TRSR分别维持在70%和69.3%，路由成功率分别提高了10.4%和11.5%。

图3 NetTest模拟环境实验结果3

图4中，横坐标表示实验时间，纵坐标表示TRSR。实验仿真时间达到52 s处且经过2次模拟攻击后，HACASI算法的TRSR平均维持在92.3%左右，HTRA算法和AHPSO算法的TRSR分别维持在89.3%和88.5%。但实验仿真时间达到130 s处且连续经过3次以上模拟攻击后，HACASI算法的TRSR平均维持在77.6%左右，HTRA算法和AHPSO算法的TRSR分别维持在64.7%和66%，路由成功率分别提高了19.9%和17.5%。

图4 NetTest模拟环境实验结果4

从4次试验结果可知，随着网络规模扩大及模拟攻击次数增多，HACASI算法表现出具有较好的扩展性、可信性和可靠性。

5 结 语

针对现有研究成果不具备动态评估网络节点可信度能力，提出一种启发式算法，该算法引入元胞自动机和复杂网络SI模型，建立具有全局协同机制的网络节点可信度动态评估模型，有效降低网络节点可信度评估误差，提高QoS路由可信度。但本文未考虑路由失败重传机制以及信息内容可信等问题，这些将是未来工作的重点。