基于模式融合的网络动态资源柔性调度仿真

姜 涛

(长春工业大学人文信息学院，吉林 长春 130122)

1 引言

移动网络教学是一种新型的学习模式，有助于实现开放式教学目标，为教学的全面展开奠定了基础[1]。由于网络资源的有限性，导致不能满足众多教育网络的需要，目前，移动网络中动态教育资源的有效调度，是移动网络面临的主要难题之一。

文献[2]提出基于蚁群算法的网络动态资源柔性调度方法，通过建立调度模型，构建基于Qo S的多目标优化调度函数，利用蚁群算法进行求解，但该方法的网络动态资源共享效果较差；文献[3]提出基于max-min算法的网络动态资源柔性调度方法，利用整数线性规划建立虚拟链路的动态带宽分配策略，在传统调度模型的基础上引入了数据流量在虚拟链路中的传输时延，并建立相应的5G网络资源调度模型。采用max-min算法，获得更好的调度方案，但该方法存在网络动态资源分配不均的问题。文献[4]提出基于遗传算法的网络动态资源柔性调度方法，将每个染色体视作独立的智能体，采用工序编码方式随机初始化每个智能体，结合多智能体协作与竞争理论设计了实现智能体之间交互作用的邻居交互算子，利用ASA对每个智能体开展局部寻优，引入遗传算法，选择动态调度与静态分配的使用方式，实现网络动态资源柔性调度，但该方法网络动态资源利用率较小，应用效果不理想。

为此，提出基于模式融合的网络动态资源柔性调度方法。明确移动中心网络结构，获取网络结构中节点负载和资源占有率，并以此得出适配因子，利用max-min蚁群算法自动调度资源，实现移动网络动态教育资源的均衡分配，提高资源利用率。

2 基于模式融合的网络动态资源柔性调度方法

2.1 资源调度原理

1)假设a为移动中心网络中节点数量，R为节点当前资源规模，则节点当前资源规模占据自身所能容纳总资源的比重为

(1)

式中，p代表节点当前资源规模占据自身所能容纳总资源的比重；n代表资源维度；b代表任务集合中互不相交的子集；x(k)代表节点的第k维资源量；d代表每个任务需要的资源。

2)假定e(i，j)为第i节点已经调度好的资源，则该资源与其它节点全部已经调度的资源量之间的比值f[e(i，j)]为

(2)

式中，g(i，j)代表节点待调度的资源；h代表资源均衡度；l代表资源负载度；mi代表第i个节点已经调度到资源量。

3)假定mi为第i节点已经调度到的资源，则各个节点的动态权值w为

(3)

式中，o代表剩余资源动态权值；Q代表资源的剩余值；S代表常数；t代表同资源对节点剩余负载能力的影响；u代表节点在加入任务后的资源均衡度。

4)假定z为总的请任务数，则节点的剩余负载能力Y为

(4)

式中，α代表请求任务集合数量；β代表每个任务所需要资源规模；δ代表节点对资源的容量；ε代表任务集合中每个集合任务数；φ代表总的资源数量。

5)假设σ为任意随机非负正整数；则可完成对动态资源均衡分配μ为

(5)

式中，v代表节点的负载权重。根据上述描述，可以明确移动中心网络动态资源调度原理。利用该原理，资源调度具体流程如图1所示。

图1 基于模式融合的网络动态资源调度流程

2.2 移动中心网络结构节点的分布

目前教育网络应用的拓扑结构多是以网络服务器作为转发设备来设计，此这类结构具有极高的可扩展性和二分带宽大等优势，但随着挖网络节点服务器的增多，均衡调度越加困难。为实现资源调度目标，本章节度对当前常用的几种移动中心网络结构，如HCN，DCent等，进行分析[5]。

一般情况下，为明确节点在移动网络结构中的分布，需要将拓扑结构转换为无向图模式。定义如下：假定移动中心网络拓扑结构G(V，E，φ)是由众多节点和链路构成的图，其中V、E代表节点的集合、链路的集合；φ是从E到无序偶集合上的函数。节点x，y之间存在边链路(x，y)，则x和y可以实现通信。

定义：网络拓扑结构G(V，E，φ)中有n个节点V=(v1，v2，…，vn)，则n阶方阵A(G)=aij称为G的邻接矩阵，其中

(6)

当i=j时设定aij=1。

以图2(a)HCN网络拓扑结构为例，矩阵表达形式如下

图2 节点分布示意图

(7)

根据矩阵表形式得到节点分布示意图，如图3所示。

图3 混合max-min和蚁群算法资源调度流程

2.3 确定适配因子

在整个移动网络结构中，各节点组成一个相当大的集群系统。该集群系统由一个中心节点和若干个计算节点组成，中心节点负责按照某种负载均衡策略进行任务请求的分配，计算节点任务请求的处理执行[6]。对于一个规模较大的集群系统而言，避免节点集群中仅有少量节点提供服务以至超载而其它节点处于空闲状态，平衡各节点之间的任务请求分配，成为该子议案共享中面临的关键问题。

1)节点负载状态确定

节点状态有三种：空闲状态、繁忙状态以及节点过载状态。其中，空闲状态是指节点都处在一种空置状态，相当于节点中没有任何负载数据；繁忙状态是指节点一直处在资源将近饱和的状态；过载状态是指节点已经处在满载状态，不能再接收调度的资源[7]。

对于网络节点负载状态的确定，目前有小波包、最小二乘支持向量机两种方法，但前者计算精度不够，后者计算过程较为复杂，因此将二者结合，提出一种混合预测模型。混合预测模型具体运行过程如下：

步骤1：网络服务节点初始化，清空节点中负载信息和样本空间。

步骤2：想节点中输入资源，并采集节点的负载值。

步骤3：将采集到的负载值生成负载序列值存放在样本空间中。

步骤4：建立节点负载估算模型。将上述结果输入到模型当中，进行模型训练。

步骤5：利用训练好的模型预测连接节点的负载值。

步骤6：将计算出来的节点负载值并发给负载均衡节点，用新的负载值来更新节点负载状态。

步骤7：误差判断。计算节点预测负载值与实际值之间的误差，若误差大于设定的阈值，则回到步骤4，重新训练样本；若设定的误差小于设定的阈值，则需要重复步骤5操作，直至得到较为准确的负载预测值[8]。

2)资源占有率确定

除了要明确节点资源占有率外，还需要明确各节点的资源占有率，才能得到适配因子，为后续资源调度奠定基础。

节点资源占有率是指节点现有资源在该节点总体资源使用能力中的比重，公式表示如下

(8)

式中，c为节点资源占有率；z为节点现有资源规模；v为节点总体资源使用能力。

3)适配因子确定

根据上述结果，计算二者之间的适配因子a，计算公式如下

(9)

式中，bi为资源处理权；e为增加匹配的可行性系数；d为节点负载指数。

2.4 混合模式实现资源调度

对于资源调度，常用的处理模式有蚁群算法、max-min算法、遗传算法、贪婪算法等，但均存在一些缺点，因此本文将其中两种单一模式结合在一起，实现优势互补，即提出基于模式融合的网络动态资源柔性调度方法，主要选用max-min算法和蚁群算法来完成[9]。

1)max-min算法

max-min算法是一种较为经典的调度方法，优点是简单，易操作，因此执行效率较高。基本原理过程如下：

步骤1：判断网络节点是否处在空闲状态。若处在空闲状态，则直接跳转到步骤7；若不是空闲状态则继续执行步骤2；

步骤2：将节点中现有资源映射到所有可用节点上，并求出最快完成该任务的时间。

步骤3：根据步骤2得到的结果，找出最早完成时间所对应的那个资源规模和所对应的节点。

步骤4：将资源映射到节点上，并将该资源从节点资源集合删除。

步骤5：更新节点的期望就绪时间。

步骤6：更新其它资源在节点上完成映射的时间，并回到步骤1。

步骤7：结束。

2)蚁群算法

蚁群算法是模拟蚂蚁觅食原理而构建的一种寻优方法，其基本原理如下：

步骤1：假定蚁群规模为M，其中每只蚂蚁都代表一种调度方案。

步骤2：初始化移动网络节点集群系统，并提供集群中所有节点自身的CPU个数以及处理性能等，这些记为集群节点的信息素[10]。

步骤3：利用初始化公式对集群节点的信息素初始化，得到初始信息素。

步骤4：收集各节点的资源信息。

步骤5：随机选取一个节点组作为资源调度的第一个节点，并根据其信息素计算出转移概率的大小。按照从大到小的顺序决定下一资源分配的节点[11]。重复本步骤，直至所有节点都调度完成。

步骤6：根据适配因子，筛选调度方案，并根据执行时间和负载均衡性，修改信息素，重复上述步骤，直至寻找到最优资源调度方案。

步骤7：结束。

3)混合算法

将上述max-min算法和蚁群算法混合在一起，实现网络动态教育资源柔性调度，基本流程如图4所示[12]。

图4 实验环境

通过以上步骤，将max-min算法与蚁群算法相结合，实现网络动态资源的柔性调度。

3 实验结果与分析

3.1 实验环境

表1 实验环境

3.2 实验平台

由C1oudSim搭建资源均衡调度仿真平台。平台操作步骤如下：

步骤1：初始化GridSim 库

步骤2：创建数据中心，在CloudSim仿真平台中，一个数据中心由一个或多个Machine组成，一个Machine是由一个或多个PEs或CPUs组成。

步骤3：创建代理Broker。

步骤4：创建虚拟机。

步骤5：创建云任务。

步骤6：启动仿真。

步骤7：在仿真结束后统计结果[12]。

3.3 移动网络节点分布

图5 移动网络节点分布波形图

3.4 结果分析

1)调度精度

为验证研究方法的网络动态资源柔性调度精度，在本次实验中，将文献[2]、文献[3]、文献[4]三种传统方法作为实验的对照组，与研究方法作对比，得到网络资源调度精度结果。

根据图6的实验结果可得知，对于移动网络整体区域来讲，研究方法的资源柔性调度效果是更好的，具有更高的调度精度。三种传统方法的调度精度最高为40%，这样的精度是无法满足实际应用要求的，说明传统方法具有较差的应用性。相比之下，研究方法的资源调度精度可以稳定在50～60%，研究方法不仅在精度上有所提升，且具有很好的稳定性。

图6 不同方法调度精度对比

2)资源利用率

由表2可知，本文调度方法运行下，资源利用率最后达到为95.77%。这一结果与基于三种单一模式的网络动态教育资源调度方法相比，资源利用率有了极大提高，由此证明了本文基于模式融合的网络动态资源柔性调度的有效性和可行性。

表2 资源利用率

3)负载均衡度

由表3可知，本文调度方法运行下，资负载均衡度最终达到为93.12%。而基于三种单一模式的网络动态教育资源调度方法运行下，负载均衡度达到88.14%、85.10%、90.12%。四种结果对比可知，本文基于模式融合的网络动态资源柔性调度方法调度效果更好。

表3 节点负载均衡度

通过上述资源利用率和负载均衡度两个指标结果，证明了本文方法能更改善资源不均衡现象，更有利于实现资源共享。