启发式规划算法下云边缘节点均衡调度仿真

杨裴裴,黄 燕,叶海智

(1. 郑州工商学院信息工程学院,河南 郑州 451400;2. 河南师范大学,河南 新乡 453007)

1 引言

随着科学技术的快速发展,互联网成为人类生活不可或缺的重要组成部分。作为由计算机技术和数字技术共同组建的高质量网络服务平台,互联网在对现代社会造成重大影响的同时,还被广泛应用于医疗卫生、机械制造、航空航天等多个领域。物联网计算又称云计算[1],即通过处理和生成超大数据集,实现整体用户资源共享。然而当下社会信息化强度的不断提升不仅加重了物联网计算的负担,还降低了用户资源利用率。为了将信息化时代下爆炸式增长的数据按目标需求弹性分配至各云边缘节点并顺利完成调度作业,相关人员开展对云边缘节点调度方法的研究。

林霄[2]等人通过将云计算平台的海量数据纳入SnF调度决策,促使布局散乱的离散化数据按决策需求排列成与所有网络节点相对应的跨数据中心网络场景。通过量化分析场景内计算复杂度较高的部分数据,并针对性提供实时调度服务,实现云边缘节点调度,该方法存在调度性能差的问题。沈学利[3]等人通过在异构资源环境下按数据量和任务数量减少节点备份任务,使集群节点在启动数量和作业完成时间两方面得到全面优化。通过将优化集群节点与自适应调度算法结合,获取基于任务特征的调度因子,实现云边缘节点调度。何贞贞[4]等人通过计算各任务间的数据流大小,确定节点可用资源与任务通信开销间的关联度,并参考关联度拓扑边权重,绘制针对节点调度任务的有向无环图,实现云边缘节点调度,上述两种方法存在负载平衡度低的问题。

为了解决上述方法中存在的问题,提出基于启发式规划算法的云边缘节点调度方法。

2 云边缘节点空间域建模

空间域建模是扩大网络生命周期、固定任意时间点网络瞬时状态的有力手段。因具备较为优越的节点汇聚能力和路由规划能力,空间域建模常作为设计方案被广泛应用于动态网络的静态片段分析中。就云边缘节点调度问题而言,如果单纯以网络结构为调度背景,则极易由于通讯干扰、链路传输模式不当和数据包丢失[5]等问题导致网络中参与调度的节点个数与节点集群总数不一致。想要弥补以上缺陷,获取观测结果更为精确的多汇聚节点调度背景,需要在考虑容量原则、工作负载合并原则和流量平衡原则的基础上,建立基于云边缘节点的空间域。参与调度的节点个数的计算公式如下:

(1)

式中,g表示数据链路的传输速率;n表示目标状态的后验分布;r表示节点迁移率;α表示期望最小累积损失;v2表示节点密度;β表示传感器能量信号强度。

节点集群总数的计算公式如下:

(2)

式中,∂i表示节点i的有效覆盖面积;dk表示节点k的无效覆盖面积;h表示传感器能量信号衰减度;j表示网络最大发射功率;δm表示网络载波频率;λ表示节点剩余能量。

由于时间具有连续性和不可逆性,因此单位时刻点在网络中有且仅有一种表现形式,即源节点线性延伸形式。相较于云中心节点,云边缘节点的低编解码复杂度[6]、通信半径[7]和能耗标准更低,这表示任意位置上的云边缘节点均不会每时每刻移动,且即便发生移动,其任意时间窗[8]的移动幅度也会因观测价值过低而忽略不计。这种类比静态片段的动态移动过程促使云边缘节点在度量动作好坏和确定置信状态两方面存在不容忽视的误差。节点动作好坏的度量公式如下:

(3)

节点置信状态的确定公式如下:

(4)

式中,b表示节点适应度值;ε表示全局交叉变异率;In表示历史观测动作;lnm表示目标状态;c′表示邻域节点之间的转移概率;B表示节点集群的总体能量利用阈值。

空间域[9]顾名思义,指的是由自变量像元组成的三维空间。将散落在不同阵列的云边缘节点视为自变量像元,根据调度需求和节点位置,按容量原则、工作负载合并原则和流量平衡原则将自变量像元映射至三维空间。容量原则、工作负载合并原则和流量平衡原则的表达式如下:

(5)

式中,u表示节点运行效率评价因子;ai表示邻域节点通信半径;ai+1表示休眠节点占总节点的比例;ω表示负载合并处理耗时;jm表示调度工作响应需求;φ表示节点内存的可用量;表示相互独立的流量平衡空间。

空间域拓扑结构如下图1所示。

图1 空间域拓扑结构

经过空间域建模的云边缘节点成功弥补通讯干扰、链路不当传输模式和数据包丢失所导致的传感器稳定性下降问题,并依靠自变量像元映射空间消除云边缘节点在度量动作好坏和确定置信状态两方面存在的误差,为后续云边缘节点调度奠定坚实的基础。

3 云边缘节点调度

边缘计算[10]作为热门研究话题,始终活跃在不同应用领域,尤其是计算机领域中。考虑到云端协作给网络用户[11]带来的低时延、高效率服务,计算机领域相关学者将云端协作视为在有限资源中创造无限价值的技术。云边缘节点调度隶属于云端协作技术的一项分支,是实现数据传输最小化、应用程序执行性能最大化的重要环节。传统的云边缘节点调度方法由于存在默认任务缺乏依赖性、任务执行过程中间断概率高等问题,无法发挥边缘资源的最大化功效,因此提出基于启发式规划算法的云边缘节点调度方法。

3.1 启发式规划算法

启发式规划算法是直观展现待解决问题可行解[12]与最优解偏离度,并根据经验构造给予待解决问题预计规划的一种自然体算法。在节点调度等网络规划中,启发式规划算法主要用于评估目标调度节点与目标调度终点的最优路径,其评估过程较为复杂,需同时考虑不同调度任务对CPU[13]、节点选择概率等因素的约束条件,因此在采用启发式规划算法调度云边缘节点前,应优先以云边缘节点空间域为基础,深入探讨不同调度任务对CPU、节点选择概率等因素的约束条件。

1)CPU

不同调度任务对CPU的约束条件可以理解为不同调度任务对于CPU的需求。以空间域中某一时刻一个云边缘节点接收到的来自上层网络的调度任务为例,想要在合理分配可用资源的前提下保留云边缘节点CPU可用量,需要读取这一次调度任务从起始时刻到终止时刻的全部CPU需求量。云边缘节点CPU可用量的计算公式如下:

(6)

CPU需求量读取公式如下:

(7)

2)节点选择概率

云边缘节点规模决定了调度任务搜寻目标节点的难度,随机数学[14]普遍认为,传统方法在执行云边缘节点调度任务时,其目标调度节点与目标调度终点的核心选择思路围绕随机分布理论[15]展开,这种不公平的选择方法降低了目标节点选择概率。启发式规划算法选择目标节点依赖节点上分泌的信息素,即通过搜索符合目标调度节点和目标调度终点的信息素,实现节点选择概率的大幅提升。随机分布理论的表达式如下:

(8)

信息素辨识公式如下:

(9)

3.2 节点调度

在确定不同调度任务对CPU、节点选择概率的约束条件的基础上,正式采用启发式规划算法调度云边缘节点。启发式规划算法框架如下图2所示。

图2 启发式规划算法框架

如上图2可见,启发式规划算法根据不同调度任务对CPU、节点选择概率等因素的约束条件选择合适的底层算法,并部署符合该任务需求的路径,通过反复优化调度可行解,降低调度可行解与调度最优解偏离度,实现云边缘节点调度。启发式规划算法的表达式如下:

V=tnj+tik*EUT

(10)

式中,tnj表示可分配节点阵列;tik表示最优路径解;EUT表示最小复杂不均衡度。

4 仿真与分析

为了验证基于启发式规划算法的云边缘节点调度仿真的整体有效性,采用MATLAB仿真软件进行测试。选择数量不一的三组节点(10×107、10×108、10×109)作为验证算法调度性能的试验对象。

分别采用所提方法、文献[2]方法和文献[3]方法调度三组节点,并对比不同方法选中节点、调度终点和调度轨迹与目标节点、目标终点和理想轨迹的重合度。不同方法的调度结果如下图3所示。

图3 不同方法的调度结果

如上图3可见,所提方法在调度三组数量不一的云边缘节点时,选中节点、调度终点和调度轨迹均与目标节点、目标终点和理想轨迹高度重合,说明所提方法面对任何数量的云边缘节点,均能遵循调度策略完成目标任务,即所提方法的调度性能较强。因为所提方法在调度云边缘节点前,优先获取不同调度任务对CPU、节点选择概率等因素的约束条件。文献[2]方法和文献[3]方法在调度三组数量不一的云边缘节点时,虽存在选中节点或调度终点与目标节点和目标终点重合的现象,但总体来看,两种方法几乎与目标任务完全背离,说明文献[2]方法和文献[3]方法面对任何数量的云边缘节点,均无法遵循调度策略完成目标任务,即文献[2]方法和文献[3]方法的调度性能较差。经上述对比,可知所提方法的调度性能明显优于传统方法。

负载平衡度是指算法将工作任务分配到多个操作单元(服务器)的能力。举例来说,计算机云平台仅有一个服务器,那么所有的节点调度任务均需要通过这一个服务器办理。在节点数量较少的情况下,一个服务器尚能支撑云边缘调度任务,但当节点数量增加时,为了将堆积在一个服务器的节点调度工作合理分配到其它服务器,需要降低单位服务器吞吐量,以达到加快任务执行效率的目的。

因能从侧面反映计算机集群、网络连接和磁盘驱动器对当前资源的分配能力,负载平衡度常作为度量指标判断算法执行性能。为了进一步验证所提方法的实用性,分别采用所提方法、文献[3]方法和文献[4]方法调度三组节点,并计算不同方法的执行时间和单位服务器吞吐量。执行时间和单位服务器吞吐量计算公式如下:

(11)

不同方法的负载平衡度如下表1所示。

表1 不同方法的负载平衡度

如上表1可见,随着节点数量的增加,所提方法执行节点调度任务所消耗时间始终维持在较低水平,且单位服务器吞吐量较高,说明所提方法的负载平衡度较高,能够将节点调度任务合理分配到各服务器,在保证单位服务器高吞吐量、高执行度的同时,提升云边缘节点调度效率。文献[3]方法和文献[4]方法的执行时间与所提方法存在较大差距,说明文献[3]方法和文献[4]方法的负载平衡度较低,无法将节点调度任务合理分配到各服务器,从而促使云边缘节点调度效率降低。经上述对比,进一步验证了所提方法的实用性。

5 结束语

近年来,人们对网络计算需求越来越高,现有的计算架构已无法满足网络用户需求。为了降低网络传输压力,相关人员投入到云边缘节点调度方法的研究之中。本文提出一种基于启发式规划算法的云边缘节点调度方法,经过仿真验证了该方法的调度效果。如何在保证云边缘节点调度性能的同时,对云边缘节点调度过程实时监控,是下一步工作的重点。