《基于Pareto最优的QoS路由算法》由会员分享，可在线阅读，更多相关《基于Pareto最优的QoS路由算法（6页珍藏版）》请在金锄头文库上搜索。
1、基于 Pareto 最优的 QoS 路由算法Pareto Optimal based QoS Routing AlgorithmAbstract:We propose a novel unicast QoS routing algorithm to address two additive constraints routing problem. The algorithm based on the concept of Pareto optimal and dynamic weight coefficient mechanism. Normally to attain a high perf
2、ormance, the algorithm only needs run 23 Dijkstra algorithm. Extensive simulations have shown that the algorithm is very efficient and converges quickly.Key words:QoS routing, Pareto optimal, Dynamic weight coefficient, dominated path摘 要:QoS 路由是 QoS 框架中的重要组成部分，旨在寻找多约束条件下的可行路径。本文在解决多约束（MCP）问题时，引入了 Pa
3、reto 最优概念。基于 Pareto 最优概念，提出了基于 Pareto 最优的 QoS 权重空间划分模型。在该模型中，根据路由请求与 MCP 问题解的关系，很容易判定路由请求是否能够被满足。在模型基础上，提出了用于解决具有两可加约束的动态权重系数路由算法 PODWCA。PODWCA 平均只需要运行 23 次 Dijkstra 算法就能达到很高的性能。仿真结果验证了 PODWCA 算法的有效性。关键词:QoS 路由，Pareto 最优, 动态权重系数，支配路径1 引言目前，越来越多的网络应用都需要服务质量保证，尤其是多媒体应用大多有时延、带宽以及费用的要求。一般说来，QoS 度量尺度（met
4、rics）有三种类型，可加尺度，如时延、代价等；可乘尺度，如丢失率等；极大极小尺度，如带宽等。对于极大极小约束，往往可以在路由算法之前采用一定的缩减步骤进行处理；可乘尺度可以转化为可加尺度，因此，QoS 路由问题面临的主要问题来自可加尺度。 定义 1.多约束问题（MCP） 网络，N 是节点集合，E 是边集。每条边对应一个多维权重向量。是可加权重),(ENG),.,(21mwwwwiw（weight） ，。给定 m 个约束，, 寻找从源节 s 到目的节点 d 的路径P，使得mi,.,1mjLj,.,1, i=1,m。i PeiiLewPw)()(路径P又可以写成的形式。满足所有 m 个约束的路径
5、称为一个可行路经，可能存在多条从),.,(21mwwwPs 到 d 的路径同时满足约束。当 m=2 时，MCP 问题就是具有两个可加约束的路由问题，该问题是 NP 完全问题。目前已经有很多用来解决 NP-完全问题的启发式算法1-7。Yong Cui6 提出了解决多约束的预计算算法 MEFPA。当 k=2 时，MEFPA 为二约束 QoS 路由算法，本文称其为2EFPA。2 Pareto 最优 2.1 符号约定: s 表示源节点；d 表示目的节点；表示 s 和 d 间的所有路径集合 Dijkstra()基于单一权重sdP,的 Dijkstra 算法；表示运行 Dijkstra()算法得到的路径。
6、21www1),(, 2, 1wwP,2.2 路径代价函数我们采用了线性路径代价定义形式，即把两个链路权重线性相加：= )(Pw, . 这样，Dijkstra 算法就可以基于单一权重而被使用。)()()()(212 11PwPwewewinii 12.2.1 QoS 权重空间对于路径 P=，每条边具有两个可加权重，则路径 P 每个权重的和可表示成如下形式：knnn 212，j。因此路径 P 又可写为。kiiijjnnwPw21)()(2 , 1)(),(21PwPwP定义 2. QoS 权重空间. 被称为 QoS 权重空间，如果对任212WWW何，j。),(ENGPjjWPw)(2 , 1定义
7、 3. 映射 f. 被称为 QoS 权重空间，如果对任何，j。212WWW),(ENGPjjWPw)(2 , 12.3 Pareto最优定义 4. 支配路径：路径支配路径，当且仅当,: ),.(1muuP),.(1mvvP,.,1miiivu ,.,1mi， 在本文的后面，我们将采用来表示路径支配路径。iivu p),.(1muuP),.(1mvvP),.(1muuP),.(1mvvP定义 5. Pareto 最优路径称为 Pareto 最优的，如果不存在路径，使得),(21wwPsdP),(21wwPsdP支配，即。 ),(),(2121wwwwPf),(),(2121wwwwPfp),(2
8、1ww),(21ww定义 6. Pareto 集及 Pareto front（）truePtruePF对于 MCOP 问题，=| 为 MCOP 问题的 Pareto 最优解。trueP),(21wwPsdP),(21wwPPareto front =|。由于路径 P的非连续特性，是中的点集。truePF),(21wwPf),(21wwPtruePsdPtruePF2W定理 1.对任何，路径都是 Pareto 最优的，即。),(1),(, 2, 1wwP),(, 2, 1wwtruePF证明：采用反证法. 如果路径不是 Pareto 最优的，则存在路径，使得),(, 2, 1wwP),(/, 2
9、, 1wwPtrueP，即，并且。因此，),(/, 2, 1wwp),(, 2, 1ww, 1, 1/ww, 2, 2/ww:2 , 1i,/iiww。这意味着当运行 Dijkstra()时，返回的路径是，而不是, 2, 1, 2, 1/wwww,),(/, 2, 1wwP，这与事实矛盾。),(, 2, 1wwP3 具有 2 可加约束 QoS 路由问题的 Pareo front定理 2. 对于权重系数，如果，则(1)，并且(2) ),(ii1ii2 , 1i1211, 1w22, 1w11, 2w。22, 2w证明：(1)由已知条件可知：=(i)2,22,21, 11, 1 21112111w
10、www)()(1, 12,22,21, 1 221111wwww)(1 (1, 12,2 221ww=(ii)1, 11, 12,22,2 22122212wwww)()(2,21, 11, 12,2 222112wwww)(1 (2,21, 1 222ww(i)+(ii)(iii)()(2,21, 12,21, 1 2211wwww如果，则(iii)。根据定理 1，及都在2,21, 1 11ww),(2,22,2 21wwp),(1111 21ww),(1, 11, 1 21ww),(2,22,2 21wwPareto front 中，不能支配，因此，。),(2,22,2 21ww),(1,
11、 11, 1 21ww2,21, 1 11ww(2) 根据定理 1，和不能相互支配，再由（1）的结论可知),(2,22,2 21ww),(1111 21ww2,21, 1 11ww11, 2w。22, 2w定理 3. 对于 2 可加约束 MCOP 问题，对所有的， (1) ; (2) ; (3) ),(21wwtruePF10, 1 1ww20, 1 2ww; (4) 。11 , 01ww21 , 02ww证明: 采用反证法。(1)如果存在路径满足，则 Dijkstra(1,0)返回的路径将),(21wwP0, 1 1ww 是，而不是。这与事实矛盾。),(21wwP),(0, 1 20, 1
12、1wwP(2) 如果存在路径，使得，则根据（1）的结论可知，因此支配),(21wwP 20, 1 2ww 10, 1 1ww ),(21ww ，这与定理 1 矛盾。 (3)、(4)的证明与(1)、(2)的证明类似，略。),(0, 1 20, 1 1ww作者名 等:题目34 采用 Pareto front 对进行划分2W定义 7 支配区域 向量的支配区域定义为：|。),(21www )(wD),(21ww),(),(2121wwww定义 8 可行区域: =feasibleAfeasibleA)(vDtruePFvU UtruePF定理 4. 如果路由请求约束，则该请求可被满足， 即存在从 s 到
13、 d 能满足约束的路径。),(21ccc feasibleA证明：根据的定义，使得支配，即并且，因此路径feasibleAtruePFv),(21wwv ),(21ccc 11cw 22cw 能够满足请求。前面已经提到，代表的可能不止一条路径，其中的任何一条路径都能够满足路由请)(1vf)(1vf求。 定义 9 不可行区域：=。unfeasibleAunfeasibleAbedomAU10AU01A这里，=|，使得；bedomA),(21wwv truePFv /),(21wwp/v=|x）时，它已经知道由 Dijkstra(x, 1-x)和 Dijkstra(y, 1-y)返回的路径及。PO
14、DWCA 将把区间中点作为权重系数第一个分量的值，并运行 Dijkstra(x+y)/2, 1-(x+y)/2)获得路xPyP径。然后算法判断是否与和的其中之一相同。(1)如果与和的其中之一相同，假设middlePmiddlePxPyPxPyP和是同一条路径，则算法将添加区间(x+y)/2, y到 ITL 的末尾，而忽略区间x, (x+y)/2。因为根据定理middlePxP6，对任何(x, (x+y)/2)，算法 Dijkstra(z, 1-z) 将得到与相同的路径。(2)如果与和都不相同，则zxPmiddlePxPyP记录，并把区间x, (x+y)/2和(x+y)/2, y 添加到 ITL
15、 的末尾。注意，及不会是相同的路径，否则区middlePxPyP间x, y不会被添加到 ITL。每次 PODWCA 处理 ITL 中的第一个元素，并把新区间添加到列表末尾，保证了每 次处理的区间都是 ITL 中最大的。算法处理完区间x, y后， 将其从 ITL 中删除，接着开始处理 ITL 中的下一 个区间。6 性能评估由上面的分析可知，PODWCA 的终止条件是非常灵活的，因此很难估计它的计算复杂性。我们从以下两 个方面来评价 PODWCA 算法的性能和计算复杂性：绝对性能和相对性能。作者名 等:题目56.1 绝对性能我们采用未知区域的大小来评价算法的绝对性能。同时给出了 2EFPA 的绝对性能作为比较。
