基于GSA算法的WVN资源映射数学模型
2022-05-14王晓霞郑大钊
王晓霞，郑大钊
(齐齐哈尔大学理学院，黑龙江齐齐哈尔161005)
1 引言
虚拟网络资源映射是网络虚拟化技术的重要部分，虚拟网络资源映射是将移动网络中的虚拟网络映射至物理网络中，依据固定映射算法分配移动网络物理资源，令网络资源实现良好分配[1-3]。通常将映射成功率、收益与开销设置为网络资源映射目标。目前，网络结构存在较大缺陷，容易出现网络僵化问题，严重影响互联网技术发展。网络缺少地址资源、无法充分利用网络资源等情况严重影响了网络发展。
众多研究学者提出资源预留等技术虽对资源利用问题有所改善，但仍无法从根本解决网络僵化问题。朱国晖[4]等人提出一种基于两次优先级排序的虚拟网络映射算法，首次排序中，计算请求优先级，判断虚拟网络映射顺序，二次排序中，依据链路权重获取优先级，结合两次排序对最佳映射路径进行计算。实验结果表明，该算法有效降低了网络请求的等待时间，但是存在剩余带宽和请求接受率较低的问题。王明[5]等人分别将两次优先级排序方法以及元胞遗传机制应用于虚拟网络映射中，但是该方法存在底层链路利用率和部署成本较高的缺陷。
针对传统方法存在的问题，研究基于GSA算法的无线虚拟网络资源映射数学模型，GSA算法是遗传算法与模拟退火算法结合的算法，广泛应用于求解最优化问题中。建立无线虚拟网络资源映射数学模型，利用GSA算法实现模型高效求解，获取最优无线虚拟网络资源映射结果。
2 无线虚拟网络资源映射数学模型
2.1 网络模型
1)物理网络
选取带权无向图GS=(NS，LS)表示物理网络，其中，NS表示物理节点集合，LS表示链路集合。利用节点位置、信任度以及CPU资源表示物理节点nS∈NS的属性。loc(ns)与cpu(ns)分别为节点地理位置以及可用CPU资源；二维节点坐标用(xs，ys)表示；trl(ns)为节点信任度等级，trd(ns)为节点信任度需求。用带宽lS∈LS表示物理链路属性，可用带宽资源用b(ls)表示。
2)虚拟网络请求
用VNR(t)=(Gv，t，td)与GV=(NV，LV)分别表示时间为t时虚拟网络请求以及虚拟网络拓扑，其中，td与NV分别表示虚拟网络生存时间以及虚拟节点集合，LV表示虚拟链路集合。cpu(nv)表示虚拟节点资源需求，trl(nv)与trd(nv)分别表示虚拟节点信任度等级以及信任度需求；D(nv)与loc(nv)分别表示可最远被映射至位置需求的距离以及虚拟节点地理位置需求，虚拟链路带宽资源需求用b(lv)表示。
3)安全虚拟网络映射
2.2 映射目标
底层物理网络在无线虚拟网络资源映射过程中需满足成本最小需求，实现最大化虚拟网络请求的映射，增加物理网络供应商收益以及资源利用率[6]。将虚拟网络请求接受率、物理网络映射收益以及物理网络映射成本作为无线虚拟网络资源映射目标。
1)映射成本以及映射收益
时间为t时，VNR(t)映射收益表达式如下
(1)
根据式(1)可以看出，虚拟网络资源需求总和即虚拟网络请求映射收益[7]，在信任度需求提高的条件下，虚拟网络映射总收益的安全收益有所提升。
时间为t时，VNR(t)映射成本表达式如下
(2)
2)虚拟网络请求接受率
在固定时间段T内，总虚拟网络请求数量与虚拟网络成功映射请求数之比即虚拟网络请求接收率，其表达式如下
(3)
式(3)中，VNR表示达到的虚拟网络请求总量，VNRsuccess表示时间段T内成功映射的虚拟网络请求数量。根据式(3)可以看出，固定时间段内，虚拟网络请求接受率越高，成功映射的虚拟网络请求数量越高[9]，且无线虚拟网络资源总映射收益越高。
2.3 建立数学模型
将虚拟网络映射成本最低作为映射目标，满足无线虚拟网络资源映射安全需求以及资源需求作为约束，利用混合整数线性规划模型表示无线虚拟网络资源映射问题，建立目标函数如下
(4)
式(4)中，nj表示底层节点，ni表示虚拟节点。
设置约束条件如下：
1)节点CPU资源约束
∀ni∈Nv，∀nj∈Ns，令
(5)
利用式(5)令虚拟节点CPU资源需求小于物理节点可用CPU资源。
2)节点映射位置约束
(6)
3)链路带宽资源约束
(7)
4)链路连通性约束
∀nj∈Ns，∀luv∈Lv，令
(8)
5)节点信任度安全约束
∀ni∈Nv，∀nj∈Ns，令
(9)
式(9)中，Φ(nj)表示承载于物理节点nj中的虚拟节点集合。
6)同一物理节点不可映射差异虚拟节点
(10)
7)同一物理节点仅可映射一个虚拟节点
(11)
8)变量域约束
(12)
(13)
2.4 基于GSA算法的资源映射实现
GSA算法是遗传算法与模拟退火算法结合的组合算法，利用GSA算法可快速获取无线虚拟网络资源映射数学模型最优解，采用GSA算法求解无线虚拟网络资源映射数学模型流程如下：
1)编码
选取顺序编码方式对无线虚拟网络资源映射节点号码以及物理网络节点实施编码。
2)参数初始化
用MaxPOP表示群体规模，k表示迭代次数，tk与POP(k)分别表示初始温度以及群体，对以上参数实施初始化[10]，设置POP(k)内包含符合约束条件的可行解。
3)模拟退火操作
符合所设定终止规则时，终止运算；设染色体i存在于群体POP(k)中，随机选取状态j∈POP(k)，可得该操作接受概率如下
(14)
当f(j)
4)选取种群
新种群内个体适应函数表达式如下
(15)
式(15)中，fmin表示最小目标函数值。依据通过式(15)所获取的概率分布随机于新种群个体中选取染色体，利用所形成染色体生成新种群NewPOP(k+1)。
5)交叉与变异
将交叉概率Pc依据遗传算法交叉操作获取CrossPOP(k+1)，通过变异操作变异率Pm获取MutPOP(k+1)。选取不变位法实施交叉操作过程如下：形成可表示父代个体需交叉基因的二进制向量，所生成二进制向量存在相同维数染色体编码，用1与0分别表示不变以及需要改变的基因，不变基因以及变化基因分别遗传到子代。
采用逆序变异法实施变异操作，首先需明确待变异父代，逆序操作随机选取的基因位生成新染色体。
通过自适应遗传算法交叉以及变异操作获取交叉率以及变异率公式如下
(16)
(17)
以上公式中，0≤ki≤1，Fmax与Favg分别表示群体最大适应度以及平均适应度；F与F′分别表示交叉个体中较大适应度以及将变异的个体适应度。
6)退火操作
设置tk+1=d(tk)，k=k+1，POP(k)-mutPOP(k)，转回至步骤3)。存在下降温度个体时，需采用以下公式处理：
tk+1=tk(1+σtk)-1
(18)
式(18)中，退火系数σ求解公式如下：
(19)
式(19)中，tf与N分别表示固定值以及可下降温度的最大次数，选取非时齐算法获取不同温度下的迭代次数。
通过以上过程求解无线虚拟网络资源映射数学模型，完成无线虚拟网络资源有效映射。
3 模型测试
为了验证基于GSA算法的无线虚拟网络资源映射数学模型的有效性与全面性，选取GT-ITM软件生成底层物理网络拓扑，该网络拓扑结构中包含节点数量为20个，各底层物理节点处理能力处于[100，200]个单元间，各物理链路带宽资源处于[100，200]个带宽单位间。设所建立物理网络拓扑中各网络请求功能数量处于2-16间。
统计采用本文模型实施无线虚拟网络资源映射处理时间结果如表1所示。
表1 网络功能处理时间
表1实验结果可以看出，采用本文方法可实现无线虚拟网络资源有效映射，且映射所需处理时间较短。
选取两次优先级模型(参考文献[4])以及元胞遗传模型(参考文献[5])作为对比模型，采用不同模型实施无线虚拟网络资源映射部署成本对比结果如图1所示。
图1 部署成本对比
图1实验结果可以看出，采用本文模型实现无线虚拟网络资源映射，不同迭代次数情况下的部署成本均为最低。采用本文模型实现无线虚拟网络资源映射，不仅可有效满足资源映射的业务需求，而且可降低移动网络运营商成本，提升运营商收益。
统计采用三种模型实现无线虚拟网络资源映射，虚拟网络中不同网络功能节点数量时所使用物理节点数量，统计结果如图2所示。
图2 物理节点数量对比
图2实验结果可以看出，随着虚拟网络中所包含网络功能节点数量的提升，三种模型的底层物理节点数量均有所提升，但是本文模型的底层物理节点数量低于传统方法。说明本文模型所需底层物理节点数量较少，再次验证本文模型可降低虚拟网络部署成本，节省运营商运行成本。
统计不同网络功能节点数量时三种模型的平均底层物理链路利用率，统计结果如图3所示。
图3 物理链路利用率
图3实验结果可以看出，随着网络功能节点数量的提升，不同模型的底层链路利用率均有所提升。采用本文模型映射无线虚拟网络资源，在不同网络功能节点数量情况下，底层链路利用率均明显低于另两种模型。本文模型可有效节省底层链路利用情况，提升无线虚拟网络资源映射有效性，节省映射资源。本文模型底层物理链路利用率较低，可避免网络出现拥塞情况，网络应用终端连接数量多以及节点密度大时，仍具有良好的传输性能。
统计不同网络功能节点数量时三种模型实施无线虚拟网络资源映射的剩余带宽资源，对比结果如表2所示。
表2 剩余带宽对比
表2实验结果可以看出，本文模型在不同网络功能节点数量时剩余带宽均明显高于另两种模型，剩余带宽均高于80%；另两种模型在不同网络功能节点数量时剩余带宽均低于80%。对比结果有效验证本文模型映射无线虚拟网络节点剩余带宽较高，这是因为本文模型采用GSA算法具有较高的计算效率，可快速获取最优解，具有较高的运算效率，可实现无线虚拟网络资源良好映射。
统计不同网络功能节点数量时三种模型的虚拟网络请求接受率，对比结果如表3所示。
表3 请求接受率对比
表3实验结果可以看出，本文模型可为所映射虚拟网络良好分配资源，初始映射时具有较高的物理网络可用资源，因此三种模型的虚拟网络请求接受率均较高。随着网络功能节点数量的增加，三种模型的虚拟网络请求接受率均有所降低，采用本文模型实施无线虚拟网络资源映射，不同网络功能节点数量时虚拟网络请求接受率均高于92%，验证本文模型具有较高的映射性能。
4 结论
构建无线虚拟网络资源映射数学模型，充分考虑信任度问题，提升无线虚拟网络安全性。选取GSA算法实现模型高效求解，通过实验验证所研究模型可有效实现无线虚拟网络资源有效映射，该模型在映射收益、请求接受率等方面均具有较高的优势，体现了该模型的映射效率。所研究模型可有效改善以往无线虚拟网络资源映射所具有的映射效率低的缺陷，可满足5G移动网络多样化应用场景需求。
