基于自适应遗传蚁群算法的SDN路由规划研究.pdf

第 卷 第 期 年 月天 津理工大学学报 .收稿日期:修订日期:基金项目:湖北省教育厅科研计划重点项目()湖北省科技厅重点研发计划项目():/基于自适应遗传蚁群算法的 路由规划研究崔峻玮翟亚红(湖北汽车工业学院 电气与信息工程学院 湖北 十堰)摘要:技术的快速发展使网络规模不断扩大 结构日益复杂 传统路由算法已无法满足不同业务服务质量()需求的数据传输 设计了基于软件定义网络()的实时路由规划框架 以有效地管理网络资源 结合遗传算法和蚁群算法的优点 提出基于自适应遗传蚁群()的 路由算法 通过仿真试验将该算法与遗传算法、蚁群算法在不同网络规模中进行对比 并进行了路由仿真 结果表明:该算法能在大规模网络中通过快速搜索得到多个优选路径 可充分利用正反馈来缩小最大搜索时间 快速找到满足不同业务的最优路径 且面对大规模网络时 效率和稳定性更高 基于自适应遗传蚁群的 路由算法在不同业务需求下的寻优能力均得到保障 对比其他两种传统算法寻优效率得到明显提升关键词:软件定义网络 服务质量 路由规划 自适应遗传蚁群算法中图分类号:文献标识码:文章编号:()():.:随着网络用户的增多 网络规模不断扩大 网络新型业务对时延与带宽有着不同的需求 传统网络只进行转发 无法选择转发的目标路由器 并且无法全局统筹规划出合理的且符合业务需求的转发路径 所天津理工大学学报第 卷 第 期以不 同 的 业 务 流 无 法 得 到 服 务 质 量()上的保障 众多研究人员致力于研究新型网络体系架构 以便于解决传统网络中路由规划问题 软件定义网络()是网络虚拟化的一种实现方式 通过转发与控制分离 实现集中式网络资源分配和调度 使网络更加智能化 资源分配更加合理 旨在克服传统网络限制 重塑互联网并提高网络性能目前 研究发现各类智能算法性能突出 网络路由规划结合智能算法是当前研究的热点问题 国内外研究人员提出了多种 路由算法 郭荣梅等使用 条最短路径()算法计算出最小时延和最大可用带宽的 条路径 但 算法是基于 的传统算法 用于大型网络时会使处理速度慢 张德干等提出一种动态路由协议 与传统的路由协议相比 在递交率、平均跳数及端到端时延等方面均有较好的表现 尹凤杰等提出基于改进的蚁群多路径路由算法 可保证网络稳定且达到高利用率 但此算法收敛速度慢 会造成不必要的时延 且容易陷入局部最优解 李道全等提出一种基于流量分倾向度的多路径负载均衡路由算法 通过比较当前获得的链路 负载 选择最小负载的路径 但计算负载的同时会增加时间复杂度 徐啸等提出基于强化学习的多路径路由算法 在网络负载动态变化过程中实时选择最优路径 但同样存在时间复杂度高的问题 等提出一种基于深度强化学习的可扩展路由算法 以动态地调整加权求解最短路径 但在面对较为复杂的网络时 整体性能有所下降 等提出一种改进的分布式 路由算法 通过不同的 指标参数来选取最优路径 但在解决物理链路的可靠性、网络控制能力和单一控制平面的拓展性等方面还存较多问题 等提出一种自适应重新配置现有流量的路由算法 保证 路由性能 但在面对大型网络时 暴露出调度能力不足的问题 张志威等提出一种快速拓展随机树优化算法进行路径规划 当拓扑结构复杂时 算法效率降低 文献 基于遗传算法()对路由进行不同的优化 针对上述问题 遗传算法面对规模较大的复杂网络具有快速全局搜索的能力 但没有利用系统中的反馈信息 所以经常导致无用的冗余迭代和低计算效率 文献 基于蚁群()算法对 路由算法进行不同的优化 通过信息素的积累和更新 收敛到最优路径 然而 上述算法在一定程度上存在局限性 早期信息素的缺乏导致速度缓慢 易出现局部最优和盲目搜索等状态针对上述问题 遗传算法和蚁群算法可互补优缺点 发挥各自的优势 因此 文中设计了一种基于 的实时路由规划框架 并提出基于自适应遗传蚁群()的路由算法该算法可根据不同的业务需求 选择出合理的路径进行数据转发 在与遗传算法和蚁群算法评估对比后能在规模复杂的网络中起到较好的路由效果 试验结果表明:根据业务需求选择最优路径 能很好地保障路由 在根据时延需求业务进行规划路径时 时延小于 丢包率小于 在根据带宽需求业务进行规划路径时 带宽占用率远远小于理论值 基于 的实时路由规划框架 基于 的实时路由规划框架主要由控制器与底层转发设备组成 通过在控制器中部署相关检测模块和路由算法实现基于整个网络结构及状态的动态路由优化 进一步提高路由转发的整体性能 保障实时数据的传输 基于 的实时路由规划框架设计如图 所示图 基于 的实时路由规划框架图 转发平面中部署拓扑搭建模块 整体路由规划通过所搭建的拓扑进行测试及结果分析 年 月崔峻玮 等:基于自适应遗传蚁群算法的 路由规划研究控制平面中主要部署接网络感知、网络监控、接收模块、信息处理模块、路由规划、时延探测和资源分配 个模块 当具有 需求的业务流到达时 流的报文信息被发送到控制器 接收模块接收数据包信息 并将其发送至信息模块 信息处理模块主要记录各功能模块所采集的信息 以便各模块随时调用 资源分配模块根据信息模块中记录的网络状态信息进行资源的动态调整 并从全局的角度尽可能地满足所有流的要求 同时也将分配的信息存储在信息模块应用平面中部署前端显示模块 可将上述所有模块收集到的网络拓扑及链路信息 通过 反馈给前端页面进行显示 能反映当前网络的状态及拓扑连接情况 网络感知模块网络感知模块主要监控网络拓扑的变化 及时更新拓扑 获取网络拓扑信息、交换机端口信息及主机信息等 时延探测模块通过解析封装在链路层发现协议()数据包的时间戳信息 能获取 数据包经由交换机间链路的时间差信息结合 消息求出的控制器和交换机间的往返时间差 能计算出交换机链路间的传输时延 数据包与 数据包传输情况如图 所示图 获取链路时延原理图 交换机 与交换机 间的链路时延 为:()网络监测模块网络监控用于实时获取和分析网络的状态 对业务流流速 流表项、交换机端口性能和链路性能等数据进行统计 通过对参数采集和计算可得到剩余带宽 链路时延和丢包率等指标 并将相关信息发送到信息模块当中 路由规划模块在监听到网络协议()数据包时 会 根 据 报 文 头 部 的 服 务 类 型()字段针对业务的时延、带宽等 需求进行标记 该字段共有 位二进制数 前 位表示数据业务的优先级 位表示业务的需求 最后一位置 保留定义 其业务需求与 字段对照如表 所示表 业务需求 字段对照表 业务需求 字段最小时延最大吞吐量最高可靠性最小成本 前端显示模块前端显示模块需将当前网络拓扑显示在网页上并显示收集的交换机的信息和路径规划结果 该模块通过 控制器内置的模块获得 的接口 通过 的 库获得 接口返回的数据再通过 渲染该数据 返回给前端显示 路由算法设计 通过对路由机制进行研究 文中提出基于自适应遗传蚁群的智能路由算法 该算法将两种算法混合使用 通过遗传算法输出路径 作为蚁群算法的初始化信息素 利用遗传算法的快速全局搜索能力 加快 算法的收敛速度 同时也避免蚁群算法停滞在局部最优解状态 在遗传算法的基础上对蚁群算法进行优化 以保证改进后的算法能充分利用信息的正反馈效应 算法结合了两种算法的优点 在早期阶段可快速产生最优的解决方案 指标基于约束 路由是指从源节点开始 建立一条到达目的节点的路由路径 同时 该路径满足不同业务的路由约束条件 则 的参数定义如下:时延为:()()()()天津理工大学学报第 卷 第 期带宽为:()()()()式中:为全部可通信的链路 两个节点间存在一条可行链路 且 路径 为路径集合其路径 的边集为()遗传算法部分路由规划问题本质上是多条路径中求最优解的问题 遗传算法能在大量的解中求得最优解 将遗传算法应用在路由规划系统中能提高大型网络路由选择的收敛速度 且在同时处理群体中的多个个体时 能对解进行评估 减少陷入局部最优解的风险 染色体编码染色体编码采用优先级编码技术 在文中该染色体并不会表示一条传输路径 在通过解码后 染色体才会表示为一条传输路径 编码针对选择下一节点的不同优先级进行节点选择 该编码在染色体上的每个基因都不同 具备排列编码的特征 以一条染色体编码为例 加入 台交换机节点编号依次为 如图 所示图 优先级编码实例图 每个交换机节点对应 个优先级编码 中的 个基因 将该优先级编码定义为 条染色体 文中将遗传算法中的染色体定义为候选路径 条路径对应 条染色体 适应度计算适应度函数用来判断寻找到的路径的优劣 在遗传算法中优劣的判断至关重要 适应度函数是遗传算法中最关键的一步 对算法找到最优解有重大影响根据业务对时延和带宽占用率的影响程度 文中求解多条可行路径 路径 的适应度为:()()()()式中:路径 为路径解空间集合()为路径 的时延()为路径 的带宽占用率 和 为影响因子 其大小决定了不同业务适应度的影响程度 选择算子选择算子与自然界中的优胜劣汰类似 环境适应能力强的个体被保留下来 否则将会被淘汰 通过选择算子保留优秀的个体遗传或使用交叉算子生成下一代个体 交叉算子采用顺序交叉 随机选取位置交叉两个染色体的基因 以产生新的个体 变异算子该算子主要思想是将相对负载较大或断开的链路进行变异 使链路通畅如循环次数小于指定次数 则继续循环 循环结束将种群中的路径 按适应度从大到小排列 输出 条路径给蚁群算法 蚁群算法蚁群算法受蚂蚁觅食行为的启发式算法 在食物未知的情况下 许多蚂蚁开始寻找食物 当一只蚂蚁成功找到食物时 会释放一种信息素物质 因此 其他蚂蚁识别来自环境的信息素 从而逐渐专注于真正的路径 最终找到食物 算法初始化最大搜索次数为 初始搜索时间 值为 假设蚂蚁的数量总共为 所有路径上的信息素被初始化为常数 蚂蚁移动根据路径上的信息素浓度和链路状态 通过计算所有可达节点的概率 使蚂蚁移动到下一个节点()()()()()(其他)()式中:为蚂蚁的序列号 为蚂蚁 从当前节点 转移到可行节点 的概率 为信息素因子 为链路参数因子()为节点 和 间链路的信息素浓度()为节点 和 间链路的能见度 为尚未访问过的节点集合 更新信息素信息素更新规则为:()()()()()年 月崔峻玮 等:基于自适应遗传蚁群算法的 路由规划研究式中:为信息素挥发因子 为信息素浓度衰减系数()为在路径()上新增的信息素含量()()()式中:()为第 只蚂蚁在时间()内在路径()上留下的信息素含量()()()()式中:为信息素强度 和 为影响因子()为第 只蚂蚁在本次循环中所经过路径的时延()为第 只蚂蚁在本次循环中所经过路径的带宽占用率 算法设计 算法的主要步骤如下:()算法初始化()遗传算法通过选择、交叉和变异来模拟 次进化操作 得到 条更好的路径()记录 条最优的具体路径 将信息素等价分配给信息素矩阵中的相应路径()在网络中的节点上随机放置 个蚂蚁()将蚂蚁的初始起点放在集合 中 按照式()将每个蚂蚁移动到下一个顶点 然后将该路径添加到可选路径列表中 并将节点 加入集合 重复该过程 直至所有蚂蚁完成遍历()增加循环次数 将 赋给 如果 则结束搜索 进入步骤()否则 根据式()更新信息素浓度 并返回步骤()()输出最优路径自适应遗传蚁群算法流程如图 所示 算法可根据不同的业务需求求解最优路径 主要采用遗传算法 通过适应度中不同影响因子值决定业务需求 并从大量路径中选择所需业务的最优路径 遗传算法在求解过程的早期阶段比蚁群算法能更快地生成更好的解 然后 将信息素浓度分配给最优路径 信息素浓度包含时延和带宽占用率 根据不同业务更新信息素浓度 由于蚁群算法充分利用了反馈信息 所以 该算法可减少原始最大搜索次数更快地获得最佳路径图 自适应遗传蚁群算法流程图 算法评估 仿真环境建立 软件是用于算法开发、数据可视化、数据分析和数值计算的高级计算语言和交互环境文中在 上进行算法运行时间对比试验 将提出的 算法与蚁 群 算 法 和 遗 传 算 法 进 行比较 拓扑结构的结构源、目的节点间具有多条并行路径 因此 网络容错性能良好 不会出现单点故障 网络直径小 能保障流量对网络实时性的要求 拓扑结构规则对称 利于网络优化升级 邻接矩阵用于构建具有 个节点的 网络拓扑如图 所示 构造 节点网络的邻接矩阵 如式()所示 采用相同的方法构建拥有 个节点的二元 和拥有 个节点的五元 网络拓扑 种算法在不同规模的网络结构下进行仿真图 网络拓扑 天津理工大学学报第 卷 第 期 ()仿真结果与分析 蚁群算法仿真仿真模拟选择适当的蚂蚁数量和迭代次数 并记录运行时间 为确保数据可靠性 运行 次取平均值 对不同网络规模的试验数据比较 可看出蚁群算法在小规模的网络中是有效的 但如果网络规模迅速扩大 为保证结果的稳定性 需增加蚂蚁数量和迭代次数 算法时间会迅速增加 因此 对于大规模网络 蚁群算法的效率和稳定性并不高 遗传算法仿真仿真模拟选择适当的种群数量进化数 然后记录运行时间 对不同网络规模的试验数据比较 得出遗传算法的局部搜索能力较差 后期搜索效率会降低在种群数量足够的情况下 即使进化数增加 最短路径的平均长度不会有很大提高 因此 种群数量和进化次数的增加没有意义 导致遗传算法性能达到极限 算法仿真根据文中对遗传算法和蚁群算法的分析 算法减少了进化次数 在初始化前添加循环 对种群进行选择、交叉和变异 次 输出 个结果 其中包含最短路径 不同网络规模下 种算法的仿真结果如表 所示表 不同网络规模下 种算法仿真结果对比 遗传算法蚁群算法 算法节点数种群数蚂蚁数迭代次数最短路径长度 运行时间 算法对比分析比较不同规模的网络下 算法与其他两种算法的运行时间 算法的主要时间开销在遗传阶段 此该段要保证 个结果必须输出 条最短路径且其他路径不能重复 在迭代次数较少的情况下 蚁群算法阶段的时间成本较低在 个节点的小型网络中 可看到 算法在运行时间上比其他算法有优势 蚁群算法在小型网络中稳定且效率高 局部搜索能力强 遗传算法在小型网络中局部搜索能力较差 运行时间较长 如图 所示 在 个节点的网络中 使用 算法可得到更稳定的结果 运行时间明显降低 当网络结构复杂 蚁群算法容易陷入最优解图 节点网络运行时间的比较 遗传算法在复杂的网络中更容易提高搜索能力如图 所示 在 个节点的复杂大型网络中 年 月崔峻玮 等:基于自适应遗传蚁群算法的 路由规划研究算法不仅可取得更加稳定的结果 且花费时间明显降低 结合遗传算法的搜索能力强的特点 可输出多条可用路径 蚁群算法根据可用路径初始化信息素 提高收敛速度 所以 面对较大型的网络 算法的效果更明显 如图 所示图 节点网络运行时间的比较 图 节点网络运行时间的比较 试验分析 试验平台文中在 系统下搭建试验平台 控制器作为轻量级和高效性的控制器 可用于控制流表的下发等一系列操作 同时 也提供了搭建不同网络数据中心拓扑的功能 并需模拟各种业务流 因此 需用到 中的 工具模拟各种业务流 并对业务流进行实时监控 由于在不同规模的网络中进行多次仿真验证 所提算法具有相同的性能 因此 使用 搭建一个 节点的 网络 该网络架构链路冗余较好 并能模拟真实环境中接入网、承载网及核心网的 种层级架构 交换机 为接入层 交换机 为承载层 交换机 和 为核心层 按照网络拓扑的水平划分 将接入层和承载层间的链路改成 承载层和核心层改为 有利于模拟真实环境如图 所示图 试验网络拓扑图 路由算法相关参数设置仿真需对算法参数进行设定 参数的设定决定了所提算法的求解性能 依照不同业务需求参考多次试验结果 算法相关参数如表 所示表 算法主要参数 遗传算法参数设定值蚁群算法参数设定值初始种群数 蚂蚁个数 影响因子 信息素因子 影响因子 链路参数因子 交叉率 信息素挥发因子 变异率 信息素强度 输出路径 表 中 影响因子 代表()时延的权重 影响因子 代表()的权重 根据权重的大小决定输出对于业务需求的路径 当 时 说明需输出以时延业务为主的最优路径 当 时 说明需输出以带宽占用率为主的最优路径 基于时延业务 路由规划结果分析基于时延的路径规划测试结果 文中将 主机设置为服务端 主机设置为客户端 向 发送 数据包 并将 数据包中 数据报文中 段中的值设置为 前端页面显示了基于时延路径规划的最优路径 由 发送给 的 数据包经过 交换机节点到达 此时的路径为时延最小路径 时延为 丢包率为 天津理工大学学报第 卷 第 期如图 所示 针对时延业务路径规划结果分析 同样使用 工具进行模拟业务数据 将 作为服务器进行监控业务的参数 使用 连续发送 组 时延业务需求数据包进行测试图 基于时延业务的路由规划试验结果 算法的遗传算法部分会输出 条最优路径 可看出:路径 的平均时延为 路径 的平均时延为 路径 的平均时延为 路径 的平均时延为 路径 的平均时延为 根据时延的 需求 通过 路由算法选择最低时延路径 测试的结果分析如图 所示图 条路径的时延对比 在相同条件下 对遗传算法和蚁群算法进行时延业务路由测试 在路由过程中 时延越低表示通信质量越好 种算法迭代后输出的最优路径的平均时延均有降低 其中 算法迭代后时延最小 平均时延为 遗传算法和蚁群算法迭代后的时延较大 分别为 和 算法有效地降低了所需链路的时延 保证了链路对时延业务的 需求 时延对比如图 所示图 时延对比 基于带宽业务 路径规由结果分析基于带宽占用率的路由规划测试结果 将 设为客户机 将 设为 服务器 使 客户机向服务器发送 数据包 设计 数据包中 数据报文 段中的值为 前端页面同时显示切换后的最优路径 结果如图 所示图 基于带宽业务的路由规划试验结果 从图 中可看出 在传输过程中由带宽占用率 的路径 切换到带宽占用率 的路径 同时 也可观察到控制器实时根据占用率情况进行多条路径切换在连续发送 /的数据业务时 其网络当前最大的带宽占用率为 低于理论的 但在自适应遗传算法路由规划下 所有路径平均占用 年 月崔峻玮 等:基于自适应遗传蚁群算法的 路由规划研究率在以下 远小于理论的最大带宽占用率 算法会实时根据带宽占用率进行多条路径切换 因此 算法在处理带宽业务时能在规划路径中起到全局低带宽占用率的效果 如图 所示图 条路径的带宽占用率对比 在相同条件下 对遗传算法和蚁群算法进行带宽业务路由测试 在路由过程中 带宽占用率越低表示链路通信越好 链路的负载越小 种算法在迭代后输出的最优路径的平均带宽占用率均降低 且都低于 远小于理论值 其中 算法迭代后的带宽占用率最低 平均带宽占用率为 遗传算法和蚁群算法迭代后的平均带宽占用率分别为 和 算法有效降低了链路负载 保障了链路对带宽占用率业务的 需求 带宽占用率对比如图 所示图 带宽占用率对比 结论 由于传统网络资源管理难 传统路由算法已无法满足不同业务的 需求 文中设计了基于 的实时路由规划框架 并对各个模块进行分析实现 提出一种基于自适应遗传蚁群的 路由算法 结合遗传算法和蚁群算法的特点 在一定程度上加强了算法的整体收敛速度 通过将改进路由算法与基于 的实时路由规划框架相结合 对基于 的 路由规划进行了整体研究 该算法可根据不同业务需求寻找最优路径 有效降低网络时延与丢包率 提高链路利用率 解决网络拥堵的问题 从而保障网络业务的 需求 试验结果表明:算法在不同规模的网络下性能优于遗传与蚁群算法 算法在不同业务需求的 路由规划中 能更有效地找到所需 传输路径 且性能优于其他两种算法在进一步的研究中 可考虑在同一时间如有大量的数据包进行路由规划时 所提算法可能陷入局部最优解 算法还需进一步优化 文中使用 数据报文的报头 字段对业务需求进行区分 还可使用机器学习的方式提取业务特征来进行区分 后续研究将主要针对以上方面进行分析和探讨参 考 文 献崔峻玮 翟亚红 周婉旭 等.基于 的细粒度视频流量控制机制研究.湖北汽车工业学院学报 ():.吕勇 翟亚红 李鹏 等.基于 的新型车载网络架构研究.湖北汽车工业学院学报 ():.郭荣梅 胡小兵.求解时间窗口网络中前 条最短路径的方法.电子学报 ():.张德干 汤雅梦 张捷 等.一种面向移动物联网环境的动态路由新协议.天津理工大学学报 ():.尹凤杰 褚群森.基于改进蚁群算法的 路由研究.辽 宁 大 学 学 报:自 然 科 学 版 ():.李道全 黄泰铭 于波 等.基于流量分配倾向度的 多路径负载均衡.计算机工程与设计 ():.徐啸 顾玲丽 陈建平 等.一种智能多路径路由及子流分配协同算法.计算机工程 ():.天津理工大学学报第 卷 第 期 ./():./.():.:.():.张志威 贾云伟 王永霞 等.基于改进的快速扩展随机树的快速路径规划算法.天津理工大学学报 ():.陈磊 张颖.基于自适应遗传算法的 分簇路由方法.微电子学与计算机 ():.张举 王浩 罗舒婷 等.基于遗传算法的混合软件定义网络路由节能算法.计算机科学 ():.卢毅 徐梦颖 周杰.基于改进的免疫克隆蛙跳算法的多约束 路由优化研究.通信学报 ():.():.():.刘振鹏 张庆文 李明 等.基于蚁群优化算法的 路由策略.昆明理工大学学报:自然科学版 ():.龚娉婷 周金和.基于蚁群算法的 路由算法.计算机工程与设计 ():.王恭 孙铭阳 孙汇阳 等.基于自适应剩余能量阈值的 蚁群路由算法.西北工业大学学报 ():.魏德宾 刘健 潘成胜 等.卫星网络中基于多 约束的蚁群优化路由算法.计算机工程 ():.李罡 吴志军.基于多 约束条件的广域信息管理系统任务调度算法.通信学报 ():.():.作者简介:崔峻玮()男 硕士研究生 研究方向:智能网联、软件定义网络等:翟亚红(通信作者)()女 副教授 硕士 研究方向:智能网络、大数据等: