趙 輝，馮南之，王 泉，萬 波，王 靜

(1.西安電子科技大學 計算機科學與技術(shù)學院，陜西 西安 710071；2.陜西省智能人機交互與可穿戴技術(shù)重點實驗室，陜西 西安 710071)

近年來，在云計算的發(fā)展與普及基礎(chǔ)之上，由于邊緣計算將處理過程先放在邊緣計算節(jié)點完成，然后將處理結(jié)果傳給云端，可以大大提升處理效率，減輕云端的負荷，因此，邊緣計算廣泛應(yīng)用于具有實時性、安全與隱私保護等需求的領(lǐng)域，如物聯(lián)網(wǎng)、智慧交通、智慧城市等。

邊緣計算，尤其是移動邊緣計算，在能效方面存在很大挑戰(zhàn)。針對該挑戰(zhàn)，許多研究嘗試通過合理的任務(wù)調(diào)度策略來盡可能地利用系統(tǒng)資源、降低功耗。一般地，任務(wù)調(diào)度模式可分為線上或線下調(diào)度[1-4]。前者是指所有任務(wù)只有在被執(zhí)行后才能得到它們的處理時間；后者則是處理器的速度和作業(yè)長度提前已知。然而實際應(yīng)用中，由于網(wǎng)絡(luò)路由不穩(wěn)定、隱私保護等條件限制，人們通常只能獲取邊緣計算平臺中部分節(jié)點的性能，存在部分節(jié)點性能未知的情況。此時，線上或線下的調(diào)度算法就無法有效地感知系統(tǒng)資源，可能導致任務(wù)執(zhí)行時間或傳輸時間過長，不但降低效率，還會使邊緣計算平臺高能耗的問題更加突出。

當邊緣計算平臺中存在部分已知性能節(jié)點和部分未知性能節(jié)點時，這樣的任務(wù)調(diào)度方法稱為半線上任務(wù)調(diào)度方法。半線上任務(wù)調(diào)度模型可以看作是很多實際系統(tǒng)的抽象，例如對于單個本地設(shè)備來說，自身的多個CPU核可被看作已知性能的計算節(jié)點，而遠端或是云端的服務(wù)器可以被視為是未知性能的計算節(jié)點；在涉及隱私保護的云存儲中，未知性能節(jié)點可以是用來加密重要數(shù)據(jù)的私有云；在云計算中，未知性能節(jié)點可以是彈性云服務(wù)器或者共享虛擬機。但是，目前有關(guān)半線上任務(wù)調(diào)度的研究很少，甚至對半線上也沒有統(tǒng)一的定義。文獻[5]考慮了半在線調(diào)度時服務(wù)器之間通信時間，根據(jù)通信延遲與遠程處理器的速度之間的大小關(guān)系分別設(shè)計了兩種算法，但是討論的情景是只有一臺本地處理器和一臺未知遠程處理器，并且通信延遲和處理速度的關(guān)系在現(xiàn)實各種情況下很難是固定的。文獻[6]還考慮將任務(wù)分配給m+m′個處理器來最小化完成時間，m是指已知速度的處理單元，m′是指未知速度的處理單元，當任務(wù)的處理時間為長尾分布時該文章提出的方法有顯著的效果，但是該方法沒有考慮任務(wù)在處理器之間的路由延遲，且存在再分配開銷，沒有充分利用到系統(tǒng)資源。文獻[7]提出了用于多用戶卸載的高效半在線算法，該算法分兩種情況，分別對應(yīng)已知服務(wù)器空閑時間和已知任務(wù)完成時間。文獻[8]總結(jié)了半線上調(diào)度實際上是在線上調(diào)度算法的基礎(chǔ)上添加了額外的已知條件，在不同工作中這個已知額外信息可以是最大作業(yè)大小、作業(yè)到達順序或是執(zhí)行總時間。在文獻[9]的工作中這一額外信息指的是任務(wù)執(zhí)行的總時間已知。在文中，這一額外信息是指任務(wù)長度已知，以及只有部分計算節(jié)點的處理速度和任務(wù)分配到該節(jié)點時的路由延遲已知。在這種條件下，需要研究如何有效地調(diào)度任務(wù)來優(yōu)化系統(tǒng)的能耗。

因此，以能耗優(yōu)化為目標，筆者提出了一種面向邊緣計算平臺的半線上任務(wù)動態(tài)調(diào)度方法。首先，邊緣計算平臺的能耗主要由3部分構(gòu)成：任務(wù)被執(zhí)行時的功耗、任務(wù)在路由傳輸時的功耗以及計算節(jié)點空閑時的能耗。半線上任務(wù)調(diào)度場景下，由于路由延遲的不確定性，可能導致數(shù)據(jù)傳輸時間過長，不僅消耗較多的傳輸能耗，還會降低整個系統(tǒng)的運行效率，從而加重能源開銷。以往的研究很少考慮因路由延遲導致的任務(wù)傳輸能耗，而在邊緣計算平臺中，由路由延遲導致的能耗不可忽略。從邊緣節(jié)點的處理速度、路由延遲和隊列長度三個角度，引入邊緣節(jié)點的任務(wù)執(zhí)行能耗、任務(wù)傳輸能耗和空閑能耗，建立了能耗優(yōu)化的邊緣計算平臺任務(wù)調(diào)度模型。該模型既能更客觀地反映邊緣計算平臺的實際能耗，也是下一步任務(wù)調(diào)度算法的基礎(chǔ)。其次，提出了一種基于動態(tài)映射的半線上任務(wù)調(diào)度算法。該算法分為兩個步驟：① 假定未知節(jié)點的性能等于某個已知節(jié)點的性能，建立未知-已知節(jié)點之間的映射，再不斷感知映射雙方的任務(wù)隊列長度來動態(tài)調(diào)整映射關(guān)系。其原理是對于性能相近的兩個節(jié)點，調(diào)度算法大體上會分配類似的任務(wù)量，若一段時間后，它們的任務(wù)隊列差異過大，則說明這兩個節(jié)點的映射關(guān)系不合理，需要進行重新映射和調(diào)整；② 在未知-已知節(jié)點映射基礎(chǔ)上，有效利用系統(tǒng)中已知節(jié)點性能這一先驗知識，利用改進的Power-of-two，或稱Power-of-D算法[10]來完成任務(wù)調(diào)度。針對每一個任務(wù)，根據(jù)節(jié)點處理速度、路由延遲和隊列長度，考慮節(jié)點的執(zhí)行、傳輸、空閑能耗來選擇處理節(jié)點，從而降低整個邊緣計算系統(tǒng)的能耗。最后，在CloudSim實驗平臺中對比了筆者所提方法和其他的任務(wù)調(diào)度方法，結(jié)果表明所提出的方法在能耗優(yōu)化上優(yōu)于其他算法。筆者的主要貢獻如下：

(1)針對存在部分已知性能和部分未知性能節(jié)點的邊緣計算平臺任務(wù)調(diào)度的高能耗問題，首次提出了一種面向邊緣計算平臺的半線上任務(wù)動態(tài)調(diào)度方法。

(2)針對邊緣計算平臺中任務(wù)傳輸路由延遲導致的能耗問題，考慮邊緣計算節(jié)點的處理速度、路由延遲等，分別計算邊緣計算節(jié)點的任務(wù)執(zhí)行能耗、任務(wù)傳輸能耗和空閑能耗，從而建立更加細致的邊緣計算平臺任務(wù)調(diào)度能耗優(yōu)化模型；

(3)通過動態(tài)感知未知-已知節(jié)點的任務(wù)隊列長度，建立未知-已知節(jié)點之間的動態(tài)映射關(guān)系，充分利用已有先驗知識，提出了一種基于動態(tài)映射的半線上任務(wù)調(diào)度算法，實現(xiàn)能耗優(yōu)化的半線上任務(wù)調(diào)度算法。

1 建立能耗模型

文中的任務(wù)調(diào)度算法以最小化系統(tǒng)能耗為目標。每個任務(wù)是獨立且非搶占式的，分別從它們的執(zhí)行時間、路由延遲和排隊時間出發(fā)，研究對系統(tǒng)能耗的影響，建立能耗優(yōu)化的任務(wù)調(diào)度模型。

對于節(jié)點k∈K，用kr表示它的隊列容量，kv表示處理速度；對于任務(wù)m∈M，用mr，ml分別表示它占用的隊列資源和數(shù)據(jù)長度。因此，當任務(wù)生成并在t時刻被分配給k時，需要滿足

(1)

(2)

使用pmk表示m在k上的處理時間，pmk=ml/kv。任務(wù)被分配時需要經(jīng)歷路由傳輸?shù)难舆temk=umk+u′mk。等式后面分別代表了m路由到節(jié)點k被處理和m從節(jié)點k路由到目的地之間的延遲。將節(jié)點資源量kr、處理速度kv和任務(wù)到它的延遲emk三者統(tǒng)稱為節(jié)點的性能。

(3)

其中，

(4)

因為整個系統(tǒng)是并行工作的，所以系統(tǒng)的總工作時長等于節(jié)點中工作時長最大的，即

TG=max(Tk)，k∈K。

(5)

(6)

因此，邊緣計算平臺總系統(tǒng)能耗為

(7)

最終，得到邊緣平臺能耗優(yōu)化目標為

(8)

2 任務(wù)調(diào)度算法

并行處理器中的任務(wù)調(diào)度問題已被證明是NP難[11]的，很難在多項式時間內(nèi)求出最優(yōu)解，更何況當系統(tǒng)中出現(xiàn)未知性能的計算節(jié)點時，無論是在線算法還是離線算法都無法有效利用已知部分節(jié)點性能這一先驗知識，導致資源利用率不高。筆者提出一種半線上任務(wù)調(diào)度算法，來求解該實時調(diào)度問題。首先，采用一種動態(tài)映射思想，根據(jù)已知節(jié)點性能這一先驗知識來想辦法確定未知節(jié)點的性能，實現(xiàn)未知-已知節(jié)點的映射；其次，在動態(tài)映射基礎(chǔ)上，充分利用系統(tǒng)已知先驗知識，提出一種基于動態(tài)映射的半線上任務(wù)調(diào)度算法。

2.1 未知節(jié)點性能映射

在任務(wù)開始被分配之前，需要根據(jù)已知的節(jié)點性能這一先驗知識來確定未知節(jié)點的性能。文中采用了一種映射思想，具體做法是通過將未知節(jié)點的性能映射為已知的節(jié)點；這里的性能不僅僅指的是計算節(jié)點的處理速度kv和隊列容量kr，還包括路由延遲emk，?m∈M。

維護一個未知節(jié)點到已知節(jié)點的映射表B，并且感知節(jié)點任務(wù)隊列不斷動態(tài)調(diào)整映射的節(jié)點。映射表的元素bij表示將節(jié)點i映射為節(jié)點j。初始化時，先將已知節(jié)點集K+按照處理速度kv的升序排列，然后讓未知節(jié)點映射到K+的中位元素，該中位元素記為z；之后執(zhí)行任務(wù)調(diào)度算法，在基于概率的分配下，理論上所有的未知節(jié)點和所映射的節(jié)點應(yīng)當被分配幾乎相同數(shù)量的任務(wù)。如果一段時間后發(fā)現(xiàn)任務(wù)隊列長度差異明顯，則根據(jù)不同情況調(diào)整映射表。具體來說，如果未知節(jié)點的任務(wù)隊列長于所映射的已知節(jié)點上的任務(wù)隊列，說明對其性能期待過高，需將該未知節(jié)點映射為更低性能的已知節(jié)點，反之亦然。該動態(tài)映射過程如圖1所示。

圖1 動態(tài)映射表工作原理

在實際應(yīng)用中，影響映射雙方的任務(wù)隊列可能受到延遲等不穩(wěn)定因素的影響，需要式(9)來抵消可能存在的誤差，增加算法魯棒性，即

(9)

其中，ε是閾值參數(shù)，如果映射雙方任務(wù)隊列長度之差沒有超過某個閾值則不會更新映射關(guān)系。

通過這樣的動態(tài)映射，不同性能的未知節(jié)點會被映射到一個較為合理的已知節(jié)點，于是就能夠?qū)崿F(xiàn)利用已知性能這一先驗知識去推測未知性能，高效利用系統(tǒng)的計算資源調(diào)度任務(wù)。具體偽代碼如算法1所示。

算法1未知節(jié)點映射算法。

輸入：mapping tableB。

輸出：updated mapping tableB。

① ∥Initializing

② if first time running then

③ SortK+in the ascending order ofkv；

④ Let all elements inBequal to 0；

⑤z=u/2；

⑥ for alliinvdo

⑦biz=1；

⑨ end for

⑩ end if

2.2 任務(wù)調(diào)度

在經(jīng)過算法1動態(tài)映射后，當調(diào)度算法遇到未知節(jié)點時，就能通過查詢映射表找到它所映射的已知節(jié)點，接下來用到的所有節(jié)點性能數(shù)據(jù)都參考該已知節(jié)點。Power-of-D算法的原理是先讓任務(wù)隨機選d(d通常等于2)個處理單元，再選擇其中隊列最短的那個，這種隨機性讓Power-of-D算法在實際應(yīng)用表現(xiàn)良好。除了考慮計算節(jié)點存在任務(wù)隊列長度外，還需要考慮其處理速度和路由延遲。

首先，用k′v來重新定義節(jié)點的處理速度，它表示在邊緣節(jié)點受到路由延遲的影響后的處理速度：

(10)

根據(jù)每個節(jié)點的k′v計算并歸一化，得到選中概率，即

(11)

這樣那些低延遲、高速度的節(jié)點就會有更高的概率被選中。當任務(wù)m在t時刻生成后，按照概率F(k)選取d個節(jié)點，這些處理節(jié)點用集合D表示，最終m會被分配給其中一個節(jié)點并滿足：

(12)

其中，α，β，γ是3個權(quán)重參數(shù)且β為負數(shù)，即m要在候選的d個節(jié)點中進一步選擇隊列短、速度快、延遲低的節(jié)點。以上3步既考慮了節(jié)點的速度和延遲，又考慮了任務(wù)隊列的長度，對應(yīng)于第1節(jié)功耗模型中的3項參數(shù)。其偽代碼如算法2所示。因為算法中有任務(wù)在所有節(jié)點上求k′v的步驟，因此算法復(fù)雜度為O(mn)，m、n分別為任務(wù)和節(jié)點總數(shù)。

3 實驗及結(jié)果分析

文中面向的是半線上邊緣計算環(huán)境，但實際在大型的邊緣計算網(wǎng)絡(luò)中進行可重復(fù)任務(wù)調(diào)度實驗是非常困難的。因此，采用云仿真平臺CloudSim[12]對算法的性能進行評估，該平臺能夠?qū)υ朴嬎阆到y(tǒng)和應(yīng)用程序供應(yīng)環(huán)境進行建模和仿真，支持云計算的資源管理和調(diào)度模擬，同時提供了多種可擴展接口。通過擴展部分模塊將云計算模擬轉(zhuǎn)變?yōu)閷吘売嬎隳M。

算法2半線上動態(tài)調(diào)度策略。

輸入：task m，mapping tableB。

① for allkinKdo

② ifki∈K-

③ Findjthatbij==1；

⑤ end if

⑧ end for

⑨ for allkinKdo

3.1 實驗環(huán)境與設(shè)置

因為現(xiàn)有的線上、線下和半在線方法并不完全適用于文中所討論的場景(即存在若干已知和未知的性能節(jié)點，伴有不斷變化的路由延遲)。文中選擇一些通用的任務(wù)調(diào)度方法與提出的方法進行性能對比：

半線上動態(tài)調(diào)度策略(DSS)：即文中所采用的任務(wù)調(diào)度策略。

貪心算法(Greedy)：每個任務(wù)都分配給當前任務(wù)隊列最短的節(jié)點。

Power-of-D[10]算法(PoD)：隨機挑選D個節(jié)點，之后從這些節(jié)點中再選一個任務(wù)隊列最短的節(jié)點，將任務(wù)分配給它?？梢钥吹絇oD和Greedy是在某些地方比較相似，但由于文中討論的情景中存在路由延遲，當延遲波動較大時，PoD的隨機性可以為它帶來一定的優(yōu)勢。

輪循算法(RR)：任務(wù)依次順序地被分配給所有的節(jié)點，是CloudSim的默認調(diào)度算法。

由于Greedy和PoD本身無法適用于半線上情景，所以在其中也添加了靜態(tài)映射表來處理未知節(jié)點。實驗設(shè)置了共16個邊緣節(jié)點，它們按照處理速度(單位MIPS)被分為4組：250，350，450，550；每組4個節(jié)點，包括3個已知節(jié)點和1個未知節(jié)點；未知節(jié)點的性能在實驗中對算法是隱藏的，但真實性能如表1的12，13，14，15所示。

表1 邊緣節(jié)點的處理速度分布

實驗過程中CloudSim每經(jīng)過一段時間會采集各邊緣節(jié)點的CPU利用率，根據(jù)利用率計算出這段時間的能耗，最后將所有時間段的功耗累加就得到了整個邊緣計算平臺的能耗。表2為不同CPU利用率下處理節(jié)點的能耗，具體數(shù)值設(shè)置參照了HP ProLiant ML110 G4的能耗模型。

表2 邊緣節(jié)點的不同負載情況下的能耗

在任務(wù)設(shè)置方面，基于高斯分布分別生成了6 000、12 000、18 000、24 000、30 000、36 000，42 000，48 000條不同長度的任務(wù)，接著采用分批到達來實現(xiàn)持續(xù)的調(diào)度，每一批設(shè)定為300個任務(wù)。

3.2 結(jié)果分析

由于實驗過程中有許多隨機變量，如不斷變化的路由延遲、算法的隨機調(diào)度等，為了盡量減少誤差，需要將實驗中每個算法都重復(fù)執(zhí)行數(shù)次再取結(jié)果的平均值。不同算法的調(diào)度結(jié)果如圖2和圖3所示。圖2為不同調(diào)度算法的執(zhí)行時長結(jié)果，圖3為不同的調(diào)度算法的系統(tǒng)能耗結(jié)果。從圖中均可以明顯地看出，文中所提算法在所有數(shù)據(jù)規(guī)模下表現(xiàn)都是最佳的，在所有任務(wù)規(guī)模下都優(yōu)于其他算法，顯著降低了邊緣計算平臺的能耗。這是因為文中算法在基于PoD算法隨機性優(yōu)勢的同時，考慮了邊緣節(jié)點的處理速度、路由延遲、任務(wù)隊列的長度，并且結(jié)合了動態(tài)映射的思想，建立未知-已知節(jié)點的動態(tài)映射，能夠充分地利用未知節(jié)點的資源。PoD算法的結(jié)果是第二好的，略微優(yōu)于Greedy算法。這是因為文中所設(shè)定的情景還包含任務(wù)到節(jié)點的路由延遲，盡管這兩個算法都沒有考慮路由延遲，但PoD算法因為具備隨機性，當任務(wù)量足夠且延遲較為波動時能夠在一定程度上緩解這方面的缺點。RR算法只是簡單的將任務(wù)一個個輪詢分配在節(jié)點上，并沒有進行任何的優(yōu)化，所以其消耗的能耗也就最多。

圖2 各方法的任務(wù)完成時間對比

圖3 各方法能耗對比

圖4和圖5分別顯示了對PoD和Greedy算法添加動態(tài)映射機制后性能提升的對比。從中可以看出，通過維護一個動態(tài)的映射表，合理假設(shè)出未知節(jié)點的性能后，兩種算法的性能都得到了提升。這是因為在系統(tǒng)中存在未知節(jié)點，由此導致路由延遲不可忽略，在這種情況下，如何有效利用節(jié)點的資源，對于實現(xiàn)高效的任務(wù)調(diào)度是十分關(guān)鍵的。這也體現(xiàn)了筆者提出的動態(tài)映射思想在半線上情景中的有效性。

圖4 使用動態(tài)映射后各方法的任務(wù)完成時間對比

圖5 使用動態(tài)映射后各方法能耗對比

4 結(jié)束語

以能耗優(yōu)化為目標，筆者提出了一種面向邊緣計算平臺半線上任務(wù)動態(tài)調(diào)度方法。首先，建立面向邊緣計算平臺的任務(wù)調(diào)度模型，該模型將總能耗劃分為處理、傳輸和空閑三段能耗進行建模，更加細致地表示邊緣計算平臺的能耗；其次，對建立的任務(wù)調(diào)度優(yōu)化模型，提出了基于動態(tài)映射的任務(wù)調(diào)度算法。對于系統(tǒng)中的未知節(jié)點，通過動態(tài)映射算法將其性能假設(shè)為某個已知節(jié)點，從而形成已知-未知節(jié)點之間的映射關(guān)系，之后不斷感知映射雙方的任務(wù)隊列長度來動態(tài)調(diào)整映射關(guān)系，從而充分利用已有先驗知識，提出了一種基于動態(tài)映射的半線上任務(wù)調(diào)度算法；最后，在CloudSim平臺完成對比試驗，結(jié)果表明文中所提方法能夠有效利用系統(tǒng)的資源，有助于降低邊緣計算平臺的能耗。