云邊環(huán)境下的任務調(diào)度算法研究綜述

靳紫薇，郭會明，焦 函

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

0 引言

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

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

1 調(diào)度問題優(yōu)化目標

縮短執(zhí)行時間和降低成本是大多數(shù)調(diào)度算法重點關(guān)注的兩種優(yōu)化目標，除此之外，調(diào)度算法的研究通常也考慮了其他一些性能指標：負載均衡、能耗等。

1.1 執(zhí)行時間

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

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

1.2 成本

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

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

1.3 負載均衡

云邊環(huán)境下，負載均衡表示系統(tǒng)內(nèi)不同節(jié)點負載的均勻程度，可通過公式（1）表示。其中，u表示第個節(jié)點的資源利用率，-表示系統(tǒng)內(nèi)設備平均資源利用率，表示系統(tǒng)內(nèi)設備數(shù)目。

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

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

本節(jié)針對云邊環(huán)境，按以下分類方法梳理了當前任務調(diào)度算法的發(fā)展歷程與研究現(xiàn)狀，介紹了各類算法的策略思想與優(yōu)缺點。

圖1 任務調(diào)度算法分類

2.1 啟發(fā)式算法

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

2.1.1 基于列表的調(diào)度算法

基于列表的調(diào)度算法是當前研究最廣泛的啟發(fā)式算法，通常基于列表的調(diào)度算法包含兩個主要階段：第一階段是列表優(yōu)先級排序，基于優(yōu)先級度量為每個任務分配優(yōu)先級；第二階段是任務映射，按照優(yōu)先級和約束條件為每個任務匹配適當?shù)奈锢碣Y源。

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

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

2.1.2 基于復制的調(diào)度算法

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

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

2.1.3 基于聚類的調(diào)度算法

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

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

2.2 元啟發(fā)式算法

元啟發(fā)式算法是隨機算法與局部搜索算法相結(jié)合的產(chǎn)物。元啟發(fā)式任務調(diào)度算法主要包括群體智能算法和機器學習算法。

2.2.1 群體智能算法

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

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

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

2.2.2 機器學習算法

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

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

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

3 挑戰(zhàn)與展望

諸多研究人員在調(diào)度算法領(lǐng)域取得了諸多成果，但是當前研究還存在多種問題。

3.1 虛擬化技術(shù)為調(diào)度算法帶來諸多不確定因素

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

3.2 云邊環(huán)境下的調(diào)度策略難以實際驗證

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

3.3 無服務器執(zhí)行模型的興起

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

云計算和邊緣計算領(lǐng)域新技術(shù)的發(fā)展為任務調(diào)度帶來了更多可能性，結(jié)合當前需求和技術(shù)發(fā)展進行分析，云邊調(diào)度算法的后續(xù)研究可以從以下幾個方面尋求突破。

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

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

4 結(jié)語

本文敘述了云邊環(huán)境下，任務調(diào)度算法的發(fā)展歷程及未來挑戰(zhàn)，其中，以啟發(fā)式和元啟發(fā)式算法為劃分詳細介紹了任務調(diào)度算法的研究現(xiàn)狀， 在此基礎上，對比和分析了當前各類算法的優(yōu)勢與不足，總結(jié)了當前云邊環(huán)境下任務調(diào)度算法面臨的挑戰(zhàn)及未來發(fā)展方向，以期為該領(lǐng)域?qū)W者的后續(xù)研究提供參考。