面向ET-DQN的衛星網絡任務部署算法研究

劉治國,董效奇,汪 林,夏清雨,潘成勝,3

1(大連大學 通信與網絡重點實驗室,遼寧 大連 116622)

2(大連大學 環境與化學工程學院,遼寧 大連 116622)

3(南京信息工程大學 電子與信息工程學院,南京 211800)

0 引 言

隨著大量物聯網(Internet of Things,IoT)設備、虛擬現實(Virtual Reality,VR)、高清視頻傳輸以及自動無人駕駛新興應用的出現[1],第五代移動通信標準(5G)地面網絡可能無法對森林、農村、山地和海洋等地區實現覆蓋,然而在這些地區,物聯網設備卻廣泛部署用于攝像信息處理以及信息收集,并產生大量的處理延遲.除此之外,地面網絡的抗干擾和抗災害能力較弱,不能夠應對突發事件[2].由此第六代移動通信標準(6G)將地面網絡與衛星通信集成,真正的做到了網絡的全覆蓋,同時又不受外部環境的影響[3].星地協同網絡可以應用于許多有前途的領域,如智能交通系統、遠程區域監控、災難救援和大規模高速移動互聯網接入,還能實現真正意義上的全球廣域覆蓋,真正的解決了地面網絡的諸多問題[4].

而隨著新興應用的出現,部分應用需要大量的計算資源.例如,虛擬現實和高清視頻流需要大量計算資源用于渲染和視頻的編碼和解碼,自動駕駛車輛依賴大量計算進行自動控制[5].這些計算密集型應用對資源受限的終端設備的電池和計算能力帶來了巨大挑戰,由此云計算被提出.在云計算中,計算密集型應用被部署到具有集中和豐富計算資源的云服務器上.雖然云計算能降低用戶的計算延遲和能耗,但它無法滿足延遲敏感應用的需求,例如增強現實,因為終端用戶和云服務器之間的傳輸距離很長,從而導致較大的傳輸延遲[6].為了解決這個問題,世界各學者對移動邊緣計算(Mobile Edge Computing,MEC)進行了廣泛的研究,利用網絡邊緣的計算資源來提供高效靈活的計算服務.將邊緣計算技術引入星地協同網絡,即將云計算平臺擴展到網絡邊緣,為用戶提供異構計算資源,同時使得用戶可以在世界任何地方獲取計算服務,從而改善用戶服務體驗,減少冗余網絡流量[7].

然而,由于衛星MEC服務器計算能力和能耗都是十分有限的,只能同時部署一部分的服務請求,分配給每個服務的計算資源也十分有限.終端用戶希望將盡可能多的任務轉移到衛星邊緣計算節點,從而減少任務處理延遲,改善用戶體驗.如果衛星邊緣計算節點資源不足,用戶設備的計算任務將發送至遠程云進行處理,這無疑會增加服務請求的處理成本.

因此在地面網絡稀疏環境下,面對衛星網絡的資源和能量的有限性,制定高效的任務部署算法,降低處理時延和衛星系統能耗是當今衛星網絡邊緣計算研究的一大挑戰.本文提出了SDN的衛星-地面聯合部署網絡架構SSGIN,并對融合邊緣計算的SDN控制器進行設計,為遠程終端提供強大的邊緣-云計算服務.在該框架下,將任務部署問題表述為馬爾可夫決策過程(Markov Decision Process,MDP),提出了改進的深度強化學習算法:經驗競選的DQN算法(Experience Tournament-DQN,ET-DQN),動態學習最優部署策略,以最小化任務處理時延和能耗.因此本文的貢獻歸納為3點:

1)提出了SSGIN網絡架構,并對融合邊緣計算的SDN控制器進行設計.

2)提出了改進DQN算法:經驗競選的ET-DQN,在SSGIN網絡架構下,對批量任務的處理時延和能耗作為優化目標,顯著降低了優化問題的復雜性,并與基準算法相比,在時延和能耗方面獲得了更好的性能.

3)在仿真結果中,將ET-DQN與傳統的DQN算法、Prioritized-DQN的收斂性以及平均獎勵以及方差進行了對比,在收斂性表現優秀,與Prioritized-DQN平均獎勵提高近百分之16%.

1 相關研究

1.1 SDN衛星網絡相關研究

SDN作為一種新興的網絡管理模式,能夠有效提高衛星網絡的資源管理水平,提高衛星網絡的整體性能.Li等[8]人將SDN思想引入衛星網絡以提高網絡的管理和配置效率,設計了一種基于SDN的空地一體的多層網絡結構,包括多層網絡結構和虛擬化服務的部署.Toufik Ahmed等[9]結合SDN和NVF技術,針對于網絡切片不同的階段設計了相應的資源管理策略,實現了切片綜合效益最大化.Qiu C等[10]人以資源角度出發,提出了基于SDN的天地一體化網絡架構,并將整個網絡的網絡資源、緩存資源、計算資源一起,用于動態管理和聯合編排.然而融合邊緣計算的SDN空地一體的網絡結構的研究卻很少.

1.2 融合邊緣計算的衛星網絡相關研究

近些年來,國內外對邊緣計算都進行了廣泛的研究,在國際上,行業標準化權威組織 IEC 發布了垂直邊緣智能(Vertical Edge Intelligence,VEI)白皮書,介紹了邊緣計算對制造業和其他垂直行業的重要價值[11].信息和通信技術(Information and Communications Technology,ICT)領域的權威標準組織 ISO/IEC JTC1成立了邊緣計算研究小組,推動邊緣計算標準化工作[12].除了邊緣計算各種標準相關標準、布局的研究外,任務卸載是邊緣計算中解決邊緣設備計算、存儲和性能資源限制的主要方法.大量文獻致力于針對不同場景和不同優化目標下的最優部署策略,文獻[13-17]通過聚類和凸優化方法解決衛星網絡中的資源分配和計算卸載,其中zhu等[15]人通過基于模擬退火的粒子群優化算法(SAPSO)獲得滿足延遲約束的最優分配方案.該類方法都是通過多項式時間復雜度來解決該類問題的,然而面對實時變化的衛星網絡,上述方法一般需要重新進行搜索求解.文獻[18-20]通過強化學習的相關算法解決任務部署問題,Zhang等[18]以時延和能耗為優化目標,通過地軌衛星實現對資源的整合和分配,提出一種協同計算卸載的方案.Cheng等[19]建立了一種空天地邊緣-云網絡,并在此基礎上,提出了聯合資源分配和任務調度方案,以有效地進行資源分配并調度卸載的任務.然而強化學習算法仍然存在經驗池利用率低和網絡訓練的效率低下的問題.Xiong等[20]在DQN的基礎上,對神經網絡訓練進行改進,由于DQN算法存在難以收斂以及過學習的問題,該文獻對DQN網絡進行了改進,采用多個重放存儲器分別存儲相互影響較小的經驗,進一步改進了Q 網絡的訓練過程,然而設計多個重放存儲器,經驗選擇策略仍然采用隨機選擇,沒有根本上解決樣本利用率低下的問題.除此以外,相關任務部署的研究對于針對任務部署的SDN控制器的具體設計,以及在衛星星座任務部署具體流程卻很少提及.

綜上所述,本文提出了SDN的衛星-地面聯合部署網絡架構,并對融合邊緣計算的SDN控制器、以及衛星星座卸載流程進行設計.與此同時,為了解決DQN經驗利用率和網絡訓練的效率低下的問題,提出改進的ET-DQN算法以解決任務部署問題.

2 系統模型和問題表述

基于SDN的衛星-地面聯合部署網絡架構(SDN-Space-Ground Integrated Network,SSGIN)如圖1所示,其主要有地面網絡和衛星網絡兩個部分組成,兩者互為彼此的補充,實現全球無縫覆蓋.

圖1 基于SDN的衛星-地面聯合部署網絡架構示意圖Fig.1 Schematic diagram of SDN based satellite ground joint deployment network architecture

衛星網絡由LEO低軌衛星網絡、GEO同步衛星網絡以及相應的地面基礎設施組成(信關站和衛星地面控制中心).LEO低軌衛星構成空間接入網絡,每個LEO衛星可部署邊緣計算節點為地面稀疏終端設備直接提供服務.GEO同步衛星得益于其覆蓋范圍廣的特性,可作為SDN衛星網絡的控制層,用以維護網絡拓撲和狀態信息,并以OpenFlow協議進行路由控制.

地面網絡主要由地面通信系統組成,包括移動網絡、轉發網絡、自組織移動網絡、無線局域網和地面云計算中心.地面網絡在人口密集區域可以為用戶提供超高速的服務,而在農村和偏遠地區、人口稀疏的區域,網絡覆蓋范圍有限.

GEO衛星作為SSGIN網絡架構的控制層,為了實現邊緣計算任務部署的相關功能,需針對任務部署的SDN控制器進行設計.SDN控制器中有4個主要模塊:網絡拓撲管理模塊、路由管理模塊、邊緣計算管理模塊和任務部署模塊.網絡拓撲管理模塊和路由管理模塊與傳統的SDN控制器相同,主要負責拓撲相關和路由相關的服務.為了實現邊緣計算任務部署的相關功能,在SDN控制器中增加了邊緣計算管理模塊,主負責邊緣計算節點的監控和管理.任務部署模塊的作用是任務到達時,任務部署模塊需從網絡拓撲管理模塊獲取全局拓撲,從邊緣計算節點管理模塊獲取節點信息,最后,將本文提出的算法用于求解任務的部署位置.

衛星網絡的部署任務過程如下:

步驟1.地面多個用戶向對應覆蓋的衛星發起任務部署請求.

步驟2.對應的接收衛星統一向GEO衛星發送任務信息,GEO上有全局的SDN控制器,SDN控制器只的各個模塊相互配合協調,最終由任務部署模塊求解最佳部署位置.

步驟3.GEO控制器將對應的控制信息下發至LEO衛星上.

步驟4.低軌衛星通過流表控制將任務轉發至指定部署位置.

步驟5.邊緣計算節點經過任務處理將結果返給至任務發起衛星.

步驟6.將任務結果返回至地面用戶.

3 成本模型

3.1 任務部署時延

3.1.1 任務處理時延

(1)

3.1.2 任務等待時延

由于本文衛星邊緣計算服務器是以多核多線程并行的情況下提供服務的,需對節點sk上資源調度建立模型.在衛星sk上的wait_queuek,run_queuek分別表示等待任務集合和執行任務集合.本文采用非搶占式的先來先服務的思想來分配衛星邊緣計算服務器的計算資源,該方式優點簡單易實現.即對到來的任務如果不滿足其需要獲取的計算資源,那么需要進入wait_queuek等待資源分配滿足后,再使其進入run_queuek隊列執行,任務等待時延可分為以下兩種情況:

(2)

3.1.3 任務傳輸時延

(3)

(4)

3.2 任務能耗

(5)

3.3 總成本模型

為了解決部署位置和計算資源分配不合理而導致任務處理時延過長、衛星能耗過大的問題,本文以任務部署時延和衛星能耗為優化目標,求解該批服務請求各自的最佳部署位置,以及分配的計算資源,使得其該批請求的任務處理時延和衛星能耗最小.

根據公式(4)、公式(5),最終得優化方程為:

(6a)

(6b)

elemi,k∈{0,1}i∈N,k∈M

(6c)

(6d)

(6e)

4 算法設計

4.1 ET-DQN算法

4.1.1 狀態空間

狀態空間state第1部分為當前邊緣計算節點的狀態矩陣,即將計算節點集合S={s1,s2,…,sp,scloud}組成矩陣s_sat:

(7)

第2部分為當前服務請求矩陣s_app:

(8)

4.1.2 動作空間

定義動作空間action:

(9)

4.1.3 獎勵函數

(10)

(11)

其中θ和θ-分別代表估計網絡與目標網絡的參數值.

立即回報reward值高的經驗對Agent的學習同樣有很大的影響.因此本文以TD-error和立即回報reward作為各樣本優先級的衡量標準.TD-error和reward立即回報越大,其優先級越高.樣本的TD-error的優先級y1和reward的優先級分別y2為:

y1=reward+ρ

(12)

y2=|δ|+ρ

(13)

其中ρ為一正常數,以確保樣本y1與y2不為0.那么最終優先級Y可表示為:

(14)

目前已知的經驗回放方法都是以高優先級樣本為主,而過度的使用優先級高的樣本,低優先級的樣本很有可能長時間不能被回放,從而造成Q網絡過擬合的發生.由此本文提出經驗競選的DQN算法(Experience Tournament-DQN,ET-DQN).采用經驗抽樣策略,該抽樣選擇和遺傳算法的選擇策略十分類似,Schaul等[23]提出了Prioritized replay的采樣策略,其采樣方式采用輪盤賭策略,而競選策略比輪盤賭無論是在通用性還是性能上都表現更佳.本文采用競選策略來抽取批量的經驗行經驗回放.競選策略流程圖如圖2所示.

圖2 競選策略流程圖Fig.2 Campaign strategy flow chart

在競選策略流程中,初始化神經網絡的batchsize,并從經驗池中隨機獲取n個經驗,并計算每條經驗的Y值,選出Y值經驗最大的放入到批量訓練集中,直到取滿batchsize為止,并放入神經網絡進行訓練.

ET-DQN算法如算法1所示.

算法1.ET-DQN算法

1.初始化估計網絡與目標網絡的參數值θ,θ-,經驗池容量為Z,批量經驗數batchsize,遍歷次數X,目標網絡的更新步幅D,折扣因子γ,ε-greedy,策略π,學習率ρ,隨機經驗數n;

2.Start

3.Forepisode=1,Xdo

4.初始化環境,通過SDN控制器獲取當前網絡狀態state={s_sat,s_app};

5.Fort=1,Hdo

6. 以ε的概率隨機選擇一個動作action,或者根據模型選擇當前最優的action=maxactionQ*(state,action;θ);

7. 執行動作action,進入新狀態state′和回報reward;

8. 通過κ=(state,action,state′,reward)經驗樣本計算該經驗的優先級Y,并放入經驗池;

9. 根據圖2流程選取經驗放入批量訓練集中,并計算該批經驗的y值:

10. 根據公式在(y-Q(state,action;θ))2上執行梯度下降,更新估計網絡θ參數;

11. 如果t可被更新步幅D除盡,則將估計網絡參數θ賦給目標網絡θ-;

12.EndFor

13.EndFor

5 仿真實驗

為了驗證ET-DQN的算法性能,本次仿真實驗使用STK仿真軟件模擬信息傳輸網絡,并使用python和pytorch搭建神經網絡,進行訓練.在仿真實驗中,本文采用LEO衛星星座采用66顆衛星的Walker星座,即將軌道傾角90度的walker星座劃分為6個軌道面,11顆低軌衛星分布在每個軌道平面上.通過3顆GEO衛星覆蓋整個walker星座和地面,將SDN控制器部署至GEO衛星上,對walker星座的各個衛星進行監控,以做到全局的優化.

系統模擬仿真參數如表1所示.

表1 系統模擬參數Table 1 System simulation parameters

為驗證ET-DQN的收斂性,仿真實驗中,分別對傳統DQN,Prioritized-DQN以及ET-DQN的loss函數進行測試,得出的結論如圖3所示.

圖3 loss對比圖Fig.3 Loss comparison chart

由loss可知,傳統的DQN算法在經過80000次迭代后依然難以收斂,仍然有較大的振幅,而Prioritized-DQN收斂速度很快,但是隨著迭代次數增加,loss不降反升,說明此時的Prioritized-DQN經驗池因為記憶緩存中的記憶單元不再獨立.經過多次迭代,高優先級的存儲經驗被多次存入經驗池,低優先級的經驗逐漸消失,經驗池有效的訓練集變小,導致訓練模型下降陷入局部最優.而ET-DQN算法,初期的收斂速度不及Prioritized-DQN,由于其由于抽樣的隨機性,并不會造成經驗池利用不充分的問題,loss處于平穩下降狀態,并在50000次后基本趨于穩定,在收斂性方面,ET-DQN算法是優于其他兩種算法的.

在強化學習中,獎勵reward是深度強化學習的最重要的指標參數,獎勵reward對比圖如圖4所示.

圖4 reward變化圖Fig.4 Reward variation diagram

由圖4可知,隨著迭代次數的增加,3種算法在每個回合獲得到的reward值都逐漸提高.表2中列舉了在訓練過程中,3種算法的均值與方差.由表2可得,ET-DQN算法在仿真實驗中平均每個回合獲得的回報最大,比Prioritized-DQN提高了近16%.二者的方差相近的情況下,在迭代40000次后,雖然每輪的獎勵值略有波動,但獲得的總體獎勵值保持穩定.Prioritized-DQN收斂快,但在訓練后期,仍然出現性能下降的情況,而DQN的reward均值最低,方差大,出現了較大的震蕩.綜上所述,ET-DQN算法在是優于其他兩個算法的.

表2 實驗效果對比Table 2 Comparison of experimental results

在經過算法的性能對比后,對ET-DQN訓練完成的神經網絡進行性能測試,除了DQN和Prioritized-DQN以外,需要加入基準算法進行對比:隨機任務部署法:將應用隨機部署至各個邊緣計算節點處;衛星節點部署法:將所有任務部署至合適的衛星節點.

圖5和圖6中分別為時延與能耗性能對比.由圖可知,ET-DQN、DQN和Prioritized-DQN對任務處理時延都有一定程度的優化,在任務規模小于15時,ET-DQN、DQN和Prioritized-DQN的對時延的優化效果很接近,甚至在圖6中,任務規模為15時,Prioritized-DQN的性能優于ET-DQN,因為Prioritized-DQN訓練時總是盡可能選擇優先級高的經驗進行訓練,收斂快,任務量小時能展現出較好的性能.隨著任務數量的增大,Prioritized-DQN則出現過擬合現象,導致其性能變差.而ET-DQN在任務量小時也展現了很好的性能,隨著任務的增大,泛化能力更強,優化最為明顯且穩定,由此可得ET-DQN訓練出的模型在性能優化方面更為出色.

圖5 不同任務放置策略時延性能對比Fig.5 Comparison of delay performance of different task placement strategies

圖6 不同任務放置策略能耗對比Fig.6 Comparison of energy consumption of different task placement strategies

6 總結和展望

為了解決在衛星邊緣計算中,部署位置和計算資源分配不合理而導致任務處理時延過長、衛星能耗過大的問題,本文提出了基于SDN的衛星-地面聯合部署網絡架構SSGIN,同時對衛星網絡的成本模型進行分析,并改進了經典DQN算法的經驗池利用率低、過估計和難收斂的問題:提出ET-DQN以優化任務部署的時延與能耗.在仿真實驗中,對ET-DQN算法的收斂性、泛化性以及優化性能進行測試.仿真結果表明,所提出的任務部署算法能夠有效地減少了任務計算的處理延遲和系統能耗,并且算法能夠穩定地進行訓練和收斂.與典型的強化學習算法相比,學習效率明顯提高,能夠有效解決經典DQN算法經驗池利用率低,過估計以及難收斂的問題.ET-DQN雖能提提高傳統DQN的收斂速度,然而相較于Prioritized-DQN仍然收斂速度稍慢,而如何提高深度強化學習算法的收斂速度仍然需要后續的研究.