邊緣計算中基于節點服務能力評價的多層級任務調度方法研究

陳 順，劉 剛，熊 原

國家批準第五代移動通信網絡（5G）正式商用更加速了萬物互聯、智慧互聯、實時響應時代的到來。隨著這些技術的日漸成熟，網聯的終端設備不斷增多，需要處理的數據也呈指數級增長趨勢。同時，終端用戶也要求信息服務的質量越來越高，響應時間越來越短。這些新趨勢給傳統的云計算架構帶來了極大的挑戰。在云計算模式下，由于應用終端的計算能力和資源有限，需要將數據上傳到云中心去處理，但這些云中心與終端之間的距離往往較遠，用戶請求服務的時候往往得不到及時的響應，同時也極大的增加了云中心和網絡負載的壓力。邊緣計算正是在此背景下應運而生。

1 邊緣計算概述

邊緣計算是指在云中心和終端設備之間，更靠近用戶的一側設置一些邊緣服務節點來替代云中心的功能,由這些邊緣節點來直接處理終端產生的任務，提供相應的服務。這種方式相對于將任務提交到遠端的云中心處理，產生的傳輸時延更小，因此在很大程度上能提高任務處理的及時性。相較傳統的云計算，邊緣計算的優勢主要體現在以下幾點[1]：

1）隔離性：邊緣服務節點一般由位于本地的服務器集群組成，在運行時可以與其他網絡隔離，訪問本地資源速度更快。

2）低延遲：由于邊緣服務節點更靠近終端設備，因此終端與服務端的通信延遲大大縮小，可帶來更好的用戶體驗，也減小了線網數據，緩解了通信擁塞。

3）位置感知：當邊緣網絡為無線網絡時，無論是Wi-Fi、藍牙或者蜂窩網絡，本地服務都可以利用低級別的信令信息來確定每個連接設備的位置。

2 任務調度方法的研究現狀

邊緣計算理論的出現，解決了計算密集型與時延敏感性的任務對計算資源與響應時間兩方面的要求。但邊緣服務節點自身的資源相對于云中心是有限的,而且各邊緣服務節點之間的計算和存儲資源也不盡相同，多并發任務之間還存在資源競爭。因此邊緣計算中的任務調度方法具有舉足輕重的作用。任務調度就是使邊緣服務節點用自身有限的資源來處理更多的任務，又要保證用戶的服務體驗。

目前,邊緣計算環境下的調度問題主要圍繞以下幾方面來研究：從邊緣節點的體系結構考慮任務調度策略，如Liang T，Li Y，Gao W 等[2]提出了一種層次邊緣云的結構，可以在任務高峰時期平衡邊緣節點的負載，提高任務處理的效率，但該方法忽略了實際應用中任務處理需求的動態性。Ha K,Pillai P,Richter W 等[3]提出了一種在相關終端設備控制下，快速有效地支持時間敏感性任務的邊緣云結構，但該方法沒有將資源開銷納入評價體系中。Su 等[4]使用了PSO-HH 算法來優化邊緣云的結構參數來為任務設計一個自適應分配規則，但該算法會造成較長的運行時間，降低調度的實時性。有些學者從邊緣服務節點的負載均衡角度來考慮調度策略，如Wang 等[5]使用JLGA 算法,不但縮短了各服務器處理任務的時間,而且提高了服務器的資源利用率，但該方法沒有研究任務間的聯系與調度的動態性。Li 等[6]基于博弈論的思想提出了一種在移動終端間（Ad-Hoc 組網）進行任務轉移的策略，但未考慮任務優先級次序。有些學者從縮短任務的響應時間方面考慮調度策略，如Alicherry 等[7]提出了一種智能虛擬機布局來縮短數據傳輸時間，但這種布局需要隨著網絡和任務數量的動態變化及時調整，自適應性較差。

上述方法僅從某一個角度來考慮任務調度的研究，未能從全方位考慮各種任務調度的影響因素。在個別邊緣環境中，節點之間的計算能力和計算資源差異較大，而且處于網絡弱連接環境下，通信質量很不穩定。在這種情況下，如何綜合多方面因素，使任務調度滿足現實應用是一個非常重要的技術挑戰。因此，本文提出了一種基于節點服務能力評價的多層級任務調度方法，從邊緣節點的體系結構、負載均衡、網絡質量等方面來綜合評估任務完成效率，大大提升了邊緣節點的處理能力。

3 基于節點服務能力評價的多層級任務調度方法

基于綜合節點服務能力評價的多層級任務調度方法，是指將節點通信質量、節點運動狀況、計算能力、節點負荷等因素統一納入任務調度計算模型，將不同任務調度到最優的邊緣信息服務節點上運行，確保服務整體響應時間最短，且各節點間負載均衡，滿足邊緣受限環境下的任務快速調度的需要。本文將從節點上下文、節點服務能力和節點選擇算法3 個方面研究多層級任務調度算法。

1）把網絡節點上下文構建為一個節點上下文元素的集合，被選擇用于任務調度決策的節點上下文元素主要包括節點標識CitemI、節點負載系數CitemL、節點的通信質量CitemC。（1）節點負載系數CitemL 用節點中待執行的任務數來衡量；（2）節點的處理能力CitemP 用節點的CPU 的占用率來衡量，在邊緣信息服務節點環境下，各個節點之間存在一定的異構性，各服務節點的處理能力有可能不同；（3）通信服務質量CitemC 包括傳輸延遲RTT(Round Trip Times)和網絡傳輸丟包率PLR(Packet Loss Rate)，RTT 指從發起傳輸的節點到接收節點的網絡傳輸延遲時間，網絡傳輸丟包率PLR 指由于信道帶寬有限及網絡擁塞導致的發送數據包在到達接收端時產生包丟失的比例。

在邊緣中心環境下，由于節點受網絡環境的影響較大，因此在執行任務調度的時候需要考慮到節點的通信服務質量，因為它影響到了邊緣中心和云中心的通訊交互能力以及對終端節點的服務響應能力。而丟包率在媒體服務中尤為重要，直接影響音視頻媒體的服務質量，所以將節點的擴展了丟包率的通信服務質量納入上下文元素中，對邊緣計算中心下的任務調度決策發揮了重要的作用。

2）邊緣節點服務能力評價方法，對本區域內所有節點做出綜合服務能力評價，為任務調度做決策支撐。針對上述每項上下文元素，進一步轉化，由上下文要素轉化為調度決策因子，針對每個調度決策因子我們定義了一項有效權值，并建立以下公式進行服務質量Q 的計算：

Q=M’*k1+L*k2+C1*k3+C2*k4

M’=log(M)

M’為歸一化的已分配的任務數量，代表邊緣節點當前的負載狀態；

L 為CPU 的當前占用率，代表邊緣信息服務節點的處理能力；C1 為傳輸延遲RTT；C2 為通信丟包率PLR。k1、k2、k3、k4 為調度決策要素的加權值。因為任務數的量級以及處理器工作頻率比其他的大，所以使用對數函數對它們做歸一化處理。對于以上計算結果，本文創新性的定義了統一的QT作為閥值，當Q＜QT 時，該節點作為調度節點，將該節點加入可調度節點集合。

3）有中心網絡和無中心網絡的服務節點選擇算法。（1）有中心網絡。在有中心的網絡中，采用上下文集中管理模式，由中心管理節點承擔全局節點上下文信息的集中管理，當中心管理節點接收到調度任務時，中心管理節點會根據各邊緣信息服務節點的上下文計算節點綜合服務能力的Q 值評價，并基于最小Q 值原則找到相應的邊緣節點，將任務下達到該節點。（2）無中心網絡。將無中心的網絡轉化為準中心網絡，即集群式區域管理，每個區域的邊緣信息服務節點，納入區域中心管理節點統一管理，區域中心管理節點作為準中心進行任務接入和調度。

當某個中心管理節點接收到任務調度請求時，該中心管理節點根據當前區域節點的上下文數據集，綜合評價本區域的平均Q 值Qav，如下式所示：

Qav=Sum(Q0+…+Qi+…+Qn)/N

其中：Qi=Nodes 集合中第i 節點的Q 值。

被轉移到的準中心管理節點一旦接收到任務調度申請，將在本區域內對所有邊緣節點的綜合服務能力進行Q 值計算并計算平均值Qav，用以評估本區域邊緣節點的綜合負載狀況。如果當前區域的Qav 大于調度轉移閥值Qtran，則隨機選取S 個周邊準中心候選節點做區域負載調查。區域負載調查的方法是發送負載查詢消息到這S 個候選中心節點中的一個，并獲取Qav。

當Qav＜Qtran 時，向其發送調度轉移申請，并由該節點安排區域內調度，調度算法按照有中心的動態調度算法。

如果Qav＞Qtran，繼續發送負載查詢消息到下個候選節點。

當所有節點的Qav 均大于 Qtran，那么選取Qav 最小的那個區域向其發送調度轉移申請。

采用這種算法可保證在整個邊緣網絡環境下，既能保持負載均衡，也能保證服務質量，任務總能找到接近最優處理能力的節點進行服務處理。

4 結語

本文分析了邊緣計算環境中任務調度問題的起因,對現有的一些調度算法進行了充分的分析，針對存在問題提出了基于節點服務能力評價的多層級任務調度算法，并在湖南移動直播信息系統上進行了應用驗證，運行效果良好。后續的研究工作主要考慮在邊緣服務節點故障或網絡連接斷續的情況下，如何保證服務能夠順利遷移到正常節點上，并能恢復故障前或斷連之前的狀態。