云邊環境下的任務調度算法研究綜述

靳紫薇，郭會明，焦 函

（1.中國航天科工集團第二研究院，北京 100039；2.北京航天長峰股份有限公司，北京 100039）

0 引言

隨著物聯網及相關技術的發展，海量終端設備加入互聯網，形成萬物互聯的網絡空間。面對終端和用戶的海量請求，云計算難以滿足終端低延遲與及時響應的要求。邊緣計算應運而生，文獻［1］首次正式定義了邊緣計算：允許在網絡邊緣對代表云服務的下游數據和代表物聯網服務的上游數據進行處理的新型計算范式。

云中心與邊緣設備的硬件異構性、地理位置差異性導致了二者適用任務不同。傳統云計算具有強大的集中式計算能力和存儲能力，比較適合長周期，非實時性的數據處理。邊緣計算與用戶地理位置更為接近，但受限于計算和通信能力、續航能力，邊緣計算更適合短周期、實時性的數據處理。在云邊計算模型下，“如何協同”成為當下研究人員謀求突破的一大難點。在云邊環境下，合理分配用戶任務能夠實現硬件資源與用戶需求的高效映射，能夠提高整個系統的性能與效率、降低成本與能耗、滿足用戶服務質量。然而，任務調度本身是一個NP-難問題，同時，云-邊、邊-邊資源異構性、虛擬化技術的發展也為任務調度優化問題提出了嚴峻的挑戰。資源管理與任務調度作為云邊協同計算模型至關重要亦是不可回避的關鍵環節，成為當下研究的重點與難點。

1 調度問題優化目標

縮短執行時間和降低成本是大多數調度算法重點關注的兩種優化目標，除此之外，調度算法的研究通常也考慮了其他一些性能指標：負載均衡、能耗等。

1.1 執行時間

云邊環境下，任務的執行時間是指節點提交任務請求至收到云邊系統的任務執行結果的整個過程所需的響應時間。任務的執行時延取決于任務本身的量級和任務被分配的資源容量，文獻［4］通過實驗比較了純云、純邊緣和云邊混合處理執行MapReduce 任務集種不同應用的性能，分析得出不同的應用適用于不同的處理方式，而合理的調度方案能夠實現任務與資源的高效映射，縮短執行時延。

對計算時間和云邊通信時間的優化是縮短執行時延的有效手段，也是當前研究的熱點。文獻［5］考慮到云邊節點處理速度差異，將云邊環境下的任務調度問題執行時間最小化問題抽象為將基于邏輯的Benders 分解（LBBD）原理與混合整數線性規劃（MILP）模型相結合的求解，實現任務到異構計算節點的映射。由于云邊架構的地理位置、帶寬差異等特性，任務卸載至不同位置的服務器將帶來不同的通信開銷。相比于傳統云計算，這種通信差異在云邊環境下導致了不可忽略的執行時間的影響。文獻［6］考慮了邊緣計算和云計算的數據分布特點，與云邊之間的數據帶寬、邊緣端數據中心數量和邊緣數據中心的存儲容量等影響因素，提出了一種混合遺傳算子的自適應粒子群優化算法，有效減小工作流調度在云端與邊緣端之間的數據傳輸時延。

1.2 成本

成本取決于能耗與執行時間，同時也與設備損耗相關。其他一些研究還考慮了云邊的設備狀態差異、結構差異等因素，如文獻［7-9］使用動態電源管理、動態電壓頻率縮放、松弛回收、資源休眠等技術有效減少了計算資源的能耗。

文獻［10］通過電壓動態調整技術，在滿足任務截至時間約束的前提下，達到系統能耗最小化。文獻［11］通過分析計算節點功耗與設備資源利用率之間的關系，推斷出作業執行能耗和最佳資源利用率，通過感知資源利用率，提出具有能源感知的啟發式調度算法，將貪心策略與搜索優化方法相結合，提出了混合粒子群優化算法，作用于任務調度，提高了該算法的全局優化能力，降低了工作的平均能耗。

1.3 負載均衡

云邊環境下，負載均衡表示系統內不同節點負載的均勻程度，可通過公式（1）表示。其中，u表示第個節點的資源利用率，-表示系統內設備平均資源利用率，表示系統內設備數目。

文獻［12］針對異構云環境，提出了具有物聯網感知的多資源任務調度算法，主要針對計算資源負載均衡和時間均衡。文獻［13］針對云計算的復雜能耗問題，提出了一種基于云霧計算的能源感知型調度算法，從軟件定義網絡架構和云霧計算負載均衡算法入手，一方面分散了霧節點和云計算系統的異構計算數據，另一方面，定義了網絡的的集中信息和分布式調度程序，以橢圓分割區域為對象，實施部署數據共享和異構云霧計算任務的最佳分配。

2 任務調度算法

本節針對云邊環境，按以下分類方法梳理了當前任務調度算法的發展歷程與研究現狀，介紹了各類算法的策略思想與優缺點。

圖1 任務調度算法分類

2.1 啟發式算法

啟發式算法的算法思想比較簡單直觀，它基于經驗，在可接受時間內中給出待解決問題的一個可行解。啟發式任務調度算法大致分為三類：基于列表的算法、基于任務復制的算法和基于聚類的算法。

2.1.1 基于列表的調度算法

基于列表的調度算法是當前研究最廣泛的啟發式算法，通常基于列表的調度算法包含兩個主要階段：第一階段是列表優先級排序，基于優先級度量為每個任務分配優先級；第二階段是任務映射，按照優先級和約束條件為每個任務匹配適當的物理資源。

其中最著名的就是異構最早完成時間算法（HEFT）, 該算法思想對后來基于列表的調度算法產生了深遠的影響。HEFT 首先計算各任務的優先級，然后按優先級進行排序并依次分配任務給最早空閑的實例上。傳統HEFT算法通常考慮調度時延作為優先級排序的標準，但目前也有學者研究將HEFT 算法擴展到多目標空間，應對復雜的云邊環境異構資源管理場景。文獻［16］提出了FDHEFT 算法，將模糊優勢排序機制作為優先級計算方式，實現了云霧環境中調度成本和完成時間的聯合優化，但是對云霧節點間的通信和存儲開銷等考慮不夠充分。傳統的列表調度算法準確度高度依賴于任務基于硬件的執行前估計，而云邊計算允許設備自由接入接出，硬件環境頻繁改變，使得估計難以實現。當前研究對這一缺陷也有突破，文獻［17］提出了SHEFT 算法，考慮資源數量可以根據服務請求彈性擴展，允許在調度過程中動態變化，實現了工作流的彈性調度，滿足了實際云邊環境下資源按需分配、彈性伸縮的應用場景，但是未能考慮云邊異構的通信能力和邊緣設備的管理。

除此之外，基于列表的調度算法研究的另一重要成果是處理器上關鍵路徑算法（CPOP），該算法也對后續研究產生了深遠影響。文獻［18］對CPOP算法進行改進提出了新的調度算法CPOC，為關鍵路徑任務分配一個硬件集群，更細粒度的資源分配進一步縮短了關鍵路徑處理時間，但同時引入了任務間的數據通信開銷，導致該算法不適用于云邊下通信能力存在差異的場景。

2.1.2 基于復制的調度算法

為解決邊緣節點計算資源、網絡帶寬、電池壽命受限問題，計算遷移技術應運而生，極大擴充了任務分配方案的選擇：將終端的計算任務遷移到資源更為豐富的設備上、將云中心的計算下沉至邊緣節點、對任務進行細粒度拆分并使用多個資源協同計算，計算遷移使得相互依賴任務在不同設備間的數據傳輸時延問題愈發嚴重。基于復制的調度算法通過冗余計算的方法來減少此類開銷，優化調度。其主要方法是將具有數據依賴的任務分配給相同的實例單元來避免文件傳輸，從而減少任務間通信開銷。

基于復制的調度算法分為兩類：部分復制的調度（SPD）和完整復制的調度（SFD）算法。SPD 算法只允許復制關鍵路徑上的任務，因此具有較低的時間復雜度，但是對于數據流較大的系統該方法并不適用。SFD 算法可以復制聯接節點的所有父任務，并且可以將任務復制到包含聯接節點的所有VM實例。這使得該算法具有更好的性能，但同時也提高了任務的復雜度。文獻［19］提出了一種LSTD 算法，在不增加整體時間復雜度的情況下，引入任務復制策略，嘗試在最早空閑的兩個節點上插入任務，保障任務調度的可靠性，但是插入節點的選擇可能會導致任務整體的執行時延增加。文獻［20］提出了一種基于任務復制和插入的調度算法（DILS），結合動態完成時間預測，將部分任務復制到不同節點，并插入空閑時隙，以加快后續任務的執行。在不影響整體調度時延的前提下降低任務間通信時間，但是插入時隙的選擇依賴于任務的預先估計，且會帶來更高量級的時間復雜度。

2.1.3 基于聚類的調度算法

云邊環境中，常常存在云、霧、邊的設備差異性與地理位置差異性，各節點實例間存在通信開銷差異。為了提高各數據中心內聚性、降低不同數據中心之間的耦合性，基于聚類的調度算法通過將存在大量通信的任務組合到同一個集合中并進行統一分配，從而實現云與邊緣設備的低傳輸延遲，在多個數據中心之間保持負載平衡和有效的資源利用率。

文獻［21］提出了一種基于任務聚類（HTTSC）的混合調度算法，巧妙地將任務聚類的方法與任務復制相結合。該方法首先根據任務間通信開銷將任務聚類為多個簇，將任務復制的對象由單個任務轉變為任務簇，縮短了通信開銷，并提前了后續任務的開始時間，但是多種調度方法的結合也增加了調度算法的復雜性，在云計算實時調度場景下應用效果不佳。文獻［22］提出使用顯性序列聚類（DSC）將任務劃分為不同的簇；使用內核函數均值漂移聚類（MSE）對虛擬機進行實例聚類，之后根據硬件權重和負載情況匹配節點簇與任務簇，該算法創新性地將任務和節點都進行聚類，減少了通信開銷，但是每個任務均需要調用MHEFT 算法計算權重，導致該算法時間復雜度提高了一個量級。文獻［23］提出了一種基于三路決策的聚類權重算法（TWCW），使用三向K-means 聚類將任務劃分多個簇，并包含核心區域、邊緣區域、模糊區域，根據聚類中心的屬性偏好進行調度，使任務簇盡可能執行在適合的設備上，該方案顯著提高服務質量（QoS），降低能耗。由于其簡單的任務適配在多任務場景下導致負載不均，降低系統資源利用率，使得QoS下降。

2.2 元啟發式算法

元啟發式算法是隨機算法與局部搜索算法相結合的產物。元啟發式任務調度算法主要包括群體智能算法和機器學習算法。

2.2.1 群體智能算法

與基于貪婪的局部最優選擇思想的啟發式任務調度算法不同，群體智能算法是隨機初始化和局部搜索算法相結合的產物，它規避了啟發式算法針對不同問題實例產生不一致結果的問題，這類算法很大程度上參考了生物特性，具有很強的適應性。許多著名的元啟發式算法已經得到了廣泛應用，包括遺傳算法（GA）、粒子群優化（PSO）、布谷鳥搜索（CS）等。但是，元啟發式算法的搜索過程隨問題的不同而變化，并且具有隨機性大，全局搜索效率低以及后期迭代收斂過早的缺點。許多專家學者為改善這一不足進行了深入研究。文獻［24］考慮了數據中心之間的帶寬、邊緣數據中心的數量和存儲容量等傳輸時延影響因素，提出了一種帶有遺傳算法交叉和變異算子的自適應離散PSO 算法（GA-DPSO），避免了傳統粒子群優化算法的早熟收斂，增強了種群進化的多樣性，有效壓縮數據傳輸時延，提高了系統服務質量。該方法通過固定部分任務與節點的映射關系規避了種群多樣性多帶來的搜索效率下降問題，但是該策略存在一定缺陷，限制了解空間，影響了調度結果。文獻［25］提出了一種改進的多目標灰狼優化算法（IMOGWO），該方法維護一個非最優解外部存檔，通過網格機制改進非最優解，領導者選擇機制更新和替換外部存檔，并且引入了個體密度和細胞支配概念動態調整自適應參數，并且以高斯擾動的經營學習策略緩解過過早收斂問題，該方法在執行時間和負載均衡指標上均有顯著提升，但是該方法局限于獨立任務調度，難以適用云計算多任務調度場景。

除此之外，亦有諸多研究人員考慮云邊環境下的其他影響因素，在算法工程化過程中貢獻出智慧。文獻［26］針對云-霧環境下大規模異構并行結構資源利用率低、數據傳輸消耗網絡帶寬、終端請求對資源需求不同的特點，提出了一種改進的煙花算法（I-FASC），量化任務與資源并分類為計算、存儲、帶寬敏感型，將云邊系統內各設備負載均衡作為優化目標，通過引入煙花爆炸半徑檢測機制，設置爆炸半徑最小閾值及半徑參數自適應的方式，提高算法局部搜索能力，改善算法整體效果。但是該算法以獨熱編碼表示解空間，以歐式距離作為煙花間距忽略了任務-節點對的差異性，影響了算法的效果。

群體智能算法相比于啟發式算法具有更高的時間復雜度，導致其很難適應于云邊環境下實時調度場景。隨著云邊環境下虛擬化技術的發展，任務調度問題常常與虛擬機或容器的創建緊密相關。文獻［27］在Kubernetes框架的基礎上，研究了為Pod選擇虛擬實例時的資源使用成本問題，將蟻群算法和粒子群算法相結合，對Kubernetes 調度模塊進行了Pod 的節點部署優化。但多容器環境下任務存在資源競爭，許多學者為了研究的方便，對調度模型進行簡化，常常忽略資源爭用導致的執行結果干擾，導致群體智能算法研究中構造的適應度函數難以準確反應實際調度方案的真實性能。

2.2.2 機器學習算法

機器學習算法由于其時間復雜度問題，在云邊環境下的任務調度領域的應用存在一些限制，但也取得了諸多成就。機器學習算法常用于預測應用執行情況，進一步指導調度算法，從而提高云邊系統的資源管理能力與調度效率。

文獻［28］將任務分類為CPU、Web、IO 密集型，使用主成分分析與回歸分析提取、篩選并評估任務不同特征指標對系統總能耗的貢獻，針對異構環境下不同設備的硬件信息，進行云邊數據中心設備實例的能耗建模，為指導資源供應和虛擬機遷移做出參考。該論文考慮了多類任務在異構硬件上運行對能耗的不同貢獻，對動態任務調度有重要意義，但是該方法要求預先獲取大量任務特性，難以滿足云計算實時性要求，具有一定的局限性。文獻［29］中提出了一種基于ANN 的機器學習算法以實現高吞吐量的異構系統調度，該調度模型使用不同計算資源及其當前負載的統計信息預測下一個調度間隔中的任務行為，獲得資源實例的服務能力最大化，并為每個資源實例訓練兩個模型提高預測算法的準確度。根據預測結果預先分配資源，并根據任務行為進行對應處理，顯著提高系統的吞吐量，但是任務行為難以預測，模型預測準確度不高。文獻［30］中作者通過在線學習的隱馬爾可夫鏈模型，對工作流任務進行預測，并將篩選部分特征參數和預測結果進行在線訓練，以此提高任務調度的精度，該算法在預測精度上有明顯提升，改善了文獻［29］預測精度差的問題，但引入了在線學習的時間開銷，增加了調度模塊的時空復雜度。

機器學習算法不但在任務估計中發揮重要作用，其中的分類算法亦可直接應用于任務調度。該類算法憑借其極強的適應性且具有在線學習能力等特點，在云邊系統下的調度過程中，能夠不斷完善算法準確度，從而提高云邊計算系統服務質量。雖然機器學習算法的時間和空間復雜度問題，限制了該算法在任務調度領域的表現。但是隨著硬件算力的提升，這些問題正得到逐步緩解。機器學習仍然是當前云邊環境下的任務調度研究的一大熱點。

3 挑戰與展望

諸多研究人員在調度算法領域取得了諸多成果，但是當前研究還存在多種問題。

3.1 虛擬化技術為調度算法帶來諸多不確定因素

隨著容器化技術的發展，為云計算帶來輕量化的部署和資源管理的同時，也對任務調度提出了動態化要求，容器的遷移使得調度模塊必須能夠動態修改調度策略，此外容器化技術隔離性差的特點，也會導致當多個容器部署在同一虛擬機（VM）內，任務間存在相互干擾。虛擬化技術使得云邊環境下的任務調度研究更加艱難。

3.2 云邊環境下的調度策略難以實際驗證

當前研究通常只通過模擬驗證調度策略的有效性，例如使用CloudSim、iFogSIm 等軟件建模和模擬整個云計算環境。調度策略通常是為管理大型云邊環境中的大量應用程序而設計的，實際環境下的驗證成本高昂、耗時過久。當前研究受限于研究環境，難以對調度方案進行頻繁測試。

3.3 無服務器執行模型的興起

無服務器計算是一種事件驅動的新興云執行模型，其中云用戶提供代碼，云提供商管理該代碼執行環境的生命周期。該執行模型提供更細粒度的資源分配，能充分利用分配的資源。同時也為任務調度帶來了極大困難，細粒度的資源分配往往會導致當前基于任務與節點映射關系的傳統調度算法研究失效。

云計算和邊緣計算領域新技術的發展為任務調度帶來了更多可能性，結合當前需求和技術發展進行分析，云邊調度算法的后續研究可以從以下幾個方面尋求突破。

（1）云邊環境下自適應和智能化任務劃分和任務調度。云邊環境上應用的自適應劃分和分配是未來一大發展方向。為了實現這種細粒度劃分，需要感知與預測云邊系統中的節點特性和運行狀態。與當前基于完整任務的任務調度相比，自適應的細粒度任務劃分能進一步降低用戶的操作難度，提高任務執行效率并提升系統的負載均衡，是未來的一大研究熱點。

（2）跨云環境下的任務調度算法研究。隨著云用戶數量和任務計算規模的急劇增加，在大型跨云服務環境中向用戶提供資源將成為未來的重要方向。跨云環境為資源管理帶來了更大的挑戰，當前針對跨云環境滿足服務質量（QoS）、負載均衡等調度目標的研究相對匱乏，特別是針對大規模計算密集型任務的調度研究尚處于起步階段。

4 結語

本文敘述了云邊環境下，任務調度算法的發展歷程及未來挑戰，其中，以啟發式和元啟發式算法為劃分詳細介紹了任務調度算法的研究現狀， 在此基礎上，對比和分析了當前各類算法的優勢與不足，總結了當前云邊環境下任務調度算法面臨的挑戰及未來發展方向，以期為該領域學者的后續研究提供參考。