王柄焱，鄭向平，賈文杰，李大鵬

（1.南京郵電大學(xué)通信與信息工程學(xué)院，江蘇 南京 210003；2.江蘇永豐機(jī)械有限責(zé)任公司，江蘇 南京 210094；3.重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054）

0 引言

移動(dòng)自組網(wǎng)（Mobile Ad Hoc Networks，MANET）是一種自組織、無(wú)中心、多跳傳輸?shù)臒o(wú)線網(wǎng)絡(luò)，與傳統(tǒng)中心控制的無(wú)線網(wǎng)絡(luò)相比，移動(dòng)自組網(wǎng)不依賴任何中央基礎(chǔ)設(shè)施，可以實(shí)現(xiàn)低成本，快速的網(wǎng)絡(luò)部署，同時(shí)也便于擴(kuò)展和維護(hù)，近年來(lái)得到了廣泛的應(yīng)用[1-2]。無(wú)人機(jī)自組網(wǎng)（Unmanned Aerial Vehicles Ad Hoc Networks,UANET）是MANET 在無(wú)人機(jī)領(lǐng)域的擴(kuò)展應(yīng)用，有動(dòng)態(tài)性高、鏈路長(zhǎng)、資源有限、數(shù)據(jù)交互頻繁的特點(diǎn)，這給執(zhí)行任務(wù)帶來(lái)了多樣性與靈活性，但也給路由協(xié)議的設(shè)計(jì)帶來(lái)了很大的挑戰(zhàn)[3-5]。

目前，OLSR（Optimized Link State Routing）協(xié)議是應(yīng)用比較廣泛的主動(dòng)式路由協(xié)議[6]，相比于以AODV（Ad hoc On-Demand Distance Vector Routing）為代表的被動(dòng)式路由協(xié)議，OLSR 協(xié)議中的節(jié)點(diǎn)會(huì)周期性地交互路由測(cè)度信息，更新路由表，當(dāng)要發(fā)送業(yè)務(wù)時(shí)，可以直接查詢已經(jīng)建立的路由，而被動(dòng)式路由協(xié)議采用的是一種有業(yè)務(wù)發(fā)送時(shí)才開啟路由建立的執(zhí)行方式，所以，在對(duì)實(shí)時(shí)性要求較高的無(wú)人機(jī)網(wǎng)絡(luò)場(chǎng)景中，OLSR 協(xié)議更有優(yōu)勢(shì)[7]。

OLSR 協(xié)議中的節(jié)點(diǎn)通過(guò)廣播Hello 分組來(lái)完成鏈路探測(cè)與鄰居發(fā)現(xiàn)，通過(guò)廣播拓?fù)淇刂疲═C,Topology Control）分組來(lái)共享網(wǎng)絡(luò)拓?fù)湫畔ⅲ瑫r(shí)通過(guò)多點(diǎn)中繼技術(shù)（MPR,Multi-Point Relay），在一定程度上減少了路由維護(hù)開銷[8-10]。但傳統(tǒng)的OLSR 協(xié)議僅使用跳數(shù)作為路由的決策準(zhǔn)則，選擇的標(biāo)準(zhǔn)過(guò)于單一，難以適應(yīng)真實(shí)的UANET 場(chǎng)景。

針對(duì)網(wǎng)絡(luò)拓?fù)渥兓l繁的場(chǎng)景，王旭東等人[11]提出了一種基于位置信息的速度加權(quán)SW-OLSR 協(xié)議，通過(guò)預(yù)估計(jì)算一個(gè)ETX 值來(lái)度量無(wú)線鏈路的鏈路質(zhì)量，進(jìn)而輔助路由決策。周長(zhǎng)家等人[12]針對(duì)UANET 的動(dòng)態(tài)性和能量受限的特點(diǎn)提出了一種適用于UANET 的UAV-OLSR協(xié)議，通過(guò)感知在發(fā)送Hello 消息間隔內(nèi)的鄰居變動(dòng)狀況以及發(fā)送TC 消息間隔內(nèi)的拓?fù)渥儎?dòng)狀況動(dòng)態(tài)調(diào)整兩種控制信息的發(fā)送周期，同時(shí)通過(guò)評(píng)估節(jié)點(diǎn)能量?jī)?yōu)化了MPR機(jī)制；姚玉坤等人[13]提出在選取MPR 節(jié)點(diǎn)集時(shí)，加入鏈路穩(wěn)定性和鏈路存在時(shí)間這兩個(gè)鏈路狀態(tài)指標(biāo)，使得選取的MPR 節(jié)點(diǎn)集更穩(wěn)定、合理，同時(shí)結(jié)合Q-learning算法實(shí)現(xiàn)了對(duì)TC 消息發(fā)送間隔的動(dòng)態(tài)調(diào)整，在一定程度上降低了路由控制開銷。實(shí)際上，上述改進(jìn)協(xié)議都針對(duì)運(yùn)動(dòng)拓?fù)鋵?duì)OLSR 協(xié)議進(jìn)行了優(yōu)化，但缺少對(duì)節(jié)點(diǎn)負(fù)載的考量。王靖等人[14]采用跨層協(xié)議設(shè)計(jì)理論，通過(guò)對(duì)節(jié)點(diǎn)負(fù)載、鏈路投遞率和鏈路可用性等信息進(jìn)行感知，并以此為依據(jù)來(lái)推理鏈路質(zhì)量，進(jìn)一步優(yōu)化了路由選擇，保證了網(wǎng)絡(luò)的負(fù)載均衡，有效地提高了協(xié)議的可靠性。但該協(xié)議引入了較大的控制開銷，難以適用于節(jié)點(diǎn)能量有限的UANET。

針對(duì)OLSR 協(xié)議路由選擇指標(biāo)單一的問(wèn)題，本文提出了在無(wú)人機(jī)自組網(wǎng)場(chǎng)景中，基于鏈路質(zhì)量與節(jié)點(diǎn)負(fù)載估計(jì)的Q 學(xué)習(xí)OLSR 協(xié)議（UQL-OLSR,Q-learning OLSR Based on Link Quality and Node Load Estimation for UANET），主要內(nèi)容包括：1）針對(duì)高動(dòng)態(tài)和高吞吐兩種網(wǎng)絡(luò)場(chǎng)景，分別定義了鏈路質(zhì)量和節(jié)點(diǎn)負(fù)載兩個(gè)參數(shù)，并提供了相應(yīng)的估計(jì)方法；2）基于Q 學(xué)習(xí)算法，結(jié)合OLSR 協(xié)議控制信息的交互過(guò)程，設(shè)計(jì)了基于跳數(shù)、鏈路質(zhì)量、節(jié)點(diǎn)負(fù)載三方面的獎(jiǎng)勵(lì)函數(shù)，并提供了路由建立過(guò)程中Q 值表與路由表的更新方法，用于指導(dǎo)在多因素影響下的路由決策。該協(xié)議已在某網(wǎng)絡(luò)仿真環(huán)境中實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的協(xié)議更加適用于高動(dòng)態(tài)、高負(fù)載環(huán)境下的無(wú)人機(jī)自組網(wǎng)。

1 系統(tǒng)模型與問(wèn)題分析

1.1 系統(tǒng)模型

本文使用Q 學(xué)習(xí)算法對(duì)OLSR 協(xié)議在UANET 場(chǎng)景下的路由選擇與路由建立過(guò)程建立模型。Q 學(xué)習(xí)是一種基于值函數(shù)的無(wú)模型強(qiáng)化學(xué)習(xí)（Reinforcement Learning,RL）算法[15]，它能夠?qū)W(xué)習(xí)任務(wù)分散到每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)中，通過(guò)周期性的與鄰居交互控制信息來(lái)動(dòng)態(tài)更新路由表，這意味著網(wǎng)絡(luò)中的節(jié)點(diǎn)可以根據(jù)它們的互動(dòng)經(jīng)驗(yàn)不斷改善路由決策，以提高網(wǎng)絡(luò)性能和可靠性。這種方法有助于優(yōu)化數(shù)據(jù)傳輸，使網(wǎng)絡(luò)更有效地工作。

圖1 為Q 學(xué)習(xí)的基本模型，以馬爾可夫決策過(guò)程（Markov Decision Process，MDP）為理論基礎(chǔ)。在MDP 中，智能體（Agent）處于一個(gè)由狀態(tài)（State）、動(dòng)作（Action）和獎(jiǎng)勵(lì)（Reward）組成的環(huán)境中，假設(shè)在t時(shí)刻智能體的狀態(tài)為St，在收到基于上一次動(dòng)作環(huán)境反饋的獎(jiǎng)勵(lì)值Rt之后，經(jīng)過(guò)決策執(zhí)行最優(yōu)動(dòng)作At并進(jìn)入狀態(tài)St+1，智能體循環(huán)執(zhí)行以上操作，經(jīng)過(guò)了動(dòng)作帶來(lái)獎(jiǎng)勵(lì)后又反過(guò)來(lái)影響動(dòng)作決策的過(guò)程，以達(dá)到在特定的環(huán)境中選擇最優(yōu)決策的問(wèn)題[16]。

圖1 Q學(xué)習(xí)的基本模型

Q 學(xué)習(xí)算法通過(guò)Q 值來(lái)評(píng)估狀態(tài)行動(dòng)的價(jià)值，其中Q 值的更新規(guī)則如下：

式中Q(st,at) 是狀態(tài)-動(dòng)作對(duì)(s,a) 的值函數(shù)，表示在狀態(tài)s下采取動(dòng)作a所能獲得的獎(jiǎng)勵(lì)期望，α∈(0,1)為學(xué)習(xí)率，用于控制學(xué)習(xí)的速度，γ∈(0,1)為折扣因子，用于控制長(zhǎng)期獎(jiǎng)勵(lì)的重要性。

為了讓網(wǎng)絡(luò)中的節(jié)點(diǎn)能夠自主學(xué)習(xí)，及時(shí)感知拓?fù)浣Y(jié)構(gòu)與節(jié)點(diǎn)狀態(tài)，將Q 學(xué)習(xí)算法與OLSR 協(xié)議結(jié)合，定義智能體Agent 為網(wǎng)絡(luò)中的節(jié)點(diǎn)，學(xué)習(xí)環(huán)境為整個(gè)UANET。

定義三元組（A,S,R）如下：

1）動(dòng)作（A）：節(jié)點(diǎn)通過(guò)感知鄰居與拓?fù)渥兓?，新增或更新本地路由表?xiàng)，從一跳鄰居集N={N1,N2,…,Nn}中選取一個(gè)節(jié)點(diǎn)作為相應(yīng)目的的下一跳。

2）狀態(tài)（S）：節(jié)點(diǎn)的本地路由信息及狀態(tài)統(tǒng)計(jì)信息，包括跳數(shù)hop、節(jié)點(diǎn)地理位置 (x,y)、數(shù)據(jù)接收速率R等，反應(yīng)節(jié)點(diǎn)當(dāng)前的情況，用于指導(dǎo)路由決策。

3）獎(jiǎng)勵(lì)（R）：整個(gè)網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)的即時(shí)反饋值，可以根據(jù)網(wǎng)絡(luò)性能的需求，將跳數(shù)、時(shí)延、負(fù)載、能耗等指標(biāo)映射到獎(jiǎng)勵(lì)R中，使節(jié)點(diǎn)能夠適應(yīng)動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境。

在路由建立過(guò)程中，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都維護(hù)一張Q 值表，表中的列表示經(jīng)過(guò)本節(jié)點(diǎn)的目的節(jié)點(diǎn)ID，行表示本節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)ID，用來(lái)記錄當(dāng)前節(jié)點(diǎn)在指定目的節(jié)點(diǎn)的情況下，選擇某個(gè)鄰居節(jié)點(diǎn)作為下一跳可以得到的累積獎(jiǎng)勵(lì)期望值，節(jié)點(diǎn)會(huì)選擇Q 值最大的鄰居作為下一跳節(jié)點(diǎn)。Q 值表的具體格式如表1 所示。

表1 節(jié)點(diǎn)維護(hù)的Q值表格式

基于該路由策略，參考公式(1)，以D作為目的節(jié)點(diǎn)，源節(jié)點(diǎn)S將鄰居節(jié)點(diǎn)N作為下一跳的質(zhì)量評(píng)估值，即對(duì)應(yīng)Q 值的更新公式變?yōu)椋?/p>

其中α為學(xué)習(xí)率，γ為折扣因子，Ns為源節(jié)點(diǎn)S 的一跳鄰居集。

Q 學(xué)習(xí)作為一種無(wú)模型算法，其復(fù)雜度可以表示為O(SAH)，其中S表示狀態(tài)空間的大小，A表示動(dòng)作空間的大小，H表示每一次執(zhí)行所走的步長(zhǎng)[17]。S的大小受到網(wǎng)絡(luò)規(guī)模的影響，節(jié)點(diǎn)越多，需要統(tǒng)計(jì)的狀態(tài)參量相應(yīng)增加；A的大小則與網(wǎng)絡(luò)節(jié)點(diǎn)的一跳鄰居集大小相關(guān)，具體的，節(jié)點(diǎn)可供選擇的下一跳節(jié)點(diǎn)數(shù)量越多，動(dòng)作空間越大；同時(shí)，由于每次執(zhí)行動(dòng)作只會(huì)新增或更新一行路由表項(xiàng)，因此步長(zhǎng)H可視為1。綜上，通過(guò)Q 學(xué)習(xí)實(shí)現(xiàn)路由建立的復(fù)雜度受到網(wǎng)絡(luò)規(guī)模與節(jié)點(diǎn)密集程度的影響，設(shè)置合理的節(jié)點(diǎn)總數(shù)與拓?fù)浣Y(jié)構(gòu)可以顯著降低算法的復(fù)雜度。

1.2 問(wèn)題分析

傳統(tǒng)的OLSR 協(xié)議僅基于跳數(shù)，使用Dijkstra 算法計(jì)算路徑，生成路由。選擇路由的標(biāo)準(zhǔn)過(guò)于單一，難以適應(yīng)網(wǎng)絡(luò)拓?fù)涞目焖僮兓瑫?huì)導(dǎo)致鏈路易斷裂，路由更新不及時(shí)等問(wèn)題[18]，同時(shí)，在業(yè)務(wù)量較大的場(chǎng)景中，MPR 節(jié)點(diǎn)的負(fù)載加重，業(yè)務(wù)發(fā)生擁塞的可能性增加，進(jìn)而也會(huì)降低網(wǎng)絡(luò)的性能[19]，因此：

1）考慮到無(wú)人機(jī)節(jié)點(diǎn)的移動(dòng)性：在制定路由轉(zhuǎn)發(fā)策略時(shí)，選擇質(zhì)量更高，穩(wěn)定性更好的下一跳節(jié)點(diǎn)，能夠延長(zhǎng)路徑生存時(shí)間，減少鏈路斷裂，提高路由質(zhì)量和數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

2）考慮到高負(fù)載情況下的數(shù)據(jù)擁塞問(wèn)題：在路由選擇時(shí)，選擇負(fù)載較小，空閑度較大的轉(zhuǎn)發(fā)節(jié)點(diǎn)可以減少這種問(wèn)題的發(fā)生，降低網(wǎng)絡(luò)的時(shí)延[20]。

綜合考慮以上2 個(gè)問(wèn)題，同時(shí)也保留對(duì)跳數(shù)的考量，定義跳數(shù)因子HF、鏈路質(zhì)量因子QF和節(jié)點(diǎn)空閑度因子LF，共同構(gòu)成Q 學(xué)習(xí)中對(duì)節(jié)點(diǎn)的即時(shí)獎(jiǎng)勵(lì)R（獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)見2.1 節(jié)），用于指導(dǎo)節(jié)點(diǎn)在多因素影響下的路由決策。

2 基于鏈路質(zhì)量與節(jié)點(diǎn)負(fù)載估計(jì)的Q學(xué)習(xí)路由協(xié)議

2.1 獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)

（1）最小跳數(shù)

在OLSR 協(xié)議中，采用Dijkstra 算法計(jì)算路由最小跳數(shù)，以節(jié)點(diǎn)i為例，每個(gè)節(jié)點(diǎn)獲取其到達(dá)其他節(jié)點(diǎn)的最小跳數(shù)的核心步驟如下：

①節(jié)點(diǎn)通過(guò)交互Hello 分組和TC 分組分別維護(hù)一個(gè)鄰居表和一個(gè)拓?fù)浔恚?/p>

②根據(jù)拓?fù)浔碇械谋眄?xiàng)初始化節(jié)點(diǎn)i中的一個(gè)二維數(shù)組min_h，其中min_h[i][j]表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的最小跳數(shù)；

③節(jié)點(diǎn)i找到未訪問(wèn)節(jié)點(diǎn)中離本節(jié)點(diǎn)最近（跳數(shù)最?。┑墓?jié)點(diǎn)ni，判斷節(jié)點(diǎn)ni是否可以使得節(jié)點(diǎn)i到其他所有節(jié)點(diǎn)的跳數(shù)變小，若滿足，更新min_h；

④節(jié)點(diǎn)i根據(jù)二維數(shù)組min_h記錄到其他節(jié)點(diǎn)的最小跳數(shù)hopmin；

⑤重復(fù)③④直到網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都獲取到達(dá)其他節(jié)點(diǎn)的最小跳數(shù)。

定義跳數(shù)因子HF 如下：

其中hopmin為通過(guò)Dijkstra 算法計(jì)算的路由最小跳數(shù)，hopmax為路由最大跳數(shù)，默認(rèn)為16。

（2）鏈路質(zhì)量

定義鏈路質(zhì)量因子QF來(lái)估計(jì)兩節(jié)點(diǎn)之間的鏈路質(zhì)量。

定義t時(shí)刻，節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的直線距離為：

其中節(jié)點(diǎn)i的地理位置為，節(jié)點(diǎn)j的地理位置為。

在時(shí)間間隔T內(nèi)，兩個(gè)節(jié)點(diǎn)的相對(duì)移動(dòng)距離如下：

定義節(jié)點(diǎn)i相對(duì)于節(jié)點(diǎn)j的質(zhì)量因子為：

其中，Rd為無(wú)人機(jī)節(jié)點(diǎn)的最大通信距離，單位時(shí)間內(nèi)兩節(jié)點(diǎn)相對(duì)移動(dòng)距離越小，則認(rèn)為兩節(jié)點(diǎn)間的鏈路質(zhì)量越好。

為了避免在節(jié)點(diǎn)劇烈運(yùn)動(dòng)的場(chǎng)景下，節(jié)點(diǎn)相對(duì)移動(dòng)距離Δd變化過(guò)大，進(jìn)而導(dǎo)致質(zhì)量因子QF劇烈變動(dòng)的情況，使用指數(shù)移動(dòng)平均（EMA）對(duì)鏈路質(zhì)量因子做平滑處理：

其中，β∈(0,1)，為平滑因子，表示當(dāng)前數(shù)據(jù)點(diǎn)的權(quán)重，經(jīng)過(guò)仿真測(cè)試，本文β取0.75。

（3）節(jié)點(diǎn)負(fù)載

借用文獻(xiàn)[20] 中使用網(wǎng)絡(luò)節(jié)點(diǎn)內(nèi)數(shù)據(jù)包的排隊(duì)時(shí)延來(lái)評(píng)估節(jié)點(diǎn)負(fù)載的思路，采用M/M/1 排隊(duì)模型對(duì)網(wǎng)絡(luò)層隊(duì)列進(jìn)行建模，網(wǎng)絡(luò)層隊(duì)列中數(shù)據(jù)包數(shù)量的期望值為：

其中，pi表示隊(duì)列中數(shù)據(jù)包個(gè)數(shù)為i的概率，λ表示節(jié)點(diǎn)接收數(shù)據(jù)包的速率，μ表示節(jié)點(diǎn)處理數(shù)據(jù)包的速率。

進(jìn)一步，數(shù)據(jù)包的平均排隊(duì)時(shí)延為：

這樣在每個(gè)節(jié)點(diǎn)處理數(shù)據(jù)包的速率μ一定的情況下，節(jié)點(diǎn)接收數(shù)據(jù)包的速率越大，則數(shù)據(jù)包的排隊(duì)時(shí)延越長(zhǎng)，此節(jié)點(diǎn)的負(fù)載越高。因此，可以使用節(jié)點(diǎn)接收速率λ來(lái)衡量網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)載量。定義網(wǎng)絡(luò)中某節(jié)點(diǎn)相對(duì)于其鄰居節(jié)點(diǎn)i的空閑度因子估計(jì)值如下：

其中Ri為鄰居節(jié)點(diǎn)i的瞬時(shí)接收速率，Rmax為該節(jié)點(diǎn)所有鄰居接收速率的最大值。

（4）獎(jiǎng)勵(lì)函數(shù)

根據(jù)前文對(duì)節(jié)點(diǎn)跳數(shù)因子、質(zhì)量因子、空閑度因子的定義可知，HF∈[0,1]，QF∈[0,1]，LF∈[0,1]，定義當(dāng)前節(jié)點(diǎn)c從節(jié)點(diǎn)i獲取的瞬時(shí)獎(jiǎng)勵(lì)R(c,i)為：

其中：ωH，ωQ和ωL分別為路徑跳數(shù)、鏈路質(zhì)量、節(jié)點(diǎn)空閑度的權(quán)重因子，滿足ωH+ωQ+ωL=1。

2.2 路由方案設(shè)計(jì)

（1）路由建立過(guò)程

在路由建立的過(guò)程中，每個(gè)節(jié)點(diǎn)都會(huì)周期性廣播Hello 分組用于探測(cè)鄰居節(jié)點(diǎn)，為了判斷應(yīng)該轉(zhuǎn)發(fā)來(lái)自哪些節(jié)點(diǎn)的廣播消息，節(jié)點(diǎn)會(huì)在本地維護(hù)一張MPR_S（MPR Selector）集合。節(jié)點(diǎn)將MPR_S 集合中的信息加入TC分組后，向全網(wǎng)洪泛TC 分組用于交互網(wǎng)絡(luò)的拓?fù)湫畔?，由MPR 節(jié)點(diǎn)進(jìn)行處理和轉(zhuǎn)發(fā)，參考1.1 節(jié)中對(duì)Q 表的定義，網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)交互Hello 和TC 分組維護(hù)一張Q值表，更新路由時(shí)，選擇Q 值最大的鄰居節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，無(wú)人機(jī)節(jié)點(diǎn)維護(hù)Q 表的示意圖如圖2 所示：

圖2 無(wú)人機(jī)節(jié)點(diǎn)維護(hù)Q表示意圖

為了計(jì)算本節(jié)點(diǎn)到對(duì)應(yīng)目的節(jié)點(diǎn)的Q 值，節(jié)點(diǎn)首先會(huì)收集并計(jì)算本地路由與狀態(tài)測(cè)度信息，再將這些信息添加到Hello 分組中，并定期地將這些數(shù)據(jù)共享給鄰居節(jié)點(diǎn)，MPR 節(jié)點(diǎn)接收到鄰居的測(cè)度信息后，會(huì)將這些信息添加到TC 分組中，向全網(wǎng)廣播。在開始階段，每個(gè)節(jié)點(diǎn)Q 表的初始值都設(shè)為0，當(dāng)節(jié)點(diǎn)接收到鄰居節(jié)點(diǎn)發(fā)送來(lái)的TC 分組后，將在本地維護(hù)一個(gè)拓?fù)浔?，提取其中記錄的目的地址Dt、TC 分組中的上一跳地址Pt、節(jié)點(diǎn)地理位置、接收速率等相關(guān)信息，按照公式(11) 計(jì)算獎(jiǎng)勵(lì)值R，然后將Dt作為Q 值參數(shù)的目的節(jié)點(diǎn)Di，Pt作為鄰居節(jié)點(diǎn)Ni，按公式(2) 更新本地Q 值表。經(jīng)過(guò)這一過(guò)程，就更新了當(dāng)前節(jié)點(diǎn)以MPR_S 集合中的節(jié)點(diǎn)為目的，上一跳節(jié)點(diǎn)為鄰居的Q 值。更新完成后，如果當(dāng)前節(jié)點(diǎn)是MPR 節(jié)點(diǎn)，則將上一跳地址設(shè)為自己，再以單跳廣播的方式向全網(wǎng)轉(zhuǎn)發(fā)該TC 分組。同理，收到其他鄰居節(jié)點(diǎn)發(fā)來(lái)的TC 分組也如此處理，經(jīng)過(guò)一段時(shí)間的算法收斂，以全網(wǎng)中其他節(jié)點(diǎn)為目的的Q 值都得到更新。

UQL-OLSR 協(xié)議的路由建立流程如圖3 所示。

圖3 UQL-OLSR協(xié)議路由建立流程

（2）路由維護(hù)過(guò)程

在路由建立的過(guò)程中，為了應(yīng)對(duì)高動(dòng)態(tài)場(chǎng)景中節(jié)點(diǎn)入網(wǎng)，退網(wǎng)的場(chǎng)景，制定了Q 值表中節(jié)點(diǎn)的有效時(shí)間，在這個(gè)有效時(shí)間內(nèi)，如果某個(gè)節(jié)點(diǎn)的Q 值沒(méi)有被更新，系統(tǒng)會(huì)將該目的節(jié)點(diǎn)視為下線，并清除相應(yīng)行的數(shù)據(jù)。同時(shí)，需要根據(jù)網(wǎng)絡(luò)規(guī)模設(shè)置TC 報(bào)文的生存時(shí)間（TTL），在確保全網(wǎng)能夠感知拓?fù)湫畔⒌那闆r下，減少控制信息的冗余。

由于Q 學(xué)習(xí)算法需要需要一定時(shí)間才能收斂，在當(dāng)前節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的Q 值都收斂時(shí)，更新后的路由才能逐漸趨近最佳。然而，在更新路由表時(shí)，Q 值可能與穩(wěn)態(tài)值存在較大偏差。為了盡快達(dá)到Q 值收斂，特別是在動(dòng)態(tài)性較高的網(wǎng)絡(luò)中，需要適度降低Hello 報(bào)文和TC報(bào)文的發(fā)送間隔，以促進(jìn)Q 值的快速更新。同時(shí)為了減少控制信息在網(wǎng)絡(luò)中的競(jìng)爭(zhēng)和碰撞，實(shí)驗(yàn)過(guò)程中設(shè)定控制信息的發(fā)送時(shí)延為γT,其中γ為[0,1] 之間的隨機(jī)數(shù)，T為控制報(bào)文的發(fā)送間隔，每個(gè)節(jié)點(diǎn)錯(cuò)開控制信息的發(fā)送時(shí)間，確保網(wǎng)絡(luò)中的消息傳輸更均勻，保證在路由建立過(guò)程中控制信息的接收速率和占用的帶寬基本保持恒定。

3 仿真與分析

本文使用某網(wǎng)絡(luò)仿真平臺(tái)對(duì)UQL-OLSR 協(xié)議進(jìn)行仿真驗(yàn)證，將其與集成的標(biāo)準(zhǔn)版OLSR 協(xié)議以及文獻(xiàn)[11]中的基于位置信息的速度加權(quán)OLSR 協(xié)議（SW-OLSR）進(jìn)行對(duì)比分析，并分別設(shè)計(jì)了如下仿真實(shí)驗(yàn)：

1）預(yù)估UQL-OLSR 協(xié)議的路由建立時(shí)間，通過(guò)獲得業(yè)務(wù)源節(jié)點(diǎn)本地Q 表中最大Q 值的收斂時(shí)間來(lái)估計(jì)；

2）驗(yàn)證節(jié)點(diǎn)吞吐量一致的情況下，網(wǎng)絡(luò)拓?fù)渥兓l繁程度對(duì)時(shí)延和分組投遞率的影響；

3）驗(yàn)證網(wǎng)絡(luò)拓?fù)渥兓潭纫恢碌那闆r下，節(jié)點(diǎn)吞吐量的變化對(duì)時(shí)延和分組投遞率的影響。

實(shí)驗(yàn)中設(shè)置最小跳數(shù)、鏈路穩(wěn)定性和節(jié)點(diǎn)空閑度的權(quán)重因子分別為0.3、0.4 和0.3，場(chǎng)景規(guī)模為2 km×2 km；節(jié)點(diǎn)的移動(dòng)方式采用隨機(jī)移動(dòng)（Random WayPoint），整體實(shí)驗(yàn)仿真參數(shù)如表2 所示：

表2 仿真參數(shù)配置

3.1 路由建立時(shí)間分析

在2.2 節(jié)中提到，只有當(dāng)節(jié)點(diǎn)的Q 值都達(dá)到收斂狀態(tài)時(shí)，更新后的路由才會(huì)逐漸接近最佳路由，所以為了評(píng)估UQLOLSR 協(xié)議的性能，需要保證在傳輸業(yè)務(wù)數(shù)據(jù)時(shí)，節(jié)點(diǎn)維護(hù)的Q 值都達(dá)到收斂狀態(tài)。在路由選擇時(shí)，節(jié)點(diǎn)選擇Q 值最大的鄰居作為下一跳節(jié)點(diǎn)，因此可以通過(guò)最大Q 值的收斂時(shí)間來(lái)預(yù)估學(xué)習(xí)過(guò)程的收斂時(shí)間和路由建立的時(shí)間。

設(shè)置場(chǎng)景中節(jié)點(diǎn)的最大移動(dòng)速度為5 m/s，設(shè)置5 條端到端業(yè)務(wù)，發(fā)送速率為4 kbps，隨機(jī)選取實(shí)驗(yàn)場(chǎng)景中的一條端到端業(yè)務(wù)，源節(jié)點(diǎn)的Qmax值隨仿真時(shí)間的收斂過(guò)程如圖4 所示。

圖4 源節(jié)點(diǎn)Qmax隨仿真時(shí)間的變化情況

在仿真的開始階段，Qmax增加迅速，隨著時(shí)間的增加增幅逐漸變緩，并在20 s 左右趨于穩(wěn)定，這說(shuō)明在協(xié)議運(yùn)行期間，源節(jié)點(diǎn)從網(wǎng)絡(luò)中學(xué)習(xí)最小跳數(shù)、網(wǎng)絡(luò)拓?fù)渥兓闆r以及鏈路空閑程度信息，這些信息最終反應(yīng)在Q值的大小上。隨著節(jié)點(diǎn)的運(yùn)動(dòng)和網(wǎng)絡(luò)中業(yè)務(wù)負(fù)載的變化，Qmax也可能小幅度波動(dòng)，但不會(huì)像路由建立初期那樣劇烈變化?？梢哉J(rèn)為，在按照表2 配置的仿真參數(shù)下，路由建立的時(shí)間為20 s 左右，因此為了避免誤差，業(yè)務(wù)數(shù)據(jù)的傳輸應(yīng)該設(shè)置在網(wǎng)絡(luò)啟動(dòng)運(yùn)行20 s 之后。

3.2 性能分析

為了測(cè)試網(wǎng)絡(luò)拓?fù)溥\(yùn)動(dòng)的劇烈程度對(duì)協(xié)議性能的影響，設(shè)置業(yè)務(wù)源節(jié)點(diǎn)的發(fā)送速率一致，均為4 kbps。無(wú)人機(jī)最大移動(dòng)速度在0～25 m/s 時(shí)的端到端時(shí)延和分組投遞率變化情況分別如圖5 和圖6 所示，可以看到，節(jié)點(diǎn)的移動(dòng)速度越快，端到端時(shí)延逐漸增加，分組投遞率逐漸降低，在無(wú)人機(jī)移動(dòng)速度較低時(shí)，拓?fù)浣Y(jié)構(gòu)的變化不大，三種協(xié)議的端到端時(shí)延和分組投遞率基本保持一致，當(dāng)無(wú)人機(jī)最大速度上升到25 m/s 時(shí)，SW-OLSR 通過(guò)引入速度加權(quán)的ETX 和節(jié)點(diǎn)位置信息，UQL-OLSR 通過(guò)加入對(duì)鏈路質(zhì)量和節(jié)點(diǎn)負(fù)載的評(píng)估和Q-learning 獎(jiǎng)勵(lì)機(jī)制，在時(shí)延上相比OLSR 分別降低了9.8% 和13.5%，在分組投遞率上分別提高了46.2%和51.8%。兩種優(yōu)化OLSR 協(xié)議都考慮了拓?fù)浣Y(jié)構(gòu)變化對(duì)數(shù)據(jù)傳輸?shù)挠绊?，能夠選擇穩(wěn)定性更高的下一跳節(jié)點(diǎn)，減少了網(wǎng)絡(luò)中鏈路斷裂的情況。

圖6 分組投遞率隨節(jié)點(diǎn)移動(dòng)速度的變化情況

同時(shí)，為了測(cè)試節(jié)點(diǎn)吞吐量對(duì)協(xié)議性能的影響，統(tǒng)一設(shè)置節(jié)點(diǎn)的最大移動(dòng)速度為5 m/s，在場(chǎng)景中隨機(jī)添加5 條端到端業(yè)務(wù)，統(tǒng)計(jì)業(yè)務(wù)速率在100 kbps～500 kbps 下的端到端時(shí)延和分組投遞率變化情況。如圖7 和圖8 所示，隨著業(yè)務(wù)速率的提高，網(wǎng)絡(luò)中的節(jié)點(diǎn)負(fù)載增加，端到端時(shí)延提高，分組投遞率降低。同樣，發(fā)送速率較低時(shí)三種協(xié)議的端到端時(shí)延和分組投遞率沒(méi)有明顯區(qū)別，但當(dāng)發(fā)送速率相對(duì)較大，為500 kbps 時(shí)，SW-OLSR 協(xié)議由于考慮了無(wú)人機(jī)節(jié)點(diǎn)運(yùn)動(dòng)的因素，在時(shí)延和分組投遞率上分別進(jìn)步了17.0% 和21.2%，但UQL-OLSR 協(xié)議同時(shí)還考慮了節(jié)點(diǎn)鄰居的負(fù)載程度，優(yōu)先選擇負(fù)載較小的下一跳鄰居，因此，在業(yè)務(wù)速率較大的場(chǎng)景下，時(shí)延和分組投遞率進(jìn)一步優(yōu)化了7.4% 和12.1%。

圖8 分組投遞率隨業(yè)務(wù)發(fā)送速率的變化情況

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

傳統(tǒng)OLSR 協(xié)議在更新路由時(shí)僅使用路徑跳數(shù)作為判決準(zhǔn)則，無(wú)法適應(yīng)現(xiàn)今無(wú)人機(jī)自組網(wǎng)中高動(dòng)態(tài)、高負(fù)載的場(chǎng)景，針對(duì)這個(gè)問(wèn)題，本文以Q 學(xué)習(xí)框架為基礎(chǔ)，將路徑跳數(shù)、鏈路質(zhì)量和節(jié)點(diǎn)負(fù)載三個(gè)因子作為路由測(cè)度，設(shè)計(jì)了UQL-OLSR 協(xié)議，在協(xié)議的工作過(guò)程中，節(jié)點(diǎn)通過(guò)廣播Hello 和TC 分組交互路由測(cè)度信息，網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)維護(hù)一個(gè)Q 值表實(shí)現(xiàn)動(dòng)態(tài)的路由更新。實(shí)驗(yàn)結(jié)果表明，UQL-OLSR 協(xié)議相比OLSR 協(xié)議在平均端到端時(shí)延和分組投遞率上有明顯優(yōu)勢(shì)，更加適用于節(jié)點(diǎn)高速移動(dòng)，數(shù)據(jù)交互頻繁的無(wú)人機(jī)自組網(wǎng)場(chǎng)景。