发布时间 : 星期四 文章QoS约束路由问题的求解算法的设计与实现更新完毕开始阅读08cca7d80029bd64783e2c9d
钦州学院本科毕业论文（设计）
给出了算法的主要步骤。本文的第四部分给出了在matlab平台上通过蚁群算法求解QoS路由问题实验的结果，并做出分析。最后，在本论文的第五部分中，概括了本论文的研究内容，分析了本论文的优缺点，并给出了以后的研究方向。
2 蚁群算法及QoS路由问题简介
2.1 QoS路由问题描述
Qos路由便是在网络中寻找一条满足带宽、时延、时延抖动等约束条件，同时优化配置网络资源的路径。为了问题分析方便，将网络看做为无向带权的连通图[13]。
设
定义1[14]：（链路） 在网络中，如果节点为链路
定义2[14]：（路径） 称节点序列
，且
Qos路由便是需要得到一条从源节点
到终点
的路径
为节点到节点
的一条长为的路径，其中
，且
连通，且
之间不存在其他节点，则称连接
的边
表示网络，其中表示网络节点集，表示网络边集，
，
，并且该路径需要满足具体业务的服务质量要求，同时优化配置网络
资源。
本文立足于多约束的Qos路由模型，综合考虑Qos路由的加性约束，乘性约束
5
劳明昕 QoS约束路由问题的求解算法的设计与实现
以及凹性约束。其中，对于加性约束，路径的指标等于组成该路径的各个链路、节点指标值的和，主要有路径时延以及时延抖动；对于乘性约束，路径的指标等于组成该路径的各个链路、节点指标值的乘积，主要有丢包率；对于凹性约束，路径的指标等于组成该路径的各个链路、节点指标值的最小值，主要有带宽。下面，从路径时延，时延抖动，丢包率以及带宽四个方面给出Qos路由的约束条件。
首先假设从源点到目标点由的指标可以表示如下：
a) 路径时延：
长度为的路径
，则Qos路
其中b) 路径时延：
，分别表示链路
、节点的时延指标值；
其中值； c) 丢包率：
，分别表示链路
、节点的时延抖动指标
其中d) 带宽：
其中
表示链路
的带宽指标值；
表示节点的丢包率指标值；
则多约束的Qos路由则是寻找满足下面约束条件的的路径：
6
钦州学院本科毕业论文（设计）
其中，、、
、
分别表示时延，时延抖动，丢包率以及带宽约束。
对于多约束的路由问题，由于指标量纲的不一致，指标在数值上会有较大的差异，这可能会导致部分指标被淹没的现象[15]。例如，如果时延抖动淹没的时延，最终结果
将不能反映业务Qos要求，因此我们需要模糊评判的方法，对各个指标进行综合的优化。
所谓的模糊评判，是指为各个指标建立隶属度函数，将指标映射到消指标间的量纲差异，其需要设立隶属度函数矢量：
其中，各个元素分别表示各个指标的隶属度函数，并且，其值越大，表示该指标越为重要。
由于不同的业务对服务质量的要求不用，因此各个指标的重要程度也不尽相同；针对具体的业务，可以对各个指标赋予权重，得权重向量：
并且，
。
，其可以表示为：
区间，取
到这里，便给出了可以判别一条路径优越性的综合指标
因此，多约束的Qos路由问题可以表示为在图中寻找
最大的路径。
从路由的方式来说，路由问题可以分为单播和多播问题，单播问题要求建立源节点和目标节点之间的一条路径。多播问题要求建立源节点和目标节点之间的支撑树。下面，将从单播和多播两个角度，分别建立Qos路由的数学模型
7
劳明昕 QoS约束路由问题的求解算法的设计与实现
2.2 Qos路由的数学模型 2.3 单播Qos路由
单播QoS路由问题是最基本的QoS问题，其主要目的是建立一条连接源节点和目标节点的路径，并且使其在满足QoS约束条件的同时最优化网络资源。
对于单播Qos路由问题，其可以描述为：
2.4 多播Qos路由
多播Qos路由问题是单播QoS路由问题的一个扩展，其要求在图中寻找一个可以连接源节点和目标节点的支撑树，并且要求该支撑树的各项指标满足QoS的约束条件的同时最优化网络资源[16]。
定义：（支撑树） 称图，
对于多播Qos路由问题，其可以描述为：
的一个连通无圈子图。
为图
的一个支撑树，其中
其中
，
，
，
分别是支撑树上的
各项指标值。类似于路径，下面给出计算支撑树各项指标的数学公式，如下所示：
a) 路径时延：
8