基于Q-learning的飛行自組織網(wǎng)絡QoS路由方法*

黃鑫陳，陳光祖，鄭敏，譚沖，劉洪

(1 中國科學院上海微系統(tǒng)與信息技術(shù)研究所， 上海 200050； 2 中國科學院大學微電子學院， 北京 100049) (2020年1月2日收稿； 2020年4月29日收修改稿)

隨著傳感器和通信技術(shù)的快速發(fā)展，各種有人和無人飛行設備大量應用于軍事和民用領(lǐng)域。戰(zhàn)斗機、火炮等裝備已成為各國強大的戰(zhàn)斗力量，國產(chǎn)殲-20已裝備人民空軍的王牌部隊，在這種趨勢下國內(nèi)外掀起一股無人機的理論和實踐研究熱潮。飛行自組網(wǎng)(flying ad hoc networks)作為一種新的移動自組網(wǎng)(mobile ad-hoc networks)應運而生[1]。這種網(wǎng)絡由具有無線通信功能的節(jié)點組成，不依賴任何固定的基礎(chǔ)設施，以一種無中心、自組織和多跳傳輸方式，為戰(zhàn)機協(xié)同、搶險救災等應用場景提供應急通信網(wǎng)絡。

路由選擇作為網(wǎng)絡通信的關(guān)鍵技術(shù)之一，決定了數(shù)據(jù)的傳輸路徑，對網(wǎng)絡整體性能有著非常重要的影響[2]。然而，在高動態(tài)飛行自組織網(wǎng)絡中，網(wǎng)絡節(jié)點頻繁入網(wǎng)、退網(wǎng)以及快速移動，網(wǎng)絡拓撲變化快，鏈路容易斷裂和路由重建頻繁，從而導致數(shù)據(jù)分組丟失嚴重，網(wǎng)絡性能嚴重下降[3-5]。傳統(tǒng)的Ad hoc網(wǎng)絡路由協(xié)議，例如AODV(ad hoc on-demand distance vector routing)和DSR(dynamic source routing)，難以適應網(wǎng)絡拓撲結(jié)構(gòu)的快速變化，不能保證網(wǎng)絡的服務質(zhì)量(quality of service, QoS)。

鏈路可用帶寬被認為是QoS的一個重要指標，它是指由發(fā)/收節(jié)點組成的鏈路中未被使用的空閑帶寬，表征通信鏈路還可以提供的數(shù)據(jù)傳輸能力，通常定義為在不影響當前網(wǎng)絡中現(xiàn)有業(yè)務服務質(zhì)量的前提下，該鏈路可以為新加入的業(yè)務流提供的最大傳輸速率。在現(xiàn)有的帶寬預測方法中，基于被動測量的帶寬預測算法利用節(jié)點自身的物理載波檢測能力，獲取帶寬利用信息來預測鏈路的可用帶寬?；诒粍訙y量的方法無需向網(wǎng)絡中發(fā)送探測包，不會對原有業(yè)務的服務質(zhì)量造成額外影響，預測結(jié)果更加可靠，得到了較為廣泛的應用[6]。

近年來，Q-learning作為一種離策略、無模型的啟發(fā)式強化學習方法，受到眾多研究人員的關(guān)注[7-8]，它能夠通過與周圍環(huán)境交互信息動態(tài)地調(diào)整傳輸路徑，將學習任務分散在每一個網(wǎng)絡節(jié)點中，通過周期性地與周圍鄰居節(jié)點交換控制信息，可為尋找可靠的傳輸路徑提供依據(jù)[9-13]。

基于Q-learning強化學習框架，本文研究一種面向高動態(tài)飛行自組網(wǎng)的QoS路由方法，該方法考慮了轉(zhuǎn)發(fā)節(jié)點質(zhì)量、鏈路穩(wěn)定性和鏈路通信質(zhì)量，分別將鄰居節(jié)點數(shù)量、鏈路持續(xù)時間和鏈路可用帶寬作為路由度量信息，設計一種提供QoS保證的Q-learning獎勵函數(shù)。網(wǎng)絡節(jié)點周期性統(tǒng)計本地路由度量信息并封裝在IP頭部，然后通過廣播Hello消息和發(fā)送數(shù)據(jù)分組進行交互，當鄰居節(jié)點接收到Hello分組或者數(shù)據(jù)分組，根據(jù)獎勵函數(shù)計算并更新Q值，源節(jié)點或者中繼節(jié)點根據(jù)其維護的Q值表智能選擇下一跳節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)。EXata網(wǎng)絡仿真結(jié)果表明，該方法在吞吐量和平均端到端時延上具有較好的性能，能為高動態(tài)飛行自組織網(wǎng)絡中數(shù)據(jù)傳輸提供穩(wěn)定性好、服務質(zhì)量高的通信鏈路。

1 Q-learning與路由重建

強化學習(reinforcement learning, RL)利用智能體(agent)與環(huán)境(environment)的交互，通過映射動作(action)和場景進行學習以獲得最優(yōu)策略。它不會告訴agent在當前狀態(tài)(state)下應該采取的最優(yōu)動作，而是讓agent與環(huán)境進行交互，通過不斷地嘗試最大化總獎勵值進而獲得最優(yōu)策略。Q-learning作為一種經(jīng)典的強化學習算法，通過不斷與外界交互信息，能夠在動態(tài)的環(huán)境中找出一條到達目的地的最佳路徑。

圖1描述RL的基本框架。RL中的智能體根據(jù)系統(tǒng)的當前狀態(tài)以及從環(huán)境中接收到的反饋來選擇操作。滿足馬爾可夫性質(zhì)的強化學習任務稱為馬爾可夫決策過程(Markov decision process, MDP)，通常用一個4元組(s,a,p,r)來描述，該4元組分別表示狀態(tài)、動作、轉(zhuǎn)移概率(transition probabilities)和獎勵(reward)。

圖1 強化學習的基本框架

定義：

1)動作(a)：智能體可以采取的所有可能的行動。

2)狀態(tài)(s)：環(huán)境返回的當前情況。

3)獎勵(rt)：環(huán)境的即時反饋值，以評估智能體選擇的上一個動作。

4)策略(p)：智能體根據(jù)當前狀態(tài)決定下一步動作的策略。

5)價值(V)：折扣(discount)下的長期期望返回值，與rt代表的短期返回相區(qū)分。Vp(s)定義為策略p下當前狀態(tài)s長期返回值的期望。

6)Q值或行動值(Q)：與rt相似，但多一個參數(shù)a。Qp(s,a)指當前狀態(tài)s在策略p下采取動作a的長期回報。

Q-learning是基于貝爾曼方程(Bellman equation)的離策略、無模型強化學習算法。在通信網(wǎng)絡中，一個節(jié)點代表一個狀態(tài)，數(shù)據(jù)分組從一個節(jié)點傳輸?shù)搅硪粋€節(jié)點稱為一個動作。每發(fā)送一個數(shù)據(jù)分組，更新一次平均值，這就是Q-learning路由的基本思想。數(shù)據(jù)分組被轉(zhuǎn)發(fā)的次數(shù)越多，得到樣本就越多，則更新次數(shù)越多，Q的估計值就越接近于真實值，最后依概率收斂于最優(yōu)值，從而可以找出一條從源節(jié)點到目的節(jié)點的最佳路徑。

標準Q-learning 的更新公式為

Q(st,at)←(1-α)Q(st,at)+

(1)

其中:α∈(0,1]為學習速率，用于控制學習更新的速度；γ∈[0,1)，用于表示未來獎賞的折扣，意味著相較于以后的回報看重眼前獎勵的程度；rt為環(huán)境的即時反饋值，可根據(jù)網(wǎng)絡性能需求，將性能參數(shù)如跳數(shù)、帶寬、時延、丟包率、能耗等映射到rt中。

2 基于Q-learning的QoS路由方法

2.1 獎勵函數(shù)設計

2.1.1 鄰居節(jié)點度

鄰居節(jié)點度即一跳鄰居節(jié)點數(shù)，是衡量節(jié)點質(zhì)量的重要度量指標。如果有待發(fā)送數(shù)據(jù)的節(jié)點隨機選擇鄰居節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點，該轉(zhuǎn)發(fā)節(jié)點的鄰居節(jié)點度可能較小，則鄰居節(jié)點稀少甚至沒有，容易造成通信鏈路斷裂，從而導致鏈路的可持續(xù)性降低。用N(R)表示節(jié)點R的鄰居節(jié)點度，N(R)并非越大越好。假設節(jié)點的發(fā)送概率為Pt，在基于競爭接入的移動自組織網(wǎng)絡中，節(jié)點成功傳輸數(shù)據(jù)分組的概率Ps為1-(1-Pt)N(R)-1。鄰居節(jié)點數(shù)越多，越有可能產(chǎn)生分組沖突，導致網(wǎng)絡性能下降。

2.1.2 鏈路可用帶寬

文獻[14]提出一種基于載波檢測的鏈路可用帶寬被動測量方法，節(jié)點通過載波檢測偵聽自身的發(fā)送和接收可用時長，對鏈路可用帶寬進行初步估計，然后偵聽可能導致數(shù)據(jù)沖突的其他節(jié)點發(fā)送時長，對初步估計值進行修正。該方法不依賴于鄰居節(jié)點的數(shù)量，考慮了當前網(wǎng)絡的業(yè)務量，且能獲得較為精確的可用帶寬預測值。

首先根據(jù)數(shù)據(jù)鏈路層協(xié)議模型確定鏈路可用帶寬的上限值。定義傳輸周期為鏈路成功完成一次數(shù)據(jù)傳輸所需要的時間，以IEEE 802.11DCF協(xié)議為例，考慮圖2所示的RTS/CTS 4次握手機制，傳輸周期包含分布式幀間間隔(distributed interframe space，DIFS)、退避過程(BackOff)所經(jīng)歷的時間、RTS/CTS控制幀交互過程經(jīng)歷的時間，DATA/ACK(acknowledgement)幀交互過程經(jīng)歷的時間，以及3個短幀間間隔(short interframe space，SIFS)。

圖2 傳輸周期示意圖

t=tDIFS+tB+tRTS+tCTS+tDATA+tACK+3tSIFS，

(2)

用LDATA表示DATA幀的大小，考慮到傳輸周期t包含傳輸一個DATA幀的其他協(xié)議開銷，則網(wǎng)絡中一條鏈路能獲得的最大吞吐量Bmax為

(3)

最大吞吐量Bmax可視為鏈路可用帶寬的上限值。

為了獲得實際鏈路可用帶寬，節(jié)點利用自身的物理載波檢測能力偵聽周圍信道的“忙閑”狀態(tài)，在一個固定測量周期Tmea內(nèi)，統(tǒng)計各自的發(fā)送可用時長和接收可用時長。節(jié)點的物理層狀態(tài)有4種情況：發(fā)送、接收、偵聽和空閑，發(fā)送可用時長為節(jié)點處于空閑狀態(tài)，且空閑時間大于DIFS的時長；接收可用時長為節(jié)點處于空閑或偵聽狀態(tài)的時長。用Ts(S)表示發(fā)送節(jié)點的發(fā)送可用時長，Tr(R)表示接收節(jié)點的接收可用時長，則由發(fā)/收節(jié)點對(S,R)組成的鏈路LS,R的可用時長TL計算為

TL=min{[1-p(S,R)]·Ts(S),

[1-p(R,S)]·Tr(R)}.

(4)

其中：p(S,R)為節(jié)點S可以發(fā)送數(shù)據(jù)，但節(jié)點R不能接收的概率；p(R,S)為節(jié)點R可以接收數(shù)據(jù)，但節(jié)點S不能發(fā)送的概率。在每個測量周期Tmea內(nèi)，鏈路LS,R的可用帶寬初步估計值Bpre根據(jù)鏈路可用時長的占比計算為

(5)

在基于競爭接入的多跳ad hoc網(wǎng)絡中，考慮隱藏節(jié)點的信號傳輸導致節(jié)點對(S,R)數(shù)據(jù)分組沖突，以及信道忙而不能應答CTS，從而造成鏈路可用帶寬損耗的情況，對初步估計值進行修正。在一個測量周期Tmea內(nèi)，通過偵聽信道統(tǒng)計發(fā)送節(jié)點S的隱藏節(jié)點發(fā)送信號的總時間為Thid，可以推出隱藏節(jié)點導致可用帶寬消耗的概率pcon為

(6)

則鏈路LS,R最終的可用帶寬B(S,R)為

B(S,R)=(1-pcon)·Bmax.

(7)

2.1.3 鏈路持續(xù)時間

考慮圖3所示的平面拓撲，設節(jié)點S為源節(jié)點，D為目的節(jié)點，R為節(jié)點S的一個鄰居節(jié)點，鏈路持續(xù)時間是移動距離RH所需的時間tRH。然而，在基于貪婪和競爭的轉(zhuǎn)發(fā)過程中，它是經(jīng)過距離RK所需的時間tRK，而tRK明顯小于tRH。

圖3 鏈路持續(xù)時間計算模型

設節(jié)點S、R和D的坐標分別為(xS,yS)、(xR,yR)和(xD,yD)，節(jié)點移動的速度和方向分別為(VS,θS)、(VR,θR)和(VD,θD)，參考文獻[15]，節(jié)點R處于節(jié)點S通信范圍的時間T(S,R)預測為

(8)

其中h為傳輸距離，且

(9)

2.1.4 獎勵函數(shù)

根據(jù)前面對鄰居節(jié)點度、鏈路持續(xù)時間和鏈路可用帶寬的定義可知，N(R)∈[0,∞)，T(S,R)∈[0,∞)，B(S,R)∈[0,Bmax]，首先對3個參量分別進行歸一化，其歸一化值n(R)、t(S,R)和b(S,R)為

(10)

定義節(jié)點S到R的瞬時獎勵A(S,R)為

A(S,R)=-g+[wN·n(R)+wB·

b(S,R)+wT·t(S,R)]，

(11)

其中：wN、wB和wT分別為鄰居節(jié)點度、鏈路可用帶寬和鏈路持續(xù)時間的權(quán)重因子，且滿足wN+wB+wT=1。定義g為取值是正常數(shù)的懲罰因子，則-g為負值，因為每次發(fā)送數(shù)據(jù)分組都會消耗節(jié)點能量，并且占用一定的信道帶寬?；跉w一化的n(R)、t(S,R)和b(S,R)，取g=1，則A(S,R)∈[-1,0]。A(S,R)表明網(wǎng)絡節(jié)點發(fā)送數(shù)據(jù)分組之后會獲得一個負的獎勵，從而迫使源節(jié)點最終選擇相對跳數(shù)較少的轉(zhuǎn)發(fā)路徑，因為跳數(shù)越多，轉(zhuǎn)發(fā)節(jié)點獲得的負獎勵越多，Q值則越小，被選為轉(zhuǎn)發(fā)節(jié)點的機會越小。對于目的節(jié)點D的一個鄰居節(jié)點X，有A(X,D)=-1。由于A(S,R)總是負值，則非目的節(jié)點的V值也是負的，從而目的節(jié)點的V值最大，定義為V(D,D)=0。

根據(jù)瞬時獎勵對相應鄰居節(jié)點的Q值進行更新，更新當前節(jié)點S對其鄰居節(jié)點R的質(zhì)量評估為

QS(D,R)←(1-α)QS(D,R)+α·

(12)

其中：α∈(0,1]為學習速率，γ∈[0,1)為折扣因子，NR為節(jié)點R的鄰居節(jié)點集。

2.2 路由方案設計

基于上述的Q-learning框架，結(jié)合考慮鏈路可靠性和穩(wěn)定性保障的獎勵函數(shù)，提出基于Q-learning的QoS路由方法(Q-learning based QoS routing，QQR)。

為了計算本節(jié)點到相應目的節(jié)點的Q值，網(wǎng)絡節(jié)點首先在本地統(tǒng)計路由測度相關(guān)信息，然后將其元數(shù)據(jù)封裝在IP頭部，并通過周期性廣播Hello分組以及轉(zhuǎn)發(fā)數(shù)據(jù)分組，將本地元數(shù)據(jù)發(fā)送給鄰居節(jié)點。若其鄰居節(jié)點正確接收到該分組，就可以從分組頭部提取元數(shù)據(jù)，從而完成后續(xù)Q值的計算更新。節(jié)點周期性廣播Hello分組的目的是確保所有節(jié)點(包括那些沒有數(shù)據(jù)流量的節(jié)點)能夠更新路由測度信息，以輔助鄰居節(jié)點做出正確的路由決策，其周期大小應根據(jù)網(wǎng)絡應用需求進行設置。

IP頭部除包含傳統(tǒng)的IP版本、協(xié)議版本、源地址、目的地址等信息，還需要添加本節(jié)點的發(fā)送可用時長、節(jié)點位置、鄰居節(jié)點數(shù)和V值鏈表，其中V值(即Qmax)鏈表與經(jīng)過本節(jié)點的目的節(jié)點數(shù)量有關(guān)。本節(jié)點的鄰居節(jié)點表中相應地維護鄰居節(jié)點上一次位置和記錄時間、鏈路持續(xù)時間、鄰居節(jié)點數(shù)、可用帶寬鏈表和V值鏈表。為了減少協(xié)議開銷，計算鏈路持續(xù)時間所需的速度參數(shù)由節(jié)點及其鄰居節(jié)點在前、后2個時刻的位置進行估算，而不再交互額外的速度矢量信息。此外，每個節(jié)點都為其已知鄰居維護一個如表1所示的Q值表(即Q矩陣)，表中的行代表經(jīng)過本節(jié)點的目的節(jié)點ID，列表示與其相鄰的一跳鄰居節(jié)點ID。

表1 Q值表

1)路由發(fā)現(xiàn)

圖4為QQR路由方法的路由發(fā)現(xiàn)流程框圖。當網(wǎng)絡節(jié)點正確接收到分組(Hello分組或者數(shù)據(jù)分組)時，無論該節(jié)點是否被指定為下一跳轉(zhuǎn)發(fā)節(jié)點，它先從分組的報頭中提取發(fā)送節(jié)點攜帶的信息，即發(fā)送可用時長，位置坐標x、y、z，鄰居節(jié)點數(shù)和Qmax鏈表，計算和更新本節(jié)點鄰居鏈表中的鄰居節(jié)點數(shù)、鏈路持續(xù)時間和鏈路可用帶寬。

圖4 QQR路由發(fā)現(xiàn)流程

如果該節(jié)點接收到的分組是一個數(shù)據(jù)包，則提取IP頭部中的目的地址插入Q值表，并通過式(12)計算該目的節(jié)點與本節(jié)點每個鄰居相關(guān)聯(lián)的Q值，即更新Q值表中該目的節(jié)點對應的列。如果本節(jié)點接收到的是Hello包，將丟棄Hello分組釋放內(nèi)存。若節(jié)點進一步判斷自己是中繼節(jié)點，即數(shù)據(jù)包是發(fā)給自己但自己不是目的節(jié)點，則本節(jié)點通過查詢Q值表選擇Q值最高的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點，然后用自己最新的路由測度信息替換IP頭部中的舊元數(shù)據(jù)并發(fā)送數(shù)據(jù)分組。如果當前不存在到目的節(jié)點的Q值，或者存在多個最高Q值相同的節(jié)點，則從中隨機選擇一個節(jié)點轉(zhuǎn)發(fā)本次數(shù)據(jù)分組。最后，不是發(fā)給本節(jié)點的數(shù)據(jù)分組將被丟棄，發(fā)給本節(jié)點的數(shù)據(jù)分組將上傳給上層。

2)路由維護

當數(shù)據(jù)分組成功到達目的節(jié)點，則與這條路徑相鄰的部分節(jié)點的Q值表也得到更新，如果數(shù)據(jù)分組超過規(guī)定跳數(shù)或時間沒有達到目的節(jié)點，則將該分組丟棄而不再進行轉(zhuǎn)發(fā)。周期性廣播Hello分組的主要目的是動態(tài)地維護全網(wǎng)節(jié)點的Q值表，并解決鏈路斷開問題。此外規(guī)定了Q值表中目的節(jié)點的生存時間，如果在生存周期內(nèi)某一個目的節(jié)點相關(guān)的Q值沒有得到更新，則認為此目的節(jié)點失效，并刪除其對應的一列Q值。

2.3 路由方法分析

1)網(wǎng)絡開銷

路由信息交互需要在IP頭部添加本節(jié)點的發(fā)送可用時長(8字節(jié))、節(jié)點位置(24字節(jié))、鄰居節(jié)點數(shù)(4字節(jié))和V值鏈表(8×NDi字節(jié)，其中NDi為有數(shù)據(jù)包中轉(zhuǎn)至節(jié)點i的目的節(jié)點數(shù))。因此，QQR路由方法的Hello分組交互導致的吞吐量開銷Thpoverhead大約為

(13)

式中：Ntotal為網(wǎng)絡總節(jié)點數(shù)，Thello為Hello分組更新周期，一般將鏈路可用帶寬的估計周期Tmea設置為Thello。

2)反饋代價

QQR算法中節(jié)點每接收到一個分組便計算并更新Q值，該過程即為一次Q學習。假設當前時刻源節(jié)點S和目的節(jié)點D之間存在一條最優(yōu)路徑P，Q學習的目的就是通過多次迭代學習最后逼近這條最優(yōu)路徑。在網(wǎng)絡初始化時采用ε-greedy算法進行探索，發(fā)現(xiàn)的傳輸路徑與最優(yōu)路徑存在較大的偏差，可能是跳數(shù)較大甚至沒有找到目的節(jié)點，那么吞吐量和時延等網(wǎng)絡性能就表現(xiàn)得較差。隨著學習次數(shù)的增多，Q值不斷更新逼近穩(wěn)態(tài)值，則傳輸路徑越接近最優(yōu)路徑，網(wǎng)絡性能逐漸提升。Q學習發(fā)現(xiàn)的傳輸路徑與理想傳輸路徑之間的偏差導致的網(wǎng)絡性能降低，就是Q學習用于路由時在通信網(wǎng)絡中的反饋代價。

3)收斂時間

由于Q-learning算法的收斂需要一定的時間，只有網(wǎng)絡中所有節(jié)點的Q值收斂后，建立的路由才會逼近最佳路由。然而對于拓撲運動的網(wǎng)絡，可能存在Q學習還未收斂時，網(wǎng)絡狀態(tài)已經(jīng)發(fā)生改變的情況，所以要求：①算法收斂時間內(nèi)網(wǎng)絡拓撲不能劇烈變化，不能導致Q值總是與穩(wěn)態(tài)值存在很大的偏差；②Hello包更新時間要小于算法收斂時間，且如果網(wǎng)絡拓撲變化較快，更新時間應該取較小的值，從而保證鄰居節(jié)點能夠及時報告網(wǎng)絡狀態(tài)。

3 仿真結(jié)果與分析

3.1 收斂分析

本文提出的QQR協(xié)議已在EXata網(wǎng)絡仿真環(huán)境中實現(xiàn)，設置鄰居節(jié)點數(shù)、鏈路持續(xù)時間和鏈路可用帶寬的權(quán)重系數(shù)為0.2、0.3和0.5，其他主要仿真參數(shù)如表2所示。

表2 主要仿真參數(shù)

本文采用的業(yè)務流模型為泊松流，數(shù)據(jù)包的產(chǎn)生時間服從泊松分布。為了評估QQR協(xié)議的收斂性，建立4×4平面網(wǎng)格拓撲，網(wǎng)格邊長為250 m，配置一條業(yè)務流使得源節(jié)點和目的節(jié)點位于整個拓撲主對角線的2個端點，源節(jié)點發(fā)包速率為1 pkt/s，Hello包的廣播間隔設置為1 s。統(tǒng)計仿真運行過程中源節(jié)點的Qmax值隨發(fā)包數(shù)目的變化情況如圖5(a)所示，依據(jù)圖5(a)結(jié)合根據(jù)發(fā)包速率、數(shù)目和傳輸時間的關(guān)系，可轉(zhuǎn)化出源節(jié)點Qmax值隨傳輸時間的變化情況如圖5(b)所示。

圖5 源節(jié)點Qmax值隨發(fā)包數(shù)目和傳輸時間的變化情況

在該網(wǎng)格拓撲中，因為源節(jié)點與目的節(jié)點距離最遠，所以源節(jié)點的Qmax值收斂時間最長。圖5(a)中曲線開始部分Qmax值劇烈下降，在發(fā)包數(shù)為20時開始緩慢減少，說明源節(jié)點從網(wǎng)絡中學習，并獲得接近真實網(wǎng)絡的信息，包括網(wǎng)絡拓撲的運動性、周圍鄰居節(jié)點情況，以及流內(nèi)競爭程度。當發(fā)包數(shù)為40時曲線趨于穩(wěn)定，表明Qmax值基本達到收斂狀態(tài)。曲線穩(wěn)定后也可能小幅波動，因為流內(nèi)競爭導致最佳路徑上的可用帶寬降低，QQR路由算法會根據(jù)獎勵函數(shù)選擇帶寬較高的另一個節(jié)點，此時的路徑可能不是最短路徑。

圖5(a)還反映了源節(jié)點的Qmax值隨數(shù)據(jù)分組傳輸時間的變化情況。源節(jié)點發(fā)包速率為1 pkt/s，考慮“2.1.2鏈路可用帶寬”中的數(shù)據(jù)分組傳輸周期，根據(jù)式(2)計算單個數(shù)據(jù)分組的平均傳輸時間t=5 952 μs。則由圖5(a)可知，在沒有其他業(yè)務流干擾的情況下，源節(jié)點業(yè)務飽和時Qmax值收斂的數(shù)據(jù)分組總傳輸時間約為40t≈0.24 s。在源節(jié)點業(yè)務非飽和以及存在干擾業(yè)務的條件下，節(jié)點Qmax值收斂時間為節(jié)點發(fā)送最后一個(當前仿真場景中為40 pkt)使得Qmax值基本穩(wěn)定的數(shù)據(jù)包之前的所有時間，主要包含所有數(shù)據(jù)包的端到端傳輸時延以及發(fā)包間隔，下面通過靜態(tài)拓撲仿真對其分析討論。

3.2 靜態(tài)拓撲

在1 000 m×1 000 m的方形拓撲中隨機均勻分布25個靜態(tài)節(jié)點，隨機建立6條多跳泊松業(yè)務流。Hello包的廣播間隔設置為0.1 s，仿真時間40 s，統(tǒng)計6條業(yè)務流總的分組投遞率，吞吐量和平均端到端時延，并與LAOD[16]和AODV[17]比較分析。

1)分組投遞率和平均端到端時延隨仿真時間的變化

設置每條業(yè)務流的業(yè)務負載為50 Kbit/s，在40 s的仿真過程中每隔2 s統(tǒng)計一次所有業(yè)務流的總分組投遞率和總平均端到端時延，仿真結(jié)果如圖6(a)和圖6(b)所示。

在靜態(tài)拓撲中，由于網(wǎng)絡節(jié)點靜止不動，LAOD退化為AODV。如圖6(a)所示，當業(yè)務負載保持不變時，LAOD協(xié)議獲得的分組投遞率基本保持在一個穩(wěn)定水平，Poisson業(yè)務流的隨機性會導致統(tǒng)計結(jié)果有一些小范圍波動。因為LAOD協(xié)議同樣通過廣播RREQ分組和應答RREP分組進行路由發(fā)現(xiàn)，而且是按需執(zhí)行該過程，不需要額外的判斷和等待，所以能在較短時間內(nèi)建立路由。然而對于QQR協(xié)議，在仿真初期需要發(fā)送數(shù)據(jù)包來建立并更新Q值表，探索傳輸路徑的過程使得開始階段業(yè)務的分組投遞率比較小。隨著Q值表慢慢收斂，傳輸路徑也逐漸收斂到較優(yōu)路徑，分組投遞率逐漸提高并達到穩(wěn)定水平。靜態(tài)拓撲中鄰居節(jié)點數(shù)和鏈路持續(xù)時間維持恒定，由于QQR協(xié)議還考慮了鏈路可用帶寬，減少了網(wǎng)絡擁塞，因而較LAOD協(xié)議提高了分組投遞率。

圖6 分組投遞率和總平均端到端時延隨仿真時間的變化情況

如圖6(b)所示，在靜態(tài)拓撲條件下，當業(yè)務負載保持不變時，經(jīng)過2 s后LAOD協(xié)議完成路由發(fā)現(xiàn)，通過穩(wěn)定的鏈路傳輸數(shù)據(jù)包，所以平均端到端時延保持在一個平均水平。而QQR協(xié)議初始化時Q值表還未建立，在仿真初期需要發(fā)送一定的數(shù)據(jù)包來建立并更新Q值表，Q值表未收斂時網(wǎng)絡中還不存在完整的轉(zhuǎn)發(fā)路徑，或者轉(zhuǎn)發(fā)路徑較長，造成大量的數(shù)據(jù)包積累，所以仿真開始階段平均端到端時延較LAOD更高。仿真后期隨著Q值表慢慢收斂，逐漸產(chǎn)生穩(wěn)定且跳數(shù)較優(yōu)的傳輸路徑，故而平均端到端時延逐漸變小，最后趨于穩(wěn)定。由于QQR考慮了網(wǎng)絡中鏈路可用帶寬，優(yōu)先選擇可用帶寬較大的鏈路轉(zhuǎn)發(fā)數(shù)據(jù)包，減少了不必要的數(shù)據(jù)包接入排隊，從而提升了時延性能。QQR協(xié)議中穩(wěn)定狀態(tài)與未收斂條件下的時延差值可以看做是Q學習反饋代價在時延性能上的體現(xiàn)。

2)分組投遞率和平均端到端時延隨全網(wǎng)業(yè)務負載的變化

依次改變單條業(yè)務流的負載為100、150、200和250 Kbit/s，統(tǒng)計不同業(yè)務負載條件下的分組投遞率和平均端到端時延，仿真結(jié)果如圖7(a)和圖7(b)所示。小負載條件下2種協(xié)議均保持較高的分組投遞率和較低的平均端到端時延，隨著網(wǎng)絡總負載的增加，分組投遞率下降，平均端到端時延隨之增加。由于考慮到鏈路可用帶寬，QQR協(xié)議會輪換使用負載較輕的節(jié)點當作中繼節(jié)點，從而減少分組沖突和網(wǎng)絡擁塞，因此整體來看QQR的分組投遞率要高于LAOD，同時平均端到端時延比LAOD更小。

圖7 不同業(yè)務負載下的分組投遞率和總平均端到端時延

3.3 運動拓撲

在3.2節(jié)的靜態(tài)拓撲條件下增加節(jié)點的運動性，設置節(jié)點運動模型為random waypoint，停留時間為0 s，最小速率為0 m/s，最大速率依次設置為0、5、10、15和20 m/s，統(tǒng)計全網(wǎng)的丟包率和吞吐量如圖8(a)和圖8(b)所示。隨著節(jié)點運動速率的加快，通信鏈路斷裂變得頻繁，3種協(xié)議下的網(wǎng)絡丟包率均呈增大趨勢，相應的網(wǎng)絡吞吐量不斷減小。然而，通過周期性交互的Hello分組和轉(zhuǎn)發(fā)的數(shù)據(jù)分組，QQR協(xié)議的Q值表得以不斷地更新，Q學習的任務被分配到每一個節(jié)點中，使得算法能夠快速地收斂到最優(yōu)路徑。重要的是QQR協(xié)議綜合考慮了鄰居節(jié)點數(shù)、鏈路持續(xù)時間和鏈路可用帶寬3個指標，對網(wǎng)絡拓撲的變化能夠做出及時的調(diào)整，不需要在拓撲變化導致鏈路斷裂時重啟路由發(fā)現(xiàn)交互控制信息，因此較AODV和LAOD協(xié)議的丟包率更低，吞吐量更大。LAOD協(xié)議考慮了鏈路持續(xù)時間和路由跳數(shù)，能夠?qū)\動拓撲做出反應，故而網(wǎng)絡性能優(yōu)于AODV協(xié)議。當拓撲運動速率增大到一定程度，QQR協(xié)議的性能較LAOD沒有太大優(yōu)勢，因為Q值的收斂需要一定的時間，QQR協(xié)議很難適應運動速率很快的網(wǎng)絡場景，因此需要改進和提高Q值收斂速度以獲得更好的網(wǎng)絡性能。

圖8 不同運動速率下的網(wǎng)絡丟包率和網(wǎng)絡吞吐量

4 結(jié)論

Q-learning作為一種離策略、無模型的啟發(fā)式強化學習方法，為無線自組織網(wǎng)絡路由設計提供了新的思路。本文研究一種基于Q-learning的QoS路由方法，該方法以Q-learning學習框架為基礎(chǔ)，將鄰居節(jié)點數(shù)量、鏈路持續(xù)時間和鏈路可用帶寬作為路由測度，設計了一種提供QoS保證的獎勵函數(shù)。網(wǎng)絡節(jié)點通過廣播Hello消息和發(fā)送數(shù)據(jù)分組交互路由測度信息，并根據(jù)獎勵函數(shù)計算和更新Q值，待轉(zhuǎn)發(fā)數(shù)據(jù)分組的節(jié)點根據(jù)其維護的Q值表智能選擇下一跳轉(zhuǎn)發(fā)節(jié)點。EXata網(wǎng)絡仿真結(jié)果證明了該方法的有效性，該方法能為高動態(tài)飛行自組網(wǎng)提供可靠的通信鏈路。后續(xù)工作將圍繞大規(guī)模網(wǎng)絡和高業(yè)務量場景中Q值表的快速收斂和動態(tài)維護問題展開，將Q-learning與神經(jīng)網(wǎng)絡結(jié)合使用也是未來的研究方向之一。此外，可以搭建無人機或無人車硬件系統(tǒng)，將本文實現(xiàn)的QQR路由算法移植到移動自組網(wǎng)節(jié)點的協(xié)議棧中，對路由算法的耗時性和實時性等性能進行實測。