邊緣環境下計算密集型任務調度研究綜述

劉炎培，朱運靜，賓艷茹，陳寧寧，王麗萍

鄭州輕工業大學 計算機與通信工程學院，鄭州 450001

根據最新的思科年度互聯網報告顯示，到2023年，5G將支持超過10%的全球移動網絡連接，連接到IP網絡的設備數量將是全球人口的三倍以上，平均5G速度將達到575 Mbit/s，比平均移動網絡連接快13倍。憑借強大的功能，5G將為人工智能和新興物聯網應用提供更靈活的移動基礎設施，如自動駕駛汽車、智慧城市、遠程醫療和全景視頻。為了不斷發展5G無線技術并使網絡傳輸具有超高數據速率，低延遲，低能耗，高品質質量體驗和用戶數據的安全性[1]。近年來，在實時應用和智能通信的愿景驅動下，集中式云計算向分布式邊緣計算的范式轉變。邊緣計算的主要特性是將云服務拖向網絡邊緣，大幅減少延遲，同時提高網絡和計算設備的資源利用率。邊緣計算作為云計算的自然延伸，延續了各種研究挑戰，也提出了不同的新問題需要解決。任務調度[2]是邊緣計算的一個關鍵的環節，是任務經過優化后可以映射到合適的資源池上執行的一個過程，且調度算法策略旨在優化各種QoS參數，如成本、完工時間、可擴展性、可靠性、資源利用率以及能耗等性能指標。

由于邊緣環境存在當用戶數據請求過于頻繁時，會導致網絡卡頓和延遲，邊緣調度技術是減少時延和視頻傳播任務的延遲敏感性的重要方法，所以邊緣計算調度和分配技術作為移動邊緣計算技術的熱點，為5G發展的需求提供了可能。隨著5G和邊緣計算的結合滿足了自動駕駛的需求，無論是在面對高性能計算的需求還是對計算密集型應用服務網絡延遲的需求[3]，當用戶發送大量的任務請求時，會給邊緣端服務器帶來巨大負擔和能耗，車輛或路測單元使用邊緣調度技術可以滿足用戶服務質量的需求，并且可以為車輛用戶提供更好的服務質量體驗。在邊緣計算中，任務調度不僅影響用戶的時間和成本，同時對邊緣平臺的性能起到很大的作用，因此實現高效的調度用戶任務，成了邊緣云研究領域的一個重要問題。邊緣計算調度在物聯網（IoT）中應用的場景：（1）人臉識別。由于目前現存的基于中心云人臉識別系統遠離終端設備，并且大量圖像數據會給云服務器帶來高計算負載和低實時性的問題，于是邊緣服務器可以對人臉進行實時性檢測以及特征提取，并根據深度強化學習訓練的中間結果對魯棒的人臉特征進行快速處理和響應，對于無法處理的人臉識別任務，實施人臉識別任務調度算法。（2）車聯網（internet of vehicles，IoV）。車聯網環境中車載終端中的實時任務卸載到路邊單元RSU使用調度技術，可以有效緩解車輛終端計算力低下、資源匱乏或者資源搶占等困境。（3）虛擬現實（virtual reality，VR）。目前已提出了構建云計算數據中心資源采樣模型，并結合虛擬現實（VR）互動裝置輸出、轉換、調度中心資源，提取中心資源的關聯規則特征量，采用模糊聚類融合分析方法重構中心資源，建立虛擬化云計算數據中心資源的信息融合中心，使用分析方法實現對數據中心資源調度，可以實現虛擬化云計算數據中心資源實時節能調度。

任務調度在提高資源利用率和為用戶提供優質服務方面發揮著重要作用，并且計算調度技術也成為邊緣計算領域中的熱門話題之一。一個好的任務調度策略可以靈活地適應邊緣和云計算的動態環境，有效地減少用戶提交任務所需的時間，提高資源利用效率。文獻[4]研究了節點到節點/設備到設備（N2N/D2D）通信和任務調度的備用頻譜，并比較了不同的網絡參數和服務條件下的性能增益。文獻[5]研究了將任務卸載到網絡邊緣的設備，邊緣計算減少了服務延遲和帶寬消耗，于是通過任務調度提升網絡的性能。并比較了各種優化算法之間的能耗、成本和安全性方面。文獻[6]研究了任務調度在移動云計算平臺面臨著設備移動性、工作負載分布、連接選擇、成本估算和能量限制等影響因素。雖然上述研究取得了一定成果，到目前為止，由于邊緣服務器上任務調度的資源分配不合理不僅會降低任務的計算效率增加計算時間，還會造成任務排隊產生排隊時延，由一些服務器資源枯竭進而導致其他服務器資源浪費的情況，從而使得邊緣網絡出現整體資源利用率不高、性能差等問題。為了克服這些問題，本文通過對目前最新任務調度方法進行系統的分析、整理和歸納，總結當前基于SDN的MEC框架和計算密集型應用任務調度執行過程，以及應用場景進行了詳細的論述，通過考慮時間和成本、能耗和資源利用率、負載均衡和吞吐量對當前調度策略技術的研究成果進行分析、對比和總結，并介紹了適合5G環境下最新的計算密集型調度優化策略。最后討論了邊緣調度策略的研究趨勢。

1 邊緣環境下計算密集型任務調度概述

歐洲電信標準協會（European Telecommunications Standards Institute，ETSI）通過將邊緣計算融合到移動網絡的架構，提出了移動邊緣計算[6]。邊緣計算的主要特點是：（1）支持異構資源集；（2）地理分布；（3）支持時延敏感的應用；（4）提供可靠的無線通信，支持計算密集型終端設備可移動；（5）以最小延遲的位置感知。調度技術應用于邊緣云環境使得網絡數據傳輸更加高效，本章主要介紹邊緣云環境下的調度框架、執行過程、應用場景以及影響調度策略的性能指標。

1.1 計算密集型任務的分類

任務調度算法是云計算中的一個重要問題，因為它會影響邊緣云的性能；按照文獻[7]可以將任務劃分為計算密集型[8]和數據密集型[9]。科學和工程領域的復雜模擬通常包含大量計算密集型的數值任務，這些任務占用了大量的求解時間，并且這類應用程序對CPU計算的需求不同，與問題實例相關的數據量無關。數據密集型任務會發出大量的數據I/O，因此數據I/O通常占主導地位，并分布在整個任務中。同時，計算密集型作業/任務只執行有限的數據I/O，但大部分時間花在計算上。在計算密集型應用中，有基于仿真的應用，其目的是最大化系統資源來處理用于仿真的大型計算[10]，并且典型的用法之一是運行參數掃描實驗，其中研究模型的參數空間，以獲得一般行為的概述。其中計算密集型和數據密集型任務的不同影響如表1所示。

表1 計算密集型和數據密集型任務的不同影響Table 1 Differential impact of compute-intensive and data-intensive tasks

對于本文主要研究計算密集型任務數據處理，在其基礎上任務調度可分為以下幾類：

（1）即時任務調度：當新任務到達時，它們將直接調度到VM。

（2）批量任務調度：任務在發送前分組為一個批次；這種類型也稱為映射事件。

（3）靜態任務調度：它基于系統全局狀態的先驗信息，不考慮虛擬機的當前狀態，然后以類似的方式如循環和隨機調度算法在所有虛擬機之間等效地劃分所有流量。

（4）動態任務調度：考慮到虛擬機的當前狀態，不需要系統全局狀態的先驗信息，并根據所有可用虛擬機的容量分配任務。

（5）搶占式任務調度：每個任務在執行過程中被中斷，可以移動到另一個資源以完成執行。

（6）非搶占式任務調度：在完成已調度任務的執行之前，不會將VM重新分配給新任務。

1.2 計算密集型任務調度框架

邊緣計算支持分布式架構，其中計算設備被放置在本地，并且分布在離最終用戶更近的地方。邊緣計算的主要利益相關者是邊緣服務提供商、云服務提供商和最終用戶。邊緣框架與本地端設備之間的通信距離最小，可以最大限度地減少邊緣服務提供商的延遲和能耗。根據文獻[11-12]的研究，邊緣計算由一組無處不在的去中心化邊緣設備組成，這些設備可以使用不同的無線通信模式在本地處理和存儲數據，而不需要第三方的干預。圖1描述了邊緣環境下計算密集型應用的任務調度的框架，其中三個部分組成了調度整個框架：云服務提供商（CSP）、邊緣服務提供商（ESP）和用戶設備。對資源有需求的用戶設備可以用包含相關任務的請求來表示。假設一個分時系統，在任何時間段，一個用戶都會帶著包含在請求中的各種任務出現，并通過付費將該請求發送給ESP。用戶的目標是減少響應和處理時間，以獲得滿意的任務結果。眾所周知，邊緣計算被認為是云和用戶之間的樞紐，它是通過將計算傳遞到靠近這些用戶的普及網絡的邊緣來提出的。一方面，每個邊緣中心都配備了許多不同的邊緣移動設備，即資源。另一方面，EP在日程安排中起著重要的作用。主要功能如下：首先，根據處理歷史數據方面的預測，為未來需求儲備資源。其次，以獲取更多利潤為動機，匹配任務和邊緣移動設備，然后將這些任務盡可能分配給與不同邊緣中心關聯的相關邊緣移動設備。最后，它將超出其能力的任務發送到云上進行處理，并為這項工作付費。相應地，云處理EP交付的任務并從中獲利。

圖1 邊緣環境下計算密集型應用的任務調度框架Fig.1 Task scheduling framework for computing-intensive applications in edge environments

1.3 計算密集型任務調度的執行過程

當計算量和網絡資源有限時，最大限度地利用資源變得至關重要，在用戶移動過程中，進行任務調度，選擇最優的邊緣服務器為用戶提供服務，從而實現MEC系統的最低能耗，移動邊緣調度是減少時延和視頻傳播任務的延遲敏感性的重要方法，根據各種用戶參數對任務進行調度，如到達時間、系統負載、執行時間和截止日期，在邊緣環境中任務調度算法的目的是在用戶和虛擬機之間，找到一個最優映射，以使在滿足用戶的需求前提下，提高邊緣云的使用效率以及降低能耗。圖2描述了邊緣環境下計算密集型任務調度的執行過程。

圖2 邊緣環境下計算密集型任務調度的執行過程Fig.2 Execution process of computing-intensive task scheduling in edge environments

在該過程中假設有K個移動終端，每個移動終端上有一個具有一定優先級的待處理任務，即共有K個待處理的任務。用T={T1,T2,T3,…,Tn,…,Tk}表示K個待執行計算任務調度到邊緣服務器端進行處理，要將K個任務分配給n個邊緣資源節點，資源節點用S={S1,S2,S3,…,Sn}表示，當移動端發送任務請求，調度策略通過考慮QoS資源監控的信息，將任務分配給匹配的邊緣端資源節點來完成任務調度。

1.4 計算密集型任務調度的應用場景

邊緣計算調度的應用不僅可以克服現有主機網絡的限制，而且在實現調度任務分配方面發揮了重要的作用。目前對綠色IoV的研究主要集中在電池供電的RSU或電動汽車的能量管理上。由于傳感器和智能車輛的快速發展，車聯網（IoV）正在成為智能交通系統的基礎技術，要求提高道路車輛的機動性和安全性。圖3描述了邊緣環境下計算密集型任務調度的應用場景。

圖3中，IoV支持各種通信模式，例如車輛到車輛（V2V）、車輛到基礎設施（V2I）和車輛到傳感器（V2S），車輛連接到匹配的MEC服務器的RSU，以執行實時或重要的計算任務，車輛和終端等服務用戶能夠從位于用戶附近的基站（BS）的邊緣計算服務器（ECS）訪問計算和存儲服務，當車輛用戶發送任務由基站進行調度，調度算法決定將計算任務調度到基站節點端的服務隊列或車輛的服務隊列中，然后由邊緣服務器對任務實施調度策略，最終返回到用戶。通過將服務從核心網絡推送到邊緣網絡，這大大減少了網絡延遲。目前，現有的大多數工作僅僅考慮車輛之間的調度，而忽略了RSUs之間的對應關系。如何利用有限的RSU數量來應對不斷增長的車輛交通需求是一個非常具有挑戰性的問題。

圖3 邊緣環境下計算密集型任務調度的應用場景Fig.3 Application scenarios of computing-intensive task scheduling in edge environments

1.5 計算密集型任務調度的性能指標

邊緣計算中調度的評價標準影響調度技術的設計和方法，大多數任務調度技術是多目標的，在邊緣計算調度中時間和成本大多都是一起考慮的，為了達到更好的調度效能，需要依賴于時間、成本、可靠性、能耗、資源利用率以及負載均衡等不同的指標：

（1）時間：包括最大完成時間、總執行時間、截止時間以及等待時間。在邊緣計算環境下任務調度中，其中完成時間是任務從提交到執行完成的整個調度時間；執行時間是指資源被分配到完成的時間；截止時間是指任務要求的最終完成時間，等待時間是任務執行開始到提交之間的時間。

（2）成本：任務執行產生的成本包括計算成本、數據傳輸成本以及用戶為使用邊緣計算平臺向供應商所付出的費用。

（3）能耗：指應用程序在處理計算設備內的數據（計算能量）和通過可靠的網絡傳輸數據（傳輸能量）期間消耗的能量。

（4）資源利用率：計算設備的資源利用率取決于重新調度和處理實時應用程序的資源數量，是指用戶在進行邊緣調度的過程所占用邊緣環境中的CPU、存儲、內存和應用各類的軟硬件的資源利用率。

（5）負載均衡：是指用戶請求的邊緣任務在不同的虛擬機、虛擬機不同的節點上分配的調度。負載均衡不僅可以改善資源的利用率，還可以通過低載資源的合并以及遷移能夠降低能耗。

（6）可靠性：是指任務執行的可靠性，確保在計劃中選擇的資源并可能會完成為其安排的任務。任務執行失敗通常通過重新啟動和復制任務來處理。任務的可靠性執行可以降低時間和計算資源的浪費。

2 邊緣計算環境下計算密集型任務調度技術現狀

邊緣計算調度策略的根本目的是提高資源的利用率，降低負載均衡以及能耗，進而提高用戶體驗。本文為了增加可讀性、可靠性，根據優化目標的不同，將目前的調度優化策略分為：時間和成本的優化調度策略、能耗和資源利用率的優化調度策略、負載均衡和吞吐量的優化調度策略；這些將有助于邊緣計算調度領域的研究人員探索高效的調度策略，表2總結了近幾年來相關的邊緣環境下計算密集型任務調度方案。

表2 邊緣環境下計算密集型任務調度方案總結Table 2 Summary of computing-intensive task scheduling in edge environments

2.1 時間和成本的優化調度策略

在網絡的邊緣部署使用合適的調度策略不僅可以降低云邊端的計算復雜度，并且可以延長用戶主機設備的壽命。其中，時間和成本是影響用戶體驗的關鍵指標之一，因此綜合考慮時間和成本是設計高效調度策略的重要參考因素。

針對如何提高在作業分配過程中數據的處理能力，文獻[13]總體技術路線是基于成本的作業調度。該方法的優點是可以縮短提交作業的相應時間，并考慮了抖動因素以改善QoS和網絡狀態，缺點是在計算成本的過程中忽略了由等待所產生的成本以及數據返回產生的成本。文獻[14]使用了新的動態調度技術，該技術隨著時間的推移管理云資源，以處理工作流中的數據速度變化，同時保持用戶定義的實時數據分析要求并最小化執行成本，減少執行時間。

針對如何解決多QoS的優化約束問題，文獻[15]基于混合蜘蛛猴優化算法解決任務調度問題。總體在滿足預算和期限約束的同時，優化了完工時間和成本。文獻[16]利用遺傳算法（genetic algorithm，GA）將異構任務調度到異構處理器上的調度策略，以減少總執行時間。文獻[17]研究了在結合邊緣處理和集中式云處理的云邊協作架構適用于流媒體的放置緩存調度，并基于鄰域搜索的緩存感知調度模型，如圖4所示。具體執行流程為：首先，樸素貝葉斯理論將工作分為三類。其次，根據不同作業類型的操作，為節點分配不同的資源來執行不同的作業，并監控作業執行情況以調整資源。最后，采用緩存感知方法延遲調度作業，并將作業調度到滿足緩存局部性的節點。根據鄰域搜索結果，調度不滿足節點局部性的作業在具有相似能力的節點上執行。該方法有效地減少內容傳輸延遲，縮短作業執行時間，提高云數據中心的處理能力。

圖4 邊緣環境下基于鄰域搜索的緩存感知調度模型Fig.4 Cache-aware scheduling model based on neighborhood search in edge environment

針對多目標優化和工作流任務調度問題，文獻[18]在云工作流應用中生成帕累托最優解的進化多目標優化算法，并將其用于多目標調度問題。該策略的優點在于根據混沌理論在云環境下通過貪婪算法和使用隨機數來提高搜索性能，與其他算法相比，該算法具有更好的收斂性和更均勻的節間距離，并解決了原算法總是陷入局部最優的問題。文獻[19]應用了基于模糊的任務調度，該方法的優勢是在能量消耗方面優于微遺傳算法，其最終的目標是在高負載條件下，在總執行時間、最大完工時間、不平衡度和安全價值等方面都優于其他同類調度方法。文獻[20]定義了云邊緣網絡體系結構中任務調度的最小化延遲優化問題。將該問題描述為一個馬爾可夫決策過程，通過無模型DRL算法來訓練系統的狀態，以解決云服務器存在長延遲和巨大的帶寬需求問題。在該過程中，各優化目標被量化為：

2.2 能耗和資源利用率的優化調度策略

在網絡的邊緣部署調度不僅可以降低服務器端的能耗和并且還可以降低服務器資源枯竭和其他服務器浪費的情況。能源和資源利用率是影響用戶體驗的關鍵指標之一，因此綜合考慮能耗和資源利用率是設計高效調度策略的重要參考因素。

針對克服調度優化問題以獲取更高的資源利用率為目標，文獻[21]對工作流調度問題進行了研究，提出了基于服務質量的資源分配和調度，利用基于群體的蟻群優化提供更可預測的結果。實驗結果已經與其他策略進行了比較，結果表明該策略較其他算法策略在能耗和資源利率方面有所提高。文獻[22]利用一種基于訂單級需求的實時邊緣調度模型，該模型考慮了訂單的實時插入，在滿足單個客戶需求的同時實時插入到貨單。所提策略在顧客滿意度等訂單級指標上具有顯著優勢，在資源利用率、能耗和完工時間等車間級指標上表現較好。文獻[23]解決了以節能的方式在一組專用私有軟件定義的廣域網連接的數據中心上調度由數據驅動的工業工作流應用程序的問題，并同時管理云提供商收入的權衡。與基于成本的工作流調度方法相比，該文獻提出的方法可以將工業工作流執行的綠色能源利用率提高3倍，并降低了能耗。

針對為給定的輸入任務找到最優的資源，文獻[24]引入了一種能量-最大完工時間多目標優化調度策略，目的是找到這些沖突的目標之間的折衷降低能源消耗和最大完工時間，它分兩個階段工作。首先，引入加權雙目標代價函數。其次，通過應用期限約束的頻率縮放來進一步減少能源消耗。建議的工作確保在建議的期限內完成工作流應用，同時也減少了能源消耗。文獻[25]通過考慮多云的完工時間、負載均衡、資源利用率和成本等參數來改善任務調度行為。該方法結合了遺傳算法和電搜索算法的優點。遺傳算法提供最佳局部最優解，而電搜索算法提供最佳全局最優解。由實驗結果來看，該算法優于混合粒子群優化算法、遺傳算法、專家系統和蟻群算法等現有調度算法。

2.3 負載均衡和吞吐量的優化調度策略

邊緣計算環境下邊緣節點間資源差距過大且任務分配的負載不均衡，平衡負載可以降低總體能耗和防止某個邊緣云超載，負載均衡和吞吐量是影響用戶體驗的關鍵指標之一，因此綜合考慮負載均衡和吞吐量是設計高效調度策略的重要參考因素。

為了克服現有關于負載均衡的困難，優化動態資源調度。在文獻[26]中利用基于端口的源路由地址的特性和胖樹拓撲的規律性，設計了一種極其簡單的路由機制，該方法適用于云數據中心網絡和邊緣計算，可以降低交換機的復雜度和整個網絡的功耗，顯著減少了完成時間，提高了平均吞吐量，并在服務器上實現負載均衡。文獻[27]通過基站學習和交換信息獲得的環境知識用于分布式資源塊分配。該資源分配方案可以在較短的學習時間內獲得最優的資源分配策略，并可以根據不同服務的延遲要求隨時終止學習過程。與傳統的資源分配方案相比，它能有效提高系統吞吐量。文獻[28]使用量子啟發的二進制混沌群算法來調度多處理器系統中的任務，以實現負載的均勻分散。充分的負載平衡和高效的調度機制增強了整體性能，并顯著提高了服務質量指標，如計算系統的吞吐量、資源利用率、可擴展性、可靠性和響應時間，較鳥群優化、改進粒子群優化、JAYA和標準SSA（二進制數相乘）算法在性能方面有所提高。文獻[29]基于粒子群優化的多目標調度，用于對大量任務進行優化分配。該算法旨在通過調度任務來減少每個粒子上的剩余工作量。在利用粒子群優化（particle swarm optimization，PSO）調度算法得到每個集群的問題答案之后，IPSO嘗試調整資源上的負載。該算法減少了所有任務的完成時間，同時還平衡了框架負載，提高了整個云階段的詳盡度。

針對考慮請求調度的資源故障率問題，以便為所請求的服務提供可靠性，文獻[30]引入了一種可靠的負載平衡服務調度方法，用于將客戶的請求分配給云-霧環境的資源。通過將請求任務按實時性、重要性和時效性進行分類，在分配請求時考慮了資源之間的負載均衡，該方法可以將客戶的請求任務分布在不同的計算資源上，具有高度的負載平衡。文獻[31]基于深度強化學習（DRL）的服務水平協議約束下的動態負載平衡任務調度策略。使用DRL方法為任務選擇合適的虛擬機，然后確定在選定的虛擬機上執行任務是否違反服務級別協議。如果違反了服務水平協議，任務將被拒絕，并反饋DRL訓練的負面獎勵；否則，接收并執行任務，并在任務執行后根據虛擬機負載的平衡反饋獎勵。該策略在平衡虛擬機負載、降低任務拒絕率、提高系統吞吐量，提高云計算服務整體水平方面表現最佳。

從以上優化目標的角度出發，通過對目前邊緣計算調度的分析和對比可知，將用戶請求的任務調度到邊緣服務器端處理確實在一定程度上提高了網絡的性能和用戶體驗。但是目前仍然面臨一系列的問題：如用戶請求任務的多樣性對調度策略有嚴重影響，如何準確預測用戶的任務分類來最大化調度的資源利用率是一項復雜的任務；此外，用戶不愿為了提高網絡性能而消耗他們的時間和成本，所以用戶在云端執行任務調度，以利用D2D通信是困難的；因為對于調度任務的分類和特性難以確定，所以設計的調度策略應該能夠準確觀察用戶任務的特性、用戶任務請求的方式、移動性、網絡狀態。因此，綜合考慮邊緣設備的移動性、異構邊緣計算服務器的資源以及任務的計算需求，可以利用深度強化學習以及來跨層的方式解決調度任務處理速度，縮短任務超時時間。因為深度學習具有生物相關性和學習自主性，可以通過嘗試錯誤將狀態和動作與環境進行最佳匹配，以獲得最大的資源利用率，且未來邊緣計算調度技術希望利用智能的調度機制來最大限度地提高網絡性能。

3 邊緣計算環境下面向5G的計算密集型任務調度的發展趨勢

第1章和第2章所描述的調度技術主要都是應用在4G傳統的MEC網絡。然而5G的應用背景下，通過在云上部署強大的計算和存儲能力，可以有效地處理物聯網計算密集型應用產生的數據，從而確保物聯網應用向最終用戶提供有效的服務。本章將分析邊緣環境下面向計算密集型應用的任務調度技術策略，目前正在發展的幾個熱點方向，如邊緣環境下基于SND下的調度策略，基于深度強化學習的調度策略，以及在車聯網環境中的跨層調度策略的實施。

3.1 面向5G邊緣環境下基于SDN的計算密集型數據包調度策略

邊緣計算通過提供分布式處理能力來支持移動計算和物聯網技術分布式開放架構[32]。為了支持高擴展性、超低延遲、高吞吐量和可靠的數據傳輸，軟件定義網絡（SDN）被認為是合適的解決方案之一，這使得邊緣計算更加可行[33]。考慮到SDN技術通過將網絡解耦為控制平面和數據平面來實現動態、編程高效的網絡配置的特點，能夠提高邊緣服務器的性能和低延遲。SDN的這些特性和邊緣計算一起使用，可以實現各種附加功能以及性能的提升。使用OpenFlow協議，SDN控制器可以控制底層網絡組件[34-35]。圖5描述了邊緣環境下基于SDN的邊緣計算架構，其中架構中主要包括網絡應用、MEC系統水平、MEC主機水平、網絡層。在SDN支持的 邊緣架構中，MECs部署在邊緣接入網中，減少了接入終端與計算資源和網絡資源的距離，增加了終端對資源的訪問[36-37]。

圖5 邊緣環境下基于SDN的邊緣計算架構Fig.5 SDN-based edge computing architecture in edge environment

圖6描述了基于SDN的計算密集型數據包調度方案。當邊緣中心接收到緊急數據，它會像其他正常數據包一樣遵循一般的OpenFlow操作。邊緣中心將緊急數據以地址為源地址打包，發送到目的地。同時發送packet-in消息，通知控制器發生緊急報文，控制器收到入包消息后，檢查并發送一個出包消息。接收分組輸出消息的邊緣中心更改或添加接收到的消息的流表，并傳送到合適的輸出端口。在基于OpenFlow的功能之后，在邊緣中心檢查數據，來確定是將入隊的數據轉移到優先級隊列還是普通隊列。在工業物聯網環境產生的數據中，假設應急數據只用EQ處理，其他所有情況如周期性傳感數據都用NQ處理。傳入數據包由M/G/1排隊模型處理，調度模型側重于網絡延遲的排隊延遲，該方案從數據包的角度出發，通過分析用戶的數據包的緊急性優化調度策略，并將SDN合并到MEC邊緣中，以最大化命中率，最小化傳輸能耗為優化目標。

圖6 基于SDN的計算密集型數據包調度方案Fig.6 Computing-intensive packet scheduling scheme based on SDN

圖7描述了不同調度策略下的任務平均時間響應情況，在單個服務器中，資源利率ρ表示為ρ=λ×c×Sˉ，λ表示為，其中p為任務的優先級，Sˉ指處理一個數據包所需的服務時間，在計算平均等待時間時，將到達率λ的方差設為0.01～0.09，從圖中可以看出，當系統利用率為低情況時，可以更快地處理應急數據，反之處理應急數據的時間更長。基于SDN的邊緣調度策略具有的性能優于現有的基于優先級（FCFS）的調度方法。SDN下的任務調度策略不同之處在于：不同于現有的基于優先級的技術，提出的方案使用兩個隊列而不是多個隊列來管理邊緣計算服務器的資源；為了減少傳輸延遲，邊緣計算服務器和邊緣計算主機采用SDN概念。

圖7 不同調度策略下的任務平均時間響應情況Fig.7 Average time response of tasks under different scheduling strategies

3.2 基于深度強化學習的計算密集型任務調度策略

為了解決邊緣環境中任務如何進行調度的問題，以及用戶請求任務密集和資源的合理分配，啟發式算法目前在任務調度問題方面應用研究廣泛，基本原型如蟻群算法（ant colony optimization，ACO）、粒子群優化（particle swarm optimization，PSO）、遺傳算法（genetic algorithm，GA）等。這類算法可在約束條件下尋找到符合條件的可行解，但是由于無法預計可行解與最優解之間的偏差，收斂速度比較慢，在求解過程中往往陷入局部最優解，較難滿足低時延的任務要求。因此在此背景下，利用強化學習[38]方法優秀的決策能力來解決復雜邊緣環境中的調度問題，通過不斷矯正可行解和更優解的偏差，可以加快收斂速度。但是由于自身的局限性，它無法處理高維和連續性問題。深度學習方法側重于感知和輸入的表達，善于發現數據的特征。由于深度學習可以彌補強化學習的缺點，因此深度強化學習（deep reinforcement learning，DRL）利用深度神經網絡捕捉環境特征的能力和RL的決策能力來解決復雜的系統控制問題[39]，并且可以使用邊緣節點作為智能代理學習調度策略，不需要全局有關環境的信息。

邊緣云任務調度結合深度強化學習的內容，并按照任務調度模型構建合理的部署的方法，相比于傳統的方法[40]更有優勢。邊緣環境下基于深度強化學習的任務調度模型如圖8所示，當用戶發送視頻任務請求時，調度決策器根據目前的邊緣計算系統環境狀態即時回報的結果，使用強化學習模型通過大量的學習訓練，使得調度決策器按照經驗策略將視頻任務接入到最合適的服務器。并使用深度卷積神經網絡進行確定性策略梯度進行神經網絡訓練，最后根據服務器的負載狀態信息，通過視頻的遷移策略，來執行新的任務請求。

圖8 邊緣環境下基于深度強化學習的任務調度模型Fig.8 Task scheduling model based on deep reinforcement learning in edge environments

強化學習主要用到的是行為策略選擇，定義函數μ，通過使用卷積神經網絡對μ函數進行模擬，該網絡即為策略網絡，如果都按照策略μ選擇動作，能夠產生Q值，該值為期望值。通過使用卷積神經網絡對Q函數進行模擬，在訓練的過程中，采用目標網絡方法，建立策略網絡和Q網絡來計算目標值，然后通過比例緩慢更新網絡。通過該學習方法，使學習過程更加穩定，收斂更有保障。圖9描述了不同負載情況下的任務處理時間以及算法的收斂性比較。

圖9 不同策略任務處理時間和算法收斂性比較Fig.9 Comparison of processing time and algorithm convergence of different strategy tasks

從圖9可以看出其他算法與深度強化學習調度策略的運行時間，無論是低負載還是高負載，深度學習算法的運行時間均優于DTAMS（dynamic threshold allocated migration strategy，DTAMS）以及PSO算法，對于平均運行時間縮短了54.54%。這是因為在用戶請求訪問的過程中，需要通過DTAMS算法不斷更新會話分配閾值，計算量大。為了找到最優解，采用的深度強化學習方法只需要通過訓練好的策略網絡進行調度決策，計算復雜度較低，提高了調度效率。幾種算法的收斂曲線如圖9（b）所示。深度強化學習算法以比其他兩種算法更快的速度實現了最優策略。此外，隨著迭代時間步長的增加，該算法比其他算法有更高的回報，這表明該算法是有優勢的。

3.3 計算資源協同的跨層任務調度策略

車聯網（internet of vehicles，IoV）是物聯網在汽車行業的典型應用，被認為是一種具有巨大潛力的下一代智能交通系統，由于每個邊緣節點的計算和存儲資源有限，以及物聯網設備產生的數據規模龐大，即使在網絡邊緣節點之間實施資源調度，也無法滿足物聯網的計算需求。因此，有必要實施跨層資源調度（cross-layer task scheduling，CLTS），利用云中的資源來補充邊緣節點的需求，有效解決邊緣計算能力不足的問題。跨層資源調度方法[41]，可以實現物聯網應用完成時間、資源利用率和能耗的聯合優化。基于特征分析的結果，設計了一個新的跨層云計算系統多計算機任務調度框架，該框架具有動態定制的能力，通過該調度策略，跨層云計算系統中的計算機任務可以動態選擇合適的算法，更有效地利用資源。圖10描述了5G邊緣環境下計算資源協同的跨層任務調度過程，具體步驟為：

圖10 5G邊緣環境下計算資源協同的跨層任務調度Fig.10 Cross-layer task scheduling of computing resource coordination in 5G edge environment

步驟1將不同物聯網服務和應用的需求分解為不同的計算機任務類型，其中任務之間的關系由有向圖描述。

步驟2任務分析器分析計算機任務的特征，并將各種標簽賦予它們，包括任務調度目標、任務類型等。

步驟3任務分析器將任務快照分發給調度管理目標（SMO）分析器和任務調度器。此外，任務也被分配到任務調度器。

步驟4 SMO分析器可以區分每個任務目標之間的差異。調度管理目標分析器決策可以從任務性質、資源狀態和系統層次結構三個方面進行推導。調度管理目標分析器創建相應的目標控制器窗體。目標控制器根據目標控制器窗體從目標池中選擇目標。

步驟5目標控制器監控任務調度器，以確保每個任務的輸出都是可接受的。

步驟6任務調度器使用算法池中的算法執行算法功能。然后，它將來自資源監視器的信息和相關算法的結果發送給資源調度器。

步驟7資源調度器根據任務調度器的算法結果為這些任務分配資源。

其中通過考慮完成時間、資源利用率和能耗的聯合優化指標模型，因此，任務的完成時間分為任務轉移時間DTm、任務完成時間TEm和結果返回時間DFm，由TCm=DTm+TEm+DFm表示。利用一系列方法推導出邊緣節點的資源利用率AU。因此，綜合要解決的問題定義為：

將θ(tnm)表示為一個二元變量，旨在估計tnm是否部署在enn上。所有邊緣節點的能量消耗通過以下公式計算：ES=BCS+FCS+NCS,BCS代表邊緣節點的基本運行能耗，FCS代表滿載VMs的能耗，NCS代表空載VMs的能耗。圖11描述了不同策略在不同任務數量下的性能，從中可以看出跨層資源調度（CLTS）相較于PSO和LC（least-connection scheduling）在任務數量大的情況下平均作業完成時間和平均消耗總能耗最優，在處理大量任務的作業時跨層資源調度相比較PSO和LC算法具有一定的優勢。

圖11 不同策略在不同任務數量下的性能指標比較Fig.11 Performance comparison of different strategies under different number of tasks

4 問題與挑戰

4.1 容錯調度機制

由于移動用戶的移動性和復雜的云環境，在移動應用的執行過程中可能會出現故障和不確定性。在執行過程中，可能會違反資源和應用程序之間的契約。因此，容錯動態調度對于在線修改是必要的，以處理執行過程中的故障和不確定性，特別是在邊緣計算環境中。在此基礎上，一種基于分層移動邊緣云架構的容錯動態調度方法被研究。它旨在為移動應用程序執行期間提供動態和優化的調度策略。容錯調度已經在網格、多處理器系統和一般云中進行了研究。移動云環境下的容錯調度問題很少受到關注。在這些容錯技術中，重疊技術是最流行的一種。此外，還有兩個重疊的模型：主備份（表示為PB）模型和備份（表示為BB）模型。在PB模型中，允許主拷貝與其他后拷貝重疊。在BB模式中，允許不同的備份副本相互重疊[42]。除了重疊技術，還有其他容錯調度技術。文獻[43]針對異構分布式嵌入式系統上的可靠并行應用，提出了兩種節能容錯調度算法。通過結合重提交和復制技術，文獻[44]提出了一種容錯工作流調度方法，其中提出了一種在線預留調整機制來調整容錯策略和一些未執行任務的子線索。文獻[45]使用一種不確定感知的容錯調度方法來處理執行過程中的不確定性，從而糾正延遲。文獻[46]研究了云計算中期限約束任務調度容錯策略的建模與分析。由于，用戶請求的多樣性可能需要不同的資源類型，例如VM、帶寬和存儲。因此，保持動態制定容錯策略的能力至關重要，可用于控制任務的容錯模式（主動或被動），從而滿足云應用的可靠性和實時性要求。邊緣云應用的容錯過程可能涉及多個資源，資源調度的并發性和不確定性將增加模型驗證的復雜性。很難證明所提出的方法能夠提供關于容錯過程行為的模型的可靠性和完整性檢查。并且，邊緣云計算的故障非常復雜，相關故障可能滿足概率分布[47]。此外，如何提供能夠滿足所需QoS的容錯調度，對于邊緣云應用程序也是一個具有挑戰性的問題。

4.2 動態微服務調度

為邊緣計算平臺設計一種高效、最優的動態微服務調度機制是一項具有挑戰性的工作，因為每個微服務都有異構的資源需求來執行邊緣用戶的可用任務。除此之外，每個邊緣用戶都有嚴格的延遲要求，以從微服務獲取可執行結果。在邊緣平臺中，邊緣服務器啟動多個微服務以滿足邊緣用戶的需求。于是動態微服務調度被研究，在微服務之間調度任務，最大化網絡吞吐量和QoS[48]。調度框架應該考慮需要執行的可用任務的數量，動態地將微服務從頂部隊列移至底部隊列。關鍵的微服務被認為是在頂級隊列中執行的，因此它應該比正常的微服務具有更高的優先級，動態微服務調度框架的主要目標是最小化平均服務質量，需要優化服務質量，以應對底層網絡條件和基礎設施的突然變化。因此，如此快速的增長和發展導致了面向微服務的邊緣計算平臺的出現[49-52]。并且在微服務之間分配公平的資源，可以提高網絡中的資源利用率。微服務的最新進展，文獻[53]中的微服務多樣性的服務器優化方案，試圖找出最佳卸載解決方案，以最大限度地減少總體延遲。文獻[54]設計了一種異構云邊緣環境下的微服務調度模型，其新穎之處在于面向微服務的方法。文獻[55]設計了基于微服務的三層性能模型應用程序，制定基于微服務的應用程序工作流調度問題。文獻[56]基于模型的強化學習方案，用于科學工作流上的微服務資源分配。文獻[57]應用了微服務的服務布局方案，并設計了一種自動擴展資源的算法。文獻[58]在基于強化學習的邊緣平臺延遲感知微服務協調方案。以上文獻對比之后發現，微服務調度框架在總網絡延遲、平均價格、滿意度、能耗率、故障率和網絡吞吐量方面顯著提高了性能指標。但是，其缺點是如何設計高效并且最優的動態服務調度機制是一個難點。

4.3 人群感知調度

人群感知有效地解決了大多數數據驅動應用面臨的海量數據采集困境。移動人群感知通過無處不在的智能終端和網絡接入，將感知任務從集中式平臺跨時空維度遷移到分布式計算終端[59]，為大規模高精度實時感知問題提供了新思路[60]。由于任務調度過程中需要考慮數據的冗余性和協同性，并且網絡環境的不確定性、用戶的多樣性、任務需求的多樣性等因素會嚴重影響感知。因此，當傳感器分配的任務不能滿足不同任務的質量要求時，移動人群感知應具有良好的適應性，以便快速適應各種異構物理傳感器的部署[61]。文獻[62]構建了一個基于攝影的移動人群感知系統。在選擇參與者時，參與者與監控對象之間的距離是影響任務分配的主要因素之一，因為道路上的車輛需要及時跟蹤。文獻[63]利用總線載波覆蓋范圍大和傳感器節點自主聚合的優勢進行任務分配，并通過實驗驗證了分配的準確性。文獻[64]提出了一種新的任務分配框架，通過將現有的任務序列與用戶的移動規律盡可能地對齊。將傳統的任務分配問題轉化為滿足資源效率和感知質量的模式匹配問題。文獻[65]是在基于任務異質性興趣點（如不同的空間-時間需求）的移動性預測模型。它獲得傳感器完成任務的可能性。實驗結果表明，該框架具有較好的效率。文獻[66]對任務的地理位置進行集群，將一組傳感器分配給一組任務，同時，最大限度地提高了任務的服務質量，縮短了完成任務的時間。目前，對不同階段的響應時延和運行成本進行了深入分析，并設計了分階段調度算法，共同優化總時延和成本。在混合人群感知系統中[67]，有多種類型的資源可用于執行人群感測任務，例如像云服務器這樣的云資源，邊緣設備和邊緣服務器這樣的邊緣資源。最重要的問題是找到一種合適的方法在這些資源中安排任務。盡管有工作[68]已經探索了面向邊緣計算的任務卸載，但是很少有工作能夠直接應用于解決人群感知場景中的任務調度問題。當人群感知系統中處理任務調度時，有三個主要挑戰：（1）與為特定應用目的而設置的邊緣服務器不同，邊緣設備通常由個人擁有，并且這些專用設備不專用于執行傳感任務。（2）在將結果返回到云中之前，需要在邊緣設備和邊緣服務器上執行檢測任務。這種執行邏輯在邊緣使能的人群感知系統中是獨特的，其中兩種類型的資源上的任務調度是高度耦合的。（3）此外，大多數人群感應應用程序必須循環執行任務。任務調度的長期目標使得這個問題更具挑戰性。

4.4 安全和隱私

與傳統云計算相比，邊緣節點更接近用戶設備，并且邊緣計算可以提供更好的隱私保護措施。傳統的云調度策略中，數據的安全可以通過加密以及用戶和調度節點的認證來保證。隱私保護和數據安全是邊緣云工作流調度中需要解決的重要問題。許多黑客試圖在用戶中心或者邊緣云卸載和處理任務時中斷或竊取數據。安全和隱私是一套基于控制的技術和策略，旨在保護敏感信息、數據、應用程序和基礎架構[69]。由于分布式環境中的資源虛擬化和多樣化；在邊緣云計算中，安全成為一個復雜的過程。因此，資源監控、資源管理和資源安全已經成為云邊計算領域的突出問題。有研究人員采用離散PSO方法來解決安全威脅對工作流調度的影響[70]，在這種方法中，使用云模型來量化任務和虛擬機資源的安全性。此外，一般通過度量安全云的相似度來估計用戶對虛擬資源任務分配過程的安全性滿意度。同樣，調度策略也可以通過某種方式來保護提交的應用程序的機密和私有信息[71]。文獻[72]考慮移動邊緣計算環境下位置隱私保護的車聯網計算資源協同調度策略，以用來保護車輛用戶位置隱私泄露的問題。在文獻[73]應用多目標隱私感知工作流調度，是為了解決數據隱私保護約束下調度工作流，同時最小化云上大數據應用的執行時間和成本。文獻[74]用于物聯網任務調度的隱私體系結構，并在此基礎上提出了一種多目標算法，以最小化服務時間和服務成本。以上文獻綜合考慮了調度過程中的安全問題，但是在將來仍然需要研究移動設備的調度工作流任務所導致的額外延遲的安全問題。

5 結束語

為了全面地了解邊緣調度技術，本文重點對邊緣計算調度框架、執行過程和評價性能指標進行相關描述，對最新的任務調度策略以不同性能目標分類并進行了分析和總結。通過對比不同移動邊緣調度策略，對面向5G環境下邊緣調度技術進行研究，分析5G環境下SDN支持的邊緣計算架構并提出了面向5G環境下計算密集型任務調度優化策略，研究了基于深度強化學習的計算密集型任務調度策略以及基于5G IoV計算資源協同的跨層任務調度策略。最后，根據本文調查的調度方案，總結出了邊緣調度策略的研究挑戰。目前邊緣計算研究的重點是根據QoS需求如何將請求任務和協同資源實現最優匹配，這是實現邊緣計算技術快速發展的關鍵點之一。通過該綜述研究的領域和方法，總結出該邊緣計算調度領域的研究思路，從而為相關領域的研究人員提供參考和幫助。