一種基于深度Q學習的移動自組網穩(wěn)定路由

高翔，馬少斌，張成文

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

認知無線電(cognitive radio,CR)技術允許未注冊的節(jié)點以機會形式使用已注冊的頻譜資源。將CR應用于移動自組網(mobile ad hoc network,MANETs)[1]，可以有效地提高MANETs的頻譜利用率[2]。

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

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

近期，為了提高無線網絡的路由性能，研究者將深度學習算法應用于路由[6-8]。例如：文獻[6]針對CR-MANETs網絡，提出基于深度Q-學習的路由，旨在減少端到端傳輸時延；文獻[9]提出基于Q-學習自適應路由模型(Q-learning based adaptive routing model,QLAR)，其引用增強學習技術對節(jié)點的移動情況進行檢測，進而使每個節(jié)點能夠自動地更新路由指標。

作為增強學習的分支，博弈論成為構建簇的有效方法[2]。文獻[2]提出基于博弈論的簇路由，其利用博弈論構建穩(wěn)定簇，進而控制開銷。

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

1 系統(tǒng)模型

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

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

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

圖1 網絡模型

2 DQLR路由

2.1 DQLR路由概述

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

2.2 路由建立階段

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

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

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

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

2.3 鏈路成本函數

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

(1)

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

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

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

(2)

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

(3)

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

依據節(jié)點si與節(jié)點sj的相對移動速度，可計算鏈路li,j的持續(xù)時間ti,j：

(4)

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

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

(5)

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

(6)

2.5 最小端到端成本

(7)

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

2.6 深度Q-學習模型

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

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

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

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

Environment：當Agent處于狀態(tài)sk時，它具有一個環(huán)境，其包括網絡內所有節(jié)點的位置、速度以及節(jié)點的隊列尺寸。

Reward Function：當Agent處于狀態(tài)si時，它選擇一個動作sj∈Ai，所產生的獎勵值：

(8)

式中：λ1，λ2為權重系數，且λ1+λ2=1；wgth表示跳數權重值，且wgth∈(0,1)。最初，λ1=1，λ2=0。隨著深度Q-學習算法的迭代，源節(jié)點利用Q-值構建通往目的節(jié)點的路由。如果所構建的路由的跳數高于預定的路由跳數值hopthres，則對λ1和λ2值進行調整：λ1=λ1-0.1，λ2=λ2+0.1。

2.7 Q值的更新

當Agent處于狀態(tài)si時，它選擇一個動作sj∈Ai，它所形成的Q值：

(9)

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

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

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

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

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

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

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

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

Step2.3：如果目的節(jié)點dst接收一個RREQ包，就將產生RREP，并向源節(jié)點回復RREP包，再進入Step4。

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

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

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

Step4：路由結束。

3 性能仿真

3.1 仿真環(huán)境

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

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

3.2 路由時延和隊列時延的性能

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

?max/(km·h-1)

?max/(km·h-1)

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

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

3.3 數據包傳遞率和控制開銷

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

?max/(km·h-1)

?max/(km·h-1)

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

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

4 結語

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