基于增強(qiáng)學(xué)習(xí)的非協(xié)作認(rèn)知無(wú)線網(wǎng)絡(luò)路由算法研究

楊振宇

(安徽交通職業(yè)技術(shù)學(xué)院 信息工程系，合肥 230051)

無(wú)線通信系統(tǒng)所需的無(wú)線電頻譜是一種有限的資源.隨著各種無(wú)線應(yīng)用的蓬勃發(fā)展，可用的頻譜已經(jīng)越來(lái)越少，頻譜稀缺問(wèn)題日益嚴(yán)重.認(rèn)知無(wú)線電網(wǎng)絡(luò)(Cognitive Radio Networks，CRNs)允許通過(guò)支持動(dòng)態(tài)頻譜接入(DSA)來(lái)提高無(wú)線電頻譜的使用效率.在CRNs中，次用戶(hù)(SUs)只有在主用戶(hù)(PUs)沒(méi)有占用頻譜的情況下才可以使用頻譜資源；當(dāng)PUs需要使用頻譜時(shí)，SUs必須立即停止數(shù)據(jù)傳輸，并將頻譜資源讓給PUs[1].CRNs中的路由利用中間SUs節(jié)點(diǎn)，以多跳方式將源SU的數(shù)據(jù)轉(zhuǎn)發(fā)到目的SU.在設(shè)計(jì)路由算法的時(shí)候需要考慮以下幾個(gè)問(wèn)題：1)CRNs是一個(gè)動(dòng)態(tài)的環(huán)境，所以SUs需要適應(yīng)環(huán)境的變化；2)SUs需要交換大量的路由信息，由于CRNs是一個(gè)分布式的環(huán)境，需要考慮如何優(yōu)化路由算法以減少路由開(kāi)銷(xiāo)；3)由于各個(gè)SUs之間是非協(xié)作的，因此，設(shè)計(jì)路由算法時(shí)考慮到SUs之間的非協(xié)作交互；4)CRN路由協(xié)議設(shè)計(jì)是需要考慮PUs的活動(dòng)模型，在實(shí)現(xiàn)高路由性能的同時(shí)并滿(mǎn)足PU的服務(wù)質(zhì)量(QoS)需求.

1 問(wèn)題建模

1.1 系統(tǒng)模型

假設(shè)CRN中有N個(gè)SUs以及M個(gè)PUs，網(wǎng)絡(luò)中有多個(gè)源SU發(fā)送數(shù)據(jù)包，并以多跳的方式通過(guò)中間SU發(fā)送到目的地SU節(jié)點(diǎn).假設(shè)PUs也在發(fā)送數(shù)據(jù)包，PUs也可以轉(zhuǎn)發(fā)其他PUs的數(shù)據(jù)包.利用離散時(shí)間馬爾科夫泊松過(guò)程(DT-MMPP)來(lái)對(duì)PUs的活動(dòng)進(jìn)行建模[2-3].SUs之間是非協(xié)作的，每個(gè)SU只優(yōu)化自己的路由性能，而不考慮其他SU的路由性能.當(dāng)一個(gè)SU將數(shù)據(jù)包傳輸?shù)降较乱惶?jié)點(diǎn)后，該SU會(huì)收到來(lái)自下一跳SU的確認(rèn)包(ACK).

1.2 問(wèn)題定義

每個(gè)SU的目標(biāo)是選擇下一跳SU節(jié)點(diǎn)來(lái)發(fā)送數(shù)據(jù)包，使其被PU干擾的概率小于給定閾值，從而最小化其端到端時(shí)延.因此，SUi的優(yōu)化問(wèn)題具有如下的形式：

(1)

(2)

Costi(nhi,nh-i)=Di(nhi,nh-i)+Li(nhi,nh-i)

(3)

其中，Li(nhi,nh-i)是干擾的成本，計(jì)算如下：

(4)

B是一個(gè)很大的常數(shù).

1.3 路由問(wèn)題的博弈模型

(5)

其中，Costi(si(t),ai(t),a-i(t))是使用公式(3)計(jì)算，Dmax是最大的時(shí)延.SUi的一個(gè)策略被定義為一個(gè)概率向量[πi(si,ai)]ai∈Ai∈Oi(si)，πi(si,ai)是指在狀態(tài)si選擇動(dòng)作ai的概率.SUi的期望折合成本函數(shù)可以表示為[6]：

(6)

其中，β∈[0,1)是折合因子.

2 基于增強(qiáng)學(xué)習(xí)的路由策略

(7)

(8)

(9)

利用Boltzmann分布[8]，可得以下的結(jié)論：

(10)

(11)

(12)

(13)

將式(12)、(13)代入(7)，可得：

(14)

于是，根據(jù)Boltzmann分布，可以得到SUi的策略如下：

(15)

基于增強(qiáng)學(xué)習(xí)的非協(xié)作路由算法如表1所示.

表1 基于增強(qiáng)學(xué)習(xí)的非協(xié)作路由算法

3 仿真實(shí)驗(yàn)及結(jié)果分析

圖1 端到端時(shí)延對(duì)比

利用NS-2網(wǎng)絡(luò)模擬器，通過(guò)與最短路徑算法進(jìn)行對(duì)比來(lái)評(píng)估本文算法的性能.實(shí)驗(yàn)網(wǎng)絡(luò)中一共有100個(gè)節(jié)點(diǎn)，其中有4個(gè)源Sus，兩個(gè)Pus，其余的是中間SU.模擬實(shí)驗(yàn)場(chǎng)地的大小是1 km2.每一個(gè)SU的傳輸范圍是100 m，PU每秒發(fā)送20個(gè)數(shù)據(jù)包，參數(shù)τ的值是1，β的值是0.5.

圖1和圖2分別是時(shí)延以及SU被干擾概率的實(shí)驗(yàn)結(jié)果.如圖1所示，使用本文的算法，當(dāng)PU可接受干擾的概率增加時(shí)，SU可以更自由地轉(zhuǎn)發(fā)數(shù)據(jù)包，從而減少了緩沖數(shù)據(jù)包的數(shù)量，所以時(shí)延就會(huì)降低.當(dāng)PU可接受干擾的概率低時(shí)，本文算法的延遲會(huì)大于最短路徑算法的延遲.當(dāng)使用本文提出的路由算法時(shí)，在PU可接受干擾的概率低的情況下，SU必須緩沖更多的數(shù)據(jù)包，此時(shí)被轉(zhuǎn)發(fā)的數(shù)據(jù)包就會(huì)變少.這是為了保證PU實(shí)際受到干擾的概率小于PU可接受干擾的概率.當(dāng)PU可接受干擾的概率大于0.8時(shí)，SU緩沖的數(shù)據(jù)包數(shù)量減少，因此時(shí)延會(huì)小于最短路徑算法的延遲.如圖2所示，本文算法所獲得的干擾概率總是小于PU的可接受的干擾概率.圖3是SU數(shù)據(jù)包投遞率的實(shí)驗(yàn)結(jié)果.當(dāng)PU可接受干擾的概率低時(shí)，本文算法的數(shù)據(jù)包投遞率略小于最短路徑算法.這是由于當(dāng)PU可接受干擾的概率低時(shí)，SU需要緩存部分?jǐn)?shù)據(jù)包，以此避免SUs的傳輸會(huì)對(duì)PU造成影響.當(dāng)PU可接受干擾的概率逐漸增大時(shí)，本文算法的數(shù)據(jù)包投遞率要比最短路徑算法的要高.

圖2 SU被干擾的概率

圖3 數(shù)據(jù)包投遞率

4 結(jié)論

本文提出在認(rèn)知無(wú)線電網(wǎng)絡(luò)中的SU的分布式路由方案，SU通過(guò)本地的信息進(jìn)行路由，使用MMPP模型對(duì)PU行為進(jìn)行建模.關(guān)于SU之間是非協(xié)作的，SU需要對(duì)環(huán)境的變化進(jìn)行快速適應(yīng)，將路由問(wèn)題建模為非合作的隨機(jī)學(xué)習(xí)過(guò)程.使用多agent的Q學(xué)習(xí)方法作為路由問(wèn)題的解決方案框架.仿真實(shí)驗(yàn)的結(jié)果顯示出本文算法優(yōu)異的性能.

[1] LIANG Y C,CHEN K C,LI G Y,et al.Cognitive radio networking and communications:an overview[J].IEEE Transactions on Vehicular Technology,2011,60(7):3386-3407.

[2] FU F,SCHAAR M V D.A systematic framework for dynamically optimizing multi-user wireless video transmission[J].IEEE Journal on Selected Areas in Communications,2009,28(3):308-320.

[3] FU F,SCHAAR M V D.Learning to compete for resources in wireless stochastic games[J].IEEE Transactions on Vehicular Technology,2009,58(4):1904-1919.

[4] CHAN W C,LU T C,CHEN R J.Pollaczek-Khinchin formula for the M/G/1 queue in discrete time with vacations[J].IEE Proceedings -Computers and Digital Techniques,2002,144(4):222-226.

[5] ROTH U.Highly dynamic destination-sequenced distance-vector routing[C].Proc Acm Sigcomm94 Aug,1994:234-244.

[6] MOZER S M C,HASSELMO M.Reinforcement learning:an introduction[J].Machine Learning,1992,8(3-4):225-227.

[7] HUSHENG L.Multiagent-learning for aloha-like spectrum access in cognitive radio systems[J].Eurasip Journal on Wireless Communications & Networking,2010,2010(1):1-15.

[8] KIANERCY A,GALSTYAN A.Dynamics of boltzmann Q learning in two-player two-action games.[J].Physical Review E,2011,85(4):1574-1604.