基于等待代價(jià)的云平臺(tái)電力通信業(yè)務(wù)調(diào)度算法

黃國(guó)倫　藍(lán)天寶　王光波　閆江毓　樊冰　郭昊博

摘 要： 基于云平臺(tái)的電力通信業(yè)務(wù)可以實(shí)現(xiàn)電力通信集中化、精細(xì)化管控，提高電力通信的運(yùn)維效率。但是業(yè)務(wù)的重要程度各不相同，不同業(yè)務(wù)之間的受理順序會(huì)影響業(yè)務(wù)的執(zhí)行效率。針對(duì)此問題設(shè)計(jì)了一種基于等待代價(jià)的調(diào)度算法。首先對(duì)業(yè)務(wù)劃分優(yōu)先級(jí)，并按優(yōu)先級(jí)設(shè)定隊(duì)列數(shù)量，然后綜合考慮隊(duì)列歷史長(zhǎng)度和出入隊(duì)列業(yè)務(wù)，動(dòng)態(tài)化設(shè)定隊(duì)列長(zhǎng)度和量化隊(duì)列擁塞度，得到總等待代價(jià)函數(shù)。通過動(dòng)態(tài)規(guī)劃求得代價(jià)函數(shù)的最優(yōu)解。仿真結(jié)果表明，該算法在保證業(yè)務(wù)公平性的同時(shí)盡量使高優(yōu)先級(jí)業(yè)務(wù)優(yōu)先處理。高優(yōu)先級(jí)隊(duì)列的阻塞率和平均延時(shí)有明顯降低，在電力通信領(lǐng)域具有很好的實(shí)際應(yīng)用價(jià)值。

關(guān)鍵詞： 云平臺(tái); 等待代價(jià); 業(yè)務(wù)調(diào)度; 電力通信

中圖分類號(hào)： TP 311文獻(xiàn)標(biāo)志碼： 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 引言

電力網(wǎng)絡(luò)面向千家萬(wàn)戶，服務(wù)要求高、社會(huì)影響力大，是國(guó)家高速發(fā)展的堅(jiān)實(shí)后盾。電力通信網(wǎng)作為電力業(yè)務(wù)的承載網(wǎng)絡(luò)，其可靠性與電網(wǎng)穩(wěn)定運(yùn)行息息相關(guān)，要確保電力業(yè)務(wù)的連續(xù)性以避免引起大型停電事故[1]。

目前電力通信網(wǎng)的網(wǎng)管系統(tǒng)及其包含的各子系統(tǒng)大多分而治之，這種模式下全面運(yùn)維的成本較高，因此基于云平臺(tái)的一體化綜合系統(tǒng)成為當(dāng)前較為可靠的集中化實(shí)施方案[2]。今年來，大量的云調(diào)度算法相繼提出，如文獻(xiàn)[3]面向風(fēng)電場(chǎng)設(shè)計(jì)了一種雙隊(duì)列的作業(yè)調(diào)度器，綜合考慮作業(yè)的截止時(shí)間和優(yōu)先級(jí)來進(jìn)行作業(yè)調(diào)度決策，文獻(xiàn)[4]面向分布式云平臺(tái)設(shè)計(jì)出快速收斂的高效多目標(biāo)博弈調(diào)度算法，文獻(xiàn)[5]面向高能物理領(lǐng)域基于雙閾值的彈性資源管理算法實(shí)現(xiàn)業(yè)務(wù)調(diào)度。這些算法的原理不同，應(yīng)用的領(lǐng)域也會(huì)有所不同。本文面向云平臺(tái)下的電力通信業(yè)務(wù)調(diào)度，提出一種基于等待代價(jià)的業(yè)務(wù)調(diào)度算法，通過以最小化業(yè)務(wù)等待代價(jià)為目標(biāo)優(yōu)化調(diào)度策略，在保證各等級(jí)業(yè)務(wù)穩(wěn)定受理的前提下盡量降低高優(yōu)先級(jí)業(yè)務(wù)的排隊(duì)時(shí)延。

1 電力通信業(yè)務(wù)特征

電力通信業(yè)務(wù)的主要職能是監(jiān)視、控制和管理電力通信網(wǎng)，保證電力通信網(wǎng)正常穩(wěn)定運(yùn)行，電力業(yè)務(wù)可靠傳輸?shù)囊幌盗袠I(yè)務(wù)。當(dāng)前電力通信業(yè)務(wù)主要包括電力調(diào)度電話管控、通信設(shè)備故障診斷及報(bào)警、網(wǎng)絡(luò)設(shè)備管理、VLAN配置、網(wǎng)絡(luò)性能與狀態(tài)圖表分析、端口狀態(tài)監(jiān)視與分析，網(wǎng)絡(luò)拓?fù)涔芾淼戎T多功能[6]。電力通信業(yè)務(wù)的具體特性如表1所示。

與調(diào)度數(shù)據(jù)網(wǎng)相關(guān)的通信業(yè)務(wù)以及會(huì)造成電力一次業(yè)務(wù)中斷的故障都屬于緊急類業(yè)務(wù)，比如從故障發(fā)生到發(fā)出報(bào)警提醒，調(diào)度員下達(dá)指令到通信設(shè)備完成路由倒換。這類業(yè)務(wù)對(duì)時(shí)延較為敏感，如果處理時(shí)間延長(zhǎng)，可能引發(fā)電力一次業(yè)務(wù)級(jí)聯(lián)反應(yīng)，從而造成大的事故。

2 云平臺(tái)電力通信業(yè)務(wù)調(diào)度模型

基于云平臺(tái)的電力通信管控實(shí)現(xiàn)了電力通信管控的集中化處理，業(yè)務(wù)響應(yīng)更為迅速和精確。云平臺(tái)處理資源豐富，控制靈活性強(qiáng)，可以實(shí)現(xiàn)精細(xì)化、細(xì)粒度的業(yè)務(wù)調(diào)度，保證業(yè)務(wù)的持續(xù)性。基于云平臺(tái)的業(yè)務(wù)調(diào)度模型如圖1所示。

電力通信業(yè)務(wù)周期性地從通信設(shè)備和網(wǎng)絡(luò)采集監(jiān)控?cái)?shù)據(jù)，提交到電力通信云管控系統(tǒng)。若發(fā)生承載一次業(yè)務(wù)中斷、設(shè)備故障等突發(fā)隨機(jī)性事件也通過云管控系統(tǒng)進(jìn)行處理。云平臺(tái)業(yè)務(wù)調(diào)度器按照業(yè)務(wù)的優(yōu)先等級(jí)進(jìn)行業(yè)務(wù)調(diào)度。根據(jù)云管控系統(tǒng)管理的電力通信網(wǎng)絡(luò)規(guī)模以及管控系統(tǒng)所屬級(jí)別，模型中業(yè)務(wù)數(shù)量和優(yōu)先級(jí)級(jí)數(shù)也有差異。調(diào)度器為每個(gè)優(yōu)先級(jí)設(shè)置一個(gè)隊(duì)列，優(yōu)先級(jí)相同的業(yè)務(wù)進(jìn)入同一個(gè)隊(duì)列，調(diào)度器在適當(dāng)?shù)臅r(shí)刻將業(yè)務(wù)發(fā)送到管控系統(tǒng)。

由于云平臺(tái)計(jì)算資源受限，導(dǎo)致隊(duì)列長(zhǎng)度有限，當(dāng)業(yè)務(wù)急劇增多時(shí)，隊(duì)列中等待調(diào)度的業(yè)務(wù)數(shù)量增加，隊(duì)列被阻塞，造成業(yè)務(wù)延時(shí)增大。本文所提調(diào)度算法依據(jù)隊(duì)列歷史動(dòng)態(tài)調(diào)整隊(duì)列長(zhǎng)度，計(jì)算出隊(duì)列擁塞度并轉(zhuǎn)化為全隊(duì)列業(yè)務(wù)等待代價(jià)，通過優(yōu)化算法使總代價(jià)最小化，能有效降低高優(yōu)先級(jí)業(yè)務(wù)的阻塞率和業(yè)務(wù)延時(shí)。

3 基于業(yè)務(wù)等待代價(jià)的調(diào)度優(yōu)化算法

為了保證高優(yōu)先級(jí)業(yè)務(wù)得到盡快處理，并且兼顧其他業(yè)務(wù)的公平效率，本文提出了一種基于業(yè)務(wù)等待代價(jià)的調(diào)度優(yōu)化算法。

3.1 動(dòng)態(tài)隊(duì)列長(zhǎng)度

云平臺(tái)業(yè)務(wù)調(diào)度器為每個(gè)優(yōu)先級(jí)設(shè)置一個(gè)隊(duì)列，網(wǎng)管系統(tǒng)發(fā)起的電力通信業(yè)務(wù)進(jìn)入隊(duì)列等待調(diào)度器執(zhí)行。每個(gè)隊(duì)列單位周期內(nèi)到達(dá)的業(yè)務(wù)數(shù)是一個(gè)滿足泊松分布的隨機(jī)變量，因此隊(duì)列長(zhǎng)度動(dòng)態(tài)變化。采用固定隊(duì)列長(zhǎng)度易導(dǎo)致資源利用率不足，隊(duì)列擁塞程度不均衡，極端情況下會(huì)造成高優(yōu)先性級(jí)隊(duì)列嚴(yán)重阻塞，電力通信業(yè)務(wù)得不到正常響應(yīng)，業(yè)務(wù)故障級(jí)聯(lián)傳遞到電力核心業(yè)務(wù)，造成惡劣的連鎖反應(yīng)。

本文基于歷史隊(duì)列長(zhǎng)度定義了動(dòng)態(tài)隊(duì)列長(zhǎng)度。云調(diào)度器周期性動(dòng)態(tài)調(diào)整隊(duì)列長(zhǎng)度。在每個(gè)調(diào)度周期T，設(shè)第i隊(duì)列的隊(duì)列長(zhǎng)度為qTi、調(diào)度器記錄進(jìn)隊(duì)列業(yè)務(wù)數(shù)in_qi和出隊(duì)列業(yè)務(wù)數(shù)out_qi。則調(diào)度周期T+1內(nèi)其隊(duì)列長(zhǎng)度qT+1i為式（1）—式（3）。

其中N為判斷窗口長(zhǎng)度，包含當(dāng)前調(diào)度周期T之前的N個(gè)周期。in_qT+1i和out_qT+1i分別代表調(diào)度器預(yù)測(cè)i隊(duì)列在T+1周期新增（進(jìn)隊(duì)列）及處理（出隊(duì)列）的電力通信業(yè)務(wù)數(shù)量。

N值與周期T內(nèi)電力通信業(yè)務(wù)規(guī)模以及云平臺(tái)處理能力有關(guān)，根據(jù)經(jīng)驗(yàn)靈活設(shè)定。根據(jù)廣西電網(wǎng)的實(shí)際應(yīng)用來說，可以取15～20。

3.2 隊(duì)列擁塞度

隊(duì)列擁塞度與業(yè)務(wù)隊(duì)列長(zhǎng)度的動(dòng)態(tài)變化有關(guān)，如果業(yè)務(wù)的流入速度不及流出速度，那么隊(duì)列中各業(yè)務(wù)的等待時(shí)間會(huì)不可避免的延長(zhǎng)，造成業(yè)務(wù)響應(yīng)速度下降?；趧?dòng)態(tài)隊(duì)列長(zhǎng)度，定義當(dāng)前調(diào)度周期T內(nèi)隊(duì)列i的擁塞度jTi為式（4）。

式中qmax及qmin分別表示全部隊(duì)列中隊(duì)列長(zhǎng)度的最大值和最小值。引入ξi因子，用來放大或縮小該等級(jí)隊(duì)列的影響。ji越大意味著隊(duì)列的擁塞度越大。

3.3 業(yè)務(wù)等待代價(jià)

如果隊(duì)列擁塞程度高，業(yè)務(wù)等待時(shí)間就會(huì)延長(zhǎng)。為了保證優(yōu)先級(jí)高的業(yè)務(wù)處理時(shí)延，在相同擁塞水平下，應(yīng)優(yōu)先處理高等級(jí)業(yè)務(wù)。定義調(diào)度周期T內(nèi)i隊(duì)列中業(yè)務(wù)的等待代價(jià)wTi為式（5）。

其中，ηi為i隊(duì)列的相對(duì)重要程度，即業(yè)務(wù)優(yōu)先級(jí)的量化值，該參量根據(jù)實(shí)際情況憑經(jīng)驗(yàn)確定，應(yīng)滿足，

其中M為隊(duì)列總數(shù)。式（5）分母體現(xiàn)了當(dāng)前隊(duì)列i在判斷窗口N內(nèi)的擁塞情況。

業(yè)務(wù)等待代價(jià)wi融合隊(duì)列擁塞度及業(yè)務(wù)重要程度，在保證優(yōu)先處理高等級(jí)業(yè)務(wù)的前提下盡量保證各等級(jí)業(yè)務(wù)的處理公平性。調(diào)度算法還需要從全局考慮所有隊(duì)列的擁塞情況和業(yè)務(wù)代價(jià)。

定義云平臺(tái)所有電力業(yè)務(wù)隊(duì)列等待總代價(jià)為式（6）。

其中，M為隊(duì)列總數(shù)。S={s1，s2，…，sM}為業(yè)務(wù)處理方案，si表示系統(tǒng)決定當(dāng)前調(diào)度周期T處理的i等級(jí)業(yè)務(wù)的數(shù)量，該方法通過動(dòng)態(tài)加權(quán)的方式計(jì)算剩余未處理業(yè)務(wù)等待一個(gè)調(diào)度周期的代價(jià)，量化不同業(yè)務(wù)處理策略的總體調(diào)度效果。

3.4 多約束優(yōu)化

調(diào)度算法的目標(biāo)是最小化業(yè)務(wù)等待總代價(jià)，將業(yè)務(wù)調(diào)度轉(zhuǎn)化為（7）式的多約束優(yōu)化問題為式（7）。

其中，Smax為單位周期內(nèi)系統(tǒng)所能處理業(yè)務(wù)數(shù)量闕值，其表征云平臺(tái)的業(yè)務(wù)處理能力有限，單位周期內(nèi)不同等級(jí)業(yè)務(wù)的處理量總和應(yīng)小于闕值，防止系統(tǒng)過載。其余約束防止云平臺(tái)為某一隊(duì)列過度分配計(jì)算資源的情況發(fā)生，使其合理的分配計(jì)算性能，避免資源浪費(fèi)。該規(guī)劃將隊(duì)列等待代價(jià)作為目標(biāo)函數(shù)，綜合考慮各等級(jí)業(yè)務(wù)的重要程度及其隊(duì)列長(zhǎng)度，在優(yōu)先處理高等級(jí)業(yè)務(wù)的同時(shí)兼顧不同等級(jí)業(yè)務(wù)的處理公平性，最優(yōu)化系統(tǒng)的業(yè)務(wù)處理效能。

由于問題規(guī)模不算太大，啟發(fā)式優(yōu)化算法性能優(yōu)越但計(jì)算量大耗時(shí)較長(zhǎng)，因此本文采用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。

4 仿真分析

為了驗(yàn)證算法的性能，本文在MATLAB上進(jìn)行仿真。根據(jù)廣西電網(wǎng)運(yùn)維經(jīng)驗(yàn)，將電力通信業(yè)務(wù)分為三級(jí)：緊急業(yè)務(wù)，重要業(yè)務(wù)和一般業(yè)務(wù)，每級(jí)對(duì)應(yīng)一個(gè)隊(duì)列，各級(jí)業(yè)務(wù)數(shù)的之比設(shè)為1∶2∶7。各優(yōu)先級(jí)業(yè)務(wù)的最大排隊(duì)時(shí)延需求分別設(shè)為T、10T和70T。業(yè)務(wù)到達(dá)速率服從參數(shù)為λi（i=1，2，3）的泊松分布，，仿真時(shí)間為800T，其中在0T、200T、400T時(shí)緊急業(yè)務(wù)突發(fā)，突發(fā)量為2個(gè)/T，持續(xù)時(shí)間均為20T。為保證無突發(fā)情況下系統(tǒng)能滿足用戶需求，系統(tǒng)總處理能力為10個(gè)/T，取前800個(gè)緊急業(yè)務(wù)做時(shí)延比對(duì)，具體仿真結(jié)果如圖2所示。

圖2對(duì)本文算法和FIFO算法的處理性能進(jìn)行了比對(duì)。FIFO調(diào)度算法下，業(yè)務(wù)先到先服務(wù)。圖2（a）和圖2（b）可以看出，根據(jù)FIFO算法進(jìn)行調(diào)度時(shí)，一旦出現(xiàn)緊急情況，緊急業(yè)務(wù)量突增，其時(shí)延波動(dòng)幅度很大且逐漸上升，最大時(shí)延接近16T，平均時(shí)延為7.5T;且下降緩慢，大部分緊急業(yè)務(wù)不能達(dá)到1T的時(shí)延要求;而本文算法利用等待代價(jià)函數(shù)及時(shí)發(fā)現(xiàn)了擁塞程度較大的隊(duì)列，避免緊急業(yè)務(wù)隊(duì)列過長(zhǎng)，少部分業(yè)務(wù)時(shí)延過大，最高為8T，平均時(shí)延為1.7T。

圖2（c）和圖2（e）表明，對(duì)于重要業(yè)務(wù)和一般業(yè)務(wù)，F(xiàn)IFO算法下不受緊急業(yè)務(wù)量劇增的影響，時(shí)延變化比較平緩。在本文算法下，由于對(duì)緊急業(yè)務(wù)隊(duì)列進(jìn)行了優(yōu)先處理，占用了計(jì)算資源，導(dǎo)致重要業(yè)務(wù)的平均時(shí)延有所增加，如圖2（d）所示。對(duì)于一般業(yè)務(wù)也會(huì)受到影響，緊急業(yè)務(wù)劇增的情況下，其阻塞率較高，等待時(shí)延增加明顯，如圖2（f）所示。

通過仿真表明，本文算法在滿足時(shí)延要求的前提下適度延長(zhǎng)低等級(jí)業(yè)務(wù)的時(shí)延以降低緊急業(yè)務(wù)時(shí)延，在系統(tǒng)性能有限的條件下更好的實(shí)現(xiàn)了任務(wù)的調(diào)度，保證了電力通信系統(tǒng)的可靠性。

5 總結(jié)

本文針對(duì)電力通信業(yè)務(wù)的特點(diǎn)，利用業(yè)務(wù)分類模型將不同種類的核心業(yè)務(wù)進(jìn)行分級(jí)，并將業(yè)務(wù)調(diào)度過程轉(zhuǎn)化約束優(yōu)化問題求出最優(yōu)解。仿真結(jié)果表明，在緊急業(yè)務(wù)申請(qǐng)量發(fā)生突變時(shí)，該算法調(diào)度性能優(yōu)異且穩(wěn)定性較好，對(duì)電力云網(wǎng)管建設(shè)具有一定的指導(dǎo)作用。

參考文獻(xiàn)

[1] 樊冰， 唐良瑞. 電力通信網(wǎng)脆弱性分析[J]. 中國(guó)電機(jī)工程學(xué)報(bào)， 2014， 34（7）：1191-1197.

[2] 曾珊， 陳剛， 齊法制. 高性能云數(shù)據(jù)中心彈性網(wǎng)絡(luò)研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2018，54（7）：89-95.

[3] 羅賢縉，岳黎明，甄成剛. 風(fēng)電場(chǎng)數(shù)據(jù)中心Hadoop云平臺(tái)作業(yè)調(diào)度算法研究[J].計(jì)算機(jī)工程與應(yīng)用， 2015， 51（15）： 266-270.

[4] 沈堯， 秦小麟， 鮑芝峰 . 一種云環(huán)境中數(shù)據(jù)流的高效多目標(biāo)調(diào)度方法[J]. 軟件學(xué)報(bào)， 2017，28（3）： 579-597.

[5] 程振京，李海波，黃秋蘭，等. 高能物理云平臺(tái)中的彈性計(jì)算資源管理機(jī)制[J].計(jì)算機(jī)工程與應(yīng)用， 2017， 53（8）： 8-14.

[6] 黃漢華. 基于云平臺(tái)的廣西電力省地一體化通信運(yùn)行管控系統(tǒng)設(shè)計(jì)[D].北京：華北電力大學(xué)，2017.

（收稿日期： 2020.01.08）

作者簡(jiǎn)介：

黃國(guó)倫（1986-），男，碩士，工程師，研究方向：光傳輸及數(shù)據(jù)通信。

藍(lán)天寶（1986-），男，碩士，工程師，研究方向：電力通信。

王光波（1991-），男，碩士，助理工程師，研究方向：光傳輸。

閆江毓（1979-），男，碩士，講師，研究方向：電力通信。

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

郭昊博（1994-），男，博士，助教，研究方向：泛在物聯(lián)網(wǎng)。