一種基于深度Q網絡改進的低軌衛星路由算法

許向陽 彭文鑫 李京陽

DOI：10.19850/j.cnki.2096-4706.2024.01.014

收稿日期：2023-06-05

摘? 要：針對衛星節點高速移動，導致節點之間鏈路狀態變化過快的問題，對基于深度強化學習的衛星路由算法進行了研究，由此提出一種基于深度Q網絡改進的衛星路由算法。算法采用虛擬節點的思想，以最小跳數為原則，將跳數和距離設置為獎勵函數相關參數。同時設置優先經驗回放機制，使得算法訓練中學習價值最高的樣本；最后對網絡進行參數的設置并且進行訓練。仿真結果表明，從網絡傳輸時延、系統吞吐量、丟包率方面有明顯的提升，能有效地適應衛星節點之間鏈路狀態高動態變化。

關鍵詞：衛星路由；虛擬節點；優先經驗回放；深度Q網絡

中圖分類號：TN927+.2? ? ? ? 文獻標識碼：A? 文章編號：2096-4706（2024）01-0067-05

An Improved Low-orbit Satellite Routing Algorithm Based on DQN

XU Xiangyang， PENG Wenxin， LI Jingyang

（School of Information Science and Engineering， Hebei University of Science and Technology， Shijiazhuang? 050018， China）

Abstract： To deal with the problem of fast-changing link-state between satellite nodes due to high-speed movement of satellite nodes， a satellite routing algorithm based on deep reinforcement learning is studied， and an improved satellite routing algorithm based on DQN is proposed. The algorithm adopts the idea of virtual nodes， and sets the number of hops and distance as the related parameters of reward function based on the principle of minimum hops. Meanwhile， a priority experience replay mechanism is set up to train the algorithm by learning samples with the highest value. Finally， the network is set in parameters and is trained. The simulation results show that there are significant improvements in network transmission delay， system throughput， and rate of packet loss， effectively adapting to high dynamic changes in link-state between satellite nodes.

Keywords： satellite routing; virtual node; priority experience replay; DQN

0? 引? 言

近年來，隨著無線通信技術的發展與技術的迭代，地面基站受限于地形限制、抗毀性差等因素，無法真正實現全球覆蓋。而衛星通信以其覆蓋范圍廣、抗毀性強、不受地理環境約束等優勢在移動通信領域得到廣泛的應用[1]。相比于中、高軌衛星，低軌衛星具有傳輸時延更小、鏈路損耗較低、整體制造成本低等優勢[2]。使得構建低軌衛星星座網絡成為研究重點。與地面網絡相比，低軌衛星網絡存在諸多優勢，但仍存在網絡節點變化過快、節點處理能力不足[3]，數據包傳輸效率較低等問題。網絡拓撲結構存在高動態和時變性[4]，使得地面網絡的路由方法無法有效應用于低軌衛星網絡。Taleb等人指出衛星網絡內存在當局部節點已經處于高負載狀態時，其他節點卻一直處于空閑狀態的情況，在此基礎上提出了一種基于顯示負載均衡（Explicitload Balancing， ELB）的算法。BominMao等人提出了一種基于張量的深度學習智能路由（A Tensor Based Deep Learning Technique for Intelligence Packet Routing）策略，根據開放式最短路徑優先（Open Shortest Path First， OSPF）協議中的歷史提取路由信息，針對每個源節點和目的節點對建立基于張量的深度信念網絡（Tensor-based Deep Nelief Architecture， TDBA），利用深度信念網絡提取路由信息中的深層維度特征，在應用時，只需要輸入當前的路由信息張量即可得到最優的下一跳節點。深度強化學習對復雜問題具有強大的表征能力和解決能力[5]，可以為解決問題提供了新的思路。針對低軌衛星的一些問題，本文設計一種基于深度強化學習改進的低軌衛星路由算法，該方法將整個衛星網絡作為深度強化學習的環境，將衛星節點作為智能體。基于STK軟件建立低軌衛星模型，選用極軌道星座模型中的銥星系統作為研究對象，由NS3平臺負責輸出結果，設計的算法應具備低時延、低丟包率以及較高系統吞吐量的特點。

1? 深度Q網絡

傳統的強化學習算法在面對一些大狀態空間或連續狀態空間的學習任務時，通常需要耗費大量時間和計算資源才能學習到一個比較合理的解決方案。這是由于狀態空間的維度很高，導致狀態-動作空間的規模呈指數級增長，使得傳統算法在搜索過程中面臨維數災難問題。

隨著深度學習的發展，研究人員在強化學習中引入了神經網絡，通過神經網絡來估計動作價值，通過強化學習來獲取最大化獎勵。從而解決了狀態空間維度高的問題。這種結合兩者優勢的方法被稱為深度強化學習（Deep Reinforcement Learning， DRL）[6]。

在訓練過程中，DQN使用經驗回放和固定目標網絡來提高學習效率和穩定性。但單一神經網絡對狀態-動作值進行估計，會高估動作的Q值，從而造成某些狀態下次優動作獎勵值會優于最優動作，從而找不到最優策略，導致算法訓練不穩定。針對此情況，本文引入DQN算法作為路由算法的基礎。

Dueling DQN算法通過將網絡拆分為兩個部分來進一步提高學習效率和穩定性[7，8]。這兩個部分分別是狀態價值函數和優勢函數。價值函數V（s; α， θ）用來估計每個狀態的價值，僅與狀態有關，與將要執行的動作無關，優勢函數A（s， α; β， θ）來估計每個動作的優劣程度，與狀態動作都有關，最后的輸出則將兩者相加，如下所示：

（1）

其中α表示價值函數支路的網絡參數，β表示優勢函數支路的網絡參數，θ表示卷積層公共部分的網絡參數。但直接訓練會存在將V值訓練為固定值時，則算法變為DQN算法，則需要為神經網絡增加一個約束條件，則Q值函數計算如下所示：

（2）

2? 改進的Dueling DQN算法

2.1? 經驗回放機制的改進

在原始的RL算法中，每次使用完一個樣本（st，at，rt，st+1）就丟棄，造成經驗的浪費，并且相關性強，不利于模型的學習。對此情況，Nature DQN算法設置了經驗池，為了更新深度神經網絡的參數，從經驗池中隨機選擇一小批樣本作為訓練更新的樣本。使用經驗回放機制，每次采樣時都從經驗池中隨機選擇樣本。這種隨機選擇樣本的方式可以有效打破樣本之間的相關性，從而更好地訓練深度神經網絡。

隨機采樣是在經驗池中等概率的隨機選擇樣本，可能會存在信息價值較高的樣本在神經網絡的訓練中使用率比較低甚至沒有被使用過的情況，會使得訓練次數增加導致訓練效率變低。為防止出現此類問題，本章使用優先經驗回放[9，10]來進行采樣。核心思想是利用經驗樣本的重要性來加快學習速度和提高學習效果。在這種方法中，智能體會優先選擇最有價值的一批樣本來訓練，提升深度強化學習的效率和性能。為了防止過擬合，低價值的樣本也會有一定的概率被選擇。優先經驗回放樣本采樣見式（3）與式（4）：

（3）

（4）

其中，P（t）表示第t個經驗被采樣的概率，pt表示樣本優先級，α表示一個超參數，用于控制優先級的衰減速度。δt表示時間差分誤差，又稱為時序誤差，通常用于衡量代理在執行動作后，對于預期獎勵的估計值與實際獎勵之間的差異。時序誤差一般是用來更新行為值函數，時序誤差絕對值越大，說明其學習價值越高。優先經驗回放采用時序誤差，可以使得增加價值高的樣本的重要性和減少錯誤行為發生的概率。而ε的設置則是為了保證時序誤差為零時采樣概率不為零，時序誤差計算公式由式（5）可得：

（5）

其中，Rt表示當前的獎勵，γ表示衰減因子，Q′（St， At， θ′）是目標網絡。在訓練過程中，當從回放緩沖區中按照優先級采樣一批經驗樣本進行訓練時，優先級高的樣本會被更頻繁地選擇進行訓練，以提高重要經驗樣本的學習效率。優先經驗回放步驟如下：

1）對于每個樣本（st，at，rt，st+1），計算時序誤差δt。

2）根據時序誤差得出優先級高低，時序誤差越大，優先級越高，將樣本添加到經驗回放緩沖區。

3）根據優先級高低對樣本排序。

4）在每次訓練時，從經驗回放緩沖區按照優先級采樣一批樣本進行訓練。

2.2? 獎勵函數

在使用DQN算法進行訓練時，將獎勵函數作為目標Q值的計算基礎。在每個時間步，計算出當前狀態下所有可能的行動的Q值，并根據當前的行動選擇一個最優的行動，用于下一個時間步的狀態轉移。然后，我們可以計算當前狀態下選擇的行動的Q值和目標Q值之間的差異，將其作為樣本的時序誤差，用于訓練DQN的神經網絡。本節設置的路由算法的目標是在已知源節點和目的節點的情況下，選擇合適的鏈路來進行數據傳輸。因此設定的獎勵函數以最小跳數鏈路為優先選擇。獎勵函數R由跳數評價函數Hc、源節點與目的節點距離Di， j （t）構成。具體設置如式（6）所示：

（6）

其中μ，η表示權重參數，令其μ + η = 1，將最大獎勵設置為Ra，Ra表示絕對值較大的正獎勵，當下一跳為目的節點時，獎勵最大，其他情況獎勵均為負值。在獎勵函數設置時，衛星執行當前動作后，下一跳節點距離和目的節點相對距離越近，獎勵值越大。節點距離Di， j （t）可由升交點赤經的差值Δλ和真近地點角差值Δω來表示，見式（7）：

（7）

（8）

在路由算法中，為了避免追求最大獎勵值從而產生路由跳數過多的問題，設置路由最大跳數N，令當前跳數為n，可設置跳數評價函數Hc，見公式（8）。當跳數越來越大時，Hc趨向于1。

2.3? 模型訓練

在算法中，需要對模型的狀態S、動作A、獎勵函數R、狀態轉移概率P、折扣率γ進行設置。其中，狀態S設置為鏈路狀態，動作A設置為下一跳衛星節點，狀態轉移概率P為選擇下一跳節點的概率，獎勵函數R設置為當前路由到下一跳衛星節點的獎勵，折扣率γ為未來期望獎勵權重。模型訓練是輸入鏈路狀態和目的節點，來選擇到目的節點的最優下一跳節點。

在算法中，由于使用了優先經驗回放，使得樣本的分布發生改變，產生重要性采樣權重，如式（9）所示：

（9）

其中，N表示樣本容量，β為超參數，代表優先經驗回放對收斂結果的影響程度，由此可得，采用優先經驗回放的DQN算法的Loss函數如式（10）所示：

（10）

基于DQN改進的算法完整流程：

輸入：網絡拓撲G（V，E）、狀態空間S、學習率λ、動作空間A、折扣率γ、目標網絡更新參數頻率F、回合M、迭代次數T。

輸出：訓練完成的DQN模型。

1）初始化經驗池D、Q網絡參數θ、目標Q網絡θ′、α，β超參數；

2）for episode =1 to M do：

3）? ? 初始化環境，得到初始狀態St；

4）? ? for iteration t =1 to T do：

5）? ? ? ? 采用ε貪婪策略選擇動作，隨機選擇一個動作；

6）? ? ? ? 執行動作At，觀察獎勵Rt和下一個狀態St+1；

7）? ? ? ? 計算時序誤差，存儲經驗到經驗池D；

8）? ? ? ? 將樣本（st，at，rt，st+1）添加到經驗池D中，更新優先級并從高到低進行排序；

9）? ? ? ? 當經驗池D中的樣本大于某個閾值，從中刪除優先級最低的樣本；

10）? ? ? ?從經驗池D中隨機采樣N個樣本進行訓練；

11）? ? ? ?對于每個（St，At，Rt，St+1）執行以下步驟；

12）? ? ? ? ? ?if St+1是終止狀態，則Q_target=Rt；

13）? ? ? ? ? ?else 用目標Q網絡計算Q_target = Rt + γ max Q′（St， At， θ′ ）；

14）? ? ? ?使用反向傳播算法更新神經網絡參數θ；

15）? ? ? ? ? 計算當前狀態下執行At的Q值Q（St，At），以及當前狀態下所有行動的Q值；

16）? ? ? ? ? 計算Q_target和Q（St，At）之間的時序誤差δt；

17）? ? ? ? ? 計算Loss函數；

18）? ? ? ? ? 使用梯度下降算法更新Q值網絡：θ = θ - λ*θ ? Loss；

19）? ? ? ? ? 每隔F步更新目標Q網絡：θ′←θ；

20）? ? ? ?更新狀態S = St+1；

21）? ? end for

22）end for

3? 仿真

3.1? 仿真參數設置

為了評估算法性能，利用NS3仿真軟件，在一個類似銥星衛星網絡中構建仿真。其中，66顆衛星分布在六個平面上。每顆衛星有兩個層內鏈路和兩個層間鏈路，層內鏈路一直連接，層間鏈路在反向縫區域斷開。設置同層衛星鏈路帶寬為25 Mbit/s，層間鏈路帶寬為1.5 Mbit/s，隊列緩沖大小為50 kB。數據包大小設置為1 kB，Hello包發送周期仿真時間設置為90 s。仿真參數和算法訓練參數分別如表1和表2所示。

3.2? 仿真結果分析

與本文算法進行對比的路由算法為SPF路由算法和ELB路由算法，將通過網絡平均傳輸時延和丟包率以及系統吞吐量三個方面進行對比。

3.2.1? 網絡平均傳輸時延

如圖1所示，隨著數據傳輸速率不斷增大，網內傳輸數據包數量增加，逐漸達到鏈路帶寬上限，所以網絡中數據包的傳輸平均時延上升。通過仿真結果可以看出，本文路由算法在網絡傳輸時延上略優于SPF算法和ELB算法。由于采用了DQN模型進行路由計算，訓練后的模型遵循最短路徑的原則去選擇路徑，并在鏈路狀態變化時，對鏈路進行切換從而減少節點擁塞問題。

3.2.2? 丟包率

如圖2所示的仿真結果表明，本文算法在丟包率上當鏈路狀態到達擁塞時，將會將數據轉發到次優鏈路，有效地降低了丟包率。

3.2.3? 吞吐量

吞吐量是對衛星網絡中路由算法在一定時間內的數據傳輸總容量的衡量標準。系統仿真結果如圖3所示。

由仿真結果可知，隨著數據傳輸的速率的增大，系統吞吐量也在提升。由于獎勵函數的設置，使得數據包會往距離最近，時延最短的方向進行轉發，算法可以快速為衛星提供下一跳節點的選擇，從而使得同樣的時間內，衛星節點可以處理更多的任務，提升系統的吞吐量。

4? 結? 論

本文針對低軌衛星網絡存在的高動態性的問題，提出了一種基于深度強化學習的衛星路由算法，并通過設置相應的參數以及改進的采樣機制來實現更好的效果。仿真結果表明，基于優先經驗采樣機制的深度強化學習算法有效降低了數據發送時延，降低了丟包率，提高了系統吞吐量。

參考文獻：

[1] IZZAT G，MOHAMMED H.Optimised routing algorithm in low Earth orbit satellite network [J].International journal of ad hoc and ubiquitous computing，2021，36（4）：230-237.

[2] 吳署光，王宏艷，王宇，等.低軌衛星網絡路由技術研究分析 [J].衛星與網絡，2021（9）：66-74.

[3] KUANG Y，YI X，HOU Z. Congestion avoidance routing algorithm for topology-inhomogeneous low earth orbit satellite navigation augmentation network [J].International Journal of Satellite Communications and Networking，2021，39（2）：221-235.

[4] 頓聰穎，金鳳林，譚詩翰，等.衛星網絡負載均衡路由技術研究綜述 [J].信息技術與網絡安全，2021，40（4）：46-55+63.

[5] WEI D，ZHANG J，ZHANG X，et al. Plume：Lightweight and Generalized Congestion Control with Deep Reinforcement Learning [J].China Communications，2022，19（12）：101-117.

[6] LIU W，CAI J，CHEN Q，et al. DRL-R：Deep reinforcement learning approach for intelligent routing in software-defined data-center networks [J/OL].Journal of network and computer applications，2021，177（Mara）：102865[2023-02-24].https：//doi.org/10.1016/j.jnca.2020.102865.

[7] 楊思明，單征，丁煜，等.深度強化學習研究綜述 [J].計算機工程，2021，47（12）：19-29.

[8] 趙星宇，丁世飛.深度強化學習研究綜述 [J].計算機科學，2018，45（7）：1-6.

[9] LI Z，XIE Z，LIANG X. Dynamic Channel Reservation Strategy Based on DQN Algorithm for Multi-Service LEO Satellite Communication System [J].IEEE Wireless Communications Letters，2021，10（4）：770-774.

[10] GUAN Y，LIU B，ZHOU J，et al. A New Subsampling Deep Q Network Method [C]//2020 International Conference on Computer Network，Electronic and Automation（ICCNEA）.Xi'an：IEEE，2020：26-31.

作者簡介：許向陽（1967—），男，漢族，河北石家莊人，副教授，碩士導師，碩士，主要研究方向：無線自組網、衛星通信；彭文鑫（1999—），男，漢族，河北唐山人，碩士在讀，主要研究方向：衛星路由；李京陽（1997—），男，漢族，河北滄州人，碩士在讀，主要研究方向：衛星路由。