包交换网络中运用神经网络优化路径技术

余平

摘 要：互联网络中寻找最优路由是最广泛研究的一个课题，如何找到两个节点之间的最优路径却一直是包交换互联网络中的一个难题。本文提出了一种基于神经网络技术寻找最优路径的方法，通过调整神经元权值解决寻找最优路径问题，经过反向传播算法求解最优路径。通过运用本文算法测试表明，本文提出的算法计算简单，收敛速度快，适合在以包交换作为路由算法获得最优路径的研究中使用。可以尽管目前已经建立了最短路径算法，技术人员仍然在不断研究其他更优的路径选择方法，神经网络技术正是其中可选方法之一。

关键词：最短路径；神经网络；多层前向反馈网络（MLFN）；激活函数

中图分类号：TP18 文献标识码：A

1 引言（Introduction）

现代通信网络广泛使用TCP/IP网络体系结构，在TCP/IP网络体系结构中，网际层是很重要的网络层次，网际层的主要功能就是为数据包（网际层的数据信息单元）寻找路径并转发数据包，这个过程称为路由选择，路由选择是网际层最重要的功能，特别是在包交换网络中。路由选择技术对网络性能有很大的影响，最理想的路由算法就是为源节点与目标节点寻找最短路径并高速转发数据，并且能够避免数据包的丢失。不过要寻找两个节点之间的最短路径是众所周知的难题，目前广泛研究的最短路径算法都具有许多约束条件[1]。

在包交换网络中，两个主机之间的数据包通信一般通过如下方式：发送主机将数据组织成数据块，一般称为包，包中封装有目标主机的网络地址（一般称为IP地址），网络中的路由设备根据包中携带的目标地址为数据包寻找路径并转发，最终到达目标主机。一个路由策略的主要目标就是尽量减少IP数据包的传输延迟，尽最大可能传输数据包。影响数据包平均传输延迟时间的主要因素有网络的可靠性以及网络带宽容量和网络路由等因素的影响，其中路由对网络性能影响非常重大。因此一个理想的路由算法[2]应该尽量在规定的时间内找到最优路径来满足网络的服务质量（QoS）。

目前的最短路径搜索算法主要有：

（1）Bellman-Ford的动态规划算法，这种算法主要用于求含负权值的单源点最短路径算法。

（2）与Bellman算法类似的Dijkstra标记算法（也称迪杰斯特拉算法），其按路径长度递增依次产生最短路径。

当前在大多数的包交换网络中，最短路径计算都应用于网际层路由算法中，特别是网络连接的链路具有权值，权值反映的是每条传输链路的传输代价，包括传输容量、网络拥塞、传输状态（如包队列头分组延迟以及网络故障等）。最短路径问题可以归结为在源节点和目标节点之间寻找成本最小路径问题，换句话说，最短路径路由问题其实是在许多设计和规划中都需要的经典组合优化问题，神经网络技术[3]就可以解决这个复杂的问题。

2 多层前向反馈网络（MultiLayer forward feedback

network）

多层次网络，顾名思义由多个功能层次组成的网络，这种结构的网络，除了数据输出层和数据输入层意外，还包括隐藏层（或者隐藏单元），每个层次各司其职。多层前向反馈网络是神经网络中一种典型的分层结构，输入层神经元信息从输入层进入隐藏层神经元网络后逐层向前传递直至输出层，神经元与神经元之间的连接的权值称为链接权值。现代网络一般都是分层次的结构网络，其中最著名的有ISO七层体系结构与Internet实际使用的TCP/IP体系结构，网络的体系结构都是分层次的，都是多层次的网络结构。通信网络中的网络节点对应神经网络的神经元，节点与节点之间有链接链路，每条链路具有相应的链路权重，对应神经元节点与输出节点之间的链接链路也具有链接权重值，两者之间关系如图1所示。

图1 多层前向反馈网图

Fig.1 Multilayer forward feedback

3 反向传输网络（Back propagation network）

反向传输是训练多层人工神经网络的一种系统方法，它需要具有很好的数学基础，并具有广泛的应用潜力。

与生物神经元类似，人工神经元接收代表其他神经元输出的大量数据，每个输入都乘以链路链接权值，类似于生物神经中的突触强度，汇总后的输入加权值通过激活函数处理最后确定神经元的输出图，如图2所示。

图2 反向传输多层训练网图

Fig.2 Back propagation training network

其中的净值输入：

考虑到线值，相应的神经元输入由下面的公式给出：

=

相应的输出（激活值）使用非线性变换函数f给出。

4 激活函数（Activation function）

最后的数据输出是通过称为激活函数的非线性过滤函数产生的（有时称为变换函数），常见的选择是S函数或逻辑函数。如图3所示，其中α是斜率参数，当函数的改变在两个渐进值之间变化时，用于调整函数突发。

图3 逻辑函数

Fig.3 Logistic function

多个激活函数称为阶跃函数，或Heaviside函数，如图4所示。

图4 Heaviside函数

Fig.4 Heaviside function

5 学习速率（Learning rate）

大多数网络结构在学习过程中都要对权值w和v进行调整。学习速率系数的选择决定了权重调整的大小，从而影响每次迭代的收敛速度，差的系数选择可能导致收敛失败。如果学习速率系数过大，搜索路径将发生振荡，导致后面的收敛速度更慢。而如果系数过小，后面的过程将以很小的步骤进行，也会导致收敛速度减慢。

6 问题陈述（Statements）

考虑一个加权有向图G=（V；E），V是有n个顶点的集合，E是一组有序的m条边。固定成本Cij与图G中顶点i到顶点j的边相关联。在运输系统或机器人系统中，物理成本可能就是两个顶点间的距离，从一个顶点到另一个顶点也需要时间和精力。在一个通信系统中，成本可以由传输时间，节点到节点间链路容量来确定。一般来说，成本系数矩阵【Cij】不一定是对称的，比如，从顶点i到顶点j的成本不一定与从顶点j到顶点i的成本一样。此外，一些顶点间的边可能也不存在，也就是m可能小于n2（也就是m学习算法如下：

如果输出是正确的，那就不用做权重调整了。

Wij（k+1）=Wijk

如果输出是1，但是结果本来应该为0，那么在活动输入链路中将降低权重值。

Wij（k+1）=Wijk-α.xi，其中α是学习速率（因子）。

如果输出是0，但是结果本来应该为1，那么在活动输入链路中将增加权重值。

Wij（k+1）=Wijk+α.xi

Wij（k+1）是调整后的权重值，而Wijk是调整前的权重值。

Rosenblatts算法如下：

（1）用（n+1）个输入神经元X0，X1，X2，…，Xn创建感知器，其中X=1是偏置输入，O是输出神经元。

（2）初始化随机权重W=（W0，W1…Wn）。

（3）遍历训练输入模式X集合，使用权值为每个输入模式j计算输入加权后的总和。

（4）使用阶梯函数计算输出Y。

Y=f（netj）=1 netj>0

=0 其他

（5）对每个输入模式j，用目标输出Yj与计算得到的Yj进行比较，是否对所有的输入模式都正确分类并都存在且输出了权重值。

如果计算的输出Yj是1，而结果本来为0，用下面给出的公式修改权值。

Wi=Wi-α.xi

如果计算的输出Yj是0，而结果本来应该为1，就使用如下公式修改权值。

Wi=Wi+α.xi其中，α是学习因子。

（7）回到第（3）步。

7 结论（Conclusion）

神经网络被证明是优化分组交换多层网络的一种简单方法，Rosenblatts算法的初步完成为优化神经网络完成最短路径奠定了基础，经过几次迭代网络可以得到优化后的路由。

参考文献（References）

[1] 孙俊逸，雷建锋.基于神经网络下的最短路径问题求解[J].中 国科技论文在线，1-7.

[2] 李望超.神经网络中的最短路径问题[J].电子科学学刊，1996， S1期.

[3] 朱大铭，马绍汉.神经网络求解图最短路径问题的一种新方法 [J].软件学报，1996，A00：191-198.

作者简介：

余 平（1969-），女，学士，副教授.研究领域：计算机网络，网 络安全.