摘要：随着网络规模的不断扩大，一些基于纯数学模型的路由算法已经面临新的挑战。针对网络路由对实时性和可靠性的要求，采用动态路径诱导算法对网络流量进行实时预测，可以解决传统的诱导算法存在的时变性差和收敛慢的问题。动态路径诱导算法基于神经网络时间预测模型和遗传算法，经仿真表明该动态路径诱导方法在网络繁忙时能显著改善网络路由性能。
关键词：遗传算法；动态路径诱导；最优路径；神经网络
Abstract:Withtheconstantexpansion of the network size, some routing algorithms based on pure mathematical models have been confronted with new challenges. In order to meet the requirements for real-time and reliability of network routing, a new dynamic route guidance method resolved the limitation of traditional dynamic route guidance algorithm by forecasting the network traffic and composing real-time road weight matrix. This method is based on Neural Network (NN) and Genetic Algorithm (GA), and it has been proven by lab experiments that it can significantly optimize the performance of network routing in the busy network.
Keywords:geneticalgorithm;dynamic route guidance; optimal route; neural network
随着各种网络设备、高带宽的传输媒质和丰富多彩的网络内容不断涌现，一些基于纯数学模型的路由算法已面临挑战。基于神经网络和遗传算法的动态路径诱导方法，可以有效地保证在复杂多变的网络环境下最优选路的及时性和准确性。
1 网络路由概述
网络路由发生在开放系统互联(OSI)七层协议规定的第三层网络层，分为转发和选路，在此只考虑选路问题。当分组从发送方流向接受方时，网络层必须决定这些分组所采用的路径或者路由，计算这些路径的算法称为选路算法，例如在图1中一个选路算法将决定分组从主机PC1到达PC2所遵循的路径。
用图论中的模型来表示路由选路，图G=(N,E),其中N是网络环境中的路由设备集合(n1,n2……nn)，E是路由设备之间的路径集合。对于E中的每一条边用c(v1,v2)表示，表示v1和v2之间的单位路由费用量，具体费用可以在几个基础上进行运算再制定。若v1和v2之间不通就用∞表示，实际应用中就用一个很大的整数值表示该边不存在。将各边组织成一个矩阵W={c(v1,v2)) v1,v2∈N}，此时W就反映了这个时间段的网络路由代价情况。根据不同的路由目标可以制定不同的路由边权值，例如可以将数据包通过此段路径的平均时间作为权值，可以将数据包的最短选路路径做为权值，可以将数据包选路费用作为权值，还可以根据特殊的要求制定不同的权值赋予不同的含义。
2 动态选路诱导算法
现有的网络路由算法一旦选定路径就会按照既定的路径路由，即使这条路径上的网络流量已经饱和，而Internet上网络流量随时都在发生变化，因此势必会造成网络选路的进一步恶化和无限的路由延迟。动态选路诱导算法依据神经网络和遗传算法中染色体变异原理，根据选路路径上前一段时间的网络流量进行下一步的路由路径选择，使网络中各路由节点不会出现一些非常忙碌而另一些非常空闲的情况，同时减少了选路时延，增强了网络程序的时用性。
2.1神经网络路由时间预测模型
神经网络模型可以演变出新型的数据建模方法，它具有非线性、适应性与集成性等特点，能够准确、有效地实现路由信息的预测。神经网络路由时间预测模型由数据处理器和神经网络组成，将实测的路由时间数据和网络流量数据进行处理构成输入样本，分为输入层、隐层和输出层3层结构。
设qi(τ)为路段i上τ时刻的网络流量向量，qi(τ-1)为路段i上τ-1时刻的网络流量向量，Qi(τ)=[q1(τ)，q2(τ)……qd(τ)]；d为所研究网络的某条选路的路径跳数总和，若只考虑研究选路路径的网络流量，则置d =1；设ti(τ)为路段i上τ时刻的行程时间向量，ti(τ-1)为τ-1时刻的行程时间向量,Ti(τ)=[t1(τ)，t2(τ)……td (τ)]。考虑到路径的费用和网络流的特性，采用当前时间段和前m个时间段的网络流量和选路时间对未来时间段的选路时间进行预测。将 Qi(τ)， Qi (τ-1)…… Qi(τ-m)和Ti(τ)，Ti(τ-1)……Ti(τ-m)作为输入，Ti(τ+1)为输出值[1]，具体模型如图2所示。
根据神经网络预测模型计算可以得到的某时刻计算机网络各路径的权重[2]，即平均路由时间Xij，表示在某时刻从节点i 路由到节点j 所花费的时间，如果两节点间的路径不连通，则Xij的值等于一个大于所有路径的权值的和的值M。
2.2基于遗传算法的最优网络路由选路算法
该算法首先根据遗传算法中的染色体上基因的排列规则排列路由节点，节点的所有排列顺序就是所研究网络中的路由选路路径，然后通过染色体交叉、变异对初始生成的选路路径进行优化，经过一定代数的变异遗传，得到最优的选路路径。
(1) 染色体的编码
最优路径选择算法中的基因是路由节点，这些节点的排列顺序就是所要求的路径，所以采取有序的实数编码方式[3]。
(2) 适应度函数的确定
在遗传计算前期，根据每个染色体的有效基因片段，即染色体中连通的节点数p定义适应度函数，即f(k)=p(k)/(1+pmax)，其中p(k)表示第k个染色体的有效基因片段数，pmax表示这一代所有个体中最大的有效基因片段数，加1是为避免出现适应度值为1的情况；当计算进行到某一遗传代数，以染色体的路阻(路由费用)和定义适应度函数。定义p为某一染色体从O到D所经过的路径的路阻之和，即该染色体的目标函数p=∑d(i,j ),d(i,j )为i和j 之间的费用，则适应度函数为f (k)=1-p(k)/∑p(i )，其中k =1，2，3……M，M为群体规模[4]。
(3) 染色体的交叉
在父母染色体A、B中随机地选取一个交叉点Q，交叉点Q不能为起点和终点，Q至少应从第三个节点开始；当Max(PA,PB)≥Min(ZA,ZB)时，双亲染色体不交叉，以保证有效基因片段和零基因不被交叉，其中Z表示染色体中非零基因的个数；当Max(PA,PB)≤Min(ZA,ZB)时，Q应在Max(PA,PB)和Min(ZA,ZB)之间,以保证父母染色体的有效基因片段不被破坏，并去除交叉所得两个新染色体中重复的节点和冗余节点，在染色体的末端补0[4]。
