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

      令Q1, …, Qn 为所有加性的QoS度量，那么整棵组播树 T(s,D)的某个QoS度量为该树中所有链路的该QoS度量的总和。表示为： ,令QM1, … , QMn 为所有凹性的QoS度量（如带宽等）。那么整棵组播树 T(s,D)的瓶颈QoS度量则为所有链路中该度量的最小值： ,       令△₁ , … _△n, 为需满足的加性QoS度量约束， 为需满足的凹性QoS度量的约束，那么组播多约束QoS路由问题则可定义为：寻找一棵满足以下条件的组播树：

           (4)

 

对于使用PSO求解组合优化问题，一般采用实数编码。但对于组播路由问题，采用实数编码使得算法编码、解码过程复杂。为克服编码操作带来的负面影响，所设计的算法采用了节点序列的编码机制，每个个体（即每棵组播树）被编码为源节点到各目标节点的节点系列。如：有n个目标节点，就有n条节点系列，那么PSO的搜索空间也设计成n维的空间，搜索空间的每一维坐标由所有网络节点的排列组合成的序列构成。

粒子群的规模根据具体的网络规模和组播成员规模决定，本文在进行初始化原始粒子时，采用了随机深度搜索的方式构造：每棵组播树，由组播源节点到各个目的节点的节点序列构成。从而得到一系列个体 ，k为群体大小。

我们按（7）式计算每个个体T_i(s,D)的适应度 f_i，并按适应度大小进行排序得到队列：

                (5)

然后 按如下规则分成 个复形： ,每一个复形包含 个个体：

        (6)

 

在所设计的算法中,使用了惩罚函数来处理QoS约束，这样约束优化问题就变成了非约束的优化问题。算法用到的适应度函数设计如下：

                (7)

这里，是正的实数，反映了各QoS参量的重要性。 为惩罚函数， r是惩罚的程度。

      如2.3分析，为了防止停滞现象，本文设计的算法引入了SCE的洗牌处理。其处理如下：

首先指定每个复形经过y次迭代后重新进行洗牌，按式（6）进行处理，重新形成P个复形。

     出的结合SCE的PSO路由算法的步骤如下：

     1：编码和初始化，采用随机深度优先的搜索方法随机产生个体。

     2：根据公式(7)计算每个个体的适应度，并排序，按式（6）把他们分为p个复形。

     3：每个复形中有各自的个体最优 和全局最优 ，根据公式（3）和（2）计算复形中所有粒子的下一位置，并根据公式(7)计算其适应度，根据适应度值判断，如果某一粒子新的位置 优于,则更新 值。

     4：如果存在最优的新位置优于 ,则用该新位置更新 值。

     5：如果满足结束判据，返回最优解，否则判断是否达到指定的迭代次数y，如果未到达转3继续执行，否则,转2进行重新洗牌处理。

     本文在PC机上（p4,2.4G,256m）对上述算法进行了仿真试验，仿真使用的网络采用了Salama ^[13] 网络拓扑生成算法来生成。

首先，在相同运行条件下，比较了提出的结合SCE的PSO，标准PSO^[12]和遗传算法的运行时间。

表1 各算法运行时间的比较

 

 

 

 

 

 

 

 

 

     如表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算法收敛情况比较

 

 

表2可以看出，基本PSO算法没有很好的机制跳出局部最优解的约束，陷于局部收敛的概率较大，而结合SCE的PSO算法由于增加了利用了各个复形的信息，通过重新洗牌操作，充分利用了解空间的整体信息，增加了粒子解的多样性，从而很好地防止了停滞的出现时，因此陷于局部收敛的概率小。

      本文提出了一种结合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.