面向新型電力系統的最小服務延遲的負載分配算法研究

張秋雨，蔣云峰，張常穩，張一鳴

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

0 引 言

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

文獻[10]基于邊緣計算技術的邊緣處理能力，對配網業務的需求進行分析處理，有效提高業務處理能力，降低處理延時。文獻[11]構建了基于云邊協同的配電網絡故障邊緣網絡架構，實現網絡狀態的實時監測，有效提高故障定位和隱患排查準確和時效性。文獻[12]提出了一種基于機器學習的邊緣智能任務卸載模式，通過對正常和故障情況下配電網絡運行參數波形進行實時采集和比對分析，保證了配網運行實時和穩定性。文獻[13]提出了一種基于邊緣計算的配電網絡拓撲結構的最小碰撞診斷算法，在云平臺的邊緣側引入了邊緣計算終端，并基于距離和處理任務對終端數據資源接入進行合理調度分配。文獻[14]開發了一種數據驅動方法，完成配電網的初始故障檢測和定位。

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

1 系統模型

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

圖1 基于邊緣計算的新型電力系統通信網絡架構Fig.1 New power system communication network architecture based on edge computing

1.1 基于邊緣計算的新型電力業務負載分配模型

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

圖2 任務分配模型Fig.2 Task allocation model

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

(1)

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

在邊緣計算中，業務請求由用戶設備生成，并通過網絡信道傳輸到網元進行處理。因此，dijk分配給ENi的APPkUEj的延遲，包含了到ENi的網絡延遲和業務請求在ENi中處理所消耗的計算延遲。

(2)

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

(3)

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

(4)

1.2 問題形成

V=(vik)×K為EN中VMs(虛擬機)資源分配向量。vik為VMk在ENi的處理速率，vi為邊緣計算節點數據處理速度。基于網絡實際運行現狀，合理的調節和分配虛擬中的數據處理任務，可有效邊緣節點的任務處理時延，達到最優，對其處理速度進行約束：

(5)

0≤vik≤vi

(6)

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

(7)

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

(8)

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

dj≤Tj

(9)

優化目標是P1。

(10)

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

(11)

2 問題優化

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

2.1 平衡初始化

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

(12)

(13)

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

2.2 資源配置

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

0≤vik≤vi

(14)

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

(15)

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

位置和速度是粒子群算法中兩個基本參數，其中的每一粒子位置都對應一個可行解。資源分配矩陣為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次迭代后粒子的個體和全局最優解。

根據式(17)更新位置：

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

(17)

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

(18)

為了滿足終端用戶對低時延網絡環境的需求，這部分的重點從降低系統的服務時延角度出發，則對應適應度函數可表示為：

(19)

為了防止基于傳統PSO算法對網絡性能進行優化，因粒子節點狀態無法進行實時上傳，分析容易陷入局部最優的風險。對此，在傳統PSO算法的基礎上將信息素考慮在內，基于想信息素濃度完成位置信息的更新。

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

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

(20)

式中ρ是信息素揮發因子。

信息素增量矩陣表示為：

(21)

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

為了有效反應信息素對網絡路徑選擇的影響，這里通過引入轉移概率概念：

(22)

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

η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算法的復雜度是不確定的，近似等于O(N×(I×K)+|ε|)。

2.3 任務分配

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

(25)

(26)

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

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的可以轉換成P5：

(31)

up是一個(I×J×K+J)維向量，其第p個維度對應的數值為1，其他元素的值全部為0。diag(up)是由up作為對角中的元素構成的(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進行變換轉化為P6：

(45)

等式中的符號如下：

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

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

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

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

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

(46)

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

3 仿真結果分析

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

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

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

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

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

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

圖6 結果準確性比高斯變量數量間的關系Fig.6 Relationship between the accuracy of the results and the number of Gaussian variables

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

圖7 新型電力業務接入數量與服務時延之間的關系Fig.7 Relationship between the access number of new power businesses and the service delay

圖8為服務時延與新型電力業務接入數量之間的關系。從圖8中可以看出系統服務時延與新型電力業務接入數量大概成線性關系，LEAD算法的增長率最大，因為它無法區分不同類型應用請求的延遲要求。LAB算法可以協調計算量大的應用請求和計算量小的應用請求，因此增長速度稍慢。SAA算法的服務時延絕對值小于LAB，但由于多種類型的應用請求之間沒有區別，因此增長率仍然沒有降低。所提出的BRT算法能夠將不同類型的業務請求分配給邊緣節點上對應的虛擬機，不僅實現了邊緣節點間的應用請求分配，還優化了邊緣節點內的計算資源分配。因此，增長率較小。

圖8 不同數量新型電力業務的服務時間Fig.8 Service hours of different numbers of new power businesses

4 結束語

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