邊緣計(jì)算中動(dòng)態(tài)服務(wù)器部署與任務(wù)卸載聯(lián)合優(yōu)化算法

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

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

a）在計(jì)算資源有限與網(wǎng)絡(luò)環(huán)境變化的情況下，構(gòu)建出可動(dòng)態(tài)調(diào)整的邊緣服務(wù)器布局與任務(wù)卸載模型，提出使每個(gè)計(jì)算任務(wù)的平均效用與系統(tǒng)整體效用最大化的目標(biāo)。

b）將優(yōu)化問(wèn)題分解為兩層子問(wèn)題，進(jìn)而轉(zhuǎn)換為雙馬爾可夫順序決策過(guò)程，并提出一種基于分層強(qiáng)化學(xué)習(xí)的聯(lián)合優(yōu)化算法。通過(guò)引人K-means為上層DQN提供先驗(yàn)知識(shí)加速模型收斂和優(yōu)化模型學(xué)習(xí)過(guò)程，利用狀態(tài)歸一化改善下層多智能體近端策略優(yōu)化（multi-agentproximalpolicyoptimization，MAPPO）的訓(xùn)練效果和收斂速度，通過(guò)上下層策略交替優(yōu)化對(duì)聯(lián)合優(yōu)化問(wèn)題進(jìn)行求解。

c）通過(guò)設(shè)置不同物理參數(shù)與網(wǎng)絡(luò)參數(shù)進(jìn)行廣泛實(shí)驗(yàn)，結(jié)果表明，所提算法能有效解決邊緣服務(wù)器部署與任務(wù)卸載聯(lián)合優(yōu)化問(wèn)題，比隨機(jī)算法與其他強(qiáng)化學(xué)習(xí)算法有實(shí)質(zhì)性的性能改進(jìn)。

1系統(tǒng)模型和問(wèn)題描述

1.1 網(wǎng)絡(luò)模型

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

1.2 通信模型

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

其中： p_i 為 u_i 的發(fā)送功率； N₀ 為高斯白噪聲功率； B 為信道帶寬； I_j 為當(dāng)前時(shí)隙卸載到 e_j 的計(jì)算任務(wù)數(shù)量。

1.3計(jì)算模型

每個(gè)時(shí)隙開(kāi)始，系統(tǒng)會(huì)執(zhí)行部署策略，確定ES在當(dāng)前時(shí)隙的具體位置，在此過(guò)程中每個(gè)ES由原來(lái)位置到新部署位置的遷移會(huì)產(chǎn)生相應(yīng)的時(shí)間與經(jīng)濟(jì)成本[25]，對(duì)于卸載任務(wù)的計(jì)算來(lái)說(shuō)不可忽略，所以邊緣服務(wù)器部署成本定義為

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

其中： S_i^t 表示計(jì)算任務(wù)所需要的CPU周期數(shù) ：f⁰_i 為 u_i 本地的計(jì)算頻率。本地計(jì)算產(chǎn)生的能耗表示為

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

其中： κ_i 表示設(shè)備功率系數(shù)，由設(shè)備CPU芯片架構(gòu)所決定。因此本地計(jì)算任務(wù)的整體效用可定義為

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

其中： η 為時(shí)延與能耗的權(quán)重系數(shù)。

在時(shí)隙 χ_t ，對(duì)于卸載任務(wù)來(lái)說(shuō)，服務(wù)器返回的計(jì)算結(jié)果通常很小，所以反饋時(shí)間與反饋能耗可忽略不計(jì)。因此，任務(wù)卸載到邊緣服務(wù)器上計(jì)算產(chǎn)生的時(shí)延包括任務(wù)傳輸時(shí)延和卸載計(jì)算時(shí)延，任務(wù)傳輸時(shí)延和卸載計(jì)算時(shí)延分別表示為

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

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

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 問(wèn)題構(gòu)建

本文從任務(wù)處理的整體效用來(lái)構(gòu)建問(wèn)題模型，在動(dòng)態(tài)移動(dòng)邊緣計(jì)算應(yīng)用場(chǎng)景中，計(jì)算任務(wù)的時(shí)延、能耗以及邊緣服務(wù)器的部署成本影響到用戶體驗(yàn)與服務(wù)商運(yùn)營(yíng)成本。受文獻(xiàn)[14]啟發(fā)，本文通過(guò)對(duì)時(shí)延、能耗和部署成本進(jìn)行綜合考慮，將任務(wù)計(jì)算效用和邊緣服務(wù)器部署成本通過(guò)加權(quán)求平均來(lái)建立目標(biāo)函數(shù)，定義如式（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}

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

混合整數(shù)非線性規(guī)劃問(wèn)題式（9）由于其離散的二進(jìn)制服務(wù)器部署變量與任務(wù)卸載變量高度耦合而難以求解。此外，MD在各個(gè)時(shí)隙的分布是動(dòng)態(tài)變化的，邊緣服務(wù)器每時(shí)隙部署一次，任務(wù)卸載決策必須實(shí)時(shí)完成，所以考慮到?jīng)Q策動(dòng)作先后順序的特點(diǎn)，本文將整個(gè)系統(tǒng)優(yōu)化問(wèn)題分層分解為兩個(gè)子問(wèn)題：

a）邊緣服務(wù)器部署優(yōu)化問(wèn)題P1。由于移動(dòng)設(shè)備可以在很大范圍內(nèi)移動(dòng)到新位置，對(duì)于計(jì)算資源有限的場(chǎng)景來(lái)說(shuō)，移動(dòng)設(shè)備與邊緣服務(wù)器之間的距離是影響信道增益的關(guān)鍵，在卸載策略中，該參數(shù)最終會(huì)影響卸載任務(wù)的時(shí)延和能耗，同時(shí)邊緣服務(wù)器部署產(chǎn)生的成本也是整體效用的一部分，所以應(yīng)該根據(jù)當(dāng)前時(shí)隙用戶位置分布與上個(gè)時(shí)隙的部署位置來(lái)正確選擇邊緣服務(wù)器的新位置，以獲得最優(yōu)時(shí)隙整體效益，所以問(wèn)題 P1 定義為

b）卸載優(yōu)化問(wèn)題 P2 。在每個(gè)時(shí)隙中，每個(gè)MD根據(jù)已部

署邊緣服務(wù)器的位置以及當(dāng)前時(shí)隙中自己的位置與計(jì)算任務(wù)等信息，確定卸載決策，使所有MD的平均效用最小。問(wèn)題P2定義為

2基于分層強(qiáng)化學(xué)習(xí)的聯(lián)合優(yōu)化算法

上述兩個(gè)子問(wèn)題都為混合整數(shù)非線性規(guī)劃問(wèn)題，傳統(tǒng)方法難以解決。因此，本文將上述優(yōu)化問(wèn)題轉(zhuǎn)換為雙馬爾可夫決策過(guò)程（Markovdecisionprocess，MDP），然后根據(jù)分層強(qiáng)化學(xué)習(xí)架構(gòu)提出一種HKDMP（hierarchicalreinforcementlearningbasedonDQNwithK-meansandMAPPO，HKDMP）算法進(jìn)行求解。針對(duì)任務(wù)卸載問(wèn)題，HKDMP采用MAPPO來(lái)獲得下層最優(yōu)卸載策略；對(duì)于邊緣服務(wù)器部署問(wèn)題，HKDMP使用K-means指導(dǎo)DQN算法來(lái)獲得上層服務(wù)器最優(yōu)部署策略。

2.1 MDP過(guò)程建立

馬爾可夫決策過(guò)程是一種數(shù)學(xué)模型，用于描述在決策環(huán)境中的最優(yōu)決策問(wèn)題，標(biāo)準(zhǔn)的MDP由一個(gè)五元組 （s，A，P，R γ ）組成，其中 s 是狀態(tài)空間， A 是動(dòng)作空間， P 是狀態(tài)轉(zhuǎn)移概率，R 是獎(jiǎng)勵(lì)函數(shù)， γ 是折扣因子， γ∈[0，1] 。本文是雙MDP過(guò)程，對(duì)于上層邊緣服務(wù)器部署策略，構(gòu)建一個(gè)全局可觀察智能體，將MD的任務(wù)與位置坐標(biāo)、ES位置坐標(biāo)和通過(guò)K-means聚類得到的待部署位置信息視為狀態(tài)，把是否部署視為動(dòng)作。

a）上層策略狀態(tài)空間：在每個(gè)時(shí)隙開(kāi)始，全局智能體將當(dāng)前時(shí)隙任務(wù)信息、聚類得到的服務(wù)器待部署位置與上一時(shí)隙服務(wù)器部署位置作為觀察到的狀態(tài)，狀態(tài)空間可定義為

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} 表示當(dāng)前時(shí)隙通過(guò)聚類得到的服務(wù)器待部署位置。

b）上層策略動(dòng)作空間：智能體根據(jù)當(dāng)前時(shí)隙所觀察到的 狀態(tài)來(lái)作出是否部署的離散動(dòng)作決策，動(dòng)作空間可以定義為

a_t^h=β^t

c）上層策略獎(jiǎng)勵(lì)函數(shù)：作為全局優(yōu)化策略，目標(biāo)是將整體效用達(dá)到最大化，考慮到本文優(yōu)化目標(biāo)為最小化計(jì)算時(shí)延、能耗與部署成本，所以取目標(biāo)函數(shù)的相反數(shù)作為獎(jiǎng)勵(lì)函數(shù)，定義為

對(duì)于下層策略，為了使所有MD的平均效用最小，所以將每個(gè)MD都視作一個(gè)智能體，在上層給出服務(wù)器部署方案的基礎(chǔ)上，每個(gè)智能體將自己的任務(wù)信息與服務(wù)器位置信息作為狀態(tài)，把卸載決策作為動(dòng)作。

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

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

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

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

c）下層策略獎(jiǎng)勵(lì)函數(shù)：由于下層策略為任務(wù)卸載策略，目標(biāo)為最小化每個(gè)任務(wù)執(zhí)行時(shí)延與能耗，所以下層策略使用任務(wù)執(zhí)行時(shí)延 T_i^? 與能耗 E_i^t 的加權(quán)和的相反數(shù)作為獎(jiǎng)勵(lì)函數(shù)，則 Ψ_t 時(shí)刻，智能體 u_i 的獎(jiǎng)勵(lì)函數(shù)表示為 r_i，t^l=-[μT_i^t+（?1-μ）E_i^t] ，所以系統(tǒng)整體獎(jiǎng)勵(lì)函數(shù)集合為

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

2.2基于分層強(qiáng)化學(xué)習(xí)的聯(lián)合優(yōu)化算法

2.2.1上層邊緣服務(wù)器放置網(wǎng)絡(luò)

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

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

若對(duì)于下一個(gè)狀態(tài) s_t+1^h 的所有可能動(dòng)作 a_t+1^h 都已知，那么當(dāng)前優(yōu)化目標(biāo)為選擇下個(gè)狀態(tài)所有動(dòng)作中最大的狀態(tài)動(dòng)作價(jià)值。

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

通過(guò)更新預(yù)測(cè)網(wǎng)絡(luò)狀態(tài)動(dòng)作價(jià)值函數(shù)不斷迭代。

在每次迭代中，DQN通過(guò)優(yōu)化均方誤差損失函數(shù)，使得目標(biāo)收斂于最優(yōu)動(dòng)作價(jià)值函數(shù)。損失函數(shù)定義如下：

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

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下層任務(wù)卸載網(wǎng)絡(luò)

在實(shí)際環(huán)境中，服務(wù)器上的任務(wù)負(fù)載大小對(duì)計(jì)算任務(wù)的時(shí)延和能耗有很大影響，單個(gè)任務(wù)卸載策略的改變會(huì)導(dǎo)致信道與計(jì)算資源發(fā)生改變，從而影響其他計(jì)算任務(wù)的時(shí)延與能耗。除此之外，在考慮每個(gè)任務(wù)卸載策略好壞的同時(shí)，還要使系統(tǒng)整體性能達(dá)到最優(yōu)。對(duì)于這種存在競(jìng)爭(zhēng)-合作關(guān)系的問(wèn)題，本文在下層任務(wù)卸載策略引入MAPPO算法，將每個(gè)MD視作一個(gè)智能體，對(duì)每個(gè)智能體的狀態(tài)空間進(jìn)行歸一化處理，并采用“集中式訓(xùn)練，分布式執(zhí)行\(zhòng)"結(jié)構(gòu)，使每個(gè)智能體作出最優(yōu)卸載決策。

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

同上層邊緣服務(wù)器部署策略一樣，下層策略優(yōu)化的目標(biāo)是使每個(gè)智能體的累積折扣回報(bào)達(dá)到最大化，得到最優(yōu)策略網(wǎng)絡(luò)參數(shù)。

其中：目標(biāo)函數(shù) J（θ_i^π） 為累計(jì)折扣獎(jiǎng)勵(lì)的期望，定義為

為穩(wěn)定訓(xùn)練過(guò)程和降低梯度估計(jì)方差。引入優(yōu)勢(shì)函數(shù)替

代策略梯度中的累計(jì)折扣獎(jiǎng)勵(lì)，定義如下：

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

此外，利用重要性采樣和裁剪策略來(lái)提高訓(xùn)練效率和穩(wěn)定性，actor網(wǎng)絡(luò)的損失函數(shù)構(gòu)造如下：

其中：

為新舊策略的重要性采樣比值，表示兩個(gè)網(wǎng)絡(luò)的差異程度。裁剪策略利用clip函數(shù)防止產(chǎn)生因策略網(wǎng)絡(luò)參數(shù)過(guò)度更新而導(dǎo)致訓(xùn)練不穩(wěn)定問(wèn)題， ε 為剪裁范圍參數(shù)，本文設(shè)置為0.2。價(jià)值網(wǎng)絡(luò)的損失函數(shù)為

其中： 為價(jià)值網(wǎng)絡(luò)的估計(jì)。

通過(guò)梯度下降對(duì)參數(shù) θ 和 ? 進(jìn)行更新：

經(jīng)過(guò)固定步長(zhǎng)后對(duì)舊actor和舊critic網(wǎng)絡(luò)進(jìn)行更新：

其中： α_θ 和 α_? 是神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)率。

算法1基于分層強(qiáng)化學(xué)習(xí)的聯(lián)合優(yōu)化算法

輸入：任務(wù)位置集合 {p₁^t，…，p_N^t} ，計(jì)算任務(wù)集合 {D^t，S^t} ，ES位置集合 {P₁^t，…，P_j^t} ，BS位置集合 P_BS ，ES數(shù)量 K （204號(hào)

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

觀測(cè)狀態(tài)歸一化 智能體 u_i 根據(jù) 按照策略 π_θi 采取動(dòng)作 a_i，t^l 執(zhí)行動(dòng)作 a_i，t^l 得到即時(shí)獎(jiǎng)勵(lì) r_i，t^l 下一個(gè)狀態(tài) s_i，t+1^l 和時(shí)隙結(jié)束標(biāo)志done使用價(jià)值網(wǎng)絡(luò)和目標(biāo)價(jià)值網(wǎng)絡(luò)計(jì)算當(dāng)前狀態(tài)價(jià)值 V_?i （s_i，t^l） 和下個(gè)狀態(tài)的價(jià)值 根據(jù)式（26）使用計(jì)算優(yōu)勢(shì)函數(shù) 根據(jù)式（28）計(jì)算策略網(wǎng)絡(luò)損失函數(shù) L^CLIP（θ_i^π） （204根據(jù)式（30）計(jì)算價(jià)值網(wǎng)絡(luò)損失函數(shù) L^VF（?_i） 根據(jù)式（31）更新策略網(wǎng)絡(luò)參數(shù) θ_i^π 根據(jù)式（32）更新價(jià)值網(wǎng)絡(luò)參數(shù) ?_i 根據(jù)式（33）和（34）更新目標(biāo)網(wǎng)絡(luò)參數(shù)end forend forend for

2.3算法復(fù)雜度分析

HKDMP算法復(fù)雜度由上下兩層網(wǎng)絡(luò)的復(fù)雜度構(gòu)成，首先，對(duì)于上層策略，假設(shè) T_i^q 為DQN第 i 層中的神經(jīng)元數(shù)量，所以計(jì)算復(fù)雜度可以寫成：

其中： L_q 是上層網(wǎng)絡(luò)的總層數(shù)，因此上層網(wǎng)絡(luò)的計(jì)算復(fù)雜度為

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

其中： N_batch 為訓(xùn)練批量大小； Z 為迭代次數(shù)； G 表示Adam優(yōu)化器在梯度計(jì)算與反向傳播過(guò)程中的計(jì)算復(fù)雜度。對(duì)于下層策略，假設(shè) T_i^q 和 T_i^c 分別為actor和critic第 i 層全連接層中的神經(jīng)元數(shù)量，所以其復(fù)雜度分別為

同理 ，L_a 和 L_c 是下層網(wǎng)絡(luò)中actor網(wǎng)絡(luò)和critic網(wǎng)絡(luò)的總層數(shù)，下層網(wǎng)絡(luò)的計(jì)算復(fù)雜度為

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

其中： N 為智能體數(shù)量。所以，結(jié)合上下層網(wǎng)絡(luò)結(jié)構(gòu)，HKDMP算法的計(jì)算復(fù)雜度為

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1評(píng)價(jià)指標(biāo)

為了評(píng)估HKDMP算法的性能，本文采用負(fù)載均衡指標(biāo)和平均任務(wù)獎(jiǎng)勵(lì)作為評(píng)價(jià)指標(biāo)。使用負(fù)載均衡指標(biāo)來(lái)評(píng)價(jià)在算法訓(xùn)練過(guò)程中所有MD任務(wù)卸載的負(fù)載均衡效用，統(tǒng)計(jì)平均每個(gè)服務(wù)器上任務(wù)處理個(gè)數(shù)，具體按式（41）計(jì)算。

其中： L_j^t 為卸載到 e_j 上的任務(wù)數(shù)量； 為卸載到每個(gè)邊緣服務(wù)器上的平均任務(wù)數(shù)量。

平均任務(wù)獎(jiǎng)勵(lì)是訓(xùn)練過(guò)程中所有任務(wù)獲得的平均獎(jiǎng)勵(lì)，主要用于評(píng)估多智能體算法的整體性能，具體按式（42）計(jì)算。

3.2 仿真實(shí)驗(yàn)設(shè)置

本節(jié)通過(guò)仿真實(shí)驗(yàn)來(lái)評(píng)估HKDMP算法性能。仿真實(shí)驗(yàn)在基于Python3.6和PyTorch1.8的環(huán)境上進(jìn)行，并使用NVIDIA-A100-PCIE-40GB對(duì)智能體進(jìn)行訓(xùn)練。環(huán)境設(shè)定移動(dòng)設(shè)備MD在 1 000m×1 000m 區(qū)域內(nèi)隨機(jī)分布，設(shè)備的移動(dòng)速度 v_i 為 17m/s ，移動(dòng)方向隨機(jī)產(chǎn)生，區(qū)域內(nèi)垂直與水平方向每

200m 放置一個(gè)基站，共計(jì)16個(gè)基站，時(shí)隙個(gè)數(shù) T 為100，每個(gè)時(shí)隙移動(dòng)設(shè)備的計(jì)算任務(wù) 隨機(jī)生成，具體參數(shù)設(shè)置參考文獻(xiàn)[24，26]，如表1與2所示。訓(xùn)練輪次 Z 為1000，上下層模型每個(gè)時(shí)隙對(duì)網(wǎng)絡(luò)參數(shù)進(jìn)行一次更新。

3.3 收斂性分析

圖3展示了不同學(xué)習(xí)率下系統(tǒng)平均時(shí)隙獎(jiǎng)勵(lì)隨訓(xùn)練次數(shù)的變化?？梢钥吹剑?dāng)上層網(wǎng)絡(luò)與下層網(wǎng)絡(luò)的學(xué)習(xí)率都為0.0005時(shí)，系統(tǒng)獎(jiǎng)勵(lì)的收斂效果達(dá)到最優(yōu)。當(dāng)上層網(wǎng)絡(luò)的學(xué)習(xí)率較大時(shí)，在訓(xùn)練初期，獎(jiǎng)勵(lì)收斂較快，在訓(xùn)練50＼～200輪之間，由于學(xué)習(xí)率較大，使參數(shù)更新方向頻繁變化，獎(jiǎng)勵(lì)出現(xiàn)波動(dòng)現(xiàn)象。當(dāng)上層網(wǎng)絡(luò)的學(xué)習(xí)率較小時(shí)，在訓(xùn)練130＼～270輪時(shí)獎(jiǎng)勵(lì)下降，模型陷入鞍點(diǎn)，智能體參數(shù)更新緩慢導(dǎo)致策略的改進(jìn)停滯，但隨著訓(xùn)練次數(shù)增加，模型逐漸積累了足夠多的有效更新，導(dǎo)致獎(jiǎng)勵(lì)再次上升。當(dāng)下層網(wǎng)絡(luò)學(xué)習(xí)率較大時(shí)，參數(shù)更新步長(zhǎng)太大，模型的損失函數(shù)在不同方向上大幅波動(dòng)，導(dǎo)致前期無(wú)法得到最大獎(jiǎng)勵(lì)。當(dāng)下層網(wǎng)絡(luò)的學(xué)習(xí)率較小時(shí)，導(dǎo)致模型收斂速度較慢，訓(xùn)練時(shí)間較長(zhǎng)。

3.4性能比較

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

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

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

圖8展示了不同任務(wù)大小下各個(gè)算法的負(fù)載均衡指標(biāo)與任務(wù)平均獎(jiǎng)勵(lì)。圖8（a）中，隨著任務(wù)大小增加，Random的負(fù)載均衡指標(biāo)一直保持較高數(shù)值，且?guī)缀鯖](méi)有改變，其他RL算法的負(fù)載均衡指標(biāo)在相應(yīng)提高，因?yàn)殡S著任務(wù)大小增加，RL算法更傾向于將任務(wù)卸載到邊緣服務(wù)器上進(jìn)行計(jì)算從而降低任務(wù)計(jì)算時(shí)延和計(jì)算能耗，所以其下層策略的探索動(dòng)作空間變小，系統(tǒng)不再需要復(fù)雜地評(píng)估多種任務(wù)分配路徑，更容易實(shí)現(xiàn)負(fù)載均衡。當(dāng)任務(wù)大小為[4＼～5]MB時(shí)，相較于其他算法，HKDMP的負(fù)載均衡指標(biāo)分別提高 12.1% ） 46.6% 、66. 1% 和

88.8% 。圖8（b）中，隨著任務(wù)大小增加，單個(gè)任務(wù)計(jì)算需求變大，導(dǎo)致系統(tǒng)資源緊張，同時(shí)消耗更多能量，影響任務(wù)的執(zhí)行時(shí)延與能耗，所以任務(wù)平均獎(jiǎng)勵(lì)相應(yīng)減少。其中HKDMP算法能夠獲得環(huán)境最大獎(jiǎng)勵(lì)，當(dāng)任務(wù)大小為[4＼～5]MB時(shí)，相較其他四種方案平均任務(wù)獎(jiǎng)勵(lì)分別提高1.8%、7.0% .8.8% 和 14.4% 。

圖9對(duì)比了在不同任務(wù)大小下各個(gè)算法的時(shí)延、能耗與放置成本，隨著邊緣服務(wù)器數(shù)量的增加，每個(gè)算法得到的任務(wù)平均時(shí)延與能耗相應(yīng)減小，服務(wù)器放置成本相應(yīng)增加。因?yàn)檫吘壏?wù)器數(shù)量的增加使邊緣服務(wù)器更靠近移動(dòng)設(shè)備，計(jì)算任務(wù)更傾向于卸載到距離近的服務(wù)器計(jì)算，且更多的邊緣服務(wù)器會(huì)分擔(dān)計(jì)算任務(wù)，避免了少數(shù)服務(wù)器過(guò)載以及網(wǎng)絡(luò)擁塞，從而降低任務(wù)的傳輸時(shí)延與傳輸能耗。當(dāng)服務(wù)器數(shù)量為2時(shí)，相較于其他四種算法，HKDMP的任務(wù)計(jì)算時(shí)延分別減小 0.9%6.3%8.9% 、19.4% ，計(jì)算能耗以及服務(wù)器放置成本方面都得到較優(yōu)策略。

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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，F(xiàn)engZihan，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] 章剛，胡鵬，算力網(wǎng)絡(luò)下的算力邊緣服務(wù)器部署算法[J]。計(jì)算機(jī)應(yīng) 用研究，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ì)算中協(xié)作計(jì)算卸載與動(dòng)態(tài) 任務(wù)調(diào)度[J]。軟件學(xué)報(bào)，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]唐倫，李質(zhì)萱，文雯，等，基于智能分層切片技術(shù)的數(shù)字孿生傳 感信息同步策略 電子與信息學(xué)報(bào)，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］李志華，余自立，基于深度強(qiáng)化學(xué)習(xí)的多用戶計(jì)算卸載優(yōu)化模型和 算法[J].電子與信息學(xué)報(bào)，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.