邊緣計(jì)算使能星地協(xié)同網(wǎng)絡(luò)下的服務(wù)部署機(jī)制

盧華 段雪飛 李斌

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

關(guān)鍵詞：邊緣計(jì)算；服務(wù)部署；強(qiáng)化學(xué)習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

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

為了使用強(qiáng)化學(xué)習(xí)算法解決服務(wù)部署問(wèn)題，我們需要將其建模為MDP，具體過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）對(duì)于隨機(jī)部署算法，每次部署隨機(jī)選擇節(jié)點(diǎn)；

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

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

2.2結(jié)果分析

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

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

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

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

參考文獻(xiàn)

[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)，楊磊，等.邊緣計(jì)算綜述：應(yīng)用、現(xiàn)狀及挑戰(zhàn)[J].中興通訊技術(shù)， 2019， 25（3）： 2-7. DOI： 10.12142/ZTETJ.201903001

[3]秦永彬，韓蒙，楊清亮.邊緣計(jì)算中數(shù)據(jù)驅(qū)動(dòng)的智能應(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]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)： C語(yǔ)言版[M].北京：清華大學(xué)出版社， 1997

作者簡(jiǎn)介

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

段雪飛，廣東省新一代通信與網(wǎng)絡(luò)創(chuàng)新研究院網(wǎng)絡(luò)技術(shù)創(chuàng)新中心核心網(wǎng)部門(mén)負(fù)責(zé)人；研究方向包括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ù)的研究；曾獲國(guó)家科學(xué)技術(shù)進(jìn)步獎(jiǎng)二等獎(jiǎng)。