面向邊緣計(jì)算平臺(tái)的半線上任務(wù)動(dòng)態(tài)調(diào)度方法

趙 輝，馮南之，王 泉，萬(wàn) 波，王 靜

(1.西安電子科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710071；2.陜西省智能人機(jī)交互與可穿戴技術(shù)重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071)

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

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

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

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

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

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

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

1 建立能耗模型

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

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

(1)

(2)

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

(3)

其中，

(4)

因?yàn)檎麄€(gè)系統(tǒng)是并行工作的，所以系統(tǒng)的總工作時(shí)長(zhǎng)等于節(jié)點(diǎn)中工作時(shí)長(zhǎng)最大的，即

TG=max(Tk)，k∈K。

(5)

(6)

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

(7)

最終，得到邊緣平臺(tái)能耗優(yōu)化目標(biāo)為

(8)

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

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

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

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

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

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

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

(9)

其中，ε是閾值參數(shù)，如果映射雙方任務(wù)隊(duì)列長(zhǎng)度之差沒(méi)有超過(guò)某個(gè)閾值則不會(huì)更新映射關(guān)系。

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

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

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

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

(10)

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

(11)

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

(12)

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

輸入：task m，mapping tableB。

① for allkinKdo

② ifki∈K-

③ Findjthatbij==1；

⑤ end if

⑧ end for

⑨ for allkinKdo

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

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

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

貪心算法(Greedy)：每個(gè)任務(wù)都分配給當(dāng)前任務(wù)隊(duì)列最短的節(jié)點(diǎn)。

Power-of-D[10]算法(PoD)：隨機(jī)挑選D個(gè)節(jié)點(diǎn)，之后從這些節(jié)點(diǎn)中再選一個(gè)任務(wù)隊(duì)列最短的節(jié)點(diǎn)，將任務(wù)分配給它。可以看到PoD和Greedy是在某些地方比較相似，但由于文中討論的情景中存在路由延遲，當(dāng)延遲波動(dòng)較大時(shí)，PoD的隨機(jī)性可以為它帶來(lái)一定的優(yōu)勢(shì)。

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

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

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

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

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

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

3.2 結(jié)果分析

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

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

圖3 各方法能耗對(duì)比

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

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

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

4 結(jié)束語(yǔ)

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