邊緣計算中動態服務器部署與任務卸載聯合優化算法

中圖分類號：TP393 文獻標志碼：A 文章編號：1001-3695（2025）06-031-1830-08

doi： 10.19734/j. issn.1001-3695.2024.11.0462

Joint optimization algorithm for dynamic server deployment and task offloading in edge computing

BaiWenchao，Lu Xianling? （SchoolofInternetofThings，JiangnanUniversity，WuxiJiangsu214122，China）

Abstract：Inmobileedgecomputing，thefixedlocations of edgeserverdeploymentscanleadtoimbalancedresourceutilizationof edgeservers，resultinginincreasedlatencyandenergyconsumptionduringthetask ofloading process.Toaddressthis issue，thispaperproposedaierarchicalreiforcementlearing-basedjointoptimizationalgorithm.Firstly，itdecomposedthe problemofedge serverplacementand task ofloading and transformedthemintoabi-Markovdecision processThen，itconstructedaglobalintellgentagentmodelforhigher-leveledgeserverdeploymentusingthedeepQ-network，andaccelerated modelconvergencebyintroducingthe K-means algorithmtoprovide high-qualitysamplesforthehigher-layer policy.Itbuilta lower-layer multi-agentmodelfortaskofloadingusingthemulti-agentproximalpolicyoptimizationalgorithm，andimproved trainingstabilitybyintroducingstatenormalizationtoreducethestatesfeaturescalediferencesinthelower-layerpolicy.Finally，itachievedtheultimateoptimizationgoaltroughalternatingoptimizationofthehigher-layerandlower-layerpolicies. Simulationresults indicatethattheproposedalgorithmcanachieveoptimal serverdeploymentandtask ofloading strategies， comparedtorandomstrategiesandotherreinforcementlearningalgorithm，and itdemonstratesgreater benefitsintermsof model training efficiency，target rewards，and load balancing metrics.

Key words：edge computing；task ofloading；edge server deployment；hierarchical reinforcement learning

0 引言

隨著5G和6G技術的高速發展，越來越多的計算密集型應用出現[1]，如虛擬現實和面部識別等。然而，由于資源的限制，大多數移動終端用戶很難處理這些計算密集型任務[2]。在這種情況下，移動邊緣計算（mobileedgecomputing，MEC）將計算和存儲資源帶到移動網絡的邊緣，利用MEC可以使終端運行計算密集型和資源密集型的應用程序，從而減少任務處理延遲和能耗[3]。因此，用戶可以將計算密集型任務卸載到附近的MEC服務器進行計算，也稱為任務卸載，從而減輕繁重的計算工作量[4]。在MEC場景中，邊緣服務器（edge server，ES）是一個至關重要的部分，位于網絡邊緣，靠近終端設備和數據源，負責處理數據和執行計算任務[5]。通常，ES與基站（basestation，BS）或無線接入點集成在一起，這樣可以降低放置成本并提高可靠性。然而，由于建設成本和實際需求，不可能為每個BS配置一個ES。在包含數百或數千個BS的智能城市中，移動設備通過BS訪問邊緣服務器。由于通信網絡規模龐大，低效的ES部署和不合理的任務卸載將導致長時間的傳輸延遲和ES工作負載的不平衡，造成邊緣服務器資源利用不充分[6]。所以，合理部署ES和優化任務卸載策略，對提高MEC系統的整體性能以及提升用戶體驗和服務質量至關重要。關于ES部署與任務卸載的問題，大多數現有的工作都假設ES已經部署在BS或其他確定位置，通過設計任務卸載方案或計算資源分配方案，以優化處理延遲[7，8]能耗[9，10]用戶體驗[11]和系統成本[12]。而有些工作集中在確定任務處理方式下ES的部署問題。如文獻[13]通過引入雙Q學習和延遲策略更新的強化學習算法，處理動態MEC場景下的邊緣服務器放置問題，實現了最小化MEC系統能耗；文獻[14]提出一種二進制版本混合算法，在同時優化網絡延遲、覆蓋重疊控制和MEC運營支出的模型下，獲得ES放置近似解；文獻［15]研究了基于決斗雙深度Q網絡（deepQnetwork，DQN）的放置算法和基于近端策略優化的放置算法，解決考慮時變網絡狀態和放置成本的高效智能動態邊緣服務器放置問題;文獻［16]提出一種基于集群和啟發式算法相結合的邊緣服務器布局策略，實現了更好的工作負載均衡。

上述文獻將服務放置問題與任務卸載問題分開研究。然而在實際中，由于服務器部署影響任務的卸載，而任務的卸載策略也會影響之后服務器的再次部署，兩個問題之間存在耦合關系，不能完全分開獨立研究，需要對問題進行聯合優化，并且這類聯合優化問題的計算復雜度會隨著任務規模的增加呈指數型增長，而傳統的非線性規劃[17]、整數線性規劃[18]與啟發式算法[19]等面對這類NP-hard 問題，存在求解方面的困難[20]對于這類層次變化的決策問題，單一的強化學習（reinforcementlearning，RL）算法無法靈活且高效解決，而分層強化學習通過引入層次結構，構建上層服務器放置網絡與下層任務卸載網絡，有效處理復雜和多階段任務，具有更好的擴展性和學習效率。文獻[21]通過將調度問題分解為兩層子問題，利用分層強化學習交替優化，以獲取動態環境下MEC大規模無人機實時調度策略。文獻[22]提出一種基于智能分層切片技術的數字孿生傳感信息同步策略。使用優先經驗回放的多智體深度確定性梯度算法學習下層控制策略，使用雙深度Q網絡學習上層控制策略，有效解決了切片無線資源配置以及傳感信息同步聯合優化問題。文獻[23]在星際爭霸2人工智能研究環境（StarCraftIIlearningenvironment，SC2LE）下，提出具有可解釋子任務的分層多智能體強化學習算法，有效解決了異構智能體合作的復雜場景下多智能體行為可解釋性挑戰，提高了訓練收斂速度。上述研究已經充分證明分層強化學習在解決大規模和高維度問題時具有合理有效性。本文基于分層強化學習思想，提出一種邊緣服務器部署與任務卸載聯合優化算法，旨在同時實現動態場景下MEC系統的整體系統效用與用戶設備個體效用最大化。本文的主要貢獻如下：

a）在計算資源有限與網絡環境變化的情況下，構建出可動態調整的邊緣服務器布局與任務卸載模型，提出使每個計算任務的平均效用與系統整體效用最大化的目標。

b）將優化問題分解為兩層子問題，進而轉換為雙馬爾可夫順序決策過程，并提出一種基于分層強化學習的聯合優化算法。通過引人K-means為上層DQN提供先驗知識加速模型收斂和優化模型學習過程，利用狀態歸一化改善下層多智能體近端策略優化（multi-agentproximalpolicyoptimization，MAPPO）的訓練效果和收斂速度，通過上下層策略交替優化對聯合優化問題進行求解。

c）通過設置不同物理參數與網絡參數進行廣泛實驗，結果表明，所提算法能有效解決邊緣服務器部署與任務卸載聯合優化問題，比隨機算法與其他強化學習算法有實質性的性能改進。

1系統模型和問題描述

1.1 網絡模型

如圖1左側所示，本文考慮一個支持MEC的蜂窩網絡，該網絡由 N 個移動設備（mobiledevice，MD） Ω，M 個BS和 K 個等待部署的 ES 組成。其中，MD 用集合 U={u₁，u₂，…，u_i，… u_N} 表示，且隨機分布在邊長為 L_max 的矩形區域中，BS用集合β={b₁，b₂，…，b_k，…，b_M} 表示，邊緣服務器用集合 {ε={σ_e1 e₂，…，e_j，…，e_K} 表示。整個通信時間被劃分為 T 個相等時隙，移動設備在每個時隙開始隨機產生一個計算任務，任務集用集合 表示，其中 D^t={D₁^t，D₂^t，…，D_N^t} 表示計算任務的數據大小， 表示完成任務所需CPU周期數。設備產生計算任務之后，需要在BS上對邊緣服務器進行部署，以更好地確定任務卸載決策，假設計算任務不可分割，每個計算任務可以選擇通過BS將任務卸載到ES上執行或者在本地執行。圖1右側分別展示了兩種服務器部署場景，可以看到不同的部署策略會導致計算任務與服務器之間的相對距離產生改變，從而移動設備會產生不同的卸載策略。

1.2 通信模型

本文考慮設備移動性和通信信道間的干擾[24]，設備 u_i 在χ_t 時隙的位置為 p_i^t={x_i^t，y_i^t} ，下個時隙， u_i 的位置為 p_i^t+1={x_i^t+ v_iΔ_Tcosγ_i（t），y_i^t+v_iΔ_Tsinγ_i（t）∣ ，其中 Δ_?T 是時隙長度， γ_i（t）∈ [0，2π] 是 u_i 的移動方向， v_i 為 u_i 的移動速度，邊緣服務器 e_j 在每個時隙的位置表示為 P_j^t={X_j^t，Y_j^t} ，每個時隙 e_j 的位置會根據部署決策作相應改變，BS的位置固定，用 P_BS={P₁，… P_k，…，P_?M} 表示， u_i 與部署 e_j 的BS之間的信道增益可以定義為 g_i^t=β₀d_i^t ，其中， β₀ 為參考距離為 1m 時的信道功率增益， 為 u_i 與部署 e_j 的BS之間的歐氏距離。本文采用正交頻分多址協議避免MD之間的相互干擾，每個部署的ES會同時接收多個MD的計算任務數據，與之相連的BS上的總無線傳輸帶寬被卸載到此ES上的MD等分。當共享無線鏈路的MD數量發生變化時，帶寬進行重新分配。MD與ES之間的上行鏈路傳輸速率計算公式為

其中： p_i 為 u_i 的發送功率； N₀ 為高斯白噪聲功率； B 為信道帶寬； I_j 為當前時隙卸載到 e_j 的計算任務數量。

1.3計算模型

每個時隙開始，系統會執行部署策略，確定ES在當前時隙的具體位置，在此過程中每個ES由原來位置到新部署位置的遷移會產生相應的時間與經濟成本[25]，對于卸載任務的計算來說不可忽略，所以邊緣服務器部署成本定義為

其中 ?β^t∈{0，1} 表示在時隙 χ_t 時邊緣服務器 e_j 的部署決策， β^{t °}=1 表示 e_j 重新部署， B^t=0 則表示 e_j 位置不變； ξ 為單位距離部署成本。通常任務卸載方式包括完全卸載和部分卸載，部分卸載可能會破壞存在復雜依賴關系的任務數據，所以本文采用完全卸載方式來處理 u_i 產生的計算任務Ω。 a_i^t∈{0，1，… ∣N∣ 表示在時隙 χ_t 時 Q_i^t 的卸載決策， a_i^t=0 表示計算任務 在本地處理， a_i^t=j，j∈{1，…，K} 表示任務 i卸載到邊緣服務器e_j 上計算。在時隙 χ_t ，本地計算產生的時延表示為

其中： S_i^t 表示計算任務所需要的CPU周期數 ：f⁰_i 為 u_i 本地的計算頻率。本地計算產生的能耗表示為

E_loc，i^t=κ_i（f_i⁰）³T_loc，i^t

其中： κ_i 表示設備功率系數，由設備CPU芯片架構所決定。因此本地計算任務的整體效用可定義為

Q_loc，i^t=ηT_loc，i^t+（1-η）E_loc，i^t

其中： η 為時延與能耗的權重系數。

在時隙 χ_t ，對于卸載任務來說，服務器返回的計算結果通常很小，所以反饋時間與反饋能耗可忽略不計。因此，任務卸載到邊緣服務器上計算產生的時延包括任務傳輸時延和卸載計算時延，任務傳輸時延和卸載計算時延分別表示為

其中 表示邊緣服務器 e_j 為卸載任務 分配的計算頻率。同理，任務卸載到邊緣服務器上處理的能耗包括任務傳輸能耗和卸載計算能耗，分別表示為

其中： κ_j 表示邊緣服務器 e_j 功率系數。因此卸載計算任務的整體效用可以定義為

Q_off，i^t=ηT_off，i^t+（1-η）E_off，i^t=η（T_man，i^t+T_mec，i^t）+（1-η）（E_tran，i^t+E_mec，i^t）

1.4 問題構建

本文從任務處理的整體效用來構建問題模型，在動態移動邊緣計算應用場景中，計算任務的時延、能耗以及邊緣服務器的部署成本影響到用戶體驗與服務商運營成本。受文獻[14]啟發，本文通過對時延、能耗和部署成本進行綜合考慮，將任務計算效用和邊緣服務器部署成本通過加權求平均來建立目標函數，定義如式（9）所示。

t.C1：a_i^t∈{0，1，…，K}，C2：β^t∈{0，1}，

C5：0?x_i^t?L_max，C6：0?y_i^t?L_max

C7：P_j^t∈{P₁，…，P_M}

其中： λ 為計算效用與部署成本的權重系數；C1、C2表示邊緣服務器部署與任務卸載決策約束；C3、C4表示計算任務所能容忍的時延約束與能耗約束；C5、C6表示移動用戶移動范圍約束；C7表示邊緣服務器部署必須與基站相連。

混合整數非線性規劃問題式（9）由于其離散的二進制服務器部署變量與任務卸載變量高度耦合而難以求解。此外，MD在各個時隙的分布是動態變化的，邊緣服務器每時隙部署一次，任務卸載決策必須實時完成，所以考慮到決策動作先后順序的特點，本文將整個系統優化問題分層分解為兩個子問題：

a）邊緣服務器部署優化問題P1。由于移動設備可以在很大范圍內移動到新位置，對于計算資源有限的場景來說，移動設備與邊緣服務器之間的距離是影響信道增益的關鍵，在卸載策略中，該參數最終會影響卸載任務的時延和能耗，同時邊緣服務器部署產生的成本也是整體效用的一部分，所以應該根據當前時隙用戶位置分布與上個時隙的部署位置來正確選擇邊緣服務器的新位置，以獲得最優時隙整體效益，所以問題 P1 定義為

b）卸載優化問題 P2 。在每個時隙中，每個MD根據已部

署邊緣服務器的位置以及當前時隙中自己的位置與計算任務等信息，確定卸載決策，使所有MD的平均效用最小。問題P2定義為

2基于分層強化學習的聯合優化算法

上述兩個子問題都為混合整數非線性規劃問題，傳統方法難以解決。因此，本文將上述優化問題轉換為雙馬爾可夫決策過程（Markovdecisionprocess，MDP），然后根據分層強化學習架構提出一種HKDMP（hierarchicalreinforcementlearningbasedonDQNwithK-meansandMAPPO，HKDMP）算法進行求解。針對任務卸載問題，HKDMP采用MAPPO來獲得下層最優卸載策略；對于邊緣服務器部署問題，HKDMP使用K-means指導DQN算法來獲得上層服務器最優部署策略。

2.1 MDP過程建立

馬爾可夫決策過程是一種數學模型，用于描述在決策環境中的最優決策問題，標準的MDP由一個五元組 （s，A，P，R γ ）組成，其中 s 是狀態空間， A 是動作空間， P 是狀態轉移概率，R 是獎勵函數， γ 是折扣因子， γ∈[0，1] 。本文是雙MDP過程，對于上層邊緣服務器部署策略，構建一個全局可觀察智能體，將MD的任務與位置坐標、ES位置坐標和通過K-means聚類得到的待部署位置信息視為狀態，把是否部署視為動作。

a）上層策略狀態空間：在每個時隙開始，全局智能體將當前時隙任務信息、聚類得到的服務器待部署位置與上一時隙服務器部署位置作為觀察到的狀態，狀態空間可定義為

s_t^h={D^t，S^t，{p₁^t，…，p_N^t}，{P₁^t-1，…，P_K^t-1}，P_pre^t}

其中 ?P_pre^t={P_pre，1^t，…，P_pre，K^t} 表示當前時隙通過聚類得到的服務器待部署位置。

b）上層策略動作空間：智能體根據當前時隙所觀察到的 狀態來作出是否部署的離散動作決策，動作空間可以定義為

a_t^h=β^t

c）上層策略獎勵函數：作為全局優化策略，目標是將整體效用達到最大化，考慮到本文優化目標為最小化計算時延、能耗與部署成本，所以取目標函數的相反數作為獎勵函數，定義為

對于下層策略，為了使所有MD的平均效用最小，所以將每個MD都視作一個智能體，在上層給出服務器部署方案的基礎上，每個智能體將自己的任務信息與服務器位置信息作為狀態，把卸載決策作為動作。

a）下層策略狀態空間：在上層服務器部署策略指導下，由于部分可觀察性，智能體 u_i 的局部觀測狀態由四個部分組成，分別為 χ_t 時刻產生的任務數據量大小 D_i^t 、計算任務所需要的CPU周期數 S_i^t 、智能體 u_i 的位置坐標及每個邊緣服務器 e_j 的位置坐標 {P₁^t，…，P_K^t} ，所以智能體 u_i 的局部觀測空間為 s_i，t^l= {D_i^t，S_i^t，p_i^t，P₁^t，…，P_K^t} ，環境的全局狀態 S_t^l 為所有智能體局部觀測信息的拼接

S_t^l=（s_1，t^l，s_2，t^l，…，s_N，t^l）

b）下層策略動作空間：每個智能體根據各自狀態信息 s_i，t^l 作出相應卸載決策，智能體的卸載決策對應于計算任務的執行位置，所以智能體 u_i 對應的動作空間定義為 a_i，t^l∈{0，1，… |K} ， a_i，t^l=0 表示計算任務 ‘在本地處理， a_i，t^l=j，j∈{1，…，K} 表示任務 卸載到邊緣服務器 e_j 上計算。所有智能體的聯合動作空間為

A_t^l=（a_1，t^l，a_2，t^l，…，a_N，t^l）

c）下層策略獎勵函數：由于下層策略為任務卸載策略，目標為最小化每個任務執行時延與能耗，所以下層策略使用任務執行時延 T_i^? 與能耗 E_i^t 的加權和的相反數作為獎勵函數，則 Ψ_t 時刻，智能體 u_i 的獎勵函數表示為 r_i，t^l=-[μT_i^t+（?1-μ）E_i^t] ，所以系統整體獎勵函數集合為

R_t^l=（r_1，t^l，r_2，t^l，…，r_N，t^l）

2.2基于分層強化學習的聯合優化算法

2.2.1上層邊緣服務器放置網絡

為解決ES部署問題，算法上層結構采用DQN來得到邊緣服務器最佳部署策略，由于環境動作空間較大，全局智能體難以在合理時間內充分探索所有可能的狀態-動作對。所以本文使用聚類思想，通過任務位置聚類將到達任務根據服務器數量劃分為不同的簇，從而來指導全局智能體得到是否部署的最佳部署策略。由于BS的位置與數量是固定且已知的，首先將當前時隙所有產生計算任務的MD的位置根據ES數量進行K-means聚類，在每個集群中，通過計算每個聚類中心與每個BS的歐氏距離 ，將距離集群中心最近的BS作為ES待部署位置，使得BS到計算任務的平均距離最小，從而降低卸載任務的傳輸時延。然后全局智能體與環境進行交互，從而獲得上層策略狀態空間和動作空間。將交互得到的狀態與動作放入經驗回放池h_buffer中，訓練時從h_buffer中隨機抽取小批量元組來更新DQN參數，最后得到輸出最優服務器部署策略的網絡模型。如圖2左側所示，本文采用兩個結構相同、參數不同的網絡分別作為預測網絡和目標網絡，預測網絡與環境交互用于估計當前狀態動作對的價值函數并進行智能體決策以及參數更新，目標網絡用于參與預測網絡的參數更新并且使其訓練穩定。DQN算法的目標是通過最大化狀態價值函數來得到最大化累積獎勵，根據Bellman最優方程定義 Q^* 為最優動作價值函數，則

Q^*（s_t^h，a_t^h;θ）=E[r_t^h+γmax_at+1^hQ^*（s_t+1^h，a_t+1^h;θ^′）]

若對于下一個狀態 s_t+1^h 的所有可能動作 a_t+1^h 都已知，那么當前優化目標為選擇下個狀態所有動作中最大的狀態動作價值。

y_t^h=r_t^h+γmax_at+1^hQ（s_t+1^h，a_t+1^h;θ^'）

通過更新預測網絡狀態動作價值函數不斷迭代。

在每次迭代中，DQN通過優化均方誤差損失函數，使得目標收斂于最優動作價值函數。損失函數定義如下：

其中 ：y_i=r_t^h+γ^hmax_at+1^hQ（s_t+1^h，a_t+1^h;θ_t^'） 為第 i 次迭代的目標。然后，利用梯度下降公式來優化損失函數。

abla_θiL_i（θ_i）=E[（y-Q（s_t^h，a_t^h;θ_i））?_θiQ（s_t^h，a_t^h;θ_i）]

2.2.2下層任務卸載網絡

在實際環境中，服務器上的任務負載大小對計算任務的時延和能耗有很大影響，單個任務卸載策略的改變會導致信道與計算資源發生改變，從而影響其他計算任務的時延與能耗。除此之外，在考慮每個任務卸載策略好壞的同時，還要使系統整體性能達到最優。對于這種存在競爭-合作關系的問題，本文在下層任務卸載策略引入MAPPO算法，將每個MD視作一個智能體，對每個智能體的狀態空間進行歸一化處理，并采用“集中式訓練，分布式執行\"結構，使每個智能體作出最優卸載決策。

如圖2右側所示，下層算法采用actor-critic網絡模型，并由 2N 個結構相同的策略網絡和 2N 個結構相同的價值網絡組成，每個智能體的策略網絡負責生成當前狀態 s_i，t^l 下的動作分布 π_θi^π（a_i，t^l|s_i，t^l） ，根據得到的動作訓練參數 θ_i^π ，并賦值給目標策略網絡。每個智能體的價值網絡負責評估所有智能體當前狀態 s_i，t^l 的價值函數 Vφ_i（s_i，t^l） ，目標價值網絡預測智能體下個狀態 s_i，t+1^l 的價值函數 Vφ_i（s_i，t+1^l） ，以指導價值函數優化。由于狀態 s_i，t^l 特征較多且尺度范圍大，如果直接將未經歸一化的數據輸入到神經網絡中，會導致梯度不穩定以及參數更新困難，所以需要對狀態 s_i，t^l 進行歸一化處理，將狀態中每個變量減去范圍內最小值再除以其最大值與最小值的差作為歸一化處理后的狀態變量，如式（23）所示。

同上層邊緣服務器部署策略一樣，下層策略優化的目標是使每個智能體的累積折扣回報達到最大化，得到最優策略網絡參數。

其中：目標函數 J（θ_i^π） 為累計折扣獎勵的期望，定義為

為穩定訓練過程和降低梯度估計方差。引入優勢函數替

代策略梯度中的累計折扣獎勵，定義如下：

其中： δ_i^t=r_i^l+γ^lV（s_i，t+1^l）-V（s_i，t^l） 為TD誤差； λ 為平滑參數； γ^l 為回報折扣因子；策略梯度的更新表示為

此外，利用重要性采樣和裁剪策略來提高訓練效率和穩定性，actor網絡的損失函數構造如下：

其中：

為新舊策略的重要性采樣比值，表示兩個網絡的差異程度。裁剪策略利用clip函數防止產生因策略網絡參數過度更新而導致訓練不穩定問題， ε 為剪裁范圍參數，本文設置為0.2。價值網絡的損失函數為

其中： 為價值網絡的估計。

通過梯度下降對參數 θ 和 ? 進行更新：

經過固定步長后對舊actor和舊critic網絡進行更新：

其中： α_θ 和 α_? 是神經網絡的學習率。

算法1基于分層強化學習的聯合優化算法

輸入：任務位置集合 {p₁^t，…，p_N^t} ，計算任務集合 {D^t，S^t} ，ES位置集合 {P₁^t，…，P_j^t} ，BS位置集合 P_BS ，ES數量 K （204號

輸出：最佳ES部署策略 a_t^h 和最佳任務卸載策略 a_i，t^l 初始化網絡參數 ，經驗回放池h_buffer、樣本批次大小 N_batch 以及訓練步數 stepforepisode Ω=1，2，…，N for t=1，2，…，T 對任務位置 {p₁^t，…，p_N^t} 使用K-means 聚類返回簇 {S₁，… S_K} 和質心 {c₁，…，c_K} 計算每個質心 c_i 與每個BS的歐氏距離： dist（P_k，c_i）= （204號 將距離質心最小的 BS作為服務器待部署位置： P_pre，j^t=arg_- min dist {P_k，c_j} 返回所有 ES 待部署位置集合 {P_pre，1^t，…，P_pre，K^t} （20初始化任務信息 以及初始狀態 s₀^h （204號使用 ε -greedy策略選擇部署動作 a_t^h 執行動作 a_t^h ，得到即時獎勵 r_t^h 和下一個狀態 s_t+1^h ，以及時隙結束標志done將 （s_t^h，a_t^h，r_t^h，s_t+1^h ，done）存儲到經驗池中step=step+1 證 stepgt;N_batch ：從經驗回放池中隨機采樣批次大小為 N_batch 的樣本根據式（18）通過樣本計算目標 Q^*（s_t^h，a_t^h;θ^′） 根據式（20）計算當前 Q（s_t^h，a_t^h;θ） （2根據式（21）計算均方誤差損失函數 L_i（θ_i） 使用梯度下降算法更新Q網絡參數 θ：θ←θ–α?_θL（θ） 每隔固定步數將Q網絡的參數復制到目標網絡： θ^′θ end if初始化下層網絡中每個智能體觀察狀態 s₀^h for i=1，2，…，n

觀測狀態歸一化 智能體 u_i 根據 按照策略 π_θi 采取動作 a_i，t^l 執行動作 a_i，t^l 得到即時獎勵 r_i，t^l 下一個狀態 s_i，t+1^l 和時隙結束標志done使用價值網絡和目標價值網絡計算當前狀態價值 V_?i （s_i，t^l） 和下個狀態的價值 根據式（26）使用計算優勢函數 根據式（28）計算策略網絡損失函數 L^CLIP（θ_i^π） （204根據式（30）計算價值網絡損失函數 L^VF（?_i） 根據式（31）更新策略網絡參數 θ_i^π 根據式（32）更新價值網絡參數 ?_i 根據式（33）和（34）更新目標網絡參數end forend forend for

2.3算法復雜度分析

HKDMP算法復雜度由上下兩層網絡的復雜度構成，首先，對于上層策略，假設 T_i^q 為DQN第 i 層中的神經元數量，所以計算復雜度可以寫成：

其中： L_q 是上層網絡的總層數，因此上層網絡的計算復雜度為

O（N_batch?Z?T?（ζ_q+G））

其中： N_batch 為訓練批量大小； Z 為迭代次數； G 表示Adam優化器在梯度計算與反向傳播過程中的計算復雜度。對于下層策略，假設 T_i^q 和 T_i^c 分別為actor和critic第 i 層全連接層中的神經元數量，所以其復雜度分別為

同理 ，L_a 和 L_c 是下層網絡中actor網絡和critic網絡的總層數，下層網絡的計算復雜度為

O（Z?T?（N?（ζ_a+ζ_c）+G）））

其中： N 為智能體數量。所以，結合上下層網絡結構，HKDMP算法的計算復雜度為

O（Z?T?（N_bateh?（ζ_q+G）+（N?（ζ_a+ζ_c）+G）））

3 實驗結果與分析

3.1評價指標

為了評估HKDMP算法的性能，本文采用負載均衡指標和平均任務獎勵作為評價指標。使用負載均衡指標來評價在算法訓練過程中所有MD任務卸載的負載均衡效用，統計平均每個服務器上任務處理個數，具體按式（41）計算。

其中： L_j^t 為卸載到 e_j 上的任務數量； 為卸載到每個邊緣服務器上的平均任務數量。

平均任務獎勵是訓練過程中所有任務獲得的平均獎勵，主要用于評估多智能體算法的整體性能，具體按式（42）計算。

3.2 仿真實驗設置

本節通過仿真實驗來評估HKDMP算法性能。仿真實驗在基于Python3.6和PyTorch1.8的環境上進行，并使用NVIDIA-A100-PCIE-40GB對智能體進行訓練。環境設定移動設備MD在 1 000m×1 000m 區域內隨機分布，設備的移動速度 v_i 為 17m/s ，移動方向隨機產生，區域內垂直與水平方向每

200m 放置一個基站，共計16個基站，時隙個數 T 為100，每個時隙移動設備的計算任務 隨機生成，具體參數設置參考文獻[24，26]，如表1與2所示。訓練輪次 Z 為1000，上下層模型每個時隙對網絡參數進行一次更新。

3.3 收斂性分析

圖3展示了不同學習率下系統平均時隙獎勵隨訓練次數的變化。可以看到，當上層網絡與下層網絡的學習率都為0.0005時，系統獎勵的收斂效果達到最優。當上層網絡的學習率較大時，在訓練初期，獎勵收斂較快，在訓練50＼～200輪之間，由于學習率較大，使參數更新方向頻繁變化，獎勵出現波動現象。當上層網絡的學習率較小時，在訓練130＼～270輪時獎勵下降，模型陷入鞍點，智能體參數更新緩慢導致策略的改進停滯，但隨著訓練次數增加，模型逐漸積累了足夠多的有效更新，導致獎勵再次上升。當下層網絡學習率較大時，參數更新步長太大，模型的損失函數在不同方向上大幅波動，導致前期無法得到最大獎勵。當下層網絡的學習率較小時，導致模型收斂速度較慢，訓練時間較長。

3.4性能比較

本節通過設計對比實驗來驗證HKDMP算法的高效性，將HKDMP與以下幾種算法比較：a）HDMP（hierarchicalreinforcementleamingbasedonDQNandMAPPO）算法，該算法與HKDMP相比，上層策略中未使用K-means聚類;b）HKDMD（hierarchicalrein-forcementlearningbasedonDQNwithK-meansandMADDPG）算法[22]，與HKDMP相比，該算法采用多智能體深度確定性策略梯度（multi-agent deep deterministic policy gradient，MADDPG）構建下層任務卸載策略;c）HKDP（hierarchicalreinforcementlearning based on DQN with K-means and PPO）算法[21]，相比于HKDMP，該算法采用單智能體近端策略優化（proximalpolicyoptimization，PPO）構建下層任務卸載策略;d）Random算法，算法的邊緣服務器放置策略與任務卸載策略均為隨機策略。首先，在表1和2所示的參數環境下，對比了各個算法的累計獎勵收斂情況。然后，分析了不同算法隨移動設備數量、任務大小變化時的性能表現。圖4展示了不同算法的累計獎勵隨訓練次數的變化，整體上HKDMP表現最好。HDMP算法由于算法結構與HKDMP相同，所以最終獎勵收斂與HKDMP相近，但由于其未增加K-means指導，所以在訓練前200輪左右，未能找到適合的邊緣服務器放置策略，獎勵收斂速度較慢；HK-DP算法由于下層策略采取單智能體算法，只使用局部狀態信息進行critic網絡更新，未能考慮到其他智能體的影響，導致無法找到最優任務卸載策略；HKDMD在訓練前30輪的獎勵呈下降趨勢，但之后HKDMD的收斂速度快于其他算法，因為HKDMD算法下層策略采用確定性策略梯度方法更新，更新過程中不需要頻繁的策略采樣，減少了更新步驟的計算負擔，其他RL算法的下層策略基于PPO，使用裁剪策略梯度方法保證策略的穩定性和收斂性，但限制了更新幅度，導致收斂速度較慢，但HKDMD確定性策略因為探索不足而陷入局部最優解，導致最終的收斂獎勵表現不如HKDMP。

圖5對比了不同移動設備數量下各個算法的時延、能耗與放置成本。當移動設備數量在6＼～14個變化時，隨著設備數量的增加，任務的計算時延、計算能耗在相應增加，因為每個智能體在環境中的行為會不斷改變其他智能體的策略選擇，隨著智能體數量增多，這種相互影響導致環境對每個智能體來說變得非平穩，從而導致策略學習變得更加困難和不穩定，系統獎勵下降，但HKDMP時延、能耗與平均放置成本的綜合水平都能達到最優的性能。在圖5（a）和（b）中，當設備數量為14時，相較于其他四種算法，HKDMP的時延分別減小 1.1% 、 7.3% 、3.8% 和 22.1% ，HKDMP的能耗分別減小 1.1% 13.2% 5.3%和 39.8% 。由于放置成本受環境動態變化影響較大，而且在上層邊緣服務器放置策略中是優化目標的一部分，所以在圖5（c）中，相對于Random算法，其他RL算法在放置成本上有更好的表現。圖6評估了不同移動設備數量下各個算法的負載均衡指標與平均任務獎勵。圖6（a）中，隨著設備數量增加，每種算法的負載均衡指標也相應增加，其中，HKDMP算法的負載均衡性能最好，當設備數量為14個時，較之其他算法，HKDMP的負載均衡指標分別提高 18.7%.46.7%.64.0% 和80.8% 。圖6（b）中，隨著設備數量增加，網絡結構的狀態空間和動作空間變得更加龐大，網絡訓練需要更多時間和數據來找到最優策略，同時系統計算資源競爭加劇，負載均衡變得復雜，影響任務執行時延與能耗，每種算法所獲得的任務平均獎勵相應減少。當設備數量為14個時，相較于其他算法，HKDMP的任務平均獎勵分別提高 1.2% 6.2% .12.5% 和 25.6% 。

圖7對比了在不同任務大小下各個算法的時延、能耗與放置成本，當任務大小由[0＼～1]MB到[4＼～5]MB變化時，隨著任務大小增加，時延、能耗、服務器放置成本也在相應增加。當計算任務為[0＼～1]MB時，對于計算量較低的小任務，不論是本地計算還是卸載到邊緣服務器，執行時間都較短，不同算法之間難以顯現出顯著差異，每種算法性能相近。隨著計算任務增大，每種算法的時延與能耗都相應增大，各個算法之間性能差距愈加明顯，其中HKDMP在能耗、時延與服務器放置成本方面都達到最好性能。從圖7可以看到，當任務大小為［4＼～5]MB時，相較其他四種算法，所提算法的時延分別減小 0.1% 、2.9% 5. 2% 和11. 5% ；所提方案的能耗分別減小 0.1% 、9.3% 、15. 3% 和 20.8% ；所提方案的邊緣服務器放置成本分別減小 14.1% 44.7% 59.1% 和 82.5% 。

圖8展示了不同任務大小下各個算法的負載均衡指標與任務平均獎勵。圖8（a）中，隨著任務大小增加，Random的負載均衡指標一直保持較高數值，且幾乎沒有改變，其他RL算法的負載均衡指標在相應提高，因為隨著任務大小增加，RL算法更傾向于將任務卸載到邊緣服務器上進行計算從而降低任務計算時延和計算能耗，所以其下層策略的探索動作空間變小，系統不再需要復雜地評估多種任務分配路徑，更容易實現負載均衡。當任務大小為[4＼～5]MB時，相較于其他算法，HKDMP的負載均衡指標分別提高 12.1% ） 46.6% 、66. 1% 和

88.8% 。圖8（b）中，隨著任務大小增加，單個任務計算需求變大，導致系統資源緊張，同時消耗更多能量，影響任務的執行時延與能耗，所以任務平均獎勵相應減少。其中HKDMP算法能夠獲得環境最大獎勵，當任務大小為[4＼～5]MB時，相較其他四種方案平均任務獎勵分別提高1.8%、7.0% .8.8% 和 14.4% 。

圖9對比了在不同任務大小下各個算法的時延、能耗與放置成本，隨著邊緣服務器數量的增加，每個算法得到的任務平均時延與能耗相應減小，服務器放置成本相應增加。因為邊緣服務器數量的增加使邊緣服務器更靠近移動設備，計算任務更傾向于卸載到距離近的服務器計算，且更多的邊緣服務器會分擔計算任務，避免了少數服務器過載以及網絡擁塞，從而降低任務的傳輸時延與傳輸能耗。當服務器數量為2時，相較于其他四種算法，HKDMP的任務計算時延分別減小 0.9%6.3%8.9% 、19.4% ，計算能耗以及服務器放置成本方面都得到較優策略。

圖10展示了不同邊緣服務器數量下各個算法的負載均衡指標與任務平均獎勵。圖10（a）中，隨著邊緣服務器數量的增加，每個服務器上所承擔的計算任務數量下降，但服務器之間的任務量差異相應增加，每個算法得到的負載均衡指標也相應增加，當服務器數量為5時，HKDMP仍能得到最優的負載均衡指標，相比于其他四種方法，分別提高了5. 2% 、15. 7% 、21.3%.44.1% 。圖10（b）中，隨著邊緣服務器數量的增加，計算任務能夠更靠近邊緣服務器，任務卸載能夠獲得更優的計算時延和計算能耗，所以每個算法獲得的平均任務獎勵相應提高，且差距越來越小，當服務器數量為2時，相較其他四種方案，HKDMP算法平均任務獎勵分別提高 0.8%2.6%.6.1% 和 16.7% 。

4結束語

本文針對動態邊緣計算場景，研究了一種邊緣服務器部署與任務卸載聯合優化算法。其中，邊緣服務器會根據移動設備的分布而部署到相應位置，移動設備可以將產生的計算任務卸載到邊緣服務器計算或在本地執行，并以最小化每個MD的平均任務延遲、計算能耗和部署成本為目標。為了合理且高效地求解，本文將優化問題分層分解為放置優化子問題和卸載優化子問題，并提出一種基于分層強化學習的聯合優化算法HKDMP，上層邊緣服務器部署策略采用K-means和DQN相結合的方法實現整體效用最大化，下層任務卸載策略采用MAPPO使得每個移動設備都能夠獲得最大卸載效益。仿真結果表明，在不同的參數設置下，相比于隨機算法和其他RL算法，HKDMP可以在收斂效率、個體平均效用和整體效用方面實現令人滿意的性能改進。然而，在未來工作中，仍需進一步開展研究以解決邊緣設備訪問量產生突變，導致邊緣服務器頻繁遷移和服務網絡壓力過大的問題。此外，探索其他場景以實現算法普適性具有深遠的意義，例如部分卸載、無線能量收集和無人機輔助計算場景等。

參考文獻：

[1]Li Tianxu，Zhu Kun，Luong NC，et al.Applications of multi-agent reinforcement learning in future Internet：acomprehensive survey[J].IEEE CommunicationsSurveysamp; Tutorials，2022，24（2）：1240-1279.

[2]Li Xuanheng，Du Xinyang，Zhao Nan，etal.Computing over the sky：joint UAV trajectory and task offloading scheme basedon optimization-embeddingmulti-agentdeepreinforcementlearning[J]. IEEETrans onCommunications，2024，72（3）：1355-1369.

[3] LiangJingyu，MaBowen，FengZihan，etal.Reliability-awaretask processing and offloading for data-intensive applications_in edge computing[J]. IEEETransonNetworkand ServiceManagement， 2023，20（4）：4668-4680.

[4]SadatdiynovK，CuiLaizhong，ZhangLei，etal．Areviewofoptimization methods for computation offoading in edge computing networks[J]. Digital Communicationsand Networks，2023，9（2）： 450-461.

[5]Chen Jingxuan， Cao Xianbin， Yang Peng， et al.Deep reinforcement learning based resource alocation in multi-UAV-aided MEC networks [J]. IEEE Trans on Communications， 2023， 71（1）： 296-309.

[6] 章剛，胡鵬，算力網絡下的算力邊緣服務器部署算法[J]。計算機應 用研究，2024，41（5）：1527-1531.（Zhang Gang，HuPengComputng first edge server deployment algorithm for computing first network[J]. Application Research of Computers，2024， 41（5） ： 1527-1531.）

[7] 張斐斐，葛季棟，李忠金，等，邊緣計算中協作計算卸載與動態 任務調度[J]。軟件學報，2023，34（12）：5737-5756.（Zhang Feifei，Ge Jidong，Li Zhongjin，et al.Cooperativecomputationoff loading and dynamic task scheduling inedge computing[J]. Journal of Software，2023，34（12）： 5737-5756.）

[8]Sun Zhenchuan， Mo Yijun， Yu Chen. Graph-reinforcement-learningbased task_offloading for multiaccess edge computing [J]. IEEE Internet of Things Journal，2023，10（4） ： 3138-3150.

[9]Gu Lin， Zhang Weiying， Wang Zhongkui， et al. Service management and energy scheduling toward low-carbon edge computing [J]. IEEE Trans on Sustainable Computing，2023，8（1）：109-119.

[10]Bahreini T，Brocanelli M，Grosu D.VECMAN：a framework for energy-aware resourcemanagementinvehicularedge computing systems[J]. IEEE Trans on Mobile Computing，2023，22（2）： 1231- 1245.

[11]Deng Xiaoheng，Yin Jian，Guan Peiyuan，el al.Inteligent delayawarepartial computing taskoffloading for_multiuserindustrial Internet of Things through edge computing[J].IEEE Internet of Things Joumal，2023，10（4）：2954-2966.

[12]NingZhaolong，YangYuxuan，Wang Xiaojieeldl.Dyamicopu tation offloading and server deployment for UAV-enabled multi-access edge_computing[J]. IEEE Trans on Mobile Computing，2023， 22（5）：2628-2644.

[13] Chen Cen，Guo Yingya.Energy-aware edge server placement in dynamic scenario using reinforcement learning[C]// Proc of the 15th International Conference on Communication Software and Networks. Piscataway，NJ： IEEE Press，2023：183-187.

[14]Bahrami B，KhayyambashiMR，MirjaliS.Multi-objectiveplacement of edge servers in MEC environment using a hybrid algorithm based on NSGA-IIand MOPSO[J]. IEEE Internet of Things Journal，2024，11（18）： 29819-29837.

[15]Jiang Xiaohan，HouPeng，Zhu Hongbin，etdl.Dynamic andinteligent edge server placement based on deep reinforcement learning in mobile edge computing[J]. Ad hoc Networks，2023，145：103172.

[16]Liu Haotian， Wang Shiyun，Huang Hui，et_al. On the placement of edge servers in mobile edge_computing [C]// Proc of International Conference on Computing， Networking and Communications. Piscataway，NJ： IEEE Press， 2023： 496-500.

[17]Zhang Xinglin，Li Zhenjang，Lai Chang，et al.Joint edge serverplace ment and service placement in mobile-edge computing[J]. IEEE Internet of Things Jourmal， 2022， 9（13）： i1261-1274.

[18]Liu Huaizhe，WangZ，WuJiaqictal.Jointoptmizationofserice placement and computation offloading_ for mobile edge computing [C]// Proc of IEEE/CIC International Conference on Communications in China.Piscataway，NJ： IEEE Press，2023： 1-6.

[19]AsghariA，Sohrabi MK.Multobjectiveedge server placement in mobile-edge computing using a combination of_multiagent deep Q-network andcoral refsoptimization_[J].IEEE Intemetof Things Joumal，2022，9（18）：17503-17512.

[20]Hua Haochen，Li Yutong，Wang Tonghe，et al. Edge computing with artificialintellence：maceangpsei Computing Surveys，2023，55（9）：1-35.

[21]Ren TaoNiuJianeiDai Binetal.Enablingefcientscduling in large-scale UAV-assisted mobile-edge computing via hierarchical reinforcement leaming_[J]. IEEE Intermet of Things Journal， 2022，9（10）：7095-7109.

[22]唐倫，李質萱，文雯，等，基于智能分層切片技術的數字孿生傳 感信息同步策略 電子與信息學報，2024，46（7）：2793- 2802.（TangLun，Li Zhixuan， Wen Wen，et al.Digital twinsensing information synchronizationstrategy_basedonintellgent hierarchical slicing technique[J]. Journal of Electronics amp; Information Technology，2024，46（7）：2793-2802.）

[23]Qiao Tianrun，Cui Peng，Zhang Ya.Hierarchical reinforcement learning based multi-agent collaborative control approach[C]//Proc of the 42nd Chinese Control Conference. Piscataway，NJ：IEEE Press， 2023： 8645-8650.

[24］李志華，余自立，基于深度強化學習的多用戶計算卸載優化模型和 算法[J].電子與信息學報，2024，46（4）：1321-132。（LiZhihua， Yu Zili.A multi-usercomputationoffloading optimization model_and algorithm based on deep_reinforcement learning[J].Journal of Electronicsamp; Information Technology，2024，46（4）：1321-1332.）

[25] Zhang Yongmin，Wang Wei，Ren Ju， el al. Efficient revenue-based MEC server deployment and management in mobile edge-cloud computing [J].IEEE/ACM Trans_on Networking，2023，31（4）： 1449- 1462.

[26]Hu Xi， Huang Yang.Deep reinforcement learning_based offloading decision algorithm for vehicular edge computing [J]. PeerJ ComputerScience，2022，8：e1126.