1、小生境粒子群优化支持型组播路由机制2022-7-272目录引言与相关工作问题分析与建模组播路由机制描述仿真实现与性能评价结论及下一步工作2022-7-273引言与相关工作2022-7-274引言与相关工作u 引言引言u 随着下一代互联网技术的迅速发展以及大量新型网络应用的涌现，特别随着下一代互联网技术的迅速发展以及大量新型网络应用的涌现，特别是认知网络、物联网、云计算和大数据等新技术的相互融合，用户对网络带宽的是认知网络、物联网、云计算和大数据等新技术的相互融合，用户对网络带宽的需求以及网络用户数量都急剧增大。除此以外，网络本身所具有的动态性和异构需求以及网络用户数量都急剧增大。除此以外，网络
2、本身所具有的动态性和异构性等特点，也使得保证端到端的服务质量和为组播用户提供最佳接入方式变得很性等特点，也使得保证端到端的服务质量和为组播用户提供最佳接入方式变得很有挑战性。有挑战性。u 当前的支持的路由机制存在着以下三个问题：）网络的异构和链路参数当前的支持的路由机制存在着以下三个问题：）网络的异构和链路参数的不精确性；）用户只关心良好的用户体验，对于参数需求难以精确的描述；）的不精确性；）用户只关心良好的用户体验，对于参数需求难以精确的描述；）网络的运营受市场经济规律的支配，网络用户和运营商的效用互相矛盾，难以保网络的运营受市场经济规律的支配，网络用户和运营商的效用互相矛盾，难以保证两者的
3、公平性。证两者的公平性。2022-7-275引言与相关工作u 相关工作相关工作u 从路由角度来看，支持型路由问题是在多约束下的优化问题。对于此类问题常用从路由角度来看，支持型路由问题是在多约束下的优化问题。对于此类问题常用智能优化算法进行求解。比如：小生境蚁群算法、粒子群算法、遗传算法、植物智能优化算法进行求解。比如：小生境蚁群算法、粒子群算法、遗传算法、植物根系趋向性算法、萤火虫算法等。根系趋向性算法、萤火虫算法等。u 本文的思想本文的思想u 本文运用模糊数学的方法对不精确的参数进行了处理；通过用户和运营商博弈，本文运用模糊数学的方法对不精确的参数进行了处理；通过用户和运营商博弈，保证用户和
4、运营商之间的公平性，建立了多目标优化的数学模型；在聚类小生境保证用户和运营商之间的公平性，建立了多目标优化的数学模型；在聚类小生境粒子群算法基础上，引入更新机制，设计一种动态解聚类分析小生境粒子群算法粒子群算法基础上，引入更新机制，设计一种动态解聚类分析小生境粒子群算法（，）求解该组播路由问题。，）求解该组播路由问题。2022-7-276问题分析与建模2022-7-277问题分析与建模u 问题分析问题分析u 在给定的网络拓扑在给定的网络拓扑()()中为节点集，为边集，即链中为节点集，为边集，即链路集合。任意两个节点和之间可能存在多条边，路集合。任意两个节点和之间可能存在多条边，表示从节点到节点
5、可以使用多条不同的通信链路表示从节点到节点可以使用多条不同的通信链路转发分组，如右图所示。转发分组，如右图所示。u 支持的组播路由问题就可以转化为，在网络拓扑支持的组播路由问题就可以转化为，在网络拓扑中寻找一棵满足组播用户给定的需求且能保证对中寻找一棵满足组播用户给定的需求且能保证对用户和运营商公平的组播树。用户和运营商公平的组播树。2022-7-278问题分析与建模u 建立模型建立模型u.刻画组播请求参数和网络的链路参数刻画组播请求参数和网络的链路参数u 在网络中组播路由的请求可以刻画为元组在网络中组播路由的请求可以刻画为元组 ，其中其中 为组播的源节点，为组播的源节点，为组播目的节点集；为
6、组播目的节点集；分别为请求的带宽、延迟、延迟抖动和出错率的约束区间。分别为请求的带宽、延迟、延迟抖动和出错率的约束区间。u 为简化问题，对于节点的抖动和处理时延，将其归约到下游的边，这样对于每条为简化问题，对于节点的抖动和处理时延，将其归约到下游的边，这样对于每条链路就可以给出其带宽、延迟、延迟抖动、出错率的保证区间。链路就可以给出其带宽、延迟、延迟抖动、出错率的保证区间。BDJE,s D sDBDJE,2022-7-279问题分析与建模.运用模糊数学和博弈的方法刻画组播树可信度、用户效用和运营商效用对于可信度的计算，首先需要确定一个组播用户到源节点的端到端的带宽、延迟、延迟抖动和出错率的可信
7、度，然后进行加权求和，最终组播树的可信度取决于源节点到所有组播用户的路径中可信度的最小值。对于用户效用和运营商效用的计算，应以满足用户需求为前提。对不同的参数需求区间，比如带宽，首先确定其满意度为低、中、高的三种隶属函数，确定其隶属度，计算用户的综合满意度；然后分别制定用户和运营商的策略集，结合满意度和用户偏好计算链路在不同策略对下用户和运营商的效用 ，构成效应矩阵，其中效应矩阵的元素 是用户和运营商在对应策略对下效用对。,ijijijqab,ijijab2022-7-2710问题分析与建模比较矩阵中的所有元素值，找到其中的非支配解集（最优解集）。如果非支配解集中元素唯一，该策略对就是用户和运
8、营商博弈的纳什均衡，选择该非支配解；否则，根据式（）计算其优先级，选择优先级最高的非支配解。最后将选出的非支配解对应的策略对作为最佳策略对，其中 为偏向系数：（）111priijijijabl,2022-7-2711问题分析与建模组播树的可信度如式（）所示，其中表示源节点到目的节点的路径的可信度；组播树上用户效用如式（）所示 表示到的路径，表示路径上的跳数，表示用户在链路上的效用；组播树上运营商效用如式（）所示，表示运营商在组播树上的链路数。（）（）（）min,|s DTdRRdDUsershopddlulPTPdDdDdUUUP ISPISPcount=isplisplTTisp TispU
9、UTdRdPhopdPluUcountispT2022-7-2712问题分析与建模 建立多目标模型组播路由问题的解实际上是一棵在满足需求约束下的包含所有组播目的节点的树。为支持总最佳链接的特性，考虑用户偏好、网络的异构性和公平性建立如下多目标模型：（）（）（）（）对,maxs DTRUsersmaxTUISPmaxTUUsersISPmaxTTUU,.dD s tlowBPB highDPD highJPJ highEPE 2022-7-2713问题分析与建模对于每一个满足约束的组播树，其适应度计算如式（）所示，为可信度，为用户在链路上的满意度，为上非支配解的最高优先级，为系数。（）prina
10、shfitdegree1l TTijRllTlTRdegreelpriijlnashl2022-7-2714组播路由机制描述2022-7-2715组播路由机制描述u 解的构成解的构成u 网络中有个目的节点，先计算源节点到每个目的节点的备选路径集合，假设有条，网络中有个目的节点，先计算源节点到每个目的节点的备选路径集合，假设有条，将他们编号为将他们编号为,，那么从每个节点的备选路径集中选择一条，消除冗余路径后就，那么从每个节点的备选路径集中选择一条，消除冗余路径后就可以构成一颗组播树。按目的节点的顺序选择出的路径序列可以构成一颗组播树。按目的节点的顺序选择出的路径序列 u 作为解的备选，如果它满
11、足约束则就是一个可行解，但不一定最优。作为解的备选，如果它满足约束则就是一个可行解，但不一定最优。u 定义解在四个目标上的取值为一个维向量，用它表示解的质量定义解在四个目标上的取值为一个维向量，用它表示解的质量 。非支。非支配解是指在存在至少一个维度，在该维度上它优于其他的所有解。定义两个解之配解是指在存在至少一个维度，在该维度上它优于其他的所有解。定义两个解之间的距离为，两个解质量的欧氏距离。间的距离为，两个解质量的欧氏距离。u 如：解如：解与解与解 的距离如式（）所示。的距离如式（）所示。u（）（）12()()(),.,mpppqualityT T1234,XXXXX1234,XXXXX4
12、21iiidXXX,X2022-7-2716组播路由机制描述u 聚类算法聚类算法u 定义满足约束的一个解为粒子，粒子之间定义满足约束的一个解为粒子，粒子之间的距离为解之间的距离，然后对粒子群可的距离为解之间的距离，然后对粒子群可以按照右边所示的算法进行聚类。以按照右边所示的算法进行聚类。u 主要思想：设定聚类半径，最小聚类规模，主要思想：设定聚类半径，最小聚类规模，分别以粒子群中的每一个粒子为聚类中心分别以粒子群中的每一个粒子为聚类中心进行聚类，同时记录每个粒子能形成的聚进行聚类，同时记录每个粒子能形成的聚类规模，每次输出最大的一个子类，同时类规模，每次输出最大的一个子类，同时把输出后的子类中
13、的粒子从当前种群中排把输出后的子类中的粒子从当前种群中排除。不断迭代，直到无法形成新的子类。除。不断迭代，直到无法形成新的子类。2022-7-2717组播路由机制描述u 算法算法u 设维空间中的粒子设维空间中的粒子 在时刻的位置为在时刻的位置为 ，速度为，速度为 ，同理在时刻的位，同理在时刻的位置为置为 ，速度为，速度为 。的表示形式如的表示形式如 ，表示到目的节点（第维）的单播路径序号，表示到目的节点（第维）的单播路径序号，的表示形式的表示形式为为 ，其中，其中 表示粒子表示粒子 第维上的速度。粒第维上的速度。粒子的速度和位置更新公式如式（）（）所示。子的速度和位置更新公式如式（）（）所示。
14、（）（）u（）（）u 其中其中 为惯性权重，为惯性权重，分别为局部认知系数和群体认知系数分别为局部认知系数和群体认知系数，为为随机数。随机数。分别表示当前的局部最优和全局最优解。分别表示当前的局部最优和全局最优解。u 当当 时，称为局部最优（时，称为局部最优（），当），当 为全局最优（为全局最优（）。）。12()()(),.,mpppix()ix t()iv t1()ix t 1()iv t ix()jp()iv t12,(),(),.,()iii mvtvtvt,()i jvtix11()()()iiix tx tv t1 12 21,()()()()()()()()iiiiiiiiv tw
15、v tc rty tx tc rty tx tw12,c c12,(),()iirtrt20c10c(),()iiy ty t2022-7-2718组播路由机制描述u 动态解聚类分析小生境粒子群算法算法动态解聚类分析小生境粒子群算法算法u 主要分为三部分，首先是初始粒子群的生主要分为三部分，首先是初始粒子群的生成及初始解集的构建；然后是算法主体的成及初始解集的构建；然后是算法主体的迭代过程；最后从解集中输出最优解。其迭代过程；最后从解集中输出最优解。其中迭代过程主要包含个操作：主粒子群的中迭代过程主要包含个操作：主粒子群的 、聚类、子类的聚类、子类的 、边界的更新，算法步骤如、边界的更新，算法
16、步骤如右所示。右所示。2022-7-2719仿真实现与性能评价2022-7-2720仿真实现与性能评价u 仿真实验部分仿真实验部分u 为评估本文提出的路由机制的综合性能，采用算法作为基准算法，采用自组织蠕为评估本文提出的路由机制的综合性能，采用算法作为基准算法，采用自组织蠕虫算法（虫算法（,），小生境遗传算法（），小生境遗传算法（，）和作为对比算法进行实例仿真。，）和作为对比算法进行实例仿真。u 仿真程序使用如下四个网络拓扑。它们分别基于美国的，中国的和，以及根据仿真程序使用如下四个网络拓扑。它们分别基于美国的，中国的和，以及根据 的的随机图模型生成的随机图模型生成的 个节点的随机拓扑。个节点
17、的随机拓扑。u图 拓扑图图 拓扑图2022-7-2721仿真实现与性能评价图 拓扑图图 随机图模型u 仿真实验部分仿真实验部分2022-7-2722仿真实现与性能评价u 性能评价部分性能评价部分u 评价指标选取路径可信度、用户效用、运营商效用以及用户和运营商综合效用对评价指标选取路径可信度、用户效用、运营商效用以及用户和运营商综合效用对不同的算法机制进行对比。不同的算法机制进行对比。u2022-7-2723仿真实现与性能评价u 性能评价部分性能评价部分u2022-7-2724结论及下一步工作2022-7-2725结论及下一步工作区别于当前的单目标处理组播路由的方式，本文综合考虑链路参数不精确、用户需求不精确和用户与运营商之间的公平性因素，采用模糊数学和博弈论的方法，建立了一个保证网络各方效用达到共赢的多目标组播路由模型。为有效求解该模型，引入动态更新机制改进了小生境粒子群算法。该算法采用小生境机制保证解的多样性，结合动态更新最优解的方法，快速获得大量优质解。最后，基于平台，对本文提出的路由机制进行了综合的性能指标评价，结果验证了其有效性与可行性。下一步工作：对用户的偏好（通信方式、运营商）进行更好的刻画，改进用户的带宽需求策略和运营商定价策略。2022-7-2726谢谢！
