基于混沌粒子群算法的选播交错服务问题的研究.doc

基于混沌粒子群算法的选播交错服务问题的研究摘要：选播是为了平衡负载和提高网络服务质量而提出的新的通信模式，由于交错服务问题的存在，使得服务效率极大的下降，本文为了解决这类问题，从全局角度出发对所选的路由路径进行优化调整，提出了一种基于混沌粒子群优化算法，并通过仿真实验验证了算法的可行性与效率。 关键词：选播 交错服务 混沌 粒子群 多目标优化1、 引言为了提高网络的服务质量和平衡网络负载，选播（anycast）作为一种新的网络服务通信模式被提出。在传统的Internet中，不同的通信数据报之间平等的共享网络资源，网络提供“尽力而为(Best-effort)”服务。但是随着互联网中多媒体实时业务如视频点播、在线会议和网络电视等不断推出，人们对网络的服务质量（QoS）要求也越来越高，选播的一个重要应用就是提高视频流传输的效率，如同多播可以有效解决视频流的直播问题，选播可以有效解决视频流的点播问题。目前对于选播QoS问题的研究无论哪种方式都会导致交错服务问题，尤其是对于服务时间长的选播流，该问题会使其服务效率下降，甚至低于单播流。因此，不仅要设计选播的QoS路由算法还有必要从全局角度对路由进行优化。QoS选播流服务需要一定的时间，而网络的状态是不断发生变化的，选播流初始化时最优的服务器和路径在服务过程中并不一定最优，这样就会产生交错服务问题，如图1所示。在某一时刻，用户C1发送请求服务，服务器S1接受请求并建立连接进行通信；同时，用户C4发送请求服务，服务器S2接受请求并建立连接进行通信。在另一个时刻到来时，用户C2请求服务，此时边界路由器ER1被占用，服务器S2响应并接受请求建立连接；同时用户C3请求服务，此时边界路由器ER2被占用，服务器S1响应并接受请求建立连接。这样就产生了不同区域的选播服务器和客户端之间交叉访问的问题。引起交错服务问题的原因主要归为两类：服务器能力受限和网络带宽受限，其结果都会导致用户访问的服务器不是最近的，大大降低了服务的效率。DS1DS2DS3DS5DS4C1S1S2C3C4C2ER1ER2边界路由器数据流图1 交错服务问题不同于一般的QoS选播路由算法目的为选出一条满足用户请求参数的链路，解决交错服务问题就需要对QoS选播流路由从网络全局角度进行调整优化，也就是在满足各个约束条件的前提下，将客户端的服务请求重新定向到距离最近的选播服务器，实现真正意义的选播服务。2、 问题的描述及数学模型QoS的路径调整必须满足以下要求：1)调整后的路径仍然支持QoS路径的需求；2）合理分配网络资源。具体的来说就是压缩网络中选播流的传输路径，降低网络资源的消耗，同时实现网络流量平衡及选播服务器负载均衡。把网络定义为一个有向加权图G=(V,E)，其中V是网络有限的顶点集，E是网络有限的链路集，这里顶点V的集合包括两类节点：客户端节点集合M和服务器节点集合N。对于申请任一个选播请求为ni（niN）的客户端mi，有mini种可行的路径，这里所要求解的问题就是从这些可选状态中选取一种，以使网络在满足约束条件的情况下整体性能最优。引入决策便量X=xim，表示用户xi所选的服务器的集合。RD=rdkl表示链路时延的集合，rdk某条链路K的时延；LD=ldkl表示链路长度的集合，ldk表示链路k的长度；服务器负载这里用其单位时间内处理的数据包数来测量，SP=spjn表示网络中服务器负载的集合，spj表示服务器j当前的负载状况；CB=cbim表示用户占用带宽的集合，cbi表示用户i所占用的带宽，当前网络总的带宽为SB；R=ri,j,km*n*l表示客户端i到服务器j的链路集合，R=1说明包括此段链路，R=0说明不包括此段链路。本文主要选择四个网络性能参数作为优化目标：1） C与S间总时延最小，这可以保证调整后的路径使得C与S尽量不相距太远；2） 选播服务器的负载均衡，这个参数保证在各个服务器利用率最大化的情况下，使用户的请求均匀分布到各个选播服务器上；3） 网络资源负载均衡，这个参数保证了避免网络某一段链路由于反复使用而导致链路拥塞；4） 调整路径的数目，这个参数保证了在整体网络路径不做很大调整的情况下重新完成优化。将选播路由优化问题数学描述为如下多目标优化问题：minf1(x), minf2(x), minf3(x), minf4(x).f1(x) =;源节点到目标节点的总时延；;服务器的总负载；;网络链路资源利用率的方差；路径调整的数量。约束条件为：CB=SB；x=0,1,2.,n-1.即用户所消耗的带宽小于各个链路所提供的带宽和；，当前服务器所能承受的负载必须小于服务器所能提供的总负载。这实际上是一个多个约束条件的优化问题，被证明为NP完全问题。这就意味着无法在多项式的计算级别上找到最优解。目前解决这个问题多用启发式算法，然而这类算法有其自身的缺陷，运算开销过大，不能运用到大规模的网络中去，只能找到局部最优等。随着混沌研究热潮的掀起，人们认识到具有遍历性特征的混沌优化是一种全局和局部搜索能力都很强的算法。本文提出的基于混沌粒子种群混合优化算法就是基于此。3、 基于混沌粒子群优化算法实现3.1 基本思想粒子群优化算法（PSO）是一种源于对鸟类觅食行为模拟的智能优化算法，将群体中粒子的个体性和社会性有机结合产生群体智能，指导优化搜索，具有建模简单、实现容易，收敛速度快等特点。但存在易陷入局部最优点、进化后期收敛速度慢，鲁棒性较差等缺陷。混沌是自然界中的一种非线性现象，混沌变量看似杂乱的变化过程其实含有内在的规律性。本文将混沌思想引入粒子群优化算法，其基本思想是首先对例子群体里最优粒子进行混沌优寻优，然后把混沌寻优的结果随机替换粒子群中的一个粒子。这种方法改善了传统粒子群算法摆脱局部极值点的能力，提高了算法的收敛速度和精度。3.2 实现步骤假设在一个n维的目标搜索空间中，有N个粒子组成一个群体，其中第i个粒子表示一个n维的向量xi=(xi1,xi2xin),i=1,2,N，分量xij在ai,bj范围内取值，即ai=xij=bj,i=1,2,N,j=1,2,n.计算每个粒子xi的适用度函数，根据适用度值大小衡量xi的优劣。定义vi=(vi1,vi2,vin),i=1,2,.N.记第i个粒子迄今为止搜索到的最优位置为Pi=(pi1,pi2,.,pin),i=1,2,.N.整个粒子群迄今为止搜索到的最优位置为Pg=(pg1,pg2,.pgn),粒子群的更新操作为：Vi+1=vi+c1r1(pi-xi)+c2r2(pg-xi) 1Xi+1=xi+v 2其中，i=1,2.N;学习因子c1和c2是非负常数；r1和r2是介于0,1之间的随机数。迭代中止的条件根据具体问题一般选为最大迭代次数或粒子群迄今为止搜索到的最优位置满足预定的最小适应阈值。为了防止迭代过程陷入局部最优，利用混沌运动的遍历性以当前整个粒子群迄今为止搜索到的最有位置为基础产生混沌序列，把产生的混沌序列中的最优位置粒子随机替代当前粒子群中的一个粒子的位置。一般将由确定性方程得到的具有随机性运动状态称为混沌，呈现混沌状态的变量成为混沌变量。这里我们用Logistic混沌系统引入粒子群算法：Zn+1=zn(1-zn) n=0,1,2, 3式中为控制参量，方程可以看作是一个动力学系统。的值确定后，由任意初值z00,1，可迭代出一个确定的时间序列z1,z2,z3。具体的步骤如下：1）确定初始参数：群体规模N，学习因子c1，c2，进化次数，混沌寻优次数。群体规模通过随机产生，并按1，2式子对粒子进行操作；2）适用度函数的确定：F(x)=w1f1(x)+w2f2(x)+w3f3(x)+w4f4(x).w1,w2,w3,w4表示目标函数的权重，可以根据不同的应用来确定不同的系数。3）对最优位置pg= (pg1,pg2,.pgn)进行混沌优化。将pgi（i=1,2,.n）映射到方程3的定义域0,1:zi=pgi-a/bi-ai，（i=1,2,.n），然后用方程3进行迭代产生的混沌变量序列zi(m)(m=1,2,.),再把产生的混沌变量zi(m)(m=1,2,.)序列通过逆映射Pgi(m)=ai+(bi-ai)zi(m)(m=1,2,)返回到原解空间，得 Pg(m)=( Pg1(m),) Pg2(m),. Pgn(m),(m=1,2,)在原解空间对混沌变量经历的每一个可行解Pg(m) ,(m=1,2,)计算其适用度函数值，保留性能最好的可行解P*.4）随机从当前群体中选取一个粒子用P*取代;5）若达到最大代数或者得到满意解，则优化过程结束，否则转3。4、算法分析及仿真4.1 收敛性分析 在编码方面，将路径序列用一个整数表示，使得原本对路径序列的操作简化为对整数的操作。根据文献，在整数域进行直接进化搜索的CPSO算法从收敛的最优性和收敛速度方面均有最好的性能。根据文献5，本文提出的CPSO算法可以收敛到全局最优，并且具有良好的稳定性。4.2 有效性分析通过仿真的方式对本文提出的混沌粒子群算法和传统的PSO算法进行了比较。其中仿真网络用Waxman提出的方法随机生成，选播的源节点和服务器节点通过随机生成。服务器资源在1,10之间,混沌粒子群算法用C语言进行实现。首先，在不同规模的网络执行混沌粒子群算法，结果如图1所示。从图1我们可以看出，随着网络规模的增大，混沌PSO算法仍然有很好的表现，它的运行时间随着网络中节点个数的增加缓慢增加，没有出现指数增长的情况，这说明该算法具有较高的效率，能满足现行网络中实时性的要求。图1 混沌粒子群算法运行时间为了便于与传统的PSO算法进行比较，在多个约束目标中算法采取了相同的带宽和时延约束，初始种群个数也相同。主要在于考察算法的收敛能力和收敛速度。图2显示了具有100个节点的混沌粒子群算法和传统的粒子群算法的收敛情况。两个算法都很好的收敛 于一条可行的路由。但是在搜索效率上，由于引入了混沌的映射思想，psco能较快达到全局最优，因此，在收敛速度上混沌PSO算法要优于PSO算法。图2 混沌PSO与PSO算法的收敛程度4、 结论本文针对选播服务的交错服务问题，提出了基于混沌的粒子群优化算法，对优化后的路径进行了调整，调整方式转化为多目标路由优化问题，基于混沌的PSO算法既保存了群体的多样性又能加快搜索效率，避免了陷入局部最优，达到了预期的目的。参考文献1 He Hong, Qian Feng, Du Wenli. A chaotic immune algorithm with fuzzy adaptive parameters J. Asia-Pacific Journal of Chemical Engineering, 2008,3(6):695-705.2 Lovbjerg M, Rasmussen T K, Krink T. Hybrid particle swarm optimizer with breeding and subpopulationsC/ Proceedings of Genetic and Evolutionary Computation Conf. San Francisco: Morgan Kaufmann Publishers Inc, 2001: 469-476.3 B Liu,L Wang,Y-H Jin,F Tang,D X Huang. Improved particle swarm optimization combined with chaosJ.Chaos Solitons &Fractals(S0960-0779),2005,25(21):1261-1271.4 UN J,FENG B,XU WB.Par