基于等待代價的云平臺電力通信業(yè)務調度算法

黃國倫　藍天寶　王光波　閆江毓　樊冰　郭昊博

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

關鍵詞： 云平臺; 等待代價; 業(yè)務調度; 電力通信

中圖分類號： 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 引言

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

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

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

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

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

2 云平臺電力通信業(yè)務調度模型

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

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

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

3 基于業(yè)務等待代價的調度優(yōu)化算法

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

3.1 動態(tài)隊列長度

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

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

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

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

3.2 隊列擁塞度

隊列擁塞度與業(yè)務隊列長度的動態(tài)變化有關，如果業(yè)務的流入速度不及流出速度，那么隊列中各業(yè)務的等待時間會不可避免的延長，造成業(yè)務響應速度下降。基于動態(tài)隊列長度，定義當前調度周期T內隊列i的擁塞度jTi為式（4）。

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

3.3 業(yè)務等待代價

如果隊列擁塞程度高，業(yè)務等待時間就會延長。為了保證優(yōu)先級高的業(yè)務處理時延，在相同擁塞水平下，應優(yōu)先處理高等級業(yè)務。定義調度周期T內i隊列中業(yè)務的等待代價wTi為式（5）。

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

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

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

定義云平臺所有電力業(yè)務隊列等待總代價為式（6）。

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

3.4 多約束優(yōu)化

調度算法的目標是最小化業(yè)務等待總代價，將業(yè)務調度轉化為（7）式的多約束優(yōu)化問題為式（7）。

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

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

4 仿真分析

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

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

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

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

5 總結

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

參考文獻

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

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

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

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

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

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

（收稿日期： 2020.01.08）

作者簡介：

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

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

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

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

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

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