一種資源受限的時延與能耗優化卸載策略

關鍵詞：邊緣計算；多點協作傳輸；vogel；任務卸載；遷移成本

中圖分類號：TP393.01 文獻標志碼：A 文章編號：1671-6841（2025）05-0062-07

DOI：10.13705/j. issn.1671-6841.2023262

Abstract： Ofload decision-making was an important part of data processing. However，most studies ignored the delay and energy consumption generated by collboration between edge servers when determining offload decisions. An algorithm to minimize task processing costs was proposed，to achieve the goals of optimizing costs by minimizing the delay and energy consumption generated during task migration and determining the optimal ofload ratio of sensed data between the cloud and the edge.Firstly，the optimization objective was transformed into a transportation problem with balanced production and sales，and the Vogel algorithm was used to solve the minimum delay and energy consumption of task processing at the edge.Secondly，combined with the delay and energy consumption of task processing in the cloud and the edge，the optimal offloading ratio was solved to minimize the costs of task processing.Finally，Matlab simulation experiments showed that the proposed algorithm reduces the task processng cost by about 18% （20 to 25% compared with other algorithms.

Key words： edge computing； multipoint cooperative transmision; vogel; task offloading； migration costs

0 引言

（mobileedgecomputing，MEC）通過將物聯網等應用程序部署到距離用戶更近的邊緣服務器中，可以有效降低訪問時延與能耗。但是與傳統的云計算相比，邊緣服務器的計算和存儲資源相對有限。如何利用有限的計算資源來滿足用戶需求，提升用戶體

隨著5G/6G移動通信時代的到來，用戶對低時延、低能耗的服務需求不斷增長。移動邊緣計算驗，對邊緣計算的性能尤為重要。一般情況下，用戶將任務發送到距離其最近的邊緣服務器上，但由于未考慮邊緣服務器的計算能力，在用戶密集地區邊緣服務器的任務會出現排隊擁擠的狀況，而用戶稀疏地區邊緣服務器在多數時間計算資源處于空閑狀態，不僅影響用戶的體驗，還造成了資源的嚴重浪費。

另一方面，邊緣服務器之間的相互協作可以將處于擁擠狀態的服務器遷移部分任務至空閑狀態的服務器，從而緩解服務器負載不均衡的情況。同時，隨著邊緣服務器數量的增多，服務器之間的協作開銷也會顯著增加。在邊緣服務器相互協作的場景下，根據任務對計算資源的需求，以降低任務遷移時的時延與能耗為目標，對服務器接收的任務進行遷移調整，制定合理的遷移策略，實現資源的均衡分配，是當前的研究重點。

相關卸載工作中很少考慮多個邊緣服務器協作卸載的情況，本文以邊緣節點的計算能力為約束，提出了一種最小化任務處理成本（minimizationoftaskprocessingcost，MTPC）算法，具體表述如下。首先，考慮將問題表述為一個受邊緣服務器計算能力約束的最優卸載比例問題。其次，使用Vogel法求解任務在邊緣端處理的最小時延與能耗。最后，通過邊緣服務器與云服務器協作處理，求解任務處理的最小成本及最優卸載比例，并與其他算法的任務處理成本及任務卸載比例進行對比。

1相關工作

近年來，邊緣計算卸載[2]受到了廣泛關注。目前對卸載決策的研究主要圍繞降低時延[3-5]、減少能耗[6-7]和同時降低時延和能耗[8-10]進行。

在降低時延方面，文獻［3]提出一種基于深度Q網絡的隱私保護任務卸載算法，減少延遲，提高隱私水平。文獻［4]主要研究在延遲約束下的長期系統平均成本隨機規劃問題，通過交替方向乘子法來實現分布式資源分配。文獻[5]提出基于潛在博弈論的分布式算法來優化物聯網設備的計算卸載問題，以降低時延并最小化最大用戶任務完成時間。

在減少能耗方面，文獻[6]提出一種輪詢回調的節能卸載策略，通過游戲學習算法，實現任務處理的能耗最小化。文獻［7]針對邊緣服務器能源浪費的情況，提出基于集群的能量感知卸載框架，采用自適應策略，減少了能耗，同時節省了相關的計算和存儲資源成本。

在同時降低時延和能耗方面，文獻[8]針對多用戶對多服務器的邊緣計算問題，利用遺傳算法求解卸載策略，降低終端的平均延遲和能耗。文獻[9]提出一種移動邊緣計算視頻緩存策略，通過分支和綁定算法對問題進行優化求解，有效降低系統的時延和能耗。文獻［10］考慮物聯網設備的計算能力有限，通過廣泛搜索算法對計算卸載問題進行求解，實現低能耗與低延遲的目標。

還有一部分工作關注資源分配與任務卸載之間的關系。例如，文獻［11]提出一種基于李雅普諾夫優化的在線移動感知卸載和資源分配算法，在系統服務成本和能量隊列長度之間有效平衡。文獻[12]設計一個混合整數非線性規劃問題，通過塊坐標下降法，對計算資源進行合理分配。文獻［13]提出一種低復雜度的多用戶多基站關聯算法對任務、功率進行分配，從而減少能耗。文獻「14將通信資源分配問題轉化為基于馬爾可夫決策過程的問題，利用深度確定性策略梯度算法對問題進行求解，最小化時延和能耗。

以上研究大多是在單個邊緣服務器上圍繞時延與能耗等指標對任務進行卸載決策，達到降低時延、減少能耗的目的。很少有研究考慮多個邊緣服務器進行協作處理的情況。本文算法是利用邊緣服務器之間的協作機制，通過制定計算卸載策略，對服務器收到的任務進行分配，使得服務器接收的任務量與其自身的計算能力相匹配，同時遷移時延與能耗達到最小，充分利用邊緣節點的計算資源，最后結合任務在云端處理產生的時延與能耗，通過求解最優卸載比例來最小化任務處理所產生的成本。

2 系統模型架構

本文考慮終端設備可將任務數據直接發送至云服務器或邊緣服務器，研究的場景如圖1所示。每個邊緣服務器的通信范圍內覆蓋多個物聯網感知終端。

假設在一個區域內共有 ?_m 個物聯網終端 D_i，i= {1，2，…，m} ， n 個邊緣服務器 E_j，j={1，2，…，n} 。物聯網終端感知大量數據，但任務數據只能發送到云服務器或邊緣服務器進行處理。假設在邊緣服務器的通信范圍內，節點之間可以相互協作。因此，當某邊緣服務器接收的任務數據“超載”時，可以向協作服務器發出協作請求，邊緣服務器通過合理的策略發送部分任務至協作的節點進行計算處理。

圖1協作處理示意圖

Figure1Schematic diagram of collaborativeprocessing

3 問題的建模

假設每一個物聯網終端設備 D_i 需要計算的任務數據量為 δ_i 。在任務的卸載決策中，設置 α_ij 為設備 的任務數據發送至邊緣服務器 E_j 的卸載決策， α_ij∈{0，1} 。當 α_ij=0 時，設備 D_i 不選擇邊緣服務器 E_j 進行任務的卸載；當 α_ij=1 時，設備 D_i 將全部任務卸載至邊緣服務器 E_j 。以上，可將邊緣服務器 E_j 在可通信范圍內收到的全部任務數據量 λ_j 表示為

考慮靜態的條件下，假設每個邊緣服務器的計算資源是一個定值，將邊緣服務器 E_j 在某時刻的計算資源設為 μ_j 。設 θ_jk 為邊緣服務器 E_j 向邊緣服務器 E_k 發送任務數據的比例，其中 0?θ_jk?1 。邊緣服務器可將接收的任務發送至多個邊緣服務器進行協作處理，因此邊緣服務器 E_j 發送的任務數據量（204號 λ_j- 為

同樣的，邊緣服務器 E_j 接收其他邊緣服務器發送的任務數據量 λ_j+ 為

經過邊緣服務器間的協作請求之后，邊緣服務器 E_j 的最終任務數據量 λ_j^′ 為

3.1 時延模型

3.1.1邊緣端處理時延當任務數據在邊緣端進行處理時，產生的時延包括用戶將任務卸載至邊緣服務器時的傳輸時延、服務器與服務器間協作處理的協作時延以及任務在邊緣服務器上的處理時延。

首先可根據香農公式[15]計算用戶將任務卸載至邊緣服務器時的傳輸速率 r₁ ，即

其中： w 表示信道帶寬； P₁ 表示物聯網終端的傳輸功率； l₁ 表示用戶與邊緣服務器之間的距離； α 表示路徑損耗因子； h_?1 表示用戶與邊緣服務器之間的信道增益; N₀ 表示噪聲功率。

因此，用戶將任務卸載至邊緣服務器的傳輸時延 T₁^e 為

其中： δ_?1 表示在邊緣服務器上處理的數據量。

當任務需要邊緣服務器協作處理時，每兩個邊緣服務器之間的協作時延根據服務器之間距離不同而不同。在任務轉發的過程中，邊緣服務器間協作處理產生的協作時延 T₂^e 為

其中： λ_i 表示需要在邊緣服務器間協作處理的任務數據量; r₂ 表示邊緣服務器的傳輸速率。 r₂ 計算為

其中： P₂ 表示邊緣服務器的傳輸功率； l₂ 表示服務器發送方與接收方之間的距離； h₂ 表示邊緣服務器之間的信道增益。

任務在邊緣服務器上產生的處理時延 T₃^e 計算為

其中： δ_?1 表示計算每字節數據需要的CPU運算輪數； f₁ 表示邊緣服務器的CPU計算頻率。

那么任務在邊緣端處理的時延 T₁ 計算為

T_?1=T_?1^e+T_?2^e+T_?3°^e

3.1.2云端處理時延當任務數據在云端進行處理時，產生的時延包括用戶將任務卸載至云服務器時的傳輸時延以及任務在云服務器上處理的處理時延。

首先根據香農公式計算用戶將任務卸載至云服務器時的傳輸速率 r₃ ，即

其中： l₃ 為用戶到云服務器的距離； h₃ 為用戶與云服務器之間的信道增益。

因此用戶將任務卸載至云服務器的傳輸時延T₁^c 為

其中： δ_?2 為需要在云服務器中處理的數據量。

任務在云服務器上產生的處理時延為

其中： λ₂ 表示在云服務器上處理的任務數據量; f₂

表示云服務器的CPU計算頻率。

任務在云端處理的時延為

T_?2=T_?1^c+T_?2^c

綜上，處理所有任務數據產生的時延 T 為

T=T_?1+T_?2O

3.2 能耗模型

3.2.1邊緣端處理能耗當任務數據在邊緣端進行處理時，產生的能耗包括用戶將任務卸載至邊緣服務器時的傳輸能耗、邊緣服務器間協作處理的協作能耗以及任務在邊緣服務器上處理的處理能耗。

數據在邊緣端處理的能耗 E_?1 為

E_?1=P_?1T_?1^e+P_?2T_?2^e+P_?2T_?3^e，

其中： P₁T₁^e 表示用戶將任務卸載至邊緣服務器時產生的傳輸能耗； P₂T₂^e 表示邊緣服務器間協作處理產生的協作能耗； P₂T₃^e 表示任務在邊緣服務器上處理產生的處理能耗。

3.2.2云端處理能耗當任務數據在云端進行處理時，產生的能耗包括用戶將任務卸載至云服務器時的傳輸能耗以及任務在云服務器上處理的能耗。

數據在云端處理的能耗 E₂ 為

其中： P₃ 表示云服務器的傳輸功率； P₁T₁^c 表示用戶將任務卸載至云服務器時的傳輸能耗； P₃T₂^c 表示任務在云服務器上處理的能耗。

綜上，處理所有任務數據產生的能耗 E 為

E=E_?1+E_?2°

3.3 研究問題描述

本文的目標是設計一種合理的卸載策略，將邊緣服務器接收的任務數據量以及自身的計算能力資源作為輸人，通過協調任務在云服務器與邊緣服務器上的處理比例，使服務器的任務配置均衡，任務處理成本達到最小，此時引入時延和能耗的權重變量ω，ω∈[0，1] 。那么權衡時延和能耗的任務處理成本 c 定義為

C=ωT+（1-ω）E

綜合以上分析，本文研究問題可以優化為

minC ，

其中： λ_j^′?μ_j 表示邊緣服務器 E_j 的最終任務數據量要小于等于邊緣服務器 E_j 的計算能力； λ_j?0 表示邊緣服務器 E_j 的最終任務數據量要大于等于 0;μ_j?0 表示邊緣服務器 E_j 的計算能力要大于等于 0 。

問題的求解

本文將上述問題轉化為一個產銷平衡的運輸問題[16]。產地與銷售地都作為運輸點，每個運輸點既可以作為產地生產產品，也可以作為銷售地銷售產品。在解決邊緣服務器任務遷移的問題中，邊緣服務器類似于運輸問題中的產地。同時，邊緣服務器也相當于銷售地。任務既可以在本服務器進行處理，也可以發送至協作服務器進行處理。

本文采用Vogel法確定初始任務分配方案，Vo-gel法是線性規劃中用來編制最優計劃方案的方法，且Vogel法一般能得到一個比西北角法和最小元素法這兩種方法更好的初始基本可行解[17]。下面以三個邊緣服務器A1、A2、A3為例進行說明。假定三個邊緣服務器分別收到的任務數量為7、4、3，計算能力分別為3、6、5。

每兩個邊緣服務器之間的傳輸代價如表1所示，表中的數字代表其對應的橫向邊緣服務器到縱向邊緣服務器的傳輸代價。

表1邊緣服務器間傳輸代價

Table1Transmission cost between different edge servers

有的邊緣服務器任務數量多導致計算能力不足，有的邊緣服務器任務數量少使得計算資源浪費。因此需要制定一個合理的任務分配策略。首先制定任務分配方案。

根據A1～A3收到的任務數量和計算能力，可得到初步的任務處理方案。即卸載至邊緣服務器A1的7個任務需要自身處理3個，邊緣服務器A2協助處理2個，邊緣服務器A3協助處理2個。卸載至邊緣服務器 _A2 的4個任務由其自身處理。卸載至邊緣服務器A3的3個任務由其自身處理。這種分配方式不僅能處理完所有任務而且所產生的代價也是最小的。再結合表1即可求出該任務分配方案的代價。

在求出任務在邊緣服務器上處理的時延與能耗后，結合任務在云服務器上處理的時延與能耗，計算出處理任務所需的最小成本。基于上述分析，MTPC算法的步驟如算法1所示。

算法1 MTPC算法

輸入：計算能力 m ，任務數量 n ，傳輸代價。輸出：最小成本 ∣c∣ 。1）計算任務在云端處理的時延 t₁ 與能耗 e₁ 2）通過Vogel法確定任務在邊緣端分配方案以及計算邊緣端處理時延 t₂ 與能耗 e₂ 3）for i=1 n 4） for j=1：n 5） c_i=ω（t₁^j+t₂^n-j）+（1-ω）（e₁^j+e₂^n-j） 6） end for7） end for8）輸出最小成本

5 仿真實驗與結果分析

此次實驗使用Matlab展示了基站的位置部署并開發一個異構網絡系統來測試所提算法的性能。進行仿真實驗時，在 10×10 的區域內隨機生成100個用戶以及每個邊緣服務器的計算能力，每個用戶產生一個任務并將任務上傳至距離自己最近的邊緣服務器。

在設置的過程中，需要考慮任務數量的總和要小于等于邊緣服務器計算能力的總和。因此在對每個邊緣服務器的計算能力進行賦值時，應使邊緣服務器的計算能力總和為100。本實驗共進行50次，取50次實驗的平均值作為最終實驗結果。實驗的主要參數見表2。

當任務在云服務器上處理時，用戶直接將任務發送至云服務器進行處理。由于用戶與云服務器之間的距離相差很遠，因此將不同用戶與云服務器間的距離假設為一樣。

當任務僅在邊緣服務器上處理時，物聯網設備對距離最近的服務器進行任務卸載，邊緣服務器收到物聯網設備發送的任務之后進行協作處理。

在仿真實驗中，本文算法與邊緣端執行算法、文獻[18]算法、文獻[19]算法進行仿真對比實驗。

表2仿真參數

Table2 Simulationparameter

圖2任務數量對時延的影響Figure2Impactof task number on delay

圖2表示在不同算法下，任務數量與時延之間的關系圖。從圖2中可以看出，隨著任務數量的增多，時延也在增加。任務數量在80個之后，增長的速率開始變快。在相同任務數量的情況下，本文算法的時延優于其他算法的時延。

圖3表示在不同算法下，任務數量與能耗之間的關系圖。從圖中可以看出，隨著任務數量的增多，能耗也在增加。但無論任務數量是多少，在處理任務時本文算法所產生的能耗都優于其他算法所產生的能耗。

圖4表示在權重變量 ω 取值分別為0.2、0.4、0.5、0.6與0.8時，任務數量與成本之間的關系。當 ω 變大時，表明減少時延成為優化的主要目標。從圖4中可以看出，當 ω 取值為0.5時，系統成本最低。

圖5表示當權重變量 ω 取值為0.5時，任務數量與成本之間的關系。隨著任務數量的增多，成本也在不斷增加。本文算法比文獻［18]算法降低約

圖3任務數量對能耗的影響

Figure3Impact of task number on energy consumption

圖4不同權重變量下任務數量對成本的影響 Figure 4 Impact of task number on cost with different weightvariables

圖5任務數量對成本的影響 Figure5Impact of task number on cost

25% 的成本，比文獻［19]算法降低約 18% 的成本。

圖6表示當權重變量 ω 取值為0.5時，不同算法在不同任務數量下，任務在云服務器上處理的比例。從圖6可以看出，當任務數量較少時，文獻[18]算法、文獻[19]算法與本文算法的任務都在邊緣服務器上處理。隨著任務數量的增多，開始采用與云邊緣端結合的方式處理任務。且隨著任務數量的不斷增多，任務在云服務器上處理的比例也在不斷增大。但與其他算法相比，本文算法能在成本更低的情況下，使更多的任務在邊緣端通過邊緣服務器的協作進行處理，使整個邊緣服務器的計算資源得到更充分的利用，只有當任務量足夠大時，才會將任務發送至云端處理，

圖6不同任務數量云處理比例 Figure 6 Proportion of cloud processing for different numberof tasks

6 結語

本文研究了在移動邊緣場景下物聯網應用終端設備感知數據卸載到云服務器或邊緣服務器上所產生的成本最小化問題。通過Vogel法計算任務在邊緣服務器之間進行遷移時的最小時延與能耗。通過改變任務在云服務器與邊緣服務器上處理的數量，計算任務處理所產生的最小成本，并將所提出的算法與其他算法進行了對比。仿真結果表明，本文提出的MTPC算法能夠大幅降低任務處理時產生的成本，同時使整個邊緣服務器的計算資源得到更好的利用。

參考文獻：

[1] 李朋朋，劉紀平，閆浩文，等．基于方向關系矩陣的 空間方向相似性計算改進模型［J]．測繪科學技術學 報，2018，35（2）：216-220. LIPP，LIUJP，YANHW，etal.Animprovedmodel forcalculating the similarity of spatial directionbasedon direction relation matrix[J].Journal of geomaticsscience and technology，2018，35（2）：216-220.

[2] 陳霄，劉巍，陳靜，等．邊緣計算環境下的計算卸載 策略研究[J]．火力與指揮控制，2022，47（1）：7-14， 19. CHEN X， LIU W，CHEN J，et al. Research on computing offload strategy in edge computing environment[J]. Fire control amp; command control，2022，47（1）：7-14， 19.

[3]ZHANG G L，NI S F，ZHAO P. Learning-based joint optimization of energy delay and privacy in multiple-user edge-cloud collaboration MEC systems[J]. IEEE Internet of Things journal，2022，9（2）：1491-1502.

[4］ZHANG W Q， ZHANG G L，MAO S W. Joint parallel offloading and load balancing for cooperative-MEC systems with delay constraints[J]. IEEE transactions on vehicular technology，2022，71（4）：4249-4263.

[5］趙夢遠，郝萬明，楊守義，等．多用戶多邊緣的公平 卸載及優化策略研究［J]．鄭州大學學報（理學版）， 2022，54（5） ： 16-21. ZHAO M Y，HAO W M， YANG SY，et al. Research on multi-edge fair offloading and optimization strategy for multi-user[J]. Journal of Zhengzhou university（natural science edition），2022，54（5）：16-21.

[6]CHEN M J，LIU W，WANG T，et al. A game-based deep reinforcement learning approach for energy-efficient computation in MEC systems[J]. Knowledge-based systems，2022，235：107660.

[7]SAMIR R，EL-HENNAWY H，EL-BADAWY H M. Orchestration of MEC computation jobs and energy consumption challenges in 5G and beyond[J]. IEEE access， 2022，10：18645-18652.

[8]LIAO Z F，PENG J S， XIONG B， et al. Adaptive offloading in mobile-edge computing for ultra-dense celllar networks based on genetic algorithm[J]. Journal of cloud computing，2021，

[9]LI C L， ZHANG Y，SUN QQ，et al. Collaborative caching strategy based on optimization of latency and energy consumption in MEC[J]. Knowledge-based systems， 2021，233：107523.

[10] RAFIQ A， PING W，MIN W， et al. Optimizing energy consumption and Latency based on computation offloading and cell association in MEC enabled industrial IoT environment[C]//The 6th International Conference on Intelligent Computing and Signal Processing. Piscataway：IEEE Press，2021：10-14.

[11]HU H，WANG Q，HU RQ，et al. Mobility-aware offloading and resource allocation in a MEC-enabled IoT network with energy harvesting[J]. IEEE Internet of Things journal，2021，8（24） ： 17541-17556.

[12] ZHENG G Y， XU C，WEN M W，et al. Service caching based aerial cooperative computing and resource allocation in multi-UAV enabled MEC systems[J]. IEEE transactions on vehicular technology，2022，71（10）：10934- 10947.

[13]FANG F，WANG K D，DING Z G，et al. Energy-eficient resource allocation for NOMA-MEC networks with imperfect CSI[J]. IEEE transactions on communications， 2021，69（5）：3436-3449.

[14]LAKEW D S，TRAN A T，DAO NN，et al. Intelligent offloading and resource allocation in HAP-assisted MEC networks[ C]//2O21 International Conference on Information and Communication Technology Convergence. Piscataway：IEEE Press，2021：1582-1587.

[15]LI Z， ZHU Q. An offloading strategy for multi-user energy consumption optimization in multi-MEC scene[J]. KSII transactions on internet and information systems， 2020，14（10）：4025-4041.

[16］王楠，閆琳靜，王瑜．線性規劃模型在運輸問題中的 應用［J]．數學學習與研究，2021（20）：153-154. WANG N，YAN L J，WANG Y. Application of linear programming model in transportation problem[J]. Mathematics learning and research，2021（20）：153-154.

［17］吳建平，吳上民．垂直循環法在運輸問題中的應用 [J]．吉首大學學報（自然科學版），2010，31（4）： 31-34. WU JP，WU S M. Application of vertical circulation method in the transportation problem[J].Journal of Jishou university（natural sciences edition），2010，31 （4）： 31-34.

[18]LIAO L B，LAI Y X，YANG F，et al. Online computation offloading with double reinforcement learning algorithm in mobile edge computing[J]. Journal of parallel and distributed computing，2023，171：28-39.

［19］李順，葛海波，劉林歡，等．移動邊緣計算中的協同 計算卸載策略［J]．計算機工程與應用，2022，58 （21）：83-90. LI S，GE H B，LIU L H，et al. Collaborative computing offloading strategy in mobile edge computing[J]. Computer engineering and applications，2022，58（21）：83- 90.