盧華 段雪飛 李斌

摘要：在移動邊緣計算（MEC）與星地協(xié)同網(wǎng)絡(luò)（STIN）融合的網(wǎng)絡(luò)架構(gòu)中，針對衛(wèi)星網(wǎng)絡(luò)和邊緣計算對時延與資源敏感的特點，以最大化用戶服務(wù)質(zhì)量（QoS）為目標，提出基于強化學習的深度Q網(wǎng)絡(luò)（DQN）算法部署機制。將部署問題描述為一個馬爾可夫決策過程（MDP），并把衛(wèi)星節(jié)點的狀態(tài)和部署行為分別建模為DQN中的狀態(tài)和動作。通過衛(wèi)星的計算資源與衛(wèi)星和用戶的通信時延給出獎勵值，在神經(jīng)網(wǎng)絡(luò)中訓練以優(yōu)化部署行為，進而實現(xiàn)最優(yōu)部署策略，并對提出的算法做仿真。與其他算法對比的結(jié)果表明，在相同的優(yōu)化目標條件下，DQN算法有較好的性能。

關(guān)鍵詞：邊緣計算；服務(wù)部署；強化學習

Abstract： In the network architecture of mobile edge computing （MEC） and satellite terrestrial integrated network （STIN）， the satellite network and edge computing are sensitive to delay and resources. To maximize users quality of service （QoS）， a deployment mechanism based on the reinforcement learning deep Q network （DQN） algorithm is proposed. The deployment problem is described as a Markov Decision Process （MDP）. The state and deployment behavior of the satellite nodes are modelled as the state and action in the DQN. The reward value is given by the satellite computing resources and the communication delay between the satellite and the user. Training in the neural network to optimize the deployment behavior achieves the optimal deployment strategy. The proposed algorithm is simulated and compared with other algorithms. The result shows that under the same optimization target conditions， the DQN algorithm has better performance.

Keywords： edge computing； service deployment； reinforcement learning

近年來，互聯(lián)網(wǎng)與通信技術(shù)都取得了長足進步。大數(shù)據(jù)、云計算等新興技術(shù)已經(jīng)得到廣泛運用并成為當前的基礎(chǔ)性技術(shù)[1]。受益于5G的大規(guī)模使用，物聯(lián)網(wǎng)（IoT）、虛擬現(xiàn)實（VR）/增強現(xiàn)實（AR）/混合現(xiàn)實（MR）、高分辨率（4K/8K）視頻傳輸?shù)玫搅诉M一步推廣。然而，以車聯(lián)網(wǎng)（IoV）、遠程醫(yī)療、高幀率游戲等為代表的要求響應(yīng)速度快、時延超低、占用帶寬較大的應(yīng)用，對現(xiàn)有網(wǎng)絡(luò)體系架構(gòu)提出很大的挑戰(zhàn)。雖然5G的應(yīng)用可以緩解部分需求，但是用戶與云計算中心通信產(chǎn)生的時延，以及海量數(shù)據(jù)傳輸對帶寬的占用，與云計算技術(shù)本身都是矛盾的。為了解決這些問題，我們需要在數(shù)據(jù)中心之外，讓計算、存儲、網(wǎng)絡(luò)延展到互聯(lián)網(wǎng)的邊緣，甚至到每個家庭的互聯(lián)網(wǎng)網(wǎng)關(guān)上，使服務(wù)更加靠近用戶。這種技術(shù)就是邊緣計算[2-3]。星地協(xié)同網(wǎng)絡(luò)雖然有著很好的發(fā)展前景，但也面臨著和上述云計算類似的高數(shù)據(jù)速率、低通信時延等挑戰(zhàn)。移動邊緣計算（MEC）技術(shù)的引入可以更好地保障用戶服務(wù)質(zhì)量（QoS）。

關(guān)于邊緣計算中服務(wù)部署問題的研究有很多。文獻[4]將邊緣計算系統(tǒng)中的服務(wù)部署建模為一個多階段隨機規(guī)劃問題，設(shè)計了一個樣本平均近似（SAA）方法以估計多階段模型中資源函數(shù)的期望值，并提出貪心算法來解決基于SAA的并行算法中每個階段都需要解決的整數(shù)優(yōu)化問題。針對把服務(wù)完全部署到本地的情況，文獻[5]將問題建模為非線性整數(shù)規(guī)劃問題，并采用元啟發(fā)式算法求出近似解。文獻[6]將服務(wù)部署問題建模為馬爾可夫決策過程（MDP），并設(shè)計了一種在線算法，同時證明該算法是成本最優(yōu)的。文獻[7]同樣將服務(wù)部署問題建模為MDP，但采用強化學習中的Dueling-DQN算法（一種改進的DQN算法）進行求解。

不同部署問題的解決方案雖然有很大不同，但基本可以歸納為傳統(tǒng)算法和基于學習的方法。傳統(tǒng)算法一般將問題描述為規(guī)劃問題或優(yōu)化問題，但通常由于問題的復雜性以及多目標約束的存在而變?yōu)榉谴_定性多項式（NP）問題，使求解變得困難。而部署問題能夠容易地被建模為MDP過程，可采用強化學習中的QLearning或DQN等算法進行求解。

1服務(wù)部署模型與算法設(shè)計

1.1服務(wù)部署模型設(shè)計

這里，我們首先對研究問題做一些說明和假設(shè)：

（1）對于每個衛(wèi)星，除運行軌跡不同外，其他完全相同；

（2）用戶請求的服務(wù)相同；

（3）用戶與衛(wèi)星的距離用時延來描述；

（4）衛(wèi)星的可用計算能力與中央處理器（CPU）、內(nèi)存占用率成反比；

（5）衛(wèi)星的CPU和內(nèi)存消耗是線性的；

（6）服務(wù)在節(jié)點上并行計算；（7）衛(wèi)星計算能力存在上限和下限。

為了使用強化學習算法解決服務(wù)部署問題，我們需要將其建模為MDP，具體過程如下：

公式（1）中，E表示邊緣節(jié)點集合，Ue表示服務(wù)部署在節(jié)點e上的用戶集合，proce表示在節(jié)點e上處理服務(wù)需要的時間（根據(jù)假設(shè)，相同節(jié)點上的proc相同），delayu，e表示用戶u與節(jié)點e的通信時延。需要說明的是，這里的delay不僅代表時延，還代表用戶與衛(wèi)星的物理距離。因此，我們可將時延進行適當?shù)姆糯?，以擴大其在問題中的影響。

MDP是一個四元組，分別代表狀態(tài)、動作、狀態(tài)轉(zhuǎn)移概率和獎勵。本問題中的狀態(tài)轉(zhuǎn)移概率均為1。下面我們將討論S、A與R。

在本問題中，MDP中的動作是把服務(wù)部署在某個邊緣節(jié)點上。我們可以規(guī)定服務(wù)的部署順序。對于某個狀態(tài)集si而言，要部署的服務(wù)就是確定的。此時，動作數(shù)量與邊緣節(jié)點數(shù)量一致。本問題的MDP在狀態(tài)集si中執(zhí)行一個動作a，隨后進入狀態(tài)集si + 1。

獎勵是決定算法最終效果的核心。在使用簡化狀態(tài)集時，我們顯然不能為狀態(tài)集si中的所有狀態(tài)設(shè)置同一個獎勵值。單純地為簡化狀態(tài)集中的每一個狀態(tài)而定義一個獎勵值也是不合理的。因此，在設(shè)置獎勵值時，我們要按具體狀態(tài)集來處理。

1.2基于服務(wù)部署模型的算法設(shè)計

當利用強化學習來求解MDP模型時，我們可以采用Q-Learning或DQN算法。在本問題中，即使我們采用簡化狀態(tài)集，隨著服務(wù)數(shù)量的增加，其規(guī)模也呈指數(shù)級增長，此時不宜采用Q-Learning算法進行求解。因此，本文中我們采用DQN算法。

算法的模型如圖1所示。操作環(huán)境輸入選擇的動作，并執(zhí)行該動作，隨后進入下一狀態(tài)，同時反饋這一步的獎勵值和是否到達終止態(tài)等信息。這些信息會形成一條記錄被存入經(jīng)驗回放區(qū)。當經(jīng)驗回放區(qū)存儲一定數(shù)量的記錄后，神經(jīng)網(wǎng)絡(luò)會從中隨機選取一些記錄來進行訓練，并更新相應(yīng)的網(wǎng)絡(luò)參數(shù)，選擇基于當前網(wǎng)絡(luò)參數(shù)選出的價值最大的動作來讓環(huán)境執(zhí)行。新的記錄生成后會被繼續(xù)存入經(jīng)驗回放區(qū)。當經(jīng)驗回放區(qū)的數(shù)據(jù)足夠多時，新記錄將逐漸代替舊記錄，以便于那些之前使用價值不大的的記錄不會再被學習。本文中，我們使用的神經(jīng)網(wǎng)絡(luò)有兩個隱藏層。神經(jīng)網(wǎng)絡(luò)通過反向傳播當前Q網(wǎng)絡(luò)與目標Q網(wǎng)絡(luò)的差值來優(yōu)化參數(shù)。

獎勵值的計算方法可參照公式（2）。假設(shè)節(jié)點在最佳性能時處理一個服務(wù)消耗的時間為t0，則基本時間tbasic是所有已部署服務(wù)t0的簡單求和，如公式（3）所示：

公式（5）中，Rj代表當前獎勵值。γ為衰減因子（0≤γ≤1），表示后續(xù)獎勵值對當前Q值的影響。Q是目標Q網(wǎng)絡(luò)，ф（Sj）表示下一狀態(tài)的特征向量，Aj表示下一步動作，w為Q網(wǎng)絡(luò)中的狀態(tài)價值函數(shù)。

2實驗仿真與結(jié)果分析

2.1實驗環(huán)境及參數(shù)

實驗中，我們假定邊緣節(jié)點數(shù)量為9個，用戶（服務(wù)）數(shù)量n為20～50個，服務(wù)的最短執(zhí)行時間t0為60 s。為了簡化問題，我們假設(shè)每個服務(wù)都會消耗節(jié)點10%的CPU。同時，節(jié)點CPU空閑率的下限為10%，即一個節(jié)點最多可以同時為9個用戶提供服務(wù)。如果部署服務(wù)多于9個就需要排隊等候。顯然，在一個節(jié)點部署過多服務(wù)，不僅會導致每個服務(wù)的計算時間變長，還會使需要等待的節(jié)點產(chǎn)生更多不必要的等待時延。在上文假設(shè)的服務(wù)數(shù)量下，這顯然不是最優(yōu)策略。強化學習過程中的隨機選擇動作會導致這些策略被執(zhí)行和學習，因此，我們要在算法中避免這種情況的發(fā)生，即如果采取某個動作后會進入需要排隊的狀態(tài)，就令這一動作無效且下一狀態(tài)仍為原狀態(tài)，同時給這次動作一個很低的獎勵值，以避免再次作出同樣的選擇。

用戶與衛(wèi)星的時延是一個難以準確評估的參數(shù)。本文1.1節(jié)已經(jīng)指出，時延可代表用戶與衛(wèi)星的物理距離。為了在仿真中模擬現(xiàn)實情況，我們需要對其進行適當放大。經(jīng)過調(diào)試，我們認為，時延分布在1～20 s之間是比較合理的。

此外，本文同時設(shè)計了隨機部署算法、最短時延貪心算法、均勻部署算法3個參考算法[8]。我們分析了在不同服務(wù)數(shù)量條件下4個算法的性能。為了控制無關(guān)變量，這3個參考算法中每一個節(jié)點部署服務(wù)的數(shù)量均不會超過9個，且滿足如下條件：

（1）對于隨機部署算法，每次部署隨機選擇節(jié)點；

（2）對于最短時延貪心算法，每次部署選擇時延最小的節(jié)點；

（3）對于均勻部署算法，將服務(wù)平均部署到節(jié)點中。

2.2結(jié)果分析

我們選擇服務(wù)數(shù)量n分別為20、30、40和50，并進行測試比較。得到的柱狀圖結(jié)果如圖2所示。其中，縱坐標表示每種算法處理時延與傳輸時延之和。為了直觀地顯示不同情況的算法結(jié)果，我們對縱坐標的范圍進行適當調(diào)整。圖3是將柱狀圖繪制成折線圖的結(jié)果。

由圖2和圖3可知，在不同服務(wù)數(shù)量的情況下，DQN算法的性能均優(yōu)于另外3種算法。由于對問題作出的一系列假設(shè)使最優(yōu)部署方案接近于均勻部署，因此仿真中的平均部署算法性能與DQN較為接近。在實際問題中，服務(wù)對CPU的影響沒有那么劇烈，平均部署算法與DQN的真實差距要大于仿真中的差距。此外，在算法設(shè)計中，時延對結(jié)果的影響小于節(jié)點計算能力對結(jié)果的影響。因此，基于時延的貪婪算法的性能并不出色，甚至在某些情況下要比隨機算法性能更低。

3結(jié)束語

本文中，我們圍繞邊緣計算使能星地協(xié)同網(wǎng)絡(luò)中的服務(wù)部署問題展開研究，將服務(wù)部署問題建模為MDP過程，用DQN算法對模型進行求解，并提出詳細的算法步驟。我們通過設(shè)定基本參數(shù)，對算法進行仿真，并將DQN算法與隨機部署算法、時延優(yōu)先貪婪算法、平均部署算法這3個參考算法進行性能比較，發(fā)現(xiàn)DQN算法是解決邊緣計算服務(wù)部署問題的一種有效算法。

參考文獻

[1] ZHAO J J， XU C Z， MENG T H. Big data-driven residents travel mode choice： a research overview [J]. ZTE communications， 2019， 17（3）： 9-14. DOI： 10.12142/ZTECOM.201903003

[2]丁春濤，曹建農(nóng)，楊磊，等.邊緣計算綜述：應(yīng)用、現(xiàn)狀及挑戰(zhàn)[J].中興通訊技術(shù)， 2019， 25（3）： 2-7. DOI： 10.12142/ZTETJ.201903001

[3]秦永彬，韓蒙，楊清亮.邊緣計算中數(shù)據(jù)驅(qū)動的智能應(yīng)用：前景與挑戰(zhàn)[J].中興通訊技術(shù)， 2019，25（3）：68-76.DOI：10.12142/ ZTETJ.201903010

[4] BADRI H， BAHREINI T， GROSU D， et al. A sample average approximation-based parallel algorithm for application placement in edge computing systems [C]//2018 IEEE InternationalConferenceonCloudEngineering（IC2E）. Orlando， USA： IEEE， 2018：198-203

[5] CHENG Z X， LI P， WANG J B， et al. Just-intime code offloading for wearable computing[J]. IEEE transactions on emerging topics in computing， 2015， 3（1）： 74-83

[6] WANG S Q， URGAONKAR R， ZAFER M， et al. Dynamic service migration in mobile edge computing based on Markov decision process[EB/OL]. [2021-04-06]. https：//arxiv. org/abs/ 1506.05261

[7] ZHAI Y L， BAO T H， ZHU L H， et al. Toward reinforcement-learning-basedservicedeployment of 5G mobile edge computing with request-aware scheduling [J]. IEEE wireless communications， 2020， 27（1）： 84-91. DOI： 10.1109/MWC.001.1900298

[8]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)： C語言版[M].北京：清華大學出版社， 1997

作者簡介

盧華，廣東省新一代通信與網(wǎng)絡(luò)創(chuàng)新研究院網(wǎng)絡(luò)技術(shù)創(chuàng)新中心主任；研究方向包括5 G核心網(wǎng)、邊緣計算、新型網(wǎng)絡(luò)架構(gòu)、軟件定義網(wǎng)絡(luò)、P 4可編程、虛擬化等。

段雪飛，廣東省新一代通信與網(wǎng)絡(luò)創(chuàng)新研究院網(wǎng)絡(luò)技術(shù)創(chuàng)新中心核心網(wǎng)部門負責人；研究方向包括5 G核心網(wǎng)架構(gòu)、6 G網(wǎng)絡(luò)架構(gòu)、空天一體化通信系統(tǒng)等。

李斌，中興通訊股份有限公司系統(tǒng)架構(gòu)師；主要從事IP網(wǎng)絡(luò)相關(guān)技術(shù)的研究；曾獲國家科學技術(shù)進步獎二等獎。