Page 31 - 网络电信2018年5月刊上

解 决 方 案

式中：η表示虚拟链路总的传输时延。式（5）表示带宽 13、else
动态分配的目标，即最小化总传输时延；式（6）确保从一个虚 14、t' ij -1=starting_time_link(T,T',Z,k)
拟机流出的所有链路带宽之和不大于该虚拟机的流出带宽；式 15、t ij =starting_time_VM(T,T’,Z,k)
（7）确保流入一个虚拟机的所有链路带宽之和不大于该虚拟机 16、endif
的流入带宽。 17、endfor
算法的第1-2行表示，由染色体得到虚拟机之间的链路分
二、联合遗传和禁忌搜索算法(GATS) 配，根据链路带宽分配模型，执行整数线性规划算法，求得虚
根据上述虚拟网络功能调度模型，虚拟网络功能调度问题 拟网络中各个虚拟机之间的链路带宽。第3-7行表示，得到基因
可看做是柔性车间调度问题的扩展，该问题是NP难问题，引入 o的服务功能链序号、虚拟网络功能序号和分配的虚拟机序号。
动态的链路带宽分配后，进一步增加了其复杂性，因此在多项 第8-12行表示，求解得到相应虚拟网络功能f ij 在虚拟机中开始
式时间内无法利用传统方法求得精确解[7]。为了有效的解决虚 处理达到数据流的时间t ij 和在虚拟链路中开始转发数据流的时
拟网络功能调度问题，本文设计了一种联合遗传算法（genetic 间t' ij ，最终得到可行的调度方案。
algorithm，GA）和禁忌搜索（tabu search，TS）的启发式算 2、适应度计算和选择
法（GATS），通过利用遗传算法的全局搜索能力和禁忌搜索的 染色体的适应度值为所有服务功能链请求完成时间δ的倒
局部搜索能力，能够得到更优的调度方案。 数，如式（9）所示。
1、染色体编码和解码
采用多层编码的方法对染色体进行编码，每个染色体表示 （9）
一种虚拟网络功能调度的可行解。染色体的长度为 ，对于
任意染色体，其基因被分为2部分，第一部分表示虚拟网络功能 对于任意染色体，计算其适应度值，然后采用轮盘赌法进
的调度顺序，第二部分表示实例化相应虚拟网络功能的虚拟机 行排序，个体的选择概率如式（10）所示，其中NIND表示种群
的序号。 个数。
C i =[322131231231421324] (8) (10)
式（8）给出了相应的染色体编码示例，该染色体中包含3
条服务功能链，每条服务功能链由3个虚拟网络功能构成，共有
4个虚拟机实例化所有虚拟网络功能。 3、交叉
前9位基因表示虚拟网络功能的调度顺 种群通过交叉获得新的个体，从
而推动整个种群向前进化，交叉操作
序，可被解码为f 31 →f 21 →f 22 →f 11 →f 3
2 →f 12 →f 23 →f 33 →f 13 ，后9位基因表示 采用整数交叉法。首先，从种群中随
实例化前9位虚拟网络功能的虚拟机序 机选择两个染色体，并取出每个染色
号，可解码为，其中M f31 (2)→M f21 (3)→ 体的前 位基因，然后随机选择交
叉位置进行交叉。交叉后生成新的染
M f22 (1)→M f11 (4)→M f22 (2)→M f12 (1)→M f
23 (3)→M f33 (2)→M f13 (4),其中M f31 (2)为 色体中，一些服务功能链中会增加虚
可实例化虚拟网络功能f 31 的虚拟机节 拟网络功能，有些服务功能链会缺少
点集合M f31 中的第2个元素。当完成染 虚拟网络功能，因此，把增加虚拟网
色体编码后，需要将其解码，以生成 络功能的服务功能链序号调整为缺失
可行的调度方案。下列伪代码表示相应的解码 虚拟网络功能的服务功能链序号，并按照交叉前相应虚拟网络
算法： 功能的虚拟机分配来调整个体 位基因，方法
1、输入：染色体c 如图2所示。例如，交叉位置为5，交叉两个染色体c 1 和c 2 的前4
2、输出：可行的调度方案{t ij ,t' ij ,x ijk } 位基因获得c 3 和c 4 。交叉后染色体c 3 上出现了2个问题：一是服
3、定义：T={t ij },T'={t' ij },Z={x ijk } 务功能链s 1 缺失一个虚拟网络功能而服务功能链s 2 上增加了一
4、根据c计算每个虚拟机的路由 个虚拟网络功能；二是虚拟机分配与虚拟网络功能的调度顺序
5、根据动态链路带宽分配模型，执行整数规划算法进行链
图2 染色体交叉过程
路带宽分配
6、for从前往后选择c中的基因odo
7、i=get_service(c(o))
8、j=get_function(c(o))
9、k=get_VM_node(c(o))
10、X ijk =1
11、i fj =1 then
12、t ij =starting_time_VM(T,T’,Z,k)

52 网络电信 二零一八年五月