《动态最优路径技术的路径诱导方法》由会员分享，可在线阅读，更多相关《动态最优路径技术的路径诱导方法（7页珍藏版）》请在金锄头文库上搜索。
1、1动态最优路径技术的路径诱导方法关键词：动态最优路径,遗传算法；动态路径诱导；最优路径；神经网络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
2、 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
3、significantly optimize the performance of network routing in the busy network. 随着各种网络设备、高带宽的传输媒质和丰富多彩的网络内容不断涌现，一些基于纯数学模型的路由算法已面临挑战。基于神经网络和遗传算法的动态路径诱导方法，可以有效地保证在复杂多变的网络环境下最优选路的及时性和准确性。1 网络路由概述网络路由发生在开放系统互联(OSI)七层协议规定的第三层网络层，分为转发和选路，在此只考虑选路问题。当分组从发送方流向接受方时，网络层必须决定这些分组所采用的路径或者路由，计算这些路径的算法称为选路算法，例如在图 1
4、中一个选路算法将决定分组从主机 PC1 到达 PC2 所遵循的路径。2用图论中的模型来表示路由选路，图 G=(N,E),其中 N 是网络环境中的路由设备集合(n1,n2nn)，E 是路由设备之间的路径集合。对于 E 中的每一条边用 c(v1,v2)表示，表示 v1 和 v2 之间的单位路由费用量，具体费用可以在几个基础上进行运算再制定。若 v1 和 v2 之间不通就用表示，实际应用中就用一个很大的整数值表示该边不存在。将各边组织成一个矩阵 W=c(v1,v2) v1,v2N，此时 W 就反映了这个时间段的网络路由代价情况。根据不同的路由目标可以制定不同的路由边权值，例如可以将数据包通过此段路径
5、的平均时间作为权值，可以将数据包的最短选路路径做为权值，可以将数据包选路费用作为权值，还可以根据特殊的要求制定不同的权值赋予不同的含义。2 动态选路诱导算法现有的网络路由算法一旦选定路径就会按照既定的路径路由，即使这条路径上的网络流量已经饱和，而 Internet 上网络流量随时都在发生变化，因此势必会造成网络选路的进一步恶化和无限的路由延迟。动态选路诱导算法依据神经网络和遗传算法中染色体变异原理，根据选路路径上前一段时间的网络流量进行下一步的路由路径选择，使网络中各路由节点不会出现一些非常忙碌而另一些非常空闲的情况，同时减少了选路时延，增强了网络程序的时用性。2.1 神经网络路由时间预测模型
6、神经网络模型可以演变出新型的数据建模方法，它具有非线性、适应性与集成性等特点，能够准确、有效地实现路由信息的预测。神经网络路由时间预测模型由数据处理器和神经网络组成，将实测的路由时间数据和网络流量数据进行处理构成3输入样本，分为输入层、隐层和输出层 3 层结构。设 qi()为路段 i 上 时刻的网络流量向量，qi(-1)为路段 i 上 -1 时刻的网络流量向量，Qi()=q1()，q2()qd()；d 为所研究网络的某条选路的路径跳数总和，若只考虑研究选路路径的网络流量，则置 d =1；设 ti()为路段 i 上 时刻的行程时间向量，ti(-1)为 -1 时刻的行程时间向量,Ti()=t1()
7、，t2()td ()。考虑到路径的费用和网络流的特性，采用当前时间段和前 m 个时间段的网络流量和选路时间对未来时间段的选路时间进行预测。将 Qi()， Qi (-1) Qi(-m)和 Ti()，Ti(-1)Ti(-m)作为输入，Ti(+1)为输出值1，具体模型如图 2 所示。 根据神经网络预测模型计算可以得到的某时刻计算机网络各路径的权重2，即平均路由时间 XIJ，表示在某时刻从节点 I 路由到节点 J 所花费的时间，如果两节点间的路径不连通，则 XIJ 的值等于一个大于所有路径的权值的和的值M。,XbR/KdJ*N“eUo#cA$ bw+2GFic9 测控技术论文 U zsOXz4CjY6
8、dN;|i552.2 基于遗传算法的最优网络路由选路算法该算法首先根据遗传算法中的染色体上基因的排列规则排列路由节点，节点的所有排列顺序就是所研究网络中的路由选路路径，然后通过染色体交叉、变异对初始生成的选路路径进行优化，经过一定代数的变异遗传，得到最优的选路路径。(1) 染色体的编码最优路径选择算法中的基因是路由节点，这些节点的排列顺序就是所要求的路径，所以采取有序的实数编码方式3。(2) 适应度函数的确定在遗传计算前期，根据每个染色体的有效基因片段，即染色体中连通的节点数 P定义适应度函数，即 F(K)=P(K)/(1+PMAX)，其中 P(K)表示第 K 个染色体的有效基因片段数，PMA
9、X 表示这一代所有个体中最大的有效基因片段数，加 1 是为避免出现适应度值为 1 的情况；当计算进行到某一遗传代数，以染色体的路阻(路由费用)和定义适应度函数。定义 P 为某一染色体从 O 到 D 所经过的路径的路阻之和，即该染色体的目标函数 P=D(I,J ),D(I,J )为 I 和 J 之间的费用，则适应度函数为 F (K)=1-P(K)/P(I )，其中 K =1，2，3M，M 为群体规模4。 6论文动态最优路径技术的路径诱导方法来自 WWW.66WEN.COM 免费论文网(3) 染色体的交叉在父母染色体 A、B 中随机地选取一个交叉点 Q，交叉点 Q 不能为起点和终点，Q 至少应从第
10、三个节点开始；当 MAX(PA,PB)MIN(ZA,ZB)时，双亲染色体不交叉，以保证有效基因片段和零基因不被交叉，其中 Z 表示染色体中非零基因的个数；当 MAX(PA,PB)MIN(ZA,ZB)时，Q 应在 MAX(PA,PB)和 MIN(ZA,ZB)之间,以保证父母染色体的有效基因片段不被破坏，并去除交叉所得两个新染色体中重复的节点和冗余节点，在染色体的末端补 04。 (4) 染色体的变异将无效基因片段的第一位进行变异，变异后的染色体如果比原染色体的有效基因片段长，即 P 值增加，则替换母染色体，否则不予替换；当无效基因片段的第一位为 D，且该染色体是不合理的，则在 D 的前一个位置插入
11、一个节点，插入后要保证所得染色体仍是合法的，即符合编码规则，且不能改变染色体的长度。染色体的选择：首先将本代染色体经轮盘赌选择、交叉、变异后得到下一代染色体。由于在前几代的遗传计算中，大量的染色体都是不合理的，因此，将本代中合理的染色体代替下一代中基因片段小的不合理的染色体；如果本代中没有合理的染色体，则不进行替换。当遗传计算进行到一定代数时，染色体大部分是合理的，这时将本代路阻(选路费用)和最小的染色体与下一代路阻(算路费用)和最大的染色体进行比较，如果本代最优的染色体比下一代最差染色体的路阻小，则进行替换，反之则不替换；如果本代群体中路阻和最小的个体不是合理的路径，也不进行替换操作。7(5
12、) 染色群体的更新方式群体的设计需要平衡群体多样性维护和快速收敛，从数学的角度讲，允许父辈中的优良个体进入下一轮的竞争确保了最优解的迭代稳定性，而将后代中劣化的个体提前淘汰出局加速了寻优过程的实现。采取让子代中的优秀个体和父辈中的优良个体同时进入下一代的群体更新方式，即父辈个体经过交叉、变异操作后得到临时子个体，将父辈个体和临时子代个体进行比较，选择适应度高的个体作为子代个体进入下一代的竞争。这种群体更新方式能保证每一次交叉、变异操作都将产生两个更好的子个体，从而保证该算法的收敛性。3 仿真研究研究结果用如图 3 所示的网络连接图测试。以路由时间最短作为最优目标，通过神经网络对路由网各路径任意
13、时刻的平均路由时间进行预测，动态地得出该路网任意时刻的权重。取 T -1、T -2、T -3、T -4 四个时间段路网的数据流量和平均路由时间作为神经网络的输入，因此神经网络输入层取 8 个节点；输出层取 1 个节点，输出为 T 时刻该路由网各路径的行程时间。根据实验，隐层取 3 个节点。由神经网络预测所得 T 时刻路网各路段的平均行程时间构成路阻矩阵，路阻矩阵的大小是 1616，两节点间的路段不连通时，用一个大于所有路阻和的数 1 000 表示。 求得 t 时刻路网的路阻矩阵后，采用遗传算法进行最优路径的选择，遗传算法参数的确定如下：由于网络节点数为 16，所以染色体的编码长度为 16。综合
14、考虑论文所研究的网络规模、遗传算法的求解精度和遗传算法的收敛速度等方面的因素，8并通过多次仿真实验的验证可知，种群规模选为 160 时，最优路径选择算法的性能最好。经仿真实验验证，遗传终止代数可取为 85。用 Matlab 对上述试验模型进行仿真试验，仿真结果表明，对于 86 个 OD 对寻优，遗传算法计算得到 77 条最优路径，83 条有效路径，求解准确率为 0.895，有效率为 0.989，平均寻优时间为 8 ms15 ms，满足了路径诱导的准确性和实时性。对随机产生的 OD 对(1，16)分别求解 t1、t2、t3 时刻的最优路径，可得 R1 为 t1 时刻最优路径 1-5-6-11-1
15、2-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，解决了传统的诱导算法带来的收敛慢的问题，满足路由的实时性。但是对于大规模
16、的复杂的 Internet 路由，需要做进一步的研究来保证选路问题的及时性和收敛性，从而使选路在各方面得到最优化保证。5 参考文献91景玲,黄席樾,潘娅. 基于遗传算法的动态路径诱导J. 重庆大学学报, 2002, 25(4): 68-71.2徐仙伟,叶小岭.遗传算法优化 BP 网络初始权重用于入侵检测J.计算机应用研究,2005,22(3): 127-128, 132.3吴成东,杨丽英,许可.神经网络和遗传算法在动态路径诱导中的应用J.计算机应用研究,2006,25(4): 23-28.4FUL.An adaptive routing algorithm for in-vehicle route guidance systems with real- time information J.Transportation Research: P
