遗传路由算法在栅格通信网中的应用

康江 冯钊 乔瑞娟 张雅男

摘 要：遗传算法是一种通过模拟自然进化过程搜索最优解的方法。针对Dijkstra算法在复杂的栅格化通信网路由中的应用的局限性，本文将遗传算法引入到路由算法中，通过仿真表明随着网络规模的扩大，遗传路由算法可降低路由算法的复杂度，提高网络运行的效率。

关键词：遗传路由算法；栅格通信网；应用

随着通信、计算机和网络技术的迅猛发展，通信网络以综合业务、异构网络资源共享为发展趋势。现有的电信网体系结构从业务开放性、数据综合业务及带宽性能等方面，不能满足将来业务的需求。为了提供安全、集成、一体化的端到端信息服务，构建新一代的栅格化通信网络[1]势在必行。

1 栅格通信网的体系结构

基于网络构建的、灵活分布的信息网格，支持在动态变化的网络环境中分享和协同解决问题。栅格与网格没有本质的区别，网格是基于因特网构建，而栅格是基于专用通信网络构建[2]。

新一代的柵格化通信网络除了具备支持综合业务、统一通信、集成服务和集成应用等主要通信网络功能还需具备规模和功能扩展、平台和网络开放及资源的有限共享、端到端高性能的通信能力等特征[3]。

本文提出一种栅格通信网的分层结构。在通信网的网络层上添加一个栅格通信服务层，更好的感知网络资源从而支持栅格应用。

2 栅格通信网中的路由技术

目前基于栅格通信网研究的项目不多，大多是关于网络架构方面的，较少考虑底层通信网中承载栅格服务的具体路径。

文献[4]提出了一种以信息安全程度为QoS参考量的策略路由技术。该策略路由技术在一定程度可以提高栅格通信网络的安全可靠性，但是文中只在给出的简单网络中进行了有效验证。文献[4]采用了最短路径路由算法中常用的Dijkstra（迪杰斯特拉）算法对文中提出的栅格化网络跨域通信资源联合调度方法进行了验证。Dijkstra算法适合求解确定起点的最短路径路由问题，然而随着网络规模与复杂度的增加，Dijkstra算法复杂度会呈现几何级数的增长，该算法不能很好的去适应。本文采用具有较强的自适应性及全局优化性的遗传算法对底层通信网的具体路径选择进行研究。

3 遗传路由算法的应用

遗传算法（Genetic Algorithm-GA），是模拟自然生物界系统优胜劣汰的一种智能搜索算法，它可在大的搜索空间寻找最优解或近似最优解。以下为遗传算法的一般流程。

3.1 种群初始化

种群的选定是遗传算法的前提。遗传算法要求所选初始种群的规模要适当，使算法既能体现良好的优化性能又不至于陷入局部最优解。本文选定起点到终点的所有路径作为初始种群。

3.2 适应度函数

自然界中，个体的适应值，即是它的繁殖能力，将直接关系到后代的数量。遗传算法在运算过程中用适应度函数来评价个体优劣。然而网络中的链路具有带宽、时延、延时抖动、包丢失率等属性，很难从某一角度评价链路的优劣。本文构建如下适应度函数对各条链路进行客观的评价：

其中B（x）正比于各条链路中具有最小带宽的节点链路，D（x）、J（x）、L（x）分别反比于节点链路的最大时延、延时抖动、丢包率。，是正加权系数，分别表示带宽、时延、延时抖动、丢包率在适应度函数中所占的比例。，它们的值根据具体应用的侧重点确定。

3.3 遗传的操作

遗传算法的核心步骤是选择、交叉、变异。

选择是从群体中选择优良个体并淘汰劣质个体。各个个体被选择的概率与其适应度成正比。高适应度值趋向于被选中，低适应度趋向于被淘汰。采用保留最优解与轮盘法想结合进行个体选择。先按需保留最佳个体，再按概率选择适当的其他个体。设个体i被选中概率为（i=1，2，3，……n），其中n为种群大小。

交叉是指把两个父代个体的部分基因加以替换重组而生成新个体的操作，模拟自然界有性繁殖生成新个体，使其比它的两个父代有更高的适应值。交叉是遗传算法主要搜索工具，也是区别于其他进化算法的主要标志。由于网络中连路的特殊性，防止两个父代个体产生错误的子代，因此交叉必须满足以下两个条件：

⑴进行繁殖的两个父代个体必须具有相同的链路节点，防止不存在相同节点的链路交叉产生后代

⑵生成的子代链路不能含有相同的链路节点，防止路由环的出现。

遗传算法中同样引入变异产生新个体，即将个体染色体上的某些基因用其它等位值替代，从而形成新个体。交叉与变异相互配合，共同完成对搜索空间的优化搜索。

4 仿真实验及结果分析

采用网络仿真软件OMNeT++4.3构建仿真环境对遗传路由算法优越性进行验证。

仿真系统包含2个网管域。每个域内异构通信网络拓扑分别由Area1.ned和Area2.ned进行描述，设置为有若干个路由器和多条有线光纤、卫星等不同类型的传输链路构成的网络拓扑。两个域内路由器分别设置为10、30、50等3组进行仿真。源和目的节点在两个域内随机选择，目的节点优先考虑跨域选择。设置源节点业务类型为普通报文。每一组均用Dijkstra算法、遗传算法分别进行5次实验查找最短路径，分别记录查询到最短路径的时间，同时记录报文在源与目的节点的报文接收数量。实验结果如下：

表1 网络节点收发包数统计表

路由数 算法 发送包数 接收包数 接收成功率

10 遗传 3065 2597 84.75%

迪杰斯 3065 2609 85.12%

30 遗传 3065 2303 75.16%

迪杰斯 3065 2319 75.66%

50 遗传 3065 1886 61.53%

迪杰斯 3065 1896 61.85%

表1表明兩种算法在网络数据包接收成功率方面大体一致。图2横轴表示两种算法搜索最优路径所用的时间，纵轴表示网络的复杂度（本文采用网络路由数量衡量），左右图分别表示Dijkstra和遗传遗传算法复杂度。舍弃两图中刚开始统计的不合理数据，通过对比可以看出随着网络规模的扩大，Dijkstra搜索最优路径时间的增幅要明显快于遗传算法搜索最优路径时间的增幅。

综上所述，遗传路由算法可以降低栅格化通信网络路由算法的复杂度。

[参考文献]

[1]汪陶先.信息栅格与通信栅格[J].现代通信技术，2004（4）：1-6.

[2]范淑艳，熊高云.栅格通信网络体系机构及关键技术研究.西安电子科技大学学报，2009（6）：990-995

[3]黄天章，等.面向通信网络服务架构的通信网络设计分析.通信系统与网络技术，2012（3）：5-8.

[4]任勇毛，唐海娜，李俊，等.支持网格应用的光网络控制和管理[J].软件学报，2008，19（6）：1481-1490.

[5]张培珍，杨根源，等.全球信息栅格服务质量互通性研究[J].计算机测量与控制，2010.18（2）：393-396.

[6]ZHANG Yongding，ZHENG Xiangquan，WEN Xiang.Research on grid-enabled communication network architecture[C].Changzhou：IEEE 2010 International conference on research challenges in computer science（ICRCCS2010），2010.

[7]Christodoulopoulos K，Doulamis N，Vararigous E M.Joint Communication and Computation Task Scheduling in Grids [C].Proceedings of the 8th IEEE International Symposium on Cluster Computing and Grid（CCGRID08）.Lyou：IEEE，2008：17-25.

[8]Chen Fu，Yang Jiahai，Yang Yang.Toplogy Discovery Service Research in Grid Environments[C].Proceedings of the 7th World Congress on Intelligent Control and Automation（WCICA 2008）.Chongqing：IEEE，2008：2104-2109