邓沌华，刘秋兵2，李 蔚

（1.湖北经济学院信息管理学院，武汉 430205； 2.北方自动控制技术研究所，太原 030062；3.华中科技大学武汉国家光电实验室，武汉 430074）

一种基于改进遗传算法的波长路由算法

邓沌华1，刘秋兵2，李 蔚3

（1.湖北经济学院信息管理学院，武汉 430205； 2.北方自动控制技术研究所，太原 030062；3.华中科技大学武汉国家光电实验室，武汉 430074）

WDM（波分复用）光网络中基于GA（遗传算法）的RWA（路由与波长分配）算法是目前最常见的算法，为了提高网络资源利用率并进一步降低阻塞率，提出了一种动态的、基于改进GA的DCMA-GA（双交叉变异自适应遗传算法），通过引入自适应交叉与变异概率机制来减少GA的复杂度并应用于波长分配子算法中。仿真结果表明，与经典算法Dijkstra+FF（首次命中）相比，新算法最大能降低50%的阻塞率，在波长分配方面可提高10%的性能，验证了新算法的有效性。

波分复用；改进遗传算法；路由与波长分配；双交叉变异；自适应

0　引 言

RWA（路由与波长分配）的本质是为请求的连接寻找合适的路由并分配适当的波长。在当前技术条件下，网络越复杂，RWA问题的优化越关键，如果RWA耗时较多，则无法准确及时地建立光链路［1-2］。目前对于波长分配子问题的求解主要有3类算法，即基于局部信息、全局资源信息和全局通路信息的波长分配算法，而常见的波长分配算法主要有最大总和算法、最小影响算法、RCL（相对容量损失）算法以及RLI（相对最小影响）算法等［3-8］。其中，RCL和RLI算法的性能相对较好，且后者比前者描述网络状态更加准确，也是当前重点研究和应用的波长分配算法。

而GA（遗传算法）自1975年被提出至今已有近40年历史，基于GA对RWA算法进行改进，再有所创新和突破完全可期。本文提出了一种动态的、基于改进GA的DCMA-GA（双交叉变异自适应遗传算法），通过引入自适应交叉与变异概率机制来降低GA的复杂度，并应用于波长分配子算法中。

1　RWA改进算法

对于WDM（波分复用）光网络中的RWA问题，DCMA-GA是一种改进型求解算法，主要改进在于GA的染色体的设计，其染色体由波长和路径编号序列混合组成，长度动态增长，并采用双交叉变异遗传操作，变异概率采用自适应机制。另外，在GA的适应度函数计算公式中引入了高效的RLI波长分配算法，可以加快GA收敛，同时得到RWA的两个最优解。

1.1编码策略和相关的原则

图1所示为DCMA-GA的染色体编码形式，其采用波长编号与路由节点序列组合的可变长编码方式。

图1　DCMA-GA的染色体编码形式

波长编号和节点编号在程序初始化时赋给固定的值，运行过程中，编号保持不变。首先对全网中的所有波长按长度排序，对应λ1～λm，m为可用波长总数。节点编号是拓扑中所有节点的索引编号，对应节点1至节点n，n为拓扑中节点总数。

编码方式应满足完备性、健全性、非冗余性、紧致性和可扩展性的原则。适度函数的设计与选择也要满足适应性评分的非负性、合理与一致性和计算的简单性。

1.2初始种群的生成

GA能否快速有效收敛并得到最优解，初始种群分布的广泛性和多样性至关重要。DCMA-GA的解决思路是初始种群中路由部分采用随机深度优先搜索的方法生成。具体算法如下：

bool Get OnePath（std：：map＜int，bool＞Visited，/*由调用者提供的节点访问记录表*/Node *A，/*源节点*/Node*B，/*目的节点*/ std：：vector＜Node*＞Path/*路径节点序列存储表*/）//成功返回true，此时Path中为随机搜索到的A B的一条路径，失败返回false

｛Path.clear（）；Path.push_back（A）；

Visited［A节点对应的编号］=true；//设置A节点已被访问过

while（！Path.empty（））

｛cur Node=Path.back（）；

if（cur Node==B）return true；//找到一条路径

if（cur Node的所有邻接点都已被访问过‖cur Node到所有未被访问过的邻接点均无可用波长通道）Path.pop_back（）；

else

｛从cur Node未被访问过且有可用波长通道的邻接点中随机选择一个；

Path.push_back（选中的新节点）；

Visited［新节点对应的编号］=true；//设置新节点已被访问过｝//else结束

｝//while结束

return false；/*寻找路径失败*｝//结束

1.3适应度函数的设计

适应度函数是GA对群体进行评估并作出相应选择的唯一依据，故适应度函数影响到群体的进化质量，甚至影响到算法最终能否得到最优解。路由选择的优化目标为路径代价尽量小，这是因为光纤传输的代价问题仍是光路设计时不可忽略的重要考虑因素之一；波长分配的优化目标为对其他相关通路的相对影响尽量小，因为其直接影响全网的平均阻塞率指标。综合上述两方面的优化目标以及适应度函数选择与设计的原则，DCMA-GA的适应度函数可表示为

式中，α、β为修正系数，主要是为了调节F（x）的值以便于统计，且满足α＞β＞1；Cost（p*）为路径对应的代价函数，如果不考虑其他QoS（服务质量）约束，该值为组成p*的各链路的距离代价之和；RBC（p*，w）即为RLI算法中定义的“分配波长给光通路对全网造成的影响”。

1.4遗传操作

GA的遗传操作包括选择、交叉和变异3个基本操作算子。为了有效提高GA的性能，DCMAGA引入了自适应交叉与变异机制：根据染色体编码方式的特殊性，对波长与路径分别进行概率独立的交叉与变异操作，即个体的路径部分与波长部分分别以独立概率进行交叉，但是波长部分须在路径部分的可用波长集范围内交叉。既保证了交叉后不会出现非法个体，又尽可能地保证了群体的多样性，扩大了算法的全局搜索空间范围。完整的DCMAGA描述如下：

（1）对当前请求的源宿节点利用1.2节算法生成初始种群oldpop；

（2）设迭代数gennum=0；

（3）计算oldpop的适应度，得到适应度总和sumfitness以及最佳个体bestfit；

（4）判断gennum是否大于maxgen，是则跳转至（9），否则继续；

（5）对oldpop逐对进行遗传操作，子代个体对放入新种群newpop，循环直到newpop大小达到popsize；

（6）用bestfit随机替换newpop中的一个个体；

（7）newpop和oldpop互换指针值；

（8）gennum=gennum+1，转至（3）；（9）bestfit作为算法结果输出。

2　仿真结果与分析

仿真采用14节点、21条双向单纤链路的NSFNET（美国国家科学基金会网络），其拓扑及链路代价如图2所示。

图2　NSFNET的仿真拓扑图

（1）与Dijkstra+FF（首次命中）算法的比较

图3所示为DCMA-GA与Dijkstra+FF的性能比较，相较于Dijkstra+FF算法，DCMA-GA性能明显优于经典算法。当负载较小时，二者的阻塞率相似，当负载逐渐增大到80 Erl左右时，Dijkstra+FF算法的阻塞率明显增大，原因是：（1）Dijkstra+FF算法在寻找路由时只考察路径最短的那条，而在网络负荷较大时该路由上极有可能已没有可用波长，此时Dijkstra算法的不灵活性导致寻路失败；（2）即使Dijkstra算法可以获得该最短路由，但由于FF算法在分配波长时不会做某种影响评估，势必会影响后继RWA。而DCMA-GA不仅在寻路时借助GA进行全局搜索，在分配波长时也借助了RLI算法进行全网影响评估，所得RWA结果不仅对当前请求较优，而且对后继其他请求的影响也较小，因此对全网平均阻塞率的影响较大。

图3　DCMA-GA与Dijkstra+FF性能比较

当网络负荷变大时，本文所提算法与经典算法相比能逐步降低网络阻塞率，在网络负荷很大时，所提算法较经典算法最大能降低50%的阻塞率。

（2）与普通GA的比较

图4所示为DCMA-GA与普通GA的性能对比图。由图可知，在迭代开始阶段（前15代），DCMA-GA并没有表现出比普通GA更好的性能。这主要是由于DCMA-GA采用的自适应交叉变异机制仍处在试探阶段，交叉变异概率波动较大，算法尚未能快速得到最适合当前代群体的交叉变异概率。然而在试探阶段结束后（第20代开始），DCMA-GA迅速向群体更优的方向进化，体现了算法较好的改进性能。这主要是由于自适应交叉变异机制能够得到更丰富的交叉与变异操作，因此群体的多样性要好于普通GA。同时，由于在自适应交叉变异机制中，精英个体得到保留的概率较大，因此到遗传进化后期（第30代后），DCMA-GA得到的群体平均适应度基本稳定在3.4，而普通GA则维持在3.0左右，表明DCMA-GA能够得到更优的解，较普通算法能提高10%的优化率，改进效果较为明显。

图4　DCMA-GA与普通GA的性能对比

3　结束语

本文提出了一种基于全局通路信息的DCMAGA并应用于波长分配子算法中。通过引入自适应交叉与变异概率机制来降低GA的复杂度。仿真结果表明，所提算法能有效地提高算法效率，降低算法的复杂度，尤其在网络的负荷较大时，所提算法与经典算法Dijkstra+FF相比可降低50%的网络阻塞率，在波长分配方面可提高10%的算法性能。为WDM光网络中动态RWA问题的算法研究提供了新的改进思路，对光网络的规划与优化设计也具有一定的指导意义。

［1］ 原荣.光纤通信技术［M］.北京：机械工业出版社，2011.

［2］ 顾畹仪，张杰.全光通信网［M］.北京：北京邮电大学出版社，1999.

［3］ Palais Joseph C.光纤通信［M］.王江平，等译.第五版.北京：电子工业出版社，2011.

［4］ Mukherjee B.WDM optical communication networks：progress and challenges［J］.IEEE JSAC，2000，18 （10）：1810-1824.

［5］ 孙雪荣.光网络路由选择及波长分配算法［D］.西安：西安电子科技大学，2011.

［6］ 徐世中，王展，李乐民.DWDM光传送网中选路和波长分配［J］.通信学报，2001，24（4）：51-56.

［7］ 张百成，高随祥.WDM光网络动态路由和波长分配算法［J］.微型机与应用，2005，（11）：37-39.

［8］ 李蔚.波长路由光网络中快速动态光链路建立的研究［D］.武汉：华中科技大学，2006.

A RWA Algorithm Based on Improved Genetic Algorithm

DENG Zhuan-hua1，LIU Qiu-bing2，LI Wei3
（1.College of Information Management，Hubei University of Economics，Wuhan 430205，China；2.North Automatic Control Technology Research Institute，Taiyuan 030062，China 3.Wuhan National Laboratory for Optoelectronics，Wuhan 430074，China）

In WDM optical networks，the routing selection algorithm based on GA and wavelength assignment algorithm are widely used.In order to further optimize the routing and wavelength assignment in WDM optical network，a dynamic RWA algorithm named Double Crossover and Mutation Adaptive-Genetic Algorithm（DCMA-GA）for WDM network based on improved GA is proposed.Through simulation，the new algorithm can reduce the network blocking rate by 50%when the network load is big.The efficiency of algorithm can also be improved by 10%when compared with the normal genetic RWA algorithm.

WDM；improved GA；RWA；double crossover and mutation；adaptive

TN929

A

1005-8788（2016）04-0019-03

10.13756/j.gtxyj.2016.04.006

2016-04-16

国家自然科学基金资助项目（61177063）

邓沌华（1976-），女，湖北武汉人。副教授，硕士，主要研究方向为计算机网络。