基于邊緣計算的多目標任務調度方法

摘要： 針對智能工廠中的邊緣算力資源調度問題，提出基于邊緣計算的多目標任務調度模型； 以最小化任務時延和任務能耗為目標函數，添加傳輸時延、 計算時延、 排隊時延、 遷移時延、 傳輸能耗、 計算能耗、 遷移能耗等7項約束條件建模； 為了解決多目標調度求解問題，提出基于任務緊急度的資源調度與分配算法，并設置遷移判斷中服務器選擇和任務排序方法； 以占地面積為1.2×104 m2的智能工廠的邊云設備為實驗環境，對比基于任務緊急度的資源調度與分配算法與隨機接入資源分配算法、 迭代資源分配算法的平均任務完成率。結果表明，基于任務緊急度的資源調度與分配算法的服務器任務完成率較其他2種算法分別提高48、 5個百分點，大多數服務器的任務丟棄率被降至2%～4%，并且對系統負載均衡等問題的處理效果顯著。

關鍵詞： 生產任務調度； 多目標優化； 邊緣計算； 邊云協同

中圖分類號： TP301

文獻標志碼： A

開放科學識別碼（OSID碼）：

Multi-objective Task Scheduling Method Based on Edge Computing

XIE Yanyu CHEN Lansun2

（1. School of General Education， Minnan Science and Technology College， Quanzhou 362332， Fujian， China;

2. Academy of Mathematics and Systems Science， Chinese Academy of Sciences， Beijing 100190， China）

Abstract： Aiming at the scheduling problem of edge computing resources in industrial intelligent factories， a multi-objective task scheduling model based on edge computing was proposed. With the objective function of minimizing task delay and task energy consumption， seven constraints such as transmission delay， computing delay， queuing delay， migration delay， transmission energy consumption， computing energy consumption and migration energy consumption were added for modeling. In order to solve the multi-objective scheduling problem， a resource scheduling and allocation algorithm based on task urgency （RSA_TU） was proposed， and the methods of server selection and task sequencing in migration judgment were set. Taking the edge cloud equipment of a smart factory covering an area of 12 000 m2 as an experimental environment， RSA_TU algorithm was compared with the random-access resource allocation algorithm and iterative resource allocation algorithm based on greedy search in average mandate completion rate. The results show that the server task completion rate of RSA_TU algorithm is improved by 48 percentage points and 5 percentage points respectively compared with the other two algorithms， and the discard rate of most servers is reduced to 2% to 4%， which reflects the remarkable effect of the proposed algorithm on system load balancing and other issues.

Keywords： production task scheduling; multi-objective optimization; edge computing; edge-cloud collaboration

邊緣化網絡計算已成為網絡計算架構的新趨勢。在實際應用中，邊緣節點的計算能力可能是有限的， 當大量移動設備將任務調度到同一邊緣節點時， 可能導致任務處理延遲增加， 甚至導致任務被放棄。 為了解決該問題， 一些研究者考慮諸如任務傳輸速率、調度速率以及設備處理能力等因素， 利用凸優化方法求解最優的任務調度決策， 以最小化任務的計算延遲和邊緣計算環境中的工作流調度問題。例如， Sun等^［1］將調度問題轉變為整數規劃問題， 并采用貪婪搜索策略和復合啟發式算法確保解的質量。Meng等^［2］提出基于新的截止日期的貪婪調度算法。彭青藍等^［3］以任務優先級加權的卸載響應時間為評價指標， 提出一種去中心化的在線任務調度與資源分配方法， 能夠減少34.21%的加權任務卸載響應時間。 Han等^［4］綜合考慮所有任務的計算時間對用戶服務體驗的影響， 提出一種任務調度方法， 旨在最小化所有任務的加權處理時間。 巨濤等^［5］在改進深度強化學習模型的基礎上， 提出自適應邊緣計算任務調度方法， 能充分利用邊緣計算資源改善任務處理的實時性， 降低系統能耗。

在處理任務調度問題時，上述凸優化方法和啟發式方法具有較高的計算效率和可解釋性^［6-7］，但在面對復雜的邊緣計算場景時，通常需要場景的全部信息，導致在處理復雜場景時變得困難，難以優化得出良好的調度策略。此外，在復雜的邊緣計算場景中，任務之間的依賴關系和所需的計算資源通常難以精確建模，傳統方法的準確性和可靠性受到挑戰。本文中結合邊云協同與算力組網的理念，建立基于邊緣計算的多目標任務調度模型，考慮包含靜態設備、 巡檢機器人、 邊緣服務器和邊緣網絡鏈路的智能工廠層次邊緣網絡，旨在最小化任務的總體時延和能耗。

1 邊緣計算

隨著物聯網技術的飛速發展，移動邊緣計算（MEC）^［8-9］作為一項減輕云端壓力的解決方案，備受研究者的廣泛關注。早期MEC的發展受益于內容分發網絡技術（CDN）的興起^［10］。隨著時間推移，CDN提供的數據備份功能無法滿足用戶日益增長的任務處理需求，目前的邊緣計算不再局限于內容分發和緩存管理，而是利用邊緣服務器強大的計算能力為終端設備提供低延遲的計算服務，成為邊緣計算的另一個重要功能^［11］。典型的3層邊緣計算框架包括具有強大計算能力的云計算層、 距離終端設備較近的具有較強處理能力的邊緣層以及終端設備層，如圖1所示。

終端設備層由各式各樣的物聯網終端設備所組成，由于這些終端設備自身計算能力的限制，在大多數場景下無法滿足產生的任務日益增長的時敏性需求^［12-13］，因此，在面對計算密集及延遲敏感型任務時，終端設備層通常將此類任務調度到邊緣層處理或通過邊緣層進一步傳輸到云計算層處理。邊緣層是3層邊緣計算框架的核心，主要由位于網絡邊緣位置的智能化基站、 邊緣網關以及路由器等設備所組成^［14］。由于這些邊緣層設備距離終端設備較近，因此可以將終端設備上的時敏性任務傳輸到邊緣層處理，或者通過邊緣層將任務傳輸至計算能力更強的云計算層處理，從而有效減少云計算層和核心網的負載。云計算層主要通過軟件定義網絡、 網絡功能虛擬化等虛擬化技術，封裝大規模集群式計算資源，根據實際動態的需求管理計算資源，為終端設備提供計算服務^［15-16］。

2 基于邊緣計算的多目標任務調度模型

2.1 系統建模

本文中定義的智能工廠層次邊緣網絡協作架構為W=（M∪N∪E∪C， L）， 其中， M為靜態設備， N為巡檢機器人， E為邊緣服務器， L為邊緣網絡鏈路。

以下逐一描述模型的7項約束條件。

2.1.1 傳輸時延

傳輸時延不僅包括數據在有線信道傳輸的時間，還包括數據在光纖中傳遞的時間。任務量AM，t為靜態設備M在t時刻通過光纖連接到邊緣服務器E的距離為SM，E，傳輸時延TtM，t的表達式為

TtM，t=AM，tvnet+SM，Evlig ，（1）

式中： vnet與vlig分別為網絡和光信號在無線信道中的傳輸速度。

本文中使用時分復用的傳輸模式，以保證任務在無線信道上傳輸至邊緣服務器時不會相互干擾。根據香農（Shannon）公式，計算得到t時刻巡檢機器人N能夠達到的最大傳輸速率vN，t為

vN，t=BN，tlog21+PN，tP′N，t

，（2）

式中： BN，t為巡檢機器人N在t時刻上傳處理任務時分配的上行信道帶寬； PN，t與P′N，t分別為巡檢機器人N在t時刻的上傳功率和噪聲功率。

信道增益GN，t的計算公式為

GN，t=λ4π（xE-xN，t）2+（yE-yN，t）2 ，（3）

式中：（xE， yE）為邊緣服務器E的坐標； （xN，t， yN，t）為巡檢機器人N在t時刻的實時坐標。

2.1.2 計算時延

將靜態設備M和巡檢機器人N統稱為終端設備K， t時刻待處理任務量為AK，t，則本地終端設備K的計算時延TcK，t為

TcK，t=HE，tAK，tfE，t ，（4）

式中HE，t和fE，t分別為邊緣服務器E在t時刻的中央處理器（CPU）的計算能力和頻率。

2.1.3 排隊時延

對本地層終端設備產生的待處理任務的緊急度記為δK，t，設ts為單位時隙，當t≥ts時，有UK，t=AM，t和δK，t=δK，t-ts，其中UK，t為t時刻終端設備K無法處理的任務量。本地終端設備K的排隊時延TqK，t計算公式為

TqK，t=HE，tAE，tfE，t ，（5）

式中AE，t為邊緣服務器E在t時刻的任務量。

2.1.4 遷移時延

設Tp（E，E′）表示任務從邊緣服務器E遷移到邊緣服務器E′所經過的路徑上的時延，其中路徑包括了起始點、 終止點以及中間經過的所有邊緣服務器，則鏈路時延TlK，t計算公式為

TlK，t=σTp（E，E′） ，（6）

式中σ為固定的鏈路時延系數。

綜合考慮傳輸、 計算、 等待時延以及路徑時延，可以得到任務遷移總時延TmK，t為

TmK，t=TtM，t+TcK，t+TqK，t+TlK，t 。（7）

2.1.5 傳輸能耗

巡檢機器人N與邊緣服務器E之間天線連接的傳輸能耗RtN，t為

RtN，t=TtN，tPN，t ，（8）

式中TtN，t為巡檢機器人N在t時刻的傳輸時延。

2.1.6 計算能耗

終端設備K在特定時刻產生的任務，經過直連邊緣服務器進行處理時的計算能耗RcK，t為

RcK，t=αEHE，tAK，t f2E，t ，（9）

式中αE為邊緣服務器E中芯片的有效電容系數。

2.1.7 遷移能耗

遷移能耗為邊緣服務器E遷入到另一邊緣服務器E′中產生的消耗，計算公式為

RmK，t=αE′HE′，tAK，t f2E′，t 。（10）

式中： αE′為邊緣服務器E′中芯片的有效電容系數； HE′，t、 fE′，t分別為邊緣服務器E′在t時刻的CPU的計算能力和頻率。

2.2 問題描述

在多目標任務中，當遷移時延不為0時，須要應調整原計算和排隊時延，總時延在系統中的計算表達為Tt=TtM，t+TqK，t。在原有模型基礎上，引入不同任務緊急度作為系數，如果存在任務遷移，則系統在某一時刻產生的總能耗為計算能耗和遷移能耗的總和，即

Rt=RcN，t+RmK，t 。（11）

綜上，任務緊急度已融入到時延中，則最小化總體時延和能耗的目標函數為

f=min（T+γR） ，（12）

式中： T為系統總時延； R為系統總能耗； γ為時延和能耗平衡系數。

2.3 基于邊緣計算的多目標任務調度問題求解

為了求解上述多目標任務調度問題， 本文提出了一種基于任務緊急度感知的算力資源調度和分配（RSA_TU）算法， 其核心思想是對待處理任務排序， 并根據服務器的處理能力判斷是否遷移任務。 設TmaxK，ts為單位時隙ts時本地終端設備K集合的最大排隊時延。

RSA_TU算法的輸入和輸出分別為多目標任務調度模型和調度結果。首先，初始化時間變量t=0時； 然后進入一個循環結構， 條件是時間t小于總時間長度。 在這個循環中， 終端設備K集合根據設備坐標匹配服務器， 同時邊緣服務器E集合根據名下所有待處理任務次序排列。 設邊緣服務器E集合在單位時隙ts的最大排隊時延為T^maxE，ts， 如果T^maxE，tsgt;T^maxK，ts， 則更新待處理任務矩陣信息； 否則， 更新不處理任務矩陣信息。記錄不處理任務矩陣中的最大緊急度閾值Nmax， 如果當前設備的任務緊急度δM，t小于Nmax，則將其轉移至不處理任務矩陣，并重新排序。

在任務處理過程中， 邊緣服務器每個時隙都會更新任務排序， 確保新到達的任務被及時添加到處理隊列中， 這意味著每個任務都必須在同一時隙內在某個邊緣服務器上完成處理。 該處理機制確保了任務的有序執行， 同時避免了因大任務而導致的任務積壓問題。 整個遷移判斷和選擇過程如圖2所示。

在資源調度與分配過程中， 首先要識別和分類接收到的任務^［17-18］。 基于對邊緣計算節點資源狀態的實時監測， 包括CPU利用率、 內存利用率和網絡帶寬等信息， 將任務分為不同的優先級和處理要求。

在任務識別與資源監測的基礎上， 系統自動評估每個任務的緊急度， 綜合考慮任務的截止時間、 重要性等因素。 隨后， 系統根據任務的緊急度和當前資源狀態作出資源調度決策。 對于高緊急度的任務， 系統優先選擇資源充足、 響應速度快的節點用于分配，以確保及時完成任務。 對于低緊急度的任務， 則選擇資源利用率較低的節點， 實現資源的均衡利用。 一旦完成資源調度決策，系統就將任務分配給相應的邊緣節點， 并啟動執行。 在任務執行過程中， 系統持續監測資源利用情況和任務執行進度， 并根據需要動態調整。 這種動態調整與優化確保了系統在面對不同負載和任務情況時能夠靈活適應， 提高了系統的性能和響應速度。

邊緣算力資源調度任務處理和排序過程如圖3所示。針對服務器的虛擬處理情況，根據任務排序，各服務器在同一時隙內處理任務，避免任務遷移。若每臺服務器可完全處理自身任務，則考慮更新處理結果。當服務器算力不足時，系統根據緊急程度決定是否遷移任務，將低緊急度任務重新分配。

3 實驗與結果分析

3.1 實驗環境及設置

實驗基于占地面積為1.2×104 m2的智能工廠，邊緣服務器、 云中心、 分布式單元、 本地終端設備、 傳感設備的數量分別設置為8、 2、 6、 400、 180。

設定邊緣服務器CPU周期數為6×10^-6，數據加

密級別為AES-256， 單位時隙為1 ms。當任務因失效而被丟棄時，排隊時長被統一設定為0.05 ms。采用泊松分布模擬終端設備的任務時間流，數據存儲量為0～50 KiB。

3.2 仿真結果分析

為了評估本文RSA_TU算法的特性， 引入Chen等^［19］提出的基于預測的隨機接入資源分配算法（PRARA）、 Fan等^［20］提出的基于貪婪搜索的迭代資源分配算法（IGS）作對比， 實驗中不同邊緣服務器的任務完成率如表1和圖4所示。

PRARA算法—基于預測的隨機接入資源分配算法； IGS算法—基于貪婪搜索的迭代資源分配算法；

RSA_TU算法—基于任務緊急度感知的算力資源調度和分配算法。

在PRARA算法應用中， 除5號服務器外， 其他服務器的任務完成率為19%～40%。 在IGS算法應用中， 各服務器的平均任務完成率相對平穩， 為61%～81%， 總平均完成率為72%。 本文提出的 RSA_TU算法在8個服務器中的平均任務完成率為66%～86%， 總平均任務完成率約為77%，較PRARA、 IGS算法分別提高了48、 5個百分點。

此外，針對因排隊時間過長而被丟棄的任務，本文中采用任務丟棄率量化分析，圖5為不同算法在不同邊緣服務器的任務丟棄率雷達圖。由圖可知，在PRARA算法應用中，除3號服務器外，其他服務器的任務丟棄率普遍較高，達到12%～17%。IGS算法雖然在1、 2、 5、 7、 8號服務器的任務丟棄率降低，但其他服務器的改善有限，任務丟棄率仍為10%左右。本文中提出的RSA_TU算法顯著降低任務丟棄率，大多數服務器的任務丟棄率降至2%～4%，多邊形的面積差異也反映了該算法對系統負載均衡等問題的顯著處理效果。

4 結語

針對智能工廠中的邊緣算力資源受限的調度問題， 本文中建立了以最小化任務時延、 任務能耗為目標函數， 以7項不同時延、 能耗指標為約束條件的多目標調度模型。 為了求解此多目標調度模型， 本文中提出RSA_TU算法， 建立任務緊急度評價方法， 提出遷移判斷中的服務器選擇和任務排序方法。以智能工廠邊緣云設備為實驗環境， 對比實驗結果顯示， RSA_TU算法的服務器任務完成率較PRARA、 IGS算法分別提高48、 5個百分點， 且大多數服務器的任務丟棄率被降至2%～4%， 表明該算法在系統負載均衡等方面具有顯著的優勢。

參考文獻：

［1］ SUN J， YIN L， ZOU M H， et al. Makespan-minimization workflow scheduling for complex networks with social groups in edge computing［J］. Journal of Systems Architecture， 2020， 108： 101799.

［2］ MENG J Y， TAN H S， LI X Y， et al. Online deadline-aware task dispatching and scheduling in edge computing［J］. IEEE Transactions on Parallel and Distributed Systems， 2019， 31（6）： 1271.

［3］ 彭青藍， 夏云霓， 鄭萬波， 等. 一種去中心化的在線邊緣任務調度與資源分配方法［J］. 計算機學報， 2022， 45（7）： 1464.

［4］ HAN Z H， TAN H S， LI X Y， et al. Ondisc： online latency-sensitive job dispatching and scheduling in heterogeneous edge-clouds［J］. IEEE/ACM Transactions on Networking， 2019， 27（6）： 2475.

［5］ 巨濤， 王志強， 劉帥， 等. D3DQN-CAA：一種基于DRL的自適應邊緣計算任務調度方法［J］. 湖南大學學報（自然科學版）， 2024， 51（6）： 76.

［6］ LUO S Q， CHEN X， WU Q， et al. HFEL： joint edge association and resource allocation for cost-efficient hierarchical federated edge learning［J］. IEEE Transactions on Wireless Communications， 2020， 19（10）： 6535.

［7］ 肖燁. 面向智能工廠的邊緣計算節點部署及節能技術研究［D］. 北京： 北京郵電大學， 2021： 37.

［8］ 狄箏， 曹一凡， 仇超， 等. 新型算力網絡架構及其應用案例分析［J］. 計算機應用， 2022， 42（6）： 1656.

［9］ ZENG L， LIU Q， SHEN S G， et al. Improved double deep Q network-based task scheduling algorithm in edge computing for make-span optimization［J］. Tsinghua Science and Technology， 2023， 29（3）： 806.

［10］ 張依琳， 梁玉珠， 尹沐君， 等. 移動邊緣計算中計算卸載方案研究綜述［J］. 計算機學報， 202 44（12）： 2406.

［11］ FENG Y X， HONG Z X， LI Z W， et al. Integrated intelligent greenschedulingofsustainableflexibleworkshopwithedgecomputingconsideringuncertain machine state［J］. Journal of Cleaner Production， 2020， 246： 119070.

［12］ PAN Z Y， HOU X H， XU H， et al. A hybrid manufacturing scheduling optimization strategy in collaborative edge computing［J］. Evolutionary Intelligence， 2022， 17（2）： 1065.

［13］ 劉澤寧， 李凱， 吳連濤， 等. 多層次算力網絡中代價感知任務調度算法［J］. 計算機研究與發展， 2020， 57（9）： 1810.

［14］ WANG X F， HAN Y W， LEUNG V C M， et al. Convergence of edge computing and deep learning： a comprehensive survey［J］. IEEE Communications Surveys amp; Tutorials， 2020， 22（2）： 869.

［15］ WANG J， LIU Y， REN S， et al. Edge computing-based real-time scheduling for digital twin flexible job shop with variable time window［J］. Robotics and Computer： Integrated Manufacturing， 2023， 79： 102435.

［16］ TANG M， WONG V W S. Deep reinforcement learning for task offloading in mobile edge computing systems［J］. IEEE Transactions on Mobile Computing， 2020， 21（6）： 1985.

［17］ YEGANEH S， SANGAR A B， AZIZI S. A novel Q-learning-based hybrid algorithm for the optimal offloading and scheduling in mobile edge computing environments［J］. Journal of Network and Computer Applications， 2023， 214： 103617.

［18］ ZHOUMT，RENTF，DAIZ M， et al. Task scheduling and resource balancing of fog computing in smart factory［J］. Mobile Networks and Applications， 2023， 28： 19.

［19］ CHEN Y W， YOU J Z. Effective radio resource allocation for IoT randomaccessbyusingreinforcementlearning［J］. Journal of Internet Technology， 2022， 23（5）： 1070-1071.

［20］ FAN Y Q， WANG L F， WU W L， et al. Cloud/edge computing resource allocation and pricing for mobile blockchain： an iterative greedy and search approach［J］. IEEE Transactions on Computational Social Systems， 202 8（2）： 461-462.

（責任編輯：劉 飚）