基于改进蚁群算法的电力云数据中心任务调度策略研究

孙湛冬，焦 娇，李 伟，李志鹏，李鹏恩

基于改进蚁群算法的电力云数据中心任务调度策略研究

孙湛冬1，焦 娇1，李 伟1，李志鹏1，李鹏恩2

(1.北京电力经济技术研究院有限公司，北京 100055；2.北京恒华伟业科技股份有限公司，北京 100011)

针对现有云环境下电力数据中心任务调度的高能耗、低效率等问题，在电力云体系结构的基础上，提出了一种基于随机Petri网的云数据中心任务调度模型。通过综合考虑时间约束、负载、能耗约束对蚁群算法进行改进，并通过改进算法对模型进行求解。通过实验对运行时间、能耗、平均等待时间、系统负载等几个方面进行了比较分析，验证了该方法的优越性。结果表明，改进蚁群算法在保证性能的前提下，可以有效降低数据中心能耗，为电力数据中心任务调度策略的发展提供参考和借鉴。

云环境；任务调度；Petri网；蚁群优化算法；电力数据；运行能耗

0 引言

信息平台是支撑统一坚强智能电网建设的公共平台和重要手段，从而为智能电网提供了更高效、灵活、安全可靠的信息基础架构[1]。随着电力信息技术的不断发展，数据量的不断增加和云计算的出现，大数据处理成为可能。云计算根据需要获取计算能力和存储空间等服务，广泛应用于智能电网领域。电力调度是整个电网的大脑，需要高效、安全的大数据计算能力支撑[2]。因此，研究云环境下的电力数据中心任务调度策略具有重要的实际意义。

目前，国内外学者对电力云数据中心调度策略进行了大量的研究，取得了部分研究成果。文献[3]提出了一种云任务调度优化策略，该策略综合考虑了用户的最短等待时间、资源负载分配和经济原则，建立了多目标数学模型，通过离散的人工蜂群算法进行求解。结果表明，该方法可以较好地提高虚拟资源上云任务调度系统的性能。文献[4]提出了一种改进的蚁群算法，用于电力云任务调度策略。结果表明，改进算法在保证数据集处理的基础上，可以有效降低执行时间和均衡负载。文献[5]提出了一种改进的遗传算法，用于电力云任务调度策略。该策略对最大任务和平均任务完成时间进行考虑，使系统可靠性和用户满意度得到加强。文献[6]提出了一种改进的蚁群算法，用于电力云任务调度策略，以解决虚拟机的任务调度问题。通过对基本蚁群算法改进实现任务调度时间和负载均衡，从而最小化总体完成时间。结果表明，该算法可以减少任务调度时间，实现云节点负载均衡。文献[7]提出一种基本蚁群算法，用于电力云任务调度策略，结果表明，该算法可以较为灵活地进行任务处理，同时减少任务完成时间。文献[8]提出一种新的聚类调度算法，结果表明，该算法考虑了系统特性，可以实现高效的调度。但是，上述方法没有考虑能耗问题，因此需要进一步提高解的质量和适应性。

因此本文提出了一种基于改进蚁群算法的电力云数据中心调度策略，使用随机Petri网对云数据中心任务调度进行建模，通过改进蚁群优化(Ant Colony Optimization, ACO)算法求解该模型。仿真验证了该方法的优越性。

1 电力云架构

云计算广泛应用于智能电网领域，在电网建设、智能分析、存储等方面作用巨大[9]。云计算技术在电力数据中心的应用可以提高服务器资源利用效率。电力云不是单一的服务，而是多种服务的集合，图1为电力云架构。它主要由五层组成：基础结构层、虚拟化层、系统管理层、应用接口层和服务访问层[10]。

图1 系统架构

2 调度策略

2.1 建模

文中采用随机Petri网对云数据中心的任务调度进行建模[11]。首先对任务进行分解，通过调度将子任务分配给计算资源。

连续时间随机Petri网可以用六元组来表示，如式(2)所示[13]。

式中：为库所集；为变迁集合；为网的流关系；为有向边集合上的权函数；为系统的初始识别；为变迁的平均实施率的集合 ，为变迁的平均服务时间。图2为云任务调度系统的随机Petri网模型。

通过上述方法，可以获得整个系统的性能等价时间。

2.2 蚁群算法

区域栅格化形成一个网络，并给出每个栅格的分类和成本值。蚁群算法搜索流程如图3所示。

图3 蚁群算法搜索流程

蚁群算法的搜索过程主要使用两种类型的规则，确定下一个位置移动规则和算法的核心信息素更新规则[17]。在信息素的引导下，蚁群解向最佳方向发展。

如图3所示，可以假设蚂蚁的位置(黑色)可以移至下一个位置，例如B的灰色部分。蚂蚁的移动方向与移动规则有关，该运动规则由路径的信息素浓度和相邻栅格之间的距离确定。

归一化处理后如式(6)所示[19]。

2.3 改进蚁群算法

在路径选择方面，传统的蚁群算法既耗时又效率低，文中提出了一种改进的蚁群算法，该算法综合考虑了时间、负载和能耗约束等。

(1) 系统初始化

(2) 状态转移概率

(3) 信息素

通过局部更新对节点上信息素进行动态修正，所有蚂蚁完成路径搜索后，更改信息素浓度如式(11)所示[23]。

步骤1) 获取主机状态信息并调控主机电压；

步骤2) 获取可用的虚拟机序列[25]；

步骤4) 为可用计算节点设置初始信息素；

步骤5) 初始化蚁群，随机分布在虚拟机中；

步骤7) 在蚂蚁完成当前搜索后更新本地信息素，否则，返回上一步。

步骤8) 在所有蚂蚁完成对这一轮的搜索后，更新全局信息素。否则，返回到步骤6)。

步骤9) 当达到迭代次数时，任务调度模块输出最优分配计划。否则，返回到步骤5)。

步骤10) 确定任务队列中是否有任务要处理。如果是，返回步骤1)。否则，任务分配结束。

改进蚁群算法流程如图4所示。

3 实验结果与分析

3.1 实验参数

通过实验对文中改进方法的准确性和优越性进行验证。实验中使用的计算机是Intel i5处理器，2.3G Hz，8G内存，并使用CloudSim进行仿真[26]。

图4 改进蚁群优化算法流程图

在实验中，采用60主台搭载300台虚拟机，任务数为1 000～4 000。具体参数设置见表1。

实验中，改进蚁群算法的参数设置如表2所示。

表1 仿真参数

表2 算法参数

3.2 实验结果与分析

为了验证本文所提算法的优越性，从四个方面进行分析：任务执行时间、能耗、任务等待时间和系统负载，并与改进前的蚁群算法和Min-Min算法进行比较[27]。

使用文中改进算法和基本蚁群算法、Min-Min算法，比较任务数为1 000～4 000时的执行时间。实验结果如图5所示。横轴是执行任务的数量，纵轴是任务执行时间。

图5 算法改进前后任务时间对比

从图5中可以看到，随着任务数量的增加，任务完成时间也随之增加。Min-Min算法的任务执行消耗时间最长，文中算法的结果与基本蚁群算法相似。这是因为文中算法考虑了时间和能耗因素，而基本蚁群算法只考虑时间系数，因此从任务执行时间指标上，基本蚁群算法略优于文中算法。结果表明，文中算法增加了能耗因素，但并没有显著增加完成时间。

使用文中算法和基本蚁群算法、Min-Min算法，比较任务数为1 000～4 000时的能耗。实验结果如图6所示。横轴是执行的任务数，纵轴是机器的能耗。

图6 算法改进前后能耗对比

从图6中可以看到，随着任务数量的增加，执行这些任务所消耗的能量也随之增加。Min-Min算法的任务执行消耗的能量最多，文中算法消耗能量最少，与基本蚁群算法相比，文中算法用于任务调度，显著降低了系统能耗。这是因为基本蚁群算法和Min-Min算法仅关注时间指标，而不考虑能耗。

使用文中改进算法和基本蚁群算法、Min-Min算法，比较任务数为1 000～4 000时任务的平均等待时间。实验结果如图7所示，横轴是执行的任务数，纵轴是平均等待时间。

图7 算法改进前后平均等待时间对比

从图7可以看出，文中改进算法的任务等待时间略长于基本蚁群算法和Min-Min算法的任务等待时间。这是因为文中算法具有较高的时间复杂度，花费了大量时间计算分配方案所致。

使用文中改进算法和蚁群算法、Min-Min算法，对1 000～4 000个任务的系统负载进行比较。实验结果如图8所示，横轴是执行的任务数，纵轴是系统负载。

图8 算法改进前后系统负载对比

实验结果表明，改进算法可以使系统负载均衡在0.5到0.6之间，优于Min-Min算法和基本蚁群算法。这是由于基本的蚁群算法、Min-Min算法未添加负载均衡模块，系统的稳定性较差。

综上所述，本文提出的改进蚁群算法在保证性能的前提下，可以有效降低数据中心的能耗。

4 结论

本文对云数据中心任务调度进行建模，综合考虑时间、负荷和能耗等约束对蚁群算法进行改进，并通过改进算法对模型进行求解。结果表明，文中提出的改进蚁群算法在保证性能的前提下，可以有效降低数据中心能耗，在任务数4 000时，相对于改进前能耗降低了4.05%，系统负载降低了6.35%。考虑到现有的实验设备和数据规模，文中仅对调度策略进行了研究，后期可以通过云强大的计算和存储能力，高效地处理和制作三维可视化内容，使显示更加直观。

[1] 张伟晨, 熊永新, 李程昊, 等. 基于改进VDCOL的多馈入直流系统连续换相失败抑制及协调恢复[J]. 电力系统保护与控制, 2020, 48(13): 63-72.

ZHANG Weichen, XIONG Yongxin, LI Chenghao, et al. Continuous commutation failure suppression and coordinated restoration of multi infeed DC systems based on improved VDCOL[J]. Power System Protection and Control, 2020, 48(13): 63-72.

[2] 陈友辉, 王耀南, 肖赞, 等. 高压线路除冰机器人越障识别定位算法研究[J]. 计算机工程与应用, 2013, 49(24): 266-270.

CHEN Youhui, WANG Yaonan, XIAO Zan, et al. Research on obstacle crossing recognition and positioning algorithm of high voltage line deicing robot[J]. Computer Engineering and Application, 2013, 49(24): 266-270.

[3] 倪志伟, 李蓉蓉, 方清华, 等. 基于离散人工蜂群算法的云任务调度优化[J]. 计算机应用, 2016, 36(1): 107-112, 121.

NI Zhiwei, LI Rongrong, FANG Qinghua, et al. Cloud task scheduling optimization based on discrete artificial bee colony algorithm[J]. Computer Applications, 2016, 36(1): 107-112, 121.

[4] 周宇, 陈江兴, 付俊峰, 等. 基于云计算的电力任务调度优化策略研究[J]. 电测与仪表, 2020, 57(13): 28-32, 39.

ZHOU Yu, CHEN Jiangxing, FU Junfeng, et al. Research on power task scheduling optimization strategy based on cloud computing[J]. Electrical Measurement & Instrumentation, 2020, 57(13): 28-32, 39.

[5] 任金霞, 黄艺培, 钟小康. 基于遗传算法的云任务调度改进算法[J]. 江西理工大学学报, 2018, 39(6): 90-94.

REN Jinxia, HUANG Yipei, ZHONG Xiaokang. Improved cloud task scheduling algorithm based on genetic algorithm[J]. Journal of Jiangxi University ofTechnology, 2018, 39(6): 90-94.

[6] 罗斯宁, 王化龙, 李弘宇, 等. 基于改进蚁群算法的云计算用户任务调度算法[J]. 电信科学, 2020, 36(2): 95-100.

LUO Sining, WANG Hualong, LI Hongyu, et al. Cloud computing user task scheduling algorithm based on improved ant colony algorithm[J]. Telecom Science, 2020, 36(2): 95-100.

[7] MATEOS C, PACINI E, GARINO C G. An ACO-inspired algorithm for minimizing weighted flowtime in cloud-based parameter sweep experiments[J]. Advances in Engineering Software, 2013, 56(2): 38-50.

[8] KANEMITSU H, HANADA M, NAKAZATO H. Clustering-based task scheduling in a large number of heterogeneous processors[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(11): 3144-3157.

[9] 汪亚斌, 丁峰, 郭成昊. 面向边缘计算的战术时敏任务调度方法[J]. 指挥信息系统与技术, 2018, 9(6): 36-40.

WANG Yabin, DING Feng, GUO Chenghao. Edge computing oriented tactical time sensitive task scheduling method[J]. Command Information System and Technology, 2018, 9(6): 36-40.

[10] 詹文翰, 王瑾, 朱清新, 等. 移动边缘计算中基于深度强化学习的计算卸载调度方法[J]. 计算机应用研究, 2021, 38(1): 241-245, 263.

ZHAN Wenhan, WANG Jin, ZHU Qingxin, et al. Computational unloading scheduling method based on deep reinforcement learning in mobile edge computing[J]. Computer Application Research, 2021, 38(1): 241-245, 263.

[11] 陈磊, 何慧雯, 王磊, 等. 基于限流器与断路器协调的混合直流输电系统故障隔离方法[J]. 电力系统保护与控制, 2020, 48(19): 119-127.

CHEN Lei, HE Huiwen, WANG Lei, et al. Fault isolation method for hybrid HVDC system based on coordination of current limiter and circuit breaker[J]. Power System Protection and Control, 2020, 48(19): 119-127.

[12] 王波, 张晓磊. 基于粒子群遗传算法的云计算任务调度研究[J]. 计算机工程与应用, 2015, 51(6): 84-88.

WANG Bo, ZHANG Xiaolei. Research on cloud computing task scheduling based on particle swarm genetic algorithm[J]. Computer Engineering and Application, 2015, 51(6): 84-88.

[13] 魏赟, 陈元元. 基于改进蚁群算法的云计算任务调度模型[J]. 计算机工程, 2015, 41(2): 12-16.

WEI Fu, CHEN Yuanyuan. Cloud computing task scheduling model based on improved ant colony algorithm[J]. Computer Engineering, 2015, 41(2): 12-16.

[14] 张龙信, 周立前, 文鸿, 等. 基于异构云计算的成本约束下的工作流能量高效调度算法[J]. 计算机科学, 2020, 47(8): 112-118.

ZHANG Longxin, ZHOU Liqian, WEN Hong, et al. Energy efficient scheduling algorithm of workflow under cost constraint based on heterogeneous cloud computing[J]. Computer Science, 2020, 47(8): 112-118.

[15] PATEL G K, DABHI V K, PRAJAPATI H B. Clustering using a combination of particle swarm optimization and K-means[J]. Journal of Intelligent Systems, 2017, 12(3): 457-469.

[16] GAUTAM J V, PRAJAPATI H B, DABHI V K, et al. Empirical study of job scheduling algorithms in Hadoop MapReduce[J]. Cybernetics and Information Technologies, 2017, 21(1): 146-163.

[17] CAETANO C E F, LIMA A B, PAULINO J O S, et al. A conductor arrangement that overcomes the effective length issue in transmission line grounding[J]. Electric Power Systems Research, 2018, 46(5): 159-162.

[18] HU Jianjiang, FICHTNER M, BARICCO M. Preparation of Li-Mg-N-H hydrogen storage materials for an auxiliary power unit[J]. International Journal of Hydrogen Energy, 2017, 42(27): 17144-17148.

[19] JIA Zhiwei, WANG Lijun, ZHANG Jinchuan, et al. High efficiency, low power-consumption DFB quantum cascade lasers without lateral regrowth[J]. Nanoscale Research Letters, 2017, 12(1): 88-95.

[20] 张婕, 曾国辉, 赵晋斌, 等. 基于改进冒泡排序的模块化多电平换流器电容电压均衡策略[J]. 电力系统保 护与控制, 2020, 48(6): 92-99.

ZHANG Jie, ZENG Guohui, ZHAO Jinbin, et al. Capacitor voltage equalization strategy for modular multilevel converter based on improved bubble sorting[J]. Power System Protection and Control, 2020, 48(6): 92-99.

[21] 陈驰, 彭向阳, 宋爽, 等. 大型无人机电力巡检LiDAR点云安全距离诊断方法[J]. 电网技术, 2017, 41(8): 2723-2730.

CHEN Chi, PENG Xiangyang, SONG Shuang, et al. Safety distance diagnosis of large scale transmission line corridor inspection based on LiDAR point cloud collected with UAV[J]. Power System Technology, 2017, 41(8): 2723-2730.

[22] 孙立明, 杨博. 蓄电池/超导混合储能系统非线性鲁棒分数阶控制[J]. 电力系统保护与控制, 2020, 48(22): 76-83.

SUN Liming, YANG Bo. Nonlinear robust fractional order control for battery / superconducting hybrid energy storage systems[J]. Power System Protection and Control, 2020, 48(22): 76-83.

[23] 戴志辉, 黄敏, 苏怀波. 基于 MMC 的环状直流配网在不同接地方式下的故障特性分析[J]. 电力系统保护与控制, 2019, 47(1): 1-10.

DAI Zhihui, HUANG Min, SU Huaibo. Fault characteristics analysis of circular DC distribution network under different grounding modes based on MMC[J]. Power System Protection and Control, 2019, 47(1): 1-10.

[24] 王利平, 庞晓艳, 朱雨, 等. 基于物联网和移动互联的二次设备运维技术研究与应用[J]. 中国电力, 2019, 52(3): 177-184.

WANG Liping, PANG Xiaoyan, ZHU Yu, et al. Research and application of secondary equipment operation and maintenance technology based on Internet of Things and mobile interconnection[J]. Electric Power, 2019, 52(3): 177-184.

[25] 盛津芳, 滕潇雨, 李伟民, 等. 移动边缘计算中基于改进拍卖模型的计算卸载策略[J]. 计算机应用研究, 2020, 37(6): 1688-1692.

SHENG Jinfang, TENG Xiaoyu, LI Weimin, et al. Computing offload strategy based on improved auction model in mobile edge computing[J]. Computer Application Research, 2020, 37(6): 1688-1692.

[26] 王德文, 刘晓萌. 基于虚拟机动态迁移的电力仿真云计算平台资源调度策略[J]. 计算机科学, 2015, 39(12): 97-105.

WANG Dewen, LIU Xiaomeng. Resource scheduling strategy of power simulation cloud computing platform based on virtual machine dynamic migration[J]. Computer Science, 2015, 39(12): 97-105.

[27] BRAUN T D, SIEGEL H J, BECK N, et al. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[J]. Journal of Parallel & Distributed Computing, 2001, 61(6): 810-837.

A task scheduling strategy for a power cloud data center based on an improved ant colony algorithm

SUN Zhandong1, JIAO Jiao1, LI Wei1, LI Zhipeng1, LI Peng’en2

(1. Beijing Electric Power Economic Research Institute Co., Ltd., Beijing 100055, China; 2. Beijing Forever Technology Co., Ltd., Beijing 100011, China)

There are problems of high energy consumption and low efficiency of power data center task scheduling in the existing cloud environment. Thus, based on power cloud architecture, this paper proposes a cloud data center task scheduling based on the stochastic Petri net model, and considers the time, load, and energy consumption constraints to improve the ant colony algorithm to solve the problem presented by the model. The advantages of this method are verified by comparing and analyzing the running time, energy consumption, average waiting time and system load. The results show that the improved ant colony algorithm can effectively reduce the energy consumption of the data center and guarantee performance. It provides a reference for the development of a task scheduling strategy in a power data center.

This work is supported by the Science and Technology Project of State Grid Corporation of China (No. 520234190006).

cloud environment; task scheduling; Petri network; ant colony optimization algorithm; power data; operation energy consumption

10.19783/j.cnki.pspc.210466

国家电网公司科技项目资助(520234190006)

2021-04-22；

2021-06-05

孙湛冬(1989—)，男，博士，高级工程师，从事电网规划设计工作；E-mail: sun250072@163.com

焦 娇(1988—)，女，博士，高级工程师，从事电网规划设计工作；

李 伟(1977—)，男，硕士，教授级高工，从事电网规划设计工作。

(编辑 张爱琴)