蚁群算法在 OBS RWA中的应用.doc

蚁群算法在 OBS RWA中的应用于挺进，张奭，张冰（西安电子科技大学ISN国家重点实验室，西安 710071）摘 要： 光突发交换（OBS）以一步占用方式为突发建立端到端的全光连接。现有的RWA算法通常以源宿结点对间最短路径作为突发的路由，沿路逐跳进行波长分配。在非对称的网络中，或网络业务流量非均匀分布时，会造成链路负载不均衡，加大突发冲突概率。本文基于蚁群思想，提出了一种OBS网络中分布式RWA算法。对于每一个成功接收的突发，宿结点向源结点发送一个ACK，ACK按原路返回。结点利用ACK统计途经其输出链路到达某一宿结点的发送成功概率，并以此作为经过该链路到此宿结点的“气味权值”，当新的突发到达时，按照输出链路上的气味权值，实时为突发选择输出链路和波长。仿真表明，与现有的RWA算法相比，本文算法可以自适应的发现最佳路由，平衡链路负载，减小突发阻塞概率。关键词： 光突发交换 蚁群算法 路由波长分配Ant algorithm in OBS RWATing-Jin Yu, Shi Zhang, Bing Zhang (State Key Lab of ISN, XiDian University Xian ,710071)Abstract: OBS uses one-way reservation protocol to set up end-to-end all-optical connections. The current RWA algorithms usually use the shortest path between source-destination pair as the route, and wavelengths are assigned hop-by-hop. In an unsymmetrical or load with unbalanced distribution network, this algorithm will result larger probability of loss. In this paper, we propose a dynamic distributed OBS RWA algorithm enlightened by ant colony. The destination nodes feed ACKs back for each successfully received burst control packet (BCP) used for resource reservation. The ACKs are feed back along the same path as the one through which BCPs are forwarded. In each node, the success sending probability for each source-destination pair is calculated by recording the number of ACKs The probabilities are regarded as the “pheromone” of the output links. For the incoming BCPs, the node will choose the output link based on the “pheromone”. Numerical results obtained from simulation show that our RWA algorithm can find the optimal routes adaptively and get a better burst block probability performance compared with current RWA algorithms.key words: OBS Ant Algorithm RWA于挺进 (1979-) 男 吉林乾安 西安电子科技大学ISN国家重点实验室 2002级硕士1 引言随着全球范围内IP业务的迅猛增长，对传送网带宽和交换系统容量的需求正以前所未有的速度增加。现有的DWDM技术可以使一根光纤上可利用的带宽达到10Tbit/s左右,可以满足较长时期内对传送网带宽的要求 1。光分组交换（Optical Packet Switching，OPS）是全光网络的发展方向。但OPS存在着两个主要问题：一是没有合适的光缓存器。目前的实验系统中采用的光纤延迟线（Fiber Delay Line ,FDL）往往比较笨重，不灵活。1km光纤只能对光信号延迟5us,存储深度有限；二是在OPS交换节点处的多输入分组精确同步难以实现。因此，光分组交换的商业应用前景短时期内并不被看好。光突发交换（Optical Burst Switching，OBS）2是近期光通信领域的研究热点之一，它是基于电路交换的波长路由和光分组交换的有效折中。它的交换粒度介于波长路由和光分组交换之间，带宽利用率高于波长路由交换，并且比光分组交换易于实现，是很有前途的光交换技术。路由及波长分配（Route and Wavelength Assignment RWA）是OBS网络中需要解决的关键问题之一。由于OBS网络采用一步占用（one-way reservation）2的方式为突发分配路由和波长，源节点不必等待光路建立的确认就可以发送突发，具有很大的盲目性，并且由于业务的突发性，使得链路状态变化频繁，上游结点无法实时掌握下游链路的波长占用状态，更一步加剧了突发冲突的概率。选择合理的RWA算法，成为减小突发冲突概率的关键。蚁群算法是受仿生学上蚁群寻路的启迪而产生的一种新型模拟进化算法，它具有分布式、正反馈、全局收敛等优点。借鉴蚁群算法，本文提出了一种基于蚁群算法的OBS RWA算法（以下简称蚁群算法）。经过仿真验证，本文算法与现有的RWA算法相比各方面性能均有很大提高。本文第二节介绍现有的一些OBS RWA算法；第三节简要地介绍仿生学中的蚁群算法；第四节介绍本文提出的基于蚁群算法的OBS RWA算法；第五节给出仿真数据和分析；第六节给出结论及下一步工作。2 现有OBS路由及波长分配算法现有的OBS网络中的RWA算法将路由和波长分配分成两个独立的子问题单独考虑。路由算法采用静态路由，即源宿对间的最短路径作为突发传送的路由。算法的优点在于简单，容易实现。缺点是：对于多个流的情况，如果流的路由存在共用路由，共用路由有可能成为网络中的瓶颈，造成大量突发冲突。图1 鱼型网络我们举例说明，用（s, d）表示以s为源结点d为目的结点的源宿对，如图1所示的非对称鱼型网络，假设各个链路的时延相同，均为5ms。网络中存在（n0, n7）和（n1, n8）两个源宿对。（n0, n7）间的突发将沿最短路径，即n0n2n3n6n7传输；同理，（n1, n8）间的突发将沿n1n2n3n6n8传输。此时，在两个源宿对的共用路由n2n3n6上将重载，导致大量的突发冲突，而n2n4n5n6却处于空闲状态。OBS的波长分配算法主要有四种：LAUC（Latest Available Unused Channel）3，LAUC-VF（LAUC-Void Filling） 4，MVG（Minimizing Voids Generated）5，随机波长分配（RANDOM）。其中MVG可以最大限度的利用波长带宽，但与其它三种波长分配方案相比，其带来的性能提升非常有限。3 蚁群算法简介蚁群算法是一种新型的模拟进化算法。该算法由意大利学者M. Do rigo、V. M aniez2zo和A. Co lo rini 等人在90年代首先提出67，称之为蚁群系统(ant colony system )，应用该算法求解TSP 问题、分配问题，取得了较好的结果。算法受到真实蚁群觅食行为的启发，科学家发现虽然单个蚂蚁没有太多的智力，也无法掌握附近的地理信息，但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线。经过大量细致观察研究发现： 蚂蚁个体之间通过一种称之为外激素(pheromone) 的物质进行信息传递。蚂蚁在运动过程中, 能够在它所经过的路径上留下该种物质， 而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上单位时间走过的蚂蚁越多，表明该路线的可用性越好，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流寻找最优的到达食物源的线路。蚁群算法具有实现简单、正反馈、分布式的优点。图2 蚁群算法说明在图2中， 从A到E（或者从E 到A）有两条路径（ABCDE 和ABHDE），其中B到H、D到H的距离为1，B到C和D到C的距离为0.5。下面分别考虑在时刻t = 0 , 1 ,2 . .时蚁群的运动情况。如图2b，在时刻t = 0 ,设有30只蚂蚁从A运动到B。此时路径BH、BC上没有外激素(蚂蚁留下的信息量)，故蚂蚁将以相同的概率向BC、BH 运动，于是各有15只蚂蚁分别选择路径BH和BC。在真实蚁群中，外激素的数量会随时间的流逝而蒸发掉一部分，为说明方便，此处假设：所有蚂蚁运动的速度相等； 外激素蒸发量与时间成正比例，即路径上外激素的剩余量与路径的长度成反比； 蚂蚁选路的概率与所选路上外激素的浓度成正比。因为路径BHD 的长度是路径BCD的2倍，当B点的蚂蚁到达D点后，路径BCD上的外激素是BHD上的2倍。如图2c，在时刻t =1有30只蚂蚁从E到达D。因为路径DC上的外激素量是DH上的2倍，根据蚂蚁选路特点，将会有20只蚂蚁选择DC，而只有10只蚂蚁选择DH。以此类推，当t = 2 ,3 ,4. . . 时，将会有更多的蚂蚁选择路径BCD。经过较长时间运动后，蚁群最终会沿着最优路径ABCDE运动。网络的路由问题与蚁群寻路的问题有很大的可比性，都是寻找可以到达目的地的最优路线。目前已经证明蚁群算法在解决路由问题上具有分布式、正反馈、全局收敛等优点。4 蚁群算法在OBS RWA中的应用4.1 算法描述本文借鉴蚁群算法的思想，将其应用在OBS的路由波长分配问题上。视突发的源结点（s）为蚁群的巢穴，宿结点（d）为食物源，每个突发为一个从巢穴出发向食物源觅食的蚂蚁，网络中每一个源宿对（s，d）为一个蚁群。每个结点记录其链路集中各个链路转发到指定目的结点的突发数目以及该突发成功到达目的结点后按原路返回的ACK数目。由突发发送数目和其相应的ACK数目计算链路发送到目的结点的成功率并将其作为该链路的气味值。由链路气味值计算链路转发概率，后续突发按照转发概率进行转发。本文算法与第三节所述原始蚁群算法有三点不同：原始算法中只存在一个蚁群，相当于一个源宿对，而实际网络中会存在多个源宿对，即存在多个不同的蚁群，我们规定相同食物源的蚂蚁的气味值可以叠加，不同食物源的蚂蚁的气味值互不干扰。原始蚁群算法的某路线上气味值是与其上经过的蚂蚁数目相关的，经过的蚂蚁越多，气味值越大。这是因为在原始蚁群算法中蚁群经过的路线无限宽，不存在阻塞丢弃的情况，所以单位时间经过的蚂蚁数目某种程度就代表了这条路线的可用性。而实际的网络中某条链路的带宽不可能无限大，超过链路负载能力的突发将丢失，因此用链路上经过的突发数目不能很好的描述该链路的可用性。我们规定每个成功到达目的结点的突发按原路无阻的返回一个ACK。据此计算通过该链路转发到指定目的结点的成功率作为该链路上的气味值，结点根据链路上的气味值为到达的突发选择输出链路，气味值越浓，说明经过该链路到达目的结点的成功率越大，则该链路被选择的概率越大。这个气味值可以反映在实际网络情况中该链路的可用性。原始蚁群算法存在一个外激素蒸发量，主要目的是为了减小历史气味对现有气味值的影响。这里我们假设外激素不蒸发。在进一步的工作中我们再设置外激素蒸发量。4.2 算法详细说明用G（K,L,W）表示一个光突发交换网络。K为节点集合，|K| = N 为结点数目；对于，Li表示结点的输出链路集合；对于，W为链路上的波长集合，|W| = M 为链路上的波长数目。对于，记为途经链路，利用波长，去往目的结点的突发数目，表示链路关于目的结点的气味值。记为途经链路，利用波长，成功到达目的结点突发个数，通过统计按原路返回的ACK数目得到。表示目的结点为的突发的BCP（Burst Control Packet）。表示对应于的由目的结点返回的ACK。算法描述如下：第一步：初始化。对于，0 0。第二步：结点如果接收，转入第三步；如果接收，转入第四步。第三步：根据到达的结点为目的结点或者为源结点和中间结点做不同的处理。如果，说明突发到达了目的结点，目的结点生成，将中的路由信息写入，按原路返回到上一跳结点，释放。这里我们假设和都利用控制波长传输，在控制波上没有阻塞。转入第四步。如果，则是源结点或中间结点，将相应的路由信息记录在中。若，说明还没有返回，按照等概率1/N选择链路；选定链路之后对其上M个波长按照等概率1/M选择波长。若RWA分配成功，加1，将向下一个结点转发。否则立即丢弃。若，说明已有气味值产生。转入第五步。第四步：若已返回到源结点，则释放，的处理中止。否则按原路返回到上一跳结点，加1。第五步：在结点上，对于，其气味值，结点将以概率为到达的突发选择链路l，并以概率在链路上选择波长。如果波长选择成功，加1，将沿l向下一个结点转发。否则立即丢弃。5 试验数据及分析为了说明本文算法的有效性，我们用现有的RWA算法作为与本文算法比较的基准算法。由于现有的路由波长分配策略间的性能差异不大，我们选用在最短路由上的LAUC（记为Shortest）为基准算法。仿真平台如下：网络拓扑为图1所示的鱼型网络。两个业务流：（n0, n7）和（n1, n8）；每条链路上可用波长数W6，其中一个波长为控制波长，五个波长为数据波长，单波长带宽10Gb；每个节点处均有全范围波长转换器；数据源的统计特性相同，源宿对间的突发到达均为到达率为的泊松分布，突发占用波长的持续时间服从参数为的负指数分布，本文假设=80微秒，即平均突发长度为100K字节；结点处理BHP的时间为10微秒，链路传输时延均为5毫秒。图3为蚁群算法在业务量强度为2Erlang时收敛情况。可以看出蚁群算法可以很快地收敛，在本仿真中大概在5万包左右的时候整个网络就稳定了。开始产生一个峰值是因为开始一段时间ACK没有返回，突发盲目的向各个输出链路等概率随机分配，造成较多的突发丢弃。ACK返回时，链路上产生了“气味”，新到达的突发在路由和波长分配时根据链路的气味值选择路由和波长，使得丢失率迅速下降并最终稳定。图4给出了在业务量强度从1Erlang变化到2Erlang时，基准算法（Shortest）与本文算法（Ant）丢失率的比较。与基准算法相比，本文算法使突发丢失率明显降低。在基准算法中，大量突发拥挤在共用路由n2n3n6上，从而产生了大量的突发冲突，而此时路由n2n4n5n6则空载。虽然n2n4n5n6不是最短路径，但如果适当地将部分负载向其转发则可以大大减轻n2n36上的拥塞状况。蚁群算法则可以充分的利用n2n4n5n6的带宽，根据各个路由上突发成功发送概率，动态将业务量分摊到n2n3n6和n2n4n5n6两条路由上，使得本文算法的丢失率大大优于基准算法。 图3 蚁群算法丢失率收敛曲线 图4丢失率 图5 链路负载均值 图6 链路负载标准差图5给出了基准算法（Shortest）与本文算法（Ant）在业务量强度从1Erlang变化到2Erlang时链路负载均值的比较。与基准算法相比，本文算法链路负载均值较高，说明链路利用率高。由于基准算法将负载集中到共用路由，其他路由处于空载，其链路利用率较低。本文算法则可以动态地发现路由，自发地将突发向负载相对较轻的链路发送（负载轻的链路突发发送成功率大，气味值即转发概率大）。图6为基准算法（Shortest）与本文算法（Ant）在业务量强度从1Erlang变化到2Erlang时链路负载标准差的比较。与基准算法相比，本文算法链路的负载标准差非常小，说明了链路负载比较均衡。这是由于蚁群算法的自适应性，各个链路不会出现很大的空闲状态，各个链路之间的负载很接近，使得链路负载标准差很小。6 结论及下一步工作通过在简单的鱼型网络（图1）下对比静态路由LAUC算法和蚁群算法，我们可以得出以下结论：蚁群算法在丢失率、链路利用率、负载均衡方面均优于静态路由LAUC算法且可以较快地收敛。由于蚁群算法是分布式、动态的RWA算法，所以在链路状态出现变化时可以自适应的改变气味值，从而重新找到较优的路径。这点是静态路由LAUC算法无法比拟的，说明蚁群算法的健壮性也相当好。蚁群算法中还有一个外激素挥发量v，每隔一定时间气味值p挥发掉v，在没有新的外激素增加的情况下，经过p/v的时间，该气味值完全挥发掉，p=0。该参数的作用是减小气味值对历史数据的依赖，同时可以较快的发现突然断裂的线路，如果某条线路突然断路，则最多经历p/v时间，该路的气味值变为0，则不会有突发向该线路转发。另外，借鉴其它蚁群算法，通常气味值不出现0和1这样的值，而是用一个最小值Pmin0和一个最大值Pmax1分别代替0和1。通常PminPmax1，这样做的好处是即使真实气味值为0，该链路仍有可能被重新被利用。如某一链路断了一段时间又通了，如果采用0，1的气味值，则该路断了之后就没有可能被重新启用了。参考文献：1.Qiu yinghui, Ji xueifeng and Xu daxiong.Technology of OBS Routing.电信科学 2004年01期2.C. Qiao and M. Yoo. Choices, Features and Issues in Optical Burst Switching. Optical Network Magazine, 1(2):36-44, 2000.3.Turner. Terabit burst switching. Journ