基于深度強化學習的衛星光網絡波長路由算法

李 信, 李勇軍, 趙尚弘

(空軍工程大學信息與導航學院, 陜西 西安 710003)

0 引 言

衛星通信系統因其在全球通信、遙感遙測、軍事指揮等許多應用領域的獨特優勢而引起了人們的廣泛關注。然而，隨著接入用戶的爆炸式增長和對通信質量要求的日益提升,傳統以微波通信技術為基礎的衛星網絡遇到了一些瓶頸,如有限的頻帶資源、較差的方向性和有限的通信容量等[1-5]。激光通信技術由于通信質量好、帶寬寬、功耗低等優點引起了人們的關注。隨著未來天地一體化進程的加速推進,衛星光網絡必然有廣泛的應用前景[6-10]。在衛星光網絡中,波長路由分配(routing and wavelength assignment,RWA)問題是一個研究的難點,動態的RWA問題已經被證明是NP-hard問題[11-14]。

現有對衛星光網絡的研究多是基于分布式網絡架構,很難產生基于全局最優的路由策略。軟件定義網絡(software defined network, SDN)架構以及網絡功能虛擬化(network functions virtualization, NFV)技術的出現為解決這一問題提供了可能。由于SDN架構可以實現控制與轉發的解耦,NFV技術可以實現網絡節點功能分塊化,已經有越來越多學者開始研究SDN架構和NFV技術與衛星光網絡波長路由技術的結合[15-20]。文獻[21]的提出基于SDN和NFV的天地一體化三層架構,證明了該體系架構可以實現靈活可靠的路由并且提高服務質量,并進行了相關實驗進行驗證,但是未考慮具體的算法實現。基于SDN架構,文獻[22]針對衛星光網絡的多業務問題,提出了一種改進蟻群算法,解決了衛星光網絡業務的多服務質量(quality of service, QoS)問題。

然而,以上路由算法大多是通過啟發式算法實現的,存在計算復雜度大、收斂速度慢、容易陷入局部最優等缺點。強化學習算法作為一種高效的智能化決策算法，已經開始應用于無線網絡路由決策中。強化學習可以通過智能體與環境之間的交互,快速得到接近全局最優解的路由解決方案,并且不需要精確的底層網絡數學模型[23-24]。文獻[25]首次提出基于傳統強化學習Q-learning算法的逐跳路由算法,并且證明其在動態網絡中性能優于傳統的路由協議。文獻[26]提出了一種基于深度強化學習的能量高效機會路由算法來解決無線多跳網絡中的路由問題,獲得了較好的路由和能耗性能,然而將其應用于衛星光網絡存在無法感知網絡環境狀態的問題。此外,由于衛星光網絡拓撲結構的動態變化和業務時空分布不均,會對波長路由策略產生較大影響。在進行路由策略選擇時應該考慮網絡當前的拓撲結構和業務負載大小,確定合適的動態波長路由策略,確保達到最優的網絡QoS[27]。

綜上,在基于SDN的中軌/低軌(medium earth orbit/low earth orbit, MEO/LEO)雙層衛星網絡架構基礎上,提出了基于深度強化學習的衛星光網絡波長路由算法(deep reinforcement learning routing and wavelength algorithm, DRL-RWA)。該算法在進行路由選擇前先通過深度學習來感知網絡鏈路連接情況和負載分布情況,創建智能體決策的環境,然后通過強化學習來進行路由決策。在進行路由選擇時綜合考慮鏈路當前時延、波長利用率、丟包率等信息,從而找到一條滿足QoS的較優路徑。

1 系統模型及問題描述

1.1 衛星光網絡模型

圖1所示為基于SDN的衛星光網絡3層架構。網絡的應用層主要由通信、導航、遙感和探測等各種空間任務組成[28]。控制層包含網絡的智能決策模塊,是整個網絡進行控制的核心,由若干高軌道(geosynchronous earth orbit, GEO)衛星控制器或MEO控制器組成,本文采用時延較小、組網靈活的MEO衛星作為控制器,MEO衛星通過星間鏈路收集LEO衛星的全網信息并通過深度強化學習算法制定和下發路由策略。基礎設施層由具有轉發功能的LEO衛星組成,主要執行兩個任務：一是上傳節點當前狀態信息和業務到達信息;二是根據MEO衛星下發的路由表進行數據的轉發。

圖1 基于SDN的衛星光網絡架構Fig.1 Optical satellite network architecture based on SDN

1.2 問題描述

圖2所示為基于深度強化學習的衛星光網絡路由機制的基本過程。通過引入SDN架構,可以實現網絡的集中控制,控制器可以掌握整個網絡的狀態信息,從而實現全局最優的路由決策。當有業務到達LEO衛星時,LEO衛星將當前的業務信息和自身鏈路狀態信息通過南向接口上傳至對應的MEO衛星。為了簡化單個LEO衛星被多個MEO衛星同時覆蓋的問題,假設LEO衛星只和距離最近的MEO衛星建立激光鏈路。MEO衛星中的SDN控制器收集全網的鏈路狀態信息和業務請求信息,通過深度學習的感知能力來創造與智能體交互的環境,通過強化學習算法構造獎勵函數,對各種路徑進行試探,最終得到最優的路由決策,并通過南向接口下發至LEO衛星。LEO衛星根據MEO衛星下發的路由表進行轉發,并將最終服務質量信息上傳至MEO衛星,用于更新深度學習感知數據庫。

圖2 基于深度強化學習的路由過程Fig.2 Routing process based on deep reinforcement learning

在該路由機制下,由于實現了控制層面和轉發層面的解耦,LEO衛星只需要根據路由表進行業務轉發,減小了LEO衛星的計算復雜度。在MEO衛星控制層面,在深度學習感知的基礎上,利用強化學習進行路由決策代替傳統的啟發式算法,可以減小計算復雜度,加快收斂,提高網絡性能。

2 基于深度強化學習的路由策略

2.1 算法框架

深度強化學習將深度學習的感知能力和強化學習的決策能力相結合,以不斷試探的方式與環境進行相互交互,通過最大化獎勵函數的方式來獲得最優決策。如圖3所示,深度學習感知模塊根據當前LEO衛星上傳的用戶業務信息和鏈路狀態信息來感知環境狀態,為強化學習進行決策提供當前環境狀態信息。強化學習決策模塊中智能體將深度學習感知的環境信息視為狀態,衛星之間的鏈路選擇視為動作,根據鏈路權重設置獎勵,根據獲得的獎勵來調整當前和下一步的動作,最終達到獎勵最大化。通過訓練,智能體執行一系列動作獲得最大獎勵值,對應到衛星光網絡,即選擇了一條滿足多種服務質量約束的最優路徑。本文強化學習算法采用的是Q學習算法,這是一種經典的強化學習離線算法。

圖3 基于深度強化學習的路由算法基本框架Fig.3 A basic framework of routing algorithms based on deep reinforcement learning

2.2 路由策略

2.2.1 數學模型

深度強化學習的任務定義中主要有智能體和環境兩個可以進行交互的對象,基本要素有狀態s、動作a、狀態轉移概率p(s,a,s′)、即時獎勵r(s,a,s′)。通過四元數組(S,A,P,R)來定義深度強化學習的數學模型。

S={s1,s2,…，sn}為有限狀態集,代表LEO衛星當前業務信息和鏈路狀態信息,通過深度學習模塊的感知得到。

A={a1,a2,…，an}為有限動作集,代表當前LEO衛星節點業務可選擇的所有光鏈路情況的集合。

P={(sn,an,sn+1)}為概率轉移集,表示在狀態sn情況下選擇動作an對應光鏈路的概率,sn+1為選擇動作an后的下一狀態。

R={(sn,an,sn+1)}為獎勵集合,表示在狀態sn情況下選擇動作an轉移到狀態sn+1可以得到的獎勵大小。

2.2.2 獎勵設計

深度強化學習的目的是實現獎勵最大化,即為當前業務找到符合要求的最優路徑。基于Q學習算法,智能體根據當前網絡拓撲中的實時鏈路連接狀態,為當前業務找到一條符合QoS約束的最優路徑。獎勵函數值的確定應該考慮鏈路當前的時延、可用波長、丟包等參數。基于QoS的獎勵函數為

(1)

(2)

式中:Delayij(n)表示節點上的排隊時延;Delayij(e)表示鏈路上的傳播時延。

(3)

式中:Lossij(e)表示單位時間內路徑Lij中鏈路e的丟包率。

(4)

式中:|Nij|表示鏈路Lij上的總波長數；nij(t)表示t時刻鏈路Lij上被占用的波長。

歸一化處理方法如下,以Delayij為例:

(5)

式中:Delaymax和Delaymin分別表示當前路徑上所有節點間鏈路的最大時延和最小時延。

為了解決鏈路中的瓶頸因子對鏈路質量的約束,即路由鏈路中單條鏈路上較大的時延、較大的丟包率和較小的剩余波長數對整個鏈路質量的影響,引入Q調節因子,定義如下:

(6)

(7)

衛星網絡中,每次路徑的選擇并非隨機的,每個衛星節點需要根據一個既定的選擇策略來選擇一條鏈路到達下一個衛星節點。因此,在Q學習算法中,需要引入一個動作選擇策略π(st,at),即在狀態st下,智能體根據π(st,at)來執行動作at。

對于每次的動作選擇,可以分成兩種情況:對未知網絡空間的采樣叫做“探索”,利用探索的結果進行預測叫做“利用”,而“探索”和“利用”兩者是矛盾的。 Softmax算法是一種基于已知動作的平均獎勵來對“探索”和“利用”進行折中的動作選擇策略。對于softmax策略,處于st狀態下選擇動作at的概率π(st,at)服從

(8)

式中:n為采取的動作數；Q(st,at)為狀態-動作價值函數;τn是“溫度”參數,τn越小越趨于“利用”,τn越大越趨于“探索”。為實現有限時間內的學習收斂,將溫度設置為隨時間的線性函數

(9)

式中:T為達到收斂的時間;τ0和τT分別是初始時刻的溫度和最后T時刻的溫度。路由選擇的過程中,衛星節點可以通過上述π(st,at)動作選擇策略進行鏈路選擇,最終達到獎勵最大化。

智能體每次從當前狀態執行動作轉移到下一狀態時,都需要更新Q(st,at),其Q(st,at)的更新如下：

Qt+1(st,at)=(1-α)Qt(st,at)+
α[R(st,at)+γmaxQt(st+1,at+1)]

(10)

式中:α∈[0,1]為學習因子,表示學習速率；γ∈[0,1]為折扣因子,表示長期收益的重要性；maxQ(st+1,at+1)表示智能體執行不同的動作可以獲得的最大累積回報的估計值。

2.3 算法流程

基于深度強化學習的衛星光網絡波長路由算法實現步驟如下。

DRL-RWA算法1: 輸入 初始化網絡, 設定學習因子α;折扣因子γ;迭代次數N;輸出 當前最優路由策略2: 深度學習感知階段3: 根據請求業務和鏈路狀態,生成感知環境;4: 將感知環境輸出到強化學習模塊5: 強化學習決策階段for i=1,2,…,N, do6: 智能體通過深度學習模塊得到初始狀態st7: 按照式(8)選擇動作at8: 按照式(7) 獲得獎勵rt并存儲,進入下一狀態st+19: if st+1不為目的節點,then執行步驟710:else 結束,記錄本次路由表,并計算累計獎勵R11:find最大獎勵R的策略為當前最優路徑12:end if13:end14:下發當前路由策略

2.4 波長分配方法

衛星光網絡中視頻、話音和數據等業務對時延和帶寬的要求不同,即使同一類業務在軍用、商用和民用等不同場景中對服務質量的要求也不同,因此應該對不同業務進行劃分等級。根據對時延和吞吐量要求的不同,將業務劃分為A、B、C 3種等級。A等級業務對時延和吞吐量都有較高的要求,B等級業務對吞吐量有較高要求但對時延有一定的容忍,C等級業務為盡力而為型,對時延和吞吐量都有一定的容忍。

針對A、B、C 3種不同等級的業務,采用波長分組競爭合作機制進行波長分配。設LEO衛星光鏈路之間可用波長數為6,即λV=(λ1,λ2,λ3,λ4,λ5,λ6),A、B、C 3種等級的業務的可用波長集分別為λA=(λ1,λ2,λ3,λ4),λB=(λ5,λ4,λ3),λc=(λ6,λ5),波長集中波長的先后順序表示該波長在該等級業務中的優先級,例如對于B類業務,波長優先級順序為λ5>λ4>λ3,采用這種順序可以減少波長沖突,降低阻塞率。對于不同業務中的公共波長,高優先級業務可以搶占低優先級業務對應的波長。波長分配步驟如圖4所示。

圖4 區分優先級波長分配Fig.4 Priority wavelength assignments

2.5 算法復雜度分析

DRL-RWA算法在搜尋最優路徑時采用的基本方法是最大累計獎勵原則,當網絡中衛星節點數量為m,可用波長數為λ時,算法復雜度為O(λm2)。若設置迭代次數為k時獲得可行最優路徑,則時間復雜度為O(kλm2),而深度優先搜索(deep-first search, DFS)算法、廣度優先搜索(breadth-first search, BFS)算法的時間復雜度均為O(kλ2m2)。相比來說,DRL-RWA算法時間復雜度較小,適用于計算資源受限的星上環境。

3 仿真結果分析

3.1 場景設置

本文首先利用STK仿真軟件模擬基于SDN的衛星光網絡架構,并產生相應的網絡拓撲結構和連接關系,在此基礎上使用Matlab軟件對提出的算法進行了仿真驗證。

仿真的場景如圖5所示,控制層由MEO衛星組成,包含智能體感知決策模塊,負責制定和下發全網路由策略。基礎設施層由LEO衛星組成,通過路由表進行全網業務的轉發。網絡中鏈路均采用激光鏈路。

圖5 仿真場景設計Fig.5 Simulation scene design

衛星光網絡仿真參數如表1所示。仿真過程中,業務類型包括A、B、C 3種等級。在LEO光網絡中隨機選取6對源目的節點衛星,進行某一種等級業務的傳輸,并且隨著時間的增加,業務強度即每個節點的業務請求次數不斷增加。

表1 仿真參數設置

3.2 仿真結果分析

α,γ值的選取對算法收斂性能有重要的影響,因此對不同的α,γ值對平均訓練步數的影響進行數值計算,結果如圖6所示。從結果中可以看出,隨著學習因子α的增大,算法收斂速度加快,由于較小的折扣因子γ更加關注當前回報,而較大的折扣因子γ更加關注長遠回報,因此折扣因子γ的取值應該適當。因此,本文在訓練中取α=0.9,γ=0.6。

圖6 α,γ與平均訓練步數的關系Fig.6 α,γ in relation to the average number of training steps

對本文提出的DRL-RWA算法性能進行分析,分別在平均傳輸時延、平均丟包率、波長利用率3個方面與Q-Routing算法和SDRA算法進行比較。其中,SDRA算法是一種基于SDN架構的最短路徑算法[29],Q-Routing算法可看作是強化學習和Dijkstra的結合,其獎勵函數設置相對簡單,收斂速度較快,也能在一定程度上緩解鏈路擁塞[30]。

平均時延隨業務強度變化的曲線如圖7所示。當業務強度較小時,由于網絡負載較小,3種算法所選路徑基本相同,因此平均時延相差較小。隨著業務強度的增大,SDRA算法不考慮鏈路時延,選擇的路徑會變得擁塞,會導致業務的平均端到端時延不斷增大,而DRL-RWA算法和Q-routing算法會選擇避開負載較大的鏈路,優先選擇時延較小的鏈路。DRL-RWA算法在路由選擇的過程中綜合考慮了鏈路的時延瓶頸因子,因此當服務請求數較多時,DRL-RWA算法的平均時延特性更好。

圖7 平均時延仿真結果Fig.7 Average time-delay simulation results

波長利用率隨業務強度變化的曲線如圖8所示。當業務強度較小時,由于網絡負載較輕,3種算法的波長利用率差別不大。隨著服務請求數量的增加,Q-routing算法和DRL-RWA算法的波長利用率與SDRA算法相比顯著增加。當服務請求數較大時,由于SDRA算法會導致網絡擁塞,從而帶寬利用率基本不再增加。而DRL-RWA算法在路由選擇的過程中綜合考慮了鏈路波長占有情況和波長瓶頸因子因素,使得其在帶寬利用率方面有更好的表現。

圖8 波長利用率仿真結果Fig.8 Simulation results of the wavelength utilization rate

平均丟包率隨業務強度變化的曲線如圖9所示。當業務強度較小時,3種算法的丟包率也基本相同。隨著服務請求數的增大,SDRA算法在路由過程中未考慮網絡中鏈路的當前占用情況,部分鏈路開始出現擁塞,導致丟包率迅速增加,因此SDRA算法的丟包率明顯高于其他兩種路由算法。Q-routing算法和DRL-RWA算法都可以動態感知網絡節點的占用情況,丟包率比SDRA算法有顯著降低。在服務請求數量較多的情況下,DRL-RWA算法考慮鏈路的丟包率瓶頸因子,因此平均丟包率更低。

圖9 平均丟包率仿真結果Fig.9 Simulation results of the average packet loss rate

不同業務強度下不同等級業務阻塞率的比較如圖10所示。由圖10可知,隨著業務強度的增加,由于C等級業務可用波長較少,因此阻塞率迅速增加。A等級業務由于可用波長數較多并且可以搶占B等級業務的波長,因此A等級業務的阻塞率維持在較低水平。由結果可知,對業務進行劃分等級可以有效降低高優先級業務的網絡阻塞率,提高衛星光網絡按需服務能力。

圖10 阻塞率仿真結果Fig.10 Blocking rate simulation results

4 結 論

本文提出了一種基于深度強化學習的衛星光網絡波長路由算法,基于SDN的MEO/LEO雙層衛星光網絡架構下,將深度學習對環境的感知能力和強化學習的決策能力相結合,實現衛星光網絡多QoS波長路由。提出的DRL-RWA算法在進行基于價值動作狀態函數的路徑選擇時,綜合考慮了鏈路的時延、丟包率和剩余波長,并且考慮了鏈路瓶頸因子對網絡性能的限制。仿真結果表明,與SDRA算法和Q-routing算法相比,本文所提算法在時延、波長利用率和丟包率方面均有較優的性能,此外,還降低了高優先級業務的阻塞率。下一步,可將深度強化學習與衛星光網絡流量均衡和功率代價成本相結合,在保證業務對多QoS需求的同時,提高衛星光網絡資源的綜合利用率。