基于PCNN的多约束QoS路由算法研究

廖礼 马建林

摘 要 多约束QoS路由是用来寻找一条同时满足多个约束条件的可行路径，这是NPC问题。本文主要介绍基于PCNN的算多约束QoS路由算法，通过对常见算法的分析，得出了PCNN在解决多约束QoS问题中的优势。

关键词 脉冲耦合神经网络 多约束QoS路由 最短路径

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

0引言

QoS路由（QoS Routing）是根据网络上可利用资源和流（flow）的QoS需求决定流的路由的机制。QoS路由应该实现以下三个目标：

（1）确定动态可行路径;

（2）优化路由资源利用;

（3）对整体性能影响尽可能小。

如果能通过有效的方法找出既满足应用的QoS需求，又具有最小代价，负载分布均衡的路由，则阻塞概率将大大降低，同时也将显著提高网络的利用效率。

服务时被要求提供的QoS，对于给定路径的指标一般可以分为三类：

（1）可加性。总QoS等于构成这条路径的所有链路QoS值的和（如跳数、成本、链路长度、时延等），可加性能够在问题中作预处理操作;

（2）可乘性。总QoS等于构成这条路径的所有链路QoS值的积（如误差率，丢包率和链路利用率等）;

（3）最大最小性。总QoS等于构成这条路径的所有链路QoS值中的最小者（如费用，时延、跳数等），总QoS等于构成这条路径的所有链路QoS值中的最大者（如流量、带宽和带宽利用率等）。

1基于PCNN的多约束QoS路由算法

脉冲耦合神经网络（PCNN，pulse-coupled neural network）作为有着生物学背景的新一代人工神经网络，在图像处理、模式识别、路径优化求解等方面具有重要的应用。PCNN网络使用其自动波特性求解路径优化问题，是一种非确定性方法，用够实现用最小的努力求得问题的全局最优结果，这一成果已经在求解最短路径问题（SP）中得到了很好的运用。

多约束QoS路由选择问题（单播）实际上是一个带约束条件的最短路问题。因此利用基于PCNN 的最短路求解方法，并对在PCNN上传播的每一个自动波随时进行约束条件满足与否的检验，是完全可以实现解决的。如果所有约束条件均满足，则该自动波继续传播。如果约束条件中至少有一个不满足，则该自动波消失，从而允许其它自动波在网络上继续传播。那么最先到达目标神经元的自动波走过的路径即为满足要求多约束的QoS路由路径，即为文中提到的式（6）的解。但实际中需对基于PCNN的最短路算法进行改进。若某自动波不满足任一个约束，则允许其他自动波继续传播，这就需要将不满足约束的自动波走过的路径的神经元熄火，它们的再次点火则应由其他自动波的继续传播引起。这就涉及一个自动波回退、熄火的过程，从点火神经元i回退的一般过程如下：

（1）判断到达神经元i的自动波是从哪个神经元的点火传播来的（设判断结果为是从神经元1的点火传播来的），是否是多个自动波通过竞争传播来的。若是，则设置，从而使得该自动波无法继续传播下去，结束回退，否则做（2）;

（2）使自动波回退到神经元l，即神经元i熄火，即使，且，并删除该自动波在路径矩阵中的路径，转去做（1）。

上述熄火、回退过程是沿传播到神经元i的自动波路径不断逆向而行的过程，直到该自动波是以竞争形式获得传播并通过设置链路费用为无穷来抑制不满足约束的自动波的传播，从而允许其它自动波在网络上继续传播。

这样我们就获得了基于PCNN的QoS路由选择算法：

step 1：如果NDV（D）>jitter，则式（6）无解，算法结束，否则转到step 2;

step 2：初始化。即对于，设，;

step 3：让start神经元点火。即设，并保持其余神经元的各个状态不变（其中 为一正数）;

step 4：对于，若神经元i点火，即若，计算链路路径start-i的QoS指标，若至少有一个指标不满足约束条件，则回退神经元i，否则做step 5;

step 5：自动波及其传播。对于，若，计算链路路径start-（i，j）的QoS指标，且若所有指标均满足约束条件、、、，并实现路径记录;

step 6：重复做step4～5，直到end神经元点火，或者自动波回退到start神经元为止。

step 7：对于end神经元点火的情况，根据路径记录矩阵B=（bij），从神经元end开始进行路径回溯，即可得到满足所有约束条件下费用最小的链路路径，即式（6）的解;对于自动波回溯到start神经元的情况，则式（6）无解，即没有满足所有约束的链路路径。算法结束。

2总结

将基于PCNN的QoS路由算法结果与蚂蚁算法、遗传算法、Hopfield算法的结果进行了对比，发现运用PCNN的QoS路由算法大大降低了迭代次数，明显提高了效率，并且算法全局收敛。另外，运用PCNN求解QoS路由问题后面又相继提出了Q-PCNNs模型和CPCNN模型，在保留PCNN基本特性的前提下，对模型做了适当的改进，使模型更加适合于解决QoS路由问题求解。

参 考 文 献

[1] 赵荣昌，马义德，绽琨.三态层叠脉冲耦合神经网络及其思想在最短路径求解中的应用[J].系统工程与电子技术，2008（09）.

[2] 张军英，王德峰，石美红.基于点火耦合神经网络的多约束QoS路由选择算法[J].通信学报，2002（06）.

[3] 董继扬，张军英.基于累积竞争神经网络的多约束路由算法[J].控制与决策，2004，19（07）：751-755.

[4] 朱尚明，黄明.基于脉冲耦合神经网络的QoS路由算法[J].华东理工大学学报（自然科学版），2008（03）.

[5] John Caulfield，H.&J.M.Kinser.Finding shortest path in the shortest time using PCNNS[J].IEEE Trans Neural Networks，1999，10（03）：604-606.

[6] 顾晓东，余道衡，张立.时延PCNN及其用于求解最短路径[J].电子学報，2004，32（09）：1441-1443.

[7] 张军英，王德峰，石美红.输出-阈值耦合神经网络及基于此的最短路径问题求解[J].中国科学（E辑），2003（33）.