小生境粒子群优化ABC支持型QoS组播路由机制ppt课件.ppt

小生境粒子群优化ABC支持型 QoS组播路由机制 作者：马连博 胡书培 王兴伟 黄敏 主讲人：胡书培 单位：东北大学 目录 1引言与相关工作 问题分析与建模2 18:30:382 组播路由机制描述3 仿真实现与性能评价4 结论及下一步工作5 引言与相关工作 18:30:383 引言与相关工作 u 引言 随着下一代互联网技术的迅速发展以及大量新型网络应用的涌现，特别是认知 网络、物联网、云计算和大数据等新技术的相互融合，用户对网络带宽的需求以及 网络用户数量都急剧增大。除此以外，网络本身所具有的动态性和异构性等特点， 也使得保证端到端的服务质量和为组播用户提供最佳接入方式变得很有挑战性。 当前的ABC支持的路由机制存在着以下三个问题：1）网络的异构和链路参数的 不精确性；2）用户只关心良好的用户体验，对于QoS参数需求难以精确的描述；3） 网络的运营受市场经济规律的支配，网络用户和运营商的效用互相矛盾，难以保证 两者的公平性。 18:30:384 引言与相关工作 u 相关工作 从路由角度来看，ABC支持型路由问题是在多QoS约束下的优化问题。对于此类 问题常用智能优化算法进行求解。比如：小生境蚁群算法、粒子群算法、遗传算 法、植物根系趋向性算法、萤火虫算法等。 u 本文的思想 本文运用模糊数学的方法对不精确的参数进行了处理；通过用户和运营商博弈 ，保证用户和运营商之间的公平性，建立了多目标优化的数学模型；在聚类小生境 粒子群算法基础上，引入Pareto更新机制，设计一种动态Pareto解聚类分析小生境粒 子群算法（Niche particle swarm optimization based on dynamic Pareto cluster algorithm ，NPSODPC）求解该QoS组播路由问题。 18:30:385 问题分析与建模 18:30:386 问题分析与建模 u 问题分析 在给定的网络拓扑G(V,E)中V为节点集，E为边 集，即链路集合。任意两个节点和之间可能存在多 条边，表示从节点到节点可以使用多条不同的通信 链路转发分组，如右图所示。 ABC支持的组播路由问题就可以转化为，在网 络拓扑中寻找一棵满足组播用户给定的QoS需求且 能保证对用户和运营商公平的组播树。 18:30:387 问题分析与建模 u 建立模型 1. 刻画组播QoS请求参数和网络的链路参数 在网络中组播路由的QoS请求可以刻画为6元组 ，其中 为组播的源节点， 为组播目的节点集； 分别 为QoS请求的带宽、延迟、延迟抖动和出错率的约束区间。 为简化问题，对于节点的抖动和处理时延，将其归约到下游的边，这样对于每 条链路就可以给出其带宽、延迟、延迟抖动、出错率的保证区间。 18:30:388 问题分析与建模 2. 运用模糊数学和博弈的方法刻画组播树可信度、用户效用和运营商效用 对于可信度的计算，首先需要确定一个组播用户到源节点的端到端的带宽、延 迟、延迟抖动和出错率的可信度，然后进行加权求和，最终组播树的可信度取决于 源节点到所有组播用户的路径中可信度的最小值。 对于用户效用和运营商效用的计算，应以满足用户QoS需求为前提。对不同的参 数QoS需求区间，比如带宽，首先确定其满意度为低、中、高的三种隶属函数，确定 其隶属度，计算用户的综合满意度；然后分别制定用户和运营商的策略集，结合满 意度和用户偏好计算链路在不同策略对下用户和运营商的效用 ，构成 效应矩阵Q，其中效应矩阵的元素 是用户和运营商在对 应策略对下效用对 。 18:30:389 问题分析与建模 比较矩阵中的所有元素值，找到其中的非支配解集（Pareto最优解集）。如果非 支配解集中元素唯一，该策略对就是用户和运营商博弈的纳什均衡，选择该非支配 解；否则，根据式（1）计算其优先级，选择优先级最高的非支配解。最后将选出的 非支配解对应的策略对作为最佳策略对，其中 为偏向系数： （1） 18:30:3810 问题分析与建模 组播树的可信度如式（2）所示，其中表示源节点s到目的节点d的路径的可信 度；组播树上用户效用如式（3）所示 表示s到d的路径，表示路径上的跳数 ，表示用户u在链路l上的效用；组播树上运营商效用如式（4）所示， 表 示运营商在组播树上的链路数。 （2） （3） （4） 18:30:3911 问题分析与建模 3. 建立多目标模型 组播路由问题的解实际上是一棵在满足QoS需求约束下的包含所有组播目的节点 的树。为支持总最佳链接的特性，考虑用户偏好、网络的异构性和公平性建立如下 多目标模型： （6） （7） （8） （9） 对 18:30:3912 问题分析与建模 对于每一个满足QoS约束的组播树，其适应度计算如式（10）所示， 为可信度 ，为用户在链路l上的满意度， 为l上非支配解的最高优先级， 为系数。 （10） 18:30:3913 组播路由机制描述 18:30:3914 组播路由机制描述 u 解的构成 网络中有m个目的节点，先计算源节点到每个目的节点的备选路径集合，假设有 n条，将他们编号为1,2,n，那么从每个节点的备选路径集中选择一条，消除冗余路 径后就可以构成一颗组播树。按目的节点的顺序选择出的路径序列 作为解的备选，如果它满足QoS约束则就是一个可行解，但不一定最优。 定义解在四个目标上的取值为一个4维向量，用它表示解的质量 。非 支配解是指在存在至少一个维度，在该维度上它优于其他的所有解。定义两个解之 间的距离为，两个解质量的欧氏距离。 如：解与解 的距离如式（11）所示。 （11） 18:30:3915 组播路由机制描述 u 聚类算法 定义满足QoS约束的一个解为粒子，粒子 之间的距离为解之间的距离，然后对粒子群可 以按照右边所示的算法进行聚类。 主要思想：设定聚类半径R，最小聚类规 模M，分别以粒子群C中的每一个粒子为聚类 中心进行聚类，同时记录每个粒子能形成的聚 类规模，每次输出最大的一个子类，同时把输 出后的子类中的粒子从当前种群中排除。不断 迭代，直到无法形成新的子类。 18:30:3916 组播路由机制描述 u PSO算法 设n维空间中的粒子 在t时刻的位置为 ，速度为 ，同理在t+1时刻的位置为 ，速度为 。 的表示形式如 ， 表示s到目的节点j （第j维）的单播路径序号， 的表示形式为 ，其中 表示粒子 第j维上的速度。粒子的速度和位置更新公式 如式（12）（13）所示。 （12） （13） 其中 为惯性权重， 分别为局部认知系数和群体认知系数 ， 为随机数。 分别表示当前的局部最优和全局最优解。 当 时，称为局部最优PSO（Local-best PSO），当 为全 局最优PSO（Global-best PSO）。 18:30:3917 组播路由机制描述 u 动态Pareto解聚类分析小生境粒子群算法 算法 主要分为三部分，首先是初始粒子群的生 成及初始Pareto解集的构建；然后是算法主体 的迭代过程；最后从Pareto解集中输出最优 解。其中迭代过程主要包含4个操作：主粒子 群的Local-best PSO、聚类、子类的Global-best PSO、Pareto边界的更新，算法步骤如右所 示。 18:30:3918 仿真实现与性能评价 18:30:3919 仿真实现与性能评价 u 仿真实验部分 为评估本文提出的路由机制的综合性能，采用SPEA算法作为基准算法，采用自 组织蠕虫算法（Self-Organizing Worm Algorithm, SOWA），小生境遗传算法（Niched Genetic Algorithms，NGA）和作为对比算法进行实例仿真。 仿真程序使用如下四个网络拓扑。它们分别基于美国的NSFNet，中国的CERNET 和CERNET2，以及根据Waxman 的随机图模型生成的30 个节点的随机拓扑。 18:30:3920 图1 NSFNet拓扑图图2 CERNET拓扑图 仿真实现与性能评价 18:30:3921 图3 CERNET2拓扑图图4 随机图模型 u 仿真实验部分 仿真实现与性能评价 u 性能评价部分 评价指标选取路径可信度、用户效用、运营商效用以及用户和运营商综合效用 对不同的算法机制进行对比。 18:30:3922 仿真实现与性能评价 u 性能评价部分 18:30:3923 结论及下一步工作 18:30:3924 结论及下一步工作 区别于当前的单目标处理组播路由的方式，本文综合考虑链路参数不精确、用 户QoS需求不精确和用户与运营商之间的公平性因素，采用模糊数学和博弈论的方法 ，建立了一个保证网络各方效用达到共赢的多目标组播路由模型。为有效求解该模 型，引入动态Pareto更新机制改进了小生境粒子群算法。该算法采用小生境机制保证 解的多样性，结合动态更新Pareto最优解的方法，快速获得大量优质解。最后，基于 NS2平台，对本文提出的路由机制进行了综合的性能指标评价，结果验证了其有效性 与可行性。 下一步工作：对用户的偏好（通信方式、运营商）进行更好的刻画，改进用户 的带宽需求策略和运营商定价策略。 18:30:3925 18:30:3926 谢谢！