陳 順，劉 剛，熊 原

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

1 邊緣計算概述

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

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

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

3）位置感知：當(dāng)邊緣網(wǎng)絡(luò)為無線網(wǎng)絡(luò)時，無論是Wi-Fi、藍(lán)牙或者蜂窩網(wǎng)絡(luò)，本地服務(wù)都可以利用低級別的信令信息來確定每個連接設(shè)備的位置。

2 任務(wù)調(diào)度方法的研究現(xiàn)狀

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

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

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

3 基于節(jié)點服務(wù)能力評價的多層級任務(wù)調(diào)度方法

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

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

在邊緣中心環(huán)境下，由于節(jié)點受網(wǎng)絡(luò)環(huán)境的影響較大，因此在執(zhí)行任務(wù)調(diào)度的時候需要考慮到節(jié)點的通信服務(wù)質(zhì)量，因為它影響到了邊緣中心和云中心的通訊交互能力以及對終端節(jié)點的服務(wù)響應(yīng)能力。而丟包率在媒體服務(wù)中尤為重要，直接影響音視頻媒體的服務(wù)質(zhì)量，所以將節(jié)點的擴(kuò)展了丟包率的通信服務(wù)質(zhì)量納入上下文元素中，對邊緣計算中心下的任務(wù)調(diào)度決策發(fā)揮了重要的作用。

2）邊緣節(jié)點服務(wù)能力評價方法，對本區(qū)域內(nèi)所有節(jié)點做出綜合服務(wù)能力評價，為任務(wù)調(diào)度做決策支撐。針對上述每項上下文元素，進(jìn)一步轉(zhuǎn)化，由上下文要素轉(zhuǎn)化為調(diào)度決策因子，針對每個調(diào)度決策因子我們定義了一項有效權(quán)值，并建立以下公式進(jìn)行服務(wù)質(zhì)量Q 的計算：

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

M’=log(M)

M’為歸一化的已分配的任務(wù)數(shù)量，代表邊緣節(jié)點當(dāng)前的負(fù)載狀態(tài)；

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

3）有中心網(wǎng)絡(luò)和無中心網(wǎng)絡(luò)的服務(wù)節(jié)點選擇算法。（1）有中心網(wǎng)絡(luò)。在有中心的網(wǎng)絡(luò)中，采用上下文集中管理模式，由中心管理節(jié)點承擔(dān)全局節(jié)點上下文信息的集中管理，當(dāng)中心管理節(jié)點接收到調(diào)度任務(wù)時，中心管理節(jié)點會根據(jù)各邊緣信息服務(wù)節(jié)點的上下文計算節(jié)點綜合服務(wù)能力的Q 值評價，并基于最小Q 值原則找到相應(yīng)的邊緣節(jié)點，將任務(wù)下達(dá)到該節(jié)點。（2）無中心網(wǎng)絡(luò)。將無中心的網(wǎng)絡(luò)轉(zhuǎn)化為準(zhǔn)中心網(wǎng)絡(luò)，即集群式區(qū)域管理，每個區(qū)域的邊緣信息服務(wù)節(jié)點，納入?yún)^(qū)域中心管理節(jié)點統(tǒng)一管理，區(qū)域中心管理節(jié)點作為準(zhǔn)中心進(jìn)行任務(wù)接入和調(diào)度。

當(dāng)某個中心管理節(jié)點接收到任務(wù)調(diào)度請求時，該中心管理節(jié)點根據(jù)當(dāng)前區(qū)域節(jié)點的上下文數(shù)據(jù)集，綜合評價本區(qū)域的平均Q 值Qav，如下式所示：

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

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

被轉(zhuǎn)移到的準(zhǔn)中心管理節(jié)點一旦接收到任務(wù)調(diào)度申請，將在本區(qū)域內(nèi)對所有邊緣節(jié)點的綜合服務(wù)能力進(jìn)行Q 值計算并計算平均值Qav，用以評估本區(qū)域邊緣節(jié)點的綜合負(fù)載狀況。如果當(dāng)前區(qū)域的Qav 大于調(diào)度轉(zhuǎn)移閥值Qtran，則隨機(jī)選取S 個周邊準(zhǔn)中心候選節(jié)點做區(qū)域負(fù)載調(diào)查。區(qū)域負(fù)載調(diào)查的方法是發(fā)送負(fù)載查詢消息到這S 個候選中心節(jié)點中的一個，并獲取Qav。

當(dāng)Qav＜Qtran 時，向其發(fā)送調(diào)度轉(zhuǎn)移申請，并由該節(jié)點安排區(qū)域內(nèi)調(diào)度，調(diào)度算法按照有中心的動態(tài)調(diào)度算法。

如果Qav＞Qtran，繼續(xù)發(fā)送負(fù)載查詢消息到下個候選節(jié)點。

當(dāng)所有節(jié)點的Qav 均大于 Qtran，那么選取Qav 最小的那個區(qū)域向其發(fā)送調(diào)度轉(zhuǎn)移申請。

采用這種算法可保證在整個邊緣網(wǎng)絡(luò)環(huán)境下，既能保持負(fù)載均衡，也能保證服務(wù)質(zhì)量，任務(wù)總能找到接近最優(yōu)處理能力的節(jié)點進(jìn)行服務(wù)處理。

4 結(jié)語

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