電力物聯網邊緣計算終端部署與業務分配優化方法

陳元櫸，蔡澤祥，孫宇嫣，岑伯維，胡凱強，武志剛

(華南理工大學電力學院，廣州510640)

0 引言

在電力物聯網中[1]，智能設備數量巨大，待處理信息量呈爆炸式增長，有效降低邊緣數據的處理延時成為目前亟需解決的問題之一[2]。目前，邊緣計算技術在電力物聯網中的應用存在“邊-邊交互”及“邊-端交互”等方式[3 - 5]，且邊緣計算終端(edge computing terminals，ECT)具有一定的業務處理獨立性。ECT的所處位置、管控區域及其承擔的業務直接影響系統數據傳輸特性與處理特性等[6 - 8]，故在多臺ECT協同處理系統數據架構下，合理部署ECT對提高系統數據處理實時性、計算資源利用率具有重要意義。

目前，對于復雜網絡中節點的劃分，文獻[9]提出一種利用節點連接關系確定子圖的劃分方法，該方法并未充分考慮節點位置差異對部署方案的影響。對于智能終端部署，文獻[10]提出一種適用于電纜監測的邊緣計算終端部署節點的規劃方法。文獻[11]提出一種云邊協同模式下的電力終端控制方法，該方法結合密度和距離兩個因素，采用聚類的思想部署電力終端，該方法未充分考慮終端間相互交互對終端部署的影響。文獻[12]提出一種基于需求分析的云計算資源部署方法。針對任務分配，文獻[13]根據用戶體驗質量建立霧計算場景下的模糊模型，以最大化用戶體驗質量為目標實現任務的分配。文獻[14]介紹一種任務卸載決策算法，考慮設備有限的供電能力與任務最大允許延時較小的情況，可有效均衡設備能耗與計算任務處理時間，但未充分考慮業務間的關聯關系對終端部署的影響。

多“邊”協同的業務處理方式是提高邊緣區域業務處理自動化的主要手段之一，ECT部署與業務分配是直接影響業務處理特性的主要原因，ECT部署時考慮其承擔的業務類型的影響對提高業務處理性能具有重要意義。而上述研究均將ECT部署與業務分配當成獨立的研究內容，并未充分考慮兩者的相互影響對提高業務處理實時性的作用。本文提出一種電力物聯網的ECT部署與業務分配方法，首先提出一種考慮業務關聯的多ECT處理架構，根據業務的關聯關系及業務在ECT間的分配情況，系統內ECT間的交互呈現多元結果。其次，根據系統節點分布提出ECT管控節點的劃分方法，為ECT部署奠定基礎。再次，建立考慮業務關聯的ECT部署與業務分配的雙層模型，外層模型根據內層模型的ECT部署方案求解最優的業務分配結果，內層模型根據外層的業務分配情況確定最優的ECT部署方案，通過分析內、外層模型間的相互影響以實現系統業務處理實時性的最優。最后，利用求解器CPLEX求解該雙層模型的最優解，并利用算例驗證了本文所提模型與方法的有效性與先進性。

1 系統模型

1.1 邊緣計算終端信息處理架構

如圖1所示，系統的通信拓撲結構包含數據分析設備、采集設備與指令執行終端，前者指ECT，后兩者指數據節點(data points，DP)上實現數據采集與指令操作功能的物理設備。在信息處理過程中，DP的數據信息上送至ECT，ECT根據系統分配的業務實現對接收的數據的處理，并將處理結果信息與其他ECT進行通信共享，而ECT將處理指令下達至執行終端并由其完成，執行終端將處理完的結果返回ECT[15 - 16]。在上述過程中，節點間通信鏈路的構建取決于業務間的處理關系及信息流的傳輸[17 - 18]。

圖1 電力物聯網通信拓撲結構Fig.1 Communication topology in power Internet of Things

1.2 業務處理模型

本文考慮ECT處理的業務信息如表1所示，包括基礎業務與應用服務兩類，基礎業務指ECT對管控范圍內每個DP均需完成的處理任務，應用服務指在完成基礎業務后的一些高級應用服務。本文考慮系統的應用服務的數據處理任務由一臺ECT完成，故分別將每個應用服務部署于一臺ECT上。基礎業務與應用服務間的處理關系如圖2所示，設表1中的業務處理邏輯分為并行處理與串行處理[19]，對于每臺ECT需執行的基礎業務均可并行處理，并將處理結果按業務處理邏輯輸入至下一業務APP；對于APP3與APP4，在接收到APP2的處理結果時，可并行處理；基礎業務APP實現對數據采集與預處理，APP1將采集的數據傳輸至APP2；將應用服務分為監測類應用服務APP與分析類服務APP，APP3與APP4在接收到APP2的處理結果時，可并行處理APP2的處理數據；APP5、APP6與其他業務為串行處理關系，APP3與APP4的處理結果輸入至APP5，待APP5處理完成后，將APP3與APP4、APP5的處理結果輸入至APP6，完成整個業務處理時序邏輯，做出相應的指令。

表1 系統業務的相關參數Tab.1 Related parameters of service application

圖2 系統業務及其關聯關系Fig.2 System services and their relationship

2 ECT部署與業務分配雙層模型

數據處理延時主要來自數據傳輸、處理的過程，一方面ECT承擔的應用服務不同將影響ECT間的數據傳輸特性及其本身的數據處理延時，另一方面ECT管控區域及其所處位置影響ECT承擔的應用服務類型，即在系統數據處理過程中，ECT的部署位置與應用服務的分配存在耦合關系[20]。因此提出利用雙層模型實現對ECT的部署以及應用服務的優化分配。其中外層模型以總處理延時最小為目標求解系統應用服務在各ECT間的分配；內層模型以傳輸延時最小為目標求解ECT在節點簇內的部署。

2.1 外層模型

對于內層模型中每種ECT部署方案，外層模型可計算得到一種實時性最優的應用服務分配方案，外層模型在遍歷所有方案后確定總延時最小的應用服務分配方案及其對應的ECT部署情況。

1)目標函數

以優化系統數據處理延時為目標，如式(1)所示。

minDsum=Dt+Dc

(1)

式中：Dsum為處理總延時；Dt為總計算延時；Dc為總通信延時；i為數據源節點編號；a為APP編號；下標e、e′均為ECT編號，用以區分不同的ECT；tae為計算延時，表示ECTe處理APPa時產生的計算延時；die為數據源節點i與ECTe間的通信延時，dee′為ECTe與ECTe′間的通信延時。

2)計算模型

DP業務數據處理響應時間包括ECT中業務應用模型對數據的處理時間tae，該延時主要與ECT分配給該任務的處理頻率及數據處理的負荷有關。在ECT內，任務處理時占用CPU資源，所需的處理時間以經過的CPU時鐘周期(CPU cycle)的多少進行表征，當以單位處理頻率f0處理APPa時，APPa所需的時鐘周期為wa，即APPa在ECT內產生的負荷為wa。ECT根據其承擔的處理業務不同，對其CPU資源進行分配，當處理任務獲得的CPU資源愈多，其所需的處理時間愈少，本文以同一時刻下處理APPa的處理頻率fae表征APPa獲得的CPU資源。因此，可利用式(2)表征計算延時tae。在電力物聯網中DP數據動態變化，導致不同業務應用APP的負荷動態變化，而在一段時間內，ECT分配給APPa的計算資源基本不變[21]。為了更好實現ECT部署與業務分配優化，提出利用單位計算延時t0對tae進行簡化，t0為單位處理頻率f0處理單位負荷w0時產生的計算延時，所以當fae給定時，計算延時tae為t0的倍數，其動態變化關系與wa相同。

(2)

(3)

式中：wa為ECTe處理應用服務APPa產生的負荷；fae為ECTe處理業務應用APPa時的處理頻率；ζae為0- 1變量，當ECTe完成業務a的處理任務時ζae=1， 反之ζae=0。表1中業務負荷wa與處理的數據量有關；Fe為ECTe所能提供的最大處理頻率。

3)通信模型

數據在通信網絡的傳輸造成傳輸延時與傳輸的數據量大小成正相關、與傳輸速率成負相關，所以刻畫DPi與ECTe間的傳輸延時die如式(4)所示。本文考慮uie由多個基本數據單元u0組成，在一定數據傳輸速率R0下，u0在傳輸單位距離l0時產生的延時為d0。一般而言，節點間采用的通信方式不變，即傳輸速率不變，傳輸延時可簡化為單位傳輸延時d0的倍數，且傳輸延時的變化情況與傳輸數據量的變化情況相同。de′e為分布式部署時ECT間的通信延時，其計算方法同die，僅將式(4)中下標i替換為另一臺ECT的下標e′。

(4)

(5)

(6)

2.2 內層模型

1)目標函數

本文將ECTe管控的DP稱為一個節點簇Se(節點簇與ECT采用相同的編號e)，系統各節點簇Se的并集為Ssum。在系統通信架構中，ECT與節點簇內DP及系統其他ECT間的相對位置關系直接影響節點簇的數據傳輸延時，據此本文提出內層模型以實現ECT于節點簇中的部署，使系統業務處理延時最小。根據外層模型中通信延時的刻畫，建立內層模型的目標函數如式(7)所示。

minDc

(7)

2)節點簇劃分

在內層模型中，實現節點簇內ECT的部署的前提是對DP進行劃分，劃分依據主要考慮ECT管控的DP數量及其位置。當DP數據處理產生的計算負荷相同時，ECT管控DP數量相同可使各計算設備間負載較均衡。故設ECTe管控的節點數為he，根據系統ECT數量K與DP數量n確定ECT管控的平均節點數量he，如式(8)所示。

(8)

式中：PInt表示整數部分；PMod表示小數部分。當PMod≠0時，系統存在[K×(1-PMod)]臺ECT管控的DP數量為PInt，(K×PMod)臺ECT管控的節點數為(PInt+1)。

確定節點簇內的節點數量后，本文考慮節點簇劃分依據是使節點簇節點距離之和最小，如式(9)所示。式(10)所示為一個NP-hard問題[22]，故本文提出利用系統節點的分布位置關系對該NP-hard問題進行近似求解，即根據系統已知條件對上述問題進行約束，包括：1)存在與其他所有節點的相對距離之和最小的節點Vi，距離Vi較遠的一些位于拓撲結構邊界處的節點，僅能與其最近的若干個節點組成節點簇；2)任意選取he個節點構成節點簇，對節點簇內節點的相對距離之和的最小值進行排序得到A，選取距離之和最小的前m個節點簇，在滿足式(9)的約束下，本文所求Ssum必存在于A中。此外，m的選取影響系統節點簇劃分的精確性與計算速率。

(9)

(10)

式中：Lsum為各節點簇ECT與DP距離之和的最小值；Lemin為ECTe所在節點簇的ECT與DP距離之和的最小值；lie為DPi與ECTe間的距離；φ為空集；SK為第K個節點簇中所有DP構成的集合；∪、 ∩分別為集合的并、交運算。

3 模型處理與求解

3.1 其他約束條件

1)約束條件線性化

CPLEX求解器是求解線性優化問題、混合整型規劃問題的常用工具，可靈活快速求解規劃問題的最優解[23]，是目前求解優化問題的主要手段之一[24]，因此，本文提出利用CPLEX求解上述優化問題。在上述雙層模型中，連續變量與離散變量間的乘積造成系統模型的強非線性，為利用CPLEX求解該模型，需對上述模型中非線性部分進行線性化變化[25]。利用麥考密克凸包絡法實現對式(2)的taefae進行線性化，如式(11)所示。

(11)

利用方形約束實現對式(9)中lie的非線性表征進行轉換[26]，如式(12)所示。

(12)

在利用CPLEX進行求解過程之前，需對系統相關參數進行設置及定義傳輸延時、計算延時變量及相關的中間變量。中間變量用于表示對延時變量的約束，或表示多變量的乘積。表示多變量乘積的變量需用式(11)—(13)所示的多組不等式約束進行等價替換。其次，將上述ζie與ζae設為求解變量，即為CPLEX的決策變量。

(13)

式中：下標U、L分別表示該變量的最大值、最小值，如fae,U、fae,L分別為fae的最大值、最小值。

2)延時約束條件

不同業務對數據處理實時性需求不同，利用式(14)所示的約束條件進行約束，即

(14)

式中：dea為ECTe處理APPa時產生的延時；de為ECTe處理各種APP產生的延時；da為APPa的延時容忍度。

3.2 模型求解

1)節點簇劃分

針對上述NP-hard問題的約束，提出系統節點簇劃分流程如圖3所示，虛線框中為節點簇內的節點相對距離之和Le min的求解流程，得到節點簇Ssum。

圖3 節點簇劃分流程圖Fig.3 Flow chart of node cluster partition

2)雙層模型嵌套求解

系統業務處理成本分析過程中，需要同時考慮ECT管控的節點及其部署節點的選取，以及ECT協同處理的業務類型。在實現節點簇劃分的基礎上，上述雙層模型等價為求解ζie與ζae， 雙層模型求解算法如圖4所示。

圖4 雙層優化算法Fig.4 Bi-layer optimization algorithm

4 算例分析

4.1 參數設置

為了驗證本文所提模型與方法的可行性與有效性，根據電力物聯網實際運行情況，在如圖1所示的某地區30節點系統中，以節點V9為參考節點，利用節點的相對位置關系，形成各節點的位置信息，令該地區ECT的數量為K=6，設每臺ECT的最大處理能力為Fe=3.2 GHz；令d0=t0=20 ms；且ECT處理業務相關參數如表2所示，ECT業務處理信息流如圖2所示[27 - 28]。

表2 業務應用的相關參數Tab.2 Related parameters of service application

4.2 節點簇劃分

對于n節點系統而言，任意he個節點的組合存在[n!/(K×he!)]種方案，即在圖1所示的30節點系統中約存在3.684×1029種ECT管控方案。本文考慮對NP-hard問題的約束條件為：1)V26與V6、V21與V3、V4與V24等綁定在同一節點簇內；2)將距離V9較遠的若干個邊界節點與它們最近的(he-1)個節點構成一個Ssum，并將各節點簇的節點距離之和進行排序，得到A。選取Lsum最小的組合作為系統節點簇劃分依據。隨后利用仿真軟件確定滿足式(12)所示模型的節點分簇方案，如表3所示。

表3 節點簇劃分及終端部署與應用服務分配結果Tab.3 The results of node cluster partition, ECT deployment and services allocation

4.3 延時分析及終端部署與應用服務分配

針對節點傳輸的數據量差異，研究不同場景下業務計算時的傳輸延時大小，以DP數據相同時為場景1，當DP的數據波動情況不同時記為場景2～4，其中場景2中的數據相較場景1的變化率為1.67%；場景3中的數據相較場景1的變化率為27.08%；場景4中的數據相較場景1的變化率為9.58%。并將場景1中的業務數據處理延時從大到小排序，得到如圖5所示的曲線，橫坐標表示內層模型求解的應用服務分配方案，按場景1的業務分配方案排序方式獲取其他場景的延時曲線，如圖5所示。可知當DP數據動態變化時，系統完成數據處理產生的延時隨應用服務的分配方案不同的變化趨勢基本一致，且當DP數據一致時系統的延時曲線最低，即場景1的延時變化曲線低于場景2～4的延時變化曲線。

圖5 不同場景中的總延時Fig.5 Total latency in different scenarios

以圖5所示的延時最小的應用服務分配方案作為系統應用服務分配方案，如表3所示，并據此計算完成系統各業務的計算所需的延時大小，各ECT承擔業務處理時產生的總延時，其結果如圖6所示。圖6(a)為不同場景中各業務總處理延時的變化情況，其中橫坐標為業務的種類，縱坐標為延時大小，不同顏色的柱狀圖表示不同的場景。圖6(b)為不同場景中ECT承擔業務處理時產生的總延時，其中橫坐標表示不同場景，縱坐標表示延時大小，不同顏色的柱狀圖表示不同的ECT。

一般而言，業務的負荷較大時，處理延時較大。如圖6(a)中，業務5與業務6的處理延時明顯高于其他業務，從而導致承擔這些業務的ECT的處理延時高于其他ECT，如圖6(b)中ECT5與ECT6的總延時明顯高于其他ECT。但是當業務負荷相對較小，而處理的數據量較大時，總處理延時也將達到較高水平，如圖6(a)中業務2的處理延時與業務5的基本一致，而業務2與業務5的負荷相差較大，即相同業務處理數據量的累積將影響業務負荷。

圖6 各業務與各ECT的處理總延時Fig.6 Total latency of each service and each ECT

分別以業務與ECT為研究對象，由圖6(a)計算不同場景下各業務的總處理延時，由圖6(b)計算不同場景下各ECT處理其承擔的業務的從延時，可以得到兩者的結果相同，即可以確定圖6中在不同場景下各業務總延時大小總是與各ECT處理總延時保持一致。由表2的業務參數及表3的業務分配情況，當ECT承擔較多類型或數量的處理業務時，ECT的負荷較大，如ECT5與ECT6。為保證ECT5與ECT6在分別處理負荷較大的APP6與APP5時，能夠滿足延時要求，APP6與APP5將占用ECT的主要的CPU資源，從而導致ECT5與ECT6承擔的其他業務的處理延時增加，如APP1與APP2，從而導致業務的總延時增加或ECT的處理總延時增加，如圖6(a)中業務2的處理總延時高于業務3與業務4，圖(b)中ECT3與ECT4的處理總延時遠小于ECT5與ECT6的總處理延時。

為比較本文所提模型與方法的優勢，在場景一中比較本文所提方法與其他方法如top-k[29]、K-means[30]與Random下的ECT部署與業務分配的結果，如表4所示，其中O(·)表示所用算法的復雜度的數量級運算。從表4的結果可知，Random方法下延時明顯高于其他3種方法；而利用top-k與K-means方法計算出的ECT部署與業務分配結果，系統業務處理所能達到的最小延時高于本文所用方法；且基于圖1所示的系統拓撲結構，本文方法的復雜度為常數階，而top-k與K-means方法的復雜度分別為線性對數階、線性階。此外，top-k與K-Means方法下ECT負荷的平衡程度較本文所用方法差。

表4 不同方法下的ECT部署與業務分配結果比較Tab.4 Comparison of ECT deployment and service allocation results under different methods

5 結論

本文基于電力物聯網邊緣數據節點的分簇，考慮ECT部署與業務處理關聯關系，建立相應的雙層模型，利用仿真軟件模擬30節點系統信息的場景，分析得到以下結論。

1)利用本文所提的考慮業務關聯的ECT處理架構，可實現多ECT間的業務信息的靈活交互，實現邊緣區域業務處理自動化。

2)節點分簇方法有效劃分ECT管控的數據節點，減少數據節點與ECT間的通信延時，提高業務處理的實時性，對大規模節點群的分簇具有借鑒意義。

3)在ECT部署過程中，ECT承擔的業務類型與數量影響其分配給每個業務的CPU資源數量。當其承擔的某種業務的負荷較大時，為滿足延時約束條件，該業務占用了ECT的主要CPU資源，導致同一ECT承擔的其他業務處理延時增大。

4)ECT部署影響傳輸延時，而ECT承擔的業務類型影響計算延時，綜合考慮兩者的相互影響從而確定ECT在節點簇內的部署與ECT承擔的業務類型，達到系統業務處理總延時最小，該方法為電力物聯網智能設備的部署與處理任務的分配提供借鑒意義。