高翔，馬少斌，張成文

(蘭州文理學(xué)院數(shù)字媒體學(xué)院，甘肅 蘭州 730000)

認(rèn)知無線電(cognitive radio,CR)技術(shù)允許未注冊(cè)的節(jié)點(diǎn)以機(jī)會(huì)形式使用已注冊(cè)的頻譜資源。將CR應(yīng)用于移動(dòng)自組網(wǎng)(mobile ad hoc network,MANETs)[1]，可以有效地提高M(jìn)ANETs的頻譜利用率[2]。

然而，由于MANETs中設(shè)備移動(dòng)性，如何有效地分配資源進(jìn)而形成最佳路由是CR-MANETs網(wǎng)絡(luò)亟待解決的問題。目前，CR-MANETs中多數(shù)路由是以泛洪方式在整個(gè)網(wǎng)絡(luò)內(nèi)尋找最佳路由，這消耗了大量資源，如控制開銷、頻譜、時(shí)延和能量[3]。

此外，由于物聯(lián)網(wǎng)的快速發(fā)展，其對(duì)通信效率、時(shí)延和頻譜資源的利用率提出了更高要求。為此，研究都對(duì)CR-MANETs的路由進(jìn)行了大量研究。例如：文獻(xiàn)[4]提出基于能效分簇的多跳路由；文獻(xiàn)[5]提出基于分配集連通的簇路由，其通過構(gòu)建穩(wěn)定的簇，提高路由性能，如控制開銷、數(shù)據(jù)包傳遞率和數(shù)據(jù)傳輸時(shí)延。

近期，為了提高無線網(wǎng)絡(luò)的路由性能，研究者將深度學(xué)習(xí)算法應(yīng)用于路由[6-8]。例如：文獻(xiàn)[6]針對(duì)CR-MANETs網(wǎng)絡(luò)，提出基于深度Q-學(xué)習(xí)的路由，旨在減少端到端傳輸時(shí)延；文獻(xiàn)[9]提出基于Q-學(xué)習(xí)自適應(yīng)路由模型(Q-learning based adaptive routing model,QLAR)，其引用增強(qiáng)學(xué)習(xí)技術(shù)對(duì)節(jié)點(diǎn)的移動(dòng)情況進(jìn)行檢測(cè)，進(jìn)而使每個(gè)節(jié)點(diǎn)能夠自動(dòng)地更新路由指標(biāo)。

作為增強(qiáng)學(xué)習(xí)的分支，博弈論成為構(gòu)建簇的有效方法[2]。文獻(xiàn)[2]提出基于博弈論的簇路由，其利用博弈論構(gòu)建穩(wěn)定簇，進(jìn)而控制開銷。

受上述文獻(xiàn)的啟發(fā)，本文針對(duì)CR-MANETs網(wǎng)絡(luò)特點(diǎn)，提出了基于深度Q學(xué)習(xí)的穩(wěn)定路由。本文的主要工作如下：(1)利用深度Q學(xué)習(xí)模型(deepQ-learning,DQL)建立低成本路由。通過節(jié)點(diǎn)隊(duì)列尺寸空間和鏈路的連通時(shí)間構(gòu)成鏈路成本；(2)通過DQL模型選擇具有最小Q值的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，形成穩(wěn)定路由。

1 系統(tǒng)模型

考慮如圖1所示的CR-MANETs網(wǎng)絡(luò)模型，CR-MANETs由多個(gè)次級(jí)用戶(secondary users,SU)和一個(gè)主級(jí)用戶(primary user,PU)構(gòu)成。由于PU的通信半徑受限，它只有有限的通信區(qū)域。

將每個(gè)SU看成一個(gè)移動(dòng)節(jié)點(diǎn)，并且SU遵照隨機(jī)waypoint模型(random waypoint model,RWM)在二維平面內(nèi)移動(dòng)。圖中的空心圓圈表示移動(dòng)節(jié)點(diǎn)(SU)。

此外，假定節(jié)點(diǎn)通過全球定位系統(tǒng)[10]或者其他定位算法能夠估計(jì)自己的位置和目的節(jié)點(diǎn)的位置。同時(shí)，假定每個(gè)節(jié)點(diǎn)有固定的通信范圍。網(wǎng)絡(luò)內(nèi)的控制包沿著控制信道傳輸，其不影響PU的已注冊(cè)信道的性能。本文引用兩類控制包：RREQ和RREP。RREQ包表示路由請(qǐng)求包，即源節(jié)點(diǎn)向目的節(jié)點(diǎn)請(qǐng)求構(gòu)建路由的控制包；RREP包表示路由回復(fù)包，即目的節(jié)點(diǎn)回復(fù)源節(jié)點(diǎn)的控制包，如圖1所示。

圖1 網(wǎng)絡(luò)模型

2 DQLR路由

2.1 DQLR路由概述

DQLR路由按周期運(yùn)行，且每個(gè)周期劃分為路由建立階段和數(shù)據(jù)傳輸階段。在路由建立階段，源節(jié)點(diǎn)通過傳遞RREQ包構(gòu)建路由；在傳輸數(shù)據(jù)階段，源節(jié)點(diǎn)依據(jù)已構(gòu)建的路由向目的節(jié)點(diǎn)傳輸數(shù)據(jù)包。

2.2 路由建立階段

若源節(jié)點(diǎn)需要向目的節(jié)點(diǎn)傳輸數(shù)據(jù)，且源節(jié)點(diǎn)目前沒有通往該目的節(jié)點(diǎn)路由時(shí)，源節(jié)點(diǎn)就向其周圍節(jié)點(diǎn)交互Hello包，進(jìn)而與鄰居節(jié)點(diǎn)建立鄰居關(guān)系。

隨后，源節(jié)點(diǎn)就產(chǎn)生一個(gè)RREQ包，然后將具有最小Q值的鄰居節(jié)點(diǎn)作為最佳鄰居節(jié)點(diǎn)(best neighbor node,BNN)，并將RREQ包傳輸至此BNN。利用DQL模型計(jì)算鄰居節(jié)點(diǎn)的Q值。

如果一個(gè)節(jié)點(diǎn)收到RREQ包，它就將發(fā)送節(jié)點(diǎn)作為上一跳節(jié)點(diǎn)存入路由表中。然后此節(jié)點(diǎn)再將此RREQ包轉(zhuǎn)發(fā)至它的BNN，重復(fù)上述過程，直到RREQ包被傳輸至目的節(jié)點(diǎn)，如圖2(a)所示。

一旦目的節(jié)點(diǎn)接收RREQ包，目的節(jié)點(diǎn)就沿著傳輸RREQ包的反向路徑回復(fù)RREP包，直到RREP被傳輸至源節(jié)點(diǎn)，如圖2(b)所示。

2.3 鏈路成本函數(shù)

DQLR路由依據(jù)節(jié)點(diǎn)的隊(duì)列空間和鏈路的穩(wěn)定計(jì)算鏈路成本。為了簡化表述，令si表示源節(jié)點(diǎn)。Ni表示節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)集。對(duì)于Ni內(nèi)的任意一個(gè)節(jié)點(diǎn)sj，源節(jié)點(diǎn)si鏈路li,j的成本：

(1)

式中：li,j表示由si與sj形成的鏈路；Qz(j)表示節(jié)點(diǎn)sj的隊(duì)列空間；Qz，max表示最大的隊(duì)列空間；r(li,j)表示鏈路li,j的穩(wěn)定值；α1和α2表示權(quán)值系數(shù)，且α1+α2=1。

2.4 鏈路li,j的穩(wěn)定值

假定節(jié)點(diǎn)的移動(dòng)速度服從正態(tài)分布[11]。令?i表示節(jié)點(diǎn)si的移動(dòng)速度。因此，移動(dòng)速度?i的概率分布函數(shù)：

(2)

式中：g(?i)表示概率密度函數(shù)，則有

(3)

式中：μ,σ2分別表示速度的均值、方差[12]。

依據(jù)節(jié)點(diǎn)si與節(jié)點(diǎn)sj的相對(duì)移動(dòng)速度，可計(jì)算鏈路li,j的持續(xù)時(shí)間ti,j：

(4)

式中：di,j表示節(jié)點(diǎn)si與節(jié)點(diǎn)sj間距離；Δ?i,j表示它們的相對(duì)速度。

結(jié)合式(6)，計(jì)算ti,j的概率密度函數(shù)f(ti,j)：

(5)

最后，依據(jù)式(6)計(jì)算鏈路的穩(wěn)定li,j的穩(wěn)定值[13]：

(6)

2.5 最小端到端成本

(7)

式(7)表示端到端成本。DQLR路由旨在建立從源節(jié)點(diǎn)至目的節(jié)點(diǎn)的最小端到端成本路由，將其稱為最小端到端成本(minimum end-to-end cost,MEC)。

2.6 深度Q-學(xué)習(xí)模型

DQLR路由引用深度Q-學(xué)習(xí)選擇下一跳節(jié)點(diǎn)。深度Q-學(xué)習(xí)算法主要由代理(Agent)、狀態(tài)(State)、動(dòng)作(Action)、環(huán)境(Environment)和獎(jiǎng)懲函數(shù)(Reward Function)5個(gè)因素組成。Agent根據(jù)所在的狀態(tài)，選擇不同的動(dòng)作，動(dòng)作作用于環(huán)境形成獎(jiǎng)懲函數(shù)。再依據(jù)獎(jiǎng)懲函數(shù)，對(duì)動(dòng)作進(jìn)行修正。

Agent：在DQLR路由中，假定源節(jié)點(diǎn)旁邊有一個(gè)機(jī)器人。該機(jī)器人在滿足MEC條件下尋找通往目的節(jié)點(diǎn)的最佳路由。因此，將機(jī)器人稱為Agent。

State：機(jī)器人擁有一個(gè)狀態(tài)集S，其為節(jié)點(diǎn)集N。在特定時(shí)刻，如果機(jī)器人位于節(jié)點(diǎn)sk∈N，則認(rèn)為機(jī)器人位于狀態(tài)sk。

Action：若機(jī)器人移到節(jié)點(diǎn)sk，則此時(shí)它處于狀態(tài)sk。令NBk表示節(jié)點(diǎn)sk的動(dòng)態(tài)鄰居節(jié)點(diǎn)集。機(jī)器人有|NBk|個(gè)選擇移動(dòng)的位置。因此，將NBk作為處于狀態(tài)sk時(shí)Agent的動(dòng)作集Ak，將sj∈Ak作為處于狀態(tài)sk時(shí)的一個(gè)動(dòng)作。

Environment：當(dāng)Agent處于狀態(tài)sk時(shí)，它具有一個(gè)環(huán)境，其包括網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)的位置、速度以及節(jié)點(diǎn)的隊(duì)列尺寸。

Reward Function：當(dāng)Agent處于狀態(tài)si時(shí)，它選擇一個(gè)動(dòng)作sj∈Ai，所產(chǎn)生的獎(jiǎng)勵(lì)值：

(8)

式中：λ1，λ2為權(quán)重系數(shù)，且λ1+λ2=1；wgth表示跳數(shù)權(quán)重值，且wgth∈(0,1)。最初，λ1=1，λ2=0。隨著深度Q-學(xué)習(xí)算法的迭代，源節(jié)點(diǎn)利用Q-值構(gòu)建通往目的節(jié)點(diǎn)的路由。如果所構(gòu)建的路由的跳數(shù)高于預(yù)定的路由跳數(shù)值hopthres，則對(duì)λ1和λ2值進(jìn)行調(diào)整：λ1=λ1-0.1，λ2=λ2+0.1。

2.7 Q值的更新

當(dāng)Agent處于狀態(tài)si時(shí)，它選擇一個(gè)動(dòng)作sj∈Ai，它所形成的Q值：

(9)

2.8 基于節(jié)點(diǎn)Q值的路由步驟

DQLR路由Q值選擇下一跳節(jié)點(diǎn)，該Q值包含了基于隊(duì)列尺寸和鏈路穩(wěn)定性的成本值。網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)依據(jù)以下流程執(zhí)行：

Step 1：如果節(jié)點(diǎn)si是源節(jié)點(diǎn)，其就進(jìn)入Step1.1，否則就進(jìn)入Step2。

Step1.1：如果源節(jié)點(diǎn)si需要向目的節(jié)點(diǎn)dst傳輸數(shù)據(jù)Data，si就廣播請(qǐng)求包(Request Information Packet,RIP)獲取鄰居節(jié)點(diǎn)的位置、速度以及鄰居節(jié)點(diǎn)的隊(duì)列尺寸，再進(jìn)入Step1.2。如果源節(jié)點(diǎn)si不需要向dst傳輸數(shù)據(jù)包，就直接進(jìn)入第3步(Step3)。

Step1.2：源節(jié)點(diǎn)si就計(jì)算鄰居節(jié)點(diǎn)的成本值，并從鄰居節(jié)點(diǎn)中選擇具有最小Q值的節(jié)點(diǎn)，將此節(jié)點(diǎn)作為下一跳鄰居節(jié)點(diǎn)(假定是節(jié)點(diǎn)s*)。源節(jié)點(diǎn)si就向節(jié)點(diǎn)s*傳輸RREQ包。然后進(jìn)入Step3。

Step2：如果節(jié)點(diǎn)si不是源節(jié)點(diǎn)，就進(jìn)入Step2.1，否則就進(jìn)入Step2.3。

Step2.1：如果節(jié)點(diǎn)si從源節(jié)點(diǎn)接收了RREQ包，它就記錄發(fā)送節(jié)點(diǎn)(源節(jié)點(diǎn))的ID，并將其作為自己的上一跳節(jié)點(diǎn)，然后節(jié)點(diǎn)si就向鄰居節(jié)點(diǎn)廣播RIP包，進(jìn)而獲取鄰居節(jié)點(diǎn)的位置、速度以及鄰居節(jié)點(diǎn)的隊(duì)列尺寸，并進(jìn)入Step2.2。

Step2.2：節(jié)點(diǎn)si就計(jì)算鄰居節(jié)點(diǎn)的成本值，并從鄰居節(jié)點(diǎn)中選擇具有最小Q值的節(jié)點(diǎn)，將此節(jié)點(diǎn)作為下一跳鄰居節(jié)點(diǎn)，并向此節(jié)點(diǎn)傳輸RREQ包。然后進(jìn)入Step3。

Step2.3：如果目的節(jié)點(diǎn)dst接收一個(gè)RREQ包，就將產(chǎn)生RREP，并向源節(jié)點(diǎn)回復(fù)RREP包，再進(jìn)入Step4。

Step3：如果節(jié)點(diǎn)si從目的節(jié)點(diǎn)dst接收了RREP包，就進(jìn)入Step3.1，否則就進(jìn)入Step4。

Step3.1：如果節(jié)點(diǎn)si不是源節(jié)點(diǎn)，它就將RREP轉(zhuǎn)發(fā)到它的上一跳節(jié)點(diǎn)，并記錄傳輸RREP包的ID，并將其作為自己下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，再進(jìn)入Step4。若節(jié)點(diǎn)si是源節(jié)點(diǎn)，就進(jìn)入Step3.2。

Step3.2：節(jié)點(diǎn)si是源節(jié)點(diǎn)，就將傳輸RREP的發(fā)送節(jié)點(diǎn)作為自己的下一跳節(jié)點(diǎn)，并將寫入路由表，將數(shù)據(jù)Data傳輸至該下一跳節(jié)點(diǎn)，再進(jìn)入Step4。

Step4：路由結(jié)束。

3 性能仿真

3.1 仿真環(huán)境

為了更好地分析算法性能，利用SimPy仿真框架建立仿真平臺(tái)。50個(gè)移動(dòng)節(jié)點(diǎn)(SUs)和一個(gè)PU分布于1 km×1 km的區(qū)域。移動(dòng)節(jié)點(diǎn)依據(jù)RMM模型在區(qū)域內(nèi)移動(dòng)。令?max表示最大的移動(dòng)速度。仿真區(qū)域?yàn)? km×1 km；移動(dòng)節(jié)點(diǎn)數(shù)為50個(gè)；節(jié)點(diǎn)通信半徑和PU的通信半徑均為250 m；數(shù)據(jù)包到達(dá)隊(duì)列率為10 packets/s；學(xué)習(xí)率為0.9；仿真時(shí)間為1 000 s。仿真參數(shù)如表1所示。每次實(shí)驗(yàn)獨(dú)立進(jìn)行20次，取平均值作為最終的實(shí)驗(yàn)數(shù)據(jù)。

此外，選擇LSR路由[13]和QLAR路由[9]作為參照，并與 DQLR路由進(jìn)行性能比較，分析它們時(shí)延、開銷和數(shù)據(jù)包傳遞率性能。

3.2 路由時(shí)延和隊(duì)列時(shí)延的性能

圖3、圖4分別給出DQLR路由、QLAR路由和LSR路由的路由時(shí)延tR和隊(duì)列時(shí)延tQ隨?max的變化情況。從圖3可知，?max值的增加，增加了路由時(shí)延和隊(duì)列時(shí)延。原因在于：?max越大，節(jié)點(diǎn)移動(dòng)越多，降低了路由的穩(wěn)定性。

?max/(km·h-1)

?max/(km·h-1)

此外，相比于LSR路由，DQLR路由降低了路由時(shí)延和隊(duì)列時(shí)延。這主要是因?yàn)椋篋QLR路由利用通過選擇滿足MEC條件的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，降低了時(shí)延。而LSR路由采用泛洪RREQ包構(gòu)建路由，其需用更長時(shí)延構(gòu)建路由。同時(shí)，LSR路由在選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)并沒有考慮鏈路的穩(wěn)定性，增加了構(gòu)建路由的頻率。

在?max較小時(shí)，DQLR路由的時(shí)延性能劣于QLAR，但是當(dāng)?max在逐步增加時(shí)，QLAR的時(shí)延隨之快速增加，并高于DQLR路由。原因在于：QLAR路由需要檢測(cè)節(jié)點(diǎn)的移動(dòng)速度，并動(dòng)態(tài)地調(diào)整路由指標(biāo)。節(jié)點(diǎn)移動(dòng)速度越大，檢測(cè)難度越大，必然增加了處理時(shí)延。

3.3 數(shù)據(jù)包傳遞率和控制開銷

圖5、圖6分別給出DQLR路由、QLAR路由和LSR路由的控制開銷C和數(shù)據(jù)包傳遞率η隨?max的變化情況。

?max/(km·h-1)

?max/(km·h-1)

從圖5可知，控制開銷C隨?max的增加而上升。這主要是因?yàn)椋?max值的增加，路由的連通時(shí)間短，需要頻繁地構(gòu)建路由，這增加了路由開銷。但相比于LSR路由和QLAR路由，DQLR路由有效地降低控制開銷。原因在于：DQLR路由是利用單播方式向下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)傳輸RREQ包，而LSR路由采用泛洪方式傳輸RREQ包。QLAR路由需要檢測(cè)節(jié)點(diǎn)的移動(dòng)信息，這增加開銷。

此外，從圖6可知，?max的增加降低了數(shù)據(jù)包傳遞率，這符合邏輯。節(jié)點(diǎn)移動(dòng)速度的增加，降低了路由的穩(wěn)定性，最終降低了數(shù)據(jù)包傳遞率。QLAR路由和DQLR路由的數(shù)據(jù)包傳遞率η相近。在?max較低時(shí)，QLAR路由的數(shù)據(jù)包傳遞率略優(yōu)于DQLR路由。但隨著?max的增加，QLAR路由的數(shù)據(jù)包傳遞率逐步低于DQLR路由的數(shù)據(jù)包傳遞率。這主要是因?yàn)椋?max越大，QLAR路由需要實(shí)時(shí)地調(diào)整模型，更新路由指標(biāo)。

4 結(jié)語

針對(duì)認(rèn)知無線電-移動(dòng)自組網(wǎng)的路由問題，提出基于深度Q學(xué)習(xí)的穩(wěn)定路由DQLR。DQLR路由通過深度Q學(xué)習(xí)模型選擇最低成本的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，提高了路由的穩(wěn)定性。仿真結(jié)果表明，DQLR路由降低了控制開銷以及路由時(shí)延，并提高了數(shù)據(jù)包傳遞率。