蚁群算法在 OBS RWA中的应用

1、蚁群算法在OBS RW A中的应用于挺进,张奭,张冰(西安电子科技大学ISN国家重点实验室,西安710071摘要:光突发交换(OBS以一步占用方式为突发建立端到端的全光连接。现有的RWA算法通常以源宿结点对间最短路径作为突发的路由,沿路逐跳进行波长分配。在非对称的网络中,或网络业务流量非均匀分布时,会造成链路负载不均衡,加大突发冲突概率。本文基于蚁群思想,提出了一种OBS网络中分布式RWA算法。对于每一个成功接收的突发,宿结点向源结点发送一个ACK,ACK按原路返回。结点利用ACK统计途经其输出链路到达某一宿结点的发送成功概率,并以此作为经过该链路到此宿结点的“气味权值”,当新的突发到达时,按

2、照输出链路上的气味权值,实时为突发选择输出链路和波长。仿真表明,与现有的RWA算法相比,本文算法可以自适应的发现最佳路由,平衡链路负载,减小突发阻塞概率。关键词:光突发交换蚁群算法路由波长分配Ant algorithm in OBS RWATing-Jin Y u, Shi Zhang, Bing Zhang(State Key Lab of ISN, XiDian University Xian ,710071Abstract: OBS uses one-way reservation protocol to set up end-to-end all-optical connections

3、. 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 dynami

4、c 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 se

5、nding 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 BC P s, the node will choose the output link based on the “pheromone”. Numerical results obtained from simulation s

6、how 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技术可以使一根光纤上可利用的带宽达

7、到10Tbit/s左右,可以满足较长时期内对传送网带宽的要求1。光分组交换(Optical Packet Switching,OPS是全光网络的发展方向。但OPS存在着两个主要问题:一是没有合适的光缓存器。目前的实验系统中采用的光纤延迟线(Fiber Delay Line ,FDL往往比较笨重,不灵活。1km光纤只能对光信号延迟5us,存储深度有限;二是在OPS交换节点处的多输入分组精确同步难以实现。因此,光分组交换的商业应用前景短时期内并不被看好。光突发交换(Optical Burst Switching,OBS2是近期光通信领域的研究热点之一,它是基于电路交换的波长路由和光分组交换的有效折

8、中。它的交换粒度介于波长路由和光分组交换之间,带宽利用率高于波长路由交换,并且比光分组交换易于实现,是很有前途的光交换技术。路由及波长分配(Route and Wavelength Assignment R WA是OBS网络中需要解决的关键问题之一。由于OBS网络采用一步占用(one-way reservation2的方式为突发分配路由和波长,源节点不必等待光路建立的确认就可以发送突发,具有很大的盲目性,并且由于业务的突发性,使得链路状态变化频繁,上游结点无法实时掌握下游链路的波长占用状态,更一步加剧了突发冲突的概率。选择合理的RW A算法,成为减小突发冲突概率的关键。蚁群算法是受仿生学上蚁群

9、寻路的启迪而产生的一种新型模拟进化算法,它具有分布式、正反馈、全局收敛等优点。借鉴蚁群算法,本文提出了一种基于蚁群算法的OBS RWA算法(以下简称蚁群算法。经过仿真验证,本文算法与现有的RW A算法相比各方面性能均有很大提高。本文第二节介绍现有的一些OBS RWA算法;第三节简要地介绍仿生学中的蚁群算法;第四节介绍本文提出的基于蚁群算法的OBS RWA算法;第五节给出仿真数据和分析;第六节给出结论及下一步工作。2现有OBS路由及波长分配算法现有的OBS网络中的RWA算法将路由和波长分配分成两个独立的子问题单独考虑。路由算法采用静态路由,即源宿对间的最短路径作为突发传送的路由。算法的优点在于简

10、单,容易实现。缺点是:对于多个流的情况,如果流的路由存在共用路由,共用路由有可能成为网络中的瓶颈,造成大量突发冲突。我们举例说明,用(s, 图1 鱼型网络d表示以s为源结点d为目的结点的源宿对,如图1所示的非对称鱼型网络,假设各个链路的时延相同,均为5ms。网络中存在(n0, n7和(n1, n8两个源宿对。(n0, n7间的突发将沿最短路径,即n0n2n3n6n7传输;同理,(n1, n8间的突发将沿n1n2n3n6n8传输。此时,在两个源宿对的共用路由n2n3n6上将重载,导致大量的突发冲突,而n2n4n5n6却处于空闲状态。OBS的波长分配算法主要有四种:LAUC(Latest A va

11、ilable Unused Channel3,LA UC-VF (LAUC-V oid Filling4,MVG(Minimizing V oids Generated5,随机波长分配(RANDOM。其中MVG可以最大限度的利用波长带宽,但与其它三种波长分配方案相比,其带来的性能提升非常有限。3蚁群算法简介蚁群算法是一种新型的模拟进化算法。该算法由意大利学者M. Do rigo、V. M aniez2zo和A. Co lo rini 等人在90年代首先提出67,称之为蚁群系统(ant colony system ,应用该算法求解TSP 问题、分配问题,取得了较好的结果。算法受到真实蚁群觅食行为

12、的启发,科学家发现虽然单个蚂蚁没有太多的智力,也无法掌握附近的地理信息,但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线。经过大量细致观察研究发现:蚂蚁个体之间通过一种称之为外激素(pheromone的物质进行信息传递。蚂蚁在运动过程中, 能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上单位时间走过的蚂蚁越多,表明该路线的可用性越好,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流寻找最优的到达食物源的线路。蚁群算法具有实现简单、正反馈、分布式的优

13、点。 图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。在真实蚁群中,外激素的数量会随时间的流逝而蒸发掉一部分,为说明方便,此处假设:所有蚂蚁运动的速度相等;外激素蒸发量与时间成正比例,即路径上外激素的剩余量与路径的长度成反比;蚂蚁选路的概率

14、与所选路上外激素的浓度成正比。因为路径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 蚁群算法在O

15、BS RWA 中的应用4.1 算法描述本文借鉴蚁群算法的思想,将其应用在OBS 的路由波长分配问题上。视突发的源结点(s 为蚁群的巢穴,宿结点(d 为食物源,每个突发为一个从巢穴出发向食物源觅食的蚂蚁,网络中每一个源宿对(s ,d 为一个蚁群。每个结点记录其链路集中各个链路转发到指定目的结点的突发数目以及该突发成功到达目的结点后按原路返回的ACK 数目。由突发发送数目和其相应的ACK 数目计算链路发送到目的结点的成功率并将其作为该链路的气味值。由链路气味值计算链路转发概率,后续突发按照转发概率进行转发。本文算法与第三节所述原始蚁群算法有三点不同:原始算法中只存在一个蚁群,相当于一个源宿对,而实

16、际网络中会存在多个源宿对,即存在多个不同的蚁群,我们规定相同食物源的蚂蚁的气味值可以叠加,不同食物源的蚂蚁的气味值互不干扰。原始蚁群算法的某路线上气味值是与其上经过的蚂蚁数目相关的,经过的蚂蚁越多,气味值越大。这是因为在原始蚁群算法中蚁群经过的路线无限宽,不存在阻塞丢弃的情况,所以单位时间经过的蚂蚁数目某种程度就代表了这条路线的可用性。而实际的网络中某条链路的带宽不可能无限大,超过链路负载能力的突发将丢失,因此用链路上经过的突发数目不能很好的描述该链路的可用性。我们规定每个成功到达目的结点的突发按原路无阻的返回一个ACK 。据此计算通过该链路转发到指定目的结点的成功率作为该链路上的气味值,结点

17、根据链路上的气味值为到达的突发选择输出链路,气味值越浓,说明经过该链路到达目的结点的成功率越大,则该链路被选择的概率越大。这个气味值可以反映在实际网络情况中该链路的可用性。原始蚁群算法存在一个外激素蒸发量,主要目的是为了减小历史气味对现有气味值的影响。这里我们假设外激素不蒸发。在进一步的工作中我们再设置外激素蒸发量。4.2 算法详细说明用G (K,L,W 表示一个光突发交换网络。K 为节点集合,|K| = N 为结点数目;对于i K ,L i 表示结点i 的输出链路集合;对于i l L ,W 为链路l 上的波长集合,|W| = M 为链路l 上的波长数目。对于i l L ,记k lw C 为途

18、经链路l ,利用波长w W ,去往目的结点k K 的突发数目,k lS 表示链路l 关于目的结点k 的气味值。记k lw A 为途经链路l ,利用波长w ,成功到达目的结点k K突发个数,klw A 通过统计按原路返回的ACK 数目得到。k b 表示目的结点为k 的突发的BCP (BurstControl Packet 。'k b 表示对应于k b 的由目的结点k 返回的ACK 。算法描述如下:第一步:初始化。对于i K ,i l L ,w W ,k lw C =0 k lw A =0。 第二步:结点i 如果接收k b ,转入第三步;如果接收'k b ,转入第四步。第三步:根据

19、k b 到达的结点i 为目的结点或者为源结点和中间结点做不同的处理。如果i k =,说明突发到达了目的结点,目的结点生成'k b ,将k b 中的路由信息写入'k b ,'k b 按原路返回到上一跳结点,释放k b 。这里我们假设k b 和'k b 都利用控制波长传输,在控制波上没有阻塞。转入第四步。如果i k ,则i 是源结点或中间结点,将相应的路由信息记录在k b 中。若0k lw l w A =,说明还没有'k b 返回,按照等概率1/N 选择链路l ;选定链路l 之后对其上M 个波长按照等概率1/M 选择波长w 。若RW A 分配成功,k lw

20、C 加1,将k b 向下一个结点转发。否则立即丢弃k b 。若0k lw l w A ,说明已有气味值产生。转入第五步。第四步:若'k b 已返回到源结点,则释放'k b ,'k b 的处理中止。否则'k b 按原路返回到上一跳结点,klw A 加1。 第五步:在结点i 上,对于i l L ,其气味值k k k l lw lw w w S A C =,结点将以概率k k l l l S S 为到达的突发选择链路l ,并以概率k klwl klw A S C 在链路l 上选择波长w 。如果波长选择成功,k lw C 加1,将k b 沿l 向下一个结点转发。否则立即

21、丢弃k b 。5 试验数据及分析为了说明本文算法的有效性,我们用现有的RW A 算法作为与本文算法比较的基准算法。由于现有的路由波长分配策略间的性能差异不大,我们选用在最短路由上的LAUC (记为Shortest 为基准算法。仿真平台如下:网络拓扑为图1所示的鱼型网络。两个业务流:(n0, n7和(n1, n8;每条链路上可用波长数W =6,其中一个波长为控制波长,五个波长为数据波长,单波长带宽10Gb ;每个节点处均有全范围波长转换器;数据源的统计特性相同,源宿对间的突发到达均为到达率为的泊松分布,突发占用波长的持续时间服从参数为的负指数分布,本文假设=80微秒,即平均突发长度为100K 字

22、节;结点处理BHP 的时间为10微秒,链路传输时延均为5毫秒。图3为蚁群算法在业务量强度为2Erlang 时收敛情况。可以看出蚁群算法可以很快地收敛,在本仿真中大概在5万包左右的时候整个网络就稳定了。开始产生一个峰值是因为开始一段时间ACK 没有返回,突发盲目的向各个输出链路等概率随机分配,造成较多的突发丢弃。ACK 返回时,链路上产生了“气味”,新到达的突发在路由和波长分配时根据链路的气味值选择路由和波长,使得丢失率迅速下降并最终稳定。图4给出了在业务量强度从1Erlang 变化到2Erlang 时,基准算法(Shortest 与本文算法(Ant 丢失率的比较。与基准算法相比,本文算法使突发

23、丢失率明显降低。在基准算法中,大量突发拥挤在共用路由n2n3n6上,从而产生了大量的突发冲突,而此时路由n2n4n5n6则空载。虽然n2n4n5n6不是最短路径,但如果适当地将部分负载向其转发则可以大大减轻n2n36上的拥塞状况。蚁群算法则可以充分的利用n2n4n5n6的带宽,根据各个路由上突发成功发送概率,动态将业务量分摊到n2n3n6和n2n4n5n6两条路由上,使得本文算法的丢失率大大优于基准算法。 0.22 0.30 0.20 Ant Drop Rate 0.25 Shortest Ant 0.18 0.16 丢 失 率 0.20 Traffic Load= 2 Erlang 0.14

24、 丢 失 率 0.12 0.10 0.08 0.06 0.15 0.10 0.04 0.02 0.05 0 50000 100000 150000 200000 0.00 1.0 1.2 1.4 1.6 1.8 2.0 BCH发送包数 3 算法 4 1.4 2.0 1.8 1.6 1.4 Shortest Ant 1.2 Shortest Ant 1.0 平 均 负 载 负 载 标 准 差 0.6 0.8 1.2 1.0 0.4 0.8 0.6 0.4 1.0 1.2 1.4 1.6 1.8 2.0 0.2 0.0 1.0 1.2 1.4 1.6 1.8 2.0 5 6 准 5 准算法 发 基

25、准算法 Shortest 。 基准算法 。 发 发 。 6 基准算法 Shortest 准 。 基准算法 于 算法 准 。 算法 Ant 算法 于 发送 算法 Ant 算法 1Erlang 。 算法 发发送 1Erlang 准 2Erlang 。 于基 发 2Erlang 6 1 于 。 算法 算法 优 算法 。 发 v RWA 算法 LAUC 算法 法 p 发 v 算法 LAUC 算法 优于 算法 LAUC 算法 。 的情况下，经过 p/v 的时间，该气味值完全挥发掉，p=0。该参数的作用是减小气味值对历史数据的 依赖，同时可以较快的发现突然断裂的线路，如果某条线路突然断路，则最多经历 p/

26、v 时间，该路 的气味值变为 0，则不会有突发向该线路转发。另外，借鉴其它蚁群算法，通常气味值不出现 0 和 1 这样的值，而是用一个最小值 Pmin>0 和一个最大值 Pmax<1 分别代替 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, 200