基于神经网络实现QOS路由优化研究

陈晓琳

【摘 要】本文结合BP神经算法特性，分析了BP神经算法在解决QOS问题的可行性，并提出了解决该问题的有效算法模型，详细说明了如何运用该模型算法来解决QOS多播路由决策的问题。

【关键词】神经网络；QOS路由；优化算法

1 基于BP神经网路优化的可行性分析

由于BP神经网络是一个既向前传播也能向后传播的过程。它在多级网络中，可以计算出隐藏层的任何神经元的误差。它利用最后输出端的误差计算出前一个神经元输出端的误差，并再次利用这个误差值估计出更前一层的误差值。循环下来，就可获得所有其他各层的误差估计。这误差估计虽然它本身的精度会在向后传播的过程中不断降低，但却可以为多层网络的训练提供有效算法。

BP神经网络作为一个有导师训练的网络。在输入一个向量时，也会被要求给出对应的一个理想输出向量，使网络中出现异相联的映射。也就是输入向量与对应的输出向量之间构成一个“训练对”。

根据以上的研究分析，我们可以得出采用有导师学习的训练方法，需进行以下步骤：1）从训练的样本集合中取一个样本（Ai，Bi）；2）计算神经网络中的实际输出O；3）求D=Bi-O；4）根据D调整权矩阵W；5）对每个样本重复上述过程，直到对整个样本集来说，误差不超过规定范围。

BP神经网络向前传播训练方法：1）从样本集中取一个样本（XP，YP）；2）计算相应的实际输出OP；

在这个过程中，信息从输入层经过逐级的变换，传送到输出层。它是在网络完成训练后正常执行的过程，这个过程在网络中执行以下运算：

OP=Fn（...F2（F1（XPW（1））W（2））...）W（n））

BP神经网络向后传播阶段训练方法[1]：1）计算实际输出Op与相应的理想输出Yp的差；2）依照极小化误差的方式来调整网络的权矩阵。

以上两个阶段的训练方法都必须受到精度的控制，即：

Ep=■■（ypj-Opj）2

以上即作为网络中关于第p个样本的误差测度。而将网络关于整个样本集的误差测度定义为E=■Ep

值得注意的是，在开始调整神经元的连接权时，得先求出输出层的误差，而其它层的误差要通过此误差反向逐层推算后才能得到。

那么在这里还要注意误差传播分析中输出层权和隐藏层权的调整，下图是ANP到ANq接：

图1

ANP是输出层的第q个神经元，Wpq是从其前导层的第p个神经元到ANq得联接权。取wpq=wpq+Δwpq （1）

据Delta规则Wij（t+1）=W（t）+α（yi-aj（t））O（t） （2）

有Δwpq=αδvp （3）

那么在实际的路由问题中，我们就可以利用神经网络这种不断调整其连接权值或阀值的过程来不断的为我们每一个节点选择其最优的路由决定，并最终达到整个路径或延时方面的最优化。每一个节点中的神经元会根据每一次反馈过来的信息进行下一步选择。但由于每个节点同时存在很多不同的相连的路径，那么数据会通过各个不同路径先向前传播，然后根据最终到达目的节点的信息反馈到源节点，供其参考，最后选择最终合适的路径。

2 QOS路由优化算法的实现

被调整后的神经网络连接权值，可以使任意一个输入都可在网络对中得到最佳的的输出或者结果，这也是BP神经网络学习的最终目的。正向传播和反向传播构成了BP神经网络的学习过程。正向传播按照字面意思，就肯定是向前传递网络信息，并针对某一输入值得到相应输出结果；而反向传播既是向后一层一层的传递误差值，不断地向后反馈信息，调整每个神经元之间的的连接权值，使网络在得到不同的输入信息后都能经过正确的计算得到最佳的输出结果，并且误差得保持在一定的范围之内。

BP神经算法的学习方法是对需要得到训练的样本进行针对网络权值的调整的训练。每组都由相应的输入以及希望得到的输出这两个结构的组成。在向前传播的过程中，将需要得到训练的样本输入，通过每一个神经元进行处理，并最终到达输出。在这整个过程中，上一级的神经元就会影响到下一级的神经元，如果通过层层传播，最终得到的结果不是期望的结果，就会进行下一步，向后传播。

向后传播则是将误差信号依照原来的方式向后传播，传播的过程中根据一定的规则对每个节点的权重阀值进行更改，这个过程直到到达最开始的神经元才停止，转而开始上面的步骤，向前传播。这个过程循环往复下去，直至最终的输出结果达到期望的要求，那么这个时候算法的学习才算完毕，否则，继续往复下去。

学习过程的循环往复，最终到整个神经网络得到理想的结果为止。在这里需要注意的是，神经网络在进行训练的实际过程中，是只有向前传播而没有向后传播的。

具体步骤如下：在此次学习算法中，只考虑QOS路由的最小跳转数，根据BP神经网络模型的相关理论，本文首先建立一个反馈式神经网络路由分配计算机结构。

定义反馈函数R，它表示反向传播中对神经网络的反馈：1）定义参考数值P；2）若Rk≥Pk-1，那么有W+ij修正为w+ji+Rk； w-jt修正为w-jt+Rk/（n-1） .（ t≠i）

当该路径的回馈函数大于等于P，到达神经元j的所有正权重加强，这个就意味改路径下次被使用的机率增大，而且其它的负权重会相应加强些许，以期达到平衡。反之，神经元j的负权重被加强，该路径被使用的机率减小，而且其正权重相应加强达到平衡。

在此例中，节点A到目的节点F，路径（A，C，F）跳转2次，测量数据包返回起始节点A，获得的路径值为2。α为学习速率，用来控制反馈函数的取值范围。若α值取0.5，路径（A，C，F）的反馈函数为1，路径（A，E，C，F）的反馈值为0.667，很显然前一个路径为改变权重值做出最大的贡献，那么神经元就优先选择该路径。

3 BP神经网络算法过程

1）分别对输入层到隐含层的权值、隐含层到输出层的权值和输入层到隐含层的阀值进行初始化。（其中p0表示训练样本输入；t0表示训练样本期望值；ptest表示需要仿真的样本；l表示隐含层神经元数目；r表示迭代次数；lv表示权值学习率；lf表示阀值学习率；mse表示误差）

Function[out7，out1，out2，out3，out4，out5，out6]=bp0（p0，t0，ptest，l，r，lv，lf，mse） [p，minp，maxp，t，mint，maxt]=premnmx（p0，t0）；

P2=tramnmx（ptest，minp，maxp）；

m=size（p）；

n=size（t）；

w=rand（m（1），1）； %初始化输入层到隐含层的权值

v=rand（1，n（1））； %初始化隐含层到输出层的权值

thetal1=rand（1，1）； %初始化输入层的阀值

thetal2=rand（n（1），1）； %初始化隐含层的阀值

m0=size（ptest）；

sum00（1：r）=mse；

h0=plot（1：r，sum00，EraseMode，normal）；

2）分别计算输入层的输出、隐含层的输出和输出层的输出。

o1=p（：，g0）； %输入层的输出

o2=1./（1+exp（-（w*o1+theta1）））；%计算隐含层的输出

o3=v*o2+theta2； %计算输出层的输出

e=t（：，g0）-o3；

3）对神经网络中的各层次进行训练，即对输出层、隐含层和输入层进行阀值调整。

theta2=theta2+lf*e； %调整输出层阀值

deta=v*e；

v=v+lv*o2*e； %调整输入层至隐含层权值

g=（o2）.*（1-o2）.*deta；

theta1=theta1+lf*g； %调整隐含层阀值

w=w+lv*o1*g； %调整隐含层至输出层权值

4 结语

本文针对QOS的特诊及相应的一些参数特点，构建了QOS组播路由的数学模型。然后在此基础之上利用神经网络的工作原理和流程，立足于QOS路由——NP-complete问题的特征，阐述了选取BP神经网络算法作为参考依据的原因。和算法过程。

【参考文献】

[1]Q Zhu，M Parsa，J Garcial-Luna-Aceves.A Source-based Algonthm for Delay-constrained Minimum-cost Multi casting[J]. Proceeding of IEEE INFOCOM95， 1995.

[2]方建安，等.采用神经网络学习的神经网络控制器[J].控制与决策，1993，3（3）.

[3]万晓榆.下一代网络技术与应用[M].北京：人民邮电出版社，2003，3：15-16.

[责任编辑：丁艳]

3 BP神经网络算法过程

1）分别对输入层到隐含层的权值、隐含层到输出层的权值和输入层到隐含层的阀值进行初始化。（其中p0表示训练样本输入；t0表示训练样本期望值；ptest表示需要仿真的样本；l表示隐含层神经元数目；r表示迭代次数；lv表示权值学习率；lf表示阀值学习率；mse表示误差）

Function[out7，out1，out2，out3，out4，out5，out6]=bp0（p0，t0，ptest，l，r，lv，lf，mse） [p，minp，maxp，t，mint，maxt]=premnmx（p0，t0）；

P2=tramnmx（ptest，minp，maxp）；

m=size（p）；

n=size（t）；

w=rand（m（1），1）； %初始化输入层到隐含层的权值

v=rand（1，n（1））； %初始化隐含层到输出层的权值

thetal1=rand（1，1）； %初始化输入层的阀值

thetal2=rand（n（1），1）； %初始化隐含层的阀值

m0=size（ptest）；

sum00（1：r）=mse；

h0=plot（1：r，sum00，EraseMode，normal）；

2）分别计算输入层的输出、隐含层的输出和输出层的输出。

o1=p（：，g0）； %输入层的输出

o2=1./（1+exp（-（w*o1+theta1）））；%计算隐含层的输出

o3=v*o2+theta2； %计算输出层的输出

e=t（：，g0）-o3；

3）对神经网络中的各层次进行训练，即对输出层、隐含层和输入层进行阀值调整。

theta2=theta2+lf*e； %调整输出层阀值

deta=v*e；

v=v+lv*o2*e； %调整输入层至隐含层权值

g=（o2）.*（1-o2）.*deta；

theta1=theta1+lf*g； %调整隐含层阀值

w=w+lv*o1*g； %调整隐含层至输出层权值

4 结语

本文针对QOS的特诊及相应的一些参数特点，构建了QOS组播路由的数学模型。然后在此基础之上利用神经网络的工作原理和流程，立足于QOS路由——NP-complete问题的特征，阐述了选取BP神经网络算法作为参考依据的原因。和算法过程。

【参考文献】

[1]Q Zhu，M Parsa，J Garcial-Luna-Aceves.A Source-based Algonthm for Delay-constrained Minimum-cost Multi casting[J]. Proceeding of IEEE INFOCOM95， 1995.

[2]方建安，等.采用神经网络学习的神经网络控制器[J].控制与决策，1993，3（3）.

[3]万晓榆.下一代网络技术与应用[M].北京：人民邮电出版社，2003，3：15-16.

[责任编辑：丁艳]

3 BP神经网络算法过程

1）分别对输入层到隐含层的权值、隐含层到输出层的权值和输入层到隐含层的阀值进行初始化。（其中p0表示训练样本输入；t0表示训练样本期望值；ptest表示需要仿真的样本；l表示隐含层神经元数目；r表示迭代次数；lv表示权值学习率；lf表示阀值学习率；mse表示误差）

Function[out7，out1，out2，out3，out4，out5，out6]=bp0（p0，t0，ptest，l，r，lv，lf，mse） [p，minp，maxp，t，mint，maxt]=premnmx（p0，t0）；

P2=tramnmx（ptest，minp，maxp）；

m=size（p）；

n=size（t）；

w=rand（m（1），1）； %初始化输入层到隐含层的权值

v=rand（1，n（1））； %初始化隐含层到输出层的权值

thetal1=rand（1，1）； %初始化输入层的阀值

thetal2=rand（n（1），1）； %初始化隐含层的阀值

m0=size（ptest）；

sum00（1：r）=mse；

h0=plot（1：r，sum00，EraseMode，normal）；

2）分别计算输入层的输出、隐含层的输出和输出层的输出。

o1=p（：，g0）； %输入层的输出

o2=1./（1+exp（-（w*o1+theta1）））；%计算隐含层的输出

o3=v*o2+theta2； %计算输出层的输出

e=t（：，g0）-o3；

3）对神经网络中的各层次进行训练，即对输出层、隐含层和输入层进行阀值调整。

theta2=theta2+lf*e； %调整输出层阀值

deta=v*e；

v=v+lv*o2*e； %调整输入层至隐含层权值

g=（o2）.*（1-o2）.*deta；

theta1=theta1+lf*g； %调整隐含层阀值

w=w+lv*o1*g； %调整隐含层至输出层权值

4 结语

本文针对QOS的特诊及相应的一些参数特点，构建了QOS组播路由的数学模型。然后在此基础之上利用神经网络的工作原理和流程，立足于QOS路由——NP-complete问题的特征，阐述了选取BP神经网络算法作为参考依据的原因。和算法过程。

【参考文献】

[1]Q Zhu，M Parsa，J Garcial-Luna-Aceves.A Source-based Algonthm for Delay-constrained Minimum-cost Multi casting[J]. Proceeding of IEEE INFOCOM95， 1995.

[2]方建安，等.采用神经网络学习的神经网络控制器[J].控制与决策，1993，3（3）.

[3]万晓榆.下一代网络技术与应用[M].北京：人民邮电出版社，2003，3：15-16.

[责任编辑：丁艳]