邊云協同計算中基于預測的資源部署與任務調度優化

蘇命峰 王國軍 李仁發

1(中南大學計算機學院 長沙 410083) 2(湖南商務職業技術學院商務信息技術學院 長沙 410205) 3(廣州大學計算機科學與網絡工程學院 廣州 510006) 4(湖南大學信息科學與工程學院 長沙 410082) (sumingfeng@csu.edu.cn)

云計算、物聯網、車聯網、智能電網等技術迅速發展，泛在化、普適化、智能化終端廣泛應用，虛擬現實、增強現實、無人駕駛、遠程醫療、動態內容交付等新型網絡應用對網絡和計算的要求越來越高，傳統數據、存儲、處理集中的云計算模式面臨新挑戰，出現了霧計算[1]、透明計算[2]、邊緣計算[3]、移動邊緣計算[4]等新型網絡計算模式.受分布式計算啟發，邊云協同計算將云計算能力擴展到邊緣設備，聚合云計算與邊緣計算各自優勢，進行網絡高速傳輸、資源高效分發、任務快速卸載，強化云、邊數據協同處理，可以有效減少數據處理延遲，提高系統可擴展性，提升系統服務效應.

和人類生活相關的數據很多具有季節等時空特征[5]，在時空維度具有顯性或隱性的周期性、趨勢性等信息，可以對數據變化進行有效預測[6].在邊云協同計算中，借助云服務中心的海量計算能力對端任務的變化趨勢進行預測，將預測結果指導邊緣層服務器任務運行所需資源的部署，促進資源的高效利用.在邊緣層服務器考慮用戶與服務供應商需求權衡多個目標優化任務調度，以提升用戶服務體驗，提高服務供應商整體效益.

為此，本文研究邊云協同計算中使用任務預測的資源部署與任務調度優化，主要貢獻有3個方面：

1) 提出一種基于任務預測的資源部署算法，在云服務中心從橫向和縱向2個時間維度對任務進行綜合預測，優化部署邊緣服務器的任務運行所需資源，提高平均用戶任務命中率；

2) 提出一種基于帕累托優化的任務調度算法，面向用戶和服務供應商，在邊緣服務器對用戶服務質量和系統服務效應這2個目標進行帕累托改進，以優化任務調度；

3) 提出一種邊云協同計算框架，搭建實驗環境，考慮不同的用戶規模和Zipf分布參數α影響，從用戶平均服務完成時間、系統整體服務效應度、總任務延遲率等評估分析任務調度算法.

1 相關工作

“互聯網+”“智能+”技術快速發展，以網絡為媒介，衍生多態網絡應用.面對動態、多樣、大量的用戶服務請求，傳統云計算利用虛擬化技術聚集高性能硬件設備，提供集中式的數據計算處理，依托互聯網絡實現任務按需共享[7].為了提升用戶服務質量，云計算需要減少任務完成時間.文獻[8]在分布式集群中使用強化學習和神經網絡根據特定工作負載設計調度算法，高效調度數據處理作業以最小化平均作業完成時間.文獻[9]基于工作預測提出結合數據放置與計算優化的調度方法，減少跨機架的數據傳輸以降低工作完成時間.文獻[10]預測集群中心的尾延遲(stragglers)，借助副本機制，考慮數據位置、任務執行時間、任務相互依賴關系在集中和分散式調度中減少任務延遲.文獻[11-13]測度云與客戶端之間的網絡通信，通過提前部署虛擬機映像、預先啟動配置實例、將應用程序分解為若干輕量級小粒度服務、增加冗余備份等為用戶提供低延遲服務.

為了提升系統服務效應，云計算需要提高資源利用率，降低系統成本.文獻[14]在公共IaaS(infra-structure as a service)平臺提出一種新的群集調度程序Stratus，動態分配虛擬機實例以提高資源利用率和降低成本.文獻[15]在移動云計算中提出一種基于改進遺傳算法的任務聯合執行策略，減少系統整體能耗.文獻[16-17]設計一種服務質量感知任務管理方法和輕量級云管理方法，利用深度強化學習減少共享資源爭用防止交互任務調度，在保證服務質量(quality of service, QoS)的同時降低數據中心能耗.文獻[18]提出一個基于開放計算語言的異構系統優化框架，利用GPU和FPGA(field programmable gate array)加速器在保障數據中心總體吞吐量的情況下提高能耗均衡性.

數據集中處理的云計算模式提供交互迅速、綠色高效的多樣化應用服務面臨新挑戰.邊緣計算將任務部分或全部卸載到邊緣計算服務器，將計算能力延伸到邊緣層[19-20]，可減少數據處理延遲.文獻[21]考慮計算和通信提出一種多cloudlet服務器環境下最小化服務延遲的方法，將用戶無法運行的任務卸載到網絡邊緣cloudlet服務器，通過虛擬機遷移、傳輸功率控制來降低任務的處理延遲和傳輸延遲.文獻[22]提出一種兼顧移動執行CPU周期頻率和卸載發射功率的Lyapunov在線算法，考慮移動邊緣計算的執行延遲、任務失敗執行成本、移動設備電池容量，漸進優化計算密集型工作負載提升用戶體驗.文獻[23]利用混合整數非線性規劃方法優化任務派遣和資源分配，解決移動邊緣計算超密集網絡任務卸載，在考慮設備電池壽命前提下最大限度減少延遲.文獻[24]提出一個在線拍賣的激勵機制，將邊緣用戶任務卸載到相鄰移動設備以滿足低延遲需求.

為提升用戶服務質量與系統服務效應，邊緣計算需要考慮任務卸載、網絡負載、資源分配、傳輸延遲等[25-27].文獻[28]提出一種單變量搜索技術的局部最優算法，在計算卸載中引入動態電壓縮放技術，利用變量替換技術尋求最小化移動能耗和應用程序執行延遲的最優解.文獻[29]提出一個移動設備到多個邊緣設備的任務卸載框架，考慮固定和彈性2種移動設備CPU頻率基于半定松弛逼近方法改善任務執行延遲和設備能量消耗.文獻[30]提出一種能量感知的計算卸載方案，在能量和延遲受限情況下優化通信資源和計算資源分配，通過迭代搜索算法尋找計算卸載與資源分配的混合非線性整數最優解.文獻[31]提出一個聯合接入點(access point, AP)能量傳輸消耗、CPU處理頻率、用戶卸載文件大小、用戶時間分配的最優資源分配方案，考慮計算和無線功率傳輸取得用戶個體計算延遲約束下的最小化AP總能耗.文獻[32]在用戶設備資源受限的移動邊緣計算環境下基于代碼分區卸載提出一種分散卸載策略，優化任務的執行位置、CPU頻率、傳輸功率，最小化應用程序執行時間和能耗開銷.

由此，將云計算能力擴展到邊緣設備提出邊云協同計算框架，面向用戶和服務供應商研究邊云協同計算環境下基于任務預測的資源部署與任務調度優化，提升用戶服務質量和系統服務效應.

2 邊云協同計算框架與建模

2.1 邊云協同計算框架

邊云協同計算框架分為云服務層、邊緣服務層和端用戶層，通過Internet互聯互通，如圖1所示.邊云協同計算可在內容分發網絡、工業互聯網、智能家庭、智慧交通等場景應用.云服務層包括云服務中心，由若干同構或異構的計算、存儲、網絡等硬件組成.云服務中心利用虛擬化、軟件定義網絡、冗余等技術提供高性能、高可靠、可擴展的資源，以支撐用戶多樣按需服務.云服務層與邊緣服務層之間產生控制流(control flow, CF).云服務中心對任務請求進行預測，根據預測結果提前將任務運行所需資源(包括運行任務所需軟件及軟件依賴，簡稱任務資源)通過CF推送到邊緣服務器.云服務中心實時監測邊緣服務器的任務處理和資源使用，并將各邊緣服務器的任務處理和資源使用情況匯總，通過CF下發給邊緣服務器.

Fig.1 Edge cloud collaborative computing framework圖1 邊云協同計算框架

邊緣服務層由多個資源受限的邊緣服務器組成，向用戶提供實時、快速、多樣、靈活的網絡應用.邊緣服務器根據當前資源使用情況，依據調度策略將用戶任務決定在本地邊緣服務器單獨執行，或者將任務細分調度到其他邊緣服務器和(或)云服務中心協同執行.在邊—邊、邊—云之間執行任務產生數據流(data flow, DF).邊緣服務器通過CF從云服務中心接收并加載任務資源，預先啟動任務運行所需環境.邊緣服務器將任務處理情況和計算、存儲、網絡等資源使用情況通過CF上傳到云服務中心.邊緣服務器之間不相互傳遞CF，以減少邊緣服務器的處理開銷和帶寬占用.

端用戶層由用戶擁有的移動設備、計算機、網聯汽車、智能家電、智能終端等組成，具有一定算力，可以將任務進行預處理或部分前置處理，向邊緣服務器發送任務請求(request data, RD).請求任務在本地邊緣服務器單獨執行，或者在其他邊緣服務器和(或)云服務中心協同執行后，任務執行結果(answer data, AD)將從本地邊緣服務器、其他邊緣服務器、云服務中心返回至用戶端.

Table 1 Meaning of the Main Symbols表1 主要符號及其含義

2.2 邊云協同計算建模

定義1.邊云協同計算模型.邊云協同計算模型(edge cloud collaborative computing model,MEC3)為一個六元組模型MEC3=(U,J,E,C,O,Γ).U為用戶集，由n(u)個獨立的用戶組成，U={u0,u1,…,un(u)-1}，用戶之間互不干擾，用戶提交的各類任務存在時間序列相關性，可以對任務的類型數量進行預測.J為任務集，由n(j)個任務組成，J={j0,j1,…,jn(j)-1}，一個用戶可以提交不同任務，任務分為時間敏感型和非時間敏感型2類，每類任務包括多種不同任務以滿足多樣用戶需求，任務可以細分為若干子任務.E為邊緣服務器集，由n(e)個地理位置分散的邊緣服務器組成，E={e0,e1,…,en(e)-1}，邊緣服務器的計算、存儲、網絡等硬件資源有限，擁有部分任務資源，能將任務細分并根據決策將任務在本地執行或派遣至遠端執行.C為云服務中心，擁有大量的計算、存儲、網絡等硬件資源，擁有全部任務資源.云服務中心對邊緣服務器進行管理和監控，對用戶任務進行有效預測，以推送合適任務資源至相關邊緣服務器.O為邊云協同計算的優化目標，具體由用戶服務質量(quality of user service, QUS)和系統服務效用(effect of system service, ESS)綜合量化，記為Qus和Ess，O={max(Qus),max(Ess)}.Γ是資源部署與任務調度優化算法.

定義2.用戶服務質量.QUS主要關注用戶在邊云協同計算環境中的服務體驗與質量.一般來說，用戶任務在接收任務的邊緣服務器本地執行，用戶任務請求的響應時間越小，用戶服務質量越高.用戶服務質量系數為

(1)

(2)

定義3.系統服務效應.ESS主要關注服務供應商在邊云協同計算中的系統服務收益與系統服務消耗.系統服務收益系數為

(3)

(4)

在式(4)中，統計周期內的系統服務消耗為任務執行時間當量t與服務平均能耗系數s的乘積.tC，te分別表示云服務中心、邊緣服務器的任務執行時間當量，sC，se分別表示云服務中心、邊緣服務器的服務平均能耗系數.能耗系數取決于硬(軟)件成本和系統運維成本.前者包括硬(軟)件采購成本、折舊損耗成本；后者包括設備電能消耗、空調制冷能耗、管理服務成本.從單量比較分析，sC>se.系統服務收益越高，系統服務消耗越低，則Ess值越大，邊云協同計算的系統服務效應越高.

在邊云協同計算模型中，用戶服務質量與系統服務效應的目標優化涉及資源部署與任務調度.需要對用戶任務的類型與數量進行預測，合理推送任務資源至邊緣服務器，高效利用邊緣服務器的計算、存儲、網絡等資源；需要優化任務調度，通過本地邊緣服務器、其他邊緣服務器和云服務中心的任務協同處理，提升用戶服務質量，提高系統服務效用.

3 任務預測

對用戶任務進行長期監測，從局部看用戶任務變化是一個動態隨機過程，可以顯性或隱性看到一種變化趨勢，其任務變化和時間具有很強的關聯性；從全局看用戶任務與年、月、周、日等時間周期呈現明顯自相關.基于縱向和橫向時間維度的任務變化規律，可以通過預測找到任務變化趨勢.圖2(a)為某電商平臺集群服務器中部署的任務數量統計圖，圖2(b)為某高校數據中心外網接口的任務請求統計圖.這2個圖的任務數隨著時間的變化而改變.觀察圖2(a)連續7天、圖2(b)連續3天列出的任務數，發現每天的任務數值在相同時間段的變化趨勢相近，總體呈現有規律的周期波動，為邊云協同計算的用戶任務預測提供參考依據.

Fig.2 Task request statistics圖2 任務請求統計圖

根據邊云協同計算中用戶任務為強周期性、中趨勢性和弱隨機性的疊加變化趨勢，可在云服務中心對用戶任務從橫向和縱向2個維度進行綜合預測，統計分析過去基于時間序列的數據，推測任務的發展變化.預測模型為

L(t)=δx(t)+(1-δ)z(t)+ε(t)，

(5)

L(t)為下一個時間序列的任務預測結果；x(t)為橫向維度的當前時間序列值，為趨勢預測部分；z(t)為縱向維度的當前時間序列值，為周期性統計部分，具體為不同周期的同一時間序列均值；ε(t)為隨機噪聲；δ為二維時間序列調整因子，取值介于0～1之間.

定理1.邊云協同計算模型基于橫向維度的趨勢預測任務為

證明.對實踐數據統計分析，從局部看任務數為線性增長或減少趨勢，可用線性方程表示任務數變化，表示為

x(t)=?t+b.

(6)

由此可以得到時間t-n的任務數為

x(t-n)=?(t-n)+b.

(7)

(8)

(9)

根據式(6)，將時間t的任務數x(t)=?t+b代入式(9)，得到：

(10)

即

證畢.

由此得到基于二維時間序列的任務預測：

(11)

4 資源部署與任務調度

邊云協同計算的資源部署與任務調度優化，首先需要在云服務中心根據任務預測結果將任務資源推送至合適的邊緣服務器，提高用戶任務在邊緣服務器的本地執行率.其次需要在邊緣服務器通過帕累托優化任務調度，提高用戶服務質量，提升系統服務效應.

4.1 基于任務預測的資源部署算法

算法1.基于任務預測的資源部署算法RDTP.

輸入：邊緣服務器集E、任務集J、邊緣服務器最大可用資源集A、邊緣服務器當前可用資源集K；

輸出：邊緣服務器任務資源部署集X.

① 任務j∈J分類；

② fore∈Edo

④ 應用式(11)預測任務；

⑤ 任務的分類聚合、降序排列(頻次)；

⑥ forj∈Jdo

⑦ if時間敏感型任務且在邊緣服務器運行

/*延遲閾值判定*/

/*計算當前可用資源*/

/*延遲閾值判定*/

/*計算當前可用資源*/

在云服務中心進行基于任務預測的資源部署.行①將所有任務分類，分為時間敏感型和非時間敏感型2類.行②③根據監測數據，計算每個邊緣服務器的當前可用資源和最大可用資源，包括計算資源和存儲資源.行④應用式(11)基于二維時間序列進行任務預測.行⑤根據預測結果對每個邊緣服務器的任務分類聚合，并根據出現頻次降序排列，減少任務資源的推送數量，降低邊緣服務器的資源占用，提升資源緊張情況下的用戶任務命中率.行⑥～根據任務分類聚合結果，優先考慮時間敏感型任務資源部署，在邊緣服務器有富余可用資源情況下，再考慮非時間敏感型任務所需資源，有利于保障用戶服務質量.得到每個邊緣服務器部署的任務資源后，更新每個邊緣服務器的當前可用資源.為減少任務延遲，進行延遲閾值判定，確保邊緣服務器包括計算資源和存儲資源的可用資源占比高于任務延遲發生閾值ζ，控制推送至邊緣服務器的任務資源數.行返回邊緣服務器任務資源部署集X，云服務中心將任務資源推送到邊緣服務器.基于任務預測的資源部署算法時間復雜度為O(n(E)×n(J)(lbn(J)+1)).

4.2 基于帕累托優化的任務調度算法

邊云協同計算環境下的任務調度需要面向用戶和服務供應商，綜合考慮用戶服務質量和系統服務效用2個目標優化.任務調度的單一目標最優不能確保另一目標亦為最優，需要權衡2個目標進行綜合優化.為此，引入經濟學領域的帕累托優化，通過尋求用戶服務質量和系統服務效應這2個目標的帕累托改進，得到邊云協同計算的任務調度方案.基于帕累托優化的任務調度算法(task scheduling algorithm based on Pareto improvement, TSPI)為：

算法2.基于帕累托優化的任務調度算法TSPI.

輸出：任務調度方案集Y.

① if收到新任務j

② 將新任務j加入任務集J；

③ end if

④ if任務集J非空

⑤ 任務j∈J升序排列(數據量)；

⑥ end if

⑦ forj∈Jdo

⑧ forE∪Cdo

⑩ 運用式(2)計算Qus；

/*第1階段任務調度方案求解*/

/*第2階段任務調度方案求解*/

在邊緣服務器進行基于帕累托優化的任務調度.行①～⑥接收新任務，將其加入到任務集，如果同時有多個用戶發起任務請求，將任務按數據量大小升序排列.行⑦～分2個階段進行任務調度的帕累托優化.行⑧～為第1階段用戶服務質量目標優化，基于隨機貪心近似算法分別求解第1階段m組任務調度方案，運用式(2)分別計算每組的用戶服務質量Qus值，從中選擇每組中Qus值最大的調度方案，這些方案集可以得到用戶服務質量目標曲線.行～為第2階段系統服務效應目標優化，基于隨機貪心近似算法求解第2階段m組任務調度方案，通過運用式(4)分別計算每組的系統服務效應Ess值，從中選擇每組中Ess值最大的調度方案，這些方案集可以得到系統服務效用目標曲線.行將2個階段得到的任務調度方案進行帕累托漸進比較，選取用戶服務質量目標曲線和系統服務效用目標曲線對應的相切點或任一相交點，前者為2個目標唯一最優方案，后者為2個目標任一共優方案，從而得到每個任務的最優調度方案.行返回任務調度方案集Y.算法中2個階段的m組任務調度方案取值應適宜.值過小會導致2個階段的解集較單一，可能出現無用戶服務質量目標曲線與系統服務效用目標曲線相交或相切的情況；值過大會增加任務調度本身的計算開銷.基于帕累托優化的任務調度算法時間復雜度為O(n(J)×(lbn(J)+(n(E)+1)×m)).

5 實驗及結果分析

本節搭建邊云協同計算實驗環境，設置實驗參數，確定評價指標，對基于任務預測的資源部署算法和基于帕累托優化的任務調度算法進行綜合評價.

5.1 實驗環境與參數

邊云協同計算實驗的硬件平臺為一臺擁有Intel E5-2620V4 CPU，64 GB ECC RAM，3×2 TB STA的x86服務器.軟件平臺依托CentOS 8.0 x86_64操作系統，采用Python 3.8搭建邊云協同計算仿真環境.采用OriginPro 2017軟件進行數據分析處理與后期繪圖.本實驗環境的參數如表2所示.在邊云協同計算環境中借鑒阿里云公布的數據集[33-34]，設置用戶任務的類型、執行時間、CPU資源占用、RAM資源占用.用戶任務具有隨機無后效性，總體呈現Zipf分布[35]，其任務出現的頻率與任務熱度排名成反比關系，實驗中Zipf分布的參數α值缺省為1.0.云服務中心擁有的最大可用資源為10K PE CPU，10 TB RAM，10 PB硬盤.邊緣服務器的硬件資源參數如表3所示:

Table 2 Experimental Environment Parameters表2 實驗環境參數

Table 3 Hardware Resource Parameters of Edge Servers表3 邊緣服務器硬件資源參數

5.2 實驗結果分析

5.2.1 任務預測與資源部署

Fig.3 Prediction of user tasks圖3 用戶任務預測

在邊云協同計算環境中評估分析基于任務預測的資源部署.以日作為統計周期，每個周期分為24個時間段，每個時間段為1 h.在實驗中，云服務中心基于二維時間序列對邊緣服務器的任務進行預測，時間槽n=10，根據前期任務預測實驗數據，設置二維時間序列調整因子δ=0.78，并忽略隨機噪聲.將預測結果與邊緣服務器實際處理的任務數進行比較分析，如圖3所示.邊云協同計算環境中用戶任務的實際值變化較大，任務的預測值變化相對較平緩.總體看基于二維時間序列的任務預測接近真實值，平均任務數偏差小于5%，任務預測的準確度高，其結果可以指導云服務中心優化邊緣服務器的任務資源部署.

采用平均用戶任務命中率(average user task hit rate,ATHR)評估基于任務預測的資源部署效果.ATHR指各邊緣服務器首次接收用戶任務請求，其具備任務運行所需資源并將任務本地執行的占比均值.ATHR高，說明云服務中心基于預測結果推送任務資源的準確率高.在邊緣服務器本地執行任務的比率高，有利于提高用戶服務質量，提升系統服務效應.在邊云協同計算環境中，云服務中心通過基于二維時間序列對用戶任務有效預測，根據預測結果分類聚合，優化推送任務資源到各邊緣服務器，提高用戶任務在邊緣服務器本地執行比率，減少邊緣服務器因無任務運行所需資源而被動向云服務中心申請任務資源.通過連續15天的實驗，實驗結果如圖4所示，其中橫軸di表示第i天，i=1,2,…,15.圖4通過基于二維時間序列任務預測部署邊緣服務器所需任務資源，邊緣服務器的平均用戶任務命中率有了很大提高，ATHR達到82.51%～90.92%，遠高于無任務預測資源部署不到50%的平均用戶任務命中率.

Fig.4 Average user task hit rate of edge servers圖4 邊緣服務器平均用戶任務命中率

5.2.2 任務調度

在邊云協同計算環境中，從用戶平均服務完成時間、系統整體服務效應度、總任務延遲率，對基于帕累托優化的任務調度算法TSPI、結合基于任務預測的資源部署算法與基于帕累托優化的任務調度算法(resource deployment algorithm based on task prediction-task scheduling algorithm based on Pareto improvement, RDTP-TSPI)、基于FIFO的基準任務調度算法(benchmark task scheduling algorithm based on FIFO, BA)[36]進行任務調度的性能評估分析.根據任務調度實驗數據，將TSPI算法2個階段的m組任務調度方案值設置為7，可得到用戶服務質量和系統服務效用這2個目標的唯一或共優方案，且不過多增加任務調度本身的計算開銷.

1) 評估用戶平均服務完成時間(average service completion time of users,ASCT).ASCT為統計時間段內所有用戶任務的完成時間總和與用戶任務數之比.ASCT主要考慮用戶的服務體驗，其值越小，說明任務平均完成時間越短，用戶的服務質量越高.在邊云協同計算環境中，用戶任務為缺省參數α的Zipf分布，通過改變任務規模比較分析TSPI，RDTP-TSPI，BA這3種算法的ASCT,如圖5所示，隨著用戶任務數的增加，3種算法的ASCT隨之增加，呈現近似線性變化趨勢.相比較BA算法，RDTP-TSPI算法和TSPI算法的ASCT均明顯降低，其中TSPI算法通過對用戶服務質量和系統服務效應這2個目標的帕累托改進，有效降低用戶平均服務完成時間，其ASCT相比較BA算法平均總體減少38.85%.RDTP-TSPI算法預測用戶任務類型數量，提高云服務中心向邊緣服務器推送任務所需資源的準確度，在此基礎上分2個階段進行任務調度的帕累托優化，進一步降低用戶平均服務完成時間，其ASCT相比較BA算法平均總體減少46.84%.

Fig.5 Average service completion time of users under different tasks圖5 不同任務下用戶平均服務完成時間

在用戶任務固定情況下，考慮任務Zipf分布參數α的影響，進一步評測TSPI，RDTP-TSPI，BA這3種算法的ASCT.它們的用戶平均服務完成時間如圖6所示，在邊云協同計算環境中將用戶任務數設置為5 000個，隨著Zipf分布參數α值的增大，用戶任務越來越集中于流行度高的任務類型，3種調度算法的ASCT均有不同程度的減小.總體分析，RDTP-TSPI算法對任務類型數量進行預測，提高任務資源推送準確率，提升平均用戶任務命中率，再綜合用戶服務質量和系統服務效用目標進行帕累托優化任務調度，其ASCT最優，相比BA算法平均總體減少40.68%.TSPI算法得益于對用戶服務質量和系統服務效用的2階段帕累托優化，在無任務預測優化資源部署的情況下，其ASCT相比BA算法平均總體減少27.13%.

Fig.6 Average service completion time of users underdifferent Zipf distribution parameters α圖6 不同Zipf分布參數α下用戶平均服務完成時間

2) 評估系統整體服務效應度(overall service effectiveness of system,OSES).OSES為統計周期內云服務中心和各邊緣服務器的系統服務收益與系統服務消耗之差，是歸一化處理的系統服務效應.OSES主要考慮服務供應商的利益，供應商的系統服務收益越高，系統服務消耗越低，其值越大.在邊云協同計算環境中，用戶任務為缺省參數α的Zipf分布，通過逐漸增加用戶任務數來評測TSPI，RDTP-TSPI，BA這3種算法的OSES.它們的系統整體服務效應度如圖7所示.隨著用戶任務數的增加，3種算法的OSES隨之增大，呈現近似對數增長變化.相比較BA算法，RDTP-TSPI算法和TSPI算法的OSES有明顯提升，其中TSPI算法通過對用戶服務質量和系統服務效用目標的帕累托改進優化任務調度，提高了云服務中心和邊緣服務器的系統整體服務效應度，其OSES平均總體提升34.78%；RDTP-TSPI算法在云服務中心基于任務類型數量預測，有效推送任務資源，提升平均用戶任務命中率，在邊緣服務器基于用戶服務質量和系統服務效用目標優化任務調度，進一步提升OSES，其OSES平均總體提高49.91%.

Fig.7 Overall service effectiveness of systemunder different tasks圖7 不同任務下系統整體服務效應度

Fig.8 Overall service effectiveness of system underdifferent Zipf distribution parameters α圖8 不同Zipf分布參數α下系統整體服務效應度

同樣在用戶任務一定情況下，考慮任務Zipf分布參數α的影響，進一步評測TSPI，RDTP-TSPI，BA這3種算法的系統整體服務效應度.它們的OSES變化情況如圖8所示，在邊云協同計算環境下用戶任務數為5 000個，隨著Zipf分布參數α值的增大，使得用戶任務逐漸趨向流行度高的任務類型，減少邊緣服務器的任務資源數，3種算法的OSES有很大提升.總體來說，RDTP-TSPI算法由于對任務類型進行預測，可以提升推送邊緣服務器任務運行所需資源的準確度，提高平均用戶任務命中率，再通過兼顧用戶服務質量和系統服務效用的2階段綜合優化，其OSES最優，相比BA算法平均總體提升46.84%.TSPI算法在無任務預測情況下，通過對用戶服務質量和系統服務效用的帕累托漸進優化，其OSES相比BA算法平均總體提高38.85%.

3) 評估總任務延遲率(total task delay rate,TTDR).TTDR為統計時間段內任務響應時間超過同類任務響應時間均值3倍的任務數占比.TTDR影響用戶服務質量和系統服務效應[37].TTDR低，有利于降低用戶平均服務完成時間，提升用戶服務質量；有利于減少系統能耗，提高系統服務效應.在邊云協同計算環境中，用戶任務為缺省參數α的Zipf分布，通過逐漸增加用戶任務數來評測TSPI，RDTP-TSPI，BA這3種算法的總任務延遲率.如圖9所示.隨著用戶任務數的增加，3種算法的TTDR隨之增加，總體看RDTP-TSPI算法最優、TSPI算法次之、BA算法最差.RDTP-TSPI算法對任務進行預測、分類聚合減少推送至邊緣服務器的任務資源數，在資源部署時進行延遲閾值判定，考慮邊緣服務器的可用資源以減少任務延遲發生概率，隨著任務數量的增長，其總任務延遲率增長緩慢，TTDR控制在0.10%～4.01%之間.BA算法和TSPI算法在任務調度時都缺少任務預測，沒有對可能出現任務延遲的情況進行處理，它們的TTDR偏高，隨著任務的增加總任務延遲率亦呈線性增長.BA算法的TTDR最高，為8.03%～36.08%.由于TSPI算法對任務調度進行綜合用戶服務質量和系統服務效用目標的帕累托優化，能減少任務平均服務完成時間，其TTDR較低，為3.01%～33.02%.

Fig.9 Total task delay rate under different tasks圖9 不同任務下總任務延遲率

同樣在用戶任務不變情況下，考慮任務Zipf分布參數α的影響，進一步評測TSPI，RDTP-TSPI，BA這3種算法的總任務延遲率.在邊云協同計算環境下將用戶任務數設置為5 000個，它們的總任務延遲率變化情況如圖10所示，隨著Zipf分布參數α值增加，用戶任務越來越集中于流行度高的任務類型，總體看邊緣服務器需要的任務資源類型有所減少，TSPI，RDTP-TSPI，BA這3種算法的總任務延遲率均有不同程度下降.RDTP-TSPI算法對用戶任務進行預測和分類聚合，減少推送至邊緣服務器所需的任務資源，在資源部署時通過延遲閾值判定以有效降低任務延遲發生，再通過帕累托優化任務調度，使其TTDR始終處在低水平，值為0.11%～4.03%，相比BA算法平均減少18.88%.TSPI算法缺乏用戶任務預測，沒有優化邊緣服務器的任務資源部署，在用戶任務調度時綜合用戶服務質量和系統服務效用進行帕累托優化，其TTDR較高，為11.02%～22.67%，相比BA算法平均減少4.56%.BA算法的TTDR最高，為15.28%～28.37%，均值達到20.22%.

Fig.10 Total task delay rate under different Zipfdistribution parameters α圖10 不同Zipf分布參數α下總任務延遲率

6 結束語

本文面向用戶和服務供應商研究邊云協同計算中使用任務預測的資源部署與任務調度優化.首先設計邊云協同計算框架，提出基于任務預測的資源部署算法RDTP，在云服務中心基于二維時間序列對用戶任務進行預測，分類聚合用戶任務類型，推送任務資源至邊緣服務器，提高平均用戶任務命中率，減少服務器資源占用開銷.然后提出基于帕累托優化的任務調度算法TSPI，在邊緣服務器基于隨機貪心近似算法，分別對用戶服務質量和系統服務效應這2個目標進行帕累托改進，尋求2個目標曲線的相切點或相交點以優化任務調度.通過實驗評估分析，結合基于任務預測的資源部署算法與基于帕累托優化的任務調度算法RDTP-TSPI，在提高平均用戶任務命中率基礎上，其用戶平均服務完成時間、系統整體服務效應度、總任務延遲率，均優于基于帕累托優化的任務調度算法TSPI和基于FIFO的基準任務調度算法BA.未來的研究，將考慮在邊云協同計算環境下進行可擴展的自適應資源部署與任務調度.