無人機自組網(wǎng)中基于Q-learning算法的 及時穩(wěn)定路由策略

摘 要： "無人機自組網(wǎng)憑借其抗干擾能力強、適用于復雜地形、智能化程度高和成本較低的優(yōu)點，近年來受到廣泛關(guān)注，該網(wǎng)絡(luò)中路由協(xié)議的設(shè)計與優(yōu)化一直是核心研究問題。針對無人機自組網(wǎng)中因節(jié)點快速移動造成節(jié)點本地存儲的路由未及時更新而失效的問題，提出一種基于Q-learning算法的動態(tài)感知優(yōu)化鏈路狀態(tài)路由協(xié)議（DSQ-OLSR）。該協(xié)議首先充分考慮了無人機自組網(wǎng)節(jié)點高速移動的特點，在選取多點中繼（MPR）節(jié)點時添加了鏈路穩(wěn)定性和鏈路存在時間這兩個指標，使得選出的MPR節(jié)點集更穩(wěn)定、合理；其次，結(jié)合Q-learning算法對TC消息的發(fā)送間隔進行自適應(yīng)調(diào)整，使得在網(wǎng)絡(luò)拓撲變動較小時增大TC發(fā)送間隔以減小控制開銷，而在拓撲變動較大時減小TC發(fā)送間隔用于達到快速感知并構(gòu)建網(wǎng)絡(luò)拓撲的要求，進而實現(xiàn)數(shù)據(jù)的及時路由。仿真結(jié)果表明，與DT-OLSR協(xié)議相比，該協(xié)議在端到端時延、吞吐量、成功率和網(wǎng)絡(luò)生存時間性能上分別提高了12.61%、9.28%、7.69%和5.86%，由此驗證了其有效性。

關(guān)鍵詞： "無人機自組網(wǎng)； OLSR； Q-learning； TC消息； 動態(tài)感知

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

文章編號： "1001-3695（2022）02-035-0531-06

doi：10.19734/j.issn.1001-3695.2021.07.0304

Timely and stable routing strategy based on Q-learning algorithm in "UAV Ad hoc network

Yao Yukun， Zhang Benjun， Zhou Yang

（School of Communication amp; Information Engineering， Chongqing University of Posts amp; Telecommunications， Chongqing 400065， China）

Abstract： "The UAV Ad hoc network receives extensive attention in recent years due to its strong anti-interference ability，suitable for complex terrain，high degree of intelligence and low cost.The design and optimization of the routing protocol in this network are always the core research problem.Aiming at the problem that the node doesn’t update the local route in time due to it’s rapid movement in the UAV Ad hoc network，this paper proposed a dynamic sensor optimized link state routing protocol based on the Q-learning algorithm（dynamic sensor optimized link state routing based on Q-learning algorithm，DSQ-OLSR）.Firstly，the proposed protocol fully considered the characteristics of the high-speed movement of nodes in the UAV Ad hoc network.When selected MPR（multi-point relay） nodes，this paper added two indicators of link stability and link existence time to make the selected MPR nodes set more stable and reasonable.In addition，this paper used the Q-learning algorithm to adjust the sending interval of TC messages adaptively.In order to reduce control overhead，the proposed algorithm increased the TC sen-ding interval when the network topology changed slightly.In order to meet the requirements of rapid perception and construction of the network topology and further realize the timely routing of data，the algorithm reduced the TC sending interval when the topology changed greatly.The simulation results show that compared with the DT-OLSR（dynamic topology link state routing based on Q-learning algorithm） protocol，the proposed protocol improves the end-to-end delay，throughput，success rate and network lifetime performance by 12.61%，9.28%，7.69% and 5.86% respectively，which verifies the effectiveness of this protocol.

Key words： "UAV Ad hoc network； OLSR； Q-learning； TC messages； dynamic perception

0 引言

移動自組網(wǎng)（mobile Ad hoc network，MANET）是一種多跳、無中心、自組織的無線網(wǎng)絡(luò)，網(wǎng)絡(luò)中節(jié)點之間的通信不依賴于其他任何基礎(chǔ)設(shè)施，并且網(wǎng)絡(luò)規(guī)模具有可擴展性［1］。憑借上述優(yōu)點，移動自組網(wǎng)近年來得到廣泛的關(guān)注。

無人機自組網(wǎng)（UAV Ad hoc network，UANET）是移動自組織網(wǎng)絡(luò)在無人機領(lǐng)域的擴展應(yīng)用［2］，相比于MANET，該網(wǎng)絡(luò)的節(jié)點移動性更高、網(wǎng)絡(luò)拓撲變化更頻繁并且能源自治［3］，有較高的研究價值。目前，對于無人機自組網(wǎng)路由協(xié)議的研究主要集中于結(jié)合UANET的特性對傳統(tǒng)MANET路由協(xié)議進行優(yōu)化改進和設(shè)計新的適用于無人機自組網(wǎng)的路由協(xié)議兩個方向。OLSR［4～6］是一種用于MANET的先驗式路由協(xié)議，在數(shù)據(jù)傳輸前已建立路由，時延較小，適合節(jié)點數(shù)較多、拓撲變化不太劇烈的場景，因此其改進協(xié)議被廣泛用于無人機自組網(wǎng)［7］。

當前國內(nèi)外現(xiàn)有文獻對于OLSR協(xié)議的改進研究點主要有路由方案、多點中繼機制（MPR選擇機制）優(yōu)化和根據(jù)特定場景對OLSR協(xié)議參數(shù)的改進與優(yōu)化。針對路由方案的優(yōu)化問題，文獻［8］提出了一種基于Q-learning算法的移動自組網(wǎng)路由協(xié)議QL-OLSR，該路由協(xié)議從節(jié)點移動性、鏈路速率和節(jié)點跳數(shù)三方面進行考慮，能適應(yīng)高動態(tài)的拓撲結(jié)構(gòu)，檢測不同時間點的節(jié)點移動程度，使每個節(jié)點能相應(yīng)地更新路由度量。Tilwari等人［9］基于移動性、剩余能量和鏈路質(zhì)量感知并結(jié)合Q-learning算法提出一種新的自組網(wǎng)路由方案。該方案通過確定具有高效能節(jié)點的最優(yōu)路徑來進行路由決策，進而可以保證網(wǎng)絡(luò)的穩(wěn)定性、可靠性和生命周期。文獻［10］針對MP-OLSR協(xié)議的路由度量單一和代價函數(shù)固定的缺點，基于模糊系統(tǒng)對延遲、吞吐量和信噪比進行了分析，同時通過調(diào)整代價函數(shù)實現(xiàn)了對D算法計算出的路由判罰。文獻［11］采用量子遺傳策略對網(wǎng)絡(luò)中的每個節(jié)點進行編碼和初始化，同時結(jié)合了Q學習策略實現(xiàn)對每個節(jié)點的MPR集的優(yōu)化，并提出一種新的路由方式。

針對MPR選擇機制的優(yōu)化問題，文獻［12］設(shè)計了一種模糊系統(tǒng)，該系統(tǒng)以緩沖區(qū)可用性、穩(wěn)定性和信噪比這三種狀態(tài)變量作為輸入并調(diào)整節(jié)點愿意轉(zhuǎn)發(fā)數(shù)據(jù)的意愿值willingness，進而選擇了較優(yōu)的MPR集，提高了網(wǎng)絡(luò)生存期和網(wǎng)絡(luò)傳輸能力。文獻［13］通過添加一種新的消息——確認HELLO消息和設(shè)計轉(zhuǎn)發(fā)度準則對MPR選擇機制進行了優(yōu)化進而解決網(wǎng)絡(luò)運行過程中可能受到的單一黑洞攻擊問題。曹余健［14］對基于權(quán)值的分簇算法進行改進，在選舉簇首時綜合考慮了節(jié)點的能量、連通度、移動性和局部鏈路穩(wěn)定性等因素，選擇合適的節(jié)點作為簇首，有效提高簇結(jié)構(gòu)的穩(wěn)定性，更有利于無人機網(wǎng)絡(luò)的自由擴展。文獻［15］提出一種最小多點中繼機制，用于最小化洪泛控制消息和最大限度提高信道利用率。所提協(xié)議側(cè)重于確保只有一組選定的節(jié)點參與轉(zhuǎn)發(fā)從源發(fā)出的包來增強傳輸?shù)陌踩浴?/p>

針對OLSR協(xié)議參數(shù)的改進與優(yōu)化問題，文獻［7］根據(jù)網(wǎng)絡(luò)拓撲的變化動態(tài)調(diào)整HELLO消息的廣播周期，當有節(jié)點加入時會立即將HELLO的廣播周期減少到最優(yōu)值；當拓撲不再變化時，設(shè)置廣播周期為默認值，并基于此提出改進路由協(xié)議DT-OLSR。文獻［16］提出了一種基于差分進化優(yōu)化（DE）的自適應(yīng)HELLO消息鄰居發(fā)現(xiàn)方案，其中每個節(jié)點都能選擇HELLO間隔參數(shù)的最優(yōu)配置。李懌［17］提出了一種基于支持向量機的信標周期模型并基于該模型實現(xiàn)了OLSR協(xié)議的HELLO消息的自適應(yīng)發(fā)送。

針對OLSR協(xié)議的MPR選擇機制和TC消息的發(fā)送與交互過程，并考慮到無人機自組網(wǎng)場景的特征，本文提出一種基于動態(tài)拓撲感知并結(jié)合Q-learning算法的改進OLSR路由協(xié)議，主要內(nèi)容包括：a）在進行MPR節(jié)點選擇的時候，加入了鏈路穩(wěn)定性和鏈路維持時間兩個度量進而優(yōu)化MPR選擇機制；b）基于Q-learning實現(xiàn)TC消息發(fā)送周期的自適應(yīng)調(diào)整。

1 無人機自組網(wǎng)中OLSR協(xié)議的研究

對于OLSR協(xié)議，網(wǎng)絡(luò)中的MPR節(jié)點通過周期性地洪泛TC消息實現(xiàn)全網(wǎng)拓撲的發(fā)現(xiàn)和生成。與傳統(tǒng)協(xié)議中所有鄰居節(jié)點參與轉(zhuǎn)發(fā)拓撲控制消息的方式相比，由于MPR選擇機制的使用，使得應(yīng)用OLSR協(xié)議的網(wǎng)絡(luò)中相鄰節(jié)點之間的控制消息得到較大的減少，進而減小了網(wǎng)絡(luò)的控制開銷。

1.1 TC消息的生成與交互過程

OLSR協(xié)議中，網(wǎng)絡(luò)中的節(jié)點通過定期發(fā)送HELLO消息實現(xiàn)鄰居發(fā)現(xiàn)過程。每個節(jié)點在找到自己的一跳鄰居和兩跳鄰居之后，根據(jù)設(shè)計的MPR選擇算法選擇MPR節(jié)點，補充并更新鄰居表和MPR選擇集表（MPR selector set，MPR_S集合）。節(jié)點將MPR選擇集中的信息添加進TC消息中，待TC消息發(fā)送定時器到期時進行全網(wǎng)洪泛，由MPR節(jié)點進行處理和轉(zhuǎn)發(fā)，與其具有對稱鏈路的節(jié)點會對收到的TC消息進行處理，用于建立網(wǎng)絡(luò)拓撲和用于數(shù)據(jù)傳輸?shù)穆酚伞?/p>

1.2 問題描述

TC消息用于進行網(wǎng)絡(luò)拓撲的維護，需要在全網(wǎng)進行洪泛，OLSR協(xié)議的MPR選擇機制主要是為每個節(jié)點在自己的一跳鄰居中選擇中繼節(jié)點（MPR節(jié)點），用于轉(zhuǎn)發(fā)自己的TC消息，故MPR節(jié)點數(shù)越少，用于拓撲維護所需要的控制開銷也越小。對于OLSR路由協(xié)議的MPR選取和TC消息的洪泛過程，主要存在以下兩個方面的問題：

a）傳統(tǒng)MPR選擇算法的單一指標選擇導致鄰居節(jié)點的狀態(tài)信息失效。傳統(tǒng)MPR選擇算法［18］在選擇MPR節(jié)點時除了將必經(jīng)節(jié)點（只有經(jīng)過該一跳必經(jīng)節(jié)點到達某兩跳節(jié)點）加入MPR集之外，僅以一跳節(jié)點能連接的兩跳節(jié)點數(shù)（節(jié)點連接度）作為選擇依據(jù)而盡可能將覆蓋度高的一跳節(jié)點加入MPR集合。這種貪心算法的思想能達到局部最優(yōu)的效果，但直接用于UANET時，由于無人機節(jié)點較高的移動性可能導致覆蓋度高的節(jié)點會在短時間內(nèi)離開其他鄰居節(jié)點的通信范圍，進而導致本節(jié)點維護的鄰居表的鄰居狀態(tài)信息失效，造成在當前TC消息發(fā)送間隔內(nèi)數(shù)據(jù)的路由滯后或丟失，這使得僅以節(jié)點的覆蓋度作為MPR節(jié)點選取的唯一選擇指標存在不足。

b）固定的TC消息發(fā)送周期不能實現(xiàn)網(wǎng)絡(luò)拓撲的及時更新。RFC3626［19］中TC消息的發(fā)送間隔為固定值5 s，相鄰兩個發(fā)送周期內(nèi)發(fā)送的TC消息的內(nèi)容差別或大或小，取決于網(wǎng)絡(luò)拓撲的變動情況，故將OLSR協(xié)議用于無人機自組網(wǎng)時應(yīng)當充分考慮無人機節(jié)點高移動性的特點，在網(wǎng)絡(luò)拓撲變動較大時，應(yīng)當減小TC消息的發(fā)送間隔用于及時感知并更新建立網(wǎng)絡(luò)拓撲；當網(wǎng)絡(luò)的變動情況較小時，應(yīng)當增大TC消息的發(fā)送間隔以減小網(wǎng)絡(luò)的控制開銷。

2 改進協(xié)議DSQ-OLSR的原理和實現(xiàn)

針對1.2節(jié)中無人機自組網(wǎng)OLSR協(xié)議存在的兩個問題，本文提出了一種可以感知網(wǎng)絡(luò)拓撲變化的及時、穩(wěn)定路由算法DSQ-OLSR。該算法首先對OLSR協(xié)議的MPR選擇機制進行了優(yōu)化，使MPR節(jié)點的選取更能適用于高速移動的無人機場景；其次，通過對無人機自組網(wǎng)網(wǎng)絡(luò)拓撲的動態(tài)感知并結(jié)合Q-learning算法實現(xiàn)TC消息發(fā)送周期的自適應(yīng)調(diào)整，進而在網(wǎng)絡(luò)拓撲變化不劇烈時能夠減小網(wǎng)絡(luò)的控制開銷。

2.1 基于三指標的MPR選擇機制

針對傳統(tǒng)MPR選擇算法的單一指標選擇導致鄰居節(jié)點狀態(tài)信息失效的問題，提出了優(yōu)化MPR選擇機制，在進行MPR節(jié)點選擇時考慮節(jié)點連接度、節(jié)點間鏈路的穩(wěn)定性和鏈路存在時間這三個指標。

a）鏈路穩(wěn)定性。鏈路穩(wěn)定性 L s 是一個用于體現(xiàn)節(jié)點之間的通信鏈路在一段時間內(nèi)是否可以穩(wěn)定存在的指標，可以通過兩個無人機節(jié)點的速度相似性來進行定量估算其大小。相比于RFC3626中的原始HELLO消息包結(jié)構(gòu)，本文在原始HELLO消息中加入節(jié)點在水平平面上的速度分量 v "x和 v "y ，修改后改進HELLO消息的格式如圖1所示。

根據(jù)式（1）（2）計算節(jié)點的實時速度。

v=v "x+ v "y ""（1）

|v|= |v "x|2+| v "y|2 """（2）

圖2為無人機自組網(wǎng)場景。該場景中無人機節(jié)點1、2、3、4和5的移動速度分別為 v 1、v 2、v 3、v 4和v 5 ，其中速度的大小相同，方向不同。通過式（1）（2）可求得無人機1和2的實際速度分別為 v 1和v 2 。定義兩個節(jié)點之間的鏈路穩(wěn)定性 L s ，如式（3）所示。

L s= cos 〈 v 1，v 2〉= v 1·v 2 |v 1|×|v 2| """（3）

通過式（3）得出向量的相似性，當速度夾角的余弦值越大，兩個速度的相似性越高。當無人機節(jié)點的移動相似性越高，節(jié)點的運動狀態(tài)越接近，節(jié)點之間的鏈路也更穩(wěn)定，故更適合被選為MPR節(jié)點。

b）鏈路維持時間。鏈路維持時間是用來判斷節(jié)點之間鏈路可以維持的有效時間的一個度量值。通過相對速度和節(jié)點的通信范圍可以計算出鏈路維持時間 L time ，如式（4）所示。

L time= R | v 2-v "1| ""（4）

其中： R 表示節(jié)點的通信半徑； v 2-v 1 表示節(jié)點2相對于節(jié)點1的相對速度。

2.2 基于Q-learning算法的TC消息自適應(yīng)發(fā)送機制

2.2.1 Q-learning算法概述

Q-learning是一種智能體在馬爾可夫域中選取并執(zhí)行最優(yōu)動作的強化學習算法。智能體作為動作的發(fā)起者，通過和環(huán)境的交互完成學習過程，并累計該過程中環(huán)境的反饋獎勵值為下次處于相同狀態(tài)時提供決策依據(jù)。

圖3為Q-learning算法的基本框架。Q-learning以馬爾可夫決策過程（Markov decision process，MDP）為理論基礎(chǔ)，MDP過程可以用三元組 〈S，A，R〉表示，其中S表示狀態(tài)集，A表示動作集，R 表示環(huán)境的獎勵值。該過程的基本思路如下：假設(shè)在 t 時刻智能體處于狀態(tài) S t（S t∈S） ，在接收到環(huán)境對于上次動作產(chǎn)生的延遲獎勵值 R t-1（R t-1∈R） 后根據(jù)Q-table選擇最優(yōu)動作 A t（A t∈A） 轉(zhuǎn)移至狀態(tài) S t+1 ，之后累計環(huán)境反饋回的延遲獎勵值 R t（R t∈R） 用于下次決策 A t+1（A t+1∈A） 。智能體循環(huán)執(zhí)行這種根據(jù)環(huán)境執(zhí)行動作——執(zhí)行動作后又有環(huán)境獎勵的反饋式交互完成學習過程，為特定環(huán)境狀態(tài)提供最優(yōu)決策。

2.2.2 模型構(gòu)建

傳統(tǒng)的OLSR協(xié)議中，用于拓撲維護和生成路由的TC控制消息的發(fā)送間隔為固定值5 s。在高速移動的無人機場景下，當TC發(fā)送間隔較大并且無人機節(jié)點快速移動時，會導致網(wǎng)絡(luò)拓撲在短時間內(nèi)發(fā)生較大的變化，進而造成數(shù)據(jù)不能正確及時路由；TC發(fā)送間隔較小會導致拓撲控制消息頻繁發(fā)送，進而產(chǎn)生較大的控制開銷。使用了Q-learning算法的無人機在進行在線自主學習時能及時感知網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化，故可以將Q-learning與OLSR相結(jié)合應(yīng)用于無人機自組網(wǎng)。 本文的智能體是指無人機節(jié)點，根據(jù)Q-learning算法，假設(shè)智能體agent處于狀態(tài)集 S 中的狀態(tài) s 1 ，根據(jù)當前環(huán)境執(zhí)行動作集 A中的某個動作a ，并且在一定延遲之后環(huán)境會給予回報 R （獎勵或懲罰），智能體累計在該狀態(tài)下執(zhí)行各種動作的獎懲值用于為下次處于相同狀態(tài)下的最優(yōu)決策提供依據(jù)。智能體與環(huán)境的交互過程實際上是一個馬爾可夫決策過程，因此在使用Q-learning對OLSR協(xié)議的TC消息發(fā)送過程進行優(yōu)化時，首要的問題就是將TC消息的自適應(yīng)發(fā)送過程描述為一個MDP過程。以下對這一MDP過程中需要的狀態(tài)、動作、獎勵函數(shù)給出定義。

1）狀態(tài) 考慮到無人機場景下節(jié)點處于連續(xù)移動的過程，因此產(chǎn)生的狀態(tài)具有連續(xù)性。為了簡化狀態(tài)集并使智能體無人機的學習過程更易于處理和分析，需要采用多個適當?shù)臓顟B(tài)參量將連續(xù)狀態(tài)離散化。本文使用了如下的兩個狀態(tài)參量：

a）MPR_S集合的變化率。MPR_S集合的元素是選擇本節(jié)點作為MPR的節(jié)點，MPR節(jié)點可以讓本節(jié)點感知兩跳范圍內(nèi)的拓撲，因此可以通過計算MPR_S集合中元素的變化率 C MPR_S 來估算網(wǎng)絡(luò)拓撲的變化程度。定義 C MPR_S 為

C MPR_S= num c num c+num nc """（5）

其中： num c=num{G 1∪G 2-G 1∩G 2} ，表示前后兩個時刻MPR_S集合中增加或減少的元素（節(jié)點）的數(shù)目； num nc=num{G 1∩G 2} ，表示前后兩個時刻MPR_S集合中相同元素的數(shù)目， G 1 是上一TC消息發(fā)送時刻 t 1 本節(jié)點的MPR_S集合， G 2 是本時刻 t 2 本節(jié)點的MPR_S集合， num 表示數(shù)目。

b）節(jié)點MAC層的緩存占用率。節(jié)點MAC層緩存隊列的占用率可以定量估算節(jié)點的負載程度。假設(shè)每個節(jié)點的緩沖隊列長度為 L ，緩沖區(qū)中放置的包主要分為本節(jié)點發(fā)送的數(shù)據(jù)包 num s_d 、發(fā)送的控制消息包 num s_c （如果需要的話）、轉(zhuǎn)發(fā)的數(shù)據(jù)包 num f_d 、轉(zhuǎn)發(fā)的控制消息 num f_c （如果需要的話）、重傳的數(shù)據(jù)包 num ret 五種。假設(shè)鏈路中的出錯概率為 P e ，則有

num ret=（num s_d+num s_c+num f_d+num f_c）×P e×NUM ret ""（6）

其中： NUM ret 表示重傳次數(shù)。故節(jié)點MAC層的緩存占用率 U 的計算如式（7）所示。

U=（num s_d+num s_c+num f_d+num f_c+num ret）/L ""（7）

2）動作 本文的動作為無人機智能體根據(jù)感知到的網(wǎng)絡(luò)拓撲變化采取TC消息發(fā)送周期的自適應(yīng)調(diào)整策略。TC消息發(fā)送間隔的減小能增加智能體無人機對網(wǎng)絡(luò)拓撲和環(huán)境的感知靈敏度，并實現(xiàn)數(shù)據(jù)的及時路由，但是同樣會增加用于維護網(wǎng)絡(luò)的控制開銷。因此，在某一狀態(tài)下選取動作的策略是使用Q-learning對OLSR路由協(xié)議的TC消息發(fā)送的過程進行優(yōu)化的主要目標。前文MPR選擇機制中的指標鏈路存在時間 L time ，實際意義是鄰居節(jié)點在相對運動的情況下移出本節(jié)點通信范圍的最小時間。場景中的每個節(jié)點維護一個鏈路存在時間表 T link，T link 的結(jié)構(gòu)如表1所示。

表1中第三列表示本節(jié)點與對應(yīng)鄰居節(jié)點之間鏈路的存在時間。將TC消息的發(fā)送間隔設(shè)置為發(fā)送TC消息時本節(jié)點 T link 表中 L time 的最小值，如式（8）所示。

I TC =min {L time_1，L time_2，…} ""（8）

式（8）中的TC消息發(fā)送間隔可以實現(xiàn)所有的一跳鄰居節(jié)點在下一次TC消息發(fā)送時刻前與本節(jié)點之間的通信鏈路仍處于有效期，即網(wǎng)絡(luò)拓撲有效，故不會產(chǎn)生數(shù)據(jù)包的丟失。

3）價值函數(shù)和回報函數(shù) 無人機智能體在執(zhí)行了動作集中的某個動作之后，會接收環(huán)境的反饋獎勵值，并累計該值為下次再出現(xiàn)在該狀態(tài)時要執(zhí)行的決策提供依據(jù)，獎勵值為正值時表示是獎勵，為負值時表示是懲罰。因此，定義每個狀態(tài)的價值函數(shù) V 如式（9）所示。

V=-α ×lg （C MPR_S）+β ×lg （1-U）+γ×L s ""（9）

其中： 1-U 表示節(jié)點當前的業(yè)務(wù)負載能力； α、β和γ 分別是MPR_S集合變化率、節(jié)點負載能力和鏈路穩(wěn)定性這三個參量的權(quán)重系數(shù)，并且在本文中設(shè)置為0.4、0.2和0.4。從式（9）可以得出，該價值函數(shù)具有快速平穩(wěn)節(jié)點拓撲發(fā)現(xiàn)能力和負載能力的功能，并且變量之間的相關(guān)性符合理論分析。

定義環(huán)境反饋的回報函數(shù)如式（10）所示。

R t=V′ t 1-V t 1 ""（10）

其中：節(jié)點在 t 1時刻執(zhí)行動作a由狀態(tài)s 1轉(zhuǎn)至s 2，價值分別為V′ t 1和V t 1 。取狀態(tài)轉(zhuǎn)移前后價值的差值作為環(huán)境的獎勵值，即回報函數(shù) R t ，并作為獎勵矩陣R-table的表項值。

4）訓練算法 訓練算法是為了找到一種策略，該策略選定特定狀態(tài)下的動作使得智能體能獲得該狀態(tài)下已有記錄的動作的最大回報獎勵值。在DSQ-OLSR中，狀態(tài)轉(zhuǎn)移前后環(huán)境的獎勵值即前文中的回報函數(shù)。本文中訓練算法的目的是為了在訓練過程中，通過不斷與環(huán)境進行著有獎懲值這種類型的交互和學習，實現(xiàn)無人機節(jié)點對網(wǎng)絡(luò)拓撲變化情況的靈敏感知和用于網(wǎng)絡(luò)維護的控制開銷兩者之間的平衡，即在網(wǎng)絡(luò)拓撲結(jié)構(gòu)變動較大的時候，減小TC消息的發(fā)送間隔，用于及時感知節(jié)點的周邊網(wǎng)絡(luò)和實現(xiàn)數(shù)據(jù)的及時正確路由；在網(wǎng)絡(luò)拓撲變動情況較低時，增大TC消息的發(fā)送周期，以減小網(wǎng)絡(luò)控制開銷。

Q-learning中，智能體的學習過程就是通過值的迭代不斷更新在特定狀態(tài)下采取的最優(yōu)決策的過程，決策過程中會維護一個Q表（Q-table），記錄學習過程中所有的狀態(tài)、動作和Q值。Q表的具體格式如表2所示。

表2中，表項 Q（s 1，a 1） 表示 t 1 時刻，節(jié)點在狀態(tài) s 1 采取動作 a 1 的預(yù)期折扣獎勵值。假設(shè)在時間 t ，對應(yīng)于狀態(tài) s t和a t ，則 Q（s t，a t） 的更新規(guī)則如式（11）所示。

Q（s t，a t）←（1-λ）Q（s t，a t）+λ[R t+1+μ max "Q（s t+1，a t+1）] ""（11）

其中： λ 是學習率，滿足 0≤λ≤1；μ 是折扣因子，滿足 0lt;μ≤1 。本文中設(shè)置 λ和μ 均為0.5。

使用Q-learning對無人機自組網(wǎng)OLSR協(xié)議的TC消息發(fā)送過程的優(yōu)化步驟具體如下：

a）設(shè)置初始狀態(tài)為當前狀態(tài) s ，目的狀態(tài)為 D ，并分別初始化Q-table、R-table矩陣中的 Q值、R 值全為0和TC消息的起始發(fā)送周期為5 s，其中 Q值為Q（s t，a t）， ε（s∈S，a∈A） 。

b）無人機智能體根據(jù)當前狀態(tài)選取Q-table表中相應(yīng)行中Q值最大的表項執(zhí)行對應(yīng)的動作，狀態(tài)轉(zhuǎn)移至 s′ 。

c）根據(jù)式（9）計算每個狀態(tài)的價值函數(shù) V ，并根據(jù)式（10）計算回報函數(shù) R t 。收到對應(yīng)的環(huán)境反饋的獎勵值 R 后，更新Q-table和R-table。其中，Q-table的更新規(guī)則如式（11）所示。

d）將初始狀態(tài)重置為 s′ ，執(zhí)行步驟b），直至 s′為D（D 為本無人機節(jié)點的目的節(jié)點），結(jié)束訓練過程。

上述步驟的流程如圖4所示。

3 理論分析和仿真驗證

3.1 理論分析

1）對于MPR選擇算法 算法的計算和存儲開銷是增大的。在收到HELLO消息后需要提取速度信息字段，并按照式（1）（2）進行計算，故相較于原始OLSR協(xié)議的計算開銷增大了。由于無人機節(jié)點收到不同HELLO消息的時刻可能不同，并且需要在Q-learning算法中用到鏈路穩(wěn)定性 L s 這一指標，所以需要將這兩個指標的信息存儲在每個節(jié)點本地內(nèi)存中。對于鏈路穩(wěn)定性 L s ，由于 L s 值為-1～1，所以采用1 Byte來存放（其中1 bit表示符號位，1 bit表示個位是0或1，剩下6 bit表示小數(shù)部分，即精確度）；對于鏈路維持時間 L time，L time 為float類型的數(shù)據(jù)，因此分配4 Byte的內(nèi)存。故當收到一個HELLO消息后，需要5 Byte的內(nèi)存來存放 L s和L time 。設(shè)網(wǎng)絡(luò)中的節(jié)點數(shù)為 n ，每個節(jié)點的平均鄰居數(shù)為 num neighbor ，則所有節(jié)點在一個HELLO周期內(nèi)收到一條鄰居發(fā)來的HELLO消息后，開辟的本地內(nèi)存為 n×num neighbor×5。L s和L time 在下次收到HELLO消息時需要重新計算，但是已經(jīng)分配的內(nèi)存可以重復使用，故內(nèi)存開銷有一定的增大，但是增加量并不大。雖然在計算和內(nèi)存開銷上增加了，但是通過3.2節(jié)可知，這樣的犧牲可以換來端到端時延、吞吐量和成功率性能的提升，完全滿足無人機場景的迫切需求。

2）對于Q-learning算法 由MPR選擇算法確定了每個節(jié)點的MPR集合后，需要執(zhí)行Q-learning算法進行TC消息發(fā)送周期的自適應(yīng)調(diào)整。Q-learning算法中需要使用上文中提到的鏈路穩(wěn)定性 L s 這一指標，而這一指標已經(jīng)存儲在節(jié)點本地內(nèi)存，但其仍然會參與式（9）的計算。

3.2 仿真驗證

仿真中，選取了標準的OLSR路由協(xié)議與本文DSQ-OLSR協(xié)議作對比，分析了兩者的端到端時延、吞吐量、控制開銷和成功率這四個網(wǎng)絡(luò)性能指標。

3.2.1 仿真參數(shù)設(shè)置

在Windows 10平臺下的OPNET 14.5仿真軟件中，設(shè)置了五個大小為1 500 m×1 500 m的仿真場景，節(jié)點數(shù)分別為15、30、45、60、75個，且呈均勻分布。MAC層使用的是IEEE 802.11標準，節(jié)點的移動模型采用PPRAM模型。具體的仿真參數(shù)如表3所示。

3.2.2 仿真結(jié)果分析

1）平均端到端時延分析

平均端到端時延 D aver-ete 的計算如式（12）所示。

D aver-ete= ∑T rcv num rcv """（12）

其中： ∑T rcv 表示所有目的節(jié)點收到數(shù)據(jù)包的傳輸時間； num rcv 表示目的節(jié)點收到的數(shù)據(jù)包數(shù)目。

圖5表明，DT-OLSR、QL-OLSR和DSQ-OLSR協(xié)議的端到端時延隨著節(jié)點數(shù)的增大而增加，但端到端時延的性能由DT-OLSR、QL-OLSR到DSQ-OLSR逐漸變好。DT-OLSR中通過對節(jié)點位置的預(yù)測判斷節(jié)點下一時刻是否超出通信范圍，并據(jù)此對HELLO消息的發(fā)送周期進行了調(diào)整，使其更適合于動態(tài)網(wǎng)絡(luò)，故較OLSR協(xié)議時延性能更好。QL-OLSR中綜合考慮了網(wǎng)絡(luò)拓撲的變動幅度和鏈路速率（可以反映鏈路容量），建立的路由較穩(wěn)定，故時延性能較DT-OLSR更好。DSQ-OLSR中在選取MPR節(jié)點時考慮了鏈路穩(wěn)定性和鏈路質(zhì)量，在Q-learning算法中選取的狀態(tài)變量使得TC消息的更新更及時，即拓撲更準確，故時延性能最好。

2）吞吐量分析

吞吐量 T 的計算如式（13）所示。

Throught= num rcv×S pk D aver_ete """（13）

其中： S pk 表示數(shù)據(jù)包的大小，仿真中設(shè)為512 Bytes。

圖6表明，DSQ-OLSR協(xié)議較QL-OLSR和DT-OLSR的吞吐量性能均有一定的提升。DT-OLSR在OLSR協(xié)議的基礎(chǔ)上考慮了無人機場景的高動態(tài)的特點，并根據(jù)網(wǎng)絡(luò)拓撲的變動對HELLO消息的發(fā)送過程進行了優(yōu)化調(diào)整，故吞吐量增大。相較于QL-OLSR，DSQ-OLSR考慮了節(jié)點MAC層的負載并優(yōu)化了MPR選擇過程，并且由Q-learning算法實現(xiàn)的TC消息自適應(yīng)發(fā)送機制更適合拓撲不穩(wěn)定的移動場景，更有利于數(shù)據(jù)的及時正確路由，所以數(shù)據(jù)包因為重傳失敗造成的丟包情況較少，故正確接收的包的數(shù)量增大，吞吐量性能更好。

3）控制開銷分析

控制開銷用于進行鄰居發(fā)現(xiàn)的HELLO消息的發(fā)送和進行拓撲維護的TC消息的發(fā)送和轉(zhuǎn)發(fā)。如圖7所示，OLSR路由協(xié)議的控制消息是固定周期發(fā)送，所以控制開銷整體上在一個穩(wěn)定值的小范圍內(nèi)波動，與速度的大小無關(guān)。DT-OLSR協(xié)議在HELLO消息中添加了每個鄰居的位置信息（96 bit），并且該協(xié)議對HELLO消息的發(fā)送進行了動態(tài)調(diào)整，當無人機節(jié)點速度較大時，鄰居節(jié)點的入網(wǎng)和脫網(wǎng)較頻繁，故控制開銷增加。QL-OLSR協(xié)議中，雖然使用了Q-learning算法對路由選擇進行了優(yōu)化，但是控制消息仍然是定期發(fā)送，故控制開銷與OLSR基本相同，圍繞一個定值上下波動。DSQ-OLSR協(xié)議相比QL-OLSR協(xié)議的控制開銷較大。DSQ-OLSR協(xié)議在HELLO消息中添加了32 bit的無人機節(jié)點在水平方向上的速度分量大小信息（| v "x|和| v "y| ），造成HELLO消息開銷增大，但是由于TC消息發(fā)送間隔的調(diào)整，使得在拓撲變動不大時TC消息發(fā)送間隔增大，減小TC消息開銷（這種性能的改善隨著節(jié)點移動速度的增加而降低），故DSQ-OLSR協(xié)議實際上是通過犧牲控制開銷來換取吞吐量和成功率性能的提升。

4）成功率分析

成功率 P success 的計算如式（14）所示。

P success= num rcv num send """（14）

其中： num send 表示發(fā)送的數(shù)據(jù)包的個數(shù)。

圖8表明，DSQ-OLSR協(xié)議的成功率性能較DT-OLSR相比有明顯的提升。DT-OLSR協(xié)議中設(shè)計了HELLO消息自適應(yīng)發(fā)送機制，使得一些新入網(wǎng)和脫網(wǎng)的無人機節(jié)點能被及時發(fā)現(xiàn)，故較OLSR成功率有所提高。QL-OLSR基于Q-learning算法，并從鏈路速率、節(jié)點移動性和節(jié)點跳數(shù)三個方面對路由策略進行了優(yōu)化，提高了路由的穩(wěn)定性。由于考慮了鏈路速率，故QL-learning協(xié)議的成功率性能進一步提高。DSQ-OLSR協(xié)議中更綜合考慮了無人機場景的特征，添加了鏈路穩(wěn)定性和鏈路有效時間兩個度量值，并在設(shè)計TC消息自適應(yīng)發(fā)送機制時考慮了節(jié)點的負載能力，更有利于網(wǎng)絡(luò)拓撲感知和負載感知，能使數(shù)據(jù)包得到正確的轉(zhuǎn)發(fā)，提高了成功率，并且隨著節(jié)點速度的增加，性能的改善效果更明顯。

5）網(wǎng)絡(luò)生存時間分析

網(wǎng)絡(luò)生存時間是指網(wǎng)絡(luò)中的節(jié)點能維持通信的最大時間。該無人機場景下，網(wǎng)絡(luò)生存時間主要受到節(jié)點的能量和移速影響。仿真中設(shè)置每個節(jié)點的初始能量為300 J，發(fā)送和接收包的功率為1.5 W。隨著網(wǎng)絡(luò)的運行，節(jié)點的剩余能量在減少。

圖9表明DSQ-OLSR協(xié)議的網(wǎng)絡(luò)生存時間性能較DT-OLSR相比有明顯的提升。DT-OLSR協(xié)議控制消息最大，消耗的能量最多，因此網(wǎng)絡(luò)存在時間最短。DSQ-OLSR協(xié)議控制消息的大小介于OLSR（或QL-OLSR）和DT-OLSR之間，故生存時間大小關(guān)系成相反的關(guān)系。OLSR和QL-OLSR的控制消息大小相同，故網(wǎng)絡(luò)生存時間基本相同。隨著節(jié)點移速的增加，具有動態(tài)感知拓撲變化能力的DT-OLSR和DSQ-OLSR協(xié)議的生存時間因為控制消息發(fā)送的更頻繁，導致能量損耗加快，所以網(wǎng)絡(luò)生存時間降低。

4 結(jié)束語

本文提出了一種改進OLSR協(xié)議（DSQ-OLSR協(xié)議），該協(xié)議對OLSR中的MPR選擇機制進行了優(yōu)化，添加了鏈路穩(wěn)定性和鏈路維持時間這兩個MPR選擇度量，并基于Q-learning算法實現(xiàn)了TC消息發(fā)送周期的自適應(yīng)調(diào)整，使無人機節(jié)點具有了認知能力，更適合高速移動的無人機自組網(wǎng)。仿真結(jié)果表明，改進協(xié)議DSQ-OLSR在吞吐量、成功率、端到端時延和網(wǎng)絡(luò)生存時間性能上均有所改善。由于在優(yōu)化OLSR協(xié)議過程中，在HELLO消息中添加了節(jié)點的速度信息，導致控制開銷有一定的增加，下一步將針對控制開銷問題考慮無人機自組網(wǎng)的優(yōu)化路由方案。

參考文獻：

［1］ "Sathyaraj P，Devi D R.Designing the routing protocol with secured IoT devices and QoS over manet using trust-based performance evaluation method［J］. Journal of Ambient Intelligence and Humanized Computing ，2021， 12 （7）：6987-6995.

［2］ Wang Xudong，Mi Zhichao，Wang Hai， et al. Performance test and analysis of multi-hop network based on UAV Ad hoc network experiment［C］//Proc of the 9th International Conference on Wireless Communications and Signal Processing.New York：Institute of Electrical and Electronics Engineers Inc.，2017：1-6.

［3］ 李子恒.無人機自組織網(wǎng)絡(luò)中的OLSR路由協(xié)議的研究與優(yōu)化［D］.哈爾濱：哈爾濱工業(yè)大學，2020. （Li Ziheng.Research and optimization of OLSR routing protocol in UAV Ad hoc network［D］.Harbin：Harbin Institute of Technology，2020.）

［4］ Zougagh H，Idboufker N，Saadi Y.Trust-based intrusion detection for multi path OLSR protocol［C］//Proc of the 12th International Confe-rence on Soft Computing and Pattern Recognition.Berlin：Springer，2021：690-705.

［5］ Hong Kunqi，Shi Shuo，Gu Xuemai， et al. Optimization of OLSR protocol in UAV network［C］//Proc of International Conference on Artificial Intelligence for Communications and Networks.Berlin：Springer，2021：239-248.

［6］ Jiang Yuqing，Mi Zhichao，Wang Hai.An improved OLSR protocol based on task driven used for military UAV swarm network［C］//Proc of International Conference on Intelligent Robotics and Applications.Berlin：Springer，2019：569-581.

［7］ 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 Techno-logy.New York：Institute of Electrical and Electronics Engineers Inc.，2019：1258-1263.

［8］ 金鑫.大規(guī)模移動自組織網(wǎng)絡(luò)OLSR路由協(xié)議優(yōu)化［D］.北京：北京交通大學，2020. （Jin Xin.Optimization of OLSR routing protocol for large-scale mobile Ad hoc network［D］.Beijing：Beijing Jiaotong University，2020.）

［9］ Tilwari V，Dimyati K，Hindia M.Mobility，residual energy，and link quality aware multipath routing in MANETs with Q-learning algorithm［J］. Applied Sciences ，2019， 9 （8）：1582-1605.

［10］ Boushaba A，Benabbou A，Benabbou R， et al. "An intelligent multipath optimized link state routing protocol for QoS and QoE enhancement of video transmission in MANETs［J］. Computing ，2016， 98 （8）：803-825.

［11］ Zhang Degan，Cui Yuya，Zhang Ting.New quantum-genetic based OLSR protocol（QG-OLSR） for mobile Ad hoc network［J］. Applied Soft Computing ，2019， 80 （8）：285-296.

［12］ "Hanin M H，F(xiàn)akhri Y，Amnai M， et al. "A new efficient technique to enhance quality of service in OLSR protocol［C］//Proc of International Conference on Advanced Intelligent Systems for Sustainable Development.Berlin：Springer，2018：85-97 .

［13］ Nabou A，Laanaoui M，Ouzzif M.New MPR computation for securing OLSR routing protocol against single black hole attack［J］. Wireless Personal Communications ，2021， 117 （2）：525-544.

［14］ 曹余健.無人機網(wǎng)絡(luò)的路由協(xié)議研究［D］.西安：西安電子科技大學，2020. （Cao Yujian.Research on routing protocol of UAV network［D］.Xi’an：Xidian University，2020.）

［15］ Usha M，Ramakrishnan B.A robust architecture of the OLSR protocol for channel utilization and optimized transmission using minimal multi point relay selection in VANET［J］. Wireless Personal Communications ，2019， 109 （1）：271-295.

［16］ Harrag N，Refoufi A.Neighbor discovery using novel DE-based adaptive hello messaging scheme improving OLSR routing protocol perfor-mances［C］//Proc of the 6th International Conference on Systems and Control.Piscataway，NJ：IEEE Press，2019：1763-1767.

［17］ 李懌.針對FANETs的基于信標周期模型的自適應(yīng)OLSR協(xié)議［D］.廣州：華南理工大學，2020. （Li Yi.Adaptive OLSR protocol based on the beacon period model for FANETs［D］.Guangzhou：South China University of Technology，2020.）

［18］ 陳煉.基于Linux系統(tǒng)的OLSR路由協(xié)議研究與實現(xiàn)［D］.重慶：重慶郵電大學，2017. （Chen Lian.Research and implementation of OLSR routing protocol based on Linux system［D］.Chongqing：Chongqing University of Posts and Telecommunications，2017.）

［19］ Clausen T，Jacquet P.RFC3626：optimized link state routing protocol（OLSR）［J］. Experimental ，2003， 51 （1）：78-167.