仿真实验部分自强不息，知行合一

1 .小生境粒子群优化 ABC 支持型 QoS 组播路由机制 作者：马连博 胡书培 王兴伟 黄敏 主讲人：胡书培 单位：东北大学 

2 .目录 1 引言与相关工作 2 问题分析与建模 3 组播路由机制描述 4 仿真实现与性能评价 5 结论及下一步工作 23:22:50 2 

3 . 引言与相关工作 23:22:50 3 

4 .引言与相关工作  引言 随着下一代互联网技术的迅速发展以及大量新型网络应用的涌现，特别是认知 网络、物联网、云计算和大数据等新技术的相互融合，用户对网络带宽的需求以及 网络用户数量都急剧增大。除此以外，网络本身所具有的动态性和异构性等特点， 也使得保证端到端的服务质量和为组播用户提供最佳接入方式变得很有挑战性。 当前的 ABC 支持的路由机制存在着以下三个问题： 1 ）网络的异构和链路参 数的不精确性； 2 ）用户只关心良好的用户体验，对于 QoS 参数需求难以精确的描 述； 3 ）网络的运营受市场经济规律的支配，网络用户和运营商的效用互相矛盾， 难以保证两者的公平性。 23:22:50 4 

5 .引言与相关工作  相关工作 从路由角度来看， ABC 支持型路由问题是在多 QoS 约束下的优化问题。对于此 类问题常用智能优化算法进行求解。比如：小生境蚁群算法、粒子群算法、遗传算 法、植物根系趋向性算法、萤火虫算法等。  本文的思想 本文运用模糊数学的方法对不精确的参数进行了处理；通过用户和运营商博弈 ，保证用户和运营商之间的公平性，建立了多目标优化的数学模型；在聚类小生境 粒子群算法基础上，引入 Pareto 更新机制，设计一种动态 Pareto 解聚类分析小生境 粒子群算法（ Niche particle swarm optimization based on dynamic Pareto cluster algorithm ， NPSODPC ）求解该 QoS 组播路由问题。 23:22:50 5 

6 . 问题分析与建模 23:22:50 6 

7 .问题分析与建模  问题分析 在给定的网络拓扑 G(V,E) 中 V 为节点集， E 为 边集，即链路集合。任意两个节点和之间可能存在 多条边，表示从节点到节点可以使用多条不同的通 信链路转发分组，如右图所示。 ABC 支持的组播路由问题就可以转化为，在网 络拓扑中寻找一棵满足组播用户给定的 QoS 需求且 能保证对用户和运营商公平的组播树。 23:22:50 7 

8 .问题分析与建模  建立模型 1. 刻画组播 QoS 请求参数和网络的链路参数  在网络中组播路由的 QoS 请求可以刻画为 6 元组 s, D,  B ,  D ,  J ,  E  s，其中 D 为组播的源节点， B , D , J , E 为组播目的节点集； 分别为 QoS 请求的带宽、 延迟、延迟抖动和出错率的约束区间。 为简化问题，对于节点的抖动和处理时延，将其归约到下游的边，这样对于每 条链路就可以给出其带宽、延迟、延迟抖动、出错率的保证区间。 23:22:50 8 

9 .问题分析与建模 2. 运用模糊数学和博弈的方法刻画组播树可信度、用户效用和运营商效用 对于可信度的计算，首先需要确定一个组播用户到源节点的端到端的带宽、延 迟、延迟抖动和出错率的可信度，然后进行加权求和，最终组播树的可信度取决于 源节点到所有组播用户的路径中可信度的最小值。 对于用户效用和运营商效用的计算，应以满足用户 QoS 需求为前提。对不同的 参数 QoS 需求区间，比如带宽，首先确定其满意度为低、中、高的三种隶属函数， 确定其隶属度，计算用户的综合满意度；然后分别制定用户和运营商的策略集，结 aij , bij 合满意度和用户偏好计算链路在不同策略对下用户和运营商的效用 ，构成效 qij   aij , bij  应矩阵 Q ，其中效应矩阵的元素 是用户和运营商在对应策略对下效 用对 。 23:22:50 9 

10 .问题分析与建模 比较矩阵中的所有元素值，找到其中的非支配解集（ Pareto 最优解集）。如果 非支配解集中元素唯一，该策略对就是用户和运营商博弈的纳什均衡，选择该非支 配解；否则，根据式（ 1 ）计算其优先级，选择优先级最高的非支配解。最后将选 出的非支配解对应的策略对作为最佳策略对，其中 ,  为偏向系数： 1 lij  pri 1 （ 1 ）1     aij bij 23:22:50 10 

11 .问题分析与建模 组播树的可信度如式（ 2 ）所示，其中R 表示源节点 s 到目的节点 d 的路径的可 d 信度；组播树上用户效用如式（ 3 ）所示 P 表示 s 到 d 的路径，表示路径上的跳 Pd d hop 数，U ul 表示用户 u 在链路 l 上的效用；组播树上运营商效用如式（ 4 ）所示， T count isp 表示运营商在组播树上的链路数。 （2） RT  s , D   min Rd | d  D     U u l    l  Pd UT  U（  P 3 ）   Users d  D d d D  Pdhop     l U isp  lisp T UT = （4） count ISP ispTISP T isp 23:22:50 11 

12 .问题分析与建模 3.建立多目标模型 组播路由问题的解实际上是一棵在满足 QoS 需求约束下的包含所有组播目的节 点的树。为支持总最佳链接的特性，考虑用户偏好、网络的异构性和公平性建立如 下多目标模型： max RT   （6） s ,D  max  U T  （7） Users  max U TISP  （8）  max U TUsers  U T （ 9 ） ISP 对 d  D, s.t . low BP   B high DP   D high J P  J high EP   E 23:22:50 12 

13 .问题分析与建模 对于每一个满足 QoS 约束的组播树，其适应度计算如式（ 10 ）所示， RT 为可 信度， ldegree 为用户在链路 l 上的满意度，lij 为 l 上非支配解的最高优先级， lnash 为系数 pri 。 1 lnash Tfit  RT l l T  lij degree pri （ 10 ） 23:22:51 13 

14 . 组播路由机制描述 23:22:51 14 

15 .组播路由机制描述  解的构成 网络中有 m 个目的节点，先计算源节点到每个目的节点的备选路径集合，假设 有 n 条，将他们编号为 1,2,…,n ，那么从每个节点的备选路径集中选择一条，消除  p( 1) , p( 2) , . . . , p( m)  冗余路径后就可以构成一颗组播树。按目的节点的顺序选择出的路径序列 作为解的备选，如果它满足 QoS 约束则就是一个可行解，但不一定最优。 定义解在四个目标上的取值为一个 4 维向量，用它表示解的质量Tquality 。非支 配解是指在存在至少一个维度，在该维度上它优于其他的所有解。定义两个解之间 的距离为，两个解质量的欧氏距离。 如：解  与解 X X1, X 2 , X 3 , X 4   的距离如式（  11 ）所示。 X  X 1, X 2 , X 3 , X 4 4   X（11 X ） 2 d X, X   i i i 1 23:22:51 15 

16 .组播路由机制描述  聚类算法 定义满足 QoS 约束的一个解为粒子，粒 子之间的距离为解之间的距离，然后对粒子群 可以按照右边所示的算法进行聚类。 主要思想：设定聚类半径 R ，最小聚类 规模 M ，分别以粒子群 C 中的每一个粒子为 聚类中心进行聚类，同时记录每个粒子能形成 的聚类规模，每次输出最大的一个子类，同时 把输出后的子类中的粒子从当前种群中排除。 不断迭代，直到无法形成新的子类。 23:22:51 16 

17 .组播路由机制描述  PSO 算法 x xi( t ) vi( t ) 设 n 维空间中的粒子 i 在 t 时刻的位置为 ，速度为 ，同理在 。  的表示形式如 xi( t  1)  1) vi( t ，速度为 xi p( 1) , p( 2) , . . . , p( m )  p( j ) t+1 时刻的位置为 ， 表示 s 到目的节点 j （第 vi( t ) j 维）的单播路径序号，  v ( t ) , v ( t ) ,的表示形式. . . , v ( t)  i ,1 i, 2 i, m 为 vi , j( t ) xi ，其中 表示粒子 第 j 维上的速度。粒 xi( t  1)12 子的速度和位置更新公式如式（  ）（  v）所示。 xi( t ) 13 i ( t  1) （v12 ( t ）1)  wvi( t )  c1r1,i( t ) [ yi( t )  xi( t ) ]  c2 r2,i( t ) [ yˆi( t )  xi( t ) ] i w c1 , c2 （ 13 ） r1,i( t ) , r2, i( t ) yi( t ) , yˆi( t ) 其中 为惯性权重， 分别为局部认知系数和群体认知系数 ， c2  0 为随机数。 c1  0 分别表示当前的局部最优和全局最优解。 当 时，称为局部最优 PSO （ Local-best PSO ），当 为全局 最优 PSO （ Global-best PSO ）。 23:22:51 17 

18 .组播路由机制描述  动态 Pareto 解聚类分析小生境粒子群算 法算法 主要分为三部分，首先是初始粒子群的生 成及初始 Pareto 解集的构建；然后是算法主 体的迭代过程；最后从 Pareto 解集中输出最 优解。其中迭代过程主要包含 4 个操作：主 粒子群的 Local-best PSO 、聚类、子类的 Global-best PSO 、 Pareto 边界的更新，算法 步骤如右所示。 23:22:51 18 

19 . 仿真实现与性能评价 23:22:51 19 

20 .仿真实现与性能评价  仿真实验部分 为评估本文提出的路由机制的综合性能，采用 SPEA 算法作为基准算法，采用自 组织蠕虫算法（ Self-Organizing Worm Algorithm, SOWA ），小生境遗传算法 （ Niched Genetic Algorithms ， NGA ）和作为对比算法进行实例仿真。 仿真程序使用如下四个网络拓扑。它们分别基于美国的 NSFNet ，中国的 CERNET 和 CERNET2 ，以及根据 Waxman 的随机图模型生成的 30 个节点的随机拓 扑。 图 1 NSFNet 拓扑 图 2 CERNET 拓扑 23:22:51 图 图 20 

21 .仿真实现与性能评价  仿真实验部分 图 3 CERNET2 拓 图4 随机图模 扑图 型 23:22:51 21 

22 .仿真实现与性能评价  性能评价部分 评价指标选取路径可信度、用户效用、运营商效用以及用户和运营商综合效用 对不同的算法机制进行对比。 23:22:51 22 

23 .仿真实现与性能评价  性能评价部分 23:22:51 23 

24 . 结论及下一步工作 23:22:51 24 

25 .结论及下一步工作 区别于当前的单目标处理组播路由的方式，本文综合考虑链路参数不精确、用 户 QoS 需求不精确和用户与运营商之间的公平性因素，采用模糊数学和博弈论的方 法，建立了一个保证网络各方效用达到共赢的多目标组播路由模型。为有效求解该 模型，引入动态 Pareto 更新机制改进了小生境粒子群算法。该算法采用小生境机制 保证解的多样性，结合动态更新 Pareto 最优解的方法，快速获得大量优质解。最后 ，基于 NS2 平台，对本文提出的路由机制进行了综合的性能指标评价，结果验证了 其有效性与可行性。 下一步工作：对用户的偏好（通信方式、运营商）进行更好的刻画，改进用户 的带宽需求策略和运营商定价策略。 23:22:51 25 

26 . 谢谢！ 23:22:51 26