基于等待代价的云平台电力通信业务调度算法

黄国伦　蓝天宝　王光波　闫江毓　樊冰　郭昊博

摘 要： 基于云平台的电力通信业务可以实现电力通信集中化、精细化管控，提高电力通信的运维效率。但是业务的重要程度各不相同，不同业务之间的受理顺序会影响业务的执行效率。针对此问题设计了一种基于等待代价的调度算法。首先对业务划分优先级，并按优先级设定队列数量，然后综合考虑队列历史长度和出入队列业务，动态化设定队列长度和量化队列拥塞度，得到总等待代价函数。通过动态规划求得代价函数的最优解。仿真结果表明，该算法在保证业务公平性的同时尽量使高优先级业务优先处理。高优先级队列的阻塞率和平均延时有明显降低，在电力通信领域具有很好的实际应用价值。

关键词： 云平台; 等待代价; 业务调度; 电力通信

中图分类号： TP 311文献标志码： A

Power Communication Service for Cloud Platform Scheduling

AlgorithmBased on Waiting Cost

HUANG Guolun1， LAN Tianbao1， WANG Guangbo1， YAN Jiangyu2， FAN Bing2， GUO Haobo2

（1.Dispatching Control Center， Guangxi Power Grid Power，   Nanning， Guangxi 530023， China;

2.School of Electrical and Electronic Engineering， North China Electric Power University， Beijing 102206， China）

Abstract： Cloud-based power communications business can achieve centralized， fine-grained control of power communications， and improve the efficiency of power communication operation and maintenance. However， the importance of the business varies， and the order of acceptance between different businesses affects the efficiency of the business execution. A scheduling algorithm based on waiting cost is designed for this problem. First， we prioritize the business and prioritize the number of queues. Then we consider the queue history length and access to the business， dynamically set the queue length and quantify the queue congestion， and get the total waiting cost function. The optimal solution of the cost function is obtained through dynamic planning. The simulation results show that the algorithm makes high priority business priority as far as possible while ensuring business fairness. The blocking rate and average delay of the highest priority queues are significantly reduced. This algorithm is of good practical application value in the field of power communication.

Key words： cloud platform; waiting cost; service scheduling; power communication

0 引言

電力网络面向千家万户，服务要求高、社会影响力大，是国家高速发展的坚实后盾。电力通信网作为电力业务的承载网络，其可靠性与电网稳定运行息息相关，要确保电力业务的连续性以避免引起大型停电事故[1]。

目前电力通信网的网管系统及其包含的各子系统大多分而治之，这种模式下全面运维的成本较高，因此基于云平台的一体化综合系统成为当前较为可靠的集中化实施方案[2]。今年来，大量的云调度算法相继提出，如文献[3]面向风电场设计了一种双队列的作业调度器，综合考虑作业的截止时间和优先级来进行作业调度决策，文献[4]面向分布式云平台设计出快速收敛的高效多目标博弈调度算法，文献[5]面向高能物理领域基于双阈值的弹性资源管理算法实现业务调度。这些算法的原理不同，应用的领域也会有所不同。本文面向云平台下的电力通信业务调度，提出一种基于等待代价的业务调度算法，通过以最小化业务等待代价为目标优化调度策略，在保证各等级业务稳定受理的前提下尽量降低高优先级业务的排队时延。

1 电力通信业务特征

电力通信业务的主要职能是监视、控制和管理电力通信网，保证电力通信网正常稳定运行，电力业务可靠传输的一系列业务。当前电力通信业务主要包括电力调度电话管控、通信设备故障诊断及报警、网络设备管理、VLAN配置、网络性能与状态图表分析、端口状态监视与分析，网络拓扑管理等诸多功能[6]。电力通信业务的具体特性如表1所示。

与调度数据网相关的通信业务以及会造成电力一次业务中断的故障都属于紧急类业务，比如从故障发生到发出报警提醒，调度员下达指令到通信设备完成路由倒换。这类业务对时延较为敏感，如果处理时间延长，可能引发电力一次业务级联反应，从而造成大的事故。

2 云平台电力通信业务调度模型

基于云平台的电力通信管控实现了电力通信管控的集中化处理，业务响应更为迅速和精确。云平台处理资源丰富，控制灵活性强，可以实现精细化、细粒度的业务调度，保证业务的持续性。基于云平台的业务调度模型如图1所示。

电力通信业务周期性地从通信设备和网络采集监控数据，提交到电力通信云管控系统。若发生承载一次业务中断、设备故障等突发随机性事件也通过云管控系统进行处理。云平台业务调度器按照业务的优先等级进行业务调度。根据云管控系统管理的电力通信网络规模以及管控系统所属级别，模型中业务数量和优先级级数也有差异。调度器为每个优先级设置一个队列，优先级相同的业务进入同一个队列，调度器在适当的时刻将业务发送到管控系统。

由于云平台计算资源受限，导致队列长度有限，当业务急剧增多时，队列中等待调度的业务数量增加，队列被阻塞，造成业务延时增大。本文所提调度算法依据队列历史动态调整队列长度，计算出队列拥塞度并转化为全队列业务等待代价，通过优化算法使总代价最小化，能有效降低高优先级业务的阻塞率和业务延时。

3 基于业务等待代价的调度优化算法

为了保证高优先级业务得到尽快处理，并且兼顾其他业务的公平效率，本文提出了一种基于业务等待代价的调度优化算法。

3.1 动态队列长度

云平台业务调度器为每个优先级设置一个队列，网管系统发起的电力通信业务进入队列等待调度器执行。每个队列单位周期内到达的业务数是一个满足泊松分布的随机变量，因此队列长度动态变化。采用固定队列长度易导致资源利用率不足，队列拥塞程度不均衡，极端情况下会造成高优先性级队列严重阻塞，电力通信业务得不到正常响应，业务故障级联传递到电力核心业务，造成恶劣的连锁反应。

本文基于历史队列长度定义了动态队列长度。云调度器周期性动态调整队列长度。在每个调度周期T，设第i队列的队列长度为qTi、调度器记录进队列业务数in_qi和出队列业务数out_qi。则调度周期T+1内其队列长度qT+1i为式（1）—式（3）。

其中N为判断窗口长度，包含当前调度周期T之前的N个周期。in_qT+1i和out_qT+1i分别代表调度器预测i队列在T+1周期新增（进队列）及处理（出队列）的电力通信业务数量。

N值与周期T内电力通信业务规模以及云平台处理能力有关，根据经验灵活设定。根据广西电网的实际应用来说，可以取15～20。

3.2 队列拥塞度

队列拥塞度与业务队列长度的动态变化有关，如果业务的流入速度不及流出速度，那么队列中各业务的等待时间会不可避免的延长，造成业务响应速度下降。基于动态队列长度，定义当前调度周期T内队列i的拥塞度jTi为式（4）。

式中qmax及qmin分别表示全部队列中队列长度的最大值和最小值。引入ξi因子，用来放大或缩小该等级队列的影响。ji越大意味着队列的拥塞度越大。

3.3 业务等待代价

如果队列拥塞程度高，业务等待时间就会延长。为了保证优先级高的业务处理时延，在相同拥塞水平下，应优先处理高等级业务。定义调度周期T内i队列中业务的等待代价wTi为式（5）。

其中，ηi為i队列的相对重要程度，即业务优先级的量化值，该参量根据实际情况凭经验确定，应满足，

其中M为队列总数。式（5）分母体现了当前队列i在判断窗口N内的拥塞情况。

业务等待代价wi融合队列拥塞度及业务重要程度，在保证优先处理高等级业务的前提下尽量保证各等级业务的处理公平性。调度算法还需要从全局考虑所有队列的拥塞情况和业务代价。

定义云平台所有电力业务队列等待总代价为式（6）。

其中，M为队列总数。S={s1，s2，…，sM}为业务处理方案，si表示系统决定当前调度周期T处理的i等级业务的数量，该方法通过动态加权的方式计算剩余未处理业务等待一个调度周期的代价，量化不同业务处理策略的总体调度效果。

3.4 多约束优化

调度算法的目标是最小化业务等待总代价，将业务调度转化为（7）式的多约束优化问题为式（7）。

其中，Smax为单位周期内系统所能处理业务数量阙值，其表征云平台的业务处理能力有限，单位周期内不同等级业务的处理量总和应小于阙值，防止系统过载。其余约束防止云平台为某一队列过度分配计算资源的情况发生，使其合理的分配计算性能，避免资源浪费。该规划将队列等待代价作为目标函数，综合考虑各等级业务的重要程度及其队列长度，在优先处理高等级业务的同时兼顾不同等级业务的处理公平性，最优化系统的业务处理效能。

由于问题规模不算太大，启发式优化算法性能优越但计算量大耗时较长，因此本文采用动态规划算法进行求解。

4 仿真分析

为了验证算法的性能，本文在MATLAB上进行仿真。根据广西电网运维经验，将电力通信业务分为三级：紧急业务，重要业务和一般业务，每级对应一个队列，各级业务数的之比设为1∶2∶7。各优先级业务的最大排队时延需求分别设为T、10T和70T。业务到达速率服从参数为λi（i=1，2，3）的泊松分布，，仿真时间为800T，其中在0T、200T、400T时紧急业务突发，突发量为2个/T，持续时间均为20T。为保证无突发情况下系统能满足用户需求，系统总处理能力为10个/T，取前800个紧急业务做时延比对，具体仿真结果如图2所示。

图2对本文算法和FIFO算法的处理性能进行了比对。FIFO调度算法下，业务先到先服务。图2（a）和图2（b）可以看出，根据FIFO算法进行调度时，一旦出现紧急情况，紧急业务量突增，其时延波动幅度很大且逐渐上升，最大时延接近16T，平均时延为7.5T;且下降缓慢，大部分紧急业务不能达到1T的时延要求;而本文算法利用等待代价函数及时发现了拥塞程度较大的队列，避免紧急业务队列过长，少部分业务时延过大，最高为8T，平均时延为1.7T。

图2（c）和图2（e）表明，对于重要业务和一般业务，FIFO算法下不受紧急业务量剧增的影响，时延变化比较平缓。在本文算法下，由于对紧急业务队列进行了优先处理，占用了计算资源，导致重要业务的平均时延有所增加，如图2（d）所示。对于一般业务也会受到影响，紧急业务剧增的情况下，其阻塞率较高，等待时延增加明显，如图2（f）所示。

通过仿真表明，本文算法在满足时延要求的前提下适度延长低等级业务的时延以降低紧急业务时延，在系统性能有限的条件下更好的实现了任务的调度，保证了电力通信系统的可靠性。

5 总结

本文针对电力通信业务的特点，利用业务分类模型将不同种类的核心业务进行分级，并将业务调度过程转化约束优化问题求出最优解。仿真结果表明，在紧急业务申请量发生突变时，该算法调度性能优异且稳定性较好，对电力云网管建设具有一定的指导作用。

参考文献

[1] 樊冰， 唐良瑞. 电力通信网脆弱性分析[J]. 中国电机工程学报， 2014， 34（7）：1191-1197.

[2] 曾珊， 陈刚， 齐法制. 高性能云数据中心弹性网络研究[J]. 计算机工程与应用， 2018，54（7）：89-95.

[3] 罗贤缙，岳黎明，甄成刚. 风电场数据中心Hadoop云平台作业调度算法研究[J].计算机工程与应用， 2015， 51（15）： 266-270.

[4] 沈堯， 秦小麟， 鲍芝峰 . 一种云环境中数据流的高效多目标调度方法[J]. 软件学报， 2017，28（3）： 579-597.

[5] 程振京，李海波，黄秋兰，等. 高能物理云平台中的弹性计算资源管理机制[J].计算机工程与应用， 2017， 53（8）： 8-14.

[6] 黄汉华. 基于云平台的广西电力省地一体化通信运行管控系统设计[D].北京：华北电力大学，2017.

（收稿日期： 2020.01.08）

作者简介：

黄国伦（1986-），男，硕士，工程师，研究方向：光传输及数据通信。

蓝天宝（1986-），男，硕士，工程师，研究方向：电力通信。

王光波（1991-），男，硕士，助理工程师，研究方向：光传输。

闫江毓（1979-），男，硕士，讲师，研究方向：电力通信。

樊冰（1978-），男，博士，副教授，研究方向：电力通信。

郭昊博（1994-），男，博士，助教，研究方向：泛在物联网。