结合SCE法的粒子群优化QoS路由算法(1)

摘  要  QoS (Quality of Service) 路由问题是一个非线性的组合优化问题，理论上已证明了该问题是NP完全问题。粒子群优化算法是一种基于群智能演化计算技术,PSO在求解连续性优化问题上得到了较好的应用，而把PSO算法用于求解路由算法等离散性问题还比较少见，同时，PSO算法在收敛过程中还存在随机性，某些情况下会出现停滞现象。为此本文提出了一种结合SCE（shuffled complex evolution）法的粒子群优化方法用于求解QoS路由问题。该算法通过引入插入算子，删除算子，算子系列和基本算子序列等概念，对基本的粒子群优化算法进行改进；通过采用SCE法，使算法跳出局部最优解的限制。仿真结果显示，该算法取得了满意的效果，在寻优速度上优于遗传算法，也提高了算法收敛到最优解的能力。

关键词  粒子群优化算法；服务质量；组播路由；遗传算法；洗牌复形进化算法

 

      当前随着网络向着数字化，高速化，宽带化的发展，出现了许多新型的多媒体实时应用。如电视会议、视频点播、远程医疗及远程教学等等。这些应用涉及到多个用户并要求一定的服务质量保证，如何在提供业务的前提下保证网络的服务质量成了这些应用能否最终实施的关键。因此，近年来，QoS组播路由算法的研究已成为网络领域中的一类重要研究课题。  

     多QoS参数约束的路由问题是一个非线性的组合优化问题，文献【1】已证明了, 基于多个不相关可加度量的QoS路由问题是NP完全问题。近年来，研究者对此类问题作了大量的研究工作，提出了多种解决方法，如模拟退火，禁忌搜索，神经网络，遗传算法等^[2-6]。目前，一类新兴的模拟生物群体行为的集群智能算法被引入到此类优化问题中，如：蚁群优化算法^[8]和粒子群优化算法^[7]（PSO）等。

      PSO是一种基于群智能的演化计算技术。PSO最早由Kennedy 和 Eberhart受人工生命研究结果的启发在1995年提出的^[10]。其基本概念源自鸟群捕食行为的研究。PSO算法在连续性问题上取得了较为满意的效果，但在离散问题，NP完全问题方面研究得较少^[9]，特别是用PSO求解QoS路由问题是一个新的研究方向。另外，PSO算法存在着易于陷入“停滞”阶段的缺点，为此本文提出了一种结合SCE（shuffled complex evolution）算法的PSO求解QoS路由问题的算法，仿真结果显示了该算法的有效和可行性。

      基本PSO的原理是: 每个优化问题的解都是粒子在搜索空间中的位置，粒子的速度值决定它们飞翔的方向和距离，粒子群追随当前的最优粒子在解空间中搜索。

      在D维的搜索空间中，有随机分布的m个粒子组成的一个初始粒子群，每个粒子有各自的位置和速度。如第i个粒子的位置表示为一个D维的向量 ,速度也是一个D维的向量，记为 。每个粒子记住自己在迭代过程中找到的最优位置，记为 ，整个粒子群迄今为止搜索到的最优位置为全局最优解，记为 。在算法的初期，为了避免搜索过早陷入局部最优解，把粒子群按空间划分为几个区域，而用局部区域的极值粒子代替全局最优解。这样的寻优为局部PSO算法，经过一定的迭代后，改用全局最优解，即全局PSO算法进行迭代以加快收敛。整个粒子群通过选定个体的 和 来更新自身的位置和速度：

  (1)

                             (2)

       这里，学习因子C₁，C₂是非负常数，他们决定, 的影响程度，r₁ ， r₂是介于【0，l】之间的随机数。迭代中止条件根据具体问题一般选为最大迭代次数或(和)粒子群迄今为止搜索到的最优位置满足预定最小适应阈值。

      SCE（shuffled complex evolution ）是一种相对较新的连续性问题的元启发搜索算法^[11]。非常适合于求解具有多个局部最小的全局优化问题。它主要基于如下概念：

      结合了随机性和确定性算法；

      参数空间中的多点组成的复形进行系统进化；

      复形中的竞争进化；

      构成复形的点的重新洗牌。

      SCE算法的处理过程如下：首先，随机地从问题空间中选定一系列点（或者称为个体），这里，n是问题空间的维数。这些个体分别构成p个复形，每个复形由m个点构成。P和m是用户定义的参数，他们决定了群体的大小s，即s=mp。每个复形独立地采用下山单纯形法（Nelder and Mead，1965）进行迭代进化。为了实现信息的共享，这些复形会定期进行洗牌（shuffled）处理，然后形成新的复形。如此，进化和洗牌重复进行直到满足预先指定的收敛准则。SCE算法的主要特征是通过竞争进化和定期洗牌来确保每个复形获得的信息能在整个问题空间获得共享。

      研究发现^[14]，基本PSO粒子的位置是在本粒子前一最优位置和全局最优位置之间以减幅正弦波方式振荡的，如果在这一过程中，粒子经过的位置比前一最优位置要好，那么粒子将继续移动，通常收敛到目前找到的全局最优位置，所有的粒子跟随这一相同行为，很快聚集到一个本地最优解。然而，如果全局最优解不是刚好存在于初始粒子与这个本地最优解之间的位置的话，那么大部分粒子均被相同的本地最优解所限制，算法将出现暂时的停滞现象，需要经过很长的一段时间才能突破这个本地最优解的限制。那么，大多数粒子将浪费大量的计算时间在寻找和移动到局部最优的方向上。为了克服这种现象，我们采用结合了SCE 的PSO算法。

      我们在每个复形中不是采用下山法，而是采用PSO算法。从而利用洗牌的处理，保证每个复形的多样性，利于算法跳出停滞阶段。

      为了能使我们提出的结合SCE的PSO算法应用到求解QoS路由的离散性问题上，我们做如下改进：

       首先我们定义如下几个概念：插入算子，删除算子，

算子序列和基本算子序列。

       ■ 插入算子

       对于一条QoS单播路由，用其经过的节点序列表示为 R=(Ni) i=1,…,n; 因此定义的插入算子INS(i1,k)如下：

       定义1: 如果用插入算子INS(i1，k)作用于路由R，那么其结果为：在网络中搜寻一条从路由的第i1-1个节点N(i1-1)到节点k的不包含源节点的最短费用路径，插入到路由的第i1个节点Ni1前，然后,再在网络中寻找一条从节点k到节点Ni1的不包含源节点的最短费用路径，插入到Ni1前，并删除节点Ni1。

      如果网络中节点N(i1-1)到节点k不存在连通的路径，则扩大为节点N(i1-2)到节点k，以此类推，直到找到或到达路由源节点为止。

同理，如果网络中节点k到节点Ni1, 不存在连通的路径，则扩大为节点k到节点N(i1+1)，以此类推，直到找到或到达路由终节点为止。

图1. 随机生成的15 节点网络拓扑结构

 

例1：如图1中：单播路由R=(3，7，11，8),那么R’=R+ INS(3，4)的结果是，寻找一条从R的第3个节点11到节点4的最短费用路径(11,9,4)，然后再寻找节点4到节点8的的最短路径（4，8），插入并删除节点8，最后得到的路径为（3，7，11，9，4，8）。

       ■删除算子

       定义2: 如果用删除算子DEL(i1)作用于路由R，那么其结果为：在网络中搜寻一条从节点N(i1-1)到节点N(i1+1)的不包含节点Ni1的最短费用路径，然后用它替代路由中N(i1-1)，Ni1和N(i1+1)三个节点。如果节点N(i1-1)到节点N(i1+1)不存在连通的路径,扩大为N(i1-2,i1+1)，如果仍找不到再扩大为N(i1-1,i1+2)，以此类推直到找到一条可替代的路径为止。

       例2：如图1中：单播路由R=(3，7，11，9，8),那么R’= R+ DEL (4)的结果是，寻找一条节点11到8的最短费用路径(11,8)，替代11，9，8，最后得到的路径为（3，7，11，8）。

       ■算子序列

       定义3：如果有多个算子作用于一条路由，那么由这些算子组成的序列称为算子序列。

如算子序列OS={INS1, INS2, DEL1}。这里，对各算子的先后顺序是敏感的。

       ■ 基本算子序列

       定义4：不同的算子序列作用于同一条路由，有可能得到相同的结果，把有最少操作的算子序列称为基本算子序列。

      根据上面的定义我们设定基本算子序列的构造的准则：

假设有两条路由R1,R2。这里的目标是如何构造基本算子序列，使之作用于R2从而得到R1。定义SS=R1-R2,从而，R2=R1+OS。

      构造的基本规则是：首先对齐节点数，如果节点数少，则选择插入算子，如果节点数多，则选择删除算子，如果相等且有不同的节点，则随机选择插入或删除算子。

      如图1中： 路由B={3,1,4,8},路由A={3,7,11,9,8}，求OS=A-B。首先是对齐节点数，路由A中 的第2个节点7在路由B中不存在，因此可考虑插入算子INS(2,7)，有B1=B+INS(2,7) ,此时路由在3和7之间寻找到最短费用路径（3,7），7和4之间不经过源节点的最短费用路径为(7,11,8,4)，替换后得到B1=(3,7,11,8,4,8)。删除相同节点间的路径得B1=(3,7,11,,8)。

此时，B1的节点数仍小于A，路由A中 的第4个节点9在路由A中仍不存在因此考虑INS(4,9)，根据插入算子的定义，最后得到B2=B1+INC(4,9)=(3,7,11,9,8)=A。因此得到基本算子：

OS=A-B={INS(2,7),INS(4,9)}。

       ■更新位置和速度

       由于不再采用实数编码方式，因此公式(1)不再满足要求。根据上面的讨论，作如下修改：

 (3)

这里r₁， r₂, 是介于【O，l】之间的随机数，符号 定义为：合并两个算子序列并把他们转换为基本算子序列的操作。的含义是基本算子序列 以r₁的概率保留下来。 具有类似的含义。r₁ , r₂的大小决定了 和 的影响程度。

      通过上述设计，我们就得到了适合于路由算法的离散形式的结合SCE的PSO算法。

3．QoS路由的数学模型

      不失一般性,把通信网看成一个有向连通图G(V,E)， ，其中Ｖ为节点集合，Ｅ为图中连接两个节点的链路的集合，每条链路 e(u,v)∈E和一些QoS度量相关，这些度量包括：费用、延时、可用带宽和抖动等。这里用函数C（e）代表费用，它反映了支持QoS而需要的资源总数，它可以是金钱上的也可以是关于资源的其他任何度量。其他的QoS度量用Q_i(e)来表示。

      组播路由问题就是要找到一棵组播斯坦立树：T(s,D) 这里s ∈V 是组播应用的数据源节点，是一组目的节点D = { , … , },{s} ∪D是组播组。给定一个组播斯坦立树，令P(s,d_i)代表源节点s和一个目标节点d_i之间经过的路径，那么组播树 T(s,D)中的所有路径可以表示为 。从源节点s到某一目标节点d_i 的费用可表示为： ,那么组播树T(s,D) 的总的费用即为所有