面向新型電力系統(tǒng)的最小服務(wù)延遲的負(fù)載分配算法研究

張秋雨，蔣云峰，張常穩(wěn)，張一鳴

(1. 國網(wǎng)河北省電力有限公司邢臺供電分公司，河北 邢臺 054000; 2. 華北電力大學(xué)科技學(xué)院，河北 保定 071051)

0 引 言

近兩年來國家積極推動新型電力系統(tǒng)發(fā)展，建設(shè)以新能源為主體的新型電力系統(tǒng)，有效支撐為微網(wǎng)、分布式電源和新能源的大范圍接入，打造多能互補、雙向互動的能源互聯(lián)網(wǎng)[1-2]。新型電力系統(tǒng)核心特征在于新能源占據(jù)主導(dǎo)地位，分布式能源大規(guī)模并網(wǎng)接入，成為主要能源形式，為有效提高新型電力系統(tǒng)能源利用率，進一步完善整個電力系統(tǒng)發(fā)電、輸電、用電和儲能環(huán)節(jié)的深度感知[3-5]。對低時延的要求非常高，其中配電網(wǎng)保護與控制、智能配電網(wǎng)微型同步測量都要求低于10 ms的超低時延，一些關(guān)鍵性的控制指令時延要求高達(dá)毫秒級。然而，在傳統(tǒng)的云計算架構(gòu)中，數(shù)據(jù)上傳到遠(yuǎn)程云服務(wù)器需要消耗大量的傳輸時間，核心網(wǎng)有限的帶寬難以承受海量的數(shù)據(jù)傳輸[6]。作為一種更接近業(yè)務(wù)端的新型計算技術(shù)，邊緣計算已經(jīng)成為處理延遲敏感業(yè)務(wù)的有效解決方案，推動新型電力系統(tǒng)能源互聯(lián)網(wǎng)的發(fā)展步伐[7-9]。

文獻[10]基于邊緣計算技術(shù)的邊緣處理能力，對配網(wǎng)業(yè)務(wù)的需求進行分析處理，有效提高業(yè)務(wù)處理能力，降低處理延時。文獻[11]構(gòu)建了基于云邊協(xié)同的配電網(wǎng)絡(luò)故障邊緣網(wǎng)絡(luò)架構(gòu)，實現(xiàn)網(wǎng)絡(luò)狀態(tài)的實時監(jiān)測，有效提高故障定位和隱患排查準(zhǔn)確和時效性。文獻[12]提出了一種基于機器學(xué)習(xí)的邊緣智能任務(wù)卸載模式，通過對正常和故障情況下配電網(wǎng)絡(luò)運行參數(shù)波形進行實時采集和比對分析，保證了配網(wǎng)運行實時和穩(wěn)定性。文獻[13]提出了一種基于邊緣計算的配電網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的最小碰撞診斷算法，在云平臺的邊緣側(cè)引入了邊緣計算終端，并基于距離和處理任務(wù)對終端數(shù)據(jù)資源接入進行合理調(diào)度分配。文獻[14]開發(fā)了一種數(shù)據(jù)驅(qū)動方法，完成配電網(wǎng)的初始故障檢測和定位。

通過上述研究分析發(fā)現(xiàn)，邊緣計算技術(shù)能夠有效地緩解網(wǎng)絡(luò)傳輸延時造成的電力運維和現(xiàn)場作業(yè)的風(fēng)險。但隨著新型電力系緣側(cè)終端數(shù)量的急劇增加，僅依靠單個邊緣設(shè)備依然無法完全滿足所有電力業(yè)務(wù)的時延要求，同時由于邊緣節(jié)點資源有限，單純通過優(yōu)化邊緣節(jié)點資源分配來提高應(yīng)用請求處理速率，對于網(wǎng)絡(luò)時延的改善依然有限?；谏鲜鰡栴}方面，綜合考慮邊緣節(jié)點間和節(jié)點內(nèi)的資源分配，研究了滿足較低服務(wù)延遲的工作負(fù)載分配機制。依托網(wǎng)絡(luò)時延和計算時延，構(gòu)建了一個基于邊緣智能的網(wǎng)絡(luò)負(fù)載分配模型，以最小化新型電力系統(tǒng)負(fù)荷控制類業(yè)務(wù)總體傳輸延時。此外，為進一步降低多業(yè)務(wù)終端的服務(wù)時延，構(gòu)建了一種網(wǎng)絡(luò)負(fù)載資源分配模型。在初始化階段，通過任務(wù)平衡算法來改善邊緣節(jié)點間的工作負(fù)載平衡。為了有效保證資源分配的合理性，提出了一種改進的粒子群優(yōu)化算法，對于邊緣節(jié)點的CPU資源進行有效地分配。在分配的決策中，基于半定規(guī)劃算法，將應(yīng)用任務(wù)分配給邊緣節(jié)點，實現(xiàn)網(wǎng)絡(luò)資源的合理分配。

1 系統(tǒng)模型

隨著新型電力系統(tǒng)的建設(shè)步伐的不斷加快，各種終端設(shè)備的大范圍接入，電網(wǎng)信息業(yè)務(wù)急劇增加，大量數(shù)據(jù)信息上傳到遠(yuǎn)程云端處理器需耗費大量時間和帶寬資源，對云端處理器的數(shù)據(jù)處理造成巨大的挑戰(zhàn)，對此文中構(gòu)建了基于邊緣計算的新型電力系統(tǒng)通信網(wǎng)絡(luò)架構(gòu)如圖1所示。分布式新能源發(fā)電、智能輸配變電、儲能和智慧用電等新型電力業(yè)務(wù)位于網(wǎng)絡(luò)接入側(cè)，基于各類傳感設(shè)備完成各類業(yè)務(wù)狀態(tài)的實時監(jiān)控和靈活感知，并通過有線、4G、5G、電力無線專網(wǎng)等方式將邊緣節(jié)點信息傳輸給邊緣物聯(lián)代理設(shè)備，承擔(dān)遠(yuǎn)端云服務(wù)器最初需處理的部分或全部任務(wù)，完成數(shù)據(jù)的實時計算和智能存儲，有效提高數(shù)據(jù)處理效率，降低任務(wù)處理延時。云端控制器基于典型業(yè)務(wù)數(shù)據(jù)需要，從邊緣設(shè)備中實時調(diào)取相關(guān)數(shù)據(jù)，做到數(shù)據(jù)的靈活靈用，實時調(diào)取。

圖1 基于邊緣計算的新型電力系統(tǒng)通信網(wǎng)絡(luò)架構(gòu)Fig.1 New power system communication network architecture based on edge computing

1.1 基于邊緣計算的新型電力業(yè)務(wù)負(fù)載分配模型

由于需要用戶端(User Ends, UE)提供不同的業(yè)務(wù)，一個用戶端運行新型電力系統(tǒng)業(yè)務(wù)，每種類型的業(yè)務(wù)請求都需要上傳邊緣節(jié)點(Edge Node, EN)通過不同的虛擬機(Virtual Machine, VM)對不同業(yè)務(wù)需求進行處理。為實現(xiàn)多業(yè)務(wù)資源的有效調(diào)度，有必要設(shè)計一種用戶終端如何訪問邊緣節(jié)點的工作負(fù)載分配機制。提出的工作量分配模型如圖2所示，在一個區(qū)域中，I為邊緣節(jié)點的集合，J為用戶端的集合，Kj為UEj中所有新型電力業(yè)務(wù)的總和。其中Kj是在UEj中運行的新型電力業(yè)務(wù)的集合，假設(shè)第k個新型電力業(yè)務(wù)的需求響應(yīng)集合為wjk=[ljk,wjk]。ljk為任務(wù)總量，wjk為負(fù)荷工作量，服從泊松分布[15]。服務(wù)延遲被定義為從請求生成到請求在網(wǎng)絡(luò)上完全處理時的時間，并且代表網(wǎng)絡(luò)的服務(wù)時間。

圖2 任務(wù)分配模型Fig.2 Task allocation model

dijk代表延遲wjk，UEj的第k個業(yè)務(wù)請求分配給ENi。由此可見，UEj的任務(wù)分配是一個Kj→I映射問題?？紤]所有的UE，所有新型電力業(yè)務(wù)的集合為K=∪j∈JKj，任務(wù)分配為J×K→I映射問題。因此，dj和dijk之間的關(guān)系可以表示如下：

(1)

其中xijk是一個二進制變量，如果wjk是分配給ENi，那么xijk=1，否則，xijk=0。

在邊緣計算中，業(yè)務(wù)請求由用戶設(shè)備生成，并通過網(wǎng)絡(luò)信道傳輸?shù)骄W(wǎng)元進行處理。因此，dijk分配給ENi的APPkUEj的延遲，包含了到ENi的網(wǎng)絡(luò)延遲和業(yè)務(wù)請求在ENi中處理所消耗的計算延遲。

(2)

Bj為UEj的傳輸速率，rij為UEj和ENi之間的距離，c為傳播速度。考慮無線電波的反射和繞射，假設(shè)模型分析中Bj足夠大，這就有l(wèi)ijk/Bj?rijk/c，所以接下來主要考慮網(wǎng)絡(luò)延遲，忽略傳輸延遲。其網(wǎng)絡(luò)延遲為：

(3)

計算延遲由EN的計算能力決定，vij為ENi處理第k個應(yīng)用的CPU速率，則計算延遲為：

(4)

1.2 問題形成

V=(vik)×K為EN中VMs(虛擬機)資源分配向量。vik為VMk在ENi的處理速率，vi為邊緣計算節(jié)點數(shù)據(jù)處理速度?；诰W(wǎng)絡(luò)實際運行現(xiàn)狀，合理的調(diào)節(jié)和分配虛擬中的數(shù)據(jù)處理任務(wù)，可有效邊緣節(jié)點的任務(wù)處理時延，達(dá)到最優(yōu)，對其處理速度進行約束：

(5)

0≤vik≤vi

(6)

X=(xijk)I×J×K是一個三維數(shù)組,表示UE和EN中應(yīng)用請求的映射關(guān)系，數(shù)組元素的值規(guī)定如下：

(7)

一個任務(wù)只能分配給一個EN進行處理，因此有以下限制:

(8)

為滿足每個用戶設(shè)備的服務(wù)質(zhì)量要求，用戶設(shè)備的服務(wù)延遲必須小于特定值。設(shè)Tj為UEj的服務(wù)延遲約束，即滿足以下約束：

dj≤Tj

(9)

優(yōu)化目標(biāo)是P1。

(10)

此類問題為一種NP難問題，直接進行求解相對比較困難。

(11)

2 問題優(yōu)化

解決P1的難點在于任務(wù)分配X依賴于EN中的資源分配V，而任務(wù)分配反過來又影響EN中的資源分配。為解決P1問題，提出了一種快速分配算法，將上述問題分解為三個子問題:均衡初始化、資源分配和任務(wù)分配。在初始化過程中，每個用戶設(shè)備生成的應(yīng)用請求被分配給網(wǎng)元。為了避免最近的進化網(wǎng)絡(luò)因計算任務(wù)多而增加的計算延遲， 提出了一種面向網(wǎng)絡(luò)負(fù)載均衡的傳輸機制。資源分配階段，通過在遺傳算法中引入信息素對傳統(tǒng)粒子群算法進行改進。

2.1 平衡初始化

在不考慮數(shù)據(jù)處理時延的情況下，僅需要從數(shù)據(jù)傳輸?shù)臅r延方面分析效率。即使rij(i∈I)最小，優(yōu)化問題P1可表示為P2。

(12)

(13)

由于只考慮網(wǎng)絡(luò)時延，所以與計算時延無關(guān)，也就是說可以忽略UE中新型電力業(yè)務(wù)的類型。P2的維度縮小了，相當(dāng)于P2的問題。找到UE所有最近的EN作為陣列X=(xij)I×J的最優(yōu)解X(0)。

2.2 資源配置

通過平衡初始化，可以解決邊緣節(jié)點(即P3)的計算資源分配問題。

0≤vik≤vi

(14)

為方便后續(xù)求解，需要對變量進行歸一化處理，這里有vik/vi=pik，對應(yīng)的矩陣為P，其中pik為VM中計算任務(wù)占整體處理任務(wù)的比重，因此求解問題可重新表示為：

(15)

提出了一種改進粒子群算法解決P3問題。該算法的本質(zhì)就是基于有限迭代逐漸逼近問題的最小化和最大化函數(shù)，通過交叉求解的方式獲得最優(yōu)解。改進粒子群算法利用蟻群算法中的信息素保留所有粒子的最優(yōu)經(jīng)驗信息，并影響粒子選擇路徑的速度，使算法能夠快速收斂。

位置和速度是粒子群算法中兩個基本參數(shù)，其中的每一粒子位置都對應(yīng)一個可行解。資源分配矩陣為P∈，而速度定義為矩陣U∈。

U∈(n+1)=g(wU∈(n))+c1·r1(n)·(Pb∈(n)-

P∈(n))+c2·r2(n)·(Gb∈(n)-P∈(n))

(16)

式中Pb∈(n)、Gb∈(n)分別為n次迭代后粒子的個體和全局最優(yōu)解。

根據(jù)式(17)更新位置：

P∈(n+1)=P∈(n)+U∈(n+1)

(17)

其中，uik∈[-umax,umax]，umax為最大粒子速度。

(18)

為了滿足終端用戶對低時延網(wǎng)絡(luò)環(huán)境的需求，這部分的重點從降低系統(tǒng)的服務(wù)時延角度出發(fā)，則對應(yīng)適應(yīng)度函數(shù)可表示為：

(19)

為了防止基于傳統(tǒng)PSO算法對網(wǎng)絡(luò)性能進行優(yōu)化，因粒子節(jié)點狀態(tài)無法進行實時上傳，分析容易陷入局部最優(yōu)的風(fēng)險。對此，在傳統(tǒng)PSO算法的基礎(chǔ)上將信息素考慮在內(nèi)，基于想信息素濃度完成位置信息的更新。

基于式(20)完成信息素矩陣的更新：

T(n+1)=(1-ρ)T(n)+ΔT(n)

(20)

式中ρ是信息素?fù)]發(fā)因子。

信息素增量矩陣表示為：

(21)

式中S為信息素的稠密程度；ε為種群規(guī)模。

為了有效反應(yīng)信息素對網(wǎng)絡(luò)路徑選擇的影響，這里通過引入轉(zhuǎn)移概率概念：

(22)

式中φik(n)為第n次迭代后ENi處理k型應(yīng)用的請求概率；ηik和β分別為啟發(fā)因子和對應(yīng)的權(quán)重;a為權(quán)重參數(shù)。

ηik由式(23)計算得出：

(23)

速度更新如下：

U∈(n+1)=g(wU∈(n))+c1·r1(n)·(Pb∈(n)-P∈(n))+c2·r2(n)·(Gb∈(n)-P∈(n))+φ(n)

(24)

MPSO算法的復(fù)雜度是不確定的，近似等于O(N×(I×K)+|ε|)。

2.3 任務(wù)分配

在解決邊緣節(jié)點資源分配問題后，將原來的工作量分配問題簡化為任務(wù)使用目的分配問題，如問題P4：

(25)

(26)

為了簡化問題分析的復(fù)雜性，將P4的問題可以轉(zhuǎn)化為一個等價的問題。通過減少秩1約束，將問題轉(zhuǎn)化為齊次半定規(guī)劃，二元約束可以用二次約束代替。

x(x-1)?x∈{0,1}

(27)

X和ψ表示為一維向量，如下所示：

X=[x111, …,xI11,x121, …,xI21,x1J1, …,xIJ1,

x112,…,xI12,x122, …,xI22,x1J2, …,xIJ2, …,x11K, …,xI1K,x121K,…,xI2K,x1JK, …,xIJK]T

(28)

ψ=[ψ1,ψ2,…,ψJ]T

(29)

定義一個新的變量y=[XTψT]T，其元素yi滿足約束(30)：

yi(yi-1)=0 ?yi∈{0,1},i=1,2,…,

(I×J×K)

(30)

然后，P4的可以轉(zhuǎn)換成P5：

(31)

up是一個(I×J×K+J)維向量，其第p個維度對應(yīng)的數(shù)值為1，其他元素的值全部為0。diag(up)是由up作為對角中的元素構(gòu)成的(I×J×K)×(I×J×K)維對角矩陣。

其他符號解釋如下：

(32)

(33)

b2=[T1T2....TJ]T

(34)

(35)

A1=[B1-B2]

(36)

A2=[0I×J×K-EJ×J]

(37)

A3=[diag(11×I...11×I)(J×K)×(I×J×K)0I×J×K]

(38)

(39)

B2=diag(V…V)(I×J×K)×J

(40)

B3=diag(W1…WK)(I×K)×(I×J×K)

(41)

Wk=[W1k…WJk]I×(I×J)

(42)

Wjk=wjkEI

(43)

V=[v11,...,vI1,v12,...,vI2,...,v1K,...,vIK]T

(44)

定義Z=[yT1]T[yT1]和Q=I×J×K+J，對問題P5進行變換轉(zhuǎn)化為P6：

(45)

等式中的符號如下：

ZQ+1,Q+1是矩陣Z的第(Q+1)行和第(Q+1)列元素。A1,p、A2,t、A3,j分別為矩陣A1、A2和A3對應(yīng)p，t和j行向量。

Z*是最優(yōu)解，利用CVX凸優(yōu)化工具包忽略秩-1約束，如果Z*滿足秩-1約束，P4的最優(yōu)解可以從Z*得到。

從Z*的左上角(I×J×K)×(I×J×K)矩陣中提取的Z′=x*x*T。由于xijk∈{0,1}，因而xijkxijk=xijk，x*可以由Z′的對角線構(gòu)造，工作負(fù)荷分配矩陣X*可以通過使用“整形”運算轉(zhuǎn)換x*得到。

L為樣本數(shù)量，(l)為樣本指數(shù)。通過高斯變換，對Z*不滿足條件進行分析。

算法3總結(jié)了所提出的算法。通過提取左上角的(I×J×K)×(I×J×K)子矩陣Z′作為協(xié)方差矩陣，生成L個隨機(I×J×K)×1維向量。[0.68L]表示向下舍入，對應(yīng)的分布函數(shù)可表示為：

(46)

圖3 基于SDR和高斯隨機的算法流程Fig.3 Algorithm flow based on SDR and Gaussian random

3 仿真結(jié)果分析

搭建仿真環(huán)境對提出的算法進行測試驗證。對于邊緣計算系統(tǒng)的仿真參數(shù)設(shè)置，將物理環(huán)境為設(shè)置為邊長為5 km的正方形區(qū)域。其中EN的數(shù)量為20，UE的數(shù)量為50～200[16-17]。為了保證結(jié)果的合理性，將EN和UE這兩個參數(shù)的距離范圍控制在1 km以內(nèi)。此外，ENs和UEs采用無線的方式進行連接，傳輸速度為54 Mb/s～300 Mb/s[18]。新型電力業(yè)務(wù)存在6種不同的類型，不同類型的新型電力業(yè)務(wù)將采用不同的UE，從而生成對應(yīng)的請求命令。同時，為了突出所提出的基于SDR算法的有效性，與文獻[19-21]的卸載算法進行比對分析。

圖4為邊緣計算節(jié)點基于平衡和最近策略的計算時間。從仿真結(jié)果中可以發(fā)現(xiàn)，距離用戶較近的邊緣節(jié)點計算時延相對較大。因為考慮到系統(tǒng)的整體時延，為降低信息傳輸時延，將更多的工作任務(wù)分配給較近的邊緣節(jié)點進行處理。對此利用所提出的平衡策略能綜合考慮用戶的計算和傳輸時延，對任務(wù)進行合理分配。實驗結(jié)果表明，所提出的平衡策略能夠有效縮小各邊緣節(jié)點的計算上的耗時差異，從而在整體上提高計算效率。

圖4 平衡策略和最近策略初始化時ENs的計算時間Fig.4 Calculation time of ENs when the balance strategy and the most recent strategy are initialized

圖5為不同算法收斂性的對比分析，通過對比分析發(fā)現(xiàn)所提出的圖5為不同算法收斂性的對比分析，通過對比分析發(fā)現(xiàn)所提出的改進粒子群算法(MPSO)[22]相比于蟻群算法(ACO)[23]和傳統(tǒng)粒子群算法(PSO)[24]能夠?qū)崿F(xiàn)快速收斂，同時基于信息共享的策略防止算法陷入局部最優(yōu)的缺陷，通過對比分析發(fā)現(xiàn)MPSO算法的收斂時間比蟻群算法短7.4%。在優(yōu)化效果方面，與粒子群算法相比，MPSO算法的服務(wù)時間減少了18.7%。

圖5 資源分配中應(yīng)用MPSO、粒子群、蟻群 算法的服務(wù)時間Fig.5 Service time of MPSO, particle swarm and ant colony algorithm lied in resource allocation

圖6為算法準(zhǔn)確性與高斯隨機變量之間的關(guān)系?？梢钥闯?，隨著高斯隨機變量數(shù)的增加，相比與其他算法，SDR的解更接近真實解，誤差更低。同時仿真結(jié)果可以看出，隨機變量接入數(shù)量的增加可以顯著降低求解誤差這是因為當(dāng)隨機變量的個數(shù)超過問題的約束個數(shù)時，可以充分滿足求解問題的需要，獲得更精確的結(jié)果。

圖6 結(jié)果準(zhǔn)確性比高斯變量數(shù)量間的關(guān)系Fig.6 Relationship between the accuracy of the results and the number of Gaussian variables

圖7對比分析了新型電力終端接入數(shù)量對系統(tǒng)服務(wù)時延的影響，從圖7中可以看出，服務(wù)時延隨新型電力系統(tǒng)業(yè)務(wù)接入數(shù)量的增加會不斷的加大。所提出的BRT邊緣節(jié)點資源分配算法，相較于SAA算法[25]服務(wù)延遲降低了9.1%。同時，通過對比分析發(fā)現(xiàn)，在相同的終端新型電力業(yè)務(wù)接入數(shù)量下所提出的邊緣計算方式相對傳統(tǒng)的集中式云計算方式,系統(tǒng)的服務(wù)時延得到明顯的改善。

圖7 新型電力業(yè)務(wù)接入數(shù)量與服務(wù)時延之間的關(guān)系Fig.7 Relationship between the access number of new power businesses and the service delay

圖8為服務(wù)時延與新型電力業(yè)務(wù)接入數(shù)量之間的關(guān)系。從圖8中可以看出系統(tǒng)服務(wù)時延與新型電力業(yè)務(wù)接入數(shù)量大概成線性關(guān)系，LEAD算法的增長率最大，因為它無法區(qū)分不同類型應(yīng)用請求的延遲要求。LAB算法可以協(xié)調(diào)計算量大的應(yīng)用請求和計算量小的應(yīng)用請求，因此增長速度稍慢。SAA算法的服務(wù)時延絕對值小于LAB，但由于多種類型的應(yīng)用請求之間沒有區(qū)別，因此增長率仍然沒有降低。所提出的BRT算法能夠?qū)⒉煌愋偷臉I(yè)務(wù)請求分配給邊緣節(jié)點上對應(yīng)的虛擬機，不僅實現(xiàn)了邊緣節(jié)點間的應(yīng)用請求分配，還優(yōu)化了邊緣節(jié)點內(nèi)的計算資源分配。因此，增長率較小。

圖8 不同數(shù)量新型電力業(yè)務(wù)的服務(wù)時間Fig.8 Service hours of different numbers of new power businesses

4 結(jié)束語

在新型電力系統(tǒng)建設(shè)過程中資源有限的單一邊緣節(jié)點的固有特性已無法滿足大規(guī)模接入的新型電力業(yè)務(wù)的延遲要求。對此文章研究了一種基于邊緣智能的新型電力系統(tǒng)最小服務(wù)延遲的負(fù)載分配模型，推導(dǎo)出在信息傳輸速率和最大任務(wù)總量等約束條件下的系統(tǒng)傳輸時延，將目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)問題分別求解，為了避免最近的進化網(wǎng)絡(luò)因計算任務(wù)多而增加的計算延遲， 提出了一種面向網(wǎng)絡(luò)負(fù)載均衡的傳輸機制。通過在遺傳算法中引入信息素對傳統(tǒng)粒子群算法進行改進，有效降低資源分配過程中的處理時延。仿真結(jié)果表明：與其他資源調(diào)度算法相比，無論是在系統(tǒng)時延還是算法收斂性方面都具有明顯的優(yōu)勢。下一步，針對不同形態(tài)的業(yè)務(wù)類型可開展制定化的低時延邊緣處理方案研究，并通過聚類分析完成業(yè)務(wù)類型的遞歸分類。