基于遗传算法的SDN 网络装箱问题研究*

何利文 张幸宁

（南京邮电大学 南京 210023）

1 引言

为了应对用户对于复杂网络环境下日益增多的请求，运营商对网络业务路径的部署提出了更高的要求。因此在有限网络资源中尽可能装载更多业务流量成为了当前评判网络状态的一个重要指标。当前运营商正处于向新型网络架构SDN 迈进的阶段，SDN 网路和传统IP 网络不同，其核心思想是将转发平面与控制平面相分离［1］。这使得SDN网络在流量监控和调度上比传统网络更有优势，并且更大程度实现网络自动化和虚拟化。这些特性使得新型网络架构SDN 在掌控网络流量以及负载均衡优化上有很大的优势［2～3］。

图1展示了一个基本的网络装箱场景［4］。先后部署了两条业务，第一条5M 业务是从A 到E，部署的链路为A-C-D-E。第二条10M 业务是从B到E，发现第二条业务无法部署。但整体网络带宽资源满足这两个业务所需带宽，此时需要对之前部署的第一条业务路径进行调整，使新增业务得以部署在网络中。调整方法是：业务1 的路径改为A-C-E，业务二的路径为B-C-D-E。

为了能够在大规模的网络中解决上述问题，引入了SDN网络装箱问题，调整已有的业务所在的通信链路，实现网络中带宽利用率的负载均衡的同时，部署新的业务，并且达到对原有网络中的扰动最小的目标。装箱问题是个多目标优化的NP-hard 问题，其求解是极为困难的，由于其目标解的搜索涉及解空间的组合爆炸［5～6］，传统优化方法难以求最优解的NP-hard 问题，因此本文采用遗传算法这类启发式算法求其近似解。

图1 简单网络装箱场景示意图

2 SDN网络下网络装箱问题建模

定义网络的拓扑模型，用G=(V，E，C) 抽象描述网络拓扑。V是网络节点的集合，E是网络链路的集合。集合C则是E的带宽以及其他的一些等约束条件的集合，这里简记为带宽C。集合A代表网络中的请求路径的业务，A={a1，…，ak，…，am}，设网络中已有m个业务。对任意k∈m，用三元组(sk，dk，bk)表示，其中sk，dk分别为业务k的起始节点和目的节点，bk表示业务k的带宽需求。的值为0或者1，表示业务k是否经过链路(i，j)，(i，j)∈E，hk为业务k的最大跳数限制，Cij表示链路(i，j)的容量，ω表示网络中的最大链路利用率。

优化目标：

其中式（1）以使最大链路利用率最小化以及扰动最小为优化目标，这样可以实现装箱问题的寻优；式（2）～（3）是限制条件；式（2）是链路上的最大负载限制；式（3）是对起始节点到目的节点的路径最大跳数限制；式（4）是对的整数限制，以及对ω的非负条件限制。

其中f1=ω表示网络中的最大链路利用率，f2=θ表示受到扰动的业务个数β占之前业务总数m的比例。将业务k所有满足路径约束条件的路由组成的集合称为业务k的备用路由集。当前网络中现有业务个数为m，记第k个业务的备用路径集为为第k条业务拥有的备用路径集元素的个数，表示业务k的第i条备用路由。用集合X表示网络中新增的φ个业务，其中，同理，根据每一个新增业务xf计算出的备用路经集为第f条业务拥有的备用路径集元素的个数，可以将装箱问题转化为求解最优化路由集：，满足式（1）优化目标，设其为方案p。用l表示链路(i，j)，Cl为链路(i，j)的带宽。

则方案p中某一链路段l的负载γp(l)和方案p链路利用率ωp(l)可分别由式（6）和式（7）计算得出。

在这种情况下，通过遗传算法可以求解出既满足负载均衡，又能满足新增业务部署的解决方案。上述优化问题本质上是从每一个多选择域（Qk）中选择正确的变量（pk），即多选择指派问题［7］，它是NP-hard 问题，人们通常采用启发式算法来求解现实生活中的NP完全问题。上述优化问题的特点是搜索空间大，所以我们考虑采用基于全局搜索能力强的遗传算法进行求解。

3 基于改进遗传算法的网络装箱求解

遗传算法（Genetic Algorithm，GA）是一类借鉴生物界自然选择和自然遗传机制的生物进化过程的模型，是一种通过模拟自然进化过程对解空间搜索最优解的方法［8～9］。遗传算法包括三个基本遗传算子：选择，交叉，变异。选择操作使得种群中优良个体得以保留，体现出“优胜劣汰，适者生存”。交叉可以创造出新的染色体解，避免遗传算法陷入局部最优解。变异操作模拟生物在自然界发生的基因突变，它以很小的概率随机地改变遗传基因值，使得遗传算法可以在初始组合之外的空间搜索，扩大了解空间［10］，也避免了陷入局部最优解。

3.1 适应度函数

装箱算法中，要求能够求同时控制整体网络的负载均衡以及受扰动业务个数，因此选取如下适应度函数：

式中，a 和 b 为权值，ω是带宽利用率，θ是业务受到的扰动率。将多目标的问题通过权重转化为单目标进行求解是解决多目标优化的一个有效途径。但是对于不同网络环境场景中，权重比例是不同的，为了能够实现比例系数的自适应变化，采用如下公式确定系数：

式中，p是种群规模大小，γ为负载率与扰动率二者的比例系数。为了避免个别较差或者较优的个体对最小带宽利用率以及扰动率带来的影响，求取γ时，采取去掉最好和最差的个体结果的策略。

3.2 染色体编码

遗传算法首先要解决的问题是把解空间的解编码成遗传解空间中由基因组成的染色体。本文采用自然数编码，编码长度只与业务个数相关，与业务的备用路径集中路径个数无关。一条染色体的基因是由各个业务的备用路径集随机选一条路径构成的。比如业务k 选择的备用集中的第i个路由，记为Rk，作为第k个业务选择的路由路径。则一条染色体由（R1，R2，…Rk，…，Rm）组成的。

3.3 选择操作

从种群中选择优胜的个体，淘汰适应度差的劣质个体的操作称为选择。选择为遗传算法向有前途的解空间搜索提供了动力［11～12］。本文采取的锦标赛方法具有收敛速度快的优势，可以在较短的时间内得到结果。设置比赛规模为2，每次从种群中随机选择两个个体构成一组，根据这个两个个体的适应度值，将适应度高的个体取出入选子代的范围，重复上述步骤，直到得到的个体数量满足新一代种群的规模［13］。

3.4 交叉和变异操作

自然界生物进化过程中核心的部分就是遗传基因的交叉变异。一般交叉概率在0.4～0.6 之间，变异概率在0.001～0.01 之间［14］，单纯采用固定的交叉和变异概率并不能根据种群状态变化而做出适时的改变，因此需采取自适应的交叉算子来保证上述要求。种群迭代前期，应适当加大交叉变异概率，有利于增加种群多样性，迭代后期交叉变异概率适当降低，增强种群收敛效率。此外为了保证种群多样性以及刺激表现差的个体，采用自适应的方法对表现差的个体施加更大的基因重组变异概率，表现好的个体给予保护，相应降低其发生交差和突变的概率。根据自适应规则，和分别代表个体i的交叉概率和变异概率，其自适应公式如下：

其中，pc1和pm1代表着交叉和变异的初始概率，gen 代表当前种群代数，maxgen 代表最大种群迭代个数，fi代表着个体i 的适应度值，c1和c1代表交叉率和变异率的比例系数，确保交叉率和变异率非负。随着代数增加，交叉变异的概率在降低，拥有更高适应度值的个体发生重组变异的概率也更低，在保护种群优秀个体的同时，保证了种群的多样性［15～16］。

改进遗传算法求解网络装箱的算法步骤如图2所示。

图2 网络装箱遗传算法流程图

4 算例仿真与分析

为了测试网络装箱遗传算法的有效性，模拟测试了在当前运营商主流的网络环境。通过配置不同网络规模，不同节点个数，不同业务个数等参数，并与其他主流启发式算法进行对比测试，验证本论文所提算法针对网络装箱问题的有效性。

在500节点网格网络中，网络规模为1910条链路，链路带宽在5G，6G，7G 中随机生成，请求业务的带宽分别为1M～200M 之间，分别测试了50 条业务、100 条业务、250 条业务、500 条业务以及 1000条业务情况下的装箱算法测试，设置遗传算法最大代数为100代。

图3 不同业务数量情况下三种算法耗时对比

从图3 实验数据可以看出，随着网络中承载的业务个数逐渐增加，算法执行所消耗的时间从整体上看也在增加，但从柱状图中可以看出在相同网络环境中，遗传算法耗费时间更少。

图4 不同业务数量情况下三种算法负载对比

从图4 可知，通过实验结果对比，可以得出在完成相同装箱任务的前提下，改进的遗传算法在负载均衡方面表现均优于蚁群算法和粒子群算法的结论。

图5 不同算法对网络装箱业务扰动比例的影响

图5 是基于1000 条业务，迭代5000 次获得的结果，可以看出遗传算法是这三种算法中收敛最快，优化效果最好的算法，其次是蚁群算法，最后是粒子群算法。

本文还模拟了在IPRAN 网络环境下的测试。IPRAN目前运营商广泛支持的一种网络，采取端到端的IP 化方式，使得运营商网络扁平化，简易化。省级IPRAN 由核心层，汇聚层，接入层组成。为检验在该网络环境下，多目标网络装箱算法的效果，构造出一个有5个核心环，100个汇聚环，1000个接入环的 IPRAN 场景，共 8280 个节点，18800 条链路的网络，装入500 条业务。每条链路带宽在5G，6G，7G 之间随机生成，每个请求业务的带宽在50M～5G之间随机生成。

表1 仿真结果统计表

在采用改进的遗传算法对省级IPRAN 进行网络装箱优化后，与其他启发式算法相比，所耗时间几乎减少一半，扰动率也下降了约83%。在相同收敛速度的情况下，遗传算法保持更高的优化效率。实验表明，无论是在小规模的网格网络中，还是大规模的省级IPRAN 网络中，本论文提出的网络装箱算法均能够保持较好的表现，成功实现了在部署新增网络业务的同时，也很好地控制了网络负载均衡问题。

5 结语

本论文是基于SDN网络，围绕在复杂网络环境下如何合理部署业务路径问题展开的。以网络装箱中扰动业务比例和负载均衡为目标建立数学模型，提出基于改进的遗传算法解决网络装箱问题的解决方案，通过对遗传算法的交叉变异算子进行自适应调整，提高了算法对多指派域问题优化的效果。实验结果证明，该方案与其同级别启发式算法相比，无论是在运算耗时上还是在优化负载和扰动率上，均表现出色。本论文所提方案能够为运营商提供更加便捷，高效的网络业务部署方案，从而降低运维成本，实现提高收益的同时，保障了企业和用户在复杂网络环境下的服务和需求。