摘 要:由于無人機網(wǎng)絡的動態(tài)特性,要保證其具有可靠的通信保障仍存在一定的挑戰(zhàn),尤其是在軍事領域,對無人機網(wǎng)絡的QoS保障能力要求更高。針對上述需求,提出了一種基于Q學習的自適應QoS路由算法。在該算法中,每個節(jié)點通過HELLO消息和數(shù)據(jù)包相結(jié)合的方式來進行鄰居信息感知,通過接收鄰居節(jié)點反饋的ACK來獲取鏈路時延和丟包率,然后根據(jù)鏈路時延和丟包率來更新維護Q表??紤]節(jié)點移動特性,算法還引入了節(jié)點的位置信息。在路由過程中,節(jié)點綜合考慮Q表和鄰居節(jié)點的位置信息來進行最優(yōu)下一跳選擇。通過仿真驗證,對比參考的路由算法,提出的路由算法能夠在較低的路由開銷下提供更低的傳輸時延和更高的傳輸成功率。
關鍵詞:無人機網(wǎng)絡;強化學習;路由算法
中圖分類號: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],其具有部署方便快速、可擴展、靈活、自組織能力強、經(jīng)濟高效、機動性強等特點。近年來,隨著無人機在通信能力、載荷能力、機動能力等方面的提升,其在軍事領域和民用領域已得到了廣泛的應用[2,3]。最初,無人機是單個獨立使用的,但是由于單個無人機存在通信范圍有限、功能單一等弊端,無法完成較為復雜的任務。與單一無人機系統(tǒng)相比,多無人機系統(tǒng)可以更有效、更經(jīng)濟地協(xié)同完成任務。因此由無人機組成的飛行自組織網(wǎng)絡近年來得到了深入研究。
盡管無人機網(wǎng)絡在各領域中已廣泛使用,但如何保證無人機網(wǎng)絡提供可靠穩(wěn)定的通信服務仍是一個具有挑戰(zhàn)的問題。無人機自組網(wǎng)(也被稱為飛行自組織網(wǎng)絡)可以看作是移動自組網(wǎng)(MANET)和車載自組網(wǎng)(VANET)的一種特殊形式[4]。它具有這些網(wǎng)絡共同特性的同時,還存在著一些獨特的挑戰(zhàn)。在無人機網(wǎng)絡中,每個節(jié)點的遷移程度遠遠高于VANET和MANET。無人機的速度為30~460 km/h[5]。換句話說,無人機的位置是時刻變化的,無人機之間的聯(lián)系是間歇性地建立和破壞的。由于更高的可移動性,無人機網(wǎng)絡拓撲結(jié)構(gòu)的變化也比MANET和VANET拓撲結(jié)構(gòu)更頻繁。頻繁的拓撲變化也增加了網(wǎng)絡的時延、丟包和控制信令開銷。另外,無人機網(wǎng)絡的工作環(huán)境較為復雜,尤其是在軍事應用領域,無人機往往面臨著干擾和被摧毀等威脅,這同樣會對網(wǎng)絡通信造成影響。無人機網(wǎng)絡的這些特性對路由協(xié)議的性能提出了更高的要求。
目前應用于無人機網(wǎng)絡的路由協(xié)議大多是對移動自組網(wǎng)路由協(xié)議的改進,無線自組網(wǎng)路由協(xié)議可分為主動路由、被動路由和混合路由。
主動路由協(xié)議也被稱為表驅(qū)動路由協(xié)議,因為它們傾向于以表的形式存儲更新路由信息。主動路由協(xié)議的著名例子包括目的地序列距離向量(destination-sequence distance vector, DSDV)[6]和優(yōu)化鏈路狀態(tài)路由協(xié)議(optimized link state routing protocol, OLSR)[7]。每個節(jié)點以表格的形式維護和存儲網(wǎng)絡拓撲信息,以便維護一致的網(wǎng)絡視圖。運行主動路由協(xié)議的節(jié)點之間需要不時地交換最新路由信息表。每當節(jié)點需要傳輸數(shù)據(jù)包時,它首先從維護的表中提取路由信息,并使用該表進行路由。因此,路由發(fā)現(xiàn)過程所需的時間更少,從而減少了源節(jié)點和目的節(jié)點之間數(shù)據(jù)傳輸?shù)亩说蕉搜舆t。為適應無人機網(wǎng)絡特點,人們又提出了一些改進的主動路由協(xié)議,如文獻[8]提出DT-OLSR,該協(xié)議根據(jù)節(jié)點位置和移動特性動態(tài)調(diào)整HELLO消息發(fā)送頻率,提升了協(xié)議的動態(tài)適應性。文獻[9]提出了一種先進的快速恢復OLSR(AFR-OLSR)協(xié)議,該協(xié)議通過定義新的鏈路狀態(tài)和使用懲罰函數(shù)來改進路由計算規(guī)則,在無人機群中節(jié)點突然離線或高速移動的情況下,AFR-OLSR可以保持較高的數(shù)據(jù)包傳送率,并且?guī)缀醪粫眍~外的網(wǎng)絡延遲。文獻[10]提出的MCNA-OLSR選取節(jié)點的剩余能量、節(jié)點連接時間和緩沖區(qū)占用來優(yōu)化MPR節(jié)點的選擇,從而實現(xiàn)在相應場景下降低時延和丟包率。但是,主動式路由在路由發(fā)現(xiàn)和維護過程中,其大量交換路由信息和路由請求報文導致整個網(wǎng)絡的控制開銷很高。
被動路由協(xié)議也被稱為按需路由協(xié)議,因為它們在路由選擇過程中采用按需方式。被動路由協(xié)議的一些很好的例子是動態(tài)源路由協(xié)議(dynamic source routing, DSR)[11]和無線自組網(wǎng)按需平面距離向量路由協(xié)議(Ad hoc on-demand distance vector routing,AODV)[12]。運行被動路由協(xié)議的節(jié)點不需要維護任何先前的路由信息,只在需要通信時交換網(wǎng)絡的路由信息。被動路由協(xié)議的源節(jié)點簡單地按需發(fā)現(xiàn)路由以建立到目的節(jié)點的連接。因此,維護網(wǎng)絡拓撲信息產(chǎn)生的控制報文開銷很少。同樣,被動路由協(xié)議也有很多改進協(xié)議。如文獻[13]引入蟻群算法的思想,設計了一種改進的AODV協(xié)議。它提供了多種可選路由,降低了泛洪概率,并且可以保護低功耗節(jié)點。文獻[14]提出了一種加權聚類AODV(WBC-AODV),在該路由協(xié)議下,簇頭節(jié)點可以有效地管理成員節(jié)點的路由建立,從而減少路由泛洪過程中控制數(shù)據(jù)包的重復轉(zhuǎn)發(fā),降低數(shù)據(jù)包沖突的概率,提高網(wǎng)絡的分組傳輸率。但是被動路由協(xié)議在路由發(fā)現(xiàn)過程中,所有節(jié)點相互交換拓撲信息,這往往會導致網(wǎng)絡中數(shù)據(jù)包的泛濫。并且被動協(xié)議需要一定的時間來收集和分析網(wǎng)絡拓撲信息,這一過程往往會延長源節(jié)點和目的節(jié)點之間數(shù)據(jù)傳輸?shù)亩说蕉搜舆t。
混合路由需要在主動路由和被動路由之間進行權衡。它結(jié)合了主動路由低延遲和被動路由低開銷的優(yōu)點。在混合路由協(xié)議中,網(wǎng)絡被劃分為不同的區(qū)域,在區(qū)域內(nèi)和區(qū)域間分別使用主動協(xié)議和被動協(xié)議進行路由。混合路由協(xié)議的例子主要包括區(qū)域路由協(xié)議(zone routing protocol,ZRP) [15]和臨時有序路由算法(temporally ordered routing algorithm,TORA) [16]。
復雜的飛行環(huán)境和多樣化的飛行任務使無人機網(wǎng)絡處于不可預測的隨機波動狀態(tài),傳統(tǒng)的路由協(xié)議難以實時適應網(wǎng)絡的變化,會導致網(wǎng)絡性能的降低。強化學習是一種自適應學習方法,屬于機器學習范疇。使用強化學習來解決無人機網(wǎng)絡路由問題是一個有效的途徑。文獻[17]首次使用強化學習來解決靜態(tài)網(wǎng)絡中的路由問題?;赒學習提出了一種自適應的Q-routing算法。文獻[18]對Q-routing進行了擴展,提出了一種針對無線傳感器網(wǎng)絡的能量均衡路由算法。目前,基于Q學習的Ad hoc網(wǎng)絡路由協(xié)議正在逐漸興起。文獻[19]提出了一種新的基于Q學習的多目標優(yōu)化路由協(xié)議(QMR),將鏈路時延和節(jié)點剩余能量作為獎勵,為飛行自組網(wǎng)提供低時延、低能耗的服務保障。文獻[20]提出了DeepCQ+路由協(xié)議,該協(xié)議將新興的多智能體深度強化學習(MADRL)技術集成到現(xiàn)有的基于Q學習的路由協(xié)議及其變體中,通過引入Q、C兩個值來分別表征路由跳數(shù)和鏈路質(zhì)量,采用基于近端策略優(yōu)化(proximal policy optimization, PPO)的路由轉(zhuǎn)發(fā)機制來決定是否進行網(wǎng)絡探索,在廣泛的拓撲和移動性配置中實現(xiàn)了更高的性能。文獻[21]提出了一種基于Q學習的拓撲感知彈性路由策略(TARRAQ),以低開銷準確捕獲拓撲變化,并以分布式和自治的方式做出路由決策。文獻[22]提出了一種基于Q學習的自適應地理路由協(xié)議(QFAGR),該協(xié)議綜合考慮了時延、節(jié)點機動性和能耗對路由的影響,通過感知局部拓撲變化自適應調(diào)整強化學習參數(shù)和HELLO報文間隔,同時提出了一種新的路由洞規(guī)避機制,實現(xiàn)了吞吐量的提升和延遲的降低。文獻[23]提出了一種基于雙向Q學習的多目標優(yōu)化路由協(xié)議(BQMR),以解決多目標FANET中網(wǎng)絡負載增加和路由復雜度提高等問題。在BQMR中,將鄰居節(jié)點的負載占用引入獎勵函數(shù),以增加在更高網(wǎng)絡負載下對網(wǎng)絡擁塞的抵抗力,通過雙向Q值更新機制加速網(wǎng)絡對拓撲變化的感知,從而提升數(shù)據(jù)包傳輸率和吞吐量,降低網(wǎng)絡時延。
從上面的分析可以看出,無人機網(wǎng)絡的應用雖然越來越廣泛,但在無人機網(wǎng)絡中采用怎樣的路由協(xié)議來保證數(shù)據(jù)的可靠通信仍是一大難點,尤其是在軍事領域,無人機網(wǎng)絡的高動態(tài)特性和高QoS需求更是對無人機網(wǎng)絡路由協(xié)議提出了更高的挑戰(zhàn)。傳統(tǒng)的路由協(xié)議對網(wǎng)絡的動態(tài)變化反應不敏感且缺乏對QoS指標的考量,已無法滿足需求,而基于Q學習的路由算法能夠通過與網(wǎng)絡的實時交互及時感知網(wǎng)絡狀態(tài)的變化,從而做出路由調(diào)整,因此能夠較好地適應無人機網(wǎng)絡的動態(tài)特性。但是現(xiàn)有的Q學習路由算法往往存在對QoS度量考慮不充分的問題,單純地對鏈路時延和丟包率等QoS指標進行累積得到的往往只是局部最優(yōu)解。因此為解決上述問題,本文針對無人機網(wǎng)絡特性以及現(xiàn)有算法的不足,提出了一種基于Q學習的QoS路由算法(Q-learning based QoS-aware routing,QBQR)。無人機通過HELLO消息感知鏈路狀態(tài)(包括時延和丟包率)和鄰居節(jié)點的移動特性。針對不同QoS指標的特性(如時延為可加性度量,丟包率為可乘性度量),設計專門的懲罰函數(shù),使無人機更準確地感知網(wǎng)絡狀態(tài),同時引入節(jié)點間距離進一步約束路由選擇,從而優(yōu)化無人機路由決策,實現(xiàn)業(yè)務的可靠傳輸。對比傳統(tǒng)的移動自組織網(wǎng)絡路由協(xié)議,所提出的路由算法能夠提供更好的QoS保障。
1 Q學習原理
Q學習是強化學習領域中應用最廣泛的算法之一。該算法主要包含環(huán)境(environment)、代理(agent)、狀態(tài)空間(S)、動作空間(A)和獎勵(R)等要素。Q學習的基本思想是通過代理與環(huán)境的不斷交互,來學習環(huán)境特征,從而得到最優(yōu)策略。在Q學習算法中,代理在每個狀態(tài)下的每個動作都有一個對應的Q值表示最大累積獎勵。代理與環(huán)境的交互過程如圖1所示。在時刻t,處于狀態(tài)st(st∈S)的代理根據(jù)當前策略采取一個動作at(at∈A)后,從環(huán)境中獲得獎勵rt(rt∈R),根據(jù)獎勵更新對應Q值,然后進入到下一個狀態(tài)st+1。Q值的基本迭代公式如下所示。
Q(st,at)=Q(st,at)+α(rt+1+γmaxaQ(st+1,a)-Q(st,at))
(1)
其中:α是學習率,γ是折現(xiàn)因子,它們設置在0到1之間。未來Q值期望(maxaQ(st+1,a)),是代理在下一個狀態(tài)st+1選擇可能動作a時的最大Q值。Q學習算法通過建立一張二維的Q表來存儲狀態(tài)-動作對以及對應的Q值。智能體在給定狀態(tài)下,總是根據(jù)Q表按照一定的策略(例如:ε-greedy)進行動作選取。因此,Q學習算法也被稱作表查找法。Q學習適用于狀態(tài)和動作都是離散且有限的情況。對于連續(xù)狀態(tài)和動作或者狀態(tài)和動作集過大的情況,Q學習算法不能很好地適應。
2 QBQR算法設計
2.1 路由過程建模
在無人機網(wǎng)絡中,路由的過程是一個數(shù)據(jù)包來自一個源節(jié)點,并通過多跳通信定向到目的節(jié)點。路由的目的是確定可以將數(shù)據(jù)包從源節(jié)點傳輸?shù)侥康牡氐倪m當路徑,該路徑由許多單跳決策組成。它涉及到在缺乏整個網(wǎng)絡信息的情況下,從有限的鄰居中選擇最佳中繼的概率。這正是Q學習的核心思想,即在沒有關于動作對環(huán)境影響的先驗知識的情況下,為有限的馬爾可夫決策過程找到最佳的動作選擇策略。因此,路由過程可以用馬爾可夫決策過程建模,用Q學習算法求解。具體如下:
將整個骨干網(wǎng)絡視為一個環(huán)境,每個網(wǎng)關節(jié)點均視為代理。代理的每一種狀態(tài)由數(shù)據(jù)包所在網(wǎng)關和數(shù)據(jù)包的目的網(wǎng)關決定。例如,在時刻t,網(wǎng)關節(jié)點i要轉(zhuǎn)發(fā)的數(shù)據(jù)包的目的地為d,則對應代理的狀態(tài)st可表示為si,d。動作就是將數(shù)據(jù)包轉(zhuǎn)發(fā)至下一跳。動作at則可用ai,j來表示,即節(jié)點i在時刻t將數(shù)據(jù)包轉(zhuǎn)發(fā)到相鄰節(jié)點j。通過該動作,代理的狀態(tài)從si,d移動到sj,d,并收到關于該動作的獎勵。代理在狀態(tài)si,d時的動作空間為節(jié)點i的所有鄰居節(jié)點。用Q(si,d,ai,j)表示在狀態(tài)si,d,選擇動作ai,j時的Q值。需要注意的是,當不同數(shù)據(jù)包位于節(jié)點i時,如果數(shù)據(jù)包的目的節(jié)點不同,其對應的Q值也不同。每個網(wǎng)關節(jié)點都維護著一張Q表,用于存儲采用不同動作轉(zhuǎn)發(fā)不同目的地的數(shù)據(jù)包對應的Q值。以節(jié)點i為例,其維護的Q表如表1所示。表中,n為網(wǎng)絡中節(jié)點數(shù)量,k為節(jié)點i的鄰居數(shù)量。當節(jié)點i產(chǎn)生或收到需轉(zhuǎn)發(fā)的數(shù)據(jù)包時,會根據(jù)數(shù)據(jù)包的目的地確定當前狀態(tài),然后再根據(jù)Q表選擇下一跳節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)。數(shù)據(jù)包轉(zhuǎn)發(fā)后獲取相應反饋,然后按照Q值更新公式更新Q表。一個數(shù)據(jù)包從源節(jié)點傳輸至目的節(jié)點,或者超過指定跳數(shù)未到達目的節(jié)點而被丟棄即為一個回合。
2.2 QBQR算法總體框架
本文針對無人機網(wǎng)絡特點,考慮網(wǎng)絡運行時的QoS需求,提出一種基于Q學習的QoS路由算法。QBQR算法的總體框架如圖2所示。主要包含鄰居發(fā)現(xiàn)及維護、鏈路狀態(tài)感知、Q學習、路由決策等部分。
鄰居發(fā)現(xiàn)及維護主要用于探測各節(jié)點的鄰居節(jié)點,為代理在特定狀態(tài)下提供動作空間(即數(shù)據(jù)包可選擇的所有下一跳節(jié)點集合),同時獲取鄰居節(jié)點位置和移動速度。鏈路狀態(tài)感知主要是完成鏈路時延和丟包率的測量,同時獲取下一跳節(jié)點的最優(yōu)Q值。Q學習主要是完成Q表的維護和更新。路由決策主要是根據(jù)Q表和相應策略進行下一跳選擇。本章后續(xù)將對上述內(nèi)容進行詳細介紹。
2.2.1 鄰居發(fā)現(xiàn)及維護
無人機網(wǎng)絡中每個節(jié)點周期性向鄰居節(jié)點廣播HELLO消息,用HI表示HELLO消息發(fā)送間隔。HELLO消息中包含了節(jié)點的地理位置、移動速度等信息。節(jié)點通過接收到的HELLO消息來建立和維護鄰居表。鄰居表里存儲了各鄰居節(jié)點的地理位置、移動速度等重要信息。如果超過時間T未收到某鄰居節(jié)點的HELLO消息,則該鄰居將被從鄰居表中刪除。本文中的T取3倍HELLO消息的時間間隔??紤]到網(wǎng)絡開銷,HELLO消息發(fā)送的頻率不能過于頻繁。但是在動態(tài)的網(wǎng)絡中,HELLO消息間隔過大,往往會導致鄰居信息更新不及時,在數(shù)據(jù)轉(zhuǎn)發(fā)時就會出現(xiàn)大量丟包的情況?;诖耍疚膶?shù)據(jù)包和HELLO消息結(jié)合使用來進行鄰居節(jié)點維護。當節(jié)點向鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包時,收到數(shù)據(jù)包的節(jié)點會向上一跳節(jié)點回復ACK。當節(jié)點連續(xù)向鄰居節(jié)點發(fā)送超過3個數(shù)據(jù)包均未收到ACK時,則將該鄰居從鄰居表中刪除。這樣,當數(shù)據(jù)包轉(zhuǎn)發(fā)頻率較高時,可以在不增加網(wǎng)絡開銷的同時使節(jié)點更快地發(fā)現(xiàn)鏈路失效,并進行路由切換,提升路由的動態(tài)適應性。
2.2.2 鏈路狀態(tài)感知
本文在設計路由算法時,重點將時延和丟包率兩項QoS指標作為優(yōu)化目標,因此需要對鏈路時延和丟包率進行測量。鏈路時延和丟包率均在數(shù)據(jù)包轉(zhuǎn)發(fā)過程中獲取,具體過程如下。
a)鏈路時延測量。當節(jié)點B在t1時刻收到節(jié)點A轉(zhuǎn)發(fā)的數(shù)據(jù)包時,節(jié)點B會將該時刻記錄下來。然后節(jié)點B向節(jié)點A回復ACK,在ACK消息中攜帶收到對應數(shù)據(jù)包的時刻t1。節(jié)點A收到節(jié)點B回復的ACK,記錄接收時刻t2,并讀取ACK中的時刻t1。節(jié)點A就可以通過計算t1到t2的時間差得到一個時延,記為delayA,B。
delayA,B=t2-t1
(2)
為避免單次測量帶來較大的抖動,可令節(jié)點A記錄最近n次測量的時延,然后將這些時延的均值作為最終測得的時延,記為DelayA,B。如式(3)所示。其中,delayA,B表示最近n次測量的時延中的第i個測量值。本文中n取值為3。
DelayA,B=∑ni=1delayA,B(i)
(3)
從上述過程可以看出,節(jié)點A所測得的時延實際上是節(jié)點B收到節(jié)點A發(fā)來的數(shù)據(jù)包到節(jié)點A收到節(jié)點B回復的ACK所經(jīng)歷的時延,而不是節(jié)點A向B發(fā)送數(shù)據(jù)包的時延。該時延能夠有效反映節(jié)點B在收到A發(fā)來的數(shù)據(jù)包后進行轉(zhuǎn)發(fā)的速度。
b)鏈路丟包率測量。給定一個時間窗口W,節(jié)點A記錄在時間窗口W內(nèi)向節(jié)點B發(fā)送包的數(shù)量nt,這里的包包含所有控制報文和數(shù)據(jù)包。本文中所有的包在被某個節(jié)點發(fā)送或轉(zhuǎn)發(fā)時都會攜帶上發(fā)送或被轉(zhuǎn)發(fā)的時間ts。節(jié)點B根據(jù)收到包的發(fā)送時間ts持續(xù)統(tǒng)計從節(jié)點A接收的發(fā)送時間大于等于時刻ts-W的包的數(shù)量nr。當節(jié)點A向B轉(zhuǎn)發(fā)數(shù)據(jù)包時,在數(shù)據(jù)包里攜帶上當前窗口對應的發(fā)包數(shù)量nt。當節(jié)點B收到數(shù)據(jù)包后,通過記錄的nr和數(shù)據(jù)包里攜帶的nt來計算節(jié)點A到B的丟包率,如式(4)所示。節(jié)點B計算得到pdrA,B過后,通過ACK反饋給節(jié)點A。這樣,節(jié)點A收到B回復的ACK后就能夠獲知其到節(jié)點B之間的鏈路丟包率。
pdrA,B=nt-nrnt
(4)
2.3 QBQR中的Q學習
在傳統(tǒng)的Q學習算法中,代理每采取一個動作,便會從環(huán)境中獲得相應的獎勵,算法的目標是獲取最大累積獎勵,即最大Q值。Q值越大表示對應的動作越優(yōu)。而本文提出的QBQR算法將Q學習中獎勵函數(shù)改成懲罰函數(shù),目標是獲得最小累積懲罰,即最小Q值。Q值越小表示對應的動作越優(yōu)??紤]無人機網(wǎng)絡在運行時的高QoS需求,本文將前文所述的鏈路時延和丟包率引入到懲罰函數(shù)的設計當中。懲罰函數(shù)和Q值更新函數(shù)分別如式(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表示在狀態(tài)st時數(shù)據(jù)包所在的節(jié)點;j表示動作at選擇的下一跳節(jié)點;Delayi,j表示節(jié)點i向節(jié)點j轉(zhuǎn)發(fā)數(shù)據(jù)包時測量得到的鏈路時延。特別地,當節(jié)點j為目的節(jié)點時,令Delayi,j=0,因為Delayi,j反映的是節(jié)點j收到節(jié)點i發(fā)來的數(shù)據(jù)包后進行轉(zhuǎn)發(fā)的速度,而當節(jié)點j為目的節(jié)點時,節(jié)點j不需要再對數(shù)據(jù)包進行轉(zhuǎn)發(fā)。Delaymax為最大鏈路時延,由節(jié)點的最大隊列長度和最大傳播距離決定;pdri,j表示節(jié)點i到j的丟包率;pdrmax表示業(yè)務允許的最大丟包率。因此,當節(jié)點i到j的丟包率大于業(yè)務允許的最大丟包率時,動作at將獲得最大懲罰。其他情況下,動作at獲得的懲罰將由鏈路時延和丟包率決定,時延和丟包率越小,得到的懲罰就越小。ω為時延和丟包率的權重參數(shù)(0≤ω≤1)。合理調(diào)整ω的值可以使路由的性能在兩者之間取得較好的平衡。為了統(tǒng)一度量,本文利用Delaymax和pdrmax對時延和丟包率進行了歸一化處理。
在QBQR中,節(jié)點將所有鄰居節(jié)點對應的Q值的初始值設置為一個很大的值,記為Qinitial。當節(jié)點j收到節(jié)點i發(fā)來的一個目的地為d數(shù)據(jù)包時,節(jié)點j便會向節(jié)點i回復一個ACK。ACK中攜帶了節(jié)點j轉(zhuǎn)發(fā)該數(shù)據(jù)包時Q表中的最小Q值,minaQ(sj,d,a)。如果節(jié)點j即為目的節(jié)點d,則ACK中回復的Q值為0。這樣,節(jié)點i便能利用該Q值和得到的懲罰來更新對應動作的Q值Q(si,d,ai,j)。當節(jié)點發(fā)送的數(shù)據(jù)包足夠多時,節(jié)點能夠?qū)︵従庸?jié)點實現(xiàn)遍歷,所有鄰居的Q值便會收斂到一個最小的值,節(jié)點通過選擇Q值最小的鄰居進行數(shù)據(jù)轉(zhuǎn)發(fā),便能得到最優(yōu)路徑??梢钥闯鲈赒BQR中,算法的收斂速度取決于網(wǎng)絡的規(guī)模和網(wǎng)絡的拓撲結(jié)構(gòu),網(wǎng)絡規(guī)模越大,節(jié)點的鄰居越多,算法的狀態(tài)空間和動作空間就越大,算法要收斂就需要進行更多的探索,因此復雜度也會相應增加。由于在無人機網(wǎng)絡中,節(jié)點的數(shù)量比較有限,所以QBQR算法能夠較好應對。在本文中由于懲罰函數(shù)為每條鏈路的時延和丟包率的加權值,而一條路徑在時延和丟包率上的表現(xiàn)實際上就是路徑上每條鏈路懲罰之和,所以為準確反映每條路徑在時延和丟包率上的表現(xiàn),本文將γ取值設為1。學習率α決定節(jié)點對網(wǎng)絡狀態(tài)變化學習的快慢,在傳統(tǒng)的Q學習中,α取值通常小于1,這是為了避免Q值的隨機誤差和不規(guī)則波動。但是在本文的懲罰函數(shù)中的時延為多次測量的平均時延,丟包率也是通過滑動窗口得到,它們均進行了平滑處理,因此Q值的變化實際上反映的就是路徑質(zhì)量的變化趨勢。為保證節(jié)點及時感知網(wǎng)絡變化并對路由策略進行調(diào)整,本文將α取值也設為1。
2.4 路由決策
在QBQR中,理論上最小Q值對應的下一跳即為最優(yōu)動作。但是在數(shù)據(jù)轉(zhuǎn)發(fā)初期,代理與環(huán)境交互不夠充分,得出的Q值無法真實反映網(wǎng)絡狀況。另外由于無人機網(wǎng)絡的動態(tài)特性,選擇Q值最小的動作也不一定是最優(yōu)解。而且如果代理始終利用Q值最小的動作,這樣就會導致可能的其他更優(yōu)動作不能被發(fā)現(xiàn)。所以在傳統(tǒng)的Q學習算法中,通常采用ε-greedy策略來平衡探索和利用。
在傳統(tǒng)的ε-greedy策略中,ε通常取一個很小的值,當節(jié)點進行路由決策時,總是以1-ε的概率選擇Q值最小的鄰節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù),以ε的概率隨機選取鄰節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。這樣就能使代理在利用最小Q值的同時,有一定的概率探索其他動作。但是由于ε是一個很小的固定值,在算法運行初期或網(wǎng)絡頻繁變化時,往往會出現(xiàn)探索力度不夠,導致算法收斂慢的問題。而當網(wǎng)絡較為穩(wěn)定時,又會出現(xiàn)對學習結(jié)果利用不充分的問題?;诖?,本文在QBQR中對傳統(tǒng)的ε-greedy策略進行了改進,將ε設置成一個可變的參數(shù),ε的表達式如式(7)所示。
ε=0.3maxaQ(st,a)≥Qinitial amp; cnlt;0.3cnotherwise
(7)
其中:maxaQ(st,a)為代理在狀態(tài)st時所有動作對應的最大Q值;c∈(0,1),為一個可調(diào)參數(shù);n為源節(jié)點持續(xù)向同一目的節(jié)點發(fā)送數(shù)據(jù)包的總數(shù)量(包含自己產(chǎn)生的數(shù)據(jù)包和轉(zhuǎn)發(fā)其它節(jié)點的數(shù)據(jù)包),當源節(jié)點超過一定時間未向該目的節(jié)點發(fā)送數(shù)據(jù)包時,n將被重置。源節(jié)點在發(fā)送數(shù)據(jù)包時會攜帶該值,以供后續(xù)節(jié)點計算ε的值。通過分析Q學習的過程可知,在源節(jié)點向目的節(jié)點發(fā)數(shù)據(jù)包的數(shù)量過少或有新的鄰居節(jié)點加入的時候,就會出現(xiàn)maxaQ(St,a)≥Qinitial的情況,這表明節(jié)點對網(wǎng)絡探索不夠充分。因此,在這種情況下令ε不小于0.3,保證節(jié)點采取較大探索力度,有利于路由的快速收斂和對新加入動作的快速學習。其他情況下ε會隨著發(fā)包數(shù)量的增加而不斷減小,這也更符合Q學習特性,當節(jié)點對網(wǎng)絡探索到一定程度的時候,再做過多的探索就會導致對學習結(jié)果利用不充分的情況,影響路由性能。c值可用于調(diào)整節(jié)點的探索力度,c值越大,ε為較大值的時間就越長,探索的力度就越大。因此,可根據(jù)網(wǎng)絡規(guī)模的大小對c值進行適當調(diào)整,通常網(wǎng)絡規(guī)模越大,需要探索的時間越長,c值就應取得越大。
考慮到無人機網(wǎng)絡的動態(tài)特性,無人機節(jié)點的鄰居表往往存在更新不及時的問題,在節(jié)點進行路由決策的時候,有的鄰居節(jié)點可能已經(jīng)飛出了節(jié)點的通信范圍Rmax,如果選擇飛出通信范圍內(nèi)的節(jié)點作為下一跳的話,就會導致數(shù)據(jù)包的丟失。為避免這樣的情況,本文在路由決策的時候引入了節(jié)點間距離作為約束。假設節(jié)點移動速度在短時間內(nèi)是固定的,當節(jié)點i在t2時刻進行路由決策時,其所在位置記為(pxi(t2),pyi(t2),pzi(t2)),其最近一次更新鄰居表的時間記為t1。在t1時刻,其獲知的鄰居節(jié)點j的位置為(pxj(t1),pyj(t1),pzj(t1)),速度為(vxj(t1),vyj(t1),vzj(t1))。那么在t2時刻,節(jié)點i可通過計算估計節(jié)點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時刻,節(jié)點i和j的距離估計值di,j如式(10)所示。
di,j=[pxj(t2)-pxi(t2)]2+[pyj(t2)-pyi(t2)]2+[pzj(t2)-pzi(t2)]2
(10)
當發(fā)現(xiàn)di,jgt;Rmax,節(jié)點i就知道節(jié)點j離開了自身通信范圍,在路由決策時,不會選擇節(jié)點j作為下一跳。
綜上,在QBQR運行過程中,所有節(jié)點在進行路由決策時,會以1-ε的概率在估計距離小于等于其通信范圍的鄰居節(jié)點間選擇Q值最小的鄰居,以ε的概率在估計距離小于等于其通信范圍的鄰居節(jié)點間隨機選取鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。若節(jié)點的所有鄰居節(jié)點的估計距離均超出了節(jié)點的通信范圍,則采用廣播的方式發(fā)送數(shù)據(jù)包。
2.5 算法流程
QBQR運行流程如算法1所示,總共可以分鄰居發(fā)現(xiàn)及維護、路由決策以及Q學習三個階段。鄰居發(fā)現(xiàn)及維護階段如第2~11行所示。各網(wǎng)關節(jié)點通過周期發(fā)送和接收HELLO報文來進行鄰居發(fā)現(xiàn)。為及時地發(fā)現(xiàn)鄰居失效,節(jié)點會在超過時間T未收到鄰居發(fā)來的HELLO消息或者連續(xù)向鄰居節(jié)點發(fā)送超過3個數(shù)據(jù)包且未收到ACK時,將該鄰居視為失效。路由決策階段如第12~27行所示。主要是對傳統(tǒng)的ε-greedy策略進行改進,使ε的值隨著網(wǎng)絡狀態(tài)變化而變化,更好地平衡了探索與利用的關系。同時結(jié)合節(jié)點間距離約束,提升路由決策的有效性。Q學習階段如第28~35行所示。網(wǎng)關節(jié)點每轉(zhuǎn)發(fā)一個數(shù)據(jù)包后,會收到下一跳節(jié)點回復的ACK,從中可獲得相應的鏈路時延和丟包率,通過鏈路時延和丟包率來計算相應懲罰,從而完成Q表的更新。節(jié)點根據(jù)Q表便可獲知所有鄰居作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳的優(yōu)劣。
算法1 QBQR算法
1 輸入:HI, ω, c, W, Delaymax, pdrmax。
2 階段1:鄰居發(fā)現(xiàn)及維護
3 if 到了某個節(jié)點發(fā)送HELLO報文的時間 then
4 節(jié)點發(fā)送HELLO報文
5 end if
6 if 某個節(jié)點收到HELLO報文 then
7 節(jié)點讀取報文信息,更新鄰居表
8 end if
9 if 某個節(jié)點超過時間T未收到某個鄰居的HELLO消息or向某個鄰居連續(xù)發(fā)送超過3個數(shù)據(jù)包未收到ACK then
10 節(jié)點將該鄰居從鄰居表中刪除
11 end if
12 階段2:路由決策
13 while 節(jié)點有數(shù)據(jù)需要轉(zhuǎn)發(fā) do
14" "計算所有鄰居節(jié)點所在位置
15" "將處于通信范圍內(nèi)的鄰居節(jié)點作為數(shù)據(jù)轉(zhuǎn)發(fā)的備選節(jié)點
16" "if 備選節(jié)點為空 then
17"" "廣播數(shù)據(jù)包
18" "else
19""" 生成一個隨機數(shù)a,a∈(0,1)
20""" 按照式(7)計算ε的值
21""" if alt;ε then
22"""" 在備選節(jié)點中隨機選取一個節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)
23""" else
24"""" 選擇備選節(jié)點中Q值最小的節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)
25""" end if
26" "end if
27 end while
28 階段3:Q學習
29 if 某個節(jié)點有新鄰居加入 then
30 初始化新加入鄰居節(jié)點的Q值
31 end if
32 if 某個節(jié)點收到下一跳反饋的ACK then
33 通過ACK攜帶的信息,按照式(5)計算懲罰
34 按照式(6)更新Q表
35 end if
3 仿真結(jié)果及分析
3.1 仿真環(huán)境
本文采用Linux平臺下的NS-3網(wǎng)絡模擬仿真器來對QBQR性能進行仿真驗證。仿真參數(shù)設置如表2所示。無人機網(wǎng)絡中共包含36個節(jié)點,均勻分布在100 km×100 km區(qū)域內(nèi)。節(jié)點采用隨機游走移動模型,MAC層采用TDMA協(xié)議。每個節(jié)點的通信半徑設置為10 000 m,仿真時長為300 s。
3.2 仿真結(jié)果分析
本文主要選取端到端時延、報文投遞率和路由開銷三項指標來對QBQR的性能進行仿真驗證。引入的對比算法為OLSR、AODV以及文獻[20]中提出的DeepCQ+。端到端時延是指數(shù)據(jù)包從源節(jié)點傳輸?shù)侥康墓?jié)點的總時延。報文投遞率是指目的節(jié)點成功接收數(shù)據(jù)包數(shù)量與源節(jié)點發(fā)送數(shù)據(jù)包數(shù)量的比值。路由開銷本文定義為數(shù)據(jù)傳輸過程中產(chǎn)生的所有路由控制消息的總數(shù)據(jù)量與成功交付的數(shù)據(jù)包的總數(shù)據(jù)量的比值。
3.2.1 平均端到端時延
圖3展示了網(wǎng)絡規(guī)模為36個節(jié)點時,不同業(yè)務分別采用QBQR、OLSR、AODV和DeepCQ+算法得到的平均端到端時延。共選取6類業(yè)務,每類業(yè)務均選取不同的源、目的節(jié)點。從圖中可以看出,所有業(yè)務使用QBQR算法得到的平均端到端時延均小于使用OLSR、AODV和DeepCQ+算法。其中,6類業(yè)務使用QBQR算法的平均端到端時延與OLSR相比平均降低了20.9%,與AODV相比平均降低了18.6%,與DeepCQ+相比平均降低了18.3%。
圖4分別展示了網(wǎng)絡規(guī)模為36個節(jié)點時,在不同移動模型和不同移動速度下,平均端到端時延的變化情況??梢钥闯鏊姆N算法隨著節(jié)點移動速度的增加,平均端到端時延均呈上升趨勢。這是因為隨著節(jié)點移動速度的增加,網(wǎng)絡中鏈路頻繁斷裂,從而導致了端到端時延的增加。QBQR算法表現(xiàn)仍為最佳,其平均端到端時延相較于OLSR最多降低了20.4%,相較于AODV最多降低了37.1%,相較于DeepCQ+最多降低了20.1%。
圖5展示了不同節(jié)點規(guī)模下,四種算法的平均端到端時延??梢钥闯?,隨著節(jié)點規(guī)模的增加,四種算法的業(yè)務平均端到端時延總體呈上升趨勢,這是因為隨著節(jié)點數(shù)量的增加,節(jié)點的時隙周期變長,且業(yè)務傳輸路徑跳數(shù)可能也有所增加造成的。QBQR在不同節(jié)點規(guī)模下得到的平均端到端時延始終低于OLSR和AODV,其平均端到端時延相較于OLSR在節(jié)點數(shù)量為60的時候降低最多達到50.7%,相較于AODV在節(jié)點數(shù)量為80的時候降低最多達到35.7%,相較于DeepCQ+在節(jié)點數(shù)量為60的時候降低最多達到35.6%。
綜上,相比于OLSR、AODV和DeepCQ+算法,QBQR算法在平均端到端時延上更具優(yōu)勢。這是因為OLSR、AODV和DeepCQ+在計算路由時,都是基于“最小跳數(shù)”,沒有考慮鏈路時延。鏈路時延往往會受到節(jié)點間距離、網(wǎng)絡負載以及節(jié)點時隙配置等因素的影響,而OLSR、AODV和DeepCQ+無法有效進行感知,因此得到的路徑的時延往往不是最優(yōu)的。QBQR在計算路由時引入鏈路時延,能夠找出處從源端到目的地時延最小的路徑,從而降低端到端時延。
3.2.2 報文投遞率
圖6展示了網(wǎng)絡規(guī)模為36個節(jié)點時,無人網(wǎng)絡中部分節(jié)點受到干擾條件下,不同業(yè)務分別采用QBQR、OLSR和AODV算法得到的報文投遞率。通常情況下,節(jié)點受到干擾會出現(xiàn)一定概率的丟包。因此,本文在網(wǎng)絡中隨機選取了8個節(jié)點均以0.1~0.3的隨機概率出現(xiàn)丟包,來模擬節(jié)點受到干擾的情況。為避免節(jié)點移動性對本次仿真結(jié)果的影響,本文將節(jié)點的移動速度設置為5 m/s,以保證仿真過程中網(wǎng)絡拓撲的穩(wěn)定。從仿真結(jié)果可以看出,6類業(yè)務下QBQR和DeepCQ+算法都取得了較高的報文投遞率,QBQR略高于DeepCQ+。業(yè)務1、2、3、4、6使用QBQR算法得到的報文投遞率均高于OLSR、AODV。業(yè)務5使用QBQR算法得到的報文投遞率高于AODV,與OLSR算法相當。6類業(yè)務使用QBQR算法總的報文投遞率相較于OLSR提升了19.2%,相較于AODV提升了20%,相較于DeepCQ+提升了1.7%。
圖7展示了網(wǎng)絡規(guī)模為36個節(jié)點時,網(wǎng)絡中不同數(shù)量的節(jié)點受干擾情況下,6類業(yè)務的報文總投遞率變化情況。從圖中可以看出四種算法的報文總投遞率均隨著受干擾節(jié)點數(shù)量的增加而降低。這是因為網(wǎng)絡中受干擾節(jié)點的數(shù)量越多,數(shù)據(jù)包傳輸路徑中受干擾的節(jié)點也會增多,從而導致丟包率的增加,降低了報文的投遞率。QBQR算法的報文總投遞率總是優(yōu)于OLSR、AODV和DeepCQ+。QBQR算法的報文總投遞率與OLSR相比最大提升了12.7%,與AODV相比最大提升了19.7%,與DeepCQ+相比最大提升了5.5%。
綜上所述,可以看出QBQR算法能夠更好地適應干擾環(huán)境,在有節(jié)點受到干擾時能夠提供更高的報文投遞率。這是因為QBQR算法在數(shù)據(jù)包的傳輸過程中進行了鏈路丟包率的測量,并將丟包率這一指標引入了懲罰函數(shù)的計算過程中。節(jié)點在數(shù)據(jù)轉(zhuǎn)發(fā)過程中能夠及時感知到鄰居節(jié)點的丟包情況,從而選擇丟包率更低的鄰居進行數(shù)據(jù)轉(zhuǎn)發(fā),避開那些高丟包率的節(jié)點。而OLSR和AODV并不能準確感知到鄰居節(jié)點的丟包情況,所以得到的數(shù)據(jù)轉(zhuǎn)發(fā)路徑無法避開受到干擾的節(jié)點,從而導致了較高的丟包率。圖6中的業(yè)務5使用OLSR得到的報文投遞率之所以與QBQR相當,是因為OLSR計算的轉(zhuǎn)發(fā)路徑中恰好沒有節(jié)點受到干擾,但是OLSR無法總是提供這樣的保障。DeepCQ+通過C值反映了鏈路質(zhì)量,同樣能夠感知到鄰居節(jié)點丟包,因此同樣取得了較高的報文投遞率,但是C值的改變是根據(jù)節(jié)點丟包的變化而變化,對于節(jié)點隨機丟包反應不夠靈敏,因此其路由決策有時并不能完全避開受干擾的節(jié)點,導致其投遞率低于QBQR。
圖8展示了網(wǎng)絡規(guī)模為36個節(jié)點時,不同業(yè)務在節(jié)點快速移動條件下的報文投遞率。本次仿真同樣選取網(wǎng)絡中6類源、目的節(jié)點各不相同的業(yè)務。此時,網(wǎng)絡中的節(jié)點均以20 m/s的速度移動??梢钥闯?,所有業(yè)務使用QBQR算法得到的報文投遞率均高于OLSR、AODV和DeepCQ+。其中,6類業(yè)務使用QBQR算法得到的報文總投遞率相較于OLSR提升了20.6%,相較于AODV提升了41.7%,相較于OLSR提升了20.6%,相較于DeepCQ+提升了3.5%。
圖9展示了網(wǎng)絡規(guī)模為36個節(jié)點時,不同移動模型下,業(yè)務的報文投遞率隨節(jié)點移動速度的變化??梢钥吹?,隨著節(jié)點移動速度的增加,業(yè)務的報文投遞率呈下降趨勢。這是因為隨著節(jié)點移動速度的增加,節(jié)點間鏈路中斷頻率也會增加,節(jié)點在進行數(shù)據(jù)轉(zhuǎn)發(fā)時無法及時發(fā)現(xiàn)鏈路中斷,導致在轉(zhuǎn)發(fā)數(shù)據(jù)包時更容易出現(xiàn)丟包。QBQR算法的報文投遞率始終高于OLSR、AODV和DeepCQ+。QBQR算法的報文投遞率相比于OLSR算法最多提升了30%,相比于AODV最多提升了51.8%,相比于DeepCQ+最多提升了7.3%。
圖10展示了不同節(jié)點規(guī)模下,四種算法的報文投遞率??梢钥闯?,隨著節(jié)點規(guī)模的增加,四種算法的報文投遞率呈下降趨勢,這是因為隨著節(jié)點規(guī)模的增加,業(yè)務傳輸路徑跳數(shù)增加,路徑失效中斷的頻率也隨之增加,導致了丟包率的增加。QBQR算法的報文投遞率始終高于OLSR、AODV和DeepCQ+。在節(jié)點數(shù)量為100時,QBQR算法的報文投遞率相比于OLSR、AODV和DeepCQ+提升最多,分別達到了37.9%、67.9%和13.7%。
綜上所述,可以看出QBQR算法能夠更好地適應網(wǎng)絡中節(jié)點的動態(tài)特性,在網(wǎng)絡拓撲結(jié)構(gòu)頻繁變化的情況下,能夠提供更高的報文投遞率。OLSR算法需要感知全網(wǎng)拓撲才能計算路由,但是由于拓撲更新時間較長,得到的路由存在一定滯后,數(shù)據(jù)包在轉(zhuǎn)發(fā)時,路徑可能已經(jīng)失效,從而導致大量丟包。AODV雖然不用感知全網(wǎng)拓撲,但是由于其路由有效時間設置較長,無法及時針對網(wǎng)絡拓撲變化做出路由調(diào)整,同樣也會導致數(shù)據(jù)包的大量丟失。DeepCQ+雖然通過C值更夠更快速地感知網(wǎng)絡變化,但是其路由策略調(diào)整的效率仍低于QBQR。QBQR之所以能保持較高的報文投遞率,主要因為:a)當鏈路因為節(jié)點移動出現(xiàn)間歇性中斷時,QBQR算法能夠及時獲取鏈路丟包情況,從而避開質(zhì)量較差的鏈路;b)當鄰居節(jié)點離開節(jié)點的通信范圍后,節(jié)點能夠利用數(shù)據(jù)轉(zhuǎn)發(fā)時接收ACK的情況,更快地更新鄰居表;c)當節(jié)點在進行路由決策時,通過估計鄰居節(jié)點的實時位置,來選擇位于自身節(jié)點通信范圍內(nèi)的節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā),避免了數(shù)據(jù)包的丟失。
3.2.3 路由開銷
圖11展示了不同節(jié)點數(shù)量下算法的路由開銷??梢钥闯觯S著節(jié)點數(shù)量的增加,四種算法的路由開銷均呈上升趨勢。這是因為隨著網(wǎng)絡規(guī)模的增大,算法在網(wǎng)絡中需要傳輸更多的控制報文才能完成路由計算。四種算法中,OLSR算法路由開銷最大,AODV算法路由開銷最小,QBQR路由開銷低于OLSR和DeepCQ+,稍大于AODV。
圖12展示了在節(jié)點數(shù)量為36的網(wǎng)絡中,路由開銷隨節(jié)點移動速度變化的情況??梢钥闯觯S著節(jié)點移動速度的增加,四種算法的路由開銷均呈上升趨勢。這是因為節(jié)點移動速度越快,網(wǎng)拓撲變化就越頻繁,要完成數(shù)據(jù)包的交付就需要更多的控制報文來感知網(wǎng)絡變化。同樣,OLSR算法路由開銷最大,AODV算法路由開銷最小,QBQR路由開銷低于OLSR和DeepCQ+,稍大于AODV。
綜上可以看出,QBQR算法在路由開銷上的表現(xiàn)要優(yōu)于OLSR和DeepCQ+,略差于AODV。這是因為OLSR算法需要定期對全網(wǎng)拓撲進行感知,這需要大量的控制報文,而且隨著節(jié)點數(shù)量的增加,控制報文增加得越明顯。DeepCQ+引入了廣播機制來進行探索,導致了較高的報文開銷。QBQR只需要感知鄰居信息,不需要感知全網(wǎng)拓撲,因此控制報文得到明顯減少。而AODV只在業(yè)務發(fā)送的初始階段進行路由發(fā)現(xiàn),因此路由開銷更小。QBQR相較于AODV雖然增加了一定的路由開銷,但是其在平均端到端時延和報文投遞率方面取得了較大的優(yōu)勢。
3.2.4 探索與利用策略比較
圖13展示了在節(jié)點數(shù)量為36的網(wǎng)絡中,采用傳統(tǒng)ε-greedy策略和本文改進的ε-greedy策略時,算法的收斂過程。本次仿真Qinitial取100,遠大于收斂后的Q值。在改進的ε-greedy策略中,c值取0.96。可以看到,對于傳統(tǒng)的ε-greedy策略,ε取值越大,算法的收斂速度越快,這是因為ε越大,節(jié)點對鄰居節(jié)點的探索力度就越大。當ε取0.1時,算法要進行90余次的迭代才能收斂;當ε取0.3時,算法要進行60余次的迭代才能收斂;當ε取0.5時,要進行20余次的迭代才能收斂。對于改進的ε-greedy策略,算法的收斂速度與傳統(tǒng)的ε-greedy策略ε取0.5時相當,同樣只需要進行20余次的迭代便能收斂。算法收斂后,需要對Q值進行充分利用,以保證路由路徑的最佳。傳統(tǒng)的ε-greedy策略通過取較大的ε值,雖然能提升算法收斂速度,但是不利于算法收斂后的利用。改進的ε-greedy策略會隨著迭代次數(shù)的增加,逐漸減小探索力度,進而充分利用收斂后的Q值進行下一跳選擇,從而取得更優(yōu)的路由效果。圖14展示了不同策略下6類業(yè)務的平均端到端時延??梢钥闯?,采用改進的ε-greedy策略得到的平均端到端時延優(yōu)于傳統(tǒng)的ε-greedy策略。傳統(tǒng)的ε-greedy策略在ε取0.1時的平均端到端時延要優(yōu)于ε取0.3時。改進的ε-greedy策略相較于傳統(tǒng)ε-greedy策略ε取0.1時,6類業(yè)務的平均端到端延時平均降低了8.1%;相較于ε取0.3時,平均降低了30.2%。
圖15展示了不同策略下6類業(yè)務的報文投遞率。該次仿真,仍在網(wǎng)絡中隨機選擇了8個節(jié)點以0.1~0.3的隨機概率出現(xiàn)丟包。同樣可以看到,采用改進的ε-greedy策略得到的報文投遞率優(yōu)于傳統(tǒng)ε-greedy策略。傳統(tǒng)的ε-greedy策略在ε取0.1時的報文投遞率要優(yōu)于ε取0.3時。改進的ε-greedy策略相較于傳統(tǒng)ε-greedy策略ε取0.1時,6類業(yè)務的報文總投遞率提升了13.3%;相較于ε取0.3時,報文總投遞率提升了19.7%。
4 結(jié)束語
本文針對無人機網(wǎng)絡高動態(tài)、易受干擾等特點,設計了一種基于Q學習的QoS路由算法。該算法通過引入鏈路時延和丟包率作為路由決策的依據(jù),來提升路由的QoS保障能力。在節(jié)點進行鄰居發(fā)現(xiàn)和維護過程中,通過將HELLO消息和數(shù)據(jù)包相結(jié)合的方式來提升節(jié)點鄰居表更新效率。在路由決策時,通過采用動態(tài)ε-greedy策略來優(yōu)化節(jié)點探索和利用過程,同時引入節(jié)點間距離作為約束,來提升路由對節(jié)點移動的適應能力。最后的仿真結(jié)果表明,本文設計的路由算法相較于傳統(tǒng)的OLSR、AODV算法和基于強化學習的DeepCQ+算法,在無人機網(wǎng)絡中能夠在較低的路由開銷下提供更好的時延和傳輸成功率保障。
參考文獻:
[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]韓磊. 無人機集群自組織網(wǎng)絡路由協(xié)議研究及優(yōu)化 [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.