波长分配算法（通用4篇）
波长分配算法 篇1
0 引 言
光通信的最大优势在于其潜在的巨大带宽,而光纤的传输容量与多波长的复用密切相关,但单根光纤可复用的波长数是有限的,因此RWA (路由波长分配)问题引起了人们的高度关注。RWA问题属于NP-C问题,在解决大规模网络的RWA问题时通常采用启发式算法。现有的启发式方案大多从阻塞率[1]、负载均衡[2]、信号损伤[3]和物理攻击[4]等方面考虑RWA问题,很少涉及网络业务与光纤链路工作状态的依赖关系的研究。链路失效是指数据无法在链路上正常传输,包括由于串扰、色散、传输损耗及非线性损伤等各种损伤造成链路质量下降导致的链路失效,也包括由于雷击、覆冰和台风等自然灾害造成的链路失效。本文着重考虑由于自然灾害所造成的链路失效对网络业务的影响,并以网络的最大风险Rm来定义这种影响,提出了一种基于网络风险的RWA算法———R-RWA。 在解决RWA问题时,以最大风险Rm为优化目标,目的在于在不增加任何管理设备成本的前提下,通过恰当的路由波长设计,使得网络发生单链路失效时,全网的安全性能下降最小,以提高网络的抗风险能力。
1 R-RWA算法的基本原理
1.1 业务可靠性
在光通信网络中,一根光纤往往承载着巨大的数据量。发生单链路失效时,若两节点之间只存在一条业务路由,则会直接造成业务的中断。因此,重要业务一般都会采用1+1保护方式对数据业务进行保护,提高其传输可靠性。单路径无保护业务和双路径1+1保护业务是两种比较常见的业务,其路由配置情况如图1所示。单链路失效是链路失效中发生率最高的一种。下面分析单链路失效对单路径无保护业务和双路径1+1保护业务传输可靠性的影响。
设业务a为单路径无保护业务,其源节点为s,汇节点为t,业务路由 为 {e1、e2、…、ei、…、en},1 ≤i≤n,如图1(a)所示。设链路ei的可靠性为ri,则链路正常状态下,业务a的可靠性为。 假设失效链路为ek(1≤k≤n)。链路ek由正常状态转入失效状态后,业务完全中断,业务a的可靠性变为r′a=0。因此链路失效前后业务a的可靠性变化为。
设业务b采用1+1保护方式,其源节点为s,汇节点为t。传输业务时,发端同时在两条路由中传输相同的数据。正常情况下,收端选收主路由的数据,只有主路由发生链路失效时,收端才会通过切换选收保护路由的数据。设路由{e11、e12、…、e1i、…、e1p},1≤i≤p,为业务主路由,路由{e21、e22、…、e2j、…、e2q},1≤j≤q,为业务保护路由,如图1(b)所示。设业务主路由上链路e1i的可靠性为r1i,保护路由上链路e2j的可靠性为r2j,则链路正常工作时,业务b的可靠性为
假设失效链路e1k(1≤k ≤p)在主路由上,链路e1k由正常状态转入失效状态后,业务b的数据只能经由保护路由传输 , 其可靠性变为,因此链路失效前后业务b的可靠性变化为
1.2 网络风险R
网络的运行风险取决于风险事件发生的概率和事件发生后对业务的影响程度。网络的运行风险主要来自于光缆、通信设备等。通信设备的可靠性较高,而且在重要位置还有备用,所以本文只考虑光缆链路对网络运行质量的影响。分析光缆链路的可靠性时需要同时考虑光缆和光放大器的影响。设光缆单位长度的可靠性为rL,光放大器的可靠性为rA。链路ej长度为l,其上有mA个光放大器,则链路ej的可靠性可表示为rj=rlL·rmAA。
单链路失效对全网业务的影响由业务的可靠性变化和业务的权重决定。设失效的链路为ej,业务bi的权重为ωi,则链路ej失效前后全网业务的可靠性扰动为, 式中 , ΔBij为链路ej失效前后业务bi的可靠性扰动,即ΔBij=Bij-B′ij,Bij、B′ij分别为链路ej失效前、后业务bi的可靠性。那么网络的最大风险Rm= max{(1-rj)·ΔEj}。
1.3 R-RWA算法
R-RWA算法考虑到业务与链路失效的依赖关系,确立风险值指标,在搜索最优路由解时以降低网络的最大风险Rm为目标。Rm越小,当网络发生单链路失效时,全网业务的可靠性扰动就越小,数据的传输也就越可靠。下面对算法进行详细描述。
设图G(V,E)为网络的实际拓扑结构,其中,V为节点集合,且V = {ν1,ν2,…,νm},E为链路集合,且E = {e1,e2,…,en}。光路请求 集合为SLP ={SLP1,SLP2,…,SLPp},SLPi= {si,ti,di}(i=1,2,…,p),si和ti分别为光路请求的源节点 和汇节点,di为业务类型。di= 1表示是单路径无保护业务;di=2表示是双路径1+1保护业务。假定网络中的节点都具有全波长转换能力,则负载最大的链路所承载的光路数即为网络所需波长数。同时,为了保证能够得到一对路径完全分离的工作路由和保护路由,网络中每个节点的度应大于1。根据光路请求矩阵求出各个光路请求的k最短路由。网络的路由方案表示为X = {x1,x2,…,xp},式中,xi= 1,2,…,k,xi表示第i个光路请求采取的是k最短路由中的第xi条路由。算法的执行过程如下:
步骤1:初始化。设置k最短路径的k值,求解各个光路请求的k最短路由。初始路由解设为光路请求的最短路径路由,即Xnow= {1,1,…,1},路由方案最优解Xbest= Xnow;计算当前路由方案的Rm= maxR(Xnow),并置Rm的最优解 为Best R =maxR(Xnow);置禁忌表tabulist为空,禁忌长度为tl,最大迭代次数为StopL,循环变量i=1。
步骤2 : 判断是否 满足算法 结束条件 , 若i≤StopL,则由当前解Xnow从某一光路请求的k最短路由中随机选取一条新的路由,得到一个新的邻域解,由此产生邻域解集合。计算所有邻域解的Rm,并按从小到大的顺序排序,转入步骤3。若i>StopL,则转入步骤4。
步骤3:若邻域解 的Best R优于当前 最优解Best R,则用此邻域最优解Xnei_best替换当前解Xnow和最优解Xbest,并将其放入禁忌表中,更新禁忌表状态;若由邻域 解得到的Best R劣于当前 最优解Best R,则用非禁忌邻域解的最优解NTXnei_best替换当前解Xnow,并将其放入禁忌表中,更新禁忌表状态。i=i+1,转至步骤2,进入下一次迭代过程。
步骤4:结束算法,得到最优路由解。
2 仿真分析
用于算法性能分析的业务量矩阵由程序随机产生,默认业务源点编号小于汇点编号,同时不产生相同业务点对的业务需求。业务类型有两种,即单路径无保护业务和双路径1+1保护业务,且为了保证存在链路完全分离的主用和保护路由,需要网络中每个节点的度大于1。不同类型业务的权重是相同的。测试网络为COST239和欧洲基本网络,拓扑结构如图2所示。
COST239网络有11个节点,最多能承 载C211=55条业务,随机均匀产生15组业务请求矩阵,业务数为30~50,网络链路可靠性均匀随机分布在区间(0.7,1.0)内。欧洲基本网络有30个节点,最多能承载C230=435条业务,随机均匀产生15组业务请求矩阵,业务数为120~180,网络链路可靠性均匀随机分布在区间(0.7,1.0)内。SP(最短路径)算法是一种常见的RWA算法。本文同时采用SP和R-RWA两种算法为网络选择RWA方案,并分别对比不同规模的两个网络拓扑下15组实验的Rm和占用波长数W 。实验结果如图3和图4所示。
由图3(b)和4(b)可知,R-RWA算法和SP算法提供的方案占用波长数的差别很小,可以认为两者消耗了等同的波长资源。而从图3(a)和4(a)可以看出,相较于SP算法,R-RWA算法在最大风险Rm指标上有明显的改善,平均减小了约33.96%和46.42%。也就是说,在消耗等同网络资 源的条件下,相较于SP算法,R-RWA算法提供的RWA方案有着更小的Rm,即网络有着更强的抗风险能力和更高的安全性能。最大风险Rm在一定程度上还可以反映链路的负载情况,链路负载越均衡,单条链路上承载的业务数量越少,发生单链路失效时,被中断的业务就越少,网络的最大风险也就越小。
3 结束语
RWA问题是光网络中的核心问题。本文在解决网络的RWA问题时,考虑了链路失效对全网业务的影响,提出了一 种基于网 络风险的RWA算法———R-RWA,并通过网络实例验证了算法的有效性。实验结果表明,与经典SP算法相比,在消耗相同网络资源的条件下,R-RWA提供的RWA方案有着更小的安全风险。在COST239和欧洲基本网络拓扑下,R-RWA算法的网络最大风险Rm分别降低了约33.96%和46.42%。算法通过降低网络的最大风险,有效抑制了单链路失效对全网业务的影响,提高了网络的安全性能。
基于PID算法的波长锁定技术 篇2
(1)采用电EA(电吸收调制)激光器，实现波长锁定。
(2)采用波长锁定器技术来实现波长锁定。
1 采用法布里—波罗标准具波长锁定器
图1是法布里—波罗标准具波长锁定器的原理框图，输入光先经过分光器，一部分送入探测器PD1，另一部分经过Etalon送入探测器PD2。其中，PD1用于产生I Reference(参考信号);PD2产生I Etalon(I Etalon随光信号频率的变化而变化)[1]。电流比I Etalon/I Reference的变化反应了波长的变化，因此可以通过检测IEtalon/IReference的比值来判断波长是否锁定。
该锁定器需要利用分光器将一部分光信号送入锁定器，从而判断此时波长是否稳定。由于分光器的引入，这样将会带来损耗，从而影响输出光功率，降低稳定性。随着半导体技术的迅猛发展，如今已经实现了将激光器、MZM调制器、波长锁定器等集成在一起，而波长锁定器的输入则是利用激光器的背向光，这样在降低成本的同时也提高了系统的可靠性。因此，本文所使用的就是这种集成式的波长锁存器。
2 PID算法原理和实现
本文使用的是集成式的波长锁定器，即激光器、MZM调制器、波长锁定器等集成在一起，波长锁定器的输入则是利用激光器的背向光，这样在降低成本的同时也提高了系统的可靠性。这种集成的波长锁定器即为第一节中介绍的法布里—波罗标准具波长锁定器。
从第一节的介绍可知这种波长锁定器的工作原理，即:波长锁定器可以根据输入光的不同波长得到不同对应的比值Ratio。所以，要想锁住波长就要控制其他变量使得Ratio值保持此波长对应的目标值，从而实现波长锁定。本设计中通过PID控制DBR激光器的Phase电流实现Ratio值的恒定，从而实现波长锁定。
2.1 PID算法的原理
PID算法是一种在过程控制中，按偏差的比例(P)、积分(I)和微分(D)运算的结果控制输出的闭环控制算法。应用这种算法的控制器称为PID控制器(亦称为PID调节器)是应用最为广泛的一种自动控制器。它具有原理简单，易于实现，使用面广，控制参数相互独立，参数的选定比较简单等优点。PID调节是连续系统动态品质校正的一种有效方法，它的参数确定方式简便，结构改变灵活(有PI、PD和PID三种)[3]。
2.2 PID算法的实现
PID算法根据其处理方式不同，可以分为增量式PID算法、位置式PID算法和微分先行PID算法。数字控制器的输出作为控制量的增量kuΔ的算法被称为增量式PID算法。数字控制器的输出值与控制量的值u(k)相对应的PID算法被称之为位置式PID控制算法。而当控制系统的给定值发生阶跃变化时，微分作用将导致输出值大幅度变化，这样不利于生产的稳定操作。因此在微分项中不考虑给定值，只对被控量(控制器输入值)进行微分，这种算法被称为微分先行PID算法。然而，目前一般的系统中应用较为广泛的依然是位置式PID算法和增量式PID算法。
位置式PID控制算法的当前控制量的大小由当前误差、累计误差和一阶前向误差共同决定，位置式PID算法具体的C语言实现如下:
所谓增量式PID是指数字控制器的输出只是控制量的增量Δuk。当执行机构需要的控制量是增量而不是位置量的绝对值时，可以使用增量式PID控制算法进行控制[4]。其中，具体的增量式PID算法的推导如下所示:
因此，如果计算机控制系统采用恒定的采样周期T，一旦A、B、C确定，只要使用前后三次测量的偏差值，就可以求出控制量。
增量PID控制算法与位置式PID算法相比，计算量小得多，因此在实际中得到广泛的应用。而位置式PID控制算法也可以通过增量式控制算法推出递推计算公式:
位置式PID控制算法的当前控制量是由当前误差和前两次的误差共同决定的，具体的C语言的实现方式如下所示:
2.3 PID参数的确定
在使用PID算法时，只有确定一组合理的PID参数才能使控制起到良好的效果，不合理的PID参数会给整个控制系统带来各种各样不良的后果。以下简要介绍PID参数调整的一般步骤和方法:
(1)比例参数Kp:首先仅仅只考虑比例控制系统，即令积分参数和微分参数的值都为0。将调整量的值设置为允许最大值的60%左右，将比例参数Kp从0开始逐渐增大，直到系统出现振荡为止。接着将Kp值慢慢减小，直到振荡消失，那个PID算法的比例参数即为振荡消失时所设置的P值的60%左右[5]。
(2)积分参数Ti:比例增益Kp确定后，设定一个较大的积分时间常数Ti，然后逐渐减小Ti，直至系统出现振荡，然后逐渐加大Ti，直至振荡消失。记录此时的Ti，设置PID的积分时间常数Ti为当前值的150%～180%[5]。
(3)微分参数Td:微分时间常数Td一般不用设定，为0即可。若要设定，与确定P和Ti的方法相同，取不振荡时的30%[6]。
(4)系统空载、带载联调，再对PID参数进行微调，直至满足要求。
以上便是PID参数确定的一般步骤，不过在实际的应用中，可以根据实际的情况进行具体灵活的调整。不过，总体的宗旨就是保证系统的快速有效的稳定，并且尽可能地减小因调整带来的振荡。
3 PID改进算法
在实际的应用过程中会遇到很多控制量与调整量非单调的情况，即:有时会遇到在一定范围内，当调制量增大时，被控制量也会随之增大，但是当调整量增大到一定的值使，控制量可能会减小，然后再随着调整量的增大而增大。具体的曲线关系，如图2所示。即，当调制量从A'增大道B'时，控制量也会随之从A增大到B，随着调整量的增加，控制量会达到最大值。此时，若调整量继续增加，如增加到C'则控制量会从最大值减小到C。
在使用PID控制算法时，如果出现振荡比较大的情况，可能会出现控制量失锁的情况。即，如图2所示，当控制量的目标值为B，而此时控制量的值为A时，如果PID的振荡较大，则在调制过程中，可能会出现下一次的调整值被设置为C'的情况。那么此时的控制量为C，则会使得误差越来越大，有时甚至会出现控制量失锁的情况。
因此，为了避免在非线性系统中，PID控制算法中因过冲过大而引起的控制环路失锁的问题，结合位置式和增量式PID算法的思路，对PID算法做了改进。一般情况下，如果PID控制算法的参数调节得足够合理的话，调整最大点只会出现在第一次调制的过程中。也就是说，第一次调整是最容易出现失锁，那么就必须保证控制量在第一次调整时保持在安全的范围内。因此，系统上电之后，应首先对调整量进行预装载，使得控制量达到目标值附近，再使用PID控制算法。这样可以避免因为首次误差太大引起的Inrush问题，同时也可以避免累计误差过大而造成震荡时间过长的问题。具体的表达式如式(5)，其中，Initialvalue表示预装载之后调整量的值，u0表示第一次PID的值。
改进之后的PID控制算法的流程图如图3所示。
从以上算法可知，改进之后的PID算法，实际上第一次是没有做调整的。那么，PID参数的I和D不能同时为0，如果出现两者同时为0的情况，则PID算法失效。并且，调整量的初始值不可以为0，若初始值为0则与位置式PID算法没有分别了，而一般情况下，将初始值设定为对系统相对来说比较安全的值，即在目标值附近。具体的C语言实现方式如下:
文中Ratio与Phase的关系并不是单调的，在一定范围内当Phase增大时，Ratio就会随之增大，但是当Phase增大到一定的值的时候Ratio又会变为最小值，再随着Phase的增大继续增大，并且每个通道对应的Phase电流临界点各不相同。在这种情况下，如果PID调节过程中，振荡过大，则会造成Phase过调，导致Ratio超过最大值而又从最小值一点点的变大，这样就会造成波长漂移而失锁。改进之后的PID控制算法可以消除调整中出现的过冲，从而解决本课题中Phase电流和Ratio非线性的问题，从而避免因Phase电流过调而带来的波长失锁问题。
4 结束语
首先介绍了常用的波长锁定技术，并通过两者的比较体现了文中所用的集成式法布里—波罗标准具波长锁定器的优势。随后，介绍了PID算法的原理，并通过推导得出了增量式PID算法和位置式PID算法的计算公式以及介绍了PID参数的确定方法。最后，针对本课题的具体情况，为了消除因Phase过调造成的波长失锁的问题，在位置式PID算法的基础上提出了改进PID控制算法。
摘要：文中主要讨论10G可调谐SFP+光模块基于DBR可调谐激光器的设计与实现。该方向主要技术涉及波长调谐、波长锁定、功率均衡以及TEC控制等。并通过PID算法实现波长锁定,该算法是对传统的位置式PID算法改进得到的。改进后的PID算法可以避免在波长锁定过程中,因Ratio过冲引起的波长失锁的问题。
关键词：DWDM,PID,波长锁定,锁定器
参考文献
[1]PID调节控制做电机速度控制[EB/OL].(2013-03-02).土豆网http:∥www.docin.com/p-24314415.html.
[2]施锴.单片集成DBR型可调谐半导体激光器的研究[D].武汉:华中科技大学硕士论文,2008.
[3]PID控制原理百度文库[EB/OL].(2013-03-02).http:∥www.docin.com/p-24314415.html.
[4]基于ARM微处理器的变频电源研究[EB/OL].百度文库.
[5]曹志刚,钱亚生.现代通信原理[M].北京:清华大学出版社,1991.
波长分配算法 篇3
光传送网(OTN)的可重构节点技术已经趋于成熟,而上层的智能控制技术还处于研究和探索阶段。控制平面的关键技术包括:RWA技术、分布式呼叫和连接管理信令技术、链路诊断、源管理技术、自动发现技术以及数据通信网业务自适应技术等等。自动交换光网络(ASON)在一定程度上解决了RWA技术和分布式呼叫和连接管理信令技术的难题,但对WRON的RWA问题的优化和设计提出了更高要求。所以对WRON中RWA算法的研究具有十分重要的意义。
1 WRON中的RWA问题
WRON被认为是构建下一代光网络的候选方案之一。但是由于网络资源有限(如波长数、收发器数目等),不可能在网络中为每一节点对都建立一条直接相连的光路,因此针对不同的网络需求,需要考虑对现有可用资源进行高效利用和优化设计。WRON的核心问题是优化设计光路的选路和波长分配,寻找一条合适的光路并为之合理地分配波长,使有限的资源充分发挥作用,以提供尽可能大的通信容量。
根据光通道连接请求的特点,可以把RWA问题分成静态和动态两类。
(1) 静态RWA(SRWA)问题:
网络的业务类型是静态的,而且当所有连接建立好之后,连接将保持不变。光通道连接请求是预先给出的,因此要求离线计算路由和分配波长,而不需要实时计算。SRWA问题的研究适合广域网(或骨干网),因为对于广域网来说,其业务流量基本是确定的。SRWA的输出结果是所有的源-目的节点对之间的光通道的路由以及给这些光通道分配的波长。
(2) 动态RWA(DRWA)问题:
光通道连接请求是逐条提出的,而且一条光通道持续一段时间后又被拆除,因此需要为每一条光通道做实时RWA计算。对于DRWA问题,对光通道建立请求的处理通常有两种策略:可重构型策略和不可重构型策略。所谓可重构型策略,就是当网络拥塞发生的时候,光网络的逻辑拓扑可以进行重构,以消除拥塞情况。但是这样的操作可能会中断很多现有的连接,而且需要对网络节点之间的光通道进行大量的调整(拆除或者重新建立),因此不适合大规模的网络。而不可重构型策略,则在拥塞发生的时候不能重构光通道,只能拒绝该请求。
总体上看,RWA中的路由和波长分配是不可分割的,但是由于RWA是个NP-C(非确定型多项式-完全,Nondeterministic Polynomial-Complete)问题,要在合理的运算时间内解决大型网络的RWA问题是不可能的,只能对规模有限的网络优化作出RWA问题的解答,所以目前一种求解RWA的方法是采用图分层方法,这种算法可以将路由和波长分配一起完成。另一种方法是把RWA问题分解为路由子问题和波长分配子问题。这种方法通常先为WRON选路,即先解决路由子问题,然后在满足一定优化性能的情况下逐一为光路分配波长。它们大多建立在传统的无向图的模型之上,在该模型中首先为每个光路请求找出最佳路由,然后再分配波长。
1.1 路由子问题
对于将RWA问题分两步进行的求解,影响阻塞率的因素主要在路由算法上。目前解决路由子问题的主要方法大致如下:
(1) 固定路由选路(FR)法:
选路是事先进行的,网络拓扑结构已知后,按照标准最短路径算法(如Dijkstra算法和Bellman-Ford算法)为每个节点对分配固定的光路。当光路请求到达时,源、目的节点对之间的通信连接总是建立在预定好的路由上。这种方法的优点是可以把RWA问题简化为波长分配问题,从而大大简化网络的控制和管理。缺点是网络性能较差、阻塞率较高。另外,该算法中网络不具备链路故障恢复能力。
(2) 固定备用路由选路(FAR)法:
FAR的核心思想是为每个节点对预先确定多条备用路由,并按一定的优先级顺序排列。排在最前面的称为主路由,其他的视为备用路由。当业务到达时,按照工作路由建立光通路,当工作路由己被占用或失效时,选择次优路由。与固定路由方案相比,网络的阻塞率大大降低,网络具有故障恢复能力,但时间复杂度相对较高。
(3) 自适应选路(AR)法:
AR算法中路由根据网络的状态动态地确定。它的实现可采用以下两类方法,第一类是预先为节点对之间确定多条备用路由,与固定、备用路由方案类似。第二类方法是不预先为节点对确定备选路由,当连接请求到达时根据网络状态为其确定路由。AR业务请求的阻塞率同FR和FAR相比最低,但网络的控制和管理比较复杂,时间复杂度也大大提高。
(4) 整数线性规划(ILP)法:
通常分为基于流的ILP和基于通道的ILP。基本思路是:列写优化目标方程→列写约束条件方程→求解线性规划。这里可以利用现有的线性规划软件工具(Lingo)对光网络拓扑设计的ILP方程进行求解,最终求得优化路由的方法。利用ILP选路灵活,网络可以具有或不具有故障恢复机制,但是这种方法只适用于规模较小的网络。
(5) 路由扩展方法:
该方法是在一段链路中插入一个节点,用新节点与原链路两端节点构成的两段链路来替换原来的一段链路,这样就构成了一个新路由,利用逐步扩展思想来构造节点之间所有的可能连接方式。此方法既可以用于网络的实际拓扑,也可以用于网络的虚拓扑。这种方法对于业务的恢复路由计算速度比较快,但路由扩展方法只是一种局部的方法,不具有全局性。
WRON中的路由子问题是确定光通路经过哪些光纤链路,从整体上讲它可以分为基于全网信息和基于局部信息的两种方式,这两种方式可以在权重定义和选路算法中得到体现。所谓基于全网信息是指做出路由决策的节点维护有全网每一条链路的资源信息。这种方式既适用于集中式控制的网络,也适用于分布式控制的网络。基于全网信息的路由策略是基于端到端的通路来选择路由的,而基于局部信息的路由方式是以逐跳方式确定路由的。与基于全网信息的路由策略相比,基于局部信息的路由策略更为灵活,具有很强的可扩展性,但其缺点是连接建立的时间较长,信令过程比较复杂。目前,基于全网信息的路由方式是一种较为成熟的路由策略,因此很多文献都是讨论这种路由策略中的各种算法。
1.2 波长分配子问题
RWA中另外一个重要子问题是波长分配问题,它可以影响全网的资源利用率和网络负载,所以选择合适的波长分配算法对于提高全网的资源利用率和网络负载均衡有很重要的作用。下面介绍目前解决波长分配子问题的算法。
1.2.1 基于局部信息的波长分配算法
此类算法仅考虑待分配连接请求路由上的波长使用信息,不需要考虑全网的波长使用情况,是最简单的一类算法。此类算法中常见的有:
(1) 随机分配(R)算法:
首先搜索所有波长的集合,找出可用波长集,再从中随机选择波长分配给光通道。
(2) 首次命中(FF)算法:
将波长在可用波长集中按固定顺序排列,对新到达的连接请求要建立的光通路,每次选择波长时均按固定顺序选择可用波长,并将选到的可用波长分配给路由。
1.2.2 基于全局资源信息的波长分配算法
这类算法首先对全网所有波长资源的使用情况进行分析,根据分析的结果选取最适合全网状况的一个可用波长。常见的算法有:
(1) 最大使用(MU)算法:
首先统计全网中所有波长的使用率,然后优先选择使用率最高的可用波长。这种算法有利于将流量集中在少数波长上,这样可以减少网络的波长需求。
(2) 最小使用(LU)算法:
首先统计全网中的所有波长的使用率,然后选择使用率最低的可用波长。这种算法的出发点是使网络流量均匀分摊到各个波长上。
1.2.3 基于全局光通道信息的波长分配算法
此类算法在为新的连接请求分配波长时,必须考虑原有波长通道的建立情况,并根据对原有波长通道的影响来选择一个可用波长。常见的算法有:
(1) 最小乘积(MP)算法:
优先选择能使光通道的所有链路占用某波长的光纤总数乘积项最小的且编号较低的波长。当每条链路的光纤数目为1时,MP算法就蜕化为FF算法。
(2) 最轻承载(LL)算法:
将最空闲的波长分配给最繁忙的链路段。
(3) 最大总和(MS)算法:
该方法使得选择该波长后,全网的其他通道的剩余可用通道数目总和最大。
(4) 最小影响(LI)算法:
选择该波长后,对全网其他通道的影响(相关通道造成的瓶颈总和)最小。
(5) 相对容量损失(RCL)算法:
该方法类似于MS算法,也是针对提升网络其他链路的空闲容量。MS算法只是致力于将网络其他链路的绝对空闲容量最大化,而RCL算法则致力于将相对空闲容量最大化。
通过比较分析可知,波长分配子问题实际上是在给定的路径上寻找一个最优的波长分配方案,使得波长利用率最高。通常的分配方案有两种,一种就是利用上述9种算法进行波长分配;另一种是使用启发式算法(如顶点着色算法、遗传算法和紧急搜索算法等)来考虑不同路径之间波长分配的互相影响,反复修改波长分配方案,改善总的波长利用率,直到无法改善为止。
2 RWA问题优化解决方法分析研究
从目前文献中提出的RWA算法来看,主要有3类RWA问题的优化解决办法:
(1) 对于基于线性规划(LP)模型的RWA解决方案,目前已经提出了许多整数线性规划(ILP)公式或者是混合整数线性规划(MILP)公式,例如针对单跳WRON和多跳WRON。虽然LP模型可以很好地对WRON进行描述,获得网络的最优解,但是由于RWA问题是一个NP-C问题,也就是说,RWA问题不能够在多项式时间内完成问题的求解。对于这些MILP公式需要进行大量的运算,因而根据目前的计算资源,这类方法往往只适用于中小规模的WRON的优化设计。为了解决此问题,目前思路是考虑通过放松或是取消一定的约束条件使问题的公式简化,从而获得问题的近似解。
(2) 对于基于概率模型的RWA解决方案,目前进行了大量的研究。主要是研究各种网络系统设计参数,例如所用的波长数目、波长路由节点的规模、光通道的平均长度和可用的波长变换数目等,对网络的阻塞概率和网络的资源利用率的影响。这种模型主要用于动态通信模式的情况,也就是说,光通道请求是一种随机的方式。例如该过程可以描述成到达概率为泊松分布,持续时间呈指数分布。网络根据需求建立或者是拆除光通道连接,不难看出该模型类似于传统电信网络的电路交换。
(3) 基于快速有效启发式算法的RWA算法解决方案,由于WRON的RWA问题是一个NP-C问题,虽然线性规划方法能够获得准确的最优解,但是这种方法计算复杂,花费的代价太高,不适合用于大通信负荷或是大规模网络的设计。在这种情况下往往需要采用近似优化的启发式算法,这是因为启发式算法强调的是得到“满意解”,在实际问题的决策过程中,往往不去苛求最优性和探索最优解。启发式算法是在研究问题模型和优化解之间内在联系的基础上获得启发而建立的。它的优点是:计算步骤简单,易于实现;计算量小,能够在短时间内获得问题的求解;易于将定性分析和定量分析相结合。因而启发式算法具有很大的实用性,对于WRON中启发式算法的研究己经得到了广泛的重视。
3 RWA算法设计存在的问题分析
RWA是WRON设计中的一项关键技术,它不仅影响网络中波长的利用率,还会影响网络的其他特性,如业务容量、设备数目和传输时延等。从目前的研究情况来看,RWA算法设计中存在以下问题需要解决:
(1) 非精确网络状态问题:
在大规模网络中保持网络全局信息的精确性几乎是不可能的。许多因素,如时延问题、网络状态更新频率和大型网络状态聚集等都会影响网络状态信息的准确性。因此,对于非精确网络状态信息下的RWA算法进行研究也很有必要。
(2) 综合性能优化问题:
网络设计需要优化的目标很多,但现有的文献大多仅考虑其中的一个,其结果虽然在某一个网络特性上达到了最优(如阻塞率),但由于缺少各个特性之间的均衡与折中,网络的代价并没有因为RWA算法的优化而降低。因此,需要研究有利于提高网络综合性能(如业务等级划分、面向业务等)的合理的RWA算法。
(3) 服务策略问题:
选路和波长分配过程所选择的光通路一般都没有考虑物理层传输系统的约束和高层业务的要求,但网络实际运营时要引入各种策略,例如引入优先策略,一些光通路必须达到损伤要求,而另一些光通路不用达到一定的损伤要求,选择的光通路必须满足WDM传输系统通路可靠性要求等。要解决这些问题必须有相应的RWA算法。
(4) 组播技术问题:
组播路由优化旨在通过共享通信资源,实现通信资源的优化利用。组播应用的普及导致了组播网络的快速发展。组播问题的求解主要在于寻找从源节点到多个目的节点的最小生成树。从数学角度归结为Steiner树问题,它属于NP-C问题。对多波光网络的研究主要集中在RWA算法方面和业务量疏导问题。
(5) 抗毁问题:
光网络的抗毁十分重要,工作光通路和保护光通路的优化也是十分重要的,必须同时考虑这两方面才能达到网络的整体优化。一种情况是只考虑波长路由光网络本身的抗毁,可以分成保护和恢复两种机制:保护机制是为每一条工作光路准备一条备用光路,要求这两条光路不会在一根光纤断裂时同时失效,解决的算法类似于备用路由算法;恢复机制是在网络有故障造成某一条光路失效时,根据网络状态实时地重新构造一条光通路,这种方法实现较复杂,同时也需要网络有一定的剩余容量。另一种情况是考虑 IP over WDM网络的抗毁,涉及光层和IP层的多层抗毁问题。
(6) 波长变换问题:
引入波长变换可使在一条光路上分配波长时更灵活,动态建立光路时阻塞率降低。目前的波长变换研究有完全波长变换和稀疏波长变换。对于不同的波长变换配置,除了要解决RWA问题外,还要解决如何实现最佳配置的问题。由于波长变换器价格昂贵,而且技术上有限制,因此波长变换在网络中的作用仍是一个争论点,波长变换对RWA问题结果的影响以及怎样在网络中引入波长变换以达到性能最佳等问题的研究还需要进一步深入。
4 结束语
WRON被认为是实现未来高速率、大容量全光网络的有效的解决方案。它以一个波长为交换粒度,采用WDM技术和波长路由技术,通过波长进行端到端之间的路由。但由于在WRON中,网络单元的功能、物理传输性能以及实际可使用的网络资源受到限制,在网络的所有接入节点之间都建立直接的光通道连接是非常困难的。所以,为了合理进行网络优化设计,有效利用网络资源,利用启发式算法对RWA算法进行优化已经成为研究的热点。
摘要：文章通过对波长路由光网络中路由与波长分配(RWA)问题的研究,介绍了求解路由子问题和波长分配子问题的常用方法,总结了3种类型的RWA问题的优化解决方法,最后对目前RWA算法设计中存在的问题进行了分析并阐述了解决此类问题的重要性。
关键词：波分复用,波长路由光网络,路由与波长分配
参考文献
[1]王汝言,张普钊,隆克平,等.WDM网络中一种基于分层图模型的RWA算法[J].光通信技术,2007,(10):4-6.
[2]罗启彬,邱昆,张宏斌.波分复用光网络中的波长路由分配策略[J].电子学报,2001,29(12):1 628-1 631.
[3]项鹏,王荣.多域光网络中的动态RWA算法研究[J].光通信技术,2007,31(1):23-26.
[4]杨春勇,王文珍,刘德明,等.一种全光路由器的设计及性能分析研究[J].电子与信息学报,2008,30(2):455-458.
[5]Goran Z,Markovic Dusan B,Teodorovic Vladanka S.Acimovic-Raspopovic.Routing and wavelength assign-ment in all-optical networks based on the bee colonyoptimization[J].AI Communications,2007,20(4):273-285.
[6]Zhang Yu,Xu Anshi,Wu Deming.Dynamic routingand wavelength assignment in multi-granularity WDMnetworks[J].Photonic Network Communications,2007,13(3):267-276.
波长分配算法 篇4
1 波长路由算法基本概述
1.1 波长路由算法的基本概念
波长路由算法是一种网路算法, 具体是指在网络中给定各节点之间的连接请求, 以网络节点连接请求为依据寻找相关网点, 从而实现路由与波长分配算法, 这一过程就称之为波长路由算法。光传输网可以分为交换网络与无交换网络, 所谓的无交换网络就是保证网络通信路径不变, 在此基础上将信号发送到网络中每一个可达到的节点, 接收节点会有选择性的对信号进行接收操作, 然而交换网络则是通过交换节点将输入端口的信号有选择性地输出到一个输出端口或者多个输出端口上。在研究中由于无交换网络路由工作性质比较简单, 并且波长的利用率较低, 所以目前我国主要研究交换网络下的波长路由算法及相关问题。
1.2 波长路由算法研究中需要考虑的因素
在波分复用光传输网中对波长路由算法进行研究需要考虑三方面因素, 需要考虑波长转换能力, 光传输网中可分为有波长转换器与无波长转换器两种状况, 波长转换器主要运用二分图表示, 与二分图相对节点的最大度数是波长转换器的度。需要考虑光传输网的拓扑结构, 通常情况下可分为一般网络与特殊网络, 特殊网络主要包括环网、线性网、树网以及网格等形式的网络。需要考虑通信请求特征, 请求可分为动态请求、静态请求以及增量请求等。
2 波分复用光传输网中的波长路由算法分析
2.1 波长路由算法的性能分析
在波分复用光传输网运行过程中, 假设某一个网络的平均通信量是已知或者可以预见, 而实时通信请求则是随机的, 光传输网在这种情况下运行网络中可能会出现信元阻塞的现象。要计算波长与路由分配实际情况, 需要对光传输网中的信元阻塞率进行计算, 而信元阻塞率可以通过试验模拟与模型分析得出。在信元阻塞率计算中不仅要考虑光传输网的拓扑结构以及波长转换器的应用, 同时还要考虑波长选择算法与路由算法。其中路由算法主要包括固定路由、选择路由以及自适应路由, 固定路由两节点之间的通信传输路径是固定不变的, 一般都是路由运行的最短路径;选择路由则是在路由表设备中为每对节点进行预先设计通信传输路径, 为了方便辨识, 还要对这些通信传输路径进行合理编号, 建立通信传输链路时应选择编号中最小的空闲路径;自适应路由设置中没有路由表, 当光传输网中存在通信传输请求时, 应根据网络的实际负载选择一条恰当的通信路径。
波长选择算法中包括四个方面内容, 随机选择, 在光传输网运行中可以从空闲波长中选择任意一条;首次适应, 对光传输网中的波长进行规范化编号, 在应用中应选择最小的空闲波长;使用链数最多, 在光传输网运行过程中选择一个空闲波长;最大容量, 该种算法主要作用于固定或者选择路由的情况下, 光传输网络中应包含一个涵盖所有通信路径的路径表, 在分配波长时, 使光传输网络所涵盖的所有通信路径剩下的空闲波长数综合实现最大化。
2.2 光传输网波长与路由分配中的困难
在波分复用光传输网中, 若多个请求共用一个链条, 那么会增加波分复用光传输网中信元阻塞率分析难度, 在分析过程中光传输网中信元阻塞率常遇到的困难主要表现在四方面:
(1) 假设光传输网中的链条是相互独立的, 该假设适合在多种电交换网络中应用, 在光传输网运行中相邻两个链上的波长选择至关重要。
(2) 假设波长是相互独立的, 那么在实际计算分析中往往会造成信元阻塞率的估计值过高。
(3) 波长选择算法对各波长通信量的影响, 在波分复用光传输网运行时网络中各波长的通信量分布在很大程度上取决于波长选择算法, 若网络中各波长的通信量均匀分布, 这种情况适合随机选择的波长算法, 而负载最大以及首次适应等其它波长选择算法的信元阻塞率分析模型则比较复杂, 在计算过程中计算量过大, 易出现计算失误的情况。
(4) 计算较为复杂, 波分复用光传输网中部分复杂波长选择算法的计算很多都是以递归方式呈现, 各波长之间以及各链条之间若不是相互独立的, 则会增加信元阻塞率的复杂性, 从而使波长与路由分配的合理性无法得到保证。
3 结语
在波分复用光传输网运行中, 每根光纤带宽都可以分为上千个波长, 可以从几个Tb/s达到几十个Tb/s的输送速率。波长路由算法的优劣直接关系着光传输网通信性能高低, 因此合理选择波长路由算法, 做好路由与波长分配尤为重要, 目前光传输网波长路由算法中还存在一定挑战, 但其应用前景是不可否认的。
摘要：随着我国器件的不断进步与发展, 现今信号在传输过程中不仅源、汇节点需要进行光电转换, 中间节点位置也可进行光传输, 以这种方式实现通信的网络称之为光传输网, 波分复用技术是光传输网中的重要技术, 其可以将光纤带宽分为多个信道, 并且不同信道利用不同波长可以实现信息的同时传输, 强化了网络带宽。基于波分复用光传输网强大的功能性, 文章对波分复用传输网中的波长路由算法进行了研究分析。
关键词：波分复用技术,光传输网,波长路由算法
参考文献
[1]王楼函, 黄胜, 阳小龙, 隆克平.WDM网络中基于负载平衡的动态波长路由算法[J].通信技术, 2010, 40 (11) :255-256