一種基于深度Q網(wǎng)絡(luò)改進的低軌衛(wèi)星路由算法

許向陽 彭文鑫 李京陽

DOI：10.19850/j.cnki.2096-4706.2024.01.014

收稿日期：2023-06-05

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

關(guān)鍵詞：衛(wèi)星路由；虛擬節(jié)點；優(yōu)先經(jīng)驗回放；深度Q網(wǎng)絡(luò)

中圖分類號：TN927+.2? ? ? ? 文獻標(biāo)識碼：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? 引? 言

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

1? 深度Q網(wǎng)絡(luò)

傳統(tǒng)的強化學(xué)習(xí)算法在面對一些大狀態(tài)空間或連續(xù)狀態(tài)空間的學(xué)習(xí)任務(wù)時，通常需要耗費大量時間和計算資源才能學(xué)習(xí)到一個比較合理的解決方案。這是由于狀態(tài)空間的維度很高，導(dǎo)致狀態(tài)-動作空間的規(guī)模呈指數(shù)級增長，使得傳統(tǒng)算法在搜索過程中面臨維數(shù)災(zāi)難問題。

隨著深度學(xué)習(xí)的發(fā)展，研究人員在強化學(xué)習(xí)中引入了神經(jīng)網(wǎng)絡(luò)，通過神經(jīng)網(wǎng)絡(luò)來估計動作價值，通過強化學(xué)習(xí)來獲取最大化獎勵。從而解決了狀態(tài)空間維度高的問題。這種結(jié)合兩者優(yōu)勢的方法被稱為深度強化學(xué)習(xí)（Deep Reinforcement Learning， DRL）[6]。

在訓(xùn)練過程中，DQN使用經(jīng)驗回放和固定目標(biāo)網(wǎng)絡(luò)來提高學(xué)習(xí)效率和穩(wěn)定性。但單一神經(jīng)網(wǎng)絡(luò)對狀態(tài)-動作值進行估計，會高估動作的Q值，從而造成某些狀態(tài)下次優(yōu)動作獎勵值會優(yōu)于最優(yōu)動作，從而找不到最優(yōu)策略，導(dǎo)致算法訓(xùn)練不穩(wěn)定。針對此情況，本文引入DQN算法作為路由算法的基礎(chǔ)。

Dueling DQN算法通過將網(wǎng)絡(luò)拆分為兩個部分來進一步提高學(xué)習(xí)效率和穩(wěn)定性[7，8]。這兩個部分分別是狀態(tài)價值函數(shù)和優(yōu)勢函數(shù)。價值函數(shù)V（s; α， θ）用來估計每個狀態(tài)的價值，僅與狀態(tài)有關(guān)，與將要執(zhí)行的動作無關(guān)，優(yōu)勢函數(shù)A（s， α; β， θ）來估計每個動作的優(yōu)劣程度，與狀態(tài)動作都有關(guān)，最后的輸出則將兩者相加，如下所示：

（1）

其中α表示價值函數(shù)支路的網(wǎng)絡(luò)參數(shù)，β表示優(yōu)勢函數(shù)支路的網(wǎng)絡(luò)參數(shù)，θ表示卷積層公共部分的網(wǎng)絡(luò)參數(shù)。但直接訓(xùn)練會存在將V值訓(xùn)練為固定值時，則算法變?yōu)镈QN算法，則需要為神經(jīng)網(wǎng)絡(luò)增加一個約束條件，則Q值函數(shù)計算如下所示：

（2）

2? 改進的Dueling DQN算法

2.1? 經(jīng)驗回放機制的改進

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

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

（3）

（4）

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

（5）

其中，Rt表示當(dāng)前的獎勵，γ表示衰減因子，Q′（St， At， θ′）是目標(biāo)網(wǎng)絡(luò)。在訓(xùn)練過程中，當(dāng)從回放緩沖區(qū)中按照優(yōu)先級采樣一批經(jīng)驗樣本進行訓(xùn)練時，優(yōu)先級高的樣本會被更頻繁地選擇進行訓(xùn)練，以提高重要經(jīng)驗樣本的學(xué)習(xí)效率。優(yōu)先經(jīng)驗回放步驟如下：

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

2）根據(jù)時序誤差得出優(yōu)先級高低，時序誤差越大，優(yōu)先級越高，將樣本添加到經(jīng)驗回放緩沖區(qū)。

3）根據(jù)優(yōu)先級高低對樣本排序。

4）在每次訓(xùn)練時，從經(jīng)驗回放緩沖區(qū)按照優(yōu)先級采樣一批樣本進行訓(xùn)練。

2.2? 獎勵函數(shù)

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

（6）

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

（7）

（8）

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

2.3? 模型訓(xùn)練

在算法中，需要對模型的狀態(tài)S、動作A、獎勵函數(shù)R、狀態(tài)轉(zhuǎn)移概率P、折扣率γ進行設(shè)置。其中，狀態(tài)S設(shè)置為鏈路狀態(tài)，動作A設(shè)置為下一跳衛(wèi)星節(jié)點，狀態(tài)轉(zhuǎn)移概率P為選擇下一跳節(jié)點的概率，獎勵函數(shù)R設(shè)置為當(dāng)前路由到下一跳衛(wèi)星節(jié)點的獎勵，折扣率γ為未來期望獎勵權(quán)重。模型訓(xùn)練是輸入鏈路狀態(tài)和目的節(jié)點，來選擇到目的節(jié)點的最優(yōu)下一跳節(jié)點。

在算法中，由于使用了優(yōu)先經(jīng)驗回放，使得樣本的分布發(fā)生改變，產(chǎn)生重要性采樣權(quán)重，如式（9）所示：

（9）

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

（10）

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

輸入：網(wǎng)絡(luò)拓撲G（V，E）、狀態(tài)空間S、學(xué)習(xí)率λ、動作空間A、折扣率γ、目標(biāo)網(wǎng)絡(luò)更新參數(shù)頻率F、回合M、迭代次數(shù)T。

輸出：訓(xùn)練完成的DQN模型。

1）初始化經(jīng)驗池D、Q網(wǎng)絡(luò)參數(shù)θ、目標(biāo)Q網(wǎng)絡(luò)θ′、α，β超參數(shù)；

2）for episode =1 to M do：

3）? ? 初始化環(huán)境，得到初始狀態(tài)St；

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

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

6）? ? ? ? 執(zhí)行動作At，觀察獎勵Rt和下一個狀態(tài)St+1；

7）? ? ? ? 計算時序誤差，存儲經(jīng)驗到經(jīng)驗池D；

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

9）? ? ? ? 當(dāng)經(jīng)驗池D中的樣本大于某個閾值，從中刪除優(yōu)先級最低的樣本；

10）? ? ? ?從經(jīng)驗池D中隨機采樣N個樣本進行訓(xùn)練；

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

12）? ? ? ? ? ?if St+1是終止?fàn)顟B(tài)，則Q_target=Rt；

13）? ? ? ? ? ?else 用目標(biāo)Q網(wǎng)絡(luò)計算Q_target = Rt + γ max Q′（St， At， θ′ ）；

14）? ? ? ?使用反向傳播算法更新神經(jīng)網(wǎng)絡(luò)參數(shù)θ；

15）? ? ? ? ? 計算當(dāng)前狀態(tài)下執(zhí)行At的Q值Q（St，At），以及當(dāng)前狀態(tài)下所有行動的Q值；

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

17）? ? ? ? ? 計算Loss函數(shù)；

18）? ? ? ? ? 使用梯度下降算法更新Q值網(wǎng)絡(luò)：θ = θ - λ*θ ? Loss；

19）? ? ? ? ? 每隔F步更新目標(biāo)Q網(wǎng)絡(luò)：θ′←θ；

20）? ? ? ?更新狀態(tài)S = St+1；

21）? ? end for

22）end for

3? 仿真

3.1? 仿真參數(shù)設(shè)置

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

3.2? 仿真結(jié)果分析

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

3.2.1? 網(wǎng)絡(luò)平均傳輸時延

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

3.2.2? 丟包率

如圖2所示的仿真結(jié)果表明，本文算法在丟包率上當(dāng)鏈路狀態(tài)到達擁塞時，將會將數(shù)據(jù)轉(zhuǎn)發(fā)到次優(yōu)鏈路，有效地降低了丟包率。

3.2.3? 吞吐量

吞吐量是對衛(wèi)星網(wǎng)絡(luò)中路由算法在一定時間內(nèi)的數(shù)據(jù)傳輸總?cè)萘康暮饬繕?biāo)準(zhǔn)。系統(tǒng)仿真結(jié)果如圖3所示。

由仿真結(jié)果可知，隨著數(shù)據(jù)傳輸?shù)乃俾实脑龃螅到y(tǒng)吞吐量也在提升。由于獎勵函數(shù)的設(shè)置，使得數(shù)據(jù)包會往距離最近，時延最短的方向進行轉(zhuǎn)發(fā)，算法可以快速為衛(wèi)星提供下一跳節(jié)點的選擇，從而使得同樣的時間內(nèi)，衛(wèi)星節(jié)點可以處理更多的任務(wù)，提升系統(tǒng)的吞吐量。

4? 結(jié)? 論

本文針對低軌衛(wèi)星網(wǎng)絡(luò)存在的高動態(tài)性的問題，提出了一種基于深度強化學(xué)習(xí)的衛(wèi)星路由算法，并通過設(shè)置相應(yīng)的參數(shù)以及改進的采樣機制來實現(xiàn)更好的效果。仿真結(jié)果表明，基于優(yōu)先經(jīng)驗采樣機制的深度強化學(xué)習(xí)算法有效降低了數(shù)據(jù)發(fā)送時延，降低了丟包率，提高了系統(tǒng)吞吐量。

參考文獻：

[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] 吳署光，王宏艷，王宇，等.低軌衛(wèi)星網(wǎng)絡(luò)路由技術(shù)研究分析 [J].衛(wèi)星與網(wǎng)絡(luò)，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] 頓聰穎，金鳳林，譚詩翰，等.衛(wèi)星網(wǎng)絡(luò)負載均衡路由技術(shù)研究綜述 [J].信息技術(shù)與網(wǎng)絡(luò)安全，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] 楊思明，單征，丁煜，等.深度強化學(xué)習(xí)研究綜述 [J].計算機工程，2021，47（12）：19-29.

[8] 趙星宇，丁世飛.深度強化學(xué)習(xí)研究綜述 [J].計算機科學(xué)，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—），男，漢族，河北石家莊人，副教授，碩士導(dǎo)師，碩士，主要研究方向：無線自組網(wǎng)、衛(wèi)星通信；彭文鑫（1999—），男，漢族，河北唐山人，碩士在讀，主要研究方向：衛(wèi)星路由；李京陽（1997—），男，漢族，河北滄州人，碩士在讀，主要研究方向：衛(wèi)星路由。