基于強化學習的無人機網絡自適應QoS路由算法

摘 要：由于無人機網絡的動態特性，要保證其具有可靠的通信保障仍存在一定的挑戰，尤其是在軍事領域，對無人機網絡的QoS保障能力要求更高。針對上述需求，提出了一種基于Q學習的自適應QoS路由算法。在該算法中，每個節點通過HELLO消息和數據包相結合的方式來進行鄰居信息感知，通過接收鄰居節點反饋的ACK來獲取鏈路時延和丟包率，然后根據鏈路時延和丟包率來更新維護Q表。考慮節點移動特性，算法還引入了節點的位置信息。在路由過程中，節點綜合考慮Q表和鄰居節點的位置信息來進行最優下一跳選擇。通過仿真驗證，對比參考的路由算法，提出的路由算法能夠在較低的路由開銷下提供更低的傳輸時延和更高的傳輸成功率。

關鍵詞：無人機網絡；強化學習；路由算法

中圖分類號：TP393"" 文獻標志碼：A

文章編號：1001-3695（2025）04-028-1177-08

doi： 10.19734/j.issn.1001-3695.2024.08.0318

Adaptive QoS routing algorithm of UAV network based on reinforcement learning

Tan Zhouzheng1，2， Fan Lang1， Li Yufeng1， Zhang Xiaoning1

（1. School of Information amp; Communication Engineering， University of Electronic Science amp; Technology of China， Chengdu 611731， China;2. State Key Laboratory of Astronautic Dynamics，Xi’an 710043，China）

Abstract：Due to the dynamic nature of UAV network， there are still certain challenges in ensuring reliable communication support， especially in the military field， which requires higher QoS guarantee capability of UAV network. Aiming at the above requirements， this paper proposed an adaptive QoS routing algorithm based on Q-learning. In this algorithm， each node detected neighbor information through the combination of HELLO messages and data packets， received ACK feedback from neighbor nodes to obtain the link delay and packet loss rate， and then updated and maintained the Q table based on the link delay and packet loss rate. Considering the mobility characteristics of nodes， this algorithm also introduced the location information of nodes. During the routing process， the node comprehensively considered the Q table and the location information of neighbor nodes to select the optimal next hop. Through simulation verification， the proposed routing algorithm can provide lower transmission delay and higher transmission success rate under lower routing cost compared with the reference routing algorithms.

Key words：unmanned aerial vehicle （UAV） network; reinforcement learning; routing algorithm

0 引言

無人駕駛飛行器（UAV）也被稱為無人機[1]，其具有部署方便快速、可擴展、靈活、自組織能力強、經濟高效、機動性強等特點。近年來，隨著無人機在通信能力、載荷能力、機動能力等方面的提升，其在軍事領域和民用領域已得到了廣泛的應用[2，3]。最初，無人機是單個獨立使用的，但是由于單個無人機存在通信范圍有限、功能單一等弊端，無法完成較為復雜的任務。與單一無人機系統相比，多無人機系統可以更有效、更經濟地協同完成任務。因此由無人機組成的飛行自組織網絡近年來得到了深入研究。

盡管無人機網絡在各領域中已廣泛使用，但如何保證無人機網絡提供可靠穩定的通信服務仍是一個具有挑戰的問題。無人機自組網（也被稱為飛行自組織網絡）可以看作是移動自組網（MANET）和車載自組網（VANET）的一種特殊形式[4]。它具有這些網絡共同特性的同時，還存在著一些獨特的挑戰。在無人機網絡中，每個節點的遷移程度遠遠高于VANET和MANET。無人機的速度為30～460 km/h[5]。換句話說，無人機的位置是時刻變化的，無人機之間的聯系是間歇性地建立和破壞的。由于更高的可移動性，無人機網絡拓撲結構的變化也比MANET和VANET拓撲結構更頻繁。頻繁的拓撲變化也增加了網絡的時延、丟包和控制信令開銷。另外，無人機網絡的工作環境較為復雜，尤其是在軍事應用領域，無人機往往面臨著干擾和被摧毀等威脅，這同樣會對網絡通信造成影響。無人機網絡的這些特性對路由協議的性能提出了更高的要求。

目前應用于無人機網絡的路由協議大多是對移動自組網路由協議的改進，無線自組網路由協議可分為主動路由、被動路由和混合路由。

主動路由協議也被稱為表驅動路由協議，因為它們傾向于以表的形式存儲更新路由信息。主動路由協議的著名例子包括目的地序列距離向量（destination-sequence distance vector， DSDV）[6]和優化鏈路狀態路由協議（optimized link state routing protocol， OLSR）[7]。每個節點以表格的形式維護和存儲網絡拓撲信息，以便維護一致的網絡視圖。運行主動路由協議的節點之間需要不時地交換最新路由信息表。每當節點需要傳輸數據包時，它首先從維護的表中提取路由信息，并使用該表進行路由。因此，路由發現過程所需的時間更少，從而減少了源節點和目的節點之間數據傳輸的端到端延遲。為適應無人機網絡特點，人們又提出了一些改進的主動路由協議，如文獻[8]提出DT-OLSR，該協議根據節點位置和移動特性動態調整HELLO消息發送頻率，提升了協議的動態適應性。文獻[9]提出了一種先進的快速恢復OLSR（AFR-OLSR）協議，該協議通過定義新的鏈路狀態和使用懲罰函數來改進路由計算規則，在無人機群中節點突然離線或高速移動的情況下，AFR-OLSR可以保持較高的數據包傳送率，并且幾乎不會帶來額外的網絡延遲。文獻[10]提出的MCNA-OLSR選取節點的剩余能量、節點連接時間和緩沖區占用來優化MPR節點的選擇，從而實現在相應場景下降低時延和丟包率。但是，主動式路由在路由發現和維護過程中，其大量交換路由信息和路由請求報文導致整個網絡的控制開銷很高。

被動路由協議也被稱為按需路由協議，因為它們在路由選擇過程中采用按需方式。被動路由協議的一些很好的例子是動態源路由協議（dynamic source routing， DSR）[11]和無線自組網按需平面距離向量路由協議（Ad hoc on-demand distance vector routing，AODV）[12]。運行被動路由協議的節點不需要維護任何先前的路由信息，只在需要通信時交換網絡的路由信息。被動路由協議的源節點簡單地按需發現路由以建立到目的節點的連接。因此，維護網絡拓撲信息產生的控制報文開銷很少。同樣，被動路由協議也有很多改進協議。如文獻[13]引入蟻群算法的思想，設計了一種改進的AODV協議。它提供了多種可選路由，降低了泛洪概率，并且可以保護低功耗節點。文獻[14]提出了一種加權聚類AODV（WBC-AODV），在該路由協議下，簇頭節點可以有效地管理成員節點的路由建立，從而減少路由泛洪過程中控制數據包的重復轉發，降低數據包沖突的概率，提高網絡的分組傳輸率。但是被動路由協議在路由發現過程中，所有節點相互交換拓撲信息，這往往會導致網絡中數據包的泛濫。并且被動協議需要一定的時間來收集和分析網絡拓撲信息，這一過程往往會延長源節點和目的節點之間數據傳輸的端到端延遲。

混合路由需要在主動路由和被動路由之間進行權衡。它結合了主動路由低延遲和被動路由低開銷的優點。在混合路由協議中，網絡被劃分為不同的區域，在區域內和區域間分別使用主動協議和被動協議進行路由。混合路由協議的例子主要包括區域路由協議（zone routing protocol，ZRP） [15]和臨時有序路由算法（temporally ordered routing algorithm，TORA） [16]。

復雜的飛行環境和多樣化的飛行任務使無人機網絡處于不可預測的隨機波動狀態，傳統的路由協議難以實時適應網絡的變化，會導致網絡性能的降低。強化學習是一種自適應學習方法，屬于機器學習范疇。使用強化學習來解決無人機網絡路由問題是一個有效的途徑。文獻[17]首次使用強化學習來解決靜態網絡中的路由問題。基于Q學習提出了一種自適應的Q-routing算法。文獻[18]對Q-routing進行了擴展，提出了一種針對無線傳感器網絡的能量均衡路由算法。目前，基于Q學習的Ad hoc網絡路由協議正在逐漸興起。文獻[19]提出了一種新的基于Q學習的多目標優化路由協議（QMR），將鏈路時延和節點剩余能量作為獎勵，為飛行自組網提供低時延、低能耗的服務保障。文獻[20]提出了DeepCQ+路由協議，該協議將新興的多智能體深度強化學習（MADRL）技術集成到現有的基于Q學習的路由協議及其變體中，通過引入Q、C兩個值來分別表征路由跳數和鏈路質量，采用基于近端策略優化（proximal policy optimization， PPO）的路由轉發機制來決定是否進行網絡探索，在廣泛的拓撲和移動性配置中實現了更高的性能。文獻[21]提出了一種基于Q學習的拓撲感知彈性路由策略（TARRAQ），以低開銷準確捕獲拓撲變化，并以分布式和自治的方式做出路由決策。文獻[22]提出了一種基于Q學習的自適應地理路由協議（QFAGR），該協議綜合考慮了時延、節點機動性和能耗對路由的影響，通過感知局部拓撲變化自適應調整強化學習參數和HELLO報文間隔，同時提出了一種新的路由洞規避機制，實現了吞吐量的提升和延遲的降低。文獻[23]提出了一種基于雙向Q學習的多目標優化路由協議（BQMR），以解決多目標FANET中網絡負載增加和路由復雜度提高等問題。在BQMR中，將鄰居節點的負載占用引入獎勵函數，以增加在更高網絡負載下對網絡擁塞的抵抗力，通過雙向Q值更新機制加速網絡對拓撲變化的感知，從而提升數據包傳輸率和吞吐量，降低網絡時延。

從上面的分析可以看出，無人機網絡的應用雖然越來越廣泛，但在無人機網絡中采用怎樣的路由協議來保證數據的可靠通信仍是一大難點，尤其是在軍事領域，無人機網絡的高動態特性和高QoS需求更是對無人機網絡路由協議提出了更高的挑戰。傳統的路由協議對網絡的動態變化反應不敏感且缺乏對QoS指標的考量，已無法滿足需求，而基于Q學習的路由算法能夠通過與網絡的實時交互及時感知網絡狀態的變化，從而做出路由調整，因此能夠較好地適應無人機網絡的動態特性。但是現有的Q學習路由算法往往存在對QoS度量考慮不充分的問題，單純地對鏈路時延和丟包率等QoS指標進行累積得到的往往只是局部最優解。因此為解決上述問題，本文針對無人機網絡特性以及現有算法的不足，提出了一種基于Q學習的QoS路由算法（Q-learning based QoS-aware routing，QBQR）。無人機通過HELLO消息感知鏈路狀態（包括時延和丟包率）和鄰居節點的移動特性。針對不同QoS指標的特性（如時延為可加性度量，丟包率為可乘性度量），設計專門的懲罰函數，使無人機更準確地感知網絡狀態，同時引入節點間距離進一步約束路由選擇，從而優化無人機路由決策，實現業務的可靠傳輸。對比傳統的移動自組織網絡路由協議，所提出的路由算法能夠提供更好的QoS保障。

1 Q學習原理

Q學習是強化學習領域中應用最廣泛的算法之一。該算法主要包含環境（environment）、代理（agent）、狀態空間（S）、動作空間（A）和獎勵（R）等要素。Q學習的基本思想是通過代理與環境的不斷交互，來學習環境特征，從而得到最優策略。在Q學習算法中，代理在每個狀態下的每個動作都有一個對應的Q值表示最大累積獎勵。代理與環境的交互過程如圖1所示。在時刻t，處于狀態st（st∈S）的代理根據當前策略采取一個動作at（at∈A）后，從環境中獲得獎勵rt（rt∈R），根據獎勵更新對應Q值，然后進入到下一個狀態st+1。Q值的基本迭代公式如下所示。

Q（st，at）=Q（st，at）+α（rt+1+γmaxaQ（st+1，a）－Q（st，at））

（1）

其中：α是學習率，γ是折現因子，它們設置在0到1之間。未來Q值期望（maxaQ（st+1，a）），是代理在下一個狀態st+1選擇可能動作a時的最大Q值。Q學習算法通過建立一張二維的Q表來存儲狀態-動作對以及對應的Q值。智能體在給定狀態下，總是根據Q表按照一定的策略（例如：ε-greedy）進行動作選取。因此，Q學習算法也被稱作表查找法。Q學習適用于狀態和動作都是離散且有限的情況。對于連續狀態和動作或者狀態和動作集過大的情況，Q學習算法不能很好地適應。

2 QBQR算法設計

2.1 路由過程建模

在無人機網絡中，路由的過程是一個數據包來自一個源節點，并通過多跳通信定向到目的節點。路由的目的是確定可以將數據包從源節點傳輸到目的地的適當路徑，該路徑由許多單跳決策組成。它涉及到在缺乏整個網絡信息的情況下，從有限的鄰居中選擇最佳中繼的概率。這正是Q學習的核心思想，即在沒有關于動作對環境影響的先驗知識的情況下，為有限的馬爾可夫決策過程找到最佳的動作選擇策略。因此，路由過程可以用馬爾可夫決策過程建模，用Q學習算法求解。具體如下：

將整個骨干網絡視為一個環境，每個網關節點均視為代理。代理的每一種狀態由數據包所在網關和數據包的目的網關決定。例如，在時刻t，網關節點i要轉發的數據包的目的地為d，則對應代理的狀態st可表示為si，d。動作就是將數據包轉發至下一跳。動作at則可用ai，j來表示，即節點i在時刻t將數據包轉發到相鄰節點j。通過該動作，代理的狀態從si，d移動到sj，d，并收到關于該動作的獎勵。代理在狀態si，d時的動作空間為節點i的所有鄰居節點。用Q（si，d，ai，j）表示在狀態si，d，選擇動作ai，j時的Q值。需要注意的是，當不同數據包位于節點i時，如果數據包的目的節點不同，其對應的Q值也不同。每個網關節點都維護著一張Q表，用于存儲采用不同動作轉發不同目的地的數據包對應的Q值。以節點i為例，其維護的Q表如表1所示。表中，n為網絡中節點數量，k為節點i的鄰居數量。當節點i產生或收到需轉發的數據包時，會根據數據包的目的地確定當前狀態，然后再根據Q表選擇下一跳節點進行數據轉發。數據包轉發后獲取相應反饋，然后按照Q值更新公式更新Q表。一個數據包從源節點傳輸至目的節點，或者超過指定跳數未到達目的節點而被丟棄即為一個回合。

2.2 QBQR算法總體框架

本文針對無人機網絡特點，考慮網絡運行時的QoS需求，提出一種基于Q學習的QoS路由算法。QBQR算法的總體框架如圖2所示。主要包含鄰居發現及維護、鏈路狀態感知、Q學習、路由決策等部分。

鄰居發現及維護主要用于探測各節點的鄰居節點，為代理在特定狀態下提供動作空間（即數據包可選擇的所有下一跳節點集合），同時獲取鄰居節點位置和移動速度。鏈路狀態感知主要是完成鏈路時延和丟包率的測量，同時獲取下一跳節點的最優Q值。Q學習主要是完成Q表的維護和更新。路由決策主要是根據Q表和相應策略進行下一跳選擇。本章后續將對上述內容進行詳細介紹。

2.2.1 鄰居發現及維護

無人機網絡中每個節點周期性向鄰居節點廣播HELLO消息，用HI表示HELLO消息發送間隔。HELLO消息中包含了節點的地理位置、移動速度等信息。節點通過接收到的HELLO消息來建立和維護鄰居表。鄰居表里存儲了各鄰居節點的地理位置、移動速度等重要信息。如果超過時間T未收到某鄰居節點的HELLO消息，則該鄰居將被從鄰居表中刪除。本文中的T取3倍HELLO消息的時間間隔。考慮到網絡開銷，HELLO消息發送的頻率不能過于頻繁。但是在動態的網絡中，HELLO消息間隔過大，往往會導致鄰居信息更新不及時，在數據轉發時就會出現大量丟包的情況。基于此，本文將數據包和HELLO消息結合使用來進行鄰居節點維護。當節點向鄰居節點轉發數據包時，收到數據包的節點會向上一跳節點回復ACK。當節點連續向鄰居節點發送超過3個數據包均未收到ACK時，則將該鄰居從鄰居表中刪除。這樣，當數據包轉發頻率較高時，可以在不增加網絡開銷的同時使節點更快地發現鏈路失效，并進行路由切換，提升路由的動態適應性。

2.2.2 鏈路狀態感知

本文在設計路由算法時，重點將時延和丟包率兩項QoS指標作為優化目標，因此需要對鏈路時延和丟包率進行測量。鏈路時延和丟包率均在數據包轉發過程中獲取，具體過程如下。

a）鏈路時延測量。當節點B在t1時刻收到節點A轉發的數據包時，節點B會將該時刻記錄下來。然后節點B向節點A回復ACK，在ACK消息中攜帶收到對應數據包的時刻t1。節點A收到節點B回復的ACK，記錄接收時刻t2，并讀取ACK中的時刻t1。節點A就可以通過計算t1到t2的時間差得到一個時延，記為delayA，B。

delayA，B=t2－t1

（2）

為避免單次測量帶來較大的抖動，可令節點A記錄最近n次測量的時延，然后將這些時延的均值作為最終測得的時延，記為DelayA，B。如式（3）所示。其中，delayA，B表示最近n次測量的時延中的第i個測量值。本文中n取值為3。

DelayA，B=∑ni=1delayA，B（i）

（3）

從上述過程可以看出，節點A所測得的時延實際上是節點B收到節點A發來的數據包到節點A收到節點B回復的ACK所經歷的時延，而不是節點A向B發送數據包的時延。該時延能夠有效反映節點B在收到A發來的數據包后進行轉發的速度。

b）鏈路丟包率測量。給定一個時間窗口W，節點A記錄在時間窗口W內向節點B發送包的數量nt，這里的包包含所有控制報文和數據包。本文中所有的包在被某個節點發送或轉發時都會攜帶上發送或被轉發的時間ts。節點B根據收到包的發送時間ts持續統計從節點A接收的發送時間大于等于時刻ts－W的包的數量nr。當節點A向B轉發數據包時，在數據包里攜帶上當前窗口對應的發包數量nt。當節點B收到數據包后，通過記錄的nr和數據包里攜帶的nt來計算節點A到B的丟包率，如式（4）所示。節點B計算得到pdrA，B過后，通過ACK反饋給節點A。這樣，節點A收到B回復的ACK后就能夠獲知其到節點B之間的鏈路丟包率。

pdrA，B=nt－nrnt

（4）

2.3 QBQR中的Q學習

在傳統的Q學習算法中，代理每采取一個動作，便會從環境中獲得相應的獎勵，算法的目標是獲取最大累積獎勵，即最大Q值。Q值越大表示對應的動作越優。而本文提出的QBQR算法將Q學習中獎勵函數改成懲罰函數，目標是獲得最小累積懲罰，即最小Q值。Q值越小表示對應的動作越優。考慮無人機網絡在運行時的高QoS需求，本文將前文所述的鏈路時延和丟包率引入到懲罰函數的設計當中。懲罰函數和Q值更新函數分別如式（5）和（6）所示。

fP（st，at）=pmaxpdri，jgt;pdrmaxω（Delayi，jDelaymax）+1－ωlg（1－pdri，j）lg（1－pdrmax）otherwise

（5）

Q（st，at）=fP（st，at）+minaQ（st+1，a）

（6）

其中：i表示在狀態st時數據包所在的節點；j表示動作at選擇的下一跳節點；Delayi，j表示節點i向節點j轉發數據包時測量得到的鏈路時延。特別地，當節點j為目的節點時，令Delayi，j=0，因為Delayi，j反映的是節點j收到節點i發來的數據包后進行轉發的速度，而當節點j為目的節點時，節點j不需要再對數據包進行轉發。Delaymax為最大鏈路時延，由節點的最大隊列長度和最大傳播距離決定；pdri，j表示節點i到j的丟包率；pdrmax表示業務允許的最大丟包率。因此，當節點i到j的丟包率大于業務允許的最大丟包率時，動作at將獲得最大懲罰。其他情況下，動作at獲得的懲罰將由鏈路時延和丟包率決定，時延和丟包率越小，得到的懲罰就越小。ω為時延和丟包率的權重參數（0≤ω≤1）。合理調整ω的值可以使路由的性能在兩者之間取得較好的平衡。為了統一度量，本文利用Delaymax和pdrmax對時延和丟包率進行了歸一化處理。

在QBQR中，節點將所有鄰居節點對應的Q值的初始值設置為一個很大的值，記為Qinitial。當節點j收到節點i發來的一個目的地為d數據包時，節點j便會向節點i回復一個ACK。ACK中攜帶了節點j轉發該數據包時Q表中的最小Q值，minaQ（sj，d，a）。如果節點j即為目的節點d，則ACK中回復的Q值為0。這樣，節點i便能利用該Q值和得到的懲罰來更新對應動作的Q值Q（si，d，ai，j）。當節點發送的數據包足夠多時，節點能夠對鄰居節點實現遍歷，所有鄰居的Q值便會收斂到一個最小的值，節點通過選擇Q值最小的鄰居進行數據轉發，便能得到最優路徑。可以看出在QBQR中，算法的收斂速度取決于網絡的規模和網絡的拓撲結構，網絡規模越大，節點的鄰居越多，算法的狀態空間和動作空間就越大，算法要收斂就需要進行更多的探索，因此復雜度也會相應增加。由于在無人機網絡中，節點的數量比較有限，所以QBQR算法能夠較好應對。在本文中由于懲罰函數為每條鏈路的時延和丟包率的加權值，而一條路徑在時延和丟包率上的表現實際上就是路徑上每條鏈路懲罰之和，所以為準確反映每條路徑在時延和丟包率上的表現，本文將γ取值設為1。學習率α決定節點對網絡狀態變化學習的快慢，在傳統的Q學習中，α取值通常小于1，這是為了避免Q值的隨機誤差和不規則波動。但是在本文的懲罰函數中的時延為多次測量的平均時延，丟包率也是通過滑動窗口得到，它們均進行了平滑處理，因此Q值的變化實際上反映的就是路徑質量的變化趨勢。為保證節點及時感知網絡變化并對路由策略進行調整，本文將α取值也設為1。

2.4 路由決策

在QBQR中，理論上最小Q值對應的下一跳即為最優動作。但是在數據轉發初期，代理與環境交互不夠充分，得出的Q值無法真實反映網絡狀況。另外由于無人機網絡的動態特性，選擇Q值最小的動作也不一定是最優解。而且如果代理始終利用Q值最小的動作，這樣就會導致可能的其他更優動作不能被發現。所以在傳統的Q學習算法中，通常采用ε-greedy策略來平衡探索和利用。

在傳統的ε-greedy策略中，ε通常取一個很小的值，當節點進行路由決策時，總是以1-ε的概率選擇Q值最小的鄰節點轉發數據，以ε的概率隨機選取鄰節點轉發數據。這樣就能使代理在利用最小Q值的同時，有一定的概率探索其他動作。但是由于ε是一個很小的固定值，在算法運行初期或網絡頻繁變化時，往往會出現探索力度不夠，導致算法收斂慢的問題。而當網絡較為穩定時，又會出現對學習結果利用不充分的問題。基于此，本文在QBQR中對傳統的ε-greedy策略進行了改進，將ε設置成一個可變的參數，ε的表達式如式（7）所示。

ε=0.3maxaQ（st，a）≥Qinitial amp; cnlt;0.3cnotherwise

（7）

其中：maxaQ（st，a）為代理在狀態st時所有動作對應的最大Q值；c∈（0，1），為一個可調參數；n為源節點持續向同一目的節點發送數據包的總數量（包含自己產生的數據包和轉發其它節點的數據包），當源節點超過一定時間未向該目的節點發送數據包時，n將被重置。源節點在發送數據包時會攜帶該值，以供后續節點計算ε的值。通過分析Q學習的過程可知，在源節點向目的節點發數據包的數量過少或有新的鄰居節點加入的時候，就會出現maxaQ（St，a）≥Qinitial的情況，這表明節點對網絡探索不夠充分。因此，在這種情況下令ε不小于0.3，保證節點采取較大探索力度，有利于路由的快速收斂和對新加入動作的快速學習。其他情況下ε會隨著發包數量的增加而不斷減小，這也更符合Q學習特性，當節點對網絡探索到一定程度的時候，再做過多的探索就會導致對學習結果利用不充分的情況，影響路由性能。c值可用于調整節點的探索力度，c值越大，ε為較大值的時間就越長，探索的力度就越大。因此，可根據網絡規模的大小對c值進行適當調整，通常網絡規模越大，需要探索的時間越長，c值就應取得越大。

考慮到無人機網絡的動態特性，無人機節點的鄰居表往往存在更新不及時的問題，在節點進行路由決策的時候，有的鄰居節點可能已經飛出了節點的通信范圍Rmax，如果選擇飛出通信范圍內的節點作為下一跳的話，就會導致數據包的丟失。為避免這樣的情況，本文在路由決策的時候引入了節點間距離作為約束。假設節點移動速度在短時間內是固定的，當節點i在t2時刻進行路由決策時，其所在位置記為（pxi（t2），pyi（t2），pzi（t2）），其最近一次更新鄰居表的時間記為t1。在t1時刻，其獲知的鄰居節點j的位置為（pxj（t1），pyj（t1），pzj（t1）），速度為（vxj（t1），vyj（t1），vzj（t1））。那么在t2時刻，節點i可通過計算估計節點j的位置，如式（8）～（10）所示。

pxj（t2）=vxj（t1）×（t2－t1）+pxj（t1）

（8）

pyj（t2）=vyj（t1）×（t2－t1）+pyj（t1）

（9）

pzj（t2）=vzj（t1）×（t2－t1）+pzj（t1）

（10）

這樣，在t2時刻，節點i和j的距離估計值di，j如式（10）所示。

di，j=［pxj（t2）－pxi（t2）］2+［pyj（t2）－pyi（t2）］2+［pzj（t2）－pzi（t2）］2

（10）

當發現di，jgt;Rmax，節點i就知道節點j離開了自身通信范圍，在路由決策時，不會選擇節點j作為下一跳。

綜上，在QBQR運行過程中，所有節點在進行路由決策時，會以1－ε的概率在估計距離小于等于其通信范圍的鄰居節點間選擇Q值最小的鄰居，以ε的概率在估計距離小于等于其通信范圍的鄰居節點間隨機選取鄰居節點轉發數據。若節點的所有鄰居節點的估計距離均超出了節點的通信范圍，則采用廣播的方式發送數據包。

2.5 算法流程

QBQR運行流程如算法1所示，總共可以分鄰居發現及維護、路由決策以及Q學習三個階段。鄰居發現及維護階段如第2～11行所示。各網關節點通過周期發送和接收HELLO報文來進行鄰居發現。為及時地發現鄰居失效，節點會在超過時間T未收到鄰居發來的HELLO消息或者連續向鄰居節點發送超過3個數據包且未收到ACK時，將該鄰居視為失效。路由決策階段如第12～27行所示。主要是對傳統的ε-greedy策略進行改進，使ε的值隨著網絡狀態變化而變化，更好地平衡了探索與利用的關系。同時結合節點間距離約束，提升路由決策的有效性。Q學習階段如第28～35行所示。網關節點每轉發一個數據包后，會收到下一跳節點回復的ACK，從中可獲得相應的鏈路時延和丟包率，通過鏈路時延和丟包率來計算相應懲罰，從而完成Q表的更新。節點根據Q表便可獲知所有鄰居作為數據轉發的下一跳的優劣。

算法1 QBQR算法

1 輸入：HI， ω， c， W， Delaymax， pdrmax。

2 階段1：鄰居發現及維護

3 if 到了某個節點發送HELLO報文的時間 then

4 節點發送HELLO報文

5 end if

6 if 某個節點收到HELLO報文 then

7 節點讀取報文信息，更新鄰居表

8 end if

9 if 某個節點超過時間T未收到某個鄰居的HELLO消息or向某個鄰居連續發送超過3個數據包未收到ACK then

10 節點將該鄰居從鄰居表中刪除

11 end if

12 階段2：路由決策

13 while 節點有數據需要轉發 do

14" "計算所有鄰居節點所在位置

15" "將處于通信范圍內的鄰居節點作為數據轉發的備選節點

16" "if 備選節點為空 then

17"" "廣播數據包

18" "else

19""" 生成一個隨機數a，a∈（0，1）

20""" 按照式（7）計算ε的值

21""" if alt;ε then

22"""" 在備選節點中隨機選取一個節點進行數據轉發

23""" else

24"""" 選擇備選節點中Q值最小的節點進行數據轉發

25""" end if

26" "end if

27 end while

28 階段3：Q學習

29 if 某個節點有新鄰居加入 then

30 初始化新加入鄰居節點的Q值

31 end if

32 if 某個節點收到下一跳反饋的ACK then

33 通過ACK攜帶的信息，按照式（5）計算懲罰

34 按照式（6）更新Q表

35 end if

3 仿真結果及分析

3.1 仿真環境

本文采用Linux平臺下的NS-3網絡模擬仿真器來對QBQR性能進行仿真驗證。仿真參數設置如表2所示。無人機網絡中共包含36個節點，均勻分布在100 km×100 km區域內。節點采用隨機游走移動模型，MAC層采用TDMA協議。每個節點的通信半徑設置為10 000 m，仿真時長為300 s。

3.2 仿真結果分析

本文主要選取端到端時延、報文投遞率和路由開銷三項指標來對QBQR的性能進行仿真驗證。引入的對比算法為OLSR、AODV以及文獻[20]中提出的DeepCQ+。端到端時延是指數據包從源節點傳輸到目的節點的總時延。報文投遞率是指目的節點成功接收數據包數量與源節點發送數據包數量的比值。路由開銷本文定義為數據傳輸過程中產生的所有路由控制消息的總數據量與成功交付的數據包的總數據量的比值。

3.2.1 平均端到端時延

圖3展示了網絡規模為36個節點時，不同業務分別采用QBQR、OLSR、AODV和DeepCQ+算法得到的平均端到端時延。共選取6類業務，每類業務均選取不同的源、目的節點。從圖中可以看出，所有業務使用QBQR算法得到的平均端到端時延均小于使用OLSR、AODV和DeepCQ+算法。其中，6類業務使用QBQR算法的平均端到端時延與OLSR相比平均降低了20.9%，與AODV相比平均降低了18.6%，與DeepCQ+相比平均降低了18.3%。

圖4分別展示了網絡規模為36個節點時，在不同移動模型和不同移動速度下，平均端到端時延的變化情況。可以看出四種算法隨著節點移動速度的增加，平均端到端時延均呈上升趨勢。這是因為隨著節點移動速度的增加，網絡中鏈路頻繁斷裂，從而導致了端到端時延的增加。QBQR算法表現仍為最佳，其平均端到端時延相較于OLSR最多降低了20.4%，相較于AODV最多降低了37.1%，相較于DeepCQ+最多降低了20.1%。

圖5展示了不同節點規模下，四種算法的平均端到端時延。可以看出，隨著節點規模的增加，四種算法的業務平均端到端時延總體呈上升趨勢，這是因為隨著節點數量的增加，節點的時隙周期變長，且業務傳輸路徑跳數可能也有所增加造成的。QBQR在不同節點規模下得到的平均端到端時延始終低于OLSR和AODV，其平均端到端時延相較于OLSR在節點數量為60的時候降低最多達到50.7%，相較于AODV在節點數量為80的時候降低最多達到35.7%，相較于DeepCQ+在節點數量為60的時候降低最多達到35.6%。

綜上，相比于OLSR、AODV和DeepCQ+算法，QBQR算法在平均端到端時延上更具優勢。這是因為OLSR、AODV和DeepCQ+在計算路由時，都是基于“最小跳數”，沒有考慮鏈路時延。鏈路時延往往會受到節點間距離、網絡負載以及節點時隙配置等因素的影響，而OLSR、AODV和DeepCQ+無法有效進行感知，因此得到的路徑的時延往往不是最優的。QBQR在計算路由時引入鏈路時延，能夠找出處從源端到目的地時延最小的路徑，從而降低端到端時延。

3.2.2 報文投遞率

圖6展示了網絡規模為36個節點時，無人網絡中部分節點受到干擾條件下，不同業務分別采用QBQR、OLSR和AODV算法得到的報文投遞率。通常情況下，節點受到干擾會出現一定概率的丟包。因此，本文在網絡中隨機選取了8個節點均以0.1～0.3的隨機概率出現丟包，來模擬節點受到干擾的情況。為避免節點移動性對本次仿真結果的影響，本文將節點的移動速度設置為5 m/s，以保證仿真過程中網絡拓撲的穩定。從仿真結果可以看出，6類業務下QBQR和DeepCQ+算法都取得了較高的報文投遞率，QBQR略高于DeepCQ+。業務1、2、3、4、6使用QBQR算法得到的報文投遞率均高于OLSR、AODV。業務5使用QBQR算法得到的報文投遞率高于AODV，與OLSR算法相當。6類業務使用QBQR算法總的報文投遞率相較于OLSR提升了19.2%，相較于AODV提升了20%，相較于DeepCQ+提升了1.7%。

圖7展示了網絡規模為36個節點時，網絡中不同數量的節點受干擾情況下，6類業務的報文總投遞率變化情況。從圖中可以看出四種算法的報文總投遞率均隨著受干擾節點數量的增加而降低。這是因為網絡中受干擾節點的數量越多，數據包傳輸路徑中受干擾的節點也會增多，從而導致丟包率的增加，降低了報文的投遞率。QBQR算法的報文總投遞率總是優于OLSR、AODV和DeepCQ+。QBQR算法的報文總投遞率與OLSR相比最大提升了12.7%，與AODV相比最大提升了19.7%，與DeepCQ+相比最大提升了5.5%。

綜上所述，可以看出QBQR算法能夠更好地適應干擾環境，在有節點受到干擾時能夠提供更高的報文投遞率。這是因為QBQR算法在數據包的傳輸過程中進行了鏈路丟包率的測量，并將丟包率這一指標引入了懲罰函數的計算過程中。節點在數據轉發過程中能夠及時感知到鄰居節點的丟包情況，從而選擇丟包率更低的鄰居進行數據轉發，避開那些高丟包率的節點。而OLSR和AODV并不能準確感知到鄰居節點的丟包情況，所以得到的數據轉發路徑無法避開受到干擾的節點，從而導致了較高的丟包率。圖6中的業務5使用OLSR得到的報文投遞率之所以與QBQR相當，是因為OLSR計算的轉發路徑中恰好沒有節點受到干擾，但是OLSR無法總是提供這樣的保障。DeepCQ+通過C值反映了鏈路質量，同樣能夠感知到鄰居節點丟包，因此同樣取得了較高的報文投遞率，但是C值的改變是根據節點丟包的變化而變化，對于節點隨機丟包反應不夠靈敏，因此其路由決策有時并不能完全避開受干擾的節點，導致其投遞率低于QBQR。

圖8展示了網絡規模為36個節點時，不同業務在節點快速移動條件下的報文投遞率。本次仿真同樣選取網絡中6類源、目的節點各不相同的業務。此時，網絡中的節點均以20 m/s的速度移動。可以看出，所有業務使用QBQR算法得到的報文投遞率均高于OLSR、AODV和DeepCQ+。其中，6類業務使用QBQR算法得到的報文總投遞率相較于OLSR提升了20.6%，相較于AODV提升了41.7%，相較于OLSR提升了20.6%，相較于DeepCQ+提升了3.5%。

圖9展示了網絡規模為36個節點時，不同移動模型下，業務的報文投遞率隨節點移動速度的變化。可以看到，隨著節點移動速度的增加，業務的報文投遞率呈下降趨勢。這是因為隨著節點移動速度的增加，節點間鏈路中斷頻率也會增加，節點在進行數據轉發時無法及時發現鏈路中斷，導致在轉發數據包時更容易出現丟包。QBQR算法的報文投遞率始終高于OLSR、AODV和DeepCQ+。QBQR算法的報文投遞率相比于OLSR算法最多提升了30%，相比于AODV最多提升了51.8%，相比于DeepCQ+最多提升了7.3%。

圖10展示了不同節點規模下，四種算法的報文投遞率。可以看出，隨著節點規模的增加，四種算法的報文投遞率呈下降趨勢，這是因為隨著節點規模的增加，業務傳輸路徑跳數增加，路徑失效中斷的頻率也隨之增加，導致了丟包率的增加。QBQR算法的報文投遞率始終高于OLSR、AODV和DeepCQ+。在節點數量為100時，QBQR算法的報文投遞率相比于OLSR、AODV和DeepCQ+提升最多，分別達到了37.9%、67.9%和13.7%。

綜上所述，可以看出QBQR算法能夠更好地適應網絡中節點的動態特性，在網絡拓撲結構頻繁變化的情況下，能夠提供更高的報文投遞率。OLSR算法需要感知全網拓撲才能計算路由，但是由于拓撲更新時間較長，得到的路由存在一定滯后，數據包在轉發時，路徑可能已經失效，從而導致大量丟包。AODV雖然不用感知全網拓撲，但是由于其路由有效時間設置較長，無法及時針對網絡拓撲變化做出路由調整，同樣也會導致數據包的大量丟失。DeepCQ+雖然通過C值更夠更快速地感知網絡變化，但是其路由策略調整的效率仍低于QBQR。QBQR之所以能保持較高的報文投遞率，主要因為：a）當鏈路因為節點移動出現間歇性中斷時，QBQR算法能夠及時獲取鏈路丟包情況，從而避開質量較差的鏈路；b）當鄰居節點離開節點的通信范圍后，節點能夠利用數據轉發時接收ACK的情況，更快地更新鄰居表；c）當節點在進行路由決策時，通過估計鄰居節點的實時位置，來選擇位于自身節點通信范圍內的節點進行數據轉發，避免了數據包的丟失。

3.2.3 路由開銷

圖11展示了不同節點數量下算法的路由開銷。可以看出，隨著節點數量的增加，四種算法的路由開銷均呈上升趨勢。這是因為隨著網絡規模的增大，算法在網絡中需要傳輸更多的控制報文才能完成路由計算。四種算法中，OLSR算法路由開銷最大，AODV算法路由開銷最小，QBQR路由開銷低于OLSR和DeepCQ+，稍大于AODV。

圖12展示了在節點數量為36的網絡中，路由開銷隨節點移動速度變化的情況。可以看出，隨著節點移動速度的增加，四種算法的路由開銷均呈上升趨勢。這是因為節點移動速度越快，網拓撲變化就越頻繁，要完成數據包的交付就需要更多的控制報文來感知網絡變化。同樣，OLSR算法路由開銷最大，AODV算法路由開銷最小，QBQR路由開銷低于OLSR和DeepCQ+，稍大于AODV。

綜上可以看出，QBQR算法在路由開銷上的表現要優于OLSR和DeepCQ+，略差于AODV。這是因為OLSR算法需要定期對全網拓撲進行感知，這需要大量的控制報文，而且隨著節點數量的增加，控制報文增加得越明顯。DeepCQ+引入了廣播機制來進行探索，導致了較高的報文開銷。QBQR只需要感知鄰居信息，不需要感知全網拓撲，因此控制報文得到明顯減少。而AODV只在業務發送的初始階段進行路由發現，因此路由開銷更小。QBQR相較于AODV雖然增加了一定的路由開銷，但是其在平均端到端時延和報文投遞率方面取得了較大的優勢。

3.2.4 探索與利用策略比較

圖13展示了在節點數量為36的網絡中，采用傳統ε-greedy策略和本文改進的ε-greedy策略時，算法的收斂過程。本次仿真Qinitial取100，遠大于收斂后的Q值。在改進的ε-greedy策略中，c值取0.96。可以看到，對于傳統的ε-greedy策略，ε取值越大，算法的收斂速度越快，這是因為ε越大，節點對鄰居節點的探索力度就越大。當ε取0.1時，算法要進行90余次的迭代才能收斂；當ε取0.3時，算法要進行60余次的迭代才能收斂；當ε取0.5時，要進行20余次的迭代才能收斂。對于改進的ε-greedy策略，算法的收斂速度與傳統的ε-greedy策略ε取0.5時相當，同樣只需要進行20余次的迭代便能收斂。算法收斂后，需要對Q值進行充分利用，以保證路由路徑的最佳。傳統的ε-greedy策略通過取較大的ε值，雖然能提升算法收斂速度，但是不利于算法收斂后的利用。改進的ε-greedy策略會隨著迭代次數的增加，逐漸減小探索力度，進而充分利用收斂后的Q值進行下一跳選擇，從而取得更優的路由效果。圖14展示了不同策略下6類業務的平均端到端時延。可以看出，采用改進的ε-greedy策略得到的平均端到端時延優于傳統的ε-greedy策略。傳統的ε-greedy策略在ε取0.1時的平均端到端時延要優于ε取0.3時。改進的ε-greedy策略相較于傳統ε-greedy策略ε取0.1時，6類業務的平均端到端延時平均降低了8.1%；相較于ε取0.3時，平均降低了30.2%。

圖15展示了不同策略下6類業務的報文投遞率。該次仿真，仍在網絡中隨機選擇了8個節點以0.1～0.3的隨機概率出現丟包。同樣可以看到，采用改進的ε-greedy策略得到的報文投遞率優于傳統ε-greedy策略。傳統的ε-greedy策略在ε取0.1時的報文投遞率要優于ε取0.3時。改進的ε-greedy策略相較于傳統ε-greedy策略ε取0.1時，6類業務的報文總投遞率提升了13.3%；相較于ε取0.3時，報文總投遞率提升了19.7%。

4 結束語

本文針對無人機網絡高動態、易受干擾等特點，設計了一種基于Q學習的QoS路由算法。該算法通過引入鏈路時延和丟包率作為路由決策的依據，來提升路由的QoS保障能力。在節點進行鄰居發現和維護過程中，通過將HELLO消息和數據包相結合的方式來提升節點鄰居表更新效率。在路由決策時，通過采用動態ε-greedy策略來優化節點探索和利用過程，同時引入節點間距離作為約束，來提升路由對節點移動的適應能力。最后的仿真結果表明，本文設計的路由算法相較于傳統的OLSR、AODV算法和基于強化學習的DeepCQ+算法，在無人機網絡中能夠在較低的路由開銷下提供更好的時延和傳輸成功率保障。

參考文獻：

[1]

Gupta L， Jain R， Vaszkun G. Survey of important issues in UAV communication networks [J].IEEE Communications Surveys amp; Tutorials，" 2015， 18 （2）： 1123-1152.

[2]Mohsan S A H， Khan M A， Noor F，et al. Towards the unmanned aerial vehicles （UAVs）： a comprehensive review [J]. Drones， 2022， 6 （6）： 147.

[3]韓磊. 無人機集群自組織網絡路由協議研究及優化 [D]. 西安： 西安電子科技大學， 2022. （Han Lei. Research and optimization of UAV cluster ad hoc network routing protocol [D]. Xi’an： Xidian University， 2022. ）

[4]Yang Q， Jang S J， Yoo S J. Q-learning-based fuzzy logic for multi-objective routing algorithm in flying Ad hoc networks [J].Wireless Personal Communications，" 2020， 113 （2）： 115-138.

[5]Li Xianfeng， Yan Jiaojiao. LEPR： Link stability estimation-based preemptive routing protocol for flying Ad hoc networks [C]// Proc of IEEE Symposium on Computers and Communications. Piscataway，NJ：IEEE Press， 2017： 1079-1084.

[6]Zhang Hang， Wang Xi， Memarmoshrefi P，et al. A survey of ant colony optimization based routing protocols for mobile Ad hoc networks [J]. IEEE Access， 2017， 5： 24139-24161.

[7]Plesse T， Adjih C， Minet P，et al. OLSR performance measurement in a military mobile Ad hoc network [J].Ad Hoc Networks，" 2005， 3 （5）： 575-588.

[8]Jiang Yuqing， Mi Zhichao， Wang Hai，et al. Research on OLSR adaptive routing strategy based on dynamic topology of UANET [C]//Proc of the 19th IEEE International Conference on Communication Technology. Piscataway，NJ：IEEE Press， 2019： 1258-1263.

[9]Liu Qingxin， Zhu Xiaojun， Zhou Chuanxinet al. Advanced fast reco-very OLSR protocol for UAV swarms in the presence of topological change [C]// Proc of the 26th International Conference on Computer Supported Cooperative Work in Design. Piscataway，NJ：IEEE Press， 2023： 709-714.

[10]Liu Chao. Multi-Criterion OLSR protocol optimization based on network analysis method [C]//Proc of the 2nd IEEE International Conference on Control， Electronics and Computer Technology. Pisca-taway，NJ：IEEE Press， 2024： 1235-1239.

[11]Taha A， Alsaqour R， Uddin M，et al. Energy efficient multipath routing protocol for mobile Ad-hoc network using the fitness function [J]. IEEE Access， 2017， 5： 10369-10381.

[12]Singh M， Kumar S. A survey： Ad-hoc on-demand distance vector （AODV） protocol [J].International Journal of Computer Applications， 2017， 161 （1）： 38-44.

[13]Xu Jian. A modified AODV routing protocol using in WSN based on ant colony algorithm [C]//Proc of the 2nd International Conference on Electronics， Communications and Information Technology. Pisca-taway，NJ：IEEE Press， 2021： 87-90.

[14]Xie Hanbing， Zou Gui， Ma Lin. A hierarchical routing protocol based on AODV for unmanned aerial vehicle swarm network [C]//Proc of IEEE International Conference on Unmanned Systems. Piscataway，NJ：IEEE Press， 2022： 1113-1117.

[15]Beijar N. Zone routing protocol （ZRP） [EB/OL].（2002-05-08）. https：//www.netlab.tkk.fi/opetus/s38030/k02/Papers/08-Nicklas.pdf.

[16]Weiss E， Hiertz G R， Xu Bangnan. Performance analysis of temporally ordered routing algorithm based on IEEE 802.11a [C]//Proc of the 61st IEEE Vehicular Technology Conference. Piscataway，NJ：IEEE Press， 2005： 2565-2569.

[17]Boyan J， Littman M. Packet routing in dynamically changing networks：a reinforcement learning approach [C]//Proc of International Conference on Neural Information Processing Systems. 1993： 671-678.

[18]Oddi G， Pietrabissa A， Liberati F. Energy balancing in multi-hop wireless sensor networks：an approach based on reinforcement learning [C]// Proc of NASA/ESA Conference on Adaptive Hardware and Systems. Piscataway，NJ：IEEE Press， 2014： 262-269.

[19]Liu Jianmin， Wang Qi， He Chentao，et al. QMR： Q-learning based multi-objective optimization routing protocol for flying Ad hoc networks [J]. Computer Communications， 2019， 150： 304-316.

[20]Kaviani S， Ryu B， Ahmed E，et al. DeepCQ+： robust and scalable routing with multi-agent deep reinforcement learning for highly dyna-mic networks [C]// Proc of MILCOM IEEE Military Communications Conference. Piscataway，NJ：IEEE Press， 2021： 31-36.

[21]Cui Yanpeng， Zhang Qixun， Feng Zhiyong，et al. Topology-aware resilient routing protocol for FANETs： an adaptive Q-learning approach [J].IEEE Internet of Things Journal，" 2022， 9 （19）： 18632-18649.

[22]Wei Chi， Wang Yuanyu， Wang Xiang，et al. QFAGR： a Q-learning based fast adaptive geographic routing protocol for flying Ad hoc networks [C]// Proc of IEEE Global Communications Conference. Piscataway，NJ：IEEE Press， 2023： 4613-4618.

[23]Xue Liang， Tang Jie， Zhang Jiaying，et al. Bidirectional Q-learning based multi-objective optimization routing protocol for multi-destination FANETs [C]//Proc of IEEE International Workshop on Radio Frequency and Antenna Technologies. Piscataway，NJ：IEEE Press， 2024： 421-426.