謝勇盛，楊余旺，邱修林，王吟吟

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210094）

0 概述

近年來(lái)，無(wú)人機(jī)群在森林防火、智能農(nóng)業(yè)、滲透?jìng)刹?、火力打擊等民用和軍用領(lǐng)域具有廣泛應(yīng)用。為完成復(fù)雜的協(xié)同任務(wù)，穩(wěn)健的通信方式是必不可少的。移動(dòng)自組網(wǎng)（Mobile Ad-Hoc Network，MANET）［1］作為一種無(wú)中心、多跳、自治的無(wú)線網(wǎng)絡(luò)，被認(rèn)為是最適合無(wú)人機(jī)的通信方式之一［2-3］。在MANET 中，每個(gè)節(jié)點(diǎn)不僅作為終端主機(jī)，也充當(dāng)轉(zhuǎn)發(fā)消息的路由器。但由于節(jié)點(diǎn)是移動(dòng)的，這導(dǎo)致通信鏈路的頻繁變化，因此需要一個(gè)能夠幫助網(wǎng)絡(luò)組網(wǎng)和維護(hù)鏈路穩(wěn)定的路由協(xié)議。目前，對(duì)MANET 路由協(xié)議的研究已經(jīng)有了很大的發(fā)展，根據(jù)不同的路由策略，可將路由協(xié)議分為主動(dòng)路由協(xié)議、按需路由協(xié)議和混合路由協(xié)議。在主動(dòng)路由協(xié)議中，在進(jìn)行業(yè)務(wù)傳輸前，節(jié)點(diǎn)主動(dòng)探測(cè)周邊鄰居節(jié)點(diǎn)并維護(hù)鏈路信息。這種優(yōu)先確定路由鏈路的方式相較按需路由協(xié)議和混合路由協(xié)議具有更高的實(shí)時(shí)性［4］。但由于無(wú)人機(jī)節(jié)點(diǎn)移動(dòng)速度快，網(wǎng)絡(luò)拓?fù)渥兓杆伲瑐鹘y(tǒng)的MANET 路由協(xié)議已經(jīng)難以滿足無(wú)人機(jī)通信組網(wǎng)的需求，為此研究人員提出飛行自組網(wǎng)（Flying Ad-Hoc Network，F(xiàn)ANET）［5］，因此探究適用于FANET 環(huán)境的路由技術(shù)對(duì)改善網(wǎng)絡(luò)性能具有著重要的意義。

FANET 雖源于MANET，但 比MANET 有著更復(fù)雜的應(yīng)用環(huán)境，具有高動(dòng)態(tài)性、高稀疏性、鏈路質(zhì)量多變等通信特點(diǎn)，為建立穩(wěn)定鏈路帶來(lái)很大困難。因此，F(xiàn)ANET 路由協(xié)議應(yīng)綜合考慮無(wú)人機(jī)應(yīng)用、服務(wù)器性質(zhì)、節(jié)點(diǎn)高速移動(dòng)等特性。常見(jiàn)的FANET 路由協(xié)議設(shè)計(jì)思路源于對(duì)傳統(tǒng)的MANET 路由協(xié)議進(jìn)行適當(dāng)改進(jìn)。MANET 研究初期的路由協(xié)議對(duì)節(jié)點(diǎn)移動(dòng)性并不敏感，若要使網(wǎng)絡(luò)適應(yīng)飛行節(jié)點(diǎn)的動(dòng)態(tài)特性，則需要節(jié)點(diǎn)自身能夠通過(guò)問(wèn)候消息（即HELLO 消息）或鏈路層反饋機(jī)制探測(cè)和維護(hù)可連通鄰居節(jié)點(diǎn)，以此保障鏈路暢通。與鏈路反饋機(jī)制相比，通過(guò)路由協(xié)議定期交換問(wèn)候消息更優(yōu)，因?yàn)榍罢卟⒉皇芟抻谌魏翁囟ǖ逆溌穼蛹夹g(shù)［6］。這種主動(dòng)發(fā)送探測(cè)包的路由技術(shù)在MANET 中被稱為主動(dòng)路由協(xié)議，其中應(yīng)用較廣泛的為最優(yōu)鏈路狀態(tài)路由（Optimal Link State Routing，OLSR）［4］協(xié)議。

但對(duì)于高動(dòng)態(tài)FANET 而言，這種定期交換HELLO 消息的路由協(xié)議難以適應(yīng)多變的網(wǎng)絡(luò)環(huán)境。在主動(dòng)路由協(xié)議中，HELLO 消息時(shí)隙的選擇對(duì)于鏈路的發(fā)現(xiàn)起著決定性的作用［3］。時(shí)隙越短，越有助于快速檢測(cè)新鄰居或鏈路中斷，但會(huì)產(chǎn)生更高的開(kāi)銷，阻礙正常數(shù)據(jù)包的發(fā)送。時(shí)隙越長(zhǎng)，開(kāi)銷會(huì)越少，但會(huì)限制鄰居發(fā)現(xiàn)和鏈接中斷檢測(cè)能力。在高動(dòng)態(tài)FANET 中，需要在實(shí)時(shí)感知環(huán)境的同時(shí)自適應(yīng)修改HELLO 時(shí)隙并優(yōu)化整個(gè)網(wǎng)絡(luò)性能［7-8］。針對(duì)FANET 高動(dòng)態(tài)網(wǎng)絡(luò)場(chǎng)景下的節(jié)點(diǎn)鏈路探測(cè)問(wèn)題，本文對(duì)傳統(tǒng)OLSR 算法進(jìn)行改進(jìn)，提出一種基于強(qiáng)化學(xué)習(xí)的自適應(yīng)鏈路狀態(tài)路由算法QLA-OLSR。通過(guò)感知?jiǎng)討B(tài)環(huán)境下節(jié)點(diǎn)鄰居數(shù)量變化程度和業(yè)務(wù)負(fù)載能力，獲取最優(yōu)HELLO 時(shí)隙決策，并利用自學(xué)習(xí)不斷調(diào)整和完善這一決策，以達(dá)到優(yōu)化網(wǎng)絡(luò)性能的目的。

1 相關(guān)工作

主動(dòng)路由協(xié)議節(jié)點(diǎn)定期發(fā)送HELLO 消息，探測(cè)周圍鏈路情況，能幫助網(wǎng)絡(luò)更快地適應(yīng)環(huán)境。但無(wú)人機(jī)高速移動(dòng)和分布稀疏的特性又造成了節(jié)點(diǎn)交匯的時(shí)間減少、相遇的可能性降低等問(wèn)題。針對(duì)傳統(tǒng)MANET 路由協(xié)議的HELLO 時(shí)隙改進(jìn)以適應(yīng)節(jié)點(diǎn)高速運(yùn)動(dòng)，一些研究人員提出了不同的方案。

MAHMUD 等［7］提出一 種EE-OLSR 路由協(xié) 議，通過(guò)計(jì)算網(wǎng)絡(luò)密度，感知節(jié)點(diǎn)能量消耗、綜合節(jié)點(diǎn)密度等多種參量達(dá)到選擇時(shí)隙的目的。

HERNANDEZ-CONS 等［9］提出一種基于鏈路變化率的自適應(yīng)HELLO 時(shí)隙方法。節(jié)點(diǎn)統(tǒng)計(jì)單位時(shí)間內(nèi)添加或刪除的鏈路總數(shù)作為衡量鏈路變化的標(biāo)準(zhǔn)，如果鏈路變化率高，則鄰居變化快，探測(cè)消息時(shí)隙縮短，反之，增加時(shí)隙。

GIRUKA 等［10］提出另一種解決方案，節(jié)點(diǎn)感知自身運(yùn)動(dòng)速度，在特定速度時(shí)采用響應(yīng)的時(shí)隙發(fā)送HELLO 消息。由于節(jié)點(diǎn)具有不同速度，因此為高速節(jié)點(diǎn)分配了較短的探測(cè)報(bào)文時(shí)隙，為低速節(jié)點(diǎn)分配了較長(zhǎng)的探測(cè)報(bào)文時(shí)隙，且局部采用最優(yōu)時(shí)隙，達(dá)到整個(gè)網(wǎng)絡(luò)性能的均衡穩(wěn)定。

HAN 等［11］提出一種用于鄰居發(fā)現(xiàn)的自適應(yīng)HELLO 消息傳遞方案。該方案利用平均事件間隔，即節(jié)點(diǎn)上兩個(gè)連續(xù)事件（發(fā)送或接收數(shù)據(jù)包）之間的平均時(shí)間間隔，估計(jì)節(jié)點(diǎn)在發(fā)送或轉(zhuǎn)發(fā)中的活躍程度。如果某個(gè)節(jié)點(diǎn)在給定時(shí)間內(nèi)未參與任何通信，則無(wú)需維護(hù)鏈路狀態(tài)，在此期間廣播HELLO 消息是不必要的，因?yàn)橐种撇槐匾膯?wèn)候消息可節(jié)省能量，并且能持續(xù)對(duì)鏈路狀態(tài)進(jìn)行檢測(cè)。

2 QLA-OLSR 算法

2.1 Q 學(xué)習(xí)算法流程

Q 學(xué)習(xí)［12］是一種智能體在可控馬爾科夫域中選取并執(zhí)行最優(yōu)動(dòng)作的強(qiáng)化學(xué)習(xí)算法，類似于一種動(dòng)態(tài)規(guī)劃的增量方法，通過(guò)不斷獲取特定狀態(tài)下特定動(dòng)作的累計(jì)獎(jiǎng)懲值，為下一次遇到相似環(huán)境狀態(tài)時(shí)選擇最優(yōu)動(dòng)作提供依據(jù)。強(qiáng)化學(xué)習(xí)不同于機(jī)器學(xué)習(xí)，學(xué)習(xí)過(guò)程沒(méi)有監(jiān)督者，智能體通過(guò)接收環(huán)境反饋獎(jiǎng)勵(lì)信號(hào)來(lái)評(píng)估動(dòng)作價(jià)值，并且反饋是延遲的，表現(xiàn)為一系列狀態(tài)價(jià)值函數(shù)對(duì)下一步動(dòng)作的影響。

圖1 給出了強(qiáng)化學(xué)習(xí)流程。智能體通過(guò)與環(huán)境進(jìn)行交互獲得回報(bào)來(lái)修正動(dòng)作，其行為步驟可以表示為一個(gè)馬爾科夫決策（Markov Decision Process，MDP）過(guò)程。MDP 可以描述為一個(gè)三元組其基本流程是：當(dāng)t時(shí)刻智能體的狀態(tài)為st(st∈S)時(shí)，智能體會(huì)收到環(huán)境給予它的回報(bào)rt(rt∈R)；智能體根據(jù)累計(jì)的回報(bào)值，做出決策選擇動(dòng)作at(at∈A)并執(zhí)行；智能體進(jìn)入新的狀態(tài)st+1。循環(huán)執(zhí)行這些操作，達(dá)到在特定環(huán)境下選擇最優(yōu)策略的目的。

圖1 強(qiáng)化學(xué)習(xí)流程Fig.1 Procedure of reinforcement learning

2.2 模型構(gòu)建

在使用強(qiáng)化學(xué)習(xí)優(yōu)化OLSR 路由協(xié)議前，需要先將HELLO 時(shí)隙調(diào)整問(wèn)題描述為MDP 過(guò)程。

2.2.1 狀態(tài)

無(wú)人機(jī)節(jié)點(diǎn)具有高動(dòng)態(tài)特點(diǎn)，網(wǎng)絡(luò)拓?fù)渥兓赡芎軓?fù)雜，尤其是考慮到網(wǎng)絡(luò)一直在運(yùn)行，可用于表示網(wǎng)絡(luò)的連續(xù)高維狀態(tài)空間，可以生成幾乎無(wú)限數(shù)量的狀態(tài)。因此，無(wú)人機(jī)節(jié)點(diǎn)需要確定適當(dāng)?shù)臓顟B(tài)變量，以捕獲節(jié)點(diǎn)選擇時(shí)隙帶來(lái)的性能差異并保障學(xué)習(xí)過(guò)程中的易處理性。本文選擇以下3 個(gè)狀態(tài)變量：

1）snbr，表示當(dāng)前節(jié)點(diǎn)時(shí)間步長(zhǎng)Δt內(nèi)鄰居節(jié)點(diǎn)變化程度。snbr計(jì)算如式（1）所示：

其中：nt表示t時(shí)刻鄰居表中的節(jié)點(diǎn)數(shù)目。

2）sload，表示節(jié)點(diǎn)接口隊(duì)列中待發(fā)送的數(shù)據(jù)包個(gè)數(shù)。

3）ssolt，表示當(dāng)前節(jié)點(diǎn)的HELLO 時(shí)隙長(zhǎng)度。

節(jié)點(diǎn)主要是通過(guò)與鄰居節(jié)點(diǎn)交互HELLO 消息來(lái)發(fā)現(xiàn)連通鏈路。頻繁的HELLO 消息可以讓節(jié)點(diǎn)更快地探測(cè)出鄰居節(jié)點(diǎn)的存在，并改變鄰居表中節(jié)點(diǎn)的數(shù)目，但是這也必然會(huì)增加網(wǎng)絡(luò)負(fù)載，阻礙節(jié)點(diǎn)數(shù)據(jù)隊(duì)列中數(shù)據(jù)的發(fā)送。本文通過(guò)QLA-OLSR 權(quán)衡兩者之間的關(guān)系，使其處于一個(gè)平衡的狀態(tài)。

2.2.2 動(dòng)作

選擇下一動(dòng)作是Q 學(xué)習(xí)的主要目標(biāo)，也是影響協(xié)議性能的關(guān)鍵因素。在本文中動(dòng)作指定為智能體感知鄰居節(jié)點(diǎn)拓?fù)渥兓椭苓叚h(huán)境的變化來(lái)更改其HELLO 消息發(fā)送時(shí)隙。本文使用3 個(gè)動(dòng)作來(lái)簡(jiǎn)化動(dòng)作空間，如表1 所示。動(dòng)作指定節(jié)點(diǎn)為響應(yīng)網(wǎng)絡(luò)環(huán)境的變化需要改變其感知時(shí)隙，減少時(shí)隙必然能加快鄰居節(jié)點(diǎn)的感知速度，但是隨之會(huì)帶來(lái)網(wǎng)絡(luò)開(kāi)銷的增長(zhǎng)，節(jié)點(diǎn)通過(guò)接收到的獎(jiǎng)勵(lì)來(lái)選擇一個(gè)動(dòng)作，從而達(dá)到感知速度快與網(wǎng)絡(luò)開(kāi)銷低之間的均衡。

表1 QLA-OLSR 動(dòng)作Table 1 QLA-OLSR action

2.2.3 效用函數(shù)和回報(bào)函數(shù)

學(xué)習(xí)的目標(biāo)是找到調(diào)整HELLO 時(shí)隙的調(diào)整策略，采取決策動(dòng)作后，接收環(huán)境反饋的回報(bào)，累計(jì)此回報(bào)值作為下一次決策的依據(jù)。為此，需要根據(jù)環(huán)境給出回報(bào)正負(fù)價(jià)值的衡量標(biāo)準(zhǔn)，并定義如下效用函數(shù)：

其中：C表示節(jié)點(diǎn)在時(shí)間步t內(nèi)鄰居節(jié)點(diǎn)的數(shù)量變化程度，計(jì)算公式如式（3）所示；L表示當(dāng)前節(jié)點(diǎn)的業(yè)務(wù)負(fù)載能力［13-14］，計(jì)算公式如式（4）所示，其中l(wèi)表示節(jié)點(diǎn)的隊(duì)列緩存長(zhǎng)度；α和δ表示鄰居節(jié)點(diǎn)變化程度和業(yè)務(wù)負(fù)載能力的相對(duì)權(quán)重，在本文中分別設(shè)置為50%。可以直觀地看出，該函數(shù)能夠表示在最大程度上快速平穩(wěn)鄰居節(jié)點(diǎn)探測(cè)并最大化保留節(jié)點(diǎn)轉(zhuǎn)發(fā)業(yè)務(wù)數(shù)據(jù)的能力。

在連續(xù)的效用值中，通過(guò)其差值來(lái)定義如下回報(bào)函數(shù)：

其中：ζ表現(xiàn)為一個(gè)可調(diào)參數(shù)。當(dāng)連續(xù)時(shí)刻效用函數(shù)差值大于ζ時(shí)，取兩者之差為回報(bào)函數(shù)，若回報(bào)函數(shù)為正值，則表現(xiàn)為獎(jiǎng)勵(lì)，若回報(bào)函數(shù)為負(fù)值時(shí)，則表現(xiàn)為懲罰。

2.3 算法訓(xùn)練

訓(xùn)練QLA-OLSR 算法試圖找到一種策略，該策略選定特定狀態(tài)下的動(dòng)作執(zhí)行，并使智能體所接收到的長(zhǎng)期獎(jiǎng)勵(lì)值最大。在QLA-OLSR 中，獎(jiǎng)勵(lì)通過(guò)效用值函數(shù)，訓(xùn)練策略的目的是自適應(yīng)調(diào)整HELLO時(shí)隙變化策略，在高拓?fù)渥兓闆r下，以最大程度地提高節(jié)點(diǎn)感知鄰居的速度，達(dá)到更高的吞吐量，同時(shí)在低拓?fù)渥兓闆r下，最大程度地減少網(wǎng)絡(luò)開(kāi)銷。因此，訓(xùn)練算法的學(xué)習(xí)速度和質(zhì)量是QLA-OLSR 性能的關(guān)鍵。

Q 學(xué)習(xí)用一個(gè)簡(jiǎn)單的迭代值去更新決策過(guò)程，決策動(dòng)作記錄在一個(gè)Q 表中。在時(shí)間步t時(shí)，對(duì)應(yīng)有一個(gè)狀態(tài)st和一個(gè)動(dòng)作at。算法計(jì)算出該時(shí)間步的預(yù)期折扣獎(jiǎng)勵(lì)Q(st,at)，更新規(guī)則如下：

其中：α為學(xué)習(xí)率，滿足0 ≤α≤1；γ為折扣因子，滿足0<γ≤1。在Q 學(xué)習(xí)中所有狀態(tài)下的Q(st,at)存儲(chǔ)在Q 表中。

Q 學(xué)習(xí)為小規(guī)模、離散狀態(tài)空間問(wèn)題提供了一個(gè)良好的解決方案，并且表現(xiàn)出較好的學(xué)習(xí)性和收斂性，但在大規(guī)模、非離散狀態(tài)空間中的伸縮性非常差。因?yàn)樵谶@種情況下，枚舉狀態(tài)量是無(wú)限的，使用Q 表記錄每個(gè)狀態(tài)或狀態(tài)動(dòng)作的價(jià)值函數(shù)是不切實(shí)際的。為了減少存儲(chǔ)大Q 表所需的內(nèi)存和更新訪問(wèn)狀態(tài)或動(dòng)作狀態(tài)對(duì)應(yīng)的Q值所需的訓(xùn)練時(shí)間，在采用RL 算法時(shí)，使用函數(shù)逼近將相似狀態(tài)之間的值關(guān)聯(lián)起來(lái)，使連續(xù)狀態(tài)空間能夠映射到有限的域，添加函數(shù)逼近方式后的強(qiáng)化學(xué)習(xí)流程如圖2 所示。

圖2 基于函數(shù)逼近的強(qiáng)化學(xué)習(xí)流程Fig.2 Procedure of reinforcement learning based on function approximation

3 基于函數(shù)逼近的QLA-OLSR 算法

節(jié)點(diǎn)可感知的狀態(tài)空間是極大且連續(xù)的，對(duì)于Q 學(xué)習(xí)算法而言，迭代出完整的Q 表是極具挑戰(zhàn)性的。為此，本文采用Kanerva 編碼的函數(shù)逼近策略，以減少訓(xùn)練所需的狀態(tài)數(shù)量，可以在存在高維連續(xù)狀態(tài)空間的情況下簡(jiǎn)化Q 學(xué)習(xí)［15］。

3.1 Kanerva 編碼算法

在Kanerva 編碼算法中，選擇一組原型狀態(tài)，并用于估計(jì)值函數(shù)，其中狀態(tài)值是通過(guò)本地原型狀態(tài)值的線性組合來(lái)估算的。在每次迭代中，只有與輸入狀態(tài)相鄰的原型狀態(tài)才會(huì)被更新。原型狀態(tài)由一系列狀態(tài)變量描述，每個(gè)狀態(tài)變量都有一定的數(shù)值范圍。在迭代學(xué)習(xí)之前選擇k個(gè)原型作為狀態(tài)集。假設(shè)給定狀態(tài)s和原型狀態(tài)pi，‖s-pi‖表示兩者數(shù)值差值，如果相差小于某一定值ε，則認(rèn)為狀態(tài)s和原型狀態(tài)pi相鄰，定義s與pi的隸屬度μ(s,pi)如下：

若相差大于給定值，則μ(s,pi)=0。考慮到原型狀態(tài)pi的Q值由其相鄰狀態(tài)共同決定，因此使每一個(gè)原型狀態(tài)pi和動(dòng)作a維護(hù)一個(gè)θ(pi,a)，則狀態(tài)-動(dòng)作對(duì)應(yīng)的為狀態(tài)s與動(dòng)作a的相鄰原型狀態(tài)的θ值之和，具體定義如下：

當(dāng)智能體在狀態(tài)s時(shí)采取動(dòng)作a、獲得獎(jiǎng)勵(lì)r并進(jìn)入下一狀態(tài)s′時(shí)，在新的狀態(tài)下已經(jīng)選擇出了新的動(dòng)作a′，每個(gè)原型pi與動(dòng)作a維護(hù)的θ值更新規(guī)則如下：

其中：N是狀態(tài)s的相鄰原型的數(shù)量。

對(duì)于原型狀態(tài)集，Kanerva 編碼通常從整個(gè)狀態(tài)空間中隨機(jī)選擇一組初始原型開(kāi)始學(xué)習(xí)。然而，原型的選擇對(duì)Kanerva 編碼的性能有著重要影響，即估計(jì)并分配原型集對(duì)于逼近函數(shù)能力是非常敏感的，如果原型不能很好地分布在狀態(tài)空間區(qū)域中，可能造成許多輸入樣本找不到足夠的相鄰原型，這樣很難估計(jì)它們的Q值。若原型設(shè)置不合理，則會(huì)造成大量原型碰撞，使得在強(qiáng)化學(xué)習(xí)過(guò)程中遇到兩個(gè)不同的狀態(tài)動(dòng)作具有相同的隸屬度［16］。

3.2 優(yōu)化的Kanerva 編碼算法

由上文可知，每個(gè)原型狀態(tài)pi維護(hù)一個(gè)半徑為ε的接收?qǐng)?，接收?qǐng)龅拇笮》从吃蜖顟B(tài)的泛化程度。文獻(xiàn)［17］提出一種自適應(yīng)鄰接法，為每個(gè)原型接收?qǐng)稣{(diào)整大小。以該方式管理泛化能力，代替整個(gè)學(xué)習(xí)過(guò)程中的固定接收?qǐng)觯枰谠宛囸I時(shí)（接收?qǐng)鲞^(guò)小難以起到函數(shù)逼近的功能），將其與避免過(guò)度概括進(jìn)行權(quán)衡。

為進(jìn)一步提高Kanerva 的性能，本文提出一種狀態(tài)相似度機(jī)制（State Similarity Mechanism，SSM），它能夠準(zhǔn)確測(cè)量出多維連續(xù)狀態(tài)空間中的狀態(tài)相似性，并計(jì)算出輸入狀態(tài)與原型狀態(tài)的相似度等級(jí)，以此代替二進(jìn)制隸屬度，具體步驟如下：

1）定義相似距離dij(s,pi)，表示為多維狀態(tài)空間中n維輸入狀態(tài)與原型狀態(tài)p=在第j維上的差值平方除以一個(gè)恒定方差σ2，如式（10）所示：

2）對(duì)相似距離進(jìn)行歸一化處理，表示為相似度等級(jí)mij。相似度等級(jí)mij在2 個(gè)狀態(tài)變量相同時(shí)數(shù)值為1，2 個(gè)狀態(tài)變量相差很大時(shí)數(shù)值接近0，如式（11）所示：

3）在s和p的所有維度中選擇最小狀態(tài)等級(jí)作為狀態(tài)s與原型p的隸屬度μ(s,pi)，如式（12）所示：

3.3 算法步驟

將每個(gè)節(jié)點(diǎn)看作是一個(gè)獨(dú)立的智能體，智能體以當(dāng)前HELLO 報(bào)文時(shí)隙為周期感知自身所在狀態(tài)，并根據(jù)當(dāng)前狀態(tài)下的Q值選擇調(diào)整時(shí)隙的下一決策，以此進(jìn)入下一狀態(tài)，具體算法流程如下：

算法1基于Kanerva 編碼函數(shù)逼近的時(shí)隙決策

對(duì)于每個(gè)智能體，循環(huán)感知自身所在狀態(tài)，并通過(guò)上述算法做出下一步的HELLO 報(bào)文時(shí)隙調(diào)整策略，與此同時(shí)不停更新θ值，計(jì)算出新的Q值。

4 仿真結(jié)果與性能分析

實(shí)驗(yàn)選取傳統(tǒng)OLSR算法、EE-OLSR算法［7］作為本文QLA-OLSR 算法的比較對(duì)象。通過(guò)仿真實(shí)驗(yàn)對(duì)比分析各算法之間的吞吐量與網(wǎng)絡(luò)開(kāi)銷這兩個(gè)網(wǎng)絡(luò)性能指標(biāo)，根據(jù)路由算法在不同迭代次數(shù)下的性能表現(xiàn)，驗(yàn)證算法的穩(wěn)定性與收斂性。

4.1 仿真設(shè)置

實(shí)驗(yàn)采用NS2 仿真工具進(jìn)行建模仿真，將每個(gè)節(jié)點(diǎn)看作是智能體，即要求每個(gè)節(jié)點(diǎn)有相應(yīng)的計(jì)算能力。在仿真實(shí)驗(yàn)中，為方便起見(jiàn)，將每個(gè)節(jié)點(diǎn)的狀態(tài)輸入到一個(gè)智能體中，輸出各自不同的時(shí)隙結(jié)果，有利于智能體獲得更多的狀態(tài)，并且學(xué)習(xí)效果更好，如圖3 所示。

圖3 建模仿真框架Fig.3 Framework of modeling and simulation

為體現(xiàn)網(wǎng)絡(luò)拓?fù)涞母邉?dòng)態(tài)性，貼合真實(shí)情況下無(wú)人機(jī)群飛行場(chǎng)景，實(shí)驗(yàn)選用高斯馬爾科夫模型（Gauss Markov Model，GMM）模擬無(wú)人機(jī)飛行場(chǎng)景［18-20］，仿真參數(shù)設(shè)置如表2 所示。

表2 仿真參數(shù)設(shè)置Table 2 Setting of simulation parameters

4.2 性能分析

4.2.1 網(wǎng)絡(luò)動(dòng)態(tài)拓?fù)浞治?/p>

實(shí)驗(yàn)節(jié)點(diǎn)以不同速度在GMM 模型下運(yùn)動(dòng)仿真無(wú)人機(jī)飛行實(shí)際場(chǎng)景，其中以速度這一變量來(lái)直觀表示高動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涞淖兓潭龋?1］。實(shí)驗(yàn)?zāi)康氖窃谙嗤瑯I(yè)務(wù)負(fù)載下，模擬QLA-OLSR 算法在高動(dòng)態(tài)FANET 場(chǎng)景下的性能表現(xiàn)，并與EE-OLSR［7］、傳統(tǒng)OLSR 算法進(jìn)行比較，分析各協(xié)議的吞吐量與網(wǎng)絡(luò)開(kāi)銷。

無(wú)人機(jī)在不同節(jié)點(diǎn)移動(dòng)速度下的網(wǎng)絡(luò)吞吐量與網(wǎng)絡(luò)開(kāi)銷如圖4 所示，可以看出吞吐量受節(jié)點(diǎn)移動(dòng)速度的影響較大。隨著節(jié)點(diǎn)移動(dòng)速度的增加，網(wǎng)絡(luò)拓?fù)渥兓S之加快，原來(lái)穩(wěn)定的鏈路由于節(jié)點(diǎn)離開(kāi)而斷開(kāi)，新來(lái)的節(jié)點(diǎn)由于HELLO 消息時(shí)隙長(zhǎng)而未被發(fā)現(xiàn)，節(jié)點(diǎn)路由表跟不上鏈路的變化，因此網(wǎng)絡(luò)吞吐量降低。但是，在QLA-OLSR 算法中節(jié)點(diǎn)能夠更快速地感知鏈路變化，維護(hù)新的鏈路，保持較優(yōu)的吞吐量。對(duì)于網(wǎng)絡(luò)開(kāi)銷，固定時(shí)隙的OLSR 協(xié)議在相同時(shí)刻發(fā)送的HELLO 消息應(yīng)該是相近的，QLA-OLSR和EE-OLSR 算法在節(jié)點(diǎn)移動(dòng)速度增加時(shí)相應(yīng)的節(jié)點(diǎn)需減少時(shí)隙，導(dǎo)致開(kāi)銷增加，并且節(jié)點(diǎn)在感知鏈路變化的同時(shí)也會(huì)感知業(yè)務(wù)負(fù)載，低業(yè)務(wù)負(fù)載的節(jié)點(diǎn)會(huì)減少HELLO 時(shí)隙。由此可見(jiàn)，在不同節(jié)點(diǎn)移動(dòng)速度下，QLA-OLSR 算法相比OLSR 與EE-OLSR 算法具有更優(yōu)的網(wǎng)絡(luò)吞吐量和網(wǎng)絡(luò)開(kāi)銷。

圖4 不同節(jié)點(diǎn)移動(dòng)速度下的網(wǎng)絡(luò)吞吐量和網(wǎng)絡(luò)開(kāi)銷對(duì)比Fig.4 Comparison of network throughput and overhead at different node moving speeds

4.2.2 網(wǎng)絡(luò)負(fù)載分析

實(shí)驗(yàn)仿真在不同節(jié)點(diǎn)負(fù)載任務(wù)下，通過(guò)調(diào)整任務(wù)節(jié)點(diǎn)的發(fā)送數(shù)據(jù)量，分析相同節(jié)點(diǎn)移動(dòng)速度下各協(xié)議的網(wǎng)絡(luò)吞吐量與網(wǎng)絡(luò)開(kāi)銷。

無(wú)人機(jī)在不同IP 業(yè)務(wù)負(fù)載下的網(wǎng)絡(luò)吞吐量與網(wǎng)絡(luò)開(kāi)銷如圖5 所示，可以看出隨著業(yè)務(wù)負(fù)載的增加吞吐量隨之增加，但由于網(wǎng)絡(luò)容量的限制會(huì)達(dá)到峰值，但在QLA-OLSR 算法中，在不影響網(wǎng)絡(luò)性能的同時(shí)，會(huì)減少網(wǎng)絡(luò)開(kāi)銷以增加網(wǎng)絡(luò)容量，因此峰值會(huì)在更靠后時(shí)刻到來(lái)。關(guān)于網(wǎng)絡(luò)開(kāi)銷，OLSR 和EE-OLSR算法對(duì)于業(yè)務(wù)負(fù)載不形成依賴，因此它們的網(wǎng)絡(luò)開(kāi)銷變化不明顯，但QLA-OLSR 算法在高業(yè)務(wù)負(fù)載時(shí)會(huì)更傾向于發(fā)送業(yè)務(wù)數(shù)據(jù)包，從而通過(guò)增加時(shí)隙來(lái)減少HELLO 消息的發(fā)送。由此可見(jiàn)，在不同節(jié)點(diǎn)業(yè)務(wù)負(fù)載下，QLA-OLSR 算法相比OLSR 與EE-OLSR協(xié)議具有更優(yōu)的網(wǎng)絡(luò)吞吐量和網(wǎng)絡(luò)開(kāi)銷。

圖5 不同IP 業(yè)務(wù)負(fù)載下的網(wǎng)絡(luò)吞吐量和網(wǎng)絡(luò)開(kāi)銷對(duì)比Fig.5 Comparison of network throughput and overhead at different IP business loads

4.2.3 算法性能分析

強(qiáng)化學(xué)習(xí)算法是通過(guò)學(xué)習(xí)過(guò)往經(jīng)驗(yàn)來(lái)優(yōu)化當(dāng)前動(dòng)作，當(dāng)算法穩(wěn)定后節(jié)點(diǎn)只需查找Q值來(lái)對(duì)下一動(dòng)作進(jìn)行選擇。Kanerva 編碼方式可優(yōu)化網(wǎng)絡(luò)狀態(tài)空間，加快算法收斂，提高算法效率。為驗(yàn)證Kanerva編碼方式的優(yōu)化效果，實(shí)驗(yàn)給出了QLA-OLSR 算法的網(wǎng)絡(luò)性能隨迭代次數(shù)的變化情況。

如表3 所示，在選定節(jié)點(diǎn)移動(dòng)速度為100 m/s、IP業(yè)務(wù)負(fù)載為50 kb/s 的場(chǎng)景下，QLA-OLSR 算法初始時(shí)的性能表現(xiàn)并不好，此時(shí)算法隨機(jī)性較大，但隨著學(xué)習(xí)迭代次數(shù)的增加，吞吐量開(kāi)始逐步上升，網(wǎng)絡(luò)開(kāi)銷亦逐步下降，當(dāng)?shù)揭欢ù螖?shù)時(shí)逐步趨于穩(wěn)定，在沒(méi)有較大網(wǎng)絡(luò)波動(dòng)下算法收斂，可見(jiàn)QLA-OLSR算法具有較好的適應(yīng)性。

表3 QLA-OLSR 算法性能隨迭代次數(shù)的變化情況Table 3 The changes of QLA-OLSR algorithm performance with the number of iterations

5 結(jié)束語(yǔ)

本文提出一種基于強(qiáng)化學(xué)習(xí)的自適應(yīng)鏈路狀態(tài)路由算法QLA-OLSR，利用強(qiáng)化學(xué)習(xí)算法對(duì)傳統(tǒng)OLSR 協(xié)議的HELLO 時(shí)隙算法進(jìn)行優(yōu)化，使得節(jié)點(diǎn)對(duì)環(huán)境有認(rèn)知能力，并采用最大回報(bào)的方式選擇調(diào)整時(shí)隙的決策。仿真結(jié)果表明：相比傳統(tǒng)OLSR、EE-OLSR 算法，QLA-OLSR 算法在高動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)鋱?chǎng)景下能夠更快適應(yīng)環(huán)境，具有更高的吞吐量和更低的丟包率；在平穩(wěn)的網(wǎng)絡(luò)拓?fù)鋱?chǎng)景下，在保持較高網(wǎng)絡(luò)吞吐量的同時(shí)，降低了網(wǎng)絡(luò)開(kāi)銷，為環(huán)境多變的FANET 通信提供了有效的解決方案。但由于拓?fù)淇刂品纸M傳輸也是影響QLA-OLSR 算法性能的重要因素，因此后續(xù)將優(yōu)化拓?fù)淇刂品纸M發(fā)送方式，并在時(shí)隙算法中考慮無(wú)人機(jī)在實(shí)際場(chǎng)景中節(jié)點(diǎn)能量受限這一因素，進(jìn)一步提升網(wǎng)絡(luò)性能。