高素林，張盈希，任奕菲，馮光升

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150001)

0 引言

隨著互聯(lián)網(wǎng)和智能設(shè)備的普及，人們享受著網(wǎng)絡(luò)和智能設(shè)備帶來的便捷。同時(shí)智能設(shè)備上的應(yīng)用程序?qū)τ谟?jì)算資源的需求越來越高,云計(jì)算的出現(xiàn)解決了計(jì)算資源受限的問題，卻未能提供低延遲的服務(wù)[1-2]。隨著移動邊緣計(jì)算的興起，智能設(shè)備將資源密集型任務(wù)遷移到移動邊緣計(jì)算(Mobile Edge Computing,MEC)服務(wù)器上執(zhí)行以緩解自身資源受限問題并獲得低延遲的高質(zhì)量服務(wù)。邊緣計(jì)算從最初的薄云計(jì)算[3]演變到如今的MEC，不斷地靠近用戶，建立MEC服務(wù)器[4]為用戶提供高質(zhì)量服務(wù)。所以MEC有著邊緣部署、臨近用戶、低時(shí)延和高帶寬[5]等特點(diǎn)。據(jù)調(diào)查研究，預(yù)計(jì)到2030年全球的智能設(shè)備數(shù)量將達(dá)到180億[6]。MEC服務(wù)器的計(jì)算資源相對于如此龐大數(shù)量的智能設(shè)備也變得相對有限，如何對大量的任務(wù)進(jìn)行有效調(diào)度變得十分重要。

對于調(diào)度問題，早期的研究對于時(shí)延和能量的消耗考慮較少，大多是將龐大的計(jì)算任務(wù)調(diào)度到MEC服務(wù)器中執(zhí)行[7]，計(jì)算資源利用率和調(diào)度的效率都比較低，導(dǎo)致服務(wù)質(zhì)量較差。在近期的研究中，多用戶場景、智能設(shè)備和服務(wù)器計(jì)算資源相對有限、任務(wù)時(shí)延要求較高等問題得到更多的關(guān)注。研究者們將任務(wù)分割[8]，考慮任務(wù)優(yōu)先級、資源分配、功率調(diào)整等因素，提高了任務(wù)調(diào)度的效率和MEC服務(wù)器計(jì)算資源的利用率[9-11]。任務(wù)調(diào)度問題相關(guān)研究的主要目的是為了降低任務(wù)時(shí)延和提高服務(wù)器計(jì)算資源利用率，通過提高服務(wù)器資源利用率可將更多的任務(wù)調(diào)度到服務(wù)器上執(zhí)行，從而降低智能設(shè)備的能量消耗[12-13]。

Liu等人[14]研究了在多用戶場景中以任務(wù)優(yōu)先級和空間限制為約束，以服務(wù)器資源利用率為優(yōu)化目標(biāo)的任務(wù)調(diào)度問題，提出了一種任務(wù)卸載調(diào)度器——Horae，Horae有效提高了資源利用率并且降低了所有任務(wù)的時(shí)延，但服務(wù)器和智能設(shè)備可能因此消耗更多的能量。Liu等人[15]以降低平均執(zhí)行時(shí)延為優(yōu)化目標(biāo)使用馬爾科夫決策過程來解決任務(wù)調(diào)度問題，該研究以任務(wù)調(diào)度系統(tǒng)的功率為約束提出了一種一維搜索算法來找到最佳任務(wù)調(diào)度策略，但時(shí)延較長的任務(wù)可能不會被調(diào)度到服務(wù)器中執(zhí)行，造成智能設(shè)備消耗更多的能量。Tseng等人[16]在網(wǎng)關(guān)處建立了邊緣計(jì)算節(jié)點(diǎn)，實(shí)行按需分配的資源分配策略減少了傳輸延遲的同時(shí)提供高性能服務(wù)，探究了如何部署邊緣計(jì)算服務(wù)器以及如何將用戶智能設(shè)備上的任務(wù)調(diào)度到服務(wù)器上執(zhí)行從而提高服務(wù)質(zhì)量，對于如何部署MEC服務(wù)器并完成任務(wù)調(diào)度有很大的借鑒意義，但是對于用戶智能設(shè)備的能量消耗問題考慮得不足。Chen等人[17]研究了混合能量供應(yīng)的異構(gòu)MEC中的任務(wù)調(diào)度和能量管理，聯(lián)合優(yōu)化任務(wù)調(diào)度和能量管理以最大程度提高M(jìn)EC服務(wù)器的資源利用率，文中還提出了在線任務(wù)調(diào)度和服務(wù)器能量管理算法，該算法能得到近似最大化的MEC服務(wù)器資源利用率，但更多的關(guān)注在于MEC系統(tǒng)集成了能量收集模塊后對能量的管理。Yan等人[18]研究了在不確定運(yùn)行時(shí)間和不穩(wěn)定通信條件下的節(jié)能任務(wù)調(diào)度問題，將β分布的通信速率和不確定運(yùn)行時(shí)間下的任務(wù)調(diào)度問題轉(zhuǎn)換為一個整數(shù)規(guī)劃問題并建立模型，這個模型的優(yōu)化目標(biāo)為最小化服務(wù)器能量消耗，最后提出EASE啟發(fā)式算法來解決任務(wù)調(diào)度問題。Saleem等人[19]解決了MEC中基于移動感知的任務(wù)調(diào)度和資源分配問題，提出了一個移動感知任務(wù)調(diào)度算法，并使用遺傳算法和移動感知任務(wù)調(diào)度算法來解決任務(wù)調(diào)度問題，文中更多關(guān)注智能設(shè)備的移動性，而對用戶智能設(shè)備的能量消耗考慮不足。

本文對多用戶場景下的任務(wù)調(diào)度問題進(jìn)行研究，以時(shí)延和任務(wù)依賴性為約束條件，以智能設(shè)備最小化能量消耗為優(yōu)化目標(biāo)建立了優(yōu)化模型，通過對優(yōu)化模型進(jìn)行求解得到調(diào)度策略。仿真實(shí)驗(yàn)結(jié)果表明算法在滿足時(shí)延和任務(wù)依賴性約束的同時(shí)，有效對智能設(shè)備上的任務(wù)進(jìn)行調(diào)度。算法充分利用了MEC服務(wù)器計(jì)算資源,同時(shí)更大程度地降低了智能設(shè)備整體的能量消耗，有效緩解了智能設(shè)備能量受限問題，提高了服務(wù)質(zhì)量。

1 系統(tǒng)與計(jì)算模型

1.1 系統(tǒng)模型

假設(shè)有m個智能設(shè)備，用集合M={1,2,3,…,M}表示。每個智能設(shè)備會生成n個任務(wù)，用集合N={1,2,3,…,N}表示。這n個任務(wù)之間存在依賴性約束，即先生成的任務(wù)需先運(yùn)行結(jié)束，后續(xù)的任務(wù)才能開始運(yùn)行。并且每個任務(wù)均有時(shí)延要求，任務(wù)必須在特定時(shí)間內(nèi)完成才不會影響整體任務(wù)的運(yùn)行和用戶體驗(yàn)。對于任務(wù)密集型任務(wù)往往需要大量的計(jì)算資源(CPU計(jì)算頻率、內(nèi)存和電池容量)，而由于智能設(shè)備的計(jì)算資源有限，所以需要將一部分任務(wù)密集型任務(wù)遷移到MEC服務(wù)器上運(yùn)行。

假設(shè)有一臺MEC服務(wù)器，它的CPU頻率為fc，其他計(jì)算資源(內(nèi)存、電池容量)可視為無限大。智能設(shè)備通過網(wǎng)絡(luò)與MEC服務(wù)器建立連接后可將任務(wù)遷移到MEC服務(wù)器上運(yùn)行，而MEC服務(wù)器相較于大量的來自智能設(shè)備的任務(wù)，它的CPU計(jì)算頻率也相對有限。所以MEC服務(wù)器需要對這些任務(wù)進(jìn)行調(diào)度，即決定這些任務(wù)是否能遷移到MEC服務(wù)上運(yùn)行、何時(shí)運(yùn)行。

1.2 計(jì)算模型

1.2.1 本地計(jì)算模型

任務(wù)在本地執(zhí)行的時(shí)間消耗為：

任務(wù)在本地執(zhí)行的能量消耗為：

1.2.2 服務(wù)器計(jì)算模型

因?yàn)橐昅EC服務(wù)器的能量是無限的，所以任務(wù)在MEC服務(wù)器上的能量消耗不計(jì)，只考慮任務(wù)執(zhí)行的時(shí)間消耗。此時(shí)間消耗為：

1.2.3 數(shù)據(jù)傳輸模型

任務(wù)在傳輸過程中的時(shí)間消耗為：

任務(wù)在傳輸過程中的能量消耗為：

2 能量消耗模型與任務(wù)調(diào)度問題

2.1 任務(wù)的時(shí)延約束

2.2 任務(wù)的依賴性約束

2.3 能量消耗模型

任務(wù)調(diào)度的最小單位為單個任務(wù)，所以對于任一任務(wù)只有被調(diào)度和不被調(diào)度兩種結(jié)果。任務(wù)被調(diào)度則遷移到MEC服務(wù)器上執(zhí)行，反之則在智能設(shè)備上執(zhí)行。任務(wù)的調(diào)度結(jié)果用am,n∈{0,1}表示，am,n=1表示任務(wù)被調(diào)度，反之則表示不被調(diào)度。如果任務(wù)被調(diào)度到MEC服務(wù)器執(zhí)行，能量消耗為數(shù)據(jù)傳輸產(chǎn)生的能量消耗。如果任務(wù)不被調(diào)度到MEC服務(wù)器執(zhí)行，能量消耗為本地計(jì)算產(chǎn)生的能量消耗。設(shè)Em,n表示智能設(shè)備m的任務(wù)n的能量消耗，則任一任務(wù)的能量消耗可以表示為：

設(shè)所有連接到任務(wù)調(diào)度系統(tǒng)的智能設(shè)備的整體能量消耗為E，則E可以表示為：

2.4 任務(wù)調(diào)度問題

在任務(wù)調(diào)度問題中需要確定哪個任務(wù)可以被調(diào)度到MEC服務(wù)器中執(zhí)行，任務(wù)能否被調(diào)度到MEC服務(wù)器中執(zhí)行取決于時(shí)延約束和任務(wù)依賴性約束，此外還需考慮智能設(shè)備的能量消耗問題。所以多用戶場景下的任務(wù)調(diào)度問題可以轉(zhuǎn)換為一個以任務(wù)時(shí)延和依賴性為約束條件，以最小化整體能量消耗為目標(biāo)函數(shù)的優(yōu)化問題：

s.t.?m∈M,?n∈N,

C3:am,n∈{0,1},

式中,A表示所有任務(wù)的調(diào)度決策，A={am,n|m∈M,n∈N}。約束C1是時(shí)間延遲約束,約束C2是任務(wù)依賴性約束,約束C3是對調(diào)度決策的約束。

3 問題求解與算法設(shè)計(jì)

因?yàn)橹悄茉O(shè)備持續(xù)生成任務(wù)并持續(xù)遷移到MEC服務(wù)器上執(zhí)行，而任務(wù)具有時(shí)延約束需要盡快得到合理的調(diào)度。所以很難得到一個較長時(shí)間段內(nèi)智能設(shè)備整體的能量消耗最小值，只能將較長的時(shí)間段分割成若干個較小的時(shí)間段，以較小時(shí)間段內(nèi)的能量消耗最小值累積得到較長時(shí)間段內(nèi)的近似能量消耗最小值。

3.1 優(yōu)化問題求解

將較長的時(shí)間段分割至極小，即每當(dāng)有任務(wù)遷移請求達(dá)到MEC服務(wù)器就對該任務(wù)進(jìn)行一次調(diào)度。因?yàn)檫w移到MEC服務(wù)器上執(zhí)行的任務(wù)較多，所以會有一部分任務(wù)在MEC服務(wù)器中等待被執(zhí)行。當(dāng)新任務(wù)到達(dá)時(shí)對新任務(wù)和等待執(zhí)行的任務(wù)進(jìn)行調(diào)度操作(可能改變執(zhí)行的順序或之前的調(diào)度決策)。設(shè)總共進(jìn)行Y次調(diào)度，每次調(diào)度后產(chǎn)生的能量消耗為ΔEy。

假設(shè)，新到達(dá)的任務(wù)來自智能設(shè)備m上的任務(wù)n。如果新任務(wù)不被調(diào)度，則ΔEy等于在智能設(shè)備上執(zhí)行產(chǎn)生的能量消耗，可表示為：

如果新任務(wù)被調(diào)度且等待執(zhí)行的任務(wù)調(diào)度決策沒有被改變，則ΔEy等于在MEC服務(wù)執(zhí)行所產(chǎn)生的能量消耗，可表示為：

如果新任務(wù)替換了之前被調(diào)度的任務(wù)，則ΔEy等于新任務(wù)在MEC服務(wù)器上執(zhí)行產(chǎn)生的能量消耗加上被替換的任務(wù)回到智能設(shè)備執(zhí)行產(chǎn)生的能量消耗，設(shè)被替換的任務(wù)來自智能設(shè)備i上的任務(wù)j，則表示為：

所有連接到MEC服務(wù)器的智能設(shè)備的整體能量消耗可看作所有操作產(chǎn)生的ΔEy之和，可表示為：

因此OP1可以放縮為：

針對每個任務(wù)的調(diào)度問題可以表示為：

s.t.?m∈M,?n∈N,

C3:am,n∈{0,1}。

3.2 實(shí)時(shí)調(diào)度算法

該問題中每次只對一個新到的任務(wù)進(jìn)行調(diào)度，復(fù)雜度相對較低。因?yàn)榈却龍?zhí)行的任務(wù)都是被調(diào)度過的，所以它們的相對順序不會被改變。新到的任務(wù)只能被插入到隊(duì)伍列(隊(duì)列中間或隊(duì)列末尾)或替換其中某個等待執(zhí)行的任務(wù)。而等待執(zhí)行的隊(duì)列中只有隊(duì)尾的一部分任務(wù)可以被替換或被“插隊(duì)”，因?yàn)殛?duì)伍前的任務(wù)即將被執(zhí)行或有極大的可能性被再次調(diào)度后不滿足時(shí)延要求，因此找到可行解并找到最優(yōu)解的復(fù)雜度并不高，可以將新到的任務(wù)從隊(duì)列末尾依次往前“插隊(duì)”找出所有可行解，并在可行解中選擇最優(yōu)解后完成調(diào)度。為了充分利用時(shí)間資源，如果存在多個相同的最優(yōu)解，則選擇靠近隊(duì)列頭部的調(diào)度方式。

實(shí)時(shí)調(diào)度算法可表示為：對于新到的任務(wù)x和等待隊(duì)列K。

① 將x放置到隊(duì)列末尾，檢查x的約束條件是否滿足，若滿足則記錄下該可行解；

② 針對隊(duì)列中的任務(wù)k從隊(duì)列尾部至隊(duì)列頭部依次向前重復(fù)步驟③和步驟④，直至步驟③和步驟④均未得到可行解；

③ 嘗試將x插入到k之前，如果x和k及k以后的所有任務(wù)均滿足時(shí)延約束和依賴性約束，則記錄該可行解；

④ 嘗試將x替換k，如果x和k及k以后的所有任務(wù)均滿足時(shí)延約束和依賴性約束，則記錄下該可行解；

⑤ 如果有可行解則選擇其中的最優(yōu)解，如果存在多個最優(yōu)解則選擇最后獲得的最優(yōu)解，如果不存在可行解則新到的任務(wù)x不被調(diào)度。

3.3 遺傳算法

因此OP1可以放縮為所有較小時(shí)間段內(nèi)的最優(yōu)解之和：

因此較小時(shí)間段內(nèi)的調(diào)度問題可以表示為：

s.t.?m∈Mx,?n∈Nx,

C3:am,n∈{0,1}。

對于調(diào)度策略Ax，Ax={am,n|m∈Mx,n∈Nx}，Ax是一串由0或1組成的二進(jìn)制編碼，將此編碼作為遺傳算法的基因編碼，使用對應(yīng)調(diào)度策略的能量消耗的倒數(shù)作為個體的適應(yīng)值，即可使用遺傳算法對該問題進(jìn)行求解。

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

仿真實(shí)驗(yàn)?zāi)M了20臺智能設(shè)備與一臺MEC服務(wù)器。智能設(shè)備以一定的速率和概率生成任務(wù)，這些任務(wù)的工作量、時(shí)延要求是不一樣的，但是在合理的范圍內(nèi)。為了更逼真地模擬真實(shí)場景，實(shí)驗(yàn)中存在許多隨機(jī)因素(任務(wù)生成的概率、任務(wù)工作量和任務(wù)時(shí)延要求)，所以每次實(shí)驗(yàn)是唯一的、不可重復(fù)的，因此同時(shí)使用遺傳算法和實(shí)時(shí)調(diào)度算法分別進(jìn)行調(diào)度以對比兩種算法的性能。實(shí)驗(yàn)中各參數(shù)設(shè)置如表1所示，參數(shù)設(shè)置參考文獻(xiàn)[9]。

表1 實(shí)驗(yàn)的參數(shù)設(shè)置

4.1 任務(wù)到達(dá)速率對算法性能的影響

該實(shí)驗(yàn)將探究在不同的任務(wù)到達(dá)速率的情況下遺傳算法和實(shí)時(shí)調(diào)度算法的性能。該實(shí)驗(yàn)在合理的范圍內(nèi)隨機(jī)生成了200個任務(wù)，使用不同的速率到達(dá)MEC服務(wù)器。共進(jìn)行7組實(shí)驗(yàn)，每組實(shí)驗(yàn)僅到達(dá)速率不同。通過控制任務(wù)到達(dá)的時(shí)間間隔實(shí)現(xiàn)不同的到達(dá)速率，如時(shí)間間隔為50 ms則表示每秒到達(dá)20個任務(wù)。實(shí)驗(yàn)結(jié)果如圖1所示，隨著任務(wù)到達(dá)速率的降低，經(jīng)過兩個算法進(jìn)行調(diào)度后能量消耗均有所降低，意味著更多的任務(wù)被調(diào)度到MEC服務(wù)器上執(zhí)行。當(dāng)任務(wù)到達(dá)速率較高時(shí)，大量的任務(wù)競爭MEC服務(wù)器計(jì)算資源。而MEC服務(wù)器計(jì)算資源較為有限，所以很多任務(wù)不能被調(diào)度，造成了更多的能量消耗。當(dāng)任務(wù)到達(dá)速率較低時(shí)則相反。

圖1 不同任務(wù)到達(dá)速率對算法性能的影響

由圖1可以看出，實(shí)時(shí)調(diào)度算法的性能優(yōu)于遺傳算法。遺傳算法優(yōu)化的是較小時(shí)間段內(nèi)到達(dá)的所有任務(wù)，而實(shí)時(shí)調(diào)度算法優(yōu)化的是每個任務(wù)到達(dá)后的調(diào)度操作，更大程度地提高了計(jì)算資源的利用率和調(diào)度效率，使得更多的任務(wù)被調(diào)度。此外實(shí)時(shí)調(diào)度算法在不用任務(wù)達(dá)到速率情況下的性能仍受響應(yīng)時(shí)間的影響，如圖2所示,圖中的平均響應(yīng)時(shí)間為所有響應(yīng)時(shí)間之和與響應(yīng)次數(shù)之比。

圖2 不同任務(wù)到達(dá)速率對算法響應(yīng)時(shí)間的影響

由圖2可以看出，隨著任務(wù)到達(dá)速率降低，兩個算法的平均響應(yīng)時(shí)間均降低。因?yàn)閱挝粫r(shí)間到達(dá)的任務(wù)數(shù)量減少了，算法調(diào)度的復(fù)雜度有所減低使得平均響應(yīng)速率降低。而當(dāng)任務(wù)到達(dá)速率較高時(shí)遺傳算法的性能受到很大影響，因?yàn)檫z傳算法每次調(diào)度的任務(wù)數(shù)量較多，算法復(fù)雜度較高，導(dǎo)致平均響應(yīng)時(shí)間較高，從而導(dǎo)致了對時(shí)延要求較高的任務(wù)錯過了有效時(shí)間。而實(shí)時(shí)調(diào)度算法的平均響應(yīng)時(shí)間受任務(wù)到達(dá)速率的影響較小，當(dāng)任務(wù)到達(dá)速率降低至一定程度后兩個算法擁有相同的平均響應(yīng)時(shí)間。

4.2 任務(wù)工作量對算法性能的影響

工作量決定任務(wù)執(zhí)行需要的時(shí)間，從而對調(diào)度決定造成影響，該實(shí)驗(yàn)探究不同工作量情況下兩個算法的性能。該實(shí)驗(yàn)中生成了200個相同工作量的任務(wù)，這200個任務(wù)其余的參數(shù)均在合理范圍內(nèi)隨機(jī)生成。任務(wù)以相同的速率到達(dá)MEC服務(wù)器，到達(dá)速率選取為5個/s，由上一個實(shí)驗(yàn)可知再次到達(dá)速率下兩個算法的性能同樣好。共進(jìn)行10組實(shí)驗(yàn)，每組實(shí)驗(yàn)中的任務(wù)除工作量外均相同。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 不同工作量對算法性能的影響

由圖3可知，隨著任務(wù)工作量的增加，兩個算法所對應(yīng)的能量消耗與工作量之比均上升，即算法性能降低。當(dāng)工作量足夠小時(shí)，兩個算法的性能達(dá)到最佳。因?yàn)楣ぷ髁孔銐蛐?，任?wù)所需的計(jì)算資源少，所有的任務(wù)都被調(diào)度到MEC服務(wù)器上執(zhí)行。隨著任務(wù)工作量的增加算法性能迅速下降，性能下降速率逐漸降低，而當(dāng)工作量達(dá)到一定值時(shí)兩個算法性能均達(dá)到最差，因?yàn)槿蝿?wù)工作量過大，對計(jì)算資源的需求很高，所以絕大部分的任務(wù)沒有被調(diào)度。隨著任務(wù)工作量逐漸增加，任務(wù)對計(jì)算資源的需求也隨之增加，任務(wù)之間對計(jì)算資源的競爭更加激烈，而后激烈程度逐漸降低，所以算法性能降低的速度先快后慢。

由圖3可以看出，實(shí)時(shí)調(diào)度算法的性能優(yōu)于遺傳算法的性能，性能下降的速率也較低于遺傳算法。因?yàn)閷?shí)時(shí)調(diào)度算法提高了對計(jì)算資源的利用率，使得更多的任務(wù)被調(diào)度到MEC服務(wù)器上執(zhí)行。

4.3 任務(wù)時(shí)延要求對算法性能的影響

任務(wù)時(shí)延要求決定了任務(wù)是否應(yīng)該被先執(zhí)行，也影響著調(diào)度決策。任務(wù)時(shí)延要求為除去任務(wù)執(zhí)行所必需的時(shí)間(以任務(wù)本地執(zhí)行的時(shí)間為必需時(shí)間)外可等待的、延遲的時(shí)間。該實(shí)驗(yàn)將探究不同的任務(wù)時(shí)延要求對算法性能的影響，實(shí)驗(yàn)生成了200個任務(wù)有相同時(shí)延要求的任務(wù)，這200個任務(wù)其余參數(shù)均在合理范圍內(nèi)隨機(jī)生成，以5個/s的速率到達(dá)MEC服務(wù)器。共設(shè)計(jì)10組實(shí)驗(yàn)，每組數(shù)據(jù)除時(shí)延要求外均相同，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 不同時(shí)延要求對算法性能的影響

由圖4可以看出，任務(wù)時(shí)延要求對遺傳算法的影響較小，但是能量消耗總體呈現(xiàn)下降趨勢。而實(shí)時(shí)調(diào)度算法受任務(wù)時(shí)延要求的影響較大，能量消耗總體呈現(xiàn)上升趨勢，但是上升幅度較小。任務(wù)時(shí)延要求的時(shí)間越長，被調(diào)度的可能性越高，所以遺傳算法的能量消耗總體呈現(xiàn)下降趨勢。任務(wù)時(shí)延要求的時(shí)間越長相對于先到達(dá)的任務(wù)是有優(yōu)勢的，大部分任務(wù)被調(diào)度。但是會導(dǎo)致等待執(zhí)行隊(duì)列逐漸變長，這對后到的任務(wù)并不有利，甚至導(dǎo)致一部分任務(wù)不被調(diào)度，所以遺傳算法的性能提升較小。因?yàn)榈却龍?zhí)行隊(duì)列過長，實(shí)時(shí)調(diào)度算法可利用的資源減少了，所以算法的性能反而有所下降。但是總體來看實(shí)時(shí)調(diào)度算法的性能仍然優(yōu)于遺傳算法。當(dāng)任務(wù)時(shí)延要求的時(shí)間增大到某個數(shù)值(圖4中A點(diǎn))時(shí)所有的任務(wù)都能被調(diào)度，所以兩個算法的能量消耗會穩(wěn)定在某個值。

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

本節(jié)探究了多種因素對算法性能的影響，從實(shí)驗(yàn)結(jié)果可看出實(shí)時(shí)調(diào)度算法在高并發(fā)和高時(shí)延要求情況仍能保存良好的性能，且始終優(yōu)于遺傳算法，主要有以下兩個原因：一是實(shí)時(shí)調(diào)度算法的復(fù)雜度比遺傳算法復(fù)雜度低，每增加一個任務(wù)，遺傳算法增加的處理步驟是實(shí)時(shí)調(diào)度算法的幾十倍，使得有些任務(wù)沒能被及時(shí)處理而錯過了有效調(diào)度時(shí)間；二是實(shí)時(shí)調(diào)度算法對計(jì)算資源的利用率更高，實(shí)時(shí)調(diào)度算法通過“插隊(duì)”和“替換”方式更大程度地利用計(jì)算資源，提高計(jì)算資源的效用。

5 結(jié)束語

本文研究了MEC中多用戶場景下的任務(wù)調(diào)度問題，分析了有效解決任務(wù)調(diào)度問題的必要性。通過分析場景特性建立任務(wù)調(diào)度問題的優(yōu)化模型，并依據(jù)任務(wù)調(diào)度的實(shí)時(shí)性將該優(yōu)化問題分別放縮至兩個較小規(guī)模的優(yōu)化問題。使用遺傳算法和實(shí)時(shí)調(diào)度算法進(jìn)行求解得到任務(wù)調(diào)度策略。通過仿真實(shí)驗(yàn)，驗(yàn)證了實(shí)時(shí)調(diào)度算法的可行性，測試了多種環(huán)境下算法的性能優(yōu)勢。實(shí)時(shí)調(diào)度算法在有效實(shí)現(xiàn)任務(wù)調(diào)度、保障服務(wù)質(zhì)量的同時(shí)降低了智能設(shè)備整體的能量消耗，即使在高并發(fā)和高時(shí)延要求等情況下仍能保持良好的性能。在未來的研究中，擬考慮更大規(guī)模(任務(wù)數(shù)量更多、智能設(shè)備更多、MEC服務(wù)器數(shù)量更多)的任務(wù)調(diào)度問題，在大規(guī)模場景下繼續(xù)完善優(yōu)化模型及算法。