基于移動邊緣計算的任務調度算法設計

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

(哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱150001)

0 引言

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

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

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

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

1 系統與計算模型

1.1 系統模型

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

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

1.2 計算模型

1.2.1 本地計算模型

任務在本地執行的時間消耗為：

任務在本地執行的能量消耗為：

1.2.2 服務器計算模型

因為視MEC服務器的能量是無限的，所以任務在MEC服務器上的能量消耗不計，只考慮任務執行的時間消耗。此時間消耗為：

1.2.3 數據傳輸模型

任務在傳輸過程中的時間消耗為：

任務在傳輸過程中的能量消耗為：

2 能量消耗模型與任務調度問題

2.1 任務的時延約束

2.2 任務的依賴性約束

2.3 能量消耗模型

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

設所有連接到任務調度系統的智能設備的整體能量消耗為E，則E可以表示為：

2.4 任務調度問題

在任務調度問題中需要確定哪個任務可以被調度到MEC服務器中執行，任務能否被調度到MEC服務器中執行取決于時延約束和任務依賴性約束，此外還需考慮智能設備的能量消耗問題。所以多用戶場景下的任務調度問題可以轉換為一個以任務時延和依賴性為約束條件，以最小化整體能量消耗為目標函數的優化問題：

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

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

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

3 問題求解與算法設計

因為智能設備持續生成任務并持續遷移到MEC服務器上執行，而任務具有時延約束需要盡快得到合理的調度。所以很難得到一個較長時間段內智能設備整體的能量消耗最小值，只能將較長的時間段分割成若干個較小的時間段，以較小時間段內的能量消耗最小值累積得到較長時間段內的近似能量消耗最小值。

3.1 優化問題求解

將較長的時間段分割至極小，即每當有任務遷移請求達到MEC服務器就對該任務進行一次調度。因為遷移到MEC服務器上執行的任務較多，所以會有一部分任務在MEC服務器中等待被執行。當新任務到達時對新任務和等待執行的任務進行調度操作(可能改變執行的順序或之前的調度決策)。設總共進行Y次調度，每次調度后產生的能量消耗為ΔEy。

假設，新到達的任務來自智能設備m上的任務n。如果新任務不被調度，則ΔEy等于在智能設備上執行產生的能量消耗，可表示為：

如果新任務被調度且等待執行的任務調度決策沒有被改變，則ΔEy等于在MEC服務執行所產生的能量消耗，可表示為：

如果新任務替換了之前被調度的任務，則ΔEy等于新任務在MEC服務器上執行產生的能量消耗加上被替換的任務回到智能設備執行產生的能量消耗，設被替換的任務來自智能設備i上的任務j，則表示為：

所有連接到MEC服務器的智能設備的整體能量消耗可看作所有操作產生的ΔEy之和，可表示為：

因此OP1可以放縮為：

針對每個任務的調度問題可以表示為：

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

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

3.2 實時調度算法

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

實時調度算法可表示為：對于新到的任務x和等待隊列K。

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

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

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

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

⑤ 如果有可行解則選擇其中的最優解，如果存在多個最優解則選擇最后獲得的最優解，如果不存在可行解則新到的任務x不被調度。

3.3 遺傳算法

因此OP1可以放縮為所有較小時間段內的最優解之和：

因此較小時間段內的調度問題可以表示為：

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

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

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

4 實驗

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

表1 實驗的參數設置

4.1 任務到達速率對算法性能的影響

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

圖1 不同任務到達速率對算法性能的影響

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

圖2 不同任務到達速率對算法響應時間的影響

由圖2可以看出，隨著任務到達速率降低，兩個算法的平均響應時間均降低。因為單位時間到達的任務數量減少了，算法調度的復雜度有所減低使得平均響應速率降低。而當任務到達速率較高時遺傳算法的性能受到很大影響，因為遺傳算法每次調度的任務數量較多，算法復雜度較高，導致平均響應時間較高，從而導致了對時延要求較高的任務錯過了有效時間。而實時調度算法的平均響應時間受任務到達速率的影響較小，當任務到達速率降低至一定程度后兩個算法擁有相同的平均響應時間。

4.2 任務工作量對算法性能的影響

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

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

由圖3可知，隨著任務工作量的增加，兩個算法所對應的能量消耗與工作量之比均上升，即算法性能降低。當工作量足夠小時，兩個算法的性能達到最佳。因為工作量足夠小，任務所需的計算資源少，所有的任務都被調度到MEC服務器上執行。隨著任務工作量的增加算法性能迅速下降，性能下降速率逐漸降低，而當工作量達到一定值時兩個算法性能均達到最差，因為任務工作量過大，對計算資源的需求很高，所以絕大部分的任務沒有被調度。隨著任務工作量逐漸增加，任務對計算資源的需求也隨之增加，任務之間對計算資源的競爭更加激烈，而后激烈程度逐漸降低，所以算法性能降低的速度先快后慢。

由圖3可以看出，實時調度算法的性能優于遺傳算法的性能，性能下降的速率也較低于遺傳算法。因為實時調度算法提高了對計算資源的利用率，使得更多的任務被調度到MEC服務器上執行。

4.3 任務時延要求對算法性能的影響

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

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

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

4.4 實驗分析

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

5 結束語

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