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

摘  要  QoS (Quality of Service) 路由问题是一个非线性的组合优化问题，理论上已证明了该问题是NP完全问题。粒子群优化算法是一种基于群智能演化技术,PSO在求解连续性优化问题上得到了较好的应用，而把PSO算法用于求解路由算法等离散性问题还比较少见，同时，PSO算法在收敛过程中还存在随机性，某些情况下会出现停滞现象。为此本文提出了一种结合SCE（shuffled complex evolution）法的粒子群优化方法用于求解QoS路由问题。该算法通过引入插入算子，删除算子，算子系列和基本算子序列等概念，对基本的粒子群优化算法进行改进；通过采用SCE法，使算法跳出局部最优解的限制。仿真结果显示，该算法取得了满意的效果，在寻优速度上优于遗传算法，也提高了算法收敛到最优解的能力。关键词  粒子群优化算法；服务质量；组播路由；遗传算法；洗牌复形进化算法 
1  引言       当前随着向着数字化，高速化，宽带化的，出现了许多新型的多媒体实时应用。如电视会议、视频点播、远程医疗及远程教学等等。这些应用涉及到多个用户并要求一定的服务质量保证，如何在提供业务的前提下保证网络的服务质量成了这些应用能否最终实施的关键。因此，近年来，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路由问题的算法，仿真结果显示了该算法的有效和可行性。2 基本概念2.1 基本PSO算法      基本PSO的原理是: 每个优化问题的解都是粒子在搜索空间中的位置，粒子的速度值决定它们飞翔的方向和距离，粒子群追随当前的最优粒子在解空间中搜索。      在D维的搜索空间中，有随机分布的m个粒子组成的一个初始粒子群，每个粒子有各自的位置和速度。如第i个粒子的位置表示为一个D维的向量 ,速度也是一个D维的向量，记为 。每个粒子记住自己在迭代过程中找到的最优位置，记为 ，整个粒子群迄今为止搜索到的最优位置为全局最优解，记为 。在算法的初期，为了避免搜索过早陷入局部最优解，把粒子群按空间划分为几个区域，而用局部区域的极值粒子代替全局最优解。这样的寻优为局部PSO算法，经过一定的迭代后，改用全局最优解，即全局PSO算法进行迭代以加快收敛。整个粒子群通过选定个体的 和 来更新自身的位置和速度：  (1)                             (2)       这里，学习因子C₁，C₂是非负常数，他们决定, 的影响程度，r₁ ， r₂是介于【0，l】之间的随机数。迭代中止条件根据具体问题一般选为最大迭代次数或(和)粒子群迄今为止搜索到的最优位置满足预定最小适应阈值。2.2 SCE算法简介      SCE（shuffled complex evolution ）是一种相对较新的连续性问题的元启发搜索算法^[11]。非常适合于求解具有多个局部最小的全局优化问题。它主要基于如下概念：      结合了随机性和确定性算法；      参数空间中的多点组成的复形进行系统进化；      复形中的竞争进化；      构成复形的点的重新洗牌。      SCE算法的处理过程如下：首先，随机地从问题空间中选定一系列点（或者称为个体），这里，n是问题空间的维数。这些个体分别构成p个复形，每个复形由m个点构成。P和m是用户定义的参数，他们决定了群体的大小s，即s=mp。每个复形独立地采用下山单纯形法（Nelder and Mead，1965）进行迭代进化。为了实现信息的共享，这些复形会定期进行洗牌（shuffled）处理，然后形成新的复形。如此，进化和洗牌重复进行直到满足预先指定的收敛准则。SCE算法的主要特征是通过竞争进化和定期洗牌来确保每个复形获得的信息能在整个问题空间获得共享。2.3基本PSO的停滞现象与改进      研究发现^[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) 的总的费用即为所有链路的费用总和，表示为： .                                 令Q1, …, Qn 为所有加性的QoS度量，那么整棵组播树 T(s,D)的某个QoS度量为该树中所有链路的该QoS度量的总和。表示为： ,令QM1, … , QMn 为所有凹性的QoS度量（如带宽等）。那么整棵组播树 T(s,D)的瓶颈QoS度量则为所有链路中该度量的最小值： ,       令△₁ , … _△n, 为需满足的加性QoS度量约束， 为需满足的凹性QoS度量的约束，那么组播多约束QoS路由问题则可定义为：寻找一棵满足以下条件的组播树：           (4) 4  PSO组播路由算法4.1 编码及初始化对于使用PSO求解组合优化问题，一般采用实数编码。但对于组播路由问题，采用实数编码使得算法编码、解码过程复杂。为克服编码操作带来的负面影响，所设计的算法采用了节点序列的编码机制，每个个体（即每棵组播树）被编码为源节点到各目标节点的节点系列。如：有n个目标节点，就有n条节点系列，那么PSO的搜索空间也设计成n维的空间，搜索空间的每一维坐标由所有节点的排列组合成的序列构成。粒子群的规模根据具体的网络规模和组播成员规模决定，本文在进行初始化原始粒子时，采用了随机深度搜索的方式构造：每棵组播树，由组播源节点到各个目的节点的节点序列构成。从而得到一系列个体 ，k为群体大小。我们按（7）式每个个体T_i(s,D)的适应度 f_i，并按适应度大小进行排序得到队列：                (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个复形。     3：每个复形中有各自的个体最优 和全局最优 ，根据公式（3）和（2）计算复形中所有粒子的下一位置，并根据公式(7)计算其适应度，根据适应度值判断，如果某一粒子新的位置 优于,则更新 值。     4：如果存在最优的新位置优于 ,则用该新位置更新 值。     5：如果满足结束判据，返回最优解，否则判断是否达到指定的迭代次数y，如果未到达转3继续执行，否则,转2进行重新洗牌处理。5 仿真结果     本文在PC机上（p4,2.4G,256m）对上述算法进行了仿真试验，仿真使用的网络采用了Salama ^[13] 网络拓扑生成算法来生成。首先，在相同运行条件下，比较了提出的结合SCE的PSO，标准PSO^[12]和遗传算法的运行时间。表1 各算法运行时间的比较

网络规模	PSO算法	结合sce的PSO算法	GA算法
20	0.11	0.11	0.12
40	0.20	0.19	0.23
60	0.46	0.42	0.51
80	1.35	1.14	1.51
100	1.75	1.37	3.35

              如表1所示。表中组播规模为网络规模的30%。表中可以看出，SCE的PSO和标准的PSO的运行时间均少于GA算法所需的运行时间，这是由于PSO只在解空间中搜索很小的一部分，因而在全局搜索能力上强于GA，收敛速度也较快。而结合SCE算法的PSO算法由于把采用了分散迭代的方法，从而减少了外循环的次数，提高了算法的效率，因而比PSO算法需要更少的运算时间。 

                    图2 PSO和结合SCE的PSO 延时，费用随迭代次数变化曲线     其次，对图1所示的网络拓扑结构进行了仿真试验。图中的三元组（cost,bandwidth,delay）分别表示链路上的费用，提供的带宽以及延时。这里考虑了带宽限制的时延约束费用最小的组播路由问题：源节点3,目标节点为：5，8，12，13；QOS限制为：延时D=38ms,这里假设到每个目标节点的时延限制都相同；带宽限制 B=70。      图2显示了随迭代次数变化的延时，费用变化的情况。从图中可以看出，标准PSO和结合SCE的PSO算法在较少的迭代次数的情况下都收敛到最优解，可见算法是可行的，而结合SCE的PSO算法稍优于标准PSO算法。      当网络规模较小时，PSO与结合SCE的PSO差别不大，这是由于搜索空间本身不大，搜索过程中出现局部最小的约束的几率也不大，但在较大规模的网络中就会有较大机会出现局部最小，从而导致停滞现象的出现。因此，本文比较了标准PSO和结合SCE的PSO在较大规模网络中的收敛测试。其结果如表2所示： 表2 标准PSO与结合SCE的PSO算法收敛情况比较

网络规模	基本 PSO的平均收敛代数	结合SCE的PSO的平均收敛代数	基本PSO局部收敛的概率	结合SCE的PSO局部收敛的概率
60	55	45	0.21	0.05
70	120	94	0.22	0.03
80	115	120	0.43	0.02
90	144	119	0.42	0.01
100	221	193	0.51	0.02

  表2可以看出，基本PSO算法没有很好的机制跳出局部最优解的约束，陷于局部收敛的概率较大，而结合SCE的PSO算法由于增加了利用了各个复形的信息，通过重新洗牌操作，充分利用了解空间的整体信息，增加了粒子解的多样性，从而很好地防止了停滞的出现时，因此陷于局部收敛的概率小。6结论      本文提出了一种结合SCE的粒子群优化的方法用于求解具有NP完全难度的QoS路由问题。与遗传算法的QOS路由算法相比，本文的方法更易于实现，需要的内存空间和运算时间更少。仿真结果显示，提出的算法在求解QoS组播路由问题上的应用是可行的，在寻优速度上优于采用遗传算法；SCE的引入，增加了解的多样化，克服了标准PSO算法易于陷入停滞阶段的缺点，收到较好的效果。 [1]     Wang, Z., Crowcroft, J.: Quality of service for supporting multimedia applications［J］. IEEE JSAC, 1996, (14) ： 1228-1234.[2]     Wu, J.J., Hwang, R.H., Liu, H.I.: Multicast routing with multiple QoS constraints in ATM networks［J］.  Information Sciences, 2000, (124 )：29–57.[3]     Haghighatab, A.T., Faezb, K., Dehghan, M.: A. Mowlaeib, Y. Ghahremani. GA-Based heuristic algorithms for QoS based multicast routing ［J］. Knowledge-Based Systems,2003, (16)：305–312.[4]     Wang, Z., Shi, B.: Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm ［J］. Computer Communications, 2001, (24)：685–692[5]     J. Hakkinen, M. Lagerholm, C. Peterson, and B. Sodrnberg, Local routing algorithms based on Potts Neural networks［J］. IEEE Transactions on Neural Networks, July 2000, 11(4 )：970-977 [6]     王征应,石冰心,赵尔敦 ＱｏＳ组播路由的启发式遗传算法[J]．学报, Feb. 2001, 29(2 )：253-256[7]     Russel C. Eberhart, Yushi Shi, Particle swarm optimization : developments, applications and resources[C]. Proceedings of the IEEE congress on Evolutionary Computtion (CEC2001),seoul,korea,2001：81-84[8]     Kwang Mong Sim, Weng Hong Sun, Ant colony optimization for routing and load-balanceing: surey and new directios[J]. IEEE Trans on systems, man and cybersnetics-part a: systems and humans. 2004,33(5): 560-572[9]     Kangping Wang, Lan Huang, Chunguang Zhou Wei Pan. Particle swarm optimization fro traveling salesman [C]. Proceedings of the Second International Conference on Machine Learning and Cybernetics, Xi'an, November 2-5, 2003：1583-1585. [10]  Kennedy J, Eberhart R. Particle Swarm Optimization [C]．IEEE Intemational Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, IV, 1995: 1942-1948 [11]  Thyer, M., Kuczera, G. and Bates, B. C.: 1999, ‘Probabilistic optimization for conceptual rainfallrunoff models: A comparison of the shuffled complex evolution and simulated annealing algorithms’, Water Resour. Res. 35(3), 767–773.[12]  潘达儒,杜明辉 基于粒子群优化的QoS组播路由算法[J].  , 2006,42(1):138-140[13]  Salama, H.F., Reeves, D.S., Viniotis, Y. : Evaluation of multicast routing algorithms for real-time communication on high-speed networks［J］.  IEEE JSAC, 1997, (15)： 332-345.