当前位置:首页 >> 信息与通信 >>

蚁群算法在 OBS RWA中的应用


蚁群算法在 OBS RWA 中的应用
于挺进,张奭,张冰
(西安电子科技大学 ISN 国家重点实验室,西安 710071)

摘 要: 光突发交换(OBS)以一步占用方式为突发建立端到端的全光连接。现有的 RWA 算法通常以源 宿结点对间最短路径作为突发的路由,沿路逐跳进行波长分配。在非对称的网络中,或网络业务流量非均 匀分布时,会造成链

路负载不均衡,加大突发冲突概率。本文基于蚁群思想,提出了一种 OBS 网络中分布 式 RWA 算法。对于每一个成功接收的突发,宿结点向源结点发送一个 ACK,ACK 按原路返回。结点利用 ACK 统计途经其输出链路到达某一宿结点的发送成功概率,并以此作为经过该链路到此宿结点的“气味权 值”,当新的突发到达时,按照输出链路上的气味权值,实时为突发选择输出链路和波长。仿真表明,与现 有的 RWA 算法相比,本文算法可以自适应的发现最佳路由,平衡链路负载,减小突发阻塞概率。 关键词: 关键词: 光突发交换 蚁群算法 路由波长分配

Ant algorithm in OBS RWA
Ting-Jin Yu, Shi Zhang, Bing Zhang
(State Key Lab of ISN, XiDian University Xi’an ,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 RWA1

于挺进 (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 算法;第五节给出仿真数据和分析;第六节给出结论及 下一步工作。

带格式的: 字体: (默认) Times 格式的 New Roman 带格式的: 字体: (默认) Times 格式的 New Roman 带格式的: 字体: (默认) Times 格式的 New Roman 带格式的: 字体: (默认) Times 格式的 New Roman

2

路由及波长分配算法 现有 OBS 路由及波长分配算法
鱼型网络拓扑

现有的 OBS 网络中的 RWA 算法将路 由和波长分配分成两个独立的子问题单独 考虑。路由算法采用静态路由,即源宿对 n2 n6 间的最短路径作为突发传送的路由。算法 的优点在于简单,容易实现。缺点是:对 n4 n1 n5 n8 于多个流的情况,如果流的路由存在共用 路由, 共用路由有可能成为网络中的瓶颈, 造成大量突发冲突。 我们举例说明, (s, 用 图 1 鱼型网络 d) 表示以 s 为源结点 d 为目的结点的源宿 对,如图 1 所示的非对称鱼型网络,假设各个链路的时延相同,均为 5ms。网络中存在(n0, n7)和 (n1, n8)两个源宿对。 (n0, n7)间的突发将沿最短路径,即 n0→n2→n3→n6→n7 传输;同理, (n1, n8)间的突发将沿 n1→n2→n3→n6→n8 传输。此时,在两个源宿对的共用路由 n2→n3→n6 上将重 载,导致大量的突发冲突,而 n2→n4→n5→n6 却处于空闲状态。 OBS 的波长分配算法主要有四种: LAUC (Latest Available Unused Channel) [3] ,LAUC-VF (LAUC-Void Filling) [4],MVG(Minimizing Voids Generated)[5],随机波长分配(RANDOM) 。其 中 MVG 可以最大限度的利用波长带宽,但与其它三种波长分配方案相比,其带来的性能提升非常 有限。
n0 n3 n7

3

蚁群算法简介 蚁群算法简介

蚁群算法是一种新型的模拟进化算法。该算法由意大利学者 M. Do rigo、V. M aniez2zo 和 A. Co 称之为蚁群系统(ant colony system ), 应用该算法求解 TSP 问题、 lo rini 等人在 90 年代首先提出[6][7], 分配问题,取得了较好的结果。算法受到真实蚁群觅食行为的启发,科学家发现虽然单个蚂蚁没有 太多的智力,也无法掌握附近的地理信息,但整个蚁群却可以找到一条从巢穴到食物源之间的最优 路线。经过大量细致观察研究发现: 蚂蚁个体之间通过一种称之为外激素(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
4.1

蚁群算法在 OBS RWA 中的应用

算法描述 算法描述 本文借鉴蚁群算法的思想,将其应用在 OBS 的路由波长分配问题上。视突发的源结点(s)为 蚁群的巢穴,宿结点(d)为食物源,每个突发为一个从巢穴出发向食物源觅食的蚂蚁,网络中每一 个源宿对(s,d)为一个蚁群。每个结点记录其链路集中各个链路转发到指定目的结点的突发数目 以及该突发成功到达目的结点后按原路返回的 ACK 数目。由突发发送数目和其相应的 ACK 数目计 算链路发送到目的结点的成功率并将其作为该链路的气味值。由链路气味值计算链路转发概率,后 续突发按照转发概率进行转发。本文算法与第三节所述原始蚁群算法有三点不同:①原始算法中只 存在一个蚁群,相当于一个源宿对,而实际网络中会存在多个源宿对,即存在多个不同的蚁群,我 们规定相同食物源的蚂蚁的气味值可以叠加,不同食物源的蚂蚁的气味值互不干扰。②原始蚁群算 法的某路线上气味值是与其上经过的蚂蚁数目相关的,经过的蚂蚁越多,气味值越大。这是因为在 原始蚁群算法中蚁群经过的路线无限宽,不存在阻塞丢弃的情况,所以单位时间经过的蚂蚁数目某 种程度就代表了这条路线的可用性。而实际的网络中某条链路的带宽不可能无限大,超过链路负载 能力的突发将丢失,因此用链路上经过的突发数目不能很好的描述该链路的可用性。我们规定每个 成功到达目的结点的突发按原路无阻的返回一个 ACK。据此计算通过该链路转发到指定目的结点的 成功率作为该链路上的气味值,结点根据链路上的气味值为到达的突发选择输出链路,气味值越浓, 说明经过该链路到达目的结点的成功率越大,则该链路被选择的概率越大。这个气味值可以反映在 实际网络情况中该链路的可用性。③原始蚁群算法存在一个外激素蒸发量,主要目的是为了减小历 史气味对现有气味值的影响。这里我们假设外激素不蒸发。在进一步的工作中我们再设置外激素蒸 发量。 4.2 算法详细说明 算法详细 详细说明 用 G(K,L,W)表示一个光突发交换网络。K 为节点集合,|K| = N 为结点数目;对于 ?i ∈ K , Li 表示结点 i 的输出链路集合;对于 ?l ∈ Li ,W 为链路 l 上的波长集合,|W| = M 为链路 l 上的波长
k 数目。对于 ?l ∈ Li ,记 Clw 为途经链路 l ,利用波长 w ∈ W ,去往目的结点 k ∈ K 的突发数目, Slk

带格式的: 字体: (默认) Times 格式的 New Roman

表示链路 l 关于目的结点 k 的气味值。 Alw 为途经链路 l , 记 k 利用波长 w , 成功到达目的结点 k ∈ K
k 突发个数, Alw 通过统计按原路返回的 ACK 数目得到。 bk 表示目的结点为 k 的突发的 BCP(Burst

Control Packet) bk' 表示对应于 bk 的由目的结点 k 返回的 ACK。 。 算法描述如下:
k k 第一步:初始化。对于 ?i ∈ K , ?l ∈ Li , ?w ∈ W , Clw =0 Alw =0。

第二步:结点 i 如果接收 bk ,转入第三步;如果接收 bk' ,转入第四步。 第三步:根据 bk 到达的结点 i 为目的结点或者为源结点和中间结点做不同的处理。 如果 i = k ,说明突发到达了目的结点,目的结点生成 bk ,将 bk 中的路由信息写入 bk , bk 按原
' ' '

路返回到上一跳结点,释放 bk 。这里我们假设 bk 和 bk 都利用控制波长传输,在控制波上没有阻塞。 转入第四步。 如果 i ≠ k ,则 i 是源结点或中间结点,将相应的路由信息记录在 bk 中。若

'

∑∑ A
l w

k lw

= 0 ,说明

还没有 bk' 返回,按照等概率 1/N 选择链路 l ;选定链路 l 之后对其上 M 个波长按照等概率 1/M 选择
k 波长 w 。若 RWA 分配成功, Clw 加 1,将 bk 向下一个结点转发。否则立即丢弃 bk 。



∑∑ A
l w

k lw

≠ 0 ,说明已有气味值产生。转入第五步。
' ' ' '

第四步:若 bk 已返回到源结点,则释放 bk , bk 的处理中止。否则 bk 按原路返回到上一跳结点,
k Alw 加 1。

第五步:在结点 i 上,对于 ?l ∈ Li ,其气味值 Slk =

∑ A ∑C
k lw w w

k lw

,结点将以概率 Slk

∑S
l

k l

为到

达的突发选择链路 l, 并以概率

k Alw k 如果波长选择成功,Clw 加 1, bk 将 Slk 在链路 l 上选择波长 w 。 k Clw

沿 l 向下一个结点转发。否则立即丢弃 bk 。

5

试验数据及分析 试验数据及分析

为了说明本文算法的有效性, 我们用现有的 RWA 算法作为与本文算法比较的基准算法。 由于现 有的路由波长分配策略间的性能差异不大,我们选用在最短路由上的 LAUC(记为 Shortest)为基准 算法。 仿真平台如下:网络拓扑为图 1 所示的鱼型网络。两个业务流: (n0, n7)和(n1, n8) ;每条链 路上可用波长数 W=6,其中一个波长为控制波长,五个波长为数据波长,单波长带宽 10Gb;每个 节点处均有全范围波长转换器;数据源的统计特性相同,源宿对间的突发到达均为到达率为 λ 的泊 松分布,突发占用波长的持续时间服从参数为 ? 的负指数分布,本文假设 ?=80 微秒,即平均突发长 度为 100K 字节;结点处理 BHP 的时间为 10 微秒,链路传输时延均为 5 毫秒。 图 3 为蚁群算法在业务量强度为 2Erlang 时收敛情况。 可以看出蚁群算法可以很快地收敛, 在本 仿真中大概在 5 万包左右的时候整个网络就稳定了。 开始产生一个峰值是因为开始一段时间 ACK 没 有返回,突发盲目的向各个输出链路等概率随机分配,造成较多的突发丢弃。ACK 返回时,链路上 产生了“气味”,新到达的突发在路由和波长分配时根据链路的气味值选择路由和波长,使得丢失率 迅速下降并最终稳定。 图 4 给出了在业务量强度从 1Erlang 变化到 2Erlang 时,基准算法(Shortest)与本文算法(Ant) 丢失率的比较。与基准算法相比,本文算法使突发丢失率明显降低。在基准算法中,大量突发拥挤 在共用路由 n2→n3→n6 上,从而产生了大量的突发冲突,而此时路由 n2→n4→n5→n6 则空载。虽 然 n2→n4→n5→n6 不是最短路径, 但如果适当地将部分负载向其转发则可以大大减轻 n2→n3→6 上 的拥塞状况。蚁群算法则可以充分的利用 n2→n4→n5→n6 的带宽,根据各个路由上突发成功发送概 率,动态将业务量分摊到 n2→n3→n6 和 n2→n4→n5→n6 两条路由上,使得本文算法的丢失率大大

带格式的: 字体: 非倾斜 格式的

优于基准算法。

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

丢 失 率

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 准算法 发

基准算法 Shortest 。 基准算法



发 发 。 6 基准算法 Shortest 准 。 基准算法 于 算法 准 。

算法 Ant 算法 于 发送 算法 Ant 算法

1Erlang 。 算法 发发送 1Erlang 准

2Erlang 。 于基 发

2Erlang

6
1 于 。 算法 算法 优 算法 。 发 v RWA 算法 LAUC 算法 法 p 发 v 算法 LAUC 算法 优于 算法 LAUC 算法 。

的情况下,经过 p/v 的时间,该气味值完全挥发掉,p=0。该参数的作用是减小气味值对历史数据的 依赖,同时可以较快的发现突然断裂的线路,如果某条线路突然断路,则最多经历 p/v 时间,该路 的气味值变为 0,则不会有突发向该线路转发。另外,借鉴其它蚁群算法,通常气味值不出现 0 和 1 这样的值,而是用一个最小值 Pmin>0 和一个最大值 Pmax<1 分别代替 0 和 1。通常 Pmin+Pmax=1,这 样做的好处是即使真实气味值为 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. Journal of High Speed Networks, 1999, 8(1):3-16. [4].Y. Xiong, M. Vandenhoute, and H. Cankaya. Control architecture in optical burst-switched WDM networks. IEEE Journal on Selected Areas in Communications, 2000, 18(10):1838-1851. [5].M. Iizuka and M. Sakuta and Y. Nishino and I. Sasase. A scheduling algorithm minimizing voids generated by arriving bursts in optical burst switched WDM network. in: Proceeding of GLOBECOM, Taipei, IEEE, 2002, 2736-2740. [6]. M Dorigo. Optimiztion, Learning and Natural Algorithma (in Italian)[M]. Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Mi2 lano, IT, 1992. [7]. M Dorigo, VManiezzo and A Colorni. The ant system: Optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man, and Cybernetics Part B ,1996 , 26 (1) : 29 - 41.

导师: 于挺进 导师:张冰 通信与信息系统 2002 年 9 月入学 电话: tjyu@163.com 电话:029-88201010-602


相关文章:
蚁群算法应用
自此,蚁群算法越来越多地被用于求解其它的组合优化 问题,也被推广到工业工程上应用蚁群算法特点是并发性、鲁棒性、正反馈性等。在蚁群算法求解问题的过程中,...
蚁群算法在 OBS RWA中的应用
蚁群算法在 OBS RWA中的应用 光突发交换(OBS)以一步占用方式为突发建立端到端的全光连接。本文基于蚁群思想,提出了一种OBS网络中分布式RWA算法。对于每一个成功接...
蚁群算法原理及在TSP中的应用(附程序)
蚁群算法原理及在TSP中的应用(附程序)_信息与通信_工程科技_专业资料。作者:胡斌(Author:xiao5) 2012-5-5!QQ:2262058730 蚁群算法原理及在 TSP 中的应用 1 ...
蚁群算法应用
改进的蚁群算法及其应用 40页 免费 蚁群算法的理论及其应用 3页 免费喜欢...跳过那些已经在关闭列表中的或者不可通过的(有墙, 水的地形,或者其他 无法通过...
蚁群算法在WSN中的应用
[4] 郭新华, 姜艳, 曹建霞, WSN 中动态自适应蚁群路由算法[J], 微电子学与计算机, 2008 (8)Vol.25 No.12 [5] 段海滨,蚁群算法原理及其应用[M],科学...
蚁群算法应用(运输问题)
蚁群算法应用(运输问题)_信息与通信_工程科技_专业资料。一、蚁群算法基本原理 ...ij (t ) ? 1 d ij ,这是一个与时间无关的常数.在搜索过程中,蚂 蚁...
蚂蚁算法在现实生活中的应用
蚂蚁算法在现实生活中的应用_林学_农林牧渔_专业资料。蚂蚁算法在现实生活中的应用摘要:蚁群优化算法(简称 ACO)是一种近年来才发展起来的新颖的仿生型的智 能优化...
蚁群算法在车辆路径问题中的应用
蚁群算法在车辆路径问题中的应用摘 要 蚁群算法( Ant Colony Optimization, ACO )是意大利学者 M.Dorigo 等人通过模拟蚁群觅食行为提出的一种基于种群的模 拟进化...
蚁群算法在连续函数优化求解中的应用
蚁群算法在连续函数优化求解中的应用_其它考试_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档 蚁群算法在连续函数优化求解中的应用_其它考试_资格考试...
蚁群算法实例仿真
蚁群算法实例仿真_计算机软件及应用_IT/计算机_专业资料。基本蚁群算法(AS)实例应用 蚁群算法实例仿真 TSPLIB 中的 eil51 问题 C=[ 37 52 49 49 52 64 20 ...
更多相关标签:
蚁群算法原理及其应用 | 蚁群算法及其应用 | 蚁群算法的应用 | 蚁群算法应用 | 混沌蚁群算法及应用 | 蚁群算法及其应用 pdf | 智能蚁群算法及应用 | 蚁群算法应用实例 |