王 星，于 炯，杜旭升，張姍姍，楊少智

(新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046)

0 引 言

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，延時(shí)敏感型應(yīng)用(如健康監(jiān)測(cè)、增強(qiáng)現(xiàn)實(shí)游戲等)量日益增長(zhǎng)[1]。由于IoT設(shè)備資源有限，可以將運(yùn)算量較大且復(fù)雜的任務(wù)卸載至遠(yuǎn)程服務(wù)器執(zhí)行。云計(jì)算是處理卸載任務(wù)的潛在方式。然而，由于距離云端較遠(yuǎn)，IoT設(shè)備發(fā)送大量任務(wù)至遠(yuǎn)程云端會(huì)導(dǎo)致較長(zhǎng)響應(yīng)時(shí)間和嚴(yán)重的網(wǎng)絡(luò)擁塞。為此，邊緣計(jì)算作為新計(jì)算模式應(yīng)運(yùn)而生[2,3]。邊緣計(jì)算在計(jì)算基礎(chǔ)設(shè)施上提供了一個(gè)附加層，由網(wǎng)絡(luò)邊緣的若干服務(wù)器構(gòu)成。對(duì)于來(lái)自IoT設(shè)備的卸載任務(wù)，邊緣計(jì)算可提供計(jì)算服務(wù)并返回結(jié)果。利用這種方式，卸載任務(wù)的傳輸延時(shí)和核心網(wǎng)絡(luò)上的負(fù)載可以得到有效降低，使得邊緣計(jì)算成為應(yīng)用的熱點(diǎn)。

邊緣計(jì)算中，任務(wù)調(diào)度是核心問(wèn)題[4]。為了降低任務(wù)計(jì)算能耗，IoT設(shè)備可卸載任務(wù)至邊緣服務(wù)器。然而，任務(wù)卸載會(huì)導(dǎo)致額外的傳輸能耗，并延長(zhǎng)卸載任務(wù)的完成時(shí)間。此時(shí)，必須研究IoT設(shè)備如何做出卸載決策。此外，當(dāng)計(jì)算任務(wù)調(diào)度至不同邊緣服務(wù)器時(shí)，傳輸和計(jì)算代價(jià)均有所不同。因此，如何設(shè)計(jì)有效的調(diào)度策略降低任務(wù)傳輸和計(jì)算所導(dǎo)致的系統(tǒng)代價(jià)也是調(diào)度問(wèn)題必須解決的難題。然而，有關(guān)邊緣服務(wù)器調(diào)度策略的相關(guān)研究中，考慮服務(wù)器代價(jià)優(yōu)化的策略目前相對(duì)較少，尤其是在非高峰時(shí)期的邊緣服務(wù)器代價(jià)優(yōu)化問(wèn)題少有研究。

本文將研究邊緣計(jì)算環(huán)境下任務(wù)調(diào)度的代價(jià)優(yōu)化問(wèn)題，目標(biāo)是最小化邊緣計(jì)算系統(tǒng)代價(jià)，并滿足任務(wù)QoS需求。提出一種針對(duì)延時(shí)敏感任務(wù)的調(diào)度模型，設(shè)計(jì)兩階段任務(wù)調(diào)度代價(jià)優(yōu)化算法TTSCO，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了算法的效率。

1 相關(guān)研究

邊緣計(jì)算環(huán)境中任務(wù)調(diào)度問(wèn)題已有一些研究成果。文獻(xiàn)[5]研究了移動(dòng)計(jì)算系統(tǒng)中雙國(guó)代價(jià)/延時(shí)均衡的任務(wù)調(diào)度問(wèn)題，所設(shè)計(jì)的調(diào)度算法可以最小化競(jìng)爭(zhēng)與協(xié)作場(chǎng)景下的系統(tǒng)代價(jià)。文獻(xiàn)[6]在移動(dòng)邊緣計(jì)算MEC系統(tǒng)中提出了一種動(dòng)態(tài)計(jì)算卸載策略以最小化執(zhí)行代價(jià)。文獻(xiàn)[7]提出了一種漸近式最優(yōu)卸載方法以最大化網(wǎng)絡(luò)利用率，并確保無(wú)線應(yīng)用的服務(wù)質(zhì)量。文獻(xiàn)[8]針對(duì)多用戶的MEC系統(tǒng)提出了一種在線聯(lián)合計(jì)算資源管理算法，可以有效降低任務(wù)調(diào)度中的長(zhǎng)期能量消耗。以上工作僅考慮的是用戶與邊緣云間的負(fù)載分布，而邊緣云中的任務(wù)調(diào)度問(wèn)題并沒(méi)有有效解決。

文獻(xiàn)[9]研究了大規(guī)模無(wú)線城域網(wǎng)絡(luò)WMAN中的多重朵云部署問(wèn)題，可以有效降低移動(dòng)端與朵云間的平均訪問(wèn)延時(shí)。文獻(xiàn)[10]在霧計(jì)算系統(tǒng)中設(shè)計(jì)了一種以最小化任務(wù)完成時(shí)間為目標(biāo)的任務(wù)調(diào)度與資源管理策略。文獻(xiàn)[11]提出了一種兩階段線性規(guī)劃算法處理霧計(jì)算中的代價(jià)優(yōu)化問(wèn)題。為了處理移動(dòng)用戶的峰值負(fù)載和云端資源的高效利用問(wèn)題，文獻(xiàn)[12]在邊緣云中提出了一種樹(shù)型結(jié)構(gòu)分布的服務(wù)器模型，并通過(guò)一種啟發(fā)式算法對(duì)任務(wù)負(fù)載進(jìn)行了有效調(diào)度。文獻(xiàn)[13]將代價(jià)優(yōu)化問(wèn)題形式化為馬爾可夫決策問(wèn)題MDP，并設(shè)計(jì)了一種最小化運(yùn)行代價(jià)的方法。為了滿足任務(wù)的服務(wù)質(zhì)量需求，文獻(xiàn)[14]在邊緣云中提出了一種周期性任務(wù)調(diào)度方法，可以使在邊緣云中的處理的任務(wù)量達(dá)到最大。以上工作中，雖然對(duì)邊緣云中的任務(wù)調(diào)度與資源管理問(wèn)題有所研究，但并沒(méi)有以降低邊緣服務(wù)器的利用代價(jià)為目標(biāo)考慮任務(wù)調(diào)度。

2 系統(tǒng)模型

2.1 邊緣計(jì)算體系

邊緣計(jì)算系統(tǒng)由一個(gè)邊緣計(jì)算代理ECA和若干異構(gòu)邊緣服務(wù)器構(gòu)成，如圖1所示。ECA擁有全部可用資源信息，并實(shí)現(xiàn)與每個(gè)部署服務(wù)器的通訊。每臺(tái)服務(wù)器可運(yùn)行若干虛擬機(jī)，可負(fù)責(zé)用戶卸載任務(wù)的執(zhí)行。通過(guò)將計(jì)算任務(wù)卸載至邊緣計(jì)算系統(tǒng)，可以使用戶獲得更好的體檢質(zhì)量(低延時(shí)、強(qiáng)大計(jì)算能力)。

圖1 邊緣計(jì)算模型

對(duì)于來(lái)自用戶的卸載計(jì)算任務(wù)，ECA將根據(jù)資源需求選擇合適的服務(wù)器進(jìn)行處理，即：ECA將周期性地執(zhí)行任務(wù)調(diào)度策略。令I(lǐng)為兩個(gè)連續(xù)任務(wù)調(diào)度過(guò)程的間隔時(shí)間，由于每組任務(wù)的完成時(shí)間不同，因此需要?jiǎng)討B(tài)的調(diào)整I的取值，將其定義為

I=tmd

(1)

其中，tmd為所有任務(wù)的期望完成時(shí)間的最大值。

2.2 問(wèn)題描述

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

令T={t1,t2,…,tn} 為邊緣計(jì)算系統(tǒng)中一組延時(shí)敏感型任務(wù)，n為任務(wù)數(shù)。將ti∈T定義為ti={di,wi,δi,si}，di為任務(wù)ti的數(shù)據(jù)傳輸量，wi為ti的任務(wù)執(zhí)行負(fù)載，δi為完成任務(wù)ti的截止時(shí)間，si為任務(wù)ti對(duì)系統(tǒng)的存儲(chǔ)需求。

令集合E={e1,e2,…,em} 為構(gòu)成邊緣計(jì)算系統(tǒng)的m臺(tái)異構(gòu)邊緣服務(wù)器。每臺(tái)服務(wù)器ej∈E定義為ej={Bj,Vj,Rj,Sj}， 其中，Bj為服務(wù)器ej與ECA間的通信帶寬，邊緣服務(wù)器的作用在于可以部署若干臺(tái)虛擬機(jī)VM，每臺(tái)虛擬機(jī)VM可用于執(zhí)行單一的計(jì)算任務(wù)。令Vj為部署在ej上的虛擬機(jī)數(shù)量，Sj為ej上的可用存儲(chǔ)資源量。ej上每臺(tái)虛擬機(jī)的計(jì)算速率是相同的，表示為Rj。當(dāng)發(fā)生任務(wù)調(diào)度時(shí)，每臺(tái)虛擬機(jī)占據(jù)的帶寬可以動(dòng)態(tài)調(diào)整。令bi,j為ti調(diào)度至ej上執(zhí)行時(shí)的帶寬需求，Cj為ej的接通代價(jià)。

以變量xij表示ti是否調(diào)度至ej上執(zhí)行，并以二進(jìn)制形式定義為

同時(shí)，約定一個(gè)服務(wù)器僅能處理一個(gè)任務(wù)，即

(2)

邊緣服務(wù)器的資源受限，必須滿足以下任務(wù)調(diào)度約束條件，即服務(wù)器必須具有足夠的存儲(chǔ)空間，否則會(huì)產(chǎn)生數(shù)據(jù)流失。因此，調(diào)度任務(wù)的總體存儲(chǔ)需求不能超過(guò)ej的存儲(chǔ)資源，即

(3)

此外，由于每臺(tái)服務(wù)器上部署的虛擬機(jī)數(shù)量有限，調(diào)度任務(wù)的總數(shù)也不能超過(guò)ej的虛擬機(jī)總數(shù)，即

(4)

(2)性能

卸載任務(wù)的完成時(shí)間由3個(gè)部分組成：任務(wù)的計(jì)算時(shí)間lij,com、 從ECA至ej的ti輸入數(shù)據(jù)的傳輸時(shí)間lij,in以及服務(wù)器至ECA的輸出數(shù)據(jù)傳輸時(shí)間lij,out， 因此約束為

xij(lij,com+lij,in+lij,out)≤δi

(5)

對(duì)于調(diào)度至服務(wù)器ej上的任務(wù)ti，以上的3個(gè)時(shí)間分別計(jì)算為

lij,com=wi/Rj

(6)

lij,in=di,in/bij,down

(7)

lij,out=di,out/bij,up

(8)

其中，di,in為ti的輸入數(shù)據(jù)量，di,out為ti的輸出數(shù)據(jù)量，bij,up和bij,down分別為ECA與邊緣服務(wù)器間的上行和下行帶寬。假設(shè)上行帶寬與下行帶寬相等，即

bij,*=bij,up=bij,down

(9)

因此，式(5)可變?yōu)?/p>

(10)

其中

di=di,in+di,out

若ti調(diào)度至ej，通過(guò)解式(10)可得到需求帶寬。帶寬需求不等式如下

(11)

在所有任務(wù)可在各自截止時(shí)間δi內(nèi)完成的前提條件下，需要盡可能降低邊緣計(jì)算系統(tǒng)代價(jià)。那么，ECA與ej間ti的需求帶寬可表示為

(12)

對(duì)于每臺(tái)服務(wù)器ej，調(diào)度至ej上任務(wù)的需求帶寬之和不能超過(guò)ej的總帶寬，即

(13)

(3)代價(jià)

邊緣計(jì)算系統(tǒng)中，由于ECA負(fù)責(zé)與每臺(tái)邊緣服務(wù)器通信，并管理服務(wù)器，每臺(tái)服務(wù)器通過(guò)ECA可以轉(zhuǎn)換為在線ON和離線OFF狀態(tài)。若服務(wù)器為ON狀態(tài)，維持服務(wù)器運(yùn)行則會(huì)生成相應(yīng)代價(jià)，如運(yùn)行服務(wù)器的能量消耗。令服務(wù)器ej在ON狀態(tài)時(shí)的系統(tǒng)代價(jià)為Cj，則總體代價(jià)為所有處理ON狀態(tài)的服務(wù)器代價(jià)之和。

令yj為標(biāo)識(shí)服務(wù)器ej狀態(tài)的二進(jìn)制變量，表示為

(4)最優(yōu)化問(wèn)題

邊緣計(jì)算系統(tǒng)中，邊緣計(jì)算代理的目標(biāo)是將卸載任務(wù)調(diào)度至邊緣服務(wù)器上執(zhí)行。若服務(wù)器已有分派任務(wù)，定義狀態(tài)為ON；若沒(méi)有分派任務(wù)，定義狀態(tài)為OFF。調(diào)度算法的目標(biāo)是使系統(tǒng)代價(jià)達(dá)到最小，形式化模型為

(14)

約束條件為

(15)

(16)

(17)

(18)

以下驗(yàn)證以上的代價(jià)優(yōu)化問(wèn)題為NP難問(wèn)題。

定理邊緣計(jì)算系統(tǒng)的代價(jià)優(yōu)化問(wèn)題為NP難問(wèn)題。

證明：將邊緣服務(wù)器ej上的資源表示為pej=(Sj,Vj,Bj)。 當(dāng)ti在服務(wù)器ej上執(zhí)行時(shí)，ti的資源需求可表示為ptij=(si,I,bij)。 考慮一種特殊情形，即所有服務(wù)器為同質(zhì)的。則ti的資源需求可重寫為pti=(si,I,bi)， 而服務(wù)器ej的資源可重寫為pe=(S,V,B)。 代價(jià)優(yōu)化問(wèn)題的目標(biāo)是最小化邊緣計(jì)算系統(tǒng)代價(jià)并確保所有任務(wù)的QoS需求。將每個(gè)任務(wù)視為一個(gè)物品，而每臺(tái)服務(wù)器為一個(gè)箱子。那么，目標(biāo)即為利用最小數(shù)量的箱子裝入所有物品。顯然，該問(wèn)題等同于三維矢量的裝箱問(wèn)題，為NP難問(wèn)題。證畢。

3 TTSCO算法設(shè)計(jì)

3.1 階段一

TTSCO算法首先選擇擁有最小單位代價(jià)uj的服務(wù)器執(zhí)行卸載任務(wù)，單位代價(jià)表示為式(19)。不失一般性，不同邊緣服務(wù)器的單位代價(jià)不同

uj=Cj/zj

(19)

其中，zj為服務(wù)器ej的大小，且

(20)

定義qej為任務(wù)調(diào)度至服務(wù)器后ej的剩余可用資源。根據(jù)裝箱問(wèn)題中的最佳適應(yīng)算法BF，對(duì)于在服務(wù)器ej上處理的卸載任務(wù)，ECA將選擇該服務(wù)器上的最大largest任務(wù)進(jìn)行處理。在TTSCO算法中，定義largest任務(wù)為具有最大標(biāo)量積hi的任務(wù)，而標(biāo)量積hi定義為

hi=qejptij=siS′j+V′j+bijB′j

(21)

其中

qej=(S′j,V′j,B′j)=pej-∑pe*j

(22)

其中，ptij為調(diào)度至服務(wù)器ej上任務(wù)的資源需求。

3.2 階段二

階段一之后，可以得到初步的任務(wù)調(diào)度策略。但在部分情形下，初步的調(diào)度策略得到的邊緣計(jì)算系統(tǒng)代價(jià)還可以進(jìn)一步降低。例如：現(xiàn)有兩個(gè)用戶任務(wù)，表示為A1、A2，兩臺(tái)邊緣服務(wù)器，表示為B1、B2。A1的資源需求為(10,10,10)，A2的資源需求為(20,20,20)。B1和B2的可用資源矢量分別為(15,15,15)和(50,50,50)。根據(jù)第一階段的調(diào)度策略，任務(wù)A1將被調(diào)度至B1，而A2被調(diào)度至B2。此時(shí)，總體代價(jià)為兩臺(tái)服務(wù)器的代價(jià)之和。然而，如果所有任務(wù)均調(diào)度至B2處理，總代價(jià)僅為服務(wù)器B2的代價(jià)。通過(guò)該策略，總代價(jià)可以進(jìn)一步降低。

根據(jù)以上案例，對(duì)于最終選擇的服務(wù)器，僅擁有較少資源量的服務(wù)器被利用。因此，第一階段調(diào)度后，需要進(jìn)一步優(yōu)化調(diào)度策略而降低不必要的代價(jià)。一般情形下，最后選擇的服務(wù)器擁有更多的可用資源量。在TTSCO算法中，將設(shè)計(jì)一種在最后選擇的服務(wù)器上最大化資源利用率的優(yōu)化策略，目標(biāo)是重新將最小代價(jià)服務(wù)器上的任務(wù)調(diào)度至第一階段中最后選擇的服務(wù)器上執(zhí)行。通過(guò)這種方式，TTSCO算法能夠以最大的代價(jià)提高服務(wù)器資源利用率，并以更小的代價(jià)降低服務(wù)器上的非必要代價(jià)。

綜合以上，TTSCO算法的執(zhí)行過(guò)程如算法1所示。算法輸入為待調(diào)度至邊緣服務(wù)器上的任務(wù)集合以及可用邊緣服務(wù)器集合。步驟(1)對(duì)二進(jìn)制決策變量xij和yj進(jìn)行初始化操作。

接下來(lái)，在第一階段中，需要以單位代價(jià)uj的非遞減方式對(duì)邊緣服務(wù)器進(jìn)行排列。若單位代價(jià)相同，則以Cj的非遞減方式進(jìn)行排列，即式(19)和式(20)。步驟(5)～步驟(15)的主要目標(biāo)是算法將根據(jù)任務(wù)對(duì)資源的需求以及當(dāng)前服務(wù)器的可用資源情況選擇相應(yīng)可執(zhí)行待調(diào)度任務(wù)的資源提供方。步驟(6)從集合E中選擇單位使用代價(jià)最小的服務(wù)器ej。步驟(7)～步驟(14)的目標(biāo)是先判斷是否所選服務(wù)器資源可以滿足集合T中的任務(wù)資源需求，若滿足，則選擇計(jì)算量最大的任務(wù)提交至服務(wù)器ej執(zhí)行；否則，將ej從服務(wù)器集合E中移除，即步驟(15)。步驟(8)中根據(jù)式(21)和式(22)獲得最大任務(wù)。然后，任務(wù)ti從待調(diào)度任務(wù)集合T中移除，并將tij和yj設(shè)置為1，即步驟(10)～步驟(12)。步驟(13)則將ej添加至已利用服務(wù)器集合U中。

第二階段中，首先獲取最后所選服務(wù)器eg1和集合U中擁有最小代價(jià)的服務(wù)器eg2。在步驟(19)～步驟(27)中，若eg1的可用資源可滿足eg2上任務(wù)ti的資源需求，則將ti重新調(diào)度至eg1，再更新決策變量。當(dāng)eg2上的任務(wù)均被移除時(shí)，可從U中移除服務(wù)器eg2，再更新eg2的狀態(tài)。然后，即可從U中得到代價(jià)最小的新服務(wù)器，即步驟(22)～步驟(25)所示。

算法1： TTSCO算法

Input: set of tasks to be scheduledT, set of available edge serversE

Output: task scheduling variable {xij}, the state of severs {yj}

(1)initialize all variablexijto be 0,setyj=0 for all servers

(2)stage1:

(3)obtain the vector pej and compute the unit costujof each serverej∈E

(4)set of severs that are usedU={}

(5)whileT≠NULLdo

(6) choose the serverejwith the smallest value of unit costujinE

(7)whilethere are tasks can be assigned into serverejdo

(8) compute the dot producthof all tasks can be assigned int serverej

(9) accommodate thattiwith the biggest value of dot product into serverej

(10)T←T(〗ti}

(11) setxij=1

(12) setyj=1

(13)U=U∪{ej}

(14)endwhile

(15)E←E(〗ej}

(16)endwhile

(17)stage2:

(18)obtain the last selected servereg1and servereg2with smallest cost inU

(19)whiletasktiineg2can be put into the servereg1do

(20) put tasktiinto servereg2

(21) setxig1=1

(22)ifthere is no task ineg2then

(23)U←U(〗eg2}

(24) setyg2=0

(25) obtain the new servereg2with smallest cost inU

(26)endif

(27)endwhile

TTSCO時(shí)間復(fù)雜度分析。TTSCO算法劃分為兩個(gè)階段：先對(duì)邊緣服務(wù)器進(jìn)行排列，然后將任務(wù)調(diào)度至邊緣服務(wù)器。首階段對(duì)服務(wù)器按服務(wù)性能進(jìn)行排列的時(shí)間復(fù)雜度為O(mlogm)。 次階段中，需要調(diào)度的任務(wù)數(shù)為n個(gè)，在最差的情況下，所選服務(wù)器可以滿足所有未調(diào)度任務(wù)的資源需求，則算法將進(jìn)行n次的標(biāo)量積計(jì)算，并選擇最大largest的任務(wù)。那么，該階段的時(shí)間代價(jià)至少為O(n2)。綜上，最差情況下TTSCO算法的時(shí)間復(fù)雜度為O(mlogm+n2)。

4 實(shí)驗(yàn)分析

本節(jié)在Matlab中構(gòu)建仿真實(shí)驗(yàn)驗(yàn)證TTSCO算法的性能。構(gòu)建兩種類型服務(wù)器組成的邊緣計(jì)算系統(tǒng)，并假設(shè)該系統(tǒng)擁有足夠的服務(wù)資源處理所有的任務(wù)需求。對(duì)于每個(gè)任務(wù)請(qǐng)求，其延時(shí)需求為di/α，α為[9,11]間的隨機(jī)分布量。為了實(shí)驗(yàn)結(jié)果的有效性，將不同的服務(wù)器配置不同的能力，包括：服務(wù)器配置虛擬機(jī)數(shù)、服務(wù)器的存儲(chǔ)能力和計(jì)算效率、虛擬機(jī)間的通信帶寬等。每臺(tái)服務(wù)器的利用代價(jià)與其服務(wù)能力成正比。對(duì)比算法選擇隨機(jī)調(diào)度策略RANDOM進(jìn)行對(duì)比。

4.1 對(duì)比研究

如圖2是TTSCO算法與LINGO軟件生成的理論最優(yōu)解的代價(jià)分布情況，可以看到，TTSCO生成的解與最優(yōu)解較為接近。

圖2 TTSCO算法與理論最優(yōu)解的分布

進(jìn)一步，若定義c1為TTSCO算法獲得的解，c2為L(zhǎng)INGO軟件得到的理論最優(yōu)解。令近似比c1/c2表示一種性能度量因子，如圖3是近似比的累積分布函數(shù)CDF。可以看到，近似比基本處于1～1.3之間，且95%的近似比取值小于1.2，驗(yàn)證TTSCO算法的求解準(zhǔn)確率還是較高的。同時(shí)，隨著輸入任務(wù)的增加，LINGO軟件將花費(fèi)更多時(shí)間(接近于一小時(shí))求解理論最優(yōu)解。而TTSCO算法在Matlab上運(yùn)行時(shí)間僅多花費(fèi)幾秒即可得到近似最優(yōu)解。此外，由于本文討論的邊緣計(jì)算系統(tǒng)代價(jià)的最優(yōu)化問(wèn)題是NP難問(wèn)題，即在多項(xiàng)式時(shí)間內(nèi)無(wú)法獲得最優(yōu)解，但TTSCO算法在多項(xiàng)式時(shí)間內(nèi)獲得的近似最優(yōu)解依然是有效準(zhǔn)確的。

圖3 近似率的CDF

4.2 參數(shù)影響分析

本節(jié)將分析相關(guān)參數(shù)配置對(duì)于TTSCO算法的影響，包括輸入任務(wù)數(shù)量、傳輸數(shù)據(jù)量以及任務(wù)的延時(shí)需求。

(1)任務(wù)量的影響

本部分評(píng)估不同輸入數(shù)據(jù)量對(duì)TTSCO算法的影響，輸入任務(wù)的傳輸數(shù)據(jù)量設(shè)置為50 MB，輸入任務(wù)量從30增加到150，步長(zhǎng)為30。結(jié)果如圖4所示。可以看到，若輸入任務(wù)量在增加，會(huì)導(dǎo)致系統(tǒng)代價(jià)增加，這是因?yàn)樾枰_(kāi)啟更多的服務(wù)器執(zhí)行卸載任務(wù)，進(jìn)而導(dǎo)致更大的代價(jià)。而TTSCO算法相比RANDOM算法平均可以降低約50%的代價(jià)，這是由于TTSCO算法可以大幅提升每臺(tái)邊緣服務(wù)器的資源利用率，即處于ON狀態(tài)的服務(wù)器數(shù)量會(huì)大幅減少。

圖4 輸入任務(wù)量的影響

(2)傳輸數(shù)據(jù)量的影響

設(shè)置任務(wù)量為150，輸入任務(wù)的數(shù)據(jù)傳輸量從25 MB增加至50 MB，步長(zhǎng)為5 MB。結(jié)果如圖5所示?？傮w來(lái)看，TTSCO算法得到的系統(tǒng)代價(jià)會(huì)隨著傳輸數(shù)據(jù)量的增加而增加。然而，當(dāng)傳輸數(shù)據(jù)量較小時(shí)(低于30 MB)，代價(jià)并不會(huì)隨著傳輸數(shù)據(jù)量的增加而增加，趨勢(shì)較為平緩，這是由于任務(wù)調(diào)度會(huì)受到虛擬機(jī)利用數(shù)量的限制，而服務(wù)器的帶寬和存儲(chǔ)資源利用也相對(duì)較低。當(dāng)增加任務(wù)傳輸數(shù)據(jù)量時(shí)，資源利用率雖有所增加，但總體代價(jià)并未變化，所以表現(xiàn)出在前期25 MB～35 MB的任務(wù)數(shù)據(jù)傳輸量時(shí)算法曲線基本是平緩直線形式。但進(jìn)一步增加數(shù)據(jù)傳輸量后，當(dāng)前服務(wù)器已無(wú)法滿足更大量的任務(wù)處理需求，更多的服務(wù)器將被開(kāi)啟使用。此時(shí)，系統(tǒng)代價(jià)也將隨著傳輸數(shù)據(jù)量的增加而增加。

圖5 任務(wù)傳輸數(shù)據(jù)量的影響

同時(shí)，根據(jù)圖5，RANDOM算法得到的代價(jià)曲線比較平滑，說(shuō)明代價(jià)值基本不隨輸入任務(wù)的數(shù)據(jù)傳輸量發(fā)生變化，這是由于RANDOM算法是以隨機(jī)方式選擇服務(wù)器執(zhí)行任務(wù)的，這樣會(huì)開(kāi)啟過(guò)多處于運(yùn)行狀態(tài)的服務(wù)器從而導(dǎo)致服務(wù)資源利用率較低。增加任務(wù)的傳輸數(shù)據(jù)量，資源利用率雖然會(huì)有所增加，但總代價(jià)不會(huì)出現(xiàn)大幅波動(dòng)。圖5的結(jié)果也表明TTSCO算法比較RANDOM算法可以平均降低約50%的代價(jià)。

(3)任務(wù)延時(shí)需求的影響

本部分定義任務(wù)集包括7個(gè)任務(wù)，任務(wù)的數(shù)據(jù)傳輸量以5 MB步長(zhǎng)從20 MB增加至50 MB，輸入任務(wù)量為15個(gè)任務(wù)集。每個(gè)任務(wù)的延時(shí)需求設(shè)置為δ/ρ，其中，δ為初始延時(shí)，ρ為下降率。以步長(zhǎng)0.2從1至2改變?chǔ)选D6是實(shí)驗(yàn)結(jié)果?？梢钥吹剑S著下降率ρ的增加，TTSCO算法的代價(jià)也將增加，而RANDOM算法的代價(jià)并沒(méi)有發(fā)生多大變化。這是由于較小的延時(shí)會(huì)要求更大的傳輸帶寬，在這種情況下需要開(kāi)啟更多的邊緣服務(wù)器來(lái)滿足任務(wù)處理的需求。而本文的TTSCO算法平均比RANDOM算法可以降低約45%的代價(jià)。

圖6 任務(wù)延時(shí)需求的影響

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

研究了邊緣計(jì)算環(huán)境中任務(wù)調(diào)度的代價(jià)優(yōu)化問(wèn)題，提出了一種兩階段調(diào)度算法。算法可以在滿足所有輸入任務(wù)的QoS需求的同時(shí)，使邊緣計(jì)算系統(tǒng)的任務(wù)調(diào)度代價(jià)達(dá)到最小。將算法的調(diào)度結(jié)果與LINGO軟件下得到的理論最優(yōu)解結(jié)果進(jìn)行了比較，驗(yàn)證算法可以以多項(xiàng)式時(shí)間得到較為接近于最優(yōu)解的調(diào)度方案，而相比對(duì)比算法可以有效降低邊緣計(jì)算系統(tǒng)的代價(jià)。進(jìn)一步的研究方向可以考慮研究在多重邊緣服務(wù)器環(huán)境下的動(dòng)態(tài)資源管理和任務(wù)調(diào)度決策問(wèn)題。