第38卷第2期______________________________计算机仿真_________________________________2021年2月
文章编号：1006-9348(2021)02-0291 -05
关于跨域虚拟网络的优化狼群映射研究仿真
司法考试历年真题及答案王珂琦，张耀
牛至(河南工业大学漯河工学院，河南漯河462000)
摘要：虚拟网络映射的目的是将网络底层物理资源，以高可用低开销的方式配置到虚拟网络中，进而提高物理网络的业务扩
展性能。针对分布式跨域带来的网络资源异构特性，现有映射算法往往存在节点或链路负载不均衡，资源开销过大，以及报
文抖动等问题，提出了优化狼群的跨域虚拟网络映射算法。由于跨域虚拟网络映射过程中，额外的资源开销主要来源于域
间，因此算法将映射处理分为域内与域间两部分进行独立分析。对于域内映射只引人元胞结构，增强单目标优化处理性能，
将节点采用二进制表示，并设定每一位作为一个元胞，建立节点元胞模型，通过更新元胞与近邻得到域内节点与链路资源的
最优配置；对于域间映射，则在元胞基础上，引入优化狼群算法，元胞结构提高搜索的分布能力，优化狼群提高全局寻优性
王连明
能，利用探狼四处游走，在元胞向量中搜索解，同时得到头狼信息，头狼产生召唤行为通知猛狼目标解的信息，从而利用分工
协作实现节点与链路最优解的搜索。仿真结果表明，提出的优化狼群网络映射算法能够有效应对跨域异构资源问题，均衡
节点和链路的负载，显著降低网络映射开销和网络映射执行时间。
关键词：跨域虚拟网络；网络映射；元胞；狼群算法；资源开销
中图分类号:TP393 文献标识码：B
Rearch and Simulation of Optimal Wolf Swarm
Mapping for Cross - Domain Virtual Networks
WANG ke - q i, ZHANG Yao
(L uohe In stitu te of T ech n o lo g y, H enan U niversity of T e ch n o lo g y, L uohe H en an462000, C h in a)
A B S T R A C T： T he p u rp o of v irtu al netw ork m apping is to configure th e u n d erly in g p h y sic al d ev ice reso u rces of th e
network into a virtual netw ork in a way of high availability an d low o v e rh e a d, th u s to. im prove th e rv ice sc alab ility
of physical netw ork. S pecific to th e heterogeneous c h a ra c te ristic s of netw ork reso u rces b rought by d istrib u ted cro ss -
d om ain, existing m apping algorithm s often hav
e problem s su c h a s u n b ala n ced load o
f nod es or lin k s, ex cessiv e re
source o v e rh e a d, a n d m essage jitte r. T h e re fo re, a cro ss -d o m ain virtual netw ork m ap p in g algorithm is p ropod to
optim ize wolves. B ecau in the pro cess of cross -dom ain v irtu al netw ork m a p p in g, ex tra reso u rce overh ead m ainly
com es from in te r - d o m a in, the algorithm divides th e m ap p in g p ro cessin g into two p a r ts, in tra-dom ain an d in te r -
d o m ain, for in d ep
e n d en t analysis. For in tra -dom ain m ap p in g, only cell stru ctu re w as in tro d u c e d, e n h an cin g the
perform ance of sin g le - objectiv e optim ization processing. T he no d es w ere rep re n ted in b in a ry,e a c h b it w as t as a
c e ll, an
d th
e node cell m odel w as estab lish ed. The optim al allo catio n o
f node and lin k reso u rces in th e d o m ain w as
obtained by u p d atin g cells and neighbors. For inter - dom ain m a p p in g, on th e b asis of c e lls, th e optim al w olf sw arm
algorithm w as in tro d u ced. C e llu lar stru ctu re im proves th e d istrib u tio n ab ility of s e a rc h, optim izes w olves an d im
proves global arc h perform ance. U sing w olf detection to w an d er aro u n d a n d arch for so lutions in c ell v e c to rs, the
inform ation of wolf h e ad c an b e o btained. T he wolf p ro d u ced ca lls to inform th e targ et of th e wolf. F in a lly, th e o p ti
m al solution of th e m ost nodes a n d lin k s w as arc h ed by m ean s of d ivision of lab o r an d cooperation. T he sim ulation
results show th at the propod optim ization w olf sw arm netw ork m ap p in g algorithm can effectively d eal w ith cro ss - do
m ain h eterogeneous reso u rces and b alan ce the load of n o d es an d lin k s. T he overhead of netw ork m ap p in g an d th e ex e
cution tim e of netw ork m apping are significantly red u ced.
收稿日期:2019 -07- 10修回日期:2019 - 09 - 01
—291—
K EY W O R DS：Cross - domain virtual network；Network mapping；C ell；Wolf swarm algorithm；Resource overhead
i引言
虚拟网络的作用是解决物理网络拓扑的僵化问题m，从
而使有限的物理资源能够满足更多的网络事务需求。而虚
拟网络映射，就是把物理资源准确有效的配置到相应的虚拟
网络上[^3]，完成功能扩展。随着分布式网络的发展，网络
忘乎所以是什么意思业务的运营一般不是由单一服务商独立支撑，而且物理网络
也并非处于同一位置，这就使得虚拟网络映射需要面对大量
具有异构与分布性质的跨域网络资源，同时对虚拟网络映射
算法提出了更高要求。
文献[4]分析了网络节点与邻近链路之间的资源差异，
采用k最小路径方式动态更新节点与链路资源，并得到链路
开销状况，该方法获得较好的映射率，并且能够在资源缺乏 时采取调整动作。文献[5]针对最优映射采用元胞遗传算法，定义了元胞自动机，并利用改进遗传优化元胞近邻的训练能力，从而提高算法的收敛速度与局部最优解的搜索性能，但是该方法缺乏对邻域模型的动态调整能力。文献[6] 针对跨域情况设计了分层分域的资源管理模型，将最低映射 开销作为最优解搜索，并引入蜂群改进寻优性能，取得
了较 好的网络请求能力，但是该算法复杂度过高，无法应用在网 络规模较大的场合。文献[7]也将网络映射转换为寻优问题，将单纯形算法与遗传相结合，从而避免遗传算法早熟。现有的研究算法，都针对虚拟网络映射的某个方面进行优化，并取得了一定程度的效果，但是缺乏对跨域本质区别的 考虑分析，不同域的网络之间存在信息的未知性，同时，任一 网络域都存在不止一个对外节点，对外节点选取的不同会产 生开销差异，为此，本文提出了关于跨域虚拟网络的优化狼群映射方法。该方法分别针对域内映射和域间映射进行分析，采用资源开销作为目标，引入元胞转换为寻优计算。由于域内映射产生的开销不大，因此对其进行快速处理，而域 间开销则加人优化狼群，增加元胞寻优的多样性与全局性，提高域间映射的有效性，降低域间开销。
2跨域映射模型
跨域虚拟网络的映射可以通过图1来描述。图中模拟 了三个虚拟网络域，它们分别由三个InPs建立。在任意的网 络域中，都包含/V类和类两种节点，它们分别代表各域中 的内部与边界节点。所谓的跨域网络映射，本质就是利用W 节点完成虚拟网络的搭建，并利用B节点实现跨域数据的传递。
通常物理网络可以描述为G,=(况，£,)，其中夂表示节点，戈表示链路。据此，采取无向图将虚拟网络描述为c… = (\,£,)，这里％ = |<，4,_"，<；丨代表虚拟节点集。进行 映射处理时，不仅应符合虚拟网络的要求，还应该尽量降低 物理网络中的资源消耗。假定将物理网络中的处理资源表—292 —示成)，且<e'，节点 <；与 <；的链路带宽表示成6(<，圮），于是映射处理时所需开销可以表示为2处理
n v eMQ
器剩余开销如下
= \c(n t) -^c(n v)(1)
n$ e nv eM^
这里的为处理器的所有可使用资源，是虚拟网络中所有节点集。同理可以得出可使用带宽为
R(e') =- Z K e J(2)
es^i e…eW f,
式中^表示全部带宽，^表示已使用的带宽。
ev eM$
根据处理器与带宽开销分析，在映射处理过程中，其虚拟网 络的开销是受限制的，据此，可以将虚拟网络构建所需的开 销表示如下
rc(n») «flv(M v(^))(3)
\b(e") ^R E(M E(e c))
另外，虚拟网络中心还需要具有切片功能，因此，在其中 一些节点中还应该加以限制
音乐教案网loc(n ,n v)r i
可以部署
i〇不可部署
(4)
当满足上述限制条件时，即认为映射为有效的，虚拟网 络中会出现若干映射情况，而本文针对跨域虚拟网络映射存 在资源分配不合理，开销过重，以及负载不均衡的问题进行 改进优化，为此，这里把跨域虚拟网络在实现映射过程中所 产生的负载情况描述如下
cos t(G") =a c(n ) + (1- a)工 B(e c)x length(e v)
n*>eNv e v eE v
(5) 3虚拟网络域内映射
为了建立域内节点模型，这里引人元胞概念，映射过程 中，假定将节点看作个体，则节点集合可以编码为％ = U
!,
…丨，其中的任意节点4均可以通过M 的二进制进
行描述，并把对应的每一位称作一个元胞。由于元胞适用于 离散系统，符合虚拟网络中域内节点的分布状态，在元胞基 础上，通过搜索虚拟网络最优开销作为映射优化目标。根据 映射模型，把采取无向图描述的网络请求转换成空间结构， 即对应到二进制位构成的向量矩阵上，也就是元胞矩阵，然 后不断的更新元胞与近邻。元胞状态的更新可表示为
/：s ;+, =A S 'X )
(6)
式中是元胞i 在时间》时对应的近邻元胞状态。这里设 定：当某死亡元胞存在三个非死亡近邻时，该元胞进行繁殖 操作，其它情况采取保持；当某非死亡元胞存在两个或者三 个非死亡元胞，该元胞采取保持，其它情况将该元胞杀死。 据此将更新规则描述为
i f = 0 then 5j +1
i f = 1 then Sj +,
i f j .s 1, =3i f
=2,3
(7)
网络底层资源始终处于动态变化，尤其在负载增加的情 况下，经常会出现节点非均衡现象，如果要实
现最大利益，就 应该尽可能缩减网络底层成本，同时也应该达到节点的均衡 性。因此本文将底层资源的配置设定为元胞繁殖动作，将回 收设定为元胞死亡动作，于是，更新操作可以进一步描述为
1, X s« = 4>5>6-7.〇, i f
#4,5,6,71，
= 1,2,3,4
,〇, i f J ^S 'N ^ 1,2,3,4
(8)
映射产生的节点成本固定不变，在采用的映射策略改变 时，影响的是所需带宽，于是，设计模型更新过程中的目标函 数如下
i f S J = 0 then S :+1 =
i f Sj = 1 then 5]+1 =
/ = Miniimize Y
^ f L x b (l uv)
(9)
(u,v ) e E y (i j ) e L s
其中，6(u
表示虚拟网络节点与〃之间的链路带宽资源；
/i .表示二进制向量，当/iL = 1成立，说明虚拟网络中节点“ 成功映射至底层的节点~当/i = 〇成立，则说明未实现映射 处理。为保证虚拟网络与底层之间的节点对应关系，设置限 定条件如下
r 1
K = 1
I f
l -
海市蜃楼什么意思I /L = -1, < = 1
(i 〇)
(i j ) e Z ，5
O '.Oe L g
L 0,
other
假定虚拟网络节点u 与r 依次完成了至底层；与y '节点 的映射处理，则U 与t ；对应的路径也会与底层路径形成对应 关系，因此通过上述连接限定，就能够控制底层节点间的 流量。
4
虚拟网络域间映射
4.1优化狼群算法
狼群算法在寻求最优解的过程中是利用分工合作机制
完成的，其中包含头狼，探狼，以及猛狼。探狼具有游走行 为，根据决策获取所需信息，同时得到头狼的位置信息。头 狼具有召唤行为，传递猛狼和猎物对应的信息。通过分工合 作机制达到信息搜索与传输目的，并实现捕猎行为，即最优 解搜寻。
在狼群算法处理时，假定狼群数量记作将位置％对 应狼的信息记作％(X ,)
，•••,<)，搜索到猎物资
源记作1=/(弋），则在解空间内，可以确定探狼％的范围
是
，其中a 代表探狼系数。当符合条件
时，使用该探狼作为头狼，同时执行召唤行为，当符合条件k <
时，令该探狼执行游走，设定步长为；哗,，保存游走时搜索到的资源信息，满足游走步数时再返回初始点，在游走 时探狼的位置可以描述为
+ r • sin (27r x
x stepd s (11)
n
其中d 表示游走的空间维度，P 表示约束次数，r e [-1,1]表示随机系数。游走行为发生过程中，得到的游走 点尸对应位置描述表示成
(p ) I ，计算出/(釺）对应的最大值y r 和资源k ，并不断确 定出资源所在位置信息，带到后续捕猎过程中。当头狼产生 召唤行为，猛狼接收召唤并集体朝头狼方向逼近，设定逼近 步长为wep 〖，则猛狼对应位置信息描述如下
xki l '
= + s t e P d b
• ((g d - x t i )/
1 1 ) (12)
这里d 为迭代A 次后头狼所处的位置信息，说/)〖•（（Z -4)/I Z -41)项描述猛狼的逼近。利用头狼％^和探
狼％的距离^进行后续行为的决策，当符合条件^时，进行捕猎，反之进行搜索，其距离阈值设定为
=
^
^ maXj ~ minj I (13)
其中的D 是维度，w 是阈值系数。4.2基于狼群优化的虚拟网络域间映射
对于跨域虚拟网络，要得到资源的最佳配置，除了分析 域内的链路与节点消耗外，还需要分析域间的消耗情况。由 于狼群算法具有出色的全局寻优性能，因此，引人狼群优化 算法，改进映射处理时链路与节点资源的全局性。在具有跨 域属性的虚拟网络中，M A N O 无法获知网络的详细信息，可
以利用竞价来估算出各个网络域的资源配置情况，也就是从 域间的链路开销与节点开销两方面采取配置分析。其中在 链路资源方面，采取启发算法，搜索出满足时间约束的有效 解。在节点资源方面，M A N O 能够保存S P 所请求的目标节 点，同时InPs 会把所在域中的可用节点及其对应资源与开销 通知服务中心，服务中心据此来建立竞价机制，并由M A N O
—293
—
系，如图2所示。根据结果曲线可知，随着虚拟网络节点数 量的增加，所有方法的映射开销均呈现增加趋势，其中两种 文献方法的增长速度近似线性，当节点数量达到一定值后, 很容易导致处理崩溃，而本文方法则近似于对数增长，当节 点数量急剧增加时，其映射开销也不会随之急剧增加，由于 从节点与链路两方面进行资源寻优，同时针对离散情况引入 元胞处理，有效提高了离散情况下最优解的寻求性能，能够 有效应对大规模网络场景。
老师对学生
图3
映射开销与网络域数置关系
图4所示为三种网络映射的执行时间结果，可以看出， 本文方法的执行速度要稍微领先于文献方法。这三种方法 均为改进方法，在引人算法时带来了算法与时间复杂度的增
10 15
20 25
30
虚拟网络节点数
量
图2映射开销与节点数置关系曲线
为了验证本文方法在跨域映射中的具体性能，仿真得出
映射开销与网络域数量之间的关系，如图3所示。实验过程 中，令虚拟节点与底层节点数量相同，仅让底层的网络域数
量发生改变。根据结果数据比较，当网络域数量发生改变
时，文献方法的映射开销均有一定程度的增加，而本文方法
的映射开销几乎保持不变，且始终小于文献方法的映射开
销。表明网络域的增加导致文献方法的额外开销，本文方法
由于针对域间映射做了处理，并引人狼群优化，结合元胞处
理，有效应对了跨域映射的寻优性能，合理处理了域内与域 间的节点、带宽资源，实现域间节点的资源均衡。
800
■本文方法 □文献[5]方法 □文献M 方法
完成节点的合理映射。
将虚拟网络节点作为元胞，所有节点对应的元胞组成一 组向量，向量的大小由节点数量决定，向量中任意分量表示 节点标识，不同的映射结果将产生不同的向量。另外，在映 射过程中，向量结果也将同步进行更新。更新的判定依据为 方向向量，其向量元素包含0和1，分别对应不更新与更新标 志。对于每种映射结果，为判定其优劣程度，设计目标函数 如下
/ =
LEN(u ,v )
x
BW(u ,v )
(14)
(u ,r ) e L y
这里的Lf /V U ，!；)代表链路（映射时对应的实际跳
数，代表链路带宽。根据该公式，利用域间节点的 映射情况计算出链路的目标函数，获取链路的适应程度。其 处理过程可以描述如下：
1)参数初始化，包括元胞向量，方向向量，狼群数量，以 及其它因子参数；
2〉随机选择头狼，并搜索出合理的探狼，进行游走，利用 方向更新节点元胞位置，得到新的元胞向量；
3) 求解映射的最小路径，利用猛狼感知，当1>1^^时,
令
=
并产生召唤信息，当（^时，令其保持嗅
探。即当判断映射发生链路故障，且未达到约定计数时，重 新返回上一步操作，当达到约定计数时，确定为映射不成功。
4)
利用目标函数得到适应度，并根据适应度衡量节点元
胞向量的优劣性，零局部演化4/； = 0，且=、… +1，采取
猎杀操作，对现有优势空间进行更新操作。
5) 再次更新元胞向量，求解链路最小路径，当成功实现
映射，跳回上一步，当未成功完成映射，同时又未达到约束计
数上限的，继续更新元胞向量，直至映射成功或者确定失败。
5
仿真分析
5.1仿真与参数设置
仿真采用G T - I T M 构建网络拓扑，其中设定InPs 数量 为5个，物理节点数量为100，物理链路数量为500，且网络中 InPs 提供给节点的资源满足[20,50]与[0,50]均匀分布，设
置虚拟节点形成链路的概率为0.5。另外初始化参数如表1所示。
表1
初始化参数
参数初始给定值
阈值系数(〇 = 500
步长系数S =800探狼系数 a =4
游走次数限定
T m a x = 25
5.2仿真结果分析
为了验证本文方法在虚拟网络映射中的实际性能，仿真 过程中，采用文献[5]与文献[6]中的方法作为对比。首先, 通过仿真，得到虚拟网络映射的开销与节点数量之间的关
500000500000500000500 3
3 2
2 1
1
班
电苌
隹获
E 000000
6
4
2
v d
—294
—
加，本文方法由于元胞空间的庞大，导致映射处理的中间变 量增加，但是元胞与狼群优化对于寻优和收敛效果的改进, 使得本文方法在映射时间上最终还是产生了一定的优势。
本
文
方
法
文
献
[5]方法文_方法
图4跨域虚拟网络映射执行时间
6
结束语
虚拟网络映射可以把物理资源配置到对应的虚拟节点
上，并在其上实现业务处理功能，避免网络底层资源受成本 和性能等因素制约。由于现有虚拟网络映射算法不能有效 满足跨域分布需求，本文提出了优化狼群映射算法。将跨域 映射问题分解为域内和域间两种情况进行分析。在跨域映 射时，主要资源开销在于域间，因此对域内采取快速处理，仅 引人元胞处理进行最优资源开销搜索。域间处理在元胞基 础上加人了优化狼群，增强全局搜索能力，从
而得到合理的 节点与链路资源分配。通过仿真，验证了本文方法在跨域情
(上接第209页）
通过实验分析得出，所提数值模拟结果真实有效，在满足施 工要求的同时又极大程度的保障工程安全性。但由于锚固 存在群锚固支护与单锚固支护的分别，而该方法无法做到对 单体锚固支护进行精细的模拟，因此下一步需要研究的课题 即：在该算法的基础上，添加细分算法，依靠该算法将整体锚
固支护，划分成多个单一锚固支护，进而完成对单一锚固支 护的数值模拟。参考文献：
[1] 王刚，韩伟，刘传正，等.预应力锚杆-围岩耦合模型时变效应 分析[J ].中国公路学报，2018,31(10) :311 -319.
[2] 李学君，曹善鹏.基于FLAC 〜（3D )的区段煤柱合理留设及锚
杆支护研究[J ].煤炭技术，2020,316(4) :69 - 72.
[3] 纪海玉，张琰岽，张杨，等•近距离采空区下煤巷顶板预应力全
锚索支护技术研究[J ].矿业研究与开发，2020,238(5) :93
-
97.
[4] 陈登国，高召宁，赵光明，等.基于锚固力学效应巷道围岩稳定
性分析[J ].煤炭学报，2020，45(3):1009-1019.
[5] 毕卫国，郭伟娜，林登阁•千米深井中央泵房围岩支护数值模
拟分析[J ].煤炭工程，2019,51(5) :129 -133.
[6]
单仁亮，鲍永生，原鸿鹄.厚顶煤巷道顶帮整体锚固支护体系
况下，有效降低了网络映射开销，且资源开销受网络域数量的影响很小，同时也降低了网络映射的执行时间。参考文献：
[1] 王轩，杨龙祥.多域虚拟网络映射算法研究[J ].计算机技术
与发展，2018,28(7): 134 -139.
[2] Mijumbi R , Serrat J, Gorricho J, et al. A path generation approach to embedding of virtual networks[ J ]. IEEE Transactions on Network and Service Management, 2015,12(3) ： 334 -348.
[3] Zhang Min, Tang Xi Jie. Hop - limit path mapping algorithm for virtual network embedding [ J ]. Wireless Personal Communications, 2016,95(3) ：1 - 16.
[4] 高斐，陈德礼，洪家军，等.基于k 最短路径算法优化与负载均
衡的虚拟网络映射机制[J ].计算机工程，2018,44(5) :146
-
154.
漆书[5] 王明，庄雷，王国卿，等.基于元胞遗传机制的虚拟网络映射算
法[J ].计算机科学，2018,45(12): 66-70,103.
[6] 贾伟，夏靖波.跨域虚拟网络映射问题研究[J ].电子与信息
学报，2016,38(3) :728 -734.
[7] 刘佳，宋涛，胡颖，等.基于混合遗传算法的虚拟网络映射方法
研究[J ].小型微型计算机系统，2016,37(4) :773 -777.
[作者简介]
王珂琦（1981 -，男（汉族），河南省漯河市人，硕
士，讲师，研究方向：计算机。
张耀(1987 -)，男（汉族），河南省漯河市人，硕
士，讲师，研究方向：计算机。
研究与应用[J ].煤炭科学技术，2018,46(4) :93 -99.
[7] 言志信，屈文瑞，龙哲，等.地震作用下锚固参数对岩体边坡锚
固界面剪应力分布影响分析[J ].岩土工程学报，2018,40
(11) ： 2110-2119.
[8] 徐江，肖仕周，龚维明，等.锚碇深基坑施工过程数值模拟及安
全监测研究[
J ]
•施工技术，
2018,47(7) :20 - 25.
[
9
]
白海峰，刘奇.三维强震下路堑高边坡预应力锚索加固分析
[
J ]
•铁道工程学报，
2018,35(11) :11 -15.
[10] 郭兵兵，纪炎涛，刘德峰.大跨度巷道锚杆锚索联合支护设计
数值模拟研究[J ].化工矿物与加工，2018,47(8) :31 -34.
[11] 张驰，彭张，冀虎，等.基于B L S S -P E 与FLAC3D 耦合建模技
术的采区溜井稳定性分析[J ].有色金属工程，2020,10(2):
92-99.
[12] 刘宏伟.大跨度预应力混凝土桥梁裂缝加固监测仿真[J ].
计算机仿真，2019,36(2): 410 - 413,467.
[作者简介]
盛晓杰（1985 -)，男（汉族），四川苍溪人，硕士研
究生，讲师，研究方向：岩土工程。
陆汉光（1983 -)，男（汉族），重庆大足人，硕士，讲
师，研究方向：地基及边坡处理、绿色建筑（通讯作者）。
8
6 4 2
<
6
4 2
0—295
—
