动态最优路径技术的路径诱导方法

关键词：动态最优路径,遗传算法；动态路径诱导；最优路径；神经网络

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.

随着各种网络设备、高带宽的传输媒质和丰富多彩的网络内容不断涌现，一些基于纯数学模型的路由算法已面临挑战。基于神经网络和遗传算法的动态路径诱导方法，可以有效地保证在复杂多变的网络环境下最优选路的及时性和准确性。

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。,xbr/k[dj*n"euo#ca$~ ^bw+2gfic9测控技术论文u zsox€zcjy6dn}€;||i5

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]。

(4) 染色体的变异

将无效基因片段的第一位进行变异，变异后的染色体如果比原染色体的有效基因片段长，即p值增加，则替换母染色体，否则不予替换；当无效基因片段的第一位为d，且该染色体是不合理的，则在d的前一个位置插入一个节点，插入后要保证所得染色体仍是合法的，即符合编码规则，且不能改变染色体的长度。染色体的选择：首先将本代染色体经轮盘赌选择、交叉、变异后得到下一代染色体。由于在前几代的遗传计算中，大量的染色体都是不合理的，因此，将本代中合理的染色体代替下一代中基因片段小的不合理的染色体；如果本代中没有合理的染色体，则不进行替换。当遗传计算进行到一定代数时，染色体大部分是合理的，这时将本代路阻(选路费用)和最小的染色体与下一代路阻(算路费用)和最大的染色体进行比较，如果本代最优的染色体比下一代最差染色体的路阻小，则进行替换，反之则不替换；如果本代群体中路阻和最小的个体不是合理的路径，也不进行替换操作。

(5) 染色群体的更新方式

群体的设计需要平衡群体多样性维护和快速收敛，从数学的角度讲，允许父辈中的优良个体进入下一轮的竞争确保了最优解的迭代稳定性，而将后代中劣化的个体提前淘汰出局加速了寻优过程的实现。采取让子代中的优秀个体和父辈中的优良个体同时进入下一代的群体更新方式，即父辈个体经过交叉、变异操作后得到临时子个体，将父辈个体和临时子代个体进行比较，选择适应度高的个体作为子代个体进入下一代的竞争。这种群体更新方式能保证每一次交叉、变异操作都将产生两个更好的子个体，从而保证该算法的收敛性。

3 仿真研究

研究结果用如图3所示的网络连接图测试。

以路由时间最短作为最优目标，通过神经网络对路由网各路径任意时刻的平均路由时间进行预测，动态地得出该路网任意时刻的权重。取t -1、t -2、t -3、t -4四个时间段路网的数据流量和平均路由时间作为神经网络的输入，因此神经网络输入层取8个节点；输出层取1个节点，输出为t时刻该路由网各路径的行程时间。根据实验，隐层取3个节点。由神经网络预测所得t时刻路网各路段的平均行程时间构成路阻矩阵，路阻矩阵的大小是16×16，两节点间的路段不连通时，用一个大于所有路阻和的数1 000表示。

求得t 时刻路网的路阻矩阵后，采用遗传算法进行最优路径的选择，遗传算法参数的确定如下：由于网络节点数为16，所以染色体的编码长度为16。综合考虑论文所研究的网络规模、遗传算法的求解精度和遗传算法的收敛速度等方面的因素，并通过多次仿真实验的验证可知，种群规模选为160时，最优路径选择算法的性能最好。经仿真实验验证，遗传终止代数可取为8[5]。

用matlab对上述试验模型进行仿真试验，仿真结果表明，对于86个od对寻优，遗传算法计算得到77条最优路径，83条有效路径，求解准确率为0.895，有效率为0.989，平均寻优时间为8 ms~15 ms，满足了路径诱导的准确性和实时性。

对随机产生的od对(1，16)分别求解t1、t2、t3时刻的最优路径，可得r1为t1时刻最优路径1-5-6-11-12-16，r2为t2时刻最优路径1-2-6-11-15-16，r3为t3时刻最短路径1-2-3-4-8-12-16。具体计算结果见表1所示。

从表1可以看出，当网络流量在不断变化时，在不同时刻对应各条路径的费用也在不断的变化，路径最短的所需的费用并不是最少的。

4 结束语

实验室模拟条件下不存在路由拥塞导致的网络延迟以及真实环境中存在各种网络问题。从表3的试验结果来看，基于神经网络的遗传算法的动态路径诱导算法在动态路由中可以得到很好的预测流量，并且最优路径的求解率达到89.5％、有效率达到98.9％，解决了传统的诱导算法带来的收敛慢的问题，满足路由的实时性。但是对于大规模的复杂的internet路由，需要做进一步的研究来保证选路问题的及时性和收敛性，从而使选路在各方面得到最优化保证。

5 参考文献

[1]景玲,黄席樾,潘娅. 基于遗传算法的动态路径诱导[j]. 重庆大学学报, 2002, 25(4): 68-71.

[2]徐仙伟,叶小岭.遗传算法优化bp网络初始权重用于入侵检测[j].计算机应用研究,2005,22(3): 127-128, 132.

[3]吴成东,杨丽英,许可.神经网络和遗传算法在动态路径诱导中的应用[j].计算机应用研究,2006,25(4): 23-28.

[4] adaptive routing algorithm for in-vehicle route guidance systems with real-time information [j].transportation research: part b, 2001, 35( 8) : 749-765.

[5]wahlej,annen o, schuster c, et al. a dynamic route guidance system based on real traffic data [j]. european journal of operational research, 2001, 13(1): 302-308.

作者简介：

朱能方，本科毕业于安徽大学，硕士毕业于电子科技大学。现工作于中兴通讯股份有限公司，主要研究方向为网络信息安全。黄迪明，电子科技大学计算机系教授。主要研究方向为网络信息技术、信息安全、软件工程等，已发表学术论文20余篇。