陳元櫸，蔡澤祥，岑伯維，胡凱強(qiáng)，武志剛，康逸群

（華南理工大學(xué)電力學(xué)院，廣東省廣州市510641）

0 引言

隨著電力物聯(lián)網(wǎng)的發(fā)展，電力末端設(shè)備如傳感器、智能電表等呈現(xiàn)海量接入的態(tài)勢(shì)［1-2］，異構(gòu)多源的信息數(shù)據(jù)在爆發(fā)式增長(zhǎng)的同時(shí)也催生出多元化、生態(tài)化的配電網(wǎng)業(yè)務(wù)需求［3-4］。配電網(wǎng)中的數(shù)據(jù)測(cè)點(diǎn)分散且分布廣泛，傳統(tǒng)主站的集中式處理難以提供可靠的數(shù)據(jù)處理支持，“一測(cè)點(diǎn)一機(jī)”的智能終端配置方式難以實(shí)現(xiàn)。邊緣計(jì)算為實(shí)現(xiàn)信息就地化處理、計(jì)算資源供需平衡提供了重要技術(shù)手段。邊緣計(jì)算終端（edge computing terminal，ECT）是邊緣區(qū)域的信息、業(yè)務(wù)聚合中心，實(shí)現(xiàn)對(duì)若干分散測(cè)點(diǎn)的數(shù)據(jù)進(jìn)行匯集、處理，使配電網(wǎng)數(shù)據(jù)處理呈現(xiàn)出“分布聚合”的特點(diǎn)［5-7］。

ECT 多采用分布式部署，多ECT 協(xié)同被廣泛應(yīng)用于處理邊緣區(qū)域的自主決策業(yè)務(wù)［8-9］。業(yè)務(wù)的處理需要獲取全域節(jié)點(diǎn)的數(shù)據(jù)信息，且在將業(yè)務(wù)分解為若干子任務(wù)進(jìn)行處理時(shí)，各子任務(wù)需遵循一定的邏輯耦合關(guān)系［10-11］。在多ECT 協(xié)同系統(tǒng)中，每臺(tái)ECT 管控一個(gè)節(jié)點(diǎn)簇（node cluster，NC），不同ECT部署與任務(wù)分配策略將導(dǎo)致計(jì)算資源的供需關(guān)系和服務(wù)質(zhì)量產(chǎn)生偏差［12-15］。因此，合理決策ECT 的部署位置及其承擔(dān)的任務(wù)，適應(yīng)ECT 分布式部署與任務(wù)耦合下的計(jì)算資源供需平衡，對(duì)優(yōu)化信息流分布、降低任務(wù)處理成本、提高資源利用率等具有重要意義。

目前，智能終端部署與多處理器系統(tǒng)中的任務(wù)分配是重要的研究課題，文獻(xiàn)［16-17］提出了在分布式多代理系統(tǒng)中的任務(wù)分配方法與調(diào)度方法。時(shí)延、能耗或成本等是重要的評(píng)價(jià)指標(biāo)，文獻(xiàn)［18］提出了一種移動(dòng)邊緣計(jì)算技術(shù)下的智能設(shè)備部署與任務(wù)分配方法，可以使能耗最小化。文獻(xiàn)［19］提出了利用微云部署降低任務(wù)卸載終端的概率，減少云服務(wù)器的延時(shí)、傳輸功耗。文獻(xiàn)［20］提出了一種考慮業(yè)務(wù)可靠性的任務(wù)分配方法，實(shí)現(xiàn)任務(wù)卸載時(shí)的成本最小化。上述研究主要以達(dá)到能耗等某方面性能最優(yōu)為目標(biāo)，缺少考慮計(jì)算資源層面或通信層面的耦合關(guān)系以及多智能終端間的協(xié)同效應(yīng)。文獻(xiàn)［21］提出了一種基于需求分析的計(jì)算資源部署方法，為解決計(jì)算資源供需平衡提供了借鑒意義。

本文提出一種考慮配電網(wǎng)任務(wù)耦合的ECT 部署與任務(wù)分配方法。首先，提出基于NC 劃分的邊緣計(jì)算架構(gòu)并提出任務(wù)處理模型，刻畫任務(wù)的處理特征及不同任務(wù)間耦合關(guān)系。其次，建立考慮ECT部署與任務(wù)分配的雙層模型，其中，上層模型求解任務(wù)在ECT 間的分配問(wèn)題，下層模型求解ECT 在NC內(nèi)的部署。再次，分析雙層模型間的耦合關(guān)系，提出改進(jìn)的K-means 法實(shí)現(xiàn)NC 的劃分，并利用帶邊界條件的隱枚舉法求解該雙層模型。最后，利用算例驗(yàn)證了本文所提方法的有效性與可行性。

1 邊緣計(jì)算架構(gòu)與任務(wù)處理模型

1.1 基于NC 劃分的邊緣計(jì)算架構(gòu)

根據(jù)配電網(wǎng)中節(jié)點(diǎn)的計(jì)算資源差異將系統(tǒng)節(jié)點(diǎn)分為數(shù)據(jù)節(jié)點(diǎn)（data point，DP）與邊緣計(jì)算節(jié)點(diǎn)［22-23］。DP 分布廣泛，其位置與配電網(wǎng)實(shí)際運(yùn)行控制、接入對(duì)象相關(guān)，如開閉所、負(fù)荷開關(guān)、充電樁等在內(nèi)的數(shù)據(jù)獲取，DP 將待處理數(shù)據(jù)上傳至最近的ECT。邊緣計(jì)算節(jié)點(diǎn)部署有ECT，受限于計(jì)算資源與通信資源數(shù)量，ECT 僅管控一定范圍內(nèi)的DP，將ECT 管控的若干DP 構(gòu)成的集合稱為NC。ECT 是邊緣區(qū)域的信息聚合中心，實(shí)現(xiàn)NC 內(nèi)分散分布的DP 請(qǐng)求的任務(wù)聚合處理，即DP 的廣泛分布與ECT管控的NC 共同構(gòu)成配電網(wǎng)“分布聚合”的數(shù)據(jù)處理特征。邊緣計(jì)算架構(gòu)如圖1 所示。

圖1 配電網(wǎng)邊緣計(jì)算架構(gòu)Fig.1 Architecture of edge computing in distribution network

根據(jù)配電網(wǎng)業(yè)務(wù)處理時(shí)的數(shù)據(jù)來(lái)源差異將任務(wù)抽象為單節(jié)點(diǎn)請(qǐng)求和多節(jié)點(diǎn)請(qǐng)求任務(wù)兩大類，即下文所述的單終端任務(wù)（single-terminal task，STT）和跨終端任務(wù)（cross-terminal task，CTT）。在CTT 的處理過(guò)程中，ECT 需要獲取不同NC 內(nèi)的處理數(shù)據(jù)，處理數(shù)據(jù)與任務(wù)間的耦合關(guān)系是邊緣計(jì)算架構(gòu)中多ECT 協(xié)同機(jī)制的基礎(chǔ)。在多ECT 協(xié)同過(guò)程中，數(shù)據(jù) 交 互 方 式 包 括：1）NC 內(nèi) 的DP 與ECT 的 數(shù) 據(jù) 交互，通信雙方屬于不同節(jié)點(diǎn)層級(jí)，構(gòu)成邊緣計(jì)算架構(gòu)中的垂直式架構(gòu)；2）不同ECT 間的數(shù)據(jù)交互，通信雙方均為邊緣計(jì)算節(jié)點(diǎn)，構(gòu)成邊緣計(jì)算架構(gòu)中的水平式架構(gòu)［24］。

1.2 任務(wù)的特征模型

1.2.1 STT 和CTT

STT 是指由單DP 請(qǐng)求的處理任務(wù)，在ECT 管控 的NC 內(nèi)，各DP 的STT 請(qǐng) 求 由 該ECT 處 理。CTT 是指該類任務(wù)的處理需獲取邊緣區(qū)域中的多個(gè)NC 內(nèi)DP 的采集數(shù)據(jù)，在ECT 間產(chǎn)生數(shù)據(jù)交互。一般而言，STT 的計(jì)算負(fù)荷與延時(shí)容忍度較小、任務(wù)周期較短；CTT 的計(jì)算負(fù)荷與延時(shí)容忍度較大、任務(wù)周期較長(zhǎng)。

1.2.2 任務(wù)計(jì)算負(fù)荷

在通過(guò)建立任務(wù)的特征模型表征不同類型任務(wù)處理時(shí)，需要滿足計(jì)算資源及延時(shí)容忍度，其中，對(duì)計(jì)算資源的需求表征為任務(wù)的計(jì)算負(fù)荷。計(jì)算負(fù)荷的大小與任務(wù)類型、處理數(shù)據(jù)量大小有關(guān)，表達(dá)式為：

式 中：θa為 任 務(wù)a的 特 征 模 型；pa為 任 務(wù)a的 類 型；wa（t）為任務(wù)a在時(shí)刻t的計(jì)算負(fù)荷；Ta為任務(wù)a的延時(shí)約束；qa為處理pa類任務(wù)時(shí)單位數(shù)據(jù)量的計(jì)算負(fù)荷；ua（t）為任務(wù)a在時(shí)刻t的數(shù)據(jù)量；W為m個(gè)任務(wù)構(gòu)成的向量。

1.3 任務(wù)處理耦合模型

1.3.1 任務(wù)處理時(shí)序邏輯鏈

將m個(gè) 任 務(wù) 分 為m1個(gè)STT 與m2個(gè)CTT，則m1+m2=m。將ECT 在滿足STT 的處理需求后剩余的資源稱為剩余資源，剩余資源的數(shù)量影響ECT 處理CTT 時(shí)的計(jì)算延時(shí)。在處理m2個(gè)CTT時(shí)，利用處理時(shí)序邏輯鏈表征跨終端業(yè)務(wù)分解的若干CTT 的耦合關(guān)系，CTT 的耦合關(guān)系表現(xiàn)為任務(wù)間的承接與并列關(guān)系。

配電網(wǎng)自動(dòng)化與系統(tǒng)用戶行為的相互作用使配電網(wǎng)的能量傳輸關(guān)系發(fā)生變化，ECT 承擔(dān)的任務(wù)主要涉及用戶側(cè)的能量分析控制等計(jì)算，故將其統(tǒng)稱為能量管理業(yè)務(wù)。將能量管理業(yè)務(wù)進(jìn)行如下分解：CTT1表示電壓與無(wú)功控制；CTT2表示電力負(fù)荷管理；CTT3表示設(shè)備管理；CTT4表示停電與檢修管理；CTT5表示源荷儲(chǔ)微交易；CTT6表示配電運(yùn)行輔助決策。圖2 為能量管理業(yè)務(wù)分解為6 個(gè)CTT 時(shí)的處理時(shí)序邏輯關(guān)系［8-9，25-27］。在同一處理周期中，CTT 的承接關(guān)系表現(xiàn)為任務(wù)在時(shí)間軸上的先后順序，同一時(shí)序邏輯鏈上位于前方的CTT 處理完成后，將處理結(jié)果傳輸至下一CTT 并觸發(fā)其執(zhí)行，如圖2 中的CTT1與CTT3所示。

圖2 多周期耦合下能量管理業(yè)務(wù)的處理時(shí)序邏輯鏈Fig.2 Time sequential logic chain of energy management business processing under multi-cycle coupling

CTT 的并列關(guān)系是指若干任務(wù)在被觸發(fā)后可同時(shí)進(jìn)行處理。并列任務(wù)組成的整體與其他CTT構(gòu)成承接關(guān)系，例如CTT3、CTT4、CTT5構(gòu)成并列關(guān)系并組成整體，與CTT2、CTT6構(gòu)成承接關(guān)系，利用變量yav刻畫時(shí)序邏輯鏈中各CTT 的數(shù)據(jù)傳輸方向，表達(dá)式為：

1.3.2 多周期耦合的跨終端業(yè)務(wù)計(jì)算負(fù)荷

在穩(wěn)態(tài)運(yùn)行時(shí)，任務(wù)處理呈周期性，圖2 中能量管理業(yè)務(wù)的一次觸發(fā)的周期為T0至T5，其中，T0為任務(wù)的開始時(shí)刻，T5為任務(wù)的結(jié)束時(shí)刻。由于CTT處理時(shí)的承接關(guān)系，在時(shí)刻t下，同一處理時(shí)序邏輯鏈中存在單個(gè)承接任務(wù)或多個(gè)并列任務(wù)處于處理狀態(tài)的情況。當(dāng)業(yè)務(wù)請(qǐng)求達(dá)到穩(wěn)態(tài)時(shí)，時(shí)刻t下會(huì)存在多個(gè)任務(wù)周期，如圖2 中的多周期耦合下的處理時(shí)序邏輯鏈。每臺(tái)ECT 為任務(wù)分配獨(dú)立的資源空間，同一ECT 內(nèi)的不同任務(wù)相互獨(dú)立。不同周期下的處理任務(wù)同時(shí)進(jìn)行，使每臺(tái)ECT 最多可同時(shí)運(yùn)行5 個(gè)處理周期中的同一個(gè)CTT。在如圖2 所示的CTT 的穩(wěn)態(tài)處理過(guò)程中，時(shí)刻t下能量管理業(yè)務(wù)產(chǎn)生的計(jì)算負(fù)荷l(t)表達(dá)式為：

式中：T為業(yè)務(wù)觸發(fā)的時(shí)間周期。

為滿足電力物聯(lián)網(wǎng)中海量設(shè)備與用戶的數(shù)據(jù)處理需求，單臺(tái)ECT 受限于計(jì)算容量和獲取數(shù)據(jù)數(shù)量，僅能處理所在區(qū)域內(nèi)的部分計(jì)算任務(wù)。而利用多ECT 的協(xié)同，可靈活調(diào)用各ECT 計(jì)算資源，處理較大范圍內(nèi)的計(jì)算任務(wù)。若能量管理業(yè)務(wù)中各子任務(wù)多周期并發(fā)處理，會(huì)使數(shù)據(jù)處理性能變差，在傳輸與計(jì)算過(guò)程中產(chǎn)生更多的處理延時(shí)。若按照一定的任務(wù)處理先后順序，根據(jù)不同處理周期內(nèi)CTT 計(jì)算負(fù)荷的差異調(diào)用系統(tǒng)可用的ECT 資源，可使資源利用更加合理，并獲得更優(yōu)的處理性能。

2 ECT 部署與任務(wù)分配優(yōu)化模型

在上述的邊緣計(jì)算架構(gòu)中，ECT 數(shù)量有限，其分布應(yīng)考慮使DP 可都處于ECT 的服務(wù)范圍內(nèi)。由于DP 處理數(shù)據(jù)、任務(wù)計(jì)算負(fù)荷的波動(dòng)性與差異性，以及ECT 部署與任務(wù)分配策略的不同，導(dǎo)致計(jì)算資源供需關(guān)系、任務(wù)處理服務(wù)質(zhì)量產(chǎn)生偏差。為解決ECT 分布式部署與任務(wù)耦合的計(jì)算資源供需平衡的適應(yīng)性問(wèn)題，本文提出ECT 部署與任務(wù)分配優(yōu)化的雙層模型，其中，上層模型求解任務(wù)在ECT 間的最優(yōu)分配，下層模型求解ECT 在NC 內(nèi)的最優(yōu)部署。

2.1 上層模型

在上層模型中，根據(jù)已知的ECT 部署結(jié)果，確定使總成本最小的任務(wù)分配方案，采用0-1 變量χae表 征 任 務(wù)a與ECTe間 對(duì) 應(yīng) 關(guān) 系，e∈{1，2，…，K}，其中K為系統(tǒng)ECT 的數(shù)量，表達(dá)式為：

1）目標(biāo)函數(shù)

任務(wù)處理需要占用計(jì)算資源和通信資源，并產(chǎn)生能耗。由于任務(wù)的計(jì)算負(fù)荷隨處理的數(shù)據(jù)量發(fā)生變化，導(dǎo)致數(shù)據(jù)處理與傳輸過(guò)程中占用的計(jì)算資源與通信資源發(fā)生變化。此外，利用能耗成本表征不同ECT 被占用不同數(shù)量的資源時(shí)產(chǎn)生的能耗。上層模型的目標(biāo)函數(shù)為：

式中：C（t）為在時(shí)刻t系統(tǒng)任務(wù)處理的總成本；e為ECT 的編號(hào)；(t)、(t)、(t)分別為ECTe處理任務(wù)時(shí)產(chǎn)生的計(jì)算、能耗和通信成本。

2）計(jì)算成本

在ECT 中，不同任務(wù)被放置于不同處理容器中，并根據(jù)任務(wù)屬性為每個(gè)容器分配一定數(shù)量的計(jì)算、通信資源，使在滿足STT 的延時(shí)約束條件下為CTT 提供更多的剩余資源。在實(shí)際應(yīng)用中，由于計(jì)算負(fù)荷隨數(shù)據(jù)的變化，計(jì)算成本的表達(dá)式為：

式中：dae(t)為ECTe處理任務(wù)a時(shí)所需的時(shí)間；fae(t)為ECTe分配給任務(wù)a所屬容器的計(jì)算資源；(t)為占用ECTe的單位計(jì)算資源所需的成本；Fe為ECTe的計(jì)算資源總量；∝為正比符號(hào)。式（9）為ECTe分配任務(wù)a時(shí)應(yīng)滿足的計(jì)算資源約束條件。

3）能耗成本

電力系統(tǒng)中ECT 數(shù)量及其運(yùn)行能耗巨大。在可持續(xù)發(fā)展與“雙碳”目標(biāo)下，減少處理設(shè)備產(chǎn)生的能耗至關(guān)重要。處理設(shè)備產(chǎn)生的能耗與其承擔(dān)的處理任務(wù)有關(guān)，即任務(wù)的不同分配導(dǎo)致設(shè)備的不同能耗［26-28］，ECT 協(xié)同過(guò)程中處理任務(wù)的合理分配，既有利于提高設(shè)備的資源利用率，又有利于減少能耗的產(chǎn)生。ECT 產(chǎn)生的能耗與當(dāng)前運(yùn)行的計(jì)算資源數(shù)量關(guān)系為：

式中：pe（t）為ECTe的能耗功率；αe、βe、θ為 能耗參數(shù)，且αe，βe＞0，θ∈[2.5，3.0]。

因此，能耗成本為：

由式（6）至式（12）可得，上層模型目標(biāo)函數(shù)的結(jié)果取決于通信成本及χae。當(dāng)下層模型確定最優(yōu)的通信方案時(shí)，通信成本隨之確定，故上層模型目標(biāo)函數(shù)的最小值等價(jià)于最優(yōu)的任務(wù)分配結(jié)果，即變量χae的全體取值。在任務(wù)分配過(guò)程中，在滿足約束條件下，任務(wù)間的分配相互獨(dú)立，其不同的分配結(jié)果導(dǎo)致ECT 的數(shù)據(jù)處理性能、數(shù)據(jù)傳輸延時(shí)等產(chǎn)生差異。

2.2 下層模型

1）目標(biāo)函數(shù)

ECT 是數(shù)據(jù)處理的主要設(shè)備，其部署會(huì)影響系統(tǒng)數(shù)據(jù)傳輸結(jié)構(gòu)、特性。為優(yōu)化數(shù)據(jù)流分布、減少通信資源的占用，建立下層模型的目標(biāo)函數(shù)為：

式中：C3（t）為總的通信成本。

2）通信延時(shí)

節(jié)點(diǎn)間的數(shù)據(jù)交互存在2 種方式：（1）垂直式架構(gòu)下DP 與ECT 間的通信；（2）水平式架構(gòu)下各ECT 間的數(shù)據(jù)交互。節(jié)點(diǎn)間的通信方式包括無(wú)線方式和有線方式。根據(jù)DP 所處位置采用的通信方式不同，例如：負(fù)荷開關(guān)采用低壓載波通信，充電樁采用遠(yuǎn)距離無(wú)線電（long range radio，LoRa）通信等。利用0-1 變量χie與χee'表征節(jié)點(diǎn)間的通信關(guān)系，數(shù)據(jù)傳輸延時(shí)為：

式中：die為時(shí)刻t第i個(gè)DP 與ECTe間傳輸數(shù)據(jù)量為uie(t)時(shí)產(chǎn)生的傳輸延時(shí)，其中，i∈[1，n]，n為系統(tǒng)DP 的數(shù)量；dee'(t)為時(shí)刻t在ECTe與ECTe'間傳輸數(shù)據(jù)量為uee'(t)時(shí)產(chǎn)生的傳輸延時(shí)；Rie，ee'(t)為時(shí)刻t利用香農(nóng)公式計(jì)算得到的第i個(gè)DP 與ECTe（或ECTe與ECTe'）間的信息傳輸速率；Bie，ee'為第i個(gè)DP與ECT（e或ECTe與ECTe）'間 的 帶 寬；Nie，ee'(t)為 時(shí)刻t在第i個(gè)DP 與ECTe（或ECTe與ECTe'）間的信噪比。

3）通信成本

參考國(guó)內(nèi)外相關(guān)運(yùn)營(yíng)商的通信資費(fèi)情況，采用流量方式對(duì)本文的通信成本進(jìn)行刻畫。通信流量以數(shù)據(jù)傳輸時(shí)占用的通信資源數(shù)量與使用時(shí)間的乘積進(jìn)行表征，則通信成本表征為單位數(shù)據(jù)傳輸成本與傳輸數(shù)據(jù)量的乘積，表達(dá)式為：

4）延時(shí)約束

配電物聯(lián)網(wǎng)中的各任務(wù)都具有處理延時(shí)容忍度，任務(wù)的服務(wù)延時(shí)主要分為數(shù)據(jù)上行與指令下行的傳輸延時(shí)和ECT 處理數(shù)據(jù)時(shí)產(chǎn)生的計(jì)算延時(shí)。針對(duì)垂直式架構(gòu)下的處理任務(wù)，其處理任務(wù)為STT，延時(shí)約束模型如式（20）所示。針對(duì)水平式架構(gòu)下的服務(wù)延時(shí)，由于CTT 在處理時(shí)序邏輯鏈的位置不同，導(dǎo)致ECT 間的數(shù)據(jù)傳輸方向不同，CTT 類任務(wù)的處理延時(shí)約束模型如式（21）所示，而如圖2所示的一個(gè)任務(wù)周期內(nèi)的能量管理業(yè)務(wù)的延時(shí)約束如式（22）所示。為處理時(shí)序邏輯鏈上各承接部分的延時(shí)與各并列部分延時(shí)的最大值之和不超過(guò)能量管理業(yè)務(wù)的延時(shí)容忍度。

式中：Tmax為能量管理業(yè)務(wù)的延時(shí)容忍度。

2.3 上、下層模型間的耦合關(guān)系

上層模型以優(yōu)化系統(tǒng)任務(wù)處理成本實(shí)現(xiàn)任務(wù)在ECT 間的分配，下層模型以優(yōu)化系統(tǒng)的信息流分布實(shí)現(xiàn)ECT 的最優(yōu)部署。由附錄B 第B1 章的決策變量分析，得到如圖3 所示的上、下層模型間的耦合關(guān)系，雙層模型的耦合作用過(guò)程如附錄B 第B2 章所述。

圖3 上、下層模型間的耦合關(guān)系Fig.3 Coupling relationship between upper and lower models

3 模型求解

3.1 模型假設(shè)與簡(jiǎn)化

3.1.1 模型假設(shè)

假設(shè)1：為保證數(shù)據(jù)處理的可靠性，NC 內(nèi)DP 數(shù)據(jù)量的變化可實(shí)時(shí)測(cè)得；DP 數(shù)據(jù)波動(dòng)滿足正態(tài)分布，且DP 之間相互獨(dú)立；DP 間的相對(duì)位置可知。

假設(shè)2：各任務(wù)的單位數(shù)據(jù)量的計(jì)算負(fù)荷可知；能量管理業(yè)務(wù)的處理時(shí)序邏輯可知。

假設(shè)3：ECT 內(nèi)部為容器分配計(jì)算資源的時(shí)間可忽略不計(jì)；容器的創(chuàng)建與銷毀可實(shí)時(shí)完成。

3.1.2 模型簡(jiǎn)化

在上述ECT 的部署過(guò)程中，考慮n個(gè)DP 請(qǐng)求的STT 產(chǎn)生的計(jì)算負(fù)荷，以及不同ECT 部署與任務(wù)分配策略下對(duì)計(jì)算、通信資源的占用等，使對(duì)決策變量χie的求解等價(jià)為一個(gè)非確定性多項(xiàng)式（nondeterministic polynomial，NP）難問(wèn)題，為雙層模型的求解帶來(lái)困難［29］。在實(shí)際ECT 部署中，考慮到DP的計(jì)算負(fù)荷變化存在波動(dòng)區(qū)間，且NC 內(nèi)的DP 數(shù)量差異易造成ECT 負(fù)載的不均衡，結(jié)合實(shí)際DP 的位置分布，提出在求解雙層模型前先確定K個(gè)NC 的劃分，ECT 的部署位置從每個(gè)NC 中選擇。

3.2 NC 劃分方法

邊緣的數(shù)據(jù)源節(jié)點(diǎn)依賴于邊緣計(jì)算終端的處理資源，故在采用K-means 法對(duì)節(jié)點(diǎn)進(jìn)行劃分時(shí)，考慮以邊緣計(jì)算終端的數(shù)量K為NC 劃分?jǐn)?shù)量。每個(gè)NC 內(nèi)的節(jié)點(diǎn)數(shù)量不同使ECT 的計(jì)算負(fù)荷、數(shù)據(jù)傳輸量產(chǎn)生較大差異，進(jìn)而影響ECT 的負(fù)載率及每個(gè)節(jié)點(diǎn)可利用的資源數(shù)量，從而導(dǎo)致節(jié)點(diǎn)的數(shù)據(jù)處理產(chǎn)生較大差異。所以，在利用K-Means 法進(jìn)行K個(gè)NC 劃分時(shí)，以每個(gè)NC 內(nèi)的節(jié)點(diǎn)數(shù)量均衡為劃分標(biāo)準(zhǔn)。為使各ECT 在處理STT 時(shí)的負(fù)載均衡，將系統(tǒng)n個(gè)DP 均分為K個(gè)NC，則ECTe管控的DP 數(shù)量ne為：

式中：I為ne計(jì)算結(jié)果的整數(shù)部分；M為ne計(jì)算結(jié)果的小數(shù)部分。當(dāng)M≠0 時(shí)，系統(tǒng)存在K(1-M)臺(tái)ECT 管控的節(jié)點(diǎn)數(shù)為I，KM臺(tái)ECT 管控的節(jié)點(diǎn)數(shù)為I+1。

根據(jù)組合理論，上述NC 約共有n!/(Kne！)種，此外，還需要計(jì)算每個(gè)NC 內(nèi)的各節(jié)點(diǎn)間的距離，計(jì)算量大。而對(duì)于K-means 法等節(jié)點(diǎn)聚類方法，在節(jié)點(diǎn)劃分過(guò)程中并未考慮每個(gè)NC 內(nèi)的DP 數(shù)量，會(huì)使ECT 的負(fù)載均衡度降低。為此，提出一種結(jié)合啟發(fā)式與K-means 法的NC 劃分方法，求解算法1 見(jiàn)附錄A 表A1，實(shí)現(xiàn)流程見(jiàn)附錄A 圖A1。

3.3 雙層模型求解算法

雙層模型求解適用方法分析見(jiàn)附錄B 第B3章［30-34］。不考慮垂直式架構(gòu)下任務(wù)分配的影響時(shí)，易證每個(gè)NC 內(nèi)存在唯一DP 使處理基本負(fù)荷時(shí)的通信延時(shí)最小。確定每個(gè)NC 內(nèi)的上述DP，將其作為ECT 部署的初始節(jié)點(diǎn)，計(jì)算此時(shí)的總成本，并將其設(shè)為初始邊界。雙層模型的求解流程見(jiàn)附錄A圖A2，基于隱枚舉法求解雙層模型的算法見(jiàn)附錄A表A2。本文采用隱枚舉法，其求解本質(zhì)與聯(lián)立求解的枚舉法相同，均是在所有可行解中尋找最優(yōu)解，只是在求解過(guò)程中，本文利用不同可行解的特征（可行解與ECT 部署節(jié)點(diǎn)的分布、承擔(dān)任務(wù)的數(shù)量相關(guān)），排除一些明顯使目標(biāo)函數(shù)遠(yuǎn)離最小值的可行解，即縮小每次的求解域。此外，在第4 章中，通過(guò)多次仿真實(shí)驗(yàn)，比較了隱枚舉法與方程組聯(lián)立求解的結(jié)果，兩者具有一致性，可知該最優(yōu)解為全局最優(yōu)解。

4 算例分析

4.1 參數(shù)設(shè)置

為探究不同節(jié)點(diǎn)的數(shù)據(jù)變化情況下，能量管理業(yè)務(wù)分解的各個(gè)子任務(wù)在不同ECT 間的分配，本文以如圖1 所示的某地區(qū)30 節(jié)點(diǎn)配電系統(tǒng)為例進(jìn)行仿真 分 析［20］，設(shè) 圖1 中 節(jié) 點(diǎn)1 至5 為 開 閉 所、節(jié) 點(diǎn)6 至12 為 負(fù) 荷 開 關(guān)、節(jié) 點(diǎn)13 至16 為 充 電 樁、節(jié) 點(diǎn)17 至21 為分支線開關(guān)、節(jié)點(diǎn)22 至24 為分布式電源、節(jié)點(diǎn)25 至30 為用戶分界開關(guān)。設(shè)系統(tǒng)配置6 個(gè)ECT，其參數(shù)見(jiàn)附錄A 表A3［35］，ECT 的單位計(jì)算、能耗及通信成本見(jiàn)表A4。DP 的STT 計(jì)算負(fù)荷變化曲線見(jiàn)圖A3（a）。能量管理業(yè)務(wù)分解的6 個(gè)CTT 的時(shí)序邏輯鏈如圖2 所示，各CTT 的計(jì)算負(fù)荷變化曲線見(jiàn)圖A3（b），系統(tǒng)請(qǐng)求能量管理任務(wù)的時(shí)間間隔為2 s。STT 與CTT 的相關(guān)參數(shù)見(jiàn)表A5。

4.2 NC 劃分

設(shè)DP 采集的數(shù)據(jù)量滿足［0.16，0.24］MB 間的正態(tài)分布，以各個(gè)DP 數(shù)據(jù)的均值作為NC 劃分時(shí)的權(quán)重。為得到較好的聚類結(jié)果，首先需選擇合適的節(jié)點(diǎn)作為初始聚類中心。初始聚類中心的選取與DP 的分布相關(guān)，計(jì)算各DP 與其他DP 的相對(duì)距離之和，確定節(jié)點(diǎn)9 與其他DP 的加權(quán)相對(duì)距離之和最小，選取與節(jié)點(diǎn)9 的加權(quán)距離最大的DP（節(jié)點(diǎn)21）作為第1 個(gè)初始聚類中心，并將距離D21及距離其最近的4 個(gè)DP（節(jié)點(diǎn)3、30、18、8）劃入同一NC 中。從剩余未被劃分至NC 中的DP 中選取距離節(jié)點(diǎn)9 最遠(yuǎn)的DP（節(jié)點(diǎn)29）作為另一初始聚類中心，并重復(fù)上述步驟直至形成初始6 個(gè)NC。聚類中心的確定路徑及最終的NC 劃分結(jié)果見(jiàn)附錄A 圖A4。

4.3 ECT 部署與任務(wù)分配

NC 內(nèi)每一個(gè)DP 均可作為ECT 的部署節(jié)點(diǎn)，且每臺(tái)ECT 部署彼此獨(dú)立，6 個(gè)CTT 可部署于任一臺(tái)ECT 上，故上述雙層模型的可行解個(gè)數(shù)為7.29×108。利用隱枚舉法設(shè)置的初始邊界中選取的ECT部署節(jié)點(diǎn)分別為：節(jié)點(diǎn)3、9、15、19、27、28。將上述DP 連接為閉合五邊形，見(jiàn)附錄A 圖A4，不考慮五邊形外的DP 作為ECT 的部署節(jié)點(diǎn)，此時(shí)排除可行解個(gè)數(shù)約為7.21×108。在上述ECT 部署方案下，計(jì)算各ECT 的剩余資源，在滿足任務(wù)處理延時(shí)約束下，排除能耗成本過(guò)高的任務(wù)分配方案，如將多個(gè)子任務(wù)分配在同一臺(tái)ECT 上，能耗成本的增加量大于通信成本的減小量，此時(shí)排除的可行解個(gè)數(shù)約為7.44×106，將ECT 部署單個(gè)CTT 設(shè)為邊界2。迭代求解出使處理成本最小的ECT 部署與任務(wù)分配方案，結(jié)果見(jiàn)表A6。根據(jù)上述ECT 部署與任務(wù)分配結(jié)果，各CTT 的處理延時(shí)如圖4 所示，各ECT 的計(jì)算資源利用率變化如圖5 所示，各成本如表A7所示。

圖4 各CTT 處理延時(shí)曲線Fig.4 Processing delay curves of each CTT

圖5 ECT 的計(jì)算資源利用率曲線Fig.5 Computing resource utilization rate curves of ECT

在不同ECT 部署與任務(wù)分配策略下，任務(wù)計(jì)算負(fù)荷的變化會(huì)對(duì)計(jì)算資源供需關(guān)系及業(yè)務(wù)服務(wù)質(zhì)量產(chǎn)生影響。附錄A 圖A5 為峰值負(fù)荷增加時(shí)各ECT的計(jì)算資源利用率變化情況。

4.4 結(jié)果分析

在NC 劃分過(guò)程中，合理的初始聚類中心的選取可有效減少聚類所需的迭代計(jì)算次數(shù)。在選取第3 個(gè)初始NC 時(shí)，選擇節(jié)點(diǎn)26 作為初始聚類中心，距離節(jié)點(diǎn)29 最近的4 個(gè)DP 中，節(jié)點(diǎn)18 已被劃分至第1個(gè)初始NC 中，因此利用剩余DP 中距離最近的節(jié)點(diǎn)2 代替節(jié)點(diǎn)18。在利用初始聚類中心形成的6 個(gè)初始NC 中，有4 個(gè)NC 與最終的NC 劃分結(jié)果一致，則其在第2、3 次計(jì)算后得到的密度中心相同。即利用上述方法最少可在3 次迭代計(jì)算后得到系統(tǒng)NC 劃分的結(jié)果。在DP 處理數(shù)據(jù)發(fā)生±20%的變化時(shí)，ECT 處理NC 內(nèi)DP 請(qǐng)求的STT 時(shí)負(fù)載的不均衡度小于9.4%。

上、下層模型可行解的個(gè)數(shù)分別為46 656 和15 625。若僅考慮垂直式架構(gòu)下的任務(wù)處理，則ECT 部署于NC 的密度中心將使處理成本最小。水平式架構(gòu)下，任務(wù)間的耦合關(guān)系使ECT 之間存在數(shù)據(jù)交互，即產(chǎn)生對(duì)通信資源的占用，導(dǎo)致ECT 的部署位置偏移NC 的密度中心，從而降低網(wǎng)絡(luò)傳輸延時(shí)。ECT 部署時(shí)設(shè)置的第1 個(gè)迭代邊界為上述的密度中心，使下層模型的可行解個(gè)數(shù)減少15 463 個(gè)；任務(wù)分配時(shí)，均勻分配可有效減少ECT 的能耗，排除將多個(gè)任務(wù)分配在同一ECT 上的可行解，進(jìn)一步將可行解的個(gè)數(shù)減少為原始可行解個(gè)數(shù)的0.016%。雙層模型優(yōu)化結(jié)果與邊界2 的任務(wù)分配與ECT 部署策略相比，總成本降低約16%，計(jì)算成本與通信成本分別降低約15.5%與26.6%。

典型的邊緣計(jì)算架構(gòu)為文獻(xiàn)［26，36］提出的垂直式架構(gòu)，其邊緣計(jì)算方法（記為方法1）與本文所用的計(jì)算方法在處理配電網(wǎng)業(yè)務(wù)時(shí)，各ECT 的資源利用率變化曲線如圖5 所示。由圖5 可知，本文所提的邊緣計(jì)算方法得到的資源利用率大于方法1 的資源利用率。相較于方法1，ECT 的資源利用率平均提高約30%，最大可提高約39%。在考慮系統(tǒng)配置10%的計(jì)算資源容量時(shí)，本文所提方法相較方法1而言，可短時(shí)承載的尖峰負(fù)荷提高約17%。區(qū)域邊緣計(jì)算終端可承載的負(fù)荷增加，為后續(xù)數(shù)據(jù)源節(jié)點(diǎn)負(fù)荷的增加提供足夠的消納能力，由此產(chǎn)生的效益隨之增加。此外，與隨機(jī)ECT 部署與任務(wù)分配策略相比，相同資源配置與處理任務(wù)下，任務(wù)處理開銷減少約35%，對(duì)計(jì)算資源的占用減少14%～16%。

5 結(jié)語(yǔ)

針對(duì)當(dāng)前配電網(wǎng)物聯(lián)網(wǎng)的ECT 部署與任務(wù)分配問(wèn)題，本文提出利用任務(wù)的耦合關(guān)系實(shí)現(xiàn)在穩(wěn)態(tài)運(yùn)行時(shí)的處理成本最低。任務(wù)的計(jì)算負(fù)荷模型、處理架構(gòu)是ECT 部署與任務(wù)分配的基礎(chǔ)，計(jì)算負(fù)荷模型實(shí)現(xiàn)對(duì)ECT 計(jì)算資源利用率、任務(wù)計(jì)算復(fù)雜度進(jìn)行定量表征。垂直式架構(gòu)下ECT 與DP 交互，任務(wù)處理方式單一，而水平式架構(gòu)下ECT 間相互協(xié)同，在兩者結(jié)合作用下，任務(wù)分配更具靈活性，同時(shí)減少云主站計(jì)算壓力，發(fā)揮多邊緣計(jì)算終端的協(xié)同效應(yīng)，降低任務(wù)處理開銷。ECT 部署應(yīng)關(guān)注穩(wěn)態(tài)時(shí)各ECT 的計(jì)算資源利用率，合理化信息流分布，優(yōu)化ECT 承擔(dān)的任務(wù)類型。任務(wù)分配應(yīng)關(guān)注ECT 的管控區(qū)域的計(jì)算負(fù)荷變化，確定各ECT 當(dāng)前可調(diào)用的計(jì)算資源數(shù)量，合理化任務(wù)分配，合理劃分ECT 的管控區(qū)域。

本文基于將計(jì)算負(fù)荷較大、跨終端處理的業(yè)務(wù)分解為若干子任務(wù)并將其分配至各臺(tái)ECT 的方法，適用于其他不同處理邏輯的業(yè)務(wù)類型。同時(shí)，本文從計(jì)算負(fù)荷的角度研究ECT 計(jì)算資源利用率，為后續(xù)不同類型和不同處理時(shí)序邏輯的任務(wù)卸載、資源動(dòng)態(tài)調(diào)度、信息流分布優(yōu)化等打下基礎(chǔ)。

附錄見(jiàn)本刊網(wǎng)絡(luò)版（http：//www.aeps-info.com/aeps/ch/index.aspx），掃英文摘要后二維碼可以閱讀網(wǎng)絡(luò)全文。