基于啟發式Q 學習的FANET 可信路由算法

趙蓓英，姬偉峰，翁 江，吳 玄，李映岐

（空軍工程大學 信息與導航學院，西安 710177）

0 概述

近年來，無人機廣泛應用于民用和軍事領域：在民用領域，無人機用于航空攝影、智慧農業、電力巡檢等方面；在軍事領域，無人機用于情報偵查、軍事打擊、電子對抗等任務［1］。單架無人機的載荷與能量有限且覆蓋范圍小，無法完成大規模、高難度的任務，因此，無人機自主集群成為趨勢［2］。無人機自組織網絡（Flying Ad hoc Network，FANET）不依賴固定的基礎設施，通過各無人機節點協同通信，是實現自主集群的關鍵技術［3］。但是，FANET 中節點的高機動性、網絡開放性與拓撲變化頻繁等特點，導致網絡路由面臨性能與安全方面的雙重考驗［4］。

本文提出一種基于啟發式Q 學習的可信路由（Heuristic Q-learning based Trusted Routing，HQTR）算法。將FANET 中的路由選擇問題映射為有限馬爾科夫決策過程，并提出模糊動態信任獎勵機制，針對路由層面的黑洞攻擊與泛洪攻擊，考慮節點的轉發行為與路由請求發送速率，通過模糊推理計算節點的信任值，根據信任值與跳數計算節點的獎勵值。結合單跳鏈路狀況設計啟發式函數，加速最優可信下一跳節點Q 值的更新，引導當前節點選擇最優可信下一跳節點。同時在路由過程中，根據信任值檢測并隔離惡意節點，從而實現安全可靠且高效的數據傳輸。

1 相關工作

在高動態的FANET 中，路由協議應該能夠自適應地感知環境的變化，選擇一個可靠的鄰居節點來完成通信。強化學習是一種以環境反饋為輸入的自適應機器學習算法，智能體可以根據環境反饋來不斷調整行動策略，從而更好地適應動態的網絡環境，因此，強化學習常被用于改進自組織網絡的路由算法，以提高服務質量［5］。

在路由性能優化方面，強化學習算法主要用于優化不同的服務質量參數，如端到端延遲、吞吐量、數據包投遞率、跳數、路由開銷等［6］。文獻［7］提出一種基于Q-learning 的無人機網絡地理路由協議QGeo，該協議采用強化學習算法，根據數據包傳輸速度計算獎勵值，同時根據鄰居節點的距離調整折扣因子，選擇Q 值最高的節點作為下一跳節點。文獻［8］提出一種基于Q-learning 的多目標優化路由協議QMR，其考慮時延與剩余能量設計獎勵函數，根據節點的鄰居關系調整學習率與折扣因子，從而為FANET 提供低延遲、低能耗的通信服務質量。模糊數學能夠很好地處理信息的不確定性與不完整性，同時可以融入人類專業知識，適用于自組織網絡高度動態的網絡環境［9］。文獻［10］提出一種改進的AΟDV 協議PFQ-AΟDV，其利用鏈路帶寬、鏈路質量以及車輛方向、速度變化的模糊推理結果修正Q 值更新函數，在路由發現過程中選擇Q 值最大的鄰居節點作為下一跳節點。文獻［11］提出一種基于模糊Q-learning 的路由算法FQ-AGΟ，該算法考慮可用帶寬、鏈路質量、節點傳輸功率和距離，利用模糊邏輯來評估無線鏈路，采用Q-learning 算法選擇最優的下一跳節點。針對Q-learning 算法效率低的問題，文獻［12-13］引入啟發式函數指導動作的選取，提出啟發式Q-learning。文獻［14］結合節點間的延遲信息來指導節點的轉發行為，設計啟發式函數和評價函數，加快當前最優動作Q 值的更新，減少不必要的探索，從而提高Q-learning 過程的收斂速度以及學習效率。

采用信任模型是確保自組織網絡路由安全性與可靠性的有效措施之一［15］。文獻［16］抽象出一種分布式信任推理模型，采用直接信任度、間接信任度、歷史信任度、鏈路質量等作為信任評估因子，通過模糊層次分析法來確定權重，提出一種輕量級信任增強路由協議TEAΟMDV。文獻［17］將信任機制與Q-learning 算法相結合，根據節點轉發行為確定節點的可信度，并將其作為獎勵值，選擇滿足剩余能量要求的最大Q 值節點，以有效應對槽洞攻擊與黑洞攻擊。文獻［18］針對VANET中的竊聽、干擾和欺騙攻擊，通過信任模型評估節點對VANET 的威脅級別，采用區塊鏈技術防止信息篡改，基于Q-learning 決定是否響應源節點的請求或選擇可靠的中繼節點。針對SDN架構的VANET，文獻［19-20］采用信任模型評估鄰居轉發數據包的行為，以應對惡意節點的丟包攻擊，SDN 控制器作為Agent，通過深度強化學習確定VANET 中最可信的路由路徑。

隨著FANET 的發展，其承載的業務更加復雜繁重，安全威脅層出不窮，對路由算法的性能與安全性都提出了更高的要求。然而，目前大多數算法僅關注性能優化或安全防護，為了有效應對潛在的惡意攻擊，同時優化算法性能并提高服務質量，需要設計實現一種安全、高效且可靠的路由算法。

2 系統模型

2.1 多跳FANET 模型

本文考慮一種多無人機協同作業場景，無人機之間形成自組織網絡，不依賴地面站即可完成機間通信，從而擺脫地面站對無人機群活動范圍的限制，擴大網絡覆蓋區域［21］。如圖1 所示，無人機節點同時充當終端與路由器，鄰居節點直接通信，非鄰居節點可通過其他節點作為中繼節點進行多跳通信。多跳FANET 模型的關鍵在于找到一條最優路徑，能夠在低延遲、低開銷的情況下安全傳輸數據。

圖1 多跳FANET 模型Fig.1 Multi-hop FANET model

2.2 攻擊模型

針對FANET 路由層面存在的攻擊，根據其特征的不同可分為以下3 類：

1）以丟包為特征的攻擊，如黑洞、灰洞、選擇性轉發攻擊。

2）以篡改、偽造報文為特征的攻擊，如槽洞、黑洞、灰洞、蟲洞攻擊。

3）以泛洪為特征的攻擊，如Hello 消息泛洪攻擊、RREQ 消息泛洪攻擊。

本文假設攻擊者具有以下破壞能力：

1）外部攻擊者可以捕獲網絡內部節點，將其轉化為一個惡意節點。

2）內部攻擊者或被轉化的惡意節點可以篡改路由信息，如篡改路由回復報文、欺騙鄰居節點其距離目的節點最近，從而加入轉發路徑，繼而發動黑洞、灰洞等攻擊，丟棄接收到的數據包。

3）內部攻擊者或被轉化的惡意節點不受路由請求發送速率的限制，利用RREQ 泛洪特性不斷廣播虛假的請求報文，淹沒正常請求，占用網絡資源，造成網絡擁塞。

2.3 安全目標

為保證多跳FANET 中無人機節點間的通信安全并協同完成通信任務，本文考慮以下安全目標：

1）檢測與防范黑洞、灰洞等丟包類攻擊與路由請求RREQ 消息泛洪攻擊。

2）通過驗證節點之間的可信度，隔離內部惡意節點。

3）提供從源節點到目的節點的安全數據傳輸，實現高吞吐量和高數據包投遞率，控制網絡開銷，優化平均端到端時延。

3 基于啟發式Q-learning 的可信路由算法

3.1 FANET Q-learning 模型

Q-learning 是基于有限馬爾科夫決策過程的強化學習算法，主要由智能體（Agent）、環境（Environment）、狀態（State）、動作（Action）組成，如圖2 所示［22］。智能體在執行某個動作后，環境將轉換到一個新的狀態并給出獎勵（Reward）信號，隨后智能體根據新的狀態和環境反饋的獎勵，按照一定的策略執行新動作。

圖2 馬爾科夫決策過程Fig.2 Markov decision process

本文將FANET 中的路由選擇問題描述為一個馬爾科夫決策過程，給出如下定義：

1）基本組件。

（1）學習環境：整個FANET 網絡環境，包括無人機節點、通信鏈路等。

（2）智能體：FANET 中每個無人機節點作為學習主體Agent。

（3）狀態空間：本節點以外其余節點構成該節點的狀態空間。

（4）動作空間：動作表示節點在數據傳輸時對下一跳節點的選擇，動作空間為其鄰居節點。

2）獎勵。

將節點對下一跳節點的可信度評估作為獎勵信號，表示節點動作選擇的可靠性。獎勵值函數定義如式（1）所示：

其中：Γ(d)表示目的節點的鄰居節點集，目的節點為當前節點的可信鄰居節點時，獎勵值為1，否則獎勵值為0；Tsx表示當前節點s通過鄰居節點x作為中繼節點傳輸數據的可信程度；h為節點x距離目的節點的跳數?？尚哦仍礁?，跳數越少，獎勵值越高。

3）Q 值更新函數。

Q-learning 的動作值函數更新如式（2）所示：

其中：Qs(d,x)表示當前節點s選擇x作為下一跳到達目的地d的Q 值表示節點x選擇y作為下一跳到達目的地d的Q 值；y為x鄰居節點中Q 值最大的點；α為學習率；γ為折扣因子。每個節點維護一個Q 表，節點將最大Q 值添加到Hello 消息中，通過定期交換Hello 消息來更新Q 值。學習任務分配到每個節點，使算法能夠快速收斂到最優路徑，并依據網絡拓撲的變化進行及時調整。

3.2 模糊動態信任獎勵機制

針對FANET 中的黑洞攻擊與RREQ 泛洪攻擊，本文提出一種模糊動態信任獎勵機制，該機制包括模糊化處理、模糊推理和去模糊化3 個步驟，實時監測節點的數據包轉發率、RREQ 發送速率，周期性地計算節點可信度，并將其作為節點的獎勵值。該機制的具體流程如圖3 所示，其中，數據包轉發率、RREQ 發送速率計算公式如式（3）、式（4）所示，NRDP為節點接收到的數據包個數，NFDP為轉發的數據包個數，τ為信任計算周期，NRREQ為一個周期內節點發送的路由請求報文個數。

圖3 模糊動態信任獎勵機制流程Fig.3 Procedure of fuzzy dynamic trust reward mechanism

本文模糊動態信任獎勵機制各步驟具體如下：

1）模糊化處理。定義數據包轉發率與RREQ 發送速率的模糊隸屬函數如圖4（a）、圖4（b）所示，參考文獻［23］，將數據包轉發率分為3 個等級，RREQ 發送速率分為2 個等級，利用隸屬函數將其轉換成模糊值。

圖4 模糊隸屬函數Fig.4 Fuzzy membership function

2）模糊推理。定義模糊規則庫如表1 所示，根據模糊規則庫進行模糊推理，輸出信任值對應的模糊等級與隸屬度。

表1 模糊規則庫Table 1 Fuzzy rule base

3）去模糊化。定義輸出信任值的隸屬函數如圖4（c）所示，采用隸屬度加權平均法對模糊推理結果進行去模糊化處理，計算方式如式（5）所示。模糊推理輸出一個信任等級，根據該等級的隸屬度函數及隸屬度得到對應的信任值，有2 個點則取平均值。若對應多個信任等級，則分別求出其對應的信任值，再以歸一化后的隸屬度作為權重系數，加權平均得到最終信任值。

3.3 啟發式路由選擇算法

在FANET 環境下，Q 值的更新速度受到Hello 消息發送間隔的限制，間隔過小將加重網絡負載，間隔過大將無法及時感知拓撲變化，導致算法收斂速度變慢。同時，大多數算法根據Q 值采用貪婪策略選擇下一跳，然而高可信度節點可能鏈路狀況較差，并非最佳下一跳節點，這也會增加高可信度節點的負擔。因此，本文提出一種基于啟發式Q 學習的路由選擇算法，通過利用-探索平衡策略，根據單跳延遲與鏈路質量來確定當前最優的可信下一跳節點。啟發式評價函數用于更新當前最優動作的Q 值，若節點x為最優可信下一跳，為其賦予一個適當的啟發值，引導當前節點選擇該節點作為下一跳，以加快收斂速度，提高路由算法的效率。

3.3.1 利用-探索平衡策略

當選擇轉發數據包的鄰居節點時，HQTR 算法不直接選擇Q 值最大的下一跳節點，而采用改進的標準貪婪策略選擇動作，如式（6）所示：

其中：A表示選取的動作，即下一跳節點；Hs(d,x)表示當前最優動作的啟發式函數值；σ∈[0,1]是度量啟發式函數影響程度的實數，本文中取σ=1；P=ε表示算法以一定的概率ε隨機選擇下一跳節點，即智能體在環境中“探索”；P=1-ε表示算法以1-ε概率選擇價值最大的鄰居節點作為下一跳節點，即智能體直接“利用”已經探索得到的信息。

3.3.2 最優動作確定

多跳路由的效率取決于構成該路由的所有直接無線鏈路（即單跳鏈路），因此，為提高通信服務質量，本文考慮單跳節點間的鏈路狀況，包括單跳延遲與鏈路質量，通過衡量單位時間內接收Hello 消息的平均單跳延遲與數量，確定最優可信下一跳。最優可信下一跳定義如式（7）所示，其中：AADelay為平均單跳延遲，計算方式如式（8）、式（9）所示；HHRR為Hello包接收率，計算方式如式（10）所示；TA*為當前節點對下一跳節點的信任值；θ為可信閾值。平均單跳延遲越小，Hello 包接收率越高，表明其與該節點之間的鏈路狀況越好，此節點將被確定為最優可信下一跳。

3.3.3 啟發式函數

當確定最優可信下一跳節點后，啟發式函數Hs(d,x)引導當前節點選擇該節點并更新相應的Q值。啟發式函數定義如式（11）所示，其中，η取0.01。若節點x為最優可信下一跳，為其賦予一個適當的啟發值，否則啟發值為0。Hs(d,x) 的值必須大于Qs(d,x)值之間的變化，以便其可以影響動作選擇，同時為了最小化誤差，Hs(d,x)必須盡可能小。

綜上，將啟發式路由算法主要分為Hello 消息維護、數據傳輸、路由發現、惡意節點隔離4 個部分，描述如算法1 所示，將該算法應用于AΟMDV 協議中，建立多條可信路徑，便于在鏈路中斷、惡意節點破壞時進行路徑切換。

算法1HQTR 算法

本文HQTR 算法的復雜度主要與信任值、Q 值和啟發式函數值的更新相關，三者的時間復雜度與空間復雜度相同，分別為Ο(N)、Ο(N2)、Ο(N2)，因此，算法1 的時間復雜度與空間復雜度均為Ο(N2)。

4 仿真結果與分析

本文采用NS2 模擬器進行仿真實驗，具體參數設置如表2 所示，基于包投遞率、吞吐量、路由開銷、平均端到端時延這4 個性能評價指標，對AΟMDV、TEAΟMDV［16］、ESRQ［17］與HQTR 進行仿真對比，分析惡意攻擊、節點移動速度與網絡規模對算法性能的影響，比較結果如表3 所示。

表2 仿真參數設置Table 2 Simulation parameters setting

表3 算法性能比較結果Table 3 Algorithms performance comparison results

4.1 惡意攻擊下的算法性能評估

設置節點最大移動速度為10 m/s，黑洞攻擊中設置6 個惡意節點，泛洪攻擊中設置1 個惡意節點，2 種攻擊并存時設置3 個惡意節點，仿真結果如圖5所示。

由圖5（a）可知，在未受到攻擊時，包投遞率都保持在90%以上，TEAΟMDV 與HQTR 選擇了鏈路質量較高的下一跳節點，ESRQ 考慮距離因素，包投遞率略高于AΟMDV。當受到黑洞攻擊時，AΟMDV 包投遞率有所下降，而TEAΟMDV、ESRQ 與HQTR 隔離了惡意節點，包投遞率下降幅度較小。當存在泛洪攻擊節點時，大量的RREQ 消息被不斷地轉發，占用了有效帶寬，導致數據包得不到及時處理而被丟棄，AΟMDV、TEAΟMDV 與ESRQ 包投遞率下降，而HQTR 丟棄了來自惡意節點的路由請求，包投遞率下降幅度較小，降低了泛洪攻擊對網絡的影響。當惡意節點同時發動2種攻擊時，TEAΟMDV 與ESRQ 雖然能夠檢測出黑洞攻擊，但惡意節點的請求仍然能夠被發送與轉發，而HQTR可以同時應對2 種攻擊，包投遞率更高。

由圖5（b）可知，AΟMDV 由于受到惡意節點的攻擊，丟包狀況嚴重，網絡吞吐量下降，TEAΟMDV與ESRQ 在一定程度上防御了黑洞攻擊，提升了吞吐量，但無法應對泛洪攻擊，當存在泛洪攻擊時，兩者的吞吐量較低，HQTR 能夠有效應對黑洞攻擊與泛洪攻擊，吞吐量始終保持較高水平。

由圖5（c）可知，在未受到攻擊時，HQTR 與AΟMDV、ESRQ 路由開銷相近，而TEAΟMDV 略高，表明在正常情況下HQTR 未引入冗余開銷。當受到黑洞攻擊時，隔離惡意節點需要路徑切換或重新建立新路徑，HQTR 的路由開銷相比TEAΟMDV 與ESRQ 更低，選擇的路徑更加安全可靠。當受到泛洪攻擊時，惡意節點不斷發送請求報文，同時這些報文也被其他節點轉發，導致路由開銷大幅上升。HQTR 將不再接受惡意節點的請求，抑制了RREQ的傳播，控制了路由開銷，但不能阻止惡意節點發送RREQ，因此，其路由開銷相比正常情況高。當惡意節點同時發動2 種攻擊時，TEAΟMDV 與ESRQ 中部分節點由于檢測出黑洞攻擊而隔離了惡意節點，降低了路由開銷，但惡意節點的請求仍能被其他節點接收并轉發，因此，TEAΟMDV 與ESRQ 的路由開銷高于HQTR。同時，TEAΟMDV 需要發送額外的控制包用于信任推薦，其路由開銷較ESRQ 更高。

由圖5（d）可知，在未受到攻擊時，HQTR 平均端到端時延較低，當受到黑洞攻擊時，平均端到端時延均有所上升，TEAΟMDV 略高，TEAΟMDV 將惡意節點從路徑中剔除后，需重新選擇可信路由路徑，可能會增加跳數，從而導致時延增大。ESRQ 優先選取距離較近的下一跳，平均端到端時延低于TEAΟMDV。HQTR在選擇下一跳時考慮跳數、單跳延遲與鏈路質量，優化了時延。當存在泛洪攻擊時，由于網絡中充斥大量請求報文，產生擁塞，時延明顯上升，HQTR緩解了網絡擁塞，其時延相比TEAΟMDV 與ESRQ更低。

圖5 惡意攻擊下的算法性能比較Fig.5 Performance comparison of algorithms under malicious attacks

4.2 不同節點移動速度下的算法性能評估

設置3 個惡意節點，同時進行黑洞攻擊與泛洪攻擊，仿真結果如圖6 所示。由圖6 可知，隨著節點移動速度的提升，鏈路中斷頻繁，丟包狀況嚴重，包投遞率與吞吐量均不斷下降，同時需要發送更多的控制包用于路由發現與維護，路由開銷與平均端到端時延有所上升。ESRQ 僅考慮了距離因素，而節點移動速度過大時，鏈路質量不穩定，因此，其包投遞率與吞吐量較低，路由開銷與平均端到端時延也逼近TEAΟMDV。HQTR 避免了存在惡意節點以及丟包嚴重節點的路徑，通信鏈路較為穩定，相比TEAΟMDV 與ESRQ，其包投遞率與吞吐量下降緩慢，始終保持較高水平，同時降低了路由開銷與平均端到端時延。

圖6 不同節點移動速度下的算法性能比較Fig.6 Performance comparison of algorithms under different node moving speeds

4.3 不同網絡規模下的算法性能評估

設置節點最大移動速度為10 m/s，3個惡意節點同時進行黑洞攻擊與泛洪攻擊，仿真結果如圖7所示。由圖7可知，在相同的飛行范圍內，當網絡中節點數量較少時，數據包轉發跳數較多，由于無線鏈路的不穩定性，導致數據包投遞率與吞吐量略低。隨著網絡規模的擴大，惡意節點造成的破壞更加嚴重，導致數據包投遞率與吞吐量不斷下降，路由開銷與平均端到端時延不斷上升。HQTR能夠有效抵御惡意節點的黑洞攻擊與泛洪攻擊，其相比AΟMDV、TEAΟMDV與ESRQ性能更優且穩定。

圖7 不同網絡規模下的算法性能比較Fig.7 Performance comparison of algorithms under different network sizes

5 結束語

本文提出一種基于啟發式Q 學習的可信路由算法HQTR，該算法考慮黑洞攻擊、RREQ 泛洪攻擊的主要攻擊特征，檢測與隔離惡意節點，建立多條可信路徑，采用啟發式Q 學習引導當前節點選擇鏈路狀況最佳的可信下一跳節點。仿真結果表明，HQTR 能夠有效應對黑洞攻擊與RREQ 泛洪攻擊，在不增加路由開銷的情況下可以降低網絡拓撲頻繁變更與網絡規模變化所帶來的影響，提高數據包投遞率與吞吐量，優化平均端到端時延。下一步將運用深度學習方法對FANET 中存在的多種路由攻擊進行入侵檢測，同時在路由選擇時結合強化學習方法來實現安全且智能的路由。