[發明專利]在邊緣計算中在線批并行任務調度方法

在審

• 申請號: 202110731470.5
• 申請日: 2021-06-29
• 公開（公告）號: CN113448707A
• 公開（公告）日: 2021-09-28
• 發明（設計）人: 郭星;魯俊;李煒;張以文
• 申請（專利權）人: 安徽大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 合肥市長遠專利代理事務所(普通合伙) 34119
• 代理人: 孫麗麗

在邊緣計算中在線批并行任務調度方法，具體步驟為：S1、使用馬爾科夫決策過程進行建模；S2、在每一段時間片段內，為每一個邊緣服務器的Batch容器進行任務分發；S3、使用強化學習來進行求解，最終完成在線任務的調度。相對于目前的邊緣計算調度算法，對于任務的處理大多采用串行處理策略，使用馬爾科夫決策過程的思想在n個任務如何在m臺邊緣服務器上處理，而且在選擇算法的優化目標時，考慮優化多種開銷和任務處理的及時性；在使用增強學習方法設計調度算法時，算法運行時間過短，實用性較強。

技術領域

本發明涉及邊緣計算的技術領域，尤其涉及在邊緣計算中在線批并行任務調度方法。

背景技術

隨著云計算與信息技術的快速發展，生活中移動設備的數量與設備間通信數據量在逐年增長。根據思科公司的預測，到2021年時，移動設備間的通信數據月間流量會達到48.3EB。而且這些移動設備越來越智能化，能夠為用戶提供更強大，更多樣化的服務，例如，視頻的拍攝與處理，虛擬現實(VR)游戲，移動視頻通信等等。然而，伴隨著移動設備功能的增多，各種應用與服務對設備本身的計算資源需求也越來越大。由于一般的移動設備本身的資源與電池容量的限制，這些計算密集型的應用通常不能在移動設備自身上得到及時有效的處理。在先前一段時間的研究中，解決上述問題的一種方法是通任務卸載(taskoffloading)的方式，將移動設備自身不能處理的應用轉移到有著充足計算資源的云計算中心去處理，從而滿足計算密集型應用對計算資源的需求。然而，隨著移動應用自身的功能與數據量持續增長，上述方法的缺陷也暴露了出來：雖然將移動設備上的任務遷移到云計算中心處理這任務對計算資源的需求，但同時遠端云與移動設備間傳輸信息時也產生了很大的通信時延，增長了用戶等待任務執行的響應時間，從而影響到用戶的服務體驗。為了彌補上述因傳輸時延影響用戶服務體驗的問題，一些學者提出了新的計算模型，即將大部分原本在云計算中心完成的任務轉移到網絡邊緣上完成。這種新型計算模型通過綜合利用廣泛分布在網絡邊緣的空閑資源，為移動設備上的計算密集型與時延敏感性的任務提供計算資源，從而滿足這些任務對于計算資源與響應時間兩方面的要求。這種新型計算模型稱為邊緣計算，它的體系結構如Fig.1所示，通過在網絡邊緣靠近用戶的一邊設置一些邊緣云節點，移動設備自身產生的任務可以直接卸載到邊緣云上去處理，而且這種方式相對于將任務卸載到遠端云處理會產生的網絡傳輸時延更少，從而能提高任務處理的及時性。雖然通過設置邊緣云節點就近處理用戶任務大大縮短了用戶設備與遠端云處理中心的通信時延，但同時也產生了一個新的問題，即如何為卸載到邊緣云節點上的任務制定有效的調度策略。這是因為邊緣服務器自身的資源相對于遠端云是有限的，且各邊緣服務器之間的處理速度與資源總量往往不完全一樣，同時任務之間還存在著資源競爭。如果在某一時間段內，有較多的任務卸載到邊緣節點上而沒有得到合理地處理，必然會影響用戶體驗，因此如何對卸載到邊緣服務器上任務進行合理調度，使得邊緣服務器使用自身有限的資源處理更多的任務，同時能夠保證用戶的服務體驗是一個重要的問題。

在邊緣計算的任務調度問題上,Liang et al.提出了一種層次邊緣云的結構，使得邊緣服務器在高峰期處理任務時有更高的效率。Ha et al.[提出一種在相關設備控制下，快速有效地支持時延敏感性任務的邊緣云結構。Su et al.使用了PSO-HH算法優化邊緣云的結構參數來為任務設計一個自適應分配規則。Urgaonkar將工作負載調度問題轉化為一個馬爾可夫決策過程，并通過Lyapunov優化策略來解決這一問題。Li et al.基于博弈論的思想提出了一種在Ad-Hoc結構下的邊緣設備間任務轉移的策略。對于以縮短任務的響應時間為目標的的調度策略，M Alicherry et al.提出了一種智能虛擬機布局來縮短數據傳輸時間。對于以減少服務器的運行能耗為目標的調度策略，Zhang et al.在移動云環境下，使用LARAC算法解決任務在移動設備與云上協同運行的節省能耗開銷；Zhu et al.]提出了一種在虛擬云環境下的面向任務的能耗節約算法EARH。對于平衡各服務器負載的任務數量為目標的調度策略，Wang et al.使用JLGA算法不但縮短了各服務器處理任務的完成時間，而且提高各服務器的資源利用率；Chen et al在Min-Min算法的基礎上，提出了LBIMM算法，也在服務器的完成時間與資源利用率進行了優化。