廖礼 马建林

摘 要 多约束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）中得到了很好的运用。……