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

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

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

路由選擇作為網(wǎng)絡(luò)通信的關(guān)鍵技術(shù)之一，決定了數(shù)據(jù)的傳輸路徑，對(duì)網(wǎng)絡(luò)整體性能有著非常重要的影響[2]。然而，在高動(dòng)態(tài)飛行自組織網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)頻繁入網(wǎng)、退網(wǎng)以及快速移動(dòng)，網(wǎng)絡(luò)拓?fù)渥兓欤溌啡菀讛嗔押吐酚芍亟l繁，從而導(dǎo)致數(shù)據(jù)分組丟失嚴(yán)重，網(wǎng)絡(luò)性能嚴(yán)重下降[3-5]。傳統(tǒng)的Ad hoc網(wǎng)絡(luò)路由協(xié)議，例如AODV(ad hoc on-demand distance vector routing)和DSR(dynamic source routing)，難以適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的快速變化，不能保證網(wǎng)絡(luò)的服務(wù)質(zhì)量(quality of service, QoS)。

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

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

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

1 Q-learning與路由重建

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

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

圖1 強(qiáng)化學(xué)習(xí)的基本框架

定義：

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

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

3)獎(jiǎng)勵(lì)(rt)：環(huán)境的即時(shí)反饋值，以評(píng)估智能體選擇的上一個(gè)動(dòng)作。

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

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

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

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

標(biāo)準(zhǔn)Q-learning 的更新公式為

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

(1)

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

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

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

2.1.1 鄰居節(jié)點(diǎn)度

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

2.1.2 鏈路可用帶寬

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

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

圖2 傳輸周期示意圖

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

(2)

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

(3)

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

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

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

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

(4)

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

(5)

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

(6)

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

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

(7)

2.1.3 鏈路持續(xù)時(shí)間

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

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

設(shè)節(jié)點(diǎn)S、R和D的坐標(biāo)分別為(xS,yS)、(xR,yR)和(xD,yD)，節(jié)點(diǎn)移動(dòng)的速度和方向分別為(VS,θS)、(VR,θR)和(VD,θD)，參考文獻(xiàn)[15]，節(jié)點(diǎn)R處于節(jié)點(diǎn)S通信范圍的時(shí)間T(S,R)預(yù)測(cè)為

(8)

其中h為傳輸距離，且

(9)

2.1.4 獎(jiǎng)勵(lì)函數(shù)

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

(10)

定義節(jié)點(diǎn)S到R的瞬時(shí)獎(jiǎng)勵(lì)A(yù)(S,R)為

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

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

(11)

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

根據(jù)瞬時(shí)獎(jiǎng)勵(lì)對(duì)相應(yīng)鄰居節(jié)點(diǎn)的Q值進(jìn)行更新，更新當(dāng)前節(jié)點(diǎn)S對(duì)其鄰居節(jié)點(diǎn)R的質(zhì)量評(píng)估為

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

(12)

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

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

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

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

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

表1 Q值表

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

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

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

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

2)路由維護(hù)

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

2.3 路由方法分析

1)網(wǎng)絡(luò)開銷

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

(13)

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

2)反饋代價(jià)

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

3)收斂時(shí)間

由于Q-learning算法的收斂需要一定的時(shí)間，只有網(wǎng)絡(luò)中所有節(jié)點(diǎn)的Q值收斂后，建立的路由才會(huì)逼近最佳路由。然而對(duì)于拓?fù)溥\(yùn)動(dòng)的網(wǎng)絡(luò)，可能存在Q學(xué)習(xí)還未收斂時(shí)，網(wǎng)絡(luò)狀態(tài)已經(jīng)發(fā)生改變的情況，所以要求：①算法收斂時(shí)間內(nèi)網(wǎng)絡(luò)拓?fù)洳荒軇×易兓荒軐?dǎo)致Q值總是與穩(wěn)態(tài)值存在很大的偏差；②Hello包更新時(shí)間要小于算法收斂時(shí)間，且如果網(wǎng)絡(luò)拓?fù)渥兓^快，更新時(shí)間應(yīng)該取較小的值，從而保證鄰居節(jié)點(diǎn)能夠及時(shí)報(bào)告網(wǎng)絡(luò)狀態(tài)。

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

3.1 收斂分析

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

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

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

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

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

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

3.2 靜態(tài)拓?fù)?/h3>

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

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

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

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

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

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

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

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

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

3.3 運(yùn)動(dòng)拓?fù)?/h3>

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

圖8 不同運(yùn)動(dòng)速率下的網(wǎng)絡(luò)丟包率和網(wǎng)絡(luò)吞吐量

4 結(jié)論

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