动态最优路径技术的路径诱导方法(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 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所示。

共3页: 1 [2] [3] 下一页