结合sce法的粒子群优化qos路由算法

《结合sce法的粒子群优化qos路由算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、结合SCE法的粒子群优化QoS路由算法摘要QoS(QualityofService)路由问题是一个非线性的组合优化问题，理论上已证明了该问题是NP完全问题。粒子群优化算法是一种基于群智能演化计算技术,PSO在求解连续性优化问题上得到了较好的应用，而把PSO算法用于求解路由算法等离散性问题还比较少见，同时，PSO算法在收敛过程中还存在随机性，某些情况下会出现停滞现象。为此本文提出了一种结合SCE（shuffledplexevolution）法的粒子群优化方法用于求解QoS路由问题。该算法通过引入插入算子，删除算子，算子系列和基本算子序列等概念，对基本的粒子群优化算法进行改进；通过采用S

2、CE法，使算法跳出局部最优解的限制。仿真结果显示，该算法取得了满意的效果，在寻优速度上优于遗传算法，也提高了算法收敛到最优解的能力。关键词粒子群优化算法；服务质量；组播路由；遗传算法；洗牌复形进化算法1引言当前随着网络向着数字化，高速化，宽带化的发展，出现了许多新型的多媒体实时应用。如电视会议、视频点播、远程医疗及远程教学等等。这些应用涉及到多个用户并要求一定的服务质量保证，如何在提供业务的前提下保证网络的服务质量成了这些应用能否最终实施的关键。因此，近年来，QoS组播路由算法的研究已成为网络领域中的一类重要研究课题。多QoS参数约束的路由问题是一个非线性的组合优化问题，链路的费用总

3、和，表示为：.令Q1,…,Qn为所有加性的QoS度量，那么整棵组播树T(s,D)的某个QoS度量为该树中所有链路的该QoS度量的总和。表示为：,令QM1,…,QMn为所有凹性的QoS度量（如带宽等）。那么整棵组播树T(s,D)的瓶颈QoS度量则为所有链路中该度量的最小值：,令△1,…△n,为需满足的加性QoS度量约束，为需满足的凹性QoS度量的约束，那么组播多约束QoS路由问题则可定义为：寻找一棵满足以下条件的组播树：(4)4PSO组播路由算法4.1编码及初始化对于使用PSO求解组合优化问题，一般采用实数编码。但对于组播路由问题，采用实数编码使得算法编码、解码过程复杂。为克服编码操作

4、带来的负面影响，所设计的算法采用了节点序列的编码机制，每个个体（即每棵组播树）被编码为源节点到各目标节点的节点系列。如：有n个目标节点，就有n条节点系列，那么PSO的搜索空间也设计成n维的空间，搜索空间的每一维坐标由所有网络节点的排列组合成的序列构成。粒子群的规模根据具体的网络规模和组播成员规模决定，本文在进行初始化原始粒子时，采用了随机深度搜索的方式构造：每棵组播树，由组播源节点到各个目的节点的节点序列构成。从而得到一系列个体，k为群体大小。我们按（7）式计算每个个体Ti(s,D)的适应度fi，并按适应度大小进行排序得到队列：(5)然后按如下规则分成个复形：,每一个复形包含个个体：

5、(6)4.2.适应度函数在所设计的算法中,使用了惩罚函数来处理QoS约束，这样约束优化问题就变成了非约束的优化问题。算法用到的适应度函数设计如下：(7)这里，是正的实数，反映了各QoS参量的重要性。为惩罚函数，r是惩罚的程度。4.3洗牌处理如2.3分析，为了防止停滞现象，本文设计的算法引入了SCE的洗牌处理。其处理如下：首先指定每个复形经过y次迭代后重新进行洗牌，按式（6）进行处理，重新形成P个复形。4.4算法描述出的结合SCE的PSO路由算法的步骤如下：1：编码和初始化，采用随机深度优先的搜索方法随机产生个体。2：根据公式(7)计算每个个体的适应度，并排序，按式（6）把他们分为p个

6、复形。3：每个复形中有各自的个体最优和全局最优，根据公式（3）和（2）计算复形中所有粒子的下一位置，并根据公式(7)计算其适应度，根据适应度值判断，如果某一粒子新的位置优于,则更新值。4：如果存在最优的新位置优于,则用该新位置更新值。5：如果满足结束判据，返回最优解，否则判断是否达到指定的迭代次数y，如果未到达转3继续执行，否则,转2进行重新洗牌处理。5仿真结果本文在PC机上（p4,2.4G,256m）对上述算法进行了仿真试验，仿真使用的网络采用了Salama[13]网络拓扑生成算法来生成。首先，在相同运行条件下，比较了提出的结合SCE的PSO，标准PSO[12]和遗传算法的运行时间

7、。表1各算法运行时间的比较网络规模PSO算法结合sce的PSO算法GA算法200.110.110.12400.200.190.23600.460.420.51801.351.141.511001.751.373.35如表1所示。表中组播规模为网络规模的30%。表中可以看出，SCE的PSO和标准的PSO的运行时间均少于GA算法所需的运行时间，这是由于PSO只在解空间中搜索很小的一部分，因而在全局搜索能力上强于GA，收敛速度也较快。而结合SCE算法的PSO算法