基于5G邊緣計(jì)算的智能電網(wǎng)高性價(jià)比任務(wù)調(diào)度

張少軍，金 燊，于 佳

(1.國(guó)網(wǎng)冀北電力有限公司信息通信分公司，北京100053；2.南瑞集團(tuán)有限公司，江蘇 南京 210003)

0 引言

智能電網(wǎng)中的電力數(shù)據(jù)信息量是巨大的、高度異構(gòu)的，如何有效地分析和處理這些數(shù)據(jù)是智能電網(wǎng)面臨的挑戰(zhàn)之一[1]。5G帶來(lái)的大帶寬、廣連接、低時(shí)延促進(jìn)了邊緣計(jì)算技術(shù)的進(jìn)一步發(fā)展，通過(guò)在智能電網(wǎng)中引入5G邊緣計(jì)算可以很好地解決上述問(wèn)題[2]。文獻(xiàn)[3]將邊緣計(jì)算引入智能電網(wǎng)，提出了智能電網(wǎng)中實(shí)時(shí)監(jiān)控服務(wù)的邊緣計(jì)算框架，并進(jìn)一步建立了最小化框架連接時(shí)延的邊緣調(diào)度策略問(wèn)題。文獻(xiàn)[4]提出了一種基于云-霧的智能電網(wǎng)資源管理模型，并且使用一些負(fù)載平衡策略來(lái)處理智能電網(wǎng)消費(fèi)需求；文獻(xiàn)[5]在智能電網(wǎng)中提出了一種使用霧節(jié)點(diǎn)來(lái)進(jìn)行數(shù)據(jù)處理的通信系統(tǒng)；文獻(xiàn)[6]提出了一個(gè)任務(wù)調(diào)度和資源管理策略，以最大限度地減少霧計(jì)算系統(tǒng)中的任務(wù)完成時(shí)間；文獻(xiàn)[7]提出了一種動(dòng)態(tài)計(jì)算卸載策略，以最小化帶有能量收集設(shè)備的貪婪移動(dòng)邊緣計(jì)算系統(tǒng)的執(zhí)行成本。在這些工作中，邊緣計(jì)算中的任務(wù)調(diào)度和資源管理問(wèn)題得到了很好的研究。然而，在智能電網(wǎng)環(huán)境中，針對(duì)在邊緣服務(wù)器上執(zhí)行任務(wù)的成本缺乏研究。因此，本文研究了智能電網(wǎng)場(chǎng)景下邊緣計(jì)算系統(tǒng)任務(wù)調(diào)度的成本，在完成任務(wù)需求的同時(shí)，最大限度地降低成本[8]。

1 系統(tǒng)模型

1.1 基于邊緣計(jì)算系統(tǒng)的智能電網(wǎng)通信網(wǎng)絡(luò)

智能電網(wǎng)通過(guò)集成先進(jìn)技術(shù)，為傳統(tǒng)電網(wǎng)增加信息流，打造自動(dòng)高效的能源傳輸網(wǎng)絡(luò)[9]。為了實(shí)現(xiàn)多路電力數(shù)據(jù)的實(shí)時(shí)采集和網(wǎng)絡(luò)的控制，智能電網(wǎng)部署了大量的物聯(lián)網(wǎng)設(shè)備，如傳感器、攝像機(jī)等[10]。它們可以收集不同類型的數(shù)據(jù)，是智能電網(wǎng)中信息流的來(lái)源。然而，由于資源和功能的限制，物聯(lián)網(wǎng)設(shè)備無(wú)法對(duì)數(shù)據(jù)進(jìn)行實(shí)時(shí)分析和處理，這需要智能電網(wǎng)通信網(wǎng)絡(luò)中強(qiáng)大的存儲(chǔ)和計(jì)算資源[11]?；谶吘売?jì)算系統(tǒng)的智能電網(wǎng)通信網(wǎng)絡(luò)系統(tǒng)模型如圖1所示。

圖1 系統(tǒng)模型Fig.1 System model

邊緣計(jì)算將服務(wù)器部署在靠近數(shù)據(jù)源的地方，以便在附近提供服務(wù)[12]。通常，邊緣計(jì)算系統(tǒng)由控制器和多個(gè)異構(gòu)邊緣服務(wù)器組成[13]?？刂破骶哂兴锌捎觅Y源的全局概述，并與每個(gè)部署的服務(wù)器通信[14]。每個(gè)服務(wù)器都可以運(yùn)行幾臺(tái)虛擬機(jī)來(lái)對(duì)智能電網(wǎng)網(wǎng)絡(luò)中物聯(lián)網(wǎng)設(shè)備卸載的數(shù)據(jù)進(jìn)行分析和處理。

對(duì)于從物聯(lián)網(wǎng)設(shè)備卸載的每個(gè)任務(wù)，控制器將根據(jù)其資源需求選擇可用的服務(wù)器進(jìn)行處理[15]。本文研究了任務(wù)調(diào)度，以盡量減少維護(hù)邊緣服務(wù)正常運(yùn)行的成本。

1.2 任務(wù)建模和優(yōu)化目標(biāo)

為了解決智能電網(wǎng)中的邊緣計(jì)算系統(tǒng)任務(wù)調(diào)度問(wèn)題，本文首先對(duì)物聯(lián)網(wǎng)設(shè)備和可用邊緣服務(wù)器上卸載的輸入任務(wù)進(jìn)行建模[16];然后，列出了任務(wù)調(diào)度問(wèn)題的資源約束，并提出了一個(gè)統(tǒng)一的優(yōu)化框架。

1.2.1 任務(wù)模型和服務(wù)器模型

在邊緣計(jì)算系統(tǒng)中，考慮一組延遲敏感任務(wù)T={t1,t2,…,tn}，其中n是輸入任務(wù)的總數(shù)。每個(gè)任務(wù)由ti={di,wi,δi,si}表示，其中di表示任務(wù)ti的傳輸數(shù)據(jù)大小,它包括由服務(wù)器計(jì)算的輸入數(shù)據(jù)和返回的輸出數(shù)據(jù),wi表示ti的計(jì)算工作量，δi表示任務(wù)ti的截止時(shí)間要求，si表示ti的存儲(chǔ)要求。

在邊緣計(jì)算系統(tǒng)中有m個(gè)異構(gòu)邊緣服務(wù)器E={e1,e2,…,em}，每個(gè)服務(wù)器由ej={Bj,Vj,Rj,Sj}表示，其中Bj表示執(zhí)行任務(wù)調(diào)度策略時(shí)服務(wù)器ej與控制器之間的可用通信帶寬。在每個(gè)服務(wù)器上部署一組VM，每個(gè)VM只能同時(shí)處理一個(gè)計(jì)算任務(wù)。設(shè)Vj是部署在服務(wù)器ej上VM 的數(shù)量，Sj表示服務(wù)器ej的可用存儲(chǔ)資源。用Rj表示服務(wù)器ej上VM的計(jì)算速率，每個(gè)VM的計(jì)算速率相等。當(dāng)系統(tǒng)進(jìn)行任務(wù)調(diào)度時(shí)，可以動(dòng)態(tài)調(diào)整每個(gè)VM所占用的帶寬[17]。

此外，將bij表示任務(wù)ti計(jì)劃到服務(wù)器ej進(jìn)行處理時(shí)的帶寬需求，Cj表示服務(wù)器ej處于開(kāi)啟狀態(tài)時(shí)的每秒成本。定義二進(jìn)制變量xij來(lái)表示任務(wù)ti是否被調(diào)度到服務(wù)器ej，當(dāng)任務(wù)ti被調(diào)度到服務(wù)器ej時(shí)，xij=1，否則xij=0。

由于邊緣計(jì)算系統(tǒng)計(jì)算能力足夠強(qiáng)，可以處理所有電網(wǎng)任務(wù)請(qǐng)求，而任務(wù)ti只能由一個(gè)服務(wù)器處理。

(1)

在任務(wù)調(diào)度過(guò)程中，服務(wù)器存儲(chǔ)空間溢出將丟失任務(wù)數(shù)據(jù)，而每個(gè)服務(wù)器的存儲(chǔ)能力受限。因此，服務(wù)器ej上所有任務(wù)的存儲(chǔ)需求要小于它的可用存儲(chǔ)資源：

(2)

由于部署在服務(wù)器上的VM有限，因此調(diào)度到服務(wù)器ej的任務(wù)數(shù)要小于它部署的VM數(shù)：

(3)

1.2.2 性能分析

由于智能電網(wǎng)的卸載任務(wù)時(shí)延受限，任務(wù)總時(shí)延包括：任務(wù)ti從控制器到服務(wù)器ej的輸入數(shù)據(jù)傳輸時(shí)間、任務(wù)計(jì)算時(shí)間以及輸出數(shù)據(jù)返回傳輸時(shí)間。

(4)

對(duì)于每一個(gè)任務(wù)ti調(diào)度到服務(wù)器ej處理時(shí)，這三部分時(shí)間用以下公式來(lái)計(jì)算：

(5)

(6)

(7)

(8)

代入式(4)，

(9)

如果任務(wù)ti被調(diào)度到服務(wù)器ej，通過(guò)求解式(9)可以得到：

(10)

為了減少邊緣計(jì)算系統(tǒng)成本，考慮所有任務(wù)在它們截止時(shí)間前準(zhǔn)確完成，那么在控制器和服務(wù)器間的任務(wù)ti所需的帶寬為：

(11)

調(diào)度到服務(wù)器ej上的任務(wù)總帶寬要小于它的可用通信帶寬：

(12)

1.2.3 成本最小化優(yōu)化問(wèn)題

在邊緣計(jì)算系統(tǒng)中，由于控制器與每個(gè)邊緣服務(wù)器通信，對(duì)于處于開(kāi)啟狀態(tài)的服務(wù)器，維持該服務(wù)器的正常運(yùn)行需要一定的成本[18]。例如，控制器需要消耗資源來(lái)管理正在運(yùn)行的服務(wù)器，而運(yùn)行狀態(tài)的服務(wù)器將消耗大量的能量。讓Cj表示邊緣計(jì)算系統(tǒng)在服務(wù)器ej處于開(kāi)啟狀態(tài)下的開(kāi)銷。本文將邊緣計(jì)算系統(tǒng)的成本定義為服務(wù)器開(kāi)啟狀態(tài)下的總成本。

下面用一個(gè)二進(jìn)制變量yj來(lái)表示服務(wù)器ej的狀態(tài)：

在本文基于邊緣計(jì)算系統(tǒng)的智能電網(wǎng)通信網(wǎng)絡(luò)中，控制器負(fù)責(zé)向不同的服務(wù)器調(diào)度任務(wù)。分配到任務(wù)的服務(wù)器即處于開(kāi)啟狀態(tài)，需要計(jì)算成本。本文任務(wù)調(diào)度策略的優(yōu)化目標(biāo)是最小化邊緣計(jì)算系統(tǒng)的成本[8]。 綜上所述，邊緣計(jì)算系統(tǒng)的成本最小化優(yōu)化問(wèn)題可以表述如下：

(13)

s.t.

(14)

(15)

(16)

(17)

2 算法設(shè)計(jì)

由于本文提出的成本優(yōu)化問(wèn)題是NP-hard的，因此不可能在多項(xiàng)式時(shí)間中得到最優(yōu)解[19]。本文提出一種基于貪心策略的啟發(fā)式任務(wù)調(diào)度算法來(lái)解決上述成本最優(yōu)問(wèn)題。算法包括兩個(gè)階段，在第一階段得到初步的任務(wù)調(diào)度策略，在第二階段優(yōu)化之前的策略并得到最終策略。本文所提具體算法分析如下：

任務(wù)調(diào)度到不同的服務(wù)器成本也不一樣，本文所設(shè)計(jì)的算法目的是最小化邊緣計(jì)算系統(tǒng)的成本，選擇單位成本uj最小的服務(wù)器，不失一般性，不同服務(wù)器的單位成本也不同。

(18)

式中，zj表示服務(wù)器ej的大?。?/p>

(19)

(20)

其中，

(21)

式中，pt*j表示調(diào)度到服務(wù)器ej的所有任務(wù)需要的資源。由于最后選擇的服務(wù)器將有大量可用資源，所以將單位成本最小的服務(wù)器任務(wù)調(diào)度到最終選定的服務(wù)器。本算法可以提高成本最高的服務(wù)器利用率，并且可以減少成本較小的服務(wù)器造成的不必要成本。

綜上所述，本文基于貪心策略的啟發(fā)式任務(wù)調(diào)度算法如算法1所示。

算法的輸入是需要進(jìn)行調(diào)度的任務(wù)集和可供選擇的邊緣服務(wù)器集。在第一行，首先初始化優(yōu)化問(wèn)題中的二進(jìn)制決策變量xij和yj。

在第一階段，當(dāng)單位成本等于根據(jù)式(18)和式(19)算出的值時(shí)，按照uj以及Cj從小到大的順序?qū)吘壏?wù)器進(jìn)行排序。從算法的第5～16步，根據(jù)服務(wù)器的資源需求和可用資源選擇服務(wù)器來(lái)處理計(jì)劃外的任務(wù)。在第6步，選擇可用服務(wù)器集E中有著最小單位成本的服務(wù)器ej。如果所選服務(wù)器的可用資源能夠滿足計(jì)劃外任務(wù)集T中某些任務(wù)的資源需求則選擇要放入服務(wù)器ej的最大任務(wù)(第7～14步)。否則，服務(wù)器ej從可用服務(wù)器集E中刪除(第15行)。最大的任務(wù)ti可以根據(jù)式(21)和式(22)在第8步上得到，然后將任務(wù)ti從計(jì)劃外的任務(wù)集刪除，并且將tij，yj設(shè)為1(第10～12步),然后將服務(wù)器ej添加到使用服務(wù)器集U中。

在第二階段，首先獲得U中成本最小的最后選擇的服務(wù)器eg1和eg2。如果服務(wù)器eg1中的可用資源能滿足服務(wù)器eg2中任務(wù)ti的資源需求i，重新將任務(wù)ti輸入服務(wù)器eg1并更新任務(wù)調(diào)度變量(第19～27步)。當(dāng)服務(wù)器eg2中的任務(wù)都被刪除時(shí)，它將從U中刪除并更新?tīng)顟B(tài)，然后從U獲得成本最小的新服務(wù)器(第22～25步)。

下面分析基于貪心策略的啟發(fā)式任務(wù)調(diào)度算法的時(shí)間復(fù)雜度。算法的第一階段包括兩部分：選擇服務(wù)器和向服務(wù)器調(diào)度任務(wù)。第一部分選擇服務(wù)器的時(shí)間復(fù)雜度至少為O(mlog(m))，第二部分有n個(gè)任務(wù)需要調(diào)度。考慮被選服務(wù)器滿足所有未調(diào)度任務(wù)資源需求的最差情況，算法需要n時(shí)間計(jì)算點(diǎn)積和選擇最大任務(wù)。在此情況下，第二部分至少花n2時(shí)間。因此算法第一階段的最差時(shí)間復(fù)雜度為O(mlog(m))+n2。第二階段在最差情況下將需要n-1時(shí)間。因此本文基于貪心策略的啟發(fā)式任務(wù)調(diào)度算法最差時(shí)間復(fù)雜度為O(mlog(m))+n2。

3 仿真分析

本節(jié)對(duì)求解成本優(yōu)化問(wèn)題的算法進(jìn)行性能評(píng)估，比較輸入任務(wù)數(shù)量、傳輸數(shù)據(jù)大小和延遲要求對(duì)所提算法成本的影響，經(jīng)過(guò)與能量感知資源調(diào)度策略(EARS)[20]和隨機(jī)調(diào)度策略(RANDOM)仿真結(jié)果對(duì)比，表明本文所提算法的有效性與性能改進(jìn)良好。本文算法在不同輸入任務(wù)數(shù)量下的性能比較如圖2所示。

圖2 不同輸入任務(wù)數(shù)量下算法的性能Fig.2 Performance of the algorithm under different input tasks

輸入任務(wù)的傳輸數(shù)據(jù)大小設(shè)置為50 MB，將輸入任務(wù)的數(shù)量由20更改為200，增量為20。將本文所提算法的性能與RANDOM算法和EARS算法進(jìn)行了比較，當(dāng)輸入任務(wù)數(shù)量增加時(shí)，邊緣計(jì)算系統(tǒng)的成本也隨之增加，原因是更多的服務(wù)器參與了任務(wù)卸載。如圖2所示，本文算法平均可以降低RANDOM算法50%的成本，原因是增加了每個(gè)使用服務(wù)器的資源利用率。在這種情況下，開(kāi)啟狀態(tài)下的服務(wù)器數(shù)量將減少。與EARS算法相比，隨著任務(wù)數(shù)量的增加，本算法與EARS算法之間的差距變小，最終趨于一致。輸入任務(wù)的不同傳輸數(shù)據(jù)大小對(duì)本文所提基于貪心策略的啟發(fā)式任務(wù)調(diào)度算法、EARS算法以及RANDOM算法性能的影響如圖3所示。

圖3 不同輸入任務(wù)傳輸數(shù)據(jù)量下算法的性能Fig.3 Performance of the algorithm for different input tasks

設(shè)置輸入任務(wù)數(shù)為150，傳輸任務(wù)數(shù)據(jù)量以5 MB的增量從15 MB增加到50 MB。結(jié)果表明，在本文所提算法下，傳輸任務(wù)數(shù)據(jù)量的增加，邊緣計(jì)算系統(tǒng)的成本也隨之增加。

但是在圖3中，任務(wù)傳輸數(shù)據(jù)量小于25 MB時(shí)，成本保持不變，其原因在于每個(gè)服務(wù)器上部署多個(gè)VM，此時(shí)任務(wù)傳輸數(shù)據(jù)量很小，服務(wù)器上的資源利用率(包括帶寬和存儲(chǔ)容量)不高。隨著任務(wù)傳輸數(shù)據(jù)量繼續(xù)增加，服務(wù)器資源利用率達(dá)到上限，需要增加服務(wù)器，成本也就增加了[8]。

此外，圖3中RANDOM算法成本維持穩(wěn)定，原因是RANDOM算法對(duì)任務(wù)處理時(shí)采用隨機(jī)調(diào)度的方式，并未充分利用服務(wù)器的資源。當(dāng)傳輸數(shù)據(jù)量增大時(shí)，服務(wù)器資源利用率提高了，但總成本保持不變。本文所提算法可以平均降低RANDOM算法30%的成本，降低EARS算法50%的成本。算法在不同的輸入任務(wù)延遲要求下的性能評(píng)估如圖4所示。

圖4 不同減少率下算法的性能Fig.4 Performance of the algorithm at different reduction rates

定義一個(gè)包括7個(gè)任務(wù)的任務(wù)集，其中任務(wù)的傳輸數(shù)據(jù)大小從20～50 MB不等，增量為5 MB。使用 15個(gè)任務(wù)集作為輸入任務(wù)，每個(gè)任務(wù)的延遲要求設(shè)置為γ/α，其中γ是初始延遲，α是減少率，將α從1改為2，增量為0.1，并繪制了3種算法得到的邊緣計(jì)算系統(tǒng)的成本。隨著減少率α的增加，所提算法和EARS算法獲得的成本將增加，RANDOM策略的成本基本沒(méi)有變化，這是因?yàn)檩^小的延遲意味著需要更大的傳輸帶寬，這導(dǎo)致需要更多的服務(wù)器來(lái)處理輸入任務(wù)。結(jié)果表明，本文基于貪心策略的啟發(fā)式任務(wù)調(diào)度算法平均可以降低RANDOM算法45%的成本，降低EARS算法40%的成本。

4 結(jié)論

本文探討了基于5G邊緣計(jì)算的智能電網(wǎng)任務(wù)調(diào)度的成本優(yōu)化問(wèn)題，首先提出了一個(gè)帶邊緣計(jì)算系統(tǒng)的智能電網(wǎng)通信網(wǎng)絡(luò)模型，接著在同時(shí)滿足所有輸入任務(wù)QoS要求下提出一個(gè)優(yōu)化問(wèn)題以最小化邊緣計(jì)算系統(tǒng)的成本，然后提出了一種基于貪心策略的啟發(fā)式任務(wù)調(diào)度算法用于求解成本優(yōu)化問(wèn)題。仿真結(jié)果表明，與RANDOM算法和EARS算法相比，所提算法在降低系統(tǒng)成本方面有所改進(jìn)。